SimplifyCFG: prevent certain transforms on convergent operations

[nhaehnle]

Summary

These changes are justified by the new controlled convergent
operations semantics. This change is taken from the otherwise obsolete
https://reviews.llvm.org/D68994

Change-Id: I4f8b780e8c69f98389e4094477fd03e88fc95573

[arsenm]

llvm/lib/Analysis/ValueTracking.cpp

4468–4473

Sink this below the convergent check?

[nhaehnle]

llvm/lib/Analysis/ValueTracking.cpp

4468–4473

Will do.

[efriedma]

llvm/lib/Analysis/ValueTracking.cpp

4479

I can't imagine a function that makes sense to mark both convergent and speculatable.

[nhaehnle]

• sink use getCalledFunction() below convergence check in ValueTracking

[nhaehnle]

llvm/lib/Analysis/ValueTracking.cpp

4479

An example would be a shuffle operation:

if (cond1) {
  y = shuffle(x, srcIdx, token);
  foo(y);
} else if (cond2) {
  y = shuffle(x, srcIdx, token);
  bar(y)
}

If any(cond1 || cond2) is sufficiently likely, the following is more efficient:

y = shuffle(x, srcIdx, token);
if (cond1) {
  foo(y);
} else if (cond2) {
  bar(y)
}

This transform is correct for the underlying hardware implementation if srcIdx can be out-of-range without causing undefined behavior.

convergent speculatable would still indicate that the transform is forbidden, because it changes the set of communicating threads, but I think we're going to want attributes that partially relax convergent again. In this case, we'd allow changing the set of communicating threads to a superset.

[efriedma]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

if (mustSuppressSpeculation(*LI))
       return false;
     const DataLayout &DL = LI->getModule()->getDataLayout();
     return isDereferenceableAndAlignedPointer(
         LI->getPointerOperand(), LI->getType(), MaybeAlign(LI->getAlignment()),
         DL, CtxI, DT);
   }
   case Instruction::Call: {
     auto *CI = cast<const CallInst>(Inst);
-    const Function *Callee = CI->getCalledFunction();
+
+    // The called function depends on the set of threads executing it, which
+    // could change if the call is moved to a different location in control
+    // flow.
+    if (CI->isConvergent())
+      return false;
 
     // The called function could have undefined behavior or side-effects, even
     // if marked readnone nounwind.
+    const Function *Callee = CI->getCalledFunction();
     return Callee && Callee->isSpeculatable();
   }
   case Instruction::VAArg:
   case Instruction::Alloca:
   case Instruction::Invoke:
   case Instruction::CallBr:
   case Instruction::PHI:
   case Instruction::Store:
   case Instruction::Ret:
   case Instruction::Br:

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

while (isa<DbgInfoIntrinsic>(I2))
       I2 = &*BB2_Itr++;
   }
   // FIXME: Can we define a safety predicate for CallBr?
   if (isa<PHINode>(I1) || !I1->isIdenticalToWhenDefined(I2) ||
       (isa<InvokeInst>(I1) && !isSafeToHoistInvoke(BB1, BB2, I1, I2)) ||
       isa<CallBrInst>(I1))
     return false;
 
+  // Cannot hoist convergent calls since that could change the set of threads
+  // with which they communicate.
+  if (const auto *C = dyn_cast<CallBase>(I1)) {
+    if (C->isConvergent())
+      return false;
+  }
+
   BasicBlock *BIParent = BI->getParent();
 
   bool Changed = false;
 
   auto _ = make_scope_exit([&]() {
     if (Changed)
       ++NumHoistCommonCode;
   });
static bool canSinkInstructions(
   // PHI instruction in the successor.
   bool HasUse = !Insts.front()->user_empty();
   for (auto *I : Insts) {
     // These instructions may change or break semantics if moved.
     if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
         I->getType()->isTokenTy())
       return false;
 
+    if (const auto *C = dyn_cast<CallBase>(I)) {
       // Conservatively return false if I is an inline-asm instruction. Sinking
       // and merging inline-asm instructions can potentially create arguments
       // that cannot satisfy the inline-asm constraints.
       // If the instruction has nomerge attribute, return false.
-    if (const auto *C = dyn_cast<CallBase>(I))
       if (C->isInlineAsm() || C->cannotMerge())
         return false;
 
+      // Do not sink convergent calls, as sinking may affect the set of threads
+      // with which the convergent operation communicates.
+      if (C->isConvergent())
+        return false;
+    }
+
     // Each instruction must have zero or one use.
     if (HasUse && !I->hasOneUse())
       return false;
     if (!HasUse && !I->user_empty())
       return false;
   }
 
   const Instruction *I0 = Insts.front();

llvm/test/Transforms/SimplifyCFG/attr-convergent.ll

 ; RUN: opt < %s -simplifycfg -S | FileCheck %s
 
 ; Checks that the SimplifyCFG pass won't duplicate a call to a function marked
 ; convergent.
 ;
+; CHECK-LABEL: @check
 ; CHECK: call void @barrier
 ; CHECK-NOT: call void @barrier
 define void @check(i1 %cond, i32* %out) {
 entry:
   br i1 %cond, label %if.then, label %if.end
 
 if.then:
   store i32 5, i32* %out
   br label %if.end
 
 if.end:
   %x = phi i1 [ true, %entry ], [ false, %if.then ]
   call void @barrier()
   br i1 %x, label %cond.end, label %cond.false
 
 cond.false:
   br label %cond.end
 
 cond.end:
   ret void
 }
 
+; CHECK-LABEL: @dont_merge_convergent
+; CHECK: if.then:
+; CHECK:   %ballot.then = call i32 @ballot
+; CHECK: if.else:
+; CHECK:   %ballot.else = call i32 @ballot
+define i32 @dont_merge_convergent(i1 %cond1, i1 %cond2) {
+entry:
+  %tok = call token @llvm.experimental.convergence.anchor()
+  br i1 %cond1, label %if.then, label %if.else
+
+if.then:
+  %ballot.then = call i32 @ballot(i1 %cond2) [ "convergencectrl"(token %tok) ]
+  br label %end
+
+if.else:
+  %ballot.else = call i32 @ballot(i1 %cond2) [ "convergencectrl"(token %tok) ]
+  br label %end
+
+end:
+  %ballot = phi i32 [ %ballot.then, %if.then ], [ %ballot.else, %if.else ]
+  ret i32 %ballot
+}
+
+; CHECK-LABEL: @dont_speculate_convergent
+; CHECK: entry:
+; CHECK: then:
+; CHECK:   call i32 @speculatable_convergent
+; CHECK: end:
+define i32 @dont_speculate_convergent(i1 %cond1, i32 %in) {
+entry:
+  %tok = call token @llvm.experimental.convergence.anchor()
+  br i1 %cond1, label %then, label %end
+
+then:
+  %v = call i32 @speculatable_convergent(i32 %in) [ "convergencectrl"(token %tok) ]
+  br label %end
+
+end:
+  %r = phi i32 [ 0, %entry ], [ %v, %then ]
+  ret i32 %r
+}
+
+declare token @llvm.experimental.convergence.anchor()
+
+declare i32 @ballot(i1 %arg) convergent readnone
+declare i32 @speculatable_convergent(i32) convergent readnone speculatable
+
 declare void @barrier() convergent