32 #define DEBUG_TYPE "affine-utils"
35 using namespace affine;
36 using namespace presburger;
42 class AffineApplyExpander
49 : builder(builder), dimValues(dimValues), symbolValues(symbolValues),
52 template <
typename OpTy>
58 auto op = builder.
create<OpTy>(loc, lhs, rhs);
63 return buildBinaryExpr<arith::AddIOp>(expr);
67 return buildBinaryExpr<arith::MulIOp>(expr);
80 if (
auto rhsConst = dyn_cast<AffineConstantExpr>(expr.
getRHS())) {
81 if (rhsConst.getValue() <= 0) {
82 emitError(loc,
"modulo by non-positive value is not supported");
89 assert(lhs && rhs &&
"unexpected affine expr lowering failure");
91 Value remainder = builder.
create<arith::RemSIOp>(loc, lhs, rhs);
92 Value zeroCst = builder.
create<arith::ConstantIndexOp>(loc, 0);
93 Value isRemainderNegative = builder.
create<arith::CmpIOp>(
94 loc, arith::CmpIPredicate::slt, remainder, zeroCst);
95 Value correctedRemainder =
96 builder.
create<arith::AddIOp>(loc, remainder, rhs);
98 loc, isRemainderNegative, correctedRemainder, remainder);
120 if (
auto rhsConst = dyn_cast<AffineConstantExpr>(expr.
getRHS())) {
121 if (rhsConst.getValue() <= 0) {
122 emitError(loc,
"division by non-positive value is not supported");
128 assert(lhs && rhs &&
"unexpected affine expr lowering failure");
130 Value zeroCst = builder.
create<arith::ConstantIndexOp>(loc, 0);
131 Value noneCst = builder.
create<arith::ConstantIndexOp>(loc, -1);
133 loc, arith::CmpIPredicate::slt, lhs, zeroCst);
134 Value negatedDecremented = builder.
create<arith::SubIOp>(loc, noneCst, lhs);
136 builder.
create<arith::SelectOp>(loc, negative, negatedDecremented, lhs);
137 Value quotient = builder.
create<arith::DivSIOp>(loc, dividend, rhs);
138 Value correctedQuotient =
139 builder.
create<arith::SubIOp>(loc, noneCst, quotient);
140 Value result = builder.
create<arith::SelectOp>(loc, negative,
141 correctedQuotient, quotient);
159 if (
auto rhsConst = dyn_cast<AffineConstantExpr>(expr.
getRHS())) {
160 if (rhsConst.getValue() <= 0) {
161 emitError(loc,
"division by non-positive value is not supported");
167 assert(lhs && rhs &&
"unexpected affine expr lowering failure");
169 Value zeroCst = builder.
create<arith::ConstantIndexOp>(loc, 0);
170 Value oneCst = builder.
create<arith::ConstantIndexOp>(loc, 1);
172 loc, arith::CmpIPredicate::sle, lhs, zeroCst);
173 Value negated = builder.
create<arith::SubIOp>(loc, zeroCst, lhs);
174 Value decremented = builder.
create<arith::SubIOp>(loc, lhs, oneCst);
176 builder.
create<arith::SelectOp>(loc, nonPositive, negated, decremented);
177 Value quotient = builder.
create<arith::DivSIOp>(loc, dividend, rhs);
178 Value negatedQuotient =
179 builder.
create<arith::SubIOp>(loc, zeroCst, quotient);
180 Value incrementedQuotient =
181 builder.
create<arith::AddIOp>(loc, quotient, oneCst);
183 loc, nonPositive, negatedQuotient, incrementedQuotient);
188 auto op = builder.
create<arith::ConstantIndexOp>(loc, expr.
getValue());
194 "affine dim position out of range");
200 "symbol dim position out of range");
219 return AffineApplyExpander(builder, dimValues, symbolValues, loc).visit(expr);
224 std::optional<SmallVector<Value, 8>>
228 auto expanded = llvm::to_vector<8>(
230 [numDims, &builder, loc, operands](
AffineExpr expr) {
231 return expandAffineExpr(builder, loc, expr,
232 operands.take_front(numDims),
233 operands.drop_front(numDims));
235 if (llvm::all_of(expanded, [](
Value v) {
return v; }))
245 assert(ifOp.hasElse() &&
"else block expected");
247 Block *destBlock = ifOp->getBlock();
248 Block *srcBlock = elseBlock ? ifOp.getElseBlock() : ifOp.getThenBlock();
251 std::prev(srcBlock->
end()));
262 auto *res = ifOp.getOperation();
263 while (!isa<func::FuncOp>(res->getParentOp())) {
264 auto *parentOp = res->getParentOp();
265 if (
auto forOp = dyn_cast<AffineForOp>(parentOp)) {
266 if (llvm::is_contained(ifOperands, forOp.getInductionVar()))
268 }
else if (
auto parallelOp = dyn_cast<AffineParallelOp>(parentOp)) {
269 for (
auto iv : parallelOp.getIVs())
270 if (llvm::is_contained(ifOperands, iv))
272 }
else if (!isa<AffineIfOp>(parentOp)) {
287 if (hoistOverOp == ifOp)
297 auto hoistedIfOp = b.
create<AffineIfOp>(ifOp.getLoc(), ifOp.getIntegerSet(),
306 StringAttr idForIfOp = b.
getStringAttr(
"__mlir_if_hoisting");
311 hoistOverOpClone = b.
clone(*hoistOverOp, operandMap);
317 auto *thenBlock = hoistedIfOp.getThenBlock();
318 thenBlock->getOperations().splice(thenBlock->begin(),
323 AffineIfOp ifCloneInElse;
324 hoistOverOpClone->walk([&](AffineIfOp ifClone) {
325 if (!ifClone->getAttr(idForIfOp))
327 ifCloneInElse = ifClone;
330 assert(ifCloneInElse &&
"if op clone should exist");
333 if (!ifCloneInElse.hasElse())
334 ifCloneInElse.erase();
339 auto *elseBlock = hoistedIfOp.getElseBlock();
340 elseBlock->getOperations().splice(
341 elseBlock->begin(), hoistOverOpClone->getBlock()->getOperations(),
350 AffineParallelOp *resOp) {
352 unsigned numReductions = parallelReductions.size();
353 if (numReductions != forOp.getNumIterOperands())
358 AffineMap lowerBoundMap = forOp.getLowerBoundMap();
359 ValueRange lowerBoundOperands = forOp.getLowerBoundOperands();
360 AffineMap upperBoundMap = forOp.getUpperBoundMap();
361 ValueRange upperBoundOperands = forOp.getUpperBoundOperands();
364 auto reducedValues = llvm::to_vector<4>(llvm::map_range(
366 auto reductionKinds = llvm::to_vector<4>(llvm::map_range(
368 AffineParallelOp newPloop = outsideBuilder.
create<AffineParallelOp>(
375 Operation *yieldOp = &newPloop.getBody()->back();
380 newResults.reserve(numReductions);
381 for (
unsigned i = 0; i < numReductions; ++i) {
382 Value init = forOp.getInits()[i];
387 assert(reductionOp &&
"yielded value is expected to be produced by an op");
391 reductionOp->
setOperands({init, newPloop->getResult(i)});
392 forOp->getResult(i).replaceAllUsesWith(reductionOp->
getResult(0));
401 newPloop.getBody()->eraseArguments(numIVs, numReductions);
413 if (ifOp.getNumResults() != 0)
422 AffineIfOp::getCanonicalizationPatterns(patterns, ifOp.
getContext());
439 assert(llvm::all_of(ifOp.getOperands(),
441 return isTopLevelValue(v) || isAffineForInductionVar(v);
443 "operands not composed");
451 if (hoistedIfOp == ifOp)
468 return positivePath ?
min :
max;
469 if (
auto bin = dyn_cast<AffineBinaryOpExpr>(e)) {
476 auto c1 = dyn_cast<AffineConstantExpr>(bin.getLHS());
477 auto c2 = dyn_cast<AffineConstantExpr>(bin.getRHS());
478 if (c1 && c1.getValue() < 0)
481 if (c2 && c2.getValue() < 0)
493 if (op.hasMinMaxBounds())
496 AffineMap lbMap = op.getLowerBoundsMap();
499 bool isAlreadyNormalized =
500 llvm::all_of(llvm::zip(steps, lbMap.
getResults()), [](
auto tuple) {
501 int64_t step = std::get<0>(tuple);
502 auto lbExpr = dyn_cast<AffineConstantExpr>(std::get<1>(tuple));
503 return lbExpr && lbExpr.getValue() == 0 && step == 1;
505 if (isAlreadyNormalized)
510 op.getLowerBoundsValueMap(), &ranges);
512 auto zeroExpr = builder.getAffineConstantExpr(0);
515 for (
unsigned i = 0, e = steps.size(); i < e; ++i) {
516 int64_t step = steps[i];
519 lbExprs.push_back(zeroExpr);
523 ubExprs.push_back(ubExpr);
529 auto expr = lbExpr + builder.getAffineDimExpr(nDims) * step;
536 OperandRange dimOperands = lbOperands.take_front(nDims);
537 OperandRange symbolOperands = lbOperands.drop_front(nDims);
539 applyOperands.push_back(iv);
540 applyOperands.append(symbolOperands.begin(), symbolOperands.end());
541 auto apply = builder.create<AffineApplyOp>(op.
getLoc(), map, applyOperands);
546 op.setSteps(newSteps);
549 op.setLowerBounds({}, newLowerMap);
552 op.setUpperBounds(ranges.
getOperands(), newUpperMap);
556 bool promoteSingleIter) {
561 if (op.hasConstantLowerBound() && (op.getConstantLowerBound() == 0) &&
574 int64_t origLoopStep = op.getStepAsInt();
577 AffineMap oldLbMap = op.getLowerBoundMap();
589 AffineValueMap paddedLbValueMap(paddedLbMap, op.getLowerBoundOperands());
590 AffineValueMap ubValueMap(op.getUpperBoundMap(), op.getUpperBoundOperands());
599 for (
unsigned i = 0; i < numResult; ++i)
608 op.setUpperBound(newUbValueMap.
getOperands(), newUbMap);
621 (void)newIvToOldIvMap.canonicalize();
622 auto newIV = opBuilder.
create<AffineApplyOp>(
623 loc, newIvToOldIvMap.getAffineMap(), newIvToOldIvMap.getOperands());
624 op.getInductionVar().replaceAllUsesExcept(newIV->getResult(0), newIV);
649 unsigned minSurroundingLoops) {
663 for (
unsigned d = nsLoops + 1; d > minSurroundingLoops; d--) {
665 srcAccess, destAccess, d, &dependenceConstraints,
680 template <
typename EffectType,
typename T>
686 bool hasSideEffect =
false;
689 Value memref = memOp.getMemRef();
695 if (
auto memEffect = dyn_cast<MemoryEffectOpInterface>(op)) {
697 memEffect.getEffects(effects);
699 bool opMayHaveEffect =
false;
700 for (
auto effect : effects) {
703 if (isa<EffectType>(effect.getEffect())) {
704 if (effect.getValue() && effect.getValue() != memref &&
705 !
mayAlias(effect.getValue(), memref))
707 opMayHaveEffect =
true;
712 if (!opMayHaveEffect)
717 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) {
724 unsigned minSurroundingLoops =
727 hasSideEffect =
true;
733 hasSideEffect =
true;
741 for (
Block &block : region)
749 hasSideEffect =
true;
760 checkOperation(parent);
769 "Checking for side effect between two operations without a common "
777 until(untilOp->getParentOp(), untilOp);
789 for (
auto iter = ++from->getIterator(), end = from->
getBlock()->
end();
790 iter != end && &*iter != untilOp; ++iter) {
791 checkOperation(&*iter);
796 if (untilOp->getBlock() != from->
getBlock())
798 todoBlocks.push_back(succ);
803 while (!todoBlocks.empty()) {
804 Block *blk = todoBlocks.pop_back_val();
808 for (
auto &op : *blk) {
814 todoBlocks.push_back(succ);
819 return !hasSideEffect;
838 for (
auto *user : loadOp.getMemRef().getUsers()) {
839 auto storeOp = dyn_cast<AffineWriteOpInterface>(user);
853 if (srcAccess != destAccess)
863 if (storeOp->getBlock() != loadOp->getBlock() &&
869 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(storeOp, loadOp,
874 assert(lastWriteStoreOp ==
nullptr &&
875 "multiple simultaneous replacement stores");
876 lastWriteStoreOp = storeOp;
879 if (!lastWriteStoreOp)
884 cast<AffineWriteOpInterface>(lastWriteStoreOp).getValueToStore();
887 if (storeVal.
getType() != loadOp.getValue().getType())
891 memrefsToErase.insert(loadOp.getMemRef());
893 loadOpsToErase.push_back(loadOp);
898 affine::AffineReadOpInterface>(
914 auto writeB = dyn_cast<AffineWriteOpInterface>(user);
919 if (writeB == writeA)
923 if (writeB->getParentRegion() != writeA->getParentRegion())
930 if (srcAccess != destAccess)
939 if (!affine::hasNoInterveningEffect<MemoryEffects::Read>(writeA, writeB,
943 opsToErase.push_back(writeA);
954 static void loadCSE(AffineReadOpInterface loadA,
959 for (
auto *user : loadA.getMemRef().getUsers()) {
960 auto loadB = dyn_cast<AffineReadOpInterface>(user);
961 if (!loadB || loadB == loadA)
968 if (srcAccess != destAccess) {
977 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(
978 loadB.getOperation(), loadA,
mayAlias))
983 if (loadB.getValue().getType() != loadA.getValue().getType())
986 loadCandidates.push_back(loadB);
992 for (AffineReadOpInterface option : loadCandidates) {
993 if (llvm::all_of(loadCandidates, [&](AffineReadOpInterface depStore) {
994 return depStore == option ||
996 depStore.getOperation());
998 loadB = option.getValue();
1006 loadOpsToErase.push_back(loadA);
1045 return !aliasAnalysis.
alias(val1, val2).
isNo();
1049 f.walk([&](AffineReadOpInterface loadOp) {
1052 for (
auto *op : opsToErase)
1057 f.walk([&](AffineWriteOpInterface storeOp) {
1060 for (
auto *op : opsToErase)
1068 for (
auto memref : memrefsToErase) {
1070 Operation *defOp = memref.getDefiningOp();
1071 if (!defOp || !hasSingleEffect<MemoryEffects::Allocate>(defOp, memref))
1075 if (llvm::any_of(memref.getUsers(), [&](
Operation *ownerOp) {
1076 return !isa<AffineWriteOpInterface>(ownerOp) &&
1077 !hasSingleEffect<MemoryEffects::Free>(ownerOp, memref);
1082 for (
auto *user : llvm::make_early_inc_range(memref.getUsers()))
1090 f.walk([&](AffineReadOpInterface loadOp) {
1093 for (
auto *op : opsToErase)
1102 bool allowNonDereferencingOps) {
1103 unsigned newMemRefRank = cast<MemRefType>(newMemRef.
getType()).getRank();
1104 (void)newMemRefRank;
1105 unsigned oldMemRefRank = cast<MemRefType>(oldMemRef.
getType()).getRank();
1106 (void)oldMemRefRank;
1108 assert(indexRemap.
getNumSymbols() == symbolOperands.size() &&
1109 "symbolic operand count mismatch");
1111 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1112 assert(indexRemap.
getNumResults() + extraIndices.size() == newMemRefRank);
1114 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1118 assert(cast<MemRefType>(oldMemRef.
getType()).getElementType() ==
1119 cast<MemRefType>(newMemRef.
getType()).getElementType());
1123 if (opEntry.value() == oldMemRef)
1124 usePositions.push_back(opEntry.index());
1128 if (usePositions.empty())
1131 if (usePositions.size() > 1) {
1133 assert(
false &&
"multiple dereferencing uses in a single op not supported");
1137 unsigned memRefOperandPos = usePositions.front();
1142 auto affMapAccInterface = dyn_cast<AffineMapAccessInterface>(op);
1143 if (!affMapAccInterface) {
1144 if (!allowNonDereferencingOps) {
1155 affMapAccInterface.getAffineMapAttrForMemRef(oldMemRef);
1160 op->
operand_begin() + memRefOperandPos + 1 + oldMapNumInputs);
1165 oldMemRefOperands.reserve(oldMemRefRank);
1167 for (
auto resultExpr : oldMap.
getResults()) {
1170 auto afOp = builder.
create<AffineApplyOp>(op->
getLoc(), singleResMap,
1172 oldMemRefOperands.push_back(afOp);
1173 affineApplyOps.push_back(afOp);
1176 oldMemRefOperands.assign(oldMapOperands.begin(), oldMapOperands.end());
1183 remapOperands.reserve(extraOperands.size() + oldMemRefRank +
1184 symbolOperands.size());
1185 remapOperands.append(extraOperands.begin(), extraOperands.end());
1186 remapOperands.append(oldMemRefOperands.begin(), oldMemRefOperands.end());
1187 remapOperands.append(symbolOperands.begin(), symbolOperands.end());
1190 remapOutputs.reserve(oldMemRefRank);
1195 for (
auto resultExpr : indexRemap.
getResults()) {
1198 auto afOp = builder.
create<AffineApplyOp>(op->
getLoc(), singleResMap,
1200 remapOutputs.push_back(afOp);
1201 affineApplyOps.push_back(afOp);
1205 remapOutputs.assign(remapOperands.begin(), remapOperands.end());
1209 newMapOperands.reserve(newMemRefRank);
1212 for (
Value extraIndex : extraIndices) {
1214 "invalid memory op index");
1215 newMapOperands.push_back(extraIndex);
1219 newMapOperands.append(remapOutputs.begin(), remapOutputs.end());
1222 assert(newMapOperands.size() == newMemRefRank);
1228 for (
Value value : affineApplyOps)
1229 if (value.use_empty())
1230 value.getDefiningOp()->erase();
1234 state.operands.reserve(op->
getNumOperands() + extraIndices.size());
1239 state.operands.push_back(newMemRef);
1242 state.operands.append(newMapOperands.begin(), newMapOperands.end());
1245 state.operands.append(op->
operand_begin() + memRefOperandPos + 1 +
1252 state.types.push_back(result.getType());
1256 for (
auto namedAttr : op->
getAttrs()) {
1257 if (namedAttr.getName() == oldMapAttrPair.
getName())
1258 state.attributes.push_back({namedAttr.getName(), newMapAttr});
1260 state.attributes.push_back(namedAttr);
1264 auto *repOp = builder.
create(state);
1275 Operation *postDomOpFilter,
bool allowNonDereferencingOps,
1276 bool replaceInDeallocOp) {
1277 unsigned newMemRefRank = cast<MemRefType>(newMemRef.
getType()).getRank();
1278 (void)newMemRefRank;
1279 unsigned oldMemRefRank = cast<MemRefType>(oldMemRef.
getType()).getRank();
1280 (void)oldMemRefRank;
1282 assert(indexRemap.
getNumSymbols() == symbolOperands.size() &&
1283 "symbol operand count mismatch");
1285 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1286 assert(indexRemap.
getNumResults() + extraIndices.size() == newMemRefRank);
1288 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1292 assert(cast<MemRefType>(oldMemRef.
getType()).getElementType() ==
1293 cast<MemRefType>(newMemRef.
getType()).getElementType());
1295 std::unique_ptr<DominanceInfo> domInfo;
1296 std::unique_ptr<PostDominanceInfo> postDomInfo;
1298 domInfo = std::make_unique<DominanceInfo>(
1301 if (postDomOpFilter)
1302 postDomInfo = std::make_unique<PostDominanceInfo>(
1309 for (
auto *op : oldMemRef.
getUsers()) {
1311 if (domOpFilter && !domInfo->dominates(domOpFilter, op))
1315 if (postDomOpFilter && !postDomInfo->postDominates(postDomOpFilter, op))
1320 if (hasSingleEffect<MemoryEffects::Free>(op, oldMemRef) &&
1321 !replaceInDeallocOp)
1327 if (!isa<AffineMapAccessInterface>(*op)) {
1328 if (!allowNonDereferencingOps) {
1329 LLVM_DEBUG(llvm::dbgs()
1330 <<
"Memref replacement failed: non-deferencing memref op: \n"
1337 LLVM_DEBUG(llvm::dbgs() <<
"Memref replacement failed: use without a "
1338 "memrefs normalizable trait: \n"
1346 opsToReplace.insert(op);
1349 for (
auto *op : opsToReplace) {
1351 oldMemRef, newMemRef, op, extraIndices, indexRemap, extraOperands,
1352 symbolOperands, allowNonDereferencingOps)))
1353 llvm_unreachable(
"memref replacement guaranteed to succeed here");
1393 if (isa_and_nonnull<AffineApplyOp>(operand.getDefiningOp()))
1394 subOperands.push_back(operand);
1400 if (affineApplyOps.empty())
1405 bool localized =
true;
1406 for (
auto *op : affineApplyOps) {
1408 for (
auto *user : result.getUsers()) {
1409 if (user != opInst) {
1425 sliceOps->reserve(composedMap.getNumResults());
1426 for (
auto resultExpr : composedMap.getResults()) {
1428 composedMap.getNumSymbols(), resultExpr);
1429 sliceOps->push_back(builder.
create<AffineApplyOp>(
1430 opInst->
getLoc(), singleResMap, composedOpOperands));
1438 for (
Value &operand : newOperands) {
1441 for (
j = 0, f = subOperands.size();
j < f;
j++) {
1442 if (operand == subOperands[
j])
1445 if (
j < subOperands.size())
1446 operand = (*sliceOps)[
j];
1448 for (
unsigned idx = 0, e = newOperands.size(); idx < e; idx++)
1471 SmallVectorImpl<std::tuple<AffineExpr, unsigned, unsigned>> &tileSizePos) {
1482 if (isa<AffineConstantExpr>(binaryExpr.
getRHS()))
1483 floordivExprs.emplace_back(
1484 std::make_tuple(binaryExpr.
getLHS(), binaryExpr.
getRHS(), pos));
1489 if (floordivExprs.empty()) {
1496 for (std::tuple<AffineExpr, AffineExpr, unsigned> fexpr : floordivExprs) {
1497 AffineExpr floordivExprLHS = std::get<0>(fexpr);
1498 AffineExpr floordivExprRHS = std::get<1>(fexpr);
1499 unsigned floordivPos = std::get<2>(fexpr);
1511 bool notTiled =
false;
1512 if (pos != floordivPos) {
1514 if (e == floordivExprLHS) {
1516 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(expr);
1518 if (floordivExprLHS == binaryExpr.getLHS() &&
1519 floordivExprRHS == binaryExpr.getRHS()) {
1523 tileSizePos.emplace_back(
1524 std::make_tuple(binaryExpr.getRHS(), floordivPos, pos));
1576 if (isa<AffineDimExpr>(e) &&
1577 llvm::any_of(inMemrefTypeDynDims, [&](
unsigned dim) {
1596 binaryExpr = cast<AffineBinaryOpExpr>(oldMapOutput);
1597 newMapOutput = binaryExpr.
getRHS();
1600 binaryExpr = cast<AffineBinaryOpExpr>(oldMapOutput);
1605 newMapOutput = oldMapOutput;
1607 return newMapOutput;
1643 MemRefType newMemRefType,
AffineMap map,
1649 unsigned dynIdx = 0;
1650 for (
unsigned d = 0; d < oldMemRefType.getRank(); ++d) {
1651 if (oldMemRefShape[d] < 0) {
1653 inAffineApply.emplace_back(allocOp->getDynamicSizes()[dynIdx]);
1658 inAffineApply.emplace_back(
1659 b.
create<arith::ConstantOp>(allocOp->getLoc(), constantAttr));
1665 unsigned newDimIdx = 0;
1670 if (newMemRefShape[newDimIdx] < 0) {
1673 for (
auto pos : tileSizePos) {
1674 if (newDimIdx == std::get<1>(pos))
1676 else if (newDimIdx == std::get<2>(pos))
1683 b.
create<AffineApplyOp>(allocOp->getLoc(), newMap, inAffineApply);
1684 newDynamicSizes.emplace_back(affineApp);
1692 MemRefType memrefType = allocOp->getType();
1698 if (newMemRefType == memrefType)
1703 Value oldMemRef = allocOp->getResult();
1706 AffineMap layoutMap = memrefType.getLayout().getAffineMap();
1707 memref::AllocOp newAlloc;
1712 if (newMemRefType.getNumDynamicDims() > 0 && !tileSizePos.empty()) {
1713 MemRefType oldMemRefType = cast<MemRefType>(oldMemRef.
getType());
1719 b.
create<memref::AllocOp>(allocOp->getLoc(), newMemRefType,
1720 newDynamicSizes, allocOp->getAlignmentAttr());
1722 newAlloc = b.
create<memref::AllocOp>(allocOp->getLoc(), newMemRefType,
1723 allocOp->getAlignmentAttr());
1741 return hasSingleEffect<MemoryEffects::Free>(op, oldMemRef);
1749 unsigned rank = memrefType.getRank();
1753 if (memrefType.getLayout().isIdentity()) {
1758 AffineMap layoutMap = memrefType.getLayout().getAffineMap();
1769 if (memrefType.getNumDynamicDims() > 0 && tileSizePos.empty())
1778 for (
unsigned d = 0; d < rank; ++d) {
1782 fac.
addBound(BoundType::UB, d, shape[d] - 1);
1784 memrefTypeDynDims.emplace_back(d);
1797 for (
unsigned d = 0; d < newRank; ++d) {
1800 newShape[d] = ShapedType::kDynamic;
1809 if (!ubConst.has_value() || *ubConst < 0) {
1810 LLVM_DEBUG(llvm::dbgs()
1811 <<
"can't normalize map due to unknown/invalid upper bound");
1815 newShape[d] = *ubConst + 1;
1819 auto newMemRefType =
1824 return newMemRefType;
1847 for (
unsigned i = 1, e = set.size(); i < e; i++)
1852 FailureOr<SmallVector<Value>>
1855 unsigned numDims = basis.size();
1858 for (
unsigned i = 1; i < numDims; i++) {
1867 results.reserve(divisors.size() + 1);
1868 Value residual = linearIndex;
1869 for (
Value divisor : divisors) {
1871 results.push_back(divMod.
quotient);
1874 results.push_back(residual);
1881 assert(multiIndex.size() == basis.size());
1883 for (
size_t i = 0; i < basis.size(); ++i) {
1889 strides.reserve(stridesAffine.size());
1890 llvm::transform(stridesAffine, std::back_inserter(strides),
1893 builder, builder.
getLoc(), strideExpr, basis);
1899 builder, builder.
getLoc(), linearIndexExpr, multiIndexAndStrides);
static void createNewDynamicSizes(MemRefType oldMemRefType, MemRefType newMemRefType, AffineMap map, memref::AllocOp *allocOp, OpBuilder b, SmallVectorImpl< Value > &newDynamicSizes)
Create new maps to calculate each dimension size of newMemRefType, and create newDynamicSizes from th...
static bool mayHaveEffect(Operation *srcMemOp, Operation *destMemOp, unsigned minSurroundingLoops)
Returns true if srcMemOp may have an effect on destMemOp within the scope of the outermost minSurroun...
static LogicalResult getTileSizePos(AffineMap map, SmallVectorImpl< std::tuple< AffineExpr, unsigned, unsigned >> &tileSizePos)
Check if map is a tiled layout.
static FailureOr< OpFoldResult > getIndexProduct(OpBuilder &b, Location loc, ArrayRef< Value > set)
Create IR that computes the product of all elements in the set.
TileExprPattern
Enum to set patterns of affine expr in tiled-layout map.
static void promoteIfBlock(AffineIfOp ifOp, bool elseBlock)
Promotes the then or the else block of ifOp (depending on whether elseBlock is false or true) into if...
static bool isNormalizedMemRefDynamicDim(unsigned dim, AffineMap layoutMap, SmallVectorImpl< unsigned > &inMemrefTypeDynDims)
Check if dim dimension of memrefType with layoutMap becomes dynamic after normalization.
static void loadCSE(AffineReadOpInterface loadA, SmallVectorImpl< Operation * > &loadOpsToErase, DominanceInfo &domInfo, llvm::function_ref< bool(Value, Value)> mayAlias)
static AffineExpr createDimSizeExprForTiledLayout(AffineExpr oldMapOutput, TileExprPattern pat)
Create affine expr to calculate dimension size for a tiled-layout map.
static Operation * getOutermostInvariantForOp(AffineIfOp ifOp)
Returns the outermost affine.for/parallel op that the ifOp is invariant on.
static void findUnusedStore(AffineWriteOpInterface writeA, SmallVectorImpl< Operation * > &opsToErase, PostDominanceInfo &postDominanceInfo, llvm::function_ref< bool(Value, Value)> mayAlias)
static bool mustReachAtInnermost(const MemRefAccess &srcAccess, const MemRefAccess &destAccess)
Returns true if the memory operation of destAccess depends on srcAccess inside of the innermost commo...
static void forwardStoreToLoad(AffineReadOpInterface loadOp, SmallVectorImpl< Operation * > &loadOpsToErase, SmallPtrSetImpl< Value > &memrefsToErase, DominanceInfo &domInfo, llvm::function_ref< bool(Value, Value)> mayAlias)
Attempt to eliminate loadOp by replacing it with a value stored into memory which the load is guarant...
static void visit(Operation *op, DenseSet< Operation * > &visited)
Visits all the pdl.operand(s), pdl.result(s), and pdl.operation(s) connected to the given operation.
static bool mayAlias(Value first, Value second)
Returns true if two values may be referencing aliasing memory.
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
Affine binary operation expression.
AffineExpr getLHS() const
AffineExpr getRHS() const
An integer constant appearing in affine expression.
A dimensional identifier appearing in an affine expression.
unsigned getPosition() const
See documentation for AffineExprVisitorBase.
Base type for affine expression.
AffineExpr floorDiv(uint64_t v) const
RetT walk(FnT &&callback) const
Walk all of the AffineExpr's in this expression in postorder.
AffineExpr ceilDiv(uint64_t v) const
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
MLIRContext * getContext() const
static AffineMap getMultiDimIdentityMap(unsigned numDims, MLIRContext *context)
Returns an AffineMap with 'numDims' identity result dim exprs.
static AffineMap get(MLIRContext *context)
Returns a zero result affine map with no dimensions or symbols: () -> ().
unsigned getNumSymbols() const
unsigned getNumDims() const
ArrayRef< AffineExpr > getResults() const
unsigned getNumResults() const
unsigned getNumInputs() const
AffineExpr getResult(unsigned idx) const
AffineMap compose(AffineMap map) const
Returns the AffineMap resulting from composing this with map.
A symbolic identifier appearing in an affine expression.
unsigned getPosition() const
This class represents the main alias analysis interface in MLIR.
AliasResult alias(Value lhs, Value rhs)
Given two values, return their aliasing behavior.
bool isNo() const
Returns if this result indicates no possibility of aliasing.
This class represents an argument of a Block.
Block represents an ordered list of Operations.
OpListType::iterator iterator
SuccessorRange getSuccessors()
Operation * getTerminator()
Get the terminator operation of this block.
OpListType & getOperations()
IntegerAttr getIndexAttr(int64_t value)
IntegerAttr getIntegerAttr(Type type, int64_t value)
AffineMap getMultiDimIdentityMap(unsigned rank)
BoolAttr getBoolAttr(bool value)
StringAttr getStringAttr(const Twine &bytes)
AffineExpr getAffineDimExpr(unsigned position)
AffineMap getConstantAffineMap(int64_t val)
Returns a single constant result affine map with 0 dimensions and 0 symbols.
MLIRContext * getContext() const
A class for computing basic dominance information.
bool dominates(Operation *a, Operation *b) const
Return true if operation A dominates operation B, i.e.
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
void projectOut(Value val)
Projects out the variable that is associate with Value.
This class represents a frozen set of patterns that can be processed by a pattern applicator.
This class allows control over how the GreedyPatternRewriteDriver works.
GreedyRewriteStrictness strictMode
Strict mode can restrict the ops that are added to the worklist during the rewrite.
This is a utility class for mapping one set of IR entities to another.
void clear()
Clears all mappings held by the mapper.
ImplicitLocOpBuilder maintains a 'current location', allowing use of the create<> method without spec...
Location getLoc() const
Accessors for the implied location.
This class defines the main interface for locations in MLIR and acts as a non-nullable wrapper around...
MLIRContext is the top-level object for a collection of MLIR operations.
This is a builder type that keeps local references to arguments.
Builder & setLayout(MemRefLayoutAttrInterface newLayout)
Builder & setShape(ArrayRef< int64_t > newShape)
NamedAttribute represents a combination of a name and an Attribute value.
StringAttr getName() const
Return the name of the attribute.
Attribute getValue() const
Return the value of the attribute.
This class helps build Operations.
static OpBuilder atBlockBegin(Block *block, Listener *listener=nullptr)
Create a builder and set the insertion point to before the first operation in the block but still ins...
Block::iterator getInsertionPoint() const
Returns the current insertion point of the builder.
Operation * clone(Operation &op, IRMapping &mapper)
Creates a deep copy of the specified operation, remapping any operands that use values outside of the...
void setInsertionPointToStart(Block *block)
Sets the insertion point to the start of the specified block.
Operation * create(const OperationState &state)
Creates an operation given the fields represented as an OperationState.
void setInsertionPointAfter(Operation *op)
Sets the insertion point to the node after the specified operation, which will cause subsequent inser...
Block * getInsertionBlock() const
Return the block the current insertion point belongs to.
This class represents a single result from folding an operation.
This trait indicates that the memory effects of an operation includes the effects of operations neste...
This class provides the API for ops that are known to be isolated from above.
This class implements the operand iterators for the Operation class.
Operation is the basic unit of execution within MLIR.
Value getOperand(unsigned idx)
bool hasTrait()
Returns true if the operation was registered with a particular trait, e.g.
void setOperand(unsigned idx, Value value)
operand_iterator operand_begin()
OpResult getResult(unsigned idx)
Get the 'idx'th result of this operation.
MLIRContext * getContext()
Return the context this operation is associated with.
Location getLoc()
The source location the operation was defined or derived from.
unsigned getNumOperands()
Operation * getParentOp()
Returns the closest surrounding operation that contains this operation or nullptr if this is a top-le...
ArrayRef< NamedAttribute > getAttrs()
Return all of the attributes on this operation.
Block * getBlock()
Returns the operation block that contains this operation.
OpTy getParentOfType()
Return the closest surrounding parent operation that is of type 'OpTy'.
operand_iterator operand_end()
Region & getRegion(unsigned index)
Returns the region held by this operation at position 'index'.
MutableArrayRef< Region > getRegions()
Returns the regions held by this operation.
OperationName getName()
The name of an operation is the key identifier for it.
operand_range getOperands()
Returns an iterator on the underlying Value's.
bool isAncestor(Operation *other)
Return true if this operation is an ancestor of the other operation.
void replaceAllUsesWith(ValuesT &&values)
Replace all uses of results of this operation with the provided 'values'.
void setOperands(ValueRange operands)
Replace the current operands of this operation with the ones provided in 'operands'.
user_range getUsers()
Returns a range of all users.
Region * getParentRegion()
Returns the region to which the instruction belongs.
result_range getResults()
void erase()
Remove this operation from its parent block and delete it.
unsigned getNumResults()
Return the number of results held by this operation.
A class for computing basic postdominance information.
bool postDominates(Operation *a, Operation *b)
Return true if operation A postdominates operation B.
This class contains a list of basic blocks and a link to the parent operation it is attached to.
Region * getParentRegion()
Return the region containing this region or nullptr if the region is attached to a top-level operatio...
bool isAncestor(Region *other)
Return true if this region is ancestor of the other region.
void takeBody(Region &other)
Takes body of another region (that region will have no body after this operation completes).
MLIRContext * getContext() const
This class provides an abstraction over the different types of ranges over Values.
type_range getTypes() const
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.
void replaceAllUsesExcept(Value newValue, const SmallPtrSetImpl< Operation * > &exceptions)
Replace all uses of 'this' value with 'newValue', updating anything in the IR that uses 'this' to use...
void replaceAllUsesWith(Value newValue)
Replace all uses of 'this' value with the new value, updating anything in the IR that uses 'this' to ...
user_range getUsers() const
Operation * getDefiningOp() const
If this value is the result of an operation, return the operation that defines it.
static WalkResult advance()
static WalkResult interrupt()
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes.
LogicalResult canonicalize()
Attempts to canonicalize the map and operands.
unsigned getNumSymbols() const
ArrayRef< Value > getOperands() const
unsigned getNumDims() const
AffineExpr getResult(unsigned i)
AffineMap getAffineMap() const
unsigned getNumResults() const
static void difference(const AffineValueMap &a, const AffineValueMap &b, AffineValueMap *res)
Return the value map that is the difference of value maps 'a' and 'b', represented as an affine map a...
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, ValueRange operands)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
std::optional< int64_t > getConstantBound64(BoundType type, unsigned pos) const
The same, but casts to int64_t.
unsigned getNumVars() const
unsigned getNumLocalVars() const
std::optional< SmallVector< Value, 8 > > expandAffineMap(OpBuilder &builder, Location loc, AffineMap affineMap, ValueRange operands)
Create a sequence of operations that implement the affineMap applied to the given operands (as it it ...
void fullyComposeAffineMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Given an affine map map and its input operands, this method composes into map, maps of AffineApplyOps...
FailureOr< SmallVector< Value > > delinearizeIndex(OpBuilder &b, Location loc, Value linearIndex, ArrayRef< Value > basis)
Generate the IR to delinearize linearIndex given the basis and return the multi-index.
void affineScalarReplace(func::FuncOp f, DominanceInfo &domInfo, PostDominanceInfo &postDomInfo, AliasAnalysis &analysis)
Replace affine store and load accesses by scalars by forwarding stores to loads and eliminate invaria...
LogicalResult promoteIfSingleIteration(AffineForOp forOp)
Promotes the loop body of a AffineForOp to its containing block if the loop was known to have a singl...
bool isValidDim(Value value)
Returns true if the given Value can be used as a dimension id in the region of the closest surroundin...
Value expandAffineExpr(OpBuilder &builder, Location loc, AffineExpr expr, ValueRange dimValues, ValueRange symbolValues)
Emit code that computes the given affine expression using standard arithmetic operations applied to t...
unsigned getNumCommonSurroundingLoops(Operation &a, Operation &b)
Returns the number of surrounding loops common to both A and B.
void normalizeAffineParallel(AffineParallelOp op)
Normalize a affine.parallel op so that lower bounds are 0 and steps are 1.
DependenceResult checkMemrefAccessDependence(const MemRefAccess &srcAccess, const MemRefAccess &dstAccess, unsigned loopDepth, FlatAffineValueConstraints *dependenceConstraints=nullptr, SmallVector< DependenceComponent, 2 > *dependenceComponents=nullptr, bool allowRAR=false)
LogicalResult affineParallelize(AffineForOp forOp, ArrayRef< LoopReduction > parallelReductions={}, AffineParallelOp *resOp=nullptr)
Replaces a parallel affine.for op with a 1-d affine.parallel op.
AffineApplyOp makeComposedAffineApply(OpBuilder &b, Location loc, AffineMap map, ArrayRef< OpFoldResult > operands)
Returns a composed AffineApplyOp by composing map and operands with other AffineApplyOps supplying th...
void canonicalizeMapAndOperands(AffineMap *map, SmallVectorImpl< Value > *operands)
Modifies both map and operands in-place so as to:
void getReachableAffineApplyOps(ArrayRef< Value > operands, SmallVectorImpl< Operation * > &affineApplyOps)
Returns in affineApplyOps, the sequence of those AffineApplyOp Operations that are reachable via a se...
LogicalResult normalizeAffineFor(AffineForOp op, bool promoteSingleIter=false)
Normalize an affine.for op.
LogicalResult normalizeMemRef(memref::AllocOp *op)
Rewrites the memref defined by this alloc op to have an identity layout map and updates all its index...
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...
OpFoldResult makeComposedFoldedAffineApply(OpBuilder &b, Location loc, AffineMap map, ArrayRef< OpFoldResult > operands)
Constructs an AffineApplyOp that applies map to operands after composing the map with the maps of any...
bool hasDependence(DependenceResult result)
Utility function that returns true if the provided DependenceResult corresponds to a dependence resul...
MemRefType normalizeMemRefType(MemRefType memrefType)
Normalizes memrefType so that the affine layout map of the memref is transformed to an identity map w...
OpFoldResult linearizeIndex(ArrayRef< OpFoldResult > multiIndex, ArrayRef< OpFoldResult > basis, ImplicitLocOpBuilder &builder)
Region * getAffineScope(Operation *op)
Returns the closest region enclosing op that is held by an operation with trait AffineScope; nullptr ...
DivModValue getDivMod(OpBuilder &b, Location loc, Value lhs, Value rhs)
Create IR to calculate (div lhs, rhs) and (mod lhs, rhs).
bool hasNoInterveningEffect(Operation *start, T memOp, llvm::function_ref< bool(Value, Value)> mayAlias)
Ensure that all operations that could be executed after start (noninclusive) and prior to memOp (e....
void createAffineComputationSlice(Operation *opInst, SmallVectorImpl< AffineApplyOp > *sliceOps)
Given an operation, inserts one or more single result affine apply operations, results of which are e...
LogicalResult hoistAffineIfOp(AffineIfOp ifOp, bool *folded=nullptr)
Hoists out affine.if/else to as high as possible, i.e., past all invariant affine....
bool noDependence(DependenceResult result)
Returns true if the provided DependenceResult corresponds to the absence of a dependence.
AffineExpr substWithMin(AffineExpr e, AffineExpr dim, AffineExpr min, AffineExpr max, bool positivePath=true)
Traverse e and return an AffineExpr where all occurrences of dim have been replaced by either:
LogicalResult replaceAllMemRefUsesWith(Value oldMemRef, Value newMemRef, ArrayRef< Value > extraIndices={}, AffineMap indexRemap=AffineMap(), ArrayRef< Value > extraOperands={}, ArrayRef< Value > symbolOperands={}, Operation *domOpFilter=nullptr, Operation *postDomOpFilter=nullptr, bool allowNonDereferencingOps=false, bool replaceInDeallocOp=false)
Replaces all "dereferencing" uses of oldMemRef with newMemRef while optionally remapping the old memr...
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Include the generated interface declarations.
AffineMap simplifyAffineMap(AffineMap map)
Simplifies an affine map by simplifying its underlying AffineExpr results.
LogicalResult applyOpPatternsAndFold(ArrayRef< Operation * > ops, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr, bool *allErased=nullptr)
Rewrite the specified ops by repeatedly applying the highest benefit patterns in a greedy worklist dr...
void bindDims(MLIRContext *ctx, AffineExprTy &...exprs)
Bind a list of AffineExpr references to DimExpr at positions: [0 .
std::pair< AffineExpr, SmallVector< OpFoldResult > > computeLinearIndex(OpFoldResult sourceOffset, ArrayRef< OpFoldResult > strides, ArrayRef< OpFoldResult > indices)
Compute linear index from provided strides and indices, assuming strided layout.
SmallVector< int64_t > computeStrides(ArrayRef< int64_t > sizes)
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
@ CeilDiv
RHS of ceildiv is always a constant or a symbolic expression.
@ Mod
RHS of mod is always a constant or a symbolic expression with a positive value.
@ FloorDiv
RHS of floordiv is always a constant or a symbolic expression.
AffineExpr getAffineBinaryOpExpr(AffineExprKind kind, AffineExpr lhs, AffineExpr rhs)
void bindSymbols(MLIRContext *ctx, AffineExprTy &...exprs)
Bind a list of AffineExpr references to SymbolExpr at positions: [0 .
LogicalResult applyPatternsAndFoldGreedily(Region ®ion, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr)
Rewrite ops in the given region, which must be isolated from above, by repeatedly applying the highes...
Value getValueOrCreateConstantIndexOp(OpBuilder &b, Location loc, OpFoldResult ofr)
Converts an OpFoldResult to a Value.
auto get(MLIRContext *context, Ts &&...params)
Helper method that injects context only if needed, this helps unify some of the attribute constructio...
@ ExistingOps
Only pre-existing ops are processed.
AffineExpr getAffineDimExpr(unsigned position, MLIRContext *context)
These free functions allow clients of the API to not use classes in detail.
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
The following effect indicates that the operation reads from some resource.
This represents an operation in an abstracted form, suitable for use with the builder APIs.
Checks whether two accesses to the same memref access the same element.
Holds the result of (div a, b) and (mod a, b).
A description of a (parallelizable) reduction in an affine loop.
arith::AtomicRMWKind kind
Reduction kind.
Value value
The value being reduced.
Encapsulates a memref load or store access information.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.