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>
682 auto isLocallyAllocated = [](
Value memref) {
683 auto *defOp = memref.getDefiningOp();
684 return defOp && hasSingleEffect<MemoryEffects::Allocate>(defOp, memref);
689 bool hasSideEffect =
false;
692 Value memref = memOp.getMemRef();
698 if (
auto memEffect = dyn_cast<MemoryEffectOpInterface>(op)) {
700 memEffect.getEffects(effects);
702 bool opMayHaveEffect =
false;
703 for (
auto effect : effects) {
706 if (isa<EffectType>(effect.getEffect())) {
709 if (effect.getValue() && effect.getValue() != memref &&
710 isLocallyAllocated(memref) &&
711 isLocallyAllocated(effect.getValue()))
713 opMayHaveEffect =
true;
718 if (!opMayHaveEffect)
723 if (isa<AffineReadOpInterface, AffineWriteOpInterface>(op)) {
730 unsigned minSurroundingLoops =
733 hasSideEffect =
true;
739 hasSideEffect =
true;
747 for (
Block &block : region)
755 hasSideEffect =
true;
766 checkOperation(parent);
775 "Checking for side effect between two operations without a common "
783 until(untilOp->getParentOp(), untilOp);
795 for (
auto iter = ++from->getIterator(), end = from->
getBlock()->
end();
796 iter != end && &*iter != untilOp; ++iter) {
797 checkOperation(&*iter);
802 if (untilOp->getBlock() != from->
getBlock())
804 todoBlocks.push_back(succ);
809 while (!todoBlocks.empty()) {
810 Block *blk = todoBlocks.pop_back_val();
814 for (
auto &op : *blk) {
820 todoBlocks.push_back(succ);
825 return !hasSideEffect;
844 for (
auto *user : loadOp.getMemRef().getUsers()) {
845 auto storeOp = dyn_cast<AffineWriteOpInterface>(user);
859 if (srcAccess != destAccess)
869 if (storeOp->getBlock() != loadOp->getBlock() &&
875 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(storeOp, loadOp))
879 assert(lastWriteStoreOp ==
nullptr &&
880 "multiple simultaneous replacement stores");
881 lastWriteStoreOp = storeOp;
884 if (!lastWriteStoreOp)
889 cast<AffineWriteOpInterface>(lastWriteStoreOp).getValueToStore();
892 if (storeVal.
getType() != loadOp.getValue().getType())
896 memrefsToErase.insert(loadOp.getMemRef());
898 loadOpsToErase.push_back(loadOp);
903 affine::AffineReadOpInterface>(
917 auto writeB = dyn_cast<AffineWriteOpInterface>(user);
922 if (writeB == writeA)
926 if (writeB->getParentRegion() != writeA->getParentRegion())
933 if (srcAccess != destAccess)
942 if (!affine::hasNoInterveningEffect<MemoryEffects::Read>(writeA, writeB))
945 opsToErase.push_back(writeA);
956 static void loadCSE(AffineReadOpInterface loadA,
960 for (
auto *user : loadA.getMemRef().getUsers()) {
961 auto loadB = dyn_cast<AffineReadOpInterface>(user);
962 if (!loadB || loadB == loadA)
969 if (srcAccess != destAccess) {
978 if (!affine::hasNoInterveningEffect<MemoryEffects::Write>(
979 loadB.getOperation(), loadA))
984 if (loadB.getValue().getType() != loadA.getValue().getType())
987 loadCandidates.push_back(loadB);
993 for (AffineReadOpInterface option : loadCandidates) {
994 if (llvm::all_of(loadCandidates, [&](AffineReadOpInterface depStore) {
995 return depStore == option ||
997 depStore.getOperation());
999 loadB = option.getValue();
1007 loadOpsToErase.push_back(loadA);
1045 f.walk([&](AffineReadOpInterface loadOp) {
1048 for (
auto *op : opsToErase)
1053 f.walk([&](AffineWriteOpInterface storeOp) {
1056 for (
auto *op : opsToErase)
1064 for (
auto memref : memrefsToErase) {
1066 Operation *defOp = memref.getDefiningOp();
1067 if (!defOp || !hasSingleEffect<MemoryEffects::Allocate>(defOp, memref))
1071 if (llvm::any_of(memref.getUsers(), [&](
Operation *ownerOp) {
1072 return !isa<AffineWriteOpInterface>(ownerOp) &&
1073 !hasSingleEffect<MemoryEffects::Free>(ownerOp, memref);
1078 for (
auto *user : llvm::make_early_inc_range(memref.getUsers()))
1086 f.walk([&](AffineReadOpInterface loadOp) {
1087 loadCSE(loadOp, opsToErase, domInfo);
1089 for (
auto *op : opsToErase)
1098 bool allowNonDereferencingOps) {
1099 unsigned newMemRefRank = cast<MemRefType>(newMemRef.
getType()).getRank();
1100 (void)newMemRefRank;
1101 unsigned oldMemRefRank = cast<MemRefType>(oldMemRef.
getType()).getRank();
1102 (void)oldMemRefRank;
1104 assert(indexRemap.
getNumSymbols() == symbolOperands.size() &&
1105 "symbolic operand count mismatch");
1107 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1108 assert(indexRemap.
getNumResults() + extraIndices.size() == newMemRefRank);
1110 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1114 assert(cast<MemRefType>(oldMemRef.
getType()).getElementType() ==
1115 cast<MemRefType>(newMemRef.
getType()).getElementType());
1119 if (opEntry.value() == oldMemRef)
1120 usePositions.push_back(opEntry.index());
1124 if (usePositions.empty())
1127 if (usePositions.size() > 1) {
1129 assert(
false &&
"multiple dereferencing uses in a single op not supported");
1133 unsigned memRefOperandPos = usePositions.front();
1138 auto affMapAccInterface = dyn_cast<AffineMapAccessInterface>(op);
1139 if (!affMapAccInterface) {
1140 if (!allowNonDereferencingOps) {
1151 affMapAccInterface.getAffineMapAttrForMemRef(oldMemRef);
1156 op->
operand_begin() + memRefOperandPos + 1 + oldMapNumInputs);
1161 oldMemRefOperands.reserve(oldMemRefRank);
1163 for (
auto resultExpr : oldMap.
getResults()) {
1166 auto afOp = builder.
create<AffineApplyOp>(op->
getLoc(), singleResMap,
1168 oldMemRefOperands.push_back(afOp);
1169 affineApplyOps.push_back(afOp);
1172 oldMemRefOperands.assign(oldMapOperands.begin(), oldMapOperands.end());
1179 remapOperands.reserve(extraOperands.size() + oldMemRefRank +
1180 symbolOperands.size());
1181 remapOperands.append(extraOperands.begin(), extraOperands.end());
1182 remapOperands.append(oldMemRefOperands.begin(), oldMemRefOperands.end());
1183 remapOperands.append(symbolOperands.begin(), symbolOperands.end());
1186 remapOutputs.reserve(oldMemRefRank);
1191 for (
auto resultExpr : indexRemap.
getResults()) {
1194 auto afOp = builder.
create<AffineApplyOp>(op->
getLoc(), singleResMap,
1196 remapOutputs.push_back(afOp);
1197 affineApplyOps.push_back(afOp);
1201 remapOutputs.assign(remapOperands.begin(), remapOperands.end());
1205 newMapOperands.reserve(newMemRefRank);
1208 for (
Value extraIndex : extraIndices) {
1210 "invalid memory op index");
1211 newMapOperands.push_back(extraIndex);
1215 newMapOperands.append(remapOutputs.begin(), remapOutputs.end());
1218 assert(newMapOperands.size() == newMemRefRank);
1224 for (
Value value : affineApplyOps)
1225 if (value.use_empty())
1226 value.getDefiningOp()->erase();
1230 state.operands.reserve(op->
getNumOperands() + extraIndices.size());
1235 state.operands.push_back(newMemRef);
1238 state.operands.append(newMapOperands.begin(), newMapOperands.end());
1241 state.operands.append(op->
operand_begin() + memRefOperandPos + 1 +
1248 state.types.push_back(result.getType());
1252 for (
auto namedAttr : op->
getAttrs()) {
1253 if (namedAttr.getName() == oldMapAttrPair.
getName())
1254 state.attributes.push_back({namedAttr.getName(), newMapAttr});
1256 state.attributes.push_back(namedAttr);
1260 auto *repOp = builder.
create(state);
1271 Operation *postDomOpFilter,
bool allowNonDereferencingOps,
1272 bool replaceInDeallocOp) {
1273 unsigned newMemRefRank = cast<MemRefType>(newMemRef.
getType()).getRank();
1274 (void)newMemRefRank;
1275 unsigned oldMemRefRank = cast<MemRefType>(oldMemRef.
getType()).getRank();
1276 (void)oldMemRefRank;
1278 assert(indexRemap.
getNumSymbols() == symbolOperands.size() &&
1279 "symbol operand count mismatch");
1281 extraOperands.size() + oldMemRefRank + symbolOperands.size());
1282 assert(indexRemap.
getNumResults() + extraIndices.size() == newMemRefRank);
1284 assert(oldMemRefRank + extraIndices.size() == newMemRefRank);
1288 assert(cast<MemRefType>(oldMemRef.
getType()).getElementType() ==
1289 cast<MemRefType>(newMemRef.
getType()).getElementType());
1291 std::unique_ptr<DominanceInfo> domInfo;
1292 std::unique_ptr<PostDominanceInfo> postDomInfo;
1294 domInfo = std::make_unique<DominanceInfo>(
1297 if (postDomOpFilter)
1298 postDomInfo = std::make_unique<PostDominanceInfo>(
1305 for (
auto *op : oldMemRef.
getUsers()) {
1307 if (domOpFilter && !domInfo->dominates(domOpFilter, op))
1311 if (postDomOpFilter && !postDomInfo->postDominates(postDomOpFilter, op))
1316 if (hasSingleEffect<MemoryEffects::Free>(op, oldMemRef) &&
1317 !replaceInDeallocOp)
1323 if (!isa<AffineMapAccessInterface>(*op)) {
1324 if (!allowNonDereferencingOps) {
1325 LLVM_DEBUG(llvm::dbgs()
1326 <<
"Memref replacement failed: non-deferencing memref op: \n"
1333 LLVM_DEBUG(llvm::dbgs() <<
"Memref replacement failed: use without a "
1334 "memrefs normalizable trait: \n"
1342 opsToReplace.insert(op);
1345 for (
auto *op : opsToReplace) {
1347 oldMemRef, newMemRef, op, extraIndices, indexRemap, extraOperands,
1348 symbolOperands, allowNonDereferencingOps)))
1349 llvm_unreachable(
"memref replacement guaranteed to succeed here");
1389 if (isa_and_nonnull<AffineApplyOp>(operand.getDefiningOp()))
1390 subOperands.push_back(operand);
1396 if (affineApplyOps.empty())
1401 bool localized =
true;
1402 for (
auto *op : affineApplyOps) {
1404 for (
auto *user : result.getUsers()) {
1405 if (user != opInst) {
1421 sliceOps->reserve(composedMap.getNumResults());
1422 for (
auto resultExpr : composedMap.getResults()) {
1424 composedMap.getNumSymbols(), resultExpr);
1425 sliceOps->push_back(builder.
create<AffineApplyOp>(
1426 opInst->
getLoc(), singleResMap, composedOpOperands));
1434 for (
Value &operand : newOperands) {
1437 for (
j = 0, f = subOperands.size();
j < f;
j++) {
1438 if (operand == subOperands[
j])
1441 if (
j < subOperands.size())
1442 operand = (*sliceOps)[
j];
1444 for (
unsigned idx = 0, e = newOperands.size(); idx < e; idx++)
1467 SmallVectorImpl<std::tuple<AffineExpr, unsigned, unsigned>> &tileSizePos) {
1478 if (isa<AffineConstantExpr>(binaryExpr.
getRHS()))
1479 floordivExprs.emplace_back(
1480 std::make_tuple(binaryExpr.
getLHS(), binaryExpr.
getRHS(), pos));
1485 if (floordivExprs.empty()) {
1492 for (std::tuple<AffineExpr, AffineExpr, unsigned> fexpr : floordivExprs) {
1493 AffineExpr floordivExprLHS = std::get<0>(fexpr);
1494 AffineExpr floordivExprRHS = std::get<1>(fexpr);
1495 unsigned floordivPos = std::get<2>(fexpr);
1507 bool notTiled =
false;
1508 if (pos != floordivPos) {
1510 if (e == floordivExprLHS) {
1512 AffineBinaryOpExpr binaryExpr = cast<AffineBinaryOpExpr>(expr);
1514 if (floordivExprLHS == binaryExpr.getLHS() &&
1515 floordivExprRHS == binaryExpr.getRHS()) {
1519 tileSizePos.emplace_back(
1520 std::make_tuple(binaryExpr.getRHS(), floordivPos, pos));
1572 if (isa<AffineDimExpr>(e) &&
1573 llvm::any_of(inMemrefTypeDynDims, [&](
unsigned dim) {
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) {
1796 newShape[d] = ShapedType::kDynamic;
1805 if (!ubConst.has_value() || *ubConst < 0) {
1806 LLVM_DEBUG(llvm::dbgs()
1807 <<
"can't normalize map due to unknown/invalid upper bound");
1811 newShape[d] = *ubConst + 1;
1815 auto newMemRefType =
1820 return newMemRefType;
1843 for (
unsigned i = 1, e = set.size(); i < e; i++)
1851 unsigned numDims = basis.size();
1854 for (
unsigned i = 1; i < numDims; i++) {
1863 results.reserve(divisors.size() + 1);
1864 Value residual = linearIndex;
1865 for (
Value divisor : divisors) {
1867 results.push_back(divMod.
quotient);
1870 results.push_back(residual);
1877 assert(multiIndex.size() == basis.size());
1879 for (
size_t i = 0; i < basis.size(); ++i) {
1885 strides.reserve(stridesAffine.size());
1886 llvm::transform(stridesAffine, std::back_inserter(strides),
1889 builder, builder.
getLoc(), strideExpr, basis);
1895 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 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 bool isNormalizedMemRefDynamicDim(unsigned dim, AffineMap layoutMap, SmallVectorImpl< unsigned > &inMemrefTypeDynDims)
Check if dim dimension of memrefType with layoutMap becomes dynamic after normalization.
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 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
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 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.
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.
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.
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...
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).
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)
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.
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.
AffineExpr getAffineSymbolExpr(unsigned position, MLIRContext *context)
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.