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