include/llvm/CodeGen/LatencyPriorityQueue.h

   1 //===---- LatencyPriorityQueue.h - A latency-oriented priority queue ------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file declares the LatencyPriorityQueue class, which is a
  10 // SchedulingPriorityQueue that schedules using latency information to
  11 // reduce the length of the critical path through the basic block.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H
  16 #define LLVM_CODEGEN_LATENCYPRIORITYQUEUE_H
  17
  18 #include "llvm/CodeGen/ScheduleDAG.h"
  19 #include "llvm/Config/llvm-config.h"
  20
  21 namespace llvm {
  22   class LatencyPriorityQueue;
  23
  24   /// Sorting functions for the Available queue.
  25   struct latency_sort {
  26     LatencyPriorityQueue *PQ;
  27     explicit latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {}
  28
  29     bool operator()(const SUnit* LHS, const SUnit* RHS) 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     bool isBottomUp() const override { return false; }
  51
  52     void initNodes(std::vector<SUnit> &sunits) override {
  53       SUnits = &sunits;
  54       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  55     }
  56
  57     void addNode(const SUnit *SU) override {
  58       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  59     }
  60
  61     void updateNode(const SUnit *SU) override {
  62     }
  63
  64     void releaseState() override {
  65       SUnits = nullptr;
  66     }
  67
  68     unsigned getLatency(unsigned NodeNum) const {
  69       assert(NodeNum < (*SUnits).size());
  70       return (*SUnits)[NodeNum].getHeight();
  71     }
  72
  73     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
  74       assert(NodeNum < NumNodesSolelyBlocking.size());
  75       return NumNodesSolelyBlocking[NodeNum];
  76     }
  77
  78     bool empty() const override { return Queue.empty(); }
  79
  80     void push(SUnit *U) override;
  81
  82     SUnit *pop() override;
  83
  84     void remove(SUnit *SU) override;
  85
  86 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  87     LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override;
  88 #endif
  89
  90     // scheduledNode - As nodes are scheduled, we look to see if there are any
  91     // successor nodes that have a single unscheduled predecessor.  If so, that
  92     // single predecessor has a higher priority, since scheduling it will make
  93     // the node available.
  94     void scheduledNode(SUnit *SU) override;
  95
  96 private:
  97     void AdjustPriorityOfUnscheduledPreds(SUnit *SU);
  98     SUnit *getSingleUnscheduledPred(SUnit *SU);
  99   };
 100 }
 101
 102 #endif