[InstCombine] Delay Phi operand folding in the pass manager

[labrinea]

Summary

Folding Phi operands too early in the pass pipeline can prevent other optimization passes, like GVN-Hoist, from being beneficial. This patch makes InstCombine capable of turning on/off the folding of Phi operands. Then uses that capability to delay Phi operand folding from the pass manager.

[labrinea]

Not ready for review. Using this as reference to and RFC in llvm-dev.

include/llvm/Transforms/IPO/PassManagerBuilder.h

 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 addPGOInstrPasses(legacy::PassManagerBase &MPM);
   void addFunctionSimplificationPasses(legacy::PassManagerBase &MPM);
-  void addInstructionCombiningPass(legacy::PassManagerBase &MPM) const;
+  void addInstructionCombiningPass(legacy::PassManagerBase &MPM,
+                                   bool FoldPhiArgs = true) const;
 
 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.

include/llvm/Transforms/InstCombine/InstCombine.h

 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 
 namespace llvm {
 
 class InstCombinePass : public PassInfoMixin<InstCombinePass> {
   InstCombineWorklist Worklist;
   bool ExpensiveCombines;
+  bool FoldPhiArgs;
 
 public:
   static StringRef name() { return "InstCombinePass"; }
 
-  explicit InstCombinePass(bool ExpensiveCombines = true)
-      : ExpensiveCombines(ExpensiveCombines) {}
+  explicit InstCombinePass(bool ExpensiveCombines = true,
+                           bool FoldPhiArgs = true)
+      : ExpensiveCombines(ExpensiveCombines),
+        FoldPhiArgs(FoldPhiArgs) {}
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 };
 
 /// The legacy pass manager's instcombine pass.
 ///
 /// This is a basic whole-function wrapper around the instcombine utility. It
 /// will try to combine all instructions in the function.
 class InstructionCombiningPass : public FunctionPass {
   InstCombineWorklist Worklist;
   const bool ExpensiveCombines;
+  const bool FoldPhiArgs;
 
 public:
   static char ID; // Pass identification, replacement for typeid
 
-  InstructionCombiningPass(bool ExpensiveCombines = true)
-      : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines) {
+  InstructionCombiningPass(bool ExpensiveCombines = true,
+                           bool FoldPhiArgs = true)
+      : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines),
+        FoldPhiArgs(FoldPhiArgs) {
     initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   bool runOnFunction(Function &F) override;
 };
 
 //===----------------------------------------------------------------------===//
 //
 // InstructionCombining - Combine instructions to form fewer, simple
 // instructions. This pass does not modify the CFG, and has a tendency to make
 // instructions dead, so a subsequent DCE pass is useful.
 //
 // This pass combines things like:
 //    %Y = add int 1, %X
 //    %Z = add int 1, %Y
 // into:
 //    %Z = add int 2, %X
 //
-FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true);
+FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true,
+                                             bool FoldPhiArgs = true);
 }
 
 #endif

lib/Passes/PassBuilder.cpp

PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
 
   // Remove any dead arguments exposed by cleanups and constand folding
   // globals.
   MPM.addPass(DeadArgumentEliminationPass());
 
   // Create a small function pass pipeline to cleanup after all the global
   // optimizations.
   FunctionPassManager GlobalCleanupPM(DebugLogging);
