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 = aorx = a op bwith 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))