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