Can C++ compilers optimize "if" statements inside "for" loops?

Question

Consider an example like this:

if (flag)
  for (condition)
    do_something();
else
  for (condition)
    do_something_else();

If flag doesn't change inside the for loops, this should be semantically equivalent to:

for (condition)
  if (flag)
    do_something();
  else
    do_something_else();

Only in the first case, the code might be much longer (e.g. if several for loops are used or if do_something() is a code block that is mostly identical to do_something_else()), while in the second case, the flag gets checked many times.

I'm curious whether current C++ compilers (most importantly, g++) would be able to optimize the second example to get rid of the repeated tests inside the for loop. If so, under what conditions is this possible?

Answer 1

Yes, if it is determined that flag doesn't change and can't be changed by do_something or do_something_else, it can be pulled outside the loop. I've heard of this called loop hoisting, but Wikipedia has an entry called "loop invariant code motion".

If flags is a local variable, the compiler should be able to do this optimization since it's guaranteed to have no effect on the behavior of the generated code.

If flags is a global variable, and you call functions inside your loop it might not perform the optimization - it may not be able to determine if those functions modify the global.

This can also be affected by the sort of optimization you do - optimizing for size would favor the non-hoisted version while optimizing for speed would probably favor the hoisted version.

In general, this isn't the sort of thing that you should worry about, unless profiling tells you that the function is a hotspot and you see that less than efficient code is actually being generated by going over the assembly the compiler outputs. Micro-optimizations like this you should always just leave to the compiler unless you absolutely have to.

Answer 2

I'm sure if the compiler can determine that the flag will remain constant, it can do some shufflling:

const bool flag = /* ... */;
for (..;..;..;)
{
    if (flag)
    {
        // ...
    }
    else
    {
        // ...
    }
}

If the flag is not const, the compiler cannot necessarily optimize the loop, because it can't be sure flag won't change. It can if it does static analysis, but not all compilers do, I think. const is the sure-fire way of telling the compiler the flag won't change, after that it's up to the compiler.

As usual, profile and find out if it's really a problem.

Answer 3

It's called a loop invariant and the optimization is called loop invariant code motion and also code hoisting. The fact that it's in a conditional will definitely make the code analysis more complex and the compiler may or may not invert the loop and the conditional depending on how clever the optimizer is.

There is a general answer for any specific case of this kind of question, and that's to compile your program and look at the generated code.

Answer 4

I would be wary to say that it will. Can it guarantee that the value won't be modified by this, or another thread?

That said, the second version of the code is generally more readable and it would probably be the last thing to optimize in a block of code.

Answer 5

Generally, yes. But there is no guarantee, and the places where the compiler will do it are probably rare.

What most compilers do without a problem is hoisting immutable evaluations out of the loop, e.g. if your condition is

if (a<b) ....

when a and b are not affected by the loop, the comparison will be made once before the loop.

This means if the compiler can determine the condition does not change, the test is cheap and the jump wenll predicted. This in turn means the test itself costs one cycle or no cycle at all (really).

In which cases splitting the loop would be beneficial?

a) a very tight loop where the 1 cycle is a significant cost
b) the entire loop with both parts does not fit the code cache

Now, the compiler can only make assumptions about the code cache, and usually can order the code in a way that one branch will fit the cache.

Without any testing, I'dexpect a) the only case where such an optimization would be applied, becasue it's nto always the better choice:

In which cases splitting the loop would be bad?

When splitting the loop increases code size beyond the code cache, you will take a significant hit. Now, that only affects you if the loop itself is called within another loop, but that's something the compiler usually can't determine.

[edit]
I couldn't get VC9 to split the following loop (one of the few cases where it might actually be beneficial)

extern volatile int vflag = 0;

int foo(int count)
{
   int sum = 0;
   int flag = vflag;
   for(int i=0; i<count; ++i)
   {
      if (flag)
         sum += i;
      else
         sum -= i;
   }

   return sum;
}

[edit 2]
note that with int flag = true; the second branch does get optimized away. (and no, const doesn't make a difference here ;))

What does that mean? Either it doesn't support that, it doesn't matter, ro my analysis is wrong ;-)

Generally, I'd asume this is an optimization that is valuable only in a very few cases, and can be done by hand easily in most scenarios.

Answer 6

As many have said: it depends.

If you want to be sure, you should try to force a compile-time decision. Templates often come in handy for this:

for (condition)
  do_it<flag>();

Answer 7

Tried with GCC and -O3:

void foo();
void bar();

int main()
{
    bool doesnt_change = true;
    for (int i = 0; i != 3; ++i) {
        if (doesnt_change) {
            foo();
        }
        else {
            bar();
        }
    }
}

Result for main:

_main:
pushl %ebp
movl %esp, %ebp
andl $-16, %esp
call ___main
call __Z3foov
call __Z3foov
call __Z3foov
xorl %eax, %eax
leave
ret

So it does optimize away the choice (and unrolls smaller loops).

This optimization is not done if doesnt_change is global.