| Previous Next |
Implement graph-coloring register allocation as two modules: Color, which does just the graph coloring itself, and RegAlloc, which manages spilling and calls upon Color as a subroutine. To keep things simple, do not implement spilling or coalescing; this simplifies the algorithm considerably.
package RegAlloc;
public class RegAlloc implements Temp.TempMap {
public Assem.InstrList instrs;
public String tempMap(Temp temp);
public RegAlloc(Frame.Frame f, Assem.InstrList il);
}
class Color implements TempMap {
public TempList spills();
public String tempMap(Temp t);
public Color(InterferenceGraph ig,
TempMap initial,
TempList registers);
}
Given an interference graph, an initial allocation (precoloring) of some temporaries imposed by calling conventions, and a list of colors (registers), color produces an extension of the initial allocation. The resulting allocation assigns all temps used in the flow graph, making use of registers from the registers list. The initial allocation is the frame (which implements a TempMap describing precolored temporaries); the registers argument is just the list of all machine registers, Frame.registers (see page 251). The registers in the initial allocation can also appear in the registers argument to Color, since it's OK to use them to color other nodes as well. The result of Color is a TempMap (that is, Color implements TempMap) describing the register allocation, along with a list of spills. The result of RegAlloc - if there were no spills - is an identical TempMap, which can be used in final assembly-code emission as an argument to Assem.format. A better Color interface would have a spillCost argument that specifies the spilling cost of each temporary. This can be just the number of uses and defs, or better yet, uses and defs weighted by occurrence in loops and nested loops. A naive spillCost that just returns 1 for every temporary will also work. A simple implementation of the coloring algorithm without coalescing requires only one work list: the simplifyWorklist, which contains all non-precolored, nonsimplified nodes of degree less than K . Obviously, no freezeWorklist is necessary. No spillWorklist is necessary either, if we are willing to look through all the nodes in the original graph for a spill candidate every time the simplifyWorklist becomes empty. With only a simplifyWorklist, the doubly linked representation is not necessary: This work list can be implemented as a singly linked list or a stack, since it is never accessed "in the middle."
Implement spilling, so that no matter how many parameters and locals a MiniJava program has, you can still compile it.
Implement coalescing, to eliminate practically all the MOVE instructions from the program.
| JaVa |
Previous Next |