[mlir] Add attribute constraints for sorted order.

[akuegel]

Summary

We often have constraints for array attributes that they are sorted
non-decreasing or strictly increasing. This change adds AttrConstraint classes
that support DenseArrayAttr for integer types.

[akuegel]

Remove unintended whitespace change.

[akuegel]

Remove tabs.

[akuegel]

Fix test name.

[akuegel]

Sorry for the many updates for this patch, I should have self-reviewed everything before uploading. But I have finished self-review now, so it should be ready to take a look now.

[akuegel]

This AttrConstr is planned to be used for Linalg ReduceOp:

ConfinedAttr<DenseI64ArrayAttr, [ArrayStrictlySorted<64>]>:$dimensions

But it seems likely to be useful in other cases as well.
Should I add this usage in this patch, or in a separate one?

[nicolasvasilache]

thanks!

[nicolasvasilache]

In D134944#3826715, @akuegel wrote:

This AttrConstr is planned to be used for Linalg ReduceOp:

ConfinedAttr<DenseI64ArrayAttr, [ArrayStrictlySorted<64>]>:$dimensions

But it seems likely to be useful in other cases as well.
Should I add this usage in this patch, or in a separate one?

Separate patch for separate things is always better IMO.

[nicolasvasilache]

mlir/include/mlir/IR/OpBase.td

1639

Sorry, accepted too quickly, this feels a bit wonky ..

Can we use the full type instead of just the number of bits?

ConfinedAttr<DenseI16ArrayAttr, ArraySorted<DenseI16ArrayAttr>>

just 16 looks very surprising to use here.

[rriddle]

mlir/include/mlir/IR/OpBase.td

1639

The naming on these looks off, Array by itself should only be used for ArrayAttr (this is DenseArrayAttr).

+1 also on not just using bitwidth, the context is not obvious enough here.

[akuegel]

Address review comments.

[akuegel]

mlir/include/mlir/IR/OpBase.td

1639

I am now using DenseArraySorted/DenseArrayStrictlySorted as names.
For DenseArrayStrictlySorted, I still need to pass the element type as well. I am passing it as string, not sure whether it is possible to pass it differently?

[akuegel]

Fix test names, and rebase.

[zero9178]

mlir/include/mlir/IR/OpBase.td

1639

You could use arrayType.returnType instead of ArrayRef<" # elementType # "> to get rid of the element type parameter. The returnType of DenseArrayAttrBase is always an ArrayRef of the element type which happens to be what you need.

[akuegel]

Use arrayType.returnType

mlir/include/mlir/IR/OpBase.td

1639

Thank you very much :)
This is exactly what I need here. Done.

[akuegel]

Fix indentation.

[nicolasvasilache]

mlir/include/mlir/IR/OpBase.td

1645

I think you should be able to use is_sorted with a comparator here ? (i.e. always return false if elements are equal)

[akuegel]

mlir/include/mlir/IR/OpBase.td

1645

TLDR: Technically, it seems using the std::less_equal comparator should work.

I was not sure whether we can rely on the way the comparator will be used. The documentation says you need to pass a "less" comparator. But then it also defines sorted as:

A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, comp(*(it + n), *it) evaluates to false.

If implemented like that, using std::less_equal would definitely work. Also I see that boost uses std::less_equal to implement is_strictly_increasing.

But I think this would mean that I need another parameter to the DenseArrayStrictlySorted constraint: the element type, so that I can specify the comparator. Or is there a way to derive that from DenseArrayAttrBase?

[nicolasvasilache]

mlir/include/mlir/IR/OpBase.td

1645

If it is not possible to use some auto type deduction based on the result of asArrayRef we could always make the cppType available from DenseArrayAttrBase.
But that may be a bridge too far for @rriddle , I am fine with landing as is and iterating later.
Thanks for trying!

mlir/include/mlir/IR/OpBase.td

 class ArrayMinCount<int n> : AttrConstraint<
     CPred<"$_self.cast<::mlir::ArrayAttr>().size() >= " # n>,
     "with at least " # n # " elements">;
 
 class ArrayCount<int n> : AttrConstraint<
     CPred<"$_self.cast<::mlir::ArrayAttr>().size() == " #n>,
     "with exactly " # n # " elements">;
 
