CompilersOptimizationsMedium

Dead Code Elimination

Master the fundamental concepts of optimizations through this focused micro-challenge.

~45 minutes Optimizations Ready to learn

Topic Overview

Remove Unused Computations

Dead code elimination (DCE) deletes instructions whose results are never used and branches that can never execute. LLVM's DCE and SCCP passes run constantly. Without DCE, folded if (0) blocks and temp chains clutter the output.

Liveness-Based Removal

Mark instructions needed if they have side effects (store, call, return) or feed a needed instruction. Iterate backward: unmarked instructions are dead and deletable.

c
Loading…

Pure arithmetic with unused results is dead
Dead blocks after constant-folded branches go away
Must preserve observable side effects
Aggressive DCE pairs with SSA (single-use chains)

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 dead code elimination on your IR. This exercise asks you to compute liveness and delete instructions and basic blocks that do not contribute to observable program behavior.

Implementation Task

Your Task

Implement dead code elimination: remove code that can never run and assignments whose values are never used, repeating until nothing more can be removed, and report every deletion with its reason.

Input

One statement per line; indentation is ignored.

Line	Meaning
`x = EXPR`	assignment (`EXPR`: names, integers, `+ - * /`, parentheses: no side effects)
`print EXPR` / `return EXPR`	uses its operands; `return` ends the enclosing block
`if (COND) {` … `}`	a block that runs when `COND` is non-zero; `COND` is an expression

Passes (repeat all three, in order, until a round removes nothing)

Unreachable code: inside a block (or at top level), every statement after a return is removed: reason unreachable. A whole if block counts as one statement (its braces and contents go together).
Constant conditions: if (N) { where N is an integer literal: if N is 0, remove the whole block (reason constant-false for every line in it, including the braces); otherwise keep the contents and remove only the if line and its closing } (reason constant-true).
Dead stores: an assignment x = … is dead if x is not live right after it. Liveness is computed backward: nothing is live at the end of the program; print/return and assignment right-hand sides use names; an if block may or may not run, so what is live before it is the union of what is live after it and what is live at the start of its body, plus the names in its condition. Remove every dead store (reason dead-store).

Output

The remaining program, statements indented 2 spaces per block level, then:

c
Loading…

sorted by original line number, with the original text trimmed (removed: none if nothing was removed). Finish with kept=K removed=R rounds=N, where N counts rounds including the final one that removed nothing.

Example

Input:

c
Loading…

Output:

c
Loading…

b = a + 2 only dies because pass 2 already deleted the if (0) block that read it; the same backward walk then finds a = 1 dead, since b no longer needs it. Round 2 removes nothing, so the program is final.

Requirements

Represent the program as a tree of statements (so a block can be removed or unwrapped as a unit) that remembers each statement's source line.
A backward liveness walk that handles if blocks as described.

Hidden tests cover a return inside an if (code after the block stays), if (1) unwrapping, stores that are only dead after other removals, and a program where nothing is dead.