Revert "[BrachProbablityInfo] Set edge probabilities at once. NFC."
authorReid Kleckner <rnk@google.com>
Wed, 13 May 2020 15:23:09 +0000 (08:23 -0700)
committerReid Kleckner <rnk@google.com>
Wed, 13 May 2020 15:23:09 +0000 (08:23 -0700)
This reverts commit eef95f2746c3347b8dad19091ffb82a88d73acd3.

The new assertion about branch propability sums does not hold.

llvm/include/llvm/Analysis/BranchProbabilityInfo.h
llvm/lib/Analysis/BranchProbabilityInfo.cpp
llvm/lib/Transforms/Scalar/JumpThreading.cpp
llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp
llvm/lib/Transforms/Utils/CodeExtractor.cpp

index 3e72afb..4c538d8 100644 (file)
@@ -121,7 +121,6 @@ public:
   raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src,
                                     const BasicBlock *Dst) const;
 
-protected:
   /// Set the raw edge probability for the given edge.
   ///
   /// This allows a pass to explicitly set the edge probability for an edge. It
@@ -131,15 +130,6 @@ protected:
   void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors,
                           BranchProbability Prob);
 
-public:
-  /// Set the raw probabilities for all edges from the given block.
-  ///
-  /// This allows a pass to explicitly set edge probabilities for a block. It
-  /// can be used when updating the CFG to update the branch probability
-  /// information.
-  void setEdgeProbability(const BasicBlock *Src,
-                          const SmallVectorImpl<BranchProbability> &Probs);
-
   static BranchProbability getBranchProbStackProtector(bool IsLikely) {
     static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
     return IsLikely ? LikelyProb : LikelyProb.getCompl();
index ff13c07..d33af83 100644 (file)
@@ -251,13 +251,10 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
   if (UnreachableEdges.empty())
     return false;
 
-  SmallVector<BranchProbability, 4> EdgeProbabilities(
-      BB->getTerminator()->getNumSuccessors(), BranchProbability::getUnknown());
   if (ReachableEdges.empty()) {
     BranchProbability Prob(1, UnreachableEdges.size());
     for (unsigned SuccIdx : UnreachableEdges)
-      EdgeProbabilities[SuccIdx] = Prob;
-    setEdgeProbability(BB, EdgeProbabilities);
+      setEdgeProbability(BB, SuccIdx, Prob);
     return true;
   }
 
@@ -267,11 +264,10 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
       ReachableEdges.size();
 
   for (unsigned SuccIdx : UnreachableEdges)
-    EdgeProbabilities[SuccIdx] = UnreachableProb;
+    setEdgeProbability(BB, SuccIdx, UnreachableProb);
   for (unsigned SuccIdx : ReachableEdges)
-    EdgeProbabilities[SuccIdx] = ReachableProb;
+    setEdgeProbability(BB, SuccIdx, ReachableProb);
 
-  setEdgeProbability(BB, EdgeProbabilities);
   return true;
 }
 
@@ -367,7 +363,8 @@ bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
     }
   }
 
-  setEdgeProbability(BB, BP);
+  for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
+    setEdgeProbability(BB, i, BP[i]);
 
   return true;
 }
@@ -400,13 +397,10 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
   if (ColdEdges.empty())
     return false;
 
-  SmallVector<BranchProbability, 4> EdgeProbabilities(
-      BB->getTerminator()->getNumSuccessors(), BranchProbability::getUnknown());
   if (NormalEdges.empty()) {
     BranchProbability Prob(1, ColdEdges.size());
     for (unsigned SuccIdx : ColdEdges)
-      EdgeProbabilities[SuccIdx] = Prob;
-    setEdgeProbability(BB, EdgeProbabilities);
+      setEdgeProbability(BB, SuccIdx, Prob);
     return true;
   }
 
@@ -418,11 +412,10 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
       (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
 
   for (unsigned SuccIdx : ColdEdges)
-    EdgeProbabilities[SuccIdx] = ColdProb;
+    setEdgeProbability(BB, SuccIdx, ColdProb);
   for (unsigned SuccIdx : NormalEdges)
-    EdgeProbabilities[SuccIdx] = NormalProb;
+    setEdgeProbability(BB, SuccIdx, NormalProb);
 
-  setEdgeProbability(BB, EdgeProbabilities);
   return true;
 }
 
