15 #define DEBUG_TYPE "pre-RA-sched"
31 cl::desc(
"Stress test instruction scheduling"));
34 void SchedulingPriorityQueue::anchor() { }
38 TII(
TM.getInstrInfo()),
39 TRI(
TM.getRegisterInfo()),
40 MF(mf),
MRI(mf.getRegInfo()),
71 if (!Required &&
I->getSUnit() == D.
getSUnit())
76 SUnit *PredSU =
I->getSUnit();
81 EE = PredSU->
Succs.end(); II != EE; ++II) {
82 if (*II == ForwardD) {
98 assert(
NumPreds < UINT_MAX &&
"NumPreds will overflow!");
99 assert(N->
NumSuccs < UINT_MAX &&
"NumSuccs will overflow!");
108 assert(
NumPredsLeft < UINT_MAX &&
"NumPredsLeft will overflow!");
117 assert(N->
NumSuccsLeft < UINT_MAX &&
"NumSuccsLeft will overflow!");
122 N->
Succs.push_back(P);
144 assert(Succ != N->
Succs.end() &&
"Mismatching preds / succs lists!");
145 N->
Succs.erase(Succ);
149 assert(
NumPreds > 0 &&
"NumPreds will underflow!");
150 assert(N->
NumSuccs > 0 &&
"NumSuccs will underflow!");
158 assert(
NumPredsLeft > 0 &&
"NumPredsLeft will underflow!");
166 assert(N->
NumSuccsLeft > 0 &&
"NumSuccsLeft will underflow!");
170 if (
P.getLatency() != 0) {
178 void SUnit::setDepthDirty() {
179 if (!isDepthCurrent)
return;
184 SU->isDepthCurrent =
false;
186 E = SU->
Succs.end();
I != E; ++
I) {
187 SUnit *SuccSU =
I->getSUnit();
188 if (SuccSU->isDepthCurrent)
191 }
while (!WorkList.
empty());
195 if (!isHeightCurrent)
return;
200 SU->isHeightCurrent =
false;
202 E = SU->
Preds.end();
I != E; ++
I) {
203 SUnit *PredSU =
I->getSUnit();
204 if (PredSU->isHeightCurrent)
207 }
while (!WorkList.
empty());
218 isDepthCurrent =
true;
229 isHeightCurrent =
true;
234 void SUnit::ComputeDepth() {
241 unsigned MaxPredDepth = 0;
243 E = Cur->
Preds.end();
I != E; ++
I) {
244 SUnit *PredSU =
I->getSUnit();
245 if (PredSU->isDepthCurrent)
246 MaxPredDepth = std::max(MaxPredDepth,
247 PredSU->Depth +
I->getLatency());
256 if (MaxPredDepth != Cur->Depth) {
258 Cur->Depth = MaxPredDepth;
260 Cur->isDepthCurrent =
true;
262 }
while (!WorkList.
empty());
267 void SUnit::ComputeHeight() {
274 unsigned MaxSuccHeight = 0;
276 E = Cur->
Succs.end();
I != E; ++
I) {
277 SUnit *SuccSU =
I->getSUnit();
278 if (SuccSU->isHeightCurrent)
279 MaxSuccHeight = std::max(MaxSuccHeight,
280 SuccSU->Height +
I->getLatency());
289 if (MaxSuccHeight != Cur->Height) {
291 Cur->Height = MaxSuccHeight;
293 Cur->isHeightCurrent =
true;
295 }
while (!WorkList.
empty());
303 unsigned MaxDepth = BestI->getSUnit()->getDepth();
309 if (BestI !=
Preds.begin())
313 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
335 if (
Preds.size() != 0) {
336 dbgs() <<
" Predecessors:\n";
340 switch (
I->getKind()) {
346 dbgs() <<
"SU(" <<
I->getSUnit()->NodeNum <<
")";
347 if (
I->isArtificial())
349 dbgs() <<
": Latency=" <<
I->getLatency();
350 if (
I->isAssignedRegDep())
355 if (
Succs.size() != 0) {
356 dbgs() <<
" Successors:\n";
360 switch (
I->getKind()) {
366 dbgs() <<
"SU(" <<
I->getSUnit()->NodeNum <<
")";
367 if (
I->isArtificial())
369 dbgs() <<
": Latency=" <<
I->getLatency();
370 if (
I->isAssignedRegDep())
384 bool AnyNotSched =
false;
385 unsigned DeadNodes = 0;
386 for (
unsigned i = 0, e =
SUnits.size(); i != e; ++i) {
387 if (!
SUnits[i].isScheduled) {
388 if (
SUnits[i].NumPreds == 0 &&
SUnits[i].NumSuccs == 0) {
393 dbgs() <<
"*** Scheduling failed! ***\n";
395 dbgs() <<
"has not been scheduled!\n";
398 if (
SUnits[i].isScheduled &&
399 (isBottomUp ?
SUnits[i].getHeight() :
SUnits[i].getDepth()) >
402 dbgs() <<
"*** Scheduling failed! ***\n";
404 dbgs() <<
"has an unexpected "
405 << (isBottomUp ?
"Height" :
"Depth") <<
" value!\n";
409 if (
SUnits[i].NumSuccsLeft != 0) {
411 dbgs() <<
"*** Scheduling failed! ***\n";
413 dbgs() <<
"has successors left!\n";
417 if (
SUnits[i].NumPredsLeft != 0) {
419 dbgs() <<
"*** Scheduling failed! ***\n";
421 dbgs() <<
"has predecessors left!\n";
426 assert(!AnyNotSched);
427 return SUnits.size() - DeadNodes;
461 unsigned DAGSize = SUnits.size();
462 std::vector<SUnit*> WorkList;
465 Index2Node.resize(DAGSize);
466 Node2Index.resize(DAGSize);
470 WorkList.push_back(ExitSU);
471 for (
unsigned i = 0, e = DAGSize; i != e; ++i) {
472 SUnit *SU = &SUnits[i];
474 unsigned Degree = SU->
Succs.size();
476 Node2Index[NodeNum] = Degree;
480 assert(SU->
Succs.empty() &&
"SUnit should have no successors");
482 WorkList.push_back(SU);
487 while (!WorkList.empty()) {
488 SUnit *SU = WorkList.back();
494 SUnit *SU =
I->getSUnit();
498 WorkList.push_back(SU);
506 for (
unsigned i = 0, e = DAGSize; i != e; ++i) {
507 SUnit *SU = &SUnits[i];
510 assert(Node2Index[SU->
NodeNum] > Node2Index[
I->getSUnit()->NodeNum] &&
511 "Wrong topological sorting");
520 int UpperBound, LowerBound;
521 LowerBound = Node2Index[Y->
NodeNum];
522 UpperBound = Node2Index[X->
NodeNum];
523 bool HasLoop =
false;
525 if (LowerBound < UpperBound) {
528 DFS(Y, UpperBound, HasLoop);
529 assert(!HasLoop &&
"Inserted edge creates a loop!");
531 Shift(Visited, LowerBound, UpperBound);
545 void ScheduleDAGTopologicalSort::DFS(
const SUnit *SU,
int UpperBound,
547 std::vector<const SUnit*> WorkList;
548 WorkList.
reserve(SUnits.size());
550 WorkList.push_back(SU);
552 SU = WorkList.back();
555 for (
int I = SU->
Succs.size()-1;
I >= 0; --
I) {
556 unsigned s = SU->
Succs[
I].getSUnit()->NodeNum;
558 if (s >= Node2Index.size())
560 if (Node2Index[s] == UpperBound) {
565 if (!Visited.
test(s) && Node2Index[s] < UpperBound) {
566 WorkList.push_back(SU->
Succs[
I].getSUnit());
569 }
while (!WorkList.empty());
574 void ScheduleDAGTopologicalSort::Shift(
BitVector& Visited,
int LowerBound,
580 for (i = LowerBound; i <= UpperBound; ++i) {
582 int w = Index2Node[i];
583 if (Visited.
test(w)) {
589 Allocate(w, i - shift);
593 for (
unsigned j = 0; j < L.size(); ++j) {
594 Allocate(L[j], i - shift);
607 I = TargetSU->
Preds.begin(), E = TargetSU->
Preds.end();
I != E; ++
I)
608 if (
I->isAssignedRegDep() &&
616 const SUnit *TargetSU) {
619 int UpperBound, LowerBound;
620 LowerBound = Node2Index[TargetSU->
NodeNum];
621 UpperBound = Node2Index[SU->
NodeNum];
622 bool HasLoop =
false;
624 if (LowerBound < UpperBound) {
627 DFS(TargetSU, UpperBound, HasLoop);
633 void ScheduleDAGTopologicalSort::Allocate(
int n,
int index) {
634 Node2Index[n] = index;
635 Index2Node[index] = n;
640 : SUnits(sunits), ExitSU(exitsu) {}
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
void push_back(const T &Elt)
virtual ~ScheduleHazardRecognizer()
void removePred(const SDep &D)
SmallVector< SDep, 4 > Preds
A register anti-dependedence (aka WAR).
void dumpAll(const ScheduleDAG *G) const
unsigned getHeight() const
const HexagonInstrInfo * TII
T LLVM_ATTRIBUTE_UNUSED_RESULT pop_back_val()
Regular data dependence (aka true-dependence).
void InitDAGTopologicalSorting()
A register output-dependence (aka WAW).
bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const
static cl::opt< bool > StressSchedOpt("stress-sched", cl::Hidden, cl::init(false), cl::desc("Stress test instruction scheduling"))
void setDepthToAtLeast(unsigned NewDepth)
void setHeightToAtLeast(unsigned NewHeight)
initializer< Ty > init(const Ty &Val)
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle.
void clearDAG()
clearDAG - clear the DAG state (between regions).
ItTy next(ItTy it, Dist n)
unsigned getLatency() const
void RemovePred(SUnit *M, SUnit *N)
Any other ordering dependency.
const MCInstrDesc & get(unsigned Opcode) const
bool test(unsigned Idx) const
raw_ostream & dbgs()
dbgs - Return a circular-buffered debug stream.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
IsReachable - Checks if SU is reachable from TargetSU.
void biasCriticalPath()
Order this node's predecessor edges such that the critical path edge occurs first.
ScheduleDAG(MachineFunction &mf)
unsigned getDepth() const
unsigned VerifyScheduledDAG(bool isBottomUp)
const TargetRegisterInfo * TRI
unsigned short NumRegDefsLeft
Kind getKind() const
getKind - Return an enum value representing the kind of the dependence.
const TargetInstrInfo * TII
virtual void dumpNode(const SUnit *SU) const =0
bool addPred(const SDep &D, bool Required=true)
SmallVector< SDep, 4 > Succs
void AddPred(SUnit *Y, SUnit *X)
const MCRegisterInfo & MRI
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml","ocaml 3.10-compatible collector")
std::vector< SUnit > SUnits
ScheduleDAGTopologicalSort(std::vector< SUnit > &SUnits, SUnit *ExitSU)
static RegisterPass< NVPTXAllocaHoisting > X("alloca-hoisting","Hoisting alloca instructions in non-entry ""blocks to the entry block")
void dump(const ScheduleDAG *G) const
SUnit - Scheduling unit. This is a node in the scheduling DAG.
bool isMachineOpcode() const
unsigned getMachineOpcode() const