23 #include "llvm/ADT/SmallPtrSet.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/raw_ostream.h"
28 #define DEBUG_TYPE "analysis-utils"
31 using namespace presburger;
33 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());
56 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))
57 ops->push_back(currOp);
60 std::reverse(ops->begin(), ops->end());
67 assert(!ivs.empty() &&
"Cannot have a slice without its IVs");
70 for (
Value iv : ivs) {
72 assert(loop &&
"Expected affine for");
82 assert(!lbOperands.empty());
84 unsigned numDims = ivs.size();
86 unsigned numSymbols = lbOperands[0].size();
90 values.append(lbOperands[0].begin(), lbOperands[0].end());
95 for (
unsigned i = numDims, end = values.size(); i < end; ++i) {
96 Value value = values[i];
97 assert(cst->
containsVar(value) &&
"value expected to be present");
111 "should not fail as we never have semi-affine slice maps");
125 llvm::errs() <<
"\tIVs:\n";
127 llvm::errs() <<
"\t\t" << iv <<
"\n";
129 llvm::errs() <<
"\tLBs:\n";
131 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
132 llvm::errs() <<
"\t\tOperands:\n";
133 for (
Value lbOp : lbOperands[en.index()])
134 llvm::errs() <<
"\t\t\t" << lbOp <<
"\n";
137 llvm::errs() <<
"\tUBs:\n";
139 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
140 llvm::errs() <<
"\t\tOperands:\n";
141 for (
Value ubOp : ubOperands[en.index()])
142 llvm::errs() <<
"\t\t\t" << ubOp <<
"\n";
151 std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck()
const {
152 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
153 "Unexpected number of lbs, ubs and ivs in slice");
155 for (
unsigned i = 0, end = lbs.size(); i < end; ++i) {
177 AffineForOp dstLoop =
181 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
182 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
186 assert(srcLoop &&
"Expected affine for");
187 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
188 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
208 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
209 srcLoop.getStep() != dstLoop.getStep())
230 std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
231 if (isValidFastCheck && *isValidFastCheck)
237 if (
failed(getSourceAsConstraints(srcConstraints))) {
238 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute source's domain\n");
244 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle symbols in source domain\n");
251 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle locals in source domain\n");
258 if (
failed(getAsConstraints(&sliceConstraints))) {
259 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute slice's domain\n");
268 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the source of the slice:\n");
269 LLVM_DEBUG(srcConstraints.
dump());
270 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the slice if this fusion succeeds "
271 "(expressed in terms of its source's IVs):\n");
272 LLVM_DEBUG(sliceConstraints.
dump());
280 LLVM_DEBUG(llvm::dbgs() <<
"Incorrect slice\n");
292 std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
293 if (isMaximalFastCheck)
294 return isMaximalFastCheck;
300 for (
Value iv : ivs) {
302 assert(loop &&
"Expected affine for");
310 for (
Value lbOp : lbOperands[0])
312 consumerIVs.push_back(lbOp);
316 for (
int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
317 consumerIVs.push_back(
Value());
340 return memref.getType().cast<MemRefType>().getRank();
346 auto memRefType = memref.getType().cast<MemRefType>();
347 unsigned rank = memRefType.getRank();
349 shape->reserve(rank);
351 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
359 for (
unsigned r = 0; r < rank; r++) {
361 int64_t dimSize = memRefType.getDimSize(r);
362 if (ShapedType::isDynamic(dimSize))
369 int64_t numElements = 1;
370 int64_t diffConstant;
372 for (
unsigned d = 0; d < rank; d++) {
374 std::optional<int64_t> diff =
376 if (diff.has_value()) {
377 diffConstant = *diff;
378 assert(diffConstant >= 0 &&
"Dim size bound can't be negative");
379 assert(lbDivisor > 0);
383 auto dimSize = memRefType.getDimSize(d);
384 if (dimSize == ShapedType::kDynamic)
386 diffConstant = dimSize;
391 numElements *= diffConstant;
394 assert(lbDivisors &&
"both lbs and lbDivisor or none");
395 lbDivisors->push_back(lbDivisor);
398 shape->push_back(diffConstant);
406 assert(pos < cst.getNumDimVars() &&
"invalid position");
407 auto memRefType = memref.getType().cast<MemRefType>();
408 unsigned rank = memRefType.getRank();
410 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
412 auto boundPairs = cst.getLowerAndUpperBound(
413 pos, 0, rank, cst.getNumDimAndSymbolVars(),
414 {}, memRefType.getContext());
415 lbMap = boundPairs.first;
416 ubMap = boundPairs.second;
417 assert(lbMap &&
"lower bound for a region must exist");
418 assert(ubMap &&
"upper bound for a region must exist");
419 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
420 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
424 assert(memref == other.
memref);
447 bool addMemRefDimBounds) {
448 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
449 "affine read/write op expected");
455 unsigned rank = access.
getRank();
457 LLVM_DEBUG(llvm::dbgs() <<
"MemRefRegion::compute: " << *op
458 <<
"\ndepth: " << loopDepth <<
"\n";);
464 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
466 ivs.resize(loopDepth);
482 operands.resize(numOperands);
483 for (
unsigned i = 0; i < numOperands; ++i)
486 if (sliceState !=
nullptr) {
487 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
489 for (
auto extraOperand : sliceState->
lbOperands[0]) {
490 if (!llvm::is_contained(operands, extraOperand)) {
491 operands.push_back(extraOperand);
503 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
504 auto operand = operands[i];
510 if (
failed(cst.addAffineForOpDomain(affineFor)))
513 if (
failed(cst.addAffineParallelOpDomain(parallelOp)))
517 Value symbol = operand;
521 LLVM_DEBUG(llvm::dbgs() <<
"unknown affine dimensional value");
527 if (sliceState !=
nullptr) {
529 for (
auto operand : sliceState->
lbOperands[0]) {
530 cst.addInductionVarOrTerminalSymbol(operand);
534 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
537 "should not fail as we never have semi-affine slice maps");
542 if (
failed(cst.composeMap(&accessValueMap))) {
543 op->
emitError(
"getMemRefRegion: compose affine map failed");
551 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
557 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
558 enclosingIVs.resize(loopDepth);
560 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
561 for (
Value var : vars) {
569 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
572 cst.constantFoldVarRange(cst.getNumDimVars(),
573 cst.getNumSymbolVars());
575 assert(cst.getNumDimVars() == rank &&
"unexpected MemRefRegion format");
580 if (addMemRefDimBounds) {
581 auto memRefType = memref.getType().cast<MemRefType>();
582 for (
unsigned r = 0; r < rank; r++) {
584 if (memRefType.isDynamicDim(r))
586 cst.addBound(
BoundType::UB, r, memRefType.getDimSize(r) - 1);
589 cst.removeTrivialRedundancy();
591 LLVM_DEBUG(llvm::dbgs() <<
"Memory region:\n");
592 LLVM_DEBUG(cst.dump());
596 std::optional<int64_t>
598 auto elementType = memRefType.getElementType();
601 if (elementType.isIntOrFloat()) {
602 sizeInBits = elementType.getIntOrFloatBitWidth();
603 }
else if (
auto vectorType = elementType.dyn_cast<VectorType>()) {
604 if (vectorType.getElementType().isIntOrFloat())
606 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
612 return llvm::divideCeil(sizeInBits, 8);
617 auto memRefType = memref.getType().cast<MemRefType>();
619 if (!memRefType.getLayout().isIdentity()) {
620 LLVM_DEBUG(llvm::dbgs() <<
"Non-identity layout map not yet supported\n");
631 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
633 LLVM_DEBUG(llvm::dbgs() <<
"Dynamic shapes not yet supported\n");
639 return *eltSize * *numElements;
646 std::optional<uint64_t>
648 if (!memRefType.hasStaticShape())
650 auto elementType = memRefType.getElementType();
651 if (!elementType.isIntOrFloat() && !elementType.isa<VectorType>())
657 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
658 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
663 template <
typename LoadOrStoreOp>
666 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
667 AffineWriteOpInterface>::value,
668 "argument should be either a AffineReadOpInterface or a "
669 "AffineWriteOpInterface");
671 Operation *op = loadOrStoreOp.getOperation();
673 if (
failed(region.compute(op, 0,
nullptr,
677 LLVM_DEBUG(llvm::dbgs() <<
"Memory region");
678 LLVM_DEBUG(region.getConstraints()->dump());
680 bool outOfBounds =
false;
681 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
684 for (
unsigned r = 0; r < rank; r++) {
691 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
698 outOfBounds = !ucst.isEmpty();
700 loadOrStoreOp.emitOpError()
701 <<
"memref out of upper bound access along dimension #" << (r + 1);
706 std::fill(ineq.begin(), ineq.end(), 0);
709 outOfBounds = !lcst.isEmpty();
711 loadOrStoreOp.emitOpError()
712 <<
"memref out of lower bound access along dimension #" << (r + 1);
729 while (block != limitBlock) {
732 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
733 positions->push_back(instPosInBlock);
737 std::reverse(positions->begin(), positions->end());
744 unsigned level,
Block *block) {
746 for (
auto &op : *block) {
747 if (i != positions[level]) {
751 if (level == positions.size() - 1)
753 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
755 childAffineForOp.getBody());
758 for (
auto &b : region)
772 if (ivs.count(value) == 0) {
786 unsigned numOps = ops.size();
787 assert(numOps > 0 &&
"Expected at least one operation");
789 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
791 for (
unsigned i = 0; i < numOps; ++i) {
794 std::min(loopDepthLimit,
static_cast<unsigned>(loops[i].size()));
797 unsigned loopDepth = 0;
798 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
800 for (i = 1; i < numOps; ++i) {
801 if (loops[i - 1][d] != loops[i][d])
804 if (surroundingLoops)
805 surroundingLoops->push_back(loops[i - 1][d]);
817 unsigned loopDepth,
unsigned numCommonLoops,
818 bool isBackwardSlice,
824 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
825 for (
auto *i : opsA) {
827 for (
auto *
j : opsB) {
834 LLVM_DEBUG(llvm::dbgs() <<
"Invalid loop depth\n");
838 bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.
opInst) &&
839 isa<AffineReadOpInterface>(dstAccess.
opInst);
843 srcAccess, dstAccess, numCommonLoops + 1,
844 &dependenceConstraints,
nullptr,
847 LLVM_DEBUG(llvm::dbgs() <<
"Dependence check failed\n");
852 dependentOpPairs.emplace_back(i,
j);
857 isBackwardSlice, &tmpSliceState);
862 LLVM_DEBUG(llvm::dbgs()
863 <<
"Unable to compute slice bound constraints\n");
873 LLVM_DEBUG(llvm::dbgs()
874 <<
"Unable to compute slice bound constraints\n");
884 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimVars(); k < l; ++k)
885 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
887 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimVars(); k < l; ++k)
888 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
906 LLVM_DEBUG(llvm::dbgs()
907 <<
"Unable to compute union bounding box of slice bounds\n");
919 for (
auto &dep : dependentOpPairs) {
920 ops.push_back(isBackwardSlice ? dep.second : dep.first);
923 unsigned innermostCommonLoopDepth =
925 if (loopDepth > innermostCommonLoopDepth) {
926 LLVM_DEBUG(llvm::dbgs() <<
"Exceeds max loop depth\n");
941 opsA[0]->getContext(), &sliceUnion->
lbs,
948 &sliceBoundOperands);
951 sliceUnion->
ivs.clear();
952 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
957 ? surroundingLoops[loopDepth - 1].getBody()->begin()
958 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
962 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
963 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
967 std::optional<bool> isSliceValid = sliceUnion->
isSliceValid();
969 LLVM_DEBUG(llvm::dbgs() <<
"Cannot determine if the slice is valid\n");
981 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
982 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
1001 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1002 unsigned numSrcLoopIVs = slice.
ivs.size();
1004 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1006 auto *op = forOp.getOperation();
1015 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1016 (*tripCountMap)[op] =
1017 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1021 if (maybeConstTripCount.has_value()) {
1022 (*tripCountMap)[op] = *maybeConstTripCount;
1029 if (!tripCount.has_value())
1031 (*tripCountMap)[op] = *tripCount;
1038 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1039 uint64_t iterCount = 1;
1040 for (
const auto &count : sliceTripCountMap) {
1041 iterCount *= count.second;
1058 unsigned numSrcLoopIVs = srcLoopIVs.size();
1063 unsigned numDstLoopIVs = dstLoopIVs.size();
1065 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1066 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1069 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1071 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1075 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1076 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1077 dependenceConstraints->
getValues(offset, offset + numSliceLoopIVs,
1087 &sliceState->
lbs, &sliceState->
ubs);
1092 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1093 if (i < offset || i >= offset + numSliceLoopIVs) {
1094 sliceBoundOperands.push_back(dependenceConstraints->
getValue(i));
1100 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1101 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1105 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1106 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1108 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1109 if (isa<AffineReadOpInterface>(depSourceOp) &&
1110 isa<AffineReadOpInterface>(depSinkOp)) {
1116 auto getSliceLoop = [&](
unsigned i) {
1117 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1119 auto isInnermostInsertion = [&]() {
1120 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1121 : loopDepth >= dstLoopIVs.size());
1123 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1124 auto srcIsUnitSlice = [&]() {
1131 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1132 Value iv = getSliceLoop(i).getInductionVar();
1133 if (sequentialLoops.count(iv) == 0 &&
1141 std::optional<bool> isMaximal = sliceState->
isMaximal();
1143 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1145 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1167 unsigned dstLoopDepth,
1172 unsigned numSrcLoopIVs = srcLoopIVs.size();
1177 unsigned dstLoopIVsSize = dstLoopIVs.size();
1178 if (dstLoopDepth > dstLoopIVsSize) {
1179 dstOpInst->
emitError(
"invalid destination loop depth");
1180 return AffineForOp();
1190 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1191 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1192 auto sliceLoopNest =
1193 cast<AffineForOp>(b.
clone(*srcLoopIVs[0].getOperation()));
1202 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1203 (void)sliceSurroundingLoopsSize;
1204 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1205 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1206 (void)sliceLoopLimit;
1207 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1210 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1211 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1213 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1215 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1217 return sliceLoopNest;
1223 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1224 memref = loadOp.getMemRef();
1225 opInst = loadOrStoreOpInst;
1226 llvm::append_range(indices, loadOp.getMapOperands());
1228 assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1229 "Affine read/write op expected");
1230 auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1231 opInst = loadOrStoreOpInst;
1232 memref = storeOp.getMemRef();
1233 llvm::append_range(indices, storeOp.getMapOperands());
1238 return memref.getType().cast<MemRefType>().getRank();
1242 return isa<AffineWriteOpInterface>(opInst);
1251 if (isa<AffineForOp>(currOp))
1264 if (memref != rhs.
memref)
1268 getAccessMap(&thisMap);
1277 AffineForOp currAffineForOp;
1281 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
1282 ivs.push_back(currAffineForOp.getInductionVar());
1283 else if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
1284 llvm::append_range(ivs, parOp.getIVs());
1285 currOp = currOp->getParentOp();
1287 std::reverse(ivs.begin(), ivs.end());
1297 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
1298 unsigned numCommonLoops = 0;
1299 for (
unsigned i = 0; i < minNumLoops; ++i) {
1300 if (loopsA[i] != loopsB[i])
1304 return numCommonLoops;
1311 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
1315 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
1321 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
1323 region->compute(opInst,
1325 return opInst->
emitError(
"error obtaining memory region\n");
1328 auto it = regions.find(region->memref);
1329 if (it == regions.end()) {
1330 regions[region->memref] = std::move(region);
1331 }
else if (
failed(it->second->unionBoundingBox(*region))) {
1333 "getMemoryFootprintBytes: unable to perform a union on a memory "
1338 if (result.wasInterrupted())
1339 return std::nullopt;
1341 int64_t totalSizeInBytes = 0;
1342 for (
const auto ®ion : regions) {
1343 std::optional<int64_t> size = region.second->getRegionSize();
1344 if (!size.has_value())
1345 return std::nullopt;
1346 totalSizeInBytes += *size;
1348 return totalSizeInBytes;
1353 auto *forInst = forOp.getOperation();
1364 return !reductions.empty();
1370 llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
1372 if (
auto innerFor = dyn_cast<AffineForOp>(op))
1374 sequentialLoops->insert(innerFor.getInductionVar());
1386 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
1387 return simplifiedSet;
1393 llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
1394 return val.has_value() ? *val :
Value();
1413 for (
unsigned i = syms.size(); i < newSyms.size(); ++i)
1415 return constraints.
addBound(type, pos, alignedMap);
1422 newResults.push_back(r + val);
1467 bool isMin = isa<AffineMinOp>(op);
1468 assert((isMin || isa<AffineMaxOp>(op)) &&
"expect AffineMin/MaxOp");
1472 isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
1479 unsigned resultDimStart = constraints.
appendDimVar(numResults);
1494 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
1523 for (
unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
1531 map.
getSubMap({i - resultDimStart}), operands)))
1539 ineq[dimOpBound] = isMin ? 1 : -1;
1540 ineq[i] = isMin ? -1 : 1;
static std::optional< uint64_t > getConstDifference(AffineMap lbMap, AffineMap ubMap)
static void findInstPosition(Operation *op, Block *limitBlock, SmallVectorImpl< unsigned > *positions)
const char *const kSliceFusionBarrierAttrName
static LogicalResult addMissingLoopIVBounds(SmallPtrSet< Value, 8 > &ivs, FlatAffineValueConstraints *cst)
static Operation * getInstAtPosition(ArrayRef< unsigned > positions, unsigned level, Block *block)
static std::optional< int64_t > getMemoryFootprintBytes(Block &block, Block::iterator start, Block::iterator end, int memorySpace)
static AffineMap addConstToResults(AffineMap map, int64_t val)
Add val to each result of map.
static LogicalResult alignAndAddBound(FlatAffineValueConstraints &constraints, BoundType type, unsigned pos, AffineMap map, ValueRange operands)
Bound an identifier pos in a given FlatAffineValueConstraints with constraints drawn from an affine m...
static void unpackOptionalValues(ArrayRef< std::optional< Value >> source, SmallVector< Value > &target)
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
An integer constant appearing in affine expression.
A dimensional identifier appearing in an affine expression.
unsigned getPosition() const
Base type for affine expression.
constexpr bool isa() const
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
MLIRContext * getContext() const
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
AffineMap shiftDims(unsigned shift, unsigned offset=0) const
Replace dims[offset ...
unsigned getNumSymbols() const
unsigned getNumDims() const
ArrayRef< AffineExpr > getResults() const
unsigned getNumResults() const
unsigned getNumInputs() const
AffineExpr getResult(unsigned idx) const
AffineMap replace(AffineExpr expr, AffineExpr replacement, unsigned numResultDims, unsigned numResultSyms) const
Sparse replace method.
AffineMap getSubMap(ArrayRef< unsigned > resultPos) const
Returns the map consisting of the resultPos subset.
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes.
Value getOperand(unsigned i) const
unsigned getNumOperands() const
AffineMap getAffineMap() const
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...
Block represents an ordered list of Operations.
OpListType::iterator iterator
RetT walk(FnT &&callback)
Walk the operations in this block.
Operation * getParentOp()
Returns the closest surrounding operation that contains this block.
This class is a general helper class for creating context-global objects like types,...
AffineExpr getAffineSymbolExpr(unsigned position)
AffineExpr getAffineConstantExpr(int64_t constant)
AffineExpr getAffineDimExpr(unsigned position)
This class provides support for representing a failure result, or a valid value of type T.
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, ValueRange operands)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
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 ...
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
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 vari...
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
LogicalResult unionBoundingBox(const FlatLinearValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
void mergeAndAlignVarsWithOther(unsigned offset, FlatLinearValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void projectOut(Value val)
Projects out the variable that is associate with Value.
bool containsVar(Value val) const
Returns true if a variable with the specified Value exists, false otherwise.
unsigned appendDimVar(ValueRange vals)
ArrayRef< std::optional< Value > > getMaybeValues() const
bool areVarsAlignedWithOther(const FlatLinearConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
unsigned appendSymbolVar(ValueRange vals)
An integer set representing a conjunction of one or more affine equalities and inequalities.
unsigned getNumDims() const
MLIRContext * getContext() const
static IntegerSet getEmptySet(unsigned numDims, unsigned numSymbols, MLIRContext *context)
unsigned getNumSymbols() const
MLIRContext is the top-level object for a collection of MLIR operations.
This class helps build Operations.
Operation * clone(Operation &op, IRMapping &mapper)
Creates a deep copy of the specified operation, remapping any operands that use values outside of the...
Operation is the basic unit of execution within MLIR.
InFlightDiagnostic emitWarning(const Twine &message={})
Emit a warning about this operation, reporting up to any diagnostic handlers that may be listening.
MLIRContext * getContext()
Return the context this operation is associated with.
Location getLoc()
The source location the operation was defined or derived from.
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
InFlightDiagnostic emitError(const Twine &message={})
Emit an error about fatal conditions with this operation, reporting up to any diagnostic handlers tha...
Block * getBlock()
Returns the operation block that contains this operation.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
operand_range getOperands()
Returns an iterator on the underlying Value's.
This class provides an abstraction over the different types of ranges over Values.
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
A utility result that is used to signal how to proceed with an ongoing walk:
static WalkResult advance()
Specialization of arith.constant op that returns an integer of index type.
void addInequality(ArrayRef< MPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
void removeTrivialRedundancy()
Removes duplicate constraints, trivially true constraints, and constraints that can be detected as re...
std::optional< int64_t > getConstantBoundOnDimSize64(unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *boundFloorDivisor=nullptr, SmallVectorImpl< int64_t > *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
The same, but casts to int64_t.
unsigned getNumSymbolVars() const
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned getNumVars() const
unsigned getNumLocalVars() const
unsigned getNumDimAndSymbolVars() const
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
unsigned getNumCols() const
Returns the number of columns in the constraint system.
unsigned getNumDimVars() const
bool isIntegerEmpty() const
Return true if all the sets in the union are known to be integer empty false otherwise.
PresburgerSet subtract(const PresburgerRelation &set) const
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
BoundType
The type of bound: equal, lower bound or upper bound.
Include the generated interface declarations.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
std::optional< uint64_t > getIntOrFloatMemRefSizeInBytes(MemRefType memRefType)
Returns the size of a memref with element type int or float in bytes if it's statically shaped,...
std::optional< int64_t > getMemRefIntOrFloatEltSizeInBytes(MemRefType memRefType)
Returns the memref's element type's size in bytes where the elemental type is an int or float or a ve...
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
void getAffineIVs(Operation &op, SmallVectorImpl< Value > &ivs)
Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel ops ordered from the outer...
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...
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 ...
void getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
FailureOr< AffineValueMap > simplifyConstrainedMinMaxOp(Operation *op, FlatAffineValueConstraints constraints)
Try to simplify the given affine.min or affine.max op to an affine map with a single result and opera...
bool isAffineInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands, ValueRange dims, ValueRange syms, SmallVector< Value > *newSyms=nullptr)
Re-indexes the dimensions and symbols of an affine map with given operands values to align with dims ...
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
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...
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
AffineParallelOp getAffineParallelInductionVarOwner(Value val)
Returns true if the provided value is among the induction variables of an AffineParallelOp.
std::optional< uint64_t > getConstantTripCount(AffineForOp forOp)
Returns the trip count of the loop if it's a constant, std::nullopt otherwise.
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost.
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst',...
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 ...
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
unsigned getInnermostCommonLoopDepth(ArrayRef< Operation * > ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in 'ops'.
std::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...
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints=nullptr, SmallVector< DependenceComponent, 2 > *dependenceComponents=nullptr, bool allowRAR=false)
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
bool isAffineForInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp.
void getAffineForIVs(Operation &op, SmallVectorImpl< AffineForOp > *loops)
Populates 'loops' with IVs of the affine.for ops surrounding 'op' ordered from the outermost 'affine....
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)
Returns true if ‘forOp’ is a parallel loop.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
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 ...
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
SmallVector< AffineMap, 4 > ubs
SmallVector< AffineMap, 4 > lbs
std::vector< SmallVector< Value, 4 > > ubOperands
Block::iterator insertPoint
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
std::vector< SmallVector< Value, 4 > > lbOperands
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst)
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
SmallVector< Value, 4 > ivs
std::optional< bool > isSliceValid()
Checks the validity of the slice computed.
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst)
Checks whether two accesses to the same memref access the same element.
enum mlir::DependenceResult::ResultEnum value
This class represents an efficient way to signal success or failure.
Encapsulates a memref load or store access information.
MemRefAccess(Operation *opInst)
Constructs a MemRefAccess from a load or store operation.
void getAccessMap(AffineValueMap *accessMap) const
Populates 'accessMap' with composition of AffineApplyOps reachable from 'indices'.
bool operator==(const MemRefAccess &rhs) const
Equal if both affine accesses can be proved to be equivalent at compile time (considering the memrefs...
A region of a memref's data space; this is typically constructed by analyzing load/store op's on this...
FlatAffineValueConstraints * getConstraints()
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
std::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...
void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const
Gets the lower and upper bound map for the dimensional variable at pos.
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
LogicalResult unionBoundingBox(const MemRefRegion &other)
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...
Value memref
Memref that this region corresponds to.
Enumerates different result statuses of slice computation by computeSliceUnion
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.