Lesson 10.3 — Building IR: IRBuilder, insertion points, folders and inserters¶

Techniques: direct construction (BinaryOperator::Create with an InsertPosition), insertion points (SetInsertPoint, iterator-based insertion and the debug-record head bit), folders (ConstantFolder, NoFolder, InstSimplifyFolder, TargetFolder), inserters (IRBuilderDefaultInserter, IRBuilderCallbackInserter, custom inserters), builder state (fast-math flags, debug locations, constrained FP, guards) · Pebble uses: IRBuilder<> in its code generator (Ch 11) and in every pass that creates code · Lab: Lab 10.1 · Prerequisites: Lessons 10.1, 10.2 · Time: 3 hours

To build the running example you could call five constructors, each with the right operand types and a position to insert at. Or you could write:

IRBuilder<> B(BasicBlock::Create(Ctx, "entry", F));
Value *A = B.CreateAdd(X, Y, "a");
Value *Bv = B.CreateMul(A, A, "b");
Value *C = B.CreateSub(Bv, A, "c");
B.CreateRet(B.CreateXor(X, C, "d"));

The builder remembers where to insert, so each call appends to entry. It also decides whether to create an instruction at all: B.CreateAdd(B.getInt32(6), B.getInt32(7)) creates nothing and returns the constant 13. And it carries state (debug location, fast-math flags) that is stamped onto every instruction it creates. This lesson makes the three mechanisms precise: position, folding and state.

1. Problem and motivation¶

Front ends and passes emit instructions all the time, and every emission has to answer the same questions:

which block, and before which instruction (and, since LLVM 19, before or after the debug records attached there);
should an operation on constants be computed now or emitted;
which flags and which source location go on the new instruction.

Getting any of these wrong gives invalid IR (the verifier catches it), wrong debug info (nobody catches it), or IR that later passes must clean up [LLVM-IRB, KAL].

Direct construction¶

Every instruction class has static Create functions that take operands and an InsertPosition (a block iterator, a block end, or nothing). This is the lowest level: no folding and no state. It is what the builder itself calls, and what passes use when they need exact control, such as the rewrite in Lab 10.2 [LLVM-Instr].

Insertion points¶

A builder holds a current block and an iterator in it, and new instructions go before the iterator. Since the move from debug-info intrinsics to debug records [LLVM-DbgRecords], an iterator carries one more bit, the head bit. It decides whether an instruction inserted at a position with attached #dbg_value records goes before or after them. That is why LLVM 23 deprecates the InsertPosition(Instruction *) constructor and getFirstNonPHI(). (IRBuilder::SetInsertPoint(Instruction *) still exists; it behaves like the instruction's own iterator, with the head bit clear.)

Folders¶

A folder is the builder's peephole: before creating op a, b it asks the folder whether the result is already known. Three folders are provided:

ConstantFolder (the default) folds operations whose operands are all constants;
NoFolder never folds, which is useful in tests and when you need the literal instruction;
InstSimplifyFolder runs InstSimplify, so x + 0 returns x and x - x returns 0.

TargetFolder is the data-layout-aware variant that Clang uses [LLVM-Folders].

Inserters¶

The inserter is the hook that actually places a created instruction (InsertHelper). Clang replaces it to attach its own bookkeeping to every emitted instruction (CGBuilderInserter), and IRBuilderCallbackInserter lets a pass count or post-process what it creates [LLVM-IRB, CLANG-CGBuilder].

Builder state¶

Floating-point code needs fast-math flags and sometimes strict FP semantics, and everything needs a source location. The builder holds these as state (setFastMathFlags, SetCurrentDebugLocation, setIsFPConstrained) and applies them to each instruction it creates. RAII guards (InsertPointGuard, FastMathFlagGuard) restore them [LLVM-IRB].

2. Definitions and algorithms¶

Definition 10.3.1 (Insertion point)

An insertion point is a pair $(B, p)$ of a block and a position $p \in \mathrm{insts}(B) \cup \{\mathrm{end}(B)\}$, together with a head bit $\eta \in \{0, 1\}$. Inserting an instruction $I$ at $(B, p, \eta)$ links $I$ immediately before $p$ (Algorithm 10.1.7 Insert). If $p$ carries debug records $R_p$ (records that describe variables just before $p$), then:

$\eta = 1$ places $I$ before $R_p$;
$\eta = 0$ places $I$ after $R_p$ (the records move onto $I$).

BasicBlock::begin(), getFirstNonPHIIt() and getFirstInsertionPt() return iterators with $\eta = 1$. Instruction::getIterator() returns $\eta = 0$. A null insertion point means "create but do not insert".

Definition 10.3.2 (Folder)

