[FunctionAttrs] Remove post order "no-recurse" attribute deduction

[jdoerfert]

Summary

The Attributor can deduce "no-recurse" function attributes (see D60074)
generally equivalent to the hereby removed functionality.

Test cases have been adjusted to run the attributor in addition to
functionattrs if they were not already.

This fixed the bug https://llvm.org/PR41336, where no-recurse was
derived for a function with linkonce_odr linkage (which be replaced
later and should therefore not participate in inter-procedural
reasoning).

Test case is available in:

`llvm/test/Transforms/FunctionAttrs/arg_returned.ll`

[jdoerfert]

Update tests

[reames]

Please post for review once attributor is actually enabled by default. Removing existing code before that point is inappropriate.

llvm/lib/Transforms/IPO/FunctionAttrs.cpp

for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
     //
     // Writes memory, remember that.
     WritesMemory |= I->mayWriteToMemory();
 
     // If this instruction may read memory, remember that.
     ReadsMemory |= I->mayReadFromMemory();
   }
 
-  if (WritesMemory) { 
+  if (WritesMemory) {
     if (!ReadsMemory)
       return MAK_WriteOnly;
     else
       return MAK_MayWrite;
   }
 
   return ReadsMemory ? MAK_ReadOnly : MAK_ReadNone;
 }

 static bool setDoesNotRecurse(Function &F) {
   if (F.doesNotRecurse())
     return false;
   F.setDoesNotRecurse();
   ++NumNoRecurse;
   return true;
 }
 
-static bool addNoRecurseAttrs(const SCCNodeSet &SCCNodes) {
-  // Try and identify functions that do not recurse.
-
-  // If the SCC contains multiple nodes we know for sure there is recursion.
-  if (SCCNodes.size() != 1)
-    return false;
-
-  Function *F = *SCCNodes.begin();
-  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.
-  for (auto &BB : *F)
-    for (auto &I : BB.instructionsWithoutDebug())
-      if (auto CS = CallSite(&I)) {
-        Function *Callee = CS.getCalledFunction();
-        if (!Callee || Callee == F || !Callee->doesNotRecurse())
-          // Function calls a potentially recursive function.
-          return false;
-      }
-
-  // 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.
-  return setDoesNotRecurse(*F);
-}
-
 template <typename AARGetterT>
 static bool deriveAttrsInPostOrder(SCCNodeSet &SCCNodes, AARGetterT &&AARGetter,
                                    bool HasUnknownCall) {
   bool Changed = false;
 
   // Bail if the SCC only contains optnone functions.
   if (SCCNodes.empty())
     return Changed;
 
   Changed |= addArgumentReturnedAttrs(SCCNodes);
   Changed |= addReadAttrs(SCCNodes, AARGetter);
   Changed |= addArgumentAttrs(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);
   }
 
   return Changed;
 }
 
 PreservedAnalyses PostOrderFunctionAttrsPass::run(LazyCallGraph::SCC &C,
                                                   CGSCCAnalysisManager &AM,
                                                   LazyCallGraph &CG,

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 ;
 ;  int *calls_maybe_redefined_fn(int *r) {
 ;    maybe_redefined_fn(r);
 ;    return r;
 ;  }
 ;
 ; Verify the maybe-redefined function is not annotated:
 ;
-; CHECK: Function Attrs: noinline norecurse nounwind uwtable
+; CHECK: Function Attrs: noinline nounwind uwtable
 ; CHECK: define linkonce_odr i32* @maybe_redefined_fn(i32* %r)
-; FIXME: We should not derive norecurse for potentially redefined functions!
-;        Function Attrs: noinline nounwind uwtable
-;        define linkonce_odr i32* @maybe_redefined_fn(i32* %r)
 ;
-; CHECK: Function Attrs: noinline norecurse nounwind uwtable
+; CHECK: Function Attrs: noinline nounwind uwtable
 ; CHECK: define i32* @calls_maybe_redefined_fn(i32* returned %r)
-; FIXME: We should not derive norecurse for potentially redefined functions!
-;        Function Attrs: noinline nounwind uwtable
-;        define i32* @calls_maybe_redefined_fn(i32* returned %r)
 define linkonce_odr i32* @maybe_redefined_fn(i32* %r) #0 {
 entry:
   ret i32* %r
 }
 
 define i32* @calls_maybe_redefined_fn(i32* %r) #0 {
 entry:
   %call = call i32* @maybe_redefined_fn(i32* %r)

llvm/test/Transforms/FunctionAttrs/norecurse.ll

define internal void @o() {
   %a = call i32 @called_by_norecurse_indirectly()
   ret void
 }
 define void @p() norecurse {
   call void @o()
   ret void
 }
 
-; FIXME: This test exposes a bug: https://llvm.org/PR41336
-; CHECK: Function Attrs: norecurse
+; PR41336
+; CHECK: Function Attrs:
+; CHECK-NOT: norecurse
 ; CHECK-NEXT: define i32 @leaf_redefinable()
 define linkonce_odr i32 @leaf_redefinable() {
   ret i32 1
 }