[MLIR][PDL] Execute nondeterministic bytecode & lower some PDLInterp ops

[srishti-pm]

Summary

1. This commit first adds a stack of bytecode positions within the

ByteCodeExecutor. This is needed because in pdl_interp.choose_range,
we iterate over a range of operands/values from a list of permutations
returned by pdl_interp.get_permutations until we reach finalize. When
we reach finalize, we need to return back to the position marked in the
stack.

2. Then a functionality to extend the lifetime of values that cross the

nondeterministic choice is added. The existing bytecode generator
allocates the values to memory positions by representing the liveness of
values as a collection of disjoint intervals over the matcher positions.
This is akin to register allocation, and substantially reduces the
footprint of the bytecode executor. However, because with
nondeterministic op pdl_interp.choose_range, execution "returns" back,
so any values whose original liveness cross the nondeterminstic choice
must have their lifetime executed until finalize.

3. Then, lowerings of pdl_interp.choose_range, pdl_interp.get_item,

pdl_interp.get_permutations, and pdl_interp.is_commutative ops to
bytecode is added.

Co-authors: Srishti Srivastava, Stanislav Funiak, Prateek Gupta

Signed-off-by: Srishti Srivastava <[e-mail]>

[sfuniak]

As I mentioned in the previous diff on this stack, instead of implementing a new op ChooseRange, you should generalize ForEach. Also, GetItem is a duplicate of Extract.

As a side note: is there going to be one more diff stacked on top of this one that implements the lowering of commutative pdl.operations?

mlir/lib/Rewrite/ByteCode.cpp

663–686

Now that ForEach is implemented with subregions, extending the lifetime should not be needed.

777–824

Deprecated code; delete.

mlir/lib/Rewrite/ByteCode.h

91–95

The range-of-ranges use case seems parallel to operation ranges above. Now that pdl_interp.foreach does not mutate the range (of operations/ranges) it iterates over, can we replace

std::vector<RangeRange> rangeRangeMemory;
std::vector<llvm::OwningArrayRef<ValueRange>> allocatedRangeRangeMemory;

with

using OwningRangeRange = llvm::OwningArrayRef<ValueRange>;
...
std::vector<OwningRangeRange> rangeRangeMemory;

?

[Mogball]

mlir/lib/Rewrite/ByteCode.cpp

1988

There needs to be a limit on the number of operands allowed to be commutative.

[srishti-pm]

In D118689#3293202, @sfuniak wrote:

As a side note: is there going to be one more diff stacked on top of this one that implements the lowering of commutative pdl.operations?

Yes, I intended to do that. But, I think I will add that after I am able to complete this lowering. What are your views about this?

[srishti-pm]

mlir/lib/Rewrite/ByteCode.cpp

663–686

Oh okay. I'll do that, thanks!

1988

Okay, what would you want to happen if that limit is exceeded? Should the op not be treated as commutative?

mlir/lib/Rewrite/ByteCode.h

91–95

Sure. But how do we define allocatedRangeRangeMemory in that case?

[srishti-pm]

This change is obsolete now, based on our concluding remark here: https://discourse.llvm.org/t/mlir-pdl-extending-pdl-pdlinterp-bytecode-to-enable-commutative-matching/60798/19 and my new solution here: https://reviews.llvm.org/D124750.

mlir/lib/Dialect/PDL/IR/PDLTypes.cpp

 void RangeType::print(AsmPrinter &printer) const {
   printer << "<";
   (void)generatedTypePrinter(getElementType(), printer);
   printer << ">";
 }
 
 LogicalResult RangeType::verify(function_ref<InFlightDiagnostic()> emitError,
                                 Type elementType) {
-  if (!elementType.isa<PDLType>() || elementType.isa<RangeType>()) {
+  if (!elementType.isa<PDLType>()) {
     return emitError()
            << "expected element of pdl.range to be one of [!pdl.attribute, "
-              "!pdl.operation, !pdl.type, !pdl.value], but got "
+              "!pdl.operation, !pdl.type, !pdl.value, !pdl.range], but got "
            << elementType;
   }
   return success();
 }

mlir/lib/Rewrite/ByteCode.h

 namespace detail {
 class PDLByteCode;
 
 /// Use generic bytecode types. ByteCodeField refers to the actual bytecode
 /// entries. ByteCodeAddr refers to size of indices into the bytecode.
 using ByteCodeField = uint16_t;
 using ByteCodeAddr = uint32_t;
 using OwningOpRange = llvm::OwningArrayRef<Operation *>;
+using RangeRange = llvm::ArrayRef<ValueRange>;
 
 //===----------------------------------------------------------------------===//
 // PDLByteCodePattern
 //===----------------------------------------------------------------------===//
 
 /// All of the data pertaining to a specific pattern within the bytecode.
 class PDLByteCodePattern : public Pattern {
 public:
private:
 
   /// A mutable block of memory used during the matching and rewriting phase of
   /// the bytecode to store ranges of operations. These are always stored by
   /// owning references, because at no point in the execution of the byte code
   /// we get an indexed range (view) of operations.
   std::vector<OwningOpRange> opRangeMemory;
 
   /// A mutable block of memory used during the matching and rewriting phase of
+  /// the bytecode to store ranges of value range.
+  std::vector<RangeRange> rangeRangeMemory;
+  /// A set of value range ranges that have been allocated by the byte code
+  /// interpreter to provide a guaranteed lifetime.
+  std::vector<llvm::OwningArrayRef<ValueRange>> allocatedRangeRangeMemory;
+
+  /// A mutable block of memory used during the matching and rewriting phase of
   /// the bytecode to store ranges of types.
   std::vector<TypeRange> typeRangeMemory;
   /// A set of type ranges that have been allocated by the byte code interpreter
   /// to provide a guaranteed lifetime.
   std::vector<llvm::OwningArrayRef<Type>> allocatedTypeRangeMemory;
 
   /// A mutable block of memory used during the matching and rewriting phase of
   /// the bytecode to store ranges of values.
private:
   std::vector<PDLConstraintFunction> constraintFunctions;
   std::vector<PDLRewriteFunction> rewriteFunctions;
 
   /// The maximum memory index used by a value.
   ByteCodeField maxValueMemoryIndex = 0;
 
   /// The maximum number of different types of ranges.
   ByteCodeField maxOpRangeCount = 0;
+  ByteCodeField maxRangeRangeCount = 0;
   ByteCodeField maxTypeRangeCount = 0;
   ByteCodeField maxValueRangeCount = 0;
 
   /// The maximum number of nested loops.
   ByteCodeField maxLoopLevel = 0;
 };
 
 } // namespace detail
 } // namespace mlir
 
 #endif // MLIR_REWRITE_BYTECODE_H_

mlir/lib/Rewrite/ByteCode.cpp

void PDLByteCodeMutableState::updatePatternBenefit(unsigned patternIndex,
                                                    PatternBenefit benefit) {
   currentPatternBenefits[patternIndex] = benefit;
 }
 
 /// Cleanup any allocated state after a full match/rewrite has been completed.
 /// This method should be called irregardless of whether the match+rewrite was a
 /// success or not.
 void PDLByteCodeMutableState::cleanupAfterMatchAndRewrite() {
+  allocatedRangeRangeMemory.clear();
   allocatedTypeRangeMemory.clear();
   allocatedValueRangeMemory.clear();
 }
 
 //===----------------------------------------------------------------------===//
 // Bytecode OpCodes
 //===----------------------------------------------------------------------===//
 
