1 files changed, 67 insertions, 76 deletions

diff --git a/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp b/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
index d35abb92dd08..a99c58b74fb1 100644
--- a/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
+++ b/llvm/lib/Transforms/Instrumentation/ControlHeightReduction.cpp
@@ -221,10 +221,8 @@ class CHRScope {
            "Must be siblings");
     assert(getExitBlock() == Next->getEntryBlock() &&
            "Must be adjacent");
-    for (RegInfo &RI : Next->RegInfos)
-      RegInfos.push_back(RI);
-    for (CHRScope *Sub : Next->Subs)
-      Subs.push_back(Sub);
+    RegInfos.append(Next->RegInfos.begin(), Next->RegInfos.end());
+    Subs.append(Next->Subs.begin(), Next->Subs.end());
   }
 
   void addSub(CHRScope *SubIn) {
@@ -246,37 +244,36 @@ class CHRScope {
     assert(Boundary && "Boundary null");
     assert(RegInfos.begin()->R != Boundary &&
            "Can't be split at beginning");
-    auto BoundaryIt = std::find_if(RegInfos.begin(), RegInfos.end(),
-                                   [&Boundary](const RegInfo& RI) {
-                                     return Boundary == RI.R;
-                                   });
+    auto BoundaryIt = llvm::find_if(
+        RegInfos, [&Boundary](const RegInfo &RI) { return Boundary == RI.R; });
     if (BoundaryIt == RegInfos.end())
       return nullptr;
-    SmallVector<RegInfo, 8> TailRegInfos;
-    SmallVector<CHRScope *, 8> TailSubs;
-    TailRegInfos.insert(TailRegInfos.begin(), BoundaryIt, RegInfos.end());
-    RegInfos.resize(BoundaryIt - RegInfos.begin());
+    ArrayRef<RegInfo> TailRegInfos(BoundaryIt, RegInfos.end());
     DenseSet<Region *> TailRegionSet;
-    for (RegInfo &RI : TailRegInfos)
+    for (const RegInfo &RI : TailRegInfos)
       TailRegionSet.insert(RI.R);
-    for (auto It = Subs.begin(); It != Subs.end(); ) {
-      CHRScope *Sub = *It;
-      assert(Sub && "null Sub");
-      Region *Parent = Sub->getParentRegion();
-      if (TailRegionSet.count(Parent)) {
-        TailSubs.push_back(Sub);
-        It = Subs.erase(It);
-      } else {
-        assert(std::find_if(RegInfos.begin(), RegInfos.end(),
-                            [&Parent](const RegInfo& RI) {
-                              return Parent == RI.R;
-                            }) != RegInfos.end() &&
-               "Must be in head");
-        ++It;
-      }
-    }
+
+    auto TailIt =
+        std::stable_partition(Subs.begin(), Subs.end(), [&](CHRScope *Sub) {
+          assert(Sub && "null Sub");
+          Region *Parent = Sub->getParentRegion();
+          if (TailRegionSet.count(Parent))
+            return false;
+
+          assert(llvm::find_if(RegInfos,
+                               [&Parent](const RegInfo &RI) {
+                                 return Parent == RI.R;
+                               }) != RegInfos.end() &&
+                 "Must be in head");
+          return true;
+        });
+    ArrayRef<CHRScope *> TailSubs(TailIt, Subs.end());
+
     assert(HoistStopMap.empty() && "MapHoistStops must be empty");
-    return new CHRScope(TailRegInfos, TailSubs);
+    auto *Scope = new CHRScope(TailRegInfos, TailSubs);
+    RegInfos.erase(BoundaryIt, RegInfos.end());
+    Subs.erase(TailIt, Subs.end());
+    return Scope;
   }
 
   bool contains(Instruction *I) const {
@@ -314,9 +311,9 @@ class CHRScope {
   HoistStopMapTy HoistStopMap;
 
  private:
-  CHRScope(SmallVector<RegInfo, 8> &RegInfosIn,
-           SmallVector<CHRScope *, 8> &SubsIn)
-    : RegInfos(RegInfosIn), Subs(SubsIn), BranchInsertPoint(nullptr) {}
+   CHRScope(ArrayRef<RegInfo> RegInfosIn, ArrayRef<CHRScope *> SubsIn)
+       : RegInfos(RegInfosIn.begin(), RegInfosIn.end()),
+         Subs(SubsIn.begin(), SubsIn.end()), BranchInsertPoint(nullptr) {}
 };
 
 class CHR {
@@ -340,8 +337,7 @@ class CHR {
 
   void findScopes(SmallVectorImpl<CHRScope *> &Output) {
     Region *R = RI.getTopLevelRegion();
-    CHRScope *Scope = findScopes(R, nullptr, nullptr, Output);
-    if (Scope) {
+    if (CHRScope *Scope = findScopes(R, nullptr, nullptr, Output)) {
       Output.push_back(Scope);
     }
   }
@@ -514,39 +510,36 @@ static bool isHoistable(Instruction *I, DominatorTree &DT) {
 // first-region entry block) or the (hoistable or unhoistable) base values that
 // are defined outside (including the first-region entry block) of the
 // scope. The returned set doesn't include constants.
-static std::set<Value *> getBaseValues(
-    Value *V, DominatorTree &DT,
-    DenseMap<Value *, std::set<Value *>> &Visited) {
-  if (Visited.count(V)) {
-    return Visited[V];
+static const std::set<Value *> &
+getBaseValues(Value *V, DominatorTree &DT,
+              DenseMap<Value *, std::set<Value *>> &Visited) {
+  auto It = Visited.find(V);
+  if (It != Visited.end()) {
+    return It->second;
   }
   std::set<Value *> Result;
   if (auto *I = dyn_cast<Instruction>(V)) {
-    // We don't stop at a block that's not in the Scope because we would miss some
-    // instructions that are based on the same base values if we stop there.
+    // We don't stop at a block that's not in the Scope because we would miss
+    // some instructions that are based on the same base values if we stop
+    // there.
     if (!isHoistable(I, DT)) {
       Result.insert(I);
-      Visited.insert(std::make_pair(V, Result));
-      return Result;
+      return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
     }
     // I is hoistable above the Scope.
     for (Value *Op : I->operands()) {
-      std::set<Value *> OpResult = getBaseValues(Op, DT, Visited);
+      const std::set<Value *> &OpResult = getBaseValues(Op, DT, Visited);
       Result.insert(OpResult.begin(), OpResult.end());
     }
-    Visited.insert(std::make_pair(V, Result));
-    return Result;
+    return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
   }
   if (isa<Argument>(V)) {
     Result.insert(V);
-    Visited.insert(std::make_pair(V, Result));
-    return Result;
   }
   // We don't include others like constants because those won't lead to any
   // chance of folding of conditions (eg two bit checks merged into one check)
   // after CHR.
-  Visited.insert(std::make_pair(V, Result));
-  return Result;  // empty
+  return Visited.insert(std::make_pair(V, std::move(Result))).first->second;
 }
 
 // Return true if V is already hoisted or can be hoisted (along with its
@@ -560,8 +553,9 @@ checkHoistValue(Value *V, Instruction *InsertPoint, DominatorTree &DT,
                 DenseMap<Instruction *, bool> &Visited) {
   assert(InsertPoint && "Null InsertPoint");
   if (auto *I = dyn_cast<Instruction>(V)) {
-    if (Visited.count(I)) {
-      return Visited[I];
+    auto It = Visited.find(I);
+    if (It != Visited.end()) {
+      return It->second;
     }
     assert(DT.getNode(I->getParent()) && "DT must contain I's parent block");
     assert(DT.getNode(InsertPoint->getParent()) && "DT must contain Destination");
@@ -1094,11 +1088,11 @@ static bool shouldSplit(Instruction *InsertPoint,
     std::set<Value *> PrevBases, Bases;
     DenseMap<Value *, std::set<Value *>> Visited;
     for (Value *V : PrevConditionValues) {
-      std::set<Value *> BaseValues = getBaseValues(V, DT, Visited);
+      const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
       PrevBases.insert(BaseValues.begin(), BaseValues.end());
     }
     for (Value *V : ConditionValues) {
-      std::set<Value *> BaseValues = getBaseValues(V, DT, Visited);
+      const std::set<Value *> &BaseValues = getBaseValues(V, DT, Visited);
       Bases.insert(BaseValues.begin(), BaseValues.end());
     }
     CHR_DEBUG(
@@ -1111,10 +1105,9 @@ static bool shouldSplit(Instruction *InsertPoint,
           dbgs() << *V << ", ";
         }
         dbgs() << "\n");
-    std::set<Value *> Intersection;
-    std::set_intersection(PrevBases.begin(), PrevBases.end(),
-                          Bases.begin(), Bases.end(),
-                          std::inserter(Intersection, Intersection.begin()));
+    std::vector<Value *> Intersection;
+    std::set_intersection(PrevBases.begin(), PrevBases.end(), Bases.begin(),
+                          Bases.end(), std::back_inserter(Intersection));
     if (Intersection.empty()) {
       // Empty intersection, split.
       CHR_DEBUG(dbgs() << "Split. Intersection empty\n");
@@ -1439,7 +1432,7 @@ void CHR::setCHRRegions(CHRScope *Scope, CHRScope *OutermostScope) {
     setCHRRegions(Sub, OutermostScope);
 }
 
-bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) {
+static bool CHRScopeSorter(CHRScope *Scope1, CHRScope *Scope2) {
   return Scope1->RegInfos[0].R->getDepth() < Scope2->RegInfos[0].R->getDepth();
 }
 
@@ -1578,26 +1571,24 @@ static bool negateICmpIfUsedByBranchOrSelectOnly(ICmpInst *ICmp,
 static void insertTrivialPHIs(CHRScope *Scope,
                               BasicBlock *EntryBlock, BasicBlock *ExitBlock,
                               DenseSet<PHINode *> &TrivialPHIs) {
-  DenseSet<BasicBlock *> BlocksInScopeSet;
-  SmallVector<BasicBlock *, 8> BlocksInScopeVec;
+  SmallSetVector<BasicBlock *, 8> BlocksInScope;
   for (RegInfo &RI : Scope->RegInfos) {
     for (BasicBlock *BB : RI.R->blocks()) { // This includes the blocks in the
                                             // sub-Scopes.
-      BlocksInScopeSet.insert(BB);
-      BlocksInScopeVec.push_back(BB);
+      BlocksInScope.insert(BB);
     }
   }
-  CHR_DEBUG(
-      dbgs() << "Inserting redudant phis\n";
-      for (BasicBlock *BB : BlocksInScopeVec) {
-        dbgs() << "BlockInScope " << BB->getName() << "\n";
-      });
-  for (BasicBlock *BB : BlocksInScopeVec) {
+  CHR_DEBUG({
+    dbgs() << "Inserting redundant phis\n";
+    for (BasicBlock *BB : BlocksInScope)
+      dbgs() << "BlockInScope " << BB->getName() << "\n";
+  });
+  for (BasicBlock *BB : BlocksInScope) {
     for (Instruction &I : *BB) {
       SmallVector<Instruction *, 8> Users;
       for (User *U : I.users()) {
         if (auto *UI = dyn_cast<Instruction>(U)) {
-          if (BlocksInScopeSet.count(UI->getParent()) == 0 &&
+          if (BlocksInScope.count(UI->getParent()) == 0 &&
               // Unless there's already a phi for I at the exit block.
               !(isa<PHINode>(UI) && UI->getParent() == ExitBlock)) {
             CHR_DEBUG(dbgs() << "V " << I << "\n");
@@ -1874,9 +1865,10 @@ void CHR::fixupBranchesAndSelects(CHRScope *Scope,
         << " branches or selects";
   });
   MergedBR->setCondition(MergedCondition);
-  SmallVector<uint32_t, 2> Weights;
-  Weights.push_back(static_cast<uint32_t>(CHRBranchBias.scale(1000)));
-  Weights.push_back(static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)));
+  uint32_t Weights[] = {
+      static_cast<uint32_t>(CHRBranchBias.scale(1000)),
+      static_cast<uint32_t>(CHRBranchBias.getCompl().scale(1000)),
+  };
   MDBuilder MDB(F.getContext());
   MergedBR->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
   CHR_DEBUG(dbgs() << "CHR branch bias " << Weights[0] << ":" << Weights[1]
@@ -2101,8 +2093,7 @@ PreservedAnalyses ControlHeightReductionPass::run(
   auto &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
   auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);
   auto &MAMProxy = FAM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
-  auto &MAM = MAMProxy.getManager();
-  auto &PSI = *MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
+  auto &PSI = *MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
   auto &RI = FAM.getResult<RegionInfoAnalysis>(F);
   auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
   bool Changed = CHR(F, BFI, DT, PSI, RI, ORE).run();