[mlir][DialectConversion] Update the documentation for dialect conversion

[rriddle]

Summary

This revision updates the documentation for dialect conversion, as many concepts have changed/evolved over time.

[stephenneuendorffer]

One thing I think is missing from this when and if failed type conversions result in failed patterns. I was debugging a case recently where a type conversion failed, but it wasn't obvious why this happened, and it was not reported separately, only as part of a failing pattern.

mlir/docs/DialectConversion.md

130–134

This sentence doesn't really say anything... Suggest: "If an operation is marked recursively legal, either statically or dynamically, then all of..."

193

comma after space

218

"and how to" Lacks parallel structure.

356–359

It seems that Materializations are only part of partial conversions and not full conversions. Perhaps this should be explicit? Or at least for source materialization and target materialization?

[bondhugula]

This is quite useful - thanks. Some minor comments on the first half.

mlir/docs/DialectConversion.md

189

Nit: ; -> , ?

191

-> replacements and erasures

193

space after comma

316

Is there a reason you use "casts" here instead of "converts"?

322

The last clause "... may persist ... has finished" isn't clear.

325

Is this stale?

351–354

Should these paras be moved above the snippet above?

356–358

Nice.

[rriddle]

Resolve comments and a section on debugging

[rriddle]

In D85167#2192431, @stephenneuendorffer wrote:

One thing I think is missing from this when and if failed type conversions result in failed patterns. I was debugging a case recently where a type conversion failed, but it wasn't obvious why this happened, and it was not reported separately, only as part of a failing pattern.

Thanks for the reminder, added a section for that.

mlir/docs/DialectConversion.md

316

Not particularly, they are used somewhat interchangeably. Switched to converts.

325

That applies solely to the addArgumentMaterialization method, do you have a suggestion?

356–359

A materialization can happen during any conversion type, didn't mean to to allude here that it was just during a partial conversion. Removed the use of partial, so that it says "during a conversion".

[stephenneuendorffer]

mlir/docs/DialectConversion.md

277–281

Is this what you added about failing type conversions? I can't quite parse it. I think you're saying:
If they (users of that definition) aren't (updated during the conversion process), then a type conversion must be materialized.... But that means that patterns fail? What's the point of materializing the conversion if patterns will still fail?

[rriddle]

mlir/docs/DialectConversion.md

277–281

Is this what you added about failing type conversions? I can't quite parse it.

No, I added a section on Type Safety to Conversion Pattern.

If they (users of that definition) aren't (updated during the conversion process), then a type conversion must be materialized.... But that means that patterns fail?

No, because if the type of a definition has been changed the pattern has largely already been successfully applied. The only times that you can really tie failed materialization with a failed pattern are when it involves the remapped inputs. That is only one situation though.

There are two situations for when type materializations occur:

• Materializing a conversion for the remapped input to a pattern. If the materialization here fails, the pattern will fail automatically and never reach the matchAndRewrite.

• Materializing a conversion for an operation generated during a successful pattern match that is being used by an already legal operation. This is only possible to detect at the end of the conversion process, given that you don't know if all of the users of the original value are going to be updated when you initially applied the pattern.

What's the point of materializing the conversion if patterns will still fail?

You don't know if a pattern will fail, and the materialization can happen after all patterns have already been applied.

[ftynse]

Thanks, River! This makes things more much clearer for the users.

mlir/docs/DialectConversion.md

129

Nit: regions of operations -> regions

133

Nit: use quotes rather than backticks for "illegal"

173

It may or may not update the operations in-place (pattern root operations can be updated using a mechanism AFAIR).

Disregard if it is mentioned below, but we should really mention that in-place op updates such as replaceAllUsesWith or setOperand are not allowed (except the special mechanism for root) in conversion patterns.

177

The type of an operation -> the types of values defined by an operation? There has been some confusion between operations being values and thus having types in the past.

179

types of the operands?

182

the set of values that were used to replace the original operands -> the list of operands that the operation should use after conversion?

Set/list is a semantic nit on the importance of the order, and the operands are not necessarily replaced.
It may also be worth mentioning that original operands are available and can be inspected.

225

Nit: I'd drop the comma here

227

Ultra-nit: let's keep backticks for the code. We can use _italics_ for highlights, e.g. _conversion_.

232

An important difference is that a materialization can produce IR but a conversion cannot.

242

