Compilers: How many registers?

Measure register pressure to find how many registers straight-line code needs.

What to build

A program that finds the largest number of values live at the same time, and where it happens.

Requirements

  • Live ranges as in the previous exercise. A value is live after line g if start ≤ g < end; a value that is never read is never live.
  • Print registers: K, the largest number of values live after any line g (0 ≤ g < n), then busiest after line G: NAMES for the first such g, names sorted. If no value is ever live, print only registers: 0.

Input

Line 1: n. Then n instructions.

Output

One or two lines.

Constraints

n ≤ 100.

Example

Input:

4
a = x + 1
b = a * a
c = b - x
print c

Output:

registers: 2
busiest after line 1: a x

Why it works

In straight-line code, the largest number of overlapping live ranges is exactly the number of registers needed to avoid spilling.

Examples

Example 1 · Input
4
a = x + 1
b = a * a
c = b - x
print c
Expected output
registers: 2
busiest after line 1: a x
Example 2 · Input
5
a = p + q
b = p - q
c = a * b
d = p + c
print d
Expected output
registers: 3
busiest after line 1: a p q

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

Hints

Hint 1

A range (start, end] covers the point after line g when start ≤ g < end.

Hint 2

Check every point from after line 0 to after line n − 1 and keep the first one with the most live values.

Solution

Show one correct solution (try it yourself first)
lines = [input().split() for _ in range(int(input()))]
start, end = {}, {}
for k, words in enumerate(lines, start=1):
    dest, read = (None, words[1:]) if words[0] == "print" else (words[0], words[2:])
    for word in read:
        if word.isidentifier():
            start.setdefault(word, 0)
            end[word] = k
    if dest:
        start[dest] = k
        end.setdefault(dest, k)
best, where = 0, None
for gap in range(len(lines)):
    live = sorted(n for n in start if start[n] <= gap < end[n])
    if len(live) > best:
        best, where = len(live), (gap, live)
print("registers:", best)
if where:
    print(f"busiest after line {where[0]}: {' '.join(where[1])}")

Lesson: Register allocation →