Lab 17 ★ · Lazy code motion on three-address code¶

Chapter: 17 · SSA-Based Scalar Optimizations · Lessons: 17.6 (Algorithm 17.6.6), with the dataflow of Lesson 14.3 · Time: 6–10 hours · Tests: ./course test 17 (label ch17, suite ch17.lab: lcm-sets.test, lcm-transform.test) · Optional (★)

Goal¶

Implement Knoop–Rüthing–Steffen lazy code motion in Drechsler and Stadel's edge form (Definition 17.6.5, Algorithm 17.6.6) on Chapter 8's three-address code. You compute the four bit-vector problems (availability, anticipability, earliest placement, later placement), print them in a fixed format, and then rewrite the program. The rewritten program must return the same value, and each expression must be evaluated exactly as often as LCM predicts: never more than before on any path (Theorem 17.6.13), and fewer times wherever it was partially redundant. The expressions are lexical (add a, b is one expression wherever it appears), as in the lesson. This is the classic form that GCC's RTL PRE uses (lcm.cc).

Requirements¶

Blocks and edges. Basic blocks are found by the leaders algorithm: - the first instruction is a leader; - so is every jump target; - so is every instruction after a goto, if, ifz or return.

Blocks are numbered B0, B1, … in listing order. The successors of a block are, in this order, its jump target (for goto, if, ifz) and then the next block (for anything but goto and return), each listed once. The edges are listed per block in block order, and per block in successor order.

Candidate expressions. A binary instruction x = op a, b with op in add sub mul lt le gt ge eq ne and at least one variable operand is an evaluation of the expression op a, b, written exactly like that: operator, space, a, comma, space, b. The universe is the set of distinct expressions, in order of first occurrence in the listing. An assignment to v (any instruction with destination v) kills every expression with operand v.

R0 (entry). If the entry block B0 has predecessors (a jump back to the first instruction), return the error the entry block has predecessors.
R1 (L1, local sets). Per block, with EaC3's names:
UEEXPR: evaluated before any operand is assigned in the block;
DEEXPR: evaluated with no later assignment to an operand in the block;
EXPRKILL: some operand is assigned in the block.

An instruction a = add a, 1 evaluates add a, 1 (upward exposed) and then kills it (not downward exposed). - R2 (L2, global sets). Solve these to their maximal fixed points by round-robin iteration, starting from the universe (entry and exit boundaries as given): - \(\mathrm{AVIN}(B_0) = \emptyset\) and \(\mathrm{AVIN}(b) = \bigcap_{p \in \mathrm{preds}(b)} \mathrm{AVOUT}(p)\) (\(\emptyset\) for any other block without predecessors); - \(\mathrm{AVOUT}(b) = \mathrm{DEEXPR}(b) \cup (\mathrm{AVIN}(b) - \mathrm{EXPRKILL}(b))\); - \(\mathrm{ANTOUT}(b) = \bigcap_{s \in \mathrm{succs}(b)} \mathrm{ANTIN}(s)\) (\(\emptyset\) for blocks without successors); - \(\mathrm{ANTIN}(b) = \mathrm{UEEXPR}(b) \cup (\mathrm{ANTOUT}(b) - \mathrm{EXPRKILL}(b))\). - R3 (L3, placement). - \(\mathrm{EARLIEST}(i, j) = \mathrm{ANTIN}(j) - \mathrm{AVOUT}(i)\), further intersected with \(\mathrm{EXPRKILL}(i) \cup \overline{\mathrm{ANTOUT}(i)}\) when \(i \neq B_0\). - \(\mathrm{LATERIN}(B_0) = \emptyset\), and \(\mathrm{LATERIN}(j) = \bigcap_{i \in \mathrm{preds}(j)} \mathrm{LATER}(i, j)\) (\(\emptyset\) for any other block without predecessors). - \(\mathrm{LATER}(i, j) = \mathrm{EARLIEST}(i, j) \cup (\mathrm{LATERIN}(i) - \mathrm{UEEXPR}(i))\), starting from the universe. - \(\mathrm{INSERT}(i, j) = \mathrm{LATER}(i, j) - \mathrm{LATERIN}(j)\). - \(\mathrm{DELETE}(b) = \mathrm{UEEXPR}(b) - \mathrm{LATERIN}(b)\) for \(b \neq B_0\), and \(\emptyset\) for \(B_0\).

