Rework the LTO Pipeline, aligning closer to the O2/O3 pipeline.

[mehdi_amini]

Summary

It seems that the LTO pipeline didn't receive as much attention as the
regular O2/O3 pipeline the last few years. This patch attempts to
refactor the pass pipeline initialization to align LTO with the
regular pipeline.

The proposed change exit the compile phase before the inliner is ran
during the compile phase. The link phase will run the usuall pipeline,
extended with some specific passes that leverage the augmented
knowledge we have from full program visibility.

The LTO addition over the regular pipeline consists mainly of re-doing
the peephole a second after the inliner is done, but prepended with a
run of GlobalDCE/GlobalOpt.

The measurement on the public test suite as well as on our internal
suite show an overall net improvement. With some regression that I
am still tracking. Consider this patch as a work in progress that I
submit now for feedback.

[mehdi_amini]

Minor update, moving EliminateAvailableExternallyPass before GlobalOpt

[tejohnson]

lib/Transforms/IPO/PassManagerBuilder.cpp

329

Why not perform the first round of inlining and some of the other optimizations (like the peepholes) called below when preparing for LTO? I would think this would result in smaller intermediate .o bitcode sizes and more efficient LTO.

[mehdi_amini]

I'm not sure why inlining should be able to end up with smaller files, except in the case where an "internal linkage" function can end up with no call site. Do you see any other cases?

The inliner may take different decisions with more of the call graph available. Assuming the inliner heuristics are well tuned, running on a partial call-graph shouldn't result in better results but on the opposite only limits the freedom of it during LTO.

If your only concern is about compile time, it is fairly easy to test and I can launch a run of our compile-time test-suite.

[mehdi_amini]

Teresa (and other), can you run this on your internal benchmark suite to see the performance impact?

[tejohnson]

Unfortunately, we haven't had a lot of success running LTO on our
internal benchmarks in the past due to the scaling issue.

That's great it is giving you better performance - I was just
surprised that it was beneficial to skip all of those downstream
optimizations in the initial compile step. Is the better performance
coming from skipping the initial inline? Is there no benefit to doing
the peepholes etc in the initial compile?

[mehdi_amini]

Right now my view of it is that if I get a performance improvement by running two times the inliner and the "peephole" passes, then it is a bug. If it is not a bug it means that the O3 pipeline is affected as well and we might run it two times there as well. Does it make sense?

I ran the LLVM benchmark suite + some internals with a return before and after the inliner+peephole phase. Stopping before the inliner during the compile phase ends up with 13 regressions and 20 improvements, compared to running the inliner during the compile phase. I sent you some more details by email.

[tejohnson]

Hi Mehdi,

Thanks for sharing the results. As you note there are swings in both
directions, but the improvements outweigh the regressions.

[tejohnson]

include/llvm/Transforms/IPO/PassManagerBuilder.h

154

Can this be removed? I think it is dead code now.

lib/Transforms/IPO/PassManagerBuilder.cpp

599

This can be removed - it only needs to be called once and now the LTO pipeline calls it via addLTOOptimizationPasses.

[mehdi_amini]

include/llvm/Transforms/IPO/PassManagerBuilder.h

154

Yes, the patch is not ready for review. I posted it for feedback on the approach as a work in progress, and hoping you (google) and others may have other benchmarks to run.

[mehdi_amini]

Rebase

include/llvm/Transforms/IPO/PassManagerBuilder.h

public:
   bool LoopVectorize;
   bool RerollLoops;
   bool LoadCombine;
   bool DisableGVNLoadPRE;
   bool VerifyInput;
   bool VerifyOutput;
   bool MergeFunctions;
   bool PrepareForLTO;
