gccint: Alias analysis

1 
1 13.4 Alias analysis
1 ===================
1 
1 Alias analysis in GIMPLE SSA form consists of two pieces.  First the
1 virtual SSA web ties conflicting memory accesses and provides a SSA
1 use-def chain and SSA immediate-use chains for walking possibly
1 dependent memory accesses.  Second an alias-oracle can be queried to
1 disambiguate explicit and implicit memory references.
1 
1   1. Memory SSA form.
1 
1      All statements that may use memory have exactly one accompanied use
1      of a virtual SSA name that represents the state of memory at the
1      given point in the IL.
1 
1      All statements that may define memory have exactly one accompanied
1      definition of a virtual SSA name using the previous state of memory
1      and defining the new state of memory after the given point in the
1      IL.
1 
1           int i;
1           int foo (void)
1           {
1             # .MEM_3 = VDEF <.MEM_2(D)>
1             i = 1;
1             # VUSE <.MEM_3>
1             return i;
1           }
1 
1      The virtual SSA names in this case are '.MEM_2(D)' and '.MEM_3'.
1      The store to the global variable 'i' defines '.MEM_3' invalidating
1      '.MEM_2(D)'.  The load from 'i' uses that new state '.MEM_3'.
1 
1      The virtual SSA web serves as constraints to SSA optimizers
1      preventing illegitimate code-motion and optimization.  It also
1      provides a way to walk related memory statements.
1 
1   2. Points-to and escape analysis.
1 
1      Points-to analysis builds a set of constraints from the GIMPLE SSA
1      IL representing all pointer operations and facts we do or do not
1      know about pointers.  Solving this set of constraints yields a
1      conservatively correct solution for each pointer variable in the
1      program (though we are only interested in SSA name pointers) as to
1      what it may possibly point to.
1 
1      This points-to solution for a given SSA name pointer is stored in
1      the 'pt_solution' sub-structure of the 'SSA_NAME_PTR_INFO' record.
1      The following accessor functions are available:
1 
1         * 'pt_solution_includes'
1         * 'pt_solutions_intersect'
1 
1      Points-to analysis also computes the solution for two special set
1      of pointers, 'ESCAPED' and 'CALLUSED'.  Those represent all memory
1      that has escaped the scope of analysis or that is used by pure or
1      nested const calls.
1 
1   3. Type-based alias analysis
1 
1      Type-based alias analysis is frontend dependent though generic
1      support is provided by the middle-end in 'alias.c'.  TBAA code is
1      used by both tree optimizers and RTL optimizers.
1 
1      Every language that wishes to perform language-specific alias
1      analysis should define a function that computes, given a 'tree'
1      node, an alias set for the node.  Nodes in different alias sets are
1      not allowed to alias.  For an example, see the C front-end function
1      'c_get_alias_set'.
1 
1   4. Tree alias-oracle
1 
1      The tree alias-oracle provides means to disambiguate two memory
1      references and memory references against statements.  The following
1      queries are available:
1 
1         * 'refs_may_alias_p'
1         * 'ref_maybe_used_by_stmt_p'
1         * 'stmt_may_clobber_ref_p'
1 
1      In addition to those two kind of statement walkers are available
1      walking statements related to a reference ref.
1      'walk_non_aliased_vuses' walks over dominating memory defining
1      statements and calls back if the statement does not clobber ref
1      providing the non-aliased VUSE. The walk stops at the first
1      clobbering statement or if asked to.  'walk_aliased_vdefs' walks
1      over dominating memory defining statements and calls back on each
1      statement clobbering ref providing its aliasing VDEF. The walk
1      stops if asked to.
1