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