c++ : Can the compiler optimize this code segment?

Question

void foo(const int constant)
{
    for(int i = 0; i < 1000000; i++) {
        // do stuff
        if(constant < 10) {              // Condition is tested million times :(
            // inner loop stuff
        }
    }
}

For every execution of the outer loop the value of "constant" is checked. However, constant never changes so a lot of CPU time is being wasted to test the condition constant < 10? over and over again. A human would realize after the first few passes that constant never changes, and intelligently avoid checking it over and over again. Does the compiler notice this and intelligently optimize it, or is the repeated if loop unavoidable?

Personally, I think the problem is unavoidable. Even if the compiler put the comparison before the outer loop and set some kind of boolean variable "skip_inner_stuff" this variable would still have to be checked for each pass of the outer for loop.

What are your thoughts on the matter? Is there a more efficient way to write the above code segment that would avoid the problem?

Answer 1

The optimization you describe is also called loop unswitching. It has been a standard part of optimizing compilers for many years - but if you want to make sure your compiler performs it, compile your sample code with some optimization level (e.g. -O2 in gcc) and check the generated code.

However, in cases where the compiler cannot prove that a piece of code is invariant throughout the loop - e.g. a call to an external function which is not available at compile time - then indeed, manually hoisting the code to be outside the loop can net a very big performance boost.

Answer 2

Compiler can optimize the code but you couldn't expect it does a magic tricks on your code.

The optimization strongly depends on your code and the usage of your code. For example if you use foo like this:

foo(12345);

Compiler can optimize the code very much. Even it can compute the result in compile time.

But if you use it like this:

int k;
cin >> k;
foo(k);

In this case it can not get rid of inner if (the value is provided in run-time).

I wrote a sample code with MinGW/GCC-4.8.0:

void foo(const int constant)
{
    int x = 0;
    for (int i = 0; i < 1000000; i++)
    {
        x++;
        if (constant < 10)
        {
            x--;
        }
    }
    cout << x << endl;
}

int main()
{
    int k;
    cin >> k;
    foo(k);
}

Let's see the generate assembly code:

004015E1  MOV EAX,0F4240                 // i = 1000000
004015E6  MOV EBP,ESP
004015E8  XOR EDX,EDX
004015EA  PUSH ESI
004015EB  PUSH EBX
004015EC  SUB ESP,10
004015EF  MOV EBX,DWORD PTR SS:[EBP+8]
004015F2  XOR ECX,ECX                    // set ECX to 0
004015F4  CMP EBX,0A                     // if constant < 10
          ^^^^^^^^^^
004015F7  SETGE CL                       // then set ECX to 1
004015FA  ADD EDX,ECX                    // add ECX to i
004015FC  SUB EAX,1                      // i--
004015FF  JNE SHORT 004015F2             // loop if i is not zero

As you can see the inner if exists in the code. See CMP EBX,0A.

I repeat again it strongly depends on the lines with loops.