Skip to content

Lab 10.2 · An IR inspection and rewriting tool

Chapter: 10 · The LLVM C++ API · Lessons: 10.1, 10.2, 10.4, 10.7 · Time: 4–6 hours · Tests: ./course test 10 (labels ch10)

Goal

Write ch10-tool, a small command-line tool in the style of LLVM's own llvm-* utilities. It reads a textual .ll file and does one of three things:

  • --stats prints counts per function;
  • --def-use prints every value's def-use chain in a canonical order;
  • --rewrite-pow2 replaces multiplications, unsigned divisions and unsigned remainders by powers of two with shifts and masks, then prints the module.

You will practise loading IR with error handling, walking the ownership tree, following use lists, casting with dyn_cast, and rewriting while iterating without invalidating your iterator. The rewrite must also keep the program's meaning, and the tests run the program before and after under lli to check that.

Requirements

  • R1 (CLI and errors). Usage is ch10-tool --stats|--def-use|--rewrite-pow2 <file.ll>.
  • Wrong argument count or unknown mode: print a line containing usage: ch10-tool --stats|--def-use|--rewrite-pow2 <file.ll> to stderr and exit 2.
  • Unreadable file, parse error, or a module that fails verifyModule: print a diagnostic containing error: to stderr and exit 1.
  • Success: exit 0.
  • On failure, nothing goes to stdout.
  • R2 (--stats). Print exactly the format in "Output formats": one header line, then for every defined function in module order its block count, instruction count, phi count and call count (isa<CallBase>: call, invoke, callbr), followed by one line per opcode present (Instruction::getOpcodeName()), sorted by opcode name.
  • R3 (--def-use). For every defined function in module order, print its name, then one line per argument (in order) and per non-void instruction (in program order). Each line gives the value and its uses:
  • The value is printed as printAsOperand prints it without the type, so unnamed values appear as %0, %1, …
  • Each use is written <block>:<index>#<operand>, where <block> is the user's block as printAsOperand prints it, <index> is the user's 0-based position in that block, and <operand> is Use::getOperandNo().
  • Uses are sorted by (block position in the function, index, operand number). Do not print them in use-list order: that order is an implementation detail (Lesson 10.2).
  • R4 (--rewrite-pow2: what). In every defined function, rewrite every scalar integer instruction of these forms, where \(C = 2^k\) is a ConstantInt whose value is a power of two as an unsigned number:
  • mul X, C and mul C, X become shl X, k;
  • udiv X, C (divisor on the right only) becomes lshr X, k;
  • urem X, C becomes and X, C-1.

Everything else stays as it is, including vectors, sdiv/srem and non-power-of-two constants. - R5 (flags). mul nuw becomes shl nuw. mul nsw becomes shl nsw only when \(k < w - 1\) (\(w\) = bit width): multiplying by \(2^{w-1}\) is not the same as shifting by \(w-1\) under nsw: as a signed number the constant is \(-2^{w-1}\), so mul nsw %x, C is defined for \(x = 1\) while shl nsw 1, w-1 is poison (Ch 9, poison, Ch 13). udiv exact becomes lshr exact. - R6 (identity). The new instruction takes the old one's name (takeName) and debug location. All uses are redirected to it (RAUW), and the old instruction is erased. - R7 (output). Print the rewritten module to stdout with Module::print and a line rewrote <N> instruction(s) to stderr: instruction for \(N = 1\), instructions otherwise. The printed module must verify. - R8 (safety). Rewriting happens while iterating over the function. Your iteration must not touch an erased instruction; use make_early_inc_range (Lesson 10.1, Theorem on early increment) or collect first. The input tests/ch10/lit/tool-rewrite-iterate.ll has rewrites at the first and last position of blocks and in blocks that contain nothing else. - R9 (semantics). The rewritten program must behave exactly like the input. The tests run both under lli and compare stdout.

The contract

A black-box CLI (LABS.md): the lit tests run the executable and check its output. The provided tools/Main.cpp forwards argv to one function you implement:

// labs/ch10-irtool/include/irtool/Tool.h  (provided; do not change)
namespace irtool {
/// Runs `ch10-tool <Args...>`; returns the exit code (0, 1 or 2 as in R1).
int run(llvm::ArrayRef<llvm::StringRef> Args, llvm::raw_ostream &Out, llvm::raw_ostream &Err);
}

Output formats

For labs/ch10-irtool/inputs/small.ll:

