[attrs] Handle convergent CallSites.

[jlebar]

Summary

Previously we had a notion of convergent functions but not of convergent
calls. This is insufficient to correctly analyze calls where the target
is unknown, e.g. indirect calls.

Now a call is convergent if it targets a known-convergent function, or
if it's explicitly marked as convergent. As usual, we can remove
convergent where we can prove that no convergent operations are
performed in the call.

Originally landed as r261544, then reverted in r261544 for (incidental)
build breakage. Re-landed here with no changes.

[jlebar]

This should be entirely or mostly good-to-go, but would like a once-over by chanclerc, since the last attempt at landing this, D17317, didn't get his final approval.

[jlebar]

Chandler, friendly ping.

[chandlerc]

Very nice. Two small nits below, feel free to land with those addressed.

lib/Transforms/IPO/FunctionAttrs.cpp

910–919 ↗

(On Diff #49422)

Perhaps its just me, but I would find this easier to read as a single loop over the functions in the SCC, and three conditions on which we return false (with the exact comments you currently have, those are awesome).

923 ↗

(On Diff #49422)

"if is CS a" -> "if CS is a"

[jlebar]

lib/Transforms/IPO/FunctionAttrs.cpp

910–919 ↗

(On Diff #49422)

Hm, it's slightly more complicated than that, because the first 'if' is a !any_of. But I went ahead and made the change, because I think it's justified on the grounds of not wanting to iterate over a non-convergent function's instructions if it happens to be in an SCC with a convergent function.

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

for (Function *F : SCCNodes) {
       ++NumNonNullReturn;
       MadeChange = true;
     }
   }
 
   return MadeChange;
 }
 
-/// Removes convergent attributes where we can prove that none of the SCC's
-/// callees are themselves convergent.  Returns true if successful at removing
-/// the attribute.
+/// Remove the convergent attribute from all functions in the SCC if every
+/// callsite within the SCC is not convergent (except for calls to functions
+/// within the SCC).  Returns true if changes were made.
 static bool removeConvergentAttrs(const SCCNodeSet &SCCNodes) {
-  // Determines whether a function can be made non-convergent, ignoring all
-  // other functions in SCC.  (A function can *actually* be made non-convergent
-  // only if all functions in its SCC can be made convergent.)
-  auto CanRemoveConvergent = [&](Function *F) {
-    if (!F->isConvergent())
-      return true;
+  // For every function in SCC, ensure that either
+  //  * it is not convergent, or
+  //  * we can remove its convergent attribute.
+  bool HasConvergentFn = false;
+  for (Function *F : SCCNodes) {
+    if (!F->isConvergent()) continue;
+    HasConvergentFn = true;
 
-    // Can't remove convergent from declarations.
-    if (F->isDeclaration())
-      return false;
+    // Can't remove convergent from function declarations.
+    if (F->isDeclaration()) return false;
 
-    for (Instruction &I : instructions(*F))
-      if (auto CS = CallSite(&I)) {
-        // Can't remove convergent if any of F's callees -- ignoring functions
-        // in the SCC itself -- are convergent. This needs to consider both
-        // function calls and intrinsic calls. We also assume indirect calls
-        // might call a convergent function.
-        // FIXME: We should revisit this when we put convergent onto calls
-        // instead of functions so that indirect calls which should be
-        // convergent are required to be marked as such.
-        Function *Callee = CS.getCalledFunction();
-        if (!Callee || (SCCNodes.count(Callee) == 0 && Callee->isConvergent()))
-          return false;
-      }
+    // Can't remove convergent if any of our functions has a convergent call to a
+    // function not in the SCC.
+    for (Instruction &I : instructions(*F)) {
+      CallSite CS(&I);
+      // Bail if CS is a convergent call to a function not in the SCC.
+      if (CS && CS.isConvergent() &&
+          SCCNodes.count(CS.getCalledFunction()) == 0)
+  }
 
-    return true;
-  };
-
-  // We can remove the convergent attr from functions in the SCC if they all
-  // can be made non-convergent (because they call only non-convergent
-  // functions, other than each other).
-  if (!llvm::all_of(SCCNodes, CanRemoveConvergent))
-    return false;
+  // If the SCC doesn't have any convergent functions, we have nothing to do.
+  if (!HasConvergentFn) return false;
 
-  // If we got here, all of the SCC's callees are non-convergent. Therefore all
-  // of the SCC's functions can be marked as non-convergent.
+  // If we got here, all of the calls the SCC makes to functions not in the SCC
+  // are non-convergent.  Therefore all of the SCC's functions can also be made
+  // non-convergent.  We'll remove the attr from the callsites in
+  // InstCombineCalls.
   for (Function *F : SCCNodes) {
-    if (F->isConvergent())
-      DEBUG(dbgs() << "Removing convergent attr from " << F->getName() << "\n");
+    if (!F->isConvergent()) continue;
+
+    DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
+                 << "\n");
     F->setNotConvergent();
   }
   return true;
 }
 
 static bool setDoesNotRecurse(Function &F) {
   if (F.doesNotRecurse())
     return false;

llvm/trunk/lib/Transforms/InstCombine/InstCombineCalls.cpp

Instruction *InstCombiner::visitCallSite(CallSite CS) {
   }
 
   // If the callee is a pointer to a function, attempt to move any casts to the
   // arguments of the call/invoke.
   Value *Callee = CS.getCalledValue();
   if (!isa<Function>(Callee) && transformConstExprCastCall(CS))
     return nullptr;
 
-  if (Function *CalleeF = dyn_cast<Function>(Callee))
+  if (Function *CalleeF = dyn_cast<Function>(Callee)) {
+    // Remove the convergent attr on calls when the callee is not convergent.
+    if (CS.isConvergent() && !CalleeF->isConvergent()) {
+      DEBUG(dbgs() << "Removing convergent attr from instr "
+                   << CS.getInstruction() << "\n");
+      CS.setNotConvergent();
+      return CS.getInstruction();
+    }
+
     // If the call and callee calling conventions don't match, this call must
     // be unreachable, as the call is undefined.
     if (CalleeF->getCallingConv() != CS.getCallingConv() &&
         // Only do this for calls to a function with a body.  A prototype may
         // not actually end up matching the implementation's calling conv for a
         // variety of reasons (e.g. it may be written in assembly).
         !CalleeF->isDeclaration()) {
       Instruction *OldCall = CS.getInstruction();
       new StoreInst(ConstantInt::getTrue(Callee->getContext()),
                 UndefValue::get(Type::getInt1PtrTy(Callee->getContext())),
                                   OldCall);
       // If OldCall does not return void then replaceAllUsesWith undef.
       // This allows ValueHandlers and custom metadata to adjust itself.
       if (!OldCall->getType()->isVoidTy())
         replaceInstUsesWith(*OldCall, UndefValue::get(OldCall->getType()));
       if (isa<CallInst>(OldCall))
         return eraseInstFromFunction(*OldCall);
 
       // We cannot remove an invoke, because it would change the CFG, just
       // change the callee to a null pointer.
       cast<InvokeInst>(OldCall)->setCalledFunction(
                                     Constant::getNullValue(CalleeF->getType()));
       return nullptr;
     }
+  }
 
   if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
     // If CS does not return void then replaceAllUsesWith undef.
     // This allows ValueHandlers and custom metadata to adjust itself.
     if (!CS.getInstruction()->getType()->isVoidTy())
       replaceInstUsesWith(*CS.getInstruction(),
                           UndefValue::get(CS.getInstruction()->getType()));
 

llvm/trunk/test/Transforms/FunctionAttrs/convergent.ll

-; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s
+; RUN: opt -functionattrs -S < %s | FileCheck %s
 
 ; CHECK: Function Attrs
 ; CHECK-NOT: convergent
 ; CHECK-NEXT: define i32 @nonleaf()
 define i32 @nonleaf() convergent {
   %a = call i32 @leaf()
   ret i32 %a
 }

 ; CHECK-SAME: convergent
 ; CHECK-NEXT: declare i32 @k()
 declare i32 @k() convergent
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: convergent
 ; CHECK-NEXT: define i32 @extern()
 define i32 @extern() convergent {
+  %a = call i32 @k() convergent
+  ret i32 %a
+}
+
+; Convergent should not be removed on the function here.  Although the call is
+; not explicitly convergent, it picks up the convergent attr from the callee.
+;
+; CHECK: Function Attrs
+; CHECK-SAME: convergent
+; CHECK-NEXT: define i32 @extern_non_convergent_call()
+define i32 @extern_non_convergent_call() convergent {
   %a = call i32 @k()
   ret i32 %a
 }
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: convergent
-; CHECK-NEXT: define i32 @call_extern()
-define i32 @call_extern() convergent {
-  %a = call i32 @extern()
+; CHECK-NEXT: define i32 @indirect_convergent_call(
+define i32 @indirect_convergent_call(i32 ()* %f) convergent {
+   %a = call i32 %f() convergent
+   ret i32 %a
+}
+; Give indirect_non_convergent_call the norecurse attribute so we get a
+; "Function Attrs" comment in the output.
+;
+; CHECK: Function Attrs
+; CHECK-NOT: convergent
+; CHECK-NEXT: define i32 @indirect_non_convergent_call(
+define i32 @indirect_non_convergent_call(i32 ()* %f) convergent norecurse {
+   %a = call i32 %f()
    ret i32 %a
 }
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: convergent
 ; CHECK-NEXT: declare void @llvm.cuda.syncthreads()
 declare void @llvm.cuda.syncthreads() convergent
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: convergent
 ; CHECK-NEXT: define i32 @intrinsic()
 define i32 @intrinsic() convergent {
+  ; Implicitly convergent, because the intrinsic is convergent.
   call void @llvm.cuda.syncthreads()
   ret i32 0
 }
 
-@xyz = global i32 ()* null
-; CHECK: Function Attrs
-; CHECK-SAME: convergent
-; CHECK-NEXT: define i32 @functionptr()
-define i32 @functionptr() convergent {
-  %1 = load i32 ()*, i32 ()** @xyz
-  %2 = call i32 %1()
-  ret i32 %2
-}
-
 ; CHECK: Function Attrs
 ; CHECK-NOT: convergent
 ; CHECK-NEXT: define i32 @recursive1()
 define i32 @recursive1() convergent {
-  %a = call i32 @recursive2()
+  %a = call i32 @recursive2() convergent
   ret i32 %a
 }
 
 ; CHECK: Function Attrs
 ; CHECK-NOT: convergent
 ; CHECK-NEXT: define i32 @recursive2()
 define i32 @recursive2() convergent {
-  %a = call i32 @recursive1()
+  %a = call i32 @recursive1() convergent
   ret i32 %a
 }
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: convergent
 ; CHECK-NEXT: define i32 @noopt()
 define i32 @noopt() convergent optnone noinline {
-  %a = call i32 @noopt_friend()
+  %a = call i32 @noopt_friend() convergent
   ret i32 0
 }
 
 ; A function which is mutually-recursive with a convergent, optnone function
 ; shouldn't have its convergent attribute stripped.
 ; CHECK: Function Attrs
 ; CHECK-SAME: convergent
 ; CHECK-NEXT: define i32 @noopt_friend()
 define i32 @noopt_friend() convergent {
   %a = call i32 @noopt()
   ret i32 0
 }

llvm/trunk/test/Transforms/InstCombine/convergent.ll

+; RUN: opt -instcombine -S < %s | FileCheck %s
+
+declare i32 @k() convergent
+declare i32 @f()
+
+define i32 @extern() {
+  ; Convergent attr shouldn't be removed here; k is convergent.
+  ; CHECK: call i32 @k() [[CONVERGENT_ATTR:#[0-9]+]]
+  %a = call i32 @k() convergent
+  ret i32 %a
+}
+
+define i32 @extern_no_attr() {
+  ; Convergent attr shouldn't be added here, even though k is convergent.
+  ; CHECK: call i32 @k(){{$}}
+  %a = call i32 @k()
+  ret i32 %a
+}
+
+define i32 @no_extern() {
+  ; Convergent should be removed here, as the target is convergent.
+  ; CHECK: call i32 @f(){{$}}
+  %a = call i32 @f() convergent
+  ret i32 %a
+}
+
+define i32 @indirect_call(i32 ()* %f) {
+  ; CHECK call i32 %f() [[CONVERGENT_ATTR]]
+  %a = call i32 %f() convergent
+  ret i32 %a
+}
+
+; CHECK: [[CONVERGENT_ATTR]] = { convergent }