Loading page…
Master the fundamental concepts of code generation 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 worksAfter initial codegen, target-specific passes clean up obvious waste. LLVM's machine instruction passes replace mul by 2 with shl, fold address modes, and delete redundant moves. GCC's peephole pass runs on the rtl stream.
Strength reduction: x * 8 becomes x << 3. Peephole: mov rax, X; mov rbx, rax becomes one move. Branch folding: eliminate jump to adjacent label. Instruction combining: lea for add + shift.
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 target-specific code optimizations on generated assembly. This exercise asks you to apply strength reduction and peephole rewrites that exploit x86 instruction patterns.
Write a peephole optimiser for x86-64 assembly: slide a small window over the instruction list and replace short patterns with cheaper, target-specific equivalents (xor zeroing, inc/dec, shifts, lea), repeating until nothing changes. (A real compiler also checks that the flags these rewrites clobber are dead; here you may assume they are.)
Intel-syntax assembly, one per line: labels NAME: or instructions OP, OP a, OP a, b. Everything after ; is a comment; blank lines are ignored. A register is one of rax rbx rcx rdx rsi rdi rbp rsp r8 … r15; an immediate is an integer literal.
| # | Name | Pattern | Replacement |
|---|---|---|---|
| 1 | self-move | mov R, R | (delete) |
| 2 | identity | add R, 0 · sub R, 0 · imul R, 1 | (delete) |
| 3 | reload | mov A, B then mov B, A | keep the first, delete the second |
| 4 | jump-to-next | jmp L then L: | delete the jmp |
| 5 | zero-idiom | mov R, 0 | xor R, R |
| 6 | inc-dec | add R, 1 / sub R, 1 | inc R / dec R |
| 7 | mul-to-shift | imul R, 2^k (k ≥ 1) | shl R, k |
| 8 | lea | mov R1, R2 then add R1, R3 (all registers, R1 ≠ R2, R1 ≠ R3) | lea R1, [R2+R3] |
| 9 | lea | mov R1, R2 then add R1, IMM (R1 ≠ R2) | lea R1, [R2+IMM] |
R is a register; A, B are any operands.
A pass walks the list from the top. At each position it tries the rules in the order above and applies the first one that matches (two-instruction rules look at this instruction and the next). It then moves on to the next position: after a deletion, that is whatever instruction now occupies this spot, and after a rewrite, the instruction after the rewritten one(s). Passes repeat until one makes no change (this lets mov rax, rax disappearing expose a new pair, for example).
The optimised code (labels flush left, instructions indented 4 spaces, operands separated by , ), then:
cLoading…
Input:
cLoading…
Output:
cLoading…
lea rules count as lea).Hidden tests cover self-moves that expose a reload pair, identities, sub … 1, non-power-of-two multiplies (unchanged), lea with an immediate, and code with nothing to optimise.