@@ -445,21 +438,19 @@ bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
 
   assert(CI->getOperand(1)->getType()->isPointerTy());
 
-  BranchProbability TakenProb(PH_TAKEN_WEIGHT,
-                              PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
-  BranchProbability UntakenProb(PH_NONTAKEN_WEIGHT,
-                                PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
-
   // p != 0   ->   isProb = true
   // p == 0   ->   isProb = false
   // p != q   ->   isProb = true
   // p == q   ->   isProb = false;
+  unsigned TakenIdx = 0, NonTakenIdx = 1;
   bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
   if (!isProb)
-    std::swap(TakenProb, UntakenProb);
+    std::swap(TakenIdx, NonTakenIdx);
 
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+  BranchProbability TakenProb(PH_TAKEN_WEIGHT,
+                              PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
+  setEdgeProbability(BB, TakenIdx, TakenProb);
+  setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
   return true;
 }
 
@@ -656,20 +647,18 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
                    (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) +
                    (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
 
-  SmallVector<BranchProbability, 4> EdgeProbabilities(
-      BB->getTerminator()->getNumSuccessors(), BranchProbability::getUnknown());
   if (uint32_t numBackEdges = BackEdges.size()) {
     BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
     auto Prob = TakenProb / numBackEdges;
     for (unsigned SuccIdx : BackEdges)
-      EdgeProbabilities[SuccIdx] = Prob;
+      setEdgeProbability(BB, SuccIdx, Prob);
   }
 
   if (uint32_t numInEdges = InEdges.size()) {
     BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
     auto Prob = TakenProb / numInEdges;
     for (unsigned SuccIdx : InEdges)
-      EdgeProbabilities[SuccIdx] = Prob;
+      setEdgeProbability(BB, SuccIdx, Prob);
   }
 
   if (uint32_t numExitingEdges = ExitingEdges.size()) {
@@ -677,7 +666,7 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
                                                        Denom);
     auto Prob = NotTakenProb / numExitingEdges;
     for (unsigned SuccIdx : ExitingEdges)
-      EdgeProbabilities[SuccIdx] = Prob;
+      setEdgeProbability(BB, SuccIdx, Prob);
   }
 
   if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
@@ -685,10 +674,9 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
                                                        Denom);
     auto Prob = UnlikelyProb / numUnlikelyEdges;
     for (unsigned SuccIdx : UnlikelyEdges)
-      EdgeProbabilities[SuccIdx] = Prob;
+      setEdgeProbability(BB, SuccIdx, Prob);
   }
 
-  setEdgeProbability(BB, EdgeProbabilities);
   return true;
 }
 
@@ -799,15 +787,15 @@ bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
     return false;
   }
 
-  BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
-                              ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
-  BranchProbability UntakenProb(ZH_NONTAKEN_WEIGHT,
-                                ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
+  unsigned TakenIdx = 0, NonTakenIdx = 1;
+
   if (!isProb)
-    std::swap(TakenProb, UntakenProb);
+    std::swap(TakenIdx, NonTakenIdx);
 
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+  BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
+                              ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
+  setEdgeProbability(BB, TakenIdx, TakenProb);
+  setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
   return true;
 }
 
@@ -842,13 +830,14 @@ bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
     return false;
   }
 
-  BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight);
-  BranchProbability UntakenProb(NontakenWeight, TakenWeight + NontakenWeight);
+  unsigned TakenIdx = 0, NonTakenIdx = 1;
+
   if (!isProb)
-    std::swap(TakenProb, UntakenProb);
+    std::swap(TakenIdx, NonTakenIdx);
 
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, UntakenProb}));
+  BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight);
+  setEdgeProbability(BB, TakenIdx, TakenProb);
+  setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
   return true;
 }
 
@@ -859,8 +848,8 @@ bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
 
   BranchProbability TakenProb(IH_TAKEN_WEIGHT,
                               IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
-  setEdgeProbability(
-      BB, SmallVector<BranchProbability, 2>({TakenProb, TakenProb.getCompl()}));
+  setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
+  setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
   return true;
 }
 
