Do a scheduling pass ignoring anti-dependencies to identify candidate registers that should be renamed.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@85939 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/PostRASchedulerList.cpp b/lib/CodeGen/PostRASchedulerList.cpp
index 7e85c48..d5edb36 100644
--- a/lib/CodeGen/PostRASchedulerList.cpp
+++ b/lib/CodeGen/PostRASchedulerList.cpp
@@ -175,10 +175,11 @@
void FixupKills(MachineBasicBlock *MBB);
private:
- void ReleaseSucc(SUnit *SU, SDep *SuccEdge);
- void ReleaseSuccessors(SUnit *SU);
- void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
- void ListScheduleTopDown();
+ void ReleaseSucc(SUnit *SU, SDep *SuccEdge, bool IgnoreAntiDep);
+ void ReleaseSuccessors(SUnit *SU, bool IgnoreAntiDep);
+ void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle, bool IgnoreAntiDep);
+ void ListScheduleTopDown(
+ AntiDepBreaker::CandidateMap *AntiDepCandidates);
void StartBlockForKills(MachineBasicBlock *BB);
// ToggleKillFlag - Toggle a register operand kill flag. Other
@@ -320,15 +321,32 @@
BuildSchedGraph(AA);
if (AntiDepBreak != NULL) {
+ AntiDepBreaker::CandidateMap AntiDepCandidates;
+ const bool NeedCandidates = AntiDepBreak->NeedCandidates();
+
for (unsigned i = 0, Trials = AntiDepBreak->GetMaxTrials();
i < Trials; ++i) {
- DEBUG(errs() << "********** Break Anti-Deps, Trial " <<
+ DEBUG(errs() << "\n********** Break Anti-Deps, Trial " <<
i << " **********\n");
+
+ // If candidates are required, then schedule forward ignoring
+ // anti-dependencies to collect the candidate operands for
+ // anti-dependence breaking. The candidates will be the def
+ // operands for the anti-dependencies that if broken would allow
+ // an improved schedule
+ if (NeedCandidates) {
+ DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
+ SUnits[su].dumpAll(this));
+
+ AntiDepCandidates.clear();
+ AvailableQueue.initNodes(SUnits);
+ ListScheduleTopDown(&AntiDepCandidates);
+ AvailableQueue.releaseState();
+ }
+
unsigned Broken =
- AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos,
- InsertPosIndex);
- if (Broken == 0)
- break;
+ AntiDepBreak->BreakAntiDependencies(SUnits, AntiDepCandidates,
+ Begin, InsertPos, InsertPosIndex);
// We made changes. Update the dependency graph.
// Theoretically we could update the graph in place:
@@ -336,24 +354,26 @@
// the def's anti-dependence *and* output-dependence edges due to
// that register, and add new anti-dependence and output-dependence
// edges based on the next live range of the register.
- SUnits.clear();
- EntrySU = SUnit();
- ExitSU = SUnit();
- BuildSchedGraph(AA);
+ if ((Broken != 0) || NeedCandidates) {
+ SUnits.clear();
+ Sequence.clear();
+ EntrySU = SUnit();
+ ExitSU = SUnit();
+ BuildSchedGraph(AA);
+ }
NumFixedAnti += Broken;
+ if (Broken == 0)
+ break;
}
}
DEBUG(errs() << "********** List Scheduling **********\n");
-
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this));
AvailableQueue.initNodes(SUnits);
-
- ListScheduleTopDown();
-
+ ListScheduleTopDown(NULL);
AvailableQueue.releaseState();
}
@@ -552,7 +572,8 @@
/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
/// the PendingQueue if the count reaches zero. Also update its cycle bound.
-void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) {
+void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge,
+ bool IgnoreAntiDep) {
SUnit *SuccSU = SuccEdge->getSUnit();
#ifndef NDEBUG
@@ -568,7 +589,8 @@
// Compute how many cycles it will be before this actually becomes
// available. This is the max of the start time of all predecessors plus
// their latencies.
- SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency());
+ SuccSU->setDepthToAtLeast(SU->getDepth(IgnoreAntiDep) +
+ SuccEdge->getLatency(), IgnoreAntiDep);
// If all the node's predecessors are scheduled, this node is ready
// to be scheduled. Ignore the special ExitSU node.
@@ -577,40 +599,73 @@
}
/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors.
-void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) {
+void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU, bool IgnoreAntiDep) {
for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
- I != E; ++I)
- ReleaseSucc(SU, &*I);
+ I != E; ++I) {
+ if (IgnoreAntiDep && (I->getKind() == SDep::Anti)) continue;
+ ReleaseSucc(SU, &*I, IgnoreAntiDep);
+ }
}
/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
/// count of its successors. If a successor pending count is zero, add it to
/// the Available queue.
-void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
+void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle,
+ bool IgnoreAntiDep) {
DEBUG(errs() << "*** Scheduling [" << CurCycle << "]: ");
DEBUG(SU->dump(this));
Sequence.push_back(SU);
- assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
- SU->setDepthToAtLeast(CurCycle);
+ assert(CurCycle >= SU->getDepth(IgnoreAntiDep) &&
+ "Node scheduled above its depth!");
+ SU->setDepthToAtLeast(CurCycle, IgnoreAntiDep);
- ReleaseSuccessors(SU);
+ ReleaseSuccessors(SU, IgnoreAntiDep);
SU->isScheduled = true;
AvailableQueue.ScheduledNode(SU);
}
/// ListScheduleTopDown - The main loop of list scheduling for top-down
/// schedulers.
-void SchedulePostRATDList::ListScheduleTopDown() {
+void SchedulePostRATDList::ListScheduleTopDown(
+ AntiDepBreaker::CandidateMap *AntiDepCandidates) {
unsigned CurCycle = 0;
+ const bool IgnoreAntiDep = (AntiDepCandidates != NULL);
+
+ // We're scheduling top-down but we're visiting the regions in
+ // bottom-up order, so we don't know the hazards at the start of a
+ // region. So assume no hazards (this should usually be ok as most
+ // blocks are a single region).
+ HazardRec->Reset();
+
+ // If ignoring anti-dependencies, the Schedule DAG still has Anti
+ // dep edges, but we ignore them for scheduling purposes
+ AvailableQueue.setIgnoreAntiDep(IgnoreAntiDep);
// Release any successors of the special Entry node.
- ReleaseSuccessors(&EntrySU);
+ ReleaseSuccessors(&EntrySU, IgnoreAntiDep);
- // All leaves to Available queue.
+ // Add all leaves to Available queue. If ignoring antideps we also
+ // adjust the predecessor count for each node to not include antidep
+ // edges.
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
// It is available if it has no predecessors.
- if (SUnits[i].Preds.empty()) {
+ bool available = SUnits[i].Preds.empty();
+ // If we are ignoring anti-dependencies then a node that has only
+ // anti-dep predecessors is available.
+ if (!available && IgnoreAntiDep) {
+ available = true;
+ for (SUnit::const_pred_iterator I = SUnits[i].Preds.begin(),
+ E = SUnits[i].Preds.end(); I != E; ++I) {
+ if (I->getKind() != SDep::Anti) {
+ available = false;
+ } else {
+ SUnits[i].NumPredsLeft -= 1;
+ }
+ }
+ }
+
+ if (available) {
AvailableQueue.push(&SUnits[i]);
SUnits[i].isAvailable = true;
}
@@ -629,26 +684,25 @@
// so, add them to the available queue.
unsigned MinDepth = ~0u;
for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
- if (PendingQueue[i]->getDepth() <= CurCycle) {
+ if (PendingQueue[i]->getDepth(IgnoreAntiDep) <= CurCycle) {
AvailableQueue.push(PendingQueue[i]);
PendingQueue[i]->isAvailable = true;
PendingQueue[i] = PendingQueue.back();
PendingQueue.pop_back();
--i; --e;
- } else if (PendingQueue[i]->getDepth() < MinDepth)
- MinDepth = PendingQueue[i]->getDepth();
+ } else if (PendingQueue[i]->getDepth(IgnoreAntiDep) < MinDepth)
+ MinDepth = PendingQueue[i]->getDepth(IgnoreAntiDep);
}
DEBUG(errs() << "\n*** Examining Available\n";
LatencyPriorityQueue q = AvailableQueue;
while (!q.empty()) {
SUnit *su = q.pop();
- errs() << "Height " << su->getHeight() << ": ";
+ errs() << "Height " << su->getHeight(IgnoreAntiDep) << ": ";
su->dump(this);
});
SUnit *FoundSUnit = 0;
-
bool HasNoopHazards = false;
while (!AvailableQueue.empty()) {
SUnit *CurSUnit = AvailableQueue.pop();
@@ -672,9 +726,30 @@
NotReady.clear();
}
- // If we found a node to schedule, do it now.
+ // If we found a node to schedule...
if (FoundSUnit) {
- ScheduleNodeTopDown(FoundSUnit, CurCycle);
+ // If we are ignoring anti-dependencies and the SUnit we are
+ // scheduling has an antidep predecessor that has not been
+ // scheduled, then we will need to break that antidep if we want
+ // to get this schedule when not ignoring anti-dependencies.
+ if (IgnoreAntiDep) {
+ AntiDepBreaker::AntiDepRegVector AntiDepRegs;
+ for (SUnit::const_pred_iterator I = FoundSUnit->Preds.begin(),
+ E = FoundSUnit->Preds.end(); I != E; ++I) {
+ if ((I->getKind() == SDep::Anti) && !I->getSUnit()->isScheduled)
+ AntiDepRegs.push_back(I->getReg());
+ }
+
+ if (AntiDepRegs.size() > 0) {
+ DEBUG(errs() << "*** AntiDep Candidate: ");
+ DEBUG(FoundSUnit->dump(this));
+ AntiDepCandidates->insert(
+ AntiDepBreaker::CandidateMap::value_type(FoundSUnit, AntiDepRegs));
+ }
+ }
+
+ // ... schedule the node...
+ ScheduleNodeTopDown(FoundSUnit, CurCycle, IgnoreAntiDep);
HazardRec->EmitInstruction(FoundSUnit);
CycleHasInsts = true;