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 16249423Sdim#ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H 17249423Sdim#define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H 18193323Sed 19193323Sed#include "llvm/CodeGen/ScheduleDAG.h" 20193323Sed 21193323Sednamespace llvm { 22193323Sed class LatencyPriorityQueue; 23218893Sdim 24193323Sed /// Sorting functions for the Available queue. 25193323Sed struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { 26193323Sed LatencyPriorityQueue *PQ; 27193323Sed explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} 28218893Sdim 29193323Sed bool operator()(const SUnit* left, const SUnit* right) const; 30193323Sed }; 31193323Sed 32193323Sed class LatencyPriorityQueue : public SchedulingPriorityQueue { 33193323Sed // SUnits - The SUnits for the current graph. 34193323Sed std::vector<SUnit> *SUnits; 35218893Sdim 36193323Sed /// NumNodesSolelyBlocking - This vector contains, for every node in the 37193323Sed /// Queue, the number of nodes that the node is the sole unscheduled 38193323Sed /// predecessor for. This is used as a tie-breaker heuristic for better 39193323Sed /// mobility. 40193323Sed std::vector<unsigned> NumNodesSolelyBlocking; 41218893Sdim 42198892Srdivacky /// Queue - The queue. 43208599Srdivacky std::vector<SUnit*> Queue; 44208599Srdivacky latency_sort Picker; 45193323Sed 46208599Srdivacky public: 47208599Srdivacky LatencyPriorityQueue() : Picker(this) { 48193323Sed } 49198892Srdivacky 50218893Sdim bool isBottomUp() const { return false; } 51218893Sdim 52193323Sed void initNodes(std::vector<SUnit> &sunits) { 53193323Sed SUnits = &sunits; 54193323Sed NumNodesSolelyBlocking.resize(SUnits->size(), 0); 55193323Sed } 56193323Sed 57193323Sed void addNode(const SUnit *SU) { 58193323Sed NumNodesSolelyBlocking.resize(SUnits->size(), 0); 59193323Sed } 60193323Sed 61193323Sed void updateNode(const SUnit *SU) { 62193323Sed } 63193323Sed 64193323Sed void releaseState() { 65193323Sed SUnits = 0; 66193323Sed } 67218893Sdim 68193323Sed unsigned getLatency(unsigned NodeNum) const { 69193323Sed assert(NodeNum < (*SUnits).size()); 70199989Srdivacky return (*SUnits)[NodeNum].getHeight(); 71193323Sed } 72218893Sdim 73193323Sed unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { 74193323Sed assert(NodeNum < NumNodesSolelyBlocking.size()); 75193323Sed return NumNodesSolelyBlocking[NodeNum]; 76193323Sed } 77218893Sdim 78193323Sed bool empty() const { return Queue.empty(); } 79218893Sdim 80208599Srdivacky virtual void push(SUnit *U); 81218893Sdim 82208599Srdivacky virtual SUnit *pop(); 83193323Sed 84208599Srdivacky virtual void remove(SUnit *SU); 85193323Sed 86218893Sdim virtual void dump(ScheduleDAG* DAG) const; 87218893Sdim 88234353Sdim // scheduledNode - As nodes are scheduled, we look to see if there are any 89193323Sed // successor nodes that have a single unscheduled predecessor. If so, that 90193323Sed // single predecessor has a higher priority, since scheduling it will make 91193323Sed // the node available. 92234353Sdim void scheduledNode(SUnit *Node); 93193323Sed 94193323Sedprivate: 95193323Sed void AdjustPriorityOfUnscheduledPreds(SUnit *SU); 96193323Sed SUnit *getSingleUnscheduledPred(SUnit *SU); 97193323Sed }; 98193323Sed} 99193323Sed 100193323Sed#endif 101