18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/Support/MathExtras.h"
26 using llvm::divideCeilSigned;
27 using llvm::divideFloorSigned;
28 using llvm::divideSignedWouldOverflow;
38 template <
typename WalkRetTy>
41 struct AffineExprWalker
46 : callback(callback) {}
49 return callback(expr);
52 return callback(expr);
54 WalkRetTy visitDimExpr(
AffineDimExpr expr) {
return callback(expr); }
58 return AffineExprWalker(callback).walkPostOrder(e);
81 llvm_unreachable(
"unknown binary operation on affine expressions");
93 unsigned dimId = llvm::cast<AffineDimExpr>(*this).getPosition();
94 if (dimId >= dimReplacements.size())
96 return dimReplacements[dimId];
99 unsigned symId = llvm::cast<AffineSymbolExpr>(*this).getPosition();
100 if (symId >= symReplacements.size())
102 return symReplacements[symId];
109 auto binOp = llvm::cast<AffineBinaryOpExpr>(*
this);
110 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
111 auto newLHS = lhs.replaceDimsAndSymbols(dimReplacements, symReplacements);
112 auto newRHS = rhs.replaceDimsAndSymbols(dimReplacements, symReplacements);
113 if (newLHS == lhs && newRHS == rhs)
117 llvm_unreachable(
"Unknown AffineExpr");
121 return replaceDimsAndSymbols(dimReplacements, {});
126 return replaceDimsAndSymbols({}, symReplacements);
132 unsigned offset)
const {
134 for (
unsigned idx = 0; idx < offset; ++idx)
136 for (
unsigned idx = offset; idx < numDims; ++idx)
138 return replaceDimsAndSymbols(dims, {});
144 unsigned offset)
const {
146 for (
unsigned idx = 0; idx < offset; ++idx)
148 for (
unsigned idx = offset; idx < numSymbols; ++idx)
150 return replaceDimsAndSymbols({}, symbols);
156 auto it = map.find(*
this);
167 auto binOp = llvm::cast<AffineBinaryOpExpr>(*
this);
168 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
169 auto newLHS = lhs.replace(map);
170 auto newRHS = rhs.replace(map);
171 if (newLHS == lhs && newRHS == rhs)
175 llvm_unreachable(
"Unknown AffineExpr");
181 map.insert(std::make_pair(expr, replacement));
200 auto expr = llvm::cast<AffineBinaryOpExpr>(*
this);
201 return expr.getLHS().isSymbolicOrConstant() &&
202 expr.getRHS().isSymbolicOrConstant();
205 llvm_unreachable(
"Unknown AffineExpr");
217 auto op = llvm::cast<AffineBinaryOpExpr>(*
this);
218 return op.getLHS().isPureAffine() && op.getRHS().isPureAffine();
224 auto op = llvm::cast<AffineBinaryOpExpr>(*
this);
225 return op.getLHS().isPureAffine() && op.getRHS().isPureAffine() &&
226 (llvm::isa<AffineConstantExpr>(op.getLHS()) ||
227 llvm::isa<AffineConstantExpr>(op.getRHS()));
232 auto op = llvm::cast<AffineBinaryOpExpr>(*
this);
233 return op.getLHS().isPureAffine() &&
234 llvm::isa<AffineConstantExpr>(op.getRHS());
237 llvm_unreachable(
"Unknown AffineExpr");
253 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
254 auto rhs = llvm::dyn_cast<AffineConstantExpr>(binExpr.
getRHS());
256 if (rhs && rhs.getValue() != 0) {
258 if (lhsDiv % rhs.getValue() == 0)
259 return std::abs(lhsDiv / rhs.getValue());
264 return std::abs(llvm::cast<AffineConstantExpr>(*this).getValue());
266 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
273 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
278 llvm_unreachable(
"Unknown AffineExpr");
288 return factor * factor == 1;
290 return llvm::cast<AffineConstantExpr>(*this).getValue() % factor == 0;
292 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
298 (l * u) % factor == 0;
304 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
311 llvm_unreachable(
"Unknown AffineExpr");
318 if (
auto expr = llvm::dyn_cast<AffineBinaryOpExpr>(*
this)) {
319 return expr.getLHS().isFunctionOfDim(position) ||
320 expr.getRHS().isFunctionOfDim(position);
329 if (
auto expr = llvm::dyn_cast<AffineBinaryOpExpr>(*
this)) {
330 return expr.getLHS().isFunctionOfSymbol(position) ||
331 expr.getRHS().isFunctionOfSymbol(position);
359 bool fromMul =
false) {
363 "unexpected opKind");
366 return cast<AffineConstantExpr>(expr).getValue() == 0;
370 return (cast<AffineSymbolExpr>(expr).getPosition() == symbolPos);
419 llvm_unreachable(
"Unknown AffineExpr");
430 "unexpected opKind");
433 if (cast<AffineConstantExpr>(expr).getValue() != 0)
459 return binaryExpr.
getLHS() *
474 llvm_unreachable(
"Unknown AffineExpr");
482 auto addExpr = dyn_cast<AffineBinaryOpExpr>(expr);
484 result.push_back(expr);
494 auto mulExpr = dyn_cast<AffineBinaryOpExpr>(candidate);
497 if (
auto lhs = dyn_cast<AffineConstantExpr>(mulExpr.getLHS())) {
498 if (lhs.getValue() == -1) {
499 expr = mulExpr.getRHS();
503 if (
auto rhs = dyn_cast<AffineConstantExpr>(mulExpr.getRHS())) {
504 if (rhs.getValue() == -1) {
505 expr = mulExpr.getLHS();
521 unsigned numDims,
unsigned numSymbols) {
528 for (int64_t i = 0, e = summands.size(); i < e; ++i) {
536 if (innerMod.
getRHS() != rhs)
541 for (int64_t
j = 0;
j < e; ++
j)
543 diff = diff + summands[
j];
544 diff = diff - innerMod.
getLHS();
546 auto constExpr = dyn_cast<AffineConstantExpr>(diff);
547 if (constExpr && constExpr.getValue() == 0)
559 unsigned numSymbols) {
600 return simplifiedQuotient
605 llvm_unreachable(
"Unknown AffineExpr");
611 storage->context = context;
616 assignCtx,
static_cast<unsigned>(
kind), position);
645 storage->context = context;
655 return llvm::to_vector(llvm::map_range(constants, [&](int64_t constant) {
662 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
663 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
665 if (lhsConst && rhsConst) {
667 if (llvm::AddOverflow(lhsConst.getValue(), rhsConst.getValue(), sum)) {
675 if (isa<AffineConstantExpr>(lhs) ||
684 if (rhsConst.getValue() == 0)
688 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
690 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS()))
691 return lBin.getLHS() + (lrhs.getValue() + rhsConst.getValue());
697 std::optional<int64_t> rLhsConst, rRhsConst;
700 auto lBinOpExpr = dyn_cast<AffineBinaryOpExpr>(lhs);
702 (rLhsConstExpr = dyn_cast<AffineConstantExpr>(lBinOpExpr.getRHS()))) {
703 rLhsConst = rLhsConstExpr.
getValue();
704 firstExpr = lBinOpExpr.getLHS();
710 auto rBinOpExpr = dyn_cast<AffineBinaryOpExpr>(rhs);
713 (rRhsConstExpr = dyn_cast<AffineConstantExpr>(rBinOpExpr.getRHS()))) {
714 rRhsConst = rRhsConstExpr.
getValue();
715 secondExpr = rBinOpExpr.getLHS();
721 if (rLhsConst && rRhsConst && firstExpr == secondExpr)
729 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
730 return lBin.getLHS() + rhs + lrhs;
743 auto lrhs = rBinOpExpr.getLHS();
744 auto rrhs = rBinOpExpr.getRHS();
750 auto lrhsBinOpExpr = dyn_cast<AffineBinaryOpExpr>(lrhs);
752 auto rrhsConstOpExpr = dyn_cast<AffineConstantExpr>(rrhs);
753 if (rrhsConstOpExpr && rrhsConstOpExpr.getValue() == -1 && lrhsBinOpExpr &&
756 llrhs = lrhsBinOpExpr.getLHS();
758 rlrhs = lrhsBinOpExpr.getRHS();
759 auto llrhsBinOpExpr = dyn_cast<AffineBinaryOpExpr>(llrhs);
762 if (llrhsBinOpExpr.getRHS() == rlrhs && lhs == llrhsBinOpExpr.getLHS())
773 llrhs = lrBinOpExpr.
getLHS();
774 rlrhs = lrBinOpExpr.
getRHS();
775 auto rlrhsConstOpExpr = dyn_cast<AffineConstantExpr>(rlrhs);
777 bool isPositiveRhs = rlrhsConstOpExpr && rlrhsConstOpExpr.getValue() > 0;
779 if (isPositiveRhs && lhs == llrhs && rlrhs == -rrhs) {
788 if (
auto simplified =
simplifyAdd(lBinOpExpr.getRHS(), rhs))
789 return lBinOpExpr.getLHS() + simplified;
795 static std::pair<AffineExpr, AffineExpr>
797 auto sym1 = dyn_cast<AffineSymbolExpr>(expr1);
798 auto sym2 = dyn_cast<AffineSymbolExpr>(expr2);
801 return sym1.getPosition() < sym2.getPosition() ? std::pair{expr1, expr2}
802 : std::pair{expr2, expr1};
804 auto dim1 = dyn_cast<AffineDimExpr>(expr1);
805 auto dim2 = dyn_cast<AffineDimExpr>(expr2);
807 return dim1.getPosition() < dim2.getPosition() ? std::pair{expr1, expr2}
808 : std::pair{expr2, expr1};
818 return {expr1, expr2};
837 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
838 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
840 if (lhsConst && rhsConst) {
842 if (llvm::MulOverflow(lhsConst.getValue(), rhsConst.getValue(),
product)) {
863 if (rhsConst.getValue() == 1)
866 if (rhsConst.getValue() == 0)
871 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
873 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS()))
874 return lBin.getLHS() * (lrhs.getValue() * rhsConst.getValue());
880 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
881 return (lBin.getLHS() * rhs) * lrhs;
910 return *
this + (-other);
914 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
915 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
917 if (!rhsConst || rhsConst.getValue() == 0)
921 if (divideSignedWouldOverflow(lhsConst.getValue(), rhsConst.getValue()))
924 divideFloorSigned(lhsConst.getValue(), rhsConst.getValue()),
935 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
937 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
939 if (lrhs.getValue() % rhsConst.getValue() == 0)
940 return lBin.getLHS() * (lrhs.getValue() / rhsConst.getValue());
947 int64_t llhsDiv = lBin.getLHS().getLargestKnownDivisor();
948 int64_t lrhsDiv = lBin.getRHS().getLargestKnownDivisor();
950 if (llhsDiv % rhsConst.getValue() == 0 ||
951 lrhsDiv % rhsConst.getValue() == 0)
952 return lBin.getLHS().floorDiv(rhsConst.getValue()) +
953 lBin.getRHS().floorDiv(rhsConst.getValue());
973 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
974 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
976 if (!rhsConst || rhsConst.getValue() == 0)
980 if (divideSignedWouldOverflow(lhsConst.getValue(), rhsConst.getValue()))
983 divideCeilSigned(lhsConst.getValue(), rhsConst.getValue()),
989 if (rhsConst.getValue() == 1)
994 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
996 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
998 if (lrhs.getValue() % rhsConst.getValue() == 0)
999 return lBin.getLHS() * (lrhs.getValue() / rhsConst.getValue());
1020 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
1021 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
1024 if (!rhsConst || rhsConst.getValue() < 1)
1041 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
1043 int64_t llhsDiv = lBin.getLHS().getLargestKnownDivisor();
1044 int64_t lrhsDiv = lBin.getRHS().getLargestKnownDivisor();
1046 if (llhsDiv % rhsConst.getValue() == 0)
1047 return lBin.getRHS() % rhsConst.getValue();
1048 if (lrhsDiv % rhsConst.getValue() == 0)
1049 return lBin.getLHS() % rhsConst.getValue();
1054 auto intermediate = dyn_cast<AffineConstantExpr>(lBin.getRHS());
1055 if (intermediate && intermediate.getValue() >= 1 &&
1056 mod(intermediate.getValue(), rhsConst.getValue()) == 0) {
1057 return lBin.getLHS() % rhsConst.getValue();
1092 unsigned numSymbols,
1096 assert(flatExprs.size() - numDims - numSymbols - 1 == localExprs.size() &&
1097 "unexpected number of local expressions");
1101 for (
unsigned j = 0;
j < numDims + numSymbols;
j++) {
1102 if (flatExprs[
j] == 0)
1106 expr = expr +
id * flatExprs[
j];
1110 for (
unsigned j = numDims + numSymbols, e = flatExprs.size() - 1;
j < e;
1112 if (flatExprs[
j] == 0)
1114 auto term = localExprs[
j - numDims - numSymbols] * flatExprs[
j];
1119 int64_t constTerm = flatExprs[flatExprs.size() - 1];
1121 expr = expr + constTerm;
1135 unsigned numSymbols,
1138 assert(!flatExprs.empty() &&
"flatExprs cannot be empty");
1141 assert(flatExprs.size() - numDims - numSymbols - 1 == localExprs.size() &&
1142 "unexpected number of local expressions");
1174 auto addEntry = [&](std::pair<unsigned, signed> index, int64_t coefficient,
1176 assert(!llvm::is_contained(indices, index) &&
1177 "Key is already present in indices vector and overwriting will "
1178 "happen in `indexToExprMap` and `coefficients`!");
1180 indices.push_back(index);
1181 coefficients.insert({index, coefficient});
1182 indexToExprMap.insert({index, expr});
1190 unsigned offsetSym = 0;
1191 signed offsetDim = -1;
1192 for (
unsigned j = numDims;
j < numDims + numSymbols; ++
j) {
1193 if (flatExprs[
j] == 0)
1199 std::pair<unsigned, signed> indexEntry(
1200 j - numDims,
std::max(numDims, numSymbols) + offsetSym++);
1201 addEntry(indexEntry, flatExprs[
j],
1209 unsigned lhsPos, rhsPos;
1215 if (flatExprs[numDims + numSymbols + it.index()] == 0)
1218 auto binaryExpr = dyn_cast<AffineBinaryOpExpr>(expr);
1224 if (!((isa<AffineDimExpr>(lhs) || isa<AffineSymbolExpr>(lhs)) &&
1225 (isa<AffineDimExpr>(rhs) || isa<AffineSymbolExpr>(rhs) ||
1226 isa<AffineConstantExpr>(rhs)))) {
1229 if (isa<AffineConstantExpr>(rhs)) {
1234 if (isa<AffineDimExpr>(lhs)) {
1235 lhsPos = cast<AffineDimExpr>(lhs).getPosition();
1236 std::pair<unsigned, signed> indexEntry(lhsPos, offsetDim--);
1237 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()],
1240 lhsPos = cast<AffineSymbolExpr>(lhs).getPosition();
1241 std::pair<unsigned, signed> indexEntry(
1242 lhsPos,
std::max(numDims, numSymbols) + offsetSym++);
1243 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()],
1246 }
else if (isa<AffineDimExpr>(lhs)) {
1252 lhsPos = cast<AffineDimExpr>(lhs).getPosition();
1253 rhsPos = cast<AffineSymbolExpr>(rhs).getPosition();
1254 std::pair<unsigned, signed> indexEntry(lhsPos, rhsPos);
1255 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()], expr);
1261 lhsPos = cast<AffineSymbolExpr>(lhs).getPosition();
1262 rhsPos = cast<AffineSymbolExpr>(rhs).getPosition();
1263 std::pair<unsigned, signed> indexEntry(
1264 lhsPos,
std::max(numDims, numSymbols) + offsetSym++);
1265 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()], expr);
1267 addedToMap[it.index()] =
true;
1270 for (
unsigned j = 0;
j < numDims; ++
j) {
1271 if (flatExprs[
j] == 0)
1277 std::pair<unsigned, signed> indexEntry(
j, offsetDim--);
1284 llvm::sort(indices);
1285 for (
const std::pair<unsigned, unsigned> index : indices) {
1286 assert(indexToExprMap.lookup(index) &&
1287 "cannot find key in `indexToExprMap` map");
1288 expr = expr + indexToExprMap.lookup(index) * coefficients.lookup(index);
1292 for (
unsigned j = numDims + numSymbols, e = flatExprs.size() - 1;
j < e;
1296 if (flatExprs[
j] == 0 || addedToMap[
j - numDims - numSymbols])
1298 auto term = localExprs[
j - numDims - numSymbols] * flatExprs[
j];
1303 int64_t constTerm = flatExprs.back();
1305 expr = expr + constTerm;
1310 unsigned numSymbols)
1311 : numDims(numDims), numSymbols(numSymbols), numLocals(0) {
1329 if (!isa<AffineConstantExpr>(expr.
getRHS())) {
1336 return addLocalVariableSemiAffine(mulLhs, rhs, a * b, lhs, lhs.size());
1340 int64_t rhsConst = rhs[getConstantIndex()];
1341 for (int64_t &lhsElt : lhs)
1351 assert(lhs.size() == rhs.size());
1353 for (
unsigned i = 0, e = rhs.size(); i < e; i++) {
1382 if (!isa<AffineConstantExpr>(expr.
getRHS())) {
1388 AffineExpr modExpr = dividendExpr % divisorExpr;
1389 return addLocalVariableSemiAffine(modLhs, rhs, modExpr, lhs, lhs.size());
1392 int64_t rhsConst = rhs[getConstantIndex()];
1398 for (i = 0, e = lhs.size(); i < e; i++)
1399 if (lhs[i] % rhsConst != 0)
1402 if (i == lhs.size()) {
1411 uint64_t gcd = rhsConst;
1412 for (int64_t lhsElt : lhs)
1413 gcd = std::gcd(gcd, (uint64_t)
std::abs(lhsElt));
1416 for (int64_t &floorDividendElt : floorDividend)
1417 floorDividendElt = floorDividendElt /
static_cast<int64_t
>(gcd);
1419 int64_t floorDivisor = rhsConst /
static_cast<int64_t
>(gcd);
1428 if ((loc = findLocalId(floorDivExpr)) == -1) {
1431 lhs[getLocalVarStartIndex() +
numLocals - 1] = -rhsConst;
1434 lhs[getLocalVarStartIndex() + loc] -= rhsConst;
1441 return visitDivExpr(expr,
true);
1445 return visitDivExpr(expr,
false);
1461 eq[getSymbolStartIndex() + expr.
getPosition()] = 1;
1469 eq[getConstantIndex()] = expr.
getValue();
1473 LogicalResult SimpleAffineExprFlattener::addLocalVariableSemiAffine(
1476 assert(result.size() == resultSize &&
1477 "`result` vector passed is not of correct size");
1479 if ((loc = findLocalId(localExpr)) == -1) {
1483 llvm::fill(result, 0);
1485 result[getLocalVarStartIndex() +
numLocals - 1] = 1;
1487 result[getLocalVarStartIndex() + loc] = 1;
1516 if (!isa<AffineConstantExpr>(expr.
getRHS())) {
1523 return addLocalVariableSemiAffine(divLhs, rhs, divExpr, lhs, lhs.size());
1527 int64_t rhsConst = rhs[getConstantIndex()];
1534 for (int64_t lhsElt : lhs)
1535 gcd = std::gcd(gcd, (uint64_t)
std::abs(lhsElt));
1538 for (int64_t &lhsElt : lhs)
1539 lhsElt = lhsElt /
static_cast<int64_t
>(gcd);
1541 int64_t divisor = rhsConst /
static_cast<int64_t
>(gcd);
1557 if ((loc = findLocalId(divExpr)) == -1) {
1564 dividend.back() += divisor - 1;
1572 lhs[getLocalVarStartIndex() +
numLocals - 1] = 1;
1574 lhs[getLocalVarStartIndex() + loc] = 1;
1586 assert(divisor > 0 &&
"positive constant divisor expected");
1588 subExpr.insert(subExpr.begin() + getLocalVarStartIndex() +
numLocals, 0);
1597 subExpr.insert(subExpr.begin() + getLocalVarStartIndex() +
numLocals, 0);
1604 int SimpleAffineExprFlattener::findLocalId(
AffineExpr localExpr) {
1613 unsigned numSymbols) {
1638 return simplifiedExpr;
1642 AffineExpr expr,
unsigned numDims,
unsigned numSymbols,
1643 ArrayRef<std::optional<int64_t>> constLowerBounds,
1644 ArrayRef<std::optional<int64_t>> constUpperBounds,
bool isUpper) {
1646 if (
auto binOpExpr = dyn_cast<AffineBinaryOpExpr>(expr)) {
1650 auto rhsConst = dyn_cast<AffineConstantExpr>(binOpExpr.getRHS());
1651 if (!rhsConst || rhsConst.getValue() < 1)
1652 return std::nullopt;
1655 constLowerBounds, constUpperBounds, isUpper);
1657 return std::nullopt;
1658 return divideFloorSigned(*bound, rhsConst.getValue());
1661 auto rhsConst = dyn_cast<AffineConstantExpr>(binOpExpr.getRHS());
1662 if (rhsConst && rhsConst.getValue() >= 1) {
1665 constLowerBounds, constUpperBounds, isUpper);
1667 return std::nullopt;
1668 return divideCeilSigned(*bound, rhsConst.getValue());
1670 return std::nullopt;
1676 auto rhsConst = dyn_cast<AffineConstantExpr>(binOpExpr.getRHS());
1677 if (rhsConst && rhsConst.getValue() >= 1) {
1678 int64_t rhsConstVal = rhsConst.getValue();
1680 constLowerBounds, constUpperBounds,
1684 constLowerBounds, constUpperBounds, isUpper);
1686 divideFloorSigned(*lb, rhsConstVal) ==
1687 divideFloorSigned(*ub, rhsConstVal))
1688 return isUpper ? mod(*ub, rhsConstVal) : mod(*lb, rhsConstVal);
1689 return isUpper ? rhsConstVal - 1 : 0;
1697 if (
failed(simpleResult))
1698 return std::nullopt;
1703 return std::nullopt;
1707 for (
unsigned i = 0, e = numDims + numSymbols; i < e; ++i) {
1708 if (flattenedExpr[i] > 0) {
1709 auto &constBound = isUpper ? constUpperBounds[i] : constLowerBounds[i];
1711 return std::nullopt;
1712 bound += *constBound * flattenedExpr[i];
1713 }
else if (flattenedExpr[i] < 0) {
1714 auto &constBound = isUpper ? constLowerBounds[i] : constUpperBounds[i];
1716 return std::nullopt;
1717 bound += *constBound * flattenedExpr[i];
1721 bound += flattenedExpr.back();
static int64_t product(ArrayRef< int64_t > vals)
static AffineExpr symbolicDivide(AffineExpr expr, unsigned symbolPos, AffineExprKind opKind)
Divides the given expression by the given symbol at position symbolPos.
static AffineExpr simplifyMul(AffineExpr lhs, AffineExpr rhs)
Simplify a multiply expression. Return nullptr if it can't be simplified.
static AffineExpr simplifyMod(AffineExpr lhs, AffineExpr rhs)
static AffineExpr simplifyAdd(AffineExpr lhs, AffineExpr rhs)
Simplify add expression. Return nullptr if it can't be simplified.
static AffineExpr getSemiAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs a semi-affine expression from a flat ArrayRef.
static bool canSimplifyDivisionBySymbol(AffineExpr expr, unsigned symbolPos, AffineExprKind opKind, bool fromMul=false)
Returns true if the expression is divisible by the given symbol with position symbolPos.
static AffineExpr simplifyCeilDiv(AffineExpr lhs, AffineExpr rhs)
static AffineExpr simplifyFloorDiv(AffineExpr lhs, AffineExpr rhs)
static bool isNegatedAffineExpr(AffineExpr candidate, AffineExpr &expr)
Return "true" if candidate is a negated expression, i.e., Mul(-1, expr).
static AffineExpr getAffineDimOrSymbol(AffineExprKind kind, unsigned position, MLIRContext *context)
static bool isModOfModSubtraction(AffineExpr lhs, AffineExpr rhs, unsigned numDims, unsigned numSymbols)
Return "true" if lhs % rhs is guaranteed to evaluate to zero based on the fact that lhs contains anot...
static std::pair< AffineExpr, AffineExpr > orderCommutativeArgs(AffineExpr expr1, AffineExpr expr2)
Get the canonical order of two commutative exprs arguments.
static void getSummandExprs(AffineExpr expr, SmallVector< AffineExpr > &result)
Populate result with all summand operands of given (potentially nested) addition.
static AffineExpr simplifySemiAffine(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify a semi-affine expression by handling modulo, floordiv, or ceildiv operations when the second...
static MLIRContext * getContext(OpFoldResult val)
union mlir::linalg::@1244::ArityGroupAndKind::Kind kind
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
Affine binary operation expression.
AffineExpr getLHS() const
AffineBinaryOpExpr(AffineExpr::ImplType *ptr)
AffineExpr getRHS() const
An integer constant appearing in affine expression.
AffineConstantExpr(AffineExpr::ImplType *ptr=nullptr)
A dimensional identifier appearing in an affine expression.
AffineDimExpr(AffineExpr::ImplType *ptr)
unsigned getPosition() const
See documentation for AffineExprVisitorBase.
RetTy walkPostOrder(AffineExpr expr)
Base type for affine expression.
AffineExpr replaceDimsAndSymbols(ArrayRef< AffineExpr > dimReplacements, ArrayRef< AffineExpr > symReplacements) const
This method substitutes any uses of dimensions and symbols (e.g.
AffineExpr shiftDims(unsigned numDims, unsigned shift, unsigned offset=0) const
Replace dims[offset ...
AffineExpr operator+(int64_t v) const
bool isSymbolicOrConstant() const
Returns true if this expression is made out of only symbols and constants, i.e., it does not involve ...
AffineExpr operator*(int64_t v) const
bool operator==(AffineExpr other) const
bool isPureAffine() const
Returns true if this is a pure affine expression, i.e., multiplication, floordiv, ceildiv,...
AffineExpr shiftSymbols(unsigned numSymbols, unsigned shift, unsigned offset=0) const
Replace symbols[offset ...
AffineExpr operator-() const
AffineExpr floorDiv(uint64_t v) const
RetT walk(FnT &&callback) const
Walk all of the AffineExpr's in this expression in postorder.
AffineExprKind getKind() const
Return the classification for this type.
bool isMultipleOf(int64_t factor) const
Return true if the affine expression is a multiple of 'factor'.
int64_t getLargestKnownDivisor() const
Returns the greatest known integral divisor of this affine expression.
AffineExpr compose(AffineMap map) const
Compose with an AffineMap.
bool isFunctionOfDim(unsigned position) const
Return true if the affine expression involves AffineDimExpr position.
bool isFunctionOfSymbol(unsigned position) const
Return true if the affine expression involves AffineSymbolExpr position.
AffineExpr replaceDims(ArrayRef< AffineExpr > dimReplacements) const
Dim-only version of replaceDimsAndSymbols.
AffineExpr operator%(uint64_t v) const
MLIRContext * getContext() const
AffineExpr replace(AffineExpr expr, AffineExpr replacement) const
Sparse replace method.
AffineExpr replaceSymbols(ArrayRef< AffineExpr > symReplacements) const
Symbol-only version of replaceDimsAndSymbols.
AffineExpr ceilDiv(uint64_t v) const
void print(raw_ostream &os) const
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
ArrayRef< AffineExpr > getResults() const
A symbolic identifier appearing in an affine expression.
AffineSymbolExpr(AffineExpr::ImplType *ptr)
unsigned getPosition() const
MLIRContext is the top-level object for a collection of MLIR operations.
StorageUniquer & getAffineUniquer()
Returns the storage uniquer used for creating affine constructs.
virtual void addLocalFloorDivId(ArrayRef< int64_t > dividend, int64_t divisor, AffineExpr localExpr)
LogicalResult visitSymbolExpr(AffineSymbolExpr expr)
std::vector< SmallVector< int64_t, 8 > > operandExprStack
LogicalResult visitDimExpr(AffineDimExpr expr)
LogicalResult visitFloorDivExpr(AffineBinaryOpExpr expr)
LogicalResult visitConstantExpr(AffineConstantExpr expr)
virtual LogicalResult addLocalIdSemiAffine(ArrayRef< int64_t > lhs, ArrayRef< int64_t > rhs, AffineExpr localExpr)
Add a local identifier (needed to flatten a mod, floordiv, ceildiv, mul expr) when the rhs is a symbo...
LogicalResult visitModExpr(AffineBinaryOpExpr expr)
LogicalResult visitAddExpr(AffineBinaryOpExpr expr)
LogicalResult visitCeilDivExpr(AffineBinaryOpExpr expr)
LogicalResult visitMulExpr(AffineBinaryOpExpr expr)
SmallVector< AffineExpr, 4 > localExprs
SimpleAffineExprFlattener(unsigned numDims, unsigned numSymbols)
A utility class to get or create instances of "storage classes".
Storage * get(function_ref< void(Storage *)> initFn, TypeID id, Args &&...args)
Gets a uniqued instance of 'Storage'.
A utility result that is used to signal how to proceed with an ongoing walk:
constexpr void enumerate(std::tuple< Tys... > &tuple, CallbackT &&callback)
Fraction abs(const Fraction &f)
Include the generated interface declarations.
std::optional< int64_t > getBoundForAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, ArrayRef< std::optional< int64_t >> constLowerBounds, ArrayRef< std::optional< int64_t >> constUpperBounds, bool isUpper)
Get a lower or upper (depending on isUpper) bound for expr while using the constant lower and upper b...
@ CeilDiv
RHS of ceildiv is always a constant or a symbolic expression.
@ Mul
RHS of mul is always a constant or a symbolic expression.
@ Mod
RHS of mod is always a constant or a symbolic expression with a positive value.
@ DimId
Dimensional identifier.
@ FloorDiv
RHS of floordiv is always a constant or a symbolic expression.
@ Constant
Constant integer.
@ SymbolId
Symbolic identifier.
AffineExpr getAffineBinaryOpExpr(AffineExprKind kind, AffineExpr lhs, AffineExpr rhs)
AffineExpr getAffineExprFromFlatForm(ArrayRef< int64_t > flatExprs, unsigned numDims, unsigned numSymbols, ArrayRef< AffineExpr > localExprs, MLIRContext *context)
Constructs an affine expression from a flat ArrayRef.
AffineExpr getAffineConstantExpr(int64_t constant, MLIRContext *context)
AffineExpr simplifyAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols)
Simplify an affine expression by flattening and some amount of simple analysis.
SmallVector< AffineExpr > getAffineConstantExprs(ArrayRef< int64_t > constants, MLIRContext *context)
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)
raw_ostream & operator<<(raw_ostream &os, const AliasResult &result)
A binary operation appearing in an affine expression.
An integer constant appearing in affine expression.
A dimensional or symbolic identifier appearing in an affine expression.
Base storage class appearing in an affine expression.
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.