diff --git a/llvm/lib/Transforms/IPO/Inliner.cpp b/llvm/lib/Transforms/IPO/Inliner.cpp
--- a/llvm/lib/Transforms/IPO/Inliner.cpp
+++ b/llvm/lib/Transforms/IPO/Inliner.cpp
@@ -890,6 +890,30 @@
         continue;
       }
 
+      // Do not inline a function involved in a mutual-recursive cycle. Due to
+      // the lack of a global inline history, such inlining may cause an
+      // exponential size growth as the inlining extends up along the call
+      // graph. Consider the following example,
+      //   void A() { B(); B();}
+      //   void B() { A(); }
+      //   void C() { B(); }
+      //   void D() { C(); }
+      // When processing C, inlining B will result in
+      //   void C() { B(); B(); }
+      // When processing D, inlining C and futher the two B callsites will
+      // result in
+      //   void D() { B(); B(); B(); B(); }
+      // Note that we are only checking mutual-recursion here. Self-recurision
+      // is handled by inline cost analyzer.
+      if (CalleeSCC != C && CalleeSCC->size() > 1 &&
+          Callee.hasFnAttribute(Attribute::AlwaysInline)) {
+        LLVM_DEBUG(dbgs() << "Skipping inlining a node that is involved in a "
+                             "mutual-recursive SCC"
+                          << F.getName() << " -> " << Callee.getName() << "\n");
+        setInlineRemark(*CB, "recursive");
+        continue;
+      }
+
       std::unique_ptr<InlineAdvice> Advice =
           Advisor.getAdvice(*CB, OnlyMandatory);