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/ScheduleDAG.h" |
20 | |
21 | namespace 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. |
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(new_size: SUnits->size(), x: 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 | |
126 | private: |
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 |
135 | |