[BBUtils][NFC] Delete SplitBlockAndInsertIfThen with DT.

[caojoshua]

Summary

The method is marked for deprecation. Delete the method and move all of
its consumers to use the DomTreeUpdater version.

[caojoshua]

Add [NFC] to commit message

[caojoshua]

Add [NFC] to commit message

[caojoshua]

ping

[fhahn]

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

419

Sounds like this needs updating, maybe something like Updates the dominator tree via DTU and LI if given.

llvm/lib/Target/AMDGPU/AMDGPUAtomicOptimizer.cpp

107–108

nit: might be clearer to move this to the DomTreeUpdater initialization so it is clear that DT isn't used elsewhere?

108

nit: can just be DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);? Same at other places.

[caojoshua]

Address comments, all stylistic / comments

[caojoshua]

ping

[foad]

Looks fine to me.

I have a slight preference for landing this in two stages, first convert all users and then delete the old method, but I won't insist.

llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp

504

What's the reason for removing this extra verification?

[caojoshua]

Add back DT verification in LibCallsShrinkWrap

[caojoshua]

llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp

504

No good reason. Added it back.

llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h

 ///   SplitBefore
 ///   Tail
 ///
 /// If \p ThenBlock is not specified, a new block will be created for it.
 /// If \p Unreachable is true, the newly created block will end with
 /// UnreachableInst, otherwise it branches to Tail.
 /// Returns the NewBasicBlock's terminator.
 ///
-/// Updates DT and LI if given.
-///
-/// FIXME: deprecated, switch to the DomTreeUpdater-based one.
-Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
-                                       bool Unreachable, MDNode *BranchWeights,
-                                       DominatorTree *DT,
-                                       LoopInfo *LI = nullptr,
-                                       BasicBlock *ThenBlock = nullptr);
-
-/// Split the containing block at the specified instruction - everything before
-/// SplitBefore stays in the old basic block, and the rest of the instructions
-/// in the BB are moved to a new block. The two blocks are connected by a
-/// conditional branch (with value of Cmp being the condition).
-/// Before:
-///   Head
-///   SplitBefore
-///   Tail
-/// After:
-///   Head
-///   if (Cond)
-///     ThenBlock
-///   SplitBefore
-///   Tail
-///
-/// If \p ThenBlock is not specified, a new block will be created for it.
-/// If \p Unreachable is true, the newly created block will end with
-/// UnreachableInst, otherwise it branches to Tail.
-/// Returns the NewBasicBlock's terminator.
-///
-/// Updates DT and LI if given.
+/// Updates DTU and LI if given.
 Instruction *SplitBlockAndInsertIfThen(Value *Cond, Instruction *SplitBefore,
                                        bool Unreachable,
                                        MDNode *BranchWeights = nullptr,
                                        DomTreeUpdater *DTU = nullptr,
                                        LoopInfo *LI = nullptr,
                                        BasicBlock *ThenBlock = nullptr);
 
 /// SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen,

