I’m atempting to implement the following linear scan register allocator called “second chance binpacking”:

What I really like about the paper is that, unlike most other linear scan

allocators, it does the rewriting and allocation in one pass over the flattened

CFG.

However, it seems to me there is a problem with this. The paper doesn’t say

that the correctness of the algorithm depends on the ordering of the basic

blocks; merely that reverse postorder is preferrable. If that’s the case, then

suppose that we picked an arbitrary block order:

Suppose that when we first encounter y we must assign to it some register R,

and x is currently assigned to R. We check whether x is in a hole and

whether (according to the paper) x’s hole can fit the **remainder** of y’s

lifetime (relative to the current position). But what about y’s lifetime to the

left of the current position? We have a problem if we assign

R to y’s current interval because the hole is not big enough to the left.

It seems to me that the only way this algorithm could work is if the start of a

lifetime interval of a temporary always coincides with the first encounter of

that temporary. But this depends on the ordering we choose. I believe it’s

possible to ensure this invariant in the following way:

```
Assume:
- The input IR to the allocator is in strict form. That is, along any
path from entry to exit, a virtual reg is defined before it is used.
- The CFG is traversed in reverse postorder during register allocation.
(1) When we reach the start of a block B following reverse postorder, then
there exists a path from the entry to B whose blocks we have visited.
Proof: We construct the reverse postorder with a depth-first traversal
of the CFG starting at the entry. When we first visit B, there is a path
from the entry to B whose nodes are currently grey and will thus have a
lower reverse postorder number than B.
(2) When we reach the start of a block B following reverse postorder,
we have seen a def of every virtual reg v in the live_in set of B.
Proof: There is a path P: B -> B1 -> ... -> Bn where Bn contains a use
of v before any defs in Bn and the remaining blocks don't contain uses
or defs of v. It's possible that B = Bn. Then by (1) there is a path T
from entry to B that we have visited. We can extend T with P to form a
path from entry to the use of v in Bn. Since P doesn't contain any defs
of v, T must containt a def of v due to the strictness property.
(3) When we reach the end of a block B following reverse postorder,
we have seen a def of every virtual reg in the live_out set of B.
Proof: Since the live_out set of B is the union of live_in sets of
B's successors, this is a corollary of (2).
```

Also, we would need to ensure that any time we evict a temporary from a

register, that we immediately assign it to a register or spill to memory. But

we might not want to do either. For example, there might be a hole in the

lifetime of that temporary on the next instruction so a spill or move would be

redundant, yet we have to unbind that temporary from that register. So we end

up with a temporary not currently assigned to a reg or memory.

Does anyone have any idea what’s going on?