Reland "mlir/Presburger/MPInt: move into llvm/ADT" (#95254)

Change: remove guards on debug-printing, to allow Release builds without
LLVM_ENABLE_DUMP to pass.

MPInt is an arbitrary-precision int

Reland "mlir/Presburger/MPInt: move into llvm/ADT" (#95254)

Change: remove guards on debug-printing, to allow Release builds without
LLVM_ENABLE_DUMP to pass.

MPInt is an arbitrary-precision integer library that builds on top of
APInt, and has a fast-path when the number fits within 64 bits. It was
originally written for the Presburger library in MLIR, but seems useful
to the LLVM project in general, independently of the Presburger library
or MLIR. Hence, move it into LLVM/ADT under the name DynamicAPInt.

This patch is part of a project to move the Presburger library into
LLVM.

show more ...

Revert #95218 and #94953 (#95244)

mlir/Presburger/MPInt: move into llvm/ADT (#94953)

MPInt is an arbitrary-precision integer library that builds on top of
APInt, and has a fast-path when the number fits within 64 bits. It was
orig

mlir/Presburger/MPInt: move into llvm/ADT (#94953)

MPInt is an arbitrary-precision integer library that builds on top of
APInt, and has a fast-path when the number fits within 64 bits. It was
originally written for the Presburger library in MLIR, but seems useful
to the LLVM project in general, independently of the Presburger library
or MLIR. Hence, move it into LLVM/ADT under the name DynamicAPInt.

This patch is part of a project to move the Presburger library into
LLVM.

show more ...

[MLIR][Presburger] Implement Matrix::moveColumns (#68362)

[MLIR][Presburger] Fix a bug with determinant of IntMatrix (#76622)

Fixed a bug where IntMatrix determinant() had a bug where it would try to assign to a null
pointer.
Added a test case that trigger

[MLIR][Presburger] Fix a bug with determinant of IntMatrix (#76622)

Fixed a bug where IntMatrix determinant() had a bug where it would try to assign to a null
pointer.
Added a test case that triggers this bug to avoid regressions.

show more ...

[MLIR][Presburger] Add LLL basis reduction (#75565)

Add a method for LLL basis reduction to the FracMatrix class.
This needs an abs() method for Fractions, which is added to Fraction.h.

[MLIR][Presburger] Add Gram-Schmidt (#70843)

Implement Gram-Schmidt orthogonalisation for the FracMatrix class.
This requires dotProduct, which has been added as a util.

[MLIR][Presburger] Implement matrix inverse (#67382)

Shift the `determinant()` function from LinearTransform to Matrix.
Implement a FracMatrix class, inheriting from Matrix<Fraction>, for inverses.

[MLIR][Presburger] Implement matrix inverse (#67382)

Shift the `determinant()` function from LinearTransform to Matrix.
Implement a FracMatrix class, inheriting from Matrix<Fraction>, for inverses.
Implement inverse for FracMatrix and intInverse for IntMatrix.
Make Matrix internals protected instead of private so that Int/FracMatrix can access them.

show more ...

[MLIR][Presburger] Template Matrix to allow MPInt and Fraction; use IntMatrix for integer matrices (#66897)

Matrix has been templated to Matrix (for MPInt and Fraction) with
explicit instantiation

[MLIR][Presburger] Template Matrix to allow MPInt and Fraction; use IntMatrix for integer matrices (#66897)

Matrix has been templated to Matrix (for MPInt and Fraction) with
explicit instantiation for both these types.
IntMatrix, inheriting from Matrix<MPInt>, has been created to allow for
integer-only methods.
makeMatrix has been duplicated to makeIntMatrix and makeFracMatrix.

This was already landed previously but was reverted in
98c994c8e22d7f38cc04f56ee5cdeb337734414d due to build failure. This
fixes the failure.

show more ...

Revert "[MLIR][Presburger] Template Matrix to allow MPInt and Fraction (#65272)"

This reverts commit efca035c6d28542ad6374cd8bf17ae7c72407ead.

Reverting due to windows build bot failure:
https://la

Revert "[MLIR][Presburger] Template Matrix to allow MPInt and Fraction (#65272)"

This reverts commit efca035c6d28542ad6374cd8bf17ae7c72407ead.

Reverting due to windows build bot failure:
https://lab.llvm.org/buildbot/#/builders/13/builds/40242/steps/6/logs/stdio

show more ...

[MLIR][Presburger] Template Matrix to allow MPInt and Fraction (#65272)

The method implementations remain in the .cpp file; explicit instantiations have been added for these two types.
makeMatrix

[MLIR][Presburger] Template Matrix to allow MPInt and Fraction (#65272)

The method implementations remain in the .cpp file; explicit instantiations have been added for these two types.
makeMatrix has been duplicated to makeIntMatrix and makeFracMatrix.

show more ...

[MLIR][Presburger] Add hermite normal form computation to Matrix

This patch adds hermite normal form computation to Matrix. Part of this algorithm
lived in LinearTransform, being used for compuing c

[MLIR][Presburger] Add hermite normal form computation to Matrix

This patch adds hermite normal form computation to Matrix. Part of this algorithm
lived in LinearTransform, being used for compuing column echelon form. This
patch moves the implementation to Matrix::hermiteNormalForm and generalises it
to compute the hermite normal form.

Reviewed By: arjunp

Differential Revision: https://reviews.llvm.org/D133510

show more ...

[MLIR][Presburger] Move Presburger/ files to presburger namespace

This patch moves the Presburger library to a new `presburger` namespace.

This allows to shorten some names, helps to avoid pollutin

[MLIR][Presburger] Move Presburger/ files to presburger namespace

This patch moves the Presburger library to a new `presburger` namespace.

This allows to shorten some names, helps to avoid polluting the mlir namespace,
and also provides some structure.

Reviewed By: arjunp

Differential Revision: https://reviews.llvm.org/D120505

show more ...

[MLIR] Matrix: support resizing horizontally

Reviewed By: Groverkss

Differential Revision: https://reviews.llvm.org/D109897

[MLIR] FlatAffineConstraints: Use Matrix objects to store the constraints

This results in significant deduplication of code. This patch is not expected to change any functionality, it's just some si

[MLIR] FlatAffineConstraints: Use Matrix objects to store the constraints

This results in significant deduplication of code. This patch is not expected to change any functionality, it's just some simplification in preparation for future work. Also slightly simplified some code that was being touched anyway and added some unit tests for some functions that were touched.

Reviewed By: bondhugula

Differential Revision: https://reviews.llvm.org/D105152

show more ...

[MLIR] Exact integer emptiness checks for FlatAffineConstraints

This patch adds the capability to perform exact integer emptiness checks for FlatAffineConstraints using the General Basis Reduction a

[MLIR] Exact integer emptiness checks for FlatAffineConstraints

This patch adds the capability to perform exact integer emptiness checks for FlatAffineConstraints using the General Basis Reduction algorithm (GBR). Previously, only a heuristic was available for emptiness checks, which was not guaranteed to always give a conclusive result.

This patch adds a `Simplex` class, which can be constructed using a `FlatAffineConstraints`, and can find an integer sample point (if one exists) using the GBR algorithm. Additionally, it adds two classes `Matrix` and `Fraction`, which are used by `Simplex`.

The integer emptiness check functionality can be accessed through the new `FlatAffineConstraints::isIntegerEmpty()` function, which runs the existing heuristic first and, if that proves to be inconclusive, runs the GBR algorithm to produce a conclusive result.

Differential Revision: https://reviews.llvm.org/D80860

show more ...