Compilers: Live variables

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

Example 1 · Input
8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:
live at exit:
Expected output
B1 in: - | out: i
B2 in: i | out: i
B3 in: i | out: i
B4 in: - | out: -
Example 2 · Input
3
a = x + 1
b = a * y
print b
live at exit: a
Expected output
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])}")

Lesson: Basic blocks, control-flow graphs and liveness →