llvm/lib/Target/AMDGPU/AMDGPUAtomicOptimizer.cpp

 /// This pass optimizes atomic operations by using a single lane of a wavefront
 /// to perform the atomic operation, thus reducing contention on that memory
 /// location.
 //
 //===----------------------------------------------------------------------===//
 
 #include "AMDGPU.h"
 #include "GCNSubtarget.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/UniformityAnalysis.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/IntrinsicsAMDGPU.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"

 };
 
 class AMDGPUAtomicOptimizerImpl
     : public InstVisitor<AMDGPUAtomicOptimizerImpl> {
 private:
   SmallVector<ReplacementInfo, 8> ToReplace;
   const UniformityInfo *UA;
   const DataLayout *DL;
-  DominatorTree *DT;
+  DomTreeUpdater &DTU;
   const GCNSubtarget *ST;
   bool IsPixelShader;
 
   Value *buildReduction(IRBuilder<> &B, AtomicRMWInst::BinOp Op, Value *V,
                         Value *const Identity) const;
   Value *buildScan(IRBuilder<> &B, AtomicRMWInst::BinOp Op, Value *V,
                    Value *const Identity) const;
   Value *buildShiftRight(IRBuilder<> &B, Value *V, Value *const Identity) const;
 
   void optimizeAtomic(Instruction &I, AtomicRMWInst::BinOp Op, unsigned ValIdx,
                       bool ValDivergent) const;
 
 public:
   AMDGPUAtomicOptimizerImpl() = delete;
 
   AMDGPUAtomicOptimizerImpl(const UniformityInfo *UA, const DataLayout *DL,
-                            DominatorTree *DT, const GCNSubtarget *ST,
+                            DomTreeUpdater &DTU, const GCNSubtarget *ST,
                             bool IsPixelShader)
-      : UA(UA), DL(DL), DT(DT), ST(ST), IsPixelShader(IsPixelShader) {}
+      : UA(UA), DL(DL), DTU(DTU), ST(ST), IsPixelShader(IsPixelShader) {}
 
   bool run(Function &F);
 
   void visitAtomicRMWInst(AtomicRMWInst &I);
   void visitIntrinsicInst(IntrinsicInst &I);
 };
 
 } // namespace
 
 char AMDGPUAtomicOptimizer::ID = 0;
 
 char &llvm::AMDGPUAtomicOptimizerID = AMDGPUAtomicOptimizer::ID;
 
 bool AMDGPUAtomicOptimizer::runOnFunction(Function &F) {
   if (skipFunction(F)) {
     return false;
   }
 
   const UniformityInfo *UA =
       &getAnalysis<UniformityInfoWrapperPass>().getUniformityInfo();
   const DataLayout *DL = &F.getParent()->getDataLayout();
 
   DominatorTreeWrapperPass *const DTW =
       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-  DominatorTree *DT = DTW ? &DTW->getDomTree() : nullptr;
+  DomTreeUpdater DTU(DTW ? &DTW->getDomTree() : nullptr,
+                     DomTreeUpdater::UpdateStrategy::Lazy);
 
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
   const TargetMachine &TM = TPC.getTM<TargetMachine>();
   const GCNSubtarget *ST = &TM.getSubtarget<GCNSubtarget>(F);
 
   bool IsPixelShader = F.getCallingConv() == CallingConv::AMDGPU_PS;
 
-  return AMDGPUAtomicOptimizerImpl(UA, DL, DT, ST, IsPixelShader).run(F);
+  return AMDGPUAtomicOptimizerImpl(UA, DL, DTU, ST, IsPixelShader).run(F);
 }
 
 PreservedAnalyses AMDGPUAtomicOptimizerPass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
 
   const auto *UA = &AM.getResult<UniformityInfoAnalysis>(F);
   const DataLayout *DL = &F.getParent()->getDataLayout();
 
-  DominatorTree *DT = &AM.getResult<DominatorTreeAnalysis>(F);
+  DomTreeUpdater DTU(&AM.getResult<DominatorTreeAnalysis>(F),
+                     DomTreeUpdater::UpdateStrategy::Lazy);
   const GCNSubtarget *ST = &TM.getSubtarget<GCNSubtarget>(F);
 
   bool IsPixelShader = F.getCallingConv() == CallingConv::AMDGPU_PS;
 
-  return AMDGPUAtomicOptimizerImpl(UA, DL, DT, ST, IsPixelShader).run(F)
+  return AMDGPUAtomicOptimizerImpl(UA, DL, DTU, ST, IsPixelShader).run(F)
              ? PreservedAnalyses::none()
              : PreservedAnalyses::all();
 }
 
 bool AMDGPUAtomicOptimizerImpl::run(Function &F) {
 
   visit(F);
 
void AMDGPUAtomicOptimizerImpl::optimizeAtomic(Instruction &I,
   // in any cross-lane communication, and we use a branch on whether the lane is
   // live to do this.
   if (IsPixelShader) {
     // Record I's original position as the entry block.
     PixelEntryBB = I.getParent();
 
     Value *const Cond = B.CreateIntrinsic(Intrinsic::amdgcn_ps_live, {}, {});
     Instruction *const NonHelperTerminator =
-        SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, DT, nullptr);
+        SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, &DTU, nullptr);
 
     // Record I's new position as the exit block.
     PixelExitBB = I.getParent();
 
     I.moveBefore(NonHelperTerminator);
     B.SetInsertPoint(&I);
   }
 
void AMDGPUAtomicOptimizerImpl::optimizeAtomic(Instruction &I,
   BasicBlock *const EntryBB = I.getParent();
 
   // We need to introduce some new control flow to force a single lane to be
   // active. We do this by splitting I's basic block at I, and introducing the
   // new block such that:
   // entry --> single_lane -\
   //       \------------------> exit
   Instruction *const SingleLaneTerminator =
-      SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, DT, nullptr);
+      SplitBlockAndInsertIfThen(Cond, &I, false, nullptr, &DTU, nullptr);
 
   // Move the IR builder into single_lane next.
   B.SetInsertPoint(SingleLaneTerminator);
 
   // Clone the original atomic operation into single lane, replacing the
   // original value with our newly created one.
   Instruction *const NewI = I.clone();
   B.Insert(NewI);

