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