[FunctionAttrs] Identify norecurse functions

[jmolloy]

Summary

A function can be marked as norecurse if:

• The SCC to which it belongs has cardinality 1.
• It does not call any non-norecurse function. This includes self-recursion.

We can simply build up norecurse attributes in the existing SCC pass.

[mehdi_amini]

I don't know the CGSCC enough: what about a function whose address is taken? What about potential call site from a different module you have no visibility to?

[jmolloy]

Hi,

My understanding is that CGSCC behaves conservatively - if a function's address is taken, an edge is added from the "Externally called" node to that function. However, in our case we don't actually need to care what can *call* a function, we just need to know whether or not we have full knowledge about what that function *can call*. That's why we only mark functions norecurse if we've enumerated successfully all call edges and found them not to form a cycle or encounter the special "calls external" node in which case all bets are off.

James

[reames]

lib/Transforms/IPO/FunctionAttrs.cpp

82

It looks like this change needs to be rebased over Chandler's recent ones. Can you update the patch?

1876

If there's a single element in the SCC, why do you need the any_of?

1884

The change needs to be conditional on whether the function was already marked recursive. Otherwise, you'll be misleading the wrapping code about changes being made.

test/Transforms/FunctionAttrs/norecurse.ll

10

"self_rec" rather than "g"?

16

for readability, I'd call these two something like: mutually_rec1 and mutually_rec2

[manmanren]

Thanks for working on it!
Manman

lib/Transforms/IPO/FunctionAttrs.cpp

1867

This comment seems to be incorrect. Should it be "must not call itself or any function that may be recursive"?

1876

Here it is checking the edges from the single element in the SCC.

1881

Can you add comments to explain how self-recursion is handled here?

[mehdi_amini]

lib/Transforms/IPO/FunctionAttrs.cpp

1867

It can call a recursive function, as long at it is not involved in the recursion.

i.e. if:
a() calls b()
b() calls c()
c() calls b()

a is not recursive, but b() and c() are.

The issue with external function is that you don't know if they can call back into a() or one of its callers.
Or did I misunderstand what you meant?

1876

A comment might be useful?

[manmanren]

lib/Transforms/IPO/FunctionAttrs.cpp

1867

I was talking about what is actually implemented. But it is not the necessary condition.

// For a function not to recurse, it must be in its own SCC and must not

// call itself or any function that may be recursive.

is incorrect.

But this makes sense:
We mark a function as norecurse if it is in its own SCC and it does not call itself
or any function that may be recursive.

[jmolloy]

Hi,

Thanks all for the feedback. This new version is rebased to HEAD on top of Chandler's changes, and improves the way the algorithm works.

I've added an extra inference rule - if a function F has only one callsite and that callsite is itself in a norecurse function, then F cannot recurse. Obviously this lends itself to top-down propagation rather than the bottom-up propagation we get with SCC passes.

Now, we do the same bottom-up approach but if we see a function that is not obviously recursive but can't be proven non-recursive we save it and after the SCC is over we go and revisit it, top-down. This allows more functions to be marked norecurse.

I think I've acted on all the review comments so far, and I've added more comments into the code to make it clearer what's going on.

Cheers,

James

[mehdi_amini]

lib/Transforms/IPO/FunctionAttrs.cpp

71

