23 #include "llvm/ADT/SetVector.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 (
auto forOp = dyn_cast<AffineForOp>(op)) {
44 forOps.push_back(forOp);
45 }
else if (isa<AffineReadOpInterface>(op)) {
46 loadOpInsts.push_back(op);
47 }
else if (isa<AffineWriteOpInterface>(op)) {
48 storeOpInsts.push_back(op);
50 auto memInterface = dyn_cast<MemoryEffectOpInterface>(op);
57 if (!isa<MemRefType>(v.getType()))
60 memrefLoads.push_back(op);
61 memrefStores.push_back(op);
65 if (hasEffect<MemoryEffects::Read>(op))
66 memrefLoads.push_back(op);
67 if (hasEffect<MemoryEffects::Write>(op))
68 memrefStores.push_back(op);
69 if (hasEffect<MemoryEffects::Free>(op))
70 memrefFrees.push_back(op);
76 unsigned Node::getLoadOpCount(
Value memref)
const {
77 unsigned loadOpCount = 0;
80 if (
auto affineLoad = dyn_cast<AffineReadOpInterface>(loadOp)) {
81 if (memref == affineLoad.getMemRef())
83 }
else if (hasEffect<MemoryEffects::Read>(loadOp, memref)) {
91 unsigned Node::getStoreOpCount(
Value memref)
const {
92 unsigned storeOpCount = 0;
93 for (
auto *storeOp : llvm::concat<Operation *const>(stores, memrefStores)) {
95 if (
auto affineStore = dyn_cast<AffineWriteOpInterface>(storeOp)) {
96 if (memref == affineStore.getMemRef())
98 }
else if (hasEffect<MemoryEffects::Write>(
const_cast<Operation *
>(storeOp),
107 unsigned Node::hasStore(
Value memref)
const {
109 llvm::concat<Operation *const>(stores, memrefStores),
111 if (
auto affineStore = dyn_cast<AffineWriteOpInterface>(storeOp)) {
112 if (memref == affineStore.getMemRef())
114 }
else if (hasEffect<MemoryEffects::Write>(storeOp, memref)) {
121 unsigned Node::hasFree(
Value memref)
const {
122 return llvm::any_of(memrefFrees, [&](
Operation *freeOp) {
123 return hasEffect<MemoryEffects::Free>(freeOp, memref);
128 void Node::getStoreOpsForMemref(
Value memref,
131 if (memref == cast<AffineWriteOpInterface>(storeOp).getMemRef())
132 storeOps->push_back(storeOp);
137 void Node::getLoadOpsForMemref(
Value memref,
140 if (memref == cast<AffineReadOpInterface>(loadOp).getMemRef())
141 loadOps->push_back(loadOp);
147 void Node::getLoadAndStoreMemrefSet(
149 llvm::SmallDenseSet<Value, 2> loadMemrefs;
151 loadMemrefs.insert(cast<AffineReadOpInterface>(loadOp).getMemRef());
154 auto memref = cast<AffineWriteOpInterface>(storeOp).getMemRef();
155 if (loadMemrefs.count(memref) > 0)
156 loadAndStoreMemrefSet->insert(memref);
162 template <
typename... EffectTys>
164 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
171 if (isa<MemRefType>(operand.getType()))
172 values.push_back(operand);
177 memOp.getEffects(effects);
178 for (
auto &effect : effects) {
179 Value effectVal = effect.getValue();
180 if (isa<EffectTys...>(effect.getEffect()) && effectVal &&
181 isa<MemRefType>(effectVal.
getType()))
182 values.push_back(effectVal);
191 auto &nodes = mdg.
nodes;
197 Node &node = nodes.insert({newNodeId,
Node(newNodeId, nodeOp)}).first->second;
199 node.
loads.push_back(op);
200 auto memref = cast<AffineReadOpInterface>(op).getMemRef();
201 memrefAccesses[memref].insert(node.id);
204 node.stores.push_back(op);
205 auto memref = cast<AffineWriteOpInterface>(op).getMemRef();
206 memrefAccesses[memref].insert(node.id);
210 getEffectedValues<MemoryEffects::Read>(op, effectedValues);
211 if (llvm::any_of(((
ValueRange)effectedValues).getTypes(),
212 [](
Type type) {
return !isa<MemRefType>(type); }))
215 for (
Value memref : effectedValues)
216 memrefAccesses[memref].insert(node.id);
217 node.memrefLoads.push_back(op);
221 getEffectedValues<MemoryEffects::Write>(op, effectedValues);
222 if (llvm::any_of((
ValueRange(effectedValues)).getTypes(),
223 [](
Type type) {
return !isa<MemRefType>(type); }))
225 for (
Value memref : effectedValues)
226 memrefAccesses[memref].insert(node.id);
227 node.memrefStores.push_back(op);
231 getEffectedValues<MemoryEffects::Free>(op, effectedValues);
232 if (llvm::any_of((
ValueRange(effectedValues)).getTypes(),
233 [](
Type type) {
return !isa<MemRefType>(type); }))
235 for (
Value memref : effectedValues)
236 memrefAccesses[memref].insert(node.id);
237 node.memrefFrees.push_back(op);
244 LLVM_DEBUG(llvm::dbgs() <<
"--- Initializing MDG ---\n");
252 if (
auto forOp = dyn_cast<AffineForOp>(op)) {
256 forToNodeMap[&op] = node->
id;
257 }
else if (isa<AffineReadOpInterface>(op)) {
259 Node node(nextNodeId++, &op);
260 node.
loads.push_back(&op);
261 auto memref = cast<AffineReadOpInterface>(op).getMemRef();
262 memrefAccesses[memref].insert(node.
id);
263 nodes.insert({node.
id, node});
264 }
else if (isa<AffineWriteOpInterface>(op)) {
266 Node node(nextNodeId++, &op);
267 node.
stores.push_back(&op);
268 auto memref = cast<AffineWriteOpInterface>(op).getMemRef();
269 memrefAccesses[memref].insert(node.
id);
270 nodes.insert({node.
id, node});
271 }
else if (op.getNumResults() > 0 && !op.use_empty()) {
278 (op.getNumRegions() == 0 || isa<RegionBranchOpInterface>(op))) {
287 }
else if (op.getNumRegions() != 0 && !isa<RegionBranchOpInterface>(op)) {
291 LLVM_DEBUG(llvm::dbgs()
292 <<
"MDG init failed; unknown region-holding op found!\n");
300 LLVM_DEBUG(llvm::dbgs() <<
"Created " << nodes.size() <<
" nodes\n");
304 for (
auto &idAndNode : nodes) {
305 const Node &node = idAndNode.second;
313 if (block.getParent()->findAncestorOpInRegion(*user)->getBlock() !=
320 auto *it = llvm::find_if(loops, [&](AffineForOp loop) {
321 return loop->getBlock() == █
323 if (it == loops.end())
325 assert(forToNodeMap.count(*it) > 0 &&
"missing mapping");
326 unsigned userLoopNestId = forToNodeMap[*it];
327 addEdge(node.
id, userLoopNestId, value);
333 for (
auto &memrefAndList : memrefAccesses) {
334 unsigned n = memrefAndList.second.size();
335 Value srcMemRef = memrefAndList.first;
337 for (
unsigned i = 0; i < n; ++i) {
338 unsigned srcId = memrefAndList.second[i];
339 Node *srcNode = getNode(srcId);
340 bool srcHasStoreOrFree =
342 for (
unsigned j = i + 1;
j < n; ++
j) {
343 unsigned dstId = memrefAndList.second[
j];
344 Node *dstNode = getNode(dstId);
345 bool dstHasStoreOrFree =
347 if (srcHasStoreOrFree || dstHasStoreOrFree)
348 addEdge(srcId, dstId, srcMemRef);
357 auto it = nodes.find(
id);
358 assert(it != nodes.end());
364 for (
auto &idAndNode : nodes)
365 if (idAndNode.second.op == forOp)
366 return &idAndNode.second;
372 Node node(nextNodeId++, op);
373 nodes.insert({node.
id, node});
380 if (inEdges.count(
id) > 0) {
382 for (
auto &inEdge : oldInEdges) {
383 removeEdge(inEdge.id,
id, inEdge.value);
387 if (outEdges.contains(
id)) {
389 for (
auto &outEdge : oldOutEdges) {
390 removeEdge(
id, outEdge.id, outEdge.value);
402 const Node *node = getNode(
id);
403 for (
auto *storeOpInst : node->
stores) {
404 auto memref = cast<AffineWriteOpInterface>(storeOpInst).getMemRef();
405 auto *op = memref.getDefiningOp();
411 for (
auto *user : memref.getUsers())
412 if (!isa<AffineMapAccessInterface>(*user))
423 if (!outEdges.contains(srcId) || !inEdges.contains(dstId)) {
426 bool hasOutEdge = llvm::any_of(outEdges.lookup(srcId), [=](
const Edge &edge) {
427 return edge.id == dstId && (!value || edge.value == value);
429 bool hasInEdge = llvm::any_of(inEdges.lookup(dstId), [=](
const Edge &edge) {
430 return edge.id == srcId && (!value || edge.value == value);
432 return hasOutEdge && hasInEdge;
438 if (!hasEdge(srcId, dstId, value)) {
439 outEdges[srcId].push_back({dstId, value});
440 inEdges[dstId].push_back({srcId, value});
441 if (isa<MemRefType>(value.
getType()))
442 memrefEdgeCount[value]++;
449 assert(inEdges.count(dstId) > 0);
450 assert(outEdges.count(srcId) > 0);
451 if (isa<MemRefType>(value.
getType())) {
452 assert(memrefEdgeCount.count(value) > 0);
453 memrefEdgeCount[value]--;
456 for (
auto *it = inEdges[dstId].begin(); it != inEdges[dstId].end(); ++it) {
457 if ((*it).id == srcId && (*it).value == value) {
458 inEdges[dstId].erase(it);
463 for (
auto *it = outEdges[srcId].begin(); it != outEdges[srcId].end(); ++it) {
464 if ((*it).id == dstId && (*it).value == value) {
465 outEdges[srcId].erase(it);
475 unsigned dstId)
const {
478 worklist.push_back({srcId, 0});
481 while (!worklist.empty()) {
482 auto &idAndIndex = worklist.back();
484 if (idAndIndex.first == dstId)
488 if (!outEdges.contains(idAndIndex.first) ||
489 idAndIndex.second == outEdges.lookup(idAndIndex.first).size()) {
494 const Edge edge = outEdges.lookup(idAndIndex.first)[idAndIndex.second];
501 if (!afterDst && edge.
id != idAndIndex.first)
502 worklist.push_back({edge.
id, 0});
510 Value memref)
const {
511 unsigned inEdgeCount = 0;
512 for (
const Edge &inEdge : inEdges.lookup(
id)) {
513 if (inEdge.value == memref) {
514 const Node *srcNode = getNode(inEdge.id);
526 Value memref)
const {
527 unsigned outEdgeCount = 0;
528 for (
const auto &outEdge : outEdges.lookup(
id))
529 if (!memref || outEdge.value == memref)
537 for (
const Edge &edge : inEdges.lookup(
id))
541 if (!isa<MemRefType>(edge.value.getType()))
542 definingNodes.insert(edge.id);
550 unsigned dstId)
const {
551 if (!outEdges.contains(srcId))
552 return getNode(dstId)->op;
556 gatherDefiningNodes(dstId, definingNodes);
557 if (llvm::any_of(definingNodes,
558 [&](
unsigned id) {
return hasDependencePath(srcId,
id); })) {
559 LLVM_DEBUG(llvm::dbgs()
560 <<
"Can't fuse: a defining op with a user in the dst "
561 "loop has dependence from the src loop\n");
567 for (
auto &outEdge : outEdges.lookup(srcId))
568 if (outEdge.id != dstId)
569 srcDepInsts.insert(getNode(outEdge.id)->op);
573 for (
auto &inEdge : inEdges.lookup(dstId))
574 if (inEdge.id != srcId)
575 dstDepInsts.insert(getNode(inEdge.id)->op);
577 Operation *srcNodeInst = getNode(srcId)->op;
578 Operation *dstNodeInst = getNode(dstId)->op;
591 std::optional<unsigned> firstSrcDepPos;
592 std::optional<unsigned> lastDstDepPos;
597 if (srcDepInsts.count(op) > 0 && firstSrcDepPos == std::nullopt)
598 firstSrcDepPos = pos;
599 if (dstDepInsts.count(op) > 0)
601 depInsts.push_back(op);
605 if (firstSrcDepPos.has_value()) {
606 if (lastDstDepPos.has_value()) {
607 if (*firstSrcDepPos <= *lastDstDepPos) {
613 return depInsts[*firstSrcDepPos];
629 if (inEdges.count(srcId) > 0) {
631 for (
auto &inEdge : oldInEdges) {
633 if (!privateMemRefs.contains(inEdge.value))
634 addEdge(inEdge.id, dstId, inEdge.value);
639 if (outEdges.count(srcId) > 0) {
641 for (
auto &outEdge : oldOutEdges) {
643 if (outEdge.id == dstId)
644 removeEdge(srcId, outEdge.id, outEdge.value);
645 else if (removeSrcId) {
646 addEdge(dstId, outEdge.id, outEdge.value);
647 removeEdge(srcId, outEdge.id, outEdge.value);
654 if (inEdges.count(dstId) > 0 && !privateMemRefs.empty()) {
656 for (
auto &inEdge : oldInEdges)
657 if (privateMemRefs.count(inEdge.value) > 0)
658 removeEdge(inEdge.id, dstId, inEdge.value);
668 if (inEdges.count(sibId) > 0) {
670 for (
auto &inEdge : oldInEdges) {
671 addEdge(inEdge.id, dstId, inEdge.value);
672 removeEdge(inEdge.id, sibId, inEdge.value);
679 if (outEdges.count(sibId) > 0) {
681 for (
auto &outEdge : oldOutEdges) {
682 addEdge(dstId, outEdge.id, outEdge.value);
683 removeEdge(sibId, outEdge.id, outEdge.value);
694 Node *node = getNode(
id);
695 llvm::append_range(node->
loads, loads);
696 llvm::append_range(node->
stores, stores);
697 llvm::append_range(node->
memrefLoads, memrefLoads);
699 llvm::append_range(node->
memrefFrees, memrefFrees);
703 Node *node = getNode(
id);
711 unsigned id,
const std::function<
void(
Edge)> &callback) {
712 if (inEdges.count(
id) > 0)
713 forEachMemRefEdge(inEdges[
id], callback);
719 unsigned id,
const std::function<
void(
Edge)> &callback) {
720 if (outEdges.count(
id) > 0)
721 forEachMemRefEdge(outEdges[
id], callback);
728 for (
const auto &edge : edges) {
730 if (!isa<MemRefType>(edge.value.getType()))
732 assert(nodes.count(edge.id) > 0);
734 if (!isa<AffineForOp>(getNode(edge.id)->op))
742 os <<
"\nMemRefDependenceGraph\n";
744 for (
const auto &idAndNode : nodes) {
745 os <<
"Node: " << idAndNode.first <<
"\n";
746 auto it = inEdges.find(idAndNode.first);
747 if (it != inEdges.end()) {
748 for (
const auto &e : it->second)
749 os <<
" InEdge: " << e.id <<
" " << e.value <<
"\n";
751 it = outEdges.find(idAndNode.first);
752 if (it != outEdges.end()) {
753 for (
const auto &e : it->second)
754 os <<
" OutEdge: " << e.id <<
" " << e.value <<
"\n";
762 AffineForOp currAffineForOp;
766 if (
auto currAffineForOp = dyn_cast<AffineForOp>(currOp))
767 loops->push_back(currAffineForOp);
768 currOp = currOp->getParentOp();
770 std::reverse(loops->begin(), loops->end());
781 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))
782 ops->push_back(currOp);
785 std::reverse(ops->begin(), ops->end());
792 assert(!ivs.empty() &&
"Cannot have a slice without its IVs");
795 for (
Value iv : ivs) {
797 assert(loop &&
"Expected affine for");
807 assert(!lbOperands.empty());
809 unsigned numDims = ivs.size();
811 unsigned numSymbols = lbOperands[0].size();
815 values.append(lbOperands[0].begin(), lbOperands[0].end());
820 for (
unsigned i = numDims, end = values.size(); i < end; ++i) {
821 Value value = values[i];
822 assert(cst->
containsVar(value) &&
"value expected to be present");
826 cst->
addBound(BoundType::EQ, value, cOp.value());
834 LogicalResult ret = cst->
addSliceBounds(ivs, lbs, ubs, lbOperands[0]);
835 assert(succeeded(ret) &&
836 "should not fail as we never have semi-affine slice maps");
850 llvm::errs() <<
"\tIVs:\n";
852 llvm::errs() <<
"\t\t" << iv <<
"\n";
854 llvm::errs() <<
"\tLBs:\n";
856 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
857 llvm::errs() <<
"\t\tOperands:\n";
858 for (
Value lbOp : lbOperands[en.index()])
859 llvm::errs() <<
"\t\t\t" << lbOp <<
"\n";
862 llvm::errs() <<
"\tUBs:\n";
864 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
865 llvm::errs() <<
"\t\tOperands:\n";
866 for (
Value ubOp : ubOperands[en.index()])
867 llvm::errs() <<
"\t\t\t" << ubOp <<
"\n";
876 std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck()
const {
877 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
878 "Unexpected number of lbs, ubs and ivs in slice");
880 for (
unsigned i = 0, end = lbs.size(); i < end; ++i) {
892 isa<AffineConstantExpr>(lbMap.
getResult(0)))
902 AffineForOp dstLoop =
906 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
907 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
911 assert(srcLoop &&
"Expected affine for");
912 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
913 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
925 if (!isa<AffineConstantExpr>(srcLbResult) ||
926 !isa<AffineConstantExpr>(srcUbResult) ||
927 !isa<AffineConstantExpr>(dstLbResult) ||
928 !isa<AffineConstantExpr>(dstUbResult))
933 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
934 srcLoop.getStep() != dstLoop.getStep())
955 std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
956 if (isValidFastCheck && *isValidFastCheck)
962 if (failed(getSourceAsConstraints(srcConstraints))) {
963 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute source's domain\n");
969 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle symbols in source domain\n");
976 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle locals in source domain\n");
983 if (failed(getAsConstraints(&sliceConstraints))) {
984 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute slice's domain\n");
993 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the source of the slice:\n");
994 LLVM_DEBUG(srcConstraints.
dump());
995 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the slice if this fusion succeeds "
996 "(expressed in terms of its source's IVs):\n");
997 LLVM_DEBUG(sliceConstraints.
dump());
1005 LLVM_DEBUG(llvm::dbgs() <<
"Incorrect slice\n");
1017 std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
1018 if (isMaximalFastCheck)
1019 return isMaximalFastCheck;
1025 for (
Value iv : ivs) {
1027 assert(loop &&
"Expected affine for");
1029 return std::nullopt;
1035 for (
Value lbOp : lbOperands[0])
1037 consumerIVs.push_back(lbOp);
1041 for (
int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
1042 consumerIVs.push_back(
Value());
1049 return std::nullopt;
1054 return std::nullopt;
1065 return cast<MemRefType>(memref.getType()).getRank();
1070 auto memRefType = cast<MemRefType>(memref.getType());
1072 unsigned rank = memRefType.getRank();
1074 shape->reserve(rank);
1076 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1084 for (
unsigned r = 0; r < rank; r++) {
1085 cstWithShapeBounds.
addBound(BoundType::LB, r, 0);
1086 int64_t dimSize = memRefType.getDimSize(r);
1087 if (ShapedType::isDynamic(dimSize))
1089 cstWithShapeBounds.
addBound(BoundType::UB, r, dimSize - 1);
1094 int64_t numElements = 1;
1095 int64_t diffConstant;
1096 for (
unsigned d = 0; d < rank; d++) {
1098 std::optional<int64_t> diff =
1100 if (diff.has_value()) {
1101 diffConstant = *diff;
1102 assert(diffConstant >= 0 &&
"dim size bound cannot be negative");
1106 auto dimSize = memRefType.getDimSize(d);
1107 if (ShapedType::isDynamic(dimSize))
1108 return std::nullopt;
1109 diffConstant = dimSize;
1114 numElements *= diffConstant;
1119 shape->push_back(diffConstant);
1126 assert(pos < cst.getNumDimVars() &&
"invalid position");
1127 auto memRefType = cast<MemRefType>(memref.getType());
1128 unsigned rank = memRefType.getRank();
1130 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1132 auto boundPairs = cst.getLowerAndUpperBound(
1133 pos, 0, rank, cst.getNumDimAndSymbolVars(),
1134 {}, memRefType.getContext());
1135 lbMap = boundPairs.first;
1136 ubMap = boundPairs.second;
1137 assert(lbMap &&
"lower bound for a region must exist");
1138 assert(ubMap &&
"upper bound for a region must exist");
1139 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1140 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1144 assert(memref == other.
memref);
1167 bool addMemRefDimBounds,
bool dropLocalVars,
1168 bool dropOuterIvs) {
1169 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
1170 "affine read/write op expected");
1176 unsigned rank = access.
getRank();
1178 LLVM_DEBUG(llvm::dbgs() <<
"MemRefRegion::compute: " << *op
1179 <<
"\ndepth: " << loopDepth <<
"\n";);
1185 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
1187 ivs.resize(loopDepth);
1203 operands.resize(numOperands);
1204 for (
unsigned i = 0; i < numOperands; ++i)
1207 if (sliceState !=
nullptr) {
1208 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
1210 for (
auto extraOperand : sliceState->
lbOperands[0]) {
1211 if (!llvm::is_contained(operands, extraOperand)) {
1212 operands.push_back(extraOperand);
1224 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
1225 auto operand = operands[i];
1231 if (failed(cst.addAffineForOpDomain(affineFor)))
1234 if (failed(cst.addAffineParallelOpDomain(parallelOp)))
1238 Value symbol = operand;
1240 cst.addBound(BoundType::EQ, symbol, constVal.value());
1242 LLVM_DEBUG(llvm::dbgs() <<
"unknown affine dimensional value");
1248 if (sliceState !=
nullptr) {
1250 for (
auto operand : sliceState->
lbOperands[0]) {
1251 if (failed(cst.addInductionVarOrTerminalSymbol(operand)))
1256 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
1258 assert(succeeded(ret) &&
1259 "should not fail as we never have semi-affine slice maps");
1264 if (failed(cst.composeMap(&accessValueMap))) {
1265 op->
emitError(
"getMemRefRegion: compose affine map failed");
1273 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
1279 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
1280 enclosingIVs.resize(loopDepth);
1282 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
1285 !llvm::is_contained(enclosingIVs, en.value())) {
1287 cst.projectOut(en.value());
1289 unsigned varPosition;
1290 cst.findVar(en.value(), &varPosition);
1291 auto varKind = cst.getVarKindAt(varPosition);
1292 varPosition -= cst.getNumDimVars();
1293 cst.convertToLocal(varKind, varPosition, varPosition + 1);
1301 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
1304 cst.constantFoldVarRange(cst.getNumDimVars(),
1305 cst.getNumSymbolVars());
1307 assert(cst.getNumDimVars() == rank &&
"unexpected MemRefRegion format");
1312 if (addMemRefDimBounds) {
1313 auto memRefType = cast<MemRefType>(memref.getType());
1314 for (
unsigned r = 0; r < rank; r++) {
1315 cst.addBound(BoundType::LB, r, 0);
1316 if (memRefType.isDynamicDim(r))
1318 cst.addBound(BoundType::UB, r, memRefType.getDimSize(r) - 1);
1321 cst.removeTrivialRedundancy();
1323 LLVM_DEBUG(llvm::dbgs() <<
"Memory region:\n");
1324 LLVM_DEBUG(cst.dump());
1328 std::optional<int64_t>
1330 auto elementType = memRefType.getElementType();
1332 unsigned sizeInBits;
1333 if (elementType.isIntOrFloat()) {
1334 sizeInBits = elementType.getIntOrFloatBitWidth();
1335 }
else if (
auto vectorType = dyn_cast<VectorType>(elementType)) {
1336 if (vectorType.getElementType().isIntOrFloat())
1338 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
1340 return std::nullopt;
1342 return std::nullopt;
1349 auto memRefType = cast<MemRefType>(memref.getType());
1351 if (!memRefType.getLayout().isIdentity()) {
1352 LLVM_DEBUG(llvm::dbgs() <<
"Non-identity layout map not yet supported\n");
1357 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
1359 LLVM_DEBUG(llvm::dbgs() <<
"Dynamic shapes not yet supported\n");
1360 return std::nullopt;
1364 return std::nullopt;
1365 return *eltSize * *numElements;
1372 std::optional<uint64_t>
1374 if (!memRefType.hasStaticShape())
1375 return std::nullopt;
1376 auto elementType = memRefType.getElementType();
1377 if (!elementType.isIntOrFloat() && !isa<VectorType>(elementType))
1378 return std::nullopt;
1382 return std::nullopt;
1383 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
1384 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
1389 template <
typename LoadOrStoreOp>
1392 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
1393 AffineWriteOpInterface>::value,
1394 "argument should be either a AffineReadOpInterface or a "
1395 "AffineWriteOpInterface");
1397 Operation *op = loadOrStoreOp.getOperation();
1399 if (failed(region.compute(op, 0,
nullptr,
1403 LLVM_DEBUG(llvm::dbgs() <<
"Memory region");
1404 LLVM_DEBUG(region.getConstraints()->dump());
1406 bool outOfBounds =
false;
1407 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
1410 for (
unsigned r = 0; r < rank; r++) {
1417 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
1423 ucst.addBound(BoundType::LB, r, dimSize);
1424 outOfBounds = !ucst.isEmpty();
1426 loadOrStoreOp.emitOpError()
1427 <<
"memref out of upper bound access along dimension #" << (r + 1);
1432 llvm::fill(ineq, 0);
1434 lcst.addBound(BoundType::UB, r, -1);
1435 outOfBounds = !lcst.isEmpty();
1437 loadOrStoreOp.emitOpError()
1438 <<
"memref out of lower bound access along dimension #" << (r + 1);
1441 return failure(outOfBounds);
1445 template LogicalResult
1448 template LogicalResult
1457 while (block != limitBlock) {
1460 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
1461 positions->push_back(instPosInBlock);
1465 std::reverse(positions->begin(), positions->end());
1472 unsigned level,
Block *block) {
1474 for (
auto &op : *block) {
1475 if (i != positions[level]) {
1479 if (level == positions.size() - 1)
1481 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
1483 childAffineForOp.getBody());
1486 for (
auto &b : region)
1498 for (
unsigned i = 0, e = cst->
getNumDimVars(); i < e; ++i) {
1500 if (ivs.count(value) == 0) {
1514 unsigned numOps = ops.size();
1515 assert(numOps > 0 &&
"Expected at least one operation");
1517 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
1519 for (
unsigned i = 0; i < numOps; ++i) {
1522 std::min(loopDepthLimit,
static_cast<unsigned>(loops[i].size()));
1525 unsigned loopDepth = 0;
1526 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
1528 for (i = 1; i < numOps; ++i) {
1529 if (loops[i - 1][d] != loops[i][d])
1532 if (surroundingLoops)
1533 surroundingLoops->push_back(loops[i - 1][d]);
1546 unsigned numCommonLoops,
bool isBackwardSlice,
1552 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
1564 LLVM_DEBUG(llvm::dbgs() <<
"Invalid loop depth\n");
1568 bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.
opInst) &&
1569 isa<AffineReadOpInterface>(dstAccess.
opInst);
1573 srcAccess, dstAccess, numCommonLoops + 1,
1574 &dependenceConstraints,
nullptr,
1577 LLVM_DEBUG(llvm::dbgs() <<
"Dependence check failed\n");
1582 dependentOpPairs.emplace_back(a, b);
1587 isBackwardSlice, &tmpSliceState);
1592 LLVM_DEBUG(llvm::dbgs()
1593 <<
"Unable to compute slice bound constraints\n");
1603 LLVM_DEBUG(llvm::dbgs()
1604 <<
"Unable to compute slice bound constraints\n");
1614 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimVars(); k < l; ++k)
1615 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
1617 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimVars(); k < l; ++k)
1618 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
1636 LLVM_DEBUG(llvm::dbgs()
1637 <<
"Unable to compute union bounding box of slice bounds\n");
1645 LLVM_DEBUG(llvm::dbgs() <<
"empty slice union - unexpected\n");
1651 for (
auto &dep : dependentOpPairs) {
1652 ops.push_back(isBackwardSlice ? dep.second : dep.first);
1655 unsigned innermostCommonLoopDepth =
1657 if (loopDepth > innermostCommonLoopDepth) {
1658 LLVM_DEBUG(llvm::dbgs() <<
"Exceeds max loop depth\n");
1678 sliceUnionCst.
getValues(numSliceLoopIVs,
1680 &sliceBoundOperands);
1683 sliceUnion->
ivs.clear();
1684 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
1690 ? surroundingLoops[loopDepth - 1].getBody()->begin()
1691 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
1695 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1696 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1700 std::optional<bool> isSliceValid = sliceUnion->
isSliceValid();
1701 if (!isSliceValid) {
1702 LLVM_DEBUG(llvm::dbgs() <<
"Cannot determine if the slice is valid\n");
1714 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
1715 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
1722 auto cExpr = dyn_cast<AffineConstantExpr>(loopSpanExpr);
1724 return std::nullopt;
1725 return cExpr.getValue();
1734 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1735 unsigned numSrcLoopIVs = slice.
ivs.size();
1737 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1739 auto *op = forOp.getOperation();
1748 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1749 (*tripCountMap)[op] =
1750 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1754 if (maybeConstTripCount.has_value()) {
1755 (*tripCountMap)[op] = *maybeConstTripCount;
1762 if (!tripCount.has_value())
1764 (*tripCountMap)[op] = *tripCount;
1771 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1772 uint64_t iterCount = 1;
1773 for (
const auto &count : sliceTripCountMap) {
1774 iterCount *= count.second;
1791 unsigned numSrcLoopIVs = srcLoopIVs.size();
1796 unsigned numDstLoopIVs = dstLoopIVs.size();
1798 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1799 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1802 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1804 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1809 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1810 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1811 sliceCst.
getValues(offset, offset + numSliceLoopIVs, &sliceState->
ivs);
1819 &sliceState->
lbs, &sliceState->
ubs);
1824 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1825 if (i < offset || i >= offset + numSliceLoopIVs)
1826 sliceBoundOperands.push_back(sliceCst.
getValue(i));
1831 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1832 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1836 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1837 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1839 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1840 if (isa<AffineReadOpInterface>(depSourceOp) &&
1841 isa<AffineReadOpInterface>(depSinkOp)) {
1847 auto getSliceLoop = [&](
unsigned i) {
1848 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1850 auto isInnermostInsertion = [&]() {
1851 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1852 : loopDepth >= dstLoopIVs.size());
1854 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1855 auto srcIsUnitSlice = [&]() {
1862 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1863 Value iv = getSliceLoop(i).getInductionVar();
1864 if (sequentialLoops.count(iv) == 0 &&
1872 std::optional<bool> isMaximal = sliceState->
isMaximal();
1874 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1876 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1902 unsigned numSrcLoopIVs = srcLoopIVs.size();
1907 unsigned dstLoopIVsSize = dstLoopIVs.size();
1908 if (dstLoopDepth > dstLoopIVsSize) {
1909 dstOpInst->
emitError(
"invalid destination loop depth");
1910 return AffineForOp();
1920 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1921 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1922 auto sliceLoopNest =
1923 cast<AffineForOp>(b.
clone(*srcLoopIVs[0].getOperation()));
1932 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1933 (void)sliceSurroundingLoopsSize;
1934 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1935 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1936 (void)sliceLoopLimit;
1937 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1940 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1941 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1943 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1945 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1947 return sliceLoopNest;
1953 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(memOp)) {
1954 memref = loadOp.getMemRef();
1956 llvm::append_range(indices, loadOp.getMapOperands());
1958 assert(isa<AffineWriteOpInterface>(memOp) &&
1959 "Affine read/write op expected");
1960 auto storeOp = cast<AffineWriteOpInterface>(memOp);
1962 memref = storeOp.getMemRef();
1963 llvm::append_range(indices, storeOp.getMapOperands());
1968 return cast<MemRefType>(memref.getType()).getRank();
1972 return isa<AffineWriteOpInterface>(opInst);
1981 if (isa<AffineForOp>(currOp))
1983 if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
1984 depth += parOp.getNumDims();
1996 if (memref != rhs.
memref)
2000 getAccessMap(&thisMap);
2002 return thisMap == rhsMap;
2007 AffineForOp currAffineForOp;
2011 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
2012 ivs.push_back(currAffineForOp.getInductionVar());
2013 else if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
2014 llvm::append_range(ivs, parOp.getIVs());
2015 currOp = currOp->getParentOp();
2017 std::reverse(ivs.begin(), ivs.end());
2028 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
2029 unsigned numCommonLoops = 0;
2030 for (
unsigned i = 0; i < minNumLoops; ++i) {
2031 if (loopsA[i] != loopsB[i])
2035 return numCommonLoops;
2042 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
2046 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
2052 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
2054 region->compute(opInst,
2056 LLVM_DEBUG(opInst->
emitError(
"error obtaining memory region"));
2060 auto [it, inserted] = regions.try_emplace(region->memref);
2062 it->second = std::move(region);
2063 }
else if (failed(it->second->unionBoundingBox(*region))) {
2065 "getMemoryFootprintBytes: unable to perform a union on a memory "
2071 if (result.wasInterrupted())
2072 return std::nullopt;
2074 int64_t totalSizeInBytes = 0;
2075 for (
const auto ®ion : regions) {
2076 std::optional<int64_t> size = region.second->getRegionSize();
2077 if (!size.has_value())
2078 return std::nullopt;
2079 totalSizeInBytes += *size;
2081 return totalSizeInBytes;
2086 auto *forInst = forOp.getOperation();
2097 return !reductions.empty();
2103 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
2105 if (
auto innerFor = dyn_cast<AffineForOp>(op))
2107 sequentialLoops->insert(innerFor.getInductionVar());
2119 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
2120 return simplifiedSet;
2126 llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
2127 return val.has_value() ? *val :
Value();
2146 for (
unsigned i = syms.size(); i < newSyms.size(); ++i)
2148 return constraints.
addBound(type, pos, alignedMap);
2155 newResults.push_back(r + val);
2199 bool isMin = isa<AffineMinOp>(op);
2200 assert((isMin || isa<AffineMaxOp>(op)) &&
"expect AffineMin/MaxOp");
2204 isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
2211 unsigned resultDimStart = constraints.
appendDimVar(numResults);
2215 auto boundType = isMin ? BoundType::UB : BoundType::LB;
2226 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
2237 if (failed(constraints.
addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))
2255 for (
unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
2263 map.
getSubMap({i - resultDimStart}), operands)))
2271 ineq[dimOpBound] = isMin ? 1 : -1;
2272 ineq[i] = isMin ? -1 : 1;
2306 if (aScope != bScope)
2311 auto getBlockAncestry = [&](
Operation *op,
2315 ancestry.push_back(curOp->
getBlock());
2320 assert(curOp &&
"can't reach root op without passing through affine scope");
2321 std::reverse(ancestry.begin(), ancestry.end());
2325 getBlockAncestry(a, aAncestors);
2326 getBlockAncestry(b, bAncestors);
2327 assert(!aAncestors.empty() && !bAncestors.empty() &&
2328 "at least one Block ancestor expected");
2330 Block *innermostCommonBlock =
nullptr;
2331 for (
unsigned a = 0, b = 0, e = aAncestors.size(), f = bAncestors.size();
2332 a < e && b < f; ++a, ++b) {
2333 if (aAncestors[a] != bAncestors[b])
2335 innermostCommonBlock = aAncestors[a];
2337 return innermostCommonBlock;
static std::optional< uint64_t > getConstDifference(AffineMap lbMap, AffineMap ubMap)
static void findInstPosition(Operation *op, Block *limitBlock, SmallVectorImpl< unsigned > *positions)
static Node * addNodeToMDG(Operation *nodeOp, MemRefDependenceGraph &mdg, DenseMap< Value, SetVector< unsigned >> &memrefAccesses)
Add op to MDG creating a new node and adding its memory accesses (affine or non-affine to memrefAcces...
const char *const kSliceFusionBarrierAttrName
static LogicalResult addMissingLoopIVBounds(SmallPtrSet< Value, 8 > &ivs, FlatAffineValueConstraints *cst)
static void getEffectedValues(Operation *op, SmallVectorImpl< Value > &values)
Returns the values that this op has a memref effect of type EffectTys on, not considering recursive e...
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)
A dimensional identifier appearing in an affine expression.
unsigned getPosition() const
Base type for affine expression.
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 all nested operations, blocks (including this block) or regions, depending on the type of callba...
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)
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...
std::optional< int64_t > getConstantBoundOnDimSize(MLIRContext *context, unsigned pos, AffineMap *lb=nullptr, AffineMap *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
Returns a non-negative constant bound on the extent (upper bound - lower bound) of the specified vari...
FlatLinearValueConstraints represents an extension of FlatLinearConstraints where each non-local vari...
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...
SmallVector< std::optional< Value > > getMaybeValues() const
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.
void addBound(presburger::BoundType type, Value val, int64_t value)
Adds a constant bound for the variable associated with the given Value.
unsigned appendDimVar(ValueRange vals)
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...
A trait of region holding operations that defines a new scope for polyhedral optimization purposes.
This trait indicates that the memory effects of an operation includes the effects of operations neste...
Operation is the basic unit of execution within MLIR.
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
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.
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.
user_range getUsers()
Returns a range of all users.
Region * getParentRegion()
Returns the region to which the instruction belongs.
result_range getResults()
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Instances of the Type class are uniqued, have an immutable identifier and an optional mutable compone...
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
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 removeTrivialRedundancy()
Removes duplicate constraints, trivially true constraints, and constraints that can be detected as re...
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.
void addInequality(ArrayRef< DynamicAPInt > inEq)
Adds an inequality (>= 0) from the coefficients specified in inEq.
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 while stoppin...
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 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.
Region * getAffineAnalysisScope(Operation *op)
Returns the closest region enclosing op that is held by a non-affine operation; nullptr if there is n...
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...
void getComputationSliceState(Operation *depSourceOp, Operation *depSinkOp, const 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 ...
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 ...
mlir::Block * findInnermostCommonBlockInScope(mlir::Operation *a, mlir::Operation *b)
Find the innermost common Block of a and b in the affine scope that a and b are part of.
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)
llvm::TypeSize divideCeil(llvm::TypeSize numerator, uint64_t denominator)
Divides the known min value of the numerator by the denominator and rounds the result up to the next ...
BoundType
The type of bound: equal, lower bound or upper bound.
Include the generated interface declarations.
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 isMemoryEffectFree(Operation *op)
Returns true if the given operation is free of memory effects.
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 ...
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
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
SmallVector< Operation *, 4 > memrefFrees
SmallVector< Operation *, 4 > loadOpInsts
SmallVector< Operation *, 4 > memrefStores
void collect(Operation *opToWalk)
SmallVector< Operation *, 4 > memrefLoads
SmallVector< Operation *, 4 > storeOpInsts
Encapsulates a memref load or store access information.
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 hasFree(Value memref) const
SmallVector< Operation *, 4 > memrefLoads
SmallVector< Operation *, 4 > memrefStores
unsigned getStoreOpCount(Value memref) const
unsigned hasStore(Value memref) const
Returns true if there exists an operation with a write memory effect to memref in this node.
SmallVector< Operation *, 4 > memrefFrees
unsigned addNode(Operation *op)
bool writesToLiveInOrEscapingMemrefs(unsigned id) const
void removeEdge(unsigned srcId, unsigned dstId, Value value)
void addEdge(unsigned srcId, unsigned dstId, Value value)
DenseMap< unsigned, Node > nodes
void gatherDefiningNodes(unsigned id, DenseSet< unsigned > &definingNodes) const
Return all nodes which define SSA values used in node 'id'.
bool hasDependencePath(unsigned srcId, unsigned dstId) const
void clearNodeLoadAndStores(unsigned id)
const Node * getForOpNode(AffineForOp forOp) const
Operation * getFusedLoopNestInsertionPoint(unsigned srcId, unsigned dstId) const
void updateEdges(unsigned srcId, unsigned dstId, const DenseSet< Value > &privateMemRefs, bool removeSrcId)
void forEachMemRefInputEdge(unsigned id, const std::function< void(Edge)> &callback)
unsigned getOutEdgeCount(unsigned id, Value memref=nullptr) const
const Node * getNode(unsigned id) const
void removeNode(unsigned id)
void forEachMemRefOutputEdge(unsigned id, const std::function< void(Edge)> &callback)
void forEachMemRefEdge(ArrayRef< Edge > edges, const std::function< void(Edge)> &callback)
void addToNode(unsigned id, ArrayRef< Operation * > loads, ArrayRef< Operation * > stores, ArrayRef< Operation * > memrefLoads, ArrayRef< Operation * > memrefStores, ArrayRef< Operation * > memrefFrees)
unsigned getIncomingMemRefAccesses(unsigned id, Value memref) const
bool hasEdge(unsigned srcId, unsigned dstId, Value value=nullptr) const
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...
std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, SmallVectorImpl< AffineMap > *lbs=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
FlatAffineValueConstraints * getConstraints()
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true, bool dropLocalVars=true, bool dropOuterIVs=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
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.
Enumerates different result statuses of slice computation by computeSliceUnion
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.