Loading page…
Master the fundamental concepts of optimizations through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksPeephole optimization slides a small window over instructions and replaces matching patterns with cheaper equivalents. GCC's peephole2 pass and LLVM's machine peephole delete mov r, r, fuse compare-branch, and swap redundant loads.
jmp L; L: eliminates the jump. add r, 0 deletes the add. mov r1, X; mov r2, r1 may become one move if safe.
asmLoading…
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.
You will implement peephole optimizations on your instruction list. This exercise asks you to define local patterns and rewrite sequences that are redundant or substitutable with fewer instructions.
Write a peephole optimiser for three-address code: small local rewrites (algebraic identities, strength reduction, constant folding and jump clean-ups) applied repeatedly until the code stops changing.
TAC, one instruction per line: x = a, x = a OP b (OP: + - * / <<), L:, goto L, if a goto L, ifFalse a goto L, print a, return a. Operands are names or integer literals (possibly negative).
| # | Name | Pattern | Result |
|---|---|---|---|
| 1 | self-copy | x = x | delete |
| 2 | fold | x = N OP M (both literals; not / by 0) | x = RESULT (64-bit, / truncates) |
| 3 | identity | x = a + 0, x = 0 + a, x = a - 0, x = a * 1, x = 1 * a, x = a / 1, x = a << 0 | x = a |
| 4 | annihilate | x = a * 0, x = 0 * a, x = a - a (same name) | x = 0 |
| 5 | strength | x = a * 2^k or x = 2^k * a (k ≥ 1, a a name) | x = a << k |
| 6 | jump-chain | goto L, if a goto L or ifFalse a goto L, where the first non-label instruction after L: is goto M (M ≠ L) | retarget the jump to M |
| 7 | jump-to-next | goto L when the next instructions up to the first non-label include L: | delete the goto |
| 8 | dead-after-goto | an instruction right after goto that is not a label | delete it |
A pass walks the list from the top; at each position it applies the first rule that matches. After a deletion the next position is whatever now occupies the spot; after a rewrite it moves on. Passes repeat until one changes nothing.
The optimised code (labels flush left, instructions indented 4 spaces), then before=N after=M and applied: NAME=COUNT ... in table order (or applied: none).
Input:
cLoading…
Output:
cLoading…
{label?, op, dst, a, binop, b, target}; rules match on fields.Hidden tests cover every identity form, a - a, negative literals in folding, conditional jumps through a chain of gotos, and code with nothing to optimise.