llvm/lib/Transforms/Instrumentation/DataFlowSanitizer.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/iterator.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
void DFSanFunction::storeOrigin(Instruction *Pos, Value *Addr, uint64_t Size,
 
   if (shouldInstrumentWithCall()) {
     IRB.CreateCall(DFS.DFSanMaybeStoreOriginFn,
                    {CollapsedShadow,
                     IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
                     ConstantInt::get(DFS.IntptrTy, Size), Origin});
   } else {
     Value *Cmp = convertToBool(CollapsedShadow, IRB, "_dfscmp");
+    DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
     Instruction *CheckTerm = SplitBlockAndInsertIfThen(
-        Cmp, &*IRB.GetInsertPoint(), false, DFS.OriginStoreWeights, &DT);
+        Cmp, &*IRB.GetInsertPoint(), false, DFS.OriginStoreWeights, &DTU);
     IRBuilder<> IRBNew(CheckTerm);
     paintOrigin(IRBNew, updateOrigin(Origin, IRBNew), StoreOriginAddr, Size,
                 OriginAlignment);
     ++NumOriginStores;
   }
 }
 
 void DFSanFunction::storeZeroPrimitiveShadow(Value *Addr, uint64_t Size,

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

ReturnInst *llvm::FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB,
   UncondBranch->eraseFromParent();
 
   if (DTU)
     DTU->applyUpdates({{DominatorTree::Delete, Pred, BB}});
 
   return cast<ReturnInst>(NewRet);
 }
 
-static Instruction *
-SplitBlockAndInsertIfThenImpl(Value *Cond, Instruction *SplitBefore,
-                              bool Unreachable, MDNode *BranchWeights,
-                              DomTreeUpdater *DTU, DominatorTree *DT,
-                              LoopInfo *LI, BasicBlock *ThenBlock) {
+Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
+                                             Instruction *SplitBefore,
+                                             bool Unreachable,
+                                             MDNode *BranchWeights,
+                                             DomTreeUpdater *DTU, LoopInfo *LI,
+                                             BasicBlock *ThenBlock) {
   SmallVector<DominatorTree::UpdateType, 8> Updates;
   BasicBlock *Head = SplitBefore->getParent();
   BasicBlock *Tail = Head->splitBasicBlock(SplitBefore->getIterator());
   if (DTU) {
     SmallPtrSet<BasicBlock *, 8> UniqueSuccessorsOfHead;
     Updates.push_back({DominatorTree::Insert, Head, Tail});
     Updates.reserve(Updates.size() + 2 * succ_size(Tail));
     for (BasicBlock *SuccessorOfHead : successors(Tail))
BranchInst *HeadNewTerm =
       BranchInst::Create(/*ifTrue*/ ThenBlock, /*ifFalse*/ Tail, Cond);
   if (DTU)
     Updates.push_back({DominatorTree::Insert, Head, ThenBlock});
   HeadNewTerm->setMetadata(LLVMContext::MD_prof, BranchWeights);
   ReplaceInstWithInst(HeadOldTerm, HeadNewTerm);
 
   if (DTU)
     DTU->applyUpdates(Updates);
-  else if (DT) {
-    if (DomTreeNode *OldNode = DT->getNode(Head)) {
-      std::vector<DomTreeNode *> Children(OldNode->begin(), OldNode->end());
-
-      DomTreeNode *NewNode = DT->addNewBlock(Tail, Head);
-      for (DomTreeNode *Child : Children)
-        DT->changeImmediateDominator(Child, NewNode);
-
-      // Head dominates ThenBlock.
-      if (CreateThenBlock)
-        DT->addNewBlock(ThenBlock, Head);
-      else
-        DT->changeImmediateDominator(ThenBlock, Head);
-    }
-  }
 
   if (LI) {
     if (Loop *L = LI->getLoopFor(Head)) {
       L->addBasicBlockToLoop(ThenBlock, *LI);
       L->addBasicBlockToLoop(Tail, *LI);
     }
   }
 
   return CheckTerm;
 }
 
-Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
-                                             Instruction *SplitBefore,
-                                             bool Unreachable,
-                                             MDNode *BranchWeights,
-                                             DominatorTree *DT, LoopInfo *LI,
-                                             BasicBlock *ThenBlock) {
-  return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
-                                       BranchWeights,
-                                       /*DTU=*/nullptr, DT, LI, ThenBlock);
-}
-Instruction *llvm::SplitBlockAndInsertIfThen(Value *Cond,
-                                             Instruction *SplitBefore,
-                                             bool Unreachable,
-                                             MDNode *BranchWeights,
-                                             DomTreeUpdater *DTU, LoopInfo *LI,
-                                             BasicBlock *ThenBlock) {
-  return SplitBlockAndInsertIfThenImpl(Cond, SplitBefore, Unreachable,
-                                       BranchWeights, DTU, /*DT=*/nullptr, LI,
-                                       ThenBlock);
-}
-
 void llvm::SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore,
                                          Instruction **ThenTerm,
                                          Instruction **ElseTerm,
                                          MDNode *BranchWeights,
                                          DomTreeUpdater *DTU) {
   BasicBlock *Head = SplitBefore->getParent();
 
   SmallPtrSet<BasicBlock *, 8> UniqueOrigSuccessors;

llvm/lib/Transforms/Utils/LibCallsShrinkWrap.cpp

 //  These partially dead calls are usually results of C++ abstraction penalty
 //  exposed by inlining.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 #include <cmath>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "libcalls-shrinkwrap"
 
 STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted");
 STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted");
 
 namespace {
 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> {
 public:
-  LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DominatorTree *DT)
-      : TLI(TLI), DT(DT){};
+  LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DomTreeUpdater &DTU)
+      : TLI(TLI), DTU(DTU){};
   void visitCallInst(CallInst &CI) { checkCandidate(CI); }
   bool perform() {
     bool Changed = false;
     for (auto &CI : WorkList) {
       LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName()
                         << "\n");
       if (perform(CI)) {
         Changed = true;
private:
   // Create a single condition.
   Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) {
     IRBuilder<> BBBuilder(CI);
     Value *Arg = CI->getArgOperand(0);
     return createCond(BBBuilder, Arg, Cmp, Val);
   }
 
   const TargetLibraryInfo &TLI;
-  DominatorTree *DT;
+  DomTreeUpdater &DTU;
   SmallVector<CallInst *, 16> WorkList;
 };
 } // end anonymous namespace
 
 // Perform the transformation to calls with errno set by domain error.
 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI,
                                                     const LibFunc &Func) {
   Value *Cond = nullptr;

 
 // Wrap conditions that can potentially generate errno to the library call.
 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) {
   assert(Cond != nullptr && "ShrinkWrapCI is not expecting an empty call inst");
   MDNode *BranchWeights =
       MDBuilder(CI->getContext()).createBranchWeights(1, 2000);
 
   Instruction *NewInst =
-      SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, DT);
+      SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, &DTU);
   BasicBlock *CallBB = NewInst->getParent();
   CallBB->setName("cdce.call");
   BasicBlock *SuccBB = CallBB->getSingleSuccessor();
   assert(SuccBB && "The split block should have a single successor");
   SuccBB->setName("cdce.end");
   CI->removeFromParent();
   CI->insertInto(CallBB, CallBB->getFirstInsertionPt());
   LLVM_DEBUG(dbgs() << "== Basic Block After ==");
