Compilers: Build the control-flow graph

Connect the blocks into a graph and find code that can never run.

What to build

A program that builds the control-flow graph of three-address code and lists its unreachable blocks.

Requirements

  • Blocks as in the previous exercise. A block ending in goto L goes to L's block; one ending in if … goto L or ifFalse … goto L goes to L's block and to the next block; any other block goes to the next block, or to exit if it is the last.
  • Print Bk (lines a-b) -> S1 S2 … for each block, successors in order with exit last, then unreachable: and the blocks not reachable from B1, or none.

Input

Line 1: n. Then n lines of three-address code.

Output

One line per block, then the unreachable line.

Constraints

n ≤ 100; every jump's label exists.

Example

Input:

8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:

Output:

B1 (lines 1-1) -> B2
B2 (lines 2-4) -> B3 B4
B3 (lines 5-7) -> B2
B4 (lines 8-8) -> exit
unreachable: none

Why it works

The last instruction of a block decides where control can go next, and any block no path reaches can never run.

Examples

Example 1 · Input
8
i = 0
L1:
t1 = i < 3
ifFalse t1 goto L2
print i
i = i + 1
goto L1
L2:
Expected output
B1 (lines 1-1) -> B2
B2 (lines 2-4) -> B3 B4
B3 (lines 5-7) -> B2
B4 (lines 8-8) -> exit
unreachable: none
Example 2 · Input
5
x = 1
goto L1
x = 2
L1:
print x
Expected output
B1 (lines 1-2) -> B3
B2 (lines 3-3) -> B3
B3 (lines 4-5) -> exit
unreachable: B2

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

Hints

Hint 1

Find the blocks as in the previous exercise, and record which block holds each label.

Hint 2

Then search from B1 along the edges to find the reachable blocks.

Solution

Show one correct solution (try it yourself first)
lines = [input().strip() for _ in range(int(input()))]
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
block_of = {}
for k in range(count):
    for line in lines[starts[k]:starts[k + 1]]:
        if line.endswith(":"):
            block_of[line[:-1]] = k
succ = []
for k in range(count):
    words = lines[starts[k + 1] - 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})
seen, todo = {0}, [0]
while todo:
    for s in succ[todo.pop()]:
        if s < count and s not in seen:
            seen.add(s)
            todo.append(s)


def name(k):
    return "exit" if k == count else f"B{k + 1}"


for k in range(count):
    print(f"B{k + 1} (lines {starts[k] + 1}-{starts[k + 1]}) -> " + " ".join(name(s) for s in sorted(succ[k])))
missing = [name(k) for k in range(count) if k not in seen]
print("unreachable:", " ".join(missing) if missing else "none")

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