[llvm-dev] sinking in LICM

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

[llvm-dev] sinking in LICM

George Karpenkov via llvm-dev
Hi,

In the IR below, %tmp.7 and %tmp.8 are not used in loop, so we can sink
them in exit blocks. However, LICM do not handle this case because of
the check in isNotUsedInLoop() which returns false when a PHI node use
is hooked from a block inside the loop. I'm not sure if we really need
to have this check even when the PHI is outside the loop?

define i32 @test7(i32 %N, i32 %N2, i1 %C) {
Entry:
         br label %Loop
Loop:
         %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
         %tmp.6 = mul i32 %N, %N_addr.0.pn
         %tmp.7 = sub i32 %tmp.6, %N
         %tmp.8 = sub i32 %tmp.6, %N2
         %dec = add i32 %N_addr.0.pn, -1
         br i1 %C, label %ContLoop, label %Out12

ContLoop:
         %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
         br i1 %tmp.1, label %Loop, label %Out12

Out12:
   %tmp.7.8.lcssa1 = phi i32 [%tmp.8, %ContLoop], [%tmp.7, %Loop]
   ret i32 %tmp.7.8.lcssa1
}

Is there any problem I'm missing if we convert the above IR to the IR
below :

define i32 @test7(i32 %N, i32 %N2, i1 %C) {
Entry:
   br label %Loop

Loop:
   %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
   %dec = add i32 %N_addr.0.pn, -1
   br i1 %C, label %ContLoop, label %Out01

ContLoop:
   %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
   br i1 %tmp.1, label %Loop, label %Out02

Out01:
   %N_addr.0.pn.lcssa2 = phi i32 [ %N_addr.0.pn, %Loop ]
   %tmp.6.le1 = mul i32 %N, %N_addr.0.pn.lcssa2
   %tmp.8.new = sub i32 %tmp.6.le1, %N2
   br label %Out12

Out02:
   %N_addr.0.pn.lcssa = phi i32 [ %N_addr.0.pn, %ContLoop ]
   %tmp.6.le = mul i32 %N, %N_addr.0.pn.lcssa
   %tmp.7.new = sub i32 %tmp.6.le, %N
   br label %Out12

Out12:
   %tmp.7.8.ret = phi i32 [ %tmp.8.new, %Out01 ], [ %tmp.7.new, %Out02 ]
   ret i32 %tmp.7.8.ret
}

Thanks,
Jun


--
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] sinking in LICM

George Karpenkov via llvm-dev
Hi,

That sounds like a job for the SinkingPass. Doesn’t it catch this case?

Cheers,
-Quentin

> On Aug 10, 2017, at 11:34 AM, via llvm-dev <[hidden email]> wrote:
>
> Hi,
>
> In the IR below, %tmp.7 and %tmp.8 are not used in loop, so we can sink them in exit blocks. However, LICM do not handle this case because of the check in isNotUsedInLoop() which returns false when a PHI node use is hooked from a block inside the loop. I'm not sure if we really need to have this check even when the PHI is outside the loop?
>
> define i32 @test7(i32 %N, i32 %N2, i1 %C) {
> Entry:
>        br label %Loop
> Loop:
>        %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
>        %tmp.6 = mul i32 %N, %N_addr.0.pn
>        %tmp.7 = sub i32 %tmp.6, %N
>        %tmp.8 = sub i32 %tmp.6, %N2
>        %dec = add i32 %N_addr.0.pn, -1
>        br i1 %C, label %ContLoop, label %Out12
>
> ContLoop:
>        %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
>        br i1 %tmp.1, label %Loop, label %Out12
>
> Out12:
>  %tmp.7.8.lcssa1 = phi i32 [%tmp.8, %ContLoop], [%tmp.7, %Loop]
>  ret i32 %tmp.7.8.lcssa1
> }
>
> Is there any problem I'm missing if we convert the above IR to the IR below :
>
> define i32 @test7(i32 %N, i32 %N2, i1 %C) {
> Entry:
>  br label %Loop
>
> Loop:
>  %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
>  %dec = add i32 %N_addr.0.pn, -1
>  br i1 %C, label %ContLoop, label %Out01
>
> ContLoop:
>  %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
>  br i1 %tmp.1, label %Loop, label %Out02
>
> Out01:
>  %N_addr.0.pn.lcssa2 = phi i32 [ %N_addr.0.pn, %Loop ]
>  %tmp.6.le1 = mul i32 %N, %N_addr.0.pn.lcssa2
>  %tmp.8.new = sub i32 %tmp.6.le1, %N2
>  br label %Out12
>
> Out02:
>  %N_addr.0.pn.lcssa = phi i32 [ %N_addr.0.pn, %ContLoop ]
>  %tmp.6.le = mul i32 %N, %N_addr.0.pn.lcssa
>  %tmp.7.new = sub i32 %tmp.6.le, %N
>  br label %Out12
>
> Out12:
>  %tmp.7.8.ret = phi i32 [ %tmp.8.new, %Out01 ], [ %tmp.7.new, %Out02 ]
>  ret i32 %tmp.7.8.ret
> }
>
> Thanks,
> Jun
>
>
> --
> 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.
> _______________________________________________
> 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
|  
Report Content as Inappropriate

