0
$\begingroup$

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--;
}
$\endgroup$
  • $\begingroup$ Note: The wikipedia page is fixed now. $\endgroup$ – gnasher729 Apr 27 at 19:39
0
$\begingroup$

You can also replace with

if (loop_condition) {
    loop_invariant_code
    do {
        loop_body
    } while (loop_condition)
}

With all he precautions of course. That makes the loop a bit simpler, and saves one test of the condition. And because you have no extra evaluations of loop_condition, this should be correct even if loop_condition has side effects.

And in the first example starting with i = 10 you should be able to optimise the first loop condition away.

But absolutely, you cannot just move code with side effects out of a loop, and you should be careful moving code without side effects, in case the loop is not executed and the moved code just wastes time. This more critical in languages that do overflow checks, so adding a+b can actually have a side effect on overflow.

Note: The wikipedia article also mentions strength reduction (for example, instead of calculating i*6, set tmp = 0 before the loop starts, and increase tmp by six at each iteration). Setting tmp = 0 would also only be executed if the loop condition is tested once.

$\endgroup$
  • $\begingroup$ Thank you for your answer! I've not considered using a loop with a post-check (as well as putting the whole thing inside the if). I'm however still wondering why is this not covered by any literature on the topic (Aho and Ullman would be the prime example). So I'm kind of afraid of implementing the optimization in the way you suggested... $\endgroup$ – aolo2 Apr 27 at 19:13
  • $\begingroup$ Being kind of afraid adding optimisations to a compiler is the right approach :-) Moving the test to the end of the loop is often done in a similar way. And PowerPC / POWER produce extra fast loops if you can calculate the actual iteration count before you start iterating; basically the iteration is exactly as fast as an unconditional jump. $\endgroup$ – gnasher729 Apr 27 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.