llvm dev - Oct 2017 - Less aggressive on the first allocation of CSR if detecting an early exit

When compiling C code below for AArach64, I saw that shrink-wrapping didn't
happen due to the very early uses of CSRs in the entry block. So CSR
spills/reloads are executed even when the early exit block is taken.

 

int getI(int i);

 

int foo(int *P, int i) {

   if (i>0)

     return P[i];

 

   i = getI(i);

   return P[i];

}

 

It's not that hard to find such cases where RegAllocGreedy aggressively
allocates a CSRs when a live range expands across a call-site.  That's
because of the conservatively initialized CSRCost, causing RegAllocGreedy to
strongly favour allocating a CSR over splitting a region. Since allocation
of CSRs requires the cost of spilling CSRs, allocating CSRs is not always
beneficial. Like the case above, if a function has an early exit code, we
may want to be less aggressive on the first allocation of CSR in the entry
block by increasing the CSRCost. 

 

Previously, I proposed https://reviews.llvm.org/D34608 in this matter, but
the way I detect the profitable cases and the way I increase the CRSCost was
somewhat unclear. Now, I'm thinking to less aggressive on the first
allocation of CSR in the entry block in case where the function has an early
exit so that encourage more shrink-wrapping and avoid executing CSR
spill/recover when the early exit is taken. By sending this out, I just want
to get any high level feedback early. Please let me know if anyone has any
opinion about this. 

 

Thanks,
Jun

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/63368b72/attachment-0001.html>

On 10/27/2017 03:32 PM, Jun Lim via llvm-dev wrote:
>
> When compiling C code below for AArach64, I saw that shrink-wrapping 
> didn't happen due to the very early uses of CSRs in the entry block. 
> So CSR spills/reloads are executed even when the early exit block is 
> taken.
>
> int getI(int i);
>
> int foo(int *P, int i) {
>
>    if (i>0)
>
>      return P[i];
>
>    i = getI(i);
>
>    return P[i];
>
> }
>
> It's not that hard to find such cases where RegAllocGreedy 
> aggressively allocates a CSRs when a live range expands across a 
> call-site.  That's because of the conservatively initialized CSRCost, 
> causing RegAllocGreedy to strongly favour allocating a CSR over 
> splitting a region. Since allocation of CSRs requires the cost of 
> spilling CSRs, allocating CSRs is not always beneficial. Like the case 
> above, if a function has an early exit code, we may want to be less 
> aggressive on the first allocation of CSR in the entry block by 
> increasing the CSRCost.
>
> Previously, I proposed https://reviews.llvm.org/D34608 in this matter, 
> but the way I detect the profitable cases and the way I increase the 
> CRSCost was somewhat unclear. Now, I'm thinking to less aggressive on 
> the first allocation of CSR in the entry block in case where the 
> function has an early exit so that encourage more shrink-wrapping and 
> avoid executing CSR spill/recover when the early exit is taken. By 
> sending this out, I just want to get any high level feedback early. 
> Please let me know if anyone has any opinion about this.
>
So the heuristic will have nothing to do with the presence of calls? 
Might this increase spilling in loops?

  -Hal
> Thanks,
> Jun
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171027/1adafae7/attachment.html>

On 2017-10-27 19:50, Hal Finkel wrote:
> On 10/27/2017 03:32 PM, Jun Lim via llvm-dev wrote:
> 
>> When compiling C code below for AArach64, I saw that shrink-wrapping
>> didn't happen due to the very early uses of CSRs in the entry
block.
>> So CSR spills/reloads are executed even when the early exit block is
>> taken.
>> 
>> int getI(int i);
>> 
>> int foo(int *P, int i) {
>> 
>> if (i>0)
>> 
>> return P[i];
>> 
>> i = getI(i);
>> 
>> return P[i];
>> 
>> }
>> 
>> It's not that hard to find such cases where RegAllocGreedy
>> aggressively allocates a CSRs when a live range expands across a
>> call-site.  That's because of the conservatively initialized
>> CSRCost, causing RegAllocGreedy to strongly favour allocating a CSR
>> over splitting a region. Since allocation of CSRs requires the cost
>> of spilling CSRs, allocating CSRs is not always beneficial. Like the
>> case above, if a function has an early exit code, we may want to be
>> less aggressive on the first allocation of CSR in the entry block by
>> increasing the CSRCost.
>> 
>> Previously, I proposed https://reviews.llvm.org/D34608 in this
>> matter, but the way I detect the profitable cases and the way I
>> increase the CRSCost was somewhat unclear. Now, I'm thinking to
less
>> aggressive on the first allocation of CSR in the entry block in case
>> where the function has an early exit so that encourage more
>> shrink-wrapping and avoid executing CSR spill/recover when the early
>> exit is taken. By sending this out, I just want to get any high
>> level feedback early. Please let me know if anyone has any opinion
>> about this.
> 
> So the heuristic will have nothing to do with the presence of calls?
> Might this increase spilling in loops?
> 
>  -Hal
> 
Before allowing the first allocation from CSRs, I will check if the 
virtual register is really live across a call in other blocks. If the 
function have a call in entry or exit, we don't need to increase the 
CSRCost. This heuristic will be applied only for the very first 
allocation from CSRs only in the entry block when the function has an 
early exit; if a CSR is already allocated in the function, we will use 
the current default global CSRCost.

Even after increasing the CSRCost, we should end up allocating the first 
CSR if the cost of splitting the live-range is still higher than the 
increased CSRCost. I believe the amount we want to increase the CSRCost 
must be target-dependent, but it must be conservative enough to avoid 
too many copies in the related spots.

Thanks,
Jun
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> 
> --
> Hal Finkel
> Lead, Compiler Technology and Programming Languages
> Leadership Computing Facility
> Argonne National Laboratory
-- 
Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm 
Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a 
Linux Foundation Collaborative Project.