10.2.1 Loop-Invariant Computations and Code Motion
Loop-invariant statements are shose statements within a loop which produce the same value each time the loop is executed. We identify them and then move them outside the loop.
Example 7 shows a control flow graph and a loop-invariant statement.
Preheaders
For each loop, create a new block, which has only the header as a successor. This is called a preheader and is not part of the loop. It is used to hold statements moved out of the loop. Here, these are the loop-invariant statements. In the next section, the preheader will be used to hold initializations for the induction variables.
Code Motion Algorithm
If a statements is loop-invariant, it is moved to the preheader provided (1) the movement does not change what the program computes and 2) the program does not slow up.
Algorithm
Loop-Invariant Code Motion
Given the nodes in a loop, compute the definitions reaching the header
and dominator.
Find the loop-invariant statements.
Find the exits of the loop: the nodes with a successor outside the loop.
Select for code motion those statements that:
(i) are loop-invariant and
(ii) are in blocks that dominate exits and
(iii) are in blocks that dominate all blocks in the loop which use their
computed values and
(iv) assign to variables not assigned to elsewhere in loop
Perform a depth-first search of the loop. Visit each block in depth-first order, moving all statements selected above to the preheader.
The last step preserves the execution order.
Moving statements to the preheader may cause the program to slow down if the loop is never entered. The criterion that the loop never slow down may be enforced by executing the statements in the preheader only if the loop is executed.
Taking this one step further, the condition:
WHILE Condition DO Statements
becomes
IF Condition
THEN Preheader
REPEAT
Statements
UNTIL NOT Condition
ENDIF
Now the preheader is executed only if the loop is entered.