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.
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.
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.
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 the basic block (-0.06%) allowed to remove this check. Removing the pattern matches for nowadays non-canonical integer minimum/maximum based on icmp+select, which since a few releases are canonicalized to dedicated intrinsics, provided some improvements (-0.09%), primarily due to the smaller pattern match functions that are now inlined.
Quite a lot of instructions have metadata attached, e.g. for debug info or type-based alias analysis. Debuginfo has a fast path for instructions, but all other metadata attachments are stored in the context, previously in a hash map keyed on the Value pointer mapping to a vector of attachments. Storing these attachments in a single vector (-0.35%) (forming multiple linked lists over vector entries) and storing the start of the attachment list in the instruction made metadata queries much cheaper. Using a SmallVector has the disadvantage that all TrackingMDNodeRef need to be moved on growth, but experiments with data structures that added an extra layer of indirection (e.g., a modified PagedVector) yielded worse performance. Metadata remains an expensive mechanism, however, and instructions that likely have metadata (especially related to alias analysis) should probably get this information stored inline at some point. That getting metadata remains expensive can be demonstrated with the change that made InstCombine !annotation metadata accesses lazy (-0.07%). Debuginfo metadata was improved to no longer use TrackingMDNodeRef but plain MDNode pointers (stage2-O3: -0.50%, stage2-O0-g: -1.15%) to refer to debug location; this is possible as debug locations are never replaced. IRBuilder lost the ability to attach arbitrary metadata (-0.04%), saving on an almost-never hit check on every inserted instruction.
Constant::isNullValue was changed to be computed eagerly and storing the bit in SubclassOptionalData (-0.14%), avoiding frequent switches on the type of the constant.
Several hash maps mapping with basic block keys were removed, continuing work I started in 2024 by introducing block numbers. Originally, to share infrastructure with Machine IR, all data analyses using these had to support the case where blocks were renumbered. This proved to be limiting and preventing adoption in e.g. LoopInfo, where renumbering cannot be supported easily. Introducing separate, more stable analysis block numbers in Machine IR unblocked several other uses. Block numbers are now also used by MemoryDependenceAnalysis (-0.14%), BlockFrequencyInfo (-0.15%), LazyValueInfo (-0.02%), LoopInfo (-0.15%), BranchProbabilityInfo (-0.05%), removeUnreachableBlocks() (-0.03%), and post-order traversal (-0.18%). Renumbering blocks after SimplifyCFG (-0.05%) also helps to keep the numbers dense; it might beneficial to do this in a few more places.
A side effect of using block numbers instead of block pointers is that BlockFrequencyInfo and BranchProbabilityInfo no longer need to use expensive ValueHandles to remove basic blocks from their data structures (which was necessary to prevent wrong data if the pointer is reused). ValueHandles continue to be a substantial source of overhead and should probably be removed in the long-term.
GlobalISel, the maybe-eventually replacement instruction selection back-end, has seen a fair amount of improvements, primarily focused on AArch64 -O0, where it is the default. The end-to-end slowdown over FastISel went down from 12.71% to 9.39% (sqlite3: 31.81% to 26.13%). My favorite improvement is dropping the localizer from the -O0 pipeline (stage1-aarch64-O0-g: -1.10%), which previously caused quadratic compile-time in the number of constants per basic block. (This was sadly reverted -- this means that I still have to force-disable GlobalISel when building Disarm and its users like TPDE.) It remains to be seen to which extent GlobalISel can catch up with FastISel.
Other than that, there were only a few improvements (-0.21%, -0.10%, -0.23%) on the back-ends.
Reducing the minimal density for generating static lookup tables from switches in SimplifyCFG from 40% to 10% improved Clang performance for C++ programs (stage2-O0-g: -0.17%) -- the density of clang::Decl::castToDeclContext is 38%, which previously resulted in an often-mispredicted branch to compute a constant pointer offset. This is one of the rare cases where a compile-time improvement comes from an optimization improvement.
Not recomputing the current location metadata improved builds with debuginfo (stage2-O0-g -3.53%), but the improvement in cycles was only half of that (both in c-t-t and in own measurements).
Many distributions build LLVM as a shared library, as it substantially reduces the package size and build time. However, this has two downsides over a statically linked non-PIE build: first, references to other functions and global objects now require dynamic relocations that must be processed on startup. This particularly affects vtables and data structures containing pointers to strings (e.g. const char * or StringRef). (NB: it's not the relocations themselves that are so expensive, it's largely the page faults they cause.) Second, LLVM's option parsing (llvm::cl) is based on every option initializing and registering itself in their own global constructor. This is especially costly in terms of page faults: the code page of the ctor function of ~each object faults, the access of option string faults, the access of the option struct (>=184B each) in .bss faults, and growing the DenseMap several times causes faults.
While porting away from llvm::cl is a bigger effort (it requires writing a new option parsing framework, probably based on TableGen, hopefully happens for LLVM 24), I did work on reducing the number of page faults on startup by shrinking .data.rel.ro/.data and reducing relocations. Notable improvements came from adding a new compact enum table that stores strings attached to records via record-relative offsets, rewriting unique_function, removing vtables from formatv and format, using StringTable for FeatureKV, SubTypeKV and searchable tables, and merging TargetRegClass into MCRegClass.
I summarized the dylib-related startup costs as of LLVM 23 shortly before branching here.
Not strictly a compile-time improvement, but related: as a big change in the way LLVM and it's in-tree dependants are built, LLVM now uses precompiled headers for almost all compilation units, improving the build times of LLVM/Clang by ~45%. Compiling LLVM was previously very front-end intensive, spending there >80% even in release builds, repeatedly parsing C++ standard library and LLVM Support. With PCH the front-end time is down to ~55%. There are five PCHs now (LLVM Support (-14.73%), LLVM Core (-12.70%), LLVM CodeGen (-6.33%) (more beneficial in all-target builds), clangAST (-13.85%), and some time later clangCodeGen (-8.12%)). The PCH build is on by default when building with MSVC or Clang; GCC is disabled as the additional template instantiations, which GCC, unlike Clang, doesn't cache, negate the benefits and GCC's PCH files are quite large.
Thanks to Nikita Popov and Fangrui Song for reviewing most of my changes. Thanks to Nikita Popov for hosting LLVM compile-time-tracker. Most of the compile-time improvements in LLVM 23 were authored by Cullen Rhodes, Fangrui Song, and myself.