[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.

[chandlerc]

See my comment below, but it seems like the removal of the call instruction attribute makes more sense in instcombine or something like it when we see a direct call to a non-convergent function (we don't need any call graph analysis for that). Then this code would just need to handle removing the attribute from function definitions when we can do a conservative analysis of an entire SCC and determine that no convergent operation is actually reached.

These should still iterate nicely in a bottom-up fashion.

lib/Transforms/IPO/FunctionAttrs.cpp

938–941

The first claim doesn't seem true. This code bails when the SCC contains a call to a declaration, and we don't even call this routine if the SCC contains an external call.

[jlebar]

Update per chandlerc's review.

[jlebar]

This is a lot better, thank you. I went ahead and split up the test.

[chandlerc]

lib/Transforms/IPO/FunctionAttrs.cpp

952–958

When these become multi-line lambdas with names and potential for confusing double negation, I have to say I find the early exit from a range based for loop substantially easier to read...

lib/Transforms/InstCombine/InstCombineCalls.cpp

2039–2042

It's not clear that it is correct to fall through here... Usually these things go back onto a worklist and get visited again anyways. Is there a reason you chose this particular pattern?

[jlebar]

Update per Chandler's review.

lib/Transforms/InstCombine/InstCombineCalls.cpp

2039–2042

No particular reason; I was following the Indices.empty() branch above, which seems to be doing something similar. I changed it as suggested.

[jingyue]

lib/Transforms/IPO/FunctionAttrs.cpp

955–958

Maybe this reads better

if (CS && CS.isConvergent()) {
  if (SCCNodes.count(CS.getCalledFunction()) == 0)
    return false;
}

This reads exactly like your comment -- if CS is a convergent call to a function not in SCC.

958

What happens if CS.getCalledFunction() == nullptr? i.e. CS calls a function pointer.

[jlebar]

Combine if statements in removeConvergentAttrs.

[jlebar]

lib/Transforms/IPO/FunctionAttrs.cpp

955–958

Maybe this reads better

Sure, I think that's better; combined the if statements.

What happens if CS.getCalledFunction() == nullptr?

We do a lookup of nullptr in the map, which is fine. (This is covered by a testcase -- I hope. :)

[jlebar]

Friendly ping -- are we happy with this?

[jingyue]

Happy!

[jlebar]

Thanks. Will wait for chandlerc, since he has opinions.

[jlebar]

So much for waiting; I accidentally committed this because I fail at git.

On the bright side, it has a strange test failure that manifested only after sync'ing, so I get to revert.

[jlebar]

Reverted in r261549.

[jlebar]

Wrong link: New review in D17518.

[jlebar]

New review in D17518.

Sorry, posted in wrong tab.

The relevant link here is https://gist.github.com/57285538454829420e0e -- with this change (which fixes a bug where we'd sometimes return MadeChange = true when we should have returned MadeChange = false), the readattrs.ll test fails.

$ opt < /usr/local/google/home/jlebar/code/llvm/src/test/Transforms/FunctionAttrs/readattrs.ll -aa-pipeline=basic-aa -passes='require<targetlibinfo>,cgscc(function-attrs)' -S -debug
https://gist.github.com/0c003a39199904e230dc

[jlebar]

OK, now that things are working again, new review in D17739. Would appreciate a review there, Chandler, to make sure you're happy with this patch.

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;
-
-    // Can't remove convergent from declarations.
-    if (F->isDeclaration())
-      return false;
+  // No point checking if none of SCCNodes is convergent.
+  if (!llvm::any_of(SCCNodes, [](Function *F) { return F->isConvergent(); }))
 
-    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 from function declarations.
+  if (llvm::any_of(SCCNodes, [](Function *F) { return F->isDeclaration(); }))
 
-    return true;
+  // Determines whether an instr is a convergent call to a function not in the
+  // SCC.
+  auto IsConvergentNonSCCCall = [&](Instruction &I) {
+    CallSite CS(&I);
+    if (!CS || !CS.isConvergent())
+      return false;
+    Function *Callee = CS.getCalledFunction();
+    return !Callee || SCCNodes.count(Callee) == 0;
   };
 
-  // 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))
+  // Bail if there are any convergent calls in the SCC to functions not in the
+  // SCC.
+  for (Function *F : SCCNodes)
+    if (llvm::any_of(instructions(*F), IsConvergentNonSCCCall))
       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");
+      DEBUG(dbgs() << "Removing convergent attr from fn " << F->getName()
+                   << "\n");
     F->setNotConvergent();
   }
   return true;
 }
 
 static bool setDoesNotRecurse(Function &F) {
   if (F.doesNotRecurse())
     return false;

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();
+      Changed = true;
+    }
+
     // 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()));
 

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
 }

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 }