Lab 21 · Guided MIR exploration: LLVM's selectors, frames and object files¶

Goal¶

You follow small LLVM IR functions through LLVM 23's code generator with llc and read the answers off its output: SelectionDAG on x86-64 and AArch64 (Lesson 21.5), GlobalISel stage by stage and FastISel's fallback (Lesson 21.6), legalization of wide and narrow types (Lesson 21.5), prologue/epilogue insertion (Lesson 21.9), and the object file with its relocations and branch relaxation (Lesson 21.10). There is no code to write: the deliverable is answers.yaml, graded automatically. This is exercise E5 in chapters/21-instruction-selection/exercises.md.

Requirements¶

R1. Fill in every key of answers.yaml (24 answers, tasks 1–9 below), replacing each TODO.
R2. Every answer is read off the output of the commands of its task, run with LLVM 23.1.2 (export PATH=/opt/llvm-23/bin:$PATH on Linux, or your LLVM 23 install on macOS). Do not guess: the grader accepts only the exact opcode, register, number or name.
R3. Write opcodes exactly as MIR prints them (MOV64mr, G_MUL), registers without % or $, sets as YAML lists ([a, b]), numbers as numbers.

The contract¶

answers.yaml: one key per question id, in any order. The questions, with their ids and exact wording, are in questions.yaml (answers hashed, so you cannot read them off). Formats: text answers are a single token, number answers an integer, set answers a YAML list whose order does not matter.

some-text-question: ADD64rr     # a single token
some-number-question: 16
some-set-question: [OPC1, OPC2] # order does not matter
still-open: TODO

python3 labs/ch21-mir/check.py [answers.yaml] grades a file and prints ok or WRONG with feedback per question; it exits with TODO(ch21) while every answer is still TODO.

Inputs¶

All in inputs/: store.ll (the running example a[i] = p[3] as store(ptr a, i64 i, ptr p)), wide.ll (add128, div128, add8, pop with llvm.ctpop.i64), sum.ll (a loop summing an array), call.ll (f(x, y) = g(x) + g(y) + x), fb.ll (an i128 multiply and a <4 x i32> add) and relax.s (x86-64 assembly: a jmp over 128 bytes of padding).

Tasks¶

Run the commands from the repository root. -o - prints to the terminal; add | less or redirect to a file.

Task 1 · SelectionDAG on x86-64 (Lesson 21.5 §7). Questions x86-store-opcode, x86-store-scale.

llc -O2 -mtriple=x86_64-linux-gnu -stop-after=finalize-isel labs/ch21-mir/inputs/store.ll -o -

Find the store; x86 memory operands are five MIR operands: base, scale, index, displacement, segment.

Task 2 · SelectionDAG on AArch64. Questions a64-load-imm, a64-store-opcode. The same command with -mtriple=aarch64-linux-gnu. Why is the load's immediate not 24?

Task 3 · GlobalISel, stage by stage (Lesson 21.6 §3). Questions gisel-irtranslator-op, gisel-legalizer-op, gisel-bank.

for p in irtranslator legalizer regbankselect instruction-select; do
  echo "== $p"
  llc -O2 -mtriple=aarch64-linux-gnu -global-isel -stop-after=$p labs/ch21-mir/inputs/store.ll -o - \
    | sed -n '/^body:/,$p'
done

Task 4 · GlobalISel on x86-64. Question gisel-x86-count: -mtriple=x86_64-linux-gnu -global-isel -stop-after=instruction-select on store.ll. Compare with task 1: which fold did SelectionDAG make that GlobalISel did not?

Task 5 · Legalization (Lesson 21.5 §3). Questions wide-add128, wide-div128, wide-add8-a64, wide-pop-a64.

llc -O2 -mtriple=x86_64-linux-gnu  -stop-after=finalize-isel labs/ch21-mir/inputs/wide.ll -o -
llc -O2 -mtriple=aarch64-linux-gnu -stop-after=finalize-isel labs/ch21-mir/inputs/wide.ll -o -

For each function, name the legalization action (Definition 21.5.6) that explains what you see; ./course drill legalization checks your reasoning.

Task 6 · Folding and SSA MIR. Questions sum-fold, sum-phis, sum-phi-pass.

