[MLIR][PDL] Make predicate order deterministic.

[sfuniak]

Summary

The tree merging of pattern predicates places the predicates in an unordered set. When the predicates are sorted, they are taken in the set order, not the insertion order. This results in nondeterministic behavior.

One solution to this problem would be to use SetVector. However, the value SetVector does not provide a find function for fast O(1) lookups and stores the predicates twice -- once in the set and once in the vector, which is undesirable, because we store patternToAnswer in each predicate. A simpler solution is to store the tie breaking ID (which follows the insertion order), and use this ID to break any ties when comparing predicates.

[Mogball]

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp

913

Nit: can we make the IDs start from 0?

[sfuniak]

Changed to 0-based indexing of the insertion order.

[sfuniak]

Rebased.

mlir/lib/Conversion/PDLToPDLInterp/PredicateTree.cpp

struct OrderedPredicate {
   /// of the patterns.
   unsigned primary = 0;
   /// The secondary sum is a squared summation of the primary sum of all of the
   /// predicates within each pattern that contains this predicate. This allows
   /// for favoring predicates that are more commonly shared within a pattern, as
   /// opposed to those shared across patterns.
   unsigned secondary = 0;
 
+  /// The tie breaking ID, used to preserve a deterministic (insertion) order
+  /// among all the predicates with the same priority, depth, and position /
+  /// predicate dependency.
+  unsigned id = 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 `rhs`, based on the cost
   /// model.
   bool operator<(const OrderedPredicate &rhs) const {
     // Sort by:
     // * higher first and secondary order sums
     // * lower depth
     // * lower position dependency
     // * lower predicate dependency
+    // * lower tie breaking ID
     auto *rhsPos = rhs.position;
     return std::make_tuple(primary, secondary, rhsPos->getOperationDepth(),
-                           rhsPos->getKind(), rhs.question->getKind()) >
+                           rhsPos->getKind(), rhs.question->getKind(), rhs.id) >
            std::make_tuple(rhs.primary, rhs.secondary,
                            position->getOperationDepth(), position->getKind(),
-                           question->getKind());
+                           question->getKind(), id);
   }
 };
 
 /// A DenseMapInfo for OrderedPredicate based solely on the position and
 /// question.
 struct OrderedPredicateDenseInfo {
   using Base = DenseMapInfo<std::pair<Position *, Qualifier *>>;
 
MatcherNode::generateMatcherTree(ModuleOp module, PredicateBuilder &builder,
 
   // Associate a pattern result with each unique predicate.
   DenseSet<OrderedPredicate, OrderedPredicateDenseInfo> uniqued;
   for (auto &patternAndPredList : patternsAndPredicates) {
     for (auto &predicate : patternAndPredList.predicates) {
       auto it = uniqued.insert(predicate);
       it.first->patternToAnswer.try_emplace(patternAndPredList.pattern,
                                             predicate.answer);
+      // Mark the insertion order.
+      if (it.second)
+        it.first->id = uniqued.size();
     }
   }
 
   // Associate each pattern to a set of its ordered predicates for later lookup.
   std::vector<OrderedPredicateList> lists;
   lists.reserve(patternsAndPredicates.size());
   for (auto &patternAndPredList : patternsAndPredicates) {
     OrderedPredicateList list(patternAndPredList.pattern,
MatcherNode::generateMatcherTree(ModuleOp module, PredicateBuilder &builder,
   }
 
   // Sort the set of predicates now that the cost primary and secondary sums
   // have been computed.
   std::vector<OrderedPredicate *> ordered;
   ordered.reserve(uniqued.size());
   for (auto &ip : uniqued)
     ordered.push_back(&ip);
-  std::stable_sort(
-      ordered.begin(), ordered.end(),
-      [](OrderedPredicate *lhs, OrderedPredicate *rhs) { return *lhs < *rhs; });
+  llvm::sort(ordered, [](OrderedPredicate *lhs, OrderedPredicate *rhs) {
+    return *lhs < *rhs;
+  });
 
   // Build the matchers for each of the pattern predicate lists.
   std::unique_ptr<MatcherNode> root;
   for (OrderedPredicateList &list : lists)
     propagatePattern(root, list, ordered.begin(), ordered.end());
 
   // Collapse the graph and insert the exit node.
   foldSwitchToBool(root);