Browse Prior Art Database

Computing the Aliasing Relation

IP.com Disclosure Number: IPCOM000059706D
Original Publication Date: 1986-Jan-01
Included in the Prior Art Database: 2005-Mar-08
Document File: 4 page(s) / 20K

Publishing Venue

IBM

Related People

Gurevich, L: AUTHOR [+3]

Abstract

A method of computing an aliasing relation using an on-line transitive closure algorithm is described. Optimizing compilers must compute a number of complex relations over the objects found in the source program. Among these is the alias relation. Two names in a program are termed aliases if both may refer to the same storage location at some point in the program. The two names x and y are aliases if there is a name z, associated with a storage location, such that x renames z and y renames z. This ignores scoping considerations which can obviously be dealt with separately. Two names may refer to the same storage location if: 1. Statements in the program can directly cause one name to be aliased with a second.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 25% of the total text.

Page 1 of 4

Computing the Aliasing Relation

A method of computing an aliasing relation using an on-line transitive closure algorithm is described. Optimizing compilers must compute a number of complex relations over the objects found in the source program. Among these is the alias relation. Two names in a program are termed aliases if both may refer to the same storage location at some point in the program. The two names x and y are aliases if there is a name z, associated with a storage location, such that x renames z and y renames z. This ignores scoping considerations which can obviously be dealt with separately. Two names may refer to the same storage location if: 1. Statements in the program can directly cause one name to be aliased with a second. For example, the "call by reference of a procedure constant" which makes each formal parameter refer to the same storage as the corresponding actual argument. 2. Certain assignments have aliasing consequences. For example, if the set of possible values which a procedure variable can receive is known, then the actuals at each call point can be aliased with the corresponding formals. Another common example is the assignment of pointers. If the pointer p can have the address of x as a possible value, then references made through p can refer to the same storage as x. Some languages try to reduce the effects of the second type by not allowing procedure variables, by typing pointers or by restricting the use of expressions which return addresses. It is possible to compute correct but overly conservative aliasing information by assuming that all variables receive all possible values. The formulation herein described attempts to provide a more effective analysis but does not consider flow information. The following relations over the objects in the program are defined: 1. DA = {<x,y> there as a direct assignment x := y in the program} 2. DR = {<x,y> there is a statement which directly renames y to be x} An example would be a call by reference which has y as a formal and x as the corresponding actual. 3. VAL = {<x,y> y is a possible value for x} 4. A = {<x,y> x and y are aliases} Also, the function f: f(x,y) = {<u,v> v renames u if x receives the value y} Relations 1 and 2 can be constructed by a single scan of the program. Information used in computing f can also be constructed in this scan. Relations 3 and 4 can be calculated as the solution of: 1. VAL = (A$DA)*
2. RENAMES = (f(VAL) DR)* 3. A = RENAMES$RENAMESt where * is the reflexive transitive closure and t is the transpose. These equations reformulate work done by Weihl. The equations can be simplified if f preserves the transitive closure (i.e., if f(S*) = f(S)*). In particular, if f(x,y) = (g(x), g(y)) where g is any function, then f preserves the transitive closure. This is the case in most real programming languages; for example, given the pointer assignment p = q, the indirect aliases are between objects referenced via p and objects reference...