Re: Graph colouring and local register allocation

Mohamed Shafi <shafitvm@gmail.com> wrote:
>Register allocation based on graph colouring is a global register
>allocation technique. Most of the modern compliers will have both
>global register allocation and local register allocation.
>
>Graph colouring based allocator primarily depends on interference
>graph for allocating registers. In the interference graph after its
>build will have both the local and global virtual registers(with
>respect to a block) as the nodes. These are the nodes that will be
>considered later stages of the allocator, as in select and simplify of
>chatins/briggs register allocator. If this is the case, what is the
>purpose of a separate local register allocator?
>
>As I Am Implementing A Register Allocator Based On Briggs Optimistic
>Register Allocator Which Works On The Pseudo Assembly Instructions, I
>Would Want To Know The Need Of A Local Register Allocator.


A local register allocator is not NEEDED if you are using a
Chaiting-Briggs allocator. However, there are circumstances where a
local allocator MAY be useful. For example, most compilers have
optimization levels controlled by the user (-O0, -O1, etc). For low
optimization levels, a local allocator may be desirable as they are
often very fast and do a reasonably good job. At higher levels the
local allocator could be disabled, and the global allocator enabled.


There is also reason to believe that some local allocators may perform
better on large basic blocks with high register pressure compared to a
global coloring allocator. That is, the spilling behavior of a
vanilla Chaitin-style allocator on large basic blocks can sometimes be
poor. There have been comparison papers, though the titles escape me
at the moment (I believe LCPC'03 had one along these lines).


Local allocation seems to be easier to integrate with instruction
scheduling in basic blocks as well-- and this integration is important
for large basic blocks with high register pressure (e.g., read about
the Multiflow compiler).


If engineering time is a concern, writing a local allocator is
arguably easier/faster to write than a Chaitin-style allocator
(although with Preston's thesis spelling out the details so nicely,
this argument is harder to make). But nowadays, almost everyone uses
modified Chaitin allocators that do live range splitting, etc. This
adds more complication and engineering time.


Finally, there are schemes that start with a local allocation phase
followed by a global one, so that the local allocator in no longer
optional.


Jason.

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