[FunctionAttrs][NPM] Fix handling of convergent

[aeubanks]

Summary

The legacy pass didn't properly detect indirect calls.

We can still remove the convergent attribute when there are indirect
calls. The LangRef says:

When it appears on a call/invoke, the convergent attribute indicates

that we should treat the call as though we’re calling a convergent
function. This is particularly useful on indirect calls; without this we
may treat such calls as though the target is non-convergent.

So don't skip handling of convergent when there are unknown calls.

[jdoerfert]

Before I look at the changes in more detail, two high level comments, one we need to address actually. (And more people).

1. I find this sentence troublesome: This is particularly useful on indirect calls; without this we may treat such calls as though the target is non-convergent. We should say we do treat them or we don't, but not we may. That said, I am unsure if treating indirect calls as non-convergent regardless of what the function is is a good idea. auto t = (&barrier); t(); seems to be the minimal example to make my point.
2. I would encourage someone that cares about convergent (which in theory includes me but not *right now*) to add this deduction to the Attributor.

[efriedma]

At a high level, it should be fine to assume an indirect call without the "convergent" attribute isn't convergent. If the language rules for some language say the callee of an indirect call might be convergent, the frontend can add the convergent attribute to that call. (Unlike most attributes, it's a negative attribute: it restricts optimizations, and attribute inference optimizations would remove it,)

[jdoerfert]

In D89826#2346511, @efriedma wrote:

At a high level, it should be fine to assume an indirect call without the "convergent" attribute isn't convergent. If the language rules for some language say the callee of an indirect call might be convergent, the frontend can add the convergent attribute to that call. (Unlike most attributes, it's a negative attribute: it restricts optimizations, and attribute inference optimizations would remove it,)

I don't object to that but I want us to remove the "may" from the lang ref and make it a "will" (or similar). It describes the semantics not the optimization we "may" perform.

[nhaehnle]

In D89826#2347822, @jdoerfert wrote:

In D89826#2346511, @efriedma wrote:

At a high level, it should be fine to assume an indirect call without the "convergent" attribute isn't convergent. If the language rules for some language say the callee of an indirect call might be convergent, the frontend can add the convergent attribute to that call. (Unlike most attributes, it's a negative attribute: it restricts optimizations, and attribute inference optimizations would remove it,)

I don't object to that but I want us to remove the "may" from the lang ref and make it a "will" (or similar). It describes the semantics not the optimization we "may" perform.

I'd be fine with this change temporarily. Longer term, we should just do D85603.

I'd argue that making the change s/may/will/ does not actually change meaning here (because if a consumer of LLVM IR may treat calls this way, then any frontend must conservatively assume that it will), and it also doesn't change the fact that the LangRef talks about allowed optimizations instead of semantics. The latter is an inherent downside of the current definition of convergent, and one of the things that D85603 solves.

[nhaehnle]

Oh, and on the change itself: I'm not familiar enough with the attributor framework to judge the implementation, but the described reasoning (being able to make deductions from indirect calls) is sound.

[sstefan1]

In D89826#2348164, @nhaehnle wrote:

Oh, and on the change itself: I'm not familiar enough with the attributor framework to judge the implementation, but the described reasoning (being able to make deductions from indirect calls) is sound.

I might try to add this to attributor soon.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

1306

Nit: This doesn't remove convergent anymore.

[aeubanks]

update comment

[aeubanks]

ping

[aeubanks]

ping

[jdoerfert]

LGTM.

It took me a while to see that the de-duplication of the SCCNodeSet contained the change that was important.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

 //===- FunctionAttrs.cpp - Pass which marks functions attributes ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 /// \file
 /// This file implements interprocedural passes which walk the
 /// call-graph deducing and/or propagating function attributes.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/FunctionAttrs.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
for (auto &ID : InferInSCC) {
       if (ID.SkipFunction(*F))
         continue;
       Changed = true;
       ID.SetAttribute(*F);
     }
   return Changed;
 }
 
+struct SCCNodesResult {
+  SCCNodeSet SCCNodes;
+  bool HasUnknownCall;
+};
+
 } // end anonymous namespace
 
 /// Helper for non-Convergent inference predicate InstrBreaksAttribute.
 static bool InstrBreaksNonConvergent(Instruction &I,
                                      const SCCNodeSet &SCCNodes) {
   const CallBase *CB = dyn_cast<CallBase>(&I);
   // Breaks non-convergent assumption if CS is a convergent call to a function
   // not in the SCC.
if (Callee->doesNotFreeMemory())
     return false;
 
   if (SCCNodes.count(Callee) > 0)
     return false;
 
   return true;
 }
 
