• Part I: Fundamentals of alias analysis
• Part II: Inter-procedural alias analysis - a survey
• Part III: Assembly level alias analysis
• Part IV: References

This part severs as an introduction and overview of alias analysis:

• Different alias representations in literature.
• Motivation and application of alias analysis.
• Intra-procedural alias analysis.
• Overview of alias analysis in current practice and research activities.

• What is alias?
  • Two variables referring to the same memory location.
    
  • For example, in C, if p = &i, then <*p, i> is an alias pair.
• Representations of alias relation in literature.
  
  • Complete alias pairs: store all alias pairs explicitly, such as in [Landi et al.'92].
  • Compact alias pairs: store only basic alias pairs, and derive new alias pairs by dereference, transitivity and commutativity, such as in [Choi et al.'93].
  • Points-to relations: points-to pairs to indicate one variable is pointing to anothe, such as in [Emmai'93]
• An example: "q=&p; p=&i; r=&i;"
  • Complete: <*q,p> <*p,i> <*r,i> <**q,p> <**q,i> <*p,*r> <**q,*r>
  • Compact: <*q,p> <*p,i> <*r,i>
  • Points-to: (q,p) (p,i) (r,i)
• Must-alias and maybe-alias
  

• Alias analysis are needed for
  • More accurate memory dependence analysis and data flow analysis.
  • More aggressive optimization and scheduling. Without alias analysis, data flow analysis, optimization and scheduling have to be conservative.
• An example:
  • Without alias information: no optimization and wide-issue scheduling for   
         r1 = M[A];
         M[B] = r2;
         r3 = M[A];
         r5 = r3 +r4;
    
  • With alias information: assume A and B are shown not alias, now can eliminate redundant load/store and schedule code
         r1 = M[A];    M[B] = r2;
         r5 = r1 + r4;
    
• To get alias information, the intra-procedural alias analysis ......

• Iterative data flow analysis framework
  • Like standard data flow analysis, such as reaching definition analysis, see figure below.
  • Gen(N) = set of points-to pairs generated by Node N.
  • Kill(N) = set of points-to pairs killed by Node N .
  • Forward order: Out(N) = Gen(N) +(In(N) - Kill(N));
  • 
    
    
• A simple example:
  • Control flow graph:
    
  • Iteration 1:
    
  • Iteration 2:
    
• A more complicated example here with complex language features ......

• Function calls
  • will formal parameters and global variables be changed?
• Function pointers
  • how to resolve function pointers?
• Aggregate data structure
  • how to handle struct and union?
• Heap objects
  • how to include heap object?
• Recursive data structure
  • will it lead to infinite number of alias?
• Pointer arithmetic
  • will points-to relations change due to pointer arithmetic?
• Type casting
  • what to do if a variable is type-casted?

• Research started in late 1970s.
• Moderate alias analysis implemented in commercial compilers, like gcc and DEC
• Aggressive alias analysis still in research stage.
• Classifications of existing alias analysis:
  • Intra-procedural: isolated functions only.
  • Inter-procedural: consider function calls and their interactions;
  • Type-based techniques: use type information to decide alias.
  • Flow-based techniques: consider alias generated by flow of statement.
• A view by graph:
  

This part surveys several recent inter-procedural alias analysis algorithms in literature:

• Inter-procedural frameworks
• Other advanced issues
  • Abstract data representations
  • Recursive and aggregate data structure
  • Heap objects
  • Function pointers and recursive function calls

Algorithms are grouped into 4 groups according to their inter-procedural frameworks:

• Group #1: Inter-procedural control flow graph (ICFG).
  • [Landi et al.'92]
  • [Landi et al.'93]
• Group #2: Invocation graph (IG).
  • [Emami'93, Emami et al'94]
  • [Wilson et al'95]
• Group #3: Procedural call graph (PCG)
  • [Choi et al'93]
  • [Burke et al'95]
• Group #4: Context-sensitive PCG
  • [Ryder et al'99]
  • [Cheng et al'00]

• Inter-procedural control flow graph [Landi et al'92 93].
  • Connection of isolated control flow graphs.
  • Call node and Return node added.
  • Entry node and Exit node added (see figure below).
• 
  
• Problems:
  • Poor efficiency and scalebility - ICFG can be very large.
  • inaccuracy: context insensitivity - can not distinguish different calls of the same procedure (e.g. foo() can not distinguish call sites C1 and C2, therefore a spurious points-to pair (b,e) is generated at call site C2).
• How to get context sensitivity?
  • one solution: Invocation Graph

• Invocation graph (IG) [Emami '93]
  • Fully context sensitive.
  • Each call sites - a node in IG.
  • Each function call - a unique path from main() in IG (see figure below).
• 
  
• Algorithm outline
  • Starting from main(), recursively process each function call.
  • Using map and unmap processor for formal-actual match.
  • Processing callee function body for each procedure call (IG node).
  • A sample algorithm to process calls in IG.
• 
  
• Problems:
  • Number of IG nodes can increase exponentially - memory storage requirement!
  • Processing function body for each IG node - large amount of computation!
• Can we use memoization?
  • one solution: partial transfer function.

• Partial transfer function [Wilson et al'95]
  • Use memoization.
  • funcOutput = PTF(funcInput).
  • PTF computed once for an "input pattern".
  • Lazily compute PTFs for each procedure.
• An example to illustrate PTF
  • Source code here
  • Total 8 procedure calls
  • Results:
    

• Procedure call graph [Choi et al'93]
  • Each procedure - a PCG node.
  • Each call site - an edge in PCG.
• 
  
• Iterative data flow analysis framework
  • Similar to Group #1, but decoupled.
  • Decoupled: two levels of iteration
    • Outer level: PCG
    • Inner level: CFG in each procedure
• Effects of a procedure call
  • Summarized in two sets of points-to pairs
    • foo.Entry - set at the entry point of procedure foo()
    • foo.Exit - set at the exit point of procedure foo()
  • Backward_binding foo.Exit from callee to caller.
  • Cumulative updating foo.Entry.
• 
  
• A sample algorithm using PCG.
• Problems:
  • Context insensitive.
  • Efficiency and scalebility
• Do we really care about flow order?
  • One way to improve efficiency and scalebility: flow-insensitive[Burke et al'95].
• Flow-insensitive approach
  

• Using procedure call graph (PCG) in a context sensitive way [Ryder et al'99,Cheng et al'00].
• Idea: context independent summary function (CISF):
  • CISF: effects of a procedure with unknown initial alias at the entry.
  • PTF: transfer function for a particular input pattern at the entry.
• Algorithm outline
  • Context sensitive: only input at the current call site involved in actual-formal binding (see figure below).
  • Effective: for each procedure, only one CISF need to be computed and stored (as compared with a number of PTFs)
  • 
    
• A sample algorithm using CISF.
• Computing CISF:
  
• Put all together: compare algorithms in Group #2,#3 and #4
  • An example: Source code here
  • Results:
    

• Abstract data representations
• Recursive and aggregate data structure
• Heap objects
• Function pointers and recursive function calls

• Invisible variables [Landi et al'92, Emami et al'94]
  • Variables not "visible" to a procedure, such as its caller's local variables.
  • Abstractly represented by "invisible variables" and map-information
• An example to illustrate invisible variables
  • Source code here
  • Results:
    
• Extended variable [Wilson et al'95]
  • Global variables are also represented abstractly.
  • For fewer input patterns and partial transfer functions.
• Access path (AP) [Landi et al'92, Deutch'94, Cheng et al'00]
  • Access path is defined as a symbolic notation to represent memory location.
      AP : variable
            | AP *
            | AP.field_name
      e.g:   p*.left*.right*.data
    
  • AP is used for abstract data representation [Cheng et al'00]
    
• Extended access path (EAP) [Cheng et al'00]
  • Access path extended from formal parameters or global variables.
  • Only those with non-empty EAP need to be propagated back to caller. for example:
          (temp, malloc_1*) => EAP(malloc_1*) = empty.
          (x*, malloc_1*) => EAP(malloc_1*) = x**.
    

• Nameless: [Emami et al'94]
  • All heap objects are represented by one "heap".
• Context-insensitive naming: [Landi et al'92]
  • Head objects are named by the creating statement.
• Context-sensitive naming: [Choi et al'93, Wilson et al'95]
  • Head objects are named by the creating statement and the call path.
• An example:
  • Source code here
  • Results:
    • Points-to pairs with context-insensitive naming:
         (p, S1) (q,S1)
      
    • Points-to pairs with context-sensitive naming:
         (p,C1_S1) (q,C2_S1)

• Problem: potentially infinite number of aliases
  
• Approaches classified by depth of indirection:
  • 1-level: combine all elements as one big cell [Emami'93,Wilson et al'95]
  • k-limiting: distinguish first k-elements (k is an arbitrary number) [Landi et al'92, Cheng et al'00]
  • beyond k-limiting: consider all elements, using some kinds symbolic access paths [Deutch'94]
  • shape analysis: not only distinguish all elements, but also tell how they are connected (connection analysis) and what their shape is.[Ghiya et al'95]

• A deadlock?
  • Need call graph to resolve function pointers.
  • Need resolving function pointers to build the call graph.
• Solution:
  • Iteration, using existing results and keep updating.
  • A sample algorithm from [Choi et al'93]

• A problem for IG approach
  
• Solution: [Emami '93, Wilson et al'95]
  • foo_Recursive
  • foo_Approximate
  • pending list in foo_Recursive
    

• Classified using context and flow sensitivity
  
• Comparison by a table
  

Traditional alias analysis are conducted at the level of source codes or high level IRs (including those in Part II). This part will look at assembly level alias analysis:

• Why assembly level?
• Previous work at assembly level.
• Alias analysis for Liberty Xcode.

• Avoid inaccuracy in alias information due to code transformation.
• Reduce cost of maintaining alias information.
• Apply to wider range of language.
• High level code may not be available:
  • Binary translation and optimization.
  • Run-time optimization.
  • Assembly applications.
• Information about the entire program/library.

• [Debray et al'98]
  • Binary level, inter-procedural, flow-sensitive, context insensitive.
• Algorithm outline:
  • ICFG, iterative data flow analysis framework.
  • mod-k residues address representation.
  • Address descriptor (AD): set of possible addresses for each register
    • AD(r) = < I, M >
    • I: definition instruction.
    • M: offset, which is a set of mod-k residues
  • Iteration framework: Out[N](r) = Evaluate(In[N])
    
  • Sufficient condition for not-an-alias
    • at N1: address1 = < I, M1 >
    • at N2: address1 = < I, M2 >
    • condition is:
      • I dominates both N1 and N2
      • either N1 dominate N2, or vice verse.
      • M1 intersect M2 = empty
  • An example: to show N1 and N2 are not dependent:
     
    

• No type information available.
• More complicated pointer arithmetics.
• Still a frontier area.
• Algorithm in [Debray et al'98] is relatively efficient but inaccurate
  • tested for gcc with 137,389 ld/st instructions.
  • 30 percent has known mod-k residues address.
• Can we do better?

• In planning stages.
• Comments welcome.
• An Xcode example:
  • To get insight and potential for alias analysis.
  • Source C code here
  • Unoptimized Liberty Xcode here

• [Burke et al'95]: M.Burke, P.Carini,J.Choi and M.Hind, "Flow-insensitive inter-procedural alias analysis in the presence of pointers", In Lecture Notes in Computer Science, 892, pp.234-250, Springier-Verlag, 1995.
• [Cheng et al'00] B.Cheng and W.Hwu, "Modular Interprocedural pointer analysis using access paths: design implementation and evaluation,", PLDI 2000, Vancouver, British Columbia, Canada.
• [Choi et al'93]: J.Choi, M.Burke and P.Carini, "Efficient flow-sensitive inter-procedural computation of pointer-induced aliases and side effects,", In Proceedings of the 20th Annual ACM Symposium on Principles of Programming Languages, pp.233-245, January 1993.
• [Deutsch'94]:A. Deutsch, "Interprocedural may-alias analysis for pointers: Beyond k-limiting,", In Proceeding of the ACM SIGPLAN'94 Conference on Programing language Design and Implementation, pp.230-241, June 1994.
• [Emami'93]: M. Emami, "A practical inter-procedural alias analysis for an optimizing/paralleling C compiler", Master thesis, School of Computer Science, McGill University, August 1993.
• [Emami et al'94]: M.Emami, R.Ghiya and L.Hendren, "Context-sensitive inter-procedural points-to analysis in the presence of function pointers", in Proceedings of ACM SIGPLAN'94 Conference on Programming Language Design and Implementation, pp. 242-256, June 1994.
• [Landi et al'92]: W.Landi and B.Ryder, "A safe approximate algorithm for inter-procedural pointer aliasing". In Proceeding of the ACM SIGPLAN'92 Conference on Programing language Design and Implementation, pp.235-248, June 1992.
• [Ryder et al'99] R.Chatterjee, R.Ryder and W.Landi, "Relevant context inference,", In Proceedings of the ACM Symposium on Principles of Programming Languages, pp.133-146, January 1999.
• [Wilson et al'95] R.Wilson and M.Lam, "Efficient context-sensitive pointer analysis for C programs", In Proceeding of the ACM SIGPLAN'95 Conference on Programing language Design and Implementation, pp.1-12, June 1995.
• More ......