[Attributor] Implement "norecurse" function attribute deduction

[uenoku]

Summary

This patch introduces norecurse function attribute deduction.

norecurse will be deduced if the following conditions hold:

• The size of SCC in which the function belongs equals to 1.
• The function doesn't have self-recursion.
• We have norecurse for all call site.

To avoid a large change, SCC is calculated using scc_iterator in InfoCache initialization for now.

[jdoerfert]

Thx, I have a few minor comments, mostly wrt. to the test.

llvm/include/llvm/Transforms/IPO/Attributor.h

547

nit: Make it MAM.

568

nit: can you add a newline here :)

llvm/test/Transforms/FunctionAttrs/norecurse.ll

129

do we have a function pointer test?
do we have a test with recursion through a dead call site?

llvm/test/Transforms/FunctionAttrs/willreturn.ll

526

Willreturn uses norecurse, could we have a test to show how this improved willreturn?

[uenoku]

Address comment

[uenoku]

llvm/test/Transforms/FunctionAttrs/norecurse.ll

129

I added both. See below.

llvm/test/Transforms/FunctionAttrs/willreturn.ll

526

I change Test8 a bit and willreturn and norecurse will be propagated in the test.

[jdoerfert]

LGTM.

llvm/include/llvm/Transforms/IPO/Attributor.h

 //   `InformationCache::getOpcodeInstMapForFunction` interface and eliminate the
 //   need to traverse the IR repeatedly.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
+#include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Analysis/CallGraph.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/ADT/MapVector.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 struct AbstractAttribute;
 struct InformationCache;
 struct AAIsDead;
