74 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H 75 #define LLVM_CODEGEN_MACHINESCHEDULER_H 105 class MachineDominatorTree;
106 class MachineFunction;
108 class MachineLoopInfo;
109 class RegisterClassInfo;
110 class SchedDFSResult;
111 class ScheduleHazardRecognizer;
112 class TargetInstrInfo;
113 class TargetPassConfig;
114 class TargetRegisterInfo;
136 ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
174 bool ShouldTrackPressure =
false;
177 bool ShouldTrackLaneMasks =
false;
181 bool OnlyTopDown =
false;
182 bool OnlyBottomUp =
false;
186 bool DisableLatencyHeuristic =
false;
197 virtual void anchor();
205 unsigned NumRegionInstrs) {}
239 virtual SUnit *pickNode(
bool &IsTopNode) = 0;
246 virtual void schedNode(
SUnit *SU,
bool IsTopNode) = 0;
250 virtual void releaseTopNode(
SUnit *SU) = 0;
254 virtual void releaseBottomNode(
SUnit *SU) = 0;
272 std::vector<std::unique_ptr<ScheduleDAGMutation>>
Mutations;
281 const SUnit *NextClusterPred =
nullptr;
282 const SUnit *NextClusterSucc =
nullptr;
287 unsigned NumInstrsScheduled = 0;
292 bool RemoveKillFlags)
294 LIS(C->LIS), SchedImpl(
std::move(S)), Topo(SUnits, &ExitSU) {}
303 return SchedImpl->doMBBSchedRegionsTopDown();
319 Mutations.push_back(std::move(Mutation));
324 bool canAddEdge(
SUnit *SuccSU,
SUnit *PredSU);
342 unsigned regioninstrs)
override;
346 void schedule()
override;
349 void finishBlock()
override;
360 void viewGraph()
override;
367 void postprocessDAG();
373 void updateQueues(
SUnit *SU,
bool IsTopNode);
376 void placeDebugValues();
379 void dumpSchedule()
const;
382 bool checkSchedLimit();
387 void releaseSucc(
SUnit *SU,
SDep *SuccEdge);
388 void releaseSuccessors(
SUnit *SU);
389 void releasePred(
SUnit *SU,
SDep *PredEdge);
390 void releasePredecessors(
SUnit *SU);
415 bool ShouldTrackPressure =
false;
416 bool ShouldTrackLaneMasks =
false;
435 bool DisconnectedComponentsRenamed =
false;
439 std::unique_ptr<MachineSchedStrategy> S)
441 RegClassInfo(C->RegClassInfo), RPTracker(RegPressure),
442 TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
464 return RegionCriticalPSets;
468 return SUPressureDiffs[SU->
NodeNum];
471 return SUPressureDiffs[SU->
NodeNum];
476 void computeDFSResult();
489 unsigned regioninstrs)
override;
493 void schedule()
override;
496 unsigned computeCyclicCriticalPath();
498 void dump()
const override;
507 void buildDAGWithRegPressure();
514 void scheduleMI(
SUnit *SU,
bool IsTopNode);
518 void initRegPressure();
522 void updateScheduledPressure(
const SUnit *SU,
523 const std::vector<unsigned> &NewMaxPressure);
525 void collectVRegUses(
SUnit &SU);
544 std::vector<SUnit*> Queue;
556 bool empty()
const {
return Queue.empty(); }
560 unsigned size()
const {
return Queue.size(); }
578 (*I)->NodeQueueId &= ~ID;
580 unsigned idx =
I - Queue.begin();
582 return Queue.begin() + idx;
608 IsAcyclicLatencyLimited =
false;
609 RemainingCounts.
clear();
650 unsigned MinReadyCycle;
653 unsigned ExpectedLatency;
658 unsigned DependentLatency;
662 unsigned RetiredMOps;
672 unsigned MaxExecutedResCount;
675 unsigned ZoneCritResIdx;
678 bool IsResourceLimited;
687 unsigned MaxObservedStall;
694 Available(ID, Name+
".A"), Pending(ID << LogMaxQID, Name+
".P") {
706 return Available.
getID() == TopQID;
722 return std::max(ExpectedLatency, CurrCycle);
730 return ExecutedResCounts[ResIdx];
738 return getResourceCount(ZoneCritResIdx);
746 MaxExecutedResCount);
756 unsigned getLatencyStallCycles(
SUnit *SU);
758 unsigned getNextResourceCycle(
unsigned PIdx,
unsigned Cycles);
760 bool checkHazard(
SUnit *SU);
764 unsigned getOtherResourceCount(
unsigned &OtherCritIdx);
766 void releaseNode(
SUnit *SU,
unsigned ReadyCycle);
768 void bumpCycle(
unsigned NextCycle);
770 void incExecutedResources(
unsigned PIdx,
unsigned Count);
772 unsigned countResource(
unsigned PIdx,
unsigned Cycles,
unsigned ReadyCycle);
774 void bumpNode(
SUnit *SU);
776 void releasePending();
778 void removeReady(
SUnit *SU);
783 SUnit *pickOnlyChoice();
785 void dumpScheduledState()
const;
796 NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster,
Weak,
806 bool ReduceLatency =
false;
807 unsigned ReduceResIdx = 0;
808 unsigned DemandResIdx = 0;
818 return !(*
this == RHS);
825 unsigned CritResources = 0;
828 unsigned DemandedResources = 0;
907 bool ComputeRemLatency,
unsigned &RemLatency)
const;
911 bool tryLess(
int TryVal,
int CandVal,
942 unsigned NumRegionInstrs)
override;
944 void dumpPolicy()
const override;
947 return RegionPolicy.ShouldTrackPressure;
951 return RegionPolicy.ShouldTrackLaneMasks;
956 SUnit *pickNode(
bool &IsTopNode)
override;
958 void schedNode(
SUnit *SU,
bool IsTopNode)
override;
965 TopCand.SU =
nullptr;
973 BotCand.SU =
nullptr;
976 void registerRoots()
override;
992 void checkAcyclicLatency();
1001 SUnit *pickNodeBidirectional(
bool &IsTopNode);
1008 void reschedulePhysReg(
SUnit *SU,
bool isTop);
1029 unsigned NumRegionInstrs)
override {
1038 void registerRoots()
override;
1040 SUnit *pickNode(
bool &IsTopNode)
override;
1046 void schedNode(
SUnit *SU,
bool IsTopNode)
override;
1073 std::unique_ptr<ScheduleDAGMutation>
1077 std::unique_ptr<ScheduleDAGMutation>
1081 std::unique_ptr<ScheduleDAGMutation>
1087 #endif // LLVM_CODEGEN_MACHINESCHEDULER_H unsigned getCriticalCount() const
Get the scaled count of scheduled micro-ops and resources, including executed resources.
VReg2SUnitMultiMap VRegUses
Maps vregs to the SUnits of their uses in the current scheduling region.
void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs) override
Optionally override the per-region scheduling policy.
int biasPhysReg(const SUnit *SU, bool isTop)
Minimize physical register live ranges.
const_iterator end(StringRef path)
Get end iterator over path.
unsigned getZoneCritResIdx() const
Base class for GenericScheduler.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
static MachinePassRegistry< ScheduleDAGCtor > Registry
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
virtual ~MachineSchedContext()
Each Scheduling boundary is associated with ready queues.
PostGenericScheduler - Interface to the scheduling algorithm used by ScheduleDAGMI.
GenericSchedulerBase(const MachineSchedContext *C)
This class represents lattice values for constants.
const MachineSchedContext * Context
void Remove(MachinePassRegistryNode< PassCtorTy > *Node)
Remove - Removes a function pass from the registration list.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries...
ScheduleDAGMI(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S, bool RemoveKillFlags)
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
const MachineLoopInfo * MLI
void push_back(const T &Elt)
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling...
unsigned getCurrCycle() const
Number of cycles to issue the instructions scheduled in this zone.
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...
unsigned DemandedResources
bool isInQueue(SUnit *SU) const
ScheduleDAGMI * createGenericSchedPostRA(MachineSchedContext *C)
Create a generic scheduler with no vreg liveness or DAG mutation passes.
const IntervalPressure & getBotPressure() const
Get current register pressure for the bottom scheduled instructions.
MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
unsigned getUnscheduledLatency(SUnit *SU) const
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
unsigned getDependentLatency() const
unsigned const TargetRegisterInfo * TRI
Summarize the unscheduled region.
void reset(const CandPolicy &NewPolicy)
const SchedDFSResult * getDFSResult() const
Return a non-null DFS result if the scheduling strategy initialized it.
MachineSchedRegistry provides a selection of available machine instruction schedulers.
RegisterClassInfo * RegClassInfo
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
std::unique_ptr< MachineSchedStrategy > SchedImpl
unsigned BotReadyCycle
Cycle relative to end when node is ready.
bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, SchedBoundary &Zone)
ScheduleDAGMILive is an implementation of ScheduleDAGInstrs that schedules machine instructions while...
virtual bool hasVRegLiveness() const
Return true if this DAG supports VReg liveness and RegPressure.
bool isScheduled
True once scheduled.
ArrayRef< SUnit * > elements()
const RegPressureTracker & getBotRPTracker() const
BitVector & getScheduledTrees()
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Provide an instruction scheduling machine model to CodeGen passes.
const HexagonInstrInfo * TII
const TargetPassConfig * PassConfig
virtual void dumpPolicy() const
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
StringRef getName() const
void scheduleTree(unsigned SubtreeID) override
Scheduler callback to notify that a new subtree is scheduled.
PressureDiff & getPressureDiff(const SUnit *SU)
std::vector< std::unique_ptr< ScheduleDAGMutation > > Mutations
Ordered list of DAG postprocessing steps.
void setListener(MachinePassRegistryListener< PassCtorTy > *L)
Target-Independent Code Generator Pass Configuration Options.
bool IsAcyclicLatencyLimited
bool shouldTrackLaneMasks() const override
Returns true if lanemasks should be tracked.
static MachineSchedRegistry * getList()
static const char * getReasonStr(SIScheduleCandReason Reason)
Compute the values of each DAG node for various metrics during DFS.
unsigned TopReadyCycle
Cycle relative to start when node is ready.
MachineBasicBlock::iterator LiveRegionEnd
RegPressureTracker BotRPTracker
MachineBasicBlock::iterator top() const
MachineSchedPolicy RegionPolicy
std::vector< PressureChange > RegionCriticalPSets
List of pressure sets that exceed the target's pressure limit before scheduling, listed in increasing...
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
virtual void initPolicy(MachineBasicBlock::iterator Begin, MachineBasicBlock::iterator End, unsigned NumRegionInstrs)
Optionally override the per-region scheduling policy.
bool doMBBSchedRegionsTopDown() const override
If this method returns true, handling of the scheduling regions themselves (in case of a scheduling b...
ScheduleDAGMILive * createGenericSchedLive(MachineSchedContext *C)
Create the standard converging machine scheduler.
std::vector< SUnit * >::iterator iterator
unsigned getCurrMOps() const
Micro-ops issued in the current cycle.
const SUnit * getNextClusterSucc() const
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
TargetInstrInfo - Interface to description of machine instruction set.
virtual void registerRoots()
Notify this strategy that all roots have been released (including those that depend on EntrySU or Exi...
SchedCandidate(const CandPolicy &Policy)
RegisterClassInfo * RegClassInfo
static void setListener(MachinePassRegistryListener< FunctionPassCtor > *L)
initializer< Ty > init(const Ty &Val)
CandReason
Represent the type of SchedCandidate found within a single queue.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Helpers for implementing custom MachineSchedStrategy classes.
RegisterPressure computed within a region of instructions delimited by TopIdx and BottomIdx...
HazardRecognizer - This determines whether or not an instruction can be issued this cycle...
bool tryGreater(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
virtual void enterMBB(MachineBasicBlock *MBB)
Tell the strategy that MBB is about to be processed.
unsigned getLatencyFactor() const
Multiply cycle count by this factor to normalize it relative to other resources.
void Add(MachinePassRegistryNode< PassCtorTy > *Node)
Add - Adds a function pass to the registration list.
bool operator!=(const CandPolicy &RHS) const
Store the state used by GenericScheduler heuristics, required for the lifetime of one invocation of p...
Track the current register pressure at some position in the instruction stream, and remember the high...
Policy for scheduling the next instruction in the candidate's zone.
unsigned getScheduledLatency() const
Get the number of latency cycles "covered" by the scheduled instructions.
List of PressureChanges in order of increasing, unique PSetID.
MachinePassRegistryNode< PassCtorTy > * getList()
SchedResourceDelta ResDelta
ScheduleDAGInstrs *(*)(MachineSchedContext *) ScheduleDAGCtor
std::unique_ptr< ScheduleDAGMutation > createStoreClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
PressureDiffs SUPressureDiffs
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
unsigned getWeakLeft(const SUnit *SU, bool isTop)
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
SchedBoundary(unsigned ID, const Twine &Name)
Pending queues extend the ready queues with the same ID and the PendingFlag set.
std::unique_ptr< ScheduleDAGMutation > createLoadClusterDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
bool operator==(const SchedResourceDelta &RHS) const
GenericScheduler shrinks the unscheduled zone using heuristics to balance the schedule.
bool shouldTrackPressure() const override
Check if pressure tracking is needed before building the DAG and initializing this strategy...
void releaseNode(SUnit *SU, unsigned ReadyCycle)
unsigned getMicroOpFactor() const
Multiply number of micro-ops by this factor to normalize it relative to other resources.
bool hasVRegLiveness() const override
Return true if this DAG supports VReg liveness and RegPressure.
const RegPressureTracker & getTopRPTracker() const
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isResourceLimited() const
std::unique_ptr< ScheduleDAGMutation > createCopyConstrainDAGMutation(const TargetInstrInfo *TII, const TargetRegisterInfo *TRI)
unsigned getResourceCount(unsigned ResIdx) const
PostGenericScheduler(const MachineSchedContext *C)
bool tryLess(int TryVal, int CandVal, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason)
Return true if this heuristic determines order.
ReadyQueue(unsigned id, const Twine &name)
unsigned getExecutedCount() const
Get a scaled count for the minimum execution time of the scheduled micro-ops that are ready to execut...
static void initialize(TargetLibraryInfoImpl &TLI, const Triple &T, ArrayRef< StringRef > StandardNames)
Initialize the set of available library functions based on the specified target triple.
virtual bool shouldTrackPressure() const
Check if pressure tracking is needed before building the DAG and initializing this strategy...
const IntervalPressure & getTopPressure() const
Get current register pressure for the top scheduled instructions.
ScheduleDAGMILive(MachineSchedContext *C, std::unique_ptr< MachineSchedStrategy > S)
const PressureDiff & getPressureDiff(const SUnit *SU) const
virtual void scheduleTree(unsigned SubtreeID)
Scheduler callback to notify that a new subtree is scheduled.
unsigned NodeQueueId
Queue id of node.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
A ScheduleDAG for scheduling lists of MachineInstr.
Define a generic scheduling policy for targets that don't provide their own MachineSchedStrategy.
Representation of each machine instruction.
const MachineDominatorTree * MDT
Status of an instruction's critical resource consumption.
GenericScheduler(const MachineSchedContext *C)
LiveIntervals * getLIS() const
bool shouldTrackPressure() const override
PostRA scheduling does not track pressure.
SchedCandidate BotCand
Candidate last picked from Bot boundary.
cl::opt< bool > ForceBottomUp
virtual void leaveMBB()
Tell the strategy that current MBB is done.
MachineBasicBlock::iterator bottom() const
bool operator!=(const SchedResourceDelta &RHS) const
MachinePassRegistryNode * getNext() const
MachineSchedContext provides enough context from the MachineScheduler pass for the target to instanti...
MachineSchedStrategy - Interface to the scheduling algorithm used by ScheduleDAGMI.
MachinePassRegistryNode - Machine pass node stored in registration list.
Capture a change in pressure for a single pressure set.
SmallVector< unsigned, 16 > RemainingCounts
const SUnit * getNextClusterPred() const
IntervalPressure TopPressure
The top of the unscheduled zone.
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling...
unsigned NodeNum
Entry # of node in the node vector.
const std::vector< PressureChange > & getRegionCriticalPSets() const
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
bool tryPressure(const PressureChange &TryP, const PressureChange &CandP, GenericSchedulerBase::SchedCandidate &TryCand, GenericSchedulerBase::SchedCandidate &Cand, GenericSchedulerBase::CandReason Reason, const TargetRegisterInfo *TRI, const MachineFunction &MF)
Store the effects of a change in pressure on things that MI scheduler cares about.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
MachineSchedRegistry * getNext() const
bool operator==(const CandPolicy &RHS) const
bool isTrackingPressure() const
Return true if register pressure tracking is enabled.
virtual bool doMBBSchedRegionsTopDown() const
SchedCandidate TopCand
Candidate last picked from Top boundary.
IntervalPressure RegPressure
virtual bool shouldTrackLaneMasks() const
Returns true if lanemasks should be tracked.
StringRef - Represent a constant reference to a string, i.e.
bool operator==(uint64_t V1, const APInt &V2)
IntervalPressure BotPressure
The bottom of the unscheduled zone.
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
RegPressureTracker TopRPTracker
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
RegPressureTracker RPTracker
void setBest(SchedCandidate &Best)
ScheduleDAGCtor FunctionPassCtor
Scheduling unit. This is a node in the scheduling DAG.
void addMutation(std::unique_ptr< ScheduleDAGMutation > Mutation)
Add a postprocessing step to the DAG builder.
cl::opt< bool > ForceTopDown
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.