X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLatencyPriorityQueue.cpp;h=deab05a412c92de4a8349b534e86625ac13584b0;hb=57a964bc635359b97340b57510df4ebaf506806b;hp=131da27c337df4e080bb229b0df4770422fc9eb5;hpb=54e4c36a7349e94a84773afb56eccd4ca65b49e9;p=oota-llvm.git diff --git a/lib/CodeGen/LatencyPriorityQueue.cpp b/lib/CodeGen/LatencyPriorityQueue.cpp index 131da27c337..deab05a412c 100644 --- a/lib/CodeGen/LatencyPriorityQueue.cpp +++ b/lib/CodeGen/LatencyPriorityQueue.cpp @@ -16,9 +16,18 @@ #define DEBUG_TYPE "scheduler" #include "llvm/CodeGen/LatencyPriorityQueue.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/raw_ostream.h" using namespace llvm; bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { + // The isScheduleHigh flag allows nodes with wraparound dependencies that + // cannot easily be modeled as edges with latencies to be scheduled as + // soon as possible in a top-down schedule. + if (LHS->isScheduleHigh && !RHS->isScheduleHigh) + return false; + if (!LHS->isScheduleHigh && RHS->isScheduleHigh) + return true; + unsigned LHSNum = LHS->NodeNum; unsigned RHSNum = RHS->NodeNum; @@ -27,82 +36,20 @@ bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { 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; + return RHSNum < LHSNum; } -/// 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 WorkList; - WorkList.push_back(&SU); - while (!WorkList.empty()) { - const SUnit *Cur = WorkList.back(); - unsigned CurLatency = Cur->Latency; - bool AllDone = true; - unsigned MaxSuccLatency = 0; - for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end(); - I != E; ++I) { - int SuccLatency = Latencies[I->getSUnit()->NodeNum]; - if (SuccLatency == -1) { - AllDone = false; - WorkList.push_back(I->getSUnit()); - } else { - // This assumes that there's no delay for reusing registers. - unsigned NewLatency = SuccLatency + CurLatency; - MaxSuccLatency = std::max(MaxSuccLatency, NewLatency); - } - } - if (AllDone) { - Latencies[Cur->NodeNum] = MaxSuccLatency; - 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 > 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->getSUnit(), Latency)); - } - } -} - /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor /// of SU, return it, otherwise return null. SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { @@ -118,32 +65,34 @@ SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { OnlyAvailablePred = &Pred; } } - + return OnlyAvailablePred; } -void LatencyPriorityQueue::push_impl(SUnit *SU) { +void LatencyPriorityQueue::push(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) + I != E; ++I) { if (getSingleUnscheduledPred(I->getSUnit()) == SU) ++NumNodesBlocking; + } NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; - - Queue.push(SU); + + Queue.push_back(SU); } -// ScheduledNode - As nodes are scheduled, we look to see if there are any +// 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) { +void LatencyPriorityQueue::scheduledNode(SUnit *SU) { for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); - I != E; ++I) + I != E; ++I) { AdjustPriorityOfUnscheduledPreds(I->getSUnit()); + } } /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just @@ -154,10 +103,10 @@ void LatencyPriorityQueue::ScheduledNode(SUnit *SU) { /// node of the same priority that will not make a node available. void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { if (SU->isAvailable) 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); @@ -166,3 +115,38 @@ void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { // NumNodesSolelyBlocking value. push(OnlyAvailablePred); } + +SUnit *LatencyPriorityQueue::pop() { + if (empty()) return NULL; + std::vector::iterator Best = Queue.begin(); + for (std::vector::iterator I = llvm::next(Queue.begin()), + E = Queue.end(); I != E; ++I) + if (Picker(*Best, *I)) + Best = I; + SUnit *V = *Best; + if (Best != prior(Queue.end())) + std::swap(*Best, Queue.back()); + Queue.pop_back(); + return V; +} + +void LatencyPriorityQueue::remove(SUnit *SU) { + assert(!Queue.empty() && "Queue is empty!"); + std::vector::iterator I = std::find(Queue.begin(), Queue.end(), SU); + if (I != prior(Queue.end())) + std::swap(*I, Queue.back()); + Queue.pop_back(); +} + +#ifdef NDEBUG +void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const {} +#else +void LatencyPriorityQueue::dump(ScheduleDAG *DAG) const { + LatencyPriorityQueue q = *this; + while (!q.empty()) { + SUnit *su = q.pop(); + dbgs() << "Height " << su->getHeight() << ": "; + su->dump(DAG); + } +} +#endif