[MLIR][PDL] Add support for representing and lowering negated constraints

[martin-luecke]

Summary

This commit enables modelling negation of native constraints.

This is accomplished through an attribute isNegated on the operations pdl.apply_native_constraint and pdl_interp.apply_constraint and according adjustments to the conversion in the ConvertPDLToPDLInterpPass.

[Mogball]

mlir/include/mlir/Dialect/PDL/IR/PDLOps.td

50

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

105–107

please fit this into a line 80 characters wide

mlir/lib/Conversion/PDLToPDLInterp/Predicate.h

474

Why did this need to get defined?

[martin-luecke]

address comments

[martin-luecke]

Thank you for the comments @Mogball

I do not have commit priviledges, so if you are happy with the current state I would appreciate it if you could commit on my behalf.

mlir/lib/Conversion/PDLToPDLInterp/Predicate.h

474

The error I get without this is along the lines of

llvm-project/llvm/include/llvm/ADT/DenseMapInfo.h:267:44: error: ‘getHashValue’ is not a member of ‘llvm::DenseMapInfo<bool, void>’
  267 |         DenseMapInfo<EltType>::getHashValue(std::get<I>(values)),

i.e. the correct hash function for this key could not be found. I added this as a fix, similar to the other structs defined here that have a boolean as part of their key.

mlir/include/mlir/Dialect/PDL/IR/PDLOps.td

let description = [{
     Example:
 
     ```mlir
     // Apply `myConstraint` to the entities defined by `input`, `attr`, and `op`.
     pdl.apply_native_constraint "myConstraint"(%input, %attr, %op : !pdl.value, !pdl.attribute, !pdl.operation)
     ```
   }];
 
-  let arguments = (ins StrAttr:$name, Variadic<PDL_AnyType>:$args);
+  let arguments = (ins StrAttr:$name, 
+                       Variadic<PDL_AnyType>:$args, 
+                       DefaultValuedAttr<BoolAttr, "false">:$isNegated);
   let assemblyFormat = "$name `(` $args `:` type($args) `)` attr-dict";
   let hasVerifier = 1;
 }
 
 //===----------------------------------------------------------------------===//
 // pdl::ApplyNativeRewriteOp
 //===----------------------------------------------------------------------===//
 

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

 //===----------------------------------------------------------------------===//
 
 def PDLInterp_ApplyConstraintOp : PDLInterp_PredicateOp<"apply_constraint"> {
   let summary = "Apply a constraint to a set of positional values";
   let description = [{
     `pdl_interp.apply_constraint` operations apply a generic constraint, that
     has been registered with the interpreter, with a given set of positional
     values. On success, this operation branches to the true destination,
-    otherwise the false destination is taken.
+    otherwise the false destination is taken. This behavior can be reversed
+    by setting the attribute `isNegated` to true.
 
     Example:
 
     ```mlir
     // Apply `myConstraint` to the entities defined by `input`, `attr`, and
     // `op`.
     pdl_interp.apply_constraint "myConstraint"(%input, %attr, %op : !pdl.value, !pdl.attribute, !pdl.operation) -> ^matchDest, ^failureDest
     ```
   }];
 
-  let arguments = (ins StrAttr:$name, Variadic<PDL_AnyType>:$args);
+  let arguments = (ins StrAttr:$name, 
+                       Variadic<PDL_AnyType>:$args,
+                       DefaultValuedAttr<BoolAttr, "false">:$isNegated);
   let assemblyFormat = [{
     $name `(` $args `:` type($args) `)` attr-dict `->` successors
   }];
 }
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::ApplyRewriteOp
 //===----------------------------------------------------------------------===//

mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp

case Predicates::EqualToQuestion: {
     bool trueAnswer = isa<TrueAnswer>(answer);
     builder.create<pdl_interp::AreEqualOp>(loc, val, args.front(),
                                            trueAnswer ? success : failure,
                                            trueAnswer ? failure : success);
     break;
   }
   case Predicates::ConstraintQuestion: {
     auto *cstQuestion = cast<ConstraintQuestion>(question);
-    builder.create<pdl_interp::ApplyConstraintOp>(loc, cstQuestion->getName(),
-                                                  args, success, failure);
+    builder.create<pdl_interp::ApplyConstraintOp>(
+        loc, cstQuestion->getName(), args, cstQuestion->getIsNegated(), success,
+        failure);
     break;
   }
   default:
     llvm_unreachable("Generating unknown Predicate operation");
   }
 }
 
 template <typename OpT, typename PredT, typename ValT = typename PredT::KeyTy>

mlir/lib/Conversion/PDLToPDLInterp/Predicate.h

 /// Compare an `Attribute` to a constant value.
 struct AttributeQuestion
     : public PredicateBase<AttributeQuestion, Qualifier, void,
                            Predicates::AttributeQuestion> {};
 
 /// Apply a parameterized constraint to multiple position values.
 struct ConstraintQuestion
     : public PredicateBase<ConstraintQuestion, Qualifier,