enum OpCode : ByteCodeField {
   /// Compare the operand count of an operation with a constant.
   CheckOperandCount,
   /// Compare the name of an operation with a constant.
   CheckOperationName,
   /// Compare the result count of an operation with a constant.
   CheckResultCount,
   /// Compare a range of types to a constant range of types.
   CheckTypes,
+  /// Performs a nondeterministic choice over a range of orderings.
+  ChooseRange,
   /// Continue to the next iteration of a loop.
   Continue,
   /// Create an operation.
   CreateOperation,
   /// Create a range of types.
   CreateTypes,
   /// Erase an operation.
   EraseOp,
   /// Extract the op from a range at the specified index.
   ExtractOp,
   /// Extract the type from a range at the specified index.
   ExtractType,
   /// Extract the value from a range at the specified index.
   ExtractValue,
   /// Terminate a matcher or rewrite sequence.
   Finalize,
   /// Iterate over a range of values.
   ForEach,
   /// Get a specific attribute of an operation.
   GetAttribute,
   /// Get the type of an attribute.
   GetAttributeType,
   /// Get the defining operation of a value.
   GetDefiningOp,
+  /// Get a specific value from a list of values.
+  GetItem,
   /// Get a specific operand of an operation.
   GetOperand0,
   GetOperand1,
   GetOperand2,
   GetOperand3,
   GetOperandN,
   /// Get a specific operand group of an operation.
   GetOperands,
+  /// Get a permutation of a list of values.
+  GetPermutations,
   /// Get a specific result of an operation.
   GetResult0,
   GetResult1,
   GetResult2,
   GetResult3,
   GetResultN,
   /// Get a specific result group of an operation.
   GetResults,
   /// Get the users of a value or a range of values.
   GetUsers,
   /// Get the type of a value.
   GetValueType,
   /// Get the types of a value range.
   GetValueRangeTypes,
+  /// Check if a given operation is commutative.
+  IsCommutative,
   /// Check if a generic value is not null.
   IsNotNull,
   /// Record a successful pattern match.
   RecordMatch,
   /// Replace an operation.
   ReplaceOp,
   /// Compare an attribute with a set of constants.
   SwitchAttribute,

 class Generator {
 public:
   Generator(MLIRContext *ctx, std::vector<const void *> &uniquedData,
             SmallVectorImpl<ByteCodeField> &matcherByteCode,
             SmallVectorImpl<ByteCodeField> &rewriterByteCode,
             SmallVectorImpl<PDLByteCodePattern> &patterns,
             ByteCodeField &maxValueMemoryIndex,
             ByteCodeField &maxOpRangeMemoryIndex,
+            ByteCodeField &maxRangeRangeMemoryIndex,
             ByteCodeField &maxTypeRangeMemoryIndex,
             ByteCodeField &maxValueRangeMemoryIndex,
             ByteCodeField &maxLoopLevel,
             llvm::StringMap<PDLConstraintFunction> &constraintFns,
             llvm::StringMap<PDLRewriteFunction> &rewriteFns)
       : ctx(ctx), uniquedData(uniquedData), matcherByteCode(matcherByteCode),
         rewriterByteCode(rewriterByteCode), patterns(patterns),
         maxValueMemoryIndex(maxValueMemoryIndex),
         maxOpRangeMemoryIndex(maxOpRangeMemoryIndex),
+        maxRangeRangeMemoryIndex(maxRangeRangeMemoryIndex),
         maxTypeRangeMemoryIndex(maxTypeRangeMemoryIndex),
         maxValueRangeMemoryIndex(maxValueRangeMemoryIndex),
         maxLoopLevel(maxLoopLevel) {
     for (const auto &it : llvm::enumerate(constraintFns))
       constraintToMemIndex.try_emplace(it.value().first(), it.index());
     for (const auto &it : llvm::enumerate(rewriteFns))
       externalRewriterToMemIndex.try_emplace(it.value().first(), it.index());
   }
getMemIndex(T val) {
     return it.first->second;
   }
 
 private:
   /// Allocate memory indices for the results of operations within the matcher
   /// and rewriters.
   void allocateMemoryIndices(FuncOp matcherFunc, ModuleOp rewriterModule);
 
+  /// Extend the lifetime of a value to its block and block descendants.
+  void extendLifetime(ByteCodeLiveRange &range, Value value);
+  void extendLifetime(ByteCodeLiveRange &range, Block *block,
+                      DenseSet<Block *> &visited);
+
   /// Generate the bytecode for the given operation.
   void generate(Region *region, ByteCodeWriter &writer);
   void generate(Operation *op, ByteCodeWriter &writer);
   void generate(pdl_interp::ApplyConstraintOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::ApplyRewriteOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::AreEqualOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::BranchOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CheckAttributeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CheckOperandCountOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CheckOperationNameOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CheckResultCountOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CheckTypeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CheckTypesOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::ChooseRangeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::ContinueOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CreateAttributeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CreateOperationOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CreateTypeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CreateTypesOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::EraseOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::ExtractOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::FinalizeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::ForEachOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetAttributeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetAttributeTypeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetDefiningOpOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetItemOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetOperandOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetOperandsOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::GetPermutationsOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetResultOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetResultsOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetUsersOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::GetValueTypeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::InferredTypesOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::IsCommutativeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::IsNotNullOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::RecordMatchOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::ReplaceOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::SwitchAttributeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::SwitchTypeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::SwitchTypesOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::SwitchOperandCountOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::SwitchOperationNameOp op, ByteCodeWriter &writer);
private:
   DenseMap<const void *, ByteCodeField> uniquedDataToMemIndex;
 
   /// The current level of the foreach loop.
   ByteCodeField curLoopLevel = 0;
 
   /// The current MLIR context.
   MLIRContext *ctx;
 
+  /// Mapping from operation to its first and last indices.
+  DenseMap<Operation *, unsigned> opToFirstIndex;
+  DenseMap<Operation *, unsigned> opToLastIndex;
+
   /// Mapping from block to its address.
   DenseMap<Block *, ByteCodeAddr> blockToAddr;
 
   /// Data of the ByteCode class to be populated.
   std::vector<const void *> &uniquedData;
   SmallVectorImpl<ByteCodeField> &matcherByteCode;
   SmallVectorImpl<ByteCodeField> &rewriterByteCode;
   SmallVectorImpl<PDLByteCodePattern> &patterns;
   ByteCodeField &maxValueMemoryIndex;
   ByteCodeField &maxOpRangeMemoryIndex;
+  ByteCodeField &maxRangeRangeMemoryIndex;
   ByteCodeField &maxTypeRangeMemoryIndex;
   ByteCodeField &maxValueRangeMemoryIndex;
   ByteCodeField &maxLoopLevel;
 };
 
 /// This class provides utilities for writing a bytecode stream.
 struct ByteCodeWriter {
   ByteCodeWriter(SmallVectorImpl<ByteCodeField> &bytecode, Generator &generator)
struct ByteCodeLiveRange {
   /// We use std::unique_ptr here, because IntervalMap does not provide a
   /// correct copy or move constructor. We can eliminate the pointer once
   /// https://reviews.llvm.org/D113240 lands.
   std::unique_ptr<llvm::IntervalMap<uint64_t, char, 16>> liveness;
 
   /// The operation range storage index for this range.
   Optional<unsigned> opRangeIndex;
 
+  /// The range range storage index for this range.
+  Optional<unsigned> rangeRangeIndex;
+
   /// The type range storage index for this range.
   Optional<unsigned> typeRangeIndex;
 
   /// The value range storage index for this range.
   Optional<unsigned> valueRangeIndex;
 };
 } // namespace
 
void Generator::allocateMemoryIndices(FuncOp matcherFunc,
   }
 
   // The matcher function uses a more sophisticated numbering that tries to
   // minimize the number of memory indices assigned. This is done by determining
   // a live range of the values within the matcher, then the allocation is just
   // finding the minimal number of overlapping live ranges. This is essentially
   // a simplified form of register allocation where we don't necessarily have a
   // limited number of registers, but we still want to minimize the number used.
-  DenseMap<Operation *, unsigned> opToFirstIndex;
-  DenseMap<Operation *, unsigned> opToLastIndex;
 
   // A custom walk that marks the first and the last index of each operation.
   // The entry marks the beginning of the liveness range for this operation,
   // followed by nested operations, followed by the end of the liveness range.
   unsigned index = 0;
+  SmallVector<std::pair<Operation *, unsigned>> nondeterministicIndices;
   llvm::unique_function<void(Operation *)> walk = [&](Operation *op) {
+    // Extract the indices of nondeterministic operations.
+    if (isa<pdl_interp::ChooseRangeOp>(op))
+      nondeterministicIndices.emplace_back(op, index);
     opToFirstIndex.try_emplace(op, index++);
     for (Region &region : op->getRegions())
       for (Block &block : region.getBlocks())
         for (Operation &nested : block)
           walk(&nested);
     opToLastIndex.try_emplace(op, index++);
   };
   walk(matcherFunc);
auto processValue = [&](Value value, Operation *firstUseOrDef) {
           opToLastIndex[info->getEndOperation(value, firstUseOrDef)],
           /*dummyValue*/ 0);
 
