[JumpThreading] Use runtime parameter to allow for DT and LVI preservation.

[brzycki]

Summary

The flag "print-lvi-after-jump-threading" determines if DT and LVI should be preserved in JumpThreading. The default is to disable preservation.

I have concerns with this approach as it requires passes that want to rely on LVI and DT to also understand the conditional nature of JumpThreading. This may complicate work like D34135 .

I am posting it here in case it is useful in profiling compile time deltas.

This patch requires D38558 to be applied first in order to function.

[brzycki]

I'd rather not use a flag to enable Dominance. The newer patch D40146 uses a deferred preservation method to reclaim performance.

llvm/lib/Transforms/Scalar/JumpThreading.cpp

 ImplicationSearchThreshold(
   "jump-threading-implication-search-threshold",
   cl::desc("The number of predecessors to search for a stronger "
            "condition to use to thread over a weaker condition"),
   cl::init(3), cl::Hidden);
 
 static cl::opt<bool> PrintLVIAfterJumpThreading(
     "print-lvi-after-jump-threading",
-    cl::desc("Print the LazyValueInfo cache after JumpThreading"), cl::init(false),
-    cl::Hidden);
+    cl::desc("Print the LazyValueInfo cache after JumpThreading"),
+    cl::init(false), cl::Hidden);
+
+static cl::opt<bool> PreserveDTandLVI(
+    "jump-threading-preserve-dt-and-lvi",
+    cl::desc("Preserve DominatorTree and LazyValueInfo while JumpThreading"),
+    cl::init(false), cl::Hidden);
 
 namespace {
 
   /// This pass performs 'jump threading', which looks at blocks that have
   /// multiple predecessors and multiple successors.  If one or more of the
   /// predecessors of the block can be proven to always jump to one of the
   /// successors, we forward the edge from the predecessor to the successor by
   /// duplicating the contents of this block.
public:
     JumpThreading(int T = -1) : FunctionPass(ID), Impl(T) {
       initializeJumpThreadingPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<DominatorTreeWrapperPass>();
+      if (PreserveDTandLVI)
         AU.addPreserved<DominatorTreeWrapperPass>();
       AU.addRequired<AAResultsWrapperPass>();
       AU.addRequired<LazyValueInfoWrapperPass>();
+      if (PreserveDTandLVI)
         AU.addPreserved<LazyValueInfoWrapperPass>();
       AU.addPreserved<GlobalsAAWrapperPass>();
       AU.addRequired<TargetLibraryInfoWrapperPass>();
     }
 
     void releaseMemory() override { Impl.releaseMemory(); }
   };
 
 } // end anonymous namespace
