22 #include "llvm/ADT/SmallPtrSet.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/raw_ostream.h" 26 #define DEBUG_TYPE "analysis-utils" 29 using namespace presburger;
31 using llvm::SmallDenseMap;
37 AffineForOp currAffineForOp;
41 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
42 loops->push_back(currAffineForOp);
43 currOp = currOp->getParentOp();
45 std::reverse(loops->begin(), loops->end());
59 if (isa<AffineIfOp, AffineForOp>(currOp))
60 ops->push_back(currOp);
63 std::reverse(ops->begin(), ops->end());
70 assert(!ivs.empty() &&
"Cannot have a slice without its IVs");
71 cst.
reset(ivs.size(), 0, 0, ivs);
72 for (
Value iv : ivs) {
74 assert(loop &&
"Expected affine for");
84 assert(!lbOperands.empty());
86 unsigned numDims = ivs.size();
88 unsigned numSymbols = lbOperands[0].size();
92 values.append(lbOperands[0].begin(), lbOperands[0].end());
93 cst->
reset(numDims, numSymbols, 0, values);
97 for (
unsigned i = numDims, end = values.size(); i < end; ++i) {
99 assert(cst->
containsId(value) &&
"value expected to be present");
113 "should not fail as we never have semi-affine slice maps");
127 llvm::errs() <<
"\tIVs:\n";
129 llvm::errs() <<
"\t\t" << iv <<
"\n";
131 llvm::errs() <<
"\tLBs:\n";
133 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
134 llvm::errs() <<
"\t\tOperands:\n";
135 for (
Value lbOp : lbOperands[en.index()])
136 llvm::errs() <<
"\t\t\t" << lbOp <<
"\n";
139 llvm::errs() <<
"\tUBs:\n";
141 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
142 llvm::errs() <<
"\t\tOperands:\n";
143 for (
Value ubOp : ubOperands[en.index()])
144 llvm::errs() <<
"\t\t\t" << ubOp <<
"\n";
153 Optional<bool> ComputationSliceState::isSliceMaximalFastCheck()
const {
154 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
155 "Unexpected number of lbs, ubs and ivs in slice");
157 for (
unsigned i = 0, end = lbs.size(); i < end; ++i) {
179 AffineForOp dstLoop =
183 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
184 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
188 assert(srcLoop &&
"Expected affine for");
189 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
190 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
210 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
211 srcLoop.getStep() != dstLoop.getStep())
233 if (isValidFastCheck.hasValue() && isValidFastCheck.getValue())
239 if (
failed(getSourceAsConstraints(srcConstraints))) {
240 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute source's domain\n");
246 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle symbols in source domain\n");
253 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle locals in source domain\n");
260 if (
failed(getAsConstraints(&sliceConstraints))) {
261 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute slice's domain\n");
268 sliceConstraints.
getNumIds() - ivs.size());
270 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the source of the slice:\n");
271 LLVM_DEBUG(srcConstraints.
dump());
272 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the slice if this fusion succeeds " 273 "(expressed in terms of its source's IVs):\n");
274 LLVM_DEBUG(sliceConstraints.
dump());
282 LLVM_DEBUG(llvm::dbgs() <<
"Incorrect slice\n");
295 if (isMaximalFastCheck.hasValue())
296 return isMaximalFastCheck;
300 srcConstraints.
reset(ivs.size(), 0,
302 for (
Value iv : ivs) {
304 assert(loop &&
"Expected affine for");
312 for (
Value lbOp : lbOperands[0])
314 consumerIVs.push_back(lbOp);
318 for (
int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
319 consumerIVs.push_back(
Value());
322 sliceConstraints.
reset(consumerIVs.size(), 0,
342 return memref.getType().cast<MemRefType>().getRank();
348 auto memRefType = memref.getType().cast<MemRefType>();
349 unsigned rank = memRefType.getRank();
351 shape->reserve(rank);
353 assert(rank == cst.getNumDimIds() &&
"inconsistent memref region");
361 for (
unsigned r = 0; r < rank; r++) {
363 int64_t dimSize = memRefType.getDimSize(r);
364 if (ShapedType::isDynamic(dimSize))
371 int64_t numElements = 1;
372 int64_t diffConstant;
374 for (
unsigned d = 0; d < rank; d++) {
377 cstWithShapeBounds.getConstantBoundOnDimSize(d, &lb, &lbDivisor);
378 if (diff.hasValue()) {
379 diffConstant = diff.getValue();
380 assert(diffConstant >= 0 &&
"Dim size bound can't be negative");
381 assert(lbDivisor > 0);
385 auto dimSize = memRefType.getDimSize(d);
388 diffConstant = dimSize;
390 lb.resize(cstWithShapeBounds.getNumSymbolIds() + 1, 0);
393 numElements *= diffConstant;
396 assert(lbDivisors &&
"both lbs and lbDivisor or none");
397 lbDivisors->push_back(lbDivisor);
400 shape->push_back(diffConstant);
408 assert(pos < cst.getNumDimIds() &&
"invalid position");
409 auto memRefType = memref.getType().cast<MemRefType>();
410 unsigned rank = memRefType.getRank();
412 assert(rank == cst.getNumDimIds() &&
"inconsistent memref region");
414 auto boundPairs = cst.getLowerAndUpperBound(
415 pos, 0, rank, cst.getNumDimAndSymbolIds(),
416 {}, memRefType.getContext());
417 lbMap = boundPairs.first;
418 ubMap = boundPairs.second;
419 assert(lbMap &&
"lower bound for a region must exist");
420 assert(ubMap &&
"upper bound for a region must exist");
421 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolIds() - rank);
422 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolIds() - rank);
426 assert(memref == other.
memref);
449 bool addMemRefDimBounds) {
450 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
451 "affine read/write op expected");
457 unsigned rank = access.
getRank();
459 LLVM_DEBUG(llvm::dbgs() <<
"MemRefRegion::compute: " << *op
460 <<
"depth: " << loopDepth <<
"\n";);
466 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
468 ivs.resize(loopDepth);
472 cst.reset(rank, loopDepth, 0, regionSymbols);
486 operands.resize(numOperands);
487 for (
unsigned i = 0; i < numOperands; ++i)
490 if (sliceState !=
nullptr) {
491 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
493 for (
auto extraOperand : sliceState->
lbOperands[0]) {
494 if (!llvm::is_contained(operands, extraOperand)) {
495 operands.push_back(extraOperand);
503 cst.reset(numDims, numSymbols, 0, operands);
507 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
508 auto operand = operands[i];
514 if (
failed(cst.addAffineForOpDomain(loop)))
518 auto symbol = operand;
521 if (
auto *op = symbol.getDefiningOp()) {
522 if (
auto constOp = dyn_cast<arith::ConstantIndexOp>(op)) {
530 if (sliceState !=
nullptr) {
532 for (
auto operand : sliceState->
lbOperands[0]) {
533 cst.addInductionVarOrTerminalSymbol(operand);
537 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
540 "should not fail as we never have semi-affine slice maps");
545 if (
failed(cst.composeMap(&accessValueMap))) {
546 op->
emitError(
"getMemRefRegion: compose affine map failed");
554 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolIds() - rank);
560 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
561 enclosingIVs.resize(loopDepth);
563 cst.getValues(cst.getNumDimIds(), cst.getNumDimAndSymbolIds(), &ids);
564 for (
auto id : ids) {
567 !llvm::is_contained(enclosingIVs, iv)) {
574 cst.projectOut(cst.getNumDimAndSymbolIds(), cst.getNumLocalIds());
577 cst.constantFoldIdRange(cst.getNumDimIds(),
578 cst.getNumSymbolIds());
580 assert(cst.getNumDimIds() == rank &&
"unexpected MemRefRegion format");
585 if (addMemRefDimBounds) {
586 auto memRefType = memref.getType().cast<MemRefType>();
587 for (
unsigned r = 0; r < rank; r++) {
589 if (memRefType.isDynamicDim(r))
592 memRefType.getDimSize(r) - 1);
595 cst.removeTrivialRedundancy();
597 LLVM_DEBUG(llvm::dbgs() <<
"Memory region:\n");
598 LLVM_DEBUG(cst.dump());
603 auto elementType = memRefType.getElementType();
606 if (elementType.isIntOrFloat()) {
607 sizeInBits = elementType.getIntOrFloatBitWidth();
609 auto vectorType = elementType.cast<VectorType>();
613 return llvm::divideCeil(sizeInBits, 8);
618 auto memRefType = memref.getType().cast<MemRefType>();
620 if (!memRefType.getLayout().isIdentity()) {
621 LLVM_DEBUG(llvm::dbgs() <<
"Non-identity layout map not yet supported\n");
633 if (!numElements.hasValue()) {
634 LLVM_DEBUG(llvm::dbgs() <<
"Dynamic shapes not yet supported\n");
645 if (!memRefType.hasStaticShape())
647 auto elementType = memRefType.getElementType();
648 if (!elementType.isIntOrFloat() && !elementType.isa<VectorType>())
652 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
653 sizeInBytes = sizeInBytes * memRefType.getDimSize(i);
658 template <
typename LoadOrStoreOp>
663 "argument should be either a AffineReadOpInterface or a " 664 "AffineWriteOpInterface");
666 Operation *op = loadOrStoreOp.getOperation();
668 if (
failed(region.compute(op, 0,
nullptr,
672 LLVM_DEBUG(llvm::dbgs() <<
"Memory region");
673 LLVM_DEBUG(region.getConstraints()->dump());
675 bool outOfBounds =
false;
676 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
679 for (
unsigned r = 0; r < rank; r++) {
686 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
693 outOfBounds = !ucst.isEmpty();
694 if (outOfBounds && emitError) {
695 loadOrStoreOp.emitOpError()
696 <<
"memref out of upper bound access along dimension #" << (r + 1);
701 std::fill(ineq.begin(), ineq.end(), 0);
704 outOfBounds = !lcst.isEmpty();
705 if (outOfBounds && emitError) {
706 loadOrStoreOp.emitOpError()
707 <<
"memref out of lower bound access along dimension #" << (r + 1);
724 while (block != limitBlock) {
727 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
728 positions->push_back(instPosInBlock);
732 std::reverse(positions->begin(), positions->end());
739 unsigned level,
Block *block) {
741 for (
auto &op : *block) {
742 if (i != positions[level]) {
746 if (level == positions.size() - 1)
748 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
750 childAffineForOp.getBody());
752 for (
auto ®ion : op.getRegions()) {
753 for (
auto &b : region)
765 for (
unsigned i = 0, e = cst->
getNumDimIds(); i < e; ++i) {
767 if (ivs.count(
value) == 0) {
781 unsigned numOps = ops.size();
782 assert(numOps > 0 &&
"Expected at least one operation");
784 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
786 for (
unsigned i = 0; i < numOps; ++i) {
789 std::min(loopDepthLimit, static_cast<unsigned>(loops[i].size()));
792 unsigned loopDepth = 0;
793 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
795 for (i = 1; i < numOps; ++i) {
796 if (loops[i - 1][d] != loops[i][d])
799 if (surroundingLoops)
800 surroundingLoops->push_back(loops[i - 1][d]);
812 unsigned loopDepth,
unsigned numCommonLoops,
813 bool isBackwardSlice,
819 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
820 for (
auto *i : opsA) {
822 for (
auto *
j : opsB) {
829 LLVM_DEBUG(llvm::dbgs() <<
"Invalid loop depth\n");
833 bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.
opInst) &&
834 isa<AffineReadOpInterface>(dstAccess.
opInst);
838 srcAccess, dstAccess, numCommonLoops + 1,
839 &dependenceConstraints,
nullptr,
842 LLVM_DEBUG(llvm::dbgs() <<
"Dependence check failed\n");
847 dependentOpPairs.emplace_back(i,
j);
852 isBackwardSlice, &tmpSliceState);
857 LLVM_DEBUG(llvm::dbgs()
858 <<
"Unable to compute slice bound constraints\n");
868 LLVM_DEBUG(llvm::dbgs()
869 <<
"Unable to compute slice bound constraints\n");
879 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimIds(); k < l; ++k)
880 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
882 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimIds(); k < l; ++k)
883 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
901 LLVM_DEBUG(llvm::dbgs()
902 <<
"Unable to compute union bounding box of slice bounds\n");
914 for (
auto &dep : dependentOpPairs) {
915 ops.push_back(isBackwardSlice ? dep.second : dep.first);
918 unsigned innermostCommonLoopDepth =
920 if (loopDepth > innermostCommonLoopDepth) {
921 LLVM_DEBUG(llvm::dbgs() <<
"Exceeds max loop depth\n");
926 unsigned numSliceLoopIVs = sliceUnionCst.
getNumDimIds();
936 opsA[0]->getContext(), &sliceUnion->
lbs,
943 &sliceBoundOperands);
946 sliceUnion->
ivs.clear();
947 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
952 ? surroundingLoops[loopDepth - 1].getBody()->begin()
953 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
957 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
958 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
963 if (!isSliceValid.hasValue()) {
964 LLVM_DEBUG(llvm::dbgs() <<
"Cannot determine if the slice is valid\n");
967 if (!isSliceValid.getValue())
975 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
976 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
986 return cExpr.getValue();
995 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
996 unsigned numSrcLoopIVs = slice.
ivs.size();
998 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1000 auto *op = forOp.getOperation();
1009 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1010 (*tripCountMap)[op] =
1011 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1015 if (maybeConstTripCount.hasValue()) {
1016 (*tripCountMap)[op] = maybeConstTripCount.getValue();
1023 if (!tripCount.hasValue())
1025 (*tripCountMap)[op] = tripCount.getValue();
1032 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1033 uint64_t iterCount = 1;
1034 for (
const auto &count : sliceTripCountMap) {
1035 iterCount *= count.second;
1052 unsigned numSrcLoopIVs = srcLoopIVs.size();
1057 unsigned numDstLoopIVs = dstLoopIVs.size();
1059 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1060 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1063 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1065 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1069 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1070 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1071 dependenceConstraints->
getValues(offset, offset + numSliceLoopIVs,
1081 &sliceState->
lbs, &sliceState->
ubs);
1086 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1087 if (i < offset || i >= offset + numSliceLoopIVs) {
1088 sliceBoundOperands.push_back(dependenceConstraints->
getValue(i));
1094 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1095 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1099 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1100 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1102 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1103 if (isa<AffineReadOpInterface>(depSourceOp) &&
1104 isa<AffineReadOpInterface>(depSinkOp)) {
1110 auto getSliceLoop = [&](
unsigned i) {
1111 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1113 auto isInnermostInsertion = [&]() {
1114 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1115 : loopDepth >= dstLoopIVs.size());
1117 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1118 auto srcIsUnitSlice = [&]() {
1125 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1126 Value iv = getSliceLoop(i).getInductionVar();
1127 if (sequentialLoops.count(iv) == 0 &&
1137 isInnermostInsertion() && srcIsUnitSlice() && isMaximal.hasValue() &&
1138 isMaximal.getValue())
1140 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1162 unsigned dstLoopDepth,
1167 unsigned numSrcLoopIVs = srcLoopIVs.size();
1172 unsigned dstLoopIVsSize = dstLoopIVs.size();
1173 if (dstLoopDepth > dstLoopIVsSize) {
1174 dstOpInst->
emitError(
"invalid destination loop depth");
1175 return AffineForOp();
1185 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1186 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1187 auto sliceLoopNest =
1188 cast<AffineForOp>(b.clone(*srcLoopIVs[0].getOperation()));
1194 getLoopIVs(*sliceInst, &sliceSurroundingLoops);
1197 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1198 (
void)sliceSurroundingLoopsSize;
1199 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1200 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1201 (
void)sliceLoopLimit;
1202 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1205 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1206 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1208 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1210 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1212 return sliceLoopNest;
1218 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1220 opInst = loadOrStoreOpInst;
1223 assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1224 "Affine read/write op expected");
1225 auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1226 opInst = loadOrStoreOpInst;
1233 return memref.getType().cast<MemRefType>().getRank();
1237 return isa<AffineWriteOpInterface>(opInst);
1246 if (isa<AffineForOp>(currOp))
1259 if (memref != rhs.
memref)
1263 getAccessMap(&thisMap);
1277 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
1278 unsigned numCommonLoops = 0;
1279 for (
unsigned i = 0; i < minNumLoops; ++i) {
1280 if (loopsA[i].getOperation() != loopsB[i].getOperation())
1284 return numCommonLoops;
1291 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
1295 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
1301 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
1303 region->compute(opInst,
1305 return opInst->
emitError(
"error obtaining memory region\n");
1308 auto it = regions.find(region->memref);
1309 if (it == regions.end()) {
1310 regions[region->memref] = std::move(region);
1311 }
else if (
failed(it->second->unionBoundingBox(*region))) {
1313 "getMemoryFootprintBytes: unable to perform a union on a memory " 1318 if (result.wasInterrupted())
1321 int64_t totalSizeInBytes = 0;
1322 for (
const auto ®ion : regions) {
1323 Optional<int64_t> size = region.second->getRegionSize();
1324 if (!size.hasValue())
1326 totalSizeInBytes += size.getValue();
1328 return totalSizeInBytes;
1333 auto *forInst = forOp.getOperation();
1344 return !reductions.empty();
1350 llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
1352 if (
auto innerFor = dyn_cast<AffineForOp>(op))
1354 sequentialLoops->insert(innerFor.getInductionVar());
1366 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
1367 return simplifiedSet;
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints, SmallVector< DependenceComponent, 2 > *dependenceComponents, bool allowRAR=false)
static Optional< int64_t > getMemoryFootprintBytes(Block &block, Block::iterator start, Block::iterator end, int memorySpace)
Include the generated interface declarations.
bool isIntegerEmpty() const
Return true if all the sets in the union are known to be integer empty false otherwise.
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.
unsigned getNumSymbols() const
unsigned getNumDims() const
Block represents an ordered list of Operations.
SmallVector< Value, 4 > ivs
Optional< int64_t > getMemoryFootprintBytes(AffineForOp forOp, int memorySpace=-1)
Gets the memory footprint of all data touched in the specified memory space in bytes; if the memory s...
void convertLoopIVSymbolsToDims()
Changes all symbol identifiers which are loop IVs to dim identifiers.
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value...
bool operator==(const MemRefAccess &rhs) const
Equal if both affine accesses can be proved to be equivalent at compile time (considering the memrefs...
static Operation * getInstAtPosition(ArrayRef< unsigned > positions, unsigned level, Block *block)
bool buildSliceTripCountMap(const ComputationSliceState &slice, llvm::SmallDenseMap< Operation *, uint64_t, 8 > *tripCountMap)
Builds a map 'tripCountMap' from AffineForOp to constant trip count for loop nest surrounding represe...
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value...
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'.
void getLoopIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)
Populates 'loops' with IVs of the loops surrounding 'op' ordered from the outermost 'affine...
unsigned getPosition() const
Block * getBlock()
Returns the operation block that contains this operation.
static void difference(const AffineValueMap &a, const AffineValueMap &b, AffineValueMap *res)
Return the value map that is the difference of value maps 'a' and 'b', represented as an affine map a...
Checks whether two accesses to the same memref access the same element.
Optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, std::vector< SmallVector< int64_t, 4 >> *lbs=nullptr, SmallVectorImpl< int64_t > *lbDivisors=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
An integer constant appearing in affine expression.
Operation::operand_range getMapOperands()
Enumerates different result statuses of slice computation by computeSliceUnion
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
Optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest...
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
Optional< uint64_t > getMemRefSizeInBytes(MemRefType memRefType)
Returns the size of memref data in bytes if it's statically shaped, None otherwise.
AffineExpr getResult(unsigned idx) const
MLIRContext * getContext()
Return the context this operation is associated with.
bool containsId(Value val) const
Returns true if an identifier with the specified Value exists, false otherwise.
unsigned getNumInputs() const
LogicalResult addSliceBounds(ArrayRef< Value > values, ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds slice lower bounds represented by lower bounds in lbMaps and upper bounds in ubMaps to each iden...
unsigned getInnermostCommonLoopDepth(ArrayRef< Operation *> ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in 'ops'.
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.
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst)
OpListType::iterator iterator
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
static LogicalResult addMissingLoopIVBounds(SmallPtrSet< Value, 8 > &ivs, FlatAffineValueConstraints *cst)
SmallVector< AffineMap, 4 > lbs
unsigned getNumLocalIds() const
Optional< bool > isSliceValid()
Checks the validity of the slice computed.
bool areIdsAlignedWithOther(const FlatAffineValueConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
static Optional< uint64_t > getConstDifference(AffineMap lbMap, AffineMap ubMap)
bool isValidSymbol(Value value)
Returns true if the given value can be used as a symbol in the region of the closest surrounding op t...
unsigned getNumOperands() const
static void findInstPosition(Operation *op, Block *limitBlock, SmallVectorImpl< unsigned > *positions)
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
Block::iterator insertPoint
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
static unsigned getMemRefEltSizeInBytes(MemRefType memRefType)
enum mlir::DependenceResult::ResultEnum value
LogicalResult addDomainFromSliceMaps(ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds constraints (lower and upper bounds) for each loop in the loop nest described by the bound maps ...
Operation::operand_range getMapOperands()
Base type for affine expression.
static WalkResult advance()
unsigned getNumResults() const
Location getLoc()
The source location the operation was defined or derived from.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
LogicalResult unionBoundingBox(const MemRefRegion &other)
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.
RetT walk(FnT &&callback)
Walk the operations in this block.
AffineMap getAffineMap() const
InFlightDiagnostic emitWarning(const Twine &message={})
Emit a warning about this operation, reporting up to any diagnostic handlers that may be listening...
A utility result that is used to signal how to proceed with an ongoing walk:
ArrayRef< AffineExpr > getResults() const
unsigned getNumSymbolIds() const
Eliminates identifier at the specified position using Fourier-Motzkin variable elimination.
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'. ...
void removeTrivialRedundancy()
Removes duplicate constraints, trivially true constraints, and constraints that can be detected as re...
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
void projectOut(Value val)
Projects out the identifier that is associate with Value.
LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
FlatAffineValueConstraints * getConstraints()
MemRefAccess(Operation *opInst)
Constructs a MemRefAccess from a load or store operation.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
SmallVector< AffineMap, 4 > ubs
SliceComputationResult computeSliceUnion(ArrayRef< Operation *> opsA, ArrayRef< Operation *> opsB, unsigned loopDepth, unsigned numCommonLoops, bool isBackwardSlice, ComputationSliceState *sliceUnion)
Computes in 'sliceUnion' the union of all slice bounds computed at 'loopDepth' between all dependent ...
const char *const kSliceFusionBarrierAttrName
Optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, FlatAffineValueConstraints *dependenceConstraints, unsigned loopDepth, bool isBackwardSlice, ComputationSliceState *sliceState)
Computes the computation slice loop bounds for one loop nest as affine maps of the other loop nest's ...
void getEnclosingAffineForAndIfOps(Operation &op, SmallVectorImpl< Operation *> *ops)
Populates 'ops' with IVs of the loops surrounding op, along with affine.if operations interleaved bet...
LogicalResult boundCheckLoadOrStoreOp(LoadOrStoreOpPointer loadOrStoreOp, bool emitError=true)
Checks a load or store op for an out of bound access; returns failure if the access is out of bounds ...
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
std::vector< SmallVector< Value, 4 > > ubOperands
PresburgerSet subtract(const PresburgerRelation &set) const
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local identifi...
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
A dimensional identifier appearing in an affine expression.
Specialization of arith.constant op that returns an integer of index type.
static VectorType vectorType(CodeGen &codegen, Type etp)
Constructs vector type.
bool isEmpty() const
Checks for emptiness by performing variable elimination on all identifiers, running the GCD test on e...
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst)
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst', slices the iteration space of src loop based on slice bounds in 'sliceState', and inserts the computation slice at the beginning of the operation block of the loop at 'dstLoopDepth' in the loop nest surrounding 'dstOpInst'.
Encapsulates a memref load or store access information.
unsigned getNumDimIds() const
Optional< uint64_t > getConstantTripCount(AffineForOp forOp)
Returns the trip count of the loop if it's a constant, None otherwise.
Value memref
Memref that this region corresponds to.
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th identifier.
void mergeAndAlignIdsWithOther(unsigned offset, FlatAffineValueConstraints *other)
Merge and align the identifiers of this and other starting at offset, so that both constraint systems...
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
unsigned getNumIds() const
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation...
A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...
std::vector< SmallVector< Value, 4 > > lbOperands
void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const
Gets the lower and upper bound map for the dimensional identifier at pos.
static IntegerSet getEmptySet(unsigned numDims, unsigned numSymbols, MLIRContext *context)
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with identifiers in range [start, end).
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
This class helps build Operations.
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
unsigned getNumDimAndSymbolIds() const
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool getClosedUB=false)
Computes the lower and upper bounds of the first num dimensional identifiers (starting at offset) as ...
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
Value getOperand(unsigned i) const
LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the identifier at the specified position with constraints being drawn from the speci...
An integer set representing a conjunction of one or more affine equalities and inequalities.