[CallSiteSplitting] Preserve DominatorTreeAnalysis.

[fhahn]

Summary

The dominator tree analysis can be preserved easily.
Some other kinds of analysis can probably be preserved
too.

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

547

Considering that this pass doesn't use DT, do we need to get DT to preserve DT ?

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

547

We need the current dominator tree, so we can update it. Not sure if there is a better way to get it though.

[junbuml]

lib/Transforms/Scalar/CallSiteSplitting.cpp

547

I just wanted to ask if constructing DT in advance is just okay because this pass doesn't even use DT. Isn't it okay to construct DT when DT is really required in a later pass?

[fhahn]

lib/Transforms/Scalar/CallSiteSplitting.cpp

547

I'll check. AFAIK CallSiteSplitting is run after a bunch of passes that require the DT to be constructed already and by saying we do not preserve the DT we force it to be re-computed.

[brzycki]

lib/Transforms/Scalar/CallSiteSplitting.cpp

547

Hi @fhahn , you should just need one additional line in your patch to inform the pass manager to properly preserve DT.

INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)

You can use -debug-pass=Executions with opt during testing to verify the order of creation/deletion of the Dominator Tree pass. Here's an example snippet:

[2018-02-12 11:37:22.659888285] 0x1fb5240     Executing Pass 'Dominator Tree Construction' on Function 'test1'...
[2018-02-12 11:37:22.659992339] 0x1fb5240     Executing Pass 'Basic Alias Analysis (stateless AA impl)' on Function 'test1'...
[2018-02-12 11:37:22.660156849] 0x1fb5240     Executing Pass 'Function Alias Analysis Results' on Function 'test1'...
[2018-02-12 11:37:22.660254827] 0x1fb5240     Executing Pass 'Lazy Value Information Analysis' on Function 'test1'...
[2018-02-12 11:37:22.660302165] 0x1fb5240     Executing Pass 'Jump Threading' on Function 'test1'...
[2018-02-12 11:37:22.661679568] 0x1fb5240     Made Modification 'Jump Threading' on Function 'test1'...
[2018-02-12 11:37:22.661739504] 0x1fb5240      Freeing Pass 'Basic Alias Analysis (stateless AA impl)' on Function 'test1'...
[2018-02-12 11:37:22.661767275] 0x1fb5240      Freeing Pass 'Function Alias Analysis Results' on Function 'test1'...
[2018-02-12 11:37:22.661795430] 0x1fb5240      Freeing Pass 'Lazy Value Information Analysis' on Function 'test1'...
[2018-02-12 11:37:22.661840127] 0x1fb5240      Freeing Pass 'Jump Threading' on Function 'test1'...
[2018-02-12 11:37:22.661870858] 0x1fb5240      Freeing Pass 'Dominator Tree Construction' on Function 'test1'...
[2018-02-12 11:37:22.661904074] 0x1fb5240     Executing Pass 'Module Verifier' on Function 'test1'...

[• dberlin]

Please use getAnalysisIfAvailable for the old pass manager
Please use getCachedResult for the new pass manager.

That is the correct way to "get an analysis if it is sitting around so we can update it".

The way you've done it now will actually calculate DT if it's not calculated already.

[fhahn]

Thanks @dberlin .

updated to use use getAnalysisIfAvailable for the old pass manager and getCachedResult for the new pass manager.

[fhahn]

Mark DominatorTreeWrapperPass as preserved with old pass manager.

[• dberlin]

So this looks right to me.
I'm a little worried about how we are having to modify tons and tons of functions to push these through.
When we get to postdominator updates, we'll have to do the same thing.

At some point, if what we are trying to do is preserve analysis, i wonder if we shouldn't be passing analysismanager's around or something.

[• dberlin]

An example of that is getBestSimplifyQuery, which takes various analysis managers, etc, and extracts the analysis it cares about them.
If we did similar, we could simplify what gets passed through and easily add updating of a new thing.

[fhahn]

