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