Implement Common Subexpression Elimination (CSE)

Reuse Redundant Computations

CSE 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.

Available Expressions

Track expressions computed and still valid (operands unchanged). On duplicate t2 = a + b when t1 = a + b is available, replace with t2 = t1.

cCopy
Loading…

• Memory loads need alias analysis to CSE safely
• Kill available expr when operand redefined
• Global CSE uses dominator-based placement (PRE)
• Local CSE within one block is simpler

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 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.