30 #define DEBUG_TYPE "affine-utils"
33 using namespace affine;
34 using namespace presburger;
40 class AffineApplyExpander
47 : builder(builder), dimValues(dimValues), symbolValues(symbolValues),
50 template <
typename OpTy>
56 auto op = builder.
create<OpTy>(loc, lhs, rhs);
61 return buildBinaryExpr<arith::AddIOp>(expr);
65 return buildBinaryExpr<arith::MulIOp>(expr);
78 if (
auto rhsConst = dyn_cast<AffineConstantExpr>(expr.
getRHS())) {
79 if (rhsConst.getValue() <= 0) {
80 emitError(loc,
"modulo by non-positive value is not supported");
87 assert(lhs && rhs &&
"unexpected affine expr lowering failure");
89 Value remainder = builder.
create<arith::RemSIOp>(loc, lhs, rhs);
90 Value zeroCst = builder.
create<arith::ConstantIndexOp>(loc, 0);
91 Value isRemainderNegative = builder.
create<arith::CmpIOp>(
92 loc, arith::CmpIPredicate::slt, remainder, zeroCst);
93 Value correctedRemainder =
94 builder.
create<arith::AddIOp>(loc, remainder, rhs);
96 loc, isRemainderNegative, correctedRemainder, remainder);
118 if (
auto rhsConst = dyn_cast<AffineConstantExpr>(expr.
getRHS())) {
119 if (rhsConst.getValue() <= 0) {
120 emitError(loc,
"division by non-positive value is not supported");
126 assert(lhs && rhs &&
"unexpected affine expr lowering failure");
128 Value zeroCst = builder.
create<arith::ConstantIndexOp>(loc, 0);
129 Value noneCst = builder.
create<arith::ConstantIndexOp>(loc, -1);
131 loc, arith::CmpIPredicate::slt, lhs, zeroCst);
132 Value negatedDecremented = builder.
create<arith::SubIOp>(loc, noneCst, lhs);
134 builder.
create<arith::SelectOp>(loc, negative, negatedDecremented, lhs);
135 Value quotient = builder.
create<arith::DivSIOp>(loc, dividend, rhs);
136 Value correctedQuotient =
137 builder.
create<arith::SubIOp>(loc, noneCst, quotient);
138 Value result = builder.
create<arith::SelectOp>(loc, negative,
139 correctedQuotient, quotient);
157 if (
auto rhsConst = dyn_cast<AffineConstantExpr>(expr.
getRHS())) {
158 if (rhsConst.getValue() <= 0) {
159 emitError(loc,
"division by non-positive value is not supported");
165 assert(lhs && rhs &&
"unexpected affine expr lowering failure");
167 Value zeroCst = builder.
create<arith::ConstantIndexOp>(loc, 0);
168 Value oneCst = builder.
create<arith::ConstantIndexOp>(loc, 1);
170 loc, arith::CmpIPredicate::sle, lhs, zeroCst);
171 Value negated = builder.
create<arith::SubIOp>(loc, zeroCst, lhs);
172 Value decremented = builder.
create<arith::SubIOp>(loc, lhs, oneCst);
174 builder.
create<arith::SelectOp>(loc, nonPositive, negated, decremented);
175 Value quotient = builder.
create<arith::DivSIOp>(loc, dividend, rhs);
176 Value negatedQuotient =
177 builder.
create<arith::SubIOp>(loc, zeroCst, quotient);
178 Value incrementedQuotient =
179 builder.
create<arith::AddIOp>(loc, quotient, oneCst);
181 loc, nonPositive, negatedQuotient, incrementedQuotient);
186 auto op = builder.
create<arith::ConstantIndexOp>(loc, expr.
getValue());
192 "affine dim position out of range");
198 "symbol dim position out of range");
217 return AffineApplyExpander(builder, dimValues, symbolValues, loc).visit(expr);
222 std::optional<SmallVector<Value, 8>>
226 auto expanded = llvm::to_vector<8>(
228 [numDims, &builder, loc, operands](
AffineExpr expr) {
229 return expandAffineExpr(builder, loc, expr,
230 operands.take_front(numDims),
231 operands.drop_front(numDims));
233 if (llvm::all_of(expanded, [](
Value v) {
return v; }))
243 assert(ifOp.hasElse() &&
"else block expected");
245 Block *destBlock = ifOp->getBlock();
246 Block *srcBlock = elseBlock ? ifOp.getElseBlock() : ifOp.getThenBlock();
249 std::prev(srcBlock->
end()));
260 auto *res = ifOp.getOperation();
261 while (!isa<func::FuncOp>(res->getParentOp())) {
262 auto *parentOp = res->getParentOp();
263 if (
auto forOp = dyn_cast<AffineForOp>(parentOp)) {
264 if (llvm::is_contained(ifOperands, forOp.getInductionVar()))
266 }
else if (
auto parallelOp = dyn_cast<AffineParallelOp>(parentOp)) {
267 for (
auto iv : parallelOp.getIVs())
268 if (llvm::is_contained(ifOperands, iv))
270 }
else if (!isa<AffineIfOp>(parentOp)) {
285 if (hoistOverOp == ifOp)
295 auto hoistedIfOp = b.
create<AffineIfOp>(ifOp.getLoc(), ifOp.getIntegerSet(),
304 StringAttr idForIfOp = b.
getStringAttr(
"__mlir_if_hoisting");
309 hoistOverOpClone = b.
clone(*hoistOverOp, operandMap);
315 auto *thenBlock = hoistedIfOp.getThenBlock();
316 thenBlock->getOperations().splice(thenBlock->begin(),
321 AffineIfOp ifCloneInElse;
322 hoistOverOpClone->walk([&](AffineIfOp ifClone) {
323 if (!ifClone->getAttr(idForIfOp))
325 ifCloneInElse = ifClone;
328 assert(ifCloneInElse &&
"if op clone should exist");
331 if (!ifCloneInElse.hasElse())
332 ifCloneInElse.erase();
337 auto *elseBlock = hoistedIfOp.getElseBlock();
338 elseBlock->getOperations().splice(
339 elseBlock->begin(), hoistOverOpClone->getBlock()->getOperations(),
348 AffineParallelOp *resOp) {
350 unsigned numReductions = parallelReductions.size();
351 if (numReductions != forOp.getNumIterOperands())
356 AffineMap lowerBoundMap = forOp.getLowerBoundMap();
357 ValueRange lowerBoundOperands = forOp.getLowerBoundOperands();
358 AffineMap upperBoundMap = forOp.getUpperBoundMap();
359 ValueRange upperBoundOperands = forOp.getUpperBoundOperands();
362 auto reducedValues = llvm::to_vector<4>(llvm::map_range(
364 auto reductionKinds = llvm::to_vector<4>(llvm::map_range(
366 AffineParallelOp newPloop = outsideBuilder.
create<AffineParallelOp>(
373 Operation *yieldOp = &newPloop.getBody()->back();
378 newResults.reserve(numReductions);
379 for (
unsigned i = 0; i < numReductions; ++i) {
380 Value init = forOp.getInits()[i];
385 assert(reductionOp &&
"yielded value is expected to be produced by an op");
389 reductionOp->
setOperands({init, newPloop->getResult(i)});
390 forOp->getResult(i).replaceAllUsesWith(reductionOp->
getResult(0));
399 newPloop.getBody()->eraseArguments(numIVs, numReductions);
411 if (ifOp.getNumResults() != 0)
420 AffineIfOp::getCanonicalizationPatterns(patterns, ifOp.
getContext());
437 assert(llvm::all_of(ifOp.getOperands(),
439 return isTopLevelValue(v) || isAffineForInductionVar(v);
441 "operands not composed");
449 if (hoistedIfOp == ifOp)
466 return positivePath ?
min :
max;
467 if (
auto bin = dyn_cast<AffineBinaryOpExpr>(e)) {
474 auto c1 = dyn_cast<AffineConstantExpr>(bin.getLHS());
475 auto c2 = dyn_cast<AffineConstantExpr>(bin.getRHS());
476 if (c1 && c1.getValue() < 0)
479 if (c2 && c2.getValue() < 0)
491 if (op.hasMinMaxBounds())
494 AffineMap lbMap = op.getLowerBoundsMap();
497 bool isAlreadyNormalized =
498 llvm::all_of(llvm::zip(steps, lbMap.
getResults()), [](
auto tuple) {
499 int64_t step = std::get<0>(tuple);
500 auto lbExpr = dyn_cast<AffineConstantExpr>(std::get<1>(tuple));
501 return lbExpr && lbExpr.getValue() == 0 && step == 1;
503 if (isAlreadyNormalized)
508 op.getLowerBoundsValueMap(), &ranges);
510 auto zeroExpr = builder.getAffineConstantExpr(0);
513 for (
unsigned i = 0, e = steps.size(); i < e; ++i) {
514 int64_t step = steps[i];
517 lbExprs.push_back(zeroExpr);
521 ubExprs.push_back(ubExpr);
527 auto expr = lbExpr + builder.getAffineDimExpr(nDims) * step;
534 OperandRange dimOperands = lbOperands.take_front(nDims);
535 OperandRange symbolOperands = lbOperands.drop_front(nDims);
537 applyOperands.push_back(iv);
538 applyOperands.append(symbolOperands.begin(), symbolOperands.end());
539 auto apply = builder.create<AffineApplyOp>(op.
getLoc(), map, applyOperands);
544 op.setSteps(newSteps);
547 op.setLowerBounds({}, newLowerMap);
550 op.setUpperBounds(ranges.
getOperands(), newUpperMap);
554 bool promoteSingleIter) {
559 if (op.hasConstantLowerBound() && (op.getConstantLowerBound() == 0) &&
572 int64_t origLoopStep = op.getStepAsInt();
575 AffineMap oldLbMap = op.getLowerBoundMap();
587 AffineValueMap paddedLbValueMap(paddedLbMap, op.getLowerBoundOperands());
588 AffineValueMap ubValueMap(op.getUpperBoundMap(), op.getUpperBoundOperands());
597 for (
unsigned i = 0; i < numResult; ++i)
606 op.setUpperBound(newUbValueMap.
getOperands(), newUbMap);
619 (void)newIvToOldIvMap.canonicalize();
620 auto newIV = opBuilder.
create<AffineApplyOp>(
621 loc, newIvToOldIvMap.getAffineMap(), newIvToOldIvMap.getOperands());
622 op.getInductionVar().replaceAllUsesExcept(newIV->getResult(0), newIV);
647 unsigned minSurroundingLoops) {
661 for (
unsigned d = nsLoops + 1; d > minSurroundingLoops; d--) {
663 srcAccess, destAccess, d, &dependenceConstraints,
678 template <
typename EffectType,
typename T>
680 auto isLocallyAllocated = [](
Value memref) {
681 auto *defOp = memref.getDefiningOp();
682 return defOp && hasSingleEffect<MemoryEffects::Allocate>(defOp, memref);
687 bool hasSideEffect =
false;
690 Value memref = memOp.getMemRef();
696 if (
auto memEffect = dyn_cast<MemoryEffectOpInterface>(op)) {
698 memEffect.getEffects(effects);
700 bool opMayHaveEffect =
false;
701 for (
auto effect : effects) {
704 if (isa<EffectType>(effect.getEffect())) {
707 if (effect.getValue() && effect.getValue() != memref &&
708 isLocallyAllocated(memref) &&
709 isLocallyAllocated(effect.getValue()))
711 opMayHaveEffect =
true;
716 if (!opMayHaveEffect)
721 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) {
728 unsigned minSurroundingLoops =
731 hasSideEffect =
true;
737 hasSideEffect =
true;
745 for (
Block &block : region)
753 hasSideEffect =
true;
764 checkOperation(parent);
773 "Checking for side effect between two operations without a common "
781 until(untilOp->getParentOp(), untilOp);
793 for (
auto iter = ++from->getIterator(), end = from->
getBlock()->
end();
794 iter != end && &*iter != untilOp; ++iter) {
795 checkOperation(&*iter);
800 if (untilOp->getBlock() != from->
getBlock())
802 todoBlocks.push_back(succ);
807 while (!todoBlocks.empty()) {
808 Block *blk = todoBlocks.pop_back_val();
812 for (
auto &op : *blk) {
818 todoBlocks.push_back(succ);
823 return !hasSideEffect;
842 for (
auto *user : loadOp.getMemRef().getUsers()) {
843 auto storeOp = dyn_cast<AffineWriteOpInterface>(user);
857 if (srcAccess != destAccess)
867 if (storeOp->getBlock() != loadOp->getBlock() &&
873 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(storeOp, loadOp))
877 assert(lastWriteStoreOp ==
nullptr &&
878 "multiple simultaneous replacement stores");
879 lastWriteStoreOp = storeOp;
882 if (!lastWriteStoreOp)
887 cast<AffineWriteOpInterface>(lastWriteStoreOp).getValueToStore();
890 if (storeVal.
getType() != loadOp.getValue().getType())
894 memrefsToErase.insert(loadOp.getMemRef());
896 loadOpsToErase.push_back(loadOp);
901 affine::AffineReadOpInterface>(
915 auto writeB = dyn_cast<AffineWriteOpInterface>(user);
920 if (writeB == writeA)
924 if (writeB->getParentRegion() != writeA->getParentRegion())
931 if (srcAccess != destAccess)
940 if (!affine::hasNoInterveningEffect<MemoryEffects::Read>(writeA, writeB))
943 opsToErase.push_back(writeA);
954 static void loadCSE(AffineReadOpInterface loadA,
958 for (
auto *user : loadA.getMemRef().getUsers()) {
959 auto loadB = dyn_cast<AffineReadOpInterface>(user);
960 if (!loadB || loadB == loadA)
967 if (srcAccess != destAccess) {
976 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(
977 loadB.getOperation(), loadA))
982 if (loadB.getValue().getType() != loadA.getValue().getType())
985 loadCandidates.push_back(loadB);
991 for (AffineReadOpInterface option : loadCandidates) {
992 if (llvm::all_of(loadCandidates, [&](AffineReadOpInterface depStore) {
993 return depStore == option ||
995 depStore.getOperation());
997 loadB = option.getValue();
1005 loadOpsToErase.push_back(loadA);
1043 f.walk([&](AffineReadOpInterface loadOp) {
1046 for (
auto *op : opsToErase)
1051 f.walk([&](AffineWriteOpInterface storeOp) {
1054 for (
auto *op : opsToErase)
1062 for (
auto memref : memrefsToErase) {
1064 Operation *defOp = memref.getDefiningOp();
1065 if (!defOp || !hasSingleEffect<MemoryEffects::Allocate>(defOp, memref))
1069 if (llvm::any_of(memref.getUsers(), [&](
Operation *ownerOp) {
1070 return !isa<AffineWriteOpInterface>(ownerOp) &&
1071 !hasSingleEffect<MemoryEffects::Free>(ownerOp, memref);
1076 for (
auto *user : llvm::make_early_inc_range(memref.getUsers()))
1084 f.walk([&](AffineReadOpInterface loadOp) {
1085 loadCSE(loadOp, opsToErase, domInfo);
1087 for (
auto *op : opsToErase)
1096 bool allowNonDereferencingOps) {
1097 unsigned newMemRefRank = cast<MemRefType>(newMemRef.
getType()).getRank();
1098 (void)newMemRefRank;
1099 unsigned oldMemRefRank = cast<MemRefType>(oldMemRef.
getType()).getRank();
1100 (void)oldMemRefRank;
1102 assert(indexRemap.
getNumSymbols() == symbolOperands.size() &&
1103 "symbolic operand count mismatch");
1105 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1106 assert(indexRemap.
getNumResults() + extraIndices.size() == newMemRefRank);
1108 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1112 assert(cast<MemRefType>(oldMemRef.
getType()).getElementType() ==
1113 cast<MemRefType>(newMemRef.
getType()).getElementType());
1117 if (opEntry.value() == oldMemRef)
1118 usePositions.push_back(opEntry.index());
1122 if (usePositions.empty())
1125 if (usePositions.size() > 1) {
1127 assert(
false &&
"multiple dereferencing uses in a single op not supported");
1131 unsigned memRefOperandPos = usePositions.front();
1136 auto affMapAccInterface = dyn_cast<AffineMapAccessInterface>(op);
1137 if (!affMapAccInterface) {
1138 if (!allowNonDereferencingOps) {
1149 affMapAccInterface.getAffineMapAttrForMemRef(oldMemRef);
1154 op->
operand_begin() + memRefOperandPos + 1 + oldMapNumInputs);
1159 oldMemRefOperands.reserve(oldMemRefRank);
1161 for (
auto resultExpr : oldMap.
getResults()) {
1164 auto afOp = builder.
create<AffineApplyOp>(op->
getLoc(), singleResMap,
1166 oldMemRefOperands.push_back(afOp);
1167 affineApplyOps.push_back(afOp);
1170 oldMemRefOperands.assign(oldMapOperands.begin(), oldMapOperands.end());
1177 remapOperands.reserve(extraOperands.size() + oldMemRefRank +
1178 symbolOperands.size());
1179 remapOperands.append(extraOperands.begin(), extraOperands.end());
1180 remapOperands.append(oldMemRefOperands.begin(), oldMemRefOperands.end());
1181 remapOperands.append(symbolOperands.begin(), symbolOperands.end());
1184 remapOutputs.reserve(oldMemRefRank);
1189 for (
auto resultExpr : indexRemap.
getResults()) {
1192 auto afOp = builder.
create<AffineApplyOp>(op->
getLoc(), singleResMap,
1194 remapOutputs.push_back(afOp);
1195 affineApplyOps.push_back(afOp);
1199 remapOutputs.assign(remapOperands.begin(), remapOperands.end());
1203 newMapOperands.reserve(newMemRefRank);
1206 for (
Value extraIndex : extraIndices) {
1208 "invalid memory op index");
1209 newMapOperands.push_back(extraIndex);
1213 newMapOperands.append(remapOutputs.begin(), remapOutputs.end());
1216 assert(newMapOperands.size() == newMemRefRank);
1223 for (
Value value : affineApplyOps)
1224 if (value.use_empty())
1225 value.getDefiningOp()->erase();
1229 state.operands.reserve(op->
getNumOperands() + extraIndices.size());
1234 state.operands.push_back(newMemRef);
1237 state.operands.append(newMapOperands.begin(), newMapOperands.end());
1240 state.operands.append(op->
operand_begin() + memRefOperandPos + 1 +
1247 state.types.push_back(result.getType());
1251 for (
auto namedAttr : op->
getAttrs()) {
1252 if (namedAttr.getName() == oldMapAttrPair.
getName())
1253 state.attributes.push_back({namedAttr.getName(), newMapAttr});
1255 state.attributes.push_back(namedAttr);
1259 auto *repOp = builder.
create(state);
1270 Operation *postDomOpFilter,
bool allowNonDereferencingOps,
1271 bool replaceInDeallocOp) {
1272 unsigned newMemRefRank = cast<MemRefType>(newMemRef.
getType()).getRank();
1273 (void)newMemRefRank;
1274 unsigned oldMemRefRank = cast<MemRefType>(oldMemRef.
getType()).getRank();
1275 (void)oldMemRefRank;
1277 assert(indexRemap.
getNumSymbols() == symbolOperands.size() &&
1278 "symbol operand count mismatch");
1280 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1281 assert(indexRemap.
getNumResults() + extraIndices.size() == newMemRefRank);
1283 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1287 assert(cast<MemRefType>(oldMemRef.
getType()).getElementType() ==
1288 cast<MemRefType>(newMemRef.
getType()).getElementType());
1290 std::unique_ptr<DominanceInfo> domInfo;
1291 std::unique_ptr<PostDominanceInfo> postDomInfo;
1293 domInfo = std::make_unique<DominanceInfo>(
1296 if (postDomOpFilter)
1297 postDomInfo = std::make_unique<PostDominanceInfo>(
1304 for (
auto *op : oldMemRef.
getUsers()) {
1306 if (domOpFilter && !domInfo->dominates(domOpFilter, op))
1310 if (postDomOpFilter && !postDomInfo->postDominates(postDomOpFilter, op))
1315 if (hasSingleEffect<MemoryEffects::Free>(op, oldMemRef) &&
1316 !replaceInDeallocOp)
1322 if (!isa<AffineMapAccessInterface>(*op)) {
1323 if (!allowNonDereferencingOps) {
1324 LLVM_DEBUG(llvm::dbgs()
1325 <<
"Memref replacement failed: non-deferencing memref op: \n"
1332 LLVM_DEBUG(llvm::dbgs() <<
"Memref replacement failed: use without a "
1333 "memrefs normalizable trait: \n"
1341 opsToReplace.insert(op);
1344 for (
auto *op : opsToReplace) {
1346 oldMemRef, newMemRef, op, extraIndices, indexRemap, extraOperands,
1347 symbolOperands, allowNonDereferencingOps)))
1348 llvm_unreachable(
"memref replacement guaranteed to succeed here");
1388 if (isa_and_nonnull<AffineApplyOp>(operand.getDefiningOp()))
1389 subOperands.push_back(operand);
1395 if (affineApplyOps.empty())
1400 bool localized =
true;
1401 for (
auto *op : affineApplyOps) {
1403 for (
auto *user : result.getUsers()) {
1404 if (user != opInst) {
1420 sliceOps->reserve(composedMap.getNumResults());
1421 for (
auto resultExpr : composedMap.getResults()) {
1423 composedMap.getNumSymbols(), resultExpr);
1424 sliceOps->push_back(builder.
create<AffineApplyOp>(
1425 opInst->
getLoc(), singleResMap, composedOpOperands));
1433 for (
Value &operand : newOperands) {
1436 for (
j = 0, f = subOperands.size();
j < f;
j++) {
1437 if (operand == subOperands[
j])
1440 if (
j < subOperands.size())
1441 operand = (*sliceOps)[
j];
1443 for (
unsigned idx = 0, e = newOperands.size(); idx < e; idx++)
1466 SmallVectorImpl<std::tuple<AffineExpr, unsigned, unsigned>> &tileSizePos) {
1477 if (isa<AffineConstantExpr>(binaryExpr.
getRHS()))
1478 floordivExprs.emplace_back(
1479 std::make_tuple(binaryExpr.
getLHS(), binaryExpr.
getRHS(), pos));
1484 if (floordivExprs.empty()) {
1491 for (std::tuple<AffineExpr, AffineExpr, unsigned> fexpr : floordivExprs) {
1492 AffineExpr floordivExprLHS = std::get<0>(fexpr);
1493 AffineExpr floordivExprRHS = std::get<1>(fexpr);
1494 unsigned floordivPos = std::get<2>(fexpr);
1506 bool notTiled =
false;
1507 if (pos != floordivPos) {
1509 if (e == floordivExprLHS) {
1511 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(expr);
1513 if (floordivExprLHS == binaryExpr.getLHS() &&
1514 floordivExprRHS == binaryExpr.getRHS()) {
1518 tileSizePos.emplace_back(
1519 std::make_tuple(binaryExpr.getRHS(), floordivPos, pos));
1566 bool isDynamicDim =
false;
1570 expr.
walk([&inMemrefTypeDynDims, &isDynamicDim, &context](
AffineExpr e) {
1571 if (isa<AffineDimExpr>(e)) {
1572 for (
unsigned dm : inMemrefTypeDynDims) {
1574 isDynamicDim =
true;
1579 return isDynamicDim;
1592 binaryExpr = cast<AffineBinaryOpExpr>(oldMapOutput);
1593 newMapOutput = binaryExpr.
getRHS();
1596 binaryExpr = cast<AffineBinaryOpExpr>(oldMapOutput);
1601 newMapOutput = oldMapOutput;
1603 return newMapOutput;
1639 MemRefType newMemRefType,
AffineMap map,
1645 unsigned dynIdx = 0;
1646 for (
unsigned d = 0; d < oldMemRefType.getRank(); ++d) {
1647 if (oldMemRefShape[d] < 0) {
1649 inAffineApply.emplace_back(allocOp->getDynamicSizes()[dynIdx]);
1654 inAffineApply.emplace_back(
1655 b.
create<arith::ConstantOp>(allocOp->getLoc(), constantAttr));
1661 unsigned newDimIdx = 0;
1666 if (newMemRefShape[newDimIdx] < 0) {
1669 for (
auto pos : tileSizePos) {
1670 if (newDimIdx == std::get<1>(pos))
1672 else if (newDimIdx == std::get<2>(pos))
1679 b.
create<AffineApplyOp>(allocOp->getLoc(), newMap, inAffineApply);
1680 newDynamicSizes.emplace_back(affineApp);
1688 MemRefType memrefType = allocOp->getType();
1694 if (newMemRefType == memrefType)
1699 Value oldMemRef = allocOp->getResult();
1702 AffineMap layoutMap = memrefType.getLayout().getAffineMap();
1703 memref::AllocOp newAlloc;
1708 if (newMemRefType.getNumDynamicDims() > 0 && !tileSizePos.empty()) {
1709 MemRefType oldMemRefType = cast<MemRefType>(oldMemRef.
getType());
1715 b.
create<memref::AllocOp>(allocOp->getLoc(), newMemRefType,
1716 newDynamicSizes, allocOp->getAlignmentAttr());
1718 newAlloc = b.
create<memref::AllocOp>(allocOp->getLoc(), newMemRefType,
1719 allocOp->getAlignmentAttr());
1737 return hasSingleEffect<MemoryEffects::Free>(op, oldMemRef);
1745 unsigned rank = memrefType.getRank();
1749 if (memrefType.getLayout().isIdentity()) {
1754 AffineMap layoutMap = memrefType.getLayout().getAffineMap();
1765 if (memrefType.getNumDynamicDims() > 0 && tileSizePos.empty())
1774 for (
unsigned d = 0; d < rank; ++d) {
1778 fac.
addBound(BoundType::UB, d, shape[d] - 1);
1780 memrefTypeDynDims.emplace_back(d);
1793 for (
unsigned d = 0; d < newRank; ++d) {
1798 newShape[d] = ShapedType::kDynamic;
1806 if (!ubConst.has_value() || *ubConst < 0) {
1807 LLVM_DEBUG(llvm::dbgs()
1808 <<
"can't normalize map due to unknown/invalid upper bound");
1812 newShape[d] = *ubConst + 1;
1817 MemRefType newMemRefType =
1822 return newMemRefType;
1845 for (
unsigned i = 1, e = set.size(); i < e; i++)
1853 unsigned numDims = basis.size();
1856 for (
unsigned i = 1; i < numDims; i++) {
1865 results.reserve(divisors.size() + 1);
1866 Value residual = linearIndex;
1867 for (
Value divisor : divisors) {
1869 results.push_back(divMod.
quotient);
1872 results.push_back(residual);
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 void loadCSE(AffineReadOpInterface loadA, SmallVectorImpl< Operation * > &loadOpsToErase, DominanceInfo &domInfo)
static void forwardStoreToLoad(AffineReadOpInterface loadOp, SmallVectorImpl< Operation * > &loadOpsToErase, SmallPtrSetImpl< Value > &memrefsToErase, DominanceInfo &domInfo)
Attempt to eliminate loadOp by replacing it with a value stored into memory which the load is guarant...
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.
static void findUnusedStore(AffineWriteOpInterface writeA, SmallVectorImpl< Operation * > &opsToErase, PostDominanceInfo &postDominanceInfo)
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 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 bool isNormalizedMemRefDynamicDim(unsigned dim, AffineMap layoutMap, SmallVectorImpl< unsigned > &inMemrefTypeDynDims, MLIRContext *context)
Check if dim dimension of memrefType with layoutMap becomes dynamic after normalization.
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 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 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
Base type for affine expression.
void walk(std::function< void(AffineExpr)> callback) const
Walk all of the AffineExpr's in this expression in postorder.
AffineExpr floorDiv(uint64_t v) const
AffineExpr ceilDiv(uint64_t v) const
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
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 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 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.
This class provides support for representing a failure result, or a valid value of type T.
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.
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.
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...
void affineScalarReplace(func::FuncOp f, DominanceInfo &domInfo, PostDominanceInfo &postDomInfo)
Replace affine store and load accesses by scalars by forwarding stores to loads and eliminate invaria...
bool hasNoInterveningEffect(Operation *start, T memOp)
Ensure that all operations that could be executed after start (noninclusive) and prior to memOp (e....
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...
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).
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 failure(bool isFailure=true)
Utility function to generate a LogicalResult.
LogicalResult applyOpPatternsAndFold(ArrayRef< Operation * > ops, const FrozenRewritePatternSet &patterns, GreedyRewriteConfig config=GreedyRewriteConfig(), bool *changed=nullptr, bool *allErased=nullptr)
Applies the specified rewrite patterns on ops while also trying to fold these ops.
void bindDims(MLIRContext *ctx, AffineExprTy &...exprs)
Bind a list of AffineExpr references to DimExpr at positions: [0 .
InFlightDiagnostic emitError(Location loc)
Utility method to emit an error message using this location.
bool succeeded(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a success value.
LogicalResult success(bool isSuccess=true)
Utility function to generate a LogicalResult.
@ 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.
bool failed(LogicalResult result)
Utility function that returns true if the provided LogicalResult corresponds to a failure value.
This class represents an efficient way to signal success or failure.
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.