[Inliner][NewPM] Inline functions outside of current SCC first

[haicheng]

Summary

When we enabled the new PM, we noticed several big regressions. One reason is that the new PM has different inline orders. The legacy PM has a step that the new PM does not have which is moving the call sites calling functions in the current SCC to the end of the iteration list. I don't know whether the new PM omits this intentionally or not, but I can see two benefits of doing this.

1. This step first inlines functions outside of the current SCC to discourage functions inside the same SCC inlining each other which can bloat up the code size.

1. Inlining a callee inside the current SCC likely makes the caller recursive. LLVM does not inline any recursive functions.

One drawback I can think of is that callsites from the same caller are stored in two places instead of one. Thus, we may have to switch function proxies more often.

This patch just copied the code from the legacy PM to the new PM. Here is the SPEC performance and code size change

	code size (%) (- is smaller)	performance (%) (+ is faster)
spec2000/ammp	-1.32	+0.02
spec2000/vortex	-1.06	-0.21
spec2006/gobmk	+0.8	+1.22
spec2006/povray	-0.11	+31.90
spec2017/leela	-1.67	-0.78
spec2017/povray	-0.24	+27.12

[haicheng]

Kindly Ping

Please let me know if this is the right approach.

[davidxl]

Using heuristic like this for inline order decision is like tossing a coin. It is very likely that doing this can hurt some cases where inlining of inner edges are important but gets blocked.

Due to current practical limitation in the inliner such as lack of the ability to inline self recursive functions, this patch can help to workaround that limitation a little, so the patch looks fine for now, though we should not depend strongly on this inline behavior in the future.

[haicheng]

In D40097#932995, @davidxl wrote:

Using heuristic like this for inline order decision is like tossing a coin. It is very likely that doing this can hurt some cases where inlining of inner edges are important but gets blocked.

Due to current practical limitation in the inliner such as lack of the ability to inline self recursive functions, this patch can help to workaround that limitation a little, so the patch looks fine for now, though we should not depend strongly on this inline behavior in the future.

Thank you for your reply.

I agree that this heuristic is not the best, but it is consistent with what the legacy PM does so that we wouldn't have unpleasant surprise (e.g. spec2006/2017 povray listed in the summary) when we switch to the new PM. When we have a better one, we can certainly replace this heuristic.

Or I can modify the heuristic in this way: only call sites which can make the callers recursive if the callees are inlined are moved to the end of the candidate list.

[haicheng]

Kindly Ping.

[haicheng]

Kindly Ping (#2).

[haicheng]

Kindly Ping (#3)

[haicheng]

Now I only move the callsites whose callees also call the callers to the end of the inline list to delay the creation of recursive functions. Is it more acceptable?

[Prazek]

Unfortunately, I don't know much about the inliner to accept it, but propsy for finding it and fixing.
I am sorry to see that it takes so much time for the review, I hope someone who knows about the inliner will review it soon.

[haicheng]

Thank you, Piotr.

This patch just lets NewPM be consistent with the legacy PM to prevent big performance drop we observed when turning on NewPM.

lib/Transforms/IPO/Inliner.cpp

PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   // To compensate for this, we don't process transitive edges made immediate
   // by inlining until we've done one pass of inlining across the entire SCC.
   // Large, highly connected SCCs still lead to some amount of code bloat in
   // this model, but it is uniformly spread across all the functions in the SCC
   // and eventually they all become too large to inline, rather than
   // incrementally maknig a single function grow in a super linear fashion.
   SmallVector<std::pair<CallSite, int>, 16> Calls;
 
+  SmallPtrSet<Function *, 8> SCCFunctions;
+
   // Populate the initial list of calls in this SCC.
   for (auto &N : InitialC) {
     // We want to generally process call sites top-down in order for
     // simplifications stemming from replacing the call with the returned value
     // after inlining to be visible to subsequent inlining decisions.
     // FIXME: Using instructions sequence is a really bad way to do this.
     // Instead we should do an actual RPO walk of the function body.
     for (Instruction &I : instructions(N.getFunction()))
       if (auto CS = CallSite(&I))
         if (Function *Callee = CS.getCalledFunction())
           if (!Callee->isDeclaration())
             Calls.push_back({CS, -1});
+    SCCFunctions.insert(&N.getFunction());
   }
   if (Calls.empty())
     return PreservedAnalyses::all();
 
-  // Capture updatable variables for the current SCC and RefSCC.
+  // Now that we have all of the call sites, move the ones to functions in the
+  // current SCC to the end of the list.
+  unsigned FirstCallInSCC = Calls.size();
+  for (unsigned i = 0; i < FirstCallInSCC; ++i)
+    if (Function *F = Calls[i].first.getCalledFunction())
+      if (SCCFunctions.count(F))
+        std::swap(Calls[i--], Calls[--FirstCallInSCC]);
+
+  // Capture updatable variables for the current SC and RefSCC.
   auto *C = &InitialC;
   auto *RC = &C->getOuterRefSCC();
 
   // When inlining a callee produces new call sites, we want to keep track of
   // the fact that they were inlined from the callee.  This allows us to avoid
   // infinite inlining in some obscure cases.  To represent this, we use an
   // index into the InlineHistory vector.
   SmallVector<std::pair<Function *, int>, 16> InlineHistory;

test/Transforms/Inline/cgscc-order.ll

+; RUN: opt < %s -passes='cgscc(inline)' -S -inline-threshold=30 | FileCheck %s
+
+@glbl = external global i32
+
+define void @out() {
+  store i32 0, i32* @glbl
+  store i32 1, i32* @glbl
+  store i32 2, i32* @glbl
+  store i32 3, i32* @glbl
+  store i32 4, i32* @glbl
+  store i32 5, i32* @glbl
+  store i32 6, i32* @glbl
+  store i32 7, i32* @glbl
+  store i32 8, i32* @glbl
+  store i32 9, i32* @glbl
+  ret void
+}
+
+define void @scc_a() {
+entry:
+  call void @scc_b()
+  call void @out()
+  ret void
+}
+
+define void @scc_b() {
+; CHECK-LABEL: define void @scc_b(
+; Make sure out is inlined into scc_a first so that scc_a is too big to be 
+; inined into scc_b
+entry:
+; CHECK:    call
+; CHECK-NEXT:    ret
+  call void @scc_a()
+  ret void
+}
+