1//===- ConvertConv2DToImg2Col.cpp - im2col implementation -----------------===//
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/Affine/Utils.h"
10#include "mlir/Dialect/Arith/IR/Arith.h"
11#include "mlir/Dialect/Complex/IR/Complex.h"
12#include "mlir/Dialect/Linalg/IR/Linalg.h"
13#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
14#include "mlir/Dialect/Tensor/IR/Tensor.h"
15#include "mlir/Dialect/Utils/IndexingUtils.h"
16#include "mlir/Dialect/Utils/ReshapeOpsUtils.h"
17#include "mlir/Dialect/Utils/StructuredOpsUtils.h"
18#include "mlir/IR/AffineExpr.h"
19#include "mlir/IR/AffineMap.h"
20#include "mlir/IR/Builders.h"
21#include "mlir/IR/BuiltinAttributes.h"
22#include "mlir/IR/BuiltinTypes.h"
23#include "llvm/ADT/SmallVectorExtras.h"
24#include <cassert>
25#include <utility>
26
27namespace mlir {
28namespace linalg {
29static bool hasAllOneValues(DenseIntElementsAttr attr) {
30 return llvm::all_of(
31 Range&: attr, P: [](const APInt &element) { return element.getSExtValue() == 1; });
32}
33
34static Value createAdd(Location loc, Value x, Value y, OpBuilder &builder) {
35 if (isa<IntegerType>(Val: x.getType()))
36 return arith::AddIOp::create(builder, location: loc, lhs: x, rhs: y);
37 if (isa<ComplexType>(Val: x.getType()))
38 return complex::AddOp::create(builder, location: loc, lhs: x, rhs: y);
39 return arith::AddFOp::create(builder, location: loc, lhs: x, rhs: y);
40}
41
42static Value createMul(Location loc, Value x, Value y, Type accType,
43 OpBuilder &builder) {
44 // Linalg named ops specify signed extend for named ops.
45 Value xConvert =
46 convertScalarToDtype(b&: builder, loc, operand: x, toType: accType, /*isUnsignedCast=*/false);
47 Value yConvert =
48 convertScalarToDtype(b&: builder, loc, operand: y, toType: accType, /*isUnsignedCast=*/false);
49 if (isa<ComplexType>(Val: accType))
50 return complex::MulOp::create(builder, location: loc, lhs: xConvert, rhs: yConvert);
51 if (isa<IntegerType>(Val: accType))
52 return arith::MulIOp::create(builder, location: loc, lhs: xConvert, rhs: yConvert);
53 return arith::MulFOp::create(builder, location: loc, lhs: xConvert, rhs: yConvert);
54}
55
56// Generate the affine expression to compute the convolved index
57// for the input as `oIndex * stride + fIndex * dilation`,
58// where oIndex: output iterator; fIndex: filter iterator.
59static AffineExpr getConvolvedExpr(OpBuilder &b, int64_t stride,
60 int64_t dilation, bool useSymbols = true) {
61 AffineExpr oExpr, fExpr;
62 if (useSymbols)
63 bindSymbols(ctx: b.getContext(), exprs&: oExpr, exprs&: fExpr);
64 else
65 bindDims(ctx: b.getContext(), exprs&: oExpr, exprs&: fExpr);
66 return AffineExpr(stride * oExpr + dilation * fExpr);
67}
68
69// Stores the affine expressions to map the iteration space of the im2col matrix
70// to the corresponding indices of the output and filter matrices
71struct Im2ColToOperandsExprs {
72 AffineExpr fhIndex;
73 AffineExpr fwIndex;
74 AffineExpr icIndex;
75 AffineExpr ohIndex;
76 AffineExpr owIndex;
77};
78
79// Stores the affine expressions to map the iteration space of the im2col matrix
80// to the input matrix indices
81struct Im2ColToInputDimsExprs {
82 AffineExpr bIndex;
83 AffineExpr hIndex;
84 AffineExpr wIndex;
85 AffineExpr cIndex;
86};
87
88/// Construct the affine expressions that map the indices of the im2col matrix
89/// to the corresponding input tensor indices for a 2D convolution with the the
90/// provided strides.
91///
92/// @param exprs Affine expressions for output and filter indices.
93/// @param strides [height, width] stride values for the convolution.
94/// @param dilations [height, width] dilation values for the convolution.
95/// @param rewriter Pattern rewriter.
96/// @return Affine expressions mapping im2col matrix indices to input
97/// offsets.
98static Im2ColToInputDimsExprs
99getIm2ColInputExpressions(Im2ColToOperandsExprs exprs,
100 ArrayRef<int64_t> strides,
101 ArrayRef<int64_t> dilations, RewriterBase &rewriter) {
102 // maps the iteration space of the im2col matrix to (output_y, filter_y)
103 auto hIndicesMap = AffineMap::inferFromExprList(
104 exprsList: {ArrayRef{exprs.ohIndex, exprs.fhIndex}}, context: rewriter.getContext())[0];
105 // maps the iteration space of the im2col matrix to (output_x, filter_x)
106 auto wIndicesMap = AffineMap::inferFromExprList(
107 exprsList: {ArrayRef{exprs.owIndex, exprs.fwIndex}}, context: rewriter.getContext())[0];
108 // Compute the input indexing map, to map the indices of the im2col matrix to
109 // the original input offsets. Each element of the im2col matrix corresponds
110 // to a pair of (out_element, filter_element). First, we build the expressions
111 // to compute the input (ix, iy) indices from [out_x/y, filter_x/y] pairs;
112 // then we compose them with the maps that map the im2col matrix elements to
113 // the (out_element, filter_element) pairs.
114 auto bIndexExpr = rewriter.getAffineDimExpr(position: 0U);
115 auto hIndexExpr = getConvolvedExpr(b&: rewriter, stride: strides[0], dilation: dilations[0],
116 /*useSymbols*/ false);
117 hIndexExpr = hIndexExpr.compose(map: hIndicesMap);
118 auto wIndexExpr = getConvolvedExpr(b&: rewriter, stride: strides[1], dilation: dilations[1],
119 /*useSymbols*/ false);
120 wIndexExpr = wIndexExpr.compose(map: wIndicesMap);
121 auto cIndexExpr = exprs.icIndex;
122 return {.bIndex: bIndexExpr, .hIndex: hIndexExpr, .wIndex: wIndexExpr, .cIndex: cIndexExpr};
123}
124
125FailureOr<std::pair<Operation *, Operation *>>
126rewriteInIm2Col(RewriterBase &rewriter, linalg::Conv2DNhwcHwcfOp convOp) {
127 auto inputType = cast<ShapedType>(Val: convOp.getInputs()[0].getType());
128 auto filterType = cast<ShapedType>(Val: convOp.getInputs()[1].getType());
129 auto outputType = cast<ShapedType>(Val: convOp.getOutputs()[0].getType());
130
131 if (!convOp.hasPureTensorSemantics())
132 return rewriter.notifyMatchFailure(
133 arg&: convOp, msg: "expected op to have pure tensor semantics");
134
135 if (!filterType.hasStaticShape())
136 return rewriter.notifyMatchFailure(
137 arg&: convOp, msg: "expected a static shape for the filter");
138
139 if (!inputType.hasStaticShape())
140 return rewriter.notifyMatchFailure(arg&: convOp,
141 msg: "expected a static shape for the input");
142
143 MLIRContext *context = rewriter.getContext();
144 Value input = convOp.getInputs()[0];
145 Value filter = convOp.getInputs()[1];
146 Value output = convOp.getOutputs()[0];
147
148 ArrayRef<int64_t> filterShape = filterType.getShape();
149 ArrayRef<int64_t> outputShape = outputType.getShape();
150
151 int64_t n = outputShape[0];
152 int64_t oh = outputShape[1];
153 int64_t ow = outputShape[2];
154 int64_t oc = outputShape[3];
155 int64_t fh = filterShape[0];
156 int64_t fw = filterShape[1];
157 int64_t ic = filterShape[2];
158
159 Location loc = convOp.getLoc();
160
161 assert(isa<RankedTensorType>(filterType) &&
162 "expected filter type to be a ranked tensor");
163 auto tensorFilterType = cast<RankedTensorType>(Val&: filterType);
164
165 // Reshape output and filter to the LHS and result of a (B)MNK matmul.
166 SmallVector<ReassociationIndices> filterReassocIndices = {{0, 1, 2}, {3}};
167 auto reshapedFilterType =
168 RankedTensorType::get(shape: {fh * fw * ic, oc}, elementType: filterType.getElementType(),
169 encoding: tensorFilterType.getEncoding());
170 Value reshapedFilter = tensor::CollapseShapeOp::create(
171 builder&: rewriter, location: loc, resultType: reshapedFilterType, src: filter, reassociation: filterReassocIndices);
172
173 SmallVector<ReassociationIndices> outputReassocIndices = {{0}, {1, 2}, {3}};
174 RankedTensorType reshapedOutputType =
175 RankedTensorType::get(shape: {n, oh * ow, oc}, elementType: outputType.getElementType());
176 Value reshapedOutput = tensor::CollapseShapeOp::create(
177 builder&: rewriter, location: loc, resultType: reshapedOutputType, src: output, reassociation: outputReassocIndices);
178
179 SmallVector<int64_t> colTensorShape = {n, oh * ow, fh * fw * ic};
180 Value colTensor = tensor::EmptyOp::create(builder&: rewriter, location: loc, staticShape: colTensorShape,
181 elementType: inputType.getElementType());
182
183 // Convert the input to a (BMK) column tensor.
184 auto nloops = colTensorShape.size();
185
186 auto parallel = utils::IteratorType::parallel;
187 auto reduction = utils::IteratorType::reduction;
188 SmallVector<utils::IteratorType> img2colIterators(nloops, parallel);
189
190 // Given an index of the im2col matrix, retrieve the corresponding indices of
191 // the output and filter matrices
192 auto mIndicesExprs =
193 delinearize(linearIndex: rewriter.getAffineDimExpr(position: 1U), strides: ArrayRef<int64_t>{ow, 1});
194 auto kIndicesExprs = delinearize(linearIndex: rewriter.getAffineDimExpr(position: 2U),
195 strides: ArrayRef<int64_t>{fw * ic, ic, 1});
196 Im2ColToOperandsExprs i2cToOperExprs;
197 i2cToOperExprs.fhIndex = kIndicesExprs[0];
198 i2cToOperExprs.fwIndex = kIndicesExprs[1];
199 i2cToOperExprs.icIndex = kIndicesExprs[2];
200 i2cToOperExprs.ohIndex = mIndicesExprs[0];
201 i2cToOperExprs.owIndex = mIndicesExprs[1];
202
203 // im2col[n, oh*ow, fh*fw*ic] = input[n, sh*oh + dh*fh, sw*ow + dw*fw, ic]
204 Im2ColToInputDimsExprs inExprs = getIm2ColInputExpressions(
205 exprs: i2cToOperExprs, strides: llvm::to_vector(Range: convOp.getStrides().getValues<int64_t>()),
206 dilations: llvm::to_vector(Range: convOp.getDilations().getValues<int64_t>()), rewriter);
207 auto inMap =
208 AffineMap::inferFromExprList(exprsList: {ArrayRef{inExprs.bIndex, inExprs.hIndex,
209 inExprs.wIndex, inExprs.cIndex}},
210 context: rewriter.getContext())[0];
211
212 SmallVector<AffineMap> img2colIndexingMaps = {
213 inMap, AffineMap::getMultiDimIdentityMap(numDims: nloops, context)};
214
215 auto img2ColTensor = linalg::GenericOp::create(
216 builder&: rewriter, location: loc, resultTensorTypes: colTensor.getType(),
217 /*inputs=*/input, /*outputs=*/colTensor, indexingMaps: img2colIndexingMaps,
218 iteratorTypes: img2colIterators,
219 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
220 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: args[0]);
221 });
222
223 // Because the filter does not share the same batch dimension,
224 // the batch dimension is only used in indexing the input and output. Thus
225 // we cannot use existing linalg named ops like linalg.batch_matmul.
226 // i.e. (B x) M x K * K x N = (B x) M x N
227 AffineExpr bDim, mDim, nDim, kDim;
228 bindDims(ctx: context, exprs&: bDim, exprs&: mDim, exprs&: nDim, exprs&: kDim);
229 auto lhsMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {bDim, mDim, kDim}, context);
230 auto rhsMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {kDim, nDim}, context);
231 auto resultMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {bDim, mDim, nDim}, context);
232 SmallVector<utils::IteratorType> genericIterators = {parallel, parallel,
233 parallel, reduction};
234
235 auto genericOp = linalg::GenericOp::create(
236 builder&: rewriter, location: loc, resultTensorTypes: reshapedOutputType,
237 /*inputs=*/ValueRange{img2ColTensor.getResult(i: 0), reshapedFilter},
238 /*outputs=*/ValueRange{reshapedOutput},
239 indexingMaps: ArrayRef<AffineMap>{lhsMap, rhsMap, resultMap}, iteratorTypes: genericIterators,
240 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
241 Value mul =
242 createMul(loc, x: args[0], y: args[1], accType: args[2].getType(), builder&: nestedBuilder);
243 Value add = createAdd(loc, x: mul, y: args[2], builder&: nestedBuilder);
244 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: add);
245 });
246 Value result = genericOp.getResults().front();
247
248 auto reshapedResult = tensor::ExpandShapeOp::create(
249 builder&: rewriter, location: loc, resultType: outputType, src: result, reassociation: outputReassocIndices);
250
251 rewriter.replaceOp(op: convOp, newValues: ArrayRef<Value>{reshapedResult});
252
253 return std::make_pair(x: img2ColTensor.getOperation(),
254 y: reshapedResult.getOperation());
255}
256
257FailureOr<std::pair<Operation *, Operation *>>
258rewriteInIm2Col(RewriterBase &rewriter,
259 linalg::DepthwiseConv2DNhwcHwcOp convOp) {
260 auto inputType = cast<RankedTensorType>(Val: convOp.getInputs()[0].getType());
261 auto filterType = cast<RankedTensorType>(Val: convOp.getInputs()[1].getType());
262 auto outputType = cast<RankedTensorType>(Val: convOp.getOutputs()[0].getType());
263
264 if (!convOp.hasPureTensorSemantics())
265 return rewriter.notifyMatchFailure(
266 arg&: convOp, msg: "expected op to have pure tensor semantics");
267
268 if (!filterType.hasStaticShape())
269 return rewriter.notifyMatchFailure(
270 arg&: convOp, msg: "expected a static shape for the filter");
271
272 if (!inputType.hasStaticShape())
273 return rewriter.notifyMatchFailure(arg&: convOp,
274 msg: "expected a static shape for the input");
275
276 // TODO: Support dilation.
277 if (!hasAllOneValues(attr: convOp.getDilations()))
278 return rewriter.notifyMatchFailure(arg&: convOp,
279 msg: "expected all ones for dilations");
280
281 Location loc = convOp.getLoc();
282
283 auto transposeOperand = [&](Value operand, ArrayRef<int64_t> indices) {
284 auto operandTensorType = cast<RankedTensorType>(Val: operand.getType());
285 auto nloops = indices.size();
286 ArrayRef<int64_t> inputShape = operandTensorType.getShape();
287
288 SmallVector<AffineExpr> exprs =
289 llvm::map_to_vector<4>(C&: indices, F: [&](int64_t index) -> AffineExpr {
290 return rewriter.getAffineDimExpr(position: index);
291 });
292
293 SmallVector<int64_t> targetShape = llvm::map_to_vector<4>(
294 C&: indices, F: [&](int64_t index) -> int64_t { return inputShape[index]; });
295
296 Value outputTensor = tensor::EmptyOp::create(
297 builder&: rewriter, location: loc, staticShape: targetShape, elementType: operandTensorType.getElementType());
298
299 SmallVector<utils::IteratorType> loopAttributeTypes(
300 nloops, utils::IteratorType::parallel);
301
302 SmallVector<AffineMap> indexingMaps = {
303 inversePermutation(
304 map: AffineMap::get(dimCount: nloops, symbolCount: 0, results: exprs, context: rewriter.getContext())),
305 AffineMap::getMultiDimIdentityMap(numDims: nloops, context: rewriter.getContext())};
306
307 auto transposedOp = linalg::GenericOp::create(
308 builder&: rewriter, location: loc, resultTensorTypes: outputTensor.getType(),
309 /*inputs=*/operand, /*outputs=*/outputTensor, indexingMaps,
310 iteratorTypes: loopAttributeTypes,
311 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
312 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: args[0]);
313 });
314
315 return transposedOp.getResult(i: 0);
316 };
317
318 Value input = convOp.getInputs()[0];
319 Value filter = convOp.getInputs()[1];
320 Value output = convOp.getOutputs()[0];
321
322 // Transpose input, filter so channels are outermost
323 Value inputT = transposeOperand(input, {0, 3, 1, 2});
324 Value filterT = transposeOperand(filter, {2, 0, 1});
325 ArrayRef<int64_t> filterTShape =
326 cast<RankedTensorType>(Val: filterT.getType()).getShape();
327 ArrayRef<int64_t> outputShape = outputType.getShape();
328
329 int n = outputShape[0];
330 int oh = outputShape[1];
331 int ow = outputShape[2];
332 int c = outputShape[3];
333 int fh = filterTShape[1];
334 int fw = filterTShape[2];
335
336 SmallVector<int64_t> colTensorShape = {n, c, oh, ow, fh, fw};
337 Value transposedOutputTensor = transposeOperand(output, {0, 3, 1, 2});
338
339 AffineExpr nDim, cDim, ohDim, owDim, khDim, kwDim;
340 bindDims(ctx: rewriter.getContext(), exprs&: nDim, exprs&: cDim, exprs&: ohDim, exprs&: owDim, exprs&: khDim, exprs&: kwDim);
341
342 AffineExpr shSym = rewriter.getAffineConstantExpr(
343 constant: convOp.getStrides().getValues<int64_t>()[0]);
344 AffineExpr swSym = rewriter.getAffineConstantExpr(
345 constant: convOp.getStrides().getValues<int64_t>()[1]);
346
347 SmallVector<AffineExpr> inputExprs = {nDim, cDim, ohDim * shSym + khDim,
348 owDim * swSym + kwDim};
349
350 auto nloops = colTensorShape.size();
351
352 SmallVector<utils::IteratorType> loopAttributeTypes(
353 nloops, utils::IteratorType::parallel);
354
355 SmallVector<AffineMap> indexingMaps = {
356 AffineMap::get(dimCount: nloops, symbolCount: 0, results: inputExprs, context: rewriter.getContext()),
357 AffineMap::getMultiDimIdentityMap(numDims: nloops, context: rewriter.getContext())};
358
359 Value colTensor = tensor::EmptyOp::create(builder&: rewriter, location: loc, staticShape: colTensorShape,
360 elementType: inputType.getElementType());
361
362 auto img2ColTensor = linalg::GenericOp::create(
363 builder&: rewriter, location: loc, resultTensorTypes: colTensor.getType(),
364 /*inputs=*/inputT, /*outputs=*/colTensor, indexingMaps,
365 iteratorTypes: loopAttributeTypes,
366 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
367 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: args[0]);
368 });
369
370 SmallVector<ReassociationIndices> img2ColTensorReassocIndices = {
371 {0, 1}, {2, 3}, {4, 5}};
372 SmallVector<ReassociationIndices> filterReassociationIndice = {{0}, {1, 2}};
373 SmallVector<ReassociationIndices> outputReassociationIndice = {{0, 1},
374 {2, 3}};
375
376 auto reshapedImg2ColTensorType = RankedTensorType::get(
377 shape: {n * c, oh * ow, fh * fw}, elementType: inputType.getElementType());
378 auto reshapedFilterTensorType =
379 RankedTensorType::get(shape: {c, fh * fw}, elementType: filterType.getElementType());
380 auto reshapedOutputTensorType =
381 RankedTensorType::get(shape: {n * c, oh * ow}, elementType: outputType.getElementType());
382
383 Value reshapedImg2ColTensor = tensor::CollapseShapeOp::create(
384 builder&: rewriter, location: loc, resultType: reshapedImg2ColTensorType, src: img2ColTensor.getResult(i: 0),
385 reassociation: img2ColTensorReassocIndices);
386 Value reshapedFilterTensor =
387 tensor::CollapseShapeOp::create(builder&: rewriter, location: loc, resultType: reshapedFilterTensorType,
388 src: filterT, reassociation: filterReassociationIndice);
389 Value reshapedoutputTensor = tensor::CollapseShapeOp::create(
390 builder&: rewriter, location: loc, resultType: reshapedOutputTensorType, src: transposedOutputTensor,
391 reassociation: outputReassociationIndice);
392
393 auto batchMatVecResult = linalg::BatchMatvecOp::create(
394 builder&: rewriter, location: loc, resultTensorTypes: TypeRange{reshapedoutputTensor.getType()},
395 inputs: ValueRange{reshapedImg2ColTensor, reshapedFilterTensor},
396 outputs: ValueRange{reshapedoutputTensor});
397
398 SmallVector<ReassociationIndices> batchMatVecReassociationIndice = {{0, 1},
399 {2, 3}};
400
401 auto batchMatVecResultReshaped = tensor::ExpandShapeOp::create(
402 builder&: rewriter, location: loc, resultType: transposedOutputTensor.getType(),
403 src: batchMatVecResult.getResult(i: 0), reassociation: batchMatVecReassociationIndice);
404
405 Value transposedResult =
406 transposeOperand(batchMatVecResultReshaped, {0, 2, 3, 1});
407
408 rewriter.replaceOp(op: convOp, newValues: ArrayRef<Value>{transposedResult});
409 return std::make_pair(x: img2ColTensor.getOperation(),
410 y: transposedResult.getDefiningOp());
411}
412
413FailureOr<std::pair<Operation *, Operation *>>
414rewriteInIm2Col(RewriterBase &rewriter, linalg::Conv2DNchwFchwOp convOp) {
415 auto inputType = cast<ShapedType>(Val: convOp.getInputs()[0].getType());
416 auto filterType = cast<ShapedType>(Val: convOp.getInputs()[1].getType());
417 auto outputType = cast<ShapedType>(Val: convOp.getOutputs()[0].getType());
418
419 if (!convOp.hasPureTensorSemantics())
420 return rewriter.notifyMatchFailure(
421 arg&: convOp, msg: "expected op to have pure tensor semantics");
422
423 if (!filterType.hasStaticShape())
424 return rewriter.notifyMatchFailure(
425 arg&: convOp, msg: "expected a static shape for the filter");
426
427 if (!inputType.hasStaticShape())
428 return rewriter.notifyMatchFailure(arg&: convOp,
429 msg: "expected a static shape for the input");
430
431 Value input = convOp.getInputs()[0];
432 Value filter = convOp.getInputs()[1];
433 Value output = convOp.getOutputs()[0];
434
435 auto filterShape = filterType.getShape();
436 auto outputShape = outputType.getShape();
437
438 int64_t n = outputShape[0];
439 int64_t oc = outputShape[1];
440 int64_t oh = outputShape[2];
441 int64_t ow = outputShape[3];
442 int64_t ic = filterShape[1];
443 int64_t fh = filterShape[2];
444 int64_t fw = filterShape[3];
445
446 auto loc = convOp.getLoc();
447 MLIRContext *context = rewriter.getContext();
448
449 assert(isa<RankedTensorType>(filterType) &&
450 "expected filter type to be a ranked tensor");
451 auto tensorFilterType = cast<RankedTensorType>(Val&: filterType);
452
453 SmallVector<ReassociationIndices> filterReassocIndices = {{0}, {1, 2, 3}};
454 auto reshapedFilterType =
455 RankedTensorType::get(shape: {oc, ic * fh * fw}, elementType: inputType.getElementType(),
456 encoding: tensorFilterType.getEncoding());
457 Value reshapedFilter = tensor::CollapseShapeOp::create(
458 builder&: rewriter, location: loc, resultType: reshapedFilterType, src: filter, reassociation: filterReassocIndices);
459
460 SmallVector<ReassociationIndices> outputReassocIndices = {{0}, {1}, {2, 3}};
461 auto reshapedOutputType =
462 RankedTensorType::get(shape: {n, oc, oh * ow}, elementType: outputType.getElementType());
463 Value reshapedOutput = tensor::CollapseShapeOp::create(
464 builder&: rewriter, location: loc, resultType: reshapedOutputType, src: output, reassociation: outputReassocIndices);
465
466 // Convert the input to a (BKN) tensor.
467 SmallVector<int64_t, 4> colTensorShape = {n, ic * fh * fw, oh * ow};
468 Value colTensor = tensor::EmptyOp::create(builder&: rewriter, location: loc, staticShape: colTensorShape,
469 elementType: inputType.getElementType());
470
471 auto nloops = colTensorShape.size();
472
473 auto parallel = utils::IteratorType::parallel;
474 auto reduction = utils::IteratorType::reduction;
475 SmallVector<utils::IteratorType, 3> img2colIterators(nloops, parallel);
476
477 // Recover the original iteration indices from the problem/input sizes:
478 // given an index of the im2col matrix, retrieve the corresponding indices of
479 // the output and filter matrices
480 auto kIndicesExprs = delinearize(linearIndex: rewriter.getAffineDimExpr(position: 1U),
481 strides: ArrayRef<int64_t>{fh * fw, fw, 1});
482 auto mIndicesExprs =
483 delinearize(linearIndex: rewriter.getAffineDimExpr(position: 2U), strides: ArrayRef<int64_t>{ow, 1});
484 Im2ColToOperandsExprs i2cToOperExprs;
485 i2cToOperExprs.icIndex = kIndicesExprs[0];
486 i2cToOperExprs.fhIndex = kIndicesExprs[1];
487 i2cToOperExprs.fwIndex = kIndicesExprs[2];
488 i2cToOperExprs.ohIndex = mIndicesExprs[0];
489 i2cToOperExprs.owIndex = mIndicesExprs[1];
490 Im2ColToInputDimsExprs inExprs = getIm2ColInputExpressions(
491 exprs: i2cToOperExprs, strides: llvm::to_vector(Range: convOp.getStrides().getValues<int64_t>()),
492 dilations: llvm::to_vector(Range: convOp.getDilations().getValues<int64_t>()), rewriter);
493 auto inMap =
494 AffineMap::inferFromExprList(exprsList: {ArrayRef{inExprs.bIndex, inExprs.cIndex,
495 inExprs.hIndex, inExprs.wIndex}},
496 context: rewriter.getContext())[0];
497 // im2col[n, ic*fh*fw, oh*ow] = input[n, ic, sh*oh + dh*fh, sw*ow + dw*fw]
498 SmallVector<AffineMap> img2colIndexingMaps = {
499 inMap, AffineMap::getMultiDimIdentityMap(numDims: nloops, context)};
500
501 auto img2ColTensor = linalg::GenericOp::create(
502 builder&: rewriter, location: loc, resultTensorTypes: colTensor.getType(),
503 /*inputs=*/input, /*outputs=*/colTensor, indexingMaps: img2colIndexingMaps,
504 iteratorTypes: img2colIterators,
505 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
506 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: args[0]);
507 });
508
509 // Because the filter does not share the same batch dimension,
510 // the batch dimension is only used in indexing the input and output. Thus
511 // we cannot use existing linalg named ops like linalg.batch_matmul.
512 // i.e. M x K * (B x) K x N = (B x) M x N
513 AffineExpr bDim, mDim, nDim, kDim;
514 bindDims(ctx: context, exprs&: bDim, exprs&: mDim, exprs&: nDim, exprs&: kDim);
515 auto lhsMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {mDim, kDim}, context);
516 auto rhsMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {bDim, kDim, nDim}, context);
517 auto resultMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {bDim, mDim, nDim}, context);
518 SmallVector<utils::IteratorType> genericIterators = {parallel, parallel,
519 parallel, reduction};
520 auto genericOp = linalg::GenericOp::create(
521 builder&: rewriter, location: loc, resultTensorTypes: reshapedOutputType,
522 /*inputs=*/ValueRange{reshapedFilter, img2ColTensor.getResult(i: 0)},
523 /*outputs=*/ValueRange{reshapedOutput},
524 indexingMaps: ArrayRef<AffineMap>{lhsMap, rhsMap, resultMap}, iteratorTypes: genericIterators,
525 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
526 Value mul =
527 createMul(loc, x: args[0], y: args[1], accType: args[2].getType(), builder&: nestedBuilder);
528 Value add = createAdd(loc, x: mul, y: args[2], builder&: nestedBuilder);
529 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: add);
530 });
531 Value result = genericOp.getResults().front();
532
533 auto reshapedResult = tensor::ExpandShapeOp::create(
534 builder&: rewriter, location: loc, resultType: outputType, src: result, reassociation: outputReassocIndices);
535
536 rewriter.replaceOp(op: convOp, newValues: ArrayRef<Value>{reshapedResult});
537
538 return std::make_pair(x: img2ColTensor.getOperation(),
539 y: reshapedResult.getOperation());
540}
541
542FailureOr<std::pair<Operation *, Operation *>>
543rewriteInIm2Col(RewriterBase &rewriter, linalg::Conv2DNhwcFhwcOp convOp) {
544 auto inputType = cast<ShapedType>(Val: convOp.getInputs()[0].getType());
545 auto filterType = cast<ShapedType>(Val: convOp.getInputs()[1].getType());
546 auto outputType = cast<ShapedType>(Val: convOp.getOutputs()[0].getType());
547
548 if (!convOp.hasPureTensorSemantics())
549 return rewriter.notifyMatchFailure(
550 arg&: convOp, msg: "expected op to have pure tensor semantics");
551
552 if (!filterType.hasStaticShape())
553 return rewriter.notifyMatchFailure(
554 arg&: convOp, msg: "expected a static shape for the filter");
555
556 if (!inputType.hasStaticShape())
557 return rewriter.notifyMatchFailure(arg&: convOp,
558 msg: "expected a static shape for the input");
559
560 MLIRContext *context = rewriter.getContext();
561 Value input = convOp.getInputs()[0];
562 Value filter = convOp.getInputs()[1];
563 Value output = convOp.getOutputs()[0];
564
565 ArrayRef<int64_t> filterShape = filterType.getShape();
566 ArrayRef<int64_t> outputShape = outputType.getShape();
567
568 int64_t n = outputShape[0];
569 int64_t oh = outputShape[1];
570 int64_t ow = outputShape[2];
571 int64_t oc = outputShape[3];
572 int64_t fh = filterShape[1];
573 int64_t fw = filterShape[2];
574 int64_t ic = filterShape[3];
575
576 Location loc = convOp.getLoc();
577
578 assert(isa<RankedTensorType>(filterType) &&
579 "expected filter type to be a ranked tensor");
580 auto tensorFilterType = cast<RankedTensorType>(Val&: filterType);
581
582 // Reshape output and filter to the LHS and result of a "row-wise" matrix
583 // multiplication.
584 SmallVector<ReassociationIndices> filterReassocIndices = {{0}, {1, 2, 3}};
585 auto reshapedFilterType =
586 RankedTensorType::get(shape: {oc, fh * fw * ic}, elementType: filterType.getElementType(),
587 encoding: tensorFilterType.getEncoding());
588 Value reshapedFilter = tensor::CollapseShapeOp::create(
589 builder&: rewriter, location: loc, resultType: reshapedFilterType, src: filter, reassociation: filterReassocIndices);
590
591 SmallVector<ReassociationIndices> outputReassocIndices = {{0}, {1, 2}, {3}};
592 RankedTensorType reshapedOutputType =
593 RankedTensorType::get(shape: {n, oh * ow, oc}, elementType: outputType.getElementType());
594 Value reshapedOutput = tensor::CollapseShapeOp::create(
595 builder&: rewriter, location: loc, resultType: reshapedOutputType, src: output, reassociation: outputReassocIndices);
596
597 // Shape of the Toeplitz matrix produced by Im2col.
598 SmallVector<int64_t> colTensorShape = {n, oh * ow, fh * fw * ic};
599 Value colTensor = tensor::EmptyOp::create(builder&: rewriter, location: loc, staticShape: colTensorShape,
600 elementType: inputType.getElementType());
601
602 // Convert the input to a (BMK) column tensor.
603 auto nloops = colTensorShape.size();
604
605 auto parallel = utils::IteratorType::parallel;
606 auto reduction = utils::IteratorType::reduction;
607 SmallVector<utils::IteratorType> img2colIterators(nloops, parallel);
608
609 // Given an index of the im2col matrix, retrieve the corresponding indices of
610 // the output and filter matrices
611 auto mIndicesExprs =
612 delinearize(linearIndex: rewriter.getAffineDimExpr(position: 1U), strides: ArrayRef<int64_t>{ow, 1});
613 auto kIndicesExprs = delinearize(linearIndex: rewriter.getAffineDimExpr(position: 2U),
614 strides: ArrayRef<int64_t>{fw * ic, ic, 1});
615 Im2ColToOperandsExprs i2cToOperExprs;
616 i2cToOperExprs.fhIndex = kIndicesExprs[0];
617 i2cToOperExprs.fwIndex = kIndicesExprs[1];
618 i2cToOperExprs.icIndex = kIndicesExprs[2];
619 i2cToOperExprs.ohIndex = mIndicesExprs[0];
620 i2cToOperExprs.owIndex = mIndicesExprs[1];
621
622 // im2col[n, oh*ow, fh*fw*ic] = input[n, sh*oh + dh*fh, sw*ow + dw*fw, ic]
623 Im2ColToInputDimsExprs inExprs = getIm2ColInputExpressions(
624 exprs: i2cToOperExprs, strides: llvm::to_vector(Range: convOp.getStrides().getValues<int64_t>()),
625 dilations: llvm::to_vector(Range: convOp.getDilations().getValues<int64_t>()), rewriter);
626 auto inMap =
627 AffineMap::inferFromExprList(exprsList: {ArrayRef{inExprs.bIndex, inExprs.hIndex,
628 inExprs.wIndex, inExprs.cIndex}},
629 context: rewriter.getContext())[0];
630 SmallVector<AffineMap> img2colIndexingMaps = {
631 inMap, AffineMap::getMultiDimIdentityMap(numDims: nloops, context)};
632
633 auto img2ColTensor = linalg::GenericOp::create(
634 builder&: rewriter, location: loc, resultTensorTypes: colTensor.getType(),
635 /*inputs=*/input, /*outputs=*/colTensor, indexingMaps: img2colIndexingMaps,
636 iteratorTypes: img2colIterators,
637 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
638 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: args[0]);
639 });
640
641 // Because we didn't transpose the filters we don't actually have a batched
642 // matrix multiply. Instead, we have an operation consisting of "row-wise" dot
643 // products.
644 AffineExpr bDim, mDim, nDim, kDim;
645 bindDims(ctx: context, exprs&: bDim, exprs&: mDim, exprs&: nDim, exprs&: kDim);
646 auto lhsMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {bDim, mDim, kDim}, context);
647 auto rhsMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {nDim, kDim}, context);
648 auto resultMap = AffineMap::get(dimCount: 4, symbolCount: 0, results: {bDim, mDim, nDim}, context);
649 SmallVector<utils::IteratorType> genericIterators = {parallel, parallel,
650 parallel, reduction};
651
652 auto genericOp = linalg::GenericOp::create(
653 builder&: rewriter, location: loc, resultTensorTypes: reshapedOutputType,
654 /*inputs=*/ValueRange{img2ColTensor.getResult(i: 0), reshapedFilter},
655 /*outputs=*/ValueRange{reshapedOutput},
656 indexingMaps: ArrayRef<AffineMap>{lhsMap, rhsMap, resultMap}, iteratorTypes: genericIterators,
657 odsArg5: [&](OpBuilder &nestedBuilder, Location nestedLoc, ValueRange args) {
658 Value mul =
659 createMul(loc, x: args[0], y: args[1], accType: args[2].getType(), builder&: nestedBuilder);
660 Value add = createAdd(loc, x: mul, y: args[2], builder&: nestedBuilder);
661 linalg::YieldOp::create(builder&: nestedBuilder, location: nestedLoc, values: add);
662 });
663 Value result = genericOp.getResults().front();
664
665 auto reshapedResult = tensor::ExpandShapeOp::create(
666 builder&: rewriter, location: loc, resultType: outputType, src: result, reassociation: outputReassocIndices);
667
668 rewriter.replaceOp(op: convOp, newValues: ArrayRef<Value>{reshapedResult});
669
670 return std::make_pair(x: img2ColTensor.getOperation(),
671 y: reshapedResult.getOperation());
672}
673
674namespace {
675
676class ConvertConv2DNhwcHwcf final
677 : public OpRewritePattern<linalg::Conv2DNhwcHwcfOp> {
678public:
679 using Base::Base;
680
681 LogicalResult matchAndRewrite(linalg::Conv2DNhwcHwcfOp convOp,
682 PatternRewriter &rewriter) const override {
683 if (failed(Result: rewriteInIm2Col(rewriter, convOp)))
684 return failure();
685 return success();
686 }
687};
688
689class ConvertDepthwiseConv2DNhwcHwc final
690 : public OpRewritePattern<linalg::DepthwiseConv2DNhwcHwcOp> {
691public:
692 using OpRewritePattern<linalg::DepthwiseConv2DNhwcHwcOp>::OpRewritePattern;
693
694 LogicalResult matchAndRewrite(linalg::DepthwiseConv2DNhwcHwcOp convOp,
695 PatternRewriter &rewriter) const override {
696 if (failed(Result: rewriteInIm2Col(rewriter, convOp)))
697 return failure();
698 return success();
699 }
700};
701
702class ConvertConv2DNchwFchw final
703 : public OpRewritePattern<linalg::Conv2DNchwFchwOp> {
704public:
705 using Base::Base;
706
707 LogicalResult matchAndRewrite(linalg::Conv2DNchwFchwOp convOp,
708 PatternRewriter &rewriter) const override {
709 if (failed(Result: rewriteInIm2Col(rewriter, convOp)))
710 return failure();
711 return success();
712 }
713};
714
715class ConvertConv2DNhwcFhwc final
716 : public OpRewritePattern<linalg::Conv2DNhwcFhwcOp> {
717public:
718 using Base::Base;
719
720 LogicalResult matchAndRewrite(linalg::Conv2DNhwcFhwcOp convOp,
721 PatternRewriter &rewriter) const override {
722 if (failed(Result: rewriteInIm2Col(rewriter, convOp)))
723 return failure();
724 return success();
725 }
726};
727} // end anonymous namespace
728
729void populateConvertConv2DToImg2ColPatterns(RewritePatternSet &patterns) {
730 MLIRContext *context = patterns.getContext();
731 patterns.insert<ConvertConv2DNhwcHwcf, ConvertDepthwiseConv2DNhwcHwc,
732 ConvertConv2DNchwFchw, ConvertConv2DNhwcFhwc>(arg&: context);
733}
734} // end namespace linalg
735} // end namespace mlir
736