3

I decided to check the result of loop invariant code motion optimization using g++. However, when I compiled the following code with -fmove-loop-invariants and analysed its assembly, I saw that k + 17 calculation is still performed in the loop body.

What could prevent the compiler from optimizing it?

May be the compiler concludes that it is more efficient to recalculate k + 17?

int main()
{
    int k = 0;
    std::cin >> k;

    for (int i = 0; i < 10000; ++i)
    {
        int n = k + 17; // not moved out of the loop
        printf("%d\n", n);
    }

    return 0;
}

Tried g++ -O0 -fmove-loop-invariants, g++ -O3 and g++ -O3 -fmove-loop-invariants using both g++ 4.6.3 and g++ 4.8.3.

LVK
  • 288
  • 4
  • 13
  • 1
    For all the compiler knows, calling operator>> on k stored a pointer to k in a global variable (k "escapes"), and calling printf might modify k using that global pointer. The compiler is thus unable to perform the optimization you would like. If instead you write a function that takes k as argument by value, the computation of k+17 is moved before the loop. – Marc Glisse Feb 14 '16 at 21:23
  • @MarcGlisse Thanks, got it. I removed `int k = 0; std::cin >> k;` and made `k` a parameter: `main(int k, char **argv)`. Invariant is moved starting from `-O1`. The last small question is why invariant is not moved when compiling with `-O0 -fmove-loop-invariants`? – LVK Feb 14 '16 at 22:37
  • gcc 5.x doesn't seem to move the calculation ... at -O1 and higher it uses `lea esi, [rax+17]` within the loop, perhaps as you say this doesn't take any more cycles than just loading rax by itself. clang 3.7 still does `add esi, 17` within the loop even at `-O3` – M.M Feb 15 '16 at 02:17
  • 2
    `-O0 -fmove-loop-invariants` does not make sense, as -O0 disables all optimizations (even if you try to enable them with -f flags). – Marc Glisse Feb 15 '16 at 08:05
  • @MarcGlisse Ah, I see. Missed it in the docs: "Most optimizations are only enabled if an -O level is set on the command line. Otherwise they are disabled, even if individual optimization flags are specified." I wish gcc notified me about suppressing options. Thank you again. – LVK Feb 15 '16 at 16:01

1 Answers1

1

EDIT: Ignore my previous answer. You can see that the calculation has been folded into a constant. Therefore it is performing the loop invariant optimization.

Because of the as-if rule. Simply put, the compiler is not allowed to make any optimizations that may affect the observable behavior of the program, in this case the printf. You can see what happens if you make n volatile and remove the printf:

for (int i = 0; i < 10000; ++i)
{
    volatile int n = k + 17; // not moved out of the loop
}

// Example assembly output for GCC 4.6.4
// ...
        movl    $10000, %eax
        addl    $17, %edx
.L2:
        subl    $1, %eax
        movl    %edx, 12(%rsp)
// ...
user5924117
  • 49
  • 3
  • 3
    How can precalucaltion of `k+17` influence _observable behaviour_ of `printf`? And unfortunately, I do not understand your demonstration of _as-if rule_ regarding my question. In your example when you declare a variable `volatile`, you tell the compiler not to throw away `n` (i.e. you tell here that optimizing `n` can actually influence _observable behaviour_), but it does not influence `k+17` precalculation and it actually does loop invariant optimization (as you pointed out in your edit). – LVK Feb 14 '16 at 14:08