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
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?