[mlir][pdl] Fix bug when ordering predicates

[rriddle]

Summary

We should be ordering predicates with higher primary/secondary sums first, but we are currently ordering them last. This allows for predicates more frequently encountered to be checked first.

[jpienaar]

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

152

both ? This reads like a generic statement while I believe it is a specific one related to this test

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp

struct OrderedPredicate {
   /// for favoring predicates that are more commonly shared within a pattern, as
   /// opposed to those shared across patterns.
   unsigned secondary = 0;
 
   /// A map between a pattern operation and the answer to the predicate question
   /// within that pattern.
   DenseMap<Operation *, Qualifier *> patternToAnswer;
 
-  /// Returns true if this predicate is ordered before `other`, based on the
-  /// cost model.
-  bool operator<(const OrderedPredicate &other) const {
+  /// Returns true if this predicate is ordered before `rhs`, based on the cost
+  /// model.
+  bool operator<(const OrderedPredicate &rhs) const {
     // Sort by:
-    // * first and secondary order sums
+    // * higher first and secondary order sums
     // * lower depth
-    // * position dependency
-    // * predicate dependency.
-    auto *otherPos = other.position;
-    return std::make_tuple(other.primary, other.secondary,
-                           otherPos->getIndex().size(), otherPos->getKind(),
-                           other.question->getKind()) >
-           std::make_tuple(primary, secondary, position->getIndex().size(),
-                           position->getKind(), question->getKind());
+    // * lower position dependency
+    // * lower predicate dependency
+    auto *rhsPos = rhs.position;
+    return std::make_tuple(primary, secondary, rhsPos->getIndex().size(),
+                           rhsPos->getKind(), rhs.question->getKind()) >
+           std::make_tuple(rhs.primary, rhs.secondary,
+                           position->getIndex().size(), position->getKind(),
+                           question->getKind());
   }
 };
 
 /// A DenseMapInfo for OrderedPredicate based solely on the position and
 /// question.
 struct OrderedPredicateDenseInfo {
   using Base = DenseMapInfo<std::pair<Position *, Qualifier *>>;
 

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

pdl.pattern : benefit(1) {
     pdl.rewrite %root with "rewriter"
   }
   pdl.pattern : benefit(1) {
     %type = pdl.type : i64
     %root, %result = pdl.operation -> %type
     pdl.rewrite %root with "rewriter"
   }
 }
+
+// -----
+
+// CHECK-LABEL: module @predicate_ordering
+module @predicate_ordering  {
+  // Check that the result is checked for null first, before applying the
+  // constraint. The null check is prevalent in both patterns, so should be
+  // prioritized first.
+
+  // CHECK: func @matcher(%[[ROOT:.*]]: !pdl.operation)
+  // CHECK:   %[[RESULT:.*]] = pdl_interp.get_result 0 of %[[ROOT]]
+  // CHECK-NEXT: pdl_interp.is_not_null %[[RESULT]]
+  // CHECK:   %[[RESULT_TYPE:.*]] = pdl_interp.get_value_type of %[[RESULT]]
+  // CHECK: pdl_interp.apply_constraint "typeConstraint" [](%[[RESULT_TYPE]]
+
+  pdl.pattern : benefit(1) {
+    %resultType = pdl.type
+    pdl.apply_constraint "typeConstraint"[](%resultType : !pdl.type)
+    %root, %result = pdl.operation -> %resultType
+    pdl.rewrite %root with "rewriter"
+  }
+
+  pdl.pattern : benefit(1) {
+    %resultType = pdl.type
+    %apply, %applyRes = pdl.operation -> %resultType
+    pdl.rewrite %apply with "rewriter"
+  }
+}