diff --git a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h --- a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h @@ -121,6 +121,7 @@ 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 @@ -130,6 +131,15 @@ 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 &Probs); + static BranchProbability getBranchProbStackProtector(bool IsLikely) { static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); return IsLikely ? LikelyProb : LikelyProb.getCompl(); diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -251,10 +251,13 @@ if (UnreachableEdges.empty()) return false; + SmallVector EdgeProbabilities( + BB->getTerminator()->getNumSuccessors(), BranchProbability::getUnknown()); if (ReachableEdges.empty()) { BranchProbability Prob(1, UnreachableEdges.size()); for (unsigned SuccIdx : UnreachableEdges) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -264,10 +267,11 @@ ReachableEdges.size(); for (unsigned SuccIdx : UnreachableEdges) - setEdgeProbability(BB, SuccIdx, UnreachableProb); + EdgeProbabilities[SuccIdx] = UnreachableProb; for (unsigned SuccIdx : ReachableEdges) - setEdgeProbability(BB, SuccIdx, ReachableProb); + EdgeProbabilities[SuccIdx] = ReachableProb; + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -363,8 +367,7 @@ } } - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - setEdgeProbability(BB, i, BP[i]); + setEdgeProbability(BB, BP); return true; } @@ -397,10 +400,13 @@ if (ColdEdges.empty()) return false; + SmallVector EdgeProbabilities( + BB->getTerminator()->getNumSuccessors(), BranchProbability::getUnknown()); if (NormalEdges.empty()) { BranchProbability Prob(1, ColdEdges.size()); for (unsigned SuccIdx : ColdEdges) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -412,10 +418,11 @@ (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size())); for (unsigned SuccIdx : ColdEdges) - setEdgeProbability(BB, SuccIdx, ColdProb); + EdgeProbabilities[SuccIdx] = ColdProb; for (unsigned SuccIdx : NormalEdges) - setEdgeProbability(BB, SuccIdx, NormalProb); + EdgeProbabilities[SuccIdx] = NormalProb; + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -438,19 +445,21 @@ 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(TakenIdx, NonTakenIdx); + std::swap(TakenProb, UntakenProb); - BranchProbability TakenProb(PH_TAKEN_WEIGHT, - PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT); - setEdgeProbability(BB, TakenIdx, TakenProb); - setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); + setEdgeProbability( + BB, SmallVector({TakenProb, UntakenProb})); return true; } @@ -647,18 +656,20 @@ (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) + (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT); + SmallVector 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) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; } if (uint32_t numInEdges = InEdges.size()) { BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom); auto Prob = TakenProb / numInEdges; for (unsigned SuccIdx : InEdges) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; } if (uint32_t numExitingEdges = ExitingEdges.size()) { @@ -666,7 +677,7 @@ Denom); auto Prob = NotTakenProb / numExitingEdges; for (unsigned SuccIdx : ExitingEdges) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; } if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) { @@ -674,9 +685,10 @@ Denom); auto Prob = UnlikelyProb / numUnlikelyEdges; for (unsigned SuccIdx : UnlikelyEdges) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; } + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -787,15 +799,15 @@ return false; } - unsigned TakenIdx = 0, NonTakenIdx = 1; - - if (!isProb) - std::swap(TakenIdx, NonTakenIdx); - BranchProbability TakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); - setEdgeProbability(BB, TakenIdx, TakenProb); - setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); + BranchProbability UntakenProb(ZH_NONTAKEN_WEIGHT, + ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT); + if (!isProb) + std::swap(TakenProb, UntakenProb); + + setEdgeProbability( + BB, SmallVector({TakenProb, UntakenProb})); return true; } @@ -830,14 +842,13 @@ return false; } - unsigned TakenIdx = 0, NonTakenIdx = 1; - + BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight); + BranchProbability UntakenProb(NontakenWeight, TakenWeight + NontakenWeight); if (!isProb) - std::swap(TakenIdx, NonTakenIdx); + std::swap(TakenProb, UntakenProb); - BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight); - setEdgeProbability(BB, TakenIdx, TakenProb); - setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl()); + setEdgeProbability( + BB, SmallVector({TakenProb, UntakenProb})); return true; } @@ -848,8 +859,8 @@ BranchProbability TakenProb(IH_TAKEN_WEIGHT, IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT); - setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb); - setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl()); + setEdgeProbability( + BB, SmallVector({TakenProb, TakenProb.getCompl()})); return true; } @@ -962,6 +973,28 @@ << "\n"); } +/// Set the edge probability for all edges at once. +void BranchProbabilityInfo::setEdgeProbability( + const BasicBlock *Src, const SmallVectorImpl &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, diff --git a/llvm/lib/Transforms/Scalar/JumpThreading.cpp b/llvm/lib/Transforms/Scalar/JumpThreading.cpp --- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -2513,8 +2513,7 @@ } // Update edge probabilities in BPI. - for (int I = 0, E = BBSuccProbs.size(); I < E; I++) - BPI->setEdgeProbability(BB, I, BBSuccProbs[I]); + BPI->setEdgeProbability(BB, BBSuccProbs); // Update the profile metadata as well. // diff --git a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -401,9 +401,7 @@ BasicBlock *BodyBlock = Target->splitBasicBlock(FirstNonPHI, ".split"); if (ShouldUpdateAnalysis) { // Copy the BFI/BPI from Target to BodyBlock. - for (unsigned I = 0, E = BodyBlock->getTerminator()->getNumSuccessors(); - I < E; ++I) - BPI->setEdgeProbability(BodyBlock, I, EdgeProbabilities[I]); + BPI->setEdgeProbability(BodyBlock, EdgeProbabilities); BFI->setBlockFreq(BodyBlock, BFI->getBlockFreq(Target).getFrequency()); } // It's possible Target was its own successor through an indirectbr. diff --git a/llvm/lib/Transforms/Utils/CodeExtractor.cpp b/llvm/lib/Transforms/Utils/CodeExtractor.cpp --- a/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ b/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -1364,6 +1364,9 @@ // Block Frequency distribution with dummy node. Distribution BranchDist; + SmallVector 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); @@ -1371,12 +1374,14 @@ if (ExitFreq != 0) BranchDist.addExit(ExitNode, ExitFreq); else - BPI->setEdgeProbability(CodeReplacer, i, BranchProbability::getZero()); + EdgeProbabilities[i] = BranchProbability::getZero(); } // Check for no total weight. - if (BranchDist.Total == 0) + if (BranchDist.Total == 0) { + BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities); return; + } // Normalize the distribution so that they can fit in unsigned. BranchDist.normalize(); @@ -1388,8 +1393,9 @@ // Get the weight and update the current BFI. BranchWeights[Weight.TargetNode.Index] = Weight.Amount; BranchProbability BP(Weight.Amount, BranchDist.Total); - BPI->setEdgeProbability(CodeReplacer, Weight.TargetNode.Index, BP); + EdgeProbabilities[Weight.TargetNode.Index] = BP; } + BPI->setEdgeProbability(CodeReplacer, EdgeProbabilities); TI->setMetadata( LLVMContext::MD_prof, MDBuilder(TI->getContext()).createBranchWeights(BranchWeights));