1//===- Split.cpp - Structured op splitting --------------------------------===//
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/IR/AffineOps.h"
10#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
11#include "mlir/Dialect/Utils/StaticValueUtils.h"
12#include "mlir/IR/AffineExpr.h"
13#include "mlir/IR/Attributes.h"
14#include "mlir/IR/BuiltinAttributes.h"
15#include "mlir/IR/OpDefinition.h"
16#include "mlir/Interfaces/TilingInterface.h"
17#include "llvm/ADT/SmallVectorExtras.h"
18
19#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/SmallVector.h"
21
22using namespace mlir;
23using namespace mlir::linalg;
24
25/// Creates a part of the given `op` split along the iteration space `dimension`
26/// with the given `size` and an optional `offset` (default 0). Makes slices
27/// of operands, using the input operands of the original op and the output
28/// operands provided as `resultOperands`. Expects `offsets` and `sizes` to
29/// define the shape of the iteration space of the original op. Returns the
30/// split-out op as well as the output operand values updated with the partial
31/// results produced by this op through `results`.
32static TilingInterface
33createSplitPart(RewriterBase &b, Location loc, TilingInterface op,
34 ArrayRef<OpFoldResult> offsets, ArrayRef<OpFoldResult> sizes,
35 ValueRange resultOperands, unsigned dimension,
36 OpFoldResult size, OpFoldResult offset,
37 SmallVectorImpl<Value> &results) {
38 // Iteration space of the current part.
39 SmallVector<OpFoldResult> sizesCopy = llvm::to_vector(Range&: sizes);
40 SmallVector<OpFoldResult> offsetsCopy = llvm::to_vector(Range&: offsets);
41 sizesCopy[dimension] = size;
42 offsetsCopy[dimension] = offset;
43
44 // Create the part as if it were a single tile.
45 FailureOr<TilingResult> tilingResult =
46 op.getTiledImplementation(b, offsets: offsetsCopy, sizes: sizesCopy);
47
48 // Insert the results back and populate the `results` list.
49 for (auto [index, result] : llvm::enumerate(First&: tilingResult->tiledValues)) {
50 SmallVector<OpFoldResult> resultOffsets, resultSizes;
51 if (failed(Result: op.getResultTilePosition(b, resultNumber: index, offsets: offsetsCopy, sizes: sizesCopy,
52 resultOffsets, resultSizes)))
53 return nullptr;
54 SmallVector<OpFoldResult> resultStrides(resultOffsets.size(),
55 b.getIndexAttr(value: 1));
56 Value inserted = tensor::InsertSliceOp::create(
57 builder&: b, location: loc, source: result, dest: resultOperands[index], offsets: resultOffsets, sizes: resultSizes,
58 strides: resultStrides);
59 results.push_back(Elt: inserted);
60 }
61 // TODO: this part can be generalized maybe to not expect a single op.
62 assert(tilingResult->tiledOps.size() == 1 &&
63 "expected split part to return a single tiled operation");
64 return cast<TilingInterface>(Val: tilingResult->tiledOps[0]);
65}
66
67std::pair<TilingInterface, TilingInterface>
68linalg::splitOp(RewriterBase &rewriter, TilingInterface op, unsigned dimension,
69 OpFoldResult splitPoint) {
70 // Compute the iteration space.
71 SmallVector<Range> iterationSpace = op.getIterationDomain(b&: rewriter);
72
73 // Bail out on dimension overflow.
74 if (dimension >= iterationSpace.size())
75 return std::make_pair(x&: op, y: TilingInterface());
76
77 SmallVector<OpFoldResult> offsets = llvm::map_to_vector(
78 C&: iterationSpace, F: [](const Range &range) { return range.offset; });
79 SmallVector<OpFoldResult> sizes = llvm::map_to_vector(
80 C&: iterationSpace, F: [](const Range &range) { return range.size; });
81
82 // Adjust the split point so that it doesn't overflow the size.
83 AffineExpr d0, d1, d2;
84 bindDims(ctx: rewriter.getContext(), exprs&: d0, exprs&: d1, exprs&: d2);
85 OpFoldResult minSplitPoint = affine::makeComposedFoldedAffineMin(
86 b&: rewriter, loc: op.getLoc(),
87 map: AffineMap::inferFromExprList(exprsList: ArrayRef<AffineExpr>{d0, d1 + d2},
88 context: rewriter.getContext())
89 .front(),
90 operands: {splitPoint, offsets[dimension], sizes[dimension]});
91
92 // Compute the size of the second part. Return early if the second part would
93 // have an empty iteration space.
94 OpFoldResult remainingSize = affine::makeComposedFoldedAffineApply(
95 b&: rewriter, loc: op.getLoc(), expr: d0 + d1 - d2,
96 operands: {iterationSpace[dimension].offset, iterationSpace[dimension].size,
97 minSplitPoint});
98 if (auto attr = llvm::dyn_cast_if_present<Attribute>(Val&: remainingSize)) {
99 if (cast<IntegerAttr>(Val&: attr).getValue().isZero())
100 return {op, TilingInterface()};
101 }
102
103 // Compute destination tensors.
104 SmallVector<Value> destinationTensors;
105 LogicalResult destStatus = tensor::getOrCreateDestinations(
106 b&: rewriter, loc: op.getLoc(), op, result&: destinationTensors);
107 (void)destStatus;
108 assert(succeeded(destStatus) && "failed to get destination tensors");
109
110 // Create the first part.
111 SmallVector<Value> firstResults;
112 TilingInterface firstPart = createSplitPart(
113 b&: rewriter, loc: op.getLoc(), op, offsets, sizes, resultOperands: destinationTensors, dimension,
114 size: minSplitPoint, offset: iterationSpace[dimension].offset, results&: firstResults);
115
116 // Need to pretend that the original op now takes as operands firstResults,
117 // otherwise tiling interface implementation will take the wrong value to
118 // produce data tiles.
119 rewriter.modifyOpInPlace(root: op, callable: [&]() {
120 unsigned numTotalOperands = op->getNumOperands();
121 unsigned numOutputOperands = firstResults.size();
122 op->setOperands(start: numTotalOperands - numOutputOperands, length: numOutputOperands,
123 operands: firstResults);
124 });
125
126 // Create the second part.
127 OpFoldResult totalOffset = affine::makeComposedFoldedAffineApply(
128 b&: rewriter, loc: op.getLoc(), expr: d0 + d1, operands: {offsets[dimension], minSplitPoint});
129 SmallVector<Value> secondResults;
130 TilingInterface secondPart =
131 createSplitPart(b&: rewriter, loc: op.getLoc(), op, offsets, sizes, resultOperands: firstResults,
132 dimension, size: remainingSize, offset: totalOffset, results&: secondResults);
133
134 // Propagate any errors in part creation.
135 if (!firstPart || !secondPart)
136 return {TilingInterface(), TilingInterface()};
137
138 // Replace the original op with the results of the two newly created ops.
139 rewriter.replaceOp(op, newValues: secondResults);
140 return {firstPart, secondPart};
141}
142