Posts
Who pays for Clang
Clang's funders have changed since 2010: Apple and Google, which wrote most of it until the mid-2010s, now write a small share, and GPU and accelerator vendors, Red Hat, and new sponsors of C++ conformance work write more. This post counts commits, pull-request approvals, and the kind of code each employer touches. The method is unscientific: commit counts are a crude proxy for work, and the attribution is my best guess, so read the numbers as rough trends, not an authoritative record. It grew out of ClangIR and the cost of MLIR, which needed it to explain who wanted an MLIR-based Clang.
…ClangIR and the cost of MLIR
ClangIR (CIR) is an MLIR dialect between the AST and LLVM IR, and in October 2026 the clang area team accepted building it by default. CIR is built on MLIR because each step along the way was locally reasonable, and together the steps locked MLIR in. The costs (build time, binary size, MLIR API churn) land largely on Clang contributors who neither chose MLIR nor use CIR.
This post traces how CIR came to depend on MLIR, collects what the dependency costs, and uses an MLIR-free CIR as a thought experiment to separate the costs inherent to MLIR from those that can be reduced.
…Linker I/O tricks and their downsides
mold and wild enable several tricks by default that other linkers don't do. This post looks at three of them:
- overwrite an existing output file in place instead of creating a new file
- fork a child to do the link, so that the parent can exit before the child releases its memory
- ask the kernel for transparent huge pages
Each saves a few percent of wall time in an edit-relink loop. Each also breaks an assumption that build systems, debuggers, and profilers make about a process. I measured what they save and what they break.
Setup: Linux 6.18, i7-14700K (28 threads), ext4 on a SATA SSD, transparent huge pages enabled=always.
GNU ld 2.47, gold 2.47, LLD 23, mold 2.42.1 (TODO: I used the Rust port under development; check against the C++ release), wild at commit 47cc8e8e.
lld 23 ELF changes
LLVM 23.1 has been released. As usual, I maintain lld/ELF and as volunteer work have added some notes to https://github.com/llvm/llvm-project/blob/release/23.x/lld/docs/ReleaseNotes.rst.
Like last time, I used Claude Code to summarize git log llvmorg-23-init..origin/release/23.x -- lld/ELF, excluding changes cherry-picked into 22.x (git rev-list llvmorg-23-init..llvmorg-22.1.8 -- lld), and then edited the draft.
This was a busy cycle: 141 commits landed in lld/ELF between the branch point (2026-01-13) and 23.1.0-rc1 (2026-07-16), compared with 72 in the 22 cycle. Much of the increase is performance work, which I described in Recent lld/ELF performance improvements. lld 23 is the first release that ships all of it.
…Block frequency
Estimating branch probabilities says how one branch splits.
BlockFrequencyInfo turns those local numbers into per-block frequencies, which nearly every profitability decision in LLVM ends up reading.
The core is a linear-time propagation over loop-packaged regions. Where no such structure exists — irreducible control flow — the accuracy goes with it.
…Estimating branch probabilities
LLVM's BranchProbabilityInfo assigns every multi-successor terminator a probability distribution over its successors.
This post describes the estimation used when no profile is available and reimplements it as a standalone program.
Irreducible loops
The dominator tree lets us identify natural loops: a back edge T->H whose head H dominates its tail T defines a loop with the single entry H.
This works only for reducible control flow graphs.
Optimized machine code and decompiler output routinely contain irreducible loops, which have more than one entry and thus no dominating header, so the dominator-based method cannot see them.
This post builds a loop-nesting forest for an arbitrary CFG with the single-pass depth-first search of 韦韬、毛剑、邹维、陈宇(Tao Wei, Jian Mao, Wei Zou & Yu Chen) A New Algorithm for Identifying Loops in Decompilation, SAS 2007 (The 14th International Static Analysis Symposium).
…Optimizing LLVM's bump allocator
BumpPtrAllocator is LLVM's bump allocator (arena allocator): each allocation bumps a pointer within a slab, and everything is freed at once when the allocator dies.
It backs Clang's ASTContext, lld's make<T> object pools, TableGen records, and many other arenas.
Here is the fast path before three recent changes:
__attribute__((returns_nonnull)) void *Allocate(size_t Size, Align Alignment) {
BytesAllocated += Size; // (3) accounting RMW
uintptr_t AlignedPtr = alignAddr(CurPtr, Alignment); // (1) always realign
size_t SizeToAllocate = Size;
#if LLVM_ADDRESS_SANITIZER_BUILD
SizeToAllocate += RedZoneSize;
#endif
uintptr_t AllocEndPtr = AlignedPtr + SizeToAllocate;
if (LLVM_LIKELY(AllocEndPtr <= uintptr_t(End)
&& CurPtr != nullptr)) { // (2) bound + null check
CurPtr = reinterpret_cast<char *>(AllocEndPtr);
...
return reinterpret_cast<char *>(AlignedPtr);
}
return AllocateSlow(Size, SizeToAllocate, Alignment);
}A deep dive into SmallVector::push_back
tl;dr This blog post describes a recent SmallVector::push_back optimization for approximately trivially copyable element types.
SmallVector is LLVM's most-used container, and push_back its hot operation.
For the trivially-copyable specialization the fast path should be fast.
#include <llvm/ADT/SmallVector.h>
void f(llvm::SmallVectorImpl<int> &v, int x) { v.push_back(x); }clang -S --target=x86_64 -O2 -DNDEBUG a.cc generates:
push rbp # callee-saved spills + a stack realignment,
push rbx # all on the fast path
push rax
mov eax, [rdi + 8] # size
cmp eax, [rdi + 12] # vs capacity
jae .Lgrow
.Lstore: # reached from the fast path AND from .Lgrow
mov rcx, [rdi]
mov [rcx + rax*4], esi
inc dword ptr [rdi + 8]
add rsp, 8
pop rbx
pop rbp
ret
.Lgrow:
mov rbx, rdi # keep `this`/`x` alive across the call
mov ebp, esi
call SmallVectorBase<unsigned>::grow_pod
...
jmp .LstoreRecent LLVM hash table improvements
LLVM has several hash tables. They used quadratic probing with in-band sentinel keys (empty, tombstone); recent work has been replacing that with linear probing with tombstone key removed.
DenseMap(replacement forstd::unordered_map):DenseMapInfo::getEmptyKey()/getTombstoneKey().DenseSet: implemented usingDenseMapcompiler-rt/lib/sanitizer_common/sanitizer_dense_map.hports the implementation for sanitizers.
SmallPtrSet(replacement forstd::unordered_set<T *>): hard-coded-1(empty) and-2(tombstone).StringMap(replacement forstd::unordered_map<std::string, V>)StringSet: implemented usingStringMap
FoldingSet(uniquing/hash-consing container, not a general map)
For the open-addressed DenseMap and SmallPtrSet, pointers, references, and iterators are invalidated by insert.
StringMap is different: each entry lives in a heap-allocated StringMapEntry<V> node, so entry pointers survive grow.
std::unordered_map, being node-based, keeps surviving-element pointers valid across both insert and erase and only invalidates the erased element's own iterator.
LLVM code rarely needs that stronger contract — callers do not hold long-lived references into the container across mutation — and that gap is what gives pass to relocating erase and bit-array occupancy.
Recently,
- Tombstones have been removed from DenseMap and SmallPtrSet.
erase()also invalidates pointers. - DenseMap has also retired its empty-key sentinel, leading to significant performance improvements.
DenseMap with integer keys (
int/unsigned/size_t) had-1/-2reserved — a footgun, now fixed. - StringMap got Algorithm R deletion too. Its entries are separately heap-allocated, so erase keeps entry pointers valid but invalidates iterators; erase-while-iterating moved to
remove_if. - FoldingSet dropped chaining for linear probing plus Algorithm R; the intrusive next-in-bucket pointer became a cached 32-bit hash.
- ← Prev
- 1 of 30
- Next →