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