X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FCodeGen%2FLatencyPriorityQueue.cpp;h=0eb009ddac2943c1a5730a23ea92c7457ce97bcb;hb=ab2e3e2d7074207e2a4bb15e2913fa83795bb1ca;hp=70b6574996be5d555a99fb0212e215e5043ff966;hpb=343f0c046702831a4a6aec951b6a297a23241a55;p=oota-llvm.git diff --git a/lib/CodeGen/LatencyPriorityQueue.cpp b/lib/CodeGen/LatencyPriorityQueue.cpp index 70b6574996b..0eb009ddac2 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,86 +36,27 @@ 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; } -/// 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(); - 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 > 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; + SUnit &Pred = *I->getSUnit(); 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. @@ -115,21 +65,22 @@ 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) - if (getSingleUnscheduledPred(I->Dep) == SU) + I != E; ++I) { + if (getSingleUnscheduledPred(I->getSUnit()) == SU) ++NumNodesBlocking; + } NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; - - Queue.push(SU); + + Queue.push_back(SU); } @@ -139,8 +90,9 @@ void LatencyPriorityQueue::push_impl(SUnit *SU) { // 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); + I != E; ++I) { + AdjustPriorityOfUnscheduledPreds(I->getSUnit()); + } } /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just @@ -151,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); @@ -163,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