[CGP] Avoid repeatedly building DominatorTree causing long compile-time (NFC)

[tejohnson]

Summary

In r354298 a DominatorTree construction was added via new function
combineToUSubWithOverflow, which was subsequently restructured into
replaceMathCmpWithIntrinsic in r354689. We are hitting a very long
compile time due to this repeated construction, once per math cmp in
the function.

We shouldn't need to build the DominatorTree more than once per
function, except when a transformation invalidates it. There is already
a boolean flag that is returned from these methods indicating whether
the DT has been modified. We can simply build the DT once per
Function walk in CodeGenPrepare::runOnFunction, since any time a change
is made we break out of the Function walk and restart it.

I modified the code so that both replaceMathCmpWithIntrinsic as well as
mergeSExts (which was also building a DT) use the DT constructed by the
run method.

From -mllvm -time-passes:
Before this patch: CodeGen Prepare user time is 328s
With this patch: CodeGen Prepare user time is 21s

[spatel]

LGTM
Sorry I didn't see this problem, and thanks for fixing it!
If you have any perf data that you can share, it would be good to include that here or in the commit message. I'm curious if this change recovers all of the compile-time perf or if walking the icmp users is also expensive (although I'm not sure how to make that any faster).

[tejohnson]

In D58995#1419051, @spatel wrote:

LGTM
Sorry I didn't see this problem, and thanks for fixing it!
If you have any perf data that you can share, it would be good to include that here or in the commit message. I'm curious if this change recovers all of the compile-time perf or if walking the icmp users is also expensive (although I'm not sure how to make that any faster).

I don't have data on how much the time was before your patches went in, but I do have some performance data before and after this patch. Will add it in the commit message.

[rafauler]

Hi, do we know whether this patch fully mitigated the issue or if there are still opportunities to improve compile time? I'm using clang trunk from Wednesday March 20th, and I cannot finish the compilation of a large project with ThinLTO and autofdo profile (compilation time was reasonable before, but ballooned to over 10 hours). When I run perf top to see what is happening, I see that the compiler is most of the time in code dealing with dominator trees or in CodeGenPrepare::runOnFunction. I don't remember seeing this issue before (Clang from February). A snapshot of hottest functions while waiting for the never finishing linking:

 1.43%  [.] (anonymous namespace)::CodeGenPrepare::runOnFunction
 1.38%  [.] llvm::TargetLibraryInfoImpl::getLibFunc
  1.19%  [.] llvm::BasicBlock::getTerminator
 1.13%  [.] llvm::DenseMapBase<llvm::DenseMap<llvm::BasicBlock*, llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::InfoRec, llvm::DenseMapInfo<llvm::BasicBlock*>, llvm::detail::DenseMapPair<llvm::BasicBlock*, llvm::DomTreeBuilder::SemiNCAInfo<l
 0.94%  [.] (anonymous namespace)::CodeGenPrepare::optimizeInst
 0.81%  [.] llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::attachNewSubtree
 0.65%  [.] (anonymous namespace)::CodeGenPrepare::optimizeCallInst
0.54%  [.] llvm::Instruction::getSuccessor
 0.51%  [.] llvm::DomTreeBuilder::SemiNCAInfo<llvm::DominatorTreeBase<llvm::BasicBlock, false> >::runDFS<false, bool (*)(llvm::BasicBlock*, llvm::BasicBlock*)>

Just thought about mentioning here in case anyone has ideas, but I'm still figuring out the root cause.

llvm/trunk/lib/CodeGen/CodeGenPrepare.cpp

private:
 
     bool eliminateFallThrough(Function &F);
     bool eliminateMostlyEmptyBlocks(Function &F);
     BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
     bool canMergeBlocks(const BasicBlock *BB, const BasicBlock *DestBB) const;
     void eliminateMostlyEmptyBlock(BasicBlock *BB);
     bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
                                        bool isPreheader);