llc -O2 -mtriple=x86_64-linux-gnu -stop-after=finalize-isel labs/ch21-mir/inputs/sum.ll -o -
llc -O2 -mtriple=x86_64-linux-gnu -stop-before=phi-node-elimination labs/ch21-mir/inputs/sum.ll -o - | grep -c PHI
llc -O2 -mtriple=x86_64-linux-gnu -stop-after=phi-node-elimination  labs/ch21-mir/inputs/sum.ll -o - | grep -c PHI

Task 7 · Prologue/epilogue insertion (Lesson 21.9 §3). Questions call-csr, call-stacksize, call-pseudos.

llc -O2 -mtriple=x86_64-linux-gnu -stop-before=prolog-epilog labs/ch21-mir/inputs/call.ll -o - > before.mir
llc -O2 -mtriple=x86_64-linux-gnu -stop-after=prolog-epilog  labs/ch21-mir/inputs/call.ll -o - > after.mir
diff before.mir after.mir

Task 8 · FastISel and its fallback (Lesson 21.6 §7). Question fastisel-fallback.

llc -O0 -mtriple=x86_64-linux-gnu -fast-isel-report-on-fallback labs/ch21-mir/inputs/fb.ll -o /dev/null

Task 9 · The object file (Lesson 21.10). Questions obj-call-reloc, obj-call-addend, obj-call-offset, obj-macho-reloc, obj-relax-size.

llc -O2 -mtriple=x86_64-linux-gnu -filetype=obj labs/ch21-mir/inputs/call.ll -o call.o
llvm-objdump -dr call.o
llvm-readelf -r call.o
llc -O2 -mtriple=arm64-apple-macos -filetype=obj labs/ch21-mir/inputs/call.ll -o call-macho.o
llvm-readobj -r call-macho.o
llvm-mc -triple=x86_64-linux-gnu -filetype=obj labs/ch21-mir/inputs/relax.s -o relax.o
llvm-objdump -d relax.o

Then change the padding in a copy of relax.s to 127 bytes and explain the difference with Algorithm 21.10.6.

What the tests check¶

Test	What it asserts
`ch21.lit` / `mir-answers.test`	`check.py` grades your `answers.yaml` against `questions.yaml`: all 24 answers must be correct
`ch21.lit` / `mir-facts.test`	the `llc` facts the answers rest on (the store opcodes, the GlobalISel opcodes, `__divti3`, the PHI count, the prologue, the fallbacks, the relocations and the relaxed `jmp`), so that a change of LLVM version is caught by this test rather than by your answers

Run ./course test 21, or python3 labs/ch21-mir/check.py while you work.

Milestones¶

Tasks 1, 2 and 5 after Lesson 21.5 (task 5 together with the legalization drill).
Task 6 after Lesson 21.5 (Ch 16 explains PHI elimination).
Tasks 3, 4 and 8 after Lesson 21.6.
Task 7 after Lesson 21.9, task 9 after Lesson 21.10.

Hints¶

Hint 1: reading MIR

Skip the YAML header until body:. Each instruction reads %dst:class = OPCODE operands; virtual registers are %N, physical ones $name. The MIR language reference (llvm/docs/MIRLangRef.md, entry MIR-LangRef in the chapter references) documents the syntax. Flags such as nsw or killed do not change the opcode.

Hint 2: finding the right pass name

llc -O2 -mtriple=… -debug-pass=Structure file.ll -o /dev/null lists the passes; -stop-before=NAME and -stop-after=NAME take the command-line names, which -print-after-all shows in its # *** IR Dump After … (name) *** headers.

Hint 3: relocations

llvm-objdump -dr prints each relocation under the instruction it patches; llvm-readelf -r prints the offset of the patched field, the type, the symbol and the addend. The field of a callq starts one byte after the instruction.

Stretch goals ★¶

Repeat task 1 with -O0 and with -fast-isel=false -O0 and explain the difference in the MIR.
Run task 3 for sum.ll and find where GlobalISel's G_PHI survives until instruction selection.
Produce the COFF object of call.ll (-mtriple=x86_64-pc-windows-msvc) and explain why its prologue differs from the ELF one.