Re: coalescing in graph coloring register allocator

Clifford Click <cliff.click@Eng.Sun.COM>
13 Aug 1998 22:09:57 -0400

          From comp.compilers

Related articles
coalescing in graph coloring register allocator jp@altair.snu.ac.kr (jp) (1998-08-03)
Re: coalescing in graph coloring register allocator max@gac.edu (Max Hailperin) (1998-08-04)
Re: coalescing in graph coloring register allocator cliff.click@Eng.Sun.COM (Clifford Click) (1998-08-05)
Re: coalescing in graph coloring register allocator george@research.bell-labs.com (Lal George) (1998-08-10)
Re: coalescing in graph coloring register allocator cliff.click@Eng.Sun.COM (Clifford Click) (1998-08-13)
Re: coalescing in graph coloring register allocator george@research.bell-labs.com (Lal George) (1998-08-16)
Re: coalescing in graph coloring register allocator cliff.click@Eng.Sun.COM (Clifford Click) (1998-08-19)
| List of all articles for this month |

From: Clifford Click <cliff.click@Eng.Sun.COM>
Newsgroups: comp.compilers
Date: 13 Aug 1998 22:09:57 -0400
Organization: Sun Microsystems
References: 98-08-021 98-08-037 98-08-074
Keywords: registers,optimize

> > My compiler is a run-time compiler for Java and has strict
> > compile-time constraints. I'm running 1 round of agressive
> > coalescing, and 1 round of conservative coalescing each time I split
> > live ranges.


Lal George wrote:
> Briggs, Click, and others have used a combination of techniques,
> however the order in which to apply the aggressive and conservative
> strategies is adhoc, and there is no guarantee against additional
> spills being introduced.
>
> Our algorithm, on the other hand, guarantees not to introduce spills,
> and is often much better than the conservative technique alone, and is
> very simple to implement. The fully pseudo-code for the algorithm is
> given in the article:


Let me add that I tried the George/Lal/Appel approach and found it was
too slow for my purposes. I couldn't dream up a way to effeciently
flip-flop between coalescing copies related to live ranges that just
recently become of low degree and Simplifying.


That is, after you Simplify some low degree live range, what is the
set of copies that should be reinspected to see if they can be
coalesced? Inspecting them all is quite slow.


People doing static compilers probably do not care about the speed problem.


Cliff
--
Cliff Click Compiler Designer and Researcher
cliffc at acm.org JavaSoft
(408) 863-3266 MS UCUP02-302
--


Post a followup to this message

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