Compile-Time Improvements in LLVM 23

aengelke.net

Compile-Time Improvements in LLVM 23 2026-08-21

LLVM 23 has seen substantial compile-time improvements of -6.75% (sqlite3: -10.53%) in -O3 builds. This article describes the major sources of these improvements.

All performance numbers refer to the the stage2-O3 configuration on LLVM compile-time-tracker unless noted otherwise.

ADT

Hash maps/sets, which LLVM uses extensively, have seen three substantial improvements (also described here): first, moving away from quadratically probed hash tables to linear probing and an improved deletion (DenseMap (-1.27%), SmallPtrSet (-0.24%), StringMap (-0.10%)), removing the need for tombstone keys. Second, occupancy for DenseMap is now stored in a compact bit array (+0.13%) instead of using empty keys, which avoid the need for having any in-band reserved values. While worse in terms of instructions in Clang-built Clang, this improves in cycles and reduces branch and cache misses. As a side-effect, removing empty and tombstone keys also made hash table look ups more efficient (-0.04%), as some equality functions no longer need to explicitly check for these. Third, moving from CityHash and a weak pointer hash function to xxh3 (-0.18%) already improved performance with the old hash table and was a prerequisite for the previous changes.

In SmallVector, the trivially-copyable push_back grow path was moved out-of-line and changed to permit tail call optimization (also described here) (-0.50%), resulting in shorter live ranges for registers in some cases, fewer instructions on the fast path, more shrink wrapping, and in smaller code and therefore more inlining.

BumpAllocator saw some clean up (-0.17%, +0.06%). Compile-time numbers were a bit mixed due to inlining heuristics; the smaller allocation functions shifted inlining boundaries resulting in different "even-odd" inlining. (E.g. for A -> B -> C -> D, if D isn't inlined, B will be inlined into C; if D becomes smaller it will be inlined into C, but then C will no longer be inlined into B, but B will be inlined into A -- but this might miss important simplifications possible when inlining C into B.)

post_order traversal was rewritten (-0.18%) to no longer stores the traversal state in the iterator itself, while still not ideal, this made iterator moves cheaper and enabled inlining in some of the iterator functions.

Dominator Tree

The dominator tree representation changed from storing a vector of children to the child-sibling representation (-0.13%), avoiding allocations. Care is required to not change the order of the children, as several passes depend on that and produce substantially different output of the children order is reversed. Using a bump allocator (-0.50%) for nodes noticably reduced the number of calls to malloc()/free(), considering the amount of dominator trees that are constructed during compilation.

The dominator tree construction saw a few improvements, most notably not materializing successors (-0.21%) and storing predecessors as an edge list (-0.11%) provided the largest single improvements.

While the construction algorithm is quite fast even on larger programs (despite being O(n^2) in the worst case), the dominator tree representation remains rather inefficient, largely to maintain compatibility with existing traversal patterns and to support updating. In fact, a substantial part of the construction time is purely spent on materializing the result into the DominatorTreeBase data structures.

IR Data Structures

Implementing successors() as iterators over a range of Uses (-0.21%) addresses a long-standing inefficiency: previously, each use access was an out-of-line function call that repeatedly dispatched over the terminator instruction type. Doing this required some preparatory work to ensure that successors are stored contiguously in all terminators (SwitchInst needed changes, the case values are no longer Uses but plain ConstantInt*) and the larger effort of splitting the Br opcode into separate UncondBr and CondBr opcodes (-0.08%) to avoid bitfield accesses to distinguish these. Nonetheless, successors() remains in the top 15 of the hottest functions (self time), primarily due to the cache miss when accessing the terminator opcode and the branch miss at the switch on the terminator type.

Requiring well-formed IR in BasicBlock::getTerminator() (-0.07%) and successors() (-0.12%) and requiring non-null blocks in the dominator tree (-0.06%) also provided improvements -- even cheap checks are somewhat expensive if they're done often. In a similar vein, predecessor iteration got faster: LLVM stores predecessors of basic blocks through their use list, terminators use the successor blocks. Previously, the other type of user of basic blocks was BlockAddress, which occurred quite rarely (only needed for computed goto in C), so the predecessor iterator had to check every block use whether it is a terminator. Changing BlockAddress to no longer use...