LLVM 20.0.0git
ReductionRules.h
Go to the documentation of this file.
1//===- ReductionRules.h - Reduction Rules -----------------------*- C++ -*-===//
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// Reduction Rules.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
14#define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
15
16#include "Graph.h"
17#include "Math.h"
18#include "Solution.h"
19#include <cassert>
20#include <limits>
21
22namespace llvm {
23namespace PBQP {
24
25 /// Reduce a node of degree one.
26 ///
27 /// Propagate costs from the given node, which must be of degree one, to its
28 /// neighbor. Notify the problem domain.
29 template <typename GraphT>
30 void applyR1(GraphT &G, typename GraphT::NodeId NId) {
31 using NodeId = typename GraphT::NodeId;
32 using EdgeId = typename GraphT::EdgeId;
33 using Vector = typename GraphT::Vector;
34 using Matrix = typename GraphT::Matrix;
35 using RawVector = typename GraphT::RawVector;
36
37 assert(G.getNodeDegree(NId) == 1 &&
38 "R1 applied to node with degree != 1.");
39
40 EdgeId EId = *G.adjEdgeIds(NId).begin();
41 NodeId MId = G.getEdgeOtherNodeId(EId, NId);
42
43 const Matrix &ECosts = G.getEdgeCosts(EId);
44 const Vector &XCosts = G.getNodeCosts(NId);
45 RawVector YCosts = G.getNodeCosts(MId);
46
47 // Duplicate a little to avoid transposing matrices.
48 if (NId == G.getEdgeNode1Id(EId)) {
49 for (unsigned j = 0; j < YCosts.getLength(); ++j) {
50 PBQPNum Min = ECosts[0][j] + XCosts[0];
51 for (unsigned i = 1; i < XCosts.getLength(); ++i) {
52 PBQPNum C = ECosts[i][j] + XCosts[i];
53 if (C < Min)
54 Min = C;
55 }
56 YCosts[j] += Min;
57 }
58 } else {
59 for (unsigned i = 0; i < YCosts.getLength(); ++i) {
60 PBQPNum Min = ECosts[i][0] + XCosts[0];
61 for (unsigned j = 1; j < XCosts.getLength(); ++j) {
62 PBQPNum C = ECosts[i][j] + XCosts[j];
63 if (C < Min)
64 Min = C;
65 }
66 YCosts[i] += Min;
67 }
68 }
69 G.setNodeCosts(MId, YCosts);
70 G.disconnectEdge(EId, MId);
71 }
72
73 template <typename GraphT>
74 void applyR2(GraphT &G, typename GraphT::NodeId NId) {
75 using NodeId = typename GraphT::NodeId;
76 using EdgeId = typename GraphT::EdgeId;
77 using Vector = typename GraphT::Vector;
78 using Matrix = typename GraphT::Matrix;
79 using RawMatrix = typename GraphT::RawMatrix;
80
81 assert(G.getNodeDegree(NId) == 2 &&
82 "R2 applied to node with degree != 2.");
83
84 const Vector &XCosts = G.getNodeCosts(NId);
85
86 typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin();
87 EdgeId YXEId = *AEItr,
88 ZXEId = *(++AEItr);
89
90 NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId),
91 ZNId = G.getEdgeOtherNodeId(ZXEId, NId);
92
93 bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId),
94 FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId);
95
96 const Matrix *YXECosts = FlipEdge1 ?
97 new Matrix(G.getEdgeCosts(YXEId).transpose()) :
98 &G.getEdgeCosts(YXEId);
99
100 const Matrix *ZXECosts = FlipEdge2 ?
101 new Matrix(G.getEdgeCosts(ZXEId).transpose()) :
102 &G.getEdgeCosts(ZXEId);
103
104 unsigned XLen = XCosts.getLength(),
105 YLen = YXECosts->getRows(),
106 ZLen = ZXECosts->getRows();
107
108 RawMatrix Delta(YLen, ZLen);
109
110 for (unsigned i = 0; i < YLen; ++i) {
111 for (unsigned j = 0; j < ZLen; ++j) {
112 PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0];
113 for (unsigned k = 1; k < XLen; ++k) {
114 PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k];
115 if (C < Min) {
116 Min = C;
117 }
118 }
119 Delta[i][j] = Min;
120 }
121 }
122
123 if (FlipEdge1)
124 delete YXECosts;
125
126 if (FlipEdge2)
127 delete ZXECosts;
128
129 EdgeId YZEId = G.findEdge(YNId, ZNId);
130
131 if (YZEId == G.invalidEdgeId()) {
132 YZEId = G.addEdge(YNId, ZNId, Delta);
133 } else {
134 const Matrix &YZECosts = G.getEdgeCosts(YZEId);
135 if (YNId == G.getEdgeNode1Id(YZEId)) {
136 G.updateEdgeCosts(YZEId, Delta + YZECosts);
137 } else {
138 G.updateEdgeCosts(YZEId, Delta.transpose() + YZECosts);
139 }
140 }
141
142 G.disconnectEdge(YXEId, YNId);
143 G.disconnectEdge(ZXEId, ZNId);
144
145 // TODO: Try to normalize newly added/modified edge.
146 }
147
148#ifndef NDEBUG
149 // Does this Cost vector have any register options ?
150 template <typename VectorT>
151 bool hasRegisterOptions(const VectorT &V) {
152 unsigned VL = V.getLength();
153
154 // An empty or spill only cost vector does not provide any register option.
155 if (VL <= 1)
156 return false;
157
158 // If there are registers in the cost vector, but all of them have infinite
159 // costs, then ... there is no available register.
160 for (unsigned i = 1; i < VL; ++i)
161 if (V[i] != std::numeric_limits<PBQP::PBQPNum>::infinity())
162 return true;
163
164 return false;
165 }
166#endif
167
168 // Find a solution to a fully reduced graph by backpropagation.
169 //
170 // Given a graph and a reduction order, pop each node from the reduction
171 // order and greedily compute a minimum solution based on the node costs, and
172 // the dependent costs due to previously solved nodes.
173 //
174 // Note - This does not return the graph to its original (pre-reduction)
175 // state: the existing solvers destructively alter the node and edge
176 // costs. Given that, the backpropagate function doesn't attempt to
177 // replace the edges either, but leaves the graph in its reduced
178 // state.
179 template <typename GraphT, typename StackT>
180 Solution backpropagate(GraphT& G, StackT stack) {
181 using NodeId = GraphBase::NodeId;
182 using Matrix = typename GraphT::Matrix;
183 using RawVector = typename GraphT::RawVector;
184
185 Solution s;
186
187 while (!stack.empty()) {
188 NodeId NId = stack.back();
189 stack.pop_back();
190
191 RawVector v = G.getNodeCosts(NId);
192
193#if LLVM_ENABLE_ABI_BREAKING_CHECKS
194 // Although a conservatively allocatable node can be allocated to a register,
195 // spilling it may provide a lower cost solution. Assert here that spilling
196 // is done by choice, not because there were no register available.
197 if (G.getNodeMetadata(NId).wasConservativelyAllocatable())
198 assert(hasRegisterOptions(v) && "A conservatively allocatable node "
199 "must have available register options");
200#endif
201
202 for (auto EId : G.adjEdgeIds(NId)) {
203 const Matrix& edgeCosts = G.getEdgeCosts(EId);
204 if (NId == G.getEdgeNode1Id(EId)) {
205 NodeId mId = G.getEdgeNode2Id(EId);
206 v += edgeCosts.getColAsVector(s.getSelection(mId));
207 } else {
208 NodeId mId = G.getEdgeNode1Id(EId);
209 v += edgeCosts.getRowAsVector(s.getSelection(mId));
210 }
211 }
212
213 s.setSelection(NId, v.minIndex());
214 }
215
216 return s;
217 }
218
219} // end namespace PBQP
220} // end namespace llvm
221
222#endif // LLVM_CODEGEN_PBQP_REDUCTIONRULES_H
#define G(x, y, z)
Definition: MD5.cpp:56
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned NodeId
Definition: Graph.h:28
PBQP Matrix class.
Definition: Math.h:121
unsigned getRows() const
Return the number of rows in this matrix.
Definition: Math.h:161
Vector getColAsVector(unsigned C) const
Returns the given column as a vector.
Definition: Math.h:196
Vector getRowAsVector(unsigned R) const
Returns the given row as a vector.
Definition: Math.h:187
Represents a solution to a PBQP problem.
Definition: Solution.h:26
void setSelection(GraphBase::NodeId nodeId, unsigned selection)
Set the selection for a given node.
Definition: Solution.h:38
unsigned getSelection(GraphBase::NodeId nodeId) const
Get a node's selection.
Definition: Solution.h:45
PBQP Vector class.
Definition: Math.h:25
unsigned getLength() const
Return the length of the vector.
Definition: Math.h:60
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
float PBQPNum
Definition: Math.h:22
void applyR2(GraphT &G, typename GraphT::NodeId NId)
void applyR1(GraphT &G, typename GraphT::NodeId NId)
Reduce a node of degree one.
Solution backpropagate(GraphT &G, StackT stack)
bool hasRegisterOptions(const VectorT &V)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18