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; resource_sortresource_sort33 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 ~ResourcePriorityQueue()80 ~ResourcePriorityQueue() { 81 delete ResourcesModel; 82 } 83 isBottomUp()84 bool isBottomUp() const override { return false; } 85 86 void initNodes(std::vector<SUnit> &sunits) override; 87 addNode(const SUnit * SU)88 void addNode(const SUnit *SU) override { 89 NumNodesSolelyBlocking.resize(SUnits->size(), 0); 90 } 91 updateNode(const SUnit * SU)92 void updateNode(const SUnit *SU) override {} 93 releaseState()94 void releaseState() override { 95 SUnits = nullptr; 96 } 97 getLatency(unsigned NodeNum)98 unsigned getLatency(unsigned NodeNum) const { 99 assert(NodeNum < (*SUnits).size()); 100 return (*SUnits)[NodeNum].getHeight(); 101 } 102 getNumSolelyBlockNodes(unsigned NodeNum)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 empty()119 bool empty() const override { return Queue.empty(); } 120 121 void push(SUnit *U) override; 122 123 SUnit *pop() override; 124 125 void remove(SUnit *SU) override; 126 127 void dump(ScheduleDAG* DAG) const override; 128 129 /// scheduledNode - Main resource tracking point. 130 void scheduledNode(SUnit *Node) override; 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 143