This is sad: it will run at the end of the SCC PassManager, it means you need a barrier after this pass in the pipeline before running another pass. (I don't have a better solution to suggest though).

1778

Why one use? If F has multiple callers but they are all "norecurse", shouldn't it be enough?

[manmanren]

lib/Transforms/IPO/FunctionAttrs.cpp

1778

During bottom-up traversal, have the uses of F been visited and possibly marked as norecurse?

[jmolloy]

Hi Mehdi,

I agree with you, having thought about it. I've updated the patch to be less strict.

Cheers,

James

[jmolloy]

Hi Mehdi,

Sorry, I created the last diff from an old branch. This now contains the correct code.

Cheers,

James

[manmanren]

lib/Transforms/IPO/FunctionAttrs.cpp

1778

There may be an ordering problem on setting NoRecurse. Have users of F been traversed? A testing case that exercises this would be nice.

1811

A testing case that covers this would be nice. I didn't really look through your testing cases, so you may already have one there :]

[jmolloy]

Hi Manman,

I think these should already be tested by the tests @called_by_norecurse and @called_by_norecurse_indirectly?

Cheers,

James

[jmolloy]

Hi Manman,

Chatting with Mehdi on IRC, I elaborated a bit on what that first check is doing; it's just an optimization. It's the same check as in the top-down-only function, it just runs a bit earlier so has the potential to catch more cases, earlier, opening up more opportunities for the other bottom-up checks.

Mehdi rightly stated that it only affects functions that were marked norecurse before FunctionAttrs ran. He also mentioned that the checks should be factored together, which I agree with (changing the first check in bottom-up to just call addNoRecurseAttrsTopDownOnly().

James

[jmolloy]

Hi Mehdi,

I've removed the offending bottom-up check as we discussed yesterday.

Cheers,

James

[mehdi_amini]

r252871

lib/Transforms/IPO/FunctionAttrs.cpp

 STATISTIC(NumReadNone, "Number of functions marked readnone");
 STATISTIC(NumReadOnly, "Number of functions marked readonly");
 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
 STATISTIC(NumAnnotated, "Number of attributes added to library functions");
+STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
 
 namespace {
 typedef SmallSetVector<Function *, 8> SCCNodeSet;
 }
 
 namespace {
 struct FunctionAttrs : public CallGraphSCCPass {
   static char ID; // Pass identification, replacement for typeid
   FunctionAttrs() : CallGraphSCCPass(ID) {
     initializeFunctionAttrsPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnSCC(CallGraphSCC &SCC) override;
+  bool doInitialization(CallGraph &CG) override {
+    Revisit.clear();
+    return false;
+  }
+  bool doFinalization(CallGraph &CG) override;
   
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     CallGraphSCCPass::getAnalysisUsage(AU);
   }
 
 private:
   TargetLibraryInfo *TLI;
+  SmallVector<WeakVH,16> Revisit;
 };
 }
 
 char FunctionAttrs::ID = 0;
 INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs",
                       "Deduce function attributes", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(CallGraphWrapperPass)

 
 static void setDoesNotAlias(Function &F, unsigned n) {
   if (!F.doesNotAlias(n)) {
     F.setDoesNotAlias(n);
     ++NumAnnotated;
   }
 }
 
+static bool setDoesNotRecurse(Function &F) {
+  if (F.doesNotRecurse())
+    return false;
+  F.setDoesNotRecurse();
+  ++NumNoRecurse;
+  return true;
+}
+
 /// Analyze the name and prototype of the given function and set any applicable
 /// attributes.
 ///
 /// Returns true if any attributes were set and false otherwise.
 static bool inferPrototypeAttributes(Function &F, const TargetLibraryInfo &TLI) {
   if (F.hasFnAttribute(Attribute::OptimizeNone))
     return false;
 
static bool inferPrototypeAttributes(Function &F, const TargetLibraryInfo &TLI) {
   default:
     // Didn't mark any attributes.
     return false;
   }
 
   return true;
 }
 
+static bool addNoRecurseAttrs(const CallGraphSCC &SCC,
+                              SmallVectorImpl<WeakVH> &Revisit) {
+  // Try and identify functions that do not recurse.
+
+  // If the SCC contains multiple nodes we know for sure there is recursion.
+  if (!SCC.isSingular())
+    return false;
+
+  const CallGraphNode *CGN = *SCC.begin();
+  Function *F = CGN->getFunction();
+  if (!F || F->isDeclaration() || F->doesNotRecurse())
+    return false;
+
+  // If all of the calls in F are identifiable and are to norecurse functions, F
+  // is norecurse. This check also detects self-recursion as F is not currently
+  // marked norecurse, so any called from F to F will not be marked norecurse.
+  if (std::all_of(CGN->begin(), CGN->end(),
+                  [](const CallGraphNode::CallRecord &CR) {
+                    Function *F = CR.second->getFunction();
+                    return F && F->doesNotRecurse();
+                  }))
+    // Function calls a potentially recursive function.
+    return setDoesNotRecurse(*F);
+
+  // We know that F is not obviously recursive, but we haven't been able to
+  // prove that it doesn't actually recurse. Add it to the Revisit list to try
+  // again top-down later.
+  Revisit.push_back(F);
+  return false;
+}
+
+static bool addNoRecurseAttrsTopDownOnly(Function *F) {
+  // If F is internal and all uses are in norecurse functions, then F is also
+  // norecurse.
+  if (F->doesNotRecurse())
+    return false;
+  if (F->hasInternalLinkage()) {
+    for (auto *U : F->users())
+      if (auto *I = dyn_cast<Instruction>(U)) {
+        if (!I->getParent()->getParent()->doesNotRecurse())
+          return false;
+      } else {
+        return false;
+      }
+    return setDoesNotRecurse(*F);
+  }
+  return false;
+}
+
 bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   bool Changed = false;
 
   // We compute dedicated AA results for each function in the SCC as needed. We
   // use a lambda referencing external objects so that they live long enough to
   // be queried, but we re-use them each time.
   Optional<BasicAAResult> BAR;
bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) {
   Changed |= addArgumentAttrs(SCCNodes);
 
   // If we have no external nodes participating in the SCC, we can infer some
   // more precise attributes as well.
   if (!ExternalNode) {
     Changed |= addNoAliasAttrs(SCCNodes);
     Changed |= addNonNullAttrs(SCCNodes, *TLI);
   }
   
+  Changed |= addNoRecurseAttrs(SCC, Revisit);
+  return Changed;
+}
+
+bool FunctionAttrs::doFinalization(CallGraph &CG) {
+  bool Changed = false;
+  // When iterating over SCCs we visit functions in a bottom-up fashion. Some of
+  // the rules we have for identifying norecurse functions work best with a
+  // top-down walk, so look again at all the functions we previously marked as
+  // worth revisiting, in top-down order.
+  for (auto &F : reverse(Revisit))
+    if (F)
+      Changed |= addNoRecurseAttrsTopDownOnly(cast<Function>((Value*)F));
   return Changed;
 }

test/Analysis/TypeBasedAliasAnalysis/functionattrs.ll

 ; TBAA says doesn't modify any memory.
 
 ; CHECK: define void @test1_yes(i32* nocapture %p) #2 {
 define void @test1_yes(i32* %p) nounwind {
   call void @callee(i32* %p), !tbaa !1
   ret void
 }
 
-; CHECK: define void @test1_no(i32* %p) #1 {
+; CHECK: define void @test1_no(i32* %p) #3 {
 define void @test1_no(i32* %p) nounwind {
   call void @callee(i32* %p), !tbaa !2
   ret void
 }
 
 ; Add the readonly attribute, as above, but this time BasicAA will say
 ; that the function accesses memory through its arguments, which TBAA
 ; still says that the function doesn't write to memory.

 define i32 @test3_no(i8* %p) nounwind {
   %t = va_arg i8* %p, i32, !tbaa !2
   ret i32 %t
 }
 
 declare void @callee(i32* %p) nounwind
 declare void @llvm.memcpy.p0i8.p0i8.i64(i8*, i8*, i64, i32, i1) nounwind
 
-; CHECK: attributes #0 = { nounwind readnone }
-; CHECK: attributes #1 = { nounwind }
+; CHECK: attributes #0 = { norecurse nounwind readnone }
+; CHECK: attributes #1 = { norecurse nounwind }
 ; CHECK: attributes #2 = { nounwind readonly }
+; CHECK: attributes #3 = { nounwind }
+; CHECK: attributes #4 = { nounwind argmemonly }
 
 ; Root note.
 !0 = !{ }
 
 ; Invariant memory.
 !1 = !{!3, !3, i64 0, i1 1 }
 ; Not invariant memory.
 !2 = !{!3, !3, i64 0, i1 0 }
 !3 = !{ !"foo", !0 }

test/Transforms/FunctionAttrs/2008-09-03-ReadNone.ll

 ; RUN: opt < %s -basicaa -functionattrs -S | FileCheck %s
 @x = global i32 0
 
 ; CHECK: declare i32 @e() #0
 declare i32 @e() readnone
 
 ; CHECK: define i32 @f() #0
 define i32 @f() {
   %tmp = call i32 @e( )   ; <i32> [#uses=1]
   ret i32 %tmp
 }
 
-; CHECK: define i32 @g() #0
+; CHECK: define i32 @g() #1
 define i32 @g() readonly {
   ret i32 0
 }
 
-; CHECK: define i32 @h() #0
+; CHECK: define i32 @h() #1
 define i32 @h() readnone {
   %tmp = load i32, i32* @x    ; <i32> [#uses=1]
   ret i32 %tmp
 }
 
 ; CHECK: attributes #0 = { readnone }
+; CHECK: attributes #1 = { norecurse readnone }

test/Transforms/FunctionAttrs/2010-10-30-volatile.ll

 ; RUN: opt < %s -functionattrs -S | FileCheck %s
 ; PR8279
 
 @g = constant i32 1
 
 define void @foo() {
-; CHECK: void @foo() {
+; CHECK: void @foo() #0 {
   %tmp = load volatile i32, i32* @g
   ret void
 }
+
+; CHECK: attributes #0 = { norecurse }

test/Transforms/FunctionAttrs/atomic.ll

 ; A function with an Acquire load is not readonly.
 define i32 @test2(i32* %x) uwtable ssp {
 ; CHECK: define i32 @test2(i32* nocapture readonly %x) #1 {
 entry:
   %r = load atomic i32, i32* %x seq_cst, align 4
   ret i32 %r
 }
 
-; CHECK: attributes #0 = { readnone ssp uwtable }
-; CHECK: attributes #1 = { ssp uwtable }
+; CHECK: attributes #0 = { norecurse readnone ssp uwtable }
+; CHECK: attributes #1 = { norecurse ssp uwtable }

test/Transforms/FunctionAttrs/norecurse.ll

+; RUN: opt < %s -basicaa -functionattrs -S | FileCheck %s
+
+; CHECK: define i32 @leaf() #0
+define i32 @leaf() {
+  ret i32 1
+}
+
+; CHECK: define i32 @self_rec() #1
+define i32 @self_rec() {
+  %a = call i32 @self_rec()
+  ret i32 4
+}
+
+; CHECK: define i32 @indirect_rec() #1
+define i32 @indirect_rec() {
+  %a = call i32 @indirect_rec2()
+  ret i32 %a
+}
+; CHECK: define i32 @indirect_rec2() #1
+define i32 @indirect_rec2() {
+  %a = call i32 @indirect_rec()
+  ret i32 %a
+}
+
+; CHECK: define i32 @extern() #1
+define i32 @extern() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+declare i32 @k() readnone
+
+; CHECK: define internal i32 @called_by_norecurse() #0
+define internal i32 @called_by_norecurse() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+define void @m() norecurse {
+  %a = call i32 @called_by_norecurse()
+  ret void
+}
+
+; CHECK: define internal i32 @called_by_norecurse_indirectly() #0
+define internal i32 @called_by_norecurse_indirectly() {
+  %a = call i32 @k()
+  ret i32 %a
+}
+define internal void @o() {
+  %a = call i32 @called_by_norecurse_indirectly()
+  ret void
+}
+define void @p() norecurse {
+  call void @o()
+  ret void
+}
+
+; CHECK: attributes #0 = { norecurse readnone }
+; CHECK: attributes #1 = { readnone }

test/Transforms/FunctionAttrs/optnone.ll

 define void @test_optnone(i8* %p) noinline optnone {
 ; CHECK-LABEL: @test_optnone
 ; CHECK: (i8* %p) #1 {
   ret void
 }
 
 declare i8 @strlen(i8*) noinline optnone
 ; CHECK-LABEL: @strlen
-; CHECK: (i8*) #1
+; CHECK: (i8*) #2
 
 ; CHECK-LABEL: attributes #0
-; CHECK: = { readnone }
+; CHECK: = { norecurse readnone }
 ; CHECK-LABEL: attributes #1
+; CHECK: = { noinline norecurse optnone }
+; CHECK-LABEL: attributes #2
 ; CHECK: = { noinline optnone }