• Alias_Improvements

Alias Improvements Branch

The branch is merged as of SVN revision 145494.

(see http://gcc.gnu.org/ml/gcc/2009-01/msg00286.html)

The primary objective of the branch is to transition away from the use of the virtual operand use-def chains as data-flow representation for memory optimizations. Memory optimizers need to transition to the use of the alias-oracle which is a query based system. For the foreseeable future they can still rely on the safety-net the virtual operand use-def chain provides.

Overview of infrastructure changes done on the branch:

• There is a single memory symbol (.MEM) per function used to build the virtual operand use-def chain. In trunk terms you can view this as equivalent to having a single memory partition containing all symbols. Due to the lack of precision computing and keeping this virtual operand use-def chain is trivial, all code supporting more complex operations has been removed. In particular it can be assumed that at most a single VUSE and VDEF is available per statement. Most code has been simplified according to that assumption.
• This single-symbol virtual operand use-def chain safety-net is also available during early optimizations (in fact, always if the IL is in SSA form). This removes the need for special-casing memory statements during that compilation phase and enables to use common infrastructure during early (and IPA) optimization phases. It also allows to schedule regular memory optimization passes during early optimization.
• The virtual operand use-def chain is kept up-to-date by the operand-scanner on the branch. There is no need to manually mark any symbols for renaming (instead this is now useless and costly). As there cannot be magically more, less or different memory symbols required (there's only one) optimization passes usually know if they are removing a load or a store and so can act properly (or rely on the operand scanner which updates virtual SSA form manually in the simple cases of removing virtual operands and otherwise marks .MEM for renaming).
• The at most two virtual operands (a VUSE and a VDEF) are now real operands (there is a vuse and a vdef member in the gimple structure for memory statements). This means they can share the infrastructure present for regular operands and immediate uses. All infrastructure dealing with the old virtual operands has been removed. The operand structures are linked in the normal use and defs lists, the special lists for virtual uses and defs has been removed. This means that operand iterators have been simplified a lot. The possibility to iterate over only virtual operands has been removed (there is only at most a single one, directly accessible via gimple_v{use,def}_op). Most bulk changes in optimizers had to be done because of this simplification.
• Global data that was not kept in sync and is either unused on the branch or very hard to keep up-to-date has been removed. This includes the bitmap of addressable variables, the escape type per variable and pointer and the bitmaps of loaded and stored symbols on statements.
• Points-to information has been abstracted and is directly used for pointer information as well as call-clobber related information. All existing call-clobber related code has been removed. Low-level operations on points-to information are implemented in tree-ssa-structalias.c.
• Numerous fixes to the points-to analysis code have been done.
• The alias-oracle present on the trunk has been extended to also use points-to alias information and it has been split up to be more easily available in different contexts. The implementation resides in tree-ssa-alias.c, interfaces are exported from tree-ssa-alias.h.
• The FRE and PRE passes using the common SCCVN infrastructure have been improved by improving the memory statement walking infrastructure of the alias-oracle and its precision.
• The tree DSE pass has been improved to compensate the loss of DSE on aliased symbols done by the tree DCE pass on the trunk.
• The tree DCE pass has been improved to do DSE of non-aliased symbols and thus fully replaces the SDSE (simple DSE) early optimization pass.

The alias-oracle and its interface is contained in the tree-ssa-alias.[ch] files. Common with the trunk is the refs_may_alias_p type of query which has been accompanied by statement based clobber / use queries.

Preliminary performance measurements show comparable performance for SPEC 2000, Polyhedron and our usual set of C++ benchmarks. SPEC 2006 measurements are on the way, all on x86_64. Daily testing can be monitored beyond http://gcc.opensuse.org/, look for "alias-improvements" branch annotation and compare with the other runs on the frescobaldi machine.

In general the trade-off with the new scheme is that walking statements via the virtual use-def links will be slower because possibly (a lot) more statements are visited. This is offsetted by leaner operand iterators, cheaper operand scanning and updating and less memory use for maintaining the virtual operands. And most important, a lot less code to maintain.

Followup Improvements

There are a number of tasks left to do.

• push/pop_stmt_changes can be removed. Done!

• The inliner can rewrite the virtual operands itself just like regular operands. The only difficulties are that new pure/const functions are exposed after IPA-pure-const and that new PHI-nodes need to be inserted to merge VDEFs in the inlined function to the VDEF of

  the call statement. Partial patch available.

• The single pre-function gimple_vop (cfun) DECL can be made per CU. The disadvantage is that cross-function inconsistencies are harder to detect.

• Most passes that mark symbols for renaming should not need to. This is mostly fixed.

• into-SSA could go into virtual SSA form directly, without doing an ssa update

  to rename the virtual operands after into-SSA. into-SSA expert needed.

• In PTA we can generate a CALLUSED variable and its constraints for each pure call

  (just like we do with consttmp for const calls). Done!

• Simple mod/ref analysis can be done in PTA handle_rhs_call for builtins. call-used queries have to be extended to builtin function calls then (or finally a stmt local

  call-used points-to solution reference can be introduced). Done!

• Add params for the magic number(s) in the DCE/DSE oracle query limits. Done!

• Add oracle query limits to SCCVN.
• 189.lucas regressed about 10% on x86_64, that needs to be investigated.