Thanks for the pointers. Do you think it would make sense to add something generic which takes various analysis managers, etc, and extracts the analysis on demand, for other passes to use too?

[• dberlin]

Personally, i totally think this is worthwhile and worth spending some time on to prevent the slow proliferation of 10+ argument functions taking analysis results. Because that's the path we are heading down, and that's definitely hard to refactor, change, etc
But i'm also not the person who would do the work (though happy to review).

If you want to look into it, bring it up on the mailing list and see what folks think.

[fhahn]

Rebased.

[fhahn]

rebased again

lib/Transforms/Scalar/CallSiteSplitting.cpp

 ///   Tail:
 ///    %p = phi i1 [%ca1, %Tail-split1],[%ca2, %Tail-split2]
 ///
 /// Note that in case any arguments at the call-site are constrained by its
 /// predecessors, new call-sites with more constrained arguments will be
 /// created in createCallSitesOnPredicatedArgument().
 static void splitCallSite(
     CallSite CS,
-    const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds) {
+    const SmallVectorImpl<std::pair<BasicBlock *, ConditionsTy>> &Preds,
+    DominatorTree *DT) {
   Instruction *Instr = CS.getInstruction();
   BasicBlock *TailBB = Instr->getParent();
   bool IsMustTailCall = CS.isMustTailCall();
 
   PHINode *CallPN = nullptr;
 
   // `musttail` calls must be followed by optional `bitcast`, and `ret`. The
   // split blocks will be terminated right after that so there're no users for
   // this phi in a `TailBB`.
   if (!IsMustTailCall && !Instr->use_empty())
     CallPN = PHINode::Create(Instr->getType(), Preds.size(), "phi.call");
 
   DEBUG(dbgs() << "split call-site : " << *Instr << " into \n");
 
   assert(Preds.size() == 2 && "The ValueToValueMaps array has size 2.");
   // ValueToValueMapTy is neither copy nor moveable, so we use a simple array
   // here.
   ValueToValueMapTy ValueToValueMaps[2];
   for (unsigned i = 0; i < Preds.size(); i++) {
     BasicBlock *PredBB = Preds[i].first;
     BasicBlock *SplitBlock = DuplicateInstructionsInSplitBetween(
-        TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i]);
+        TailBB, PredBB, &*std::next(Instr->getIterator()), ValueToValueMaps[i],
+        DT);
     assert(SplitBlock && "Unexpected new basic block split.");
 
     Instruction *NewCI =
         &*std::prev(SplitBlock->getTerminator()->getIterator());
     CallSite NewCS(NewCI);
     addConditions(NewCS, Preds[i].second);
 
     // Handle PHIs used as arguments in the call-site.
if (PHINode *PN = dyn_cast<PHINode>(&BI)) {
             return true;
         }
     }
     break;
   }
   return false;
 }
 
