[MLIR][PDLInterp] Define new ops in PDLInterp to support commutativity

[srishti-pm]

Summary

Defined 4 new ops in the PDLInterp dialect to help support
commutativity. The ops are as follows:

1. pdl_interp.choose_range: This op performs a nondeterministic choice

of a range of PDL Values from a list of ranges.

2. pdl_interp.get_item: This op gets an operand at index from a range of

values.

3. pdl_interp.get_permutations: This op gets the permutations of given

list of PDL Values.

4. pdl_interp.is_commutative: This op checks if a positional value is a

commutative operation.

Co-authors: Srishti Srivastava, Prateek Gupta

Signed-off-by: Srishti Srivastava <[e-mail]>

[srishti-pm]

Correct a typo in the commit summary.

[Mogball]

Can you add lit tests for these new ops?

[rriddle]

Thanks! Will get to reviewing this stack in the next day or two.

[sfuniak]

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

377–394

This is a duplicate of pdl_interp.foreach. Please remove this op and generalize pdl_interp.foreach if needed.

749–766

This is a duplicate of pdl_interp.extract; please remove.

1034–1051

Do we still need this op? As discussed earlier, I thought that whether or not an operation is commutative should be specified in the pdl.operation. If you do not want to force commutativity in pdl.operation, care must be taken to avoid the exponential blowup of the generated pdl_interp code.

[srishti-pm]

In D118684#3292160, @Mogball wrote:

Can you add lit tests for these new ops?

Sure, I'll do that. There is yet a consensus to be reached about which ops we add here. Will add their lit tests once that consensus is reached.

[srishti-pm]

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

377–394

Thanks Stano! I'm working on this.

749–766

Sure, working on it.

1034–1051

How would you advice this to be specified in the pdl.operation? Also, could you kindly let me know the following:

If my pattern looks like this in PDL:
%c = pdl.operation "foo.op" commutative (%a, %b : !pdl.value, !pdl.value) ->(%type : !pdl.type)
pdl.rewrite %c with "rewriter",
then how would you want its PDL_Interp to look like?

[srishti-pm]

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

749–766

@sfuniak, is it okay to generalize the pdl_interp.extract op? It seems like they aren't really exact duplicates and the pdl_interp.extract op might need some changes.

[srishti-pm]

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 and my new solution here: https://reviews.llvm.org/D124750.

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

