[MLIR][Analysis] Consolidate topological sort utilities (#92563)

This PR attempts to consolidate the different topological sort utilities
into one place. It adds them to the analysis folder becaus

[MLIR][Analysis] Consolidate topological sort utilities (#92563)

This PR attempts to consolidate the different topological sort utilities
into one place. It adds them to the analysis folder because the
`SliceAnalysis` uses some of these.

There are now two different sorting strategies:
1. Sort only according to SSA use-def chains
2. Sort while taking regions into account. This requires a much more
elaborate traversal and cannot be applied on graph regions that easily.

This additionally reimplements the region aware topological sorting
because the previous implementation had an exponential space complexity.

I'm open to suggestions on how to combine this further or how to fuse
the test passes.

show more ...

[mlir][NFC] Simplify type checks with isa predicates (#87183)

For more context on isa predicates, see:
https://github.com/llvm/llvm-project/pull/83753.

[MLIR] NFC. Clean up stale TODO comments and style deviations in affine utils (#79079)

NFC. Clean up stale TODO comments and style deviations in affine utils
and
affine fusion utils.

Revert "[mlir][affine] implement `promoteIfSingleIteration` for `AffineForOp` (#72547)"

This reverts commit aa6be2f7c94ea3302fcc1ab034a85cd375eaa800.

[mlir][affine] implement `promoteIfSingleIteration` for `AffineForOp` (#72547)

Generalize affine fusion to work at all depths and inside other region-holding ops (#72288)

Generalize affine fusion to work at any inner depth; fusing loops inside
other
affine.for or even inside

Generalize affine fusion to work at all depths and inside other region-holding ops (#72288)

Generalize affine fusion to work at any inner depth; fusing loops inside
other
affine.for or even inside scf.for or scf.while nests. Apply in post
order on
all affine nests on the pass' top-level operation.

Fix MDG init for blocks inside other affine nests.

Relax unnecessary requirement for unique vars during merge and align of
FlatLinearValueConstraints. There are several cases where
FlatLinearValueConstraints need to have duplicate Values for the
dimensions:
for eg. in dependence relation systems with source and destination
accesses
could have common loop IVs. `mergeAndAlign` can be done even in the
presence
of Values reappearing by simply aligning from left to right in that
order.

While at this, drop outdated comments; improve some debug messages.

show more ...

[mlir][Interfaces] `LoopLikeOpInterface`: Add `replaceWithAdditionalYields` (#67121)

`affine::replaceForOpWithNewYields` and `replaceLoopWithNewYields` (for
"scf.for") are now interface methods and

[mlir][Interfaces] `LoopLikeOpInterface`: Add `replaceWithAdditionalYields` (#67121)

`affine::replaceForOpWithNewYields` and `replaceLoopWithNewYields` (for
"scf.for") are now interface methods and additional loop-carried
variables can now be added to "scf.for"/"affine.for" uniformly. (No more
`TypeSwitch` needed.)

Note: `scf.while` and other loops with loop-carried variables can
implement `replaceWithAdditionalYields`, but to keep this commit small,
that is not done in this commit.

show more ...

[mlir][Interfaces] `LoopLikeOpInterface`: Add helpers to get region iter_args and inits (#66925)

`AffineForOp::getInitOperands` is renamed to `getInits` to be consistent
with MLIR operand getter n

[mlir][Interfaces] `LoopLikeOpInterface`: Add helpers to get region iter_args and inits (#66925)

`AffineForOp::getInitOperands` is renamed to `getInits` to be consistent
with MLIR operand getter naming conventions. ("get" + operand name)

show more ...

fix unused variable warnings in conditionals

warning was updated in 92023b15099012a657da07ebf49dd7d94a260f84

[mlir][Affine][NFC] Wrap dialect in "affine" namespace

This cleanup aligns the affine dialect with all the other dialects.

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

[mlir][affine][analysis][NFC] Simplify FlatAffineConstraints API

* Remove `reset` function. Use copy assignment directly (instead of within `reset`).
* Fix potential `nullptr` dereference in `getFla

[mlir][affine][analysis][NFC] Simplify FlatAffineConstraints API

* Remove `reset` function. Use copy assignment directly (instead of within `reset`).
* Fix potential `nullptr` dereference in `getFlattenedAffineExprs`.
* Make constraint set optional in `checkMemrefAccessDependence`.

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

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] Add operations to BlockAndValueMapping and rename it to IRMapping

The patch adds operations to `BlockAndValueMapping` and renames it to `IRMapping`. When operations are cloned, old operations

[mlir] Add operations to BlockAndValueMapping and rename it to IRMapping

The patch adds operations to `BlockAndValueMapping` and renames it to `IRMapping`. When operations are cloned, old operations are mapped to the cloned operations. This allows mapping from an operation to a cloned operation. Example:

```
Operation *opWithRegion = ...
Operation *opInsideRegion = &opWithRegion->front().front();

IRMapping map
Operation *newOpWithRegion = opWithRegion->clone(map);
Operation *newOpInsideRegion = map.lookupOrNull(opInsideRegion);
```

Migration instructions:
All includes to `mlir/IR/BlockAndValueMapping.h` should be replaced with `mlir/IR/IRMapping.h`. All uses of `BlockAndValueMapping` need to be renamed to `IRMapping`.

Reviewed By: rriddle, mehdi_amini

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

show more ...

[MLIR] Fix affine analysis methods for affine.parallel

Drop unnecessary bailout in checkMemRefAccessDependence in the presence of
surrounding affine.parallel ops. When the affine.parallel op was add

[MLIR] Fix affine analysis methods for affine.parallel

Drop unnecessary bailout in checkMemRefAccessDependence in the presence of
surrounding affine.parallel ops. When the affine.parallel op was added, affine
analysis methods weren't extended to account for it. Fix this and allow memref
dependence check to work in the presence of affine.parallel ops in the mix.

Rename isForInductionVar -> isAffineForInductionVar, getLoopIVs ->
getAffineForIVs to avoid confusion since that's what they were.

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

show more ...

[MLIR] Generalize affine fusion to work on `Block` instead of `FuncOp`

The affine fusion pass can actually work on the top-level of a `Block`
and doesn't require to be called on a `FuncOp`. Remove t

[MLIR] Generalize affine fusion to work on `Block` instead of `FuncOp`

The affine fusion pass can actually work on the top-level of a `Block`
and doesn't require to be called on a `FuncOp`. Remove this restriction
and generalize the pass to work on any `Block`. This allows fusion to be
performed, for example, on multiple blocks of a FuncOp or any
region-holding op like an scf.while, scf.if or even at an inner depth of
an affine.for or affine.if op. This generalization has no effect on
existing functionality. No changes to the fusion logic or its
transformational power were needed.

Update fusion pass to be a generic operation pass (instead of FuncOp
pass) and remove references and assumptions on the parent being a
FuncOp.

Reviewed By: dcaballe

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

show more ...

NFC. Refactor/update some affine fusion pass code for readability

NFC. Refactor some affine fusion pass code for readability. Some of its
methods are too long. This is the first among some NFC chang

NFC. Refactor/update some affine fusion pass code for readability

NFC. Refactor some affine fusion pass code for readability. Some of its
methods are too long. This is the first among some NFC changes before new
features/related updates are posted. Add missing code comments at a couple of
places.

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

show more ...

[mlir] Don't use Optional::getValue (NFC)

[mlir] Don't use Optional::hasValue (NFC)

[mlir:NFC] Remove the forward declaration of FuncOp in the mlir namespace

FuncOp has been moved to the `func` namespace for a little over a month, the
using directive can be dropped now.

[mlir] Move the Builtin FuncOp to the Func dialect

This commit moves FuncOp out of the builtin dialect, and into the Func
dialect. This move has been planned in some capacity from the moment
we made

[mlir] Move the Builtin FuncOp to the Func dialect

This commit moves FuncOp out of the builtin dialect, and into the Func
dialect. This move has been planned in some capacity from the moment
we made FuncOp an operation (years ago). This commit handles the
functional aspects of the move, but various aspects are left untouched
to ease migration: func::FuncOp is re-exported into mlir to reduce
the actual API churn, the assembly format still accepts the unqualified
`func`. These temporary measures will remain for a little while to
simplify migration before being removed.

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

show more ...

[mlir:Transforms] Move out the remaining non-dialect independent transforms and utilities

This has been a major TODO for a very long time, and is necessary for establishing a proper
dialect-free dep

[mlir:Transforms] Move out the remaining non-dialect independent transforms and utilities

This has been a major TODO for a very long time, and is necessary for establishing a proper
dialect-free dependency layering for the Transforms library. Code was moved to effectively
two main locations:

* Affine/
There was quite a bit of affine dialect related code in Transforms/ do to historical reasons
(of a time way into MLIR's past). The following headers were moved to:
Transforms/LoopFusionUtils.h -> Dialect/Affine/LoopFusionUtils.h
Transforms/LoopUtils.h -> Dialect/Affine/LoopUtils.h
Transforms/Utils.h -> Dialect/Affine/Utils.h

The following transforms were also moved:
AffineLoopFusion, AffinePipelineDataTransfer, LoopCoalescing

* SCF/
Only one SCF pass was in Transforms/ (likely accidentally placed here): ParallelLoopCollapsing
The SCF specific utilities in LoopUtils have been moved to SCF/Utils.h

* Misc:
mlir::moveLoopInvariantCode was also moved to LoopLikeInterface.h given
that it is a simple utility defined in terms of LoopLikeOpInterface.

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

show more ...