I'd really appreciate an easy rule to remember what are source and target materializations. Something like: if a value is used by an op that isn't converted, it needs conversion at _source_ (or def) of the value, hence source materialization; if a value is used by an op that is being converted by has a wrong type, it needs conversion at _target_ (or use) of the value, hence target materialization.

269

Typo: "converted provided"

277–281

This seems to be missing a logical connection: "In the case of a target
materialization for the remapped inputs of a conversion pattern, the pattern application fails" sounds like "if target materialization happens, the pattern fails". It should be something like "If the target materialization is required, but cannot be performed, the pattern application fails".

432

"needs to be legalized" sounds a bit weird here since it's declared legal by the target

[bondhugula]

mlir/docs/DialectConversion.md

325

I'll give it another read. Nothing now.

[rriddle]

Address comments

[rriddle]

mlir/docs/DialectConversion.md

173

I have a followup revision that talks about the constraints on patterns in general. I'll add a link from here to the appropriate section in that revision.

227

I'd prefer to keep them for now, as this is consistent with the rest of the doc(and other docs).

[ftynse]

Thanks!

[bondhugula]

mlir/docs/DialectConversion.md

183–186

There is still one key thing that would not be clear here: what happens when there are no replacement operands available, i.e., the def's or the block arguments of the operands were not converted? Will those positions in operands be nullptr or would they be the current operand on the op? I believe it's the latter but the statement ... list of operands that the operation should use after conversion would make it ambiguous or imply nullptr, and this information I think can only be found by digging the implementation of dialect conversion.

[rriddle]

Resolve comments

mlir/docs/DialectConversion.md

183–186

Updated, if an operand belongs to an operation that wasn't converted the original operand is used, the entries are never null.

[bondhugula]

Thanks for addressing everything.

mlir/docs/DialectConversion.md

 # 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:
+The dialect conversion framework consists of the following components:
 
 *   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:
+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
+        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
 
     -   This action signals that every instance of a given operation is legal,
         i.e. any combination of attributes, operands, types, etc. are valid.
 
 *   Dynamic
 
struct MyTarget : public ConversionTarget {
   /// 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<>`:
+"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 = ...;
 
 /// 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.
+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` ->
 `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
+### Conversion Patterns
 
-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.
+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 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 type of an operation has changed. The
+general Rewrite Patterns can no longer be used in these situations, as the
+values of the operands of the operation being matched will not correspond with
+the values expected by the user. This pattern provides, as an additional
+argument to the `matchAndRewrite` and `rewrite` methods, the set of values that
+were used to replace the original operands of the operation. 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;
+};
+```
+
+#### 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. 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 converted provided by the pattern.
+
+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. In the case of a target
+materialization for the remapped inputs of a
+[conversion pattern](#conversion-patterns), the pattern application fails. In
+the case of a source materialization for a converted value with live users, 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<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.
+  /// Note: When attempting to convert a type, e.g. via 'convertType', the
+  ///       mostly recently added conversions will be invoked first.
+  template <typename FnT,
+            typename T = typename llvm::function_traits<FnT>::template arg_t<0>>
+  void addConversion(FnT &&callback) {
+    registerConversion(wrapCallback<T>(std::forward<FnT>(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<Value> operands,
-                  ConversionPatternRewriter &rewriter) const;
+  /// Register a materialization function, which must be convertible to the
+  /// following form:
+  ///   `Optional<Value> (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 <typename FnT,
+            typename T = typename llvm::function_traits<FnT>::template arg_t<1>>
+  void addArgumentMaterialization(FnT &&callback) {
+    argumentMaterializations.emplace_back(
+        wrapMaterialization<T>(std::forward<FnT>(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 <typename FnT,
+            typename T = typename llvm::function_traits<FnT>::template arg_t<1>>
+  void addSourceMaterialization(FnT &&callback) {
+    sourceMaterializations.emplace_back(
+        wrapMaterialization<T>(std::forward<FnT>(callback)));
+  }
+  /// This method registers a materialization that will be called when
+  /// converting type from an illegal, or source, type to a legal type.
+  template <typename FnT,
+            typename T = typename llvm::function_traits<FnT>::template arg_t<1>>
+  void addTargetMaterialization(FnT &&callback) {
+    targetMaterializations.emplace_back(
+        wrapMaterialization<T>(std::forward<FnT>(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
 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:
+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 {
 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);
 
public:
     /// 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)`.
+
+## 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` also needs to be
+legalized, but it is already legal as per the target.