Alias analysis

Alias analysis is a technique in compiler theory, used to determine if a storage location may be accessed in more than one way.

Alias analysers intend to make and compute useful information for understanding aliasing in programs.

In both cases, we are able to perform optimizations from the alias knowledge (assuming that no other thread updating the same locations can interleave with the current thread, or that the language memory model permits those updates to be not immediately visible to the current thread in absence of explicit synchronization constructs).

On the other hand, if it is not known if p and q alias or not, then no optimizations can be performed and the whole of the code must be executed to get the result.

For the discussion here, it is assumed that the optimizations done here occur on a low-level intermediate representation of the program.

If the language being compiled is type safe, the compiler's type checker is correct, and the language lacks the ability to create pointers referencing local variables, (such as ML, Haskell, or Java) then some useful optimizations can be made.

[1] There are many cases where we know that two memory locations must be in different alias classes: When performing alias analysis for code, every load and store to memory needs to be labeled with its class.

Analysis based on flow, can be applied to programs in a language with references or type-casting.

In flow based analysis, new alias classes are created for each memory allocation, and for every global and local variable whose address has been used.