Question

I've been implementing LICM for a project, and came upon a strange observation.

Let's say we have a loop

int i = 10;
while (i > 0) {
    a = 2;
    i--;
}

One can easily see that a = 2 is invariant. What we do next is check (for each invariant candidate) if the containing basic block dominates all uses of the said variable and all exits of the loop.

The former is clearly true, as a is only used once. The latter is what I don't seem to get. The CFG of the example above is

control flow graph

By looking at the graph we can clearly see that the cycle body (which is just a single basic block in this case) does not dominate all exits!

After thinking about this for some time, I got to the following conclusion:


In a general case, we can not know for sure if the body of a loop is going to be executed at least once. This implies that one can not simply move invariant instructions out of the loop, as they will then be executed dependless of the actual value of the loop termination condition.


I have not seen this adressed in any of the material covering LICM, as well as in the wikipedia article. In fact, their example, in which they transform

for (int i = 0; i < n; ++i) {
    x = y + z;
    a[i] = 6 * i + x * x;
}

into

x = y + z;
t1 = x * x;
for (int i = 0; i < n; ++i) {
    a[i] = 6 * i + t1;
}

seems incorrect, as the loop condition generally could have been false on the first iteration, and so x = y + z should not have been executed at all.

My proposed solution

All code deemed invariant should be put in an if (expr), where expr is the loop condition. For my original example, that would give us

int i = 10;
if (i > 0) {
   a = 2;
}
while (i > 0) {
    i--;
}

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top