20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Support/MathExtras.h"
28 using llvm::divideCeilSigned;
29 using llvm::divideFloorSigned;
30 using llvm::divideSignedWouldOverflow;
40 template <
typename WalkRetTy>
43 struct AffineExprWalker
48 : callback(callback) {}
51 return callback(expr);
54 return callback(expr);
56 WalkRetTy visitDimExpr(
AffineDimExpr expr) {
return callback(expr); }
60 return AffineExprWalker(callback).walkPostOrder(e);
83 llvm_unreachable(
"unknown binary operation on affine expressions");
95 unsigned dimId = llvm::cast<AffineDimExpr>(*this).getPosition();
96 if (dimId >= dimReplacements.size())
98 return dimReplacements[dimId];
101 unsigned symId = llvm::cast<AffineSymbolExpr>(*this).getPosition();
102 if (symId >= symReplacements.size())
104 return symReplacements[symId];
111 auto binOp = llvm::cast<AffineBinaryOpExpr>(*
this);
112 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
113 auto newLHS = lhs.replaceDimsAndSymbols(dimReplacements, symReplacements);
114 auto newRHS = rhs.replaceDimsAndSymbols(dimReplacements, symReplacements);
115 if (newLHS == lhs && newRHS == rhs)
119 llvm_unreachable(
"Unknown AffineExpr");
123 return replaceDimsAndSymbols(dimReplacements, {});
128 return replaceDimsAndSymbols({}, symReplacements);
134 unsigned offset)
const {
136 for (
unsigned idx = 0; idx < offset; ++idx)
138 for (
unsigned idx = offset; idx < numDims; ++idx)
140 return replaceDimsAndSymbols(dims, {});
146 unsigned offset)
const {
148 for (
unsigned idx = 0; idx < offset; ++idx)
150 for (
unsigned idx = offset; idx < numSymbols; ++idx)
152 return replaceDimsAndSymbols({}, symbols);
158 auto it = map.find(*
this);
169 auto binOp = llvm::cast<AffineBinaryOpExpr>(*
this);
170 auto lhs = binOp.getLHS(), rhs = binOp.getRHS();
171 auto newLHS = lhs.replace(map);
172 auto newRHS = rhs.replace(map);
173 if (newLHS == lhs && newRHS == rhs)
177 llvm_unreachable(
"Unknown AffineExpr");
183 map.insert(std::make_pair(expr, replacement));
202 auto expr = llvm::cast<AffineBinaryOpExpr>(*
this);
203 return expr.getLHS().isSymbolicOrConstant() &&
204 expr.getRHS().isSymbolicOrConstant();
207 llvm_unreachable(
"Unknown AffineExpr");
219 auto op = llvm::cast<AffineBinaryOpExpr>(*
this);
220 return op.getLHS().isPureAffine() && op.getRHS().isPureAffine();
226 auto op = llvm::cast<AffineBinaryOpExpr>(*
this);
227 return op.getLHS().isPureAffine() && op.getRHS().isPureAffine() &&
228 (llvm::isa<AffineConstantExpr>(op.getLHS()) ||
229 llvm::isa<AffineConstantExpr>(op.getRHS()));
234 auto op = llvm::cast<AffineBinaryOpExpr>(*
this);
235 return op.getLHS().isPureAffine() &&
236 llvm::isa<AffineConstantExpr>(op.getRHS());
239 llvm_unreachable(
"Unknown AffineExpr");
255 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
256 auto rhs = llvm::dyn_cast<AffineConstantExpr>(binExpr.
getRHS());
258 if (rhs && rhs.getValue() != 0) {
260 if (lhsDiv % rhs.getValue() == 0)
261 return std::abs(lhsDiv / rhs.getValue());
266 return std::abs(llvm::cast<AffineConstantExpr>(*this).getValue());
268 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
275 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
280 llvm_unreachable(
"Unknown AffineExpr");
290 return factor * factor == 1;
292 return llvm::cast<AffineConstantExpr>(*this).getValue() % factor == 0;
294 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
300 (l * u) % factor == 0;
306 binExpr = llvm::cast<AffineBinaryOpExpr>(*
this);
313 llvm_unreachable(
"Unknown AffineExpr");
320 if (
auto expr = llvm::dyn_cast<AffineBinaryOpExpr>(*
this)) {
321 return expr.getLHS().isFunctionOfDim(position) ||
322 expr.getRHS().isFunctionOfDim(position);
331 if (
auto expr = llvm::dyn_cast<AffineBinaryOpExpr>(*
this)) {
332 return expr.getLHS().isFunctionOfSymbol(position) ||
333 expr.getRHS().isFunctionOfSymbol(position);
364 "unexpected opKind");
367 return cast<AffineConstantExpr>(expr).getValue() == 0;
371 return (cast<AffineSymbolExpr>(expr).getPosition() == symbolPos);
412 llvm_unreachable(
"Unknown AffineExpr");
423 "unexpected opKind");
426 if (cast<AffineConstantExpr>(expr).getValue() != 0)
452 return binaryExpr.
getLHS() *
467 llvm_unreachable(
"Unknown AffineExpr");
475 auto addExpr = dyn_cast<AffineBinaryOpExpr>(expr);
477 result.push_back(expr);
487 auto mulExpr = dyn_cast<AffineBinaryOpExpr>(candidate);
490 if (
auto lhs = dyn_cast<AffineConstantExpr>(mulExpr.getLHS())) {
491 if (lhs.getValue() == -1) {
492 expr = mulExpr.getRHS();
496 if (
auto rhs = dyn_cast<AffineConstantExpr>(mulExpr.getRHS())) {
497 if (rhs.getValue() == -1) {
498 expr = mulExpr.getLHS();
514 unsigned numDims,
unsigned numSymbols) {
521 for (int64_t i = 0, e = summands.size(); i < e; ++i) {
529 if (innerMod.
getRHS() != rhs)
534 for (int64_t
j = 0;
j < e; ++
j)
536 diff = diff + summands[
j];
537 diff = diff - innerMod.
getLHS();
539 auto constExpr = dyn_cast<AffineConstantExpr>(diff);
540 if (constExpr && constExpr.getValue() == 0)
552 unsigned numSymbols) {
593 llvm_unreachable(
"Unknown AffineExpr");
599 storage->context = context;
604 assignCtx,
static_cast<unsigned>(kind), position);
633 storage->context = context;
643 return llvm::to_vector(llvm::map_range(constants, [&](int64_t constant) {
650 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
651 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
653 if (lhsConst && rhsConst) {
655 if (llvm::AddOverflow(lhsConst.getValue(), rhsConst.getValue(), sum)) {
663 if (isa<AffineConstantExpr>(lhs) ||
672 if (rhsConst.getValue() == 0)
676 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
678 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS()))
679 return lBin.getLHS() + (lrhs.getValue() + rhsConst.getValue());
685 std::optional<int64_t> rLhsConst, rRhsConst;
688 auto lBinOpExpr = dyn_cast<AffineBinaryOpExpr>(lhs);
690 (rLhsConstExpr = dyn_cast<AffineConstantExpr>(lBinOpExpr.getRHS()))) {
691 rLhsConst = rLhsConstExpr.
getValue();
692 firstExpr = lBinOpExpr.getLHS();
698 auto rBinOpExpr = dyn_cast<AffineBinaryOpExpr>(rhs);
701 (rRhsConstExpr = dyn_cast<AffineConstantExpr>(rBinOpExpr.getRHS()))) {
702 rRhsConst = rRhsConstExpr.
getValue();
703 secondExpr = rBinOpExpr.getLHS();
709 if (rLhsConst && rRhsConst && firstExpr == secondExpr)
717 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
718 return lBin.getLHS() + rhs + lrhs;
731 auto lrhs = rBinOpExpr.getLHS();
732 auto rrhs = rBinOpExpr.getRHS();
738 auto lrhsBinOpExpr = dyn_cast<AffineBinaryOpExpr>(lrhs);
740 auto rrhsConstOpExpr = dyn_cast<AffineConstantExpr>(rrhs);
741 if (rrhsConstOpExpr && rrhsConstOpExpr.getValue() == -1 && lrhsBinOpExpr &&
744 llrhs = lrhsBinOpExpr.getLHS();
746 rlrhs = lrhsBinOpExpr.getRHS();
747 auto llrhsBinOpExpr = dyn_cast<AffineBinaryOpExpr>(llrhs);
750 if (llrhsBinOpExpr.getRHS() == rlrhs && lhs == llrhsBinOpExpr.getLHS())
761 llrhs = lrBinOpExpr.
getLHS();
762 rlrhs = lrBinOpExpr.
getRHS();
764 if (lhs == llrhs && rlrhs == -rrhs) {
784 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
785 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
787 if (lhsConst && rhsConst) {
789 if (llvm::MulOverflow(lhsConst.getValue(), rhsConst.getValue(),
product)) {
810 if (rhsConst.getValue() == 1)
813 if (rhsConst.getValue() == 0)
818 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
820 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS()))
821 return lBin.getLHS() * (lrhs.getValue() * rhsConst.getValue());
827 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
828 return (lBin.getLHS() * rhs) * lrhs;
855 return *
this + (-other);
859 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
860 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
862 if (!rhsConst || rhsConst.getValue() == 0)
866 if (divideSignedWouldOverflow(lhsConst.getValue(), rhsConst.getValue()))
869 divideFloorSigned(lhsConst.getValue(), rhsConst.getValue()),
880 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
882 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
884 if (lrhs.getValue() % rhsConst.getValue() == 0)
885 return lBin.getLHS() * (lrhs.getValue() / rhsConst.getValue());
892 int64_t llhsDiv = lBin.getLHS().getLargestKnownDivisor();
893 int64_t lrhsDiv = lBin.getRHS().getLargestKnownDivisor();
895 if (llhsDiv % rhsConst.getValue() == 0 ||
896 lrhsDiv % rhsConst.getValue() == 0)
897 return lBin.getLHS().floorDiv(rhsConst.getValue()) +
898 lBin.getRHS().floorDiv(rhsConst.getValue());
918 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
919 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
921 if (!rhsConst || rhsConst.getValue() == 0)
925 if (divideSignedWouldOverflow(lhsConst.getValue(), rhsConst.getValue()))
928 divideCeilSigned(lhsConst.getValue(), rhsConst.getValue()),
934 if (rhsConst.getValue() == 1)
939 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
941 if (
auto lrhs = dyn_cast<AffineConstantExpr>(lBin.getRHS())) {
943 if (lrhs.getValue() % rhsConst.getValue() == 0)
944 return lBin.getLHS() * (lrhs.getValue() / rhsConst.getValue());
965 auto lhsConst = dyn_cast<AffineConstantExpr>(lhs);
966 auto rhsConst = dyn_cast<AffineConstantExpr>(rhs);
969 if (!rhsConst || rhsConst.getValue() < 1)
986 auto lBin = dyn_cast<AffineBinaryOpExpr>(lhs);
988 int64_t llhsDiv = lBin.getLHS().getLargestKnownDivisor();
989 int64_t lrhsDiv = lBin.getRHS().getLargestKnownDivisor();
991 if (llhsDiv % rhsConst.getValue() == 0)
992 return lBin.getRHS() % rhsConst.getValue();
993 if (lrhsDiv % rhsConst.getValue() == 0)
994 return lBin.getLHS() % rhsConst.getValue();
999 auto intermediate = dyn_cast<AffineConstantExpr>(lBin.getRHS());
1000 if (intermediate && intermediate.getValue() >= 1 &&
1001 mod(intermediate.getValue(), rhsConst.getValue()) == 0) {
1002 return lBin.getLHS() % rhsConst.getValue();
1038 unsigned numSymbols,
1042 assert(flatExprs.size() - numDims - numSymbols - 1 == localExprs.size() &&
1043 "unexpected number of local expressions");
1047 for (
unsigned j = 0;
j < numDims + numSymbols;
j++) {
1048 if (flatExprs[
j] == 0)
1052 expr = expr +
id * flatExprs[
j];
1056 for (
unsigned j = numDims + numSymbols, e = flatExprs.size() - 1;
j < e;
1058 if (flatExprs[
j] == 0)
1060 auto term = localExprs[
j - numDims - numSymbols] * flatExprs[
j];
1065 int64_t constTerm = flatExprs[flatExprs.size() - 1];
1067 expr = expr + constTerm;
1081 unsigned numSymbols,
1084 assert(!flatExprs.empty() &&
"flatExprs cannot be empty");
1087 assert(flatExprs.size() - numDims - numSymbols - 1 == localExprs.size() &&
1088 "unexpected number of local expressions");
1120 auto addEntry = [&](std::pair<unsigned, signed> index, int64_t coefficient,
1122 assert(!llvm::is_contained(indices, index) &&
1123 "Key is already present in indices vector and overwriting will "
1124 "happen in `indexToExprMap` and `coefficients`!");
1126 indices.push_back(index);
1127 coefficients.insert({index, coefficient});
1128 indexToExprMap.insert({index, expr});
1136 unsigned offsetSym = 0;
1137 signed offsetDim = -1;
1138 for (
unsigned j = numDims;
j < numDims + numSymbols; ++
j) {
1139 if (flatExprs[
j] == 0)
1145 std::pair<unsigned, signed> indexEntry(
1146 j - numDims,
std::max(numDims, numSymbols) + offsetSym++);
1147 addEntry(indexEntry, flatExprs[
j],
1155 unsigned lhsPos, rhsPos;
1162 if (flatExprs[numDims + numSymbols + it.index()] == 0)
1164 AffineExpr lhs = cast<AffineBinaryOpExpr>(expr).getLHS();
1165 AffineExpr rhs = cast<AffineBinaryOpExpr>(expr).getRHS();
1166 if (!((isa<AffineDimExpr>(lhs) || isa<AffineSymbolExpr>(lhs)) &&
1167 (isa<AffineDimExpr>(rhs) || isa<AffineSymbolExpr>(rhs) ||
1168 isa<AffineConstantExpr>(rhs)))) {
1171 if (isa<AffineConstantExpr>(rhs)) {
1176 if (isa<AffineDimExpr>(lhs)) {
1177 lhsPos = cast<AffineDimExpr>(lhs).getPosition();
1178 std::pair<unsigned, signed> indexEntry(lhsPos, offsetDim--);
1179 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()],
1182 lhsPos = cast<AffineSymbolExpr>(lhs).getPosition();
1183 std::pair<unsigned, signed> indexEntry(
1184 lhsPos,
std::max(numDims, numSymbols) + offsetSym++);
1185 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()],
1188 }
else if (isa<AffineDimExpr>(lhs)) {
1194 lhsPos = cast<AffineDimExpr>(lhs).getPosition();
1195 rhsPos = cast<AffineSymbolExpr>(rhs).getPosition();
1196 std::pair<unsigned, signed> indexEntry(lhsPos, rhsPos);
1197 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()], expr);
1203 lhsPos = cast<AffineSymbolExpr>(lhs).getPosition();
1204 rhsPos = cast<AffineSymbolExpr>(rhs).getPosition();
1205 std::pair<unsigned, signed> indexEntry(
1206 lhsPos,
std::max(numDims, numSymbols) + offsetSym++);
1207 addEntry(indexEntry, flatExprs[numDims + numSymbols + it.index()], expr);
1209 addedToMap[it.index()] =
true;
1212 for (
unsigned j = 0;
j < numDims; ++
j) {
1213 if (flatExprs[
j] == 0)
1219 std::pair<unsigned, signed> indexEntry(
j, offsetDim--);
1226 llvm::sort(indices);
1227 for (
const std::pair<unsigned, unsigned> index : indices) {
1228 assert(indexToExprMap.lookup(index) &&
1229 "cannot find key in `indexToExprMap` map");
1230 expr = expr + indexToExprMap.lookup(index) * coefficients.lookup(index);
1234 for (
unsigned j = numDims + numSymbols, e = flatExprs.size() - 1;
j < e;
1238 if (flatExprs[
j] == 0 || addedToMap[
j - numDims - numSymbols])
1240 auto term = localExprs[
j - numDims - numSymbols] * flatExprs[
j];
1245 int64_t constTerm = flatExprs.back();
1247 expr = expr + constTerm;
1252 unsigned numSymbols)
1253 : numDims(numDims), numSymbols(numSymbols), numLocals(0) {
1271 if (!isa<AffineConstantExpr>(expr.
getRHS())) {
1278 return addLocalVariableSemiAffine(mulLhs, rhs, a * b, lhs, lhs.size());
1282 int64_t rhsConst = rhs[getConstantIndex()];
1283 for (int64_t &lhsElt : lhs)
1293 assert(lhs.size() == rhs.size());
1295 for (
unsigned i = 0, e = rhs.size(); i < e; i++) {
1324 if (!isa<AffineConstantExpr>(expr.
getRHS())) {
1330 AffineExpr modExpr = dividendExpr % divisorExpr;
1331 return addLocalVariableSemiAffine(modLhs, rhs, modExpr, lhs, lhs.size());
1334 int64_t rhsConst = rhs[getConstantIndex()];
1340 for (i = 0, e = lhs.size(); i < e; i++)
1341 if (lhs[i] % rhsConst != 0)
1344 if (i == lhs.size()) {
1345 std::fill(lhs.begin(), lhs.end(), 0);
1353 uint64_t gcd = rhsConst;
1354 for (int64_t lhsElt : lhs)
1355 gcd = std::gcd(gcd, (uint64_t)
std::abs(lhsElt));
1358 for (int64_t &floorDividendElt : floorDividend)
1359 floorDividendElt = floorDividendElt /
static_cast<int64_t
>(gcd);
1361 int64_t floorDivisor = rhsConst /
static_cast<int64_t
>(gcd);
1370 if ((loc = findLocalId(floorDivExpr)) == -1) {
1373 lhs[getLocalVarStartIndex() +
numLocals - 1] = -rhsConst;
1376 lhs[getLocalVarStartIndex() + loc] = -rhsConst;
1383 return visitDivExpr(expr,
true);
1387 return visitDivExpr(expr,
false);
1403 eq[getSymbolStartIndex() + expr.
getPosition()] = 1;
1411 eq[getConstantIndex()] = expr.
getValue();
1415 LogicalResult SimpleAffineExprFlattener::addLocalVariableSemiAffine(
1418 assert(result.size() == resultSize &&
1419 "`result` vector passed is not of correct size");
1421 if ((loc = findLocalId(localExpr)) == -1) {
1425 std::fill(result.begin(), result.end(), 0);
1427 result[getLocalVarStartIndex() +
numLocals - 1] = 1;
1429 result[getLocalVarStartIndex() + loc] = 1;
1458 if (!isa<AffineConstantExpr>(expr.
getRHS())) {
1465 return addLocalVariableSemiAffine(divLhs, rhs, divExpr, lhs, lhs.size());
1469 int64_t rhsConst = rhs[getConstantIndex()];
1476 for (int64_t lhsElt : lhs)
1477 gcd = std::gcd(gcd, (uint64_t)
std::abs(lhsElt));
1480 for (int64_t &lhsElt : lhs)
1481 lhsElt = lhsElt /
static_cast<int64_t
>(gcd);
1483 int64_t divisor = rhsConst /
static_cast<int64_t
>(gcd);
1499 if ((loc = findLocalId(divExpr)) == -1) {
1506 dividend.back() += divisor - 1;
1512 std::fill(lhs.begin(), lhs.end(), 0);
1514 lhs[getLocalVarStartIndex() +
numLocals - 1] = 1;
1516 lhs[getLocalVarStartIndex() + loc] = 1;
1528 assert(divisor > 0 &&
"positive constant divisor expected");
1530 subExpr.insert(subExpr.begin() + getLocalVarStartIndex() +
numLocals, 0);
1539 subExpr.insert(subExpr.begin() + getLocalVarStartIndex() +
numLocals, 0);
1546 int SimpleAffineExprFlattener::findLocalId(
AffineExpr localExpr) {
1555 unsigned numSymbols) {
1580 return simplifiedExpr;
1584 AffineExpr expr,
unsigned numDims,
unsigned numSymbols,
1585 ArrayRef<std::optional<int64_t>> constLowerBounds,
1586 ArrayRef<std::optional<int64_t>> constUpperBounds,
bool isUpper) {
1588 if (
auto binOpExpr = dyn_cast<AffineBinaryOpExpr>(expr)) {
1592 auto rhsConst = dyn_cast<AffineConstantExpr>(binOpExpr.getRHS());
1593 if (!rhsConst || rhsConst.getValue() < 1)
1594 return std::nullopt;
1597 constLowerBounds, constUpperBounds, isUpper);
1599 return std::nullopt;
1600 return divideFloorSigned(*bound, rhsConst.getValue());
1603 auto rhsConst = dyn_cast<AffineConstantExpr>(binOpExpr.getRHS());
1604 if (rhsConst && rhsConst.getValue() >= 1) {
1607 constLowerBounds, constUpperBounds, isUpper);
1609 return std::nullopt;
1610 return divideCeilSigned(*bound, rhsConst.getValue());
1612 return std::nullopt;
1618 auto rhsConst = dyn_cast<AffineConstantExpr>(binOpExpr.getRHS());
1619 if (rhsConst && rhsConst.getValue() >= 1) {
1620 int64_t rhsConstVal = rhsConst.getValue();
1622 constLowerBounds, constUpperBounds,
1626 constLowerBounds, constUpperBounds, isUpper);
1628 divideFloorSigned(*lb, rhsConstVal) ==
1629 divideFloorSigned(*ub, rhsConstVal))
1630 return isUpper ? mod(*ub, rhsConstVal) : mod(*lb, rhsConstVal);
1631 return isUpper ? rhsConstVal - 1 : 0;
1639 if (failed(simpleResult))
1640 return std::nullopt;
1645 return std::nullopt;
1649 for (
unsigned i = 0, e = numDims + numSymbols; i < e; ++i) {
1650 if (flattenedExpr[i] > 0) {
1651 auto &constBound = isUpper ? constUpperBounds[i] : constLowerBounds[i];
1653 return std::nullopt;
1654 bound += *constBound * flattenedExpr[i];
1655 }
else if (flattenedExpr[i] < 0) {
1656 auto &constBound = isUpper ? constLowerBounds[i] : constUpperBounds[i];
1658 return std::nullopt;
1659 bound += *constBound * flattenedExpr[i];
1663 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 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 void getSummandExprs(AffineExpr expr, SmallVector< AffineExpr > &result)
Populate result with all summand operands of given (potentially nested) addition.
static bool isDivisibleBySymbol(AffineExpr expr, unsigned symbolPos, AffineExprKind opKind)
Returns true if the expression is divisible by the given symbol with position symbolPos.
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)
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.