[patch] Lno branch merge part 3 -- ssa form updating improvements

[Kenneth Zadeck]

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