misched: Infrastructure for weak DAG edges.
This adds support for weak DAG edges to the general scheduling
infrastructure in preparation for MachineScheduler support for
heuristics based on weak edges.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@167738 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp
index a4817d0..71cc072 100644
--- a/lib/CodeGen/MachineScheduler.cpp
+++ b/lib/CodeGen/MachineScheduler.cpp
@@ -310,6 +310,10 @@
void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
SUnit *SuccSU = SuccEdge->getSUnit();
+ if (SuccEdge->isWeak()) {
+ --SuccSU->WeakPredsLeft;
+ return;
+ }
#ifndef NDEBUG
if (SuccSU->NumPredsLeft == 0) {
dbgs() << "*** Scheduling failed! ***\n";
@@ -338,6 +342,10 @@
void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
SUnit *PredSU = PredEdge->getSUnit();
+ if (PredEdge->isWeak()) {
+ --PredSU->WeakSuccsLeft;
+ return;
+ }
#ifndef NDEBUG
if (PredSU->NumSuccsLeft == 0) {
dbgs() << "*** Scheduling failed! ***\n";
@@ -530,17 +538,20 @@
}
// Release all DAG roots for scheduling.
+//
+// Nodes with unreleased weak edges can still be roots.
void ScheduleDAGMI::releaseRoots() {
SmallVector<SUnit*, 16> BotRoots;
for (std::vector<SUnit>::iterator
I = SUnits.begin(), E = SUnits.end(); I != E; ++I) {
+ SUnit *SU = &(*I);
// A SUnit is ready to top schedule if it has no predecessors.
- if (I->Preds.empty())
- SchedImpl->releaseTopNode(&(*I));
+ if (!I->NumPredsLeft && SU != &EntrySU)
+ SchedImpl->releaseTopNode(SU);
// A SUnit is ready to bottom schedule if it has no successors.
- if (I->Succs.empty())
- BotRoots.push_back(&(*I));
+ if (!I->NumSuccsLeft && SU != &ExitSU)
+ BotRoots.push_back(SU);
}
// Release bottom roots in reverse order so the higher priority nodes appear
// first. This is more natural and slightly more efficient.
@@ -555,13 +566,12 @@
// Initialize the strategy before modifying the DAG.
SchedImpl->initialize(this);
- // Release edges from the special Entry node or to the special Exit node.
+ // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
+ releaseRoots();
+
releaseSuccessors(&EntrySU);
releasePredecessors(&ExitSU);
- // Release all DAG roots for scheduling.
- releaseRoots();
-
SchedImpl->registerRoots();
CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp
index d57bc73..4284c42 100644
--- a/lib/CodeGen/PostRASchedulerList.cpp
+++ b/lib/CodeGen/PostRASchedulerList.cpp
@@ -111,9 +111,6 @@
/// added to the AvailableQueue.
std::vector<SUnit*> PendingQueue;
- /// Topo - A topological ordering for SUnits.
- ScheduleDAGTopologicalSort Topo;
-
/// HazardRec - The hazard recognizer to use.
ScheduleHazardRecognizer *HazardRec;
@@ -198,7 +195,7 @@
AliasAnalysis *AA, const RegisterClassInfo &RCI,
TargetSubtargetInfo::AntiDepBreakMode AntiDepMode,
SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs)
- : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), Topo(SUnits), AA(AA),
+ : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), AA(AA),
LiveRegs(TRI->getNumRegs())
{
const TargetMachine &TM = MF.getTarget();
@@ -580,10 +577,14 @@
//===----------------------------------------------------------------------===//
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
-/// the PendingQueue if the count reaches zero. Also update its cycle bound.
+/// the PendingQueue if the count reaches zero.
void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
SUnit *SuccSU = SuccEdge->getSUnit();
+ if (SuccEdge->isArtificial()) {
+ --SuccSU->WeakPredsLeft;
+ return;
+ }
#ifndef NDEBUG
if (SuccSU->NumPredsLeft == 0) {
dbgs() << "*** Scheduling failed! ***\n";
@@ -653,8 +654,7 @@
// Add all leaves to Available queue.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
- bool available = SUnits[i].Preds.empty();
- if (available) {
+ if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) {
AvailableQueue.push(&SUnits[i]);
SUnits[i].isAvailable = true;
}
diff --git a/lib/CodeGen/ScheduleDAG.cpp b/lib/CodeGen/ScheduleDAG.cpp
index 9a65071..6224036 100644
--- a/lib/CodeGen/ScheduleDAG.cpp
+++ b/lib/CodeGen/ScheduleDAG.cpp
@@ -62,10 +62,14 @@
/// addPred - This adds the specified edge as a pred of the current node if
/// not already. It also adds the current node as a successor of the
/// specified node.
-bool SUnit::addPred(const SDep &D) {
+bool SUnit::addPred(const SDep &D, bool Required) {
// If this node already has this depenence, don't add a redundant one.
for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end();
I != E; ++I) {
+ // Zero-latency weak edges may be added purely for heuristic ordering. Don't
+ // add them if another kind of edge already exists.
+ if (!Required && I->getSUnit() == D.getSUnit())
+ return false;
if (I->overlaps(D)) {
// Extend the latency if needed. Equivalent to removePred(I) + addPred(D).
if (I->getLatency() < D.getLatency()) {
@@ -96,13 +100,26 @@
++NumPreds;
++N->NumSuccs;
}
+ // SD scheduler relies on artificial edges to enforce physreg
+ // antidependence, so it doesn't treat them as weak edges.
+ bool isWeak = D.isWeak() && N->isInstr();
if (!N->isScheduled) {
- assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!");
- ++NumPredsLeft;
+ if (isWeak) {
+ ++WeakPredsLeft;
+ }
+ else {
+ assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!");
+ ++NumPredsLeft;
+ }
}
if (!isScheduled) {
- assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
- ++N->NumSuccsLeft;
+ if (isWeak) {
+ ++N->WeakSuccsLeft;
+ }
+ else {
+ assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
+ ++N->NumSuccsLeft;
+ }
}
Preds.push_back(D);
N->Succs.push_back(P);
@@ -143,13 +160,22 @@
--NumPreds;
--N->NumSuccs;
}
+ bool isWeak = D.isWeak() && N->isInstr();
if (!N->isScheduled) {
- assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");
- --NumPredsLeft;
+ if (isWeak)
+ --WeakPredsLeft;
+ else {
+ assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");
+ --NumPredsLeft;
+ }
}
if (!isScheduled) {
- assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");
- --N->NumSuccsLeft;
+ if (isWeak)
+ --N->WeakSuccsLeft;
+ else {
+ assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");
+ --N->NumSuccsLeft;
+ }
}
if (P.getLatency() != 0) {
this->setDepthDirty();
@@ -292,6 +318,10 @@
dbgs() << " # preds left : " << NumPredsLeft << "\n";
dbgs() << " # succs left : " << NumSuccsLeft << "\n";
+ if (WeakPredsLeft)
+ dbgs() << " # weak preds left : " << WeakPredsLeft << "\n";
+ if (WeakSuccsLeft)
+ dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n";
dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n";
dbgs() << " Latency : " << Latency << "\n";
dbgs() << " Depth : " << Depth << "\n";
@@ -429,6 +459,8 @@
Node2Index.resize(DAGSize);
// Initialize the data structures.
+ if (ExitSU)
+ WorkList.push_back(ExitSU);
for (unsigned i = 0, e = DAGSize; i != e; ++i) {
SUnit *SU = &SUnits[i];
int NodeNum = SU->NodeNum;
@@ -448,11 +480,12 @@
while (!WorkList.empty()) {
SUnit *SU = WorkList.back();
WorkList.pop_back();
- Allocate(SU->NodeNum, --Id);
+ if (SU->NodeNum < DAGSize)
+ Allocate(SU->NodeNum, --Id);
for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
I != E; ++I) {
SUnit *SU = I->getSUnit();
- if (!--Node2Index[SU->NodeNum])
+ if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])
// If all dependencies of the node are processed already,
// then the node can be computed now.
WorkList.push_back(SU);
@@ -513,7 +546,10 @@
WorkList.pop_back();
Visited.set(SU->NodeNum);
for (int I = SU->Succs.size()-1; I >= 0; --I) {
- int s = SU->Succs[I].getSUnit()->NodeNum;
+ unsigned s = SU->Succs[I].getSUnit()->NodeNum;
+ // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
+ if (s >= Node2Index.size())
+ continue;
if (Node2Index[s] == UpperBound) {
HasLoop = true;
return;
@@ -554,15 +590,16 @@
}
-/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
-/// create a cycle.
-bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
- if (IsReachable(TargetSU, SU))
+/// WillCreateCycle - Returns true if adding an edge to TargetSU from SU will
+/// create a cycle. If so, it is not safe to call AddPred(TargetSU, SU).
+bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
+ // Is SU reachable from TargetSU via successor edges?
+ if (IsReachable(SU, TargetSU))
return true;
- for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
- I != E; ++I)
+ for (SUnit::pred_iterator
+ I = TargetSU->Preds.begin(), E = TargetSU->Preds.end(); I != E; ++I)
if (I->isAssignedRegDep() &&
- IsReachable(TargetSU, I->getSUnit()))
+ IsReachable(SU, I->getSUnit()))
return true;
return false;
}
@@ -592,6 +629,7 @@
}
ScheduleDAGTopologicalSort::
-ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits) : SUnits(sunits) {}
+ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
+ : SUnits(sunits), ExitSU(exitsu) {}
ScheduleHazardRecognizer::~ScheduleHazardRecognizer() {}
diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp
index a4d4a93..836349f 100644
--- a/lib/CodeGen/ScheduleDAGInstrs.cpp
+++ b/lib/CodeGen/ScheduleDAGInstrs.cpp
@@ -245,21 +245,26 @@
if (UseSU == SU)
continue;
- SDep dep(SU, SDep::Data, *Alias);
-
// Adjust the dependence latency using operand def/use information,
// then allow the target to perform its own adjustments.
int UseOp = UseList[i].OpIdx;
- MachineInstr *RegUse = UseOp < 0 ? 0 : UseSU->getInstr();
- dep.setLatency(
+ MachineInstr *RegUse = 0;
+ SDep Dep;
+ if (UseOp < 0)
+ Dep = SDep(SU, SDep::Artificial);
+ else {
+ Dep = SDep(SU, SDep::Data, *Alias);
+ RegUse = UseSU->getInstr();
+ Dep.setMinLatency(
+ SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
+ RegUse, UseOp, /*FindMin=*/true));
+ }
+ Dep.setLatency(
SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
RegUse, UseOp, /*FindMin=*/false));
- dep.setMinLatency(
- SchedModel.computeOperandLatency(SU->getInstr(), OperIdx,
- RegUse, UseOp, /*FindMin=*/true));
- ST.adjustSchedDependency(SU, UseSU, dep);
- UseSU->addPred(dep);
+ ST.adjustSchedDependency(SU, UseSU, Dep);
+ UseSU->addPred(Dep);
}
}
}
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
index c554569..dc8f0ee 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
@@ -156,7 +156,7 @@
CodeGenOpt::Level OptLevel)
: ScheduleDAGSDNodes(mf),
NeedLatency(needlatency), AvailableQueue(availqueue), CurCycle(0),
- Topo(SUnits) {
+ Topo(SUnits, NULL) {
const TargetMachine &tm = mf.getTarget();
if (DisableSchedCycles || !NeedLatency)
diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGVLIW.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGVLIW.cpp
index 30f03ac..f8ca7b1 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGVLIW.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGVLIW.cpp
@@ -123,6 +123,8 @@
llvm_unreachable(0);
}
#endif
+ assert(!D.isWeak() && "unexpected artificial DAG edge");
+
--SuccSU->NumPredsLeft;
SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());