From eef95f2746c3347b8dad19091ffb82a88d73acd3 Mon Sep 17 00:00:00 2001 From: Yevgeny Rouban Date: Wed, 13 May 2020 12:14:06 +0700 Subject: [PATCH] [BrachProbablityInfo] Set edge probabilities at once. NFC. Hide the method that allows setting probability for particular edge and introduce a public method that sets probabilities for all outgoing edges at once. Setting individual edge probability is error prone. More over it is difficult to check that the total probability is 1.0 because there is no easy way to know when the user finished setting all the probabilities. Reviewers: yamauchi, ebrevnov Tags: #llvm Differential Revision: https://reviews.llvm.org/D79396 --- llvm/include/llvm/Analysis/BranchProbabilityInfo.h | 10 +++ llvm/lib/Analysis/BranchProbabilityInfo.cpp | 99 ++++++++++++++-------- llvm/lib/Transforms/Scalar/JumpThreading.cpp | 3 +- llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp | 4 +- llvm/lib/Transforms/Utils/CodeExtractor.cpp | 12 ++- 5 files changed, 87 insertions(+), 41 deletions(-) diff --git a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h index 4c538d8..3e72afb 100644 --- a/llvm/include/llvm/Analysis/BranchProbabilityInfo.h +++ b/llvm/include/llvm/Analysis/BranchProbabilityInfo.h @@ -121,6 +121,7 @@ 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 @@ -130,6 +131,15 @@ public: 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 index d33af83..ff13c07 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -251,10 +251,13 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { 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 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { 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 @@ bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { } } - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - setEdgeProbability(BB, i, BP[i]); + setEdgeProbability(BB, BP); return true; } @@ -397,10 +400,13 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) { 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 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) { (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 @@ 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(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 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, (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 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, 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 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, 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 @@ bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB, 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 @@ bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) { 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 @@ bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) { 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 @@ void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src, << "\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 index c59b2ce..146ee13 100644 --- a/llvm/lib/Transforms/Scalar/JumpThreading.cpp +++ b/llvm/lib/Transforms/Scalar/JumpThreading.cpp @@ -2513,8 +2513,7 @@ void JumpThreadingPass::UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, } // 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 index f34d098..9c995de 100644 --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -401,9 +401,7 @@ bool llvm::SplitIndirectBrCriticalEdges(Function &F, 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 index e8154ec..a7d5ef5 100644 --- a/llvm/lib/Transforms/Utils/CodeExtractor.cpp +++ b/llvm/lib/Transforms/Utils/CodeExtractor.cpp @@ -1364,6 +1364,9 @@ void CodeExtractor::calculateNewCallTerminatorWeights( // 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 @@ void CodeExtractor::calculateNewCallTerminatorWeights( 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 @@ void CodeExtractor::calculateNewCallTerminatorWeights( // 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)); -- 2.7.4