[MLIR][Presburger] use arbitrary-precision arithmetic with MPInt instead of int64_t

[arjunp]

Summary

Only the main Presburger library under the Presburger directory has been switched to use arbitrary precision. Users have been changed to just cast returned values back to int64_t or to use newly added convenience functions that perform the same cast internally.

The performance impact of this has been tested by checking test runtimes after copy-pasting 100 copies of each function. Affine/simplify-structures.mlir goes from 0.76s to 0.80s after this patch. Its performance sees no regression compared to its original performance at commit 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc before a series of patches that I landed to offset the performance overhead of switching to arbitrary precision.

Affine/canonicalize.mlir and SCF/canonicalize.mlir show no noticable difference, staying at 2.02s and about 2.35s respectively.

Also, for Affine and SCF tests as a whole (no copy-pasting), the runtime remains about 0.09s on average before and after.

[Groverkss]

For classes other than IntegerRelation, I don't think the public API should have int64_t methods. They should be MPInt only. Can you please change this?

[arjunp]

• address kunwar's comment

[arjunp]

In D129510#3648445, @Groverkss wrote:

For classes other than IntegerRelation, I don't think the public API should have int64_t methods. They should be MPInt only. Can you please change this?

It makes sense for Fraction to have these since it's useful for constructing it out of literals. I also retained the one in PresburgerRelation and Utils since they're also user-facing like IntegerRelation.

Removed the ones in Simplex.

[arjunp]

Rebase.

[arjunp]

Format.

[Groverkss]

Could you add some int64_t overflow tests for major algorithms like point sampling, lexmin, subtraction, etc.?

mlir/include/mlir/Analysis/Presburger/Utils.h

175

This introduces some unintended behaviour here. We always assume that the denominators are positive. Making them MPInt instead of unsigned allows negative values also now. Similar comments for all changes of integers holding denominators from unsigned to MPInt.

mlir/lib/Analysis/Presburger/Simplex.cpp

25

Shouldn't the scale also be MPInt?

[arjunp]

Address the inline comments; test cases to be added soon

[arjunp]

mlir/include/mlir/Analysis/Presburger/Utils.h

175

Added documentation and asserts that the denominators are positive (or non-negative, when representations may not exist)

[ftynse]

This looks pretty mechanical. Before we proceed, I would suggest taking some passes / pass pipelines that are affected by this (affine/scf dialect canonicalization, affine transformation passes), measuring the effect on the compilation time and reporting it in the commit message. Most tests are too small to notice effects on the compile time, but it is possible to replicate the same function 10k times with different names and thus increase the runtime of the pass to allow for more stable measurement.

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

195

Any reason to specify the stack size here?

mlir/include/mlir/Analysis/Presburger/Simplex.h

187–188

Something wrong happened with the comment.

mlir/include/mlir/Analysis/Presburger/Utils.h

207–209

Cant we drop 8 here and in all the other places?

[bondhugula]

In D129510#3665422, @ftynse wrote:

This looks pretty mechanical. Before we proceed, I would suggest taking some passes / pass pipelines that are affected by this (affine/scf dialect canonicalization, affine transformation passes), measuring the effect on the compilation time and reporting it in the commit message. Most tests are too small to notice effects on the compile time, but it is possible to replicate the same function 10k times with different names and thus increase the runtime of the pass to allow for more stable measurement.

I too strongly recommend this exercise. The commit summary should be expanded to describe the change and its impact.

[arjunp]

Rebase.

[arjunp]

Updated the summary with some performance statistics.

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

195

We uniformly use 8-element stack sizes because this is the ~70th percentile of dimensionality in our benchmark. For int64_t, I think the default is 8 anyway, but for MPInt it wouldn't be, and I believe that it makes sense to not make incur allocations on too high a fraction of the sets.

This could be worth discussing further but I would prefer to keep the current patch as a single mostly mechanical change. If we decide to change the stack size, I think that would be better suited for a different patch.

mlir/include/mlir/Analysis/Presburger/Simplex.h

187–188

I am not sure what you mean. The comment seems correct to me.

[arjunp]

Add test case to test emptiness checks and integer lexmin.

[arjunp]

Rebase to fix build.

[arjunp]

Slightly improve test.

[arjunp]

@ftynse @bondhugula do you have any further comments on this patch? :)

[bondhugula]

Can you better capture in the commit summary what the changes are and the rationale?

Reg. the increase from 0.76s to 0.80s for simplify-affine-structures, I'm trying to under why there is an impact at all? Is the slowdown reproducible or an error in measurement? (If the run was multithreaded, consider timing with -mlir-disable-threading to get more reproducible runs.)

[bondhugula]

Sorry about the delay here. I'll be quick to respond on the remaining discussion.

[arjunp]

In D129510#3738533, @bondhugula wrote:

Can you better capture in the commit summary what the changes are and the rationale?

Reg. the increase from 0.76s to 0.80s for simplify-affine-structures, I'm trying to under why there is an impact at all? Is the slowdown reproducible or an error in measurement? (If the run was multithreaded, consider timing with -mlir-disable-threading to get more reproducible runs.)

There is an impact associated with switching from plain unsafe int64_ts. For example, after this patch whenever we perform integer operations, we check whether overflow occurs and, if it does, switch to arbitrary precision. This adds some overhead.

[bondhugula]

In D129510#3739392, @arjunp wrote:

In D129510#3738533, @bondhugula wrote:

Can you better capture in the commit summary what the changes are and the rationale?

Reg. the increase from 0.76s to 0.80s for simplify-affine-structures, I'm trying to under why there is an impact at all? Is the slowdown reproducible or an error in measurement? (If the run was multithreaded, consider timing with -mlir-disable-threading to get more reproducible runs.)

There is an impact associated with switching from plain unsafe int64_ts. For example, after this patch whenever we perform integer operations, we check whether overflow occurs and, if it does, switch to arbitrary precision. This adds some overhead.

Right - I'm trying to understand/recall which part of simplify-affine-structures is using the Presburger library.

[arjunp]

I spent quite a bit of time performance tuning this implementation. Also, I tuned the rest of the library a little bit more to offset some of the impact. But there is some non-zero impact in going from the unsafe 64-bit to overflow-checked arithmetic with fallback to arbitrary precision.

I just ran it five times with mlir-opt and the flag as you said and saw the same difference in runtime. 0.32s vs 0.36s. (The other runtime is more because I was running the whole test then -- including filecheck)

[arjunp]

In D129510#3739404, @bondhugula wrote:

In D129510#3739392, @arjunp wrote:

In D129510#3738533, @bondhugula wrote:

Can you better capture in the commit summary what the changes are and the rationale?

Reg. the increase from 0.76s to 0.80s for simplify-affine-structures, I'm trying to under why there is an impact at all? Is the slowdown reproducible or an error in measurement? (If the run was multithreaded, consider timing with -mlir-disable-threading to get more reproducible runs.)

There is an impact associated with switching from plain unsafe int64_ts. For example, after this patch whenever we perform integer operations, we check whether overflow occurs and, if it does, switch to arbitrary precision. This adds some overhead.

Right - I'm trying to understand/recall which part of simplify-affine-structures is using the Presburger library.

Sorry, didn't see this earlier because I didn't refresh my browser.

I see that SimplifyAffineStructures.cpp calls through to simplifyIntegerSet in mlir/lib/Dialect/Affine/Analysis/Utils.cpp, in turn calling to IntegerRelation::removeTrivialRedundancy

[bondhugula]

In D129510#3739477, @arjunp wrote:

In D129510#3739404, @bondhugula wrote:

In D129510#3739392, @arjunp wrote:

In D129510#3738533, @bondhugula wrote:

Can you better capture in the commit summary what the changes are and the rationale?

Reg. the increase from 0.76s to 0.80s for simplify-affine-structures, I'm trying to under why there is an impact at all? Is the slowdown reproducible or an error in measurement? (If the run was multithreaded, consider timing with -mlir-disable-threading to get more reproducible runs.)

There is an impact associated with switching from plain unsafe int64_ts. For example, after this patch whenever we perform integer operations, we check whether overflow occurs and, if it does, switch to arbitrary precision. This adds some overhead.

Right - I'm trying to understand/recall which part of simplify-affine-structures is using the Presburger library.

Sorry, didn't see this earlier because I didn't refresh my browser.

I see that SimplifyAffineStructures.cpp calls through to simplifyIntegerSet in mlir/lib/Dialect/Affine/Analysis/Utils.cpp, in turn calling to IntegerRelation::removeTrivialRedundancy

Thanks for digging into this. removeTrivialRedundancy is expected to only perform really trivial checks -- I just verified, and it doesn't (and shouldn't) depend on the Presburger library. So your changes here should have nil impact on -simplify-affine-structures. I now looked at changes above again, and you've modified removeTrivialRedundancy to use MPInt (switched from int64) although this method doesn't in any way depend on the Presburger library. I'm pretty sure the change causes a significant impact on that method alone (which is reflecting as a small overall slowdown on the pass that exercises many things). Do we need MPInt for removeTrivialRedundancy? (It only does divisions and normalization.) I'm concerned by this impact to a trivial method that is used on several paths where speed is deserved. Should we be templating the method to allow MPInt and int64 (have both versions) and use the latter almost everywhere?

The above impact also goes against the commit summary that only the Presburger library has been changed -- the change to removeTrivialRedundancy impacts things in affine analysis completely unrelated to and non-dependent on the Presburger library.

[arjunp]

Thanks for digging into this. removeTrivialRedundancy is expected to only perform really trivial checks -- I just verified, and it doesn't (and shouldn't) depend on the Presburger library. So your changes here should have nil impact on -simplify-affine-structures. I now looked at changes above again, and you've modified removeTrivialRedundancy to use MPInt (switched from int64) although this method doesn't in any way depend on the Presburger library. I'm pretty sure the change causes a significant impact on that method alone (which is reflecting as a small overall slowdown on the pass that exercises many things). Do we need MPInt for removeTrivialRedundancy? (It only does divisions and normalization.) I'm concerned by this impact to a trivial method that is used on several paths where speed is deserved. Should we be templating the method to allow MPInt and int64 (have both versions) and use the latter almost everywhere?

The above impact also goes against the commit summary that only the Presburger library has been changed -- the change to removeTrivialRedundancy impacts things in affine analysis completely unrelated to and non-dependent on the Presburger library.

I went back and checked, and the performance tuning I did to offset the overhead of this change seems to have been sufficient. I just did a median of five and it seems to take around 0.80-0.81s on both arbitrary precision with this patch, and the original performance before I started this work (at commit 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc). I will update the summary accordingly.

Converting this one function alone does not really make much sense to me. It's true that this one function would not need MPInt, but in general it is necessary to store the data as MPInts. For example, the results of fourier-motzkin elimination, such as in IntegerRelation::projectOut, can have arbitrarily large integers in the result. So if we wrote a templated version of this removeTrivialRedundancy, it would still have to convert the data to int64_t and then operate on that. I'm not sure that this would improve the performance by much.

When I wrote "Presburger library", I was referring to classes and files under the Presburger directory, including IntegerRelation and its member function removeTrivialRedundancy. When I wrote that only the Presburger directory has been changed, I meant that I have only fixed the correctness issues inside the Presburger directory and that the stuff outside it is still affected by overflow bugs. I was not referring to changes in performance. Sorry if this was unclear. I will update the summary.

[bondhugula]

In D129510#3743283, @arjunp wrote:

Thanks for clarifying. This part from the commit summary still seems confusing to me - trying to understand this better. Did 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc improve perf of this pass from 0.80s to 0.76s? But at 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc, I assume simplify-affine-structures didn't use any MPInt based stuff (or did it) in which case 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc shouldn't have impacted it?

The performance impact of this has been tested by checking test runtimes after copy-pasting 100 copies of each function. Affine/simplify-structures.mlir goes from 0.76s to 0.80s after this patch. Its performance sees no regression compared to its original performance at commit 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc before a series of patches that I landed to offset the performance overhead of switching to arbitrary precision.

[arjunp]

In D129510#3776097, @bondhugula wrote:

In D129510#3743283, @arjunp wrote:

Thanks for clarifying. This part from the commit summary still seems confusing to me - trying to understand this better. Did 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc improve perf of this pass from 0.80s to 0.76s? But at 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc, I assume simplify-affine-structures didn't use any MPInt based stuff (or did it) in which case 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc shouldn't have impacted it?

The performance impact of this has been tested by checking test runtimes after copy-pasting 100 copies of each function. Affine/simplify-structures.mlir goes from 0.76s to 0.80s after this patch. Its performance sees no regression compared to its original performance at commit 18a06d4f3a7474d062d1fe7d405813ed2e40b4fc before a series of patches that I landed to offset the performance overhead of switching to arbitrary precision.

Yes, it does use some stuff that I tuned. For example, it uses Matrix. Matrix was a big performance bottleneck with MPInt in my initial prototype, so I did some tuning on it. This reduced the performance gap between MPInt and int64, but it also improved the int64 version as compared to the version without the Matrix tuning.

[bondhugula]

LGTM

[arjunp]

Rebase.

[arjunp]

Uday, Alex, Kunwar, thanks for your reviews!

mlir/include/mlir/Analysis/Presburger/Fraction.h

 //===- Fraction.h - MLIR Fraction Class -------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is a simple class to represent fractions. It supports multiplication,
 // comparison, floor, and ceiling operations.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_FRACTION_H
 #define MLIR_ANALYSIS_PRESBURGER_FRACTION_H
 
