1//===- Loops.cpp - conversion from Linalg named and generic ops to loops --===//
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/Linalg/Passes.h"
10
11#include "mlir/Dialect/Affine/IR/AffineOps.h"
12#include "mlir/Dialect/Arith/IR/Arith.h"
13#include "mlir/Dialect/Func/IR/FuncOps.h"
14#include "mlir/Dialect/Linalg/IR/Linalg.h"
15#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
16#include "mlir/Dialect/Linalg/Utils/Utils.h"
17#include "mlir/Dialect/SCF/Transforms/Transforms.h"
18#include "mlir/Dialect/SCF/Utils/AffineCanonicalizationUtils.h"
19#include "mlir/IR/AffineExpr.h"
20#include "mlir/IR/AffineMap.h"
21#include "mlir/IR/IRMapping.h"
22#include "mlir/Support/LLVM.h"
23#include "mlir/Transforms/DialectConversion.h"
24#include "mlir/Transforms/FoldUtils.h"
25#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
26#include "llvm/ADT/TypeSwitch.h"
27
28namespace mlir {
29#define GEN_PASS_DEF_CONVERTLINALGTOAFFINELOOPSPASS
30#define GEN_PASS_DEF_CONVERTLINALGTOLOOPSPASS
31#define GEN_PASS_DEF_CONVERTLINALGTOPARALLELLOOPSPASS
32#include "mlir/Dialect/Linalg/Passes.h.inc"
33} // namespace mlir
34
35using namespace mlir;
36using namespace mlir::linalg;
37
38static SmallVector<Value> makeCanonicalAffineApplies(OpBuilder &b, Location loc,
39 AffineMap map,
40 ArrayRef<Value> vals) {
41 if (map.isEmpty())
42 return {};
43
44 assert(map.getNumInputs() == vals.size());
45 SmallVector<Value> res;
46 res.reserve(N: map.getNumResults());
47 auto dims = map.getNumDims();
48 for (auto e : map.getResults()) {
49 auto exprMap = AffineMap::get(dimCount: dims, symbolCount: map.getNumSymbols(), result: e);
50 SmallVector<Value> operands(vals);
51 affine::canonicalizeMapAndOperands(map: &exprMap, operands: &operands);
52 res.push_back(Elt: affine::AffineApplyOp::create(builder&: b, location: loc, map: exprMap, mapOperands: operands));
53 }
54 return res;
55}
56
57template <typename LoadOpTy, typename StoreOpTy, typename OpType>
58static void inlineRegionAndEmitStore(OpBuilder &b, Location loc, OpType op,
59 ArrayRef<Value> indexedValues,
60 ArrayRef<SmallVector<Value>> indexing,
61 ArrayRef<Value> outputBuffers) {
62 auto &block = op->getRegion(0).front();
63 IRMapping map;
64 map.map(block.getArguments(), indexedValues);
65 for (auto &op : block.without_terminator()) {
66 auto *newOp = b.clone(op, map);
67 map.map(op.getResults(), newOp->getResults());
68 }
69
70 Operation *terminator = block.getTerminator();
71 for (OpOperand &operand : terminator->getOpOperands()) {
72 Value toStore = map.lookupOrDefault(from: operand.get());
73 StoreOpTy::create(b, loc, toStore,
74 outputBuffers[operand.getOperandNumber()],
75 indexing[operand.getOperandNumber()]);
76 }
77}
78
79/// Emits the MLIR for the scalar part of the generic op by:
80/// 1. Emitting load ops for each input and output view in order. This is
81/// achieved by applying the appropriate input or output map to the
82/// enclosing induction variables.
83/// 2. Emitting a call to `op.fun()` that takes as arguments the scalars
84/// from point 1. above.
85/// 3. Emitting store ops to store the results of 2. to the output
86/// views.
87///
88/// An example output may resemble:
89///
90/// ```
91/// scf.for %i = %c0 to %0 step %c1 {
92/// scf.for %j = %c0 to %1 step %c1 {
93/// scf.for %k = %c0 to %4 step %c1 {
94/// %11 = load %arg0[%i, %j] :
95/// memref<?x?xf32, stride_specification>
96/// %12 = load %arg1[%i, %j, %k] :
97/// memref<?x?x?xf32, stride_specification>
98/// %13 = load %arg2[%i, %k, %j] :
99/// memref<?x?x?xf32, stride_specification>
100/// %14:2 = call @foo(%11, %12, %13) : (f32, f32, f32) -> (f32, f32)
101/// store %14#0, %arg1[%i, %j, %k] :
102/// memref<?x?x?Xf32, stride_specification>
103/// store %14#1, %arg2[%i, %k, %j] :
104/// memref<?x?x?Xf32, stride_specification>
105/// }
106/// }
107/// }
108/// ```
109template <typename LoadOpTy, typename StoreOpTy>
110static void emitScalarImplementation(OpBuilder &b, Location loc,
111 ArrayRef<Value> allIvs,
112 LinalgOp linalgOp) {
113 assert(linalgOp.hasPureBufferSemantics() &&
114 "expected linalg op with buffer semantics");
115 SmallVector<Value> indexedValues;
116 indexedValues.reserve(N: linalgOp->getNumOperands());
117
118 auto allIvsPlusDims = SmallVector<Value>(allIvs);
119
120 // TODO: Avoid the loads if the corresponding argument of the
121 // region has no uses.
122 // 1.a. Emit load from input operand or for scalars access the operand itself.
123 for (OpOperand *inputOperand : linalgOp.getDpsInputOperands()) {
124 if (linalgOp.isScalar(opOperand: inputOperand)) {
125 indexedValues.push_back(Elt: inputOperand->get());
126 continue;
127 }
128 auto indexing = makeCanonicalAffineApplies(
129 b, loc, map: linalgOp.getMatchingIndexingMap(opOperand: inputOperand), vals: allIvsPlusDims);
130 indexedValues.push_back(
131 Elt: LoadOpTy::create(b, loc, inputOperand->get(), indexing));
132 }
133 // 1.b. Emit load from output views.
134 for (OpOperand &outputOperand : linalgOp.getDpsInitsMutable()) {
135 SmallVector<Value> indexing = makeCanonicalAffineApplies(
136 b, loc, map: linalgOp.getMatchingIndexingMap(opOperand: &outputOperand),
137 vals: allIvsPlusDims);
138 indexedValues.push_back(
139 Elt: LoadOpTy::create(b, loc, outputOperand.get(), indexing));
140 }
141
142 // TODO: When a region inliner exists, use it.
143 // 2. Inline region, currently only works for a single basic block.
144 // 3. Emit store.
145 SmallVector<SmallVector<Value>, 8> indexing;
146 SmallVector<Value> outputBuffers;
147 for (OpOperand &outputOperand : linalgOp.getDpsInitsMutable()) {
148 if (!isa<MemRefType>(Val: outputOperand.get().getType()))
149 continue;
150 indexing.push_back(Elt: makeCanonicalAffineApplies(
151 b, loc, map: linalgOp.getMatchingIndexingMap(opOperand: &outputOperand),
152 vals: allIvsPlusDims));
153 outputBuffers.push_back(Elt: outputOperand.get());
154 }
155 inlineRegionAndEmitStore<LoadOpTy, StoreOpTy>(b, loc, linalgOp, indexedValues,
156 indexing, outputBuffers);
157}
158
159/// Replace the index operations in the body of the loop nest by the matching
160/// induction variables.
161static void replaceIndexOpsByInductionVariables(RewriterBase &rewriter,
162 LinalgOp linalgOp,
163 ArrayRef<Operation *> loopOps) {
164 // Extract the induction variables of the loop nest from outer to inner.
165 SmallVector<Value> allIvs;
166 for (Operation *loopOp : loopOps) {
167 llvm::TypeSwitch<Operation *>(loopOp)
168 .Case(caseFn: [&](scf::ParallelOp parallelOp) {
169 allIvs.append(RHS: parallelOp.getInductionVars());
170 })
171 .Case(caseFn: [&](scf::ForOp forOp) {
172 allIvs.push_back(Elt: forOp.getInductionVar());
173 })
174 .Case(caseFn: [&](affine::AffineForOp affineForOp) {
175 allIvs.push_back(Elt: affineForOp.getInductionVar());
176 })
177 .DefaultUnreachable(message: "unexpected op");
178 }
179 assert(linalgOp.getNumLoops() == allIvs.size() &&
180 "expected the number of loops and induction variables to match");
181 // Replace the index operations in the body of the innermost loop op.
182 if (!loopOps.empty()) {
183 auto loopOp = cast<LoopLikeOpInterface>(Val: loopOps.back());
184 for (Region *r : loopOp.getLoopRegions())
185 for (IndexOp indexOp : llvm::make_early_inc_range(Range: r->getOps<IndexOp>()))
186 rewriter.replaceOp(op: indexOp, newValues: allIvs[indexOp.getDim()]);
187 }
188}
189
190template <typename LoopTy>
191static FailureOr<LinalgLoops> linalgOpToLoopsImpl(RewriterBase &rewriter,
192 LinalgOp linalgOp) {
193 using LoadOpTy =
194 std::conditional_t<std::is_same<LoopTy, affine::AffineForOp>::value,
195 affine::AffineLoadOp, memref::LoadOp>;
196 using StoreOpTy =
197 std::conditional_t<std::is_same<LoopTy, affine::AffineForOp>::value,
198 affine::AffineStoreOp, memref::StoreOp>;
199
200 // The flattened loopToOperandRangesMaps is expected to be an invertible
201 // permutation map (which is asserted in the inverse calculation).
202 assert(linalgOp.hasPureBufferSemantics() &&
203 "expected linalg op with buffer semantics");
204
205 auto loopRanges = linalgOp.createLoopRanges(b&: rewriter, loc: linalgOp.getLoc());
206 auto iteratorTypes = linalgOp.getIteratorTypesArray();
207
208 SmallVector<Value> allIvs;
209 GenerateLoopNest<LoopTy>::doit(
210 rewriter, linalgOp.getLoc(), loopRanges, linalgOp, iteratorTypes,
211 [&](OpBuilder &b, Location loc, ValueRange ivs,
212 ValueRange operandValuesToUse) -> scf::ValueVector {
213 assert(operandValuesToUse == linalgOp->getOperands() &&
214 "expect operands are captured and not passed by loop argument");
215 allIvs.append(in_start: ivs.begin(), in_end: ivs.end());
216 emitScalarImplementation<LoadOpTy, StoreOpTy>(b, loc, allIvs, linalgOp);
217 return scf::ValueVector{};
218 });
219 // Number of loop ops might be different from the number of ivs since some
220 // loops like affine.parallel and scf.parallel have multiple ivs.
221 SetVector<Operation *> loopSet;
222 for (Value iv : allIvs) {
223 if (!iv)
224 return failure();
225 // The induction variable is a block argument of the entry block of the
226 // loop operation.
227 BlockArgument ivVal = dyn_cast<BlockArgument>(Val&: iv);
228 if (!ivVal)
229 return failure();
230 loopSet.insert(X: ivVal.getOwner()->getParentOp());
231 }
232 LinalgLoops loops(loopSet.begin(), loopSet.end());
233 // Replace all index operations in the loop body.
234 replaceIndexOpsByInductionVariables(rewriter, linalgOp, loopOps: loops);
235 return loops;
236}
237
238namespace {
239template <typename LoopType>
240class LinalgRewritePattern : public RewritePattern {
241public:
242 LinalgRewritePattern(MLIRContext *context)
243 : RewritePattern(MatchAnyOpTypeTag(), /*benefit=*/1, context) {}
244
245 LogicalResult matchAndRewrite(Operation *op,
246 PatternRewriter &rewriter) const override {
247 auto linalgOp = dyn_cast<LinalgOp>(Val: op);
248 if (!isa<LinalgOp>(Val: op) || !linalgOp.hasPureBufferSemantics()) {
249 return rewriter.notifyMatchFailure(
250 arg&: op, msg: "expected linalg op with buffer semantics");
251 }
252 if (failed(linalgOpToLoopsImpl<LoopType>(rewriter, linalgOp)))
253 return failure();
254 rewriter.eraseOp(op);
255 return success();
256 }
257};
258
259/// Local folding pattern for AffineApplyOp that we can apply greedily.
260/// This replaces AffineApplyOp by the proper value in cases where the
261/// associated map is trivial.
262/// A trivial map here is defined as a map with a single result and either:
263/// 1. Zero operand + returns a single AffineConstantExpr
264/// 2. One operand + returns a single AffineDimExpr
265/// 3. One operand + returns a single AffineSymbolExpr
266//
267/// In the first case, the AffineApplyOp is replaced by a new constant. In the
268/// other cases, it is replaced by its unique operand.
269struct FoldAffineOp : public RewritePattern {
270 FoldAffineOp(MLIRContext *context)
271 : RewritePattern(affine::AffineApplyOp::getOperationName(), 0, context) {}
272
273 LogicalResult matchAndRewrite(Operation *op,
274 PatternRewriter &rewriter) const override {
275 auto affineApplyOp = cast<affine::AffineApplyOp>(Val: op);
276 auto map = affineApplyOp.getAffineMap();
277 if (map.getNumResults() != 1 || map.getNumInputs() > 1)
278 return failure();
279
280 AffineExpr expr = map.getResult(idx: 0);
281 if (map.getNumInputs() == 0) {
282 if (auto val = dyn_cast<AffineConstantExpr>(Val&: expr)) {
283 rewriter.replaceOpWithNewOp<arith::ConstantIndexOp>(op, args: val.getValue());
284 return success();
285 }
286 return failure();
287 }
288 if (isa<AffineDimExpr, AffineSymbolExpr>(Val: expr)) {
289 rewriter.replaceOp(op, newValues: op->getOperand(idx: 0));
290 return success();
291 }
292 return failure();
293 }
294};
295
296template <typename LoopType>
297static void lowerLinalgToLoopsImpl(Operation *enclosingOp) {
298 MLIRContext *context = enclosingOp->getContext();
299 RewritePatternSet patterns(context);
300 patterns.add<LinalgRewritePattern<LoopType>>(context);
301 memref::DimOp::getCanonicalizationPatterns(results&: patterns, context);
302 tensor::DimOp::getCanonicalizationPatterns(results&: patterns, context);
303 affine::AffineApplyOp::getCanonicalizationPatterns(results&: patterns, context);
304 patterns.add<FoldAffineOp>(arg&: context);
305 // Just apply the patterns greedily.
306 (void)applyPatternsGreedily(op: enclosingOp, patterns: std::move(patterns));
307}
308
309struct LowerToAffineLoops
310 : public impl::ConvertLinalgToAffineLoopsPassBase<LowerToAffineLoops> {
311 using impl::ConvertLinalgToAffineLoopsPassBase<
312 LowerToAffineLoops>::ConvertLinalgToAffineLoopsPassBase;
313 void getDependentDialects(DialectRegistry &registry) const override {
314 registry.insert<memref::MemRefDialect>();
315 }
316 void runOnOperation() override {
317 lowerLinalgToLoopsImpl<affine::AffineForOp>(enclosingOp: getOperation());
318 }
319};
320
321struct LowerToLoops : public impl::ConvertLinalgToLoopsPassBase<LowerToLoops> {
322 using impl::ConvertLinalgToLoopsPassBase<
323 LowerToLoops>::ConvertLinalgToLoopsPassBase;
324 void getDependentDialects(DialectRegistry &registry) const override {
325 registry.insert<memref::MemRefDialect, scf::SCFDialect>();
326 }
327 void runOnOperation() override {
328 lowerLinalgToLoopsImpl<scf::ForOp>(enclosingOp: getOperation());
329 }
330};
331
332struct LowerToParallelLoops
333 : public impl::ConvertLinalgToParallelLoopsPassBase<LowerToParallelLoops> {
334 using impl::ConvertLinalgToParallelLoopsPassBase<
335 LowerToParallelLoops>::ConvertLinalgToParallelLoopsPassBase;
336 void runOnOperation() override {
337 lowerLinalgToLoopsImpl<scf::ParallelOp>(enclosingOp: getOperation());
338 }
339};
340
341} // namespace
342
343/// Emits a loop nest of `affine.for` with the proper body for `linalgOp`.
344FailureOr<LinalgLoops>
345mlir::linalg::linalgOpToAffineLoops(RewriterBase &rewriter, LinalgOp linalgOp) {
346 return linalgOpToLoopsImpl<affine::AffineForOp>(rewriter, linalgOp);
347}
348
349/// Emits a loop nest of `scf.for` with the proper body for `linalgOp`.
350FailureOr<LinalgLoops> mlir::linalg::linalgOpToLoops(RewriterBase &rewriter,
351 LinalgOp linalgOp) {
352 return linalgOpToLoopsImpl<scf::ForOp>(rewriter, linalgOp);
353}
354
355/// Emits a loop nest of `scf.parallel` with the proper body for `linalgOp`.
356FailureOr<LinalgLoops>
357mlir::linalg::linalgOpToParallelLoops(RewriterBase &rewriter,
358 LinalgOp linalgOp) {
359 return linalgOpToLoopsImpl<scf::ParallelOp>(rewriter, linalgOp);
360}
361