-    bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT);
-    bool optimizeInst(Instruction *I, bool &ModifiedDT);
+    bool optimizeBlock(BasicBlock &BB, DominatorTree &DT, bool &ModifiedDT);
+    bool optimizeInst(Instruction *I, DominatorTree &DT, bool &ModifiedDT);
     bool optimizeMemoryInst(Instruction *MemoryInst, Value *Addr,
                             Type *AccessTy, unsigned AddrSpace);
     bool optimizeInlineAsmInst(CallInst *CS);
     bool optimizeCallInst(CallInst *CI, bool &ModifiedDT);
     bool optimizeExt(Instruction *&I);
     bool optimizeExtUses(Instruction *I);
     bool optimizeLoadExt(LoadInst *Load);
     bool optimizeSelectInst(SelectInst *SI);
     bool optimizeShuffleVectorInst(ShuffleVectorInst *SVI);
     bool optimizeSwitchInst(SwitchInst *SI);
     bool optimizeExtractElementInst(Instruction *Inst);
     bool dupRetToEnableTailCallOpts(BasicBlock *BB);
     bool placeDbgValues(Function &F);
     bool canFormExtLd(const SmallVectorImpl<Instruction *> &MovedExts,
                       LoadInst *&LI, Instruction *&Inst, bool HasPromoted);
     bool tryToPromoteExts(TypePromotionTransaction &TPT,
                           const SmallVectorImpl<Instruction *> &Exts,
                           SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
                           unsigned CreatedInstsCost = 0);