if (HasProfileData) {
     BPI.reset(new BranchProbabilityInfo(F, LI, TLI));
     BFI.reset(new BlockFrequencyInfo(F, *BPI, LI));
   }
 
   bool Changed = Impl.runImpl(F, TLI, LVI, AA, DT, HasProfileData,
                               std::move(BFI), std::move(BPI));
   if (PrintLVIAfterJumpThreading) {
     dbgs() << "LVI for function '" << F.getName() << "':\n";
+    if (!PreserveDTandLVI)
+      DT->recalculate(F);
     LVI->printLVI(F, *DT, dbgs());
   }
   return Changed;
 }
 
 PreservedAnalyses JumpThreadingPass::run(Function &F,
                                          FunctionAnalysisManager &AM) {
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
PreservedAnalyses JumpThreadingPass::run(Function &F,
 
   bool Changed = runImpl(F, &TLI, &LVI, &AA, &DT, HasProfileData,
                          std::move(BFI), std::move(BPI));
 
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<GlobalsAA>();
+  if (PreserveDTandLVI) {
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<LazyValueAnalysis>();
+  }
   return PA;
 }
 
 bool JumpThreadingPass::runImpl(Function &F, TargetLibraryInfo *TLI_,
                                 LazyValueInfo *LVI_, AliasAnalysis *AA_,
                                 DominatorTree *DT_, bool HasProfileData_,
                                 std::unique_ptr<BlockFrequencyInfo> BFI_,
                                 std::unique_ptr<BranchProbabilityInfo> BPI_) {
   DEBUG(dbgs() << "Jump threading on function '" << F.getName() << "'\n");
   TLI = TLI_;
   LVI = LVI_;
   AA = AA_;
+  if (PreserveDTandLVI)
     DT = DT_;
+  else
+    DT = nullptr;
   BFI.reset();
   BPI.reset();
   // When profile data is available, we need to update edge weights after
   // successful jump threading, which requires both BPI and BFI being available.
   HasProfileData = HasProfileData_;
   auto *GuardDecl = F.getParent()->getFunction(
       Intrinsic::getName(Intrinsic::experimental_guard));
   HasGuards = GuardDecl && !GuardDecl->use_empty();
if (isa<UndefValue>(Condition)) {
     // Fold the branch/switch.
     TerminatorInst *BBTerm = BB->getTerminator();
     for (unsigned i = 0, e = BBTerm->getNumSuccessors(); i != e; ++i) {
       if (i == BestSucc) continue;
       BasicBlock *Succ = BBTerm->getSuccessor(i);
       Succ->removePredecessor(BB, true);
       if (Succ == BB)
         continue;
+      if (DT) {
         DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, Succ};
         // Make sure to remove a DT edge exactly once and not an edge to itself.
         if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
           Updates.push_back(UT);
       }
+    }
 
     DEBUG(dbgs() << "  In block '" << BB->getName()
           << "' folding undef terminator: " << *BBTerm << '\n');
     BranchInst::Create(BBTerm->getSuccessor(BestSucc), BBTerm);
     BBTerm->eraseFromParent();
+    if (DT)
       DT->applyUpdates(Updates);
     return true;
   }
 
   // If the terminator of this block is branching on a constant, simplify the
   // terminator to an unconditional branch.  This can occur due to threading in
   // other blocks.
   if (getKnownConstant(Condition, Preference)) {
     DEBUG(dbgs() << "  In block '" << BB->getName()
if (CondBr && CondConst) {
       if (Ret != LazyValueInfo::Unknown) {
         unsigned ToRemove = Ret == LazyValueInfo::True ? 1 : 0;
         unsigned ToKeep = Ret == LazyValueInfo::True ? 0 : 1;
         BasicBlock *ToRemoveSucc = CondBr->getSuccessor(ToRemove);
         BasicBlock *ToKeepSucc = CondBr->getSuccessor(ToKeep);
         ToRemoveSucc->removePredecessor(BB, true);
         BranchInst::Create(CondBr->getSuccessor(ToKeep), CondBr);
         CondBr->eraseFromParent();
-        if (BB != ToRemoveSucc && ToRemoveSucc != ToKeepSucc)
+        if (DT && BB != ToRemoveSucc && ToRemoveSucc != ToKeepSucc)
           DT->deleteEdge(BB, ToRemoveSucc);
         if (CondCmp->use_empty())
           CondCmp->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
         // presence of guards and assumes, that have the `Cond` as the use. This
         // is because we use the guards/assume to reason about the `Cond` value
         // at the end of block, but RAUW unconditionally replaces all uses
while (CurrentPred && Iter++ < ImplicationSearchThreshold) {
     Optional<bool> Implication =
         isImpliedCondition(PBI->getCondition(), Cond, DL, CondIsTrue);
     if (Implication) {
       BasicBlock *KeepSucc = BI->getSuccessor(*Implication ? 0 : 1);
       BasicBlock *RemoveSucc = BI->getSuccessor(*Implication ? 1 : 0);
       RemoveSucc->removePredecessor(BB);
       BranchInst::Create(KeepSucc, BI);
       BI->eraseFromParent();
-      if (BB != RemoveSucc && RemoveSucc != KeepSucc)
+      if (DT && BB != RemoveSucc && RemoveSucc != KeepSucc)
         DT->deleteEdge(BB, RemoveSucc);
       return true;
     }
     CurrentBB = CurrentPred;
     CurrentPred = CurrentBB->getSinglePredecessor();
   }
 
   return false;
if (PredWithKnownDest ==
         (size_t)std::distance(pred_begin(BB), pred_end(BB))) {
       std::vector<DominatorTree::UpdateType> Updates;
       bool SeenFirstBranchToOnlyDest = false;
       for (BasicBlock *SuccBB : successors(BB)) {
         if (SuccBB == OnlyDest && !SeenFirstBranchToOnlyDest) {
           SeenFirstBranchToOnlyDest = true; // Don't modify the first branch.
         } else {
           SuccBB->removePredecessor(BB, true); // This is unreachable successor.
-          if (SuccBB != OnlyDest && SuccBB != BB) {
+          if (DT && SuccBB != OnlyDest && SuccBB != BB) {
             DominatorTree::UpdateType UT = {DominatorTree::Delete, BB, SuccBB};
             // Make sure to remove a DT edge exactly once.
             if (std::find(Updates.begin(), Updates.end(), UT) == Updates.end())
               Updates.push_back(UT);
           }
         }
       }
 
       // Finally update the terminator.
       TerminatorInst *Term = BB->getTerminator();
       BranchInst::Create(OnlyDest, Term);
       Term->eraseFromParent();
+      if (DT)
         DT->applyUpdates(Updates);
 
       // If the condition is now dead due to the removal of the old terminator,
       // erase it.
       if (auto *CondInst = dyn_cast<Instruction>(Cond)) {
         if (CondInst->use_empty() && !CondInst->mayHaveSideEffects())
           CondInst->eraseFromParent();
         // We can safely replace *some* uses of the CondInst if it has
         // exactly one value as returned by LVI. RAUW is incorrect in the
bool JumpThreadingPass::ThreadEdge(BasicBlock *BB,
   // us to simplify any PHI nodes in BB.
   TerminatorInst *PredTerm = PredBB->getTerminator();
   for (unsigned i = 0, e = PredTerm->getNumSuccessors(); i != e; ++i)
     if (PredTerm->getSuccessor(i) == BB) {
       BB->removePredecessor(PredBB, true);
       PredTerm->setSuccessor(i, NewBB);
     }
 
+  if (DT)
     DT->applyUpdates({{DominatorTree::Insert, NewBB, SuccBB},
                       {DominatorTree::Insert, PredBB, NewBB},
                       {DominatorTree::Delete, PredBB, BB}});
 
   // At this point, the IR is fully up to date and consistent.  Do a quick scan
   // over the new instructions and zap any that are constants or dead.  This
   // frequently happens because of phi translation.
   SimplifyInstructionsInBlock(NewBB, TLI);
 
   // Update the edge weight from BB to SuccBB, which should be less than before.
   UpdateBlockFreqAndEdgeWeight(PredBB, BB, NewBB, SuccBB);
bool JumpThreadingPass::DuplicateCondBranchOnPHIIntoPred(
   }
 
   // PredBB no longer jumps to BB, remove entries in the PHI node for the edge
   // that we nuked.
   BB->removePredecessor(PredBB, true);
 
   // Remove the unconditional branch at the end of the PredBB block.
   OldPredBranch->eraseFromParent();
-  if (BB != PredBB)
+  if (DT && BB != PredBB)
     DT->deleteEdge(PredBB, BB);
 
   ++NumDupes;
   return true;
 }
 
 /// TryToUnfoldSelect - Look for blocks of the form
 /// bb1:
if ((LHSFolds != LazyValueInfo::Unknown ||
       //  |-----
       //  v
       // BB
       BasicBlock *NewBB = BasicBlock::Create(BB->getContext(), "select.unfold",
                                              BB->getParent(), BB);
       // Move the unconditional branch to NewBB.
       PredTerm->removeFromParent();
       NewBB->getInstList().insert(NewBB->end(), PredTerm);
+      if (DT)
         DT->insertEdge(NewBB, BB);
       // Create a conditional branch and update PHI nodes.
       BranchInst::Create(NewBB, BB, SI->getCondition(), Pred);
       CondLHS->setIncomingValue(I, SI->getFalseValue());
       CondLHS->addIncoming(SI->getTrueValue(), NewBB);
       // The select is now dead.
       SI->eraseFromParent();
 
+      if (DT)
         DT->insertEdge(Pred, NewBB);
       // Update any other PHI nodes in BB.
       for (BasicBlock::iterator BI = BB->begin();
            PHINode *Phi = dyn_cast<PHINode>(BI); ++BI)
         if (Phi != CondLHS)
           Phi->addIncoming(Phi->getIncomingValueForBlock(Pred), NewBB);
       return true;
     }
   }
bool JumpThreadingPass::ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard,
   BasicBlock *UnguardedBlock = DuplicateInstructionsInSplitBetween(
       BB, PredUnguardedBlock, Guard, UnguardedMapping);
   assert(UnguardedBlock && "Could not create the unguarded block?");
   DEBUG(dbgs() << "Moved guard " << *Guard << " to block "
                << GuardedBlock->getName() << "\n");
   // DuplicateInstructionsInSplitBetween inserts a new block, BB.split, between
   // PredBB and BB. We need to perform two inserts and one delete in DT for each
   // of the above calls.
-  DT->applyUpdates({// Guarded block split.
-                    {DominatorTree::Delete, PredGuardedBlock, BB},
-                    {DominatorTree::Insert, PredGuardedBlock, GuardedBlock},
-                    {DominatorTree::Insert, GuardedBlock, BB},
-                    // Unguarded block split.
-                    {DominatorTree::Delete, PredUnguardedBlock, BB},
-                    {DominatorTree::Insert, PredUnguardedBlock, UnguardedBlock},
-                    {DominatorTree::Insert, UnguardedBlock, BB}});
+  if (DT)
+    DT->applyUpdates(
+        {// Guarded block split.
 
   // Some instructions before the guard may still have uses. For them, we need
   // to create Phi nodes merging their copies in both guarded and unguarded
   // branches. Those instructions that have no uses can be just removed.
   SmallVector<Instruction *, 4> ToRemove;
   for (auto BI = BB->begin(); &*BI != AfterGuard; ++BI)
     if (!isa<PHINode>(&*BI))
       ToRemove.push_back(&*BI);