Compilers: Linear-scan register allocation

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, or NAME -> rN (spill OTHER) when NAME takes the register of a spilled active range, or NAME -> memory when NAME itself is spilled. Finish with spilled: and the spilled names in the order they were spilled, or none.

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

Example 1 · Input
2
5
a = p + q
b = p - q
c = a * b
d = p + c
print d
Expected output
p -> r1
q -> r2
a -> r1 (spill p)
b -> r2
c -> r1
d -> r1
spilled: p
Example 2 · Input
3
5
a = p + q
b = p - q
c = a * b
d = p + c
print d
Expected output
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")

Lesson: Register allocation →