1//===- IterationGraphSorter.cpp -------------------------------------------===//
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#include "IterationGraphSorter.h"
10
11#include "mlir/Dialect/Linalg/IR/Linalg.h"
12#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
13#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
14#include "mlir/IR/AffineExprVisitor.h"
15#include "mlir/IR/BuiltinTypes.h"
16#include "llvm/ADT/DenseSet.h"
17
18using namespace mlir;
19using namespace mlir::sparse_tensor;
20
21namespace {
22
23/// A helper class that visits an affine expression and tries to find
24/// an AffineDimExpr to which the corresponding iterator from a GenericOp
25/// matches the desired iterator type. If there is no matched iterator
26/// type, the method returns the first DimExpr in the expression.
27class AffineDimFinder : public AffineExprVisitor<AffineDimFinder> {
28public:
29 explicit AffineDimFinder(ArrayRef<utils::IteratorType> itTypes)
30 : iterTypes(itTypes) {}
31
32 /// Overrides the visit method from AffineExprVisitor.
33 void visitDimExpr(AffineDimExpr expr) {
34 if (pickedDim == nullptr || pickIterType == iterTypes[expr.getPosition()])
35 pickedDim = expr;
36 }
37
38 /// Sets the desired iterator type that we want to pick.
39 void setPickedIterType(utils::IteratorType iterType) {
40 pickIterType = iterType;
41 }
42
43 /// Gets the desired AffineDimExpr.
44 AffineDimExpr getDimExpr() const {
45 return llvm::cast<AffineDimExpr>(Val: pickedDim);
46 }
47
48 /// Walks the graph in post order to find dim expr.
49 void walkPostOrder(AffineExpr expr) {
50 pickedDim = nullptr;
51 AffineExprVisitor<AffineDimFinder>::walkPostOrder(expr);
52 }
53
54private:
55 /// The picked AffineDimExpr after visit.
56 AffineExpr pickedDim;
57 /// The iterator type that we want.
58 utils::IteratorType pickIterType;
59 /// The mapping between levels and iterator types.
60 ArrayRef<utils::IteratorType> iterTypes;
61};
62
63/// Flattens an affine expression into a list of AffineDimExprs.
64struct AffineDimCollector : public AffineExprVisitor<AffineDimCollector> {
65 // Overrides method from AffineExprVisitor.
66 void visitDimExpr(AffineDimExpr expr) { dims.push_back(Elt: expr); }
67 SmallVector<AffineDimExpr> dims;
68};
69
70} // namespace
71
72inline static bool includesAny(SortMask mask1, SortMask mask2) {
73 return static_cast<unsigned>(mask1) & static_cast<unsigned>(mask2);
74}
75
76inline static bool includesDenseInput(SortMask mask) {
77 return includesAny(mask1: mask, mask2: SortMask::kIncludeDenseInput);
78}
79
80inline static bool includesDenseOutput(SortMask mask) {
81 return includesAny(mask1: mask, mask2: SortMask::kIncludeDenseOutput);
82}
83
84/// Returns a sparsity rank for loop ordering: lower values indicate
85/// dimensions that should be placed in outer loops.
86/// When preferDenseOuter is true the ranking is
87/// 0 = Dense, 1 = Compressed, 2 = Singleton, 3 = Other/Unknown.
88/// Otherwise
89/// 0 = Singleton, 1 = Compressed, 2 = Dense, 3 = Other/Unknown.
90static unsigned getLoopSparsityRank(unsigned loop, ArrayRef<Value> allTensors,
91 ArrayRef<AffineMap> allMaps,
92 bool preferDenseOuter) {
93 const unsigned denseRank = preferDenseOuter ? 0 : 2;
94 const unsigned singletonRank = preferDenseOuter ? 2 : 0;
95 const unsigned compressedRank = 1;
96 const unsigned unknownRank = 3;
97
98 unsigned minRank = unknownRank;
99
100 for (auto [tensor, map] : llvm::zip(t&: allTensors, u&: allMaps)) {
101 // Check if this loop accesses this tensor.
102 bool loopAccessesTensor = false;
103 unsigned tensorDim = 0;
104 for (AffineExpr expr : map.getResults()) {
105 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
106 if (dimExpr.getPosition() == loop) {
107 loopAccessesTensor = true;
108 break;
109 }
110 }
111 tensorDim++;
112 }
113
114 if (loopAccessesTensor) {
115 const auto enc = getSparseTensorEncoding(type: tensor.getType());
116 if (!enc) {
117 // Dense tensor.
118 return denseRank;
119 } else {
120 // Sparse tensor - check the level type for this dimension.
121 auto lvlTypes = enc.getLvlTypes();
122 if (tensorDim < lvlTypes.size()) {
123 auto lvlType = lvlTypes[tensorDim];
124 if (isDenseLT(lt: lvlType)) {
125 return denseRank; // Dense level.
126 } else if (isCompressedLT(lt: lvlType)) {
127 minRank = std::min(a: minRank, b: compressedRank); // Compressed level.
128 } else if (isSingletonLT(lt: lvlType)) {
129 minRank = std::min(a: minRank, b: singletonRank); // Singleton level.
130 }
131 }
132 }
133 }
134 }
135
136 return minRank;
137}
138
139/// Count distinct input accesses whose indexing expressions use each loop.
140static SmallVector<unsigned> getLoopUseCounts(linalg::GenericOp genericOp) {
141 SmallVector<unsigned> counts(genericOp.getNumLoops(), 0);
142 llvm::SmallDenseSet<std::pair<Value, AffineMap>> seen;
143 auto maps = genericOp.getIndexingMapsArray();
144
145 for (auto [idx, input] : llvm::enumerate(First: genericOp.getDpsInputs())) {
146 if (genericOp.getRegion().front().getArgument(i: idx).use_empty())
147 continue;
148
149 AffineMap map = maps[idx];
150 if (!seen.insert(V: {input, map}).second)
151 continue;
152
153 llvm::SmallDenseSet<unsigned> accessedLoops;
154 for (AffineExpr expr : map.getResults()) {
155 // Count dependencies within expressions.
156 expr.walk(callback: [&](AffineExpr subExpr) {
157 if (auto dim = dyn_cast<AffineDimExpr>(Val&: subExpr))
158 accessedLoops.insert(V: dim.getPosition());
159 });
160 }
161 // Each access contributes once per loop.
162 for (unsigned loop : accessedLoops)
163 ++counts[loop];
164 }
165 return counts;
166}
167
168AffineMap IterationGraphSorter::topoSort() {
169 // The sorted result will put the first Reduction iterator to the
170 // latest possible position.
171 std::vector<unsigned> redIt; // reduce iterator with 0 degree
172 std::vector<unsigned> parIt; // parallel iterator with 0 degree
173 const unsigned numLoops = getNumLoops();
174 for (unsigned i = 0; i < numLoops; i++) {
175 if (inDegree[i] == 0) {
176 if (iterTypes[i] == utils::IteratorType::reduction)
177 redIt.push_back(x: i);
178 else
179 parIt.push_back(x: i);
180 }
181 }
182
183 SmallVector<unsigned> loopOrder;
184 while (!redIt.empty() || !parIt.empty()) {
185 // We always prefer a parallel loop over a reduction loop because putting
186 // a reduction loop early might make the loop sequence inadmissible.
187 auto &it = !parIt.empty() ? parIt : redIt;
188
189 // Select loop based on strategy.
190 unsigned src;
191 switch (strategy) {
192 case sparse_tensor::LoopOrderingStrategy::kDefault:
193 src = it.back();
194 break;
195 case sparse_tensor::LoopOrderingStrategy::kLoopUseOuter:
196 case sparse_tensor::LoopOrderingStrategy::kLoopUseInner: {
197 // Loop use counts must already be populated.
198 assert(loopUseCounts.size() == numLoops);
199
200 const bool preferMore = strategy == LoopOrderingStrategy::kLoopUseOuter;
201 src = it.front();
202 for (unsigned candidate : it) {
203 unsigned count = loopUseCounts[candidate];
204 unsigned bestCount = loopUseCounts[src];
205
206 if (preferMore ? count > bestCount : count < bestCount)
207 src = candidate;
208 }
209 break;
210 }
211 case sparse_tensor::LoopOrderingStrategy::kDenseOuter: {
212 // Prefer dense, then compressed, then singleton dimensions outermost.
213 // Create combined tensor and map lists for analysis.
214 SmallVector<Value> allTensors = ins;
215 allTensors.push_back(Elt: out);
216 SmallVector<AffineMap> allMaps = loop2InsLvl;
217 allMaps.push_back(Elt: loop2OutLvl);
218
219 // Find loop with minimum (lowest) sparsity rank.
220 unsigned minLoop = it[0];
221 unsigned minRank =
222 getLoopSparsityRank(loop: minLoop, allTensors, allMaps, preferDenseOuter: true);
223
224 for (auto candidateLoop : it) {
225 unsigned rank =
226 getLoopSparsityRank(loop: candidateLoop, allTensors, allMaps, preferDenseOuter: true);
227 if (rank < minRank || (rank == minRank && candidateLoop < minLoop)) {
228 minLoop = candidateLoop;
229 minRank = rank;
230 }
231 }
232 src = minLoop;
233 break;
234 }
235 case sparse_tensor::LoopOrderingStrategy::kSparseOuter: {
236 // Prefer singleton, then compressed, then dense dimensions outermost.
237 SmallVector<Value> allTensors = ins;
238 allTensors.push_back(Elt: out);
239 SmallVector<AffineMap> allMaps = loop2InsLvl;
240 allMaps.push_back(Elt: loop2OutLvl);
241
242 unsigned minLoop = it[0];
243 unsigned minRank =
244 getLoopSparsityRank(loop: minLoop, allTensors, allMaps, preferDenseOuter: false);
245
246 for (auto candidateLoop : it) {
247 unsigned rank =
248 getLoopSparsityRank(loop: candidateLoop, allTensors, allMaps, preferDenseOuter: false);
249 if (rank < minRank || (rank == minRank && candidateLoop < minLoop)) {
250 minLoop = candidateLoop;
251 minRank = rank;
252 }
253 }
254 src = minLoop;
255 break;
256 }
257 }
258
259 loopOrder.push_back(Elt: src);
260 // Remove the selected loop from the worklist.
261 it.erase(position: std::find(first: it.begin(), last: it.end(), val: src));
262 // Update in-degree, and push 0-degree node into worklist.
263 for (unsigned dst = 0; dst < numLoops; dst++) {
264 if (itGraph[src][dst] && --inDegree[dst] == 0) {
265 if (iterTypes[dst] == utils::IteratorType::reduction)
266 redIt.push_back(x: dst);
267 else
268 parIt.push_back(x: dst);
269 }
270 }
271 }
272
273 // Return the topological sort on success.
274 if (loopOrder.size() == numLoops)
275 return AffineMap::getPermutationMap(permutation: loopOrder, context: out.getContext());
276
277 // Cycle detected.
278 return AffineMap();
279}
280
281IterationGraphSorter IterationGraphSorter::fromGenericOp(
282 linalg::GenericOp genericOp, sparse_tensor::LoopOrderingStrategy strategy) {
283 // Must be a demapped sparse kernel.
284 assert(!hasAnyNonIdentityOperandsOrResults(genericOp) &&
285 hasAnySparseOperandOrResult(genericOp) &&
286 genericOp.getNumDpsInits() == 1);
287
288 SmallVector<AffineMap> loopMap = genericOp.getIndexingMapsArray();
289 SmallVector<Value> ins = genericOp.getDpsInputs();
290
291 AffineMap outMap = loopMap.back();
292 loopMap.pop_back();
293
294 Value out = genericOp.getDpsInitOperand(i: 0)->get();
295 SmallVector<utils::IteratorType> iterTypes =
296 genericOp.getIteratorTypesArray();
297
298 return IterationGraphSorter(std::move(ins), std::move(loopMap), out, outMap,
299 std::move(iterTypes), genericOp, strategy);
300}
301
302IterationGraphSorter::IterationGraphSorter(
303 SmallVector<Value> &&insArg, SmallVector<AffineMap> &&loop2InsLvlArg,
304 Value out, AffineMap loop2OutLvl,
305 SmallVector<utils::IteratorType> &&iterTypesArg,
306 linalg::GenericOp genericOp, sparse_tensor::LoopOrderingStrategy strategy)
307 : ins(std::move(insArg)), loop2InsLvl(std::move(loop2InsLvlArg)), out(out),
308 loop2OutLvl(loop2OutLvl), iterTypes(std::move(iterTypesArg)),
309 strategy(strategy) {
310 // One map per tensor.
311 assert(loop2InsLvl.size() == ins.size());
312 // All the affine maps have the same number of dimensions (loops).
313 assert(llvm::all_equal(llvm::map_range(
314 loop2InsLvl, [](AffineMap m) { return m.getNumDims(); })));
315 // The number of results of the map should match the rank of the tensor.
316 assert(llvm::all_of(llvm::zip(loop2InsLvl, ins), [](auto mvPair) {
317 auto [m, v] = mvPair;
318
319 // For ranked types the rank must match.
320 // Simply return true for UnrankedTensorType
321 if (auto shapedType = llvm::dyn_cast<ShapedType>(v.getType())) {
322 return !shapedType.hasRank() ||
323 (m.getNumResults() == shapedType.getRank());
324 }
325 // Non-shaped (scalar) types behave like rank-0.
326 return m.getNumResults() == 0;
327 }));
328
329 switch (strategy) {
330 case LoopOrderingStrategy::kLoopUseOuter:
331 case LoopOrderingStrategy::kLoopUseInner:
332 loopUseCounts = getLoopUseCounts(genericOp);
333 break;
334 default:
335 break;
336 }
337
338 itGraph.resize(new_size: getNumLoops(), x: std::vector<bool>(getNumLoops(), false));
339 inDegree.resize(new_size: getNumLoops());
340}
341
342AffineMap IterationGraphSorter::sort(SortMask mask, Value ignored) {
343 // Reset the adjacency matrix that represents the iteration graph.
344 for (auto &row : itGraph)
345 llvm::fill(Range&: row, Value: false);
346
347 // Reset in-degree.
348 llvm::fill(Range&: inDegree, Value: 0);
349
350 // Add the constraints for the loop to level map.
351 for (auto [in, map] : llvm::zip(t&: ins, u&: loop2InsLvl)) {
352 // Get map and encoding.
353 const auto enc = getSparseTensorEncoding(type: in.getType());
354 // Skip dense inputs when not requested.
355 if ((!enc && !includesDenseInput(mask)) || in == ignored)
356 continue;
357 addConstraints(t: in, loop2LvlMap: map);
358 }
359
360 // Add the constraints for the output map.
361 const auto enc = getSparseTensorEncoding(type: out.getType());
362 if ((enc || includesDenseOutput(mask)) && out != ignored)
363 addConstraints(t: out, loop2LvlMap: loop2OutLvl);
364
365 // Return the topological sort (empty for cyclic).
366 return topoSort();
367}
368
369void IterationGraphSorter::addConstraints(Value t, AffineMap loop2LvlMap) {
370 auto addIterOrdering = [this](unsigned f, unsigned t) {
371 if (!itGraph[f][t] && f != t) {
372 itGraph[f][t] = true;
373 inDegree[t]++;
374 }
375 };
376
377 // Set up a reduction finder.
378 AffineDimFinder finder(iterTypes);
379 finder.setPickedIterType(utils::IteratorType::reduction);
380
381 // To compute iteration graph for tensor[d0 + d1 + d3, d4 + d5 + d6],
382 // we require there exist d_x \in {d0, d1, d3} and d_y \in {d4, d5, d6},
383 // and d_x > d_y && {d0, d1, d3} - d_x > {d4, d5, d6} - d_y
384 const Level lvlRank = loop2LvlMap.getNumResults();
385 for (Level lvl = 1; lvl < lvlRank; lvl++) {
386 const AffineExpr fa = loop2LvlMap.getResult(idx: lvl - 1);
387 const AffineExpr ta = loop2LvlMap.getResult(idx: lvl);
388
389 if (llvm::isa<AffineDimExpr>(Val: fa) || llvm::isa<AffineDimExpr>(Val: ta)) {
390 // Special case when at least one loop2LvlExp is a simple AffineDimExpr
391 // (say, d0) and we require d0 > {d1, d2, ...} or {d1, d2, ...} > d0
392 AffineDimCollector fCollector;
393 fCollector.walkPostOrder(expr: fa);
394 AffineDimCollector tCollector;
395 tCollector.walkPostOrder(expr: ta);
396
397 for (auto fd : fCollector.dims) {
398 for (auto td : tCollector.dims) {
399 const unsigned f = fd.getPosition();
400 const unsigned t = td.getPosition();
401 addIterOrdering(f, t);
402 }
403 }
404 continue;
405 }
406
407 // When both loop2LvlExpr is compound, we pick an abitrary reduction loop
408 // from lhs and rhs and use them as d_x and d_y.
409 finder.walkPostOrder(expr: fa);
410 const AffineDimExpr fexp = finder.getDimExpr();
411 const unsigned fldx = fexp.getPosition();
412
413 finder.walkPostOrder(expr: ta);
414 const AffineDimExpr texp = finder.getDimExpr();
415 const unsigned tldx = texp.getPosition();
416
417 // d_x > d_y
418 addIterOrdering(fldx, tldx);
419
420 AffineDimCollector fCollector;
421 fCollector.walkPostOrder(expr: fa);
422 AffineDimCollector tCollector;
423 tCollector.walkPostOrder(expr: ta);
424
425 // Make sure dx and dy is the last.
426 for (auto fd : fCollector.dims) {
427 const unsigned f = fd.getPosition();
428 addIterOrdering(f, fldx);
429 }
430 for (auto td : tCollector.dims) {
431 const unsigned t = td.getPosition();
432 addIterOrdering(t, tldx);
433 }
434 // {d0, d1, d3} - d_x > {d4, d5, d6} - d_y
435 // This is to ensure that the affine expressions are reduced in sparse
436 // tensor level ordering.
437 for (auto fd : fCollector.dims) {
438 const unsigned f = fd.getPosition();
439 if (f == fldx) // skip d_x
440 continue;
441 for (auto td : tCollector.dims) {
442 const unsigned t = td.getPosition();
443 if (t == tldx) // skip d_y
444 continue;
445 addIterOrdering(f, t);
446 }
447 }
448 }
449}
450