[MLIR][Presburger] Support lexicographic max/min union of two PWMAFunction

This patch implements a lexicographic max/min union of two PWMAFunctions.

The lexmax/lexmin union of two functions is defi

[MLIR][Presburger] Support lexicographic max/min union of two PWMAFunction

This patch implements a lexicographic max/min union of two PWMAFunctions.

The lexmax/lexmin union of two functions is defined as a function defined on
the union of the input domains of both functions, such that when only one of the
functions are defined, it outputs the same as that function, and if both are
defined, it outputs the lexmax/lexmin of the two outputs. On points where
neither function is defined, the union is not defined either.

Reviewed By: arjunp

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

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] Remove inheritence in MultiAffineFunction

This patch removes inheritence of MultiAffineFunction from IntegerPolyhedron
and instead makes IntegerPolyhedron as a member.

This patch

[MLIR][Presburger] Remove inheritence in MultiAffineFunction

This patch removes inheritence of MultiAffineFunction from IntegerPolyhedron
and instead makes IntegerPolyhedron as a member.

This patch removes virtualization in MultiAffineFunction and also removes
unnecessary functions inherited from IntegerPolyhedron.

Reviewed By: ftynse

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

show more ...

[MLIR][Presburger] change some `push_back`s to `emplace_back`s

[MLIR][Presburger] Remove inheritance from PresburgerSpace in IntegerRelation, PresburgerRelation and PWMAFunction

This patch removes inheritence from PresburgerSpace in IntegerRelation and
instead

[MLIR][Presburger] Remove inheritance from PresburgerSpace in IntegerRelation, PresburgerRelation and PWMAFunction

This patch removes inheritence from PresburgerSpace in IntegerRelation and
instead makes it a member of these classes.

This is required for three reasons:
- It prevents implicit casting to PresburgerSpace.
- Not all functions of PresburgerSpace need to be exposed by the deriving classes.
- IntegerRelation and IntegerPolyhedron are defined in a PresburgerSpace. It
makes more sense for the space to be a member instead of them inheriting from
a space.

Reviewed By: arjunp, ftynse

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

show more ...

[MLIR][Presburger] IntegerPolyhedron: add support for symbolic integer lexmin

Add support for computing the symbolic integer lexmin of a polyhedron.
This finds, for every assignment to the symbols,

[MLIR][Presburger] IntegerPolyhedron: add support for symbolic integer lexmin

Add support for computing the symbolic integer lexmin of a polyhedron.
This finds, for every assignment to the symbols, the lexicographically
minimum value attained by the dimensions. For example, the symbolic lexmin
of the set

`(x, y)[a, b, c] : (a <= x, b <= x, x <= c)`

can be written as

```
x = a if b <= a, a <= c
x = b if a < b, b <= c
```

This also finds the set of assignments to the symbols that make the lexmin unbounded.

This was previously landed in da92f92621e28a56fe8ad79d82eb60e436bf1d39 and
reverted in b238c252e8b1bbebc7ed79c08e06c23514d0dfb4 due to a build failure
in the code. Re-landing now with a fixed build.

Reviewed By: Groverkss

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

show more ...

Revert "[MLIR][Presburger] IntegerPolyhedron: add support for symbolic integer lexmin"

This reverts commit da92f92621e28a56fe8ad79d82eb60e436bf1d39.

[MLIR][Presburger] IntegerPolyhedron: add support for symbolic integer lexmin

Add support for computing the symbolic integer lexmin of a polyhedron.
This finds, for every assignment to the symbols,

[MLIR][Presburger] IntegerPolyhedron: add support for symbolic integer lexmin

Add support for computing the symbolic integer lexmin of a polyhedron.
This finds, for every assignment to the symbols, the lexicographically
minimum value attained by the dimensions. For example, the symbolic lexmin
of the set

`(x, y)[a, b, c] : (a <= x, b <= x, x <= c)`

can be written as

```
x = a if b <= a, a <= c
x = b if a < b, b <= c
```

This also finds the set of assignments to the symbols that make the lexmin unbounded.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] Use PresburgerSpace in constructors

This patch modifies IntegerPolyhedron, IntegerRelation, PresburgerRelation,
PresburgerSet, PWMAFunction, constructors to take PresburgerSpace i

[MLIR][Presburger] Use PresburgerSpace in constructors

This patch modifies IntegerPolyhedron, IntegerRelation, PresburgerRelation,
PresburgerSet, PWMAFunction, constructors to take PresburgerSpace instead of
dimensions. This allows information present in PresburgerSpace to be carried
better and allows for a general interface.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] MultiAffineFunction:eliminateRedundantLocalId: fix bug where local offset was not considered

Previously, when updating the outputs matrix, the local offset was not being considere

[MLIR][Presburger] MultiAffineFunction:eliminateRedundantLocalId: fix bug where local offset was not considered

Previously, when updating the outputs matrix, the local offset was not being considered.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] Merge PresburgerLocalSpace and PresburgerSpace

