llvm/CodeGen/ResourcePriorityQueue.h

0001 //===----- ResourcePriorityQueue.h - A DFA-oriented priority queue -------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file implements the ResourcePriorityQueue class, which is a
0010 // SchedulingPriorityQueue that schedules using DFA state to
0011 // reduce the length of the critical path through the basic block
0012 // on VLIW platforms.
0013 //
0014 //===----------------------------------------------------------------------===//
0015
0016 #ifndef LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H
0017 #define LLVM_CODEGEN_RESOURCEPRIORITYQUEUE_H
0018
0019 #include "llvm/CodeGen/ScheduleDAG.h"
0020
0021 namespace llvm {
0022   class DFAPacketizer;
0023   class InstrItineraryData;
0024   class ResourcePriorityQueue;
0025   class SelectionDAGISel;
0026   class TargetInstrInfo;
0027   class TargetRegisterInfo;
0028
0029   /// Sorting functions for the Available queue.
0030   struct resource_sort {
0031     ResourcePriorityQueue *PQ;
0032     explicit resource_sort(ResourcePriorityQueue *pq) : PQ(pq) {}
0033
0034     bool operator()(const SUnit* LHS, const SUnit* RHS) const;
0035   };
0036
0037   class ResourcePriorityQueue : public SchedulingPriorityQueue {
0038     /// SUnits - The SUnits for the current graph.
0039     std::vector<SUnit> *SUnits;
0040
0041     /// NumNodesSolelyBlocking - This vector contains, for every node in the
0042     /// Queue, the number of nodes that the node is the sole unscheduled
0043     /// predecessor for.  This is used as a tie-breaker heuristic for better
0044     /// mobility.
0045     std::vector<unsigned> NumNodesSolelyBlocking;
0046
0047     /// Queue - The queue.
0048     std::vector<SUnit*> Queue;
0049
0050     /// RegPressure - Tracking current reg pressure per register class.
0051     ///
0052     std::vector<unsigned> RegPressure;
0053
0054     /// RegLimit - Tracking the number of allocatable registers per register
0055     /// class.
0056     std::vector<unsigned> RegLimit;
0057
0058     resource_sort Picker;
0059     const TargetRegisterInfo *TRI;
0060     const TargetLowering *TLI;
0061     const TargetInstrInfo *TII;
0062     const InstrItineraryData* InstrItins;
0063     /// ResourcesModel - Represents VLIW state.
0064     /// Not limited to VLIW targets per say, but assumes
0065     /// definition of DFA by a target.
0066     std::unique_ptr<DFAPacketizer> ResourcesModel;
0067
0068     /// Resource model - packet/bundle model. Purely
0069     /// internal at the time.
0070     std::vector<SUnit*> Packet;
0071
0072     /// Heuristics for estimating register pressure.
0073     unsigned ParallelLiveRanges;
0074     int HorizontalVerticalBalance;
0075
0076   public:
0077     ResourcePriorityQueue(SelectionDAGISel *IS);
0078
0079     bool isBottomUp() const override { return false; }
0080
0081     void initNodes(std::vector<SUnit> &sunits) override;
0082
0083     void addNode(const SUnit *SU) override {
0084       NumNodesSolelyBlocking.resize(SUnits->size(), 0);
0085     }
0086
0087     void updateNode(const SUnit *SU) override {}
0088
0089     void releaseState() override {
0090       SUnits = nullptr;
0091     }
0092
0093     unsigned getLatency(unsigned NodeNum) const {
0094       assert(NodeNum < (*SUnits).size());
0095       return (*SUnits)[NodeNum].getHeight();
0096     }
0097
0098     unsigned getNumSolelyBlockNodes(unsigned NodeNum) const {
0099       assert(NodeNum < NumNodesSolelyBlocking.size());
0100       return NumNodesSolelyBlocking[NodeNum];
0101     }
0102
0103     /// Single cost function reflecting benefit of scheduling SU
0104     /// in the current cycle.
0105     int SUSchedulingCost (SUnit *SU);
0106
0107     /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
0108     ///
0109     void initNumRegDefsLeft(SUnit *SU);
0110     int regPressureDelta(SUnit *SU, bool RawPressure = false);
0111     int rawRegPressureDelta (SUnit *SU, unsigned RCId);
0112
0113     bool empty() const override { return Queue.empty(); }
0114
0115     void push(SUnit *U) override;
0116
0117     SUnit *pop() override;
0118
0119     void remove(SUnit *SU) override;
0120
0121     /// scheduledNode - Main resource tracking point.
0122     void scheduledNode(SUnit *SU) override;
0123     bool isResourceAvailable(SUnit *SU);
0124     void reserveResources(SUnit *SU);
0125
0126 private:
0127     void adjustPriorityOfUnscheduledPreds(SUnit *SU);
0128     SUnit *getSingleUnscheduledPred(SUnit *SU);
0129     unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
0130     unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
0131   };
0132 }
0133
0134 #endif