LLVM 20.0.0git
ResourcePriorityQueue.h
Go to the documentation of this file.
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
20
21namespace llvm {
22 class DFAPacketizer;
23 class InstrItineraryData;
24 class ResourcePriorityQueue;
25 class SelectionDAGISel;
26 class TargetInstrInfo;
27 class TargetRegisterInfo;
28
29 /// Sorting functions for the Available queue.
32 explicit resource_sort(ResourcePriorityQueue *pq) : PQ(pq) {}
33
34 bool operator()(const SUnit* LHS, const SUnit* RHS) const;
35 };
36
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:
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 int regPressureDelta(SUnit *SU, bool RawPressure = false);
111 int rawRegPressureDelta (SUnit *SU, unsigned RCId);
112
113 bool empty() const override { return Queue.empty(); }
114
115 void push(SUnit *U) override;
116
117 SUnit *pop() override;
118
119 void remove(SUnit *SU) override;
120
121 /// scheduledNode - Main resource tracking point.
122 void scheduledNode(SUnit *SU) override;
123 bool isResourceAvailable(SUnit *SU);
124 void reserveResources(SUnit *SU);
125
126private:
127 void adjustPriorityOfUnscheduledPreds(SUnit *SU);
128 SUnit *getSingleUnscheduledPred(SUnit *SU);
129 unsigned numberRCValPredInSU (SUnit *SU, unsigned RCId);
130 unsigned numberRCValSuccInSU (SUnit *SU, unsigned RCId);
131 };
132}
133
134#endif
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Value * RHS
Value * LHS
Itinerary data supplied by a subtarget to be used by a target.
void scheduledNode(SUnit *SU) override
scheduledNode - Main resource tracking point.
void initNodes(std::vector< SUnit > &sunits) override
Initialize nodes.
unsigned getLatency(unsigned NodeNum) const
void updateNode(const SUnit *SU) override
bool isBottomUp() const override
SUnit * pop() override
Main access point - returns next instructions to be placed in scheduling sequence.
int rawRegPressureDelta(SUnit *SU, unsigned RCId)
int regPressureDelta(SUnit *SU, bool RawPressure=false)
Estimates change in reg pressure from this SU.
void remove(SUnit *SU) override
unsigned getNumSolelyBlockNodes(unsigned NodeNum) const
void reserveResources(SUnit *SU)
Keep track of available resources.
int SUSchedulingCost(SUnit *SU)
Single cost function reflecting benefit of scheduling SU in the current cycle.
void initNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
void addNode(const SUnit *SU) override
bool isResourceAvailable(SUnit *SU)
Check if scheduling of this SU is possible in the current packet.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
This interface is used to plug different priorities computation algorithms into the list scheduler.
Definition: ScheduleDAG.h:514
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
TargetInstrInfo - Interface to description of machine instruction set.
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Sorting functions for the Available queue.
bool operator()(const SUnit *LHS, const SUnit *RHS) const
This heuristic is used if DFA scheduling is not desired for some VLIW platform.
ResourcePriorityQueue * PQ
resource_sort(ResourcePriorityQueue *pq)