This transformation moves Scribble CFG nodes to the outer-most basic block in which they may be executed correctly.
Using the SSA use-def links, Scribble CFG nodes are moved into the outer-most basic block in which their dependencies are available. In order to preserve the program semantics, only Scribble CFG nodes containing stores into temporary variables are moved.
The algorithm does a depth first visit to all the Scribble CFG nodes. The nodes in each basic block are numbered with the basic blocks number. The basic block number starts at 0 and is incremented each time a new basic block is encountered. Because the Scribble CFG is in SSA form, we know that the definition for every dependency has already been encountered when we reach any particular Scribble CFG node. (We exclude Phi functions.) Consequently, we can simply compare the current basic block number to the basic block number of the defining Scribble CFG node for every dependency. If it is different, then the Scribble CFG node is moved to the end of the basic block with the highest number containing the definition of a dependency that is at the same or higher loop nesting depth. This results in loop invariant code being moved out of loops and still preserves the SSA form of the Scribble CFG.
Call expressions and expressions involving global variables are never moved.