Go to the documentation of this file.
28 #define DEBUG_TYPE "pre-RA-sched"
30 STATISTIC(NumUnfolds,
"Number of nodes unfolded");
31 STATISTIC(NumDups,
"Number of duplicated nodes");
32 STATISTIC(NumPRCopies,
"Number of physical copies");
46 struct FastPriorityQueue {
49 bool empty()
const {
return Queue.empty(); }
56 if (
empty())
return nullptr;
57 return Queue.pop_back_val();
67 FastPriorityQueue AvailableQueue;
73 std::vector<SUnit*> LiveRegDefs;
74 std::vector<unsigned> LiveRegCycles;
80 void Schedule()
override;
95 void ReleasePred(
SUnit *SU,
SDep *PredEdge);
96 void ReleasePredecessors(
SUnit *SU,
unsigned CurCycle);
97 void ScheduleNodeBottomUp(
SUnit*,
unsigned);
99 void InsertCopiesAndMoveSuccs(
SUnit*,
unsigned,
104 void ListScheduleBottomUp();
107 bool forceUnitLatencies()
const override {
return true; }
113 void ScheduleDAGFast::Schedule() {
121 BuildSchedGraph(
nullptr);
126 ListScheduleBottomUp();
135 void ScheduleDAGFast::ReleasePred(
SUnit *SU,
SDep *PredEdge) {
140 dbgs() <<
"*** Scheduling failed! ***\n";
142 dbgs() <<
" has been released too many times!\n";
152 AvailableQueue.push(PredSU);
156 void ScheduleDAGFast::ReleasePredecessors(
SUnit *SU,
unsigned CurCycle) {
159 ReleasePred(SU, &Pred);
165 if (!LiveRegDefs[Pred.
getReg()]) {
168 LiveRegCycles[Pred.
getReg()] = CurCycle;
177 void ScheduleDAGFast::ScheduleNodeBottomUp(
SUnit *SU,
unsigned CurCycle) {
181 assert(CurCycle >= SU->
getHeight() &&
"Node scheduled below its height!");
185 ReleasePredecessors(SU, CurCycle);
191 assert(NumLiveRegs > 0 &&
"NumLiveRegs is already zero!");
193 "Physical register dependency violated?");
195 LiveRegDefs[Succ.
getReg()] =
nullptr;
196 LiveRegCycles[Succ.
getReg()] = 0;
206 SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(
SUnit *SU) {
215 bool TryUnfold =
false;
216 for (
unsigned i = 0,
e =
N->getNumValues();
i !=
e; ++
i) {
217 MVT VT =
N->getSimpleValueType(
i);
224 MVT VT =
Op.getNode()->getSimpleValueType(
Op.getResNo());
231 if (!
TII->unfoldMemoryOperand(*DAG,
N, NewNodes))
235 assert(NewNodes.size() == 2 &&
"Expected a load folding node!");
238 SDNode *LoadNode = NewNodes[0];
239 unsigned NumVals =
N->getNumValues();
241 for (
unsigned i = 0;
i != NumVals; ++
i)
243 DAG->ReplaceAllUsesOfValueWith(
SDValue(SU->
getNode(), OldNumVals-1),
246 SUnit *NewSU = newSUnit(
N);
247 assert(
N->getNodeId() == -1 &&
"Node already inserted!");
263 bool isNewLoad =
true;
269 LoadSU = newSUnit(LoadNode);
283 LoadPreds.push_back(Pred);
285 NodePreds.push_back(Pred);
289 ChainSuccs.push_back(Succ);
291 NodeSuccs.push_back(Succ);
295 RemovePred(SU, ChainPred);
297 AddPred(LoadSU, ChainPred);
299 for (
unsigned i = 0,
e = LoadPreds.size();
i !=
e; ++
i) {
300 const SDep &Pred = LoadPreds[
i];
301 RemovePred(SU, Pred);
303 AddPred(LoadSU, Pred);
306 for (
unsigned i = 0,
e = NodePreds.size();
i !=
e; ++
i) {
307 const SDep &Pred = NodePreds[
i];
308 RemovePred(SU, Pred);
309 AddPred(NewSU, Pred);
311 for (
unsigned i = 0,
e = NodeSuccs.size();
i !=
e; ++
i) {
313 SUnit *SuccDep =
D.getSUnit();
315 RemovePred(SuccDep,
D);
319 for (
unsigned i = 0,
e = ChainSuccs.size();
i !=
e; ++
i) {
321 SUnit *SuccDep =
D.getSUnit();
323 RemovePred(SuccDep,
D);
350 AddPred(NewSU, Pred);
364 DelDeps.push_back(std::make_pair(SuccSU,
D));
367 for (
unsigned i = 0,
e = DelDeps.size();
i !=
e; ++
i)
368 RemovePred(DelDeps[
i].first, DelDeps[
i].second);
376 void ScheduleDAGFast::InsertCopiesAndMoveSuccs(
SUnit *SU,
unsigned Reg,
380 SUnit *CopyFromSU = newSUnit(
static_cast<SDNode *
>(
nullptr));
384 SUnit *CopyToSU = newSUnit(
static_cast<SDNode *
>(
nullptr));
397 D.setSUnit(CopyToSU);
399 DelDeps.push_back(std::make_pair(SuccSU, Succ));
402 for (
unsigned i = 0,
e = DelDeps.size();
i !=
e; ++
i) {
403 RemovePred(DelDeps[
i].first, DelDeps[
i].second);
406 FromDep.setLatency(SU->
Latency);
407 AddPred(CopyFromSU, FromDep);
409 ToDep.setLatency(CopyFromSU->
Latency);
410 AddPred(CopyToSU, ToDep);
412 Copies.push_back(CopyFromSU);
413 Copies.push_back(CopyToSU);
437 return N->getSimpleValueType(NumRes);
443 std::vector<SUnit *> &LiveRegDefs,
447 const SDNode *Node =
nullptr) {
451 if (!LiveRegDefs[*AI])
455 if (LiveRegDefs[*AI] == SU)
459 if (Node && LiveRegDefs[*AI]->getNode() == Node)
463 if (RegAdded.
insert(*AI).second) {
464 LRegs.push_back(*AI);
475 bool ScheduleDAGFast::DelayForLiveRegsBottomUp(
SUnit *SU,
477 if (NumLiveRegs == 0)
485 RegAdded, LRegs,
TRI);
489 for (
SDNode *Node = SU->
getNode(); Node; Node = Node->getGluedNode()) {
493 unsigned NumOps = Node->getNumOperands();
494 if (Node->getOperand(NumOps-1).getValueType() ==
MVT::Glue)
499 cast<ConstantSDNode>(Node->getOperand(
i))->getZExtValue();
507 for (; NumVals; --NumVals, ++
i) {
508 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(
i))->getReg();
519 Register Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
520 if (
Reg.isPhysical()) {
521 SDNode *SrcNode = Node->getOperand(2).getNode();
526 if (!Node->isMachineOpcode())
535 return !LRegs.empty();
541 void ScheduleDAGFast::ListScheduleBottomUp() {
542 unsigned CurCycle = 0;
545 ReleasePredecessors(&ExitSU, CurCycle);
548 if (!SUnits.empty()) {
549 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
550 assert(RootSU->
Succs.empty() &&
"Graph root shouldn't have successors!");
552 AvailableQueue.push(RootSU);
560 while (!AvailableQueue.empty()) {
561 bool Delayed =
false;
563 SUnit *CurSU = AvailableQueue.pop();
566 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
569 LRegsMap.
insert(std::make_pair(CurSU, LRegs));
572 NotReady.push_back(CurSU);
573 CurSU = AvailableQueue.pop();
579 if (Delayed && !CurSU) {
584 SUnit *TrySU = NotReady[0];
586 assert(LRegs.size() == 1 &&
"Can't handle this yet!");
587 unsigned Reg = LRegs[0];
601 SUnit *NewDef =
nullptr;
603 NewDef = CopyAndMoveSuccessors(LRDef);
604 if (!DestRC && !NewDef)
606 "register dependency!");
611 InsertCopiesAndMoveSuccs(LRDef,
Reg, DestRC, RC,
Copies);
613 <<
" to SU #" <<
Copies.front()->NodeNum <<
"\n");
619 <<
" to SU #" << TrySU->
NodeNum <<
"\n");
620 LiveRegDefs[
Reg] = NewDef;
632 for (
unsigned i = 0,
e = NotReady.size();
i !=
e; ++
i) {
633 NotReady[
i]->isPending =
false;
636 AvailableQueue.push(NotReady[
i]);
641 ScheduleNodeBottomUp(CurSU, CurCycle);
649 VerifyScheduledSequence(
true);
664 void Schedule()
override;
677 void ScheduleDAGLinearize::ScheduleNode(
SDNode *
N) {
678 if (
N->getNodeId() != 0)
681 if (!
N->isMachineOpcode() &&
690 unsigned NumOps =
N->getNumOperands();
691 if (
unsigned NumLeft = NumOps) {
692 SDNode *GluedOpN =
nullptr;
697 if (NumLeft == NumOps &&
Op.getValueType() ==
MVT::Glue) {
711 if (DI != GluedMap.end() && DI->second !=
N)
716 assert(Degree > 0 &&
"Predecessor over-released!");
727 while (
SDNode *Glued =
N->getGluedUser())
732 void ScheduleDAGLinearize::Schedule() {
733 LLVM_DEBUG(
dbgs() <<
"********** DAG Linearization **********\n");
736 unsigned DAGSize = 0;
737 for (
SDNode &Node : DAG->allnodes()) {
741 unsigned Degree =
N->use_size();
742 N->setNodeId(Degree);
743 unsigned NumVals =
N->getNumValues();
744 if (NumVals &&
N->getValueType(NumVals-1) ==
MVT::Glue &&
745 N->hasAnyUseOfValue(NumVals-1)) {
753 if (
N->isMachineOpcode() ||
758 for (
unsigned i = 0,
e = Glues.size();
i !=
e; ++
i) {
760 SDNode *GUser = GluedMap[Glue];
775 ScheduleNode(DAG->getRoot().getNode());
781 DAG->getUseInstrRefDebugInfo());
786 unsigned NumNodes =
Sequence.size();
788 for (
unsigned i = 0;
i != NumNodes; ++
i) {
791 Emitter.EmitNode(
N,
false,
false, VRBaseMap);
794 if (
N->getHasDebugValue()) {
796 for (
auto DV : DAG->GetDbgValues(
N)) {
797 if (!DV->isEmitted())
798 if (
auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap))
799 BB->insert(InsertPos, DbgMI);
806 InsertPos = Emitter.getInsertPos();
807 return Emitter.getBlock();
816 return new ScheduleDAGFast(*IS->
MF);
821 return new ScheduleDAGLinearize(*IS->
MF);
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
ScheduleDAGSDNodes * createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createDAGLinearizer - This creates a "no-scheduling" scheduler which linearize the DAG using topologi...
static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, std::vector< SUnit * > &LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI, const SDNode *Node=nullptr)
CheckForLiveRegDef - Return true and update live register vector if the specified register def of the...
This is an optimization pass for GlobalISel generic memory operations.
virtual const TargetRegisterClass * getCrossCopyRegClass(const TargetRegisterClass *RC) const
Returns a legal register class to copy a register in the specified class to or from.
static RegisterScheduler linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", createDAGLinearizer)
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
@ Artificial
Arbitrary strong DAG edge (no real dependence).
bool isAvailable
True once available.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Reg
All possible values of the reg field in the ModR/M byte.
bool isCommutable
Is a commutable instruction.
ScheduleDAGSDNodes * createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createFastDAGScheduler - This creates a "fast" scheduler.
Represents one node in the SelectionDAG.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
SmallVector< SDep, 4 > Succs
All sunit successors.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
unsigned const TargetRegisterInfo * TRI
@ INLINEASM
INLINEASM - Represents an inline asm block.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
TargetInstrInfo - Interface to description of machine instruction set.
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
unsigned short Latency
Node latency.
static RegisterScheduler fastDAGScheduler("fast", "Fast suboptimal list scheduling", createFastDAGScheduler)
unsigned NodeNum
Entry # of node in the node vector.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
const MCPhysReg * getImplicitDefs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
const HexagonInstrInfo * TII
Describe properties that are true of each instruction in the target description file.
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
iterator_range< use_iterator > uses()
static bool isRegDefKind(unsigned Flag)
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
STATISTIC(NumFunctions, "Total number of functions")
@ Data
Regular data dependence (aka true-dependence).
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
SDNode * getGluedUser() const
If this node has a glue value with a user, return the user (there is at most one).
bool isPending
True once pending.
static SDNode * findGluedUser(SDNode *N)
findGluedUser - Find the representative use of a glue value by walking the use chain.
static bool isRegDefEarlyClobberKind(unsigned Flag)
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
void setNodeId(int Id)
Set unique node id.
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
unsigned getReg() const
Returns the register associated with this edge.
bool isScheduled
True once scheduled.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
int getNodeId() const
Return the unique node id.
const TargetRegisterClass * CopySrcRC
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool isOperandOf(const SDNode *N) const
Return true if this node is an operand of N.
static bool isClobberKind(unsigned Flag)
@ Barrier
An unknown scheduling barrier.
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Wrapper class representing virtual and physical registers.
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool isTwoAddress
Is a two-address instruction.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Scheduling unit. This is a node in the scheduling DAG.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
const TargetRegisterClass * getMinimalPhysRegClass(MCRegister Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified no...
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
MCRegAliasIterator enumerates all registers aliasing Reg.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
const MCPhysReg * ImplicitDefs
iterator insert(iterator I, T &&Elt)