Combine all of the lesson's optimizations into one optimizer.
What to build
A program that optimizes a basic block with propagation, folding, identities, common subexpression elimination and dead code elimination.
Requirements
- Instructions are
x = aorx = a op bwith op one of+ - *; each variable is assigned once. Forward, for each instruction: replace operands that are known constants or copies; fold two numbers; applyx+0, 0+x, x-0, x*1, 1*x → x,x*0, 0*x, x-x → 0; otherwise reuse an earlier variable holding the same expression (+and*in either order). An instruction that becomes a single value makes its variable a known constant or copy. - Then remove dead code backwards from the live variables. Print the remaining instructions, then
before N, after M.
Input
Line 1: n. Then n instructions. Last line: live: followed by names.
Output
The optimized block, then the counts.
Constraints
n ≤ 50.
Example
Input:
6
a = x * 1
b = a + y
c = y + x
d = b - c
e = d * z
f = 2 * 3
live: e f
Output:
e = 0
f = 6
before 6, after 2
Why it works
Each rewrite turns work into known values, which lets the next rewrite fire, and the backward pass then removes everything those values made unnecessary.
Examples
6 a = x * 1 b = a + y c = y + x d = b - c e = d * z f = 2 * 3 live: e f
e = 0 f = 6 before 6, after 2
5 t1 = a + b t2 = t1 * 4 t3 = a + b t4 = t3 * 4 s = t2 + t4 live: s
t1 = a + b t2 = t1 * 4 s = t2 + t2 before 5, after 3
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Forward pass: substitute known values, then try folding and the identities, then look the expression up among those already computed.
Hint 2
For `+` and `*`, store and look up the expression with its two operands sorted, so that `y + x` matches `x + y`.
Solution
Show one correct solution (try it yourself first)
FOLD = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b}
def is_number(text):
return text.lstrip("-").isdigit()
def simplify(a, op, b):
if is_number(a) and is_number(b):
return str(FOLD[op](int(a), int(b)))
if op == "*" and "0" in (a, b):
return "0"
if (op in ("+", "-") and b == "0") or (op == "*" and b == "1"):
return a
if (op == "+" and a == "0") or (op == "*" and a == "1"):
return b
if op == "-" and a == b:
return "0"
return None
def key(a, op, b):
return (op, *sorted((a, b))) if op in ("+", "*") else (op, a, b)
lines = [input() for _ in range(int(input()))]
live = set(input().split(":", 1)[1].split())
known, available, block = {}, {}, []
for line in lines:
dest, expr = line.split(" = ")
parts = [known.get(p, p) for p in expr.split()]
if len(parts) == 3:
single = simplify(*parts) or available.get(key(*parts))
if single is None:
available[key(*parts)] = dest
else:
parts = [single]
if len(parts) == 1:
known[dest] = parts[0]
block.append(f"{dest} = {' '.join(parts)}")
kept = []
for line in reversed(block):
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(f"before {len(lines)}, after {len(kept)}")