Prevent LICM and machineLICM from hoisting convergent operations

[xiaoqing_wu]

Summary

Results of convergent operations are implicitly affected by the enclosing control flows and should not be hoisted out of arbitrary loops.

[foad]

Results of convergent operations are implicitly affected by the enclosing control flows and should not be hoisted out of arbitrary loops.

I thought it was OK to hoist them out of loops, but not to sink them into loops? The langref says they "should not be made control-dependent on additional values".

[arsenm]

This is allowed by the current definition. See D85603

[xiaoqing_wu]

In D90361#2361510, @foad wrote:

Results of convergent operations are implicitly affected by the enclosing control flows and should not be hoisted out of arbitrary loops.

I thought it was OK to hoist them out of loops, but not to sink them into loops? The langref says they "should not be made control-dependent on additional values".

In practice, convergent attribute has been used on operations that involve inter-thread communication which results are implicitly affected by the enclosing control flows. This was pointed out in the proposal in https://reviews.llvm.org/D85603. The definition in the current langref doesn't reflect how the attribute is used.

[xiaoqing_wu]

In D90361#2362068, @arsenm wrote:

This is allowed by the current definition. See D85603

D85603 requires changes to IR to model the dependency of convergent operations on their enclosing control flows.
The change in this review solves a different problem, it is to prevent hoisting with the existing IR.

[qcolombet]

Hi @foad, hi @arsenm

This is allowed by the current definition. See D85603

I was gong to say that @xiaoqing_wu's patch looks good to me, but I didn't think this was allowed by the current definition, but you're right it looks like it is.
Now, in practice is this something that works for you guys?

I would rather that we fix that asap than pinning that on the new convergence revamp, but if the current definition is okay for some users, I guess we'll have to explore a more target specific way to describe what is and what is not okay to hoist.

What do you think?

Cheers,
-Quentin

[arsenm]

In D90361#2364797, @qcolombet wrote:

Hi @foad, hi @arsenm

This is allowed by the current definition. See D85603

I was gong to say that @xiaoqing_wu's patch looks good to me, but I didn't think this was allowed by the current definition, but you're right it looks like it is.
Now, in practice is this something that works for you guys?

I would rather that we fix that asap than pinning that on the new convergence revamp, but if the current definition is okay for some users, I guess we'll have to explore a more target specific way to describe what is and what is not okay to hoist.

What do you think?

Cheers,
-Quentin

This moves in the more conservative direction more in line with the new definition. It's good for some convergent cases, but not all. For the machine level, I don't think we have an answer for the equivalent of the convergence operands yet.

llvm/lib/Transforms/Scalar/LICM.cpp

1167

isConvergent instead of directly checking the attribute

[xiaoqing_wu]

Changed LICM to call Function::isConvergent() method.

[xiaoqing_wu]

@nhaehnle Does the change look good to you?

@foad Please let me know if you have other questions or concerns regarding the change. Thanks.

[foad]

In D90361#2375045, @xiaoqing_wu wrote:

@foad Please let me know if you have other questions or concerns regarding the change. Thanks.

I think it could at least do with a comment explaining that LICM is being more conservative than the documented meaning of "convergent".

[xiaoqing_wu]

Added a comment on why convergent instructions should not be hoisted or sunk in LICM and machineLICM.

[xiaoqing_wu]

In D90361#2375626, @foad wrote:

I think it could at least do with a comment explaining that LICM is being more conservative than the documented meaning of "convergent".

Added some comments.

llvm/lib/CodeGen/MachineLICM.cpp

bool MachineLICMBase::IsLICMCandidate(MachineInstr &I) {
   // the loop which does not execute this load, so we can't hoist it. Loads
   // from constant memory are not safe to speculate all the time, for example
   // indexed load from a jump table.
   // Stores and side effects are already checked by isSafeToMove.
   if (I.mayLoad() && !mayLoadFromGOTOrConstantPool(I) &&
       !IsGuaranteedToExecute(I.getParent()))
     return false;
 
+  // Convergent attribute has been used on operations that involve inter-thread
+  // communication which results are implicitly affected by the enclosing
+  // control flows. It is not safe to hoist or sink such operations across
+  // control flow.
+  if (I.isConvergent())
+    return false;
+
   return true;
 }
 
 /// Returns true if the instruction is loop invariant.
 /// I.e., all virtual register operands are defined outside of the loop,
 /// physical registers aren't accessed explicitly, and there are no side
 /// effects that aren't captured by the operands or other flags.
 bool MachineLICMBase::IsLoopInvariantInst(MachineInstr &I) {

llvm/lib/Transforms/Scalar/LICM.cpp

if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
     // Don't sink or hoist dbg info; it's legal, but not useful.
     if (isa<DbgInfoIntrinsic>(I))
       return false;
 
     // Don't sink calls which can throw.
     if (CI->mayThrow())
       return false;
 
+    // Convergent attribute has been used on operations that involve
+    // inter-thread communication which results are implicitly affected by the
+    // enclosing control flows. It is not safe to hoist or sink such operations
+    // across control flow.
+    if (CI->isConvergent())
+      return false;
+
     using namespace PatternMatch;
     if (match(CI, m_Intrinsic<Intrinsic::assume>()))
       // Assumes don't actually alias anything or throw
       return true;
 
     if (match(CI, m_Intrinsic<Intrinsic::experimental_widenable_condition>()))
       // Widenable conditions don't actually alias anything or throw
       return true;

llvm/test/CodeGen/AMDGPU/machinelicm-convergent.mir

+# RUN: llc -march=amdgcn  -run-pass=early-machinelicm -o - %s | FileCheck %s
+
+# Test to check machine LICM does not hoist convergent instructions,
+# DS_PERMUTE_B32 in this example.
+
+---
+# CHECK-LABEL: name: _amdgpu_cs_main
+# CHECK: bb.1:
+# CHECK: DS_PERMUTE_B32
+
+name: _amdgpu_cs_main
+body: |
+  bb.0:
+    liveins: $vgpr0, $vgpr1
+    successors: %bb.1
+
+    %0:vgpr_32 = COPY $vgpr0
+    %1:vgpr_32 = COPY $vgpr1
+
+  bb.1:
+    successors: %bb.1, %bb.2
+
+    %2:vgpr_32 = DS_PERMUTE_B32 %0, %1, 0, implicit $exec
+    %3:vgpr_32 = V_ADD_CO_U32_e32 %0, %2, implicit-def $vcc, implicit $exec
+    S_CBRANCH_SCC1 %bb.1, implicit undef $scc
+    S_BRANCH %bb.2
+
+  bb.2:
+    $vgpr0 = COPY %3
+    S_ENDPGM 0
+
+...

llvm/test/Transforms/LICM/convergent.ll

+; RUN: opt < %s -S -licm | FileCheck %s
+
+; Check that we do not hoist convergent functions out of loop
+; CHECK: define i32 @test
+; CHECK: loop:
+; CHECK: call i32 @f
+
+define i32 @test(i32* nocapture noalias %x, i32* nocapture %y) {
+entry:
+  br label %loop
+
+loop:
+  %a = call i32 @f() nounwind readnone convergent
+  %exitcond = icmp ne i32 %a, 0
+  br i1 %exitcond, label %end, label %loop
+
+end:
+  ret i32 %a
+}
+
+declare i32 @f() nounwind readnone convergent