[mlir] Delete ForwardDataFlowAnalysis

With SCCP and integer range analysis ported to the new framework, this old framework is redundant. Delete it.

Depends on D128866

Reviewed By: rriddle

Differe

[mlir] Delete ForwardDataFlowAnalysis

With SCCP and integer range analysis ported to the new framework, this old framework is redundant. Delete it.

Depends on D128866

Reviewed By: rriddle

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

show more ...

[mlir] Support getSuccessorInputs from parent op

Ops that implement `RegionBranchOpInterface` are allowed to indicate that they can branch back to themselves in `getSuccessorRegions`, but there is n

[mlir] Support getSuccessorInputs from parent op

Ops that implement `RegionBranchOpInterface` are allowed to indicate that they can branch back to themselves in `getSuccessorRegions`, but there is no API that allows them to specify the forwarded operands. This patch enables that by changing `getSuccessorEntryOperands` to accept `None`.

Fixes #54928

Reviewed By: rriddle

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

show more ...

[mlir] Fix handling of some region branch terminator successors

When `RegionBranchOpInterface::getSuccessorRegions` is called for anything other than the parent op, it expects the operands of the te

[mlir] Fix handling of some region branch terminator successors

When `RegionBranchOpInterface::getSuccessorRegions` is called for anything other than the parent op, it expects the operands of the terminator of the source region to be passed, not the operands of the parent op. This was not always respected.

This fixes a bug in integer range inference and ForwardDataFlowSolver and changes `scf.while` to allow narrowing of successors using constant inputs.

Fixes #55873

Reviewed By: mehdi_amini, krzysz00

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

show more ...

Re-land "[mlir] Add integer range inference analysis""

This reverts commit 4e5ce2056e3e85f109a074e80bdd23a10ca2bed9.

This relands commit 1350c9887dca5ba80af8e3c1e61b29d6696eb240.

Reinstates the ra

Re-land "[mlir] Add integer range inference analysis""

This reverts commit 4e5ce2056e3e85f109a074e80bdd23a10ca2bed9.

This relands commit 1350c9887dca5ba80af8e3c1e61b29d6696eb240.

Reinstates the range analysis with the build issue fixed.

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

show more ...

Revert "[mlir] Add integer range inference analysis"

This reverts commit 1350c9887dca5ba80af8e3c1e61b29d6696eb240.

Shared library build is broken with undefined references.

[mlir] Add integer range inference analysis

This commit defines a dataflow analysis for integer ranges, which
uses a newly-added InferIntRangeInterface to compute the lower and
upper bounds on the r

[mlir] Add integer range inference analysis

This commit defines a dataflow analysis for integer ranges, which
uses a newly-added InferIntRangeInterface to compute the lower and
upper bounds on the results of an operation from the bounds on the
arguments. The range inference is a flow-insensitive dataflow analysis
that can be used to simplify code, such as by statically identifying
bounds checks that cannot fail in order to eliminate them.

The InferIntRangeInterface has one method, inferResultRanges(), which
takes a vector of inferred ranges for each argument to an op
implementing the interface and a callback allowing the implementation
to define the ranges for each result. These ranges are stored as
ConstantIntRanges, which hold the lower and upper bounds for a
value. Bounds are tracked separately for the signed and unsigned
interpretations of a value, which ensures that the impact of
arithmetic overflows is correctly tracked during the analysis.

The commit also adds a -test-int-range-inference pass to test the
analysis until it is integrated into SCCP or otherwise exposed.

Finally, this commit fixes some bugs relating to the handling of
region iteration arguments and terminators in the data flow analysis
framework.

Depends on D124020

Depends on D124021

Reviewed By: rriddle, Mogball

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

show more ...

[mlir] Allow data flow analysis of non-control flow branch arguments

This commit adds the visitNonControlFlowArguments method to
DataFlowAnalysis, allowing analyses to provide lattice values for the

[mlir] Allow data flow analysis of non-control flow branch arguments

This commit adds the visitNonControlFlowArguments method to
DataFlowAnalysis, allowing analyses to provide lattice values for the
arguments to a RegionSuccessor block that aren't directly tied to an
op's inputs. For example, integer range interface can use this method
to infer bounds for the step values in loops.