if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func))
     return true;
   return performCallErrors(CI, Func);
 }
 
 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
                     DominatorTree *DT) {
   if (F.hasFnAttribute(Attribute::OptimizeForSize))
     return false;
-  LibCallsShrinkWrap CCDCE(TLI, DT);
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
+  LibCallsShrinkWrap CCDCE(TLI, DTU);
   CCDCE.visit(F);
-  bool Changed = CCDCE.perform();
-
-// Verify the dominator after we've updated it locally.
-  assert(!DT || DT->verify(DominatorTree::VerificationLevel::Fast));
-  return Changed;
+  return CCDCE.perform();
 }
 
 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F,
                                               FunctionAnalysisManager &FAM) {
   auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
   if (!runImpl(F, TLI, DT))
     return PreservedAnalyses::all();
   auto PA = PreservedAnalyses();
   PA.preserve<DominatorTreeAnalysis>();
   return PA;
 }

polly/lib/CodeGen/BlockGenerators.cpp

 #include "polly/CodeGen/BlockGenerators.h"
 #include "polly/CodeGen/IslExprBuilder.h"
 #include "polly/CodeGen/RuntimeDebugBuilder.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/ISLTools.h"
 #include "polly/Support/ScopHelper.h"
 #include "polly/Support/VirtualInstruction.h"
+#include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "isl/ast.h"
 #include <deque>
 
void BlockGenerator::generateConditionalExecution(
   if (auto *Const = dyn_cast<ConstantInt>(Cond))
     if (Const->isZero())
       return;
 
   BasicBlock *HeadBlock = Builder.GetInsertBlock();
   StringRef BlockName = HeadBlock->getName();
 
   // Generate the conditional block.
+  DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   SplitBlockAndInsertIfThen(Cond, &*Builder.GetInsertPoint(), false, nullptr,
-                            &DT, &LI);
+                            &DTU, &LI);
   BranchInst *Branch = cast<BranchInst>(HeadBlock->getTerminator());
   BasicBlock *ThenBlock = Branch->getSuccessor(0);
   BasicBlock *TailBlock = Branch->getSuccessor(1);
 
   // Assign descriptive names.
   if (auto *CondInst = dyn_cast<Instruction>(Cond))
     CondInst->setName("polly." + Subject + ".cond");
   ThenBlock->setName(BlockName + "." + Subject + ".partial");