LLVM 24.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>TargetMachine::
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>TargetMachine::
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>TargetMachine::
43// createMachineScheduler(MachineSchedContext *C) {
44// ScheduleDAGMI *DAG = createSchedLive(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// const SchedRegion &Region) 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"
82#include "llvm/ADT/StringRef.h"
83#include "llvm/ADT/Twine.h"
96#include <algorithm>
97#include <cassert>
98#include <list>
100#include <memory>
101#include <string>
102#include <vector>
103
104namespace llvm {
105namespace impl_detail {
106// FIXME: Remove these declarations once RegisterClassInfo is queryable as an
107// analysis.
111} // namespace impl_detail
112
113namespace MISched {
120} // namespace MISched
121
122/// Returns -misched-prera-direction.
124/// Returns -misched-postra-break-antideps.
126/// Returns whether -verify-misched is set.
128/// Return -misched-print-dags, which is false in a build without assertions.
130/// Return -misched-view-dags, which is false in a build without assertions.
132
133class AAResults;
134class LiveIntervals;
135class MachineFunction;
136class MachineInstr;
137class MachineLoopInfo;
138class RegisterClassInfo;
139class SchedDFSResult;
140class TargetInstrInfo;
141class TargetPassConfig;
142class TargetRegisterInfo;
143
144/// MachineSchedContext provides enough context from the MachineScheduler pass
145/// for the target to instantiate a scheduler.
161
162/// MachineSchedRegistry provides a selection of available machine instruction
163/// schedulers.
166 ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
167public:
169
170 // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
172
174
175 MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
177 Registry.Add(this);
178 }
179
180 ~MachineSchedRegistry() { Registry.Remove(this); }
181
182 // Accessors.
183 //
187
189 return (MachineSchedRegistry *)Registry.getList();
190 }
191
193 Registry.setListener(L);
194 }
195};
196
197class ScheduleDAGMI;
198
199/// Define a generic scheduling policy for targets that don't provide their own
200/// MachineSchedStrategy. This can be overriden for each scheduling region
201/// before building the DAG.
203 // Allow the scheduler to disable register pressure tracking.
205 /// Track LaneMasks to allow reordering of independent subregister writes
206 /// of the same vreg. \sa MachineSchedStrategy::shouldTrackLaneMasks()
208
209 // Allow the scheduler to force top-down or bottom-up scheduling. If neither
210 // is true, the scheduler runs in both directions and converges.
211 bool OnlyTopDown = false;
212 bool OnlyBottomUp = false;
213
214 // Disable heuristic that tries to fetch nodes from long dependency chains
215 // first.
217
218 // Compute DFSResult for use in scheduling heuristics.
219 bool ComputeDFSResult = false;
220
221 // If enabled, some extra cases of physreg defs will be biased towards user.
222 bool BiasPRegsExtra = false;
223
225};
226
227/// A region of an MBB for scheduling.
229 /// RegionBegin is the first instruction in the scheduling region, and
230 /// RegionEnd is either MBB->end() or the scheduling boundary after the
231 /// last instruction in the scheduling region. These iterators cannot refer
232 /// to instructions outside of the identified scheduling region because
233 /// those may be reordered before scheduling this region.
237
241};
242
243/// MachineSchedStrategy - Interface to the scheduling algorithm used by
244/// ScheduleDAGMI.
245///
246/// Initialization sequence:
247/// initPolicy -> shouldTrackPressure -> initialize(DAG) -> registerRoots
249 virtual void anchor();
250
251public:
252 virtual ~MachineSchedStrategy() = default;
253
254 /// Optionally override the per-region scheduling policy.
257 unsigned NumRegionInstrs) {}
258
259 virtual MachineSchedPolicy getPolicy() const { return {}; }
260 virtual void dumpPolicy() const {}
261
262 /// Check if pressure tracking is needed before building the DAG and
263 /// initializing this strategy. Called after initPolicy.
264 virtual bool shouldTrackPressure() const { return true; }
265
266 /// Returns true if lanemasks should be tracked. LaneMask tracking is
267 /// necessary to reorder independent subregister defs for the same vreg.
268 /// This has to be enabled in combination with shouldTrackPressure().
269 virtual bool shouldTrackLaneMasks() const { return false; }
270
271 // If this method returns true, handling of the scheduling regions
272 // themselves (in case of a scheduling boundary in MBB) will be done
273 // beginning with the topmost region of MBB.
274 virtual bool doMBBSchedRegionsTopDown() const { return false; }
275
276 /// Initialize the strategy after building the DAG for a new region.
277 virtual void initialize(ScheduleDAGMI *DAG) = 0;
278
279 /// Tell the strategy that MBB is about to be processed.
280 virtual void enterMBB(MachineBasicBlock *MBB) {};
281
282 /// Tell the strategy that current MBB is done.
283 virtual void leaveMBB() {};
284
285 /// Notify this strategy that all roots have been released (including those
286 /// that depend on EntrySU or ExitSU).
287 virtual void registerRoots() {}
288
289 /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
290 /// schedule the node at the top of the unscheduled region. Otherwise it will
291 /// be scheduled at the bottom.
292 virtual SUnit *pickNode(bool &IsTopNode) = 0;
293
294 /// Scheduler callback to notify that a new subtree is scheduled.
295 virtual void scheduleTree(unsigned SubtreeID) {}
296
297 /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
298 /// instruction and updated scheduled/remaining flags in the DAG nodes.
299 virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
300
301 /// When all predecessor dependencies have been resolved, free this node for
302 /// top-down scheduling.
303 virtual void releaseTopNode(SUnit *SU) = 0;
304
305 /// When all successor dependencies have been resolved, free this node for
306 /// bottom-up scheduling.
307 virtual void releaseBottomNode(SUnit *SU) = 0;
308};
309
310/// State for breaking physical-register anti-dependencies while scheduling a
311/// machine basic block after register allocation.
313 /// The selected breaker, or null when anti-dependency breaking is disabled.
314 std::unique_ptr<AntiDepBreaker> Breaker;
315
316 /// Instruction index of the current region's end in its basic block.
317 unsigned RegionEndIndex = 0;
318
319 /// Position from which boundary instructions are scanned for liveness.
320 MachineBasicBlock::iterator BoundaryScanPos;
321
322 /// Instruction index corresponding to `BoundaryScanPos`.
323 unsigned BoundaryScanIndex = 0;
324
325 /// Whether ScheduleDAGMI::schedule() processed the current region.
326 bool RegionProcessed = false;
327
328public:
331
333
334 void finishBlock();
335
337
340
341 bool breakAntiDependencies(const std::vector<SUnit> &SUnits,
345
346private:
347 void scanRangeBackwards(MachineBasicBlock::iterator From,
349};
350
351/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply
352/// schedules machine instructions according to the given MachineSchedStrategy
353/// without much extra book-keeping. This is the common functionality between
354/// PreRA and PostRA MachineScheduler.
356protected:
360 std::unique_ptr<MachineSchedStrategy> SchedImpl;
361
362 /// State for optional post-RA anti-dependency breaking.
364
365 /// Ordered list of DAG postprocessing steps.
366 std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
367
368 /// The top of the unscheduled zone.
370
371 /// The bottom of the unscheduled zone.
373
374#if LLVM_ENABLE_ABI_BREAKING_CHECKS
375 /// The number of instructions scheduled so far. Used to cut off the
376 /// scheduler at the point determined by misched-cutoff.
377 unsigned NumInstrsScheduled = 0;
378#endif
379
380public:
381 ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
382 bool RemoveKillFlags)
384 TargetSubtargetInfo::ANTIDEP_NONE) {}
385
386 /// Construct a post-RA scheduler with the requested anti-dependency mode.
387 ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr<MachineSchedStrategy> S,
388 bool RemoveKillFlags,
391 LIS(C->LIS), MBFI(C->MBFI), SchedImpl(std::move(S)),
393 ? TargetSubtargetInfo::ANTIDEP_NONE
394 : AntiDepMode) {}
395
396 // Provide a vtable anchor
397 ~ScheduleDAGMI() override;
398
399 /// If this method returns true, handling of the scheduling regions
400 /// themselves (in case of a scheduling boundary in MBB) will be done
401 /// beginning with the topmost region of MBB.
402 bool doMBBSchedRegionsTopDown() const override {
403 return SchedImpl->doMBBSchedRegionsTopDown();
404 }
405
406 // Returns LiveIntervals instance for use in DAG mutators and such.
407 LiveIntervals *getLIS() const { return LIS; }
408
409 /// Return true if this DAG supports VReg liveness and RegPressure.
410 virtual bool hasVRegLiveness() const { return false; }
411
412 /// Add a postprocessing step to the DAG builder.
413 /// Mutations are applied in the order that they are added after normal DAG
414 /// building and before MachineSchedStrategy initialization.
415 ///
416 /// ScheduleDAGMI takes ownership of the Mutation object.
417 void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
418 if (Mutation)
419 Mutations.push_back(std::move(Mutation));
420 }
421
424
425 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
426 /// region. This covers all instructions in a block, while schedule() may only
427 /// cover a subset.
428 void enterRegion(MachineBasicBlock *bb, MachineBasicBlock::iterator begin,
430 unsigned regioninstrs) override;
431
432 void exitRegion() override;
433
434 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
435 /// reorderable instructions.
436 void schedule() override;
437
438 void startBlock(MachineBasicBlock *bb) override;
439 void finishBlock() override;
440
441 /// Change the position of an instruction within the basic block and update
442 /// live ranges and region boundary iterators.
443 void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
444
445 void viewGraph(const Twine &Name, const Twine &Title) override;
446 void viewGraph() override;
447
448protected:
449 // Top-Level entry points for the schedule() driver...
450
451 /// Apply each ScheduleDAGMutation step in order. This allows different
452 /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
453 void postProcessDAG();
454
455 /// Release ExitSU predecessors and setup scheduler queues.
456 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
457
458 /// Update scheduler DAG and queues after scheduling an instruction.
459 void updateQueues(SUnit *SU, bool IsTopNode);
460
461 /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
462 void placeDebugValues();
463
464 /// dump the scheduled Sequence.
465 void dumpSchedule() const;
466 /// Print execution trace of the schedule top-down or bottom-up.
467 void dumpScheduleTraceTopDown() const;
468 void dumpScheduleTraceBottomUp() const;
469
470 // Lesser helpers...
471 bool checkSchedLimit();
472
473 void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
474 SmallVectorImpl<SUnit*> &BotRoots);
475
476 void releaseSucc(SUnit *SU, SDep *SuccEdge);
477 void releaseSuccessors(SUnit *SU);
478 void releasePred(SUnit *SU, SDep *PredEdge);
479 void releasePredecessors(SUnit *SU);
480};
481
482/// ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules
483/// machine instructions while updating LiveIntervals and tracking regpressure.
485protected:
487
488 /// Information about DAG subtrees. If DFSResult is NULL, then SchedulerTrees
489 /// will be empty.
492
494
495 /// Maps vregs to the SUnits of their uses in the current scheduling region.
497
498 // Map each SU to its summary of pressure changes. This array is updated for
499 // liveness during bottom-up scheduling. Top-down scheduling may proceed but
500 // has no affect on the pressure diffs.
502
503 /// Register pressure in this region computed by initRegPressure.
508
509 /// List of pressure sets that exceed the target's pressure limit before
510 /// scheduling, listed in increasing set ID order. Each pressure set is paired
511 /// with its max pressure in the currently scheduled regions.
512 std::vector<PressureChange> RegionCriticalPSets;
513
514 /// The top of the unscheduled zone.
517
518 /// The bottom of the unscheduled zone.
521
522public:
524 std::unique_ptr<MachineSchedStrategy> S)
525 : ScheduleDAGMI(C, std::move(S), /*RemoveKillFlags=*/false),
528
529 ~ScheduleDAGMILive() override;
530
531 /// Return true if this DAG supports VReg liveness and RegPressure.
532 bool hasVRegLiveness() const override { return true; }
533
534 /// Return true if register pressure tracking is enabled.
536
537 /// Get current register pressure for the top scheduled instructions.
538 const IntervalPressure &getTopPressure() const { return TopPressure; }
540
541 /// Get current register pressure for the bottom scheduled instructions.
542 const IntervalPressure &getBotPressure() const { return BotPressure; }
544
545 /// Get register pressure for the entire scheduling region before scheduling.
546 const IntervalPressure &getRegPressure() const { return RegPressure; }
547
548 const std::vector<PressureChange> &getRegionCriticalPSets() const {
549 return RegionCriticalPSets;
550 }
551
553 return SUPressureDiffs[SU->NodeNum];
554 }
555 const PressureDiff &getPressureDiff(const SUnit *SU) const {
556 return SUPressureDiffs[SU->NodeNum];
557 }
558
559 /// Compute a DFSResult after DAG building is complete, and before any
560 /// queue comparisons.
561 void computeDFSResult();
562
563 /// Return a non-null DFS result if the scheduling strategy initialized it.
564 const SchedDFSResult *getDFSResult() const { return DFSResult; }
565
567
568 /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
569 /// region. This covers all instructions in a block, while schedule() may only
570 /// cover a subset.
571 void enterRegion(MachineBasicBlock *bb,
574 unsigned regioninstrs) override;
575
576 /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
577 /// reorderable instructions.
578 void schedule() override;
579
580 /// Compute the cyclic critical path through the DAG.
581 unsigned computeCyclicCriticalPath();
582
583 void dump() const override;
584
585protected:
586 // Top-Level entry points for the schedule() driver...
587
588 /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
589 /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
590 /// region, TopTracker and BottomTracker will be initialized to the top and
591 /// bottom of the DAG region without covereing any unscheduled instruction.
592 void buildDAGWithRegPressure();
593
594 /// Release ExitSU predecessors and setup scheduler queues. Re-position
595 /// the Top RP tracker in case the region beginning has changed.
596 void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
597
598 /// Move an instruction and update register pressure.
599 void scheduleMI(SUnit *SU, bool IsTopNode);
600
601 // Lesser helpers...
602
603 void initRegPressure();
604
605 void updatePressureDiffs(ArrayRef<VRegMaskOrUnit> LiveUses);
606
607 void updateScheduledPressure(const SUnit *SU,
608 const std::vector<unsigned> &NewMaxPressure);
609
610 void collectVRegUses(SUnit &SU);
611};
612
613//===----------------------------------------------------------------------===//
614///
615/// Helpers for implementing custom MachineSchedStrategy classes. These take
616/// care of the book-keeping associated with list scheduling heuristics.
617///
618//===----------------------------------------------------------------------===//
619
620/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
621/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
622/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
623///
624/// This is a convenience class that may be used by implementations of
625/// MachineSchedStrategy.
627 unsigned ID;
628 std::string Name;
629 std::vector<SUnit*> Queue;
630
631public:
632 ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
633
634 unsigned getID() const { return ID; }
635
636 StringRef getName() const { return Name; }
637
638 // SU is in this queue if it's NodeQueueID is a superset of this ID.
639 bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
640
641 bool empty() const { return Queue.empty(); }
642
643 void clear() { Queue.clear(); }
644
645 unsigned size() const { return Queue.size(); }
646
647 using iterator = std::vector<SUnit*>::iterator;
648
649 iterator begin() { return Queue.begin(); }
650
651 iterator end() { return Queue.end(); }
652
653 ArrayRef<SUnit*> elements() { return Queue; }
654
655 iterator find(SUnit *SU) { return llvm::find(Queue, SU); }
656
657 void push(SUnit *SU) {
658 Queue.push_back(SU);
659 SU->NodeQueueId |= ID;
660 }
661
663 (*I)->NodeQueueId &= ~ID;
664 *I = Queue.back();
665 unsigned idx = I - Queue.begin();
666 Queue.pop_back();
667 return Queue.begin() + idx;
668 }
669
670 LLVM_ABI void dump() const;
671};
672
673/// Summarize the unscheduled region.
675 // Critical path through the DAG in expected latency.
676 unsigned CriticalPath;
678
679 // Scaled count of micro-ops left to schedule.
681
683
684 // Unscheduled resources
686
688
689 void reset() {
690 CriticalPath = 0;
691 CyclicCritPath = 0;
692 RemIssueCount = 0;
694 RemainingCounts.clear();
695 }
696
697 LLVM_ABI void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
698};
699
700/// ResourceSegments are a collection of intervals closed on the
701/// left and opened on the right:
702///
703/// list{ [a1, b1), [a2, b2), ..., [a_N, b_N) }
704///
705/// The collection has the following properties:
706///
707/// 1. The list is ordered: a_i < b_i and b_i < a_(i+1)
708///
709/// 2. The intervals in the collection do not intersect each other.
710///
711/// A \ref ResourceSegments instance represents the cycle
712/// reservation history of the instance of and individual resource.
714public:
715 /// Represents an interval of discrete integer values closed on
716 /// the left and open on the right: [a, b).
717 typedef std::pair<int64_t, int64_t> IntervalTy;
718
719 /// Adds an interval [a, b) to the collection of the instance.
720 ///
721 /// When adding [a, b[ to the collection, the operation merges the
722 /// adjacent intervals. For example
723 ///
724 /// 0 1 2 3 4 5 6 7 8 9 10
725 /// [-----) [--) [--)
726 /// + [--)
727 /// = [-----------) [--)
728 ///
729 /// To be able to debug duplicate resource usage, the function has
730 /// assertion that checks that no interval should be added if it
731 /// overlaps any of the intervals in the collection. We can
732 /// require this because by definition a \ref ResourceSegments is
733 /// attached only to an individual resource instance.
734 LLVM_ABI void add(IntervalTy A, const unsigned CutOff = 10);
735
736public:
737 /// Checks whether intervals intersect.
739
740 /// These function return the interval used by a resource in bottom and top
741 /// scheduling.
742 ///
743 /// Consider an instruction that uses resources X0, X1 and X2 as follows:
744 ///
745 /// X0 X1 X1 X2 +--------+-------------+--------------+
746 /// |Resource|AcquireAtCycle|ReleaseAtCycle|
747 /// +--------+-------------+--------------+
748 /// | X0 | 0 | 1 |
749 /// +--------+-------------+--------------+
750 /// | X1 | 1 | 3 |
751 /// +--------+-------------+--------------+
752 /// | X2 | 3 | 4 |
753 /// +--------+-------------+--------------+
754 ///
755 /// If we can schedule the instruction at cycle C, we need to
756 /// compute the interval of the resource as follows:
757 ///
758 /// # TOP DOWN SCHEDULING
759 ///
760 /// Cycles scheduling flows to the _right_, in the same direction
761 /// of time.
762 ///
763 /// C 1 2 3 4 5 ...
764 /// ------|------|------|------|------|------|----->
765 /// X0 X1 X1 X2 ---> direction of time
766 /// X0 [C, C+1)
767 /// X1 [C+1, C+3)
768 /// X2 [C+3, C+4)
769 ///
770 /// Therefore, the formula to compute the interval for a resource
771 /// of an instruction that can be scheduled at cycle C in top-down
772 /// scheduling is:
773 ///
774 /// [C+AcquireAtCycle, C+ReleaseAtCycle)
775 ///
776 ///
777 /// # BOTTOM UP SCHEDULING
778 ///
779 /// Cycles scheduling flows to the _left_, in opposite direction
780 /// of time.
781 ///
782 /// In bottom up scheduling, the scheduling happens in opposite
783 /// direction to the execution of the cycles of the
784 /// instruction. When the instruction is scheduled at cycle `C`,
785 /// the resources are allocated in the past relative to `C`:
786 ///
787 /// 2 1 C -1 -2 -3 -4 -5 ...
788 /// <-----|------|------|------|------|------|------|------|---
789 /// X0 X1 X1 X2 ---> direction of time
790 /// X0 (C+1, C]
791 /// X1 (C, C-2]
792 /// X2 (C-2, C-3]
793 ///
794 /// Therefore, the formula to compute the interval for a resource
795 /// of an instruction that can be scheduled at cycle C in bottom-up
796 /// scheduling is:
797 ///
798 /// [C-ReleaseAtCycle+1, C-AcquireAtCycle+1)
799 ///
800 ///
801 /// NOTE: In both cases, the number of cycles booked by a
802 /// resources is the value (ReleaseAtCycle - AcquireAtCycle).
803 static IntervalTy getResourceIntervalBottom(unsigned C, unsigned AcquireAtCycle,
804 unsigned ReleaseAtCycle) {
805 return std::make_pair<long, long>((long)C - (long)ReleaseAtCycle + 1L,
806 (long)C - (long)AcquireAtCycle + 1L);
807 }
808 static IntervalTy getResourceIntervalTop(unsigned C, unsigned AcquireAtCycle,
809 unsigned ReleaseAtCycle) {
810 return std::make_pair<long, long>((long)C + (long)AcquireAtCycle,
811 (long)C + (long)ReleaseAtCycle);
812 }
813
814private:
815 /// Finds the first cycle in which a resource can be allocated.
816 ///
817 /// The function uses the \param IntervalBuider [*] to build a
818 /// resource interval [a, b[ out of the input parameters \param
819 /// CurrCycle, \param AcquireAtCycle and \param ReleaseAtCycle.
820 ///
821 /// The function then loops through the intervals in the ResourceSegments
822 /// and shifts the interval [a, b[ and the ReturnCycle to the
823 /// right until there is no intersection between the intervals of
824 /// the \ref ResourceSegments instance and the new shifted [a, b[. When
825 /// this condition is met, the ReturnCycle (which
826 /// correspond to the cycle in which the resource can be
827 /// allocated) is returned.
828 ///
829 /// c = CurrCycle in input
830 /// c 1 2 3 4 5 6 7 8 9 10 ... ---> (time
831 /// flow)
832 /// ResourceSegments... [---) [-------) [-----------)
833 /// c [1 3[ -> AcquireAtCycle=1, ReleaseAtCycle=3
834 /// ++c [1 3)
835 /// ++c [1 3)
836 /// ++c [1 3)
837 /// ++c [1 3)
838 /// ++c [1 3) ---> returns c
839 /// incremented by 5 (c+5)
840 ///
841 ///
842 /// Notice that for bottom-up scheduling the diagram is slightly
843 /// different because the current cycle c is always on the right
844 /// of the interval [a, b) (see \ref
845 /// `getResourceIntervalBottom`). This is because the cycle
846 /// increments for bottom-up scheduling moved in the direction
847 /// opposite to the direction of time:
848 ///
849 /// --------> direction of time.
850 /// XXYZZZ (resource usage)
851 /// --------> direction of top-down execution cycles.
852 /// <-------- direction of bottom-up execution cycles.
853 ///
854 /// Even though bottom-up scheduling moves against the flow of
855 /// time, the algorithm used to find the first free slot in between
856 /// intervals is the same as for top-down scheduling.
857 ///
858 /// [*] See \ref `getResourceIntervalTop` and
859 /// \ref `getResourceIntervalBottom` to see how such resource intervals
860 /// are built.
861 LLVM_ABI unsigned getFirstAvailableAt(
862 unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle,
863 std::function<IntervalTy(unsigned, unsigned, unsigned)> IntervalBuilder)
864 const;
865
866public:
867 /// getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop
868 /// should be merged in a single function in which a function that
869 /// creates the `NewInterval` is passed as a parameter.
870 unsigned getFirstAvailableAtFromBottom(unsigned CurrCycle,
871 unsigned AcquireAtCycle,
872 unsigned ReleaseAtCycle) const {
873 return getFirstAvailableAt(CurrCycle, AcquireAtCycle, ReleaseAtCycle,
875 }
876 unsigned getFirstAvailableAtFromTop(unsigned CurrCycle,
877 unsigned AcquireAtCycle,
878 unsigned ReleaseAtCycle) const {
879 return getFirstAvailableAt(CurrCycle, AcquireAtCycle, ReleaseAtCycle,
881 }
882
883private:
884 std::list<IntervalTy> _Intervals;
885 /// Merge all adjacent intervals in the collection. For all pairs
886 /// of adjacient intervals, it performs [a, b) + [b, c) -> [a, c).
887 ///
888 /// Before performing the merge operation, the intervals are
889 /// sorted with \ref sort_predicate.
890 LLVM_ABI void sortAndMerge();
891
892public:
893 // constructor for empty set
894 explicit ResourceSegments() = default;
895 bool empty() const { return _Intervals.empty(); }
896 explicit ResourceSegments(const std::list<IntervalTy> &Intervals)
897 : _Intervals(Intervals) {
898 sortAndMerge();
899 }
900
901 friend bool operator==(const ResourceSegments &c1,
902 const ResourceSegments &c2) {
903 return c1._Intervals == c2._Intervals;
904 }
906 const ResourceSegments &Segments) {
907 os << "{ ";
908 for (auto p : Segments._Intervals)
909 os << "[" << p.first << ", " << p.second << "), ";
910 os << "}\n";
911 return os;
912 }
913};
914
915/// Each Scheduling boundary is associated with ready queues. It tracks the
916/// current cycle in the direction of movement, and maintains the state
917/// of "hazards" and other interlocks at the current cycle.
919public:
920 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
921 enum {
925 };
926
927 ScheduleDAGMI *DAG = nullptr;
928 const TargetSchedModel *SchedModel = nullptr;
929 SchedRemainder *Rem = nullptr;
930
933
934 std::unique_ptr<ScheduleHazardRecognizer> HazardRec;
935
936private:
937 /// True if the pending Q should be checked/updated before scheduling another
938 /// instruction.
939 bool CheckPending;
940
941 /// Number of cycles it takes to issue the instructions scheduled in this
942 /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls.
943 /// See getStalls().
944 unsigned CurrCycle;
945
946 /// Micro-ops issued in the current cycle
947 unsigned CurrMOps;
948
949 /// MinReadyCycle - Cycle of the soonest available instruction.
950 unsigned MinReadyCycle;
951
952 // The expected latency of the critical path in this scheduled zone.
953 unsigned ExpectedLatency;
954
955 // The latency of dependence chains leading into this zone.
956 // For each node scheduled bottom-up: DLat = max DLat, N.Depth.
957 // For each cycle scheduled: DLat -= 1.
958 unsigned DependentLatency;
959
960 /// Count the scheduled (issued) micro-ops that can be retired by
961 /// time=CurrCycle assuming the first scheduled instr is retired at time=0.
962 unsigned RetiredMOps;
963
964 // Count scheduled resources that have been executed. Resources are
965 // considered executed if they become ready in the time that it takes to
966 // saturate any resource including the one in question. Counts are scaled
967 // for direct comparison with other resources. Counts can be compared with
968 // MOps * getMicroOpFactor and Latency * getLatencyFactor.
969 SmallVector<unsigned, 16> ExecutedResCounts;
970
971 /// Cache the max count for a single resource.
972 unsigned MaxExecutedResCount;
973
974 // Cache the critical resources ID in this scheduled zone.
975 unsigned ZoneCritResIdx;
976
977 // Is the scheduled region resource limited vs. latency limited.
978 bool IsResourceLimited;
979
980public:
981private:
982 /// Record how resources have been allocated across the cycles of
983 /// the execution.
984 std::map<unsigned, ResourceSegments> ReservedResourceSegments;
985 std::vector<unsigned> ReservedCycles;
986 /// For each PIdx, stores first index into ReservedResourceSegments that
987 /// corresponds to it.
988 ///
989 /// For example, consider the following 3 resources (ResourceCount =
990 /// 3):
991 ///
992 /// +------------+--------+
993 /// |ResourceName|NumUnits|
994 /// +------------+--------+
995 /// | X | 2 |
996 /// +------------+--------+
997 /// | Y | 3 |
998 /// +------------+--------+
999 /// | Z | 1 |
1000 /// +------------+--------+
1001 ///
1002 /// In this case, the total number of resource instances is 6. The
1003 /// vector \ref ReservedResourceSegments will have a slot for each instance.
1004 /// The vector \ref ReservedCyclesIndex will track at what index the first
1005 /// instance of the resource is found in the vector of \ref
1006 /// ReservedResourceSegments:
1007 ///
1008 /// Indexes of instances in
1009 /// ReservedResourceSegments
1010 ///
1011 /// 0 1 2 3 4 5
1012 /// ReservedCyclesIndex[0] = 0; [X0, X1,
1013 /// ReservedCyclesIndex[1] = 2; Y0, Y1, Y2
1014 /// ReservedCyclesIndex[2] = 5; Z
1015 SmallVector<unsigned, 16> ReservedCyclesIndex;
1016
1017 // For each PIdx, stores the resource group IDs of its subunits
1018 SmallVector<APInt, 16> ResourceGroupSubUnitMasks;
1019
1020#if LLVM_ENABLE_ABI_BREAKING_CHECKS
1021 // Remember the greatest possible stall as an upper bound on the number of
1022 // times we should retry the pending queue because of a hazard.
1023 unsigned MaxObservedStall;
1024#endif
1025
1026public:
1027 /// Pending queues extend the ready queues with the same ID and the
1028 /// PendingFlag set.
1029 SchedBoundary(unsigned ID, const Twine &Name):
1030 Available(ID, Name+".A"), Pending(ID << LogMaxQID, Name+".P") {
1031 reset();
1032 }
1033 SchedBoundary &operator=(const SchedBoundary &other) = delete;
1034 SchedBoundary(const SchedBoundary &other) = delete;
1036
1037 LLVM_ABI void reset();
1038
1039 LLVM_ABI void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
1040 SchedRemainder *rem);
1041
1042 bool isTop() const {
1043 return Available.getID() == TopQID;
1044 }
1045
1046 /// Number of cycles to issue the instructions scheduled in this zone.
1047 unsigned getCurrCycle() const { return CurrCycle; }
1048
1049 /// Micro-ops issued in the current cycle
1050 unsigned getCurrMOps() const { return CurrMOps; }
1051
1052 // The latency of dependence chains leading into this zone.
1053 unsigned getDependentLatency() const { return DependentLatency; }
1054
1055 /// Get the number of latency cycles "covered" by the scheduled
1056 /// instructions. This is the larger of the critical path within the zone
1057 /// and the number of cycles required to issue the instructions.
1058 unsigned getScheduledLatency() const {
1059 return std::max(ExpectedLatency, CurrCycle);
1060 }
1061
1062 unsigned getUnscheduledLatency(SUnit *SU) const {
1063 return isTop() ? SU->getHeight() : SU->getDepth();
1064 }
1065
1066 unsigned getResourceCount(unsigned ResIdx) const {
1067 return ExecutedResCounts[ResIdx];
1068 }
1069
1070 /// Get the scaled count of scheduled micro-ops and resources, including
1071 /// executed resources.
1072 unsigned getCriticalCount() const {
1073 if (!ZoneCritResIdx)
1074 return RetiredMOps * SchedModel->getMicroOpFactor();
1075 return getResourceCount(ZoneCritResIdx);
1076 }
1077
1078 /// Get a scaled count for the minimum execution time of the scheduled
1079 /// micro-ops that are ready to execute by getExecutedCount. Notice the
1080 /// feedback loop.
1081 unsigned getExecutedCount() const {
1082 return std::max(CurrCycle * SchedModel->getLatencyFactor(),
1083 MaxExecutedResCount);
1084 }
1085
1086 unsigned getZoneCritResIdx() const { return ZoneCritResIdx; }
1087
1088 // Is the scheduled region resource limited vs. latency limited.
1089 bool isResourceLimited() const { return IsResourceLimited; }
1090
1091 /// Get the difference between the given SUnit's ready time and the current
1092 /// cycle.
1093 LLVM_ABI unsigned getLatencyStallCycles(SUnit *SU);
1094
1095 LLVM_ABI unsigned getNextResourceCycleByInstance(unsigned InstanceIndex,
1096 unsigned ReleaseAtCycle,
1097 unsigned AcquireAtCycle);
1098
1099 LLVM_ABI std::pair<unsigned, unsigned>
1100 getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx,
1101 unsigned ReleaseAtCycle, unsigned AcquireAtCycle);
1102
1103 bool isReservedGroup(unsigned PIdx) const {
1104 return SchedModel->getProcResource(PIdx)->SubUnitsIdxBegin &&
1105 !SchedModel->getProcResource(PIdx)->BufferSize;
1106 }
1107
1108 LLVM_ABI bool checkHazard(SUnit *SU);
1109
1110 LLVM_ABI unsigned findMaxLatency(ArrayRef<SUnit *> ReadySUs);
1111
1112 LLVM_ABI unsigned getOtherResourceCount(unsigned &OtherCritIdx);
1113
1114 /// Release SU to make it ready. If it's not in hazard, remove it from
1115 /// pending queue (if already in) and push into available queue.
1116 /// Otherwise, push the SU into pending queue.
1117 ///
1118 /// @param SU The unit to be released.
1119 /// @param ReadyCycle Until which cycle the unit is ready.
1120 /// @param InPQueue Whether SU is already in pending queue.
1121 /// @param Idx Position offset in pending queue (if in it).
1122 LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue,
1123 unsigned Idx = 0);
1124
1125 LLVM_ABI void bumpCycle(unsigned NextCycle);
1126
1127 LLVM_ABI void incExecutedResources(unsigned PIdx, unsigned Count);
1128
1129 LLVM_ABI unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx,
1130 unsigned Cycles, unsigned ReadyCycle,
1131 unsigned StartAtCycle);
1132
1133 LLVM_ABI void bumpNode(SUnit *SU);
1134
1135 LLVM_ABI void releasePending();
1136
1137 LLVM_ABI void removeReady(SUnit *SU);
1138
1139 /// Call this before applying any other heuristics to the Available queue.
1140 /// Updates the Available/Pending Q's if necessary and returns the single
1141 /// available instruction, or NULL if there are multiple candidates.
1143
1144 /// Dump the state of the information that tracks resource usage.
1145 LLVM_ABI void dumpReservedCycles() const;
1146 LLVM_ABI void dumpScheduledState() const;
1147};
1148
1149/// Base class for GenericScheduler. This class maintains information about
1150/// scheduling candidates based on TargetSchedModel making it easy to implement
1151/// heuristics for either preRA or postRA scheduling.
1153public:
1154 /// Represent the type of SchedCandidate found within a single queue.
1155 /// pickNodeBidirectional depends on these listed by decreasing priority.
1175
1176#ifndef NDEBUG
1177 static const char *getReasonStr(GenericSchedulerBase::CandReason Reason);
1178#endif
1179
1180 /// Policy for scheduling the next instruction in the candidate's zone.
1181 struct CandPolicy {
1182 bool ReduceLatency = false;
1183 unsigned ReduceResIdx = 0;
1184 unsigned DemandResIdx = 0;
1185
1186 CandPolicy() = default;
1187
1188 bool operator==(const CandPolicy &RHS) const {
1189 return ReduceLatency == RHS.ReduceLatency &&
1190 ReduceResIdx == RHS.ReduceResIdx &&
1191 DemandResIdx == RHS.DemandResIdx;
1192 }
1193 bool operator!=(const CandPolicy &RHS) const {
1194 return !(*this == RHS);
1195 }
1196 };
1197
1198 /// Status of an instruction's critical resource consumption.
1200 // Count critical resources in the scheduled region required by SU.
1201 unsigned CritResources = 0;
1202
1203 // Count critical resources from another region consumed by SU.
1204 unsigned DemandedResources = 0;
1205
1207
1208 bool operator==(const SchedResourceDelta &RHS) const {
1209 return CritResources == RHS.CritResources
1210 && DemandedResources == RHS.DemandedResources;
1211 }
1212 bool operator!=(const SchedResourceDelta &RHS) const {
1213 return !operator==(RHS);
1214 }
1215 };
1216
1217 /// Store the state used by GenericScheduler heuristics, required for the
1218 /// lifetime of one invocation of pickNode().
1221
1222 // The best SUnit candidate.
1224
1225 // The reason for this candidate.
1227
1228 // Whether this candidate should be scheduled at top/bottom.
1229 bool AtTop;
1230
1231 // Register pressure values for the best candidate.
1233
1234 // Critical resource consumption of the best candidate.
1236
1239
1240 void reset(const CandPolicy &NewPolicy) {
1241 Policy = NewPolicy;
1242 SU = nullptr;
1243 Reason = NoCand;
1244 AtTop = false;
1247 }
1248
1249 bool isValid() const { return SU; }
1250
1251 // Copy the status of another candidate without changing policy.
1253 assert(Best.Reason != NoCand && "uninitialized Sched candidate");
1254 SU = Best.SU;
1255 Reason = Best.Reason;
1256 AtTop = Best.AtTop;
1257 RPDelta = Best.RPDelta;
1258 ResDelta = Best.ResDelta;
1259 }
1260
1263 };
1264
1265protected:
1268 const TargetRegisterInfo *TRI = nullptr;
1269 unsigned TopIdx = 0;
1270 unsigned BotIdx = 0;
1271 unsigned NumRegionInstrs = 0;
1272
1274
1276
1278
1279 LLVM_ABI void setPolicy(CandPolicy &Policy, bool IsPostRA,
1280 SchedBoundary &CurrZone, SchedBoundary *OtherZone);
1281
1282 MachineSchedPolicy getPolicy() const override { return RegionPolicy; }
1283
1284#ifndef NDEBUG
1285 void traceCandidate(const SchedCandidate &Cand);
1286#endif
1287
1288private:
1289 bool shouldReduceLatency(const CandPolicy &Policy, SchedBoundary &CurrZone,
1290 bool ComputeRemLatency, unsigned &RemLatency) const;
1291};
1292
1293// Utility functions used by heuristics in tryCandidate().
1294LLVM_ABI unsigned computeRemLatency(SchedBoundary &CurrZone);
1295LLVM_ABI bool tryLess(int TryVal, int CandVal,
1296 GenericSchedulerBase::SchedCandidate &TryCand,
1297 GenericSchedulerBase::SchedCandidate &Cand,
1299LLVM_ABI bool tryGreater(int TryVal, int CandVal,
1300 GenericSchedulerBase::SchedCandidate &TryCand,
1301 GenericSchedulerBase::SchedCandidate &Cand,
1303LLVM_ABI bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
1304 GenericSchedulerBase::SchedCandidate &Cand,
1305 SchedBoundary &Zone);
1306LLVM_ABI bool tryPressure(const PressureChange &TryP,
1307 const PressureChange &CandP,
1308 GenericSchedulerBase::SchedCandidate &TryCand,
1309 GenericSchedulerBase::SchedCandidate &Cand,
1311 const TargetRegisterInfo *TRI,
1312 const MachineFunction &MF);
1313LLVM_ABI bool tryBiasPhysRegs(GenericSchedulerBase::SchedCandidate &TryCand,
1314 GenericSchedulerBase::SchedCandidate &Cand,
1315 SchedBoundary *Zone, bool BiasPRegsExtra);
1316LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop);
1317LLVM_ABI int biasPhysReg(const SUnit *SU, bool isTop,
1318 bool BiasPRegsExtra = false);
1319
1320/// GenericScheduler shrinks the unscheduled zone using heuristics to balance
1321/// the schedule.
1323public:
1325 GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
1326 Bot(SchedBoundary::BotQID, "BotQ") {}
1327
1328 void initPolicy(MachineBasicBlock::iterator Begin,
1330 unsigned NumRegionInstrs) override;
1331
1332 void dumpPolicy() const override;
1333
1334 bool shouldTrackPressure() const override {
1335 return RegionPolicy.ShouldTrackPressure;
1336 }
1337
1338 bool shouldTrackLaneMasks() const override {
1339 return RegionPolicy.ShouldTrackLaneMasks;
1340 }
1341
1342 void initialize(ScheduleDAGMI *dag) override;
1343
1344 SUnit *pickNode(bool &IsTopNode) override;
1345
1346 void schedNode(SUnit *SU, bool IsTopNode) override;
1347
1348 void releaseTopNode(SUnit *SU) override {
1349 if (SU->isScheduled)
1350 return;
1351
1352 Top.releaseNode(SU, SU->TopReadyCycle, false);
1353 TopCand.SU = nullptr;
1354 }
1355
1356 void releaseBottomNode(SUnit *SU) override {
1357 if (SU->isScheduled)
1358 return;
1359
1360 Bot.releaseNode(SU, SU->BotReadyCycle, false);
1361 BotCand.SU = nullptr;
1362 }
1363
1364 void registerRoots() override;
1365
1366protected:
1368
1369 // State of the top and bottom scheduled instruction boundaries.
1372
1375
1376 /// Candidate last picked from Top boundary.
1378 /// Candidate last picked from Bot boundary.
1380
1381 void checkAcyclicLatency();
1382
1383 void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop,
1384 const RegPressureTracker &RPTracker,
1385 RegPressureTracker &TempTracker);
1386
1387 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand,
1388 SchedBoundary *Zone) const;
1389
1390 SUnit *pickNodeBidirectional(bool &IsTopNode);
1391
1393 const CandPolicy &ZonePolicy,
1394 const RegPressureTracker &RPTracker,
1395 SchedCandidate &Candidate);
1396
1397 void reschedulePhysReg(SUnit *SU, bool isTop);
1398};
1399
1400/// PostGenericScheduler - Interface to the scheduling algorithm used by
1401/// ScheduleDAGMI.
1402///
1403/// Callbacks from ScheduleDAGMI:
1404/// initPolicy -> initialize(DAG) -> registerRoots -> pickNode ...
1406protected:
1407 ScheduleDAGMI *DAG = nullptr;
1410
1411 /// Candidate last picked from Top boundary.
1413 /// Candidate last picked from Bot boundary.
1415
1418
1419public:
1421 : GenericSchedulerBase(C), Top(SchedBoundary::TopQID, "TopQ"),
1422 Bot(SchedBoundary::BotQID, "BotQ") {}
1423
1424 ~PostGenericScheduler() override = default;
1425
1428 unsigned NumRegionInstrs) override;
1429
1430 /// PostRA scheduling does not track pressure.
1431 bool shouldTrackPressure() const override { return false; }
1432
1433 void initialize(ScheduleDAGMI *Dag) override;
1434
1435 void registerRoots() override;
1436
1437 SUnit *pickNode(bool &IsTopNode) override;
1438
1439 SUnit *pickNodeBidirectional(bool &IsTopNode);
1440
1441 void scheduleTree(unsigned SubtreeID) override {
1442 llvm_unreachable("PostRA scheduler does not support subtree analysis.");
1443 }
1444
1445 void schedNode(SUnit *SU, bool IsTopNode) override;
1446
1447 void releaseTopNode(SUnit *SU) override {
1448 if (SU->isScheduled)
1449 return;
1450 Top.releaseNode(SU, SU->TopReadyCycle, false);
1451 TopCand.SU = nullptr;
1452 }
1453
1454 void releaseBottomNode(SUnit *SU) override {
1455 if (SU->isScheduled)
1456 return;
1457 Bot.releaseNode(SU, SU->BotReadyCycle, false);
1458 BotCand.SU = nullptr;
1459 }
1460
1461protected:
1462 virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand);
1463
1464 void pickNodeFromQueue(SchedBoundary &Zone, SchedCandidate &Cand);
1465};
1466
1467/// If ReorderWhileClustering is set to true, no attempt will be made to
1468/// reduce reordering due to store clustering.
1469LLVM_ABI std::unique_ptr<ScheduleDAGMutation>
1470createLoadClusterDAGMutation(const TargetInstrInfo *TII,
1471 bool ReorderWhileClustering = false);
1472
1473/// If ReorderWhileClustering is set to true, no attempt will be made to
1474/// reduce reordering due to store clustering.
1475LLVM_ABI std::unique_ptr<ScheduleDAGMutation>
1476createStoreClusterDAGMutation(const TargetInstrInfo *TII,
1477 bool ReorderWhileClustering = false);
1478
1479LLVM_ABI std::unique_ptr<ScheduleDAGMutation>
1480createCopyConstrainDAGMutation(const TargetInstrInfo *TII);
1481
1482/// Create the standard converging machine scheduler. This will be used as the
1483/// default scheduler if the target does not set a default.
1484/// Adds default DAG mutations.
1485template <typename Strategy = GenericScheduler>
1487 ScheduleDAGMILive *DAG =
1488 new ScheduleDAGMILive(C, std::make_unique<Strategy>(C));
1489 // Register DAG post-processors.
1490 //
1491 // FIXME: extend the mutation API to allow earlier mutations to instantiate
1492 // data and pass it to later mutations. Have a single mutation that gathers
1493 // the interesting nodes in one pass.
1495 return DAG;
1496}
1497
1498/// Create a generic scheduler with no vreg liveness or DAG mutation passes.
1499template <typename Strategy = PostGenericScheduler>
1501 return new ScheduleDAGMI(C, std::make_unique<Strategy>(C),
1502 /*RemoveKillFlags=*/true, getPostRABreakAntiDeps());
1503}
1504
1506 : public OptionalPassInfoMixin<MachineSchedulerPass> {
1507 // FIXME: Remove this member once RegisterClassInfo is queryable as an
1508 // analysis.
1509 std::unique_ptr<impl_detail::MachineSchedulerImpl> Impl;
1510 const TargetMachine *TM;
1511
1512public:
1518};
1519
1521 : public OptionalPassInfoMixin<SSAMachineSchedulerPass> {
1522 // FIXME: Remove this member once RegisterClassInfo is queryable as an
1523 // analysis.
1524 std::unique_ptr<impl_detail::SSAMachineSchedulerImpl> Impl;
1525 const TargetMachine *TM;
1526
1527public:
1533};
1534
1536 : public OptionalPassInfoMixin<PostMachineSchedulerPass> {
1537 // FIXME: Remove this member once RegisterClassInfo is queryable as an
1538 // analysis.
1539 std::unique_ptr<impl_detail::PostMachineSchedulerImpl> Impl;
1540 const TargetMachine *TM;
1541
1542public:
1548};
1549} // end namespace llvm
1550
1551#endif // LLVM_CODEGEN_MACHINESCHEDULER_H
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock & MBB
This file implements the BitVector class.
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
#define LLVM_ABI
Definition Compiler.h:211
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition MD5.cpp:57
Register const TargetRegisterInfo * TRI
PowerPC VSX FMA Mutation
This file contains some templates that are useful if you are working with the STL at all.
static const char * name
This file defines the SmallVector class.
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, const llvm::StringTable &StandardNames, VectorLibrary VecLib)
Initialize the set of available library functions based on the specified target triple.
Value * RHS
std::vector< std::pair< MachineInstr *, MachineInstr * > > DbgValueVector
State for breaking physical-register anti-dependencies while scheduling a machine basic block after r...
void startBlock(MachineBasicBlock *MBB)
bool breakAntiDependencies(const std::vector< SUnit > &SUnits, MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, AntiDepBreaker::DbgValueVector &DbgValues)
void exitRegion(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End)
AntiDepState(MachineSchedContext *C, TargetSubtargetInfo::AntiDepBreakMode AntiDepMode)
void enterRegion(MachineBasicBlock::iterator End)
Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition ArrayRef.h:40
void traceCandidate(const SchedCandidate &Cand)
LLVM_ABI 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...
MachineSchedPolicy RegionPolicy
const TargetSchedModel * SchedModel
static const char * getReasonStr(GenericSchedulerBase::CandReason Reason)
MachineSchedPolicy getPolicy() const override
GenericSchedulerBase(const MachineSchedContext *C)
const MachineSchedContext * Context
CandReason
Represent the type of SchedCandidate found within a single queue.
const TargetRegisterInfo * TRI
void checkAcyclicLatency()
Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic critical path by more cycle...
SchedCandidate BotCand
Candidate last picked from Bot boundary.
SchedCandidate TopCand
Candidate last picked from Top boundary.
virtual bool tryCandidate(SchedCandidate &Cand, SchedCandidate &TryCand, SchedBoundary *Zone) const
Apply a set of heuristics to a new candidate.
ScheduleDAGMILive * DAG
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
void initCandidate(SchedCandidate &Cand, SUnit *SU, bool AtTop, const RegPressureTracker &RPTracker, RegPressureTracker &TempTracker)
bool shouldTrackPressure() const override
Check if pressure tracking is needed before building the DAG and initializing this strategy.
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
void reschedulePhysReg(SUnit *SU, bool isTop)
void pickNodeFromQueue(SchedBoundary &Zone, const CandPolicy &ZonePolicy, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the queue.
bool shouldTrackLaneMasks() const override
Returns true if lanemasks should be tracked.
GenericScheduler(const MachineSchedContext *C)
SUnit * pickNodeBidirectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
MachineInstrBundleIterator< MachineInstr > iterator
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
Representation of each machine instruction.
MachinePassRegistryListener - Listener to adds and removals of nodes in registration list.
MachinePassRegistryNode(const char *N, const char *D, ScheduleDAGInstrs *C)
MachinePassRegistryNode * getNext() const
MachinePassRegistry - Track the registration of machine passes.
static void setListener(MachinePassRegistryListener< FunctionPassCtor > *L)
static LLVM_ABI MachinePassRegistry< ScheduleDAGCtor > Registry
MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
static MachineSchedRegistry * getList()
ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor
MachineSchedRegistry * getNext() const
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
virtual bool shouldTrackPressure() const
Check if pressure tracking is needed before building the DAG and initializing this strategy.
virtual void leaveMBB()
Tell the strategy that current MBB is done.
virtual void enterMBB(MachineBasicBlock *MBB)
Tell the strategy that MBB is about to be processed.
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
virtual void schedNode(SUnit *SU, bool IsTopNode)=0
Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an instruction and updated scheduled/rem...
virtual ~MachineSchedStrategy()=default
virtual void initialize(ScheduleDAGMI *DAG)=0
Initialize the strategy after building the DAG for a new region.
virtual MachineSchedPolicy getPolicy() const
virtual void releaseTopNode(SUnit *SU)=0
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
virtual void dumpPolicy() const
virtual bool doMBBSchedRegionsTopDown() const
virtual SUnit * pickNode(bool &IsTopNode)=0
Pick the next node to schedule, or return NULL.
virtual void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs)
Optionally override the per-region scheduling policy.
virtual void releaseBottomNode(SUnit *SU)=0
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
virtual bool shouldTrackLaneMasks() const
Returns true if lanemasks should be tracked.
virtual void registerRoots()
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI MachineSchedulerPass(const TargetMachine *TM)
LLVM_ABI MachineSchedulerPass(MachineSchedulerPass &&Other)
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Optionally override the per-region scheduling policy.
bool shouldTrackPressure() const override
PostRA scheduling does not track pressure.
void scheduleTree(unsigned SubtreeID) override
Scheduler callback to notify that a new subtree is scheduled.
SchedCandidate BotCand
Candidate last picked from Bot boundary.
SchedCandidate TopCand
Candidate last picked from Top boundary.
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
~PostGenericScheduler() override=default
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
PostGenericScheduler(const MachineSchedContext *C)
LLVM_ABI PostMachineSchedulerPass(PostMachineSchedulerPass &&Other)
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI PostMachineSchedulerPass(const TargetMachine *TM)
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
List of PressureChanges in order of increasing, unique PSetID.
Array of PressureDiffs.
Helpers for implementing custom MachineSchedStrategy classes.
void push(SUnit *SU)
iterator find(SUnit *SU)
ArrayRef< SUnit * > elements()
LLVM_ABI void dump() const
ReadyQueue(unsigned id, const Twine &name)
bool isInQueue(SUnit *SU) const
std::vector< SUnit * >::iterator iterator
StringRef getName() const
unsigned size() const
iterator remove(iterator I)
unsigned getID() const
Track the current register pressure at some position in the instruction stream, and remember the high...
LLVM_ABI void add(IntervalTy A, const unsigned CutOff=10)
Adds an interval [a, b) to the collection of the instance.
static IntervalTy getResourceIntervalBottom(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
These function return the interval used by a resource in bottom and top scheduling.
friend bool operator==(const ResourceSegments &c1, const ResourceSegments &c2)
static LLVM_ABI bool intersects(IntervalTy A, IntervalTy B)
Checks whether intervals intersect.
unsigned getFirstAvailableAtFromTop(unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle) const
friend llvm::raw_ostream & operator<<(llvm::raw_ostream &os, const ResourceSegments &Segments)
std::pair< int64_t, int64_t > IntervalTy
Represents an interval of discrete integer values closed on the left and open on the right: [a,...
static IntervalTy getResourceIntervalTop(unsigned C, unsigned AcquireAtCycle, unsigned ReleaseAtCycle)
ResourceSegments(const std::list< IntervalTy > &Intervals)
unsigned getFirstAvailableAtFromBottom(unsigned CurrCycle, unsigned AcquireAtCycle, unsigned ReleaseAtCycle) const
getFirstAvailableAtFromBottom and getFirstAvailableAtFromTop should be merged in a single function in...
Scheduling dependency.
Definition ScheduleDAG.h:54
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI SSAMachineSchedulerPass(SSAMachineSchedulerPass &&Other)
LLVM_ABI SSAMachineSchedulerPass(const TargetMachine *TM)
Scheduling unit. This is a node in the scheduling DAG.
unsigned NodeQueueId
Queue id of node.
unsigned TopReadyCycle
Cycle relative to start when node is ready.
unsigned NodeNum
Entry # of node in the node vector.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
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...
bool isScheduled
True once scheduled.
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Each Scheduling boundary is associated with ready queues.
LLVM_ABI unsigned getNextResourceCycleByInstance(unsigned InstanceIndex, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
Compute the next cycle at which the given processor resource unit can be scheduled.
LLVM_ABI void releasePending()
Release pending ready nodes in to the available queue.
unsigned getDependentLatency() const
bool isReservedGroup(unsigned PIdx) const
unsigned getScheduledLatency() const
Get the number of latency cycles "covered" by the scheduled instructions.
LLVM_ABI void incExecutedResources(unsigned PIdx, unsigned Count)
bool isResourceLimited() const
const TargetSchedModel * SchedModel
unsigned getExecutedCount() const
Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execut...
LLVM_ABI unsigned getLatencyStallCycles(SUnit *SU)
Get the difference between the given SUnit's ready time and the current cycle.
SchedBoundary(const SchedBoundary &other)=delete
LLVM_ABI unsigned findMaxLatency(ArrayRef< SUnit * > ReadySUs)
LLVM_ABI void dumpReservedCycles() const
Dump the state of the information that tracks resource usage.
LLVM_ABI unsigned getOtherResourceCount(unsigned &OtherCritIdx)
SchedRemainder * Rem
LLVM_ABI void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
unsigned getCriticalCount() const
Get the scaled count of scheduled micro-ops and resources, including executed resources.
LLVM_ABI SUnit * pickOnlyChoice()
Call this before applying any other heuristics to the Available queue.
LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle, bool InPQueue, unsigned Idx=0)
Release SU to make it ready.
LLVM_ABI unsigned countResource(const MCSchedClassDesc *SC, unsigned PIdx, unsigned Cycles, unsigned ReadyCycle, unsigned StartAtCycle)
Add the given processor resource to this scheduled zone.
SchedBoundary(unsigned ID, const Twine &Name)
Pending queues extend the ready queues with the same ID and the PendingFlag set.
LLVM_ABI ~SchedBoundary()
LLVM_ABI void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem)
SchedBoundary & operator=(const SchedBoundary &other)=delete
unsigned getResourceCount(unsigned ResIdx) const
LLVM_ABI void bumpCycle(unsigned NextCycle)
Move the boundary of scheduled code by one cycle.
unsigned getCurrMOps() const
Micro-ops issued in the current cycle.
unsigned getCurrCycle() const
Number of cycles to issue the instructions scheduled in this zone.
std::unique_ptr< ScheduleHazardRecognizer > HazardRec
LLVM_ABI bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
LLVM_ABI std::pair< unsigned, unsigned > getNextResourceCycle(const MCSchedClassDesc *SC, unsigned PIdx, unsigned ReleaseAtCycle, unsigned AcquireAtCycle)
Compute the next cycle at which the given processor resource can be scheduled.
LLVM_ABI void dumpScheduledState() const
LLVM_ABI void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
unsigned getZoneCritResIdx() const
unsigned getUnscheduledLatency(SUnit *SU) const
Compute the values of each DAG node for various metrics during DFS.
Definition ScheduleDFS.h:65
A ScheduleDAG for scheduling lists of MachineInstr.
ScheduleDAGInstrs(MachineFunction &mf, const MachineLoopInfo *mli, bool RemoveKillFlags=false)
const MachineLoopInfo * MLI
bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
VReg2SUnitMultiMap VRegUses
Maps vregs to the SUnits of their uses in the current scheduling region.
PressureDiff & getPressureDiff(const SUnit *SU)
SchedDFSResult * DFSResult
Information about DAG subtrees.
RegPressureTracker BotRPTracker
std::vector< PressureChange > RegionCriticalPSets
List of pressure sets that exceed the target's pressure limit before scheduling, listed in increasing...
IntervalPressure TopPressure
The top of the unscheduled zone.
const RegPressureTracker & getBotRPTracker() const
ScheduleDAGMILive(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
IntervalPressure BotPressure
The bottom of the unscheduled zone.
bool isTrackingPressure() const
Return true if register pressure tracking is enabled.
bool hasVRegLiveness() const override
Return true if this DAG supports VReg liveness and RegPressure.
RegisterClassInfo * RegClassInfo
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
const PressureDiff & getPressureDiff(const SUnit *SU) const
const RegPressureTracker & getTopRPTracker() const
RegPressureTracker RPTracker
bool ShouldTrackPressure
Register pressure in this region computed by initRegPressure.
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
const IntervalPressure & getBotPressure() const
Get current register pressure for the bottom scheduled instructions.
MachineBasicBlock::iterator LiveRegionEnd
const IntervalPressure & getTopPressure() const
Get current register pressure for the top scheduled instructions.
const std::vector< PressureChange > & getRegionCriticalPSets() const
IntervalPressure RegPressure
RegPressureTracker TopRPTracker
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
std::unique_ptr< MachineSchedStrategy > SchedImpl
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Add a postprocessing step to the DAG builder.
MachineBasicBlock::iterator top() const
AntiDepState AntiDep
State for optional post-RA anti-dependency breaking.
ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S, bool RemoveKillFlags)
MachineBasicBlock::iterator bottom() const
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
bool doMBBSchedRegionsTopDown() const override
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
virtual bool hasVRegLiveness() const
Return true if this DAG supports VReg liveness and RegPressure.
LiveIntervals * getLIS() const
ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S, bool RemoveKillFlags, TargetSubtargetInfo::AntiDepBreakMode AntiDepMode)
Construct a post-RA scheduler with the requested anti-dependency mode.
~ScheduleDAGMI() override
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
MachineBlockFrequencyInfo * MBFI
std::vector< std::unique_ptr< ScheduleDAGMutation > > Mutations
Ordered list of DAG postprocessing steps.
const TargetInstrInfo * TII
Target instruction information.
MachineFunction & MF
Machine function.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Represent a constant reference to a string, i.e.
Definition StringRef.h:56
Primary interface to the complete machine description for the target machine.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Provide an instruction scheduling machine model to CodeGen passes.
TargetSubtargetInfo - Generic base class for all target subtargets.
enum { ANTIDEP_NONE, ANTIDEP_CRITICAL, ANTIDEP_ALL } AntiDepBreakMode
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition Twine.h:82
Impl class for MachineScheduler.
Impl class for PostMachineScheduler.
Impl class for SSAMachineScheduler.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI int biasPhysReg(const SUnit *SU, bool isTop, bool BiasPRegsExtra=false)
Minimize physical register live ranges.
ScheduleDAGMILive * createSchedLive(MachineSchedContext *C)
Create the standard converging machine scheduler.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
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:1781
LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop)
LLVM_ABI bool shouldVerifyScheduling(const MachineFunction &MF)
Returns whether -verify-misched is set.
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, bool ReorderWhileClustering=false)
If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...
LLVM_ABI TargetSubtargetInfo::AntiDepBreakMode getPostRABreakAntiDeps()
Returns -misched-postra-break-antideps.
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, bool ReorderWhileClustering=false)
If ReorderWhileClustering is set to true, no attempt will be made to reduce reordering due to store c...
LLVM_ABI bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
SparseMultiSet< VReg2SUnit, Register, VirtReg2IndexFunctor > VReg2SUnitMultiMap
Track local uses of virtual registers.
ScheduleDAGMI * createSchedPostRA(MachineSchedContext *C)
Create a generic scheduler with no vreg liveness or DAG mutation passes.
LLVM_ABI bool shouldPrintMISchedDAGs(const MachineFunction &MF)
Return -misched-print-dags, which is false in a build without assertions.
LLVM_ABI bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
@ Other
Any other memory.
Definition ModRef.h:68
LLVM_ABI MISched::Direction getPreRADirection(const MachineFunction &MF)
Returns -misched-prera-direction.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
Definition InstrProf.h:145
LLVM_ABI bool tryBiasPhysRegs(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary *Zone, bool BiasPRegsExtra)
LLVM_ABI std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII)
LLVM_ABI bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
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:1933
LLVM_ABI unsigned computeRemLatency(SchedBoundary &CurrZone)
Compute remaining latency.
LLVM_ABI bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
Return true if this heuristic determines order.
@ End
Run the machine verifier once, at the end of the pipeline.
Definition CodeGen.h:320
LLVM_ABI bool shouldViewMISchedDAGs(const MachineFunction &MF)
Return -misched-view-dags, which is false in a build without assertions.
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
#define N
Policy for scheduling the next instruction in the candidate's zone.
bool operator==(const CandPolicy &RHS) const
bool operator!=(const CandPolicy &RHS) const
Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...
void reset(const CandPolicy &NewPolicy)
LLVM_ABI void initResourceDelta(const ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
Status of an instruction's critical resource consumption.
bool operator!=(const SchedResourceDelta &RHS) const
bool operator==(const SchedResourceDelta &RHS) const
RegisterPressure computed within a region of instructions delimited by TopIdx and BottomIdx.
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition MCSchedule.h:124
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
RegisterClassInfo * RegClassInfo
MachineBlockFrequencyInfo * MBFI
const MachineLoopInfo * MLI
const TargetMachine * TM
MachineSchedContext & operator=(const MachineSchedContext &other)=delete
MachineSchedContext(const MachineSchedContext &other)=delete
Define a generic scheduling policy for targets that don't provide their own MachineSchedStrategy.
bool ShouldTrackLaneMasks
Track LaneMasks to allow reordering of independent subregister writes of the same vreg.
A CRTP mix-in for passes that can be skipped.
Store the effects of a change in pressure on things that MI scheduler cares about.
MachineBasicBlock::iterator RegionBegin
RegionBegin is the first instruction in the scheduling region, and RegionEnd is either MBB->end() or ...
MachineBasicBlock::iterator RegionEnd
SchedRegion(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E, unsigned N)
Summarize the unscheduled region.
LLVM_ABI void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel)
SmallVector< unsigned, 16 > RemainingCounts