sinking in LICM

Project Infrastructure LLVM Dev List Archives
1

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

2

Hi,

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

Cheers,
-Quentin

3

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

-Eli

4

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.

5

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?

6

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