1//===- IterationGraphSorter.h -----------------------------------*- 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// This header file defines the iteration graph sorter (top-sort scheduling).
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef MLIR_DIALECT_SPARSETENSOR_TRANSFORMS_UTILS_ITERATIONGRAPHSORTER_H_
14#define MLIR_DIALECT_SPARSETENSOR_TRANSFORMS_UTILS_ITERATIONGRAPHSORTER_H_
15
16#include "mlir/Dialect/SparseTensor/Transforms/Passes.h"
17#include "mlir/IR/AffineMap.h"
18
19namespace mlir {
20
21// Forward declarations.
22class Value;
23namespace utils {
24enum class IteratorType : uint32_t;
25} // namespace utils
26namespace linalg {
27class GenericOp;
28} // namespace linalg
29
30namespace sparse_tensor {
31
32/// Iteration graph sorting mask,
33enum class SortMask : unsigned {
34 // The individual mask bits.
35 kIncludeDenseOutput = 0x1, // b001
36 kIncludeDenseInput = 0x2, // b010
37 // The subsets of mask bits.
38 kIncludeAll = 0x7, // b111
39 kIncludeDense = 0x3, // b011
40 kSparseOnly = 0x0, // b000
41};
42
43class IterationGraphSorter {
44public:
45 /// Factory method that constructs an iteration graph sorter
46 /// for the given linalg.generic operation with a specific loop ordering
47 /// strategy.
48 static IterationGraphSorter
49 fromGenericOp(linalg::GenericOp genericOp,
50 sparse_tensor::LoopOrderingStrategy strategy);
51
52 /// Returns a permutation that represents the scheduled loop order.
53 /// Note that the returned AffineMap could be null if the kernel
54 /// cannot be scheduled due to cyclic iteration graph.
55 [[nodiscard]] AffineMap sort(SortMask mask, Value ignored = nullptr);
56
57 /// Returns the number of loops in the iteration graph.
58 unsigned getNumLoops() const { return loop2OutLvl.getNumDims(); }
59
60private:
61 // Private constructor.
62 IterationGraphSorter(SmallVector<Value> &&insArg,
63 SmallVector<AffineMap> &&loop2InsLvlArg, Value out,
64 AffineMap loop2OutLvl,
65 SmallVector<utils::IteratorType> &&iterTypesArg,
66 linalg::GenericOp genericOp,
67 sparse_tensor::LoopOrderingStrategy strategy =
68 sparse_tensor::LoopOrderingStrategy::kDefault);
69
70 // Adds all the constraints in the given loop to level map.
71 void addConstraints(Value t, AffineMap loop2LvlMap);
72
73 /// A helper to compute a topological sort. The method has an
74 /// O(n^2) time complexity since we use an adjacency matrix
75 /// representation for the iteration graph.
76 AffineMap topoSort();
77
78 // Input tensors and associated loop to level maps.
79 SmallVector<Value> ins;
80 SmallVector<AffineMap> loop2InsLvl;
81
82 // Output tensor and associated loop to level map.
83 Value out;
84 AffineMap loop2OutLvl;
85
86 // Loop itation types;
87 SmallVector<utils::IteratorType> iterTypes;
88
89 // Adjacency matrix that represents the iteration graph.
90 std::vector<std::vector<bool>> itGraph;
91
92 // InDegree used for topo sort.
93 std::vector<unsigned> inDegree;
94
95 // Loop ordering strategy.
96 sparse_tensor::LoopOrderingStrategy strategy;
97
98 // Prepared once in the constructor for the loop-use strategies.
99 SmallVector<unsigned> loopUseCounts;
100};
101
102} // namespace sparse_tensor
103} // namespace mlir
104
105#endif // MLIR_DIALECT_SPARSETENSOR_TRANSFORMS_UTILS_ITERATIONGRAPHSORTER_H_
106