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