This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[patch] Lno branch merge part 3 -- ssa form updating improvements
- From: Kenneth Zadeck <zadeck at naturalbridge dot com>
- To: gcc-patches at gcc dot gnu dot org
- Cc: rakdver at atrey dot karlin dot mff dot cuni dot cz, amacleod at redhat dot com,dnovillo at redhat dot com
- Date: Tue, 15 Jun 2004 15:17:06 -0500
- Subject: [patch] Lno branch merge part 3 -- ssa form updating improvements
I must apologize for not responding to this properly. I am visiting my
parents who have a dsl from aol that will neither allow me to connect my
laptop where this note exists or use port 25 for sending mail so that I
can use emacs to fake it.
While this patch satisfies my main objection of not adding anything else
to the main branch that destroys the aliasing information, it does have
two costs associated with it that need to be considered:
1) The code replicates, with minor changes, a significant amount of ssa
code from earlier in the compiler. This will have a very high
maintenance cost as changes are made to the ssa infrastructure. With
this patch, each change to the infrastructure must be replicated.
2) This code will not be as fast as simply identifying the relevant
variables before ssa is built and adding special copy statements at the
loop exit. Then you just let the efficient, offline algorithm do the
rest. The incremental ssa algorithms have much higher overhead than the
offline version.
What follows here is an expanded version of the algorithm I described at
the GCC summit. Since this is done so early all of the alias building
and ssa building just happens.
Kenny
==============
First, a new intermediate type needs to be created, loopExitCopy,
which at NaturalBridge was a subtype of copy. These may be transmuted
into phi functions when the loop is unrolled.
Getting into loop closed ssa form is best accomplished as a prepass
before entering ssa form, but after the control flow graph is built.
1) analyse the cfg to determine the loop nest.
2) run live variables and construct the set of variables live at each
loop exit from each loop (this can be skipped but it means that you
will put in the loopExitCopies into loops where the variable was
only live in the inner loop but not in the outer loop. Dead code
will get rid of these, but since you seem use live variables to
guide your ssa building, this should be easy to do.)
3) for each loop L in the program (inner to outer) {
scan the statements in the loop to construct the set, S, of
variables that are assigned to within the loop.
for each variable V in S
for each exit E of L
if V is in Live(E)
add a loopExitCopy for V to E
4) build ssa form.
5) modify the copy propagator to leave the loopExitCopies alone until
the end of compilation. At the end of compilation, the
loopExitCopies are treated as regular copies and may be propagated.
Several notes here:
1) when scanning the statements in a loop, it is not necessary to
scan the statements in inner loops as long as the loop exit blocks
for the inner loop are counted as part of the outer loop.
2) if the loop exit block is part of the outer loop, this will
propagate new copies out of the entire loop nest (since the loops
are processed inner to outer)
These two steps keep the process form being n**2.
3) The NaturalBridge world was different from the GCC world in one
important way. The phi functions were part of the instruction
stream, not an annotation of the block.
Because of this, there were less edge cases when transmuting copies
to phis or back. In some sense, these loopExitCopies are really
one arg phis, however there are not supposed to be phis before ssa
form was built.
=================
Hello,
this patch adds a possibility to handle ssa form updating without need
to rewrite variables out of ssa form. The idea is to allow to violate
the invariants of the ssa form temporarily and let a single ssa name
have several definitions. A call to rewrite_ssa_into_ssa (running
standard ssa creation algorithm just over those ssa names) then
"repairs" the ssa form.
To show one of the applications, loop header copying is also modified in
this patch so that it no longer needs to rewrite any variables out of
ssa form.
Bootstrapped & regtested on i686.
Zdenek