42#define DEBUG_TYPE "machine-scheduler"
63 cl::desc(
"High register pressure threhold."));
67 :
TII(STI.getInstrInfo()), SchedModel(SM) {
88 if (SUd->
Succs.size() == 0)
91 for (
const auto &S : SUd->
Succs) {
97 if (S.getSUnit() == SUu && S.getLatency() > 0)
119 case TargetOpcode::EXTRACT_SUBREG:
120 case TargetOpcode::INSERT_SUBREG:
121 case TargetOpcode::SUBREG_TO_REG:
122 case TargetOpcode::REG_SEQUENCE:
123 case TargetOpcode::IMPLICIT_DEF:
124 case TargetOpcode::COPY:
125 case TargetOpcode::INLINEASM:
126 case TargetOpcode::INLINEASM_BR:
146 bool startNewCycle =
false;
159 startNewCycle =
true;
166 case TargetOpcode::EXTRACT_SUBREG:
167 case TargetOpcode::INSERT_SUBREG:
168 case TargetOpcode::SUBREG_TO_REG:
169 case TargetOpcode::REG_SEQUENCE:
170 case TargetOpcode::IMPLICIT_DEF:
171 case TargetOpcode::KILL:
172 case TargetOpcode::CFI_INSTRUCTION:
173 case TargetOpcode::EH_LABEL:
174 case TargetOpcode::COPY:
175 case TargetOpcode::INLINEASM:
176 case TargetOpcode::INLINEASM_BR:
183 for (
unsigned i = 0, e =
Packet.size(); i != e; ++i) {
190 return startNewCycle;
223 if (SU.getHeight() > maxH)
224 maxH = SU.getHeight();
225 dbgs() <<
"Max Height " << maxH <<
"\n";
230 if (SU.getDepth() > maxD)
231 maxD = SU.getDepth();
232 dbgs() <<
"Max Depth " << maxD <<
"\n";
240 bool IsTopNode =
false;
243 dbgs() <<
"** VLIWMachineScheduler::schedule picking next node\n");
263 dbgs() <<
"*** Final schedule for "
292 const std::vector<unsigned> &MaxPressure =
295 for (
unsigned i = 0, e = MaxPressure.size(); i < e; ++i) {
298 ((float)MaxPressure[i] > ((
float)Limit *
RPThreshold));
327 unsigned SuccReadyCycle =
I->getSUnit()->BotReadyCycle;
328 unsigned MinLatency =
I->getLatency();
359 if (HazardRec->isEnabled())
370 SUnit *SU,
unsigned ReadyCycle) {
371 if (ReadyCycle < MinReadyCycle)
372 MinReadyCycle = ReadyCycle;
376 if (ReadyCycle > CurrCycle || checkHazard(SU))
386 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
388 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
389 "MinReadyCycle uninitialized");
390 unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
392 if (!HazardRec->isEnabled()) {
394 CurrCycle = NextCycle;
397 for (; CurrCycle != NextCycle; ++CurrCycle) {
399 HazardRec->AdvanceCycle();
401 HazardRec->RecedeCycle();
407 << CurrCycle <<
'\n');
412 bool startNewCycle =
false;
415 if (HazardRec->isEnabled()) {
416 if (!isTop() && SU->
isCall) {
421 HazardRec->EmitInstruction(SU);
425 startNewCycle = ResourceModel->reserveResources(SU, isTop());
431 LLVM_DEBUG(
dbgs() <<
"*** Max instrs at cycle " << CurrCycle <<
'\n');
434 LLVM_DEBUG(
dbgs() <<
"*** IssueCount " << IssueCount <<
" at cycle "
435 << CurrCycle <<
'\n');
443 MinReadyCycle = std::numeric_limits<unsigned>::max();
447 for (
unsigned i = 0, e = Pending.size(); i != e; ++i) {
448 SUnit *SU = *(Pending.begin() + i);
451 if (ReadyCycle < MinReadyCycle)
452 MinReadyCycle = ReadyCycle;
454 if (ReadyCycle > CurrCycle)
461 Pending.remove(Pending.begin() + i);
465 CheckPending =
false;
473 assert(Pending.isInQueue(SU) &&
"bad ready count");
474 Pending.remove(Pending.find(SU));
485 auto AdvanceCycle = [
this]() {
488 if (
Available.size() == 1 && Pending.size() > 0)
489 return !ResourceModel->isResourceAvailable(*
Available.begin(), isTop()) ||
493 for (
unsigned i = 0; AdvanceCycle(); ++i) {
494 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
497 ResourceModel->reserveResources(
nullptr, isTop());
513 <<
P.getUnitInc() <<
" ";
532 std::stringstream dbgstr;
533 dbgstr <<
"SU(" << std::setw(3) << (*I)->NodeNum <<
")";
534 dbgs() << dbgstr.str();
537 (*I)->getInstr()->dump();
549 for (
auto &Pred : SU->
Preds) {
551 if (!Pred.getSUnit()->isScheduled && (Pred.getSUnit() != SU2))
564 for (
auto &Succ : SU->
Succs) {
566 if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
579 for (
const auto &
P : PD) {
586 return (isBotUp ?
P.getUnitInc() : -
P.getUnitInc());
612 unsigned IsAvailableAmt = 0;
621 std::stringstream dbgstr;
622 dbgstr <<
"h" << std::setw(3) << SU->
getHeight() <<
"|";
623 dbgs() << dbgstr.str();
630 ResCount += IsAvailableAmt;
641 std::stringstream dbgstr;
642 dbgstr <<
"d" << std::setw(3) << SU->
getDepth() <<
"|";
643 dbgs() << dbgstr.str();
650 ResCount += IsAvailableAmt;
656 unsigned NumNodesBlocking = 0;
673 ResCount += (NumNodesBlocking *
ScaleTwo);
676 std::stringstream dbgstr;
677 dbgstr <<
"blk " << std::setw(2) << NumNodesBlocking <<
")|";
678 dbgs() << dbgstr.str();
696 ResCount -= IsAvailableAmt;
717 if (!SI.getSUnit()->getInstr()->isPseudo() && SI.isAssignedRegDep() &&
718 SI.getLatency() == 0 &&
733 for (
const auto &PI : SU->
Preds) {
734 if (PI.getLatency() > 0 &&
741 for (
const auto &SI : SU->
Succs) {
742 if (SI.getLatency() > 0 &&
752 std::stringstream dbgstr;
753 dbgstr <<
"Total " << std::setw(4) << ResCount <<
")";
754 dbgs() << dbgstr.str();
781 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
792 Candidate.
SCost = CurrentCost;
799 if (CurrentCost < 0 && Candidate.
SCost < 0) {
805 Candidate.
SCost = CurrentCost;
812 if (CurrentCost > Candidate.
SCost) {
816 Candidate.
SCost = CurrentCost;
824 if (CurrWeak != CandWeak) {
825 if (CurrWeak < CandWeak) {
829 Candidate.
SCost = CurrentCost;
830 FoundCandidate =
Weak;
836 unsigned CurrSize, CandSize;
838 CurrSize = (*I)->Succs.size();
839 CandSize = Candidate.
SU->
Succs.size();
841 CurrSize = (*I)->Preds.size();
842 CandSize = Candidate.
SU->
Preds.size();
844 if (CurrSize > CandSize) {
848 Candidate.
SCost = CurrentCost;
853 if (CurrSize != CandSize)
866 Candidate.
SCost = CurrentCost;
874 if (FoundCandidate ==
NoCand)
877 return FoundCandidate;
898 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
916 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
960 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
971 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
985 <<
" Scheduling instruction in cycle "
static const Function * getParent(const Value *V)
@ Available
We know the block is fully available. This is a fixpoint.
const HexagonInstrInfo * TII
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
static bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2)
isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor of SU, return true (we may have ...
static cl::opt< bool > CheckEarlyAvail("check-early-avail", cl::Hidden, cl::init(true))
static cl::opt< bool > IgnoreBBRegPressure("ignore-bb-reg-pressure", cl::Hidden, cl::init(false))
static cl::opt< float > RPThreshold("vliw-misched-reg-pressure", cl::Hidden, cl::init(0.75f), cl::desc("High register pressure threhold."))
static cl::opt< bool > UseNewerCandidate("use-newer-candidate", cl::Hidden, cl::init(true))
static bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2)
isSingleUnscheduledSucc - If SU2 is the only unscheduled successor of SU, return true (we may have du...
static cl::opt< unsigned > SchedDebugVerboseLevel("misched-verbose-level", cl::Hidden, cl::init(1))
VLIWMachineScheduler * DAG
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
static constexpr unsigned PriorityOne
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
virtual VLIWResourceModel * createVLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SchedModel) const
int pressureChange(const SUnit *SU, bool isBotUp)
Check if the instruction changes the register pressure of a register in the high pressure set.
SmallVector< bool > HighPressureSets
List of pressure sets that have a high pressure level in the region.
static constexpr unsigned ScaleTwo
CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
void readyQueueVerboseDump(const RegPressureTracker &RPTracker, SchedCandidate &Candidate, ReadyQueue &Q)
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
SUnit * pickNodeBidrectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
static constexpr unsigned PriorityTwo
static constexpr unsigned PriorityThree
const TargetSchedModel * SchedModel
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, SchedCandidate &Candidate, RegPressureDelta &Delta, bool verbose)
Single point to compute overall scheduling cost.
void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P=PressureChange())
CandResult
Represent the type of SchedCandidate found within a single queue.
bool canReserveResources(const MCInstrDesc *MID)
void reserveResources(const MCInstrDesc *MID)
Itinerary data supplied by a subtarget to be used by a target.
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
bool isPseudo(QueryType Type=IgnoreBundle) const
Return true if this is a pseudo instruction that doesn't correspond to a real machine instruction.
Capture a change in pressure for a single pressure set.
List of PressureChanges in order of increasing, unique PSetID.
Helpers for implementing custom MachineSchedStrategy classes.
std::vector< SUnit * >::iterator iterator
StringRef getName() const
Track the current register pressure at some position in the instruction stream, and remember the high...
void getMaxPressureDelta(const MachineInstr *MI, RegPressureDelta &Delta, ArrayRef< PressureChange > CriticalPSets, ArrayRef< unsigned > MaxPressureLimit)
Find the pressure set with the most change beyond its pressure limit after traversing this instructio...
unsigned getRegPressureSetLimit(unsigned Idx) const
Get the register unit limit for the given pressure set index.
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Scheduling unit. This is a node in the scheduling DAG.
bool isCall
Is a function call.
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...
bool isScheduleHigh
True if preferable to schedule high.
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.
SmallVector< SDep, 4 > Succs
All sunit successors.
bool isBottomReady() const
SmallVector< SDep, 4 > Preds
All sunit predecessors.
SmallVectorImpl< SDep >::iterator succ_iterator
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
MachineBasicBlock * BB
The block in which to insert instructions.
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
void dumpNode(const SUnit &SU) const override
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
const MachineLoopInfo * MLI
void scheduleMI(SUnit *SU, bool IsTopNode)
Move an instruction and update register pressure.
PressureDiff & getPressureDiff(const SUnit *SU)
void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
Release ExitSU predecessors and setup scheduler queues.
void buildDAGWithRegPressure()
Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.
const RegPressureTracker & getBotRPTracker() const
const RegPressureTracker & getTopRPTracker() const
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
void dump() const override
const std::vector< PressureChange > & getRegionCriticalPSets() const
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
void dumpSchedule() const
dump the scheduled Sequence.
std::unique_ptr< MachineSchedStrategy > SchedImpl
void postProcessDAG()
Apply each ScheduleDAGMutation step in order.
MachineBasicBlock::iterator top() const
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
MachineBasicBlock::iterator bottom() const
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
void viewGraph() override
Out-of-line implementation with no arguments is handy for gdb.
void updateQueues(SUnit *SU, bool IsTopNode)
Update scheduler DAG and queues after scheduling an instruction.
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
std::vector< SUnit > SUnits
The scheduling units.
const TargetRegisterInfo * TRI
Target processor register info.
MachineFunction & MF
Machine function.
void assign(size_type NumElts, ValueParamT Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
TargetInstrInfo - Interface to description of machine instruction set.
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
virtual const char * getRegPressureSetName(unsigned Idx) const =0
Get the name of this register unit pressure set.
Provide an instruction scheduling machine model to CodeGen passes.
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return the number of issue slots required for this MI.
const InstrItineraryData * getInstrItineraries() const
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetInstrInfo * getInstrInfo() const
Extend the standard ScheduleDAGMILive to provide more context and override the top-level schedule() d...
RegisterClassInfo * getRegClassInfo()
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it's time to do some work.
unsigned TotalPackets
Total packets created.
virtual ~VLIWResourceModel()
virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu)
Return true if there is a dependence between SUd and SUu.
virtual DFAPacketizer * createPacketizer(const TargetSubtargetInfo &STI) const
virtual bool reserveResources(SUnit *SU, bool IsTop)
Keep track of available resources.
bool isInPacket(SUnit *SU) const
DFAPacketizer * ResourcesModel
ResourcesModel - Represents VLIW state.
SmallVector< SUnit * > Packet
Local packet/bundle model.
const TargetSchedModel * SchedModel
VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
virtual bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned getWeakLeft(const SUnit *SU, bool isTop)
cl::opt< bool > ViewMISchedDAGs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
cl::opt< MISched::Direction > PreRADirection
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Store the state used by ConvergingVLIWScheduler heuristics, required for the lifetime of one invocati...
Each Scheduling boundary is associated with ready queues.
bool isLatencyBound(SUnit *SU)
void releaseNode(SUnit *SU, unsigned ReadyCycle)
void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
ScheduleHazardRecognizer * HazardRec
void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
VLIWResourceModel * ResourceModel
void releasePending()
Release pending ready nodes in to the available queue.
SUnit * pickOnlyChoice()
If this queue only has one ready candidate, return it.
void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel)
void bumpCycle()
Move the boundary of scheduled code by one cycle.
bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
Store the effects of a change in pressure on things that MI scheduler cares about.
PressureChange CriticalMax
PressureChange CurrentMax
std::vector< unsigned > MaxSetPressure
Map of max reg pressure indexed by pressure set ID, not class ID.