def PDLInterp_CheckTypesOp
   }];
 
   let arguments = (ins PDL_RangeOf<PDL_Type>:$value,
                        TypeArrayAttr:$types);
   let assemblyFormat = "$value `are` $types attr-dict `->` successors";
 }
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::ChooseRangeOp
+//===----------------------------------------------------------------------===//
+
+def PDLInterp_ChooseRangeOp 
+    : PDLInterp_Op<"choose_range", [NoSideEffect]> {
+  let summary = "Nondeterministic choice of a range of PDL Values from a list"
+                "of ranges.";
+  let description = [{
+    `pdl_interp.choose_range` returns an `range` of PDL Values from a given
+    `list` of ranges. A range/ordering of PDL values is selected and then the
+    rest of the pattern is executed until `pdl_interp.finalize` is reached.
+    Example:
+    ```mlir
+      %order = pdl_interp.choose_range from %list
+    ```
+  }];
+
+  let arguments = (ins PDL_RangeOf<PDL_RangeOf<PDL_Value>>:$list);
+  let results = (outs PDL_RangeOf<PDL_Value>:$range);
+  let assemblyFormat = "`from` $list attr-dict";
+}
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::ContinueOp
 //===----------------------------------------------------------------------===//
 
 def PDLInterp_ContinueOp
     : PDLInterp_Op<"continue", [NoSideEffect, HasParent<"ForEachOp">,
                                Terminator]> {
   let summary = "Breaks the current iteration";
   let description = [{
def PDLInterp_GetDefiningOpOp
   }];
 
   let arguments = (ins PDL_InstOrRangeOf<PDL_Value>:$value);
   let results = (outs PDL_Operation:$operation);
   let assemblyFormat = "`of` $value `:` type($value) attr-dict";
 }
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::GetItemOp
+//===----------------------------------------------------------------------===//
+
+def PDLInterp_GetItemOp : PDLInterp_Op<"get_item"> {
+  let summary = "Gets an operand at index from a range of values.";
+  let description = [{
+    `pdl_interp.get_item` gets a `value` specified at a particular
+    `index` from a range of values/operands, `values`.
+    Example:
+    ```mlir
+      %0 = pdl_interp.get_item 0 from %values
+    ```  
+  }];
+
+  let arguments = (ins
+    PDL_RangeOf<PDL_Value>:$values,
+    Confined<I32Attr, [IntNonNegative]>:$index
+  );
+  let results = (outs PDL_Value:$value);
+  let assemblyFormat = "$index `from` $values attr-dict";
+}
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::GetOperandOp
 //===----------------------------------------------------------------------===//
 
 def PDLInterp_GetOperandOp : PDLInterp_Op<"get_operand", [NoSideEffect]> {
   let summary = "Get a specified operand from an `Operation`";
   let description = [{
     `pdl_interp.get_operand` operations try to get a specific operand from an
     operation If the operation does not have an operand for the given index, a
OpBuilder<(ins "Type":$resultType, "Value":$operation,
                    "Optional<unsigned>":$index), [{
       build($_builder, $_state, resultType, operation,
             index ? $_builder.getI32IntegerAttr(*index) : IntegerAttr());
     }]>,
   ];
 }
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::GetPermutationsOp
+//===----------------------------------------------------------------------===//
+
+def PDLInterp_GetPermutationsOp : 
+                PDLInterp_Op<"get_permutations", [NoSideEffect]> {
+  let summary = "Get the permutations of given list of PDL Values.";
+  let description = [{
+    `pdl_interp.get_permutations` operation gets all the permutations of a given
+    list of PDL Values. If the `list` has values [0 , 1] then `permutations` will
+    be a list of lists [[0 , 1], [1 , 0]].
+    Example:
+    ```mlir
+      %0 = pdl_interp.get_permutations for %list
+    ```
+  }];
+
+  let arguments = (ins PDL_RangeOf<PDL_Value>:$list);
+  let results = (outs PDL_RangeOf<PDL_RangeOf<PDL_Value>>:$permutations);
+  let assemblyFormat = "`for` $list attr-dict";
+}
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::GetResultOp
 //===----------------------------------------------------------------------===//
 
 def PDLInterp_GetResultOp : PDLInterp_Op<"get_result", [NoSideEffect]> {
   let summary = "Get a specified result from an `Operation`";
   let description = [{
     `pdl_interp.get_result` operations try to get a specific result from an
     operation. If the operation does not have a result for the given index, a
let builders = [
     OpBuilder<(ins), [{
       build($_builder, $_state,
             pdl::RangeType::get($_builder.getType<pdl::TypeType>()));
     }]>
   ];
 }
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::IsCommutativeOp
+//===----------------------------------------------------------------------===//
+def PDLInterp_IsCommutativeOp
+    : PDLInterp_PredicateOp<"is_commutative", [NoSideEffect]> {
+  let summary = "Check if a positional value is a commutative operation";
+  let description = [{
+    `pdl_interp.is_commutative` operation checks whether a positional value is a
+    commutative operation, and on success this operation branches to the true
+    destination; otherwise, the false destination is taken.
+
+    Example:
+
+    ```mlir
+    pdl_interp.is_commutative %op : !pdl.operation -> ^matchDest, ^failureDest
+    ```
+  }];
+
+  let arguments = (ins PDL_Operation:$op);
+  let assemblyFormat = "$op `:` type($op) attr-dict `->` successors";
+}
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::IsNotNullOp
 //===----------------------------------------------------------------------===//
 
 def PDLInterp_IsNotNullOp
     : PDLInterp_PredicateOp<"is_not_null", [NoSideEffect]> {
   let summary = "Check if a positional value is non-null";
   let description = [{
     `pdl_interp.is_not_null` operations check that a positional value or range