[PM] keeping history when original SCC split and then merge into itself in the same round of SCC update .

[wmi]

Summary

I am not sure whether this is the right approach, just send it out to get comments and improve it on the way.

In https://reviews.llvm.org/rL309784, inline history is added to prevent infinite inlining across multiple run of inliner and SCC update, but the history will only be kept when new SCC is actually generated during SCC update.

We found a case that SCC can be split and then merge into itself in the same round of SCC update, so the same SCC will be pop out from UR.CWorklist and then added back immediately, without any new SCC generated, that is why the existing patch cannot catch the case.

The patch changes the condition when inline history should be kept. If only UR.CWorklist has ever increased after SCC update, it means split has happen and we should keep the inline history to prevent infinite loop.

[chandlerc]

Just wanted to send a quick note that I saw this and am thinking about the approach and the problem. Thanks for looking at this (really tricky) problem!

[eraman]

I also think checking for the change in worklist size better captures the splitting of the SCC than checking C != OldC

test/Transforms/Inline/cgscc-cycle-2.ll

41 ↗

(On Diff #168401)

Please shorten this code by making use of -inline-threshold appropriately.

[wmi]

Addressing Easwaran's comment by shortening the testcase.

[wmi]

FileCheck is not needed in the testcase. Removed it.

[chandlerc]

Minor implementation improvement suggestion...

lib/Transforms/IPO/Inliner.cpp

1163–1170

Using the size seems a bit odd here -- what about instead checking whether C != OldC or if C is in CWorklist? This is efficient with the given data structure and seems like it captures the intent of what you're checking.

[chandlerc]

Basic suggestions on test case...

test/Transforms/Inline/cgscc-cycle-2.ll

1–2 ↗

(On Diff #169121)

We have multiple tests in cgscc-cycle.ll already -- why not add this one there?

I suspect all of those will work fine with whatever inlining threshold makes it easy to exercise.

28 ↗

(On Diff #169121)

I strongly prefer to always include check patterns that verify the inlining we expect to happen does happen (or does not happen). Otherwise some other change may make this entire test irrelevant and we would never know.

100–102 ↗

(On Diff #169121)

Please always minimize the attributes for test cases.

Similarly, use unmangled symbol names, avoid dso_local, and avoid unnecessary tail, align and other noise in the test case. The goal is to make the IR of the test case as minimal as possible while still exercising the behavior and being easy to read and modify.

[chandlerc]

Ok, also had some time to really think about the core problem and approach. Write-up below.

Sorry for the spam of different responses as I looked at this from different angles.

test/Transforms/Inline/cgscc-cycle-2.ll

24–26 ↗

(On Diff #169121)

FWIW, this description and ascii art are *awesome*. Thanks for that.

The only high level question I have here is: *should* we have put the SCC onto the worklist?

One fix (which you have here) is to detect when we will revisit the SCC and retain information to break any cycles in inlining.

Another fix in theory is to avoid putting the SCC onto the queue.

What I haven't yet figured out (but you may have already thought about) is if the split+re-merge operations happen in a context where we might expect interesting SCC-structure changes to have occurred and thus it to be profitable to re-enqueue the SCC on the worklist. If that would normally happen, then ythe fix you have here makes perfect sense. But if this is (for example) just an artifact of the order in which we apply updates, and the SCC is never actually going to be different, maybe we should find a way to avoid enqueuing it? It might be too hard to do that though and we'd still end up where your current patch is...

[wmi]

Thanks for the review.

lib/Transforms/IPO/Inliner.cpp

1163–1170

That is clearer to check if OldC is inside of UR.CWorklist. Done.

test/Transforms/Inline/cgscc-cycle-2.ll

1–2 ↗

(On Diff #169121)

Ok. I move the test into cgscc-cycle.ll

24–26 ↗

(On Diff #169121)

Yeah, Easwaran and I considered the fix to avoid putting the unchanged original SCC into the worklist, but we don't know how to efficiently check when the internal structure of the original SCC is unchanged so we can avoid enqueuing it.

28 ↗

(On Diff #169121)

Ok, check added.

100–102 ↗

(On Diff #169121)

Ok, done.

[wmi]

Address Chandler's comments.

[wmi]

update testcase monster_scc.ll. With the patch, less inlining is happening for monster_scc.ll because we block the inlining inside of the same function in the same SCC from happening more than once.

I do some performance testing on x86 for the patch: run google internal perf benchmark suite and one server benchmark, the performance result is neutral.

[wmi]

Chandler, could you take another look? Although like the testcase monster_scc.ll shows, current solution using inline history for SCC could reduce the inlining in a SCC, it didn't show up as a problem in performance testing, so can we use the solution for now to unblock the infinite compilation issue until we get a better idea for how to keep the inline history?

[wmi]

Ping.

[chandlerc]

Sorry for delay...

I'm still curious if there is a good reason why we are re-adding the SCC to the worklist (there may be! just hard to think through it all), but it does seem fine to just directly catch the cycle and block it here, and is the minimal change that should fix things. LGTM.

lib/Transforms/IPO/Inliner.cpp

1168

nit: s/cache/catch/, s/case/cases/

[wmi]

Thanks for the review!

Wei.

lib/Transforms/IPO/Inliner.cpp

for (int i = 0; i < (int)Calls.size(); ++i) {
     // is a subtle risk we need to prepare for. Other transformations may
     // expose an "infinite inlining" opportunity later, and because of the SCC
     // mutation, we will revisit this function and potentially re-inline. If we
     // do, and that re-inlining also has the potentially to mutate the SCC
     // structure, the infinite inlining problem can manifest through infinite
     // SCC splits and merges. To avoid this, we capture the originating caller
     // node and the SCC containing the call edge. This is a slight over
     // approximation of the possible inlining decisions that must be avoided,
-    // but is relatively efficient to store.
+    // but is relatively efficient to store. We use C != OldC to know when
+    // a new SCC is generated and the original SCC may be generated via merge
+    // in later iterations.
+    //
+    // It is also possible that even if no new SCC is generated
+    // (i.e., C == OldC), the original SCC could be split and then merged
+    // into the same one as itself. and the original SCC will be added into
+    // UR.CWorklist again, we want to cache such case too.
+    //
     // FIXME: This seems like a very heavyweight way of retaining the inline
     // history, we should look for a more efficient way of tracking it.
-    if (C != OldC && llvm::any_of(InlinedCallees, [&](Function *Callee) {
+    if ((C != OldC || UR.CWorklist.count(OldC)) &&
+        llvm::any_of(InlinedCallees, [&](Function *Callee) {
           return CG.lookupSCC(*CG.lookup(*Callee)) == OldC;
         })) {
       LLVM_DEBUG(dbgs() << "Inlined an internal call edge and split an SCC, "
                            "retaining this to avoid infinite inlining.\n");
       UR.InlinedInternalEdges.insert({&N, OldC});
     }
     InlinedCallees.clear();
   }

test/Transforms/Inline/cgscc-cycle.ll

 ; This test contains extremely tricky call graph structures for the inliner to
 ; handle correctly. They form cycles where the inliner introduces code that is
 ; immediately or can eventually be transformed back into the original code. And
 ; each step changes the call graph and so will trigger iteration. This requires
 ; some out-of-band way to prevent infinitely re-inlining and re-transforming the
 ; code.
 ;
-; RUN: opt < %s -passes='cgscc(inline,function(sroa,instcombine))' -S | FileCheck %s
+; RUN: opt < %s -passes='cgscc(inline,function(sroa,instcombine))' -inline-threshold=50 -S | FileCheck %s
 
 
 ; The `test1_*` collection of functions form a directly cycling pattern.
 
 define void @test1_a(i8** %ptr) {
 ; CHECK-LABEL: define void @test1_a(
 entry:
   call void @test1_b(i8* bitcast (void (i8*, i1, i32)* @test1_b to i8*), i1 false, i32 0)
bb2:
   call void %cast(i8* %arg1, i8* %arg2, i1 %flag, i32 %inline_count_inc)
 ; And we should continue to load and call indirectly through optimization.
 ; CHECK:         %[[CAST:.*]] = bitcast i8** %[[A]] to void (i8*, i8*, i1, i32)**
 ; CHECK:         %[[P:.*]] = load void (i8*, i8*, i1, i32)*, void (i8*, i8*, i1, i32)** %[[CAST]]
 ; CHECK:         call void %[[P]](
 
   ret void
 }
+
+; Another infinite inlining case. The initial callgraph is like following:
+;
+;         test3_a <---> test3_b
+;             |         ^
+;             v         |
+;         test3_c <---> test3_d
+;
+; For all the call edges in the call graph, only test3_c and test3_d can be
+; inlined into test3_a, and no other call edge can be inlined.
+;
+; After test3_c is inlined into test3_a, the original call edge test3_a->test3_c
+; will be removed, a new call edge will be added and the call graph becomes:
+;
+;            test3_a <---> test3_b
+;                  \      ^
+;                   v    /
+;     test3_c <---> test3_d
+; But test3_a, test3_b, test3_c and test3_d still belong to the same SCC.
+;
+; Then after test3_a->test3_d is inlined, when test3_a->test3_d is converted to
+; a ref edge, the original SCC will be split into two: {test3_c, test3_d} and
+; {test3_a, test3_b}, immediately after the newly added ref edge
+; test3_a->test3_c will be converted to a call edge, and the two SCCs will be
+; merged into the original one again. During this cycle, the original SCC will
+; be added into UR.CWorklist again and this creates an infinite loop.
+
+@a = global i64 0
+@b = global i64 0
+
+define void @test3_c(i32 %i) {
+entry:
+  %cmp = icmp eq i32 %i, 5
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i64 @random()
+  %t0 = load i64, i64* @a
+  %add = add nsw i64 %t0, %call
+  store i64 %add, i64* @a
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  tail call void @test3_d(i32 %i)
+  %t6 = load i64, i64* @a
+  %add85 = add nsw i64 %t6, 1
+  store i64 %add85, i64* @a
+  ret void
+}
+
+declare i64 @random()
+
+define void @test3_d(i32 %i) {
+entry:
+  %cmp = icmp eq i32 %i, 5
+  br i1 %cmp, label %if.end, label %if.then
+
+if.then:                                          ; preds = %entry
+  %call = tail call i64 @random()
+  %t0 = load i64, i64* @a
+  %add = add nsw i64 %t0, %call
+  store i64 %add, i64* @a
+  br label %if.end
+
+if.end:                                           ; preds = %entry, %if.then
+  tail call void @test3_c(i32 %i)
+  tail call void @test3_b()
+  %t6 = load i64, i64* @a
+  %add79 = add nsw i64 %t6, 3
+  store i64 %add79, i64* @a
+  ret void
+}
+
+; Function Attrs: noinline
+define void @test3_b() #0 {
+entry:
+  tail call void @test3_a()
+  %t0 = load i64, i64* @a
+  %add = add nsw i64 %t0, 2
+  store i64 %add, i64* @a
+  ret void
+}
+
+; Check test3_c is inlined into test3_a once and only once.
+; CHECK-LABEL: @test3_a(
+; CHECK: tail call void @test3_b()
+; CHECK-NEXT: tail call void @test3_d(i32 5)
+; CHECK-NEXT: %[[LD1:.*]] = load i64, i64* @a
+; CHECK-NEXT: %[[ADD1:.*]] = add nsw i64 %[[LD1]], 1
+; CHECK-NEXT: store i64 %[[ADD1]], i64* @a
+; CHECK-NEXT: %[[LD2:.*]] = load i64, i64* @b
+; CHECK-NEXT: %[[ADD2:.*]] = add nsw i64 %[[LD2]], 5
+; CHECK-NEXT: store i64 %[[ADD2]], i64* @b
+; CHECK-NEXT: ret void
+
+; Function Attrs: noinline
+define void @test3_a() #0 {
+entry:
+  tail call void @test3_b()
+  tail call void @test3_c(i32 5)
+  %t0 = load i64, i64* @b
+  %add = add nsw i64 %t0, 5
+  store i64 %add, i64* @b
+  ret void
+}
+
+attributes #0 = { noinline }