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

[sfuniak]

Summary

This is commit 1 of 4 for the multi-root matching in PDL, discussed in https://llvm.discourse.group/t/rfc-multi-root-pdl-patterns-for-kernel-matching/4148 (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.

[rriddle]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

401

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?

638–642

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.

[sfuniak]

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?

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

401

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.

638–642

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

[sfuniak]

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]

Really nice!

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

401

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.

406

Is this foreach now?

898–899

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

mlir/lib/Dialect/PDLInterp/IR/PDLInterp.cpp

200–207

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)

[rriddle]

In D108543#3024057, @sfuniak wrote:

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

Yeah that seems fine.

[sfuniak]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

401

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?

406

Thanks, will update.

898–899

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.

mlir/lib/Dialect/PDLInterp/IR/PDLInterp.cpp

200–207

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]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

401

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

mlir/lib/Dialect/PDLInterp/IR/PDLInterp.cpp

200–207

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

[sfuniak]

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

[sfuniak]

Replaced ForEachOp::create with a custom builder.

[rriddle]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

900

of the user operation?

902–904

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]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

902–904

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]

Simplified pdl_interp.get_users.

[sfuniak]

Fixed English mistake.

[rriddle]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

898–899

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

[sfuniak]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

898–899

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]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

898–899

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.

[sfuniak]

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

[sfuniak]

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.

[sfuniak]

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 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]

Fixed the comments.

[sfuniak]

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

In D108543#3145839, @sfuniak wrote:

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

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

898–899

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)

?

926–954

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

933–934

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]

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

898–899

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).

926–954

Sure, will do.

933–934

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

[rriddle]

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

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

898–899

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.

[sfuniak]

Generalized pdl_interp.get_value to pdl_interp.extract

[sfuniak]

Minor cleanup.