LLVM: include/llvm/CodeGen/MachineScheduler.h Source File (original) (raw)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
75#define LLVM_CODEGEN_MACHINESCHEDULER_H
76
94#include
95#include
97#include
98#include
99#include
100
101namespace llvm {
108
117
120#ifndef NDEBUG
123#else
126#endif
127
128class AAResults;
129class LiveIntervals;
130class MachineDominatorTree;
131class MachineFunction;
132class MachineInstr;
133class MachineLoopInfo;
134class RegisterClassInfo;
135class SchedDFSResult;
136class ScheduleHazardRecognizer;
137class TargetInstrInfo;
138class TargetPassConfig;
139class TargetRegisterInfo;
140
141
142
158
159
160
163 ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
164public:
166
167
169
171
176
178
179
180
184
188
192};
193
194class ScheduleDAGMI;
195
196
197
198
200
202
203
205
206
207
210
211
212
214
215
217
219};
220
221
223
224
225
226
227
231
235};
236
237
238
239
240
241
243 virtual void anchor();
244
245public:
247
248
251 unsigned NumRegionInstrs) {}
252
255
256
257
259
260
261
262
264
265
266
267
269
270
272
273
275
276
278
279
280
282
283
284
285
287
288
290
291
292
294
295
296
298
299
300
302};
303
304
305
306
307
309protected:
312 std::unique_ptr SchedImpl;
313
314
315 std::vector<std::unique_ptr> Mutations;
316
317
319
320
322
323#if LLVM_ENABLE_ABI_BREAKING_CHECKS
324
325
326 unsigned NumInstrsScheduled = 0;
327#endif
328
329public:
334
335
337
338
339
340
342 return SchedImpl->doMBBSchedRegionsTopDown();
343 }
344
345
347
348
350
351
352
353
354
355
360
363
364
365
366
370 unsigned regioninstrs) override;
371
372
373
374 void schedule() override;
375
377 void finishBlock() override;
378
379
380
382
383 void viewGraph(const Twine &Name, const Twine &Title) override;
384 void viewGraph() override;
385
386protected:
387
388
389
390
391 void postProcessDAG();
392
393
395
396
397 void updateQueues(SUnit *SU, bool IsTopNode);
398
399
400 void placeDebugValues();
401
402
403 void dumpSchedule() const;
404
405 void dumpScheduleTraceTopDown() const;
406 void dumpScheduleTraceBottomUp() const;
407
408
409 bool checkSchedLimit();
410
413
414 void releaseSucc(SUnit *SU, SDep *SuccEdge);
415 void releaseSuccessors(SUnit *SU);
416 void releasePred(SUnit *SU, SDep *PredEdge);
417 void releasePredecessors(SUnit *SU);
418};
419
420
421
423protected:
425
426
427
430
432
433
435
436
437
438
440
441
446
447
448
449
451
452
455
456
459
460public:
462 std::unique_ptr S)
466
468
469
471
472
474
475
478
479
482
483
485
489
496
497
498
499 void computeDFSResult();
500
501
503
505
506
507
508
512 unsigned regioninstrs) override;
513
514
515
516 void schedule() override;
517
518
519 unsigned computeCyclicCriticalPath();
520
521 void dump() const override;
522
523protected:
524
525
526
527
528
529
530 void buildDAGWithRegPressure();
531
532
533
535
536
537 void scheduleMI(SUnit *SU, bool IsTopNode);
538
539
540
541 void initRegPressure();
542
544
545 void updateScheduledPressure(const SUnit *SU,
546 const std::vector &NewMaxPressure);
547
548 void collectVRegUses(SUnit &SU);
549};
550
551
552
553
554
555
556
557
558
559
560
561
562
563
565 unsigned ID;
566 std::string Name;
567 std::vector<SUnit*> Queue;
568
569public:
571
572 unsigned getID() const { return ID; }
573
575
576
578
579 bool empty() const { return Queue.empty(); }
580
581 void clear() { Queue.clear(); }
582
583 unsigned size() const { return Queue.size(); }
584
585 using iterator = std::vector<SUnit*>::iterator;
586
588
590
592
594
596 Queue.push_back(SU);
598 }
599
601 (*I)->NodeQueueId &= ~ID;
602 *I = Queue.back();
603 unsigned idx = I - Queue.begin();
604 Queue.pop_back();
605 return Queue.begin() + idx;
606 }
607
609};
610
611
613
616
617
619
621
622
624
626
634
636};
637
638
639
640
641
642
643
644
645
646
647
648
649
650
652public:
653
654
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
673
674public:
675
677
678
679
680
681
682
683
684
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
742 unsigned ReleaseAtCycle) {
743 return std::make_pair<long, long>((long)C - (long)ReleaseAtCycle + 1L,
744 (long)C - (long)AcquireAtCycle + 1L);
745 }
747 unsigned ReleaseAtCycle) {
748 return std::make_pair<long, long>((long)C + (long)AcquireAtCycle,
749 (long)C + (long)ReleaseAtCycle);
750 }
751
752private:
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 LLVM_ABI unsigned getFirstAvailableAt(
800 unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle,
801 std::function<IntervalTy(unsigned, unsigned, unsigned)> IntervalBuilder)
802 const;
803
804public:
805
806
807
809 unsigned AcquireAtCycle,
810 unsigned ReleaseAtCycle) const {
811 return getFirstAvailableAt(CurrCycle, AcquireAtCycle, ReleaseAtCycle,
813 }
815 unsigned AcquireAtCycle,
816 unsigned ReleaseAtCycle) const {
817 return getFirstAvailableAt(CurrCycle, AcquireAtCycle, ReleaseAtCycle,
819 }
820
821private:
822 std::list _Intervals;
823
824
825
826
827
828 LLVM_ABI void sortAndMerge();
829
830public:
831
833 bool empty() const { return _Intervals.empty(); }
835 : _Intervals(Intervals) {
836 sortAndMerge();
837 }
838
841 return c1._Intervals == c2._Intervals;
842 }
845 os << "{ ";
846 for (auto p : Segments._Intervals)
847 os << "[" << p.first << ", " << p.second << "), ";
848 os << "}\n";
849 return os;
850 }
851};
852
853
854
855
857public:
858
859 enum {
863 };
864
868
871
873
874private:
875
876
877 bool CheckPending;
878
879
880
881
882 unsigned CurrCycle;
883
884
885 unsigned CurrMOps;
886
887
888 unsigned MinReadyCycle;
889
890
891 unsigned ExpectedLatency;
892
893
894
895
896 unsigned DependentLatency;
897
898
899
900 unsigned RetiredMOps;
901
902
903
904
905
906
908
909
910 unsigned MaxExecutedResCount;
911
912
913 unsigned ZoneCritResIdx;
914
915
916 bool IsResourceLimited;
917
918public:
919private:
920
921
922 std::map<unsigned, ResourceSegments> ReservedResourceSegments;
923 std::vector ReservedCycles;
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
954
955
957
958#if LLVM_ENABLE_ABI_BREAKING_CHECKS
959
960
961 unsigned MaxObservedStall;
962#endif
963
964public:
965
966
974
976
979
983
984
986
987
989
990
992
993
994
995
997 return std::max(ExpectedLatency, CurrCycle);
998 }
999
1003
1005 return ExecutedResCounts[ResIdx];
1006 }
1007
1008
1009
1011 if (!ZoneCritResIdx)
1012 return RetiredMOps * SchedModel->getMicroOpFactor();
1014 }
1015
1016
1017
1018
1020 return std::max(CurrCycle * SchedModel->getLatencyFactor(),
1021 MaxExecutedResCount);
1022 }
1023
1025
1026
1028
1029
1030
1032
1034 unsigned ReleaseAtCycle,
1035 unsigned AcquireAtCycle);
1036
1037 LLVM_ABI std::pair<unsigned, unsigned>
1039 unsigned ReleaseAtCycle, unsigned AcquireAtCycle);
1040
1042 return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin &&
1043 ->getProcResource(PIdx)->BufferSize;
1044 }
1045
1047
1049
1051
1052
1053
1054
1055
1056
1057
1058
1059
1061 unsigned Idx = 0);
1062
1064
1066
1068 unsigned Cycles, unsigned ReadyCycle,
1069 unsigned StartAtCycle);
1070
1072
1074
1076
1077
1078
1079
1081
1082
1085};
1086
1087
1088
1089
1091public:
1092
1093
1113
1114#ifndef NDEBUG
1116#endif
1117
1118
1123
1125
1132 return !(*this == RHS);
1133 }
1134 };
1135
1136
1138
1140
1141
1143
1145
1153 };
1154
1155
1156
1159
1160
1162
1163
1165
1166
1168
1169
1171
1172
1174
1177
1180 SU = nullptr;
1185 }
1186
1188
1189
1197 }
1198
1201 };
1202
1203protected:
1210
1212
1214
1216
1219
1221
1222#ifndef NDEBUG
1224#endif
1225
1226private:
1227 bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
1228 bool ComputeRemLatency, unsigned &RemLatency) const;
1229};
1230
1231
1233 GenericSchedulerBase::SchedCandidate &TryCand,
1234 GenericSchedulerBase::SchedCandidate &Cand,
1237 GenericSchedulerBase::SchedCandidate &TryCand,
1238 GenericSchedulerBase::SchedCandidate &Cand,
1240LLVM_ABI bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
1241 GenericSchedulerBase::SchedCandidate &Cand,
1242 SchedBoundary &Zone);
1244 const PressureChange &CandP,
1245 GenericSchedulerBase::SchedCandidate &TryCand,
1246 GenericSchedulerBase::SchedCandidate &Cand,
1248 const TargetRegisterInfo *TRI,
1249 const MachineFunction &MF);
1252
1253
1254
1256public:
1260
1263 unsigned NumRegionInstrs) override;
1264
1265 void dumpPolicy() const override;
1266
1270
1274
1276
1277 SUnit *pickNode(bool &IsTopNode) override;
1278
1279 void schedNode(SUnit *SU, bool IsTopNode) override;
1280
1288
1296
1297 void registerRoots() override;
1298
1299protected:
1301
1302
1305
1308
1309
1311
1313
1315
1319
1322
1324
1329
1331};
1332
1333
1334
1335
1336
1337
1339protected:
1343
1344
1346
1348
1351
1352public:
1356
1358
1362
1363
1365
1367
1368 void registerRoots() override;
1369
1370 SUnit *pickNode(bool &IsTopNode) override;
1371
1372 SUnit *pickNodeBidirectional(bool &IsTopNode);
1373
1375 llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1376 }
1377
1378 void schedNode(SUnit *SU, bool IsTopNode) override;
1379
1386
1393
1394protected:
1395 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1396
1397 void pickNodeFromQueue(SchedBoundary &Zone, SchedCandidate &Cand);
1398};
1399
1400
1401
1402LLVM_ABI std::unique_ptr
1404 const TargetRegisterInfo *TRI,
1405 bool ReorderWhileClustering = false);
1406
1407
1408
1409LLVM_ABI std::unique_ptr
1411 const TargetRegisterInfo *TRI,
1412 bool ReorderWhileClustering = false);
1413
1414LLVM_ABI std::unique_ptr
1416 const TargetRegisterInfo *TRI);
1417
1418
1419
1420
1421template
1425
1426
1427
1428
1429
1431
1433
1435 if (!MacroFusions.empty())
1437 return DAG;
1438}
1439
1440
1441template
1444 true);
1446
1448 if (!MacroFusions.empty())
1450 return DAG;
1451}
1452
1454
1455
1456 std::unique_ptr<impl_detail::MachineSchedulerImpl> Impl;
1458
1459public:
1465};
1466
1468 : public PassInfoMixin {
1469
1470
1471 std::unique_ptr<impl_detail::PostMachineSchedulerImpl> Impl;
1473
1474public:
1480};
1481}
1482
1483#endif
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
const TargetInstrInfo & TII
This file implements a class to represent arbitrary precision integral constant values and operations...
This file implements the BitVector class.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
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")
Register const TargetRegisterInfo * TRI
This file defines the SmallVector class.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)
Initialize the set of available library functions based on the specified target triple.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
void traceCandidate(const SchedCandidate &Cand)
unsigned TopIdx
Definition MachineScheduler.h:1207
SchedRemainder Rem
Definition MachineScheduler.h:1213
unsigned NumRegionInstrs
Definition MachineScheduler.h:1209
LLVM_ABI void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone, SchedBoundary *OtherZone)
Set the CandPolicy given a scheduling zone given the current resources and latencies inside and outsi...
unsigned BotIdx
Definition MachineScheduler.h:1208
MachineSchedPolicy RegionPolicy
Definition MachineScheduler.h:1211
const TargetSchedModel * SchedModel
Definition MachineScheduler.h:1205
static const char * getReasonStr(GenericSchedulerBase::CandReason Reason)
MachineSchedPolicy getPolicy() const override
Definition MachineScheduler.h:1220
GenericSchedulerBase(const MachineSchedContext *C)
Definition MachineScheduler.h:1215
const MachineSchedContext * Context
Definition MachineScheduler.h:1204
CandReason
Represent the type of SchedCandidate found within a single queue.
Definition MachineScheduler.h:1094
@ RegExcess
Definition MachineScheduler.h:1098
@ RegMax
Definition MachineScheduler.h:1103
@ ResourceDemand
Definition MachineScheduler.h:1105
@ FirstValid
Definition MachineScheduler.h:1111
@ Only1
Definition MachineScheduler.h:1096
@ ResourceReduce
Definition MachineScheduler.h:1104
@ Cluster
Definition MachineScheduler.h:1101
@ TopPathReduce
Definition MachineScheduler.h:1109
@ NoCand
Definition MachineScheduler.h:1095
@ BotHeightReduce
Definition MachineScheduler.h:1106
@ RegCritical
Definition MachineScheduler.h:1099
@ NodeOrder
Definition MachineScheduler.h:1110
@ PhysReg
Definition MachineScheduler.h:1097
@ Stall
Definition MachineScheduler.h:1100
@ BotPathReduce
Definition MachineScheduler.h:1107
@ Weak
Definition MachineScheduler.h:1102
@ TopDepthReduce
Definition MachineScheduler.h:1108
const TargetRegisterInfo * TRI
Definition MachineScheduler.h:1206
void checkAcyclicLatency()
Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycle...
SchedCandidate BotCand
Candidate last picked from Bot boundary.
Definition MachineScheduler.h:1312
SchedBoundary Top
Definition MachineScheduler.h:1303
SchedCandidate TopCand
Candidate last picked from Top boundary.
Definition MachineScheduler.h:1310
unsigned TopClusterID
Definition MachineScheduler.h:1306
SchedBoundary Bot
Definition MachineScheduler.h:1304
virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand, SchedBoundary *Zone) const
Apply a set of heuristics to a new candidate.
ScheduleDAGMILive * DAG
Definition MachineScheduler.h:1300
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
Definition MachineScheduler.h:1289
void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop, const RegPressureTracker &RPTracker, RegPressureTracker &TempTracker)
bool shouldTrackPressure() const override
Check if pressure tracking is needed before building the DAG and initializing this strategy.
Definition MachineScheduler.h:1267
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
Definition MachineScheduler.h:1281
void reschedulePhysReg(SUnit *SU, bool isTop)
void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the queue.
bool shouldTrackLaneMasks() const override
Returns true if lanemasks should be tracked.
Definition MachineScheduler.h:1271
GenericScheduler(const MachineSchedContext *C)
Definition MachineScheduler.h:1257
SUnit * pickNodeBidirectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
unsigned BotClusterID
Definition MachineScheduler.h:1307
MachineInstrBundleIterator< MachineInstr > iterator
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Representation of each machine instruction.
MachinePassRegistryListener - Listener to adds and removals of nodes in registration list.
MachinePassRegistryNode(const char *N, const char *D, ScheduleDAGInstrs *C)
MachinePassRegistryNode * getNext() const
MachinePassRegistry - Track the registration of machine passes.
static void setListener(MachinePassRegistryListener< FunctionPassCtor > *L)
Definition MachineScheduler.h:189
static LLVM_ABI MachinePassRegistry< ScheduleDAGCtor > Registry
Definition MachineScheduler.h:170
ScheduleDAGCtor FunctionPassCtor
Definition MachineScheduler.h:168
MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
Definition MachineScheduler.h:172
~MachineSchedRegistry()
Definition MachineScheduler.h:177
static MachineSchedRegistry * getList()
Definition MachineScheduler.h:185
ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor
Definition MachineScheduler.h:165
MachineSchedRegistry * getNext() const
Definition MachineScheduler.h:181
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
Definition MachineScheduler.h:242
virtual bool shouldTrackPressure() const
Check if pressure tracking is needed before building the DAG and initializing this strategy.
Definition MachineScheduler.h:258
virtual void leaveMBB()
Tell the strategy that current MBB is done.
Definition MachineScheduler.h:277
virtual void enterMBB(MachineBasicBlock *MBB)
Tell the strategy that MBB is about to be processed.
Definition MachineScheduler.h:274
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
Definition MachineScheduler.h:289
virtual void schedNode(SUnit *SU, bool IsTopNode)=0
Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an instruction and updated scheduled/rem...
virtual ~MachineSchedStrategy()=default
virtual void initialize(ScheduleDAGMI *DAG)=0
Initialize the strategy after building the DAG for a new region.
virtual MachineSchedPolicy getPolicy() const
Definition MachineScheduler.h:253
virtual void releaseTopNode(SUnit *SU)=0
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
virtual void dumpPolicy() const
Definition MachineScheduler.h:254
virtual bool doMBBSchedRegionsTopDown() const
Definition MachineScheduler.h:268
virtual SUnit * pickNode(bool &IsTopNode)=0
Pick the next node to schedule, or return NULL.
virtual void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs)
Optionally override the per-region scheduling policy.
Definition MachineScheduler.h:249
virtual void releaseBottomNode(SUnit *SU)=0
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
virtual bool shouldTrackLaneMasks() const
Returns true if lanemasks should be tracked.
Definition MachineScheduler.h:263
virtual void registerRoots()
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
Definition MachineScheduler.h:281
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI MachineSchedulerPass(const TargetMachine *TM)
LLVM_ABI ~MachineSchedulerPass()
LLVM_ABI MachineSchedulerPass(MachineSchedulerPass &&Other)
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Optionally override the per-region scheduling policy.
bool shouldTrackPressure() const override
PostRA scheduling does not track pressure.
Definition MachineScheduler.h:1364
void scheduleTree(unsigned SubtreeID) override
Scheduler callback to notify that a new subtree is scheduled.
Definition MachineScheduler.h:1374
ScheduleDAGMI * DAG
Definition MachineScheduler.h:1340
SchedBoundary Top
Definition MachineScheduler.h:1341
SchedCandidate BotCand
Candidate last picked from Bot boundary.
Definition MachineScheduler.h:1347
SchedBoundary Bot
Definition MachineScheduler.h:1342
unsigned TopClusterID
Definition MachineScheduler.h:1349
SchedCandidate TopCand
Candidate last picked from Top boundary.
Definition MachineScheduler.h:1345
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
Definition MachineScheduler.h:1380
~PostGenericScheduler() override=default
unsigned BotClusterID
Definition MachineScheduler.h:1350
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
Definition MachineScheduler.h:1387
PostGenericScheduler(const MachineSchedContext *C)
Definition MachineScheduler.h:1353
LLVM_ABI PostMachineSchedulerPass(PostMachineSchedulerPass &&Other)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI PostMachineSchedulerPass(const TargetMachine *TM)
LLVM_ABI ~PostMachineSchedulerPass()
A set of analyses that are preserved following a run of a transformation pass.
List of PressureChanges in order of increasing, unique PSetID.
Helpers for implementing custom MachineSchedStrategy classes.
Definition MachineScheduler.h:564
void push(SUnit *SU)
Definition MachineScheduler.h:595
iterator end()
Definition MachineScheduler.h:589
iterator find(SUnit *SU)
Definition MachineScheduler.h:593
iterator begin()
Definition MachineScheduler.h:587
ArrayRef< SUnit * > elements()
Definition MachineScheduler.h:591
LLVM_ABI void dump() const
void clear()
Definition MachineScheduler.h:581
ReadyQueue(unsigned id, const Twine &name)
Definition MachineScheduler.h:570
bool isInQueue(SUnit *SU) const
Definition MachineScheduler.h:577
std::vector< SUnit * >::iterator iterator
Definition MachineScheduler.h:585
bool empty() const
Definition MachineScheduler.h:579
StringRef getName() const
Definition MachineScheduler.h:574
unsigned size() const
Definition MachineScheduler.h:583
iterator remove(iterator I)
Definition MachineScheduler.h:600
unsigned getID() const
Definition MachineScheduler.h:572
Track the current register pressure at some position in the instruction stream, and remember the high...
ResourceSegments()=default
LLVM_ABI void add(IntervalTy A, const unsigned CutOff=10)
Adds an interval [a, b) to the collection of the instance.
bool empty() const
Definition MachineScheduler.h:833
static IntervalTy getResourceIntervalBottom(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
These function return the interval used by a resource in bottom and top scheduling.
Definition MachineScheduler.h:741
friend bool operator==(const ResourceSegments &c1, const ResourceSegments &c2)
Definition MachineScheduler.h:839
static LLVM_ABI bool intersects(IntervalTy A, IntervalTy B)
Checks whether intervals intersect.
unsigned getFirstAvailableAtFromTop(unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle) const
Definition MachineScheduler.h:814
friend llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const ResourceSegments &Segments)
Definition MachineScheduler.h:843
std::pair< int64_t, int64_t > IntervalTy
Represents an interval of discrete integer values closed on the left and open on the right: [a,...
Definition MachineScheduler.h:655
static IntervalTy getResourceIntervalTop(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
Definition MachineScheduler.h:746
ResourceSegments(const std::list< IntervalTy > &Intervals)
Definition MachineScheduler.h:834
unsigned getFirstAvailableAtFromBottom(unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle) const
getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop should be merged in a single function in...
Definition MachineScheduler.h:808
Scheduling unit. This is a node in the scheduling DAG.
unsigned NodeQueueId
Queue id of node.
unsigned TopReadyCycle
Cycle relative to start when node is ready.
unsigned NodeNum
Entry # of node in the node vector.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
bool isScheduled
True once scheduled.
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Each Scheduling boundary is associated with ready queues.
Definition MachineScheduler.h:856
LLVM_ABI unsigned getNextResourceCycleByInstance(unsigned InstanceIndex, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
Compute the next cycle at which the given processor resource unit can be scheduled.
LLVM_ABI void releasePending()
Release pending ready nodes in to the available queue.
unsigned getDependentLatency() const
Definition MachineScheduler.h:991
bool isReservedGroup(unsigned PIdx) const
Definition MachineScheduler.h:1041
unsigned getScheduledLatency() const
Get the number of latency cycles "covered" by the scheduled instructions.
Definition MachineScheduler.h:996
LLVM_ABI void incExecutedResources(unsigned PIdx, unsigned Count)
bool isResourceLimited() const
Definition MachineScheduler.h:1027
const TargetSchedModel * SchedModel
Definition MachineScheduler.h:866
unsigned getExecutedCount() const
Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execut...
Definition MachineScheduler.h:1019
LLVM_ABI unsigned getLatencyStallCycles(SUnit *SU)
Get the difference between the given SUnit's ready time and the current cycle.
SchedBoundary(const SchedBoundary &other)=delete
LLVM_ABI unsigned findMaxLatency(ArrayRef< SUnit * > ReadySUs)
ScheduleDAGMI * DAG
Definition MachineScheduler.h:865
LLVM_ABI void dumpReservedCycles() const
Dump the state of the information that tracks resource usage.
bool isTop() const
Definition MachineScheduler.h:980
@ LogMaxQID
Definition MachineScheduler.h:862
@ TopQID
Definition MachineScheduler.h:860
@ BotQID
Definition MachineScheduler.h:861
LLVM_ABI unsigned getOtherResourceCount(unsigned &OtherCritIdx)
SchedRemainder * Rem
Definition MachineScheduler.h:867
LLVM_ABI void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
unsigned getCriticalCount() const
Get the scaled count of scheduled micro-ops and resources, including executed resources.
Definition MachineScheduler.h:1010
LLVM_ABI SUnit * pickOnlyChoice()
Call this before applying any other heuristics to the Available queue.
LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue, unsigned Idx=0)
Release SU to make it ready.
LLVM_ABI unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles, unsigned ReadyCycle, unsigned StartAtCycle)
Add the given processor resource to this scheduled zone.
SchedBoundary(unsigned ID, const Twine &Name)
Pending queues extend the ready queues with the same ID and the PendingFlag set.
Definition MachineScheduler.h:967
LLVM_ABI ~SchedBoundary()
ScheduleHazardRecognizer * HazardRec
Definition MachineScheduler.h:872
ReadyQueue Available
Definition MachineScheduler.h:869
LLVM_ABI void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem)
SchedBoundary & operator=(const SchedBoundary &other)=delete
unsigned getResourceCount(unsigned ResIdx) const
Definition MachineScheduler.h:1004
LLVM_ABI void bumpCycle(unsigned NextCycle)
Move the boundary of scheduled code by one cycle.
unsigned getCurrMOps() const
Micro-ops issued in the current cycle.
Definition MachineScheduler.h:988
unsigned getCurrCycle() const
Number of cycles to issue the instructions scheduled in this zone.
Definition MachineScheduler.h:985
ReadyQueue Pending
Definition MachineScheduler.h:870
LLVM_ABI bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
LLVM_ABI std::pair< unsigned, unsigned > getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
Compute the next cycle at which the given processor resource can be scheduled.
LLVM_ABI void dumpScheduledState() const
LLVM_ABI void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
unsigned getZoneCritResIdx() const
Definition MachineScheduler.h:1024
unsigned getUnscheduledLatency(SUnit *SU) const
Definition MachineScheduler.h:1000
Compute the values of each DAG node for various metrics during DFS.
A ScheduleDAG for scheduling lists of MachineInstr.
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
const MachineLoopInfo * MLI
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
Definition MachineScheduler.h:422
VReg2SUnitMultiMap VRegUses
Maps vregs to the SUnits of their uses in the current scheduling region.
Definition MachineScheduler.h:434
PressureDiff & getPressureDiff(const SUnit *SU)
Definition MachineScheduler.h:490
SchedDFSResult * DFSResult
Information about DAG subtrees.
Definition MachineScheduler.h:428
bool ShouldTrackLaneMasks
Definition MachineScheduler.h:443
RegPressureTracker BotRPTracker
Definition MachineScheduler.h:458
std::vector< PressureChange > RegionCriticalPSets
List of pressure sets that exceed the target's pressure limit before scheduling, listed in increasing...
Definition MachineScheduler.h:450
IntervalPressure TopPressure
The top of the unscheduled zone.
Definition MachineScheduler.h:453
PressureDiffs SUPressureDiffs
Definition MachineScheduler.h:439
const RegPressureTracker & getBotRPTracker() const
Definition MachineScheduler.h:481
ScheduleDAGMILive(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
Definition MachineScheduler.h:461
IntervalPressure BotPressure
The bottom of the unscheduled zone.
Definition MachineScheduler.h:457
bool isTrackingPressure() const
Return true if register pressure tracking is enabled.
Definition MachineScheduler.h:473
bool hasVRegLiveness() const override
Return true if this DAG supports VReg liveness and RegPressure.
Definition MachineScheduler.h:470
RegisterClassInfo * RegClassInfo
Definition MachineScheduler.h:424
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
Definition MachineScheduler.h:502
const PressureDiff & getPressureDiff(const SUnit *SU) const
Definition MachineScheduler.h:493
const RegPressureTracker & getTopRPTracker() const
Definition MachineScheduler.h:477
RegPressureTracker RPTracker
Definition MachineScheduler.h:445
bool ShouldTrackPressure
Register pressure in this region computed by initRegPressure.
Definition MachineScheduler.h:442
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
Definition MachineScheduler.h:484
const IntervalPressure & getBotPressure() const
Get current register pressure for the bottom scheduled instructions.
Definition MachineScheduler.h:480
BitVector & getScheduledTrees()
Definition MachineScheduler.h:504
MachineBasicBlock::iterator LiveRegionEnd
Definition MachineScheduler.h:431
BitVector ScheduledTrees
Definition MachineScheduler.h:429
const IntervalPressure & getTopPressure() const
Get current register pressure for the top scheduled instructions.
Definition MachineScheduler.h:476
const std::vector< PressureChange > & getRegionCriticalPSets() const
Definition MachineScheduler.h:486
IntervalPressure RegPressure
Definition MachineScheduler.h:444
RegPressureTracker TopRPTracker
Definition MachineScheduler.h:454
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
Definition MachineScheduler.h:308
std::unique_ptr< MachineSchedStrategy > SchedImpl
Definition MachineScheduler.h:312
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Add a postprocessing step to the DAG builder.
Definition MachineScheduler.h:356
MachineBasicBlock::iterator top() const
Definition MachineScheduler.h:361
ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S, bool RemoveKillFlags)
Definition MachineScheduler.h:330
MachineBasicBlock::iterator bottom() const
Definition MachineScheduler.h:362
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
Definition MachineScheduler.h:321
bool doMBBSchedRegionsTopDown() const override
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
Definition MachineScheduler.h:341
virtual bool hasVRegLiveness() const
Return true if this DAG supports VReg liveness and RegPressure.
Definition MachineScheduler.h:349
AAResults * AA
Definition MachineScheduler.h:310
LiveIntervals * getLIS() const
Definition MachineScheduler.h:346
~ScheduleDAGMI() override
LiveIntervals * LIS
Definition MachineScheduler.h:311
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
Definition MachineScheduler.h:318
std::vector< std::unique_ptr< ScheduleDAGMutation > > Mutations
Ordered list of DAG postprocessing steps.
Definition MachineScheduler.h:315
const TargetInstrInfo * TII
Target instruction information.
const TargetRegisterInfo * TRI
Target processor register info.
MachineFunction & MF
Machine function.
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
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.
Primary interface to the complete machine description for the target machine.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual std::vector< MacroFusionPredTy > getMacroFusions() const
Get the list of MacroFusion predicates.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Impl class for MachineScheduler.
Impl class for PostMachineScheduler.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
Definition MachineScheduler.h:109
Direction
Definition MachineScheduler.h:110
@ Bidirectional
Definition MachineScheduler.h:114
@ BottomUp
Definition MachineScheduler.h:113
@ Unspecified
Definition MachineScheduler.h:111
@ TopDown
Definition MachineScheduler.h:112
template class LLVM_TEMPLATE_ABI opt< bool >
Definition MachineScheduler.h:102
This is an optimization pass for GlobalISel generic memory operations.
ScheduleDAGMILive * createSchedLive(MachineSchedContext *C)
Create the standard converging machine scheduler.
Definition MachineScheduler.h:1422
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop)
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createMacroFusionDAGMutation(ArrayRef< MacroFusionPredTy > Predicates, bool BranchOnly=false)
Create a DAG scheduling mutation to pair instructions back to back for instructions that benefit acco...
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
SparseMultiSet< VReg2SUnit, Register, VirtReg2IndexFunctor > VReg2SUnitMultiMap
Track local uses of virtual registers.
ScheduleDAGMI * createSchedPostRA(MachineSchedContext *C)
Create a generic scheduler with no vreg liveness or DAG mutation passes.
Definition MachineScheduler.h:1442
cl::opt< bool > ViewMISchedDAGs
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ReorderWhileClustering=false)
If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...
FunctionAddr VTableAddr Count
LLVM_ABI cl::opt< bool > VerifyScheduling
LLVM_ABI bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI, bool ReorderWhileClustering=false)
If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...
LLVM_ABI bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
Return true if this heuristic determines order.
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
LLVM_ABI cl::opt< MISched::Direction > PreRADirection
LLVM_ABI int biasPhysReg(const SUnit *SU, bool isTop)
Minimize physical register live ranges.
cl::opt< bool > PrintDAGs
Implement std::hash so that hash_code can be used in STL containers.
Policy for scheduling the next instruction in the candidate's zone.
Definition MachineScheduler.h:1119
bool operator==(const CandPolicy &RHS) const
Definition MachineScheduler.h:1126
unsigned ReduceResIdx
Definition MachineScheduler.h:1121
unsigned DemandResIdx
Definition MachineScheduler.h:1122
bool operator!=(const CandPolicy &RHS) const
Definition MachineScheduler.h:1131
bool ReduceLatency
Definition MachineScheduler.h:1120
Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...
Definition MachineScheduler.h:1157
SchedCandidate(const CandPolicy &Policy)
Definition MachineScheduler.h:1176
void setBest(SchedCandidate &Best)
Definition MachineScheduler.h:1190
SUnit * SU
Definition MachineScheduler.h:1161
void reset(const CandPolicy &NewPolicy)
Definition MachineScheduler.h:1178
LLVM_ABI void initResourceDelta(const ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
SchedCandidate()
Definition MachineScheduler.h:1175
RegPressureDelta RPDelta
Definition MachineScheduler.h:1170
bool AtTop
Definition MachineScheduler.h:1167
SchedResourceDelta ResDelta
Definition MachineScheduler.h:1173
bool isValid() const
Definition MachineScheduler.h:1187
CandReason Reason
Definition MachineScheduler.h:1164
CandPolicy Policy
Definition MachineScheduler.h:1158
Status of an instruction's critical resource consumption.
Definition MachineScheduler.h:1137
SchedResourceDelta()=default
unsigned CritResources
Definition MachineScheduler.h:1139
bool operator!=(const SchedResourceDelta &RHS) const
Definition MachineScheduler.h:1150
bool operator==(const SchedResourceDelta &RHS) const
Definition MachineScheduler.h:1146
unsigned DemandedResources
Definition MachineScheduler.h:1142
RegisterPressure computed within a region of instructions delimited by TopIdx and BottomIdx.
Summarize the scheduling resources required for an instruction of a particular scheduling class.
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
Definition MachineScheduler.h:143
MachineFunction * MF
Definition MachineScheduler.h:144
const MachineDominatorTree * MDT
Definition MachineScheduler.h:146
RegisterClassInfo * RegClassInfo
Definition MachineScheduler.h:151
AAResults * AA
Definition MachineScheduler.h:148
const MachineLoopInfo * MLI
Definition MachineScheduler.h:145
LiveIntervals * LIS
Definition MachineScheduler.h:149
const TargetMachine * TM
Definition MachineScheduler.h:147
MachineSchedContext & operator=(const MachineSchedContext &other)=delete
MachineSchedContext(const MachineSchedContext &other)=delete
Define a generic scheduling policy for targets that don't provide their own MachineSchedStrategy.
Definition MachineScheduler.h:199
bool OnlyTopDown
Definition MachineScheduler.h:208
bool DisableLatencyHeuristic
Definition MachineScheduler.h:213
bool OnlyBottomUp
Definition MachineScheduler.h:209
MachineSchedPolicy()=default
bool ComputeDFSResult
Definition MachineScheduler.h:216
bool ShouldTrackPressure
Definition MachineScheduler.h:201
bool ShouldTrackLaneMasks
Track LaneMasks to allow reordering of independent subregister writes of the same vreg.
Definition MachineScheduler.h:204
A CRTP mix-in to automatically provide informational APIs needed for passes.
Store the effects of a change in pressure on things that MI scheduler cares about.
MachineBasicBlock::iterator RegionBegin
RegionBegin is the first instruction in the scheduling region, and RegionEnd is either MBB->end() or ...
Definition MachineScheduler.h:228
unsigned NumRegionInstrs
Definition MachineScheduler.h:230
MachineBasicBlock::iterator RegionEnd
Definition MachineScheduler.h:229
SchedRegion(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E, unsigned N)
Definition MachineScheduler.h:232
Summarize the unscheduled region.
Definition MachineScheduler.h:612
SchedRemainder()
Definition MachineScheduler.h:625
LLVM_ABI void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
unsigned RemIssueCount
Definition MachineScheduler.h:618
unsigned CriticalPath
Definition MachineScheduler.h:614
unsigned CyclicCritPath
Definition MachineScheduler.h:615
SmallVector< unsigned, 16 > RemainingCounts
Definition MachineScheduler.h:623
bool IsAcyclicLatencyLimited
Definition MachineScheduler.h:620
void reset()
Definition MachineScheduler.h:627