[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

[MLIR] Use IntegerPolyhedron in Simplex instead of FlatAffineConstraints

This patch replaces usage of FlatAffineConstraints in Simplex with
IntegerPolyhedron. This removes dependency of Simplex on F

[MLIR] Use IntegerPolyhedron in Simplex instead of FlatAffineConstraints

This patch replaces usage of FlatAffineConstraints in Simplex with
IntegerPolyhedron. This removes dependency of Simplex on FlatAffineConstraints
and puts it on IntegerPolyhedron, which is part of Presburger library.

Reviewed By: arjunp

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

show more ...

[MLIR] Introduce coalesce for PresburgerSet

This patch provides functionality for simplifying `PresburgerSet`s by checking if any `FlatAffineConstraints` in the set is contained in another, and remo

[MLIR] Introduce coalesce for PresburgerSet

This patch provides functionality for simplifying `PresburgerSet`s by checking if any `FlatAffineConstraints` in the set is contained in another, and removing such redundant FACs.

This is part of a series of patches to provide functionality for [integer set coalescing](http://impact.gforge.inria.fr/impact2015/papers/impact2015-verdoolaege.pdf) in MLIR.

Reviewed By: arjunp

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

show more ...

[MLIR] Simplex: fix a bug when rolling back a Simplex with no solutions

Previously, when adding a constraint to a Simplex that is already marked
as having no solutions (marked empty), the Simplex wo

[MLIR] Simplex: fix a bug when rolling back a Simplex with no solutions

Previously, when adding a constraint to a Simplex that is already marked
as having no solutions (marked empty), the Simplex would be marked empty again,
and a second UnmarkEmpty entry would be pushed to the undo log. When rolling
back, Simplex should be unmarked empty only after rolling back past the
creation of the first constraint that made it empty.

Reviewed By: Groverkss

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

show more ...

[MLIR] Simplex::pivot: also update the redundant rows when pivoting

Previously, the pivot function would only update the non-redundant rows when
pivoting. This is incorrect because in some cases, wh

[MLIR] Simplex::pivot: also update the redundant rows when pivoting

Previously, the pivot function would only update the non-redundant rows when
pivoting. This is incorrect because in some cases, when rolling back past a
`detectRedundant` call, the basis being used could be different from that which
was used at the time of returning from the `detectRedundant` call. Therefore,
it is important to update the redundant rows as well during pivots. This could
also be triggered by pivots that occur when testing successive constraints for
being redundant in `detectRedundant` after some initial constraints are marked redundant.

Reviewed By: Groverkss

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

show more ...

[MLIR] Simplex::appendVariable: early return if count == 0

[MLIR] Simplex: rename num{Variables,Constraints} to getNum{Variables,Constraints}

As per the LLVM Coding Standards, function names should be verb phrases.

[MLIR] Simplex: support adding new variables dynamically

Reviewed By: Groverkss

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

[MLIR] Redundancy detection for FlatAffineConstraints using Simplex

This patch adds the capability to perform constraint redundancy checks for `FlatAffineConstraints` using `Simplex`, via a new memb

[MLIR] Redundancy detection for FlatAffineConstraints using Simplex

This patch adds the capability to perform constraint redundancy checks for `FlatAffineConstraints` using `Simplex`, via a new member function `FlatAffineConstraints::removeRedundantConstraints`. The pre-existing redundancy detection algorithm runs a full rational emptiness check for each inequality separately for checking redundancy. Leveraging the existing `Simplex` infrastructure, in this patch we have an algorithm for redundancy checks that can check each constraint by performing pivots on the tableau, which provides an alternative to running Fourier-Motzkin elimination for each constraint separately.

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

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 ...