Path: csiph.com!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail From: Stefan Monnier Newsgroups: comp.arch Subject: Re: Why I've Dropped In Date: Tue, 17 Jun 2025 16:43:00 -0400 Organization: A noiseless patient Spider Lines: 63 Message-ID: References: <0c857b8347f07f3a0ca61c403d0a8711@www.novabbs.com> <8addb3f96901904511fc9350c43917ef@www.novabbs.com> <102b5qh$1q55a$2@dont-email.me> <48c03284118d9d68d6ecf3c11b64a76b@www.novabbs.com> <577246053d33788ee71e2e04e8466450@www.novabbs.org> <102qg7a$1vq33$1@dont-email.me> <9668ceb1d550abdc26c923a6405b7343@www.novabbs.org> MIME-Version: 1.0 Content-Type: text/plain Injection-Date: Tue, 17 Jun 2025 22:43:01 +0200 (CEST) Injection-Info: dont-email.me; posting-host="fe7cb30879a5164d17b251be2babce56"; logging-data="2753816"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/8sf9CAhwQZ98yeXkSXVFipH0RikrXVF4=" User-Agent: Gnus/5.13 (Gnus v5.13) Cancel-Lock: sha1:XZn4caZRSjWf9S55smzoH88ipYw= sha1:Hint4exaS5ueZguMd+z69H1+9uo= Xref: csiph.com comp.arch:112149 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. >> 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