This is an archive of the discontinued LLVM Phabricator instance.

Defines new PDLInterp operations needed for multi-root matching in PDL.

Authored by sfuniak on Aug 23 2021, 5:02 AM.



This is commit 1 of 4 for the multi-root matching in PDL, discussed in (topic flagged for review).

These operations are:

  • pdl.get_accepting_ops: Returns a list of operations accepting the given value or a range of values at the specified position. Thus if there are two operations %op1 = "foo"(%val) and %op2 = "bar"(%val) accepting a value at position 0, %ops = pdl_interp.get_accepting_ops of %val : !pdl.value at 0 will return both of them. This allows us to traverse upwards from a value to operations accepting the value.
  • pdl.choose_op: Iteratively chooses one operation from a range of operations. Therefore, writing %op = pdl_interp.choose_op from %ops in the example above will select either %op1or %op2.

Testing: Added the corresponding test cases to mlir/test/Dialect/PDLInterp/ops.mlir.

Diff Detail

Event Timeline

sfuniak created this revision.Aug 23 2021, 5:02 AM
sfuniak requested review of this revision.Aug 23 2021, 5:02 AM
sfuniak edited the summary of this revision. (Show Details)Aug 23 2021, 5:11 AM
rriddle added inline comments.Sep 23 2021, 5:33 PM

Is there a longer more descriptive name we can go for here? Possibly something that also capture the iterative nature of this?

Also, I'm not entirely sure we should mark this NoSideEffect. Or more specifically, I feel like transformations to this operation have a much greater cost than other "no side effect" operations (and I'm not sure if something will negatively take advantage of that). Say if we hoisted this operation higher up, wouldn't we end up executing much more bitcode than before?


I mentioned in the RFC, but isn't this just the users of a value? I would stick with the existing IR terminology whenever possible.

Thank you for your feedback @rriddle. I will update the diff. Are you okay with moving the "body" of the loop to a region to promote better readability?


The name choose_op is a leftover from an earlier interpretation of our approach. In that interpretation, we viewed this operation as making a nondeterministic choice (in the sense of NP/nondeterministic polynomial) that the bytecode executor makes. Shall we change this to pdl_interp.iterate_ops as recommended on the RFC, or even pdl_interp.iterate to allow for other types being iterated over?

I can remove the NoSideEffect attribute. Due to its iterative nature, executing this operation higher up incurs bigger cost. We are leaving it up to a later PR to optimize that.


That's correct, it's just users. I will make the change as recommended by you here and in the RFC.

sfuniak updated this revision to Diff 378557.Oct 10 2021, 8:39 PM

Implemented a pdl_interp.foreach operation.

This change incorporates the community feedback. Instead of listing the operations all in the region of the matcher, we introduce a foreach construct that iterates over the provided operations/values, executing its nested region once for every value of the loop variable. The pdl_interp.foreach is a terminator of the block and specifies the target block that we jump to after the loop gets completed. The terminator of the loop region is pdl_interp.continue, which completes the current iteration and moves on to the next one.

rriddle accepted this revision.Oct 11 2021, 11:24 PM

Really nice!


I like pdl_interp.iterate (or is it foreach now? either one is alright with me), I already have some ideas about what we can do with that using other types of values.

Also, did you intend to drop the NoSideEffect? It still shows in this diff.


Is this foreach now?


For ranges should we do all users of all of the values? Why just the first value?


Could we use the declarative format for this? and use a custom directive for the region parsing (which is the part I think needs custom C++ handling)

This revision is now accepted and ready to land.Oct 11 2021, 11:24 PM

Are you okay with moving the "body" of the loop to a region to promote better readability?

Yeah that seems fine.

sfuniak added inline comments.Oct 12 2021, 4:22 PM

I believe the feedback about NoSideEffect applied to pdl_interp.choose_op (its reincarnation pdl_interp.foreach does not have NoSideEffect). It seems that pdl_interp.continue should have NoSideEffect, much like pdl_interp.finalize. Or am I wrong?


Thanks, will update.


I was not sure what's the right behavior; I do not have a good use case for the range of values. Will make the change you suggested.


I tried and failed to use declarative format. The issue is the parsing of the loop variable, which is an entry block argument. Do you have ideas how this can be done?

rriddle added inline comments.Oct 13 2021, 12:36 AM

Ah, you're right. Sorry about that (my eyes just ignored the actual op)


Gah, I missed that thanks. This is fine to keep in C++ for now.

sfuniak updated this revision to Diff 380903.Oct 20 2021, 4:55 AM
sfuniak marked an inline comment as done.

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

sfuniak marked 5 inline comments as done.Oct 20 2021, 4:58 AM
sfuniak updated this revision to Diff 384961.Nov 4 2021, 9:48 PM

Replaced ForEachOp::create with a custom builder.

rriddle added inline comments.Nov 18 2021, 10:31 AM

of the user operation?


Why are we requiring that the values match the operands of the user? Should we split this op into two? One that just gets the users, and one that does filtering on if the values match the specific operands of the users? This operation right now seems to be merging multiple things into one (which could be represented with components already available): getting the users of an operation, comparing a set of values to the operands of that user.

sfuniak added inline comments.Nov 18 2021, 2:44 PM