-/// Infer attributes from all functions in the SCC by scanning every
-/// instruction for compliance to the attribute assumptions. Currently it
-/// does:
-///   - removal of Convergent attribute
-///   - addition of NoUnwind attribute
+/// Attempt to remove convergent function attribute when possible.
 ///
 /// Returns true if any changes to function attributes were made.
-static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
-
+static bool inferConvergent(const SCCNodeSet &SCCNodes) {
   AttributeInferer AI;
 
   // Request to 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).
   // Note: Removal of the attr from the callsites will happen in
   // InstCombineCalls separately.
   AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
       Attribute::Convergent,
       // Skip non-convergent functions.
       [](const Function &F) { return !F.isConvergent(); },
       // Instructions that break non-convergent assumption.
       [SCCNodes](Instruction &I) {
         return InstrBreaksNonConvergent(I, SCCNodes);
       },
       [](Function &F) {
         LLVM_DEBUG(dbgs() << "Removing convergent attr from fn " << F.getName()
                           << "\n");
         F.setNotConvergent();
       },
       /* RequiresExactDefinition= */ false});
+  // Perform all the requested attribute inference actions.
+  return AI.run(SCCNodes);
+}
+
+/// Infer attributes from all functions in the SCC by scanning every
+/// instruction for compliance to the attribute assumptions. Currently it
+/// does:
+///   - removal of Convergent attribute
+///   - addition of NoUnwind attribute
+///
+/// Returns true if any changes to function attributes were made.
+static bool inferAttrsFromFunctionBodies(const SCCNodeSet &SCCNodes) {
+  AttributeInferer AI;
 
   if (!DisableNoUnwindInference)
     // Request to infer nounwind attribute for all the functions in the SCC if
     // every callsite within the SCC is not throwing (except for calls to
     // functions within the SCC). Note that nounwind attribute suffers from
     // derefinement - results may change depending on how functions are
     // optimized. Thus it can be inferred only from exact definitions.
     AI.registerAttrInference(AttributeInferer::InferenceDescriptor{
static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
   // Every call was to a non-recursive function other than this function, and
   // we have no indirect recursion as the SCC size is one. This function cannot
   // recurse.
   F->setDoesNotRecurse();
   ++NumNoRecurse;
   return true;
 }
 
+static SCCNodesResult createSCCNodeSet(ArrayRef<Function *> Functions) {
+  SCCNodesResult Res;
+  Res.HasUnknownCall = false;
+  for (Function *F : Functions) {
+    if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
+      // Treat any function we're trying not to optimize as if it were an
+      // indirect call and omit it from the node set used below.
+      Res.HasUnknownCall = true;
+      continue;
+    }
+    // Track whether any functions in this SCC have an unknown call edge.
+    // Note: if this is ever a performance hit, we can common it with
+    // subsequent routines which also do scans over the instructions of the
+    // function.
+    if (!Res.HasUnknownCall) {
+      for (Instruction &I : instructions(*F)) {
+        if (auto *CB = dyn_cast<CallBase>(&I)) {
+          if (!CB->getCalledFunction()) {
+            Res.HasUnknownCall = true;
+            break;
+          }
+        }
+      }
+    }
+    Res.SCCNodes.insert(F);
+  }
+  return Res;
+}
+
 template <typename AARGetterT>
-static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes,
-                                   AARGetterT &&AARGetter,
-                                   bool HasUnknownCall) {
+static bool deriveAttrsInPostOrder(ArrayRef<Function *> Functions,
+                                   AARGetterT &&AARGetter) {
+  SCCNodesResult Nodes = createSCCNodeSet(Functions);
   bool Changed = false;
 
   // Bail if the SCC only contains optnone functions.
-  if (SCCNodes.empty())
+  if (Nodes.SCCNodes.empty())
     return Changed;
 
-  Changed |= addArgumentReturnedAttrs(SCCNodes);
-  Changed |= addReadAttrs(SCCNodes, AARGetter);
-  Changed |= addArgumentAttrs(SCCNodes);
+  Changed |= addArgumentReturnedAttrs(Nodes.SCCNodes);
+  Changed |= addReadAttrs(Nodes.SCCNodes, AARGetter);
+  Changed |= addArgumentAttrs(Nodes.SCCNodes);
+  Changed |= inferConvergent(Nodes.SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can deduce some
   // more precise attributes as well.
-  if (!HasUnknownCall) {
-    Changed |= addNoAliasAttrs(SCCNodes);
-    Changed |= addNonNullAttrs(SCCNodes);
-    Changed |= inferAttrsFromFunctionBodies(SCCNodes);
-    Changed |= addNoRecurseAttrs(SCCNodes);
+  if (!Nodes.HasUnknownCall) {
+    Changed |= addNoAliasAttrs(Nodes.SCCNodes);
+    Changed |= addNonNullAttrs(Nodes.SCCNodes);
+    Changed |= inferAttrsFromFunctionBodies(Nodes.SCCNodes);
+    Changed |= addNoRecurseAttrs(Nodes.SCCNodes);
   }
 
   return Changed;
 }
 
 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
                                                   CGSCCAnalysisManager &AM,
                                                   LazyCallGraph &CG,
                                                   CGSCCUpdateResult &) {
   FunctionAnalysisManager &FAM =
       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 
   // We pass a lambda into functions to wire them up to the analysis manager
   // for getting function analyses.
   auto AARGetter = [&](Function &F) -> AAResults & {
     return FAM.getResult<AAManager>(F);
   };
 
-  // Fill SCCNodes with the elements of the SCC. Also track whether there are
-  // any external or opt-none nodes that will prevent us from optimizing any
-  // part of the SCC.
-  SCCNodeSet SCCNodes;
-  bool HasUnknownCall = false;
+  SmallVector<Function *, 8> Functions;
   for (LazyCallGraph::Node &N : C) {
-    Function &F = N.getFunction();
-    if (F.hasOptNone() || F.hasFnAttribute(Attribute::Naked)) {
-      // Treat any function we're trying not to optimize as if it were an
-      // indirect call and omit it from the node set used below.
-      HasUnknownCall = true;
-      continue;
-    }
-    // Track whether any functions in this SCC have an unknown call edge.
-    // Note: if this is ever a performance hit, we can common it with
-    // subsequent routines which also do scans over the instructions of the
-    // function.
-    if (!HasUnknownCall)
-      for (Instruction &I : instructions(F))
-        if (auto *CB = dyn_cast<CallBase>(&I))
-          if (!CB->getCalledFunction()) {
-            HasUnknownCall = true;
-            break;
-          }
+    Functions.push_back(&N.getFunction());
 
-    SCCNodes.insert(&F);
-  }
-
-  if (deriveAttrsInPostOrder(SCCNodes, AARGetter, HasUnknownCall))
+  if (deriveAttrsInPostOrder(Functions, AARGetter))
     return PreservedAnalyses::none();
 
   return PreservedAnalyses::all();
 }
 
 namespace {
 
 struct PostOrderFunctionAttrsLegacyPass : public CallGraphSCCPass {
INITIALIZE_PASS_END(PostOrderFunctionAttrsLegacyPass, "function-attrs",
                     "Deduce function attributes", false, false)
 
 Pass *llvm::createPostOrderFunctionAttrsLegacyPass() {
   return new PostOrderFunctionAttrsLegacyPass();
 }
 
 template <typename AARGetterT>
 static bool runImpl(CallGraphSCC &SCC, AARGetterT AARGetter) {
-
-  // Fill SCCNodes with the elements of the SCC. Used for quickly looking up
-  // whether a given CallGraphNode is in this SCC. Also track whether there are
-  // any external or opt-none nodes that will prevent us from optimizing any
-  // part of the SCC.
-  SCCNodeSet SCCNodes;
-  bool ExternalNode = false;
+  SmallVector<Function *, 8> Functions;
   for (CallGraphNode *I : SCC) {
-    Function *F = I->getFunction();
-    if (!F || F->hasOptNone() || F->hasFnAttribute(Attribute::Naked)) {
-      // External node or function we're trying not to optimize - we both avoid
-      // transform them and avoid leveraging information they provide.
-      ExternalNode = true;
-      continue;
-    }
-
-    SCCNodes.insert(F);
+    Functions.push_back(I->getFunction());
   }
 
-  return deriveAttrsInPostOrder(SCCNodes, AARGetter, ExternalNode);
+  return deriveAttrsInPostOrder(Functions, AARGetter);
 }
 
 bool PostOrderFunctionAttrsLegacyPass::runOnSCC(CallGraphSCC &SCC) {
   if (skipSCC(SCC))
     return false;
   return runImpl(SCC, LegacyAARGetter(*this));
 }
 

llvm/test/Transforms/FunctionAttrs/convergent.ll

-; FIXME: convert CHECK-INDIRECT into CHECK (and remove -check-prefixes) as soon
-; FIXME: as new-pass-manager's handling of indirect_non_convergent_call is fixed
-;
-; RUN: opt -function-attrs -S < %s | FileCheck %s --check-prefixes=CHECK,CHECK-INDIRECT
+; RUN: opt -function-attrs -S < %s | FileCheck %s
 ; RUN: opt -passes=function-attrs -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

 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-INDIRECT-NOT: convergent
-; CHECK-INDIRECT-NEXT: define i32 @indirect_non_convergent_call(
+; 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.nvvm.barrier0()