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 affine;
32 using namespace presburger;
34 using llvm::SmallDenseMap;
43 if (isa<AffineForOp>(op))
44 forOps.push_back(cast<AffineForOp>(op));
46 hasNonAffineRegionOp =
true;
47 else if (isa<AffineReadOpInterface>(op))
48 loadOpInsts.push_back(op);
49 else if (isa<AffineWriteOpInterface>(op))
50 storeOpInsts.push_back(op);
55 unsigned Node::getLoadOpCount(
Value memref)
const {
56 unsigned loadOpCount = 0;
58 if (memref == cast<AffineReadOpInterface>(loadOp).getMemRef())
65 unsigned Node::getStoreOpCount(
Value memref)
const {
66 unsigned storeOpCount = 0;
68 if (memref == cast<AffineWriteOpInterface>(storeOp).getMemRef())
75 void Node::getStoreOpsForMemref(
Value memref,
78 if (memref == cast<AffineWriteOpInterface>(storeOp).getMemRef())
79 storeOps->push_back(storeOp);
84 void Node::getLoadOpsForMemref(
Value memref,
87 if (memref == cast<AffineReadOpInterface>(loadOp).getMemRef())
88 loadOps->push_back(loadOp);
94 void Node::getLoadAndStoreMemrefSet(
96 llvm::SmallDenseSet<Value, 2> loadMemrefs;
98 loadMemrefs.insert(cast<AffineReadOpInterface>(loadOp).getMemRef());
101 auto memref = cast<AffineWriteOpInterface>(storeOp).getMemRef();
102 if (loadMemrefs.count(memref) > 0)
103 loadAndStoreMemrefSet->insert(memref);
109 auto it = nodes.find(
id);
110 assert(it != nodes.end());
116 for (
auto &idAndNode : nodes)
117 if (idAndNode.second.op == forOp)
118 return &idAndNode.second;
124 Node node(nextNodeId++, op);
125 nodes.insert({node.
id, node});
132 if (inEdges.count(
id) > 0) {
134 for (
auto &inEdge : oldInEdges) {
135 removeEdge(inEdge.id,
id, inEdge.value);
139 if (outEdges.count(
id) > 0) {
141 for (
auto &outEdge : oldOutEdges) {
142 removeEdge(
id, outEdge.id, outEdge.value);
154 Node *node = getNode(
id);
155 for (
auto *storeOpInst : node->
stores) {
156 auto memref = cast<AffineWriteOpInterface>(storeOpInst).getMemRef();
157 auto *op = memref.getDefiningOp();
163 for (
auto *user : memref.getUsers())
164 if (!isa<AffineMapAccessInterface>(*user))
175 if (outEdges.count(srcId) == 0 || inEdges.count(dstId) == 0) {
178 bool hasOutEdge = llvm::any_of(outEdges[srcId], [=](
Edge &edge) {
179 return edge.
id == dstId && (!value || edge.
value == value);
181 bool hasInEdge = llvm::any_of(inEdges[dstId], [=](
Edge &edge) {
182 return edge.
id == srcId && (!value || edge.
value == value);
184 return hasOutEdge && hasInEdge;
190 if (!hasEdge(srcId, dstId, value)) {
191 outEdges[srcId].push_back({dstId, value});
192 inEdges[dstId].push_back({srcId, value});
193 if (isa<MemRefType>(value.
getType()))
194 memrefEdgeCount[value]++;
201 assert(inEdges.count(dstId) > 0);
202 assert(outEdges.count(srcId) > 0);
203 if (isa<MemRefType>(value.
getType())) {
204 assert(memrefEdgeCount.count(value) > 0);
205 memrefEdgeCount[value]--;
208 for (
auto *it = inEdges[dstId].begin(); it != inEdges[dstId].end(); ++it) {
209 if ((*it).id == srcId && (*it).value == value) {
210 inEdges[dstId].erase(it);
215 for (
auto *it = outEdges[srcId].begin(); it != outEdges[srcId].end(); ++it) {
216 if ((*it).id == dstId && (*it).value == value) {
217 outEdges[srcId].erase(it);
229 worklist.push_back({srcId, 0});
232 while (!worklist.empty()) {
233 auto &idAndIndex = worklist.back();
235 if (idAndIndex.first == dstId)
239 if (outEdges.count(idAndIndex.first) == 0 ||
240 idAndIndex.second == outEdges[idAndIndex.first].size()) {
245 Edge edge = outEdges[idAndIndex.first][idAndIndex.second];
252 if (!afterDst && edge.
id != idAndIndex.first)
253 worklist.push_back({edge.
id, 0});
262 unsigned inEdgeCount = 0;
263 if (inEdges.count(
id) > 0)
264 for (
auto &inEdge : inEdges[
id])
265 if (inEdge.value == memref) {
266 Node *srcNode = getNode(inEdge.id);
277 unsigned outEdgeCount = 0;
278 if (outEdges.count(
id) > 0)
279 for (
auto &outEdge : outEdges[
id])
280 if (!memref || outEdge.value == memref)
292 if (!isa<MemRefType>(edge.value.getType()))
293 definingNodes.insert(edge.id);
302 if (outEdges.count(srcId) == 0)
303 return getNode(dstId)->op;
307 gatherDefiningNodes(dstId, definingNodes);
308 if (llvm::any_of(definingNodes,
309 [&](
unsigned id) {
return hasDependencePath(srcId,
id); })) {
310 LLVM_DEBUG(llvm::dbgs()
311 <<
"Can't fuse: a defining op with a user in the dst "
312 "loop has dependence from the src loop\n");
318 for (
auto &outEdge : outEdges[srcId])
319 if (outEdge.id != dstId)
320 srcDepInsts.insert(getNode(outEdge.id)->op);
324 for (
auto &inEdge : inEdges[dstId])
325 if (inEdge.id != srcId)
326 dstDepInsts.insert(getNode(inEdge.id)->op);
328 Operation *srcNodeInst = getNode(srcId)->op;
329 Operation *dstNodeInst = getNode(dstId)->op;
342 std::optional<unsigned> firstSrcDepPos;
343 std::optional<unsigned> lastDstDepPos;
348 if (srcDepInsts.count(op) > 0 && firstSrcDepPos == std::nullopt)
349 firstSrcDepPos = pos;
350 if (dstDepInsts.count(op) > 0)
352 depInsts.push_back(op);
356 if (firstSrcDepPos.has_value()) {
357 if (lastDstDepPos.has_value()) {
358 if (*firstSrcDepPos <= *lastDstDepPos) {
364 return depInsts[*firstSrcDepPos];
380 if (inEdges.count(srcId) > 0) {
382 for (
auto &inEdge : oldInEdges) {
384 if (privateMemRefs.count(inEdge.value) == 0)
385 addEdge(inEdge.id, dstId, inEdge.value);
390 if (outEdges.count(srcId) > 0) {
392 for (
auto &outEdge : oldOutEdges) {
394 if (outEdge.id == dstId)
395 removeEdge(srcId, outEdge.id, outEdge.value);
396 else if (removeSrcId) {
397 addEdge(dstId, outEdge.id, outEdge.value);
398 removeEdge(srcId, outEdge.id, outEdge.value);
405 if (inEdges.count(dstId) > 0 && !privateMemRefs.empty()) {
407 for (
auto &inEdge : oldInEdges)
408 if (privateMemRefs.count(inEdge.value) > 0)
409 removeEdge(inEdge.id, dstId, inEdge.value);
419 if (inEdges.count(sibId) > 0) {
421 for (
auto &inEdge : oldInEdges) {
422 addEdge(inEdge.id, dstId, inEdge.value);
423 removeEdge(inEdge.id, sibId, inEdge.value);
430 if (outEdges.count(sibId) > 0) {
432 for (
auto &outEdge : oldOutEdges) {
433 addEdge(dstId, outEdge.id, outEdge.value);
434 removeEdge(sibId, outEdge.id, outEdge.value);
443 Node *node = getNode(
id);
444 llvm::append_range(node->
loads, loads);
445 llvm::append_range(node->
stores, stores);
449 Node *node = getNode(
id);
457 unsigned id,
const std::function<
void(
Edge)> &callback) {
458 if (inEdges.count(
id) > 0)
459 forEachMemRefEdge(inEdges[
id], callback);
465 unsigned id,
const std::function<
void(
Edge)> &callback) {
466 if (outEdges.count(
id) > 0)
467 forEachMemRefEdge(outEdges[
id], callback);
474 for (
const auto &edge : edges) {
476 if (!isa<MemRefType>(edge.value.getType()))
478 assert(nodes.count(edge.id) > 0);
480 if (!isa<AffineForOp>(getNode(edge.id)->op))
488 os <<
"\nMemRefDependenceGraph\n";
490 for (
const auto &idAndNode : nodes) {
491 os <<
"Node: " << idAndNode.first <<
"\n";
492 auto it = inEdges.find(idAndNode.first);
493 if (it != inEdges.end()) {
494 for (
const auto &e : it->second)
495 os <<
" InEdge: " << e.id <<
" " << e.value <<
"\n";
497 it = outEdges.find(idAndNode.first);
498 if (it != outEdges.end()) {
499 for (
const auto &e : it->second)
500 os <<
" OutEdge: " << e.id <<
" " << e.value <<
"\n";
508 AffineForOp currAffineForOp;
512 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
513 loops->push_back(currAffineForOp);
514 currOp = currOp->getParentOp();
516 std::reverse(loops->begin(), loops->end());
527 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))
528 ops->push_back(currOp);
531 std::reverse(ops->begin(), ops->end());
538 assert(!ivs.empty() &&
"Cannot have a slice without its IVs");
541 for (
Value iv : ivs) {
543 assert(loop &&
"Expected affine for");
553 assert(!lbOperands.empty());
555 unsigned numDims = ivs.size();
557 unsigned numSymbols = lbOperands[0].size();
561 values.append(lbOperands[0].begin(), lbOperands[0].end());
566 for (
unsigned i = numDims, end = values.size(); i < end; ++i) {
567 Value value = values[i];
568 assert(cst->
containsVar(value) &&
"value expected to be present");
572 cst->
addBound(BoundType::EQ, value, cOp.value());
582 "should not fail as we never have semi-affine slice maps");
596 llvm::errs() <<
"\tIVs:\n";
598 llvm::errs() <<
"\t\t" << iv <<
"\n";
600 llvm::errs() <<
"\tLBs:\n";
602 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
603 llvm::errs() <<
"\t\tOperands:\n";
604 for (
Value lbOp : lbOperands[en.index()])
605 llvm::errs() <<
"\t\t\t" << lbOp <<
"\n";
608 llvm::errs() <<
"\tUBs:\n";
610 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
611 llvm::errs() <<
"\t\tOperands:\n";
612 for (
Value ubOp : ubOperands[en.index()])
613 llvm::errs() <<
"\t\t\t" << ubOp <<
"\n";
622 std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck()
const {
623 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
624 "Unexpected number of lbs, ubs and ivs in slice");
626 for (
unsigned i = 0, end = lbs.size(); i < end; ++i) {
648 AffineForOp dstLoop =
652 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
653 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
657 assert(srcLoop &&
"Expected affine for");
658 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
659 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
679 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
680 srcLoop.getStep() != dstLoop.getStep())
701 std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
702 if (isValidFastCheck && *isValidFastCheck)
708 if (
failed(getSourceAsConstraints(srcConstraints))) {
709 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute source's domain\n");
715 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle symbols in source domain\n");
722 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle locals in source domain\n");
729 if (
failed(getAsConstraints(&sliceConstraints))) {
730 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute slice's domain\n");
739 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the source of the slice:\n");
740 LLVM_DEBUG(srcConstraints.
dump());
741 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the slice if this fusion succeeds "
742 "(expressed in terms of its source's IVs):\n");
743 LLVM_DEBUG(sliceConstraints.
dump());
751 LLVM_DEBUG(llvm::dbgs() <<
"Incorrect slice\n");
763 std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
764 if (isMaximalFastCheck)
765 return isMaximalFastCheck;
771 for (
Value iv : ivs) {
773 assert(loop &&
"Expected affine for");
781 for (
Value lbOp : lbOperands[0])
783 consumerIVs.push_back(lbOp);
787 for (
int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
788 consumerIVs.push_back(
Value());
811 return cast<MemRefType>(memref.getType()).getRank();
817 auto memRefType = cast<MemRefType>(memref.getType());
818 unsigned rank = memRefType.getRank();
820 shape->reserve(rank);
822 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
830 for (
unsigned r = 0; r < rank; r++) {
831 cstWithShapeBounds.
addBound(BoundType::LB, r, 0);
832 int64_t dimSize = memRefType.getDimSize(r);
833 if (ShapedType::isDynamic(dimSize))
835 cstWithShapeBounds.
addBound(BoundType::UB, r, dimSize - 1);
840 int64_t numElements = 1;
841 int64_t diffConstant;
843 for (
unsigned d = 0; d < rank; d++) {
845 std::optional<int64_t> diff =
847 if (diff.has_value()) {
848 diffConstant = *diff;
849 assert(diffConstant >= 0 &&
"Dim size bound can't be negative");
850 assert(lbDivisor > 0);
854 auto dimSize = memRefType.getDimSize(d);
855 if (dimSize == ShapedType::kDynamic)
857 diffConstant = dimSize;
862 numElements *= diffConstant;
865 assert(lbDivisors &&
"both lbs and lbDivisor or none");
866 lbDivisors->push_back(lbDivisor);
869 shape->push_back(diffConstant);
877 assert(pos < cst.getNumDimVars() &&
"invalid position");
878 auto memRefType = cast<MemRefType>(memref.getType());
879 unsigned rank = memRefType.getRank();
881 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
883 auto boundPairs = cst.getLowerAndUpperBound(
884 pos, 0, rank, cst.getNumDimAndSymbolVars(),
885 {}, memRefType.getContext());
886 lbMap = boundPairs.first;
887 ubMap = boundPairs.second;
888 assert(lbMap &&
"lower bound for a region must exist");
889 assert(ubMap &&
"upper bound for a region must exist");
890 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
891 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
895 assert(memref == other.
memref);
918 bool addMemRefDimBounds) {
919 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
920 "affine read/write op expected");
926 unsigned rank = access.
getRank();
928 LLVM_DEBUG(llvm::dbgs() <<
"MemRefRegion::compute: " << *op
929 <<
"\ndepth: " << loopDepth <<
"\n";);
935 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
937 ivs.resize(loopDepth);
953 operands.resize(numOperands);
954 for (
unsigned i = 0; i < numOperands; ++i)
957 if (sliceState !=
nullptr) {
958 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
960 for (
auto extraOperand : sliceState->
lbOperands[0]) {
961 if (!llvm::is_contained(operands, extraOperand)) {
962 operands.push_back(extraOperand);
974 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
975 auto operand = operands[i];
981 if (
failed(cst.addAffineForOpDomain(affineFor)))
984 if (
failed(cst.addAffineParallelOpDomain(parallelOp)))
988 Value symbol = operand;
990 cst.addBound(BoundType::EQ, symbol, constVal.value());
992 LLVM_DEBUG(llvm::dbgs() <<
"unknown affine dimensional value");
998 if (sliceState !=
nullptr) {
1000 for (
auto operand : sliceState->
lbOperands[0]) {
1001 cst.addInductionVarOrTerminalSymbol(operand);
1005 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
1008 "should not fail as we never have semi-affine slice maps");
1013 if (
failed(cst.composeMap(&accessValueMap))) {
1014 op->
emitError(
"getMemRefRegion: compose affine map failed");
1022 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
1028 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
1029 enclosingIVs.resize(loopDepth);
1031 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
1032 for (
Value var : vars) {
1034 cst.projectOut(var);
1040 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
1043 cst.constantFoldVarRange(cst.getNumDimVars(),
1044 cst.getNumSymbolVars());
1046 assert(cst.getNumDimVars() == rank &&
"unexpected MemRefRegion format");
1051 if (addMemRefDimBounds) {
1052 auto memRefType = cast<MemRefType>(memref.getType());
1053 for (
unsigned r = 0; r < rank; r++) {
1054 cst.addBound(BoundType::LB, r, 0);
1055 if (memRefType.isDynamicDim(r))
1057 cst.addBound(BoundType::UB, r, memRefType.getDimSize(r) - 1);
1060 cst.removeTrivialRedundancy();
1062 LLVM_DEBUG(llvm::dbgs() <<
"Memory region:\n");
1063 LLVM_DEBUG(cst.dump());
1067 std::optional<int64_t>
1069 auto elementType = memRefType.getElementType();
1071 unsigned sizeInBits;
1072 if (elementType.isIntOrFloat()) {
1073 sizeInBits = elementType.getIntOrFloatBitWidth();
1074 }
else if (
auto vectorType = dyn_cast<VectorType>(elementType)) {
1075 if (vectorType.getElementType().isIntOrFloat())
1077 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
1079 return std::nullopt;
1081 return std::nullopt;
1083 return llvm::divideCeil(sizeInBits, 8);
1088 auto memRefType = cast<MemRefType>(memref.getType());
1090 if (!memRefType.getLayout().isIdentity()) {
1091 LLVM_DEBUG(llvm::dbgs() <<
"Non-identity layout map not yet supported\n");
1102 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
1104 LLVM_DEBUG(llvm::dbgs() <<
"Dynamic shapes not yet supported\n");
1105 return std::nullopt;
1109 return std::nullopt;
1110 return *eltSize * *numElements;
1117 std::optional<uint64_t>
1119 if (!memRefType.hasStaticShape())
1120 return std::nullopt;
1121 auto elementType = memRefType.getElementType();
1122 if (!elementType.isIntOrFloat() && !isa<VectorType>(elementType))
1123 return std::nullopt;
1127 return std::nullopt;
1128 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
1129 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
1134 template <
typename LoadOrStoreOp>
1137 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
1138 AffineWriteOpInterface>::value,
1139 "argument should be either a AffineReadOpInterface or a "
1140 "AffineWriteOpInterface");
1142 Operation *op = loadOrStoreOp.getOperation();
1144 if (
failed(region.compute(op, 0,
nullptr,
1148 LLVM_DEBUG(llvm::dbgs() <<
"Memory region");
1149 LLVM_DEBUG(region.getConstraints()->dump());
1151 bool outOfBounds =
false;
1152 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
1155 for (
unsigned r = 0; r < rank; r++) {
1162 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
1168 ucst.addBound(BoundType::LB, r, dimSize);
1169 outOfBounds = !ucst.isEmpty();
1171 loadOrStoreOp.emitOpError()
1172 <<
"memref out of upper bound access along dimension #" << (r + 1);
1177 std::fill(ineq.begin(), ineq.end(), 0);
1179 lcst.addBound(BoundType::UB, r, -1);
1180 outOfBounds = !lcst.isEmpty();
1182 loadOrStoreOp.emitOpError()
1183 <<
"memref out of lower bound access along dimension #" << (r + 1);
1202 while (block != limitBlock) {
1205 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
1206 positions->push_back(instPosInBlock);
1210 std::reverse(positions->begin(), positions->end());
1217 unsigned level,
Block *block) {
1219 for (
auto &op : *block) {
1220 if (i != positions[level]) {
1224 if (level == positions.size() - 1)
1226 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
1228 childAffineForOp.getBody());
1231 for (
auto &b : region)
1243 for (
unsigned i = 0, e = cst->
getNumDimVars(); i < e; ++i) {
1245 if (ivs.count(value) == 0) {
1259 unsigned numOps = ops.size();
1260 assert(numOps > 0 &&
"Expected at least one operation");
1262 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
1264 for (
unsigned i = 0; i < numOps; ++i) {
1267 std::min(loopDepthLimit,
static_cast<unsigned>(loops[i].size()));
1270 unsigned loopDepth = 0;
1271 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
1273 for (i = 1; i < numOps; ++i) {
1274 if (loops[i - 1][d] != loops[i][d])
1277 if (surroundingLoops)
1278 surroundingLoops->push_back(loops[i - 1][d]);
1291 unsigned numCommonLoops,
bool isBackwardSlice,
1297 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
1298 for (
auto *i : opsA) {
1300 for (
auto *
j : opsB) {
1307 LLVM_DEBUG(llvm::dbgs() <<
"Invalid loop depth\n");
1311 bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.
opInst) &&
1312 isa<AffineReadOpInterface>(dstAccess.
opInst);
1316 srcAccess, dstAccess, numCommonLoops + 1,
1317 &dependenceConstraints,
nullptr,
1320 LLVM_DEBUG(llvm::dbgs() <<
"Dependence check failed\n");
1325 dependentOpPairs.emplace_back(i,
j);
1330 loopDepth, isBackwardSlice,
1336 LLVM_DEBUG(llvm::dbgs()
1337 <<
"Unable to compute slice bound constraints\n");
1347 LLVM_DEBUG(llvm::dbgs()
1348 <<
"Unable to compute slice bound constraints\n");
1358 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimVars(); k < l; ++k)
1359 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
1361 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimVars(); k < l; ++k)
1362 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
1380 LLVM_DEBUG(llvm::dbgs()
1381 <<
"Unable to compute union bounding box of slice bounds\n");
1393 for (
auto &dep : dependentOpPairs) {
1394 ops.push_back(isBackwardSlice ? dep.second : dep.first);
1397 unsigned innermostCommonLoopDepth =
1399 if (loopDepth > innermostCommonLoopDepth) {
1400 LLVM_DEBUG(llvm::dbgs() <<
"Exceeds max loop depth\n");
1420 sliceUnionCst.
getValues(numSliceLoopIVs,
1422 &sliceBoundOperands);
1425 sliceUnion->
ivs.clear();
1426 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
1431 ? surroundingLoops[loopDepth - 1].getBody()->begin()
1432 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
1436 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1437 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1441 std::optional<bool> isSliceValid = sliceUnion->
isSliceValid();
1442 if (!isSliceValid) {
1443 LLVM_DEBUG(llvm::dbgs() <<
"Cannot determine if the slice is valid\n");
1455 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
1456 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
1465 return std::nullopt;
1475 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1476 unsigned numSrcLoopIVs = slice.
ivs.size();
1478 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1480 auto *op = forOp.getOperation();
1489 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1490 (*tripCountMap)[op] =
1491 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1495 if (maybeConstTripCount.has_value()) {
1496 (*tripCountMap)[op] = *maybeConstTripCount;
1503 if (!tripCount.has_value())
1505 (*tripCountMap)[op] = *tripCount;
1512 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1513 uint64_t iterCount = 1;
1514 for (
const auto &count : sliceTripCountMap) {
1515 iterCount *= count.second;
1532 unsigned numSrcLoopIVs = srcLoopIVs.size();
1537 unsigned numDstLoopIVs = dstLoopIVs.size();
1539 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1540 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1543 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1545 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1549 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1550 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1551 dependenceConstraints->
getValues(offset, offset + numSliceLoopIVs,
1561 &sliceState->
lbs, &sliceState->
ubs);
1566 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1567 if (i < offset || i >= offset + numSliceLoopIVs) {
1568 sliceBoundOperands.push_back(dependenceConstraints->
getValue(i));
1574 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1575 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1579 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1580 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1582 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1583 if (isa<AffineReadOpInterface>(depSourceOp) &&
1584 isa<AffineReadOpInterface>(depSinkOp)) {
1590 auto getSliceLoop = [&](
unsigned i) {
1591 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1593 auto isInnermostInsertion = [&]() {
1594 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1595 : loopDepth >= dstLoopIVs.size());
1597 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1598 auto srcIsUnitSlice = [&]() {
1605 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1606 Value iv = getSliceLoop(i).getInductionVar();
1607 if (sequentialLoops.count(iv) == 0 &&
1615 std::optional<bool> isMaximal = sliceState->
isMaximal();
1617 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1619 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1645 unsigned numSrcLoopIVs = srcLoopIVs.size();
1650 unsigned dstLoopIVsSize = dstLoopIVs.size();
1651 if (dstLoopDepth > dstLoopIVsSize) {
1652 dstOpInst->
emitError(
"invalid destination loop depth");
1653 return AffineForOp();
1663 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1664 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1665 auto sliceLoopNest =
1666 cast<AffineForOp>(b.
clone(*srcLoopIVs[0].getOperation()));
1675 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1676 (void)sliceSurroundingLoopsSize;
1677 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1678 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1679 (void)sliceLoopLimit;
1680 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1683 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1684 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1686 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1688 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1690 return sliceLoopNest;
1696 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1697 memref = loadOp.getMemRef();
1698 opInst = loadOrStoreOpInst;
1699 llvm::append_range(indices, loadOp.getMapOperands());
1701 assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1702 "Affine read/write op expected");
1703 auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1704 opInst = loadOrStoreOpInst;
1705 memref = storeOp.getMemRef();
1706 llvm::append_range(indices, storeOp.getMapOperands());
1711 return cast<MemRefType>(memref.getType()).getRank();
1715 return isa<AffineWriteOpInterface>(opInst);
1724 if (isa<AffineForOp>(currOp))
1737 if (memref != rhs.
memref)
1741 getAccessMap(&thisMap);
1750 AffineForOp currAffineForOp;
1754 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
1755 ivs.push_back(currAffineForOp.getInductionVar());
1756 else if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
1757 llvm::append_range(ivs, parOp.getIVs());
1758 currOp = currOp->getParentOp();
1760 std::reverse(ivs.begin(), ivs.end());
1771 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
1772 unsigned numCommonLoops = 0;
1773 for (
unsigned i = 0; i < minNumLoops; ++i) {
1774 if (loopsA[i] != loopsB[i])
1778 return numCommonLoops;
1785 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
1789 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
1795 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
1797 region->compute(opInst,
1799 return opInst->
emitError(
"error obtaining memory region\n");
1802 auto it = regions.find(region->memref);
1803 if (it == regions.end()) {
1804 regions[region->memref] = std::move(region);
1805 }
else if (
failed(it->second->unionBoundingBox(*region))) {
1807 "getMemoryFootprintBytes: unable to perform a union on a memory "
1812 if (result.wasInterrupted())
1813 return std::nullopt;
1815 int64_t totalSizeInBytes = 0;
1816 for (
const auto ®ion : regions) {
1817 std::optional<int64_t> size = region.second->getRegionSize();
1818 if (!size.has_value())
1819 return std::nullopt;
1820 totalSizeInBytes += *size;
1822 return totalSizeInBytes;
1827 auto *forInst = forOp.getOperation();
1838 return !reductions.empty();
1844 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
1846 if (
auto innerFor = dyn_cast<AffineForOp>(op))
1848 sequentialLoops->insert(innerFor.getInductionVar());
1860 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
1861 return simplifiedSet;
1867 llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
1868 return val.has_value() ? *val :
Value();
1887 for (
unsigned i = syms.size(); i < newSyms.size(); ++i)
1889 return constraints.
addBound(type, pos, alignedMap);
1896 newResults.push_back(r + val);
1940 bool isMin = isa<AffineMinOp>(op);
1941 assert((isMin || isa<AffineMaxOp>(op)) &&
"expect AffineMin/MaxOp");
1945 isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
1952 unsigned resultDimStart = constraints.
appendDimVar(numResults);
1956 auto boundType = isMin ? BoundType::UB : BoundType::LB;
1967 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
1978 if (
failed(constraints.
addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))
1996 for (
unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
2004 map.
getSubMap({i - resultDimStart}), operands)))
2012 ineq[dimOpBound] = isMin ? 1 : -1;
2013 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)
MemRefDependenceGraph::Node Node
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 MLIRContext * getContext(OpFoldResult val)
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.
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.
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.
bool isBeforeInBlock(Operation *other)
Given an operation 'other' that is within the same parent block, return whether the current operation...
InFlightDiagnostic emitWarning(const Twine &message={})
Emit a warning about this operation, reporting up to any diagnostic handlers that may be listening.
std::enable_if_t< llvm::function_traits< std::decay_t< FnT > >::num_args==1, RetT > walk(FnT &&callback)
Walk the operation by calling the callback for each nested operation (including this one),...
MLIRContext * getContext()
Return the context this operation is associated with.
unsigned getNumRegions()
Returns the number of regions held by this operation.
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...
Type getType() const
Return the type of this value.
A utility result that is used to signal how to proceed with an ongoing walk:
static WalkResult advance()
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...
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...
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
std::optional< uint64_t > getConstantTripCount(AffineForOp forOp)
Returns the trip count of the loop if it's a constant, std::nullopt otherwise.
IntegerSet simplifyIntegerSet(IntegerSet set)
Simplify the integer set by simplifying the underlying affine expressions by flattening and some simp...
void getEnclosingAffineOps(Operation &op, SmallVectorImpl< Operation * > *ops)
Populates 'ops' with affine operations enclosing op ordered from outermost to innermost.
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 ...
bool isAffineInductionVar(Value val)
Returns true if the provided value is the induction variable of an AffineForOp or AffineParallelOp.
bool isLoopParallelAndContainsReduction(AffineForOp forOp)
Returns whether a loop is a parallel loop and contains a reduction loop.
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
AffineForOp getForInductionVarOwner(Value val)
Returns the loop parent of an induction variable.
void getAffineIVs(Operation &op, SmallVectorImpl< Value > &ivs)
Populates 'ivs' with IVs of the surrounding affine.for and affine.parallel ops ordered from the outer...
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 getSequentialLoops(AffineForOp forOp, llvm::SmallDenseSet< Value, 8 > *sequentialLoops)
Returns in 'sequentialLoops' all sequential loops in loop nest rooted at 'forOp'.
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints=nullptr, SmallVector< DependenceComponent, 2 > *dependenceComponents=nullptr, bool allowRAR=false)
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
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....
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 getInnermostCommonLoopDepth(ArrayRef< Operation * > ops, SmallVectorImpl< AffineForOp > *surroundingLoops=nullptr)
Returns the innermost common loop depth for the set of operations in 'ops'.
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...
AffineParallelOp getAffineParallelInductionVarOwner(Value val)
Returns true if the provided value is among the induction variables of an AffineParallelOp.
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,...
unsigned getNestingDepth(Operation *op)
Returns the nesting depth of this operation, i.e., the number of loops surrounding this operation.
uint64_t getSliceIterationCount(const llvm::SmallDenseMap< Operation *, uint64_t, 8 > &sliceTripCountMap)
Return the number of iterations for the slicetripCountMap provided.
bool isLoopParallel(AffineForOp forOp, SmallVectorImpl< LoopReduction > *parallelReductions=nullptr)
Returns true if ‘forOp’ is a parallel loop.
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 ...
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...
AffineForOp insertBackwardComputationSlice(Operation *srcOpInst, Operation *dstOpInst, unsigned dstLoopDepth, ComputationSliceState *sliceState)
Creates a clone of the computation contained in the loop nest surrounding 'srcOpInst',...
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...
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...
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
BoundType
The type of bound: equal, lower bound or upper bound.
This header declares functions that assist transformations in the MemRef dialect.
LogicalResult failure(bool isFailure=true)
Utility function to generate a LogicalResult.
std::optional< int64_t > getConstantIntValue(OpFoldResult ofr)
If ofr is a constant integer or an IntegerAttr, return the integer.
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.
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.
ComputationSliceState aggregates loop IVs, loop bound AffineMaps and their associated operands for a ...
std::optional< bool > isSliceValid() const
Checks the validity of the slice computed.
SmallVector< Value, 4 > ivs
LogicalResult getAsConstraints(FlatAffineValueConstraints *cst) const
LogicalResult getSourceAsConstraints(FlatAffineValueConstraints &cst) const
Adds to 'cst' constraints which represent the original loop bounds on 'ivs' in 'this'.
std::vector< SmallVector< Value, 4 > > ubOperands
SmallVector< AffineMap, 4 > ubs
std::optional< bool > isMaximal() const
Returns true if the computation slice encloses all the iterations of the sliced loop nest.
SmallVector< AffineMap, 4 > lbs
Block::iterator insertPoint
std::vector< SmallVector< Value, 4 > > lbOperands
Checks whether two accesses to the same memref access the same element.
enum mlir::affine::DependenceResult::ResultEnum value
void collect(Operation *opToWalk)
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...
SmallVector< Operation *, 4 > loads
SmallVector< Operation *, 4 > stores
unsigned getStoreOpCount(Value memref) const
unsigned addNode(Operation *op)
unsigned getIncomingMemRefAccesses(unsigned id, Value memref)
void removeEdge(unsigned srcId, unsigned dstId, Value value)
void addEdge(unsigned srcId, unsigned dstId, Value value)
Node * getForOpNode(AffineForOp forOp)
bool hasDependencePath(unsigned srcId, unsigned dstId)
void clearNodeLoadAndStores(unsigned id)
void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)
bool writesToLiveInOrEscapingMemrefs(unsigned id)
void addToNode(unsigned id, const SmallVectorImpl< Operation * > &loads, const SmallVectorImpl< Operation * > &stores)
void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)
unsigned getOutEdgeCount(unsigned id, Value memref=nullptr)
void removeNode(unsigned id)
Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId)
void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)
void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)
bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr)
void gatherDefiningNodes(unsigned id, DenseSet< unsigned > &definingNodes)
Return all nodes which define SSA values used in node 'id'.
Node * getNode(unsigned id)
void print(raw_ostream &os) const
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)
Value memref
Memref that this region corresponds to.
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...
Enumerates different result statuses of slice computation by computeSliceUnion
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.