Question about coalescing

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Question about coalescing

Fernando Magno Quintao Pereira

Dear guys,

     I want to coalesce some copies, and I would like to know if there is
any method that I can call, like JoinCopy from the old (LLVM 1.9)
LiveIntervals class. I found it in SimpleRegisterCoalescing (LLVM 2.1),
but I do not want to call this analysis, as I have my own.

     basically, I can determine that two virtuals do not overlap, and I
know that it is safe to join them. In the old v1.9, I simply had to do
this:

     this->interval_analysis_->JoinCopy(mach_inst, use_eg, def_reg);

best,

Fernando
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question about coalescing

dag-7
On Saturday 15 December 2007 18:45, Fernando Magno Quintao Pereira wrote:

> Dear guys,
>
>      I want to coalesce some copies, and I would like to know if there is
> any method that I can call, like JoinCopy from the old (LLVM 1.9)
> LiveIntervals class. I found it in SimpleRegisterCoalescing (LLVM 2.1),
> but I do not want to call this analysis, as I have my own.
>
>      basically, I can determine that two virtuals do not overlap, and I
> know that it is safe to join them. In the old v1.9, I simply had to do
> this:
>
>      this->interval_analysis_->JoinCopy(mach_inst, use_eg, def_reg);

Fernando,

I had a similar requirement and did a ton of work to refactor
SimpleRegisterCoalescing to break out the joining and dataflow
update code into independent routines.  My custom coalescer
calls them to do the heavy lifting.

There was quite a bit of debugging involved in this.  :)

I've been meaning to submit this back to upstream.  This looks like
a good time to do so.  I'll see if I can get a draft patch soon.

                                           -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question about coalescing

Evan Cheng-2
In reply to this post by Fernando Magno Quintao Pereira

On Dec 15, 2007, at 4:45 PM, Fernando Magno Quintao Pereira wrote:

>
> Dear guys,
>
>     I want to coalesce some copies, and I would like to know if  
> there is
> any method that I can call, like JoinCopy from the old (LLVM 1.9)
> LiveIntervals class. I found it in SimpleRegisterCoalescing (LLVM  
> 2.1),
> but I do not want to call this analysis, as I have my own.
>
>     basically, I can determine that two virtuals do not overlap, and I
> know that it is safe to join them. In the old v1.9, I simply had to do
> this:
>
>     this->interval_analysis_->JoinCopy(mach_inst, use_eg, def_reg);

SimpleRegisterCoalescing::JoinCopy hasn't fundamentally changed from  
the old JoinCopy. It still does the same sort of analysis. The only  
change really is the interface.

Evan

>
>
> best,
>
> Fernando
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question about coalescing

Fernando Magno Quintao Pereira

Dear Dave, Evan, thank you for answering.

     What I did was to remove the implementation of most of the methods of
SimpleRegisterCoalescing and put them in a single class
(RegisterCoalescer_Impl) that is not an analysis. Any class that wants
these methods, can extend this class privately, or can use a reference to
an RegisterCoalescer_Impl object. I wish it would be possible to go even
further: given that I know that two virtuals do not interfere, I would
like to coalesce them by simply joining their interval representation.
When I call JoinCopy, the method does that, but it checks again a lot of
information that I already know: do not overlap, are virtuals, etc.

best,

Fernando

>
> On Dec 15, 2007, at 4:45 PM, Fernando Magno Quintao Pereira wrote:
>
>>
>> Dear guys,
>>
>>     I want to coalesce some copies, and I would like to know if
>> there is
>> any method that I can call, like JoinCopy from the old (LLVM 1.9)
>> LiveIntervals class. I found it in SimpleRegisterCoalescing (LLVM
>> 2.1),
>> but I do not want to call this analysis, as I have my own.
>>
>>     basically, I can determine that two virtuals do not overlap, and I
>> know that it is safe to join them. In the old v1.9, I simply had to do
>> this:
>>
>>     this->interval_analysis_->JoinCopy(mach_inst, use_eg, def_reg);
>
> SimpleRegisterCoalescing::JoinCopy hasn't fundamentally changed from
> the old JoinCopy. It still does the same sort of analysis. The only
> change really is the interface.
>
> Evan
>
>>
>>
>> best,
>>
>> Fernando
>> _______________________________________________
>> LLVM Developers mailing list
>> [hidden email]         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question about coalescing

dag-7
On Monday 17 December 2007 14:06, Fernando Magno Quintao Pereira wrote:

> Dear Dave, Evan, thank you for answering.
>
>      What I did was to remove the implementation of most of the methods of
> SimpleRegisterCoalescing and put them in a single class
> (RegisterCoalescer_Impl) that is not an analysis. Any class that wants
> these methods, can extend this class privately, or can use a reference to
> an RegisterCoalescer_Impl object. I wish it would be possible to go even
> further: given that I know that two virtuals do not interfere, I would
> like to coalesce them by simply joining their interval representation.
> When I call JoinCopy, the method does that, but it checks again a lot of
> information that I already know: do not overlap, are virtuals, etc.

Right.  So it does more work than necessary.  I haven't verified this, but I
suppose it's possible that your (or my) coalescer might things something
is legal when SimpleRegisterCoalescing does not, or vice-versa.  Have you
thought about the implications of this possibility?

How do you handle dataflow upsdates in your coalescer?  JoinCopy does
all that stuff, so I assume you just let that handle it.  JoinCopy also
updates some data structures internal to SimpleRegisterCoalescing, so
again, it does more work than necessary.

                                               -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Question about coalescing

Fernando Magno Quintao Pereira
>
> How do you handle dataflow upsdates in your coalescer?  JoinCopy does
> all that stuff, so I assume you just let that handle it.  JoinCopy also
> updates some data structures internal to SimpleRegisterCoalescing, so
> again, it does more work than necessary.
>

Hi,

Once I find that two variables can be coalesced, I simply call
JoinCopy(...). Ideally, the method to join two intervals (which also would
updates all the data structures internal to the LiveIntervals class)
should be separate from the method that tells when it is legal to
coalesce two variables. In this way, the same join method could be called
by different register coalescers, without loss in performance.

best,

Fernando
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev