[MLIR] Use a shared uniquer for affine maps and integer sets.

Affine maps and integer sets previously relied on a single lock for creating unique instances. In a multi-threaded setting, this lock be

[MLIR] Use a shared uniquer for affine maps and integer sets.

Affine maps and integer sets previously relied on a single lock for creating unique instances. In a multi-threaded setting, this lock becomes a contention point. This commit updates AffineMap and IntegerSet to use StorageUniquer instead. StorageUniquer internally uses sharded locks and thread-local caches to reduce contention. It is already used for affine expressions, types and attributes. On my local machine, this gives me a 5X speedup for an application that manipulates a lot of affine maps and integer sets.

This commit also removes the integer set uniquer threshold. The threshold was used to avoid adding integer sets with a lot of constraints to the hash_map containing unique instances, but the constraints and the integer set were still allocated in the same allocator and never freed, thus not saving any space expect for the hash-map entry.

Reviewed By: rriddle

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

show more ...

[MLIR][NFC] drop some unnecessary includes

Drop unnecessary includes

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

Mass update the MLIR license header to mention "Part of the LLVM project"

This is an artifact from merging MLIR into LLVM, the file headers are
now aligned with the rest of the project.

Import MLIR into the LLVM tree

Adjust License.txt file to use the LLVM license

PiperOrigin-RevId: 286906740

NFC: Remove unnecessary 'llvm::' prefix from uses of llvm symbols declared in `mlir` namespace.

Aside from being cleaner, this also makes the codebase more consistent.

PiperOrigin-RevId: 286206974

Fix typos, NFC.

PiperOrigin-RevId: 272851237

Integer set + operands / affine if op canonicalization

- turn canonicalizeMapAndOperands into a template that works on both
sets and maps, and use it to introduce a utility to canonicalize an
af

Integer set + operands / affine if op canonicalization

- turn canonicalizeMapAndOperands into a template that works on both
sets and maps, and use it to introduce a utility to canonicalize an
affine integer set and its operands
- add pattern to canonicalize affine if op's.
- rename IntegerSet::getNumOperands -> IntegerSet::getNumInputs to be
consistent with AffineMap
- add missing accessors for IntegerSet

Doesn't need extensive testing since canonicalizeSetAndOperands just
reuses canonicalizeMapAndOperands' logic, and the latter is tested on
affine.apply map + operands; the new method works the same way on an
integer set + operands of an affine if op for example.

Signed-off-by: Uday Bondhugula <uday@polymagelabs.com>

Closes tensorflow/mlir#112

COPYBARA_INTEGRATE_REVIEW=https://github.com/tensorflow/mlir/pull/112 from bondhugula:set-canonicalize eff72f23250b96fa7d9f5caff3877440f5de2cec
PiperOrigin-RevId: 267532876

show more ...

Introduce Fourier-Motzkin variable elimination + other cleanup/support

- Introduce Fourier-Motzkin variable elimination to eliminate a dimension from
a system of linear equalities/inequalities. Up

Introduce Fourier-Motzkin variable elimination + other cleanup/support

- Introduce Fourier-Motzkin variable elimination to eliminate a dimension from
a system of linear equalities/inequalities. Update isEmpty to use this.
Since FM is only exact on rational/real spaces, an emptiness check based on
this is guaranteed to be exact whenever it says the underlying set is empty;
if it says, it's not empty, there may still be no integer points in it.
Also, supports a version that computes "dark shadows".

- Test this by checking for "always false" conditionals in if statements.

- Unique IntegerSet's that are small (few constraints, few variables). This
basically means the canonical empty set and other small sets that are
likely commonly used get uniqued; allows checking for the canonical empty set
by pointer. IntegerSet::kUniquingThreshold gives the threshold constraint size
for uniqui'ing.

- rename simplify-affine-expr -> simplify-affine-structures

Other cleanup

- IntegerSet::numConstraints, AffineMap::numResults are no longer needed;
remove them.
- add copy assignment operators for AffineMap, IntegerSet.
- rename Invalid() -> Null() on AffineExpr, AffineMap, IntegerSet
- Misc cleanup for FlatAffineConstraints API

PiperOrigin-RevId: 218690456

