25 #include "llvm/ADT/SetVector.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/raw_ostream.h"
31 #define DEBUG_TYPE "analysis-utils"
34 using namespace affine;
35 using namespace presburger;
37 using llvm::SmallDenseMap;
46 if (
auto forOp = dyn_cast<AffineForOp>(op)) {
47 forOps.push_back(forOp);
48 }
else if (isa<AffineReadOpInterface>(op)) {
49 loadOpInsts.push_back(op);
50 }
else if (isa<AffineWriteOpInterface>(op)) {
51 storeOpInsts.push_back(op);
53 auto memInterface = dyn_cast<MemoryEffectOpInterface>(op);
60 if (!isa<MemRefType>(v.getType()))
63 memrefLoads.push_back(op);
64 memrefStores.push_back(op);
68 if (hasEffect<MemoryEffects::Read>(op))
69 memrefLoads.push_back(op);
70 if (hasEffect<MemoryEffects::Write>(op))
71 memrefStores.push_back(op);
72 if (hasEffect<MemoryEffects::Free>(op))
73 memrefFrees.push_back(op);
79 unsigned Node::getLoadOpCount(
Value memref)
const {
80 unsigned loadOpCount = 0;
83 if (
auto affineLoad = dyn_cast<AffineReadOpInterface>(loadOp)) {
84 if (memref == affineLoad.getMemRef())
86 }
else if (hasEffect<MemoryEffects::Read>(loadOp, memref)) {
94 unsigned Node::getStoreOpCount(
Value memref)
const {
95 unsigned storeOpCount = 0;
96 for (
auto *storeOp : llvm::concat<Operation *const>(stores, memrefStores)) {
98 if (
auto affineStore = dyn_cast<AffineWriteOpInterface>(storeOp)) {
99 if (memref == affineStore.getMemRef())
101 }
else if (hasEffect<MemoryEffects::Write>(
const_cast<Operation *
>(storeOp),
110 unsigned Node::hasStore(
Value memref)
const {
112 llvm::concat<Operation *const>(stores, memrefStores),
114 if (
auto affineStore = dyn_cast<AffineWriteOpInterface>(storeOp)) {
115 if (memref == affineStore.getMemRef())
117 }
else if (hasEffect<MemoryEffects::Write>(storeOp, memref)) {
124 unsigned Node::hasFree(
Value memref)
const {
125 return llvm::any_of(memrefFrees, [&](
Operation *freeOp) {
126 return hasEffect<MemoryEffects::Free>(freeOp, memref);
131 void Node::getStoreOpsForMemref(
Value memref,
134 if (memref == cast<AffineWriteOpInterface>(storeOp).getMemRef())
135 storeOps->push_back(storeOp);
140 void Node::getLoadOpsForMemref(
Value memref,
143 if (memref == cast<AffineReadOpInterface>(loadOp).getMemRef())
144 loadOps->push_back(loadOp);
150 void Node::getLoadAndStoreMemrefSet(
152 llvm::SmallDenseSet<Value, 2> loadMemrefs;
154 loadMemrefs.insert(cast<AffineReadOpInterface>(loadOp).getMemRef());
157 auto memref = cast<AffineWriteOpInterface>(storeOp).getMemRef();
158 if (loadMemrefs.count(memref) > 0)
159 loadAndStoreMemrefSet->insert(memref);
165 template <
typename... EffectTys>
167 auto memOp = dyn_cast<MemoryEffectOpInterface>(op);
174 if (isa<MemRefType>(operand.getType()))
175 values.push_back(operand);
180 memOp.getEffects(effects);
181 for (
auto &effect : effects) {
182 Value effectVal = effect.getValue();
183 if (isa<EffectTys...>(effect.getEffect()) && effectVal &&
184 isa<MemRefType>(effectVal.
getType()))
185 values.push_back(effectVal);
194 auto &nodes = mdg.
nodes;
200 Node &node = nodes.insert({newNodeId,
Node(newNodeId, nodeOp)}).first->second;
202 node.
loads.push_back(op);
203 auto memref = cast<AffineReadOpInterface>(op).getMemRef();
204 memrefAccesses[memref].insert(node.id);
207 node.stores.push_back(op);
208 auto memref = cast<AffineWriteOpInterface>(op).getMemRef();
209 memrefAccesses[memref].insert(node.id);
213 getEffectedValues<MemoryEffects::Read>(op, effectedValues);
214 if (llvm::any_of(((
ValueRange)effectedValues).getTypes(),
215 [](
Type type) {
return !isa<MemRefType>(type); }))
218 for (
Value memref : effectedValues)
219 memrefAccesses[memref].insert(node.id);
220 node.memrefLoads.push_back(op);
224 getEffectedValues<MemoryEffects::Write>(op, effectedValues);
225 if (llvm::any_of((
ValueRange(effectedValues)).getTypes(),
226 [](
Type type) {
return !isa<MemRefType>(type); }))
228 for (
Value memref : effectedValues)
229 memrefAccesses[memref].insert(node.id);
230 node.memrefStores.push_back(op);
234 getEffectedValues<MemoryEffects::Free>(op, effectedValues);
235 if (llvm::any_of((
ValueRange(effectedValues)).getTypes(),
236 [](
Type type) {
return !isa<MemRefType>(type); }))
238 for (
Value memref : effectedValues)
239 memrefAccesses[memref].insert(node.id);
240 node.memrefFrees.push_back(op);
247 LLVM_DEBUG(llvm::dbgs() <<
"--- Initializing MDG ---\n");
255 if (
auto forOp = dyn_cast<AffineForOp>(op)) {
259 forToNodeMap[&op] = node->
id;
260 }
else if (isa<AffineReadOpInterface>(op)) {
262 Node node(nextNodeId++, &op);
263 node.
loads.push_back(&op);
264 auto memref = cast<AffineReadOpInterface>(op).getMemRef();
265 memrefAccesses[memref].insert(node.
id);
266 nodes.insert({node.
id, node});
267 }
else if (isa<AffineWriteOpInterface>(op)) {
269 Node node(nextNodeId++, &op);
270 node.
stores.push_back(&op);
271 auto memref = cast<AffineWriteOpInterface>(op).getMemRef();
272 memrefAccesses[memref].insert(node.
id);
273 nodes.insert({node.
id, node});
274 }
else if (op.getNumResults() > 0 && !op.use_empty()) {
281 (op.getNumRegions() == 0 || isa<RegionBranchOpInterface>(op))) {
290 }
else if (op.getNumRegions() != 0 && !isa<RegionBranchOpInterface>(op)) {
294 LLVM_DEBUG(llvm::dbgs()
295 <<
"MDG init failed; unknown region-holding op found!\n");
303 LLVM_DEBUG(llvm::dbgs() <<
"Created " << nodes.size() <<
" nodes\n");
307 for (
auto &idAndNode : nodes) {
308 const Node &node = idAndNode.second;
316 if (block.getParent()->findAncestorOpInRegion(*user)->getBlock() !=
323 auto *it = llvm::find_if(loops, [&](AffineForOp loop) {
324 return loop->getBlock() == █
326 if (it == loops.end())
328 assert(forToNodeMap.count(*it) > 0 &&
"missing mapping");
329 unsigned userLoopNestId = forToNodeMap[*it];
330 addEdge(node.
id, userLoopNestId, value);
336 for (
auto &memrefAndList : memrefAccesses) {
337 unsigned n = memrefAndList.second.size();
338 Value srcMemRef = memrefAndList.first;
340 for (
unsigned i = 0; i < n; ++i) {
341 unsigned srcId = memrefAndList.second[i];
342 Node *srcNode = getNode(srcId);
343 bool srcHasStoreOrFree =
345 for (
unsigned j = i + 1;
j < n; ++
j) {
346 unsigned dstId = memrefAndList.second[
j];
347 Node *dstNode = getNode(dstId);
348 bool dstHasStoreOrFree =
350 if (srcHasStoreOrFree || dstHasStoreOrFree)
351 addEdge(srcId, dstId, srcMemRef);
360 auto it = nodes.find(
id);
361 assert(it != nodes.end());
367 for (
auto &idAndNode : nodes)
368 if (idAndNode.second.op == forOp)
369 return &idAndNode.second;
375 Node node(nextNodeId++, op);
376 nodes.insert({node.
id, node});
383 if (inEdges.count(
id) > 0) {
385 for (
auto &inEdge : oldInEdges) {
386 removeEdge(inEdge.id,
id, inEdge.value);
390 if (outEdges.contains(
id)) {
392 for (
auto &outEdge : oldOutEdges) {
393 removeEdge(
id, outEdge.id, outEdge.value);
405 const Node *node = getNode(
id);
406 for (
auto *storeOpInst : node->
stores) {
407 auto memref = cast<AffineWriteOpInterface>(storeOpInst).getMemRef();
408 auto *op = memref.getDefiningOp();
414 for (
auto *user : memref.getUsers())
415 if (!isa<AffineMapAccessInterface>(*user))
426 if (!outEdges.contains(srcId) || !inEdges.contains(dstId)) {
429 bool hasOutEdge = llvm::any_of(outEdges.lookup(srcId), [=](
const Edge &edge) {
430 return edge.id == dstId && (!value || edge.value == value);
432 bool hasInEdge = llvm::any_of(inEdges.lookup(dstId), [=](
const Edge &edge) {
433 return edge.id == srcId && (!value || edge.value == value);
435 return hasOutEdge && hasInEdge;
441 if (!hasEdge(srcId, dstId, value)) {
442 outEdges[srcId].push_back({dstId, value});
443 inEdges[dstId].push_back({srcId, value});
444 if (isa<MemRefType>(value.
getType()))
445 memrefEdgeCount[value]++;
452 assert(inEdges.count(dstId) > 0);
453 assert(outEdges.count(srcId) > 0);
454 if (isa<MemRefType>(value.
getType())) {
455 assert(memrefEdgeCount.count(value) > 0);
456 memrefEdgeCount[value]--;
459 for (
auto *it = inEdges[dstId].begin(); it != inEdges[dstId].end(); ++it) {
460 if ((*it).id == srcId && (*it).value == value) {
461 inEdges[dstId].erase(it);
466 for (
auto *it = outEdges[srcId].begin(); it != outEdges[srcId].end(); ++it) {
467 if ((*it).id == dstId && (*it).value == value) {
468 outEdges[srcId].erase(it);
478 unsigned dstId)
const {
481 worklist.push_back({srcId, 0});
484 while (!worklist.empty()) {
485 auto &idAndIndex = worklist.back();
487 if (idAndIndex.first == dstId)
491 if (!outEdges.contains(idAndIndex.first) ||
492 idAndIndex.second == outEdges.lookup(idAndIndex.first).size()) {
497 const Edge edge = outEdges.lookup(idAndIndex.first)[idAndIndex.second];
504 if (!afterDst && edge.
id != idAndIndex.first)
505 worklist.push_back({edge.
id, 0});
513 Value memref)
const {
514 unsigned inEdgeCount = 0;
515 for (
const Edge &inEdge : inEdges.lookup(
id)) {
516 if (inEdge.value == memref) {
517 const Node *srcNode = getNode(inEdge.id);
529 Value memref)
const {
530 unsigned outEdgeCount = 0;
531 for (
const auto &outEdge : outEdges.lookup(
id))
532 if (!memref || outEdge.value == memref)
540 for (
const Edge &edge : inEdges.lookup(
id))
544 if (!isa<MemRefType>(edge.value.getType()))
545 definingNodes.insert(edge.id);
553 unsigned dstId)
const {
554 if (!outEdges.contains(srcId))
555 return getNode(dstId)->op;
559 gatherDefiningNodes(dstId, definingNodes);
560 if (llvm::any_of(definingNodes,
561 [&](
unsigned id) {
return hasDependencePath(srcId,
id); })) {
562 LLVM_DEBUG(llvm::dbgs()
563 <<
"Can't fuse: a defining op with a user in the dst "
564 "loop has dependence from the src loop\n");
570 for (
auto &outEdge : outEdges.lookup(srcId))
571 if (outEdge.id != dstId)
572 srcDepInsts.insert(getNode(outEdge.id)->op);
576 for (
auto &inEdge : inEdges.lookup(dstId))
577 if (inEdge.id != srcId)
578 dstDepInsts.insert(getNode(inEdge.id)->op);
580 Operation *srcNodeInst = getNode(srcId)->op;
581 Operation *dstNodeInst = getNode(dstId)->op;
594 std::optional<unsigned> firstSrcDepPos;
595 std::optional<unsigned> lastDstDepPos;
600 if (srcDepInsts.count(op) > 0 && firstSrcDepPos == std::nullopt)
601 firstSrcDepPos = pos;
602 if (dstDepInsts.count(op) > 0)
604 depInsts.push_back(op);
608 if (firstSrcDepPos.has_value()) {
609 if (lastDstDepPos.has_value()) {
610 if (*firstSrcDepPos <= *lastDstDepPos) {
616 return depInsts[*firstSrcDepPos];
632 if (inEdges.count(srcId) > 0) {
634 for (
auto &inEdge : oldInEdges) {
636 if (!privateMemRefs.contains(inEdge.value))
637 addEdge(inEdge.id, dstId, inEdge.value);
642 if (outEdges.count(srcId) > 0) {
644 for (
auto &outEdge : oldOutEdges) {
646 if (outEdge.id == dstId)
647 removeEdge(srcId, outEdge.id, outEdge.value);
648 else if (removeSrcId) {
649 addEdge(dstId, outEdge.id, outEdge.value);
650 removeEdge(srcId, outEdge.id, outEdge.value);
657 if (inEdges.count(dstId) > 0 && !privateMemRefs.empty()) {
659 for (
auto &inEdge : oldInEdges)
660 if (privateMemRefs.count(inEdge.value) > 0)
661 removeEdge(inEdge.id, dstId, inEdge.value);
671 if (inEdges.count(sibId) > 0) {
673 for (
auto &inEdge : oldInEdges) {
674 addEdge(inEdge.id, dstId, inEdge.value);
675 removeEdge(inEdge.id, sibId, inEdge.value);
682 if (outEdges.count(sibId) > 0) {
684 for (
auto &outEdge : oldOutEdges) {
685 addEdge(dstId, outEdge.id, outEdge.value);
686 removeEdge(sibId, outEdge.id, outEdge.value);
697 Node *node = getNode(
id);
698 llvm::append_range(node->
loads, loads);
699 llvm::append_range(node->
stores, stores);
700 llvm::append_range(node->
memrefLoads, memrefLoads);
702 llvm::append_range(node->
memrefFrees, memrefFrees);
706 Node *node = getNode(
id);
714 unsigned id,
const std::function<
void(
Edge)> &callback) {
715 if (inEdges.count(
id) > 0)
716 forEachMemRefEdge(inEdges[
id], callback);
722 unsigned id,
const std::function<
void(
Edge)> &callback) {
723 if (outEdges.count(
id) > 0)
724 forEachMemRefEdge(outEdges[
id], callback);
731 for (
const auto &edge : edges) {
733 if (!isa<MemRefType>(edge.value.getType()))
735 assert(nodes.count(edge.id) > 0);
737 if (!isa<AffineForOp>(getNode(edge.id)->op))
745 os <<
"\nMemRefDependenceGraph\n";
747 for (
const auto &idAndNode : nodes) {
748 os <<
"Node: " << idAndNode.first <<
"\n";
749 auto it = inEdges.find(idAndNode.first);
750 if (it != inEdges.end()) {
751 for (
const auto &e : it->second)
752 os <<
" InEdge: " << e.id <<
" " << e.value <<
"\n";
754 it = outEdges.find(idAndNode.first);
755 if (it != outEdges.end()) {
756 for (
const auto &e : it->second)
757 os <<
" OutEdge: " << e.id <<
" " << e.value <<
"\n";
765 AffineForOp currAffineForOp;
769 if (
auto currAffineForOp = dyn_cast<AffineForOp>(currOp))
770 loops->push_back(currAffineForOp);
771 currOp = currOp->getParentOp();
773 std::reverse(loops->begin(), loops->end());
784 if (isa<AffineIfOp, AffineForOp, AffineParallelOp>(currOp))
785 ops->push_back(currOp);
788 std::reverse(ops->begin(), ops->end());
795 assert(!ivs.empty() &&
"Cannot have a slice without its IVs");
798 for (
Value iv : ivs) {
800 assert(loop &&
"Expected affine for");
810 assert(!lbOperands.empty());
812 unsigned numDims = ivs.size();
814 unsigned numSymbols = lbOperands[0].size();
818 values.append(lbOperands[0].begin(), lbOperands[0].end());
823 for (
unsigned i = numDims, end = values.size(); i < end; ++i) {
824 Value value = values[i];
825 assert(cst->
containsVar(value) &&
"value expected to be present");
829 cst->
addBound(BoundType::EQ, value, cOp.value());
837 LogicalResult ret = cst->
addSliceBounds(ivs, lbs, ubs, lbOperands[0]);
838 assert(succeeded(ret) &&
839 "should not fail as we never have semi-affine slice maps");
853 llvm::errs() <<
"\tIVs:\n";
855 llvm::errs() <<
"\t\t" << iv <<
"\n";
857 llvm::errs() <<
"\tLBs:\n";
859 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
860 llvm::errs() <<
"\t\tOperands:\n";
861 for (
Value lbOp : lbOperands[en.index()])
862 llvm::errs() <<
"\t\t\t" << lbOp <<
"\n";
865 llvm::errs() <<
"\tUBs:\n";
867 llvm::errs() <<
"\t\t" << en.value() <<
"\n";
868 llvm::errs() <<
"\t\tOperands:\n";
869 for (
Value ubOp : ubOperands[en.index()])
870 llvm::errs() <<
"\t\t\t" << ubOp <<
"\n";
879 std::optional<bool> ComputationSliceState::isSliceMaximalFastCheck()
const {
880 assert(lbs.size() == ubs.size() && !lbs.empty() && !ivs.empty() &&
881 "Unexpected number of lbs, ubs and ivs in slice");
883 for (
unsigned i = 0, end = lbs.size(); i < end; ++i) {
895 isa<AffineConstantExpr>(lbMap.
getResult(0)))
905 AffineForOp dstLoop =
909 AffineMap dstLbMap = dstLoop.getLowerBoundMap();
910 AffineMap dstUbMap = dstLoop.getUpperBoundMap();
914 assert(srcLoop &&
"Expected affine for");
915 AffineMap srcLbMap = srcLoop.getLowerBoundMap();
916 AffineMap srcUbMap = srcLoop.getUpperBoundMap();
928 if (!isa<AffineConstantExpr>(srcLbResult) ||
929 !isa<AffineConstantExpr>(srcUbResult) ||
930 !isa<AffineConstantExpr>(dstLbResult) ||
931 !isa<AffineConstantExpr>(dstUbResult))
936 if (srcLbResult != dstLbResult || srcUbResult != dstUbResult ||
937 srcLoop.getStep() != dstLoop.getStep())
958 std::optional<bool> isValidFastCheck = isSliceMaximalFastCheck();
959 if (isValidFastCheck && *isValidFastCheck)
965 if (failed(getSourceAsConstraints(srcConstraints))) {
966 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute source's domain\n");
972 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle symbols in source domain\n");
979 LLVM_DEBUG(llvm::dbgs() <<
"Cannot handle locals in source domain\n");
986 if (failed(getAsConstraints(&sliceConstraints))) {
987 LLVM_DEBUG(llvm::dbgs() <<
"Unable to compute slice's domain\n");
996 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the source of the slice:\n");
997 LLVM_DEBUG(srcConstraints.
dump());
998 LLVM_DEBUG(llvm::dbgs() <<
"Domain of the slice if this fusion succeeds "
999 "(expressed in terms of its source's IVs):\n");
1000 LLVM_DEBUG(sliceConstraints.
dump());
1008 LLVM_DEBUG(llvm::dbgs() <<
"Incorrect slice\n");
1020 std::optional<bool> isMaximalFastCheck = isSliceMaximalFastCheck();
1021 if (isMaximalFastCheck)
1022 return isMaximalFastCheck;
1028 for (
Value iv : ivs) {
1030 assert(loop &&
"Expected affine for");
1032 return std::nullopt;
1038 for (
Value lbOp : lbOperands[0])
1040 consumerIVs.push_back(lbOp);
1044 for (
int i = consumerIVs.size(), end = ivs.size(); i < end; ++i)
1045 consumerIVs.push_back(
Value());
1052 return std::nullopt;
1057 return std::nullopt;
1068 return cast<MemRefType>(memref.getType()).getRank();
1074 auto memRefType = cast<MemRefType>(memref.getType());
1075 unsigned rank = memRefType.getRank();
1077 shape->reserve(rank);
1079 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1087 for (
unsigned r = 0; r < rank; r++) {
1088 cstWithShapeBounds.
addBound(BoundType::LB, r, 0);
1089 int64_t dimSize = memRefType.getDimSize(r);
1090 if (ShapedType::isDynamic(dimSize))
1092 cstWithShapeBounds.
addBound(BoundType::UB, r, dimSize - 1);
1097 int64_t numElements = 1;
1098 int64_t diffConstant;
1100 for (
unsigned d = 0; d < rank; d++) {
1102 std::optional<int64_t> diff =
1104 if (diff.has_value()) {
1105 diffConstant = *diff;
1106 assert(diffConstant >= 0 &&
"Dim size bound can't be negative");
1107 assert(lbDivisor > 0);
1111 auto dimSize = memRefType.getDimSize(d);
1112 if (dimSize == ShapedType::kDynamic)
1113 return std::nullopt;
1114 diffConstant = dimSize;
1119 numElements *= diffConstant;
1122 assert(lbDivisors &&
"both lbs and lbDivisor or none");
1123 lbDivisors->push_back(lbDivisor);
1126 shape->push_back(diffConstant);
1134 assert(pos < cst.getNumDimVars() &&
"invalid position");
1135 auto memRefType = cast<MemRefType>(memref.getType());
1136 unsigned rank = memRefType.getRank();
1138 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1140 auto boundPairs = cst.getLowerAndUpperBound(
1141 pos, 0, rank, cst.getNumDimAndSymbolVars(),
1142 {}, memRefType.getContext());
1143 lbMap = boundPairs.first;
1144 ubMap = boundPairs.second;
1145 assert(lbMap &&
"lower bound for a region must exist");
1146 assert(ubMap &&
"upper bound for a region must exist");
1147 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1148 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1152 assert(memref == other.
memref);
1175 bool addMemRefDimBounds) {
1176 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
1177 "affine read/write op expected");
1183 unsigned rank = access.
getRank();
1185 LLVM_DEBUG(llvm::dbgs() <<
"MemRefRegion::compute: " << *op
1186 <<
"\ndepth: " << loopDepth <<
"\n";);
1192 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
1194 ivs.resize(loopDepth);
1210 operands.resize(numOperands);
1211 for (
unsigned i = 0; i < numOperands; ++i)
1214 if (sliceState !=
nullptr) {
1215 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
1217 for (
auto extraOperand : sliceState->
lbOperands[0]) {
1218 if (!llvm::is_contained(operands, extraOperand)) {
1219 operands.push_back(extraOperand);
1231 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
1232 auto operand = operands[i];
1238 if (failed(cst.addAffineForOpDomain(affineFor)))
1241 if (failed(cst.addAffineParallelOpDomain(parallelOp)))
1245 Value symbol = operand;
1247 cst.addBound(BoundType::EQ, symbol, constVal.value());
1249 LLVM_DEBUG(llvm::dbgs() <<
"unknown affine dimensional value");
1255 if (sliceState !=
nullptr) {
1257 for (
auto operand : sliceState->
lbOperands[0]) {
1258 cst.addInductionVarOrTerminalSymbol(operand);
1262 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
1264 assert(succeeded(ret) &&
1265 "should not fail as we never have semi-affine slice maps");
1270 if (failed(cst.composeMap(&accessValueMap))) {
1271 op->
emitError(
"getMemRefRegion: compose affine map failed");
1279 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
1285 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
1286 enclosingIVs.resize(loopDepth);
1288 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
1289 for (
Value var : vars) {
1291 cst.projectOut(var);
1297 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
1300 cst.constantFoldVarRange(cst.getNumDimVars(),
1301 cst.getNumSymbolVars());
1303 assert(cst.getNumDimVars() == rank &&
"unexpected MemRefRegion format");
1308 if (addMemRefDimBounds) {
1309 auto memRefType = cast<MemRefType>(memref.getType());
1310 for (
unsigned r = 0; r < rank; r++) {
1311 cst.addBound(BoundType::LB, r, 0);
1312 if (memRefType.isDynamicDim(r))
1314 cst.addBound(BoundType::UB, r, memRefType.getDimSize(r) - 1);
1317 cst.removeTrivialRedundancy();
1319 LLVM_DEBUG(llvm::dbgs() <<
"Memory region:\n");
1320 LLVM_DEBUG(cst.dump());
1324 std::optional<int64_t>
1326 auto elementType = memRefType.getElementType();
1328 unsigned sizeInBits;
1329 if (elementType.isIntOrFloat()) {
1330 sizeInBits = elementType.getIntOrFloatBitWidth();
1331 }
else if (
auto vectorType = dyn_cast<VectorType>(elementType)) {
1332 if (vectorType.getElementType().isIntOrFloat())
1334 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
1336 return std::nullopt;
1338 return std::nullopt;
1345 auto memRefType = cast<MemRefType>(memref.getType());
1347 if (!memRefType.getLayout().isIdentity()) {
1348 LLVM_DEBUG(llvm::dbgs() <<
"Non-identity layout map not yet supported\n");
1359 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
1361 LLVM_DEBUG(llvm::dbgs() <<
"Dynamic shapes not yet supported\n");
1362 return std::nullopt;
1366 return std::nullopt;
1367 return *eltSize * *numElements;
1374 std::optional<uint64_t>
1376 if (!memRefType.hasStaticShape())
1377 return std::nullopt;
1378 auto elementType = memRefType.getElementType();
1379 if (!elementType.isIntOrFloat() && !isa<VectorType>(elementType))
1380 return std::nullopt;
1384 return std::nullopt;
1385 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
1386 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
1391 template <
typename LoadOrStoreOp>
1394 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
1395 AffineWriteOpInterface>::value,
1396 "argument should be either a AffineReadOpInterface or a "
1397 "AffineWriteOpInterface");
1399 Operation *op = loadOrStoreOp.getOperation();
1401 if (failed(region.compute(op, 0,
nullptr,
1405 LLVM_DEBUG(llvm::dbgs() <<
"Memory region");
1406 LLVM_DEBUG(region.getConstraints()->dump());
1408 bool outOfBounds =
false;
1409 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
1412 for (
unsigned r = 0; r < rank; r++) {
1419 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
1425 ucst.addBound(BoundType::LB, r, dimSize);
1426 outOfBounds = !ucst.isEmpty();
1428 loadOrStoreOp.emitOpError()
1429 <<
"memref out of upper bound access along dimension #" << (r + 1);
1434 std::fill(ineq.begin(), ineq.end(), 0);
1436 lcst.addBound(BoundType::UB, r, -1);
1437 outOfBounds = !lcst.isEmpty();
1439 loadOrStoreOp.emitOpError()
1440 <<
"memref out of lower bound access along dimension #" << (r + 1);
1443 return failure(outOfBounds);
1447 template LogicalResult
1450 template LogicalResult
1459 while (block != limitBlock) {
1462 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
1463 positions->push_back(instPosInBlock);
1467 std::reverse(positions->begin(), positions->end());
1474 unsigned level,
Block *block) {
1476 for (
auto &op : *block) {
1477 if (i != positions[level]) {
1481 if (level == positions.size() - 1)
1483 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
1485 childAffineForOp.getBody());
1488 for (
auto &b : region)
1500 for (
unsigned i = 0, e = cst->
getNumDimVars(); i < e; ++i) {
1502 if (ivs.count(value) == 0) {
1516 unsigned numOps = ops.size();
1517 assert(numOps > 0 &&
"Expected at least one operation");
1519 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
1521 for (
unsigned i = 0; i < numOps; ++i) {
1524 std::min(loopDepthLimit,
static_cast<unsigned>(loops[i].size()));
1527 unsigned loopDepth = 0;
1528 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
1530 for (i = 1; i < numOps; ++i) {
1531 if (loops[i - 1][d] != loops[i][d])
1534 if (surroundingLoops)
1535 surroundingLoops->push_back(loops[i - 1][d]);
1548 unsigned numCommonLoops,
bool isBackwardSlice,
1554 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(i,
j);
1587 loopDepth, isBackwardSlice,
1593 LLVM_DEBUG(llvm::dbgs()
1594 <<
"Unable to compute slice bound constraints\n");
1604 LLVM_DEBUG(llvm::dbgs()
1605 <<
"Unable to compute slice bound constraints\n");
1615 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimVars(); k < l; ++k)
1616 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
1618 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimVars(); k < l; ++k)
1619 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
1637 LLVM_DEBUG(llvm::dbgs()
1638 <<
"Unable to compute union bounding box of slice bounds\n");
1646 LLVM_DEBUG(llvm::dbgs() <<
"empty slice union - unexpected\n");
1652 for (
auto &dep : dependentOpPairs) {
1653 ops.push_back(isBackwardSlice ? dep.second : dep.first);
1656 unsigned innermostCommonLoopDepth =
1658 if (loopDepth > innermostCommonLoopDepth) {
1659 LLVM_DEBUG(llvm::dbgs() <<
"Exceeds max loop depth\n");
1679 sliceUnionCst.
getValues(numSliceLoopIVs,
1681 &sliceBoundOperands);
1684 sliceUnion->
ivs.clear();
1685 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
1691 ? surroundingLoops[loopDepth - 1].getBody()->begin()
1692 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
1696 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1697 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1701 std::optional<bool> isSliceValid = sliceUnion->
isSliceValid();
1702 if (!isSliceValid) {
1703 LLVM_DEBUG(llvm::dbgs() <<
"Cannot determine if the slice is valid\n");
1715 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
1716 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
1723 auto cExpr = dyn_cast<AffineConstantExpr>(loopSpanExpr);
1725 return std::nullopt;
1726 return cExpr.getValue();
1735 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1736 unsigned numSrcLoopIVs = slice.
ivs.size();
1738 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1740 auto *op = forOp.getOperation();
1749 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1750 (*tripCountMap)[op] =
1751 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1755 if (maybeConstTripCount.has_value()) {
1756 (*tripCountMap)[op] = *maybeConstTripCount;
1763 if (!tripCount.has_value())
1765 (*tripCountMap)[op] = *tripCount;
1772 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1773 uint64_t iterCount = 1;
1774 for (
const auto &count : sliceTripCountMap) {
1775 iterCount *= count.second;
1792 unsigned numSrcLoopIVs = srcLoopIVs.size();
1797 unsigned numDstLoopIVs = dstLoopIVs.size();
1799 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1800 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1803 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1805 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1810 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1811 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1812 sliceCst.
getValues(offset, offset + numSliceLoopIVs, &sliceState->
ivs);
1820 &sliceState->
lbs, &sliceState->
ubs);
1825 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1826 if (i < offset || i >= offset + numSliceLoopIVs)
1827 sliceBoundOperands.push_back(sliceCst.
getValue(i));
1832 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1833 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1837 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1838 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1840 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1841 if (isa<AffineReadOpInterface>(depSourceOp) &&
1842 isa<AffineReadOpInterface>(depSinkOp)) {
1848 auto getSliceLoop = [&](
unsigned i) {
1849 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1851 auto isInnermostInsertion = [&]() {
1852 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1853 : loopDepth >= dstLoopIVs.size());
1855 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1856 auto srcIsUnitSlice = [&]() {
1863 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1864 Value iv = getSliceLoop(i).getInductionVar();
1865 if (sequentialLoops.count(iv) == 0 &&
1873 std::optional<bool> isMaximal = sliceState->
isMaximal();
1875 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1877 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1903 unsigned numSrcLoopIVs = srcLoopIVs.size();
1908 unsigned dstLoopIVsSize = dstLoopIVs.size();
1909 if (dstLoopDepth > dstLoopIVsSize) {
1910 dstOpInst->
emitError(
"invalid destination loop depth");
1911 return AffineForOp();
1921 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1922 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1923 auto sliceLoopNest =
1924 cast<AffineForOp>(b.
clone(*srcLoopIVs[0].getOperation()));
1933 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1934 (void)sliceSurroundingLoopsSize;
1935 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1936 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1937 (void)sliceLoopLimit;
1938 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1941 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1942 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1944 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1946 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1948 return sliceLoopNest;
1954 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1955 memref = loadOp.getMemRef();
1956 opInst = loadOrStoreOpInst;
1957 llvm::append_range(indices, loadOp.getMapOperands());
1959 assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1960 "Affine read/write op expected");
1961 auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1962 opInst = loadOrStoreOpInst;
1963 memref = storeOp.getMemRef();
1964 llvm::append_range(indices, storeOp.getMapOperands());
1969 return cast<MemRefType>(memref.getType()).getRank();
1973 return isa<AffineWriteOpInterface>(opInst);
1982 if (isa<AffineForOp>(currOp))
1995 if (memref != rhs.
memref)
1999 getAccessMap(&thisMap);
2001 return thisMap == rhsMap;
2006 AffineForOp currAffineForOp;
2010 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
2011 ivs.push_back(currAffineForOp.getInductionVar());
2012 else if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
2013 llvm::append_range(ivs, parOp.getIVs());
2014 currOp = currOp->getParentOp();
2016 std::reverse(ivs.begin(), ivs.end());
2027 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
2028 unsigned numCommonLoops = 0;
2029 for (
unsigned i = 0; i < minNumLoops; ++i) {
2030 if (loopsA[i] != loopsB[i])
2034 return numCommonLoops;
2041 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
2045 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
2051 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
2053 region->compute(opInst,
2055 LLVM_DEBUG(opInst->
emitError(
"error obtaining memory region"));
2059 auto [it, inserted] = regions.try_emplace(region->memref);
2061 it->second = std::move(region);
2062 }
else if (failed(it->second->unionBoundingBox(*region))) {
2064 "getMemoryFootprintBytes: unable to perform a union on a memory "
2070 if (result.wasInterrupted())
2071 return std::nullopt;
2073 int64_t totalSizeInBytes = 0;
2074 for (
const auto ®ion : regions) {
2075 std::optional<int64_t> size = region.second->getRegionSize();
2076 if (!size.has_value())
2077 return std::nullopt;
2078 totalSizeInBytes += *size;
2080 return totalSizeInBytes;
2085 auto *forInst = forOp.getOperation();
2096 return !reductions.empty();
2102 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
2104 if (
auto innerFor = dyn_cast<AffineForOp>(op))
2106 sequentialLoops->insert(innerFor.getInductionVar());
2118 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
2119 return simplifiedSet;
2125 llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
2126 return val.has_value() ? *val :
Value();
2145 for (
unsigned i = syms.size(); i < newSyms.size(); ++i)
2147 return constraints.
addBound(type, pos, alignedMap);
2154 newResults.push_back(r + val);
2198 bool isMin = isa<AffineMinOp>(op);
2199 assert((isMin || isa<AffineMaxOp>(op)) &&
"expect AffineMin/MaxOp");
2203 isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
2210 unsigned resultDimStart = constraints.
appendDimVar(numResults);
2214 auto boundType = isMin ? BoundType::UB : BoundType::LB;
2225 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
2236 if (failed(constraints.
addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))
2254 for (
unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
2262 map.
getSubMap({i - resultDimStart}), operands)))
2270 ineq[dimOpBound] = isMin ? 1 : -1;
2271 ineq[i] = isMin ? -1 : 1;
2305 if (aScope != bScope)
2310 auto getBlockAncestry = [&](
Operation *op,
2314 ancestry.push_back(curOp->
getBlock());
2319 assert(curOp &&
"can't reach root op without passing through affine scope");
2320 std::reverse(ancestry.begin(), ancestry.end());
2324 getBlockAncestry(a, aAncestors);
2325 getBlockAncestry(b, bAncestors);
2326 assert(!aAncestors.empty() && !bAncestors.empty() &&
2327 "at least one Block ancestor expected");
2329 Block *innermostCommonBlock =
nullptr;
2330 for (
unsigned a = 0, b = 0, e = aAncestors.size(), f = bAncestors.size();
2331 a < e && b < f; ++a, ++b) {
2332 if (aAncestors[a] != bAncestors[b])
2334 innermostCommonBlock = aAncestors[a];
2336 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...
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.
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...
std::optional< int64_t > getConstantBoundOnDimSize64(unsigned pos, SmallVectorImpl< int64_t > *lb=nullptr, int64_t *boundFloorDivisor=nullptr, SmallVectorImpl< int64_t > *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
The same, but casts to int64_t.
unsigned getNumSymbolVars() const
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned getNumVars() const
unsigned getNumLocalVars() const
unsigned getNumDimAndSymbolVars() const
bool isEmpty() const
Checks for emptiness by performing variable elimination on all variables, running the GCD test on eac...
unsigned getNumCols() const
Returns the number of columns in the constraint system.
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.
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.
Region * getAffineScope(Operation *op)
Returns the closest region enclosing op that is held by an operation with trait AffineScope; nullptr ...
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 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.
MemRefAccess(Operation *opInst)
Constructs a MemRefAccess from a load or store operation.
void getAccessMap(AffineValueMap *accessMap) const
Populates 'accessMap' with composition of AffineApplyOps reachable from 'indices'.
bool operator==(const MemRefAccess &rhs) const
Equal if both affine accesses can be proved to be equivalent at compile time (considering the memrefs...
SmallVector< Operation *, 4 > loads
SmallVector< Operation *, 4 > stores
unsigned 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...
FlatAffineValueConstraints * getConstraints()
unsigned getRank() const
Returns the rank of the memref that this region corresponds to.
std::optional< int64_t > getConstantBoundingSizeAndShape(SmallVectorImpl< int64_t > *shape=nullptr, std::vector< SmallVector< int64_t, 4 >> *lbs=nullptr, SmallVectorImpl< int64_t > *lbDivisors=nullptr) const
Returns a constant upper bound on the number of elements in this region if bounded by a known constan...
void getLowerAndUpperBound(unsigned pos, AffineMap &lbMap, AffineMap &ubMap) const
Gets the lower and upper bound map for the dimensional variable at pos.
std::optional< int64_t > getRegionSize()
Returns the size of this MemRefRegion in bytes.
LogicalResult unionBoundingBox(const MemRefRegion &other)
Value memref
Memref that this region corresponds to.
LogicalResult compute(Operation *op, unsigned loopDepth, const ComputationSliceState *sliceState=nullptr, bool addMemRefDimBounds=true)
Computes the memory region accessed by this memref with the region represented as constraints symboli...
Enumerates different result statuses of slice computation by computeSliceUnion
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.