Lesson 11.2 — Short-circuit conditions: jumping code vs boolean values¶

Techniques: jumping code — &&, || and ! become branches, and a condition is compiled to a pair of targets rather than a value (Arden, Galler & Graham 1962; the translation scheme of the Dragon book); boolean values — every operand is computed and the results are combined with and/or/xor or select in straight-line code (what LLVM's SimplifyCFG and the back end's setcc/cmov produce when it is safe) · Pebble implements: jumping code in lowerToPIR (spec §15 forbids and/or for &&/||); both strategies in the comparison lab (labs/ch11-lowering, part A) · Prerequisites: Lesson 11.1 (syntax-directed translation) · Time: 3–4 hours

Pebble's && and || short-circuit: the right operand runs only if the left one does not decide the result (spec §8.5). That is a statement about control: i < 3 && xs[i] > 0 must not evaluate xs[i] when i ≥ 3, or it traps. A compiler has two ways to lower a condition. It can turn the operators into control flow (jumping code), which gives short-circuit semantics by construction. Or it can compute every operand and combine the i1 results (boolean values), which has no branches but is only allowed when evaluating an operand early can do no harm. The running example is

if (a < b && !(b == c)) || c > 0 { return g(); }
return 0;

with atoms \(p = (a < b)\), \(q = (b = c)\), \(r = (c > 0)\), i.e. the condition \((p \land \neg q) \lor r\).

1. Problem and motivation¶

Jumping code¶

Arden, Galler and Graham gave an algorithm that translates a Boolean expression directly into tests and jumps, so that evaluation stops as soon as the result is known [AGG62]. The Dragon book presents it as a syntax-directed translation with two inherited attributes, the true and false labels of each subexpression [ALSU07 §6.6]; Appel's Tree IR represents such a condition as a function from two labels to code (Cx) [Appel]. For a language whose && and || are defined to short-circuit (C, Rust, Swift, Pebble), jumping code is the natural lowering: it is exactly the semantics. lowerToPIR uses it for every &&, || and ! in a condition, and in value position it stores true or false into a temporary from the two targets (E2).

Boolean values¶

On a pipelined processor a conditional branch costs almost nothing when predicted and 15–20 cycles when mispredicted. A condition of \(n\) comparisons in jumping code executes up to \(n\) branches whose outcomes may be data-dependent; the boolean-value strategy computes all \(n\) comparisons (icmp/setcc) and combines them with bitwise operations in one block, with no branch at all. It evaluates more, so it is legal only when every operand can be evaluated early without a visible difference: no trap, no side effect, no undefined behavior. LLVM's isSafeToSpeculativelyExecute decides this [LLVM-ValueTracking]; SimplifyCFG's foldBranchToCommonDest then converts jumping code into and/or/select [LLVM-SimplifyCFG]. The comparison lab implements both and measures them (part A).

2. Definitions and algorithms¶

Definition 11.2.1 (Condition, atom, short-circuit semantics)

A condition is a tree over the connectives \(\land\) (&&), \(\lor\) (||) and \(\neg\) (!) whose leaves are atoms: expressions of type bool whose value does not depend on other atoms (here: comparisons). Its short-circuit semantics evaluates \(e_1 \land e_2\) by evaluating \(e_1\), and \(e_2\) only if \(e_1\) is true; \(e_1 \lor e_2\) evaluates \(e_2\) only if \(e_1\) is false; \(\neg e\) evaluates \(e\). For an assignment \(\rho\) of truth values to atoms, \(\mathrm{read}(e, \rho)\) is the sequence of atoms this evaluation reads.

Algorithm 11.2.2 (Jumping code, JC)

Input: a condition \(e\) and two blocks \(t\), \(f\); the current insertion block.
Output: code in the current block (and new blocks) such that control reaches \(t\) iff \(e\) is true.
Precondition: \(t\) and \(f\) exist (they may be empty and filled later).
Postcondition: every path through the emitted code evaluates exactly the atoms of \(\mathrm{read}(e, \rho)\), in that order, and ends at \(t\) if \(e\) is true under \(\rho\), else at \(f\) (Theorem 11.2.3).
Invariant: each call emits code only into the current block and into the blocks it creates; it never adds an edge into an existing block other than \(t\) and \(f\).

