Re: Why I've Dropped In

On Tue, 17 Jun 2025 20:43:00 +0000, Stefan Monnier wrote:

MitchAlsup1 [2025-06-17 17:45:23] wrote:

On Tue, 17 Jun 2025 1:26:01 +0000, Stephen Fuld wrote:

On 6/16/2025 9:17 AM, Stefan Monnier wrote:

I vaguely remember reading somewhere that it doesn't have to be too bad:
e.g. if you reduce register-specifiers to just 4bits for a 32-register
architecture and kind of "randomize" which of the 16 values refer to
which of the 32 registers for each instruction, it's fairly easy to
adjust a register allocator to handle this correctly (assuming you
choose your instructions beforehand, you simply mark, for each
instructions, the unusable registers as "interfering"), and the end
result is often almost as good as if you had 5bits to specify
the registers.

I can see that it isn't too hard on the logic for the register
allocator,

You are missing the BIG problem::
>
Register allocator allocated Rk for calculation j and later allocates
Rm for instruction p, then a few instructions later the code generator
notices that Rk and RM need to be paired or shared and they were not
originally.

>
What do you mean by "a few instructions later"?  The above was stated in
the context of a register allocator based on something like Chaitin's
algorithm, which does not proceed "instruction by instruction" but
instead takes a whole function (or basic bloc), builds an interference
graph from it, then chooses registers for the vars looking only at that
interference graph.

I am regurgitating conversations I have had with compile people over
the last 40 years. Noting I have seen in ISA design has moderated
these problems--but I, personally, have not been inside a compiler
for 41 years, either (1983). So, find a compiler writer to set this
record straight. I continue to be told: it is enough harder that you
should design ISA so you don't need pairing or sharing, ever.

but I suspect it will lead to more register saving and
restoring.

And reg-reg MOVment.

>
Of course.  The point is simply that in practice (for some particular
compiler at least), the cost of restricting register access by using
only 4bits despite the existence of 32 registers was found to be small.
>
Note also that you can reduce this cost by relaxing the constraint and
using 5bit for those instructions where there's enough encoding space.
(or inversely, increase the cost by using yet fewer bits for those
instructions where the encoding space is really tight).
>
There's also a good chance that you can further reduce the cost by using
a sensible mapping from 4bit specifiers instead a randomized one.
>
IOW, the point is that just because you have chosen to have 2^N
registers in your architecture doesn't mean you have to offer access to
all 2^N registers in every instruction that can access registers.
It's clearly more convenient if you can offer that access, but if needed
you can steal a bit here and there without having too serious an impact
on performance.
>

            Consider a two instruction sequence where the output of the
first instruction is an input to the second.  The first instruction has
only a choice of 16 registers, not 32.  And the second instruction also
has 16 registers, but on average only half of them will be in the 16
included in the first instruction.  So instead of 32 registers to chose
from you only have 8.

>
Right.  But in practice, the register allocator can often choose the
rest of the register assignment such that one of those 8 is available.
>
>
        Stefan