We need to match the operands of the user, because we want to perform upward traversal from value to a specific operand group. But you are right, we could break these up into "standard" get_users + existing ops. Part of the reason why we are struggling in the byte code interpreter is that these are grouped together.

sfuniak updated this revision to Diff 388366.Nov 18 2021, 8:11 PM

Simplified pdl_interp.get_users.

sfuniak updated this revision to Diff 388367.Nov 18 2021, 8:13 PM

Fixed English mistake.

rriddle added inline comments.Nov 19 2021, 11:56 AM

Didn't we switch to return all users of ranges?

sfuniak added inline comments.Nov 21 2021, 3:02 PM

See my comment on the other diff. We never returned all users -- rather than grabbing all users of a range, we want users that match all of the range. This is achieved by taking the users of any representative value in a range (in practice, the first one) and filtering it down to those that use the range in its entirety. The newly simplified definition of pdl_interp.get_users captures the former part (gathering the users), whereas the latter (filtering) is performed by pdl_interp.get_operands and pdl_interp.are_equal.

rriddle requested changes to this revision.Nov 21 2021, 3:16 PM
rriddle added inline comments.

That is the issue I have with this though. We are creating a disconnect between what you get from the C++ API, a hypothetical ValueRange::getUsers wouldn't return the users of a single value in the range (it would likely act more similarly to ResultRange::getUsers). I'm a bit concerned that this op, which represents a general concept, is being designed for a very specific use case. If we want to only get the users of a specific value of the range, we could compose in other ways; e.g. extracting the first value of the range and then getting the users from that.

This revision now requires changes to proceed.Nov 21 2021, 3:16 PM
sfuniak added a comment.EditedNov 21 2021, 3:43 PM

@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?

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.

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.

However, I do believe that the current semantics of pdl_interp.get_defining_op for value range is broken. Consider the following example:

%f#2 = "foo"(%x)
%g = "bar"(%y)
%h = "baz"(%f#0, %g)

and a pattern

pdl.pattern {
  %in = pdl.operand
  %type = pdl.type
  %op0 = pdl.operation (%in : !pdl.value) -> (%type, %type : !pdl.type, !pdl.type)
  %res0 = pdl.results of %op0
  %op1 = pdl.operation (%res0 : !pdl.range<value>)
  pdl.rewrite %op1 with "rewriter"

With the current definition of pdl_interp.get_defining_op, the %op1 will match %h (and it should not). We should be checking the defining op of all the values in the range and return null if these ops are not all the same.

sfuniak updated this revision to Diff 388843.Nov 22 2021, 3:01 AM

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.

sfuniak updated this revision to Diff 388845.Nov 22 2021, 3:05 AM

Fixed the comments.

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

Regarding my (supposed) counter-example for pdl_interp.get_defining_op, it's not quite accurate, because we compare the results with the values whose defining operations we queried, so the matching in this case actually works as expected. But I am wondering if we should do something similar to what you suggested for pdl_interp.get_users - extracting the first value in the range and checking its defining op.

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

Regarding my (supposed) counter-example for pdl_interp.get_defining_op, it's not quite accurate, because we compare the results with the values whose defining operations we queried, so the matching in this case actually works as expected. But I am wondering if we should do something similar to what you suggested for pdl_interp.get_users - extracting the first value in the range and checking its defining op.

Thanks for bringing up get_defining_op, I agree that the semantics of that aren't great. For that one, I think we should just detect if the value range is a result range, and if it isn't we just return null.


Another comment on your use of get_users; IIUC you are getting all users of the first value and then comparing against the full range? What happens if other values in the range have more users than the first value?

%a = ...
%b = ...
foo.use1 (%a, %b)
foo.use2 (%b)



Can we have this be a general extract operation that works on any range? We could specialize it further at the bytecode level.


Can you add a note on the behavior if the index is out-of-bounds? I assume we would return null as a failure (as we do in other cases).

sfuniak added inline comments.Nov 24 2021, 2:49 PM

Ultimately, we are looking for users that accept the entirety of the value range as its operands. So if other values in the range have more users than the first value does, those users are not going to be relevant (they do not meet the aforementioned criterion of accepting all the values). We could have chosen any value, not necessarily the first one, and we could have also taken the intersection of users of all the values, rather than the users of just one value. But this does not affect correctness, because we still have the equality check between the operands of the user and the value range.

In a sense, the upward and downward traversals are completely symmetric: we extract the users (for upward traversal) or the defining op (for downward traversal) of the first value and then compare against the operands / results. You have to do this comparison because both users and the defining op are just a hint where the possible match might be found. How exactly we do this in the pdl_interp.get_defining_op is up to you, but the current implementation of that op is correct (though it may not generalize well).


Sure, will do.


Correct, the results for out-of-bounds should be null. Will update the docs.

rriddle accepted this revision.Nov 24 2021, 2:56 PM

LGTM after resolving comments. Really appreciate the discussion on different use cases.


I see. If we only care about the situations in which the operation accepts all operands, indeed the strategy of using a single value works.

This revision is now accepted and ready to land.Nov 24 2021, 2:56 PM
sfuniak updated this revision to Diff 389897.Nov 25 2021, 9:11 PM

Generalized pdl_interp.get_value to pdl_interp.extract

sfuniak updated this revision to Diff 389903.Nov 25 2021, 9:45 PM

Minor cleanup.