When Compilers Surprise You

Summary

When compilers surprise you Written by me, proof-read by an LLM. Details at end. Every now and then a compiler will surprise me with a really smart trick. When I first saw this optimisation I could hardly believe it. I was looking at loop optimisation, and wrote something like this simple function that sums all the numbers up to a given value: So far so decent: GCC has done some preliminary checks, then fallen into a loop that efficiently sums numbers using lea (we’ve seen this before). But taking a closer look at the loop we see something unusual: .L3: lea edx, [rdx+1+rax*2] ; result = result + 1 + x*2 add eax, 2 ; x += 2 cmp edi, eax ; x != value jne .L3 ; keep looping The compiler has cleverly realised it can do two numbers at a time using the fact it can see we’re going to add x and x + 1, which is the same as adding x*2 + 1. Very cunning, I think you’ll agree! If you turn the optimiser up to -O3 you’ll see the compiler works even harder to vectorise the loop using parallel adds. All very clever. This is all for GCC. Let’s see what clang does with our code: This is where I nearly fell off my chair: there is no loop! Clang checks for positive value, and if so it does: lea eax, [rdi - 1] ; eax = value - 1 lea ecx, [rdi - 2] ; ecx = value - 2 imul rcx, rax ; rcx = (value - 1) * (value - 2) shr rcx ; rcx >>= 1 lea eax, [rdi + rcx] ; eax = value + rcx dec eax ; --eax ret It was not at all obvious to me what on earth was going on here. By backing out the maths a little, this is equivalent to: v + ((v - 1)(v - 2) / 2) - 1; Expanding the parentheses: v + (v² - 2v - v + 2) / 2 - 1 Rearranging a bit: (v² - 3v + 2) / 2 + (v - 1) Multiplying the (v - 1) by 2 / 2: (v² - 3v + 2) / 2 + (2v - 2)/2 Combining those and cancelling: Simplifying and factoring gives us v(v - 1) / 2 which is the closed-form solution to the “sum of integers”! Truly amazing - we’ve gone from an O(n) algorithm as written, to an O(1) one! I love that despite working with compilers for more than twenty yea...