Implement Loop Optimizations

Topic Overview

Loops Are Hot Optimization Targets

Most execution time sits in loops. LLVM's loop vectorizer, LICM, and induction variable strength reduction target loop nests. GCC's -O3 unrolls and vectorizes inner loops. Recognizing loop headers and induction variables is the first step.

LICM and Strength Reduction

Loop-Invariant Code Motion hoists t = a + b outside the loop if a and b do not change per iteration. Strength reduction replaces i * 4 with additive induction ptr += 4.

cCopy
Loading…

• Loop header: target of back edge
• Induction variable increases by constant each iter
• Invariant test: operands defined outside loop body
• Unrolling duplicates body to reduce branch overhead

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement loop optimizations including invariant code motion. This exercise asks you to detect loops in your CFG and hoist or rewrite computations that do not change per iteration.

Your Task

Optimise a loop: find the computations that give the same result on every iteration and hoist them out (loop-invariant code motion), then identify the loop's induction variables: the counters that strength reduction and vectorisation build on.

Input

TAC (x = a, x = a OP b, L:, goto L, if a goto L, ifFalse a goto L, print a, return a) containing one loop. The loop runs from a label L: to the last jump in the program that targets L (a backward jump). The input guarantees that this final back-edge is the loop's only exit, so the body always runs at least once.

Invariant instructions

Repeat until nothing changes: an assignment in the loop is invariant if each operand is a literal, a variable with no definition inside the loop, or a variable with exactly one definition inside the loop that is itself invariant.

Hoisting (repeat until nothing changes)

An invariant instruction x = … is hoisted if all of these hold:

1. x is assigned exactly once in the loop;
2. no instruction of the loop that has not been hoisted uses x before it (otherwise the loop would read last iteration's value);
3. it cannot fault: / and % are only hoisted when the divisor is a non-zero literal;
4. every variable operand defined inside the loop has already been hoisted.

Hoisted instructions are placed, in their original order, immediately before the loop label.

Induction variables

• Basic: a variable i with exactly one definition in the loop, of the form i = i + s or i = i - s, where the step s is a literal or a loop-invariant value (not defined in the loop, or hoisted). Printed as i (+s) / i (-s).
• Derived: a non-hoisted instruction j = i * c, j = c * i, j = i + c or j = c + i with i basic, c a literal, and j assigned once in the loop and not itself basic.

Output

The transformed code (labels flush left, instructions indented 4 spaces), then:

cCopy
Loading…

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

s = s + t4 looks like a counter, but it is not an induction variable: its step t4 changes on every iteration.

Requirements

1. Identify the loop, then compute invariance and hoisting as separate fixpoint loops.
2. Keep hoisted instructions' relative order so dependencies (t1 before t2) stay correct.

Hidden tests cover a variable assigned twice in the loop (never hoisted), a loop-carried read before the definition, a division that may fault, a chain of invariants, and an induction variable with an invariant step.