When compilers surprise you

Original Article ↗ Hacker News Discussion ↗

Loop-to-closed-form optimization (SCEV)

  • Commenters explain the optimization as LLVM’s Scalar Evolution (SCEV): it models loop variables symbolically and computes the loop’s final value via binomial coefficients, even for some non-affine recurrences.
  • This is not just pattern-matching “sum of 0..N-1”, but a generic analysis that can also handle more complex polynomials (e.g., sums of powers).
  • With an integer literal argument and inlining, this can reduce the whole function call to a constant at compile time; some note C++20 consteval gives similar behavior explicitly.

Pattern matching vs general analyses

  • Several comments distinguish “idiom recognition” (pattern-matching common code shapes) from broad data-flow analyses like SCEV.
  • Pattern libraries (e.g., for popcount or bit tricks à la Hacker’s Delight) are useful but inherently limited; scalar evolution enables many optimizations beyond math loops.

GCC vs Clang behavior

  • Some are surprised GCC doesn’t perform this specific transformation; others point to roughly comparable overall optimization strength, with each having wins in different cases.
  • There are anecdotes of Clang generating better code than GCC (e.g., bit extraction), and notes that GCC is weaker on bitfields.
  • A side discussion touches on GCC’s architecture, perceived difficulty of adding modern techniques, and LLVM attracting more investment, possibly helped by licensing.

Size and structure of optimizer code

  • The SCEV implementation being ~16k lines in a single file prompts debate:
    • Some see it as natural for a tightly coupled analysis; others worry it signals “spaghetti” complexity and hampers maintainability.
    • Navigation strategies (e.g., Vim vs IDEs), potential use of DSLs, and desires for formally proved transformations (e.g., with Lean or e-graphs) are discussed.
    • There’s curiosity how much of those 16k LOC is true algorithmic work vs glue to LLVM’s IR.

Correctness, overflow, and math nitpicks

  • One commenter corrects the exact summation formula (0..N-1 vs 1..N) and notes overflow concerns with N*(N+1)/2; another suggests dividing the even factor first to mitigate overflow.

Benchmarking and optimizer “cleverness”

  • Linked material about compilers “optimizing away” benchmarks leads to joking that a “sufficiently smart compiler” could always detect and fold them, though this is considered unlikely in practice.

Perceived novelty and rarity

  • Some note loop-elimination of this kind has existed for at least a decade, but others argue it’s reasonable for practitioners to still be surprised by rarely encountered compiler tricks.
  • There’s disagreement over practical value: one person claims they’d just write the closed form directly; others emphasize that SCEV’s main payoff is enabling many other optimizations, not just this toy example.

Hardware-centric optimizations

  • Beyond arithmetic sums, commenters mention compilers mapping hand-written loops (e.g., bit-counting) onto single complex instructions like popcount, and more generally the challenge of matching scalar code to rich SIMD/SSE instruction sets.

Philosophical angle

  • One reflection is that such optimizations blur the line between “implementation” and “specification”: what looks like imperative code is increasingly interpreted as a higher-level mathematical description that the compiler is free to re-express.