This patch is a cleanup patch that merges PresburgerLocalSpace and
PresburgerSpace. Asserting that there are no locals is shifted to

[MLIR][Presburger] Merge PresburgerLocalSpace and PresburgerSpace

This patch is a cleanup patch that merges PresburgerLocalSpace and
PresburgerSpace. Asserting that there are no locals is shifted to the
users of PresburgerSpace themselves.

The reasoning for this patch is that PresburgerLocalSpace did not contribute
much and only introduced additional complexity as locals could still be present
in PresburgerSpace, just not writable. This could introduce problems if a
PresburgerSpace with locals was copied to PresburgerLocalSpace which expected
no locals in a PresburgerSpace.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] PWMAFunction::valueAt: support local ids

Add a baseline implementation of support for local ids for `PWMAFunction::valueAt`. This can be made more efficient later if needed by han

[MLIR][Presburger] PWMAFunction::valueAt: support local ids

Add a baseline implementation of support for local ids for `PWMAFunction::valueAt`. This can be made more efficient later if needed by handling locals with known div representations separately.

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] MultiAffineFunction::removeIdRange: fix bug where kind wasn't passed on to IntegerPolyhedron::removeIdRange

Reviewed By: Groverkss

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

[MLIR][Presburger] MultiAffineFunction::removeIdRange: fix bug where kind wasn't passed on to IntegerPolyhedron::removeIdRange

Reviewed By: Groverkss

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

show more ...

[MLIR][Presburger] Support PWMAFunction::dump by calling into print

This was declared but not defined previously.

[MLIR][Presburger] Add support for PresburgerRelation

This patch adds supports for union of relations (PresburgerRelation). Along
with this, support for PresburgerSet is also maintained.

This patc

[MLIR][Presburger] Add support for PresburgerRelation

This patch adds supports for union of relations (PresburgerRelation). Along
with this, support for PresburgerSet is also maintained.

This patch is part of a series of patches to add support for relations in
Presburger library.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] Remove `spaceKind` from PresburgerSpace

This patch remove `spaceKind` from PresburgerSpace, making PresburgerSpace only
a space supporting relations.

Sets are still implemented i

[MLIR][Presburger] Remove `spaceKind` from PresburgerSpace

This patch remove `spaceKind` from PresburgerSpace, making PresburgerSpace only
a space supporting relations.

Sets are still implemented in the same way, i.e. with a zero domain but instead
the asserts to check if the space is still set are added to users of
PresburgerSpace which treat it as a Set space.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] Use IdKind for removeIdRange in PresburgerSpace

This patch moves PresburgerSpace::removeIdRange(idStart, idLimit) to
PresburgerSpace::removeIdRange(kind, idStart, idLimit), i.e. i

[MLIR][Presburger] Use IdKind for removeIdRange in PresburgerSpace

This patch moves PresburgerSpace::removeIdRange(idStart, idLimit) to
PresburgerSpace::removeIdRange(kind, idStart, idLimit), i.e. identifiers
can only be removed at once for a single kind.

This makes users of PresburgerSpace to not assume any inside ordering of
identifier kinds.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger][NFC] Cleanup PresburgerSet

This patch cleans up the interface to PresburgerSet. At a high level it does
the following changes:

- Move member functions around to have constructo

[MLIR][Presburger][NFC] Cleanup PresburgerSet

This patch cleans up the interface to PresburgerSet. At a high level it does
the following changes:

- Move member functions around to have constructors at top and print/dump
at end.
- Move a private function to be a static function instead.
- Change member functions of type "getAllIntegerPolyhedron" to "getAllPolys"
instead.
- Improve documentation for PresburgerSet.

Reviewed By: arjunp

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

show more ...

[MLIR][Presburger] Factor out various Space equality checks to PresburgerSpace::isEqual

This patch factors out various checks for dimension compatibility to
PresburgerSpace::isEqual and PresburgerLo

[MLIR][Presburger] Factor out various Space equality checks to PresburgerSpace::isEqual

This patch factors out various checks for dimension compatibility to
PresburgerSpace::isEqual and PresburgerLocalSpace::isEqual (for local
identifiers).

Reviewed By: arjunp

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

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][Presburger] Add support for piece-wise multi-affine functions

Add the class MultiAffineFunction which represents functions whose domain is an
IntegerPolyhedron and which produce an output giv

[MLIR][Presburger] Add support for piece-wise multi-affine functions

Add the class MultiAffineFunction which represents functions whose domain is an
IntegerPolyhedron and which produce an output given by a tuple of affine
expressions in the IntegerPolyhedron's ids.

Also add support for piece-wise MultiAffineFunctions, which are defined on a
union of IntegerPolyhedrons, and may have different output affine expressions
on each IntegerPolyhedron. Thus the function is affine on each individual
IntegerPolyhedron piece in the domain.

This is part of a series of patches leading up to parametric integer programming.

Depends on D118778.

Reviewed By: Groverkss

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

show more ...