-  GlobalCleanupPM.addPass(InstCombinePass());
+  GlobalCleanupPM.addPass(InstCombinePass(true, false));
   invokePeepholeEPCallbacks(GlobalCleanupPM, Level);
 
   GlobalCleanupPM.addPass(SimplifyCFGPass());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(GlobalCleanupPM)));
 
   // Add all the requested passes for instrumentation PGO, if requested.
   if (PGOOpt && Phase != ThinLTOPhase::PostLink &&
       (!PGOOpt->ProfileGenFile.empty() || !PGOOpt->ProfileUseFile.empty())) {

lib/Transforms/IPO/PassManagerBuilder.cpp

void PassManagerBuilder::addInitialAliasAnalysisPasses(
   // Add TypeBasedAliasAnalysis before BasicAliasAnalysis so that
   // BasicAliasAnalysis wins if they disagree. This is intended to help
   // support "obvious" type-punning idioms.
   PM.add(createTypeBasedAAWrapperPass());
   PM.add(createScopedNoAliasAAWrapperPass());
 }
 
 void PassManagerBuilder::addInstructionCombiningPass(
-    legacy::PassManagerBase &PM) const {
+    legacy::PassManagerBase &PM, bool FoldPhiArgs) const {
   bool ExpensiveCombines = OptLevel > 2;
-  PM.add(createInstructionCombiningPass(ExpensiveCombines));
+  PM.add(createInstructionCombiningPass(ExpensiveCombines,
+                                        FoldPhiArgs));
 }
 
 void PassManagerBuilder::populateFunctionPassManager(
     legacy::FunctionPassManager &FPM) {
   addExtensionsToPM(EP_EarlyAsPossible, FPM);
   FPM.add(createEntryExitInstrumenterPass());
 
   // Add LibraryInfo if we have some.
void PassManagerBuilder::populateModulePassManager(
   MPM.add(createIPSCCPPass());          // IP SCCP
   MPM.add(createCalledValuePropagationPass());
   MPM.add(createGlobalOptimizerPass()); // Optimize out global vars
   // Promote any localized global vars.
   MPM.add(createPromoteMemoryToRegisterPass());
 
   MPM.add(createDeadArgEliminationPass()); // Dead argument elimination
 
-  addInstructionCombiningPass(MPM); // Clean up after IPCP & DAE
+  addInstructionCombiningPass(MPM, false); // Clean up after IPCP & DAE
   addExtensionsToPM(EP_Peephole, MPM);
   MPM.add(createCFGSimplificationPass()); // Clean up after IPCP & DAE
 
   // For SamplePGO in ThinLTO compile phase, we do not want to do indirect
   // call promotion as it will change the CFG too much to make the 2nd
   // profile annotation in backend more difficult.
   // PGO instrumentation is added during the compile phase for ThinLTO, do
   // not run it a second time

lib/Transforms/InstCombine/InstCombineInternal.h

 
 private:
   // Mode in which we are running the combiner.
   const bool MinimizeSize;
 
   /// Enable combines that trigger rarely but are costly in compiletime.
   const bool ExpensiveCombines;
 
+  // Allow operand folding of Phi Nodes.
+  const bool FoldPhiArgs;
+
   AliasAnalysis *AA;
 
   // Required analyses.
   AssumptionCache ∾
   TargetLibraryInfo &TLI;
   DominatorTree &DT;
   const DataLayout &DL;
   const SimplifyQuery SQ;
   OptimizationRemarkEmitter &ORE;
 
   // Optional analyses. When non-null, these can both be used to do better
   // combining and will be updated to reflect any changes.
   LoopInfo *LI;
 
   bool MadeIRChange = false;
 
 public:
   InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
-               bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
-               AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
-               OptimizationRemarkEmitter &ORE, const DataLayout &DL,
-               LoopInfo *LI)
+               bool MinimizeSize, bool ExpensiveCombines,
+               bool FoldPhiArgs, AliasAnalysis *AA,
+               AssumptionCache &AC, TargetLibraryInfo &TLI,
+               DominatorTree &DT, OptimizationRemarkEmitter &ORE,
+               const DataLayout &DL, LoopInfo *LI)
       : Worklist(Worklist), Builder(Builder), MinimizeSize(MinimizeSize),
-        ExpensiveCombines(ExpensiveCombines), AA(AA), AC(AC), TLI(TLI), DT(DT),
-        DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {}
+        ExpensiveCombines(ExpensiveCombines),
+        FoldPhiArgs(FoldPhiArgs), AA(AA), AC(AC), TLI(TLI),
+        DT(DT), DL(DL), SQ(DL, &TLI, &DT, &AC), ORE(ORE), LI(LI) {}
 
   /// Run the combiner over the entire worklist until it is empty.
   ///
   /// \returns true if the IR is changed.
   bool run();
 
   AssumptionCache &getAssumptionCache() const { return AC; }
 

lib/Transforms/InstCombine/InstCombinePHI.cpp

Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) {
   PHIArgMergedDebugLoc(NewLI, PN);
   return NewLI;
 }
 
 /// TODO: This function could handle other cast types, but then it might
 /// require special-casing a cast from the 'i1' type. See the comment in
 /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
 Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
