Introduction: This section explain how to implement getReg(I), for a three-address instruction /. There are many options, although there are also some absolute prohibitions against choices that lead to incorrect code due to the loss of the value of one or more live variables. We begin our examination with the case of an operation step, for which we again use x = y z as the generic example.

First, we must pick a register for y and a register for z. The issues are the same, so we shall concentrate on picking register Ry for y. The rules are as follows:

1.  If 2/ is currently in a register, pick a register already containing y as Ry. Do not issue a machine instruction to load this register, as none is needed.

2.  If y is not in a register, but there is a register that is currently empty, pick one such register as Ry.

3.  The difficult case occurs when y is not in a register, and there is no register that is currently empty. We need to pick one of the allowable registers anyway, and we need to make it safe to reuse. Let R be a candidate register, and suppose v is one of the variables that the register descriptor for R says is in R. We need to make sure that u's value either is not really needed, or that there is somewhere else we can go to get the value of R.

The possibilities are:

a)  If the address descriptor for v says that v is somewhere besides R, then we are OK.

b)  If v is x, the value being computed by instruction /, and x is not also one of the other operands of instruction 7 (z in this example), then we are OK. The reason is that in this case, we know this value of x is never again going to be used, so we are free to ignore it.

c)  Otherwise, if v is not used later (that is, after the instruction /, there are no further uses of v, and if v is live on exit from the block, then v is recomputed within the block), then we are OK.

d) If we are not OK by one of the first two cases, then we need to generate the store instruction ST v, R to place a copy of v in its own memory location. This operation is called a spill.

Since R may hold several variables at the moment, we repeat the above steps for each such variable v. At the end, R's "score" is the number of store instructions we needed to generate. Pick one of the registers with the lowest score.

Now, consider the selection of the register Rx. The issues and options are almost as for y, so we shall only mention the differences.

1.  Since a new value of x is being computed, a register that holds only x is always an acceptable choice for Rx. This statement holds even if x is one of y and z, since our machine instructions allows two registers to be the same in one instruction.

2.  If y is not used after instruction I, in the sense described for variable v in item (3c), and Ry holds only y after being loaded, if necessary, then Ry can also be used as Rx. A similar option holds regarding z and Rz. The last matter to consider specially is the case when I is a copy instruction x — y. We pick the register Ry as above. Then, we always choose Rx = Ry.

Previous Next