public:
   iterator begin() { return IRPositions.begin(); }
   iterator end() { return IRPositions.end(); }
 };
 
 /// Wrapper for FunctoinAnalysisManager.
 struct AnalysisGetter {
   template <typename Analysis>
   typename Analysis::Result *getAnalysis(const Function &F) {
-    if (!FAM)
+    if (!MAM || !F.getParent())
+      return nullptr;
+    auto &FAM = MAM->getResult<FunctionAnalysisManagerModuleProxy>(
+                       const_cast<Module &>(*F.getParent()))
+                    .getManager();
+    return &FAM.getResult<Analysis>(const_cast<Function &>(F));
+  }
+
+  template <typename Analysis>
+  typename Analysis::Result *getAnalysis(const Module &M) {
+    if (!MAM)
       return nullptr;
-    return &FAM->getResult<Analysis>(const_cast<Function &>(F));
+    return &MAM->getResult<Analysis>(const_cast<Module &>(M));
   }
-  AnalysisGetter(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
+  AnalysisGetter(ModuleAnalysisManager &MAM) : MAM(&MAM) {}
   AnalysisGetter() {}
 
 private:
-  FunctionAnalysisManager *FAM = nullptr;
+  ModuleAnalysisManager *MAM = nullptr;
 };
 
 /// Data structure to hold cached (LLVM-IR) information.
 ///
 /// All attributes are given an InformationCache object at creation time to
 /// avoid inspection of the IR by all of them individually. This default
 /// InformationCache will hold information required by 'default' attributes,
 /// thus the ones deduced when Attributor::identifyDefaultAbstractAttributes(..)
 /// is called.
 ///
 /// If custom abstract attributes, registered manually through
 /// Attributor::registerAA(...), need more information, especially if it is not
 /// reusable, it is advised to inherit from the InformationCache and cast the
 /// instance down in the abstract attributes.
 struct InformationCache {
-  InformationCache(const DataLayout &DL, AnalysisGetter &AG) : DL(DL), AG(AG) {}
+  InformationCache(const Module &M, AnalysisGetter &AG)
+      : DL(M.getDataLayout()), AG(AG) {
+
+    CallGraph *CG = AG.getAnalysis<CallGraphAnalysis>(M);
+    if (!CG)
+      return;
+
+    DenseMap<const Function *, unsigned> SccSize;
+    for (scc_iterator<CallGraph *> I = scc_begin(CG); !I.isAtEnd(); ++I) {
+      for (CallGraphNode *Node : *I)
+        SccSize[Node->getFunction()] = I->size();
+    }
+    SccSizeOpt = std::move(SccSize);
+  }
 
   /// A map type from opcodes to instructions with this opcode.
   using OpcodeInstMapTy = DenseMap<unsigned, SmallVector<Instruction *, 32>>;
 
   /// Return the map that relates "interesting" opcodes with all instructions
   /// with that opcode in \p F.
   OpcodeInstMapTy &getOpcodeInstMapForFunction(const Function &F) {
     return FuncInstOpcodeMap[&F];
TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) {
     return AG.getAnalysis<TargetLibraryAnalysis>(F);
   }
 
   /// Return AliasAnalysis Result for function \p F.
   AAResults *getAAResultsForFunction(const Function &F) {
     return AG.getAnalysis<AAManager>(F);
   }
 
+  /// Return SCC size on call graph for function \p F.
+  unsigned getSccSize(const Function &F) {
+    if (!SccSizeOpt.hasValue())
+      return 0;
+    return (SccSizeOpt.getValue())[&F];
+  }
+
   /// Return datalayout used in the module.
   const DataLayout &getDL() { return DL; }
 
 private:
   /// A map type from functions to opcode to instruction maps.
   using FuncInstOpcodeMapTy = DenseMap<const Function *, OpcodeInstMapTy>;
 
   /// A map type from functions to their read or write instructions.
   using FuncRWInstsMapTy = DenseMap<const Function *, InstructionVectorTy>;
 
   /// A nested map that remembers all instructions in a function with a certain
   /// instruction opcode (Instruction::getOpcode()).
   FuncInstOpcodeMapTy FuncInstOpcodeMap;
 
   /// A map from functions to their instructions that may read or write memory.
   FuncRWInstsMapTy FuncRWInstsMap;
 
-  /// A map from functions to their TLI.
-
   /// The datalayout used in the module.
   const DataLayout &DL;
 
   /// Getters for analysis.
   AnalysisGetter &AG;
 
+  /// Cache result for scc size in the call graph
+  Optional<DenseMap<const Function *, unsigned>> SccSizeOpt;
+
   /// Give the Attributor access to the members so
   /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
   friend struct Attributor;
 };
 
 /// The fixpoint analysis framework that orchestrates the attribute deduction.
 ///
 /// The Attributor provides a general abstract analysis framework (guided

llvm/lib/Transforms/IPO/Attributor.cpp

struct AANoRecurseImpl : public AANoRecurse {
   const std::string getAsStr() const override {
     return getAssumed() ? "norecurse" : "may-recurse";
   }
 };
 
 struct AANoRecurseFunction final : AANoRecurseImpl {
   AANoRecurseFunction(const IRPosition &IRP) : AANoRecurseImpl(IRP) {}
 
+  /// See AbstractAttribute::initialize(...).
+  void initialize(Attributor &A) override {
+    AANoRecurseImpl::initialize(A);
+    if (const Function *F = getAnchorScope())
+      if (A.getInfoCache().getSccSize(*F) == 1)
+        return;
+    indicatePessimisticFixpoint();
+  }
+
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
-    // TODO: Implement this.
+
+    auto CheckForNoRecurse = [&](Instruction &I) {
+      ImmutableCallSite ICS(&I);
+      if (ICS.hasFnAttr(Attribute::NoRecurse))
+        return true;
+
+      const auto &NoRecurseAA =
+          A.getAAFor<AANoRecurse>(*this, IRPosition::callsite_function(ICS));
+      if (!NoRecurseAA.isAssumedNoRecurse())
+        return false;
+
+      // Recursion to the same function
+      if (ICS.getCalledFunction() == getAnchorScope())
+        return false;
+
+      return true;
+    };
+
+    if (!A.checkForAllCallLikeInstructions(CheckForNoRecurse, *this))
       return indicatePessimisticFixpoint();
+    return ChangeStatus::UNCHANGED;
   }
 
   void trackStatistics() const override { STATS_DECLTRACK_FN_ATTR(norecurse) }
 };
 
 /// NoRecurse attribute deduction for a call sites.
 struct AANoRecurseCallSite final : AANoRecurseImpl {
   AANoRecurseCallSite(const IRPosition &IRP) : AANoRecurseImpl(IRP) {}
void Attributor::identifyDefaultAbstractAttributes(Function &F) {
   getOrCreateAAFor<AANoSync>(FPos);
 
   // Every function might be "no-free".
   getOrCreateAAFor<AANoFree>(FPos);
 
   // Every function might be "no-return".
   getOrCreateAAFor<AANoReturn>(FPos);
 
+  // Every function might be "no-recurse".
+  getOrCreateAAFor<AANoRecurse>(FPos);
+
   // Every function might be applicable for Heap-To-Stack conversion.
   if (EnableHeapToStack)
     getOrCreateAAFor<AAHeapToStack>(FPos);
 
   // Return attributes are only appropriate if the return type is non void.
   Type *ReturnType = F.getReturnType();
   if (!ReturnType->isVoidTy()) {
     // Argument attribute "returned" --- Create only one per function even
static bool runAttributorOnModule(Module &M, AnalysisGetter &AG) {
   if (DisableAttributor)
     return false;
 
   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
                     << " functions.\n");
 
   // Create an Attributor and initially empty information cache that is filled
   // while we identify default attribute opportunities.
-  InformationCache InfoCache(M.getDataLayout(), AG);
+  InformationCache InfoCache(M, AG);
   Attributor A(InfoCache, DepRecInterval);
 
   for (Function &F : M)
     A.initializeInformationCache(F);
 
   for (Function &F : M) {
     if (F.hasExactDefinition())
       NumFnWithExactDefinition++;
for (Function &F : M) {
     // function and the information cache with IR information.
     A.identifyDefaultAbstractAttributes(F);
   }
 
   return A.run(M) == ChangeStatus::CHANGED;
 }
 
 PreservedAnalyses AttributorPass::run(Module &M, ModuleAnalysisManager &AM) {
-  auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
-
-  AnalysisGetter AG(FAM);
+  AnalysisGetter AG(AM);
   if (runAttributorOnModule(M, AG)) {
     // FIXME: Think about passes we will preserve and add them here.
     return PreservedAnalyses::none();
   }
   return PreservedAnalyses::all();
 }
 
 namespace {

llvm/test/Transforms/FunctionAttrs/norecurse.ll

-; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s
-; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs),rpo-functionattrs' -S | FileCheck %s
+; RUN: opt < %s -basicaa -functionattrs -rpo-functionattrs -S | FileCheck %s --check-prefixes=CHECK,BOTH
+; RUN: opt < %s -aa-pipeline=basic-aa -passes='cgscc(function-attrs),rpo-functionattrs' -S | FileCheck %s --check-prefixes=CHECK,BOTH
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR,BOTH
 
 ; CHECK: Function Attrs
 ; CHECK-SAME: norecurse nounwind readnone
-; CHECK-NEXT: define i32 @leaf()
+; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind willreturn
+; BOTH-NEXT: define i32 @leaf()
 define i32 @leaf() {
   ret i32 1
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @self_rec()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @self_rec()
 define i32 @self_rec() {
   %a = call i32 @self_rec()
   ret i32 4
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @indirect_rec()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @indirect_rec()
 define i32 @indirect_rec() {
   %a = call i32 @indirect_rec2()
   ret i32 %a
 }
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @indirect_rec2()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @indirect_rec2()
 define i32 @indirect_rec2() {
   %a = call i32 @indirect_rec()
   ret i32 %a
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: readnone
-; CHECK-NOT: norecurse
-; CHECK-NEXT: define i32 @extern()
+; BOTH-NOT: norecurse
+; BOTH-NEXT: define i32 @extern()
 define i32 @extern() {
   %a = call i32 @k()
   ret i32 %a
 }
 
-; CHECK: Function Attrs
-; CHECK-NEXT: declare i32 @k()
+; BOTH: Function Attrs
+; BOTH-NEXT: declare i32 @k()
 declare i32 @k() readnone
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: nounwind
-; CHECK-NOT: norecurse
+; BOTH-NOT: norecurse
 ; CHECK-NEXT: define void @intrinsic(i8* nocapture %dest, i8* nocapture readonly %src, i32 %len)
+; ATTRIBUTOR-NEXT: define void @intrinsic(i8* nocapture %dest, i8* nocapture %src, i32 %len)
 define void @intrinsic(i8* %dest, i8* %src, i32 %len) {
   call void @llvm.memcpy.p0i8.p0i8.i32(i8* %dest, i8* %src, i32 %len, i1 false)
   ret void
 }
 
-; CHECK: Function Attrs
-; CHECK-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32
+; BOTH: Function Attrs
+; BOTH-NEXT: declare void @llvm.memcpy.p0i8.p0i8.i32
 declare void @llvm.memcpy.p0i8.p0i8.i32(i8*, i8*, i32, i1)
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: norecurse readnone
+; FIXME: missing "norecurse"
+; ATTRIBUTOR-SAME: nosync
 ; CHECK-NEXT: define internal i32 @called_by_norecurse()
 define internal i32 @called_by_norecurse() {
   %a = call i32 @k()
   ret i32 %a
 }
-; CHECK: Function Attrs
-; CHECK-NEXT: define void @m()
+; BOTH: Function Attrs
+; BOTH-NEXT: define void @m()
 define void @m() norecurse {
   %a = call i32 @called_by_norecurse()
   ret void
 }
 
-; CHECK: Function Attrs
+; BOTH: Function Attrs
 ; CHECK-SAME: norecurse readnone
+; FIXME: missing "norecurse"
+; ATTRIBUTOR-SAME: nosync
 ; CHECK-NEXT: define internal i32 @called_by_norecurse_indirectly()
 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
 }
+
+; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
+; ATTRIBUTOR-NEXT: define void @f(i32 %x)
+define void @f(i32 %x)  {
+entry:
+  %x.addr = alloca i32, align 4
+  store i32 %x, i32* %x.addr, align 4
+  %0 = load i32, i32* %x.addr, align 4
+  %tobool = icmp ne i32 %0, 0
+  br i1 %tobool, label %if.then, label %if.end
+
+if.then:
+  call void @g() norecurse
+  br label %if.end
+
+if.end:
+  ret void
+}
+
+; BOTH: define void @g()
+define void @g() norecurse {
+entry:
+  call void @f(i32 0)
+  ret void
+}
+
+; ATTRIBUTOR-NOT: Function Attrs
+; ATTRIBUTOR: define linkonce_odr i32 @leaf_redefinable()
+define linkonce_odr i32 @leaf_redefinable() {
+  ret i32 1
+}
+
+; Call through a function pointer
+; ATTRIBUTOR-NOT: Function Attrs
+; ATTRIBUTOR: define i32 @eval_func(i32 (i32)* nocapture %0, i32 %1)
+define i32 @eval_func(i32 (i32)* , i32) local_unnamed_addr {
+  %3 = tail call i32 %0(i32 %1) #2
+  ret i32 %3
+}
+
+declare void @unknown()
+; Call an unknown function in a dead block.
+; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind willreturn
+; ATTRIBUTOR: define i32 @call_unknown_in_dead_block()
+define i32 @call_unknown_in_dead_block() local_unnamed_addr {
+  ret i32 0
+Dead:
+  tail call void @unknown()
+  ret i32 1
+}
+

llvm/test/Transforms/FunctionAttrs/willreturn.ll

 ; RUN: opt -functionattrs -S < %s | FileCheck %s --check-prefix=FNATTR
-; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
+; RUN: opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefix=ATTRIBUTOR
 
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test cases specifically designed for the "willreturn" function attribute.
 ; We use FIXME's to indicate problems and missing attributes.
 
 
 ; TEST 1 (positive case)
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define void @only_return()
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable willreturn
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @only_return()
 define void @only_return() #0 {
     ret void
 }
 
 
 ; TEST 2 (positive & negative case)
 ; 2.1 (positive case)

 ;   }
 ;   return fact_maybe_not_halt( n > 0 ? n-1 : n) * n;
 ; }
 ; fact_maybe_not(-1) doesn't stop.
 
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr
 define i32 @fact_maybe_not_halt(i32 %0) local_unnamed_addr #0 {
   %2 = icmp eq i32 %0, 0
   br i1 %2, label %11, label %3
 
 ; <label>:3:                                      ; preds = %1, %3
   %4 = phi i32 [ %8, %3 ], [ %0, %1 ]

 ;     ans *= i;
 ;   }
 ;   return ans;
 ; }
 
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @fact_loop(i32 %0)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @fact_loop(i32 %0) local_unnamed_addr
 define i32 @fact_loop(i32 %0) local_unnamed_addr #0 {
   %2 = icmp slt i32 %0, 1
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %5, %1
   %4 = phi i32 [ 1, %1 ], [ %8, %5 ]
   ret i32 %4
