include/llvm/CodeGen/LatencyPriorityQueue.h

   1 //===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file declares the LatencyPriorityQueue class, which is a
  11 // SchedulingPriorityQueue that schedules using latency information to
  12 // reduce the length of the critical path through the basic block.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #ifndef LATENCY_PRIORITY_QUEUE_H
  17 #define LATENCY_PRIORITY_QUEUE_H
  18
  19 #include "llvm/CodeGen/ScheduleDAG.h"
  20 #include "llvm/ADT/PriorityQueue.h"
  21
  22 namespace llvm {
  23   class LatencyPriorityQueue;
  24
  25   /// Sorting functions for the Available queue.
  26   struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> {
  27     LatencyPriorityQueue *PQ;
  28     explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
  29
  30     bool operator()(const SUnit* left, const SUnit* right) const;
  31   };
  32
  33   class LatencyPriorityQueue : public SchedulingPriorityQueue {
  34     // SUnits - The SUnits for the current graph.
  35     std::vector<SUnit> *SUnits;
  36
  37     // Latencies - The latency (max of latency from this node to the bb exit)
  38     // for each node.
  39     std::vector<int> Latencies;
  40
  41     /// NumNodesSolelyBlocking - This vector contains, for every node in the
  42     /// Queue, the number of nodes that the node is the sole unscheduled
  43     /// predecessor for.  This is used as a tie-breaker heuristic for better
  44     /// mobility.
  45     std::vector<unsigned> NumNodesSolelyBlocking;
  46
  47     PriorityQueue<SUnit*, std::vector<SUnit*>, latency_sort> Queue;
  48 public:
  49     LatencyPriorityQueue() : Queue(latency_sort(this)) {
  50     }
  51
  52     void initNodes(std::vector<SUnit> &sunits) {
  53       SUnits = &sunits;
  54       // Calculate node priorities.
  55       CalculatePriorities();
  56     }
  57
  58     void addNode(const SUnit *SU) {
  59       Latencies.resize(SUnits->size(), -1);
  60       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  61       CalcLatency(*SU);
  62     }
  63
  64     void updateNode(const SUnit *SU) {
  65       Latencies[SU->NodeNum] = -1;
  66       CalcLatency(*SU);
  67     }
  68
  69     void releaseState() {
  70       SUnits = 0;
  71       Latencies.clear();
  72     }
  73
  74     unsigned getLatency(unsigned NodeNum) const {
  75       assert(NodeNum < Latencies.size());
  76       return Latencies[NodeNum];
  77     }
  78
  79     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
  80       assert(NodeNum < NumNodesSolelyBlocking.size());
  81       return NumNodesSolelyBlocking[NodeNum];
  82     }
  83
  84     unsigned size() const { return Queue.size(); }
  85
  86     bool empty() const { return Queue.empty(); }
  87
  88     virtual void push(SUnit *U) {
  89       push_impl(U);
  90     }
  91     void push_impl(SUnit *U);
  92
  93     void push_all(const std::vector<SUnit *> &Nodes) {
  94       for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
  95         push_impl(Nodes[i]);
  96     }
  97
  98     SUnit *pop() {
  99       if (empty()) return NULL;
 100       SUnit *V = Queue.top();
 101       Queue.pop();
 102       return V;
 103     }
 104
 105     void remove(SUnit *SU) {
 106       assert(!Queue.empty() && "Not in queue!");
 107       Queue.erase_one(SU);
 108     }
 109
 110     // ScheduledNode - As nodes are scheduled, we look to see if there are any
 111     // successor nodes that have a single unscheduled predecessor.  If so, that
 112     // single predecessor has a higher priority, since scheduling it will make
 113     // the node available.
 114     void ScheduledNode(SUnit *Node);
 115
 116 private:
 117     void CalculatePriorities();
 118     int CalcLatency(const SUnit &SU);
 119     void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
 120     SUnit *getSingleUnscheduledPred(SUnit *SU);
 121   };
 122 }
 123
 124 #endif