[Inliner] Mark inlinings stopped with inlining history as noinline

[aeubanks]

Summary

The inline history makes sure that we don't keep inlining due to mutual devirtualization. But this gets forgotten between inliner invocations.

So mark the inlined calls as noinline so we respect previous inline history decisions.

This overlaps with D121084, but they're not redundant since we may not inline completely through a child SCC, but we still want a cost multiplier when that happens.

See discussions in D145516.

[nikic]

This makes sense to me, but I have to admit that I'm getting somewhat lost in all the different ways we have of mitigating exponential inlining (InlineHistory, InlinedInternalEdges, InlineCostMultiplier, ...)

[aeubanks]

add comment

[jmorse]

This speeds up compile time for the reproducer we have by one or two orders of magnitude, definitely feels like the right direction to take, LGTM.

How do you feel about this being in a LLVM-16 point release, exponential behaviour is a reasonably serious defect to be avoided IMO.

llvm/lib/Transforms/IPO/Inliner.cpp

for (; I < (int)Calls.size() && Calls[I].first->getCaller() == &F; ++I) {
       const int InlineHistoryID = P.second;
       Function &Callee = *CB->getCalledFunction();
 
       if (InlineHistoryID != -1 &&
           inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
         LLVM_DEBUG(dbgs() << "Skipping inlining due to history: " << F.getName()
                           << " -> " << Callee.getName() << "\n");
         setInlineRemark(*CB, "recursive");
+        // Set noinline so that we don't forget this decision across CGSCC
+        // iterations.
+        CB->setIsNoInline();
         continue;
       }
 
       // Check if this inlining may repeat breaking an SCC apart that has
       // already been split once before. In that case, inlining here may
       // trigger infinite inlining, much like is prevented within the inliner
       // itself by the InlineHistory above, but spread across CGSCC iterations
       // and thus hidden from the full inline history.

llvm/test/Transforms/Inline/inline-history-noinline.ll

+; RUN: opt -passes=inline -S < %s | FileCheck %s
+
+; This will inline @f1 into @a, causing two new calls to @f2, which will get inlined for two calls to @f1.
+; The inline history should stop recursive inlining here, and make sure to mark the inlined calls as noinline so we don't repeat the inlining later on when @a gets inlined into @b.
+
+define internal void @f1(ptr %p) {
+  call void %p(ptr @f1)
+  ret void
+}
+
+define internal void @f2(ptr %p) {
+  call void %p(ptr @f2)
+  call void %p(ptr @f2)
+  ret void
+}
+
+define void @b() {
+; CHECK-LABEL: define void @b() {
+; CHECK-NEXT:    call void @f1(ptr @f2) #[[NOINLINE:[0-9]+]]
+; CHECK-NEXT:    call void @f1(ptr @f2) #[[NOINLINE]]
+; CHECK-NEXT:    ret void
+;
+  call void @a()
+  ret void
+}
+
+define internal void @a() {
+  call void @f1(ptr @f2)
+  ret void
+}
+
+; CHECK: [[NOINLINE]] = { noinline }