define void @call_maybe_noreturn() #0 {
     tail call void @maybe_noreturn()
     ret void
 }
 
 
 ; TEST 8 (positive case)
 ; Check propagation.
 
-; FNATTR: Function Attrs: willreturn
+; FNATTR: Function Attrs: norecurse willreturn
 ; FNATTR-NEXT: declare void @will_return()
-; ATTRIBUTOR: Function Attrs: willreturn
+; ATTRIBUTOR: Function Attrs: norecurse willreturn
 ; ATTRIBUTOR-NEXT: declare void @will_return()
-declare void @will_return() willreturn
+declare void @will_return() willreturn norecurse
 
-; FIXME: missing willreturn
-; FNATTR: Function Attrs: noinline nounwind uwtable
+; FNATTR: Function Attrs: noinline norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @f1()
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @f1()
 define void @f1() #0 {
     tail call void @will_return()
     ret void
 }
 
-; FIXME: missing willreturn
-; FNATTR: Function Attrs: noinline nounwind uwtable
+; FNATTR: Function Attrs: noinline norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @f2()
-; FIXME: missing willreturn
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @f2()
 define void @f2() #0 {
     tail call void @f1()
     ret void
 }
 
 
 ; TEST 9 (negative case)
 ; call willreturn function in endless loop.
 
