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 findSymbolicIntegerLexMax for IntegerRelation

This patch implements findSymbolicIntegerLexMax for IntegerRelation

Reviewed By: Groverkss

Differential Revision: https:/

[MLIR][Presburger] Implement findSymbolicIntegerLexMax for IntegerRelation

This patch implements findSymbolicIntegerLexMax for IntegerRelation

Reviewed By: Groverkss

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

show more ...

[mlir][Analysis][NFC] Make BoundType a top-level enum

`BoundType` is no longer a nested member of `IntegerRelation` but a top-level enum in the `presburger` namespace.

This allows `BoundType` to be

[mlir][Analysis][NFC] Make BoundType a top-level enum

`BoundType` is no longer a nested member of `IntegerRelation` but a top-level enum in the `presburger` namespace.

This allows `BoundType` to be predeclared in header files. Nested members cannot be predeclared.

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

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] Use std::nullopt instead of None in comments (NFC)

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

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalu

[mlir] Use std::nullopt instead of None in comments (NFC)

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] Fix ambiguity when building with Clang 14.0.6

Differential revision: https://reviews.llvm.org/D134219

[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] clarify why -0 is used instead of 0 (NFC)

[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][Presburger] Refactor MultiAffineFunction to be defined over universe

This patch refactors MAF to be defined over the universe in a given space
instead of being defined over a restricted domai

[MLIR][Presburger] Refactor MultiAffineFunction to be defined over universe

This patch refactors MAF to be defined over the universe in a given space
instead of being defined over a restricted domain.

The reasoning for this refactor is to store division representation for local
variables explicitly for the function outputs. This change is required for
unionLexMax/Min to support local variables which will be upstreamed after this
patch. Another reason for this refactor is to have a flattened form of
AffineMap as MultiAffineFunction.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] make sample test with integer lexmin use containsPointNoLocal

IntegerPolyhedron::findIntegerLexmin currently does not return values of
the local ids, so when a test for sampling i

[MLIR][Presburger] make sample test with integer lexmin use containsPointNoLocal

IntegerPolyhedron::findIntegerLexmin currently does not return values of
the local ids, so when a test for sampling includes a set with locals, the
result of findIntegerLexmin should be checked using containsPointNoLocal,
not containsPoint.

show more ...

[MLIR][Presburger] fix warning under g++ (NFC)

[mlir] Use has_value instead of hasValue (NFC)

[MLIR][Presburger] Refactor division representation to DivisionRepr

This patch refactors existing implementations of division representation storage
into a new class, DivisionRepr. This refactoring

[MLIR][Presburger] Refactor division representation to DivisionRepr

This patch refactors existing implementations of division representation storage
into a new class, DivisionRepr. This refactoring is done so that the common
division utilities can be shared in an upcoming patch.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] support symbolicLexMin for IntegerRelation

This also changes the space of the returned lexmin for IntegerPolyhedrons;
the symbols in the poly now correspond to symbols in the resu

[MLIR][Presburger] support symbolicLexMin for IntegerRelation

This also changes the space of the returned lexmin for IntegerPolyhedrons;
the symbols in the poly now correspond to symbols in the result rather than dims.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] Rename variable/identifier -> variable

Currently, in the Presburger library, we use the words "variables" and
"identifiers" interchangeably. This patch changes this to only use "v

[MLIR][Presburger] Rename variable/identifier -> variable

Currently, in the Presburger library, we use the words "variables" and
"identifiers" interchangeably. This patch changes this to only use "variables" to
refer to the variables of PresburgerSpace.

The reasoning behind this change is that the current usage of the word "identifier"
is misleading. variables do not "identify" anything. The information attached to them is the
actual "identifier" for the variable. The word "identifier", will later be used
to refer to the information attached to each variable in space.

Reviewed By: ftynse

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

show more ...

[MLIR][Presburger] getDivRepr: fix bug where dividend was negated

Also updated the tests, which were asserting the wrong behaviour.

Reviewed By: Groverkss

Differential Revision: https://reviews.ll

[MLIR][Presburger] getDivRepr: fix bug where dividend was negated

Also updated the tests, which were asserting the wrong behaviour.

Reviewed By: Groverkss

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

show more ...

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

This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.

Don't use Optional::hasValue (NFC)

[MLIR][Presburger] Make IntegerRelation::mergeLocalIds not delete duplicates

This patch modifies mergeLocalIds to not delete duplicate local ids in
`this` relation. This allows the ordering of the f

[MLIR][Presburger] Make IntegerRelation::mergeLocalIds not delete duplicates

This patch modifies mergeLocalIds to not delete duplicate local ids in
`this` relation. This allows the ordering of the final local ids for `this`
to be determined more easily, which is generally required when other objects
refer to these local ids.

Reviewed By: arjunp

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

show more ...