[llvm][Inline] Add a module level inliner

[taolq]

Summary

Add module level inliner, which is a minimum viable product at this point.
Also add some tests for it.

The module inliner does inlining in module level, which is a more general level
than SCC level. The main benefit is that the inliner order could be released.

With this module inliner, the inline order is not limited to bottom-up order, which
is limited in SCC inliner. Also, we could evaluate more globally scope inline order heuristics.
It's possible to explore the improvement with different inline orders with this module inliner.

RFC: https://lists.llvm.org/pipermail/llvm-dev/2021-August/152297.html

[lebedev.ri]

This could use some more words to explain what that is and how it's different from the already-existing stuff.

[taolq]

• move code to a separated file

[lebedev.ri]

In D106448#2893369, @lebedev.ri wrote:

This could use some more words to explain what that is and how it's different from the already-existing stuff.

Note that arc doesn't update review's description from the updated commit message.
Also, that seems like a lot of code duplication.

[taolq]

• add module inliner to opt pipeline
• TODO: remove duplicated code
• TODO: add more description

[kazu]

This patch looks good to me in general. The huge amount of duplicate code is a concern, but I am not too worried as long as it's all contained in ModuleInliner.cpp.

I'd like to see the clang-tidy messages addressed before you check this in. By the way, I think you can safely ignore the one about erase_if.

llvm/include/llvm/Transforms/IPO/Inliner.h

20 ↗

