mlir/docs/DialectConversion.md

   1 # Dialect Conversion
   2
   3 This document describes a framework in MLIR in which to perform operation
   4 conversions between, and within dialects. This framework allows for transforming
   5 illegal operations to those supported by a provided conversion target, via a set
   6 of pattern-based operation rewriting patterns.
   7
   8 The dialect conversion framework consists of the following components:
   9
  10 *   A [Conversion Target](#conversion-target)
  11 *   A set of [Rewrite Patterns](#rewrite-pattern-specification)
  12 *   A [Type Converter](#type-conversion) (Optional)
  13
  14 [TOC]
  15
  16 ## Modes of Conversion
  17
  18 When applying a conversion to a set of operations, there are several different
  19 conversion modes that may be selected from:
  20
  21 *   Partial Conversion
  22
  23     -   A partial conversion will legalize as many operations to the target as
  24         possible, but will allow pre-existing operations that were not
  25         explicitly marked as "illegal" to remain unconverted. This allows for
  26         partially lowering parts of the input in the presence of unknown
  27         operations.
  28     -   A partial conversion can be applied via `applyPartialConversion`.
  29
  30 *   Full Conversion
  31
  32     -   A full conversion legalizes all input operations, and is only successful
  33         if all operations are properly legalized to the given conversion target.
  34         This ensures that only known operations will exist after the conversion
  35         process.
  36     -   A full conversion can be applied via `applyFullConversion`.
  37
  38 *   Analysis Conversion
  39
  40     -   An analysis conversion will analyze which operations are legalizable to
  41         the given conversion target if a conversion were to be applied. This is
  42         done by performing a 'partial' conversion and recording which operations
  43         would have been successfully converted if successful. Note that no
  44         rewrites, or transformations, are actually applied to the input
  45         operations.
  46     -   An analysis conversion can be applied via `applyAnalysisConversion`.
  47
  48 In all cases, the framework walks the operations in preorder, examining an op
  49 before the ops in any regions it has.
  50
  51 ## Conversion Target
  52
  53 The conversion target is a formal definition of what is considered to be legal
  54 during the conversion process. The final operations generated by the conversion
  55 framework must be marked as legal on the `ConversionTarget` for the rewrite to
  56 be a success. Depending on the conversion mode, existing operations need not
  57 always be legal. Operations and dialects may be marked with any of the provided
  58 legality actions below:
  59
  60 *   Legal
  61
  62     -   This action signals that every instance of a given operation is legal,
  63         i.e. any combination of attributes, operands, types, etc. are valid.
  64
  65 *   Dynamic
  66
  67     -   This action signals that only some instances of a given operation are
  68         legal. This allows for defining fine-tune constraints, e.g. saying that
  69         `arith.addi` is only legal when operating on 32-bit integers.
  70
  71 *   Illegal
  72
  73     -   This action signals that no instance of a given operation is legal.
  74         Operations marked as "illegal" must always be converted for the
  75         conversion to be successful. This action also allows for selectively
  76         marking specific operations as illegal in an otherwise legal dialect.
  77
  78 Operations and dialects that are neither explicitly marked legal nor illegal are
  79 separate from the above ("unknown" operations) and are treated differently, for
  80 example, for the purposes of partial conversion as mentioned above.
  81
  82 An example conversion target is shown below:
  83
  84 ```c++
  85 struct MyTarget : public ConversionTarget {
  86   MyTarget(MLIRContext &ctx) : ConversionTarget(ctx) {
  87     //--------------------------------------------------------------------------
  88     // Marking an operation as Legal:
  89
  90     /// Mark all operations within the LLVM dialect are legal.
  91     addLegalDialect<LLVMDialect>();
  92
  93     /// Mark `arith.constant` op is always legal on this target.
  94     addLegalOp<arith::ConstantOp>();
  95
  96     //--------------------------------------------------------------------------
  97     // Marking an operation as dynamically legal.
  98
  99     /// Mark all operations within Affine dialect have dynamic legality
 100     /// constraints.
 101     addDynamicallyLegalDialect<affine::AffineDialect>(
 102         [](Operation *op) { ... });
 103
 104     /// Mark `func.return` as dynamically legal, but provide a specific legality
 105     /// callback.
 106     addDynamicallyLegalOp<func::ReturnOp>([](func::ReturnOp op) { ... });
 107
 108     /// Treat unknown operations, i.e. those without a legalization action
 109     /// directly set, as dynamically legal.
 110     markUnknownOpDynamicallyLegal([](Operation *op) { ... });
 111
 112     //--------------------------------------------------------------------------
 113     // Marking an operation as illegal.
 114
 115     /// All operations within the GPU dialect are illegal.
 116     addIllegalDialect<GPUDialect>();
 117
 118     /// Mark `cf.br` and `cf.cond_br` as illegal.
 119     addIllegalOp<cf::BranchOp, cf::CondBranchOp>();
 120   }
 121
 122   /// Implement the default legalization handler to handle operations marked as
 123   /// dynamically legal that were not provided with an explicit handler.
 124   bool isDynamicallyLegal(Operation *op) override { ... }
 125 };
 126 ```
 127
 128 ### Recursive Legality
 129
 130 In some cases, it may be desirable to mark entire regions as legal. This
 131 provides an additional granularity of context to the concept of "legal". If an
 132 operation is marked recursively legal, either statically or dynamically, then
 133 all of the operations nested within are also considered legal even if they would
 134 otherwise be considered "illegal". An operation can be marked via
 135 `markOpRecursivelyLegal<>`:
 136
 137 ```c++
 138 ConversionTarget &target = ...;
 139
 140 /// The operation must first be marked as `Legal` or `Dynamic`.
 141 target.addLegalOp<MyOp>(...);
 142 target.addDynamicallyLegalOp<MySecondOp>(...);
 143
 144 /// Mark the operation as always recursively legal.
 145 target.markOpRecursivelyLegal<MyOp>();
 146 /// Mark optionally with a callback to allow selective marking.
 147 target.markOpRecursivelyLegal<MyOp, MySecondOp>([](Operation *op) { ... });
 148 /// Mark optionally with a callback to allow selective marking.
 149 target.markOpRecursivelyLegal<MyOp>([](MyOp op) { ... });
 150 ```
 151
 152 ## Rewrite Pattern Specification
 153
 154 After the conversion target has been defined, a set of legalization patterns
 155 must be provided to transform illegal operations into legal ones. The patterns
 156 supplied here have the same structure and restrictions as those described in the
 157 main [Pattern](PatternRewriter.md) documentation. The patterns provided do not
 158 need to generate operations that are directly legal on the target. The framework
 159 will automatically build a graph of conversions to convert non-legal operations
 160 into a set of legal ones.
 161
 162 As an example, say you define a target that supports one operation: `foo.add`.
 163 When providing the following patterns: [`bar.add` -> `baz.add`, `baz.add` ->
 164 `foo.add`], the framework will automatically detect that it can legalize
 165 `bar.add` -> `foo.add` even though a direct conversion does not exist. This
 166 means that you don’t have to define a direct legalization pattern for `bar.add`
 167 -> `foo.add`.
 168
 169 ### Conversion Patterns
 170
 171 Along with the general `RewritePattern` classes, the conversion framework
 172 provides a special type of rewrite pattern that can be used when a pattern
 173 relies on interacting with constructs specific to the conversion process, the
 174 `ConversionPattern`. For example, the conversion process does not necessarily
 175 update operations in-place and instead creates a mapping of events such as
 176 replacements and erasures, and only applies them when the entire conversion
 177 process is successful. Certain classes of patterns rely on using the
 178 updated/remapped operands of an operation, such as when the types of results
 179 defined by an operation have changed. The general Rewrite Patterns can no longer
 180 be used in these situations, as the types of the operands of the operation being
 181 matched will not correspond with those expected by the user. This pattern
 182 provides, as an additional argument to the `matchAndRewrite` and `rewrite`
 183 methods, the list of operands that the operation should use after conversion. If
 184 an operand was the result of a non-converted operation, for example if it was
 185 already legal, the original operand is used. This means that the operands
 186 provided always have a 1-1 non-null correspondence with the operands on the
 187 operation. The original operands of the operation are still intact and may be
 188 inspected as normal. These patterns also utilize a special `PatternRewriter`,
 189 `ConversionPatternRewriter`, that provides special hooks for use with the
 190 conversion infrastructure.
 191
 192 ```c++
 193 struct MyConversionPattern : public ConversionPattern {
 194   /// The `matchAndRewrite` hooks on ConversionPatterns take an additional
 195   /// `operands` parameter, containing the remapped operands of the original
 196   /// operation.
 197   virtual LogicalResult
 198   matchAndRewrite(Operation *op, ArrayRef<Value> operands,
 199                   ConversionPatternRewriter &rewriter) const;
 200 };
 201 ```
 202
 203 #### Type Safety
 204
 205 The types of the remapped operands provided to a conversion pattern must be of a
 206 type expected by the pattern. The expected types of a pattern are determined by
 207 a provided [TypeConverter](#type-converter). If no type converter is provided,
 208 the types of the remapped operands are expected to match the types of the
 209 original operands. If a type converter is provided, the types of the remapped
 210 operands are expected to be legal as determined by the converter. If the
 211 remapped operand types are not of an expected type, and a materialization to the
 212 expected type could not be performed, the pattern fails application before the
 213 `matchAndRewrite` hook is invoked. This ensures that patterns do not have to
 214 explicitly ensure type safety, or sanitize the types of the incoming remapped
 215 operands. More information on type conversion is detailed in the
 216 [dedicated section](#type-conversion) below.
 217
 218 ## Type Conversion
 219
 220 It is sometimes necessary as part of a conversion to convert the set types of
 221 being operated on. In these cases, a `TypeConverter` object may be defined that
 222 details how types should be converted when interfacing with a pattern. A
 223 `TypeConverter` may be used to convert the signatures of block arguments and
 224 regions, to define the expected inputs types of the pattern, and to reconcile
 225 type differences in general.
 226
 227 ### Type Converter
 228
 229 The `TypeConverter` contains several hooks for detailing how to convert types,
 230 and how to materialize conversions between types in various situations. The two
 231 main aspects of the `TypeConverter` are conversion and materialization.
 232
 233 A `conversion` describes how a given illegal source `Type` should be converted
 234 to N target types. If the source type is already "legal", it should convert to
 235 itself. Type conversions are specified via the `addConversion` method described
 236 below.
 237
 238 A `materialization` describes how a set of values should be converted to a
 239 single value of a desired type. An important distinction with a `conversion` is
 240 that a `materialization` can produce IR, whereas a `conversion` cannot. These
 241 materializations are used by the conversion framework to ensure type safety
 242 during the conversion process. There are several types of materializations
 243 depending on the situation.
 244
 245 *   Argument Materialization
 246
 247     -   An argument materialization is used when converting the type of a block
 248         argument during a [signature conversion](#region-signature-conversion).
 249         The new block argument types are specified in a `SignatureConversion`
 250         object. An original block argument can be converted into multiple
 251         block arguments, which is not supported everywhere in the dialect
 252         conversion. (E.g., adaptors support only a single replacement value for
 253         each original value.) Therefore, an argument materialization is used to
 254         convert potentially multiple new block arguments back into a single SSA
 255         value.
 256
 257 *   Source Materialization
 258
 259     -   A source materialization converts from a value with a "legal" target
 260         type, back to a specific source type. This is used when an operation is
 261         "legal" during the conversion process, but contains a use of an illegal
 262         type. This may happen during a conversion where some operations are
 263         converted to those with different resultant types, but still retain
 264         users of the original type system.
 265     -   This materialization is used in the following situations:
 266         *   When a block argument has been converted to a different type, but
 267             the original argument still has users that will remain live after
 268             the conversion process has finished.
 269         *   When a block argument has been dropped, but the argument still has
 270             users that will remain live after the conversion process has
 271             finished.
 272         *   When the result type of an operation has been converted to a
 273             different type, but the original result still has users that will
 274             remain live after the conversion process is finished.
 275
 276 *   Target Materialization
 277
 278     -   A target materialization converts from a value with an "illegal" source
 279         type, to a value of a "legal" type. This is used when a pattern expects
 280         the remapped operands to be of a certain set of types, but the original
 281         input operands have not been converted. This may happen during a
 282         conversion where some operations are converted to those with different
 283         resultant types, but still retain uses of the original type system.
 284     -   This materialization is used in the following situations:
 285         *   When the remapped operands of a
 286             [conversion pattern](#conversion-patterns) are not legal for the
 287             type conversion provided by the pattern.
 288
 289 If a converted value is used by an operation that isn't converted, it needs a
 290 conversion back to the `source` type, hence source materialization; if an
 291 unconverted value is used by an operation that is being converted, it needs
 292 conversion to the `target` type, hence target materialization.
 293
 294 As noted above, the conversion process guarantees that the type contract of the
 295 IR is preserved during the conversion. This means that the types of value uses
 296 will not implicitly change during the conversion process. When the type of a
 297 value definition, either block argument or operation result, is being changed,
 298 the users of that definition must also be updated during the conversion process.
 299 If they aren't, a type conversion must be materialized to ensure that a value of
 300 the expected type is still present within the IR. If a target materialization is
 301 required, but cannot be performed, the pattern application fails. If a source
 302 materialization is required, but cannot be performed, the entire conversion
 303 process fails.
 304
 305 Several of the available hooks are detailed below:
 306
 307 ```c++
 308 class TypeConverter {
 309  public:
 310   /// Register a conversion function. A conversion function defines how a given
 311   /// source type should be converted. A conversion function must be convertible
 312   /// to any of the following forms(where `T` is a class derived from `Type`:
 313   ///   * Optional<Type>(T)
 314   ///     - This form represents a 1-1 type conversion. It should return nullptr
 315   ///       or `std::nullopt` to signify failure. If `std::nullopt` is returned, the
 316   ///       converter is allowed to try another conversion function to perform
 317   ///       the conversion.
 318   ///   * Optional<LogicalResult>(T, SmallVectorImpl<Type> &)
 319   ///     - This form represents a 1-N type conversion. It should return
 320   ///       `failure` or `std::nullopt` to signify a failed conversion. If the new
 321   ///       set of types is empty, the type is removed and any usages of the
 322   ///       existing value are expected to be removed during conversion. If
 323   ///       `std::nullopt` is returned, the converter is allowed to try another
 324   ///       conversion function to perform the conversion.
 325   ///   * Optional<LogicalResult>(T, SmallVectorImpl<Type> &, ArrayRef<Type>)
 326   ///     - This form represents a 1-N type conversion supporting recursive
 327   ///       types. The first two arguments and the return value are the same as
 328   ///       for the regular 1-N form. The third argument is contains is the
 329   ///       "call stack" of the recursive conversion: it contains the list of
 330   ///       types currently being converted, with the current type being the
 331   ///       last one. If it is present more than once in the list, the
 332   ///       conversion concerns a recursive type.
 333   /// Note: When attempting to convert a type, e.g. via 'convertType', the
 334   ///       mostly recently added conversions will be invoked first.
 335   template <typename FnT,
 336             typename T = typename llvm::function_traits<FnT>::template arg_t<0>>
 337   void addConversion(FnT &&callback) {
 338     registerConversion(wrapCallback<T>(std::forward<FnT>(callback)));
 339   }
 340
 341   /// All of the following materializations require function objects that are
 342   /// convertible to the following form:
 343   ///   `std::optional<Value>(OpBuilder &, T, ValueRange, Location)`,
 344   /// where `T` is any subclass of `Type`. This function is responsible for
 345   /// creating an operation, using the OpBuilder and Location provided, that
 346   /// "casts" a range of values into a single value of the given type `T`. It
 347   /// must return a Value of the converted type on success, an `std::nullopt` if
 348   /// it failed but other materialization can be attempted, and `nullptr` on
 349   /// unrecoverable failure. It will only be called for (sub)types of `T`.
 350   /// Materialization functions must be provided when a type conversion may
 351   /// persist after the conversion has finished.
 352
 353   /// This method registers a materialization that will be called when
 354   /// converting (potentially multiple) block arguments that were the result of
 355   /// a signature conversion of a single block argument, to a single SSA value
 356   /// with the old argument type.
 357   template <typename FnT,
 358             typename T = typename llvm::function_traits<FnT>::template arg_t<1>>
 359   void addArgumentMaterialization(FnT &&callback) {
 360     argumentMaterializations.emplace_back(
 361         wrapMaterialization<T>(std::forward<FnT>(callback)));
 362   }
 363
 364   /// This method registers a materialization that will be called when
 365   /// converting a legal replacement value back to an illegal source type.
 366   /// This is used when some uses of the original, illegal value must persist
 367   /// beyond the main conversion.
 368   template <typename FnT,
 369             typename T = typename llvm::function_traits<FnT>::template arg_t<1>>
 370   void addSourceMaterialization(FnT &&callback) {
 371     sourceMaterializations.emplace_back(
 372         wrapMaterialization<T>(std::forward<FnT>(callback)));
 373   }
 374
 375   /// This method registers a materialization that will be called when
 376   /// converting an illegal (source) value to a legal (target) type.
 377   template <typename FnT,
 378             typename T = typename llvm::function_traits<FnT>::template arg_t<1>>
 379   void addTargetMaterialization(FnT &&callback) {
 380     targetMaterializations.emplace_back(
 381         wrapMaterialization<T>(std::forward<FnT>(callback)));
 382   }
 383 };
 384 ```
 385
 386 Materializations through the type converter are optional. If the
 387 `ConversionConfig::buildMaterializations` flag is set to "false", the dialect
 388 conversion driver builds an `unrealized_conversion_cast` op instead of calling
 389 the respective type converter callback whenever a materialization is required.
 390
 391 ### Region Signature Conversion
 392
 393 From the perspective of type conversion, the types of block arguments are a bit
 394 special. Throughout the conversion process, blocks may move between regions of
 395 different operations. Given this, the conversion of the types for blocks must be
 396 done explicitly via a conversion pattern.
 397
 398 To convert the types of block arguments within a Region, a custom hook on the
 399 `ConversionPatternRewriter` must be invoked; `convertRegionTypes`. This hook
 400 uses a provided type converter to apply type conversions to all blocks of a
 401 given region. As noted above, the conversions performed by this method use the
 402 argument materialization hook on the `TypeConverter`. This hook also takes an
 403 optional `TypeConverter::SignatureConversion` parameter that applies a custom
 404 conversion to the entry block of the region. The types of the entry block
 405 arguments are often tied semantically to the operation, e.g.,
 406 `func::FuncOp`, `AffineForOp`, etc.
 407
 408 To convert the signature of just one given block, the
 409 `applySignatureConversion` hook can be used.
 410
 411 A signature conversion, `TypeConverter::SignatureConversion`, can be built
 412 programmatically:
 413
 414 ```c++
 415 class SignatureConversion {
 416 public:
 417     /// Remap an input of the original signature with a new set of types. The
 418     /// new types are appended to the new signature conversion.
 419     void addInputs(unsigned origInputNo, ArrayRef<Type> types);
 420
 421     /// Append new input types to the signature conversion, this should only be
 422     /// used if the new types are not intended to remap an existing input.
 423     void addInputs(ArrayRef<Type> types);
 424
 425     /// Remap an input of the original signature with a range of types in the
 426     /// new signature.
 427     void remapInput(unsigned origInputNo, unsigned newInputNo,
 428                     unsigned newInputCount = 1);
 429
 430     /// Remap an input of the original signature to another `replacement`
 431     /// value. This drops the original argument.
 432     void remapInput(unsigned origInputNo, Value replacement);
 433 };
 434 ```
 435
 436 The `TypeConverter` provides several default utilities for signature conversion
 437 and legality checking:
 438 `convertSignatureArgs`/`convertBlockSignature`/`isLegal(Region *|Type)`.
 439
 440 ## Debugging
 441
 442 To debug the execution of the dialect conversion framework,
 443 `-debug-only=dialect-conversion` may be used. This command line flag activates
 444 LLVM's debug logging infrastructure solely for the conversion framework. The
 445 output is formatted as a tree structure, mirroring the structure of the
 446 conversion process. This output contains all of the actions performed by the
 447 rewriter, how generated operations get legalized, and why they fail.
 448
 449 Example output is shown below:
 450
 451 ```
 452 //===-------------------------------------------===//
 453 Legalizing operation : 'func.return'(0x608000002e20) {
 454   "func.return"() : () -> ()
 455
 456   * Fold {
 457   } -> FAILURE : unable to fold
 458
 459   * Pattern : 'func.return -> ()' {
 460     ** Insert  : 'spirv.Return'(0x6070000453e0)
 461     ** Replace : 'func.return'(0x608000002e20)
 462
 463     //===-------------------------------------------===//
 464     Legalizing operation : 'spirv.Return'(0x6070000453e0) {
 465       "spirv.Return"() : () -> ()
 466
 467     } -> SUCCESS : operation marked legal by the target
 468     //===-------------------------------------------===//
 469   } -> SUCCESS : pattern applied successfully
 470 } -> SUCCESS
 471 //===-------------------------------------------===//
 472 ```
 473
 474 This output is describing the legalization of an `func.return` operation. We
 475 first try to legalize by folding the operation, but that is unsuccessful for
 476 `func.return`. From there, a pattern is applied that replaces the `func.return`
 477 with a `spirv.Return`. The newly generated `spirv.Return` is then processed for
 478 legalization, but is found to already legal as per the target.