       // Check to see if this value is a range type.
       if (auto rangeTy = value.getType().dyn_cast<pdl::RangeType>()) {
         Type eleType = rangeTy.getElementType();
         if (eleType.isa<pdl::OperationType>())
           defRangeIt->second.opRangeIndex = 0;
+        else if (eleType.isa<pdl::RangeType>())
+          defRangeIt->second.rangeRangeIndex = 0;
         else if (eleType.isa<pdl::TypeType>())
           defRangeIt->second.typeRangeIndex = 0;
         else if (eleType.isa<pdl::ValueType>())
           defRangeIt->second.valueRangeIndex = 0;
       }
     };
 
     // Process the live-ins of this block.
matcherFunc->walk([&](Block *block) {
     }
 
     // Process any new defs within this block.
     for (Operation &op : *block)
       for (Value result : op.getResults())
         processValue(result, &op);
   });
 
+  // For the values that are alive at the time a nondeterministic operation is
+  // performed, extend their lifetime until the end.
+  bool first = true;
+  for (auto &valueDefRange : valueDefRanges) {
+    Value value = valueDefRange.first;
+    ByteCodeLiveRange &range = valueDefRange.second;
+    unsigned valueIndex = opToFirstIndex[value.getDefiningOp()];
+    for (auto p : nondeterministicIndices) {
+      Operation *op = p.first;
+      unsigned index = p.second;
+      if (index != valueIndex && range.liveness->overlaps(index, index)) {
+        if (first) {
+          LLVM_DEBUG(llvm::dbgs() << "Extending lifetime:\n");
+          first = false;
+        }
+        LLVM_DEBUG(llvm::dbgs()
+                   << "  * Value: " << valueIndex << " " << value
+                   << "\n    * Overlaps: " << index << " " << *op << "\n");
+        extendLifetime(range, value);
+        break;
+      }
+    }
+  }
+
   // Greedily allocate memory slots using the computed def live ranges.
   std::vector<ByteCodeLiveRange> allocatedIndices;
 
   // The number of memory indices currently allocated (and its next value).
   // Recall that the root gets allocated memory index 0.
   ByteCodeField numIndices = 1;
 
   // The number of memory ranges of various types (and their next values).
