1//===- ElementwiseOpFusion.cpp - Implementation of linalg Fusion ---------===///
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// This file implements the linalg dialect Fusion on tensors operations pass.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/Linalg/Passes.h"
14
15#include "mlir/Dialect/Affine/IR/AffineOps.h"
16#include "mlir/Dialect/Arith/IR/Arith.h"
17#include "mlir/Dialect/Arith/Utils/Utils.h"
18#include "mlir/Dialect/Linalg/IR/Linalg.h"
19#include "mlir/Dialect/Linalg/Transforms/Transforms.h"
20#include "mlir/Dialect/Linalg/Utils/Utils.h"
21#include "mlir/Dialect/SparseTensor/IR/SparseTensor.h"
22#include "mlir/Dialect/Tensor/Transforms/Transforms.h"
23#include "mlir/IR/AffineExpr.h"
24#include "mlir/IR/AffineMap.h"
25#include "mlir/IR/Matchers.h"
26#include "mlir/IR/PatternMatch.h"
27#include "mlir/Support/LLVM.h"
28#include "mlir/Transforms/GreedyPatternRewriteDriver.h"
29#include "mlir/Transforms/RegionUtils.h"
30#include "llvm/ADT/SmallVectorExtras.h"
31#include <optional>
32#include <utility>
33
34namespace mlir {
35#define GEN_PASS_DEF_LINALGELEMENTWISEOPFUSIONPASS
36#include "mlir/Dialect/Linalg/Passes.h.inc"
37} // namespace mlir
38
39using namespace mlir;
40using namespace mlir::linalg;
41
42//===---------------------------------------------------------------------===//
43// Methods and patterns that fuse elementwise `linalg.generic` operations.
44//===---------------------------------------------------------------------===//
45
46/// Append to `fusedOpIndexingMapAttrs` the indexing maps for the operands of
47/// the `producer` to use in the fused operation given the indexing map of the
48/// result of the producer in the consumer.
49static AffineMap getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp(
50 OpOperand *producerOpOperand, AffineMap producerResultIndexMap,
51 AffineMap fusedConsumerArgIndexMap) {
52 // The indexing map in the consumer op (fusedConsumerArgIndexMap) is a map
53 // from consumer loop -> consumer arg tensor index/producer result tensor
54 // index. The fused loop is same as the consumer loop. For each producer arg
55 // the indexing map to be computed is a map from consumer loop -> producer
56 // arg tensor index.
57 // producerResultIndexMap is a map from producer loop -> tensor index.
58 // Compute the inverse to get map from tensor index -> producer loop.
59 // The inverse is a map from producer result tensor index -> producer loop.
60 AffineMap invProducerResultIndexMap =
61 inversePermutation(map: producerResultIndexMap);
62 assert(invProducerResultIndexMap &&
63 "expected producer result indexing map to be invertible");
64
65 LinalgOp producer = cast<LinalgOp>(Val: producerOpOperand->getOwner());
66 // argMap is a map from producer loop -> producer arg tensor index.
67 AffineMap argMap = producer.getMatchingIndexingMap(opOperand: producerOpOperand);
68
69 // Compose argMap with invProducerResultIndexMap to get a map from
70 // producer result tensor index -> producer arg tensor index.
71 AffineMap t1 = argMap.compose(map: invProducerResultIndexMap);
72
73 // Compose t1 with fusedConsumerArgIndexMap gives an indexing map from
74 // consumer loop/ fused loop -> producer arg tensor index.
75 return t1.compose(map: fusedConsumerArgIndexMap);
76}
77
78// Checks if the given operand can be dropped, and the remaining operands
79// of the fused producer & consumer after the fusion can still compute the
80// bounds of the op.
81static bool isOpOperandCanBeDroppedAfterFusedLinalgs(
82 GenericOp producer, GenericOp consumer,
83 ArrayRef<OpOperand *> opOperandsToIgnore) {
84 SmallVector<AffineMap> indexingMaps;
85
86 SmallVector<GenericOp> ops = {producer, consumer};
87 for (auto &op : ops) {
88 for (auto &opOperand : op->getOpOperands()) {
89 if (llvm::is_contained(Range&: opOperandsToIgnore, Element: &opOperand)) {
90 continue;
91 }
92 indexingMaps.push_back(Elt: op.getMatchingIndexingMap(opOperand: &opOperand));
93 }
94 }
95 if (indexingMaps.empty()) {
96 // If there are no indexing maps, the operand can only be dropped
97 // if neither op has loops.
98 return producer.getNumLoops() == 0 && consumer.getNumLoops() == 0;
99 }
100
101 // The concatanation of the remained indexing maps must be invertible, so
102 // the bounds of the op can be still computed after dropping the selected
103 // operand. inversePermutation returns an empty AffineMap in case the
104 // concatanated indexing maps are not invertible.
105 return inversePermutation(map: concatAffineMaps(
106 maps: indexingMaps, context: producer.getContext())) != AffineMap();
107}
108
109/// Returns a set of indices of the producer's results which would
110/// be preserved after the fusion.
111/// * There is a chance that the implementation of the transformation does not
112/// agree with the result of this method. This function gives a prediction based
113/// on an optimized fusion.
114llvm::SmallDenseSet<int> mlir::linalg::getPreservedProducerResults(
115 GenericOp producer, GenericOp consumer, OpOperand *fusedOperand) {
116 llvm::SmallDenseSet<int> preservedProducerResults;
117 llvm::SmallVector<OpOperand *> opOperandsToIgnore;
118
119 // The fusedOperand will be removed during the fusion
120 opOperandsToIgnore.emplace_back(Args&: fusedOperand);
121
122 for (const auto &producerResult : llvm::enumerate(First: producer->getResults())) {
123 auto *outputOperand = producer.getDpsInitOperand(i: producerResult.index());
124 opOperandsToIgnore.emplace_back(Args&: outputOperand);
125 if (producer.payloadUsesValueFromOperand(opOperand: outputOperand) ||
126 !isOpOperandCanBeDroppedAfterFusedLinalgs(producer, consumer,
127 opOperandsToIgnore) ||
128 llvm::any_of(Range: producerResult.value().getUsers(), P: [&](Operation *user) {
129 return user != consumer.getOperation();
130 })) {
131 preservedProducerResults.insert(V: producerResult.index());
132
133 // In case the operand can't be dropped
134 (void)opOperandsToIgnore.pop_back_val();
135 }
136 }
137 return preservedProducerResults;
138}
139
140/// Conditions for elementwise fusion of generic operations.
141bool mlir::linalg::areElementwiseOpsFusable(OpOperand *fusedOperand) {
142 if (!fusedOperand)
143 return false;
144
145 auto producer = fusedOperand->get().getDefiningOp<GenericOp>();
146 auto consumer = dyn_cast<GenericOp>(Val: fusedOperand->getOwner());
147
148 // Check producer and consumer are generic ops.
149 if (!producer || !consumer)
150 return false;
151
152 // Consumer can have mixed semantics, just check operand itself has tensor
153 // type. Producer must have full tensor semantics to avoid potential
154 // aliasing between producer and consumer memrefs.
155 if (!producer.hasPureTensorSemantics() ||
156 !isa<RankedTensorType>(Val: fusedOperand->get().getType()))
157 return false;
158
159 // Verify that
160 // - the producer has all "parallel" iterator type.
161 if (producer.getNumParallelLoops() != producer.getNumLoops())
162 return false;
163
164 // Only allow fusing the producer of an input operand for now.
165 // TODO: allow fusing the producer of an output operand.
166 if (!consumer.isDpsInput(opOperand: fusedOperand))
167 return false;
168
169 // Get the consumer index map. The number of results of the consumer index
170 // map must match the number of loops of the producer.
171 AffineMap consumerIndexMap = consumer.getMatchingIndexingMap(opOperand: fusedOperand);
172 if (consumerIndexMap.getNumResults() != producer.getNumLoops())
173 return false;
174
175 // Finally the index_map for the result must be invertible. For now just
176 // verify it is a permutation.
177 auto producerResult = cast<OpResult>(Val: fusedOperand->get());
178 AffineMap producerResultIndexMap =
179 producer.getIndexingMapMatchingResult(result: producerResult);
180 if (!producerResultIndexMap.isPermutation())
181 return false;
182
183 // Ensure that the fusion does not remove size information required to
184 // get the loop bounds. For non-reduction generics, this is trivially the
185 // case due to the output operand. For reductions, we need to check that after
186 // the fusion, each loop dimension has at least one input that defines it.
187 if ((consumer.getNumReductionLoops())) {
188 BitVector coveredDims(consumer.getNumLoops(), false);
189
190 auto addToCoveredDims = [&](AffineMap map) {
191 for (auto result : map.getResults())
192 if (auto dimExpr = dyn_cast<AffineDimExpr>(Val&: result))
193 coveredDims[dimExpr.getPosition()] = true;
194 };
195
196 for (auto pair :
197 llvm::zip(t: consumer->getOperands(), u: consumer.getIndexingMapsArray())) {
198 Value operand = std::get<0>(t&: pair);
199 if (operand == fusedOperand->get())
200 continue;
201 AffineMap operandMap = std::get<1>(t&: pair);
202 addToCoveredDims(operandMap);
203 }
204
205 for (OpOperand *operand : producer.getDpsInputOperands()) {
206 AffineMap newIndexingMap =
207 getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp(
208 producerOpOperand: operand, producerResultIndexMap, fusedConsumerArgIndexMap: consumerIndexMap);
209 addToCoveredDims(newIndexingMap);
210 }
211 if (!coveredDims.all())
212 return false;
213 }
214
215 return true;
216}
217
218/// Generate the region of the fused tensor operation. The region of the fused
219/// op must be empty.
220static void generateFusedElementwiseOpRegion(
221 RewriterBase &rewriter, GenericOp fusedOp,
222 AffineMap consumerToProducerLoopsMap, OpOperand *fusedOperand,
223 unsigned nloops, llvm::SmallDenseSet<int> &preservedProducerResults) {
224 auto producer = cast<GenericOp>(Val: fusedOperand->get().getDefiningOp());
225 auto consumer = cast<GenericOp>(Val: fusedOperand->getOwner());
226 // Build the region of the fused op.
227 Block &producerBlock = producer->getRegion(index: 0).front();
228 Block &consumerBlock = consumer->getRegion(index: 0).front();
229 OpBuilder::InsertionGuard guard(rewriter);
230 Block *fusedBlock = rewriter.createBlock(parent: &fusedOp.getRegion());
231 IRMapping mapper;
232
233 // 2. Add an index operation for every fused loop dimension and use the
234 // `consumerToProducerLoopsMap` to map the producer indices.
235 if (producer.hasIndexSemantics()) {
236 // Add an index operation for every fused loop dimension.
237 unsigned numFusedOpLoops = fusedOp.getNumLoops();
238 SmallVector<Value> fusedIndices;
239 fusedIndices.reserve(N: numFusedOpLoops);
240 llvm::transform(Range: llvm::seq<uint64_t>(Begin: 0, End: numFusedOpLoops),
241 d_first: std::back_inserter(x&: fusedIndices), F: [&](uint64_t dim) {
242 return IndexOp::create(builder&: rewriter, location: producer.getLoc(), dim);
243 });
244 for (IndexOp indexOp :
245 llvm::make_early_inc_range(Range: producerBlock.getOps<IndexOp>())) {
246 Value newIndex = affine::AffineApplyOp::create(
247 builder&: rewriter, location: producer.getLoc(),
248 map: consumerToProducerLoopsMap.getSubMap(resultPos: indexOp.getDim()), mapOperands: fusedIndices);
249 mapper.map(from: indexOp.getResult(), to: newIndex);
250 }
251 }
252 // TODO: allow fusing the producer of an output operand.
253 assert(consumer.isDpsInput(fusedOperand) &&
254 "expected producer of input operand");
255 // 3. Consumer input operands up to consumerIdx (exclusive).
256 for (BlockArgument bbArg : consumerBlock.getArguments().take_front(
257 N: fusedOperand->getOperandNumber())) // input assumption.
258 mapper.map(from: bbArg, to: fusedBlock->addArgument(type: bbArg.getType(), loc: bbArg.getLoc()));
259
260 // Replacing consumerIdx requires getting the cloned, yielded, value from
261 // the (cloned) producer block. This happens in step 9.
262
263 // 4. Splice in producer's input operands.
264 for (BlockArgument bbArg :
265 producerBlock.getArguments().take_front(N: producer.getNumDpsInputs()))
266 mapper.map(from: bbArg, to: fusedBlock->addArgument(type: bbArg.getType(), loc: bbArg.getLoc()));
267
268 // 5. Remaining consumer's input operands (drop past index `consumerIdx`).
269 for (BlockArgument bbArg :
270 consumerBlock.getArguments()
271 .take_front(N: consumer.getNumDpsInputs())
272 .drop_front(N: fusedOperand->getOperandNumber() + 1))
273 mapper.map(from: bbArg, to: fusedBlock->addArgument(type: bbArg.getType(), loc: bbArg.getLoc()));
274
275 // 6. All of the producer's output operands
276 for (const auto &bbArg : llvm::enumerate(
277 First: producerBlock.getArguments().take_back(N: producer.getNumDpsInits()))) {
278 if (!preservedProducerResults.count(V: bbArg.index()))
279 continue;
280 mapper.map(from: bbArg.value(), to: fusedBlock->addArgument(type: bbArg.value().getType(),
281 loc: bbArg.value().getLoc()));
282 }
283
284 // 7. All of consumer's output operands.
285 for (BlockArgument bbArg :
286 consumerBlock.getArguments().take_back(N: consumer.getNumDpsInits()))
287 mapper.map(from: bbArg, to: fusedBlock->addArgument(type: bbArg.getType(), loc: bbArg.getLoc()));
288
289 // 8. Clone all producer operations except for the yield and index operations
290 // to the fused operation.
291 for (auto &op : producerBlock.without_terminator()) {
292 if (!isa<IndexOp>(Val: op))
293 rewriter.clone(op, mapper);
294 }
295 // 9. Now we can map the consumerBlock's `consumerIdx` block argument. Just
296 // forward the yield operand.
297 auto producerYieldOp = cast<linalg::YieldOp>(Val: producerBlock.getTerminator());
298 unsigned producerResultNumber =
299 cast<OpResult>(Val: fusedOperand->get()).getResultNumber();
300 Value replacement =
301 mapper.lookupOrDefault(from: producerYieldOp.getOperand(i: producerResultNumber));
302
303 // Sanity checks, if replacement is not already in the mapper then it must be
304 // produced outside.
305 if (replacement == producerYieldOp.getOperand(i: producerResultNumber)) {
306 if (auto bb = dyn_cast<BlockArgument>(Val&: replacement))
307 assert(bb.getOwner() != &producerBlock &&
308 "yielded block argument must have been mapped");
309 else
310 assert(!producer->isAncestor(replacement.getDefiningOp()) &&
311 "yielded value must have been mapped");
312 }
313 mapper.map(from: consumerBlock.getArgument(i: fusedOperand->getOperandNumber()),
314 to: replacement);
315 // 10. Clone operations from the consumer to the fused op.
316 for (auto &op : consumerBlock.without_terminator())
317 rewriter.clone(op, mapper);
318
319 // 11. Include the final yield (which is the remapped values for all the
320 // yield)
321 auto consumerYieldOp = cast<linalg::YieldOp>(Val: consumerBlock.getTerminator());
322 SmallVector<Value> fusedYieldValues;
323 fusedYieldValues.reserve(N: producerYieldOp.getNumOperands() +
324 consumerYieldOp.getNumOperands());
325 for (const auto &producerYieldVal :
326 llvm::enumerate(First: producerYieldOp.getOperands())) {
327 if (preservedProducerResults.count(V: producerYieldVal.index()))
328 fusedYieldValues.push_back(
329 Elt: mapper.lookupOrDefault(from: producerYieldVal.value()));
330 }
331 for (auto consumerYieldVal : consumerYieldOp.getOperands())
332 fusedYieldValues.push_back(Elt: mapper.lookupOrDefault(from: consumerYieldVal));
333 YieldOp::create(builder&: rewriter, location: fusedOp.getLoc(), values: fusedYieldValues);
334
335 // Sanity checks.
336 assert(fusedBlock->getNumArguments() == fusedOp.getNumOperands() &&
337 "Ill-formed GenericOp region");
338}
339
340FailureOr<mlir::linalg::ElementwiseOpFusionResult>
341mlir::linalg::fuseElementwiseOps(RewriterBase &rewriter,
342 OpOperand *fusedOperand) {
343 assert(areElementwiseOpsFusable(fusedOperand) &&
344 "expected elementwise operation pre-conditions to pass");
345 auto producerResult = cast<OpResult>(Val: fusedOperand->get());
346 auto producer = cast<GenericOp>(Val: producerResult.getOwner());
347 auto consumer = cast<GenericOp>(Val: fusedOperand->getOwner());
348 // TODO: allow fusing the producer of an output operand.
349 assert(consumer.isDpsInput(fusedOperand) &&
350 "expected producer of input operand");
351 /// Find the results of the producer that have uses outside of the consumer,
352 /// after the fusion.
353 llvm::SmallDenseSet<int> preservedProducerResults =
354 mlir::linalg::getPreservedProducerResults(producer, consumer,
355 fusedOperand);
356
357 // Compute the fused operands list and indexing maps.
358 SmallVector<Value> fusedInputOperands, fusedOutputOperands;
359 SmallVector<Type> fusedResultTypes;
360 SmallVector<AffineMap> fusedIndexMaps;
361 fusedInputOperands.reserve(N: producer.getNumDpsInputs() +
362 consumer.getNumDpsInputs());
363 fusedOutputOperands.reserve(N: preservedProducerResults.size() +
364 consumer.getNumDpsInits());
365 fusedResultTypes.reserve(N: preservedProducerResults.size() +
366 consumer.getNumDpsInits());
367 fusedIndexMaps.reserve(N: producer->getNumOperands() +
368 consumer->getNumOperands());
369 // In the following, numbering matches that of `generateFusedTensorOpRegion`.
370 // 3. Consumer input operands/maps up to consumerIdx (exclusive).
371 auto consumerInputs = consumer.getDpsInputOperands();
372 auto *it = llvm::find_if(Range&: consumerInputs, P: [&](OpOperand *operand) {
373 return operand == fusedOperand;
374 });
375 assert(it != consumerInputs.end() && "expected to find the consumer operand");
376 for (OpOperand *opOperand : llvm::make_range(x: consumerInputs.begin(), y: it)) {
377 fusedInputOperands.push_back(Elt: opOperand->get());
378 fusedIndexMaps.push_back(Elt: consumer.getMatchingIndexingMap(opOperand));
379 }
380 // 4. Splice in producer's input operands/maps.
381 AffineMap producerResultIndexMap =
382 producer.getIndexingMapMatchingResult(result: producerResult);
383 for (OpOperand *opOperand : producer.getDpsInputOperands()) {
384 fusedInputOperands.push_back(Elt: opOperand->get());
385 // Compute indexing maps for the producer args in the fused operation.
386 AffineMap map = getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp(
387 producerOpOperand: opOperand, producerResultIndexMap,
388 fusedConsumerArgIndexMap: consumer.getMatchingIndexingMap(opOperand: fusedOperand));
389 fusedIndexMaps.push_back(Elt: map);
390 }
391 // 5. Remaining consumer's input operands/maps (drop past index
392 // `consumerIdx`).
393 for (OpOperand *opOperand :
394 llvm::make_range(x: std::next(x: it), y: consumerInputs.end())) {
395 fusedInputOperands.push_back(Elt: opOperand->get());
396 fusedIndexMaps.push_back(Elt: consumer.getMatchingIndexingMap(opOperand));
397 }
398
399 // 6. Collect all of the producer outputs.
400 for (const auto &opOperand : llvm::enumerate(First: producer.getDpsInitsMutable())) {
401 if (!preservedProducerResults.count(V: opOperand.index()))
402 continue;
403
404 fusedOutputOperands.push_back(Elt: opOperand.value().get());
405 AffineMap map = getIndexingMapOfProducerOperandsInCoordinatesOfFusedOp(
406 producerOpOperand: &opOperand.value(), producerResultIndexMap,
407 fusedConsumerArgIndexMap: consumer.getMatchingIndexingMap(opOperand: fusedOperand));
408 fusedIndexMaps.push_back(Elt: map);
409 fusedResultTypes.push_back(Elt: opOperand.value().get().getType());
410 }
411
412 // 7. All of consumer's output operands (skip operands: added by the builder).
413 for (OpOperand &opOperand : consumer.getDpsInitsMutable()) {
414 fusedOutputOperands.push_back(Elt: opOperand.get());
415 fusedIndexMaps.push_back(Elt: consumer.getMatchingIndexingMap(opOperand: &opOperand));
416 Type resultType = opOperand.get().getType();
417 if (!isa<MemRefType>(Val: resultType))
418 fusedResultTypes.push_back(Elt: resultType);
419 }
420
421 // Generate the fused op.
422 auto fusedOp = GenericOp::create(
423 builder&: rewriter, location: consumer.getLoc(), result_tensors: fusedResultTypes, inputs: fusedInputOperands,
424 outputs: fusedOutputOperands, indexing_maps: rewriter.getAffineMapArrayAttr(values: fusedIndexMaps),
425 iterator_types: consumer.getIteratorTypes(),
426 /*doc=*/nullptr,
427 /*library_call=*/nullptr);
428 if (!fusedOp.getShapesToLoopsMap()) {
429 // Fused op has invalid indexing maps. Typically this means something is off
430 // in the input, but going ahead here would result in verification errors.
431 // So cleanup and abort.
432 rewriter.eraseOp(op: fusedOp);
433 return rewriter.notifyMatchFailure(
434 arg&: fusedOp, msg: "fused op failed loop bound computation check");
435 }
436
437 // Construct an AffineMap from consumer loops to producer loops.
438 // consumer loop -> tensor index
439 AffineMap consumerResultIndexMap =
440 consumer.getMatchingIndexingMap(opOperand: fusedOperand);
441 // tensor index -> producer loop
442 AffineMap invProducerResultIndexMap =
443 inversePermutation(map: producerResultIndexMap);
444 assert(invProducerResultIndexMap &&
445 "expected producer result indexig map to be invertible");
446 // consumer loop -> producer loop
447 AffineMap consumerToProducerLoopsMap =
448 invProducerResultIndexMap.compose(map: consumerResultIndexMap);
449
450 generateFusedElementwiseOpRegion(
451 rewriter, fusedOp, consumerToProducerLoopsMap, fusedOperand,
452 nloops: consumer.getNumLoops(), preservedProducerResults);
453 ElementwiseOpFusionResult result;
454 result.fusedOp = fusedOp;
455 int resultNum = 0;
456 for (auto [index, producerResult] : llvm::enumerate(First: producer->getResults()))
457 if (preservedProducerResults.count(V: index))
458 result.replacements[producerResult] = fusedOp->getResult(idx: resultNum++);
459 for (auto consumerResult : consumer->getResults())
460 result.replacements[consumerResult] = fusedOp->getResult(idx: resultNum++);
461 return result;
462}
463
464namespace {
465/// Patterns to fuse a generic op, with the producer of its operands.
466class FuseElementwiseOps : public OpRewritePattern<GenericOp> {
467public:
468 FuseElementwiseOps(MLIRContext *context, ControlFusionFn fun,
469 PatternBenefit benefit = 1)
470 : OpRewritePattern<GenericOp>(context, benefit),
471 controlFn(std::move(fun)) {}
472
473 LogicalResult matchAndRewrite(GenericOp genericOp,
474 PatternRewriter &rewriter) const override {
475 // Find the first operand that is defined by another generic op on tensors.
476 for (OpOperand &opOperand : genericOp->getOpOperands()) {
477 if (!areElementwiseOpsFusable(fusedOperand: &opOperand))
478 continue;
479 if (!controlFn(&opOperand))
480 continue;
481
482 Operation *producer = opOperand.get().getDefiningOp();
483
484 // Find the producer of the operand.
485 FailureOr<ElementwiseOpFusionResult> fusionResult =
486 fuseElementwiseOps(rewriter, fusedOperand: &opOperand);
487 if (failed(Result: fusionResult))
488 return rewriter.notifyMatchFailure(arg&: genericOp, msg: "fusion failed");
489
490 // Perform the fusion.
491 for (auto [origVal, replacement] : fusionResult->replacements) {
492 rewriter.replaceUsesWithIf(from: origVal, to: replacement, functor: [&](OpOperand &use) {
493 // Only replace consumer uses.
494 return use.get().getDefiningOp() != producer;
495 });
496 }
497 rewriter.eraseOp(op: genericOp);
498 return success();
499 }
500 return failure();
501 }
502
503private:
504 ControlFusionFn controlFn;
505};
506
507/// Split an elementwise operation at the boundaries of its `tensor.concat`
508/// inputs. This exposes the producers of the concat inputs to the elementwise
509/// fusion patterns.
510///
511/// elementwise(concat(x0, x1), concat(y0, y1))
512///
513/// becomes
514///
515/// concat(elementwise(x0, y0), elementwise(x1, y1))
516///
517/// This pattern is intentionally expressed on `linalg.generic`: tensor
518/// elementwise operations such as `arith.addf` are converted to that form by
519/// `-convert-elementwise-to-linalg`, before this pattern runs as a preamble to
520/// Linalg elementwise fusion.
521///
522/// A partition is one input of a concat, viewed as a contiguous interval of
523/// the concat dimension. All concat inputs must have matching partitions: the
524/// same number of partitions with the same static size at each index.
525///
526/// All concat operands must partition the same iteration-space dimension into
527/// the same statically-sized pieces. Inputs that do not use that iteration
528/// dimension (for example, broadcast inputs) can be shared by all pieces.
529class SplitElementwiseOpWithConcatInputs : public OpRewritePattern<GenericOp> {
530public:
531 using OpRewritePattern<GenericOp>::OpRewritePattern;
532
533 LogicalResult matchAndRewrite(GenericOp genericOp,
534 PatternRewriter &rewriter) const override {
535 if (!genericOp.hasPureTensorSemantics() || !isElementwise(op: genericOp) ||
536 genericOp.hasIndexSemantics())
537 return failure();
538
539 SmallVector<tensor::ConcatOp> concatOps(genericOp.getNumDpsInputs());
540 SmallVector<OpOperand *> nonConcatInputs;
541 std::optional<unsigned> splitLoopDim;
542 // Now we limit the concat ops to have the same number of inputs for
543 // simplicity.
544 // TODO: technically, elementwise(concat(x0, x1), concat(y0, y1, y2)) ->
545 // concat(elementwise(...), elementwise(...), elementwise(...)) may be
546 // fine too. But that may require we create new slices, which might be
547 // more complex.
548 // The size in the concat dimension of different inputs. For example,
549 //
550 // x0: tensor<2x3xf32>
551 // x1: tensor<2x4xf32>
552 // x: tensor<2x7xf32>
553 // %x = tensor.concat dim(1) %x0, %x1
554 //
555 // The partition sizes in this case are [3, 4]. Same as above, we limit the
556 // partition sizes to be the same for different concat ops.
557 SmallVector<SmallVector<int64_t>> partitionSizes;
558
559 for (auto [index, operand] :
560 llvm::enumerate(First: genericOp.getDpsInputOperands())) {
561 auto concatOp = operand->get().getDefiningOp<tensor::ConcatOp>();
562 if (!concatOp) {
563 nonConcatInputs.push_back(Elt: operand);
564 continue;
565 }
566
567 // Rewriting a concat that has other consumers could increase the amount
568 // of live computation instead of just exposing fusion opportunities.
569 if (!concatOp->hasOneUse())
570 return rewriter.notifyMatchFailure(arg&: genericOp,
571 msg: "concat input has another consumer");
572
573 AffineMap inputMap = genericOp.getMatchingIndexingMap(opOperand: operand);
574 auto concatDimExpr =
575 dyn_cast<AffineDimExpr>(Val: inputMap.getResult(idx: concatOp.getDim()));
576 if (!concatDimExpr)
577 return rewriter.notifyMatchFailure(
578 arg&: genericOp, msg: "concat dimension does not map to a loop dimension");
579
580 unsigned currentSplitLoopDim = concatDimExpr.getPosition();
581 if (splitLoopDim && *splitLoopDim != currentSplitLoopDim)
582 return rewriter.notifyMatchFailure(
583 arg&: genericOp, msg: "concat inputs partition different loop dimensions");
584 splitLoopDim = currentSplitLoopDim;
585
586 SmallVector<int64_t> currentPartitionSizes;
587 currentPartitionSizes.reserve(N: concatOp.getInputs().size());
588 for (Value input : concatOp.getInputs()) {
589 int64_t size = cast<RankedTensorType>(Val: input.getType())
590 .getDimSize(idx: concatOp.getDim());
591 if (ShapedType::isDynamic(dValue: size))
592 return rewriter.notifyMatchFailure(
593 arg&: genericOp, msg: "concat partition size is dynamic");
594 currentPartitionSizes.push_back(Elt: size);
595 }
596 partitionSizes.push_back(Elt: std::move(currentPartitionSizes));
597 concatOps[index] = concatOp;
598 }
599
600 if (!splitLoopDim)
601 return rewriter.notifyMatchFailure(arg&: genericOp, msg: "has no concat input");
602 if (!llvm::all_equal(Range&: partitionSizes))
603 return rewriter.notifyMatchFailure(
604 arg&: genericOp, msg: "concat inputs have different partition sizes");
605
606 // A tensor input that varies along the split dimension must itself be a
607 // compatible concat. Inputs that are invariant along that dimension can be
608 // reused by every split operation.
609 AffineExpr splitDimExpr =
610 getAffineDimExpr(position: *splitLoopDim, context: genericOp.getContext());
611 for (OpOperand *operand : nonConcatInputs) {
612 Type operandType = operand->get().getType();
613 // Scalars do not vary along an iteration-space dimension and can be
614 // reused in every partition.
615 if (isa<IntegerType, FloatType, IndexType, ComplexType>(Val: operandType))
616 continue;
617
618 // Otherwise we want ranked tensors.
619 if (!isa<RankedTensorType>(Val: operandType))
620 return rewriter.notifyMatchFailure(
621 arg&: genericOp, msg: "non-concat shaped input is not a ranked tensor");
622
623 if (genericOp.getMatchingIndexingMap(opOperand: operand).getResultPosition(
624 input: splitDimExpr))
625 return rewriter.notifyMatchFailure(
626 arg&: genericOp, msg: "non-concat input varies along the split dimension");
627 }
628
629 // Map the iteration-space split dimension to each output's physical tensor
630 // dimension. `isElementwise` guarantees that the output maps are
631 // permutations, so every output contains this dimension.
632 SmallVector<unsigned> outputConcatDims;
633 outputConcatDims.reserve(N: genericOp.getNumDpsInits());
634 for (OpOperand &output : genericOp.getDpsInitsMutable()) {
635 std::optional<unsigned> outputDim =
636 genericOp.getMatchingIndexingMap(opOperand: &output).getResultPosition(
637 input: splitDimExpr);
638 // Otherwise the generic op is not elementwise.
639 assert(outputDim &&
640 "elementwise output map must contain the split dimension");
641 outputConcatDims.push_back(Elt: *outputDim);
642 }
643
644 Location loc = genericOp.getLoc();
645 // Keep each result in a separate list because a generic can have multiple
646 // outputs.
647 SmallVector<SmallVector<Value>> splitResults(genericOp->getNumResults());
648 SmallVector<int64_t> outputOffsets(genericOp.getNumDpsInits(), 0);
649
650 // Build one generic for each aligned concat partition. For
651 // `elementwise(concat(x0, x1), concat(y0, y1))` becomes
652 // `elementwise(x0, y0)` and `elementwise(x1, y1)`.
653 for (auto [partitionIndex, partitionSize] :
654 llvm::enumerate(First&: partitionSizes.front())) {
655 // For each partition, turn inputs `concat(x0, x1)`, `concat(y0, y1)`, and
656 // `scalar` into the inputs `x0`, `y0`, and `scalar`.
657 SmallVector<Value> inputs =
658 getPartitionInputs(genericOp, concatOps, partitionIndex);
659 // For a `tensor<7xf32>` output and partition size [3, 4], create a
660 // `tensor<3xf32>` output here; if the body reads `%init`, use
661 // `%init[0:3]` as its init instead.
662 PartitionOutputs outputs =
663 createPartitionOutputs(rewriter, loc, genericOp, outputConcatDims,
664 partitionSize, outputOffsets);
665 // For example, clone the body of
666 // `elementwise(concat(x0, x1), concat(y0, y1))` as
667 // `elementwise(x0, y0)`, retaining its indexing maps and iterators.
668 GenericOp splitOp =
669 cloneGenericForPartition(rewriter, loc, genericOp, inputs, outputs);
670 for (auto [resultIndex, result] : llvm::enumerate(First: splitOp->getResults()))
671 splitResults[resultIndex].push_back(Elt: result);
672 }
673
674 // Reassemble every original result from its partition results. The concat
675 // dimension may differ for each output due to its indexing map.
676 SmallVector<Value> replacements;
677 replacements.reserve(N: genericOp->getNumResults());
678 for (auto [resultIndex, result] :
679 llvm::enumerate(First: genericOp->getResults())) {
680 replacements.push_back(Elt: tensor::ConcatOp::create(
681 builder&: rewriter, location: loc, result: cast<RankedTensorType>(Val: result.getType()),
682 dim: outputConcatDims[resultIndex], inputs: splitResults[resultIndex]));
683 }
684 rewriter.replaceOp(op: genericOp, newValues: replacements);
685 return success();
686 }
687
688private:
689 /// Return the inputs for one concat partition.
690 /// For example, for `elementwise(concat(x0, x1), concat(y0, y1), scalar)`,
691 /// partition 0 uses `(x0, y0, scalar)` and partition 1 uses
692 /// `(x1, y1, scalar)`.
693 static SmallVector<Value>
694 getPartitionInputs(GenericOp genericOp, ArrayRef<tensor::ConcatOp> concatOps,
695 unsigned partitionIndex) {
696 SmallVector<Value> inputs;
697 inputs.reserve(N: genericOp.getNumDpsInputs());
698 for (auto [index, operand] :
699 llvm::enumerate(First: genericOp.getDpsInputOperands())) {
700 if (!concatOps[index]) {
701 inputs.push_back(Elt: operand->get());
702 continue;
703 }
704 tensor::ConcatOp concatOp = concatOps[index];
705 inputs.push_back(Elt: concatOp.getInputs()[partitionIndex]);
706 }
707 return inputs;
708 }
709
710 struct PartitionOutputs {
711 SmallVector<Value> values;
712 SmallVector<Type> resultTypes;
713 };
714
715 /// Create the output operands and result types for one concat partition.
716 /// For an output `tensor<7xf32>` split into sizes `[3, 4]`, this creates a
717 /// `tensor<3xf32>` output for partition 0 and `tensor<4xf32>` for partition
718 /// 1. If the generic body reads its output block argument, the outputs are
719 /// slices of the original init tensor, e.g. `%init[0:3]` and `%init[3:7]`;
720 /// otherwise they are `tensor.empty` values.
721 static PartitionOutputs createPartitionOutputs(
722 PatternRewriter &rewriter, Location loc, GenericOp genericOp,
723 ArrayRef<unsigned> outputConcatDims, int64_t partitionSize,
724 MutableArrayRef<int64_t> outputOffsets) {
725 PartitionOutputs partitionOutputs;
726 partitionOutputs.values.reserve(N: genericOp.getNumDpsInits());
727 partitionOutputs.resultTypes.reserve(N: genericOp->getNumResults());
728 for (auto [outputIndex, output] :
729 llvm::enumerate(First: genericOp.getDpsInitsMutable())) {
730 Value outputValue = output.get();
731 auto outputType = cast<RankedTensorType>(Val: outputValue.getType());
732 unsigned outputConcatDim = outputConcatDims[outputIndex];
733 SmallVector<int64_t> partitionShape(outputType.getShape());
734 partitionShape[outputConcatDim] = partitionSize;
735 auto partitionType =
736 RankedTensorType::get(shape: partitionShape, elementType: outputType.getElementType(),
737 encoding: outputType.getEncoding());
738
739 SmallVector<OpFoldResult> sizes =
740 tensor::getMixedSizes(builder&: rewriter, loc, value: outputValue);
741 sizes[outputConcatDim] = rewriter.getIndexAttr(value: partitionSize);
742
743 Value partitionOutput;
744 // A body such as `linalg.yield %in` does not read `%out`, so the init
745 // value is irrelevant and this partition can use `tensor.empty`.
746 if (!genericOp.payloadUsesValueFromOperand(opOperand: &output)) {
747 partitionOutput = tensor::EmptyOp::create(builder&: rewriter, location: loc, sizes,
748 elementType: outputType.getElementType(),
749 encoding: outputType.getEncoding());
750 } else {
751 // A body such as `%sum = arith.addf %in, %out` reads the init value.
752 // For a `[3, 4]` partitioning, extract `%init[0:3]` for partition 0
753 // and `%init[3:7]` for partition 1 to preserve that value.
754 SmallVector<OpFoldResult> offsets(outputType.getRank(),
755 rewriter.getIndexAttr(value: 0));
756 SmallVector<OpFoldResult> strides(outputType.getRank(),
757 rewriter.getIndexAttr(value: 1));
758 offsets[outputConcatDim] =
759 rewriter.getIndexAttr(value: outputOffsets[outputIndex]);
760 partitionOutput = tensor::ExtractSliceOp::create(
761 builder&: rewriter, location: loc, resultType: partitionType, source: outputValue, offsets, sizes, strides);
762 }
763 partitionOutputs.values.push_back(Elt: partitionOutput);
764 partitionOutputs.resultTypes.push_back(Elt: partitionType);
765 outputOffsets[outputIndex] += partitionSize;
766 }
767 return partitionOutputs;
768 }
769
770 /// Clone `genericOp` for one partition while preserving its computation and
771 /// relevant attributes. For example, this turns the `x0, y0` inputs from
772 /// `getPartitionInputs` into an `elementwise(x0, y0)` generic with the same
773 /// body as the original `elementwise(concat(x0, x1), concat(y0, y1))`.
774 static GenericOp cloneGenericForPartition(PatternRewriter &rewriter,
775 Location loc, GenericOp genericOp,
776 ArrayRef<Value> inputs,
777 const PartitionOutputs &outputs) {
778 GenericOp splitOp = GenericOp::create(
779 builder&: rewriter, location: loc, resultTensorTypes: outputs.resultTypes, inputs, outputs: outputs.values,
780 indexingMaps: genericOp.getIndexingMapsArray(), iteratorTypes: genericOp.getIteratorTypesArray());
781 if (StringAttr doc = genericOp.getDocAttr())
782 splitOp->setAttr(name: splitOp.getDocAttrName(), value: doc);
783 if (StringAttr libraryCall = genericOp.getLibraryCallAttr())
784 splitOp->setAttr(name: splitOp.getLibraryCallAttrName(), value: libraryCall);
785 splitOp->setDiscardableAttrs(genericOp->getDiscardableAttrDictionary());
786 rewriter.cloneRegionBefore(region&: genericOp.getRegion(), parent&: splitOp.getRegion(),
787 before: splitOp.getRegion().begin());
788 return splitOp;
789 }
790};
791} // namespace
792
793//===---------------------------------------------------------------------===//
794// Methods and patterns that fuse reshape ops with elementwise operations by
795// expanding the dimensionality of the elementwise operations.
796//===---------------------------------------------------------------------===//
797
798/// Conditions for folding a structured linalg operation with a reshape op by
799/// expanding the iteration space dimensionality for tensor operations. These
800/// are preconditions assumed by `foldReshapeByDimExpansion` which implements
801/// the following fusion pattern.
802///
803/// Consider
804///
805/// %c = linalg.generic ins(%a, %b : memref<?x?x?xf32>, memref<?x?xf32>)
806/// indexing_maps = [affine_map<(d0, d1, d2) -> (d1, d0, d2)>,
807/// affine_map<(d0, d1, d2) -> (d1, d2)>,
808/// affine_map<(d0, d1, d2) -> (d0, d2, d1)>]
809/// %d = tensor.expand_shape %c [[0, 1], [2], [3, 4, 5]]
810/// : tensor<?x?x?xf32> into tensor<?x?x?x?x?x?xf32>
811///
812/// The reshape can be folded into the `linalgOp` if its loop dimensionality
813/// is increased to match the result (operand) of the tensor.expand_shape.
814/// The indexing_map of the fused tensor in the `linalgOp` and the
815/// reassociation map helps compute the indexing maps of the modified op.
816/// For the above example, based on the reassociation map it
817/// can be concluded that
818///
819/// - The loop used to access the first dimension of the fused tensor is split
820/// into two.
821/// - The loop used to access the second dimension of the fused tensor is kept
822/// as is.
823/// - The loop used to access the third dimension of the fused tensor is split
824/// into three.
825///
826/// i.e. (e0, e1, e2, e3, e4) is the domain of the indexing map of the modified
827/// op, then
828///
829/// d0 -> e0, e1
830/// d1 -> e2, e3, e4
831/// d2 -> e5
832///
833/// substituting this, the structured op can be rewritten as
834///
835/// %d = linalg.generic ins(%0, %1 : )
836/// indexing_maps =
837/// [affine_map<(e0, e1, e2, e3, e4, e5) -> (e2, e3, e4, e0, e1, e5)>,
838/// affine_map<(e0, e1, e2, e3, e4, e5) -> (e2, e3, e4, e5)>,
839/// affine_map<(e0, e1, e2, e3, e4, e5) -> (e0, e1, e5, e2, e3, e4)>]
840///
841/// Since operands to the linalg generic are now 5D, reshapes can be introduced
842/// to make it consistent
843///
844/// %0 = tensor.expand_shape %a [[0, 1, 2], [3, 4], [5]]
845/// : tensor<?x?x?xf32> into tensor<?x?x?x?x?x?xf32>
846/// %1 = tensor.expand_shape %b [[0, 1, 2], [3]]
847/// : tensor<?x?x?xf32> into tensor<?x?x?x?xf32>
848///
849/// The added reshapes are again expanding patterns, so they will get fused
850/// with its producers if possible.
851static bool isFusableWithReshapeByDimExpansion(LinalgOp linalgOp,
852 OpOperand *fusableOpOperand) {
853 // Is fusable only if:
854 // - All the indexing maps for operands and results are projected
855 // permutations.
856 // - The fused tensor is not a scalar.
857 SmallVector<utils::IteratorType> iteratorTypes =
858 linalgOp.getIteratorTypesArray();
859 AffineMap operandMap = linalgOp.getMatchingIndexingMap(opOperand: fusableOpOperand);
860 return linalgOp.hasPureTensorSemantics() &&
861 llvm::all_of(Range: linalgOp.getIndexingMaps().getValue(),
862 P: [](Attribute attr) {
863 return cast<AffineMapAttr>(Val&: attr)
864 .getValue()
865 .isProjectedPermutation();
866 }) &&
867 operandMap.getNumResults() > 0;
868}
869
870namespace {
871/// Information needed to expand a generic operation to fold the reshape with
872/// it.
873class ExpansionInfo {
874public:
875 // Computes the mapping from original dimensions of the op to the dimensions
876 // of the expanded op given the `indexingMap` of the fused operand/result of
877 // the generic op, the `reassocationMaps` of the reshape op and the shape of
878 // the expanded op.
879 LogicalResult compute(LinalgOp linalgOp, OpOperand *fusableOpOperand,
880 ArrayRef<AffineMap> reassociationMaps,
881 ArrayRef<OpFoldResult> expandedShape,
882 PatternRewriter &rewriter);
883 unsigned getOrigOpNumDims() const { return reassociation.size(); }
884 unsigned getExpandedOpNumDims() const { return expandedOpNumDims; }
885 ReassociationIndicesRef getExpandedDims(unsigned i) const {
886 return reassociation[i];
887 }
888 ArrayRef<OpFoldResult> getExpandedShapeOfDim(unsigned i) const {
889 return expandedShapeMap[i];
890 }
891 ArrayRef<OpFoldResult> getOriginalShape() const { return originalLoopExtent; }
892
893private:
894 /// Reassociation from the dimensions in the original operation to the
895 /// dimension of the expanded operation.
896 SmallVector<ReassociationIndices> reassociation;
897 /// Mapping from extent of loops in the original operation, to the extent of
898 /// loops in the expanded operation.
899 SmallVector<SmallVector<OpFoldResult>> expandedShapeMap;
900 /// Extent of the loop in the original operation.
901 SmallVector<OpFoldResult> originalLoopExtent;
902 unsigned expandedOpNumDims;
903};
904} // namespace
905
906LogicalResult ExpansionInfo::compute(LinalgOp linalgOp,
907 OpOperand *fusableOpOperand,
908 ArrayRef<AffineMap> reassociationMaps,
909 ArrayRef<OpFoldResult> expandedShape,
910 PatternRewriter &rewriter) {
911 if (reassociationMaps.empty())
912 return failure();
913 AffineMap fusedIndexMap = linalgOp.getMatchingIndexingMap(opOperand: fusableOpOperand);
914
915 OpBuilder::InsertionGuard g(rewriter);
916 rewriter.setInsertionPoint(linalgOp);
917 originalLoopExtent = llvm::map_to_vector(
918 C: linalgOp.createLoopRanges(b&: rewriter, loc: linalgOp->getLoc()),
919 F: [](Range r) { return r.size; });
920
921 reassociation.clear();
922 expandedShapeMap.clear();
923 // Compute the number of dimension in the expanded op that correspond to each
924 // dimension of the original op.
925 SmallVector<unsigned> numExpandedDims(fusedIndexMap.getNumDims(), 1);
926 expandedShapeMap.resize(N: fusedIndexMap.getNumDims());
927 for (const auto &resultExpr : llvm::enumerate(First: fusedIndexMap.getResults())) {
928 unsigned pos = cast<AffineDimExpr>(Val: resultExpr.value()).getPosition();
929 AffineMap foldedDims = reassociationMaps[resultExpr.index()];
930 numExpandedDims[pos] = foldedDims.getNumResults();
931 ArrayRef<OpFoldResult> shape =
932 expandedShape.slice(N: foldedDims.getDimPosition(idx: 0), M: numExpandedDims[pos]);
933 expandedShapeMap[pos].assign(in_start: shape.begin(), in_end: shape.end());
934 }
935 // The remaining dimensions remain the same.
936 for (unsigned i : llvm::seq<unsigned>(Begin: 0, End: fusedIndexMap.getNumDims()))
937 if (expandedShapeMap[i].empty())
938 expandedShapeMap[i] = {originalLoopExtent[i]};
939
940 // Compute reassociation map from the original op to the expanded op.
941 unsigned sum = 0;
942 reassociation.reserve(N: fusedIndexMap.getNumDims());
943 for (const auto &numFoldedDim : llvm::enumerate(First&: numExpandedDims)) {
944 auto seq = llvm::seq<int64_t>(Begin: sum, End: sum + numFoldedDim.value());
945 reassociation.emplace_back(Args: seq.begin(), Args: seq.end());
946 sum += numFoldedDim.value();
947 }
948 expandedOpNumDims = sum;
949 return success();
950}
951
952/// Return the indexing map to use in the expanded op for a given the
953/// `indexingMap` of the original operation.
954static AffineMap
955getIndexingMapInExpandedOp(OpBuilder &builder, AffineMap indexingMap,
956 const ExpansionInfo &expansionInfo) {
957 SmallVector<AffineExpr> newExprs;
958 for (AffineExpr expr : indexingMap.getResults()) {
959 unsigned pos = cast<AffineDimExpr>(Val&: expr).getPosition();
960 SmallVector<AffineExpr, 4> expandedExprs = llvm::map_to_vector<4>(
961 C: expansionInfo.getExpandedDims(i: pos), F: [&](int64_t v) {
962 return builder.getAffineDimExpr(position: static_cast<unsigned>(v));
963 });
964 newExprs.append(in_start: expandedExprs.begin(), in_end: expandedExprs.end());
965 }
966 return AffineMap::get(dimCount: expansionInfo.getExpandedOpNumDims(),
967 symbolCount: indexingMap.getNumSymbols(), results: newExprs,
968 context: builder.getContext());
969}
970
971/// Return the shape and type of the operand/result to use in the expanded op
972/// given the type in the original op.
973static std::tuple<SmallVector<OpFoldResult>, RankedTensorType>
974getExpandedShapeAndType(RankedTensorType originalType, AffineMap indexingMap,
975 const ExpansionInfo &expansionInfo) {
976 SmallVector<OpFoldResult> expandedShape;
977 for (AffineExpr expr : indexingMap.getResults()) {
978 unsigned dim = cast<AffineDimExpr>(Val&: expr).getPosition();
979 ArrayRef<OpFoldResult> dimExpansion =
980 expansionInfo.getExpandedShapeOfDim(i: dim);
981 expandedShape.append(in_start: dimExpansion.begin(), in_end: dimExpansion.end());
982 }
983 SmallVector<int64_t> expandedStaticShape;
984 std::tie(args&: expandedStaticShape, args: std::ignore) =
985 decomposeMixedValues(mixedValues: expandedShape);
986 return {expandedShape, RankedTensorType::get(shape: expandedStaticShape,
987 elementType: originalType.getElementType())};
988}
989
990/// Returns the reassociation maps to use in the `tensor.expand_shape`
991/// operation to convert the operands of the original operation to operands of
992/// the expanded operation. The same method is used to compute the
993/// `tensor.collapse_shape` used to collapse the result of the expanded
994/// op to get the value that can replace all uses of the results of the original
995/// op.
996static SmallVector<ReassociationIndices>
997getReassociationForExpansion(AffineMap indexingMap,
998 const ExpansionInfo &expansionInfo) {
999 SmallVector<ReassociationIndices> reassociation;
1000 unsigned numReshapeDims = 0;
1001 for (AffineExpr expr : indexingMap.getResults()) {
1002 unsigned dim = cast<AffineDimExpr>(Val&: expr).getPosition();
1003 auto numExpandedDims = expansionInfo.getExpandedDims(i: dim).size();
1004 SmallVector<int64_t, 2> indices = llvm::to_vector<2>(
1005 Range: llvm::seq<int64_t>(Begin: numReshapeDims, End: numReshapeDims + numExpandedDims));
1006 reassociation.emplace_back(Args: std::move(indices));
1007 numReshapeDims += numExpandedDims;
1008 }
1009 return reassociation;
1010}
1011
1012/// Update the body of an expanded linalg operation having index semantics. The
1013/// indices of the original operation need to be recovered by linearizing the
1014/// indices of the correspoding dimensions of the expanded operation. For now it
1015/// is assumed that the shapes of the expanded operation needed for
1016/// linearization are static.
1017static void updateExpandedGenericOpRegion(PatternRewriter &rewriter,
1018 Location loc, Region &fusedRegion,
1019 const ExpansionInfo &expansionInfo) {
1020 // Replace the original indices by the linearization of the expanded indices.
1021 for (IndexOp indexOp :
1022 llvm::make_early_inc_range(Range: fusedRegion.front().getOps<IndexOp>())) {
1023 ArrayRef<int64_t> expandedDims =
1024 expansionInfo.getExpandedDims(i: indexOp.getDim());
1025 assert(!expandedDims.empty() && "expected valid expansion info");
1026
1027 // Skip index operations that are not affected by the expansion.
1028 if (expandedDims.size() == 1 &&
1029 expandedDims.front() == (int64_t)indexOp.getDim())
1030 continue;
1031
1032 // Linearize the expanded indices of the original index dimension.
1033 OpBuilder::InsertionGuard guard(rewriter);
1034 rewriter.setInsertionPointAfter(indexOp);
1035 ArrayRef<OpFoldResult> expandedDimsShape =
1036 expansionInfo.getExpandedShapeOfDim(i: indexOp.getDim()).drop_front();
1037 SmallVector<Value> expandedIndices;
1038 expandedIndices.reserve(N: expandedDims.size() - 1);
1039 llvm::transform(
1040 Range: expandedDims.drop_front(), d_first: std::back_inserter(x&: expandedIndices),
1041 F: [&](int64_t dim) { return IndexOp::create(builder&: rewriter, location: loc, dim); });
1042 OpFoldResult newIndex =
1043 IndexOp::create(builder&: rewriter, location: loc, dim: expandedDims.front()).getResult();
1044 for (auto [expandedShape, expandedIndex] :
1045 llvm::zip(t&: expandedDimsShape, u&: expandedIndices)) {
1046 AffineExpr idx, acc, shape;
1047 bindDims(ctx: rewriter.getContext(), exprs&: idx, exprs&: acc);
1048 bindSymbols(ctx: rewriter.getContext(), exprs&: shape);
1049 newIndex = affine::makeComposedFoldedAffineApply(
1050 b&: rewriter, loc: indexOp.getLoc(), expr: idx + acc * shape,
1051 operands: ArrayRef<OpFoldResult>{expandedIndex, newIndex, expandedShape});
1052 }
1053 Value newIndexVal =
1054 getValueOrCreateConstantIndexOp(b&: rewriter, loc: indexOp.getLoc(), ofr: newIndex);
1055 rewriter.replaceOp(op: indexOp, newValues: newIndexVal);
1056 }
1057}
1058
1059// Create an expanded transpose op.
1060// the reassociation map is already permuted hence we inverse permute and then
1061// flatten it. Then we inverse permute it again to get the final expanded
1062// transpose permutation. For example,
1063//
1064// permutation = [2, 0, 1]
1065// reassociation_map for expansion = [[0, 1], [2], [3, 4, 5]]
1066//
1067// inverse permutation = [1, 2, 0]
1068// applied to reassocation_map and then flattened becomes
1069// flatened permutation = [2, 3, 4, 5, 0, 1]
1070// final permuation is the inverse of the flattened permutation.
1071//
1072// Becomes
1073//
1074// permutation=[4, 5, 0, 1, 2, 3]
1075
1076static Operation *createExpandedTransposeOp(PatternRewriter &rewriter,
1077 TransposeOp transposeOp,
1078 Value expandedInput, Value output,
1079 ExpansionInfo &expansionInfo) {
1080 SmallVector<int64_t> newPerm;
1081 for (int64_t perm : invertPermutationVector(permutation: transposeOp.getPermutation())) {
1082 auto reassoc = expansionInfo.getExpandedDims(i: perm);
1083 for (int64_t dim : reassoc) {
1084 newPerm.push_back(Elt: dim);
1085 }
1086 }
1087 return TransposeOp::create(builder&: rewriter, location: transposeOp.getLoc(), input: expandedInput,
1088 init: output, permutation: invertPermutationVector(permutation: newPerm));
1089}
1090
1091// Create an expanded generic op.
1092static Operation *createExpandedGenericOp(
1093 PatternRewriter &rewriter, LinalgOp linalgOp, TypeRange resultTypes,
1094 ArrayRef<Value> &expandedOpOperands, ArrayRef<Value> outputs,
1095 ExpansionInfo &expansionInfo, ArrayRef<AffineMap> expandedOpIndexingMaps) {
1096 // The iterator types of the expanded op are all parallel.
1097 SmallVector<utils::IteratorType> iteratorTypes(
1098 expansionInfo.getExpandedOpNumDims(), utils::IteratorType::parallel);
1099
1100 for (auto [i, type] : llvm::enumerate(First: linalgOp.getIteratorTypesArray()))
1101 for (auto j : expansionInfo.getExpandedDims(i))
1102 iteratorTypes[j] = type;
1103
1104 Operation *fused = GenericOp::create(builder&: rewriter, location: linalgOp.getLoc(), resultTensorTypes: resultTypes,
1105 inputs: expandedOpOperands, outputs,
1106 indexingMaps: expandedOpIndexingMaps, iteratorTypes);
1107
1108 Region &fusedRegion = fused->getRegion(index: 0);
1109 Region &originalRegion = linalgOp->getRegion(index: 0);
1110 rewriter.cloneRegionBefore(region&: originalRegion, parent&: fusedRegion, before: fusedRegion.begin());
1111
1112 // Update the index accesses after the expansion.
1113 updateExpandedGenericOpRegion(rewriter, loc: linalgOp.getLoc(), fusedRegion,
1114 expansionInfo);
1115
1116 return fused;
1117}
1118
1119// Create an expanded fused op that retains the name for certain ops
1120// such as fill, copy and transpose and produce a generic op for
1121// rest of linalg ops.
1122static Operation *createExpandedOp(PatternRewriter &rewriter, LinalgOp linalgOp,
1123 TypeRange resultTypes,
1124 ArrayRef<Value> expandedOpOperands,
1125 ArrayRef<Value> outputs,
1126 ArrayRef<AffineMap> expandedOpIndexingMaps,
1127 ExpansionInfo &expansionInfo) {
1128
1129 return TypeSwitch<Operation *, Operation *>(linalgOp.getOperation())
1130 .Case(caseFn: [&](TransposeOp transposeOp) {
1131 return createExpandedTransposeOp(rewriter, transposeOp,
1132 expandedInput: expandedOpOperands[0], output: outputs[0],
1133 expansionInfo);
1134 })
1135 .Case<FillOp, CopyOp>(caseFn: [&](Operation *op) {
1136 return clone(b&: rewriter, op: linalgOp, newResultTypes: resultTypes,
1137 newOperands: llvm::to_vector(Range: llvm::concat<Value>(
1138 Ranges: llvm::to_vector(Range&: expandedOpOperands),
1139 Ranges: llvm::to_vector(Range&: outputs))));
1140 })
1141 .Default(defaultFn: [&](Operation *op) {
1142 return createExpandedGenericOp(rewriter, linalgOp, resultTypes,
1143 expandedOpOperands, outputs,
1144 expansionInfo, expandedOpIndexingMaps);
1145 });
1146}
1147
1148/// Implements the fusion of a tensor.collapse_shape or a tensor.expand_shape op
1149/// and a generic op as explained in `isFusableWithReshapeByExpansion`. Assumes
1150/// that those conditions have been satisfied.
1151static std::optional<SmallVector<Value>>
1152fuseWithReshapeByExpansion(LinalgOp linalgOp, Operation *reshapeOp,
1153 OpOperand *fusableOpOperand,
1154 PatternRewriter &rewriter) {
1155 assert(isFusableWithReshapeByDimExpansion(linalgOp, fusableOpOperand) &&
1156 "preconditions for fuse operation failed");
1157
1158 Location loc = linalgOp.getLoc();
1159 SmallVector<OpFoldResult> expandedShape;
1160 SmallVector<AffineMap, 4> reassociationIndices;
1161 Value src;
1162 if (auto expandingReshapeOp = dyn_cast<tensor::ExpandShapeOp>(Val: reshapeOp)) {
1163 // Try to move the dynamic dimensions in output shape before the `linalgOp`
1164 // to maintain SSA validity
1165 if (failed(Result: moveValueDefinitions(
1166 rewriter, values: expandingReshapeOp.getOutputShape(), insertionPoint: linalgOp)))
1167 return std::nullopt;
1168
1169 expandedShape = expandingReshapeOp.getMixedOutputShape();
1170 reassociationIndices = expandingReshapeOp.getReassociationMaps();
1171 src = expandingReshapeOp.getSrc();
1172 } else {
1173 auto collapsingReshapeOp = dyn_cast<tensor::CollapseShapeOp>(Val: reshapeOp);
1174 if (!collapsingReshapeOp)
1175 return std::nullopt;
1176
1177 expandedShape = tensor::getMixedSizes(
1178 builder&: rewriter, loc: collapsingReshapeOp->getLoc(), value: collapsingReshapeOp.getSrc());
1179 reassociationIndices = collapsingReshapeOp.getReassociationMaps();
1180 src = collapsingReshapeOp.getSrc();
1181 }
1182
1183 ExpansionInfo expansionInfo;
1184 if (failed(Result: expansionInfo.compute(linalgOp, fusableOpOperand,
1185 reassociationMaps: reassociationIndices, expandedShape,
1186 rewriter)))
1187 return std::nullopt;
1188
1189 SmallVector<AffineMap, 4> expandedOpIndexingMaps =
1190 llvm::map_to_vector<4>(C: linalgOp.getIndexingMapsArray(), F: [&](AffineMap m) {
1191 return getIndexingMapInExpandedOp(builder&: rewriter, indexingMap: m, expansionInfo);
1192 });
1193
1194 // Set insertion point to the generic op.
1195 OpBuilder::InsertionGuard g(rewriter);
1196 rewriter.setInsertionPoint(linalgOp);
1197
1198 SmallVector<Value> expandedOpOperands;
1199 expandedOpOperands.reserve(N: linalgOp.getNumDpsInputs());
1200 for (OpOperand *opOperand : linalgOp.getDpsInputOperands()) {
1201 if (opOperand == fusableOpOperand) {
1202 expandedOpOperands.push_back(Elt: src);
1203 continue;
1204 }
1205 if (auto opOperandType =
1206 dyn_cast<RankedTensorType>(Val: opOperand->get().getType())) {
1207 AffineMap indexingMap = linalgOp.getMatchingIndexingMap(opOperand);
1208 SmallVector<OpFoldResult> expandedOperandShape;
1209 RankedTensorType expandedOperandType;
1210 std::tie(args&: expandedOperandShape, args&: expandedOperandType) =
1211 getExpandedShapeAndType(originalType: opOperandType, indexingMap, expansionInfo);
1212 if (expandedOperandType != opOperand->get().getType()) {
1213 // Reshape the operand to get the right type.
1214 SmallVector<ReassociationIndices> reassociation =
1215 getReassociationForExpansion(indexingMap, expansionInfo);
1216 if (failed(Result: reshapeLikeShapesAreCompatible(
1217 emitError: [&](const Twine &msg) {
1218 return rewriter.notifyMatchFailure(arg&: linalgOp, msg);
1219 },
1220 collapsedShape: opOperandType.getShape(), expandedShape: expandedOperandType.getShape(),
1221 reassociationMaps: reassociation,
1222 /*isExpandingReshape=*/true)))
1223 return std::nullopt;
1224 expandedOpOperands.push_back(Elt: tensor::ExpandShapeOp::create(
1225 builder&: rewriter, location: loc, resultType: expandedOperandType, src: opOperand->get(), reassociation,
1226 outputShape: expandedOperandShape));
1227 continue;
1228 }
1229 }
1230 expandedOpOperands.push_back(Elt: opOperand->get());
1231 }
1232
1233 SmallVector<Value> outputs;
1234 for (OpOperand &opOperand : linalgOp.getDpsInitsMutable()) {
1235 AffineMap indexingMap = linalgOp.getMatchingIndexingMap(opOperand: &opOperand);
1236 auto opOperandType = cast<RankedTensorType>(Val: opOperand.get().getType());
1237 SmallVector<OpFoldResult> expandedOutputShape;
1238 RankedTensorType expandedOutputType;
1239 std::tie(args&: expandedOutputShape, args&: expandedOutputType) =
1240 getExpandedShapeAndType(originalType: opOperandType, indexingMap, expansionInfo);
1241 if (expandedOutputType != opOperand.get().getType()) {
1242 SmallVector<ReassociationIndices> reassociation =
1243 getReassociationForExpansion(indexingMap, expansionInfo);
1244 if (failed(Result: reshapeLikeShapesAreCompatible(
1245 emitError: [&](const Twine &msg) {
1246 return rewriter.notifyMatchFailure(arg&: linalgOp, msg);
1247 },
1248 collapsedShape: opOperandType.getShape(), expandedShape: expandedOutputType.getShape(),
1249 reassociationMaps: reassociation,
1250 /*isExpandingReshape=*/true)))
1251 return std::nullopt;
1252 outputs.push_back(Elt: tensor::ExpandShapeOp::create(
1253 builder&: rewriter, location: loc, resultType: expandedOutputType, src: opOperand.get(), reassociation,
1254 outputShape: expandedOutputShape));
1255 } else {
1256 outputs.push_back(Elt: opOperand.get());
1257 }
1258 }
1259
1260 TypeRange resultTypes = ValueRange(outputs).getTypes();
1261 Operation *fusedOp =
1262 createExpandedOp(rewriter, linalgOp, resultTypes, expandedOpOperands,
1263 outputs, expandedOpIndexingMaps, expansionInfo);
1264 // Reshape the result values to their original shape if this is a collapsing
1265 // reshape folded into its consumer.
1266 SmallVector<Value> resultVals;
1267 for (OpResult opResult : linalgOp->getOpResults()) {
1268 int64_t resultNumber = opResult.getResultNumber();
1269 if (resultTypes[resultNumber] != opResult.getType()) {
1270 SmallVector<ReassociationIndices> reassociation =
1271 getReassociationForExpansion(
1272 indexingMap: linalgOp.getMatchingIndexingMap(
1273 opOperand: linalgOp.getDpsInitOperand(i: resultNumber)),
1274 expansionInfo);
1275 resultVals.push_back(Elt: tensor::CollapseShapeOp::create(
1276 builder&: rewriter, location: linalgOp.getLoc(), resultType: opResult.getType(),
1277 src: fusedOp->getResult(idx: resultNumber), reassociation));
1278 } else {
1279 resultVals.push_back(Elt: fusedOp->getResult(idx: resultNumber));
1280 }
1281 }
1282 // Assuming a single result.
1283 return resultVals;
1284}
1285
1286namespace {
1287
1288/// Pattern to fuse a tensor.collapse_shape op with its consumer structured op,
1289/// when the reshape op is collapsing dimensions. The dimensionality of the loop
1290/// in the consumer is expanded.
1291class FoldWithProducerReshapeOpByExpansion
1292 : public OpInterfaceRewritePattern<LinalgOp> {
1293public:
1294 FoldWithProducerReshapeOpByExpansion(MLIRContext *context,
1295 ControlFusionFn foldReshapes,
1296 PatternBenefit benefit = 1)
1297 : OpInterfaceRewritePattern<LinalgOp>(context, benefit),
1298 controlFoldingReshapes(std::move(foldReshapes)) {}
1299
1300 LogicalResult matchAndRewrite(LinalgOp linalgOp,
1301 PatternRewriter &rewriter) const override {
1302 for (OpOperand *opOperand : linalgOp.getDpsInputOperands()) {
1303 tensor::CollapseShapeOp reshapeOp =
1304 opOperand->get().getDefiningOp<tensor::CollapseShapeOp>();
1305 if (!reshapeOp)
1306 continue;
1307 // Fold only if
1308 // - The tensor reshape op is folding.
1309 // - All constraints of fusing with reshape by expansion are met.
1310 if (!isFusableWithReshapeByDimExpansion(linalgOp, fusableOpOperand: opOperand) ||
1311 (!controlFoldingReshapes(opOperand)))
1312 continue;
1313
1314 std::optional<SmallVector<Value>> replacementValues =
1315 fuseWithReshapeByExpansion(linalgOp, reshapeOp, fusableOpOperand: opOperand, rewriter);
1316 if (!replacementValues)
1317 return failure();
1318 rewriter.replaceOp(op: linalgOp, newValues: *replacementValues);
1319 return success();
1320 }
1321 return failure();
1322 }
1323
1324private:
1325 ControlFusionFn controlFoldingReshapes;
1326};
1327
1328/// Carries information about a padded dimension.
1329struct PadDimInfo {
1330 // The resulting shape after padding each dimension.
1331 SmallVector<int64_t> paddedShape;
1332
1333 // Low and high padding amounts for each dimension.
1334 SmallVector<OpFoldResult> lowPad;
1335 SmallVector<OpFoldResult> highPad;
1336};
1337
1338/// Computes the expanded padding information for the given pad operation based
1339/// on the provided expanded shape and reassociation indices. Returns a list of
1340/// PadDimInfo containing the low and high padding amounts and the padded
1341/// size for each dimension, or failure if the expansion is not possible.
1342static FailureOr<PadDimInfo>
1343computeExpandedPadding(tensor::PadOp padOp, ArrayRef<int64_t> expandedShape,
1344 ArrayRef<ReassociationIndices> reassociations,
1345 PatternRewriter &rewriter) {
1346 // If the padding value depends on the index values of the pad operation,
1347 // then it may not be valid to expand the dimensions, since it will change
1348 // the index values on which the padding value depends. This is not currently
1349 // supported by the pad expansion patterns, but it could be implemented
1350 // similarly to the expansion of linalg.generic ops with linalg.index ops in
1351 // the body, as is done in `updateExpandedGenericOpRegion`.
1352 if (!padOp.getConstantPaddingValue())
1353 return failure();
1354
1355 // Expanded dimensions cannot have padding because the resulting padding may
1356 // not be representable by a tensor.pad op. There are some special cases where
1357 // it is possible (like expanding unit dims), but supporting these cases is
1358 // NYI, so disallow it for now.
1359 ArrayRef<int64_t> low = padOp.getStaticLow();
1360 ArrayRef<int64_t> high = padOp.getStaticHigh();
1361 for (auto [reInd, l, h] : llvm::zip_equal(t&: reassociations, u&: low, args&: high)) {
1362 if (reInd.size() != 1 && (l != 0 || h != 0))
1363 return failure();
1364 }
1365
1366 SmallVector<OpFoldResult> mixedLowPad(padOp.getMixedLowPad());
1367 SmallVector<OpFoldResult> mixedHighPad(padOp.getMixedHighPad());
1368 ArrayRef<int64_t> paddedShape = padOp.getResultType().getShape();
1369 PadDimInfo padDimInfo;
1370 padDimInfo.paddedShape.assign(AR: expandedShape);
1371 padDimInfo.lowPad.assign(NumElts: expandedShape.size(), Elt: rewriter.getIndexAttr(value: 0));
1372 padDimInfo.highPad.assign(NumElts: expandedShape.size(), Elt: rewriter.getIndexAttr(value: 0));
1373 for (auto [idx, reInd] : llvm::enumerate(First&: reassociations)) {
1374 if (reInd.size() == 1) {
1375 padDimInfo.paddedShape[reInd[0]] = paddedShape[idx];
1376 padDimInfo.lowPad[reInd[0]] = mixedLowPad[idx];
1377 padDimInfo.highPad[reInd[0]] = mixedHighPad[idx];
1378 }
1379 }
1380
1381 return padDimInfo;
1382}
1383
1384class FoldPadWithProducerReshapeOpByExpansion
1385 : public OpRewritePattern<tensor::PadOp> {
1386public:
1387 FoldPadWithProducerReshapeOpByExpansion(MLIRContext *context,
1388 ControlFusionFn foldReshapes,
1389 PatternBenefit benefit = 1)
1390 : OpRewritePattern<tensor::PadOp>(context, benefit),
1391 controlFoldingReshapes(std::move(foldReshapes)) {}
1392
1393 LogicalResult matchAndRewrite(tensor::PadOp padOp,
1394 PatternRewriter &rewriter) const override {
1395 tensor::CollapseShapeOp reshapeOp =
1396 padOp.getSource().getDefiningOp<tensor::CollapseShapeOp>();
1397 if (!reshapeOp)
1398 return failure();
1399
1400 if (!controlFoldingReshapes(&padOp.getSourceMutable())) {
1401 return rewriter.notifyMatchFailure(arg&: padOp,
1402 msg: "fusion blocked by control function");
1403 }
1404
1405 RankedTensorType expandedType = reshapeOp.getSrcType();
1406 SmallVector<ReassociationIndices> reassociations =
1407 reshapeOp.getReassociationIndices();
1408 FailureOr<PadDimInfo> maybeExpandedPadding = computeExpandedPadding(
1409 padOp, expandedShape: expandedType.getShape(), reassociations, rewriter);
1410 if (failed(Result: maybeExpandedPadding))
1411 return failure();
1412 PadDimInfo &expandedPadding = maybeExpandedPadding.value();
1413
1414 Location loc = padOp->getLoc();
1415 RankedTensorType expandedPaddedType =
1416 padOp.getResultType().clone(shape: expandedPadding.paddedShape);
1417
1418 auto newPadOp = tensor::PadOp::create(
1419 builder&: rewriter, location: loc, resultType: expandedPaddedType, source: reshapeOp.getSrc(),
1420 low: expandedPadding.lowPad, high: expandedPadding.highPad,
1421 constantPadValue: padOp.getConstantPaddingValue(), nofold: padOp.getNofold());
1422
1423 rewriter.replaceOpWithNewOp<tensor::CollapseShapeOp>(
1424 op: padOp, args: padOp.getResultType(), args: newPadOp.getResult(), args&: reassociations);
1425
1426 return success();
1427 }
1428
1429private:
1430 ControlFusionFn controlFoldingReshapes;
1431};
1432
1433class FoldReshapeWithProducerPadOpByExpansion
1434 : public OpRewritePattern<tensor::ExpandShapeOp> {
1435public:
1436 FoldReshapeWithProducerPadOpByExpansion(MLIRContext *context,
1437 ControlFusionFn foldReshapes,
1438 PatternBenefit benefit = 1)
1439 : OpRewritePattern<tensor::ExpandShapeOp>(context, benefit),
1440 controlFoldingReshapes(std::move(foldReshapes)) {}
1441
1442 LogicalResult matchAndRewrite(tensor::ExpandShapeOp expandOp,
1443 PatternRewriter &rewriter) const override {
1444 tensor::PadOp padOp = expandOp.getSrc().getDefiningOp<tensor::PadOp>();
1445 if (!padOp)
1446 return failure();
1447
1448 if (!controlFoldingReshapes(&expandOp.getSrcMutable())) {
1449 return rewriter.notifyMatchFailure(arg&: expandOp,
1450 msg: "fusion blocked by control function");
1451 }
1452
1453 RankedTensorType expandedType = expandOp.getResultType();
1454 SmallVector<ReassociationIndices> reassociations =
1455 expandOp.getReassociationIndices();
1456 FailureOr<PadDimInfo> maybeExpandedPadding = computeExpandedPadding(
1457 padOp, expandedShape: expandedType.getShape(), reassociations, rewriter);
1458 if (failed(Result: maybeExpandedPadding))
1459 return failure();
1460 PadDimInfo &expandedPadding = maybeExpandedPadding.value();
1461
1462 Location loc = expandOp->getLoc();
1463 SmallVector<OpFoldResult> newExpandedSizes = expandOp.getMixedOutputShape();
1464 SmallVector<int64_t> newExpandedShape(expandedType.getShape());
1465 rewriter.setInsertionPointAfterValue(padOp.getSource());
1466 SmallVector<OpFoldResult> padSrcSizes =
1467 tensor::getMixedSizes(builder&: rewriter, loc, value: padOp.getSource());
1468 for (auto [idx, reInd] : llvm::enumerate(First&: reassociations)) {
1469 // We know that any reassociation with multiple dims is not padded because
1470 // of the requirements of computeExpandedPadding.
1471 if (reInd.size() == 1) {
1472 newExpandedShape[reInd[0]] = padOp.getSourceType().getDimSize(idx);
1473 newExpandedSizes[reInd[0]] = padSrcSizes[idx];
1474 }
1475 }
1476 RankedTensorType newExpandedType = expandedType.clone(shape: newExpandedShape);
1477 auto newExpandOp = tensor::ExpandShapeOp::create(
1478 builder&: rewriter, location: loc, resultType: newExpandedType, src: padOp.getSource(), reassociation: reassociations,
1479 outputShape: newExpandedSizes);
1480 RankedTensorType expandedPaddedType =
1481 padOp.getResultType().clone(shape: expandedPadding.paddedShape);
1482 rewriter.setInsertionPoint(expandOp);
1483 auto newPadOp = tensor::PadOp::create(
1484 builder&: rewriter, location: loc, resultType: expandedPaddedType, source: newExpandOp.getResult(),
1485 low: expandedPadding.lowPad, high: expandedPadding.highPad,
1486 constantPadValue: padOp.getConstantPaddingValue(), nofold: padOp.getNofold());
1487
1488 rewriter.replaceOp(op: expandOp, newValues: newPadOp.getResult());
1489
1490 return success();
1491 }
1492
1493private:
1494 ControlFusionFn controlFoldingReshapes;
1495};
1496
1497/// Pattern to fold a tensor.expand_shape op with its producer generic op
1498/// by expanding the dimensionality of the loop in the producer op.
1499struct FoldReshapeWithGenericOpByExpansion
1500 : public OpRewritePattern<tensor::ExpandShapeOp> {
1501
1502 FoldReshapeWithGenericOpByExpansion(MLIRContext *context,
1503 ControlFusionFn foldReshapes,
1504 PatternBenefit benefit = 1)
1505 : OpRewritePattern<tensor::ExpandShapeOp>(context, benefit),
1506 controlFoldingReshapes(std::move(foldReshapes)) {}
1507
1508 LogicalResult matchAndRewrite(tensor::ExpandShapeOp reshapeOp,
1509 PatternRewriter &rewriter) const override {
1510 // Fold only if all constraints of fusing with reshape by expansion are met.
1511 auto producerResult = dyn_cast<OpResult>(Val: reshapeOp.getSrc());
1512 if (!producerResult) {
1513 return rewriter.notifyMatchFailure(arg&: reshapeOp,
1514 msg: "source not produced by an operation");
1515 }
1516
1517 auto producer = dyn_cast<LinalgOp>(Val: producerResult.getOwner());
1518 if (!producer) {
1519 return rewriter.notifyMatchFailure(arg&: reshapeOp,
1520 msg: "producer not a generic op");
1521 }
1522
1523 if (!isFusableWithReshapeByDimExpansion(
1524 linalgOp: producer,
1525 fusableOpOperand: producer.getDpsInitOperand(i: producerResult.getResultNumber()))) {
1526 return rewriter.notifyMatchFailure(
1527 arg&: reshapeOp, msg: "failed preconditions of fusion with producer generic op");
1528 }
1529
1530 if (!controlFoldingReshapes(&reshapeOp.getSrcMutable())) {
1531 return rewriter.notifyMatchFailure(arg&: reshapeOp,
1532 msg: "fusion blocked by control function");
1533 }
1534
1535 std::optional<SmallVector<Value>> replacementValues =
1536 fuseWithReshapeByExpansion(
1537 linalgOp: producer, reshapeOp,
1538 fusableOpOperand: producer.getDpsInitOperand(i: producerResult.getResultNumber()),
1539 rewriter);
1540 if (!replacementValues) {
1541 return rewriter.notifyMatchFailure(arg&: reshapeOp,
1542 msg: "fusion by expansion failed");
1543 }
1544
1545 // Find the replacement for the reshape op. Since the replacements have the
1546 // same type as the returns of the original generic op, the consumer reshape
1547 // op can be replaced by the source of the collapse_shape op that defines
1548 // the replacement.
1549 Value reshapeReplacement =
1550 (*replacementValues)[cast<OpResult>(Val: reshapeOp.getSrc())
1551 .getResultNumber()];
1552 if (auto collapseOp =
1553 reshapeReplacement.getDefiningOp<tensor::CollapseShapeOp>()) {
1554 reshapeReplacement = collapseOp.getSrc();
1555 }
1556 rewriter.replaceOp(op: reshapeOp, newValues: reshapeReplacement);
1557 rewriter.replaceOp(op: producer, newValues: *replacementValues);
1558 return success();
1559 }
1560
1561private:
1562 ControlFusionFn controlFoldingReshapes;
1563};
1564} // namespace
1565
1566//===---------------------------------------------------------------------===//
1567// Methods and patterns to fuse reshape with linalg.generic operations by
1568// contraction of dimensions.
1569//===---------------------------------------------------------------------===//
1570
1571/// For a given list of indices in the range of the `indexingMap` that are
1572/// folded, return the indices of the corresponding domain. Return
1573/// `std::nullopt` on failure. Ensures that all the elements of the returned
1574/// reassociation are distinct.
1575static ReassociationIndices
1576getDomainReassociation(AffineMap indexingMap,
1577 ReassociationIndicesRef rangeReassociation) {
1578 assert(indexingMap.isProjectedPermutation() &&
1579 "expected projected permutation");
1580
1581 ReassociationIndices domainReassociation =
1582 llvm::map_to_vector<4>(C&: rangeReassociation, F: [&](int64_t pos) -> int64_t {
1583 return cast<AffineDimExpr>(Val: indexingMap.getResults()[pos]).getPosition();
1584 });
1585 // The projected permutation semantics ensures that there is no repetition of
1586 // the domain indices.
1587 return domainReassociation;
1588}
1589
1590/// For a given `dimSequence`, check if the sequence is conserved in the
1591/// `indexingMap`. `indexingMap` is expected to be a projected permutation.
1592/// Non-existence of the sequence returns true as well.
1593bool mlir::linalg::isDimSequencePreserved(AffineMap indexingMap,
1594 ReassociationIndicesRef dimSequence) {
1595 assert(!dimSequence.empty() &&
1596 "expected non-empty list for dimension sequence");
1597
1598 // Dimension sequences can only be preserved in projected permutation maps.
1599 if (!indexingMap.isProjectedPermutation()) {
1600 return false;
1601 }
1602
1603 llvm::SmallDenseSet<unsigned, 4> sequenceElements;
1604 sequenceElements.insert_range(R&: dimSequence);
1605
1606 unsigned dimSequenceStart = dimSequence[0];
1607 for (const auto &expr : enumerate(First: indexingMap.getResults())) {
1608 unsigned dimInMapStart = cast<AffineDimExpr>(Val: expr.value()).getPosition();
1609 // 1. Check if this start of the sequence.
1610 if (dimInMapStart == dimSequenceStart) {
1611 if (expr.index() + dimSequence.size() > indexingMap.getNumResults())
1612 return false;
1613 // 1a. Check if sequence is preserved.
1614 for (const auto &dimInSequence : enumerate(First&: dimSequence)) {
1615 unsigned dimInMap =
1616 cast<AffineDimExpr>(
1617 Val: indexingMap.getResult(idx: expr.index() + dimInSequence.index()))
1618 .getPosition();
1619 if (dimInMap != dimInSequence.value())
1620 return false;
1621 }
1622 // Found the sequence. Projected permutation
1623 // enforces that all AffineDimExprs in the result are unique, so no
1624 // further checks are needed.
1625 return true;
1626 }
1627 // 2. If position in the expr (which is of type AffineDimExpr) is part
1628 // of sequence, return false here. This implies the entire sequence does not
1629 // exist in the indexing map.
1630 if (sequenceElements.count(V: dimInMapStart))
1631 return false;
1632 }
1633 // 3. No element of sequence found. Return true.
1634 return true;
1635}
1636
1637bool mlir::linalg::areDimSequencesPreserved(
1638 ArrayRef<AffineMap> maps, ArrayRef<ReassociationIndices> dimSequences) {
1639 return llvm::all_of(Range&: maps, P: [&](AffineMap map) {
1640 return llvm::all_of(Range&: dimSequences, P: [&](ReassociationIndicesRef dimSequence) {
1641 return isDimSequencePreserved(indexingMap: map, dimSequence);
1642 });
1643 });
1644}
1645
1646// Return the list of dimensions of the iteration domain that can be
1647// collapsed to allow for fusion with the a producer that is an expand_shape
1648// operation. If all dimensions created by expansion can be collapsed in the
1649// iteration space then the reshape is defunct.
1650//
1651// Example:
1652//
1653// ```mlir
1654// #map = affine_map<(d0, d1) -> (d0, d1)>
1655// %1 = tensor.expand_shape %0 [[0, 1]] : tensor<?xf32> into tensor<?x4xf32>
1656// %2 = tensor.empty [..] : tensor<?x4xf32>
1657// %3 = linalg.generic {
1658// indexing_maps = [#map, #map],
1659// iterator_types = ["parallel" ,"parallel"]}
1660// ins(%1 : tensor<?x4xf32>) outs(%2 : tensor<?x4xf32>) {.. }
1661// ```
1662//
1663// can be fused by collapsing the dimensions of the iteration space.
1664//
1665// ```mlir
1666// #map = affine_map<(d0) -> (d0)>
1667// %2 = tensor.empty [..] : tensor<?xf32>
1668// %3 = linalg.generic {
1669// indexing_maps = [#map, #map],
1670// iterator_types = ["parallel"]}
1671// ins(%1 : tensor<?xf32>) outs(%2 : tensor<?xf32>) {.. }
1672// %4 = tensor.expand_shape %3 [[0, 1]] : tensor<?xf32> into tensor<?x4xf32>
1673// ```
1674//
1675// In the following example,
1676//
1677// ```mlir
1678// #map0 = affine_map<(d0, d1) -> (d0, d1)>
1679// #map1 = affine_map<(d0, d1) -> (d1, d0)>
1680// %1 = tensor.expand_shape %0 [[0, 1]] : tensor<?xf32> into tensor<?x4xf32>
1681// %2 = tensor.empty [..] : tensor<4x?xf32>
1682// %2 = linalg.generic {
1683// indexing_maps = [#map0, #map1],
1684// iterator_types = ["parallel" ,"parallel"]}
1685// ins(%1 : tensor<?x4xf32>) outs(%2 : tensor<4x?xf32>) {.. }
1686// ```
1687//
1688// the reshape cannot be fused with the generic op by collapsing the op
1689// dimensions since the indexing maps will have to contain mods and divs
1690// to preserve the accesses pattern. When no dimensions of the iteration
1691// space are collapsable and empty vector is returned.
1692static SmallVector<ReassociationIndices>
1693getCollapsableIterationSpaceDims(GenericOp genericOp, OpOperand *fusableOperand,
1694 ArrayRef<ReassociationIndices> reassociation) {
1695 // Some basic checks for this fusion to be valid.
1696 if (!genericOp.hasPureTensorSemantics())
1697 return {};
1698
1699 if (!llvm::all_of(Range: genericOp.getIndexingMapsArray(), P: [](AffineMap map) {
1700 return map.isProjectedPermutation();
1701 })) {
1702 return {};
1703 }
1704
1705 // Compute all the loops with the reduction iterator types.
1706 SmallVector<unsigned> reductionDims;
1707 genericOp.getReductionDims(res&: reductionDims);
1708
1709 llvm::SmallDenseSet<unsigned, 4> processedIterationDims;
1710 AffineMap indexingMap = genericOp.getMatchingIndexingMap(opOperand: fusableOperand);
1711 auto iteratorTypes = genericOp.getIteratorTypesArray();
1712 SmallVector<ReassociationIndices> iterationSpaceReassociation;
1713 for (ReassociationIndicesRef foldedRangeDims : reassociation) {
1714 assert(!foldedRangeDims.empty() && "unexpected empty reassociation");
1715
1716 // Ignore dims that are not folded.
1717 if (foldedRangeDims.size() == 1)
1718 continue;
1719
1720 ReassociationIndices foldedIterationSpaceDims =
1721 getDomainReassociation(indexingMap, rangeReassociation: foldedRangeDims);
1722
1723 // Check that the folded iteration dims do not contain already processed
1724 // dims.
1725 if (llvm::any_of(Range&: foldedIterationSpaceDims, P: [&](int64_t dim) {
1726 return processedIterationDims.count(V: dim);
1727 }))
1728 continue;
1729
1730 // Check that all folded iterator types are all parallel or all reductions.
1731 utils::IteratorType startIteratorType =
1732 iteratorTypes[foldedIterationSpaceDims[0]];
1733 if (!isParallelIterator(iteratorType: startIteratorType) &&
1734 !isReductionIterator(iteratorType: startIteratorType))
1735 continue;
1736 if (llvm::any_of(Range&: foldedIterationSpaceDims, P: [&](int64_t dim) {
1737 return iteratorTypes[dim] != startIteratorType;
1738 }))
1739 continue;
1740
1741 // If the folded dimensions correspond to a "reduction" iterator type,
1742 // the folded dimensions need to be "in-order". Strictly speaking this is
1743 // not necessary, for reductions that are associative and commutative, but
1744 // using a more strict definition of reduction for now.
1745 if (isReductionIterator(iteratorType: startIteratorType)) {
1746 bool isContiguous = false;
1747 for (const auto &startDim : llvm::enumerate(First&: reductionDims)) {
1748 // Move window in `reductionDims` to start of the folded iteration dims.
1749 if (startDim.value() != foldedIterationSpaceDims[0])
1750 continue;
1751 // If sizes doesnt match, trivial not contiguous. This condition should
1752 // not be hit.
1753 if (startDim.index() + foldedIterationSpaceDims.size() >
1754 reductionDims.size())
1755 break;
1756 // Check that the contiguity is maintained.
1757 isContiguous = true;
1758 for (const auto &foldedDim :
1759 llvm::enumerate(First&: foldedIterationSpaceDims)) {
1760 if (reductionDims[foldedDim.index() + startDim.index()] !=
1761 foldedDim.value()) {
1762 isContiguous = false;
1763 break;
1764 }
1765 }
1766 break;
1767 }
1768 if (!isContiguous)
1769 continue;
1770 }
1771
1772 // Check that the sequence is preserved in all indexing maps.
1773 if (llvm::any_of(Range: genericOp.getIndexingMapsArray(),
1774 P: [&](AffineMap indexingMap) {
1775 return !isDimSequencePreserved(indexingMap,
1776 dimSequence: foldedIterationSpaceDims);
1777 }))
1778 continue;
1779
1780 processedIterationDims.insert_range(R&: foldedIterationSpaceDims);
1781 iterationSpaceReassociation.emplace_back(
1782 Args: std::move(foldedIterationSpaceDims));
1783 }
1784
1785 return iterationSpaceReassociation;
1786}
1787
1788/// Helper class to carry state while collapsing the `linalg.generic` op.
1789namespace {
1790class CollapsingInfo {
1791public:
1792 LogicalResult initialize(unsigned origNumLoops,
1793 ArrayRef<ReassociationIndices> foldedIterationDims) {
1794 llvm::SmallDenseSet<int64_t, 4> processedDims;
1795 // Find all the dims that are folded.
1796 for (ReassociationIndicesRef foldedIterationDim : foldedIterationDims) {
1797 if (foldedIterationDim.empty())
1798 continue;
1799 // If the folded dims contain dims already folded, that's illegal
1800 // specification. Repetition within a list is also illegal.
1801 for (auto dim : foldedIterationDim) {
1802 if (dim >= origNumLoops)
1803 return failure();
1804 if (processedDims.count(V: dim))
1805 return failure();
1806 processedDims.insert(V: dim);
1807 }
1808 collapsedOpToOrigOpIterationDim.emplace_back(Args: foldedIterationDim.begin(),
1809 Args: foldedIterationDim.end());
1810 }
1811 if (processedDims.size() > origNumLoops)
1812 return failure();
1813
1814 // Add all the preserved dims of the original op as single
1815 // elements to `collapsedOpToOrigOpIterationDim`.
1816 for (auto dim : llvm::seq<int64_t>(Begin: 0, End: origNumLoops)) {
1817 if (processedDims.count(V: dim))
1818 continue;
1819 collapsedOpToOrigOpIterationDim.emplace_back(Args: ReassociationIndices{dim});
1820 }
1821
1822 llvm::sort(C&: collapsedOpToOrigOpIterationDim,
1823 Comp: [&](ReassociationIndicesRef lhs, ReassociationIndicesRef rhs) {
1824 return lhs[0] < rhs[0];
1825 });
1826 origOpToCollapsedOpIterationDim.resize(N: origNumLoops);
1827 for (const auto &foldedDims :
1828 llvm::enumerate(First&: collapsedOpToOrigOpIterationDim)) {
1829 for (const auto &dim : enumerate(First&: foldedDims.value()))
1830 origOpToCollapsedOpIterationDim[dim.value()] =
1831 std::make_pair<int64_t, unsigned>(x: foldedDims.index(), y: dim.index());
1832 }
1833 return success();
1834 }
1835
1836 /// Return mapping from collapsed loop domain to original loop domain.
1837 ArrayRef<ReassociationIndices> getCollapsedOpToOrigOpMapping() const {
1838 return collapsedOpToOrigOpIterationDim;
1839 }
1840
1841 /// Return mapping from original loop domain to collapsed loop domain. The
1842 /// mapping is a pair. First value is the dimension in the collapsed loop that
1843 /// the original loop is mapped to. Second is the relative position in folded
1844 /// list of this domain. For example if the original loop domain is 3D, and
1845 /// the collapsed loop domain is folding all of it, i.e.
1846 ///
1847 /// ```
1848 /// collapsedOpToOrigOpMapping = [[0, 1, 2] [3, 4]]`
1849 /// ```
1850 ///
1851 /// then
1852 ///
1853 /// ```
1854 /// origOpToCollapsedOpMapping[0] = {0, 0};
1855 /// origOpToCollapsedOpMapping[1] = {0, 1};
1856 /// origOpToCollapsedOpMapping[2] = {0, 2};
1857 /// origOpToCollapsedOpMapping[3] = {1, 0};
1858 /// origOpToCollapsedOpMapping[4] = {1, 1};
1859 /// ```
1860 ///
1861 ArrayRef<std::pair<int64_t, unsigned>> getOrigOpToCollapsedOpMapping() const {
1862 return origOpToCollapsedOpIterationDim;
1863 }
1864
1865 /// Return the collapsed op iteration domain rank.
1866 unsigned getCollapsedOpIterationRank() const {
1867 return collapsedOpToOrigOpIterationDim.size();
1868 }
1869
1870private:
1871 /// Map from the iteration domain index in collapsed op to the iteration
1872 /// domain indices in the original op.
1873 SmallVector<ReassociationIndices> collapsedOpToOrigOpIterationDim;
1874
1875 /// Map from iteration domain index in the original op to the iteration domain
1876 /// index in the collapsed op.
1877 SmallVector<std::pair<int64_t, unsigned>> origOpToCollapsedOpIterationDim;
1878};
1879} // namespace
1880
1881/// Get the iterator types for the collapsed operation given the original
1882/// iterator types and collapsed dimensions.
1883static SmallVector<utils::IteratorType>
1884getCollapsedOpIteratorTypes(ArrayRef<utils::IteratorType> iteratorTypes,
1885 const CollapsingInfo &collapsingInfo) {
1886 SmallVector<utils::IteratorType> collapsedIteratorTypes;
1887 for (ReassociationIndicesRef foldedIterDims :
1888 collapsingInfo.getCollapsedOpToOrigOpMapping()) {
1889 assert(!foldedIterDims.empty() &&
1890 "reassociation indices expected to have non-empty sets");
1891 // Just pick the iterator type of the first folded dim. Pre-condition checks
1892 // expected to have checked that iterator types of all folded dimensions are
1893 // the same.
1894 collapsedIteratorTypes.push_back(Elt: iteratorTypes[foldedIterDims[0]]);
1895 }
1896 return collapsedIteratorTypes;
1897}
1898
1899/// Compute the indexing map in the collapsed op that corresponds to the given
1900/// `indexingMap` of the original operation.
1901static AffineMap
1902getCollapsedOpIndexingMap(AffineMap indexingMap,
1903 const CollapsingInfo &collapsingInfo) {
1904 MLIRContext *context = indexingMap.getContext();
1905 assert(indexingMap.isProjectedPermutation() &&
1906 "expected indexing map to be projected permutation");
1907 SmallVector<AffineExpr> resultExprs;
1908 auto origOpToCollapsedOpMapping =
1909 collapsingInfo.getOrigOpToCollapsedOpMapping();
1910 for (auto expr : indexingMap.getResults()) {
1911 unsigned dim = cast<AffineDimExpr>(Val&: expr).getPosition();
1912 // If the dim is not the first of the collapsed dim, do nothing.
1913 if (origOpToCollapsedOpMapping[dim].second != 0)
1914 continue;
1915 // The next n-dims are guaranteed to be collapsed. So just use the
1916 // iteration dimension of the collapsed op.
1917 resultExprs.push_back(
1918 Elt: getAffineDimExpr(position: origOpToCollapsedOpMapping[dim].first, context));
1919 }
1920 return AffineMap::get(dimCount: collapsingInfo.getCollapsedOpIterationRank(), symbolCount: 0,
1921 results: resultExprs, context);
1922}
1923
1924/// Return the `reassociation` indices to use to collapse the operand when the
1925/// iteration space of a generic op is collapsed.
1926static SmallVector<ReassociationIndices>
1927getOperandReassociation(AffineMap indexingMap,
1928 const CollapsingInfo &collapsingInfo) {
1929 unsigned counter = 0;
1930 SmallVector<ReassociationIndices> operandReassociation;
1931 auto origOpToCollapsedOpMapping =
1932 collapsingInfo.getOrigOpToCollapsedOpMapping();
1933 auto collapsedOpToOrigOpMapping =
1934 collapsingInfo.getCollapsedOpToOrigOpMapping();
1935 while (counter < indexingMap.getNumResults()) {
1936 unsigned dim =
1937 cast<AffineDimExpr>(Val: indexingMap.getResult(idx: counter)).getPosition();
1938 // This is the start of a collapsed dimensions of the iteration that
1939 // is gauranteed to be preserved in the indexing map. The number of folded
1940 // dims is obtained from the collapsed op to original op mapping.
1941 unsigned numFoldedDims =
1942 collapsedOpToOrigOpMapping[origOpToCollapsedOpMapping[dim].first]
1943 .size();
1944 if (origOpToCollapsedOpMapping[dim].second == 0) {
1945 auto range = llvm::seq<unsigned>(Begin: counter, End: counter + numFoldedDims);
1946 operandReassociation.emplace_back(Args: range.begin(), Args: range.end());
1947 }
1948 counter += numFoldedDims;
1949 }
1950 return operandReassociation;
1951}
1952
1953/// Get the new value to use for a given `OpOperand` in the collapsed operation.
1954static Value getCollapsedOpOperand(Location loc, LinalgOp op,
1955 OpOperand *opOperand,
1956 const CollapsingInfo &collapsingInfo,
1957 OpBuilder &builder) {
1958 AffineMap indexingMap = op.getMatchingIndexingMap(opOperand);
1959 SmallVector<ReassociationIndices> operandReassociation =
1960 getOperandReassociation(indexingMap, collapsingInfo);
1961
1962 // If the number of entries in the reassociation for the operand is same as
1963 // the number of results of the indexing map, then nothing to do for this
1964 // operand.
1965 Value operand = opOperand->get();
1966 if (operandReassociation.size() == indexingMap.getNumResults())
1967 return operand;
1968
1969 // Insert a reshape to collapse the dimensions.
1970 if (isa<MemRefType>(Val: operand.getType())) {
1971 return memref::CollapseShapeOp::create(builder, location: loc, src: operand,
1972 reassociation: operandReassociation)
1973 .getResult();
1974 }
1975 return tensor::CollapseShapeOp::create(builder, location: loc, src: operand,
1976 reassociation: operandReassociation)
1977 .getResult();
1978}
1979
1980/// Modify the `linalg.index` operations in the original generic op, to its
1981/// value in the collapsed operation.
1982static void generateCollapsedIndexingRegion(
1983 Location loc, Block *block, const CollapsingInfo &collapsingInfo,
1984 ArrayRef<OpFoldResult> loopRange, RewriterBase &rewriter) {
1985 OpBuilder::InsertionGuard g(rewriter);
1986 rewriter.setInsertionPointToStart(block);
1987
1988 // Collect all the original index ops.
1989 auto indexOps = llvm::to_vector(Range: block->getOps<linalg::IndexOp>());
1990
1991 // For each folded dimension list resolve the original induction variable
1992 // values in terms of the folded dimension induction variable.
1993 // i_{folded} = (i_0 * d1 + i1) * d2 + i2.
1994 // can be inverted to
1995 // i2 = i_{folded} % d2
1996 // i1 = (i_{folded} / d2) % d1
1997 // i0 = i_{folded} / (d1 * d2)
1998 llvm::DenseMap<unsigned, Value> indexReplacementVals;
1999 for (auto foldedDims :
2000 enumerate(First: collapsingInfo.getCollapsedOpToOrigOpMapping())) {
2001 ReassociationIndicesRef foldedDimsRef(foldedDims.value());
2002 Value newIndexVal =
2003 linalg::IndexOp::create(builder&: rewriter, location: loc, dim: foldedDims.index());
2004 for (auto dim : llvm::reverse(C: foldedDimsRef.drop_front())) {
2005 Value loopDim =
2006 getValueOrCreateConstantIndexOp(b&: rewriter, loc, ofr: loopRange[dim]);
2007 indexReplacementVals[dim] =
2008 rewriter.createOrFold<arith::RemSIOp>(location: loc, args&: newIndexVal, args&: loopDim);
2009 newIndexVal =
2010 rewriter.createOrFold<arith::DivSIOp>(location: loc, args&: newIndexVal, args&: loopDim);
2011 }
2012 indexReplacementVals[foldedDims.value().front()] = newIndexVal;
2013 }
2014
2015 for (auto indexOp : indexOps) {
2016 auto dim = indexOp.getDim();
2017 rewriter.replaceOp(op: indexOp, newValues: indexReplacementVals[dim]);
2018 }
2019}
2020
2021static void collapseOperandsAndResults(LinalgOp op,
2022 const CollapsingInfo &collapsingInfo,
2023 RewriterBase &rewriter,
2024 SmallVectorImpl<Value> &inputOperands,
2025 SmallVectorImpl<Value> &outputOperands,
2026 SmallVectorImpl<Type> &resultTypes) {
2027 Location loc = op->getLoc();
2028 inputOperands =
2029 llvm::map_to_vector(C: op.getDpsInputOperands(), F: [&](OpOperand *opOperand) {
2030 return getCollapsedOpOperand(loc, op, opOperand, collapsingInfo,
2031 builder&: rewriter);
2032 });
2033
2034 // Get the output operands and result types.
2035 resultTypes.reserve(N: op.getNumDpsInits());
2036 outputOperands.reserve(N: op.getNumDpsInits());
2037 for (OpOperand &output : op.getDpsInitsMutable()) {
2038 Value newOutput =
2039 getCollapsedOpOperand(loc, op, opOperand: &output, collapsingInfo, builder&: rewriter);
2040 outputOperands.push_back(Elt: newOutput);
2041 // If the op has "buffer semantics", then the init operands are ranked
2042 // memrefs and the op has no results.
2043 if (!op.hasPureBufferSemantics())
2044 resultTypes.push_back(Elt: newOutput.getType());
2045 }
2046}
2047
2048/// Clone a `LinalgOp` to a collapsed version of same name
2049template <typename OpTy>
2050static OpTy cloneToCollapsedOp(RewriterBase &rewriter, OpTy origOp,
2051 const CollapsingInfo &collapsingInfo) {
2052 return nullptr;
2053}
2054
2055/// Collapse any `LinalgOp` that does not require any specialization such as
2056/// indexing_maps, iterator_types, etc.
2057template <>
2058LinalgOp cloneToCollapsedOp<LinalgOp>(RewriterBase &rewriter, LinalgOp origOp,
2059 const CollapsingInfo &collapsingInfo) {
2060 SmallVector<Value> inputOperands, outputOperands;
2061 SmallVector<Type> resultTypes;
2062 collapseOperandsAndResults(op: origOp, collapsingInfo, rewriter, inputOperands,
2063 outputOperands, resultTypes);
2064
2065 return clone(
2066 b&: rewriter, op: origOp, newResultTypes: resultTypes,
2067 newOperands: llvm::to_vector(Range: llvm::concat<Value>(Ranges&: inputOperands, Ranges&: outputOperands)));
2068}
2069
2070/// Collapse a `GenericOp`
2071template <>
2072GenericOp cloneToCollapsedOp<GenericOp>(RewriterBase &rewriter,
2073 GenericOp origOp,
2074 const CollapsingInfo &collapsingInfo) {
2075 SmallVector<Value> inputOperands, outputOperands;
2076 SmallVector<Type> resultTypes;
2077 collapseOperandsAndResults(op: origOp, collapsingInfo, rewriter, inputOperands,
2078 outputOperands, resultTypes);
2079 SmallVector<AffineMap> indexingMaps(
2080 llvm::map_range(C: origOp.getIndexingMapsArray(), F: [&](AffineMap map) {
2081 return getCollapsedOpIndexingMap(indexingMap: map, collapsingInfo);
2082 }));
2083
2084 SmallVector<utils::IteratorType> iteratorTypes(getCollapsedOpIteratorTypes(
2085 iteratorTypes: origOp.getIteratorTypesArray(), collapsingInfo));
2086
2087 GenericOp collapsedOp = linalg::GenericOp::create(
2088 builder&: rewriter, location: origOp.getLoc(), resultTensorTypes: resultTypes, inputs: inputOperands, outputs: outputOperands,
2089 indexingMaps, iteratorTypes,
2090 odsArg5: [](OpBuilder &builder, Location loc, ValueRange args) {});
2091 Block *origOpBlock = &origOp->getRegion(index: 0).front();
2092 Block *collapsedOpBlock = &collapsedOp->getRegion(index: 0).front();
2093 rewriter.mergeBlocks(source: origOpBlock, dest: collapsedOpBlock,
2094 argValues: collapsedOpBlock->getArguments());
2095 return collapsedOp;
2096}
2097
2098/// Collapse a `BroadcastOp` with a 0-D input into the single flattened
2099/// dimension (`dimensions = [0]`).
2100template <>
2101BroadcastOp
2102cloneToCollapsedOp<BroadcastOp>(RewriterBase &rewriter, BroadcastOp origOp,
2103 const CollapsingInfo &collapsingInfo) {
2104 assert(origOp.getInput().getType().getRank() == 0 && "expected a 0-D input");
2105
2106 SmallVector<Value> inputOperands, outputOperands;
2107 SmallVector<Type> resultTypes;
2108 collapseOperandsAndResults(op: origOp, collapsingInfo, rewriter, inputOperands,
2109 outputOperands, resultTypes);
2110
2111 SmallVector<int64_t> newDimensions = {0};
2112 return BroadcastOp::create(builder&: rewriter, location: origOp.getLoc(), input: inputOperands[0],
2113 init: outputOperands[0], dimensions: newDimensions);
2114}
2115
2116static LinalgOp createCollapsedOp(LinalgOp op,
2117 const CollapsingInfo &collapsingInfo,
2118 RewriterBase &rewriter) {
2119 if (GenericOp genericOp = dyn_cast<GenericOp>(Val: op.getOperation())) {
2120 return cloneToCollapsedOp(rewriter, origOp: genericOp, collapsingInfo);
2121 }
2122 if (BroadcastOp broadcastOp = dyn_cast<BroadcastOp>(Val: op.getOperation())) {
2123 return cloneToCollapsedOp(rewriter, origOp: broadcastOp, collapsingInfo);
2124 }
2125 return cloneToCollapsedOp(rewriter, origOp: op, collapsingInfo);
2126}
2127
2128/// Implementation of fusion with reshape operation by collapsing dimensions.
2129FailureOr<CollapseResult> mlir::linalg::collapseOpIterationDims(
2130 LinalgOp op, ArrayRef<ReassociationIndices> foldedIterationDims,
2131 RewriterBase &rewriter) {
2132 // Bail on trivial no-op cases.
2133 if (op.getNumLoops() <= 1 || foldedIterationDims.empty() ||
2134 llvm::all_of(Range&: foldedIterationDims, P: [](ReassociationIndicesRef foldedDims) {
2135 return foldedDims.size() <= 1;
2136 }))
2137 return failure();
2138
2139 CollapsingInfo collapsingInfo;
2140 if (failed(
2141 Result: collapsingInfo.initialize(origNumLoops: op.getNumLoops(), foldedIterationDims))) {
2142 return rewriter.notifyMatchFailure(
2143 arg&: op, msg: "illegal to collapse specified dimensions");
2144 }
2145
2146 bool hasPureBufferSemantics = op.hasPureBufferSemantics();
2147 if (hasPureBufferSemantics &&
2148 !llvm::all_of(Range: op->getOpOperands(), P: [&](OpOperand &opOperand) -> bool {
2149 MemRefType memRefToCollapse =
2150 dyn_cast<MemRefType>(Val: opOperand.get().getType());
2151 if (!memRefToCollapse)
2152 return true;
2153
2154 AffineMap indexingMap = op.getMatchingIndexingMap(opOperand: &opOperand);
2155 SmallVector<ReassociationIndices> operandReassociation =
2156 getOperandReassociation(indexingMap, collapsingInfo);
2157 return memref::CollapseShapeOp::isGuaranteedCollapsible(
2158 srcType: memRefToCollapse, reassociation: operandReassociation);
2159 }))
2160 return rewriter.notifyMatchFailure(arg&: op,
2161 msg: "memref is not guaranteed collapsible");
2162
2163 // Bail on non-canonical ranges.
2164 SmallVector<Range> loopRanges = op.createLoopRanges(b&: rewriter, loc: op.getLoc());
2165 auto opFoldIsConstantValue = [](OpFoldResult ofr, int64_t value) {
2166 if (auto attr = llvm::dyn_cast_if_present<Attribute>(Val&: ofr))
2167 return cast<IntegerAttr>(Val&: attr).getInt() == value;
2168 llvm::APInt actual;
2169 return matchPattern(value: cast<Value>(Val&: ofr), pattern: m_ConstantInt(bind_value: &actual)) &&
2170 actual.getSExtValue() == value;
2171 };
2172 if (!llvm::all_of(Range&: loopRanges, P: [&](Range range) {
2173 return opFoldIsConstantValue(range.offset, 0) &&
2174 opFoldIsConstantValue(range.stride, 1);
2175 })) {
2176 return rewriter.notifyMatchFailure(
2177 arg&: op, msg: "expected all loop ranges to have zero start and unit stride");
2178 }
2179
2180 LinalgOp collapsedOp = createCollapsedOp(op, collapsingInfo, rewriter);
2181
2182 Location loc = op->getLoc();
2183 SmallVector<OpFoldResult> loopBound =
2184 llvm::map_to_vector(C&: loopRanges, F: [](Range range) { return range.size; });
2185
2186 if (collapsedOp.hasIndexSemantics()) {
2187 // Collect the loop range of the generic op.
2188 OpBuilder::InsertionGuard g(rewriter);
2189 rewriter.setInsertionPoint(collapsedOp);
2190 generateCollapsedIndexingRegion(loc, block: &collapsedOp->getRegion(index: 0).front(),
2191 collapsingInfo, loopRange: loopBound, rewriter);
2192 }
2193
2194 // Insert expanding reshape for the result to get back the original result
2195 // type.
2196 SmallVector<Value> results;
2197 for (const auto &originalResult : llvm::enumerate(First: op->getResults())) {
2198 Value collapsedOpResult = collapsedOp->getResult(idx: originalResult.index());
2199 auto originalResultType =
2200 cast<ShapedType>(Val: originalResult.value().getType());
2201 auto collapsedOpResultType = cast<ShapedType>(Val: collapsedOpResult.getType());
2202 if (collapsedOpResultType.getRank() != originalResultType.getRank()) {
2203 AffineMap indexingMap =
2204 op.getIndexingMapMatchingResult(result: originalResult.value());
2205 SmallVector<ReassociationIndices> reassociation =
2206 getOperandReassociation(indexingMap, collapsingInfo);
2207 assert(
2208 indexingMap.isProjectedPermutation() &&
2209 "Expected indexing map to be a projected permutation for collapsing");
2210 SmallVector<OpFoldResult> resultShape =
2211 applyPermutationMap(map: indexingMap, source: ArrayRef(loopBound));
2212 Value result;
2213 if (isa<MemRefType>(Val: collapsedOpResult.getType())) {
2214 result = memref::ExpandShapeOp::create(
2215 builder&: rewriter, location: loc, resultType: originalResultType, src: collapsedOpResult, reassociation,
2216 outputShape: resultShape);
2217 } else {
2218 result = tensor::ExpandShapeOp::create(
2219 builder&: rewriter, location: loc, resultType: originalResultType, src: collapsedOpResult, reassociation,
2220 outputShape: resultShape);
2221 }
2222 results.push_back(Elt: result);
2223 } else {
2224 results.push_back(Elt: collapsedOpResult);
2225 }
2226 }
2227 return CollapseResult{.results: results, .collapsedOp: collapsedOp};
2228}
2229
2230namespace {
2231
2232/// Pattern to fuse a tensor.expand_shape op with its consumer generic op by
2233/// contracting dimensions of the loop.
2234class FoldWithProducerReshapeOpByCollapsing
2235 : public OpRewritePattern<GenericOp> {
2236public:
2237 // TODO : support fusion with all linalg ops, not just generic.
2238 FoldWithProducerReshapeOpByCollapsing(MLIRContext *context,
2239 ControlFusionFn foldReshapes,
2240 PatternBenefit benefit = 1)
2241 : OpRewritePattern<GenericOp>(context, benefit),
2242 controlFoldingReshapes(std::move(foldReshapes)) {}
2243
2244 LogicalResult matchAndRewrite(GenericOp genericOp,
2245 PatternRewriter &rewriter) const override {
2246 for (OpOperand &opOperand : genericOp->getOpOperands()) {
2247 tensor::ExpandShapeOp reshapeOp =
2248 opOperand.get().getDefiningOp<tensor::ExpandShapeOp>();
2249 if (!reshapeOp)
2250 continue;
2251
2252 SmallVector<ReassociationIndices> collapsableIterationDims =
2253 getCollapsableIterationSpaceDims(genericOp, fusableOperand: &opOperand,
2254 reassociation: reshapeOp.getReassociationIndices());
2255 if (collapsableIterationDims.empty() ||
2256 !controlFoldingReshapes(&opOperand)) {
2257 continue;
2258 }
2259
2260 std::optional<CollapseResult> collapseResult = collapseOpIterationDims(
2261 op: genericOp, foldedIterationDims: collapsableIterationDims, rewriter);
2262 if (!collapseResult) {
2263 return rewriter.notifyMatchFailure(
2264 arg&: genericOp, msg: "failed to do the fusion by collapsing transformation");
2265 }
2266
2267 rewriter.replaceOp(op: genericOp, newValues: collapseResult->results);
2268 return success();
2269 }
2270 return failure();
2271 }
2272
2273private:
2274 ControlFusionFn controlFoldingReshapes;
2275};
2276
2277/// Pattern to fold a tensor.collapse_shape op with its producer generic op
2278/// by expanding the dimensionality of the loop in the producer op.
2279struct FoldReshapeWithGenericOpByCollapsing
2280 : public OpRewritePattern<tensor::CollapseShapeOp> {
2281
2282 FoldReshapeWithGenericOpByCollapsing(MLIRContext *context,
2283 ControlFusionFn foldReshapes,
2284 PatternBenefit benefit = 1)
2285 : OpRewritePattern<tensor::CollapseShapeOp>(context, benefit),
2286 controlFoldingReshapes(std::move(foldReshapes)) {}
2287
2288 LogicalResult matchAndRewrite(tensor::CollapseShapeOp reshapeOp,
2289 PatternRewriter &rewriter) const override {
2290 // Fold only if all constraints of fusing with reshape by collapsing are
2291 // met.
2292 auto producerResult = dyn_cast<OpResult>(Val: reshapeOp.getSrc());
2293 if (!producerResult) {
2294 return rewriter.notifyMatchFailure(arg&: reshapeOp,
2295 msg: "source not produced by an operation");
2296 }
2297
2298 // TODO : support fusion with all linalg producers, not just generic.
2299 auto producer = dyn_cast<GenericOp>(Val: producerResult.getOwner());
2300 if (!producer) {
2301 return rewriter.notifyMatchFailure(arg&: reshapeOp,
2302 msg: "producer not a generic op");
2303 }
2304
2305 SmallVector<ReassociationIndices> collapsableIterationDims =
2306 getCollapsableIterationSpaceDims(
2307 genericOp: producer,
2308 fusableOperand: producer.getDpsInitOperand(i: producerResult.getResultNumber()),
2309 reassociation: reshapeOp.getReassociationIndices());
2310 if (collapsableIterationDims.empty()) {
2311 return rewriter.notifyMatchFailure(
2312 arg&: reshapeOp, msg: "failed preconditions of fusion with producer generic op");
2313 }
2314
2315 if (!controlFoldingReshapes(&reshapeOp.getSrcMutable())) {
2316 return rewriter.notifyMatchFailure(arg&: reshapeOp,
2317 msg: "fusion blocked by control function");
2318 }
2319
2320 // Set the insertion point after `producer` because there could be uses
2321 // of `producer` between it and the `tensor.collapse_shape` op.
2322 rewriter.setInsertionPointAfter(producer);
2323 std::optional<CollapseResult> collapseResult =
2324 collapseOpIterationDims(op: producer, foldedIterationDims: collapsableIterationDims, rewriter);
2325 if (!collapseResult) {
2326 return rewriter.notifyMatchFailure(
2327 arg&: producer, msg: "failed to do the fusion by collapsing transformation");
2328 }
2329
2330 rewriter.replaceOp(op: producer, newValues: collapseResult->results);
2331 return success();
2332 }
2333
2334private:
2335 ControlFusionFn controlFoldingReshapes;
2336};
2337
2338/// Computes the collapsed padding information for the given pad operation based
2339/// on the provided collapsed shape and reassociation indices. Returns a
2340/// PadDimInfo containing the low and high padding amounts and the collapsed
2341/// shape for each dimension, or failure if the collapse is not possible.
2342static FailureOr<PadDimInfo>
2343computeCollapsedPadding(tensor::PadOp padOp,
2344 ArrayRef<ReassociationIndices> reassociations,
2345 PatternRewriter &rewriter) {
2346 // If the padding value depends on the index values of the pad operation,
2347 // then it may not be valid to collapse the dimensions, since it will change
2348 // the index values on which the padding value depends. This is not currently
2349 // supported by the pad collapsing patterns, but it could be implemented
2350 // similarly to the collapsing of linalg.generic ops with linalg.index ops in
2351 // the body, as is done in `generateCollapsedIndexingRegion`.
2352 if (!padOp.getConstantPaddingValue())
2353 return failure();
2354
2355 // Collapsed dimensions cannot have padding because this can produce strided
2356 // padding that isn't representable by a tensor.pad op. There are some special
2357 // cases where it is possible (like collapsing unit dims), but supporting
2358 // these cases is NYI, so disallow it for now.
2359 ArrayRef<int64_t> low = padOp.getStaticLow();
2360 ArrayRef<int64_t> high = padOp.getStaticHigh();
2361 for (auto [idx, reInd] : llvm::enumerate(First&: reassociations)) {
2362 for (int64_t dim : reInd) {
2363 if ((low[dim] != 0 || high[dim] != 0) && reInd.size() != 1)
2364 return failure();
2365 }
2366 }
2367
2368 // Initialize padding values for collapsed tensors with zeros
2369 ArrayRef<int64_t> expandedPaddedShape = padOp.getType().getShape();
2370 PadDimInfo padDimInfo;
2371 padDimInfo.lowPad.assign(NumElts: reassociations.size(), Elt: rewriter.getIndexAttr(value: 0));
2372 padDimInfo.highPad.assign(NumElts: reassociations.size(), Elt: rewriter.getIndexAttr(value: 0));
2373
2374 // Update padding for dimensions that are not being collapsed, and compute
2375 // the collapsed padded shape.
2376 SmallVector<OpFoldResult> mixedLowPad(padOp.getMixedLowPad());
2377 SmallVector<OpFoldResult> mixedHighPad(padOp.getMixedHighPad());
2378 for (auto [idx, reInd] : llvm::enumerate(First&: reassociations)) {
2379 if (reInd.size() == 1) {
2380 padDimInfo.lowPad[idx] = mixedLowPad[reInd[0]];
2381 padDimInfo.highPad[idx] = mixedHighPad[reInd[0]];
2382 }
2383 SaturatedInteger collapsedSize = SaturatedInteger::wrap(v: 1);
2384 for (int64_t dim : reInd) {
2385 collapsedSize =
2386 collapsedSize * SaturatedInteger::wrap(v: expandedPaddedShape[dim]);
2387 }
2388 padDimInfo.paddedShape.push_back(Elt: collapsedSize.asInteger());
2389 }
2390
2391 return padDimInfo;
2392}
2393
2394class FoldPadWithProducerReshapeOpByCollapsing
2395 : public OpRewritePattern<tensor::PadOp> {
2396public:
2397 FoldPadWithProducerReshapeOpByCollapsing(MLIRContext *context,
2398 ControlFusionFn foldReshapes,
2399 PatternBenefit benefit = 1)
2400 : OpRewritePattern<tensor::PadOp>(context, benefit),
2401 controlFoldingReshapes(std::move(foldReshapes)) {}
2402
2403 LogicalResult matchAndRewrite(tensor::PadOp padOp,
2404 PatternRewriter &rewriter) const override {
2405 tensor::ExpandShapeOp reshapeOp =
2406 padOp.getSource().getDefiningOp<tensor::ExpandShapeOp>();
2407 if (!reshapeOp)
2408 return failure();
2409
2410 if (!controlFoldingReshapes(&padOp.getSourceMutable())) {
2411 return rewriter.notifyMatchFailure(arg&: padOp,
2412 msg: "fusion blocked by control function");
2413 }
2414
2415 SmallVector<ReassociationIndices> reassociations =
2416 reshapeOp.getReassociationIndices();
2417 FailureOr<PadDimInfo> maybeCollapsedPadding =
2418 computeCollapsedPadding(padOp, reassociations, rewriter);
2419 if (failed(Result: maybeCollapsedPadding))
2420 return failure();
2421 PadDimInfo &collapsedPadding = maybeCollapsedPadding.value();
2422
2423 SmallVector<OpFoldResult> expandedPaddedSizes =
2424 reshapeOp.getMixedOutputShape();
2425 AffineExpr d0, d1, d2;
2426 bindDims(ctx: rewriter.getContext(), exprs&: d0, exprs&: d1, exprs&: d2);
2427 auto addMap = AffineMap::get(dimCount: 3, symbolCount: 0, result: {d0 + d1 + d2});
2428 Location loc = reshapeOp->getLoc();
2429 for (auto [reInd, l, h] :
2430 llvm::zip_equal(t&: reassociations, u&: collapsedPadding.lowPad,
2431 args&: collapsedPadding.highPad)) {
2432 if (reInd.size() == 1) {
2433 expandedPaddedSizes[reInd[0]] = affine::makeComposedFoldedAffineApply(
2434 b&: rewriter, loc, map: addMap, operands: {l, h, expandedPaddedSizes[reInd[0]]});
2435 }
2436 }
2437
2438 RankedTensorType collapsedPaddedType =
2439 padOp.getType().clone(shape: collapsedPadding.paddedShape);
2440 auto newPadOp = tensor::PadOp::create(
2441 builder&: rewriter, location: loc, resultType: collapsedPaddedType, source: reshapeOp.getSrc(),
2442 low: collapsedPadding.lowPad, high: collapsedPadding.highPad,
2443 constantPadValue: padOp.getConstantPaddingValue(), nofold: padOp.getNofold());
2444
2445 rewriter.replaceOpWithNewOp<tensor::ExpandShapeOp>(
2446 op: padOp, args: padOp.getResultType(), args: newPadOp.getResult(), args&: reassociations,
2447 args&: expandedPaddedSizes);
2448
2449 return success();
2450 }
2451
2452private:
2453 ControlFusionFn controlFoldingReshapes;
2454};
2455
2456class FoldReshapeWithProducerPadOpByCollapsing
2457 : public OpRewritePattern<tensor::CollapseShapeOp> {
2458public:
2459 FoldReshapeWithProducerPadOpByCollapsing(MLIRContext *context,
2460 ControlFusionFn foldReshapes,
2461 PatternBenefit benefit = 1)
2462 : OpRewritePattern<tensor::CollapseShapeOp>(context, benefit),
2463 controlFoldingReshapes(std::move(foldReshapes)) {}
2464
2465 LogicalResult matchAndRewrite(tensor::CollapseShapeOp reshapeOp,
2466 PatternRewriter &rewriter) const override {
2467 tensor::PadOp padOp = reshapeOp.getSrc().getDefiningOp<tensor::PadOp>();
2468 if (!padOp)
2469 return failure();
2470
2471 if (!controlFoldingReshapes(&reshapeOp.getSrcMutable())) {
2472 return rewriter.notifyMatchFailure(arg&: padOp,
2473 msg: "fusion blocked by control function");
2474 }
2475
2476 SmallVector<ReassociationIndices> reassociations =
2477 reshapeOp.getReassociationIndices();
2478 RankedTensorType collapsedPaddedType = reshapeOp.getResultType();
2479 FailureOr<PadDimInfo> maybeCollapsedPadding =
2480 computeCollapsedPadding(padOp, reassociations, rewriter);
2481 if (failed(Result: maybeCollapsedPadding))
2482 return failure();
2483 PadDimInfo &collapsedPadding = maybeCollapsedPadding.value();
2484
2485 Location loc = reshapeOp->getLoc();
2486 auto newCollapseOp = tensor::CollapseShapeOp::create(
2487 builder&: rewriter, location: loc, src: padOp.getSource(), reassociation: reassociations);
2488
2489 auto newPadOp = tensor::PadOp::create(
2490 builder&: rewriter, location: loc, resultType: collapsedPaddedType, source: newCollapseOp.getResult(),
2491 low: collapsedPadding.lowPad, high: collapsedPadding.highPad,
2492 constantPadValue: padOp.getConstantPaddingValue(), nofold: padOp.getNofold());
2493
2494 rewriter.replaceOp(op: reshapeOp, newValues: newPadOp.getResult());
2495 return success();
2496 }
2497
2498private:
2499 ControlFusionFn controlFoldingReshapes;
2500};
2501
2502/// Pattern to collapse dimensions.
2503template <typename LinalgType>
2504class CollapseLinalgDimensions : public OpRewritePattern<LinalgType> {
2505public:
2506 CollapseLinalgDimensions(MLIRContext *context,
2507 GetCollapsableDimensionsFn collapseDimensions,
2508 PatternBenefit benefit = 1)
2509 : OpRewritePattern<LinalgType>(context, benefit),
2510 controlCollapseDimension(std::move(collapseDimensions)) {}
2511
2512 LogicalResult matchAndRewrite(LinalgType op,
2513 PatternRewriter &rewriter) const override {
2514 SmallVector<ReassociationIndices> collapsableIterationDims =
2515 controlCollapseDimension(op);
2516 if (collapsableIterationDims.empty())
2517 return failure();
2518
2519 // Check if the specified list of dimensions to collapse is a valid list.
2520 if (!areDimSequencesPreserved(op.getIndexingMapsArray(),
2521 collapsableIterationDims)) {
2522 return rewriter.notifyMatchFailure(
2523 op, "specified dimensions cannot be collapsed");
2524 }
2525
2526 std::optional<CollapseResult> collapseResult =
2527 collapseOpIterationDims(op, collapsableIterationDims, rewriter);
2528 if (!collapseResult) {
2529 return rewriter.notifyMatchFailure(op, "failed to collapse dimensions");
2530 }
2531 rewriter.replaceOp(op, collapseResult->results);
2532 return success();
2533 }
2534
2535private:
2536 GetCollapsableDimensionsFn controlCollapseDimension;
2537};
2538
2539} // namespace
2540
2541//===---------------------------------------------------------------------===//
2542// Methods and patterns that fuse constants with linalg.generic operations.
2543//===---------------------------------------------------------------------===//
2544
2545namespace {
2546/// Pattern to fold a generic op with a splat constant/scalar constant. Does not
2547/// handle cases where the constant is not single-valued.
2548class FoldScalarOrSplatConstant : public OpRewritePattern<GenericOp> {
2549public:
2550 FoldScalarOrSplatConstant(MLIRContext *context, PatternBenefit benefit = 1)
2551 : OpRewritePattern<GenericOp>(context, benefit) {}
2552
2553 LogicalResult matchAndRewrite(GenericOp genericOp,
2554 PatternRewriter &rewriter) const override {
2555 if (!genericOp.hasPureTensorSemantics())
2556 return failure();
2557 for (OpOperand *opOperand : genericOp.getDpsInputOperands()) {
2558 Operation *def = opOperand->get().getDefiningOp();
2559 TypedAttr constantAttr;
2560 auto isScalarOrSplatConstantOp = [&constantAttr](Operation *def) -> bool {
2561 {
2562 DenseElementsAttr splatAttr;
2563 if (matchPattern(op: def, pattern: m_Constant<DenseElementsAttr>(bind_value: &splatAttr)) &&
2564 splatAttr.isSplat() &&
2565 splatAttr.getType().getElementType().isIntOrFloat()) {
2566 constantAttr = splatAttr.getSplatValue<TypedAttr>();
2567 return true;
2568 }
2569 }
2570 {
2571 IntegerAttr intAttr;
2572 if (matchPattern(op: def, pattern: m_Constant<IntegerAttr>(bind_value: &intAttr))) {
2573 constantAttr = intAttr;
2574 return true;
2575 }
2576 }
2577 {
2578 FloatAttr floatAttr;
2579 if (matchPattern(op: def, pattern: m_Constant<FloatAttr>(bind_value: &floatAttr))) {
2580 constantAttr = floatAttr;
2581 return true;
2582 }
2583 }
2584 return false;
2585 };
2586
2587 auto resultValue = dyn_cast<OpResult>(Val: opOperand->get());
2588 if (!def || !resultValue || !isScalarOrSplatConstantOp(def))
2589 continue;
2590
2591 // The operands and the indexing_maps of the fused operation the same as
2592 // the operands and indexing_maps of the generic operations with the
2593 // values at the constant index dropped.
2594 SmallVector<AffineMap> fusedIndexMaps;
2595 SmallVector<Value> fusedOperands;
2596 SmallVector<Location> fusedLocs{genericOp.getLoc()};
2597 fusedIndexMaps.reserve(N: genericOp->getNumOperands());
2598 fusedOperands.reserve(N: genericOp.getNumDpsInputs());
2599 fusedLocs.reserve(N: fusedLocs.size() + genericOp.getNumDpsInputs());
2600 for (OpOperand *inputOperand : genericOp.getDpsInputOperands()) {
2601 if (inputOperand == opOperand)
2602 continue;
2603 Value inputValue = inputOperand->get();
2604 fusedIndexMaps.push_back(
2605 Elt: genericOp.getMatchingIndexingMap(opOperand: inputOperand));
2606 fusedOperands.push_back(Elt: inputValue);
2607 fusedLocs.push_back(Elt: inputValue.getLoc());
2608 }
2609 for (OpOperand &outputOperand : genericOp.getDpsInitsMutable())
2610 fusedIndexMaps.push_back(
2611 Elt: genericOp.getMatchingIndexingMap(opOperand: &outputOperand));
2612
2613 // Check if the operation shapes to loops map is computable.
2614 if (!inversePermutation(
2615 map: concatAffineMaps(maps: fusedIndexMaps, context: rewriter.getContext()))) {
2616 return rewriter.notifyMatchFailure(
2617 arg&: genericOp, msg: "fused op loop bound computation failed");
2618 }
2619
2620 // Create a constant scalar value from the splat constant.
2621 Value scalarConstant =
2622 arith::ConstantOp::create(builder&: rewriter, location: def->getLoc(), value: constantAttr);
2623
2624 SmallVector<Value> outputOperands = genericOp.getOutputs();
2625 auto fusedOp =
2626 GenericOp::create(builder&: rewriter, location: rewriter.getFusedLoc(locs: fusedLocs),
2627 result_tensors: genericOp->getResultTypes(),
2628 /*inputs=*/fusedOperands,
2629 /*outputs=*/outputOperands,
2630 indexing_maps: rewriter.getAffineMapArrayAttr(values: fusedIndexMaps),
2631 iterator_types: genericOp.getIteratorTypes(),
2632 /*doc=*/nullptr,
2633 /*library_call=*/nullptr);
2634
2635 // Map the block argument corresponding to the replaced argument with the
2636 // scalar constant.
2637 Region &region = genericOp->getRegion(index: 0);
2638 Block &entryBlock = *region.begin();
2639 IRMapping mapping;
2640 mapping.map(from: entryBlock.getArgument(i: opOperand->getOperandNumber()),
2641 to: scalarConstant);
2642 Region &fusedRegion = fusedOp->getRegion(index: 0);
2643 rewriter.cloneRegionBefore(region, parent&: fusedRegion, before: fusedRegion.begin(),
2644 mapping);
2645 rewriter.replaceOp(op: genericOp, newValues: fusedOp->getResults());
2646 return success();
2647 }
2648 return failure();
2649 }
2650};
2651
2652} // namespace
2653
2654//===---------------------------------------------------------------------===//
2655// Miscellaneous patterns that help fusion.
2656//===---------------------------------------------------------------------===//
2657
2658namespace {
2659/// Forces `outs` operands of linalg operations to use `tensor.empty` if the
2660/// value of the `outs` operand is not used within the op. This is only
2661/// implemented for `linalg.generic` operations for now, but should hold for all
2662/// linalg structured ops.
2663struct RemoveOutsDependency : public OpRewritePattern<GenericOp> {
2664 using OpRewritePattern<GenericOp>::OpRewritePattern;
2665
2666 LogicalResult matchAndRewrite(GenericOp op,
2667 PatternRewriter &rewriter) const override {
2668 rewriter.startOpModification(op);
2669 bool modifiedOutput = false;
2670 Location loc = op.getLoc();
2671 for (OpOperand &opOperand : op.getDpsInitsMutable()) {
2672 if (!op.payloadUsesValueFromOperand(opOperand: &opOperand)) {
2673 Value operandVal = opOperand.get();
2674 auto operandType = dyn_cast<RankedTensorType>(Val: operandVal.getType());
2675 if (!operandType)
2676 continue;
2677
2678 // If outs is sparse, leave it to the sparsifier.
2679 if (sparse_tensor::getSparseTensorEncoding(type: operandVal.getType()))
2680 continue;
2681
2682 // If outs is already an `empty` operation, nothing to do.
2683 auto definingOp = operandVal.getDefiningOp<tensor::EmptyOp>();
2684 if (definingOp)
2685 continue;
2686 modifiedOutput = true;
2687 SmallVector<OpFoldResult> mixedSizes =
2688 tensor::getMixedSizes(builder&: rewriter, loc, value: operandVal);
2689 Value emptyTensor = tensor::EmptyOp::create(
2690 builder&: rewriter, location: loc, sizes: mixedSizes, elementType: operandType.getElementType());
2691 op->setOperand(idx: opOperand.getOperandNumber(), value: emptyTensor);
2692 }
2693 }
2694 if (!modifiedOutput) {
2695 rewriter.cancelOpModification(op);
2696 return failure();
2697 }
2698 rewriter.finalizeOpModification(op);
2699 return success();
2700 }
2701};
2702
2703/// Fold linalg.fill into linalg.generic
2704struct FoldFillWithGenericOp : public OpRewritePattern<GenericOp> {
2705 using OpRewritePattern<GenericOp>::OpRewritePattern;
2706
2707 LogicalResult matchAndRewrite(GenericOp genericOp,
2708 PatternRewriter &rewriter) const override {
2709 if (!genericOp.hasPureTensorSemantics())
2710 return failure();
2711 bool fillFound = false;
2712 Block &payload = genericOp.getRegion().front();
2713 for (OpOperand *opOperand : genericOp.getDpsInputOperands()) {
2714 if (!genericOp.payloadUsesValueFromOperand(opOperand))
2715 continue;
2716 FillOp fillOp = opOperand->get().getDefiningOp<FillOp>();
2717 if (!fillOp)
2718 continue;
2719 fillFound = true;
2720 Value fillVal = fillOp.value();
2721 auto resultType =
2722 cast<RankedTensorType>(Val: fillOp.result().getType()).getElementType();
2723 Value convertedVal =
2724 convertScalarToDtype(b&: rewriter, loc: fillOp.getLoc(), operand: fillVal, toType: resultType,
2725 /*isUnsignedCast =*/false);
2726 rewriter.replaceAllUsesWith(
2727 from: payload.getArgument(i: opOperand->getOperandNumber()), to: convertedVal);
2728 }
2729 return success(IsSuccess: fillFound);
2730 }
2731};
2732} // namespace
2733
2734void mlir::linalg::populateFoldReshapeOpsByExpansionPatterns(
2735 RewritePatternSet &patterns,
2736 const ControlFusionFn &controlFoldingReshapes) {
2737 patterns.add<FoldReshapeWithGenericOpByExpansion>(arg: patterns.getContext(),
2738 args: controlFoldingReshapes);
2739 patterns.add<FoldPadWithProducerReshapeOpByExpansion>(arg: patterns.getContext(),
2740 args: controlFoldingReshapes);
2741 patterns.add<FoldReshapeWithProducerPadOpByExpansion>(arg: patterns.getContext(),
2742 args: controlFoldingReshapes);
2743 patterns.add<FoldWithProducerReshapeOpByExpansion>(arg: patterns.getContext(),
2744 args: controlFoldingReshapes);
2745}
2746
2747void mlir::linalg::populateFoldReshapeOpsByCollapsingPatterns(
2748 RewritePatternSet &patterns,
2749 const ControlFusionFn &controlFoldingReshapes) {
2750 patterns.add<FoldWithProducerReshapeOpByCollapsing>(arg: patterns.getContext(),
2751 args: controlFoldingReshapes);
2752 patterns.add<FoldPadWithProducerReshapeOpByCollapsing>(
2753 arg: patterns.getContext(), args: controlFoldingReshapes);
2754 patterns.add<FoldReshapeWithProducerPadOpByCollapsing>(
2755 arg: patterns.getContext(), args: controlFoldingReshapes);
2756 patterns.add<FoldReshapeWithGenericOpByCollapsing>(arg: patterns.getContext(),
2757 args: controlFoldingReshapes);
2758}
2759
2760void mlir::linalg::populateElementwiseOpsFusionPatterns(
2761 RewritePatternSet &patterns,
2762 const ControlFusionFn &controlElementwiseOpsFusion) {
2763 auto *context = patterns.getContext();
2764 patterns.add<FuseElementwiseOps>(arg&: context, args: controlElementwiseOpsFusion);
2765 patterns.add<FoldFillWithGenericOp, FoldScalarOrSplatConstant,
2766 RemoveOutsDependency>(arg&: context);
2767 // Add the patterns that clean up dead operands and results.
2768 populateEraseUnusedOperandsAndResultsPatterns(patterns);
2769}
2770
2771void mlir::linalg::populateSplitElementwiseOpsWithConcatInputsPatterns(
2772 RewritePatternSet &patterns) {
2773 patterns.add<SplitElementwiseOpWithConcatInputs>(arg: patterns.getContext());
2774}
2775
2776void mlir::linalg::populateCollapseDimensions(
2777 RewritePatternSet &patterns,
2778 const GetCollapsableDimensionsFn &controlCollapseDimensions) {
2779 patterns.add<CollapseLinalgDimensions<linalg::GenericOp>,
2780 CollapseLinalgDimensions<linalg::CopyOp>>(
2781 arg: patterns.getContext(), args: controlCollapseDimensions);
2782}
2783
2784//===---------------------------------------------------------------------===//
2785// Passes
2786//===---------------------------------------------------------------------===//
2787
2788namespace {
2789
2790/// Pass that fuses generic ops on tensors. Used only for testing.
2791// TODO(ravishankarm): This pass is to be deprecated. The efficacy of the
2792// patterns added here heavily depends on the cost function used. Having an
2793// opinionated pass of this form is not recommended. Deprecate this pass in
2794// favor of test passes that check the functionality of each of the patterns
2795// added here individually.
2796struct LinalgElementwiseOpFusionPass
2797 : public impl::LinalgElementwiseOpFusionPassBase<
2798 LinalgElementwiseOpFusionPass> {
2799 using impl::LinalgElementwiseOpFusionPassBase<
2800 LinalgElementwiseOpFusionPass>::LinalgElementwiseOpFusionPassBase;
2801 void runOnOperation() override {
2802 Operation *op = getOperation();
2803 MLIRContext *context = op->getContext();
2804 RewritePatternSet patterns(context);
2805
2806 // Add folding with reshape by expansion patterns.
2807 ControlFusionFn defaultControlFn = [](OpOperand *fusedOperand) {
2808 Operation *producer = fusedOperand->get().getDefiningOp();
2809 return producer && producer->hasOneUse();
2810 };
2811
2812 // Add elementwise op fusion patterns.
2813 populateSplitElementwiseOpsWithConcatInputsPatterns(patterns);
2814 populateElementwiseOpsFusionPatterns(patterns, controlElementwiseOpsFusion: defaultControlFn);
2815 populateFoldReshapeOpsByExpansionPatterns(patterns, controlFoldingReshapes: defaultControlFn);
2816 tensor::populateBubbleUpExpandShapePatterns(patterns);
2817
2818 // General canonicalization patterns.
2819 affine::AffineApplyOp::getCanonicalizationPatterns(results&: patterns, context);
2820 GenericOp::getCanonicalizationPatterns(results&: patterns, context);
2821 tensor::ExpandShapeOp::getCanonicalizationPatterns(results&: patterns, context);
2822 tensor::CollapseShapeOp::getCanonicalizationPatterns(results&: patterns, context);
2823 context->getLoadedDialect<LinalgDialect>()->getCanonicalizationPatterns(
2824 results&: patterns);
2825
2826 // Add constant folding patterns.
2827 populateConstantFoldLinalgOperations(patterns, controlFn: defaultControlFn);
2828
2829 // Use TopDownTraversal for compile time reasons.
2830 (void)applyPatternsGreedily(op, patterns: std::move(patterns),
2831 config: GreedyRewriteConfig().setUseTopDownTraversal());
2832 }
2833};
2834
2835} // namespace
2836