Reaching Definitions

Analysis

• $I{n}_s={\bigcup }_{p\in predecessors}Ou{t}_p$
• $Ou{t}_s=Ge{n}_s\bigcup (I{n}_s-Kil{l}_s)$
• In: set of variable definitions that reach here
• Out: set of variable definitions that flow out here
• Gen: set of variable definitions computed in statement
• Kill: set of expressions killed by computations in stmt

Compared to Available Expressions…

Loop Invariant Code Motion

Loop invariant code motion is this idea:

• If a computation inside a loop gives the same result every iteration, move it outside the loop so you don’t redo useless work.

Take this example given in the lecture notes:

proc p(n, x, y) {
    for (i = 0; i < n; i++) {
        a[i] = x + y;
    }
}
 

We can see that x + y is never changed within the loop and thus can be factored out instead of recomputing this on every iteration:

proc p(n, x, y) {
    t = x + y;          // moved out of the loop (code motion)
    for (i = 0; i < n; i++) {
        a[i] = t;
    }
}
 

This transformation is loop invariant code motion:

• loop invariant because the value of the expression doesn’t change on an iteration
• code motion because we move the expression out of the loop

How do we do this formally? We need to know that line 4 (a[i]=x+y) does not contain any definitions of x or y from inside the loop. To do so, this is where we use reaching definitions to check that all variables in an expression are defined outside the loop so that the value doesn’t change across iterations.

• In the example, we calculate the $In$, $Gen$, $Kill$, $Out$ for every line starting at the condition at the start of the loop until the end of the loop. Then we check the $In$ set of the line we want to move or are thinking or moving. We could also look at the in set for all lines in the loop which could uncover which lines we can move outwards.