[WIP][llvm][Inline] Add helper function for inliner

[taolq]

Summary

Add helper function for inliner and move the big "while" loop into the helper function.

[mtrofin]

Can you detail a bit what motivates the change - do you plan to expose and reuse the code elsewhere? That would help in 2 ways:

• understanding how to review
• avoiding names like 'helper' in descriptions (or - not the case here - APIs). 'helper', like 'utility', communicates very little (it's not like an API would be otherwise called 'unhelpful')

llvm/lib/Transforms/IPO/Inliner.cpp

811

should this be a member function instead - to avoid passing so many parameters?

[kazu]

In D105198#2850223, @mtrofin wrote:

Can you detail a bit what motivates the change - do you plan to expose and reuse the code elsewhere? That would help in 2 ways:

• understanding how to review
• avoiding names like 'helper' in descriptions (or - not the case here - APIs). 'helper', like 'utility', communicates very little (it's not like an API would be otherwise called 'unhelpful')

I think Liqiang is trying to factor out the bit while loop so that we can share it between the module inliner and the SCC inliner, but sure, he can clarify things both in the commit message and the source code.

llvm/lib/Transforms/IPO/Inliner.cpp

void erase_if(function_ref<bool(T)> Pred) override {
     std::make_heap(Heap.begin(), Heap.end(), cmp);
   }
 
 private:
   SmallVector<T, 16> Heap;
   DenseMap<CallBase *, int> InlineHistoryMap;
 };
 
-PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
-                                   CGSCCAnalysisManager &AM, LazyCallGraph &CG,
-                                   CGSCCUpdateResult &UR) {
-  const auto &MAMProxy =
-      AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
+static bool
+doInline(std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> &Calls,
+         InlineAdvisor &Advisor, ProfileSummaryInfo *PSI,
+         FunctionAnalysisManager &FAM, bool OnlyMandatory, bool DoSCCInline,
+         LazyCallGraph::SCC *C, LazyCallGraph &CG,
+         SmallVector<Function *, 4> &DeadFunctions,
+         function_ref<bool(Function &Callee, LazyCallGraph::SCC *C,
+                           LazyCallGraph::Node &N)>
+             CheckSCCSplit,
+         function_ref<void(LazyCallGraph::SCC *C, LazyCallGraph::Node &N,
+                           SmallSetVector<Function *, 4> &InlinedCallees)>
+             UpdateSCC) {
   bool Changed = false;
 
-  assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
-  Module &M = *InitialC.begin()->getFunction().getParent();
-  ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M);
-
-  FunctionAnalysisManager &FAM =
-      AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG)
-          .getManager();
-
-  InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M);
-  Advisor.onPassEntry();
-
-  auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
-
-  // We use a single common worklist for calls across the entire SCC. We
-  // process these in-order and append new calls introduced during inlining to
-  // the end. The PriorityInlineOrder is optional here, in which the smaller
-  // callee would have a higher priority to inline.
-  //
-  // Note that this particular order of processing is actually critical to
-  // avoid very bad behaviors. Consider *highly connected* call graphs where
-  // each function contains a small amount of code and a couple of calls to
-  // other functions. Because the LLVM inliner is fundamentally a bottom-up
-  // inliner, it can handle gracefully the fact that these all appear to be
-  // reasonable inlining candidates as it will flatten things until they become
-  // too big to inline, and then move on and flatten another batch.
-  //
-  // However, when processing call edges *within* an SCC we cannot rely on this
-  // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
-  // functions we can end up incrementally inlining N calls into each of
-  // N functions because each incremental inlining decision looks good and we
-  // don't have a topological ordering to prevent explosions.
-  //
-  // 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.
-  std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> Calls;
-  if (InlineEnablePriorityOrder)
-    Calls = std::make_unique<PriorityInlineOrder>();
-  else
-    Calls = std::make_unique<DefaultInlineOrder<std::pair<CallBase *, int>>>();
-  assert(Calls != nullptr && "Expected an initialized InlineOrder");
-
-  // Populate the initial list of calls in this SCC.
-  for (auto &N : InitialC) {
-    auto &ORE =
-        FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction());
-    // 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 *CB = dyn_cast<CallBase>(&I))
-        if (Function *Callee = CB->getCalledFunction()) {
-          if (!Callee->isDeclaration())
-            Calls->push({CB, -1});
-          else if (!isa<IntrinsicInst>(I)) {
-            using namespace ore;
-            setInlineRemark(*CB, "unavailable definition");
-            ORE.emit([&]() {
-              return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
-                     << NV("Callee", Callee) << " will not be inlined into "
-                     << NV("Caller", CB->getCaller())
-                     << " because its definition is unavailable"
-                     << setIsVerbose();
-            });
-          }
-        }
-  }
-  if (Calls->empty())
-    return PreservedAnalyses::all();
-
-  // Capture updatable variable for the current SCC.
-  auto *C = &InitialC;
-
   // 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;
 
   // Track a set vector of inlined callees so that we can augment the caller
   // with all of their edges in the call graph before pruning out the ones that
   // got simplified away.
   SmallSetVector<Function *, 4> InlinedCallees;
 
