include/llvm/CodeGen/ResourcePriorityQueue.h

   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/DFAPacketizer.h"
  20 #include "llvm/CodeGen/ScheduleDAG.h"
  21 #include "llvm/CodeGen/SelectionDAGISel.h"
  22 #include "llvm/CodeGen/TargetInstrInfo.h"
  23 #include "llvm/CodeGen/TargetRegisterInfo.h"
  24 #include "llvm/MC/MCInstrItineraries.h"
  25
  26 namespace llvm {
  27   class ResourcePriorityQueue;
  28
  29   /// Sorting functions for the Available queue.
  30   struct resource_sort {
  31     ResourcePriorityQueue *PQ;
  32     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
  79     bool isBottomUp() const override { return false; }
  80
  81     void initNodes(std::vector<SUnit> &sunits) override;
  82
  83     void addNode(const SUnit *SU) override {
  84       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
  85     }
  86
  87     void updateNode(const SUnit *SU) override {}
  88
  89     void releaseState() override {
  90       SUnits = nullptr;
  91     }
  92
  93     unsigned getLatency(unsigned NodeNum) const {
  94       assert(NodeNum < (*SUnits).size());
  95       return (*SUnits)[NodeNum].getHeight();
  96     }
  97
  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     void updateNumRegDefsLeft(SUnit *SU);
 111     int regPressureDelta(SUnit *SU, bool RawPressure = false);
 112     int rawRegPressureDelta (SUnit *SU, unsigned RCId);
 113
 114     bool empty() const override { return Queue.empty(); }
 115
 116     void push(SUnit *U) override;
 117
 118     SUnit *pop() override;
 119
 120     void remove(SUnit *SU) override;
 121
 122     /// scheduledNode - Main resource tracking point.
 123     void scheduledNode(SUnit *SU) override;
 124     bool isResourceAvailable(SUnit *SU);
 125     void reserveResources(SUnit *SU);
 126
 127 private:
 128     void adjustPriorityOfUnscheduledPreds(SUnit *SU);
 129     SUnit *getSingleUnscheduledPred(SUnit *SU);
 130     unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
 131     unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
 132   };
 133 }
 134
 135 #endif