LLVM: include/llvm/Analysis/BlockFrequencyInfoImpl.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14#ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
15#define LLVM_ANALYSIS_BLOCKFREQUENCYINFOIMPL_H
16
38#include
39#include
40#include
41#include
42#include
43#include
44#include
45#include
46#include
47#include
48#include
49#include
50#include
51
52#define DEBUG_TYPE "block-freq"
53
54namespace llvm {
56
60
61class BranchProbabilityInfo;
62class Function;
63class Loop;
64class LoopInfo;
65class MachineBasicBlock;
66class MachineBranchProbabilityInfo;
67class MachineFunction;
68class MachineLoop;
69class MachineLoopInfo;
70
72
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
91
92public:
95
97
99 return BlockMass(std::numeric_limits<uint64_t>::max());
100 }
101
103
104 bool isFull() const { return Mass == std::numeric_limits<uint64_t>::max(); }
105 bool isEmpty() const { return !Mass; }
106
108
109
110
111
114 Mass = Sum < Mass ? std::numeric_limits<uint64_t>::max() : Sum;
115 return *this;
116 }
117
118
119
120
121
124 Mass = Diff > Mass ? 0 : Diff;
125 return *this;
126 }
127
129 Mass = P.scale(Mass);
130 return *this;
131 }
132
139
140
141
142
143
145
146 void dump() const;
148};
149
162
164 return X.print(OS);
165}
166
167}
168
169
170
171
172
173
174
175
176
178public:
181
182
183
184
185
186
187
188
191
193
196
203
205
207 return std::numeric_limits<uint32_t>::max() - 1;
208 }
209 };
210
211
216
217
218
219
220
225
227 bool IsPackaged = false;
234
237
238 template <class It1, class It2>
240 It2 LastOther)
243 Nodes.insert(Nodes.end(), FirstOther, LastOther);
245 }
246
253
256
258 assert(isHeader(B) && "this is only valid on loop header blocks");
262 return 0;
263 }
264
268
273 };
274
275
280
282
284
289
294 return Loop->Parent;
295 return Loop->Parent->Parent;
296 }
297
298
299
300
301
302
303
304
305
306
307
308
309
310
313 return L ? L->getHeader() : Node;
314 }
315
317 if ( ||
->IsPackaged)
318 return nullptr;
319 auto *L = Loop;
320 while (L->Parent && L->Parent->IsPackaged)
321 L = L->Parent;
322 return L;
323 }
324
325
326
327
328
329
334 return Loop->Mass;
335 return Loop->Parent->Mass;
336 }
337
338
340
341
343
344
348 };
349
350
351
352
353
354
355
356
357
358
359
360
361
362
373
374
375
376
377
378
379
380
381
384
387 bool DidOverflow = false;
388
390
394
398
402
403
404
405
406
407
408
409
410
411
413
414 private:
416 };
417
418
420
421
422
424
425
427
428
430
431
432
433
434
436
437
438
439
440
441
442
445
446
447
448
449
450
451
452
455
456
457
458
459
460
461
462
465 std::list::iterator Insert);
466
467
468
469
470
471
472
474
475
476
477
478
479
480
483
484
486
487
488
489
490
491
492
493
494
496
498
499
501
502
504
505
506
507
508
510
511
513
516
519
521
523 std::optional<uint64_t>
525 bool AllowSynthetic = false) const;
526 std::optional<uint64_t>
528 bool AllowSynthetic = false) const;
530
532
537};
538
539namespace bfi_detail {
540
541template struct TypeMap {};
558
559template <class BlockT, class BFIImplT>
561
562
563
564
565
566
567
568
569template std::string getBlockName(const BlockT *BB) {
570 assert(BB && "Unexpected nullptr");
571 auto MachineName = "BB" + Twine(BB->getNumber());
572 if (BB->getBasicBlock())
573 return (MachineName + "[" + BB->getName() + "]").str();
574 return MachineName.str();
575}
576
578 assert(BB && "Unexpected nullptr");
580}
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
598
600
605 std::deque<const IrrNode *> Edges;
606
608
609 using iterator = std::deque<const IrrNode *>::const_iterator;
610
615 };
620
621
622
623
624
625
626
627
628
629
630 template
632 BlockEdgesAdder addBlockEdges) : BFI(BFI) {
633 initialize(OuterLoop, addBlockEdges);
634 }
635
636 template
637 void initialize(const BFIBase::LoopData *OuterLoop,
638 BlockEdgesAdder addBlockEdges);
639 void addNodesInLoop(const BFIBase::LoopData &OuterLoop);
641
646
648 template
650 BlockEdgesAdder addBlockEdges);
652 const BFIBase::LoopData *OuterLoop);
653};
654
655template
657 BlockEdgesAdder addBlockEdges) {
658 if (OuterLoop) {
660 for (auto N : OuterLoop->Nodes)
661 addEdges(N, OuterLoop, addBlockEdges);
662 } else {
664 for (uint32_t Index = 0; Index < BFI.Working.size(); ++Index)
665 addEdges(Index, OuterLoop, addBlockEdges);
666 }
668}
669
670template
673 BlockEdgesAdder addBlockEdges) {
675 if (L == Lookup.end())
676 return;
677 IrrNode &Irr = *L->second;
678 const auto &Working = BFI.Working[Node.Index];
679
680 if (Working.isAPackage())
681 for (const auto &I : Working.Loop->Exits)
682 addEdge(Irr, I.first, OuterLoop);
683 else
684 addBlockEdges(*this, Irr, OuterLoop);
685}
686
687}
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
846 using BranchProbabilityInfoT =
852 using BFICallbackVH =
854
855 const BranchProbabilityInfoT *BPI = nullptr;
856 const LoopInfoT *LI = nullptr;
857 const FunctionT *F = nullptr;
858
859
860 std::vector<const BlockT *> RPOT;
862
863 using rpot_iterator = typename std::vector<const BlockT *>::const_iterator;
864
865 rpot_iterator rpot_begin() const { return RPOT.begin(); }
866 rpot_iterator rpot_end() const { return RPOT.end(); }
867
868 size_t getIndex(const rpot_iterator &I) const { return I - rpot_begin(); }
869
870 BlockNode getNode(const rpot_iterator &I) const {
872 }
873
874 BlockNode getNode(const BlockT *BB) const { return Nodes.lookup(BB).first; }
875
876 const BlockT *getBlock(const BlockNode &Node) const {
878 return RPOT[Node.Index];
879 }
880
881
882
883
884 void initializeRPOT();
885
886
887
888
889
890
891
892
893 void initializeLoops();
894
895
896
897
898
899
900
902
903
904
905
906
907
908
909
910
912
913
914
915
916
917
918
919
920
921 bool tryToComputeMassInFunction();
922
923
924
925
926
927
928
929
930
931
932
933
934
935 void computeIrreducibleMass(LoopData *OuterLoop,
936 std::list::iterator Insert);
937
938
939
940
941
942
943
944
945
946
947 void computeMassInLoops();
948
949
950
951
952
953
954
955 void computeMassInFunction();
956
957 std::string getBlockName(const BlockNode &Node) const override {
959 }
960
961
962
963
964
965
966
967
968
969
970
971 bool needIterativeInference() const;
972
973
974 void applyIterativeInference();
975
976 using ProbMatrixType = std::vector<std::vector<std::pair<size_t, Scaled64>>>;
977
978
979 void iterativeInference(const ProbMatrixType &ProbMatrix,
980 std::vector &Freq) const;
981
982
983
984 void findReachableBlocks(std::vector<const BlockT *> &Blocks) const;
985
986
987
988 void initTransitionProbabilities(
989 const std::vector<const BlockT *> &Blocks,
991 ProbMatrixType &ProbMatrix) const;
992
993#ifndef NDEBUG
994
995
996 Scaled64 discrepancy(const ProbMatrixType &ProbMatrix,
997 const std::vector &Freq) const;
998#endif
999
1000public:
1002
1004
1005 void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI,
1006 const LoopInfoT &LI);
1007
1009
1013
1014 std::optional<uint64_t>
1016 bool AllowSynthetic = false) const {
1018 AllowSynthetic);
1019 }
1020
1021 std::optional<uint64_t>
1023 bool AllowSynthetic = false) const {
1025 AllowSynthetic);
1026 }
1027
1031
1033
1035
1036
1037
1038 Nodes.erase(BB);
1039 }
1040
1044
1045 const BranchProbabilityInfoT &getBPI() const { return *BPI; }
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1059
1061
1063};
1064
1066
1067template
1069 BFIImplT *BFIImpl;
1070
1071public:
1073
1076
1078
1082};
1083
1084
1085
1086template
1092
1093}
1094
1095template
1097 const BranchProbabilityInfoT &BPI,
1098 const LoopInfoT &LI) {
1099
1100 this->BPI = &BPI;
1101 this->LI = &LI;
1102 this->F = &F;
1103
1104
1106 RPOT.clear();
1107 Nodes.clear();
1108
1109
1110 LLVM_DEBUG(dbgs() << "\nblock-frequency: " << F.getName()
1111 << "\n================="
1112 << std::string(F.getName().size(), '=') << "\n");
1113 initializeRPOT();
1114 initializeLoops();
1115
1116
1117
1118 computeMassInLoops();
1119 computeMassInFunction();
1121
1122
1123 if (needIterativeInference())
1124 applyIterativeInference();
1126
1128
1129
1130
1131 for (const BlockT &BB : F)
1132 if (!Nodes.count(&BB))
1134 }
1135}
1136
1137template
1140 auto [It, Inserted] = Nodes.try_emplace(BB);
1141 if (!Inserted)
1143 else {
1144
1145
1146
1148 It->second = {NewNode, BFICallbackVH(BB, this)};
1149 Freqs.emplace_back();
1151 }
1152}
1153
1154template void BlockFrequencyInfoImpl::initializeRPOT() {
1155 const BlockT *Entry = &F->front();
1156 RPOT.reserve(F->size());
1157 std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT));
1158 std::reverse(RPOT.begin(), RPOT.end());
1159
1160 assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
1161 "More nodes in function than Block Frequency Info supports");
1162
1163 LLVM_DEBUG(dbgs() << "reverse-post-order-traversal\n");
1164 for (rpot_iterator I = rpot_begin(), E = rpot_end(); I != E; ++I) {
1167 << "\n");
1168 Nodes[*I] = {Node, BFICallbackVH(*I, this)};
1169 }
1170
1171 Working.reserve(RPOT.size());
1172 for (size_t Index = 0; Index < RPOT.size(); ++Index)
1173 Working.emplace_back(Index);
1174 Freqs.resize(RPOT.size());
1175}
1176
1177template void BlockFrequencyInfoImpl::initializeLoops() {
1179 if (LI->empty())
1180 return;
1181
1182
1183 std::deque<std::pair<const LoopT *, LoopData *>> Q;
1184 for (const LoopT *L : *LI)
1185 Q.emplace_back(L, nullptr);
1186 while (!Q.empty()) {
1187 const LoopT *Loop = Q.front().first;
1188 LoopData *Parent = Q.front().second;
1189 Q.pop_front();
1190
1192 assert(Header.isValid());
1193
1194 Loops.emplace_back(Parent, Header);
1195 Working[Header.Index].Loop = &Loops.back();
1197
1198 for (const LoopT *L : *Loop)
1199 Q.emplace_back(L, &Loops.back());
1200 }
1201
1202
1203
1204 for (size_t Index = 0; Index < RPOT.size(); ++Index) {
1205
1206 if (Working[Index].isLoopHeader()) {
1207 LoopData *ContainingLoop = Working[Index].getContainingLoop();
1208 if (ContainingLoop)
1209 ContainingLoop->Nodes.push_back(Index);
1210 continue;
1211 }
1212
1213 const LoopT *Loop = LI->getLoopFor(RPOT[Index]);
1215 continue;
1216
1217
1219 assert(Header.isValid());
1220 const auto &HeaderData = Working[Header.Index];
1221 assert(HeaderData.isLoopHeader());
1222
1223 Working[Index].Loop = HeaderData.Loop;
1224 HeaderData.Loop->Nodes.push_back(Index);
1226 << ": member = " << getBlockName(Index) << "\n");
1227 }
1228}
1229
1230template void BlockFrequencyInfoImpl::computeMassInLoops() {
1231
1232 for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L) {
1233 if (computeMassInLoop(*L))
1234 continue;
1235 auto Next = std::next(L);
1236 computeIrreducibleMass(&*L, L.base());
1238 if (computeMassInLoop(*L))
1239 continue;
1241 }
1242}
1243
1244template
1245bool BlockFrequencyInfoImpl::computeMassInLoop(LoopData &Loop) {
1246
1247 LLVM_DEBUG(dbgs() << "compute-mass-in-loop: " << getLoopName(Loop) << "\n");
1248
1249 if (Loop.isIrreducible()) {
1251 Distribution Dist;
1252 unsigned NumHeadersWithWeight = 0;
1253 std::optional<uint64_t> MinHeaderWeight;
1255 HeadersWithoutWeight.reserve(Loop.NumHeaders);
1256 for (uint32_t H = 0; H < Loop.NumHeaders; ++H) {
1257 auto &HeaderNode = Loop.Nodes[H];
1258 const BlockT *Block = getBlock(HeaderNode);
1259 IsIrrLoopHeader.set(Loop.Nodes[H].Index);
1260 std::optional<uint64_t> HeaderWeight = Block->getIrrLoopHeaderWeight();
1261 if (!HeaderWeight) {
1262 LLVM_DEBUG(dbgs() << "Missing irr loop header metadata on "
1264 HeadersWithoutWeight.insert(H);
1265 continue;
1266 }
1268 << " has irr loop header weight " << *HeaderWeight
1269 << "\n");
1270 NumHeadersWithWeight++;
1271 uint64_t HeaderWeightValue = *HeaderWeight;
1272 if (!MinHeaderWeight || HeaderWeightValue < MinHeaderWeight)
1273 MinHeaderWeight = HeaderWeightValue;
1274 if (HeaderWeightValue) {
1275 Dist.addLocal(HeaderNode, HeaderWeightValue);
1276 }
1277 }
1278
1279
1280
1281
1282
1283
1284 if (!MinHeaderWeight)
1285 MinHeaderWeight = 1;
1286 for (uint32_t H : HeadersWithoutWeight) {
1287 auto &HeaderNode = Loop.Nodes[H];
1288 assert(!getBlock(HeaderNode)->getIrrLoopHeaderWeight() &&
1289 "Shouldn't have a weight metadata");
1290 uint64_t MinWeight = *MinHeaderWeight;
1291 LLVM_DEBUG(dbgs() << "Giving weight " << MinWeight << " to "
1293 if (MinWeight)
1294 Dist.addLocal(HeaderNode, MinWeight);
1295 }
1296 distributeIrrLoopHeaderMass(Dist);
1297 for (const BlockNode &M : Loop.Nodes)
1298 if (!propagateMassToSuccessors(&Loop, M))
1300 if (NumHeadersWithWeight == 0)
1301
1302 adjustLoopHeaderMass(Loop);
1303 } else {
1304 Working[Loop.getHeader().Index].getMass() = BlockMass::getFull();
1306 llvm_unreachable("irreducible control flow to loop header!?");
1307 for (const BlockNode &M : Loop.members())
1308 if (!propagateMassToSuccessors(&Loop, M))
1309
1310 return false;
1311 }
1312
1313 computeLoopScale(Loop);
1314 packageLoop(Loop);
1315 return true;
1316}
1317
1318template
1319bool BlockFrequencyInfoImpl::tryToComputeMassInFunction() {
1320
1322 assert(!Working.empty() && "no blocks in function");
1323 assert(!Working[0].isLoopHeader() && "entry block is a loop header");
1324
1325 Working[0].getMass() = BlockMass::getFull();
1326 for (rpot_iterator I = rpot_begin(), IE = rpot_end(); I != IE; ++I) {
1327
1329 if (Working[Node.Index].isPackaged())
1330 continue;
1331
1332 if (!propagateMassToSuccessors(nullptr, Node))
1333 return false;
1334 }
1335 return true;
1336}
1337
1338template void BlockFrequencyInfoImpl::computeMassInFunction() {
1339 if (tryToComputeMassInFunction())
1340 return;
1341 computeIrreducibleMass(nullptr, Loops.begin());
1342 if (tryToComputeMassInFunction())
1343 return;
1345}
1346
1347template
1348bool BlockFrequencyInfoImpl::needIterativeInference() const {
1350 return false;
1351 if (->getFunction().hasProfileData())
1352 return false;
1353
1354
1355 for (auto L = Loops.rbegin(), E = Loops.rend(); L != E; ++L) {
1356 if (L->isIrreducible())
1357 return true;
1358 }
1359 return false;
1360}
1361
1362template void BlockFrequencyInfoImpl::applyIterativeInference() {
1363
1364
1365
1366
1367 std::vector<const BlockT *> ReachableBlocks;
1368 findReachableBlocks(ReachableBlocks);
1369 if (ReachableBlocks.empty())
1370 return;
1371
1372
1373
1375
1376 auto Freq = std::vector(ReachableBlocks.size());
1377 Scaled64 SumFreq;
1378 for (size_t I = 0; I < ReachableBlocks.size(); I++) {
1379 const BlockT *BB = ReachableBlocks[I];
1380 BlockIndex[BB] = I;
1381 Freq[I] = getFloatingBlockFreq(BB);
1382 SumFreq += Freq[I];
1383 }
1384 assert(!SumFreq.isZero() && "empty initial block frequencies");
1385
1386 LLVM_DEBUG(dbgs() << "Applying iterative inference for " << F->getName()
1387 << " with " << ReachableBlocks.size() << " blocks\n");
1388
1389
1390 for (auto &Value : Freq) {
1391 Value /= SumFreq;
1392 }
1393
1394
1395
1396 ProbMatrixType ProbMatrix;
1397 initTransitionProbabilities(ReachableBlocks, BlockIndex, ProbMatrix);
1398
1399
1400 iterativeInference(ProbMatrix, Freq);
1401
1402
1403 for (const BlockT &BB : *F) {
1405 if (.isValid())
1406 continue;
1407 if (auto It = BlockIndex.find(&BB); It != BlockIndex.end())
1408 Freqs[Node.Index].Scaled = Freq[It->second];
1409 else
1410 Freqs[Node.Index].Scaled = Scaled64::getZero();
1411 }
1412}
1413
1414template
1415void BlockFrequencyInfoImpl::iterativeInference(
1416 const ProbMatrixType &ProbMatrix, std::vector &Freq) const {
1418 "incorrectly specified precision");
1419
1420 const auto Precision =
1423
1424#ifndef NDEBUG
1426 << discrepancy(ProbMatrix, Freq).toString() << "\n");
1427#endif
1428
1429
1430 auto Successors = std::vector<std::vector<size_t>>(Freq.size());
1431 for (size_t I = 0; I < Freq.size(); I++) {
1432 for (const auto &Jump : ProbMatrix[I]) {
1433 Successors[Jump.first].push_back(I);
1434 }
1435 }
1436
1437
1438
1439
1440
1441 auto IsActive = BitVector(Freq.size(), false);
1442 std::queue<size_t> ActiveSet;
1443 for (size_t I = 0; I < Freq.size(); I++) {
1444 if (Freq[I] > 0) {
1445 ActiveSet.push(I);
1446 IsActive[I] = true;
1447 }
1448 }
1449
1450
1451 size_t It = 0;
1452 while (It++ < MaxIterations && !ActiveSet.empty()) {
1453 size_t I = ActiveSet.front();
1454 ActiveSet.pop();
1455 IsActive[I] = false;
1456
1457
1458
1459
1460 Scaled64 NewFreq;
1461 Scaled64 OneMinusSelfProb = Scaled64::getOne();
1462 for (const auto &Jump : ProbMatrix[I]) {
1463 if (Jump.first == I) {
1464 OneMinusSelfProb -= Jump.second;
1465 } else {
1466 NewFreq += Freq[Jump.first] * Jump.second;
1467 }
1468 }
1469 if (OneMinusSelfProb != Scaled64::getOne())
1470 NewFreq /= OneMinusSelfProb;
1471
1472
1473
1474 auto Change = Freq[I] >= NewFreq ? Freq[I] - NewFreq : NewFreq - Freq[I];
1475 if (Change > Precision) {
1476 ActiveSet.push(I);
1477 IsActive[I] = true;
1478 for (size_t Succ : Successors[I]) {
1479 if (!IsActive[Succ]) {
1480 ActiveSet.push(Succ);
1481 IsActive[Succ] = true;
1482 }
1483 }
1484 }
1485
1486
1487 Freq[I] = NewFreq;
1488 }
1489
1490 LLVM_DEBUG(dbgs() << " Completed " << It << " inference iterations"
1491 << format(" (%0.0f per block)", double(It) / Freq.size())
1492 << "\n");
1493#ifndef NDEBUG
1495 << discrepancy(ProbMatrix, Freq).toString() << "\n");
1496#endif
1497}
1498
1499template
1500void BlockFrequencyInfoImpl::findReachableBlocks(
1501 std::vector<const BlockT *> &Blocks) const {
1502
1503
1504 std::queue<const BlockT *> Queue;
1506 const BlockT *Entry = &F->front();
1507 Queue.push(Entry);
1508 Reachable.insert(Entry);
1509 while (.empty()) {
1510 const BlockT *SrcBB = Queue.front();
1513 auto EP = BPI->getEdgeProbability(SrcBB, DstBB);
1514 if (EP.isZero())
1515 continue;
1516 if (Reachable.insert(DstBB).second)
1517 Queue.push(DstBB);
1518 }
1519 }
1520
1521
1522
1524 for (const BlockT &BB : *F) {
1525
1527 if (!HasSucc && Reachable.count(&BB)) {
1528 Queue.push(&BB);
1529 InverseReachable.insert(&BB);
1530 }
1531 }
1532 while (.empty()) {
1533 const BlockT *SrcBB = Queue.front();
1536 auto EP = BPI->getEdgeProbability(DstBB, SrcBB);
1537 if (EP.isZero())
1538 continue;
1539 if (InverseReachable.insert(DstBB).second)
1540 Queue.push(DstBB);
1541 }
1542 }
1543
1544
1545 Blocks.reserve(F->size());
1546 for (const BlockT &BB : *F) {
1547 if (Reachable.count(&BB) && InverseReachable.count(&BB)) {
1548 Blocks.push_back(&BB);
1549 }
1550 }
1551}
1552
1553template
1554void BlockFrequencyInfoImpl::initTransitionProbabilities(
1555 const std::vector<const BlockT *> &Blocks,
1557 ProbMatrixType &ProbMatrix) const {
1558 const size_t NumBlocks = Blocks.size();
1559 auto Succs = std::vector<std::vector<std::pair<size_t, Scaled64>>>(NumBlocks);
1560 auto SumProb = std::vector(NumBlocks);
1561
1562
1563 for (size_t Src = 0; Src < NumBlocks; Src++) {
1564 const BlockT *BB = Blocks[Src];
1567
1568 auto BlockIndexIt = BlockIndex.find(SI);
1569 if (BlockIndexIt == BlockIndex.end())
1570 continue;
1571
1572 if (!UniqueSuccs.insert(SI).second)
1573 continue;
1574
1575 auto EP = BPI->getEdgeProbability(BB, SI);
1576 if (EP.isZero())
1577 continue;
1578
1579 auto EdgeProb =
1580 Scaled64::getFraction(EP.getNumerator(), EP.getDenominator());
1581 size_t Dst = BlockIndexIt->second;
1582 Succs[Src].push_back(std::make_pair(Dst, EdgeProb));
1583 SumProb[Src] += EdgeProb;
1584 }
1585 }
1586
1587
1588 ProbMatrix = ProbMatrixType(NumBlocks);
1589 for (size_t Src = 0; Src < NumBlocks; Src++) {
1590
1591 if (Succs[Src].empty())
1592 continue;
1593
1594 assert(!SumProb[Src].isZero() && "Zero sum probability of non-exit block");
1595 for (auto &Jump : Succs[Src]) {
1596 size_t Dst = Jump.first;
1597 Scaled64 Prob = Jump.second;
1598 ProbMatrix[Dst].push_back(std::make_pair(Src, Prob / SumProb[Src]));
1599 }
1600 }
1601
1602
1603 size_t EntryIdx = BlockIndex.find(&F->front())->second;
1604 for (size_t Src = 0; Src < NumBlocks; Src++) {
1605 if (Succs[Src].empty()) {
1606 ProbMatrix[EntryIdx].push_back(std::make_pair(Src, Scaled64::getOne()));
1607 }
1608 }
1609}
1610
1611#ifndef NDEBUG
1612template
1614 const ProbMatrixType &ProbMatrix, const std::vector &Freq) const {
1615 assert(Freq[0] > 0 && "Incorrectly computed frequency of the entry block");
1616 Scaled64 Discrepancy;
1617 for (size_t I = 0; I < ProbMatrix.size(); I++) {
1618 Scaled64 Sum;
1619 for (const auto &Jump : ProbMatrix[I]) {
1620 Sum += Freq[Jump.first] * Jump.second;
1621 }
1622 Discrepancy += Freq[I] >= Sum ? Freq[I] - Sum : Sum - Freq[I];
1623 }
1624
1625 return Discrepancy / Freq[0];
1626}
1627#endif
1628
1629template
1630void BlockFrequencyInfoImpl::computeIrreducibleMass(
1631 LoopData *OuterLoop, std::list::iterator Insert) {
1633 if (OuterLoop) dbgs()
1634 << "loop: " << getLoopName(*OuterLoop) << "\n";
1635 else dbgs() << "function\n");
1636
1638
1639 auto addBlockEdges = [&](IrreducibleGraph &G, IrreducibleGraph::IrrNode &Irr,
1640 const LoopData *OuterLoop) {
1641 const BlockT *BB = RPOT[Irr.Node.Index];
1643 G.addEdge(Irr, getNode(Succ), OuterLoop);
1644 };
1645 IrreducibleGraph G(*this, OuterLoop, addBlockEdges);
1646
1647 for (auto &L : analyzeIrreducible(G, OuterLoop, Insert))
1648 computeMassInLoop(L);
1649
1650 if (!OuterLoop)
1651 return;
1652 updateLoopWithIrreducible(*OuterLoop);
1653}
1654
1655
1659
1660template
1661bool
1662BlockFrequencyInfoImpl::propagateMassToSuccessors(LoopData *OuterLoop,
1663 const BlockNode &Node) {
1665
1666 Distribution Dist;
1667 if (auto *Loop = Working[Node.Index].getPackagedLoop()) {
1668 assert(Loop != OuterLoop && "Cannot propagate mass in a packaged loop");
1669 if (!addLoopSuccessorsToDist(OuterLoop, *Loop, Dist))
1670
1671 return false;
1672 } else {
1673 const BlockT *BB = getBlock(Node);
1677 if (!addToDist(
1678 Dist, OuterLoop, Node, getNode(*SI),
1680
1681 return false;
1682 }
1683
1684
1685
1686 distributeMass(Node, OuterLoop, Dist);
1687 return true;
1688}
1689
1690template
1692 if (!F)
1693 return OS;
1694 OS << "block-frequency-info: " << F->getName() << "\n";
1695 for (const BlockT &BB : *F) {
1698 << ", int = " << getBlockFreq(&BB).getFrequency();
1701 F->getFunction(), getNode(&BB)))
1703 if (std::optional<uint64_t> IrrLoopHeaderWeight =
1704 BB.getIrrLoopHeaderWeight())
1705 OS << ", irr_loop_header_weight = " << *IrrLoopHeaderWeight;
1706 OS << "\n";
1707 }
1708
1709
1710 OS << "\n";
1711 return OS;
1712}
1713
1714template
1717 bool Match = true;
1720 for (auto &Entry : Nodes) {
1721 const BlockT *BB = Entry.first;
1722 if (BB) {
1723 ValidNodes[BB] = Entry.second.first;
1724 }
1725 }
1726 for (auto &Entry : Other.Nodes) {
1727 const BlockT *BB = Entry.first;
1728 if (BB) {
1729 OtherValidNodes[BB] = Entry.second.first;
1730 }
1731 }
1732 unsigned NumValidNodes = ValidNodes.size();
1733 unsigned NumOtherValidNodes = OtherValidNodes.size();
1734 if (NumValidNodes != NumOtherValidNodes) {
1735 Match = false;
1736 dbgs() << "Number of blocks mismatch: " << NumValidNodes << " vs "
1737 << NumOtherValidNodes << "\n";
1738 } else {
1739 for (auto &Entry : ValidNodes) {
1740 const BlockT *BB = Entry.first;
1742 if (auto It = OtherValidNodes.find(BB); It != OtherValidNodes.end()) {
1743 BlockNode OtherNode = It->second;
1744 const auto &Freq = Freqs[Node.Index];
1745 const auto &OtherFreq = Other.Freqs[OtherNode.Index];
1746 if (Freq.Integer != OtherFreq.Integer) {
1747 Match = false;
1749 << Freq.Integer << " vs " << OtherFreq.Integer << "\n";
1750 }
1751 } else {
1752 Match = false;
1754 << Node.Index << " does not exist in Other.\n";
1755 }
1756 }
1757
1758
1759 }
1760 if (!Match) {
1761 dbgs() << "This\n";
1763 dbgs() << "Other\n";
1765 }
1766 assert(Match && "BFI mismatch");
1767}
1768
1769
1770
1771
1773
1774template <class BlockFrequencyInfoT, class BranchProbabilityInfoT>
1778 using EdgeIter = typename GTraits::ChildIteratorType;
1779 using NodeIter = typename GTraits::nodes_iterator;
1780
1782
1785
1787 return G->getFunction()->getName();
1788 }
1789
1791 unsigned HotPercentThreshold = 0) {
1792 std::string Result;
1793 if (!HotPercentThreshold)
1794 return Result;
1795
1796
1803 std::max(MaxFrequency, Graph->getBlockFreq(N).getFrequency());
1804 }
1805 }
1810
1811 if (Freq < HotFreq)
1812 return Result;
1813
1815 OS << "color=\"red\"";
1817 return Result;
1818 }
1819
1821 GVDAGType GType, int layout_order = -1) {
1822 std::string Result;
1824
1825 if (layout_order != -1)
1826 OS << Node->getName() << "[" << layout_order << "] : ";
1827 else
1828 OS << Node->getName() << " : ";
1829 switch (GType) {
1832 break;
1834 OS << Graph->getBlockFreq(Node).getFrequency();
1835 break;
1837 auto Count = Graph->getBlockProfileCount(Node);
1840 else
1841 OS << "Unknown";
1842 break;
1843 }
1845 llvm_unreachable("If we are not supposed to render a graph we should "
1846 "never reach this point.");
1847 }
1848 return Result;
1849 }
1850
1852 const BlockFrequencyInfoT *BFI,
1853 const BranchProbabilityInfoT *BPI,
1854 unsigned HotPercentThreshold = 0) {
1855 std::string Str;
1856 if (!BPI)
1857 return Str;
1858
1865
1866 if (HotPercentThreshold) {
1870
1871 if (EFreq >= HotFreq) {
1872 OS << ",color=\"red\"";
1873 }
1874 }
1875
1877 return Str;
1878 }
1879};
1880
1881}
1882
1883#undef DEBUG_TYPE
1884
1885#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
This file implements the BitVector class.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file defines the little GraphTraits template class that should be specialized by classes that...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Branch Probability Basic Block static false std::string getBlockName(const MachineBasicBlock *BB)
Helper to print the name of a MBB.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the SparseBitVector class.
static TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
Value handle that asserts if the Value is deleted.
LLVM Basic Block Representation.
Base class for BlockFrequencyInfoImpl.
Definition BlockFrequencyInfoImpl.h:177
std::vector< WorkingData > Working
Loop data: see initializeLoops().
Definition BlockFrequencyInfoImpl.h:426
virtual ~BlockFrequencyInfoImplBase()=default
Virtual destructor.
void dump() const
Definition BlockFrequencyInfoImpl.h:518
std::list< LoopData > Loops
Indexed information about loops.
Definition BlockFrequencyInfoImpl.h:429
bool addLoopSuccessorsToDist(const LoopData *OuterLoop, LoopData &Loop, Distribution &Dist)
Add all edges out of a packaged loop to the distribution.
ScaledNumber< uint64_t > Scaled64
Definition BlockFrequencyInfoImpl.h:179
std::string getLoopName(const LoopData &Loop) const
bool isIrrLoopHeader(const BlockNode &Node)
void computeLoopScale(LoopData &Loop)
Compute the loop scale for a loop.
bfi_detail::BlockMass BlockMass
Definition BlockFrequencyInfoImpl.h:180
void packageLoop(LoopData &Loop)
Package up a loop.
virtual raw_ostream & print(raw_ostream &OS) const
Definition BlockFrequencyInfoImpl.h:517
virtual std::string getBlockName(const BlockNode &Node) const
void finalizeMetrics()
Finalize frequency metrics.
void setBlockFreq(const BlockNode &Node, BlockFrequency Freq)
BlockFrequency getEntryFreq() const
Definition BlockFrequencyInfoImpl.h:533
void updateLoopWithIrreducible(LoopData &OuterLoop)
Update a loop after packaging irreducible SCCs inside of it.
void clear()
Clear all memory.
std::optional< uint64_t > getBlockProfileCount(const Function &F, const BlockNode &Node, bool AllowSynthetic=false) const
BlockFrequency getBlockFreq(const BlockNode &Node) const
void distributeIrrLoopHeaderMass(Distribution &Dist)
iterator_range< std::list< LoopData >::iterator > analyzeIrreducible(const bfi_detail::IrreducibleGraph &G, LoopData *OuterLoop, std::list< LoopData >::iterator Insert)
Analyze irreducible SCCs.
bool addToDist(Distribution &Dist, const LoopData *OuterLoop, const BlockNode &Pred, const BlockNode &Succ, uint64_t Weight)
Add an edge to the distribution.
void unwrapLoops()
Unwrap loops.
std::optional< uint64_t > getProfileCountFromFreq(const Function &F, BlockFrequency Freq, bool AllowSynthetic=false) const
Scaled64 getFloatingBlockFreq(const BlockNode &Node) const
void distributeMass(const BlockNode &Source, LoopData *OuterLoop, Distribution &Dist)
Distribute mass according to a distribution.
SparseBitVector IsIrrLoopHeader
Whether each block is an irreducible loop header.
Definition BlockFrequencyInfoImpl.h:423
std::vector< FrequencyData > Freqs
Data about each block. This is used downstream.
Definition BlockFrequencyInfoImpl.h:419
void adjustLoopHeaderMass(LoopData &Loop)
Adjust the mass of all headers in an irreducible loop.
bool isIrrLoopHeader(const BlockT *BB)
Definition BlockFrequencyInfoImpl.h:1028
std::optional< uint64_t > getBlockProfileCount(const Function &F, const BlockT *BB, bool AllowSynthetic=false) const
Definition BlockFrequencyInfoImpl.h:1015
const BranchProbabilityInfoT & getBPI() const
Definition BlockFrequencyInfoImpl.h:1045
const FunctionT * getFunction() const
Definition BlockFrequencyInfoImpl.h:1003
void verifyMatch(BlockFrequencyInfoImpl< BT > &Other) const
Definition BlockFrequencyInfoImpl.h:1715
Scaled64 getFloatingBlockFreq(const BlockT *BB) const
Definition BlockFrequencyInfoImpl.h:1041
std::optional< uint64_t > getProfileCountFromFreq(const Function &F, BlockFrequency Freq, bool AllowSynthetic=false) const
Definition BlockFrequencyInfoImpl.h:1022
void calculate(const FunctionT &F, const BranchProbabilityInfoT &BPI, const LoopInfoT &LI)
Definition BlockFrequencyInfoImpl.h:1096
void setBlockFreq(const BlockT *BB, BlockFrequency Freq)
Definition BlockFrequencyInfoImpl.h:1138
BlockFrequencyInfoImpl()=default
raw_ostream & print(raw_ostream &OS) const override
Print the frequencies for the current function.
Definition BlockFrequencyInfoImpl.h:1691
void forgetBlock(const BlockT *BB)
Definition BlockFrequencyInfoImpl.h:1034
BlockFrequency getBlockFreq(const BlockT *BB) const
Definition BlockFrequencyInfoImpl.h:1010
Analysis providing branch probability information.
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
static uint32_t getDenominator()
uint32_t getNumerator() const
CallbackVH(const CallbackVH &)=default
iterator find(const_arg_type_t< KeyT > Val)
Implements a dense probed hash-table based set.
BlockT * getHeader() const
Represents a single loop in the control flow graph.
Simple representation of a scaled number.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
ptrdiff_t difference_type
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
StringRef - Represent a constant reference to a string, i.e.
std::string str() const
str - Get the contents as an std::string.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
The instances of the Type class are immutable: once they are created, they are never changed.
Value * getValPtr() const
LLVM Value Representation.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
void deleted() override
Callback for Value destruction.
Definition BlockFrequencyInfoImpl.h:1079
BFICallbackVH(const BasicBlock *BB, BFIImplT *BFIImpl)
Definition BlockFrequencyInfoImpl.h:1074
virtual ~BFICallbackVH()=default
BFICallbackVH(const MachineBasicBlock *, BFIImplT *)
Definition BlockFrequencyInfoImpl.h:1090
Mass of a block.
Definition BlockFrequencyInfoImpl.h:89
bool operator<(BlockMass X) const
Definition BlockFrequencyInfoImpl.h:137
bool operator!() const
Definition BlockFrequencyInfoImpl.h:107
bool operator>(BlockMass X) const
Definition BlockFrequencyInfoImpl.h:138
uint64_t getMass() const
Definition BlockFrequencyInfoImpl.h:102
raw_ostream & print(raw_ostream &OS) const
bool operator==(BlockMass X) const
Definition BlockFrequencyInfoImpl.h:133
bool isEmpty() const
Definition BlockFrequencyInfoImpl.h:105
bool isFull() const
Definition BlockFrequencyInfoImpl.h:104
static BlockMass getEmpty()
Definition BlockFrequencyInfoImpl.h:96
BlockMass(uint64_t Mass)
Definition BlockFrequencyInfoImpl.h:94
BlockMass & operator-=(BlockMass X)
Subtract another mass.
Definition BlockFrequencyInfoImpl.h:122
bool operator<=(BlockMass X) const
Definition BlockFrequencyInfoImpl.h:135
BlockMass & operator*=(BranchProbability P)
Definition BlockFrequencyInfoImpl.h:128
static BlockMass getFull()
Definition BlockFrequencyInfoImpl.h:98
bool operator!=(BlockMass X) const
Definition BlockFrequencyInfoImpl.h:134
BlockMass & operator+=(BlockMass X)
Add another mass.
Definition BlockFrequencyInfoImpl.h:112
bool operator>=(BlockMass X) const
Definition BlockFrequencyInfoImpl.h:136
ScaledNumber< uint64_t > toScaled() const
Convert to scaled number.
void reserve(size_t Size)
Grow the DenseSet so that it can contain at least NumEntries items before resizing again.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
A raw_ostream that writes to an std::string.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::string getBlockName(const BlockT *BB)
Get the name of a MachineBasicBlock.
Definition BlockFrequencyInfoImpl.h:569
BlockMass operator*(BlockMass L, BranchProbability R)
Definition BlockFrequencyInfoImpl.h:156
BlockMass operator+(BlockMass L, BlockMass R)
Definition BlockFrequencyInfoImpl.h:150
raw_ostream & operator<<(raw_ostream &OS, BlockMass X)
Definition BlockFrequencyInfoImpl.h:163
BlockMass operator-(BlockMass L, BlockMass R)
Definition BlockFrequencyInfoImpl.h:153
NodeAddr< NodeBase * > Node
This is an optimization pass for GlobalISel generic memory operations.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
uint32_t getWeightFromBranchProb(const BranchProbability Prob)
Definition BlockFrequencyInfoImpl.h:1656
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
llvm:🆑:opt< unsigned > IterativeBFIMaxIterationsPerBlock
po_iterator< T > po_begin(const T &G)
llvm:🆑:opt< bool > UseIterativeBFIInference
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FunctionAddr VTableAddr Count
Function::ProfileCount ProfileCount
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
llvm:🆑:opt< bool > CheckBFIUnknownBlockQueries
iterator_range< typename GraphTraits< Inverse< GraphType > >::ChildIteratorType > inverse_children(const typename GraphTraits< GraphType >::NodeRef &G)
FunctionAddr VTableAddr Next
std::string toString(const APInt &I, unsigned Radix, bool Signed, bool formatAsCLiteral=false, bool UpperCase=true, bool InsertSeparators=false)
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
iterator_range< typename GraphTraits< GraphType >::ChildIteratorType > children(const typename GraphTraits< GraphType >::NodeRef &G)
LLVM_ABI Printable printBlockFreq(const BlockFrequencyInfo &BFI, BlockFrequency Freq)
Print the block frequency Freq relative to the current functions entry frequency.
po_iterator< T > po_end(const T &G)
GVDAGType
Definition BlockFrequencyInfoImpl.h:1772
@ GVDT_Fraction
Definition BlockFrequencyInfoImpl.h:1772
@ GVDT_None
Definition BlockFrequencyInfoImpl.h:1772
@ GVDT_Count
Definition BlockFrequencyInfoImpl.h:1772
@ GVDT_Integer
Definition BlockFrequencyInfoImpl.h:1772
llvm:🆑:opt< double > IterativeBFIPrecision
Implement std::hash so that hash_code can be used in STL containers.
GraphTraits< BlockFrequencyInfoT * > GTraits
Definition BlockFrequencyInfoImpl.h:1776
std::string getNodeAttributes(NodeRef Node, const BlockFrequencyInfoT *Graph, unsigned HotPercentThreshold=0)
Definition BlockFrequencyInfoImpl.h:1790
uint64_t MaxFrequency
Definition BlockFrequencyInfoImpl.h:1781
typename GTraits::nodes_iterator NodeIter
Definition BlockFrequencyInfoImpl.h:1779
typename GTraits::NodeRef NodeRef
Definition BlockFrequencyInfoImpl.h:1777
typename GTraits::ChildIteratorType EdgeIter
Definition BlockFrequencyInfoImpl.h:1778
std::string getNodeLabel(NodeRef Node, const BlockFrequencyInfoT *Graph, GVDAGType GType, int layout_order=-1)
Definition BlockFrequencyInfoImpl.h:1820
std::string getEdgeAttributes(NodeRef Node, EdgeIter EI, const BlockFrequencyInfoT *BFI, const BranchProbabilityInfoT *BPI, unsigned HotPercentThreshold=0)
Definition BlockFrequencyInfoImpl.h:1851
BFIDOTGraphTraitsBase(bool isSimple=false)
Definition BlockFrequencyInfoImpl.h:1783
static StringRef getGraphName(const BlockFrequencyInfoT *G)
Definition BlockFrequencyInfoImpl.h:1786
Representative of a block.
Definition BlockFrequencyInfoImpl.h:189
bool operator==(const BlockNode &X) const
Definition BlockFrequencyInfoImpl.h:197
bool operator!=(const BlockNode &X) const
Definition BlockFrequencyInfoImpl.h:198
bool operator<(const BlockNode &X) const
Definition BlockFrequencyInfoImpl.h:201
bool operator>=(const BlockNode &X) const
Definition BlockFrequencyInfoImpl.h:200
BlockNode(IndexType Index)
Definition BlockFrequencyInfoImpl.h:195
static size_t getMaxIndex()
Definition BlockFrequencyInfoImpl.h:206
bool isValid() const
Definition BlockFrequencyInfoImpl.h:204
bool operator<=(const BlockNode &X) const
Definition BlockFrequencyInfoImpl.h:199
uint32_t IndexType
Definition BlockFrequencyInfoImpl.h:190
bool operator>(const BlockNode &X) const
Definition BlockFrequencyInfoImpl.h:202
BlockNode()
Definition BlockFrequencyInfoImpl.h:194
IndexType Index
Definition BlockFrequencyInfoImpl.h:192
Distribution of unscaled probability weight.
Definition BlockFrequencyInfoImpl.h:382
void addBackedge(const BlockNode &Node, uint64_t Amount)
Definition BlockFrequencyInfoImpl.h:399
SmallVector< Weight, 4 > WeightList
Definition BlockFrequencyInfoImpl.h:383
WeightList Weights
Individual successor weights.
Definition BlockFrequencyInfoImpl.h:385
uint64_t Total
Sum of all weights.
Definition BlockFrequencyInfoImpl.h:386
void normalize()
Normalize the distribution.
void addExit(const BlockNode &Node, uint64_t Amount)
Definition BlockFrequencyInfoImpl.h:395
bool DidOverflow
Whether Total did overflow.
Definition BlockFrequencyInfoImpl.h:387
void addLocal(const BlockNode &Node, uint64_t Amount)
Definition BlockFrequencyInfoImpl.h:391
Stats about a block itself.
Definition BlockFrequencyInfoImpl.h:212
Scaled64 Scaled
Definition BlockFrequencyInfoImpl.h:213
uint64_t Integer
Definition BlockFrequencyInfoImpl.h:214
Data about a loop.
Definition BlockFrequencyInfoImpl.h:221
bool isHeader(const BlockNode &Node) const
Definition BlockFrequencyInfoImpl.h:247
SmallVector< std::pair< BlockNode, BlockMass >, 4 > ExitMap
Definition BlockFrequencyInfoImpl.h:222
LoopData * Parent
The parent loop.
Definition BlockFrequencyInfoImpl.h:226
LoopData(LoopData *Parent, It1 FirstHeader, It1 LastHeader, It2 FirstOther, It2 LastOther)
Definition BlockFrequencyInfoImpl.h:239
ExitMap Exits
Successor edges (and weights).
Definition BlockFrequencyInfoImpl.h:229
uint32_t NumHeaders
Number of headers.
Definition BlockFrequencyInfoImpl.h:228
bool IsPackaged
Whether this has been packaged.
Definition BlockFrequencyInfoImpl.h:227
LoopData(LoopData *Parent, const BlockNode &Header)
Definition BlockFrequencyInfoImpl.h:235
SmallVector< BlockNode, 4 > NodeList
Definition BlockFrequencyInfoImpl.h:223
NodeList::const_iterator members_end() const
Definition BlockFrequencyInfoImpl.h:269
NodeList::const_iterator members_begin() const
Definition BlockFrequencyInfoImpl.h:265
bool isIrreducible() const
Definition BlockFrequencyInfoImpl.h:255
BlockNode getHeader() const
Definition BlockFrequencyInfoImpl.h:254
SmallVector< BlockMass, 1 > HeaderMassList
Definition BlockFrequencyInfoImpl.h:224
NodeList Nodes
Header and the members of the loop.
Definition BlockFrequencyInfoImpl.h:230
HeaderMassList BackedgeMass
Mass returned to each loop header.
Definition BlockFrequencyInfoImpl.h:231
BlockMass Mass
Definition BlockFrequencyInfoImpl.h:232
HeaderMassList::difference_type getHeaderIndex(const BlockNode &B)
Definition BlockFrequencyInfoImpl.h:257
iterator_range< NodeList::const_iterator > members() const
Definition BlockFrequencyInfoImpl.h:270
Scaled64 Scale
Definition BlockFrequencyInfoImpl.h:233
Unscaled probability weight.
Definition BlockFrequencyInfoImpl.h:363
Weight(DistType Type, BlockNode TargetNode, uint64_t Amount)
Definition BlockFrequencyInfoImpl.h:370
BlockNode TargetNode
Definition BlockFrequencyInfoImpl.h:366
DistType
Definition BlockFrequencyInfoImpl.h:364
@ Exit
Definition BlockFrequencyInfoImpl.h:364
@ Local
Definition BlockFrequencyInfoImpl.h:364
@ Backedge
Definition BlockFrequencyInfoImpl.h:364
uint64_t Amount
Definition BlockFrequencyInfoImpl.h:367
DistType Type
Definition BlockFrequencyInfoImpl.h:365
bool isPackaged() const
Has ContainingLoop been packaged up?
Definition BlockFrequencyInfoImpl.h:339
BlockMass Mass
Mass distribution from the entry block.
Definition BlockFrequencyInfoImpl.h:279
BlockMass & getMass()
Get the appropriate mass for a node.
Definition BlockFrequencyInfoImpl.h:330
WorkingData(const BlockNode &Node)
Definition BlockFrequencyInfoImpl.h:281
bool isAPackage() const
Has Loop been packaged up?
Definition BlockFrequencyInfoImpl.h:342
bool isLoopHeader() const
Definition BlockFrequencyInfoImpl.h:283
bool isDoubleLoopHeader() const
Definition BlockFrequencyInfoImpl.h:285
LoopData * Loop
The loop this block is inside.
Definition BlockFrequencyInfoImpl.h:278
LoopData * getContainingLoop() const
Definition BlockFrequencyInfoImpl.h:290
BlockNode Node
This node.
Definition BlockFrequencyInfoImpl.h:277
LoopData * getPackagedLoop() const
Definition BlockFrequencyInfoImpl.h:316
BlockNode getResolvedNode() const
Resolve a node to its representative.
Definition BlockFrequencyInfoImpl.h:311
bool isADoublePackage() const
Has Loop been packaged up twice?
Definition BlockFrequencyInfoImpl.h:345
DefaultDOTGraphTraits(bool simple=false)
static nodes_iterator nodes_end(const BlockFrequencyInfo *G)
static nodes_iterator nodes_begin(const BlockFrequencyInfo *G)
typename BlockFrequencyInfoT *::UnknownGraphTypeError NodeRef
iterator pred_end() const
Definition BlockFrequencyInfoImpl.h:613
IrrNode(const BlockNode &Node)
Definition BlockFrequencyInfoImpl.h:607
iterator pred_begin() const
Definition BlockFrequencyInfoImpl.h:611
iterator succ_begin() const
Definition BlockFrequencyInfoImpl.h:612
std::deque< const IrrNode * >::const_iterator iterator
Definition BlockFrequencyInfoImpl.h:609
BlockNode Node
Definition BlockFrequencyInfoImpl.h:603
std::deque< const IrrNode * > Edges
Definition BlockFrequencyInfoImpl.h:605
iterator succ_end() const
Definition BlockFrequencyInfoImpl.h:614
unsigned NumIn
Definition BlockFrequencyInfoImpl.h:604
Graph of irreducible control flow.
Definition BlockFrequencyInfoImpl.h:596
void addNodesInFunction()
IrreducibleGraph(BFIBase &BFI, const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
Construct an explicit graph containing irreducible control flow.
Definition BlockFrequencyInfoImpl.h:631
void addEdge(IrrNode &Irr, const BlockNode &Succ, const BFIBase::LoopData *OuterLoop)
BlockFrequencyInfoImplBase BFIBase
Definition BlockFrequencyInfoImpl.h:597
void addEdges(const BlockNode &Node, const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
Definition BlockFrequencyInfoImpl.h:671
BFIBase & BFI
Definition BlockFrequencyInfoImpl.h:599
BFIBase::BlockNode BlockNode
Definition BlockFrequencyInfoImpl.h:601
const IrrNode * StartIrr
Definition BlockFrequencyInfoImpl.h:617
std::vector< IrrNode > Nodes
Definition BlockFrequencyInfoImpl.h:618
BlockNode Start
Definition BlockFrequencyInfoImpl.h:616
SmallDenseMap< uint32_t, IrrNode *, 4 > Lookup
Definition BlockFrequencyInfoImpl.h:619
void initialize(const BFIBase::LoopData *OuterLoop, BlockEdgesAdder addBlockEdges)
Definition BlockFrequencyInfoImpl.h:656
void addNode(const BlockNode &Node)
Definition BlockFrequencyInfoImpl.h:642
void addNodesInLoop(const BFIBase::LoopData &OuterLoop)
BasicBlock BlockT
Definition BlockFrequencyInfoImpl.h:543
LoopInfo LoopInfoT
Definition BlockFrequencyInfoImpl.h:548
BranchProbabilityInfo BranchProbabilityInfoT
Definition BlockFrequencyInfoImpl.h:546
AssertingVH< const BasicBlock > BlockKeyT
Definition BlockFrequencyInfoImpl.h:544
Function FunctionT
Definition BlockFrequencyInfoImpl.h:545
Loop LoopT
Definition BlockFrequencyInfoImpl.h:547
MachineLoopInfo LoopInfoT
Definition BlockFrequencyInfoImpl.h:556
MachineFunction FunctionT
Definition BlockFrequencyInfoImpl.h:553
MachineBranchProbabilityInfo BranchProbabilityInfoT
Definition BlockFrequencyInfoImpl.h:554
MachineBasicBlock BlockT
Definition BlockFrequencyInfoImpl.h:551
const MachineBasicBlock * BlockKeyT
Definition BlockFrequencyInfoImpl.h:552
MachineLoop LoopT
Definition BlockFrequencyInfoImpl.h:555