23 #include "llvm/ADT/SetVector.h"
24 #include "llvm/Support/Debug.h"
25 #include "llvm/Support/DebugLog.h"
26 #include "llvm/Support/raw_ostream.h"
29 #define DEBUG_TYPE "analysis-utils"
32 using namespace affine;
33 using namespace presburger;
35 using llvm::SmallDenseMap;
44 if (
auto forOp = dyn_cast<AffineForOp>(op)) {
45 forOps.push_back(forOp);
46 }
else if (isa<AffineReadOpInterface>(op)) {
47 loadOpInsts.push_back(op);
48 }
else if (isa<AffineWriteOpInterface>(op)) {
49 storeOpInsts.push_back(op);
51 auto memInterface = dyn_cast<MemoryEffectOpInterface>(op);
58 if (!isa<MemRefType>(v.getType()))
61 memrefLoads.push_back(op);
62 memrefStores.push_back(op);
66 if (hasEffect<MemoryEffects::Read>(op))
67 memrefLoads.push_back(op);
68 if (hasEffect<MemoryEffects::Write>(op))
69 memrefStores.push_back(op);
70 if (hasEffect<MemoryEffects::Free>(op))
71 memrefFrees.push_back(op);
77 unsigned Node::getLoadOpCount(
Value memref)
const {
78 unsigned loadOpCount = 0;
81 if (
auto affineLoad = dyn_cast<AffineReadOpInterface>(loadOp)) {
82 if (memref == affineLoad.getMemRef())
84 }
else if (hasEffect<MemoryEffects::Read>(loadOp, memref)) {
92 unsigned Node::getStoreOpCount(
Value memref)
const {
93 unsigned storeOpCount = 0;
94 for (
auto *storeOp : llvm::concat<Operation *const>(stores, memrefStores)) {
96 if (
auto affineStore = dyn_cast<AffineWriteOpInterface>(storeOp)) {
97 if (memref == affineStore.getMemRef())
99 }
else if (hasEffect<MemoryEffects::Write>(
const_cast<Operation *
>(storeOp),
108 unsigned Node::hasStore(
Value memref)
const {
110 llvm::concat<Operation *const>(stores, memrefStores),
112 if (
auto affineStore = dyn_cast<AffineWriteOpInterface>(storeOp)) {
113 if (memref == affineStore.getMemRef())
115 }
else if (hasEffect<MemoryEffects::Write>(storeOp, memref)) {
122 unsigned Node::hasFree(
Value memref)
const {
123 return llvm::any_of(memrefFrees, [&](
Operation *freeOp) {
124 return hasEffect<MemoryEffects::Free>(freeOp, memref);
129 void Node::getStoreOpsForMemref(
Value memref,
132 if (memref == cast<AffineWriteOpInterface>(storeOp).getMemRef())
133 storeOps->push_back(storeOp);
138 void Node::getLoadOpsForMemref(
Value memref,
141 if (memref == cast<AffineReadOpInterface>(loadOp).getMemRef())
142 loadOps->push_back(loadOp);
148 void Node::getLoadAndStoreMemrefSet(
150 llvm::SmallDenseSet<Value, 2> loadMemrefs;
152 loadMemrefs.insert(cast<AffineReadOpInterface>(loadOp).getMemRef());
155 auto memref = cast<AffineWriteOpInterface>(storeOp).getMemRef();
156 if (loadMemrefs.count(memref) > 0)
157 loadAndStoreMemrefSet->insert(memref);
163 template <
typename... EffectTys>
165 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
172 if (isa<MemRefType>(operand.getType()))
173 values.push_back(operand);
178 memOp.getEffects(effects);
179 for (
auto &effect : effects) {
180 Value effectVal = effect.getValue();
181 if (isa<EffectTys...>(effect.getEffect()) && effectVal &&
182 isa<MemRefType>(effectVal.
getType()))
183 values.push_back(effectVal);
192 auto &nodes = mdg.
nodes;
198 Node &node = nodes.insert({newNodeId,
Node(newNodeId, nodeOp)}).first->second;
200 node.
loads.push_back(op);
201 auto memref = cast<AffineReadOpInterface>(op).getMemRef();
202 memrefAccesses[memref].insert(node.id);
205 node.stores.push_back(op);
206 auto memref = cast<AffineWriteOpInterface>(op).getMemRef();
207 memrefAccesses[memref].insert(node.id);
211 getEffectedValues<MemoryEffects::Read>(op, effectedValues);
212 if (llvm::any_of(((
ValueRange)effectedValues).getTypes(),
213 [](
Type type) {
return !isa<MemRefType>(type); }))
216 for (
Value memref : effectedValues)
217 memrefAccesses[memref].insert(node.id);
218 node.memrefLoads.push_back(op);
222 getEffectedValues<MemoryEffects::Write>(op, effectedValues);
223 if (llvm::any_of((
ValueRange(effectedValues)).getTypes(),
224 [](
Type type) {
return !isa<MemRefType>(type); }))
226 for (
Value memref : effectedValues)
227 memrefAccesses[memref].insert(node.id);
228 node.memrefStores.push_back(op);
232 getEffectedValues<MemoryEffects::Free>(op, effectedValues);
233 if (llvm::any_of((
ValueRange(effectedValues)).getTypes(),
234 [](
Type type) {
return !isa<MemRefType>(type); }))
236 for (
Value memref : effectedValues)
237 memrefAccesses[memref].insert(node.id);
238 node.memrefFrees.push_back(op);
245 LDBG() <<
"--- Initializing MDG ---";
253 if (
auto forOp = dyn_cast<AffineForOp>(op)) {
257 forToNodeMap[&op] = node->
id;
258 }
else if (isa<AffineReadOpInterface>(op)) {
260 Node node(nextNodeId++, &op);
261 node.
loads.push_back(&op);
262 auto memref = cast<AffineReadOpInterface>(op).getMemRef();
263 memrefAccesses[memref].insert(node.
id);
264 nodes.insert({node.
id, node});
265 }
else if (isa<AffineWriteOpInterface>(op)) {
267 Node node(nextNodeId++, &op);
268 node.
stores.push_back(&op);
269 auto memref = cast<AffineWriteOpInterface>(op).getMemRef();
270 memrefAccesses[memref].insert(node.
id);
271 nodes.insert({node.
id, node});
272 }
else if (op.getNumResults() > 0 && !op.use_empty()) {
279 (op.getNumRegions() == 0 || isa<RegionBranchOpInterface>(op))) {
288 }
else if (op.getNumRegions() != 0 && !isa<RegionBranchOpInterface>(op)) {
292 LDBG() <<
"MDG init failed; unknown region-holding op found!";
300 LDBG() <<
"Created " << nodes.size() <<
" nodes";
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 LDBG() <<
"Can't fuse: a defining op with a user in the dst "
560 <<
"loop has dependence from the src loop";
566 for (
auto &outEdge : outEdges.lookup(srcId))
567 if (outEdge.id != dstId)
568 srcDepInsts.insert(getNode(outEdge.id)->op);
572 for (
auto &inEdge : inEdges.lookup(dstId))
573 if (inEdge.id != srcId)
574 dstDepInsts.insert(getNode(inEdge.id)->op);
576 Operation *srcNodeInst = getNode(srcId)->op;
577 Operation *dstNodeInst = getNode(dstId)->op;
590 std::optional<unsigned> firstSrcDepPos;
591 std::optional<unsigned> lastDstDepPos;
596 if (srcDepInsts.count(op) > 0 && firstSrcDepPos == std::nullopt)
597 firstSrcDepPos = pos;
598 if (dstDepInsts.count(op) > 0)
600 depInsts.push_back(op);
604 if (firstSrcDepPos.has_value()) {
605 if (lastDstDepPos.has_value()) {
606 if (*firstSrcDepPos <= *lastDstDepPos) {
612 return depInsts[*firstSrcDepPos];
628 if (inEdges.count(srcId) > 0) {
630 for (
auto &inEdge : oldInEdges) {
632 if (!privateMemRefs.contains(inEdge.value))
633 addEdge(inEdge.id, dstId, inEdge.value);
638 if (outEdges.count(srcId) > 0) {
640 for (
auto &outEdge : oldOutEdges) {
642 if (outEdge.id == dstId)
643 removeEdge(srcId, outEdge.id, outEdge.value);
644 else if (removeSrcId) {
645 addEdge(dstId, outEdge.id, outEdge.value);
646 removeEdge(srcId, outEdge.id, outEdge.value);
653 if (inEdges.count(dstId) > 0 && !privateMemRefs.empty()) {
655 for (
auto &inEdge : oldInEdges)
656 if (privateMemRefs.count(inEdge.value) > 0)
657 removeEdge(inEdge.id, dstId, inEdge.value);
667 if (inEdges.count(sibId) > 0) {
669 for (
auto &inEdge : oldInEdges) {
670 addEdge(inEdge.id, dstId, inEdge.value);
671 removeEdge(inEdge.id, sibId, inEdge.value);
678 if (outEdges.count(sibId) > 0) {
680 for (
auto &outEdge : oldOutEdges) {
681 addEdge(dstId, outEdge.id, outEdge.value);
682 removeEdge(sibId, outEdge.id, outEdge.value);
693 Node *node = getNode(
id);
694 llvm::append_range(node->
loads, loads);
695 llvm::append_range(node->
stores, stores);
696 llvm::append_range(node->
memrefLoads, memrefLoads);
698 llvm::append_range(node->
memrefFrees, memrefFrees);
702 Node *node = getNode(
id);
710 unsigned id,
const std::function<
void(
Edge)> &callback) {
711 if (inEdges.count(
id) > 0)
712 forEachMemRefEdge(inEdges.at(
id), callback);
718 unsigned id,
const std::function<
void(
Edge)> &callback) {
719 if (outEdges.count(
id) > 0)
720 forEachMemRefEdge(outEdges.at(
id), callback);
727 for (
const auto &edge : edges) {
729 if (!isa<MemRefType>(edge.value.getType()))
731 assert(nodes.count(edge.id) > 0);
738 os <<
"\nMemRefDependenceGraph\n";
740 for (
const auto &idAndNode : nodes) {
741 os <<
"Node: " << idAndNode.first <<
"\n";
742 auto it = inEdges.find(idAndNode.first);
743 if (it != inEdges.end()) {
744 for (
const auto &e : it->second)
745 os <<
" InEdge: " << e.id <<
" " << e.value <<
"\n";
747 it = outEdges.find(idAndNode.first);
748 if (it != outEdges.end()) {
749 for (
const auto &e : it->second)
750 os <<
" OutEdge: " << e.id <<
" " << e.value <<
"\n";
758 AffineForOp currAffineForOp;
762 if (
auto currAffineForOp = dyn_cast<AffineForOp>(currOp))
763 loops->push_back(currAffineForOp);
764 currOp = currOp->getParentOp();
766 std::reverse(loops->begin(), loops->end());
777 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))
778 ops->push_back(currOp);
781 std::reverse(ops->begin(), ops->end());
788 assert(!ivs.empty() &&
"Cannot have a slice without its IVs");
791 for (
Value iv : ivs) {
793 assert(loop &&
"Expected affine for");
803 assert(!lbOperands.empty());
805 unsigned numDims = ivs.size();
807 unsigned numSymbols = lbOperands[0].size();
811 values.append(lbOperands[0].begin(), lbOperands[0].end());
816 for (
unsigned i = numDims, end = values.size(); i < end; ++i) {
817 Value value = values[i];
818 assert(cst->
containsVar(value) &&
"value expected to be present");
822 cst->
addBound(BoundType::EQ, value, cOp.value());
830 LogicalResult ret = cst->
addSliceBounds(ivs, lbs, ubs, lbOperands[0]);
831 assert(succeeded(ret) &&
832 "should not fail as we never have semi-affine slice maps");
846 llvm::errs() <<
"\tIVs:\n";
848 llvm::errs() <<
"\t\t" << iv <<
"\n";
850 llvm::errs() <<
"\tLBs:\n";
852 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
853 llvm::errs() <<
"\t\tOperands:\n";
854 for (
Value lbOp : lbOperands[en.index()])
855 llvm::errs() <<
"\t\t\t" << lbOp <<
"\n";
858 llvm::errs() <<
"\tUBs:\n";
860 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
861 llvm::errs() <<
"\t\tOperands:\n";
862 for (
Value ubOp : ubOperands[en.index()])
863 llvm::errs() <<
"\t\t\t" << ubOp <<
"\n";
872 std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck()
const {
873 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
874 "Unexpected number of lbs, ubs and ivs in slice");
876 for (
unsigned i = 0, end = lbs.size(); i < end; ++i) {
888 isa<AffineConstantExpr>(lbMap.
getResult(0)))
898 AffineForOp dstLoop =
902 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
903 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
907 assert(srcLoop &&
"Expected affine for");
908 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
909 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
921 if (!isa<AffineConstantExpr>(srcLbResult) ||
922 !isa<AffineConstantExpr>(srcUbResult) ||
923 !isa<AffineConstantExpr>(dstLbResult) ||
924 !isa<AffineConstantExpr>(dstUbResult))
929 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
930 srcLoop.getStep() != dstLoop.getStep())
951 std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
952 if (isValidFastCheck && *isValidFastCheck)
958 if (
failed(getSourceAsConstraints(srcConstraints))) {
959 LDBG() <<
"Unable to compute source's domain";
965 LDBG() <<
"Cannot handle symbols in source domain";
972 LDBG() <<
"Cannot handle locals in source domain";
979 if (
failed(getAsConstraints(&sliceConstraints))) {
980 LDBG() <<
"Unable to compute slice's domain";
989 LDBG() <<
"Domain of the source of the slice:\n"
990 <<
"Source constraints:" << srcConstraints
991 <<
"\nDomain of the slice if this fusion succeeds "
992 <<
"(expressed in terms of its source's IVs):\n"
993 <<
"Slice constraints:" << sliceConstraints;
1001 LDBG() <<
"Incorrect slice";
1013 std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
1014 if (isMaximalFastCheck)
1015 return isMaximalFastCheck;
1021 for (
Value iv : ivs) {
1023 assert(loop &&
"Expected affine for");
1025 return std::nullopt;
1031 for (
Value lbOp : lbOperands[0])
1033 consumerIVs.push_back(lbOp);
1037 for (
int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
1038 consumerIVs.push_back(
Value());
1045 return std::nullopt;
1050 return std::nullopt;
1061 return cast<MemRefType>(memref.getType()).getRank();
1066 auto memRefType = cast<MemRefType>(memref.getType());
1068 unsigned rank = memRefType.getRank();
1070 shape->reserve(rank);
1072 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1080 for (
unsigned r = 0; r < rank; r++) {
1081 cstWithShapeBounds.
addBound(BoundType::LB, r, 0);
1082 int64_t dimSize = memRefType.getDimSize(r);
1083 if (ShapedType::isDynamic(dimSize))
1085 cstWithShapeBounds.
addBound(BoundType::UB, r, dimSize - 1);
1090 int64_t numElements = 1;
1091 int64_t diffConstant;
1092 for (
unsigned d = 0; d < rank; d++) {
1094 std::optional<int64_t> diff =
1096 if (diff.has_value()) {
1097 diffConstant = *diff;
1098 assert(diffConstant >= 0 &&
"dim size bound cannot be negative");
1102 auto dimSize = memRefType.getDimSize(d);
1103 if (ShapedType::isDynamic(dimSize))
1104 return std::nullopt;
1105 diffConstant = dimSize;
1110 numElements *= diffConstant;
1115 shape->push_back(diffConstant);
1122 assert(pos < cst.getNumDimVars() &&
"invalid position");
1123 auto memRefType = cast<MemRefType>(memref.getType());
1124 unsigned rank = memRefType.getRank();
1126 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1128 auto boundPairs = cst.getLowerAndUpperBound(
1129 pos, 0, rank, cst.getNumDimAndSymbolVars(),
1130 {}, memRefType.getContext());
1131 lbMap = boundPairs.first;
1132 ubMap = boundPairs.second;
1133 assert(lbMap &&
"lower bound for a region must exist");
1134 assert(ubMap &&
"upper bound for a region must exist");
1135 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1136 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1140 assert(memref == other.
memref);
1163 bool addMemRefDimBounds,
bool dropLocalVars,
1164 bool dropOuterIvs) {
1165 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
1166 "affine read/write op expected");
1172 unsigned rank = access.
getRank();
1174 LDBG() <<
"MemRefRegion::compute: " << *op <<
" depth: " << loopDepth;
1180 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
1182 ivs.resize(loopDepth);
1198 operands.resize(numOperands);
1199 for (
unsigned i = 0; i < numOperands; ++i)
1202 if (sliceState !=
nullptr) {
1203 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
1205 for (
auto extraOperand : sliceState->
lbOperands[0]) {
1206 if (!llvm::is_contained(operands, extraOperand)) {
1207 operands.push_back(extraOperand);
1219 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
1220 auto operand = operands[i];
1226 if (
failed(cst.addAffineForOpDomain(affineFor)))
1229 if (
failed(cst.addAffineParallelOpDomain(parallelOp)))
1233 Value symbol = operand;
1235 cst.addBound(BoundType::EQ, symbol, constVal.value());
1237 LDBG() <<
"unknown affine dimensional value";
1243 if (sliceState !=
nullptr) {
1245 for (
auto operand : sliceState->
lbOperands[0]) {
1246 if (
failed(cst.addInductionVarOrTerminalSymbol(operand)))
1251 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
1253 assert(succeeded(ret) &&
1254 "should not fail as we never have semi-affine slice maps");
1259 if (
failed(cst.composeMap(&accessValueMap))) {
1260 op->
emitError(
"getMemRefRegion: compose affine map failed");
1261 LDBG() <<
"Access map: " << accessValueMap.
getAffineMap();
1268 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
1274 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
1275 enclosingIVs.resize(loopDepth);
1277 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
1280 !llvm::is_contained(enclosingIVs, en.value())) {
1282 cst.projectOut(en.value());
1284 unsigned varPosition;
1285 cst.findVar(en.value(), &varPosition);
1286 auto varKind = cst.getVarKindAt(varPosition);
1287 varPosition -= cst.getNumDimVars();
1288 cst.convertToLocal(varKind, varPosition, varPosition + 1);
1296 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
1299 cst.constantFoldVarRange(cst.getNumDimVars(),
1300 cst.getNumSymbolVars());
1302 assert(cst.getNumDimVars() == rank &&
"unexpected MemRefRegion format");
1307 if (addMemRefDimBounds) {
1308 auto memRefType = cast<MemRefType>(memref.getType());
1309 for (
unsigned r = 0; r < rank; r++) {
1310 cst.addBound(BoundType::LB, r, 0);
1311 if (memRefType.isDynamicDim(r))
1313 cst.addBound(BoundType::UB, r, memRefType.getDimSize(r) - 1);
1316 cst.removeTrivialRedundancy();
1318 LDBG() <<
"Memory region: " << cst;
1322 std::optional<int64_t>
1324 auto elementType = memRefType.getElementType();
1326 unsigned sizeInBits;
1327 if (elementType.isIntOrFloat()) {
1328 sizeInBits = elementType.getIntOrFloatBitWidth();
1329 }
else if (
auto vectorType = dyn_cast<VectorType>(elementType)) {
1330 if (vectorType.getElementType().isIntOrFloat())
1332 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
1334 return std::nullopt;
1336 return std::nullopt;
1343 auto memRefType = cast<MemRefType>(memref.getType());
1345 if (!memRefType.getLayout().isIdentity()) {
1346 LDBG() <<
"Non-identity layout map not yet supported";
1351 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
1353 LDBG() <<
"Dynamic shapes not yet supported";
1354 return std::nullopt;
1358 return std::nullopt;
1359 return *eltSize * *numElements;
1366 std::optional<uint64_t>
1368 if (!memRefType.hasStaticShape())
1369 return std::nullopt;
1370 auto elementType = memRefType.getElementType();
1371 if (!elementType.isIntOrFloat() && !isa<VectorType>(elementType))
1372 return std::nullopt;
1376 return std::nullopt;
1377 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
1378 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
1383 template <
typename LoadOrStoreOp>
1386 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
1387 AffineWriteOpInterface>::value,
1388 "argument should be either a AffineReadOpInterface or a "
1389 "AffineWriteOpInterface");
1391 Operation *op = loadOrStoreOp.getOperation();
1393 if (
failed(region.compute(op, 0,
nullptr,
1397 LDBG() <<
"Memory region: " << region.getConstraints();
1399 bool outOfBounds =
false;
1400 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
1403 for (
unsigned r = 0; r < rank; r++) {
1410 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
1416 ucst.addBound(BoundType::LB, r, dimSize);
1417 outOfBounds = !ucst.isEmpty();
1419 loadOrStoreOp.emitOpError()
1420 <<
"memref out of upper bound access along dimension #" << (r + 1);
1425 llvm::fill(ineq, 0);
1427 lcst.addBound(BoundType::UB, r, -1);
1428 outOfBounds = !lcst.isEmpty();
1430 loadOrStoreOp.emitOpError()
1431 <<
"memref out of lower bound access along dimension #" << (r + 1);
1434 return failure(outOfBounds);
1438 template LogicalResult
1441 template LogicalResult
1450 while (block != limitBlock) {
1453 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
1454 positions->push_back(instPosInBlock);
1458 std::reverse(positions->begin(), positions->end());
1465 unsigned level,
Block *block) {
1467 for (
auto &op : *block) {
1468 if (i != positions[level]) {
1472 if (level == positions.size() - 1)
1474 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
1476 childAffineForOp.getBody());
1479 for (
auto &b : region)
1491 for (
unsigned i = 0, e = cst->
getNumDimVars(); i < e; ++i) {
1493 if (ivs.count(value) == 0) {
1507 unsigned numOps = ops.size();
1508 assert(numOps > 0 &&
"Expected at least one operation");
1510 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
1512 for (
unsigned i = 0; i < numOps; ++i) {
1515 std::min(loopDepthLimit,
static_cast<unsigned>(loops[i].size()));
1518 unsigned loopDepth = 0;
1519 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
1521 for (i = 1; i < numOps; ++i) {
1522 if (loops[i - 1][d] != loops[i][d])
1525 if (surroundingLoops)
1526 surroundingLoops->push_back(loops[i - 1][d]);
1539 unsigned numCommonLoops,
bool isBackwardSlice,
1545 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
1557 LDBG() <<
"Invalid loop depth";
1561 bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.
opInst) &&
1562 isa<AffineReadOpInterface>(dstAccess.
opInst);
1566 srcAccess, dstAccess, numCommonLoops + 1,
1567 &dependenceConstraints,
nullptr,
1570 LDBG() <<
"Dependence check failed";
1575 dependentOpPairs.emplace_back(a, b);
1580 isBackwardSlice, &tmpSliceState);
1585 LDBG() <<
"Unable to compute slice bound constraints";
1595 LDBG() <<
"Unable to compute slice bound constraints";
1605 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimVars(); k < l; ++k)
1606 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
1608 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimVars(); k < l; ++k)
1609 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
1627 LDBG() <<
"Unable to compute union bounding box of slice bounds";
1635 LDBG() <<
"empty slice union - unexpected";
1641 for (
auto &dep : dependentOpPairs) {
1642 ops.push_back(isBackwardSlice ? dep.second : dep.first);
1645 unsigned innermostCommonLoopDepth =
1647 if (loopDepth > innermostCommonLoopDepth) {
1648 LDBG() <<
"Exceeds max loop depth";
1668 sliceUnionCst.
getValues(numSliceLoopIVs,
1670 &sliceBoundOperands);
1673 sliceUnion->
ivs.clear();
1674 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
1680 ? surroundingLoops[loopDepth - 1].getBody()->begin()
1681 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
1685 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1686 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1690 std::optional<bool> isSliceValid = sliceUnion->
isSliceValid();
1691 if (!isSliceValid) {
1692 LDBG() <<
"Cannot determine if the slice is valid";
1704 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
1705 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
1712 auto cExpr = dyn_cast<AffineConstantExpr>(loopSpanExpr);
1714 return std::nullopt;
1715 return cExpr.getValue();
1724 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1725 unsigned numSrcLoopIVs = slice.
ivs.size();
1727 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1729 auto *op = forOp.getOperation();
1738 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1739 (*tripCountMap)[op] =
1740 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1744 if (maybeConstTripCount.has_value()) {
1745 (*tripCountMap)[op] = *maybeConstTripCount;
1752 if (!tripCount.has_value())
1754 (*tripCountMap)[op] = *tripCount;
1761 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1762 uint64_t iterCount = 1;
1763 for (
const auto &count : sliceTripCountMap) {
1764 iterCount *= count.second;
1781 unsigned numSrcLoopIVs = srcLoopIVs.size();
1786 unsigned numDstLoopIVs = dstLoopIVs.size();
1788 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1789 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1792 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1794 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1799 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1800 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1801 sliceCst.
getValues(offset, offset + numSliceLoopIVs, &sliceState->
ivs);
1809 &sliceState->
lbs, &sliceState->
ubs);
1814 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1815 if (i < offset || i >= offset + numSliceLoopIVs)
1816 sliceBoundOperands.push_back(sliceCst.
getValue(i));
1821 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1822 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1826 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1827 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1829 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1830 if (isa<AffineReadOpInterface>(depSourceOp) &&
1831 isa<AffineReadOpInterface>(depSinkOp)) {
1837 auto getSliceLoop = [&](
unsigned i) {
1838 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1840 auto isInnermostInsertion = [&]() {
1841 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1842 : loopDepth >= dstLoopIVs.size());
1844 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1845 auto srcIsUnitSlice = [&]() {
1852 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1853 Value iv = getSliceLoop(i).getInductionVar();
1854 if (sequentialLoops.count(iv) == 0 &&
1862 std::optional<bool> isMaximal = sliceState->
isMaximal();
1864 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1866 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1892 unsigned numSrcLoopIVs = srcLoopIVs.size();
1897 unsigned dstLoopIVsSize = dstLoopIVs.size();
1898 if (dstLoopDepth > dstLoopIVsSize) {
1899 dstOpInst->
emitError(
"invalid destination loop depth");
1900 return AffineForOp();
1910 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1911 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1912 auto sliceLoopNest =
1913 cast<AffineForOp>(b.
clone(*srcLoopIVs[0].getOperation()));
1922 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1923 (void)sliceSurroundingLoopsSize;
1924 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1925 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1926 (void)sliceLoopLimit;
1927 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1930 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1931 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1933 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1935 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1937 return sliceLoopNest;
1943 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(memOp)) {
1944 memref = loadOp.getMemRef();
1946 llvm::append_range(indices, loadOp.getMapOperands());
1948 assert(isa<AffineWriteOpInterface>(memOp) &&
1949 "Affine read/write op expected");
1950 auto storeOp = cast<AffineWriteOpInterface>(memOp);
1952 memref = storeOp.getMemRef();
1953 llvm::append_range(indices, storeOp.getMapOperands());
1958 return cast<MemRefType>(memref.getType()).getRank();
1962 return isa<AffineWriteOpInterface>(opInst);
1971 if (isa<AffineForOp>(currOp))
1973 if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
1974 depth += parOp.getNumDims();
1986 if (memref != rhs.
memref)
1990 getAccessMap(&thisMap);
1992 return thisMap == rhsMap;
1997 AffineForOp currAffineForOp;
2001 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
2002 ivs.push_back(currAffineForOp.getInductionVar());
2003 else if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
2004 llvm::append_range(ivs, parOp.getIVs());
2005 currOp = currOp->getParentOp();
2007 std::reverse(ivs.begin(), ivs.end());
2018 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
2019 unsigned numCommonLoops = 0;
2020 for (
unsigned i = 0; i < minNumLoops; ++i) {
2021 if (loopsA[i] != loopsB[i])
2025 return numCommonLoops;
2032 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
2036 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
2042 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
2044 region->compute(opInst,
2046 LDBG() <<
"Error obtaining memory region";
2047 opInst->
emitError(
"error obtaining memory region");
2051 auto [it, inserted] = regions.try_emplace(region->memref);
2053 it->second = std::move(region);
2054 }
else if (
failed(it->second->unionBoundingBox(*region))) {
2055 LDBG() <<
"getMemoryFootprintBytes: unable to perform a union on a "
2058 "getMemoryFootprintBytes: unable to perform a union on a memory "
2064 if (result.wasInterrupted())
2065 return std::nullopt;
2067 int64_t totalSizeInBytes = 0;
2068 for (
const auto ®ion : regions) {
2069 std::optional<int64_t> size = region.second->getRegionSize();
2070 if (!size.has_value())
2071 return std::nullopt;
2072 totalSizeInBytes += *size;
2074 return totalSizeInBytes;
2079 auto *forInst = forOp.getOperation();
2090 return !reductions.empty();
2096 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
2098 if (
auto innerFor = dyn_cast<AffineForOp>(op))
2100 sequentialLoops->insert(innerFor.getInductionVar());
2112 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
2113 return simplifiedSet;
2119 llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
2120 return val.has_value() ? *val :
Value();
2139 for (
unsigned i = syms.size(); i < newSyms.size(); ++i)
2141 return constraints.
addBound(type, pos, alignedMap);
2148 newResults.push_back(r + val);
2192 bool isMin = isa<AffineMinOp>(op);
2193 assert((isMin || isa<AffineMaxOp>(op)) &&
"expect AffineMin/MaxOp");
2197 isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
2204 unsigned resultDimStart = constraints.
appendDimVar(numResults);
2208 auto boundType = isMin ? BoundType::UB : BoundType::LB;
2219 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
2230 if (
failed(constraints.
addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))
2248 for (
unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
2256 map.
getSubMap({i - resultDimStart}), operands)))
2264 ineq[dimOpBound] = isMin ? 1 : -1;
2265 ineq[i] = isMin ? -1 : 1;
2299 if (aScope != bScope)
2304 auto getBlockAncestry = [&](
Operation *op,
2308 ancestry.push_back(curOp->
getBlock());
2313 assert(curOp &&
"can't reach root op without passing through affine scope");
2314 std::reverse(ancestry.begin(), ancestry.end());
2318 getBlockAncestry(a, aAncestors);
2319 getBlockAncestry(b, bAncestors);
2320 assert(!aAncestors.empty() && !bAncestors.empty() &&
2321 "at least one Block ancestor expected");
2323 Block *innermostCommonBlock =
nullptr;
2324 for (
unsigned a = 0, b = 0, e = aAncestors.size(), f = bAncestors.size();
2325 a < e && b < f; ++a, ++b) {
2326 if (aAncestors[a] != bAncestors[b])
2328 innermostCommonBlock = aAncestors[a];
2330 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.