const SUnit *getNextClusterSucc() const { return NextClusterSucc; }
- /// Initialize a DFSResult after DAG building is complete, and before any
+ /// Compute a DFSResult after DAG building is complete, and before any
/// queue comparisons.
- void initDFSResult();
-
- /// Compute DFS result once all interesting roots are discovered.
- void computeDFSResult(ArrayRef<SUnit*> Roots);
+ void computeDFSResult();
/// Return a non-null DFS result if the scheduling strategy initialized it.
const SchedDFSResult *getDFSResult() const { return DFSResult; }
/// instances of ScheduleDAGMI to perform custom DAG postprocessing.
void postprocessDAG();
- /// Identify DAG roots and setup scheduler queues.
- void initQueues();
+ /// Release ExitSU predecessors and setup scheduler queues.
+ void initQueues(ArrayRef<SUnit*> TopRoots, ArrayRef<SUnit*> BotRoots);
/// Move an instruction and update register pressure.
void scheduleMI(SUnit *SU, bool IsTopNode);
void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
bool checkSchedLimit();
- void releaseRoots();
+ void findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
+ SmallVectorImpl<SUnit*> &BotRoots);
void releaseSucc(SUnit *SU, SDep *SuccEdge);
void releaseSuccessors(SUnit *SU);
postprocessDAG();
+ SmallVector<SUnit*, 8> TopRoots, BotRoots;
+ findRootsAndBiasEdges(TopRoots, BotRoots);
+
+ // Initialize the strategy before modifying the DAG.
+ // This may initialize a DFSResult to be used for queue priority.
+ SchedImpl->initialize(this);
+
DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this));
+ if (ViewMISchedDAGs) viewGraph();
- initQueues();
+ // Initialize ready queues now that the DAG and priority data are finalized.
+ initQueues(TopRoots, BotRoots);
bool IsTopNode = false;
while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
}
}
-void ScheduleDAGMI::initDFSResult() {
+void ScheduleDAGMI::computeDFSResult() {
if (!DFSResult)
DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize);
DFSResult->clear();
- DFSResult->resize(SUnits.size());
ScheduledTrees.clear();
-}
-
-void ScheduleDAGMI::computeDFSResult(ArrayRef<SUnit*> Roots) {
- DFSResult->compute(Roots);
+ DFSResult->resize(SUnits.size());
+ DFSResult->compute(SUnits);
ScheduledTrees.resize(DFSResult->getNumSubtrees());
}
-// Release all DAG roots for scheduling.
-//
-// Nodes with unreleased weak edges can still be roots.
-void ScheduleDAGMI::releaseRoots() {
- SmallVector<SUnit*, 16> BotRoots;
-
+void ScheduleDAGMI::findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
+ SmallVectorImpl<SUnit*> &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->NumPredsLeft && SU != &EntrySU)
- SchedImpl->releaseTopNode(SU);
+ TopRoots.push_back(SU);
// A SUnit is ready to bottom schedule if it has no successors.
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.
- for (SmallVectorImpl<SUnit*>::const_reverse_iterator
- I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I)
- SchedImpl->releaseBottomNode(*I);
}
/// Identify DAG roots and setup scheduler queues.
-void ScheduleDAGMI::initQueues() {
+void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots,
+ ArrayRef<SUnit*> BotRoots) {
NextClusterSucc = NULL;
NextClusterPred = NULL;
- // Initialize the strategy before modifying the DAG.
- SchedImpl->initialize(this);
-
// Release all DAG roots for scheduling, not including EntrySU/ExitSU.
- releaseRoots();
+ //
+ // Nodes with unreleased weak edges can still be roots.
+ // Release top roots in forward order.
+ for (SmallVectorImpl<SUnit*>::const_iterator
+ I = TopRoots.begin(), E = TopRoots.end(); I != E; ++I) {
+ SchedImpl->releaseTopNode(*I);
+ }
+ // Release bottom roots in reverse order so the higher priority nodes appear
+ // first. This is more natural and slightly more efficient.
+ for (SmallVectorImpl<SUnit*>::const_reverse_iterator
+ I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {
+ SchedImpl->releaseBottomNode(*I);
+ }
releaseSuccessors(&EntrySU);
releasePredecessors(&ExitSU);
Top.init(DAG, SchedModel, &Rem);
Bot.init(DAG, SchedModel, &Rem);
- DAG->initDFSResult();
+ DAG->computeDFSResult();
// Initialize resource counts.
Rem.CriticalPath = (*I)->getDepth();
}
DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n');
-
- DAG->computeDFSResult(Bot.Available.elements());
}
/// Does this SU have a hazard within the current instruction group.
virtual void initialize(ScheduleDAGMI *dag) {
DAG = dag;
- DAG->initDFSResult();
+ DAG->computeDFSResult();
Cmp.DFSResult = DAG->getDFSResult();
Cmp.ScheduledTrees = &DAG->getScheduledTrees();
ReadyQ.clear();
}
virtual void registerRoots() {
- DAG->computeDFSResult(ReadyQ);
// Restore the heap in ReadyQ with the updated DFS results.
std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
}
/// Compute an ILP metric for all nodes in the subDAG reachable via depth-first
/// search from this root.
-void SchedDFSResult::compute(ArrayRef<SUnit *> Roots) {
+void SchedDFSResult::compute(ArrayRef<SUnit> SUnits) {
if (!IsBottomUp)
llvm_unreachable("Top-down ILP metric is unimplemnted");
SchedDFSImpl Impl(*this);
- for (ArrayRef<const SUnit*>::const_iterator
- RootI = Roots.begin(), RootE = Roots.end(); RootI != RootE; ++RootI) {
+ for (ArrayRef<SUnit>::const_iterator
+ SI = SUnits.begin(), SE = SUnits.end(); SI != SE; ++SI) {
+ const SUnit *SU = &*SI;
+ if (Impl.isVisited(SU) || hasDataSucc(SU))
+ continue;
+
SchedDAGReverseDFS DFS;
- Impl.visitPreorder(*RootI);
- DFS.follow(*RootI);
+ Impl.visitPreorder(SU);
+ DFS.follow(SU);
for (;;) {
// Traverse the leftmost path as far as possible.
while (DFS.getPred() != DFS.getPredEnd()) {
projects / oota-llvm.git / commitdiff