It's not clear to me what optimizations the compiler actually did here. Years ago, I worked on a niche compiler, and was routinely surprised by what the optimizer was able to figure out; despite having personally written most of the optimization transformations myself.

It might have more value than you think. If you look up SCEV in LLVM you'll see it's primarily used for analysis and it enables other optimizations outside of math loops that, by themselves, probably don't show up very often.

Almost 16000 lines in a single source code file. I find this both admirable and unsettling.

Thank you, bumholes

The beginning of that article is slightly wrong: the compiler should compute N(N-1)/2 (and does), because the original code adds up all the numbers from 0 to N excluding N. The usual formulation in math includes the upper bound: the sum of integers from 1 to N, including N, is N(N+1)/2, so you have to replace N by (N-1) if you want a formula for the sum where the last number is N-1.

Couldn't the compiler optimise this still? Make two versions of the function, one with constant folding and one without. Then at runtime, check the value of the parameter and call the corresponding version.

GCC and Clang are largely similar when it comes to performance as each implements passes the other does not. It’s always possible to find examples where they optimize a piece of code differently and one comes out ahead of the other.

Compiler know-how and resources available during compilations made very signicant progress between gcc and LLVM/clang era.

gcc was and is an incredible achievement, but it is traditionally considered difficult to implement many modern compiler techqniques in it. It's at least unpleasant, let's put it this way.

I'm not. GCC started out as a work of idealistic licensing purists and was deliberately "obfuscated" to make it hard to extend and embed. That stance has since been softened considerably, but the code generator is still far more complex than it needs to be, and I think that has made it harder to modify for efficiency. Clang is far less ideology-focused and its structure makes implementing optimisations easier.

On the other hand, I find MSVC and especially ICC output to be quite decent, although I have never seen their source code.

Having inspected the output of compilers for several decades, it's rather easy to tell them apart.

Did it involve bitfields? GCC is notoriously bad at optimizing them. There are some target-specific optimizations, but pretty much nothing in the middle-end.

Graph coloring is NP-hard so it would be very difficult to replace it with an O(1) algorithm.

If you mean graph coloring restricted to planar graphs, yes it can always be done with at most 4 colors. But it could still be less, so the answer is not always the same.

(I know it was probably not a very serious comment but I just wanted to infodump about graph theory.)

He was: he brought up the very same example in a talk in 2017.

https://www.youtube.com/watch?v=bSkpMdDe4g4&t=2640

It may be a different post, but I covered this earlier this month in the same series of blog posts/YouTube videos.

It's not very tedious. Instead of dividing the product by 2, you can just divide whichever of x or x+1 is even by 2 before multiplying.

Could do that whether SCEV’d or not with C++20 consteval, lol.

This particular case isn't really due to pattern matching -- it's a result of a generic optimization that evaluates the exit value of an add recurrence using binomial coefficients (even if the recurrence is non-affine). This means it will work even if the contents of the loop get more exotic (e.g. if you perform the sum over x * x * x * x * x instead of x).

Doing something like that with a pattern is obvious, but also useless, as it will catch very limited cases. The example presented, is known there is a closed form (it’s believed Gauss even discovered it being 6 yo). I’m sure this optimization will catch many other things, so is not trivial at all.

10 years is not a lot. Is almost “yesterday” things being done in a field 10 years old, can still surprise experts in the field. With 30+ years experience I still find relatively new things, that are maybe 15 yo.

In topics like compiler optimization, is not like there are many books which describe this kind of algorithms.

Learning something old can be surprising. Enjoying that learning can be delightful.

Seems like the author is both surprised and delighted with an optimization they learned of today. Surely you’ve been in the same situation before.

You're probably thinking of another post (https://xania.org/202512/11-pop-goes-the-weasel-er-count) where an entire loop was optimized to a single instruction

This exact content was only posted today? :)