LatencyPriorityQueue.h revision 199989
1193323Sed//===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file declares the LatencyPriorityQueue class, which is a 11193323Sed// SchedulingPriorityQueue that schedules using latency information to 12193323Sed// reduce the length of the critical path through the basic block. 13193323Sed// 14193323Sed//===----------------------------------------------------------------------===// 15193323Sed 16193323Sed#ifndef LATENCY_PRIORITY_QUEUE_H 17193323Sed#define LATENCY_PRIORITY_QUEUE_H 18193323Sed 19193323Sed#include "llvm/CodeGen/ScheduleDAG.h" 20193323Sed#include "llvm/ADT/PriorityQueue.h" 21193323Sed 22193323Sednamespace llvm { 23193323Sed class LatencyPriorityQueue; 24193323Sed 25193323Sed /// Sorting functions for the Available queue. 26193323Sed struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { 27193323Sed LatencyPriorityQueue *PQ; 28193323Sed explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} 29193323Sed 30193323Sed bool operator()(const SUnit* left, const SUnit* right) const; 31193323Sed }; 32193323Sed 33193323Sed class LatencyPriorityQueue : public SchedulingPriorityQueue { 34193323Sed // SUnits - The SUnits for the current graph. 35193323Sed std::vector<SUnit> *SUnits; 36193323Sed 37193323Sed /// NumNodesSolelyBlocking - This vector contains, for every node in the 38193323Sed /// Queue, the number of nodes that the node is the sole unscheduled 39193323Sed /// predecessor for. This is used as a tie-breaker heuristic for better 40193323Sed /// mobility. 41193323Sed std::vector<unsigned> NumNodesSolelyBlocking; 42198892Srdivacky 43198892Srdivacky /// Queue - The queue. 44198892Srdivacky PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue; 45193323Sed 46193323Sedpublic: 47199989Srdivacky LatencyPriorityQueue() : Queue(latency_sort(this)) { 48193323Sed } 49198892Srdivacky 50193323Sed void initNodes(std::vector<SUnit> &sunits) { 51193323Sed SUnits = &sunits; 52193323Sed NumNodesSolelyBlocking.resize(SUnits->size(), 0); 53193323Sed } 54193323Sed 55193323Sed void addNode(const SUnit *SU) { 56193323Sed NumNodesSolelyBlocking.resize(SUnits->size(), 0); 57193323Sed } 58193323Sed 59193323Sed void updateNode(const SUnit *SU) { 60193323Sed } 61193323Sed 62193323Sed void releaseState() { 63193323Sed SUnits = 0; 64193323Sed } 65193323Sed 66193323Sed unsigned getLatency(unsigned NodeNum) const { 67193323Sed assert(NodeNum < (*SUnits).size()); 68199989Srdivacky return (*SUnits)[NodeNum].getHeight(); 69193323Sed } 70193323Sed 71193323Sed unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { 72193323Sed assert(NodeNum < NumNodesSolelyBlocking.size()); 73193323Sed return NumNodesSolelyBlocking[NodeNum]; 74193323Sed } 75193323Sed 76193323Sed unsigned size() const { return Queue.size(); } 77193323Sed 78193323Sed bool empty() const { return Queue.empty(); } 79193323Sed 80193323Sed virtual void push(SUnit *U) { 81193323Sed push_impl(U); 82193323Sed } 83193323Sed void push_impl(SUnit *U); 84193323Sed 85193323Sed void push_all(const std::vector<SUnit *> &Nodes) { 86193323Sed for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 87193323Sed push_impl(Nodes[i]); 88193323Sed } 89193323Sed 90193323Sed SUnit *pop() { 91193323Sed if (empty()) return NULL; 92193323Sed SUnit *V = Queue.top(); 93193323Sed Queue.pop(); 94193323Sed return V; 95193323Sed } 96193323Sed 97193323Sed void remove(SUnit *SU) { 98193323Sed assert(!Queue.empty() && "Not in queue!"); 99193323Sed Queue.erase_one(SU); 100193323Sed } 101193323Sed 102193323Sed // ScheduledNode - As nodes are scheduled, we look to see if there are any 103193323Sed // successor nodes that have a single unscheduled predecessor. If so, that 104193323Sed // single predecessor has a higher priority, since scheduling it will make 105193323Sed // the node available. 106193323Sed void ScheduledNode(SUnit *Node); 107193323Sed 108193323Sedprivate: 109193323Sed void AdjustPriorityOfUnscheduledPreds(SUnit *SU); 110193323Sed SUnit *getSingleUnscheduledPred(SUnit *SU); 111193323Sed }; 112193323Sed} 113193323Sed 114193323Sed#endif 115