This article includes alist of references,related reading, orexternal links,but its sources remain unclear because it lacksinline citations. Please helpimprove this article byintroducing more precise citations.(April 2009) (Learn how and when to remove this message)

Alias analysis is a technique incompiler theory, used to determine if a storage location may be accessed in more than one way. Two pointers are said to bealiased if they point to the same location.

Alias analysis techniques are usually classified by flow-sensitivity and context-sensitivity. They may determine may-alias or must-alias information. The termalias analysis is often used interchangeably withpoints-to analysis, a specific case.

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

In general, alias analysis determines whether or not separate memory references point to the same area of memory. This allows the compiler to determine what variables in the program will be affected by a statement. For example, consider the following section of code that accesses members of structures:

p.foo=1;q.foo=2;i=p.foo+3;

There are three possible alias cases here:

1. The variables p and q cannot alias (i.e., they never point to the same memory location).
2. The variables p and q must alias (i.e., they always point to the same memory location).
3. It cannot be conclusively determined at compile time if p and q alias or not.

If p and q cannot alias, theni = p.foo + 3; can be changed toi = 4. If p and q must alias, theni = p.foo + 3; can be changed toi = 5 becausep.foo + 3 =q.foo + 3. In both cases, we are able to perform optimizations from the alias knowledge (assuming that no otherthread updating the same locations can interleave with the current thread, or that the languagememory model permits those updatesto be not immediately visible to the current thread in absence of explicitsynchronization 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. Two memory references are said to have amay-alias relation if their aliasing is unknown.

In alias analysis, we divide the program's memory intoalias classes. Alias classes are disjoint sets of locations that cannot alias to one another. For the discussion here, it is assumed that the optimizations done here occur on a low-levelintermediate representation of the program. This is to say that the program has been compiled into binary operations, jumps, moves between registers, moves from registers to memory, moves from memory to registers, branches, and function calls/returns.

If the language being compiled istype safe, the compiler's type checker is correct, and the language lacks the ability to create pointers referencing local variables, (such asML,Haskell, orJava) 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:

1. Two variables of different types cannot be in the same alias class since it is a property of strongly typed, memory reference-free (i.e., references to memory locations cannot be changed directly) languages that two variables of different types cannot share the same memory location simultaneously.
2. Allocations local to the current stack frame cannot be in the same alias class as any previous allocation from another stack frame. This is the case because new memory allocations must be disjoint from all other memory allocations.
3. Each record field of each record type has its own alias class, in general, because the typing discipline usually only allows for records of the same type to alias. Since all records of a type will be stored in an identical format in memory, a field can only alias to itself.
4. Similarly, each array of a given type has its own alias class.

When performing alias analysis for code, every load and store to memory needs to be labeled with its class. We then have the useful property, given memory locations${\displaystyle A_i}$ and${\displaystyle B_j}$ with${\displaystyle i,j}$ alias classes, that if${\displaystyle i=j}$ then${\displaystyle A_i}$ may-alias${\displaystyle B_j}$, and if${\displaystyle i\ne j}$ then the memory locations will not alias.

Analysis based on flow, can be applied to programs in a language with references or type-casting. Flow based analysis can be used in lieu of or to supplement type based analysis. 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. References may point to more than one value over time and thus may be in more than one alias class. This means that each memory location has a set of alias classes instead of a single alias class.

• Escape analysis
• Pointer analysis
• Shape analysis

• Appel, Andrew W. (1998).Modern Compiler Implementation in ML. Cambridge, UK: Cambridge University Press.ISBN 0-521-60764-7.

• Taxonomy and applications of alias analysis - Master's Thesis giving an introduction to the field.

• Static program analysis

• Articles lacking in-text citations from April 2009
• All articles lacking in-text citations