[LLVM] Do not speculate convergent calls

[sameerds]

Summary

This is a rebase of D85604 by Nicolai Haehnle <[e-mail]>. The
other changes in the original review have already been committed at different
points in time.

[arsenm]

llvm/lib/Analysis/ValueTracking.cpp

6006–6012

Should go through the CallBase rather than separately checking the callee and call site attributes. Also you're missing invokes

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

46

Add invoke test

[nikic]

Shouldn't this be covered by the speculatable attribute? A convergent function shouldn't be marked speculatable.

[arsenm]

In D153414#4437694, @nikic wrote:

Shouldn't this be covered by the speculatable attribute? A convergent function shouldn't be marked speculatable.

It depends. In the future we could contextually speculate convergent instructions (e.g. if the conditions reaching the point are uniform)

[nikic]

In D153414#4437698, @arsenm wrote:

In D153414#4437694, @nikic wrote:

Shouldn't this be covered by the speculatable attribute? A convergent function shouldn't be marked speculatable.

It depends. In the future we could contextually speculate convergent instructions (e.g. if the conditions reaching the point are uniform)

I still think that would not allow you to put speculatable on the function. A speculatable function has to be speculatable unconditionally. Absense of the speculatable attribute does not imply that the call cannot be speculated, just that we don't know that it is always safe to speculate.

[sameerds]

In D153414#4437705, @nikic wrote:

In D153414#4437698, @arsenm wrote:

It depends. In the future we could contextually speculate convergent instructions (e.g. if the conditions reaching the point are uniform)

I still think that would not allow you to put speculatable on the function. A speculatable function has to be speculatable unconditionally. Absense of the speculatable attribute does not imply that the call cannot be speculated, just that we don't know that it is always safe to speculate.

From a single-threaded point of view, a speculatable function is speculatable unconditionally, because the attribute is only reporting that certain side-effects will not happen. But whether it can be speculated across a divergent branch is decided by whether it is marked convergent. These two things are orthogonal. If a pass wants to speculate a convergent function across a uniform branch (or later even across a divergent branch if permitted by convergence tokesn), then this check for isConvergent will be combined by additional information passed from outside to isSafeToSpeculativelyExecute().

Theoretically, it is plausible that some function may be non-convergent and speculatable, but based on the environment (e.g., HIP or Vulcan or OpenCL), a call to such a function may be convergent. I don't actually have an example of such a thing right now, though it was considered at one point.

[arsenm]

Missing invoke/callbr by going through CallInst

[sameerds]

Abandoning. I agree with relying on attribute speculatable. If we figure out the conditions that make a convergent call speculatable, then at that time, we should use the appropriate attribute to record that fact. On the other hand, if speculation of a convergent call is dependent on the surrounding control flow, then we will probably have to do it as a separate optimization.

llvm/lib/Analysis/ValueTracking.cpp

6006–6012

Just below, all the other "call-like" instructions are simply assumed to be not safe for speculation.

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::Load: {
     return isDereferenceableAndAlignedPointer(LI->getPointerOperand(),
                                               LI->getType(), LI->getAlign(), DL,
                                               CtxI, AC, DT, TLI);
   }
   case Instruction::Call: {
     auto *CI = dyn_cast<const CallInst>(Inst);
     if (!CI)
       return false;
-    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:

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

 ; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -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, ptr %out) {
 entry:
   br i1 %cond, label %if.then, label %if.end
 
 if.then:
   store i32 5, ptr %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_speculate_convergent
+; CHECK: entry:
+; CHECK: then:
+; CHECK:   call i32 @speculatable_convergent
+; CHECK: end:
+define i32 @dont_speculate_convergent(i1 %cond1, i32 %in) {
+entry:
+  br i1 %cond1, label %then, label %end
+
+then:
+  %v = call i32 @speculatable_convergent(i32 %in)
+  br label %end
+
+end:
+  %r = phi i32 [ 0, %entry ], [ %v, %then ]
+  ret i32 %r
+}
+
 declare void @barrier() convergent
+declare i32 @speculatable_convergent(i32) convergent readnone speculatable