Define the ThinLTO Pipeline

[mehdi_amini]

Summary

On the contrary to Full LTO, ThinLTO can afford to shift compile time
from the frontend to the linker: both phases are parallel.
This pipeline is based on the proposal in D13443 for full LTO. We ]
didn't move forward on this proposal because the link was far too long
after that.

This patch refactor the "function simplification" passes that are part
of the inliner loop in a helper function (this part is NFC and can be
commited separately to simplify the diff). The ThinLTO pipeline
integrates in the regular O2/O3 flow:

• The compile phase perform the inliner with a somehow lighter function simplification. (TODO: tune the inliner thresholds here) This is intendend to simplify the IR and get rid of obvious things like linkonce_odr that will be inlined.
• The link phase will run the pipeline from the start, extended with some specific passes that leverage the augmented knowledge we have during LTO. Especially after the inliner is done, a sequence of globalDCE/globalOpt is performed, followed by another run of the "function simplification" passes.

The measurements on the public test suite as well as on our internal
suite show an overall net improvement. The binary size for the clang
executable is reduced by 5%. We're still tuning it with the bringup
of ThinLTO but this should provide a good starting point.

[mgrang]

lib/Transforms/IPO/PassManagerBuilder.cpp

362

Period required at the end of comment.

429

Period required at the end of comment.

432

Period required at the end of comment.

[mehdi_amini]

Upload a new diff rebased on top of the NFC changes to reduce the diff.

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

354–356

I can fix these comments as part of the NFC part of the changes (I updated the diff to rebase on the existing code after refactoring).
(I plan to commit separately and the comments are like that in trunk right now)

[davidxl]

lib/Transforms/IPO/PassManagerBuilder.cpp

366–369

This needs to be run in PrepareForThinLTO. During PerformThinLTO, only cross module indirect call promotion transformation needs to be done here.

[tejohnson]

lib/Transforms/IPO/PassManagerBuilder.cpp

366–369

Right, this should be guarded by (!PerformThinLTO).

I think the IC promotion pass is not yet committed. But eventually we will add another round of it just after FunctionImport.

393

typo: s/performs/perform/

710

Don't we also need to do some of the LTO passes here? E.g. FunctionImporting is added in addLTOOptimizationPasses.

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

366–369

Good point, I didn't pay much attention to PGO, I'll update.

710

Yes we can add it the same way it is done in the LTO pipeline, i.e. guarded by the presence of the FunctionIndex.

Right now I rather have the logic in the linker plugin and separate the import from the optimization. This is also required for the incremental scheme (see the beginning of ProcessThinLTOModule () in D17066).

[mehdi_amini]

Should take into account all the comments

[tejohnson]

lib/Transforms/IPO/PassManagerBuilder.cpp

710

Ok, for now I suppose you can just set the FunctionIndex to null before invoking this.

I haven't done a full comparison between the LTO pipeline and the new ThinLTO pipeline here, is there anything else done in the LTO pipeline that is worth adding to this, or is it all covered by the module passes? Looks like it from my quick scan but I didn't compare extensively...

Also, after this goes in clang should be changed to invoke this instead of populateLTOPassManager in EmitAssemblyHelper::CreatePasses when we have a function index. And I can change my gold threads patch for ThinLTO (D15390) to do the same for ThinLTO compiles.

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

710

I tend to be data driven, so we're looking at benchmarks and tracking issues right now, but this is a good starting point.

[tejohnson]

LGTM

[mehdi_amini]

r261029

include/llvm/Transforms/IPO/PassManagerBuilder.h

public:
   bool LoopVectorize;
   bool RerollLoops;
   bool LoadCombine;
   bool DisableGVNLoadPRE;
   bool VerifyInput;
   bool VerifyOutput;
   bool MergeFunctions;
   bool PrepareForLTO;
+  bool PrepareForThinLTO;
+  bool PerformThinLTO;
 
   /// Profile data file name that the instrumentation will be written to.
   std::string PGOInstrGen;
   /// Path of the profile data file.
   std::string PGOInstrUse;
 
 private:
   /// ExtensionList - This is list of all of the extensions that are registered.
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.
   void populateModulePassManager(legacy::PassManagerBase &MPM);
   void populateLTOPassManager(legacy::PassManagerBase &PM);
+  void populateThinLTOPassManager(legacy::PassManagerBase &PM);
 };
 
 /// Registers a function for adding a standard set of passes.  This should be
 /// used by optimizer plugins to allow all front ends to transparently use
 /// them.  Create a static instance of this class in your plugin, providing a
 /// private function that the PassManagerBuilder can use to add your passes.
 struct RegisterStandardPasses {
   RegisterStandardPasses(PassManagerBuilder::ExtensionPointTy Ty,
                          PassManagerBuilder::ExtensionFn Fn) {
     PassManagerBuilder::addGlobalExtension(Ty, Fn);
   }
 };
 
 } // end namespace llvm
 #endif