A folder is a partial function $\phi(\mathit{op}, a_1, \dots, a_k)$ that either returns an existing value $v$ (a constant, an argument, or an already-built instruction) or is undefined ($\bot$). It is sound if $\phi(\mathit{op}, \vec{a}) = v$ implies that $v$ refines the instruction $\mathit{op}\ \vec{a}$: for every assignment of the free values, whenever op a⃗ is not poison, $v$ has the same value (Ch 9, refinement, Ch 13). The provided folders satisfy:

$\mathrm{dom}(\phi_{\mathrm{No}}) = \emptyset$;
$\mathrm{dom}(\phi_{\mathrm{Const}}) \subseteq \{\,(\mathit{op}, \vec{a}) \mid \text{every } a_i \text{ is a constant}\,\}$: the all-constant inputs that constant folding evaluates, or that LLVM 23 can still keep as a constant expression (add, sub, xor). The rest stay instructions: mul i64 ptrtoint (ptr @g to i64), 2 is not folded, because mul constant expressions no longer exist;
$\phi_{\mathrm{Simplify}} = $ simplifyBinOp etc., defined on all-constant inputs and on the identities InstSimplify proves (x+0, x-x, x&x, …).

Algorithm 10.3.3 (IRBuilder create)

Input: builder state $\sigma$ (insertion point, folder $\phi$, inserter $\iota$, debug location $\ell$, fast-math flags $\mathit{fmf}$, …); an opcode and operands.
Output: a value $v$ equal to (a refinement of) op a⃗.
Precondition: operand types match the opcode; every operand dominates the insertion point (or is a constant or argument).
Postcondition: either (folded) $v = \phi(\mathit{op}, \vec{a})$ and nothing was inserted, or (created) $v$ is a new instruction inserted at the insertion point, named, with debug location $\ell$ and, for FP operations, flags $\mathit{fmf}$. The inserter ran exactly once for it.
Invariant: the builder's state is unchanged by the call.

function Create(σ, op, a⃗, name):
    if σ.constrainedFP and op has a constrained form:     # checked first: never folded
        I ← call of the constrained intrinsic with a⃗, σ.rounding, σ.except
    else:
        v ← σ.folder.Fold(op, a⃗)             # e.g. FoldNoWrapBinOp, FoldBinOpFMF
        if v ≠ ⊥:
            return v                         # no instruction, no inserter call
        I ← new Instruction(op, a⃗)            # direct construction, unlinked
    if op is floating point: I.setFastMathFlags(σ.fmf)
    σ.inserter.InsertHelper(I, name, σ.insertPt)   # links I before insertPt, sets name
    I.setDebugLoc(σ.debugLoc)
    return I

In llvm/include/llvm/IR/IRBuilder.h: CreateAdd calls Folder.FoldNoWrapBinOp and then CreateInsertNUWNSWBinOp, and Insert calls Inserter.InsertHelper and then SetInstDebugLocation [LLVM-IRB]. CreateFAddFMF tests IsFPConstrained before asking the folder and then calls CreateConstrainedFPBinOp, which builds the intrinsic call with CreateIntrinsicWithoutFolding (llvm/lib/IR/IRBuilder.cpp): in constrained mode even CreateFAdd(1.0, 2.0) emits a call, because folding would lose the exception behavior.

Direct construction¶

Algorithm 10.3.4 (Create an instruction at a position)

Input: an opcode, operands, a name, an InsertPosition $q$ (an iterator, a block to append to, or null).
Output: a new instruction $I$.
Precondition: as for Algorithm 10.3.3.
Postcondition: $I$'s operands are set in order (Algorithm 10.2.3), and $I$ is linked before $q$ (or at the end of the block, or not at all if $q$ is null).
Invariant: nothing but $I$ and its operands' use lists changes.

function CreateAt(op, a⃗, name, q):
    I ← allocate with co-allocated operands (Definition 10.2.5)
    for i in 0 .. k−1: Set(ops(I)[i], a_i)
    if q is a block B: InsertBefore(I, end(B))
    else if q is an iterator: InsertBefore(I, q)    # head bit as in Definition 10.3.1
    SetName(I, name)
    return I

Direct construction, and the deprecated Instruction * position

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 direct.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o direct 2>&1 | head -2 && ./direct

Output (complete):

direct.cpp:19:63: warning: 'InsertPosition' is deprecated: Use BasicBlock::iterators for insertion instead [-Wdeprecated-declarations]
   19 |   BinaryOperator::Create(Instruction::Sub, X, Y, "old_style", Ret);
define i32 @f(i32 %0, i32 %1) {
entry:
  %sum = add i32 %0, %1
  %sq = mul i32 %0, %0
  %old_style = sub i32 %0, %1
  ret i32 %sum
}

