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
pluggable_coalescer.patch (15 KB)
No comments?
Or is everyone taking vacation before the fall? 
-Dave
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
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
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.
Ok. But that means this method doesn't belong to the InterferenceData class. Shouldn't the allocator query the coalescer instead?
Thanks,
Evan
No, it's the other way around. The coalescer needs to decide whether it can
coalesce something. It must ask the allocator if it's ok.
This is part of InterferenceData to decouple the coalescer from the allocator
so the coalescer doesn't have to keep a pointer to the allocator. In my
current implementation, InterferenceData for the graph coloring allocator
has references to all of the necessary information to return an answer to
this question.
-Dave
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.
Ok. But that means this method doesn't belong to the InterferenceData
class. Shouldn't the allocator query the coalescer instead?
No, it's the other way around. The coalescer needs to decide whether it can
coalesce something. It must ask the allocator if it's ok.
This is part of InterferenceData to decouple the coalescer from the allocator
so the coalescer doesn't have to keep a pointer to the allocator. In my
current implementation, InterferenceData for the graph coloring allocator
has references to all of the necessary information to return an answer to
this question.
Ok. This means InterferenceData contains more than interference information. Perhaps you can choose a better name? Or add another data structure to store this information.
Evan