+  bool PerformLTO;
 
 private:
   /// ExtensionList - This is list of all of the extensions that are registered.
   std::vector<std::pair<ExtensionPointTy, ExtensionFn> > Extensions;
 
 public:
   PassManagerBuilder();
   ~PassManagerBuilder();
   /// Adds an extension that will be used by all PassManagerBuilder instances.
   /// This is intended to be used by plugins, to register a set of
   /// optimisations to run automatically.
   static void addGlobalExtension(ExtensionPointTy Ty, ExtensionFn Fn);
   void addExtension(ExtensionPointTy Ty, ExtensionFn Fn);
 
 private:
   void addExtensionsToPM(ExtensionPointTy ETy,
                          legacy::PassManagerBase &PM) const;
   void addInitialAliasAnalysisPasses(legacy::PassManagerBase &PM) const;
   void addLTOOptimizationPasses(legacy::PassManagerBase &PM);
   void addLateLTOOptimizationPasses(legacy::PassManagerBase &PM);
+  void addPeepholePasses(legacy::PassManagerBase &MPM);
 
 public:
   /// populateFunctionPassManager - This fills in the function pass manager,
   /// which is expected to be run on each function immediately as it is
   /// generated.  The idea is to reduce the size of the IR in memory.
   void populateFunctionPassManager(legacy::FunctionPassManager &FPM);
 
   /// populateModulePassManager - This sets up the primary pass manager.

lib/Transforms/IPO/PassManagerBuilder.cpp

PassManagerBuilder::PassManagerBuilder() {
     LoopVectorize = RunLoopVectorization;
     RerollLoops = RunLoopRerolling;
     LoadCombine = RunLoadCombine;
     DisableGVNLoadPRE = false;
     VerifyInput = false;
     VerifyOutput = false;
     MergeFunctions = false;
     PrepareForLTO = false;
+    PerformLTO = false;
 }
 
 PassManagerBuilder::~PassManagerBuilder() {
   delete LibraryInfo;
   delete Inliner;
 }
 
 /// Set of global extensions, automatically added as part of the standard set.
void PassManagerBuilder::populateFunctionPassManager(
   if (UseNewSROA)
     FPM.add(createSROAPass());
   else
     FPM.add(createScalarReplAggregatesPass());
   FPM.add(createEarlyCSEPass());
   FPM.add(createLowerExpectIntrinsicPass());
 }
 
