Possible fix for #203862
Unsigned value is assumed but signed is possible. So added a check if it
is unsigned before accessing as unsigned, otherwise access as integer
and typecast to unsigned.
Relands #197728, which was reverted in #198048 because it broke
shared-library builds.
## Summary of build fix:
`IntegerDivisibilityAnalysis.cpp` calls
`mlir::getConstantIntValue(OpFoldResult)`, which is defined in
`mlir/lib/Dialect/Utils/StaticValueUtils.cpp`. Without this link
dependency, shared-library
builds of `libMLIRAnalysis.so` fail with undefined references.
This was the root cause of
https://github.com/llvm/llvm-project/pull/198048.
This patch is a port from
https://github.com/iree-org/iree/blob/main/compiler/src/iree/compiler/Dialect/Util/Analysis/IntegerDivisibilityAnalysis.cpp
to upstream
It introduces a dataflow analysis that tracks integer divisibility
(divisor + remainder lattice) for SSA values, plus an op interface
`InferIntDivisibilityOpInterface` for ops to participate.
It adds:
* `IntegerDivisibilityAnalysis` produces a `Divisibility` lattice
`{divisor, remainder}`
* `InferIntDivisibilityOpInterface` interface
* External-model implementations for `arith` and `affine` ops
* `test-int-divisibility` test pass + lit tests
Example:
Here is the usual approach to laod element `i` from `i4` buffer emulated
in `i8` buffer:
```mlir
%byte_idx = arith.divui %i, %c2 : index
%bit_off = arith.remui %i, %c2 : index
%byte = memref.load %buf[%byte_idx] : memref<?xi8>
%shifted = arith.shrui %byte, %bit_off_as_i8
%nibble = arith.andi %shifted, %c0xF : i8
```
If `i` comes from `affine.apply (d0) -> (d0 * 8 + 0)` over loop IV,
analysis derives `divisor=8, remainder=0` for `%i`. Then we can emit
more concise code by avoiding the shift. There are more scenarios that
could benefit from this analysis.
Adds an optional filtering control function to the dataflow solver's
initializeAndRun callback, which controls which analyses will be
initialized when running the solver. This makes it possible to reuse
existing dataflow solver instances that have already run to a fixpoint
without re-initializing all of the analyses that have already converged.
A new analysis and test pass is also added, which illustrates how the
filtering can be useful to run a staged analysis, which would not have
been possible before. The example analysis, called `BarAnalysis`,
depends on the converged state of the `FooAnalysis`. The Bar analysis is
a forward analysis that tracks, for each program point, whether any of
the preceding program points hold a `foo_state` that is divisible by 4.
In the example test, the control flow graph looks like the following:
```
entry-block
/ \
bb0 bb2
\ /
bb1
```
The `foo_state` of `bb1` depends on the `foo_state` of `bb0` and `bb2`.
If the solver goes through `bb0->bb1` before `bb2->bb1`, then there is
an intermediate stage in the analyses where the state of `bb1` could be
divisible by 4, even though the final state of `bb1` will not be
divisible by 4 in the converged state. If the `BarAnalysis` runs on
`bb1` in this intermediate state, then it will get stuck with the
"divisible by 4" state, and the analysis will not yield the desired
results.
This PR ensures that the `BarAnalysis` will see the correct state
`foo_state`, because the `FooAnalysis` will fully run to a fixpoint
before the `BarAnalysis` is loaded, initialized, and run.
The Foo and Bar analyses are just trivial examples, but this pattern is
useful when there are analyses that can be made more effective by using
complementary analyses like integer range/divisibility analyses.
**Note for integration:**
DataFlowSolver::load now stores the concrete analysis TypeID, exposed
via DataFlowAnalysis::getTypeID(). Downstream DataFlowAnalysis
subclasses defined in anonymous namespaces must add
MLIR_DEFINE_EXPLICIT_INTERNAL_INLINE_TYPE_ID(ClassName) to their class
body.
Assisted-by: Codex (gpt-5.4)
TestLastModifiedPass asserted that a dense lattice state is always
present after running the data flow solver. However, in interprocedural
analysis mode (the default), private functions that are never called
from any callee in the module are not analyzed, so no lattice state is
computed for their program points.
Replace the assertion with a null check that prints "<not computed>"
when the lattice state is absent. This matches the expected behavior:
unreachable code in interprocedural mode simply has no computed analysis
result.
Add a regression test for the case where a tagged op is inside an
unreachable private function.
Fixes#128333
Assisted-by: Claude Code
TestSparseBackwardDataFlowAnalysis::TestWrittenToPass asserted that the
WrittenTo sparse lattice was always computed for tagged operands and
results. This assertion fires when analyzing a private function that is
never called from anywhere: in interprocedural mode the backward data
flow solver does not visit such dead code, leaving the lattice state
uninitialized.
Replace the assertions with null checks that print "<not computed>"
instead, matching the approach used in TestDenseForwardDataFlowAnalysis
for the analogous dense forward case.
Fixes#128339
Assisted-by: Claude Code
This patch allows creating a hierarchy of `SideEffects::Resource`s by adding
a virtual `getParent()` method, so that effects on *disjoint* resources
can be proven non-conflicting. It also adds virtual `isAddressable()` method
that represents a property of a resource to be addressable via a pointer
value. The non-addressable resources may not be affected via any pointer.
This is unblocking CSE, LICM and alias analysis without per-pass
special-casing.
RFC:
https://discourse.llvm.org/t/rfc-mlir-memory-region-hierarchy-for-mlir-side-effects/89811
`mlir::matchReduction()` accessed `terminatorOp->getOperand(redPos)`
without checking that `redPos` is within the terminator's operand count.
This caused an assertion failure when the region's block-argument count
exceeds the terminator's yield count, e.g. for `linalg.pooling_nhwc_sum`
whose kernel region has three block args but yields only one value.
Add a bounds check before the operand access so the function returns
nullptr gracefully instead of crashing.
Fixes#131437
- Loops with 0 iterations always branch back to the parent.
- Loops with 1 iteration always branch into the loop, then immediately
back to the parent.
This change improves the quality of data flow analyses (e.g., dead code
analysis). It is also in preparation of adding a generic region inlining
canonicalization pattern for `RegionBranchOpInterface` ops (#176641).
---------
Co-authored-by: Jakub Kuderski <jakub@nod-labs.com>
`scf.forall` does not completely implement the
`RegionBranchOpInterface`: `scf.forall.in_parallel` does not implement
the `RegionBranchTerminatorOpInterface`.
Incomplete interface implementation is a problem for transformations
that try to understand the control flow by querying the
`RegionBranchOpInterface`.
Detailed explanation of what is wrong with the current implementation.
- There is exactly one region branch point: "parent". `in_parallel` is
not a region branch point because it does not implement the
`RegionBranchTerminatorOpInterface`. (Clarified in #174978.)
- `ForallOp::getSuccessorRegions(parent)` returns one region successors:
the region of the `scf.forall` op.
- Since there is no region branch point in the region, there is no way
to leave the region. This means: once you enter the region, you are
stuck in it indefinitely. (It is unspecified what happens once you are
in the region, but we can be sure that you cannot leave it.)
This commit adds the `RegionBranchTerminatorOpInterface` (via
`ReturnLike`) to `scf.forall.in_parallel` to indicate the after leaving
the region, the control flow returns to the parent. (Note: Only block
terminators in directly nested regions can be region branch terminators,
so `in_parallel` is the only possible op. I.e., `parallel_insert_slice`
cannot be a region branch terminator.)
This commit also removes all successor operands / inputs from the
implementation. The number of successor operands and successor inputs
must match, but `scf.forall.in_parallel` has no operands. Therefore, the
region must also have 0 successor inputs. Therefore, the `scf.forall` op
must also have 0 successor operands.
This commit also adds a missing control flow edge from "parent" to
"parent": in case of 0 threads, the region is not entered.
Depends on #174978.
Note: This is a "stacked PR" and depends on #174356. The intention is to
merge that PR first.
`wouldOpBeTriviallyDead` is closer to the intended purpose here, and
aligns the code with how the greedy pattern rewriter identifies dead
operations.
Importantly, it allows us to identify unused read-only memory
operations, which would previously have failed the `isMemoryEffectFree`
check.
Add visitNonControlFlowArgumentst API to SparseBackwardDataFlowAnalysis,
current SparseBackwardDataflowAnalysis cannot access all SSA values,
such as, the loop's IV. Now we can use visitNonControlFlowArgumentst to
visit it. Apply it in LivenessAnalysis/RemoveDeadValues, solved the
issue of IV liveness in the loop.
https://discourse.llvm.org/t/rfc-add-visitbranchregionargument-interface-to-sparsedataflowanalysis/89061
This relands commit aa8499863a. That
commit was originally reverted because it caused failures in shared lib
builds due to missing link dependencies. This patch relands the commit
with the missing libs added.
Signed-off-by: Fabian Mora <fabian.mora-cordero@amd.com>
Continuation of https://github.com/llvm/llvm-project/pull/156913, I'm
planning to use it to infer LLVM alias scope attributes.
* Introduce `DistinctObjectsTrait` so analysis won't need to depend on
memref dialect directly.
* Check the trairin `LocalAliasAnalysis::aliasImpl`.
This patch is forcing all values to be initialized by the
LivenessAnalysis, even in dead blocks. The dataflow framework will skip
visiting values when its already knows that a block is dynamically
unreachable, so this requires specific handling.
Downstream code could consider that the absence of liveness is the same
a "dead".
However as the code is mutated, new value can be introduced, and a
transformation like "RemoveDeadValue" must conservatively consider that
the absence of liveness information meant that we weren't sure if a
value was dead (it could be a newly introduced value.
Fixes#153906
This patch fixes the following bugs:
- In SparseBackwardAnalysis, the setToExitState function should
propagate changes if it modifies the lattice. Previously, this issue was
masked because multi-block scenarios were not tested, and the traversal
order of backward data flow analysis starts from the end of the program.
- The method in liveness analysis for determining whether the
non-forwarded operand in branch/region branch operations is live is
incorrect, which may cause originally live variables to be marked as not
live.
Dead code analysis crashed because a symbol that is called/used didn't appear in the symbol
table.
This patch fixes this by adding a nullptr check after symbol table lookup.
An operation is considered to properly dominate itself in a graph
region. That's because there is no concept of "dominance" in a graph
region. (`dominates` returns "true" for all pairs of ops in the same
block. It makes sense to do the same for `properlyDominates`.)
Previously, a block was *not* considered to dominate itself in a graph
region. This commit fixes this asymmetry between ops and blocks: both
are now properly dominating themselves in a graph region.
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.
The current implementation does not take into account definitions
created by arguments of nested blocks. This leads to an incorrect
construction of the live-in set of an outer block. Arguments of nested
blocks are added to the live-in set of an outer block.
---------
Signed-off-by: ikulagin <i.kulagin@ispras.ru>
Co-authored-by: ikulagin <i.kulagin@ispras.ru>
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.
The dataflow analysis framework within MLIR allows to customize the
transfer function when a `call-like` operation is encuntered.
The check to see if the analysis was executed in intraprocedural mode
was executed after the check to see if the callee had the
CallableOpInterface, and thus intraprocedural analyses would behave as
interpocedural ones when performing indirect calls.
This commit fixes the issue by performing the check for
intraprocedurality first.
Dense forward analyses were already behaving correctly.
https://github.com/llvm/llvm-project/blob/main/mlir/lib/Analysis/DataFlow/DenseAnalysis.cpp#L63
Co-authored-by: massimo <mo.fioravanti@gmail.com>
The core implementation of the dataflow anlysis framework is
interpocedural by design. While this offers better analysis precision,
it also comes with additional cost as it takes longer for the analysis
to reach the fixpoint state. Add a configuration mechanism to the
dataflow solver to control whether it operates inteprocedurally or not
to offer clients a choice.
As a positive side effect, this change also adds hooks for explicitly
processing external/opaque function calls in the dataflow analyses,
e.g., based off of attributes present in the the function declaration or
call operation such as alias scopes and modref available in the LLVM
dialect.
This change should not affect existing analyses and the default solver
configuration remains interprocedural.
Co-authored-by: Jacob Peng <jacobmpeng@gmail.com>
Fix for a crash reported in #64975.
The crash occurs in the cast located
[here](ece5dd101c/mlir/lib/Analysis/DataFlow/DeadCodeAnalysis.cpp (L262))
because `llvm.unreachable` doesn't implement
`RegionBranchTerminatorOpInterface`.
The crash is caused by `DeadCodeAnalysis` assuming that
`isa<RegionBranchOpInterface>(op->getParentOp())` implies
`isa<RegionBranchTerminatorOpInterface>(op)` in
`DeadCodeAnalysis::visit()`.
This patch tried to fix this by enabling the analysis to proceed
regardless of whether `op` is a `RegionBranchTerminatorOpInterface`.
The PredecessorState in dead code analysis does not register
zero-operand returns as predecessors of their corresponding call ops.
This causes bugs with dense dataflow analyses that use dead code
analysis to query for the predecessors of CallOpInterfaces.
This was reasonable for sparse analyses, but isn't for dense ones.
Currently, data in `AbstractSparseBackwardDataFlowAnalysis` is
considered to flow one-to-one, in order, from the operands of an op
implementing `CallOpInterface` to the arguments of the function it is
calling.
This understanding of the data flow is inaccurate. The operands of such
an op that forward to the function arguments are obtained using a
method provided by `CallOpInterface` called `getArgOperands()`.
This commit fixes this bug by using `getArgOperands()` instead of
`getOperands()` to get the mapping from operands to function arguments
because not all operands necessarily forward to the function arguments
and even if they do, they don't necessarily have to be in the order in
which they appear in the op. The operands that don't get forwarded are
handled by the newly introduced `visitCallOperand()` function, which
works analogous to the `visitBranchOperand()` function.
This fix is also propagated to liveness analysis that earlier relied on
this incorrect implementation of the sparse backward dataflow analysis
framework and corrects some incorrect assumptions made in it.
Extra cleanup: Improved a comment and removed an unnecessary code line.
Signed-off-by: Srishti Srivastava <srishtisrivastava.ai@gmail.com>
Reviewed By: matthiaskramm, jcai19
Differential Revision: https://reviews.llvm.org/D157261
Earlier, in the sparse backward dataflow analysis, data from the results
of an op implementing `RegionBranchOpInterface` was considered to flow
into the operands of every op that did not implement the
`RegionBranchTerminatorOpInterface` but was return-like and present
in a region of the former. It was thus also expected that the number of
results of the former be equal to the number of operands in the latter.
This understanding of dataflow is incorrect and thus this expectation is
also not justified. This commit fixes this incorrect understanding.
This commit ensures that these return-like ops are handled just like the
ops implementing the `RegionBranchTerminatorOpInterface`, which means
that, if this op has a region `A` whose successors are regions `B`, `C`,
and `D`, then data flows from the arguments (successor inputs) of `B`,
`C`, and `D` to the corresponding successor operands of this op.
This fix is also propagated to liveness analysis that earlier relied on
this incorrect implementation of the sparse backward dataflow analysis
framework and corrects some incorrect assumptions made in it.
Also cleaned up some unnecessary comments from the test file.
Issue: https://github.com/llvm/llvm-project/issues/64139.
Signed-off-by: Srishti Srivastava <srishtisrivastava.ai@gmail.com>
Reviewed By: jcai19, matthiaskramm, Mogball
Differential Revision: https://reviews.llvm.org/D156376
This commit adds a utility to implement liveness analysis using the
sparse backward data-flow analysis framework. Theoretically, liveness
analysis assigns liveness to each (value, program point) pair in the
program and it is thus a dense analysis. However, since values are
immutable in MLIR, a sparse analysis, which will assign liveness to
each value in the program, suffices here.
Liveness analysis has many applications. It can be used to avoid the
computation of extraneous operations that have no effect on the memory
or the final output of a program. It can also be used to optimize
register allocation. Both of these applications help achieve one very
important goal: reducing runtime.
A value is considered "live" iff it:
(1) has memory effects OR
(2) is returned by a public function OR
(3) is used to compute a value of type (1) or (2).
It is also to be noted that a value could be of multiple types (1/2/3) at
the same time.
A value "has memory effects" iff it:
(1.a) is an operand of an op with memory effects OR
(1.b) is a non-forwarded branch operand and a block where its op could
take the control has an op with memory effects.
A value `A` is said to be "used to compute" value `B` iff `B` cannot be
computed in the absence of `A`. Thus, in this implementation, we say that
value `A` is used to compute value `B` iff:
(3.a) `B` is a result of an op with operand `A` OR
(3.b) `A` is used to compute some value `C` and `C` is used to compute
`B`.
---
It is important to note that there already exists an MLIR liveness
utility here: llvm-project/mlir/include/mlir/Analysis/Liveness.h. So,
what is the need for this new liveness analysis utility being added by
this commit? That need is explained as follows:-
The similarities between these two utilities is that both use the
fixpoint iteration method to converge to the final result of liveness.
And, both have the same theoretical understanding of liveness as well.
However, the main difference between (a) the existing utility and (b)
the added utility is the "scope of the analysis". (a) is restricted to
analysing each block independently while (b) analyses blocks together,
i.e., it looks at how the control flows from one block to the other,
how a caller calls a callee, etc. The restriction in the former implies
that some potentially non-live values could be marked live and thus the
full potential of liveness analysis will not be realised.
This can be understood using the example below:
```
1 func.func private @private_dead_return_value_removal_0() -> (i32, i32) {
2 %0 = arith.constant 0 : i32
3 %1 = arith.addi %0, %0 : i32
4 return %0, %1 : i32, i32
5 }
6 func.func @public_dead_return_value_removal_0() -> (i32) {
7 %0:2 = func.call @private_dead_return_value_removal_0() : () -> (i32, i32)
8 return %0#0 : i32
9 }
```
Here, if we just restrict our analysis to a per-block basis like (a), we
will say that the %1 on line 3 is live because it is computed and then
returned outside its block by the function. But, if we perform a
backward data-flow analysis like (b) does, we will say that %0#1 of line
7 is not live because it isn't returned by the public function and thus,
%1 of line 3 is also not live. So, while (a) will be unable to suggest
any IR optimizations, (b) can enable this IR to convert to:-
```
1 func.func private @private_dead_return_value_removal_0() -> i32 {
2 %0 = arith.constant 0 : i32
3 return %0 : i32
4 }
5 func.func @public_dead_return_value_removal_0() -> i32 {
6 %0 = call @private_dead_return_value_removal_0() : () -> i32
7 return %0 : i32
8 }
```
One operation was removed and one unnecessary return value of the
function was removed and the function signature was modified. This is an
optimization that (b) can enable but (a) cannot. Such optimizations can
help remove a lot of extraneous computations that are currently being
done.
Signed-off-by: Srishti Srivastava <srishtisrivastava.ai@gmail.com>
Reviewed By: matthiaskramm, jcai19
Differential Revision: https://reviews.llvm.org/D153779
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
Initial implementations of dense dataflow analyses feature special cases
for operations that have region- or call-based control flow by
leveraging the corresponding interfaces. This is not necessarily
sufficient as these operations may influence the dataflow state by
themselves as well we through the control flow. For example,
`linalg.generic` and similar operations have region-based control flow
and their proper memory effects, so any memory-related analyses such as
last-writer require processing `linalg.generic` directly instead of, or
in addition to, the region-based flow.
Provide hooks to customize the processing of operations with region-
cand call-based contol flow in forward and backward dense dataflow
analysis. These hooks are trigerred when control flow is transferred
between the "main" operation, i.e. the call or the region owner, and
another region. Such an apporach allows the analyses to update the
lattice before and/or after the regions. In the `linalg.generic`
example, the reads from memory are interpreted as happening before the
body region and the writes to memory are interpreted as happening after
the body region. Using these hooks in generic analysis may require
introducing additional interfaces, but for now assume that the specific
analysis have spceial cases for the (rare) operaitons with call- and
region-based control flow that need additional processing.
Reviewed By: Mogball, phisiart
Differential Revision: https://reviews.llvm.org/D155757
This is the counterpart to the forward dense dataflow analysis and
integrates into the dataflow framework. The implementation follows the
structure of existing dataflow analyses.
Reviewed By: Mogball, phisiart
Differential Revision: https://reviews.llvm.org/D154713
This commit introduces an instantiation of LLVM's LoopInfo for CFGs in
MLIR. To test the LoopInfo, a test pass is added the checks the analysis
results for a set of CFGs.
Reviewed By: ftynse
Differential Revision: https://reviews.llvm.org/D147323
Foo analysis for testing the data flow analysis does not support the region without any block. Although that analysis is assumed to be used for testing purpose, it is generally better to be explicit about the scope the framework supports.
The original issue was reported here.
https://github.com/llvm/llvm-project/issues/60580
Reviewed By: springerm
Differential Revision: https://reviews.llvm.org/D144359
This is generated by running
```
sed --in-place 's/[[:space:]]\+$//' mlir/**/*.td
sed --in-place 's/[[:space:]]\+$//' mlir/**/*.mlir
```
Reviewed By: rriddle, dcaballe
Differential Revision: https://reviews.llvm.org/D138866
In D134622 the printed form of a pass manager is changed to include the
name of the op that the pass manager is anchored on. This updates the
`-pass-pipeline` argument format to include the anchor op as well, so
that the printed form of a pipeline can be directly passed to
`-pass-pipeline`. In most cases this requires updating
`-pass-pipeline='pipeline'` to
`-pass-pipeline='builtin.module(pipeline)'`.
This also fixes an outdated assert that prevented running a
`PassManager` anchored on `'any'`.
Reviewed By: rriddle
Differential Revision: https://reviews.llvm.org/D134900