-                           std::tuple<StringRef, ArrayRef<Position *>>,
+                           std::tuple<StringRef, ArrayRef<Position *>, bool>,
                            Predicates::ConstraintQuestion> {
   using Base::Base;
 
   /// Return the name of the constraint.
   StringRef getName() const { return std::get<0>(key); }
 
   /// Return the arguments of the constraint.
   ArrayRef<Position *> getArgs() const { return std::get<1>(key); }
 
+  /// Return the negation status of the constraint.
+  bool getIsNegated() const { return std::get<2>(key); }
+
   /// Construct an instance with the given storage allocator.
   static ConstraintQuestion *construct(StorageUniquer::StorageAllocator &alloc,
                                        KeyTy key) {
     return Base::construct(alloc, KeyTy{alloc.copyInto(std::get<0>(key)),
-                                        alloc.copyInto(std::get<1>(key))});
+                                        alloc.copyInto(std::get<1>(key)),
+                                        std::get<2>(key)});
+  }
+
+  /// Returns a hash suitable for the given keytype.
+  static llvm::hash_code hashKey(const KeyTy &key) {
+    return llvm::hash_value(key);
   }
 };
 
 /// Compare the equality of two values.
 struct EqualToQuestion
     : public PredicateBase<EqualToQuestion, Qualifier, Position *,
                            Predicates::EqualToQuestion> {
   using Base::Base;
public:
   }
 
   /// Create a predicate checking if two values are not equal.
   Predicate getNotEqualTo(Position *pos) {
     return {EqualToQuestion::get(uniquer, pos), FalseAnswer::get(uniquer)};
   }
 
   /// Create a predicate that applies a generic constraint.
-  Predicate getConstraint(StringRef name, ArrayRef<Position *> pos) {
-    return {ConstraintQuestion::get(uniquer, std::make_tuple(name, pos)),
-            TrueAnswer::get(uniquer)};
+  Predicate getConstraint(StringRef name, ArrayRef<Position *> pos,
+                          bool isNegated) {
+    return {
+        ConstraintQuestion::get(uniquer, std::make_tuple(name, pos, isNegated)),
   }
 
   /// Create a predicate comparing a value with null.
   Predicate getIsNotNull() {
     return {IsNotNullQuestion::get(uniquer), TrueAnswer::get(uniquer)};
   }
 
   /// Create a predicate comparing the number of operands of an operation to a

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp

static void getConstraintPredicates(pdl::ApplyNativeConstraintOp op,
   allPositions.reserve(arguments.size());
   for (Value arg : arguments)
     allPositions.push_back(inputs.lookup(arg));
 
   // Push the constraint to the furthest position.
   Position *pos = *std::max_element(allPositions.begin(), allPositions.end(),
                                     comparePosDepth);
   PredicateBuilder::Predicate pred =
-      builder.getConstraint(op.getName(), allPositions);
+      builder.getConstraint(op.getName(), allPositions, op.getIsNegated());
   predList.emplace_back(pos, pred);
 }
 
 static void getResultPredicates(pdl::ResultOp op,
                                 std::vector<PositionalPredicate> &predList,
                                 PredicateBuilder &builder,
                                 DenseMap<Value, Position *> &inputs) {
   Position *&resultPos = inputs[op];

mlir/test/Conversion/PDLToPDLInterp/pdl-to-pdl-interp-matcher.mlir

pdl.pattern : benefit(1) {
 
     pdl.apply_native_constraint "multi_constraint"(%input0, %input1, %result0 : !pdl.value, !pdl.value, !pdl.value)
     rewrite %root with "rewriter"
   }
 }
 
 // -----
 
+// CHECK-LABEL: module @negated_constraint
+module @negated_constraint {
+  // CHECK: func @matcher(%[[ROOT:.*]]: !pdl.operation)
+  // CHECK: pdl_interp.apply_constraint "constraint"(%[[ROOT]] : !pdl.operation) {isNegated = true}
+  // CHECK: pdl_interp.record_match @rewriters::@pdl_generated_rewriter(%[[ROOT]] : !pdl.operation)
+  pdl.pattern : benefit(1) {
+    %root = operation
+    pdl.apply_native_constraint "constraint"(%root : !pdl.operation) {isNegated = true}
+    rewrite %root with "rewriter"
+  }
+}
+
+// -----
+
 // CHECK-LABEL: module @inputs
 module @inputs {
   // CHECK: func @matcher(%[[ROOT:.*]]: !pdl.operation)
   // CHECK-DAG: pdl_interp.check_operand_count of %[[ROOT]] is 2
 
   // Get the input and check the type.
   // CHECK-DAG:   %[[INPUT:.*]] = pdl_interp.get_operand 0 of %[[ROOT]]
   // CHECK-DAG:   pdl_interp.is_not_null %[[INPUT]] : !pdl.value