$ ch10-tool --stats inputs/small.ll
functions: 2 defined, 1 declared
@f: blocks=3 instructions=9 phis=1 calls=1
  add: 1
  br: 2
  call: 1
  icmp: 1
  mul: 1
  phi: 1
  ret: 1
  sub: 1
@g: blocks=1 instructions=4 phis=0 calls=0
  ret: 1
  shl: 1
  store: 2

$ ch10-tool --def-use inputs/small.ll
@f
  %x: 2 uses: %entry:0#0 %entry:2#1
  %y: 1 use: %entry:0#1
  %a: 4 uses: %entry:1#0 %entry:1#1 %then:0#0 %join:1#1
  %b: 2 uses: %entry:2#0 %join:0#1
  %c: 1 use: %entry:3#0
  %0: 1 use: %join:0#0
  %p: 1 use: %join:1#0
  %q: 1 use: %join:2#0
@g
  %out: 2 uses: %0:1#1 %0:2#1
  %v: 2 uses: %0:0#0 %0:2#0
  %1: 1 use: %0:1#0

A value with no uses prints %v: 0 uses. Note 1 use (singular) versus 2 uses, and that a use line ends right after the last use (no trailing space). In @g the entry block is unnamed and gets slot %0, so the first unnamed instruction is %1.

For --rewrite-pow2, stdout is the whole module as Module::print writes it, and stderr is the summary line (see tests/ch10/lit/tool-rewrite.test for the exact expected IR).

Provided infrastructure

File What it gives you
include/irtool/Tool.h the contract
tools/Main.cpp main(), forwarding to irtool::run
inputs/small.ll, inputs/pow2.ll sample inputs (the tests use them)
src/Stub.cpp a stub that stops with TODO(ch10)

What the tests check

Test Checks
ch10.IrTool.ExitCodes R1 through irtool::run: 0 on success, 2 for four kinds of usage error (with usage: on stderr), 1 for a missing file and for a module that fails the verifier; nothing on stdout on failure
tests/ch10/lit/tool-errors.test R1 through the executable: usage message and error: diagnostics for a missing file, a parse error and Inputs/invalid.ll
tests/ch10/lit/tool-stats.test R2, whole output line by line (--match-full-lines)
tests/ch10/lit/tool-def-use.test, tool-def-use-unused.ll R3, whole output; values without uses, a value used twice by one instruction, void instructions omitted
tests/ch10/lit/tool-rewrite.test R4–R7 and R9 on inputs/pow2.ll: the summary line (14 rewrites), the verifier, the exact rewritten instructions including flags, untouched sdiv/udiv C, X/vector/non-power-of-two cases, and identical lli output before and after
tests/ch10/lit/tool-rewrite-iterate.ll R8 and R9: rewrites at block boundaries, across a loop and in a phi-carried chain; lli equivalence

Milestones

  1. Parse, verify and report errors (R1): ctest --test-dir build/<preset> -R 'ch10.IrTool'.
  2. --stats, then --def-use: ctest --test-dir build/<preset> -R ch10.lit (the stats and def-use tests go green first).
  3. --rewrite-pow2: the remaining lit tests.

Hints

Hint 1 — where to start

parseIRFile(Path, Diag, Ctx) returns nullptr on failure and fills an SMDiagnostic. SMDiagnostic::print(ProgName, Err) writes a message that already contains error:. A module can parse and still be invalid (a use before its definition), so call verifyModule too.

Hint 2 — the key idea

For --def-use, you need the position of each user before you can sort. Number every instruction once per function (block number, index) in a DenseMap<const Instruction *, …>, then walk V.uses() and sort by that key. ModuleSlotTracker makes repeated printAsOperand calls fast and consistent. For the rewrite, dyn_cast<BinaryOperator>, getOpcode(), and dyn_cast<ConstantInt> on each operand are all you need. Create the replacement before the old instruction (an iterator insert position), then RAUW, then erase.

Hint 3 — a design sketch

One function per mode plus a small pow2Exponent(Value *) -> optional<unsigned>. The rewrite loop is for (Instruction &I : make_early_inc_range(instructions(F))): the iterator already points past I when the body erases I. Common bugs the tests catch: printing uses in use-list order (reversed); keeping nsw for a shift by \(w-1\); rewriting udiv C, X (constant on the left); rewriting vector multiplications; forgetting takeName, which renames the value and breaks the FileCheck lines.

Stretch goals ★

  • Add --rewrite-pow2=signed: sdiv X, 2^k → ashr with the rounding fix-up (\(x + ((x \gg_s (w-1)) \gg_u (w-k))\)), and check it with lli on negative inputs.
  • Add --dot-def-use to print the def-use graph as Graphviz.