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), thenbusiest after line G: NAMESfor the first such g, names sorted. If no value is ever live, print onlyregisters: 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])}")