birthpoints in rtl.

[Kenneth Zadeck <zadeck at naturalbridge dot com>]

I want to start a discussion about some possible changes to the RTL
level of GCC.

This discussion is motivated by some of the issues raised in bug
26854.  We have addressed many of the issues in this bug, but the
remaining issue is cost, in both time and space, for the UD and DU
chains built by several back end optimizations.

I have started one possible fix for this bug, but as I do the work, I
am less convinced that it really is the best way to go.  Currently UD
or DU chains are represented as linked lists. If a pass asks for
DU-chains, there is a linked list from each def of a reg to each use
that it reaches.  

These linked lists are a big part of the space usage of this bug and I
believe a big part of the space usage of the back end, especially as
more passes are upgraded from just using the live information.

My original plan had been to convert these linked lists to VECs,
much in the way that basic block edges are represented.  However, I
believe that this is unlikely to help: currently each element of the
linked list takes two words - if I convert this to VECs, there will be
two malloc overheads per ref along with fields of the VEC and the 25%
wasted space for the data.  All of this to remove the next pointer.  
While I believe that this will improve the n**2 cases, I believe that
in most cases this will not win.

For DU and UD chains, the n**2 cases come from programs that look like
two case statements that follow each other (there are a lot of other
situations that can cause this, but this is the easiest to
visualize).   In the first case statement, each arm has a def of R and in
the second case statement each a use of R.  The number of DU chains
for this example is [the number of defs for R] * [the number of uses
for R].

To solve this, I would like to propose a datastructure that first
appeared in the open literature in by Reif and Lewis though I suspect
that it was originally developed by Shipiro and Saint.  This is the
BIRTHPOINT, and it was an idea that heavily influenced Wegman and
myself when we first developed SSA form.  The easiest way to explain a
birthpoint (in this day) is to say that a birthpoint is a simple noop
move that is inserted everywhere that one would normally add a phi
function.  I.e. it is missing the operands for each incoming edge.

Birthpoints are not nearly as useful as phi-functions because the
algorithms that use birthpoints do not generally leave the birthpoints
in the right places when they are finished.  There is a lot of value
added by the operand of phi-functions.  But they do solve the n**2
case for DU and UD chains (and because of the better SSA building
algorithms than were available when Reif and Lewis first proposed
their technique, will be much faster).

It will be possible to use some of the existing into SSA machinery
(adapted to work over RTL rather than trees or gimple) to both find
the birthpoints and to build the chains (this is what Reif and Lewis
did with their non-conditional constant propagator) and so it would
allow us to drop the RD dataflow problem which is itself, a time and
space hog.

The appeal for birthpoints is that unlike the abortive attempt in
the past to add SSA to RTL, adding a noop moves does not really mess
up anything.  We could either add them only in passes that use DU or
UD chains and get rid of them at the end of the pass or we could leave
them and only get rid of them in passes where they might get in the
way, like RA.  However, without the operands to the phis, you cannot
do SSA optimizations like conditional constant propagation.

There is the complication of how to add the noop move in the presence
of SUBREGs, and given the amount of pain that I suffered in adding the
moves for the DSE pass, I would need to get the help of one of the
active SUBREG elite, like Bonzini, Iant or Rsandifo to help.
However, I believe that birthpoints will remove many of the time and space
problems that have arisen because of the new usage of DU and UD chains
at the RTL level.

Assuming that the SUBREG issue is one that can be easily solved, this is
a big step to being able to put SSA like technology into the gcc backend
without breaking everything.

Comments? Volunteers?

Kenny


If anyone wants to see the references to the papers by Shapiro and
Saint or Reif and Lewis, I will be happy to send the references.
They are both obscure and difficult to understand.