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)
69 "Branch Probability Analysis", false, true)
70
73
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
98
99
100
101
102
103
105
106
107
114
117
118
123
124
131
132
139
140
147
148
153
154
155
156
157
158
159
160
165
166
169
170
172
173
174
176
185
186
191
192
193
195
197
199
201
203
205
206
208
209
211};
212
214
215
216
217 int SccNum = 0;
219 ++It, ++SccNum) {
220
221
222 const std::vector<const BasicBlock *> &Scc = *It;
223 if (Scc.size() == 1)
224 continue;
225
227 for (const auto *BB : Scc) {
229 SccNums[BB] = SccNum;
230 calculateSccBlockType(BB, SccNum);
231 }
233 }
234}
235
237 auto SccIt = SccNums.find(BB);
238 if (SccIt == SccNums.end())
239 return -1;
240 return SccIt->second;
241}
242
245
246 for (auto MapIt : SccBlocks[SccNum]) {
247 const auto *BB = MapIt.first;
252 }
253}
254
257 for (auto MapIt : SccBlocks[SccNum]) {
258 const auto *BB = MapIt.first;
260 for (const auto *Succ : successors(BB))
263 }
264}
265
266uint32_t BranchProbabilityInfo::SccInfo::getSccBlockType(const BasicBlock *BB,
267 int SccNum) const {
268 assert(getSCCNum(BB) == SccNum);
269
270 assert(SccBlocks.size() > static_cast<unsigned>(SccNum) && "Unknown SCC");
271 const auto &SccBlockTypes = SccBlocks[SccNum];
272
273 auto It = SccBlockTypes.find(BB);
274 if (It != SccBlockTypes.end()) {
275 return It->second;
276 }
277 return Inner;
278}
279
280void BranchProbabilityInfo::SccInfo::calculateSccBlockType(const BasicBlock *BB,
281 int SccNum) {
282 assert(getSCCNum(BB) == SccNum);
284
286
287
288 return getSCCNum(Pred) != SccNum;
289 }))
290 BlockType |= Header;
291
293 return getSCCNum(Succ) != SccNum;
294 }))
295 BlockType |= Exiting;
296
297
298
299 if (SccBlocks.size() <= static_cast<unsigned>(SccNum))
300 SccBlocks.resize(SccNum + 1);
301 auto &SccBlockTypes = SccBlocks[SccNum];
302
303 if (BlockType != Inner) {
304 bool IsInserted;
305 std::tie(std::ignore, IsInserted) =
306 SccBlockTypes.insert(std::make_pair(BB, BlockType));
307 assert(IsInserted && "Duplicated block in SCC");
308 }
309}
310
311BranchProbabilityInfo::LoopBlock::LoopBlock(const BasicBlock *BB,
312 const LoopInfo &LI,
314 : BB(BB) {
316 if (.first) {
317 LD.second = SccI.getSCCNum(BB);
318 }
319}
320
321bool BranchProbabilityInfo::isLoopEnteringEdge(const LoopEdge &Edge) const {
322 const auto &SrcBlock = Edge.first;
323 const auto &DstBlock = Edge.second;
324 return (DstBlock.getLoop() &&
325 !DstBlock.getLoop()->contains(SrcBlock.getLoop())) ||
326
327 (DstBlock.getSccNum() != -1 &&
328 SrcBlock.getSccNum() != DstBlock.getSccNum());
329}
330
331bool BranchProbabilityInfo::isLoopExitingEdge(const LoopEdge &Edge) const {
332 return isLoopEnteringEdge({Edge.second, Edge.first});
333}
334
335bool BranchProbabilityInfo::isLoopEnteringExitingEdge(
336 const LoopEdge &Edge) const {
337 return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge);
338}
339
340bool BranchProbabilityInfo::isLoopBackEdge(const LoopEdge &Edge) const {
341 const auto &SrcBlock = Edge.first;
342 const auto &DstBlock = Edge.second;
343 return SrcBlock.belongsToSameLoop(DstBlock) &&
344 ((DstBlock.getLoop() &&
345 DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) ||
346 (DstBlock.getSccNum() != -1 &&
347 SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum())));
348}
349
350void BranchProbabilityInfo::getLoopEnterBlocks(
351 const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Enters) const {
352 if (LB.getLoop()) {
353 auto *Header = LB.getLoop()->getHeader();
355 } else {
356 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?");
357 SccI->getSccEnterBlocks(LB.getSccNum(), Enters);
358 }
359}
360
361void BranchProbabilityInfo::getLoopExitBlocks(
362 const LoopBlock &LB, SmallVectorImpl<BasicBlock *> &Exits) const {
363 if (LB.getLoop()) {
364 LB.getLoop()->getExitBlocks(Exits);
365 } else {
366 assert(LB.getSccNum() != -1 && "LB doesn't belong to any loop?");
367 SccI->getSccExitBlocks(LB.getSccNum(), Exits);
368 }
369}
370
371
372
373
374
375bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
380 return false;
381
383 if (!WeightsNode)
384 return false;
385
386
388
389
390
391
392 uint64_t WeightSum = 0;
394 SmallVector<unsigned, 2> UnreachableIdxs;
395 SmallVector<unsigned, 2> ReachableIdxs;
396
398 for (unsigned I = 0, E = Weights.size(); I != E; ++I) {
399 WeightSum += Weights[I];
400 const LoopBlock SrcLoopBB = getLoopBlock(BB);
401 const LoopBlock DstLoopBB = getLoopBlock(TI->getSuccessor(I));
402 auto EstimatedWeight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
403 if (EstimatedWeight &&
406 else
408 }
410
411
412
413 uint64_t ScalingFactor =
414 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
415
416 if (ScalingFactor > 1) {
417 WeightSum = 0;
419 Weights[I] /= ScalingFactor;
420 WeightSum += Weights[I];
421 }
422 }
423 assert(WeightSum <= UINT32_MAX &&
424 "Expected weights to scale down to 32 bits");
425
426 if (WeightSum == 0 || ReachableIdxs.size() == 0) {
428 Weights[I] = 1;
430 }
431
432
435 BP.push_back({ Weights[I], static_cast<uint32_t>(WeightSum) });
436
437
438
439 if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {
441 return true;
442 }
443
445 for (auto I : UnreachableIdxs)
446 if (UnreachableProb < BP[I]) {
447 BP[I] = UnreachableProb;
448 }
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
471 for (auto I : UnreachableIdxs)
472 NewUnreachableSum += BP[I];
473
474 BranchProbability NewReachableSum =
476
478 for (auto I : ReachableIdxs)
479 OldReachableSum += BP[I];
480
481 if (OldReachableSum != NewReachableSum) {
482 if (OldReachableSum.isZero()) {
483
484
485
486 BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size();
487 for (auto I : ReachableIdxs)
488 BP[I] = PerEdge;
489 } else {
490 for (auto I : ReachableIdxs) {
491
492
493
494
495 uint64_t Mul = static_cast<uint64_t>(NewReachableSum.getNumerator()) *
496 BP[I].getNumerator();
497 uint32_t Div = static_cast<uint32_t>(
500 }
501 }
502 }
503
505
506 return true;
507}
508
509
510
511bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
514 return false;
515
519 return false;
520
522
524 return false;
525
527
530 return false;
532 return true;
533}
534
535
536
537
538static void
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
564 return;
565
566
570 return;
571
572
573
574
578
582
583 if (!L->contains(CmpLHS))
584 return;
587 if (CmpLHS)
589 }
590 if (!CmpPHI || !L->contains(CmpPHI))
591 return;
592
593
597 VisitedInsts.insert(CmpPHI);
598 while (!WorkList.empty()) {
601
602 if (!L->contains(B))
603 continue;
604 Value *V = P->getIncomingValueForBlock(B);
605
606
608 if (VisitedInsts.insert(PN).second)
610 continue;
611 }
612
613
614
617 continue;
618
623 if (!CmpLHSConst)
624 break;
625 }
626 if (!CmpLHSConst)
627 continue;
628
631
632
633 if (Result &&
634 ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
635 (Result->isOneValue() && B == BI->getSuccessor(1))))
637 }
638 }
639}
640
641std::optional<uint32_t>
642BranchProbabilityInfo::getEstimatedBlockWeight(const BasicBlock *BB) const {
643 auto WeightIt = EstimatedBlockWeight.find(BB);
644 if (WeightIt == EstimatedBlockWeight.end())
645 return std::nullopt;
646 return WeightIt->second;
647}
648
649std::optional<uint32_t>
650BranchProbabilityInfo::getEstimatedLoopWeight(const LoopData &L) const {
651 auto WeightIt = EstimatedLoopWeight.find(L);
652 if (WeightIt == EstimatedLoopWeight.end())
653 return std::nullopt;
654 return WeightIt->second;
655}
656
657std::optional<uint32_t>
658BranchProbabilityInfo::getEstimatedEdgeWeight(const LoopEdge &Edge) const {
659
660
661 return isLoopEnteringEdge(Edge)
662 ? getEstimatedLoopWeight(Edge.second.getLoopData())
663 : getEstimatedBlockWeight(Edge.second.getBlock());
664}
665
666template
667std::optional<uint32_t> BranchProbabilityInfo::getMaxEstimatedEdgeWeight(
669 std::optional<uint32_t> MaxWeight;
670 for (const BasicBlock *DstBB : Successors) {
671 const LoopBlock DstLoopBB = getLoopBlock(DstBB);
672 auto Weight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
673
674 if (!Weight)
675 return std::nullopt;
676
677 if (!MaxWeight || *MaxWeight < *Weight)
678 MaxWeight = Weight;
679 }
680
681 return MaxWeight;
682}
683
684
685
686
687
688
689bool BranchProbabilityInfo::updateEstimatedBlockWeight(
690 LoopBlock &LoopBB, uint32_t BBWeight,
691 SmallVectorImpl<BasicBlock *> &BlockWorkList,
692 SmallVectorImpl &LoopWorkList) {
694
695
696
697
698
699
700 if (!EstimatedBlockWeight.insert({BB, BBWeight}).second)
701 return false;
702
703 for (BasicBlock *PredBlock : predecessors(BB)) {
704 LoopBlock PredLoop = getLoopBlock(PredBlock);
705
706 if (isLoopExitingEdge({PredLoop, LoopBB})) {
707 if (!EstimatedLoopWeight.count(PredLoop.getLoopData()))
708 LoopWorkList.push_back(PredLoop);
709 } else if (!EstimatedBlockWeight.count(PredBlock))
710 BlockWorkList.push_back(PredBlock);
711 }
712 return true;
713}
714
715
716
717
718
719
720
721
722
723
724
725
726
727void BranchProbabilityInfo::propagateEstimatedBlockWeight(
728 const LoopBlock &LoopBB, DominatorTree *DT, PostDominatorTree *PDT,
729 uint32_t BBWeight, SmallVectorImpl<BasicBlock *> &BlockWorkList,
730 SmallVectorImpl &LoopWorkList) {
731 const BasicBlock *BB = LoopBB.getBlock();
732 const auto *DTStartNode = DT->getNode(BB);
733 const auto *PDTStartNode = PDT->getNode(BB);
734
735
736 for (const auto *DTNode = DTStartNode; DTNode != nullptr;
737 DTNode = DTNode->getIDom()) {
738 auto *DomBB = DTNode->getBlock();
739
741
742
743 break;
744
745 LoopBlock DomLoopBB = getLoopBlock(DomBB);
746 const LoopEdge Edge{DomLoopBB, LoopBB};
747
748 if (!isLoopEnteringExitingEdge(Edge)) {
749 if (!updateEstimatedBlockWeight(DomLoopBB, BBWeight, BlockWorkList,
750 LoopWorkList))
751
752
753 break;
754 } else if (isLoopExitingEdge(Edge)) {
755 LoopWorkList.push_back(DomLoopBB);
756 }
757 }
758}
759
760std::optional<uint32_t>
761BranchProbabilityInfo::getInitialEstimatedBlockWeight(const BasicBlock *BB) {
762
763 auto hasNoReturn = [&](const BasicBlock *BB) {
764 for (const auto &I : reverse(*BB))
766 if (CI->hasFnAttr(Attribute::NoReturn))
767 return true;
768
769 return false;
770 };
771
772
773
774
776
777
778
779
781 return hasNoReturn(BB)
784
785
788
789
792 if (CI->hasFnAttr(Attribute::Cold))
794
795 return std::nullopt;
796}
797
798
799
800
801void BranchProbabilityInfo::estimateBlockWeights(const Function &F,
802 DominatorTree *DT,
803 PostDominatorTree *PDT) {
804 SmallVector<BasicBlock *, 8> BlockWorkList;
806 SmallDenseMap<LoopData, SmallVector<BasicBlock *, 4>> LoopExitBlocks;
807
808
809
810 ReversePostOrderTraversal<const Function *> RPOT(&F);
811 for (const auto *BB : RPOT)
812 if (auto BBWeight = getInitialEstimatedBlockWeight(BB))
813
814
815 propagateEstimatedBlockWeight(getLoopBlock(BB), DT, PDT, *BBWeight,
816 BlockWorkList, LoopWorkList);
817
818
819
820
821
822 do {
823 while (!LoopWorkList.empty()) {
824 const LoopBlock LoopBB = LoopWorkList.pop_back_val();
825 const LoopData LD = LoopBB.getLoopData();
826 if (EstimatedLoopWeight.count(LD))
827 continue;
828
829 auto Res = LoopExitBlocks.try_emplace(LD);
830 SmallVectorImpl<BasicBlock *> &Exits = Res.first->second;
831 if (Res.second)
832 getLoopExitBlocks(LoopBB, Exits);
833 auto LoopWeight = getMaxEstimatedEdgeWeight(
835
836 if (LoopWeight) {
837
840
841 EstimatedLoopWeight.insert({LD, *LoopWeight});
842
843 getLoopEnterBlocks(LoopBB, BlockWorkList);
844 }
845 }
846
847 while (!BlockWorkList.empty()) {
848
850 if (EstimatedBlockWeight.count(BB))
851 continue;
852
853
854
855
856
857
858
859 const LoopBlock LoopBB = getLoopBlock(BB);
860 auto MaxWeight = getMaxEstimatedEdgeWeight(LoopBB, successors(BB));
861
862 if (MaxWeight)
863 propagateEstimatedBlockWeight(LoopBB, DT, PDT, *MaxWeight,
864 BlockWorkList, LoopWorkList);
865 }
866 } while (!BlockWorkList.empty() || !LoopWorkList.empty());
867}
868
869
870
871
872bool BranchProbabilityInfo::calcEstimatedHeuristics(const BasicBlock *BB) {
874 "expected more than one successor!");
875
876 const LoopBlock LoopBB = getLoopBlock(BB);
877
878 SmallPtrSet<const BasicBlock *, 8> UnlikelyBlocks;
880 if (LoopBB.getLoop())
882
883
884 bool FoundEstimatedWeight = false;
885 SmallVector<uint32_t, 4> SuccWeights;
886 uint64_t TotalWeight = 0;
887
888 for (const BasicBlock *SuccBB : successors(BB)) {
889 std::optional<uint32_t> Weight;
890 const LoopBlock SuccLoopBB = getLoopBlock(SuccBB);
891 const LoopEdge Edge{LoopBB, SuccLoopBB};
892
893 Weight = getEstimatedEdgeWeight(Edge);
894
895 if (isLoopExitingEdge(Edge) &&
896
898
899 Weight = std::max(
902 TC);
903 }
904 bool IsUnlikelyEdge = LoopBB.getLoop() && UnlikelyBlocks.contains(SuccBB);
905 if (IsUnlikelyEdge &&
906
908
909 Weight = std::max(
912 }
913
914 if (Weight)
915 FoundEstimatedWeight = true;
916
917 auto WeightVal =
919 TotalWeight += WeightVal;
920 SuccWeights.push_back(WeightVal);
921 }
922
923
924
925
926 if (!FoundEstimatedWeight || TotalWeight == 0)
927 return false;
928
930 const unsigned SuccCount = SuccWeights.size();
931
932
933
934 if (TotalWeight > UINT32_MAX) {
935 uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1;
936 TotalWeight = 0;
937 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
938 SuccWeights[Idx] /= ScalingFactor;
940 SuccWeights[Idx] =
942 TotalWeight += SuccWeights[Idx];
943 }
944 assert(TotalWeight <= UINT32_MAX && "Total weight overflows");
945 }
946
947
950
951 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
952 EdgeProbabilities[Idx] =
953 BranchProbability(SuccWeights[Idx], (uint32_t)TotalWeight);
954 }
956 return true;
957}
958
959bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
960 const TargetLibraryInfo *TLI) {
963 return false;
964
967 if (!CI)
968 return false;
969
970 auto GetConstantInt = [](Value *V) {
974 };
975
977 ConstantInt *CV = GetConstantInt(RHS);
978 if (!CV)
979 return false;
980
981
982
984 if (LHS->getOpcode() == Instruction::And)
985 if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(1)))
986 if (AndRHS->getValue().isPowerOf2())
987 return false;
988
989
990 LibFunc Func = LibFunc::NotLibFunc;
991 if (TLI)
995
996 ProbabilityTable::const_iterator Search;
997 if (Func == LibFunc_strcasecmp ||
998 Func == LibFunc_strcmp ||
999 Func == LibFunc_strncasecmp ||
1000 Func == LibFunc_strncmp ||
1001 Func == LibFunc_memcmp ||
1002 Func == LibFunc_bcmp) {
1005 return false;
1006 } else if (CV->isZero()) {
1009 return false;
1010 } else if (CV->isOne()) {
1013 return false;
1017 return false;
1018 } else {
1019 return false;
1020 }
1021
1023 return true;
1024}
1025
1026bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
1029 return false;
1030
1033 if (!FCmp)
1034 return false;
1035
1039
1041
1043 } else {
1046 return false;
1047 ProbList = Search->second;
1048 }
1049
1051 return true;
1052}
1053
1055 Probs.clear();
1056 Handles.clear();
1057}
1058
1060 FunctionAnalysisManager::Invalidator &) {
1061
1062
1066}
1067
1069 OS << "---- Branch Probabilities ----\n";
1070
1071
1072 assert(LastF && "Cannot print prior to running over a function");
1073 for (const auto &BI : *LastF) {
1076 }
1077}
1078
1085
1086
1087
1088
1089
1092 unsigned IndexInSuccessors) const {
1093 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
1094 assert((Probs.end() == Probs.find(std::make_pair(Src, 0))) ==
1095 (Probs.end() == I) &&
1096 "Probability for I-th successor must always be defined along with the "
1097 "probability for the first successor");
1098
1099 if (I != Probs.end())
1100 return I->second;
1101
1103}
1104
1110
1111
1112
1116 if (!Probs.count(std::make_pair(Src, 0)))
1118
1121 if (*I == Dst)
1122 Prob += Probs.find(std::make_pair(Src, I.getSuccessorIndex()))->second;
1123
1124 return Prob;
1125}
1126
1127
1130 assert(Src->getTerminator()->getNumSuccessors() == Probs.size());
1131 eraseBlock(Src);
1132 if (Probs.size() == 0)
1133 return;
1134
1135 Handles.insert(BasicBlockCallbackVH(Src, this));
1136 uint64_t TotalNumerator = 0;
1137 for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {
1138 this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx];
1139 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << SuccIdx
1140 << " successor probability to " << Probs[SuccIdx]
1141 << "\n");
1142 TotalNumerator += Probs[SuccIdx].getNumerator();
1143 }
1144
1145
1146
1147
1148
1149
1152 (void)TotalNumerator;
1153}
1154
1157 eraseBlock(Dst);
1158 unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors();
1159 assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors());
1160 if (NumSuccessors == 0)
1161 return;
1162 if (!this->Probs.contains(std::make_pair(Src, 0)))
1163 return;
1164
1165 Handles.insert(BasicBlockCallbackVH(Dst, this));
1166 for (unsigned SuccIdx = 0; SuccIdx < NumSuccessors; ++SuccIdx) {
1167 auto Prob = this->Probs[std::make_pair(Src, SuccIdx)];
1168 this->Probs[std::make_pair(Dst, SuccIdx)] = Prob;
1169 LLVM_DEBUG(dbgs() << "set edge " << Dst->getName() << " -> " << SuccIdx
1170 << " successor probability to " << Prob << "\n");
1171 }
1172}
1173
1175 assert(Src->getTerminator()->getNumSuccessors() == 2);
1176 auto It0 = Probs.find(std::make_pair(Src, 0));
1177 if (It0 == Probs.end())
1178 return;
1179 auto It1 = Probs.find(std::make_pair(Src, 1));
1180 assert(It1 != Probs.end());
1181 std::swap(It0->second, It1->second);
1182}
1183
1189 OS << "edge ";
1190 Src->printAsOperand(OS, false, Src->getModule());
1191 OS << " -> ";
1192 Dst->printAsOperand(OS, false, Dst->getModule());
1193 OS << " probability is " << Prob
1194 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
1195
1196 return OS;
1197}
1198
1201
1202
1203
1204
1205
1206
1207
1208
1209 Handles.erase(BasicBlockCallbackVH(BB, this));
1210 for (unsigned I = 0;; ++I) {
1211 auto MapI = Probs.find(std::make_pair(BB, I));
1212 if (MapI == Probs.end()) {
1213 assert(Probs.count(std::make_pair(BB, I + 1)) == 0 &&
1214 "Must be no more successors");
1215 return;
1216 }
1217 Probs.erase(MapI);
1218 }
1219}
1220
1225 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
1226 << " ----\n\n");
1227 LastF = &F;
1228 LI = &LoopI;
1229
1230 SccI = std::make_unique(F);
1231
1232 assert(EstimatedBlockWeight.empty());
1233 assert(EstimatedLoopWeight.empty());
1234
1235 std::unique_ptr DTPtr;
1236 std::unique_ptr PDTPtr;
1237
1238 if (!DT) {
1239 DTPtr = std::make_unique(const_cast<Function &>(F));
1240 DT = DTPtr.get();
1241 }
1242
1243 if (!PDT) {
1244 PDTPtr = std::make_unique(const_cast<Function &>(F));
1245 PDT = PDTPtr.get();
1246 }
1247
1248 estimateBlockWeights(F, DT, PDT);
1249
1250
1251
1252 for (const auto *BB : post_order(&F.getEntryBlock())) {
1254 << "\n");
1255
1257 continue;
1258 if (calcMetadataWeights(BB))
1259 continue;
1260 if (calcEstimatedHeuristics(BB))
1261 continue;
1262 if (calcPointerHeuristics(BB))
1263 continue;
1264 if (calcZeroHeuristics(BB, TLI))
1265 continue;
1266 if (calcFloatingPointHeuristics(BB))
1267 continue;
1268 }
1269
1270 EstimatedLoopWeight.clear();
1271 EstimatedBlockWeight.clear();
1272 SccI.reset();
1273
1277 }
1278}
1279
1292
1300 BPI.calculate(F, LI, &TLI, &DT, &PDT);
1301 return false;
1302}
1303
1305
1307 const Module *) const {
1308 BPI.print(OS);
1309}
1310
1311AnalysisKey BranchProbabilityAnalysis::Key;
1319 BPI.calculate(F, LI, &TLI, &DT, &PDT);
1320 return BPI;
1321}
1322
1325 OS << "Printing analysis 'Branch Probability Analysis' for function '"
1326 << F.getName() << "':\n";
1329}
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
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.
Definition BranchProbabilityInfo.cpp:194
@ NORETURN
Weight to a block containing non returning call.
Definition BranchProbabilityInfo.cpp:202
@ UNWIND
Weight to 'unwind' block of an invoke instruction.
Definition BranchProbabilityInfo.cpp:204
@ COLD
Weight to a 'cold' block.
Definition BranchProbabilityInfo.cpp:207
@ ZERO
Special weight used for cases with exact zero probability.
Definition BranchProbabilityInfo.cpp:196
@ UNREACHABLE
Weight to an 'unreachable' block.
Definition BranchProbabilityInfo.cpp:200
@ DEFAULT
Default weight is used in cases when there is no dedicated execution weight set.
Definition BranchProbabilityInfo.cpp:210
@ LOWEST_NON_ZERO
Minimal possible non zero weight.
Definition BranchProbabilityInfo.cpp:198
static const uint32_t FPH_TAKEN_WEIGHT
Definition BranchProbabilityInfo.cpp:167
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
Definition BranchProbabilityInfo.cpp:96
static const uint32_t ZH_NONTAKEN_WEIGHT
Definition BranchProbabilityInfo.cpp:126
static const ProbabilityTable ICmpWithLibCallTable
strcmp and similar functions return zero, negative, or positive, if the first string is equal,...
Definition BranchProbabilityInfo.cpp:161
static const ProbabilityTable ICmpWithMinusOneTable
Integer compares with -1:
Definition BranchProbabilityInfo.cpp:141
static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
static const ProbabilityTable ICmpWithZeroTable
Integer compares with 0:
Definition BranchProbabilityInfo.cpp:133
static const uint32_t PH_NONTAKEN_WEIGHT
Definition BranchProbabilityInfo.cpp:109
std::map< CmpInst::Predicate, ProbabilityList > ProbabilityTable
Definition BranchProbabilityInfo.cpp:116
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)
Definition BranchProbabilityInfo.cpp:108
static const BranchProbability FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
static const BranchProbability PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
SmallVector< BranchProbability > ProbabilityList
Definition BranchProbabilityInfo.cpp:115
static const ProbabilityTable ICmpWithOneTable
Integer compares with 1:
Definition BranchProbabilityInfo.cpp:149
static const uint32_t ZH_TAKEN_WEIGHT
Zero Heuristics (ZH)
Definition BranchProbabilityInfo.cpp:125
static const uint32_t FPH_NONTAKEN_WEIGHT
Definition BranchProbabilityInfo.cpp:168
static const BranchProbability UR_TAKEN_PROB
Unreachable-terminating branch taken probability.
Definition BranchProbabilityInfo.cpp:104
static const ProbabilityTable FCmpTable
Floating-Point compares:
Definition BranchProbabilityInfo.cpp:187
static const uint32_t LBH_NONTAKEN_WEIGHT
Definition BranchProbabilityInfo.cpp:97
static const ProbabilityTable PointerTable
Pointer comparisons:
Definition BranchProbabilityInfo.cpp:119
static const uint32_t FPH_ORD_WEIGHT
This is the probability for an ordered floating point comparison.
Definition BranchProbabilityInfo.cpp:171
static void computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, SmallPtrSetImpl< const BasicBlock * > &UnlikelyBlocks)
Definition BranchProbabilityInfo.cpp:539
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...
Definition BranchProbabilityInfo.cpp:175
static 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< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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...
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 ...
This file defines the SmallVector class.
This templated class represents "all analyses that operate over " (e....
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.
LLVM_ABI const CallInst * getTerminatingDeoptimizeCall() const
Returns the call instruction calling @llvm.experimental.deoptimize prior to the terminating return in...
LLVM_ABI 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.
LLVM_ABI BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
Definition BranchProbabilityInfo.cpp:1313
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...
Definition BranchProbabilityInfo.cpp:1304
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition BranchProbabilityInfo.cpp:1280
BranchProbabilityInfoWrapperPass()
Definition BranchProbabilityInfo.cpp:71
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
Definition BranchProbabilityInfo.cpp:1293
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
Definition BranchProbabilityInfo.cpp:1306
bool isSCCHeader(const BasicBlock *BB, int SccNum) const
Returns true if BB is a 'header' block in SCC with SccNum ID, false otherwise.
LLVM_ABI 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...
Definition BranchProbabilityInfo.cpp:243
bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const
Returns true if BB is an 'exiting' block in SCC with SccNum ID, false otherwise.
LLVM_ABI SccInfo(const Function &F)
Definition BranchProbabilityInfo.cpp:213
LLVM_ABI 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...
Definition BranchProbabilityInfo.cpp:255
LLVM_ABI int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
Definition BranchProbabilityInfo.cpp:236
Analysis providing branch probability information.
LLVM_ABI void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
Definition BranchProbabilityInfo.cpp:1199
LLVM_ABI void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
Definition BranchProbabilityInfo.cpp:1128
LLVM_ABI bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Definition BranchProbabilityInfo.cpp:1059
LLVM_ABI BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
Definition BranchProbabilityInfo.cpp:1091
LLVM_ABI void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
Definition BranchProbabilityInfo.cpp:1221
LLVM_ABI void releaseMemory()
Definition BranchProbabilityInfo.cpp:1054
LLVM_ABI bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
Definition BranchProbabilityInfo.cpp:1080
LLVM_ABI void swapSuccEdgesProbabilities(const BasicBlock *Src)
Swap outgoing edges probabilities for Src with branch terminator.
Definition BranchProbabilityInfo.cpp:1174
LLVM_ABI void print(raw_ostream &OS) const
Definition BranchProbabilityInfo.cpp:1068
LLVM_ABI raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
Definition BranchProbabilityInfo.cpp:1185
LLVM_ABI void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
Definition BranchProbabilityInfo.cpp:1155
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition BranchProbabilityInfo.cpp:1324
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.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
This class is the base class for the comparison instructions.
@ ICMP_SLT
signed less than
@ ICMP_SGT
signed greater than
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
bool isTrueWhenEqual() const
This is just a convenience.
Predicate getPredicate() const
Return the predicate for this instruction.
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.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
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.
static bool isEquality(Predicate Pred)
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
LLVM_ABI unsigned getNumSuccessors() const LLVM_READONLY
Return the number of successors that this instruction has.
LLVM_ABI 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.
AnalysisType & getAnalysis() const
getAnalysis() - This function is used by subclasses to get to the analysis information ...
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
LLVM_ABI 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.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
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.
bool isAtEnd() const
Direct loop termination test which is more efficient than comparison with end().
@ BasicBlock
Various leaf nodes.
initializer< Ty > init(const Ty &Val)
NodeAddr< FuncNode * > Func
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
FunctionAddr VTableAddr Value
auto pred_end(const MachineBasicBlock *BB)
decltype(auto) dyn_cast(const From &Val)
dyn_cast - Return the argument parameter cast to the specified type.
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.
LLVM_ABI 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)
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)
LLVM_ABI MDNode * getValidBranchWeightMDNode(const Instruction &I)
Get the valid branch weights metadata node.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
auto succ_size(const MachineBasicBlock *BB)
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI 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)
iterator_range(Container &&) -> iterator_range< llvm::detail::IterOfRange< Container > >
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...
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
auto pred_begin(const MachineBasicBlock *BB)
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
SuccIterator< const Instruction, const BasicBlock > const_succ_iterator
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...