Tag Archives: Register Sufficiency For Loops

Register Sufficiency For Loops

We finally get to the book problem that was the basis for our diversion.

The problem: Register Sufficiency For Loops.   This is problem PO3 in the appendix.

The description: Given a set of variables to be used within a loop of N instructions, and a set of K registers.  Each variable has a “lifetime” defined by the instruction in the loop we start needing its value, and the number of instructions we will that need that value for). We can assign two variables to the same register if they do not overlap in their lifetimes (keeping in mind that “overlap” includes wrapping around to the start of the next loop iteration).  Can we assign variables to registers such that there is no overlap?

Example: I think it’s easier to understand the concept of a “lifetime” of a variable by showing an example of a loop:

B
C
B
C
A
C
A
C
A
C
B
C
B

In this loop, we will need one register to hold C (because we’re basically using it the whole time), but the other register can alternate between holding A and B.  It holds A in the middle of the loop, but it can hold B from the end of one iteration through the start of the next.

If I added an extra B in the middle of the A instructions, I would need 3 registers (because we can’t have 1 register holding A and B because the “middle” use of B would conflict with the need to hold A).

Reduction: While this is the main result for us, this problem is mentioned as an aside in the Garey, Johnson, Miller, and Papadimitriou paper we have been working with for the past few weeks.

The idea is that this problem is very similar to Arc Coloring.  They show the problems are similar, which is sort of like doing the reduction backwards (“Look, any loop can be represented as a set of arcs!”).  But if we start from an Arc Coloring instance, we can create a loop with one statement for each point in the circle, and each arc connects the first and last uses of a variable (so the arc spans the lifetime of the variable).

The idea now is that a coloring of the graph is a way to color the arcs of the graph so that no two arcs overlap at a point.  This is exactly the same as saying we can assign a register to a set of instructions (matching the 2 uses of a variable) so that the same register is not in use during the lifetimes of two variables assigned to that register.

Difficulty: The actual reduction here is a 4.  (I think it’s a little tricky to understand the idea of a lifetime of a variable, and how it can be represented as just 2 points in the circle)  But it may be more complicated than that to explain what an arc graph is, and does.