show more ...

Adds Gaussian Elimination to FlatAffineConstraints.
- Adds FlatAffineConstraints::isEmpty method to test if there are no solutions to the system.
- Adds GCD test check if equality constraints have no

Adds Gaussian Elimination to FlatAffineConstraints.
- Adds FlatAffineConstraints::isEmpty method to test if there are no solutions to the system.
- Adds GCD test check if equality constraints have no solution.
- Adds unit test cases.

PiperOrigin-RevId: 218546319

show more ...

[MLIR] IntegerSet value type

This CL applies the same pattern as AffineMap to IntegerSet: a simple struct
that acts as the storage is allocated in the bump pointer. The IntegerSet is
immutable and a

[MLIR] IntegerSet value type

This CL applies the same pattern as AffineMap to IntegerSet: a simple struct
that acts as the storage is allocated in the bump pointer. The IntegerSet is
immutable and accessed everywhere by value.

Note that unlike AffineMap, it is not possible to remove the MLIRContext
parameter when constructing an IntegerSet for now. One possible way to achieve
this would be to add an enum to distinguish between the mathematically empty
set, the universe set and other sets.

This is left for future discussion.

PiperOrigin-RevId: 216545361

show more ...

[MLIR] AffineExpr final cleanups

This CL:
1. performs the global codemod AffineXExpr->AffineXExprClass and
AffineXExprRef -> AffineXExpr;
2. simplifies function calls by removing the redundant MLIRC

[MLIR] AffineExpr final cleanups

This CL:
1. performs the global codemod AffineXExpr->AffineXExprClass and
AffineXExprRef -> AffineXExpr;
2. simplifies function calls by removing the redundant MLIRContext parameter;
3. adds missing binary operator versions of scalar op AffineExpr where it
makes sense.

PiperOrigin-RevId: 216242674

show more ...

[RFC][MLIR] Use AffineExprRef in place of AffineExpr* in IR

This CL starts by replacing AffineExpr* with value-type AffineExprRef in a few
places in the IR. By a domino effect that is pretty telling

[RFC][MLIR] Use AffineExprRef in place of AffineExpr* in IR

This CL starts by replacing AffineExpr* with value-type AffineExprRef in a few
places in the IR. By a domino effect that is pretty telling of the
inconsistencies in the codebase, const is removed where it makes sense.

The rationale is that the decision was concisously made that unique'd types
have pointer semantics without const specifier. This is fine but we should be
consistent. In the end, the only logical invariant is that there should never
be such a thing as a const AffineExpr*, const AffineMap* or const IntegerSet*
in our codebase.

This CL takes a number of shortcuts to killing const with fire, in particular
forcing const AffineExprRef to return the underlying non-const
AffineExpr*. This will be removed once AffineExpr* has disappeared in
containers but for now such shortcuts allow a bit of sanity in this long quest
for cleanups.

The **only** places where const AffineExpr*, const AffineMap* or const
IntegerSet* may still appear is by transitive needs from containers,
comparison operators etc.

There is still one major thing remaining here: figure out why cast/dyn_cast
return me a const AffineXXX*, which in turn requires a bunch of ugly
const_casts. I suspect this is due to the classof
taking const AffineXXXExpr*. I wonder whether this is a side effect of 1., if
it is coming from llvm itself (I'd doubt it) or something else (clattner@?)

In light of this, the whole discussion about const makes total sense to me now
and I would systematically apply the rule that in the end, we should never
have any const XXX in our codebase for unique'd types (assuming we can remove
them all in containers and no additional constness constraint is added on us
from the outside world).

PiperOrigin-RevId: 215811554

show more ...

Support for affine integer sets

- introduce affine integer sets into the IR
- parse and print affine integer sets (both inline or outlined) similar to
affine maps
- use integer set for IfStmt's co

Support for affine integer sets

- introduce affine integer sets into the IR
- parse and print affine integer sets (both inline or outlined) similar to
affine maps
- use integer set for IfStmt's conditional, and implement parsing of IfStmt's
conditional

- fixed an affine expr paren omission bug while one this.

TODO: parse/represent/print MLValue operands to affine integer set references.
PiperOrigin-RevId: 207779408

show more ...