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
On Aug 27, 2007, at 2:04 PM, David Greene wrote:> >> 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> > >> 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 > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Monday 27 August 2007 19:02, Evan Cheng wrote:> > 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. -Dave