function JC(e, t, f):
    if e = ¬e1:     JC(e1, f, t)                          # swap the targets, emit nothing
    if e = e1 ∧ e2: m ← NewBlock(); JC(e1, m, f); SetInsertPoint(m); JC(e2, t, f)
    if e = e1 ∨ e2: m ← NewBlock(); JC(e1, t, m); SetInsertPoint(m); JC(e2, t, f)
    if e is the constant true / false: emit  goto t  /  goto f
    otherwise (an atom): c ← Lower(e)                     # Algorithm 11.1.3
                         emit  br c, t, f

function LowerAsValue(e):                                  # && / || in value position
    x ← FreshTemp(bool);  T ← NewBlock(); F ← NewBlock(); J ← NewBlock()
    JC(e, T, F)
    in T: x ← true;  goto J
    in F: x ← false; goto J
    SetInsertPoint(J);  return x

Theorem 11.2.3 (Jumping code implements short-circuit semantics)

For every condition \(e\), targets \(t \ne f\) and assignment \(\rho\), the unique path from the insertion point through the code emitted by \(\mathrm{JC}(e, t, f)\) reads exactly the atoms \(\mathrm{read}(e, \rho)\), in order, and leaves to \(t\) if \(e\) is true under \(\rho\) and to \(f\) otherwise.

Proof

By structural induction on \(e\). Atom: the code evaluates the atom once and branches to \(t\) if it is true, else to \(f\); \(\mathrm{read}\) is that one atom. Constant: no atom is read and the jump goes to the right target. \(\neg e_1\): by the hypothesis, \(\mathrm{JC}(e_1, f, t)\) reads \(\mathrm{read}(e_1, \rho)\) and reaches \(f\) iff \(e_1\) is true, i.e. reaches \(t\) iff \(\neg e_1\) is true; \(\mathrm{read}(\neg e_1, \rho) = \mathrm{read}(e_1, \rho)\). \(e_1 \land e_2\): the code of \(e_1\) runs first and reaches \(m\) iff \(e_1\) is true, else \(f\) — correct, since then \(e\) is false and \(e_2\) must not be read. At \(m\) the code of \(e_2\) runs, reaching \(t\) iff \(e_2\) is true, which is then the value of \(e\); the atoms read are \(\mathrm{read}(e_1, \rho) \cdot \mathrm{read}(e_2, \rho)\), as the semantics prescribes. The block \(m\) is fresh, so no other path enters it (the invariant). \(e_1 \lor e_2\): symmetric, with \(t\) and \(f\) exchanged for the first operand.

Proposition 11.2.4 (Size of jumping code)

For a condition with \(n \ge 1\) atoms and \(k\) binary connectives (\(k = n - 1\)), \(\mathrm{JC}(e, t, f)\) emits exactly \(n\) conditional branches, creates exactly \(k\) new blocks, and adds \(2n\) CFG edges; with the entry block and the two targets, the condition occupies \(n + 2\) blocks. Negations cost nothing. LowerAsValue creates 3 more blocks (\(T\), \(F\), \(J\)) and 2 more edges (\(T \to J\), \(F \to J\)).

Proof

By induction on \(e\): an atom emits one branch with two edges and creates no block; \(\neg\) emits nothing; each binary connective creates one block \(m\) and emits the code of its two operands, whose counts add up. A binary tree with \(n\) leaves has \(n - 1\) binary internal nodes, so there are \(n\) branches, \(2n\) edges and \(n - 1\) new blocks; with the entry block and \(t\), \(f\) that is \(n + 2\) blocks. LowerAsValue passes its own blocks \(T\) and \(F\) as the targets and adds \(J\) with one jump from each of \(T\) and \(F\). (The drill jumping-code counts the if-statement form: \(n + 2\) blocks, \(2n\) edges.)

Definition 11.2.5 (Speculatable expression)

An expression is speculatable if evaluating it when the source would not have evaluated it cannot change the program's behavior: it cannot trap, has no side effect, and has no undefined behavior for any value of its inputs. Comparisons of loaded scalars are speculatable; a / b, xs[i] with a bounds check, a call, or a load from a pointer that might be invalid are not.

