Invariant Code Motion

THE GENERAL METHOD can be described as follows.

1. A statement a : = b op c in block B of a loop is marked as invariant if all definitions of b and c that are in in_R(B) are outside the loop, or are invariant statements in the loop. Observe that
   • this condition is always satisfied if b,c are constants.
   • if a := b op c is invariant and if a and c do not have other definitions in the loop, then a := a op c is invariant too.
2. Repeat previous step until no more invariant statements are found.

REMARKS.

• We still need to be careful in choosing which invariant statements can be moved to the pre-header.
• The pre-header is always executed whereas the same is not true for all statements in the loop.
• The invariant statement a : = b op c moved to the pre-header need to satisfy the following requirements.
  1. The statement is always executed in the loop. That is, it dominates all the blocks. (Otherwise, different blocks in the loop may need different values of a.)
  2. The statement has to be the only definition of a belonging to in_R(B) for any block B in the loop. (a := 2 and a := 5 can be both invariant in the same loop but none can be moved out.)