# Dialect Conversion

This document describes a framework in MLIR in which to perform operation
conversions between, and within dialects. This framework allows for transforming
illegal operations to those supported by a provided conversion target, via a set
of pattern-based operation rewriting patterns.

[TOC]

To utilize the framework, a few things must be provided:

*   A [Conversion Target](#conversion-target)
*   A set of [Rewrite Patterns](#rewrite-pattern-specification)
*   A [Type Converter](#type-conversion) (Optional)

## Modes of Conversion

When applying a conversion to a set of operations, there are several conversion
modes that can 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
        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 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
        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
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:

*   Legal

    -   This action signals that every instance of a given operation is legal,
        i.e. any combination of attributes, operands, types, etc. are valid.

*   Dynamic

    -   This action signals that only some instances of a given operation are
        legal. This allows for defining fine-tune constraints, e.g. saying that
        `addi` is only legal when operating on 32-bit integers.
    -   If a specific handler is not provided when setting the action, the
        target must override the `isDynamicallyLegal` hook provided by
        `ConversionTarget`.

*   Illegal

    -   This action signals that no instance of a given operation is legal.
        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.

An example conversion target is shown below:

```c++
struct MyTarget : public ConversionTarget {
  MyTarget(MLIRContext &ctx) : ConversionTarget(ctx) {
    //--------------------------------------------------------------------------
    // Marking an operation as Legal:

    /// Mark all operations within the LLVM dialect are legal.
    addLegalDialects<LLVMDialect>();

    /// Mark `std.constant` op is always legal on this target.
    addLegalOps<ConstantOp>();

    //--------------------------------------------------------------------------
    // Marking an operation as dynamically legal.

    /// Mark all operations within Affine dialect have dynamic legality
    /// constraints.
    addDynamicallyLegalDialects<AffineDialect>();

    /// Mark `std.return` as dynamically legal.
    addDynamicallyLegalOp<ReturnOp>();

    /// Mark `std.return` as dynamically legal, but provide a specific legality
    /// callback.
    addDynamicallyLegalOp<ReturnOp>([](ReturnOp op) { ... });

    /// Treat unknown operations, i.e. those without a legalization action
    /// directly set, as dynamically legal.
    markUnknownOpDynamicallyLegal();
    markUnknownOpDynamicallyLegal([](Operation *op) { ... });

    //--------------------------------------------------------------------------
    // Marking an operation as illegal.

    /// All operations within the GPU dialect are illegal.
    addIllegalDialect<GPUDialect>();

    /// Mark `std.br` and `std.cond_br` as illegal.
    addIllegalOp<BranchOp, CondBranchOp>();
  }

  /// Implement the default legalization handler to handle operations marked as
  /// dynamically legal that were not provided with an explicit handler.
  bool isDynamicallyLegal(Operation *op) override { ... }
};
```

### 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<>`:

```c++
ConversionTarget &target = ...;

/// The operation must first be marked as `Legal` or `Dynamic`.
target.addLegalOp<MyOp>(...);
target.addDynamicallyLegalOp<MySecondOp>(...);

/// Mark the operation as always recursively legal.
target.markOpRecursivelyLegal<MyOp>();
/// Mark optionally with a callback to allow selective marking.
target.markOpRecursivelyLegal<MyOp, MySecondOp>([](Operation *op) { ... });
/// Mark optionally with a callback to allow selective marking.
target.markOpRecursivelyLegal<MyOp>([](MyOp op) { ... });
```

## 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.

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` ->
`foo.add`], the framework will automatically detect that it can legalize
`bar.add` -> `foo.add` even though a direct conversion does not exist. This
means that you don’t have to define a direct legalization pattern for `bar.add`
-> `foo.add`.

### Restrictions

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:

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 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.

### Type Converter

As stated above, the `TypeConverter` contains several hooks for detailing how to
convert types. Several of these hooks are detailed below:

```c++
class TypeConverter {
 public:
  /// Register a conversion function. A conversion function must be convertible
  /// to any of the following forms(where `T` is a class derived from `Type`:
  ///   * Optional<Type>(T)
  ///     - This form represents a 1-1 type conversion. It should return nullptr
  ///       or `llvm::None` to signify failure. If `llvm::None` is returned, the
  ///       converter is allowed to try another conversion function to perform
  ///       the conversion.
  ///   * Optional<LogicalResult>(T, SmallVectorImpl<Type> &)
  ///     - This form represents a 1-N type conversion. It should return
  ///       `failure` or `llvm::None` to signify a failed conversion. If the new
  ///       set of types is empty, the type is removed and any usages of the
  ///       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 <typename ConversionFnT>
  void addConversion(ConversionFnT &&callback);

  /// Register a materialization function, which must be convertibe to the
  /// following form
  ///   `Optional<Value>(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 <typename FnT>
  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.

```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<Value> operands,
                  ConversionPatternRewriter &rewriter) const;
};
```

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
special. Throughout the conversion process, blocks may move between regions of
different operations. Given this, the conversion of the types for blocks must be
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:

```c++
class SignatureConversion {
public:
    /// Remap an input of the original signature with a new set of types. The
    /// new types are appended to the new signature conversion.
    void addInputs(unsigned origInputNo, ArrayRef<Type> types);

    /// Append new input types to the signature conversion, this should only be
    /// used if the new types are not intended to remap an existing input.
    void addInputs(ArrayRef<Type> types);

    /// Remap an input of the original signature with a range of types in the
    /// new signature.
    void remapInput(unsigned origInputNo, unsigned newInputNo,
                    unsigned newInputCount = 1);

    /// Remap an input of the original signature to another `replacement`
    /// value. This drops the original argument.
    void remapInput(unsigned origInputNo, Value replacement);
};
```

The `TypeConverter` provides several default utilities for signature conversion
and legality checking:
`convertSignatureArgs`/`convertBlockSignature`/`isLegal(Region *|Type)`.
