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