Skip to content

Lab 11 · Short-circuit conditions and switch lowering

Chapter: 11 · Lowering & Code Generation · Lessons: 11.2, 11.3 · Time: 5–8 hours · Tests: ./course test 11 (label ch11, tests ch11.Lab.*, ch11.lab.*)

Goal

This is the chapter's comparison lab. You compile two small input languages to LLVM IR in competing ways and measure what the choice changes.

  • Part A (Lesson 11.2). A short-circuit condition such as a < b && !(c == d) || e > 0 compiled as jumping code (every comparison ends in a conditional branch, &&/||/! only choose branch targets) and as boolean values (every comparison is computed and the i1 results are combined with and/or/xor in one block).
  • Part B (Lesson 11.3). A switch on one integer compiled four ways: one LLVM switch instruction (the back end decides), a jump table (indirectbr through a table of blockaddress constants), a balanced binary search tree of comparisons, and bit tests (1 << (x - min) tested against one mask per destination).

The provided tool ch11-lowerlab checks every function you emit against the reference semantics, prints its IR shape (blocks, instructions, conditional branches, longest chain of comparisons) and times it under ORC LLJIT, with and without LLVM's default<O2>.

Requirements

  • R1. emitCondition(M, Name, C, CondStrategy::Jumping) adds define i64 @Name(i64 %a, …, i64 %h) to M that returns 1 if C holds and 0 otherwise, evaluated with short-circuit semantics. It contains exactly one icmp per comparison of C, exactly one conditional branch per comparison, and no and, or, xor or select on i1.
  • R2. emitCondition(…, CondStrategy::Value) returns the same results from a function with a single basic block (no branches), with exactly one icmp per comparison. Speculating every comparison is legal here because comparisons of arguments have no side effects and cannot trap (Lesson 11.2 §4 says when it would not be).
  • R3. emitSwitch(M, Name, S, St) adds define i64 @Name(i64 %x) that returns the destination number of x in S (0 … NumDests − 1), or NumDests for the default.
  • R4. LLVMSwitch: one switch instruction, no conditional branch, no indirectbr.
  • R5. JumpTable: one icmp (the range check x − min ≤ max − min, unsigned) and one indirectbr through a constant table of blockaddresses with one entry per value in [min, max] (holes go to the default); no switch. Returns nullptr if max − min ≥ 4096.
  • R6. BinarySearch: no switch and no indirectbr; at most ⌈log₂ n⌉ + 1 comparisons on any path from the entry (n = number of cases).
  • R7. BitTests: no switch and no indirectbr; at least one shl; at most NumDests + 1 conditional branches (the range check and one test per destination). Returns nullptr if max − min ≥ 64.
  • R8. Every strategy but LLVMSwitch returns nullptr for a switch without cases. When a function returns nullptr it adds nothing to the module.
  • R9. Every function passes llvm::verifyFunction, and results are exact for all i64 inputs, including INT64_MIN and INT64_MAX (watch the overflow in x − min).

The contract

// labs/ch11-lowering/include/lowerlab/Lowering.h  (provided; do not change)
namespace lowerlab {
enum class CondStrategy { Jumping, Value };
llvm::Function *emitCondition(llvm::Module &M, llvm::StringRef Name,
                              const Cond &C, CondStrategy S);
enum class SwitchStrategy { LLVMSwitch, JumpTable, BinarySearch, BitTests };
llvm::Function *emitSwitch(llvm::Module &M, llvm::StringRef Name,
                           const SwitchSpec &S, SwitchStrategy St);
}

Cond and SwitchSpec are the provided input trees of include/lowerlab/Inputs.h. The functions you create belong to M; any helper globals (the jump table) go into M too.

Input formats

cond := cond "||" cond | cond "&&" cond | "!" cond | "(" cond ")" | atom op atom
op   := "<" | "<=" | ">" | ">=" | "==" | "!="          (signed comparisons)
atom := a | b | … | h | integer

&& binds tighter than ||; both are left associative. A switch is a list of value:Dest pairs; destinations are letters numbered in order of first appearance:

bits3: 0:A 2:A 4:A 6:B 7:B 9:C 30:A 31:C 50:B 63:C

