diff options
Diffstat (limited to 'llvm/lib/Analysis/BranchProbabilityInfo.cpp')
| -rw-r--r-- | llvm/lib/Analysis/BranchProbabilityInfo.cpp | 265 |
1 files changed, 185 insertions, 80 deletions
diff --git a/llvm/lib/Analysis/BranchProbabilityInfo.cpp b/llvm/lib/Analysis/BranchProbabilityInfo.cpp index ffba65b5ed5ee..a396b5ad21c6a 100644 --- a/llvm/lib/Analysis/BranchProbabilityInfo.cpp +++ b/llvm/lib/Analysis/BranchProbabilityInfo.cpp @@ -61,6 +61,7 @@ INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) @@ -101,7 +102,7 @@ static const uint32_t LBH_UNLIKELY_WEIGHT = 62; /// /// This is the probability for a branch being taken to a block that terminates /// (eventually) in unreachable. These are predicted as unlikely as possible. -/// All reachable probability will equally share the remaining part. +/// All reachable probability will proportionally share the remaining part. static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1); /// Weight for a branch taken going into a cold block. @@ -240,7 +241,7 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { SmallVector<unsigned, 4> UnreachableEdges; SmallVector<unsigned, 4> ReachableEdges; - for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) + for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) if (PostDominatedByUnreachable.count(*I)) UnreachableEdges.push_back(I.getSuccessorIndex()); else @@ -250,10 +251,13 @@ 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) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -263,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; } @@ -277,7 +282,8 @@ bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) { bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { const Instruction *TI = BB->getTerminator(); assert(TI->getNumSuccessors() > 1 && "expected more than one successor!"); - if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI))) + if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI) || + isa<InvokeInst>(TI))) return false; MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); @@ -300,19 +306,19 @@ bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { SmallVector<unsigned, 2> UnreachableIdxs; SmallVector<unsigned, 2> ReachableIdxs; Weights.reserve(TI->getNumSuccessors()); - for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) { + for (unsigned I = 1, E = WeightsNode->getNumOperands(); I != E; ++I) { ConstantInt *Weight = - mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i)); + mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(I)); if (!Weight) return false; assert(Weight->getValue().getActiveBits() <= 32 && "Too many bits for uint32_t"); Weights.push_back(Weight->getZExtValue()); WeightSum += Weights.back(); - if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1))) - UnreachableIdxs.push_back(i - 1); + if (PostDominatedByUnreachable.count(TI->getSuccessor(I - 1))) + UnreachableIdxs.push_back(I - 1); else - ReachableIdxs.push_back(i - 1); + ReachableIdxs.push_back(I - 1); } assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); @@ -323,47 +329,93 @@ bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) { if (ScalingFactor > 1) { WeightSum = 0; - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) { - Weights[i] /= ScalingFactor; - WeightSum += Weights[i]; + for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) { + Weights[I] /= ScalingFactor; + WeightSum += Weights[I]; } } assert(WeightSum <= UINT32_MAX && "Expected weights to scale down to 32 bits"); if (WeightSum == 0 || ReachableIdxs.size() == 0) { - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - Weights[i] = 1; + for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) + Weights[I] = 1; WeightSum = TI->getNumSuccessors(); } // Set the probability. SmallVector<BranchProbability, 2> BP; - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) }); + for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) + BP.push_back({ Weights[I], static_cast<uint32_t>(WeightSum) }); // Examine the metadata against unreachable heuristic. // If the unreachable heuristic is more strong then we use it for this edge. - if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) { - auto ToDistribute = BranchProbability::getZero(); - auto UnreachableProb = UR_TAKEN_PROB; - for (auto i : UnreachableIdxs) - if (UnreachableProb < BP[i]) { - ToDistribute += BP[i] - UnreachableProb; - BP[i] = UnreachableProb; - } + if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) { + setEdgeProbability(BB, BP); + return true; + } + + auto UnreachableProb = UR_TAKEN_PROB; + for (auto I : UnreachableIdxs) + if (UnreachableProb < BP[I]) { + BP[I] = UnreachableProb; + } - // If we modified the probability of some edges then we must distribute - // the difference between reachable blocks. - if (ToDistribute > BranchProbability::getZero()) { - BranchProbability PerEdge = ToDistribute / ReachableIdxs.size(); - for (auto i : ReachableIdxs) - BP[i] += PerEdge; + // Sum of all edge probabilities must be 1.0. If we modified the probability + // of some edges then we must distribute the introduced difference over the + // reachable blocks. + // + // Proportional distribution: the relation between probabilities of the + // reachable edges is kept unchanged. That is for any reachable edges i and j: + // newBP[i] / newBP[j] == oldBP[i] / oldBP[j] => + // newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == K + // Where K is independent of i,j. + // newBP[i] == oldBP[i] * K + // We need to find K. + // Make sum of all reachables of the left and right parts: + // sum_of_reachable(newBP) == K * sum_of_reachable(oldBP) + // Sum of newBP must be equal to 1.0: + // sum_of_reachable(newBP) + sum_of_unreachable(newBP) == 1.0 => + // sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP) + // Where sum_of_unreachable(newBP) is what has been just changed. + // Finally: + // K == sum_of_reachable(newBP) / sum_of_reachable(oldBP) => + // K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP) + BranchProbability NewUnreachableSum = BranchProbability::getZero(); + for (auto I : UnreachableIdxs) + NewUnreachableSum += BP[I]; + + BranchProbability NewReachableSum = + BranchProbability::getOne() - NewUnreachableSum; + + BranchProbability OldReachableSum = BranchProbability::getZero(); + for (auto I : ReachableIdxs) + OldReachableSum += BP[I]; + + if (OldReachableSum != NewReachableSum) { // Anything to dsitribute? + if (OldReachableSum.isZero()) { + // If all oldBP[i] are zeroes then the proportional distribution results + // in all zero probabilities and the error stays big. In this case we + // evenly spread NewReachableSum over the reachable edges. + BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size(); + for (auto I : ReachableIdxs) + BP[I] = PerEdge; + } else { + for (auto I : ReachableIdxs) { + // We use uint64_t to avoid double rounding error of the following + // calculation: BP[i] = BP[i] * NewReachableSum / OldReachableSum + // The formula is taken from the private constructor + // BranchProbability(uint32_t Numerator, uint32_t Denominator) + uint64_t Mul = static_cast<uint64_t>(NewReachableSum.getNumerator()) * + BP[I].getNumerator(); + uint32_t Div = static_cast<uint32_t>( + divideNearest(Mul, OldReachableSum.getNumerator())); + BP[I] = BranchProbability::getRaw(Div); + } } } - for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) - setEdgeProbability(BB, i, BP[i]); + setEdgeProbability(BB, BP); return true; } @@ -386,7 +438,7 @@ bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) { // Determine which successors are post-dominated by a cold block. SmallVector<unsigned, 4> ColdEdges; SmallVector<unsigned, 4> NormalEdges; - for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) + for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) if (PostDominatedByColdCall.count(*I)) ColdEdges.push_back(I.getSuccessorIndex()); else @@ -396,10 +448,13 @@ 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) - setEdgeProbability(BB, SuccIdx, Prob); + EdgeProbabilities[SuccIdx] = Prob; + setEdgeProbability(BB, EdgeProbabilities); return true; } @@ -411,10 +466,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; } @@ -437,19 +493,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<BranchProbability, 2>({TakenProb, UntakenProb})); return true; } @@ -614,7 +672,7 @@ bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB, SmallVector<unsigned, 8> InEdges; // Edges from header to the loop. SmallVector<unsigned, 8> UnlikelyEdges; - for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch // irreducible loops. if (L) { @@ -646,18 +704,20 @@ 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) - 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()) { @@ -665,7 +725,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()) { @@ -673,9 +733,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; } @@ -786,15 +847,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<BranchProbability, 2>({TakenProb, UntakenProb})); return true; } @@ -829,14 +890,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<BranchProbability, 2>({TakenProb, UntakenProb})); return true; } @@ -847,13 +907,23 @@ 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<BranchProbability, 2>({TakenProb, TakenProb.getCompl()})); return true; } void BranchProbabilityInfo::releaseMemory() { Probs.clear(); + Handles.clear(); +} + +bool BranchProbabilityInfo::invalidate(Function &, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &) { + // Check whether the analysis, all analyses on functions, or the function's + // CFG have been preserved. + auto PAC = PA.getChecker<BranchProbabilityAnalysis>(); + return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() || + PAC.preservedSet<CFGAnalyses>()); } void BranchProbabilityInfo::print(raw_ostream &OS) const { @@ -862,7 +932,7 @@ void BranchProbabilityInfo::print(raw_ostream &OS) const { // or the function it is currently running over. assert(LastF && "Cannot print prior to running over a function"); for (const auto &BI : *LastF) { - for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE; + for (const_succ_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE; ++SI) { printEdgeProbability(OS << " ", &BI, *SI); } @@ -881,7 +951,7 @@ BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const { auto MaxProb = BranchProbability::getZero(); const BasicBlock *MaxSucc = nullptr; - for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { const BasicBlock *Succ = *I; auto Prob = getEdgeProbability(BB, Succ); if (Prob > MaxProb) { @@ -914,7 +984,7 @@ BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, BranchProbability BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, - succ_const_iterator Dst) const { + const_succ_iterator Dst) const { return getEdgeProbability(Src, Dst.getSuccessorIndex()); } @@ -925,8 +995,10 @@ BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst) const { auto Prob = BranchProbability::getZero(); bool FoundProb = false; - for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) + uint32_t EdgeCount = 0; + for (const_succ_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I) if (*I == Dst) { + ++EdgeCount; auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex())); if (MapI != Probs.end()) { FoundProb = true; @@ -934,7 +1006,7 @@ BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src, } } uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src)); - return FoundProb ? Prob : BranchProbability(1, succ_num); + return FoundProb ? Prob : BranchProbability(EdgeCount, succ_num); } /// Set the edge probability for a given edge specified by PredBlock and an @@ -949,6 +1021,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<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, @@ -962,15 +1056,16 @@ BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS, } void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) { - for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) { - auto Key = I->first; - if (Key.first == BB) - Probs.erase(Key); + for (const_succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) { + auto MapI = Probs.find(std::make_pair(BB, I.getSuccessorIndex())); + if (MapI != Probs.end()) + Probs.erase(MapI); } } void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI, - const TargetLibraryInfo *TLI) { + const TargetLibraryInfo *TLI, + PostDominatorTree *PDT) { LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() << " ----\n\n"); LastF = &F; // Store the last function we ran on for printing. @@ -998,10 +1093,15 @@ void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI, LLVM_DEBUG(dbgs() << "\n"); } - std::unique_ptr<PostDominatorTree> PDT = - std::make_unique<PostDominatorTree>(const_cast<Function &>(F)); - computePostDominatedByUnreachable(F, PDT.get()); - computePostDominatedByColdCall(F, PDT.get()); + std::unique_ptr<PostDominatorTree> PDTPtr; + + if (!PDT) { + PDTPtr = std::make_unique<PostDominatorTree>(const_cast<Function &>(F)); + PDT = PDTPtr.get(); + } + + computePostDominatedByUnreachable(F, PDT); + computePostDominatedByColdCall(F, PDT); // Walk the basic blocks in post-order so that we can build up state about // the successors of a block iteratively. @@ -1047,6 +1147,7 @@ void BranchProbabilityInfoWrapperPass::getAnalysisUsage( AU.addRequired<DominatorTreeWrapperPass>(); AU.addRequired<LoopInfoWrapperPass>(); AU.addRequired<TargetLibraryInfoWrapperPass>(); + AU.addRequired<PostDominatorTreeWrapperPass>(); AU.setPreservesAll(); } @@ -1054,7 +1155,9 @@ bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) { const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); - BPI.calculate(F, LI, &TLI); + PostDominatorTree &PDT = + getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); + BPI.calculate(F, LI, &TLI, &PDT); return false; } @@ -1069,7 +1172,9 @@ AnalysisKey BranchProbabilityAnalysis::Key; BranchProbabilityInfo BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) { BranchProbabilityInfo BPI; - BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F)); + BPI.calculate(F, AM.getResult<LoopAnalysis>(F), + &AM.getResult<TargetLibraryAnalysis>(F), + &AM.getResult<PostDominatorTreeAnalysis>(F)); return BPI; } |