Previous    Next

PRECOLORED NODES

Some temporaries are precolored - they represent machine registers. The front end generates these when interfacing to standard calling conventions across module boundaries, for example. For each actual register that is used for some specific purpose, such as the frame pointer, standard-argument-1-register, standard-argument-2-register, and so on, the Codegen or Frame module should use the particular temporary that is permanently bound to that register (see also page 251). For any given color (that is, for any given machine register) there should be only one precolored node of that color. The select and coalesce operations can give an ordinary temporary the same color as a precolored register, as long as they don't interfere, and in fact this is quite common. Thus, a standard calling-convention register can be reused inside a procedure as a temporary variable. Precolored nodes may be coalesced with other (non-precolored) nodes using conservative coalescing. For a K-register machine, there will be K precolored nodes that all interfere with each other. Those of the precolored nodes that are not used explicitly (in a parameter-passing convention, for example) will not interfere with any ordinary (non-precolored) nodes; but a machine register used explicitly will have a live range that interferes with any other variables that happen to be live at the same time. We cannot simplify a precolored node - this would mean pulling it from the graph in the hope that we can assign it a color later, but in fact we have no freedom about what color to assign it. And we should not spill precolored nodes to memory, because the machine registers are by definition registers. Thus, we should treat them as having "infinite" degree.

TEMPORARY COPIES OF MACHINE REGISTERS

The coloring algorithm works by calling simplify, coalesce, and spill until only the precolored nodes remain, and then the select phase can start adding the other nodes (and coloring them). Because precolored nodes do not spill, the front end must be careful to keep their live ranges short. It can do this by generating MOVE instructions to move values to and from precolored nodes. For example, suppose r7 is a callee-save register; it is "defined" at procedure entry and "used" at procedure exit. Instead of being kept in a precolored register throughout the procedure (Image 11.7a), it can be moved into a fresh temporary and then moved back (Image 11.7b). If there is register pressure (a high demand for registers) in this function, t231 will spill; otherwise t231 will be coalesced with r7 and the MOVE instructions will be eliminated.

Java Click To expand
Image 11.7: Moving a callee-save register to a fresh temporary.

CALLER-SAVE AND CALLEE-SAVE REGISTERS

A local variable or compiler temporary that is not live across any procedure call should usually be allocated to a caller-save register, because in this case no saving and restoring of the register will be necessary at all. On the other hand, any variable that is live across several procedure calls should be kept in a callee-save register, since then only one save/restore will be necessary (on entry/exit from the calling procedure). How can the register allocator allocate variables to registers using this criterion? Fortunately, a graph-coloring allocator can do this very naturally, as a byproduct of ordinary coalescing and spilling. All the callee-save registers are considered live on entry to the procedure, and are used by the return instruction. The CALL instructions in the Assem language have been annotated to define (interfere with) all the caller-save registers. If a variable is not live across a procedure call, it will tend to be allocated to a caller-save register.

If a variable x is live across a procedure call, then it interferes with all the caller-save (precolored) registers, and it interferes with all the new temporaries (such as t231 in Image 11.7) created for callee-save registers. Thus, a spill will occur. Using the common spill-cost heuristic that spills a node with high degree but few uses, the node chosen for spilling will not be x but t231. Since t231 is spilled, r7 will be available for coloring x (or some other variable). Essentially, the callee saves the callee-save register by spilling t231.

EXAMPLE WITH PRECOLORED NODES

A worked example will illustrate the issues of register allocation with precolored nodes, callee-save registers, and spilling. A C compiler is compiling Program 11.8a for a target machine with three registers; r1 and r2 are caller-save, and r3 is callee-save. The code generator has therefore made arrangements to preserve the value of r3 explicitly, by copying it into the temporary c and back again.

A C function and its translation into instructions
Java ScreenShot
Java End example

The instruction-selection phase has produced the instruction list of Program 11.8b. The interference graph for this function is shown at right.

Java ScreenShot

The register allocation proceeds as follows (with K = 3):

  1. In this graph, there is no opportunity for simplify or freeze (because all the non-precolored nodes have degree ≥ K ). Any attempt to coalesce would produce a coalesced node adjacent to K or more significant-degree nodes. Therefore we must spill some node. We calculate spill priorities as follows:

    Node

    Uses+Defs outside loop

    Uses+Defs within loop

    Degree

     

    Spill priority


    a

    (

    2

    + 10 ×

    0

    ) /

    4

    =

    0.50

    b

    (

    1

    + 10 ×

    1

    ) /

    4

    =

    2.75

    c

    (

    2

    + 10 ×

    0

    ) /

    6

    =

    0.33

    d

    (

    2

    + 10 ×

    2

    ) /

    4

    =

    5.50

    e

    (

    1

    + 10 ×

    3

    ) /

    3

    =

    10.33

    Node c has the lowest priority - it interferes with many other temporaries but is rarely used - so it should be spilled first. Spilling c, we obtain the graph at right.

Java ScreenShot

  1. We can now coalesce a and e, since the resulting node will be adjacent to fewer than K significant-degree nodes (after coalescing, node d will be low-degree, though it is significant-degree right now). No other simplify or coalesce is possible now.

Java ScreenShot

  1. Now we could coalesce ae&r1 or coalesce b&r2. Let us do the latter.

Java ScreenShot

  1. We can now coalesce either ae&r1 or coalesce d&r1. Let us do the former.

Java ScreenShot

  1. We cannot now coalesce r1ae&d because the move is constrained: The nodes r1ae and d interfere. We must simplify d.

Java ScreenShot

  1. Now we have reached a graph with only precolored nodes, so we pop nodes from the stack and assign colors to them. First we pick d, which can be assigned color r3. Nodes a, b, and e have already been assigned colors by coalescing. But node c, which was a potential spill, turns into an actual spill when it is popped from the stack, since no color can be found for it.

  1. Since there was spilling in this round, we must rewrite the program to include spill instructions. For each use (or definition) of c, we make up a new temporary, and fetch (or store) it immediately beforehand (or afterward).

Java ScreenShot

  1. Now we build a new interference graph:

Java ScreenShot

  1. Graph-coloring proceeds as follows. We can immediately coalesce c1&r3 and then c2&r3.

Java ScreenShot

  1. Then, as before, we can coalesce a&e and then b&r2.

Java ScreenShot

  1. As before, we can coalesce ae&r1 and then simplify d.

Java ScreenShot

  1. Now we start popping from the stack: We select color r3 for d, and this was the only node on the stack - all other nodes were coalesced or precolored. The coloring is shown at right.

 

Node

Color

a

r1

b

r2

c

r3

d

r3

e

r1

  1. Now we can rewrite the program using the register assignment.

Java ScreenShot

  1. Finally, we can delete any move instruction whose source and destination are the same; these are the result of coalescing.

Java ScreenShot

The final program has only one uncoalesced move instruction.


JaVaScreenshot Previous    Next
Comments