Re: [llvm-dev] sinking in LICM

George Karpenkov via llvm-dev
In reply to this post by George Karpenkov via llvm-dev
On 8/10/2017 11:34 AM, via llvm-dev wrote:

> Hi,
>
> In the IR below, %tmp.7 and %tmp.8 are not used in loop, so we can
> sink them in exit blocks. However, LICM do not handle this case
> because of the check in isNotUsedInLoop() which returns false when a
> PHI node use is hooked from a block inside the loop. I'm not sure if
> we really need to have this check even when the PHI is outside the loop?
>
> Is there any problem I'm missing if we convert the above IR to the IR
> below :
>

I can't see any problem, except that we don't have code to split a loop
exit like that.

-Eli

--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

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

Re: [llvm-dev] sinking in LICM

George Karpenkov via llvm-dev
In reply to this post by George Karpenkov via llvm-dev
On 2017-08-10 14:42, Quentin Colombet wrote:
> Hi,
>
> That sounds like a job for the SinkingPass. Doesn’t it catch this case?


Just ran SinkPass for the example IR. SinkPass sink only %tmp.8 from
%Loop to %ContLoop which is the last suitable place for sinking
dominating its use in %Out12. From the original IR I mentioned, we may
want to sink an instruction from the loop body to exit blocks. For me,
this seem to be a case we need to handle in LICM.


