42#define DEBUG_TYPE "machine-scheduler"
67 if (SUd->
Succs.size() == 0)
70 for (
const auto &S : SUd->
Succs) {
76 if (S.getSUnit() == SUu && S.getLatency() > 0)
98 case TargetOpcode::EXTRACT_SUBREG:
99 case TargetOpcode::INSERT_SUBREG:
100 case TargetOpcode::SUBREG_TO_REG:
101 case TargetOpcode::REG_SEQUENCE:
102 case TargetOpcode::IMPLICIT_DEF:
103 case TargetOpcode::COPY:
104 case TargetOpcode::INLINEASM:
105 case TargetOpcode::INLINEASM_BR:
125 bool startNewCycle =
false;
138 startNewCycle =
true;
145 case TargetOpcode::EXTRACT_SUBREG:
146 case TargetOpcode::INSERT_SUBREG:
147 case TargetOpcode::SUBREG_TO_REG:
148 case TargetOpcode::REG_SEQUENCE:
149 case TargetOpcode::IMPLICIT_DEF:
150 case TargetOpcode::KILL:
151 case TargetOpcode::CFI_INSTRUCTION:
152 case TargetOpcode::EH_LABEL:
153 case TargetOpcode::COPY:
154 case TargetOpcode::INLINEASM:
155 case TargetOpcode::INLINEASM_BR:
162 for (
unsigned i = 0, e =
Packet.size(); i != e; ++i) {
168 return startNewCycle;
182 <<
" in_func " <<
BB->getParent()->getName()
183 <<
" at loop depth " <<
MLI->getLoopDepth(
BB) <<
" \n");
187 Topo.InitDAGTopologicalSorting();
201 if (SU.getHeight() > maxH)
202 maxH = SU.getHeight();
203 dbgs() <<
"Max Height " << maxH <<
"\n";
208 if (SU.getDepth() > maxD)
209 maxD = SU.getDepth();
210 dbgs() <<
"Max Depth " << maxD <<
"\n";
218 bool IsTopNode =
false;
221 dbgs() <<
"** VLIWMachineScheduler::schedule picking next node\n");
241 dbgs() <<
"*** Final schedule for "
260 delete Top.HazardRec;
261 delete Bot.HazardRec;
262 Top.HazardRec =
TII->CreateTargetMIHazardRecognizer(Itin,
DAG);
263 Bot.HazardRec =
TII->CreateTargetMIHazardRecognizer(Itin,
DAG);
265 delete Top.ResourceModel;
266 delete Bot.ResourceModel;
270 const std::vector<unsigned> &MaxPressure =
271 DAG->getRegPressure().MaxSetPressure;
273 for (
unsigned i = 0, e = MaxPressure.size(); i < e; ++i) {
274 unsigned Limit =
DAG->getRegClassInfo()->getRegPressureSetLimit(i);
276 ((float)MaxPressure[i] >
277 ((float)Limit *
DAG->Opts.vliw_misched_reg_pressure));
291 Top.MaxMinLatency = std::max(MinLatency,
Top.MaxMinLatency);
306 unsigned SuccReadyCycle =
I->getSUnit()->BotReadyCycle;
307 unsigned MinLatency =
I->getLatency();
309 Bot.MaxMinLatency = std::max(MinLatency,
Bot.MaxMinLatency);
349 SUnit *SU,
unsigned ReadyCycle) {
368 "MinReadyCycle uninitialized");
391 bool startNewCycle =
false;
426 for (
unsigned i = 0, e =
Pending.size(); i != e; ++i) {
464 auto AdvanceCycle = [
this]() {
472 for (
unsigned i = 0; AdvanceCycle(); ++i) {
491 dbgs() <<
DAG->TRI->getRegPressureSetName(
P.getPSet()) <<
":"
492 <<
P.getUnitInc() <<
" ";
509 DAG->getRegionCriticalPSets(),
510 DAG->getRegPressure().MaxSetPressure);
516 (*I)->getInstr()->dump();
530 if (!
Pred.getSUnit()->isScheduled && (
Pred.getSUnit() != SU2))
543 for (
auto &Succ : SU->
Succs) {
545 if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
558 for (
const auto &
P : PD) {
565 return (isBotUp ?
P.getUnitInc() : -
P.getUnitInc());
591 unsigned IsAvailableAmt = 0;
594 if (
Top.isLatencyBound(SU)) {
600 std::stringstream dbgstr;
601 dbgstr <<
"h" << std::setw(3) << SU->
getHeight() <<
"|";
602 dbgs() << dbgstr.str();
607 if (
Top.ResourceModel->isResourceAvailable(SU,
true)) {
609 ResCount += IsAvailableAmt;
614 if (
Bot.isLatencyBound(SU)) {
620 std::stringstream dbgstr;
621 dbgstr <<
"d" << std::setw(3) << SU->
getDepth() <<
"|";
622 dbgs() << dbgstr.str();
627 if (
Bot.ResourceModel->isResourceAvailable(SU,
false)) {
629 ResCount += IsAvailableAmt;
635 unsigned NumNodesBlocking = 0;
641 if (
Top.isLatencyBound(SU))
647 if (
Bot.isLatencyBound(SU))
652 ResCount += (NumNodesBlocking *
ScaleTwo);
655 std::stringstream dbgstr;
656 dbgstr <<
"blk " << std::setw(2) << NumNodesBlocking <<
")|";
657 dbgs() << dbgstr.str();
661 if (!
DAG->Opts.vliw_misched_ignore_bb_reg_pressure) {
675 ResCount -= IsAvailableAmt;
696 if (!
SI.getSUnit()->getInstr()->isPseudo() &&
SI.isAssignedRegDep() &&
697 SI.getLatency() == 0 &&
698 Bot.ResourceModel->isInPacket(
SI.getSUnit())) {
710 if (
DAG->Opts.vliw_misched_check_early_avail) {
712 for (
const auto &PI : SU->
Preds) {
713 if (PI.getLatency() > 0 &&
714 Top.ResourceModel->isInPacket(PI.getSUnit())) {
720 for (
const auto &
SI : SU->
Succs) {
721 if (
SI.getLatency() > 0 &&
722 Bot.ResourceModel->isInPacket(
SI.getSUnit())) {
731 std::stringstream dbgstr;
732 dbgstr <<
"Total " << std::setw(4) << ResCount <<
")";
733 dbgs() << dbgstr.str();
760 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
761 DAG->getRegionCriticalPSets(),
762 DAG->getRegPressure().MaxSetPressure);
771 Candidate.
SCost = CurrentCost;
778 if (CurrentCost < 0 && Candidate.
SCost < 0) {
784 Candidate.
SCost = CurrentCost;
791 if (CurrentCost > Candidate.
SCost) {
795 Candidate.
SCost = CurrentCost;
803 if (CurrWeak != CandWeak) {
804 if (CurrWeak < CandWeak) {
808 Candidate.
SCost = CurrentCost;
809 FoundCandidate =
Weak;
815 unsigned CurrSize, CandSize;
817 CurrSize = (*I)->Succs.size();
818 CandSize = Candidate.
SU->
Succs.size();
820 CurrSize = (*I)->Preds.size();
821 CandSize = Candidate.
SU->
Preds.size();
823 if (CurrSize > CandSize) {
827 Candidate.
SCost = CurrentCost;
832 if (CurrSize != CandSize)
839 if (
DAG->Opts.vliw_misched_use_newer_candidate &&
840 CurrentCost == Candidate.
SCost) {
846 Candidate.
SCost = CurrentCost;
854 if (FoundCandidate ==
NoCand)
857 return FoundCandidate;
864 if (
SUnit *SU =
Bot.pickOnlyChoice()) {
869 if (
SUnit *SU =
Top.pickOnlyChoice()) {
878 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
896 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
928 if (
DAG->top() ==
DAG->bottom()) {
930 Bot.Available.empty() &&
Bot.Pending.empty() &&
"ReadyQ garbage");
935 SU =
Top.pickOnlyChoice();
940 assert(TopResult !=
NoCand &&
"failed to find the first candidate");
946 SU =
Bot.pickOnlyChoice();
951 assert(BotResult !=
NoCand &&
"failed to find the first candidate");
965 <<
" Scheduling instruction in cycle "
966 << (IsTopNode ?
Top.CurrCycle :
Bot.CurrCycle) <<
" ("
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static const Function * getParent(const Value *V)
const HexagonInstrInfo * TII
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 bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2)
isSingleUnscheduledSucc - If SU2 is the only unscheduled successor of SU, return true (we may have du...
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.
Itinerary data supplied by a subtarget to be used by a target.
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.
LLVM_ABI void dump() const
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 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.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
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.
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.
void dump() const override
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.
void findRootsAndBiasEdges(SmallVectorImpl< SUnit * > &TopRoots, SmallVectorImpl< SUnit * > &BotRoots)
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.
std::vector< SUnit > SUnits
The scheduling units.
MachineFunction & MF
Machine function.
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.
Provide an instruction scheduling machine model to CodeGen passes.
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...
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.
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.
const TargetInstrInfo * TII
A raw_ostream that writes to an std::string.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
LLVM_ABI unsigned getWeakLeft(const SUnit *SU, bool isTop)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
FormattedString left_justify(StringRef Str, unsigned Width)
left_justify - append spaces after string so total output is Width characters.
LLVM_ABI bool shouldViewMISchedDAGs(const MachineFunction &MF)
Return -misched-view-dags, which is false in a build without assertions.
LLVM_ABI 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.
const TargetSchedModel * SchedModel
LLVM_ABI ~VLIWSchedBoundary()
bool isLatencyBound(SUnit *SU)
LLVM_ABI void releaseNode(SUnit *SU, unsigned ReadyCycle)
LLVM_ABI void removeReady(SUnit *SU)
Remove SU from the ready set for this boundary.
ScheduleHazardRecognizer * HazardRec
LLVM_ABI void bumpNode(SUnit *SU)
Move the boundary of scheduled code by one SUnit.
unsigned MinReadyCycle
MinReadyCycle - Cycle of the soonest available instruction.
VLIWResourceModel * ResourceModel
LLVM_ABI void releasePending()
Release pending ready nodes in to the available queue.
LLVM_ABI SUnit * pickOnlyChoice()
If this queue only has one ready candidate, return it.
LLVM_ABI void bumpCycle()
Move the boundary of scheduled code by one cycle.
LLVM_ABI 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