Re: Coalescing register allocators

preston@dawn.cs.rice.edu (Preston Briggs)
Wed, 18 Aug 1993 15:58:06 GMT

          From comp.compilers

Related articles
Coalescing register allocators rusa@microsoft.com (1993-08-05)
Re: Coalescing register allocators firth@sei.cmu.edu (1993-08-06)
Re: Coalescing register allocators preston@dawn.cs.rice.edu (1993-08-06)
Re: Coalescing register allocators rusa@microsoft.com (1993-08-13)
Re: Coalescing register allocators preston@dawn.cs.rice.edu (1993-08-16)
Re: Coalescing register allocators preston@dawn.cs.rice.edu (1993-08-18)
Re: Coalescing register allocators rusa@microsoft.com (1993-08-18)
| List of all articles for this month |

Newsgroups: comp.compilers
From: preston@dawn.cs.rice.edu (Preston Briggs)
Keywords: registers, optimize
Organization: Rice University, Houston
References: 93-08-032 93-08-081
Date: Wed, 18 Aug 1993 15:58:06 GMT

>[Anyone have rules of thumb about what approaches make sense for what sizes
>of register sets. I'd expect the best techniques for a Pentium which
>still only has six general registers would be quite different from those
>for a system with 16 or 31 of them. -John]


Well, I guess my rule of thumb is that if you don't have enough registers
to support Chaitin's allocator, then you don't have enough registers to
support an optimizing compiler.


Now, it's certainly possible to generate good and bad code for a
3-register machine (say) and we should all try to avoid bad code.
However, with so few registers, probably the best we can hope for is
reasonable code for each expression, with no thought of global
optimization (perhaps not even optimization between expressions in the
same basic block).


A few more registers would allow us to look for reuse across small basic
blocks (would have to artificially limit the size to avoid problems with
things like fpppp). I guess my feeling, with no experimentation at all,
is:


0 to 3 registers - expressions
3 to 6 - small basic blocks
6 or more - arbitrary basic blocks
8 or more - global


Here I'm counting free registers available for the allocator
(i.e., not the stack pointer, frame pointer, ...)


Of course, all these numbers are arguable. Giant basic blocks can consume
a lot of registers profitably. Similarly, a couple of registers holding
the right values across a loop can be very significant.


As a final caveat, I'm only talking about optimizations involving reuse of
values. Optimizations like dead code elimination and constant propagation
don't require extra registers and should always be performed.


Preston Briggs
--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.