Move ScheduleDAGList's LatencyPriorityQueue class out to a separate file.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@59340 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1 insertions, 259 deletions

diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
index 14042ed602..168e6d5f29 100644
--- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
+++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp
@@ -30,6 +30,7 @@
 #include "llvm/Support/Compiler.h"
 #include "llvm/ADT/PriorityQueue.h"
 #include "llvm/ADT/Statistic.h"
+#include "LatencyPriorityQueue.h"
 #include <climits>
 using namespace llvm;
 
@@ -276,265 +277,6 @@ void ScheduleDAGList::ListScheduleTopDown() {
 }
 
 //===----------------------------------------------------------------------===//
-//                    LatencyPriorityQueue Implementation
-//===----------------------------------------------------------------------===//
-//
-// This is a SchedulingPriorityQueue that schedules using latency information to
-// reduce the length of the critical path through the basic block.
-// 
-namespace {
-  class LatencyPriorityQueue;
-  
-  /// Sorting functions for the Available queue.
-  struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> {
-    LatencyPriorityQueue *PQ;
-    latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
-    latency_sort(const latency_sort &RHS) : PQ(RHS.PQ) {}
-    
-    bool operator()(const SUnit* left, const SUnit* right) const;
-  };
-}  // end anonymous namespace
-
-namespace {
-  class LatencyPriorityQueue : public SchedulingPriorityQueue {
-    // SUnits - The SUnits for the current graph.
-    std::vector<SUnit> *SUnits;
-    
-    // Latencies - The latency (max of latency from this node to the bb exit)
-    // for each node.
-    std::vector<int> Latencies;
-
-    /// NumNodesSolelyBlocking - This vector contains, for every node in the
-    /// Queue, the number of nodes that the node is the sole unscheduled
-    /// predecessor for.  This is used as a tie-breaker heuristic for better
-    /// mobility.
-    std::vector<unsigned> NumNodesSolelyBlocking;
-
-    PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
-public:
-    LatencyPriorityQueue() : Queue(latency_sort(this)) {
-    }
-    
-    void initNodes(std::vector<SUnit> &sunits) {
-      SUnits = &sunits;
-      // Calculate node priorities.
-      CalculatePriorities();
-    }
-
-    void addNode(const SUnit *SU) {
-      Latencies.resize(SUnits->size(), -1);
-      NumNodesSolelyBlocking.resize(SUnits->size(), 0);
-      CalcLatency(*SU);
-    }
-
-    void updateNode(const SUnit *SU) {
-      Latencies[SU->NodeNum] = -1;
-      CalcLatency(*SU);
-    }
-
-    void releaseState() {
-      SUnits = 0;
-      Latencies.clear();
-    }
-    
-    unsigned getLatency(unsigned NodeNum) const {
-      assert(NodeNum < Latencies.size());
-      return Latencies[NodeNum];
-    }
-    
-    unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
-      assert(NodeNum < NumNodesSolelyBlocking.size());
-      return NumNodesSolelyBlocking[NodeNum];
-    }
-    
-    unsigned size() const { return Queue.size(); }
-
-    bool empty() const { return Queue.empty(); }
-    
-    virtual void push(SUnit *U) {
-      push_impl(U);
-    }
-    void push_impl(SUnit *U);
-    
-    void push_all(const std::vector<SUnit *> &Nodes) {
-      for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
-        push_impl(Nodes[i]);
-    }
-    
-    SUnit *pop() {
-      if (empty()) return NULL;
-      SUnit *V = Queue.top();
-      Queue.pop();
-      return V;
-    }
-
-    void remove(SUnit *SU) {
-      assert(!Queue.empty() && "Not in queue!");
-      Queue.erase_one(SU);
-    }
-
-    // ScheduledNode - As nodes are scheduled, we look to see if there are any
-    // successor nodes that have a single unscheduled predecessor.  If so, that
-    // single predecessor has a higher priority, since scheduling it will make
-    // the node available.
-    void ScheduledNode(SUnit *Node);
-
-private:
-    void CalculatePriorities();
-    int CalcLatency(const SUnit &SU);
-    void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
-    SUnit *getSingleUnscheduledPred(SUnit *SU);
-  };
-}
-
-bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const {
-  unsigned LHSNum = LHS->NodeNum;
-  unsigned RHSNum = RHS->NodeNum;
-
-  // The most important heuristic is scheduling the critical path.
-  unsigned LHSLatency = PQ->getLatency(LHSNum);
-  unsigned RHSLatency = PQ->getLatency(RHSNum);
-  if (LHSLatency < RHSLatency) return true;
-  if (LHSLatency > RHSLatency) return false;
-  
-  // After that, if two nodes have identical latencies, look to see if one will
-  // unblock more other nodes than the other.
-  unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum);
-  unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum);
-  if (LHSBlocked < RHSBlocked) return true;
-  if (LHSBlocked > RHSBlocked) return false;
-  
-  // Finally, just to provide a stable ordering, use the node number as a
-  // deciding factor.
-  return LHSNum < RHSNum;
-}
-
-
-/// CalcNodePriority - Calculate the maximal path from the node to the exit.
-///
-int LatencyPriorityQueue::CalcLatency(const SUnit &SU) {
-  int &Latency = Latencies[SU.NodeNum];
-  if (Latency != -1)
-    return Latency;
-
-  std::vector<const SUnit*> WorkList;
-  WorkList.push_back(&SU);
-  while (!WorkList.empty()) {
-    const SUnit *Cur = WorkList.back();
-    bool AllDone = true;
-    int MaxSuccLatency = 0;
-    for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end();
-         I != E; ++I) {
-      int SuccLatency = Latencies[I->Dep->NodeNum];
-      if (SuccLatency == -1) {
-        AllDone = false;
-        WorkList.push_back(I->Dep);
-      } else {
-        MaxSuccLatency = std::max(MaxSuccLatency, SuccLatency);
-      }
-    }
-    if (AllDone) {
-      Latencies[Cur->NodeNum] = MaxSuccLatency + Cur->Latency;
-      WorkList.pop_back();
-    }
-  }
-
-  return Latency;
-}
-
-/// CalculatePriorities - Calculate priorities of all scheduling units.
-void LatencyPriorityQueue::CalculatePriorities() {
-  Latencies.assign(SUnits->size(), -1);
-  NumNodesSolelyBlocking.assign(SUnits->size(), 0);
-
-  // For each node, calculate the maximal path from the node to the exit.
-  std::vector<std::pair<const SUnit*, unsigned> > WorkList;
-  for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
-    const SUnit *SU = &(*SUnits)[i];
-    if (SU->Succs.empty())
-      WorkList.push_back(std::make_pair(SU, 0U));
-  }
-
-  while (!WorkList.empty()) {
-    const SUnit *SU = WorkList.back().first;
-    unsigned SuccLat = WorkList.back().second;
-    WorkList.pop_back();
-    int &Latency = Latencies[SU->NodeNum];
-    if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) {
-      Latency = SU->Latency + SuccLat;
-      for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
-           I != E; ++I)
-        WorkList.push_back(std::make_pair(I->Dep, Latency));
-    }
-  }
-}
-
-/// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor
-/// of SU, return it, otherwise return null.
-SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) {
-  SUnit *OnlyAvailablePred = 0;
-  for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
-       I != E; ++I) {
-    SUnit &Pred = *I->Dep;
-    if (!Pred.isScheduled) {
-      // We found an available, but not scheduled, predecessor.  If it's the
-      // only one we have found, keep track of it... otherwise give up.
-      if (OnlyAvailablePred && OnlyAvailablePred != &Pred)
-        return 0;
-      OnlyAvailablePred = &Pred;
-    }
-  }
-      
-  return OnlyAvailablePred;
-}
-
-void LatencyPriorityQueue::push_impl(SUnit *SU) {
-  // Look at all of the successors of this node.  Count the number of nodes that
-  // this node is the sole unscheduled node for.
-  unsigned NumNodesBlocking = 0;
-  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
-       I != E; ++I)
-    if (getSingleUnscheduledPred(I->Dep) == SU)
-      ++NumNodesBlocking;
-  NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking;
-  
-  Queue.push(SU);
-}
-
-
-// ScheduledNode - As nodes are scheduled, we look to see if there are any
-// successor nodes that have a single unscheduled predecessor.  If so, that
-// single predecessor has a higher priority, since scheduling it will make
-// the node available.
-void LatencyPriorityQueue::ScheduledNode(SUnit *SU) {
-  for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
-       I != E; ++I)
-    AdjustPriorityOfUnscheduledPreds(I->Dep);
-}
-
-/// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just
-/// scheduled.  If SU is not itself available, then there is at least one
-/// predecessor node that has not been scheduled yet.  If SU has exactly ONE
-/// unscheduled predecessor, we want to increase its priority: it getting
-/// scheduled will make this node available, so it is better than some other
-/// node of the same priority that will not make a node available.
-void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) {
-  if (SU->isPending) return;  // All preds scheduled.
-  
-  SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU);
-  if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return;
-  
-  // Okay, we found a single predecessor that is available, but not scheduled.
-  // Since it is available, it must be in the priority queue.  First remove it.
-  remove(OnlyAvailablePred);
-
-  // Reinsert the node into the priority queue, which recomputes its
-  // NumNodesSolelyBlocking value.
-  push(OnlyAvailablePred);
-}
-
-
-//===----------------------------------------------------------------------===//
 //                         Public Constructor Functions
 //===----------------------------------------------------------------------===//