LLVM Is Smarter Than Me

This is of course an optimization which is hyper specific and in fact near useless in practice.<p>Converting an awful algorithm into a superior form (from O(N) to O(1)) is a neat trick, but obviously can only apply if: - Such an algorithm can be easily detected by the Compiler and there is actually a replacement algorithm which does <i>exactly</i> the same thing within the defined behavior. These cases are very rare. - The programmer is unable or unwilling to identify the optimization, which in most cases means he does not understand his algorithm well or does not care about performance.<p>Just as an example this substitutions CAN NOT be applied if you replace ints with floats. Of course the O(1) algorithm is still generally preferable in that case a Compiler will never help you with that if you use floats.

Actually that was the reason Compiler Explorer was created in first place, Matt Godbolt wanted an easy way to sort out all the usual discussions &quot;I know better than the compiler&quot; in regards to using C++ abstractions.

Does someone know how the compiler comes up with the closed form solution? Is there a hardcoded list of common patterns and their solution in the compiler, or is this really generated from the code itself?

A small correction: the sigma summation should go to n-1, not n.<p>It&#x27;s weird that LLVM computes n(n-1)&#x2F;2 in such a convoluted way, namely:<p>(n-1)(n-2)&#x2F;2 + n - 1

relevant: <a href="https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;74417624&#x2F;how-does-clang-generate-non-looping-code-for-sum-of-squares" rel="nofollow">https:&#x2F;&#x2F;stackoverflow.com&#x2F;questions&#x2F;74417624&#x2F;how-does-clang-...</a>

Check out the optimizations done by utilizing GVN and SCEV in LLVM, blows my mind every time.

sum of i: 0,n = n(n+1)&#x2F;2 not n(n-1)&#x2F;2