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.
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…
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 *…
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…
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…
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…
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…
The C and C++ standards leave nearly every detail to the implementation. C23 §6.7.3.2: An implementation may allocate any addressable storage unit large enough to hold a bit-field. If enough space remains, a bit-field that immediately follows another bit-field in a structure shall be packed into adjacent bits of the same unit. If insufficient space remains, whether a bit-field that does not fit is…
Most architectures encode direct branch/call instructions with a PC-relative displacement. This post discusses a specific category of branch relocations: those used for direct function calls and tail calls. Some architectures use two ELF relocation types for a call instruction: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 # i386, x86-64 call foo # R_386_PC32, R_X86_64_PC32 call foo@plt # R_386_PLT32,…
For those unfamiliar, lld is the LLVM linker, supporting PE/COFF, ELF, Mach-O, and WebAssembly ports. These object file formats differ significantly, and each port must follow the conventions of the platform's system linker. As a result, the ports share limited code (diagnostics, memory allocation, etc) and have largely separate reviewer groups. With LLVM 22.1 releasing soon, I've added some notes…
Branch instructions on most architectures use PC-relative addressing with a limited range. When the target is too far away, the branch becomes "out of range" and requires special handling. Consider a large binary where main() at address 0x10000 calls foo() at address 0x8010000-over 128MiB away. On AArch64, the bl instruction can only reach ±128MiB, so this call cannot be encoded directly. Without…
I've created pr-shadow with vibe coding, a tool that maintains a shadow branch for GitHub pull requests (PR) that never requires force-pushing. This addresses pain points I described in Reflections on LLVM's switch to GitHub pull requests#Patch evolution .
TODO 一如既往，主要在工具链领域耕耘。但由于工作忙碌在open source社区投入的时间减少了。 Blogging 不包括这篇总结，一共写了18篇文章。 <a href
tl;dr: Weak AVL trees are replacements for AVL trees and red-black trees. The 2014 paper <a href="https://sidsen.azurewebsites.net
周末从旧金山湾南部去Sacramento参观。
On most Linux platforms (except AArch32, which uses .ARM.exidx ), DWARF .eh_frame is required for C++ exception handling and stack unwinding to restore callee-saved registers. While .eh_frame can be used for call trace recording, it is often criticized for its runtime overhead. As an alternative, developers can enable frame pointers, or adopt SFrame, a newer format designed specifically for…
SFrame is a new stack walking format for userspace profiling, inspired by Linux's in-kernel ORC unwind format . While SFrame eliminates some .eh_frame CIE/FDE overhead, it sacrifices functionality (e.g., personality, LSDA, callee-saved registers) and flexibility, and its stack offsets are less compact than .eh_frame 's bytecode-style CFI instructions. In llvm-project executables I've tested on…
LLVM 21.1 have been released. As usual, I maintain lld/ELF and have added some notes to https://github.com/llvm/llvm-project/blob/release/21.x/lld/docs/ReleaseNotes.rst . I've meticulously reviewed nearly all the patches that are not authored by me. I'll delve into some of the key changes.
tl;dr https://gist.github.com/MaskRay/74cdaa83c1f4
Updated in 2026-04. Alignment refers to the practice of placing data or code at memory addresses that are multiples of a specific value, typically a power of 2. This is typically done to meet the requirements of the programming language, ABI, or the underlying hardware. Misaligned memory accesses might be expensive or will cause traps on certain architectures. This blog post explores how alignment…