Run the dataflow analysis that register allocators depend on.
What to build
A program that computes the live variables at the start and end of every basic block.
Requirements
- Blocks and edges as in the previous exercises. Instruction forms:
x = a,x = a op b,goto L,if a goto L,ifFalse a goto L,print a, and labels. Names are the operands that are not numbers. - The last input line lists the variables live at the exit. Print
Bk in: … | out: …for every block, names sorted,-for an empty set.
Input
Line 1: n. Then n lines of three-address code. Last line: live at exit: followed by names.
Output
One line per block.
Constraints
n ≤ 100.
Example
Input:
8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:
live at exit:
Output:
B1 in: - | out: i
B2 in: i | out: i
B3 in: i | out: i
B4 in: - | out: -
Why it works
A value is needed at a point if some path from there reads it before overwriting it, and the equations collect exactly that information, block by block, until it stops changing.
Examples
8 i = 0 L1: t1 = i < 3 ifFalse t1 goto L2 print i i = i + 1 goto L1 L2: live at exit:
B1 in: - | out: i B2 in: i | out: i B3 in: i | out: i B4 in: - | out: -
3 a = x + 1 b = a * y print b live at exit: a
B1 in: x y | out: a
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
For each block compute use (read before written in the block) and def (written in the block).
Hint 2
Start with empty sets and repeat live_in = use ∪ (live_out − def) over all blocks until nothing changes; live_out is the union of the successors' live_in, plus the exit set for blocks that reach the exit.
Solution
Show one correct solution (try it yourself first)
lines = [input().strip() for _ in range(int(input()))]
exit_live = set(input().split(":", 1)[1].split())
leaders = {0}
for i, line in enumerate(lines):
if line.endswith(":"):
leaders.add(i)
if line.split()[0] in ("goto", "if", "ifFalse") and i + 1 < len(lines):
leaders.add(i + 1)
starts = sorted(leaders) + [len(lines)]
count = len(starts) - 1
blocks = [lines[starts[k]:starts[k + 1]] for k in range(count)]
block_of = {line[:-1]: k for k in range(count) for line in blocks[k] if line.endswith(":")}
succ, uses, defs = [], [], []
for k, block in enumerate(blocks):
words = block[-1].split()
if words[0] == "goto":
succ.append({block_of[words[1]]})
elif words[0] in ("if", "ifFalse"):
succ.append({block_of[words[3]], k + 1})
else:
succ.append({k + 1})
used, defined = set(), set()
for line in block:
words = line.split()
if line.endswith(":") or words[0] == "goto":
continue
if words[0] in ("if", "ifFalse", "print"):
read, written = [words[1]], None
else:
read, written = words[2:], words[0]
used |= {w for w in read if w.isidentifier() and w not in defined}
if written:
defined.add(written)
uses.append(used)
defs.append(defined)
live_in = [set() for _ in range(count)]
live_out = [set() for _ in range(count)]
changed = True
while changed:
changed = False
for k in reversed(range(count)):
out = set()
for s in succ[k]:
out |= exit_live if s == count else live_in[s]
new = uses[k] | (out - defs[k])
if new != live_in[k] or out != live_out[k]:
live_in[k], live_out[k], changed = new, out, True
def show(names):
return " ".join(sorted(names)) or "-"
for k in range(count):
print(f"B{k + 1} in: {show(live_in[k])} | out: {show(live_out[k])}")