lcmReport prints all of them in the --sets format. - R4 (L4, transformation). lazyCodeMotion returns a new listing in which: - T1. It is a valid TAC listing: the reader accepts it, labels are unique, and it ends in goto or return. - T2. It returns the same value as the original. - T3. For each candidate expression, the number of evaluations in the run equals the original number, minus one for each visit to a block \(b\) with the expression in \(\mathrm{DELETE}(b)\), plus one for each traversal of an edge \((i, j)\) with the expression in \(\mathrm{INSERT}(i, j)\). This is exactly LCM's placement. - T4. No new kinds of computation: every op a, b in the output occurs in the input. New temporaries and copies are allowed, and so are new labels and gotos for split edges.

The usual rewrite gives each moved expression \(e\) a fresh temporary \(h_e\). Every remaining evaluation of \(e\) also writes \(h_e\). The upward-exposed evaluation in a block with \(e \in \mathrm{DELETE}\) becomes a copy from \(h_e\). An insertion on edge \((i, j)\) goes to the start of \(j\) if \(j\) has one predecessor, to the end of \(i\) (before its jump) if \(i\) has one successor, and otherwise into a new block on the split edge. - Performance. Each set is a bit vector over the universe, and each round of round-robin iteration is \(O((n + e) \cdot \lvert U \rvert / w)\). The 40 random programs of the tests (8 blocks each) take well under a second in total. There is no timing test.

The contract¶

// labs/ch17-lcm/include/lab17lcm/LCM.h  (provided; do not change)
namespace lab17lcm {
/// L1-L3: the `--sets` report. Error (R0): "the entry block has predecessors".
std::expected<std::string, std::string> lcmReport(const irforms::tac::Listing &L);
/// L4: L after lazy code motion (T1-T4).
std::expected<irforms::tac::Listing, std::string> lazyCodeMotion(const irforms::tac::Listing &L);
}

irforms::tac::Listing is Chapter 8's TAC representation (labs/ch08-forms/include/irforms/Forms.h): a vector of instructions with kind, destination, operator, operands, jump target and the labels attached to the instruction.

Input and output formats¶

Input: the tac form of Lab 8.L1: one instruction per line (x = a, x = OP a, b, x = neg a, x = not a, goto L, if a goto L, ifz a goto L, return a, L:), with # comments. Variables start at 0. The listing ends in goto or return.

ch17-lcm --sets <file.tac> prints lcmReport. Every set prints as {e1; e2} in universe order ({} when empty):

exprs: {add a, b; add x, y}
block B0: ANTIN={} ANTOUT={add a, b} AVIN={} AVOUT={} LATERIN={} DELETE={}
block B1: ANTIN={add a, b} ANTOUT={add a, b} AVIN={} AVOUT={add a, b} LATERIN={add a, b} DELETE={}
block B2: ANTIN={add a, b} ANTOUT={add a, b} AVIN={} AVOUT={} LATERIN={add a, b} DELETE={}
block B3: ANTIN={add a, b} ANTOUT={} AVIN={} AVOUT={add a, b; add x, y} LATERIN={} DELETE={add a, b}
edge B0->B2: EARLIEST={add a, b} LATER={add a, b} INSERT={}
edge B0->B1: EARLIEST={add a, b} LATER={add a, b} INSERT={}
edge B1->B3: EARLIEST={} LATER={} INSERT={}
edge B2->B3: EARLIEST={} LATER={add a, b} INSERT={add a, b}

(inputs/diamond.tac: B0 ends in ifz p goto R, so its successors are R = B2 first, then B1.)

ch17-lcm --transform <file.tac> prints the new listing in the tac form. Layout and names are free (T1–T4 are checked by running it). The reference solution's output for inputs/diamond.tac:

tac
  a = 3
  b = 4
  p = 1
  ifz p goto R
  lcm.0 = add a, b
  x = lcm.0
  goto J
R:
  x = 0
  lcm.0 = add a, b
J:
  y = lcm.0
  z = add x, y
  return z

Provided infrastructure¶

