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

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

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

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

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] Enable decoupling two kinds of greedy behavior. (#104649)

The greedy rewriter is used in many different flows and it has a lot of
convenience (work list management, debugging actions, tracin

[mlir] Enable decoupling two kinds of greedy behavior. (#104649)

The greedy rewriter is used in many different flows and it has a lot of
convenience (work list management, debugging actions, tracing, etc). But
it combines two kinds of greedy behavior 1) how ops are matched, 2)
folding wherever it can.

These are independent forms of greedy and leads to inefficiency. E.g.,
cases where one need to create different phases in lowering and is
required to applying patterns in specific order split across different
passes. Using the driver one ends up needlessly retrying folding/having
multiple rounds of folding attempts, where one final run would have
sufficed.

Of course folks can locally avoid this behavior by just building their
own, but this is also a common requested feature that folks keep on
working around locally in suboptimal ways.

For downstream users, there should be no behavioral change. Updating
from the deprecated should just be a find and replace (e.g., `find ./
-type f -exec sed -i
's|applyPatternsAndFoldGreedily|applyPatternsGreedily|g' {} \;` variety)
as the API arguments hasn't changed between the two.

show more ...

[mlir] Do not merge blocks during canonicalization by default (#95057)

This is a heavy process, and it can trigger a massive explosion in
adding block arguments. While potentially reducing the code

[mlir] Do not merge blocks during canonicalization by default (#95057)

This is a heavy process, and it can trigger a massive explosion in
adding block arguments. While potentially reducing the code size, the
resulting merged blocks with arguments are hiding some of the def-use
chain and can even hinder some further analyses/optimizations: a merge
block does not have it's own path-sensitive context, instead the context
is merged from all the predecessors.

Previous behavior can be restored by passing:

{test-convergence region-simplify=aggressive}

to the canonicalize pass.

show more ...

[mlir][Transforms][NFC] `GreedyPatternRewriteDriver`: Use composition instead of inheritance (#92785)

This commit simplifies the design of the `GreedyPatternRewriterDriver`
class. This class used t

[mlir][Transforms][NFC] `GreedyPatternRewriteDriver`: Use composition instead of inheritance (#92785)

This commit simplifies the design of the `GreedyPatternRewriterDriver`
class. This class used to inherit from both `PatternRewriter` and
`RewriterBase::Listener` and then attached itself as a listener.

In the new design, the class has a `PatternRewriter` field instead of
inheriting from `PatternRewriter`, which is generally perferred in
object-oriented programming.

---------

Co-authored-by: Markus Böck <markus.boeck02@gmail.com>

show more ...

[MLIR] Don't check for key before inserting in map in GreedyPatternRewriteDriver worklist (NFC) (#88148)

This is a common anti-pattern (any volunteer for a clang-tidy check?).

This does not show

[MLIR] Don't check for key before inserting in map in GreedyPatternRewriteDriver worklist (NFC) (#88148)

This is a common anti-pattern (any volunteer for a clang-tidy check?).

This does not show real word significant impact though.

show more ...

Add operands to worklist when only used by deleted op (#86990)

I believe the existing check to determine if an operand should be added
is incorrect: `operand.use_empty() || operand.hasOneUse()`. Th

Add operands to worklist when only used by deleted op (#86990)

I believe the existing check to determine if an operand should be added
is incorrect: `operand.use_empty() || operand.hasOneUse()`. This is
because these checks do not take into account the fact that the op is
being deleted. It hasn't been deleted yet, so `operand.use_empty()`
cannot be true, and `operand.hasOneUse()` may be true if the op being
deleted is the only user of the operand and it only uses it once, but it
will fail if the operand is used more than once (e.g. something like
`add %0, %0`).

Instead, check if the op being deleted is the only _user_ of the
operand. If so, add the operand to the worklist.

Fixes #86765

show more ...

[mlir][IR] Add listener notifications for pattern begin/end (#84131)

This commit adds two new notifications to `RewriterBase::Listener`:
* `notifyPatternBegin`: Called when a pattern application be

[mlir][IR] Add listener notifications for pattern begin/end (#84131)

This commit adds two new notifications to `RewriterBase::Listener`:
* `notifyPatternBegin`: Called when a pattern application begins during
a greedy pattern rewrite or dialect conversion.
* `notifyPatternEnd`: Called when a pattern application finishes during
a greedy pattern rewrite or dialect conversion.

The listener infrastructure already provides a `notifyMatchFailure`
callback that notifies about the reason for a pattern match failure. The
two new notifications provide additional information about pattern
applications.

This change is in preparation of improving the handle update mechanism
in the `apply_conversion_patterns` transform op.

show more ...

[mlir][IR][NFC] Rename `notify*Removed` to `notify*Erased` (#82253)

Rename listener callback names:
* `notifyOperationRemoved` -> `notifyOperationErased`
* `notifyBlockRemoved` -> `notifyBlockEras

[mlir][IR][NFC] Rename `notify*Removed` to `notify*Erased` (#82253)

Rename listener callback names:
* `notifyOperationRemoved` -> `notifyOperationErased`
* `notifyBlockRemoved` -> `notifyBlockErased`

The current callback names are misnomers. The callbacks are triggered
when an operation/block is erased, not when it is removed (unlinked).

E.g.:
```c++
/// Notify the listener that the specified operation is about to be erased.
/// At this point, the operation has zero uses.
///
/// Note: This notification is not triggered when unlinking an operation.
virtual void notifyOperationErased(Operation *op) {}
```

This change is in preparation of adding listener support to the dialect
conversion. The dialect conversion internally unlinks IR before erasing
it at a later point of time. There is an important difference between
"remove" and "erase". Lister callback names should be accurate to avoid
confusion.

show more ...

[mlir][IR][NFC] `Listener::notifyMatchFailure` returns `void` (#80704)

There are two `notifyMatchFailure` methods: one in the rewriter and one
in the listener. The one in the rewriter notifies the

[mlir][IR][NFC] `Listener::notifyMatchFailure` returns `void` (#80704)

There are two `notifyMatchFailure` methods: one in the rewriter and one
in the listener. The one in the rewriter notifies the listener and
returns "failure" for convenience. The one in the listener should not
return anything; it is just a notification. It can currently be abused
to return "success" from the rewriter function. That would be a
violation of the rewriter API rules.

Also make sure that the listener is always notified about match
failures, not just with `NDEBUG`. The current implementation is
consistent: one `notifyMatchFailure` overload notifies only in debug
mode and another one notifies all the time.

show more ...

[mlir][Transforms] `GreedyPatternRewriteDriver`: Hash ops separately (#78312)

The greedy pattern rewrite driver has multiple "expensive checks" to
detect invalid rewrite pattern API usage. As part

[mlir][Transforms] `GreedyPatternRewriteDriver`: Hash ops separately (#78312)

The greedy pattern rewrite driver has multiple "expensive checks" to
detect invalid rewrite pattern API usage. As part of these checks, it
computes fingerprints for every op that is in scope, and compares the
fingerprints before and after an attempted pattern application.

Until now, each computed fingerprint took into account all nested
operations. That is quite expensive because it walks the entire IR
subtree. It is also redundant in the expensive checks because we already
compute a fingerprint for every op.

This commit significantly improves the running time of the "expensive
checks" in the greedy pattern rewrite driver.

show more ...

[mlir] Fix build after #75103

After #75103, `MLPrgramTransforms` depends on `BufferizationDialect`.
Also fix an unrelated compile error in `GreedyPatternRewriteDriver.cpp`.
(This was not failing on

[mlir] Fix build after #75103

After #75103, `MLPrgramTransforms` depends on `BufferizationDialect`.
Also fix an unrelated compile error in `GreedyPatternRewriteDriver.cpp`.
(This was not failing on CI. I may be running an old compiler locally.)

show more ...

[mlir][IR] Change `notifyBlockCreated` to `notifyBlockInserted` (#79472)

This change makes the callback consistent with
`notifyOperationInserted`: both now notify about IR insertion, not IR
creati

[mlir][IR] Change `notifyBlockCreated` to `notifyBlockInserted` (#79472)

This change makes the callback consistent with
`notifyOperationInserted`: both now notify about IR insertion, not IR
creation. See also #78988.

This change also simplifies the dialect conversion: it is no longer
necessary to override the `inlineRegionBefore` method. All information
that is necessary for rollback is provided with the
`notifyBlockInserted` callback.

show more ...

[mlir][IR] Add rewriter API for moving operations (#78988)

The pattern rewriter documentation states that "*all* IR mutations [...]
are required to be performed via the `PatternRewriter`." This com

[mlir][IR] Add rewriter API for moving operations (#78988)

The pattern rewriter documentation states that "*all* IR mutations [...]
are required to be performed via the `PatternRewriter`." This commit
adds two functions that were missing from the rewriter API:
`moveOpBefore` and `moveOpAfter`.

After an operation was moved, the `notifyOperationInserted` callback is
triggered. This allows listeners such as the greedy pattern rewrite
driver to react to IR changes.

This commit narrows the discrepancy between the kind of IR modification
that can be performed and the kind of IR modifications that can be
listened to.

show more ...

[mlir][IR] Add `notifyBlockRemoved` callback to listener (#78306)

There is already a "block inserted" notification (in
`OpBuilder::Listener`), so there should also be a "block removed"
notificatio

[mlir][IR] Add `notifyBlockRemoved` callback to listener (#78306)

There is already a "block inserted" notification (in
`OpBuilder::Listener`), so there should also be a "block removed"
notification.

The purpose of this change is to make the listener API more mature.
There is currently a gap between what kind of IR changes can be made and
what IR changes can be listened to. At the moment, the only way to
inform listeners about "block removal" is to send a manual
`notifyOperationModified` for the parent op (e.g., by wrapping the
`eraseBlock(b)` method call in `updateRootInPlace(b->getParentOp())`).
This tells the listener that *something* has changed, but it is somewhat
of an API abuse.

show more ...

[mlir][Transforms] `GreedyPatternRewriteDriver`: Better expensive checks encapsulation (#78175)

This change moves most IR verification logic (which is part of the
expensive checks) into `DebugFinge

[mlir][Transforms] `GreedyPatternRewriteDriver`: Better expensive checks encapsulation (#78175)

This change moves most IR verification logic (which is part of the
expensive checks) into `DebugFingerPrints` and renames the struct to
`ExpensiveChecks`. This isolates the debugging logic better from the
remaining code.

This commit also removes a redundant check: the IR is no longer verified
after a failed pattern application. We already assert that the IR did
not change. (We know that the IR was valid before the attempted pattern
application.)

show more ...

[mlir][Transforms] `GreedyPatternRewriteDriver`: log successful folding (#77796)

Similar to successful pattern applications, dump the rewritten IR after
each successful folding when running with `-

[mlir][Transforms] `GreedyPatternRewriteDriver`: log successful folding (#77796)

Similar to successful pattern applications, dump the rewritten IR after
each successful folding when running with `-debug`.

show more ...

[MLIR] Handle materializeConstant failure in GreedyPatternRewriteDriver (#77258)

Make GreedyPatternRewriteDriver handle failures of `materializeConstant`
gracefully. Previously it was not checking

[MLIR] Handle materializeConstant failure in GreedyPatternRewriteDriver (#77258)

Make GreedyPatternRewriteDriver handle failures of `materializeConstant`
gracefully. Previously it was not checking whether the returned op was
null and crashing. This PR handles it similarly to how OperationFolder
does it.

show more ...

[mlir][Transforms] `GreedyPatternRewriteDriver`: Do not CSE constants during iterations (#75897)

The `GreedyPatternRewriteDriver` tries to iteratively fold ops and apply
rewrite patterns to ops. It

[mlir][Transforms] `GreedyPatternRewriteDriver`: Do not CSE constants during iterations (#75897)

The `GreedyPatternRewriteDriver` tries to iteratively fold ops and apply
rewrite patterns to ops. It has special handling for constants: they are
CSE'd and sometimes moved to parent regions to allow for additional
CSE'ing. This happens in `OperationFolder`.

To allow for efficient CSE'ing, `OperationFolder` maintains an internal
lookup data structure to find the existing constant ops with the same
value for each `IsolatedFromAbove` region:
```c++
/// A mapping between an insertion region and the constants that have been
/// created within it.
DenseMap<Region *, ConstantMap> foldScopes;
```

Rewrite patterns are allowed to modify operations. In particular, they
may move operations (including constants) from one region to another
one. Such an IR rewrite can make the above lookup data structure
inconsistent.

We encountered such a bug in a downstream project. This bug materialized
in the form of an op that uses the result of a constant op from a
different `IsolatedFromAbove` region (that is not accessible).

This commit changes the behavior of the `GreedyPatternRewriteDriver`
such that `OperationFolder` is used to CSE constants at the beginning of
each iteration (as the worklist is populated), but no longer during an
iteration. `OperationFolder` is no longer used after populating the
worklist, so we do not have to care about inconsistent state in the
`OperationFolder` due to IR rewrites. The `GreedyPatternRewriteDriver`
now performs the op folding by itself instead of calling
`OperationFolder::tryToFold`.

This change changes the order of constant ops in test cases, but not the
region in which they appear. All broken test cases were fixed by turning
`CHECK` into `CHECK-DAG`.

Alternatives considered: The state of `OperationFolder` could be
partially invalidated with every `notifyOperationModified` notification.
That is more fragile than the solution in this commit because incorrect
rewriter API usage can lead to missing notifications and hard-to-debug
`IsolatedFromAbove` violations. (It did not fix the above mention bug in
a downstream project, which could be due to incorrect rewriter API usage
or due to another conceptual problem that I missed.) Moreover, ops are
frequently getting modified during a greedy pattern rewrite, so we would
likely keep invalidating large parts of the state of `OperationFolder`
over and over.

Migration guide: Turn `CHECK` into `CHECK-DAG` in test cases. Constant
ops are no longer folded during a greedy pattern rewrite. If you rely on
folding (and rematerialization) of constant ops during a greedy pattern
rewrite, turn the folder into a pattern.

show more ...

[mlir][Transforms] `GreedyPatternRewriteDriver`: verify IR (#74270)

This commit adds an additional "expensive check" that verifies the IR
before starting a greedy pattern rewriter, after every patt

[mlir][Transforms] `GreedyPatternRewriteDriver`: verify IR (#74270)

This commit adds an additional "expensive check" that verifies the IR
before starting a greedy pattern rewriter, after every pattern
application and after every folding. (Only if
`MLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS` is set.)

It also adds an assertion that the `scope` region (part of
`GreedyRewriteConfig`) is not being erased as part of the greedy pattern
rewrite. That would break the scoping mechanism and the expensive
checks.

This commit does not fix any patterns, this is done in separate commits.

show more ...

[mlir][Transforms][NFC] GreedyPatternRewriteDriver: Remove redundant worklist management code (#74796)

Do not add the previous users of replaced ops to the worklist during
`notifyOperationReplaced`

[mlir][Transforms][NFC] GreedyPatternRewriteDriver: Remove redundant worklist management code (#74796)

Do not add the previous users of replaced ops to the worklist during
`notifyOperationReplaced`.

The previous users are modified inplace as part of
`PatternRewriter::replaceOp`, which calls
`PatternRewriter::replaceAllUsesWith`. The latter function updates all
users with `updateRootInPlace`, which already puts all previous users of
the replaced op on the worklist. No further worklist management work is
needed in the `notifyOperationReplaced` callback.

show more ...

[mlir][IR] Trigger `notifyOperationRemoved` callback for nested ops (#66771)

When cloning an op, the `notifyOperationInserted` callback is triggered
for all nested ops. Similarly, the `notifyOperat

[mlir][IR] Trigger `notifyOperationRemoved` callback for nested ops (#66771)

When cloning an op, the `notifyOperationInserted` callback is triggered
for all nested ops. Similarly, the `notifyOperationRemoved` callback
should be triggered for all nested ops when removing an op.

Listeners may inspect the IR during a `notifyOperationRemoved` callback.
Therefore, when multiple ops are removed in a single
`RewriterBase::eraseOp` call, the notifications must be triggered in an
order in which the ops could have been removed one-by-one:

* Op removals must be interleaved with `notifyOperationRemoved`
callbacks. A callback is triggered right before the respective op is
removed.
* Ops are removed post-order and in reverse order. Other traversal
orders could delete an op that still has uses. (This is not avoidable in
graph regions and with cyclic block graphs.)

Differential Revision: Imported from https://reviews.llvm.org/D144193.

show more ...

[mlir][GreedyPatternRewriter] Add out param to detect changes in IR in `applyPatternsAndFoldGreedily`

This allows users of `applyPatternsAndFoldGreedily` to detect if any MLIR changes have occurred.

[mlir][GreedyPatternRewriter] Add out param to detect changes in IR in `applyPatternsAndFoldGreedily`

This allows users of `applyPatternsAndFoldGreedily` to detect if any MLIR changes have occurred. An example use-case is where we expect the `applyPatternsAndFoldGreedily` to change the IR and want to validate that it indeed does change it.

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

show more ...

[mlir][Transforms] GreedyPatternRewriteDriver: Worklist randomizer

Instead of always taking the last op from the worklist, take a random one. For testing/debugging purposes only. This feature can be

[mlir][Transforms] GreedyPatternRewriteDriver: Worklist randomizer

Instead of always taking the last op from the worklist, take a random one. For testing/debugging purposes only. This feature can be used to ensure that lowering pipelines work correctly regardless of the order in which ops are processed by the GreedyPatternRewriteDriver.

The randomizer can be enabled by setting a numeric `MLIR_GREEDY_REWRITE_RANDOMIZER_SEED` option.

Note: When enabled, 27 tests are currently failing. Partly because FileCheck tests are looking for exact IR.

Discussion: https://discourse.llvm.org/t/discussion-fuzzing-pattern-application/67911

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

show more ...

[mlir][Transforms][NFC] GreedyPatternRewriteDriver: Add worklist class

Encapsulate all worklist-related functionality in a separate `Worklist` class. This makes the remaining code more readable and

[mlir][Transforms][NFC] GreedyPatternRewriteDriver: Add worklist class

Encapsulate all worklist-related functionality in a separate `Worklist` class. This makes the remaining code more readable and allows for custom worklist implementations (e.g., a randomized worklist for fuzzing pattern application: D142447).

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

show more ...

[mlir][Transforms] Fix mlir-config flag check

Boolean compiler flags (such as `DMLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS`) show up in `mlir-config.h` as preprocessor defines that are either 0 or 1.

[mlir][Transforms] Fix mlir-config flag check

Boolean compiler flags (such as `DMLIR_ENABLE_EXPENSIVE_PATTERN_API_CHECKS`) show up in `mlir-config.h` as preprocessor defines that are either 0 or 1. Use `#if` instead of `#ifdef`.

This should have been part of D144552.

show more ...