-    bool mergeSExts(Function &F);
+    bool mergeSExts(Function &F, DominatorTree &DT);
     bool splitLargeGEPOffsets();
     bool performAddressTypePromotion(
         Instruction *&Inst,
         bool AllowPromotionWithoutCommonHeader,
         bool HasPromoted, TypePromotionTransaction &TPT,
         SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
     bool splitBranchCondition(Function &F);
     bool simplifyOffsetableRelocate(Instruction &I);
bool CodeGenPrepare::runOnFunction(Function &F) {
 
   // Split some critical edges where one of the sources is an indirect branch,
   // to help generate sane code for PHIs involving such edges.
   EverMadeChange |= SplitIndirectBrCriticalEdges(F);
 
   bool MadeChange = true;
   while (MadeChange) {
     MadeChange = false;
+    DominatorTree DT(F);
     for (Function::iterator I = F.begin(); I != F.end(); ) {
       BasicBlock *BB = &*I++;
       bool ModifiedDTOnIteration = false;
-      MadeChange |= optimizeBlock(*BB, ModifiedDTOnIteration);
+      MadeChange |= optimizeBlock(*BB, DT, ModifiedDTOnIteration);
 
       // Restart BB iteration if the dominator tree of the Function was changed
       if (ModifiedDTOnIteration)
         break;
     }
     if (EnableTypePromotionMerge && !ValToSExtendedUses.empty())
-      MadeChange |= mergeSExts(F);
+      MadeChange |= mergeSExts(F, DT);
     if (!LargeOffsetGEPMap.empty())
       MadeChange |= splitLargeGEPOffsets();
 
     // Really free removed instructions during promotion.
     for (Instruction *I : RemovedInsts)
       I->deleteValue();
 
     EverMadeChange |= MadeChange;
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI,
   // If, after promotion, these are the same types, this is a noop copy.
   if (SrcVT != DstVT)
     return false;
 
   return SinkCast(CI);
 }
 
 static bool replaceMathCmpWithIntrinsic(BinaryOperator *BO, CmpInst *Cmp,
-                                        Intrinsic::ID IID) {
+                                        Intrinsic::ID IID, DominatorTree &DT) {
   // We allow matching the canonical IR (add X, C) back to (usubo X, -C).
   Value *Arg0 = BO->getOperand(0);
   Value *Arg1 = BO->getOperand(1);
   if (BO->getOpcode() == Instruction::Add &&
       IID == Intrinsic::usub_with_overflow) {
     assert(isa<Constant>(Arg1) && "Unexpected input for usubo");
     Arg1 = ConstantExpr::getNeg(cast<Constant>(Arg1));
   }
 
   Instruction *InsertPt;
   if (BO->hasOneUse() && BO->user_back() == Cmp) {
     // If the math is only used by the compare, insert at the compare to keep
     // the condition in the same block as its users. (CGP aggressively sinks
     // compares to help out SDAG.)
     InsertPt = Cmp;
   } else {
     // The math and compare may be independent instructions. Check dominance to
     // determine the insertion point for the intrinsic.
-    DominatorTree DT(*BO->getFunction());
     bool MathDominates = DT.dominates(BO, Cmp);
     if (!MathDominates && !DT.dominates(Cmp, BO))
       return false;
     InsertPt = MathDominates ? cast<Instruction>(BO) : cast<Instruction>(Cmp);
   }
 
   IRBuilder<> Builder(InsertPt);
   Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
for (User *U : A->users()) {
     }
   }
   return false;
 }
 
 /// Try to combine the compare into a call to the llvm.uadd.with.overflow
 /// intrinsic. Return true if any changes were made.
 static bool combineToUAddWithOverflow(CmpInst *Cmp, const TargetLowering &TLI,
-                                      const DataLayout &DL, bool &ModifiedDT) {
+                                      const DataLayout &DL, DominatorTree &DT,
+                                      bool &ModifiedDT) {
   Value *A, *B;
   BinaryOperator *Add;
   if (!match(Cmp, m_UAddWithOverflow(m_Value(A), m_Value(B), m_BinOp(Add))))
     if (!matchUAddWithOverflowConstantEdgeCases(Cmp, Add))
       return false;
 
   if (!TLI.shouldFormOverflowOp(ISD::UADDO,
                                 TLI.getValueType(DL, Add->getType())))
     return false;
 
   // We don't want to move around uses of condition values this late, so we
   // check if it is legal to create the call to the intrinsic in the basic
   // block containing the icmp.
   if (Add->getParent() != Cmp->getParent() && !Add->hasOneUse())
     return false;
 
-  if (!replaceMathCmpWithIntrinsic(Add, Cmp, Intrinsic::uadd_with_overflow))
+  if (!replaceMathCmpWithIntrinsic(Add, Cmp, Intrinsic::uadd_with_overflow, DT))
     return false;
 
   // Reset callers - do not crash by iterating over a dead instruction.
   ModifiedDT = true;
   return true;
 }
 
 static bool combineToUSubWithOverflow(CmpInst *Cmp, const TargetLowering &TLI,
-                                      const DataLayout &DL, bool &ModifiedDT) {
+                                      const DataLayout &DL, DominatorTree &DT,
+                                      bool &ModifiedDT) {
   // Convert (A u> B) to (A u< B) to simplify pattern matching.
   Value *A = Cmp->getOperand(0), *B = Cmp->getOperand(1);
   ICmpInst::Predicate Pred = Cmp->getPredicate();
   if (Pred == ICmpInst::ICMP_UGT) {
     std::swap(A, B);
     Pred = ICmpInst::ICMP_ULT;
   }
   // Convert special-case: (A == 0) is the same as (A u< 1).
static bool combineToUSubWithOverflow(CmpInst *Cmp, const TargetLowering &TLI,
   }
   if (!Sub)
     return false;
 
   if (!TLI.shouldFormOverflowOp(ISD::USUBO,
                                 TLI.getValueType(DL, Sub->getType())))
     return false;
 
-  if (!replaceMathCmpWithIntrinsic(Sub, Cmp, Intrinsic::usub_with_overflow))
+  if (!replaceMathCmpWithIntrinsic(Sub, Cmp, Intrinsic::usub_with_overflow, DT))
     return false;
 
   // Reset callers - do not crash by iterating over a dead instruction.
   ModifiedDT = true;
   return true;
 }
 
 /// Sink the given CmpInst into user blocks to reduce the number of virtual
if (Cmp->use_empty()) {
     Cmp->eraseFromParent();
     MadeChange = true;
   }
 
   return MadeChange;
 }
 
 static bool optimizeCmp(CmpInst *Cmp, const TargetLowering &TLI,
-                        const DataLayout &DL, bool &ModifiedDT) {
+                        const DataLayout &DL, DominatorTree &DT,
+                        bool &ModifiedDT) {
   if (sinkCmpExpression(Cmp, TLI))
     return true;
 
-  if (combineToUAddWithOverflow(Cmp, TLI, DL, ModifiedDT))
+  if (combineToUAddWithOverflow(Cmp, TLI, DL, DT, ModifiedDT))
     return true;
 
-  if (combineToUSubWithOverflow(Cmp, TLI, DL, ModifiedDT))
+  if (combineToUSubWithOverflow(Cmp, TLI, DL, DT, ModifiedDT))
     return true;
 
   return false;
 }
 
 /// Duplicate and sink the given 'and' instruction into user blocks where it is
 /// used in a compare to allow isel to generate better code for targets where
 /// this operation can be combined.
