26 #include "llvm/ADT/TypeSwitch.h" 27 #include "llvm/Support/Debug.h" 28 #include "llvm/Support/raw_ostream.h" 30 #define DEBUG_TYPE "affine-analysis" 33 using namespace presburger;
41 arith::AtomicRMWKind &kind) {
49 if (combinerOps.size() > 1)
52 Operation *combinerOp = combinerOps.back();
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([](arith::MinFOp) {
return arith::AtomicRMWKind::minf; })
62 .Case([](arith::MaxFOp) {
return arith::AtomicRMWKind::maxf; })
63 .Case([](arith::MinSIOp) {
return arith::AtomicRMWKind::mins; })
64 .Case([](arith::MaxSIOp) {
return arith::AtomicRMWKind::maxs; })
65 .Case([](arith::MinUIOp) {
return arith::AtomicRMWKind::minu; })
66 .Case([](arith::MaxUIOp) {
return arith::AtomicRMWKind::maxu; })
82 unsigned numIterArgs = forOp.getNumIterOperands();
85 supportedReductions.reserve(numIterArgs);
86 for (
unsigned i = 0; i < numIterArgs; ++i) {
87 arith::AtomicRMWKind kind;
98 unsigned numIterArgs = forOp.getNumIterOperands();
102 if (numIterArgs > 0 && !parallelReductions)
106 if (parallelReductions) {
110 if (parallelReductions->size() != numIterArgs)
125 if (hasSingleEffect<MemoryEffects::Allocate>(defOp, v) &&
130 auto viewOp = dyn_cast<ViewLikeOpInterface>(defOp);
136 if (llvm::any_of(forOp.getResultTypes(),
143 if (
auto readOp = dyn_cast<AffineReadOpInterface>(op)) {
146 loadAndStoreOps.push_back(op);
147 }
else if (
auto writeOp = dyn_cast<AffineWriteOpInterface>(op)) {
150 loadAndStoreOps.push_back(op);
151 }
else if (!isa<AffineForOp, AffineYieldOp, AffineIfOp>(op) &&
152 !hasSingleEffect<MemoryEffects::Allocate>(op) &&
153 !MemoryEffectOpInterface::hasNoEffect(op)) {
163 if (walkResult.wasInterrupted())
170 for (
auto *srcOp : loadAndStoreOps) {
172 for (
auto *dstOp : loadAndStoreOps) {
176 srcAccess, dstAccess, depth, &dependenceConstraints,
196 unsigned operandIndex;
199 for (
auto operand : operands) {
200 worklist.push_back({operand, 0});
203 while (!worklist.empty()) {
204 State &state = worklist.back();
205 auto *opInst = state.value.getDefiningOp();
208 if (!isa_and_nonnull<AffineApplyOp>(opInst)) {
213 if (state.operandIndex == 0) {
215 affineApplyOps.push_back(opInst);
217 if (state.operandIndex < opInst->getNumOperands()) {
220 auto nextOperand = opInst->getOperand(state.operandIndex);
222 ++state.operandIndex;
224 worklist.push_back({nextOperand, 0});
246 assert((isa<AffineForOp, AffineIfOp>(op)) &&
247 "ops should have either AffineForOp or AffineIfOp");
248 if (AffineForOp forOp = dyn_cast<AffineForOp>(op))
249 forOps.push_back(forOp);
253 domain->
reset(forOps.size(), 0, 0, indices);
256 if (AffineForOp forOp = dyn_cast<AffineForOp>(op)) {
259 }
else if (AffineIfOp ifOp = dyn_cast<AffineIfOp>(op)) {
285 unsigned minNumLoops =
287 unsigned numCommonLoops = 0;
288 for (
unsigned i = 0; i < minNumLoops; ++i) {
293 if (commonLoops !=
nullptr)
297 if (commonLoops !=
nullptr)
298 assert(commonLoops->size() == numCommonLoops);
299 return numCommonLoops;
308 auto getChainOfAncestorBlocks =
319 "parent op starting an affine scope is always expected");
320 ancestorBlocks.push_back(currBlock);
325 getChainOfAncestorBlocks(opA, srcAncestorBlocks);
326 getChainOfAncestorBlocks(opB, dstAncestorBlocks);
328 Block *commonBlock =
nullptr;
329 for (
int i = srcAncestorBlocks.size() - 1,
j = dstAncestorBlocks.size() - 1;
330 i >= 0 &&
j >= 0 && srcAncestorBlocks[i] == dstAncestorBlocks[
j];
332 commonBlock = srcAncestorBlocks[i];
334 assert(commonBlock &&
"ops expected to have a common surrounding block");
348 auto *srcInst = commonBlock->findAncestorOpInBlock(*srcAccess.
opInst);
349 assert(srcInst &&
"src access op must lie in common block");
350 auto *dstInst = commonBlock->findAncestorOpInBlock(*dstAccess.
opInst);
351 assert(dstInst &&
"dest access op must lie in common block");
354 return srcInst->isBeforeInBlock(dstInst);
369 unsigned numCols = dependenceDomain->
getNumCols();
373 unsigned numCommonLoopConstraints =
std::min(numCommonLoops, loopDepth);
374 for (
unsigned i = 0; i < numCommonLoopConstraints; ++i) {
375 std::fill(eq.begin(), eq.end(), 0);
377 eq[i + numSrcDims] = 1;
378 if (i == loopDepth - 1) {
379 eq[numCols - 1] = -1;
398 unsigned numCommonLoops =
400 if (numCommonLoops == 0)
403 unsigned numIdsToEliminate = dependenceDomain->
getNumVars();
415 for (
unsigned j = 0;
j < numCommonLoops; ++
j) {
416 std::fill(eq.begin(), eq.end(), 0);
418 eq[
j + numCommonLoops] = 1;
419 eq[
j + numCommonLoops + numSrcDims] = -1;
424 dependenceDomain->
projectOut(numCommonLoops, numIdsToEliminate);
428 dependenceComponents->resize(numCommonLoops);
429 for (
unsigned j = 0;
j < numCommonLoops; ++
j) {
430 (*dependenceComponents)[
j].op = commonLoops[
j].getOperation();
432 (*dependenceComponents)[
j].lb =
435 (*dependenceComponents)[
j].ub =
448 getAccessMap(&accessValueMap);
458 for (
unsigned i = 0, e = domain.
getNumDimVars(); i < e; ++i) {
470 domainRel.mergeSymbolVars(rel);
471 domainRel.mergeLocalVars(rel);
482 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(opInst))
483 map = loadOp.getAffineMap();
485 map = cast<AffineWriteOpInterface>(opInst).getAffineMap();
491 accessMap->
reset(map, operands);
584 LLVM_DEBUG(llvm::dbgs() <<
"Checking for dependence at depth: " 585 << Twine(loopDepth) <<
" between:\n";);
595 if (!allowRAR && !isa<AffineWriteOpInterface>(srcAccess.
opInst) &&
596 !isa<AffineWriteOpInterface>(dstAccess.
opInst))
619 assert(loopDepth <= numCommonLoops + 1);
620 if (!allowRAR && loopDepth > numCommonLoops &&
631 *dependenceConstraints = dstRel;
635 dependenceConstraints);
638 if (dependenceConstraints->
isEmpty())
642 if (dependenceComponents !=
nullptr)
644 dependenceConstraints, dependenceComponents);
646 LLVM_DEBUG(llvm::dbgs() <<
"Dependence polyhedron:\n");
647 LLVM_DEBUG(dependenceConstraints->
dump());
654 AffineForOp forOp,
unsigned maxLoopDepth,
659 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op))
660 loadAndStoreOps.push_back(op);
663 unsigned numOps = loadAndStoreOps.size();
664 for (
unsigned d = 1; d <= maxLoopDepth; ++d) {
665 for (
unsigned i = 0; i < numOps; ++i) {
666 auto *srcOp = loadAndStoreOps[i];
668 for (
unsigned j = 0;
j < numOps; ++
j) {
669 auto *dstOp = loadAndStoreOps[
j];
677 srcAccess, dstAccess, d, &dependenceConstraints, &depComps);
679 depCompsVec->push_back(depComps);
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints, SmallVector< DependenceComponent, 2 > *dependenceComponents, bool allowRAR=false)
Include the generated interface declarations.
void getDependenceComponents(AffineForOp forOp, unsigned maxLoopDepth, std::vector< SmallVector< DependenceComponent, 2 >> *depCompsVec)
Returns in 'depCompsVec', dependence components for dependences between all load and store ops in loo...
unsigned getNumDomainDims() const
Returns the number of variables corresponding to domain/range of relation.
void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals=0)
Clears any existing data and reserves memory for the specified constraints.
Operation is a basic unit of execution within MLIR.
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
Block represents an ordered list of Operations.
void addEquality(ArrayRef< int64_t > eq)
Adds an equality from the coefficients specified in eq.
A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...
A trait of region holding operations that defines a new scope for polyhedral optimization purposes...
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)
Returns true if `forOp' is a parallel loop.
void getAccessMap(AffineValueMap *accessMap) const
Populates 'accessMap' with composition of AffineApplyOps reachable from 'indices'.
Block * getBlock()
Returns the operation block that contains this operation.
Checks whether two accesses to the same memref access the same element.
LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel)
Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...
void extractForInductionVars(ArrayRef< AffineForOp > forInsts, SmallVectorImpl< Value > *ivs)
Extracts the induction variables from a list of AffineForOps and places them in the output argument i...
static constexpr const bool value
bool isLoopMemoryParallel(AffineForOp forOp)
Returns true if `forOp' doesn't have memory dependences preventing parallelization.
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
void addInequality(ArrayRef< int64_t > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
This class represents an efficient way to signal success or failure.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
static bool srcAppearsBeforeDstInAncestralBlock(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess)
Returns true if the ancestor operation of 'srcAccess' appears before the ancestor operation of 'dstAc...
bool hasDependence(DependenceResult result)
Utility function that returns true if the provided DependenceResult corresponds to a dependence resul...
unsigned getNumVars() const
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
enum mlir::DependenceResult::ResultEnum value
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
static WalkResult advance()
Value matchReduction(ArrayRef< BlockArgument > iterCarriedArgs, unsigned redPos, SmallVectorImpl< Operation *> &combinerOps)
Utility to match a generic reduction given a list of iteration-carried arguments, iterCarriedArgs and...
LogicalResult getAccessRelation(FlatAffineRelation &accessRel) const
Creates an access relation for the access.
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued...
bool isForInductionVar(Value val)
Returns true if the provided value is the induction variable of a AffineForOp.
static WalkResult interrupt()
A utility result that is used to signal how to proceed with an ongoing walk:
void getSupportedReductions(AffineForOp forOp, SmallVectorImpl< LoopReduction > &supportedReductions)
Populate supportedReductions with descriptors of the supported reductions.
static Value getSupportedReduction(AffineForOp forOp, unsigned pos, arith::AtomicRMWKind &kind)
Get the value that is being reduced by pos-th reduction in the loop if such a reduction can be perfor...
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.
unsigned getNumDimVars() const
bool findVar(Value val, unsigned *pos) const
Looks up the position of the variable with the specified Value.
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
void projectOut(Value val)
Projects out the variable that is associate with Value.
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
void append(const IntegerRelation &other)
Appends constraints from other into this.
static unsigned getNumCommonLoops(const FlatAffineValueConstraints &srcDomain, const FlatAffineValueConstraints &dstDomain, SmallVectorImpl< AffineForOp > *commonLoops=nullptr)
void getEnclosingAffineForAndIfOps(Operation &op, SmallVectorImpl< Operation *> *ops)
Populates 'ops' with IVs of the loops surrounding op, along with affine.if operations interleaved bet...
static void computeDirectionVector(const FlatAffineValueConstraints &srcDomain, const FlatAffineValueConstraints &dstDomain, unsigned loopDepth, FlatAffineValueConstraints *dependenceDomain, SmallVector< DependenceComponent, 2 > *dependenceComponents)
Region * getAffineScope(Operation *op)
Returns the closest region enclosing op that is held by an operation with trait AffineScope; nullptr ...
void push_back(Operation *op)
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
LogicalResult getIndexSet(MutableArrayRef< Operation *> ops, FlatAffineValueConstraints *domain)
Builds a system of constraints with dimensional variables corresponding to the loop IVs of the forOps...
This class provides a shared interface for ranked and unranked memref types.
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable...
static Block * getCommonBlock(Operation *opA, Operation *opB)
Returns the closest surrounding block common to opA and opB.
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
unsigned getNumCols() const
Returns the number of columns in the constraint system.
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
void insertDomainVar(unsigned pos, unsigned num=1)
Insert num variables of the specified kind after the pos variable of that kind.
static bool isLocallyDefined(Value v, Operation *enclosingOp)
Returns true if v is allocated locally to enclosingOp – i.e., it is allocated by an operation nested...
void inverse()
Swap domain and range of the relation.
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
FlatAffineValueConstraints getDomainSet() const
Returns a set corresponding to the domain/range of the affine relation.
Encapsulates a memref load or store access information.
static LogicalResult getOpIndexSet(Operation *op, FlatAffineValueConstraints *indexSet)
Computes the iteration domain for 'op' and populates 'indexSet', which encapsulates the constraints i...
unsigned getNumRangeDims() const
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
A description of a (parallelizable) reduction in an affine loop.
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
void getReachableAffineApplyOps(ArrayRef< Value > operands, SmallVectorImpl< Operation *> &affineApplyOps)
Returns in affineApplyOps, the sequence of those AffineApplyOp Operations that are reachable via a se...
static void addOrderingConstraints(const FlatAffineValueConstraints &srcDomain, const FlatAffineValueConstraints &dstDomain, unsigned loopDepth, FlatAffineValueConstraints *dependenceDomain)
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation...
void compose(const FlatAffineRelation &other)
Given affine relation other: (domainOther -> rangeOther), this operation takes the composition of oth...
void reset(AffineMap map, ValueRange operands, ValueRange results={})
bool isProperAncestor(Operation *other)
Return true if this operation is a proper ancestor of the other operation.
Optional< int64_t > getConstantBound(BoundType type, unsigned pos) const
Returns the constant bound for the pos^th variable if there is one; None otherwise.
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)