diff options
author | Andrew Trick <atrick@apple.com> | 2013-01-25 06:33:57 +0000 |
---|---|---|
committer | Andrew Trick <atrick@apple.com> | 2013-01-25 06:33:57 +0000 |
commit | 4e1fb1894048455d49d62543b3f83672b27b0000 (patch) | |
tree | f5ea7b8bbf85ae1eb6c83753e07836868f292793 | |
parent | 827de0520ee986fcda5f0d3290a3746249fa5847 (diff) | |
download | external_llvm-4e1fb1894048455d49d62543b3f83672b27b0000.zip external_llvm-4e1fb1894048455d49d62543b3f83672b27b0000.tar.gz external_llvm-4e1fb1894048455d49d62543b3f83672b27b0000.tar.bz2 |
MIsched: Improve the interface to SchedDFS analysis (subtrees).
Allow the strategy to select SchedDFS. Allow the results of SchedDFS
to affect initialization of the scheduler state.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@173425 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | include/llvm/CodeGen/MachineScheduler.h | 14 | ||||
-rw-r--r-- | include/llvm/CodeGen/ScheduleDFS.h | 7 | ||||
-rw-r--r-- | lib/CodeGen/MachineScheduler.cpp | 62 | ||||
-rw-r--r-- | lib/CodeGen/ScheduleDAGInstrs.cpp | 14 | ||||
-rw-r--r-- | lib/Target/Hexagon/HexagonMachineScheduler.cpp | 8 | ||||
-rw-r--r-- | test/CodeGen/X86/misched-matrix.ll | 3 |
6 files changed, 61 insertions, 47 deletions
diff --git a/include/llvm/CodeGen/MachineScheduler.h b/include/llvm/CodeGen/MachineScheduler.h index cc697a5..aa78f52 100644 --- a/include/llvm/CodeGen/MachineScheduler.h +++ b/include/llvm/CodeGen/MachineScheduler.h @@ -316,12 +316,9 @@ public: 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; } @@ -341,8 +338,8 @@ protected: /// 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); @@ -365,7 +362,8 @@ protected: 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); diff --git a/include/llvm/CodeGen/ScheduleDFS.h b/include/llvm/CodeGen/ScheduleDFS.h index 54b2232..e079292 100644 --- a/include/llvm/CodeGen/ScheduleDFS.h +++ b/include/llvm/CodeGen/ScheduleDFS.h @@ -127,7 +127,7 @@ public: } /// \brief Compute various metrics for the DAG with given roots. - void compute(ArrayRef<SUnit *> Roots); + void compute(ArrayRef<SUnit> SUnits); /// \brief Get the ILP value for a DAG node. /// @@ -140,7 +140,12 @@ public: unsigned getNumSubtrees() const { return SubtreeConnectLevels.size(); } /// \brief Get the ID of the subtree the given DAG node belongs to. + /// + /// For convenience, if DFSResults have not been computed yet, give everything + /// tree ID 0. unsigned getSubtreeID(const SUnit *SU) const { + if (empty()) + return 0; assert(SU->NodeNum < DFSData.size() && "New Node"); return DFSData[SU->NodeNum].SubtreeID; } diff --git a/lib/CodeGen/MachineScheduler.cpp b/lib/CodeGen/MachineScheduler.cpp index 3e5935c..aa59915 100644 --- a/lib/CodeGen/MachineScheduler.cpp +++ b/lib/CodeGen/MachineScheduler.cpp @@ -510,10 +510,19 @@ void ScheduleDAGMI::schedule() { 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)) { @@ -561,25 +570,18 @@ void ScheduleDAGMI::postprocessDAG() { } } -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); @@ -589,28 +591,33 @@ void ScheduleDAGMI::releaseRoots() { // 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); @@ -1216,7 +1223,7 @@ void ConvergingScheduler::initialize(ScheduleDAGMI *dag) { Top.init(DAG, SchedModel, &Rem); Bot.init(DAG, SchedModel, &Rem); - DAG->initDFSResult(); + DAG->computeDFSResult(); // Initialize resource counts. @@ -1278,8 +1285,6 @@ void ConvergingScheduler::registerRoots() { 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. @@ -2140,14 +2145,13 @@ public: 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); } diff --git a/lib/CodeGen/ScheduleDAGInstrs.cpp b/lib/CodeGen/ScheduleDAGInstrs.cpp index 428c1a4..7ee5207 100644 --- a/lib/CodeGen/ScheduleDAGInstrs.cpp +++ b/lib/CodeGen/ScheduleDAGInstrs.cpp @@ -1188,16 +1188,20 @@ static bool hasDataSucc(const SUnit *SU) { /// 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()) { diff --git a/lib/Target/Hexagon/HexagonMachineScheduler.cpp b/lib/Target/Hexagon/HexagonMachineScheduler.cpp index aef6830..36dfaa4 100644 --- a/lib/Target/Hexagon/HexagonMachineScheduler.cpp +++ b/lib/Target/Hexagon/HexagonMachineScheduler.cpp @@ -152,6 +152,12 @@ void VLIWMachineScheduler::schedule() { // Postprocess the DAG to add platform specific artificial dependencies. postprocessDAG(); + SmallVector<SUnit*, 8> TopRoots, BotRoots; + findRootsAndBiasEdges(TopRoots, BotRoots); + + // Initialize the strategy before modifying the DAG. + SchedImpl->initialize(this); + // To view Height/Depth correctly, they should be accessed at least once. DEBUG(unsigned maxH = 0; for (unsigned su = 0, e = SUnits.size(); su != e; ++su) @@ -166,7 +172,7 @@ void VLIWMachineScheduler::schedule() { DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) SUnits[su].dumpAll(this)); - initQueues(); + initQueues(TopRoots, BotRoots); bool IsTopNode = false; while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { diff --git a/test/CodeGen/X86/misched-matrix.ll b/test/CodeGen/X86/misched-matrix.ll index d00d173..f5566e5 100644 --- a/test/CodeGen/X86/misched-matrix.ll +++ b/test/CodeGen/X86/misched-matrix.ll @@ -8,9 +8,6 @@ ; RUN: -misched=ilpmax -verify-machineinstrs \ ; RUN: | FileCheck %s -check-prefix=ILPMAX ; -; Very temporary xfail during SchedDFSResult churn. -; XFAIL: * -; ; Verify that the MI scheduler minimizes register pressure for a ; uniform set of bottom-up subtrees (unrolled matrix multiply). ; |