Page MenuHomePhabricator

[MLIR][PDL] Add optional attribute to enable commutativity in PDL
Needs ReviewPublic

Authored by srishti-pm on Feb 1 2022, 1:45 AM.

Details

Reviewers
rriddle
Summary

Added an optional unitAttr "commutative" to the pdl.operation op. If
present, it specifies to the matcher that the operation should be
treated as commutative w.r.t. all its operands.

Co-authors: Srishti Srivastava, Prateek Gupta

Signed-off-by: Srishti Srivastava <srishti.srivastava@polymagelabs.com>

Diff Detail

Event Timeline

srishti-pm created this revision.Feb 1 2022, 1:45 AM
srishti-pm requested review of this revision.Feb 1 2022, 1:45 AM
sfuniak added inline comments.Feb 3 2022, 4:16 AM
mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
280–282

It is not clear to me from this description whether, with the commutative attribute present, the matched operation will always be treated as commutative or if it is treated as commutative provided it has a suitable IsCommutative trait / attribute.

397–400

Is there a reason not to pass the UnitAttr() temporary directly to the build function? Maybe someone more familiar with LLVM style can comment.

srishti-pm added inline comments.
mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
280–282

I believe there is no IsCommutative trait defined and thus the matched operation should always be treated as commutative when the commutative attribute is present. Is there something I'm missing here? I believe you have more knowledge about this implementation than me.

397–400

Yes, I think the original author to this (Prateek) did this because all the other values are also not being passed directly. But, I think someone more familiar with the style could answer this. Pinging @bondhugula to share his views here.

Herald added a project: Restricted Project. · View Herald TranscriptMar 2 2022, 10:47 AM
rriddle added inline comments.Mar 8 2022, 10:10 AM
mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
280–282

Well, there is (https://github.com/llvm/llvm-project/blob/29511ec7da0a740d7dec2d0f57d858d691e73ce1/mlir/include/mlir/IR/OpDefinition.h#L1116) which we could check to see if an operation is commutative. I guess the real question is if we always want to generate a commutative matcher for commutative operations, or only when requested.

Chia-hungDuan added inline comments.Mar 8 2022, 10:18 AM
mlir/include/mlir/Dialect/PDL/IR/PDLOps.td
280–282

Just FYI, the commutative in DRR is on demand based. The cases I see don't always want the commutative property to be applied while matching

Can you post an RFC on discourse discussing the desired extensions to PDL/PDLInterp/ByteCode to enable commutative matching? I know @Mogball had some concerns about some extensions to the PDLInterp/bytecode, and it would be good to discuss the full design.

The implementation of commutative matching is very byte-code heavy but it's effectively just permuting every combination of operands. I think this can be implemented by just generating one pattern for every combination. Commutative patterns for an arbitrary number of operands are undesirable in both cases due to combinatorial explosion... Generally the approach is to have a canonical form for the order of operands. I wonder if this could be implemented generatively by creating patterns that reorder operands to the "canonical" form set by the commutative pattern.

The implementation of commutative matching is very byte-code heavy but it's effectively just permuting every combination of operands. I think this can be implemented by just generating one pattern for every combination. Commutative patterns for an arbitrary number of operands are undesirable in both cases due to combinatorial explosion... Generally the approach is to have a canonical form for the order of operands. I wonder if this could be implemented generatively by creating patterns that reorder operands to the "canonical" form set by the commutative pattern.

Agree with Jeff. In DRR, only pair of operands are allowed to mark as commutative matching. Sorry, I didn't see many cases and not sure how often do we need the commutative property applied on more than two operands. I was wondering if an operation have more than two operands can be commutative, does that imply the design of operation could be refactored?

srishti-pm marked 2 inline comments as not done.Mar 8 2022, 10:57 PM

Can you post an RFC on discourse discussing the desired extensions to PDL/PDLInterp/ByteCode to enable commutative matching? I know @Mogball had some concerns about some extensions to the PDLInterp/bytecode, and it would be good to discuss the full design.

@rriddle, I have created it. Link: https://discourse.llvm.org/t/mlir-pdl-extending-pdl-pdlinterp-bytecode-to-enable-commutative-matching/60798. Kindly add your suggestions here.

The implementation of commutative matching is very byte-code heavy but it's effectively just permuting every combination of operands. I think this can be implemented by just generating one pattern for every combination. Commutative patterns for an arbitrary number of operands are undesirable in both cases due to combinatorial explosion... Generally the approach is to have a canonical form for the order of operands. I wonder if this could be implemented generatively by creating patterns that reorder operands to the "canonical" form set by the commutative pattern.

Creating more patterns rather than this approach does seem better to me as well. I have created an RFC to track the discussion on the desired requirements. Its link: https://discourse.llvm.org/t/mlir-pdl-extending-pdl-pdlinterp-bytecode-to-enable-commutative-matching/60798. Please feel free to add your comments there. Once a conclusion is reached there, I will begin implementing the same.

This change is obsolete now, based on our concluding remark here: https://discourse.llvm.org/t/mlir-pdl-extending-pdl-pdlinterp-bytecode-to-enable-commutative-matching/60798/19?u=srishtisrivastava. I am currently working on the finalized utility and will create a revision to incorporate the same into llvm-project.