Introduction

Overview

Alias Analysis is a standard component of today's optimizing compilers and automated program analysis tools. Due to the great variety of requirements regarding precision and speed, many different algorithms have been developed for this problem. This places a considerable burden on the engineer to decide which one is most appropriate in the application at hand.
AAL (Alias Analysis Library) has been developed as part of a Master's Thesis with the intent to give especially smaller projects an easy-to-use library to perform alias analysis at a much lower cost. In a second step this library has then been used to develop a static checker tool, based on the ideas of Calysto.

What is alias analysis?

Take a look at the following piece of C code:
1: int *x = initialize(); 2: int *y = initialize(); 3: 4: *x = 42; 5: 6: if (someCondition) 7: *y = 0; 8: 9: printf("%d\n", *x);
If the compiler is able to deduct statically at compile-time that 'x' and 'y' never point to the same location at runtime, it may optimize this code by replacing the load from memory on line 9 ('*x') with the value that will be loaded (42). As it was deducted that 'y' may never point to the same location as 'x' the store on line 7 ('*y = 0;') cannot override the store from line 4 ('*x = 42;'). Similarly, if the compiler proves that 'x' and 'y' always point to the same location, it may again optimize the code based on this information.

In the first case, where 'x' and 'y' never point to the same location, this code could be generated:
1: int *x = initialize(); 2: int *y = initialize(); 3: 4: *x = 42; 5: 6: if (someCondition) 7: *y = 0; 8: 9: printf("%d\n", 42);

In the second case, where 'x' and 'y' always point to the same location, this code could be generated:
1: int *x = initialize(); 2: initialize(); 3: 4: *x = 42; 5: 6: if (someCondition) { 7: *x = 0; 8: printf("%d\n", 0); 9: } 10: else 11: printf("%d\n", 42);