Compilers: Fold and propagate constants

Apply the first two optimizations to a block of three-address code.

What to build

A program that performs constant propagation and constant folding on a basic block.

Requirements

  • Instructions are x = a or x = a op b with op one of + - *; operands are names or whole numbers (possibly negative); each variable is assigned at most once.
  • Replace every use of a variable known to hold a number by that number, and replace every operation on two numbers by its result. Print every instruction after the change, in order.

Input

Line 1: n. Then n instructions.

Output

n lines.

Constraints

n ≤ 50; numbers stay below 10¹⁸ in size.

Example

Input:

3
a = 2 + 3
b = a * 4
c = b - x

Output:

a = 5
b = 20
c = 20 - x

Why it works

A forward pass knows every constant assigned so far, so each instruction can use them, and each folded result can feed the next instruction.

Examples

Example 1 · Input
3
a = 2 + 3
b = a * 4
c = b - x
Expected output
a = 5
b = 20
c = 20 - x
Example 2 · Input
2
p = q * 2
r = p + 1
Expected output
p = q * 2
r = p + 1

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

Hints

Hint 1

Keep a dictionary of variables known to be numbers; replace operands found in it before looking at the instruction.

Hint 2

If both operands are numbers, compute the result; if the result is a number, record the variable as known.

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()


known = {}
for _ in range(int(input())):
    dest, expr = input().split(" = ")
    parts = [known.get(p, p) for p in expr.split()]
    if len(parts) == 3 and is_number(parts[0]) and is_number(parts[2]):
        parts = [str(FOLD[parts[1]](int(parts[0]), int(parts[2])))]
    if len(parts) == 1 and is_number(parts[0]):
        known[dest] = parts[0]
    print(dest, "=", " ".join(parts))

Lesson: Optimizing intermediate code →