[DataFlow] Migrate away from PointerUnion::{is,get} (NFC) (#119950)

Note that PointerUnion::{is,get} have been soft deprecated in
PointerUnion.h:

// FIXME: Replace the uses of is(), get() and

[DataFlow] Migrate away from PointerUnion::{is,get} (NFC) (#119950)

Note that PointerUnion::{is,get} have been soft deprecated in
PointerUnion.h:

// FIXME: Replace the uses of is(), get() and dyn_cast() with
// isa<T>, cast<T> and the llvm::dyn_cast<T>

I'm not touching PointerUnion::dyn_cast for now because it's a bit
complicated; we could blindly migrate it to dyn_cast_if_present, but
we should probably use dyn_cast when the operand is known to be
non-null.

show more ...

[mlir] IntegerRangeAnalysis: add support for vector type (#112292)

Treat integer range for vector type as union of ranges of individual
elements. With this semantics, most arith ops on vectors will

[mlir] IntegerRangeAnalysis: add support for vector type (#112292)

Treat integer range for vector type as union of ranges of individual
elements. With this semantics, most arith ops on vectors will work out
of the box, the only special handling needed for constants and vector
elements manipulation ops.

The end goal of these changes is to be able to optimize vectorized index
calculations.

show more ...

[mlir] [dataflow] unify semantics of program point (#110344)

The concept of a 'program point' in the original data flow framework is
ambiguous. It can refer to either an operation or a block itself

[mlir] [dataflow] unify semantics of program point (#110344)

The concept of a 'program point' in the original data flow framework is
ambiguous. It can refer to either an operation or a block itself. This
representation has different interpretations in forward and backward
data-flow analysis. In forward data-flow analysis, the program point of
an operation represents the state after the operation, while in backward
data flow analysis, it represents the state before the operation. When
using forward or backward data-flow analysis, it is crucial to carefully
handle this distinction to ensure correctness.

This patch refactors the definition of program point, unifying the
interpretation of program points in both forward and backward data-flow
analysis.

How to integrate this patch?

For dense forward data-flow analysis and other analysis (except dense
backward data-flow analysis), the program point corresponding to the
original operation can be obtained by `getProgramPointAfter(op)`, and
the program point corresponding to the original block can be obtained by
`getProgramPointBefore(block)`.

For dense backward data-flow analysis, the program point corresponding
to the original operation can be obtained by
`getProgramPointBefore(op)`, and the program point corresponding to the
original block can be obtained by `getProgramPointAfter(block)`.

NOTE: If you need to get the lattice of other data-flow analyses in
dense backward data-flow analysis, you should still use the dense
forward data-flow approach. For example, to get the Executable state of
a block in dense backward data-flow analysis and add the dependency of
the current operation, you should write:

``getOrCreateFor<Executable>(getProgramPointBefore(op),
getProgramPointBefore(block))``

In case above, we use getProgramPointBefore(op) because the analysis we
rely on is dense backward data-flow, and we use
getProgramPointBefore(block) because the lattice we query is the result
of a non-dense backward data flow computation.

related dsscussion:
https://discourse.llvm.org/t/rfc-unify-the-semantics-of-program-points/80671/8
corresponding PSA:
https://discourse.llvm.org/t/psa-program-point-semantics-change/81479

show more ...

[mlir] [dataflow] Refactoring the definition of program points in data flow analysis (#105656)

This patch distinguishes between program points and lattice anchors in
data flow analysis, where latti

[mlir] [dataflow] Refactoring the definition of program points in data flow analysis (#105656)

This patch distinguishes between program points and lattice anchors in
data flow analysis, where lattice anchors represent locations where a
lattice can be attached, while program points denote points in program
execution.

Related discussions:
https://discourse.llvm.org/t/rfc-unify-the-semantics-of-program-points/80671/8

show more ...

[mlir][dataflow] Propagate errors from `visitOperation` (#105448)

Base `DataFlowAnalysis::visit` returns `LogicalResult`, but wrappers's
Sparse/Dense/Forward/Backward `visitOperation` doesn't.

S

[mlir][dataflow] Propagate errors from `visitOperation` (#105448)

Base `DataFlowAnalysis::visit` returns `LogicalResult`, but wrappers's
Sparse/Dense/Forward/Backward `visitOperation` doesn't.

Sometimes it's needed to abort solver early if some unrecoverable
condition detected inside analysis.

Update `visitOperation` to return `LogicalResult` and propagate it to
`solver.initializeAndRun()`. Only `visitOperation` is updated for now,
it's possible to update other hooks like `visitNonControlFlowArguments`,
bit it's not needed immediately and let's keep this PR small.

Hijacked `UnderlyingValueAnalysis` test analysis to test it.

show more ...

[mlir][intrange] Fix inference of zero-trip loop bound (#96429)

When lower bound and exclusive upper bound of a loop are the same, and
the zero-trip loop is not canonicalized away before the analys

[mlir][intrange] Fix inference of zero-trip loop bound (#96429)

When lower bound and exclusive upper bound of a loop are the same, and
the zero-trip loop is not canonicalized away before the analysis, this
leads to a meaningless range for the induction variable being inferred.
This patch adds a check to make sure that the inferred range for the IV
is meaningful before updating the analysis state.

Fix https://github.com/llvm/llvm-project/issues/94423

show more ...

[mlir][dataflow] Fix for integer range analysis propagation bug (#93199)

Integer range analysis will not update the range of an operation when
any of the inferred input lattices are uninitialized.

[mlir][dataflow] Fix for integer range analysis propagation bug (#93199)

Integer range analysis will not update the range of an operation when
any of the inferred input lattices are uninitialized. In the current
behavior, all lattice values for non integer types are uninitialized.

For operations like arith.cmpf

```mlir
%3 = arith.cmpf ugt, %arg0, %arg1 : f32
```

that will result in the range of the output also being uninitialized,
and so on for any consumer of the arith.cmpf result. When control-flow
ops are involved, the lack of propagation results in incorrect ranges,
as the back edges for loop carried values are not properly joined with
the definitions from the body region.

For example, an scf.while loop whose body region produces a value that
is in a dataflow relationship with some floating-point values through an
arith.cmpf operation:

```mlir
func.func @test_bad_range(%arg0: f32, %arg1: f32) -> (index, index) {
%c4 = arith.constant 4 : index
%c1 = arith.constant 1 : index
%c0 = arith.constant 0 : index

%3 = arith.cmpf ugt, %arg0, %arg1 : f32

%1:2 = scf.while (%arg2 = %c0, %arg3 = %c0) : (index, index) -> (index, index) {
%2 = arith.cmpi ult, %arg2, %c4 : index
scf.condition(%2) %arg2, %arg3 : index, index
} do {
^bb0(%arg2: index, %arg3: index):
%4 = arith.select %3, %arg3, %arg3 : index
%5 = arith.addi %arg2, %c1 : index
scf.yield %5, %4 : index, index
}

return %1#0, %1#1 : index, index
}
```

The existing behavior results in the control condition %2 being
optimized to true, turning the while loop into an infinite loop. The
update to %arg2 through the body region is never factored into the range
calculation, as the ranges for the body ops all test as uninitialized.

This change causes all values initialized with setToEntryState to be set
to some initialized range, even if the values are not integers.

---------

Co-authored-by: Spenser Bauman <sabauma@fastmail>

show more ...

[MLIR][IntegerRangeAnalysis] Avoid crash reached when loop bound is uninitialized (#74832)

If the loop bound is not initialized, the analysis crashed, as it only checked for nullity. Also checking f

[MLIR][IntegerRangeAnalysis] Avoid crash reached when loop bound is uninitialized (#74832)

If the loop bound is not initialized, the analysis crashed, as it only checked for nullity. Also checking for initialization fixes the issue.

Signed-off-by: Victor Perez <victor.perez@codeplay.com>
Co-authored-by: Tsang, Whitney <whitney.tsang@intel.com>

show more ...

[IntegerRangeAnalysis] remove constraint on integer-typed results (#72007)

Apply clang-tidy fixes for misc-include-cleaner in IntegerRangeAnalysis.cpp (NFC)

[mlir] NFC: rename XDataFlowAnalysis to XForwardDataFlowAnalysis

This makes naming consisnt with XBackwardDataFlowAnalysis.

Reviewed By: Mogball, phisiart

Differential Revision: https://reviews.ll

[mlir] NFC: rename XDataFlowAnalysis to XForwardDataFlowAnalysis

This makes naming consisnt with XBackwardDataFlowAnalysis.

Reviewed By: Mogball, phisiart

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

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.

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 patch updates all remaining uses of the deprecated functionality in
mlir/. This was done with clang-tidy as described below and further
modifications to GPUBase.td and OpenMPOpsInterfaces.td.

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:
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.

```
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
```

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

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 check for value that might be null.

Because we are generating uninitialized value for no integer type and use `isUninitialized()` to judge if it is valid after https://reviews.llvm.org/rG

[mlir] Add check for value that might be null.

Because we are generating uninitialized value for no integer type and use `isUninitialized()` to judge if it is valid after https://reviews.llvm.org/rG93f081c896536112e1ca8133991d23cb1134793a, we should check the value before use `getValue` to get it.
Fixes https://github.com/llvm/llvm-project/issues/59984.

Reviewed By: Mogball

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

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] Avoid crash of UnsignedWhenEquivalent for no integer type.

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

Reviewed By: Mogball

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

[mlir] Avoid crash of UnsignedWhenEquivalent for no integer type.

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

Reviewed By: Mogball

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

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][dataflow] Remove Lattice::isUninitialized().

Currently, for sparse analyses, we always store a `Optional<ValueT>` in each lattice element. When it's `None`, we consider the lattice element as

[mlir][dataflow] Remove Lattice::isUninitialized().

Currently, for sparse analyses, we always store a `Optional<ValueT>` in each lattice element. When it's `None`, we consider the lattice element as `uninitialized`.

However:

* Not all lattices have an `uninitialized` state. For example, `Executable` and `PredecessorState` have default values so they are always initialized.

* In dense analyses, we don't have the concept of an `uninitialized` state.

Given these inconsistencies, this patch removes `Lattice::isUninitialized()`. Individual analysis states are now default-constructed. If the default state of an analysis can be considered as "uninitialized" then this analysis should implement the following logic:

* Special join rule: `join(uninitialized, any) == any`.

* Special bail out logic: if any of the input states is uninitialized, exit the transfer function early.

Depends On D132086

Reviewed By: Mogball

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

show more ...

[mlir][dataflow] Consolidate AbstractSparseLattice::markPessimisticFixpoint() and AbstractDenseLattice::reset() into Abstract{Sparse,Dense}DataFlowAnalysis::setToEntryState().

### Rationale

For a p

[mlir][dataflow] Consolidate AbstractSparseLattice::markPessimisticFixpoint() and AbstractDenseLattice::reset() into Abstract{Sparse,Dense}DataFlowAnalysis::setToEntryState().

### Rationale

For a program point where we cannot reason about incoming dataflow (e.g. an argument of an entry block), the framework needs to initialize the state.

Currently, `AbstractSparseDataFlowAnalysis` initializes such state to the "pessimistic fixpoint", and `AbstractDenseDataFlowAnalysis` calls the state's `reset()` function.

However, entry states aren't necessarily the pessimistic fixpoint. Example: in reaching definition, the pessimistic fixpoint is `{all definitions}`, but the entry state is `{}`.

This awkwardness might be why the dense analysis API currently uses `reset()` instead of `markPessimisticFixpoint()`.

This patch consolidates entry point initialization into a single function `setToEntryState()`.

### API Location

Note that `setToEntryState()` is defined in the analysis rather than the lattice, so that we allow different analyses to use the same lattice but different entry states.

### Removal of the concept of optimistic/known value

The concept of optimistic/known value is too specific to SCCP.

Furthermore, the known value is not really used: In the current SCCP implementation, the known value (pessimistic fixpoint) is always `Attribute{}` (non-constant). This means there's no point storing a `knownValue` in each state.

If we do need to re-introduce optimistic/known value, we should put it in the SCCP analysis, not the sparse analysis API.

### Terminology

Please let me know if "entry state" is a good terminology.

I chose "entry" from Wikipedia (https://en.wikipedia.org/wiki/Data-flow_analysis#Basic_principles).

Another term I can think of is "boundary" (https://suif.stanford.edu/~courses/cs243/lectures/L3-DFA2-revised.pdf) which might be better since it also makes sense for backward analysis.

Reviewed By: Mogball

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

show more ...

Use llvm::is_contained (NFC)

[mlir] Use has_value instead of hasValue (NFC)

[mlir] Swap integer range inference to the new framework

Integer range inference has been swapped to the new framework. The integer value range lattices automatically updates the corresponding const

[mlir] Swap integer range inference to the new framework

Integer range inference has been swapped to the new framework. The integer value range lattices automatically updates the corresponding constant value on update.

Depends on D127173

Reviewed By: krzysz00, rriddle

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

show more ...