Posts
四色滑道：从博物馆的益智玩具到一道OI题
Palo Alto Junior Museum and Zoo的室内科学展区(Indoor science exhibits)墙上挂着一块大号的Montessori Slide Puzzle：下方是四条竖直滑槽，每条槽里叠着四颗彩色圆柱珠子；上方的卡片给出目标图案，玩家要通过滑动珠子把下面摆成卡片上的样子。 本文把它抽象成一道OI题，并给出题解和标准程序。
我只拍了两张照片，问了一句「能否根据这个益智玩具设计一道OI算法题？涉及编号时，从 0 开始。提供题解和C++标准程序」。 下面的题面、题解、标程、对拍程序，连同数据范围的取舍，都是Opus 5.5根据照片生成的，这篇文章也是它写的。 它自己从照片里读出了槽、木舌和滑道的结构，写暴力程序对拍，实测连通块大小来确定数据范围，还发现了「底层冻结」这个不变量。我大受震撼。
…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, compares CIR with the IRs it cites as models, Rust's MIR and Swift's SIL, collects what the MLIR 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 .Lstore- ← Prev
- 1 of 30
- Next →