Compilers: A local optimizer

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 = a or x = a op b with op one of + - *; each variable is assigned once. Forward, for each instruction: replace operands that are known constants or copies; fold two numbers; apply x+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

Example 1 · Input
6
a = x * 1
b = a + y
c = y + x
d = b - c
e = d * z
f = 2 * 3
live: e f
Expected output
e = 0
f = 6
before 6, after 2
Example 2 · Input
5
t1 = a + b
t2 = t1 * 4
t3 = a + b
t4 = t3 * 4
s = t2 + t4
live: s
Expected output
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)}")

Lesson: Optimizing intermediate code →