Lines Matching +full:hot +full:- +full:swap
1 //===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
11 //===----------------------------------------------------------------------===//
52 #define DEBUG_TYPE "branch-prob"
55 "print-bpi", cl::init(false), cl::Hidden,
59 "print-bpi-func-name", cl::Hidden,
63 INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
69 INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob", in INITIALIZE_PASS_DEPENDENCY()
88 // BB1<-+
92 // BB2--+
98 // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
99 // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
103 /// Unreachable-terminating branch taken probability.
110 /// Heuristics and lookup tables for non-loop branches:
124 {ICmpInst::ICMP_NE, {PtrTakenProb, PtrUntakenProb}}, /// p != q -> Likely
125 {ICmpInst::ICMP_EQ, {PtrUntakenProb, PtrTakenProb}}, /// p == q -> Unlikely
138 {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, /// X == 0 -> Unlikely
139 {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, /// X != 0 -> Likely
140 {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X < 0 -> Unlikely
141 {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X > 0 -> Likely
144 /// Integer compares with -1:
146 {CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}}, /// X == -1 -> Unlikely
147 {CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}}, /// X != -1 -> Likely
148 // InstCombine canonicalizes X >= 0 into X > -1
149 {CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}}, /// X >= 0 -> Likely
155 {CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}}, /// X <= 0 -> Unlikely
170 // Floating-Point Heuristics (FPH)
175 static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
190 /// Floating-Point compares:
192 {FCmpInst::FCMP_ORD, {FPOrdTakenProb, FPOrdUntakenProb}}, /// !isnan -> Likely
193 {FCmpInst::FCMP_UNO, {FPOrdUntakenProb, FPOrdTakenProb}}, /// isnan -> Unlikely
224 // Ignore single-block SCCs since they either aren't loops or LoopInfo will in SccInfo()
232 LLVM_DEBUG(dbgs() << " " << BB->getName()); in SccInfo()
243 return -1; in getSCCNum()
244 return SccIt->second; in getSCCNum()
279 return It->second; in getSccBlockType()
329 !DstBlock.getLoop()->contains(SrcBlock.getLoop())) || in isLoopEnteringEdge()
331 (DstBlock.getSccNum() != -1 && in isLoopEnteringEdge()
349 DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) || in isLoopBackEdge()
350 (DstBlock.getSccNum() != -1 && in isLoopBackEdge()
351 SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum()))); in isLoopBackEdge()
357 auto *Header = LB.getLoop()->getHeader(); in getLoopEnterBlocks()
360 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?"); in getLoopEnterBlocks()
361 SccI->getSccEnterBlocks(LB.getSccNum(), Enters); in getLoopEnterBlocks()
368 LB.getLoop()->getExitBlocks(Exits); in getLoopExitBlocks()
370 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?"); in getLoopExitBlocks()
371 SccI->getSccExitBlocks(LB.getSccNum(), Exits); in getLoopExitBlocks()
380 const Instruction *TI = BB->getTerminator(); in calcMetadataWeights()
381 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!"); in calcMetadataWeights()
391 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors"); in calcMetadataWeights()
405 const LoopBlock DstLoopBB = getLoopBlock(TI->getSuccessor(I)); in calcMetadataWeights()
413 assert(Weights.size() == TI->getNumSuccessors() && "Checked above"); in calcMetadataWeights()
422 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) { in calcMetadataWeights()
431 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) in calcMetadataWeights()
433 WeightSum = TI->getNumSuccessors(); in calcMetadataWeights()
438 for (unsigned I = 0, E = TI->getNumSuccessors(); I != E; ++I) in calcMetadataWeights()
469 // sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP) in calcMetadataWeights()
473 // K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP) in calcMetadataWeights()
479 BranchProbability::getOne() - NewUnreachableSum; in calcMetadataWeights()
516 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); in calcPointerHeuristics()
517 if (!BI || !BI->isConditional()) in calcPointerHeuristics()
520 Value *Cond = BI->getCondition(); in calcPointerHeuristics()
522 if (!CI || !CI->isEquality()) in calcPointerHeuristics()
525 Value *LHS = CI->getOperand(0); in calcPointerHeuristics()
527 if (!LHS->getType()->isPointerTy()) in calcPointerHeuristics()
530 assert(CI->getOperand(1)->getType()->isPointerTy()); in calcPointerHeuristics()
532 auto Search = PointerTable.find(CI->getPredicate()); in calcPointerHeuristics()
535 setEdgeProbability(BB, Search->second); in calcPointerHeuristics()
566 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); in computeUnlikelySuccessors()
567 if (!BI || !BI->isConditional()) in computeUnlikelySuccessors()
571 CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition()); in computeUnlikelySuccessors()
572 if (!CI || !isa<Instruction>(CI->getOperand(0)) || in computeUnlikelySuccessors()
573 !isa<Constant>(CI->getOperand(1))) in computeUnlikelySuccessors()
579 Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0)); in computeUnlikelySuccessors()
581 Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1)); in computeUnlikelySuccessors()
585 isa<Constant>(CmpLHS->getOperand(1))) { in computeUnlikelySuccessors()
587 if (!L->contains(CmpLHS)) in computeUnlikelySuccessors()
590 CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0)); in computeUnlikelySuccessors()
594 if (!CmpPHI || !L->contains(CmpPHI)) in computeUnlikelySuccessors()
604 for (BasicBlock *B : P->blocks()) { in computeUnlikelySuccessors()
606 if (!L->contains(B)) in computeUnlikelySuccessors()
608 Value *V = P->getIncomingValueForBlock(B); in computeUnlikelySuccessors()
617 // we can constant-evaluate the compare to see if it makes the branch be in computeUnlikelySuccessors()
623 const DataLayout &DL = BB->getDataLayout(); in computeUnlikelySuccessors()
626 I->getOpcode(), CmpLHSConst, cast<Constant>(I->getOperand(1)), DL); in computeUnlikelySuccessors()
632 // Now constant-evaluate the compare in computeUnlikelySuccessors()
634 CI->getPredicate(), CmpLHSConst, CmpConst, DL); in computeUnlikelySuccessors()
638 ((Result->isZeroValue() && B == BI->getSuccessor(0)) || in computeUnlikelySuccessors()
639 (Result->isOneValue() && B == BI->getSuccessor(1)))) in computeUnlikelySuccessors()
650 return WeightIt->second; in getEstimatedBlockWeight()
658 return WeightIt->second; in getEstimatedLoopWeight()
737 const auto *DTStartNode = DT->getNode(BB); in propagateEstimatedBlockWeight()
738 const auto *PDTStartNode = PDT->getNode(BB); in propagateEstimatedBlockWeight()
742 DTNode = DTNode->getIDom()) { in propagateEstimatedBlockWeight()
743 auto *DomBB = DTNode->getBlock(); in propagateEstimatedBlockWeight()
745 if (!PDT->dominates(PDTStartNode, PDT->getNode(DomBB))) in propagateEstimatedBlockWeight()
771 if (CI->hasFnAttr(Attribute::NoReturn)) in getInitialEstimatedBlockWeight()
780 if (isa<UnreachableInst>(BB->getTerminator()) || in getInitialEstimatedBlockWeight()
785 BB->getTerminatingDeoptimizeCall()) in getInitialEstimatedBlockWeight()
791 if (BB->isEHPad()) in getInitialEstimatedBlockWeight()
797 if (CI->hasFnAttr(Attribute::Cold)) in getInitialEstimatedBlockWeight()
834 SmallVectorImpl<BasicBlock *> &Exits = Res.first->second; in computeEestimateBlockWeight()
858 // weight of "hot" path. In theory we can probably find a better function in computeEestimateBlockWeight()
877 assert(BB->getTerminator()->getNumSuccessors() > 1 && in calcEstimatedHeuristics()
965 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); in calcZeroHeuristics()
966 if (!BI || !BI->isConditional()) in calcZeroHeuristics()
969 Value *Cond = BI->getCondition(); in calcZeroHeuristics()
976 return dyn_cast<ConstantInt>(I->getOperand(0)); in calcZeroHeuristics()
980 Value *RHS = CI->getOperand(1); in calcZeroHeuristics()
987 if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0))) in calcZeroHeuristics()
988 if (LHS->getOpcode() == Instruction::And) in calcZeroHeuristics()
989 if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(1))) in calcZeroHeuristics()
990 if (AndRHS->getValue().isPowerOf2()) in calcZeroHeuristics()
996 if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0))) in calcZeroHeuristics()
997 if (Function *CalledFn = Call->getCalledFunction()) in calcZeroHeuristics()
998 TLI->getLibFunc(*CalledFn, Func); in calcZeroHeuristics()
1007 Search = ICmpWithLibCallTable.find(CI->getPredicate()); in calcZeroHeuristics()
1010 } else if (CV->isZero()) { in calcZeroHeuristics()
1011 Search = ICmpWithZeroTable.find(CI->getPredicate()); in calcZeroHeuristics()
1014 } else if (CV->isOne()) { in calcZeroHeuristics()
1015 Search = ICmpWithOneTable.find(CI->getPredicate()); in calcZeroHeuristics()
1018 } else if (CV->isMinusOne()) { in calcZeroHeuristics()
1019 Search = ICmpWithMinusOneTable.find(CI->getPredicate()); in calcZeroHeuristics()
1026 setEdgeProbability(BB, Search->second); in calcZeroHeuristics()
1031 const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator()); in calcFloatingPointHeuristics()
1032 if (!BI || !BI->isConditional()) in calcFloatingPointHeuristics()
1035 Value *Cond = BI->getCondition(); in calcFloatingPointHeuristics()
1041 if (FCmp->isEquality()) { in calcFloatingPointHeuristics()
1042 ProbList = !FCmp->isTrueWhenEqual() ? in calcFloatingPointHeuristics()
1043 // f1 == f2 -> Unlikely in calcFloatingPointHeuristics()
1045 // f1 != f2 -> Likely in calcFloatingPointHeuristics()
1048 auto Search = FCmpTable.find(FCmp->getPredicate()); in calcFloatingPointHeuristics()
1051 ProbList = Search->second; in calcFloatingPointHeuristics()
1073 OS << "---- Branch Probabilities ----\n"; in print()
1085 // Hot probability is at least 4/5 = 80% in isEdgeHot()
1086 // FIXME: Compare against a static "hot" BranchProbability. in isEdgeHot()
1100 "Probability for I-th successor must always be defined along with the " in getEdgeProbability()
1104 return I->second; in getEdgeProbability()
1126 Prob += Probs.find(std::make_pair(Src, I.getSuccessorIndex()))->second; in getEdgeProbability()
1134 assert(Src->getTerminator()->getNumSuccessors() == Probs.size()); in setEdgeProbability()
1142 this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx]; in setEdgeProbability()
1143 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << SuccIdx in setEdgeProbability()
1155 assert(TotalNumerator >= BranchProbability::getDenominator() - Probs.size()); in setEdgeProbability()
1162 unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors(); in copyEdgeProbabilities()
1163 assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors()); in copyEdgeProbabilities()
1166 if (!this->Probs.contains(std::make_pair(Src, 0))) in copyEdgeProbabilities()
1171 auto Prob = this->Probs[std::make_pair(Src, SuccIdx)]; in copyEdgeProbabilities()
1172 this->Probs[std::make_pair(Dst, SuccIdx)] = Prob; in copyEdgeProbabilities()
1173 LLVM_DEBUG(dbgs() << "set edge " << Dst->getName() << " -> " << SuccIdx in copyEdgeProbabilities()
1179 assert(Src->getTerminator()->getNumSuccessors() == 2); in swapSuccEdgesProbabilities()
1183 std::swap(Probs[std::make_pair(Src, 0)], Probs[std::make_pair(Src, 1)]); in swapSuccEdgesProbabilities()
1192 Src->printAsOperand(OS, false, Src->getModule()); in printEdgeProbability()
1193 OS << " -> "; in printEdgeProbability()
1194 Dst->printAsOperand(OS, false, Dst->getModule()); in printEdgeProbability()
1196 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); in printEdgeProbability()
1202 LLVM_DEBUG(dbgs() << "eraseBlock " << BB->getName() << "\n"); in eraseBlock()
1208 // a pair (BB, N) if there is no data for (BB, N-1) because the data is always in eraseBlock()
1227 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName() in calculate()
1228 << " ----\n\n"); in calculate()
1252 // Walk the basic blocks in post-order so that we can build up state about in calculate()
1255 LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName() in calculate()
1258 if (BB->getTerminator()->getNumSuccessors() < 2) in calculate()