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
  21 namespace llvm {
  22   class LatencyPriorityQueue;
  23
  24   /// Sorting functions for the Available queue.
  25   struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> {
  26     LatencyPriorityQueue *PQ;
  27     explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
  28
  29     bool operator()(const SUnit* left, const SUnit* right) const;
  30   };
  31
  32   class LatencyPriorityQueue : public SchedulingPriorityQueue {
  33     // SUnits - The SUnits for the current graph.
  34     std::vector<SUnit> *SUnits;
  35
  36     /// NumNodesSolelyBlocking - This vector contains, for every node in the
  37     /// Queue, the number of nodes that the node is the sole unscheduled
  38     /// predecessor for.  This is used as a tie-breaker heuristic for better
  39     /// mobility.
  40     std::vector<unsigned> NumNodesSolelyBlocking;
  41
  42     /// Queue - The queue.
  43     std::vector<SUnit*> Queue;
  44     latency_sort Picker;
  45
  46   public:
  47     LatencyPriorityQueue() : Picker(this) {
  48     }
  49
  50     void initNodes(std::vector<SUnit> &sunits) {
  51       SUnits = &sunits;
  52       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  53     }
  54
  55     void addNode(const SUnit *SU) {
  56       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  57     }
  58
  59     void updateNode(const SUnit *SU) {
  60     }
  61
  62     void releaseState() {
  63       SUnits = 0;
  64     }
  65
  66     unsigned getLatency(unsigned NodeNum) const {
  67       assert(NodeNum < (*SUnits).size());
  68       return (*SUnits)[NodeNum].getHeight();
  69     }
  70
  71     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
  72       assert(NodeNum < NumNodesSolelyBlocking.size());
  73       return NumNodesSolelyBlocking[NodeNum];
  74     }
  75
  76     bool empty() const { return Queue.empty(); }
  77
  78     virtual void push(SUnit *U);
  79
  80     virtual SUnit *pop();
  81
  82     virtual void remove(SUnit *SU);
  83
  84     // ScheduledNode - As nodes are scheduled, we look to see if there are any
  85     // successor nodes that have a single unscheduled predecessor.  If so, that
  86     // single predecessor has a higher priority, since scheduling it will make
  87     // the node available.
  88     void ScheduledNode(SUnit *Node);
  89
  90 private:
  91     void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
  92     SUnit *getSingleUnscheduledPred(SUnit *SU);
  93   };
  94 }
  95
  96 #endif