This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[4.5] Alias-Improvements branch overview and merge proposal

Alias-Improvements Branch

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
forseeable future they can still rely on the safety-net the virtual
operand use-def chain provides.

I propose to merge the branch at the beginning of stage1 for GCC 4.5.
Bugfixes put on the branch can be merged independently.  Likewise it
should be possible to merge the points-to changes and some of the
call-clobber changes before the rest.
Other changes though are difficult or impossible to separate without
intermediate regressions.

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

 - 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,
   code auditing is still necessary here).  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).

 - 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 and the escape type per variable
   and pointer.

 - 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.

 - 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.

 - 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
   done by the tree DCE pass on the trunk (but see below).

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,
look for "alias-improvements" branch annotation and compare with the
other runs on the frescobaldi machine.  Performance comparisons on other
architectures are welcome.

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.

Current shortcomings ("regressions") present on the branch, which I do
not plan to work on before the merge.

 - Uninitialized warnings for memory which depend on the virtual operands
   will no longer work (but in very small testcases).
    FAIL: gcc.dg/uninit-B.c uninit i warning (test for warnings, line 12)
    FAIL: gcc.dg/uninit-pr19430.c  (test for warnings, line 32)
    FAIL: gcc.dg/uninit-pr19430.c uninitialized (test for warnings, line 41)

 - A trick on the 4.4 branch shadowed the issue with the C/C++ frontend
   using alias set zero for char and how that relates to char members
   in structures (their alias sets have a zero member).
    FAIL: gcc.dg/tree-ssa/pr27799.c (test for excess errors)

 - DCE no longer removes as many dead stores as on trunk.
    FAIL: gcc.dg/tree-ssa/loop-36.c scan-tree-dump-not dce2 "c.array"
    FAIL: gcc.dg/tree-ssa/ldist-11.c scan-tree-dump-times ldist "distributed: split to 2 loops" 1

There are also some XPASSes.  Likewise gazillions of copile-time and
memory-hog related bugs should be fixed (and an unknown amount of new
ones introduced).  A bunch of optimization related PRs are fixed as well.

There are a number of tasks left to do, either on the branch or (prefered)
on trunk after merging the branch.

 - The pass-pipeline needs re-tuning.  We re-compute points-to information
   too often and at non-optimal places (is no longer necessary for correctness
   to "re-compute" alias information).

 - Special "early" passes can get removed, merged or be made use of
   generally in the optimization pipeline.

 - The DCE / DSE situation needs to be resolved.
   On the trunk DCE does remove far more dead stores than DSE does.  On
   the branch dead store removal from DCE is severely pessimized (because
   it still relies on the virtual operands).  DSE is improved on the branch,
   but it runs too late and not often enough and is also very simple.
   The best solution is to remove the DSE pass and do all (and proper)
   dead store removal from within DCE, but this is quite an effort and
   as can be seen from benchmark numbers not a blocker for merging the

Comments / Performance measurements / code-reviews welcome.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]