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