Compilers: Remove dead code

Delete the instructions whose results are never needed.

What to build

A program that performs dead code elimination on a basic block.

Requirements

  • Instructions are x = a, x = a op b or print a; operands are names or whole numbers. A variable may be assigned more than once. print instructions are always kept.
  • The last line lists the variables live at the end of the block. Print the kept instructions in their original order, then removed K.

Input

Line 1: n. Then n instructions. Last line: live: followed by names separated by spaces (possibly none).

Output

The kept instructions, then removed K.

Constraints

n ≤ 50.

Example

Input:

5
a = x + 1
b = a * 2
c = a - y
d = c + c
print b
live:

Output:

a = x + 1
b = a * 2
print b
removed 2

Why it works

Walking backwards, the live set holds exactly the values that some later instruction will read, so an assignment to anything else can go.

Examples

Example 1 · Input
5
a = x + 1
b = a * 2
c = a - y
d = c + c
print b
live:
Expected output
a = x + 1
b = a * 2
print b
removed 2
Example 2 · Input
4
t = x * x
t = y * y
u = t + 1
v = 5
live: u
Expected output
t = y * y
u = t + 1
removed 2

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Walk the block backwards, starting with the live set from the last line.

Hint 2

Keep an assignment only if its destination is live; then remove the destination from the live set and add the names it reads.

Solution

Show one correct solution (try it yourself first)
lines = [input() for _ in range(int(input()))]
live = set(input().split(":", 1)[1].split())
kept = []
for line in reversed(lines):
    if line.startswith("print "):
        kept.append(line)
        live |= {p for p in line.split()[1:] if p.isidentifier()}
        continue
    dest, expr = line.split(" = ")
    if dest in live:
        kept.append(line)
        live.discard(dest)
        live |= {p for p in expr.split() if p.isidentifier()}
for line in reversed(kept):
    print(line)
print("removed", len(lines) - len(kept))

Lesson: Optimizing intermediate code →