Re: Coalescing register allocators

rusa@microsoft.com (Bjarne 'Rusa' Steensgaard)
Wed, 18 Aug 1993 23:27:55 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: rusa@microsoft.com (Bjarne 'Rusa' Steensgaard)
Keywords: registers, optimize
Organization: Microsoft Corporation
References: 93-08-032081@comp.compilers
Date: Wed, 18 Aug 1993 23:27:55 GMT

preston@dawn.cs.rice.edu (Preston Briggs) writes:


> [Reference to Schlomit Pinter's PLDI'93 paper]


Her approach seems a bit strange to me. It is at the same time dependent
and independent of a schedule. She does require some schedule to exist
before constructing the interference graph. The initial schedule used for
constructing the interference graph influences the quality of the final
schedule and the allocation.


An interference graph, that is independent of any schedule will have at
least at many edges (conflicts) as any interference graph constructed from
a given schedule. I will be using such an schedule independent interference
graph for my conservative register assignment algorithm.


An allocator and scheduler that is independent of any initial schedule must
use such a schedule independent interference graph. In order to generate
as good or better code than Schlomit Pinter's algorithm, the allocator and
scheduler must be able to trade off restrictions on the schedule with removal
of edges in the interference graph. Finding the optimal schedule is probably
NP-complete, but good heuristics may be found that improve on Schlomit
Pinter's algorithm.


At the time of PLDI'93 I knew next to nothing about register allocation and
instruction scheduling, so I did not benefit much from the discussions there
about Schlomit Pinter's work. Maybe somebody else could sum up the
discussions?


Bjarne Steensgaard
Microsoft Research
--


Post a followup to this message

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