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();
1073 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;
1099 for (
unsigned d = 0; d < rank; d++) {
1101 std::optional<int64_t> diff =
1103 if (diff.has_value()) {
1104 diffConstant = *diff;
1105 assert(diffConstant >= 0 &&
"dim size bound cannot be negative");
1109 auto dimSize = memRefType.getDimSize(d);
1110 if (ShapedType::isDynamic(dimSize))
1111 return std::nullopt;
1112 diffConstant = dimSize;
1117 numElements *= diffConstant;
1122 shape->push_back(diffConstant);
1129 assert(pos < cst.getNumDimVars() &&
"invalid position");
1130 auto memRefType = cast<MemRefType>(memref.getType());
1131 unsigned rank = memRefType.getRank();
1133 assert(rank == cst.getNumDimVars() &&
"inconsistent memref region");
1135 auto boundPairs = cst.getLowerAndUpperBound(
1136 pos, 0, rank, cst.getNumDimAndSymbolVars(),
1137 {}, memRefType.getContext());
1138 lbMap = boundPairs.first;
1139 ubMap = boundPairs.second;
1140 assert(lbMap &&
"lower bound for a region must exist");
1141 assert(ubMap &&
"upper bound for a region must exist");
1142 assert(lbMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1143 assert(ubMap.
getNumInputs() == cst.getNumDimAndSymbolVars() - rank);
1147 assert(memref == other.
memref);
1170 bool addMemRefDimBounds,
bool dropLocalVars,
1171 bool dropOuterIvs) {
1172 assert((isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) &&
1173 "affine read/write op expected");
1179 unsigned rank = access.
getRank();
1181 LLVM_DEBUG(llvm::dbgs() <<
"MemRefRegion::compute: " << *op
1182 <<
"\ndepth: " << loopDepth <<
"\n";);
1188 assert(loopDepth <= ivs.size() &&
"invalid 'loopDepth'");
1190 ivs.resize(loopDepth);
1206 operands.resize(numOperands);
1207 for (
unsigned i = 0; i < numOperands; ++i)
1210 if (sliceState !=
nullptr) {
1211 operands.reserve(operands.size() + sliceState->
lbOperands[0].size());
1213 for (
auto extraOperand : sliceState->
lbOperands[0]) {
1214 if (!llvm::is_contained(operands, extraOperand)) {
1215 operands.push_back(extraOperand);
1227 for (
unsigned i = 0; i < numDims + numSymbols; ++i) {
1228 auto operand = operands[i];
1234 if (failed(cst.addAffineForOpDomain(affineFor)))
1237 if (failed(cst.addAffineParallelOpDomain(parallelOp)))
1241 Value symbol = operand;
1243 cst.addBound(BoundType::EQ, symbol, constVal.value());
1245 LLVM_DEBUG(llvm::dbgs() <<
"unknown affine dimensional value");
1251 if (sliceState !=
nullptr) {
1253 for (
auto operand : sliceState->
lbOperands[0]) {
1254 if (failed(cst.addInductionVarOrTerminalSymbol(operand)))
1259 cst.addSliceBounds(sliceState->
ivs, sliceState->
lbs, sliceState->
ubs,
1261 assert(succeeded(ret) &&
1262 "should not fail as we never have semi-affine slice maps");
1267 if (failed(cst.composeMap(&accessValueMap))) {
1268 op->
emitError(
"getMemRefRegion: compose affine map failed");
1276 cst.setDimSymbolSeparation(cst.getNumDimAndSymbolVars() - rank);
1282 assert(loopDepth <= enclosingIVs.size() &&
"invalid loop depth");
1283 enclosingIVs.resize(loopDepth);
1285 cst.getValues(cst.getNumDimVars(), cst.getNumDimAndSymbolVars(), &vars);
1288 !llvm::is_contained(enclosingIVs, en.value())) {
1290 cst.projectOut(en.value());
1292 unsigned varPosition;
1293 cst.findVar(en.value(), &varPosition);
1294 auto varKind = cst.getVarKindAt(varPosition);
1295 varPosition -= cst.getNumDimVars();
1296 cst.convertToLocal(varKind, varPosition, varPosition + 1);
1304 cst.projectOut(cst.getNumDimAndSymbolVars(), cst.getNumLocalVars());
1307 cst.constantFoldVarRange(cst.getNumDimVars(),
1308 cst.getNumSymbolVars());
1310 assert(cst.getNumDimVars() == rank &&
"unexpected MemRefRegion format");
1315 if (addMemRefDimBounds) {
1316 auto memRefType = cast<MemRefType>(memref.getType());
1317 for (
unsigned r = 0; r < rank; r++) {
1318 cst.addBound(BoundType::LB, r, 0);
1319 if (memRefType.isDynamicDim(r))
1321 cst.addBound(BoundType::UB, r, memRefType.getDimSize(r) - 1);
1324 cst.removeTrivialRedundancy();
1326 LLVM_DEBUG(llvm::dbgs() <<
"Memory region:\n");
1327 LLVM_DEBUG(cst.dump());
1331 std::optional<int64_t>
1333 auto elementType = memRefType.getElementType();
1335 unsigned sizeInBits;
1336 if (elementType.isIntOrFloat()) {
1337 sizeInBits = elementType.getIntOrFloatBitWidth();
1338 }
else if (
auto vectorType = dyn_cast<VectorType>(elementType)) {
1339 if (vectorType.getElementType().isIntOrFloat())
1341 vectorType.getElementTypeBitWidth() * vectorType.getNumElements();
1343 return std::nullopt;
1345 return std::nullopt;
1352 auto memRefType = cast<MemRefType>(memref.getType());
1354 if (!memRefType.getLayout().isIdentity()) {
1355 LLVM_DEBUG(llvm::dbgs() <<
"Non-identity layout map not yet supported\n");
1360 std::optional<int64_t> numElements = getConstantBoundingSizeAndShape();
1362 LLVM_DEBUG(llvm::dbgs() <<
"Dynamic shapes not yet supported\n");
1363 return std::nullopt;
1367 return std::nullopt;
1368 return *eltSize * *numElements;
1375 std::optional<uint64_t>
1377 if (!memRefType.hasStaticShape())
1378 return std::nullopt;
1379 auto elementType = memRefType.getElementType();
1380 if (!elementType.isIntOrFloat() && !isa<VectorType>(elementType))
1381 return std::nullopt;
1385 return std::nullopt;
1386 for (
unsigned i = 0, e = memRefType.getRank(); i < e; i++) {
1387 sizeInBytes = *sizeInBytes * memRefType.getDimSize(i);
1392 template <
typename LoadOrStoreOp>
1395 static_assert(llvm::is_one_of<LoadOrStoreOp, AffineReadOpInterface,
1396 AffineWriteOpInterface>::value,
1397 "argument should be either a AffineReadOpInterface or a "
1398 "AffineWriteOpInterface");
1400 Operation *op = loadOrStoreOp.getOperation();
1402 if (failed(region.compute(op, 0,
nullptr,
1406 LLVM_DEBUG(llvm::dbgs() <<
"Memory region");
1407 LLVM_DEBUG(region.getConstraints()->dump());
1409 bool outOfBounds =
false;
1410 unsigned rank = loadOrStoreOp.getMemRefType().getRank();
1413 for (
unsigned r = 0; r < rank; r++) {
1420 int64_t dimSize = loadOrStoreOp.getMemRefType().getDimSize(r);
1426 ucst.addBound(BoundType::LB, r, dimSize);
1427 outOfBounds = !ucst.isEmpty();
1429 loadOrStoreOp.emitOpError()
1430 <<
"memref out of upper bound access along dimension #" << (r + 1);
1435 std::fill(ineq.begin(), ineq.end(), 0);
1437 lcst.addBound(BoundType::UB, r, -1);
1438 outOfBounds = !lcst.isEmpty();
1440 loadOrStoreOp.emitOpError()
1441 <<
"memref out of lower bound access along dimension #" << (r + 1);
1444 return failure(outOfBounds);
1448 template LogicalResult
1451 template LogicalResult
1460 while (block != limitBlock) {
1463 int instPosInBlock = std::distance(block->
begin(), op->getIterator());
1464 positions->push_back(instPosInBlock);
1468 std::reverse(positions->begin(), positions->end());
1475 unsigned level,
Block *block) {
1477 for (
auto &op : *block) {
1478 if (i != positions[level]) {
1482 if (level == positions.size() - 1)
1484 if (
auto childAffineForOp = dyn_cast<AffineForOp>(op))
1486 childAffineForOp.getBody());
1489 for (
auto &b : region)
1501 for (
unsigned i = 0, e = cst->
getNumDimVars(); i < e; ++i) {
1503 if (ivs.count(value) == 0) {
1517 unsigned numOps = ops.size();
1518 assert(numOps > 0 &&
"Expected at least one operation");
1520 std::vector<SmallVector<AffineForOp, 4>> loops(numOps);
1522 for (
unsigned i = 0; i < numOps; ++i) {
1525 std::min(loopDepthLimit,
static_cast<unsigned>(loops[i].size()));
1528 unsigned loopDepth = 0;
1529 for (
unsigned d = 0; d < loopDepthLimit; ++d) {
1531 for (i = 1; i < numOps; ++i) {
1532 if (loops[i - 1][d] != loops[i][d])
1535 if (surroundingLoops)
1536 surroundingLoops->push_back(loops[i - 1][d]);
1549 unsigned numCommonLoops,
bool isBackwardSlice,
1555 std::vector<std::pair<Operation *, Operation *>> dependentOpPairs;
1565 LLVM_DEBUG(llvm::dbgs() <<
"Invalid loop depth\n");
1569 bool readReadAccesses = isa<AffineReadOpInterface>(srcAccess.
opInst) &&
1570 isa<AffineReadOpInterface>(dstAccess.
opInst);
1574 srcAccess, dstAccess, numCommonLoops + 1,
1575 &dependenceConstraints,
nullptr,
1578 LLVM_DEBUG(llvm::dbgs() <<
"Dependence check failed\n");
1583 dependentOpPairs.emplace_back(i,
j);
1588 loopDepth, isBackwardSlice,
1594 LLVM_DEBUG(llvm::dbgs()
1595 <<
"Unable to compute slice bound constraints\n");
1605 LLVM_DEBUG(llvm::dbgs()
1606 <<
"Unable to compute slice bound constraints\n");
1616 for (
unsigned k = 0, l = sliceUnionCst.
getNumDimVars(); k < l; ++k)
1617 sliceUnionIVs.insert(sliceUnionCst.
getValue(k));
1619 for (
unsigned k = 0, l = tmpSliceCst.
getNumDimVars(); k < l; ++k)
1620 tmpSliceIVs.insert(tmpSliceCst.
getValue(k));
1638 LLVM_DEBUG(llvm::dbgs()
1639 <<
"Unable to compute union bounding box of slice bounds\n");
1647 LLVM_DEBUG(llvm::dbgs() <<
"empty slice union - unexpected\n");
1653 for (
auto &dep : dependentOpPairs) {
1654 ops.push_back(isBackwardSlice ? dep.second : dep.first);
1657 unsigned innermostCommonLoopDepth =
1659 if (loopDepth > innermostCommonLoopDepth) {
1660 LLVM_DEBUG(llvm::dbgs() <<
"Exceeds max loop depth\n");
1680 sliceUnionCst.
getValues(numSliceLoopIVs,
1682 &sliceBoundOperands);
1685 sliceUnion->
ivs.clear();
1686 sliceUnionCst.
getValues(0, numSliceLoopIVs, &sliceUnion->
ivs);
1692 ? surroundingLoops[loopDepth - 1].getBody()->begin()
1693 : std::prev(surroundingLoops[loopDepth - 1].getBody()->end());
1697 sliceUnion->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1698 sliceUnion->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1702 std::optional<bool> isSliceValid = sliceUnion->
isSliceValid();
1703 if (!isSliceValid) {
1704 LLVM_DEBUG(llvm::dbgs() <<
"Cannot determine if the slice is valid\n");
1716 assert(lbMap.
getNumResults() == 1 &&
"expected single result bound map");
1717 assert(ubMap.
getNumResults() == 1 &&
"expected single result bound map");
1724 auto cExpr = dyn_cast<AffineConstantExpr>(loopSpanExpr);
1726 return std::nullopt;
1727 return cExpr.getValue();
1736 llvm::SmallDenseMap<Operation *, uint64_t, 8> *tripCountMap) {
1737 unsigned numSrcLoopIVs = slice.
ivs.size();
1739 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1741 auto *op = forOp.getOperation();
1750 if (forOp.hasConstantLowerBound() && forOp.hasConstantUpperBound()) {
1751 (*tripCountMap)[op] =
1752 forOp.getConstantUpperBound() - forOp.getConstantLowerBound();
1756 if (maybeConstTripCount.has_value()) {
1757 (*tripCountMap)[op] = *maybeConstTripCount;
1764 if (!tripCount.has_value())
1766 (*tripCountMap)[op] = *tripCount;
1773 const llvm::SmallDenseMap<Operation *, uint64_t, 8> &sliceTripCountMap) {
1774 uint64_t iterCount = 1;
1775 for (
const auto &count : sliceTripCountMap) {
1776 iterCount *= count.second;
1793 unsigned numSrcLoopIVs = srcLoopIVs.size();
1798 unsigned numDstLoopIVs = dstLoopIVs.size();
1800 assert((!isBackwardSlice && loopDepth <= numSrcLoopIVs) ||
1801 (isBackwardSlice && loopDepth <= numDstLoopIVs));
1804 unsigned pos = isBackwardSlice ? numSrcLoopIVs + loopDepth : loopDepth;
1806 isBackwardSlice ? numDstLoopIVs - loopDepth : numSrcLoopIVs - loopDepth;
1811 unsigned offset = isBackwardSlice ? 0 : loopDepth;
1812 unsigned numSliceLoopIVs = isBackwardSlice ? numSrcLoopIVs : numDstLoopIVs;
1813 sliceCst.
getValues(offset, offset + numSliceLoopIVs, &sliceState->
ivs);
1821 &sliceState->
lbs, &sliceState->
ubs);
1826 for (
unsigned i = 0; i < numDimsAndSymbols; ++i) {
1827 if (i < offset || i >= offset + numSliceLoopIVs)
1828 sliceBoundOperands.push_back(sliceCst.
getValue(i));
1833 sliceState->
lbOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1834 sliceState->
ubOperands.resize(numSliceLoopIVs, sliceBoundOperands);
1838 isBackwardSlice ? dstLoopIVs[loopDepth - 1].getBody()->begin()
1839 : std::prev(srcLoopIVs[loopDepth - 1].getBody()->end());
1841 llvm::SmallDenseSet<Value, 8> sequentialLoops;
1842 if (isa<AffineReadOpInterface>(depSourceOp) &&
1843 isa<AffineReadOpInterface>(depSinkOp)) {
1849 auto getSliceLoop = [&](
unsigned i) {
1850 return isBackwardSlice ? srcLoopIVs[i] : dstLoopIVs[i];
1852 auto isInnermostInsertion = [&]() {
1853 return (isBackwardSlice ? loopDepth >= srcLoopIVs.size()
1854 : loopDepth >= dstLoopIVs.size());
1856 llvm::SmallDenseMap<Operation *, uint64_t, 8> sliceTripCountMap;
1857 auto srcIsUnitSlice = [&]() {
1864 for (
unsigned i = 0; i < numSliceLoopIVs; ++i) {
1865 Value iv = getSliceLoop(i).getInductionVar();
1866 if (sequentialLoops.count(iv) == 0 &&
1874 std::optional<bool> isMaximal = sliceState->
isMaximal();
1876 isInnermostInsertion() && srcIsUnitSlice() && isMaximal && *isMaximal)
1878 for (
unsigned j = i;
j < numSliceLoopIVs; ++
j) {
1904 unsigned numSrcLoopIVs = srcLoopIVs.size();
1909 unsigned dstLoopIVsSize = dstLoopIVs.size();
1910 if (dstLoopDepth > dstLoopIVsSize) {
1911 dstOpInst->
emitError(
"invalid destination loop depth");
1912 return AffineForOp();
1922 auto dstAffineForOp = dstLoopIVs[dstLoopDepth - 1];
1923 OpBuilder b(dstAffineForOp.getBody(), dstAffineForOp.getBody()->begin());
1924 auto sliceLoopNest =
1925 cast<AffineForOp>(b.
clone(*srcLoopIVs[0].getOperation()));
1934 unsigned sliceSurroundingLoopsSize = sliceSurroundingLoops.size();
1935 (void)sliceSurroundingLoopsSize;
1936 assert(dstLoopDepth + numSrcLoopIVs >= sliceSurroundingLoopsSize);
1937 unsigned sliceLoopLimit = dstLoopDepth + numSrcLoopIVs;
1938 (void)sliceLoopLimit;
1939 assert(sliceLoopLimit >= sliceSurroundingLoopsSize);
1942 for (
unsigned i = 0; i < numSrcLoopIVs; ++i) {
1943 auto forOp = sliceSurroundingLoops[dstLoopDepth + i];
1945 forOp.setLowerBound(sliceState->
lbOperands[i], lbMap);
1947 forOp.setUpperBound(sliceState->
ubOperands[i], ubMap);
1949 return sliceLoopNest;
1955 if (
auto loadOp = dyn_cast<AffineReadOpInterface>(loadOrStoreOpInst)) {
1956 memref = loadOp.getMemRef();
1957 opInst = loadOrStoreOpInst;
1958 llvm::append_range(indices, loadOp.getMapOperands());
1960 assert(isa<AffineWriteOpInterface>(loadOrStoreOpInst) &&
1961 "Affine read/write op expected");
1962 auto storeOp = cast<AffineWriteOpInterface>(loadOrStoreOpInst);
1963 opInst = loadOrStoreOpInst;
1964 memref = storeOp.getMemRef();
1965 llvm::append_range(indices, storeOp.getMapOperands());
1970 return cast<MemRefType>(memref.getType()).getRank();
1974 return isa<AffineWriteOpInterface>(opInst);
1983 if (isa<AffineForOp>(currOp))
1985 if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
1986 depth += parOp.getNumDims();
1998 if (memref != rhs.
memref)
2002 getAccessMap(&thisMap);
2004 return thisMap == rhsMap;
2009 AffineForOp currAffineForOp;
2013 if (AffineForOp currAffineForOp = dyn_cast<AffineForOp>(currOp))
2014 ivs.push_back(currAffineForOp.getInductionVar());
2015 else if (
auto parOp = dyn_cast<AffineParallelOp>(currOp))
2016 llvm::append_range(ivs, parOp.getIVs());
2017 currOp = currOp->getParentOp();
2019 std::reverse(ivs.begin(), ivs.end());
2030 unsigned minNumLoops =
std::min(loopsA.size(), loopsB.size());
2031 unsigned numCommonLoops = 0;
2032 for (
unsigned i = 0; i < minNumLoops; ++i) {
2033 if (loopsA[i] != loopsB[i])
2037 return numCommonLoops;
2044 SmallDenseMap<Value, std::unique_ptr<MemRefRegion>, 4> regions;
2048 if (!isa<AffineReadOpInterface, AffineWriteOpInterface>(opInst)) {
2054 auto region = std::make_unique<MemRefRegion>(opInst->
getLoc());
2056 region->compute(opInst,
2058 LLVM_DEBUG(opInst->
emitError(
"error obtaining memory region"));
2062 auto [it, inserted] = regions.try_emplace(region->memref);
2064 it->second = std::move(region);
2065 }
else if (failed(it->second->unionBoundingBox(*region))) {
2067 "getMemoryFootprintBytes: unable to perform a union on a memory "
2073 if (result.wasInterrupted())
2074 return std::nullopt;
2076 int64_t totalSizeInBytes = 0;
2077 for (
const auto ®ion : regions) {
2078 std::optional<int64_t> size = region.second->getRegionSize();
2079 if (!size.has_value())
2080 return std::nullopt;
2081 totalSizeInBytes += *size;
2083 return totalSizeInBytes;
2088 auto *forInst = forOp.getOperation();
2099 return !reductions.empty();
2105 AffineForOp forOp, llvm::SmallDenseSet<Value, 8> *sequentialLoops) {
2107 if (
auto innerFor = dyn_cast<AffineForOp>(op))
2109 sequentialLoops->insert(innerFor.getInductionVar());
2121 assert(simplifiedSet &&
"guaranteed to succeed while roundtripping");
2122 return simplifiedSet;
2128 llvm::to_vector<4>(llvm::map_range(source, [](std::optional<Value> val) {
2129 return val.has_value() ? *val :
Value();
2148 for (
unsigned i = syms.size(); i < newSyms.size(); ++i)
2150 return constraints.
addBound(type, pos, alignedMap);
2157 newResults.push_back(r + val);
2201 bool isMin = isa<AffineMinOp>(op);
2202 assert((isMin || isa<AffineMaxOp>(op)) &&
"expect AffineMin/MaxOp");
2206 isMin ? cast<AffineMinOp>(op).getMap() : cast<AffineMaxOp>(op).getMap();
2213 unsigned resultDimStart = constraints.
appendDimVar(numResults);
2217 auto boundType = isMin ? BoundType::UB : BoundType::LB;
2228 AffineMap sliceBound = isMin ? opUb[0] : opLb[0];
2239 if (failed(constraints.
addBound(BoundType::EQ, dimOpBound, alignedBoundMap)))
2257 for (
unsigned i = resultDimStart; i < resultDimStart + numResults; ++i) {
2265 map.
getSubMap({i - resultDimStart}), operands)))
2273 ineq[dimOpBound] = isMin ? 1 : -1;
2274 ineq[i] = isMin ? -1 : 1;
2308 if (aScope != bScope)
2313 auto getBlockAncestry = [&](
Operation *op,
2317 ancestry.push_back(curOp->
getBlock());
2322 assert(curOp &&
"can't reach root op without passing through affine scope");
2323 std::reverse(ancestry.begin(), ancestry.end());
2327 getBlockAncestry(a, aAncestors);
2328 getBlockAncestry(b, bAncestors);
2329 assert(!aAncestors.empty() && !bAncestors.empty() &&
2330 "at least one Block ancestor expected");
2332 Block *innermostCommonBlock =
nullptr;
2333 for (
unsigned a = 0, b = 0, e = aAncestors.size(), f = bAncestors.size();
2334 a < e && b < f; ++a, ++b) {
2335 if (aAncestors[a] != bAncestors[b])
2337 innermostCommonBlock = aAncestors[a];
2339 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.
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...
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.