1//===- DataLayoutPropagation.cpp -----------------------------------------===///
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/IR/Linalg.h"
11#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
12#include "mlir/Dialect/Linalg/Utils/Utils.h"
13#include "mlir/Dialect/Tensor/IR/Tensor.h"
14#include "mlir/Dialect/UB/IR/UBOps.h"
15#include "mlir/Dialect/Utils/IndexingUtils.h"
16#include "mlir/IR/Dominance.h"
17#include "mlir/IR/TypeUtilities.h"
18#include "llvm/ADT/SetOperations.h"
19#include "llvm/ADT/SetVector.h"
20#include "llvm/ADT/TypeSwitch.h"
21#include "llvm/Support/Debug.h"
22#include <optional>
23
24namespace mlir {
25#define GEN_PASS_DEF_LINALGDATALAYOUTPROPAGATION
26#include "mlir/Dialect/Linalg/Passes.h.inc"
27} // namespace mlir
28
29using namespace mlir;
30using namespace mlir::linalg;
31
32#define DEBUG_TYPE "linalg-data-layout-propagation"
33
34namespace {
35
36static bool hasGatherSemantics(linalg::GenericOp genericOp) {
37 for (Operation &op : genericOp.getBody()->getOperations())
38 if (isa<tensor::ExtractOp, linalg::IndexOp>(Val: op))
39 return true;
40 return false;
41}
42
43// The struct contains the infomation about mapping packing information to
44// the iteration domain of Linalg ops.
45struct PackInfo {
46 int64_t getNumTiledLoops() const { return tileToPointMapping.size(); };
47 // InnerDimsPos on iteration domain, which follows the order in pack ops.
48 SmallVector<int64_t> tiledDimsPos;
49 // The sizes of tiling data dimensions on iteration domain.
50 llvm::DenseMap<int64_t, OpFoldResult> domainDimAndTileMapping;
51 // The mapping from a dimension of iteration domain to the corresponding inner
52 // tiling dimension on iteration domain.
53 llvm::DenseMap<int64_t, int64_t> tileToPointMapping;
54 // The permutation of outer dims (on domain).
55 SmallVector<int64_t> outerDimsOnDomainPerm;
56};
57
58template <typename OpTy>
59static FailureOr<PackInfo>
60getPackingInfoFromOperand(OpOperand *opOperand, linalg::GenericOp genericOp,
61 OpTy packOrUnPackOp) {
62 static_assert(llvm::is_one_of<OpTy, linalg::PackOp, linalg::UnPackOp>::value,
63 "applies to only pack or unpack operations");
64 LLVM_DEBUG(
65 { llvm::dbgs() << "--- Construct PackInfo From an operand ---\n"; });
66
67 AffineMap indexingMap = genericOp.getMatchingIndexingMap(opOperand);
68 SmallVector<AffineMap> indexingMaps = genericOp.getIndexingMapsArray();
69 SmallVector<utils::IteratorType> iterators =
70 genericOp.getIteratorTypesArray();
71
72 PackInfo packInfo;
73 int64_t origNumDims = indexingMap.getNumDims();
74 SmallVector<AffineExpr> exprs(indexingMap.getResults());
75 ArrayRef<int64_t> innerDimsPos = packOrUnPackOp.getInnerDimsPos();
76 for (auto [index, innerDimPos, tileSize] :
77 llvm::zip_equal(llvm::seq<unsigned>(Begin: 0, End: innerDimsPos.size()),
78 innerDimsPos, packOrUnPackOp.getMixedTiles())) {
79 auto expr = exprs[innerDimPos];
80 if (!isa<AffineDimExpr>(expr))
81 return failure();
82 int64_t domainDimPos =
83 cast<AffineDimExpr>(exprs[innerDimPos]).getPosition();
84 if (!isParallelIterator(iteratorType: iterators[domainDimPos]))
85 return failure();
86 packInfo.tiledDimsPos.push_back(Elt: domainDimPos);
87 packInfo.domainDimAndTileMapping[domainDimPos] = tileSize;
88 packInfo.tileToPointMapping[domainDimPos] = origNumDims + index;
89 LLVM_DEBUG({
90 llvm::dbgs() << "map innerDimPos=" << innerDimPos
91 << " to iteration dimension (d" << domainDimPos << ", d"
92 << packInfo.tileToPointMapping[domainDimPos]
93 << "), which has size=("
94 << packInfo.domainDimAndTileMapping[domainDimPos] << ")\n";
95 });
96 }
97
98 // Bail out if a tiled dimension is present in a map but not as an affine dim
99 // expression.
100 auto areAllAffineDimExpr = [&](int dim) {
101 for (AffineMap map : indexingMaps) {
102 if (llvm::any_of(map.getResults(), [dim](AffineExpr expr) {
103 return expr.isFunctionOfDim(position: dim) && !isa<AffineDimExpr>(Val: expr);
104 })) {
105 return false;
106 }
107 }
108 return true;
109 };
110 for (int64_t i : packInfo.tiledDimsPos)
111 if (!areAllAffineDimExpr(i))
112 return failure();
113
114 // Get the outer dims perm on the iteration domain. Start by identifying the
115 // set of domain dims affected by the outer permutation along with the
116 // permuted ordering for those dims. Then the full outer dims permutation can
117 // be constructed by replacing the affected dims with the permuted result in a
118 // numLoops-rank identity. e.g.
119 // outerDimsPerm = [1, 2, 0]
120 // indexingMap = (d0, d1, d2, d3, d4) -> (d1, d4, d3)
121 //
122 // permutedOuterDims = [4, 3, 1]
123 // outerDimsOnDomainPerm = [0, 4, 2, 3, 1]
124 //
125 // Non-affine dim expressions must not be permuted by the outer dims
126 // permutation.
127 SmallVector<int64_t> permutedOuterDims;
128 for (auto [index, dim] : llvm::enumerate(packOrUnPackOp.getOuterDimsPerm())) {
129 auto permutedExpr = indexingMap.getResult(idx: dim);
130 if (auto dimExpr = dyn_cast<AffineDimExpr>(permutedExpr)) {
131 permutedOuterDims.push_back(Elt: dimExpr.getPosition());
132 continue;
133 }
134
135 // TODO: Allow propagation with transposes on non affine dim expressions,
136 // e.g. d0 + d1 which implies transposing both dims simultaneously while
137 // maintaining the relative position between them.
138 if (static_cast<int64_t>(index) != dim)
139 return failure();
140 }
141 if (!permutedOuterDims.empty()) {
142 int64_t outerDimIndex = 0;
143 llvm::DenseSet<int64_t> permutedDomainDims(permutedOuterDims.begin(),
144 permutedOuterDims.end());
145 for (int i = 0, e = indexingMap.getNumDims(); i < e; i++)
146 packInfo.outerDimsOnDomainPerm.push_back(
147 Elt: permutedDomainDims.contains(V: i) ? permutedOuterDims[outerDimIndex++]
148 : i);
149 LLVM_DEBUG({
150 llvm::dbgs() << "map outer dimsDimsPerm to ";
151 for (auto dim : packInfo.outerDimsOnDomainPerm)
152 llvm::dbgs() << dim << " ";
153 llvm::dbgs() << "\n";
154 });
155 }
156
157 return packInfo;
158}
159
160static SmallVector<int64_t> computeOuterDims(ArrayRef<int64_t> perm,
161 ArrayRef<AffineExpr> exprs) {
162 // Compute `outer_dims_perm`. See example:
163 // current exprs : (d0, d1, d2, d3) -> (d2, d3)
164 // perm : [0, 3, 1, 2]
165 // First map d2, d3 with their position in the array as:
166 // currentPositionTileLoops: dim | pos
167 // d2 | 0
168 // d3 | 1
169 // then scan `perm` in order and get the `outer_dims_perm`
170 // to be used, here it would be [1, 0].
171 assert(!perm.empty() && "expect perm not to be empty");
172 assert(!exprs.empty() && "expect exprs not to be empty");
173 if (exprs.size() == 1)
174 return {};
175 SmallVector<int64_t> outerDimsPerm;
176 DenseMap<int64_t, int64_t> currentPositionTileLoops;
177 for (auto [pos, expr] : llvm::enumerate(First&: exprs)) {
178 // Here we rely on the assumption that the outer dims permutation
179 // when propagating currently requires that non-affine dim expressions
180 // are not permuted, thus allowing the identity assignment below.
181 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val: expr))
182 currentPositionTileLoops[dimExpr.getPosition()] = pos;
183 else
184 currentPositionTileLoops[pos] = pos;
185 }
186 for (int64_t loopIdx : perm) {
187 if (currentPositionTileLoops.count(Val: loopIdx))
188 outerDimsPerm.push_back(Elt: currentPositionTileLoops.lookup(Val: loopIdx));
189 }
190 return outerDimsPerm;
191}
192
193struct PackedOperandDetails {
194 SmallVector<OpFoldResult> innerTileSizes;
195 SmallVector<int64_t> innerDimsPos;
196 SmallVector<int64_t> outerDimsPerm;
197 AffineMap indexingMap;
198};
199
200/// Helper function for getOrCreatePackedViewOfOperand that populates
201/// the details of the packedOperand that needs to be formed and also
202/// returns if the packing would require padding.
203static bool getPackedOperandDetails(
204 OpBuilder &b, PackInfo packInfo, GenericOp genericOp, OpOperand *opOperand,
205 DenseMap<OpOperand *, PackedOperandDetails> &packedOperandMap) {
206 PackedOperandDetails currOperandDetails;
207 int64_t numOrigLoops = genericOp.getNumLoops();
208 int64_t numInnerLoops = packInfo.getNumTiledLoops();
209 int64_t numLoops = numOrigLoops + numInnerLoops;
210 AffineMap origIndexingMap = genericOp.getMatchingIndexingMap(opOperand);
211 llvm::DenseMap<int64_t, int64_t> domainDimToOperandDim;
212 SmallVector<AffineExpr> exprs(origIndexingMap.getResults());
213
214 // If the OpOperand is a scalar or a zero-rank tensor, no need to pack.
215 if (genericOp.isScalar(opOperand) || exprs.empty()) {
216 currOperandDetails.indexingMap =
217 AffineMap::get(dimCount: numLoops, symbolCount: 0, results: exprs, context: b.getContext());
218 packedOperandMap[opOperand] = currOperandDetails;
219 return false;
220 }
221
222 // Step 1. Construct the information of packing data dimensions; append inner
223 // dimensions to the indexing maps for the operand.
224 for (auto [index, expr] : llvm::enumerate(First&: exprs)) {
225 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
226 int64_t dimPos = dimExpr.getPosition();
227 domainDimToOperandDim[dimPos] = index;
228 continue;
229 }
230 }
231 SmallVector<int64_t> innerDimsPos;
232 SmallVector<OpFoldResult> innerTileSizes;
233 for (auto dimPos : packInfo.tiledDimsPos) {
234 if (!domainDimToOperandDim.count(Val: dimPos))
235 continue;
236 int64_t index = domainDimToOperandDim[dimPos];
237 innerTileSizes.push_back(Elt: packInfo.domainDimAndTileMapping[dimPos]);
238 innerDimsPos.push_back(Elt: index);
239 exprs.push_back(Elt: b.getAffineDimExpr(position: packInfo.tileToPointMapping[dimPos]));
240 }
241
242 // Step 2. Handle outer dim permutations.
243 SmallVector<int64_t> outerDimsPerm;
244 if (!packInfo.outerDimsOnDomainPerm.empty()) {
245 outerDimsPerm = computeOuterDims(perm: packInfo.outerDimsOnDomainPerm, exprs);
246
247 // Step 2.1: Fold transpose into the linalg.generic.
248 SmallVector<int64_t> inversedOuterPerm =
249 invertPermutationVector(permutation: packInfo.outerDimsOnDomainPerm);
250 for (auto i : llvm::seq<unsigned>(Begin: 0, End: origIndexingMap.getNumResults())) {
251 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: exprs[i])) {
252 int64_t dimPos = dimExpr.getPosition();
253 exprs[i] = b.getAffineDimExpr(position: inversedOuterPerm[dimPos]);
254 continue;
255 }
256 assert(isa<AffineConstantExpr>(exprs[i]) &&
257 "Attempted to permute non-constant and non-affine dim expression");
258 }
259 // Step 2.2: Undo the transposition on `exprs` and propagate the
260 // transposition on the pack using outerDimsPerm.
261 if (!outerDimsPerm.empty()) {
262 SmallVector<AffineExpr> auxVec = exprs;
263 for (const auto &en : enumerate(First&: outerDimsPerm))
264 auxVec[en.index()] = exprs[en.value()];
265 exprs = auxVec;
266 }
267 }
268 currOperandDetails.indexingMap =
269 AffineMap::get(dimCount: numLoops, symbolCount: 0, results: exprs, context: b.getContext());
270
271 // The operand does not have dimensions that relates to pack op.
272 if (innerDimsPos.empty() && outerDimsPerm.empty()) {
273 packedOperandMap[opOperand] = currOperandDetails;
274 return false;
275 }
276 auto inputType = cast<RankedTensorType>(Val: opOperand->get().getType());
277
278 auto maybeIntInnerTileSizes =
279 llvm::map_to_vector(C&: innerTileSizes, F: [](OpFoldResult ofr) -> int64_t {
280 std::optional<int64_t> maybeCst = getConstantIntValue(ofr);
281 return maybeCst.value_or(u: ShapedType::kDynamic);
282 });
283 bool requirePadding = linalg::PackOp::requirePaddingValueStrict(
284 inputShape: inputType.getShape(), innerDimsPos,
285 outputShape: linalg::PackOp::inferPackedTensorType(sourceType: inputType, innerTileSizes: maybeIntInnerTileSizes,
286 innerDimsPos, outerDimsPerm)
287 .getShape(),
288 outerDimsPerm, innerTiles: innerTileSizes);
289 currOperandDetails.innerDimsPos = innerDimsPos;
290 currOperandDetails.innerTileSizes = innerTileSizes;
291 currOperandDetails.outerDimsPerm = outerDimsPerm;
292 packedOperandMap[opOperand] = currOperandDetails;
293
294 return requirePadding;
295}
296
297/// Returns a tuple for packed operand and indexing_map with the assumptions:
298/// 1) The generic op is the producer of the pack op.
299/// 2) The generic op has only one result.
300/// If the operand is a scalar or packing dimensions are all irrelevant to the
301/// operand, the operand and the updated indexing map will be returned.
302/// Otherwise, it returns the packed operand and the updated indexing map. E.g.,
303///
304/// #map0 = affine_map<(d0, d1) -> (d0, d1)>
305/// #map1 = affine_map<(d0, d1) -> (d0)>
306/// #map2 = affine_map<(d0, d1) -> (d1)>
307/// %0 = linalg.generic {indexing_maps = [#map1, #map2, #map0],
308/// iterator_types = ["parallel", "parallel"]}
309/// ins(%arg0, %arg1 : tensor<?xf32>, tensor<?xf32>)
310/// outs(%init : tensor<?x?xf32>) {
311/// ^bb0(%arg3: f32, %arg4: f32, %arg5: f32):
312/// %4 = arith.addf %arg3, %arg4 : f32
313/// linalg.yield %4 : f32
314/// } -> tensor<?x?xf32>
315/// %1 = linalg.pack %0
316/// inner_dims_pos = [0, 1]
317/// inner_tiles = [8, 2]
318/// into %dest : tensor<?x?xf32> -> tensor<?x?x8x2xf32>
319///
320/// Taking the first input operand as an example, the inner tile size of d1 is
321/// 8. Thus, the below operation and `affine_map<(d0, d1, d2, d3)> ->
322/// affine_map<(d1, d3)>` will be returned.
323///
324/// %pack = linalg.pack %arg0
325/// inner_dims_pos = [0]
326/// inner_tiles = [8]
327/// into %init : tensor<?xf32> -> tensor<?x8xf32>
328static std::tuple<Value, AffineMap> getOrCreatePackedViewOfOperand(
329 OpBuilder &b, Location loc, OpOperand *opOperand,
330 const DenseMap<OpOperand *, PackedOperandDetails> &packedOperandMap) {
331 assert(packedOperandMap.contains(opOperand) &&
332 "packed operand details expected to be populated");
333 auto currOperandDetails = packedOperandMap.at(Val: opOperand);
334 auto innerDimsPos = currOperandDetails.innerDimsPos;
335 auto outerDimsPerm = currOperandDetails.outerDimsPerm;
336 auto innerTileSizes = currOperandDetails.innerTileSizes;
337 if (innerDimsPos.empty() && outerDimsPerm.empty())
338 return std::make_tuple(args: opOperand->get(), args&: currOperandDetails.indexingMap);
339
340 auto empty = linalg::PackOp::createDestinationTensor(
341 b, loc, source: opOperand->get(), innerTileSizes, innerDimsPos, outerDimsPerm);
342 auto poison = ub::PoisonOp::create(
343 builder&: b, location: loc, result: getElementTypeOrSelf(type: opOperand->get().getType()));
344 PackOp packedOperand =
345 linalg::PackOp::create(builder&: b, location: loc, source: opOperand->get(), dest: empty, innerDimsPos,
346 innerTiles: innerTileSizes, paddingValue: poison, outerDimsPerm);
347 return std::make_tuple(args: packedOperand.getResult(),
348 args&: currOperandDetails.indexingMap);
349}
350
351/// This function is a helper subroutine to pack a genericOp and return it. It
352/// will create a new generic op with the packed operand and the packed output
353/// according to packInfo when we attempt to push down unpack or bubble up pack
354/// around it. Implicitly this will only work when a packInfo can be obtained.
355/// This make sure that we are only using this function on parallel permuted
356/// dimensions.
357static FailureOr<GenericOp>
358packGenericOp(RewriterBase &rewriter, GenericOp genericOp, Value dest,
359 AffineMap packedOutIndexingMap, const PackInfo &packInfo,
360 bool isFoldableUnpackPack, bool poisonPaddingOk) {
361 Location loc = genericOp.getLoc();
362 SmallVector<Value> inputOperands;
363 SmallVector<Value> inputOperandsFromUnpackedSource;
364 SmallVector<AffineMap> indexingMaps;
365 auto hasEquivalentTiles = [](PackOp packOp, UnPackOp unPackOp) {
366 return packOp.getOuterDimsPerm() == unPackOp.getOuterDimsPerm() &&
367 packOp.getInnerDimsPos() == unPackOp.getInnerDimsPos() &&
368 llvm::equal(LRange: packOp.getMixedTiles(), RRange: unPackOp.getMixedTiles());
369 };
370 DenseMap<OpOperand *, PackedOperandDetails> packedOperandMap;
371 bool requiresPadding = false;
372 for (OpOperand *inputOperand : genericOp.getDpsInputOperands()) {
373 requiresPadding |= getPackedOperandDetails(b&: rewriter, packInfo, genericOp,
374 opOperand: inputOperand, packedOperandMap);
375 }
376 if (requiresPadding && !poisonPaddingOk)
377 return failure();
378
379 for (OpOperand *inputOperand : genericOp.getDpsInputOperands()) {
380 auto [packedOperand, packedIndexingMap] = getOrCreatePackedViewOfOperand(
381 b&: rewriter, loc, opOperand: inputOperand, packedOperandMap);
382 auto unpackOp = inputOperand->get().getDefiningOp<linalg::UnPackOp>();
383 auto packOp = packedOperand.getDefiningOp<linalg::PackOp>();
384 if (packOp && unpackOp && hasEquivalentTiles(packOp, unpackOp)) {
385 inputOperandsFromUnpackedSource.push_back(Elt: unpackOp.getSource());
386 } else {
387 inputOperandsFromUnpackedSource.push_back(Elt: packedOperand);
388 }
389 inputOperands.push_back(Elt: packedOperand);
390 indexingMaps.push_back(Elt: packedIndexingMap);
391 }
392
393 // If the unpack->pack sequences can be folded, replace use the sources of
394 // the unpack ops in any unpack->pack chains on the generic op operands.
395 if (isFoldableUnpackPack) {
396 inputOperands = inputOperandsFromUnpackedSource;
397 if (auto destPack = dest.getDefiningOp<linalg::PackOp>()) {
398 auto destUnPack = destPack.getSource().getDefiningOp<linalg::UnPackOp>();
399 if (destUnPack && hasEquivalentTiles(destPack, destUnPack)) {
400 dest = destUnPack.getSource();
401 }
402 }
403 }
404
405 int64_t numInnerLoops = packInfo.getNumTiledLoops();
406 SmallVector<utils::IteratorType> iterTypes =
407 genericOp.getIteratorTypesArray();
408 iterTypes.append(NumInputs: numInnerLoops, Elt: utils::IteratorType::parallel);
409
410 indexingMaps.push_back(Elt: packedOutIndexingMap);
411
412 auto newGenericOp = linalg::GenericOp::create(
413 builder&: rewriter, location: loc, resultTensorTypes: dest.getType(), inputs: inputOperands, outputs: dest, indexingMaps,
414 iteratorTypes: iterTypes,
415 /*bodyBuild=*/odsArg5: nullptr, attributes: linalg::getPrunedAttributeList(op: genericOp));
416 rewriter.cloneRegionBefore(region&: genericOp.getRegion(), parent&: newGenericOp.getRegion(),
417 before: newGenericOp.getRegion().begin());
418 return newGenericOp;
419}
420
421static bool isGenericOutsNotUsed(linalg::GenericOp genericOp) {
422 return llvm::all_of(Range: genericOp.getDpsInitsMutable(), P: [&](OpOperand &operand) {
423 return genericOp.getMatchingBlockArgument(opOperand: &operand).use_empty();
424 });
425}
426
427/// Bubbles up linalg.pack op through a producer generic op. This
428/// swap pack(generic) to generic(pack). The new generic op works on packed
429/// domain; pack ops are created for input and output operands. E.g.,
430///
431/// #map0 = affine_map<(d0, d1) -> (d0, d1)>
432/// %0 = tensor.dim %arg0, %c0 : tensor<?x?xf32>
433/// %1 = tensor.dim %arg0, %c1 : tensor<?x?xf32>
434/// %2 = tensor.empty(%0, %1) : tensor<?x?xf32>
435/// %3 = linalg.generic {indexing_maps = [#map0, #map0],
436/// iterator_types = ["parallel", "parallel"]}
437/// ins(%arg0 : tensor<?x?xf32>)
438/// outs(%2 : tensor<?x?xf32>) {
439/// ^bb0(%arg3: f32, %arg4: f32):
440/// %4 = arith.addf %arg3, %arg3 : f32
441/// linalg.yield %4 : f32
442/// } -> tensor<?x?xf32>
443/// %4 = linalg.pack %3
444/// inner_dims_pos = [0, 1]
445/// inner_tiles = [8, 2]
446/// into %dest : tensor<?x?xf32> -> tensor<?x?x8x2xf32>
447///
448/// will be converted to
449///
450/// #map = affine_map<()[s0] -> (s0 ceildiv 8)>
451/// #map1 = affine_map<()[s0] -> (s0 ceildiv 2)>
452/// #map2 = affine_map<(d0, d1, d2, d3) -> (d0, d1, d2, d3)>
453/// %dim = tensor.dim %arg0, %c0 : tensor<?x?xf32>
454/// %dim_0 = tensor.dim %arg0, %c1 : tensor<?x?xf32>
455/// %0 = affine.apply #map()[%dim]
456/// %1 = affine.apply #map1()[%dim_0]
457/// %2 = tensor.empty(%0, %1) : tensor<?x?x8x2xf32>
458/// %pack = linalg.pack %arg0
459/// inner_dims_pos = [0, 1]
460/// inner_tiles = [8, 2]
461/// into %2 : tensor<?x?xf32> -> tensor<?x?x8x2xf32>
462/// %3 = linalg.generic {indexing_maps = [#map2, #map2],
463/// iterator_types = ["parallel", "parallel", "parallel", "parallel"]}
464/// ins(%pack : tensor<?x?x8x2xf32>)
465/// outs(%arg1 : tensor<?x?x8x2xf32>) {
466/// ^bb0(%in: f32, %out: f32):
467/// %4 = arith.addf %in, %in : f32
468/// linalg.yield %4 : f32
469/// } -> tensor<?x?x8x2xf32>
470static FailureOr<GenericOp>
471bubbleUpPackOpThroughGenericOp(RewriterBase &rewriter, linalg::PackOp packOp,
472 const ControlPropagationFn &controlFn,
473 bool poisonPaddingOk) {
474 auto genericOp = packOp.getSource().getDefiningOp<GenericOp>();
475 if (!genericOp)
476 return failure();
477
478 // User controlled propagation function.
479 if (!controlFn(&packOp.getSourceMutable()))
480 return failure();
481
482 // TODO: Enable propagation in the presence of linalg.index and
483 // tensor.extract, likely as a separate pattern as the pack information and
484 // propagation decision needs to be inferred from the region of the generic.
485 if (hasGatherSemantics(genericOp))
486 return failure();
487
488 // TODO: Relax the restriction. We are able to bubble up the pack op through
489 // multi-result generic op. It just needs more work.
490 if (genericOp.getNumResults() != 1)
491 return failure();
492
493 // Bail-out if the result of the generic has multiple uses, as bubbling up
494 // creates recomputation if the generic has multiple users.
495 // TODO: Enable the case where every use is an identical pack op as no
496 // recomputation is needed in that case.
497 if (!genericOp->getResult(idx: 0).hasOneUse())
498 return failure();
499
500 // TODO: Add an option for allowing padding values. It could introduce
501 // undefined behavior if we unconditionally propagate pack op through all
502 // the ops. E.g., if the padding value is zero and there are division ops in
503 // a generic op. Some values of padding area could be NaN (0/0).
504 if (packOp.getPaddingValue())
505 return failure();
506
507 OpOperand *opOperand = genericOp.getDpsInitOperand(i: 0);
508 auto packInfo = getPackingInfoFromOperand(opOperand, genericOp, packOrUnPackOp: packOp);
509 if (failed(Result: packInfo))
510 return failure();
511
512 // We want to move the pack not the generic.
513 OpBuilder::InsertionGuard guard(rewriter);
514 rewriter.setInsertionPoint(genericOp);
515
516 // We need to handle two cases:
517 // 1) The linalg.pack destination is a tensor.empty. If this is the case, we
518 // create a new tensor.empty to avoid breaking dominance, as we are moving the
519 // linalg.pack above the linalg.generic.
520 // 2) The destination is not a tensor.empty. In this case we can replace only
521 // if the destination of the linalg.pack dominates the linalg.generic.
522 Value packOpDest = packOp.getDest();
523 if (!packOpDest.hasOneUse())
524 return failure();
525 if (auto emptyOp = packOpDest.getDefiningOp<tensor::EmptyOp>()) {
526 packOpDest = tensor::EmptyOp::create(builder&: rewriter, location: genericOp->getLoc(),
527 sizes: emptyOp.getMixedSizes(),
528 elementType: emptyOp.getType().getElementType());
529 } else {
530 DominanceInfo dom(genericOp);
531 if (!dom.properlyDominates(a: packOpDest, b: genericOp))
532 return failure();
533 }
534
535 // Rebuild the indexing map for the corresponding init operand.
536 DenseMap<OpOperand *, PackedOperandDetails> packedOperandMap;
537 bool requiresPadding = getPackedOperandDetails(b&: rewriter, packInfo: *packInfo, genericOp,
538 opOperand, packedOperandMap);
539 if (requiresPadding && !poisonPaddingOk)
540 return failure();
541
542 auto [packedOutOperand, packedOutIndexingMap] =
543 getOrCreatePackedViewOfOperand(b&: rewriter, loc: genericOp.getLoc(), opOperand,
544 packedOperandMap);
545 // Forward the new tensor.empty as a destination if it is one of the following
546 // situations:
547 // 1) The dps init operand is a tensor.empty.
548 // 2) The dps init is a write-only operand, i.e., it is not used in the
549 // genericOp
550 Value dest = packedOutOperand;
551 auto initTensor =
552 genericOp.getDpsInitOperand(i: 0)->get().getDefiningOp<tensor::EmptyOp>();
553 if (initTensor || isGenericOutsNotUsed(genericOp)) {
554 dest = packOpDest;
555 }
556 // pack(unpack) isn't naively foldable because the unpack op can be from
557 // an arbitrary domain so we need to keep both.
558 return packGenericOp(rewriter, genericOp, dest, packedOutIndexingMap,
559 packInfo: *packInfo, /*isFoldableUnpackPack=*/false,
560 poisonPaddingOk);
561}
562
563/// Wrapper pattern that applies bubbleUpPackOpThroughGenericOp method.
564struct BubbleUpPackOpThroughGenericOpPattern
565 : public OpRewritePattern<linalg::PackOp> {
566public:
567 BubbleUpPackOpThroughGenericOpPattern(MLIRContext *context,
568 ControlPropagationFn fun,
569 bool poisonPaddingOk)
570 : OpRewritePattern<linalg::PackOp>(context), controlFn(std::move(fun)),
571 poisonPaddingOk(std::move(poisonPaddingOk)) {}
572
573 LogicalResult matchAndRewrite(linalg::PackOp packOp,
574 PatternRewriter &rewriter) const override {
575 // Pack/unpack memref transformations are unsupported. The memref forms
576 // are mainly for bufferization and scalar lowering. Other uses are not
577 // recommended, see #225650 for details.
578 if (!packOp.hasPureTensorSemantics())
579 return failure();
580
581 auto genericOp = bubbleUpPackOpThroughGenericOp(rewriter, packOp, controlFn,
582 poisonPaddingOk);
583 if (failed(Result: genericOp))
584 return failure();
585 rewriter.replaceOp(op: packOp, newValues: genericOp->getResults());
586 return success();
587 }
588
589private:
590 ControlPropagationFn controlFn;
591 bool poisonPaddingOk;
592};
593
594/// Propagate a linalg.pack operation up through a tensor.pad. The idea is to
595/// add as many zero padding dimensions in `high` and `low` based on the number
596/// of point loops.
597class BubbleUpPackThroughPadOp final : public OpRewritePattern<linalg::PackOp> {
598public:
599 BubbleUpPackThroughPadOp(MLIRContext *context, ControlPropagationFn fun)
600 : OpRewritePattern<linalg::PackOp>(context), controlFn(std::move(fun)) {}
601
602 LogicalResult matchAndRewrite(linalg::PackOp packOp,
603 PatternRewriter &rewriter) const override {
604 // Pack/unpack memref transformations are unsupported. The memref forms
605 // are mainly for bufferization and scalar lowering. Other uses are not
606 // recommended, see #225650 for details.
607 if (!packOp.hasPureTensorSemantics())
608 return failure();
609
610 auto padOp = packOp.getSource().getDefiningOp<tensor::PadOp>();
611 if (!padOp)
612 return failure();
613
614 // User controlled propagation function.
615 if (!controlFn(&packOp.getSourceMutable()))
616 return failure();
617
618 // TODO: Enable padding when the padding values are the same.
619 if (packOp.getPaddingValue())
620 return failure();
621
622 // Fail for non-constant padding values. The body of the pad could
623 // depend on the padding indices and/or properties of the padded
624 // tensor so for now we fail.
625 // TODO: Support non-constant padding values.
626 Value paddingVal = padOp.getConstantPaddingValue();
627 if (!paddingVal)
628 return failure();
629
630 if (!packOp.getDest().getDefiningOp<tensor::EmptyOp>())
631 return failure();
632
633 ArrayRef<int64_t> innerDimsPos = packOp.getInnerDimsPos();
634
635 // Bail out if one of the padded dimension is a tiled one.
636 llvm::SmallBitVector paddedDims = padOp.getPaddedDims();
637 llvm::SmallBitVector innerDims(paddedDims.size());
638 for (int64_t dim : innerDimsPos)
639 innerDims.flip(Idx: dim);
640 if (paddedDims.anyCommon(RHS: innerDims))
641 return failure();
642
643 Location loc = padOp->getLoc();
644 OpBuilder::InsertionGuard guard(rewriter);
645 rewriter.setInsertionPoint(padOp);
646
647 ArrayRef<int64_t> outerDimsPerm = packOp.getOuterDimsPerm();
648 SmallVector<OpFoldResult> mixedTiles = packOp.getMixedTiles();
649 auto empty = linalg::PackOp::createDestinationTensor(
650 b&: rewriter, loc, source: padOp.getSource(), innerTileSizes: mixedTiles, innerDimsPos,
651 outerDimsPerm);
652 auto sourcePack = linalg::PackOp::create(
653 builder&: rewriter, location: loc, source: padOp.getSource(), dest: empty, innerDimsPos, innerTiles: mixedTiles,
654 /*padding=*/paddingValue: std::nullopt, outerDimsPerm);
655
656 // If we have `outer_dims_perms` we need to adjust the padded dimensions.
657 SmallVector<OpFoldResult> lowPad = padOp.getMixedLowPad();
658 SmallVector<OpFoldResult> highPad = padOp.getMixedHighPad();
659 if (!outerDimsPerm.empty()) {
660 applyPermutationToVector<OpFoldResult>(inVec&: lowPad, permutation: outerDimsPerm);
661 applyPermutationToVector<OpFoldResult>(inVec&: highPad, permutation: outerDimsPerm);
662 }
663 // The tiled dimensions were verified to be unpadded above, so here we
664 // just append 0 for the inner tile dimensions.
665 size_t pointLoopsSize = innerDimsPos.size();
666 lowPad.append(NumInputs: pointLoopsSize, Elt: rewriter.getIndexAttr(value: 0));
667 highPad.append(NumInputs: pointLoopsSize, Elt: rewriter.getIndexAttr(value: 0));
668
669 auto newPadOp = tensor::PadOp::create(
670 builder&: rewriter, location: loc, /*result=*/resultType: Type(), source: sourcePack.getResult(), low: lowPad,
671 high: highPad, constantPadValue: paddingVal, nofold: padOp.getNofold());
672
673 // If the pad has more than one user, create an unpack on the new pad to
674 // replace the other uses.
675 if (!padOp->hasOneUse()) {
676 auto unpackEmpty = linalg::UnPackOp::createDestinationTensor(
677 b&: rewriter, loc, source: newPadOp, innerTileSizes: mixedTiles, innerDimsPos, outerDimsPerm);
678 UnPackOp unpackedPad =
679 linalg::UnPackOp::create(builder&: rewriter, location: loc, source: newPadOp, dest: unpackEmpty,
680 innerDimsPos, innerTiles: mixedTiles, outerDimsPerm);
681 rewriter.replaceAllUsesExcept(from: padOp, to: unpackedPad.getResult(), exceptedUser: sourcePack);
682 }
683
684 // Replace the pack with the new pad.
685 rewriter.replaceOp(op: packOp, newValues: newPadOp.getResult());
686
687 return success();
688 }
689
690private:
691 ControlPropagationFn controlFn;
692};
693
694/// Project dimsPos to the inner-most non-unit dim pos with reassocIndices.
695///
696/// For example, given dimsPos [0, 2], reassocIndices [[0, 1], [2, 3]], and
697/// targetShape [16, 16, 32, 1], it returns [1, 2]. Because for pos 0, the
698/// inner-most projected dim in pos [0, 1] is 1. And for pos 2, the inner-most
699/// non-unit projected dims in pos [2, 3] is 2.
700///
701/// If all candidates in a reassociation are unit dims, it chooses the
702/// inner-most dim pos.
703static SmallVector<int64_t>
704projectToInnerMostNonUnitDimsPos(ArrayRef<int64_t> dimsPos,
705 ArrayRef<ReassociationIndices> reassocIndices,
706 ArrayRef<int64_t> targetShape) {
707 SmallVector<int64_t> projectedDimsPos;
708 for (auto pos : dimsPos) {
709 // In the case all dims are unit, this will return the inner-most one.
710 int64_t projectedPos = reassocIndices[pos].back();
711 for (auto i : llvm::reverse(C: reassocIndices[pos])) {
712 int64_t dim = targetShape[i];
713 if (dim > 1 || ShapedType::isDynamic(dValue: dim)) {
714 projectedPos = i;
715 break;
716 }
717 }
718 projectedDimsPos.push_back(Elt: projectedPos);
719 }
720 return projectedDimsPos;
721}
722
723/// Check if all dims in dimsPos are divisible by the corresponding tile sizes.
724static bool isDimsDivisibleByTileSizes(ArrayRef<int64_t> dimsPos,
725 ArrayRef<int64_t> shape,
726 ArrayRef<int64_t> tileSizes) {
727 for (auto [pos, tileSize] : llvm::zip_equal(t&: dimsPos, u&: tileSizes)) {
728 int64_t dim = shape[pos];
729 if (ShapedType::isDynamic(dValue: dim) || (dim % tileSize) != 0)
730 return false;
731 }
732 return true;
733}
734
735/// Permutate the reassociation indices and reindex them in the sequence order.
736/// Returns the next dim pos in the sequence.
737///
738/// For example, given reassocIndices [[0, 1], [2]] and permutation [1, 0], it
739/// applies the permutation to get [[2], [0, 1]] and reindexes the indices into
740/// [[0], [1, 2]].
741static int64_t applyPermutationAndReindexReassoc(
742 SmallVector<ReassociationIndices> &reassocIndices,
743 ArrayRef<int64_t> permutation) {
744 if (!permutation.empty())
745 applyPermutationToVector<ReassociationIndices>(inVec&: reassocIndices, permutation);
746 int64_t nextPos = 0;
747 for (ReassociationIndices &indices : reassocIndices) {
748 for (auto &index : indices) {
749 index = nextPos;
750 nextPos += 1;
751 }
752 }
753 return nextPos;
754}
755
756/// Bubble up pack op through collapse shape op when the packed dims can be
757/// projected to the dims before collapsing. This is possible when the inner
758/// tile sizes can divide the projected dims.
759///
760/// For example:
761///
762/// %collapsed = tensor.collapse_shape %in [[0, 1], 2]
763/// : tensor<?x16x4xf32> into tensor<?x4xf32>
764/// %pack = linalg.pack %collapsed outer_dims_perm = [0, 1]
765/// inner_dims_pos = [0, 1] inner_tiles = [8, 1] into %empty
766/// : tensor<?x4xf32> -> tensor<?x4x8x1xf32>
767///
768/// can be transformed into:
769///
770/// %pack = linalg.pack %in outer_dims_perm = [1, 2]
771/// inner_dims_pos = [1, 2] inner_tiles = [8, 1] into %empty
772/// : tensor<?x16x4xf32> -> tensor<?x2x4x8x1xf32>
773/// %collapsed = tensor.collapse_shape %pack [[0, 1], 2, 3, 4]
774/// : tensor<?x2x4x8x1xf32> into tensor<?x4x8x1>
775static LogicalResult
776bubbleUpPackOpThroughCollapseShape(tensor::CollapseShapeOp collapseOp,
777 linalg::PackOp packOp,
778 PatternRewriter &rewriter) {
779 // Pack/unpack memref transformations are unsupported. The memref forms
780 // are mainly for bufferization and scalar lowering. Other uses are not
781 // recommended, see #225650 for details.
782 if (!packOp.hasPureTensorSemantics())
783 return failure();
784
785 SmallVector<int64_t> innerTileSizes = packOp.getStaticTiles();
786 ArrayRef<int64_t> innerDimsPos = packOp.getInnerDimsPos();
787 ArrayRef<int64_t> outerDimsPerm = packOp.getOuterDimsPerm();
788
789 ArrayRef<int64_t> srcShape = collapseOp.getSrcType().getShape();
790 SmallVector<ReassociationIndices> reassocIndices =
791 collapseOp.getReassociationIndices();
792 // Project inner tile pos to the dim pos before collapsing. For example, if
793 // dims [x, y] is collapsed into [z], packing on dim z can be projected back
794 // to pack on dim y.
795 //
796 // Project to inner-most non-unit dims to increase the chance that they can be
797 // divided by the inner tile sizes. This is correct because for [..., x, 1],
798 // packing on dim 1 is equivalent to packing on dim x.
799 SmallVector<int64_t> projectedInnerDimsPos =
800 projectToInnerMostNonUnitDimsPos(dimsPos: innerDimsPos, reassocIndices, targetShape: srcShape);
801
802 if (!isDimsDivisibleByTileSizes(dimsPos: projectedInnerDimsPos, shape: srcShape,
803 tileSizes: innerTileSizes)) {
804 return failure();
805 }
806 // Expand the outer dims permutation with the associated source dims for the
807 // new permutation after bubbling. This is because moving a collapsed dim is
808 // equivalent to moving the associated source dims together.
809 SmallVector<int64_t> newOuterDimsPerm;
810 for (auto outerPos : outerDimsPerm)
811 llvm::append_range(C&: newOuterDimsPerm, R&: reassocIndices[outerPos]);
812
813 auto emptyOp = linalg::PackOp::createDestinationTensor(
814 b&: rewriter, loc: packOp.getLoc(), source: collapseOp.getSrc(), innerTileSizes: packOp.getMixedTiles(),
815 innerDimsPos: projectedInnerDimsPos, outerDimsPerm: newOuterDimsPerm);
816 auto newPackOp = linalg::PackOp::create(
817 builder&: rewriter, location: packOp.getLoc(), source: collapseOp.getSrc(), dest: emptyOp,
818 innerDimsPos: projectedInnerDimsPos, innerTiles: packOp.getMixedTiles(), paddingValue: packOp.getPaddingValue(),
819 outerDimsPerm: newOuterDimsPerm);
820
821 SmallVector<ReassociationIndices> newReassocIndices = reassocIndices;
822 // First apply the permutation on the reassociations of the outer dims.
823 // For example given the permutation [1, 0], the reassociations [[0, 1], [2]]
824 // -> [[0], [1, 2]]
825 int64_t nextPos =
826 applyPermutationAndReindexReassoc(reassocIndices&: newReassocIndices, permutation: outerDimsPerm);
827 // Then add direct mapping for the inner tile dims.
828 for (size_t i = 0; i < innerDimsPos.size(); ++i) {
829 newReassocIndices.push_back(Elt: {nextPos});
830 nextPos += 1;
831 }
832
833 auto newCollapseOp = tensor::CollapseShapeOp::create(
834 builder&: rewriter, location: collapseOp.getLoc(), resultType: packOp.getResult().getType(),
835 src: newPackOp.getResult(), reassociation: newReassocIndices);
836 rewriter.replaceOp(op: packOp, newOp: newCollapseOp);
837
838 return success();
839}
840
841/// Project dimsPos to their collapsed positions in the reassocIndices.
842///
843/// For example, given dimsPos [0, 1, 2, 4], and matching reassocIndices
844/// [[0], [1, 2], [3], [4]], it returns [0, 1, 1, 3]. Because for pos 0,
845/// the reassoc dim [0] is 0. For pos 1 and 2, the reassoc dim in pos
846/// [1, 2] is 1. And for pos 4, the reassoc dim [4] is 3.
847static SmallVector<int64_t>
848projectDimsPosIntoReassocPos(ArrayRef<int64_t> dimsPos,
849 ArrayRef<ReassociationIndices> reassocIndices) {
850 SmallVector<int64_t> projectedPos;
851
852 // Map each dimension to the position of corresponding reassociation index.
853 for (auto pos : dimsPos) {
854 for (auto [idx, indices] : llvm::enumerate(First&: reassocIndices)) {
855 // If the dimension is present in the current indices group, the group
856 // position within the reassociation map is the desired projected
857 // dimension position.
858 if (llvm::is_contained(Range: indices, Element: pos)) {
859 projectedPos.push_back(Elt: idx);
860 break;
861 }
862 }
863 }
864 assert(projectedPos.size() == dimsPos.size() && "Invalid dim pos projection");
865
866 return projectedPos;
867}
868
869/// Bubble up pack op through expand shape op.
870///
871/// For example:
872///
873/// %expand = tensor.expand_shape %in [[0], [1, 2]]
874/// : tensor<?x64xf32> into tensor<?x4x16xf32>
875/// %pack = linalg.pack %expand outer_dims_perm = [0, 1]
876/// inner_dims_pos = [2] inner_tiles = [8] into %empty
877/// : tensor<?x4x16xf32> -> tensor<?x4x2x8xf32>
878///
879/// can be transformed into:
880///
881/// %pack = linalg.pack %in outer_dims_perm = [1, 2]
882/// inner_dims_pos = [1] inner_tiles = [8] into %empty
883/// : tensor<?x64xf32> -> tensor<?x8x8xf32>
884/// %expand = tensor.expand_shape %pack [[0], [1, 2], [3]]
885/// : tensor<?x8x8xf32> into tensor<?x4x2x8xf32>
886static LogicalResult
887bubbleUpPackOpThroughExpandShape(tensor::ExpandShapeOp expandOp,
888 linalg::PackOp packOp,
889 PatternRewriter &rewriter) {
890 // Pack/unpack memref transformations are unsupported. The memref forms
891 // are mainly for bufferization and scalar lowering. Other uses are not
892 // recommended, see #225650 for details.
893 if (!packOp.hasPureTensorSemantics())
894 return failure();
895
896 // Outer dimensions permutation is not supported currently.
897 // TODO: Handle outer_dims_perm variants.
898 ArrayRef<int64_t> outerDimsPerm = packOp.getOuterDimsPerm();
899 if (!outerDimsPerm.empty() && !isIdentityPermutation(permutation: outerDimsPerm)) {
900 return rewriter.notifyMatchFailure(arg&: packOp,
901 msg: "non-identity outer dims perm NYI");
902 }
903
904 // Validate dimensions' relations between shape expansion and packing.
905 SmallVector<ReassociationIndices, 4> reassoc =
906 expandOp.getReassociationIndices();
907 ArrayRef<int64_t> packInnerDims = packOp.getInnerDimsPos();
908 llvm::SetVector<int64_t> packDimsPos(llvm::from_range, packInnerDims);
909
910 for (auto [idx, indices] : llvm::enumerate(First&: reassoc)) {
911 // For each expand_shape reassociation, figure out which dimensions get
912 // packed if any.
913 llvm::SetVector<int64_t> expandDimPos(llvm::from_range, indices);
914 llvm::SetVector<int64_t> packedDims =
915 llvm::set_intersection(S1: packDimsPos, S2: expandDimPos);
916
917 // The expanded dimension is not packed so, it does not affect moving pack
918 // before shape expansion - simply continue.
919 if (packedDims.empty())
920 continue;
921 // Shape expansion cannot be propagated when multiple expanded dimension are
922 // packed - in this case operation reordering would affect final element
923 // positions and/or shapes can no longer be projected.
924 if (packedDims.size() != 1)
925 return rewriter.notifyMatchFailure(
926 arg&: packOp, msg: "only one of the expanded dimensions can be packed");
927 // Only the inner-most expanded dimension should be packed. Otherwise,
928 // elements order will be affected after operation reordering.
929 if (packedDims.front() != indices.back())
930 return rewriter.notifyMatchFailure(
931 arg&: packOp, msg: "can only pack the inner-most expanded dimension");
932 }
933
934 // Project pack.inner_dims_pos to positions before shape expansion.
935 SmallVector<int64_t> projectedInnerDimsPos =
936 projectDimsPosIntoReassocPos(dimsPos: packInnerDims, reassocIndices: reassoc);
937
938 // Project the shape expansion to new packed shape.
939 // The pack.outer_dims_perm is restricted to identity so, the permutation can
940 // be omitted for simplicity.
941 // TODO: Account for outer dimensions permutation.
942 //
943 // If reassociation is not possible, then reordering cannot happen.
944 // This can be caused by pack padding affecting previously expanded
945 // dimensions or packing extending dimensions.
946 RankedTensorType newPackType = linalg::PackOp::inferPackedTensorType(
947 sourceType: expandOp.getSrcType(), innerTileSizes: packOp.getStaticInnerTiles(),
948 innerDimsPos: projectedInnerDimsPos, /*outerDimsPerm=*/SmallVector<int64_t>{});
949 auto reassocExpand =
950 getReassociationIndicesForReshape(sourceType: newPackType, targetType: packOp.getDestType());
951 if (!reassocExpand)
952 return rewriter.notifyMatchFailure(
953 arg&: packOp, msg: "could not reassociate dims after bubbling up");
954
955 Value destTensor = linalg::PackOp::createDestinationTensor(
956 b&: rewriter, loc: packOp.getLoc(), source: expandOp.getSrc(), innerTileSizes: packOp.getMixedTiles(),
957 innerDimsPos: projectedInnerDimsPos, /*outerDimsPerm=*/SmallVector<int64_t>{});
958 PackOp packedVal = linalg::PackOp::create(
959 builder&: rewriter, location: packOp.getLoc(), source: expandOp.getSrc(), dest: destTensor,
960 innerDimsPos: projectedInnerDimsPos, innerTiles: packOp.getMixedTiles(), paddingValue: packOp.getPaddingValue(),
961 /*outerDimsPerm=*/SmallVector<int64_t>{});
962
963 Value newExpandOp = tensor::ExpandShapeOp::create(
964 builder&: rewriter, location: packOp.getLoc(), resultType: packOp.getDestType(), src: packedVal.getResult(),
965 reassociation: *reassocExpand);
966 rewriter.replaceOp(op: packOp, newValues: newExpandOp);
967
968 return success();
969}
970
971class BubbleUpPackOpThroughReshapeOp final
972 : public OpRewritePattern<linalg::PackOp> {
973public:
974 BubbleUpPackOpThroughReshapeOp(MLIRContext *context, ControlPropagationFn fun)
975 : OpRewritePattern<linalg::PackOp>(context), controlFn(std::move(fun)) {}
976
977 LogicalResult matchAndRewrite(linalg::PackOp packOp,
978 PatternRewriter &rewriter) const override {
979 // Pack/unpack memref transformations are unsupported. The memref forms
980 // are mainly for bufferization and scalar lowering. Other uses are not
981 // recommended, see #225650 for details.
982 if (!packOp.hasPureTensorSemantics())
983 return failure();
984
985 Operation *srcOp = packOp.getSource().getDefiningOp();
986 // Currently only support when the pack op is the only user.
987 if (!srcOp || !(srcOp->getNumResults() == 1) ||
988 !srcOp->getResult(idx: 0).hasOneUse()) {
989 return failure();
990 }
991 // Currently only support static inner tile sizes.
992 if (llvm::any_of(Range: packOp.getStaticTiles(), P: ShapedType::isDynamic))
993 return failure();
994
995 // User controlled propagation function.
996 if (!controlFn(&packOp.getSourceMutable()))
997 return failure();
998
999 return TypeSwitch<Operation *, LogicalResult>(srcOp)
1000 .Case(caseFn: [&](tensor::CollapseShapeOp op) {
1001 return bubbleUpPackOpThroughCollapseShape(collapseOp: op, packOp, rewriter);
1002 })
1003 .Case(caseFn: [&](tensor::ExpandShapeOp op) {
1004 return bubbleUpPackOpThroughExpandShape(expandOp: op, packOp, rewriter);
1005 })
1006 .Default(defaultResult: failure());
1007 }
1008
1009private:
1010 ControlPropagationFn controlFn;
1011};
1012
1013/// Push down unpack op through expand shape op when the packed dims can be
1014/// projected to the dims after expanding. This is possible when the inner tile
1015/// sizes can divide the projected dims.
1016///
1017/// For example:
1018///
1019/// %unpack = linalg.unpack %in outer_dims_perm = [0, 1]
1020/// inner_dims_pos = [0, 1] inner_tiles = [8, 8] into %empty
1021/// : tensor<?x32x8x8xf32> -> tensor<?x256xf32>
1022/// %expanded = tensor.expand_shape %unpack [[0, 1], [2]]
1023/// : tensor<?x256xf32> into tensor<?x256x256xf32>
1024///
1025/// can be transformed into:
1026///
1027/// %expanded = tensor.expand_shape %ain [[0, 1], [2], [3], [4]]
1028/// : tensor<?x32x8x8xf32> into tensor<?x32x32x8x8xf32>
1029/// %unpack = linalg.unpack %expanded outer_dims_perm = [0, 1, 2]
1030/// inner_dims_pos = [1, 2] inner_tiles = [8, 8] into %empty
1031/// : tensor<?x32x32x8x8xf32> -> tensor<?x256x256xf32>
1032static LogicalResult pushDownUnPackOpThroughExpandShape(
1033 linalg::UnPackOp unPackOp, tensor::ExpandShapeOp expandOp,
1034 PatternRewriter &rewriter, ControlPropagationFn controlFn) {
1035 // Pack/unpack memref transformations are unsupported. The memref forms
1036 // are mainly for bufferization and scalar lowering. Other uses are not
1037 // recommended, see #225650 for details.
1038 if (!unPackOp.hasPureTensorSemantics())
1039 return failure();
1040
1041 // User controlled propagation function.
1042 if (!controlFn(&expandOp.getSrcMutable()))
1043 return failure();
1044
1045 SmallVector<int64_t> innerTileSizes = unPackOp.getStaticTiles();
1046 ArrayRef<int64_t> innerDimsPos = unPackOp.getInnerDimsPos();
1047 ArrayRef<int64_t> outerDimsPerm = unPackOp.getOuterDimsPerm();
1048
1049 auto expandTy = dyn_cast<RankedTensorType>(Val: expandOp.getType());
1050 if (!expandTy)
1051 return failure();
1052 ArrayRef<int64_t> dstShape = expandTy.getShape();
1053 SmallVector<ReassociationIndices> reassocIndices =
1054 expandOp.getReassociationIndices();
1055 // Project inner tile pos to the dim pos after expanding. For example, if dims
1056 // [z] is expanded into [x, y], unpacking on dim z can be projected to unpack
1057 // on dim y.
1058 //
1059 // Project to inner-most non-unit dims to increase the chance that they can be
1060 // divided by the inner tile sizes. This is correct because for [..., x, 1],
1061 // unpacking on dim 1 is equivalent to unpacking on dim x.
1062 SmallVector<int64_t> projectedInnerDimsPos =
1063 projectToInnerMostNonUnitDimsPos(dimsPos: innerDimsPos, reassocIndices, targetShape: dstShape);
1064
1065 if (!isDimsDivisibleByTileSizes(dimsPos: projectedInnerDimsPos, shape: dstShape,
1066 tileSizes: innerTileSizes)) {
1067 return failure();
1068 }
1069 // Expand the outer dims permutation with the associated expanded dims for the
1070 // new permutation after pushing. This is because moving a source dim is
1071 // equivalent to moving the associated expanded dims together.
1072 SmallVector<int64_t> newOuterDimsPerm;
1073 for (auto outerPos : outerDimsPerm)
1074 llvm::append_range(C&: newOuterDimsPerm, R&: reassocIndices[outerPos]);
1075
1076 SmallVector<ReassociationIndices> newReassocIndices = reassocIndices;
1077 // First apply the permutation on the reassociations of the outer dims.
1078 // For example given the permutation [1, 0], the reassociations [[0, 1], [2]]
1079 // -> [[0], [1, 2]]
1080 int64_t nextPos =
1081 applyPermutationAndReindexReassoc(reassocIndices&: newReassocIndices, permutation: outerDimsPerm);
1082 // Then add direct mapping for the inner tile dims.
1083 for (size_t i = 0; i < innerDimsPos.size(); ++i) {
1084 newReassocIndices.push_back(Elt: {nextPos});
1085 nextPos += 1;
1086 }
1087
1088 RankedTensorType newExpandType = linalg::PackOp::inferPackedTensorType(
1089 sourceType: expandTy, innerTileSizes, innerDimsPos: projectedInnerDimsPos, outerDimsPerm: newOuterDimsPerm);
1090 auto newExpandOp =
1091 tensor::ExpandShapeOp::create(builder&: rewriter, location: expandOp.getLoc(), resultType: newExpandType,
1092 src: unPackOp.getSource(), reassociation: newReassocIndices);
1093
1094 auto emptyOp = linalg::UnPackOp::createDestinationTensor(
1095 b&: rewriter, loc: unPackOp.getLoc(), source: newExpandOp, innerTileSizes: unPackOp.getMixedTiles(),
1096 innerDimsPos: projectedInnerDimsPos, outerDimsPerm: newOuterDimsPerm);
1097 auto newUnPackOp = linalg::UnPackOp::create(
1098 builder&: rewriter, location: unPackOp.getLoc(), source: newExpandOp.getResult(), dest: emptyOp,
1099 innerDimsPos: projectedInnerDimsPos, innerTiles: unPackOp.getMixedTiles(), outerDimsPerm: newOuterDimsPerm);
1100 rewriter.replaceOp(op: expandOp, newOp: newUnPackOp);
1101
1102 return success();
1103}
1104
1105class PushDownUnPackOpThroughReshapeOp final
1106 : public OpRewritePattern<linalg::UnPackOp> {
1107public:
1108 PushDownUnPackOpThroughReshapeOp(MLIRContext *context,
1109 ControlPropagationFn fun)
1110 : OpRewritePattern<linalg::UnPackOp>(context), controlFn(std::move(fun)) {
1111 }
1112
1113 LogicalResult matchAndRewrite(linalg::UnPackOp unPackOp,
1114 PatternRewriter &rewriter) const override {
1115 // Pack/unpack memref transformations are unsupported. The memref forms
1116 // are mainly for bufferization and scalar lowering. Other uses are not
1117 // recommended, see #225650 for details.
1118 if (!unPackOp.hasPureTensorSemantics())
1119 return failure();
1120
1121 Value result = unPackOp.getResult();
1122 // Currently only support unpack op with the single user.
1123 if (!result.hasOneUse()) {
1124 return failure();
1125 }
1126 // Currently only support static inner tile sizes.
1127 if (llvm::any_of(Range: unPackOp.getStaticTiles(), P: ShapedType::isDynamic))
1128 return failure();
1129
1130 Operation *consumerOp = *result.user_begin();
1131 return TypeSwitch<Operation *, LogicalResult>(consumerOp)
1132 .Case(caseFn: [&](tensor::ExpandShapeOp op) {
1133 return pushDownUnPackOpThroughExpandShape(unPackOp, expandOp: op, rewriter,
1134 controlFn);
1135 })
1136 .Default(defaultResult: failure());
1137 }
1138
1139private:
1140 ControlPropagationFn controlFn;
1141};
1142
1143// TODO: Relax this restriction. We should unpack a generic op also
1144// in the presence of multiple unpack ops as producers.
1145/// Return the unpacked operand, if present, for the current generic op.
1146static FailureOr<OpOperand *> getUnPackedOperand(GenericOp genericOp) {
1147 OpOperand *unPackedOperand = nullptr;
1148 for (OpOperand &operand : genericOp->getOpOperands()) {
1149 auto unPackOp = operand.get().getDefiningOp<linalg::UnPackOp>();
1150 if (!unPackOp)
1151 continue;
1152 if (unPackedOperand)
1153 return failure();
1154 unPackedOperand = &operand;
1155 }
1156 if (!unPackedOperand)
1157 return failure();
1158 return unPackedOperand;
1159}
1160
1161/// Push down a linalg.unpack op through a generic op.
1162/// The new generic op works on packed domain; pack ops are created for input
1163/// and output operands. A linalg.unpack op is inserted right after the packed
1164/// generic. E.g.
1165///
1166/// #map = affine_map<(d0, d1, d2, d3) -> (d0, d1, d2, d3)>
1167///
1168/// %arg0 = tensor<12x2x56x56x32xf32> // packed arg.
1169///
1170/// %0 = tensor.empty() : tensor<12x56x56x64xf32>
1171/// %1 = linalg.unpack %arg0 outer_dims_perm = [0, 3, 1, 2]
1172/// inner_dims_pos = [3] inner_tiles = [32] into %0
1173/// %2 = linalg.generic {indexing_maps = [#map],
1174/// iterator_types = ["parallel", "parallel", "parallel", "parallel"]}
1175/// outs(%1 : tensor<12x56x56x64xf32>) {
1176/// ^bb0(%out : f32):
1177/// linalg.yield %out : f32
1178/// } -> tensor<12x56x56x64xf32>
1179///
1180/// will be converted to
1181///
1182/// #map = affine_map<(d0, d1, d2, d3, d4) -> (d0, d1, d2, d3, d4)>
1183///
1184/// %0 = tensor.empty() : tensor<12x56x56x64xf32>
1185/// %1 = linalg.generic {indexing_maps = [#map],
1186/// iterator_types = ["parallel", "parallel", "parallel",
1187/// "parallel", "parallel"]}
1188/// outs(%arg0 : tensor<12x2x56x56x32xf32>) {
1189/// ^bb0(%out : f32):
1190/// linalg.yield %out : f32
1191/// } -> tensor<12x2x56x56x32xf32>
1192/// %2 = linalg.unpack %1 outer_dims_perm = [0, 3, 1, 2]
1193/// inner_dims_pos = [3] inner_tiles = [32] into %0
1194///
1195static FailureOr<std::tuple<GenericOp, Value>>
1196pushDownUnPackOpThroughGenericOp(RewriterBase &rewriter, GenericOp genericOp,
1197 ControlPropagationFn controlFn,
1198 bool poisonPaddingOk) {
1199 if (genericOp.getNumResults() != 1)
1200 return failure();
1201
1202 if (hasGatherSemantics(genericOp))
1203 return failure();
1204
1205 // Collect the unPacked operand, if present.
1206 auto maybeUnPackedOperand = getUnPackedOperand(genericOp);
1207 if (failed(Result: maybeUnPackedOperand))
1208 return failure();
1209 OpOperand *unPackedOperand = *(maybeUnPackedOperand);
1210
1211 // Extract packing information.
1212 linalg::UnPackOp producerUnPackOp =
1213 unPackedOperand->get().getDefiningOp<linalg::UnPackOp>();
1214 assert(producerUnPackOp && "expect a valid UnPackOp");
1215
1216 if (!controlFn(unPackedOperand))
1217 return failure();
1218
1219 auto packInfo =
1220 getPackingInfoFromOperand(opOperand: unPackedOperand, genericOp, packOrUnPackOp: producerUnPackOp);
1221 if (failed(Result: packInfo))
1222 return failure();
1223
1224 // Rebuild the indexing map for the corresponding init operand.
1225 DenseMap<OpOperand *, PackedOperandDetails> packedOperandMap;
1226 bool requiresPadding =
1227 getPackedOperandDetails(b&: rewriter, packInfo: *packInfo, genericOp,
1228 opOperand: genericOp.getDpsInitOperand(i: 0), packedOperandMap);
1229 if (requiresPadding && !poisonPaddingOk)
1230 return failure();
1231
1232 auto [packedOutOperand, packedOutIndexingMap] =
1233 getOrCreatePackedViewOfOperand(b&: rewriter, loc: genericOp.getLoc(),
1234 opOperand: genericOp.getDpsInitOperand(i: 0),
1235 packedOperandMap);
1236 auto destPack = packedOutOperand.getDefiningOp<linalg::PackOp>();
1237
1238 // Forward the new tensor.empty as a destination if it is one of the following
1239 // situations:
1240 // 1) The dps init operand is a tensor.empty.
1241 // 2) The dps init is a write-only operand, i.e., it is not used in the
1242 // genericOp
1243 Value dest = packedOutOperand;
1244 auto initTensor =
1245 genericOp.getDpsInitOperand(i: 0)->get().getDefiningOp<tensor::EmptyOp>();
1246 if (initTensor || isGenericOutsNotUsed(genericOp)) {
1247 if (destPack)
1248 dest = destPack.getDest();
1249 }
1250
1251 // Pack the genericOp.
1252 // pack(unpack) is foldable in this case. This is because in pushing down the
1253 // unpack, by default we will populate an additional pack op after the unpack.
1254 // This guarantees them to be foldable.
1255 auto maybeGenericOp =
1256 packGenericOp(rewriter, genericOp, dest, packedOutIndexingMap, packInfo: *packInfo,
1257 /*isFoldableUnpackPack=*/true, poisonPaddingOk);
1258 if (failed(Result: maybeGenericOp))
1259 return failure();
1260 GenericOp newGenericOp = *maybeGenericOp;
1261 Value newResult =
1262 newGenericOp.getTiedOpResult(opOperand: newGenericOp.getDpsInitOperand(i: 0));
1263
1264 // If the output is unaffected, no need to unpack.
1265 if (!destPack)
1266 return std::make_tuple(args&: newGenericOp, args&: newResult);
1267
1268 auto mixedTiles = destPack.getMixedTiles();
1269 auto innerDimsPos = destPack.getInnerDimsPos();
1270 auto outerDimsPerm = destPack.getOuterDimsPerm();
1271
1272 // Insert an unPackOp right after the packed generic.
1273 Value unPackOpRes =
1274 linalg::UnPackOp::create(builder&: rewriter, location: genericOp.getLoc(), source: newResult,
1275 dest: destPack.getSource(), innerDimsPos, innerTiles: mixedTiles,
1276 outerDimsPerm)
1277 .getResult();
1278
1279 return std::make_tuple(args&: newGenericOp, args&: unPackOpRes);
1280}
1281
1282// Wrapper pattern that applies pushDownUnPackOpThroughGenericOp method.
1283struct PushDownUnPackOpThroughGenericOp : public OpRewritePattern<GenericOp> {
1284public:
1285 PushDownUnPackOpThroughGenericOp(MLIRContext *context,
1286 ControlPropagationFn fun,
1287 bool poisonPaddingOk)
1288 : OpRewritePattern<GenericOp>(context), controlFn(std::move(fun)),
1289 poisonPaddingOk(std::move(poisonPaddingOk)) {}
1290
1291 LogicalResult matchAndRewrite(GenericOp genericOp,
1292 PatternRewriter &rewriter) const override {
1293 auto genericAndRepl = pushDownUnPackOpThroughGenericOp(
1294 rewriter, genericOp, controlFn, poisonPaddingOk);
1295 if (failed(Result: genericAndRepl))
1296 return failure();
1297 rewriter.replaceOp(op: genericOp, newValues: std::get<1>(t&: *genericAndRepl));
1298 return success();
1299 }
1300
1301private:
1302 ControlPropagationFn controlFn;
1303 bool poisonPaddingOk;
1304};
1305
1306/// Propagate a linalg.unpack operation through a tensor.pad. The idea is to
1307/// add as many zero padding dimensions in `high` and `low` based on the number
1308/// of point loops.
1309struct PushDownUnPackThroughPadOp : public OpRewritePattern<tensor::PadOp> {
1310 PushDownUnPackThroughPadOp(MLIRContext *context, ControlPropagationFn fun)
1311 : OpRewritePattern<tensor::PadOp>(context), controlFn(std::move(fun)) {}
1312
1313 LogicalResult matchAndRewrite(tensor::PadOp padOp,
1314 PatternRewriter &rewriter) const override {
1315 linalg::UnPackOp unpackOp =
1316 padOp.getSource().getDefiningOp<linalg::UnPackOp>();
1317 if (!unpackOp)
1318 return failure();
1319
1320 // Pack/unpack memref transformations are unsupported. The memref forms
1321 // are mainly for bufferization and scalar lowering. Other uses are not
1322 // recommended, see #225650 for details.
1323 if (!unpackOp.hasPureTensorSemantics())
1324 return failure();
1325
1326 if (!controlFn(&padOp.getSourceMutable()))
1327 return failure();
1328
1329 Location loc = padOp.getLoc();
1330 // Bail out if one of the padded dimension is a tiled one.
1331 llvm::SmallBitVector paddedDims = padOp.getPaddedDims();
1332 ArrayRef<int64_t> innerDimsPos = unpackOp.getInnerDimsPos();
1333 llvm::SmallBitVector innerDims(paddedDims.size());
1334 for (int64_t dim : innerDimsPos)
1335 innerDims.flip(Idx: dim);
1336 if (paddedDims.anyCommon(RHS: innerDims))
1337 return failure();
1338
1339 Value paddingVal = padOp.getConstantPaddingValue();
1340 if (!paddingVal)
1341 return failure();
1342
1343 // If we have `outer_dims_perms` we need to adjust the padded dimensions.
1344 ArrayRef<int64_t> outerDimsPerm = unpackOp.getOuterDimsPerm();
1345 SmallVector<OpFoldResult> lowPad = padOp.getMixedLowPad();
1346 SmallVector<OpFoldResult> highPad = padOp.getMixedHighPad();
1347 if (!outerDimsPerm.empty()) {
1348 applyPermutationToVector<OpFoldResult>(inVec&: lowPad, permutation: outerDimsPerm);
1349 applyPermutationToVector<OpFoldResult>(inVec&: highPad, permutation: outerDimsPerm);
1350 }
1351 // Add zero padding for the point loops.
1352 size_t pointLoopsSize = innerDimsPos.size();
1353 lowPad.append(NumInputs: pointLoopsSize, Elt: rewriter.getIndexAttr(value: 0));
1354 highPad.append(NumInputs: pointLoopsSize, Elt: rewriter.getIndexAttr(value: 0));
1355
1356 auto newPadOp = tensor::PadOp::create(builder&: rewriter, location: loc, /*result=*/resultType: Type(),
1357 source: unpackOp.getSource(), low: lowPad, high: highPad,
1358 constantPadValue: paddingVal, nofold: padOp.getNofold());
1359
1360 // Inject the linalg.unpack right after the packed padOp.
1361 Value outputUnPack =
1362 tensor::EmptyOp::create(builder&: rewriter, location: loc, staticShape: padOp.getResultType().getShape(),
1363 elementType: padOp.getResultType().getElementType());
1364
1365 UnPackOp replacement = linalg::UnPackOp::create(
1366 builder&: rewriter, location: loc, source: newPadOp.getResult(), dest: outputUnPack, innerDimsPos,
1367 innerTiles: unpackOp.getMixedTiles(), outerDimsPerm);
1368 rewriter.replaceOp(op: padOp, newOp: replacement);
1369 return success();
1370 }
1371
1372private:
1373 ControlPropagationFn controlFn;
1374};
1375
1376// This struct contains infomation about extract_slice dims.
1377struct SliceDimInfo {
1378 OpFoldResult offset;
1379 OpFoldResult sliceSize;
1380 OpFoldResult outputSize;
1381};
1382
1383/// Return all extract slice operands, if present, for the current
1384/// generic op.
1385static FailureOr<SmallVector<OpOperand *>>
1386getSliceOperands(GenericOp genericOp) {
1387 SmallVector<OpOperand *> sliceOperands;
1388 for (auto operand : genericOp.getDpsInputOperands()) {
1389 auto extractOp = operand->get().getDefiningOp<tensor::ExtractSliceOp>();
1390 if (!extractOp)
1391 continue;
1392 sliceOperands.push_back(Elt: operand);
1393 }
1394 if (sliceOperands.empty()) {
1395 return failure();
1396 }
1397 return sliceOperands;
1398}
1399
1400// Return a map of dims that have partial slices on them so that other operands
1401// can use this information. Also return a bool mentioning if a reduction dim
1402// has a non full slice as that can be used to fold the original extract slice.
1403static FailureOr<llvm::DenseMap<int64_t, SliceDimInfo>>
1404getPartialSliceDimInfo(GenericOp genericOp, OpOperand *sliceOperand) {
1405 tensor::ExtractSliceOp producerSliceOp =
1406 sliceOperand->get().getDefiningOp<tensor::ExtractSliceOp>();
1407 assert(producerSliceOp && "expect a valid ExtractSliceOp");
1408 llvm::DenseMap<int64_t, SliceDimInfo> partialSliceDimMap;
1409 SmallVector<OpFoldResult> offsets = producerSliceOp.getMixedOffsets();
1410 SmallVector<OpFoldResult> sizes = producerSliceOp.getMixedSizes();
1411
1412 SmallVector<OpFoldResult> shape = getAsIndexOpFoldResult(
1413 ctx: genericOp.getContext(), values: producerSliceOp.getSourceType().getShape());
1414
1415 for (auto [idx, expr] : llvm::enumerate(
1416 First: genericOp.getMatchingIndexingMap(opOperand: sliceOperand).getResults())) {
1417 // If we have a full slice in a dimension then we dont need to add it to
1418 // the partial slice map.
1419 if (isConstantIntValue(ofr: offsets[idx], value: 0) &&
1420 isEqualConstantIntOrValue(ofr1: sizes[idx], ofr2: shape[idx])) {
1421 continue;
1422 }
1423 // We only support partial slices of AffineDimExprs so bail-out if thats not
1424 // the case.
1425 if (!isa<AffineDimExpr>(Val: expr)) {
1426 return failure();
1427 }
1428 SliceDimInfo sliceDimInfo{.offset: offsets[idx], .sliceSize: sizes[idx], .outputSize: shape[idx]};
1429 int64_t dimPos = cast<AffineDimExpr>(Val: expr).getPosition();
1430 partialSliceDimMap[dimPos] = sliceDimInfo;
1431 }
1432 // Next check if the dims with partial slice info are used in non
1433 // AffineDimExpr in other operands and if they are then bail-out.
1434 for (OpOperand &operand : genericOp->getOpOperands()) {
1435 if (operand == *sliceOperand) {
1436 continue;
1437 }
1438 AffineMap IndexingMap = genericOp.getMatchingIndexingMap(opOperand: &operand);
1439 if (llvm::any_of(Range: IndexingMap.getResults(), P: [&](AffineExpr expr) {
1440 if (isa<AffineDimExpr>(Val: expr)) {
1441 return false;
1442 }
1443 WalkResult status = expr.walk(callback: [&](AffineExpr expr) {
1444 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: expr)) {
1445 if (partialSliceDimMap.contains(Val: dimExpr.getPosition())) {
1446 return WalkResult::interrupt();
1447 }
1448 }
1449 return WalkResult::advance();
1450 });
1451 if (status.wasInterrupted()) {
1452 return true;
1453 }
1454 return false;
1455 })) {
1456 return failure();
1457 }
1458 }
1459 return partialSliceDimMap;
1460}
1461
1462static FailureOr<std::tuple<GenericOp, Value>>
1463pushDownExtractSliceOpThroughGenericOp(RewriterBase &rewriter,
1464 GenericOp genericOp,
1465 ControlPropagationFn controlFn) {
1466 if (genericOp.getNumResults() != 1)
1467 return rewriter.notifyMatchFailure(
1468 arg&: genericOp, msg: "propagation through multi-result generic is unsupported.");
1469 if (hasGatherSemantics(genericOp))
1470 return rewriter.notifyMatchFailure(
1471 arg&: genericOp,
1472 msg: "propagation through generic with gather semantics is unsupported.");
1473 // Collect the sliced operand, if present.
1474 auto maybeSliceOperands = getSliceOperands(genericOp);
1475 if (failed(Result: maybeSliceOperands))
1476 return failure();
1477 SmallVector<OpOperand *> sliceOperands = *maybeSliceOperands;
1478 OpOperand *sliceOperand;
1479
1480 bool foundValidOperand = false;
1481 for (auto currSliceOperand : sliceOperands) {
1482 if (controlFn(currSliceOperand)) {
1483 sliceOperand = currSliceOperand;
1484 foundValidOperand = true;
1485 break;
1486 }
1487 }
1488 if (!foundValidOperand) {
1489 return failure();
1490 }
1491 unsigned OperandIndex = sliceOperand->getOperandNumber();
1492
1493 tensor::ExtractSliceOp producerSliceOp =
1494 sliceOperand->get().getDefiningOp<tensor::ExtractSliceOp>();
1495 assert(producerSliceOp && "expect a valid ExtractSliceOp");
1496
1497 if (producerSliceOp.getSource().getType().getRank() !=
1498 producerSliceOp.getResult().getType().getRank()) {
1499 return rewriter.notifyMatchFailure(
1500 arg&: genericOp,
1501 msg: "propagation of rank-reducing extract slice is unsupported.");
1502 }
1503
1504 SmallVector<OpFoldResult> strides = producerSliceOp.getMixedStrides();
1505 if (!areAllConstantIntValue(ofrs: strides, value: 1))
1506 return rewriter.notifyMatchFailure(
1507 arg&: genericOp, msg: "propagation of strided extract slice is unsupported.");
1508
1509 // check if we can support the propagation of this extractSlice
1510 // through the generic op and if so return the dimensions that
1511
1512 auto maybePartialSliceDimMap =
1513 getPartialSliceDimInfo(genericOp, sliceOperand);
1514
1515 if (failed(Result: maybePartialSliceDimMap)) {
1516 return failure();
1517 }
1518
1519 auto partialSliceDimMap = *maybePartialSliceDimMap;
1520
1521 SmallVector<utils::IteratorType> iterators =
1522 genericOp.getIteratorTypesArray();
1523 bool hasPartialReductionDimSlice =
1524 llvm::any_of(Range&: partialSliceDimMap, P: [&](const auto &slice) {
1525 int64_t sliceDim = slice.first;
1526 return iterators[sliceDim] == utils::IteratorType::reduction;
1527 });
1528
1529 // Store the padding information as (dimPos, lowPad, highPad, PaddedShape).
1530 Location loc = genericOp->getLoc();
1531 AffineExpr dim0, dim1;
1532 bindDims(ctx: rewriter.getContext(), exprs&: dim0, exprs&: dim1);
1533 auto subMap = AffineMap::get(dimCount: 2, symbolCount: 0, result: {dim0 - dim1});
1534 auto sub = [&](OpFoldResult v1, OpFoldResult v2) {
1535 return affine::makeComposedFoldedAffineApply(b&: rewriter, loc, map: subMap,
1536 operands: {v1, v2});
1537 };
1538
1539 MLIRContext *ctx = genericOp.getContext();
1540 SmallVector<Value> paddedInputs;
1541 for (auto [idx, operand] : llvm::enumerate(First: genericOp.getDpsInputOperands())) {
1542 if (idx == OperandIndex && !hasPartialReductionDimSlice) {
1543 paddedInputs.push_back(Elt: producerSliceOp.getSource());
1544 continue;
1545 }
1546 AffineMap IndexingMap = genericOp.getMatchingIndexingMap(opOperand: operand);
1547 if (IndexingMap.getNumResults() == 0) {
1548 paddedInputs.push_back(Elt: operand->get());
1549 continue;
1550 }
1551 SmallVector<OpFoldResult> operandLowPads(IndexingMap.getNumResults(),
1552 getAsIndexOpFoldResult(ctx, val: 0));
1553 SmallVector<OpFoldResult> operandHighPads(IndexingMap.getNumResults(),
1554 getAsIndexOpFoldResult(ctx, val: 0));
1555 for (auto [idx, expr] : llvm::enumerate(First: IndexingMap.getResults())) {
1556 if (!isa<AffineDimExpr>(Val: expr)) {
1557 continue;
1558 }
1559 AffineDimExpr dimExpr = cast<AffineDimExpr>(Val: expr);
1560 if (!partialSliceDimMap.contains(Val: dimExpr.getPosition())) {
1561 continue;
1562 }
1563 SliceDimInfo sliceDimInfo = partialSliceDimMap[dimExpr.getPosition()];
1564 operandLowPads[idx] = sliceDimInfo.offset;
1565 operandHighPads[idx] =
1566 sub(sub(sliceDimInfo.outputSize, sliceDimInfo.offset),
1567 sliceDimInfo.sliceSize);
1568 }
1569 auto paddingValue = ub::PoisonOp::create(
1570 builder&: rewriter, location: loc, result: getElementTypeOrSelf(type: operand->get().getType()));
1571 auto paddedOperand = tensor::PadOp::create(
1572 builder&: rewriter, location: loc, resultType: Type(), source: operand->get(), low: operandLowPads, high: operandHighPads,
1573 constantPadValue: paddingValue, /*nofold=*/false);
1574 paddedInputs.push_back(Elt: paddedOperand);
1575 }
1576 AffineMap outputIndexingMap =
1577 genericOp.getMatchingIndexingMap(opOperand: genericOp.getDpsInitOperand(i: 0));
1578
1579 auto outputShapeType =
1580 llvm::cast<ShapedType>(Val: genericOp.getDpsInitOperand(i: 0)->get().getType());
1581 SmallVector<OpFoldResult> OutputShape = llvm::map_to_vector(
1582 C: outputShapeType.getShape(),
1583 F: [&](int64_t sz) -> OpFoldResult { return rewriter.getIndexAttr(value: sz); });
1584 SmallVector<OpFoldResult> newSizes = OutputShape;
1585 SmallVector<OpFoldResult> outputLowPads(outputIndexingMap.getNumResults(),
1586 getAsIndexOpFoldResult(ctx, val: 0));
1587 SmallVector<OpFoldResult> outputHighPads(outputIndexingMap.getNumResults(),
1588 getAsIndexOpFoldResult(ctx, val: 0));
1589 SmallVector<OpFoldResult> newStrides(outputIndexingMap.getNumResults(),
1590 getAsIndexOpFoldResult(ctx, val: 1));
1591 for (auto [idx, expr] : llvm::enumerate(First: outputIndexingMap.getResults())) {
1592 if (!isa<AffineDimExpr>(Val: expr)) {
1593 continue;
1594 }
1595 AffineDimExpr dimExpr = cast<AffineDimExpr>(Val: expr);
1596 if (!partialSliceDimMap.contains(Val: dimExpr.getPosition())) {
1597 continue;
1598 }
1599 SliceDimInfo sliceDimInfo = partialSliceDimMap[dimExpr.getPosition()];
1600 outputLowPads[idx] = sliceDimInfo.offset;
1601 outputHighPads[idx] = sub(sub(sliceDimInfo.outputSize, sliceDimInfo.offset),
1602 sliceDimInfo.sliceSize);
1603 OutputShape[idx] = sliceDimInfo.outputSize;
1604 newSizes[idx] = sliceDimInfo.sliceSize;
1605 }
1606 Value newPadOutput;
1607 auto outputElType =
1608 getElementTypeOrSelf(type: genericOp.getDpsInits()[0].getType());
1609 if (isGenericOutsNotUsed(genericOp)) {
1610 newPadOutput =
1611 tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes: OutputShape, elementType: outputElType);
1612 } else {
1613 auto paddingValue = ub::PoisonOp::create(builder&: rewriter, location: loc, result: outputElType);
1614 newPadOutput = tensor::PadOp::create(
1615 builder&: rewriter, location: loc, resultType: Type(), source: genericOp.getDpsInits()[0], low: outputLowPads,
1616 high: outputHighPads, constantPadValue: paddingValue, /*nofold=*/false);
1617 }
1618
1619 auto newGenericOp = linalg::GenericOp::create(
1620 builder&: rewriter, location: loc, resultTensorTypes: newPadOutput.getType(), inputs: paddedInputs, outputs: {newPadOutput},
1621 indexingMaps: genericOp.getIndexingMapsArray(), iteratorTypes: genericOp.getIteratorTypesArray(),
1622 /*bodyBuild=*/odsArg5: nullptr, attributes: linalg::getPrunedAttributeList(op: genericOp));
1623 rewriter.cloneRegionBefore(region&: genericOp.getRegion(), parent&: newGenericOp.getRegion(),
1624 before: newGenericOp.getRegion().begin());
1625
1626 auto extractOp = tensor::ExtractSliceOp::create(
1627 builder&: rewriter, location: loc,
1628 source: newGenericOp.getTiedOpResult(opOperand: newGenericOp.getDpsInitOperand(i: 0)),
1629 offsets: outputLowPads, sizes: newSizes, strides: newStrides);
1630 Value extractRes = extractOp.getResult();
1631
1632 return std::make_tuple(args&: newGenericOp, args&: extractRes);
1633}
1634
1635class PushDownExtractSliceOpThroughGenericOp final
1636 : public OpRewritePattern<GenericOp> {
1637public:
1638 PushDownExtractSliceOpThroughGenericOp(MLIRContext *context,
1639 ControlPropagationFn fun)
1640 : OpRewritePattern<GenericOp>(context), controlFn(std::move(fun)) {}
1641
1642 LogicalResult matchAndRewrite(GenericOp genericOp,
1643 PatternRewriter &rewriter) const override {
1644 auto genericAndRepl =
1645 pushDownExtractSliceOpThroughGenericOp(rewriter, genericOp, controlFn);
1646 if (failed(Result: genericAndRepl))
1647 return failure();
1648 rewriter.replaceOp(op: genericOp, newValues: std::get<1>(t&: *genericAndRepl));
1649 return success();
1650 }
1651
1652private:
1653 ControlPropagationFn controlFn;
1654};
1655
1656} // namespace
1657
1658void mlir::linalg::populateDataLayoutPropagationPatterns(
1659 RewritePatternSet &patterns,
1660 const ControlPropagationFn &controlPackUnPackPropagation,
1661 bool PoisonPaddingOk) {
1662 patterns.insert<BubbleUpPackThroughPadOp, BubbleUpPackOpThroughReshapeOp,
1663 PushDownUnPackThroughPadOp, PushDownUnPackOpThroughReshapeOp>(
1664 arg: patterns.getContext(), args: controlPackUnPackPropagation);
1665 patterns.insert<BubbleUpPackOpThroughGenericOpPattern,
1666 PushDownUnPackOpThroughGenericOp>(
1667 arg: patterns.getContext(), args: controlPackUnPackPropagation, args&: PoisonPaddingOk);
1668}
1669
1670void mlir::linalg::populateExtractSliceSinkingPatterns(
1671 RewritePatternSet &patterns,
1672 const ControlPropagationFn &controlPackUnPackPropagation) {
1673 patterns.insert<PushDownExtractSliceOpThroughGenericOp>(
1674 arg: patterns.getContext(), args: controlPackUnPackPropagation);
1675}
1676