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 borprint a; operands are names or whole numbers. A variable may be assigned more than once.printinstructions 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))