What to notice: Create(…, BB->end()) appends, and Create(…, Ret->getIterator()) inserts before ret (Algorithm 10.3.4). Passing the Instruction * still works but is deprecated in LLVM 23: it cannot carry the head bit of Definition 10.3.1. No folding happened: sub i32 %0, %1 is created even though a builder would have produced the same thing. Direct construction never folds.

Insertion points¶

The head bit: before or after the debug records

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 insert.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o insert && ./insert dbg.ll

dbg.ll's entry block is #dbg_value(i32 %x, …) followed by %y = add and ret. The program parses it twice, and inserts a mul once with B.SetInsertPoint(&BB, BB.begin()) (an iterator, $\eta = 1$) and once with B.SetInsertPoint(&BB.front()) (an Instruction *, $\eta = 0$).

Output (complete):

entry:
  %via_iterator = mul i32 %x, %x, !dbg !6
    #dbg_value(i32 %x, !7, !DIExpression(), !6)
  %y = add i32 %x, 1, !dbg !6
  ret i32 %y, !dbg !6

entry:
    #dbg_value(i32 %x, !6, !DIExpression(), !8)
  %via_pointer = mul i32 %x, %x, !dbg !8
  %y = add i32 %x, 1, !dbg !8
  ret i32 %y, !dbg !8

What to notice: the same "insert before %y" lands on different sides of the #dbg_value record, exactly as Definition 10.3.1 says. It matters when the new instruction defines something the record should describe, and for phis: inserting a phi after debug records asserts ("Inserting PHI after debug-records!" in Instruction::insertBefore). Both copies got a !dbg location because SetInsertPoint copies the location of the instruction at the position.

What the verifier says about bad insertion points

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 verify.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o verify && ./verify

The program defines %t in block then, moves the insertion point back to before entry's branch to emit %u = mul %t, %t, and then emits two rets in then.

Output (complete):

Instruction does not dominate all uses!
  %t = add i32 %0, 1
  %u = mul i32 %t, %t
Instruction does not dominate all uses!
  %t = add i32 %0, 1
  %u = mul i32 %t, %t
Terminator found in the middle of a basic block!
label %then
broken=1

What to notice: the builder happily violates the precondition of Algorithm 10.3.3 ("every operand dominates the insertion point"); verifyFunction reports it once per offending use. Inserting after a terminator is the other classic mistake of a forgotten SetInsertPoint. Always run the verifier on what you build (Lab 10.1 R1 requires it).

Folders¶

Three folders, one instruction sequence

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 folders.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o folders && ./folders

Each function issues the same calls: k = 6*7, p = x+0, q = p&p, r = q-q, ret r+k.

Output (complete):

; ModuleID = 'folders'
source_filename = "folders"

define i32 @constant_folder(i32 %0) {
entry:
  %p = add i32 %0, 0
  %q = and i32 %p, %p
  %r = sub i32 %q, %q
  %s = add i32 %r, 42
  ret i32 %s
}

define i32 @no_folder(i32 %0) {
entry:
  %k = mul i32 6, 7
  %p = add i32 %0, 0
  %q = and i32 %p, %p
  %r = sub i32 %q, %q
  %s = add i32 %r, %k
  ret i32 %s
}

define i32 @instsimplify_folder(i32 %0) {
entry:
  ret i32 42
}

What to notice: the domains of Definition 10.3.2. ConstantFolder folded only 6*7, NoFolder folded nothing (even mul i32 6, 7 stays an instruction), and InstSimplifyFolder folded everything. Each fold returned a value that already existed, so the next call's operands were already simplified: x+0 → %0, then %0 & %0 → %0, then %0 - %0 → 0, then 0 + 42 → 42.

Inserters¶

Definition 10.3.5 (Inserter)

An inserter is an object with a method $\iota(I, \mathit{name}, q)$ that links an unlinked instruction $I$ at insertion point $q$ and gives it a name. It may do more, such as attach metadata or record $I$ in a worklist. IRBuilder<Folder, Inserter> calls it for, and only for, every instruction it creates (Algorithm 10.3.3).

A callback inserter counts and tags what the builder creates

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 inserter.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o inserter && ./inserter

Output (complete):

instructions inserted: 4
define double @g(double %0, double %1) {
entry:
  %plain = fadd double %0, %1, !built.by !0
  %reassoc_nnan = fmul reassoc nnan double %plain, %0, !built.by !0
  %plain_again = fsub double %reassoc_nnan, %1, !built.by !0
  ret double %plain_again, !built.by !0
}

What to notice: the program made five builder calls. The last one, CreateFAdd(1.0, 2.0), was folded to a constant and never reached the inserter, so the count is 4 (Theorem 10.3.9). The flags also show builder state and its guard: only the fmul inside the FastMathFlagGuard scope carries reassoc nnan.

Builder state¶

