Would the compiler optimize this for loop?

Question

In C or C++, if the compiler encounters a for loop in which a counter is counting from 0 to n, and n is a variable (not a function call, and NOT A CONSTANT either), would the compiler optimize the loop by checking if the variable n (the bound variable) will be changed during the loop (accessed for write, eg: n can be a length of a string that is calculated before the loop), by optimizing here I mean copying its value to a register to avoid memory access?

Here is an example:

for (int c = 0; c < n; c++) {
    // do something not related to n
}

would the compiler notice that and optimize it?

Answer 1

Yes, at least GCC and most other compilers will do this. If you attempt to see what the for loop variable is, the debugger says that the variable has been optimized out, when you compile with -O1 or higher. Of course the compiler is not required to do this. This is what the standard says.

The for statement

for (for-init-statement; conditionopt; expressionopt) statement

is equivalent to

{
    for-init-statement
    while (condition) {
        statement
        expression
    }
}

Answer 2

would the c/c++ compiler optimize the loop by checking if the variable n ( the bound variable ) will be changed during the loop

The "as-if" rule allows the compiler to reorder or re-write code as long as the observable effect is "as if" it executed the code you wrote.

The keyword here is "observable". Unless it can be proven that n cannot change during execution of the body of the loop, then the loop must re-evaluate c < n for each iteration.

If the compiler has access to all the code in the loop (for example, it's defined in the same compilation unit, or a global optimisation has another look during linking, n is never aliased by a reference or pointer) then it may well be in a position to prove that n does not change.

In that case, you should not be surprised to see the loop optimised in some way.

Answer 3

The result depends on the compiler in use.

A compiler could use a processor register for n and you can still modify n within the loop. So minimal optimization is possible anyway.

Placing the value of the variable in a processor register may cause an 'aliasing' problem if you have a pointer pointing to n and you change the value of n indirectly using a pointer.

For example:

int n = 4;
int *nptr = &n;
for(int i = 0; i < n; ++i)
  --*nptr;

The compiler has to know that nptr is an alias for n and therefore n must be read from memory on every access but in many cases the compiler simply has no chance of knowing the relationship between n and nptr.

You can use the volatile keyword to stop the compiler from optimizing the variable (i.e. volatile int n = 4;)

Answer 4

You should try to compile and to see by yourself. Optimizations in compilers depend on several things.

Anyway in order to answer to your question, the only thing I can do is to provide you a specific case which most is similar to your.

The code is simply:

#include <string>

int main(int argc, char *argv[]) {
  std::string str = "this_is_a_string";
  int size = str.size();
  for (int i = 0; i < size; ++i) {
    str += std::to_string(i);
  }
  return 0;
}

The result assembly code is (for different optimization levels):

GCC 6.2 -O0

 movl   $0x0,-0x14(%rbp)    // int i = 0;
 mov    -0x14(%rbp),%eax    // load i into the register
 cmp    -0x18(%rbp),%eax    // load size and compare with i in the register
 jge    401317 <main+0x91>  // jump if >=

GCC 6.2 -O1

 // initialization up
 add    $0x1,%ebx         // ++i (now i is stored in register)
 cmp    %ebx,-0x5c(%ebp)  // compare i and size (which is load from memory)
 je     0x80488a3 <main(int, char**)+136>  // jump if = (and not >=)

GCC 6.2 -O2

Same -O1.

Here the used code, with the assembly.