(On Diff #363483)

I think you can remove this line.

[lebedev.ri]

This patch still doesn't explain what it does and why it does what it does.
Links to previous mails about this will be helpful.

[taolq]

• fix bugs
• add more description

[lebedev.ri]

In D106448#2934674, @taolq wrote:

• fix bugs
• add more description

I think my question is: why is the code worth it? what's the short-term plan? what's the long-term plan?
Having *so* much intentional code duplication seems counter-intuitive.

[taolq]

In D106448#2934696, @lebedev.ri wrote:

In D106448#2934674, @taolq wrote:

• fix bugs
• add more description

I think my question is: why is the code worth it? what's the short-term plan? what's the long-term plan?
Having *so* much intentional code duplication seems counter-intuitive.

Thanks for your reviews.
I wonder whether the updated summary makes sense?
If not, I would like to add more explanation.

[taolq]

• remove duplicate code: InlineOrder

[lebedev.ri]

The error is likely on my side, but i'm still not quite seeing it.
I don't see the point in asking yet again, so i would like to instead see an RFC at llvm-dev list.

[taolq]

In D106448#2941757, @lebedev.ri wrote:

The error is likely on my side, but i'm still not quite seeing it.
I don't see the point in asking yet again, so i would like to instead see an RFC at llvm-dev list.

FYI, let me put the RFC here, https://lists.llvm.org/pipermail/llvm-dev/2021-August/152297.html
How about this one? Looking forward to your comments.

[taolq]

In D106448#2970314, @taolq wrote:

In D106448#2941757, @lebedev.ri wrote:

The error is likely on my side, but i'm still not quite seeing it.
I don't see the point in asking yet again, so i would like to instead see an RFC at llvm-dev list.

FYI, let me put the RFC here, https://lists.llvm.org/pipermail/llvm-dev/2021-August/152297.html
How about this one? Looking forward to your comments.

This is just a friendly reminder for the RFC and this revision.
Please let me know if there still is anything confusing.

[taolq]

• rebase to the newest main branch

[taolq]

• fix bug

[kazu]

llvm/lib/Passes/PassBuilder.cpp

113

You should be able to remove this line if you are not otherwise changing PassBuilder.cpp at all.

llvm/lib/Passes/PassBuilderPipelines.cpp

690–691

Why do you need to do this? Performance reasons? Correctness?

llvm/lib/Transforms/IPO/Inliner.cpp

1024–1029 ↗

(On Diff #380666)

This is a strange place to add your module inliner. ModuleInlinerWrapperPass performs:

for each SCC in the bottom-up order:
  Call the inliner on the SCC
  Run cleanup passes on the SCC

Now, if UseModuleInliner is true, we don't add InlinerPass (see a few lines below), so the loop above essentially becomes:

for each SCC in the bottom-up order:
  Run cleanup passes on the SCC

If we are not inlining functions in the "for each" loop, we don't need to visit each SCC in the bottom-up order.

You might consider adding your module inliner just before:

MPM.addPass(buildInlinerPipeline(Level, Phase));

at PassBuilderPipelines.cpp:891 with an appropriate guard like if (UseModuleInliner).

This way, you don't need to touch the existing inliner at all.

[taolq]

llvm/lib/Passes/PassBuilder.cpp

113

I changed PassRegistry.def, here is a compilation error without this line in that file.

llvm/lib/Passes/PassBuilderPipelines.cpp

690–691

For performance and simplicity.
Deferral logic is necessary for bottom-up inlining, while unnecessary in priority-based inlining. So I decided to disable this logic.

[taolq]

• refactor to avoid touching the existing inliner

[taolq]

• remove comment in code

[taolq]

• remove comment in code

[kazu]

Your patch is looking good. Would you mind addressing mostly cosmetic comments? Thanks!

llvm/lib/Passes/PassBuilderPipelines.cpp

927–938

May I suggest you to put this in a function so that you can do something similar to the else clause just a couple of lines below?

MPM.addPass(buildInlinerPipeline(Level, Phase));

Maybe you can create a function named buildModuleInlinerPipeline or something.

This way, the details specific to the module inliner don't clutter buildModuleSimplificationPipeline as much.

935–936

Does your module inliner honor EnableDeferral at all? If so, and there is a good reason to disable it, please add an appropriate comment.

In any event, you should be able to remove if (EnableModuleInliner) because we are already inside if (EnableModuleInliner) above.

llvm/lib/Transforms/IPO/ModuleInliner.cpp

355

Please add a new line at the end.

[kazu]

llvm/lib/Transforms/IPO/ModuleInliner.cpp

136

I just tried to build llvm with your patch. It looks like you need one more argument for IAA. Please rebase your patch. Thanks!

[taolq]

• clean code
• rebase to main branch

[taolq]

• clean code

[kazu]

Thank you for updating the patch. The replay machinery changed since you uploaded your latest version. Please see inline comments about that.

LGTM with the replay logic updated. Thanks a lot for patiently updating multiple iterations!

llvm/lib/Transforms/IPO/ModuleInliner.cpp

63–80

I suggest you to remove the replay inliner logic, which is for debugging purposes.

The declaration of ModuleInlineReplayScope doesn't compile because of recent changes to the replay machinery. You can forget about keeping up with the machinery simply by removing the replay logic here.

119–123

I suggest you to drop this.

148–149

Replace the two replay parameters with {} like so:

if (!IAA.tryCreate(Params, Mode, {})) {

The default-constructed instance has an empty string for its ReplayFile field and thus disables replay.

[taolq]

• remove inliner replay logic

[kazu]

Thank you for updating the patch. LGTM.

[mehdi_amini]

I'm surprised the patch landed as-is without more traction or even more recent activity on the RFC.
Also I don't see here a resolution from @lebedev.ri who marked an objection to this revision?

[lebedev.ri]

In D106448#3132199, @mehdi_amini wrote:

I'm surprised the patch landed as-is without more traction or even more recent activity on the RFC.
Also I don't see here a resolution from @lebedev.ri who marked an objection to this revision?

I simply just don't understand what the high-level endgoal here is.

[kazu]

In D106448#3132199, @mehdi_amini wrote:

I'm surprised the patch landed as-is without more traction or even more recent activity on the RFC.
Also I don't see here a resolution from @lebedev.ri who marked an objection to this revision?

The patch is intended to be a testbed for anybody interested in playing with a priority-based inliner (as opposed to the bottom-up inliner). With the module inliner in place, we can try different priority functions without having to write an entire inliner from scratch.

llvm/include/llvm/Passes/PassBuilder.h

 #include "llvm/ADT/Optional.h"
 #include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Passes/OptimizationLevel.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/PGOOptions.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO/Inliner.h"
+#include "llvm/Transforms/IPO/ModuleInliner.h"
 #include "llvm/Transforms/Instrumentation.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include <vector>
 
 namespace llvm {
 class StringRef;
 class AAManager;
 class TargetMachine;
public:
   ModulePassManager buildModuleSimplificationPipeline(OptimizationLevel Level,
                                                       ThinOrFullLTOPhase Phase);
 
   /// Construct the module pipeline that performs inlining as well as
   /// the inlining-driven cleanups.
   ModuleInlinerWrapperPass buildInlinerPipeline(OptimizationLevel Level,
                                                 ThinOrFullLTOPhase Phase);
 
+  /// Construct the module pipeline that performs inlining with
+  /// module inliner pass.
+  ModuleInlinerPass buildModuleInlinerPipeline(OptimizationLevel Level,
+                                               ThinOrFullLTOPhase Phase);
+
   /// Construct the core LLVM module optimization pipeline.
   ///
   /// This pipeline focuses on optimizing the execution speed of the IR. It
   /// uses cost modeling and thresholds to balance code growth against runtime
   /// improvements. It includes vectorization and other information destroying
   /// transformations. It also cannot generally be run repeatedly on a module
   /// without potentially seriously regressing either runtime performance of
   /// the code or serious code size growth.

llvm/include/llvm/Transforms/IPO/ModuleInliner.h

+//===- ModuleInliner.h - Module level Inliner pass --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_IPO_MODULEINLINER_H
+#define LLVM_TRANSFORMS_IPO_MODULEINLINER_H
+
+#include "llvm/Analysis/InlineAdvisor.h"
+#include "llvm/Analysis/InlineCost.h"
+#include "llvm/Analysis/ReplayInlineAdvisor.h"
+#include "llvm/Analysis/Utils/ImportedFunctionsInliningStatistics.h"
+#include "llvm/IR/PassManager.h"
+#include <utility>
+
+namespace llvm {
+
+class AssumptionCacheTracker;
+class ProfileSummaryInfo;
+
+/// The module inliner pass for the new pass manager.
+///
+/// This pass wires together the inlining utilities and the inline cost
+/// analysis into a module pass. Different from SCC inliner, it considers every
+/// call in every function in the whole module and tries to inline if
+/// profitable. With this module level inliner, it is possible to evaluate more
+/// heuristics in the module level such like PriorityInlineOrder. It can be
+/// tuned with a number of parameters to control what cost model is used and
+/// what tradeoffs are made when making the decision.
+class ModuleInlinerPass : public PassInfoMixin<ModuleInlinerPass> {
+public:
+  ModuleInlinerPass(InlineParams Params = getInlineParams(),
+                    InliningAdvisorMode Mode = InliningAdvisorMode::Default)
+      : Params(Params), Mode(Mode){};
+  ModuleInlinerPass(ModuleInlinerPass &&Arg) = default;
+
+  PreservedAnalyses run(Module &, ModuleAnalysisManager &);
+
+private:
+  InlineAdvisor &getAdvisor(const ModuleAnalysisManager &MAM,
+                            FunctionAnalysisManager &FAM, Module &M);
+  std::unique_ptr<InlineAdvisor> OwnedAdvisor;
+  const InlineParams Params;
+  const InliningAdvisorMode Mode;
+};
+} // end namespace llvm
+
+#endif // LLVM_TRANSFORMS_IPO_MODULEINLINER_H

llvm/lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/IPO/HotColdSplitting.h"
 #include "llvm/Transforms/IPO/IROutliner.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/Transforms/IPO/LoopExtractor.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/MergeFunctions.h"
+#include "llvm/Transforms/IPO/ModuleInliner.h"
 #include "llvm/Transforms/IPO/OpenMPOpt.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/SampleProfile.h"
 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
 #include "llvm/Transforms/IPO/StripDeadPrototypes.h"
 #include "llvm/Transforms/IPO/StripSymbols.h"
 #include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"

llvm/lib/Passes/PassBuilderPipelines.cpp

 #include "llvm/Transforms/IPO/GlobalOpt.h"
 #include "llvm/Transforms/IPO/GlobalSplit.h"
 #include "llvm/Transforms/IPO/HotColdSplitting.h"
 #include "llvm/Transforms/IPO/IROutliner.h"
 #include "llvm/Transforms/IPO/InferFunctionAttrs.h"
 #include "llvm/Transforms/IPO/Inliner.h"
 #include "llvm/Transforms/IPO/LowerTypeTests.h"
 #include "llvm/Transforms/IPO/MergeFunctions.h"
+#include "llvm/Transforms/IPO/ModuleInliner.h"
 #include "llvm/Transforms/IPO/OpenMPOpt.h"
 #include "llvm/Transforms/IPO/PartialInlining.h"
 #include "llvm/Transforms/IPO/SCCP.h"
 #include "llvm/Transforms/IPO/SampleProfile.h"
 #include "llvm/Transforms/IPO/SampleProfileProbe.h"
 #include "llvm/Transforms/IPO/SyntheticCountsPropagation.h"
 #include "llvm/Transforms/IPO/WholeProgramDevirt.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
static cl::opt<bool>
     EnablePGOInlineDeferral("enable-npm-pgo-inline-deferral", cl::init(true),
                             cl::Hidden,
                             cl::desc("Enable inline deferral during PGO"));
 
 static cl::opt<bool> EnableMemProfiler("enable-mem-prof", cl::init(false),
                                        cl::Hidden, cl::ZeroOrMore,
                                        cl::desc("Enable memory profiler"));
 
+static cl::opt<bool> EnableModuleInliner("enable-module-inliner",
+                                         cl::init(false), cl::Hidden,
+                                         cl::desc("Enable module inliner"));
+
 static cl::opt<bool> PerformMandatoryInliningsFirst(
     "mandatory-inlining-first", cl::init(true), cl::Hidden, cl::ZeroOrMore,
     cl::desc("Perform mandatory inlinings module-wide, before performing "
              "inlining."));
 
 static cl::opt<bool> EnableO3NonTrivialUnswitching(
     "enable-npm-O3-nontrivial-unswitch", cl::init(true), cl::Hidden,
     cl::ZeroOrMore, cl::desc("Enable non-trivial loop unswitching for -O3"));
PassBuilder::buildInlinerPipeline(OptimizationLevel Level,
   InlineParams IP = getInlineParamsFromOptLevel(Level);
   if (Phase == ThinOrFullLTOPhase::ThinLTOPreLink && PGOOpt &&
       PGOOpt->Action == PGOOptions::SampleUse)
     IP.HotCallSiteThreshold = 0;
 
   if (PGOOpt)
     IP.EnableDeferral = EnablePGOInlineDeferral;
 
   ModuleInlinerWrapperPass MIWP(IP, PerformMandatoryInliningsFirst,
                                 UseInlineAdvisor, MaxDevirtIterations);
 
   // Require the GlobalsAA analysis for the module so we can query it within
   // the CGSCC pipeline.
   MIWP.addModulePass(RequireAnalysisPass<GlobalsAA, Module>());
   // Invalidate AAManager so it can be recreated and pick up the newly available
   // GlobalsAA.
   MIWP.addModulePass(
       createModuleToFunctionPassAdaptor(InvalidateAnalysisPass<AAManager>()));
MainCGPipeline.addPass(createCGSCCToFunctionPassAdaptor(
       buildFunctionSimplificationPipeline(Level, Phase),
       PTO.EagerlyInvalidateAnalyses));
 
   MainCGPipeline.addPass(CoroSplitPass(Level != OptimizationLevel::O0));
 
   return MIWP;
 }
 
+ModuleInlinerPass
+PassBuilder::buildModuleInlinerPipeline(OptimizationLevel Level,
+                                        ThinOrFullLTOPhase Phase) {
+  InlineParams IP = getInlineParamsFromOptLevel(Level);
+  if (Phase == ThinOrFullLTOPhase::ThinLTOPreLink && PGOOpt &&
+      PGOOpt->Action == PGOOptions::SampleUse)
+    IP.HotCallSiteThreshold = 0;
+
+  if (PGOOpt)
+    IP.EnableDeferral = EnablePGOInlineDeferral;
+
+  // The inline deferral logic is used to avoid losing some
+  // inlining chance in future. It is helpful in SCC inliner, in which
+  // inlining is processed in bottom-up order.
+  // While in module inliner, the inlining order is a priority-based order
+  // by default. The inline deferral is unnecessary there. So we disable the
+  // inline deferral logic in module inliner.
+  IP.EnableDeferral = false;
+
+  return ModuleInlinerPass(IP, UseInlineAdvisor);
+}
+
 ModulePassManager
 PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
                                                ThinOrFullLTOPhase Phase) {
   ModulePassManager MPM;
 
   // Place pseudo probe instrumentation as the first pass of the pipeline to
   // minimize the impact of optimization changes.
   if (PGOOpt && PGOOpt->PseudoProbeForProfiling &&
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
   if (PGOOpt && Phase != ThinOrFullLTOPhase::ThinLTOPostLink &&
       PGOOpt->CSAction == PGOOptions::CSIRInstr)
     MPM.addPass(PGOInstrumentationGenCreateVar(PGOOpt->CSProfileGenFile));
 
   // Synthesize function entry counts for non-PGO compilation.
   if (EnableSyntheticCounts && !PGOOpt)
     MPM.addPass(SyntheticCountsPropagation());
 
+  if (EnableModuleInliner)
+    MPM.addPass(buildModuleInlinerPipeline(Level, Phase));
+  else
     MPM.addPass(buildInlinerPipeline(Level, Phase));
 
   if (EnableMemProfiler && Phase != ThinOrFullLTOPhase::ThinLTOPreLink) {
     MPM.addPass(createModuleToFunctionPassAdaptor(MemProfilerPass()));
     MPM.addPass(ModuleMemProfilerPass());
   }
 
   return MPM;
 }
 
 /// TODO: Should LTO cause any differences to this set of passes?
 void PassBuilder::addVectorPasses(OptimizationLevel Level,
                                   FunctionPassManager &FPM, bool IsFullLTO) {
   FPM.addPass(LoopVectorizePass(
       LoopVectorizeOptions(!PTO.LoopInterleaving, !PTO.LoopVectorization)));
 
   if (IsFullLTO) {
     // The vectorizer may have significantly shortened a loop body; unroll

llvm/lib/Passes/PassRegistry.def

 MODULE_PASS("strip-debug-declare", StripDebugDeclarePass())
 MODULE_PASS("strip-nondebug", StripNonDebugSymbolsPass())
 MODULE_PASS("strip-nonlinetable-debuginfo", StripNonLineTableDebugInfoPass())
 MODULE_PASS("synthetic-counts-propagation", SyntheticCountsPropagation())
 MODULE_PASS("verify", VerifierPass())
 MODULE_PASS("wholeprogramdevirt", WholeProgramDevirtPass())
 MODULE_PASS("dfsan", DataFlowSanitizerPass())
 MODULE_PASS("msan-module", ModuleMemorySanitizerPass({}))
+MODULE_PASS("module-inline", ModuleInlinerPass())
 MODULE_PASS("tsan-module", ModuleThreadSanitizerPass())
 MODULE_PASS("sancov-module", ModuleSanitizerCoveragePass())
 MODULE_PASS("memprof-module", ModuleMemProfilerPass())
 MODULE_PASS("poison-checking", PoisonCheckingPass())
 MODULE_PASS("pseudo-probe-update", PseudoProbeUpdatePass())
 #undef MODULE_PASS
 
 #ifndef MODULE_PASS_WITH_PARAMS

llvm/lib/Transforms/IPO/CMakeLists.txt

add_llvm_component_library(LLVMipo
   IROutliner.cpp
   InferFunctionAttrs.cpp
   InlineSimple.cpp
   Inliner.cpp
   Internalize.cpp
   LoopExtractor.cpp
   LowerTypeTests.cpp
   MergeFunctions.cpp
+  ModuleInliner.cpp
   OpenMPOpt.cpp
   PartialInlining.cpp
   PassManagerBuilder.cpp
   PruneEH.cpp
   SampleContextTracker.cpp
   SampleProfile.cpp
   SampleProfileProbe.cpp
   SCCP.cpp

llvm/lib/Transforms/IPO/ModuleInliner.cpp

+//===- ModuleInliner.cpp - Code related to module inliner -----------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the mechanics required to implement inlining without
+// missing any calls in the module level. It doesn't need any infromation about
+// SCC or call graph, which is different from the SCC inliner.  The decisions of
+// which calls are profitable to inline are implemented elsewhere.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO/ModuleInliner.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/ScopeExit.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/GlobalsModRef.h"
+#include "llvm/Analysis/InlineAdvisor.h"
+#include "llvm/Analysis/InlineCost.h"
+#include "llvm/Analysis/InlineOrder.h"
+#include "llvm/Analysis/OptimizationRemarkEmitter.h"
+#include "llvm/Analysis/ProfileSummaryInfo.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/DebugLoc.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Metadata.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/IR/User.h"
+#include "llvm/IR/Value.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/CallPromotionUtils.h"
+#include "llvm/Transforms/Utils/Cloning.h"
+#include "llvm/Transforms/Utils/Local.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
+#include <cassert>
+#include <functional>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "module-inline"
+
+STATISTIC(NumInlined, "Number of functions inlined");
+STATISTIC(NumDeleted, "Number of functions deleted because all callers found");
+
+static cl::opt<bool> InlineEnablePriorityOrder(
+    "module-inline-enable-priority-order", cl::Hidden, cl::init(true),
+    cl::desc("Enable the priority inline order for the module inliner"));
+
+/// Return true if the specified inline history ID
+/// indicates an inline history that includes the specified function.
+static bool inlineHistoryIncludes(
+    Function *F, int InlineHistoryID,
+    const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
+  while (InlineHistoryID != -1) {
+    assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
+           "Invalid inline history ID");
+    if (InlineHistory[InlineHistoryID].first == F)
+      return true;
+    InlineHistoryID = InlineHistory[InlineHistoryID].second;
+  }
+  return false;
+}
+
+InlineAdvisor &ModuleInlinerPass::getAdvisor(const ModuleAnalysisManager &MAM,
+                                             FunctionAnalysisManager &FAM,
+                                             Module &M) {
+  if (OwnedAdvisor)
+    return *OwnedAdvisor;
+
+  auto *IAA = MAM.getCachedResult<InlineAdvisorAnalysis>(M);
+  if (!IAA) {
+    // It should still be possible to run the inliner as a stand-alone module
+    // pass, for test scenarios. In that case, we default to the
+    // DefaultInlineAdvisor, which doesn't need to keep state between module
+    // pass runs. It also uses just the default InlineParams. In this case, we
+    // need to use the provided FAM, which is valid for the duration of the
+    // inliner pass, and thus the lifetime of the owned advisor. The one we
+    // would get from the MAM can be invalidated as a result of the inliner's
+    // activity.
+    OwnedAdvisor = std::make_unique<DefaultInlineAdvisor>(M, FAM, Params);
+
+    return *OwnedAdvisor;
+  }
+  assert(IAA->getAdvisor() &&
+         "Expected a present InlineAdvisorAnalysis also have an "
+         "InlineAdvisor initialized");
+  return *IAA->getAdvisor();
+}
+
+static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {
+  LibFunc LF;
+
+  // Either this is a normal library function or a "vectorizable"
+  // function.  Not using the VFDatabase here because this query
+  // is related only to libraries handled via the TLI.
+  return TLI.getLibFunc(F, LF) ||
+         TLI.isKnownVectorFunctionInLibrary(F.getName());
+}
+
+PreservedAnalyses ModuleInlinerPass::run(Module &M,
+                                         ModuleAnalysisManager &MAM) {
+  LLVM_DEBUG(dbgs() << "---- Module Inliner is Running ---- \n");
+
+  auto &IAA = MAM.getResult<InlineAdvisorAnalysis>(M);
+  if (!IAA.tryCreate(Params, Mode, {})) {
+    M.getContext().emitError(
+        "Could not setup Inlining Advisor for the requested "
+        "mode and/or options");
+    return PreservedAnalyses::all();
+  }
+
+  bool Changed = false;
+
+  ProfileSummaryInfo *PSI = MAM.getCachedResult<ProfileSummaryAnalysis>(M);
+
+  FunctionAnalysisManager &FAM =
+      MAM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
+
+  auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
+    return FAM.getResult<TargetLibraryAnalysis>(F);
+  };
+
+  InlineAdvisor &Advisor = getAdvisor(MAM, FAM, M);
+  Advisor.onPassEntry();
+
+  auto AdvisorOnExit = make_scope_exit([&] { Advisor.onPassExit(); });
+
+  // In the module inliner, a priority-based worklist is used for calls across
+  // the entire Module. With this module inliner, the inline order is not
+  // limited to bottom-up order. More globally scope inline order is enabled.
+  // Also, the inline deferral logic become unnecessary in this module inliner.
+  // It is possible to use other priority heuristics, e.g. profile-based
+  // heuristic.
+  //
+  // TODO: Here is a huge amount duplicate code between the module inliner and
+  // the SCC inliner, which need some refactoring.
+  std::unique_ptr<InlineOrder<std::pair<CallBase *, int>>> Calls;
+  if (InlineEnablePriorityOrder)
+    Calls = std::make_unique<PriorityInlineOrder<InlineSizePriority>>();
+  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 module.
+  for (Function &F : M) {
+    auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
+    // 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(F))
+      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();
+
+  // 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();
+
+    LLVM_DEBUG(dbgs() << "Inlining calls in: " << F.getName() << "\n"
+                      << "    Function size: " << F.getInstructionCount()
+                      << "\n");
+
+    auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
+      return FAM.getResult<AssumptionAnalysis>(F);
+    };
+
+    // Now process as many calls as we have within this caller in the sequence.
+    // We bail out as soon as the caller has to change so we can
+    // prepare the context of that new caller.
+    bool DidInline = false;
+    while (!Calls->empty() && Calls->front().first->getCaller() == &F) {
+      auto P = Calls->pop();
+      CallBase *CB = P.first;
+      const int InlineHistoryID = P.second;
+      Function &Callee = *CB->getCalledFunction();
+
+      if (InlineHistoryID != -1 &&
+          inlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory)) {
+        setInlineRemark(*CB, "recursive");
+        continue;
+      }
+
+      auto Advice = Advisor.getAdvice(*CB, /*OnlyMandatory*/ false);
+      // Check whether we want to inline this callsite.
+      if (!Advice->isInliningRecommended()) {
+        Advice->recordUnattemptedInlining();
+        continue;
+      }
+
+      // Setup the data structure used to plumb customization into the
+      // `InlineFunction` routine.
+      InlineFunctionInfo IFI(
+          /*cg=*/nullptr, GetAssumptionCache, PSI,
+          &FAM.getResult<BlockFrequencyAnalysis>(*(CB->getCaller())),
+          &FAM.getResult<BlockFrequencyAnalysis>(Callee));
+
+      InlineResult IR =
+          InlineFunction(*CB, IFI, &FAM.getResult<AAManager>(*CB->getCaller()));
+      if (!IR.isSuccess()) {
+        Advice->recordUnsuccessfulInlining(IR);
+        continue;
+      }
+
+      DidInline = true;
+      InlinedCallees.insert(&Callee);
+      ++NumInlined;
+
+      LLVM_DEBUG(dbgs() << "    Size after inlining: "
+                        << F.getInstructionCount() << "\n");
+
+      // Add any new callsites to defined functions to the worklist.
+      if (!IFI.InlinedCallSites.empty()) {
+        int NewHistoryID = InlineHistory.size();
+        InlineHistory.push_back({&Callee, InlineHistoryID});
+
+        for (CallBase *ICB : reverse(IFI.InlinedCallSites)) {
+          Function *NewCallee = ICB->getCalledFunction();
+          if (!NewCallee) {
+            // Try to promote an indirect (virtual) call without waiting for
+            // the post-inline cleanup and the next DevirtSCCRepeatedPass
+            // iteration because the next iteration may not happen and we may
+            // miss inlining it.
+            if (tryPromoteCall(*ICB))
+              NewCallee = ICB->getCalledFunction();
+          }
+          if (NewCallee)
+            if (!NewCallee->isDeclaration())
+              Calls->push({ICB, NewHistoryID});
+        }
+      }
+
+      // Merge the attributes based on the inlining.
+      AttributeFuncs::mergeAttributesForInlining(F, Callee);
+
+      // For local functions, check whether this makes the callee trivially
+      // dead. In that case, we can drop the body of the function eagerly
+      // which may reduce the number of callers of other functions to one,
+      // changing inline cost thresholds.
+      bool CalleeWasDeleted = false;
+      if (Callee.hasLocalLinkage()) {
+        // To check this we also need to nuke any dead constant uses (perhaps
+        // made dead by this operation on other functions).
+        Callee.removeDeadConstantUsers();
+        // if (Callee.use_empty() && !CG.isLibFunction(Callee)) {
+        if (Callee.use_empty() && !isKnownLibFunction(Callee, GetTLI(Callee))) {
+          Calls->erase_if([&](const std::pair<CallBase *, int> &Call) {
+            return Call.first->getCaller() == &Callee;
+          });
+          // Clear the body and queue the function itself for deletion when we
+          // finish inlining.
+          // Note that after this point, it is an error to do anything other
+          // than use the callee's address or delete it.
+          Callee.dropAllReferences();
+          assert(!is_contained(DeadFunctions, &Callee) &&
+                 "Cannot put cause a function to become dead twice!");
+          DeadFunctions.push_back(&Callee);
+          CalleeWasDeleted = true;
+        }
+      }
+      if (CalleeWasDeleted)
+        Advice->recordInliningWithCalleeDeleted();
+      else
+        Advice->recordInlining();
+    }
+
+    if (!DidInline)
+      continue;
+    Changed = true;
+
+    InlinedCallees.clear();
+  }
+
+  // Now that we've finished inlining all of the calls across this module,
+  // delete all of the trivially dead functions.
+  //
+  // 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.
+  for (Function *DeadF : DeadFunctions) {
+    // Clear out any cached analyses.
+    FAM.clear(*DeadF, DeadF->getName());
+
+    // And delete the actual function from the module.
+    // The Advisor may use Function pointers to efficiently index various
+    // internal maps, e.g. for memoization. Function cleanup passes like
+    // argument promotion create new functions. It is possible for a new
+    // function to be allocated at the address of a deleted function. We could
+    // index using names, but that's inefficient. Alternatively, we let the
+    // Advisor free the functions when it sees fit.
+    DeadF->getBasicBlockList().clear();
+    M.getFunctionList().remove(DeadF);
+
+    ++NumDeleted;
+  }
+
+  if (!Changed)
+    return PreservedAnalyses::all();
+
+  return PreservedAnalyses::none();
+}

llvm/test/Transforms/Inline/callbr.ll

 ; RUN: opt -inline -S < %s | FileCheck %s
 ; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck %s
+; RUN: opt -passes='module-inline' -S < %s | FileCheck %s
 
 define dso_local i32 @main() #0 {
   %1 = alloca i32, align 4
   store i32 0, i32* %1, align 4
   %2 = call i32 @t32(i32 0)
   ret i32 %2
 }
 

llvm/test/Transforms/Inline/casts.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt < %s -passes='module-inline' -S | FileCheck %s
 
 define i32 @testByte(i8 %X) {
 entry:
   %tmp = icmp ne i8 %X, 0
   %tmp.i = zext i1 %tmp to i32
   ret i32 %tmp.i
 }
 
 define i32 @main() {
 ; CHECK-LABEL: define i32 @main()
 entry:
   %rslt = call i32 @testByte(i8 123)
 ; CHECK-NOT: call
   ret i32 %rslt
 ; CHECK: ret i32 1
 }

llvm/test/Transforms/Inline/comdat-ipo.ll

 ; RUN: opt -inline -S < %s | FileCheck %s
 ; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck %s
+; RUN: opt -passes='module-inline' -S < %s | FileCheck %s
 
 define i32 @caller() {
 ; CHECK-LABEL: @caller(
 ; CHECK-NEXT:  %val2 = call i32 @linkonce_callee(i32 42)
 ; CHECK-NEXT:  ret i32 %val2
 
   %val = call i32 @odr_callee()
   %val2 = call i32 @linkonce_callee(i32 %val);

llvm/test/Transforms/Inline/crash-lifetime-marker.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt < %s -passes='module-inline' -S | FileCheck %s
 
 ; InlineFunction would assert inside the loop that leaves lifetime markers if
 ; there was an zero-sized AllocaInst. Check that it doesn't assert and doesn't
 ; leave lifetime markers in that case.
 
 declare i32 @callee2(i8*)
 
 define i32 @callee1(i32 %count) {

llvm/test/Transforms/Inline/frameescape.ll

 ; RUN: opt -inline -S < %s | FileCheck %s
 ; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck %s
+; RUN: opt -passes='module-inline' -S < %s | FileCheck %s
 
 ; PR23216: We can't inline functions using llvm.localescape.
 
 declare void @llvm.localescape(...)
 declare i8* @llvm.frameaddress(i32)
 declare i8* @llvm.localrecover(i8*, i8*, i32)
 
 define internal void @foo(i8* %fp) {

llvm/test/Transforms/Inline/inline-assume.ll

 ; RUN: opt -inline -S -o - < %s | FileCheck %s
 ; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck %s
+; RUN: opt -passes='module-inline' -S < %s | FileCheck %s
 
 %0 = type opaque
 %struct.Foo = type { i32, %0* }
 
 ; Test that we don't crash when inlining @bar (rdar://22521387).
 define void @foo(%struct.Foo* align 4 %a) {
 entry:
   call fastcc void @bar(%struct.Foo* nonnull align 4 undef)

llvm/test/Transforms/Inline/inline-constexpr-addrspacecast-argument.ll

 ; RUN: opt -S -inline < %s | FileCheck %s
 ; RUN: opt -S -passes='cgscc(inline)' < %s | FileCheck %s
+; RUN: opt -S -passes='module-inline' < %s | FileCheck %s
 
 target datalayout = "e-p3:32:32-p4:64:64-n32"
 
 @lds = internal addrspace(3) global [64 x i64] zeroinitializer
 
 ; CHECK-LABEL: @constexpr_addrspacecast_ptr_size_change(
 ; CHECK: load i64, i64 addrspace(4)* addrspacecast (i64 addrspace(3)* getelementptr inbounds ([64 x i64], [64 x i64] addrspace(3)* @lds, i32 0, i32 0) to i64 addrspace(4)*)
 ; CHECK-NEXT: br

llvm/test/Transforms/Inline/inline-fast-math-flags.ll

 ; RUN: opt < %s -S -inline -inline-threshold=20 | FileCheck %s
 ; RUN: opt < %s -S -passes='cgscc(inline)' -inline-threshold=20 | FileCheck %s
+; RUN: opt < %s -S -passes='module-inline' -inline-threshold=20 | FileCheck %s
 ; Check that we don't drop FastMathFlag when estimating inlining profitability.
 ;
 ; In this test we should inline 'foo'  to 'boo', because it'll fold to a
 ; constant.
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 define float @foo(float* %a, float %b) {

llvm/test/Transforms/Inline/inline-vla.ll

 ; RUN: opt -S -inline %s -o - | FileCheck %s
 ; RUN: opt -S -passes='cgscc(inline)' %s -o - | FileCheck %s
+; RUN: opt -S -passes='module-inline' %s -o - | FileCheck %s
 
 ; Check that memcpy2 is completely inlined away.
 ; CHECK-NOT: memcpy2
 
 @.str = private unnamed_addr constant [2 x i8] c"a\00", align 1
 @.str1 = private unnamed_addr constant [3 x i8] c"ab\00", align 1
 
 ; Function Attrs: nounwind ssp uwtable

llvm/test/Transforms/Inline/invoke-cleanup.ll

 ; RUN: opt %s -inline -S | FileCheck %s
 ; RUN: opt %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt %s -passes='module-inline' -S | FileCheck %s
 
 declare void @external_func()
 
 @exception_type1 = external global i8
 @exception_type2 = external global i8
 
 
 define internal void @inner() personality i8* null {

llvm/test/Transforms/Inline/invoke-combine-clauses.ll

 ; RUN: opt %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt %s -passes='module-inline' -S | FileCheck %s
 
 declare void @external_func()
 declare void @abort()
 
 @exception_inner = external global i8
 @exception_outer = external global i8
 @condition = external global i1
 

llvm/test/Transforms/Inline/invoke_test-1.ll

 ; Test that we can inline a simple function, turning the calls in it into invoke
 ; instructions
 
 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt < %s -passes='module-inline' -S | FileCheck %s
 
 declare void @might_throw()
 
 define internal void @callee() {
 entry:
   call void @might_throw()
   ret void
 }

llvm/test/Transforms/Inline/invoke_test-3.ll

 ; Test that any rethrown exceptions in an inlined function are automatically
 ; turned into branches to the invoke destination.
 
 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt < %s -passes='module-inline' -S | FileCheck %s
 
 declare void @might_throw()
 
 define internal i32 @callee() personality i32 (...)* @__gxx_personality_v0 {
 entry:
   invoke void @might_throw()
       to label %cont unwind label %exc
 

llvm/test/Transforms/Inline/nested-inline.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt < %s -passes='module-inline' -S | FileCheck %s
 ; Test that bar and bar2 are both inlined throughout and removed.
 @A = weak global i32 0    ; <i32*> [#uses=1]
 @B = weak global i32 0    ; <i32*> [#uses=1]
 @C = weak global i32 0    ; <i32*> [#uses=1]
 
 define fastcc void @foo(i32 %X) {
 entry:
 ; CHECK-LABEL: @foo(

llvm/test/Transforms/Inline/nonnull.ll

 ; RUN: opt -S -inline %s | FileCheck %s
 ; RUN: opt -S -passes='cgscc(inline)' %s | FileCheck %s
+; RUN: opt -S -passes='module-inline' %s | FileCheck %s
 
 declare void @foo()
 declare void @bar()
 
 define void @callee(i8* %arg) {
   %cmp = icmp eq i8* %arg, null
   br i1 %cmp, label %expensive, label %done
 

llvm/test/Transforms/Inline/pr21206.ll

 ; RUN: opt < %s -inline -S | FileCheck %s
 ; RUN: opt < %s -passes='cgscc(inline)' -S | FileCheck %s
+; RUN: opt < %s -passes='module-inline' -S | FileCheck %s
 
 $c = comdat any
 ; CHECK: $c = comdat any
 
 define linkonce_odr void @foo() comdat($c) {
   ret void
 }
 ; CHECK: define linkonce_odr void @foo() comdat($c)