Home | History | Annotate | Download | only in CodeGen 
      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
    143