1//===- ParallelLoopFusion.cpp - Code to perform loop 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 loop fusion on parallel loops.
10//
11//===----------------------------------------------------------------------===//
12
13#include "mlir/Dialect/SCF/Transforms/Passes.h"
14
15#include "mlir/Analysis/AliasAnalysis.h"
16#include "mlir/Dialect/Affine/IR/AffineOps.h"
17#include "mlir/Dialect/Index/IR/IndexOps.h"
18#include "mlir/Dialect/MemRef/IR/MemRef.h"
19#include "mlir/Dialect/MemRef/Utils/MemRefUtils.h"
20#include "mlir/Dialect/SCF/IR/SCF.h"
21#include "mlir/Dialect/SCF/Transforms/Transforms.h"
22#include "mlir/Dialect/SCF/Utils/Utils.h"
23#include "mlir/Dialect/Utils/IndexingUtils.h"
24#include "mlir/Dialect/Utils/StaticValueUtils.h"
25#include "mlir/Dialect/Vector/IR/VectorOps.h"
26#include "mlir/IR/Builders.h"
27#include "mlir/IR/BuiltinTypes.h"
28#include "mlir/IR/IRMapping.h"
29#include "mlir/IR/Matchers.h"
30#include "mlir/IR/OpDefinition.h"
31#include "mlir/IR/OperationSupport.h"
32#include "mlir/IR/PatternMatch.h"
33#include "mlir/IR/Value.h"
34#include "mlir/Interfaces/SideEffectInterfaces.h"
35
36#include "llvm/ADT/STLExtras.h"
37#include "llvm/ADT/SetVector.h"
38#include "llvm/ADT/SmallBitVector.h"
39#include "llvm/ADT/TypeSwitch.h"
40#include "llvm/Support/InterleavedRange.h"
41
42#include "llvm/Support/DebugLog.h"
43#include <numeric>
44#include <optional>
45#include <tuple>
46#define DEBUG_TYPE "parallel-loop-fusion"
47
48namespace mlir {
49#define GEN_PASS_DEF_SCFPARALLELLOOPFUSION
50#include "mlir/Dialect/SCF/Transforms/Passes.h.inc"
51} // namespace mlir
52
53using namespace mlir;
54using namespace mlir::scf;
55
56/// Verify there are no nested ParallelOps.
57static bool hasNestedParallelOp(ParallelOp ploop) {
58 auto walkResult =
59 ploop.getBody()->walk(callback: [](ParallelOp) { return WalkResult::interrupt(); });
60 return walkResult.wasInterrupted();
61}
62
63/// Verify equal iteration spaces.
64static bool equalIterationSpaces(ParallelOp firstPloop,
65 ParallelOp secondPloop) {
66 if (firstPloop.getNumLoops() != secondPloop.getNumLoops() ||
67 firstPloop.getUnsignedCmp() != secondPloop.getUnsignedCmp())
68 return false;
69
70 // Two bounds match if they are the same value, or if both are constants
71 // holding the same value. The latter matters because equivalent bounds are
72 // often materialized by distinct `arith.constant` ops, which leaves the
73 // iteration spaces equal even though the SSA values differ.
74 auto matchOperands = [&](const OperandRange &lhs,
75 const OperandRange &rhs) -> bool {
76 // TODO: Extend this to support aliases.
77 return std::equal(first1: lhs.begin(), last1: lhs.end(), first2: rhs.begin(),
78 binary_pred: [](Value lhsValue, Value rhsValue) {
79 if (lhsValue == rhsValue)
80 return true;
81 std::optional<int64_t> lhsConst =
82 getConstantIntValue(ofr: lhsValue);
83 std::optional<int64_t> rhsConst =
84 getConstantIntValue(ofr: rhsValue);
85 return lhsConst && rhsConst && *lhsConst == *rhsConst;
86 });
87 };
88 return matchOperands(firstPloop.getLowerBound(),
89 secondPloop.getLowerBound()) &&
90 matchOperands(firstPloop.getUpperBound(),
91 secondPloop.getUpperBound()) &&
92 matchOperands(firstPloop.getStep(), secondPloop.getStep());
93}
94
95/// Check if both operations are the same type of memory write op and
96/// write to the same memory location (same buffer and same indices).
97static bool opsWriteSameMemLocation(Operation *op1, Operation *op2) {
98 if (!op1 || !op2 || op1->getName() != op2->getName())
99 return false;
100 if (op1 == op2)
101 return true;
102 // support only these memory-writing ops for now
103 if (!isa<memref::StoreOp, vector::TransferWriteOp, vector::StoreOp>(Val: op1))
104 return false;
105 bool opsAreIdentical =
106 llvm::TypeSwitch<Operation *, bool>(op1)
107 .Case(caseFn: [&](memref::StoreOp storeOp1) {
108 auto storeOp2 = cast<memref::StoreOp>(Val: op2);
109 return (storeOp1.getMemRef() == storeOp2.getMemRef()) &&
110 (storeOp1.getIndices() == storeOp2.getIndices());
111 })
112 .Case(caseFn: [&](vector::TransferWriteOp writeOp1) {
113 auto writeOp2 = cast<vector::TransferWriteOp>(Val: op2);
114 return (writeOp1.getBase() == writeOp2.getBase()) &&
115 (writeOp1.getIndices() == writeOp2.getIndices()) &&
116 (writeOp1.getMask() == writeOp2.getMask()) &&
117 (writeOp1.getValueToStore().getType() ==
118 writeOp2.getValueToStore().getType()) &&
119 (writeOp1.getInBounds() == writeOp2.getInBounds());
120 })
121 .Case(caseFn: [&](vector::StoreOp vecStoreOp1) {
122 auto vecStoreOp2 = cast<vector::StoreOp>(Val: op2);
123 return (vecStoreOp1.getBase() == vecStoreOp2.getBase()) &&
124 (vecStoreOp1.getIndices() == vecStoreOp2.getIndices()) &&
125 (vecStoreOp1.getValueToStore().getType() ==
126 vecStoreOp2.getValueToStore().getType()) &&
127 (vecStoreOp1.getAlignment() == vecStoreOp2.getAlignment()) &&
128 (vecStoreOp1.getNontemporal() ==
129 vecStoreOp2.getNontemporal());
130 })
131 .Default(defaultFn: [](Operation *) { return false; });
132 return opsAreIdentical;
133}
134
135/// Check if val1 (from the first parallel loop) and val2 (from the
136/// second) are equivalent, considering the mapping of induction variables from
137/// the first to the second parallel loop.
138static bool valsAreEquivalent(Value val1, Value val2,
139 const IRMapping &loopsIVsMap) {
140 if (val1 == val2 || loopsIVsMap.lookupOrDefault(from: val1) == val2 ||
141 loopsIVsMap.lookupOrDefault(from: val2) == val1)
142 return true;
143 Operation *val1DefOp = val1.getDefiningOp();
144 Operation *val2DefOp = val2.getDefiningOp();
145 if (!val1DefOp || !val2DefOp)
146 return false;
147 if (!isMemoryEffectFree(op: val1DefOp) || !isMemoryEffectFree(op: val2DefOp))
148 return false;
149 return OperationEquivalence::isEquivalentTo(
150 lhs: val1DefOp, rhs: val2DefOp,
151 checkEquivalent: [&](Value v1, Value v2) {
152 return success(IsSuccess: loopsIVsMap.lookupOrDefault(from: v1) == v2 ||
153 loopsIVsMap.lookupOrDefault(from: v2) == v1);
154 },
155 /*markEquivalent=*/nullptr, flags: OperationEquivalence::Flags::IgnoreLocations);
156}
157
158/// If the `expr` value is the result of an integer addition of `base` and a
159/// constant, return the constant.
160static std::optional<int64_t> getAddConstant(Value expr, Value base,
161 const IRMapping &loopsIVsMap) {
162 if (auto addOp = expr.getDefiningOp<arith::AddIOp>()) {
163 if (auto constOp = getConstantIntValue(ofr: addOp.getLhs());
164 constOp && valsAreEquivalent(val1: addOp.getRhs(), val2: base, loopsIVsMap))
165 return constOp.value();
166 if (auto constOp = getConstantIntValue(ofr: addOp.getRhs());
167 constOp && valsAreEquivalent(val1: addOp.getLhs(), val2: base, loopsIVsMap))
168 return constOp.value();
169 return std::nullopt;
170 }
171
172 if (auto addOp = expr.getDefiningOp<index::AddOp>()) {
173 if (auto constOp = getConstantIntValue(ofr: addOp.getLhs());
174 constOp && valsAreEquivalent(val1: addOp.getRhs(), val2: base, loopsIVsMap))
175 return constOp.value();
176 if (auto constOp = getConstantIntValue(ofr: addOp.getRhs());
177 constOp && valsAreEquivalent(val1: addOp.getLhs(), val2: base, loopsIVsMap))
178 return constOp.value();
179 return std::nullopt;
180 }
181
182 if (auto applyOp = expr.getDefiningOp<affine::AffineApplyOp>()) {
183 AffineMap map = applyOp.getAffineMap();
184 if (map.getNumResults() != 1 || map.getNumDims() != 1 ||
185 map.getNumSymbols() != 0)
186 return std::nullopt;
187 if (!valsAreEquivalent(val1: applyOp.getOperand(i: 0), val2: base, loopsIVsMap))
188 return std::nullopt;
189 AffineExpr result = map.getResult(idx: 0);
190 auto bin = dyn_cast<AffineBinaryOpExpr>(Val&: result);
191 if (!bin || bin.getKind() != AffineExprKind::Add)
192 return std::nullopt;
193 auto lhsDim = dyn_cast<AffineDimExpr>(Val: bin.getLHS());
194 auto rhsDim = dyn_cast<AffineDimExpr>(Val: bin.getRHS());
195 auto lhsConst = dyn_cast<AffineConstantExpr>(Val: bin.getLHS());
196 auto rhsConst = dyn_cast<AffineConstantExpr>(Val: bin.getRHS());
197 if (lhsConst && rhsDim)
198 return lhsConst.getValue();
199 if (rhsConst && lhsDim)
200 return rhsConst.getValue();
201 }
202 return std::nullopt;
203}
204
205// Return true if the scalar load index may hit any element covered by a
206// vector.store/transfer_write along a single memref dimension. Supported cases:
207//
208// 1) Direct index match (with optional offset):
209// vector.transfer_write %v, %A[%i] : vector<4xf32>, memref<...>
210// %x = memref.load %A[%i] : memref<...>
211//
212// 2) Loop IV range intersects the write range:
213// vector.transfer_write %v, %A[%c0] : vector<4xf32>, memref<...>
214// scf.for %k = %c0 to %c4 step %c1 { %x = memref.load %A[%k] }
215//
216// 3) Constant index (or IV + constant) within the write range:
217// vector.transfer_write %v, %A[%c0] : vector<4xf32>, memref<...>
218// %x = memref.load %A[%c2] : memref<...>
219// %y = memref.load %A[%i + %c1] : memref<...>
220//
221// Args:
222// - loadIndex: index used by the scalar load for this dimension.
223// - offset: subview offset for the base memref dimension (if any).
224// - writeIndex: index used by the transfer_write for this dimension. Can be
225// null if the dim was dropped by a rank reducing subview, whose result is
226// written by the vector.write.
227// - extent: vector size along this dimension (number of elements written).
228// - loopsIVsMap: IV equivalence map between fused loops.
229static bool loadIndexWithinWriteRange(Value loadIndex, OpFoldResult offset,
230 Value writeIndex, int64_t extent,
231 const IRMapping &loopsIVsMap) {
232 if (extent <= 0)
233 return false;
234
235 // Extract constant loop bounds for loop IVs (e.g. from scf.for).
236 auto getConstLoopBoundsForIV =
237 [](Value index) -> std::optional<std::tuple<int64_t, int64_t, int64_t>> {
238 auto blockArg = dyn_cast<BlockArgument>(Val&: index);
239 if (!blockArg)
240 return std::nullopt;
241 auto *parentOp = blockArg.getOwner()->getParentOp();
242 auto loopLike = dyn_cast<LoopLikeOpInterface>(Val: parentOp);
243 if (!loopLike)
244 return std::nullopt;
245 auto ranges = getConstLoopBounds(loopOp: loopLike);
246 if (ranges.empty())
247 return std::nullopt;
248
249 auto ivs = loopLike.getLoopInductionVars();
250 if (!ivs)
251 return std::nullopt;
252 auto it = llvm::find(Range&: *ivs, Val: blockArg);
253 if (it == ivs->end())
254 return std::nullopt;
255 unsigned pos = std::distance(first: ivs->begin(), last: it);
256 if (pos >= ranges.size())
257 return std::nullopt;
258 auto [lb, ub, step] = ranges[pos];
259 return std::make_tuple(args&: lb, args&: ub, args&: step);
260 };
261
262 std::optional<int64_t> offsetConst = getConstantIntValue(ofr: offset);
263 std::optional<int64_t> writeConst =
264 writeIndex ? getConstantIntValue(ofr: writeIndex) : std::optional<int64_t>(0);
265 if (!writeConst && writeIndex) {
266 // Treat single-iteration IVs as constants for matching.
267 if (auto bounds = getConstLoopBoundsForIV(writeIndex)) {
268 auto [lb, ub, step] = *bounds;
269 if (step > 0 && ub == lb + step)
270 writeConst = lb;
271 }
272 }
273
274 // Check whether a loop IV is fully contained in a constant write range.
275 auto loopIVWithinRange = [](int64_t lb, int64_t ub, int64_t step,
276 int64_t rangeStart, int64_t rangeExtent) -> bool {
277 if (rangeExtent <= 0 || step <= 0)
278 return false;
279 if (ub <= lb)
280 return false;
281 int64_t rangeEnd = rangeStart + rangeExtent;
282 return lb >= rangeStart && ub <= rangeEnd;
283 };
284
285 if (offsetConst && writeConst) {
286 // Constant start of the write range; check constant load or loop IV range.
287 int64_t start = *offsetConst + *writeConst;
288 if (auto loadConst = getConstantIntValue(ofr: loadIndex))
289 return (*loadConst >= start && *loadConst < start + extent);
290 if (auto bounds = getConstLoopBoundsForIV(loadIndex)) {
291 auto [lb, ub, step] = *bounds;
292 return loopIVWithinRange(lb, ub, step, start, extent);
293 }
294 }
295
296 if (writeIndex) {
297 // Direct IV match (or IV + constant) against the write index.
298 if (offsetConst && *offsetConst == 0 &&
299 valsAreEquivalent(val1: loadIndex, val2: writeIndex, loopsIVsMap))
300 return true;
301 if (auto addConst = getAddConstant(expr: loadIndex, base: writeIndex, loopsIVsMap)) {
302 // Match load index of the form writeIndex + C within the write extent.
303 if (offsetConst) {
304 int64_t start = *offsetConst;
305 return (*addConst >= start && *addConst < start + extent);
306 }
307 }
308 return false;
309 }
310
311 if (auto offsetVal = dyn_cast<Value>(Val&: offset)) {
312 // Exact match when extent is 1 and the load hits the offset value.
313 if (extent == 1 && valsAreEquivalent(val1: loadIndex, val2: offsetVal, loopsIVsMap))
314 return true;
315 }
316
317 return false;
318}
319
320/// Return the base memref value used by the given memory op.
321static Value getBaseMemref(Operation *op) {
322 // TODO: use the common interface for memory ops once available.
323 return llvm::TypeSwitch<Operation *, Value>(op)
324 .Case(caseFn: [&](memref::LoadOp load) { return load.getMemRef(); })
325 .Case(caseFn: [&](memref::StoreOp store) { return store.getMemRef(); })
326 .Case(caseFn: [&](vector::TransferReadOp read) { return read.getBase(); })
327 .Case(caseFn: [&](vector::TransferWriteOp write) { return write.getBase(); })
328 .Case(caseFn: [&](vector::LoadOp load) { return load.getBase(); })
329 .Case(caseFn: [&](vector::StoreOp store) { return store.getBase(); })
330 .Default(defaultFn: [](Operation *) { return Value(); });
331}
332
333/// Recognize scalar memref.load of an element produced by a vector write
334/// (vector.transfer_write or vector.store, optionally through a rank-reducing
335/// unit-stride subview) of the same buffer. This covers the pattern where a
336/// vector write stores a full lane pack and a subsequent scalar load reads an
337/// element from that lane pack. EXAMPLE:
338/// vector.transfer_write %V, %arg[%x, %y, ..., 0] {in_bounds = [true]} :
339/// vector<4xf32>, memref<4xf32, strided<[1], offset: ?>>
340/// scf.for %iter = %c0 to %c4 step %c1 iter_args(...) -> (f32) {
341/// %0 = memref.load %arg[%x, %y, ..., %iter] : memref<1x128x16x4xf32>
342/// ...
343/// }
344///
345static bool isLoadOnWrittenVector(memref::LoadOp loadOp, Value writeBase,
346 ValueRange writeIndices, VectorType vecTy,
347 ArrayRef<int64_t> vectorDimForWriteDim,
348 const IRMapping &ivsMap) {
349 if (!vecTy)
350 return false;
351
352 Value base = writeBase;
353 // The write base if there is no subview, or the subview source otherwise.
354 MemrefValue baseMemref = nullptr;
355 SmallVector<OpFoldResult> offsets;
356 llvm::SmallBitVector droppedDims;
357 bool hasSubview = false;
358 auto *ctx = loadOp.getContext();
359 if (auto subView = base.getDefiningOp<memref::SubViewOp>()) {
360 if (!subView.hasUnitStride())
361 return false;
362 baseMemref = cast<MemrefValue>(Val: subView.getSource());
363 offsets = llvm::to_vector(Range: subView.getMixedOffsets());
364 droppedDims = subView.getDroppedDims();
365 hasSubview = true;
366 } else {
367 baseMemref = dyn_cast<MemrefValue>(Val&: base);
368 if (!baseMemref)
369 return false;
370 }
371
372 auto loadIndices = loadOp.getIndices();
373 unsigned baseRank = baseMemref.getType().getRank();
374 if ((loadOp.getMemref() != baseMemref) || (loadIndices.size() != baseRank))
375 return false;
376
377 unsigned writeRank = writeIndices.size();
378 if ((!hasSubview && writeRank != baseRank) ||
379 (hasSubview && offsets.size() != baseRank) ||
380 (vectorDimForWriteDim.size() != writeRank))
381 return false;
382
383 auto zeroAttr = IntegerAttr::get(type: IndexType::get(context: ctx), value: 0);
384 unsigned writeMemrefDim = 0;
385 for (unsigned baseDim : llvm::seq(Size: baseRank)) {
386 bool wasDropped = (hasSubview && droppedDims.test(Idx: baseDim));
387 int64_t vectorDim = !wasDropped ? vectorDimForWriteDim[writeMemrefDim] : -1;
388 int64_t extent = 1;
389 if (vectorDim >= 0) {
390 int64_t dimSize = vecTy.getDimSize(idx: vectorDim);
391 if (dimSize == ShapedType::kDynamic)
392 return false;
393 extent = dimSize;
394 }
395 Value writeIndex = !wasDropped ? writeIndices[writeMemrefDim] : Value();
396 OpFoldResult offset =
397 hasSubview ? offsets[baseDim] : OpFoldResult(zeroAttr);
398 if (!loadIndexWithinWriteRange(loadIndex: loadIndices[baseDim], offset, writeIndex,
399 extent, loopsIVsMap: ivsMap))
400 return false;
401 if (!wasDropped)
402 ++writeMemrefDim;
403 }
404
405 return true;
406}
407
408/// Recognize scalar memref.load of an element produced by a
409/// vector.transfer_write
410static bool loadMatchesVectorWrite(memref::LoadOp loadOp,
411 vector::TransferWriteOp writeOp,
412 const IRMapping &ivsMap) {
413 auto vecTy = dyn_cast<VectorType>(Val: writeOp.getVector().getType());
414 if (!vecTy)
415 return false;
416
417 // A masked write may not write the element that the load reads.
418 if (writeOp.getMask() || writeOp.isMasked())
419 return false;
420
421 unsigned writeRank = writeOp.getIndices().size();
422 AffineMap permutationMap = writeOp.getPermutationMap();
423 if (!permutationMap.isProjectedPermutation() ||
424 permutationMap.getNumResults() != vecTy.getRank() ||
425 permutationMap.getNumDims() != writeRank)
426 return false;
427
428 SmallVector<int64_t> vectorDimForWriteDim(writeRank, -1);
429 for (unsigned vecDim = 0; vecDim < permutationMap.getNumResults(); ++vecDim) {
430 auto dimExpr = dyn_cast<AffineDimExpr>(Val: permutationMap.getResult(idx: vecDim));
431 if (!dimExpr)
432 return false;
433 unsigned writeDim = dimExpr.getPosition();
434 if (writeDim >= writeRank || vectorDimForWriteDim[writeDim] != -1)
435 return false;
436 vectorDimForWriteDim[writeDim] = vecDim;
437 }
438
439 return isLoadOnWrittenVector(loadOp, writeBase: writeOp.getBase(), writeIndices: writeOp.getIndices(),
440 vecTy, vectorDimForWriteDim, ivsMap);
441}
442
443/// Recognize scalar memref.load of an element produced by a vector.store
444static bool loadMatchesVectorStore(memref::LoadOp loadOp,
445 vector::StoreOp storeOp,
446 const IRMapping &ivsMap) {
447 auto vecTy = dyn_cast<VectorType>(Val: storeOp.getValueToStore().getType());
448 if (!vecTy)
449 return false;
450
451 unsigned writeRank = storeOp.getIndices().size();
452 if (vecTy.getRank() > writeRank)
453 return false;
454
455 SmallVector<int64_t> vectorDimForWriteDim(writeRank, -1);
456 unsigned vecRank = vecTy.getRank();
457 for (unsigned i = 0; i < vecRank; ++i) {
458 unsigned writeDim = writeRank - vecRank + i;
459 vectorDimForWriteDim[writeDim] = i;
460 }
461
462 return isLoadOnWrittenVector(loadOp, writeBase: storeOp.getBase(), writeIndices: storeOp.getIndices(),
463 vecTy, vectorDimForWriteDim, ivsMap);
464}
465
466/// Check if both operations access the same positions of the same
467/// buffer, but one of the two does it through a rank-reducing full subview of
468/// the buffer (the other's base). EXAMPLE:
469/// memref.store %a, %buf[%c0, %i, %j] : memref<1x2x2xf32>
470/// %alias = memref.subview %buf[0, 0, 0][1, 2, 2][1, 1, 1]: memref<1x2x2xf32>
471/// to memref<2x2xf32>
472/// %val = memref.load %alias[%i, %j] : memref<2x2xf32>
473template <typename OpTy1, typename OpTy2>
474static bool opsAccessSameIndicesViaRankReducingSubview(
475 OpTy1 op1, OpTy2 op2, const IRMapping &firstToSecondPloopIVsMap,
476 OpBuilder &b) {
477 auto base1 = cast<MemrefValue>(getBaseMemref(op1));
478 auto base2 = cast<MemrefValue>(getBaseMemref(op2));
479 if (!base1 || !base2)
480 return false;
481
482 auto accessThroughTrivialSubviewIsSame =
483 [&b](memref::SubViewOp subView, ValueRange subViewAccess,
484 ValueRange sourceAccess, const IRMapping &ivsMap) -> bool {
485 SmallVector<Value> resolvedSubviewAccess;
486 LogicalResult resolved = resolveSourceIndicesRankReducingSubview(
487 loc: subView.getLoc(), b, subViewOp: subView, indices: subViewAccess, sourceIndices&: resolvedSubviewAccess);
488 if (failed(Result: resolved) ||
489 (resolvedSubviewAccess.size() != sourceAccess.size()))
490 return false;
491 for (auto [dimIdx, resolvedIndex] :
492 llvm::enumerate(First&: resolvedSubviewAccess)) {
493 if (!matchPattern(value: resolvedIndex, pattern: m_Zero()) &&
494 !valsAreEquivalent(val1: resolvedIndex, val2: sourceAccess[dimIdx], loopsIVsMap: ivsMap))
495 return false;
496 }
497 return true;
498 };
499
500 // Case 1: op1 uses a subview of op2's base.
501 if (auto subView = base1.template getDefiningOp<memref::SubViewOp>();
502 subView &&
503 memref::isSameViewOrTrivialAlias(
504 a: base2, b: cast<MemrefValue>(subView.getSource())) &&
505 accessThroughTrivialSubviewIsSame(subView, op1.getIndices(),
506 op2.getIndices(),
507 firstToSecondPloopIVsMap))
508 return true;
509
510 // Case 2: op2 uses a subview of op1's base.
511 if (auto subView = base2.template getDefiningOp<memref::SubViewOp>();
512 subView &&
513 memref::isSameViewOrTrivialAlias(
514 a: base1, b: cast<MemrefValue>(subView.getSource())) &&
515 accessThroughTrivialSubviewIsSame(subView, op2.getIndices(),
516 op1.getIndices(),
517 firstToSecondPloopIVsMap))
518 return true;
519
520 return false;
521}
522
523/// Check if both memory read/write operations access the same indices
524/// (considering also the mapping of induction variables from the first to the
525/// second parallel loop).
526template <typename OpTy1, typename OpTy2>
527static bool opsAccessSameIndices(OpTy1 op1, OpTy2 op2,
528 const IRMapping &loopsIVsMap, OpBuilder &b) {
529 auto indices1 = op1.getIndices();
530 auto indices2 = op2.getIndices();
531 if (indices1.size() != indices2.size())
532 return opsAccessSameIndicesViaRankReducingSubview(op1, op2, loopsIVsMap, b);
533 for (auto [idx1, idx2] : llvm::zip(indices1, indices2)) {
534 if (!valsAreEquivalent(idx1, idx2, loopsIVsMap))
535 return false;
536 }
537 return true;
538}
539
540/// Check if the loadOp reads from the same memory location (same buffer,
541/// same indices and same properties) as written by the storeOp.
542static bool
543loadsFromSameMemoryLocationWrittenBy(Operation *loadOp, Operation *storeOp,
544 const IRMapping &firstToSecondPloopIVsMap,
545 OpBuilder &b) {
546 if (!loadOp || !storeOp)
547 return false;
548 // Support only these memory-reading ops for now
549 if (!isa<memref::LoadOp, vector::TransferReadOp, vector::LoadOp>(Val: loadOp))
550 return false;
551 bool accessSameMemory =
552 llvm::TypeSwitch<Operation *, bool>(loadOp)
553 .Case(caseFn: [&](memref::LoadOp memLoadOp) {
554 if (auto memStoreOp = dyn_cast<memref::StoreOp>(Val: storeOp))
555 return opsAccessSameIndices(op1: memLoadOp, op2: memStoreOp,
556 loopsIVsMap: firstToSecondPloopIVsMap, b);
557 if (auto vecWriteOp = dyn_cast<vector::TransferWriteOp>(Val: storeOp))
558 return loadMatchesVectorWrite(loadOp: memLoadOp, writeOp: vecWriteOp,
559 ivsMap: firstToSecondPloopIVsMap);
560 if (auto vecStoreOp = dyn_cast<vector::StoreOp>(Val: storeOp))
561 return loadMatchesVectorStore(loadOp: memLoadOp, storeOp: vecStoreOp,
562 ivsMap: firstToSecondPloopIVsMap);
563 return false;
564 })
565 .Case(caseFn: [&](vector::TransferReadOp vecReadOp) {
566 auto vecWriteOp = dyn_cast<vector::TransferWriteOp>(Val: storeOp);
567 if (!vecWriteOp)
568 return false;
569 // A write masked by `vector.mask` may write fewer elements than
570 // the read reads.
571 return opsAccessSameIndices(op1: vecReadOp, op2: vecWriteOp,
572 loopsIVsMap: firstToSecondPloopIVsMap, b) &&
573 (vecReadOp.getVectorType() == vecWriteOp.getVectorType()) &&
574 (vecReadOp.getPermutationMap() ==
575 vecWriteOp.getPermutationMap()) &&
576 (vecReadOp.getMask() == vecWriteOp.getMask()) &&
577 !vecWriteOp.isMasked() &&
578 (vecReadOp.getInBounds() == vecWriteOp.getInBounds());
579 })
580 .Case(caseFn: [&](vector::LoadOp vecLoadOp) {
581 auto vecStoreOp = dyn_cast<vector::StoreOp>(Val: storeOp);
582 if (!vecStoreOp)
583 return false;
584 return opsAccessSameIndices(op1: vecLoadOp, op2: vecStoreOp,
585 loopsIVsMap: firstToSecondPloopIVsMap, b) &&
586 (vecLoadOp.getVectorType() == vecStoreOp.getVectorType()) &&
587 (vecLoadOp.getAlignment() == vecStoreOp.getAlignment());
588 })
589 .Default(defaultFn: [](Operation *) { return false; });
590 return accessSameMemory;
591}
592
593static Value getStoreOpTargetBuffer(Operation *op) {
594 return llvm::TypeSwitch<Operation *, Value>(op)
595 .Case(caseFn: [&](memref::StoreOp storeOp) { return storeOp.getMemRef(); })
596 .Case(caseFn: [&](vector::TransferWriteOp writeOp) { return writeOp.getBase(); })
597 .Case(caseFn: [&](vector::StoreOp vecStoreOp) { return vecStoreOp.getBase(); })
598 .Default(defaultFn: [](Operation *) { return Value(); });
599}
600
601/// To be called when `mayAlias(val1, val2)` is true. Check if the potential
602/// aliasing between the loadOp and storeOp can be resolved by analyzing their
603/// access patterns.
604static bool canResolveAlias(Operation *loadOp, Operation *storeOp,
605 const IRMapping &loopsIVsMap) {
606 if (auto transfWriteOp = dyn_cast<vector::TransferWriteOp>(Val: storeOp);
607 transfWriteOp && isa<memref::LoadOp>(Val: loadOp))
608 return loadMatchesVectorWrite(loadOp: cast<memref::LoadOp>(Val: loadOp), writeOp: transfWriteOp,
609 ivsMap: loopsIVsMap);
610 if (auto vecStoreOp = dyn_cast<vector::StoreOp>(Val: storeOp);
611 vecStoreOp && isa<memref::LoadOp>(Val: loadOp))
612 return loadMatchesVectorStore(loadOp: cast<memref::LoadOp>(Val: loadOp), storeOp: vecStoreOp,
613 ivsMap: loopsIVsMap);
614 return false;
615}
616
617/// Check that the parallel loops have no mixed access to the same buffers.
618/// Return `true` if the second parallel loop does not read or write the buffers
619/// written by the first loop using different indices.
620static bool haveNoDataDependenciesExceptSameIndex(
621 ParallelOp firstPloop, ParallelOp secondPloop,
622 const IRMapping &firstToSecondPloopIndices,
623 llvm::function_ref<bool(Value, Value)> mayAlias, OpBuilder &b) {
624 // Map buffers to their store/write ops in the firstPloop
625 DenseMap<Value, SmallVector<Operation *>> bufferStoresInFirstPloop;
626 // Record all the memory buffers used in store/write ops found in firstPloop
627 llvm::SmallSetVector<Value, 4> buffersWrittenInFirstPloop;
628
629 auto collectStoreOpsInWalk = [&](Operation *op) {
630 auto memOpInterf = dyn_cast_if_present<MemoryEffectOpInterface>(Val: op);
631 // Ignore ops that don't write to memory
632 if (!memOpInterf || (!memOpInterf.hasEffect<MemoryEffects::Write>() &&
633 !memOpInterf.hasEffect<MemoryEffects::Free>()))
634 return WalkResult::advance();
635
636 // Only these memory-writing ops are supported for now:
637 // memref.store, vector.transfer_write, vector.store
638 Value storeOpBase = getStoreOpTargetBuffer(op);
639 if (!storeOpBase)
640 return WalkResult::interrupt();
641
642 // Expect the base operand to be a Memref
643 MemrefValue storeOpBaseMemref = dyn_cast<MemrefValue>(Val&: storeOpBase);
644 if (!storeOpBaseMemref)
645 return WalkResult::interrupt();
646 // Get the original memref buffer, skipping full view-like ops
647 Value buffer = memref::skipFullyAliasingOperations(source: storeOpBaseMemref);
648 bufferStoresInFirstPloop[buffer].push_back(Elt: op);
649 buffersWrittenInFirstPloop.insert(X: buffer);
650 return WalkResult::advance();
651 };
652
653 // Walk the first parallel loop to collect all store/write ops and their
654 // target buffers
655 if (firstPloop.getBody()->walk(callback&: collectStoreOpsInWalk).wasInterrupted())
656 return false;
657
658 // Check that this load/read op encountered while walking the second parallel
659 // loop does not have incompatible data dependencies with the store/write ops
660 // collected from the first parallel loop: the loops can be fused only if in
661 // the 2nd loop there are no loads/stores from/to the buffers written in the
662 // 1st loop, except when on the same exact memory location (same indices) as
663 // written in the 1st loop.
664 auto checkLoadInWalkHasNoIncompatibleDataDeps = [&](Operation *loadOp) {
665 auto memOpInterf = dyn_cast_if_present<MemoryEffectOpInterface>(Val: loadOp);
666 // To be conservative, we should stop on ops that don't advertise their
667 // memory effects. However, many ops don't implement MemoryEffectOpInterface
668 // yet, so for now we just skip them.
669 // TODO: once more ops add MemoryEffectOpInterface, interrupt the walk here.
670 if (!memOpInterf &&
671 !loadOp->hasTrait<mlir::OpTrait::HasRecursiveMemoryEffects>())
672 return WalkResult::advance();
673 // Ignore ops that don't read from memory, and wrapping ops that have nested
674 // memory effects (e.g. loops, conditionals) as they will be analyzed when
675 // visiting their nested ops.
676 if ((!memOpInterf &&
677 loadOp->hasTrait<mlir::OpTrait::HasRecursiveMemoryEffects>()) ||
678 (memOpInterf && !memOpInterf.hasEffect<MemoryEffects::Read>()))
679 return WalkResult::advance();
680 // Support only these memory-reading ops for now
681 if (!isa<memref::LoadOp, vector::TransferReadOp, vector::LoadOp>(Val: loadOp) ||
682 !isa<MemrefValue>(Val: loadOp->getOperand(idx: 0)))
683 return WalkResult::interrupt();
684
685 MemrefValue loadOpBase = cast<MemrefValue>(Val: loadOp->getOperand(idx: 0));
686 MemrefValue loadedOrigBuf = memref::skipFullyAliasingOperations(source: loadOpBase);
687
688 for (Value storedMem : buffersWrittenInFirstPloop)
689 if ((storedMem != loadedOrigBuf) && mayAlias(storedMem, loadedOrigBuf) &&
690 !llvm::all_of(Range&: bufferStoresInFirstPloop[storedMem],
691 P: [&](Operation *storeOp) {
692 return canResolveAlias(loadOp, storeOp,
693 loopsIVsMap: firstToSecondPloopIndices);
694 })) {
695 return WalkResult::interrupt();
696 }
697
698 auto writeOpsIt = bufferStoresInFirstPloop.find(Val: loadedOrigBuf);
699 if (writeOpsIt == bufferStoresInFirstPloop.end())
700 return WalkResult::advance();
701 // Store/write ops to this buffer in the firstPloop
702 SmallVector<mlir::Operation *> &writeOps = writeOpsIt->second;
703
704 // If the first loop has no writes to this buffer, continue
705 if (writeOps.empty())
706 return WalkResult::advance();
707
708 Operation *writeOp = writeOps.front();
709
710 // In the first parallel loop, multiple writes to the same memref are
711 // allowed only on the same memory location
712 if (!llvm::all_of(Range&: writeOps, P: [&](Operation *otherWriteOp) {
713 return opsWriteSameMemLocation(op1: writeOp, op2: otherWriteOp);
714 })) {
715 return WalkResult::interrupt();
716 }
717
718 // Check that the load in secondPloop reads from the same memory location as
719 // written by the corresponding store in firstPloop
720 if (!loadsFromSameMemoryLocationWrittenBy(loadOp, storeOp: writeOp,
721 firstToSecondPloopIVsMap: firstToSecondPloopIndices, b)) {
722 return WalkResult::interrupt();
723 }
724
725 return WalkResult::advance();
726 };
727
728 // Walk the second parallel loop to check load/read ops against the stores
729 // collected from the first parallel loop.
730 return !secondPloop.getBody()
731 ->walk(callback&: checkLoadInWalkHasNoIncompatibleDataDeps)
732 .wasInterrupted();
733}
734
735/// Check that in each loop there are no read ops on the buffers written
736/// by the other loop, except when reading from the same exact memory location
737/// (same indices) as written in the other loop.
738static bool
739noIncompatibleDataDependencies(ParallelOp firstPloop, ParallelOp secondPloop,
740 const IRMapping &firstToSecondPloopIndices,
741 llvm::function_ref<bool(Value, Value)> mayAlias,
742 OpBuilder &b) {
743 if (!haveNoDataDependenciesExceptSameIndex(
744 firstPloop, secondPloop, firstToSecondPloopIndices, mayAlias, b))
745 return false;
746
747 IRMapping secondToFirstPloopIndices;
748 secondToFirstPloopIndices.map(from: secondPloop.getBody()->getArguments(),
749 to: firstPloop.getBody()->getArguments());
750 return haveNoDataDependenciesExceptSameIndex(
751 firstPloop: secondPloop, secondPloop: firstPloop, firstToSecondPloopIndices: secondToFirstPloopIndices, mayAlias, b);
752}
753
754/// Check if fusion of the two parallel loops is legal:
755/// i.e. no nested parallel loops, equal iteration spaces,
756/// and no incompatible data dependencies between the loops.
757static bool isFusionLegal(ParallelOp firstPloop, ParallelOp secondPloop,
758 const IRMapping &firstToSecondPloopIndices,
759 llvm::function_ref<bool(Value, Value)> mayAlias,
760 OpBuilder &b) {
761 if (hasNestedParallelOp(ploop: firstPloop) || hasNestedParallelOp(ploop: secondPloop) ||
762 !equalIterationSpaces(firstPloop, secondPloop) ||
763 !noIncompatibleDataDependencies(firstPloop, secondPloop,
764 firstToSecondPloopIndices, mayAlias, b))
765 return false;
766
767 // We are fusing first loop into second, make sure there are no users of the
768 // first loop results between loops.
769 DominanceInfo dom;
770 for (Operation *user : firstPloop->getUsers()) {
771 if (!dom.properlyDominates(a: secondPloop, b: user, /*enclosingOpOk*/ false))
772 return false;
773 }
774 return true;
775}
776
777// Returns new parallel loop where two loops matching indices param are
778// interchanged
779static std::optional<ParallelOp>
780interchangeLoops(OpBuilder &builder, ParallelOp &loop,
781 const ArrayRef<int64_t> &indices) {
782 assert(loop.getNumLoops() == indices.size());
783 if (loop.getNumLoops() < 2)
784 return std::nullopt;
785
786 // Replace the parallel loop with the same parallel loop.
787 builder.setInsertionPoint(loop);
788 SmallVector<Value> newLB =
789 applyPermutation(input: SmallVector<Value>(loop.getLowerBound()), permutation: indices);
790 SmallVector<Value> newUB =
791 applyPermutation(input: SmallVector<Value>(loop.getUpperBound()), permutation: indices);
792 SmallVector<Value> newStep =
793 applyPermutation(input: SmallVector<Value>(loop.getStep()), permutation: indices);
794 auto newOp =
795 ParallelOp::create(builder, location: loop.getLoc(), lowerBounds: newLB, upperBounds: newUB, steps: newStep,
796 initVals: loop.getInitVals(), bodyBuilderFn: nullptr, unsignedCmp: loop.getUnsignedCmp());
797 auto ivs = loop.getInductionVars();
798 SmallVector<Value> newIvs = applyPermutation(
799 input: newOp.getInductionVars(), permutation: invertPermutationVector(permutation: indices));
800 IRMapping mapping;
801 for (auto [iv, riv] : llvm::zip(t&: ivs, u&: newIvs)) {
802 mapping.map(from: iv, to: riv);
803 }
804
805 // Copy parallel loop body
806 auto b = OpBuilder::atBlockBegin(block: newOp.getBody());
807 for (auto &o : loop.getNumReductions()
808 ? loop.getBodyRegion().front()
809 : loop.getBodyRegion().front().without_terminator()) {
810 b.clone(op&: o, mapper&: mapping);
811 }
812 return newOp;
813}
814
815struct LoopIV {
816 Value lBound, uBound, step;
817 bool operator!=(LoopIV const &other) const { return !(*this == other); }
818 bool operator==(LoopIV const &other) const {
819 return lBound == other.lBound && uBound == other.uBound &&
820 step == other.step;
821 }
822};
823
824template <>
825struct llvm::DenseMapInfo<LoopIV> {
826 static inline bool isEqual(const LoopIV &lhs, const LoopIV &rhs) {
827 return (lhs == rhs);
828 }
829
830 static inline unsigned getHashValue(const LoopIV &val) {
831 return llvm::hash_combine(
832 args: DenseMapInfo<mlir::Value>::getHashValue(val: val.lBound),
833 args: DenseMapInfo<mlir::Value>::getHashValue(val: val.uBound),
834 args: DenseMapInfo<mlir::Value>::getHashValue(val: val.step));
835 }
836};
837
838// Returns vector of candidate permutation indices vectors,
839// can be empty. Caps the number of extra candidate permutations
840// explored to avoid combinatorial explosion. This makes the search
841// intentionally incomplete.
842static SmallVector<SmallVector<int64_t>>
843computeCandidateInterchangePermutations(ParallelOp &firstPloop,
844 ParallelOp &secondPloop,
845 int permBudget = 120) {
846 // Check preconditions
847 if (firstPloop.getNumLoops() < 2 ||
848 firstPloop.getNumLoops() != secondPloop.getNumLoops())
849 return {};
850
851 SmallVector<LoopIV> firstIVs(firstPloop.getNumLoops());
852 SmallVector<LoopIV> secondIVs(secondPloop.getNumLoops());
853 llvm::SmallSetVector<LoopIV, 6> unique;
854 for (unsigned index : llvm::seq(Size: firstPloop.getNumLoops())) {
855 firstIVs[index].lBound = firstPloop.getLowerBound()[index];
856 firstIVs[index].uBound = firstPloop.getUpperBound()[index];
857 firstIVs[index].step = firstPloop.getStep()[index];
858 secondIVs[index].lBound = secondPloop.getLowerBound()[index];
859 secondIVs[index].uBound = secondPloop.getUpperBound()[index];
860 secondIVs[index].step = secondPloop.getStep()[index];
861 unique.insert(X: firstIVs[index]);
862 }
863
864 SmallVector<bool> diffIVs(firstPloop.getNumLoops());
865 llvm::transform(
866 Range: llvm::zip(t&: firstIVs, u&: secondIVs), d_first: diffIVs.begin(),
867 F: [](auto const &pair) { return std::get<0>(pair) != std::get<1>(pair); });
868
869 SmallVector<int64_t> indices;
870 for (auto [idx, val] : enumerate(First&: diffIVs))
871 if (val)
872 indices.push_back(Elt: idx);
873
874 // Not a permutation shortcut
875 if (indices.size() == 1)
876 return {};
877
878 // Initialize with identity permutations
879 SmallVector<int64_t> basic(firstIVs.size());
880 std::iota(first: basic.begin(), last: basic.end(), value: 0);
881
882 if (indices.empty() && unique.size() == firstIVs.size())
883 return {};
884
885 if (indices.size() > 1) {
886 // Determine whether the iteration space of the first loop is a permutation
887 // of the second and collect remaps.
888 SmallVector<int64_t> remaps;
889 for (auto fIdx : indices) {
890 for (auto sIdx : indices) {
891 // can be remapped
892 if (fIdx != sIdx && firstIVs[fIdx] == secondIVs[sIdx] &&
893 remaps.end() == std::find(first: remaps.begin(), last: remaps.end(), val: sIdx)) {
894 remaps.push_back(Elt: sIdx);
895 break;
896 }
897 }
898 }
899
900 // Not a permutation
901 if (indices.size() != remaps.size())
902 return {};
903
904 // compose permutation indices
905 for (auto [from, to] : zip(t&: indices, u&: remaps)) {
906 basic[from] = to;
907 }
908
909 LDBG() << "Collected basic permutations: "
910 << llvm::interleaved_array(R: basic);
911
912 // All axes are unique, no further permutatons needed
913 if (unique.size() == firstIVs.size()) {
914 return {basic};
915 }
916 }
917
918 //
919 // Permute equal axes
920 assert(unique.size() != firstIVs.size() &&
921 "Expected at least two equal axes");
922
923 // Collect equal axes to groups
924 SmallVector<SmallVector<int64_t>> extraResults{basic};
925 SmallVector<SmallVector<int64_t>> groups;
926 for (auto iv : unique) {
927 SmallVector<int64_t> group;
928 for (unsigned index : llvm::seq(Size: firstIVs.size())) {
929 if (firstIVs[index] == iv)
930 group.push_back(Elt: index);
931 }
932 if (group.size() > 1)
933 groups.push_back(Elt: std::move(group));
934 }
935
936 // Permute axes groups
937 SmallVector<SmallVector<int64_t>> rmpdGroups(groups);
938 bool repeat = true;
939 while (repeat && permBudget) {
940 repeat = false;
941 for (auto const &[group, groupRemaps] : zip(t&: groups, u&: rmpdGroups)) {
942 repeat |= std::next_permutation(first: groupRemaps.begin(), last: groupRemaps.end());
943 if (repeat)
944 break;
945 }
946
947 if (repeat) {
948 SmallVector<int64_t> extra(basic);
949 for (auto const &[group, groupRemaps] : zip(t&: groups, u&: rmpdGroups)) {
950 for (auto [from, to] : zip(t&: group, u&: groupRemaps))
951 extra[from] = basic[to];
952 }
953 if (basic != extra) {
954 LDBG() << "Collected extra permutations: "
955 << llvm::interleaved_array(R: extra);
956
957 extraResults.push_back(Elt: std::move(extra));
958 permBudget--;
959 }
960 }
961 }
962
963 return extraResults;
964}
965
966/// Prepend operations of firstPloop's body into secondPloop's body.
967/// Update secondPloop with new loop.
968static void applyLoopFusion(ParallelOp &firstPloop, ParallelOp &secondPloop,
969 OpBuilder &builder) {
970 Block *block1 = firstPloop.getBody();
971 Block *block2 = secondPloop.getBody();
972 ValueRange inits1 = firstPloop.getInitVals();
973 ValueRange inits2 = secondPloop.getInitVals();
974
975 SmallVector<Value> newInitVars(inits1.begin(), inits1.end());
976 newInitVars.append(in_start: inits2.begin(), in_end: inits2.end());
977
978 IRRewriter b(builder);
979 b.setInsertionPoint(secondPloop);
980 auto newSecondPloop =
981 ParallelOp::create(builder&: b, location: secondPloop.getLoc(), lowerBounds: secondPloop.getLowerBound(),
982 upperBounds: secondPloop.getUpperBound(), steps: secondPloop.getStep(),
983 initVals: newInitVars, bodyBuilderFn: nullptr, unsignedCmp: secondPloop.getUnsignedCmp());
984
985 Block *newBlock = newSecondPloop.getBody();
986 auto term1 = cast<ReduceOp>(Val: block1->getTerminator());
987 auto term2 = cast<ReduceOp>(Val: block2->getTerminator());
988
989 b.inlineBlockBefore(source: block2, dest: newBlock, before: newBlock->begin(),
990 argValues: newBlock->getArguments());
991 b.inlineBlockBefore(source: block1, dest: newBlock, before: newBlock->begin(),
992 argValues: newBlock->getArguments());
993
994 ValueRange results = newSecondPloop.getResults();
995 if (!results.empty()) {
996 b.setInsertionPointToEnd(newBlock);
997
998 ValueRange reduceArgs1 = term1.getOperands();
999 ValueRange reduceArgs2 = term2.getOperands();
1000 SmallVector<Value> newReduceArgs(reduceArgs1.begin(), reduceArgs1.end());
1001 newReduceArgs.append(in_start: reduceArgs2.begin(), in_end: reduceArgs2.end());
1002
1003 auto newReduceOp = scf::ReduceOp::create(builder&: b, location: term2.getLoc(), operands: newReduceArgs);
1004
1005 for (auto &&[i, reg] : llvm::enumerate(First: llvm::concat<Region>(
1006 Ranges: term1.getReductions(), Ranges: term2.getReductions()))) {
1007 Block &oldRedBlock = reg.front();
1008 Block &newRedBlock = newReduceOp.getReductions()[i].front();
1009 b.inlineBlockBefore(source: &oldRedBlock, dest: &newRedBlock, before: newRedBlock.begin(),
1010 argValues: newRedBlock.getArguments());
1011 }
1012
1013 firstPloop.replaceAllUsesWith(values: results.take_front(n: inits1.size()));
1014 secondPloop.replaceAllUsesWith(values: results.take_back(n: inits2.size()));
1015 }
1016 term1->erase();
1017 term2->erase();
1018 firstPloop.erase();
1019 secondPloop.erase();
1020 secondPloop = newSecondPloop;
1021}
1022
1023/// Check fusion pre-conditions and call fusion if it is possible
1024static void fuseIfLegal(ParallelOp firstPloop, ParallelOp &secondPloop,
1025 OpBuilder builder,
1026 llvm::function_ref<bool(Value, Value)> mayAlias) {
1027 Block *block1 = firstPloop.getBody();
1028 Block *block2 = secondPloop.getBody();
1029 IRMapping firstToSecondPloopIndices;
1030 firstToSecondPloopIndices.map(from: block1->getArguments(), to: block2->getArguments());
1031
1032 if (isFusionLegal(firstPloop, secondPloop, firstToSecondPloopIndices,
1033 mayAlias, b&: builder)) {
1034 applyLoopFusion(firstPloop, secondPloop, builder);
1035 return;
1036 }
1037
1038 // If iteration space of the second parallel loop is a permutation of the
1039 // first one then interchange iteration space of the second parallel loop
1040 // and re-asses possibility of fusion.
1041 for (auto &perms :
1042 computeCandidateInterchangePermutations(firstPloop, secondPloop)) {
1043 OpBuilder::InsertionGuard guard(builder);
1044 LDBG() << "Applied permutation: " << llvm::interleaved_array(R: perms);
1045
1046 auto newLoop = interchangeLoops(builder, loop&: secondPloop, indices: perms);
1047 firstToSecondPloopIndices.clear();
1048 firstToSecondPloopIndices.map(from: block1->getArguments(),
1049 to: newLoop->getBody()->getArguments());
1050 if (!isFusionLegal(firstPloop, secondPloop: *newLoop, firstToSecondPloopIndices,
1051 mayAlias, b&: builder)) {
1052 LDBG() << "Rejected: " << newLoop;
1053
1054 newLoop->erase();
1055 continue;
1056 }
1057
1058 secondPloop.replaceAllUsesWith(values: newLoop->getResults());
1059 secondPloop->erase();
1060 secondPloop = *newLoop;
1061 applyLoopFusion(firstPloop, secondPloop, builder);
1062 break;
1063 }
1064}
1065
1066void mlir::scf::naivelyFuseParallelOps(
1067 Region &region, llvm::function_ref<bool(Value, Value)> mayAlias) {
1068 OpBuilder b(region);
1069 // Consider every single block and attempt to fuse adjacent loops.
1070 SmallVector<SmallVector<ParallelOp>, 1> ploopChains;
1071 for (auto &block : region) {
1072 ploopChains.clear();
1073 ploopChains.push_back(Elt: {});
1074
1075 // Not using `walk()` to traverse only top-level parallel loops and also
1076 // make sure that there are no side-effecting ops between the parallel
1077 // loops.
1078 bool noSideEffects = true;
1079 for (auto &op : block) {
1080 if (auto ploop = dyn_cast<ParallelOp>(Val&: op)) {
1081 if (noSideEffects) {
1082 ploopChains.back().push_back(Elt: ploop);
1083 } else {
1084 ploopChains.push_back(Elt: {ploop});
1085 noSideEffects = true;
1086 }
1087 continue;
1088 }
1089 // TODO: Handle region side effects properly.
1090 noSideEffects &= isMemoryEffectFree(op: &op) && op.getNumRegions() == 0;
1091 }
1092 for (MutableArrayRef<ParallelOp> ploops : ploopChains) {
1093 for (int i = 0, e = ploops.size(); i + 1 < e; ++i)
1094 fuseIfLegal(firstPloop: ploops[i], secondPloop&: ploops[i + 1], builder: b, mayAlias);
1095 }
1096 }
1097}
1098
1099namespace {
1100struct ParallelLoopFusion
1101 : public impl::SCFParallelLoopFusionBase<ParallelLoopFusion> {
1102 void runOnOperation() override {
1103 auto &aa = getAnalysis<AliasAnalysis>();
1104
1105 auto mayAlias = [&](Value val1, Value val2) -> bool {
1106 // If the memref is defined in one of the parallel loops body, careful
1107 // alias analysis is needed.
1108 // TODO: check if this is still needed as a separate check.
1109 auto val1Def = val1.getDefiningOp();
1110 auto val2Def = val2.getDefiningOp();
1111 auto val1Loop =
1112 val1Def ? val1Def->getParentOfType<ParallelOp>() : nullptr;
1113 auto val2Loop =
1114 val2Def ? val2Def->getParentOfType<ParallelOp>() : nullptr;
1115 if (val1Loop != val2Loop)
1116 return true;
1117
1118 return !aa.alias(lhs: val1, rhs: val2).isNo();
1119 };
1120
1121 getOperation()->walk(callback: [&](Operation *child) {
1122 for (Region &region : child->getRegions())
1123 naivelyFuseParallelOps(region, mayAlias);
1124 });
1125 }
1126};
1127} // namespace
1128
1129std::unique_ptr<Pass> mlir::createParallelLoopFusionPass() {
1130 return std::make_unique<ParallelLoopFusion>();
1131}
1132