Implement the register allocator used by fast just-in-time compilers.
What to build
A program that assigns k registers to the values of straight-line code with linear scan, spilling when needed.
Requirements
- Live ranges as in the previous exercises; values that are never read are not allocated. Registers are r1 … rk; always take the lowest-numbered free one.
- Print, in the order the ranges are visited,
NAME -> rN, orNAME -> rN (spill OTHER)when NAME takes the register of a spilled active range, orNAME -> memorywhen NAME itself is spilled. Finish withspilled:and the spilled names in the order they were spilled, ornone.
Input
Line 1: k. Line 2: n. Then n instructions.
Output
One line per allocated value, then the spilled line.
Constraints
1 ≤ k ≤ 8; n ≤ 100.
Example
Input:
2
5
a = p + q
b = p - q
c = a * b
d = p + c
print d
Output:
p -> r1
q -> r2
a -> r1 (spill p)
b -> r2
c -> r1
d -> r1
spilled: p
Why it works
Visiting ranges in order of their start means a register freed by an ended range can be reused immediately, and spilling the range that ends last frees a register for as long as possible.
Examples
2 5 a = p + q b = p - q c = a * b d = p + c print d
p -> r1 q -> r2 a -> r1 (spill p) b -> r2 c -> r1 d -> r1 spilled: p
3 5 a = p + q b = p - q c = a * b d = p + c print d
p -> r1 q -> r2 a -> r3 b -> r2 c -> r2 d -> r1 spilled: none
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the live ranges by start, then by name; before each one, free the registers of active ranges whose end ≤ its start.
Hint 2
With no free register, find the active range with the largest end (the later name on a tie); if it ends after the new range, the new range takes its register.
Solution
Show one correct solution (try it yourself first)
k = int(input())
lines = [input().split() for _ in range(int(input()))]
start, end = {}, {}
for number, 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] = number
if dest:
start[dest] = number
end.setdefault(dest, number)
free, active, register, spilled = set(range(1, k + 1)), [], {}, []
for name in sorted((n for n in start if end[n] > start[n]), key=lambda n: (start[n], n)):
for other in [o for o in active if end[o] <= start[name]]:
active.remove(other)
free.add(register[other])
if free:
register[name] = min(free)
free.remove(register[name])
active.append(name)
print(f"{name} -> r{register[name]}")
continue
victim = max(active, key=lambda o: (end[o], o))
if end[victim] > end[name]:
register[name] = register.pop(victim)
active.remove(victim)
active.append(name)
spilled.append(victim)
print(f"{name} -> r{register[name]} (spill {victim})")
else:
spilled.append(name)
print(f"{name} -> memory")
print("spilled:", " ".join(spilled) if spilled else "none")