75 #ifndef LLVM_CODEGEN_MACHINESCHEDULER_H 76 #define LLVM_CODEGEN_MACHINESCHEDULER_H 106 class MachineDominatorTree;
107 class MachineFunction;
109 class MachineLoopInfo;
110 class RegisterClassInfo;
111 class SchedDFSResult;
112 class ScheduleHazardRecognizer;
113 class TargetInstrInfo;
114 class TargetPassConfig;
115 class TargetRegisterInfo;
137 ScheduleDAGInstrs *(*)(MachineSchedContext *)> {
175 bool ShouldTrackPressure =
false;
178 bool ShouldTrackLaneMasks =
false;
182 bool OnlyTopDown =
false;
183 bool OnlyBottomUp =
false;
187 bool DisableLatencyHeuristic =
false;
198 virtual void anchor();
206 unsigned NumRegionInstrs) {}
240 virtual SUnit *pickNode(
bool &IsTopNode) = 0;
247 virtual void schedNode(
SUnit *SU,
bool IsTopNode) = 0;
251 virtual void releaseTopNode(
SUnit *SU) = 0;
255 virtual void releaseBottomNode(
SUnit *SU) = 0;
273 std::vector<std::unique_ptr<ScheduleDAGMutation>>
Mutations;
282 const SUnit *NextClusterPred =
nullptr;
283 const SUnit *NextClusterSucc =
nullptr;
288 unsigned NumInstrsScheduled = 0;
293 bool RemoveKillFlags)
295 LIS(C->LIS), SchedImpl(
std::move(S)), Topo(SUnits, &ExitSU) {}
304 return SchedImpl->doMBBSchedRegionsTopDown();
320 Mutations.push_back(std::move(Mutation));
325 bool canAddEdge(
SUnit *SuccSU,
SUnit *PredSU);
343 unsigned regioninstrs)
override;
347 void schedule()
override;
350 void finishBlock()
override;
361 void viewGraph()
override;
368 void postprocessDAG();
374 void updateQueues(
SUnit *SU,
bool IsTopNode);
377 void placeDebugValues();
380 void dumpSchedule()
const;
383 bool checkSchedLimit();
388 void releaseSucc(
SUnit *SU,
SDep *SuccEdge);
389 void releaseSuccessors(
SUnit *SU);
390 void releasePred(
SUnit *SU,
SDep *PredEdge);
391 void releasePredecessors(
SUnit *SU);
416 bool ShouldTrackPressure =
false;
417 bool ShouldTrackLaneMasks =
false;
436 bool DisconnectedComponentsRenamed =
false;
440 std::unique_ptr<MachineSchedStrategy> S)
442 RegClassInfo(C->RegClassInfo), RPTracker(RegPressure),
443 TopRPTracker(TopPressure), BotRPTracker(BotPressure) {}
465 return RegionCriticalPSets;
469 return SUPressureDiffs[SU->
NodeNum];
472 return SUPressureDiffs[SU->
NodeNum];
477 void computeDFSResult();
490 unsigned regioninstrs)
override;
494 void schedule()
override;
497 unsigned computeCyclicCriticalPath();
499 void dump()
const override;
508 void buildDAGWithRegPressure();
515 void scheduleMI(
SUnit *SU,
bool IsTopNode);
519 void initRegPressure();
523 void updateScheduledPressure(
const SUnit *SU,
524 const std::vector<unsigned> &NewMaxPressure);
526 void collectVRegUses(
SUnit &SU);
545 std::vector<SUnit*> Queue;
557 bool empty()
const {
return Queue.empty(); }
561 unsigned size()
const {
return Queue.size(); }
579 (*I)->NodeQueueId &= ~ID;
581 unsigned idx =
I - Queue.begin();
583 return Queue.begin() + idx;
609 IsAcyclicLatencyLimited =
false;
610 RemainingCounts.
clear();
651 unsigned MinReadyCycle;
654 unsigned ExpectedLatency;
659 unsigned DependentLatency;
663 unsigned RetiredMOps;
673 unsigned MaxExecutedResCount;
676 unsigned ZoneCritResIdx;
679 bool IsResourceLimited;
688 unsigned MaxObservedStall;
695 Available(ID, Name+
".A"), Pending(ID << LogMaxQID, Name+
".P") {
707 return Available.
getID() == TopQID;
723 return std::max(ExpectedLatency, CurrCycle);
731 return ExecutedResCounts[ResIdx];
739 return getResourceCount(ZoneCritResIdx);
747 MaxExecutedResCount);
757 unsigned getLatencyStallCycles(
SUnit *SU);
759 unsigned getNextResourceCycle(
unsigned PIdx,
unsigned Cycles);
761 bool checkHazard(
SUnit *SU);
765 unsigned getOtherResourceCount(
unsigned &OtherCritIdx);
767 void releaseNode(
SUnit *SU,
unsigned ReadyCycle);
769 void bumpCycle(
unsigned NextCycle);
771 void incExecutedResources(
unsigned PIdx,
unsigned Count);
773 unsigned countResource(
unsigned PIdx,
unsigned Cycles,
unsigned ReadyCycle);
775 void bumpNode(
SUnit *SU);
777 void releasePending();
779 void removeReady(
SUnit *SU);
784 SUnit *pickOnlyChoice();
786 void dumpScheduledState()
const;
797 NoCand, Only1, PhysReg, RegExcess, RegCritical, Stall, Cluster,
Weak,
807 bool ReduceLatency =
false;
808 unsigned ReduceResIdx = 0;
809 unsigned DemandResIdx = 0;
819 return !(*
this == RHS);
826 unsigned CritResources = 0;
829 unsigned DemandedResources = 0;
908 bool ComputeRemLatency,
unsigned &RemLatency)
const;
912 bool tryLess(
int TryVal,
int CandVal,
943 unsigned NumRegionInstrs)
override;
945 void dumpPolicy()
const override;
948 return RegionPolicy.ShouldTrackPressure;
952 return RegionPolicy.ShouldTrackLaneMasks;
957 SUnit *pickNode(
bool &IsTopNode)
override;
959 void schedNode(
SUnit *SU,
bool IsTopNode)
override;
966 TopCand.SU =
nullptr;
974 BotCand.SU =
nullptr;
977 void registerRoots()
override;
993 void checkAcyclicLatency();
1002 SUnit *pickNodeBidirectional(
bool &IsTopNode);
1009 void reschedulePhysReg(
SUnit *SU,
bool isTop);
1030 unsigned NumRegionInstrs)
override {
1039 void registerRoots()
override;
1041 SUnit *pickNode(
bool &IsTopNode)
override;
1047 void schedNode(
SUnit *SU,
bool IsTopNode)
override;
1074 std::unique_ptr<ScheduleDAGMutation>
1078 std::unique_ptr<ScheduleDAGMutation>
1082 std::unique_ptr<ScheduleDAGMutation>
1088 #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)
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
amdgpu Simplify well known AMD library false Value Value const Twine & Name
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.