for (auto I : Exts) {
     }
     // The promotion is profitable.
     Promoted = true;
   }
   return Promoted;
 }
 
 /// Merging redundant sexts when one is dominating the other.
-bool CodeGenPrepare::mergeSExts(Function &F) {
-  DominatorTree DT(F);
+bool CodeGenPrepare::mergeSExts(Function &F, DominatorTree &DT) {
   bool Changed = false;
   for (auto &Entry : ValToSExtendedUses) {
     SExts &Insts = Entry.second;
     SExts CurPts;
     for (Instruction *Inst : Insts) {
       if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
           Inst->getOperand(0) != Entry.first)
         continue;
static bool tryUnmergingGEPsAcrossIndirectBr(GetElementPtrInst *GEPI,
   // After unmerging, verify that GEPIOp is actually only used in SrcBlock (not
   // alive on IndirectBr edges).
   assert(find_if(GEPIOp->users(), [&](User *Usr) {
         return cast<Instruction>(Usr)->getParent() != SrcBlock;
       }) == GEPIOp->users().end() && "GEPIOp is used outside SrcBlock");
   return true;
 }
 
-bool CodeGenPrepare::optimizeInst(Instruction *I, bool &ModifiedDT) {
+bool CodeGenPrepare::optimizeInst(Instruction *I, DominatorTree &DT,
+                                  bool &ModifiedDT) {
   // Bail out if we inserted the instruction to prevent optimizations from
   // stepping on each other's toes.
   if (InsertedInsts.count(I))
     return false;
 
   if (PHINode *P = dyn_cast<PHINode>(I)) {
     // It is possible for very late stage optimizations (such as SimplifyCFG)
     // to introduce PHI nodes too late to be cleaned up.  If we detect such a
if (isa<ZExtInst>(I) || isa<SExtInst>(I)) {
         bool MadeChange = optimizeExt(I);
         return MadeChange | optimizeExtUses(I);
       }
     }
     return false;
   }
 
   if (auto *Cmp = dyn_cast<CmpInst>(I))
-    if (TLI && optimizeCmp(Cmp, *TLI, *DL, ModifiedDT))
+    if (TLI && optimizeCmp(Cmp, *TLI, *DL, DT, ModifiedDT))
       return true;
 
   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
     LI->setMetadata(LLVMContext::MD_invariant_group, nullptr);
     if (TLI) {
       bool Modified = optimizeLoadExt(LI);
       unsigned AS = LI->getPointerAddressSpace();
       Modified |= optimizeMemoryInst(I, I->getOperand(0), LI->getType(), AS);
if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
     if (GEPI->hasAllZeroIndices()) {
       /// The GEP operand must be a pointer, so must its result -> BitCast
       Instruction *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
                                         GEPI->getName(), GEPI);
       NC->setDebugLoc(GEPI->getDebugLoc());
       GEPI->replaceAllUsesWith(NC);
       GEPI->eraseFromParent();
       ++NumGEPsElim;
-      optimizeInst(NC, ModifiedDT);
+      optimizeInst(NC, DT, ModifiedDT);
       return true;
     }
     if (tryUnmergingGEPsAcrossIndirectBr(GEPI, TTI)) {
       return true;
     }
     return false;
   }
 
static bool makeBitReverse(Instruction &I, const DataLayout &DL,
   I.replaceAllUsesWith(LastInst);
   RecursivelyDeleteTriviallyDeadInstructions(&I);
   return true;
 }
 
 // In this pass we look for GEP and cast instructions that are used
 // across basic blocks and rewrite them to improve basic-block-at-a-time
 // selection.
-bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, bool &ModifiedDT) {
+bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, DominatorTree &DT,
+                                   bool &ModifiedDT) {
   SunkAddrs.clear();
   bool MadeChange = false;
 
   CurInstIterator = BB.begin();
   while (CurInstIterator != BB.end()) {
-    MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
+    MadeChange |= optimizeInst(&*CurInstIterator++, DT, ModifiedDT);
     if (ModifiedDT)
       return true;
   }
 
   bool MadeBitReverse = true;
   while (TLI && MadeBitReverse) {
     MadeBitReverse = false;
     for (auto &I : reverse(BB)) {