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 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 isBottomUp()80 bool isBottomUp() const override { return false; } 81 82 void initNodes(std::vector<SUnit> &sunits) override; 83 addNode(const SUnit * SU)84 void addNode(const SUnit *SU) override { 85 NumNodesSolelyBlocking.resize(SUnits->size(), 0); 86 } 87 updateNode(const SUnit * SU)88 void updateNode(const SUnit *SU) override {} 89 releaseState()90 void releaseState() override { 91 SUnits = nullptr; 92 } 93 getLatency(unsigned NodeNum)94 unsigned getLatency(unsigned NodeNum) const { 95 assert(NodeNum < (*SUnits).size()); 96 return (*SUnits)[NodeNum].getHeight(); 97 } 98 getNumSolelyBlockNodes(unsigned NodeNum)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 empty()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 137