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