Phase Ordering Between Register Allocation and Code Scheduling
Introduction: If registers are allocated before scheduling, the resulting code tends to have many storage dependences that limit code scheduling. On the other hand, if code is scheduled before register allocation, the schedule created may require so many registers that register spilling (storing the contents of a register in a memory location, so the register can be used for some other purpose) may negate the advantages of instruction-level parallelism. Should a compiler allocate registers first before it schedules the code? Or should it be the other way round? Or, do we need to address these two problems at the same time?
To answer the questions above, we must consider the characteristics of the programs being compiled. Many nonnumeric applications do not have that much available parallelism. It suffices to dedicate a small number of registers for holding temporary results in expressions. We can first apply a coloring algorithm, as in Section 8.8.4, to allocate registers for all the non-temporary variables, then schedule the code, and finally assign registers to the temporary variables.
This approach does not work for numeric applications where there are many more large expressions. We can use a hierarchical approach where code is optimized inside out, starting with the innermost loops. Instructions are first scheduled assuming that every pseudo-register will be allocated its own physical register. Register allocation is applied after scheduling and spill code is added where necessary, and the code is then rescheduled. This process is repeated for the code in the outer loops. When several inner loops are considered together in a common outer loop, the same variable may have been assigned different registers. We can change the register assignment to avoid having to copy the values from one register to another. In Section 10.5, we shall discuss the interaction between register allocation and scheduling further in the context of a specific scheduling algorithm.
Control Dependence: Scheduling operations within a basic block is relatively easy because all theinstructions are guaranteed to execute once control flow reaches the beginningof the block. Instructions in a basic block can be reordered arbitrarily, as long asall the data dependences are satisfied. Unfortunately, basic blocks, especially innonnumeric programs, are typically very small; on average, there are only aboutfive instructions in a basic block. In addition, operations in the same block areoften highly related and thus have little parallelism. Exploiting parallelismacross basic blocks is therefore crucial.
An optimized program must execute all the operations in the original program. It can execute more instructions than the original, as long as the extra instructions do not change what the program does. Why would executing extra instructions speed up a program's execution? If we know that an instruction is likely to be executed, and an idle resource is available to perform the operation "for free," we can execute the instruction speculatively. The program runs faster when the speculation turns out to be correct.
An instruction n is said to be control-dependent on instruction i2 if the outcome of i2 determines whether h is to be executed. The notion of control dependence corresponds to the concept of nesting levels in block-structured programs. Specifically, in the if-else statement
if (c) s i ; e l s e s2;
si and s2 are control dependent on c. Similarly, in the while-statement while (c) s; the body s is control dependent on c.
Example: In the code fragment
i f (a > t)
b = a*a;
d = a c;
the statements b = a*a and d = a c have no data dependence with any other part of the fragment. The statement b = a*a depends on the comparison a > t. The statement d = a c, however, does not depend on the comparison and can be executed any time. Assuming that the multiplication a * a does not cause any side effects, it can be performed speculatively, as long as b is written only after a is found to be greater than t.