Go to the documentation of this file.
45 #define DEBUG_TYPE "machine-scheduler"
70 if (SUd->
Succs.size() == 0)
80 for (
const auto &
S : SUd->
Succs) {
86 if (
S.getSUnit() == SUu &&
S.getLatency() > 0)
108 case TargetOpcode::EXTRACT_SUBREG:
109 case TargetOpcode::INSERT_SUBREG:
110 case TargetOpcode::SUBREG_TO_REG:
111 case TargetOpcode::REG_SEQUENCE:
112 case TargetOpcode::IMPLICIT_DEF:
113 case TargetOpcode::COPY:
126 for (
unsigned i = 0,
e = Packet.size();
i !=
e; ++
i)
130 for (
unsigned i = 0,
e = Packet.size();
i !=
e; ++
i)
139 bool startNewCycle =
false;
154 startNewCycle =
true;
161 case TargetOpcode::EXTRACT_SUBREG:
162 case TargetOpcode::INSERT_SUBREG:
163 case TargetOpcode::SUBREG_TO_REG:
164 case TargetOpcode::REG_SEQUENCE:
165 case TargetOpcode::IMPLICIT_DEF:
166 case TargetOpcode::KILL:
167 case TargetOpcode::CFI_INSTRUCTION:
169 case TargetOpcode::COPY:
174 Packet.push_back(SU);
178 for (
unsigned i = 0,
e = Packet.size();
i !=
e; ++
i) {
185 return startNewCycle;
211 for (
unsigned su = 0,
e =
SUnits.size(); su !=
e;
212 ++su)
if (
SUnits[su].getHeight() > maxH) maxH =
214 dbgs() <<
"Max Height " << maxH <<
"\n";);
216 for (
unsigned su = 0,
e =
SUnits.size(); su !=
e;
217 ++su)
if (
SUnits[su].getDepth() > maxD) maxD =
219 dbgs() <<
"Max Depth " << maxD <<
"\n";);
224 bool IsTopNode =
false;
227 dbgs() <<
"** VLIWMachineScheduler::schedule picking next node\n");
246 dbgs() <<
"*** Final schedule for "
257 Top.init(DAG, SchedModel);
258 Bot.init(DAG, SchedModel);
265 delete Top.HazardRec;
266 delete Bot.HazardRec;
267 Top.HazardRec =
TII->CreateTargetMIHazardRecognizer(Itin, DAG);
268 Bot.HazardRec =
TII->CreateTargetMIHazardRecognizer(Itin, DAG);
270 delete Top.ResourceModel;
271 delete Bot.ResourceModel;
275 const std::vector<unsigned> &MaxPressure =
277 HighPressureSets.assign(MaxPressure.size(), 0);
278 for (
unsigned i = 0,
e = MaxPressure.size();
i <
e; ++
i) {
280 HighPressureSets[
i] =
281 ((float) MaxPressure[
i] > ((
float) Limit *
RPThreshold));
285 "-misched-topdown incompatible with -misched-bottomup");
296 Top.MaxMinLatency =
std::max(MinLatency, Top.MaxMinLatency);
312 unsigned SuccReadyCycle =
I->getSUnit()->BotReadyCycle;
313 unsigned MinLatency =
I->getLatency();
315 Bot.MaxMinLatency =
std::max(MinLatency, Bot.MaxMinLatency);
336 bool ConvergingVLIWScheduler::VLIWSchedBoundary::checkHazard(
SUnit *SU) {
337 if (HazardRec->isEnabled())
340 unsigned uops = SchedModel->getNumMicroOps(SU->
getInstr());
341 if (IssueCount + uops > SchedModel->getIssueWidth())
347 void ConvergingVLIWScheduler::VLIWSchedBoundary::releaseNode(
SUnit *SU,
348 unsigned ReadyCycle) {
349 if (ReadyCycle < MinReadyCycle)
350 MinReadyCycle = ReadyCycle;
354 if (ReadyCycle > CurrCycle || checkHazard(SU))
362 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpCycle() {
363 unsigned Width = SchedModel->getIssueWidth();
364 IssueCount = (IssueCount <=
Width) ? 0 : IssueCount -
Width;
367 "MinReadyCycle uninitialized");
368 unsigned NextCycle =
std::max(CurrCycle + 1, MinReadyCycle);
370 if (!HazardRec->isEnabled()) {
372 CurrCycle = NextCycle;
375 for (; CurrCycle != NextCycle; ++CurrCycle) {
377 HazardRec->AdvanceCycle();
379 HazardRec->RecedeCycle();
385 << CurrCycle <<
'\n');
389 void ConvergingVLIWScheduler::VLIWSchedBoundary::bumpNode(
SUnit *SU) {
390 bool startNewCycle =
false;
393 if (HazardRec->isEnabled()) {
394 if (!isTop() && SU->
isCall) {
399 HazardRec->EmitInstruction(SU);
403 startNewCycle = ResourceModel->reserveResources(SU, isTop());
407 IssueCount += SchedModel->getNumMicroOps(SU->
getInstr());
409 LLVM_DEBUG(
dbgs() <<
"*** Max instrs at cycle " << CurrCycle <<
'\n');
413 LLVM_DEBUG(
dbgs() <<
"*** IssueCount " << IssueCount <<
" at cycle "
414 << CurrCycle <<
'\n');
419 void ConvergingVLIWScheduler::VLIWSchedBoundary::releasePending() {
426 for (
unsigned i = 0,
e = Pending.size();
i !=
e; ++
i) {
427 SUnit *SU = *(Pending.begin()+
i);
430 if (ReadyCycle < MinReadyCycle)
431 MinReadyCycle = ReadyCycle;
433 if (ReadyCycle > CurrCycle)
440 Pending.remove(Pending.begin()+
i);
443 CheckPending =
false;
447 void ConvergingVLIWScheduler::VLIWSchedBoundary::removeReady(
SUnit *SU) {
451 assert(Pending.isInQueue(SU) &&
"bad ready count");
452 Pending.remove(Pending.find(SU));
459 SUnit *ConvergingVLIWScheduler::VLIWSchedBoundary::pickOnlyChoice() {
463 auto AdvanceCycle = [
this]() {
466 if (
Available.size() == 1 && Pending.size() > 0)
467 return !ResourceModel->isResourceAvailable(*
Available.begin(), isTop()) ||
471 for (
unsigned i = 0; AdvanceCycle(); ++
i) {
472 assert(
i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
473 "permanent hazard"); (void)
i;
474 ResourceModel->reserveResources(
nullptr, isTop());
489 <<
P.getUnitInc() <<
" ";
492 dbgs() <<
"cost(" << Cost <<
")\t";
508 std::stringstream dbgstr;
509 dbgstr <<
"SU(" << std::setw(3) << (*I)->NodeNum <<
")";
510 dbgs() << dbgstr.str();
513 (*I)->getInstr()->dump();
525 for (
auto &Pred : SU->
Preds) {
527 if (!Pred.getSUnit()->isScheduled && (Pred.getSUnit() != SU2))
540 for (
auto &Succ : SU->
Succs) {
542 if (!Succ.getSUnit()->isScheduled && (Succ.getSUnit() != SU2))
561 if (HighPressureSets[
P.getPSet()])
562 return (isBotUp ?
P.getUnitInc() : -
P.getUnitInc());
577 SchedCandidate &Candidate,
595 unsigned IsAvailableAmt = 0;
598 if (Top.isLatencyBound(SU)) {
604 std::stringstream dbgstr;
605 dbgstr <<
"h" << std::setw(3) << SU->
getHeight() <<
"|";
606 dbgs() << dbgstr.str();
611 if (Top.ResourceModel->isResourceAvailable(SU,
true)) {
613 ResCount += IsAvailableAmt;
618 if (Bot.isLatencyBound(SU)) {
624 std::stringstream dbgstr;
625 dbgstr <<
"d" << std::setw(3) << SU->
getDepth() <<
"|";
626 dbgs() << dbgstr.str();
631 if (Bot.ResourceModel->isResourceAvailable(SU,
false)) {
633 ResCount += IsAvailableAmt;
639 unsigned NumNodesBlocking = 0;
645 if (Top.isLatencyBound(SU))
651 if (Bot.isLatencyBound(SU))
656 ResCount += (NumNodesBlocking *
ScaleTwo);
659 std::stringstream dbgstr;
660 dbgstr <<
"blk " << std::setw(2) << NumNodesBlocking <<
")|";
661 dbgs() << dbgstr.str();
679 ResCount -= IsAvailableAmt;
693 Top.ResourceModel->isResourceAvailable(SU,
true)) {
697 Bot.ResourceModel->isResourceAvailable(SU,
false)) {
709 Top.ResourceModel->isInPacket(PI.
getSUnit())) {
716 if (!
SI.getSUnit()->getInstr()->isPseudo() &&
SI.isAssignedRegDep() &&
717 SI.getLatency() == 0 &&
718 Bot.ResourceModel->isInPacket(
SI.getSUnit())) {
732 for (
const auto &PI : SU->
Preds) {
733 if (PI.getLatency() > 0 &&
734 Top.ResourceModel->isInPacket(PI.getSUnit())) {
740 for (
const auto &
SI : SU->
Succs) {
741 if (
SI.getLatency() > 0 &&
742 Bot.ResourceModel->isInPacket(
SI.getSUnit())) {
751 std::stringstream dbgstr;
752 dbgstr <<
"Total " << std::setw(4) << ResCount <<
")";
753 dbgs() << dbgstr.str();
766 SchedCandidate &Candidate) {
776 CandResult FoundCandidate = NoCand;
779 TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
789 Candidate.RPDelta = RPDelta;
790 Candidate.SCost = CurrentCost;
791 FoundCandidate = NodeOrder;
797 if (CurrentCost < 0 && Candidate.SCost < 0) {
798 if ((Q.
getID() ==
TopQID && (*I)->NodeNum < Candidate.SU->NodeNum)
799 || (Q.
getID() ==
BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
802 Candidate.RPDelta = RPDelta;
803 Candidate.SCost = CurrentCost;
804 FoundCandidate = NodeOrder;
810 if (CurrentCost > Candidate.SCost) {
813 Candidate.RPDelta = RPDelta;
814 Candidate.SCost = CurrentCost;
815 FoundCandidate = BestCost;
822 if (CurrWeak != CandWeak) {
823 if (CurrWeak < CandWeak) {
826 Candidate.RPDelta = RPDelta;
827 Candidate.SCost = CurrentCost;
828 FoundCandidate = Weak;
833 if (CurrentCost == Candidate.SCost && Zone.isLatencyBound(*
I)) {
834 unsigned CurrSize, CandSize;
836 CurrSize = (*I)->Succs.size();
837 CandSize = Candidate.SU->Succs.size();
839 CurrSize = (*I)->Preds.size();
840 CandSize = Candidate.SU->Preds.size();
842 if (CurrSize > CandSize) {
845 Candidate.RPDelta = RPDelta;
846 Candidate.SCost = CurrentCost;
847 FoundCandidate = BestCost;
851 if (CurrSize != CandSize)
859 if ((Q.
getID() ==
TopQID && (*I)->NodeNum < Candidate.SU->NodeNum)
860 || (Q.
getID() ==
BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
863 Candidate.RPDelta = RPDelta;
864 Candidate.SCost = CurrentCost;
865 FoundCandidate = NodeOrder;
872 if (FoundCandidate == NoCand)
875 return FoundCandidate;
882 if (
SUnit *SU = Bot.pickOnlyChoice()) {
887 if (
SUnit *SU = Top.pickOnlyChoice()) {
892 SchedCandidate BotCand;
896 assert(BotResult != NoCand &&
"failed to find the first candidate");
905 if (BotResult == SingleExcess || BotResult == SingleCritical) {
911 SchedCandidate TopCand;
914 assert(TopResult != NoCand &&
"failed to find the first candidate");
916 if (TopResult == SingleExcess || TopResult == SingleCritical) {
923 if (BotResult == SingleMax) {
928 if (TopResult == SingleMax) {
933 if (TopCand.SCost > BotCand.SCost) {
947 assert(Top.Available.empty() && Top.Pending.empty() &&
948 Bot.Available.empty() && Bot.Pending.empty() &&
"ReadyQ garbage");
953 SU = Top.pickOnlyChoice();
955 SchedCandidate TopCand;
956 CandResult TopResult =
958 assert(TopResult != NoCand &&
"failed to find the first candidate");
964 SU = Bot.pickOnlyChoice();
966 SchedCandidate BotCand;
967 CandResult BotResult =
969 assert(BotResult != NoCand &&
"failed to find the first candidate");
983 <<
" Scheduling instruction in cycle "
984 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) <<
" ("
void updateQueues(SUnit *SU, bool IsTopNode)
Update scheduler DAG and queues after scheduling an instruction.
static cl::opt< bool > UseNewerCandidate("use-newer-candidate", cl::Hidden, cl::ZeroOrMore, cl::init(true))
const IntervalPressure & getRegPressure() const
Get register pressure for the entire scheduling region before scheduling.
void initialize(ScheduleDAGMI *dag) override
Initialize the strategy after building the DAG for a new region.
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)
static cl::opt< float > RPThreshold("hexagon-reg-pressure", cl::Hidden, cl::init(0.75f), cl::desc("High register pressure threhold."))
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)
static cl::opt< bool > IgnoreBBRegPressure("ignore-bb-reg-pressure", cl::Hidden, cl::ZeroOrMore, cl::init(false))
@ EH_LABEL
EH_LABEL - Represents a label in mid basic block used to track locations needed for debug and excepti...
bool isCall
Is a function call.
ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
void postprocessDAG()
Apply each ScheduleDAGMutation step in order.
Track the current register pressure at some position in the instruction stream, and remember the high...
SmallVector< SDep, 4 > Succs
All sunit successors.
Extend the standard ScheduleDAGMI to provide more context and override the top-level schedule() drive...
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...
MachineBasicBlock::iterator CurrentBottom
The bottom of the unscheduled zone.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
static cl::opt< unsigned > SchedDebugVerboseLevel("misched-verbose-level", cl::Hidden, cl::ZeroOrMore, cl::init(1))
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 const unsigned ScaleTwo
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.
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.
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 HexagonInstrInfo * getInstrInfo() const override
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void schedule() override
Schedule - This is called back from ScheduleDAGInstrs::Run() when it's time to do some work.
bool isResourceAvailable(SUnit *SU, bool IsTop)
Check if scheduling of this SU is possible in the current packet.
SmallVectorImpl< SDep >::iterator succ_iterator
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)
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
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
void dumpSchedule() const
dump the scheduled Sequence.
std::unique_ptr< MachineSchedStrategy > SchedImpl
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
ScheduleDAGMI is an implementation of ScheduleDAGInstrs that simply schedules machine instructions ac...
StringRef getName() const
void placeDebugValues()
Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
static const unsigned PriorityOne
const TargetRegisterInfo * TRI
Target processor register info.
cl::opt< bool > ForceBottomUp
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const RegPressureTracker & getBotRPTracker() const
MachineFunction & MF
Machine function.
if(llvm_vc STREQUAL "") set(fake_version_inc "$
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.
const MachineBasicBlock * getParent() const
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 getRegPressureSetLimit(unsigned Idx) const
Get the register unit limit for the given pressure set index.
std::vector< SUnit * >::iterator iterator
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.
static bool isSingleUnscheduledSucc(SUnit *SU, SUnit *SU2)
isSingleUnscheduledSucc - If SU2 is the only unscheduled successor of SU, return true (we may have du...
MachineBasicBlock::iterator bottom() const
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
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.
MachineBasicBlock * BB
The block in which to insert instructions.
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
static bool hasDependence(const SUnit *SUd, const SUnit *SUu, const HexagonInstrInfo &QII)
Return true if there is a dependence between SUd and SUu.
CandResult pickNodeFromQueue(VLIWSchedBoundary &Zone, const RegPressureTracker &RPTracker, SchedCandidate &Candidate)
Pick the best candidate from the top queue.
bool isInstr() const
Returns true if this SUnit refers to a machine instruction as opposed to an SDNode.
const RegPressureTracker & getTopRPTracker() const
Align max(MaybeAlign Lhs, Align Rhs)
bool canExecuteInBundle(const MachineInstr &First, const MachineInstr &Second) const
Can these instructions execute at the same time in a bundle.
MachineBasicBlock::iterator top() const
const TargetSchedModel * getSchedModel() const
Gets the machine model for instruction scheduling.
static bool isSingleUnscheduledPred(SUnit *SU, SUnit *SU2)
isSingleUnscheduledPred - If SU2 is the only unscheduled predecessor of SU, return true (we may have ...
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
unsigned getWeakLeft(const SUnit *SU, bool isTop)
void buildDAGWithRegPressure()
Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking enabled.
static cl::opt< bool > CheckEarlyAvail("check-early-avail", cl::Hidden, cl::ZeroOrMore, cl::init(true))
static const unsigned PriorityTwo
Helpers for implementing custom MachineSchedStrategy classes.
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.
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
bool mayBeCurLoad(const MachineInstr &MI) const
static const unsigned PriorityThree