Lesson 5: Global Analysis



Lots of definitions!

An algorithm for finding dominators:

dom = {every block -> all blocks}
dom[entry] = {entry}
while dom is still changing:
    for vertex in CFG except entry:
        dom[vertex] = {vertex} ∪ ⋂(dom[p] for p in vertex.preds}

The dom relation will, in the end, map each block to its set of dominators. We initialize it as the “complete” relation, i.e., mapping every block to the set of all blocks. The exception is the entry block, which we ensure always only has itself as a dominator. (This keeps the algorithm from being confused by blocks that jump back to the entry node.) The loop pares down the sets by iterating to convergence.

The running time is O(n²) in the worst case. But there’s a trick: if you iterate over the CFG in reverse post-order, and the CFG is well behaved (reducible), it runs in linear time—the outer loop runs a constant number of times.

Natural Loops

Some things about loops:

Loop-Invariant Code Motion

Here’s a preview of what we’ll do with natural loops. The loop-invariant code motion (LICM) optimization transforms code like this:

let a = ...;
let b = ...;
for (let i = 0; i < 100; ++i) {
    f(a * b);

Into this, by moving code that does the same thing on every iteration to the loop’s pre-header block:

let a = ...;
let b = ...;
let c = a * b;
for (let i = 0; i < 100; ++i) {

That is, we want to move code from inside the loop to before it—when that computation always results in the same value. We’ll return to LICM in Lesson 8.