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