Why does compiler optimization not generate a loop for sum of integers from 1..N?

Question

In order to understand compilers and in particular assembly language better, I have been experimenting with a trivial piece of code where the sum of the first N numbers is calculated, which should result in N(N+1)/2 or N(N-1)/2.

As the code shows there are two functions:

#include <cstdint>


// Once compiled with optimization, the generated assembly has a loop

uint64_t sum1( uint64_t n ) {  
    uint64_t sum = 0;
    for ( uint64_t j=0; j<=n; ++j ) {
        sum += j;
    }
    return sum;
}

// Once compiled with optimization, the generated assembly of the following has no loop

uint64_t sum2( uint64_t n ) {  
    uint64_t sum = 0;
    for ( uint64_t j=0; j<n; ++j ) {
        sum += j;
    }
    return sum;
}

In the first function I loop from O to N i.e. j<=n and in the second function I go from O to N-1 i.e. j<n.

My understanding/observation:

• For the first function sum1 the generated assembly has a loop while for the second function sum2 the assembly shows no loop. However, once I remove the compiler optimizations i.e. -O3, then you can finally see the loop for the second function in assembly.

• To see the generated assembly with compiler optimization, please see this Optimized.

• To see the generated assembly without compiler optimization, please see this non-optimized.

• Compiler is x86-64 clang

Question: Why does the compiler optimization not show the other loop in the assembly?

Answer 1

This is because your compiler is very, very smart, and it knows that the sum of all values from 0 to n can be calculated with a trivial mathematical formula, instead of a loop.

However, your C++ compiler also figured out that this mathematical formula cannot be used in the <= version because for certain input values a bug gets triggered that results in an infinite loop, so all bets are off, and the compiler compiles the code exactly as given.