Index: llvm/lib/Analysis/InlineCost.cpp
===================================================================
--- llvm/lib/Analysis/InlineCost.cpp
+++ llvm/lib/Analysis/InlineCost.cpp
@@ -938,8 +938,14 @@
 
     if (std::optional<int> AttrCostMult = getStringFnAttrAsInt(
             CandidateCall,
-            InlineConstants::FunctionInlineCostMultiplierAttributeName))
+            InlineConstants::FunctionInlineCostMultiplierAttributeName)) {
+      // In rare circumstances where the cost is negative, this cost-multiplier
+      // can never increase the cost. To avoid this, add the multiplier first,
+      // so that negative inlining costs will eventually cross over into
+      // positive territory, allowing the multiplier to have an effect.
+      Cost += *AttrCostMult;
       Cost *= *AttrCostMult;
+    }
 
     if (std::optional<int> AttrThreshold =
             getStringFnAttrAsInt(CandidateCall, "function-inline-threshold"))
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 @rec_call_to_longname(ptr @longname) #[[ATTR0:[0-9]+]]
+; CHECK-NEXT:    call void @rec_call_to_longname(ptr @longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @rec_call_to_longname(ptr @longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @rec_call_to_longname(ptr @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 @rec_call_to_longname(ptr @longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @rec_call_to_longname(ptr @longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @extern1()
+; CHECK-NEXT:    call void @rec_call_to_longname(ptr @longname) #[[ATTR0]]
+; CHECK-NEXT:    call void @rec_call_to_longname(ptr @longname) #[[ATTR0]]
+; CHECK-NEXT:    ret void
+
+; CHECK: attributes #[[ATTR0]] = { "function-inline-cost-multiplier"="64" }
+
+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
+}
+
Index: llvm/test/Transforms/Inline/inline-cost-attributes.ll
===================================================================
--- llvm/test/Transforms/Inline/inline-cost-attributes.ll
+++ llvm/test/Transforms/Inline/inline-cost-attributes.ll
@@ -13,7 +13,7 @@
 ; INLINER-LABEL: Inlining calls in: fn2
 ; INLINER-NEXT: Function size: 7
 ; INLINER-NEXT: NOT Inlining (cost=321, threshold=123), Call:   call void @fn1()
-; INLINER-NEXT: NOT Inlining (cost=963, threshold=123), Call:   call void @fn1()
+; INLINER-NEXT: NOT Inlining (cost=972, threshold=123), Call:   call void @fn1()
 ; INLINER-NEXT: NOT Inlining (cost=321, threshold=321), Call:   call void @fn1()
 ; INLINER-NEXT: NOT Inlining (cost=197, threshold=123), Call:   call void @fn1()
 ; INLINER-NEXT: Inlining (cost=197, threshold=321), Call:   call void @fn1()