+#include "mlir/Analysis/Presburger/MPInt.h"
 #include "mlir/Support/MathExtras.h"
 
 namespace mlir {
 namespace presburger {
 
 /// A class to represent fractions. The sign of the fraction is represented
 /// in the sign of the numerator; the denominator is always positive.
 ///
 /// Note that overflows may occur if the numerator or denominator are not
 /// representable by 64-bit integers.
 struct Fraction {
   /// Default constructor initializes the represented rational number to zero.
   Fraction() = default;
 
   /// Construct a Fraction from a numerator and denominator.
-  Fraction(int64_t oNum, int64_t oDen) : num(oNum), den(oDen) {
+  Fraction(const MPInt &oNum, const MPInt &oDen) : num(oNum), den(oDen) {
     if (den < 0) {
       num = -num;
       den = -den;
     }
   }
+  /// Overloads for passing literals.
+  Fraction(const MPInt &num, int64_t den) : Fraction(num, MPInt(den)) {}
+  Fraction(int64_t num, const MPInt &den) : Fraction(MPInt(num), den) {}
+  Fraction(int64_t num, int64_t den) : Fraction(MPInt(num), MPInt(den)) {}
 
   // Return the value of the fraction as an integer. This should only be called
   // when the fraction's value is really an integer.
-  int64_t getAsInteger() const {
+  MPInt getAsInteger() const {
     assert(num % den == 0 && "Get as integer called on non-integral fraction!");
     return num / den;
   }
 
   /// The numerator and denominator, respectively. The denominator is always
   /// positive.
-  int64_t num{0}, den{1};
+  MPInt num{0}, den{1};
 };
 
 /// Three-way comparison between two fractions.
 /// Returns +1, 0, and -1 if the first fraction is greater than, equal to, or
 /// less than the second fraction, respectively.
-inline int compare(Fraction x, Fraction y) {
-  int64_t diff = x.num * y.den - y.num * x.den;
+inline int compare(const Fraction &x, const Fraction &y) {
+  MPInt diff = x.num * y.den - y.num * x.den;
   if (diff > 0)
     return +1;
   if (diff < 0)
     return -1;
   return 0;
 }
 
-inline int64_t floor(Fraction f) { return floorDiv(f.num, f.den); }
+inline MPInt floor(const Fraction &f) { return floorDiv(f.num, f.den); }
 
-inline int64_t ceil(Fraction f) { return ceilDiv(f.num, f.den); }
+inline MPInt ceil(const Fraction &f) { return ceilDiv(f.num, f.den); }
 
-inline Fraction operator-(Fraction x) { return Fraction(-x.num, x.den); }
+inline Fraction operator-(const Fraction &x) { return Fraction(-x.num, x.den); }
 
-inline bool operator<(Fraction x, Fraction y) { return compare(x, y) < 0; }
+inline bool operator<(const Fraction &x, const Fraction &y) {
+  return compare(x, y) < 0;
+}
 
-inline bool operator<=(Fraction x, Fraction y) { return compare(x, y) <= 0; }
+inline bool operator<=(const Fraction &x, const Fraction &y) {
+  return compare(x, y) <= 0;
+}
 
-inline bool operator==(Fraction x, Fraction y) { return compare(x, y) == 0; }
+inline bool operator==(const Fraction &x, const Fraction &y) {
+  return compare(x, y) == 0;
+}
 
-inline bool operator!=(Fraction x, Fraction y) { return compare(x, y) != 0; }
+inline bool operator!=(const Fraction &x, const Fraction &y) {
+  return compare(x, y) != 0;
+}
 
-inline bool operator>(Fraction x, Fraction y) { return compare(x, y) > 0; }
+inline bool operator>(const Fraction &x, const Fraction &y) {
+  return compare(x, y) > 0;
+}
 
-inline bool operator>=(Fraction x, Fraction y) { return compare(x, y) >= 0; }
+inline bool operator>=(const Fraction &x, const Fraction &y) {
+  return compare(x, y) >= 0;
+}
 
-inline Fraction operator*(Fraction x, Fraction y) {
+inline Fraction operator*(const Fraction &x, const Fraction &y) {
   return Fraction(x.num * y.num, x.den * y.den);
 }
 
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_FRACTION_H

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

public:
   bool isEqual(const IntegerRelation &other) const;
 
   /// Return whether this is a subset of the given IntegerRelation. This is
   /// integer-exact and somewhat expensive, since it uses the integer emptiness
   /// check (see IntegerRelation::findIntegerSample()).
   bool isSubsetOf(const IntegerRelation &other) const;
 
   /// Returns the value at the specified equality row and column.
-  inline int64_t atEq(unsigned i, unsigned j) const { return equalities(i, j); }
-  inline int64_t &atEq(unsigned i, unsigned j) { return equalities(i, j); }
+  inline MPInt atEq(unsigned i, unsigned j) const { return equalities(i, j); }
+  /// The same, but casts to int64_t. This is unsafe and will assert-fail if the
+  /// value does not fit in an int64_t.
+  inline int64_t atEq64(unsigned i, unsigned j) const {
+    return int64_t(equalities(i, j));
+  }
+  inline MPInt &atEq(unsigned i, unsigned j) { return equalities(i, j); }
 
   /// Returns the value at the specified inequality row and column.
-  inline int64_t atIneq(unsigned i, unsigned j) const {
+  inline MPInt atIneq(unsigned i, unsigned j) const {
     return inequalities(i, j);
   }
-  inline int64_t &atIneq(unsigned i, unsigned j) { return inequalities(i, j); }
+  /// The same, but casts to int64_t. This is unsafe and will assert-fail if the
+  /// value does not fit in an int64_t.
+  inline int64_t atIneq64(unsigned i, unsigned j) const {
+    return int64_t(inequalities(i, j));
+  }
+  inline MPInt &atIneq(unsigned i, unsigned j) { return inequalities(i, j); }
 
   unsigned getNumConstraints() const {
     return getNumInequalities() + getNumEqualities();
   }
 
   unsigned getNumDomainVars() const { return space.getNumDomainVars(); }
   unsigned getNumRangeVars() const { return space.getNumRangeVars(); }
   unsigned getNumSymbolVars() const { return space.getNumSymbolVars(); }
public:
   inline unsigned getNumReservedEqualities() const {
     return equalities.getNumReservedRows();
   }
 
   inline unsigned getNumReservedInequalities() const {
     return inequalities.getNumReservedRows();
   }
 
-  inline ArrayRef<int64_t> getEquality(unsigned idx) const {
+  inline ArrayRef<MPInt> getEquality(unsigned idx) const {
     return equalities.getRow(idx);
   }
-
-  inline ArrayRef<int64_t> getInequality(unsigned idx) const {
+  inline ArrayRef<MPInt> getInequality(unsigned idx) const {
     return inequalities.getRow(idx);
   }
+  /// The same, but casts to int64_t. This is unsafe and will assert-fail if the
+  /// value does not fit in an int64_t.
+  inline SmallVector<int64_t, 8> getEquality64(unsigned idx) const {
+    return getInt64Vec(equalities.getRow(idx));
+  }
+  inline SmallVector<int64_t, 8> getInequality64(unsigned idx) const {
+    return getInt64Vec(inequalities.getRow(idx));
+  }
 
   /// Get the number of vars of the specified kind.
   unsigned getNumVarKind(VarKind kind) const {
     return space.getNumVarKind(kind);
   };
 
   /// Return the index at which the specified kind of vars starts.
   unsigned getVarKindOffset(VarKind kind) const {
public:
 
   /// Append `num` variables of the specified kind after the last variable.
   /// of that kind. Return the position of the first appended column relative to
   /// the kind of variable. The coefficient columns corresponding to the added
   /// variables are initialized to zero.
   unsigned appendVar(VarKind kind, unsigned num = 1);
 
   /// Adds an inequality (>= 0) from the coefficients specified in `inEq`.
-  void addInequality(ArrayRef<int64_t> inEq);
+  void addInequality(ArrayRef<MPInt> inEq);
+  void addInequality(ArrayRef<int64_t> inEq) {
+    addInequality(getMPIntVec(inEq));
+  }
   /// Adds an equality from the coefficients specified in `eq`.
-  void addEquality(ArrayRef<int64_t> eq);
+  void addEquality(ArrayRef<MPInt> eq);
+  void addEquality(ArrayRef<int64_t> eq) { addEquality(getMPIntVec(eq)); }
 
   /// Eliminate the `posB^th` local variable, replacing every instance of it
   /// with the `posA^th` local variable. This should be used when the two
   /// local variables are known to always take the same values.
   virtual void eliminateRedundantLocalVar(unsigned posA, unsigned posB);
 
   /// Removes variables of the specified kind with the specified pos (or
   /// within the specified range) from the system. The specified location is
public:
   /// assert-failure. Note that Domain is minimized first, then range.
   MaybeOptimum<SmallVector<Fraction, 8>> findRationalLexMin() const;
 
   /// Same as above, but returns lexicographically minimal integer point.
   /// Note: this should be used only when the lexmin is really required.
   /// For a generic integer sampling operation, findIntegerSample is more
   /// robust and should be preferred. Note that Domain is minimized first, then
   /// range.
-  MaybeOptimum<SmallVector<int64_t, 8>> findIntegerLexMin() const;
+  MaybeOptimum<SmallVector<MPInt, 8>> findIntegerLexMin() const;
 
   /// Swap the posA^th variable with the posB^th variable.
   virtual void swapVar(unsigned posA, unsigned posB);
 
   /// Removes all equalities and inequalities.
   void clearConstraints();
 
   /// Sets the `values.size()` variables starting at `po`s to the specified
   /// values and removes them.
-  void setAndEliminate(unsigned pos, ArrayRef<int64_t> values);
+  void setAndEliminate(unsigned pos, ArrayRef<MPInt> values);
+  void setAndEliminate(unsigned pos, ArrayRef<int64_t> values) {
+    setAndEliminate(pos, getMPIntVec(values));
+  }
 
   /// Replaces the contents of this IntegerRelation with `other`.
   virtual void clearAndCopyFrom(const IntegerRelation &other);
 
   /// Gather positions of all lower and upper bounds of the variable at `pos`,
   /// and optionally any equalities on it. In addition, the bounds are to be
   /// independent of variables in position range [`offset`, `offset` + `num`).
   void
public:
   Matrix getBoundedDirections() const;
 
   /// Find an integer sample point satisfying the constraints using a
   /// branch and bound algorithm with generalized basis reduction, with some
   /// additional processing using Simplex for unbounded sets.
   ///
   /// Returns an integer sample point if one exists, or an empty Optional
   /// otherwise.
-  Optional<SmallVector<int64_t, 8>> findIntegerSample() const;
+  Optional<SmallVector<MPInt, 8>> findIntegerSample() const;
 
   /// Compute an overapproximation of the number of integer points in the
   /// relation. Symbol vars currently not supported. If the computed
   /// overapproximation is infinite, an empty optional is returned.
-  Optional<uint64_t> computeVolume() const;
+  Optional<MPInt> computeVolume() const;
 
   /// Returns true if the given point satisfies the constraints, or false
   /// otherwise. Takes the values of all vars including locals.
-  bool containsPoint(ArrayRef<int64_t> point) const;
+  bool containsPoint(ArrayRef<MPInt> point) const;
+  bool containsPoint(ArrayRef<int64_t> point) const {
+    return containsPoint(getMPIntVec(point));
+  }
   /// Given the values of non-local vars, return a satisfying assignment to the
   /// local if one exists, or an empty optional otherwise.
-  Optional<SmallVector<int64_t, 8>>
-  containsPointNoLocal(ArrayRef<int64_t> point) const;
+  Optional<SmallVector<MPInt, 8>>
+  containsPointNoLocal(ArrayRef<MPInt> point) const;
+  Optional<SmallVector<MPInt, 8>>
+  containsPointNoLocal(ArrayRef<int64_t> point) const {
+    return containsPointNoLocal(getMPIntVec(point));
+  }
 
   /// Returns a `DivisonRepr` representing the division representation of local
   /// variables in the constraint system.
   ///
   /// If `repr` is not `nullptr`, the equality and pairs of inequality
   /// constraints identified by their position indices using which an explicit
   /// representation for each local variable can be computed are set in `repr`
   /// in the form of a `MaybeLocalRepr` struct. If no such inequality
   /// pair/equality can be found, the kind attribute in `MaybeLocalRepr` is set
   /// to None.
   DivisionRepr getLocalReprs(std::vector<MaybeLocalRepr> *repr = nullptr) const;
 
   /// The type of bound: equal, lower bound or upper bound.
   enum BoundType { EQ, LB, UB };
 
   /// Adds a constant bound for the specified variable.
-  void addBound(BoundType type, unsigned pos, int64_t value);
+  void addBound(BoundType type, unsigned pos, const MPInt &value);
+  void addBound(BoundType type, unsigned pos, int64_t value) {
+    addBound(type, pos, MPInt(value));
+  }
 
   /// Adds a constant bound for the specified expression.
-  void addBound(BoundType type, ArrayRef<int64_t> expr, int64_t value);
+  void addBound(BoundType type, ArrayRef<MPInt> expr, const MPInt &value);
+  void addBound(BoundType type, ArrayRef<int64_t> expr, int64_t value) {
+    addBound(type, getMPIntVec(expr), MPInt(value));
+  }
 
   /// Adds a new local variable as the floordiv of an affine function of other
   /// variables, the coefficients of which are provided in `dividend` and with
   /// respect to a positive constant `divisor`. Two constraints are added to the
   /// system to capture equivalence with the floordiv:
   /// q = dividend floordiv c    <=>   c*q <= dividend <= c*q + c - 1.
-  void addLocalFloorDiv(ArrayRef<int64_t> dividend, int64_t divisor);
+  void addLocalFloorDiv(ArrayRef<MPInt> dividend, const MPInt &divisor);
+  void addLocalFloorDiv(ArrayRef<int64_t> dividend, int64_t divisor) {
+    addLocalFloorDiv(getMPIntVec(dividend), MPInt(divisor));
+  }
 
   /// Projects out (aka eliminates) `num` variables starting at position
   /// `pos`. The resulting constraint system is the shadow along the dimensions
   /// that still exist. This method may not always be integer exact.
   // TODO: deal with integer exactness when necessary - can return a value to
   // mark exactness for example.
   void projectOut(unsigned pos, unsigned num);
   inline void projectOut(unsigned pos) { return projectOut(pos, 1); }
public:
   /// `boundFloorDivisor`) are set to represent the lower and upper bound
   /// associated with the constant difference: `lb`, `ub` have the coefficients,
   /// and `boundFloorDivisor`, their divisor. `minLbPos` and `minUbPos` if
   /// non-null are set to the position of the constant lower bound and upper
   /// bound respectively (to the same if they are from an equality). Ex: if the
   /// lower bound is [(s0 + s2 - 1) floordiv 32] for a system with three
   /// symbolic variables, *lb = [1, 0, 1], lbDivisor = 32. See comments at
   /// function definition for examples.
-  Optional<int64_t> getConstantBoundOnDimSize(
+  Optional<MPInt> getConstantBoundOnDimSize(
+      unsigned pos, SmallVectorImpl<MPInt> *lb = nullptr,
+      MPInt *boundFloorDivisor = nullptr, SmallVectorImpl<MPInt> *ub = nullptr,
+      unsigned *minLbPos = nullptr, unsigned *minUbPos = nullptr) const;
+  /// The same, but casts to int64_t. This is unsafe and will assert-fail if the
+  /// value does not fit in an int64_t.
+  Optional<int64_t> getConstantBoundOnDimSize64(
       unsigned pos, SmallVectorImpl<int64_t> *lb = nullptr,
       int64_t *boundFloorDivisor = nullptr,
       SmallVectorImpl<int64_t> *ub = nullptr, unsigned *minLbPos = nullptr,
-      unsigned *minUbPos = nullptr) const;
+      unsigned *minUbPos = nullptr) const {
+    SmallVector<MPInt, 8> ubMPInt, lbMPInt;
+    MPInt boundFloorDivisorMPInt;
+    Optional<MPInt> result = getConstantBoundOnDimSize(
+        pos, &lbMPInt, &boundFloorDivisorMPInt, &ubMPInt, minLbPos, minUbPos);
+    if (lb)
+      *lb = getInt64Vec(lbMPInt);
+    if (ub)
+      *ub = getInt64Vec(ubMPInt);
+    if (boundFloorDivisor)
+      *boundFloorDivisor = int64_t(boundFloorDivisorMPInt);
+    return result.map(int64FromMPInt);
+  }
 
   /// Returns the constant bound for the pos^th variable if there is one;
   /// None otherwise.
-  Optional<int64_t> getConstantBound(BoundType type, unsigned pos) const;
+  Optional<MPInt> getConstantBound(BoundType type, unsigned pos) const;
+  /// The same, but casts to int64_t. This is unsafe and will assert-fail if the
+  /// value does not fit in an int64_t.
+  Optional<int64_t> getConstantBound64(BoundType type, unsigned pos) const {
+    return getConstantBound(type, pos).map(int64FromMPInt);
+  }
 
   /// Removes constraints that are independent of (i.e., do not have a
   /// coefficient) variables in the range [pos, pos + num).
   void removeIndependentConstraints(unsigned pos, unsigned num);
 
   /// Returns true if the set can be trivially detected as being
   /// hyper-rectangular on the specified contiguous set of variables.
   bool isHyperRectangular(unsigned pos, unsigned num) const;
protected:
   /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced
   /// after elimination. Returns true if an invalid constraint is found;
   /// false otherwise.
   bool hasInvalidConstraint() const;
 
   /// Returns the constant lower bound bound if isLower is true, and the upper
   /// bound if isLower is false.
   template <bool isLower>
-  Optional<int64_t> computeConstantLowerOrUpperBound(unsigned pos);
+  Optional<MPInt> computeConstantLowerOrUpperBound(unsigned pos);
+  /// The same, but casts to int64_t. This is unsafe and will assert-fail if the
+  /// value does not fit in an int64_t.
+  template <bool isLower>
+  Optional<int64_t> computeConstantLowerOrUpperBound64(unsigned pos) {
+    return computeConstantLowerOrUpperBound<isLower>(pos).map(int64FromMPInt);
+  }
 
   /// Eliminates a single variable at `position` from equality and inequality
   /// constraints. Returns `success` if the variable was eliminated, and
   /// `failure` otherwise.
   inline LogicalResult gaussianEliminateVar(unsigned position) {
     return success(gaussianEliminateVars(position, position + 1) == 1);
   }
 

mlir/include/mlir/Analysis/Presburger/LinearTransform.h

public:
   makeTransformToColumnEchelon(Matrix m);
 
   // Returns an IntegerRelation having a constraint vector vT for every
   // constraint vector v in rel, where T is this transform.
   IntegerRelation applyTo(const IntegerRelation &rel) const;
 
   // The given vector is interpreted as a row vector v. Post-multiply v with
   // this transform, say T, and return vT.
-  SmallVector<int64_t, 8> preMultiplyWithRow(ArrayRef<int64_t> rowVec) const {
+  SmallVector<MPInt, 8> preMultiplyWithRow(ArrayRef<MPInt> rowVec) const {
     return matrix.preMultiplyWithRow(rowVec);
   }
 
   // The given vector is interpreted as a column vector v. Pre-multiply v with
   // this transform, say T, and return Tv.
-  SmallVector<int64_t, 8>
-  postMultiplyWithColumn(ArrayRef<int64_t> colVec) const {
+  SmallVector<MPInt, 8> postMultiplyWithColumn(ArrayRef<MPInt> colVec) const {
     return matrix.postMultiplyWithColumn(colVec);
   }
 
 private:
   Matrix matrix;
 };
 
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_LINEARTRANSFORM_H

mlir/include/mlir/Analysis/Presburger/Matrix.h

 //===- Matrix.h - MLIR Matrix Class -----------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This is a simple 2D matrix class that supports reading, writing, resizing,
 // swapping rows, and swapping columns.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_ANALYSIS_PRESBURGER_MATRIX_H
 #define MLIR_ANALYSIS_PRESBURGER_MATRIX_H
 
+#include "mlir/Analysis/Presburger/MPInt.h"
 #include "mlir/Support/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/Support/raw_ostream.h"
 
 #include <cassert>
 
 namespace mlir {
 namespace presburger {
public:
   /// Initially, the entries are initialized to ero.
   Matrix(unsigned rows, unsigned columns, unsigned reservedRows = 0,
          unsigned reservedColumns = 0);
 
   /// Return the identity matrix of the specified dimension.
   static Matrix identity(unsigned dimension);
 
   /// Access the element at the specified row and column.
-  int64_t &at(unsigned row, unsigned column) {
+  MPInt &at(unsigned row, unsigned column) {
     assert(row < nRows && "Row outside of range");
     assert(column < nColumns && "Column outside of range");
     return data[row * nReservedColumns + column];
   }
 
-  int64_t at(unsigned row, unsigned column) const {
+  MPInt at(unsigned row, unsigned column) const {
     assert(row < nRows && "Row outside of range");
     assert(column < nColumns && "Column outside of range");
     return data[row * nReservedColumns + column];
   }
 
-  int64_t &operator()(unsigned row, unsigned column) { return at(row, column); }
+  MPInt &operator()(unsigned row, unsigned column) { return at(row, column); }
 
-  int64_t operator()(unsigned row, unsigned column) const {
+  MPInt operator()(unsigned row, unsigned column) const {
     return at(row, column);
   }
 
   /// Swap the given columns.
   void swapColumns(unsigned column, unsigned otherColumn);
 
   /// Swap the given rows.
   void swapRows(unsigned row, unsigned otherRow);
 
   unsigned getNumRows() const { return nRows; }
 
   unsigned getNumColumns() const { return nColumns; }
 
   /// Return the maximum number of rows/columns that can be added without
   /// incurring a reallocation.
   unsigned getNumReservedRows() const;
   unsigned getNumReservedColumns() const { return nReservedColumns; }
 
   /// Reserve enough space to resize to the specified number of rows without
   /// reallocations.
   void reserveRows(unsigned rows);
 
   /// Get a [Mutable]ArrayRef corresponding to the specified row.
-  MutableArrayRef<int64_t> getRow(unsigned row);
-  ArrayRef<int64_t> getRow(unsigned row) const;
+  MutableArrayRef<MPInt> getRow(unsigned row);
+  ArrayRef<MPInt> getRow(unsigned row) const;
 
   /// Set the specified row to `elems`.
-  void setRow(unsigned row, ArrayRef<int64_t> elems);
+  void setRow(unsigned row, ArrayRef<MPInt> elems);
 
   /// Insert columns having positions pos, pos + 1, ... pos + count - 1.
   /// Columns that were at positions 0 to pos - 1 will stay where they are;
   /// columns that were at positions pos to nColumns - 1 will be pushed to the
   /// right. pos should be at most nColumns.
   void insertColumns(unsigned pos, unsigned count);
   void insertColumn(unsigned pos);
 
public:
   /// rows that were at positions pos + count - 1 or later will be pushed to the
   /// right. The rows to be deleted must be valid rows: pos + count - 1 must be
   /// at most nRows - 1.
   void removeRows(unsigned pos, unsigned count);
   void removeRow(unsigned pos);
 
   void copyRow(unsigned sourceRow, unsigned targetRow);
 
-  void fillRow(unsigned row, int64_t value);
+  void fillRow(unsigned row, const MPInt &value);
+  void fillRow(unsigned row, int64_t value) { fillRow(row, MPInt(value)); }
 
   /// Add `scale` multiples of the source row to the target row.
-  void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale);
+  void addToRow(unsigned sourceRow, unsigned targetRow, const MPInt &scale);
+  void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
+    addToRow(sourceRow, targetRow, MPInt(scale));
+  }
 
   /// Add `scale` multiples of the source column to the target column.
-  void addToColumn(unsigned sourceColumn, unsigned targetColumn, int64_t scale);
+  void addToColumn(unsigned sourceColumn, unsigned targetColumn,
+                   const MPInt &scale);
+  void addToColumn(unsigned sourceColumn, unsigned targetColumn,
+                   int64_t scale) {
+    addToColumn(sourceColumn, targetColumn, MPInt(scale));
+  }
 
   /// Negate the specified column.
   void negateColumn(unsigned column);
 
   /// Negate the specified row.
   void negateRow(unsigned row);
 
   /// Divide the first `nCols` of the specified row by their GCD.
   /// Returns the GCD of the first `nCols` of the specified row.
-  int64_t normalizeRow(unsigned row, unsigned nCols);
+  MPInt normalizeRow(unsigned row, unsigned nCols);
   /// Divide the columns of the specified row by their GCD.
   /// Returns the GCD of the columns of the specified row.
-  int64_t normalizeRow(unsigned row);
+  MPInt normalizeRow(unsigned row);
 
   /// The given vector is interpreted as a row vector v. Post-multiply v with
   /// this matrix, say M, and return vM.
-  SmallVector<int64_t, 8> preMultiplyWithRow(ArrayRef<int64_t> rowVec) const;
+  SmallVector<MPInt, 8> preMultiplyWithRow(ArrayRef<MPInt> rowVec) const;
 
   /// The given vector is interpreted as a column vector v. Pre-multiply v with
   /// this matrix, say M, and return Mv.
-  SmallVector<int64_t, 8>
-  postMultiplyWithColumn(ArrayRef<int64_t> colVec) const;
+  SmallVector<MPInt, 8> postMultiplyWithColumn(ArrayRef<MPInt> colVec) const;
 
   /// Resize the matrix to the specified dimensions. If a dimension is smaller,
   /// the values are truncated; if it is bigger, the new values are initialized
   /// to zero.
   ///
   /// Due to the representation of the matrix, resizing vertically (adding rows)
   /// is less expensive than increasing the number of columns beyond
   /// nReservedColumns.
   void resize(unsigned newNRows, unsigned newNColumns);
   void resizeHorizontally(unsigned newNColumns);
   void resizeVertically(unsigned newNRows);
 
   /// Add an extra row at the bottom of the matrix and return its position.
   unsigned appendExtraRow();
   /// Same as above, but copy the given elements into the row. The length of
   /// `elems` must be equal to the number of columns.
-  unsigned appendExtraRow(ArrayRef<int64_t> elems);
+  unsigned appendExtraRow(ArrayRef<MPInt> elems);
 
   /// Print the matrix.
   void print(raw_ostream &os) const;
   void dump() const;
 
   /// Return whether the Matrix is in a consistent state with all its
   /// invariants satisfied.
   bool hasConsistentState() const;
 
 private:
   /// The current number of rows, columns, and reserved columns. The underlying
   /// data vector is viewed as an nRows x nReservedColumns matrix, of which the
   /// first nColumns columns are currently in use, and the remaining are
   /// reserved columns filled with zeros.
   unsigned nRows, nColumns, nReservedColumns;
 
   /// Stores the data. data.size() is equal to nRows * nReservedColumns.
   /// data.capacity() / nReservedColumns is the number of reserved rows.
-  SmallVector<int64_t, 64> data;
+  SmallVector<MPInt, 64> data;
 };
 
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_MATRIX_H

mlir/include/mlir/Analysis/Presburger/PWMAFunction.h

public:
 
   /// Get the space of the input domain of this function.
   const PresburgerSpace &getDomainSpace() const { return domainSet.getSpace(); }
   /// Get the input domain of this function.
   const IntegerPolyhedron &getDomain() const { return domainSet; }
   /// Get a matrix with each row representing row^th output expression.
   const Matrix &getOutputMatrix() const { return output; }
   /// Get the `i^th` output expression.
-  ArrayRef<int64_t> getOutputExpr(unsigned i) const { return output.getRow(i); }
+  ArrayRef<MPInt> getOutputExpr(unsigned i) const { return output.getRow(i); }
 
   /// Insert `num` variables of the specified kind at position `pos`.
   /// Positions are relative to the kind of variable. The coefficient columns
   /// corresponding to the added variables are initialized to zero. Return the
   /// absolute column position (i.e., not relative to the kind of variable)
   /// of the first added variable.
   unsigned insertVar(VarKind kind, unsigned pos, unsigned num = 1);
 
public:
 
   /// Return whether the `this` and `other` are equal. This is the case if
   /// they lie in the same space, i.e. have the same dimensions, and their
   /// domains are identical and their outputs are equal on their domain.
   bool isEqual(const MultiAffineFunction &other) const;
 
   /// Get the value of the function at the specified point. If the point lies
   /// outside the domain, an empty optional is returned.
-  Optional<SmallVector<int64_t, 8>> valueAt(ArrayRef<int64_t> point) const;
+  Optional<SmallVector<MPInt, 8>> valueAt(ArrayRef<MPInt> point) const;
+  Optional<SmallVector<MPInt, 8>> valueAt(ArrayRef<int64_t> point) const {
+    return valueAt(getMPIntVec(point));
+  }
 
   /// Truncate the output dimensions to the first `count` dimensions.
   ///
   /// TODO: refactor so that this can be accomplished through removeVarRange.
   void truncateOutput(unsigned count);
 
   void print(raw_ostream &os) const;
   void dump() const;
public:
   MultiAffineFunction &getPiece(unsigned i) { return pieces[i]; }
 
   /// Return the domain of this piece-wise MultiAffineFunction. This is the
   /// union of the domains of all the pieces.
   PresburgerSet getDomain() const;
 
   /// Return the value at the specified point and an empty optional if the
   /// point does not lie in the domain.
-  Optional<SmallVector<int64_t, 8>> valueAt(ArrayRef<int64_t> point) const;
+  Optional<SmallVector<MPInt, 8>> valueAt(ArrayRef<MPInt> point) const;
+  Optional<SmallVector<MPInt, 8>> valueAt(ArrayRef<int64_t> point) const {
+    return valueAt(getMPIntVec(point));
+  }
 
   /// Return whether `this` and `other` are equal as PWMAFunctions, i.e. whether
   /// they have the same dimensions, the same domain and they take the same
   /// value at every point in the domain.
   bool isEqual(const PWMAFunction &other) const;
 
   /// Truncate the output dimensions to the first `count` dimensions.
   ///

mlir/include/mlir/Analysis/Presburger/PresburgerRelation.h

public:
 
   /// Return the union of this set and the given set.
   PresburgerRelation unionSet(const PresburgerRelation &set) const;
 
   /// Return the intersection of this set and the given set.
   PresburgerRelation intersect(const PresburgerRelation &set) const;
 
   /// Return true if the set contains the given point, and false otherwise.
-  bool containsPoint(ArrayRef<int64_t> point) const;
+  bool containsPoint(ArrayRef<MPInt> point) const;
+  bool containsPoint(ArrayRef<int64_t> point) const {
+    return containsPoint(getMPIntVec(point));
+  }
 
   /// Return the complement of this set. All local variables in the set must
   /// correspond to floor divisions.
   PresburgerRelation complement() const;
 
   /// Return the set difference of this set and the given set, i.e.,
   /// return `this \ set`. All local variables in `set` must correspond
   /// to floor divisions, but local variables in `this` need not correspond to
   /// divisions.
   PresburgerRelation subtract(const PresburgerRelation &set) const;
 
   /// Return true if this set is a subset of the given set, and false otherwise.
   bool isSubsetOf(const PresburgerRelation &set) const;
 
   /// Return true if this set is equal to the given set, and false otherwise.
   /// All local variables in both sets must correspond to floor divisions.
   bool isEqual(const PresburgerRelation &set) const;
 
   /// Return true if all the sets in the union are known to be integer empty
   /// false otherwise.
   bool isIntegerEmpty() const;
 
   /// Find an integer sample from the given set. This should not be called if
   /// any of the disjuncts in the union are unbounded.
-  bool findIntegerSample(SmallVectorImpl<int64_t> &sample);
+  bool findIntegerSample(SmallVectorImpl<MPInt> &sample);
 
   /// Compute an overapproximation of the number of integer points in the
   /// disjunct. Symbol vars are currently not supported. If the computed
   /// overapproximation is infinite, an empty optional is returned.
   ///
   /// This currently just sums up the overapproximations of the volumes of the
   /// disjuncts, so the approximation might be far from the true volume in the
   /// case when there is a lot of overlap between disjuncts.
-  Optional<uint64_t> computeVolume() const;
+  Optional<MPInt> computeVolume() const;
 
   /// Simplifies the representation of a PresburgerRelation.
   ///
   /// In particular, removes all disjuncts which are subsets of other
   /// disjuncts in the union.
   PresburgerRelation coalesce() const;
 
   /// Check whether all local ids in all disjuncts have a div representation.

mlir/include/mlir/Analysis/Presburger/Simplex.h

public:
 
   /// Returns true if the tableau is empty (has conflicting constraints),
   /// false otherwise.
   bool isEmpty() const;
 
   /// Add an inequality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
   /// is the current number of variables, then the corresponding inequality is
   /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} >= 0.
-  virtual void addInequality(ArrayRef<int64_t> coeffs) = 0;
+  virtual void addInequality(ArrayRef<MPInt> coeffs) = 0;
 
   /// Returns the number of variables in the tableau.
   unsigned getNumVariables() const;
 
   /// Returns the number of constraints in the tableau.
   unsigned getNumConstraints() const;
 
   /// Add an equality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
   /// is the current number of variables, then the corresponding equality is
   /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} == 0.
-  void addEquality(ArrayRef<int64_t> coeffs);
+  void addEquality(ArrayRef<MPInt> coeffs);
 
   /// Add new variables to the end of the list of variables.
   void appendVariable(unsigned count = 1);
 
   /// Append a new variable to the simplex and constrain it such that its only
   /// integer value is the floor div of `coeffs` and `denom`.
-  void addDivisionVariable(ArrayRef<int64_t> coeffs, int64_t denom);
+  void addDivisionVariable(ArrayRef<MPInt> coeffs, const MPInt &denom);
 
   /// Mark the tableau as being empty.
   void markEmpty();
 
   /// Get a snapshot of the current state. This is used for rolling back.
   /// The same basis will not necessarily be restored on rolling back.
   /// The snapshot only captures the set of variables and constraints present
   /// in the Simplex.
   unsigned getSnapshot() const;
protected:
   /// is initialized to zero. Returns the index of the added row.
   unsigned addZeroRow(bool makeRestricted = false);
 
   /// Add a new row to the tableau and the associated data structures.
   /// The new row is considered to be a constraint; the new Unknown lives in
   /// con.
   ///
   /// Returns the index of the new Unknown in con.
-  unsigned addRow(ArrayRef<int64_t> coeffs, bool makeRestricted = false);
+  unsigned addRow(ArrayRef<MPInt> coeffs, bool makeRestricted = false);
 
   /// Swap the two rows/columns in the tableau and associated data structures.
   void swapRows(unsigned i, unsigned j);
   void swapColumns(unsigned i, unsigned j);
 
   /// Enum to denote operations that need to be undone during rollback.
   enum class UndoLogEntry {
     RemoveLastConstraint,
public:
   ~LexSimplexBase() override = default;
 
   /// Add an inequality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
   /// is the current number of variables, then the corresponding inequality is
   /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} >= 0.
   ///
   /// This just adds the inequality to the tableau and does not try to create a
   /// consistent tableau configuration.
-  void addInequality(ArrayRef<int64_t> coeffs) final;
+  void addInequality(ArrayRef<MPInt> coeffs) final;
 
   /// Get a snapshot of the current state. This is used for rolling back.
   unsigned getSnapshot() { return SimplexBase::getSnapshotBasis(); }
 
 protected:
   LexSimplexBase(unsigned nVar) : SimplexBase(nVar, /*mustUseBigM=*/true) {}
   LexSimplexBase(unsigned nVar, const llvm::SmallBitVector &isSymbol)
       : SimplexBase(nVar, /*mustUseBigM=*/true, isSymbol) {}
public:
 
   /// Return the lexicographically minimum rational solution to the constraints.
   MaybeOptimum<SmallVector<Fraction, 8>> findRationalLexMin();
 
   /// Return the lexicographically minimum integer solution to the constraints.
   ///
   /// Note: this should be used only when the lexmin is really needed. To obtain
   /// any integer sample, use Simplex::findIntegerSample as that is more robust.
-  MaybeOptimum<SmallVector<int64_t, 8>> findIntegerLexMin();
+  MaybeOptimum<SmallVector<MPInt, 8>> findIntegerLexMin();
 
   /// Return whether the specified inequality is redundant/separate for the
   /// polytope. Redundant means every point satisfies the given inequality, and
   /// separate means no point satisfies it.
   ///
   /// These checks are integer-exact.
-  bool isSeparateInequality(ArrayRef<int64_t> coeffs);
-  bool isRedundantInequality(ArrayRef<int64_t> coeffs);
+  bool isSeparateInequality(ArrayRef<MPInt> coeffs);
+  bool isRedundantInequality(ArrayRef<MPInt> coeffs);
 
 private:
   /// Returns the current sample point, which may contain non-integer (rational)
   /// coordinates. Returns an empty optimum when the tableau is empty.
   ///
   /// Returns an unbounded optimum when the big M parameter is used and a
   /// variable has a non-zero big M coefficient, meaning its value is infinite
   /// or unbounded.
private:
   /// at the time of the call. (This function may modify the symbol domain, but
   /// failure statu indicates that the polytope was empty for all symbol values
   /// in the initial domain.)
   LogicalResult addSymbolicCut(unsigned row);
 
   /// Get the numerator of the symbolic sample of the specific row.
   /// This is an affine expression in the symbols with integer coefficients.
   /// The last element is the constant term. This ignores the big M coefficient.
-  SmallVector<int64_t, 8> getSymbolicSampleNumerator(unsigned row) const;
+  SmallVector<MPInt, 8> getSymbolicSampleNumerator(unsigned row) const;
 
   /// Get an affine inequality in the symbols with integer coefficients that
   /// holds iff the symbolic sample of the specified row is non-negative.
-  SmallVector<int64_t, 8> getSymbolicSampleIneq(unsigned row) const;
+  SmallVector<MPInt, 8> getSymbolicSampleIneq(unsigned row) const;
 
   /// Return whether all the coefficients of the symbolic sample are integers.
   ///
   /// This does not consult the domain to check if the specified expression
   /// is always integral despite coefficients being fractional.
   bool isSymbolicSampleIntegral(unsigned row) const;
 
   /// Record a lexmin. The tableau must be consistent with all variables
public:
   ~Simplex() override = default;
 
   /// Add an inequality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
   /// is the current number of variables, then the corresponding inequality is
   /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} >= 0.
   ///
   /// This also tries to restore the tableau configuration to a consistent
   /// state and marks the Simplex empty if this is not possible.
-  void addInequality(ArrayRef<int64_t> coeffs) final;
+  void addInequality(ArrayRef<MPInt> coeffs) final;
 
   /// Compute the maximum or minimum value of the given row, depending on
   /// direction. The specified row is never pivoted. On return, the row may
   /// have a negative sample value if the direction is down.
   ///
   /// Returns a Fraction denoting the optimum, or a null value if no optimum
   /// exists, i.e., if the expression is unbounded in this direction.
   MaybeOptimum<Fraction> computeRowOptimum(Direction direction, unsigned row);
 
   /// Compute the maximum or minimum value of the given expression, depending on
   /// direction. Should not be called when the Simplex is empty.
   ///
   /// Returns a Fraction denoting the optimum, or a null value if no optimum
   /// exists, i.e., if the expression is unbounded in this direction.
   MaybeOptimum<Fraction> computeOptimum(Direction direction,
-                                        ArrayRef<int64_t> coeffs);
+                                        ArrayRef<MPInt> coeffs);
 
   /// Returns whether the perpendicular of the specified constraint is a
   /// is a direction along which the polytope is bounded.
   bool isBoundedAlongConstraint(unsigned constraintIndex);
 
   /// Returns whether the specified constraint has been marked as redundant.
   /// Constraints are numbered from 0 starting at the first added inequality.
   /// Equalities are added as a pair of inequalities and so correspond to two
void detectRedundant(unsigned offset) {
     assert(offset <= con.size() && "invalid offset!");
     detectRedundant(offset, con.size() - offset);
   }
   void detectRedundant() { detectRedundant(0, con.size()); }
 
   /// Returns a (min, max) pair denoting the minimum and maximum integer values
   /// of the given expression. If no integer value exists, both results will be
   /// of kind Empty.
-  std::pair<MaybeOptimum<int64_t>, MaybeOptimum<int64_t>>
-  computeIntegerBounds(ArrayRef<int64_t> coeffs);
+  std::pair<MaybeOptimum<MPInt>, MaybeOptimum<MPInt>>
+  computeIntegerBounds(ArrayRef<MPInt> coeffs);
 
   /// Returns true if the polytope is unbounded, i.e., extends to infinity in
   /// some direction. Otherwise, returns false.
   bool isUnbounded();
 
   /// Make a tableau to represent a pair of points in the given tableaus, one in
   /// tableau A and one in B.
   static Simplex makeProduct(const Simplex &a, const Simplex &b);
 
   /// Returns an integer sample point if one exists, or None
   /// otherwise. This should only be called for bounded sets.
-  Optional<SmallVector<int64_t, 8>> findIntegerSample();
+  Optional<SmallVector<MPInt, 8>> findIntegerSample();
 
   enum class IneqType { Redundant, Cut, Separate };
 
   /// Returns the type of the inequality with coefficients `coeffs`.
   ///
   /// Possible types are:
   /// Redundant   The inequality is satisfied in the polytope
   /// Cut         The inequality is satisfied by some points, but not by others
   /// Separate    The inequality is not satisfied by any point
-  IneqType findIneqType(ArrayRef<int64_t> coeffs);
+  IneqType findIneqType(ArrayRef<MPInt> coeffs);
 
   /// Check if the specified inequality already holds in the polytope.
-  bool isRedundantInequality(ArrayRef<int64_t> coeffs);
+  bool isRedundantInequality(ArrayRef<MPInt> coeffs);
 
   /// Check if the specified equality already holds in the polytope.
-  bool isRedundantEquality(ArrayRef<int64_t> coeffs);
+  bool isRedundantEquality(ArrayRef<MPInt> coeffs);
 
   /// Returns true if this Simplex's polytope is a rational subset of `rel`.
   /// Otherwise, returns false.
   bool isRationalSubsetOf(const IntegerRelation &rel);
 
   /// Returns the current sample point if it is integral. Otherwise, returns
   /// None.
-  Optional<SmallVector<int64_t, 8>> getSamplePointIfIntegral() const;
+  Optional<SmallVector<MPInt, 8>> getSamplePointIfIntegral() const;
 
   /// Returns the current sample point, which may contain non-integer (rational)
   /// coordinates. Returns an empty optional when the tableau is empty.
   Optional<SmallVector<Fraction, 8>> getRationalSample() const;
 
 private:
   friend class GBRSimplex;
 

mlir/include/mlir/Analysis/Presburger/Utils.h

 /// a representation. If the local does not have a representation, the dividend
 /// of the division has no meaning and the denominator is zero.
 ///
 /// The i^th division here, represents the division representation of the
 /// variable at position `divOffset + i` in the constraint system.
 class DivisionRepr {
 public:
   DivisionRepr(unsigned numVars, unsigned numDivs)
-      : dividends(numDivs, numVars + 1), denoms(numDivs, 0) {}
+      : dividends(numDivs, numVars + 1), denoms(numDivs, MPInt(0)) {}
 
   DivisionRepr(unsigned numVars) : dividends(numVars + 1, 0) {}
 
   unsigned getNumVars() const { return dividends.getNumColumns() - 1; }
   unsigned getNumDivs() const { return dividends.getNumRows(); }
   unsigned getNumNonDivs() const { return getNumVars() - getNumDivs(); }
   // Get the offset from where division variables start.
   unsigned getDivOffset() const { return getNumVars() - getNumDivs(); }
 
   // Check whether the `i^th` division has a division representation or not.
   bool hasRepr(unsigned i) const { return denoms[i] != 0; }
   // Check whether all the divisions have a division representation or not.
   bool hasAllReprs() const {
-    return all_of(denoms, [](unsigned denom) { return denom != 0; });
+    return all_of(denoms, [](const MPInt &denom) { return denom != 0; });
   }
 
   // Clear the division representation of the i^th local variable.
   void clearRepr(unsigned i) { denoms[i] = 0; }
 
   // Get the dividend of the `i^th` division.
-  MutableArrayRef<int64_t> getDividend(unsigned i) {
-    return dividends.getRow(i);
-  }
-  ArrayRef<int64_t> getDividend(unsigned i) const {
-    return dividends.getRow(i);
-  }
+  MutableArrayRef<MPInt> getDividend(unsigned i) { return dividends.getRow(i); }
+  ArrayRef<MPInt> getDividend(unsigned i) const { return dividends.getRow(i); }
 
   // Get the `i^th` denominator.
-  unsigned &getDenom(unsigned i) { return denoms[i]; }
-  unsigned getDenom(unsigned i) const { return denoms[i]; }
+  MPInt &getDenom(unsigned i) { return denoms[i]; }
+  MPInt getDenom(unsigned i) const { return denoms[i]; }
 
-  ArrayRef<unsigned> getDenoms() const { return denoms; }
+  ArrayRef<MPInt> getDenoms() const { return denoms; }
 
-  void setDividend(unsigned i, ArrayRef<int64_t> dividend) {
+  void setDividend(unsigned i, ArrayRef<MPInt> dividend) {
     dividends.setRow(i, dividend);
   }
 
   /// Removes duplicate divisions. On every possible duplicate division found,
   /// `merge(i, j)`, where `i`, `j` are current index of the duplicate
   /// divisions, is called and division at index `j` is merged into division at
   /// index `i`. If `merge(i, j)` returns `true`, the divisions are merged i.e.
   /// `j^th` division gets eliminated and it's each instance is replaced by

 private:
   /// Each row of the Matrix represents a single division dividend. The
   /// `i^th` row represents the dividend of the variable at `divOffset + i`
   /// in the constraint system (and the `i^th` local variable).
   Matrix dividends;
 
   /// Denominators of each division. If a denominator of a division is `0`, the
   /// division variable is considered to not have a division representation.
-  SmallVector<unsigned, 4> denoms;
+  SmallVector<MPInt, 4> denoms;
 };
 
 /// If `q` is defined to be equal to `expr floordiv d`, this equivalent to
 /// saying that `q` is an integer and `q` is subject to the inequalities
 /// `0 <= expr - d*q <= c - 1` (quotient remainder theorem).
 ///
 /// Rearranging, we get the bounds on `q`: d*q <= expr <= d*q + d - 1.
 ///
 /// `getDivUpperBound` returns `d*q <= expr`, and
 /// `getDivLowerBound` returns `expr <= d*q + d - 1`.
 ///
 /// The parameter `dividend` corresponds to `expr` above, `divisor` to `d`, and
 /// `localVarIdx` to the position of `q` in the coefficient list.
 ///
 /// The coefficient of `q` in `dividend` must be zero, as it is not allowed for
 /// local variable to be a floor division of an expression involving itself.
-SmallVector<int64_t, 8> getDivUpperBound(ArrayRef<int64_t> dividend,
-                                         int64_t divisor, unsigned localVarIdx);
-SmallVector<int64_t, 8> getDivLowerBound(ArrayRef<int64_t> dividend,
-                                         int64_t divisor, unsigned localVarIdx);
+SmallVector<MPInt, 8> getDivUpperBound(ArrayRef<MPInt> dividend,
+                                       const MPInt &divisor,
+                                       unsigned localVarIdx);
+SmallVector<MPInt, 8> getDivLowerBound(ArrayRef<MPInt> dividend,
+                                       const MPInt &divisor,
+                                       unsigned localVarIdx);
 
 llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset,
                                           unsigned numSet);
 
 /// Check if the pos^th variable can be expressed as a floordiv of an affine
 /// function of other variables (where the divisor is a positive constant).
 /// `foundRepr` contains a boolean for each variable indicating if the
 /// explicit representation for that variable has already been computed.
 /// Return the given array as an array of MPInts.
 SmallVector<MPInt, 8> getMPIntVec(ArrayRef<int64_t> range);
 /// Return the given array as an array of int64_t.
 SmallVector<int64_t, 8> getInt64Vec(ArrayRef<MPInt> range);
 /// Returns the `MaybeLocalRepr` struct which contains the indices of the
 /// constraints that can be expressed as a floordiv of an affine function. If
 /// the representation could be computed, `dividend` and `denominator` are set.
 /// If the representation could not be computed, the kind attribute in
 /// `MaybeLocalRepr` is set to None.
 MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
                                     ArrayRef<bool> foundRepr, unsigned pos,
-                                    MutableArrayRef<int64_t> dividend,
+                                    MutableArrayRef<MPInt> dividend,
+                                    MPInt &divisor);
+
+/// The following overload using int64_t is required for a callsite in
+/// AffineStructures.h.
+MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
+                                    ArrayRef<bool> foundRepr, unsigned pos,
+                                    SmallVector<int64_t, 8> &dividend,
                                     unsigned &divisor);
 
 /// Given two relations, A and B, add additional local vars to the sets such
 /// that both have the union of the local vars in each set, without changing
 /// the set of points that lie in A and B.
 ///
 /// While taking union, if a local var in any set has a division representation
 /// which is a duplicate of division representation, of another local var in any
 /// set, it is not added to the final union of local vars and is instead merged.
 ///
 /// On every possible merge, `merge(i, j)` is called. `i`, `j` are position
 /// of local variables in both sets which are being merged. If `merge(i, j)`
 /// returns true, the divisions are merged, otherwise the divisions are not
 /// merged.
 void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB,
                     llvm::function_ref<bool(unsigned i, unsigned j)> merge);
 
 /// Compute the gcd of the range.
-int64_t gcdRange(ArrayRef<int64_t> range);
+MPInt gcdRange(ArrayRef<MPInt> range);
 
 /// Divide the range by its gcd and return the gcd.
-int64_t normalizeRange(MutableArrayRef<int64_t> range);
+MPInt normalizeRange(MutableArrayRef<MPInt> range);
 
 /// Normalize the given (numerator, denominator) pair by dividing out the
 /// common factors between them. The numerator here is an affine expression
 /// with integer coefficients.
-void normalizeDiv(MutableArrayRef<int64_t> num, int64_t &denom);
+void normalizeDiv(MutableArrayRef<MPInt> num, MPInt &denom);
 
 /// Return `coeffs` with all the elements negated.
-SmallVector<int64_t, 8> getNegatedCoeffs(ArrayRef<int64_t> coeffs);
+SmallVector<MPInt, 8> getNegatedCoeffs(ArrayRef<MPInt> coeffs);
 
 /// Return the complement of the given inequality.
 ///
 /// The complement of a_1 x_1 + ... + a_n x_ + c >= 0 is
 /// a_1 x_1 + ... + a_n x_ + c < 0, i.e., -a_1 x_1 - ... - a_n x_ - c - 1 >= 0,
 /// since all the variables are constrained to be integers.
-SmallVector<int64_t, 8> getComplementIneq(ArrayRef<int64_t> ineq);
-
+SmallVector<MPInt, 8> getComplementIneq(ArrayRef<MPInt> ineq);
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H

mlir/include/mlir/Dialect/Affine/Analysis/Utils.h

struct MemRefRegion {
   /// 'pos' corresponds to the position of the memref shape's dimension (major
   /// to minor) which matches 1:1 with the dimensional variable positions in
   /// 'cst'.
   Optional<int64_t>
   getConstantBoundOnDimSize(unsigned pos,
                             SmallVectorImpl<int64_t> *lb = nullptr,
                             int64_t *lbFloorDivisor = nullptr) const {
     assert(pos < getRank() && "invalid position");
-    return cst.getConstantBoundOnDimSize(pos, lb);
+    return cst.getConstantBoundOnDimSize64(pos, lb);
   }
 
   /// Returns the size of this MemRefRegion in bytes.
   Optional<int64_t> getRegionSize();
 
   // Wrapper around FlatAffineValueConstraints::unionBoundingBox.
   LogicalResult unionBoundingBox(const MemRefRegion &other);
 

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

IntegerRelation::findRationalLexMin() const {
   // will be minimized last in the lexmin. So simply truncating out the locals
   // from the end of the answer gives the desired lexmin over the dimensions.
   assert(maybeLexMin->size() == getNumVars() &&
          "Incorrect number of vars in lexMin!");
   maybeLexMin->resize(getNumDimAndSymbolVars());
   return maybeLexMin;
 }
 
-MaybeOptimum<SmallVector<int64_t, 8>>
-IntegerRelation::findIntegerLexMin() const {
+MaybeOptimum<SmallVector<MPInt, 8>> IntegerRelation::findIntegerLexMin() const {
   assert(getNumSymbolVars() == 0 && "Symbols are not supported!");
-  MaybeOptimum<SmallVector<int64_t, 8>> maybeLexMin =
+  MaybeOptimum<SmallVector<MPInt, 8>> maybeLexMin =
       LexSimplex(*this).findIntegerLexMin();
 
   if (!maybeLexMin.isBounded())
     return maybeLexMin.getKind();
 
   // The Simplex returns the lexmin over all the variables including locals. But
   // locals are not actually part of the space and should not be returned in the
   // result. Since the locals are placed last in the list of variables, they
   // will be minimized last in the lexmin. So simply truncating out the locals
   // from the end of the answer gives the desired lexmin over the dimensions.
   assert(maybeLexMin->size() == getNumVars() &&
          "Incorrect number of vars in lexMin!");
   maybeLexMin->resize(getNumDimAndSymbolVars());
   return maybeLexMin;
 }
 
-static bool rangeIsZero(ArrayRef<int64_t> range) {
-  return llvm::all_of(range, [](int64_t x) { return x == 0; });
+static bool rangeIsZero(ArrayRef<MPInt> range) {
+  return llvm::all_of(range, [](const MPInt &x) { return x == 0; });
 }
 
 static void removeConstraintsInvolvingVarRange(IntegerRelation &poly,
                                                unsigned begin, unsigned count) {
   // We loop until i > 0 and index into i - 1 to avoid sign issues.
   //
   // We iterate backwards so that whether we remove constraint i - 1 or not, the
   // next constraint to be tested is always i - 2.
unsigned IntegerRelation::insertVar(VarKind kind, unsigned pos, unsigned num) {
   return insertPos;
 }
 
 unsigned IntegerRelation::appendVar(VarKind kind, unsigned num) {
   unsigned pos = getNumVarKind(kind);
   return insertVar(kind, pos, num);
 }
 
-void IntegerRelation::addEquality(ArrayRef<int64_t> eq) {
+void IntegerRelation::addEquality(ArrayRef<MPInt> eq) {
   assert(eq.size() == getNumCols());
   unsigned row = equalities.appendExtraRow();
   for (unsigned i = 0, e = eq.size(); i < e; ++i)
     equalities(row, i) = eq[i];
 }
 
-void IntegerRelation::addInequality(ArrayRef<int64_t> inEq) {
+void IntegerRelation::addInequality(ArrayRef<MPInt> inEq) {
   assert(inEq.size() == getNumCols());
   unsigned row = inequalities.appendExtraRow();
   for (unsigned i = 0, e = inEq.size(); i < e; ++i)
     inequalities(row, i) = inEq[i];
 }
 
 void IntegerRelation::removeVar(VarKind kind, unsigned pos) {
   removeVarRange(kind, pos, pos + 1);

 bool IntegerRelation::hasConsistentState() const {
   if (!inequalities.hasConsistentState())
     return false;
   if (!equalities.hasConsistentState())
     return false;
   return true;
 }
 
-void IntegerRelation::setAndEliminate(unsigned pos, ArrayRef<int64_t> values) {
+void IntegerRelation::setAndEliminate(unsigned pos, ArrayRef<MPInt> values) {
   if (values.empty())
     return;
   assert(pos + values.size() <= getNumVars() &&
          "invalid position or too many values");
   // Setting x_j = p in sum_i a_i x_i + c is equivalent to adding p*a_j to the
   // constant term and removing the var x_j. We do this for all the vars
   // pos, pos + 1, ... pos + values.size() - 1.
   unsigned constantColPos = getNumCols() - 1;

 }
 
 // Searches for a constraint with a non-zero coefficient at `colIdx` in
 // equality (isEq=true) or inequality (isEq=false) constraints.
 // Returns true and sets row found in search in `rowIdx`, false otherwise.
 bool IntegerRelation::findConstraintWithNonZeroAt(unsigned colIdx, bool isEq,
                                                   unsigned *rowIdx) const {
   assert(colIdx < getNumCols() && "position out of bounds");
-  auto at = [&](unsigned rowIdx) -> int64_t {
+  auto at = [&](unsigned rowIdx) -> MPInt {
     return isEq ? atEq(rowIdx, colIdx) : atIneq(rowIdx, colIdx);
   };
   unsigned e = isEq ? getNumEqualities() : getNumInequalities();
   for (*rowIdx = 0; *rowIdx < e; ++(*rowIdx)) {
     if (at(*rowIdx) != 0) {
       return true;
     }
   }

 bool IntegerRelation::hasInvalidConstraint() const {
   assert(hasConsistentState());
   auto check = [&](bool isEq) -> bool {
     unsigned numCols = getNumCols();
     unsigned numRows = isEq ? getNumEqualities() : getNumInequalities();
     for (unsigned i = 0, e = numRows; i < e; ++i) {
       unsigned j;
       for (j = 0; j < numCols - 1; ++j) {
-        int64_t v = isEq ? atEq(i, j) : atIneq(i, j);
+        MPInt v = isEq ? atEq(i, j) : atIneq(i, j);
         // Skip rows with non-zero variable coefficients.
         if (v != 0)
           break;
       }
       if (j < numCols - 1) {
         continue;
       }
       // Check validity of constant term at 'numCols - 1' w.r.t 'isEq'.
       // Example invalid constraints include: '1 == 0' or '-1 >= 0'
-      int64_t v = isEq ? atEq(i, numCols - 1) : atIneq(i, numCols - 1);
+      MPInt v = isEq ? atEq(i, numCols - 1) : atIneq(i, numCols - 1);
       if ((isEq && v != 0) || (!isEq && v < 0)) {
         return true;
       }
     }
     return false;
   };
   if (check(/*isEq=*/true))
     return true;
   return check(/*isEq=*/false);
 }
 
 /// Eliminate variable from constraint at `rowIdx` based on coefficient at
 /// pivotRow, pivotCol. Columns in range [elimColStart, pivotCol) will not be
 /// updated as they have already been eliminated.
 static void eliminateFromConstraint(IntegerRelation *constraints,
                                     unsigned rowIdx, unsigned pivotRow,
                                     unsigned pivotCol, unsigned elimColStart,
                                     bool isEq) {
   // Skip if equality 'rowIdx' if same as 'pivotRow'.
   if (isEq && rowIdx == pivotRow)
     return;
-  auto at = [&](unsigned i, unsigned j) -> int64_t {
+  auto at = [&](unsigned i, unsigned j) -> MPInt {
     return isEq ? constraints->atEq(i, j) : constraints->atIneq(i, j);
   };
-  int64_t leadCoeff = at(rowIdx, pivotCol);
+  MPInt leadCoeff = at(rowIdx, pivotCol);
   // Skip if leading coefficient at 'rowIdx' is already zero.
   if (leadCoeff == 0)
     return;
-  int64_t pivotCoeff = constraints->atEq(pivotRow, pivotCol);
-  int64_t sign = (leadCoeff * pivotCoeff > 0) ? -1 : 1;
-  int64_t lcm = mlir::lcm(pivotCoeff, leadCoeff);
-  int64_t pivotMultiplier = sign * (lcm / std::abs(pivotCoeff));
-  int64_t rowMultiplier = lcm / std::abs(leadCoeff);
+  MPInt pivotCoeff = constraints->atEq(pivotRow, pivotCol);
+  int sign = (leadCoeff * pivotCoeff > 0) ? -1 : 1;
+  MPInt lcm = presburger::lcm(pivotCoeff, leadCoeff);
+  MPInt pivotMultiplier = sign * (lcm / abs(pivotCoeff));
+  MPInt rowMultiplier = lcm / abs(leadCoeff);
 
   unsigned numCols = constraints->getNumCols();
   for (unsigned j = 0; j < numCols; ++j) {
     // Skip updating column 'j' if it was just eliminated.
     if (j >= elimColStart && j < pivotCol)
       continue;
-    int64_t v = pivotMultiplier * constraints->atEq(pivotRow, j) +
-                rowMultiplier * at(rowIdx, j);
+    MPInt v = pivotMultiplier * constraints->atEq(pivotRow, j) +
     isEq ? constraints->atEq(rowIdx, j) = v
          : constraints->atIneq(rowIdx, j) = v;
   }
 }
 
 /// Returns the position of the variable that has the minimum <number of lower
 /// bounds> times <number of upper bounds> from the specified range of
 /// variables [start, end). It is often best to eliminate in the increasing

 //
 // The equality constraint:
 //
 //  c_1*x_1 + c_2*x_2 + ... + c_n*x_n = c_0
 //
 // has an integer solution iff:
 //
 //  GCD of c_1, c_2, ..., c_n divides c_0.
-//
 bool IntegerRelation::isEmptyByGCDTest() const {
   assert(hasConsistentState());
   unsigned numCols = getNumCols();
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
-    uint64_t gcd = std::abs(atEq(i, 0));
+    MPInt gcd = abs(atEq(i, 0));
     for (unsigned j = 1; j < numCols - 1; ++j) {
-      gcd = llvm::GreatestCommonDivisor64(gcd, std::abs(atEq(i, j)));
+      gcd = presburger::gcd(gcd, abs(atEq(i, j)));
     }
-    int64_t v = std::abs(atEq(i, numCols - 1));
+    MPInt v = abs(atEq(i, numCols - 1));
     if (gcd > 0 && (v % gcd != 0)) {
       return true;
     }
   }
   return false;
 }
 
 // Returns a matrix where each row is a vector along which the polytope is

 /// outside the prefix are unbounded in S*T (step 1). Substituting values for
 /// the bounded dimensions cannot make these dimensions bounded, and these are
 /// the only remaining dimensions in C, so C is unbounded along every vector (in
 /// the positive or negative direction, or both). C is hence a full-dimensional
 /// cone and therefore always contains an integer point.
 ///
 /// Concatenating the samples from B and C gives a sample v in S*T, so the
 /// returned sample T*v is a sample in S.
-Optional<SmallVector<int64_t, 8>> IntegerRelation::findIntegerSample() const {
+Optional<SmallVector<MPInt, 8>> IntegerRelation::findIntegerSample() const {
   // First, try the GCD test heuristic.
   if (isEmptyByGCDTest())
     return {};
 
   Simplex simplex(*this);
   if (simplex.isEmpty())
     return {};
 
Optional<SmallVector<MPInt, 8>> IntegerRelation::findIntegerSample() const {
   IntegerRelation boundedSet(transformedSet);
   unsigned numBoundedDims = result.first;
   unsigned numUnboundedDims = getNumVars() - numBoundedDims;
   removeConstraintsInvolvingVarRange(boundedSet, numBoundedDims,
                                      numUnboundedDims);
   boundedSet.removeVarRange(numBoundedDims, boundedSet.getNumVars());
 
   // 3) Try to obtain a sample from the bounded set.
-  Optional<SmallVector<int64_t, 8>> boundedSample =
+  Optional<SmallVector<MPInt, 8>> boundedSample =
       Simplex(boundedSet).findIntegerSample();
   if (!boundedSample)
     return {};
   assert(boundedSet.containsPoint(*boundedSample) &&
          "Simplex returned an invalid sample!");
 
   // 4) Substitute the values of the bounded dimensions into S*T to obtain a
   // full-dimensional cone, which necessarily contains an integer sample.
Optional<SmallVector<MPInt, 8>> IntegerRelation::findIntegerSample() const {
   // keep the other x_i the same. In the example, we would get x = (3, 1, 1),
   // changing the value of the LHS by -3 + -7 = -10.
   //
   // In general, the value of the LHS can change by at most the sum of the
   // negative a_i, so we accomodate this by shifting the inequality by this
   // amount for the shrunken cone.
   for (unsigned i = 0, e = cone.getNumInequalities(); i < e; ++i) {
     for (unsigned j = 0; j < cone.getNumVars(); ++j) {
-      int64_t coeff = cone.atIneq(i, j);
+      MPInt coeff = cone.atIneq(i, j);
       if (coeff < 0)
         cone.atIneq(i, cone.getNumVars()) += coeff;
     }
   }
 
   // Obtain an integer sample in the cone by rounding up a rational point from
   // the shrunken cone. Shrinking the cone amounts to shifting its apex
   // "inwards" without changing its "shape"; the shrunken cone is still a
   // full-dimensional cone and is hence non-empty.
   Simplex shrunkenConeSimplex(cone);
   assert(!shrunkenConeSimplex.isEmpty() && "Shrunken cone cannot be empty!");
 
   // The sample will always exist since the shrunken cone is non-empty.
   SmallVector<Fraction, 8> shrunkenConeSample =
       *shrunkenConeSimplex.getRationalSample();
 
-  SmallVector<int64_t, 8> coneSample(llvm::map_range(shrunkenConeSample, ceil));
+  SmallVector<MPInt, 8> coneSample(llvm::map_range(shrunkenConeSample, ceil));
 
   // 6) Return transform * concat(boundedSample, coneSample).
-  SmallVector<int64_t, 8> &sample = *boundedSample;
+  SmallVector<MPInt, 8> &sample = *boundedSample;
   sample.append(coneSample.begin(), coneSample.end());
   return transform.postMultiplyWithColumn(sample);
 }
 
 /// Helper to evaluate an affine expression at a point.
 /// The expression is a list of coefficients for the dimensions followed by the
 /// constant term.
-static int64_t valueAt(ArrayRef<int64_t> expr, ArrayRef<int64_t> point) {
+static MPInt valueAt(ArrayRef<MPInt> expr, ArrayRef<MPInt> point) {
   assert(expr.size() == 1 + point.size() &&
          "Dimensionalities of point and expression don't match!");
-  int64_t value = expr.back();
+  MPInt value = expr.back();
   for (unsigned i = 0; i < point.size(); ++i)
     value += expr[i] * point[i];
   return value;
 }
 
 /// A point satisfies an equality iff the value of the equality at the
 /// expression is zero, and it satisfies an inequality iff the value of the
 /// inequality at that point is non-negative.
-bool IntegerRelation::containsPoint(ArrayRef<int64_t> point) const {
+bool IntegerRelation::containsPoint(ArrayRef<MPInt> point) const {
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i) {
     if (valueAt(getEquality(i), point) != 0)
       return false;
   }
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
     if (valueAt(getInequality(i), point) < 0)
       return false;
   }
   return true;
 }
 
 /// Just substitute the values given and check if an integer sample exists for
 /// the local vars.
 ///
 /// TODO: this could be made more efficient by handling divisions separately.
 /// Instead of finding an integer sample over all the locals, we can first
 /// compute the values of the locals that have division representations and
 /// only use the integer emptiness check for the locals that don't have this.
 /// Handling this correctly requires ordering the divs, though.
-Optional<SmallVector<int64_t, 8>>
-IntegerRelation::containsPointNoLocal(ArrayRef<int64_t> point) const {
+Optional<SmallVector<MPInt, 8>>
+IntegerRelation::containsPointNoLocal(ArrayRef<MPInt> point) const {
   assert(point.size() == getNumVars() - getNumLocalVars() &&
          "Point should contain all vars except locals!");
   assert(getVarKindOffset(VarKind::Local) == getNumVars() - getNumLocalVars() &&
          "This function depends on locals being stored last!");
   IntegerRelation copy = *this;
   copy.setAndEliminate(0, point);
   return copy.findIntegerSample();
 }

 /// fast method - linear in the number of coefficients.
 // Example on how this affects practical cases: consider the scenario:
 // 64*i >= 100, j = 64*i; without a tightening, elimination of i would yield
 // j >= 100 instead of the tighter (exact) j >= 128.
 void IntegerRelation::gcdTightenInequalities() {
   unsigned numCols = getNumCols();
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
     // Normalize the constraint and tighten the constant term by the GCD.
-    int64_t gcd = inequalities.normalizeRow(i, getNumCols() - 1);
+    MPInt gcd = inequalities.normalizeRow(i, getNumCols() - 1);
     if (gcd > 1)
-      atIneq(i, numCols - 1) = mlir::floorDiv(atIneq(i, numCols - 1), gcd);
+      atIneq(i, numCols - 1) = floorDiv(atIneq(i, numCols - 1), gcd);
   }
 }
 
 // Eliminates all variable variables in column range [posStart, posLimit).
 // Returns the number of variables eliminated.
 unsigned IntegerRelation::gaussianEliminateVars(unsigned posStart,
                                                 unsigned posLimit) {
   // Return if variable positions to eliminate are out of range.
void IntegerRelation::removeRedundantConstraints() {
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
     if (!(simplex.isMarkedRedundant(numIneqs + 2 * r) &&
           simplex.isMarkedRedundant(numIneqs + 2 * r + 1)))
       equalities.copyRow(r, pos++);
   }
   equalities.resizeVertically(pos);
 }
 
-Optional<uint64_t> IntegerRelation::computeVolume() const {
+Optional<MPInt> IntegerRelation::computeVolume() const {
   assert(getNumSymbolVars() == 0 && "Symbols are not yet supported!");
 
   Simplex simplex(*this);
   // If the polytope is rationally empty, there are certainly no integer
   // points.
   if (simplex.isEmpty())
-    return 0;
+    return MPInt(0);
 
   // Just find the maximum and minimum integer value of each non-local var
   // separately, thus finding the number of integer values each such var can
   // take. Multiplying these together gives a valid overapproximation of the
   // number of integer points in the relation. The result this gives is
   // equivalent to projecting (rationally) the relation onto its non-local vars
   // and returning the number of integer points in a minimal axis-parallel
   // hyperrectangular overapproximation of that.
   //
   // We also handle the special case where one dimension is unbounded and
   // another dimension can take no integer values. In this case, the volume is
   // zero.
   //
   // If there is no such empty dimension, if any dimension is unbounded we
   // just return the result as unbounded.
-  uint64_t count = 1;
-  SmallVector<int64_t, 8> dim(getNumVars() + 1);
+  MPInt count(1);
+  SmallVector<MPInt, 8> dim(getNumVars() + 1);
   bool hasUnboundedVar = false;
   for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; ++i) {
     dim[i] = 1;
-    MaybeOptimum<int64_t> min, max;
+    MaybeOptimum<MPInt> min, max;
     std::tie(min, max) = simplex.computeIntegerBounds(dim);
     dim[i] = 0;
 
     assert((!min.isEmpty() && !max.isEmpty()) &&
            "Polytope should be rationally non-empty!");
 
     // One of the dimensions is unbounded. Note this fact. We will return
     // unbounded if none of the other dimensions makes the volume zero.
     if (min.isUnbounded() || max.isUnbounded()) {
       hasUnboundedVar = true;
       continue;
     }
 
     // In this case there are no valid integer points and the volume is
     // definitely zero.
     if (min.getBoundedOptimum() > max.getBoundedOptimum())
-      return 0;
+      return MPInt(0);
 
     count *= (*max - *min + 1);
   }
 
   if (count == 0)
-    return 0;
+    return MPInt(0);
   if (hasUnboundedVar)
     return {};
   return count;
 }
 
 void IntegerRelation::eliminateRedundantLocalVar(unsigned posA, unsigned posB) {
   assert(posA < getNumLocalVars() && "Invalid local var position");
   assert(posB < getNumLocalVars() && "Invalid local var position");
void IntegerRelation::removeRedundantLocalVars() {
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
     equalities.normalizeRow(i);
 
   while (true) {
     unsigned i, e, j, f;
     for (i = 0, e = getNumEqualities(); i < e; ++i) {
       // Find a local variable to eliminate using ith equality.
       for (j = getNumDimAndSymbolVars(), f = getNumVars(); j < f; ++j)
-        if (std::abs(atEq(i, j)) == 1)
+        if (abs(atEq(i, j)) == 1)
           break;
 
       // Local variable can be eliminated using ith equality.
       if (j < f)
         break;
     }
 
     // No equality can be used to eliminate a local variable.
void IntegerRelation::convertVarKind(VarKind srcKind, unsigned varStart,
   unsigned offset = getVarKindOffset(srcKind);
   for (unsigned i = 0; i < convertCount; ++i)
     swapVar(offset + varStart + i, newVarsBegin + i);
 
   // Complete the move by deleting the initially occupied columns.
   removeVarRange(srcKind, varStart, varLimit);
 }
 
-void IntegerRelation::addBound(BoundType type, unsigned pos, int64_t value) {
+void IntegerRelation::addBound(BoundType type, unsigned pos,
+                               const MPInt &value) {
   assert(pos < getNumCols());
   if (type == BoundType::EQ) {
     unsigned row = equalities.appendExtraRow();
     equalities(row, pos) = 1;
     equalities(row, getNumCols() - 1) = -value;
   } else {
     unsigned row = inequalities.appendExtraRow();
     inequalities(row, pos) = type == BoundType::LB ? 1 : -1;
     inequalities(row, getNumCols() - 1) =
         type == BoundType::LB ? -value : value;
   }
 }
 
-void IntegerRelation::addBound(BoundType type, ArrayRef<int64_t> expr,
-                               int64_t value) {
+void IntegerRelation::addBound(BoundType type, ArrayRef<MPInt> expr,
+                               const MPInt &value) {
   assert(type != BoundType::EQ && "EQ not implemented");
   assert(expr.size() == getNumCols());
   unsigned row = inequalities.appendExtraRow();
   for (unsigned i = 0, e = expr.size(); i < e; ++i)
     inequalities(row, i) = type == BoundType::LB ? expr[i] : -expr[i];
   inequalities(inequalities.getNumRows() - 1, getNumCols() - 1) +=
       type == BoundType::LB ? -value : value;
 }
 
 /// Adds a new local variable as the floordiv of an affine function of other
 /// variables, the coefficients of which are provided in 'dividend' and with
 /// respect to a positive constant 'divisor'. Two constraints are added to the
 /// system to capture equivalence with the floordiv.
 ///      q = expr floordiv c    <=>   c*q <= expr <= c*q + c - 1.
-void IntegerRelation::addLocalFloorDiv(ArrayRef<int64_t> dividend,
-                                       int64_t divisor) {
+void IntegerRelation::addLocalFloorDiv(ArrayRef<MPInt> dividend,
+                                       const MPInt &divisor) {
   assert(dividend.size() == getNumCols() && "incorrect dividend size");
   assert(divisor > 0 && "positive divisor expected");
 
   appendVar(VarKind::Local);
 
-  SmallVector<int64_t, 8> dividendCopy(dividend.begin(), dividend.end());
-  dividendCopy.insert(dividendCopy.end() - 1, 0);
+  SmallVector<MPInt, 8> dividendCopy(dividend.begin(), dividend.end());
+  dividendCopy.insert(dividendCopy.end() - 1, MPInt(0));
   addInequality(
       getDivLowerBound(dividendCopy, divisor, dividendCopy.size() - 2));
   addInequality(
       getDivUpperBound(dividendCopy, divisor, dividendCopy.size() - 2));
 }
 
 /// Finds an equality that equates the specified variable to a constant.
 /// Returns the position of the equality row. If 'symbolic' is set to true,
 /// symbols are also treated like a constant, i.e., an affine function of the
 /// symbols is also treated like a constant. Returns -1 if such an equality
 /// could not be found.
 static int findEqualityToConstant(const IntegerRelation &cst, unsigned pos,
                                   bool symbolic = false) {
   assert(pos < cst.getNumVars() && "invalid position");
   for (unsigned r = 0, e = cst.getNumEqualities(); r < e; r++) {
-    int64_t v = cst.atEq(r, pos);
+    MPInt v = cst.atEq(r, pos);
     if (v * v != 1)
       continue;
     unsigned c;
     unsigned f = symbolic ? cst.getNumDimVars() : cst.getNumVars();
     // This checks for zeros in all positions other than 'pos' in [0, f)
     for (c = 0; c < f; c++) {
       if (c == pos)
         continue;

 LogicalResult IntegerRelation::constantFoldVar(unsigned pos) {
   assert(pos < getNumVars() && "invalid position");
   int rowIdx;
   if ((rowIdx = findEqualityToConstant(*this, pos)) == -1)
     return failure();
 
   // atEq(rowIdx, pos) is either -1 or 1.
   assert(atEq(rowIdx, pos) * atEq(rowIdx, pos) == 1);
-  int64_t constVal = -atEq(rowIdx, getNumCols() - 1) / atEq(rowIdx, pos);
+  MPInt constVal = -atEq(rowIdx, getNumCols() - 1) / atEq(rowIdx, pos);
   setAndEliminate(pos, constVal);
   return success();
 }
 
 void IntegerRelation::constantFoldVarRange(unsigned pos, unsigned num) {
   for (unsigned s = pos, t = pos, e = pos + num; s < e; s++) {
     if (failed(constantFoldVar(t)))
       t++;

 /// bound associated with the constant difference. Note that 'lb' is purely
 /// symbolic and thus will contain the coefficients of the symbolic variables
 /// and the constant coefficient.
 //  Egs: 0 <= i <= 15, return 16.
 //       s0 + 2 <= i <= s0 + 17, returns 16. (s0 has to be a symbol)
 //       s0 + s1 + 16 <= d0 <= s0 + s1 + 31, returns 16.
 //       s0 - 7 <= 8*j <= s0 returns 1 with lb = s0, lbDivisor = 8 (since lb =
 //       ceil(s0 - 7 / 8) = floor(s0 / 8)).
-Optional<int64_t> IntegerRelation::getConstantBoundOnDimSize(
-    unsigned pos, SmallVectorImpl<int64_t> *lb, int64_t *boundFloorDivisor,
-    SmallVectorImpl<int64_t> *ub, unsigned *minLbPos,
-    unsigned *minUbPos) const {
+Optional<MPInt> IntegerRelation::getConstantBoundOnDimSize(
+    unsigned pos, SmallVectorImpl<MPInt> *lb, MPInt *boundFloorDivisor,
+    SmallVectorImpl<MPInt> *ub, unsigned *minLbPos, unsigned *minUbPos) const {
   assert(pos < getNumDimVars() && "Invalid variable position");
 
   // Find an equality for 'pos'^th variable that equates it to some function
   // of the symbolic variables (+ constant).
   int eqPos = findEqualityToConstant(*this, pos, /*symbolic=*/true);
   if (eqPos != -1) {
     auto eq = getEquality(eqPos);
     // If the equality involves a local var, punt for now.
     // TODO: this can be handled in the future by using the explicit
     // representation of the local vars.
     if (!std::all_of(eq.begin() + getNumDimAndSymbolVars(), eq.end() - 1,
-                     [](int64_t coeff) { return coeff == 0; }))
+                     [](const MPInt &coeff) { return coeff == 0; }))
       return None;
 
     // This variable can only take a single value.
     if (lb) {
       // Set lb to that symbolic value.
       lb->resize(getNumSymbolVars() + 1);
       if (ub)
         ub->resize(getNumSymbolVars() + 1);
       for (unsigned c = 0, f = getNumSymbolVars() + 1; c < f; c++) {
-        int64_t v = atEq(eqPos, pos);
+        MPInt v = atEq(eqPos, pos);
         // atEq(eqRow, pos) is either -1 or 1.
         assert(v * v == 1);
         (*lb)[c] = v < 0 ? atEq(eqPos, getNumDimVars() + c) / -v
                          : -atEq(eqPos, getNumDimVars() + c) / v;
         // Since this is an equality, ub = lb.
         if (ub)
           (*ub)[c] = (*lb)[c];
       }
       assert(boundFloorDivisor &&
              "both lb and divisor or none should be provided");
       *boundFloorDivisor = 1;
     }
     if (minLbPos)
       *minLbPos = eqPos;
     if (minUbPos)
       *minUbPos = eqPos;
-    return 1;
+    return MPInt(1);
   }
 
   // Check if the variable appears at all in any of the inequalities.
   unsigned r, e;
   for (r = 0, e = getNumInequalities(); r < e; r++) {
     if (atIneq(r, pos) != 0)
       break;
   }
   if (r == e)
     // If it doesn't, there isn't a bound on it.
     return None;
 
   // Positions of constraints that are lower/upper bounds on the variable.
   SmallVector<unsigned, 4> lbIndices, ubIndices;
 
   // Gather all symbolic lower bounds and upper bounds of the variable, i.e.,
   // the bounds can only involve symbolic (and local) variables. Since the
   // canonical form c_1*x_1 + c_2*x_2 + ... + c_0 >= 0, a constraint is a lower
   // bound for x_i if c_i >= 1, and an upper bound if c_i <= -1.
   getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices,
                                /*eqIndices=*/nullptr, /*offset=*/0,
                                /*num=*/getNumDimVars());
 
-  Optional<int64_t> minDiff = None;
+  Optional<MPInt> minDiff = None;
   unsigned minLbPosition = 0, minUbPosition = 0;
   for (auto ubPos : ubIndices) {
     for (auto lbPos : lbIndices) {
       // Look for a lower bound and an upper bound that only differ by a
       // constant, i.e., pairs of the form  0 <= c_pos - f(c_i's) <= diffConst.
       // For example, if ii is the pos^th variable, we are looking for
       // constraints like ii >= i, ii <= ii + 50, 50 being the difference. The
       // minimum among all such constant differences is kept since that's the
       // constant bounding the extent of the pos^th variable.
       unsigned j, e;
       for (j = 0, e = getNumCols() - 1; j < e; j++)
         if (atIneq(ubPos, j) != -atIneq(lbPos, j)) {
           break;
         }
       if (j < getNumCols() - 1)
         continue;
-      int64_t diff = ceilDiv(atIneq(ubPos, getNumCols() - 1) +
-                                 atIneq(lbPos, getNumCols() - 1) + 1,
-                             atIneq(lbPos, pos));
+      MPInt diff = ceilDiv(atIneq(ubPos, getNumCols() - 1) +
       // This bound is non-negative by definition.
-      diff = std::max<int64_t>(diff, 0);
+      diff = std::max<MPInt>(diff, MPInt(0));
       if (minDiff == None || diff < minDiff) {
         minDiff = diff;
         minLbPosition = lbPos;
         minUbPosition = ubPos;
       }
     }
   }
   if (lb && minDiff) {
Optional<MPInt> IntegerRelation::getConstantBoundOnDimSize(
   if (minLbPos)
     *minLbPos = minLbPosition;
   if (minUbPos)
     *minUbPos = minUbPosition;
   return minDiff;
 }
 
 template <bool isLower>
-Optional<int64_t>
+Optional<MPInt>
 IntegerRelation::computeConstantLowerOrUpperBound(unsigned pos) {
   assert(pos < getNumVars() && "invalid position");
   // Project to 'pos'.
   projectOut(0, pos);
   projectOut(1, getNumVars() - 1);
   // Check if there's an equality equating the '0'^th variable to a constant.
   int eqRowIdx = findEqualityToConstant(*this, 0, /*symbolic=*/false);
   if (eqRowIdx != -1)
     // atEq(rowIdx, 0) is either -1 or 1.
     return -atEq(eqRowIdx, getNumCols() - 1) / atEq(eqRowIdx, 0);
 
   // Check if the variable appears at all in any of the inequalities.
   unsigned r, e;
   for (r = 0, e = getNumInequalities(); r < e; r++) {
     if (atIneq(r, 0) != 0)
       break;
   }
   if (r == e)
     // If it doesn't, there isn't a bound on it.
     return None;
 
-  Optional<int64_t> minOrMaxConst = None;
+  Optional<MPInt> minOrMaxConst = None;
 
   // Take the max across all const lower bounds (or min across all constant
   // upper bounds).
   for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
     if (isLower) {
       if (atIneq(r, 0) <= 0)
         // Not a lower bound.
         continue;
     } else if (atIneq(r, 0) >= 0) {
       // Not an upper bound.
       continue;
     }
     unsigned c, f;
     for (c = 0, f = getNumCols() - 1; c < f; c++)
       if (c != 0 && atIneq(r, c) != 0)
         break;
     if (c < getNumCols() - 1)
       // Not a constant bound.
       continue;
 
-    int64_t boundConst =
-        isLower ? mlir::ceilDiv(-atIneq(r, getNumCols() - 1), atIneq(r, 0))
-                : mlir::floorDiv(atIneq(r, getNumCols() - 1), -atIneq(r, 0));
+    MPInt boundConst =
+        isLower ? ceilDiv(-atIneq(r, getNumCols() - 1), atIneq(r, 0))
+                : floorDiv(atIneq(r, getNumCols() - 1), -atIneq(r, 0));
     if (isLower) {
       if (minOrMaxConst == None || boundConst > minOrMaxConst)
         minOrMaxConst = boundConst;
     } else {
       if (minOrMaxConst == None || boundConst < minOrMaxConst)
         minOrMaxConst = boundConst;
     }
   }
   return minOrMaxConst;
 }
 
-Optional<int64_t> IntegerRelation::getConstantBound(BoundType type,
-                                                    unsigned pos) const {
+Optional<MPInt> IntegerRelation::getConstantBound(BoundType type,
   if (type == BoundType::LB)
     return IntegerRelation(*this)
         .computeConstantLowerOrUpperBound</*isLower=*/true>(pos);
   if (type == BoundType::UB)
     return IntegerRelation(*this)
         .computeConstantLowerOrUpperBound</*isLower=*/false>(pos);
 
   assert(type == BoundType::EQ && "expected EQ");
-  Optional<int64_t> lb =
+  Optional<MPInt> lb =
       IntegerRelation(*this).computeConstantLowerOrUpperBound</*isLower=*/true>(
           pos);
-  Optional<int64_t> ub =
+  Optional<MPInt> ub =
       IntegerRelation(*this)
           .computeConstantLowerOrUpperBound</*isLower=*/false>(pos);
-  return (lb && ub && *lb == *ub) ? Optional<int64_t>(*ub) : None;
+  return (lb && ub && *lb == *ub) ? Optional<MPInt>(*ub) : None;
 }
 
 // A simple (naive and conservative) check for hyper-rectangularity.
 bool IntegerRelation::isHyperRectangular(unsigned pos, unsigned num) const {
   assert(pos < getNumCols() - 1);
   // Check for two non-zero coefficients in the range [pos, pos + sum).
   for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
     unsigned sum = 0;

 //  remove duplicates in place.
 void IntegerRelation::removeTrivialRedundancy() {
   gcdTightenInequalities();
   normalizeConstraintsByGCD();
 
   // A map used to detect redundancy stemming from constraints that only differ
   // in their constant term. The value stored is <row position, const term>
   // for a given row.
-  SmallDenseMap<ArrayRef<int64_t>, std::pair<unsigned, int64_t>>
+  SmallDenseMap<ArrayRef<MPInt>, std::pair<unsigned, MPInt>>
       rowsWithoutConstTerm;
   // To unique rows.
-  SmallDenseSet<ArrayRef<int64_t>, 8> rowSet;
+  SmallDenseSet<ArrayRef<MPInt>, 8> rowSet;
 
   // Check if constraint is of the form <non-negative-constant> >= 0.
   auto isTriviallyValid = [&](unsigned r) -> bool {
     for (unsigned c = 0, e = getNumCols() - 1; c < e; c++) {
       if (atIneq(r, c) != 0)
         return false;
     }
     return atIneq(r, getNumCols() - 1) >= 0;
   };
 
   // Detect and mark redundant constraints.
   SmallVector<bool, 256> redunIneq(getNumInequalities(), false);
   for (unsigned r = 0, e = getNumInequalities(); r < e; r++) {
-    int64_t *rowStart = &inequalities(r, 0);
-    auto row = ArrayRef<int64_t>(rowStart, getNumCols());
+    MPInt *rowStart = &inequalities(r, 0);
+    auto row = ArrayRef<MPInt>(rowStart, getNumCols());
     if (isTriviallyValid(r) || !rowSet.insert(row).second) {
       redunIneq[r] = true;
       continue;
     }
 
     // Among constraints that only differ in the constant term part, mark
     // everything other than the one with the smallest constant term redundant.
     // (eg: among i - 16j - 5 >= 0, i - 16j - 1 >=0, i - 16j - 7 >= 0, the
     // former two are redundant).
-    int64_t constTerm = atIneq(r, getNumCols() - 1);
-    auto rowWithoutConstTerm = ArrayRef<int64_t>(rowStart, getNumCols() - 1);
+    MPInt constTerm = atIneq(r, getNumCols() - 1);
+    auto rowWithoutConstTerm = ArrayRef<MPInt>(rowStart, getNumCols() - 1);
     const auto &ret =
         rowsWithoutConstTerm.insert({rowWithoutConstTerm, {r, constTerm}});
     if (!ret.second) {
       // Check if the other constraint has a higher constant term.
       auto &val = ret.first->second;
       if (val.second > constTerm) {
         // The stored row is redundant. Mark it so, and update with this one.
         redunIneq[val.first] = true;
void IntegerRelation::fourierMotzkinEliminate(unsigned pos, bool darkShadow,
   unsigned relativePos = pos - newSpace.getVarKindOffset(idKindRemove);
   newSpace.removeVarRange(idKindRemove, relativePos, relativePos + 1);
 
   /// Create the new system which has one variable less.
   IntegerRelation newRel(lbIndices.size() * ubIndices.size() + nbIndices.size(),
                          getNumEqualities(), getNumCols() - 1, newSpace);
 
   // This will be used to check if the elimination was integer exact.
-  unsigned lcmProducts = 1;
+  MPInt lcmProducts(1);
 
   // Let x be the variable we are eliminating.
   // For each lower bound, lb <= c_l*x, and each upper bound c_u*x <= ub, (note
   // that c_l, c_u >= 1) we have:
   // lb*lcm(c_l, c_u)/c_l <= lcm(c_l, c_u)*x <= ub*lcm(c_l, c_u)/c_u
   // We thus generate a constraint:
   // lcm(c_l, c_u)/c_l*lb <= lcm(c_l, c_u)/c_u*ub.
   // Note if c_l = c_u = 1, all integer points captured by the resulting
   // constraint correspond to integer points in the original system (i.e., they
   // have integer pre-images). Hence, if the lcm's are all 1, the elimination is
   // integer exact.
   for (auto ubPos : ubIndices) {
     for (auto lbPos : lbIndices) {
-      SmallVector<int64_t, 4> ineq;
+      SmallVector<MPInt, 4> ineq;
       ineq.reserve(newRel.getNumCols());
-      int64_t lbCoeff = atIneq(lbPos, pos);
+      MPInt lbCoeff = atIneq(lbPos, pos);
       // Note that in the comments above, ubCoeff is the negation of the
       // coefficient in the canonical form as the view taken here is that of the
       // term being moved to the other size of '>='.
-      int64_t ubCoeff = -atIneq(ubPos, pos);
+      MPInt ubCoeff = -atIneq(ubPos, pos);
       // TODO: refactor this loop to avoid all branches inside.
       for (unsigned l = 0, e = getNumCols(); l < e; l++) {
         if (l == pos)
           continue;
         assert(lbCoeff >= 1 && ubCoeff >= 1 && "bounds wrongly identified");
-        int64_t lcm = mlir::lcm(lbCoeff, ubCoeff);
+        MPInt lcm = presburger::lcm(lbCoeff, ubCoeff);
         ineq.push_back(atIneq(ubPos, l) * (lcm / ubCoeff) +
                        atIneq(lbPos, l) * (lcm / lbCoeff));
         lcmProducts *= lcm;
       }
       if (darkShadow) {
         // The dark shadow is a convex subset of the exact integer shadow. If
         // there is a point here, it proves the existence of a solution.
         ineq[ineq.size() - 1] += lbCoeff * ubCoeff - lbCoeff - ubCoeff + 1;
       }
       // TODO: we need to have a way to add inequalities in-place in
       // IntegerRelation instead of creating and copying over.
       newRel.addInequality(ineq);
     }
   }
 
   LLVM_DEBUG(llvm::dbgs() << "FM isResultIntegerExact: " << (lcmProducts == 1)
                           << "\n");
   if (lcmProducts == 1 && isResultIntegerExact)
     *isResultIntegerExact = true;
 
   // Copy over the constraints not involving this variable.
   for (auto nbPos : nbIndices) {
-    SmallVector<int64_t, 4> ineq;
+    SmallVector<MPInt, 4> ineq;
     ineq.reserve(getNumCols() - 1);
     for (unsigned l = 0, e = getNumCols(); l < e; l++) {
       if (l == pos)
         continue;
       ineq.push_back(atIneq(nbPos, l));
     }
     newRel.addInequality(ineq);
   }
 
   assert(newRel.getNumConstraints() ==
          lbIndices.size() * ubIndices.size() + nbIndices.size());
 
   // Copy over the equalities.
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++) {
-    SmallVector<int64_t, 4> eq;
+    SmallVector<MPInt, 4> eq;
     eq.reserve(newRel.getNumCols());
     for (unsigned l = 0, e = getNumCols(); l < e; l++) {
       if (l == pos)
         continue;
       eq.push_back(atEq(r, l));
     }
     newRel.addEquality(eq);
   }

 }
 
 namespace {
 
 enum BoundCmpResult { Greater, Less, Equal, Unknown };
 
 /// Compares two affine bounds whose coefficients are provided in 'first' and
 /// 'second'. The last coefficient is the constant term.
-static BoundCmpResult compareBounds(ArrayRef<int64_t> a, ArrayRef<int64_t> b) {
+static BoundCmpResult compareBounds(ArrayRef<MPInt> a, ArrayRef<MPInt> b) {
   assert(a.size() == b.size());
 
   // For the bounds to be comparable, their corresponding variable
   // coefficients should be equal; the constant terms are then compared to
   // determine less/greater/equal.
 
   if (!std::equal(a.begin(), a.end() - 1, b.begin()))
     return Unknown;
IntegerRelation::unionBoundingBox(const IntegerRelation &otherCst) {
   assert(space.isEqual(otherCst.getSpace()) && "Spaces should match.");
   assert(getNumLocalVars() == 0 && "local ids not supported yet here");
 
   // Get the constraints common to both systems; these will be added as is to
   // the union.
   IntegerRelation commonCst(PresburgerSpace::getRelationSpace());
   getCommonConstraints(*this, otherCst, commonCst);
 
-  std::vector<SmallVector<int64_t, 8>> boundingLbs;
-  std::vector<SmallVector<int64_t, 8>> boundingUbs;
+  std::vector<SmallVector<MPInt, 8>> boundingLbs;
+  std::vector<SmallVector<MPInt, 8>> boundingUbs;
   boundingLbs.reserve(2 * getNumDimVars());
   boundingUbs.reserve(2 * getNumDimVars());
 
   // To hold lower and upper bounds for each dimension.
-  SmallVector<int64_t, 4> lb, otherLb, ub, otherUb;
+  SmallVector<MPInt, 4> lb, otherLb, ub, otherUb;
   // To compute min of lower bounds and max of upper bounds for each dimension.
-  SmallVector<int64_t, 4> minLb(getNumSymbolVars() + 1);
-  SmallVector<int64_t, 4> maxUb(getNumSymbolVars() + 1);
+  SmallVector<MPInt, 4> minLb(getNumSymbolVars() + 1);
+  SmallVector<MPInt, 4> maxUb(getNumSymbolVars() + 1);
   // To compute final new lower and upper bounds for the union.
-  SmallVector<int64_t, 8> newLb(getNumCols()), newUb(getNumCols());
+  SmallVector<MPInt, 8> newLb(getNumCols()), newUb(getNumCols());
 
-  int64_t lbFloorDivisor, otherLbFloorDivisor;
+  MPInt lbFloorDivisor, otherLbFloorDivisor;
   for (unsigned d = 0, e = getNumDimVars(); d < e; ++d) {
     auto extent = getConstantBoundOnDimSize(d, &lb, &lbFloorDivisor, &ub);
     if (!extent.has_value())
       // TODO: symbolic extents when necessary.
       // TODO: handle union if a dimension is unbounded.
       return failure();
 
     auto otherExtent = otherCst.getConstantBoundOnDimSize(
for (unsigned d = 0, e = getNumDimVars(); d < e; ++d) {
 
     // The divisor for lb, ub, otherLb, otherUb at this point is lbDivisor,
     // and so it's the divisor for newLb and newUb as well.
     newLb[d] = lbFloorDivisor;
     newUb[d] = -lbFloorDivisor;
     // Copy over the symbolic part + constant term.
     std::copy(minLb.begin(), minLb.end(), newLb.begin() + getNumDimVars());
     std::transform(newLb.begin() + getNumDimVars(), newLb.end(),
-                   newLb.begin() + getNumDimVars(), std::negate<int64_t>());
+                   newLb.begin() + getNumDimVars(), std::negate<MPInt>());
     std::copy(maxUb.begin(), maxUb.end(), newUb.begin() + getNumDimVars());
 
     boundingLbs.push_back(newLb);
     boundingUbs.push_back(newUb);
   }
 
   // Clear all constraints and add the lower/upper bounds for the bounding box.
   clearConstraints();

mlir/lib/Analysis/Presburger/LinearTransform.cpp

 // sourceCol. This brings M(row, targetCol) to the range [0, M(row, sourceCol)).
 // Apply the same column operation to otherMatrix, with the same integer
 // multiple.
 static void modEntryColumnOperation(Matrix &m, unsigned row, unsigned sourceCol,
                                     unsigned targetCol, Matrix &otherMatrix) {
   assert(m(row, sourceCol) != 0 && "Cannot divide by zero!");
   assert((m(row, sourceCol) > 0 && m(row, targetCol) > 0) &&
          "Operands must be positive!");
-  int64_t ratio = m(row, targetCol) / m(row, sourceCol);
+  MPInt ratio = m(row, targetCol) / m(row, sourceCol);
   m.addToColumn(sourceCol, targetCol, -ratio);
   otherMatrix.addToColumn(sourceCol, targetCol, -ratio);
 }
 
 std::pair<unsigned, LinearTransform>
 LinearTransform::makeTransformToColumnEchelon(Matrix m) {
   // We start with an identity result matrix and perform operations on m
   // until m is in column echelon form. We apply the same sequence of operations
LinearTransform::makeTransformToColumnEchelon(Matrix m) {
 
   return {echelonCol, LinearTransform(std::move(resultMatrix))};
 }
 
 IntegerRelation LinearTransform::applyTo(const IntegerRelation &rel) const {
   IntegerRelation result(rel.getSpace());
 
   for (unsigned i = 0, e = rel.getNumEqualities(); i < e; ++i) {
-    ArrayRef<int64_t> eq = rel.getEquality(i);
+    ArrayRef<MPInt> eq = rel.getEquality(i);
 
-    int64_t c = eq.back();
+    const MPInt &c = eq.back();
 
-    SmallVector<int64_t, 8> newEq = preMultiplyWithRow(eq.drop_back());
+    SmallVector<MPInt, 8> newEq = preMultiplyWithRow(eq.drop_back());
     newEq.push_back(c);
     result.addEquality(newEq);
   }
 
   for (unsigned i = 0, e = rel.getNumInequalities(); i < e; ++i) {
-    ArrayRef<int64_t> ineq = rel.getInequality(i);
+    ArrayRef<MPInt> ineq = rel.getInequality(i);
 
-    int64_t c = ineq.back();
+    const MPInt &c = ineq.back();
 
-    SmallVector<int64_t, 8> newIneq = preMultiplyWithRow(ineq.drop_back());
+    SmallVector<MPInt, 8> newIneq = preMultiplyWithRow(ineq.drop_back());
     newIneq.push_back(c);
     result.addInequality(newIneq);
   }
 
   return result;
 }

mlir/lib/Analysis/Presburger/Matrix.cpp

void Matrix::reserveRows(unsigned rows) {
   data.reserve(rows * nReservedColumns);
 }
 
 unsigned Matrix::appendExtraRow() {
   resizeVertically(nRows + 1);
   return nRows - 1;
 }
 
-unsigned Matrix::appendExtraRow(ArrayRef<int64_t> elems) {
+unsigned Matrix::appendExtraRow(ArrayRef<MPInt> elems) {
   assert(elems.size() == nColumns && "elems must match row length!");
   unsigned row = appendExtraRow();
   for (unsigned col = 0; col < nColumns; ++col)
     at(row, col) = elems[col];
   return row;
 }
 
 void Matrix::resizeHorizontally(unsigned newNColumns) {
void Matrix::swapColumns(unsigned column, unsigned otherColumn) {
   assert((column < getNumColumns() && otherColumn < getNumColumns()) &&
          "Given column out of bounds");
   if (column == otherColumn)
     return;
   for (unsigned row = 0; row < nRows; row++)
     std::swap(at(row, column), at(row, otherColumn));
 }
 
-MutableArrayRef<int64_t> Matrix::getRow(unsigned row) {
+MutableArrayRef<MPInt> Matrix::getRow(unsigned row) {
   return {&data[row * nReservedColumns], nColumns};
 }
 
-ArrayRef<int64_t> Matrix::getRow(unsigned row) const {
+ArrayRef<MPInt> Matrix::getRow(unsigned row) const {
   return {&data[row * nReservedColumns], nColumns};
 }
 
-void Matrix::setRow(unsigned row, ArrayRef<int64_t> elems) {
+void Matrix::setRow(unsigned row, ArrayRef<MPInt> elems) {
   assert(elems.size() == getNumColumns() &&
          "elems size must match row length!");
   for (unsigned i = 0, e = getNumColumns(); i < e; ++i)
     at(row, i) = elems[i];
 }
 
 void Matrix::insertColumn(unsigned pos) { insertColumns(pos, 1); }
 void Matrix::insertColumns(unsigned pos, unsigned count) {
   if (count == 0)
     return;
   assert(pos <= nColumns);
   unsigned oldNReservedColumns = nReservedColumns;
   if (nColumns + count > nReservedColumns) {
     nReservedColumns = llvm::NextPowerOf2(nColumns + count);
     data.resize(nRows * nReservedColumns);
   }
   nColumns += count;
 
   for (int ri = nRows - 1; ri >= 0; --ri) {
     for (int ci = nReservedColumns - 1; ci >= 0; --ci) {
       unsigned r = ri;
       unsigned c = ci;
-      int64_t &dest = data[r * nReservedColumns + c];
+      MPInt &dest = data[r * nReservedColumns + c];
       if (c >= nColumns) { // NOLINT
         // Out of bounds columns are zero-initialized. NOLINT because clang-tidy
         // complains about this branch being the same as the c >= pos one.
         //
         // TODO: this case can be skipped if the number of reserved columns
         // didn't change.
         dest = 0;
       } else if (c >= pos + count) {

 
 void Matrix::copyRow(unsigned sourceRow, unsigned targetRow) {
   if (sourceRow == targetRow)
     return;
   for (unsigned c = 0; c < nColumns; ++c)
     at(targetRow, c) = at(sourceRow, c);
 }
 
-void Matrix::fillRow(unsigned row, int64_t value) {
+void Matrix::fillRow(unsigned row, const MPInt &value) {
   for (unsigned col = 0; col < nColumns; ++col)
     at(row, col) = value;
 }
 
-void Matrix::addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
+void Matrix::addToRow(unsigned sourceRow, unsigned targetRow,
+                      const MPInt &scale) {
   if (scale == 0)
     return;
   for (unsigned col = 0; col < nColumns; ++col)
     at(targetRow, col) += scale * at(sourceRow, col);
 }
 
 void Matrix::addToColumn(unsigned sourceColumn, unsigned targetColumn,
-                         int64_t scale) {
+                         const MPInt &scale) {
   if (scale == 0)
     return;
   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
     at(row, targetColumn) += scale * at(row, sourceColumn);
 }
 
 void Matrix::negateColumn(unsigned column) {
   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
     at(row, column) = -at(row, column);
 }
 
 void Matrix::negateRow(unsigned row) {
   for (unsigned column = 0, e = getNumColumns(); column < e; ++column)
     at(row, column) = -at(row, column);
 }
 
-int64_t Matrix::normalizeRow(unsigned row, unsigned cols) {
+MPInt Matrix::normalizeRow(unsigned row, unsigned cols) {
   return normalizeRange(getRow(row).slice(0, cols));
 }
 
-int64_t Matrix::normalizeRow(unsigned row) {
+MPInt Matrix::normalizeRow(unsigned row) {
   return normalizeRow(row, getNumColumns());
 }
 
-SmallVector<int64_t, 8>
-Matrix::preMultiplyWithRow(ArrayRef<int64_t> rowVec) const {
+SmallVector<MPInt, 8> Matrix::preMultiplyWithRow(ArrayRef<MPInt> rowVec) const {
   assert(rowVec.size() == getNumRows() && "Invalid row vector dimension!");
 
-  SmallVector<int64_t, 8> result(getNumColumns(), 0);
+  SmallVector<MPInt, 8> result(getNumColumns(), MPInt(0));
   for (unsigned col = 0, e = getNumColumns(); col < e; ++col)
     for (unsigned i = 0, e = getNumRows(); i < e; ++i)
       result[col] += rowVec[i] * at(i, col);
   return result;
 }
 
-SmallVector<int64_t, 8>
-Matrix::postMultiplyWithColumn(ArrayRef<int64_t> colVec) const {
+SmallVector<MPInt, 8>
+Matrix::postMultiplyWithColumn(ArrayRef<MPInt> colVec) const {
   assert(getNumColumns() == colVec.size() &&
          "Invalid column vector dimension!");
 
-  SmallVector<int64_t, 8> result(getNumRows(), 0);
+  SmallVector<MPInt, 8> result(getNumRows(), MPInt(0));
   for (unsigned row = 0, e = getNumRows(); row < e; row++)
     for (unsigned i = 0, e = getNumColumns(); i < e; i++)
       result[row] += at(row, i) * colVec[i];
   return result;
 }
 
 void Matrix::print(raw_ostream &os) const {
   for (unsigned row = 0; row < nRows; ++row) {

mlir/lib/Analysis/Presburger/PWMAFunction.cpp

 #include "mlir/Analysis/Presburger/Simplex.h"
 
 using namespace mlir;
 using namespace presburger;
 
 // Return the result of subtracting the two given vectors pointwise.
 // The vectors must be of the same size.
 // e.g., [3, 4, 6] - [2, 5, 1] = [1, -1, 5].
-static SmallVector<int64_t, 8> subtract(ArrayRef<int64_t> vecA,
-                                        ArrayRef<int64_t> vecB) {
+static SmallVector<MPInt, 8> subtract(ArrayRef<MPInt> vecA,
+                                      ArrayRef<MPInt> vecB) {
   assert(vecA.size() == vecB.size() &&
          "Cannot subtract vectors of differing lengths!");
-  SmallVector<int64_t, 8> result;
+  SmallVector<MPInt, 8> result;
   result.reserve(vecA.size());
   for (unsigned i = 0, e = vecA.size(); i < e; ++i)
     result.push_back(vecA[i] - vecB[i]);
   return result;
 }
 
 PresburgerSet PWMAFunction::getDomain() const {
   PresburgerSet domain = PresburgerSet::getEmpty(getSpace());
   for (const MultiAffineFunction &piece : pieces)
     domain.unionInPlace(piece.getDomain());
   return domain;
 }
 
-Optional<SmallVector<int64_t, 8>>
-MultiAffineFunction::valueAt(ArrayRef<int64_t> point) const {
+Optional<SmallVector<MPInt, 8>>
+MultiAffineFunction::valueAt(ArrayRef<MPInt> point) const {
   assert(point.size() == domainSet.getNumDimAndSymbolVars() &&
          "Point has incorrect dimensionality!");
 
-  Optional<SmallVector<int64_t, 8>> maybeLocalValues =
+  Optional<SmallVector<MPInt, 8>> maybeLocalValues =
       getDomain().containsPointNoLocal(point);
   if (!maybeLocalValues)
     return {};
 
   // The point lies in the domain, so we need to compute the output value.
-  SmallVector<int64_t, 8> pointHomogenous{llvm::to_vector(point)};
+  SmallVector<MPInt, 8> pointHomogenous{llvm::to_vector(point)};
   // The given point didn't include the values of locals which the output is a
   // function of; we have computed one possible set of values and use them
   // here. The function is not allowed to have local vars that take more than
   // one possible value.
   pointHomogenous.append(*maybeLocalValues);
   // The matrix `output` has an affine expression in the ith row, corresponding
   // to the expression for the ith value in the output vector. The last column
   // of the matrix contains the constant term. Let v be the input point with
   // a 1 appended at the end. We can see that output * v gives the desired
   // output vector.
   pointHomogenous.emplace_back(1);
-  SmallVector<int64_t, 8> result =
-      output.postMultiplyWithColumn(pointHomogenous);
+  SmallVector<MPInt, 8> result = output.postMultiplyWithColumn(pointHomogenous);
   assert(result.size() == getNumOutputs());
   return result;
 }
 
-Optional<SmallVector<int64_t, 8>>
-PWMAFunction::valueAt(ArrayRef<int64_t> point) const {
+Optional<SmallVector<MPInt, 8>>
+PWMAFunction::valueAt(ArrayRef<MPInt> point) const {
   assert(point.size() == getNumInputs() &&
          "Point has incorrect dimensionality!");
   for (const MultiAffineFunction &piece : pieces)
-    if (Optional<SmallVector<int64_t, 8>> output = piece.valueAt(point))
+    if (Optional<SmallVector<MPInt, 8>> output = piece.valueAt(point))
       return output;
   return {};
 }
 
 void MultiAffineFunction::print(raw_ostream &os) const {
   os << "Domain:";
   domainSet.print(os);
   os << "Output:\n";
static PresburgerSet tiebreakLex(const MultiAffineFunction &mafA,
   //    (outA[0] = outB[0], ..., outA[n-2] = outB[n-2], outA[n-1] < outB[n-1])
   PresburgerSet result = PresburgerSet::getEmpty(compatibleSpace);
   IntegerPolyhedron levelSet(/*numReservedInequalities=*/1,
                              /*numReservedEqualities=*/mafA.getNumOutputs(),
                              /*numReservedCols=*/space.getNumVars() + 1, space);
   for (unsigned level = 0; level < mafA.getNumOutputs(); ++level) {
 
     // Create the expression `outA - outB` for this level.
-    SmallVector<int64_t, 8> subExpr =
+    SmallVector<MPInt, 8> subExpr =
         subtract(mafA.getOutputExpr(level), mafB.getOutputExpr(level));
 
     if (lexMin) {
       // For lexMin, we add an upper bound of -1:
       //        outA - outB <= -1
       //        outA <= outB - 1
       //        outA < outB
-      levelSet.addBound(IntegerPolyhedron::BoundType::UB, subExpr, -1);
+      levelSet.addBound(IntegerPolyhedron::BoundType::UB, subExpr, MPInt(-1));
     } else {
       // For lexMax, we add a lower bound of 1:
       //        outA - outB >= 1
       //        outA > outB + 1
       //        outA > outB
-      levelSet.addBound(IntegerPolyhedron::BoundType::LB, subExpr, 1);
+      levelSet.addBound(IntegerPolyhedron::BoundType::LB, subExpr, MPInt(1));
     }
 
     // Union the set with the result.
     result.unionInPlace(levelSet);
     // There is only 1 inequality in `levelSet`, so the index is always 0.
     levelSet.removeInequality(0);
     // Add equality `outA - outB == 0` for this level for next iteration.
     levelSet.addEquality(subExpr);

mlir/lib/Analysis/Presburger/PresburgerRelation.cpp

 PresburgerRelation::unionSet(const PresburgerRelation &set) const {
   assert(space.isCompatible(set.getSpace()) && "Spaces should match");
   PresburgerRelation result = *this;
   result.unionInPlace(set);
   return result;
 }
 
 /// A point is contained in the union iff any of the parts contain the point.
-bool PresburgerRelation::containsPoint(ArrayRef<int64_t> point) const {
+bool PresburgerRelation::containsPoint(ArrayRef<MPInt> point) const {
   return llvm::any_of(disjuncts, [&](const IntegerRelation &disjunct) {
     return (disjunct.containsPointNoLocal(point));
   });
 }
 
 PresburgerRelation
 PresburgerRelation::getUniverse(const PresburgerSpace &space) {
   PresburgerRelation result(space);

 ///
 /// Otherwise, it is then considered to index into the ineqs corresponding to
 /// eqs of `rel`, and it must hold that
 ///
 /// 0 <= idx - rel.getNumInequalities() < 2*getNumEqualities().
 ///
 /// For every eq `coeffs == 0` there are two possible ineqs to index into.
 /// The first is coeffs >= 0 and the second is coeffs <= 0.
-static SmallVector<int64_t, 8> getIneqCoeffsFromIdx(const IntegerRelation &rel,
-                                                    unsigned idx) {
+static SmallVector<MPInt, 8> getIneqCoeffsFromIdx(const IntegerRelation &rel,
   assert(idx < rel.getNumInequalities() + 2 * rel.getNumEqualities() &&
          "idx out of bounds!");
   if (idx < rel.getNumInequalities())
     return llvm::to_vector<8>(rel.getInequality(idx));
 
   idx -= rel.getNumInequalities();
-  ArrayRef<int64_t> eqCoeffs = rel.getEquality(idx / 2);
+  ArrayRef<MPInt> eqCoeffs = rel.getEquality(idx / 2);
 
   if (idx % 2 == 0)
     return llvm::to_vector<8>(eqCoeffs);
   return getNegatedCoeffs(eqCoeffs);
 }
 
 PresburgerRelation PresburgerRelation::computeReprWithOnlyDivLocals() const {
   if (hasOnlyDivLocals())
if (level == frames.size()) {
         // let the initial value of b when we first came to this level be b.
         //
         // b' is equal to b /\ s_i1 /\ s_i2 /\ ... /\ s_i{j-1} /\ ~s_ij.
         // We had previously recursed with the part where s_ij was not
         // satisfied; all further parts satisfy s_ij, so we rollback to the
         // state before adding this complement constraint, and add s_ij to b.
         simplex.rollback(frame.simplexSnapshot);
         b.truncate(frame.bCounts);
-        SmallVector<int64_t, 8> ineq =
+        SmallVector<MPInt, 8> ineq =
             getIneqCoeffsFromIdx(frame.sI, *frame.lastIneqProcessed);
         b.addInequality(ineq);
         simplex.addInequality(ineq);
       }
 
       if (frame.ineqsToProcess.empty()) {
         // No ineqs left to process; pop this level's frame and return.
         frames.pop_back();
         level = frames.size();
         continue;
       }
 
       // "Recurse" with the part where the ineq is not satisfied.
       frame.bCounts = b.getCounts();
       frame.simplexSnapshot = simplex.getSnapshot();
 
       unsigned idx = frame.ineqsToProcess.back();
-      SmallVector<int64_t, 8> ineq =
+      SmallVector<MPInt, 8> ineq =
           getComplementIneq(getIneqCoeffsFromIdx(frame.sI, idx));
       b.addInequality(ineq);
       simplex.addInequality(ineq);
 
       frame.ineqsToProcess.pop_back();
       frame.lastIneqProcessed = idx;
       ++level;
       continue;

 
 /// Return true if all the sets in the union are known to be integer empty,
 /// false otherwise.
 bool PresburgerRelation::isIntegerEmpty() const {
   // The set is empty iff all of the disjuncts are empty.
   return llvm::all_of(disjuncts, std::mem_fn(&IntegerRelation::isIntegerEmpty));
 }
 
-bool PresburgerRelation::findIntegerSample(SmallVectorImpl<int64_t> &sample) {
+bool PresburgerRelation::findIntegerSample(SmallVectorImpl<MPInt> &sample) {
   // A sample exists iff any of the disjuncts contains a sample.
   for (const IntegerRelation &disjunct : disjuncts) {
-    if (Optional<SmallVector<int64_t, 8>> opt = disjunct.findIntegerSample()) {
+    if (Optional<SmallVector<MPInt, 8>> opt = disjunct.findIntegerSample()) {
       sample = std::move(*opt);
       return true;
     }
   }
   return false;
 }
 
-Optional<uint64_t> PresburgerRelation::computeVolume() const {
+Optional<MPInt> PresburgerRelation::computeVolume() const {
   assert(getNumSymbolVars() == 0 && "Symbols are not yet supported!");
   // The sum of the volumes of the disjuncts is a valid overapproximation of the
   // volume of their union, even if they overlap.
-  uint64_t result = 0;
+  MPInt result(0);
   for (const IntegerRelation &disjunct : disjuncts) {
-    Optional<uint64_t> volume = disjunct.computeVolume();
+    Optional<MPInt> volume = disjunct.computeVolume();
     if (!volume)
       return {};
     result += *volume;
   }
   return result;
 }
 
 /// The SetCoalescer class contains all functionality concerning the coalesce
private:
   /// The current list of `IntegerRelation`s that the currently coalesced set is
   /// the union of.
   SmallVector<IntegerRelation, 2> disjuncts;
   /// The list of `Simplex`s constructed from the elements of `disjuncts`.
   SmallVector<Simplex, 2> simplices;
 
   /// The list of all inversed equalities during typing. This ensures that
   /// the constraints exist even after the typing function has concluded.
-  SmallVector<SmallVector<int64_t, 2>, 2> negEqs;
+  SmallVector<SmallVector<MPInt, 2>, 2> negEqs;
 
   /// `redundantIneqsA` is the inequalities of `a` that are redundant for `b`
   /// (similarly for `cuttingIneqsA`, `redundantIneqsB`, and `cuttingIneqsB`).
-  SmallVector<ArrayRef<int64_t>, 2> redundantIneqsA;
-  SmallVector<ArrayRef<int64_t>, 2> cuttingIneqsA;
+  SmallVector<ArrayRef<MPInt>, 2> redundantIneqsA;
+  SmallVector<ArrayRef<MPInt>, 2> cuttingIneqsA;
 
-  SmallVector<ArrayRef<int64_t>, 2> redundantIneqsB;
-  SmallVector<ArrayRef<int64_t>, 2> cuttingIneqsB;
+  SmallVector<ArrayRef<MPInt>, 2> redundantIneqsB;
+  SmallVector<ArrayRef<MPInt>, 2> cuttingIneqsB;
 
   /// Given a Simplex `simp` and one of its inequalities `ineq`, check
   /// that the facet of `simp` where `ineq` holds as an equality is contained
   /// within `a`.
-  bool isFacetContained(ArrayRef<int64_t> ineq, Simplex &simp);
+  bool isFacetContained(ArrayRef<MPInt> ineq, Simplex &simp);
 
   /// Removes redundant constraints from `disjunct`, adds it to `disjuncts` and
   /// removes the disjuncts at position `i` and `j`. Updates `simplices` to
   /// reflect the changes. `i` and `j` cannot be equal.
   void addCoalescedDisjunct(unsigned i, unsigned j,
                             const IntegerRelation &disjunct);
 
   /// Checks whether `a` and `b` can be combined in a convex sense, if there
   /// exist cutting inequalities.
   ///
   /// An example of this case:
   ///    ___________        ___________
   ///   /   /  |   /       /          /
   ///   \   \  |  /   ==>  \         /
   ///    \   \ | /          \       /
   ///     \___\|/            \_____/
   ///
   ///
   LogicalResult coalescePairCutCase(unsigned i, unsigned j);
 
   /// Types the inequality `ineq` according to its `IneqType` for `simp` into
   /// `redundantIneqsB` and `cuttingIneqsB`. Returns success, if no separate
   /// inequalities were encountered. Otherwise, returns failure.
-  LogicalResult typeInequality(ArrayRef<int64_t> ineq, Simplex &simp);
+  LogicalResult typeInequality(ArrayRef<MPInt> ineq, Simplex &simp);
 
   /// Types the equality `eq`, i.e. for `eq` == 0, types both `eq` >= 0 and
   /// -`eq` >= 0 according to their `IneqType` for `simp` into
   /// `redundantIneqsB` and `cuttingIneqsB`. Returns success, if no separate
   /// inequalities were encountered. Otherwise, returns failure.
-  LogicalResult typeEquality(ArrayRef<int64_t> eq, Simplex &simp);
+  LogicalResult typeEquality(ArrayRef<MPInt> eq, Simplex &simp);
 
   /// Replaces the element at position `i` with the last element and erases
   /// the last element for both `disjuncts` and `simplices`.
   void eraseDisjunct(unsigned i);
 
   /// Attempts to coalesce the two IntegerRelations at position `i` and `j`
   /// in `disjuncts` in-place. Returns whether the disjuncts were
   /// successfully coalesced. The simplices in `simplices` need to be the ones
for (unsigned i = 0, e = disjuncts.size(); i < e; ++i)
     newSet.unionInPlace(disjuncts[i]);
 
   return newSet;
 }
 
 /// Given a Simplex `simp` and one of its inequalities `ineq`, check
 /// that all inequalities of `cuttingIneqsB` are redundant for the facet of
 /// `simp` where `ineq` holds as an equality is contained within `a`.
-bool SetCoalescer::isFacetContained(ArrayRef<int64_t> ineq, Simplex &simp) {
+bool SetCoalescer::isFacetContained(ArrayRef<MPInt> ineq, Simplex &simp) {
   SimplexRollbackScopeExit scopeExit(simp);
   simp.addEquality(ineq);
-  return llvm::all_of(cuttingIneqsB, [&simp](ArrayRef<int64_t> curr) {
+  return llvm::all_of(cuttingIneqsB, [&simp](ArrayRef<MPInt> curr) {
     return simp.isRedundantInequality(curr);
   });
 }
 
 void SetCoalescer::addCoalescedDisjunct(unsigned i, unsigned j,
                                         const IntegerRelation &disjunct) {
   assert(i != j && "The indices must refer to different disjuncts");
   unsigned n = disjuncts.size();

 ///     \___\|/            \_____/
 ///
 ///
 LogicalResult SetCoalescer::coalescePairCutCase(unsigned i, unsigned j) {
   /// All inequalities of `b` need to be redundant. We already know that the
   /// redundant ones are, so only the cutting ones remain to be checked.
   Simplex &simp = simplices[i];
   IntegerRelation &disjunct = disjuncts[i];
-  if (llvm::any_of(cuttingIneqsA, [this, &simp](ArrayRef<int64_t> curr) {
+  if (llvm::any_of(cuttingIneqsA, [this, &simp](ArrayRef<MPInt> curr) {
         return !isFacetContained(curr, simp);
       }))
     return failure();
   IntegerRelation newSet(disjunct.getSpace());
 
-  for (ArrayRef<int64_t> curr : redundantIneqsA)
+  for (ArrayRef<MPInt> curr : redundantIneqsA)
     newSet.addInequality(curr);
 
-  for (ArrayRef<int64_t> curr : redundantIneqsB)
+  for (ArrayRef<MPInt> curr : redundantIneqsB)
     newSet.addInequality(curr);
 
   addCoalescedDisjunct(i, j, newSet);
   return success();
 }
 
-LogicalResult SetCoalescer::typeInequality(ArrayRef<int64_t> ineq,
+LogicalResult SetCoalescer::typeInequality(ArrayRef<MPInt> ineq,
                                            Simplex &simp) {
   Simplex::IneqType type = simp.findIneqType(ineq);
   if (type == Simplex::IneqType::Redundant)
     redundantIneqsB.push_back(ineq);
   else if (type == Simplex::IneqType::Cut)
     cuttingIneqsB.push_back(ineq);
   else
     return failure();
   return success();
 }
 
-LogicalResult SetCoalescer::typeEquality(ArrayRef<int64_t> eq, Simplex &simp) {
+LogicalResult SetCoalescer::typeEquality(ArrayRef<MPInt> eq, Simplex &simp) {
   if (typeInequality(eq, simp).failed())
     return failure();
   negEqs.push_back(getNegatedCoeffs(eq));
-  ArrayRef<int64_t> inv(negEqs.back());
+  ArrayRef<MPInt> inv(negEqs.back());
   if (typeInequality(inv, simp).failed())
     return failure();
   return success();
 }
 
 void SetCoalescer::eraseDisjunct(unsigned i) {
   assert(simplices.size() == disjuncts.size() &&
          "simplices and disjuncts must be equally as long");

mlir/lib/Analysis/Presburger/Simplex.cpp

 using namespace presburger;
 
 using Direction = Simplex::Direction;
 
 const int nullIndex = std::numeric_limits<int>::max();
 
 // Return a + scale*b;
 LLVM_ATTRIBUTE_UNUSED
-static SmallVector<int64_t, 8>
-scaleAndAddForAssert(ArrayRef<int64_t> a, int64_t scale, ArrayRef<int64_t> b) {
+static SmallVector<MPInt, 8>
+scaleAndAddForAssert(ArrayRef<MPInt> a, int64_t scale, ArrayRef<MPInt> b) {
   assert(a.size() == b.size());
-  SmallVector<int64_t, 8> res;
+  SmallVector<MPInt, 8> res;
   res.reserve(a.size());
   for (unsigned i = 0, e = a.size(); i < e; ++i)
     res.push_back(a[i] + scale * b[i]);
   return res;
 }
 
 SimplexBase::SimplexBase(unsigned nVar, bool mustUseBigM)
     : usingBigM(mustUseBigM), nRedundant(0), nSymbol(0),
unsigned SimplexBase::addZeroRow(bool makeRestricted) {
   undoLog.push_back(UndoLogEntry::RemoveLastConstraint);
   tableau(newRow, 0) = 1;
   return newRow;
 }
 
 /// Add a new row to the tableau corresponding to the given constant term and
 /// list of coefficients. The coefficients are specified as a vector of
 /// (variable index, coefficient) pairs.
-unsigned SimplexBase::addRow(ArrayRef<int64_t> coeffs, bool makeRestricted) {
+unsigned SimplexBase::addRow(ArrayRef<MPInt> coeffs, bool makeRestricted) {
   assert(coeffs.size() == var.size() + 1 &&
          "Incorrect number of coefficients!");
   assert(var.size() + getNumFixedCols() == getNumColumns() &&
          "inconsistent column count!");
 
   unsigned newRow = addZeroRow(makeRestricted);
   tableau(newRow, 1) = coeffs.back();
   if (usingBigM) {
     // When the lexicographic pivot rule is used, instead of the variables
     //
     // x, y, z ...
     //
     // we internally use the variables
     //
     // M, M + x, M + y, M + z, ...
     //
     // where M is the big M parameter. As such, when the user tries to add
     // a row ax + by + cz + d, we express it in terms of our internal variables
     // as -(a + b + c)M + a(M + x) + b(M + y) + c(M + z) + d.
     //
     // Symbols don't use the big M parameter since they do not get lex
     // optimized.
-    int64_t bigMCoeff = 0;
+    MPInt bigMCoeff(0);
     for (unsigned i = 0; i < coeffs.size() - 1; ++i)
       if (!var[i].isSymbol)
         bigMCoeff -= coeffs[i];
     // The coefficient to the big M parameter is stored in column 2.
     tableau(newRow, 2) = bigMCoeff;
   }
 
   // Process each given variable coefficient.
if (var[i].orientation == Orientation::Column) {
       tableau(newRow, pos) += coeffs[i] * tableau(newRow, 0);
       continue;
     }
 
     // If the variable is in row position, we need to add that row to the new
     // row, scaled by the coefficient for the variable, accounting for the two
     // rows potentially having different denominators. The new denominator is
     // the lcm of the two.
-    int64_t lcm = mlir::lcm(tableau(newRow, 0), tableau(pos, 0));
-    int64_t nRowCoeff = lcm / tableau(newRow, 0);
-    int64_t idxRowCoeff = coeffs[i] * (lcm / tableau(pos, 0));
+    MPInt lcm = presburger::lcm(tableau(newRow, 0), tableau(pos, 0));
+    MPInt nRowCoeff = lcm / tableau(newRow, 0);
+    MPInt idxRowCoeff = coeffs[i] * (lcm / tableau(pos, 0));
     tableau(newRow, 0) = lcm;
     for (unsigned col = 1, e = getNumColumns(); col < e; ++col)
       tableau(newRow, col) =
           nRowCoeff * tableau(newRow, col) + idxRowCoeff * tableau(pos, col);
   }
 
   tableau.normalizeRow(newRow);
   // Push to undo log along with the index of the new constraint.
   return con.size() - 1;
 }
 
 namespace {
-bool signMatchesDirection(int64_t elem, Direction direction) {
+bool signMatchesDirection(const MPInt &elem, Direction direction) {
   assert(elem != 0 && "elem should not be 0");
   return direction == Direction::Up ? elem > 0 : elem < 0;
 }
 
 Direction flippedDirection(Direction direction) {
   return direction == Direction::Up ? Direction::Down : Simplex::Direction::Up;
 }
 } // namespace

 /// is therefore non-negative as well.
 ///
 /// So we have
 /// ((b_1%d)y_1 + ... + (b_n%d)y_n - (-c%d))/d >= 0.
 ///
 /// The constraint is violated when added (it would be useless otherwise)
 /// so we immediately try to move it to a column.
 LogicalResult LexSimplexBase::addCut(unsigned row) {
-  int64_t d = tableau(row, 0);
+  MPInt d = tableau(row, 0);
   unsigned cutRow = addZeroRow(/*makeRestricted=*/true);
   tableau(cutRow, 0) = d;
   tableau(cutRow, 1) = -mod(-tableau(row, 1), d); // -c%d.
   tableau(cutRow, 2) = 0;
   for (unsigned col = 3 + nSymbol, e = getNumColumns(); col < e; ++col)
     tableau(cutRow, col) = mod(tableau(row, col), d); // b_i%d.
   return moveRowUnknownToColumn(cutRow);
 }
 
 Optional<unsigned> LexSimplex::maybeGetNonIntegralVarRow() const {
   for (const Unknown &u : var) {
     if (u.orientation == Orientation::Column)
       continue;
     // If the sample value is of the form (a/d)M + b/d, we need b to be
     // divisible by d. We assume M contains all possible
     // factors and is divisible by everything.
     unsigned row = u.pos;
     if (tableau(row, 1) % tableau(row, 0) != 0)
       return row;
   }
   return {};
 }
 
-MaybeOptimum<SmallVector<int64_t, 8>> LexSimplex::findIntegerLexMin() {
+MaybeOptimum<SmallVector<MPInt, 8>> LexSimplex::findIntegerLexMin() {
   // We first try to make the tableau consistent.
   if (restoreRationalConsistency().failed())
     return OptimumKind::Empty;
 
   // Then, if the sample value is integral, we are done.
   while (Optional<unsigned> maybeRow = maybeGetNonIntegralVarRow()) {
     // Otherwise, for the variable whose row has a non-integral sample value,
     // we add a cut, a constraint that remove this rational point
MaybeOptimum<SmallVector<MPInt, 8>> LexSimplex::findIntegerLexMin() {
   MaybeOptimum<SmallVector<Fraction, 8>> sample = getRationalSample();
   assert(!sample.isEmpty() && "If we reached here the sample should exist!");
   if (sample.isUnbounded())
     return OptimumKind::Unbounded;
   return llvm::to_vector<8>(
       llvm::map_range(*sample, std::mem_fn(&Fraction::getAsInteger)));
 }
 
-bool LexSimplex::isSeparateInequality(ArrayRef<int64_t> coeffs) {
+bool LexSimplex::isSeparateInequality(ArrayRef<MPInt> coeffs) {
   SimplexRollbackScopeExit scopeExit(*this);
   addInequality(coeffs);
   return findIntegerLexMin().isEmpty();
 }
 
-bool LexSimplex::isRedundantInequality(ArrayRef<int64_t> coeffs) {
+bool LexSimplex::isRedundantInequality(ArrayRef<MPInt> coeffs) {
   return isSeparateInequality(getComplementIneq(coeffs));
 }
 
-SmallVector<int64_t, 8>
+SmallVector<MPInt, 8>
 SymbolicLexSimplex::getSymbolicSampleNumerator(unsigned row) const {
-  SmallVector<int64_t, 8> sample;
+  SmallVector<MPInt, 8> sample;
   sample.reserve(nSymbol + 1);
   for (unsigned col = 3; col < 3 + nSymbol; ++col)
     sample.push_back(tableau(row, col));
   sample.push_back(tableau(row, 1));
   return sample;
 }
 
-SmallVector<int64_t, 8>
+SmallVector<MPInt, 8>
 SymbolicLexSimplex::getSymbolicSampleIneq(unsigned row) const {
-  SmallVector<int64_t, 8> sample = getSymbolicSampleNumerator(row);
+  SmallVector<MPInt, 8> sample = getSymbolicSampleNumerator(row);
   // The inequality is equivalent to the GCD-normalized one.
   normalizeRange(sample);
   return sample;
 }
 
 void LexSimplexBase::appendSymbol() {
   appendVariable();
   swapColumns(3 + nSymbol, getNumColumns() - 1);
   var.back().isSymbol = true;
   nSymbol++;
 }
 
-static bool isRangeDivisibleBy(ArrayRef<int64_t> range, int64_t divisor) {
+static bool isRangeDivisibleBy(ArrayRef<MPInt> range, const MPInt &divisor) {
   assert(divisor > 0 && "divisor must be positive!");
-  return llvm::all_of(range, [divisor](int64_t x) { return x % divisor == 0; });
+  return llvm::all_of(range,
+                      [divisor](const MPInt &x) { return x % divisor == 0; });
 }
 
 bool SymbolicLexSimplex::isSymbolicSampleIntegral(unsigned row) const {
-  int64_t denom = tableau(row, 0);
+  MPInt denom = tableau(row, 0);
   return tableau(row, 1) % denom == 0 &&
          isRangeDivisibleBy(tableau.getRow(row).slice(3, nSymbol), denom);
 }
 
 /// This proceeds similarly to LexSimplexBase::addCut(). We are given a row that
 /// has a symbolic sample value with fractional coefficients.
 ///
 /// Let the row be

 ///
 /// sum_i (b_i%d)y_i = (-c%d) + sum_i (-a_i%d)s_i - q*d + k*d for some integer k
 ///
 /// So the cut is
 /// (sum_i (b_i%d)y_i - (-c%d) - sum_i (-a_i%d)s_i + q*d)/d >= 0
 /// This constraint is violated when added so we immediately try to move it to a
 /// column.
 LogicalResult SymbolicLexSimplex::addSymbolicCut(unsigned row) {
-  int64_t d = tableau(row, 0);
+  MPInt d = tableau(row, 0);
   if (isRangeDivisibleBy(tableau.getRow(row).slice(3, nSymbol), d)) {
     // The coefficients of symbols in the symbol numerator are divisible
     // by the denominator, so we can add the constraint directly,
     // i.e., ignore the symbols and add a regular cut as in addCut().
     return addCut(row);
   }
 
   // Construct the division variable `q = ((-c%d) + sum_i (-a_i%d)s_i)/d`.
-  SmallVector<int64_t, 8> divCoeffs;
+  SmallVector<MPInt, 8> divCoeffs;
   divCoeffs.reserve(nSymbol + 1);
-  int64_t divDenom = d;
+  MPInt divDenom = d;
   for (unsigned col = 3; col < 3 + nSymbol; ++col)
     divCoeffs.push_back(mod(-tableau(row, col), divDenom)); // (-a_i%d)s_i
   divCoeffs.push_back(mod(-tableau(row, 1), divDenom));     // -c%d.
   normalizeDiv(divCoeffs, divDenom);
 
   domainSimplex.addDivisionVariable(divCoeffs, divDenom);
   domainPoly.addLocalFloorDiv(divCoeffs, divDenom);
 
for (const Unknown &u : var) {
 
     if (u.orientation == Orientation::Column) {
       // M + u has a sample value of zero so u has a sample value of -M, i.e,
       // unbounded.
       result.unboundedDomain.unionInPlace(domainPoly);
       return;
     }
 
-    int64_t denom = tableau(u.pos, 0);
+    MPInt denom = tableau(u.pos, 0);
     if (tableau(u.pos, 2) < denom) {
       // M + u has a sample value of fM + something, where f < 1, so
       // u = (f - 1)M + something, which has a negative coefficient for M,
       // and so is unbounded.
       result.unboundedDomain.unionInPlace(domainPoly);
       return;
     }
     assert(tableau(u.pos, 2) == denom &&
            "Coefficient of M should not be greater than 1!");
 
-    SmallVector<int64_t, 8> sample = getSymbolicSampleNumerator(u.pos);
-    for (int64_t &elem : sample) {
+    SmallVector<MPInt, 8> sample = getSymbolicSampleNumerator(u.pos);
+    for (MPInt &elem : sample) {
       assert(elem % denom == 0 && "coefficients must be integral!");
       elem /= denom;
     }
     output.appendExtraRow(sample);
   }
   result.lexmin.addPiece(domainPoly, output);
 }
 
if (level > stack.size()) {
       }
 
       if (doNonBranchingPivots().failed()) {
         // Could not find pivots for violated constraints; return.
         --level;
         continue;
       }
 
-      SmallVector<int64_t, 8> symbolicSample;
+      SmallVector<MPInt, 8> symbolicSample;
       unsigned splitRow = 0;
       for (unsigned e = getNumRows(); splitRow < e; ++splitRow) {
         if (tableau(splitRow, 2) > 0)
           continue;
         assert(tableau(splitRow, 2) == 0 &&
                "Non-branching pivots should have been handled already!");
 
         symbolicSample = getSymbolicSampleIneq(splitRow);
if (level == stack.size()) {
 
       // Drop the frame. We don't need it anymore.
       stack.pop_back();
 
       // Now we consider the part of the domain where the unknown `splitIndex`
       // was negative.
       assert(u.orientation == Orientation::Row &&
              "The split row should have been returned to row orientation!");
-      SmallVector<int64_t, 8> splitIneq =
+      SmallVector<MPInt, 8> splitIneq =
           getComplementIneq(getSymbolicSampleIneq(u.pos));
       normalizeRange(splitIneq);
       if (moveRowUnknownToColumn(u.pos).failed()) {
         // The unknown can't be made non-negative; return.
         --level;
         continue;
       }
 
unsigned LexSimplexBase::getLexMinPivotColumn(unsigned row, unsigned colA,
   // appropriate. This allows us to run the entire algorithm treating M
   // symbolically, as the pivot to be performed does not depend on the value
   // of M, so long as the sample value s is negative. Note that this is not
   // because of any special feature of M; by the same argument, we ignore the
   // symbols too. The caller ensure that the sample value s is negative for
   // all possible values of the symbols.
   auto getSampleChangeCoeffForVar = [this, row](unsigned col,
                                                 const Unknown &u) -> Fraction {
-    int64_t a = tableau(row, col);
+    MPInt a = tableau(row, col);
     if (u.orientation == Orientation::Column) {
       // Pivot column case.
       if (u.pos == col)
         return {1, a};
 
       // Non-pivot column case.
       return {0, 1};
     }
 
     // Pivot row case.
     if (u.pos == row)
       return {1, 1};
 
     // Non-pivot row case.
-    int64_t c = tableau(u.pos, col);
+    MPInt c = tableau(u.pos, col);
     return {c, a};
   };
 
   for (const Unknown &u : var) {
     Fraction changeA = getSampleChangeCoeffForVar(colA, u);
     Fraction changeB = getSampleChangeCoeffForVar(colB, u);
     if (changeA < changeB)
       return colA;

 /// we cannot decrease the sample value of restricted columns.
 ///
 /// If multiple columns are valid, we break ties by considering a lexicographic
 /// ordering where we prefer unknowns with lower index.
 Optional<SimplexBase::Pivot> Simplex::findPivot(int row,
                                                 Direction direction) const {
   Optional<unsigned> col;
   for (unsigned j = 2, e = getNumColumns(); j < e; ++j) {
-    int64_t elem = tableau(row, j);
+    MPInt elem = tableau(row, j);
     if (elem == 0)
       continue;
 
     if (unknownFromColumn(j).restricted &&
         !signMatchesDirection(elem, direction))
       continue;
     if (!col || colUnknown[j] < colUnknown[*col])
       col = j;

 Optional<unsigned> Simplex::findPivotRow(Optional<unsigned> skipRow,
                                          Direction direction,
                                          unsigned col) const {
   Optional<unsigned> retRow;
   // Initialize these to zero in order to silence a warning about retElem and
   // retConst being used uninitialized in the initialization of `diff` below. In
   // reality, these are always initialized when that line is reached since these
   // are set whenever retRow is set.
-  int64_t retElem = 0, retConst = 0;
+  MPInt retElem, retConst;
   for (unsigned row = nRedundant, e = getNumRows(); row < e; ++row) {
     if (skipRow && row == *skipRow)
       continue;
-    int64_t elem = tableau(row, col);
+    MPInt elem = tableau(row, col);
     if (elem == 0)
       continue;
     if (!unknownFromRow(row).restricted)
       continue;
     if (signMatchesDirection(elem, direction))
       continue;
-    int64_t constTerm = tableau(row, 1);
+    MPInt constTerm = tableau(row, 1);
 
     if (!retRow) {
       retRow = row;
       retElem = elem;
       retConst = constTerm;
       continue;
     }
 
-    int64_t diff = retConst * elem - constTerm * retElem;
+    MPInt diff = retConst * elem - constTerm * retElem;
     if ((diff == 0 && rowUnknown[row] < rowUnknown[*retRow]) ||
         (diff != 0 && !signMatchesDirection(diff, direction))) {
       retRow = row;
       retElem = elem;
       retConst = constTerm;
     }
   }
   return retRow;

 
 /// Add an inequality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
 /// is the current number of variables, then the corresponding inequality is
 /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} >= 0.
 ///
 /// We add the inequality and mark it as restricted. We then try to make its
 /// sample value non-negative. If this is not possible, the tableau has become
 /// empty and we mark it as such.
-void Simplex::addInequality(ArrayRef<int64_t> coeffs) {
+void Simplex::addInequality(ArrayRef<MPInt> coeffs) {
   unsigned conIndex = addRow(coeffs, /*makeRestricted=*/true);
   LogicalResult result = restoreRow(con[conIndex]);
   if (failed(result))
     markEmpty();
 }
 
 /// Add an equality to the tableau. If coeffs is c_0, c_1, ... c_n, where n
 /// is the current number of variables, then the corresponding equality is
 /// c_n + c_0*x_0 + c_1*x_1 + ... + c_{n-1}*x_{n-1} == 0.
 ///
 /// We simply add two opposing inequalities, which force the expression to
 /// be zero.
-void SimplexBase::addEquality(ArrayRef<int64_t> coeffs) {
+void SimplexBase::addEquality(ArrayRef<MPInt> coeffs) {
   addInequality(coeffs);
-  SmallVector<int64_t, 8> negatedCoeffs;
-  for (int64_t coeff : coeffs)
+  SmallVector<MPInt, 8> negatedCoeffs;
+  for (const MPInt &coeff : coeffs)
     negatedCoeffs.emplace_back(-coeff);
   addInequality(negatedCoeffs);
 }
 
 unsigned SimplexBase::getNumVariables() const { return var.size(); }
 unsigned SimplexBase::getNumConstraints() const { return con.size(); }
 
 /// Return a snapshot of the current state. This is just the current size of the

 }
 
 /// We add the usual floor division constraints:
 /// `0 <= coeffs - denom*q <= denom - 1`, where `q` is the new division
 /// variable.
 ///
 /// This constrains the remainder `coeffs - denom*q` to be in the
 /// range `[0, denom - 1]`, which fixes the integer value of the quotient `q`.
-void SimplexBase::addDivisionVariable(ArrayRef<int64_t> coeffs, int64_t denom) {
+void SimplexBase::addDivisionVariable(ArrayRef<MPInt> coeffs,
+                                      const MPInt &denom) {
   assert(denom != 0 && "Cannot divide by zero!\n");
   appendVariable();
 
-  SmallVector<int64_t, 8> ineq(coeffs.begin(), coeffs.end());
-  int64_t constTerm = ineq.back();
+  SmallVector<MPInt, 8> ineq(coeffs.begin(), coeffs.end());
+  MPInt constTerm = ineq.back();
   ineq.back() = -denom;
   ineq.push_back(constTerm);
   addInequality(ineq);
 
-  for (int64_t &coeff : ineq)
+  for (MPInt &coeff : ineq)
     coeff = -coeff;
   ineq.back() += denom - 1;
   addInequality(ineq);
 }
 
 void SimplexBase::appendVariable(unsigned count) {
   if (count == 0)
     return;
MaybeOptimum<Fraction> Simplex::computeRowOptimum(Direction direction,
   // The sample value is the entry in the constant column divided by the common
   // denominator for this row.
   return Fraction(tableau(row, 1), tableau(row, 0));
 }
 
 /// Compute the optimum of the specified expression in the specified direction,
 /// or None if it is unbounded.
 MaybeOptimum<Fraction> Simplex::computeOptimum(Direction direction,
-                                               ArrayRef<int64_t> coeffs) {
+                                               ArrayRef<MPInt> coeffs) {
   if (empty)
     return OptimumKind::Empty;
 
   SimplexRollbackScopeExit scopeExit(*this);
   unsigned conIndex = addRow(coeffs);
   unsigned row = con[conIndex].pos;
   return computeRowOptimum(direction, row);
 }
for (unsigned i = 0; i < count; ++i) {
     markRowRedundant(u);
   }
 }
 
 bool Simplex::isUnbounded() {
   if (empty)
     return false;
 
-  SmallVector<int64_t, 8> dir(var.size() + 1);
+  SmallVector<MPInt, 8> dir(var.size() + 1);
   for (unsigned i = 0; i < var.size(); ++i) {
     dir[i] = 1;
 
     if (computeOptimum(Direction::Up, dir).isUnbounded())
       return true;
 
     if (computeOptimum(Direction::Down, dir).isUnbounded())
       return true;
Optional<SmallVector<Fraction, 8>> Simplex::getRationalSample() const {
   // Push the sample value for each variable into the vector.
   for (const Unknown &u : var) {
     if (u.orientation == Orientation::Column) {
       // If the variable is in column position, its sample value is zero.
       sample.emplace_back(0, 1);
     } else {
       // If the variable is in row position, its sample value is the
       // entry in the constant column divided by the denominator.
-      int64_t denom = tableau(u.pos, 0);
+      MPInt denom = tableau(u.pos, 0);
       sample.emplace_back(tableau(u.pos, 1), denom);
     }
   }
   return sample;
 }
 
-void LexSimplexBase::addInequality(ArrayRef<int64_t> coeffs) {
+void LexSimplexBase::addInequality(ArrayRef<MPInt> coeffs) {
   addRow(coeffs, /*makeRestricted=*/true);
 }
 
 MaybeOptimum<SmallVector<Fraction, 8>> LexSimplex::getRationalSample() const {
   if (empty)
     return OptimumKind::Empty;
 
   SmallVector<Fraction, 8> sample;
   sample.reserve(var.size());
   // Push the sample value for each variable into the vector.
   for (const Unknown &u : var) {
     // When the big M parameter is being used, each variable x is represented
     // as M + x, so its sample value is finite if and only if it is of the
     // form 1*M + c. If the coefficient of M is not one then the sample value
     // is infinite, and we return an empty optional.
 
     if (u.orientation == Orientation::Column) {
       // If the variable is in column position, the sample value of M + x is
       // zero, so x = -M which is unbounded.
       return OptimumKind::Unbounded;
     }
 
     // If the variable is in row position, its sample value is the
     // entry in the constant column divided by the denominator.
-    int64_t denom = tableau(u.pos, 0);
+    MPInt denom = tableau(u.pos, 0);
     if (usingBigM)
       if (tableau(u.pos, 2) != denom)
         return OptimumKind::Unbounded;
     sample.emplace_back(tableau(u.pos, 1), denom);
   }
   return sample;
 }
 
-Optional<SmallVector<int64_t, 8>> Simplex::getSamplePointIfIntegral() const {
+Optional<SmallVector<MPInt, 8>> Simplex::getSamplePointIfIntegral() const {
   // If the tableau is empty, no sample point exists.
   if (empty)
     return {};
 
   // The value will always exist since the Simplex is non-empty.
   SmallVector<Fraction, 8> rationalSample = *getRationalSample();
-  SmallVector<int64_t, 8> integerSample;
+  SmallVector<MPInt, 8> integerSample;
   integerSample.reserve(var.size());
   for (const Fraction &coord : rationalSample) {
     // If the sample is non-integral, return None.
     if (coord.num % coord.den != 0)
       return {};
     integerSample.push_back(coord.num / coord.den);
   }
   return integerSample;

 public:
   GBRSimplex(const Simplex &originalSimplex)
       : simplex(Simplex::makeProduct(originalSimplex, originalSimplex)),
         simplexConstraintOffset(simplex.getNumConstraints()) {}
 
   /// Add an equality dotProduct(dir, x - y) == 0.
   /// First pushes a snapshot for the current simplex state to the stack so
   /// that this can be rolled back later.
-  void addEqualityForDirection(ArrayRef<int64_t> dir) {
-    assert(llvm::any_of(dir, [](int64_t x) { return x != 0; }) &&
+  void addEqualityForDirection(ArrayRef<MPInt> dir) {
+    assert(llvm::any_of(dir, [](const MPInt &x) { return x != 0; }) &&
            "Direction passed is the zero vector!");
     snapshotStack.push_back(simplex.getSnapshot());
     simplex.addEquality(getCoeffsForDirection(dir));
   }
   /// Compute max(dotProduct(dir, x - y)).
-  Fraction computeWidth(ArrayRef<int64_t> dir) {
+  Fraction computeWidth(ArrayRef<MPInt> dir) {
     MaybeOptimum<Fraction> maybeWidth =
         simplex.computeOptimum(Direction::Up, getCoeffsForDirection(dir));
     assert(maybeWidth.isBounded() && "Width should be bounded!");
     return *maybeWidth;
   }
 
   /// Compute max(dotProduct(dir, x - y)) and save the dual variables for only
   /// the direction equalities to `dual`.
-  Fraction computeWidthAndDuals(ArrayRef<int64_t> dir,
-                                SmallVectorImpl<int64_t> &dual,
-                                int64_t &dualDenom) {
+  Fraction computeWidthAndDuals(ArrayRef<MPInt> dir,
+                                SmallVectorImpl<MPInt> &dual,
+                                MPInt &dualDenom) {
     // We can't just call into computeWidth or computeOptimum since we need to
     // access the state of the tableau after computing the optimum, and these
     // functions rollback the insertion of the objective function into the
     // tableau before returning. We instead add a row for the objective function
     // ourselves, call into computeOptimum, compute the duals from the tableau
     // state, and finally rollback the addition of the row before returning.
     SimplexRollbackScopeExit scopeExit(simplex);
     unsigned conIndex = simplex.addRow(getCoeffsForDirection(dir));
void removeLastEquality() {
     snapshotStack.pop_back();
   }
 
 private:
   /// Returns coefficients of the expression 'dot_product(dir, x - y)',
   /// i.e.,   dir_1 * x_1 + dir_2 * x_2 + ... + dir_n * x_n
   ///       - dir_1 * y_1 - dir_2 * y_2 - ... - dir_n * y_n,
   /// where n is the dimension of the original polytope.
-  SmallVector<int64_t, 8> getCoeffsForDirection(ArrayRef<int64_t> dir) {
+  SmallVector<MPInt, 8> getCoeffsForDirection(ArrayRef<MPInt> dir) {
     assert(2 * dir.size() == simplex.getNumVariables() &&
            "Direction vector has wrong dimensionality");
-    SmallVector<int64_t, 8> coeffs(dir.begin(), dir.end());
+    SmallVector<MPInt, 8> coeffs(dir.begin(), dir.end());
     coeffs.reserve(2 * dir.size());
-    for (int64_t coeff : dir)
+    for (const MPInt &coeff : dir)
       coeffs.push_back(-coeff);
     coeffs.emplace_back(0); // constant term
     return coeffs;
   }
 
   Simplex simplex;
   /// The first index of the equality constraints, the index immediately after
   /// the last constraint in the initial product simplex.

 void Simplex::reduceBasis(Matrix &basis, unsigned level) {
   const Fraction epsilon(3, 4);
 
   if (level == basis.getNumRows() - 1)
     return;
 
   GBRSimplex gbrSimplex(*this);
   SmallVector<Fraction, 8> width;
-  SmallVector<int64_t, 8> dual;
-  int64_t dualDenom;
+  SmallVector<MPInt, 8> dual;
+  MPInt dualDenom;
 
   // Finds the value of u that minimizes width_i(b_{i+1} + u*b_i), caches the
   // duals from this computation, sets b_{i+1} to b_{i+1} + u*b_i, and returns
   // the new value of width_i(b_{i+1}).
   //
   // If dual_i is not an integer, the minimizing value must be either
   // floor(dual_i) or ceil(dual_i). We compute the expression for both and
   // choose the minimizing value.
   //
   // If dual_i is an integer, we don't need to perform these computations. We
   // know that in this case,
   //   a) u = dual_i.
   //   b) one can show that dual_j for j < i are the same duals we would have
   //      gotten from computing width_i(b_{i + 1} + u*b_i), so the correct duals
   //      are the ones already in the cache.
   //   c) width_i(b_{i+1} + u*b_i) = min_{alpha} width_i(b_{i+1} + alpha * b_i),
   //   which
   //      one can show is equal to width_{i+1}(b_{i+1}). The latter value must
   //      be in the cache, so we get it from there and return it.
   auto updateBasisWithUAndGetFCandidate = [&](unsigned i) -> Fraction {
     assert(i < level + dual.size() && "dual_i is not known!");
 
-    int64_t u = floorDiv(dual[i - level], dualDenom);
+    MPInt u = floorDiv(dual[i - level], dualDenom);
     basis.addToRow(i, i + 1, u);
     if (dual[i - level] % dualDenom != 0) {
-      SmallVector<int64_t, 8> candidateDual[2];
-      int64_t candidateDualDenom[2];
+      SmallVector<MPInt, 8> candidateDual[2];
+      MPInt candidateDualDenom[2];
       Fraction widthI[2];
 
       // Initially u is floor(dual) and basis reflects this.
       widthI[0] = gbrSimplex.computeWidthAndDuals(
           basis.getRow(i + 1), candidateDual[0], candidateDualDenom[0]);
 
       // Now try ceil(dual), i.e. floor(dual) + 1.
       ++u;

 /// the previous level.
 ///
 /// If we reach the last level where all the variables have been assigned values
 /// already, then we simply return the current sample point if it is integral,
 /// and go back to the previous level otherwise.
 ///
 /// To avoid potentially arbitrarily large recursion depths leading to stack
 /// overflows, this algorithm is implemented iteratively.
-Optional<SmallVector<int64_t, 8>> Simplex::findIntegerSample() {
+Optional<SmallVector<MPInt, 8>> Simplex::findIntegerSample() {
   if (empty)
     return {};
 
   unsigned nDims = var.size();
   Matrix basis = Matrix::identity(nDims);
 
   unsigned level = 0;
   // The snapshot just before constraining a direction to a value at each level.
   SmallVector<unsigned, 8> snapshotStack;
   // The maximum value in the range of the direction for each level.
-  SmallVector<int64_t, 8> upperBoundStack;
+  SmallVector<MPInt, 8> upperBoundStack;
   // The next value to try constraining the basis vector to at each level.
-  SmallVector<int64_t, 8> nextValueStack;
+  SmallVector<MPInt, 8> nextValueStack;
 
   snapshotStack.reserve(basis.getNumRows());
   upperBoundStack.reserve(basis.getNumRows());
   nextValueStack.reserve(basis.getNumRows());
   while (level != -1u) {
     if (level == basis.getNumRows()) {
       // We've assigned values to all variables. Return if we have a sample,
       // or go back up to the previous level otherwise.
       if (auto maybeSample = getSamplePointIfIntegral())
         return maybeSample;
       level--;
       continue;
     }
 
     if (level >= upperBoundStack.size()) {
       // We haven't populated the stack values for this level yet, so we have
       // just come down a level ("recursed"). Find the lower and upper bounds.
       // If there is more than one integer point in the range, perform
       // generalized basis reduction.
-      SmallVector<int64_t, 8> basisCoeffs =
+      SmallVector<MPInt, 8> basisCoeffs =
           llvm::to_vector<8>(basis.getRow(level));
       basisCoeffs.emplace_back(0);
 
-      MaybeOptimum<int64_t> minRoundedUp, maxRoundedDown;
+      MaybeOptimum<MPInt> minRoundedUp, maxRoundedDown;
       std::tie(minRoundedUp, maxRoundedDown) =
           computeIntegerBounds(basisCoeffs);
 
       // We don't have any integer values in the range.
       // Pop the stack and return up a level.
       if (minRoundedUp.isEmpty() || maxRoundedDown.isEmpty()) {
         assert((minRoundedUp.isEmpty() && maxRoundedDown.isEmpty()) &&
                "If one bound is empty, both should be.");
assert((snapshotStack.size() - 1 == level &&
             nextValueStack.size() - 1 == level &&
             upperBoundStack.size() - 1 == level) &&
            "Mismatched variable stack sizes!");
 
     // Whether we "recursed" or "returned" from a lower level, we rollback
     // to the snapshot of the starting state at this level. (in the "recursed"
     // case this has no effect)
     rollback(snapshotStack.back());
-    int64_t nextValue = nextValueStack.back();
+    MPInt nextValue = nextValueStack.back();
     ++nextValueStack.back();
     if (nextValue > upperBoundStack.back()) {
       // We have exhausted the range and found no solution. Pop the stack and
       // return up a level.
       snapshotStack.pop_back();
       nextValueStack.pop_back();
       upperBoundStack.pop_back();
       level--;
       continue;
     }
 
     // Try the next value in the range and "recurse" into the next level.
-    SmallVector<int64_t, 8> basisCoeffs(basis.getRow(level).begin(),
-                                        basis.getRow(level).end());
+    SmallVector<MPInt, 8> basisCoeffs(basis.getRow(level).begin(),
     basisCoeffs.push_back(-nextValue);
     addEquality(basisCoeffs);
     level++;
   }
 
   return {};
 }
 
 /// Compute the minimum and maximum integer values the expression can take. We
 /// compute each separately.
-std::pair<MaybeOptimum<int64_t>, MaybeOptimum<int64_t>>
-Simplex::computeIntegerBounds(ArrayRef<int64_t> coeffs) {
-  MaybeOptimum<int64_t> minRoundedUp(
+std::pair<MaybeOptimum<MPInt>, MaybeOptimum<MPInt>>
+Simplex::computeIntegerBounds(ArrayRef<MPInt> coeffs) {
+  MaybeOptimum<MPInt> minRoundedUp(
       computeOptimum(Simplex::Direction::Down, coeffs).map(ceil));
-  MaybeOptimum<int64_t> maxRoundedDown(
+  MaybeOptimum<MPInt> maxRoundedDown(
       computeOptimum(Simplex::Direction::Up, coeffs).map(floor));
   return {minRoundedUp, maxRoundedDown};
 }
 
 void SimplexBase::print(raw_ostream &os) const {
   os << "rows = " << getNumRows() << ", columns = " << getNumColumns() << "\n";
   if (empty)
     os << "Simplex marked empty!\n";

 /// Internally, this computes the minimum and the maximum the inequality with
 /// coefficients `coeffs` can take. If the minimum is >= 0, the inequality holds
 /// for all points in the polytope, so it is redundant.  If the minimum is <= 0
 /// and the maximum is >= 0, the points in between the minimum and the
 /// inequality do not satisfy it, the points in between the inequality and the
 /// maximum satisfy it. Hence, it is a cut inequality. If both are < 0, no
 /// points of the polytope satisfy the inequality, which means it is a separate
 /// inequality.
-Simplex::IneqType Simplex::findIneqType(ArrayRef<int64_t> coeffs) {
+Simplex::IneqType Simplex::findIneqType(ArrayRef<MPInt> coeffs) {
   MaybeOptimum<Fraction> minimum = computeOptimum(Direction::Down, coeffs);
   if (minimum.isBounded() && *minimum >= Fraction(0, 1)) {
     return IneqType::Redundant;
   }
   MaybeOptimum<Fraction> maximum = computeOptimum(Direction::Up, coeffs);
   if ((!minimum.isBounded() || *minimum <= Fraction(0, 1)) &&
       (!maximum.isBounded() || *maximum >= Fraction(0, 1))) {
     return IneqType::Cut;
   }
   return IneqType::Separate;
 }
 
 /// Checks whether the type of the inequality with coefficients `coeffs`
 /// is Redundant.
-bool Simplex::isRedundantInequality(ArrayRef<int64_t> coeffs) {
+bool Simplex::isRedundantInequality(ArrayRef<MPInt> coeffs) {
   assert(!empty &&
          "It is not meaningful to ask about redundancy in an empty set!");
   return findIneqType(coeffs) == IneqType::Redundant;
 }
 
 /// Check whether the equality given by `coeffs == 0` is redundant given
 /// the existing constraints. This is redundant when `coeffs` is already
 /// always zero under the existing constraints. `coeffs` is always zero
 /// when the minimum and maximum value that `coeffs` can take are both zero.
-bool Simplex::isRedundantEquality(ArrayRef<int64_t> coeffs) {
+bool Simplex::isRedundantEquality(ArrayRef<MPInt> coeffs) {
   assert(!empty &&
          "It is not meaningful to ask about redundancy in an empty set!");
   MaybeOptimum<Fraction> minimum = computeOptimum(Direction::Down, coeffs);
   MaybeOptimum<Fraction> maximum = computeOptimum(Direction::Up, coeffs);
   assert((!minimum.isEmpty() && !maximum.isEmpty()) &&
          "Optima should be non-empty for a non-empty set");
   return minimum.isBounded() && maximum.isBounded() &&
          *maximum == Fraction(0, 1) && *minimum == Fraction(0, 1);
 }

mlir/lib/Analysis/Presburger/Utils.cpp

 //===- Utils.cpp - General utilities for Presburger library ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Utility functions required by the Presburger Library.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/Analysis/Presburger/Utils.h"
 #include "mlir/Analysis/Presburger/IntegerRelation.h"
+#include "mlir/Analysis/Presburger/MPInt.h"
 #include "mlir/Support/LogicalResult.h"
 #include "mlir/Support/MathExtras.h"
 
 using namespace mlir;
 using namespace presburger;
 
 /// Normalize a division's `dividend` and the `divisor` by their GCD. For
 /// example: if the dividend and divisor are [2,0,4] and 4 respectively,
 /// they get normalized to [1,0,2] and 2.
-static void normalizeDivisionByGCD(MutableArrayRef<int64_t> dividend,
-                                   unsigned &divisor) {
+static void normalizeDivisionByGCD(MutableArrayRef<MPInt> dividend,
+                                   MPInt &divisor) {
   if (divisor == 0 || dividend.empty())
     return;
   // We take the absolute value of dividend's coefficients to make sure that
   // `gcd` is positive.
-  int64_t gcd =
-      llvm::greatestCommonDivisor(std::abs(dividend.front()), int64_t(divisor));
+  MPInt gcd = presburger::gcd(abs(dividend.front()), divisor);
 
   // The reason for ignoring the constant term is as follows.
   // For a division:
   //      floor((a + m.f(x))/(m.d))
   // It can be replaced by:
   //      floor((floor(a/m) + f(x))/d)
   // Since `{a/m}/d` in the dividend satisfies 0 <= {a/m}/d < 1/d, it will not
   // influence the result of the floor division and thus, can be ignored.
   for (size_t i = 1, m = dividend.size() - 1; i < m; i++) {
-    gcd = llvm::greatestCommonDivisor(std::abs(dividend[i]), gcd);
+    gcd = presburger::gcd(abs(dividend[i]), gcd);
     if (gcd == 1)
       return;
   }
 
   // Normalize the dividend and the denominator.
   std::transform(dividend.begin(), dividend.end(), dividend.begin(),
-                 [gcd](int64_t &n) { return floorDiv(n, gcd); });
+                 [gcd](MPInt &n) { return floorDiv(n, gcd); });
   divisor /= gcd;
 }
 
 /// Check if the pos^th variable can be represented as a division using upper
 /// bound inequality at position `ubIneq` and lower bound inequality at position
 /// `lbIneq`.
 ///
 /// Let `var` be the pos^th variable, then `var` is equivalent to

 ///     divisor * var - expr + (divisor - 1) >= 0  <-- Lower bound for 'var'
 ///    -divisor * var + expr - c             >= 0  <-- Upper bound for 'var'
 ///
 /// If successful, `expr` is set to dividend of the division and `divisor` is
 /// set to the denominator of the division. The final division expression is
 /// normalized by GCD.
 static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
                                 unsigned ubIneq, unsigned lbIneq,
-                                MutableArrayRef<int64_t> expr,
-                                unsigned &divisor) {
+                                MutableArrayRef<MPInt> expr, MPInt &divisor) {
 
   assert(pos <= cst.getNumVars() && "Invalid variable position");
   assert(ubIneq <= cst.getNumInequalities() &&
          "Invalid upper bound inequality position");
   assert(lbIneq <= cst.getNumInequalities() &&
          "Invalid upper bound inequality position");
   assert(expr.size() == cst.getNumCols() && "Invalid expression size");
 
   // Extract divisor from the lower bound.
   divisor = cst.atIneq(lbIneq, pos);
 
   // First, check if the constraints are opposite of each other except the
   // constant term.
   unsigned i = 0, e = 0;
   for (i = 0, e = cst.getNumVars(); i < e; ++i)
     if (cst.atIneq(ubIneq, i) != -cst.atIneq(lbIneq, i))
       break;
 
   if (i < e)
     return failure();
 
   // Then, check if the constant term is of the proper form.
   // Due to the form of the upper/lower bound inequalities, the sum of their
   // constants is `divisor - 1 - c`. From this, we can extract c:
-  int64_t constantSum = cst.atIneq(lbIneq, cst.getNumCols() - 1) +
-                        cst.atIneq(ubIneq, cst.getNumCols() - 1);
-  int64_t c = divisor - 1 - constantSum;
+  MPInt constantSum = cst.atIneq(lbIneq, cst.getNumCols() - 1) +
+  MPInt c = divisor - 1 - constantSum;
 
   // Check if `c` satisfies the condition `0 <= c <= divisor - 1`. This also
   // implictly checks that `divisor` is positive.
   if (!(0 <= c && c <= divisor - 1)) // NOLINT
     return failure();
 
   // The inequality pair can be used to extract the division.
   // Set `expr` to the dividend of the division except the constant term, which

 ///     32*k == 16*i + j - 31                 <-- `eqInd` for 'k'
 ///     expr = 16*i + j - 31, divisor = 32
 ///     k = (16*i + j - 31) floordiv 32
 ///
 /// If successful, `expr` is set to dividend of the division and `divisor` is
 /// set to the denominator of the division. The final division expression is
 /// normalized by GCD.
 static LogicalResult getDivRepr(const IntegerRelation &cst, unsigned pos,
-                                unsigned eqInd, MutableArrayRef<int64_t> expr,
-                                unsigned &divisor) {
+                                unsigned eqInd, MutableArrayRef<MPInt> expr,
+                                MPInt &divisor) {
 
   assert(pos <= cst.getNumVars() && "Invalid variable position");
   assert(eqInd <= cst.getNumEqualities() && "Invalid equality position");
   assert(expr.size() == cst.getNumCols() && "Invalid expression size");
 
   // Extract divisor, the divisor can be negative and hence its sign information
   // is stored in `signDiv` to reverse the sign of dividend's coefficients.
   // Equality must involve the pos-th variable and hence `tempDiv` != 0.
-  int64_t tempDiv = cst.atEq(eqInd, pos);
+  MPInt tempDiv = cst.atEq(eqInd, pos);
   if (tempDiv == 0)
     return failure();
-  int64_t signDiv = tempDiv < 0 ? -1 : 1;
+  int signDiv = tempDiv < 0 ? -1 : 1;
 
   // The divisor is always a positive integer.
   divisor = tempDiv * signDiv;
 
   for (unsigned i = 0, e = cst.getNumVars(); i < e; ++i)
     if (i != pos)
       expr[i] = -signDiv * cst.atEq(eqInd, i);
 
   expr.back() = -signDiv * cst.atEq(eqInd, cst.getNumCols() - 1);
   normalizeDivisionByGCD(expr, divisor);
 
   return success();
 }
 
 // Returns `false` if the constraints depends on a variable for which an
 // explicit representation has not been found yet, otherwise returns `true`.
 static bool checkExplicitRepresentation(const IntegerRelation &cst,
                                         ArrayRef<bool> foundRepr,
-                                        ArrayRef<int64_t> dividend,
+                                        ArrayRef<MPInt> dividend,
                                         unsigned pos) {
   // Exit to avoid circular dependencies between divisions.
   for (unsigned c = 0, e = cst.getNumVars(); c < e; ++c) {
     if (c == pos)
       continue;
 
     if (!foundRepr[c] && dividend[c] != 0) {
       // Expression can't be constructed as it depends on a yet unknown

 /// function of other variables (where the divisor is a positive constant).
 /// `foundRepr` contains a boolean for each variable indicating if the
 /// explicit representation for that variable has already been computed.
 /// Returns the `MaybeLocalRepr` struct which contains the indices of the
 /// constraints that can be expressed as a floordiv of an affine function. If
 /// the representation could be computed, `dividend` and `denominator` are set.
 /// If the representation could not be computed, the kind attribute in
 /// `MaybeLocalRepr` is set to None.
-MaybeLocalRepr presburger::computeSingleVarRepr(
-    const IntegerRelation &cst, ArrayRef<bool> foundRepr, unsigned pos,
-    MutableArrayRef<int64_t> dividend, unsigned &divisor) {
+MaybeLocalRepr presburger::computeSingleVarRepr(const IntegerRelation &cst,
+                                                ArrayRef<bool> foundRepr,
+                                                unsigned pos,
+                                                MutableArrayRef<MPInt> dividend,
+                                                MPInt &divisor) {
   assert(pos < cst.getNumVars() && "invalid position");
   assert(foundRepr.size() == cst.getNumVars() &&
          "Size of foundRepr does not match total number of variables");
   assert(dividend.size() == cst.getNumCols() && "Invalid dividend size");
 
   SmallVector<unsigned, 4> lbIndices, ubIndices, eqIndices;
   cst.getLowerAndUpperBoundIndices(pos, &lbIndices, &ubIndices, &eqIndices);
   MaybeLocalRepr repr{};
for (unsigned eqPos : eqIndices) {
 
     repr.kind = ReprKind::Equality;
     repr.repr.equalityIdx = eqPos;
     return repr;
   }
   return repr;
 }
 
+MaybeLocalRepr presburger::computeSingleVarRepr(
+    const IntegerRelation &cst, ArrayRef<bool> foundRepr, unsigned pos,
+    SmallVector<int64_t, 8> &dividend, unsigned &divisor) {
+  SmallVector<MPInt, 8> dividendMPInt(cst.getNumCols());
+  MPInt divisorMPInt;
+  MaybeLocalRepr result =
+      computeSingleVarRepr(cst, foundRepr, pos, dividendMPInt, divisorMPInt);
+  dividend = getInt64Vec(dividendMPInt);
+  divisor = unsigned(int64_t(divisorMPInt));
+  return result;
+}
+
 llvm::SmallBitVector presburger::getSubrangeBitVector(unsigned len,
                                                       unsigned setOffset,
                                                       unsigned numSet) {
   llvm::SmallBitVector vec(len, false);
   vec.set(setOffset, setOffset + numSet);
   return vec;
 }
 
for (unsigned i = initLocals, e = divsB.getNumDivs(); i < e; ++i) {
     divsA.getDenom(i) = divsB.getDenom(i);
   }
 
   // Remove duplicate divisions from divsA. The removing duplicate divisions
   // call, calls `merge` to effectively merge divisions in relA and relB.
   divsA.removeDuplicateDivs(merge);
 }
 
-SmallVector<int64_t, 8> presburger::getDivUpperBound(ArrayRef<int64_t> dividend,
-                                                     int64_t divisor,
-                                                     unsigned localVarIdx) {
+SmallVector<MPInt, 8> presburger::getDivUpperBound(ArrayRef<MPInt> dividend,
+                                                   const MPInt &divisor,
   assert(dividend[localVarIdx] == 0 &&
          "Local to be set to division must have zero coeff!");
-  SmallVector<int64_t, 8> ineq(dividend.begin(), dividend.end());
+  SmallVector<MPInt, 8> ineq(dividend.begin(), dividend.end());
   ineq[localVarIdx] = -divisor;
   return ineq;
 }
 
-SmallVector<int64_t, 8> presburger::getDivLowerBound(ArrayRef<int64_t> dividend,
-                                                     int64_t divisor,
-                                                     unsigned localVarIdx) {
+SmallVector<MPInt, 8> presburger::getDivLowerBound(ArrayRef<MPInt> dividend,
+                                                   const MPInt &divisor,
   assert(dividend[localVarIdx] == 0 &&
          "Local to be set to division must have zero coeff!");
-  SmallVector<int64_t, 8> ineq(dividend.size());
+  SmallVector<MPInt, 8> ineq(dividend.size());
   std::transform(dividend.begin(), dividend.end(), ineq.begin(),
-                 std::negate<int64_t>());
+                 std::negate<MPInt>());
   ineq[localVarIdx] = divisor;
   ineq.back() += divisor - 1;
   return ineq;
 }
 
-int64_t presburger::gcdRange(ArrayRef<int64_t> range) {
-  int64_t gcd = 0;
-  for (int64_t elem : range) {
-    gcd = llvm::GreatestCommonDivisor64(gcd, std::abs(elem));
+MPInt presburger::gcdRange(ArrayRef<MPInt> range) {
+  MPInt gcd(0);
+  for (const MPInt &elem : range) {
+    gcd = presburger::gcd(gcd, abs(elem));
     if (gcd == 1)
       return gcd;
   }
   return gcd;
 }
 
-int64_t presburger::normalizeRange(MutableArrayRef<int64_t> range) {
-  int64_t gcd = gcdRange(range);
-  if (gcd == 0 || gcd == 1)
+MPInt presburger::normalizeRange(MutableArrayRef<MPInt> range) {
+  MPInt gcd = gcdRange(range);
+  if ((gcd == 0) || (gcd == 1))
     return gcd;
-  for (int64_t &elem : range)
+  for (MPInt &elem : range)
     elem /= gcd;
   return gcd;
 }
 
-void presburger::normalizeDiv(MutableArrayRef<int64_t> num, int64_t &denom) {
+void presburger::normalizeDiv(MutableArrayRef<MPInt> num, MPInt &denom) {
   assert(denom > 0 && "denom must be positive!");
-  int64_t gcd = llvm::greatestCommonDivisor(gcdRange(num), denom);
-  for (int64_t &coeff : num)
+  MPInt gcd = presburger::gcd(gcdRange(num), denom);
+  for (MPInt &coeff : num)
     coeff /= gcd;
   denom /= gcd;
 }
 
-SmallVector<int64_t, 8> presburger::getNegatedCoeffs(ArrayRef<int64_t> coeffs) {
-  SmallVector<int64_t, 8> negatedCoeffs;
+SmallVector<MPInt, 8> presburger::getNegatedCoeffs(ArrayRef<MPInt> coeffs) {
+  SmallVector<MPInt, 8> negatedCoeffs;
   negatedCoeffs.reserve(coeffs.size());
-  for (int64_t coeff : coeffs)
+  for (const MPInt &coeff : coeffs)
     negatedCoeffs.emplace_back(-coeff);
   return negatedCoeffs;
 }
 
-SmallVector<int64_t, 8> presburger::getComplementIneq(ArrayRef<int64_t> ineq) {
-  SmallVector<int64_t, 8> coeffs;
+SmallVector<MPInt, 8> presburger::getComplementIneq(ArrayRef<MPInt> ineq) {
+  SmallVector<MPInt, 8> coeffs;
   coeffs.reserve(ineq.size());
-  for (int64_t coeff : ineq)
+  for (const MPInt &coeff : ineq)
     coeffs.emplace_back(-coeff);
   --coeffs.back();
   return coeffs;
 }
 
 void DivisionRepr::removeDuplicateDivs(
     llvm::function_ref<bool(unsigned i, unsigned j)> merge) {
 

mlir/lib/Dialect/Affine/Analysis/AffineAnalysis.cpp

static void computeDirectionVector(
   // Eliminate all variables other than the direction variables just added.
   dependenceDomain->projectOut(numCommonLoops, numIdsToEliminate);
 
   // Scan each common loop variable column and set direction vectors based
   // on eliminated constraint system.
   dependenceComponents->resize(numCommonLoops);
   for (unsigned j = 0; j < numCommonLoops; ++j) {
     (*dependenceComponents)[j].op = commonLoops[j].getOperation();
-    auto lbConst = dependenceDomain->getConstantBound(IntegerPolyhedron::LB, j);
+    auto lbConst =
+        dependenceDomain->getConstantBound64(IntegerPolyhedron::LB, j);
     (*dependenceComponents)[j].lb =
         lbConst.value_or(std::numeric_limits<int64_t>::min());
-    auto ubConst = dependenceDomain->getConstantBound(IntegerPolyhedron::UB, j);
+    auto ubConst =
+        dependenceDomain->getConstantBound64(IntegerPolyhedron::UB, j);
     (*dependenceComponents)[j].ub =
         ubConst.value_or(std::numeric_limits<int64_t>::max());
   }
 }
 
 LogicalResult MemRefAccess::getAccessRelation(FlatAffineRelation &rel) const {
   // Create set corresponding to domain of access.
   FlatAffineValueConstraints domain;

mlir/lib/Dialect/Affine/Analysis/AffineStructures.cpp

static bool detectAsMod(const FlatAffineValueConstraints &cst, unsigned pos,
   // be determined.
   if (lbConst != 0 || ubConst < 1)
     return false;
   int64_t divisor = ubConst + 1;
 
   // Check for the aforementioned conditions in each equality.
   for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
        curEquality < numEqualities; curEquality++) {
-    int64_t coefficientAtPos = cst.atEq(curEquality, pos);
+    int64_t coefficientAtPos = cst.atEq64(curEquality, pos);
     // If current equality does not involve `var_r`, continue to the next
     // equality.
     if (coefficientAtPos == 0)
       continue;
 
     // Constant term should be 0 in this equality.
-    if (cst.atEq(curEquality, cst.getNumCols() - 1) != 0)
+    if (cst.atEq64(curEquality, cst.getNumCols() - 1) != 0)
       continue;
 
     // Traverse through the equality and construct the dividend expression
     // `dividendExpr`, to contain all the variables which are known and are
     // not divisible by `(coefficientAtPos * divisor)`. Hope here is that the
     // `dividendExpr` gets simplified into a single variable `var_n` discussed
     // above.
     auto dividendExpr = getAffineConstantExpr(0, context);
 
     // Track the terms that go into quotient expression, later used to detect
     // additional floordiv.
     unsigned quotientCount = 0;
     int quotientPosition = -1;
     int quotientSign = 1;
 
     // Consider each term in the current equality.
     unsigned curVar, e;
     for (curVar = 0, e = cst.getNumDimAndSymbolVars(); curVar < e; ++curVar) {
       // Ignore var_r.
       if (curVar == pos)
         continue;
-      int64_t coefficientOfCurVar = cst.atEq(curEquality, curVar);
+      int64_t coefficientOfCurVar = cst.atEq64(curEquality, curVar);
       // Ignore vars that do not contribute to the current equality.
       if (coefficientOfCurVar == 0)
         continue;
       // Check if the current var goes into the quotient expression.
       if (coefficientOfCurVar % (divisor * coefficientAtPos) == 0) {
         quotientCount++;
         quotientPosition = curVar;
         quotientSign = (coefficientOfCurVar * coefficientAtPos) > 0 ? 1 : -1;
for (unsigned curEquality = 0, numEqualities = cst.getNumEqualities();
     // TODO: Handle AffineSymbolExpr as well. There is no reason to restrict it
     // to dims themselves.
     auto dimExpr = dividendExpr.dyn_cast<AffineDimExpr>();
     if (!dimExpr)
       continue;
 
     // Express `var_r` as `var_n % divisor` and store the expression in `memo`.
     if (quotientCount >= 1) {
-      auto ub = cst.getConstantBound(FlatAffineValueConstraints::BoundType::UB,
-                                     dimExpr.getPosition());
+      auto ub = cst.getConstantBound64(
+          FlatAffineValueConstraints::BoundType::UB, dimExpr.getPosition());
       // If `var_n` has an upperbound that is less than the divisor, mod can be
       // eliminated altogether.
       if (ub && *ub < divisor)
         memo[pos] = dimExpr;
       else
         memo[pos] = dimExpr % divisor;
       // If a unique quotient `var_q` was seen, it can be expressed as
       // `var_n floordiv divisor`.
FlatAffineValueConstraints::getLowerAndUpperBound(
 
   SmallVector<int64_t, 8> lb, ub;
   SmallVector<AffineExpr, 4> lbExprs;
   unsigned dimCount = symStartPos - num;
   unsigned symCount = getNumDimAndSymbolVars() - symStartPos;
   lbExprs.reserve(lbIndices.size() + eqIndices.size());
   // Lower bound expressions.
   for (auto idx : lbIndices) {
-    auto ineq = getInequality(idx);
+    auto ineq = getInequality64(idx);
     // Extract the lower bound (in terms of other coeff's + const), i.e., if
     // i - j + 1 >= 0 is the constraint, 'pos' is for i the lower bound is j
     // - 1.
     addCoeffs(ineq, lb);
     std::transform(lb.begin(), lb.end(), lb.begin(), std::negate<int64_t>());
     auto expr =
         getAffineExprFromFlatForm(lb, dimCount, symCount, localExprs, context);
     // expr ceildiv divisor is (expr + divisor - 1) floordiv divisor
     int64_t divisor = std::abs(ineq[pos + offset]);
     expr = (expr + divisor - 1).floorDiv(divisor);
     lbExprs.push_back(expr);
   }
 
   SmallVector<AffineExpr, 4> ubExprs;
   ubExprs.reserve(ubIndices.size() + eqIndices.size());
   // Upper bound expressions.
   for (auto idx : ubIndices) {
-    auto ineq = getInequality(idx);
+    auto ineq = getInequality64(idx);
     // Extract the upper bound (in terms of other coeff's + const).
     addCoeffs(ineq, ub);
     auto expr =
         getAffineExprFromFlatForm(ub, dimCount, symCount, localExprs, context);
     expr = expr.floorDiv(std::abs(ineq[pos + offset]));
     // Upper bound is exclusive.
     ubExprs.push_back(expr + 1);
   }
 
   // Equalities. It's both a lower and a upper bound.
   SmallVector<int64_t, 4> b;
   for (auto idx : eqIndices) {
-    auto eq = getEquality(idx);
+    auto eq = getEquality64(idx);
     addCoeffs(eq, b);
     if (eq[pos + offset] > 0)
       std::transform(b.begin(), b.end(), b.begin(), std::negate<int64_t>());
 
     // Extract the upper bound (in terms of other coeff's + const).
     auto expr =
         getAffineExprFromFlatForm(b, dimCount, symCount, localExprs, context);
     expr = expr.floorDiv(std::abs(eq[pos + offset]));
void FlatAffineValueConstraints::getSliceBounds(
   do {
     changed = false;
     // Identify yet unknown variables as constants or mod's / floordiv's of
     // other variables if possible.
     for (unsigned pos = 0; pos < getNumVars(); pos++) {
       if (memo[pos])
         continue;
 
-      auto lbConst = getConstantBound(BoundType::LB, pos);
-      auto ubConst = getConstantBound(BoundType::UB, pos);
+      auto lbConst = getConstantBound64(BoundType::LB, pos);
+      auto ubConst = getConstantBound64(BoundType::UB, pos);
       if (lbConst.has_value() && ubConst.has_value()) {
         // Detect equality to a constant.
         if (lbConst.value() == ubConst.value()) {
           memo[pos] = getAffineConstantExpr(lbConst.value(), context);
           changed = true;
           continue;
         }
 
for (unsigned pos = 0; pos < getNumVars(); pos++) {
       }
 
       // Build AffineExpr solving for variable 'pos' in terms of all others.
       auto expr = getAffineConstantExpr(0, context);
       unsigned j, e;
       for (j = 0, e = getNumVars(); j < e; ++j) {
         if (j == pos)
           continue;
-        int64_t c = atEq(idx, j);
+        int64_t c = atEq64(idx, j);
         if (c == 0)
           continue;
         // If any of the involved IDs hasn't been found yet, we can't proceed.
         if (!memo[j])
           break;
         expr = expr + memo[j] * c;
       }
       if (j < e)
         // Can't construct expression as it depends on a yet uncomputed
         // variable.
         continue;
 
       // Add constant term to AffineExpr.
-      expr = expr + atEq(idx, getNumVars());
-      int64_t vPos = atEq(idx, pos);
+      expr = expr + atEq64(idx, getNumVars());
+      int64_t vPos = atEq64(idx, pos);
       assert(vPos != 0 && "expected non-zero here");
       if (vPos > 0)
         expr = (-expr).floorDiv(vPos);
       else
         // vPos < 0.
         expr = expr.floorDiv(-vPos);
       // Successfully constructed expression.
       memo[pos] = expr;
if (expr) {
       // If the above fails, we'll just use the constant lower bound and the
       // constant upper bound (if they exist) as the slice bounds.
       // TODO: being conservative for the moment in cases that
       // lead to multiple bounds - until getConstDifference in LoopFusion.cpp is
       // fixed (b/126426796).
       if (!lbMap || lbMap.getNumResults() > 1) {
         LLVM_DEBUG(llvm::dbgs()
                    << "WARNING: Potentially over-approximating slice lb\n");
-        auto lbConst = getConstantBound(BoundType::LB, pos + offset);
+        auto lbConst = getConstantBound64(BoundType::LB, pos + offset);
         if (lbConst.has_value()) {
-          lbMap =
-              AffineMap::get(numMapDims, numMapSymbols,
-                             getAffineConstantExpr(lbConst.value(), context));
+          lbMap = AffineMap::get(
+              numMapDims, numMapSymbols,
         }
       }
       if (!ubMap || ubMap.getNumResults() > 1) {
         LLVM_DEBUG(llvm::dbgs()
                    << "WARNING: Potentially over-approximating slice ub\n");
-        auto ubConst = getConstantBound(BoundType::UB, pos + offset);
+        auto ubConst = getConstantBound64(BoundType::UB, pos + offset);
         if (ubConst.has_value()) {
-          ubMap = AffineMap::get(
-              numMapDims, numMapSymbols,
-              getAffineConstantExpr(ubConst.value() + ubAdjustment, context));
+          ubMap =
+              AffineMap::get(numMapDims, numMapSymbols,
+                             getAffineConstantExpr(
+                                 ubConst.value() + ubAdjustment, context));
         }
       }
     }
     LLVM_DEBUG(llvm::dbgs()
                << "lb map for pos = " << Twine(pos + offset) << ", expr: ");
     LLVM_DEBUG(lbMap.dump(););
     LLVM_DEBUG(llvm::dbgs()
                << "ub map for pos = " << Twine(pos + offset) << ", expr: ");
void FlatAffineValueConstraints::getIneqAsAffineValueMap(
   // Get expressions for local vars.
   SmallVector<AffineExpr, 8> memo(getNumVars(), AffineExpr());
   if (failed(computeLocalVars(*this, memo, context)))
     assert(false &&
            "one or more local exprs do not have an explicit representation");
   auto localExprs = ArrayRef<AffineExpr>(memo).take_back(getNumLocalVars());
 
   // Compute the AffineExpr lower/upper bound for this inequality.
-  ArrayRef<int64_t> inequality = getInequality(ineqPos);
+  SmallVector<int64_t, 8> inequality = getInequality64(ineqPos);
   SmallVector<int64_t, 8> bound;
   bound.reserve(getNumCols() - 1);
   // Everything other than the coefficient at `pos`.
   bound.append(inequality.begin(), inequality.begin() + pos);
   bound.append(inequality.begin() + pos + 1, inequality.end());
 
   if (inequality[pos] > 0)
     // Lower bound.
FlatAffineValueConstraints::getAsIntegerSet(MLIRContext *context) const {
   SmallVector<bool, 16> eqFlags(getNumConstraints());
   std::fill(eqFlags.begin(), eqFlags.begin() + getNumEqualities(), true);
   std::fill(eqFlags.begin() + getNumEqualities(), eqFlags.end(), false);
 
   SmallVector<AffineExpr, 8> exprs;
   exprs.reserve(getNumConstraints());
 
   for (unsigned i = 0, e = getNumEqualities(); i < e; ++i)
-    exprs.push_back(getAffineExprFromFlatForm(getEquality(i), numDims, numSyms,
-                                              localExprs, context));
+    exprs.push_back(getAffineExprFromFlatForm(getEquality64(i), numDims,
+                                              numSyms, localExprs, context));
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i)
-    exprs.push_back(getAffineExprFromFlatForm(getInequality(i), numDims,
+    exprs.push_back(getAffineExprFromFlatForm(getInequality64(i), numDims,
                                               numSyms, localExprs, context));
   return IntegerSet::get(numDims, numSyms, exprs, eqFlags);
 }
 
 AffineMap mlir::alignAffineMapWithValues(AffineMap map, ValueRange operands,
                                          ValueRange dims, ValueRange syms,
                                          SmallVector<Value> *newSyms) {
   assert(operands.size() == map.getNumInputs() &&

mlir/lib/Dialect/Affine/Analysis/Utils.cpp

Optional<int64_t> MemRefRegion::getConstantBoundingSizeAndShape(
   // Find a constant upper bound on the extent of this memref region along each
   // dimension.
   int64_t numElements = 1;
   int64_t diffConstant;
   int64_t lbDivisor;
   for (unsigned d = 0; d < rank; d++) {
     SmallVector<int64_t, 4> lb;
     Optional<int64_t> diff =
-        cstWithShapeBounds.getConstantBoundOnDimSize(d, &lb, &lbDivisor);
+        cstWithShapeBounds.getConstantBoundOnDimSize64(d, &lb, &lbDivisor);
     if (diff.has_value()) {
       diffConstant = diff.value();
       assert(diffConstant >= 0 && "Dim size bound can't be negative");
       assert(lbDivisor > 0);
     } else {
       // If no constant bound is found, then it can always be bound by the
       // memref's dim size if the latter has a constant size along this dim.
       auto dimSize = memRefType.getDimSize(d);

mlir/lib/Dialect/Affine/Utils/Utils.cpp

MemRefType mlir::normalizeMemRefType(MemRefType memrefType, OpBuilder b,
   for (unsigned d = 0; d < newRank; ++d) {
     // Check if each dimension of normalized memrefType is dynamic.
     bool isDynDim = isNormalizedMemRefDynamicDim(
         d, layoutMap, memrefTypeDynDims, b.getContext());
     if (isDynDim) {
       newShape[d] = -1;
     } else {
       // The lower bound for the shape is always zero.
-      auto ubConst = fac.getConstantBound(IntegerPolyhedron::UB, d);
+      auto ubConst = fac.getConstantBound64(IntegerPolyhedron::UB, d);
       // For a static memref and an affine map with no symbols, this is
       // always bounded.
       assert(ubConst && "should always have an upper bound");
       if (ubConst.value() < 0)
         // This is due to an invalid map that maps to a negative space.
         return memrefType;
       // If dimension of new memrefType is dynamic, the value is -1.
       newShape[d] = ubConst.value() + 1;

mlir/lib/Dialect/Linalg/Utils/Utils.cpp

if (failed(constraints.addBound(IntegerPolyhedron::UB,
       return;
   }
 
   // Obtain an upper bound for the affine index computation by projecting out
   // all temporary results and expressing the upper bound for `value` in terms
   // of the terminals of the index computation.
   unsigned pos = getPosition(value);
   if (constantRequired) {
-    auto ubConst = constraints.getConstantBound(
+    auto ubConst = constraints.getConstantBound64(
         FlatAffineValueConstraints::BoundType::UB, pos);
     if (!ubConst)
       return;
 
     boundMap = AffineMap::getConstantMap(*ubConst, value.getContext());
     return;
   }
 

mlir/lib/Dialect/SCF/Utils/AffineCanonicalizationUtils.cpp

canonicalizeMinMaxOp(RewriterBase &rewriter, Operation *op, AffineMap map,
   SmallVector<Value> newOperands;
   unpackOptionalValues(constraints.getMaybeValues(), newOperands);
   // If dims/symbols have known constant values, use those in order to simplify
   // the affine map further.
   for (int64_t i = 0, e = constraints.getNumVars(); i < e; ++i) {
     // Skip unused operands and operands that are already constants.
     if (!newOperands[i] || getConstantIntValue(newOperands[i]))
       continue;
-    if (auto bound = constraints.getConstantBound(IntegerPolyhedron::EQ, i))
+    if (auto bound = constraints.getConstantBound64(IntegerPolyhedron::EQ, i))
       newOperands[i] =
           rewriter.create<arith::ConstantIndexOp>(op->getLoc(), *bound);
   }
   mlir::canonicalizeMapAndOperands(&newMap, &newOperands);
   rewriter.setInsertionPoint(op);
   rewriter.replaceOpWithNewOp<AffineApplyOp>(op, newMap, newOperands);
   return success();
 }

mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp

IntegerPolyhedron set(
       PresburgerSpace::getSetSpace(ids - syms, syms, /*numLocals=*/0));
   for (const auto &eq : eqs)
     set.addEquality(eq);
   for (const auto &ineq : ineqs)
     set.addInequality(ineq);
   return set;
 }
 
-static void dump(ArrayRef<int64_t> vec) {
-  for (int64_t x : vec)
+static void dump(ArrayRef<MPInt> vec) {
+  for (const MPInt &x : vec)
     llvm::errs() << x << ' ';
   llvm::errs() << '\n';
 }
 
 /// If fn is TestFunction::Sample (default):
 ///
 ///   If hasSample is true, check that findIntegerSample returns a valid sample
 ///   for the IntegerPolyhedron poly. Also check that getIntegerLexmin finds a
 ///   non-empty lexmin.
 ///
 ///   If hasSample is false, check that findIntegerSample returns None and
 ///   findIntegerLexMin returns Empty.
 ///
 /// If fn is TestFunction::Empty, check that isIntegerEmpty returns the
 /// opposite of hasSample.
 static void checkSample(bool hasSample, const IntegerPolyhedron &poly,
                         TestFunction fn = TestFunction::Sample) {
-  Optional<SmallVector<int64_t, 8>> maybeSample;
-  MaybeOptimum<SmallVector<int64_t, 8>> maybeLexMin;
+  Optional<SmallVector<MPInt, 8>> maybeSample;
+  MaybeOptimum<SmallVector<MPInt, 8>> maybeLexMin;
   switch (fn) {
   case TestFunction::Sample:
     maybeSample = poly.findIntegerSample();
     maybeLexMin = poly.findIntegerLexMin();
 
     if (!hasSample) {
       EXPECT_FALSE(maybeSample.has_value());
       if (maybeSample.has_value()) {
TEST(IntegerPolyhedronTest, removeRedundantConstraintsTest) {
   IntegerPolyhedron poly5 = parsePoly(
       "(x,y) : (128 * x + 127 >= 0, -x + 7 >= 0, -128 * x + y >= 0, y >= 0)");
   // 128x + 127 >= 0  implies that 128x >= 0, since x has to be an integer.
   // (This should be caught by GCDTightenInqualities().)
   // So -128x + y >= 0 and 128x + 127 >= 0 imply y >= 0 since we have
   // y >= 128x >= 0.
   poly5.removeRedundantConstraints();
   EXPECT_EQ(poly5.getNumInequalities(), 3u);
-  SmallVector<int64_t, 8> redundantConstraint = {0, 1, 0};
+  SmallVector<MPInt, 8> redundantConstraint = getMPIntVec({0, 1, 0});
   for (unsigned i = 0; i < 3; ++i) {
     // Ensure that the removed constraint was the redundant constraint [3].
-    EXPECT_NE(poly5.getInequality(i), ArrayRef<int64_t>(redundantConstraint));
+    EXPECT_NE(poly5.getInequality(i), ArrayRef<MPInt>(redundantConstraint));
   }
 }
 
 TEST(IntegerPolyhedronTest, addConstantUpperBound) {
   IntegerPolyhedron poly(PresburgerSpace::getSetSpace(2));
   poly.addBound(IntegerPolyhedron::UB, 0, 1);
   EXPECT_EQ(poly.atIneq(0, 0), -1);
   EXPECT_EQ(poly.atIneq(0, 1), 0);

 /// computed representation. The expected division representation is given as
 /// a vector of expressions set in `expectedDividends` and the corressponding
 /// denominator in `expectedDenominators`. The `denominators` and `dividends`
 /// obtained through `getLocalRepr` function is verified against the
 /// `expectedDenominators` and `expectedDividends` respectively.
 static void checkDivisionRepresentation(
     IntegerPolyhedron &poly,
     const std::vector<SmallVector<int64_t, 8>> &expectedDividends,
-    ArrayRef<unsigned> expectedDenominators) {
+    ArrayRef<int64_t> expectedDenominators) {
   DivisionRepr divs = poly.getLocalReprs();
 
   // Check that the `denominators` and `expectedDenominators` match.
-  EXPECT_TRUE(expectedDenominators == divs.getDenoms());
+  EXPECT_EQ(ArrayRef<MPInt>(getMPIntVec(expectedDenominators)),
+            divs.getDenoms());
 
   // Check that the `dividends` and `expectedDividends` match. If the
   // denominator for a division is zero, we ignore its dividend.
   EXPECT_TRUE(divs.getNumDivs() == expectedDividends.size());
   for (unsigned i = 0, e = divs.getNumDivs(); i < e; ++i)
     if (divs.hasRepr(i))
       for (unsigned j = 0, f = divs.getNumVars() + 1; j < f; ++j)
         EXPECT_TRUE(expectedDividends[i][j] == divs.getDividend(i)[j]);
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprSimple) {
   IntegerPolyhedron poly(PresburgerSpace::getSetSpace(1));
 
   poly.addLocalFloorDiv({1, 4}, 10);
   poly.addLocalFloorDiv({1, 0, 100}, 10);
 
   std::vector<SmallVector<int64_t, 8>> divisions = {{1, 0, 0, 4},
                                                     {1, 0, 0, 100}};
-  SmallVector<unsigned, 8> denoms = {10, 10};
+  SmallVector<int64_t, 8> denoms = {10, 10};
 
   // Check if floordivs can be computed when no other inequalities exist
   // and floor divs do not depend on each other.
   checkDivisionRepresentation(poly, divisions, denoms);
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprConstantFloorDiv) {
   IntegerPolyhedron poly(PresburgerSpace::getSetSpace(4));
 
   poly.addInequality({1, 0, 3, 1, 2});
   poly.addInequality({1, 2, -8, 1, 10});
   poly.addEquality({1, 2, -4, 1, 10});
 
   poly.addLocalFloorDiv({0, 0, 0, 0, 100}, 30);
   poly.addLocalFloorDiv({0, 0, 0, 0, 0, 206}, 101);
 
   std::vector<SmallVector<int64_t, 8>> divisions = {{0, 0, 0, 0, 0, 0, 3},
                                                     {0, 0, 0, 0, 0, 0, 2}};
-  SmallVector<unsigned, 8> denoms = {1, 1};
+  SmallVector<int64_t, 8> denoms = {1, 1};
 
   // Check if floordivs with constant numerator can be computed.
   checkDivisionRepresentation(poly, divisions, denoms);
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprRecursive) {
   IntegerPolyhedron poly(PresburgerSpace::getSetSpace(4));
   poly.addInequality({1, 0, 3, 1, 2});
   poly.addInequality({1, 2, -8, 1, 10});
   poly.addEquality({1, 2, -4, 1, 10});
 
   poly.addLocalFloorDiv({0, -2, 7, 2, 10}, 3);
   poly.addLocalFloorDiv({3, 0, 9, 2, 2, 10}, 5);
   poly.addLocalFloorDiv({0, 1, -123, 2, 0, -4, 10}, 3);
 
   poly.addInequality({1, 2, -2, 1, -5, 0, 6, 100});
   poly.addInequality({1, 2, -8, 1, 3, 7, 0, -9});
 
   std::vector<SmallVector<int64_t, 8>> divisions = {
       {0, -2, 7, 2, 0, 0, 0, 10},
       {3, 0, 9, 2, 2, 0, 0, 10},
       {0, 1, -123, 2, 0, -4, 0, 10}};
 
-  SmallVector<unsigned, 8> denoms = {3, 5, 3};
+  SmallVector<int64_t, 8> denoms = {3, 5, 3};
 
   // Check if floordivs which may depend on other floordivs can be computed.
   checkDivisionRepresentation(poly, divisions, denoms);
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprTightUpperBound) {
   {
     IntegerPolyhedron poly = parsePoly("(i) : (i mod 3 - 1 >= 0)");
 
     // The set formed by the poly is:
     //        3q - i + 2 >= 0             <-- Division lower bound
     //       -3q + i - 1 >= 0
     //       -3q + i     >= 0             <-- Division upper bound
     // We remove redundant constraints to get the set:
     //        3q - i + 2 >= 0             <-- Division lower bound
     //       -3q + i - 1 >= 0             <-- Tighter division upper bound
     // thus, making the upper bound tighter.
     poly.removeRedundantConstraints();
 
     std::vector<SmallVector<int64_t, 8>> divisions = {{1, 0, 0}};
-    SmallVector<unsigned, 8> denoms = {3};
+    SmallVector<int64_t, 8> denoms = {3};
 
     // Check if the divisions can be computed even with a tighter upper bound.
     checkDivisionRepresentation(poly, divisions, denoms);
   }
 
   {
     IntegerPolyhedron poly =
         parsePoly("(i, j, q) : (4*q - i - j + 2 >= 0, -4*q + i + j >= 0)");
     // Convert `q` to a local variable.
     poly.convertToLocal(VarKind::SetDim, 2, 3);
 
     std::vector<SmallVector<int64_t, 8>> divisions = {{1, 1, 0, 1}};
-    SmallVector<unsigned, 8> denoms = {4};
+    SmallVector<int64_t, 8> denoms = {4};
 
     // Check if the divisions can be computed even with a tighter upper bound.
     checkDivisionRepresentation(poly, divisions, denoms);
   }
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprFromEquality) {
   {
     IntegerPolyhedron poly = parsePoly("(i, j, q) : (-4*q + i + j == 0)");
     // Convert `q` to a local variable.
     poly.convertToLocal(VarKind::SetDim, 2, 3);
 
     std::vector<SmallVector<int64_t, 8>> divisions = {{1, 1, 0, 0}};
-    SmallVector<unsigned, 8> denoms = {4};
+    SmallVector<int64_t, 8> denoms = {4};
 
     checkDivisionRepresentation(poly, divisions, denoms);
   }
   {
     IntegerPolyhedron poly = parsePoly("(i, j, q) : (4*q - i - j == 0)");
     // Convert `q` to a local variable.
     poly.convertToLocal(VarKind::SetDim, 2, 3);
 
     std::vector<SmallVector<int64_t, 8>> divisions = {{1, 1, 0, 0}};
-    SmallVector<unsigned, 8> denoms = {4};
+    SmallVector<int64_t, 8> denoms = {4};
 
     checkDivisionRepresentation(poly, divisions, denoms);
   }
   {
     IntegerPolyhedron poly = parsePoly("(i, j, q) : (3*q + i + j - 2 == 0)");
     // Convert `q` to a local variable.
     poly.convertToLocal(VarKind::SetDim, 2, 3);
 
     std::vector<SmallVector<int64_t, 8>> divisions = {{-1, -1, 0, 2}};
-    SmallVector<unsigned, 8> denoms = {3};
+    SmallVector<int64_t, 8> denoms = {3};
 
     checkDivisionRepresentation(poly, divisions, denoms);
   }
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprFromEqualityAndInequality) {
   {
     IntegerPolyhedron poly =
         parsePoly("(i, j, q, k) : (-3*k + i + j == 0, 4*q - "
                   "i - j + 2 >= 0, -4*q + i + j >= 0)");
     // Convert `q` and `k` to local variables.
     poly.convertToLocal(VarKind::SetDim, 2, 4);
 
     std::vector<SmallVector<int64_t, 8>> divisions = {{1, 1, 0, 0, 1},
                                                       {1, 1, 0, 0, 0}};
-    SmallVector<unsigned, 8> denoms = {4, 3};
+    SmallVector<int64_t, 8> denoms = {4, 3};
 
     checkDivisionRepresentation(poly, divisions, denoms);
   }
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprNoRepr) {
   IntegerPolyhedron poly =
       parsePoly("(x, q) : (x - 3 * q >= 0, -x + 3 * q + 3 >= 0)");
   // Convert q to a local variable.
   poly.convertToLocal(VarKind::SetDim, 1, 2);
 
   std::vector<SmallVector<int64_t, 8>> divisions = {{0, 0, 0}};
-  SmallVector<unsigned, 8> denoms = {0};
+  SmallVector<int64_t, 8> denoms = {0};
 
   // Check that no division is computed.
   checkDivisionRepresentation(poly, divisions, denoms);
 }
 
 TEST(IntegerPolyhedronTest, computeLocalReprNegConstNormalize) {
   IntegerPolyhedron poly =
       parsePoly("(x, q) : (-1 - 3*x - 6 * q >= 0, 6 + 3*x + 6*q >= 0)");
   // Convert q to a local variable.
   poly.convertToLocal(VarKind::SetDim, 1, 2);
 
   // q = floor((-1/3 - x)/2)
   //   = floor((1/3) + (-1 - x)/2)
   //   = floor((-1 - x)/2).
   std::vector<SmallVector<int64_t, 8>> divisions = {{-1, 0, -1}};
-  SmallVector<unsigned, 8> denoms = {2};
+  SmallVector<int64_t, 8> denoms = {2};
   checkDivisionRepresentation(poly, divisions, denoms);
 }
 
 TEST(IntegerPolyhedronTest, simplifyLocalsTest) {
   // (x) : (exists y: 2x + y = 1 and y = 2).
   IntegerPolyhedron poly(PresburgerSpace::getSetSpace(1, 0, 1));
   poly.addEquality({2, 1, -1});
   poly.addEquality({0, 1, -2});
TEST(IntegerPolyhedronTest, negativeDividends) {
   poly2.addLocalFloorDiv({-1, 0, -2}, 3); // z = [-x - 2 / 3].
   poly2.addInequality({1, -1, -1, 0});    // y + z <= x.
 
   poly1.mergeLocalVars(poly2);
 
   // Merging triggers normalization.
   std::vector<SmallVector<int64_t, 8>> divisions = {{-1, 0, 0, 1},
                                                     {-1, 0, 0, -2}};
-  SmallVector<unsigned, 8> denoms = {2, 3};
+  SmallVector<int64_t, 8> denoms = {2, 3};
   checkDivisionRepresentation(poly1, divisions, denoms);
 }
 
 void expectRationalLexMin(const IntegerPolyhedron &poly,
                           ArrayRef<Fraction> min) {
   auto lexMin = poly.findRationalLexMin();
   ASSERT_TRUE(lexMin.isBounded());
   EXPECT_EQ(ArrayRef<Fraction>(*lexMin), min);
expectNoRationalLexMin(
                 "2*x + 10*y + 8*z - 10 >= 0, 2*x + 5*y + 10*z - 10 >= 0)"));
 
   // The set is empty.
   expectNoRationalLexMin(OptimumKind::Empty,
                          parsePoly("(x) : (2*x >= 0, -x - 1 >= 0)"));
 }
 
 void expectIntegerLexMin(const IntegerPolyhedron &poly, ArrayRef<int64_t> min) {
-  auto lexMin = poly.findIntegerLexMin();
+  MaybeOptimum<SmallVector<MPInt, 8>> lexMin = poly.findIntegerLexMin();
   ASSERT_TRUE(lexMin.isBounded());
-  EXPECT_EQ(ArrayRef<int64_t>(*lexMin), min);
+  EXPECT_EQ(*lexMin, getMPIntVec(min));
 }
 
 void expectNoIntegerLexMin(OptimumKind kind, const IntegerPolyhedron &poly) {
   ASSERT_NE(kind, OptimumKind::Bounded)
       << "Use expectRationalLexMin for bounded min";
   EXPECT_EQ(poly.findRationalLexMin().getKind(), kind);
 }
 
expectSymbolicIntegerLexMin(
           "N "
           ">= 0, N + K - 2 - x >= 0, x - 4 >= 0)",
           {{0, 0, 1, 0, 1}, {0, 1, 0, 0, 0}} // (1 + x, N)
       }});
 }
 
 static void
 expectComputedVolumeIsValidOverapprox(const IntegerPolyhedron &poly,
-                                      Optional<uint64_t> trueVolume,
-                                      Optional<uint64_t> resultBound) {
+                                      Optional<int64_t> trueVolume,
+                                      Optional<int64_t> resultBound) {
   expectComputedVolumeIsValidOverapprox(poly.computeVolume(), trueVolume,
                                         resultBound);
 }
 
 TEST(IntegerPolyhedronTest, computeVolume) {
   // 0 <= x <= 3 + 1/3, -5.5 <= y <= 2 + 3/5, 3 <= z <= 1.75.
   // i.e. 0 <= x <= 3, -5 <= y <= 2, 3 <= z <= 3 + 1/4.
   // So volume is 4 * 8 * 1 = 32.
expectComputedVolumeIsValidOverapprox(
       /*trueVolume=*/61ull, /*resultBound=*/441ull);
 
   // Unbounded polytope.
   expectComputedVolumeIsValidOverapprox(
       parsePoly("(x, y) : (2*x - y >= 0, y - 3*x >= 0)"),
       /*trueVolume=*/{}, /*resultBound=*/{});
 }
 
+bool containsPointNoLocal(const IntegerPolyhedron &poly,
+                          ArrayRef<int64_t> point) {
+  return poly.containsPointNoLocal(getMPIntVec(point)).hasValue();
+}
+
 TEST(IntegerPolyhedronTest, containsPointNoLocal) {
   IntegerPolyhedron poly1 = parsePoly("(x) : ((x floordiv 2) - x == 0)");
-  EXPECT_TRUE(poly1.containsPointNoLocal({0}));
-  EXPECT_FALSE(poly1.containsPointNoLocal({1}));
+  EXPECT_TRUE(containsPointNoLocal(poly1, {0}));
+  EXPECT_FALSE(containsPointNoLocal(poly1, {1}));
 
   IntegerPolyhedron poly2 = parsePoly(
       "(x) : (x - 2*(x floordiv 2) == 0, x - 4*(x floordiv 4) - 2 == 0)");
-  EXPECT_TRUE(poly2.containsPointNoLocal({6}));
-  EXPECT_FALSE(poly2.containsPointNoLocal({4}));
+  EXPECT_TRUE(containsPointNoLocal(poly2, {6}));
+  EXPECT_FALSE(containsPointNoLocal(poly2, {4}));
 
   IntegerPolyhedron poly3 = parsePoly("(x, y) : (2*x - y >= 0, y - 3*x >= 0)");
-  EXPECT_TRUE(poly3.containsPointNoLocal({0, 0}));
-  EXPECT_FALSE(poly3.containsPointNoLocal({1, 0}));
+  EXPECT_TRUE(containsPointNoLocal(poly3, {0, 0}));
+  EXPECT_FALSE(containsPointNoLocal(poly3, {1, 0}));
 }
 
 TEST(IntegerPolyhedronTest, truncateEqualityRegressionTest) {
   // IntegerRelation::truncate was truncating inequalities to the number of
   // equalities.
   IntegerRelation set(PresburgerSpace::getSetSpace(1));
   IntegerRelation::CountsSnapshot snapshot = set.getCounts();
   set.addEquality({1, 0});
   set.truncate(snapshot);
   EXPECT_EQ(set.getNumEqualities(), 0u);
 }

mlir/unittests/Analysis/Presburger/LinearTransformTest.cpp

void testColumnEchelonForm(const Matrix &m, unsigned expectedRank) {
   std::pair<unsigned, LinearTransform> result =
       LinearTransform::makeTransformToColumnEchelon(m);
   unsigned rank = result.first;
   EXPECT_EQ(rank, expectedRank);
   LinearTransform transform = result.second;
   // In column echelon form, each row's last non-zero value can be at most one
   // column to the right of the last non-zero column among the previous rows.
   for (unsigned row = 0, nRows = m.getNumRows(); row < nRows; ++row) {
-    SmallVector<int64_t, 8> rowVec =
-        transform.preMultiplyWithRow(m.getRow(row));
+    SmallVector<MPInt, 8> rowVec = transform.preMultiplyWithRow(m.getRow(row));
     for (unsigned col = lastAllowedNonZeroCol + 1, nCols = m.getNumColumns();
          col < nCols; ++col) {
       EXPECT_EQ(rowVec[col], 0);
       if (rowVec[col] != 0) {
         llvm::errs() << "Failed at input matrix:\n";
         m.dump();
       }
     }

mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp

PresburgerSet set =
                                                "(x) : (x == 0)",
                                                "(x) : (x >= 0, -x + 1 >= 0)",
                                            });
   expectCoalesce(2, set);
 }
 
 static void
 expectComputedVolumeIsValidOverapprox(const PresburgerSet &set,
-                                      Optional<uint64_t> trueVolume,
-                                      Optional<uint64_t> resultBound) {
+                                      Optional<int64_t> trueVolume,
+                                      Optional<int64_t> resultBound) {
   expectComputedVolumeIsValidOverapprox(set.computeVolume(), trueVolume,
                                         resultBound);
 }
 
 TEST(SetTest, computeVolume) {
   // Diamond with vertices at (0, 0), (5, 5), (5, 5), (10, 0).
   PresburgerSet diamond(
       parsePoly("(x, y) : (x + y >= 0, -x - y + 10 >= 0, x - y >= 0, -x + y + "

mlir/unittests/Analysis/Presburger/SimplexTest.cpp

 #include "mlir/IR/MLIRContext.h"
 
 #include <gmock/gmock.h>
 #include <gtest/gtest.h>
 
 using namespace mlir;
 using namespace presburger;
 
+/// Convenience functions to pass literals to Simplex.
+void addInequality(SimplexBase &simplex, ArrayRef<int64_t> coeffs) {
+  simplex.addInequality(getMPIntVec(coeffs));
+}
+void addEquality(SimplexBase &simplex, ArrayRef<int64_t> coeffs) {
+  simplex.addEquality(getMPIntVec(coeffs));
+}
+bool isRedundantInequality(Simplex &simplex, ArrayRef<int64_t> coeffs) {
+  return simplex.isRedundantInequality(getMPIntVec(coeffs));
+}
+bool isRedundantInequality(LexSimplex &simplex, ArrayRef<int64_t> coeffs) {
+  return simplex.isRedundantInequality(getMPIntVec(coeffs));
+}
+bool isRedundantEquality(Simplex &simplex, ArrayRef<int64_t> coeffs) {
+  return simplex.isRedundantEquality(getMPIntVec(coeffs));
+}
+bool isSeparateInequality(LexSimplex &simplex, ArrayRef<int64_t> coeffs) {
+  return simplex.isSeparateInequality(getMPIntVec(coeffs));
+}
+
+Simplex::IneqType findIneqType(Simplex &simplex, ArrayRef<int64_t> coeffs) {
+  return simplex.findIneqType(getMPIntVec(coeffs));
+}
+ 
 /// Take a snapshot, add constraints making the set empty, and rollback.
 /// The set should not be empty after rolling back. We add additional
 /// constraints after the set is already empty and roll back the addition
 /// of these. The set should be marked non-empty only once we rollback
 /// past the addition of the first constraint that made it empty.
 TEST(SimplexTest, emptyRollback) {
   Simplex simplex(2);
   // (u - v) >= 0
-  simplex.addInequality({1, -1, 0});
+  addInequality(simplex, {1, -1, 0});
   ASSERT_FALSE(simplex.isEmpty());
 
   unsigned snapshot = simplex.getSnapshot();
   // (u - v) <= -1
-  simplex.addInequality({-1, 1, -1});
+  addInequality(simplex, {-1, 1, -1});
   ASSERT_TRUE(simplex.isEmpty());
 
   unsigned snapshot2 = simplex.getSnapshot();
   // (u - v) <= -3
-  simplex.addInequality({-1, 1, -3});
+  addInequality(simplex, {-1, 1, -3});
   ASSERT_TRUE(simplex.isEmpty());
 
   simplex.rollback(snapshot2);
   ASSERT_TRUE(simplex.isEmpty());
 
   simplex.rollback(snapshot);
   ASSERT_FALSE(simplex.isEmpty());
 }
 
 /// Check that the set gets marked as empty when we add contradictory
 /// constraints.
 TEST(SimplexTest, addEquality_separate) {
   Simplex simplex(1);
-  simplex.addInequality({1, -1}); // x >= 1.
+  addInequality(simplex, {1, -1}); // x >= 1.
   ASSERT_FALSE(simplex.isEmpty());
-  simplex.addEquality({1, 0}); // x == 0.
+  addEquality(simplex, {1, 0}); // x == 0.
   EXPECT_TRUE(simplex.isEmpty());
 }
 
 void expectInequalityMakesSetEmpty(Simplex &simplex, ArrayRef<int64_t> coeffs,
                                    bool expect) {
   ASSERT_FALSE(simplex.isEmpty());
   unsigned snapshot = simplex.getSnapshot();
-  simplex.addInequality(coeffs);
+  addInequality(simplex, coeffs);
   EXPECT_EQ(simplex.isEmpty(), expect);
   simplex.rollback(snapshot);
 }
 
 TEST(SimplexTest, addInequality_rollback) {
   Simplex simplex(3);
   SmallVector<int64_t, 4> coeffs[]{{1, 0, 0, 0},   // u >= 0.
                                    {-1, 0, 0, 0},  // u <= 0.
                                    {1, -1, 1, 0},  // u - v + w >= 0.
                                    {1, 1, -1, 0}}; // u + v - w >= 0.
   // The above constraints force u = 0 and v = w.
   // The constraints below violate v = w.
   SmallVector<int64_t, 4> checkCoeffs[]{{0, 1, -1, -1},  // v - w >= 1.
                                         {0, -1, 1, -1}}; // v - w <= -1.
 
   for (int run = 0; run < 4; run++) {
     unsigned snapshot = simplex.getSnapshot();
 
     expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false);
     expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false);
 
     for (int i = 0; i < 4; i++)
-      simplex.addInequality(coeffs[(run + i) % 4]);
+      addInequality(simplex, coeffs[(run + i) % 4]);
 
     expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], true);
     expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], true);
 
     simplex.rollback(snapshot);
     EXPECT_EQ(simplex.getNumConstraints(), 0u);
 
     expectInequalityMakesSetEmpty(simplex, checkCoeffs[0], false);
     expectInequalityMakesSetEmpty(simplex, checkCoeffs[1], false);
   }
 }
 
 Simplex simplexFromConstraints(unsigned nDim,
                                ArrayRef<SmallVector<int64_t, 8>> ineqs,
                                ArrayRef<SmallVector<int64_t, 8>> eqs) {
   Simplex simplex(nDim);
   for (const auto &ineq : ineqs)
-    simplex.addInequality(ineq);
+    addInequality(simplex, ineq);
   for (const auto &eq : eqs)
-    simplex.addEquality(eq);
+    addEquality(simplex, eq);
   return simplex;
 }
 
 TEST(SimplexTest, isUnbounded) {
   EXPECT_FALSE(simplexFromConstraints(
                    2, {{1, 1, 0}, {-1, -1, 0}, {1, -1, 5}, {-1, 1, -5}}, {})
                    .isUnbounded());
 
EXPECT_FALSE(simplexFromConstraints(1,
                                       {})
                    .getSamplePointIfIntegral()
                    .has_value());
 }
 
 /// Some basic sanity checks involving zero or one variables.
 TEST(SimplexTest, isMarkedRedundant_no_var_ge_zero) {
   Simplex simplex(0);
-  simplex.addInequality({0}); // 0 >= 0.
+  addInequality(simplex, {0}); // 0 >= 0.
 
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_TRUE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_no_var_eq) {
   Simplex simplex(0);
-  simplex.addEquality({0}); // 0 == 0.
+  addEquality(simplex, {0}); // 0 == 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_TRUE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_pos_var_eq) {
   Simplex simplex(1);
-  simplex.addEquality({1, 0}); // x == 0.
+  addEquality(simplex, {1, 0}); // x == 0.
 
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_zero_var_eq) {
   Simplex simplex(1);
-  simplex.addEquality({0, 0}); // 0x == 0.
+  addEquality(simplex, {0, 0}); // 0x == 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_TRUE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_neg_var_eq) {
   Simplex simplex(1);
-  simplex.addEquality({-1, 0}); // -x == 0.
+  addEquality(simplex, {-1, 0}); // -x == 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_pos_var_ge) {
   Simplex simplex(1);
-  simplex.addInequality({1, 0}); // x >= 0.
+  addInequality(simplex, {1, 0}); // x >= 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_zero_var_ge) {
   Simplex simplex(1);
-  simplex.addInequality({0, 0}); // 0x >= 0.
+  addInequality(simplex, {0, 0}); // 0x >= 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_TRUE(simplex.isMarkedRedundant(0));
 }
 
 TEST(SimplexTest, isMarkedRedundant_neg_var_ge) {
   Simplex simplex(1);
-  simplex.addInequality({-1, 0}); // x <= 0.
+  addInequality(simplex, {-1, 0}); // x <= 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
 }
 
 /// None of the constraints are redundant. Slightly more complicated test
 /// involving an equality.
 TEST(SimplexTest, isMarkedRedundant_no_redundant) {
   Simplex simplex(3);
 
-  simplex.addEquality({-1, 0, 1, 0});     // u = w.
-  simplex.addInequality({-1, 16, 0, 15}); // 15 - (u - 16v) >= 0.
-  simplex.addInequality({1, -16, 0, 0});  //      (u - 16v) >= 0.
+  addEquality(simplex, {-1, 0, 1, 0});     // u = w.
+  addInequality(simplex, {-1, 16, 0, 15}); // 15 - (u - 16v) >= 0.
+  addInequality(simplex, {1, -16, 0, 0});  //      (u - 16v) >= 0.
 
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
 
   for (unsigned i = 0; i < simplex.getNumConstraints(); ++i)
     EXPECT_FALSE(simplex.isMarkedRedundant(i)) << "i = " << i << "\n";
 }
 
 TEST(SimplexTest, isMarkedRedundant_repeated_constraints) {
   Simplex simplex(3);
 
   // [4] to [7] are repeats of [0] to [3].
-  simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1.
-  simplex.addInequality({-1, 0, 8, 7}); // [1]: 8z >= x - 7.
-  simplex.addInequality({1, 0, -8, 0}); // [2]: 8z <= x.
-  simplex.addInequality({0, 1, 0, 0});  // [3]: y >= 0.
-  simplex.addInequality({-1, 0, 8, 7}); // [4]: 8z >= 7 - x.
-  simplex.addInequality({1, 0, -8, 0}); // [5]: 8z <= x.
-  simplex.addInequality({0, 1, 0, 0});  // [6]: y >= 0.
-  simplex.addInequality({0, -1, 0, 1}); // [7]: y <= 1.
+  addInequality(simplex, {0, -1, 0, 1}); // [0]: y <= 1.
+  addInequality(simplex, {-1, 0, 8, 7}); // [1]: 8z >= x - 7.
+  addInequality(simplex, {1, 0, -8, 0}); // [2]: 8z <= x.
+  addInequality(simplex, {0, 1, 0, 0});  // [3]: y >= 0.
+  addInequality(simplex, {-1, 0, 8, 7}); // [4]: 8z >= 7 - x.
+  addInequality(simplex, {1, 0, -8, 0}); // [5]: 8z <= x.
+  addInequality(simplex, {0, 1, 0, 0});  // [6]: y >= 0.
+  addInequality(simplex, {0, -1, 0, 1}); // [7]: y <= 1.
 
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
 
   EXPECT_EQ(simplex.isMarkedRedundant(0), true);
   EXPECT_EQ(simplex.isMarkedRedundant(1), true);
   EXPECT_EQ(simplex.isMarkedRedundant(2), true);
   EXPECT_EQ(simplex.isMarkedRedundant(3), true);
   EXPECT_EQ(simplex.isMarkedRedundant(4), false);
   EXPECT_EQ(simplex.isMarkedRedundant(5), false);
   EXPECT_EQ(simplex.isMarkedRedundant(6), false);
   EXPECT_EQ(simplex.isMarkedRedundant(7), false);
 }
 
 TEST(SimplexTest, isMarkedRedundant) {
   Simplex simplex(3);
-  simplex.addInequality({0, -1, 0, 1}); // [0]: y <= 1.
-  simplex.addInequality({1, 0, 0, -1}); // [1]: x >= 1.
-  simplex.addInequality({-1, 0, 0, 2}); // [2]: x <= 2.
-  simplex.addInequality({-1, 0, 2, 7}); // [3]: 2z >= x - 7.
-  simplex.addInequality({1, 0, -2, 0}); // [4]: 2z <= x.
-  simplex.addInequality({0, 1, 0, 0});  // [5]: y >= 0.
-  simplex.addInequality({0, 1, -2, 1}); // [6]: y >= 2z - 1.
-  simplex.addInequality({-1, 1, 0, 1}); // [7]: y >= x - 1.
+  addInequality(simplex, {0, -1, 0, 1}); // [0]: y <= 1.
+  addInequality(simplex, {1, 0, 0, -1}); // [1]: x >= 1.
+  addInequality(simplex, {-1, 0, 0, 2}); // [2]: x <= 2.
+  addInequality(simplex, {-1, 0, 2, 7}); // [3]: 2z >= x - 7.
+  addInequality(simplex, {1, 0, -2, 0}); // [4]: 2z <= x.
+  addInequality(simplex, {0, 1, 0, 0});  // [5]: y >= 0.
+  addInequality(simplex, {0, 1, -2, 1}); // [6]: y >= 2z - 1.
+  addInequality(simplex, {-1, 1, 0, 1}); // [7]: y >= x - 1.
 
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
 
   // [0], [1], [3], [4], [7] together imply [2], [5], [6] must hold.
   //
   // From [7], [0]: x <= y + 1 <= 2, so we have [2].
   // From [7], [1]: y >= x - 1 >= 0, so we have [5].
   // From [4], [7]: 2z - 1 <= x - 1 <= y, so we have [6].
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
   EXPECT_FALSE(simplex.isMarkedRedundant(1));
   EXPECT_TRUE(simplex.isMarkedRedundant(2));
   EXPECT_FALSE(simplex.isMarkedRedundant(3));
   EXPECT_FALSE(simplex.isMarkedRedundant(4));
   EXPECT_TRUE(simplex.isMarkedRedundant(5));
   EXPECT_TRUE(simplex.isMarkedRedundant(6));
   EXPECT_FALSE(simplex.isMarkedRedundant(7));
 }
 
 TEST(SimplexTest, isMarkedRedundantTiledLoopNestConstraints) {
   Simplex simplex(3);                     // Variables are x, y, N.
-  simplex.addInequality({1, 0, 0, 0});    // [0]: x >= 0.
-  simplex.addInequality({-32, 0, 1, -1}); // [1]: 32x <= N - 1.
-  simplex.addInequality({0, 1, 0, 0});    // [2]: y >= 0.
-  simplex.addInequality({-32, 1, 0, 0});  // [3]: y >= 32x.
-  simplex.addInequality({32, -1, 0, 31}); // [4]: y <= 32x + 31.
-  simplex.addInequality({0, -1, 1, -1});  // [5]: y <= N - 1.
+  addInequality(simplex, {1, 0, 0, 0});   // [0]: x >= 0.
+  addInequality(simplex, {-32, 0, 1, -1}); // [1]: 32x <= N - 1.
+  addInequality(simplex, {0, 1, 0, 0});    // [2]: y >= 0.
+  addInequality(simplex, {-32, 1, 0, 0});  // [3]: y >= 32x.
+  addInequality(simplex, {32, -1, 0, 31}); // [4]: y <= 32x + 31.
+  addInequality(simplex, {0, -1, 1, -1});  // [5]: y <= N - 1.
   // [3] and [0] imply [2], as we have y >= 32x >= 0.
   // [3] and [5] imply [1], as we have 32x <= y <= N - 1.
   simplex.detectRedundant();
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
   EXPECT_TRUE(simplex.isMarkedRedundant(1));
   EXPECT_TRUE(simplex.isMarkedRedundant(2));
   EXPECT_FALSE(simplex.isMarkedRedundant(3));
   EXPECT_FALSE(simplex.isMarkedRedundant(4));
   EXPECT_FALSE(simplex.isMarkedRedundant(5));
 }
 
 TEST(SimplexTest, pivotRedundantRegressionTest) {
   Simplex simplex(2);
-  simplex.addInequality({-1, 0, -1}); // x <= -1.
+  addInequality(simplex, {-1, 0, -1}); // x <= -1.
   unsigned snapshot = simplex.getSnapshot();
 
-  simplex.addInequality({-1, 0, -2}); // x <= -2.
-  simplex.addInequality({-3, 0, -6});
+  addInequality(simplex, {-1, 0, -2}); // x <= -2.
+  addInequality(simplex, {-3, 0, -6});
 
   // This first marks x <= -1 as redundant. Then it performs some more pivots
   // to check if the other constraints are redundant. Pivot must update the
   // non-redundant rows as well, otherwise these pivots result in an incorrect
   // tableau state. In particular, after the rollback below, some rows that are
   // NOT marked redundant will have an incorrect state.
   simplex.detectRedundant();
 
   // After the rollback, the only remaining constraint is x <= -1.
   // The maximum value of x should be -1.
   simplex.rollback(snapshot);
   MaybeOptimum<Fraction> maxX =
-      simplex.computeOptimum(Simplex::Direction::Up, {1, 0, 0});
+      simplex.computeOptimum(Simplex::Direction::Up, getMPIntVec({1, 0, 0}));
   EXPECT_TRUE(maxX.isBounded() && *maxX == Fraction(-1, 1));
 }
 
 TEST(SimplexTest, addInequality_already_redundant) {
   Simplex simplex(1);
-  simplex.addInequality({1, -1}); // x >= 1.
-  simplex.addInequality({1, 0});  // x >= 0.
+  addInequality(simplex, {1, -1}); // x >= 1.
+  addInequality(simplex, {1, 0});  // x >= 0.
   simplex.detectRedundant();
   ASSERT_FALSE(simplex.isEmpty());
   EXPECT_FALSE(simplex.isMarkedRedundant(0));
   EXPECT_TRUE(simplex.isMarkedRedundant(1));
 }
 
 TEST(SimplexTest, appendVariable) {
   Simplex simplex(1);
 
   unsigned snapshot1 = simplex.getSnapshot();
   simplex.appendVariable();
   simplex.appendVariable(0);
   EXPECT_EQ(simplex.getNumVariables(), 2u);
 
   int64_t yMin = 2, yMax = 5;
-  simplex.addInequality({0, 1, -yMin}); // y >= 2.
-  simplex.addInequality({0, -1, yMax}); // y <= 5.
+  addInequality(simplex, {0, 1, -yMin}); // y >= 2.
+  addInequality(simplex, {0, -1, yMax}); // y <= 5.
 
   unsigned snapshot2 = simplex.getSnapshot();
   simplex.appendVariable(2);
   EXPECT_EQ(simplex.getNumVariables(), 4u);
   simplex.rollback(snapshot2);
 
   EXPECT_EQ(simplex.getNumVariables(), 2u);
   EXPECT_EQ(simplex.getNumConstraints(), 2u);
-  EXPECT_EQ(
-      simplex.computeIntegerBounds({0, 1, 0}),
-      std::make_pair(MaybeOptimum<int64_t>(yMin), MaybeOptimum<int64_t>(yMax)));
+  EXPECT_EQ(simplex.computeIntegerBounds(getMPIntVec({0, 1, 0})),
+            std::make_pair(MaybeOptimum<MPInt>(MPInt(yMin)),
+                           MaybeOptimum<MPInt>(MPInt(yMax))));
 
   simplex.rollback(snapshot1);
   EXPECT_EQ(simplex.getNumVariables(), 1u);
   EXPECT_EQ(simplex.getNumConstraints(), 0u);
 }
 
 TEST(SimplexTest, isRedundantInequality) {
   Simplex simplex(2);
-  simplex.addInequality({0, -1, 2}); // y <= 2.
-  simplex.addInequality({1, 0, 0});  // x >= 0.
-  simplex.addEquality({-1, 1, 0});   // y = x.
-
-  EXPECT_TRUE(simplex.isRedundantInequality({-1, 0, 2})); // x <= 2.
-  EXPECT_TRUE(simplex.isRedundantInequality({0, 1, 0}));  // y >= 0.
-
-  EXPECT_FALSE(simplex.isRedundantInequality({-1, 0, -1})); // x <= -1.
-  EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -2}));  // y >= 2.
-  EXPECT_FALSE(simplex.isRedundantInequality({0, 1, -1}));  // y >= 1.
+  addInequality(simplex, {0, -1, 2}); // y <= 2.
+  addInequality(simplex, {1, 0, 0});  // x >= 0.
+  addEquality(simplex, {-1, 1, 0});   // y = x.
+
+  EXPECT_TRUE(isRedundantInequality(simplex, {-1, 0, 2})); // x <= 2.
+  EXPECT_TRUE(isRedundantInequality(simplex, {0, 1, 0}));  // y >= 0.
+
+  EXPECT_FALSE(isRedundantInequality(simplex, {-1, 0, -1})); // x <= -1.
+  EXPECT_FALSE(isRedundantInequality(simplex, {0, 1, -2}));  // y >= 2.
+  EXPECT_FALSE(isRedundantInequality(simplex, {0, 1, -1}));  // y >= 1.
 }
 
 TEST(SimplexTest, ineqType) {
   Simplex simplex(2);
-  simplex.addInequality({0, -1, 2}); // y <= 2.
-  simplex.addInequality({1, 0, 0});  // x >= 0.
-  simplex.addEquality({-1, 1, 0});   // y = x.
+  addInequality(simplex, {0, -1, 2}); // y <= 2.
+  addInequality(simplex, {1, 0, 0});  // x >= 0.
+  addEquality(simplex, {-1, 1, 0});   // y = x.
 
-  EXPECT_TRUE(simplex.findIneqType({-1, 0, 2}) ==
+  EXPECT_EQ(findIneqType(simplex, {-1, 0, 2}),
               Simplex::IneqType::Redundant); // x <= 2.
-  EXPECT_TRUE(simplex.findIneqType({0, 1, 0}) ==
+  EXPECT_EQ(findIneqType(simplex, {0, 1, 0}),
               Simplex::IneqType::Redundant); // y >= 0.
 
-  EXPECT_TRUE(simplex.findIneqType({0, 1, -1}) ==
+  EXPECT_EQ(findIneqType(simplex, {0, 1, -1}),
               Simplex::IneqType::Cut); // y >= 1.
-  EXPECT_TRUE(simplex.findIneqType({-1, 0, 1}) ==
+  EXPECT_EQ(findIneqType(simplex, {-1, 0, 1}),
               Simplex::IneqType::Cut); // x <= 1.
-  EXPECT_TRUE(simplex.findIneqType({0, 1, -2}) ==
+  EXPECT_EQ(findIneqType(simplex, {0, 1, -2}),
               Simplex::IneqType::Cut); // y >= 2.
 
-  EXPECT_TRUE(simplex.findIneqType({-1, 0, -1}) ==
+  EXPECT_EQ(findIneqType(simplex, {-1, 0, -1}),
               Simplex::IneqType::Separate); // x <= -1.
 }
 
 TEST(SimplexTest, isRedundantEquality) {
   Simplex simplex(2);
-  simplex.addInequality({0, -1, 2}); // y <= 2.
-  simplex.addInequality({1, 0, 0});  // x >= 0.
-  simplex.addEquality({-1, 1, 0});   // y = x.
+  addInequality(simplex, {0, -1, 2}); // y <= 2.
+  addInequality(simplex, {1, 0, 0});  // x >= 0.
+  addEquality(simplex, {-1, 1, 0});   // y = x.
 
-  EXPECT_TRUE(simplex.isRedundantEquality({-1, 1, 0})); // y = x.
-  EXPECT_TRUE(simplex.isRedundantEquality({1, -1, 0})); // x = y.
+  EXPECT_TRUE(isRedundantEquality(simplex, {-1, 1, 0})); // y = x.
+  EXPECT_TRUE(isRedundantEquality(simplex, {1, -1, 0})); // x = y.
 
-  EXPECT_FALSE(simplex.isRedundantEquality({0, 1, -1})); // y = 1.
+  EXPECT_FALSE(isRedundantEquality(simplex, {0, 1, -1})); // y = 1.
 
-  simplex.addEquality({0, -1, 2}); // y = 2.
+  addEquality(simplex, {0, -1, 2}); // y = 2.
 
-  EXPECT_TRUE(simplex.isRedundantEquality({-1, 0, 2})); // x = 2.
+  EXPECT_TRUE(isRedundantEquality(simplex, {-1, 0, 2})); // x = 2.
 }
 
 TEST(SimplexTest, IsRationalSubsetOf) {
   IntegerPolyhedron univ = parsePoly("(x) : ()");
   IntegerPolyhedron empty = parsePoly("(x) : (x + 0 >= 0, -x - 1 >= 0)");
   IntegerPolyhedron s1 = parsePoly("(x) : ( x >= 0, -x + 4 >= 0)");
   IntegerPolyhedron s2 = parsePoly("(x) : (x - 1 >= 0, -x + 3 >= 0)");
 
TEST(SimplexTest, IsRationalSubsetOf) {
   EXPECT_TRUE(sim2.isRationalSubsetOf(univ));
   EXPECT_TRUE(sim2.isRationalSubsetOf(s1));
   EXPECT_TRUE(sim2.isRationalSubsetOf(s2));
   EXPECT_FALSE(sim2.isRationalSubsetOf(empty));
 }
 
 TEST(SimplexTest, addDivisionVariable) {
   Simplex simplex(/*nVar=*/1);
-  simplex.addDivisionVariable({1, 0}, 2);
-  simplex.addInequality({1, 0, -3}); // x >= 3.
-  simplex.addInequality({-1, 0, 9}); // x <= 9.
-  Optional<SmallVector<int64_t, 8>> sample = simplex.findIntegerSample();
+  simplex.addDivisionVariable(getMPIntVec({1, 0}), MPInt(2));
+  addInequality(simplex, {1, 0, -3}); // x >= 3.
+  addInequality(simplex, {-1, 0, 9}); // x <= 9.
+  Optional<SmallVector<MPInt, 8>> sample = simplex.findIntegerSample();
   ASSERT_TRUE(sample.has_value());
   EXPECT_EQ((*sample)[0] / 2, (*sample)[1]);
 }
 
 TEST(SimplexTest, LexIneqType) {
   LexSimplex simplex(/*nVar=*/1);
-  simplex.addInequality({2, -1}); // x >= 1/2.
+  addInequality(simplex, {2, -1}); // x >= 1/2.
 
   // Redundant inequality x >= 2/3.
-  EXPECT_TRUE(simplex.isRedundantInequality({3, -2}));
-  EXPECT_FALSE(simplex.isSeparateInequality({3, -2}));
+  EXPECT_TRUE(isRedundantInequality(simplex, {3, -2}));
+  EXPECT_FALSE(isSeparateInequality(simplex, {3, -2}));
 
   // Separate inequality x <= 2/3.
-  EXPECT_FALSE(simplex.isRedundantInequality({-3, 2}));
-  EXPECT_TRUE(simplex.isSeparateInequality({-3, 2}));
+  EXPECT_FALSE(isRedundantInequality(simplex, {-3, 2}));
+  EXPECT_TRUE(isSeparateInequality(simplex, {-3, 2}));
 
   // Cut inequality x <= 1.
-  EXPECT_FALSE(simplex.isRedundantInequality({-1, 1}));
-  EXPECT_FALSE(simplex.isSeparateInequality({-1, 1}));
+  EXPECT_FALSE(isRedundantInequality(simplex, {-1, 1}));
+  EXPECT_FALSE(isSeparateInequality(simplex, {-1, 1}));
 }

mlir/unittests/Analysis/Presburger/Utils.h

for (const auto &pair : data) {
     result.addPiece(
         domain, makeMatrix(numOutputs, domain.getNumVars() + 1, pair.second));
   }
   return result;
 }
 
 /// lhs and rhs represent non-negative integers or positive infinity. The
 /// infinity case corresponds to when the Optional is empty.
-inline bool infinityOrUInt64LE(Optional<uint64_t> lhs, Optional<uint64_t> rhs) {
+inline bool infinityOrUInt64LE(Optional<MPInt> lhs, Optional<MPInt> rhs) {
   // No constraint.
   if (!rhs)
     return true;
   // Finite rhs provided so lhs has to be finite too.
   if (!lhs)
     return false;
   return *lhs <= *rhs;
 }
 
 /// Expect that the computed volume is a valid overapproximation of
 /// the true volume `trueVolume`, while also being at least as good an
 /// approximation as `resultBound`.
 inline void
-expectComputedVolumeIsValidOverapprox(Optional<uint64_t> computedVolume,
-                                      Optional<uint64_t> trueVolume,
-                                      Optional<uint64_t> resultBound) {
+expectComputedVolumeIsValidOverapprox(const Optional<MPInt> &computedVolume,
+                                      const Optional<MPInt> &trueVolume,
+                                      const Optional<MPInt> &resultBound) {
   assert(infinityOrUInt64LE(trueVolume, resultBound) &&
          "can't expect result to be less than the true volume");
   EXPECT_TRUE(infinityOrUInt64LE(trueVolume, computedVolume));
   EXPECT_TRUE(infinityOrUInt64LE(computedVolume, resultBound));
 }
 
+inline void
+expectComputedVolumeIsValidOverapprox(const Optional<MPInt> &computedVolume,
+                                      Optional<int64_t> trueVolume,
+                                      Optional<int64_t> resultBound) {
+  expectComputedVolumeIsValidOverapprox(computedVolume,
+                                        trueVolume.map(mpintFromInt64),
+                                        resultBound.map(mpintFromInt64));
+}
+
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_UNITTESTS_ANALYSIS_PRESBURGER_UTILS_H