reland e5581df60a35 [SimplifyCFG] accumulate bonus insts cost

Fixed compile time increase due to always constructing LocalCostTracker.
Now only construct LocalCostTracker when needed.

1 files changed, 48 insertions, 18 deletions

diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
index fcdd858..7008f9b 100644
--- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -207,6 +207,21 @@ STATISTIC(NumInvokes,
 STATISTIC(NumInvokesMerged, "Number of invokes that were merged together");
 STATISTIC(NumInvokeSetsFormed, "Number of invoke sets that were formed");
 
+namespace llvm {
+
+void SimplifyCFGCostTracker::updateNumBonusInsts(BasicBlock *BB,
+                                                 unsigned InstCount) {
+  auto Loc = NumBonusInsts.find(BB);
+  if (Loc == NumBonusInsts.end())
+    Loc = NumBonusInsts.insert({BB, 0}).first;
+  Loc->second = Loc->second + InstCount;
+}
+unsigned SimplifyCFGCostTracker::getNumBonusInsts(BasicBlock *BB) {
+  return NumBonusInsts.lookup(BB);
+}
+
+} // namespace llvm
+
 namespace {
 
 // The first field contains the value that the switch produces when a certain
@@ -243,6 +258,10 @@ class SimplifyCFGOpt {
   ArrayRef<WeakVH> LoopHeaders;
   const SimplifyCFGOptions &Options;
   bool Resimplify;
+  // Accumulates number of bonus instructions due to merging basic blocks
+  // of common destination.
+  SimplifyCFGCostTracker *CostTracker;
+  std::unique_ptr<SimplifyCFGCostTracker> LocalCostTracker;
 
   Value *isValueEqualityComparison(Instruction *TI);
   BasicBlock *GetValueEqualityComparisonCases(
@@ -286,8 +305,15 @@ class SimplifyCFGOpt {
 public:
   SimplifyCFGOpt(const TargetTransformInfo &TTI, DomTreeUpdater *DTU,
                  const DataLayout &DL, ArrayRef<WeakVH> LoopHeaders,
-                 const SimplifyCFGOptions &Opts)
+                 const SimplifyCFGOptions &Opts,
+                 SimplifyCFGCostTracker *CostTracker_)
       : TTI(TTI), DTU(DTU), DL(DL), LoopHeaders(LoopHeaders), Options(Opts) {
+    // Cannot do this with member initializer list since LocalCostTracker is not
+    // initialized there yet.
+    CostTracker = CostTracker_
+                      ? CostTracker_
+                      : (LocalCostTracker.reset(new SimplifyCFGCostTracker()),
+                         LocalCostTracker.get());
     assert((!DTU || !DTU->hasPostDomTree()) &&
            "SimplifyCFG is not yet capable of maintaining validity of a "
            "PostDomTree, so don't ask for it.");
@@ -3624,8 +3650,9 @@ static bool isVectorOp(Instruction &I) {
 /// If this basic block is simple enough, and if a predecessor branches to us
 /// and one of our successors, fold the block into the predecessor and use
 /// logical operations to pick the right destination.
-bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
-                                  MemorySSAUpdater *MSSAU,
+bool llvm::FoldBranchToCommonDest(BranchInst *BI,
+                                  SimplifyCFGCostTracker &CostTracker,
+                                  DomTreeUpdater *DTU, MemorySSAUpdater *MSSAU,
                                   const TargetTransformInfo *TTI,
                                   unsigned BonusInstThreshold) {
   // If this block ends with an unconditional branch,
@@ -3697,7 +3724,6 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
   // as "bonus instructions", and only allow this transformation when the
   // number of the bonus instructions we'll need to create when cloning into
   // each predecessor does not exceed a certain threshold.
-  unsigned NumBonusInsts = 0;
   bool SawVectorOp = false;
   const unsigned PredCount = Preds.size();
   for (Instruction &I : *BB) {
@@ -3716,12 +3742,13 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
     // predecessor. Ignore free instructions.
     if (!TTI || TTI->getInstructionCost(&I, CostKind) !=
                     TargetTransformInfo::TCC_Free) {
-      NumBonusInsts += PredCount;
-
-      // Early exits once we reach the limit.
-      if (NumBonusInsts >
-          BonusInstThreshold * BranchFoldToCommonDestVectorMultiplier)
-        return false;
+      for (auto PredBB : Preds) {
+        CostTracker.updateNumBonusInsts(PredBB, PredCount);
+        // Early exits once we reach the limit.
+        if (CostTracker.getNumBonusInsts(PredBB) >
+            BonusInstThreshold * BranchFoldToCommonDestVectorMultiplier)
+          return false;
+      }
     }
 
     auto IsBCSSAUse = [BB, &I](Use &U) {
@@ -3735,10 +3762,12 @@ bool llvm::FoldBranchToCommonDest(BranchInst *BI, DomTreeUpdater *DTU,
     if (!all_of(I.uses(), IsBCSSAUse))
       return false;
   }
-  if (NumBonusInsts >
-      BonusInstThreshold *
-          (SawVectorOp ? BranchFoldToCommonDestVectorMultiplier : 1))
-    return false;
+  for (auto PredBB : Preds) {
+    if (CostTracker.getNumBonusInsts(PredBB) >
+        BonusInstThreshold *
+            (SawVectorOp ? BranchFoldToCommonDestVectorMultiplier : 1))
+      return false;
+  }
 
   // Ok, we have the budget. Perform the transformation.
   for (BasicBlock *PredBlock : Preds) {
@@ -6889,7 +6918,7 @@ bool SimplifyCFGOpt::simplifyUncondBranch(BranchInst *BI,
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
-  if (FoldBranchToCommonDest(BI, DTU, /*MSSAU=*/nullptr, &TTI,
+  if (FoldBranchToCommonDest(BI, *CostTracker, DTU, /*MSSAU=*/nullptr, &TTI,
                              Options.BonusInstThreshold))
     return requestResimplify();
   return false;
@@ -6958,7 +6987,7 @@ bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
-  if (FoldBranchToCommonDest(BI, DTU, /*MSSAU=*/nullptr, &TTI,
+  if (FoldBranchToCommonDest(BI, *CostTracker, DTU, /*MSSAU=*/nullptr, &TTI,
                              Options.BonusInstThreshold))
     return requestResimplify();
 
@@ -7257,8 +7286,9 @@ bool SimplifyCFGOpt::run(BasicBlock *BB) {
 
 bool llvm::simplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI,
                        DomTreeUpdater *DTU, const SimplifyCFGOptions &Options,
-                       ArrayRef<WeakVH> LoopHeaders) {
+                       ArrayRef<WeakVH> LoopHeaders,
+                       SimplifyCFGCostTracker *CostTracker) {
   return SimplifyCFGOpt(TTI, DTU, BB->getModule()->getDataLayout(), LoopHeaders,
-                        Options)
+                        Options, CostTracker)
       .run(BB);
 }