Line data    Source code

       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       37400 :     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       74800 :     LatencyPriorityQueue() : Picker(this) {
      49             :     }
      50             : 
      51           0 :     bool isBottomUp() const override { return false; }
      52             : 
      53           0 :     void initNodes(std::vector<SUnit> &sunits) override {
      54      425285 :       SUnits = &sunits;
      55      850570 :       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
      56           0 :     }
      57             : 
      58           0 :     void addNode(const SUnit *SU) override {
      59           0 :       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
      60           0 :     }
      61             : 
      62           0 :     void updateNode(const SUnit *SU) override {
      63           0 :     }
      64             : 
      65           0 :     void releaseState() override {
      66      425285 :       SUnits = nullptr;
      67           0 :     }
      68             : 
      69           0 :     unsigned getLatency(unsigned NodeNum) const {
      70             :       assert(NodeNum < (*SUnits).size());
      71     4602732 :       return (*SUnits)[NodeNum].getHeight();
      72             :     }
      73             : 
      74             :     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
      75             :       assert(NodeNum < NumNodesSolelyBlocking.size());
      76    11647122 :       return NumNodesSolelyBlocking[NodeNum];
      77             :     }
      78             : 
      79     1872234 :     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