File	What it gives you
`include/lab17lcm/LCM.h`	the contract
`labs/ch08-forms` (`pebble_ch08_infra`)	the TAC reader, printer and interpreter (`irforms/Forms.h`)
`tools/LcmMain.cpp`	`ch17-lcm --sets` / `--transform`
`tools/lcm_oracle.py`	`sets <file>` (the expected `--sets` output), `check <orig> <new>` (T1–T4, and a summary line `ok: value V; candidate evaluations N -> M (saved K)`), `random --seed S [--blocks N]` (random terminating programs). It uses the course's reference implementation in `tools/course/lib/scalaropt.py`, the same code as the drill `lcm-sets`
`inputs/*.tac`	`diamond` (the classic partial redundancy), `while` (top-tested loop: nothing to hoist), `dowhile` (rotated loop: hoisted), `critical` (insertion on a critical edge), `kill` (an operand changes: nothing moves), `running` (Lesson 14.3's running example, blocks A–F)
`src/Stub.cpp`	the two contract functions, stopping with `TODO(ch17)`

What the tests check¶

Test	Checks
`ch17.lab` `lcm-sets.test`	`--sets` equals the oracle on the six inputs, plus FileCheck lines for `diamond` (R1–R3); `--sets` equals the oracle on 40 random programs (`Inputs/lcm_random.py --sets`); the error of R0 on a listing whose first instruction is a loop header
`ch17.lab` `lcm-transform.test`	`--transform` passes `check` (T1–T4) on the six inputs, with evaluation counts `diamond` 3 → 2, `dowhile` 21 → 17, `while` 21 → 21, `running` 24 → 17 (value 35); and on 40 random programs (`Inputs/lcm_random.py --transform`)

Milestones¶

Blocks, edges and the universe: print exprs: and the block lines with only the local sets, and compare by eye with Lesson 17.6 §3.
L1–L3: ch17-lcm --sets labs/ch17-lcm/inputs/diamond.tac | diff - <(python3 labs/ch17-lcm/tools/lcm_oracle.py sets labs/ch17-lcm/inputs/diamond.tac), then all six inputs.
L4: python3 labs/ch17-lcm/tools/lcm_oracle.py check labs/ch17-lcm/inputs/diamond.tac <(ch17-lcm --transform labs/ch17-lcm/inputs/diamond.tac), then ctest --test-dir build/<preset> -R ch17.lab.

Hints¶

Hint 1 — where to start

Lesson 17.6 §3 computes every set of diamond and running by hand, and ./course drill lcm-sets --solution prints the sets for random CFGs in the same order. Build the blocks first and print them. Most early mismatches with the oracle come from successor order (jump target first) or from treating a constant-only instruction such as c = add 1, 2 as a candidate.

Hint 2 — the key idea

Availability and anticipability are Chapter 14's must-problems: start from the universe and intersect over the edges.
EARLIEST is where the expression becomes anticipable without being available, and where it could not have gone earlier: either the source block kills it, or the expression is not anticipable at the source's exit.
LATER pushes each insertion down along paths until an upward-exposed use or a join forces it. The insertion lands where LATER stops, which is where it is not LATERIN at the target.

Hint 3 — a design sketch

Use std::vector<bool> bit vectors indexed by expression id, a block table (first and last instruction, successors, predecessors), and maps from edges to sets.
Rewrite in one pass over the blocks: the insertions at the start, the instructions with their deletions turned into copies, and the insertions at the end before the jump. Emit new blocks for split edges: a fall-through split goes right after its source, and a jump split goes at the end with a goto to the old target, while the source's jump is retargeted to the new label.

Bugs the tests catch most often: - deleting a second evaluation in the same block (only the upward-exposed one is in DELETE); - forgetting to write \(h_e\) at the evaluations that stay, so a later copy reads 0; - inserting on a critical edge at the end of the source, which adds evaluations to the other successor's path (T3).

Stretch goals ★¶

Print LCM's result as a table of dynamic evaluations per expression, and compare with Morel–Renvoise (Algorithm 17.6.3) on the same inputs: find an input where MR moves less (Proposition 17.6.15).
Add isolated insertions (Definition 17.6.4) to avoid temporaries whose only use is in the same block, and measure the copies saved.