[mlir][bufferization] Add `BufferOriginAnalysis` (#86461)

This commit adds the `BufferOriginAnalysis`, which can be queried to
check if two buffer SSA values originate from the same allocation. Thi

[mlir][bufferization] Add `BufferOriginAnalysis` (#86461)

This commit adds the `BufferOriginAnalysis`, which can be queried to
check if two buffer SSA values originate from the same allocation. This
new analysis is used in the buffer deallocation pass to fold away or
simplify `bufferization.dealloc` ops more aggressively.

The `BufferOriginAnalysis` is based on the `BufferViewFlowAnalysis`,
which collects buffer SSA value "same buffer" dependencies. E.g., given
IR such as:
```
%0 = memref.alloc()
%1 = memref.subview %0
%2 = memref.subview %1
```
The `BufferViewFlowAnalysis` will report the following "reverse"
dependencies (`resolveReverse`) for `%2`: {`%2`, `%1`, `%0`}. I.e., all
buffer SSA values in the reverse use-def chain that originate from the
same allocation as `%2`. The `BufferOriginAnalysis` is built on top of
that. It handles only simple cases at the moment and may conservatively
return "unknown" around certain IR with branches, memref globals and
function arguments.

This analysis enables additional simplifications during
`-buffer-deallocation-simplification`. In particular, "regular" scf.for
loop nests, that yield buffers (or reallocations thereof) in the same
order as they appear in the iter_args, are now handled much more
efficiently. Such IR patterns are generated by the sparse compiler.

show more ...

[mlir][bufferization] Add `BufferViewFlowOpInterface` (#78718)

This commit adds the `BufferViewFlowOpInterface` to the bufferization
dialect. This interface can be implemented by ops that operate o

[mlir][bufferization] Add `BufferViewFlowOpInterface` (#78718)

This commit adds the `BufferViewFlowOpInterface` to the bufferization
dialect. This interface can be implemented by ops that operate on
buffers to indicate that a buffer op result and/or region entry block
argument may be the same buffer as a buffer operand (or a view thereof).
This interface is queried by the `BufferViewFlowAnalysis`.

The new interface has two interface methods:
* `populateDependencies`: Implementations use the provided callback to
declare dependencies between operands and op results/region entry block
arguments. E.g., for `%r = arith.select %c, %m1, %m2 : memref<5xf32>`,
the interface implementation should declare two dependencies: %m1 -> %r
and %m2 -> %r.
* `mayBeTerminalBuffer`: An SSA value is a terminal buffer if the buffer
view flow analysis stops at the specified value. E.g., because the value
is a newly allocated buffer or because no further information is
available about the origin of the buffer.

Ops that implement the `RegionBranchOpInterface` or `BranchOpInterface`
do not have to implement the `BufferViewFlowOpInterface`. The buffer
dependencies can be inferred from those two interfaces.

This commit makes the `BufferViewFlowAnalysis` more accurate. For
unknown ops, it conservatively used to declare all combinations of
operands and op results/region entry block arguments as dependencies
(false positives). This is no longer the case. While the analysis is
still a "maybe" analysis with false positives (e.g., when analyzing ops
such as `arith.select` or `scf.if` where the taken branch is not known
at compile time), results and region entry block arguments of unknown
ops are now marked as terminal buffers.

This commit addresses a TODO in `BufferViewFlowAnalysis.cpp`:
```
// TODO: We should have an op interface instead of a hard-coded list of
// interfaces/ops.
```
It is no longer needed to hard-code ops.

show more ...

[MLIR][Bufferizer][NFC] Simplify some codes. (#77254)

NFC. clean up.

Reland "[mlir] Use a type for representing branch points in `RegionBranchOpInterface`"

This reverts commit b26bb30b467b996c9786e3bd426c07684d84d406.

Revert "[mlir] Use a type for representing branch points in `RegionBranchOpInterface`"

This reverts commit 024f562da67180b7be1663048c960b26c2cc16f8.

Forgot to update flang

[mlir] Use a type for representing branch points in `RegionBranchOpInterface`

The current implementation is not very ergonomic or descriptive: It uses `std::optional<unsigned>` where `std::nullopt`

[mlir] Use a type for representing branch points in `RegionBranchOpInterface`

The current implementation is not very ergonomic or descriptive: It uses `std::optional<unsigned>` where `std::nullopt` represents the parent op and `unsigned` is the region number.
This doesn't give us any useful methods specific to region control flow and makes the code fragile to changes due to now taking the region number into account.

This patch introduces a new type called `RegionBranchPoint`, replacing all uses of `std::optional<unsigned>` in the interface. It can be implicitly constructed from a region or a `RegionSuccessor`, can be compared with a region to check whether the branch point is branching from the parent, adds `isParent` to check whether we are coming from a parent op and adds `RegionSuccessor::parent` as a descriptive way to indicate branching from the parent.

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

show more ...

[mlir] Revamp `RegionBranchOpInterface` successor mechanism

The `RegionBranchOpInterface` had a few fundamental issues caused by the API design of `getSuccessorRegions`.

It always required passing

[mlir] Revamp `RegionBranchOpInterface` successor mechanism

The `RegionBranchOpInterface` had a few fundamental issues caused by the API design of `getSuccessorRegions`.

It always required passing values for the `operands` parameter. This is problematic as the operands parameter actually changes meaning depending on which predecessor `index` is referring to. If coming from a region, you'd have to find a `RegionBranchTerminatorOpInterface` in that region, get its operand count, and then create a `SmallVector` of that size.
This is not only inconvenient, but also error-prone, which has lead to a bug in the implementation of a previously existing `getSuccessorRegions` overload.

Additionally, this made the method dual-use, trying to serve two different use-cases: 1) Trying to determine possible control flow edges between regions and 2) Trying to determine the region being branched to based on constant operands.

This patch fixes these issues by changing the interface methods and adding new ones:
* The `operands` argument of `getSuccessorRegions` has been removed. The method is now only responsible for returning possible control flow edges between regions.
* An optional `getEntrySuccessorRegions` method has been added. This is used to determine which regions are branched to from the parent op based on constant operands of the parent op. By default, it calls `getSuccessorRegions`. This is analogous to `getSuccessorForOperands` from `BranchOpInterface`.
* Add `getSuccessorRegions` to `RegionBranchTerminatorOpInterface`. This is used to get the possible successors of the terminator based on constant operands. By default, it calls the containing `RegionBranchOpInterface`s `getSuccessorRegions` method.
* `getSuccessorEntryOperands` was renamed to `getEntrySuccessorOperands` for consistency.

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

show more ...

[mlir][NFC] Make `ReturnLike` trait imply `RegionBranchTerminatorOpInterface`

This implication was already done de-facto and there were plenty of users and wrapper functions specifically used to han

[mlir][NFC] Make `ReturnLike` trait imply `RegionBranchTerminatorOpInterface`

This implication was already done de-facto and there were plenty of users and wrapper functions specifically used to handle the "return-like or RegionBranchTerminatorOpInterface" case. These simply existed due to up until recently missing features in ODS.

With the new capabilities of traits, we can make `ReturnLike` imply `RegionBranchTerminatorOpInterface` and auto generate proper definitions for its methods.
Various occurrences and wrapper methods used for `isa<RegionBranchTerminatorOpInterface>() || hasTrait<ReturnLike>()` have all been removed.

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

show more ...

[mlir][bufferization] Add rename function to BufferViewFlowAnalysis

This new function to replace a Value with another Value saves us from re-running
the entire alias analysis when an operation has t

[mlir][bufferization] Add rename function to BufferViewFlowAnalysis

This new function to replace a Value with another Value saves us from re-running
the entire alias analysis when an operation has to be re-build because
additional result values have to be added (e.g., when adding more iter_args to
an scf.for).

Reviewed By: springerm

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

show more ...

[mlir] allow region branch spec from parent op to itself

RegionBranchOpInterface did not allow the operation with regions to
specify itself as successors. Therefore, this implied that the control
is

[mlir] allow region branch spec from parent op to itself

RegionBranchOpInterface did not allow the operation with regions to
specify itself as successors. Therefore, this implied that the control
is always transferred to a region before being transferred back to the
parent op. Since the region can only transfer the control back to the
parent op from a terminator, this transitively implied that the first
block of any region with a RegionBranchOpInterface is always executed
until the terminator can transfer the control flow back. This is
trivially false for any conditional-like operation that may or may not
execute the region, as well as for loop-like operations that may not
execute the body.

Remove the restriction from the interface description and update the
only transform that relied on it.

See
https://discourse.llvm.org/t/rfc-region-control-flow-interfaces-should-encode-region-not-executed-correctly/72103.

Depends On: https://reviews.llvm.org/D155757

Reviewed By: Mogball, springerm

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

show more ...

[mlir][bufferization] Fix unknown ops in BufferViewFlowAnalysis

If an op is unknown to the analysis, it must be treated conservatively: assume that every operand aliases with every result.

Differen

[mlir][bufferization] Fix unknown ops in BufferViewFlowAnalysis

If an op is unknown to the analysis, it must be treated conservatively: assume that every operand aliases with every result.

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

show more ...

[MLIR] Fix non-deterministic generation from buffer-deallocation pass

The buffer-deallocation pass generates a different output on each run
due to an unstable iteration order.

Fixes: https://github

[MLIR] Fix non-deterministic generation from buffer-deallocation pass

The buffer-deallocation pass generates a different output on each run
due to an unstable iteration order.

Fixes: https://github.com/llvm/llvm-project/issues/59118

Reviewed By: mehdi_amini

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

show more ...

mlir/tblgen: use std::optional in generation

This is part of an effort to migrate from llvm::Optional to
std::optional. This patch changes the way mlir-tblgen generates .inc
files, and modifies test

mlir/tblgen: use std::optional in generation

This is part of an effort to migrate from llvm::Optional to
std::optional. This patch changes the way mlir-tblgen generates .inc
files, and modifies tests and documentation appropriately. It is a "no
compromises" patch, and doesn't leave the user with an unpleasant mix of
llvm::Optional and std::optional.

A non-trivial change has been made to ControlFlowInterfaces to split one
constructor into two, relating to a build failure on Windows.

See also: https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

Signed-off-by: Ramkumar Ramachandra <r@artagnon.com>

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

show more ...

[mlir] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of ma

[mlir] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
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][arith] Change dialect name from Arithmetic to Arith

Suggested by @lattner in https://discourse.llvm.org/t/rfc-define-precise-arith-semantics/65507/22.

Tested with:
`ninja check-mlir check-ml

[mlir][arith] Change dialect name from Arithmetic to Arith

Suggested by @lattner in https://discourse.llvm.org/t/rfc-define-precise-arith-semantics/65507/22.

Tested with:
`ninja check-mlir check-mlir-integration check-mlir-mlir-spirv-cpu-runner check-mlir-mlir-vulkan-runner check-mlir-examples`

and `bazel build --config=generic_clang @llvm-project//mlir:all`.

Reviewed By: lattner, Mogball, rriddle, jpienaar, mehdi_amini

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

show more ...

Move BufferViewFlowAnalysis to the Bufferization dialect.

It's only used from there, and this lets us remove the dependency from Analysis
to the Arith dialect.

Reviewed By: springerm

Differential

Move BufferViewFlowAnalysis to the Bufferization dialect.

It's only used from there, and this lets us remove the dependency from Analysis
to the Arith dialect.

Reviewed By: springerm

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

show more ...