1//===- SparsificationAndBufferizationPass.cpp - Tensor to Memref Lowering -===//
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 "mlir/Dialect/SparseTensor/Transforms/Passes.h"
10
11#include "mlir/Dialect/Affine/IR/AffineOps.h"
12#include "mlir/Dialect/Bufferization/IR/BufferizableOpInterface.h"
13#include "mlir/Dialect/Bufferization/IR/Bufferization.h"
14#include "mlir/Dialect/Bufferization/Transforms/Bufferize.h"
15#include "mlir/Dialect/Bufferization/Transforms/OneShotAnalysis.h"
16#include "mlir/Dialect/Bufferization/Transforms/OneShotModuleBufferize.h"
17#include "mlir/Dialect/Bufferization/Transforms/Passes.h"
18#include "mlir/Dialect/Bufferization/Transforms/Transforms.h"
19#include "mlir/Dialect/Func/IR/FuncOps.h"
20#include "mlir/Dialect/GPU/IR/GPUDialect.h"
21#include "mlir/Dialect/LLVMIR/LLVMDialectDecl.h"
22#include "mlir/Dialect/Linalg/IR/Linalg.h"
23#include "mlir/Dialect/SCF/IR/SCF.h"
24#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
25#include "mlir/Dialect/Vector/IR/VectorOps.h"
26#include "mlir/Pass/PassManager.h"
27#include "mlir/Transforms/Passes.h"
28
29using namespace mlir;
30
31namespace mlir {
32
33#define GEN_PASS_DEF_SPARSIFICATIONANDBUFFERIZATION
34#include "mlir/Dialect/SparseTensor/Transforms/Passes.h.inc"
35
36namespace sparse_tensor {
37
38/// Return `true` if one of the given types is a sparse tensor type.
39static bool containsSparseTensor(TypeRange types) {
40 for (Type t : types)
41 if (isa<TensorType>(Val: t) && getSparseTensorEncoding(type: t))
42 return true;
43 return false;
44}
45
46/// A pass that lowers tensor ops to memref ops, regardless of whether they are
47/// dense or sparse.
48///
49/// One-Shot Analysis is used to detect RaW conflicts and to insert buffer
50/// copies of the tensor level (`insertTensorCopies`). Afterwards, the lowering
51/// of tensor ops to memref ops follows a different code path depending on
52/// whether the op is sparse or dense:
53///
54/// * Sparse tensor ops are lowered through Sparsification and follow-up pass
55/// that lowers sparse_tensor dialect ops.
56/// * Dense tensor ops are lowered through BufferizableOpInterface
57/// implementations.
58class SparsificationAndBufferizationPass
59 : public impl::SparsificationAndBufferizationBase<
60 SparsificationAndBufferizationPass> {
61public:
62 // Bufferization, sparsification, and sparse storage options.
63 SparsificationAndBufferizationPass(
64 const bufferization::OneShotBufferizationOptions &bufferizationOptions,
65 const SparsificationOptions &sparsificationOptions,
66 bool createSparseDeallocs, bool enableRuntimeLibrary,
67 bool enableBufferInitialization)
68 : bufferizationOptions(bufferizationOptions),
69 sparsificationOptions(sparsificationOptions),
70 createSparseDeallocs(createSparseDeallocs),
71 enableBufferInitialization(enableBufferInitialization) {
72 this->enableRuntimeLibrary = enableRuntimeLibrary;
73 }
74 // Private pass options and visible pass options.
75 SparsificationAndBufferizationPass(
76 const bufferization::OneShotBufferizationOptions &bufferizationOptions,
77 const SparsificationOptions &sparsificationOptions,
78 bool createSparseDeallocs, bool enableRuntimeLibrary,
79 bool enableBufferInitialization, unsigned vl, bool vla, bool index32,
80 bool gpu, SparseEmitStrategy emitStrategy,
81 SparseParallelizationStrategy parallelizationStrategy)
82 : bufferizationOptions(bufferizationOptions),
83 sparsificationOptions(sparsificationOptions),
84 createSparseDeallocs(createSparseDeallocs),
85 enableBufferInitialization(enableBufferInitialization) {
86 // Set the visible pass options explicitly.
87 this->enableRuntimeLibrary = enableRuntimeLibrary;
88 vectorLength = vl;
89 enableVLAVectorization = vla;
90 enableSIMDIndex32 = index32;
91 enableGPULibgen = gpu;
92 sparseEmitStrategy = emitStrategy;
93 parallelization = parallelizationStrategy;
94 }
95
96 /// Bufferize all dense ops. This assumes that no further analysis is needed
97 /// and that all required buffer copies were already inserted by
98 /// `insertTensorCopies` in the form of `bufferization.alloc_tensor` ops.
99 LogicalResult runDenseBufferization() {
100 bufferization::OneShotBufferizationOptions updatedOptions =
101 bufferizationOptions;
102 // Skip all sparse ops.
103 updatedOptions.opFilter.denyOperation(fn: [&](Operation *op) {
104 if (containsSparseTensor(types: TypeRange(op->getResults())) ||
105 containsSparseTensor(types: TypeRange(op->getOperands())))
106 return true;
107 if (auto funcOp = dyn_cast<func::FuncOp>(Val: op)) {
108 FunctionType funcType = funcOp.getFunctionType();
109 if (containsSparseTensor(types: funcType.getInputs()) ||
110 containsSparseTensor(types: funcType.getResults()))
111 return true;
112 }
113 return false;
114 });
115
116 bufferization::BufferizationState bufferizationState;
117
118 if (failed(Result: bufferization::bufferizeModuleOp(moduleOp: getOperation(), options: updatedOptions,
119 state&: bufferizationState)))
120 return failure();
121
122 bufferization::removeBufferizationAttributesInModule(moduleOp: getOperation());
123 return success();
124 }
125
126 void runOnOperation() override {
127 // Overrides the default emit strategy using user-provided value.
128 this->sparsificationOptions.sparseEmitStrategy = sparseEmitStrategy;
129
130 // Overrides the default parallelization strategy using user-provided value.
131 this->sparsificationOptions.parallelizationStrategy = parallelization;
132
133 // Keep sparsification and sparse storage lowering on the same runtime path.
134 this->sparsificationOptions.enableRuntimeLibrary = enableRuntimeLibrary;
135
136 // Run enabling transformations.
137 {
138 OpPassManager pm("builtin.module");
139 pm.addPass(pass: createPreSparsificationRewritePass());
140 pm.addNestedPass<func::FuncOp>(
141 pass: bufferization::createEmptyTensorToAllocTensorPass());
142 if (failed(Result: runPipeline(pipeline&: pm, op: getOperation())))
143 return signalPassFailure();
144 }
145
146 // Insert tensor copies. This step runs One-Shot Analysis (which analyzes
147 // SSA use-def chains of tensor IR) and decides where buffer copies are
148 // needed and where buffers can be written to in-place. These decisions are
149 // materialized in the IR in the form of `bufferization.alloc_tensor` ops.
150 //
151 // Note: All following steps in this pass must be careful not to modify the
152 // structure of the IR (i.e., tensor use-def chains), as that could
153 // invalidate the results of the analysis. From now on, only small and
154 // localized rewrites are allowed, such as replacing a tensor op with its
155 // memref equivalent.
156 bufferization::BufferizationState bufferizationState;
157
158 if (failed(Result: bufferization::insertTensorCopies(
159 op: getOperation(), options: bufferizationOptions, bufferizationState)))
160 return signalPassFailure();
161
162 // Option `testAnalysisOnly` is a debug/testing flag. If set, the results of
163 // OneShotAnalysis are added to the IR via attributes. In that case, do not
164 // continue with the remaining pipeline.
165 if (bufferizationOptions.testAnalysisOnly)
166 return;
167
168 // Bufferize all sparse ops. No further analysis is needed. All required
169 // buffer copies were already inserted by `insertTensorCopies` in the form
170 // of `bufferization.alloc_tensor` ops.
171 {
172 OpPassManager pm("builtin.module");
173 if (enableGPULibgen)
174 pm.addPass(pass: createSparseGPUCodegenPass(numThreads: 0, enableRT: enableRuntimeLibrary));
175 pm.addPass(pass: createSparseReinterpretMapPass(scope: ReinterpretMapScope::kAll));
176 pm.addPass(pass: createSparsificationPass(options: sparsificationOptions));
177 if (sparsificationOptions.sparseEmitStrategy ==
178 SparseEmitStrategy::kSparseIterator) {
179 pm.addNestedPass<func::FuncOp>(pass: createSparseSpaceCollapsePass());
180 pm.addNestedPass<func::FuncOp>(pass: createLowerSparseIterationToSCFPass());
181 }
182
183 pm.addNestedPass<func::FuncOp>(pass: createStageSparseOperationsPass());
184 pm.addPass(pass: createLowerSparseOpsToForeachPass(enableRT: enableRuntimeLibrary,
185 /*enableConvert=*/true));
186 pm.addPass(
187 pass: createSparseReinterpretMapPass(scope: ReinterpretMapScope::kExceptGeneric));
188 pm.addNestedPass<func::FuncOp>(pass: createLowerForeachToSCFPass());
189 pm.addPass(pass: mlir::createLoopInvariantCodeMotionPass());
190 if (vectorLength > 0) {
191 pm.addPass(pass: createSparseVectorizationPass(
192 vectorLength, enableVLAVectorization, enableSIMDIndex32));
193 }
194 if (enableRuntimeLibrary) {
195 pm.addPass(pass: createSparseTensorConversionPass());
196 } else {
197 pm.addPass(pass: createSparseTensorCodegenPass(createSparseDeallocs,
198 enableBufferInitialization));
199 pm.addPass(pass: createSparseBufferRewritePass(enableBufferInitialization));
200 }
201 if (failed(Result: runPipeline(pipeline&: pm, op: getOperation())))
202 return signalPassFailure();
203 }
204
205 // Bufferize all dense ops.
206 if (failed(Result: runDenseBufferization()))
207 signalPassFailure();
208 }
209
210private:
211 bufferization::OneShotBufferizationOptions bufferizationOptions;
212 SparsificationOptions sparsificationOptions;
213 bool createSparseDeallocs;
214 bool enableBufferInitialization;
215};
216
217} // namespace sparse_tensor
218} // namespace mlir
219
220mlir::bufferization::OneShotBufferizationOptions
221mlir::getBufferizationOptionsForSparsification(bool analysisOnly) {
222 using namespace mlir::bufferization;
223 OneShotBufferizationOptions options;
224 options.bufferizeFunctionBoundaries = true;
225 options.setFunctionBoundaryTypeConversion(LayoutMapOption::IdentityLayoutMap);
226 options.unknownTypeConverterFn = [](TensorLikeType tensorType,
227 Attribute memorySpace,
228 const BufferizationOptions &options) {
229 return cast<bufferization::BufferLikeType>(
230 Val: getMemRefTypeWithStaticIdentityLayout(tensorType: cast<TensorType>(Val&: tensorType),
231 memorySpace));
232 };
233 if (analysisOnly) {
234 options.testAnalysisOnly = true;
235 options.printConflicts = true;
236 }
237 // Since this mini-pipeline may be used in alternative pipelines (viz.
238 // different from the default "sparsifier" pipeline) where unknown ops
239 // are handled by alternative bufferization methods that are downstream
240 // of this mini-pipeline, we allow unknown ops by default (failure to
241 // bufferize is eventually apparent by failing to convert to LLVM IR).
242 options.allowUnknownOps = true;
243 return options;
244}
245
246std::unique_ptr<mlir::Pass> mlir::createSparsificationAndBufferizationPass() {
247 SparsificationOptions sparseOptions;
248 return std::make_unique<
249 mlir::sparse_tensor::SparsificationAndBufferizationPass>(
250 args: getBufferizationOptionsForSparsification(/*analysisOnly=*/false),
251 args&: sparseOptions,
252 /*createSparseDeallocs=*/args: false,
253 /*enableRuntimeLibrary=*/args: false,
254 /*enableBufferInitialization=*/args: false);
255}
256
257std::unique_ptr<mlir::Pass> mlir::createSparsificationAndBufferizationPass(
258 const bufferization::OneShotBufferizationOptions &bufferizationOptions,
259 const SparsificationOptions &sparsificationOptions,
260 bool createSparseDeallocs, bool enableRuntimeLibrary,
261 bool enableBufferInitialization, unsigned vectorLength,
262 bool enableVLAVectorization, bool enableSIMDIndex32, bool enableGPULibgen,
263 SparseEmitStrategy emitStrategy,
264 SparseParallelizationStrategy parallelizationStrategy) {
265 return std::make_unique<
266 mlir::sparse_tensor::SparsificationAndBufferizationPass>(
267 args: bufferizationOptions, args: sparsificationOptions, args&: createSparseDeallocs,
268 args&: enableRuntimeLibrary, args&: enableBufferInitialization, args&: vectorLength,
269 args&: enableVLAVectorization, args&: enableSIMDIndex32, args&: enableGPULibgen, args&: emitStrategy,
270 args&: parallelizationStrategy);
271}
272