[EarlyCSE] Do not CSE convergent calls with memory effects

[foad]

Summary

D149348 did this for readnone calls, which are handled by SimpleValue.
This patch does the same for all other CSEable calls, which are handled
by CallValue.

[arsenm]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

144

Maybe should be checking nosync instead?

[foad]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

144

How is that related?

[arsenm]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

144

The comment here and special case of coroutines seems like it was hacking around the general check of nosync. In a roundabout way checking nosync is the same as convergent. IIRC the interaction between them is no-convergent + memory(none) implies nosync

[nikic]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

144

The coroutine check has no relation to nosync. It's hacking around a weakness in memory effect modelling that is unrelated to synchronization.

[nhaehnle]

I'm not familiar with the code but the thrust of it makes sense. We should probably still try to CSE calls that are in the same basic block, though. Is that easy to do?

[foad]

I need to rethink. The patch as-is does not make much sense because @llvm.read_register is not readnone.

[arsenm]

llvm/test/Transforms/EarlyCSE/AMDGPU/convergent-call.ll

22

I think something is wrong here but you should test with something normal and not read_register

[foad]

Rethink.

[jdoerfert]

Can we have a test with 2 convergent calls in the same block, or do we have one already?

[foad]

llvm/test/Transforms/EarlyCSE/AMDGPU/convergent-call.ll

47

@jdoerfert it is here. (It's not upstream yet - this comes from a patch that I only have locally.)

[arsenm]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

336

CallBase? Are invokes ever CSEable?

llvm/test/Transforms/EarlyCSE/AMDGPU/convergent-call.ll

27

Should still add another test that doesn't involve read_register and uses a proper convergent call

[arsenm]

still would like a test that's more normal than read_register

[foad]

Add test with @llvm.amdgcn.live.mask

[foad]

In D153151#4497484, @arsenm wrote:

still would like a test that's more normal than read_register

There aren't really any normal readonly convergent intrinsics. @llvm.amdgcn.live.mask is currently readonly so I used that - but it seems to me it should probably be convergent readnone.

[arsenm]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

545

Is this supposed to implicitly assume invokes and callbr can't reach here?

[foad]

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

545

Yes. This is checked in CallValue::canHandle.

llvm/lib/Transforms/Scalar/EarlyCSE.cpp

if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
              // FIXME: Currently the calls which may access the thread id may
              // be considered as not accessing the memory. But this is
              // problematic for coroutines, since coroutines may resume in a
              // different thread. So we disable the optimization here for the
              // correctness. However, it may block many other correct
              // optimizations. Revert this one when we detect the memory
              // accessing kind more precisely.
              !CI->getFunction()->isPresplitCoroutine();
     }
     return isa<CastInst>(Inst) || isa<UnaryOperator>(Inst) ||
            isa<BinaryOperator>(Inst) || isa<GetElementPtrInst>(Inst) ||
            isa<CmpInst>(Inst) || isa<SelectInst>(Inst) ||
            isa<ExtractElementInst>(Inst) || isa<InsertElementInst>(Inst) ||
            isa<ShuffleVectorInst>(Inst) || isa<ExtractValueInst>(Inst) ||
            isa<InsertValueInst>(Inst) || isa<FreezeInst>(Inst);
   }
 };
static bool matchSelectWithOptionalNotCond(Value *V, Value *&Cond, Value *&A,
   case CmpInst::ICMP_SLE: Flavor = SPF_SMIN; break;
   case CmpInst::ICMP_SGE: Flavor = SPF_SMAX; break;
   default: break;
   }
 
   return true;
 }
 
