pass4: fix register allocation

[zerbina]

Summary

• fix the "cannot satisfy constraints" assertion failing when it should not
• fix concurrently live locals sometimes being assigned same physical register

Details

Problem 1: Graph Coloring

The graph coloring wasn't able to handle (A -> B, C -> B) renames (tested by t03_rename_join.test), that is, two otherwise unconnected locals being rename-assigned to the same local.

This is addressed by using an adjusted coloring scheme: the forward coloring pass for "strong" edges is integrated into the normal forward pass, and the backward pass also propagates along strong edges now. For this to work, colors must not be propagated across pinned <-> non- pinned edges.

As a consequence, colors are propagated a bit less aggressively. However, given that Rename is mostly used for locals that have their address taken, it's better not to merge these with other locals anyway.

Problem 2: Virtual-to-Physical Register Mapping

The previous mapping allocated physical registers (and marked them live) with only the current basic-block as the context, which only works in a limited number of cases (but not all)

For example, a graph with three basic-blocks with virtual register pairs (B, A), (B, C), and (A, C) would result in A and C sharing the same physical register (when A, B, and C aren't used anywhere else).

The mapping is changed to use simplified version of the contemporary "live range" register allocation approach. For each virtual register, a live range is computed, which approximates the sub-graph in the data- flow graph where the register is live. These ranges are then used to prevent incorrect physical register re-use.

[zerbina]

@saem I've forgot to explicitly mention it, but this fixes the error you're encountering on the If branch.

[saem]

@saem I've forgot to explicitly mention it, but this fixes the error you're encountering on the If branch.

Yup, I gathered that, but that's for mentioning it explicitly.