-; FNATTR: Function Attrs: noinline nounwind uwtable
+; FNATTR: Function Attrs: noinline norecurse nounwind uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define void @call_will_return_but_has_loop()
-; ATTRIBUTOR: Function Attrs: noinline noreturn nounwind uwtable
+; ATTRIBUTOR: Function Attrs: noinline norecurse noreturn nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define void @call_will_return_but_has_loop()
 define void @call_will_return_but_has_loop() #0 {
   br label %label1
 label1:
   tail call void @will_return()
   br label %label2
 label2:

 ;        ans += p[i];
 ;    }
 ;    return ans;
 ; }
 
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly %0)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @loop_constant_trip_count(i32* nocapture readonly %0)
 define i32 @loop_constant_trip_count(i32* nocapture readonly %0) #0 {
   br label %3
 
 ; <label>:2:                                      ; preds = %3
   ret i32 %8
 
 ; <label>:3:                                      ; preds = %3, %1

 ;     for(unsigned i = s;i != e;i+=offset){
 ;         ans += p[i];
 ;     }
 ;     return ans;
 ; }
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr
 define i32 @loop_trip_count_unbound(i32 %0, i32 %1, i32* nocapture readonly %2, i32 %3) local_unnamed_addr #0 {
   %5 = icmp eq i32 %0, %1
   br i1 %5, label %6, label %8
 
 ; <label>:6:                                      ; preds = %8, %4
   %7 = phi i32 [ 0, %4 ], [ %14, %8 ]

 ;    }
 ;    return ans;
 ;  }
 
 
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline norecurse nounwind readonly uwtable
 ; FNATTR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr
 
 define i32 @loop_trip_dec(i32 %0, i32* nocapture readonly %1) local_unnamed_addr #0 {
   %3 = icmp sgt i32 %0, -1
   br i1 %3, label %4, label %14
 
 ; <label>:4:                                      ; preds = %2
   %5 = sext i32 %0 to i64
