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.