Here A = 0, B = 1, C = 2 and every other x returns 3. The input files (inputs/*.txt) hold one name: text item per line; # starts a comment.

Provided infrastructure

File What it gives you
include/lowerlab/Inputs.h, provided/Inputs.cpp the Cond and SwitchSpec trees, their parsers and printers, the reference evaluators, random generators
tools/Measure.cpp → ch11-lowerlab checks, IR shapes, timing under ORC LLJIT (--O2, --emit=<name>, --calls=N)
inputs/conditions.txt, inputs/switches.txt the measured inputs (also used by the tests)

Your code: src/ (every *.cpp there is compiled; start by deleting Stub.cpp).

What the tests check

Test Checks
ch11.Lab.ConditionsJumping R1 on the 10 inputs and 300 random conditions of 1–9 comparisons: verified IR, icmp count, branch count, no i1 logic, and the reference result on 256 random inputs in [−2, 2]⁸ each
ch11.Lab.ConditionsValue R2 on the same corpus: one block, no branches, icmp count, results
ch11.Lab.SwitchesLLVMSwitch, …JumpTable, …BinarySearch, …BitTests R3–R7 and R9 on the 6 inputs and 200 random switches (1–24 cases, spans 40, 200 and 100 000): nullptr exactly when the strategy does not apply (R5, R7), the shape of each strategy, and the reference result at every case ±2, 0, −1, INT64_MIN and INT64_MAX
ch11.Lab.SwitchWithoutCases R8
ch11.lab.measure-smoke, ch11.lab.measure-smoke-conditions ch11-lowerlab runs on both input files (checking every result)

Milestones

  1. Jumping code — ctest --test-dir build/<preset> -R Lab.ConditionsJumping.
  2. Boolean values — -R Lab.ConditionsValue.
  3. LLVMSwitch (ten lines) and BinarySearch — -R 'Lab.Switches(LLVMSwitch|BinarySearch)'.
  4. JumpTable and BitTests — -R Lab.Switch.
  5. Measure: build/<preset>/bin/ch11-lowerlab conditions, then … switches, then both again with --O2, and fill in the tables below. Look at one input with --emit=or-of-and and --emit=bits3 --O2.

Measurement

Timings are nanoseconds per call (minimum of 5 rounds of 2·10⁶ calls) on the author's machine: an x86-64 container, 4 cores, LLVM 23.1.2. Your numbers will differ; the ratios are what to compare, and they vary by a few tenths of a nanosecond from run to run.

Part A, as emitted (no IR optimization). "random" draws every variable from [−2, 2], so each branch of jumping code is close to a coin flip; "same" repeats one input, which the branch predictor learns.

condition leaves jumping: blocks / condbr value: blocks / condbr jumping ns (random / same) value ns (random / same)
and2 2 4 / 2 1 / 0 2.14 / 1.11 1.50 / 1.12
or-of-and 4 6 / 4 1 / 0 6.51 / 1.44 2.19 / 1.61
deep 6 8 / 6 1 / 0 7.28 / 1.72 2.48 / 1.83
guard8 8 10 / 8 1 / 0 5.62 / 1.94 2.53 / 2.47

With --O2, SimplifyCFG's FoldBranchToCommonDest and speculation turn the jumping code of every input into a single block: both strategies end up with the same shape (Lesson 11.2 §7).

Part B, as emitted. maxcmp is the longest chain of comparisons from the entry.

switch cases range switch table search (maxcmp) bits (maxcmp)
dense16 16 16 8.27 7.73 9.59 (5) 4.07 (9)
bits3 10 64 2.34 5.27 11.16 (5) 2.93 (4)
sparse 8 999 997 3.84 n/a 3.25 (4) n/a
chars 16 49 2.85 5.10 10.93 (5) 2.64 (4)

Fill in your own:

Input jumping (random) value (random) switch table search bits
…

Explain in two sentences each: why jumping code loses on random inputs and ties on repeated ones (misprediction cost, Lesson 11.2 §5); why the LLVM switch matches your best hand lowering on most inputs (the back end picks bit tests for bits3 and chars, a jump table for dense16, and a tree for sparse: Lesson 11.3 §7) but loses to bit tests on dense16 (an indirect jump through a table mispredicts on random inputs), and why your jump table is slower than LLVM's choice on bits3, chars and clustered (an indirect jump where LLVM uses bit tests or a short range check).

Hints

Hint 1 — where to start

Part A is Algorithm 11.2.2 of Lesson 11.2: one recursive function that takes the condition and two target blocks. ! swaps the targets; && creates one new block for its right operand. The value strategy is a post-order walk that returns an llvm::Value *.

Hint 2 — the key idea for part B

Every strategy but the LLVM switch starts from the sorted cases and the destination blocks; create one returning block per destination (and one for the default) first. The jump table and the bit tests share the range check: compute x − min with a wrapping sub and compare it unsigned against max − min. Negative results become huge unsigned numbers and fail the check, which is what makes one comparison enough (Lemma 11.3.3).

Hint 3 — a design sketch

For the table: a std::vector<llvm::Constant *> of max − min + 1 BlockAddress::get(F, block) entries initialized to the default block, then overwritten per case; a private constant GlobalVariable of type [N x ptr]; a GEP, a load and IRBuilder::CreateIndirectBr with every possible destination added. For the search: a recursive search(lo, hi) over the case index range that splits at the middle with icmp slt x, value[mid] and ends with an icmp eq per leaf. For the bit tests: one 64-bit mask per destination; test the masks with the most bits first.

Stretch goals

  • ★ Clusters. Implement LLVM's actual choice (Algorithm 11.3.6): partition the sorted cases into jump-table and bit-test clusters and search over the clusters. Compare with LLVMSwitch on clustered.
  • ★ Speculation safety. Add a division a / b as an atom. Which condition trees can the value strategy still compile, and which subtrees must stay jumping code? (Lesson 11.2 §4.)