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 worksCSE eliminates duplicate computations of the same expression in a basic block or extended region. LLVM's GVN pass and GCC's PRE track available expressions. If a + b appears twice with the same live operands, the second becomes a copy of the first's temp.
Track expressions computed and still valid (operands unchanged). On duplicate t2 = a + b when t1 = a + b is available, replace with t2 = t1.
cLoading…
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 common subexpression elimination on your IR. This exercise asks you to track available expressions per block and replace redundant instructions with copies of prior results.
Eliminate common subexpressions within a basic block using local value numbering (LVN): give every computed value a number, recognise when an expression computes a value that already exists, and replace the recomputation with a copy: as long as some variable still holds that value.
Straight-line TAC (one basic block): x = a, x = a OP b (OP: + - * / < ==), print a, return a. Operands are names or integer literals.
1, 2, 3, … in order of need.x = a: x now holds VN(a). The instruction is kept as is.x = a OP b: form the key (OP, VN(a), VN(b)); for the commutative operators + * == put the smaller number first. If the key was seen before and some variable currently holds its value, rewrite the instruction to x = HOLDER, where HOLDER is the variable that received that value number earliest among those still holding it. Otherwise give the key a new value number. Either way, x now holds the key's value number.x means x no longer holds its previous value, so it can no longer be used as a holder for it.print/return just use their operand.The rewritten block, one instruction per line, then eliminated=N: the number of expressions replaced by copies.
Input:
cLoading…
Output:
cLoading…
b + a matches a + b because + is commutative. After a = 7, a + b is a new value, so t4 must be recomputed. t2 * c has the same value numbers as t1 * c (t2 holds t1's value), so it reuses t3.
Hidden tests cover non-commutative operators (a - b vs b - a), a holder being overwritten while another variable still holds the value, literals, and a block with nothing to eliminate.