Current Alias Analysis

• interprocedurally
• intraprocedurally
• never

• Bjarne Steensgaard's Algorithm
  • a rich points-to set describes the variables
  • interprocedural flow-insensitive analysis
  • almost-linear time complexity
  • linear space complexity
  • based upon type-inference methods
• a Simple Algorithm which uses a single points-to set

Relevant Statements in Alias Analysis

   x = y
   x = &y
   x = *y
   x = op(y1, ... yn)
   x = allocate(y)
   *x = y
   x = ftn(f1, ..., fn) => (r1, ..., rm)
   x1, ..., xm = p(y1, ..., pn)

Storage Shape Graph

Type-based Alias Analysis

• Requires strongly typed language
• Typing rules, one for each relevant statement, define constraints needed to infer a set of types (for a program) that is conservative
• The alpha types describe values - a value type is a pair including a function type and a location type
• The tau types describe locations or pointers to locations
• The lambda types describe functions or pointers to functions
• All types are initialized to be bottom

Type Variable Productions

Type-based Alias Analysis Steps

• Assign each variable in the program a unique type variable
• Set each type variable to initially be
• Each statement in program is processed exactly once.
• Type variables are joined as necessary.
• Conditional joins permit a type variable with type to have a list of other types to join with should it become anything other than .

Fred Chow, Sun Chan, Shin-Ming Liu, Raymond Lo and Mark Streich. "Effective Representation of Aliases and Indirect Memory Operations in SSA Form", In Compiler Construction, 6th International Conference, CC'96, Linkoping, Sweden, Apr 1996.