lib/Transforms/IPO/PassManagerBuilder.cpp

PassManagerBuilder::PassManagerBuilder() {
     LoadCombine = RunLoadCombine;
     DisableGVNLoadPRE = false;
     VerifyInput = false;
     VerifyOutput = false;
     MergeFunctions = false;
     PrepareForLTO = false;
     PGOInstrGen = RunPGOInstrGen;
     PGOInstrUse = RunPGOInstrUse;
+    PrepareForThinLTO = false;
+    PerformThinLTO = false;
 }
 
 PassManagerBuilder::~PassManagerBuilder() {
   delete LibraryInfo;
   delete Inliner;
 }
 
 /// Set of global extensions, automatically added as part of the standard set.
void PassManagerBuilder::addFunctionSimplificationPasses(
   MPM.add(createCorrelatedValuePropagationPass()); // Propagate conditionals
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createInstructionCombiningPass());  // Combine silly seq's
   addExtensionsToPM(EP_Peephole, MPM);
 
   MPM.add(createTailCallEliminationPass()); // Eliminate tail calls
   MPM.add(createCFGSimplificationPass());     // Merge & remove BBs
   MPM.add(createReassociatePass());           // Reassociate expressions
+  if (PrepareForThinLTO) {
+    MPM.add(createAggressiveDCEPass());        // Delete dead instructions
+    MPM.add(createInstructionCombiningPass()); // Combine silly seq's
+    return;
+  }
   // Rotate Loop - disable header duplication at -Oz
   MPM.add(createLoopRotatePass(SizeLevel == 2 ? 0 : -1));
   MPM.add(createLICMPass());                  // Hoist loop invariants
   MPM.add(createLoopUnswitchPass(SizeLevel || OptLevel < 3));
   MPM.add(createCFGSimplificationPass());
   MPM.add(createInstructionCombiningPass());
   MPM.add(createIndVarSimplifyPass());        // Canonicalize indvars
   MPM.add(createLoopIdiomPass());             // Recognize idioms like memset.
void PassManagerBuilder::populateModulePassManager(
   addInitialAliasAnalysisPasses(MPM);
 
   if (!DisableUnitAtATime) {
     // Infer attributes about declarations if possible.
     MPM.add(createInferFunctionAttrsLegacyPass());
 
     addExtensionsToPM(EP_ModuleOptimizerEarly, MPM);
 
     MPM.add(createIPSCCPPass());          // IP SCCP
     MPM.add(createGlobalOptimizerPass()); // Optimize out global vars
     // Promote any localized global vars.
     MPM.add(createPromoteMemoryToRegisterPass());
 
     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 (!PerformThinLTO)
+    /// PGO instrumentation is added during the compile phase for ThinLTO, do
+    /// not run it a second time
     addPGOInstrPasses(MPM);
 
   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(createPostOrderFunctionAttrsPass());
   if (OptLevel > 2)
     MPM.add(createArgumentPromotionPass()); // Scalarize uninlined fn args
 
   addFunctionSimplificationPasses(MPM);
 
+  // If we are planning to perform ThinLTO later, let's not bloat the code with
+  // unrolling/vectorization/... now. We'll first run the inliner + CGSCC passes
+  // during ThinLTO and perform the rest of the optimizations afterward.
+  if (PrepareForThinLTO)
+    return;
+
   // 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());
 
   // Scheduling LoopVersioningLICM when inlining is over, because after that
   // we may see more accurate aliasing. Reason to run this late is that too
   // early versioning may prevent further inlining due to increase of code
   // size. By placing it just after inlining other optimizations which runs 
   // later might get benefit of no-alias assumption in clone loop. 
   if (UseLoopVersioningLICM) {
     MPM.add(createLoopVersioningLICMPass());    // Do LoopVersioningLICM
     MPM.add(createLICMPass());                  // Hoist loop invariants
   }
 
   if (!DisableUnitAtATime)
     MPM.add(createReversePostOrderFunctionAttrsPass());
 
-  if (!DisableUnitAtATime && OptLevel > 1 && !PrepareForLTO) {
+  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());
+
+  if (PerformThinLTO) {
+    // 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());
+    addFunctionSimplificationPasses(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(
   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::populateThinLTOPassManager(
+    legacy::PassManagerBase &PM) {
+  PerformThinLTO = true;
+
+  if (VerifyInput)
+    PM.add(createVerifierPass());
+
+  if (FunctionIndex)
+    PM.add(createFunctionImportPass(FunctionIndex));
+
+  populateModulePassManager(PM);
+
+  if (VerifyOutput)
+    PM.add(createVerifierPass());
+  PerformThinLTO = false;
+}
+
 void PassManagerBuilder::populateLTOPassManager(legacy::PassManagerBase &PM) {
   if (LibraryInfo)
     PM.add(new TargetLibraryInfoWrapperPass(*LibraryInfo));
 
   if (VerifyInput)
     PM.add(createVerifierPass());
 
   if (OptLevel != 0)