+static unsigned hashCallInst(CallInst *CI) {
+  // Don't CSE convergent calls in different basic blocks, because they
+  // implicitly depend on the set of threads that is currently executing.
+  if (CI->isConvergent()) {
+    return hash_combine(
+        CI->getOpcode(), CI->getParent(),
+        hash_combine_range(CI->value_op_begin(), CI->value_op_end()));
+  }
+  return hash_combine(
+      CI->getOpcode(),
+      hash_combine_range(CI->value_op_begin(), CI->value_op_end()));
+}
+
 static unsigned getHashValueImpl(SimpleValue Val) {
   Instruction *Inst = Val.Inst;
   // Hash in all of the operands as pointers.
   if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Inst)) {
     Value *LHS = BinOp->getOperand(0);
     Value *RHS = BinOp->getOperand(1);
     if (BinOp->isCommutative() && BinOp->getOperand(0) > BinOp->getOperand(1))
       std::swap(LHS, RHS);
static unsigned getHashValueImpl(SimpleValue Val) {
   // not real values, but indices into statepoint's argument list.
   // Get values they point to.
   if (const GCRelocateInst *GCR = dyn_cast<GCRelocateInst>(Inst))
     return hash_combine(GCR->getOpcode(), GCR->getOperand(0),
                         GCR->getBasePtr(), GCR->getDerivedPtr());
 
   // Don't CSE convergent calls in different basic blocks, because they
   // implicitly depend on the set of threads that is currently executing.
-  if (CallInst *CI = dyn_cast<CallInst>(Inst); CI && CI->isConvergent()) {
-    return hash_combine(
-        Inst->getOpcode(), Inst->getParent(),
-        hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
-  }
+  if (CallInst *CI = dyn_cast<CallInst>(Inst))
+    return hashCallInst(CI);
 
   // Mix in the opcode.
   return hash_combine(
       Inst->getOpcode(),
       hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
 }
 
 unsigned DenseMapInfo<SimpleValue>::getHashValue(SimpleValue Val) {

 };
 
 } // end namespace llvm
 
 unsigned DenseMapInfo<CallValue>::getHashValue(CallValue Val) {
   Instruction *Inst = Val.Inst;
 
   // Hash all of the operands as pointers and mix in the opcode.
-  return hash_combine(
-      Inst->getOpcode(),
-      hash_combine_range(Inst->value_op_begin(), Inst->value_op_end()));
+  return hashCallInst(cast<CallInst>(Inst));
 }
 
 bool DenseMapInfo<CallValue>::isEqual(CallValue LHS, CallValue RHS) {
-  Instruction *LHSI = LHS.Inst, *RHSI = RHS.Inst;
   if (LHS.isSentinel() || RHS.isSentinel())
-    return LHSI == RHSI;
+    return LHS.Inst == RHS.Inst;
+
+  CallInst *LHSI = cast<CallInst>(LHS.Inst);
+  CallInst *RHSI = cast<CallInst>(RHS.Inst);
+
+  // Convergent calls implicitly depend on the set of threads that is
+  // currently executing, so conservatively return false if they are in
+  // different basic blocks.
+  if (LHSI->isConvergent() && LHSI->getParent() != RHSI->getParent())
+      return false;
 
   return LHSI->isIdenticalTo(RHSI);
 }
 
 //===----------------------------------------------------------------------===//
 // EarlyCSE implementation
 //===----------------------------------------------------------------------===//
 

llvm/test/Transforms/EarlyCSE/AMDGPU/convergent-call.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
 ; RUN: opt < %s -S -mtriple=amdgcn-- -passes=early-cse -earlycse-debug-hash | FileCheck %s
 
 ; Should not CSE calls marked as convergent, even if the callee is not convergent.
 define i32 @test(i32 %cond) {
 ; CHECK-LABEL: define i32 @test
 ; CHECK-SAME: (i32 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X1:%.*]] = call i32 @llvm.read_register.i32(metadata [[META0:![0-9]+]]) #[[ATTR1:[0-9]+]]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[COND]], 0
 ; CHECK-NEXT:    br i1 [[CMP]], label [[IF:%.*]], label [[END:%.*]]
 ; CHECK:       if:
+; CHECK-NEXT:    [[Y1:%.*]] = call i32 @llvm.read_register.i32(metadata [[META0]]) #[[ATTR1]]
 ; CHECK-NEXT:    br label [[END]]
 ; CHECK:       end:
-; CHECK-NEXT:    [[Y2:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X1]], [[IF]] ]
+; CHECK-NEXT:    [[Y2:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[Y1]], [[IF]] ]
 ; CHECK-NEXT:    [[RET:%.*]] = add i32 [[X1]], [[Y2]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   ; %x = ballot operation over all lanes.
   %x1 = call i32 @llvm.read_register.i32(metadata !{!"exec_lo"}) convergent
   %cmp = icmp eq i32 %cond, 0
   br i1 %cmp, label %if, label %end
 
 if:
   ; %y = ballot operation over lanes satisfying %cond.
   %y1 = call i32 @llvm.read_register.i32(metadata !{!"exec_lo"}) convergent
   br label %end
 
 end:
   %y2 = phi i32 [0, %entry], [%y1, %if]
   %ret = add i32 %x1, %y2
   ret i32 %ret
 }
 
 define i32 @samebb(i32 %cond) {
 ; CHECK-LABEL: define i32 @samebb
 ; CHECK-SAME: (i32 [[COND:%.*]]) {
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @llvm.read_register.i32(metadata [[META0]]) #[[ATTR1]]
 ; CHECK-NEXT:    [[RET:%.*]] = add i32 [[X]], [[X]]
 ; CHECK-NEXT:    ret i32 [[RET]]
 ;
 entry:
   %x = call i32 @llvm.read_register.i32(metadata !{!"exec_lo"}) convergent
   %y = call i32 @llvm.read_register.i32(metadata !{!"exec_lo"}) convergent
   %ret = add i32 %x, %y
   ret i32 %ret
 }
 
 declare i32 @llvm.read_register.i32(metadata)