Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!i2pn.org!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: mitchalsup@aol.com (MitchAlsup1)
Newsgroups: comp.arch
Subject: Re: Why I've Dropped In
Date: Tue, 17 Jun 2025 21:18:29 +0000
Organization: Rocksolid Light
Message-ID: <1b5ee221db363b8e3a6ef79dc4bfa261@www.novabbs.org>
References: <0c857b8347f07f3a0ca61c403d0a8711@www.novabbs.com> <dd6e28b90190e249289add75780b204a@www.novabbs.com> <ec821d1d64555055271e3b72f241d39b@www.novabbs.com> <8addb3f96901904511fc9350c43917ef@www.novabbs.com> <102b5qh$1q55a$2@dont-email.me> <48c03284118d9d68d6ecf3c11b64a76b@www.novabbs.com> <577246053d33788ee71e2e04e8466450@www.novabbs.org> <jwvecvjacof.fsf-monnier+comp.arch@gnu.org> <102qg7a$1vq33$1@dont-email.me> <9668ceb1d550abdc26c923a6405b7343@www.novabbs.org> <jwvtt4e5d01.fsf-monnier+comp.arch@gnu.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: i2pn2.org;
	logging-data="937192"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="o5SwNDfMfYu6Mv4wwLiW6e/jbA93UAdzFodw5PEa6eU";
User-Agent: Rocksolid Light
X-Rslight-Site: $2y$10$SKYArDQ8n4gn8juaeUIwR.wT1b0gcwbg8p6Ce9Qq7sgajuusktRFK
X-Spam-Checker-Version: SpamAssassin 4.0.0
X-Rslight-Posting-User: cb29269328a20fe5719ed6a1c397e21f651bda71

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