-static bool tryToSplitOnPHIPredicatedArgument(CallSite CS) {
+static bool tryToSplitOnPHIPredicatedArgument(CallSite CS, DominatorTree *DT) {
   if (!isPredicatedOnPHI(CS))
     return false;
 
   auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
   SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2> PredsCS = {
       {Preds[0], {}}, {Preds[1], {}}};
-  splitCallSite(CS, PredsCS);
+  splitCallSite(CS, PredsCS, DT);
   return true;
 }
 
-static bool tryToSplitOnPredicatedArgument(CallSite CS) {
+static bool tryToSplitOnPredicatedArgument(CallSite CS, DominatorTree *DT) {
   auto Preds = getTwoPredecessors(CS.getInstruction()->getParent());
   if (Preds[0] == Preds[1])
     return false;
 
   SmallVector<std::pair<BasicBlock *, ConditionsTy>, 2> PredsCS;
   for (auto *Pred : make_range(Preds.rbegin(), Preds.rend())) {
     ConditionsTy Conditions;
     recordConditions(CS, Pred, Conditions);
     PredsCS.push_back({Pred, Conditions});
   }
 
   if (std::all_of(PredsCS.begin(), PredsCS.end(),
                   [](const std::pair<BasicBlock *, ConditionsTy> &P) {
                     return P.second.empty();
                   }))
     return false;
 
-  splitCallSite(CS, PredsCS);
+  splitCallSite(CS, PredsCS, DT);
   return true;
 }
 
-static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI) {
+static bool tryToSplitCallSite(CallSite CS, TargetTransformInfo &TTI,
+                               DominatorTree *DT) {
   if (!CS.arg_size() || !canSplitCallSite(CS, TTI))
     return false;
-  return tryToSplitOnPredicatedArgument(CS) ||
-         tryToSplitOnPHIPredicatedArgument(CS);
+  return tryToSplitOnPredicatedArgument(CS, DT) ||
+         tryToSplitOnPHIPredicatedArgument(CS, DT);
 }
 
 static bool doCallSiteSplitting(Function &F, TargetLibraryInfo &TLI,
-                                TargetTransformInfo &TTI) {
+                                TargetTransformInfo &TTI, DominatorTree *DT) {
   bool Changed = false;
   for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE;) {
     BasicBlock &BB = *BI++;
     auto II = BB.getFirstNonPHIOrDbg()->getIterator();
     auto IE = BB.getTerminator()->getIterator();
     // Iterate until we reach the terminator instruction. tryToSplitCallSite
     // can replace BB's terminator in case BB is a successor of itself. In that
     // case, IE will be invalidated and we also have to check the current
     // terminator.
     while (II != IE && &*II != BB.getTerminator()) {
       Instruction *I = &*II++;
       CallSite CS(cast<Value>(I));
       if (!CS || isa<IntrinsicInst>(I) || isInstructionTriviallyDead(I, &TLI))
         continue;
 
       Function *Callee = CS.getCalledFunction();
       if (!Callee || Callee->isDeclaration())
         continue;
 
       // Successful musttail call-site splits result in erased CI and erased BB.
       // Check if such path is possible before attempting the splitting.
       bool IsMustTail = CS.isMustTailCall();
 
-      Changed |= tryToSplitCallSite(CS, TTI);
+      Changed |= tryToSplitCallSite(CS, TTI, DT);
 
       // There're no interesting instructions after this. The call site
       // itself might have been erased on splitting.
       if (IsMustTail)
         break;
     }
   }
   return Changed;
 }
 
 namespace {
 struct CallSiteSplittingLegacyPass : public FunctionPass {
   static char ID;
   CallSiteSplittingLegacyPass() : FunctionPass(ID) {
     initializeCallSiteSplittingLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     AU.addRequired<TargetTransformInfoWrapperPass>();
+    AU.addPreserved<DominatorTreeWrapperPass>();
     FunctionPass::getAnalysisUsage(AU);
   }
 
   bool runOnFunction(Function &F) override {
     if (skipFunction(F))
       return false;
 
     auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
     auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
-    return doCallSiteSplitting(F, TLI, TTI);
+    auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+    return doCallSiteSplitting(F, TLI, TTI,
+                               DTWP ? &DTWP->getDomTree() : nullptr);
   }
 };
 } // namespace
 
 char CallSiteSplittingLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(CallSiteSplittingLegacyPass, "callsite-splitting",
                       "Call-site splitting", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_END(CallSiteSplittingLegacyPass, "callsite-splitting",
                     "Call-site splitting", false, false)
 FunctionPass *llvm::createCallSiteSplittingPass() {
   return new CallSiteSplittingLegacyPass();
 }
 
 PreservedAnalyses CallSiteSplittingPass::run(Function &F,
                                              FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
+  auto *DT = AM.getCachedResult<DominatorTreeAnalysis>(F);
 
-  if (!doCallSiteSplitting(F, TLI, TTI))
+  if (!doCallSiteSplitting(F, TLI, TTI, DT))
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
+  PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }