Skip to content

Lab 18 · Classic vs SSA-based induction variables, classic vs operator strength reduction, GCD vs Banerjee

Goal

Three comparisons, each between a classical technique you implement here and a technique you implement (or use) elsewhere:

  • Part A. Allen–Cocke–Kennedy induction-variable detection (Lesson 18.2, Algorithm 18.2.2) against your SSA/SCC-based pebble-iv (exercise E2) and LLVM's ScalarEvolution. What does each method find, and do they agree where they overlap?
  • Part B. Classic strength reduction (Lesson 18.4, Algorithm 18.4.2) against your pebble-osr (E3). Count the multiplications, loop instructions and header phis each leaves.
  • Part C. The GCD test and Banerjee's inequalities (Lesson 18.6, Theorems 18.6.5 and 18.6.8) against the exact answer, which the provided driver computes by enumerating every pair of iterations. How often does each test prove independence, and when is it sound but imprecise?

You write four functions (the contract below). The driver ch18-loops, the corpora and the comparison scripts are provided.

Requirements

Part A: classic induction variables

  • R1. Basic IVs. For a loop L in loop-simplify form, a header phi is a basic induction variable if its latch value is the phi plus or minus a chain of loop-invariant additions and subtractions (Definition 18.2.1). Record its start (the preheader value, as an affine combination of loop-invariant values) and its step.
  • R2. Derived IVs. An integer instruction whose innermost loop is L is a derived IV of basic IV i if it is j ± c, c ± j, c * j, j * c or j << k for a basic or derived IV j of the family of i and a loop-invariant c (a constant, an argument, or an instruction defined outside L); iterate to a fixed point in instruction order (Algorithm 18.2.2). Report Start and Step as affine combinations of loop-invariant values (Affine), Basic = the family's header phi.
  • R3. What classic detection must not report. Nothing outside the rules above: no polynomial, geometric, wrap-around, periodic or monotonic values, no sums of two families (i - j), no products of two IVs, nothing in an inner loop of L (those belong to the inner loop). findClassicIVs must not modify the IR. Every value you report must be a linear IV that pebble-iv (E2) reports with the same chain of recurrences.

Part B: classic strength reduction

  • R4. Transformation. strengthReduceClassic applies Algorithm 18.4.2 to every loop of F in loop-simplify form: for each derived IV c·i + d computed with a multiplication (or shl) by a loop-invariant value, create a new induction variable (a header phi with the preheader value c·i₀ + d and the increment c·s added in the latch) and make its uses inside L use it. Remove instructions that became dead. Process the latest-defined derived IVs first, so that an IV reduced for its only user is not reduced separately.
  • R5. Correctness. F still verifies, and every program of the corpus prints the same output under lli before and after (Theorem 18.4.12). Loop-invariant multiplications (i * m with i an IV of an outer loop) are not yours to move: that is LICM's job.
  • R6. Effect. After your pass, ch18-loops count shows no multiplication of a basic IV by an invariant left in @stride, @twice and @shifted, and at most one in @weighted (the remaining one, a[i - 1] * (i * w), multiplies by a loaded value, which is not loop-invariant).

Part C: dependence tests

  • R7. GCD test. gcdTest(P) implements Theorem 18.6.5 for every array dimension of problem P: false ("independent") iff for some dimension the gcd of all index coefficients of the write and the read does not divide the difference of their constants (with gcd 0: iff the constants differ).
  • R8. Banerjee's test. banerjeeTest(P, Dirs) implements Theorem 18.6.8 with Lemma 18.6.7's bounds for each loop's direction (<, =, >, *), dimension by dimension: false iff, for some dimension, 0 lies outside the sum of the per-loop bounds plus the constant difference; a direction that is impossible for its loop (< or > in a loop with a single iteration) makes the whole vector impossible.
  • R9. Soundness. Neither test may claim independence where a dependence exists: ch18-loops dep FILE --check prints UNSOUND and fails if the GCD test says independent while the exact answer has a direction, or if Banerjee excludes a direction that occurs.

All parts

  • Integers are 64-bit (int64_t); the corpus is small enough that no bound computation overflows.
  • No output to stdout from your functions (the driver's output is compared line by line).

The contract

include/lab18/Loops.h (read it; its comments are part of the spec):

Function Part Stub message
std::vector<ClassicIV> findClassicIVs(llvm::Loop &L, llvm::LoopInfo &LI) A TODO(ch18): A1 …
bool strengthReduceClassic(llvm::Function &F, llvm::LoopInfo &LI, llvm::DominatorTree &DT) B TODO(ch18): B1 …
bool gcdTest(const DepProblem &P) C TODO(ch18): C1 …
bool banerjeeTest(const DepProblem &P, std::string_view Dirs) C TODO(ch18): C2 …

Your code goes in src/ (any files; Stub.cpp is there only so that the project builds — replace it).

Input and output formats

ch18-loops ivs FILE.ll prints, per function and per loop in header order, the classic IVs in instruction order, in the print<pebble-iv> spelling (exercises.md, E2) plus the family:

classic-iv: function @linear
loop %for.cond (depth 1)
  %i.0: linear {0,+,1} (basic)
  %mul: linear {0,+,4} (derived from %i.0)

ch18-loops sr FILE.ll -o OUT.ll runs strengthReduceClassic on every function and writes the module. ch18-loops count FILE.ll prints @f: loop-insts=N muls=M header-phis=K per function (instructions inside loops, mul/shl inside loops, phis in loop headers).

.dep files (Part C): problem NAME, then one loop VAR LOWER UPPER line per loop (outermost first, inclusive bounds), then write A[...] and read A[...] with one bracket per dimension holding an affine expression of the loop variables (2*i + j - 1). # starts a comment. ch18-loops dep FILE.dep [--check] prints one line per problem and a summary:

shift1: gcd=dependent banerjee={<} exact={<}
summary: 67 problems; independent by gcd 4, by banerjee 11, exactly 16

banerjee lists the full direction vectors (one character per loop) for which your banerjeeTest returns true; exact lists the vectors that really occur (the driver enumerates all pairs of iterations).

Provided infrastructure

  • tools/Ch18Loops.cpp — the driver above (IR reading, printing, counting, the .dep reader and the exact answer by enumeration).
  • corpus/ivs.c, corpus/ivs.ll — 12 functions covering every sequence class of Definition 18.2.5; corpus/sr.c, corpus/sr.ll — 5 strength-reduction kernels and a main that prints their results; corpus/deps.dep — 67 dependence problems (textbook cases and problems from the dependence-test drill), corpus/edge.dep — 8 edge cases. provided/regen-corpus.sh regenerates the .ll files with clang 23.
  • provided/compare_ivs.py — runs your classic detector, print<pebble-iv> and opt -passes='print<scalar-evolution>' on a file and reports agreement. provided/deps_oracle.py — the course oracle's answer for a .dep file (the same code as ./course drill dependence-test).

What the tests check

Test Checks
classic-ivs.test ch18-loops ivs on corpus/ivs.ll prints exactly the expected classic IVs (R1–R3), including the misses listed in its header
ivs-compare.test every classic IV is reported by pebble-iv with the same CR, and pebble-iv agrees with ScalarEvolution wherever both are affine (R3; needs E2)
classic-sr.test lli output is unchanged after ch18-loops sr, and the multiplication counts of R6 hold (R4–R6)
deps.test ch18-loops dep --check reports no unsoundness, and every verdict equals the course oracle's (R7–R9), on corpus/deps.dep and on the edge cases of corpus/edge.dep (single-iteration loops, subscripts without a loop variable, constant subscripts)
classic-ivs-edge.ll the derived-IV rules the corpus does not exercise (c - j, j << k, a symbolic multiplier) and the must-not cases i - j and i * i (R2, R3)

All five run with ./course test 18 (label ch18, suite ch18.lab).

Milestones

  1. C1, C2 first: they are self-contained arithmetic. Run ch18-loops dep corpus/deps.dep --check and compare with provided/deps_oracle.py.
  2. A1: basic IVs, then derived IVs; compare ch18-loops ivs corpus/ivs.ll with opt -load-pass-plugin=… -passes='print<pebble-iv>' (if E2 is done) or with the table in Lesson 18.2 §3.
  3. B1: reduce @stride first (one derived IV), then the others; diff the lli output after each change.
  4. Fill in the measurement table below.

Measurement

Fill in (the reference solution's numbers are in Lesson 18.4 §3 and Lesson 18.2 §3; yours should match for Part C exactly and for Parts A–B up to the choices R2/R4 leave open):

Quantity Your result
Part A: IVs found on ivs.ll by classic detection / by pebble-iv (per class) / agreement with SCEV
Part B: loop-insts / muls / header-phis for each kernel: original, classic SR, pebble-osr, pebble-licm,pebble-osr
Part C: problems proven independent by GCD / by Banerjee / exactly independent

Then answer in one paragraph each: which IVs does classic detection miss, and why; why does @matrix keep a multiplication under classic SR and pebble-osr alone, but not after pebble-licm; which problems are independent although both GCD and Banerjee say "maybe", and what would prove them independent (Lesson 18.6's Omega section).

Hints

Hint 1 — Part C first

Write a helper for Lemma 18.6.7's four cases (*, =, <, >) with positive and negative parts \(t^+\), \(t^-\), and test it against brute force over a small box of \((x, y)\) before plugging it into banerjeeTest. The constant difference is Write.Const - Read.Const moved to the left side; test whether 0 lies in [Const + ΣLow, Const + ΣHigh].

Hint 2 — Part A without SSA tricks

A basic IV's latch value is a chain i → i + c1 → (i + c1) - c2 … ending at the phi: walk from the latch operand back through add/sub with one invariant operand until you reach the phi (or give up). For derived IVs, keep a map from instruction to (family, start, step) and sweep the loop's instructions in order until a sweep adds nothing.

Hint 3 — Part B's order and cleanup

Reduce the derived IVs in reverse definition order and keep a set of reduced values: if u = t + 3 is reduced first and t = 4 * i has no other user, t becomes dead and must not be reduced again. Build the new phi with IRBuilder in the header, its increment before the latch's terminator, and the start value in the preheader; finish with RecursivelyDeleteTriviallyDeadInstructions on the replaced instructions.

Stretch goals ★

  • Add the strong SIV test (Theorem 18.6.12) as a third column of dep and count how many "maybe" answers become exact.
  • Make Part B handle derived IVs of derived IVs with a symbolic multiplier and compare with pebble-osr on @matrix after pebble-licm.