Index: llvm/include/llvm/Transforms/IPO/Attributor.h
===================================================================
--- llvm/include/llvm/Transforms/IPO/Attributor.h
+++ llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -96,10 +96,12 @@
 #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"
 
@@ -524,15 +526,25 @@
 struct AnalysisGetter {
   template <typename Analysis>
   typename Analysis::Result *getAnalysis(const Function &F) {
-    if (!FAM)
+    if (!AM || !F.getParent())
       return nullptr;
-    return &FAM->getResult<Analysis>(const_cast<Function &>(F));
+    auto &FAM = AM->getResult<FunctionAnalysisManagerModuleProxy>(
+                      const_cast<Module &>(*F.getParent()))
+                    .getManager();
+    return &FAM.getResult<Analysis>(const_cast<Function &>(F));
   }
-  AnalysisGetter(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
+
+  template <typename Analysis>
+  typename Analysis::Result *getAnalysis(const Module &M) {
+    if (!AM)
+      return nullptr;
+    return &AM->getResult<Analysis>(const_cast<Module &>(M));
+  }
+  AnalysisGetter(ModuleAnalysisManager &AM) : AM(&AM) {}
   AnalysisGetter() {}
 
 private:
-  FunctionAnalysisManager *FAM = nullptr;
+  ModuleAnalysisManager *AM = nullptr;
 };
 
 /// Data structure to hold cached (LLVM-IR) information.
@@ -548,7 +560,19 @@
 /// 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>>;
@@ -577,6 +601,13 @@
     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; }
 
@@ -594,14 +625,15 @@
   /// 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;
Index: llvm/lib/Transforms/IPO/Attributor.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Attributor.cpp
+++ llvm/lib/Transforms/IPO/Attributor.cpp
@@ -1530,10 +1530,38 @@
 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.
-    return indicatePessimisticFixpoint();
+
+    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) }
@@ -3935,6 +3963,9 @@
   // 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);
@@ -4114,7 +4145,7 @@
 
   // 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)
@@ -4150,9 +4181,7 @@
 }
 
 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();
Index: llvm/test/Transforms/FunctionAttrs/norecurse.ll
===================================================================
--- llvm/test/Transforms/FunctionAttrs/norecurse.ll
+++ llvm/test/Transforms/FunctionAttrs/norecurse.ll
@@ -1,81 +1,88 @@
-; 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()
@@ -89,3 +96,34 @@
   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
+}
Index: llvm/test/Transforms/FunctionAttrs/willreturn.ll
===================================================================
--- llvm/test/Transforms/FunctionAttrs/willreturn.ll
+++ llvm/test/Transforms/FunctionAttrs/willreturn.ll
@@ -1,5 +1,5 @@
 ; 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"
@@ -11,7 +11,7 @@
 ; 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
@@ -59,7 +59,7 @@
 ; 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 {
@@ -95,7 +95,7 @@
 ; 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
@@ -340,7 +340,7 @@
 ; 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
@@ -373,7 +373,7 @@
 ; 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 {
@@ -411,7 +411,7 @@
 ; 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 {
@@ -442,7 +442,7 @@
 
 ; 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
@@ -474,7 +474,7 @@
 ; 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
@@ -518,7 +518,7 @@
 ; 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 {