LLVM: lib/Analysis/BranchProbabilityInfo.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
44#include
45#include
46#include
47#include
48
49using namespace llvm;
50
51#define DEBUG_TYPE "branch-prob"
52
55 cl::desc("Print the branch probability info."));
56
59 cl::desc("The option to specify the name of the function "
60 "whose branch probability info is printed."));
61
63 "Branch Probability Analysis", false, true)
70
75}
76
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
101
102
103
104
105
106
108
109
110
117
120
121
125};
126
127
134
135
141};
142
143
147
149};
150
151
153
155};
156
157
158
159
160
161
162
163
167};
168
169
172
173
175
176
177
179
188
189
193};
194
195
196
198
200
202
204
206
208
209
210 COLD = 0xffff,
211
212
214};
215
217
218
219
220 int SccNum = 0;
222 ++It, ++SccNum) {
223
224
225 const std::vector<const BasicBlock *> &Scc = *It;
226 if (Scc.size() == 1)
227 continue;
228
230 for (const auto *BB : Scc) {
232 SccNums[BB] = SccNum;
233 calculateSccBlockType(BB, SccNum);
234 }
236 }
237}
238
240 auto SccIt = SccNums.find(BB);
241 if (SccIt == SccNums.end())
242 return -1;
243 return SccIt->second;
244}
245
248
249 for (auto MapIt : SccBlocks[SccNum]) {
250 const auto *BB = MapIt.first;
251 if (isSCCHeader(BB, SccNum))
253 if (getSCCNum(Pred) != SccNum)
255 }
256}
257
260 for (auto MapIt : SccBlocks[SccNum]) {
261 const auto *BB = MapIt.first;
262 if (isSCCExitingBlock(BB, SccNum))
263 for (const auto *Succ : successors(BB))
264 if (getSCCNum(Succ) != SccNum)
266 }
267}
268
269uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(const BasicBlock *BB,
270 int SccNum) const {
271 assert(getSCCNum(BB) == SccNum);
272
273 assert(SccBlocks.size() > static_cast<unsigned>(SccNum) && "Unknown SCC");
274 const auto &SccBlockTypes = SccBlocks[SccNum];
275
276 auto It = SccBlockTypes.find(BB);
277 if (It != SccBlockTypes.end()) {
278 return It->second;
279 }
280 return Inner;
281}
282
283void BranchProbabilityInfo::SccInfo::calculateSccBlockType(const BasicBlock *BB,
284 int SccNum) {
285 assert(getSCCNum(BB) == SccNum);
287
289
290
291 return getSCCNum(Pred) != SccNum;
292 }))
294
296 return getSCCNum(Succ) != SccNum;
297 }))
299
300
301
302 if (SccBlocks.size() <= static_cast<unsigned>(SccNum))
303 SccBlocks.resize(SccNum + 1);
304 auto &SccBlockTypes = SccBlocks[SccNum];
305
306 if (BlockType != Inner) {
307 bool IsInserted;
308 std::tie(std::ignore, IsInserted) =
309 SccBlockTypes.insert(std::make_pair(BB, BlockType));
310 assert(IsInserted && "Duplicated block in SCC");
311 }
312}
313
314BranchProbabilityInfo::LoopBlock::LoopBlock(const BasicBlock *BB,
316 const SccInfo &SccI)
317 : BB(BB) {
319 if (.first) {
320 LD.second = SccI.getSCCNum(BB);
321 }
322}
323
324bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const {
325 const auto &SrcBlock = Edge.first;
326 const auto &DstBlock = Edge.second;
327 return (DstBlock.getLoop() &&
328 !DstBlock.getLoop()->contains(SrcBlock.getLoop())) ||
329
330 (DstBlock.getSccNum() != -1 &&
331 SrcBlock.getSccNum() != DstBlock.getSccNum());
332}
333
334bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const {
335 return isLoopEnteringEdge({Edge.second, Edge.first});
336}
337
338bool BranchProbabilityInfo::isLoopEnteringExitingEdge(
339 const LoopEdge &Edge) const {
340 return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge);
341}
342
343bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const {
344 const auto &SrcBlock = Edge.first;
345 const auto &DstBlock = Edge.second;
346 return SrcBlock.belongsToSameLoop(DstBlock) &&
347 ((DstBlock.getLoop() &&
348 DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) ||
349 (DstBlock.getSccNum() != -1 &&
350 SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum())));
351}
352
353void BranchProbabilityInfo::getLoopEnterBlocks(
355 if (LB.getLoop()) {
356 auto *Header = LB.getLoop()->getHeader();
358 } else {
359 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?");
360 SccI->getSccEnterBlocks(LB.getSccNum(), Enters);
361 }
362}
363
364void BranchProbabilityInfo::getLoopExitBlocks(
366 if (LB.getLoop()) {
367 LB.getLoop()->getExitBlocks(Exits);
368 } else {
369 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?");
370 SccI->getSccExitBlocks(LB.getSccNum(), Exits);
371 }
372}
373
374
375
376
377
378bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
381 if (!(isa(TI) || isa(TI) || isa(TI) ||
382 isa(TI) || isa(TI)))
383 return false;
384
386 if (!WeightsNode)
387 return false;
388
389
391
392
393
394
399
401 for (unsigned I = 0, E = Weights.size(); I != E; ++I) {
402 WeightSum += Weights[I];
403 const LoopBlock SrcLoopBB = getLoopBlock(BB);
404 const LoopBlock DstLoopBB = getLoopBlock(TI->getSuccessor(I));
405 auto EstimatedWeight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
406 if (EstimatedWeight &&
407 *EstimatedWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))
409 else
411 }
413
414
415
417 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
418
419 if (ScalingFactor > 1) {
420 WeightSum = 0;
422 Weights[I] /= ScalingFactor;
423 WeightSum += Weights[I];
424 }
425 }
426 assert(WeightSum <= UINT32_MAX &&
427 "Expected weights to scale down to 32 bits");
428
429 if (WeightSum == 0 || ReachableIdxs.size() == 0) {
431 Weights[I] = 1;
433 }
434
435
439
440
441
442 if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {
444 return true;
445 }
446
448 for (auto I : UnreachableIdxs)
449 if (UnreachableProb < BP[I]) {
450 BP[I] = UnreachableProb;
451 }
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
474 for (auto I : UnreachableIdxs)
475 NewUnreachableSum += BP[I];
476
479
481 for (auto I : ReachableIdxs)
482 OldReachableSum += BP[I];
483
484 if (OldReachableSum != NewReachableSum) {
485 if (OldReachableSum.isZero()) {
486
487
488
489 BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size();
490 for (auto I : ReachableIdxs)
491 BP[I] = PerEdge;
492 } else {
493 for (auto I : ReachableIdxs) {
494
495
496
497
499 BP[I].getNumerator();
503 }
504 }
505 }
506
508
509 return true;
510}
511
512
513
514bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
517 return false;
518
522 return false;
523
525
527 return false;
528
530
533 return false;
535 return true;
536}
537
538
539
540
541static void
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
567 return;
568
569
571 if (!CI || !isa(CI->getOperand(0)) ||
573 return;
574
575
576
577
579 PHINode *CmpPHI = dyn_cast(CmpLHS);
581
583 while (!CmpPHI && CmpLHS && isa(CmpLHS) &&
584 isa(CmpLHS->getOperand(1))) {
585
586 if (!L->contains(CmpLHS))
587 return;
588 InstChain.push_back(cast(CmpLHS));
589 CmpLHS = dyn_cast(CmpLHS->getOperand(0));
590 if (CmpLHS)
591 CmpPHI = dyn_cast(CmpLHS);
592 }
593 if (!CmpPHI || !L->contains(CmpPHI))
594 return;
595
596
600 VisitedInsts.insert(CmpPHI);
601 while (!WorkList.empty()) {
604
605 if (!L->contains(B))
606 continue;
607 Value *V = P->getIncomingValueForBlock(B);
608
609
610 if (PHINode *PN = dyn_cast(V)) {
611 if (VisitedInsts.insert(PN).second)
613 continue;
614 }
615
616
617
618 Constant *CmpLHSConst = dyn_cast(V);
620 continue;
621
625 I->getOpcode(), CmpLHSConst, cast(I->getOperand(1)), DL);
626 if (!CmpLHSConst)
627 break;
628 }
629 if (!CmpLHSConst)
630 continue;
631
634
635
636 if (Result &&
637 ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
638 (Result->isOneValue() && B == BI->getSuccessor(1))))
640 }
641 }
642}
643
644std::optional<uint32_t>
645BranchProbabilityInfo::getEstimatedBlockWeight(const BasicBlock *BB) const {
646 auto WeightIt = EstimatedBlockWeight.find(BB);
647 if (WeightIt == EstimatedBlockWeight.end())
648 return std::nullopt;
649 return WeightIt->second;
650}
651
652std::optional<uint32_t>
653BranchProbabilityInfo::getEstimatedLoopWeight(const LoopData &L) const {
654 auto WeightIt = EstimatedLoopWeight.find(L);
655 if (WeightIt == EstimatedLoopWeight.end())
656 return std::nullopt;
657 return WeightIt->second;
658}
659
660std::optional<uint32_t>
661BranchProbabilityInfo::getEstimatedEdgeWeight(const LoopEdge &Edge) const {
662
663
664 return isLoopEnteringEdge(Edge)
665 ? getEstimatedLoopWeight(Edge.second.getLoopData())
666 : getEstimatedBlockWeight(Edge.second.getBlock());
667}
668
669template
670std::optional<uint32_t> BranchProbabilityInfo::getMaxEstimatedEdgeWeight(
673 std::optional<uint32_t> MaxWeight;
674 for (const BasicBlock *DstBB : Successors) {
675 const LoopBlock DstLoopBB = getLoopBlock(DstBB);
676 auto Weight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
677
678 if (!Weight)
679 return std::nullopt;
680
681 if (!MaxWeight || *MaxWeight < *Weight)
682 MaxWeight = Weight;
683 }
684
685 return MaxWeight;
686}
687
688
689
690
691
692
693bool BranchProbabilityInfo::updateEstimatedBlockWeight(
694 LoopBlock &LoopBB, uint32_t BBWeight,
698
699
700
701
702
703
704 if (!EstimatedBlockWeight.insert({BB, BBWeight}).second)
705 return false;
706
708 LoopBlock PredLoop = getLoopBlock(PredBlock);
709
710 if (isLoopExitingEdge({PredLoop, LoopBB})) {
711 if (!EstimatedLoopWeight.count(PredLoop.getLoopData()))
712 LoopWorkList.push_back(PredLoop);
713 } else if (!EstimatedBlockWeight.count(PredBlock))
714 BlockWorkList.push_back(PredBlock);
715 }
716 return true;
717}
718
719
720
721
722
723
724
725
726
727
728
729
730
731void BranchProbabilityInfo::propagateEstimatedBlockWeight(
735 const BasicBlock *BB = LoopBB.getBlock();
736 const auto *DTStartNode = DT->getNode(BB);
737 const auto *PDTStartNode = PDT->getNode(BB);
738
739
740 for (const auto *DTNode = DTStartNode; DTNode != nullptr;
741 DTNode = DTNode->getIDom()) {
742 auto *DomBB = DTNode->getBlock();
743
745
746
747 break;
748
749 LoopBlock DomLoopBB = getLoopBlock(DomBB);
750 const LoopEdge Edge{DomLoopBB, LoopBB};
751
752 if (!isLoopEnteringExitingEdge(Edge)) {
753 if (!updateEstimatedBlockWeight(DomLoopBB, BBWeight, BlockWorkList,
754 LoopWorkList))
755
756
757 break;
758 } else if (isLoopExitingEdge(Edge)) {
759 LoopWorkList.push_back(DomLoopBB);
760 }
761 }
762}
763
764std::optional<uint32_t>
765BranchProbabilityInfo::getInitialEstimatedBlockWeight(const BasicBlock *BB) {
766
767 auto hasNoReturn = [&](const BasicBlock *BB) {
768 for (const auto &I : reverse(*BB))
769 if (const CallInst *CI = dyn_cast(&I))
770 if (CI->hasFnAttr(Attribute::NoReturn))
771 return true;
772
773 return false;
774 };
775
776
777
778
780
781
782
783
785 return hasNoReturn(BB)
786 ? static_cast<uint32_t>(BlockExecWeight::NORETURN)
787 : static_cast<uint32_t>(BlockExecWeight::UNREACHABLE);
788
789
791 return static_cast<uint32_t>(BlockExecWeight::UNWIND);
792
793
794 for (const auto &I : *BB)
795 if (const CallInst *CI = dyn_cast(&I))
796 if (CI->hasFnAttr(Attribute::Cold))
797 return static_cast<uint32_t>(BlockExecWeight::COLD);
798
799 return std::nullopt;
800}
801
802
803
804
805void BranchProbabilityInfo::computeEestimateBlockWeight(
810
811
812
814 for (const auto *BB : RPOT)
815 if (auto BBWeight = getInitialEstimatedBlockWeight(BB))
816
817
818 propagateEstimatedBlockWeight(getLoopBlock(BB), DT, PDT, *BBWeight,
819 BlockWorkList, LoopWorkList);
820
821
822
823
824
825 do {
826 while (!LoopWorkList.empty()) {
827 const LoopBlock LoopBB = LoopWorkList.pop_back_val();
828 const LoopData LD = LoopBB.getLoopData();
829 if (EstimatedLoopWeight.count(LD))
830 continue;
831
832 auto Res = LoopExitBlocks.try_emplace(LD);
834 if (Res.second)
835 getLoopExitBlocks(LoopBB, Exits);
836 auto LoopWeight = getMaxEstimatedEdgeWeight(
838
839 if (LoopWeight) {
840
841 if (LoopWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))
842 LoopWeight = static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);
843
844 EstimatedLoopWeight.insert({LD, *LoopWeight});
845
846 getLoopEnterBlocks(LoopBB, BlockWorkList);
847 }
848 }
849
850 while (!BlockWorkList.empty()) {
851
853 if (EstimatedBlockWeight.count(BB))
854 continue;
855
856
857
858
859
860
861
862 const LoopBlock LoopBB = getLoopBlock(BB);
863 auto MaxWeight = getMaxEstimatedEdgeWeight(LoopBB, successors(BB));
864
865 if (MaxWeight)
866 propagateEstimatedBlockWeight(LoopBB, DT, PDT, *MaxWeight,
867 BlockWorkList, LoopWorkList);
868 }
869 } while (!BlockWorkList.empty() || !LoopWorkList.empty());
870}
871
872
873
874
875bool BranchProbabilityInfo::calcEstimatedHeuristics(const BasicBlock *BB) {
877 "expected more than one successor!");
878
879 const LoopBlock LoopBB = getLoopBlock(BB);
880
883 if (LoopBB.getLoop())
885
886
887 bool FoundEstimatedWeight = false;
890
892 std::optional<uint32_t> Weight;
893 const LoopBlock SuccLoopBB = getLoopBlock(SuccBB);
894 const LoopEdge Edge{LoopBB, SuccLoopBB};
895
896 Weight = getEstimatedEdgeWeight(Edge);
897
898 if (isLoopExitingEdge(Edge) &&
899
900 Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
901
902 Weight = std::max(
903 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
904 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) /
905 TC);
906 }
907 bool IsUnlikelyEdge = LoopBB.getLoop() && UnlikelyBlocks.contains(SuccBB);
908 if (IsUnlikelyEdge &&
909
910 Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
911
912 Weight = std::max(
913 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
914 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT)) / 2);
915 }
916
917 if (Weight)
918 FoundEstimatedWeight = true;
919
920 auto WeightVal =
921 Weight.value_or(static_cast<uint32_t>(BlockExecWeight::DEFAULT));
922 TotalWeight += WeightVal;
923 SuccWeights.push_back(WeightVal);
924 }
925
926
927
928
929 if (!FoundEstimatedWeight || TotalWeight == 0)
930 return false;
931
933 const unsigned SuccCount = SuccWeights.size();
934
935
936
937 if (TotalWeight > UINT32_MAX) {
938 uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1;
939 TotalWeight = 0;
940 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
941 SuccWeights[Idx] /= ScalingFactor;
942 if (SuccWeights[Idx] == static_cast<uint32_t>(BlockExecWeight::ZERO))
943 SuccWeights[Idx] =
944 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);
945 TotalWeight += SuccWeights[Idx];
946 }
947 assert(TotalWeight <= UINT32_MAX && "Total weight overflows");
948 }
949
950
953
954 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
955 EdgeProbabilities[Idx] =
957 }
959 return true;
960}
961
962bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
966 return false;
967
970 if (!CI)
971 return false;
972
973 auto GetConstantInt = [](Value *V) {
974 if (auto *I = dyn_cast(V))
975 return dyn_cast(I->getOperand(0));
976 return dyn_cast(V);
977 };
978
981 if (!CV)
982 return false;
983
984
985
987 if (LHS->getOpcode() == Instruction::And)
988 if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(1)))
989 if (AndRHS->getValue().isPowerOf2())
990 return false;
991
992
994 if (TLI)
996 if (Function *CalledFn = Call->getCalledFunction())
998
999 ProbabilityTable::const_iterator Search;
1000 if (Func == LibFunc_strcasecmp ||
1001 Func == LibFunc_strcmp ||
1002 Func == LibFunc_strncasecmp ||
1003 Func == LibFunc_strncmp ||
1004 Func == LibFunc_memcmp ||
1005 Func == LibFunc_bcmp) {
1008 return false;
1009 } else if (CV->isZero()) {
1012 return false;
1013 } else if (CV->isOne()) {
1016 return false;
1020 return false;
1021 } else {
1022 return false;
1023 }
1024
1026 return true;
1027}
1028
1029bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
1032 return false;
1033
1036 if (!FCmp)
1037 return false;
1038
1042
1044
1046 } else {
1049 return false;
1050 ProbList = Search->second;
1051 }
1052
1054 return true;
1055}
1056
1058 Probs.clear();
1059 Handles.clear();
1060}
1061
1064
1065
1069}
1070
1072 OS << "---- Branch Probabilities ----\n";
1073
1074
1075 assert(LastF && "Cannot print prior to running over a function");
1076 for (const auto &BI : *LastF) {
1079 }
1080}
1081
1084
1085
1087}
1088
1089
1090
1091
1092
1095 unsigned IndexInSuccessors) const {
1096 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
1097 assert((Probs.end() == Probs.find(std::make_pair(Src, 0))) ==
1098 (Probs.end() == I) &&
1099 "Probability for I-th successor must always be defined along with the "
1100 "probability for the first successor");
1101
1102 if (I != Probs.end())
1103 return I->second;
1104
1106}
1107
1112}
1113
1114
1115
1119 if (!Probs.count(std::make_pair(Src, 0)))
1121
1124 if (*I == Dst)
1125 Prob += Probs.find(std::make_pair(Src, I.getSuccessorIndex()))->second;
1126
1127 return Prob;
1128}
1129
1130
1133 assert(Src->getTerminator()->getNumSuccessors() == Probs.size());
1134 eraseBlock(Src);
1135 if (Probs.size() == 0)
1136 return;
1137
1138 Handles.insert(BasicBlockCallbackVH(Src, this));
1139 uint64_t TotalNumerator = 0;
1140 for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {
1141 this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx];
1142 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << SuccIdx
1143 << " successor probability to " << Probs[SuccIdx]
1144 << "\n");
1145 TotalNumerator += Probs[SuccIdx].getNumerator();
1146 }
1147
1148
1149
1150
1151
1152
1155 (void)TotalNumerator;
1156}
1157
1160 eraseBlock(Dst);
1161 unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors();
1162 assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors());
1163 if (NumSuccessors == 0)
1164 return;
1165 if (!this->Probs.contains(std::make_pair(Src, 0)))
1166 return;
1167
1168 Handles.insert(BasicBlockCallbackVH(Dst, this));
1169 for (unsigned SuccIdx = 0; SuccIdx < NumSuccessors; ++SuccIdx) {
1170 auto Prob = this->Probs[std::make_pair(Src, SuccIdx)];
1171 this->Probs[std::make_pair(Dst, SuccIdx)] = Prob;
1172 LLVM_DEBUG(dbgs() << "set edge " << Dst->getName() << " -> " << SuccIdx
1173 << " successor probability to " << Prob << "\n");
1174 }
1175}
1176
1178 assert(Src->getTerminator()->getNumSuccessors() == 2);
1179 if (!Probs.contains(std::make_pair(Src, 0)))
1180 return;
1181 assert(Probs.contains(std::make_pair(Src, 1)));
1182 std::swap(Probs[std::make_pair(Src, 0)], Probs[std::make_pair(Src, 1)]);
1183}
1184
1190 OS << "edge ";
1191 Src->printAsOperand(OS, false, Src->getModule());
1192 OS << " -> ";
1193 Dst->printAsOperand(OS, false, Dst->getModule());
1194 OS << " probability is " << Prob
1195 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
1196
1197 return OS;
1198}
1199
1202
1203
1204
1205
1206
1207
1208
1209
1210 Handles.erase(BasicBlockCallbackVH(BB, this));
1211 for (unsigned I = 0;; ++I) {
1212 auto MapI = Probs.find(std::make_pair(BB, I));
1213 if (MapI == Probs.end()) {
1214 assert(Probs.count(std::make_pair(BB, I + 1)) == 0 &&
1215 "Must be no more successors");
1216 return;
1217 }
1218 Probs.erase(MapI);
1219 }
1220}
1221
1226 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
1227 << " ----\n\n");
1228 LastF = &F;
1229 LI = &LoopI;
1230
1231 SccI = std::make_unique(F);
1232
1233 assert(EstimatedBlockWeight.empty());
1235
1236 std::unique_ptr DTPtr;
1237 std::unique_ptr PDTPtr;
1238
1239 if (!DT) {
1240 DTPtr = std::make_unique(const_cast<Function &>(F));
1241 DT = DTPtr.get();
1242 }
1243
1244 if (!PDT) {
1245 PDTPtr = std::make_unique(const_cast<Function &>(F));
1246 PDT = PDTPtr.get();
1247 }
1248
1249 computeEestimateBlockWeight(F, DT, PDT);
1250
1251
1252
1253 for (const auto *BB : post_order(&F.getEntryBlock())) {
1255 << "\n");
1256
1258 continue;
1259 if (calcMetadataWeights(BB))
1260 continue;
1261 if (calcEstimatedHeuristics(BB))
1262 continue;
1263 if (calcPointerHeuristics(BB))
1264 continue;
1265 if (calcZeroHeuristics(BB, TLI))
1266 continue;
1267 if (calcFloatingPointHeuristics(BB))
1268 continue;
1269 }
1270
1271 EstimatedLoopWeight.clear();
1272 EstimatedBlockWeight.clear();
1273 SccI.reset();
1274
1278 }
1279}
1280
1283
1284
1285
1292}
1293
1295 const LoopInfo &LI = getAnalysis().getLoopInfo();
1297 getAnalysis().getTLI(F);
1298 DominatorTree &DT = getAnalysis().getDomTree();
1300 getAnalysis().getPostDomTree();
1301 BPI.calculate(F, LI, &TLI, &DT, &PDT);
1302 return false;
1303}
1304
1306
1308 const Module *) const {
1309 BPI.print(OS);
1310}
1311
1312AnalysisKey BranchProbabilityAnalysis::Key;
1320 BPI.calculate(F, LI, &TLI, &DT, &PDT);
1321 return BPI;
1322}
1323
1326 OS << "Printing analysis 'Branch Probability Analysis' for function '"
1327 << F.getName() << "':\n";
1330}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
BlockExecWeight
Set of dedicated "absolute" execution weights for a block.
@ NORETURN
Weight to a block containing non returning call.
@ UNWIND
Weight to 'unwind' block of an invoke instruction.
@ COLD
Weight to a 'cold' block.
@ ZERO
Special weight used for cases with exact zero probability.
@ UNREACHABLE
Weight to an 'unreachable' block.
@ DEFAULT
Default weight is used in cases when there is no dedicated execution weight set.
@ LOWEST_NON_ZERO
Minimal possible non zero weight.
static const uint32_t FPH_TAKEN_WEIGHT
static const BranchProbability FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
static const BranchProbability ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
static const uint32_t LBH_TAKEN_WEIGHT
static const uint32_t ZH_NONTAKEN_WEIGHT
static const ProbabilityTable ICmpWithLibCallTable
strcmp and similar functions return zero, negative, or positive, if the first string is equal,...
static const ProbabilityTable ICmpWithMinusOneTable
Integer compares with -1:
static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
static const ProbabilityTable ICmpWithZeroTable
Integer compares with 0:
static const uint32_t PH_NONTAKEN_WEIGHT
std::map< CmpInst::Predicate, ProbabilityList > ProbabilityTable
static const BranchProbability PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
static const BranchProbability ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
static const BranchProbability FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
static const uint32_t PH_TAKEN_WEIGHT
Heuristics and lookup tables for non-loop branches: Pointer Heuristics (PH)
static const BranchProbability FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
branch Branch Probability Analysis
static const BranchProbability PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
SmallVector< BranchProbability > ProbabilityList
static const ProbabilityTable ICmpWithOneTable
Integer compares with 1:
static const uint32_t ZH_TAKEN_WEIGHT
Zero Heuristics (ZH)
static const uint32_t FPH_NONTAKEN_WEIGHT
static const BranchProbability UR_TAKEN_PROB
Unreachable-terminating branch taken probability.
static const ProbabilityTable FCmpTable
Floating-Point compares:
static const uint32_t LBH_NONTAKEN_WEIGHT
static const ProbabilityTable PointerTable
Pointer comparisons:
static const uint32_t FPH_ORD_WEIGHT
This is the probability for an ordered floating point comparison.
static void computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, SmallPtrSetImpl< const BasicBlock * > &UnlikelyBlocks)
static const uint32_t FPH_UNO_WEIGHT
This is the probability for an unordered floating point comparison, it means one or two of the operan...
cl::opt< std::string > PrintBranchProbFuncName("print-bpi-func-name", cl::Hidden, cl::desc("The option to specify the name of the function " "whose branch probability info is printed."))
static cl::opt< bool > PrintBranchProb("print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info."))
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > & Cond
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This templated class represents "all analyses that operate over " (e....
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
const DataLayout & getDataLayout() const
Get the data layout of the module this basic block belongs to.
bool isEHPad() const
Return true if this basic block is an exception handling block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Conditional or Unconditional Branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
Value * getCondition() const
Analysis pass which computes BranchProbabilityInfo.
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
Legacy analysis pass which computes BranchProbabilityInfo.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
void getSccEnterBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Enters) const
Fills in Enters vector with all such blocks that don't belong to SCC with SccNum ID but there is an e...
SccInfo(const Function &F)
void getSccExitBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Exits) const
Fills in Exits vector with all such blocks that don't belong to SCC with SccNum ID but there is an ed...
int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
Analysis providing branch probability information.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
void swapSuccEdgesProbabilities(const BasicBlock *Src)
Swap outgoing edges probabilities for Src with branch terminator.
void print(raw_ostream &OS) const
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
static uint32_t getDenominator()
static BranchProbability getRaw(uint32_t N)
static BranchProbability getOne()
static BranchProbability getUnknown()
uint32_t getNumerator() const
static BranchProbability getZero()
Represents analyses that only rely on functions' control flow.
This class represents a function call, abstracting a target machine's calling convention.
This class is the base class for the comparison instructions.
@ ICMP_SLT
signed less than
@ ICMP_SGT
signed greater than
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getPredicate() const
Return the predicate for this instruction.
This is the shared class of boolean and integer constants.
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
This is an important base class in LLVM.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Analysis pass which computes a DominatorTree.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate Pred)
FunctionPass class - This class is used to implement most global optimizations.
This instruction compares its operands according to the predicate given to the constructor.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
BasicBlock * getSuccessor(unsigned Idx) const LLVM_READONLY
Return the specified successor. This instruction must be a terminator.
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
A Module instance is used to store all the information related to an LLVM module.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
bool isPointerTy() const
True if this is an instance of PointerType.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
StringRef getName() const
Return a constant reference to the value's name.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
BlockType
Used as immediate MachineOperands for block signatures.
initializer< Ty > init(const Ty &Val)
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
auto pred_end(const MachineBasicBlock *BB)
auto successors(const MachineBasicBlock *BB)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Constant * ConstantFoldCompareInstOperands(unsigned Predicate, Constant *LHS, Constant *RHS, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr, const Instruction *I=nullptr)
Attempt to constant fold a compare instruction (icmp/fcmp) with the specified operands.
iterator_range< po_iterator< T > > post_order(const T &G)
void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry &)
constexpr T divideNearest(U Numerator, V Denominator)
Returns (Numerator / Denominator) rounded by round-half-up.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
MDNode * getValidBranchWeightMDNode(const Instruction &I)
Get the valid branch weights metadata node.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
auto succ_size(const MachineBasicBlock *BB)
Constant * ConstantFoldBinaryOpOperands(unsigned Opcode, Constant *LHS, Constant *RHS, const DataLayout &DL)
Attempt to constant fold a binary operation with the specified operands.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
@ Mul
Product of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto pred_begin(const MachineBasicBlock *BB)
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
A special type used by analysis passes to provide an address that identifies that particular analysis...