Algorithm 11.2.6 (Boolean values, Val)

Input: a condition \(e\) all of whose atoms are speculatable.
Output: an i1 value equal to the value of \(e\).
Precondition: every atom is speculatable (Definition 11.2.5).
Postcondition: straight-line code, no branch; every atom evaluated exactly once.
Invariant: the returned value of a subtree equals its short-circuit value whenever all its atoms are defined.

function Val(e):
    if e = ¬e1:     return xor(Val(e1), true)             # `not`
    if e = e1 ∧ e2: a ← Val(e1); b ← Val(e2); return and(a, b)      # or select(a, b, false)
    if e = e1 ∨ e2: a ← Val(e1); b ← Val(e2); return or(a, b)       # or select(a, true, b)
    otherwise:      return Lower(e)                      # icmp

Theorem 11.2.7 (When the value strategy is equivalent)

If every atom of \(e\) is speculatable, then \(\mathrm{Val}(e)\) has the same value as the short-circuit evaluation of \(e\) and the program's observable behavior is unchanged. If some atom is not speculatable, the two can differ.

Proof

Evaluating an atom that short-circuit evaluation would skip has, by Definition 11.2.5, no observable effect and produces a defined i1. On defined i1 values, and, or and xor … true compute exactly \(\land\), \(\lor\) and \(\neg\), and the value of \(e_1 \land e_2\) does not depend on whether \(e_2\) was read (\(\mathit{false} \land x = \mathit{false}\) for every defined \(x\)); by structural induction the values agree. Counterexample when an atom is not speculatable: d != 0 && 10 / d > 1 with \(d = 0\) — short-circuit evaluation stops after the first atom, while \(\mathrm{Val}\) divides by zero, which traps in Pebble and is undefined behavior in LLVM IR (e2e test shortcircuit-guard.pbl).

and i1 is not a safe && in LLVM IR

Even with speculatable atoms, LLVM's and i1 %a, %b is poison when %b is poison, although %a is false. A front end that speculates an atom which may be poison (an nsw add that overflowed, say) must use select i1 %a, i1 %b, i1 false, which ignores %b when %a is false. InstCombine and SimplifyCFG emit select for exactly this reason (Lesson 13.8 covers poison).

3. Worked example¶

Jumping code¶

JC on \((p \land \neg q) \lor r\) with targets \(T\) (the call) and \(F\) (return 0); the block of a subexpression is named after its first atom. Every call, outermost first:

call	\(e\)	\(t\)	\(f\)	emits
1	\((p \land \neg q) \lor r\)	T	F	new block \(r\); first operand with \((T, r)\)
2	\(p \land \neg q\)	T	r	new block \(q\); first operand with \((q, r)\)
3	\(p\)	q	r	`br p, q, r` in the entry block
4	\(\neg q\)	T	r	nothing: swap to \((r, T)\)
5	\(q\)	r	T	`br q, r, T` in block \(q\)
6	\(r\)	T	F	`br r, T, F` in block \(r\)

Result: 3 conditional branches, blocks entry, \(q\), \(r\), T, F (\(n + 2 = 5\)), 6 edges (Proposition 11.2.4). Running it on all 8 assignments of \((p, q, r)\) reads \(p\,r\) when \(p\) is false, \(p\,q\) when \(p\) is true and \(q\) false (reaching T without reading \(r\)), and \(p\,q\,r\) otherwise — exactly short-circuit evaluation (Theorem 11.2.3). Clang produces this CFG block for block (box in §7).

flowchart TD
  E([entry: br p]) -->|true| Q[q: br q]
  E -->|false| R[r: br r]
  Q -->|true| R
  Q -->|false| T[T: call g]
  R -->|true| T
  R -->|false| F[F: return 0]

Boolean values¶

Val computes \(p\), \(q\), \(r\) (3 icmp), \(\neg q\) (xor), \(p \land \neg q\) (and), and the or: 6 instructions, 1 block, 0 branches. All three atoms compare parameters, so they are speculatable and Theorem 11.2.7 applies; clang -O2 produces the same shape, with icmp ne folding the xor into the comparison (box in §7).

Try it

