When compilers surprise you

https://xania.org/202512/24-cunning-clang

by brewmarche • 7 months ago

244 63 7 months ago

xania.org

dejj• 7 months ago

It’s neat. I wonder if someone attempted detecting a graph coloring problem to replace it with a constant.

emih• 7 months ago

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.)

andrepd• 7 months ago

I'm actually surprised that gcc doesn't do this! If there's one thing compilers do well is pattern match on code patterns and replace with more efficient ones; just try pasting things from Hacker's Delight and watch it always canonicalise it to the equivalent, fastest machine code.

nikic• 7 months ago

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).

f1shy2• 7 months ago

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.

morkalork• 7 months ago

First time I encountered that book was seeing it on the desk of a compiler engineer.

g0wda• 7 months ago

If you now have a function where you call this one with an integer literal, you will end up with a fully inlined integer answer!

loeg3• 7 months ago

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

JonChesterfield• 7 months ago

That one is called scalar evolution, llvm abbreviates it as SCEV. The implementation is relatively complicated.

gslin• 7 months ago

More similar optimizations: https://matklad.github.io/2025/12/09/do-not-optimize-away.ht...

Lvl999Noob• 7 months ago

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.

saagarjha3• 7 months ago

Yes, a sufficiently smart compiler can always tell you’re doing a benchmark and delete it. It’s just unlikely.

wging• 7 months ago

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.

phplovesong• 7 months ago

This exact content was posted a few months ago. Is this AI or just a copy paste job?

mattgodbolt2• 7 months ago

This exact content was only posted today? :)

ForceBru• 7 months ago

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

dist-epoch• 7 months ago

I love that despite working with compilers for more than twenty years, they can still surprise and delight me.

This kind of optimization, complete loop removal and computing the final value for simple math loops, is at least 10 years old.

nebezb• 7 months ago

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.

f1shy2• 7 months ago

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.

bumholes• 7 months ago

The code that does this is here, if anyone is curious:

https://github.com/llvm/llvm-project/blob/release/21.x/llvm/...

vodou2• 7 months ago

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

zahlman• 7 months ago

I do too, but I'm pretty sure I've seen worse.

loeg3• 7 months ago

Does it really matter where the lines are? 16,000 lines is still 16,000 lines.

j-o-m• 7 months ago

I find the real question: are all 16,000 of those lines require to implement the optimization? How much of that is dealing with LLVM’s internal representation and the varying complexity of LLVM’s other internal structure?

bitwizeshift• 7 months ago

Thank you, bumholes

vatsachak• 7 months ago

Compilers can add way more closed forms. Would it be worth it?

https://en.wikipedia.org/wiki/Wilf%E2%80%93Zeilberger_pair

j16sdiz• 7 months ago

The first thing I had in mind was: the final answer needed to be /2. keeping the number before dividing not overflowing needs some tedious work

trehalose• 7 months ago

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.

Neywiny2• 7 months ago

I'm once again surprised at GCC being slower than clang. I would have thought that GCC, which had a 20? year head start would've made faster code. And yet, occasionally I look into the assembly and go "what are you doing?" And the same flags + source into clang is better optimized or uses better instructions or whatever. One time it was bit extraction using shifts. Clang did it in 2 steps: shift left, shift right. GCC did it in 3 I think? I think it maybe shifted right first or maybe did a logical instead of arithmetic and then sign extended. Point is, it was just slower.

stmw• 7 months ago

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.

uecker• 7 months ago

Not sure whether this is generally true. GCC appears to have similar optimizations and I personally find LLVM's code much more intimidating. But it is certainly true that LLVM seems to see more investment. I assume the license may also play a role. For comparison, here is some related code:

https://github.com/gcc-mirror/gcc/blob/master/gcc/tree-chrec... https://github.com/llvm/llvm-project/blob/release/21.x/llvm/...

saagarjha3• 7 months ago

GCC has almost the same modern compiler techniques implemented.

fweimer• 7 months ago

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.

Neywiny2• 7 months ago

It did, yes. On an architecture without bit field extracts.

saagarjha3• 7 months ago

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.

userbinator• 7 months ago

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.

tester756• 7 months ago

A lot of hardcoding, making expression consistent, e.g transforming a+3 into 3+a for easier pattern matching

vardump• 7 months ago

Only thing that surprised me was that GCC didn't manage to optimize it. I expected it to be able to do so.

MobiusHorizons3• 7 months ago

I will admit I was initially surprised Matt was not already familiar with this behavior given his reputation. I remember discovering it while playing with llvm intermediate representation 10 years ago in college. I would never have considered myself very knowledgeable about modern compilers, and have never done any serious performance work. In that case it had solved a recursion to a simple multiplication, which completely surprised me. The fact that Matt did not know this makes me think this pass may only work on relatively trivial problems that he would never have written in the first place, and therefore never have witnessed the optimization.

pwdisswordfishy• 7 months ago

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

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

MobiusHorizons3• 7 months ago

Ah that makes much more sense. I guess he means the optimization is surprising when you first discover it, which it certainly was for me!

WalterBright3• 7 months ago

These sorts of things are fun and interesting. Compiler optimizations fall into two categories:

1. organized data flow analysis

2. recognizing a pattern and replacing it with a faster version

The first is very effective over a wide range of programs and styles, and is the bulk of the actual transformations. The second is a never-ending accumulation of patterns, where one reaches diminishing returns fairly quickly.

The example in the linked article is very clever and fun, but not really of much value (I've never written a loop like that in 45 years). As mentioned elsewhere "Everyone knows the Gauss Summation formula for sum of n integers i.e. n(n+1)/2" and since everyone knows it why not just write that instead of the loop!

Of course one could say that for any pattern, like replacing i*2 with i<<1, but those pattern replacements are very valuable because they are generated by high level generic coding.

And you could say I'm just being grumpy about this because my optimizer does not do this particular optimization. Fair enough!

Validark2• 7 months ago

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.

WalterBright3• 7 months ago

You might be right.

gizmo686• 7 months ago

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.

steveklabnik• 7 months ago

I can't actually speak to the specifics here but usually this is "idiom recognition", that is, it just notices that the pattern is there and transforms it directly.

lucyjojo• 7 months ago

isn't that kind of stuff mostly useful for generated code?

WalterBright3• 7 months ago

One recognizes different patterns for both the intermediate representation and the generated code.

jojomodding• 7 months ago

The point is not really that the compiler is able to spot the Gaussian sum. It uses a general infrastructure to turn many "math loops" that sum/multiply numbers into closed-form solutions. This handles Gauss but is much more general. In turn it allows you to write simple code that still does the right thing, instead of a complicated-looking large multiplication with a bunch of random-seeming constants.

Animats• 7 months ago

That's neat.

A hard problem in optimization today is trying to fit code into the things complex SSE-type instructions can do. Someone recently posted an example where they'd coded a loop to count the number of one bits in a word, and the compiler generated a "popcount" instruction. That's impressive.

mattgodbolt2• 7 months ago

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

Validark2• 7 months ago

What's actually way cooler about this is that it's generic. Anybody could pattern match the "sum of a finite integer sequence" but the fact that it's general purpose is really awesome.

cjdell• 7 months ago

This is really bluring the line between implementation and specification. You may think you're writing the implementation but it is really a proxy for the specification. In other words, the compiler creating an illusion of an imperative machine.

When compilers surprise you

Related Stories