Re: Graph colouring and local register allocation

jle@ural.owlnet.rice.edu (Jason Lee Eckhardt)
Sat, 3 Nov 2007 20:45:03 +0000 (UTC)

          From comp.compilers

Related articles
Graph colouring and local register allocation shafitvm@gmail.com (Mohamed Shafi) (2007-10-31)
Re: Graph colouring and local register allocation preston.briggs@gmail.com (preston.briggs@gmail.com) (2007-10-31)
Re: Graph colouring and local register allocation jle@ural.owlnet.rice.edu (2007-11-03)
Re: Graph colouring and local register allocation parthaspanda22@gmail.com (2007-11-04)
Re: Graph colouring and local register allocation SidTouati@inria.fr (Sid Touati) (2007-11-05)
Re: Graph colouring and local register allocation miles.bader@necel.com (Miles Bader) (2007-11-22)
Re: Graph colouring and local register allocation Sid.Touati@uvsq.fr (Sid Touati) (2007-11-30)
Re: Graph colouring and local register allocation gneuner2@comcast.net (George Neuner) (2007-12-01)
Re: Graph colouring and local register allocation sjdutoit@gmail.com (sdt) (2007-12-01)
[9 later articles]
| List of all articles for this month |

From: jle@ural.owlnet.rice.edu (Jason Lee Eckhardt)
Newsgroups: comp.compilers
Date: Sat, 3 Nov 2007 20:45:03 +0000 (UTC)
Organization: Rice University, Houston, TX
References: 07-10-103
Keywords: registers

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.



Post a followup to this message

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