LLVM: lib/CodeGen/ScheduleDAGInstrs.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
15
41#include "llvm/Config/llvm-config.h"
55#include
56#include
57#include
58#include
59#include
60
61using namespace llvm;
62
63#define DEBUG_TYPE "machine-scheduler"
64
67 cl::desc("Enable use of AA during MI DAG construction"));
68
70 cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"));
71
74 cl::desc("Use TargetSchedModel for latency lookup"));
75
78 cl::desc("Use InstrItineraryData for latency lookup"));
79
80
81
82
83
84
85
87 cl::init(1000), cl::desc("The limit to use while constructing the DAG "
88 "prior to scheduling, at which point a trade-off "
89 "is made to avoid excessive compile time."));
90
92 "dag-maps-reduction-size", cl::Hidden,
93 cl::desc("A huge scheduling region will have maps reduced by this many "
94 "nodes at a time. Defaults to HugeRegion / 2."));
95
96#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
99 cl::desc("Report top/bottom cycles when dumping SUnit instances"));
100#endif
101
109
111#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
112 dbgs() << "{ ";
113 for (const SUnit *SU : L) {
114 dbgs() << "SU(" << SU->NodeNum << ")";
115 if (SU != L.back())
116 dbgs() << ", ";
117 }
118 dbgs() << "}\n";
119#endif
120}
121
134
135
136
137
138
143 auto AllMMOsOkay = [&]() {
145
146 if (MMO->isVolatile() || MMO->isAtomic())
147 return false;
148
150
151
152
153
154
156 return false;
157
158
159
160
161 if (PSV->isAliased(&MFI))
162 return false;
163
164 bool MayAlias = PSV->mayAlias(&MFI);
166 } else if (const Value *V = MMO->getValue()) {
169 return false;
170
171 for (Value *V : Objs) {
174 }
175 } else
176 return false;
177 }
178 return true;
179 };
180
181 if (!AllMMOsOkay()) {
183 return false;
184 }
185
186 return true;
187}
188
192
194
195 BB = nullptr;
196}
197
201 unsigned regioninstrs) {
202 assert(bb == BB && "startBlock should set BB");
206}
207
211
216 : nullptr;
217 ExitSU.setInstr(ExitMI);
218
219 if (ExitMI) {
222 unsigned OpIdx = MO.getOperandNo();
224 if (Reg.isPhysical()) {
225
226
227
228
229
230
231
232
235 for (MCRegUnit Unit : TRI->regunits(Reg))
237 } else if (Reg.isVirtual() && MO.readsReg()) {
239 }
240 }
241 }
242 if (!ExitMI || (!ExitMI->isCall() && !ExitMI->isBarrier())) {
243
244
246 for (const auto &LI : Succ->liveins()) {
248 auto [Unit, Mask] = *U;
249 if ((Mask & LI.LaneMask).any() && .contains(Unit))
251 }
252 }
253 }
254 }
255}
256
257
258
261 assert(MO.isDef() && "expect physreg def");
263
264
266
267
268
270 bool ImplicitPseudoDef = (OperIdx >= DefMIDesc.getNumOperands() &&
272 for (MCRegUnit Unit : TRI->regunits(Reg)) {
274 ++I) {
276 if (UseSU == SU)
277 continue;
278
279
280
282 int UseOpIdx = I->OpIdx;
283 bool ImplicitPseudoUse = false;
285 if (UseOpIdx < 0) {
287 } else {
288
289
291
292 UseInstr = UseSU->getInstr();
295 ImplicitPseudoUse = UseOpIdx >= ((int)UseMIDesc.getNumOperands()) &&
297
299 }
300 if (!ImplicitPseudoDef && !ImplicitPseudoUse) {
302 UseInstr, UseOpIdx));
303 } else {
305 }
306 ST.adjustSchedDependency(SU, OperIdx, UseSU, UseOpIdx, Dep, &SchedModel);
308 }
309 }
310}
311
312
313
314
319
320 if (MRI.isConstantPhysReg(Reg))
321 return;
322
324
325
326
327
328
329
330
332 for (MCRegUnit Unit : TRI->regunits(Reg)) {
334 ++I) {
336 if (DefSU == &ExitSU)
337 continue;
340 if (DefSU != SU &&
345 SchedModel.computeOutputLatency(MI, OperIdx, DefInstr));
346 }
347 ST.adjustSchedDependency(SU, OperIdx, DefSU, I->OpIdx, Dep,
350 }
351 }
352 }
353
354 if (MO.isUse()) {
356
357
358
359 for (MCRegUnit Unit : TRI->regunits(Reg))
363 } else {
365
366
367 for (MCRegUnit Unit : TRI->regunits(Reg)) {
368 Uses.eraseAll(Unit);
370 Defs.eraseAll(Unit);
371 }
372
374
375
376
377
378
379 for (MCRegUnit Unit : TRI->regunits(Reg)) {
383 for (bool isBegin = I == B; !isBegin; ) {
385 if (->SU->isCall)
386 break;
388 }
389 }
390 }
391
392
393 for (MCRegUnit Unit : TRI->regunits(Reg))
395 }
396}
397
399{
401
405
409 return TRI->getSubRegIndexLaneMask(SubReg);
410}
411
418
419
420
421
422
423
424
429
435
436
438
440
441
442
443
446 if (OtherMO.isReg() && OtherMO.isDef() && OtherMO.getReg() == Reg)
448 }
449
450
451
453 } else {
456 }
457
460 } else {
461
466
467 if ((LaneMask & KillLaneMask).none()) {
468 ++I;
469 continue;
470 }
471
472 if ((LaneMask & DefLaneMask).any()) {
477 I->OperandIndex));
478 ST.adjustSchedDependency(SU, OperIdx, UseSU, I->OperandIndex, Dep,
481 }
482
483 LaneMask &= ~KillLaneMask;
484
485 if (LaneMask.any()) {
486 I->LaneMask = LaneMask;
487 ++I;
488 } else
490 }
491 }
492
493
494 if (MRI.hasOneDef(Reg))
495 return;
496
497
498
499
500
501
502
503
507
508 if ((V2SU.LaneMask & LaneMask).none())
509 continue;
510
511 SUnit *DefSU = V2SU.SU;
512
513
514
515
516
517 if (DefSU == SU)
518 continue;
523
524
525
526
527 LaneBitmask OverlapMask = V2SU.LaneMask & LaneMask;
528 LaneBitmask NonOverlapMask = V2SU.LaneMask & ~LaneMask;
529 V2SU.SU = SU;
530 V2SU.LaneMask = OverlapMask;
531 if (NonOverlapMask.any())
533 }
534
535 if (LaneMask.any())
537}
538
539
540
541
542
543
544
547 assert(->isDebugOrPseudoInstr());
548
551
552
556
557
560
561 LaneBitmask PrevDefLaneMask = V2SU.LaneMask;
562 if ((PrevDefLaneMask & LaneMask).none())
563 continue;
564 if (V2SU.SU == SU)
565 continue;
566
568 }
569}
570
571
580
581
582
583
584
585
586
587
588
589
590
591
592
594
595
597
599 if (MI.isDebugOrPseudoInstr())
600 continue;
601
604
607
608
610
611
612
613
614
615
616
617
618
619 if (SchedModel.hasInstrSchedModel()) {
623 SchedModel.getWriteProcResEnd(SC))) {
624 switch (SchedModel.getProcResource(PRE.ProcResourceIdx)->BufferSize) {
625 case 0:
627 break;
628 case 1:
630 break;
631 default:
632 break;
633 }
634 }
635 }
636 }
637}
638
641
642 unsigned NumNodes = 0;
643
644
645 unsigned TrueMemOrderLatency;
646
647public:
648 Value2SUsMap(unsigned lat = 0) : TrueMemOrderLatency(lat) {}
649
650
651
654
655
656
661
662
665 if (Itr != end()) {
666 assert(NumNodes >= Itr->second.size());
667 NumNodes -= Itr->second.size();
668
669 Itr->second.clear();
670 }
671 }
672
673
678
679 unsigned inline size() const { return NumNodes; }
680
681
683 NumNodes = 0;
684 for (auto &I : *this)
685 NumNodes += I.second.size();
686 }
687
689 return TrueMemOrderLatency;
690 }
691
693};
694
697 for (auto &I : Val2SUsMap)
700}
701
706 if (Itr != Val2SUsMap.end())
709}
710
713
714 for (auto &[V, SUs] : map) {
715 (void)V;
716 for (auto *SU : SUs)
718 }
720}
721
724
725
728 SUList &sus = CurrItr->second;
729 SUList::iterator SUItr = sus.begin(), SUEE = sus.end();
730 for (; SUItr != SUEE; ++SUItr) {
731
732 if ((*SUItr)->NodeNum <= BarrierChain->NodeNum)
733 break;
734
736 }
737
738
740 SUItr++;
741
742
743 if (SUItr != sus.begin())
744 sus.erase(sus.begin(), SUItr);
745 }
746
747
748 map.remove_if([&](std::pair<ValueType, SUList> &mapEntry) {
749 return (mapEntry.second.empty()); });
750
751
753}
754
762 : ST.useAA();
765
767
771
772
774
775 if (PDiffs)
777
778
779
780
781
782
783
784
785
786
787 Value2SUsMap Stores, Loads(1 );
788
789
790
791
792
793
794
795
796 Value2SUsMap NonAliasStores, NonAliasLoads(1 );
797
798
799
800
801
802
803
805
806
807
810
812 "Only BuildGraph should update Defs/Uses");
813 Defs.setUniverse(TRI->getNumRegs());
814 Uses.setUniverse(TRI->getNumRegs());
815
818 unsigned NumVirtRegs = MRI.getNumVirtRegs();
821
822
823
825
826
829 MII != MIE; --MII) {
831 if (DbgMI) {
833 DbgMI = nullptr;
834 }
835
836 if (MI.isDebugValue() || MI.isDebugPHI()) {
837 DbgMI = &MI;
838 continue;
839 }
840
841 if (MI.isDebugLabel() || MI.isDebugRef() || MI.isPseudoProbe())
842 continue;
843
845 assert(SU && "No SUnit mapped to this MI");
846
847 if (RPTracker) {
853 }
854 if (PDiffs != nullptr)
856
859 assert(&*RPTracker->getPos() == &MI && "RPTracker in sync");
860 RPTracker->recede(RegOpers);
861 }
862
865 "Cannot schedule terminators or labels!");
866
867
868
869
870
871
872 bool HasVRegDef = false;
873 for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
876 continue;
878 if (Reg.isPhysical()) {
880 } else if (Reg.isVirtual()) {
881 HasVRegDef = true;
883 }
884 }
885
886 for (unsigned j = 0, n = MI.getNumOperands(); j != n; ++j) {
888
889
890
891
893 continue;
895 if (Reg.isPhysical()) {
897 } else if (Reg.isVirtual() && MO.readsReg()) {
899 }
900 }
901
902
903
904
905
906
907
908 if (SU->NumSuccs == 0 && SU->Latency > 1 && (HasVRegDef || MI.mayLoad())) {
912 }
913
914
915
916
917
919
920 if (TII->isGlobalMemoryObject(&MI)) {
921
922
926
927 LLVM_DEBUG(dbgs() << "Global memory object and new barrier chain: SU("
929
930
936
937 continue;
938 }
939
940
941
942 if (MI.mayRaiseFPException()) {
945
947
949 LLVM_DEBUG(dbgs() << "Reducing FPExceptions map.\n");
952 }
953 }
954
955
956 if (.mayStore() &&
957 !(MI.mayLoad() && .isDereferenceableInvariantLoad()))
958 continue;
959
960
963
964
965
966
969 MF.getDataLayout());
970
971 if (MI.mayStore()) {
972 if (!ObjsFound) {
973
978
979
981 } else {
982
983
985 ValueType V = UnderlObj.getValue();
986 bool ThisMayAlias = UnderlObj.mayAlias();
987
988
991 }
992
993
995 ValueType V = UnderlObj.getValue();
996 bool ThisMayAlias = UnderlObj.mayAlias();
997
998
999 (ThisMayAlias ? Stores : NonAliasStores).insert(SU, V);
1000 }
1001
1002
1005 }
1006 } else {
1007 if (!ObjsFound) {
1008
1011
1013 } else {
1015 ValueType V = UnderlObj.getValue();
1016 bool ThisMayAlias = UnderlObj.mayAlias();
1017
1018
1019
1021
1022
1023 (ThisMayAlias ? Loads : NonAliasLoads).insert(SU, V);
1024 }
1025
1027 }
1028 }
1029
1030
1032 LLVM_DEBUG(dbgs() << "Reducing Stores and Loads maps.\n");
1034 }
1036 LLVM_DEBUG(dbgs() << "Reducing NonAliasStores and NonAliasLoads maps.\n");
1038 }
1039 }
1040
1041 if (DbgMI)
1043
1044 Defs.clear();
1045 Uses.clear();
1048
1049 Topo.MarkDirty();
1050}
1051
1053 PSV->printCustom(OS);
1054 return OS;
1055}
1056
1058 for (const auto &[ValType, SUs] : *this) {
1062 dbgs() << "Unknown";
1063 else
1064 V->printAsOperand(dbgs());
1067 else
1069
1070 dbgs() << " : ";
1072 }
1073}
1074
1078 dbgs() << "Loading SUnits:\n"; loads.dump());
1079
1080
1081 std::vector NodeNums;
1082 NodeNums.reserve(stores.size() + loads.size());
1083 for (const auto &[V, SUs] : stores) {
1084 (void)V;
1085 for (const auto *SU : SUs)
1086 NodeNums.push_back(SU->NodeNum);
1087 }
1088 for (const auto &[V, SUs] : loads) {
1089 (void)V;
1090 for (const auto *SU : SUs)
1091 NodeNums.push_back(SU->NodeNum);
1092 }
1094
1095
1096
1097
1098 assert(N <= NodeNums.size());
1099 SUnit *newBarrierChain = &SUnits[*(NodeNums.end() - N)];
1101
1102
1103
1104
1106 BarrierChain->addPredBarrier(newBarrierChain);
1108 LLVM_DEBUG(dbgs() << "Inserting new barrier chain: SU("
1110 }
1111 else
1112 LLVM_DEBUG(dbgs() << "Keeping old barrier chain: SU("
1114 }
1115 else
1117
1120
1122 dbgs() << "Loading SUnits:\n"; loads.dump());
1123}
1124
1128 if (!MO.isReg() || !MO.readsReg())
1129 continue;
1131 if ()
1132 continue;
1133
1134
1136
1137
1138 MO.setIsKill(IsKill && .isReserved(Reg));
1139 if (addToLiveRegs)
1141 }
1142}
1143
1146
1149
1150
1152 if (MI.isDebugOrPseudoInstr())
1153 continue;
1154
1155
1156
1157
1160 if (MO.isReg()) {
1161 if (!MO.isDef())
1162 continue;
1164 if (!Reg)
1165 continue;
1169 }
1170 }
1171
1172
1173 if (.isBundled()) {
1175 } else {
1177 if (MI.isBundle())
1179
1180
1181
1182
1184 while (I->isBundledWithSucc())
1185 ++I;
1186 do {
1187 if (->isDebugOrPseudoInstr())
1189 --I;
1190 } while (I != Bundle);
1191 }
1192 }
1193}
1194
1196#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1200 << ", BottomReadyCycle = " << SU.BotReadyCycle << "]";
1201 dbgs() << ": ";
1203#endif
1204}
1205
1207#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1208 if (EntrySU.getInstr() != nullptr)
1212 if (ExitSU.getInstr() != nullptr)
1214#endif
1215}
1216
1218 std::string s;
1221 oss << "";
1222 else if (SU == &ExitSU)
1223 oss << "";
1224 else
1225 SU->getInstr()->print(oss, true);
1226 return s;
1227}
1228
1229
1230
1232 return "dag." + BB->getFullName();
1233}
1234
1236 return SuccSU == &ExitSU || .IsReachable(PredSU, SuccSU);
1237}
1238
1240 if (SuccSU != &ExitSU) {
1241
1242
1243 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
1244 return false;
1245 Topo.AddPredQueued(SuccSU, PredDep.getSUnit());
1246 }
1248
1249 return true;
1250}
1251
1252
1253
1254
1255
1256namespace llvm {
1257
1258
1261
1262
1264
1265 std::vector<std::pair<const SUnit *, const SUnit*>> ConnectionPairs;
1266
1267 struct RootData {
1268 unsigned NodeID;
1269 unsigned ParentNodeID;
1270 unsigned SubInstrCount = 0;
1271
1272
1273 RootData(unsigned id): NodeID(id),
1274 ParentNodeID(SchedDFSResult::InvalidSubtreeID) {}
1275
1276 unsigned getSparseSetIndex() const { return NodeID; }
1277 };
1278
1280
1281public:
1283 RootSet.setUniverse(R.DFSNodeData.size());
1284 }
1285
1286
1287
1288
1289
1291 return R.DFSNodeData[SU->NodeNum].SubtreeID
1292 != SchedDFSResult::InvalidSubtreeID;
1293 }
1294
1295
1296
1298 R.DFSNodeData[SU->NodeNum].InstrCount =
1300 }
1301
1302
1303
1304
1306
1307
1309 RootData RData(SU->NodeNum);
1311
1312
1313
1314
1315
1316
1318 for (const SDep &PredDep : SU->Preds) {
1320 continue;
1322 if ((InstrCount - R.DFSNodeData[PredNum].InstrCount) < R.SubtreeLimit)
1324
1325
1326 if (R.DFSNodeData[PredNum].SubtreeID == PredNum) {
1327
1328
1329 if (RootSet[PredNum].ParentNodeID == SchedDFSResult::InvalidSubtreeID)
1330 RootSet[PredNum].ParentNodeID = SU->NodeNum;
1331 }
1332 else if (RootSet.count(PredNum)) {
1333
1334
1335
1336
1337 RData.SubInstrCount += RootSet[PredNum].SubInstrCount;
1338 RootSet.erase(PredNum);
1339 }
1340 }
1341 RootSet[SU->NodeNum] = RData;
1342 }
1343
1344
1345
1346
1348 R.DFSNodeData[Succ->NodeNum].InstrCount
1349 += R.DFSNodeData[PredDep.getSUnit()->NodeNum].InstrCount;
1351 }
1352
1353
1355 ConnectionPairs.emplace_back(PredDep.getSUnit(), Succ);
1356 }
1357
1358
1359
1361 SubtreeClasses.compress();
1362 R.DFSTreeData.resize(SubtreeClasses.getNumClasses());
1363 assert(SubtreeClasses.getNumClasses() == RootSet.size()
1364 && "number of roots should match trees");
1365 for (const RootData &Root : RootSet) {
1366 unsigned TreeID = SubtreeClasses[Root.NodeID];
1367 if (Root.ParentNodeID != SchedDFSResult::InvalidSubtreeID)
1368 R.DFSTreeData[TreeID].ParentTreeID = SubtreeClasses[Root.ParentNodeID];
1369 R.DFSTreeData[TreeID].SubInstrCount = Root.SubInstrCount;
1370
1371
1372
1373
1374 }
1375 R.SubtreeConnections.resize(SubtreeClasses.getNumClasses());
1376 R.SubtreeConnectLevels.resize(SubtreeClasses.getNumClasses());
1377 LLVM_DEBUG(dbgs() << R.getNumSubtrees() << " subtrees:\n");
1378 for (unsigned Idx = 0, End = R.DFSNodeData.size(); Idx != End; ++Idx) {
1379 R.DFSNodeData[Idx].SubtreeID = SubtreeClasses[Idx];
1381 << R.DFSNodeData[Idx].SubtreeID << '\n');
1382 }
1383 for (const auto &[Pred, Succ] : ConnectionPairs) {
1384 unsigned PredTree = SubtreeClasses[Pred->NodeNum];
1385 unsigned SuccTree = SubtreeClasses[Succ->NodeNum];
1386 if (PredTree == SuccTree)
1387 continue;
1388 unsigned Depth = Pred->getDepth();
1391 }
1392 }
1393
1394protected:
1395
1396
1398 bool CheckLimit = true) {
1400
1401
1403 unsigned PredNum = PredSU->NodeNum;
1404 if (R.DFSNodeData[PredNum].SubtreeID != PredNum)
1405 return false;
1406
1407
1408
1409 unsigned NumDataSucs = 0;
1410 for (const SDep &SuccDep : PredSU->Succs) {
1412 if (++NumDataSucs >= 4)
1413 return false;
1414 }
1415 }
1416 if (CheckLimit && R.DFSNodeData[PredNum].InstrCount > R.SubtreeLimit)
1417 return false;
1418 R.DFSNodeData[PredNum].SubtreeID = Succ->NodeNum;
1419 SubtreeClasses.join(Succ->NodeNum, PredNum);
1420 return true;
1421 }
1422
1423
1426 return;
1427
1428 do {
1430 R.SubtreeConnections[FromTree];
1431 for (SchedDFSResult::Connection &C : Connections) {
1432 if (C.TreeID == ToTree) {
1433 C.Level = std::max(C.Level, Depth);
1434 return;
1435 }
1436 }
1437 Connections.push_back(SchedDFSResult::Connection(ToTree, Depth));
1438 FromTree = R.DFSTreeData[FromTree].ParentTreeID;
1439 } while (FromTree != SchedDFSResult::InvalidSubtreeID);
1440 }
1441};
1442
1443}
1444
1445namespace {
1446
1447
1448class SchedDAGReverseDFS {
1449 std::vector<std::pair<const SUnit *, SUnit::const_pred_iterator>> DFSStack;
1450
1451public:
1452 bool isComplete() const { return DFSStack.empty(); }
1453
1454 void follow(const SUnit *SU) {
1455 DFSStack.emplace_back(SU, SU->Preds.begin());
1456 }
1457 void advance() { ++DFSStack.back().second; }
1458
1459 const SDep *backtrack() {
1460 DFSStack.pop_back();
1461 return DFSStack.empty() ? nullptr : std::prev(DFSStack.back().second);
1462 }
1463
1464 const SUnit *getCurr() const { return DFSStack.back().first; }
1465
1467
1469 return getCurr()->Preds.end();
1470 }
1471};
1472
1473}
1474
1476 for (const SDep &SuccDep : SU->Succs) {
1479 return true;
1480 }
1481 return false;
1482}
1483
1484
1485
1487 if (!IsBottomUp)
1489
1492 if (Impl.isVisited(&SU) || hasDataSucc(&SU))
1493 continue;
1494
1495 SchedDAGReverseDFS DFS;
1496 Impl.visitPreorder(&SU);
1497 DFS.follow(&SU);
1498 while (true) {
1499
1500 while (DFS.getPred() != DFS.getPredEnd()) {
1501 const SDep &PredDep = *DFS.getPred();
1502 DFS.advance();
1503
1506 continue;
1507 }
1508
1509 if (Impl.isVisited(PredDep.getSUnit())) {
1510 Impl.visitCrossEdge(PredDep, DFS.getCurr());
1511 continue;
1512 }
1513 Impl.visitPreorder(PredDep.getSUnit());
1514 DFS.follow(PredDep.getSUnit());
1515 }
1516
1517 const SUnit *Child = DFS.getCurr();
1518 const SDep *PredDep = DFS.backtrack();
1519 Impl.visitPostorderNode(Child);
1520 if (PredDep)
1521 Impl.visitPostorderEdge(*PredDep, DFS.getCurr());
1522 if (DFS.isComplete())
1523 break;
1524 }
1525 }
1526 Impl.finalize();
1527}
1528
1529
1530
1531
1533 for (const Connection &C : SubtreeConnections[SubtreeID]) {
1534 SubtreeConnectLevels[C.TreeID] =
1535 std::max(SubtreeConnectLevels[C.TreeID], C.Level);
1537 << SubtreeConnectLevels[C.TreeID] << '\n');
1538 }
1539}
1540
1541#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1545 OS << "BADILP";
1546 else
1548}
1549
1551 dbgs() << *this << '\n';
1552}
1553
1554[[maybe_unused]]
1559
1560#endif
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static cl::opt< bool > UseAA("aarch64-use-aa", cl::init(true), cl::desc("Enable the use of AA during codegen."))
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static unsigned InstrCount
static Register UseReg(const MachineOperand &MO)
hexagon widen Hexagon Store false hexagon widen loads
Equivalence classes for small integers.
A common definition of LaneBitmask for use in TableGen and CodeGen.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
This file implements a map that provides insertion order iteration.
MachineInstr unsigned OpIdx
static void toggleKills(const MachineRegisterInfo &MRI, LiveRegUnits &LiveRegs, MachineInstr &MI, bool addToLiveRegs)
Definition ScheduleDAGInstrs.cpp:1125
static cl::opt< unsigned > ReductionSize("dag-maps-reduction-size", cl::Hidden, cl::desc("A huge scheduling region will have maps reduced by this many " "nodes at a time. Defaults to HugeRegion / 2."))
static bool getUnderlyingObjectsForInstr(const MachineInstr *MI, const MachineFrameInfo &MFI, UnderlyingObjectsVector &Objects, const DataLayout &DL)
If this machine instr has memory reference information and it can be tracked to a normal reference to...
Definition ScheduleDAGInstrs.cpp:139
static bool hasDataSucc(const SUnit *SU)
Definition ScheduleDAGInstrs.cpp:1475
static cl::opt< bool > EnableSchedModel("schedmodel", cl::Hidden, cl::init(true), cl::desc("Use TargetSchedModel for latency lookup"))
static cl::opt< bool > EnableAASchedMI("enable-aa-sched-mi", cl::Hidden, cl::desc("Enable use of AA during MI DAG construction"))
static cl::opt< unsigned > HugeRegion("dag-maps-huge-region", cl::Hidden, cl::init(1000), cl::desc("The limit to use while constructing the DAG " "prior to scheduling, at which point a trade-off " "is made to avoid excessive compile time."))
static unsigned getReductionSize()
Definition ScheduleDAGInstrs.cpp:102
static void dumpSUList(const ScheduleDAGInstrs::SUList &L)
Definition ScheduleDAGInstrs.cpp:110
static cl::opt< bool > UseTBAA("use-tbaa-in-sched-mi", cl::Hidden, cl::init(true), cl::desc("Enable use of TBAA during MI DAG construction"))
static cl::opt< bool > EnableSchedItins("scheditins", cl::Hidden, cl::init(true), cl::desc("Use InstrItineraryData for latency lookup"))
static cl::opt< bool > SchedPrintCycles("sched-print-cycles", cl::Hidden, cl::init(false), cl::desc("Report top/bottom cycles when dumping SUnit instances"))
This file defines the SmallVector class.
This file defines the SparseSet class derived from the version described in Briggs,...
static Function * getFunction(FunctionType *Ty, const Twine &Name, Module *M)
void reComputeSize()
Counts the number of SUs in this map after a reduction.
Definition ScheduleDAGInstrs.cpp:682
void insert(SUnit *SU, ValueType V)
Adds SU to the SUList of V.
Definition ScheduleDAGInstrs.cpp:657
void dump()
Definition ScheduleDAGInstrs.cpp:1057
void clear()
Clears map from all contents.
Definition ScheduleDAGInstrs.cpp:674
Value2SUsMap(unsigned lat=0)
Definition ScheduleDAGInstrs.cpp:648
void clearList(ValueType V)
Clears the list of SUs mapped to V.
Definition ScheduleDAGInstrs.cpp:663
unsigned size() const
Definition ScheduleDAGInstrs.cpp:679
ValueType & operator[](const SUList &Key)
To keep NumNodes up to date, insert() is used instead of this operator w/ push_back().
Definition ScheduleDAGInstrs.cpp:652
unsigned getTrueMemOrderLatency() const
Definition ScheduleDAGInstrs.cpp:688
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
ConstMIBundleOperands - Iterate over all operands in a const bundle of machine instructions.
A parsed version of the target data layout string in and methods for querying it.
SlotIndex getInstructionIndex(const MachineInstr &Instr) const
Returns the base index of the given instruction.
A set of register units used to track register liveness.
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
bool hasImplicitUseOfPhysReg(MCRegister Reg) const
Return true if this instruction implicitly uses the specified physical register.
LLVM_ABI bool hasImplicitDefOfPhysReg(MCRegister Reg, const MCRegisterInfo *MRI=nullptr) const
Return true if this instruction implicitly defines the specified physical register.
MCRegUnitMaskIterator enumerates a list of register units and their associated lane masks for Reg.
bool isValid() const
Returns true if this iterator is not yet at the end.
Instructions::iterator instr_iterator
MachineInstrBundleIterator< MachineInstr > iterator
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted.
bool hasTailCall() const
Returns true if the function contains a tail call.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Representation of each machine instruction.
bool isBarrier(QueryType Type=AnyInBundle) const
Returns true if the specified instruction stops control flow from executing the instruction immediate...
bool isCall(QueryType Type=AnyInBundle) const
LLVM_ABI bool mayAlias(BatchAAResults *AA, const MachineInstr &Other, bool UseTBAA) const
Returns true if this instruction's memory access aliases the memory access of Other.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
LLVM_ABI void print(raw_ostream &OS, bool IsStandalone=true, bool SkipOpers=false, bool SkipDebugLoc=false, bool AddNewLine=true, const TargetInstrInfo *TII=nullptr) const
Print this MI to OS.
filtered_mop_range all_uses()
Returns an iterator range over all operands that are (explicit or implicit) register uses.
bool isTransient() const
Return true if this is a transient instruction that is either very likely to be eliminated during reg...
LLVM_ABI void dump() const
const MachineOperand & getOperand(unsigned i) const
A description of a memory reference used in the backend.
MachineOperand class - Representation of each machine instruction operand.
unsigned getSubReg() const
bool readsReg() const
readsReg - Returns true if this operand reads the previous value of its register.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
bool isRegMask() const
isRegMask - Tests if this is a MO_RegisterMask operand.
void setIsKill(bool Val=true)
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
const uint32_t * getRegMask() const
getRegMask - Returns a bit mask of registers preserved by this RegMask operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
typename SmallVector< std::pair< ValueType, SUList >, N >::iterator iterator
ValueT & operator[](const KeyT &Key)
iterator find(const ValueType &Key)
void remove_if(Function Pred)
LLVM_ABI void addInstruction(unsigned Idx, const RegisterOperands &RegOpers, const MachineRegisterInfo &MRI)
Record pressure difference induced by the given operand list to node with index Idx.
LLVM_ABI void init(unsigned N)
Initialize an array of N PressureDiffs.
Special value supplied for machine level alias analysis.
Track the current register pressure at some position in the instruction stream, and remember the high...
LLVM_ABI void recede(SmallVectorImpl< VRegMaskOrUnit > *LiveUses=nullptr)
Recede across the previous instruction.
LLVM_ABI void recedeSkipDebugValues()
Recede until we find an instruction which is not a DebugValue.
MachineBasicBlock::const_iterator getPos() const
Get the MI position corresponding to this register pressure.
List of registers defined and used by a machine instruction.
LLVM_ABI void collect(const MachineInstr &MI, const TargetRegisterInfo &TRI, const MachineRegisterInfo &MRI, bool TrackLaneMasks, bool IgnoreDead)
Analyze the given instruction MI and fill in the Uses, Defs and DeadDefs list based on the MachineOpe...
LLVM_ABI void adjustLaneLiveness(const LiveIntervals &LIS, const MachineRegisterInfo &MRI, SlotIndex Pos, MachineInstr *AddFlagsMI=nullptr)
Use liveness information to find out which uses/defs are partially undefined/dead and adjust the VReg...
Wrapper class representing virtual and physical registers.
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Kind
These are the different kinds of scheduling dependencies.
@ Output
A register output-dependence (aka WAW).
@ Anti
A register anti-dependence (aka WAR).
@ Data
Regular data dependence (aka true-dependence).
void setLatency(unsigned Lat)
Sets the latency for this edge.
@ Artificial
Arbitrary strong DAG edge (no real dependence).
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Scheduling unit. This is a node in the scheduling DAG.
bool isCall
Is a function call.
unsigned TopReadyCycle
Cycle relative to start when node is ready.
unsigned NodeNum
Entry # of node in the node vector.
bool isUnbuffered
Uses an unbuffered resource.
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
unsigned short Latency
Node latency.
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
bool hasPhysRegDefs
Has physreg defs that are being used.
unsigned BotReadyCycle
Cycle relative to end when node is ready.
SmallVector< SDep, 4 > Succs
All sunit successors.
bool hasReservedResource
Uses a reserved resource.
bool isCommutable
Is a commutable instruction.
bool hasPhysRegUses
Has physreg uses.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
LLVM_ABI bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
void visitPostorderNode(const SUnit *SU)
Called once for each node after all predecessors are visited.
Definition ScheduleDAGInstrs.cpp:1305
bool joinPredSubtree(const SDep &PredDep, const SUnit *Succ, bool CheckLimit=true)
Joins the predecessor subtree with the successor that is its DFS parent.
Definition ScheduleDAGInstrs.cpp:1397
void addConnection(unsigned FromTree, unsigned ToTree, unsigned Depth)
Called by finalize() to record a connection between trees.
Definition ScheduleDAGInstrs.cpp:1424
void finalize()
Sets each node's subtree ID to the representative ID and record connections between trees.
Definition ScheduleDAGInstrs.cpp:1360
void visitCrossEdge(const SDep &PredDep, const SUnit *Succ)
Adds a connection for cross edges.
Definition ScheduleDAGInstrs.cpp:1354
void visitPostorderEdge(const SDep &PredDep, const SUnit *Succ)
Called once for each tree edge after calling visitPostOrderNode on the predecessor.
Definition ScheduleDAGInstrs.cpp:1347
void visitPreorder(const SUnit *SU)
Initializes this node's instruction count.
Definition ScheduleDAGInstrs.cpp:1297
bool isVisited(const SUnit *SU) const
Returns true if this node been visited by the DFS traversal.
Definition ScheduleDAGInstrs.cpp:1290
SchedDFSImpl(SchedDFSResult &r)
Definition ScheduleDAGInstrs.cpp:1282
Compute the values of each DAG node for various metrics during DFS.
friend class SchedDFSImpl
void compute(ArrayRef< SUnit > SUnits)
Compute various metrics for the DAG with given roots.
Definition ScheduleDAGInstrs.cpp:1486
void scheduleTree(unsigned SubtreeID)
Scheduler callback to update SubtreeConnectLevels when a tree is initially scheduled.
Definition ScheduleDAGInstrs.cpp:1532
LiveRegUnits LiveRegs
Set of live physical registers for updating kill flags.
DenseMap< MachineInstr *, SUnit * > MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to...
void addVRegUseDeps(SUnit *SU, unsigned OperIdx)
Adds a register data dependency if the instruction that defines the virtual register used at OperIdx ...
Definition ScheduleDAGInstrs.cpp:545
void addVRegDefDeps(SUnit *SU, unsigned OperIdx)
Adds register output and data dependencies from this SUnit to instructions that occur later in the sa...
Definition ScheduleDAGInstrs.cpp:425
virtual void finishBlock()
Cleans up after scheduling in the given block.
Definition ScheduleDAGInstrs.cpp:193
MachineBasicBlock::iterator end() const
Returns an iterator to the bottom of the current scheduling region.
std::string getDAGName() const override
Returns a label for the region of code covered by the DAG.
Definition ScheduleDAGInstrs.cpp:1231
MachineBasicBlock * BB
The block in which to insert instructions.
MachineInstr * FirstDbgValue
virtual void startBlock(MachineBasicBlock *BB)
Prepares to perform scheduling in the given block.
Definition ScheduleDAGInstrs.cpp:189
bool CanHandleTerminators
The standard DAG builder does not normally include terminators as DAG nodes because it does not creat...
void addBarrierChain(Value2SUsMap &map)
Adds barrier chain edges from all SUs in map, and then clear the map.
Definition ScheduleDAGInstrs.cpp:711
void reduceHugeMemNodeMaps(Value2SUsMap &stores, Value2SUsMap &loads, unsigned N)
Reduces maps in FIFO order, by N SUs.
Definition ScheduleDAGInstrs.cpp:1075
void addPhysRegDeps(SUnit *SU, unsigned OperIdx)
Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the ...
Definition ScheduleDAGInstrs.cpp:315
MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
void addChainDependencies(SUnit *SU, SUList &SUs, unsigned Latency)
Adds dependencies as needed from all SUs in list to SU.
const MCSchedClassDesc * getSchedClass(SUnit *SU) const
Resolves and cache a resolved scheduling class for an SUnit.
void fixupKills(MachineBasicBlock &MBB)
Fixes register kill flags that scheduling has made invalid.
Definition ScheduleDAGInstrs.cpp:1144
void addPhysRegDataDeps(SUnit *SU, unsigned OperIdx)
MO is an operand of SU's instruction that defines a physical register.
Definition ScheduleDAGInstrs.cpp:259
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
Definition ScheduleDAGInstrs.cpp:122
LaneBitmask getLaneMaskForMO(const MachineOperand &MO) const
Returns a mask for which lanes get read/written by the given (register) machine operand.
Definition ScheduleDAGInstrs.cpp:398
DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE.
SUnit * newSUnit(MachineInstr *MI)
Creates a new SUnit and return a ptr to it.
void initSUnits()
Creates an SUnit for each real instruction, numbered in top-down topological order.
Definition ScheduleDAGInstrs.cpp:593
bool addEdge(SUnit *SuccSU, const SDep &PredDep)
Add a DAG edge to the given SU with the given predecessor dependence data.
Definition ScheduleDAGInstrs.cpp:1239
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
std::list< SUnit * > SUList
A list of SUnits, used in Value2SUsMap, during DAG construction.
SUnit * BarrierChain
Remember a generic side-effecting instruction as we proceed.
BatchAAResults * getAAForDep() const
Returns a (possibly null) pointer to the current BatchAAResults.
bool TrackLaneMasks
Whether lane masks should get tracked.
void dumpNode(const SUnit &SU) const override
Definition ScheduleDAGInstrs.cpp:1195
RegUnit2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instr...
UndefValue * UnknownValue
For an unanalyzable memory access, this Value is used in maps.
VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
void buildSchedGraph(AAResults *AA, RegPressureTracker *RPTracker=nullptr, PressureDiffs *PDiffs=nullptr, LiveIntervals *LIS=nullptr, bool TrackLaneMasks=false)
Builds SUnits for the current region.
Definition ScheduleDAGInstrs.cpp:755
TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
virtual void exitRegion()
Called when the scheduler has finished scheduling the current region.
Definition ScheduleDAGInstrs.cpp:208
bool canAddEdge(SUnit *SuccSU, SUnit *PredSU)
True if an edge can be added from PredSU to SuccSU without creating a cycle.
Definition ScheduleDAGInstrs.cpp:1235
void insertBarrierChain(Value2SUsMap &map)
Inserts a barrier chain in a huge region, far below current SU.
Definition ScheduleDAGInstrs.cpp:722
const MachineLoopInfo * MLI
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
std::optional< BatchAAResults > AAForDep
MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
void addSchedBarrierDeps()
Adds dependencies from instructions in the current list of instructions being scheduled to scheduling...
Definition ScheduleDAGInstrs.cpp:212
virtual void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned regioninstrs)
Initialize the DAG and common scheduler state for a new scheduling region.
Definition ScheduleDAGInstrs.cpp:198
void dump() const override
Definition ScheduleDAGInstrs.cpp:1206
void addChainDependency(SUnit *SUa, SUnit *SUb, unsigned Latency=0)
Adds a chain edge between SUa and SUb, but only if both AAResults and Target fail to deny the depende...
Definition ScheduleDAGInstrs.cpp:572
unsigned NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
const MachineFrameInfo & MFI
bool deadDefHasNoUse(const MachineOperand &MO)
Returns true if the def register in MO has no uses.
Definition ScheduleDAGInstrs.cpp:412
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for a DAG node that points to an instruction.
Definition ScheduleDAGInstrs.cpp:1217
MachineRegisterInfo & MRI
Virtual/real register map.
void clearDAG()
Clears the DAG state (between regions).
const TargetInstrInfo * TII
Target instruction information.
std::vector< SUnit > SUnits
The scheduling units.
const TargetRegisterInfo * TRI
Target processor register info.
SUnit EntrySU
Special node for the region entry.
MachineFunction & MF
Machine function.
ScheduleDAG(const ScheduleDAG &)=delete
void dumpNodeAll(const SUnit &SU) const
void dumpNodeName(const SUnit &SU) const
SUnit ExitSU
Special node for the region exit.
SlotIndex - An opaque wrapper around machine indexes.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
std::pair< iterator, iterator > RangePair
iterator_base< SparseMultiSet * > iterator
SparseSet - Fast set implementation for objects that can be identified by small unsigned keys.
TargetInstrInfo - Interface to description of machine instruction set.
const bool HasDisjunctSubRegs
Whether the class supports two (or more) disjunct subregister indices.
LaneBitmask getLaneMask() const
Returns the combination of all lane masks of register in this class.
TargetSubtargetInfo - Generic base class for all target subtargets.
The instances of the Type class are immutable: once they are created, they are never changed.
'undef' values are things that do not have specified contents.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
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.
Abstract Attribute helper functions.
@ C
The default llvm calling convention, compatible with C.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
LLVM_ABI bool getUnderlyingObjectsForCodeGen(const Value *V, SmallVectorImpl< Value * > &Objects)
This is a wrapper around getUnderlyingObjects and adds support for basic ptrtoint+arithmetic+inttoptr...
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto reverse(ContainerTy &&C)
decltype(auto) get(const PointerIntPair< PointerTy, IntBits, IntType, PtrTraits, Info > &Pair)
void sort(IteratorTy Start, IteratorTy End)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
IterT skipDebugInstructionsBackward(IterT It, IterT Begin, bool SkipPseudoOp=true)
Decrement It until it points to a non-debug instruction or to Begin and return the resulting iterator...
bool isa(const From &Val)
isa - Return true if the parameter to the template is an instance of one of the template type argu...
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
SmallVector< UnderlyingObject, 4 > UnderlyingObjectsVector
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
decltype(auto) cast(const From &Val)
cast - Return the argument parameter cast to the specified type.
PointerUnion< const Value *, const PseudoSourceValue * > ValueType
LLVM_ABI bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Represent the ILP of the subDAG rooted at a DAG node.
unsigned Length
Length may either correspond to depth or height, depending on direction, and cycles or nodes dependin...
void dump() const
Definition ScheduleDAGInstrs.cpp:1550
void print(raw_ostream &OS) const
Definition ScheduleDAGInstrs.cpp:1542
static constexpr LaneBitmask getAll()
constexpr bool any() const
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Identify one of the processor resource kinds consumed by a particular scheduling class for the specif...
Record a physical register access.
A MapVector that performs no allocations if smaller than a certain size.
Mapping from virtual register to SUnit including an operand index.
An individual mapping from virtual register number to SUnit.