[mlir:PDL] Add support for creating ranges in rewrites

[rriddle]

Summary

This commit adds support for building a concatenated range from
a given set of elements, either single element or other ranges, within a
rewrite. We could conceptually extend this to support constraining
input ranges, but the logic there is quite a bit more complex so it is
left for later work when a need arises.

[jpienaar]

Nice

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

1012

OOC when is it not

!pdl.T, pdl.range<T>

? E.g., with one specified is the other fixed?

mlir/lib/Rewrite/ByteCode.cpp

107

CreateDynamicTypeRange ? (just to mirror, else it feels like one is a specialization of the other)

1200

else if (TypeRange ...) ?

Or can read not fail here.

mlir/include/mlir/Dialect/PDL/IR/PDLOps.td

let extraClassDeclaration = [{
 
     /// Returns the rewrite operation of this pattern.
     RewriteOp getRewriter();
   }];
   let hasRegionVerifier = 1;
 }
 
 //===----------------------------------------------------------------------===//
+// pdl::RangeOp
+//===----------------------------------------------------------------------===//
+
+def PDL_RangeOp : PDL_Op<"range", [Pure, HasParent<"pdl::RewriteOp">]> {
+  let summary = "Construct a range of pdl entities";
+  let description = [{
+    `pdl.range` operations construct a range from a given set of PDL entities,
+    which all share the same underlying element type. For example, a
+    `!pdl.range<value>` may be constructed from a list of `!pdl.value`
+    or `!pdl.range<value>` entities.
+
+    Example:
+
+    ```mlir
+    // Construct a range of values.
+    %valueRange = pdl.range %inputValue, %inputRange : !pdl.value, !pdl.range<value>
+
+    // Construct a range of types.
+    %typeRange = pdl.range %inputType, %inputRange : !pdl.type, !pdl.range<type>
+    
+    // Construct an empty range of types.
+    %valueRange = pdl.range : !pdl.range<type>
+    ```
+
+    TODO: Range construction is currently limited to rewrites, but it could
+    be extended to constraints under certain circustances; i.e., if we can
+    determine how to extract the underlying elements. If we can't, e.g. if
+    there are multiple sub ranges used for construction, we won't be able
+    to determine their sizes during constraint time.
+  }];
+
+  let arguments = (ins Variadic<PDL_AnyType>:$arguments);
+  let results = (outs PDL_RangeOf<AnyTypeOf<[PDL_Type, PDL_Value]>>:$result);
+  let assemblyFormat = [{
+    ($arguments^ `:` type($arguments))?
+    custom<RangeType>(ref(type($arguments)), type($result))
+    attr-dict
+  }];
+  let hasVerifier = 1;
+}
+
+//===----------------------------------------------------------------------===//
 // pdl::ReplaceOp
 //===----------------------------------------------------------------------===//
 
 def PDL_ReplaceOp : PDL_Op<"replace", [
     AttrSizedOperandSegments, HasParent<"pdl::RewriteOp">
   ]> {
   let summary = "Mark an input operation as `replaced`";
   let description = [{

mlir/include/mlir/Dialect/PDL/IR/PDLTypes.h

 namespace pdl {
 /// This class represents the base class of all PDL types.
 class PDLType : public Type {
 public:
   using Type::Type;
 
   static bool classof(Type type);
 };
+
+/// If the given type is a range, return its element type, otherwise return
+/// the type itself.
+Type getRangeElementTypeOrSelf(Type type);
+
 } // namespace pdl
 } // namespace mlir
 
 #define GET_TYPEDEF_CLASSES
 #include "mlir/Dialect/PDL/IR/PDLOpsTypes.h.inc"
 
 #endif // MLIR_DIALECT_PDL_IR_PDLTYPES_H_

mlir/include/mlir/Dialect/PDLInterp/IR/PDLInterpOps.td

let description = [{
     pdl_interp.is_not_null %value : !pdl.value -> ^matchDest, ^failureDest
     ```
   }];
 
   let arguments = (ins PDL_AnyType:$value);
   let assemblyFormat = "$value `:` type($value) attr-dict `->` successors";
 }
 
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CreateRangeOp
+//===----------------------------------------------------------------------===//
+
+def PDLInterp_CreateRangeOp : PDLInterp_Op<"create_range", [Pure]> {
+  let summary = "Construct a range of PDL entities";
+  let description = [{
+    `pdl_interp.create_range` operations construct a range from a given set of PDL
+    entities, which all share the same underlying element type. For example, a
+    `!pdl.range<value>` may be constructed from a list of `!pdl.value`
+    or `!pdl.range<value>` entities.
+
+    Example:
+
+    ```mlir
+    // Construct a range of values.
+    %valueRange = pdl_interp.create_range %inputValue, %inputRange : !pdl.value, !pdl.range<value>
+
+    // Construct a range of types.
+    %typeRange = pdl_interp.create_range %inputType, %inputRange : !pdl.type, !pdl.range<type>
+    
+    // Construct an empty range of types.
+    %valueRange = pdl_interp.create_range : !pdl.range<type>
+    ```
+  }];
+
+  let arguments = (ins Variadic<PDL_AnyType>:$arguments);
+  let results = (outs PDL_RangeOf<AnyTypeOf<[PDL_Type, PDL_Value]>>:$result);
+  let assemblyFormat = [{
+    ($arguments^ `:` type($arguments))?
+    custom<RangeType>(ref(type($arguments)), type($result))
+    attr-dict
+  }];
+  let hasVerifier = 1;
+}
+
 //===----------------------------------------------------------------------===//
 // pdl_interp::RecordMatchOp
 //===----------------------------------------------------------------------===//
 
 def PDLInterp_RecordMatchOp
     : PDLInterp_Op<"record_match", [AttrSizedOperandSegments, Terminator]> {
   let summary = "Record the metadata for a successful pattern match";
   let description = [{

mlir/lib/Conversion/PDLToPDLInterp/PDLToPDLInterp.cpp

void generateRewriter(pdl::AttributeOp attrOp,
                         DenseMap<Value, Value> &rewriteValues,
                         function_ref<Value(Value)> mapRewriteValue);
   void generateRewriter(pdl::EraseOp eraseOp,
                         DenseMap<Value, Value> &rewriteValues,
                         function_ref<Value(Value)> mapRewriteValue);
   void generateRewriter(pdl::OperationOp operationOp,
                         DenseMap<Value, Value> &rewriteValues,
                         function_ref<Value(Value)> mapRewriteValue);
+  void generateRewriter(pdl::RangeOp rangeOp,
+                        DenseMap<Value, Value> &rewriteValues,
+                        function_ref<Value(Value)> mapRewriteValue);
   void generateRewriter(pdl::ReplaceOp replaceOp,
                         DenseMap<Value, Value> &rewriteValues,
                         function_ref<Value(Value)> mapRewriteValue);
   void generateRewriter(pdl::ResultOp resultOp,
                         DenseMap<Value, Value> &rewriteValues,
                         function_ref<Value(Value)> mapRewriteValue);
   void generateRewriter(pdl::ResultsOp resultOp,
                         DenseMap<Value, Value> &rewriteValues,
if (StringAttr rewriteName = rewriter.getNameAttr()) {
     args.append(mappedArgs.begin(), mappedArgs.end());
     builder.create<pdl_interp::ApplyRewriteOp>(
         rewriter.getLoc(), /*resultTypes=*/TypeRange(), rewriteName, args);
   } else {
     // Otherwise this is a dag rewriter defined using PDL operations.
     for (Operation &rewriteOp : *rewriter.getBody()) {
       llvm::TypeSwitch<Operation *>(&rewriteOp)
           .Case<pdl::ApplyNativeRewriteOp, pdl::AttributeOp, pdl::EraseOp,
-                pdl::OperationOp, pdl::ReplaceOp, pdl::ResultOp, pdl::ResultsOp,
-                pdl::TypeOp, pdl::TypesOp>([&](auto op) {
+                pdl::OperationOp, pdl::RangeOp, pdl::ReplaceOp, pdl::ResultOp,
+                pdl::ResultsOp, pdl::TypeOp, pdl::TypesOp>([&](auto op) {
             this->generateRewriter(op, rewriteValues, mapRewriteValue);
           });
     }
   }
 
   // Update the signature of the rewrite function.
   rewriterFunc.setType(builder.getFunctionType(
       llvm::to_vector<8>(rewriterFunc.front().getArgumentTypes()),
for (const auto &it : llvm::enumerate(resultTys)) {
     else
       resultVal = builder.create<pdl_interp::GetResultOp>(
           loc, valueTy, createdOp, it.index());
     type = builder.create<pdl_interp::GetValueTypeOp>(loc, resultVal);
   }
 }
 
 void PatternLowering::generateRewriter(
+    pdl::RangeOp rangeOp, DenseMap<Value, Value> &rewriteValues,
+    function_ref<Value(Value)> mapRewriteValue) {
+  SmallVector<Value, 4> replOperands;
+  for (Value operand : rangeOp.getArguments())
+    replOperands.push_back(mapRewriteValue(operand));
+  rewriteValues[rangeOp] = builder.create<pdl_interp::CreateRangeOp>(
+      rangeOp.getLoc(), rangeOp.getType(), replOperands);
+}
+
+void PatternLowering::generateRewriter(
     pdl::ReplaceOp replaceOp, DenseMap<Value, Value> &rewriteValues,
     function_ref<Value(Value)> mapRewriteValue) {
   SmallVector<Value, 4> replOperands;
 
   // If the replacement was another operation, get its results. `pdl` allows
   // for using an operation for simplicitly, but the interpreter isn't as
   // user facing.
   if (Value replOp = replaceOp.getReplOperation()) {

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

 }
 
 /// The default dialect is `pdl`.
 StringRef PatternOp::getDefaultDialect() {
   return PDLDialect::getDialectNamespace();
 }
 
 //===----------------------------------------------------------------------===//
+// pdl::RangeOp
+//===----------------------------------------------------------------------===//
+
+static ParseResult parseRangeType(OpAsmParser &p, TypeRange argumentTypes,
+                                  Type &resultType) {
+  // If arguments were provided, infer the result type from the argument list.
+  if (!argumentTypes.empty()) {
+    resultType = RangeType::get(getRangeElementTypeOrSelf(argumentTypes[0]));
+    return success();
+  }
+  // Otherwise, parse the type as a trailing type.
+  return p.parseColonType(resultType);
+}
+
+static void printRangeType(OpAsmPrinter &p, RangeOp op, TypeRange argumentTypes,
+                           Type resultType) {
+  if (argumentTypes.empty())
+    p << ": " << resultType;
+}
+
+LogicalResult RangeOp::verify() {
+  Type elementType = getType().getElementType();
+  for (Type operandType : getOperandTypes()) {
+    Type operandElementType = getRangeElementTypeOrSelf(operandType);
+    if (operandElementType != elementType) {
+      return emitOpError("expected operand to have element type ")
+             << elementType << ", but got " << operandElementType;
+    }
+  }
+  return success();
+}
+
+//===----------------------------------------------------------------------===//
 // pdl::ReplaceOp
 //===----------------------------------------------------------------------===//
 
 LogicalResult ReplaceOp::verify() {
   if (getReplOperation() && !getReplValues().empty())
     return emitOpError() << "expected no replacement values to be provided"
                             " when the replacement operation is present";
   return success();

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

 //===----------------------------------------------------------------------===//
 // PDL Types
 //===----------------------------------------------------------------------===//
 
 bool PDLType::classof(Type type) {
   return llvm::isa<PDLDialect>(type.getDialect());
 }
 
+Type pdl::getRangeElementTypeOrSelf(Type type) {
+  if (auto rangeType = type.dyn_cast<RangeType>())
+    return rangeType.getElementType();
+  return type;
+}
+
 //===----------------------------------------------------------------------===//
 // RangeType
 //===----------------------------------------------------------------------===//
 
 Type RangeType::parse(AsmParser &parser) {
   if (parser.parseLess())
     return Type();
 

mlir/lib/Dialect/PDLInterp/IR/PDLInterp.cpp

 
 /// Given the result type of a `GetValueTypeOp`, return the expected input type.
 static Type getGetValueTypeOpValueType(Type type) {
   Type valueTy = pdl::ValueType::get(type.getContext());
   return type.isa<pdl::RangeType>() ? pdl::RangeType::get(valueTy) : valueTy;
 }
 
 //===----------------------------------------------------------------------===//
+// pdl::CreateRangeOp
+//===----------------------------------------------------------------------===//
+
+static ParseResult parseRangeType(OpAsmParser &p, TypeRange argumentTypes,
+                                  Type &resultType) {
+  // If arguments were provided, infer the result type from the argument list.
+  if (!argumentTypes.empty()) {
+    resultType =
+        pdl::RangeType::get(pdl::getRangeElementTypeOrSelf(argumentTypes[0]));
+    return success();
+  }
+  // Otherwise, parse the type as a trailing type.
+  return p.parseColonType(resultType);
+}
+
+static void printRangeType(OpAsmPrinter &p, CreateRangeOp op,
+                           TypeRange argumentTypes, Type resultType) {
+  if (argumentTypes.empty())
+    p << ": " << resultType;
+}
+
+LogicalResult CreateRangeOp::verify() {
+  Type elementType = getType().getElementType();
+  for (Type operandType : getOperandTypes()) {
+    Type operandElementType = pdl::getRangeElementTypeOrSelf(operandType);
+    if (operandElementType != elementType) {
+      return emitOpError("expected operand to have element type ")
+             << elementType << ", but got " << operandElementType;
+    }
+  }
+  return success();
+}
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::SwitchAttributeOp
 //===----------------------------------------------------------------------===//
 
 LogicalResult SwitchAttributeOp::verify() { return verifySwitchOp(*this); }
 
 //===----------------------------------------------------------------------===//
 // pdl_interp::SwitchOperandCountOp
 //===----------------------------------------------------------------------===//

mlir/lib/Rewrite/ByteCode.cpp

enum OpCode : ByteCodeField {
   /// 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,
   /// Continue to the next iteration of a loop.
   Continue,
+  /// Create a type range from a list of constant types.
+  CreateConstantTypeRange,
   /// Create an operation.
   CreateOperation,
-  /// Create a range of types.
-  CreateTypes,
+  /// Create a type range from a list of dynamic types.
+  CreateDynamicTypeRange,
+  /// Create a value range.
+  CreateDynamicValueRange,
   /// 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,
private:
   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::ContinueOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CreateAttributeOp op, ByteCodeWriter &writer);
   void generate(pdl_interp::CreateOperationOp op, ByteCodeWriter &writer);
+  void generate(pdl_interp::CreateRangeOp 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 Generator::generate(Operation *op, ByteCodeWriter &writer) {
   });
   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::CreateOperationOp, pdl_interp::CreateRangeOp,
+            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::GetResultOp, pdl_interp::GetResultsOp,
             pdl_interp::GetUsersOp, pdl_interp::GetValueTypeOp,
             pdl_interp::IsNotNullOp, pdl_interp::RecordMatchOp,
             pdl_interp::ReplaceOp, pdl_interp::SwitchAttributeOp,
             pdl_interp::SwitchTypeOp, pdl_interp::SwitchTypesOp,
void Generator::generate(pdl_interp::CreateOperationOp op,
 
   // Add the result types. If the operation has inferred results, we use a
   // marker "size" value. Otherwise, we add the list of explicit result types.
   if (op.getInferredResultTypes())
     writer.append(kInferTypesMarker);
   else
     writer.appendPDLValueList(op.getInputResultTypes());
 }
+void Generator::generate(pdl_interp::CreateRangeOp op, ByteCodeWriter &writer) {
+  // Append the correct opcode for the range type.
+  TypeSwitch<Type>(op.getType().getElementType())
+      .Case(
+          [&](pdl::TypeType) { writer.append(OpCode::CreateDynamicTypeRange); })
+      .Case([&](pdl::ValueType) {
+        writer.append(OpCode::CreateDynamicValueRange);
+      });
+
+  writer.append(op.getResult(), getRangeStorageIndex(op.getResult()));
+  writer.appendPDLValueList(op->getOperands());
+}
 void Generator::generate(pdl_interp::CreateTypeOp op, ByteCodeWriter &writer) {
   // Simply repoint the memory index of the result to the constant.
   getMemIndex(op.getResult()) = getMemIndex(op.getValue());
 }
 void Generator::generate(pdl_interp::CreateTypesOp op, ByteCodeWriter &writer) {
-  writer.append(OpCode::CreateTypes, op.getResult(),
+  writer.append(OpCode::CreateConstantTypeRange, op.getResult(),
                 getRangeStorageIndex(op.getResult()), op.getValue());
 }
 void Generator::generate(pdl_interp::EraseOp op, ByteCodeWriter &writer) {
   writer.append(OpCode::EraseOp, op.getInputOp());
 }
 void Generator::generate(pdl_interp::ExtractOp op, ByteCodeWriter &writer) {
   OpCode opCode =
       TypeSwitch<Type, OpCode>(op.getResult().getType())
private:
   void executeAreEqual();
   void executeAreRangesEqual();
   void executeBranch();
   void executeCheckOperandCount();
   void executeCheckOperationName();
   void executeCheckResultCount();
   void executeCheckTypes();
   void executeContinue();
+  void executeCreateConstantTypeRange();
   void executeCreateOperation(PatternRewriter &rewriter,
                               Location mainRewriteLoc);
-  void executeCreateTypes();
+  template <typename T>
+  void executeDynamicCreateRange(StringRef type);
   void executeEraseOp(PatternRewriter &rewriter);
   template <typename T, typename Range, PDLValue::Kind kind>
   void executeExtract();
   void executeFinalize();
   void executeForEach();
   void executeGetAttribute();
   void executeGetAttributeType();
   void executeGetDefiningOp();
private:
   template <typename ValueT, typename T>
   void readList(SmallVectorImpl<T> &list) {
     list.clear();
     for (unsigned i = 0, e = read(); i != e; ++i)
       list.push_back(read<ValueT>());
   }
 
   /// Read a list of values from the bytecode buffer. The values may be encoded
-  /// as either Value or ValueRange elements.
-  void readValueList(SmallVectorImpl<Value> &list) {
+  /// either as a single element or a range of elements.
+  void readList(SmallVectorImpl<Type> &list) {
+    for (unsigned i = 0, e = read(); i != e; ++i) {
+      if (read<PDLValue::Kind>() == PDLValue::Kind::Type) {
+        list.push_back(read<Type>());
+      } else {
+        TypeRange *values = read<TypeRange *>();
+        list.append(values->begin(), values->end());
+      }
+    }
+  }
+  void readList(SmallVectorImpl<Value> &list) {
     for (unsigned i = 0, e = read(); i != e; ++i) {
       if (read<PDLValue::Kind>() == PDLValue::Kind::Value) {
         list.push_back(read<Value>());
       } else {
         ValueRange *values = read<ValueRange *>();
         list.append(values->begin(), values->end());
       }
     }
private:
   std::enable_if_t<std::is_same<T, ByteCodeField>::value, T> readImpl() {
     return *curCodeIt++;
   }
   template <typename T>
   std::enable_if_t<std::is_same<T, PDLValue::Kind>::value, T> readImpl() {
     return static_cast<PDLValue::Kind>(readImpl<ByteCodeField>());
   }
 
+  /// Assign the given range to the given memory index. This allocates a new
+  /// range object if necessary.
+  template <typename RangeT, typename T = llvm::detail::ValueOfRange<RangeT>>
+  void assignRangeToMemory(RangeT &&range, unsigned memIndex,
+                           unsigned rangeIndex) {
+    // Utility functor used to type-erase the assignment.
+    auto assignRange = [&](auto &allocatedRangeMemory, auto &rangeMemory) {
+      // If the input range is empty, we don't need to allocate anything.
+      if (range.empty()) {
+        rangeMemory[rangeIndex] = {};
+      } else {
+        // Allocate a buffer for this type range.
+        llvm::OwningArrayRef<T> storage(llvm::size(range));
+        llvm::copy(range, storage.begin());
+
+        // Assign this to the range slot and use the range as the value for the
+        // memory index.
+        allocatedRangeMemory.emplace_back(std::move(storage));
+        rangeMemory[rangeIndex] = allocatedRangeMemory.back();
+      }
+      memory[memIndex] = &rangeMemory[rangeIndex];
+    };
+
+    // Dispatch based on the concrete range type.
+    if constexpr (std::is_same_v<T, Type>) {
+      return assignRange(allocatedTypeRangeMemory, typeRangeMemory);
+    } else if constexpr (std::is_same_v<T, Value>) {
+      return assignRange(allocatedValueRangeMemory, valueRangeMemory);
+    } else {
+      llvm_unreachable("unhandled range type");
+    }
+  }
+
   /// The underlying bytecode buffer.
   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;

 void ByteCodeExecutor::executeContinue() {
   ByteCodeField level = read();
   LLVM_DEBUG(llvm::dbgs() << "Executing Continue\n"
                           << "  * Level: " << level << "\n");
   ++loopIndex[level];
   popCodeIt();
 }
 
-void ByteCodeExecutor::executeCreateTypes() {
-  LLVM_DEBUG(llvm::dbgs() << "Executing CreateTypes:\n");
+void ByteCodeExecutor::executeCreateConstantTypeRange() {
+  LLVM_DEBUG(llvm::dbgs() << "Executing CreateConstantTypeRange:\n");
   unsigned memIndex = read();
   unsigned rangeIndex = read();
   ArrayAttr typesAttr = read<Attribute>().cast<ArrayAttr>();
 
   LLVM_DEBUG(llvm::dbgs() << "  * Types: " << typesAttr << "\n\n");
-
-  // Allocate a buffer for this type range.
-  llvm::OwningArrayRef<Type> storage(typesAttr.size());
-  llvm::copy(typesAttr.getAsValueRange<TypeAttr>(), storage.begin());
-  allocatedTypeRangeMemory.emplace_back(std::move(storage));
-
-  // Assign this to the range slot and use the range as the value for the
-  // memory index.
-  typeRangeMemory[rangeIndex] = allocatedTypeRangeMemory.back();
-  memory[memIndex] = &typeRangeMemory[rangeIndex];
+  assignRangeToMemory(typesAttr.getAsValueRange<TypeAttr>(), memIndex,
+                      rangeIndex);
 }
 
 void ByteCodeExecutor::executeCreateOperation(PatternRewriter &rewriter,
                                               Location mainRewriteLoc) {
   LLVM_DEBUG(llvm::dbgs() << "Executing CreateOperation:\n");
 
   unsigned memIndex = read();
   OperationState state(mainRewriteLoc, read<OperationName>());
-  readValueList(state.operands);
+  readList(state.operands);
   for (unsigned i = 0, e = read(); i != e; ++i) {
     StringAttr name = read<StringAttr>();
     if (Attribute attr = read<Attribute>())
       state.addAttribute(name, attr);
   }
 
   // Read in the result types. If the "size" is the sentinel value, this
   // indicates that the result types should be inferred.
llvm::dbgs() << "  * Attributes: "
                  << "\n  * Operands: ";
     llvm::interleaveComma(state.operands, llvm::dbgs());
     llvm::dbgs() << "\n  * Result Types: ";
     llvm::interleaveComma(state.types, llvm::dbgs());
     llvm::dbgs() << "\n  * Result: " << *resultOp << "\n";
   });
 }
 
+template <typename T>
+void ByteCodeExecutor::executeDynamicCreateRange(StringRef type) {
+  LLVM_DEBUG(llvm::dbgs() << "Executing CreateDynamic" << type << "Range:\n");
+  unsigned memIndex = read();
+  unsigned rangeIndex = read();
+  SmallVector<T> values;
+  readList(values);
+
+  LLVM_DEBUG({
+    llvm::dbgs() << "\n  * " << type << "s: ";
+    llvm::interleaveComma(values, llvm::dbgs());
+    llvm::dbgs() << "\n";
+  });
+
+  assignRangeToMemory(values, memIndex, rangeIndex);
+}
+
 void ByteCodeExecutor::executeEraseOp(PatternRewriter &rewriter) {
   LLVM_DEBUG(llvm::dbgs() << "Executing EraseOp:\n");
   Operation *op = read<Operation *>();
 
   LLVM_DEBUG(llvm::dbgs() << "  * Operation: " << *op << "\n");
   rewriter.eraseOp(op);
 }
 
void ByteCodeExecutor::executeRecordMatch(
   }
   curCodeIt = dest;
 }
 
 void ByteCodeExecutor::executeReplaceOp(PatternRewriter &rewriter) {
   LLVM_DEBUG(llvm::dbgs() << "Executing ReplaceOp:\n");
   Operation *op = read<Operation *>();
   SmallVector<Value, 16> args;
-  readValueList(args);
+  readList(args);
 
   LLVM_DEBUG({
     llvm::dbgs() << "  * Operation: " << *op << "\n"
                  << "  * Values: ";
     llvm::interleaveComma(args, llvm::dbgs());
     llvm::dbgs() << "\n";
   });
   rewriter.replaceOp(op, args);
case CheckResultCount:
       executeCheckResultCount();
       break;
     case CheckTypes:
       executeCheckTypes();
       break;
     case Continue:
       executeContinue();
       break;
+    case CreateConstantTypeRange:
+      executeCreateConstantTypeRange();
+      break;
     case CreateOperation:
       executeCreateOperation(rewriter, *mainRewriteLoc);
       break;
-    case CreateTypes:
-      executeCreateTypes();
+    case CreateDynamicTypeRange:
+      executeDynamicCreateRange<Type>("Type");
+      break;
+    case CreateDynamicValueRange:
+      executeDynamicCreateRange<Value>("Value");
       break;
     case EraseOp:
       executeEraseOp(rewriter);
       break;
     case ExtractOp:
       executeExtract<Operation *, OwningOpRange, PDLValue::Kind::Operation>();
       break;
     case ExtractType:

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

pdl.pattern : benefit(1) {
     %root = operation "foo.op"
     rewrite %root {
       %unused = operation "bar.op"
     }
   }
 }
 
 // -----
+
+// CHECK-LABEL: module @range_op
+module @range_op {
+  // CHECK: module @rewriters
+  // CHECK:   func @pdl_generated_rewriter(%[[OPERAND:.*]]: !pdl.value)
+  // CHECK:     %[[RANGE1:.*]] = pdl_interp.create_range : !pdl.range<value>
+  // CHECK:     %[[RANGE2:.*]] = pdl_interp.create_range %[[OPERAND]], %[[RANGE1]] : !pdl.value, !pdl.range<value>
+  // CHECK:     pdl_interp.finalize
+  pdl.pattern : benefit(1) {
+    %operand = pdl.operand
+    %root = operation "foo.op"(%operand : !pdl.value)
+    rewrite %root {
+      %emptyRange = pdl.range : !pdl.range<value>
+      %range = pdl.range %operand, %emptyRange : !pdl.value, !pdl.range<value>
+    }
+  }
+}

mlir/test/Dialect/PDL/invalid.mlir

"pdl.replace"(%root, %newOp, %newResult) {
       operand_segment_sizes = array<i32: 1, 1, 1>
     } : (!pdl.operation, !pdl.operation, !pdl.value) -> ()
   }
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
+// pdl::RangeOp
+//===----------------------------------------------------------------------===//
+
+pdl.pattern : benefit(1) {
+  %operand = pdl.operand
+  %resultType = pdl.type
+  %root = pdl.operation "baz.op"(%operand : !pdl.value) -> (%resultType : !pdl.type)
+  
+  rewrite %root {
+    // expected-error @below {{expected operand to have element type '!pdl.value', but got '!pdl.type'}}
+    %range = pdl.range %operand, %resultType : !pdl.value, !pdl.type
+  }
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
 // pdl::ResultsOp
 //===----------------------------------------------------------------------===//
 
 pdl.pattern : benefit(1) {
   %root = operation "foo.op"
   // expected-error@below {{expected `pdl.range<value>` result type when no index is specified, but got: '!pdl.value'}}
   %results = "pdl.results"(%root) : (!pdl.operation) -> !pdl.value
   rewrite %root with "rewriter"

mlir/test/Dialect/PDLInterp/invalid.mlir

 // RUN: mlir-opt %s -split-input-file -verify-diagnostics
 
 //===----------------------------------------------------------------------===//
-// pdl::CreateOperationOp
+// pdl_interp::CreateOperationOp
 //===----------------------------------------------------------------------===//
 
 pdl_interp.func @rewriter() {
   // expected-error@+1 {{op has inferred results, but the created operation 'foo.op' does not support result type inference}}
   %op = pdl_interp.create_operation "foo.op" -> <inferred>
   pdl_interp.finalize
 }
 
 // -----
 
 pdl_interp.func @rewriter() {
   %type = pdl_interp.create_type i32
   // expected-error@+1 {{op with inferred results cannot also have explicit result types}}
   %op = "pdl_interp.create_operation"(%type) {
     inferredResultTypes,
     inputAttributeNames = [],
     name = "foo.op",
     operand_segment_sizes = array<i32: 0, 0, 1>
   } : (!pdl.type) -> (!pdl.operation)
   pdl_interp.finalize
 }
+
+// -----
+
+//===----------------------------------------------------------------------===//
+// pdl_interp::CreateRangeOp
+//===----------------------------------------------------------------------===//
+
+pdl_interp.func @rewriter(%value: !pdl.value, %type: !pdl.type) {
+  // expected-error @below {{expected operand to have element type '!pdl.value', but got '!pdl.type'}}
+  %range = pdl_interp.create_range %value, %type : !pdl.value, !pdl.type
+  pdl_interp.finalize
+}

mlir/test/Rewrite/pdl-bytecode.mlir

 // CHECK: "test.success"(%[[CST]])
 module @ir attributes { test.create_op_infer_results } {
   %results:2 = "test.op"() : () -> (i64, i64)
 }
 
 // -----
 
 //===----------------------------------------------------------------------===//
+// pdl_interp::CreateRangeOp
+//===----------------------------------------------------------------------===//
+
+module @patterns {
+  pdl_interp.func @matcher(%root : !pdl.operation) {
+    pdl_interp.check_operand_count of %root is 2 -> ^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) {
+      %rootOperand = pdl_interp.get_operand 0 of %root
+      %rootOperands = pdl_interp.get_operands of %root : !pdl.range<value>
+      %operandRange = pdl_interp.create_range %rootOperand, %rootOperands : !pdl.value, !pdl.range<value>
+      
+      %operandType = pdl_interp.get_value_type of %rootOperand : !pdl.type
+      %operandTypes = pdl_interp.get_value_type of %rootOperands : !pdl.range<type>
+      %typeRange = pdl_interp.create_range %operandType, %operandTypes : !pdl.type, !pdl.range<type>
+
+      %op = pdl_interp.create_operation "test.success"(%operandRange : !pdl.range<value>) -> (%typeRange : !pdl.range<type>)
+      pdl_interp.erase %root
+      pdl_interp.finalize
+    }
+  }
+}
+
+// CHECK-LABEL: test.create_range_1
+// CHECK: %[[INPUTS:.*]]:2 = "test.input"()
+// CHECK: "test.success"(%[[INPUTS]]#0, %[[INPUTS]]#0, %[[INPUTS]]#1) : (i32, i32, i32) -> (i32, i32, i32)
+module @ir attributes { test.create_range_1 } {
+  %values:2 = "test.input"() : () -> (i32, i32)
+  "test.op"(%values#0, %values#1) : (i32, i32) -> ()
+}
+
+// -----
+
+//===----------------------------------------------------------------------===//
 // pdl_interp::CreateTypeOp
 //===----------------------------------------------------------------------===//
 
 module @patterns {
   pdl_interp.func @matcher(%root : !pdl.operation) {
     %attr = pdl_interp.get_attribute "test_attr" of %root
     pdl_interp.is_not_null %attr : !pdl.attribute -> ^pat1, ^end