28#define DEBUG_TYPE "pre-RA-sched"
46 struct FastPriorityQueue {
49 bool empty()
const {
return Queue.empty(); }
56 if (empty())
return nullptr;
57 return Queue.pop_back_val();
67 FastPriorityQueue AvailableQueue;
72 unsigned NumLiveRegs = 0
u;
73 std::vector<SUnit*> LiveRegDefs;
74 std::vector<unsigned> LiveRegCycles;
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();
113void ScheduleDAGFast::Schedule() {
117 LiveRegDefs.resize(
TRI->getNumRegs(),
nullptr);
118 LiveRegCycles.resize(
TRI->getNumRegs(), 0);
121 BuildSchedGraph(
nullptr);
126 ListScheduleBottomUp();
135void ScheduleDAGFast::ReleasePred(
SUnit *SU,
SDep *PredEdge) {
140 dbgs() <<
"*** Scheduling failed! ***\n";
142 dbgs() <<
" has been released too many times!\n";
152 AvailableQueue.push(PredSU);
156void ScheduleDAGFast::ReleasePredecessors(
SUnit *SU,
unsigned CurCycle) {
159 ReleasePred(SU, &Pred);
165 if (!LiveRegDefs[Pred.
getReg()]) {
168 LiveRegCycles[Pred.
getReg()] = CurCycle;
177void 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;
206SUnit *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);
220 else if (VT == MVT::Other)
223 for (
const SDValue &Op :
N->op_values()) {
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);
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) {
312 SDep D = NodeSuccs[i];
313 SUnit *SuccDep =
D.getSUnit();
315 RemovePred(SuccDep,
D);
319 for (
unsigned i = 0, e = ChainSuccs.
size(); i != e; ++i) {
320 SDep D = ChainSuccs[i];
321 SUnit *SuccDep =
D.getSUnit();
323 RemovePred(SuccDep,
D);
350 AddPred(NewSU, Pred);
367 for (
unsigned i = 0, e = DelDeps.
size(); i != e; ++i)
368 RemovePred(DelDeps[i].first, DelDeps[i].second);
376void 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);
430 "Physical reg def must be in implicit def list!");
438 return N->getSimpleValueType(NumRes);
444 std::vector<SUnit *> &LiveRegDefs,
452 if (!LiveRegDefs[*AI])
456 if (LiveRegDefs[*AI] == SU)
460 if (
Node && LiveRegDefs[*AI]->getNode() ==
Node)
464 if (RegAdded.
insert(*AI).second) {
476bool ScheduleDAGFast::DelayForLiveRegsBottomUp(
SUnit *SU,
478 if (NumLiveRegs == 0)
486 RegAdded, LRegs,
TRI);
494 unsigned NumOps =
Node->getNumOperands();
495 if (
Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
500 cast<ConstantSDNode>(
Node->getOperand(i))->getZExtValue();
508 for (; NumVals; --NumVals, ++i) {
509 unsigned Reg = cast<RegisterSDNode>(
Node->getOperand(i))->getReg();
521 if (
Reg.isPhysical()) {
522 SDNode *SrcNode =
Node->getOperand(2).getNode();
527 if (!
Node->isMachineOpcode())
533 return !LRegs.
empty();
539void ScheduleDAGFast::ListScheduleBottomUp() {
540 unsigned CurCycle = 0;
543 ReleasePredecessors(&ExitSU, CurCycle);
546 if (!SUnits.empty()) {
547 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
548 assert(RootSU->
Succs.empty() &&
"Graph root shouldn't have successors!");
550 AvailableQueue.push(RootSU);
558 while (!AvailableQueue.empty()) {
559 bool Delayed =
false;
561 SUnit *CurSU = AvailableQueue.pop();
564 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
567 LRegsMap.
insert(std::make_pair(CurSU, LRegs));
571 CurSU = AvailableQueue.pop();
577 if (Delayed && !CurSU) {
582 SUnit *TrySU = NotReady[0];
584 assert(LRegs.
size() == 1 &&
"Can't handle this yet!");
585 unsigned Reg = LRegs[0];
589 TRI->getMinimalPhysRegClass(Reg, VT);
599 SUnit *NewDef =
nullptr;
601 NewDef = CopyAndMoveSuccessors(LRDef);
602 if (!DestRC && !NewDef)
604 "register dependency!");
609 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC,
Copies);
611 <<
" to SU #" <<
Copies.front()->NodeNum <<
"\n");
617 <<
" to SU #" << TrySU->
NodeNum <<
"\n");
618 LiveRegDefs[
Reg] = NewDef;
630 for (
unsigned i = 0, e = NotReady.
size(); i != e; ++i) {
631 NotReady[i]->isPending =
false;
633 if (NotReady[i]->isAvailable)
634 AvailableQueue.push(NotReady[i]);
639 ScheduleNodeBottomUp(CurSU, CurCycle);
647 VerifyScheduledSequence(
true);
675void ScheduleDAGLinearize::ScheduleNode(
SDNode *
N) {
676 if (
N->getNodeId() != 0)
679 if (!
N->isMachineOpcode() &&
688 unsigned NumOps =
N->getNumOperands();
689 if (
unsigned NumLeft = NumOps) {
690 SDNode *GluedOpN =
nullptr;
695 if (NumLeft == NumOps &&
Op.getValueType() == MVT::Glue) {
709 if (DI != GluedMap.end() && DI->second !=
N)
714 assert(Degree > 0 &&
"Predecessor over-released!");
725 while (
SDNode *Glued =
N->getGluedUser())
730void ScheduleDAGLinearize::Schedule() {
731 LLVM_DEBUG(
dbgs() <<
"********** DAG Linearization **********\n");
734 unsigned DAGSize = 0;
739 unsigned Degree =
N->use_size();
740 N->setNodeId(Degree);
741 unsigned NumVals =
N->getNumValues();
742 if (NumVals &&
N->getValueType(NumVals-1) == MVT::Glue &&
743 N->hasAnyUseOfValue(NumVals-1)) {
747 GluedMap.insert(std::make_pair(
N,
User));
751 if (
N->isMachineOpcode() ||
756 for (
unsigned i = 0, e = Glues.
size(); i != e; ++i) {
758 SDNode *GUser = GluedMap[Glue];
773 ScheduleNode(DAG->getRoot().getNode());
783 unsigned NumNodes =
Sequence.size();
785 for (
unsigned i = 0; i != NumNodes; ++i) {
788 Emitter.EmitNode(
N,
false,
false, VRBaseMap);
791 if (
N->getHasDebugValue()) {
793 for (
auto *DV : DAG->GetDbgValues(
N)) {
794 if (!DV->isEmitted())
795 if (
auto *DbgMI =
Emitter.EmitDbgValue(DV, VRBaseMap))
796 BB->
insert(InsertPos, DbgMI);
803 InsertPos =
Emitter.getInsertPos();
813 return new ScheduleDAGFast(*IS->
MF);
818 return new ScheduleDAGLinearize(*IS->
MF);
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
dxil DXContainer Global Emitter
const HexagonInstrInfo * TII
unsigned const TargetRegisterInfo * TRI
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified no...
static RegisterScheduler fastDAGScheduler("fast", "Fast suboptimal list scheduling", createFastDAGScheduler)
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...
static RegisterScheduler linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", createDAGLinearizer)
static SDNode * findGluedUser(SDNode *N)
findGluedUser - Find the representative use of a glue value by walking the use chain.
This file defines the SmallSet class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
static bool isClobberKind(unsigned Flag)
static bool isRegDefKind(unsigned Flag)
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag.
static bool isRegDefEarlyClobberKind(unsigned Flag)
Describe properties that are true of each instruction in the target description file.
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
ArrayRef< MCPhysReg > implicit_defs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
MCRegAliasIterator enumerates all registers aliasing Reg.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
Wrapper class representing virtual and physical registers.
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Represents one node in the SelectionDAG.
int getNodeId() const
Return the unique node id.
SDNode * getGluedUser() const
If this node has a glue value with a user, return the user (there is at most one).
iterator_range< use_iterator > uses()
void setNodeId(int Id)
Set unique node id.
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
bool isOperandOf(const SDNode *N) const
Return true if this node is an operand of N.
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
@ Data
Regular data dependence (aka true-dependence).
@ Barrier
An unknown scheduling barrier.
@ Artificial
Arbitrary strong DAG edge (no real dependence).
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
unsigned getReg() const
Returns the register associated with this edge.
Scheduling unit. This is a node in the scheduling DAG.
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
unsigned NodeNum
Entry # of node in the node vector.
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
unsigned short Latency
Node latency.
bool isPending
True once pending.
bool isScheduled
True once scheduled.
bool isAvailable
True once available.
SmallVector< SDep, 4 > Succs
All sunit successors.
const TargetRegisterClass * CopySrcRC
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
bool isTwoAddress
Is a two-address instruction.
bool isCommutable
Is a commutable instruction.
SmallVector< SDep, 4 > Preds
All sunit predecessors.
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one.
std::vector< SUnit * > Sequence
The schedule. Null SUnit*'s represent noop instructions.
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
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.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Level
Code generation optimization level.
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
@ CopyToReg
CopyToReg - This node has three operands: a chain, a register number to set to this value,...
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
@ INLINEASM
INLINEASM - Represents an inline asm block.
Reg
All possible values of the reg field in the ModR/M byte.
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
ScheduleDAGSDNodes * createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createDAGLinearizer - This creates a "no-scheduling" scheduler which linearize the DAG using topologi...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
ScheduleDAGSDNodes * createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createFastDAGScheduler - This creates a "fast" scheduler.
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.