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