diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp
--- a/llvm/lib/Transforms/IPO/Attributor.cpp
+++ b/llvm/lib/Transforms/IPO/Attributor.cpp
@@ -23,6 +23,7 @@
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/InstIterator.h"
+#include "llvm/IR/IntrinsicInst.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
@@ -43,6 +44,8 @@
 STATISTIC(NumAttributesManifested,
           "Number of abstract attributes manifested in IR");
 
+STATISTIC(NumFnNoRecurse, "Number of functions marked norecurse");
+
 // TODO: Determine a good default value.
 //
 // In the LLVM-TS and SPEC2006, 32 seems to not induce compile time overheads
@@ -86,10 +89,13 @@
 
   if (!Attr.isEnumAttribute())
     return;
-  //switch (Attr.getKindAsEnum()) {
-  //default:
-  //  return;
-  //}
+  switch (Attr.getKindAsEnum()) {
+  case Attribute::NoRecurse:
+    NumFnNoRecurse++;
+    return;
+  default:
+    return;
+  }
 }
 
 /// Helper to identify the correct offset into an attribute list.
@@ -241,6 +247,107 @@
   return const_cast<AbstractAttribute *>(this)->getAnchorScope();
 }
 
+/// ------------------------ No-Recurse Attributes ----------------------------
+
+struct AANoRecurseFunction : public AbstractAttribute, BooleanState {
+
+  /// See AbstractAttribute::AbstractAttribute(...).
+  AANoRecurseFunction(Function &F, InformationCache &InfoCache)
+      : AbstractAttribute(F, InfoCache) {}
+
+  /// See AbstractAttribute::getState()
+  ///{
+  AbstractState &getState() override { return *this; }
+  const AbstractState &getState() const override { return *this; }
+  ///}
+
+  /// See AbstractAttribute::getManifestPosition().
+  virtual ManifestPosition getManifestPosition() const override {
+    return MP_FUNCTION;
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  virtual ChangeStatus updateImpl(Attributor &A) override;
+
+  /// See AbstractState::getAsStr().
+  const std::string getAsStr() const override {
+    return getAssumed() ? "norecurse" : "may-recurse";
+  }
+
+  /// See AbstractAttribute::getAttrKind()
+  virtual Attribute::AttrKind getAttrKind() const override { return ID; }
+
+  /// The identifier used by the Attributor for this class of attributes.
+  static constexpr Attribute::AttrKind ID = Attribute::NoRecurse;
+};
+
+ChangeStatus AANoRecurseFunction::updateImpl(Attributor &A) {
+  Function &Fn = getAnchorScope();
+
+  // The map from instruction opcodes to those instructions in the function.
+  auto &OpcodeInstMap = InfoCache.getOpcodeInstMapForFunction(Fn);
+
+  // Check all "call-like" opcodes. If any call site was found without the
+  // no-recurse attribute, assume recursion through that call site.
+  for (unsigned Opcode :
+       {(unsigned)Instruction::Invoke, (unsigned)Instruction::CallBr,
+        (unsigned)Instruction::Call}) {
+    for (Instruction *I : OpcodeInstMap[Opcode]) {
+      // TODO: This should not be done here but at the intrinsic side!
+      //       See also: https://bugs.llvm.org/show_bug.cgi?id=34696
+      //       and:
+      //       http://llvm.1065342.n5.nabble.com/llvm-dev-Is-every-intrinsic-norecurse-td109617.html
+      if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
+        switch (II->getIntrinsicID()) {
+        case Intrinsic::annotation:
+        case Intrinsic::assume:
+        case Intrinsic::cos:
+        case Intrinsic::dbg_addr:
+        case Intrinsic::dbg_label:
+        case Intrinsic::dbg_declare:
+        case Intrinsic::dbg_value:
+        case Intrinsic::donothing:
+        case Intrinsic::exp:
+        case Intrinsic::exp2:
+        case Intrinsic::expect:
+        case Intrinsic::fabs:
+        case Intrinsic::floor:
+        case Intrinsic::log:
+        case Intrinsic::log10:
+        case Intrinsic::log2:
+        case Intrinsic::lifetime_start:
+        case Intrinsic::lifetime_end:
+        case Intrinsic::memset:
+        case Intrinsic::memcpy:
+        case Intrinsic::memmove:
+        case Intrinsic::pow:
+        case Intrinsic::powi:
+        case Intrinsic::sin:
+        case Intrinsic::sqrt:
+          continue;
+        default:
+          break;
+        }
+      }
+
+      ImmutableCallSite ICS(I);
+      assert(ICS && "Found an instruction with call base opcode that did not "
+                    "result in a call site");
+
+      if (ICS.hasFnAttr(getAttrKind()))
+        continue;
+
+      indicatePessimisticFixpoint();
+      return ChangeStatus::CHANGED;
+    }
+  }
+
+  // This attribute does not rely on other attributes as of now. Consequently,
+  // there is no need to update the state again.
+  indicateOptimisticFixpoint();
+  return ChangeStatus::UNCHANGED;
+}
+
 /// ----------------------------------------------------------------------------
 ///                               Attributor
 /// ----------------------------------------------------------------------------
@@ -383,6 +490,9 @@
     Function &F, InformationCache &InfoCache,
     DenseSet</* Attribute::AttrKind */ unsigned> *Whitelist) {
 
+  // Every function might be "no-recurse".
+  registerAA(*new AANoRecurseFunction(F, InfoCache));
+
   // Walk all instructions to find more attribute opportunities and also
   // interesting instructions that might be queried by abstract attributes
   // during their initialization or update.
@@ -397,10 +507,25 @@
     // to concrete attributes we only cache the ones that are as identified in
     // the following switch.
     // Note: There are no concrete attributes now so this is initially empty.
-    //switch (I.getOpcode()) {
-    //default:
-    //  break;
-    //}
+    switch (I.getOpcode()) {
+    default:
+      // The below list of "call-lile" opcodes has to be kept in sync with
+      // CallBase/CallSite and with the abstract attributes using the
+      // "Attributor::getOpcodeInstMapForFunction(...)" functionality. To verify
+      // at least the former property we provide an assertion here that should
+      // immediatly fire once the below list of switch cases is out of sync with
+      // the call site/base implementation.
+      assert((!ImmutableCallSite(&I)) && (!isa<CallBase>(&I)) &&
+             "New call site/base instruction type needs to be known in the "
+             "attributor!");
+      break;
+    case Instruction::Invoke:
+    case Instruction::CallBr:
+    case Instruction::Call:
+      // Call-like instructions are interesting for AANoRecurseFunction.
+      IsInterestingOpcode = true;
+      break;
+    }
     if (IsInterestingOpcode)
       InstOpcodeMap[I.getOpcode()].push_back(&I);
     if (I.mayReadOrWriteMemory())
diff --git a/llvm/test/Transforms/FunctionAttrs/norecurse.ll b/llvm/test/Transforms/FunctionAttrs/norecurse.ll
--- a/llvm/test/Transforms/FunctionAttrs/norecurse.ll
+++ b/llvm/test/Transforms/FunctionAttrs/norecurse.ll
@@ -89,3 +89,10 @@
   call void @o()
   ret void
 }
+
+; FIXME: This test exposes a bug: https://llvm.org/PR41336
+; CHECK: Function Attrs: norecurse
+; CHECK-NEXT: define i32 @leaf_redefinable()
+define linkonce_odr i32 @leaf_redefinable() {
+  ret i32 1
+}