Go to the documentation of this file.
42 #define DEBUG_TYPE "machine-scheduler"
64 cl::desc(
"High register pressure threhold."));
68 :
TII(STI.getInstrInfo()), SchedModel(SM) {
89 if (SUd->
Succs.size() == 0)
92 for (
const auto &
S : SUd->
Succs) {
98 if (
S.getSUnit() == SUu &&
S.getLatency() > 0)
120 case TargetOpcode::EXTRACT_SUBREG:
121 case TargetOpcode::INSERT_SUBREG:
122 case TargetOpcode::SUBREG_TO_REG:
123 case TargetOpcode::REG_SEQUENCE:
124 case TargetOpcode::IMPLICIT_DEF:
125 case TargetOpcode::COPY:
134 for (
unsigned i = 0,
e =
Packet.size();
i !=
e; ++
i)
138 for (
unsigned i = 0,
e =
Packet.size();
i !=
e; ++
i)
147 bool startNewCycle =
false;
160 startNewCycle =
true;
167 case TargetOpcode::EXTRACT_SUBREG:
168 case TargetOpcode::INSERT_SUBREG:
169 case TargetOpcode::SUBREG_TO_REG:
170 case TargetOpcode::REG_SEQUENCE:
171 case TargetOpcode::IMPLICIT_DEF:
172 case TargetOpcode::KILL:
173 case TargetOpcode::CFI_INSTRUCTION:
175 case TargetOpcode::COPY:
184 for (
unsigned i = 0,
e =
Packet.size();
i !=
e; ++
i) {
191 return startNewCycle;
224 if (SU.getHeight() > maxH)
225 maxH = SU.getHeight();
226 dbgs() <<
"Max Height " << maxH <<
"\n";
231 if (SU.getDepth() > maxD)
232 maxD = SU.getDepth();
233 dbgs() <<
"Max Depth " << maxD <<
"\n";
241 bool IsTopNode =
false;
244 dbgs() <<
"** VLIWMachineScheduler::schedule picking next node\n");
264 dbgs() <<
"*** Final schedule for "
293 const std::vector<unsigned> &MaxPressure =
296 for (
unsigned i = 0,
e = MaxPressure.size();
i <
e; ++
i) {
303 "-misched-topdown incompatible with -misched-bottomup");
331 unsigned SuccReadyCycle =
I->getSUnit()->BotReadyCycle;
332 unsigned MinLatency =
I->getLatency();
363 if (HazardRec->isEnabled())
374 SUnit *SU,
unsigned ReadyCycle) {
375 if (ReadyCycle < MinReadyCycle)
376 MinReadyCycle = ReadyCycle;
380 if (ReadyCycle > CurrCycle || checkHazard(SU))
390 IssueCount = (IssueCount <=
Width) ? 0 : IssueCount -
Width;
393 "MinReadyCycle uninitialized");
394 unsigned NextCycle =
std::max(CurrCycle + 1, MinReadyCycle);
396 if (!HazardRec->isEnabled()) {
398 CurrCycle = NextCycle;
401 for (; CurrCycle != NextCycle; ++CurrCycle) {
403 HazardRec->AdvanceCycle();
405 HazardRec->RecedeCycle();
411 << CurrCycle <<
'\n');
416 bool startNewCycle =
false;
419 if (HazardRec->isEnabled()) {
420 if (!isTop() && SU->
isCall) {
425 HazardRec->EmitInstruction(SU);
429 startNewCycle = ResourceModel->reserveResources(SU, isTop());
435 LLVM_DEBUG(
dbgs() <<
"*** Max instrs at cycle " << CurrCycle <<
'\n');
438 LLVM_DEBUG(
dbgs() <<
"*** IssueCount " << IssueCount <<
" at cycle "
439 << CurrCycle <<
'\n');
451 for (
unsigned i = 0,
e = Pending.size();
i !=
e; ++
i) {
452 SUnit *SU = *(Pending.begin() +
i);
455 if (ReadyCycle < MinReadyCycle)
456 MinReadyCycle = ReadyCycle;
458 if (ReadyCycle > CurrCycle)
465 Pending.remove(Pending.begin() +
i);
469 CheckPending =
false;
477 assert(Pending.isInQueue(SU) &&
"bad ready count");
478 Pending.remove(Pending.find(SU));
489 auto AdvanceCycle = [
this]() {
492 if (
Available.size() == 1 && Pending.size() > 0)
493 return !ResourceModel->isResourceAvailable(*
Available.begin(), isTop()) ||
497 for (
unsigned i = 0; AdvanceCycle(); ++
i) {
498 assert(
i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
501 ResourceModel->reserveResources(
nullptr, isTop());
517 <<
P.getUnitInc() <<
" ";
520 dbgs() <<
"cost(" << Cost <<
")\t";
536 std::stringstream dbgstr;
537 dbgstr <<
"SU(" << std::setw(3) << (*I)->NodeNum <<
")";
538 dbgs() << dbgstr.str();
541 (*I)->getInstr()->dump();
553 for (
auto &Pred : SU->
Preds) {
555 if (!Pred.getSUnit()->isScheduled && (Pred.getSUnit() != SU2))
568 for (
auto &Succ : SU->
Succs) {
570 if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
590 return (isBotUp ?
P.getUnitInc() : -
P.getUnitInc());
616 unsigned IsAvailableAmt = 0;
625 std::stringstream dbgstr;
626 dbgstr <<
"h" << std::setw(3) << SU->
getHeight() <<
"|";
627 dbgs() << dbgstr.str();
634 ResCount += IsAvailableAmt;
645 std::stringstream dbgstr;
646 dbgstr <<
"d" << std::setw(3) << SU->
getDepth() <<
"|";
647 dbgs() << dbgstr.str();
654 ResCount += IsAvailableAmt;
660 unsigned NumNodesBlocking = 0;
677 ResCount += (NumNodesBlocking *
ScaleTwo);
680 std::stringstream dbgstr;
681 dbgstr <<
"blk " << std::setw(2) << NumNodesBlocking <<
")|";
682 dbgs() << dbgstr.str();
700 ResCount -= IsAvailableAmt;
721 if (!
SI.getSUnit()->getInstr()->isPseudo() &&
SI.isAssignedRegDep() &&
722 SI.getLatency() == 0 &&
737 for (
const auto &PI : SU->
Preds) {
738 if (PI.getLatency() > 0 &&
745 for (
const auto &
SI : SU->
Succs) {
746 if (
SI.getLatency() > 0 &&
756 std::stringstream dbgstr;
757 dbgstr <<
"Total " << std::setw(4) << ResCount <<
")";
758 dbgs() << dbgstr.str();
785 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
796 Candidate.
SCost = CurrentCost;
803 if (CurrentCost < 0 && Candidate.
SCost < 0) {
809 Candidate.
SCost = CurrentCost;
816 if (CurrentCost > Candidate.
SCost) {
820 Candidate.
SCost = CurrentCost;
828 if (CurrWeak != CandWeak) {
829 if (CurrWeak < CandWeak) {
833 Candidate.
SCost = CurrentCost;
834 FoundCandidate =
Weak;
840 unsigned CurrSize, CandSize;
842 CurrSize = (*I)->Succs.size();
843 CandSize = Candidate.
SU->
Succs.size();
845 CurrSize = (*I)->Preds.size();
846 CandSize = Candidate.
SU->
Preds.size();
848 if (CurrSize > CandSize) {
852 Candidate.
SCost = CurrentCost;
857 if (CurrSize != CandSize)
870 Candidate.
SCost = CurrentCost;
878 if (FoundCandidate ==
NoCand)
881 return FoundCandidate;
902 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
920 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
964 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
975 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
989 <<
" 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...
static constexpr unsigned PriorityOne
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static constexpr unsigned PriorityTwo
const InstrItineraryData * getInstrItineraries() const
static cl::opt< bool > IgnoreBBRegPressure("ignore-bb-reg-pressure", cl::Hidden, cl::ZeroOrMore, cl::init(false))
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.
static cl::opt< unsigned > SchedDebugVerboseLevel("misched-verbose-level", cl::Hidden, cl::ZeroOrMore, cl::init(1))
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.
StandardInstrumentations SI(Debug, VerifyEach)
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
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.
Align max(MaybeAlign Lhs, Align Rhs)
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)
static cl::opt< bool > CheckEarlyAvail("check-early-avail", cl::Hidden, cl::ZeroOrMore, cl::init(true))
cl::opt< bool > ViewMISchedDAGs
static cl::opt< bool > UseNewerCandidate("use-newer-candidate", cl::Hidden, cl::ZeroOrMore, cl::init(true))
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