Index: mlir/lib/Rewrite/ByteCode.cpp
===================================================================
--- mlir/lib/Rewrite/ByteCode.cpp
+++ mlir/lib/Rewrite/ByteCode.cpp
@@ -773,6 +773,7 @@
          "expected index for constraint function");
   writer.append(OpCode::ApplyConstraint, constraintToMemIndex[op.getName()]);
   writer.appendPDLValueList(op.getArgs());
+  writer.append(ByteCodeField(op.getIsNegated()));
   writer.append(op.getSuccessors());
 }
 void Generator::generate(pdl_interp::ApplyRewriteOp op,
@@ -1413,10 +1414,16 @@
   LLVM_DEBUG({
     llvm::dbgs() << "  * Arguments: ";
     llvm::interleaveComma(args, llvm::dbgs());
+    llvm::dbgs() << "\n";
   });
 
+  ByteCodeField isNegated = read();
+  LLVM_DEBUG({
+    llvm::dbgs() << "  * isNegated: " << isNegated << "\n";
+    llvm::interleaveComma(args, llvm::dbgs());
+  });
   // Invoke the constraint and jump to the proper destination.
-  selectJump(succeeded(constraintFn(rewriter, args)));
+  selectJump(isNegated != succeeded(constraintFn(rewriter, args)));
 }
 
 LogicalResult ByteCodeExecutor::executeApplyRewrite(PatternRewriter &rewriter) {
Index: mlir/test/Rewrite/pdl-bytecode.mlir
===================================================================
--- mlir/test/Rewrite/pdl-bytecode.mlir
+++ mlir/test/Rewrite/pdl-bytecode.mlir
@@ -72,6 +72,44 @@
 
 // -----
 
+// Test support for negated constraints.
+module @patterns {
+  pdl_interp.func @matcher(%root : !pdl.operation) {
+    %test_attr = pdl_interp.create_attribute unit
+    %attr = pdl_interp.get_attribute "test_attr" of %root
+    pdl_interp.are_equal %test_attr, %attr : !pdl.attribute -> ^pat, ^end
+
+  ^pat:
+    pdl_interp.apply_constraint "single_entity_constraint"(%root : !pdl.operation) {isNegated = true} -> ^pat1, ^end
+
+  ^pat1:
+    pdl_interp.record_match @rewriters::@success(%root : !pdl.operation) : benefit(1), loc([%root]) -> ^end
+
+  ^end:
+    pdl_interp.finalize
+  }
+
+  module @rewriters {
+    pdl_interp.func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.replaced_by_pattern"
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.apply_constraint_3
+// CHECK-NEXT: "test.replaced_by_pattern"
+// CHECK-NOT: "test.replaced_by_pattern"
+
+module @ir attributes { test.apply_constraint_3 } {
+  "test.foo"() { test_attr } : () -> ()
+  "test.op"() { test_attr } : () -> ()
+}
+
+// -----
+
+
 //===----------------------------------------------------------------------===//
 // pdl_interp::ApplyRewriteOp
 //===----------------------------------------------------------------------===//