This method has a default implementation that keeps the old behavior
of assigning a pessimistic fixedpoint state to all such arguments.

Reviewed By: Mogball, rriddle

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

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][DataFlowAnalysis] Use a queue to maintain the worklist

Since the analysis is described to be suitable for a forward
data-flow analysis, maintaining the worklist as a queue mimics
RPO ordering

[MLIR][DataFlowAnalysis] Use a queue to maintain the worklist

Since the analysis is described to be suitable for a forward
data-flow analysis, maintaining the worklist as a queue mimics
RPO ordering of block visits, thus reaching the fixpoint earlier.

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

show more ...

Fix more clang-tidy cleanups in 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:DataFlowAnalysis] Reprocess the arguments of already executable edges

This fixes a bug where we discover new information about the arguments of an
already executable edge, but don't visit the

[mlir:DataFlowAnalysis] Reprocess the arguments of already executable edges

This fixes a bug where we discover new information about the arguments of an
already executable edge, but don't visit the arguments. We only visit the arguments, and not the block itself, so this commit shouldn't really affect performance at all.

Fixes PR#51871

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

show more ...

[mlir] Added new RegionBranchTerminatorOpInterface and adapted uses of hasTrait<ReturnLike>.

This CL adds a new RegionBranchTerminatorOpInterface to query information about operands that can be
pass

[mlir] Added new RegionBranchTerminatorOpInterface and adapted uses of hasTrait<ReturnLike>.

This CL adds a new RegionBranchTerminatorOpInterface to query information about operands that can be
passed to successor regions. Similar to the BranchOpInterface, it allows to freely define the
involved operands. However, in contrast to the BranchOpInterface, it expects an additional region
number to distinguish between various use cases which might require different operands passed to
different regions.

Moreover, we added new utility functions (namely getMutableRegionBranchSuccessorOperands and
getRegionBranchSuccessorOperands) to query (mutable) operand ranges for operations equiped with the
ReturnLike trait and/or implementing the newly added interface. This simplifies reasoning about
terminators in the scope of the nested regions.

We also adjusted the SCF.ConditionOp to benefit from the newly added capabilities.

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

show more ...

[mlir] Fix region successor bug in forward dataflow analysis

We weren't properly visiting region successors when the terminator wasn't return like, which could create incorrect results in the analys

[mlir] Fix region successor bug in forward dataflow analysis

We weren't properly visiting region successors when the terminator wasn't return like, which could create incorrect results in the analysis. This revision ensures that we properly visit region successors, to avoid optimistically assuming a value is constant when it isn't.

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

show more ...

[mlir] Fix bug in ForwardDataFlowAnalysis solver

Explicitly check for uninitialized to prevent crashes in edge cases where the derived analysis creates a lattice element for a value that hasn't been

[mlir] Fix bug in ForwardDataFlowAnalysis solver

Explicitly check for uninitialized to prevent crashes in edge cases where the derived analysis creates a lattice element for a value that hasn't been visited yet.

show more ...

[mlir] Refactor the forward dataflow propagation in SCCP into a generic framework

This revision takes the forward value propagation engine in SCCP and refactors it into a more generalized forward da

[mlir] Refactor the forward dataflow propagation in SCCP into a generic framework

This revision takes the forward value propagation engine in SCCP and refactors it into a more generalized forward dataflow analysis framework. This framework allows for propagating information about values across the various control flow constructs in MLIR, and removes the need for users to reinvent the traversal (often not as completely). There are a few aspects of the traversal, that were conservative for SCCP, that should be relaxed to support the needs of different value analyses. To keep this revision simple, these conservative behaviors will be left in (Note that this won't produce an incorrect result, but may produce more conservative results than necessary in certain edge cases. e.g. region entry arguments for non-region branch interface operations). The framework also only focuses on computing lattices for values, given the SCCP origins, but this is something to relax as needed in the future.

Given that this logic is already in SCCP, a majority of this commit is NFC. The more interesting parts are the interface glue that clients interact with.

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

show more ...