Hasty Briefsbeta

All tags

compiler optimization

20 stories total

Bilingual

Register deprivation: spills and runtime under forced register scarcity
2 months ago
- Reserving registers via gcc -ffixed-<reg> reliably increases spills, but static spill count is a weak predictor of runtime cost (Pearson r=0.55).
- Removing registers slows 8 of 9 kernels by 14–76% at the tightest budget; SipHash shows no slowdown despite 23 added spills.
- The slowdown is specific to the register file used: e.g., reserving GP registers on SHA-256 costs +33%, while reserving XMM costs only +5.6%.
- GCC auto-vectorizes part of SHA-256 with SSE, causing XMM reservation to increase stack spills 8-fold.
- Per-kernel cost per added spill varies ~30x, from about 0%/spill (SipHash) to 2.2%/spill (FIR filter).
- Out-of-order execution hides spill latency, making spills cheap; historical x86-32 would have had higher and more uniform cost.
- The experiment used gcc 15.2.0 -O2 on an Intel Xeon E-2236; code is available on GitHub.
A fuzzer for the Toy Optimizer
2 months ago
- Author builds a fuzzer to automatically find correctness bugs in a toy compiler optimizer.
- Random programs are generated using loads, stores, and escapes on three arguments.
- Verification invariant: optimized and unoptimized programs must produce identical heaps under non-aliasing and full-aliasing conditions.
- The fuzzer quickly catches a bug when a key optimization (removing aliasing writes) is disabled.
- Limitations include no handling of partial aliasing and the need for a more sophisticated equivalence definition for allocation removal.
Value numbering
2 months ago
- SSA assigns each expression a unique name, enabling clearer distinction between textually similar but different computations.
- Value numbering identifies instructions that always produce the same value, allowing reuse (e.g., via hashing instructions).
- Local value numbering (LVN) works on linear block sequences, using a hash map to find and replace duplicate pure operations.
- Global value numbering (GVN) extends across blocks, leveraging dominator relationships to share value maps for expression deduplication.
- Impure operations (like field loads) require additional bookkeeping, such as load-store forwarding or type information tracking.
- Advanced techniques include unified hash tables, value partitioning, scoped hash maps, and handling phi-functions in loops.
Partial static single information form
2 months ago
- SSI extends SSA by discovering facts from the program and reifying them as path-dependent/flow-sensitive IR nodes, such as refining types based on conditionals.
- Partial SSI can be built during SSA construction with low complexity, leveraging conditionals and branches in the source bytecode.
- Guards introduced by JIT optimization can be de-duplicated via GVN, but canonicalization is needed to rewrite operands to use the latest refined values.
- The approach offers a trade-off between compile-time and run-time, and does not insert new phi nodes or re-merge values in some implementations.
- Examples include implementations in ZJIT, TruffleRuby, Cinder, Luau, and Android ART, each using different strategies for type refinement.
constrained languages are easier to optimize
2 months ago
- Raw pointer languages (C, C++, unsafe Rust) are hard to optimize due to alias analysis and memory management.
- Constrained languages (Haskell, Futhark, SQL) give compilers more optimization freedom through additional structure like referential transparency or declarative semantics.
- Examples: Haskell stream fusion reduces nested loops to constant space; Futhark outperforms C on GPU tasks; SQL performance improves over decades via query planning.
- Performance hotspots can be addressed by using structured languages for those sections, reserving raw pointers for rare cases.
- Raw pointers are needed for specific optimizations (e.g., NaN boxing, XOR linked lists) but should be opt-in.
- Rust improves on C with unsafe opt-in, iterator fusion, and bounds check removal.
- The goal should be easy interop between languages, enabling use of the best tool for each task via inline DSLs or seamless FFI.
Matt Godbolt's blog
2 months ago
- The debate over the best loop style in C++ led to the creation of Compiler Explorer in 2011.
- Different loop styles like for(), while(), range-for, and STL algorithms often compile to identical optimized assembly code.
- Range-for and pointer-based loops produce the same efficient code, avoiding unnecessary size calculations.
- Using standard algorithms or range-for is recommended for clarity, as compilers canonicalize them into optimal underlying patterns.
- The ordinal-based loop style may incur minor inefficiencies, but modern compilers generally optimize well.
Matt Godbolt's blog
2 months ago
- The population count operation counts the number of one bits in a binary value and is useful in areas like data compression, cryptography, and chess.
- A common method to count bits is looping 64 times, but a more efficient approach uses a trick to clear the lowest set bit by ANDing the value with (value - 1).
- Modern compilers like GCC and Clang can optimize a population count loop into a single 'popcnt' instruction when using appropriate architecture flags like -march=westmere.
- The compiler's loop deletion pass recognizes the functional equivalence of the loop and replaces it with a single instruction, though using std::popcount in C++ is recommended for clarity.
- Some CPU architectures may have performance quirks, such as a false dependency bug in Sandy Bridge requiring an extra 'xor eax, eax' before 'popcnt'.
Matt Godbolt's blog
2 months ago
- Compilers optimize loops by duplicating them for different conditions, known as 'loop unswitching'.
- At lower optimization levels (e.g., -O2), compilers may use conditional instructions like multiply-and-add to avoid branches inside loops.
- Loop unswitching moves invariant checks outside loops and creates specialized loop copies, trading code size for performance.
- Higher optimization levels enable loop unswitching, eliminating unnecessary operations (e.g., multiplication) when conditions remain constant.
- Trust compiler optimization decisions but understand trade-offs, verified via tools like Compiler Explorer.
Matt Godbolt's blog
2 months ago
- The compiler optimizes loops by moving invariant code (like size calculations) outside the loop, known as Loop-Invariant Code Motion (LICM).
- In a string_view counting example, clang moves the get_range() call outside the loop and uses setle/setge to avoid branches.
- Trust the compiler, but verify its output using tools like Compiler Explorer, as gcc may fail to perform LICM on certain struct types.
Matt Godbolt's blog
2 months ago
- Loop-invariant code motion (LICM) can pull computations like `strlen` out of loops for efficient assembly.
- Adding a global variable (e.g., `num_compares`) that is modified inside the loop can cause LICM to fail.
- The failure is due to aliasing: `char*` is allowed to alias any type, so the compiler cannot prove the string is unchanged when the global is modified.
- Despite strict aliasing rules, `char*` (and `unsigned char*`, `std::byte*`) have a special exception allowing them to alias anything.
- In practice, GCC, Clang, and MSVC were all unable to perform LICM on the modified code.
- The next post will explore more aliasing issues and how to help the compiler optimize such code.
Matt Godbolt's blog
2 months ago
- Aliasing prevents compiler optimizations, and understanding why is crucial.
- A counter class example shows that with `int` types, the compiler updates the member variable each loop iteration due to potential aliasing, while with `long` types, it caches the accumulator in a register because strict aliasing rules prevent overlap.
- C++ strict aliasing allows the compiler to assume non-overlapping memory for different types, enabling optimizations like register caching and vectorization.
- Fixes include using a local variable for accumulation (e.g., `std::accumulate`) or the non-standard `__restrict` keyword.
- Aliasing is a common pitfall in C++, especially with base types; detecting unexpected memory writes in hot loops can reveal it.
Matt Godbolt's blog
2 months ago
- The calling convention is part of the ABI, varying by architecture and OS, with the System V ABI for x86 Linux discussed as the most sane.
- On x86 Linux, the first two parameters (including structures) are passed in registers rdi and rsi, often allowing efficient passing of small structures.
- For structures with multiple integer types (e.g., int), the compiler may pack them into a single register with extra instructions, while for many arguments (over 6), stack spilling occurs.
- Changing argument types (e.g., to char) can avoid stack spilling if the entire structure fits in one register, though compilers may use different optimization tricks.
- Understanding the ABI helps in designing types like std::string_view and std::optional to pass by value efficiently, using registers to avoid stack overhead.
Matt Godbolt's blog
2 months ago
- Inlining is a fundamental compiler optimization that copies function bodies into call sites, enabling further optimizations like constant propagation and dead code elimination.
- Inlining can reduce call overhead but its primary benefit is allowing the compiler to specialize code at the inline site, such as simplifying branches based on known constants.
- Drawbacks of inlining include increased code size, which can strain instruction caches, and complex heuristic-driven decisions that vary between compilers.
- Inlining requires visibility of the function definition; declaring functions without bodies prevents inlining, though link-time optimization (LTO) can help across translation units.
- The effectiveness of inlining depends on context, with nuanced trade-offs for branch prediction and performance that compilers must guess at without runtime information.
Matt Godbolt's blog
2 months ago
- SIMD allows CPUs to process multiple data points with a single instruction, improving performance for array-heavy computations.
- Compilers can automatically vectorize loops with flags like -O3 and -march=skylake, but require proper data layout (e.g., arrays of integers).
- Conditional updates (e.g., max) can be vectorized using mask moves or by rewriting as unconditional operations that map to SIMD instructions like vpmaxsd.
- Compilers add runtime checks for array overlap to ensure vectorization correctness, often generating a fallback scalar loop.
Matt Godbolt's blog
2 months ago
- Compilers optimize string comparisons against compile-time constants using overlapping memory reads and bitwise XOR operations.
- For constant strings of varying lengths, compilers inline comparisons and use efficient techniques like checking length first, then performing byte or word-level comparisons.
- The permutation for comparing a 7-character string uses two overlapping 32-bit reads and XOR operations to avoid individual byte checks, leveraging that XOR of identical values yields zero.
- Modern compilers (e.g., Clang) automatically apply such optimizations (e.g., branchless conditionals, unaligned reads) from simple code like `sv == "ABCDEFG"sv`, allowing developers to focus on clarity.
- Differences exist across compilers: for instance, GCC may produce more straightforward but less optimized code compared to Clang for similar string comparisons.
Matt Godbolt's blog
2 months ago
- GCC optimizes a simple sum loop by processing two numbers at a time using LEA instructions, achieving O(n) but with fewer iterations.
- Clang goes further by recognizing the sum of integers formula and replacing the loop with an O(1) closed-form expression: v(v-1)/2.
- The author notes decades of compiler development still produce surprising and elegant optimizations, highlighting the sophistication of modern compilers.
When Compilers Disagree About UTF‑8
2 months ago
- An open-source C++ library for UTF-8 handling was initially created without heavy optimization.
- Optimization focused on ASCII shortcut: ASCII characters (range U+0000–U+007F) always pass UTF-8 validity checks, allowing early return.
- A simple ASCII fast-path tripled Clang's performance on pure ASCII text, with 34% improvement on mixed text.
- GCC showed no change on pure ASCII and 3-4% worse performance on mixed text for the same optimization.
- Analysis revealed Clang did not eliminate post-decoding checks, while GCC already optimized them away.
- A refined approach (inline validation in decode functions) improved performance on both compilers: preserved Clang gains, added 15-20% improvement on GCC mixed text.
- Lesson: compiler behavior varies; careful optimization can yield significant gains.
Dense Arena Interning: The Engine of Compiler Performance
2 months ago
- Compiler performance is improved by reducing repeated string and structure checks using Dense Arena Interning.
- Dense Arena Interning converts strings and structures into dense integers during lexing or type construction, enabling O(1) lookups and comparisons in later compiler phases.
- Arena allocators provide stable memory, allowing pointer-based comparisons and efficient memory management without reallocation.
- Dense IDs enable flat array symbol tables, improving cache locality and turning symbol resolution into O(1) array indexing.
- Interning canonicalizes complex types, allowing shallow pointer comparisons instead of deep structural checks, further speeding up type and symbol comparisons.
Your code is fast – if you're lucky
3 months ago
- Modern compilers, particularly Clang, optimize loops using branch-free instructions when using certain programming styles.
- A Quicksort implementation with sorting networks and loop unrolling was initially slower than C++ std::sort.
- Rewriting a beginner-friendly if-statement into a compact C idiom (using post-increment operators) significantly improved performance.
- The 'cosmetic' change triggered Clang to replace branches with csel (conditional select) instructions, making the code branchless.
- On x86, Clang similarly generates branchless code using cmov, while GCC consistently produces slower branch-based versions.
- The optimized Quicksort became over 6 times faster than the original and nearly twice as fast as std::sort.
The mask that compiles to nothing: how HotSpots JIT learned to reason about bits
3 months ago
- HotSpot's C2 compiler tracks "known bits" alongside ranges to optimize bitwise operations.
- The optimization eliminates redundant bitwise ANDs, like removing (x << 2) & -4, by proving bits are unchanged.
- The system uses two 32-bit masks per integer: zeros and ones to indicate definite bit states.
- Range and known bits mutually refine each other through a process called canonicalization.
- Rules for bit propagation are defined for operations like AND, OR, and shift, enabling precise analysis.
- The feature was implemented in JDK 26 and improved in JDK 27, with test methods ensuring correctness.

firstprev0next

compiler optimization

Register deprivation: spills and runtime under forced register scarcity

A fuzzer for the Toy Optimizer

Value numbering

Partial static single information form

constrained languages are easier to optimize

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

Matt Godbolt's blog

When Compilers Disagree About UTF‑8

Dense Arena Interning: The Engine of Compiler Performance

Your code is fast – if you're lucky

The mask that compiles to nothing: how HotSpots JIT learned to reason about bits