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