Definition 10.3.6 (Builder state)

The state of an IRBuilderBase is the tuple

\[ \sigma = (B, p, \ell, \mathit{fmf}, \mathit{fpmath}, c, \rho, \epsilon, \mathit{bundles}): \]

the insertion block and position, the current debug location, the default fast-math flags, the default !fpmath tag, whether FP operations are constrained ($c$), the default rounding mode ($\rho$) and exception behavior ($\epsilon$) for constrained operations, and the default operand bundles. Every creation reads $\sigma$ (Algorithm 10.3.3), and only the setters change it. A guard is an RAII object that saves some components of $\sigma$ on construction and restores them on destruction (InsertPointGuard saves $(B, p, \ell)$; FastMathFlagGuard saves $(\mathit{fmf}, \mathit{fpmath}, c, \rho, \epsilon)$).

Debug location, fast-math and constrained FP are builder state

Reproduce (clang 23.1.2, LLVM 23.1.2, Linux x86-64):

cd chapters/10-llvm-cpp-api/examples
clang++-23 $(llvm-config --cxxflags) -std=c++23 state.cpp $(llvm-config --ldflags --libs) \
  -Wl,-rpath,$(llvm-config --libdir) -o state && ./state

Output (complete):

; Function Attrs: strictfp
define double @h(double %0, double %1) #0 !dbg !2 {
entry:
  %a = fadd double %0, %1, !dbg !5
  %b = fmul fast double %a, %0, !dbg !5
  %c = call double @llvm.experimental.constrained.fadd.f64(double %b, double %1, metadata !"round.towardzero", metadata !"fpexcept.strict") #0, !dbg !5
  ret double %c, !dbg !5
}

What to notice: one SetCurrentDebugLocation stamped !dbg !5 on all four instructions, setFastMathFlags(fast) affected only the fmul because the flags were cleared right after, and after setIsFPConstrained(true) the same call CreateFAdd produced a constrained intrinsic with the builder's rounding mode, using the MetadataAsValue operands of Lesson 10.2. (This program mixes both modes only to show the switch. In a real strictfp function every FP operation must be constrained.)

3. Worked example¶

We build the folders.cpp sequence under each folder, starting from an empty entry block of define i32 @f(i32 %0). The insertion point is $(\mathit{entry}, \mathrm{end})$ throughout.

Direct construction¶

With BinaryOperator::Create(…, BB->end()) for each step, nothing folds. The block gets the same five instructions (mul 6, 7, add %0, 0, and, sub, add) as the NoFolder column below, in call order (Algorithm 10.3.4).

Insertion points¶

All calls use the fixed point $(\mathit{entry}, \mathrm{end})$, so by Theorem 10.3.7 the created instructions appear in call order. If after step 3 we set the insertion point to %q's iterator and emit %z = add %0, 1, the block order becomes …, %p, %z, %q, …: %z lands before %q. It may use %p (defined earlier) but not %q (defined later): the verifier box's mistake.

Folders¶

step	call	ConstantFolder	NoFolder	InstSimplifyFolder
1	`k = CreateMul(6, 7)`	42 (folded)	new `%k`	42
2	`p = CreateAdd(%0, 0)`	new `%p`	new `%p`	`%0` ($x + 0 = x$)
3	`q = CreateAnd(p, p)`	new `%q` = `and %p, %p`	new `%q`	`%0` ($x \wedge x = x$; here $p$ is `%0`)
4	`r = CreateSub(q, q)`	new `%r` = `sub %q, %q`	new `%r`	0 ($x - x = 0$)
5	`s = CreateAdd(r, k)`	new `%s` = `add %r, 42`	new `%s` = `add %r, %k`	42 ($0 + 42$, both constants)
6	`CreateRet(s)`	`ret %s`	`ret %s`	`ret i32 42`
	instructions inserted	5	6	1

(The step counts include the ret, which no folder can fold.)

Inserters¶

With the callback inserter of the box around the InstSimplifyFolder builder, the callback runs once, for ret (step 6). With a ConstantFolder builder it runs five times (steps 2–6), and with NoFolder six times.

Builder state¶

The builder state (Definition 10.3.6) during the state.cpp run:

call	$\ell$	$\mathit{fmf}$	$c$, $\rho$	result
`SetCurrentDebugLocation(3:7)`	3:7	none	off	—
`CreateFAdd(x, y)`	3:7	none	off	`fadd`, `!dbg` 3:7
`setFastMathFlags(fast)`; `CreateFMul`	3:7	fast	off	`fmul fast`
`clearFastMathFlags`; `setIsFPConstrained(true)`; rounding ← towardzero	3:7	none	on, towardzero	—
`CreateFAdd(b, y)`	3:7	none	on	`call @llvm.experimental.constrained.fadd.f64(…, "round.towardzero", "fpexcept.strict")`

