[LLVMdev] [patch] Pluggable Coalescers

[David Greene]

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 &copy) {};
>
> 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