LLVM turns loops into algebra: how power sums get optimized

The surprise

It has been reported that LLVM can take a simple loop that sums j*j and emit code that never iterates — no loop, no branch, just arithmetic that evaluates the closed-form result. Wild? A little. Neat? Absolutely. Inspecting the generated assembly on Godbolt shows the compiler computing a polynomial formula instead of accumulating in a loop, and it allegedly handles more complex polynomial patterns, not just textbook cases.

The trick: scalar evolution and chains of recurrences

The secret sauce is LLVM’s (and GCC’s) Scalar Evolution analysis. The pass models each loop-produced value as a recurrence: a starting value and a rule for how the value changes each iteration. Chains of such recurrences can represent polynomials in the loop index, so j, j*j, j^3 and combinations become structured objects like {phi, +, next}. Once expressed that way, the compiler can either derive a closed-form sum or convert the loop into a small number of induction updates — think a handful of adds instead of per-iteration multiplications — or fold everything into one polynomial evaluation.

Why it matters

This isn’t just cleverness for its own sake. Eliminating loops or turning them into cheap induction updates shrinks branch pressure, improves vectorization opportunities, and can cut expensive operations on targets where multiplications are costly. It’s a reminder that modern compilers are part algebra system, part optimizer — quietly doing math we were told to memorize in school, and turning it into faster machine code. Who needs a loop when the compiler remembers calculus for you?

Sources: kristerw.blogspot.com, Lobsters