+  if (!FoldPhiArgs)
+    return nullptr;
   // We cannot create a new instruction after the PHI if the terminator is an
   // EHPad because there is no valid insertion point.
   if (TerminatorInst *TI = Phi.getParent()->getTerminator())
     if (TI->isEHPad())
       return nullptr;
 
   // Early exit for the common case of a phi with two operands. These are
   // handled elsewhere. See the comment below where we check the count of zexts
Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
   InsertNewInstBefore(NewPhi, Phi);
   return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
 }
 
 /// If all operands to a PHI node are the same "unary" operator and they all are
 /// only used by the PHI, PHI together their inputs, and do the operation once,
 /// to the result of the PHI.
 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
+  if (!FoldPhiArgs)
+    return nullptr;
   // We cannot create a new instruction after the PHI if the terminator is an
   // EHPad because there is no valid insertion point.
   if (TerminatorInst *TI = PN.getParent()->getTerminator())
     if (TI->isEHPad())
       return nullptr;
 
   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
 

lib/Transforms/InstCombine/InstructionCombining.cpp

static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
 
   return MadeIRChange;
 }
 
 static bool combineInstructionsOverFunction(
     Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA,
     AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT,
     OptimizationRemarkEmitter &ORE, bool ExpensiveCombines = true,
-    LoopInfo *LI = nullptr) {
+    bool FoldPhiArgs = true, LoopInfo *LI = nullptr) {
   auto &DL = F.getParent()->getDataLayout();
   ExpensiveCombines |= EnableExpensiveCombines;
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// instructions into the worklist when they are created.
   IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
       F.getContext(), TargetFolder(DL),
       IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
static bool combineInstructionsOverFunction(
   int Iteration = 0;
   while (true) {
     ++Iteration;
     LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
                       << F.getName() << "\n");
 
     MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
 
-    InstCombiner IC(Worklist, Builder, F.optForMinSize(), ExpensiveCombines, AA,
-                    AC, TLI, DT, ORE, DL, LI);
+    InstCombiner IC(Worklist, Builder, F.optForMinSize(), ExpensiveCombines,
+                    FoldPhiArgs, AA, AC, TLI, DT, ORE, DL, LI);
     IC.MaxArraySizeForCombine = MaxArraySize;
 
     if (!IC.run())
       break;
   }
 
   return MadeIRChange || Iteration > 1;
 }
 
 PreservedAnalyses InstCombinePass::run(Function &F,
                                        FunctionAnalysisManager &AM) {
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 
   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
 
   auto *AA = &AM.getResult<AAManager>(F);
   if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE,
-                                       ExpensiveCombines, LI))
+                                       ExpensiveCombines, FoldPhiArgs,
+                                       LI))
     // No changes, all analyses are preserved.
     return PreservedAnalyses::all();
 
   // Mark all the analyses that instcombine updates as preserved.
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<BasicAA>();
bool InstructionCombiningPass::runOnFunction(Function &F) {
   auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   auto &ORE = getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
 
   // Optional analyses.
   auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
 
   return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE,
-                                         ExpensiveCombines, LI);
+                                         ExpensiveCombines, FoldPhiArgs,
+                                         LI);
 }
 
 char InstructionCombiningPass::ID = 0;
 
 INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine",
                       "Combine redundant instructions", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
 INITIALIZE_PASS_END(InstructionCombiningPass, "instcombine",
                     "Combine redundant instructions", false, false)
 
 // Initialization Routines
 void llvm::initializeInstCombine(PassRegistry &Registry) {
   initializeInstructionCombiningPassPass(Registry);
 }
 
 void LLVMInitializeInstCombine(LLVMPassRegistryRef R) {
   initializeInstructionCombiningPassPass(*unwrap(R));
 }
 
-FunctionPass *llvm::createInstructionCombiningPass(bool ExpensiveCombines) {
-  return new InstructionCombiningPass(ExpensiveCombines);
+FunctionPass *llvm::createInstructionCombiningPass(bool ExpensiveCombines,
+                                                   bool FoldPhiArgs) {
+  return new InstructionCombiningPass(ExpensiveCombines, FoldPhiArgs);
 }
 
 void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createInstructionCombiningPass());
 }