MLIR's data flow analysis (especially dense data flow analysis)
constructs a lattice at every lattice anchor (which, for dense data
flow, means every program point). As the program grows larger, the time
and space complexity can become unmanageable.
However, in many programs, the lattice values at numerous lattice
anchors are actually identical. We can leverage this observation to
improve the complexity of data flow analysis. This patch introducing
equivalence lattice anchor to group lattice anchors that must contains
identical lattice on certain state to improve the time and space
footprint of data flow.
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.
I observed that we have the boundary comments in the codebase like:
```
//===----------------------------------------------------------------------===//
// ...
//===----------------------------------------------------------------------===//
```
I also observed that there are incomplete boundary comments. The
revision is generated by a script that completes the boundary comments.
```
//===----------------------------------------------------------------------===//
// ...
...
```
Signed-off-by: hanhanW <hanhan0912@gmail.com>
We can use *Set::insert_range to collapse:
for (auto Elem : Range)
Set.insert(E);
down to:
Set.insert_range(Range);
In some cases, we can further fold that into the set declaration.
DenseSet, SmallPtrSet, SmallSet, SetVector, and StringSet recently
gained C++23-style insert_range. This patch replaces:
Dest.insert(Src.begin(), Src.end());
with:
Dest.insert_range(Src);
This patch does not touch custom begin like succ_begin for now.
This is a code cleanup. Update a few places in MLIR that should use
`hasSingleElement`/`getSingleElement`.
Note: `hasSingleElement` is faster than `.getSize() == 1` when it is
used with linked lists etc.
Depends on #131508.
Improve memref region utility (`getConstantBoundingSizeAndShape`) to get
its constant bounding size and shape using affine expressions/maps by
also considering local variables in the system. Leads to significantly
precise and tighter bounding size and shape in the presence of div/mod
expressions (as evident from the test cases). The approach is now more
robust, proper, and complete. For affine fusion, this leads to private
memrefs of accurate size in several cases. This also impacts other
affine analysis-based passes like data copy generation that use memref
regions.
With contributions from `Vinayaka Bandishti <vinayaka@polymagelabs.com>`
on `getConstantBoundingSizeAndShape` and getConstantBoundOnDimSize`.
Fixes: https://github.com/llvm/llvm-project/issues/46317
Co-authored-by: Vinayaka Bandishti <vinayaka@polymagelabs.com>
Fix/improve debug messages and API signatures for affine
analysis/fusion utils.
Move some warnings under LLVM_DEBUG. These weren't meant to be exposed
during compilation.
Add dump pretty methods for FlatLinearConstraints.
NFC.
When querying the lower bound and upper bound of loop to update the
value range of a loop iteration variable, the program point to depend on
should be the block corresponding to the iteration variable rather than
the loop operation.
Detailed writeup is in https://github.com/google/heir/issues/1153. See
also https://github.com/llvm/llvm-project/pull/120881. In short,
`propagateIfChanged` is used outside of the `DataFlowAnalysis` scope,
because it is public, but it does not propagate as expected as the
`DataFlowSolver` has stopped running.
To solve such misuse, `propagateIfChanged` should be made
protected/private.
For downstream users affected by this, to correctly propagate the
change, the Analysis should be re-run (check #120881) instead of just a
`propagateIfChanged`
The change to `IntegerRangeAnalysis` is just a expansion of the
`solver->propagateIfChanged`. The `Lattice` has already been updated by
the `join`. Propagation is done by `onUpdate`.
Cc @Mogball for review
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.
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.
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.
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.
This commit fixes the failure in the original PR when building with
shared libs. The problem is that `visitUsedValuesDefinedAbove` is
defined in `MLIRTransformUtils`, but that lib depends on this lib
(`MLIRAnalysis`). To fix, I dropped the use of
`visitUsedValuesDefinedAbove` and use `Region::walk` to traverse values
defined above.
Reapplies PR https://github.com/llvm/llvm-project/pull/113478
Reverts PR https://github.com/llvm/llvm-project/pull/114432
This reverts commit a9a8351.
This change modifies `getBackwardSlice` to track values captures by the
regions of each operation that it traverses. Ignoring values captured
from a parent region may lead to an incomplete program slice. However,
there seems to be logic that depends on not traversing captured values,
so this change preserves the default behavior by hiding this logic
behind the `omitUsesFromAbove` flag.
I noticed that several assertions in MLIR codebase have issues with
operator precedence
The issue with operator precedence in these assertions is due to the way
logical operators are evaluated. The `&&` operator has higher precedence
than the `||` operator, which means the assertion is currently
evaluating incorrectly, like this:
```
assert((resType.getNumDynamicDims() == dynOutDims.size()) ||
(dynOutDims.empty() && "Either none or all output dynamic dims must be specified!"));
```
We should add parentheses around the entire expression involving
`dynOutDims.empty()` to ensure that the logical conditions are grouped
correctly. Here’s the corrected version:
```
assert(((resType.getNumDynamicDims() == dynOutDims.size()) || dynOutDims.empty()) &&
"Either none or all output dynamic dims must be specified!");
```
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
This macros is always defined: either 0 or 1. The correct pattern is to
use #if.
Re-apply #110185 with more fixes for debug build with the ABI breaking
checks disabled.
Hello Arjun! Please allow me to contribute this patch as it helps me
debugging significantly! When the 1's and 0's don't line up when
debugging farkas lemma of numerous polyhedrons using simplex lexmin
solver, it is truly straining on the eyes. Hopefully this patch can help
others!
The unfortunate part is the lack of testcase as I'm not sure how to add
testcase for debug dumps. :) However, you can add this testcase to the
SimplexTest.cpp to witness the nice printing!
```c++
TEST(SimplexTest, DumpTest) {
int COLUMNS = 2;
int ROWS = 2;
LexSimplex simplex(COLUMNS * 2);
IntMatrix m1(ROWS, COLUMNS * 2 + 1);
// Adding LHS columns.
for (int i = 0; i < ROWS; i++) {
// an arbitrary formula to test all kinds of integers
for (int j = 0; j < COLUMNS; j++)
m1(i, j) = i + (2 << (i % 3)) * (-1 * ((i + j) % 2));
}
// Adding RHS columns.
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++)
m1(i, j + COLUMNS) = j - (3 << (j % 4)) * (-1 * ((i + j * 2) % 2));
}
for (int i = 0; i < m1.getNumRows(); i++) {
ArrayRef<DynamicAPInt> curRow = m1.getRow(i);
simplex.addInequality(curRow);
}
IntegerRelation rel =
parseRelationFromSet("(x, y, z)[] : (z - x - 17 * y == 0, x - 11 * z >= 1)",2);
simplex.dump();
m1.dump();
rel.dump();
}
```
```
rows = 2, columns = 7
var: c3, c4, c5, c6
con: r0 [>=0], r1 [>=0]
r0: -1, r1: -2
c0: denom, c1: const, c2: 2147483647, c3: 0, c4: 1, c5: 2, c6: 3
1 0 1 0 -2 0 1
1 0 -8 -3 1 3 7
0 -2 0 1 0
-3 1 3 7 0
Domain: 2, Range: 1, Symbols: 0, Locals: 0
2 constraints
-1 -17 1 0 = 0
1 0 -11 -1 >= 0
```
Allow customization of the `resolveCallable` method in the
`CallOpInterface`. This change allows for operations implementing this
interface to provide their own logic for resolving callables.
- Introduce the `resolveCallable` method, which does not include the
optional symbol table parameter. This method replaces the previously
existing extra class declaration `resolveCallable`.
- Introduce the `resolveCallableInTable` method, which incorporates the
symbol table parameter. This method replaces the previous extra class
declaration `resolveCallable` that used the optional symbol table
parameter.
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
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.
This commit introduces a `SelectLikeOpInterface` that can be used to
handle select-like operations generically. Select operations are similar
to control flow operations, as they forward operands depending on
conditions. This is the reason why it was placed to the already existing
control flow interfaces.
This commit introduces a slicing utility that can be used to walk
arbitrary IR slices. It additionally ships logic to determine control
flow predecessors, which allows users to walk backward slices without
dealing with both `RegionBranchOpInterface` and `BranchOpInterface`.
This utility is used to improve the `noalias` propagation in the LLVM
dialect's inliner interface. Before this change, it broke down as soon
as pointer were passed through region control flow operations.
Follow up on a desire post-landing d0fee98 (mlir/Presburger: strip
dependency on MLIRSupport) to reinstate the use of LogicalResult in
Presburger. Since db791b2 (mlir/LogicalResult: move into llvm),
LogicalResult is in LLVM, and fulfilling this desire is possible while
still maintaining the goal of stripping the Presburger library of mlir
dependencies.
Strip the Presburger library's dependency on the MLIR Support library,
as well as the headers, in the interest of making it leaner.
This patch is part of a project to move the Presburger library into
LLVM.
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
Change: remove guards on debug-printing, to allow Release builds without
LLVM_ENABLE_DUMP to pass.
MPInt is an arbitrary-precision integer library that builds on top of
APInt, and has a fast-path when the number fits within 64 bits. It was
originally written for the Presburger library in MLIR, but seems useful
to the LLVM project in general, independently of the Presburger library
or MLIR. Hence, move it into LLVM/ADT under the name DynamicAPInt.
This patch is part of a project to move the Presburger library into
LLVM.
MPInt is an arbitrary-precision integer library that builds on top of
APInt, and has a fast-path when the number fits within 64 bits. It was
originally written for the Presburger library in MLIR, but seems useful
to the LLVM project in general, independently of the Presburger library
or MLIR. Hence, move it into LLVM/ADT under the name DynamicAPInt.
This patch is part of a project to move the Presburger library into
LLVM.
