diff --git a/mlir/docs/DialectConversion.md b/mlir/docs/DialectConversion.md --- a/mlir/docs/DialectConversion.md +++ b/mlir/docs/DialectConversion.md @@ -7,7 +7,7 @@ [TOC] -To utilize the framework, a few things must be provided: +The dialect conversion framework consists of the following components: * A [Conversion Target](#conversion-target) * A set of [Rewrite Patterns](#rewrite-pattern-specification) @@ -15,41 +15,44 @@ ## Modes of Conversion -When applying a conversion to a set of operations, there are several conversion -modes that can be selected from: +When applying a conversion to a set of operations, there are several different +conversion modes that may be selected from: * Partial Conversion - A partial conversion will legalize as many operations to the target as possible, but will allow pre-existing operations that were not - explicitly marked as `illegal` to remain unconverted. This allows for - partially lowering parts of the module in the presence of unknown + explicitly marked as "illegal" to remain unconverted. This allows for + partially lowering parts of the input in the presence of unknown operations. - A partial conversion can be applied via `applyPartialConversion`. * Full Conversion - - A full conversion is only successful if all operations are properly - legalized to the given conversion target. This ensures that only known - operations will exist after the conversion process. + - A full conversion legalizes all input operations, and is only successful + if all operations are properly legalized to the given conversion target. + This ensures that only known operations will exist after the conversion + process. - A full conversion can be applied via `applyFullConversion`. * Analysis Conversion - An analysis conversion will analyze which operations are legalizable to - the given conversion target if a conversion were to be applied. Note - that no rewrites, or transformations, are actually applied to the input + the given conversion target if a conversion were to be applied. This is + done by performing a 'partial' conversion and recording which operations + would have been successfully converted if successful. Note that no + rewrites, or transformations, are actually applied to the input operations. - An analysis conversion can be applied via `applyAnalysisConversion`. ## Conversion Target -The conversion target is the formal definition of what is considered to be legal +The conversion target is a formal definition of what is considered to be legal during the conversion process. The final operations generated by the conversion framework must be marked as legal on the `ConversionTarget` for the rewrite to -be a success. Existing operations need not always be legal, though; see the -different conversion modes for why. Operations and dialects may be marked with -any of the provided legality actions below: +be a success. Depending on the conversion mode, existing operations need not +always be legal. Operations and dialects may be marked with any of the provided +legality actions below: * Legal @@ -68,7 +71,7 @@ * Illegal - This action signals that no instance of a given operation is legal. - Operations marked as `illegal` must always be converted for the + Operations marked as "illegal" must always be converted for the conversion to be successful. This action also allows for selectively marking specific operations as illegal in an otherwise legal dialect. @@ -123,13 +126,12 @@ ### Recursive Legality -In some cases, it may be desirable to mark entire regions of operations as -legal. This provides an additional granularity of context to the concept of -"legal". The `ConversionTarget` supports marking operations, that were -previously added as `Legal` or `Dynamic`, as `recursively` legal. Recursive -legality means that if an operation instance is legal, either statically or -dynamically, all of the operations nested within are also considered legal. An -operation can be marked via `markOpRecursivelyLegal<>`: +In some cases, it may be desirable to mark entire regions as legal. This +provides an additional granularity of context to the concept of "legal". If an +operation is marked recursively legal, either statically or dynamically, then +all of the operations nested within are also considered legal even if they would +otherwise be considered "illegal". An operation can be marked via +`markOpRecursivelyLegal<>`: ```c++ ConversionTarget &target = ...; @@ -149,14 +151,12 @@ ## Rewrite Pattern Specification After the conversion target has been defined, a set of legalization patterns -must be provided to transform illegal operations into legal ones. The patterns -supplied here, that do not [require type changes](#conversion-patterns), are the -same as those described in the -[quickstart rewrites guide](Tutorials/QuickstartRewrites.md#adding-patterns), but have a -few additional [restrictions](#restrictions). The patterns provided do not need -to generate operations that are directly legal on the target. The framework will -automatically build a graph of conversions to convert non-legal operations into -a set of legal ones. +must be provided to transform illegal operations into legal ones. The structure +of the patterns supplied here is the same as those described in the +[quickstart rewrites guide](Tutorials/QuickstartRewrites.md#adding-patterns). +The patterns provided do not need to generate operations that are directly legal +on the target. The framework will automatically build a graph of conversions to +convert non-legal operations into a set of legal ones. As an example, say you define a target that supports one operation: `foo.add`. When providing the following patterns: [`bar.add` -> `baz.add`, `baz.add` -> @@ -165,38 +165,139 @@ means that you don’t have to define a direct legalization pattern for `bar.add` -> `foo.add`. -### Restrictions +### Conversion Patterns + +Along with the general `RewritePattern` classes, the conversion framework +provides a special type of rewrite pattern that can be used when a pattern +relies on interacting with constructs specific to the conversion process, the +`ConversionPattern`. For example, the conversion process does not necessarily +update operations in-place and instead creates a mapping of events such as +replacements and erasures, and only applies them when the entire conversion +process is successful. Certain classes of patterns rely on using the +updated/remapped operands of an operation, such as when the types of results +defined by an operation have changed. The general Rewrite Patterns can no longer +be used in these situations, as the types of the operands of the operation being +matched will not correspond with those expected by the user. This pattern +provides, as an additional argument to the `matchAndRewrite` and `rewrite` +methods, the list of operands that the operation should use after conversion. If +an operand was the result of a non-converted operation, for example if it was +already legal, the original operand is used. This means that the operands +provided always have a 1-1 non-null correspondence with the operands on the +operation. The original operands of the operation are still intact and may be +inspected as normal. These patterns also utilize a special `PatternRewriter`, +`ConversionPatternRewriter`, that provides special hooks for use with the +conversion infrastructure. -The framework processes operations in topological order, trying to legalize them -individually. As such, patterns used in the conversion framework have a few -additional restrictions: +```c++ +struct MyConversionPattern : public ConversionPattern { + /// The `matchAndRewrite` hooks on ConversionPatterns take an additional + /// `operands` parameter, containing the remapped operands of the original + /// operation. + virtual LogicalResult + matchAndRewrite(Operation *op, ArrayRef operands, + ConversionPatternRewriter &rewriter) const; +}; +``` -1. If a pattern matches, it must erase or replace the op it matched on. - Operations can *not* be updated in place. -2. Match criteria should not be based on the IR outside of the op itself. The - preceding ops will already have been processed by the framework (although it - may not update uses), and the subsequent IR will not yet be processed. This - can create confusion if a pattern attempts to match against a sequence of - ops (e.g. rewrite A + B -> C). That sort of rewrite should be performed in a - separate pass. +#### Type Safety + +The types of the remapped operands provided to a conversion pattern must be of a +type expected by the pattern. The expected types of a pattern are determined by +a provided [TypeConverter](#type-converter). If no type converter is provided, +the types of the remapped operands are expected to match the types of the +original operands. If a type converter is provided, the types of the remapped +operands are expected to be legal as determined by the converter. If the +remapped operand types are not of an expected type, and a materialization to the +expected type could not be performed, the pattern fails application before the +`matchAndRewrite` hook is invoked. This ensures that patterns do not have to +explicitly ensure type safety, or sanitize the types of the incoming remapped +operands. More information on type conversion is detailed in the +[dedicated section](#type-conversion) below. ## Type Conversion It is sometimes necessary as part of a conversion to convert the set types of being operated on. In these cases, a `TypeConverter` object may be defined that -details how types should be converted. The `TypeConverter` is used by patterns -and by the general conversion infrastructure to convert the signatures of blocks -and regions. +details how types should be converted when interfacing with a pattern. A +`TypeConverter` may be used to convert the signatures of block arguments and +regions, to define the expected inputs types of the pattern, and to reconcile +type differences in general. ### Type Converter -As stated above, the `TypeConverter` contains several hooks for detailing how to -convert types. Several of these hooks are detailed below: +The `TypeConverter` contains several hooks for detailing how to convert types, +and how to materialize conversions between types in various situations. The two +main aspects of the `TypeConverter` are conversion and materialization. + +A `conversion` describes how a given illegal source `Type` should be converted +to N target types. If the source type is already "legal", it should convert to +itself. Type conversions are specified via the `addConversion` method described +below. + +A `materialization` describes how a set of values should be converted to a +single value of a desired type. An important distinction with a `conversion` is +that a `materialization` can produce IR, whereas a `conversion` cannot. These +materializations are used by the conversion framework to ensure type safety +during the conversion process. There are several types of materializations +depending on the situation. + +* Argument Materialization + + - An argument materialization is used when converting the type of a block + argument during a [signature conversion](#region-signature-conversion). + +* Source Materialization + + - A source materialization converts from a value with a "legal" target + type, back to a specific source type. This is used when an operation is + "legal" during the conversion process, but contains a use of an illegal + type. This may happen during a conversion where some operations are + converted to those with different resultant types, but still retain + users of the original type system. + - This materialization is used in the following situations: + * When a block argument has been converted to a different type, but + the original argument still has users that will remain live after + the conversion process has finished. + * When the result type of an operation has been converted to a + different type, but the original result still has users that will + remain live after the conversion process is finished. + +* Target Materialization + + - A target materialization converts from a value with an "illegal" source + type, to a value of a "legal" type. This is used when a pattern expects + the remapped operands to be of a certain set of types, but the original + input operands have not been converted. This may happen during a + conversion where some operations are converted to those with different + resultant types, but still retain uses of the original type system. + - This materialization is used in the following situations: + * When the remapped operands of a + [conversion pattern](#conversion-patterns) are not legal for the + type conversion provided by the pattern. + +If a converted value is used by an operation that isn't converted, it needs a +conversion back to the `source` type, hence source materialization; if an +unconverted value is used by an operation that is being converted, it needs +conversion to the `target` type, hence target materialization. + +As noted above, the conversion process guarantees that the type contract of the +IR is preserved during the conversion. This means that the types of value uses +will not implicitly change during the conversion process. When the type of a +value definition, either block argument or operation result, is being changed, +the users of that definition must also be updated during the conversion process. +If they aren't, a type conversion must be materialized to ensure that a value of +the expected type is still present within the IR. If a target materialization is +required, but cannot be performed, the pattern application fails. If a source +materialization is required, but cannot be performed, the entire conversion +process fails. + +Several of the available hooks are detailed below: ```c++ class TypeConverter { public: - /// Register a conversion function. A conversion function must be convertible + /// Register a conversion function. A conversion function defines how a given + /// source type should be converted. A conversion function must be convertible /// to any of the following forms(where `T` is a class derived from `Type`: /// * Optional(T) /// - This form represents a 1-1 type conversion. It should return nullptr @@ -210,56 +311,53 @@ /// existing value are expected to be removed during conversion. If /// `llvm::None` is returned, the converter is allowed to try another /// conversion function to perform the conversion. - /// - /// When attempting to convert a type, e.g. via `convertType`, the - /// `TypeConverter` will invoke each of the converters starting with the one - /// most recently registered. - template - void addConversion(ConversionFnT &&callback); - - /// Register a materialization function, which must be convertibe to the - /// following form - /// `Optional(PatternRewriter &, T, ValueRange, Location)`, - /// where `T` is any subclass of `Type`. This function is responsible for - /// creating an operation, using the PatternRewriter and Location provided, - /// that "casts" a range of values into a single value of the given type `T`. - /// It must return a Value of the converted type on success, an `llvm::None` - /// if it failed but other materialization can be attempted, and `nullptr` on - /// unrecoverable failure. It will only be called for (sub)types of `T`. - /// Materialization functions must be provided when a type conversion - /// results in more than one type, or if a type conversion may persist after - /// the conversion has finished. - template - void addMaterialization(FnT &&callback); -}; -``` - -### Conversion Patterns - -When type conversion comes into play, the general Rewrite Patterns can no longer -be used. This is due to the fact that the operands of the operation being -matched will not correspond with the operands of the correct type as determined -by `TypeConverter`. The operation rewrites on type boundaries must thus use a -special pattern, the `ConversionPattern`. This pattern provides, as an -additional argument to the `matchAndRewrite` and `rewrite` methods, the set of -remapped operands corresponding to the desired type. These patterns also utilize -a special `PatternRewriter`, `ConversionPatternRewriter`, that provides special -hooks for use with the conversion infrastructure. + /// Note: When attempting to convert a type, e.g. via 'convertType', the + /// mostly recently added conversions will be invoked first. + template ::template arg_t<0>> + void addConversion(FnT &&callback) { + registerConversion(wrapCallback(std::forward(callback))); + } -```c++ -struct MyConversionPattern : public ConversionPattern { - /// The `matchAndRewrite` hooks on ConversionPatterns take an additional - /// `operands` parameter, containing the remapped operands of the original - /// operation. - virtual LogicalResult - matchAndRewrite(Operation *op, ArrayRef operands, - ConversionPatternRewriter &rewriter) const; + /// Register a materialization function, which must be convertible to the + /// following form: + /// `Optional (OpBuilder &, T, ValueRange, Location)`, + /// where `T` is any subclass of `Type`. + /// This function is responsible for creating an operation, using the + /// OpBuilder and Location provided, that "converts" a range of values into a + /// single value of the given type `T`. It must return a Value of the + /// converted type on success, an `llvm::None` if it failed but other + /// materialization can be attempted, and `nullptr` on unrecoverable failure. + /// It will only be called for (sub)types of `T`. + /// + /// This method registers a materialization that will be called when + /// converting an illegal block argument type, to a legal type. + template ::template arg_t<1>> + void addArgumentMaterialization(FnT &&callback) { + argumentMaterializations.emplace_back( + wrapMaterialization(std::forward(callback))); + } + /// This method registers a materialization that will be called when + /// converting a legal type to an illegal source type. This is used when + /// conversions to an illegal type must persist beyond the main conversion. + template ::template arg_t<1>> + void addSourceMaterialization(FnT &&callback) { + sourceMaterializations.emplace_back( + wrapMaterialization(std::forward(callback))); + } + /// This method registers a materialization that will be called when + /// converting type from an illegal, or source, type to a legal type. + template ::template arg_t<1>> + void addTargetMaterialization(FnT &&callback) { + targetMaterializations.emplace_back( + wrapMaterialization(std::forward(callback))); + } }; ``` -These patterns have the same [restrictions](#restrictions) as the basic rewrite -patterns used in dialect conversion. - ### Region Signature Conversion From the perspective of type conversion, the types of block arguments are a bit @@ -268,15 +366,16 @@ done explicitly via a conversion pattern. To convert the types of block arguments within a Region, a custom hook on the `ConversionPatternRewriter` must be invoked; `convertRegionTypes`. This hook uses a provided type converter to -apply type conversions to all blocks within the region, and all blocks that move -into that region. This hook also takes an optional -`TypeConverter::SignatureConversion` parameter that applies a custom conversion -to the entry block of the region. The types of the entry block arguments are -often tied semantically to details on the operation, e.g. FuncOp, AffineForOp, -etc. To convert the signature of just the region entry block, and not any other -blocks within the region, the `applySignatureConversion` hook may be used -instead. A signature conversion, `TypeConverter::SignatureConversion`, can be -built programmatically: +apply type conversions to all blocks within a given region, and all blocks that +move into that region. As noted above, the conversions performed by this method +use the argument materialization hook on the `TypeConverter`. This hook also +takes an optional `TypeConverter::SignatureConversion` parameter that applies a +custom conversion to the entry block of the region. The types of the entry block +arguments are often tied semantically to details on the operation, e.g. FuncOp, +AffineForOp, etc. To convert the signature of just the region entry block, and +not any other blocks within the region, the `applySignatureConversion` hook may +be used instead. A signature conversion, `TypeConverter::SignatureConversion`, +can be built programmatically: ```c++ class SignatureConversion { @@ -303,3 +402,43 @@ The `TypeConverter` provides several default utilities for signature conversion and legality checking: `convertSignatureArgs`/`convertBlockSignature`/`isLegal(Region *|Type)`. + +## Debugging + +To debug the execution of the dialect conversion framework, +`-debug-only=dialect-conversion` may be used. This command line flag activates +LLVM's debug logging infrastructure solely for the conversion framework. The +output is formatted as a tree structure, mirroring the structure of the +conversion process. This output contains all of the actions performed by the +rewriter, how generated operations get legalized, and why they fail. + +Example output is shown below: + +``` +//===-------------------------------------------===// +Legalizing operation : 'std.return'(0x608000002e20) { + "std.return"() : () -> () + + * Fold { + } -> FAILURE : unable to fold + + * Pattern : 'std.return -> ()' { + ** Insert : 'spv.Return'(0x6070000453e0) + ** Replace : 'std.return'(0x608000002e20) + + //===-------------------------------------------===// + Legalizing operation : 'spv.Return'(0x6070000453e0) { + "spv.Return"() : () -> () + + } -> SUCCESS : operation marked legal by the target + //===-------------------------------------------===// + } -> SUCCESS : pattern applied successfully +} -> SUCCESS +//===-------------------------------------------===// +``` + +This output is describing the legalization of an `std.return` operation. We +first try to legalize by folding the operation, but that is unsuccessful for +`std.return`. From there, a pattern is applied that replaces the `std.return` +with a `spv.Return`. The newly generated `spv.Return` is then processed for +legalization, but is found to already legal as per the target.