Here's a proposed patch for reworking register coalescing to allow pluggable
coalescers. I think I've got the interfaces where I want them and am
reasonably sure I've squashed most of the bugs. I'm still doing some
testing
and want to get through a whole regimen before committing.
As a reminder, this patch has several goals:
- Allow user-specified register coalescers, similar to how register allocators
and alias analyses work.
- Support coalescers that are not first-class passes. The interfaces need to
accommodate coalescers like the current implementation which are independent
passes and coalescers which run in tandem with another pass (usually
register allocation).
- Set up the foundation for further patches to break out common coalescing
work for reuse by various coalescers.
This patch realizes the first goal by defining a new RegisterCoalescer
interface and analysis group similar to the way AliasAnalysis is used. This
interface is used by coalescers that work in tandem with other passes.
It is mostly ignored by stand-alone coalescers except for analysis group
implementation selection by the pass managers (all coalescers must have
a common interface to be part of the analysis group).
The patch realizes the second goal through this common interface, which has
methods for invoking the coalescer, possibly repeatedly. There is an abstract
InterferenceData interface for the register allocator to provide information
to the coalescer in an opaque manner.
I've implemented these interfaces in a compiler with the current linear scan
allocator as well as a graph coloring allocator, with the current coalescer as
well as one based on George and Appel's Iterated Coalescing. It's
proven to
be sufficiently flexible for these cases.
Take a look and send feedback. Thanks for helping to make this better!
-Dave
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pluggable_coalescer.patch
Type: text/x-diff
Size: 15367 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20070820/132a31d8/attachment.patch>
On Monday 20 August 2007 15:58, David A. Greene wrote:> Here's a proposed patch for reworking register coalescing to allow > pluggable coalescers.No comments? Or is everyone taking vacation before the fall? :) -Dave
On Aug 22, 2007, at 9:06 PM, David A. Greene wrote:> On Monday 20 August 2007 15:58, David A. Greene wrote: >> Here's a proposed patch for reworking register coalescing to allow >> pluggable coalescers. > > No comments? > > Or is everyone taking vacation before the fall? :):) Evan is the one that is likely to have an opinion, he's on vacation until next monday. -Chris
Hi David,
Thanks for this patch!
Some comments:
1. typedef std::set<const LiveInterval *> IntervalSet;
Please use SmallPtrSet instead.
2.
+ virtual void mergeIntervals(const LiveInterval &a,
+ const LiveInterval &b,
+ const MachineInstr ©) {};
I find the name misleading. It's not actually performing the merging,
right? It's updating the interference graph to reflect the merge.
Please choose a more descriptive name.
3.
+ /// Allow the register allocator to communicate when it doesn't
+ /// want a copy coalesced. This may be due to assumptions made by
+ /// the allocator about various invariants and so this question is
+ /// a matter of legality, not performance. Performance decisions
+ /// about which copies to coalesce should be made by the
+ /// coalescer.
+ virtual bool okToCoalesce(const MachineInstr &inst) const {
+ return(true);
+ }
I think we discussed this early but please remind me. Why is this
necessary? Why isn't interfere() sufficient test? Also, I would prefer
a name like isLegalToCoalesce over okToCoalesce.
4. Is it necessary to separate class InterferenceData out from
RegisterCoalescer.h?
5.
+ /// Run the coalescer on this function, providing interference
+ /// data to query. Return whether we removed any copies.
+ virtual bool coalesceFunction(MachineFunction &mf,
InterferenceData &ifd) = 0;
80 col violation.
6.
+ /// doWork - The main coalescing algorithm. Return whether any
+ /// copies were coalesced.
+ bool doWork(MachineFunction &mf);
Please rename it to something like performCoalescing. Also, is this
defined anywhere?
7. About class LinearScanInterferenceData. Since it's just an
example, perhaps it should go into comments or a README file instead.
Evan
On Aug 20, 2007, at 1:58 PM, David A. Greene wrote:
> <pluggable_coalescer.patch>
On Monday 27 August 2007 15:13, Evan Cheng wrote:> 1. typedef std::set<const LiveInterval *> IntervalSet; > Please use SmallPtrSet instead.Ok.> 2. > + virtual void mergeIntervals(const LiveInterval &a, > + const LiveInterval &b, > + const MachineInstr ©) {}; > > I find the name misleading. It's not actually performing the merging, > right? It's updating the interference graph to reflect the merge. > Please choose a more descriptive name.Yes it's for updating the graph. I'll pick a better name, but I don't want it to be graph-specific.> 3. > > + /// Allow the register allocator to communicate when it doesn't > + /// want a copy coalesced. This may be due to assumptions made by > + /// the allocator about various invariants and so this question is > + /// a matter of legality, not performance. Performance decisions > + /// about which copies to coalesce should be made by the > + /// coalescer. > + virtual bool okToCoalesce(const MachineInstr &inst) const { > + return(true); > + } > > I think we discussed this early but please remind me. Why is this > necessary? Why isn't interfere() sufficient test? Also, I would prefer > a name like isLegalToCoalesce over okToCoalesce.interfere() isn't sufficient because the allocation algorithm may place other constraints on coalescing. George and Appel's iterated register coalescing is a prime example. It wants to "freeze" copies that should not be coalesced because doing so might cause spilling. You don't want the coalescer touching these because if it does the data structures will be inconsistent.> 4. Is it necessary to separate class InterferenceData out from > RegisterCoalescer.h?Good point. Originally I had thought that InterferenceData might be more general-purpose but it is rather coalescing-specific at the moment. If this changes in the future we can break it out. I'll keep it in RegisterCoalecer.h.> 5. > + /// Run the coalescer on this function, providing interference > + /// data to query. Return whether we removed any copies. > + virtual bool coalesceFunction(MachineFunction &mf, > InterferenceData &ifd) = 0; > > 80 col violation.Ok.> 6. > + /// doWork - The main coalescing algorithm. Return whether any > + /// copies were coalesced. > + bool doWork(MachineFunction &mf); > > Please rename it to something like performCoalescing. Also, is this > defined anywhere?It's just what runOnMachineFunction used to be. I split it out into doWork so that it could be called from coalesceFunction and this is what used to happen before I realized that didn't make sense at all. So really, doWork can go away. I'll change things back to the way they were.> 7. About class LinearScanInterferenceData. Since it's just an > example, perhaps it should go into comments or a README file instead.Good idea. Thanks for the good feedback. -Dave