include/llvm/CodeGen/ResourcePriorityQueue.h

   1 //===----- ResourcePriorityQueue.h - A DFA-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 implements the ResourcePriorityQueue class, which is a
  11 // SchedulingPriorityQueue that schedules using DFA state to
  12 // reduce the length of the critical path through the basic block
  13 // on VLIW platforms.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H
  18 #define LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H
  19
  20 #include "llvm/CodeGen/DFAPacketizer.h"
  21 #include "llvm/CodeGen/ScheduleDAG.h"
  22 #include "llvm/CodeGen/SelectionDAGISel.h"
  23 #include "llvm/MC/MCInstrItineraries.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Target/TargetRegisterInfo.h"
  26
  27 namespace llvm {
  28   class ResourcePriorityQueue;
  29
  30   /// Sorting functions for the Available queue.
  31   struct resource_sort : public std::binary_function<SUnit*, SUnit*, bool> {
  32     ResourcePriorityQueue *PQ;
  33     explicit resource_sort(ResourcePriorityQueue *pq) : PQ(pq) {}
  34
  35     bool operator()(const SUnit* left, const SUnit* right) const;
  36   };
  37
  38   class ResourcePriorityQueue : public SchedulingPriorityQueue {
  39     /// SUnits - The SUnits for the current graph.
  40     std::vector<SUnit> *SUnits;
  41
  42     /// NumNodesSolelyBlocking - This vector contains, for every node in the
  43     /// Queue, the number of nodes that the node is the sole unscheduled
  44     /// predecessor for.  This is used as a tie-breaker heuristic for better
  45     /// mobility.
  46     std::vector<unsigned> NumNodesSolelyBlocking;
  47
  48     /// Queue - The queue.
  49     std::vector<SUnit*> Queue;
  50
  51     /// RegPressure - Tracking current reg pressure per register class.
  52     ///
  53     std::vector<unsigned> RegPressure;
  54
  55     /// RegLimit - Tracking the number of allocatable registers per register
  56     /// class.
  57     std::vector<unsigned> RegLimit;
  58
  59     resource_sort Picker;
  60     const TargetRegisterInfo *TRI;
  61     const TargetLowering *TLI;
  62     const TargetInstrInfo *TII;
  63     const InstrItineraryData* InstrItins;
  64     /// ResourcesModel - Represents VLIW state.
  65     /// Not limited to VLIW targets per say, but assumes
  66     /// definition of DFA by a target.
  67     std::unique_ptr<DFAPacketizer> ResourcesModel;
  68
  69     /// Resource model - packet/bundle model. Purely
  70     /// internal at the time.
  71     std::vector<SUnit*> Packet;
  72
  73     /// Heuristics for estimating register pressure.
  74     unsigned ParallelLiveRanges;
  75     signed HorizontalVerticalBalance;
  76
  77   public:
  78     ResourcePriorityQueue(SelectionDAGISel *IS);
  79
  80     bool isBottomUp() const override { return false; }
  81
  82     void initNodes(std::vector<SUnit> &sunits) override;
  83
  84     void addNode(const SUnit *SU) override {
  85       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  86     }
  87
  88     void updateNode(const SUnit *SU) override {}
  89
  90     void releaseState() override {
  91       SUnits = nullptr;
  92     }
  93
  94     unsigned getLatency(unsigned NodeNum) const {
  95       assert(NodeNum < (*SUnits).size());
  96       return (*SUnits)[NodeNum].getHeight();
  97     }
  98
  99     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
 100       assert(NodeNum < NumNodesSolelyBlocking.size());
 101       return NumNodesSolelyBlocking[NodeNum];
 102     }
 103
 104     /// Single cost function reflecting benefit of scheduling SU
 105     /// in the current cycle.
 106     signed SUSchedulingCost (SUnit *SU);
 107
 108     /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
 109     ///
 110     void initNumRegDefsLeft(SUnit *SU);
 111     void updateNumRegDefsLeft(SUnit *SU);
 112     signed regPressureDelta(SUnit *SU, bool RawPressure = false);
 113     signed rawRegPressureDelta (SUnit *SU, unsigned RCId);
 114
 115     bool empty() const override { return Queue.empty(); }
 116
 117     void push(SUnit *U) override;
 118
 119     SUnit *pop() override;
 120
 121     void remove(SUnit *SU) override;
 122
 123     /// scheduledNode - Main resource tracking point.
 124     void scheduledNode(SUnit *Node) override;
 125     bool isResourceAvailable(SUnit *SU);
 126     void reserveResources(SUnit *SU);
 127
 128 private:
 129     void adjustPriorityOfUnscheduledPreds(SUnit *SU);
 130     SUnit *getSingleUnscheduledPred(SUnit *SU);
 131     unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
 132     unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
 133   };
 134 }
 135
 136 #endif