LLVM  6.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  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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  /// \brief 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 
470  /// Compute a DFSResult after DAG building is complete, and before any
471  /// queue comparisons.
472  void computeDFSResult();
473 
474  /// Return a non-null DFS result if the scheduling strategy initialized it.
475  const SchedDFSResult *getDFSResult() const { return DFSResult; }
476 
477  BitVector &getScheduledTrees() { return ScheduledTrees; }
478 
479  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
480  /// region. This covers all instructions in a block, while schedule() may only
481  /// cover a subset.
482  void enterRegion(MachineBasicBlock *bb,
485  unsigned regioninstrs) override;
486 
487  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
488  /// reorderable instructions.
489  void schedule() override;
490 
491  /// Compute the cyclic critical path through the DAG.
492  unsigned computeCyclicCriticalPath();
493 
494 protected:
495  // Top-Level entry points for the schedule() driver...
496 
497  /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
498  /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
499  /// region, TopTracker and BottomTracker will be initialized to the top and
500  /// bottom of the DAG region without covereing any unscheduled instruction.
501  void buildDAGWithRegPressure();
502 
503  /// Release ExitSU predecessors and setup scheduler queues. Re-position
504  /// the Top RP tracker in case the region beginning has changed.
505  void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
506 
507  /// Move an instruction and update register pressure.
508  void scheduleMI(SUnit *SU, bool IsTopNode);
509 
510  // Lesser helpers...
511 
512  void initRegPressure();
513 
514  void updatePressureDiffs(ArrayRef<RegisterMaskPair> LiveUses);
515 
516  void updateScheduledPressure(const SUnit *SU,
517  const std::vector<unsigned> &NewMaxPressure);
518 
519  void collectVRegUses(SUnit &SU);
520 };
521 
522 //===----------------------------------------------------------------------===//
523 ///
524 /// Helpers for implementing custom MachineSchedStrategy classes. These take
525 /// care of the book-keeping associated with list scheduling heuristics.
526 ///
527 //===----------------------------------------------------------------------===//
528 
529 /// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
530 /// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
531 /// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
532 ///
533 /// This is a convenience class that may be used by implementations of
534 /// MachineSchedStrategy.
535 class ReadyQueue {
536  unsigned ID;
537  std::string Name;
538  std::vector<SUnit*> Queue;
539 
540 public:
541  ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
542 
543  unsigned getID() const { return ID; }
544 
545  StringRef getName() const { return Name; }
546 
547  // SU is in this queue if it's NodeQueueID is a superset of this ID.
548  bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
549 
550  bool empty() const { return Queue.empty(); }
551 
552  void clear() { Queue.clear(); }
553 
554  unsigned size() const { return Queue.size(); }
555 
556  using iterator = std::vector<SUnit*>::iterator;
557 
558  iterator begin() { return Queue.begin(); }
559 
560  iterator end() { return Queue.end(); }
561 
562  ArrayRef<SUnit*> elements() { return Queue; }
563 
564  iterator find(SUnit *SU) { return llvm::find(Queue, SU); }
565 
566  void push(SUnit *SU) {
567  Queue.push_back(SU);
568  SU->NodeQueueId |= ID;
569  }
570 
571  iterator remove(iterator I) {
572  (*I)->NodeQueueId &= ~ID;
573  *I = Queue.back();
574  unsigned idx = I - Queue.begin();
575  Queue.pop_back();
576  return Queue.begin() + idx;
577  }
578 
579  void dump() const;
580 };
581 
582 /// Summarize the unscheduled region.
584  // Critical path through the DAG in expected latency.
585  unsigned CriticalPath;
586  unsigned CyclicCritPath;
587 
588  // Scaled count of micro-ops left to schedule.
589  unsigned RemIssueCount;
590 
592 
593  // Unscheduled resources
595 
596  SchedRemainder() { reset(); }
597 
598  void reset() {
599  CriticalPath = 0;
600  CyclicCritPath = 0;
601  RemIssueCount = 0;
602  IsAcyclicLatencyLimited = false;
603  RemainingCounts.clear();
604  }
605 
606  void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
607 };
608 
609 /// Each Scheduling boundary is associated with ready queues. It tracks the
610 /// current cycle in the direction of movement, and maintains the state
611 /// of "hazards" and other interlocks at the current cycle.
613 public:
614  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
615  enum {
616  TopQID = 1,
617  BotQID = 2,
618  LogMaxQID = 2
619  };
620 
621  ScheduleDAGMI *DAG = nullptr;
622  const TargetSchedModel *SchedModel = nullptr;
623  SchedRemainder *Rem = nullptr;
624 
627 
628  ScheduleHazardRecognizer *HazardRec = nullptr;
629 
630 private:
631  /// True if the pending Q should be checked/updated before scheduling another
632  /// instruction.
633  bool CheckPending;
634 
635  /// Number of cycles it takes to issue the instructions scheduled in this
636  /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
637  /// See getStalls().
638  unsigned CurrCycle;
639 
640  /// Micro-ops issued in the current cycle
641  unsigned CurrMOps;
642 
643  /// MinReadyCycle - Cycle of the soonest available instruction.
644  unsigned MinReadyCycle;
645 
646  // The expected latency of the critical path in this scheduled zone.
647  unsigned ExpectedLatency;
648 
649  // The latency of dependence chains leading into this zone.
650  // For each node scheduled bottom-up: DLat = max DLat, N.Depth.
651  // For each cycle scheduled: DLat -= 1.
652  unsigned DependentLatency;
653 
654  /// Count the scheduled (issued) micro-ops that can be retired by
655  /// time=CurrCycle assuming the first scheduled instr is retired at time=0.
656  unsigned RetiredMOps;
657 
658  // Count scheduled resources that have been executed. Resources are
659  // considered executed if they become ready in the time that it takes to
660  // saturate any resource including the one in question. Counts are scaled
661  // for direct comparison with other resources. Counts can be compared with
662  // MOps * getMicroOpFactor and Latency * getLatencyFactor.
663  SmallVector<unsigned, 16> ExecutedResCounts;
664 
665  /// Cache the max count for a single resource.
666  unsigned MaxExecutedResCount;
667 
668  // Cache the critical resources ID in this scheduled zone.
669  unsigned ZoneCritResIdx;
670 
671  // Is the scheduled region resource limited vs. latency limited.
672  bool IsResourceLimited;
673 
674  // Record the highest cycle at which each resource has been reserved by a
675  // scheduled instruction.
676  SmallVector<unsigned, 16> ReservedCycles;
677 
678 #ifndef NDEBUG
679  // Remember the greatest possible stall as an upper bound on the number of
680  // times we should retry the pending queue because of a hazard.
681  unsigned MaxObservedStall;
682 #endif
683 
684 public:
685  /// Pending queues extend the ready queues with the same ID and the
686  /// PendingFlag set.
687  SchedBoundary(unsigned ID, const Twine &Name):
688  Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
689  reset();
690  }
691 
692  ~SchedBoundary();
693 
694  void reset();
695 
696  void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
697  SchedRemainder *rem);
698 
699  bool isTop() const {
700  return Available.getID() == TopQID;
701  }
702 
703  /// Number of cycles to issue the instructions scheduled in this zone.
704  unsigned getCurrCycle() const { return CurrCycle; }
705 
706  /// Micro-ops issued in the current cycle
707  unsigned getCurrMOps() const { return CurrMOps; }
708 
709  // The latency of dependence chains leading into this zone.
710  unsigned getDependentLatency() const { return DependentLatency; }
711 
712  /// Get the number of latency cycles "covered" by the scheduled
713  /// instructions. This is the larger of the critical path within the zone
714  /// and the number of cycles required to issue the instructions.
715  unsigned getScheduledLatency() const {
716  return std::max(ExpectedLatency, CurrCycle);
717  }
718 
719  unsigned getUnscheduledLatency(SUnit *SU) const {
720  return isTop() ? SU->getHeight() : SU->getDepth();
721  }
722 
723  unsigned getResourceCount(unsigned ResIdx) const {
724  return ExecutedResCounts[ResIdx];
725  }
726 
727  /// Get the scaled count of scheduled micro-ops and resources, including
728  /// executed resources.
729  unsigned getCriticalCount() const {
730  if (!ZoneCritResIdx)
731  return RetiredMOps * SchedModel->getMicroOpFactor();
732  return getResourceCount(ZoneCritResIdx);
733  }
734 
735  /// Get a scaled count for the minimum execution time of the scheduled
736  /// micro-ops that are ready to execute by getExecutedCount. Notice the
737  /// feedback loop.
738  unsigned getExecutedCount() const {
739  return std::max(CurrCycle * SchedModel->getLatencyFactor(),
740  MaxExecutedResCount);
741  }
742 
743  unsigned getZoneCritResIdx() const { return ZoneCritResIdx; }
744 
745  // Is the scheduled region resource limited vs. latency limited.
746  bool isResourceLimited() const { return IsResourceLimited; }
747 
748  /// Get the difference between the given SUnit's ready time and the current
749  /// cycle.
750  unsigned getLatencyStallCycles(SUnit *SU);
751 
752  unsigned getNextResourceCycle(unsigned PIdx, unsigned Cycles);
753 
754  bool checkHazard(SUnit *SU);
755 
756  unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs);
757 
758  unsigned getOtherResourceCount(unsigned &OtherCritIdx);
759 
760  void releaseNode(SUnit *SU, unsigned ReadyCycle);
761 
762  void bumpCycle(unsigned NextCycle);
763 
764  void incExecutedResources(unsigned PIdx, unsigned Count);
765 
766  unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle);
767 
768  void bumpNode(SUnit *SU);
769 
770  void releasePending();
771 
772  void removeReady(SUnit *SU);
773 
774  /// Call this before applying any other heuristics to the Available queue.
775  /// Updates the Available/Pending Q's if necessary and returns the single
776  /// available instruction, or NULL if there are multiple candidates.
777  SUnit *pickOnlyChoice();
778 
779  void dumpScheduledState() const;
780 };
781 
782 /// Base class for GenericScheduler. This class maintains information about
783 /// scheduling candidates based on TargetSchedModel making it easy to implement
784 /// heuristics for either preRA or postRA scheduling.
786 public:
787  /// Represent the type of SchedCandidate found within a single queue.
788  /// pickNodeBidirectional depends on these listed by decreasing priority.
789  enum CandReason : uint8_t {
790  NoCand, Only1, PhysRegCopy, RegExcess, RegCritical, Stall, Cluster, Weak,
791  RegMax, ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
792  TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder};
793 
794 #ifndef NDEBUG
795  static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
796 #endif
797 
798  /// Policy for scheduling the next instruction in the candidate's zone.
799  struct CandPolicy {
800  bool ReduceLatency = false;
801  unsigned ReduceResIdx = 0;
802  unsigned DemandResIdx = 0;
803 
804  CandPolicy() = default;
805 
806  bool operator==(const CandPolicy &RHS) const {
807  return ReduceLatency == RHS.ReduceLatency &&
808  ReduceResIdx == RHS.ReduceResIdx &&
809  DemandResIdx == RHS.DemandResIdx;
810  }
811  bool operator!=(const CandPolicy &RHS) const {
812  return !(*this == RHS);
813  }
814  };
815 
816  /// Status of an instruction's critical resource consumption.
818  // Count critical resources in the scheduled region required by SU.
819  unsigned CritResources = 0;
820 
821  // Count critical resources from another region consumed by SU.
822  unsigned DemandedResources = 0;
823 
824  SchedResourceDelta() = default;
825 
826  bool operator==(const SchedResourceDelta &RHS) const {
827  return CritResources == RHS.CritResources
828  && DemandedResources == RHS.DemandedResources;
829  }
830  bool operator!=(const SchedResourceDelta &RHS) const {
831  return !operator==(RHS);
832  }
833  };
834 
835  /// Store the state used by GenericScheduler heuristics, required for the
836  /// lifetime of one invocation of pickNode().
837  struct SchedCandidate {
839 
840  // The best SUnit candidate.
842 
843  // The reason for this candidate.
845 
846  // Whether this candidate should be scheduled at top/bottom.
847  bool AtTop;
848 
849  // Register pressure values for the best candidate.
851 
852  // Critical resource consumption of the best candidate.
854 
855  SchedCandidate() { reset(CandPolicy()); }
856  SchedCandidate(const CandPolicy &Policy) { reset(Policy); }
857 
858  void reset(const CandPolicy &NewPolicy) {
859  Policy = NewPolicy;
860  SU = nullptr;
861  Reason = NoCand;
862  AtTop = false;
863  RPDelta = RegPressureDelta();
864  ResDelta = SchedResourceDelta();
865  }
866 
867  bool isValid() const { return SU; }
868 
869  // Copy the status of another candidate without changing policy.
870  void setBest(SchedCandidate &Best) {
871  assert(Best.Reason != NoCand && "uninitialized Sched candidate");
872  SU = Best.SU;
873  Reason = Best.Reason;
874  AtTop = Best.AtTop;
875  RPDelta = Best.RPDelta;
876  ResDelta = Best.ResDelta;
877  }
878 
879  void initResourceDelta(const ScheduleDAGMI *DAG,
880  const TargetSchedModel *SchedModel);
881  };
882 
883 protected:
885  const TargetSchedModel *SchedModel = nullptr;
886  const TargetRegisterInfo *TRI = nullptr;
887 
889 
891 
892  void setPolicy(CandPolicy &Policy, bool IsPostRA, SchedBoundary &CurrZone,
893  SchedBoundary *OtherZone);
894 
895 #ifndef NDEBUG
896  void traceCandidate(const SchedCandidate &Cand);
897 #endif
898 };
899 
900 /// GenericScheduler shrinks the unscheduled zone using heuristics to balance
901 /// the schedule.
903 public:
905  GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
906  Bot(SchedBoundary::BotQID, "BotQ") {}
907 
908  void initPolicy(MachineBasicBlock::iterator Begin,
910  unsigned NumRegionInstrs) override;
911 
912  void dumpPolicy() const override;
913 
914  bool shouldTrackPressure() const override {
915  return RegionPolicy.ShouldTrackPressure;
916  }
917 
918  bool shouldTrackLaneMasks() const override {
919  return RegionPolicy.ShouldTrackLaneMasks;
920  }
921 
922  void initialize(ScheduleDAGMI *dag) override;
923 
924  SUnit *pickNode(bool &IsTopNode) override;
925 
926  void schedNode(SUnit *SU, bool IsTopNode) override;
927 
928  void releaseTopNode(SUnit *SU) override {
929  if (SU->isScheduled)
930  return;
931 
932  Top.releaseNode(SU, SU->TopReadyCycle);
933  TopCand.SU = nullptr;
934  }
935 
936  void releaseBottomNode(SUnit *SU) override {
937  if (SU->isScheduled)
938  return;
939 
940  Bot.releaseNode(SU, SU->BotReadyCycle);
941  BotCand.SU = nullptr;
942  }
943 
944  void registerRoots() override;
945 
946 protected:
947  ScheduleDAGMILive *DAG = nullptr;
948 
950 
951  // State of the top and bottom scheduled instruction boundaries.
954 
955  /// Candidate last picked from Top boundary.
957  /// Candidate last picked from Bot boundary.
959 
960  void checkAcyclicLatency();
961 
962  void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
963  const RegPressureTracker &RPTracker,
964  RegPressureTracker &TempTracker);
965 
966  void tryCandidate(SchedCandidate &Cand,
967  SchedCandidate &TryCand,
968  SchedBoundary *Zone);
969 
970  SUnit *pickNodeBidirectional(bool &IsTopNode);
971 
972  void pickNodeFromQueue(SchedBoundary &Zone,
973  const CandPolicy &ZonePolicy,
974  const RegPressureTracker &RPTracker,
975  SchedCandidate &Candidate);
976 
977  void reschedulePhysRegCopies(SUnit *SU, bool isTop);
978 };
979 
980 /// PostGenericScheduler - Interface to the scheduling algorithm used by
981 /// ScheduleDAGMI.
982 ///
983 /// Callbacks from ScheduleDAGMI:
984 /// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
986  ScheduleDAGMI *DAG;
987  SchedBoundary Top;
988  SmallVector<SUnit*, 8> BotRoots;
989 
990 public:
992  GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ") {}
993 
994  ~PostGenericScheduler() override = default;
995 
998  unsigned NumRegionInstrs) override {
999  /* no configurable policy */
1000  }
1001 
1002  /// PostRA scheduling does not track pressure.
1003  bool shouldTrackPressure() const override { return false; }
1004 
1005  void initialize(ScheduleDAGMI *Dag) override;
1006 
1007  void registerRoots() override;
1008 
1009  SUnit *pickNode(bool &IsTopNode) override;
1010 
1011  void scheduleTree(unsigned SubtreeID) override {
1012  llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1013  }
1014 
1015  void schedNode(SUnit *SU, bool IsTopNode) override;
1016 
1017  void releaseTopNode(SUnit *SU) override {
1018  if (SU->isScheduled)
1019  return;
1020  Top.releaseNode(SU, SU->TopReadyCycle);
1021  }
1022 
1023  // Only called for roots.
1024  void releaseBottomNode(SUnit *SU) override {
1025  BotRoots.push_back(SU);
1026  }
1027 
1028 protected:
1029  void tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1030 
1031  void pickNodeFromQueue(SchedCandidate &Cand);
1032 };
1033 
1034 /// Create the standard converging machine scheduler. This will be used as the
1035 /// default scheduler if the target does not set a default.
1036 /// Adds default DAG mutations.
1038 
1039 /// Create a generic scheduler with no vreg liveness or DAG mutation passes.
1041 
1042 std::unique_ptr<ScheduleDAGMutation>
1044  const TargetRegisterInfo *TRI);
1045 
1046 std::unique_ptr<ScheduleDAGMutation>
1048  const TargetRegisterInfo *TRI);
1049 
1050 std::unique_ptr<ScheduleDAGMutation>
1052  const TargetRegisterInfo *TRI);
1053 
1054 } // end namespace llvm
1055 
1056 #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:244
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:235
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:403
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
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:305
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:289
unsigned getID() const
ArrayRef< SUnit * > elements()
const RegPressureTracker & getBotRPTracker() const
Definition: BitVector.h:920
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:304
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:406
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...
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...
static const unsigned End
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...
#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
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:788
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)
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 - 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)
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
unsigned NodeQueueId
Queue id of node.
Definition: ScheduleDAG.h:270
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:411
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:59
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.
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:269
const std::vector< PressureChange > & getRegionCriticalPSets() const
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
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:1946
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:694
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:247
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.