-void PassManagerBuilder::populateModulePassManager(
-    legacy::PassManagerBase &MPM) {
-  // If all optimizations are disabled, just run the always-inline pass and,
-  // if enabled, the function merging pass.
-  if (OptLevel == 0) {
-    if (Inliner) {
-      MPM.add(Inliner);
-      Inliner = nullptr;
-    }
-
-    // FIXME: The BarrierNoopPass is a HACK! The inliner pass above implicitly
-    // creates a CGSCC pass manager, but we don't want to add extensions into
-    // that pass manager. To prevent this we insert a no-op module pass to reset
-    // the pass manager to get the same behavior as EP_OptimizerLast in non-O0
-    // builds. The function merging pass is 
-    if (MergeFunctions)
-      MPM.add(createMergeFunctionsPass());
-    else if (!GlobalExtensions->empty() || !Extensions.empty())
-      MPM.add(createBarrierNoopPass());
-
-    addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
-    return;
-  }
-
-  // Add LibraryInfo if we have some.
-  if (LibraryInfo)
-    MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
-
-  addInitialAliasAnalysisPasses(MPM);
-
-  if (!DisableUnitAtATime) {
-    addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
-
-    MPM.add(createIPSCCPPass());              // IP SCCP
-    MPM.add(createGlobalOptimizerPass());     // Optimize out global vars
-
-    MPM.add(createDeadArgEliminationPass());  // Dead argument elimination
-
-    MPM.add(createInstructionCombiningPass());// Clean up after IPCP & DAE
-    addExtensionsToPM(EP_Peephole, MPM);
-    MPM.add(createCFGSimplificationPass());   // Clean up after IPCP & DAE
-  }
-
-  if (EnableNonLTOGlobalsModRef)
-    // We add a module alias analysis pass here. In part due to bugs in the
-    // analysis infrastructure this "works" in that the analysis stays alive
-    // for the entire SCC pass run below.
-    MPM.add(createGlobalsAAWrapperPass());
-
-  // Start of CallGraph SCC passes.
-  if (!DisableUnitAtATime)
-    MPM.add(createPruneEHPass());             // Remove dead EH info
-  if (Inliner) {
-    MPM.add(Inliner);
-    Inliner = nullptr;
-  }
-  if (!DisableUnitAtATime)
-    MPM.add(createFunctionAttrsPass());       // Set readonly/readnone attrs
-  if (OptLevel > 2)
-    MPM.add(createArgumentPromotionPass());   // Scalarize uninlined fn args
+void PassManagerBuilder::addPeepholePasses(legacy::PassManagerBase &MPM) {
 
   // Start of function pass.
   // Break up aggregate allocas, using SSAUpdater.
   if (UseNewSROA)
     MPM.add(createSROAPass());
   else
     MPM.add(createScalarReplAggregatesPass(-1, false));
   MPM.add(createEarlyCSEPass());              // Catch trivial redundancies
void PassManagerBuilder::addPeepholePasses(legacy::PassManagerBase &MPM) {
 
   if (LoadCombine)
     MPM.add(createLoadCombinePass());
 
   MPM.add(createAggressiveDCEPass());         // Delete dead instructions
   MPM.add(createCFGSimplificationPass()); // Merge & remove BBs
   MPM.add(createInstructionCombiningPass());  // Clean up after everything.
   addExtensionsToPM(EP_Peephole, MPM);
+}
+
+void PassManagerBuilder::populateModulePassManager(
+    legacy::PassManagerBase &MPM) {
+  // If all optimizations are disabled, just run the always-inline pass and,
+  // if enabled, the function merging pass.
+  if (OptLevel == 0) {
+    if (Inliner) {
+      MPM.add(Inliner);
+      Inliner = nullptr;
+    }
+
+    // FIXME: The BarrierNoopPass is a HACK! The inliner pass above implicitly
+    // creates a CGSCC pass manager, but we don't want to add extensions into
+    // that pass manager. To prevent this we insert a no-op module pass to reset
+    // the pass manager to get the same behavior as EP_OptimizerLast in non-O0
+    // builds. The function merging pass is
+    if (MergeFunctions)
+      MPM.add(createMergeFunctionsPass());
+    else if (!GlobalExtensions->empty() || !Extensions.empty())
+      MPM.add(createBarrierNoopPass());
+
+    addExtensionsToPM(EP_EnabledOnOptLevel0, MPM);
+    return;
+  }
+
+  // Add LibraryInfo if we have some.
+  if (LibraryInfo)
+    MPM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
+
+  addInitialAliasAnalysisPasses(MPM);
+
+  if (!DisableUnitAtATime) {
+    addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
+
+    MPM.add(createIPSCCPPass());          // IP SCCP
+    MPM.add(createGlobalOptimizerPass()); // Optimize out global vars
+
+    if (PerformLTO)
+      // Linking modules together can lead to duplicated global constants, only
+      // keep one copy of each constant.
+      MPM.add(createConstantMergePass());
+
+    MPM.add(createDeadArgEliminationPass()); // Dead argument elimination
+
+    MPM.add(createInstructionCombiningPass()); // Clean up after IPCP & DAE
+    addExtensionsToPM(EP_Peephole, MPM);
+    MPM.add(createCFGSimplificationPass()); // Clean up after IPCP & DAE
+  }
+
+  // If we are planning to perform LTO later, let's not bloat the code with
+  // unrolling/vectorization/... now. We'll run the inliner + CGSCC passes
+  // during LTO and performs the rest of the optimizations afterward.
+  if (PrepareForLTO)
+    return;
+
+  if (EnableNonLTOGlobalsModRef)
+    // We add a module alias analysis pass here. In part due to bugs in the
+    // analysis infrastructure this "works" in that the analysis stays alive
+    // for the entire SCC pass run below.
+    MPM.add(createGlobalsAAWrapperPass());
+
+  // Start of CallGraph SCC passes.
+  if (PerformLTO || !DisableUnitAtATime)
+    MPM.add(createPruneEHPass()); // Remove dead EH info
+  if (Inliner) {
+    MPM.add(Inliner);
+    Inliner = nullptr;
+  }
+  if (!DisableUnitAtATime)
+    MPM.add(createFunctionAttrsPass()); // Set readonly/readnone attrs
+  if (PerformLTO || OptLevel > 2)
+    MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args
+
+  addPeepholePasses(MPM);
 
   // FIXME: This is a HACK! The inliner pass above implicitly creates a CGSCC
   // pass manager that we are specifically trying to avoid. To prevent this
   // we must insert a no-op module pass to reset the pass manager.
   MPM.add(createBarrierNoopPass());
 
-  if (!DisableUnitAtATime && OptLevel > 1 && !PrepareForLTO) {
-    // Remove avail extern fns and globals definitions if we aren't
-    // compiling an object file for later LTO. For LTO we want to preserve
-    // these so they are eligible for inlining at link-time. Note if they
-    // are unreferenced they will be removed by GlobalDCE later, so
-    // this only impacts referenced available externally globals.
-    // Eventually they will be suppressed during codegen, but eliminating
-    // here enables more opportunity for GlobalDCE as it may make
-    // globals referenced by available external functions dead
-    // and saves running remaining passes on the eliminated functions.
-    MPM.add(createEliminateAvailableExternallyPass());
+  // After the inliner we don't really need to keep these around
+
+  if (PerformLTO) {
+    // Remove dead fns and globals. Removing unreferenced functions could lead
+    // to more opportunities for globalopt
+    MPM.add(createGlobalDCEPass());
+    MPM.add(createGlobalOptimizerPass());
+    // Remove dead fns and globals after globalopt
+    MPM.add(createGlobalDCEPass());
+    addPeepholePasses(MPM);
   }
 
   if (EnableNonLTOGlobalsModRef)
     // We add a fresh GlobalsModRef run at this point. This is particularly
     // useful as the above will have inlined, DCE'ed, and function-attr
     // propagated everything. We should at this point have a reasonably minimal
     // and richly annotated call graph. By computing aliasing and mod/ref
     // information for all local globals here, the late loop passes and notably

 }
 
 void PassManagerBuilder::addLateLTOOptimizationPasses(
     legacy::PassManagerBase &PM) {
   // Delete basic blocks, which optimization passes may have killed.
   PM.add(createCFGSimplificationPass());
 
   // Drop bodies of available externally objects to improve GlobalDCE.
   PM.add(createEliminateAvailableExternallyPass());
 
   // Now that we have optimized the program, discard unreachable functions.
   PM.add(createGlobalDCEPass());
 
   // FIXME: this is profitable (for compiler time) to do at -O0 too, but
   // currently it damages debug info.
   if (MergeFunctions)
     PM.add(createMergeFunctionsPass());
 }
 
 void PassManagerBuilder::populateLTOPassManager(legacy::PassManagerBase &PM) {
-  if (LibraryInfo)
-    PM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
+  PerformLTO = true;
 
   if (VerifyInput)
     PM.add(createVerifierPass());
 
   if (OptLevel > 1)
-    addLTOOptimizationPasses(PM);
+    populateModulePassManager(PM);
 
   // Lower bit sets to globals. This pass supports Clang's control flow
   // integrity mechanisms (-fsanitize=cfi*) and needs to run at link time if CFI
   // is enabled. The pass does nothing if CFI is disabled.
   PM.add(createLowerBitSetsPass());
 
   if (OptLevel != 0)
     addLateLTOOptimizationPasses(PM);
 
   if (VerifyOutput)
     PM.add(createVerifierPass());
+  PerformLTO = false;
 }
 
 inline PassManagerBuilder *unwrap(LLVMPassManagerBuilderRef P) {
     return reinterpret_cast<PassManagerBuilder*>(P);
 }
 
 inline LLVMPassManagerBuilderRef wrap(PassManagerBuilder *P) {
   return reinterpret_cast<LLVMPassManagerBuilderRef>(P);