Jump threading/bypassing volume 3

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

The issues associated with rewrite-ssa-into-ssa are not just
performance related.  They are related to the disruptive nature of
rewrite-ssa-into-ssa.

My primary motivation with dealing with dom at the summit was that the
low level ssa transformations were done in a manner that was
disruptive to ssa form and so I had set out to show that this could be
done in a manner that was less disruptive.  While it is clear that at
the summit, I only solved a portion of the problem, the amount of
disruption to the phi functions that dom does is still a concern and
the use of rewrite-ssa-into-ssa does not address this.

The problem is that rewrite-ssa-into-ssa not only touches the entire
function unnecessarily, but it will unnecessarily replace many phi
functions, even for the simplest of changes.

consider the following fragment:
          0
         / \
        /   \
       /     \
      1       2
      |     /   \
      |    3     4
      |   / \   / \
      |  5   6 7   8
      |   \ /   \ /
      |    9     10
      |     \   /
      |      11
      \     /
       \   /
        \ /
        12


Let us say that there is an assignment at 4 to x_1 and we wish to
modify this so that there are assignments at 7 and 8 to x_3 and x_4.
(This kind of cloning is the basis of many of the transformation
described in the postings.

If this is modeled as a deletion at 2 followed by insertions at 7
and 8, phi functions will touched at 10, 11, and 12 (assuming x was
live through the entire program).

However, the assignment to x_1 at 4 already had two phi functions, the
one at 11 and the one at 12.  All that is necessary is to fix up the
input at the one at 11 and add a new one at 10.

More generally, the minimum set of phi functions necessary to add is
the union of the dominance frontiers of the new assignments MINUS the
dominance frontier of the old assignment. 

The "MINUS the dominance frontier of the old assignment" part can be a
significant amount of code, and it is the kind of information that a
general function like rewrite-ssa-into-ssa cannot accommodate.  This
not only effects the overall cost of the optimization but more
importantly it effects the ability to keep any axillary information
associated with the phi functions in tact.  It is easy to argue that
since all you are doing is cloning the assignment of x_1 into x_3 and
x_4, that any phi function that only joins x_3 and x_4 together can
have the same axillary information (i.e. range info, value numbers,
etc).  But deleting the phi functions at nodes 11 and 12 are more
difficult matters since they will be joining different values that you
are not interested in.

This unnecessary and haphazard regeneration of the phi functions was
the problem that made me focus on dom for the summit.

Your last posting seems to indicate that you could have chosen any of
three approaches for updating ssa form.  I hope that you would
consider using one that does the least damage to ssa form.  This will
make it less burdensome to keep things like the aliasing up to date.
(For instance, if you are careful, you will not have to run the
aliasing analyzer after each instance of dom. )

Kenny