Go to the documentation of this file.
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:
133 for (
unsigned i = 0,
e =
Packet.size();
i !=
e; ++
i)
137 for (
unsigned i = 0,
e =
Packet.size();
i !=
e; ++
i)
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:
174 case TargetOpcode::COPY:
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) {
302 "-misched-topdown incompatible with -misched-bottomup");
330 unsigned SuccReadyCycle =
I->getSUnit()->BotReadyCycle;
331 unsigned MinLatency =
I->getLatency();
362 if (HazardRec->isEnabled())
373 SUnit *SU,
unsigned ReadyCycle) {
374 if (ReadyCycle < MinReadyCycle)
375 MinReadyCycle = ReadyCycle;
379 if (ReadyCycle > CurrCycle || checkHazard(SU))
389 IssueCount = (IssueCount <=
Width) ? 0 : IssueCount -
Width;
392 "MinReadyCycle uninitialized");
393 unsigned NextCycle =
std::max(CurrCycle + 1, MinReadyCycle);
395 if (!HazardRec->isEnabled()) {
397 CurrCycle = NextCycle;
400 for (; CurrCycle != NextCycle; ++CurrCycle) {
402 HazardRec->AdvanceCycle();
404 HazardRec->RecedeCycle();
410 << CurrCycle <<
'\n');
415 bool startNewCycle =
false;
418 if (HazardRec->isEnabled()) {
419 if (!isTop() && SU->
isCall) {
424 HazardRec->EmitInstruction(SU);
428 startNewCycle = ResourceModel->reserveResources(SU, isTop());
434 LLVM_DEBUG(
dbgs() <<
"*** Max instrs at cycle " << CurrCycle <<
'\n');
437 LLVM_DEBUG(
dbgs() <<
"*** IssueCount " << IssueCount <<
" at cycle "
438 << CurrCycle <<
'\n');
450 for (
unsigned i = 0,
e = Pending.size();
i !=
e; ++
i) {
451 SUnit *SU = *(Pending.begin() +
i);
454 if (ReadyCycle < MinReadyCycle)
455 MinReadyCycle = ReadyCycle;
457 if (ReadyCycle > CurrCycle)
464 Pending.remove(Pending.begin() +
i);
468 CheckPending =
false;
476 assert(Pending.isInQueue(SU) &&
"bad ready count");
477 Pending.remove(Pending.find(SU));
488 auto AdvanceCycle = [
this]() {
491 if (
Available.size() == 1 && Pending.size() > 0)
492 return !ResourceModel->isResourceAvailable(*
Available.begin(), isTop()) ||
496 for (
unsigned i = 0; AdvanceCycle(); ++
i) {
497 assert(
i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
500 ResourceModel->reserveResources(
nullptr, isTop());
516 <<
P.getUnitInc() <<
" ";
535 std::stringstream dbgstr;
536 dbgstr <<
"SU(" << std::setw(3) << (*I)->NodeNum <<
")";
537 dbgs() << dbgstr.str();
540 (*I)->getInstr()->dump();
552 for (
auto &Pred : SU->
Preds) {
554 if (!Pred.getSUnit()->isScheduled && (Pred.getSUnit() != SU2))
567 for (
auto &Succ : SU->
Succs) {
569 if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
582 for (
const auto &
P :
PD) {
589 return (isBotUp ?
P.getUnitInc() : -
P.getUnitInc());
615 unsigned IsAvailableAmt = 0;
624 std::stringstream dbgstr;
625 dbgstr <<
"h" << std::setw(3) << SU->
getHeight() <<
"|";
626 dbgs() << dbgstr.str();
633 ResCount += IsAvailableAmt;
644 std::stringstream dbgstr;
645 dbgstr <<
"d" << std::setw(3) << SU->
getDepth() <<
"|";
646 dbgs() << dbgstr.str();
653 ResCount += IsAvailableAmt;
659 unsigned NumNodesBlocking = 0;
676 ResCount += (NumNodesBlocking *
ScaleTwo);
679 std::stringstream dbgstr;
680 dbgstr <<
"blk " << std::setw(2) << NumNodesBlocking <<
")|";
681 dbgs() << dbgstr.str();
699 ResCount -= IsAvailableAmt;
720 if (!
SI.getSUnit()->getInstr()->isPseudo() &&
SI.isAssignedRegDep() &&
721 SI.getLatency() == 0 &&
736 for (
const auto &PI : SU->
Preds) {
737 if (PI.getLatency() > 0 &&
744 for (
const auto &
SI : SU->
Succs) {
745 if (
SI.getLatency() > 0 &&
755 std::stringstream dbgstr;
756 dbgstr <<
"Total " << std::setw(4) << ResCount <<
")";
757 dbgs() << dbgstr.str();
784 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
795 Candidate.
SCost = CurrentCost;
802 if (CurrentCost < 0 && Candidate.
SCost < 0) {
808 Candidate.
SCost = CurrentCost;
815 if (CurrentCost > Candidate.
SCost) {
819 Candidate.
SCost = CurrentCost;
827 if (CurrWeak != CandWeak) {
828 if (CurrWeak < CandWeak) {
832 Candidate.
SCost = CurrentCost;
833 FoundCandidate =
Weak;
839 unsigned CurrSize, CandSize;
841 CurrSize = (*I)->Succs.size();
842 CandSize = Candidate.
SU->
Succs.size();
844 CurrSize = (*I)->Preds.size();
845 CandSize = Candidate.
SU->
Preds.size();
847 if (CurrSize > CandSize) {
851 Candidate.
SCost = CurrentCost;
856 if (CurrSize != CandSize)
869 Candidate.
SCost = CurrentCost;
877 if (FoundCandidate ==
NoCand)
880 return FoundCandidate;
901 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
919 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
963 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
974 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
988 <<
" Scheduling instruction in cycle "
void updateQueues(SUnit *SU, bool IsTopNode)
Update scheduler DAG and queues after scheduling an instruction.
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
void viewGraph() override
Out-of-line implementation with no arguments is handy for gdb.
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
This is an optimization pass for GlobalISel generic memory operations.
void scheduleMI(SUnit *SU, bool IsTopNode)
Move an instruction and update register pressure.
RegisterClassInfo * getRegClassInfo()
SUnit * pickNode(bool &IsTopNode) override
Pick the best node to balance the schedule. Implements MachineSchedStrategy.
SUnit * pickNodeBidrectional(bool &IsTopNode)
Pick the best candidate node from either the top or bottom queue.
MachineBasicBlock::iterator begin() const
Returns an iterator to the top of the current scheduling region.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
virtual const TargetInstrInfo * getInstrInfo() const
List of PressureChanges in order of increasing, unique PSetID.
bool canReserveResources(const MCInstrDesc *MID)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
cl::opt< bool > ForceTopDown
void readyQueueVerboseDump(const RegPressureTracker &RPTracker, SchedCandidate &Candidate, ReadyQueue &Q)
VLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SM)
@ EH_LABEL
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
Store the state used by ConvergingVLIWScheduler heuristics, required for the lifetime of one invocati...
bool isCall
Is a function call.
virtual bool hasDependence(const SUnit *SUd, const SUnit *SUu)
Return true if there is a dependence between SUd and SUu.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
static bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2)
isSingleUnscheduledSucc - If SU2 is the only unscheduled successor of SU, return true (we may have du...
SmallVector< bool > HighPressureSets
List of pressure sets that have a high pressure level in the region.
Track the current register pressure at some position in the instruction stream, and remember the high...
virtual DFAPacketizer * CreateTargetScheduleState(const TargetSubtargetInfo &) const
Create machine specific model for scheduling.
SmallVector< SDep, 4 > Succs
All sunit successors.
Extend the standard ScheduleDAGMILive to provide more context and override the top-level schedule() d...
PressureDiff & getPressureDiff(const SUnit *SU)
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...
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
static cl::opt< bool > UseNewerCandidate("use-newer-candidate", cl::Hidden, cl::init(true))
static constexpr unsigned PriorityOne
static cl::opt< bool > IgnoreBBRegPressure("ignore-bb-reg-pressure", cl::Hidden, cl::init(false))
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static cl::opt< bool > CheckEarlyAvail("check-early-avail", cl::Hidden, cl::init(true))
static constexpr unsigned PriorityTwo
const InstrItineraryData * getInstrItineraries() const
void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU, int Cost, PressureChange P=PressureChange())
void initQueues(ArrayRef< SUnit * > TopRoots, ArrayRef< SUnit * > BotRoots)
Release ExitSU predecessors and setup scheduler queues.
void releaseBottomNode(SUnit *SU) override
When all successor dependencies have been resolved, free this node for bottom-up scheduling.
@ INLINEASM
INLINEASM - Represents an inline asm block.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void dump() const override
unsigned BotReadyCycle
Cycle relative to end when node is ready.
static cl::opt< float > RPThreshold("vliw-misched-reg-pressure", cl::Hidden, cl::init(0.75f), cl::desc("High register pressure threhold."))
TargetInstrInfo - Interface to description of machine instruction set.
unsigned getIssueWidth() const
Maximum number of micro-ops that may be scheduled per cycle.
bool isBottomReady() const
PressureChange CurrentMax
Itanium Name Demangler i e convert the string _Z1fv into f()". You can also use the CRTP base ManglingParser to perform some simple analysis on the mangled name
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
bool isScheduleHigh
True if preferable to schedule high.
@ Available
We know the block is fully available. This is a fixpoint.
int pressureChange(const SUnit *SU, bool isBotUp)
Check if the instruction changes the register pressure of a register in the high pressure set.
unsigned NodeNum
Entry # of node in the node vector.
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
const HexagonInstrInfo * TII
bool isPseudo(QueryType Type=IgnoreBundle) const
Return true if this is a pseudo instruction that doesn't correspond to a real machine instruction.
CandResult
Represent the type of SchedCandidate found within a single queue.
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 TopReadyCycle
Cycle relative to start when node is ready.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
bool checkHazard(SUnit *SU)
Does this SU have a hazard within the current instruction group.
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it's time to do some work.
virtual bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
SmallVectorImpl< SDep >::iterator succ_iterator
DFAPacketizer * ResourcesModel
ResourcesModel - Represents VLIW state.
ScheduleHazardRecognizer * HazardRec
bool isInPacket(SUnit *SU) const
Provide an instruction scheduling machine model to CodeGen passes.
virtual int SchedulingCost(ReadyQueue &Q, SUnit *SU, SchedCandidate &Candidate, RegPressureDelta &Delta, bool verbose)
Single point to compute overall scheduling cost.
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...
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
bool isScheduled
True once scheduled.
initializer< Ty > init(const Ty &Val)
void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
virtual const char * getRegPressureSetName(unsigned Idx) const =0
Get the name of this register unit pressure set.
PressureChange CriticalMax
virtual bool reserveResources(SUnit *SU, bool IsTop)
Keep track of available resources.
std::vector< unsigned > MaxSetPressure
Map of max reg pressure indexed by pressure set ID, not class ID.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const std::vector< PressureChange > & getRegionCriticalPSets() const
static constexpr unsigned ScaleTwo
void dumpSchedule() const
dump the scheduled Sequence.
Each Scheduling boundary is associated with ready queues.
std::unique_ptr< MachineSchedStrategy > SchedImpl
void releasePending()
Release pending ready nodes in to the available queue.
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
SmallVector< SUnit * > Packet
Local packet/bundle model.
StringRef getName() const
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
const TargetRegisterInfo * TRI
Target processor register info.
cl::opt< bool > ForceBottomUp
VLIWMachineScheduler * DAG
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const RegPressureTracker & getBotRPTracker() const
MachineFunction & MF
Machine function.
static const Function * getParent(const Value *V)
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
static cl::opt< unsigned > SchedDebugVerboseLevel("misched-verbose-level", cl::Hidden, cl::init(1))
MachineBasicBlock::iterator CurrentTop
The top of the unscheduled zone.
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
TargetSubtargetInfo - Generic base class for all target subtargets.
unsigned getNumMicroOps(const MachineInstr *MI, const MCSchedClassDesc *SC=nullptr) const
Return the number of issue slots required for this MI.
unsigned TotalPackets
Total packets created.
unsigned getRegPressureSetLimit(unsigned Idx) const
Get the register unit limit for the given pressure set index.
std::vector< SUnit * >::iterator iterator
const TargetSchedModel * SchedModel
VLIWResourceModel * ResourceModel
Store the effects of a change in pressure on things that MI scheduler cares about.
const MachineLoopInfo * MLI
std::vector< SUnit > SUnits
The scheduling units.
void schedNode(SUnit *SU, bool IsTopNode) override
Update the scheduler's state after scheduling a node.
void assign(size_type NumElts, ValueParamT Elt)
virtual ~VLIWResourceModel()
MachineBasicBlock::iterator bottom() const
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
static bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2)
isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor of SU, return true (we may have ...
Capture a change in pressure for a single pressure set.
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
void bumpCycle()
Move the boundary of scheduled code by one cycle.
void releaseNode(SUnit *SU, unsigned ReadyCycle)
MachineBasicBlock * BB
The block in which to insert instructions.
virtual VLIWResourceModel * createVLIWResourceModel(const TargetSubtargetInfo &STI, const TargetSchedModel *SchedModel) const
const TargetSchedModel * SchedModel
bool isLatencyBound(SUnit *SU)
void releaseTopNode(SUnit *SU) override
When all predecessor dependencies have been resolved, free this node for top-down scheduling.
void dumpNode(const SUnit &SU) const override
CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
const RegPressureTracker & getTopRPTracker() const
SUnit * pickOnlyChoice()
If this queue only has one ready candidate, return it.
MachineBasicBlock::iterator top() const
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
unsigned getWeakLeft(const SUnit *SU, bool isTop)
cl::opt< bool > ViewMISchedDAGs
void buildDAGWithRegPressure()
Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.
Helpers for implementing custom MachineSchedStrategy classes.
virtual DFAPacketizer * createPacketizer(const TargetSubtargetInfo &STI) const
void reserveResources(const MCInstrDesc *MID)
StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
Itinerary data supplied by a subtarget to be used by a target.
void init(VLIWMachineScheduler *dag, const TargetSchedModel *smodel)
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
static constexpr unsigned PriorityThree