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     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     ~ResourcePriorityQueue() {
  81       delete ResourcesModel;
  82     }
  83
  84     bool isBottomUp() const { return false; }
  85
  86     void initNodes(std::vector<SUnit> &sunits);
  87
  88     void addNode(const SUnit *SU) {
  89       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  90     }
  91
  92     void updateNode(const SUnit *SU) {}
  93
  94     void releaseState() {
  95       SUnits = 0;
  96     }
  97
  98     unsigned getLatency(unsigned NodeNum) const {
  99       assert(NodeNum < (*SUnits).size());
 100       return (*SUnits)[NodeNum].getHeight();
 101     }
 102
 103     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
 104       assert(NodeNum < NumNodesSolelyBlocking.size());
 105       return NumNodesSolelyBlocking[NodeNum];
 106     }
 107
 108     /// Single cost function reflecting benefit of scheduling SU
 109     /// in the current cycle.
 110     signed SUSchedulingCost (SUnit *SU);
 111
 112     /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
 113     ///
 114     void initNumRegDefsLeft(SUnit *SU);
 115     void updateNumRegDefsLeft(SUnit *SU);
 116     signed regPressureDelta(SUnit *SU, bool RawPressure = false);
 117     signed rawRegPressureDelta (SUnit *SU, unsigned RCId);
 118
 119     bool empty() const { return Queue.empty(); }
 120
 121     virtual void push(SUnit *U);
 122
 123     virtual SUnit *pop();
 124
 125     virtual void remove(SUnit *SU);
 126
 127     virtual void dump(ScheduleDAG* DAG) const;
 128
 129     /// scheduledNode - Main resource tracking point.
 130     void scheduledNode(SUnit *Node);
 131     bool isResourceAvailable(SUnit *SU);
 132     void reserveResources(SUnit *SU);
 133
 134 private:
 135     void adjustPriorityOfUnscheduledPreds(SUnit *SU);
 136     SUnit *getSingleUnscheduledPred(SUnit *SU);
 137     unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
 138     unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
 139   };
 140 }
 141
 142 #endif