Movatterモバイル変換

Next:Memory model, Previous:Static Single Assignment, Up:Analysis and Optimization of GIMPLE tuples [Contents][Index]

12.4 Alias analysis ¶

Alias analysis in GIMPLE SSA form consists of two pieces. Firstthe virtual SSA web ties conflicting memory accesses and providesa SSA use-def chain and SSA immediate-use chains for walkingpossibly dependent memory accesses. Second an alias-oracle canbe queried to disambiguate explicit and implicit memory references.

Memory SSA form.
All statements that may use memory have exactly one accompanied use ofa virtual SSA name that represents the state of memory at thegiven point in the IL.
All statements that may define memory have exactly one accompanieddefinition of a virtual SSA name using the previous state of memoryand defining the new state of memory after the given point in the IL.
```
int i;int foo (void){  # .MEM_3 = VDEF <.MEM_2(D)>  i = 1;  # VUSE <.MEM_3>  return i;}
```
The virtual SSA names in this case are.MEM_2(D) and.MEM_3. The store to the global variableidefines.MEM_3 invalidating.MEM_2(D). Theload fromi uses that new state.MEM_3.
The virtual SSA web serves as constraints to SSA optimizerspreventing illegitimate code-motion and optimization. Italso provides a way to walk related memory statements.
Points-to and escape analysis.
Points-to analysis builds a set of constraints from the GIMPLESSA IL representing all pointer operations and facts we door do not know about pointers. Solving this set of constraintsyields a conservatively correct solution for each pointervariable in the program (though we are only interested inSSA name pointers) as to what it may possibly point to.
This points-to solution for a given SSA name pointer is storedin thept_solution sub-structure of theSSA_NAME_PTR_INFO record. The following accessorfunctions are available:
- pt_solution_includes
- pt_solutions_intersect
Points-to analysis also computes the solution for two specialset of pointers,ESCAPED andCALLUSED. Thoserepresent all memory that has escaped the scope of analysisor that is used by pure or nested const calls.
Type-based alias analysis
Type-based alias analysis is frontend dependent though genericsupport is provided by the middle-end inalias.cc. TBAAcode is used by both tree optimizers and RTL optimizers.
Every language that wishes to perform language-specific alias analysisshould define a function that computes, given atreenode, an alias set for the node. Nodes in different alias sets are notallowed to alias. For an example, see the C front-end functionc_get_alias_set.
Tree alias-oracle
The tree alias-oracle provides means to disambiguate two memoryreferences and memory references against statements. The followingqueries are available:
- refs_may_alias_p
- ref_maybe_used_by_stmt_p
- stmt_may_clobber_ref_p
In addition to those two kind of statement walkers are availablewalking statements related to a reference ref.walk_non_aliased_vuses walks over dominating memory definingstatements and calls back if the statement does not clobber refproviding the non-aliased VUSE. The walk stops atthe first clobbering statement or if asked to.walk_aliased_vdefs walks over dominating memory definingstatements and calls back on each statement clobbering refproviding its aliasing VDEF. The walk stops if asked to.