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