Alias analysis

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. Two pointers are said to be aliased 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 term alias analysis is often used interchangeably with term points-to analysis, a specific case.

What Does Alias Analysis Do?

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:
#The variables p and q cannot alias.
#The variables p and q must alias.
#It cannot be conclusively determined at compile time if p and q alias or not.

If p and q cannot alias, then i = p.foo + 3; can be changed to i = 4. If p and q must alias, then i = p.foo + 3; can be changed to i = 5. In both cases, we are able to perform optimizations from the alias knowledge. 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 a "may-alias" relation if their aliasing is unknown.

Performing Alias Analysis

In alias analysis, we divide the program's memory into "alias 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-level intermediate 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.

Type Based Alias Analysis

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. There are many cases where we know that two memory locations must be in different alias classes:

#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.
#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.
#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.
#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 A_i and B_j with i,j alias classes, that if i=j then A_i may-alias B_j, and if i eq j then the memory locations will not alias.

Flow Based Alias Analysis

Analysis based on flow, unlike type based analysis, 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.

References

ee also

* Escape analysis
* Pointer analysis
* Shape analysis (software)


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Data-flow analysis — is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program s control flow graph (CFG) is used to determine those parts of a program to which a particular value assigned… …   Wikipedia

  • Shape analysis (software) — Shape analysis is a static code analysis technique that discovers and verifies properties of linked, dynamically allocated data structures in (usually imperative) computer programs. It is typically used at compile time to find software bugs or to …   Wikipedia

  • Escape analysis — In programming language compiler optimization theory, escape analysis is a method for determining the dynamic scope of pointers. It is related to pointer analysis and shape analysis.When a variable (or an object) is allocated in a subroutine, a… …   Wikipedia

  • Pointer analysis — In computer science pointer analysis, or points to analysis, is a static code analysis technique that establishes which pointers, or heap references, can point to which variables or storage locations. It is often a component of more complex… …   Wikipedia

  • Oxford Capacity Analysis — This article is about the Church of Scientology personality test. For other uses, see Oxford (disambiguation). Sign advertising Scientology personality tests. San Francisco, April 2006. The Oxford Capacity Analysis (OCA), also known as the… …   Wikipedia

  • Marcus Dixon (Alias) — Marcus Dixon Alias character Portrayed by Carl Lumbly Information Gender Male Occupation SD 6 field agent …   Wikipedia

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • Compiler — This article is about the computing term. For the anime, see Compiler (anime). A diagram of the operation of a typical multi language, multi target compiler A compiler is a computer program (or set of programs) that transforms source code written …   Wikipedia

  • Автоматическое распараллеливание — Автоматическое распараллеливание  оптимизация программы компилятором, состоящая в автоматическом ее преобразовании в форму, работающую на параллельном компьютере, например, на SMP или NUMA машине. Целью автоматизации распараллеливания… …   Википедия

  • Frameworks supporting the polyhedral model — Use of the polyhedral model within a compiler requires software to represent the objects of this framework (sets of integer valued points in regions of various spaces) and perform operations upon them (e.g., testing whether the set is empty). Two …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”