[llvm-dev] Live range priority in Greedy RA

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

[llvm-dev] Live range priority in Greedy RA

David Jones via llvm-dev
Hi,

In the Greedy RA, I see that the enqueue method adds higher priority to the live intervals based on their sizes.

Isn't it makes sense to give priority to live intervals that start and end in a loop? Please let me know if the code is already achieving it in some way.
Also consider correcting me, if this approach is wrong.

--
Regards,
DTharun

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Live range priority in Greedy RA

David Jones via llvm-dev
Hi Dangeti,

As far as I know, 'calculateSpillWeightAndHint' considers loop
induction variable and the spill weight affects evict and spill. If it
is not enough for you, I guess you can add some heuristic code on the
function.

Thanks,
JinGu Kang
2018년 10월 30일 (화) 오전 11:51, Dangeti Tharun kumar via llvm-dev
<[hidden email]>님이 작성:

>
> Hi,
>
> In the Greedy RA, I see that the enqueue method adds higher priority to the live intervals based on their sizes.
>
> Isn't it makes sense to give priority to live intervals that start and end in a loop? Please let me know if the code is already achieving it in some way.
> Also consider correcting me, if this approach is wrong.
>
> --
> Regards,
> DTharun
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Live range priority in Greedy RA

David Jones via llvm-dev
In reply to this post by David Jones via llvm-dev
This may or may not be a good idea.  Here's some hand-wavy reason why it may not be a good idea:

- It will be tricky to balance the priority based on liverange size with an extra criterium like block frequency as you propose here. In the past I've seen two criteria working against each other lead to worse allocations as there is no obvious clear cut at which point the first or at which point the 2nd criterium should be use.
- Liverange splitting should typically separate the liveranges inside the loop from the liveranges outside, so it's possible there are few interferences between values inside the loop and outside the loop left.

Ultimately the best way to argue here, is running benchmarks and looking at concrete situations. So the best way to prove this is to implement it, run it on various benchmarks and see how it performs.

- Matthias

On Oct 30, 2018, at 4:51 AM, Dangeti Tharun kumar via llvm-dev <[hidden email]> wrote:

Hi,

In the Greedy RA, I see that the enqueue method adds higher priority to the live intervals based on their sizes.

Isn't it makes sense to give priority to live intervals that start and end in a loop? Please let me know if the code is already achieving it in some way.
Also consider correcting me, if this approach is wrong.

--
Regards,
DTharun
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Live range priority in Greedy RA

David Jones via llvm-dev
In reply to this post by David Jones via llvm-dev
Hi,

I had a look at this  'calculateSpillWeightAndHint' function, spill weights are being calculated considering no of uses, defs, loops etc.
Why not these weights be used as priority, seems they are good enough to serve as priority, instead doing it by their sizes?

On Tue, Oct 30, 2018 at 5:39 PM jingu kang <[hidden email]> wrote:
Hi Dangeti,

As far as I know, 'calculateSpillWeightAndHint' considers loop
induction variable and the spill weight affects evict and spill. If it
is not enough for you, I guess you can add some heuristic code on the
function.

Thanks,
JinGu Kang
2018년 10월 30일 (화) 오전 11:51, Dangeti Tharun kumar via llvm-dev
<[hidden email]>님이 작성:
>
> Hi,
>
> In the Greedy RA, I see that the enqueue method adds higher priority to the live intervals based on their sizes.
>
> Isn't it makes sense to give priority to live intervals that start and end in a loop? Please let me know if the code is already achieving it in some way.
> Also consider correcting me, if this approach is wrong.
>
> --
> Regards,
> DTharun
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev


--
Regards,
DTharun

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|

Re: [llvm-dev] Live range priority in Greedy RA

David Jones via llvm-dev
As far as I know, there is a good comment about priority on enqueue as below.

  /// Allow the target to reverse allocation order of local live ranges. This
  /// will generally allocate shorter local live ranges first. For targets with
  /// many registers, this could reduce regalloc compile time by a large
  /// factor. It is disabled by default for three reasons:
  /// (1) Top-down allocation is simpler and easier to debug for targets that
  /// don't benefit from reversing the order.
  /// (2) Bottom-up allocation could result in poor evicition decisions on some
  /// targets affecting the performance of compiled code.
  /// (3) Bottom-up allocation is no longer guaranteed to optimally color.
  virtual bool reverseLocalAssignment() const { return false; }

If you are implementing your custom target, you could control the
priority of enqueue with 'reverseLocalAssignment()'. However, the
allocated registers can be evicted with weight comparison and the live
ranges can be split when the all of physical registers are consumed.
The priority on enqueue does not guarantee  allocation of physical
register. I am not code owner of register allocation so I might be
wrong.

Cheers,
JinGu Kang
2018년 11월 8일 (목) 오전 10:02, Dangeti Tharun kumar
<[hidden email]>님이 작성:

>
> Hi,
>
> I had a look at this  'calculateSpillWeightAndHint' function, spill weights are being calculated considering no of uses, defs, loops etc.
> Why not these weights be used as priority, seems they are good enough to serve as priority, instead doing it by their sizes?
>
> On Tue, Oct 30, 2018 at 5:39 PM jingu kang <[hidden email]> wrote:
>>
>> Hi Dangeti,
>>
>> As far as I know, 'calculateSpillWeightAndHint' considers loop
>> induction variable and the spill weight affects evict and spill. If it
>> is not enough for you, I guess you can add some heuristic code on the
>> function.
>>
>> Thanks,
>> JinGu Kang
>> 2018년 10월 30일 (화) 오전 11:51, Dangeti Tharun kumar via llvm-dev
>> <[hidden email]>님이 작성:
>> >
>> > Hi,
>> >
>> > In the Greedy RA, I see that the enqueue method adds higher priority to the live intervals based on their sizes.
>> >
>> > Isn't it makes sense to give priority to live intervals that start and end in a loop? Please let me know if the code is already achieving it in some way.
>> > Also consider correcting me, if this approach is wrong.
>> >
>> > --
>> > Regards,
>> > DTharun
>> > _______________________________________________
>> > LLVM Developers mailing list
>> > [hidden email]
>> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
>
> --
> Regards,
> DTharun
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev