Introduce hyper-rectangular sets for analysis.
- introduce hyper-rectangular set representation and API sketch for
analysis/code generation
- implement the 'intersect' and 'project out' operations.
The represention is lighter weight, and operations and other queries on it are
much faster on such domains when compared to general polyhedral domains.
PiperOrigin-RevId: 210245882
diff --git a/lib/Analysis/AffineStructures.cpp b/lib/Analysis/AffineStructures.cpp
index 295c76a..782257e 100644
--- a/lib/Analysis/AffineStructures.cpp
+++ b/lib/Analysis/AffineStructures.cpp
@@ -40,13 +40,17 @@
// TODO(bondhugula)
}
+// Universal set.
+MutableIntegerSet::MutableIntegerSet(unsigned numDims, unsigned numSymbols)
+ : numDims(numDims), numSymbols(numSymbols) {}
+
AffineValueMap::AffineValueMap(const AffineApplyOp &op)
: map(op.getAffineMap()) {
// TODO: pull operands and results in.
}
bool AffineValueMap::isMultipleOf(unsigned idx, int64_t factor) const {
- /* Check if the (first result expr) % factor becomes 0. */
+ // Check if the (first result expr) % factor becomes 0.
if (auto *expr = dyn_cast<AffineConstantExpr>(AffineBinaryOpExpr::get(
AffineExpr::Kind::Mod, map.getResult(idx),
AffineConstantExpr::get(factor, context), context)))
@@ -54,6 +58,7 @@
// TODO(bondhugula): use FlatAffineConstraints to complete this.
assert(0 && "isMultipleOf implementation incomplete");
+ return false;
}
AffineValueMap::~AffineValueMap() {}
diff --git a/lib/Analysis/HyperRectangularSet.cpp b/lib/Analysis/HyperRectangularSet.cpp
new file mode 100644
index 0000000..1a06515
--- /dev/null
+++ b/lib/Analysis/HyperRectangularSet.cpp
@@ -0,0 +1,200 @@
+//===- HyperRectangularSet.cpp - MLIR HyperRectangularSet Class--*- C++ -*-===//
+//
+// Copyright 2019 The MLIR Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+// =============================================================================
+//
+// Structures for affine/polyhedral analysis of MLIR functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Analysis/HyperRectangularSet.h"
+
+#include <algorithm>
+
+#include "mlir/IR/AffineExpr.h"
+#include "mlir/IR/IntegerSet.h"
+#include "llvm/Support/raw_ostream.h"
+
+using namespace mlir;
+
+// TODO(bondhugula): clean this code up.
+// Get the constant bound that is either the min or max (depending on 'cmp').
+static Optional<int64_t>
+getReducedConstBound(const HyperRectangularSet &set, unsigned *idx,
+ std::function<bool(int64_t, int64_t)> const &cmp) {
+ Optional<int64_t> val = None;
+
+ for (unsigned i = 0, n = set.getNumDims(); i < n; i++) {
+ auto &ubs = set.getLowerBound(i);
+ unsigned j = 0;
+ AffineBoundExprList::const_iterator it, e;
+ for (it = ubs.begin(), e = ubs.end(); it != e; it++, j++) {
+ if (auto *cExpr = dyn_cast<AffineConstantExpr>(*it)) {
+ if (val == None) {
+ val = cExpr->getValue();
+ *idx = j;
+ } else if (cmp(cExpr->getValue(), val.getValue())) {
+ val = cExpr->getValue();
+ *idx = j;
+ }
+ }
+ }
+ }
+ return val;
+}
+
+// Merge the two lists of AffineExpr's into a single one, avoiding duplicates.
+// lb specifies whether the bound lists are for a lower bound or an upper bound.
+// TODO(bondhugula): clean this code up.
+static void mergeBounds(const HyperRectangularSet &set,
+ AffineBoundExprList &lhsList,
+ const AffineBoundExprList &rhsList, bool lb) {
+ // The list of bounds is going to be small. Just a linear search
+ // should be enough to create a list without duplicates.
+ for (auto *expr : rhsList) {
+ AffineBoundExprList::const_iterator it;
+ for (it = lhsList.begin(); it != lhsList.end(); it++) {
+ if (expr == *it)
+ break;
+ }
+ if (it == lhsList.end()) {
+ // There can only be one constant affine expr in this bound list.
+ if (auto *cExpr = dyn_cast<AffineConstantExpr>(expr)) {
+ unsigned idx;
+ if (lb) {
+ auto cb = getReducedConstBound(
+ set, &idx,
+ [](int64_t newVal, int64_t oldVal) { return newVal < oldVal; });
+ if (!cb.hasValue()) {
+ lhsList.push_back(expr);
+ continue;
+ }
+ if (cExpr->getValue() < cb)
+ lhsList[idx] = expr;
+ // A constant value >= the existing bound constant.
+ continue;
+ }
+ // Upper bound case.
+ auto cb =
+ getReducedConstBound(set, &idx, [](int64_t newVal, int64_t oldVal) {
+ return newVal > oldVal;
+ });
+ if (!cb.hasValue()) {
+ lhsList.push_back(expr);
+ continue;
+ }
+ if (cExpr->getValue() > cb)
+ lhsList[idx] = expr;
+ continue;
+ }
+ // Not a constant expression; push it.
+ // TODO(bondhugula): check if this was implied by an existing symbolic
+ // expression or by the context.
+ lhsList.push_back(expr);
+ }
+ }
+}
+
+HyperRectangularSet::HyperRectangularSet(unsigned numDims, unsigned numSymbols,
+ ArrayRef<ArrayRef<AffineExpr *>> lbs,
+ ArrayRef<ArrayRef<AffineExpr *>> ubs,
+ IntegerSet *symbolContext)
+ : context(symbolContext ? MutableIntegerSet(symbolContext)
+ : MutableIntegerSet(numDims, numSymbols)) {
+ unsigned d = 0;
+ for (auto boundList : lbs) {
+ AffineBoundExprList lb;
+ for (auto *expr : boundList) {
+ assert(expr->isSymbolicOrConstant() &&
+ "bound expression should be symbolic or constant");
+ lb.push_back(expr);
+ }
+ mergeBounds(*this, lowerBounds[d++], lb, true);
+ }
+
+ d = 0;
+ for (auto boundList : ubs) {
+ AffineBoundExprList ub;
+ for (auto *expr : boundList) {
+ assert(expr->isSymbolicOrConstant() &&
+ "bound expression should be symbolic or constant");
+ ub.push_back(expr);
+ }
+ mergeBounds(*this, upperBounds[d++], ub, false);
+ }
+
+ simplifyUnderContext();
+}
+
+void HyperRectangularSet::projectOut(unsigned idx, unsigned num) {
+ // Erase the bounds along the projected out dimensions.
+ lowerBounds.erase(lowerBounds.begin() + idx, lowerBounds.begin() + idx + num);
+ upperBounds.erase(upperBounds.begin() + idx, upperBounds.begin() + idx + num);
+ numDims -= num;
+}
+
+void HyperRectangularSet::intersect(const HyperRectangularSet &rhs) {
+ assert(rhs.getNumSymbols() == getNumSymbols() &&
+ rhs.getNumDims() == getNumDims() && "operand space does not match");
+
+ // Intersection is just a concatenation of distinct bounds.
+ for (unsigned i = 0, n = getNumDims(); i < n; i++) {
+ mergeBounds(*this, getLowerBound(i), rhs.getLowerBound(i), true);
+ mergeBounds(*this, getUpperBound(i), rhs.getUpperBound(i), false);
+ }
+}
+
+void HyperRectangularSet::print(raw_ostream &os) const {
+ os << "Hyper rectangular set: " << numDims << "dimensions, " << numSymbols
+ << "symbols\n";
+ os << "Lower bounds\n";
+ unsigned d = 0;
+ for (auto &lb : lowerBounds) {
+ os << "Dim " << d++ << "\n";
+ for (auto *expr : lb) {
+ expr->print(os);
+ }
+ }
+ d = 0;
+ os << "Upper bounds\n";
+ for (auto &lb : upperBounds) {
+ os << "Dim " << d++ << "\n";
+ for (auto *expr : lb) {
+ expr->print(os);
+ }
+ }
+}
+
+void HyperRectangleList::projectOut(unsigned idx, unsigned num) {
+ for (auto &elt : hyperRectangles) {
+ elt.projectOut(idx, num);
+ }
+ // TODO: after a project out, some of the sets may be identical. Remove those.
+}
+
+bool HyperRectangleList::empty() const {
+ for (auto &set : hyperRectangles) {
+ if (!set.empty())
+ return false;
+ }
+ return true;
+}
+
+bool HyperRectangularSet::empty() const {
+ assert(0 && "unimplemented");
+ return false;
+}
+
+void HyperRectangularSet::dump() const { print(llvm::errs()); }