-  // Track the dead functions to delete once finished with inlining calls. We
-  // defer deleting these to make it easier to handle the call graph updates.
-  SmallVector<Function *, 4> DeadFunctions;
-
   // Loop forward over all of the calls.
   while (!Calls->empty()) {
     // We expect the calls to typically be batched with sequences of calls that
     // have the same caller, so we first set up some shared infrastructure for
     // this caller. We also do any pruning we can at this layer on the caller
     // alone.
     Function &F = *Calls->front().first->getCaller();
     LazyCallGraph::Node &N = *CG.lookup(F);
-    if (CG.lookupSCC(N) != C) {
+    if (DoSCCInline && CG.lookupSCC(N) != C) {
       Calls->pop();
       continue;
     }
 
     LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
                       << "    Function size: " << F.getInstructionCount()
                       << "\n");
 
while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
         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.
-      if (CG.lookupSCC(*CG.lookup(Callee)) == C &&
-          UR.InlinedInternalEdges.count({&N, C})) {
+      if (DoSCCInline && CheckSCCSplit(Callee, C, N)) {
         LLVM_DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
                              "previously split out of this SCC by inlining: "
                           << F.getName() << " -> " << Callee.getName() << "\n");
         setInlineRemark(*CB, "recursive SCC split");
         continue;
       }
 
       auto Advice = Advisor.getAdvice(*CB, OnlyMandatory);
while (!Calls->empty()) {
     Changed = true;
 
     // At this point, since we have made changes we have at least removed
     // a call instruction. However, in the process we do some incremental
     // simplification of the surrounding code. This simplification can
     // essentially do all of the same things as a function pass and we can
     // re-use the exact same logic for updating the call graph to reflect the
     // change.
+    if (DoSCCInline)
+      UpdateSCC(C, N, InlinedCallees);
+  }
+
+  return Changed;
+}
+
+PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
+                                   CGSCCAnalysisManager &AM, LazyCallGraph &CG,
+                                   CGSCCUpdateResult &UR) {
+  const auto &MAMProxy =
+      AM.getResult<ModuleAnalysisManagerCGSCCProxy>(InitialC, CG);
+  bool Changed = false;
+
+  assert(InitialC.size() > 0 && "Cannot handle an empty SCC!");
+  Module &M = *InitialC.begin()->getFunction().getParent();
+  ProfileSummaryInfo *PSI = MAMProxy.getCachedResult<ProfileSummaryAnalysis>(M);
+
+  FunctionAnalysisManager &FAM =
+      AM.getResult<FunctionAnalysisManagerCGSCCProxy>(InitialC, CG)
+          .getManager();
+
+  InlineAdvisor &Advisor = getAdvisor(MAMProxy, FAM, M);
+  Advisor.onPassEntry();
+
+  auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
 
+  // We use a single common worklist for calls across the entire SCC. We
+  // process these in-order and append new calls introduced during inlining to
+  // the end. The PriorityInlineOrder is optional here, in which the smaller
+  // callee would have a higher priority to inline.
+  //
+  // Note that this particular order of processing is actually critical to
+  // avoid very bad behaviors. Consider *highly connected* call graphs where
+  // each function contains a small amount of code and a couple of calls to
+  // other functions. Because the LLVM inliner is fundamentally a bottom-up
+  // inliner, it can handle gracefully the fact that these all appear to be
+  // reasonable inlining candidates as it will flatten things until they become
+  // too big to inline, and then move on and flatten another batch.
+  //
+  // However, when processing call edges *within* an SCC we cannot rely on this
+  // bottom-up behavior. As a consequence, with heavily connected *SCCs* of
+  // functions we can end up incrementally inlining N calls into each of
+  // N functions because each incremental inlining decision looks good and we
+  // don't have a topological ordering to prevent explosions.
+  //
+  // 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.
+  std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> Calls;
+  if (InlineEnablePriorityOrder)
+    Calls = std::make_unique<PriorityInlineOrder>();
+  else
+    Calls = std::make_unique<DefaultInlineOrder<std::pair<CallBase *, int>>>();
+  assert(Calls != nullptr && "Expected an initialized InlineOrder");
+
+  // Populate the initial list of calls in this SCC.
+  for (auto &N : InitialC) {
+    auto &ORE =
+        FAM.getResult<OptimizationRemarkEmitterAnalysis>(N.getFunction());
+    // 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 *CB = dyn_cast<CallBase>(&I))
+        if (Function *Callee = CB->getCalledFunction()) {
+          if (!Callee->isDeclaration())
+            Calls->push({CB, -1});
+          else if (!isa<IntrinsicInst>(I)) {
+            using namespace ore;
+            setInlineRemark(*CB, "unavailable definition");
+            ORE.emit([&]() {
+              return OptimizationRemarkMissed(DEBUG_TYPE, "NoDefinition", &I)
+                     << NV("Callee", Callee) << " will not be inlined into "
+                     << NV("Caller", CB->getCaller())
+                     << " because its definition is unavailable"
+                     << setIsVerbose();
+            });
+          }
+        }
+  }
+  if (Calls->empty())
+    return PreservedAnalyses::all();
+
+  // Capture updatable variable for the current SCC.
+  auto *C = &InitialC;
+
+  // Track the dead functions to delete once finished with inlining calls. We
+  // defer deleting these to make it easier to handle the call graph updates.
+  SmallVector<Function *, 4> DeadFunctions;
+
+  auto CheckSCCSplit = [&](Function &Callee, LazyCallGraph::SCC *C,
+                           LazyCallGraph::Node &N) {
+    return CG.lookupSCC(*CG.lookup(Callee)) == C &&
+           UR.InlinedInternalEdges.count({&N, C});
+  };
+
+  auto UpdateSCC = [&](LazyCallGraph::SCC *C, LazyCallGraph::Node &N,
+                       SmallSetVector<Function *, 4> &InlinedCallees) {
     // Inside the update, we also update the FunctionAnalysisManager in the
     // proxy for this particular SCC. We do this as the SCC may have changed and
     // as we're going to mutate this particular function we want to make sure
     // the proxy is in place to forward any invalidation events.
     LazyCallGraph::SCC *OldC = C;
     C = &updateCGAndAnalysisManagerForCGSCCPass(CG, *C, N, AM, UR, FAM);
     LLVM_DEBUG(dbgs() << "Updated inlining SCC: " << *C << "\n");
 
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();
-  }
+  };
+
+  Changed = doInline(Calls, Advisor, PSI, FAM, OnlyMandatory, true, C, CG,
+                     DeadFunctions, CheckSCCSplit, UpdateSCC);
 
   // Now that we've finished inlining all of the calls across this SCC, delete
   // all of the trivially dead functions, updating the call graph and the CGSCC
   // pass manager in the process.
   //
   // Note that this walks a pointer set which has non-deterministic order but
   // that is OK as all we do is delete things and add pointers to unordered
   // sets.