[MLIR] Fix pattern benefit sorting between operation specific and operation agnostic patterns.

[Hardcode84]

Summary

Previously low benefit op-specific patterns never had a chance to match
even if high benefit op-agnostic pattern failed to match.

[rriddle]

mlir/unittests/Rewrite/PatternBenefit.cpp

64

Can you test PatternApplicator directly instead of testing a user of it? That would also remove the need to create a function above.

[Hardcode84]

Use PatternApplicator directly instead of applyPatternsAndFoldGreedely

[rriddle]

LGTM

mlir/unittests/Rewrite/PatternBenefit.cpp

22

Can you add a couple of general comments in this test?

[Hardcode84]

Added comment to test

[Hardcode84]

I don't have commit access, can you please merge this

[mehdi_amini]

Can you rebase? There have been some changes recently in there.

[Hardcode84]

It seems this was already fixed upstream, only test remained

[mehdi_amini]

OK! I'll land this later today, but feel free to ask for commit access: https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access

(If you get access before I land this, feel free to land it yourself!)

mlir/lib/Rewrite/PatternApplicator.cpp

LogicalResult PatternApplicator::matchAndRewrite(
   auto anyIt = anyOpPatterns.begin(), anyE = anyOpPatterns.end();
   auto pdlIt = pdlMatches.begin(), pdlE = pdlMatches.end();
   while (true) {
     // Find the next pattern with the highest benefit.
     const Pattern *bestPattern = nullptr;
     const PDLByteCode::MatchResult *pdlMatch = nullptr;
     /// Operation specific patterns.
     if (opIt != opE)
-      bestPattern = *(opIt++);
+      bestPattern = *opIt;
     /// Operation agnostic patterns.
     if (anyIt != anyE &&
         (!bestPattern || bestPattern->getBenefit() < (*anyIt)->getBenefit()))
-      bestPattern = *(anyIt++);
+      bestPattern = *anyIt;
     /// PDL patterns.
     if (pdlIt != pdlE &&
         (!bestPattern || bestPattern->getBenefit() < pdlIt->benefit)) {
       pdlMatch = pdlIt;
-      bestPattern = (pdlIt++)->pattern;
+      bestPattern = pdlIt->pattern;
     }
     if (!bestPattern)
       break;
 
+    if (opIt != opE && bestPattern == *opIt)
+      opIt++;
+    else if (anyIt != anyE && bestPattern == *anyIt)
+      anyIt++;
+    else if (pdlIt != pdlE && bestPattern == pdlIt->pattern)
+      pdlIt++;
+
     // Check that the pattern can be applied.
     if (canApply && !canApply(*bestPattern))
       continue;
 
     // Try to match and rewrite this pattern. The patterns are sorted by
     // benefit, so if we match we can immediately rewrite. For PDL patterns, the
     // match has already been performed, we just need to rewrite.
     rewriter.setInsertionPoint(op);

mlir/unittests/CMakeLists.txt

 set_target_properties(MLIRUnitTests PROPERTIES FOLDER "MLIR Tests")
 
 function(add_mlir_unittest test_dirname)
   add_unittest(MLIRUnitTests ${test_dirname} ${ARGN})
 endfunction()
 
 add_subdirectory(Analysis)
 add_subdirectory(Dialect)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(Interfaces)
 add_subdirectory(IR)
 add_subdirectory(Pass)
+add_subdirectory(Rewrite)
 add_subdirectory(SDBM)
 add_subdirectory(TableGen)

mlir/unittests/Rewrite/CMakeLists.txt

+add_mlir_unittest(MLIRRewriteTests
+  PatternBenefit.cpp
+)
+target_link_libraries(MLIRRewriteTests
+  PRIVATE
+  MLIRRewrite
+  MLIRTransformUtils)

mlir/unittests/Rewrite/PatternBenefit.cpp

+//===- PatternBenefit.cpp - RewritePattern benefit unit tests -------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/IR/PatternMatch.h"
+#include "mlir/Rewrite/PatternApplicator.h"
+#include "gtest/gtest.h"
+
+using namespace mlir;
+
+namespace {
+TEST(PatternBenefitTest, BenefitOrder) {
+  MLIRContext context;
+
+  OpBuilder builder(&context);
+  auto module = ModuleOp::create(builder.getUnknownLoc());
+
+  struct Pattern1 : public OpRewritePattern<ModuleOp> {
+    Pattern1(mlir::MLIRContext *context, bool *called)
+        : OpRewritePattern<ModuleOp>(context, /*benefit*/ 1), called(called) {}
+
+    mlir::LogicalResult
+    matchAndRewrite(ModuleOp /*op*/,
+                    mlir::PatternRewriter & /*rewriter*/) const override {
+      *called = true;
+      return failure();
+    }
+
+  private:
+    bool *called;
+  };
+
+  struct Pattern2 : public RewritePattern {
+    Pattern2(bool *called)
+        : RewritePattern(/*benefit*/ 2, MatchAnyOpTypeTag{}), called(called) {}
+
+    mlir::LogicalResult
+    matchAndRewrite(Operation * /*op*/,
+                    mlir::PatternRewriter & /*rewriter*/) const override {
+      *called = true;
+      return failure();
+    }
+
+  private:
+    bool *called;
+  };
+
+  OwningRewritePatternList patterns;
+
+  bool called1 = false;
+  bool called2 = false;
+
+  patterns.insert<Pattern1>(&context, &called1);
+  patterns.insert<Pattern2>(&called2);
+
+  FrozenRewritePatternList frozenPatterns(std::move(patterns));
+  PatternApplicator pa(frozenPatterns);
+  pa.applyDefaultCostModel();
+
+  class MyPatternRewriter : public PatternRewriter {
+  public:
+    MyPatternRewriter(MLIRContext *ctx) : PatternRewriter(ctx) {}
+  };
+
+  MyPatternRewriter rewriter(&context);
+  (void)pa.matchAndRewrite(module, rewriter);
+
+  EXPECT_TRUE(called1);
+  EXPECT_TRUE(called2);
+}
+} // namespace