From 93d343357944beb701d425fc7ef00dd7b0a32bd7 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Wed, 26 May 2010 18:52:00 +0000 Subject: Eliminate the use of PriorityQueue and just use a std::vector, implementing pop with a linear search for a "best" element. The priority queue was a neat idea, but in practice the comparison functions depend on dynamic information. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@104718 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/LatencyPriorityQueue.cpp | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) (limited to 'lib/CodeGen/LatencyPriorityQueue.cpp') diff --git a/lib/CodeGen/LatencyPriorityQueue.cpp b/lib/CodeGen/LatencyPriorityQueue.cpp index 6df7b12064..03b4eab93d 100644 --- a/lib/CodeGen/LatencyPriorityQueue.cpp +++ b/lib/CodeGen/LatencyPriorityQueue.cpp @@ -79,7 +79,7 @@ void LatencyPriorityQueue::push(SUnit *SU) { } NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; - Queue.push(SU); + Queue.push_back(SU); } @@ -114,3 +114,25 @@ 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 = 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(); +} -- cgit v1.2.3