>
> Cheers,
> -Quentin
>> On Aug 10, 2017, at 11:34 AM, via llvm-dev <[hidden email]>
>> wrote:
>>
>> Hi,
>>
>> In the IR below, %tmp.7 and %tmp.8 are not used in loop, so we can
>> sink them in exit blocks. However, LICM do not handle this case
>> because of the check in isNotUsedInLoop() which returns false when a
>> PHI node use is hooked from a block inside the loop. I'm not sure if
>> we really need to have this check even when the PHI is outside the
>> loop?
>>
>> define i32 @test7(i32 %N, i32 %N2, i1 %C) {
>> Entry:
>>        br label %Loop
>> Loop:
>>        %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
>>        %tmp.6 = mul i32 %N, %N_addr.0.pn
>>        %tmp.7 = sub i32 %tmp.6, %N
>>        %tmp.8 = sub i32 %tmp.6, %N2
>>        %dec = add i32 %N_addr.0.pn, -1
>>        br i1 %C, label %ContLoop, label %Out12
>>
>> ContLoop:
>>        %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
>>        br i1 %tmp.1, label %Loop, label %Out12
>>
>> Out12:
>>  %tmp.7.8.lcssa1 = phi i32 [%tmp.8, %ContLoop], [%tmp.7, %Loop]
>>  ret i32 %tmp.7.8.lcssa1
>> }
>>
>> Is there any problem I'm missing if we convert the above IR to the IR
>> below :
>>
>> define i32 @test7(i32 %N, i32 %N2, i1 %C) {
>> Entry:
>>  br label %Loop
>>
>> Loop:
>>  %N_addr.0.pn = phi i32 [ %dec, %ContLoop ], [ %N, %Entry ]
>>  %dec = add i32 %N_addr.0.pn, -1
>>  br i1 %C, label %ContLoop, label %Out01
>>
>> ContLoop:
>>  %tmp.1 = icmp ne i32 %N_addr.0.pn, 1
>>  br i1 %tmp.1, label %Loop, label %Out02
>>
>> Out01:
>>  %N_addr.0.pn.lcssa2 = phi i32 [ %N_addr.0.pn, %Loop ]
>>  %tmp.6.le1 = mul i32 %N, %N_addr.0.pn.lcssa2
>>  %tmp.8.new = sub i32 %tmp.6.le1, %N2
>>  br label %Out12
>>
>> Out02:
>>  %N_addr.0.pn.lcssa = phi i32 [ %N_addr.0.pn, %ContLoop ]
>>  %tmp.6.le = mul i32 %N, %N_addr.0.pn.lcssa
>>  %tmp.7.new = sub i32 %tmp.6.le, %N
>>  br label %Out12
>>
>> Out12:
>>  %tmp.7.8.ret = phi i32 [ %tmp.8.new, %Out01 ], [ %tmp.7.new, %Out02 ]
>>  ret i32 %tmp.7.8.ret
>> }
>>
>> Thanks,
>> Jun
>>
>>
>> --
>> 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.
>> _______________________________________________
>> LLVM Developers mailing list
>> [hidden email]
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

--
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] sinking in LICM

George Karpenkov via llvm-dev
In reply to this post by George Karpenkov via llvm-dev
On 2017-08-10 14:55, Friedman, Eli wrote:

> On 8/10/2017 11:34 AM, via llvm-dev wrote:
>> Hi,
>>
>> In the IR below, %tmp.7 and %tmp.8 are not used in loop, so we can
>> sink them in exit blocks. However, LICM do not handle this case
>> because of the check in isNotUsedInLoop() which returns false when a
>> PHI node use is hooked from a block inside the loop. I'm not sure if
>> we really need to have this check even when the PHI is outside the
>> loop?
>>
>> Is there any problem I'm missing if we convert the above IR to the IR
>> below :
>>
>
> I can't see any problem, except that we don't have code to split a
> loop exit like that.


Yes, we should add code to split the loop exit to support such cases.
Before that I wanted to understand why we currently have such check for
PHI uses in isNotUsedInLoop()? Is this a bug? or is there a case we need
to consider?


>
> -Eli


--
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.
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [llvm-dev] sinking in LICM

George Karpenkov via llvm-dev
On 8/10/2017 12:32 PM, [hidden email] wrote:

> On 2017-08-10 14:55, Friedman, Eli wrote:
>> On 8/10/2017 11:34 AM, via llvm-dev wrote:
>>> Hi,
>>>
>>> In the IR below, %tmp.7 and %tmp.8 are not used in loop, so we can
>>> sink them in exit blocks. However, LICM do not handle this case
>>> because of the check in isNotUsedInLoop() which returns false when a
>>> PHI node use is hooked from a block inside the loop. I'm not sure if
>>> we really need to have this check even when the PHI is outside the
>>> loop?
>>>
>>> Is there any problem I'm missing if we convert the above IR to the
>>> IR below :
>>>
>>
>> I can't see any problem, except that we don't have code to split a
>> loop exit like that.
>
>
> Yes, we should add code to split the loop exit to support such cases.
> Before that I wanted to understand why we currently have such check
> for PHI uses in isNotUsedInLoop()? Is this a bug? or is there a case
> we need to consider?
>

I think the only reason we check PHI nodes outside the loop in
isNotUsedInLoop() is that we don't have code to split the loop exit.

-Eli

--
Employee of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project

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