Re: Graph colouring and local register allocation

"preston.briggs@gmail.com" <preston.briggs@gmail.com>
Sat, 1 Dec 2007 10:12:01 -0800 (PST)

          From comp.compilers

Related articles
[3 earlier articles]
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)
Re: Graph colouring and local register allocation preston.briggs@gmail.com (preston.briggs@gmail.com) (2007-12-01)
Re: Graph colouring and local register allocation gneuner2@/comcast.net (George Neuner) (2007-12-01)
Re: Graph colouring and local register allocation pertti.kellomaki@tut.fi (=?ISO-8859-1?Q?Pertti_Kellom=E4ki?=) (2007-12-03)
Re: Graph colouring and local register allocation SidTouati@inria.fr (Sid Touati) (2007-12-04)
Re: Graph colouring and local register allocation torbenm@app-1.diku.dk (2007-12-05)
Re: Graph colouring and local register allocation SidTouati@inria.fr (Sid Touati) (2007-12-08)
Re: Graph colouring and local register allocation anton@mips.complang.tuwien.ac.at (2007-12-09)
[2 later articles]
| List of all articles for this month |

From: "preston.briggs@gmail.com" <preston.briggs@gmail.com>
Newsgroups: comp.compilers
Date: Sat, 1 Dec 2007 10:12:01 -0800 (PST)
Organization: Compilers Central
References: 07-10-103 07-11-019 07-11-063 07-11-091 07-12-003
Keywords: registers, parallel
Posted-Date: 01 Dec 2007 13:25:08 EST

> >> So what do "modern" compilers use?
> >
> >The term "modern" has no sense. It's marketing. Maybe you mean "actual".


He probably means the same thing you meant when you wrote "modern".


> > Most of the compilers use old register
> >allocation techniques, designed for sequential processors. When ILP
> >came, few of them used advanced techniques based on strong theoretical
> >research results[...]


> Frankly, I don't see what impact ILP has on register allocation [...]


If we schedule to minimize register pressure, then allocate, then try
to reschedule to maxmize ILP, we'll have a hard time. The initial
schedule and allocation will leave us very little "room to work". On
the other hand, if we initially schedule for maximum ILP, then
allocation will require more registers, perhaps causing spill code.


For an easy example, consider finding the sum of 4 integers.
If we write the code like this


        r = A
        r += B
        r += C
        r += D
        SUM = r


versus


        r1 = A r2 = C
        r1 += B r2 += D
        r1 += C
        SUM = r1


(where I've written in this 2-column form to make the ILP obvious).
The 1st approach requires only a single register but will take at
least 5 ticks.
The 2nd approach requires 2 registers but can run a bit faster.


Google up "Register Allocation with Instruction Scheduling: A New
Approach" by Schlomit Pinter. That and the papers that cite it will
get you off to a good start.


Preston


Post a followup to this message

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