6.035 - Fall 1999 - TA: Daniel Barkalow le04

Register Allocation

le04 is...

Chris Laas (golem) Mike Phillips (mpp) Jim Waldrop (jlwfnord)

Division of Labor

Mike wrote the ReachingDefinitions.java code and DUChains. He also produced some scripts to automate regression testing which was a big win. He fixed a bug in the last phase where Dead-CodeElimination could sometimes break if constructs. Finally, he fixed the calling convention to be more n32 compliant– there was a problem with passing more than 8 arguments, since n32 apparently (from empirical observation with gdb and cc) wants to use 64 bit words for each parameter passed on the stack. Callouts to printf with more than 8 args now work, for example. Finally, a bug in the last phase caused “-opt all” to imply “-spim” which it should not, so he fixed that too. Oh, right, and he did the substituting-in Symbolic Registers trick á la the Whale book also.

Jim wrote the initial version of DUChains (which Mike later fixed so it would actually be useful), as well as all the code for Web, which allows us to produce webs out of individual DUChains. He also wrote the code for InterferenceGraph (and the slave class AdjacencyEntry) which generates the interference matrix, produces a graph, and colors it. We simplified the SpillCost heuristic (in InterferenceGraph, since that is where we color and spill the graph) in order to simplify the data structure of DUChains and the overall problem of graph coloring.

Chris created the ”proxy” concept, which allowed variables to be magically mutated from stack locals to registers without modifying the CFG or losing any of the information about the original variables. He also optimized our BinOp and Store instructions to use these proxies, and fixed a good number of previous bugs.

Clarifications, Assumptions, Additions

To access the optimizations, use these switches on the command line:

• -cp, -opt cp: Copy propagation

• -dce, -opt dce: Dead code elimination

• -all, -opt all: Turn on both optimizations

• -spim, -opt spim: output SPIM code instead of MIPS

Overview, Implementation and Insights

The goal is to make efficient use of registers and keep as much of the data being operated on in registers as possible, to avoid the huge penalties associated with accessing memory. We only use the callee-saved registers at the moment, though there are a few spare caller-saved ones which we could certainly add to the register pool without much trouble. The only care that would need to be taken would be to spill them across procedure calls – this penalty is one of the reasons we didn’t do this from the start.

It is worthy to note at what stage the register allocation is performed. The code is in a low-IR state (or DelocalizedInstructions as we ended up calling it) which is just a hair above actual assembly language. At this level, all the temporaries that are needed are created and used are in the control flow graph, so we can easily assign temporaries to registers too, since in most cases they live for a short time and are used to quickly create intermediate results– they need not live on the stack generally. Also, before we allocate registers, we run the optimizations selected by the user. Copy propagation and especially dead-code elimination do a wonderful job of both producing faster code on their own, and also reducing the strain on the register allocator as unneeded definitions can be removed along with the DUChain that would have been created if they hadn’t been.

ReachingDefinitions and DUChains

The Reaching Definitions are computed using the standard fixed-point seeking algorithm presented in class and in the Whale book. Specifically, we created a subclass of our existing FixedPointAlgorithm class to specify the few details specific to this algorithm. After the solution is found, Definition-Use Chains (class DUChain) are built to describe all of the uses each definition can reach. This information is needed to create webs and ultimately the interference graph. A DUChain object is able to perform substitution on the value it holds a definition for and propagate that change to all uses, when the time to plug in a symbolic register comes (after webs are created). It also needs to be able to determine if it intersects with a second DUChain in order to come up with the edges in the interference graph.

Web

A Web is a group of DUChains that DEFine the same variable and have at least one overlapping USE of that variable. To achieve this, a Web checks each DUChain that we try to add to it to see if it is related - that is, if any of its USEs are mirrored in the DUChains already in the Web data structure. Web also handles checking for interferences - an interference (for the InterferenceGraph) is defined as one web having any of its DUChains overlap with the DUChains of another Web. (Overlap is defined as one DUChain starting within another.)

InterferenceGraph and AdjacencyEntry

The InterferenceGraph class handles all the actual grunge of producing an interference matrix and an adjacency graph, and coloring the graph. The InterferenceGraph constructor takes in a vector of DUChains and a MethodDescriptor (for register allocation purposes). We build all our webs within the InterferenceGraph, then we produce a square interference matrix (not triangular - I chose to take the performance hit and make it a square array for ease in calculating number of intersections). After the interference matrix is built, we build a vector of AdjacencyEntries, containing our color (as yet unassigned), spill cost (as yet unassigned), number of interferences and adjacent AdjacencyEntry “nodes”, and the underlying Web that we are trying to allocate a register for. If we treat our AdjacencyEntries as nodes in our graph we need to color, we have built our adjacency graph at this point. We then color the graph with the algorithm presented in lecture - we push nodes with degree < R onto a stack and eliminate their links in the graph. If we get to a point where there are no nodes with degree < R, we take the node with the lowest spillcost off the graph and fail to place it on the stack. Once the graph is empty, we color only those nodes on the stack - the default state for a symbolic register (the underlying data structure that each Web/AdjacencyEntry represents) is spilled, so we don’t really have to generate spill code, only proxy code (which Chris deals with).

Wish list

There are certainly other optimizations our compiler could be taught about, even beyond the scope of the projects. For example, with the FixedPointAlgorithmClass and now the ReachingDefinitions class, adding Constant Propagation would be fairly simple. Constant folding is also a simple operation that could be combined into the routine which currently performs algebraic simplification. Also, the assembly output could be more debugger friendly, by putting the .ents on the right side of the procedure label and specifying stack frames (though as it was, gdb was very helpful in debugging the programs our compiler produced). All of these additions are reasonably easy to implement with a little time due to the current structure of things. Additionally it would be nice to develop a framework for performing the instruction flow optimizations that the Espresso folks had to do. Another thing it would be nice to have is a switch that toggles the generation of comments in the assembly output. Currently, this is achieved by commenting or uncommenting the one line of code in MIPSCodegen.comment() which puts commented NOPs in to make it easier to find your away around the code (an absolute must for debugging, but a waste in terms of efficiency). And last, but not least, the ability to pass arrays through callouts would let us run the Mandelbrot program.

Results

We ran our code on all of the provided test cases, and it worked on all cases except for 12-huge.dcf. This case is absolutely huge which makes it a bit harder to run through the assembly and debugging output. The answers were actually quite close to correct, off by small integral amounts, which we found odd (see Final/tests/*diff). We speculate that two symbolic registers were allocated to the same register due to a boundary condition on the code to detect overlaps, or something similarly odd. As far as more positive results go, we were also able to verify the output of the various stages of our algorithms. We verified that we were producing the correct DUChains for a few program, that we combined them into Webs properly, that the graph was colored correctly, that the register allocation was sane, and that the instruction count was reduced. A quick timing analysis demonstrated the code did indeed run faster. We would have liked to have had more time to track down the one bug preventing us from correctly compiling 12-huge.dcf (and 16-huge-dead.dcf, which is the same with more dead code tossed in); however, we did not have that luxury.