Compile-Time Improvements in LLVM 23
Compile-Time Improvements in LLVM 23
LLVM 23 的编译时间优化
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 stage2-O3 configuration on LLVM compile-time-tracker unless noted otherwise.
LLVM 23 在 -O3 构建中实现了显著的编译时间优化，整体提升了 -6.75%（sqlite3 提升了 -10.53%）。本文介绍了这些优化的主要来源。除非另有说明，所有性能数据均参考 LLVM compile-time-tracker 上的 stage2-O3 配置。
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.
LLVM 广泛使用的 ADT 哈希映射/集合（Hash maps/sets）进行了三项重大改进（此处亦有描述）：首先，从二次探测哈希表转向线性探测，并改进了删除机制（DenseMap -1.27%，SmallPtrSet -0.24%，StringMap -0.10%），从而消除了对“墓碑键”（tombstone keys）的需求。其次，DenseMap 的占用情况现在存储在紧凑的位数组中（+0.13%），而不是使用空键，这避免了在数据中预留任何特殊值。虽然在 Clang 构建的 Clang 中，指令数量略有增加，但这改善了周期数，并减少了分支预测失败和缓存缺失。作为副作用，移除空键和墓碑键也提高了哈希表查找的效率（-0.04%），因为某些相等性函数不再需要显式检查这些值。第三，从 CityHash 和弱指针哈希函数迁移到 xxh3（-0.18%），这在旧哈希表上就已经提升了性能，也是实现上述更改的前提条件。
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.)
在 SmallVector 中，可平凡复制（trivially-copyable）的 push_back 增长路径被移至行外（out-of-line），并进行了修改以允许尾调用优化（此处亦有描述）（-0.50%）。这在某些情况下缩短了寄存器的活跃范围，减少了快速路径上的指令，增加了收缩包装（shrink wrapping），并减小了代码体积，从而实现了更多的内联。BumpAllocator 进行了一些清理（-0.17%, +0.06%）。由于内联启发式算法的影响，编译时间数据表现不一；较小的分配函数改变了内联边界，导致了不同的“奇偶”内联结果。（例如，对于 A -> B -> C -> D，如果 D 不被内联，B 将被内联到 C 中；如果 D 变小了，它会被内联到 C 中，但随后 C 将不再被内联到 B 中，而是 B 被内联到 A 中——但这可能会错过将 C 内联到 B 时可能产生的关键简化。）
post_order traversal was rewritten (-0.18%) to no longer store 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.
后序遍历（post_order traversal）被重写（-0.18%），不再将遍历状态存储在迭代器本身中。虽然这仍非理想方案，但它降低了迭代器移动的开销，并使某些迭代器函数能够被内联。
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 if the children order is reversed. Using a bump allocator (-0.50%) for nodes noticeably 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.
支配树（Dominator Tree）：支配树的表示方式从存储子节点向量改为子节点-兄弟节点表示法（-0.13%），从而避免了内存分配。需要注意的是，不能改变子节点的顺序，因为多个编译过程依赖于该顺序，如果子节点顺序颠倒，会产生截然不同的输出。为节点使用 Bump Allocator（-0.50%）显著减少了 malloc()/free() 的调用次数，考虑到编译过程中构建支配树的数量，这非常重要。支配树的构建也进行了一些改进，最显著的是不再具体化（materializing）后继节点（-0.21%），以及将前驱节点存储为边列表（-0.11%），这两项提供了最大的单项性能提升。虽然构建算法即使在大型程序上也非常快（尽管最坏情况下为 O(n^2)），但支配树的表示方式仍然相当低效，这主要是为了保持与现有遍历模式的兼容性并支持更新。事实上，构建时间中有很大一部分纯粹是花在将结果具体化到 DominatorTreeBase 数据结构中。
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.
IR 数据结构：将 successors() 实现为遍历 Use 范围的迭代器（-0.21%）解决了长期存在的低效问题：此前，每次使用访问都是一次行外函数调用，并在终结指令类型上重复进行分发。实现这一点需要一些准备工作，以确保后继节点在所有终结指令中连续存储（SwitchInst 需要更改，case 值不再是 Uses，而是普通的 ConstantInt*），以及将 Br 操作码拆分为独立的 UncondBr 和 CondBr 操作码（-0.08%）这一更大的工作，以避免通过位域访问来区分它们。尽管如此，successors() 仍然处于最热函数（自身耗时）的前 15 名，这主要是由于访问终结指令操作码时的缓存缺失，以及在终结指令类型切换时的分支预测失败。在 BasicBlock::getTerminator()（-0.07%）和 successors()（-0.12%）中要求格式良好的 IR，以及在支配树中要求非空块（-0.06%）也带来了改进——即使是廉价的检查，如果执行频率过高，也会变得相当昂贵。
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.
同样，前驱迭代也变得更快了：LLVM 通过使用列表（use list）存储基本块的前驱节点，而终结指令使用后继块。此前，基本块的另一种用户类型是 BlockAddress，这种情况非常罕见（仅在 C 语言的计算跳转中需要），因此前驱迭代器必须检查每个块的使用情况以判断其是否为终结指令。将 BlockAddress 修改为不再使用基本块（-0.06%）使得移除该检查成为可能。移除基于 icmp+select 的非规范整数最小值/最大值的模式匹配（自几个版本以来，这些已规范化为专用的内部函数）也带来了一些改进（-0.09%），这主要是因为现在内联了更小的模式匹配函数。
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…
相当多的指令附带有元数据，例如用于调试信息或基于类型的别名分析。Debuginfo 对指令有快速路径，但所有其他元数据附件都存储在上下文中，此前存储在一个以 Value 指针为键、映射到附件向量的哈希映射中。将这些附件存储在单个向量中（-0.35%）（在向量条目上形成多个链表），并将附件列表的起始位置存储在指令中，使得元数据查询变得便宜得多。使用 SmallVector 的缺点是所有 TrackingMDNodeRef 在增长时都需要移动，但尝试使用增加额外间接层的数据结构（例如修改后的 PagedVector）产生的结果……