1//===- AffineAnalysis.cpp - Affine structures analysis routines -----------===//
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 miscellaneous analysis routines for affine structures
10// (expressions, maps, sets), and other utilities relying on such analysis.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Dialect/Affine/Analysis/AffineAnalysis.h"
15#include "mlir/Analysis/Presburger/IntegerRelation.h"
16#include "mlir/Analysis/Presburger/PresburgerSpace.h"
17#include "mlir/Analysis/SliceAnalysis.h"
18#include "mlir/Dialect/Affine/Analysis/LoopAnalysis.h"
19#include "mlir/Dialect/Affine/Analysis/Utils.h"
20#include "mlir/Dialect/Affine/IR/AffineOps.h"
21#include "mlir/Dialect/Affine/IR/AffineValueMap.h"
22#include "mlir/Dialect/Arith/IR/Arith.h"
23#include "mlir/Interfaces/SideEffectInterfaces.h"
24#include "mlir/Interfaces/ViewLikeInterface.h"
25#include "llvm/ADT/TypeSwitch.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/raw_ostream.h"
28#include <optional>
29
30#define DEBUG_TYPE "affine-analysis"
31
32using namespace mlir;
33using namespace affine;
34using namespace presburger;
35
36/// Get the value that is being reduced by `pos`-th reduction in the loop if
37/// such a reduction can be performed by affine parallel loops. This assumes
38/// floating-point operations are commutative. On success, `kind` will be the
39/// reduction kind suitable for use in affine parallel loop builder. If the
40/// reduction is not supported, returns null.
41static Value getSupportedReduction(AffineForOp forOp, unsigned pos,
42 arith::AtomicRMWKind &kind) {
43 SmallVector<Operation *> combinerOps;
44 Value reducedVal =
45 matchReduction(iterCarriedArgs: forOp.getRegionIterArgs(), redPos: pos, combinerOps);
46 if (!reducedVal)
47 return nullptr;
48
49 // Expected only one combiner operation.
50 if (combinerOps.size() > 1)
51 return nullptr;
52
53 Operation *combinerOp = combinerOps.back();
54 std::optional<arith::AtomicRMWKind> maybeKind =
55 TypeSwitch<Operation *, std::optional<arith::AtomicRMWKind>>(combinerOp)
56 .Case(caseFn: [](arith::AddFOp) { return arith::AtomicRMWKind::addf; })
57 .Case(caseFn: [](arith::MulFOp) { return arith::AtomicRMWKind::mulf; })
58 .Case(caseFn: [](arith::AddIOp) { return arith::AtomicRMWKind::addi; })
59 .Case(caseFn: [](arith::AndIOp) { return arith::AtomicRMWKind::andi; })
60 .Case(caseFn: [](arith::OrIOp) { return arith::AtomicRMWKind::ori; })
61 .Case(caseFn: [](arith::MulIOp) { return arith::AtomicRMWKind::muli; })
62 .Case(
63 caseFn: [](arith::MinimumFOp) { return arith::AtomicRMWKind::minimumf; })
64 .Case(
65 caseFn: [](arith::MaximumFOp) { return arith::AtomicRMWKind::maximumf; })
66 .Case(caseFn: [](arith::MinSIOp) { return arith::AtomicRMWKind::mins; })
67 .Case(caseFn: [](arith::MaxSIOp) { return arith::AtomicRMWKind::maxs; })
68 .Case(caseFn: [](arith::MinUIOp) { return arith::AtomicRMWKind::minu; })
69 .Case(caseFn: [](arith::MaxUIOp) { return arith::AtomicRMWKind::maxu; })
70 .Case(caseFn: [](arith::XOrIOp) { return arith::AtomicRMWKind::xori; })
71 .Case(caseFn: [](arith::MaxNumFOp) { return arith::AtomicRMWKind::maxnumf; })
72 .Case(caseFn: [](arith::MinNumFOp) { return arith::AtomicRMWKind::minnumf; })
73 .Default(defaultFn: [](Operation *) -> std::optional<arith::AtomicRMWKind> {
74 return std::nullopt;
75 });
76 if (!maybeKind)
77 return nullptr;
78
79 kind = *maybeKind;
80 return reducedVal;
81}
82
83/// Populate `supportedReductions` with descriptors of the supported reductions.
84void mlir::affine::getSupportedReductions(
85 AffineForOp forOp, SmallVectorImpl<LoopReduction> &supportedReductions) {
86 unsigned numIterArgs = forOp.getNumIterOperands();
87 if (numIterArgs == 0)
88 return;
89 supportedReductions.reserve(N: numIterArgs);
90 for (unsigned i = 0; i < numIterArgs; ++i) {
91 arith::AtomicRMWKind kind;
92 if (Value value = getSupportedReduction(forOp, pos: i, kind))
93 supportedReductions.emplace_back(Args: LoopReduction{.kind: kind, .iterArgPosition: i, .value: value});
94 }
95}
96
97/// Returns true if `forOp' is a parallel loop. If `parallelReductions` is
98/// provided, populates it with descriptors of the parallelizable reductions and
99/// treats them as not preventing parallelization.
100bool mlir::affine::isLoopParallel(
101 AffineForOp forOp, SmallVectorImpl<LoopReduction> *parallelReductions) {
102 unsigned numIterArgs = forOp.getNumIterOperands();
103
104 // Loop is not parallel if it has SSA loop-carried dependences and reduction
105 // detection is not requested.
106 if (numIterArgs > 0 && !parallelReductions)
107 return false;
108
109 // Find supported reductions of requested.
110 if (parallelReductions) {
111 getSupportedReductions(forOp, supportedReductions&: *parallelReductions);
112 // Return later to allow for identifying all parallel reductions even if the
113 // loop is not parallel.
114 if (parallelReductions->size() != numIterArgs)
115 return false;
116 }
117
118 // Check memory dependences.
119 return isLoopMemoryParallel(forOp);
120}
121
122/// Returns true if `v` is allocated locally to `enclosingOp` -- i.e., it is
123/// allocated by an operation nested within `enclosingOp`.
124static bool isLocallyDefined(Value v, Operation *enclosingOp) {
125 Operation *defOp = v.getDefiningOp();
126 if (!defOp)
127 return false;
128
129 if (hasSingleEffect<MemoryEffects::Allocate>(op: defOp, value: v) &&
130 enclosingOp->isProperAncestor(other: defOp))
131 return true;
132
133 // Aliasing ops.
134 auto viewOp = dyn_cast<ViewLikeOpInterface>(Val: defOp);
135 return viewOp && isLocallyDefined(v: viewOp.getViewSource(), enclosingOp);
136}
137
138/// Returns true if all memory effects of `op` free memory that is allocated
139/// locally to `enclosingOp`.
140static bool freesOnlyLocallyDefined(Operation *op, Operation *enclosingOp) {
141 auto memOp = dyn_cast<MemoryEffectOpInterface>(Val: op);
142 if (!memOp)
143 return false;
144 SmallVector<MemoryEffects::EffectInstance> effects;
145 memOp.getEffects(effects);
146 return !effects.empty() &&
147 llvm::all_of(Range&: effects, P: [&](const MemoryEffects::EffectInstance &e) {
148 return isa<MemoryEffects::Free>(Val: e.getEffect()) && e.getValue() &&
149 isLocallyDefined(v: e.getValue(), enclosingOp);
150 });
151}
152
153bool mlir::affine::isLoopMemoryParallel(AffineForOp forOp) {
154 // Any memref-typed iteration arguments are treated as serializing.
155 if (llvm::any_of(Range: forOp.getResultTypes(), P: llvm::IsaPred<BaseMemRefType>))
156 return false;
157
158 // Collect all load and store ops in loop nest rooted at 'forOp'.
159 SmallVector<Operation *, 8> loadAndStoreOps;
160 auto walkResult = forOp.walk(callback: [&](Operation *op) -> WalkResult {
161 if (auto readOp = dyn_cast<AffineReadOpInterface>(Val: op)) {
162 // Memrefs that are allocated inside `forOp` need not be considered.
163 if (!isLocallyDefined(v: readOp.getMemRef(), enclosingOp: forOp))
164 loadAndStoreOps.push_back(Elt: op);
165 } else if (auto writeOp = dyn_cast<AffineWriteOpInterface>(Val: op)) {
166 // Filter out stores the same way as above.
167 if (!isLocallyDefined(v: writeOp.getMemRef(), enclosingOp: forOp))
168 loadAndStoreOps.push_back(Elt: op);
169 } else if (!isa<AffineForOp, AffineYieldOp, AffineIfOp>(Val: op) &&
170 !hasSingleEffect<MemoryEffects::Allocate>(op) &&
171 !freesOnlyLocallyDefined(op, enclosingOp: forOp) && !isMemoryEffectFree(op)) {
172 // Alloc-like ops inside `forOp` are fine (they don't impact parallelism)
173 // as long as they don't escape the loop (which has been checked above).
174 // So are dealloc-like ops freeing such allocations. Freeing other memory
175 // may race with accesses to it from other iterations.
176 return WalkResult::interrupt();
177 }
178
179 return WalkResult::advance();
180 });
181
182 // Stop early if the loop has unknown ops with side effects.
183 if (walkResult.wasInterrupted())
184 return false;
185
186 // Dep check depth would be number of enclosing loops + 1.
187 unsigned depth = getNestingDepth(op: forOp) + 1;
188
189 // Check dependences between all pairs of ops in 'loadAndStoreOps'.
190 for (auto *srcOp : loadAndStoreOps) {
191 MemRefAccess srcAccess(srcOp);
192 for (auto *dstOp : loadAndStoreOps) {
193 MemRefAccess dstAccess(dstOp);
194 DependenceResult result =
195 checkMemrefAccessDependence(srcAccess, dstAccess, loopDepth: depth);
196 if (result.value != DependenceResult::NoDependence)
197 return false;
198 }
199 }
200 return true;
201}
202
203/// Returns the sequence of AffineApplyOp Operations operation in
204/// 'affineApplyOps', which are reachable via a search starting from 'operands',
205/// and ending at operands which are not defined by AffineApplyOps.
206// TODO: Add a method to AffineApplyOp which forward substitutes the
207// AffineApplyOp into any user AffineApplyOps.
208void mlir::affine::getReachableAffineApplyOps(
209 ArrayRef<Value> operands, SmallVectorImpl<Operation *> &affineApplyOps) {
210 struct State {
211 // The ssa value for this node in the DFS traversal.
212 Value value;
213 // The operand index of 'value' to explore next during DFS traversal.
214 unsigned operandIndex;
215 };
216 SmallVector<State, 4> worklist;
217 for (auto operand : operands) {
218 worklist.push_back(Elt: {.value: operand, .operandIndex: 0});
219 }
220
221 while (!worklist.empty()) {
222 State &state = worklist.back();
223 auto *opInst = state.value.getDefiningOp();
224 // Note: getDefiningOp will return nullptr if the operand is not an
225 // Operation (i.e. block argument), which is a terminator for the search.
226 if (!isa_and_nonnull<AffineApplyOp>(Val: opInst)) {
227 worklist.pop_back();
228 continue;
229 }
230
231 if (state.operandIndex == 0) {
232 // Pre-Visit: Add 'opInst' to reachable sequence.
233 affineApplyOps.push_back(Elt: opInst);
234 }
235 if (state.operandIndex < opInst->getNumOperands()) {
236 // Visit: Add next 'affineApplyOp' operand to worklist.
237 // Get next operand to visit at 'operandIndex'.
238 auto nextOperand = opInst->getOperand(idx: state.operandIndex);
239 // Increment 'operandIndex' in 'state'.
240 ++state.operandIndex;
241 // Add 'nextOperand' to worklist.
242 worklist.push_back(Elt: {.value: nextOperand, .operandIndex: 0});
243 } else {
244 // Post-visit: done visiting operands AffineApplyOp, pop off stack.
245 worklist.pop_back();
246 }
247 }
248}
249
250// Builds a system of constraints with dimensional variables corresponding to
251// the loop IVs of the forOps appearing in that order. Any symbols founds in
252// the bound operands are added as symbols in the system. Returns failure for
253// the yet unimplemented cases.
254// TODO: Handle non-unit steps through local variables or stride information in
255// FlatAffineValueConstraints. (For eg., by using iv - lb % step = 0 and/or by
256// introducing a method in FlatAffineValueConstraints
257// setExprStride(ArrayRef<int64_t> expr, int64_t stride)
258LogicalResult mlir::affine::getIndexSet(MutableArrayRef<Operation *> ops,
259 FlatAffineValueConstraints *domain) {
260 SmallVector<Value, 4> indices;
261 SmallVector<Operation *, 8> loopOps;
262 size_t numDims = 0;
263 for (Operation *op : ops) {
264 if (!isa<AffineForOp, AffineIfOp, AffineParallelOp>(Val: op)) {
265 LLVM_DEBUG(llvm::dbgs() << "getIndexSet only handles affine.for/if/"
266 "parallel ops");
267 return failure();
268 }
269 if (AffineForOp forOp = dyn_cast<AffineForOp>(Val: op)) {
270 loopOps.push_back(Elt: forOp);
271 // An AffineForOp retains only 1 induction variable.
272 numDims += 1;
273 } else if (AffineParallelOp parallelOp = dyn_cast<AffineParallelOp>(Val: op)) {
274 loopOps.push_back(Elt: parallelOp);
275 numDims += parallelOp.getNumDims();
276 }
277 }
278 extractInductionVars(affineOps: loopOps, ivs&: indices);
279 // Reset while associating Values in 'indices' to the domain.
280 *domain = FlatAffineValueConstraints(numDims, /*numSymbols=*/0,
281 /*numLocals=*/0, indices);
282 for (Operation *op : ops) {
283 // Add constraints from forOp's bounds.
284 if (AffineForOp forOp = dyn_cast<AffineForOp>(Val: op)) {
285 if (failed(Result: domain->addAffineForOpDomain(forOp)))
286 return failure();
287 } else if (auto ifOp = dyn_cast<AffineIfOp>(Val: op)) {
288 domain->addAffineIfOpDomain(ifOp);
289 } else if (auto parallelOp = dyn_cast<AffineParallelOp>(Val: op))
290 if (failed(Result: domain->addAffineParallelOpDomain(parallelOp)))
291 return failure();
292 }
293 return success();
294}
295
296/// Computes the iteration domain for 'op' and populates 'indexSet', which
297/// encapsulates the constraints involving loops surrounding 'op' and
298/// potentially involving any Function symbols. The dimensional variables in
299/// 'indexSet' correspond to the loops surrounding 'op' from outermost to
300/// innermost.
301static LogicalResult getOpIndexSet(Operation *op,
302 FlatAffineValueConstraints *indexSet) {
303 SmallVector<Operation *, 4> ops;
304 getEnclosingAffineOps(op&: *op, ops: &ops);
305 return getIndexSet(ops, domain: indexSet);
306}
307
308// Returns the number of outer loop common to 'src/dstDomain'.
309// Loops common to 'src/dst' domains are added to 'commonLoops' if non-null.
310static unsigned
311getNumCommonLoops(const FlatAffineValueConstraints &srcDomain,
312 const FlatAffineValueConstraints &dstDomain,
313 SmallVectorImpl<AffineForOp> *commonLoops = nullptr) {
314 // Find the number of common loops shared by src and dst accesses.
315 unsigned minNumLoops =
316 std::min(a: srcDomain.getNumDimVars(), b: dstDomain.getNumDimVars());
317 unsigned numCommonLoops = 0;
318 for (unsigned i = 0; i < minNumLoops; ++i) {
319 if ((!isAffineForInductionVar(val: srcDomain.getValue(pos: i)) &&
320 !isAffineParallelInductionVar(val: srcDomain.getValue(pos: i))) ||
321 (!isAffineForInductionVar(val: dstDomain.getValue(pos: i)) &&
322 !isAffineParallelInductionVar(val: dstDomain.getValue(pos: i))) ||
323 srcDomain.getValue(pos: i) != dstDomain.getValue(pos: i))
324 break;
325 if (commonLoops != nullptr)
326 commonLoops->push_back(Elt: getForInductionVarOwner(val: srcDomain.getValue(pos: i)));
327 ++numCommonLoops;
328 }
329 if (commonLoops != nullptr)
330 assert(commonLoops->size() == numCommonLoops);
331 return numCommonLoops;
332}
333
334/// Returns the closest surrounding block common to `opA` and `opB`. `opA` and
335/// `opB` should be in the same affine scope. Returns nullptr if such a block
336/// does not exist (when the two ops are in different blocks of an op starting
337/// an `AffineScope`).
338static Block *getCommonBlockInAffineScope(Operation *opA, Operation *opB) {
339 // Get the chain of ancestor blocks for the given `MemRefAccess` instance. The
340 // chain extends up to and includnig an op that starts an affine scope.
341 auto getChainOfAncestorBlocks =
342 [&](Operation *op, SmallVectorImpl<Block *> &ancestorBlocks) {
343 Block *currBlock = op->getBlock();
344 // Loop terminates when the currBlock is nullptr or its parent operation
345 // holds an affine scope.
346 while (currBlock &&
347 !currBlock->getParentOp()->hasTrait<OpTrait::AffineScope>()) {
348 ancestorBlocks.push_back(Elt: currBlock);
349 currBlock = currBlock->getParentOp()->getBlock();
350 }
351 assert(currBlock &&
352 "parent op starting an affine scope is always expected");
353 ancestorBlocks.push_back(Elt: currBlock);
354 };
355
356 // Find the closest common block.
357 SmallVector<Block *, 4> srcAncestorBlocks, dstAncestorBlocks;
358 getChainOfAncestorBlocks(opA, srcAncestorBlocks);
359 getChainOfAncestorBlocks(opB, dstAncestorBlocks);
360
361 Block *commonBlock = nullptr;
362 for (int i = srcAncestorBlocks.size() - 1, j = dstAncestorBlocks.size() - 1;
363 i >= 0 && j >= 0 && srcAncestorBlocks[i] == dstAncestorBlocks[j];
364 i--, j--)
365 commonBlock = srcAncestorBlocks[i];
366
367 return commonBlock;
368}
369
370/// Returns true if the ancestor operation of 'srcAccess' appears before the
371/// ancestor operation of 'dstAccess' in their common ancestral block. The
372/// operations for `srcAccess` and `dstAccess` are expected to be in the same
373/// affine scope and have a common surrounding block within it.
374static bool srcAppearsBeforeDstInAncestralBlock(const MemRefAccess &srcAccess,
375 const MemRefAccess &dstAccess) {
376 // Get Block common to 'srcAccess.opInst' and 'dstAccess.opInst'.
377 Block *commonBlock =
378 getCommonBlockInAffineScope(opA: srcAccess.opInst, opB: dstAccess.opInst);
379 assert(commonBlock &&
380 "ops expected to have a common surrounding block in affine scope");
381
382 // Check the dominance relationship between the respective ancestors of the
383 // src and dst in the Block of the innermost among the common loops.
384 Operation *srcOp = commonBlock->findAncestorOpInBlock(op&: *srcAccess.opInst);
385 assert(srcOp && "src access op must lie in common block");
386 Operation *dstOp = commonBlock->findAncestorOpInBlock(op&: *dstAccess.opInst);
387 assert(dstOp && "dest access op must lie in common block");
388
389 // Determine whether dstOp comes after srcOp.
390 return srcOp->isBeforeInBlock(other: dstOp);
391}
392
393// Adds ordering constraints to 'dependenceDomain' based on number of loops
394// common to 'src/dstDomain' and requested 'loopDepth'.
395// Note that 'loopDepth' cannot exceed the number of common loops plus one.
396// EX: Given a loop nest of depth 2 with IVs 'i' and 'j':
397// *) If 'loopDepth == 1' then one constraint is added: i' >= i + 1
398// *) If 'loopDepth == 2' then two constraints are added: i == i' and j' > j + 1
399// *) If 'loopDepth == 3' then two constraints are added: i == i' and j == j'
400static void addOrderingConstraints(const FlatAffineValueConstraints &srcDomain,
401 const FlatAffineValueConstraints &dstDomain,
402 unsigned loopDepth,
403 IntegerRelation *dependenceDomain) {
404 unsigned numCols = dependenceDomain->getNumCols();
405 SmallVector<int64_t, 4> eq(numCols);
406 unsigned numSrcDims = srcDomain.getNumDimVars();
407 unsigned numCommonLoops = getNumCommonLoops(srcDomain, dstDomain);
408 unsigned numCommonLoopConstraints = std::min(a: numCommonLoops, b: loopDepth);
409 for (unsigned i = 0; i < numCommonLoopConstraints; ++i) {
410 llvm::fill(Range&: eq, Value: 0);
411 eq[i] = -1;
412 eq[i + numSrcDims] = 1;
413 if (i == loopDepth - 1) {
414 eq[numCols - 1] = -1;
415 dependenceDomain->addInequality(inEq: eq);
416 } else {
417 dependenceDomain->addEquality(eq);
418 }
419 }
420}
421
422// Computes distance and direction vectors in 'dependences', by adding
423// variables to 'dependenceDomain' which represent the difference of the IVs,
424// eliminating all other variables, and reading off distance vectors from
425// equality constraints (if possible), and direction vectors from inequalities.
426static void computeDirectionVector(
427 const FlatAffineValueConstraints &srcDomain,
428 const FlatAffineValueConstraints &dstDomain, unsigned loopDepth,
429 IntegerPolyhedron *dependenceDomain,
430 SmallVector<DependenceComponent, 2> *dependenceComponents) {
431 // Find the number of common loops shared by src and dst accesses.
432 SmallVector<AffineForOp, 4> commonLoops;
433 unsigned numCommonLoops =
434 getNumCommonLoops(srcDomain, dstDomain, commonLoops: &commonLoops);
435 if (numCommonLoops == 0)
436 return;
437 // Compute direction vectors for requested loop depth.
438 unsigned numIdsToEliminate = dependenceDomain->getNumVars();
439 // Add new variables to 'dependenceDomain' to represent the direction
440 // constraints for each shared loop.
441 dependenceDomain->insertVar(kind: VarKind::SetDim, /*pos=*/0,
442 /*num=*/numCommonLoops);
443
444 // Add equality constraints for each common loop, setting newly introduced
445 // variable at column 'j' to the 'dst' IV minus the 'src IV.
446 SmallVector<int64_t, 4> eq;
447 eq.resize(N: dependenceDomain->getNumCols());
448 unsigned numSrcDims = srcDomain.getNumDimVars();
449 // Constraint variables format:
450 // [num-common-loops][num-src-dim-ids][num-dst-dim-ids][num-symbols][constant]
451 for (unsigned j = 0; j < numCommonLoops; ++j) {
452 llvm::fill(Range&: eq, Value: 0);
453 eq[j] = 1;
454 eq[j + numCommonLoops] = 1;
455 eq[j + numCommonLoops + numSrcDims] = -1;
456 dependenceDomain->addEquality(eq);
457 }
458
459 // Eliminate all variables other than the direction variables just added.
460 dependenceDomain->projectOut(pos: numCommonLoops, num: numIdsToEliminate);
461
462 // Scan each common loop variable column and set direction vectors based
463 // on eliminated constraint system.
464 dependenceComponents->resize(N: numCommonLoops);
465 for (unsigned j = 0; j < numCommonLoops; ++j) {
466 (*dependenceComponents)[j].op = commonLoops[j].getOperation();
467 auto lbConst = dependenceDomain->getConstantBound64(type: BoundType::LB, pos: j);
468 (*dependenceComponents)[j].lb =
469 lbConst.value_or(u: std::numeric_limits<int64_t>::min());
470 auto ubConst = dependenceDomain->getConstantBound64(type: BoundType::UB, pos: j);
471 (*dependenceComponents)[j].ub =
472 ubConst.value_or(u: std::numeric_limits<int64_t>::max());
473 }
474}
475
476LogicalResult
477mlir::affine::getAccessRelation(const AffineValueMap &accessValueMap,
478 const FlatAffineValueConstraints &domain,
479 IntegerRelation &rel) {
480 // Get access relation from access map.
481 if (failed(Result: getRelationFromMap(map: accessValueMap, rel)))
482 return failure();
483
484 // Merge and align domain ids of `rel` with ids of `domain`. Since the domain
485 // of the access map is a subset of the domain of access, the domain ids of
486 // `rel` are guranteed to be a subset of ids of `domain`.
487 unsigned inserts = 0;
488 for (unsigned i = 0, e = domain.getNumDimVars(); i < e; ++i) {
489 const Identifier domainIdi = Identifier(domain.getValue(pos: i));
490 const Identifier *findBegin = rel.getIds(kind: VarKind::SetDim).begin() + i;
491 const Identifier *findEnd = rel.getIds(kind: VarKind::SetDim).end();
492 const Identifier *itr = std::find(first: findBegin, last: findEnd, val: domainIdi);
493 if (itr != findEnd) {
494 rel.swapVar(posA: i, posB: i + std::distance(first: findBegin, last: itr));
495 } else {
496 ++inserts;
497 rel.insertVar(kind: VarKind::SetDim, pos: i);
498 rel.setId(kind: VarKind::SetDim, i, id: domainIdi);
499 }
500 }
501
502 // Append domain constraints to `rel`.
503 IntegerRelation domainRel = domain;
504 // For 0-d spaces, there will be no IDs. Enable if that's the case.
505 if (!domainRel.getSpace().isUsingIds())
506 domainRel.resetIds();
507 if (!rel.getSpace().isUsingIds())
508 rel.resetIds();
509 domainRel.appendVar(kind: VarKind::Range, num: accessValueMap.getNumResults());
510 domainRel.mergeAndAlignSymbols(other&: rel);
511 domainRel.mergeLocalVars(other&: rel);
512 rel.append(other: domainRel);
513
514 rel.convertVarKind(srcKind: VarKind::SetDim, varStart: 0, varLimit: accessValueMap.getNumDims() + inserts,
515 dstKind: VarKind::Domain);
516
517 return success();
518}
519
520LogicalResult MemRefAccess::getAccessRelation(IntegerRelation &rel) const {
521 // Create set corresponding to domain of access.
522 FlatAffineValueConstraints domain;
523 if (failed(Result: getOpIndexSet(op: opInst, indexSet: &domain)))
524 return failure();
525
526 AffineValueMap accessValueMap;
527 getAccessMap(accessMap: &accessValueMap);
528 return mlir::affine::getAccessRelation(accessValueMap, domain, rel);
529}
530
531// Populates 'accessMap' with composition of AffineApplyOps reachable from
532// indices of MemRefAccess.
533void MemRefAccess::getAccessMap(AffineValueMap *accessMap) const {
534 // Get affine map from AffineLoad/Store.
535 AffineMap map;
536 if (auto loadOp = dyn_cast<AffineReadOpInterface>(Val: opInst))
537 map = loadOp.getAffineMap();
538 else
539 map = cast<AffineWriteOpInterface>(Val: opInst).getAffineMap();
540
541 SmallVector<Value, 8> operands(indices.begin(), indices.end());
542 fullyComposeAffineMapAndOperands(map: &map, operands: &operands);
543 map = simplifyAffineMap(map);
544 canonicalizeMapAndOperands(map: &map, operands: &operands);
545 accessMap->reset(map, operands);
546}
547
548// Builds a flat affine constraint system to check if there exists a dependence
549// between memref accesses 'srcAccess' and 'dstAccess'.
550// Returns 'NoDependence' if the accesses can be definitively shown not to
551// access the same element.
552// Returns 'HasDependence' if the accesses do access the same element.
553// Returns 'Failure' if an error or unsupported case was encountered.
554// If a dependence exists, returns in 'dependenceComponents' a direction
555// vector for the dependence, with a component for each loop IV in loops
556// common to both accesses (see Dependence in AffineAnalysis.h for details).
557//
558// The memref access dependence check is comprised of the following steps:
559// *) Build access relation for each access. An access relation maps elements
560// of an iteration domain to the element(s) of an array domain accessed by
561// that iteration of the associated statement through some array reference.
562// *) Compute the dependence relation by composing access relation of
563// `srcAccess` with the inverse of access relation of `dstAccess`.
564// Doing this builds a relation between iteration domain of `srcAccess`
565// to the iteration domain of `dstAccess` which access the same memory
566// location.
567// *) Add ordering constraints for `srcAccess` to be accessed before
568// `dstAccess`.
569//
570// This method builds a constraint system with the following column format:
571//
572// [src-dim-variables, dst-dim-variables, symbols, constant]
573//
574// For example, given the following MLIR code with "source" and "destination"
575// accesses to the same memref label, and symbols %M, %N, %K:
576//
577// affine.for %i0 = 0 to 100 {
578// affine.for %i1 = 0 to 50 {
579// %a0 = affine.apply
580// (d0, d1) -> (d0 * 2 - d1 * 4 + s1, d1 * 3 - s0) (%i0, %i1)[%M, %N]
581// // Source memref access.
582// store %v0, %m[%a0#0, %a0#1] : memref<4x4xf32>
583// }
584// }
585//
586// affine.for %i2 = 0 to 100 {
587// affine.for %i3 = 0 to 50 {
588// %a1 = affine.apply
589// (d0, d1) -> (d0 * 7 + d1 * 9 - s1, d1 * 11 + s0) (%i2, %i3)[%K, %M]
590// // Destination memref access.
591// %v1 = load %m[%a1#0, %a1#1] : memref<4x4xf32>
592// }
593// }
594//
595// The access relation for `srcAccess` would be the following:
596//
597// [src_dim0, src_dim1, mem_dim0, mem_dim1, %N, %M, const]
598// 2 -4 -1 0 1 0 0 = 0
599// 0 3 0 -1 0 -1 0 = 0
600// 1 0 0 0 0 0 0 >= 0
601// -1 0 0 0 0 0 100 >= 0
602// 0 1 0 0 0 0 0 >= 0
603// 0 -1 0 0 0 0 50 >= 0
604//
605// The access relation for `dstAccess` would be the following:
606//
607// [dst_dim0, dst_dim1, mem_dim0, mem_dim1, %M, %K, const]
608// 7 9 -1 0 -1 0 0 = 0
609// 0 11 0 -1 0 -1 0 = 0
610// 1 0 0 0 0 0 0 >= 0
611// -1 0 0 0 0 0 100 >= 0
612// 0 1 0 0 0 0 0 >= 0
613// 0 -1 0 0 0 0 50 >= 0
614//
615// The equalities in the above relations correspond to the access maps while
616// the inequalities corresspond to the iteration domain constraints.
617//
618// The dependence relation formed:
619//
620// [src_dim0, src_dim1, dst_dim0, dst_dim1, %M, %N, %K, const]
621// 2 -4 -7 -9 1 1 0 0 = 0
622// 0 3 0 -11 -1 0 1 0 = 0
623// 1 0 0 0 0 0 0 0 >= 0
624// -1 0 0 0 0 0 0 100 >= 0
625// 0 1 0 0 0 0 0 0 >= 0
626// 0 -1 0 0 0 0 0 50 >= 0
627// 0 0 1 0 0 0 0 0 >= 0
628// 0 0 -1 0 0 0 0 100 >= 0
629// 0 0 0 1 0 0 0 0 >= 0
630// 0 0 0 -1 0 0 0 50 >= 0
631//
632//
633// TODO: Support AffineExprs mod/floordiv/ceildiv.
634DependenceResult mlir::affine::checkMemrefAccessDependence(
635 const MemRefAccess &srcAccess, const MemRefAccess &dstAccess,
636 unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints,
637 SmallVector<DependenceComponent, 2> *dependenceComponents, bool allowRAR) {
638 LLVM_DEBUG(llvm::dbgs() << "Checking for dependence at depth: "
639 << Twine(loopDepth) << " between:\n";);
640 LLVM_DEBUG(srcAccess.opInst->dump());
641 LLVM_DEBUG(dstAccess.opInst->dump());
642
643 // Return 'NoDependence' if these accesses do not access the same memref.
644 if (srcAccess.memref != dstAccess.memref)
645 return DependenceResult::NoDependence;
646
647 // Return 'NoDependence' if one of these accesses is not an
648 // AffineWriteOpInterface.
649 if (!allowRAR && !isa<AffineWriteOpInterface>(Val: srcAccess.opInst) &&
650 !isa<AffineWriteOpInterface>(Val: dstAccess.opInst))
651 return DependenceResult::NoDependence;
652
653 // We can't analyze further if the ops lie in different affine scopes or have
654 // no common block in an affine scope.
655 if (getAffineAnalysisScope(op: srcAccess.opInst) !=
656 getAffineAnalysisScope(op: dstAccess.opInst))
657 return DependenceResult::Failure;
658 if (!getCommonBlockInAffineScope(opA: srcAccess.opInst, opB: dstAccess.opInst))
659 return DependenceResult::Failure;
660
661 // Create access relation from each MemRefAccess.
662 PresburgerSpace space = PresburgerSpace::getRelationSpace();
663 IntegerRelation srcRel(space), dstRel(space);
664 if (failed(Result: srcAccess.getAccessRelation(rel&: srcRel)))
665 return DependenceResult::Failure;
666 if (failed(Result: dstAccess.getAccessRelation(rel&: dstRel)))
667 return DependenceResult::Failure;
668
669 FlatAffineValueConstraints srcDomain(srcRel.getDomainSet());
670 FlatAffineValueConstraints dstDomain(dstRel.getDomainSet());
671
672 // Return 'NoDependence' if loopDepth > numCommonLoops and if the ancestor
673 // operation of 'srcAccess' does not properly dominate the ancestor
674 // operation of 'dstAccess' in the same common operation block.
675 // Note: this check is skipped if 'allowRAR' is true, because RAR deps
676 // can exist irrespective of lexicographic ordering b/w src and dst.
677 unsigned numCommonLoops = getNumCommonLoops(srcDomain, dstDomain);
678 assert(loopDepth <= numCommonLoops + 1 && "Invalid depth");
679 if (!allowRAR && loopDepth > numCommonLoops &&
680 !srcAppearsBeforeDstInAncestralBlock(srcAccess, dstAccess)) {
681 return DependenceResult::NoDependence;
682 }
683
684 return checkAccessDependence(srcRel: std::move(srcRel), dstRel: std::move(dstRel), loopDepth,
685 dependenceConstraints, dependenceComponents);
686}
687
688DependenceResult mlir::affine::checkAccessDependence(
689 IntegerRelation &&srcRel, IntegerRelation &&dstRel, unsigned loopDepth,
690 FlatAffineValueConstraints *dependenceConstraints,
691 SmallVector<DependenceComponent, 2> *dependenceComponents) {
692 FlatAffineValueConstraints srcDomain(srcRel.getDomainSet());
693 FlatAffineValueConstraints dstDomain(dstRel.getDomainSet());
694 assert(loopDepth <= getNumCommonLoops(srcDomain, dstDomain) + 1 &&
695 "Invalid depth");
696
697 // Compute the dependence relation by composing `srcRel` with the inverse of
698 // `dstRel`. Doing this builds a relation between the iteration domain of the
699 // source access to the iteration domain of the destination access which
700 // access the same memory locations.
701 dstRel.inverse();
702 // For 0-d spaces, there will be no IDs. Enable if that's the case.
703 if (!dstRel.getSpace().isUsingIds())
704 dstRel.resetIds();
705 if (!srcRel.getSpace().isUsingIds())
706 srcRel.resetIds();
707 dstRel.mergeAndCompose(other: srcRel);
708 dstRel.convertVarKind(srcKind: VarKind::Domain, varStart: 0, varLimit: dstRel.getNumDomainVars(),
709 dstKind: VarKind::Range, pos: 0);
710 IntegerPolyhedron dependenceDomain(dstRel);
711
712 // Add 'src' happens before 'dst' ordering constraints.
713 addOrderingConstraints(srcDomain, dstDomain, loopDepth, dependenceDomain: &dependenceDomain);
714
715 // Return 'NoDependence' if the solution space is empty: no dependence.
716 if (dependenceDomain.isEmpty())
717 return DependenceResult::NoDependence;
718
719 // Compute dependence direction vector and return true.
720 if (dependenceComponents != nullptr)
721 computeDirectionVector(srcDomain, dstDomain, loopDepth, dependenceDomain: &dependenceDomain,
722 dependenceComponents);
723
724 LLVM_DEBUG(llvm::dbgs() << "Dependence polyhedron:\n");
725 LLVM_DEBUG(dependenceDomain.dump());
726
727 if (dependenceConstraints)
728 *dependenceConstraints = FlatAffineValueConstraints(dependenceDomain);
729 return DependenceResult::HasDependence;
730}
731
732/// Gathers dependence components for dependences between all ops in loop nest
733/// rooted at 'forOp' at loop depths in range [1, maxLoopDepth].
734void mlir::affine::getDependenceComponents(
735 AffineForOp forOp, unsigned maxLoopDepth,
736 std::vector<SmallVector<DependenceComponent, 2>> *depCompsVec) {
737 // Collect all load and store ops in loop nest rooted at 'forOp'.
738 SmallVector<Operation *, 8> loadAndStoreOps;
739 forOp->walk(callback: [&](Operation *op) {
740 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(Val: op))
741 loadAndStoreOps.push_back(Elt: op);
742 });
743
744 unsigned numOps = loadAndStoreOps.size();
745 for (unsigned d = 1; d <= maxLoopDepth; ++d) {
746 for (unsigned i = 0; i < numOps; ++i) {
747 auto *srcOp = loadAndStoreOps[i];
748 MemRefAccess srcAccess(srcOp);
749 for (unsigned j = 0; j < numOps; ++j) {
750 auto *dstOp = loadAndStoreOps[j];
751 MemRefAccess dstAccess(dstOp);
752
753 SmallVector<DependenceComponent, 2> depComps;
754 // TODO: Explore whether it would be profitable to pre-compute and store
755 // deps instead of repeatedly checking.
756 DependenceResult result = checkMemrefAccessDependence(
757 srcAccess, dstAccess, loopDepth: d, /*dependenceConstraints=*/nullptr,
758 dependenceComponents: &depComps);
759 if (hasDependence(result))
760 depCompsVec->push_back(x: std::move(depComps));
761 }
762 }
763 }
764}
765