Looks good to me--a much needed improvement! However, someone with a more recent knowledge of PDL should review as well.

As I mentioned in the previous diff on this stack, instead of implementing a new op ChooseRange, you should generalize ForEach. Also, GetItem is a duplicate of Extract.

Rebased.

Rebased.

Rebased off main.

Rebased.

Rebased.

Check against impl directly

Fix printing of null value in SSANameState::printValueID.

Implemented a custom walk to determine the liveness range of an operation.

Changed to 0-based indexing of the insertion order.

Incorporated review feedback.

Add operations to a block to facilitate automatic deletion.

Review feedback.

It is a bit unusual to work with operations that aren't inserted in a block, I guess it works here...

Messed up a rebase, will submit a new diff.

Review feedback.

I am not able to reproduce the leak on Apple clang version 12.0.5 (running on M1). Will try on a different machine tomorrow.

@bondhugula I am not sure, but I built this with GCC 5.4 myself. The code compiled, and all the tests passed.

@mehdi_amini thanks for bringing this up; I will take a look.

Rebased.

Rebased.

Rebased.

Minor cleanups.

Minor cleanup.

Added comment.

Switch from pdl_interp.get_value to pdl_interp.extract.

Rebased.

Implemented pdl_interp.extract.

Generalized pdl_interp.get_value to pdl_interp.extract

@rriddle I hope that my latest update addresses your concerns.

Rebased.

Use pdl_interp.get_value for upward traversal of value ranges.

Rebased.

Fixed the semantics of get_users for value range and implemented pdl_interp.get_value.

Fixed the comments.

Updated semantics of pdl_interp.get_users to return all users for a value range.
Added pdl_interp.get_value operation for extracting value with given index from a range.

On the second thought, the two operations (pdl_interp.get_defining_op and pdl_interp.get_users) are not symmetric. And I do see value in mimicking c++ API. I will make the change requested.

Also, as much as I understand that we are defining this new op based on a limited use case, under what circumstances would we want to return all the users of a range? In PDL, the range of values will always show up together as operands, so returning the users of a representative seems just fine.

@rriddle I am happy to make pdl_interp.get_users return all users for a range to match the ResultRange behavior (and updating the PDL-to-PDLInterp lowering). But aren't we equally worried about the inconsistency of pdl_interp.get_defining_op and pdl_interp.get_users? And does this mean I need to introduce another operation to extract the value from a list?

Extract the previous code iterator manually.

Print location instead of line numbers.

Updated code to simplified pdl_interp.get_users.

Rebased.

Simplified GetUsers.

Fixed English mistake.

Simplified pdl_interp.get_users.

Split GetUsers into GetUsersAll and GetUsersAt.

There are two places where we do an extra traversal: 1) when verifying the PDL pattern (checking for connectivity), and 2) when forming the predicate tree (detecting the roots). Both are O(E), where E is the total number of operands across all the operations in the PDL pattern -- hardly an expensive operation. Just to be sure, I did a barebones test, where I took 100 copies of test/Conversion/PDLToPDLInterp/pdl-to-pdl-interp-matcher.mlir concatenated together, and ran mlir-opt -split-input-file -convert-pdl-to-pdl-interp > /dev/null on the resulting file. The runtime of my version and the baseline version of mlir-opt were the same.

Rebased

Rebased.

Split out the debug functionality & further review feedback.

Gentle ping, @rriddle @mehdi_amini

@rriddle: This is the last remaining diff. If you can re-review it whenever you are free, that would be greatly appreciated. Then we can land all 4 and iterate. Thank you!

Final review feedback; also fixed the connected component checking code.

Rebased.

Updated comment with the IntervalMap fix.

Replaced ForEachOp::create with a custom builder.

Ran clang-format.

Addressed review feedback.

Addressed review feedback.

Attempt to fix a rebase problem.

I am sorry, I am not sure why my recent changes to PDLInterps files are showing up here. It's as if the base commit was not set right. I did update the stack diff #1. Any ideas?

Addressed review feedback and made further improvements:

1. Fixed the insertion point on pdl_interp.create_operation.
2. Fixed the implementation of pdl_interp.get_users to match its semantics specified in stacked diff #1.
3. Eliminated the extra map storing the block for each instruction address. Instead, we store the line number of the instruction directly in the bytecode when debug messages are turned on.
4. pdl_interp.foreach no longer consumes the range being iterated over. Instead, we store the index into the range and update this index every time we call pdl_interp.continue.
5. PDLByteCodeMutableState::opRangeMemory now stores an owning reference to each range.
6. Improved unit tests coverage.

Cleaned up the semantics of pdl_interp.get_users for range of values.

In D108547#3060427, @Mogball wrote:

General question: what's the cost if I never use multi-root patterns?

Thanks, I will make the changes suggested.

Thank you for the review @rriddle. Will submit an update later today.

Migrated to pdl_interp.foreach and autodetecting roots

Addressed review feedback.