1234285Sdim//===----- ResourcePriorityQueue.h - A DFA-oriented priority queue -------===// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This file implements the ResourcePriorityQueue class, which is a 11234285Sdim// SchedulingPriorityQueue that schedules using DFA state to 12234285Sdim// reduce the length of the critical path through the basic block 13234285Sdim// on VLIW platforms. 14234285Sdim// 15234285Sdim//===----------------------------------------------------------------------===// 16234285Sdim 17252723Sdim#ifndef LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H 18252723Sdim#define LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H 19234285Sdim 20234285Sdim#include "llvm/CodeGen/DFAPacketizer.h" 21252723Sdim#include "llvm/CodeGen/ScheduleDAG.h" 22234285Sdim#include "llvm/CodeGen/SelectionDAGISel.h" 23234285Sdim#include "llvm/MC/MCInstrItineraries.h" 24234285Sdim#include "llvm/Target/TargetInstrInfo.h" 25234285Sdim#include "llvm/Target/TargetRegisterInfo.h" 26234285Sdim 27234285Sdimnamespace llvm { 28234285Sdim class ResourcePriorityQueue; 29234285Sdim 30234285Sdim /// Sorting functions for the Available queue. 31234285Sdim struct resource_sort : public std::binary_function<SUnit*, SUnit*, bool> { 32234285Sdim ResourcePriorityQueue *PQ; 33234285Sdim explicit resource_sort(ResourcePriorityQueue *pq) : PQ(pq) {} 34234285Sdim 35234285Sdim bool operator()(const SUnit* left, const SUnit* right) const; 36234285Sdim }; 37234285Sdim 38234285Sdim class ResourcePriorityQueue : public SchedulingPriorityQueue { 39234285Sdim /// SUnits - The SUnits for the current graph. 40234285Sdim std::vector<SUnit> *SUnits; 41234285Sdim 42234285Sdim /// NumNodesSolelyBlocking - This vector contains, for every node in the 43234285Sdim /// Queue, the number of nodes that the node is the sole unscheduled 44234285Sdim /// predecessor for. This is used as a tie-breaker heuristic for better 45234285Sdim /// mobility. 46234285Sdim std::vector<unsigned> NumNodesSolelyBlocking; 47234285Sdim 48234285Sdim /// Queue - The queue. 49234285Sdim std::vector<SUnit*> Queue; 50234285Sdim 51234285Sdim /// RegPressure - Tracking current reg pressure per register class. 52234285Sdim /// 53234285Sdim std::vector<unsigned> RegPressure; 54234285Sdim 55234285Sdim /// RegLimit - Tracking the number of allocatable registers per register 56234285Sdim /// class. 57234285Sdim std::vector<unsigned> RegLimit; 58234285Sdim 59234285Sdim resource_sort Picker; 60234285Sdim const TargetRegisterInfo *TRI; 61234285Sdim const TargetLowering *TLI; 62234285Sdim const TargetInstrInfo *TII; 63234285Sdim const InstrItineraryData* InstrItins; 64234285Sdim /// ResourcesModel - Represents VLIW state. 65234285Sdim /// Not limited to VLIW targets per say, but assumes 66234285Sdim /// definition of DFA by a target. 67234285Sdim DFAPacketizer *ResourcesModel; 68234285Sdim 69234285Sdim /// Resource model - packet/bundle model. Purely 70234285Sdim /// internal at the time. 71234285Sdim std::vector<SUnit*> Packet; 72234285Sdim 73234285Sdim /// Heuristics for estimating register pressure. 74234285Sdim unsigned ParallelLiveRanges; 75234285Sdim signed HorizontalVerticalBalance; 76234285Sdim 77234285Sdim public: 78234285Sdim ResourcePriorityQueue(SelectionDAGISel *IS); 79234285Sdim 80234285Sdim ~ResourcePriorityQueue() { 81234285Sdim delete ResourcesModel; 82234285Sdim } 83234285Sdim 84234285Sdim bool isBottomUp() const { return false; } 85234285Sdim 86234285Sdim void initNodes(std::vector<SUnit> &sunits); 87234285Sdim 88234285Sdim void addNode(const SUnit *SU) { 89234285Sdim NumNodesSolelyBlocking.resize(SUnits->size(), 0); 90234285Sdim } 91234285Sdim 92234285Sdim void updateNode(const SUnit *SU) {} 93234285Sdim 94234285Sdim void releaseState() { 95234285Sdim SUnits = 0; 96234285Sdim } 97234285Sdim 98234285Sdim unsigned getLatency(unsigned NodeNum) const { 99234285Sdim assert(NodeNum < (*SUnits).size()); 100234285Sdim return (*SUnits)[NodeNum].getHeight(); 101234285Sdim } 102234285Sdim 103234285Sdim unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { 104234285Sdim assert(NodeNum < NumNodesSolelyBlocking.size()); 105234285Sdim return NumNodesSolelyBlocking[NodeNum]; 106234285Sdim } 107234285Sdim 108234285Sdim /// Single cost function reflecting benefit of scheduling SU 109234285Sdim /// in the current cycle. 110234285Sdim signed SUSchedulingCost (SUnit *SU); 111234285Sdim 112234285Sdim /// InitNumRegDefsLeft - Determine the # of regs defined by this node. 113234285Sdim /// 114234285Sdim void initNumRegDefsLeft(SUnit *SU); 115234285Sdim void updateNumRegDefsLeft(SUnit *SU); 116234285Sdim signed regPressureDelta(SUnit *SU, bool RawPressure = false); 117234285Sdim signed rawRegPressureDelta (SUnit *SU, unsigned RCId); 118234285Sdim 119234285Sdim bool empty() const { return Queue.empty(); } 120234285Sdim 121234285Sdim virtual void push(SUnit *U); 122234285Sdim 123234285Sdim virtual SUnit *pop(); 124234285Sdim 125234285Sdim virtual void remove(SUnit *SU); 126234285Sdim 127234285Sdim virtual void dump(ScheduleDAG* DAG) const; 128234285Sdim 129234285Sdim /// scheduledNode - Main resource tracking point. 130234285Sdim void scheduledNode(SUnit *Node); 131234285Sdim bool isResourceAvailable(SUnit *SU); 132234285Sdim void reserveResources(SUnit *SU); 133234285Sdim 134234285Sdimprivate: 135234285Sdim void adjustPriorityOfUnscheduledPreds(SUnit *SU); 136234285Sdim SUnit *getSingleUnscheduledPred(SUnit *SU); 137234285Sdim unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId); 138234285Sdim unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId); 139234285Sdim }; 140234285Sdim} 141234285Sdim 142234285Sdim#endif 143