Index: llvm/lib/Analysis/InlineCost.cpp
===================================================================
--- llvm/lib/Analysis/InlineCost.cpp
+++ llvm/lib/Analysis/InlineCost.cpp
@@ -680,7 +680,7 @@
       if (CA.analyze().isSuccess()) {
         // We were able to inline the indirect call! Subtract the cost from the
         // threshold to get the bonus we want to apply, but don't go below zero.
-        Cost -= std::max(0, CA.getThreshold() - CA.getCost());
+        Cost -= std::min(Cost, std::max(0, CA.getThreshold() - CA.getCost()));
       }
     } else
       // Otherwise simply add the cost for merely making the call.
Index: llvm/lib/Transforms/IPO/Inliner.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Inliner.cpp
+++ llvm/lib/Transforms/IPO/Inliner.cpp
@@ -418,8 +418,18 @@
               // inline through the SCC the function will end up being
               // self-recursive which the inliner bails out on, and inlining
               // within an SCC is necessary for performance.
-              if (CalleeSCC != C &&
-                  CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) {
+              // Additionally, suppress further inlining through newly
+              // devirtualised calls, to avoid ping-ponging between mutual
+              // recursion hidden behind indirect calls.
+              auto WasCallEdge = [&CG](Function &Callee, Function &NewCallee) {
+                LazyCallGraph::Node &CalleeN = CG.get(Callee);
+                LazyCallGraph::Node &NewCalleeN = CG.get(NewCallee);
+                LazyCallGraph::Edge *E = CalleeN->lookup(NewCalleeN);
+                return E && E->isCall();
+              };
+              if ((CalleeSCC != C &&
+                   CalleeSCC == CG.lookupSCC(CG.get(*NewCallee))) ||
+                  !WasCallEdge(Callee, *NewCallee)) {
                 Attribute NewCBCostMult = Attribute::get(
                     M.getContext(),
                     InlineConstants::FunctionInlineCostMultiplierAttributeName,
Index: llvm/test/Transforms/Inline/devirtualize-7.ll
===================================================================
--- /dev/null
+++ llvm/test/Transforms/Inline/devirtualize-7.ll
@@ -0,0 +1,95 @@
+; RUN: opt %s -o - --passes='cgscc(inline)' -S | FileCheck %s
+
+; The mutual recursion between @longname and @rec_call_to_longname grows
+; exponentially due to the two devirtualised calls -- the inliner should
+; annotate one of the functions in the SCC (rec_call_to_longname) with the
+; "this is part of a cycle" flag, function-inline-cost-multiplier. The fact
+; that the mutual recursion is hidden by virtual calls prevents other
+; facilities to prevent over-inlining from firing.
+;
+; Check the entire contents of the body of @d. The exact layout isn't important,
+; but without the multiplier attribute it grows from 21 to 45 direct calls to
+; extern1.
+;
+; NB: add extra direct function calls in the chain from @e to @a to add an
+; additional round of potential inlining, pre-patch this causes exponential
+; growth in the size of @e.
+
+; CHECK-LABEL: define internal void @d(
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @longname(ptr @rec_call_to_longname) #[[ATTR0]]
+; CHECK-NEXT:    ret void
+
+; CHECK: attributes #[[ATTR0]] = { "function-inline-cost-multiplier"="128" }
+
+target triple = "x86_64-unknown-unknown"
+
+declare void @extern1()
+
+define internal void @rec_call_to_longname(ptr %longname) {
+  call void %longname(ptr @rec_call_to_longname)
+  ret void
+}
+
+define internal void @longname(ptr %0) {
+  call void @extern1()
+  call void @extern1()
+  call void @extern1()
+  call void %0(ptr @longname)  ; Exponential growth occurs between these two devirt calls.
+  call void %0(ptr @longname)
+  ret void
+}
+
+define void @e() {
+  call void @d()
+  call void @d()
+  ret void
+}
+
+define internal void @d() {
+  call void @c()
+  ret void
+}
+
+define internal void @c() {
+  call void @b()
+  ret void
+}
+
+define internal void @b() {
+  call void @a()
+  ret void
+}
+
+define internal void @a() {
+  call void @rec_call_to_longname(ptr @longname)
+  ret void
+}
+