LLVM  9.0.0svn
MachineScheduler.h
Go to the documentation of this file.
1 //===- MachineScheduler.h - MachineInstr Scheduling Pass --------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file provides an interface for customizing the standard MachineScheduler
10 // pass. Note that the entire pass may be replaced as follows:
11 //
12 // <Target>TargetMachine::createPassConfig(PassManagerBase &PM) {
13 // PM.substitutePass(&MachineSchedulerID, &CustomSchedulerPassID);
14 // ...}
15 //
16 // The MachineScheduler pass is only responsible for choosing the regions to be
17 // scheduled. Targets can override the DAG builder and scheduler without
18 // replacing the pass as follows:
19 //
20 // ScheduleDAGInstrs *<Target>PassConfig::
21 // createMachineScheduler(MachineSchedContext *C) {
22 // return new CustomMachineScheduler(C);
23 // }
24 //
25 // The default scheduler, ScheduleDAGMILive, builds the DAG and drives list
26 // scheduling while updating the instruction stream, register pressure, and live
27 // intervals. Most targets don't need to override the DAG builder and list
28 // scheduler, but subtargets that require custom scheduling heuristics may
29 // plugin an alternate MachineSchedStrategy. The strategy is responsible for
30 // selecting the highest priority node from the list:
31 //
32 // ScheduleDAGInstrs *<Target>PassConfig::
33 // createMachineScheduler(MachineSchedContext *C) {
34 // return new ScheduleDAGMILive(C, CustomStrategy(C));
35 // }
36 //
37 // The DAG builder can also be customized in a sense by adding DAG mutations
38 // that will run after DAG building and before list scheduling. DAG mutations
39 // can adjust dependencies based on target-specific knowledge or add weak edges
40 // to aid heuristics:
41 //
42 // ScheduleDAGInstrs *<Target>PassConfig::
43 // createMachineScheduler(MachineSchedContext *C) {
44 // ScheduleDAGMI *DAG = createGenericSchedLive(C);
45 // DAG->addMutation(new CustomDAGMutation(...));
46 // return DAG;
47 // }
48 //
49 // A target that supports alternative schedulers can use the
50 // MachineSchedRegistry to allow command line selection. This can be done by
51 // implementing the following boilerplate:
52 //
53 // static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) {
54 // return new CustomMachineScheduler(C);
55 // }
56 // static MachineSchedRegistry
57 // SchedCustomRegistry("custom", "Run my target's custom scheduler",
58 // createCustomMachineSched);
59 //
60 //
61 // Finally, subtargets that don't need to implement custom heuristics but would
62 // like to configure the GenericScheduler's policy for a given scheduler region,
63 // including scheduling direction and register pressure tracking policy, can do
64 // this:
65 //
66 // void <SubTarget>Subtarget::
67 // overrideSchedPolicy(MachineSchedPolicy &Policy,
68 // unsigned NumRegionInstrs) const {
69 // Policy.<Flag> = true;
70 // }
71 //
72 //===----------------------------------------------------------------------===//
73 
74 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H
75 #define LLVM_CODEGEN_MACHINESCHEDULER_H
76 
77 #include "llvm/ADT/ArrayRef.h"
78 #include "llvm/ADT/BitVector.h"
79 #include "llvm/ADT/STLExtras.h"
80 #include "llvm/ADT/SmallVector.h"
81 #include "llvm/ADT/StringRef.h"
82 #include "llvm/ADT/Twine.h"
93 #include <algorithm>
94 #include <cassert>
95 #include <memory>
96 #include <string>
97 #include <vector>
98 
99 namespace llvm {
100 
101 extern cl::opt<bool> ForceTopDown;
102 extern cl::opt<bool> ForceBottomUp;
103 
104 class LiveIntervals;
105 class MachineDominatorTree;
106 class MachineFunction;
107 class MachineInstr;
108 class MachineLoopInfo;
109 class RegisterClassInfo;
110 class SchedDFSResult;
111 class ScheduleHazardRecognizer;
112 class TargetInstrInfo;
113 class TargetPassConfig;
114 class TargetRegisterInfo;
115 
116 /// MachineSchedContext provides enough context from the MachineScheduler pass
117 /// for the target to instantiate a scheduler.
119  MachineFunction *MF = nullptr;
120  const MachineLoopInfo *MLI = nullptr;
121  const MachineDominatorTree *MDT = nullptr;
122  const TargetPassConfig *PassConfig = nullptr;
123  AliasAnalysis *AA = nullptr;
124  LiveIntervals *LIS = nullptr;
125 
127 
129  virtual ~MachineSchedContext();
130 };
131 
132 /// MachineSchedRegistry provides a selection of available machine instruction
133 /// schedulers.
135  : public MachinePassRegistryNode<
136  ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
137 public:
139 
140  // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
142 
144 
145  MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
146  : MachinePassRegistryNode(N, D, C) {
147  Registry.Add(this);
148  }
149 
150  ~MachineSchedRegistry() { Registry.Remove(this); }
151 
152  // Accessors.
153  //
156  }
157 
159  return (MachineSchedRegistry *)Registry.getList();
160  }
161 
163  Registry.setListener(L);
164  }
165 };
166 
167 class ScheduleDAGMI;
168 
169 /// Define a generic scheduling policy for targets that don't provide their own
170 /// MachineSchedStrategy. This can be overriden for each scheduling region
171 /// before building the DAG.
173  // Allow the scheduler to disable register pressure tracking.
174  bool ShouldTrackPressure = false;
175  /// Track LaneMasks to allow reordering of independent subregister writes
176  /// of the same vreg. \sa MachineSchedStrategy::shouldTrackLaneMasks()
177  bool ShouldTrackLaneMasks = false;
178 
179  // Allow the scheduler to force top-down or bottom-up scheduling. If neither
180  // is true, the scheduler runs in both directions and converges.
181  bool OnlyTopDown = false;
182  bool OnlyBottomUp = false;
183 
184  // Disable heuristic that tries to fetch nodes from long dependency chains
185  // first.
186  bool DisableLatencyHeuristic = false;
187 
188  MachineSchedPolicy() = default;
189 };
190 
191 /// MachineSchedStrategy - Interface to the scheduling algorithm used by
192 /// ScheduleDAGMI.
193 ///
194 /// Initialization sequence:
195 /// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots
197  virtual void anchor();
198 
199 public:
200  virtual ~MachineSchedStrategy() = default;
201 
202  /// Optionally override the per-region scheduling policy.
205  unsigned NumRegionInstrs) {}
206 
207  virtual void dumpPolicy() const {}
208 
209  /// Check if pressure tracking is needed before building the DAG and
210  /// initializing this strategy. Called after initPolicy.
211  virtual bool shouldTrackPressure() const { return true; }
212 
213  /// Returns true if lanemasks should be tracked. LaneMask tracking is
214  /// necessary to reorder independent subregister defs for the same vreg.
215  /// This has to be enabled in combination with shouldTrackPressure().
216  virtual bool shouldTrackLaneMasks() const { return false; }
217 
218  // If this method returns true, handling of the scheduling regions
219  // themselves (in case of a scheduling boundary in MBB) will be done
220  // beginning with the topmost region of MBB.
221  virtual bool doMBBSchedRegionsTopDown() const { return false; }
222 
223  /// Initialize the strategy after building the DAG for a new region.
224  virtual void initialize(ScheduleDAGMI *DAG) = 0;
225 
226  /// Tell the strategy that MBB is about to be processed.
227  virtual void enterMBB(MachineBasicBlock *MBB) {};
228 
229  /// Tell the strategy that current MBB is done.
230  virtual void leaveMBB() {};
231 
232  /// Notify this strategy that all roots have been released (including those
233  /// that depend on EntrySU or ExitSU).
234  virtual void registerRoots() {}
235 
236  /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
237  /// schedule the node at the top of the unscheduled region. Otherwise it will
238  /// be scheduled at the bottom.
239  virtual SUnit *pickNode(bool &IsTopNode) = 0;
240 
241  /// Scheduler callback to notify that a new subtree is scheduled.
242  virtual void scheduleTree(unsigned SubtreeID) {}
243 
244  /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
245  /// instruction and updated scheduled/remaining flags in the DAG nodes.
246  virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
247 
248  /// When all predecessor dependencies have been resolved, free this node for
249  /// top-down scheduling.
250  virtual void releaseTopNode(SUnit *SU) = 0;
251 
252  /// When all successor dependencies have been resolved, free this node for
253  /// bottom-up scheduling.
254  virtual void releaseBottomNode(SUnit *SU) = 0;
255 };
256 
257 /// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
258 /// schedules machine instructions according to the given MachineSchedStrategy
259 /// without much extra book-keeping. This is the common functionality between
260 /// PreRA and PostRA MachineScheduler.
262 protected:
265  std::unique_ptr<MachineSchedStrategy> SchedImpl;
266 
267  /// Topo - A topological ordering for SUnits which permits fast IsReachable
268  /// and similar queries.
270 
271  /// Ordered list of DAG postprocessing steps.
272  std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
273 
274  /// The top of the unscheduled zone.
276 
277  /// The bottom of the unscheduled zone.
279 
280  /// Record the next node in a scheduled cluster.
281  const SUnit *NextClusterPred = nullptr;
282  const SUnit *NextClusterSucc = nullptr;
283 
284 #ifndef NDEBUG
285  /// The number of instructions scheduled so far. Used to cut off the
286  /// scheduler at the point determined by misched-cutoff.
287  unsigned NumInstrsScheduled = 0;
288 #endif
289 
290 public:
291  ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
292  bool RemoveKillFlags)
293  : ScheduleDAGInstrs(*C->MF, C->MLI, RemoveKillFlags), AA(C->AA),
294  LIS(C->LIS), SchedImpl(std::move(S)), Topo(SUnits, &ExitSU) {}
295 
296  // Provide a vtable anchor
297  ~ScheduleDAGMI() override;
298 
299  /// If this method returns true, handling of the scheduling regions
300  /// themselves (in case of a scheduling boundary in MBB) will be done
301  /// beginning with the topmost region of MBB.
302  bool doMBBSchedRegionsTopDown() const override {
303  return SchedImpl->doMBBSchedRegionsTopDown();
304  }
305 
306  // Returns LiveIntervals instance for use in DAG mutators and such.
307  LiveIntervals *getLIS() const { return LIS; }
308 
309  /// Return true if this DAG supports VReg liveness and RegPressure.
310  virtual bool hasVRegLiveness() const { return false; }
311 
312  /// Add a postprocessing step to the DAG builder.
313  /// Mutations are applied in the order that they are added after normal DAG
314  /// building and before MachineSchedStrategy initialization.
315  ///
316  /// ScheduleDAGMI takes ownership of the Mutation object.
317  void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
318  if (Mutation)
319  Mutations.push_back(std::move(Mutation));
320  }
321 
322  /// True if an edge can be added from PredSU to SuccSU without creating
323  /// a cycle.
324  bool canAddEdge(SUnit *SuccSU, SUnit *PredSU);
325 
326  /// Add a DAG edge to the given SU with the given predecessor
327  /// dependence data.
328  ///
329  /// \returns true if the edge may be added without creating a cycle OR if an
330  /// equivalent edge already existed (false indicates failure).
331  bool addEdge(SUnit *SuccSU, const SDep &PredDep);
332 
333  MachineBasicBlock::iterator top() const { return CurrentTop; }
334  MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
335 
336  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
337  /// region. This covers all instructions in a block, while schedule() may only
338  /// cover a subset.
339  void enterRegion(MachineBasicBlock *bb,
342  unsigned regioninstrs) override;
343 
344  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
345  /// reorderable instructions.
346  void schedule() override;
347 
348  void startBlock(MachineBasicBlock *bb) override;
349  void finishBlock() override;
350 
351  /// Change the position of an instruction within the basic block and update
352  /// live ranges and region boundary iterators.
353  void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
354 
355  const SUnit *getNextClusterPred() const { return NextClusterPred; }
356 
357  const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
358 
359  void viewGraph(const Twine &Name, const Twine &Title) override;
360  void viewGraph() override;
361 
362 protected:
363  // Top-Level entry points for the schedule() driver...
364 
365  /// Apply each ScheduleDAGMutation step in order. This allows different
366  /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
367  void postprocessDAG();
368 
369  /// Release ExitSU predecessors and setup scheduler queues.
370  void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
371 
372  /// Update scheduler DAG and queues after scheduling an instruction.
373  void updateQueues(SUnit *SU, bool IsTopNode);
374 
375  /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
376  void placeDebugValues();
377 
378  /// dump the scheduled Sequence.
379  void dumpSchedule() const;
380 
381  // Lesser helpers...
382  bool checkSchedLimit();
383 
384  void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
385  SmallVectorImpl<SUnit*> &BotRoots);
386 
387  void releaseSucc(SUnit *SU, SDep *SuccEdge);
388  void releaseSuccessors(SUnit *SU);
389  void releasePred(SUnit *SU, SDep *PredEdge);
390  void releasePredecessors(SUnit *SU);
391 };
392 
393 /// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules
394 /// machine instructions while updating LiveIntervals and tracking regpressure.
396 protected:
398 
399  /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
400  /// will be empty.
401  SchedDFSResult *DFSResult = nullptr;
403 
405 
406  /// Maps vregs to the SUnits of their uses in the current scheduling region.
408 
409  // Map each SU to its summary of pressure changes. This array is updated for
410  // liveness during bottom-up scheduling. Top-down scheduling may proceed but
411  // has no affect on the pressure diffs.
413 
414  /// Register pressure in this region computed by initRegPressure.
415  bool ShouldTrackPressure = false;
416  bool ShouldTrackLaneMasks = false;
419 
420  /// List of pressure sets that exceed the target's pressure limit before
421  /// scheduling, listed in increasing set ID order. Each pressure set is paired
422  /// with its max pressure in the currently scheduled regions.
423  std::vector<PressureChange> RegionCriticalPSets;
424 
425  /// The top of the unscheduled zone.
428 
429  /// The bottom of the unscheduled zone.
432 
433  /// True if disconnected subregister components are already renamed.
434  /// The renaming is only done on demand if lane masks are tracked.
435  bool DisconnectedComponentsRenamed = false;
436 
437 public:
439  std::unique_ptr<MachineSchedStrategy> S)
440  : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false),
441  RegClassInfo(C->RegClassInfo), RPTracker(RegPressure),
442  TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
443 
444  ~ScheduleDAGMILive() override;
445 
446  /// Return true if this DAG supports VReg liveness and RegPressure.
447  bool hasVRegLiveness() const override { return true; }
448 
449  /// Return true if register pressure tracking is enabled.
450  bool isTrackingPressure() const { return ShouldTrackPressure; }
451 
452  /// Get current register pressure for the top scheduled instructions.
453  const IntervalPressure &getTopPressure() const { return TopPressure; }
454  const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
455 
456  /// Get current register pressure for the bottom scheduled instructions.
457  const IntervalPressure &getBotPressure() const { return BotPressure; }
458  const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
459 
460  /// Get register pressure for the entire scheduling region before scheduling.
461  const IntervalPressure &getRegPressure() const { return RegPressure; }
462 
463  const std::vector<PressureChange> &getRegionCriticalPSets() const {
464  return RegionCriticalPSets;
465  }
466 
468  return SUPressureDiffs[SU->NodeNum];
469  }
470  const PressureDiff &getPressureDiff(const SUnit *SU) const {
471  return SUPressureDiffs[SU->NodeNum];
472  }
473 
474  /// Compute a DFSResult after DAG building is complete, and before any
475  /// queue comparisons.
476  void computeDFSResult();
477 
478  /// Return a non-null DFS result if the scheduling strategy initialized it.
479  const SchedDFSResult *getDFSResult() const { return DFSResult; }
480 
481  BitVector &getScheduledTrees() { return ScheduledTrees; }
482 
483  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
484  /// region. This covers all instructions in a block, while schedule() may only
485  /// cover a subset.
486  void enterRegion(MachineBasicBlock *bb,
489  unsigned regioninstrs) override;
490 
491  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
492  /// reorderable instructions.
493  void schedule() override;
494 
495  /// Compute the cyclic critical path through the DAG.
496  unsigned computeCyclicCriticalPath();
497 
498  void dump() const override;
499 
500 protected:
501  // Top-Level entry points for the schedule() driver...
502 
503  /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
504  /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
505  /// region, TopTracker and BottomTracker will be initialized to the top and
506  /// bottom of the DAG region without covereing any unscheduled instruction.
507  void buildDAGWithRegPressure();
508 
509  /// Release ExitSU predecessors and setup scheduler queues. Re-position
510  /// the Top RP tracker in case the region beginning has changed.
511  void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
512 
513  /// Move an instruction and update register pressure.
514  void scheduleMI(SUnit *SU, bool IsTopNode);
515 
516  // Lesser helpers...
517 
518  void initRegPressure();
519 
520  void updatePressureDiffs(ArrayRef<RegisterMaskPair> LiveUses);
521 
522  void updateScheduledPressure(const SUnit *SU,
523  const std::vector<unsigned> &NewMaxPressure);
524 
525  void collectVRegUses(SUnit &SU);
526 };
527 
528 //===----------------------------------------------------------------------===//
529 ///
530 /// Helpers for implementing custom MachineSchedStrategy classes. These take
531 /// care of the book-keeping associated with list scheduling heuristics.
532 ///
533 //===----------------------------------------------------------------------===//
534 
535 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
536 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
537 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
538 ///
539 /// This is a convenience class that may be used by implementations of
540 /// MachineSchedStrategy.
541 class ReadyQueue {
542  unsigned ID;
543  std::string Name;
544  std::vector<SUnit*> Queue;
545 
546 public:
547  ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
548 
549  unsigned getID() const { return ID; }
550 
551  StringRef getName() const { return Name; }
552 
553  // SU is in this queue if it's NodeQueueID is a superset of this ID.
554  bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
555 
556  bool empty() const { return Queue.empty(); }
557 
558  void clear() { Queue.clear(); }
559 
560  unsigned size() const { return Queue.size(); }
561 
562  using iterator = std::vector<SUnit*>::iterator;
563 
564  iterator begin() { return Queue.begin(); }
565 
566  iterator end() { return Queue.end(); }
567 
568  ArrayRef<SUnit*> elements() { return Queue; }
569 
570  iterator find(SUnit *SU) { return llvm::find(Queue, SU); }
571 
572  void push(SUnit *SU) {
573  Queue.push_back(SU);
574  SU->NodeQueueId |= ID;
575  }
576 
577  iterator remove(iterator I) {
578  (*I)->NodeQueueId &= ~ID;
579  *I = Queue.back();
580  unsigned idx = I - Queue.begin();
581  Queue.pop_back();
582  return Queue.begin() + idx;
583  }
584 
585  void dump() const;
586 };
587 
588 /// Summarize the unscheduled region.
590  // Critical path through the DAG in expected latency.
591  unsigned CriticalPath;
592  unsigned CyclicCritPath;
593 
594  // Scaled count of micro-ops left to schedule.
595  unsigned RemIssueCount;
596 
598 
599  // Unscheduled resources
601 
602  SchedRemainder() { reset(); }
603 
604  void reset() {
605  CriticalPath = 0;
606  CyclicCritPath = 0;
607  RemIssueCount = 0;
608  IsAcyclicLatencyLimited = false;
609  RemainingCounts.clear();
610  }
611 
612  void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
613 };
614 
615 /// Each Scheduling boundary is associated with ready queues. It tracks the
616 /// current cycle in the direction of movement, and maintains the state
617 /// of "hazards" and other interlocks at the current cycle.
619 public:
620  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
621  enum {
622  TopQID = 1,
623  BotQID = 2,
624  LogMaxQID = 2
625  };
626 
627  ScheduleDAGMI *DAG = nullptr;
628  const TargetSchedModel *SchedModel = nullptr;
629  SchedRemainder *Rem = nullptr;
630 
633 
634  ScheduleHazardRecognizer *HazardRec = nullptr;
635 
636 private:
637  /// True if the pending Q should be checked/updated before scheduling another
638  /// instruction.
639  bool CheckPending;
640 
641  /// Number of cycles it takes to issue the instructions scheduled in this
642  /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
643  /// See getStalls().
644  unsigned CurrCycle;
645 
646  /// Micro-ops issued in the current cycle
647  unsigned CurrMOps;
648 
649  /// MinReadyCycle - Cycle of the soonest available instruction.
650  unsigned MinReadyCycle;
651 
652  // The expected latency of the critical path in this scheduled zone.
653  unsigned ExpectedLatency;
654 
655  // The latency of dependence chains leading into this zone.
656  // For each node scheduled bottom-up: DLat = max DLat, N.Depth.
657  // For each cycle scheduled: DLat -= 1.
658  unsigned DependentLatency;
659 
660  /// Count the scheduled (issued) micro-ops that can be retired by
661  /// time=CurrCycle assuming the first scheduled instr is retired at time=0.
662  unsigned RetiredMOps;
663 
664  // Count scheduled resources that have been executed. Resources are
665  // considered executed if they become ready in the time that it takes to
666  // saturate any resource including the one in question. Counts are scaled
667  // for direct comparison with other resources. Counts can be compared with
668  // MOps * getMicroOpFactor and Latency * getLatencyFactor.
669  SmallVector<unsigned, 16> ExecutedResCounts;
670 
671  /// Cache the max count for a single resource.
672  unsigned MaxExecutedResCount;
673 
674  // Cache the critical resources ID in this scheduled zone.
675  unsigned ZoneCritResIdx;
676 
677  // Is the scheduled region resource limited vs. latency limited.
678  bool IsResourceLimited;
679 
680  // Record the highest cycle at which each resource has been reserved by a
681  // scheduled instruction.
682  SmallVector<unsigned, 16> ReservedCycles;
683 
684 #ifndef NDEBUG
685  // Remember the greatest possible stall as an upper bound on the number of
686  // times we should retry the pending queue because of a hazard.
687  unsigned MaxObservedStall;
688 #endif
689 
690 public:
691  /// Pending queues extend the ready queues with the same ID and the
692  /// PendingFlag set.
693  SchedBoundary(unsigned ID, const Twine &Name):
694  Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
695  reset();
696  }
697 
698  ~SchedBoundary();
699 
700  void reset();
701 
702  void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
703  SchedRemainder *rem);
704 
705  bool isTop() const {
706  return Available.getID() == TopQID;
707  }
708 
709  /// Number of cycles to issue the instructions scheduled in this zone.
710  unsigned getCurrCycle() const { return CurrCycle; }
711 
712  /// Micro-ops issued in the current cycle
713  unsigned getCurrMOps() const { return CurrMOps; }
714 
715  // The latency of dependence chains leading into this zone.
716  unsigned getDependentLatency() const { return DependentLatency; }
717 
718  /// Get the number of latency cycles "covered" by the scheduled
719  /// instructions. This is the larger of the critical path within the zone
720  /// and the number of cycles required to issue the instructions.
721  unsigned getScheduledLatency() const {
722  return std::max(ExpectedLatency, CurrCycle);
723  }
724 
725  unsigned getUnscheduledLatency(SUnit *SU) const {
726  return isTop() ? SU->getHeight() : SU->getDepth();
727  }
728 
729  unsigned getResourceCount(unsigned ResIdx) const {
730  return ExecutedResCounts[ResIdx];
731  }
732 
733  /// Get the scaled count of scheduled micro-ops and resources, including
734  /// executed resources.
735  unsigned getCriticalCount() const {
736  if (!ZoneCritResIdx)
737  return RetiredMOps * SchedModel->getMicroOpFactor();
738  return getResourceCount(ZoneCritResIdx);
739  }
740 
741  /// Get a scaled count for the minimum execution time of the scheduled
742  /// micro-ops that are ready to execute by getExecutedCount. Notice the
743  /// feedback loop.
744  unsigned getExecutedCount() const {
745  return std::max(CurrCycle * SchedModel->getLatencyFactor(),
746  MaxExecutedResCount);
747  }
748 
749  unsigned getZoneCritResIdx() const { return ZoneCritResIdx; }
750 
751  // Is the scheduled region resource limited vs. latency limited.
752  bool isResourceLimited() const { return IsResourceLimited; }
753 
754  /// Get the difference between the given SUnit's ready time and the current
755  /// cycle.
756  unsigned getLatencyStallCycles(SUnit *SU);
757 
758  unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles);
759 
760  bool checkHazard(SUnit *SU);
761 
762  unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
763 
764  unsigned getOtherResourceCount(unsigned &OtherCritIdx);
765 
766  void releaseNode(SUnit *SU, unsigned ReadyCycle);
767 
768  void bumpCycle(unsigned NextCycle);
769 
770  void incExecutedResources(unsigned PIdx, unsigned Count);
771 
772  unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle);
773 
774  void bumpNode(SUnit *SU);
775 
776  void releasePending();
777 
778  void removeReady(SUnit *SU);
779 
780  /// Call this before applying any other heuristics to the Available queue.
781  /// Updates the Available/Pending Q's if necessary and returns the single
782  /// available instruction, or NULL if there are multiple candidates.
783  SUnit *pickOnlyChoice();
784 
785  void dumpScheduledState() const;
786 };
787 
788 /// Base class for GenericScheduler. This class maintains information about
789 /// scheduling candidates based on TargetSchedModel making it easy to implement
790 /// heuristics for either preRA or postRA scheduling.
792 public:
793  /// Represent the type of SchedCandidate found within a single queue.
794  /// pickNodeBidirectional depends on these listed by decreasing priority.
795  enum CandReason : uint8_t {
796  NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster, Weak,
797  RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
798  TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
799 
800 #ifndef NDEBUG
801  static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
802 #endif
803 
804  /// Policy for scheduling the next instruction in the candidate's zone.
805  struct CandPolicy {
806  bool ReduceLatency = false;
807  unsigned ReduceResIdx = 0;
808  unsigned DemandResIdx = 0;
809 
810  CandPolicy() = default;
811 
812  bool operator==(const CandPolicy &RHS) const {
813  return ReduceLatency == RHS.ReduceLatency &&
814  ReduceResIdx == RHS.ReduceResIdx &&
815  DemandResIdx == RHS.DemandResIdx;
816  }
817  bool operator!=(const CandPolicy &RHS) const {
818  return !(*this == RHS);
819  }
820  };
821 
822  /// Status of an instruction's critical resource consumption.
824  // Count critical resources in the scheduled region required by SU.
825  unsigned CritResources = 0;
826 
827  // Count critical resources from another region consumed by SU.
828  unsigned DemandedResources = 0;
829 
830  SchedResourceDelta() = default;
831 
832  bool operator==(const SchedResourceDelta &RHS) const {
833  return CritResources == RHS.CritResources
834  && DemandedResources == RHS.DemandedResources;
835  }
836  bool operator!=(const SchedResourceDelta &RHS) const {
837  return !operator==(RHS);
838  }
839  };
840 
841  /// Store the state used by GenericScheduler heuristics, required for the
842  /// lifetime of one invocation of pickNode().
843  struct SchedCandidate {
845 
846  // The best SUnit candidate.
848 
849  // The reason for this candidate.
851 
852  // Whether this candidate should be scheduled at top/bottom.
853  bool AtTop;
854 
855  // Register pressure values for the best candidate.
857 
858  // Critical resource consumption of the best candidate.
860 
861  SchedCandidate() { reset(CandPolicy()); }
862  SchedCandidate(const CandPolicy &Policy) { reset(Policy); }
863 
864  void reset(const CandPolicy &NewPolicy) {
865  Policy = NewPolicy;
866  SU = nullptr;
867  Reason = NoCand;
868  AtTop = false;
869  RPDelta = RegPressureDelta();
870  ResDelta = SchedResourceDelta();
871  }
872 
873  bool isValid() const { return SU; }
874 
875  // Copy the status of another candidate without changing policy.
876  void setBest(SchedCandidate &Best) {
877  assert(Best.Reason != NoCand && "uninitialized Sched candidate");
878  SU = Best.SU;
879  Reason = Best.Reason;
880  AtTop = Best.AtTop;
881  RPDelta = Best.RPDelta;
882  ResDelta = Best.ResDelta;
883  }
884 
885  void initResourceDelta(const ScheduleDAGMI *DAG,
886  const TargetSchedModel *SchedModel);
887  };
888 
889 protected:
891  const TargetSchedModel *SchedModel = nullptr;
892  const TargetRegisterInfo *TRI = nullptr;
893 
895 
897 
898  void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
899  SchedBoundary *OtherZone);
900 
901 #ifndef NDEBUG
902  void traceCandidate(const SchedCandidate &Cand);
903 #endif
904 
905 private:
906  bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
907  bool ComputeRemLatency, unsigned &RemLatency) const;
908 };
909 
910 // Utility functions used by heuristics in tryCandidate().
911 bool tryLess(int TryVal, int CandVal,
915 bool tryGreater(int TryVal, int CandVal,
921  SchedBoundary &Zone);
922 bool tryPressure(const PressureChange &TryP,
923  const PressureChange &CandP,
927  const TargetRegisterInfo *TRI,
928  const MachineFunction &MF);
929 unsigned getWeakLeft(const SUnit *SU, bool isTop);
930 int biasPhysReg(const SUnit *SU, bool isTop);
931 
932 /// GenericScheduler shrinks the unscheduled zone using heuristics to balance
933 /// the schedule.
935 public:
937  GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
938  Bot(SchedBoundary::BotQID, "BotQ") {}
939 
940  void initPolicy(MachineBasicBlock::iterator Begin,
942  unsigned NumRegionInstrs) override;
943 
944  void dumpPolicy() const override;
945 
946  bool shouldTrackPressure() const override {
947  return RegionPolicy.ShouldTrackPressure;
948  }
949 
950  bool shouldTrackLaneMasks() const override {
951  return RegionPolicy.ShouldTrackLaneMasks;
952  }
953 
954  void initialize(ScheduleDAGMI *dag) override;
955 
956  SUnit *pickNode(bool &IsTopNode) override;
957 
958  void schedNode(SUnit *SU, bool IsTopNode) override;
959 
960  void releaseTopNode(SUnit *SU) override {
961  if (SU->isScheduled)
962  return;
963 
964  Top.releaseNode(SU, SU->TopReadyCycle);
965  TopCand.SU = nullptr;
966  }
967 
968  void releaseBottomNode(SUnit *SU) override {
969  if (SU->isScheduled)
970  return;
971 
972  Bot.releaseNode(SU, SU->BotReadyCycle);
973  BotCand.SU = nullptr;
974  }
975 
976  void registerRoots() override;
977 
978 protected:
979  ScheduleDAGMILive *DAG = nullptr;
980 
982 
983  // State of the top and bottom scheduled instruction boundaries.
986 
987  /// Candidate last picked from Top boundary.
989  /// Candidate last picked from Bot boundary.
991 
992  void checkAcyclicLatency();
993 
994  void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
995  const RegPressureTracker &RPTracker,
996  RegPressureTracker &TempTracker);
997 
998  virtual void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
999  SchedBoundary *Zone) const;
1000 
1001  SUnit *pickNodeBidirectional(bool &IsTopNode);
1002 
1003  void pickNodeFromQueue(SchedBoundary &Zone,
1004  const CandPolicy &ZonePolicy,
1005  const RegPressureTracker &RPTracker,
1006  SchedCandidate &Candidate);
1007 
1008  void reschedulePhysReg(SUnit *SU, bool isTop);
1009 };
1010 
1011 /// PostGenericScheduler - Interface to the scheduling algorithm used by
1012 /// ScheduleDAGMI.
1013 ///
1014 /// Callbacks from ScheduleDAGMI:
1015 /// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
1017  ScheduleDAGMI *DAG;
1018  SchedBoundary Top;
1019  SmallVector<SUnit*, 8> BotRoots;
1020 
1021 public:
1023  GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
1024 
1025  ~PostGenericScheduler() override = default;
1026 
1029  unsigned NumRegionInstrs) override {
1030  /* no configurable policy */
1031  }
1032 
1033  /// PostRA scheduling does not track pressure.
1034  bool shouldTrackPressure() const override { return false; }
1035 
1036  void initialize(ScheduleDAGMI *Dag) override;
1037 
1038  void registerRoots() override;
1039 
1040  SUnit *pickNode(bool &IsTopNode) override;
1041 
1042  void scheduleTree(unsigned SubtreeID) override {
1043  llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1044  }
1045 
1046  void schedNode(SUnit *SU, bool IsTopNode) override;
1047 
1048  void releaseTopNode(SUnit *SU) override {
1049  if (SU->isScheduled)
1050  return;
1051  Top.releaseNode(SU, SU->TopReadyCycle);
1052  }
1053 
1054  // Only called for roots.
1055  void releaseBottomNode(SUnit *SU) override {
1056  BotRoots.push_back(SU);
1057  }
1058 
1059 protected:
1060  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1061 
1062  void pickNodeFromQueue(SchedCandidate &Cand);
1063 };
1064 
1065 /// Create the standard converging machine scheduler. This will be used as the
1066 /// default scheduler if the target does not set a default.
1067 /// Adds default DAG mutations.
1069 
1070 /// Create a generic scheduler with no vreg liveness or DAG mutation passes.
1072 
1073 std::unique_ptr<ScheduleDAGMutation>
1075  const TargetRegisterInfo *TRI);
1076 
1077 std::unique_ptr<ScheduleDAGMutation>
1079  const TargetRegisterInfo *TRI);
1080 
1081 std::unique_ptr<ScheduleDAGMutation>
1083  const TargetRegisterInfo *TRI);
1084 
1085 } // end namespace llvm
1086 
1087 #endif // LLVM_CODEGEN_MACHINESCHEDULER_H
unsigned getCriticalCount() const
Get the scaled count of scheduled micro-ops and resources, including executed resources.
VReg2SUnitMultiMap VRegUses
Maps vregs to the SUnits of their uses in the current scheduling region.
uint64_t CallInst * C
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Optionally override the per-region scheduling policy.
int biasPhysReg(const SUnit *SU, bool isTop)
Minimize physical register live ranges.
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:258
unsigned getZoneCritResIdx() const
Base class for GenericScheduler.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
static MachinePassRegistry< ScheduleDAGCtor > Registry
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:249
Each Scheduling boundary is associated with ready queues.
PostGenericScheduler - Interface to the scheduling algorithm used by ScheduleDAGMI.
GenericSchedulerBase(const MachineSchedContext *C)
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const MachineSchedContext * Context
void Remove(MachinePassRegistryNode< PassCtorTy > *Node)
Remove - Removes a function pass from the registration list.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries...
ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S, bool RemoveKillFlags)
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
const MachineLoopInfo * MLI
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling...
unsigned getCurrCycle() const
Number of cycles to issue the instructions scheduled in this zone.
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...
Definition: ScheduleDAG.h:398
bool isInQueue(SUnit *SU) const
ScheduleDAGMI * createGenericSchedPostRA(MachineSchedContext *C)
Create a generic scheduler with no vreg liveness or DAG mutation passes.
const IntervalPressure & getBotPressure() const
Get current register pressure for the bottom scheduled instructions.
MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
unsigned getUnscheduledLatency(SUnit *SU) const
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
unsigned getDependentLatency() const
unsigned const TargetRegisterInfo * TRI
Summarize the unscheduled region.
void reset(const CandPolicy &NewPolicy)
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
MachineSchedRegistry provides a selection of available machine instruction schedulers.
RegisterClassInfo * RegClassInfo
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
std::unique_ptr< MachineSchedStrategy > SchedImpl
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Definition: ScheduleDAG.h:300
bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
virtual bool hasVRegLiveness() const
Return true if this DAG supports VReg liveness and RegPressure.
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
unsigned getID() const
ArrayRef< SUnit * > elements()
const RegPressureTracker & getBotRPTracker() const
Definition: BitVector.h:937
BitVector & getScheduledTrees()
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
const TargetPassConfig * PassConfig
virtual void dumpPolicy() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
StringRef getName() const
void scheduleTree(unsigned SubtreeID) override
Scheduler callback to notify that a new subtree is scheduled.
PressureDiff & getPressureDiff(const SUnit *SU)
std::vector< std::unique_ptr< ScheduleDAGMutation > > Mutations
Ordered list of DAG postprocessing steps.
void setListener(MachinePassRegistryListener< PassCtorTy > *L)
Target-Independent Code Generator Pass Configuration Options.
bool shouldTrackLaneMasks() const override
Returns true if lanemasks should be tracked.
static MachineSchedRegistry * getList()
static const char * getReasonStr(SIScheduleCandReason Reason)
Compute the values of each DAG node for various metrics during DFS.
Definition: ScheduleDFS.h:65
unsigned TopReadyCycle
Cycle relative to start when node is ready.
Definition: ScheduleDAG.h:299
PowerPC VSX FMA Mutation
MachineBasicBlock::iterator LiveRegionEnd
iterator find(SUnit *SU)
RegPressureTracker BotRPTracker
MachineBasicBlock::iterator top() const
MachineSchedPolicy RegionPolicy
std::vector< PressureChange > RegionCriticalPSets
List of pressure sets that exceed the target&#39;s pressure limit before scheduling, listed in increasing...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
virtual void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs)
Optionally override the per-region scheduling policy.
bool doMBBSchedRegionsTopDown() const override
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
ScheduleDAGMILive * createGenericSchedLive(MachineSchedContext *C)
Create the standard converging machine scheduler.
std::vector< SUnit * >::iterator iterator
unsigned getCurrMOps() const
Micro-ops issued in the current cycle.
const SUnit * getNextClusterSucc() const
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
TargetInstrInfo - Interface to description of machine instruction set.
virtual void registerRoots()
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
Scheduling dependency.
Definition: ScheduleDAG.h:49
RegisterClassInfo * RegClassInfo
static void setListener(MachinePassRegistryListener< FunctionPassCtor > *L)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:422
CandReason
Represent the type of SchedCandidate found within a single queue.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Helpers for implementing custom MachineSchedStrategy classes.
Array of PressureDiffs.
RegisterPressure computed within a region of instructions delimited by TopIdx and BottomIdx...
HazardRecognizer - This determines whether or not an instruction can be issued this cycle...
bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
virtual void enterMBB(MachineBasicBlock *MBB)
Tell the strategy that MBB is about to be processed.
unsigned size() const
unsigned getLatencyFactor() const
Multiply cycle count by this factor to normalize it relative to other resources.
void Add(MachinePassRegistryNode< PassCtorTy > *Node)
Add - Adds a function pass to the registration list.
bool operator!=(const CandPolicy &RHS) const
Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...
Track the current register pressure at some position in the instruction stream, and remember the high...
Policy for scheduling the next instruction in the candidate&#39;s zone.
unsigned getScheduledLatency() const
Get the number of latency cycles "covered" by the scheduled instructions.
List of PressureChanges in order of increasing, unique PSetID.
MachinePassRegistryNode< PassCtorTy > * getList()
ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor
std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
unsigned getWeakLeft(const SUnit *SU, bool isTop)
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
SchedBoundary(unsigned ID, const Twine &Name)
Pending queues extend the ready queues with the same ID and the PendingFlag set.
std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
bool operator==(const SchedResourceDelta &RHS) const
GenericScheduler shrinks the unscheduled zone using heuristics to balance the schedule.
bool shouldTrackPressure() const override
Check if pressure tracking is needed before building the DAG and initializing this strategy...
void releaseNode(SUnit *SU, unsigned ReadyCycle)
unsigned getMicroOpFactor() const
Multiply number of micro-ops by this factor to normalize it relative to other resources.
bool hasVRegLiveness() const override
Return true if this DAG supports VReg liveness and RegPressure.
const RegPressureTracker & getTopRPTracker() const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isResourceLimited() const
std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
unsigned getResourceCount(unsigned ResIdx) const
PostGenericScheduler(const MachineSchedContext *C)
bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
Return true if this heuristic determines order.
ReadyQueue(unsigned id, const Twine &name)
unsigned getExecutedCount() const
Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execut...
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
virtual bool shouldTrackPressure() const
Check if pressure tracking is needed before building the DAG and initializing this strategy...
const IntervalPressure & getTopPressure() const
Get current register pressure for the top scheduled instructions.
ScheduleDAGMILive(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
const PressureDiff & getPressureDiff(const SUnit *SU) const
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
unsigned NodeQueueId
Queue id of node.
Definition: ScheduleDAG.h:265
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:406
A ScheduleDAG for scheduling lists of MachineInstr.
Define a generic scheduling policy for targets that don&#39;t provide their own MachineSchedStrategy.
Representation of each machine instruction.
Definition: MachineInstr.h:63
LiveIntervals * LIS
const MachineDominatorTree * MDT
Status of an instruction&#39;s critical resource consumption.
GenericScheduler(const MachineSchedContext *C)
LiveIntervals * getLIS() const
bool shouldTrackPressure() const override
PostRA scheduling does not track pressure.
SchedCandidate BotCand
Candidate last picked from Bot boundary.
cl::opt< bool > ForceBottomUp
virtual void leaveMBB()
Tell the strategy that current MBB is done.
MachineBasicBlock::iterator bottom() const
bool operator!=(const SchedResourceDelta &RHS) const
MachinePassRegistryNode * getNext() const
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
MachinePassRegistryNode - Machine pass node stored in registration list.
Capture a change in pressure for a single pressure set.
SmallVector< unsigned, 16 > RemainingCounts
const SUnit * getNextClusterPred() const
IntervalPressure TopPressure
The top of the unscheduled zone.
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling...
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
const std::vector< PressureChange > & getRegionCriticalPSets() const
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
Store the effects of a change in pressure on things that MI scheduler cares about.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineSchedRegistry * getNext() const
bool operator==(const CandPolicy &RHS) const
bool isTrackingPressure() const
Return true if register pressure tracking is enabled.
static const char * name
virtual bool doMBBSchedRegionsTopDown() const
SchedCandidate TopCand
Candidate last picked from Top boundary.
IntervalPressure RegPressure
void push(SUnit *SU)
IRTranslator LLVM IR MI
virtual bool shouldTrackLaneMasks() const
Returns true if lanemasks should be tracked.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:48
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1966
bool empty() const
IntervalPressure BotPressure
The bottom of the unscheduled zone.
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:689
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
AliasAnalysis * AA
RegPressureTracker TopRPTracker
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
RegPressureTracker RPTracker
ScheduleDAGCtor FunctionPassCtor
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Add a postprocessing step to the DAG builder.
cl::opt< bool > ForceTopDown
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.