[Transforms] Avoid repeated hash lookups (NFC) (#111470)

[mlir] Fix region simplification bug when later blocks use prior block argument values (#97960)

This fixes #94520 by ensuring that any if any block arguments are being
used outside of the original

[mlir] Fix region simplification bug when later blocks use prior block argument values (#97960)

This fixes #94520 by ensuring that any if any block arguments are being
used outside of the original block that the block is not considered a
candidate for merging.

More details: the root cause of the issue described in #94520 was that
`^bb2` and `^bb5` were being merged despite `%4` (an argument to `^bb2`)
was being used later in `^bb7`. When the block merge occurred, that
unintentionally changed the value of `%4` for all downstream code. This
change prevents that from happening.

show more ...

Fix late comment review for #102038 (#102869)

[mlir] Fix block merging (#102038)

With this PR I am trying to address:
https://github.com/llvm/llvm-project/issues/63230.

What changed:
- While merging identical blocks, don't add a block argu

[mlir] Fix block merging (#102038)

With this PR I am trying to address:
https://github.com/llvm/llvm-project/issues/63230.

What changed:
- While merging identical blocks, don't add a block argument if it is
"identical" to another block argument. I.e., if the two block arguments
refer to the same `Value`. The operations operands in the block will
point to the argument we already inserted. This needs to happen to all
the arguments we pass to the different successors of the parent block
- After merged the blocks, get rid of "unnecessary" arguments. I.e., if
all the predecessors pass the same block argument, there is no need to
pass it as an argument.
- This last simplification clashed with
`BufferDeallocationSimplification`. The reason, I think, is that the two
simplifications are clashing. I.e., `BufferDeallocationSimplification`
contains an analysis based on the block structure. If we simplify the
block structure (by merging and/or dropping block arguments) the
analysis is invalid . The solution I found is to do a more prudent
simplification when running that pass.

**Note-1**: I ran all the integration tests
(`-DMLIR_INCLUDE_INTEGRATION_TESTS=ON`) and they passed.
**Note-2**: I fixed a bug found by @Dinistro in #97697 . The issue was
that, when looking for redundant arguments, I was not considering that
the block might have already some arguments. So the index (in the block
args list) of the i-th `newArgument` is `i+numOfOldArguments`.

show more ...

Revert "[mlir] Fix block merging" (#100510)

Reverts llvm/llvm-project#97697

This commit introduced non-trivial bugs related to type consistency.

[mlir] Fix block merging (#97697)

With this PR I am trying to address:
https://github.com/llvm/llvm-project/issues/63230.

What changed:
- While merging identical blocks, don't add a block argum

[mlir] Fix block merging (#97697)

With this PR I am trying to address:
https://github.com/llvm/llvm-project/issues/63230.

What changed:
- While merging identical blocks, don't add a block argument if it is
"identical" to another block argument. I.e., if the two block arguments
refer to the same `Value`. The operations operands in the block will
point to the argument we already inserted. This needs to happen to all
the arguments we pass to the different successors of the parent block
- After merged the blocks, get rid of "unnecessary" arguments. I.e., if
all the predecessors pass the same block argument, there is no need to
pass it as an argument.
- This last simplification clashed with
`BufferDeallocationSimplification`. The reason, I think, is that the two
simplifications are clashing. I.e., `BufferDeallocationSimplification`
contains an analysis based on the block structure. If we simplify the
block structure (by merging and/or dropping block arguments) the
analysis is invalid . The solution I found is to do a more prudent
simplification when running that pass.

**Note**: this a rework of #96871 . I ran all the integration tests
(`-DMLIR_INCLUDE_INTEGRATION_TESTS=ON`) and they passed.

show more ...

Revert "Fix block merging" (#97460)

Reverts llvm/llvm-project#96871

Bots are broken.

Fix block merging (#96871)

With this PR I am trying to address:
https://github.com/llvm/llvm-project/issues/63230.

What changed:
- While merging identical blocks, don't add a block argument if

Fix block merging (#96871)

With this PR I am trying to address:
https://github.com/llvm/llvm-project/issues/63230.

What changed:
- While merging identical blocks, don't add a block argument if it is
"identical" to another block argument. I.e., if the two block arguments
refer to the same `Value`. The operations operands in the block will
point to the argument we already inserted
- After merged the blocks, get rid of "unnecessary" arguments. I.e., if
all the predecessors pass the same block argument, there is no need to
pass it as an argument.
- This last simplification clashed with
`BufferDeallocationSimplification`. The reason, I think, is that the two
simplifications are clashing. I.e., `BufferDeallocationSimplification`
contains an analysis based on the block structure. If we simplify the
block structure (by merging and/or dropping block arguments) the
analysis is invalid . The solution I found is to do a more prudent
simplification when running that pass.

**Note**: many tests are still not passing. But I wanted to submit the
code before changing all the tests (and probably adding a couple), so
that we can agree in principle on the algorithm/design.

show more ...

[mlir] Do not merge blocks during canonicalization by default (#95057)

This is a heavy process, and it can trigger a massive explosion in
adding block arguments. While potentially reducing the code

[mlir] Do not merge blocks during canonicalization by default (#95057)

This is a heavy process, and it can trigger a massive explosion in
adding block arguments. While potentially reducing the code size, the
resulting merged blocks with arguments are hiding some of the def-use
chain and can even hinder some further analyses/optimizations: a merge
block does not have it's own path-sensitive context, instead the context
is merged from all the predecessors.

Previous behavior can be restored by passing:

{test-convergence region-simplify=aggressive}

to the canonicalize pass.

show more ...

[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][Transforms] Correct block sorting utils name (NFC) (#92558)

This commit renames the name of the block sorting utility function to
`getBlocksSortedByDominance`. A topological order is not def

[MLIR][Transforms] Correct block sorting utils name (NFC) (#92558)

This commit renames the name of the block sorting utility function to
`getBlocksSortedByDominance`. A topological order is not defined on a
general directed graph, so the previous name did not make sense.

show more ...

[mlir][IR] Fix overload resolution on MSVC build (#84589)

#82629 added additional overloads to `replaceAllUsesWith` and
`replaceUsesWithIf`. This caused a build breakage with MSVC when called
with

[mlir][IR] Fix overload resolution on MSVC build (#84589)

#82629 added additional overloads to `replaceAllUsesWith` and
`replaceUsesWithIf`. This caused a build breakage with MSVC when called
with ops that can implicitly convert to `Value`.

```
external/llvm-project/mlir/lib/Dialect/SCF/Transforms/TileUsingInterface.cpp(881): error C2666: 'mlir::RewriterBase::replaceAllUsesWith': 2 overloads have similar conversions
external/llvm-project/mlir/include\mlir/IR/PatternMatch.h(631): note: could be 'void mlir::RewriterBase::replaceAllUsesWith(mlir::Operation *,mlir::ValueRange)'
external/llvm-project/mlir/include\mlir/IR/PatternMatch.h(626): note: or 'void mlir::RewriterBase::replaceAllUsesWith(mlir::ValueRange,mlir::ValueRange)'
external/llvm-project/mlir/include\mlir/IR/PatternMatch.h(616): note: or 'void mlir::RewriterBase::replaceAllUsesWith(mlir::Value,mlir::Value)'
external/llvm-project/mlir/lib/Dialect/SCF/Transforms/TileUsingInterface.cpp(882): note: while trying to match the argument list '(mlir::tensor::ExtractSliceOp, T)'
with
[
T=mlir::Value
]
```

Note: The LLVM build bots (Linux and Windows) did not break, this seems
to be an issue with `Tools\MSVC\14.29.30133\bin\HostX64\x64\cl.exe`.

This change renames the newly added overloads to `replaceAllOpUsesWith`
and `replaceOpUsesWithIf`.

show more ...

[mlir][IR] Make `replaceOp` / `replaceAllUsesWith` API consistent (#82629)

* `replaceOp` replaces all uses of the original op and erases the old
op.
* `replaceAllUsesWith` replaces all uses of the

[mlir][IR] Make `replaceOp` / `replaceAllUsesWith` API consistent (#82629)

* `replaceOp` replaces all uses of the original op and erases the old
op.
* `replaceAllUsesWith` replaces all uses of the original op/value/block.
It does not erase any IR.

This commit renames `replaceOpWithIf` to `replaceUsesWithIf`.
`replaceOpWithIf` was a misnomer because the function never erases the
original op. Similarly, `replaceOpWithinBlock` is renamed to
`replaceUsesWithinBlock`. (No "operation replaced" is sent because the
op is not erased.)

Also improve comments.

show more ...

Apply clang-tidy fixes for llvm-qualified-auto in RegionUtils.cpp (NFC)

Reland: [MLIR][Transforms] Fix Mem2Reg removal order to respect dominance (#68877)

This commit fixes a bug in the Mem2Reg operation erasure order.
Replacing the use-def based topological order with

Reland: [MLIR][Transforms] Fix Mem2Reg removal order to respect dominance (#68877)

This commit fixes a bug in the Mem2Reg operation erasure order.
Replacing the use-def based topological order with a dominance-based
weak order ensures that no operation is removed before all its uses have
been replaced. The order relation uses the topological order of blocks
and block internal ordering to determine a deterministic operation
order.

Additionally, the reliance on the `DenseMap` key order was eliminated by
switching to a `MapVector`, that gives a deterministic iteration order.

Example:

```
%ptr = alloca ...
...
%val0 = %load %ptr ... // LOAD0
store %val0 %ptr ...
%val1 = load %ptr ... // LOAD1
````

When promoting the slot backing %ptr, it can happen that the LOAD0 was
cleaned before LOAD1. This results in all uses of LOAD0 being replaced
by its reaching definition, before LOAD1's result is replaced by LOAD0's
result. The subsequent erasure of LOAD0 can thus not succeed, as it has
remaining usages.

show more ...

[mlir] Move casting calls from methods to function calls

The MLIR classes Type/Attribute/Operation/Op/Value support
cast/dyn_cast/isa/dyn_cast_or_null functionality through llvm's doCast
functionali

[mlir] Move casting calls from methods to function calls

The MLIR classes Type/Attribute/Operation/Op/Value support
cast/dyn_cast/isa/dyn_cast_or_null functionality through llvm's doCast
functionality in addition to defining methods with the same name.
This change begins the migration of uses of the method to the
corresponding function call as has been decided as more consistent.

Note that there still exist classes that only define methods directly,
such as AffineExpr, and this does not include work currently to support
a functional cast/isa call.

Caveats include:
- This clang-tidy script probably has more problems.
- This only touches C++ code, so nothing that is being generated.

Context:
- https://mlir.llvm.org/deprecation/ at "Use the free function variants
for dyn_cast/cast/isa/…"
- Original discussion at https://discourse.llvm.org/t/preferred-casting-style-going-forward/68443

Implementation:
This first patch was created with the following steps. The intention is
to only do automated changes at first, so I waste less time if it's
reverted, and so the first mass change is more clear as an example to
other teams that will need to follow similar steps.

Steps are described per line, as comments are removed by git:
0. Retrieve the change from the following to build clang-tidy with an
additional check:
https://github.com/llvm/llvm-project/compare/main...tpopp:llvm-project:tidy-cast-check
1. Build clang-tidy
2. Run clang-tidy over your entire codebase while disabling all checks
and enabling the one relevant one. Run on all header files also.
3. Delete .inc files that were also modified, so the next build rebuilds
them to a pure state.
4. Some changes have been deleted for the following reasons:
- Some files had a variable also named cast
- Some files had not included a header file that defines the cast
functions
- Some files are definitions of the classes that have the casting
methods, so the code still refers to the method instead of the
function without adding a prefix or removing the method declaration
at the same time.

```
ninja -C $BUILD_DIR clang-tidy

run-clang-tidy -clang-tidy-binary=$BUILD_DIR/bin/clang-tidy -checks='-*,misc-cast-functions'\
-header-filter=mlir/ mlir/* -fix

rm -rf $BUILD_DIR/tools/mlir/**/*.inc

git restore mlir/lib/IR mlir/lib/Dialect/DLTI/DLTI.cpp\
mlir/lib/Dialect/Complex/IR/ComplexDialect.cpp\
mlir/lib/**/IR/\
mlir/lib/Dialect/SparseTensor/Transforms/SparseVectorization.cpp\
mlir/lib/Dialect/Vector/Transforms/LowerVectorMultiReduction.cpp\
mlir/test/lib/Dialect/Test/TestTypes.cpp\
mlir/test/lib/Dialect/Transform/TestTransformDialectExtension.cpp\
mlir/test/lib/Dialect/Test/TestAttributes.cpp\
mlir/unittests/TableGen/EnumsGenTest.cpp\
mlir/test/python/lib/PythonTestCAPI.cpp\
mlir/include/mlir/IR/
```

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

show more ...

[mlir] Add a utility function to make a region isolated from above.

The utility functions takes a region and makes it isolated from above
by appending to the entry block arguments that represent the

[mlir] Add a utility function to make a region isolated from above.

The utility functions takes a region and makes it isolated from above
by appending to the entry block arguments that represent the captured
values and replacing all uses of the captured values within the region
with the newly added arguments. The captures values are returned.

The utility function also takes an optional callback that allows
cloning operations that define the captured values into the region
during the process of making it isolated from above. The cloned value
is no longer a captured values. The operands of the operation are then
captured values. This is done transitively allow cloning of a DAG of
operations into the region based on the callback.

Reviewed By: jpienaar

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

show more ...

[mlir][transforms] Simplify OperationEquivalence and CSE

Replace `mapOperands` and `mapResults` with two new callbacks. It was not clear what "mapping" meant and why the equivalence relationship was

[mlir][transforms] Simplify OperationEquivalence and CSE

Replace `mapOperands` and `mapResults` with two new callbacks. It was not clear what "mapping" meant and why the equivalence relationship was a property of the Operand/OpResult as opposed to just SSA values.

This revision changes the contract of the two callbacks: `checkEquivalent` compares two values for equivalence. `markEquivalent` informs the caller that the analysis determined that two values are equivalent. This simplifies the API because callers do not have to reason about operands/results, but just SSA values.

`OperationEquivalence::isEquivalentTo` can be used directly in CSE and there is no need for a custom op equivalence analysis.

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

show more ...

[mlir] Add support for operation-produced successor arguments in BranchOpInterface

This patch revamps the BranchOpInterface a bit and allows a proper implementation of what was previously `getMutabl

[mlir] Add support for operation-produced successor arguments in BranchOpInterface

This patch revamps the BranchOpInterface a bit and allows a proper implementation of what was previously `getMutableSuccessorOperands` for operations, which internally produce arguments to some of the block arguments. A motivating example for this would be an invoke op with a error handling path:
```
invoke %function(%0)
label ^success ^error(%1 : i32)

^error(%e: !error, %arg0 : i32):
...
```
The advantages of this are that any users of `BranchOpInterface` can still argue over remaining block argument operands (such as `%1` in the example above), as well as make use of the modifying capabilities to add more operands, erase an operand etc.

The way this patch implements that functionality is via a new class called `SuccessorOperands`, which is now returned by `getSuccessorOperands`. It basically contains an `unsigned` denoting how many operator produced operands exist, as well as a `MutableOperandRange`, which are the usual forwarded operands we are used to. The produced operands are assumed to the first few block arguments, followed by the forwarded operands afterwards. The role of `SuccessorOperands` is to provide various utility functions to modify and query the successor arguments from a `BranchOpInterface`.

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

show more ...

[mlir][NFC] Fix codestyle issues introduced in D121988

These were noticed in the post commit review of https://reviews.llvm.org/D121988

[mlir] Fix block merging with the result of a terminator

When the current implementation merges two blocks that have operands defined outside of their block respectively, it will merge these by addi

[mlir] Fix block merging with the result of a terminator

When the current implementation merges two blocks that have operands defined outside of their block respectively, it will merge these by adding a block argument in the resulting merged block and adding successor arguments to the predecessors.
There is a special case where this is incorrect however: If one of predecessors terminator produce the operand, inserting the block argument and updating the predecessor would lead to the terminator using its own result as successor argument.
IR Example:
```
%0 = "test.producing_br"()[^bb1, ^bb2] {
operand_segment_sizes = dense<0> : vector<2 x i32>
} : () -> i32

^bb1:
"test.br"(%0)[^bb4] : (i32) -> ()
```
where `^bb1` is then merged with another block would lead to:
```
%0 = "test.producing_br"(%0)[^bb1, ^bb2]
```

This patch fixes that issue during clustering by making sure that if the operand is from an outside block, that it is not produced by the terminator of a predecessor.

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

show more ...

[mlir] Make locations required when adding/creating block arguments

BlockArguments gained the ability to have locations attached a while ago, but they
have always been optional. This goes against th

[mlir] Make locations required when adding/creating block arguments

BlockArguments gained the ability to have locations attached a while ago, but they
have always been optional. This goes against the core tenant of MLIR where location
information is a requirement, so this commit updates the API to require locations.

Fixes #53279

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

show more ...

Apply clang-tidy fixes for performance-for-range-copy to MLIR (NFC)

Adjust "end namespace" comment in MLIR to match new agree'd coding style

See D115115 and this mailing list discussion:
https://lists.llvm.org/pipermail/llvm-dev/2021-December/154199.html

Differenti

Adjust "end namespace" comment in MLIR to match new agree'd coding style

See D115115 and this mailing list discussion:
https://lists.llvm.org/pipermail/llvm-dev/2021-December/154199.html

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

show more ...

[mlir] Expose region utils functions

As discussed in D109579, this patch exposes `runRegionDCE` and
`eraseUnreachableBlocks` so they can be used as separate utilities in
other passes.

Reviewed By:

[mlir] Expose region utils functions

As discussed in D109579, this patch exposes `runRegionDCE` and
`eraseUnreachableBlocks` so they can be used as separate utilities in
other passes.

Reviewed By: rriddle, mehdi_amini

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

show more ...