./course drill jumping-code --seed 7 --difficulty medium --solution gives the branch targets, block and edge counts and one execution of a random condition; --difficulty hard adds the value strategy's counts.

4. Invariants and correctness¶

Jumping code¶

Theorem 11.2.3 is proved above; its invariant — each call only branches to its own targets and to blocks it created — is what lowerToPIR's lowerCond maintains by creating the intermediate block before recursing. The theorem assumes \(t \ne f\); with \(t = f\) (an if whose two branches are empty) the code is still correct but every branch is redundant, and SimplifyCFG deletes it. Nothing breaks on atoms with side effects or traps: that is the point of the strategy.

Boolean values¶

Theorem 11.2.7 needs every atom speculatable. In Pebble the checked operations (/, %, <<, indexing, overflowing +) trap, and calls may print, so the reference lowering never speculates; LLVM's optimizer can, after it has proved the atoms safe (for example once a bounds check was removed, Ch 18).

5. Complexity¶

\(n\) = atoms of the condition, \(c\) = cost of evaluating one atom, \(b\) = cost of a predicted branch, \(m\) = misprediction penalty, \(\mu_j\) = misprediction rate of atom \(j\)'s branch.

Technique	Code size	Time per evaluation (worst)	Time (typical)	Justification
Jumping code	\(n\) branches, \(n + 2\) blocks	\(n(c + b) + m \sum_j \mu_j\)	reads \(\mathbb{E}[\lvert\mathrm{read}(e, \rho)\rvert] \le n\) atoms	Proposition 11.2.4; each executed branch may mispredict
Boolean values	\(n\) `icmp` + \((n - 1)\) `and`/`or` + one op per `!`, 1 block	\(n \cdot c + O(n)\)	always \(n\) atoms, no misprediction	Algorithm 11.2.6 evaluates every atom once, straight-line

Pathological family. \(e_n = a_1 \ne 0 \land a_2 \ne 0 \land \dots \land a_n \ne 0\) with each \(a_j\) nonzero with probability \(1/2\), independently: jumping code reads on average \(\sum_{j=1}^{n} 2^{-(j-1)} < 2\) atoms, but the first branch mispredicts about half the time whatever the predictor does, so the expected cost is at least \(m/2\); the value strategy always reads \(n\) atoms and never mispredicts. Conversely, if the \(a_j\) are almost always nonzero and the atoms are expensive, jumping code wins. The lab's guard8 (8 atoms, variables uniform in [−2, 2]) measured 5.62 ns (jumping) vs 2.53 ns (values) per call on random inputs, and 1.94 vs 2.47 ns when the same input repeats and the predictor learns the branches (labs/ch11-lowering/SPEC.md, "Measurement").

Jumping code¶

