[archgoon]

So fun fact, if you compile

  int sum(int n) {
      int sum = 0;
      for(int i = 0; i < n; i++) {
          sum +=i;
      }
      return sum;
  }

clang, with -O2, will turn this into the polynomial (n+1)*n//2. It can also do similar transformations for multiple loops.

https://godbolt.org/z/so6neac33

So if you do a brute force solution which could have been reduced to a polyomial, clang has a shot of doing just that.

[sbrother]

That is mind blowing, but it’s not immediately obvious to me that it’s equivalent for n > sqrt(INT_MAX). Is it? And if so, is the compiler somehow smart enough to know that?

[marin049]

Integer overflow is actually undefined behaviour thus the compiler is free to assume it doesn't happen.

[xigoi]

If you assume two’s complement arithmetic, then this is always equivalent because you’re basically just calculating the answer in a modular ring.

[j2kun]

I believe the term for this is scalar evolution.

[archgoon]

Yep! That is it alright.

Here's a talk from an llvm conference with the details.

https://www.youtube.com/watch?v=AmjliNp0_00