Previous    Next

Register Allocation

reg-is-ter: a device for storing small amounts of data
al-lo-cate: to apportion for a specific purpose

Webster's Dictionary


The Translate, Canon, and Codegen phases of the compiler assume that there are an infinite number of registers to hold temporary values and that MOVE instructions cost nothing. The job of the register allocator is to assign the many temporaries to a small number of machine registers, and, where possible, to assign the source and destination of a MOVE to the same register so that the MOVE can be deleted. From an examination of the control and dataflow graph, we derive an interference graph. Each node in the interference graph represents a temporary value; each edge (t1, t2) indicates a pair of temporaries that cannot be assigned to the same register. The most common reason for an interference edge is that t1 and t2 are live at the same time. Interference edges can also express other constraints; for example, if a certain instruction abc cannot produce results in register r12 on our machine, we can make a interfere with r12.

Next we color the interference graph. We want to use as few colors as possible, but no pair of nodes connected by an edge may be assigned the same color. Graph coloring problems derive from the old mapmakers' rule that adjacent countries on a map should be colored with different colors. Our "colors" correspond to registers: If our target machine has K registers, and we can K -color the graph (color the graph with K colors), then the coloring is a valid register assignment for the interference graph. If there is no K -coloring, we will have to keep some of our variables and temporaries in memory instead of registers; this is called spilling.

JaVaScreenshot Previous    Next