Modeling subregister aliasing

[zlfn]

I’m experimenting with using regalloc2 for a cranelift backend targeting a old Z80 8-bit CPU with hierarchical registers —
where two small registers can form one larger register, and vice versa:

B + C = BC (16-bit)
D + E = DE (16-bit)
H + L = HL (16-bit)

Here’s the challenge:

Some 16-bit instructions can use either BC or DE.
When BC is used, both B and C become clobbered.
When DE is used, D and E are clobbered instead.

The 8-bit registers are individually addressable, but they also participate in 16-bit operations as pairs.

The problem is that regalloc2 assumes all physical registers in a class are disjoint,
and clobber sets must be fixed before allocation.
That makes it unclear how to express a relationship like “BC aliases both B and C” or “writing BC invalidates B and C.”

LLVM handles this using register units and subregisters, where overlapping registers share “register units”
and the allocator tracks partial definitions and interference on that level.
regalloc2, however, currently has no notion of aliasing or register overlap.

So I’m wondering:

Is there any way to model such subregister aliasing with the current regalloc2 API?

Would it make sense to support aliasing PRegs or register subsets (similar to LLVM’s register units / subregister indices)?

Or is the current expectation that these aliasing relationships be handled entirely outside the allocator,
e.g. by inserting explicit moves, using fixed constraints, or splitting live ranges manually?

[cfallin]

Hi @zlfn -- unfortunately, as you've noted, regalloc2 doesn't support overlapping resources. It is theoretically possible to update it to model this by modifying the register-search logic, tracking the smallest possible divisions, and checking availability in all components for a larger (composite) resource, but that's not a very simple refactor. You're welcome to explore the code and design (see the documentation in this repo for detailed design notes) and experiment with this, of course. Right now I would say simply that it is out-of-scope and you'll need to decide on disjoint units to allocate (for example: BC is a register, DE is a register; if you need only half, you ignore the other half).

[zlfn]

If registers are allocated in 16-bit units, it disables half of the registers, which lead to very poor code quality.
One possible approach could be to handle all 16-bit operations through a single register pair (like BC), locking both registers whenever a 16-bit op is emitted.

I’m thinking of implementing a Z80-style ad-hoc allocation algorithm, where 8-bit registers are treated as an Integer class and 16-bit registers as a Vector class, ensuring that certain vector-class and integer-class registers are never allocated at the same time.
Since the number of registers is fixed and relatively small, it shouldn’t be too difficult to implement.
I might try making it a separate crate with regalloc2-compatible interfaces.

[Amanieu]

regalloc3 supports sub-register aliasing, but it's a lot more involved than just modifying register probing to check both sub-register. You also need to:

• Completely revamp the parallel move resolver since it will need to be able to handle multiple cycles in the parallel move graph.
• Update redundant move elimination to track the active vreg in each sub-register and properly handle cases where only half of a register pair is overwritten.
• Update the regalloc checker to also track everything at the sub-register level.

Overall it's such a large change that I don't think it is worth supporting in regalloc2.