Try it

./course drill irbuilder-fold --seed 1 --difficulty hard asks for these results under all three folders; --solution shows the table.

4. Invariants and correctness¶

Direct construction¶

Algorithm 10.3.4 is correct by construction: operand Sets keep def-use consistency (Theorem 10.2.11), and the insertion is Algorithm 10.1.7's Insert, so the list stays well formed (Lemma 10.1.13). What it does not guarantee is dominance, because the caller chose the position. Theorem 10.3.7(b) states the condition.

Insertion points¶

Theorem 10.3.7 (Emission order and dominance)

Let a builder make creation calls $c_1, \dots, c_n$ while its insertion point stays $(B, p)$, and let $I_{j_1}, \dots, I_{j_r}$ be the instructions actually created. Then:

(a) they appear in $B$ in the order $I_{j_1}, \dots, I_{j_r}$, immediately before $p$;
(b) if every operand of every call is a constant, an argument, an instruction that dominates $p$, or the result of an earlier call $c_i$, then every created instruction's operands dominate it, so the function keeps the SSA dominance property.

Proof

(a) By induction on $r$. $I_{j_1}$ is inserted immediately before $p$. Suppose $I_{j_1}, \dots, I_{j_{s}}$ are, in order, immediately before $p$. The next creation inserts $I_{j_{s+1}}$ immediately before $p$ (Algorithm 10.1.7), which is after $I_{j_s}$, and by Lemma 10.1.13 the relative order of the others is unchanged. (b) Take an operand $v$ of $I_{j_s}$. Constants and arguments dominate everything. If $v$ dominates $p$, it dominates every instruction immediately before $p$, including $I_{j_s}$: a dominator of $p$ is either in a block strictly dominating $B$, or earlier in $B$ than the instructions inserted just before $p$. If $v$ is the result of an earlier call, it is either a folded value (a constant, an argument, or an operand of that call, which dominates by induction), or an instruction $I_{j_t}$ with $t < s$, which precedes $I_{j_s}$ in $B$ by (a) and therefore dominates it.

When it breaks: changing the insertion point to a block that does not dominate the earlier results (the verifier box), or to a position before an earlier result in the same block.

Folders¶

Proposition 10.3.8 (Folding is safe and never inserts)

If the folder is sound (Definition 10.3.2), then replacing op a⃗ by $\phi(\mathit{op}, \vec{a})$ in Algorithm 10.3.3 preserves the program's semantics (the result refines the instruction), the returned value satisfies Theorem 10.3.7(b), and the inserter is not called for the folded operation. Moreover, on integer operations, $\mathrm{dom}(\phi_{\mathrm{No}}) \subseteq \mathrm{dom}(\phi_{\mathrm{Const}}) \subseteq \mathrm{dom}(\phi_{\mathrm{Simplify}})$.

Proof

