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.

Read More

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.

Read More

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.

Read More

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.

Read More

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).

Read More

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

__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);
}

Read More

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.

1
2
3

#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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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    .Lstore

Read More

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 for std::unordered_map): DenseMapInfo::getEmptyKey() / getTombstoneKey().
  • DenseSet: implemented using DenseMap
  • compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h ports the implementation for sanitizers.
• SmallPtrSet (replacement for std::unordered_set<T *>): hard-coded -1 (empty) and -2 (tombstone).
• StringMap (replacement for std::unordered_map<std::string, V>)
  • StringSet: implemented using StringMap
• 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/-2 reserved — 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.

Read More

With a sufficient number of users of an API, it does not matter what you promise in the contract: all observable behaviors of your system will be depended on by somebody. — Hyrum's Law

In a compiler, the most common form of Hyrum's Law is dependence on unspecified behavior — hash bucket order, the order of equal elements after std::sort, padding offsets. The same framing covers a few cases that are technically undefined behavior (use of an invalidated iterator) or plain incidental properties (ABI struct layout, ELF section offsets).

When the compiler itself harbors such a dependency, the symptom is usually output that varies build-to-build: an unstable sort that lands differently after the standard library changes, a hash map whose iteration order shifts when the hash function does. Occasionally the variation is run-to-run within a single build — DenseMap<void *, X> keys with an ASLR-derived seed reorder buckets each invocation. Either way, reproducible builds, bisection, and bug reports all assume same input → same output, and a stealth Hyrum dependency breaks that.

This post surveys some mechanisms that perturb the contract's blind spots so dependencies cannot quietly form.

Read More

Updated in 2026-05.

Since the LLVM 22 branch was cut, I've landed patches that parallelize more link phases and cut task-runtime overhead. This post compares current main against lld 22.1, mold, and wild.

Headline: a Release+Asserts clang --gc-sections link is 1.34x as fast as lld 22.1; Chromium debug with --gdb-index is 1.09x as fast. mold and wild are still ahead — the last section explains why.

Read More