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] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is pa

[mlir] Use std::optional instead of llvm::Optional (NFC)

This patch replaces (llvm::|)Optional< with std::optional<. I'll post
a separate patch to remove #include "llvm/ADT/Optional.h".

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[mlir] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Optiona

[mlir] Add #include <optional> (NFC)

This patch adds #include <optional> to those files containing
llvm::Optional<...> or Optional<...>.

I'll post a separate patch to actually replace llvm::Optional with
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[MLIR][Presburger] Improve unittest parsing

This patch adds better functions for parsing MultiAffineFunctions and
PWMAFunctions in Presburger unittests.

A PWMAFunction can now be parsed as:

```
PW

[MLIR][Presburger] Improve unittest parsing

This patch adds better functions for parsing MultiAffineFunctions and
PWMAFunctions in Presburger unittests.

A PWMAFunction can now be parsed as:

```
PWMAFunction result = parsePWMAF({
{"(x, y) : (x >= 10, x <= 20, y >= 1)", "(x, y) -> (x + y)"},
{"(x, y) : (x >= 21)", "(x, y) -> (x + y)"},
{"(x, y) : (x <= 9)", "(x, y) -> (x - y)"},
{"(x, y) : (x >= 10, x <= 20, y <= 0)", "(x, y) -> (x - y)"},
});
```

which is much more readable than the old format since the output can be
described as an AffineMap, instead of coefficients.

This patch also adds support for parsing divisions in MultiAffineFunctions
and PWMAFunctions which was previously not possible.

Reviewed By: arjunp

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

show more ...

Revert "[MLIR][Presburger] Improve unittest parsing"

This reverts commit 84d07d021333f7b5716f0444d5c09105557272e0.

Reverted to fix a compilation issue on gcc8.

[MLIR][Presburger] Improve unittest parsing

This patch adds better functions for parsing MultiAffineFunctions and
PWMAFunctions in Presburger unittests.

A PWMAFunction can now be parsed as:

```
PW

[MLIR][Presburger] Improve unittest parsing

This patch adds better functions for parsing MultiAffineFunctions and
PWMAFunctions in Presburger unittests.

A PWMAFunction can now be parsed as:

```
PWMAFunction result = parsePWMAF({
{"(x, y) : (x >= 10, x <= 20, y >= 1)", "(x, y) -> (x + y)"},
{"(x, y) : (x >= 21)", "(x, y) -> (x + y)"},
{"(x, y) : (x <= 9)", "(x, y) -> (x - y)"},
{"(x, y) : (x >= 10, x <= 20, y <= 0)", "(x, y) -> (x - y)"},
});
```

which is much more readable than the old format since the output can be
described as an AffineMap, instead of coefficients.

This patch also adds support for parsing divisions in MultiAffineFunctions
and PWMAFunctions which was previously not possible.

Reviewed By: arjunp

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

show more ...

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

Only the main Presburger library under the Presburger directory has been switched to use arbitrary precision. User

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

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.

Reviewed By: bondhugula

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

show more ...

[mlir] Use has_value instead of hasValue (NFC)

Revert "Don't use Optional::hasValue (NFC)"

This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.

Don't use Optional::hasValue (NFC)

[MLIR][Presburger] LexSimplex: support is{Redundant,Separate}Inequality

Add integer-exact checks for inequalities being separate and redundant in LexSimplex.

Reviewed By: Groverkss

Differential Re

[MLIR][Presburger] LexSimplex: support is{Redundant,Separate}Inequality

Add integer-exact checks for inequalities being separate and redundant in LexSimplex.

Reviewed By: Groverkss

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

show more ...

Revert "[MLIR][Presburger] LexSimplex::addEquality: add equalities as fixed columns"

This reverts commit 5630143af33f7e6e0dabdf38982cc9800140bb75. The
implementation in this commit was incorrect. Al

