Re: Register allocation for virtual register targets

On 5/31/26 6:57 PM, feedable wrote:
> Hi all!
>
> I want to adapt the current register allocation scheme so that it is
> usable for targets with virtual registers. I believe that, if done
> correctly, this may even result in some benefit to physical register
> targets, too.
>
> ** Some background **
> I am working on a wasm port for GCC. wasm is a virtual register target,
> meaning that a compiler is supposed to declare an arbitrary set of
> registers that it is willing to use for a function, and use this set of
> registers without ever needing to spill values onto the stack.
>
> Currently, the only other virtual register target is nvptx. To have
> virtual registers, it skips over IRA and LRA entirely. This works
> relatively well for them, since due to specifics of the target, there is
> a one-to-one correspondence between register's mode and would-be
> register class, so instructions can be selected based purely on the
> instruction's RTL shape, without need for constraints. nvptx also
> doesn't need to worry about size, so it can declare as many registers
> as it likes, without trying to compress the set of declared registers.
>
> wasm unfortunately isn't like that: being a target primarily aimed at
> use on websites, size is usually very important for page loading speed.
> Proper register allocation would still be useful here to compress the
> set of declared registers for a function. This compression would also be
> useful because wasm addresses registers via leb128 indices, so popular
> registers can also have lower indices, which reduces size of register
> access instructions. (benefit form register allocation here is that
> as there are less registers in total, a bigger proportion of them can
> get short indices)
>
> Unlike nvptx, wasm lacks virtual registers for 8- and 16-bit values. As
> constraints are meaningless without register allocation, such values
> still have to be stored as 32-bit values, and pretty complicated
> workarounds are required to ensure that a register of incorrect mode
> does not end up in an operation that does not work on physical registers
> of such size (e.g. via a subreg expr).
>
> There are also optimization opportunities that are missed if only mode
> determines which register value gets placed in: if a register of small
> mode is primarily used via subregs of large mode, it would be beneficial
> to place such value in a large register in the first place, instead of
> trying to actually cast the value to a large mode first every time.
> Similar situation can occur in reverse: A large value that is used as a
> small one several times in a row, would benefit from being temporarily
> reloaded to a small register class, to coalesce the casts.
>
> ** wasm-specific considerations **
> - wasm also has special types that can only exist in registers, and for
> which no instructions to load, store or cast to/from an integer is
> available. This would mean that for these types the register allocator
> cannot ever pick NO_REGS as a fallback (which it shouldn't ever do on a
> virtual register target regardless, but it's one more thing to keep in
> mind).
> - wasm's to-be register classes are also disjoint, meaning that a value
> that resides in a 64-bit register cannot be accessed as-if it resides in
> a 32-bit register. There is also no register class that can hold any
> value, so GENERAL_REGS is also not meaningful, and ALL_REGS is not a
> register class any target virtual register can actually be assigned.
>
> ** General considerations **
> - instructions for virtual register targets may actually accept an
> arbitrary amount of arguments (e.g. wasm's call family of insns, or asm
> blocks), each of which would need a constraint, so register allocation
> infrastructure needs to be adapted to support that. It probably would be
> useful even for targets with a fixed amount of registers, as that will
> potentially remove the current 30 operand limit on asm_operands.
> - register asm decls would no longer be able to specify a specific
> register name to store the value in, they would need to specify a class
> instead. This may be of use for fixed register targets too, e.g. First 
> of all, porting GCC to one more target is not a simple task. In
> Cygnus (a company which made a lot of GCC ports), it usually took half
> a year for a developer with some experience to compile a "hello,
> world" program. Of course, there are people who could make a port much
> faster, e.g. Mike Meissner who made more than 10 ports. But probably
> for a novice like you, I'd plan on 6 months of full work at least. You
> will learn a lot about GCC during this work.
>
> To use GCC optimizations fully (e.g. generate madd insns by the GCC
> combiner pass), I believe you should get rid of stack insns: all
> operands should be explicit. And generation of stack insns should be
> the very last pass of GCC. You could adapt the reg-stack.cc pass for
> this or make your own machine-dependent pass (it is easier for
> implementation review and approval too). The machine-dependent pass
> can do some optimization too if it is necessary, e.g. renumbering
> local vars to make frequently used vars have smaller numbers (but I am
> not sure it will be necessary after IRA).
>
> Local variables should be pseudos starting with a very big number to
> avoid spilling. And hard registers (numbered before the first
> pseudo-register) should be final local variable numbers. I think
> FIRST_PSEUDO_REGISTER=10000 is enough to avoid spilling. The most
> demanding benchmarking program I know, fppp, has register pressure of
> several hundred only. You can divide 10000 hard registers by mode
> (integer, FP, vector hard regs).
>
> That is the high-level wasm port design I think is worth doing.
>
> I think although wasm is unusual, it is not complicated (real hardware
> targets are less regular than wasm). Probably RTL insns for wasm will
> have only one alternative, no secondary memory, no secondary reload,
> etc. When you run into a problem, look at how other ports solve the
> problem — the simpler and more regular the port, the better (I'd
> recommend a classic RISC architecture for this).
>
> Probably, you will need to switch off some code in LRA,
> e.g. inheritance (as you will have no spilling), hard reg splitting
> (because you always have enough regs), or maybe register
> elimination. Also, when working on RA for wasm, you could switch off
> other LRA optimizations and subpasses first (like rematerialization,
> equivalence substitution), and switch them on later (if they give some
> benefits). It may be that after switching off all LRA optimizations,
> LRA will only need to change pseudos to hard regs and check that the
> insn constraints are satisfied.
>
> You can switch off regional RA in IRA (I don't think it is necessary
> for wasm as it has an unconstrained number of locals, and regional RA
> can only help to generate smaller numbers for local vars in a
> region/loop). You could also start with IRA fast_allocation, which is
> much simpler than coloring, but I am not sure it saves you time.
>
>
> to place a value in any register as long as it has the required class.
>
> ** The request **
> I would like to adapt the current setup of IRA+LRA to work under these
> constraints. Unfortunately, after attempting to do that by myself my
> changes kept behaving unpredictably, and I realized that I lack the
> understanding necessary, and would like some guidance.
> - Which parts should I touch first, to get something testable? Every
> time I tried to start this, I felt like there were too many moving
> parts, between machine constraints, and various parts of ira and lra.
> - What would a good design for this look like? E.g. my first attempt
> used backend hooks to mark out additional operands based on
> circumstantial evidence from the RTL shape itself. Would it be better
> to create another rtx like "use with constraint" instead?
> - Is adapting the current infrastructure even the right call, or would
> it be simpler to write a separate register allocator? It may not even
> be possible to make the current scheme never reload to memory, but
> that's a hard requirement for wasm.
>