This is the mail archive of the gcc-patches@gcc.gnu.org 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]

[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



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