Revert "[MLIR][Presburger] LexSimplex::addEquality: add equalities as fixed columns"

This reverts commit 5630143af33f7e6e0dabdf38982cc9800140bb75. The
implementation in this commit was incorrect. Also, handling this representation
of equalities in the upcoming support for symbolic lexicographic minimization
makes that patch much more complex. It will be easier to review that without
this representaiton and then reintroduce the fixed column representation
later, hence the revert rather than a bug fix.

show more ...

[MLIR][Presburger] LexSimplex::addEquality: add equalities as fixed columns

In LexSimplex, instead of adding equalities as a pair of inequalities,
add them as a single row, move them into the basis,

[MLIR][Presburger] LexSimplex::addEquality: add equalities as fixed columns

In LexSimplex, instead of adding equalities as a pair of inequalities,
add them as a single row, move them into the basis, and keep them there.

There will always be a valid basis involving all non-redundant equalities. Such
equalities will then be ignored in some other operations, such as when looking
for pivot columns. This speeds them up a little bit.

More importantly, this is an important precursor patch to adding support for
symbolic integer lexmin, as this heuristic can sometimes make a big difference there.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] add Simplex:addDivisionVariable

This is a convenience function for adding new divisions to the Simplex given the numerator and denominator.

This will be needed for symbolic integ

[MLIR][Presburger] add Simplex:addDivisionVariable

This is a convenience function for adding new divisions to the Simplex given the numerator and denominator.

This will be needed for symbolic integer lexmin support.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] fix the names of some tests (NFC)

[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][Presburger] unittests: use an MLIRContext declared in parsePoly

Use an `MLIRContext` declared in a single place in the `parsePoly` function that almost all Presburger unit tests use for parsi

[MLIR][Presburger] unittests: use an MLIRContext declared in parsePoly

Use an `MLIRContext` declared in a single place in the `parsePoly` function that almost all Presburger unit tests use for parsing sets. This function is only used in tests.

This saves us from having to declare and pass a new `MLIRContext` in every test.

Reviewed By: bondhugula, mehdi_amini

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

show more ...

[MLIR][Presburger] Inequality Typing in coalesce

This patch adds typing of inequalities to the simplex. This is a cental part of the coalesce algorithm and will be heavily used in later coalesce pat

[MLIR][Presburger] Inequality Typing in coalesce

This patch adds typing of inequalities to the simplex. This is a cental part of the coalesce algorithm and will be heavily used in later coalesce patches. Currently, only the three most basic types are supported with more to be introduced when they are needed.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] Introduce MaybeOptimum type to represent computed optima

This allows to differentiate between the cases where the optimum does not
exist due to being unbounded and due to the poly

[MLIR][Presburger] Introduce MaybeOptimum type to represent computed optima

This allows to differentiate between the cases where the optimum does not
exist due to being unbounded and due to the polytope being empty.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] Simplex::computeIntegerBounds: support unbounded directions by returning Optionals

[MLIR][Presburger] factor out duplicated function `parsePoly` into a Utils.h

Reviewed By: Groverkss

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

[mlir:Analysis] Move the LoopAnalysis library to Dialect/Affine/Analysis

The current state of the top level Analysis/ directory is that it contains two libraries;
a generic Analysis library (free fr

[mlir:Analysis] Move the LoopAnalysis library to Dialect/Affine/Analysis

The current state of the top level Analysis/ directory is that it contains two libraries;
a generic Analysis library (free from dialect dependencies), and a LoopAnalysis library
that contains various analysis utilities that originated from Affine loop transformations.
This commit moves the LoopAnalysis to the more appropriate home of `Dialect/Affine/Analysis/`,
given the use and intention of the majority of the code within it. After the move, if there
are generic utilities that would fit better in the top-level Analysis/ directory, we can move
them.

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

show more ...

Apply clang-tidy fixes for performance-unnecessary-value-param to MLIR (NFC)

Reviewed By: Mogball

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