Line data    Source code

       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/CodeGen/TargetInstrInfo.h"
      24             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      25             : #include "llvm/MC/MCInstrItineraries.h"
      26             : 
      27             : namespace llvm {
      28             :   class ResourcePriorityQueue;
      29             : 
      30             :   /// Sorting functions for the Available queue.
      31             :   struct resource_sort {
      32             :     ResourcePriorityQueue *PQ;
      33           0 :     explicit resource_sort(ResourcePriorityQueue *pq) : PQ(pq) {}
      34             : 
      35             :     bool operator()(const SUnit* LHS, const SUnit* RHS) 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             :     int HorizontalVerticalBalance;
      76             : 
      77             :   public:
      78             :     ResourcePriorityQueue(SelectionDAGISel *IS);
      79             : 
      80           0 :     bool isBottomUp() const override { return false; }
      81             : 
      82             :     void initNodes(std::vector<SUnit> &sunits) override;
      83             : 
      84           0 :     void addNode(const SUnit *SU) override {
      85           0 :       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
      86           0 :     }
      87             : 
      88           0 :     void updateNode(const SUnit *SU) override {}
      89             : 
      90           0 :     void releaseState() override {
      91           0 :       SUnits = nullptr;
      92           0 :     }
      93             : 
      94           0 :     unsigned getLatency(unsigned NodeNum) const {
      95             :       assert(NodeNum < (*SUnits).size());
      96           0 :       return (*SUnits)[NodeNum].getHeight();
      97             :     }
      98             : 
      99             :     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
     100             :       assert(NodeNum < NumNodesSolelyBlocking.size());
     101           0 :       return NumNodesSolelyBlocking[NodeNum];
     102             :     }
     103             : 
     104             :     /// Single cost function reflecting benefit of scheduling SU
     105             :     /// in the current cycle.
     106             :     int 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             :     int regPressureDelta(SUnit *SU, bool RawPressure = false);
     113             :     int rawRegPressureDelta (SUnit *SU, unsigned RCId);
     114             : 
     115           0 :     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 *SU) 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