+class ArraySorted<int bitwidth> : AttrConstraint<
+    CPred<"llvm::is_sorted($_self.cast<"
+      "::mlir::DenseI" # bitwidth # "ArrayAttr>().asArrayRef())">,
+    "should be in non-decreasing order">;
+
+class ArrayStrictlySorted<int bitwidth> : AttrConstraint<
+    And<[
+      CPred<"llvm::is_sorted($_self.cast<"
+        "::mlir::DenseI" # bitwidth # "ArrayAttr>().asArrayRef())">,
+      // Check that no two adjacent elements are the same.
+      CPred<"[](ArrayRef<int" # bitwidth # "_t> a) {\n"
+        "return std::adjacent_find(std::begin(a), std::end(a)) == "
+        "std::end(a);\n"
+        "}($_self.cast<::mlir::DenseI" # bitwidth # "ArrayAttr>().asArrayRef())"
+      >]>,
+    "should be in increasing order">;
+
 class IntArrayNthElemEq<int index, int value> : AttrConstraint<
     And<[
       CPred<"$_self.cast<::mlir::ArrayAttr>().size() > " # index>,
       CPred<"$_self.cast<::mlir::ArrayAttr>()[" # index # "]"
         ".cast<::mlir::IntegerAttr>().getInt() == " # value>
        ]>,
     "whose " # index # "-th element must be " # value>;
 

mlir/test/IR/attribute.mlir

// CHECK-SAME: emptyattr = []
 
   // CHECK: test.typed_attr tensor<4xi32> = array<1, 2, 3, 4>
   test.typed_attr tensor<4xi32> = array<1, 2, 3, 4>
   return
 }
 
 // -----
 
+func.func @testConfinedDenseElementsAttr() {
+  "test.confined_dense_array_attr"() {
+    i64attr = array<i64: 0, 2, 3>,
+    i32attr = array<i32: 1>,
+    emptyattr = array<i16>
+  } : () -> ()
+  func.return
+}
+
+// -----
+
+func.func @testConfinedDenseElementsAttrDuplicateValues() {
+  // expected-error@+1{{'test.confined_dense_array_attr' op attribute 'i64attr' failed to satisfy constraint: i64 dense array attribute should be in increasing order}}
+  "test.confined_dense_array_attr"() {
+    emptyattr = array<i16>,
+    i32attr = array<i32: 1, 1>,
+    i64attr = array<i64: 0, 2, 2>
+  } : () -> ()
+  func.return
+}
+
+// -----
+
+func.func @testConfinedDenseElementsAttrDuplicateValues() {
+  // expected-error@+1{{'test.confined_dense_array_attr' op attribute 'i32attr' failed to satisfy constraint: i32 dense array attribute should be in non-decreasing order}}
+  "test.confined_dense_array_attr"() {
+    emptyattr = array<i16>,
+    i32attr = array<i32: 1, 0>,
+    i64attr = array<i64: 0, 2, 3>
+  } : () -> ()
+  func.return
+}
+
+// -----
+
 //===----------------------------------------------------------------------===//
 // Test SymbolRefAttr
 //===----------------------------------------------------------------------===//
 
 func.func @fn() { return }
 
 // CHECK: test.symbol_ref_attr
 "test.symbol_ref_attr"() {symbol = @fn} : () -> ()

mlir/test/lib/Dialect/Test/TestOps.td

def DenseArrayAttrOp : TEST_Op<"dense_array_attr"> {
   );
   let assemblyFormat = [{
    `i1attr` `=` $i1attr `i8attr` `=` $i8attr `i16attr` `=` $i16attr
    `i32attr` `=` $i32attr `i64attr` `=` $i64attr  `f32attr` `=` $f32attr
    `f64attr` `=` $f64attr `emptyattr` `=` $emptyattr attr-dict
   }];
 }
 
+def ConfinedDenseArrayAttrOp : TEST_Op<"confined_dense_array_attr"> {
+  let arguments = (ins
+      ConfinedAttr<DenseI16ArrayAttr, [ArrayStrictlySorted<16>]>:$emptyattr,
+      ConfinedAttr<DenseI32ArrayAttr, [ArraySorted<32>]>:$i32attr,
+      ConfinedAttr<DenseI64ArrayAttr, [ArrayStrictlySorted<64>]>:$i64attr
+  );
+}
+
 //===----------------------------------------------------------------------===//
 // Test Enum Attributes
 //===----------------------------------------------------------------------===//
 
 // Define the C++ enum.
 def TestEnum
     : I32EnumAttr<"TestEnum", "a test enum", [
         I32EnumAttrCase<"First", 0, "first">,