; <label>:14:                                     ; preds = %6, %2
   ret i32 %15
 }
 
 ; TEST 14 (positive case)
 ; multiple return
 
 ; FNATTR: Function Attrs: noinline norecurse nounwind readnone uwtable
 ; FNATTR-NEXT: define i32 @multiple_return(i32 %a)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable willreturn
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define i32 @multiple_return(i32 %a)
 define i32 @multiple_return(i32 %a) #0 {
   %b =  icmp eq i32 %a, 0
   br i1 %b, label %t, label %f
 
 t:
   ret i32 1
 f:
   ret i32 0
 }
 
 ; TEST 15 (positive & negative case)
 ; unreachable exit
 
 ; 15.1 (positive case)
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define void @unreachable_exit_positive1()
-; ATTRIBUTOR: Function Attrs: noinline nounwind uwtable willreturn
+; ATTRIBUTOR: Function Attrs: noinline norecurse nounwind uwtable willreturn
 ; ATTRIBUTOR-NEXT: define void @unreachable_exit_positive1()
 define void @unreachable_exit_positive1() #0 {
   tail call void @will_return()
   ret void
 
 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FIXME: missing willreturn
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NEXT: define i32 @unreachable_exit_positive2(i32 %0)
-; ATTRIBUTOR: Function Attrs: nofree noinline nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse nosync nounwind uwtable
 ; ATTRIBUTOR-NEXT: define i32 @unreachable_exit_positive2(i32 %0)
 define i32 @unreachable_exit_positive2(i32) local_unnamed_addr #0 {
   %2 = icmp slt i32 %0, 1
   br i1 %2, label %3, label %5
 
 ; <label>:3:                                      ; preds = %5, %1
   %4 = phi i32 [ 1, %1 ], [ %8, %5 ]
   ret i32 %4

 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FNATTR: Function Attrs: noinline nounwind uwtable
 ; FNATTR-NOT: willreturn
 ; FNATTR-NEXT: define void @unreachable_exit_negative2()
-; ATTRIBUTOR: Function Attrs: nofree noinline noreturn nosync nounwind uwtable
+; ATTRIBUTOR: Function Attrs: nofree noinline norecurse noreturn nosync nounwind uwtable
 ; ATTRIBUTOR-NOT: willreturn
 ; ATTRIBUTOR-NEXT: define void @unreachable_exit_negative2()
 define void @unreachable_exit_negative2() #0 {
 
   br label %L1
 L1:
   br label %L2
 L2:
   br label %L1
 
 unreachable_label:
   tail call void @exit(i32 0)
   unreachable
 }
 
 ; FNATTR: Function Attrs: noreturn nounwind