Backpatching [ALSU07 §6.7]: emit the branches with unknown targets and fill them in from lists, which gives one-pass jumping code for a translator that emits text instead of block objects.
The last operand as a value (Clang's EmitBranchOnBoolExpr and value context): in value position, compute the last atom as a value and feed it to the phi instead of branching on it — one branch and one block fewer (box in §7). Pebble's reference lowering does not, to keep the scheme uniform.
Fall-through ordering: choose which target follows each branch so that the likely successor falls through (Ch 23's code layout).

Boolean values¶

select instead of and/or for poison safety (the pitfall above; [LLVM-LangRef]).
Branch-to-select conversion after the fact: SimplifyCFG's foldBranchToCommonDest speculates a small block into its predecessor when isSafeToSpeculativelyExecute allows it [LLVM-SimplifyCFG, LLVM-ValueTracking]; the back end's if-conversion and cmov formation do the same on machine code (Lesson 23.5).
The reverse: LLVM's SelectOptimize pass (llvm/lib/CodeGen/SelectOptimize.cpp) and the X86 back end's X86CmovConversion.cpp turn a select or cmov back into a branch when the branch looks predictable and an operand is expensive to compute; trade-off: they need a cost model or profile, and a wrong guess costs mispredictions again.

7. In real compilers¶

Jumping code¶

Clang: CodeGenFunction::EmitBranchOnBoolExpr in clang/lib/CodeGen/CodeGenFunction.cpp recurses through &&, ||, ! and the conditional operator with a true and a false block [CLANG-BranchOnBool]. GCC: shortcut_cond_expr in gcc/gimplify.cc [GCC-Gimplify]. rustc: LogicalOp in compiler/rustc_mir_build/src/builder/expr/into.rs [RUSTC-LogicalOp]. Pebble: FunctionLowering::lowerCond in solutions/pebble/lib/Lower/LowerExpr.cpp; tests/ch11/lit/pir-jumping-code.pbl checks its shape.

Clang and GCC: the jumping code of Algorithm 11.2.2

Reproduce (clang 23.1.2, gcc 14.2.0):

cat > sc.c <<'EOF'
int g(void);
int f(int a, int b, int c) {
  if ((a < b && !(b == c)) || c > 0)
    return g();
  return 0;
}
EOF
clang-23 -O0 -fno-discard-value-names -S -emit-llvm sc.c -o - | sed -n '/^define/,/^if.end:/p' | grep -v 'alloca\|store i32 %'
gcc-14 -O0 -fdump-tree-gimple -c sc.c && sed -n '/if (a < b)/,/<D.2777>:/p' sc.c.*.gimple

Output:

define dso_local i32 @f(i32 noundef %a, i32 noundef %b, i32 noundef %c) #0 {
entry:
  %0 = load i32, ptr %a.addr, align 4
  %1 = load i32, ptr %b.addr, align 4
  %cmp = icmp slt i32 %0, %1
  br i1 %cmp, label %land.lhs.true, label %lor.lhs.false

land.lhs.true:                                    ; preds = %entry
  %2 = load i32, ptr %b.addr, align 4
  %3 = load i32, ptr %c.addr, align 4
  %cmp1 = icmp eq i32 %2, %3
  br i1 %cmp1, label %lor.lhs.false, label %if.then

lor.lhs.false:                                    ; preds = %land.lhs.true, %entry
  %4 = load i32, ptr %c.addr, align 4
  %cmp2 = icmp sgt i32 %4, 0
  br i1 %cmp2, label %if.then, label %if.end

if.then:                                          ; preds = %lor.lhs.false, %land.lhs.true
  %call = call i32 @g()
  br label %return

if.end:                                           ; preds = %lor.lhs.false
  if (a < b) goto <D.2779>; else goto <D.2776>;
  <D.2779>:
  if (b != c) goto <D.2777>; else goto <D.2776>;
  <D.2776>:
  if (c > 0) goto <D.2777>; else goto <D.2778>;
  <D.2777>:

What to notice: Clang's three branches are the table of §3 row for row — land.lhs.true is block \(q\), lor.lhs.false is block \(r\) — and !(b == c) produced no instruction: its branch has the targets swapped (br i1 %cmp1, label %lor.lhs.false, label %if.then, call 5 of the trace). GCC's gimplifier emits the same CFG, having folded the ! into !=.

Boolean values¶

LLVM: foldBranchToCommonDest in llvm/lib/Transforms/Utils/SimplifyCFG.cpp merges a branch on a speculatable condition into its predecessor's with or/and/select [LLVM-SimplifyCFG], guarded by isSafeToSpeculativelyExecute in llvm/lib/Analysis/ValueTracking.cpp [LLVM-ValueTracking]. The lab's emitCondition(…, CondStrategy::Value) is Algorithm 11.2.6.

From jumping code to values: Clang -O0 vs -O2 on a condition used as a value

Reproduce (clang 23.1.2, opt 23.1.2):

cat > scv.c <<'EOF'
int h(int a, int b, int c) {
  return (a < b && !(b == c)) || c > 0;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm scv.c -o - | opt -passes=mem2reg -S | sed -n '/^define/,/^}/p'
clang-23 -O2 -fno-discard-value-names -S -emit-llvm scv.c -o - | sed -n '/^define/,/^}/p'
clang-23 -O2 -S scv.c -o - | sed -n '/^h:/,/retq/p' | grep -v '^\s*\.'

Output:

define dso_local i32 @h(i32 noundef %a, i32 noundef %b, i32 noundef %c) #0 {
entry:
  %cmp = icmp slt i32 %a, %b
  br i1 %cmp, label %land.lhs.true, label %lor.rhs

land.lhs.true:                                    ; preds = %entry
  %cmp1 = icmp eq i32 %b, %c
  br i1 %cmp1, label %lor.rhs, label %lor.end

lor.rhs:                                          ; preds = %land.lhs.true, %entry
  %cmp2 = icmp sgt i32 %c, 0
  br label %lor.end

lor.end:                                          ; preds = %lor.rhs, %land.lhs.true
  %0 = phi i1 [ true, %land.lhs.true ], [ %cmp2, %lor.rhs ]
  %lor.ext = zext i1 %0 to i32
  ret i32 %lor.ext
}
define dso_local range(i32 0, 2) i32 @h(i32 noundef %a, i32 noundef %b, i32 noundef %c) local_unnamed_addr #0 {
entry:
  %cmp = icmp slt i32 %a, %b
  %cmp1 = icmp ne i32 %b, %c
  %or.cond.not = and i1 %cmp, %cmp1
  %cmp2 = icmp sgt i32 %c, 0
  %narrow = or i1 %cmp2, %or.cond.not
  %lor.ext = zext i1 %narrow to i32
  ret i32 %lor.ext
}
h:                                      # @h
# %bb.0:
    cmpl    %esi, %edi
    setl    %al
    cmpl    %edx, %esi
    setne   %cl
    andb    %al, %cl
    testl   %edx, %edx
    setg    %al
    orb %cl, %al
    movzbl  %al, %eax
    retq

What to notice: at -O0, value context is jumping code whose last atom is used as a value (%cmp2 flows into the phi; §6). At -O2, all three comparisons are speculatable (Definition 11.2.5), so SimplifyCFG rewrote the branches into Algorithm 11.2.6: three icmp, one and, one or, one block, and the machine code is branch-free setcc + and/or.

Find where LLVM does it. In llvm/lib/Transforms/Utils/SimplifyCFG.cpp, which function folds a conditional branch into a predecessor that branches to a common destination, producing the %or.cond above? (Quiz llvm-where-fold-branch.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Jumping code	Exact short-circuit semantics for any atoms, including traps and side effects	\(\le n\) atoms, \(\le n\) branches · wins when branches are predictable or atoms expensive	CFG mirrors the source; each atom keeps its own location	Low (one recursive function with two targets)	Every front end's lowering of `&&`/`\\|\\|`/`!` (Clang, GCC, rustc, Pebble)
Boolean values	Only for speculatable atoms (Theorem 11.2.7)	exactly \(n\) atoms, 0 branches · wins on unpredictable conditions of cheap atoms	Straight-line code; `select` needed for poison safety	Low, plus a speculation-safety analysis	The optimizer's rewrite of jumping code (SimplifyCFG), `setcc`/`cmov` in back ends, SIMD code

Choose jumping code when the language defines short-circuit evaluation and the atoms may trap or have effects — always in a front end. Choose boolean values when every atom is cheap and speculatable and the outcome is hard to predict; in practice you let the optimizer decide, which is what LLVM's default<O1> and default<O2> pipelines do (pebblec -O2; the lab's --O2 measurement shows SimplifyCFG making the two strategies' code identical).

9. Assessment¶

Quiz (./course quiz 11): jc-targets, jc-blocks-edges (tag jumping-code); bool-values-legal, bool-values-ops, llvm-where-fold-branch (tag bool-values).
Drill: ./course drill jumping-code (targets, counts, runs; hard: the value strategy's operation counts).
Flashcards: tags jumping-code, bool-values.
Exercises: E2 (lowerCond and value context); lab part A.

References¶

See the chapter references.

Lesson 11.2 — Short-circuit conditions: jumping code vs boolean values¶

1. Problem and motivation¶

Jumping code¶

Boolean values¶

2. Definitions and algorithms¶

3. Worked example¶

Jumping code¶

Boolean values¶

4. Invariants and correctness¶

Jumping code¶

Boolean values¶

5. Complexity¶

6. Variants and refinements¶

Jumping code¶

Boolean values¶

7. In real compilers¶

Jumping code¶

Boolean values¶

8. Comparison¶

9. Assessment¶

References¶