Updating Data Dependences
Introduction: As illustrated by Example 10.10 below, code motion can change the data dependence relations between operations. Thus data dependences must be updated after each code movement.
Example: For the flow graph shown in Fig. 10.14, either assignment to x can be moved up to the top block, since all the dependences in the original program are preserved with this transformation. However, once we have moved one assignment up, we cannot move the other. More specifically, we see that variable x is not live on exit in the top block before the code motion, but it is live after the motion. If a variable is live at a program point, then we cannot move speculative definitions to the variable above that program point.
Global Scheduling Algorithms: We saw in the last section that code motion can benefit some paths whilehurting the performance of others. The good news is that instructions are notall created equal. In fact, it is well established that over 90% of a program'sexecution time is spent on less than 10% of the code. Thus, we should aim to make the frequently executed paths run faster while possibly making the less frequent paths run slower.
There are a number of techniques a compiler can use to estimate execution frequencies. It is reasonable to assume that instructions in the innermost loops are executed more often than code in outer loops, and that branches that go backward are more likely to be taken than not taken. Also, branch statements found to guard program exits or exception-handling routines are unlikely to be taken. The best frequency estimates, however, come from dynamic profiling. In this technique, programs are instrumented to record the outcomes of conditional branches as they run. The programs are then run on representative inputs to determine how they are likely to behave in general. The results obtained from this technique have been found to be quite accurate. Such information can be fed back to the compiler to use in its optimizations.
Region-Based Scheduling: We now describe a straightforward global scheduler that supports the two easiestforms of code motion:
1. Moving operations up to control-equivalent basic blocks, and
2. Moving operations speculatively up one branch to a dominating predecessor. Recall from Section 9.7.1 that a region is a subset of a control-flow graph that can be reached only through one entry block. We may represent any procedure as a hierarchy of regions. The entire procedure constitutes the top-level region, nested in it are subregions representing the natural loops in the function. We assume that the control-flow graph is reducible.
Algorithm: Region-based scheduling.
INPUT: A control-flow graph and a machine-resource description.
OUTPUT: A schedule S mapping each instruction to a basic block and a time slot.
METHOD: Execute the program in Fig. 10.15. Some shorthand terminology should be apparent: ControlEquiv(B) is the set of blocks that are control equivalent to block B, and Dominated Succ applied to a set of blocks is the set of blocks that are successors of at least one block in the set and are dominated by all. Code scheduling in Algorithm 10.11 proceeds from the innermost regions to the outermost. When scheduling a region, each nested subregion is treated as a black box; instructions are not allowed to move in or out of a subregion.
They can, however, move around a subregion, provided their data and control dependences are satisfied.