@@ -973,28 +962,6 @@ void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
                     << "\n");
 }
 
-/// Set the edge probability for all edges at once.
-void BranchProbabilityInfo::setEdgeProbability(
-    const BasicBlock *Src, const SmallVectorImpl<BranchProbability> &Probs) {
-  assert(Src->getTerminator()->getNumSuccessors() == Probs.size());
-  if (Probs.size() == 0)
-    return; // Nothing to set.
-
-  uint64_t TotalNumerator = 0;
-  for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {
-    setEdgeProbability(Src, SuccIdx, Probs[SuccIdx]);
-    TotalNumerator += Probs[SuccIdx].getNumerator();
-  }
-
-  // Because of rounding errors the total probability cannot be checked to be
-  // 1.0 exactly. That is TotalNumerator == BranchProbability::getDenominator.
-  // Instead, every single probability in Probs must be as accurate as possible.
-  // This results in error 1/denominator at most, thus the total absolute error
-  // should be within Probs.size / BranchProbability::getDenominator.
-  assert(TotalNumerator <= BranchProbability::getDenominator() + Probs.size());
-  assert(TotalNumerator >= BranchProbability::getDenominator() - Probs.size());
-}
-
 raw_ostream &
 BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
                                             const BasicBlock *Src,
index 146ee13..c59b2ce 100644 (file)
@@ -2513,7 +2513,8 @@ void JumpThreadingPass::UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB,
   }
 
   // Update edge probabilities in BPI.
-  BPI->setEdgeProbability(BB, BBSuccProbs);
+  for (int I = 0, E = BBSuccProbs.size(); I < E; I++)
+    BPI->setEdgeProbability(BB, I, BBSuccProbs[I]);
 
   // Update the profile metadata as well.
   //
index 9c995de..f34d098 100644 (file)
@@ -401,7 +401,9 @@ bool llvm::SplitIndirectBrCriticalEdges(Function &F,
     BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split");
     if (ShouldUpdateAnalysis) {
       // Copy the BFI/BPI from Target to BodyBlock.
-      BPI->setEdgeProbability(BodyBlock, EdgeProbabilities);
+      for (unsigned I = 0, E = BodyBlock->getTerminator()->getNumSuccessors();
+           I < E; ++I)
+        BPI->setEdgeProbability(BodyBlock, I, EdgeProbabilities[I]);
       BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency());
     }
     // It's possible Target was its own successor through an indirectbr.
index a7d5ef5..e8154ec 100644 (file)
@@ -1364,9 +1364,6 @@ void CodeExtractor::calculateNewCallTerminatorWeights(
   // Block Frequency distribution with dummy node.
   Distribution BranchDist;
 
-  SmallVector<BranchProbability, 4> EdgeProbabilities(
-      TI->getNumSuccessors(), BranchProbability::getUnknown());
-
   // Add each of the frequencies of the successors.
   for (unsigned i = 0, e = TI->getNumSuccessors(); i < e; ++i) {
     BlockNode ExitNode(i);
@@ -1374,14 +1371,12 @@ void CodeExtractor::calculateNewCallTerminatorWeights(
     if (ExitFreq != 0)
       BranchDist.addExit(ExitNode, ExitFreq);
     else
-      EdgeProbabilities[i] = BranchProbability::getZero();
+      BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero());
   }
 
   // Check for no total weight.
-  if (BranchDist.Total == 0) {
-    BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
+  if (BranchDist.Total == 0)
     return;
-  }
 
   // Normalize the distribution so that they can fit in unsigned.
   BranchDist.normalize();
@@ -1393,9 +1388,8 @@ void CodeExtractor::calculateNewCallTerminatorWeights(
     // Get the weight and update the current BFI.
     BranchWeights[Weight.TargetNode.Index] = Weight.Amount;
     BranchProbability BP(Weight.Amount, BranchDist.Total);
-    EdgeProbabilities[Weight.TargetNode.Index] = BP;
+    BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP);
   }
-  BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities);
   TI->setMetadata(
       LLVMContext::MD_prof,
       MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));