Semantics: soundness says $v$ refines op a⃗, and refinement is preserved under substitution into any context (Ch 13). Dominance: the provided folders return a constant, one of the operands $a_i$ (InstSimplify's identities return operands or constants), or, rarely, another value that InstSimplify found among the operands' operands, which dominates them and hence the insertion point, by the same transitivity argument as Theorem 10.2.13. No insertion: in Algorithm 10.3.3 the folded path returns before reaching the inserter. Inclusions: $\emptyset$ is contained in everything. For integer operations on constants, simplifyBinOp calls ConstantFoldBinaryOpOperands (llvm/lib/Analysis/ConstantFolding.cpp), which tries symbolic evaluation first and otherwise does exactly what ConstantFolder::FoldBinOp does (a desirable constant expression, or ConstantFoldBinaryInstruction), so every integer input that ConstantFolder folds, InstSimplifyFolder folds too.

InstSimplifyFolder's fold is a real InstSimplify query. That is why the drill irbuilder-fold can be checked against real LLVM, exhaustively, by tests/ch10/unit/OracleCrossCheckTest.cpp.

Inserters¶

Theorem 10.3.9 (The inserter sees exactly the created instructions)

For any sequence of builder calls, the multiset of instructions passed to $\iota$ equals the set of instructions the builder created, each passed once.

Proof

By Algorithm 10.3.3, the only path to Insert is the non-folded path, which is taken once per created instruction, and Insert calls the inserter once. Folded calls return before Insert. A builder method that creates several instructions creates each one through Insert.

Builder state¶

Proposition 10.3.10 (Guards restore state)

If code between a guard's construction and destruction changes only builder state (and creates instructions), then after the guard's destruction the saved components of $\sigma$ equal their values at construction. This holds on every exit path, including early returns.

Proof

The guard copies the components into its members at construction. Its destructor, which C++ runs on every exit from the enclosing scope, writes them back with the setters. No other code writes those members of the guard.

5. Complexity¶

Variables: $k$ = number of operands, $d$ = InstSimplify's recursion limit (RecursionLimit = 3 in llvm/lib/Analysis/InstructionSimplify.cpp), $s$ = size of the constant expression being folded.

Technique	Time per call (worst)	Time (typical)	Space	Notes
Direct construction	$O(k)$	$O(k)$	one allocation (co-allocated operands)	no folding
Insertion points	$O(1)$ to set; $O(1)$ insert	$O(1)$	the iterator + head bit	`getFirstInsertionPt` scans past phis: $O(\#\text{phis})$
ConstantFolder	$O(s)$	$O(1)$	uniqued constants	only all-constant operands
NoFolder	$O(1)$	$O(1)$	—	always creates
InstSimplifyFolder	bounded by the recursion limit: $O(c^{d})$ for a branching factor $c$ of the simplifier, in practice small	$O(1)$–$O(k)$ plus known-bits queries	—	returns existing values
Inserters	$O(1)$ + callback cost	$O(1)$	—	—
Builder state	$O(1)$ per setter; $O(1)$ per stamped instruction	$O(1)$	a few words	guards $O(1)$

Proposition 10.3.11 (Builder emission is linear)

A front end that emits $n$ instructions through IRBuilder<ConstantFolder> with operands of bounded arity does $O(n)$ work in the builder.

Proof

Each call does constant work outside the folder (Algorithm 10.3.3). ConstantFolder either returns $\bot$ in $O(1)$ (after a check per operand) or folds constants of bounded size. Constants built by previous folds are uniqued, so they do not grow with $n$ unless the program itself contains large constant expressions.

Pathological input. B.SetInsertPoint(BB->getFirstInsertionPt()) inside a loop that emits one instruction per iteration into a block with $p$ phis costs $\Theta(n \cdot p)$: each call rescans the phis. Save the iterator once. With InstSimplifyFolder, each fold may compute known bits of its operands, which walks up to the recursion depth of the operand DAG. That is cheap per call, but it is a real cost in a front end that emits millions of instructions, which is why Clang uses TargetFolder (constant folding only).

Direct construction¶

Unlinked creation (nullptr position) followed by insertInto/insertBefore(iterator): build a sequence first, then place it. This is useful when the position is not yet known.
Instruction::clone creates an unlinked copy with the same operands (Lesson 10.2's use lists grow accordingly), then insertBefore places it. Loop unrolling and inlining work this way.

Insertion points¶

SetInsertPointPastAllocas(F): the first position after the entry block's static allocas. Use it for new allocas, so that they stay in the entry block and mem2reg can see them (Ch 16).
InsertPointGuard and saveIP/restoreIP: temporary detours, restored on scope exit (Proposition 10.3.10).
moveBeforePreserving(iterator): moves an instruction and keeps its debug records with it [LLVM-DbgRecords].

Folders¶

TargetFolder (llvm/include/llvm/Analysis/TargetFolder.h): constant folding that also uses the DataLayout (pointer sizes, GEP offsets) through ConstantFoldBinaryOpOperands. Clang's CGBuilderTy uses it.
Custom folders: subclass IRBuilderFolder to add domain rules, or to make folding deterministic across LLVM versions in a test.
Folding later instead of now: build with NoFolder or ConstantFolder and run instsimplify/instcombine afterwards. This is more robust and whole-function, but pays for the extra IR in the meantime.

Inserters¶

Clang's CGBuilderInserter forwards to CodeGenFunction::InsertHelper (clang/lib/CodeGen/CodeGenFunction.cpp), which calls LoopStack.InsertHelper(I) (loop metadata) and marks instructions emitted inside a sanitizer scope with setNoSanitizeMetadata() [CLANG-CGBuilder].
Worklist inserters: InstCombine's builder is IRBuilder<TargetFolder, IRBuilderInstCombineInserter> (llvm/include/llvm/Transforms/InstCombine/InstCombiner.h), whose InsertHelper adds each new instruction to InstCombine's worklist (and registers new llvm.assumes), so newly created code is itself combined.

Builder state¶

Default operand bundles and !fpmath tags (setDefaultOperandBundles, setDefaultFPMathTag).
IRBuilder<>::CreateIntrinsic/CreateBinaryIntrinsic: builder-level access to intrinsics with the same folding and state (Lab 10.1 uses it for smin).

7. In real compilers¶

Direct construction¶

LLVM

llvm/include/llvm/IR/InstrTypes.h BinaryOperator::Create, llvm/include/llvm/IR/Instruction.h InsertPosition (the Instruction * constructor is LLVM_DEPRECATED), llvm/lib/IR/Instruction.cpp Instruction::insertBefore(BasicBlock &, iterator) [LLVM-Instr].

InstCombine returns a new, unlinked instruction from a visit method and lets the driver insert it and RAUW the old one: direct construction plus deferred insertion (InstCombinerImpl::run in llvm/lib/Transforms/InstCombine/InstructionCombining.cpp).

Insertion points¶

LLVM

llvm/include/llvm/IR/BasicBlock.h begin() (sets the head bit), getFirstNonPHIIt, getFirstInsertionPt; llvm/lib/IR/Instruction.cpp Instruction::insertBefore (the head-bit logic and the phi assertion); llvm/include/llvm/IR/IRBuilder.h SetInsertPoint overloads [LLVM-IRB, LLVM-DbgRecords].

Find where LLVM does it. In Instruction.cpp, find the assertion text "Inserting PHI after debug-records!". Question: which bit of the insertion iterator must be clear for that assertion to be reachable? (Quiz llvm-where-headbit.)

Folders¶

LLVM

llvm/include/llvm/IR/ConstantFolder.h ConstantFolder::FoldBinOp (both operands must be Constant), llvm/include/llvm/IR/NoFolder.h, llvm/include/llvm/Analysis/InstSimplifyFolder.h (calls simplifyBinOp), llvm/include/llvm/Analysis/TargetFolder.h [LLVM-Folders].

Clang clang/lib/CodeGen/CGBuilder.h: typedef llvm::IRBuilder<llvm::TargetFolder, CGBuilderInserterTy> CGBuilderBaseTy; [CLANG-CGBuilder].
Swift lib/IRGen/IRBuilder.h (swift-6.1-RELEASE): using IRBuilderBase = llvm::IRBuilder<>; and class IRBuilder : public IRBuilderBase, the default folder and inserter plus Swift-specific helpers.

Inserters¶

Clang's builder: TargetFolder plus its own inserter

Reproduce (Clang source at llvmorg-23.1.2):

curl -s https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/clang/lib/CodeGen/CGBuilder.h \
  | grep -n "class CGBuilderInserter" -A 18

Output (complete):

32:class CGBuilderInserter final : public llvm::IRBuilderDefaultInserter {
33-  friend CGBuilderTy;
34-
35-public:
36-  CGBuilderInserter() = default;
37-  explicit CGBuilderInserter(CodeGenFunction *CGF) : CGF(CGF) {}
38-
39-  /// This forwards to CodeGenFunction::InsertHelper.
40-  void InsertHelper(llvm::Instruction *I, const llvm::Twine &Name,
41-                    llvm::BasicBlock::iterator InsertPt) const override;
42-
43-private:
44-  CodeGenFunction *CGF = nullptr;
45-};
46-
47-typedef CGBuilderInserter CGBuilderInserterTy;
48-
49-typedef llvm::IRBuilder<llvm::TargetFolder, CGBuilderInserterTy>
50-    CGBuilderBaseTy;

What to notice: Definition 10.3.5 in production. The inserter overrides InsertHelper(I, Name, InsertPt), and the builder type pairs it with TargetFolder, so every instruction Clang emits goes through CodeGenFunction::InsertHelper.

Builder state¶

LLVM

llvm/include/llvm/IR/IRBuilder.h: IRBuilderBase members StoredDL, FMF, IsFPConstrained, DefaultConstrainedRounding, and the nested InsertPointGuard, FastMathFlagGuard [LLVM-IRB].

Clang sets the builder's constrained-FP state from the FP options in effect for each expression (#pragma STDC FENV_ACCESS, -ffp-model) with CodeGenFunction::CGFPOptionsRAII in clang/lib/CodeGen/CodeGenFunction.cpp, an RAII guard that restores setDefaultConstrainedExcept/Rounding in its destructor, like Proposition 10.3.10.

8. Comparison¶

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Direct construction	full control, no folding	$O(k)$ per instruction	no help: you set flags, names, locations yourself	verbose	passes rewriting single instructions (Lab 10.2)
Insertion points	exact placement incl. debug-record side (Definition 10.3.1)	$O(1)$	wrong point = verifier error, or silently wrong debug info	remember to move it	every emitter
Folders	none / constants / InstSimplify identities (Proposition 10.3.8)	$O(1)$ / $O(s)$ / bounded recursion	less IR to clean up; `NoFolder` gives exact IR for tests	choose a template argument	`ConstantFolder` default; `InstSimplifyFolder` in passes; `NoFolder` in tests
Inserters	a hook per created instruction (Theorem 10.3.9)	$O(1)$ + callback	—	subclass or lambda	Clang bookkeeping, worklists, instrumentation
Builder state	flags, locations, strict FP applied uniformly	$O(1)$	forgotten state is silent (missing `!dbg`, wrong fast-math)	setters + guards	front ends, FP-sensitive passes

Choose direct construction for a one-off replacement whose position and flags you compute anyway. Choose IRBuilder<> for emitting sequences. Pick InstSimplifyFolder when you build in a pass and want the simplest IR immediately, and NoFolder when a test must see every instruction. Choose a custom inserter when every created instruction needs the same side effect. Always move the insertion point with iterators, not Instruction *, in LLVM 23.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch10.yaml`)	Drill	Flashcard tag	Exercises
Direct construction	`direct-construction-fold`, `direct-construction-position`	`./course drill irbuilder-fold --difficulty hard` (the NoFolder column is direct construction)	`direct-construction`	Lab 10.2 R6
Insertion points	`headbit-order`, `llvm-where-headbit`, `direct-construction-position`	`./course drill irbuilder-fold`	`insertion-points`	Lab 10.1
Folders	`folder-trace`, `direct-construction-fold`	`./course drill irbuilder-fold`	`folders`	Lab 10.1 R5
Inserters	`inserter-count`, `folder-trace`	`./course drill irbuilder-fold` (count the `new`s)	`inserters`	—
Builder state	`fmf-guard`, `builder-state-dbg`	— (see note)	`builder-state`	—

Builder state is a set of setters with one rule (Proposition 10.3.10), so a randomized drill would only repeat it. The quiz asks for a traced state instead.

Pitfall

B.CreateAdd(X, Y) does not always return an Instruction *. With any folder other than NoFolder it can return a constant or an existing value. Code that does cast<Instruction>(B.CreateAdd(…))->setHasNoSignedWrap() crashes the day an operand becomes constant. Pass the flags to CreateAdd(X, Y, "", /*HasNUW=*/…, /*HasNSW=*/…), or dyn_cast the result.

References¶

See the chapter references.

Technique	Time per call (worst)	Time (typical)	Space	Notes
Direct construction	\(O(k)\)	\(O(k)\)	one allocation (co-allocated operands)	no folding
Insertion points	\(O(1)\) to set; \(O(1)\) insert	\(O(1)\)	the iterator + head bit	`getFirstInsertionPt` scans past phis: \(O(\#\text{phis})\)
ConstantFolder	\(O(s)\)	\(O(1)\)	uniqued constants	only all-constant operands
NoFolder	\(O(1)\)	\(O(1)\)	—	always creates
InstSimplifyFolder	bounded by the recursion limit: \(O(c^{d})\) for a branching factor \(c\) of the simplifier, in practice small	\(O(1)\)–\(O(k)\) plus known-bits queries	—	returns existing values
Inserters	\(O(1)\) + callback cost	\(O(1)\)	—	—
Builder state	\(O(1)\) per setter; \(O(1)\) per stamped instruction	\(O(1)\)	a few words	guards \(O(1)\)

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Direct construction	full control, no folding	\(O(k)\) per instruction	no help: you set flags, names, locations yourself	verbose	passes rewriting single instructions (Lab 10.2)
Insertion points	exact placement incl. debug-record side (Definition 10.3.1)	\(O(1)\)	wrong point = verifier error, or silently wrong debug info	remember to move it	every emitter
Folders	none / constants / InstSimplify identities (Proposition 10.3.8)	\(O(1)\) / \(O(s)\) / bounded recursion	less IR to clean up; `NoFolder` gives exact IR for tests	choose a template argument	`ConstantFolder` default; `InstSimplifyFolder` in passes; `NoFolder` in tests
Inserters	a hook per created instruction (Theorem 10.3.9)	\(O(1)\) + callback	—	subclass or lambda	Clang bookkeeping, worklists, instrumentation
Builder state	flags, locations, strict FP applied uniformly	\(O(1)\)	forgotten state is silent (missing `!dbg`, wrong fast-math)	setters + guards	front ends, FP-sensitive passes

Lesson 10.3 — Building IR: IRBuilder, insertion points, folders and inserters¶

1. Problem and motivation¶

Direct construction¶

Insertion points¶

Folders¶

Inserters¶

Builder state¶

2. Definitions and algorithms¶

Direct construction¶

Insertion points¶

Folders¶

Inserters¶

Builder state¶

3. Worked example¶

Direct construction¶

Insertion points¶

Folders¶

Inserters¶

Builder state¶

4. Invariants and correctness¶

Direct construction¶

Insertion points¶

Folders¶

Inserters¶

Builder state¶

5. Complexity¶

6. Variants and refinements¶

Direct construction¶

Insertion points¶

Folders¶

Inserters¶

Builder state¶

7. In real compilers¶

Direct construction¶

Insertion points¶

Folders¶

Inserters¶

Builder state¶

8. Comparison¶

9. Assessment¶

References¶