[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][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/LogicalResult: move into llvm (#97309)

This patch is part of a project to move the Presburger library into
LLVM.

Apply clang-tidy fixes for misc-include-cleaner in ConstantPropagationAnalysis.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][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 ...

[mlir] add missing pessimistic setting

This is updated on https://reviews.llvm.org/D127139, to mark op with region as pessimistic.

Reviewed By: jpienaar

Differential Revision: https://reviews.llvm

[mlir] add missing pessimistic setting

This is updated on https://reviews.llvm.org/D127139, to mark op with region as pessimistic.

Reviewed By: jpienaar

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

show more ...

[mlir] SCCP add missing pessimistic setting

When this was updated in D127139 the update in-place case was no longer
marked as pessimistic. Add back in.

Differential Revision: https://reviews.llvm.o

[mlir] SCCP add missing pessimistic setting

When this was updated in D127139 the update in-place case was no longer
marked as pessimistic. Add back in.

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

show more ...

[mlir] An implementation of sparse data-flow analysis

This patch introduces a (forward) sparse data-flow analysis implemented with the data-flow analysis framework. The analysis interacts with liven

[mlir] An implementation of sparse data-flow analysis

This patch introduces a (forward) sparse data-flow analysis implemented with the data-flow analysis framework. The analysis interacts with liveness information that can be provided by dead-code analysis to be conditional. This patch re-implements SCCP using dead-code analysis and (conditional) constant propagation analyses.

Depends on D127064

Reviewed By: rriddle, phisiart

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

show more ...

[mlir] Add Dead Code Analysis

This patch implements the analysis state classes needed for sparse data-flow analysis and implements a dead-code analysis using those states to determine liveness of bl

[mlir] Add Dead Code Analysis

This patch implements the analysis state classes needed for sparse data-flow analysis and implements a dead-code analysis using those states to determine liveness of blocks, control-flow edges, region predecessors, and function callsites.

Depends on D126751

Reviewed By: rriddle, phisiart

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

show more ...