-  ByteCodeField numOpRanges = 0, numTypeRanges = 0, numValueRanges = 0;
+  ByteCodeField numOpRanges = 0, numRangeRanges = 0, numTypeRanges = 0,
+                numValueRanges = 0;
 
   for (auto &defIt : valueDefRanges) {
     ByteCodeField &memIndex = valueToMemIndex[defIt.first];
     ByteCodeLiveRange &defRange = defIt.second;
 
     // Try to allocate to an existing index.
     for (const auto &existingIndexIt : llvm::enumerate(allocatedIndices)) {
       ByteCodeLiveRange &existingRange = existingIndexIt.value();
       if (!defRange.overlaps(existingRange)) {
         existingRange.unionWith(defRange);
         memIndex = existingIndexIt.index() + 1;
 
         if (defRange.opRangeIndex) {
           if (!existingRange.opRangeIndex)
             existingRange.opRangeIndex = numOpRanges++;
           valueToRangeIndex[defIt.first] = *existingRange.opRangeIndex;
+        } else if (defRange.rangeRangeIndex) {
+          if (!existingRange.rangeRangeIndex)
+            existingRange.rangeRangeIndex = numRangeRanges++;
+          valueToRangeIndex[defIt.first] = *existingRange.rangeRangeIndex;
         } else if (defRange.typeRangeIndex) {
           if (!existingRange.typeRangeIndex)
             existingRange.typeRangeIndex = numTypeRanges++;
           valueToRangeIndex[defIt.first] = *existingRange.typeRangeIndex;
         } else if (defRange.valueRangeIndex) {
           if (!existingRange.valueRangeIndex)
             existingRange.valueRangeIndex = numValueRanges++;
           valueToRangeIndex[defIt.first] = *existingRange.valueRangeIndex;
         }
         break;
       }
     }
 
     // If no existing index could be used, add a new one.
     if (memIndex == 0) {
       allocatedIndices.emplace_back(allocator);
       ByteCodeLiveRange &newRange = allocatedIndices.back();
       newRange.unionWith(defRange);
 
-      // Allocate an index for op/type/value ranges.
+      // Allocate an index for op/value range/type/value ranges.
       if (defRange.opRangeIndex) {
         newRange.opRangeIndex = numOpRanges;
         valueToRangeIndex[defIt.first] = numOpRanges++;
+      } else if (defRange.rangeRangeIndex) {
+        newRange.rangeRangeIndex = numRangeRanges;
+        valueToRangeIndex[defIt.first] = numRangeRanges++;
       } else if (defRange.typeRangeIndex) {
         newRange.typeRangeIndex = numTypeRanges;
         valueToRangeIndex[defIt.first] = numTypeRanges++;
       } else if (defRange.valueRangeIndex) {
         newRange.valueRangeIndex = numValueRanges;
         valueToRangeIndex[defIt.first] = numValueRanges++;
       }
 
void Generator::allocateMemoryIndices(FuncOp matcherFunc,
   assert(allocatedIndices.size() <= std::numeric_limits<ByteCodeField>::max() &&
          "Ran out of memory for allocated indices");
 
   // Update the max number of indices.
   if (numIndices > maxValueMemoryIndex)
     maxValueMemoryIndex = numIndices;
   if (numOpRanges > maxOpRangeMemoryIndex)
     maxOpRangeMemoryIndex = numOpRanges;
+  if (numRangeRanges > maxRangeRangeMemoryIndex)
+    maxRangeRangeMemoryIndex = numRangeRanges;
   if (numTypeRanges > maxTypeRangeMemoryIndex)
     maxTypeRangeMemoryIndex = numTypeRanges;
   if (numValueRanges > maxValueRangeMemoryIndex)
     maxValueRangeMemoryIndex = numValueRanges;
 }
 
+void Generator::extendLifetime(ByteCodeLiveRange &range, Value value) {
+  DenseSet<Block *> visited;
+  Block *block = value.getParentBlock();
+  visited.insert(block);
+  // Determine the endpoints of the value in its parent block
+  unsigned start = opToFirstIndex[value.getDefiningOp()];
+  unsigned stop = opToFirstIndex[&block->back()];
+  // Start is in the range. Check for the rare case when the value is not alive
+  // at the end of its parent block. TODO: is this even possible?
+  auto it = range.liveness->find(start);
+  assert(it.valid() && "Value not found in live range");
+  if (stop > it.stop()) {
+    range.liveness->insert(it.stop() + 1, stop, /*dummyValue*/ 0);
+  }
+  // Descend to the successor blocks
+  for (Block *successor : block->getSuccessors())
+    extendLifetime(range, successor, visited);
+}
+void Generator::extendLifetime(ByteCodeLiveRange &range, Block *block,
+                               DenseSet<Block *> &visited) {
+  // Mark the block as visited; return if previously visited.
+  bool newlyVisited = visited.insert(block).second;
+  if (!newlyVisited)
+    return;
+  // Skip if the block contains the sole finalize operation
+  if (block->getOperations().size() == 1 &&
+      isa<pdl_interp::FinalizeOp>(block->front()))
+    return;
+  // Extend the liveness to this entire block
+  unsigned start = opToFirstIndex[&block->front()];
+  unsigned stop = opToFirstIndex[&block->back()];
+  auto it = range.liveness->find(start);
+  if (!it.valid() || stop < it.start())
+    // No overlap => insert the entire range.
+    ;
+  else if (stop > it.stop())
+    // Extend past the original liveness.
+    start = it.stop() + 1;
+  else
+    // Already covering the interval
+    start = stop + 1;
+  if (start <= stop) {
+    range.liveness->insert(start, stop, /*dummyValue*/ 0);
+  }
+  for (Block *successor : block->getSuccessors())
+    extendLifetime(range, successor, visited);
+}
+
 void Generator::generate(Region *region, ByteCodeWriter &writer) {
   llvm::ReversePostOrderTraversal<Region *> rpot(region);
   for (Block *block : rpot) {
     // Keep track of where this block begins within the matcher function.
     blockToAddr.try_emplace(block, matcherByteCode.size());
     for (Operation &op : *block)
       generate(&op, writer);
   }
 }
 
 void Generator::generate(Operation *op, ByteCodeWriter &writer) {
   LLVM_DEBUG({
     // The following list must contain all the operations that do not
     // produce any bytecode.
     if (!isa<pdl_interp::CreateAttributeOp, pdl_interp::CreateTypeOp,
              pdl_interp::InferredTypesOp>(op))
       writer.appendInline(op->getLoc());
   });
   TypeSwitch<Operation *>(op)
       .Case<pdl_interp::ApplyConstraintOp, pdl_interp::ApplyRewriteOp,
             pdl_interp::AreEqualOp, pdl_interp::BranchOp,
             pdl_interp::CheckAttributeOp, pdl_interp::CheckOperandCountOp,
             pdl_interp::CheckOperationNameOp, pdl_interp::CheckResultCountOp,
             pdl_interp::CheckTypeOp, pdl_interp::CheckTypesOp,
-            pdl_interp::ContinueOp, pdl_interp::CreateAttributeOp,
-            pdl_interp::CreateOperationOp, pdl_interp::CreateTypeOp,
-            pdl_interp::CreateTypesOp, pdl_interp::EraseOp,
-            pdl_interp::ExtractOp, pdl_interp::FinalizeOp,
+            pdl_interp::ChooseRangeOp, pdl_interp::ContinueOp,
+            pdl_interp::CreateAttributeOp, pdl_interp::CreateOperationOp,
+            pdl_interp::CreateTypeOp, pdl_interp::CreateTypesOp,
+            pdl_interp::EraseOp, pdl_interp::ExtractOp, pdl_interp::FinalizeOp,
             pdl_interp::ForEachOp, pdl_interp::GetAttributeOp,
             pdl_interp::GetAttributeTypeOp, pdl_interp::GetDefiningOpOp,
-            pdl_interp::GetOperandOp, pdl_interp::GetOperandsOp,
+            pdl_interp::GetItemOp, pdl_interp::GetOperandOp,
+            pdl_interp::GetOperandsOp, pdl_interp::GetPermutationsOp,
             pdl_interp::GetResultOp, pdl_interp::GetResultsOp,
             pdl_interp::GetUsersOp, pdl_interp::GetValueTypeOp,
-            pdl_interp::InferredTypesOp, pdl_interp::IsNotNullOp,
-            pdl_interp::RecordMatchOp, pdl_interp::ReplaceOp,
-            pdl_interp::SwitchAttributeOp, pdl_interp::SwitchTypeOp,
-            pdl_interp::SwitchTypesOp, pdl_interp::SwitchOperandCountOp,
-            pdl_interp::SwitchOperationNameOp, pdl_interp::SwitchResultCountOp>(
+            pdl_interp::InferredTypesOp, pdl_interp::IsCommutativeOp,
+            pdl_interp::IsNotNullOp, pdl_interp::RecordMatchOp,
+            pdl_interp::ReplaceOp, pdl_interp::SwitchAttributeOp,
+            pdl_interp::SwitchTypeOp, pdl_interp::SwitchTypesOp,
+            pdl_interp::SwitchOperandCountOp, pdl_interp::SwitchOperationNameOp,
+            pdl_interp::SwitchResultCountOp>(
           [&](auto interpOp) { this->generate(interpOp, writer); })
       .Default([](Operation *) {
         llvm_unreachable("unknown `pdl_interp` operation");
       });
 }
 
 void Generator::generate(pdl_interp::ApplyConstraintOp op,
                          ByteCodeWriter &writer) {
writer.append(OpCode::CheckResultCount, op.operation(), op.count(),
                 op.getSuccessors());
 }
 void Generator::generate(pdl_interp::CheckTypeOp op, ByteCodeWriter &writer) {
   writer.append(OpCode::AreEqual, op.value(), op.type(), op.getSuccessors());
 }
 void Generator::generate(pdl_interp::CheckTypesOp op, ByteCodeWriter &writer) {
   writer.append(OpCode::CheckTypes, op.value(), op.types(), op.getSuccessors());
 }
+void Generator::generate(pdl_interp::ChooseRangeOp op, ByteCodeWriter &writer) {
+  writer.append(OpCode::ChooseRange, getRangeStorageIndex(op.list()),
+                getRangeStorageIndex(op.range()));
+}
 void Generator::generate(pdl_interp::ContinueOp op, ByteCodeWriter &writer) {
   assert(curLoopLevel > 0 && "encountered pdl_interp.continue at top level");
   writer.append(OpCode::Continue, ByteCodeField(curLoopLevel - 1));
 }
 void Generator::generate(pdl_interp::CreateAttributeOp op,
                          ByteCodeWriter &writer) {
   // Simply repoint the memory index of the result to the constant.
   getMemIndex(op.attribute()) = getMemIndex(op.value());
void Generator::generate(pdl_interp::GetAttributeTypeOp op,
                          ByteCodeWriter &writer) {
   writer.append(OpCode::GetAttributeType, op.result(), op.value());
 }
 void Generator::generate(pdl_interp::GetDefiningOpOp op,
                          ByteCodeWriter &writer) {
   writer.append(OpCode::GetDefiningOp, op.operation());
   writer.appendPDLValue(op.value());
 }
+void Generator::generate(pdl_interp::GetItemOp op, ByteCodeWriter &writer) {
+  uint32_t index = op.index();
+  writer.append(OpCode::GetItem, index, getRangeStorageIndex(op.values()));
+  writer.append(op.value());
+}
 void Generator::generate(pdl_interp::GetOperandOp op, ByteCodeWriter &writer) {
   uint32_t index = op.index();
   if (index < 4)
     writer.append(static_cast<OpCode>(OpCode::GetOperand0 + index));
   else
     writer.append(OpCode::GetOperandN, index);
   writer.append(op.operation(), op.value());
 }
 void Generator::generate(pdl_interp::GetOperandsOp op, ByteCodeWriter &writer) {
   Value result = op.value();
   Optional<uint32_t> index = op.index();
   writer.append(OpCode::GetOperands,
                 index.getValueOr(std::numeric_limits<uint32_t>::max()),
                 op.operation());
   if (result.getType().isa<pdl::RangeType>())
     writer.append(getRangeStorageIndex(result));
   else
     writer.append(std::numeric_limits<ByteCodeField>::max());
   writer.append(result);
 }
+void Generator::generate(pdl_interp::GetPermutationsOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::GetPermutations, getRangeStorageIndex(op.list()),
+                getRangeStorageIndex(op.permutations()));
+}
 void Generator::generate(pdl_interp::GetResultOp op, ByteCodeWriter &writer) {
   uint32_t index = op.index();
   if (index < 4)
     writer.append(static_cast<OpCode>(OpCode::GetResult0 + index));
   else
     writer.append(OpCode::GetResultN, index);
   writer.append(op.operation(), op.value());
 }
void Generator::generate(pdl_interp::GetValueTypeOp op,
   }
 }
 
 void Generator::generate(pdl_interp::InferredTypesOp op,
                          ByteCodeWriter &writer) {
   // InferType maps to a null type as a marker for inferring result types.
   getMemIndex(op.type()) = getMemIndex(Type());
 }
+void Generator::generate(pdl_interp::IsCommutativeOp op,
+                         ByteCodeWriter &writer) {
+  writer.append(OpCode::IsCommutative, op.op(), op.getSuccessors());
+}
 void Generator::generate(pdl_interp::IsNotNullOp op, ByteCodeWriter &writer) {
   writer.append(OpCode::IsNotNull, op.value(), op.getSuccessors());
 }
 void Generator::generate(pdl_interp::RecordMatchOp op, ByteCodeWriter &writer) {
   ByteCodeField patternIndex = patterns.size();
   patterns.emplace_back(PDLByteCodePattern::create(
       op, rewriterToAddr[op.rewriter().getLeafReference().getValue()]));
   writer.append(OpCode::RecordMatch, patternIndex,

 // PDLByteCode
 //===----------------------------------------------------------------------===//
 
 PDLByteCode::PDLByteCode(ModuleOp module,
                          llvm::StringMap<PDLConstraintFunction> constraintFns,
                          llvm::StringMap<PDLRewriteFunction> rewriteFns) {
   Generator generator(module.getContext(), uniquedData, matcherByteCode,
                       rewriterByteCode, patterns, maxValueMemoryIndex,
-                      maxOpRangeCount, maxTypeRangeCount, maxValueRangeCount,
-                      maxLoopLevel, constraintFns, rewriteFns);
+                      maxOpRangeCount, maxRangeRangeCount, maxTypeRangeCount,
+                      maxValueRangeCount, maxLoopLevel, constraintFns,
+                      rewriteFns);
   generator.generate(module);
 
   // Initialize the external functions.
   for (auto &it : constraintFns)
     constraintFunctions.push_back(std::move(it.second));
   for (auto &it : rewriteFns)
     rewriteFunctions.push_back(std::move(it.second));
 }
 
 /// Initialize the given state such that it can be used to execute the current
 /// bytecode.
 void PDLByteCode::initializeMutableState(PDLByteCodeMutableState &state) const {
   state.memory.resize(maxValueMemoryIndex, nullptr);
   state.opRangeMemory.resize(maxOpRangeCount);
+  state.rangeRangeMemory.resize(maxRangeRangeCount, RangeRange());
   state.typeRangeMemory.resize(maxTypeRangeCount, TypeRange());
   state.valueRangeMemory.resize(maxValueRangeCount, ValueRange());
   state.loopIndex.resize(maxLoopLevel, 0);
   state.currentPatternBenefits.reserve(patterns.size());
   for (const PDLByteCodePattern &pattern : patterns)
     state.currentPatternBenefits.push_back(pattern.getBenefit());
 }
 
 //===----------------------------------------------------------------------===//
 // ByteCode Execution
 
 namespace {
 /// This class provides support for executing a bytecode stream.
 class ByteCodeExecutor {
 public:
   ByteCodeExecutor(
       const ByteCodeField *curCodeIt, MutableArrayRef<const void *> memory,
       MutableArrayRef<llvm::OwningArrayRef<Operation *>> opRangeMemory,
+      MutableArrayRef<RangeRange> rangeRangeMemory,
+      std::vector<llvm::OwningArrayRef<ValueRange>> &allocatedRangeRangeMemory,
       MutableArrayRef<TypeRange> typeRangeMemory,
       std::vector<llvm::OwningArrayRef<Type>> &allocatedTypeRangeMemory,
       MutableArrayRef<ValueRange> valueRangeMemory,
       std::vector<llvm::OwningArrayRef<Value>> &allocatedValueRangeMemory,
       MutableArrayRef<unsigned> loopIndex, ArrayRef<const void *> uniquedMemory,
       ArrayRef<ByteCodeField> code,
       ArrayRef<PatternBenefit> currentPatternBenefits,
       ArrayRef<PDLByteCodePattern> patterns,
       ArrayRef<PDLConstraintFunction> constraintFunctions,
       ArrayRef<PDLRewriteFunction> rewriteFunctions)
       : curCodeIt(curCodeIt), memory(memory), opRangeMemory(opRangeMemory),
+        rangeRangeMemory(rangeRangeMemory),
+        allocatedRangeRangeMemory(allocatedRangeRangeMemory),
         typeRangeMemory(typeRangeMemory),
         allocatedTypeRangeMemory(allocatedTypeRangeMemory),
         valueRangeMemory(valueRangeMemory),
         allocatedValueRangeMemory(allocatedValueRangeMemory),
         loopIndex(loopIndex), uniquedMemory(uniquedMemory), code(code),
         currentPatternBenefits(currentPatternBenefits), patterns(patterns),
         constraintFunctions(constraintFunctions),
         rewriteFunctions(rewriteFunctions) {}
private:
   void executeApplyRewrite(PatternRewriter &rewriter);
   void executeAreEqual();
   void executeAreRangesEqual();
   void executeBranch();
   void executeCheckOperandCount();
   void executeCheckOperationName();
   void executeCheckResultCount();
   void executeCheckTypes();
+  bool executeChooseRange();
   void executeContinue();
   void executeCreateOperation(PatternRewriter &rewriter,
                               Location mainRewriteLoc);
   void executeCreateTypes();
   void executeEraseOp(PatternRewriter &rewriter);
   template <typename T, typename Range, PDLValue::Kind kind>
   void executeExtract();
-  void executeFinalize();
+  bool executeFinalize();
   void executeForEach();
   void executeGetAttribute();
   void executeGetAttributeType();
   void executeGetDefiningOp();
+  void executeGetItem(unsigned index);
   void executeGetOperand(unsigned index);
   void executeGetOperands();
+  void executeGetPermutations();
   void executeGetResult(unsigned index);
   void executeGetResults();
   void executeGetUsers();
   void executeGetValueType();
   void executeGetValueRangeTypes();
+  void executeIsCommutative();
   void executeIsNotNull();
   void executeRecordMatch(PatternRewriter &rewriter,
                           SmallVectorImpl<PDLByteCode::MatchResult> &matches);
   void executeReplaceOp(PatternRewriter &rewriter);
   void executeSwitchAttribute();
   void executeSwitchOperandCount();
   void executeSwitchOperationName();
   void executeSwitchResultCount();
private:
   const ByteCodeField *curCodeIt;
 
   /// The stack of bytecode positions at which to resume operation.
   SmallVector<const ByteCodeField *> resumeCodeIt;
 
   /// The current execution memory.
   MutableArrayRef<const void *> memory;
   MutableArrayRef<OwningOpRange> opRangeMemory;
+  MutableArrayRef<RangeRange> rangeRangeMemory;
+  std::vector<llvm::OwningArrayRef<ValueRange>> &allocatedRangeRangeMemory;
   MutableArrayRef<TypeRange> typeRangeMemory;
   std::vector<llvm::OwningArrayRef<Type>> &allocatedTypeRangeMemory;
   MutableArrayRef<ValueRange> valueRangeMemory;
   std::vector<llvm::OwningArrayRef<Value>> &allocatedValueRangeMemory;
 
   /// The current loop indices.
   MutableArrayRef<unsigned> loopIndex;
 
void ByteCodeExecutor::executeCheckTypes() {
   LLVM_DEBUG(llvm::dbgs() << "Executing AreEqual:\n");
   TypeRange *lhs = read<TypeRange *>();
   Attribute rhs = read<Attribute>();
   LLVM_DEBUG(llvm::dbgs() << "  * " << lhs << " == " << rhs << "\n\n");
 
   selectJump(*lhs == rhs.cast<ArrayAttr>().getAsValueRange<TypeAttr>());
 }
 
+bool ByteCodeExecutor::executeChooseRange() {
+  LLVM_DEBUG(llvm::dbgs() << "Executing ChooseRange:\n");
+  const ByteCodeField *it = curCodeIt - 1; // Subtract 1 for the op code.
+  unsigned permutationsIndex = read();
+  unsigned rangeIndex = read();
+  RangeRange &permutation = rangeRangeMemory[permutationsIndex];
+  if (permutation.empty()) {
+    LLVM_DEBUG(llvm::dbgs() << "  * Done\n");
+    if (resumeCodeIt.empty())
+      return false;
+    popCodeIt();
+    return true;
+  }
+
+  ValueRange range = permutation.front();
+
+  permutation = permutation.drop_front();
+  valueRangeMemory[rangeIndex] = range;
+  pushCodeIt(it);
+  return true;
+}
+
 void ByteCodeExecutor::executeContinue() {
   ByteCodeField level = read();
   LLVM_DEBUG(llvm::dbgs() << "Executing Continue\n"
                           << "  * Level: " << level << "\n");
   ++loopIndex[level];
   popCodeIt();
 }
 
for (unsigned i = 0, e = read(); i != e; ++i) {
     if (failed(concept->inferReturnTypes(
             state.getContext(), state.location, state.operands,
             state.attributes.getDictionary(state.getContext()), state.regions,
             state.types)))
       return;
     break;
   }
 
+  // Determine the insertion point.
+  // This is the last of the operands, default to beginning of the block.
+  Block *block = rewriter.getBlock();
+  rewriter.setInsertionPointToStart(block);
+  DenseSet<Operation *> operationSet;
+  for (Value value : state.operands)
+    operationSet.insert(value.getDefiningOp());
+  for (auto it = block->rbegin(); it != block->rend(); ++it)
+    if (operationSet.count(&*it)) {
+      LLVM_DEBUG(llvm::dbgs()
+                 << "Inserting " << state.name << " after " << *it << "\n");
+      rewriter.setInsertionPointAfter(&*it);
+      break;
+    }
+
   Operation *resultOp = rewriter.createOperation(state);
   memory[memIndex] = resultOp;
 
   LLVM_DEBUG({
     llvm::dbgs() << "  * Attributes: "
                  << state.attributes.getDictionary(state.getContext())
                  << "\n  * Operands: ";
     llvm::interleaveComma(state.operands, llvm::dbgs());
void ByteCodeExecutor::executeExtract() {
 
   T result = index < range->size() ? (*range)[index] : T();
   LLVM_DEBUG(llvm::dbgs() << "  * " << kind << "s(" << range->size() << ")\n"
                           << "  * Index: " << index << "\n"
                           << "  * Result: " << result << "\n");
   storeToMemory(memIndex, result);
 }
 
-void ByteCodeExecutor::executeFinalize() {
+bool ByteCodeExecutor::executeFinalize() {
   LLVM_DEBUG(llvm::dbgs() << "Executing Finalize\n");
+  if (resumeCodeIt.empty())
+    return false;
+  popCodeIt();
+  return true;
 }
 
 void ByteCodeExecutor::executeForEach() {
   LLVM_DEBUG(llvm::dbgs() << "Executing ForEach:\n");
   const ByteCodeField *prevCodeIt = getPrevCodeIt();
   unsigned rangeIndex = read();
   unsigned memIndex = read();
   const void *value = nullptr;
if (read<PDLValue::Kind>() == PDLValue::Kind::Value) {
     }
     LLVM_DEBUG(llvm::dbgs() << "  * Values: " << values << "\n");
   }
 
   LLVM_DEBUG(llvm::dbgs() << "  * Result: " << op << "\n");
   memory[memIndex] = op;
 }
 
+void ByteCodeExecutor::executeGetItem(unsigned index) {
+  unsigned rangeIndex = read();
+  unsigned memindex = read();
+  ValueRange range = valueRangeMemory[rangeIndex];
+  Value operand = index < range.size() ? range[index] : Value();
+  LLVM_DEBUG(llvm::dbgs() << "  * Index " << index << "\n"
+                          << "  * Result: " << operand << "\n");
+  memory[memindex] = operand.getAsOpaquePointer();
+}
+
 void ByteCodeExecutor::executeGetOperand(unsigned index) {
   Operation *op = read<Operation *>();
   unsigned memIndex = read();
   Value operand =
       index < op->getNumOperands() ? op->getOperand(index) : Value();
 
   LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n"
                           << "  * Index: " << index << "\n"
void ByteCodeExecutor::executeGetOperands() {
   void *result = executeGetOperandsResults<OpTrait::AttrSizedOperandSegments>(
       op->getOperands(), op, index, rangeIndex, "operand_segment_sizes",
       valueRangeMemory);
   if (!result)
     LLVM_DEBUG(llvm::dbgs() << "  * Invalid operand range\n");
   memory[read()] = result;
 }
 
+static int64_t factorial(unsigned num) {
+  return (num == 1 || num == 0) ? 1 : num * factorial(num - 1);
+}
+
+/// Populates the initial ordering of `operandsVector`. This gets stored in
+/// `ordering`.
+static void getOperandInitialOrdering(const ArrayRef<Value> &operandsVector,
+                                      std::vector<unsigned> &ordering) {
+  llvm::DenseMap<Value, unsigned> valueToIndex;
+  for (unsigned i = 0, e = operandsVector.size(); i < e; i++) {
+    auto it = valueToIndex.try_emplace(operandsVector[i], i);
+    if (!it.second)
+      ordering.push_back(valueToIndex[operandsVector[i]]);
+    else
+      ordering.push_back(i);
+  }
+}
+
+/// Generates permutations  for a list of values.
+static void getPermutationSequences(
+    ValueRange operands, ByteCodeField rangeIndex, unsigned numOperands,
+    MutableArrayRef<RangeRange> &rangeRangeMemory,
+    std::vector<llvm::OwningArrayRef<ValueRange>> &allocatedRangeRangeMemory,
+    std::vector<llvm::OwningArrayRef<Value>> &allocatedValueRangeMemory) {
+  auto operandsVector = llvm::to_vector<4>(operands);
+  int64_t numResults = factorial(numOperands);
+  SmallVector<ValueRange, 4> results;
+  results.reserve(numResults);
+  std::vector<unsigned> orderings;
+  getOperandInitialOrdering(operandsVector, orderings);
+  std::sort(orderings.begin(), orderings.end());
+  do {
+    SmallVector<Value, 4> values;
+    values.reserve(numOperands);
+    for (unsigned i = 0; i < numOperands; i++) {
+      values.push_back(operandsVector[orderings[i]]);
+    }
+    ValueRange range(values);
+    llvm::OwningArrayRef<Value> storage(range.size());
+    llvm::copy(range, storage.begin());
+    allocatedValueRangeMemory.emplace_back(std::move(storage));
+    results.push_back(allocatedValueRangeMemory.back());
+  } while (std::next_permutation(orderings.begin(), orderings.end()));
+
+  // If the range index is valid, we are returning a range.
+  if (rangeIndex != std::numeric_limits<ByteCodeField>::max()) {
+    llvm::OwningArrayRef<ValueRange> storage(results.size());
+    llvm::copy(results, storage.begin());
+    allocatedRangeRangeMemory.emplace_back(std::move(storage));
+
+    // Assign this to the range slot.
+    rangeRangeMemory[rangeIndex] = allocatedRangeRangeMemory.back();
+  }
+}
+
+void ByteCodeExecutor::executeGetPermutations() {
+  LLVM_DEBUG(llvm::dbgs() << "Executing GetPermutations:\n");
+  unsigned listRangeIndex = read();
+  unsigned permutationsRangeIndex = read();
+  ValueRange operands = valueRangeMemory[listRangeIndex];
+  getPermutationSequences(operands, permutationsRangeIndex, operands.size(),
+                          rangeRangeMemory, allocatedRangeRangeMemory,
+                          allocatedValueRangeMemory);
+}
+
 void ByteCodeExecutor::executeGetResult(unsigned index) {
   Operation *op = read<Operation *>();
   unsigned memIndex = read();
   OpResult result =
       index < op->getNumResults() ? op->getResult(index) : OpResult();
 
   LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n"
                           << "  * Index: " << index << "\n"
LLVM_DEBUG({
     llvm::dbgs() << "\n  * Result: ";
     llvm::interleaveComma(values->getType(), llvm::dbgs());
     llvm::dbgs() << "\n";
   });
   typeRangeMemory[rangeIndex] = values->getType();
   memory[memIndex] = &typeRangeMemory[rangeIndex];
 }
 
+void ByteCodeExecutor::executeIsCommutative() {
+  LLVM_DEBUG(llvm::dbgs() << "Executing IsCommutative:\n");
+  Operation *op = read<Operation *>();
+
+  LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << op << "\n");
+  selectJump(op && (op->hasTrait<mlir::OpTrait::IsCommutative>() ||
+                    op->hasAttr("commutative")));
+}
+
 void ByteCodeExecutor::executeIsNotNull() {
   LLVM_DEBUG(llvm::dbgs() << "Executing IsNotNull:\n");
   const void *value = read<const void *>();
 
   LLVM_DEBUG(llvm::dbgs() << "  * Value: " << value << "\n");
   selectJump(value != nullptr);
 }
 
case CheckOperationName:
       executeCheckOperationName();
       break;
     case CheckResultCount:
       executeCheckResultCount();
       break;
     case CheckTypes:
       executeCheckTypes();
       break;
+    case ChooseRange:
+      if (executeChooseRange())
+        break;
+      return;
     case Continue:
       executeContinue();
       break;
     case CreateOperation:
       executeCreateOperation(rewriter, *mainRewriteLoc);
       break;
     case CreateTypes:
       executeCreateTypes();
       break;
     case EraseOp:
       executeEraseOp(rewriter);
       break;
     case ExtractOp:
       executeExtract<Operation *, OwningOpRange, PDLValue::Kind::Operation>();
       break;
     case ExtractType:
       executeExtract<Type, TypeRange, PDLValue::Kind::Type>();
       break;
     case ExtractValue:
       executeExtract<Value, ValueRange, PDLValue::Kind::Value>();
       break;
     case Finalize:
-      executeFinalize();
+      if (executeFinalize())
+        break;
       LLVM_DEBUG(llvm::dbgs() << "\n");
       return;
     case ForEach:
       executeForEach();
       break;
     case GetAttribute:
       executeGetAttribute();
       break;
     case GetAttributeType:
       executeGetAttributeType();
       break;
     case GetDefiningOp:
       executeGetDefiningOp();
       break;
+    case GetItem:
+      executeGetItem(read<uint32_t>());
+      break;
     case GetOperand0:
     case GetOperand1:
     case GetOperand2:
     case GetOperand3: {
       unsigned index = opCode - GetOperand0;
       LLVM_DEBUG(llvm::dbgs() << "Executing GetOperand" << index << ":\n");
       executeGetOperand(index);
       break;
     }
     case GetOperandN:
       LLVM_DEBUG(llvm::dbgs() << "Executing GetOperandN:\n");
       executeGetOperand(read<uint32_t>());
       break;
     case GetOperands:
       executeGetOperands();
       break;
+    case GetPermutations:
+      executeGetPermutations();
+      break;
     case GetResult0:
     case GetResult1:
     case GetResult2:
     case GetResult3: {
       unsigned index = opCode - GetResult0;
       LLVM_DEBUG(llvm::dbgs() << "Executing GetResult" << index << ":\n");
       executeGetResult(index);
       break;
case GetUsers:
       executeGetUsers();
       break;
     case GetValueType:
       executeGetValueType();
       break;
     case GetValueRangeTypes:
       executeGetValueRangeTypes();
       break;
+    case IsCommutative:
+      executeIsCommutative();
+      break;
     case IsNotNull:
       executeIsNotNull();
       break;
     case RecordMatch:
       assert(matches &&
              "expected matches to be provided when executing the matcher");
       executeRecordMatch(rewriter, *matches);
       break;
void PDLByteCode::match(Operation *op, PatternRewriter &rewriter,
                         SmallVectorImpl<MatchResult> &matches,
                         PDLByteCodeMutableState &state) const {
   // The first memory slot is always the root operation.
   state.memory[0] = op;
 
   // The matcher function always starts at code address 0.
   ByteCodeExecutor executor(
       matcherByteCode.data(), state.memory, state.opRangeMemory,
+      state.rangeRangeMemory, state.allocatedRangeRangeMemory,
       state.typeRangeMemory, state.allocatedTypeRangeMemory,
       state.valueRangeMemory, state.allocatedValueRangeMemory, state.loopIndex,
       uniquedData, matcherByteCode, state.currentPatternBenefits, patterns,
       constraintFunctions, rewriteFunctions);
   executor.execute(rewriter, &matches);
 
   // Order the found matches by benefit.
   std::stable_sort(matches.begin(), matches.end(),
                    [](const MatchResult &lhs, const MatchResult &rhs) {
                      return lhs.benefit > rhs.benefit;
                    });
 }
 
 /// Run the rewriter of the given pattern on the root operation `op`.
 void PDLByteCode::rewrite(PatternRewriter &rewriter, const MatchResult &match,
                           PDLByteCodeMutableState &state) const {
   // The arguments of the rewrite function are stored at the start of the
   // memory buffer.
   llvm::copy(match.values, state.memory.begin());
 
   ByteCodeExecutor executor(
       &rewriterByteCode[match.pattern->getRewriterAddr()], state.memory,
-      state.opRangeMemory, state.typeRangeMemory,
+      state.opRangeMemory, state.rangeRangeMemory,
+      state.allocatedRangeRangeMemory, state.typeRangeMemory,
       state.allocatedTypeRangeMemory, state.valueRangeMemory,
       state.allocatedValueRangeMemory, state.loopIndex, uniquedData,
       rewriterByteCode, state.currentPatternBenefits, patterns,
       constraintFunctions, rewriteFunctions);
   executor.execute(rewriter, /*matches=*/nullptr, match.location);
 }

mlir/test/Rewrite/pdl-bytecode.mlir

func @success(%root : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %root
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.are_equal_2
-// CHECK: "test.not_equal"
 // CHECK: "test.success"
+// CHECK: "test.not_equal"
 // CHECK-NOT: "test.op"
 module @ir attributes { test.are_equal_2 } {
   "test.not_equal"() : () -> (i32)
   "test.op"() : () -> (i32, i64)
 }
 
 // -----
 
func @success(%root : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %root
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.check_operand_count_1
-// CHECK: "test.op"() : () -> i32
 // CHECK: "test.success"
+// CHECK: "test.op"() : () -> i32
 module @ir attributes { test.check_operand_count_1 } {
   %operand = "test.op"() : () -> i32
   "test.op"(%operand, %operand) : (i32, i32) -> ()
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
func @success(%root : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %root
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.check_result_count_1
-// CHECK: "test.op"() : () -> i32
 // CHECK: "test.success"() : () -> ()
+// CHECK: "test.op"() : () -> i32
 // CHECK-NOT: "test.op"() : () -> (i32, i32)
 module @ir attributes { test.check_result_count_1 } {
   "test.op"() : () -> i32
   "test.op"() : () -> (i32, i32)
 }
 
 // -----
 
func @success(%root : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %root
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.check_types_1
-// CHECK: "test.op"() : () -> (i32, i64)
 // CHECK: "test.success"
+// CHECK: "test.op"() : () -> (i32, i64)
 // CHECK-NOT: "test.op"() : () -> i32
 module @ir attributes { test.check_types_1 } {
   "test.op"() : () -> (i32, i64)
   "test.op"() : () -> i32
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::ChooseRangeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::ContinueOp
 //===----------------------------------------------------------------------===//
 
 // Fully tested within the tests for other operations.
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::CreateAttributeOp
 //===----------------------------------------------------------------------===//
func @success(%matched : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %matched
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.extract_type
-// CHECK: %[[OPERAND:.*]] = "test.op"
 // CHECK: "test.success"
+// CHECK: %[[OPERAND:.*]] = "test.op"
 // CHECK: "test.op"(%[[OPERAND]])
 module @ir attributes { test.extract_type } {
   %operand = "test.op"() : () -> i32
   "test.op"(%operand) : (i32) -> (i32, i32)
   "test.op"(%operand) : (i32) -> (i32)
 }
 
 // -----
func @success(%matched : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %matched
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.extract_value
-// CHECK: %[[OPERAND:.*]] = "test.op"
 // CHECK: "test.success"
+// CHECK: %[[OPERAND:.*]] = "test.op"
 // CHECK: "test.op"(%[[OPERAND]])
 module @ir attributes { test.extract_value } {
   %operand = "test.op"() : () -> i32
   "test.op"(%operand) : (i32) -> (i32, i32)
   "test.op"(%operand) : (i32) -> (i32)
 }
 
 // -----
func @success(%root : !pdl.operation) {
       %op = pdl_interp.create_operation "test.success"
       pdl_interp.erase %root
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.get_defining_op_1
+// CHECK: "test.success"
 // CHECK: %[[OPERAND0:.*]] = "test.op"
 // CHECK: %[[OPERAND1:.*]] = "test.op"
-// CHECK: "test.success"
 // CHECK: "test.op"(%[[OPERAND0]], %[[OPERAND0]], %[[OPERAND0]], %[[OPERAND0]], %[[OPERAND1]])
 module @ir attributes { test.get_defining_op_1 } {
   %operand = "test.op"() : () -> i32
   %other_operand = "test.op"() : () -> i32
   "test.op"(%operand, %operand, %operand, %operand, %operand) : (i32, i32, i32, i32, i32) -> ()
   "test.op"(%operand, %operand, %operand, %operand, %other_operand) : (i32, i32, i32, i32, i32) -> ()
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::GetItemOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::GetOperandOp
 //===----------------------------------------------------------------------===//
 
 // Fully tested within the tests for other operations.
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::GetOperandsOp
 //===----------------------------------------------------------------------===//
func @success(%root: !pdl.operation, %operands_0: !pdl.range<value>, %operands_1: !pdl.range<value>, %operands_2: !pdl.range<value>, %operands_2_single: !pdl.value) {
       %op3 = pdl_interp.create_operation "test.success"(%operands_2_single : !pdl.value)
       pdl_interp.erase %root
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.get_operands_2
-// CHECK-NEXT:  %[[INPUTS:.*]]:5 = "test.producer"() : () -> (i32, i32, i32, i32, i32)
 // CHECK-NEXT:  "test.success"() : () -> ()
-// CHECK-NEXT:  "test.success"(%[[INPUTS]]#0, %[[INPUTS]]#1, %[[INPUTS]]#2, %[[INPUTS]]#3) : (i32, i32, i32, i32) -> ()
+// CHECK-NEXT:  %[[INPUTS:.*]]:5 = "test.producer"() : () -> (i32, i32, i32, i32, i32)
 // CHECK-NEXT:  "test.success"(%[[INPUTS]]#4) : (i32) -> ()
 // CHECK-NEXT:  "test.success"(%[[INPUTS]]#4) : (i32) -> ()
+// CHECK-NEXT:  "test.success"(%[[INPUTS]]#0, %[[INPUTS]]#1, %[[INPUTS]]#2, %[[INPUTS]]#3) : (i32, i32, i32, i32) -> ()
 module @ir attributes { test.get_operands_2 } {
   %inputs:5 = "test.producer"() : () -> (i32, i32, i32, i32, i32)
   "test.attr_sized_operands"(%inputs#0, %inputs#1, %inputs#2, %inputs#3, %inputs#4) {operand_segment_sizes = dense<[0, 4, 1, 0]> : vector<4xi32>} : (i32, i32, i32, i32, i32) -> ()
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::GetPermutationsOp
+//===----------------------------------------------------------------------===//
+
+module @patterns  {
+  func @matcher(%arg0: !pdl.operation) {
+    pdl_interp.is_commutative %arg0 : !pdl.operation -> ^bb2, ^bb1
+  ^bb1:  // 22 preds: ^bb0, ^bb2, ^bb3, ^bb4, ^bb5, ^bb6, ^bb7, ^bb8, ^bb9, ^bb10, ^bb11, ^bb12, ^bb13, ^bb14, ^bb15, ^bb16, ^bb17, ^bb18, ^bb19, ^bb20, ^bb21, ^bb22
+    pdl_interp.finalize
+  ^bb2:  // pred: ^bb0
+    %0 = pdl_interp.get_operands of %arg0 : !pdl.range<value>
+    %1 = pdl_interp.get_permutations for %0
+    %2 = pdl_interp.choose_range from %1
+    %3 = pdl_interp.get_item 1 from %2
+    %4 = pdl_interp.get_defining_op of %3 : !pdl.value
+    pdl_interp.is_not_null %4 : !pdl.operation -> ^bb3, ^bb1
+  ^bb3:  // pred: ^bb2
+    %5 = pdl_interp.get_item 0 from %2
+    %6 = pdl_interp.get_defining_op of %5 : !pdl.value
+    pdl_interp.is_not_null %6 : !pdl.operation -> ^bb4, ^bb1
+  ^bb4:  // pred: ^bb3
+    pdl_interp.check_operation_name of %arg0 is "test.op" -> ^bb5, ^bb1
+  ^bb5:  // pred: ^bb4
+    pdl_interp.check_operand_count of %arg0 is 2 -> ^bb6, ^bb1
+  ^bb6:  // pred: ^bb5
+    pdl_interp.check_result_count of %arg0 is 1 -> ^bb7, ^bb1
+  ^bb7:  // pred: ^bb6
+    pdl_interp.is_not_null %3 : !pdl.value -> ^bb8, ^bb1
+  ^bb8:  // pred: ^bb7
+    pdl_interp.is_not_null %5 : !pdl.value -> ^bb9, ^bb1
+  ^bb9:  // pred: ^bb8
+    %7 = pdl_interp.get_result 0 of %arg0
+    pdl_interp.is_not_null %7 : !pdl.value -> ^bb10, ^bb1
+  ^bb10:  // pred: ^bb9
+    pdl_interp.check_operand_count of %4 is 0 -> ^bb11, ^bb1
+  ^bb11:  // pred: ^bb10
+    pdl_interp.check_operand_count of %6 is 0 -> ^bb12, ^bb1
+  ^bb12:  // pred: ^bb11
+    pdl_interp.check_result_count of %6 is 1 -> ^bb13, ^bb1
+  ^bb13:  // pred: ^bb12
+    pdl_interp.check_result_count of %4 is 1 -> ^bb14, ^bb1
+  ^bb14:  // pred: ^bb13
+    %8 = pdl_interp.get_attribute "attr" of %6
+    pdl_interp.is_not_null %8 : !pdl.attribute -> ^bb15, ^bb1
+  ^bb15:  // pred: ^bb14
+    %9 = pdl_interp.get_attribute "attr1" of %4
+    pdl_interp.is_not_null %9 : !pdl.attribute -> ^bb16, ^bb1
+  ^bb16:  // pred: ^bb15
+    %10 = pdl_interp.get_result 0 of %6
+    pdl_interp.is_not_null %10 : !pdl.value -> ^bb17, ^bb1
+  ^bb17:  // pred: ^bb16
+    %11 = pdl_interp.get_result 0 of %4
+    pdl_interp.is_not_null %11 : !pdl.value -> ^bb18, ^bb1
+  ^bb18:  // pred: ^bb17
+    pdl_interp.are_equal %10, %5 : !pdl.value -> ^bb19, ^bb1
+  ^bb19:  // pred: ^bb18
+    pdl_interp.are_equal %11, %3 : !pdl.value -> ^bb20, ^bb1
+  ^bb20:  // pred: ^bb19
+    %12 = pdl_interp.get_value_type of %10 : !pdl.type
+    %13 = pdl_interp.get_value_type of %11 : !pdl.type
+    pdl_interp.are_equal %12, %13 : !pdl.type -> ^bb21, ^bb1
+  ^bb21:  // pred: ^bb20
+    %14 = pdl_interp.get_value_type of %7 : !pdl.type
+    pdl_interp.are_equal %12, %14 : !pdl.type -> ^bb22, ^bb1
+  ^bb22:  // pred: ^bb21
+    pdl_interp.record_match @rewriters::@success(%arg0 : !pdl.operation) : benefit(1), loc([%arg0, %4, %6]), root("test.op") -> ^bb1
+  }
+  module @rewriters {
+    func @success(%root : !pdl.operation) {
+      %op = pdl_interp.create_operation "test.success"
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+
+}
+
+// We can see that if the ops were not commutative, only one "test.success"
+// would have been obtained, but, since the ops are commutative, their chance of
+// matching has increased (both permutations of their operands are matched
+// above), which results in two "test.success" ops, one for each commutative
+// "test.op".
+// CHECK-LABEL: test.commutativity
+// CHECK: "test.success"
+// CHECK: "test.success"
+module @ir attributes { test.commutativity} {
+  %0 = "test.op"() {"attr1" = 2} : () -> i32
+  %1 = "test.op"() {"attr" = 1} : () -> i32
+  %2 = "test.op"(%1, %0) {"commutative"} : (i32, i32) -> i32
+  %3 = "test.op"(%0, %1) {"commutative"} : (i32, i32) -> i32
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::GetResultOp
 //===----------------------------------------------------------------------===//
 
 module @patterns {
   func @matcher(%root : !pdl.operation) {
     pdl_interp.check_result_count of %root is 5 -> ^pat1, ^end
 
   ^pat1:
func @success(%root: !pdl.operation, %results_0: !pdl.range<value>, %results_1: !pdl.range<value>, %results_2: !pdl.range<value>, %results_2_single: !pdl.value) {
 
       pdl_interp.replace %root with (%new_results_0, %new_results_1, %new_results_2 : !pdl.range<value>, !pdl.range<value>, !pdl.range<value>)
       pdl_interp.finalize
     }
   }
 }
 
 // CHECK-LABEL: test.get_results_2
-// CHECK: "test.success"() : () -> ()
-// CHECK: %[[RESULTS_1:.*]]:4 = "test.success"() : () -> (i32, i32, i32, i32)
-// CHECK: %[[RESULTS_2:.*]] = "test.success"() : () -> i32
 // CHECK: %[[RESULTS_2_SINGLE:.*]] = "test.success"() : () -> i32
+// CHECK: %[[RESULTS_2:.*]] = "test.success"() : () -> i32
+// CHECK: %[[RESULTS_1:.*]]:4 = "test.success"() : () -> (i32, i32, i32, i32)
+// CHECK: "test.success"() : () -> ()
 // CHECK: "test.consumer"(%[[RESULTS_1]]#0, %[[RESULTS_1]]#1, %[[RESULTS_1]]#2, %[[RESULTS_1]]#3, %[[RESULTS_2]]) : (i32, i32, i32, i32, i32) -> ()
 module @ir attributes { test.get_results_2 } {
   %results:5 = "test.attr_sized_results"() {result_segment_sizes = dense<[0, 4, 1, 0]> : vector<4xi32>} : () -> (i32, i32, i32, i32, i32)
   "test.consumer"(%results#0, %results#1, %results#2, %results#3, %results#4) : (i32, i32, i32, i32, i32) -> ()
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::GetValueTypeOp
 //===----------------------------------------------------------------------===//
 
 // Fully tested within the tests for other operations.
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::InferredTypesOp
 //===----------------------------------------------------------------------===//
 
 // Fully tested within the tests for other operations.
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::IsCommutativeOp
+//===----------------------------------------------------------------------===//
+
+// Fully tested within the tests for other operations.
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::IsNotNullOp
 //===----------------------------------------------------------------------===//
 
 // Fully tested within the tests for other operations.
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::RecordMatchOp
 //===----------------------------------------------------------------------===//