diff --git a/mlir/docs/Interfaces.md b/mlir/docs/Interfaces.md --- a/mlir/docs/Interfaces.md +++ b/mlir/docs/Interfaces.md @@ -202,3 +202,29 @@ ]; } ``` + +#### Operation Interface List + +MLIR includes standard interfaces providing functionality that is +likely to be common across many different operations. Below is a list +of some key interfaces that may be used directly by any dialect. The +format of the header for each interface section goes as follows: + +* `Interface class name` + - (`C++ class` -- `ODS class`(if applicable)) + +##### CallInterfaces + +* `CallOpInterface` - Used to represent operations like 'call' + - `CallInterfaceCallable getCallableForCallee()` +* `CallableOpInterface` - Used to represent the target callee of call. + - `Region * getCallableRegion()` + - `ArrayRef getCallableResults()` + +##### RegionKindInterfaces + +* `RegionKindInterface` - Used to describe the abstract semantics of regions. + - `RegionKind getRegionKind(unsigned index)` - Return the kind of the region with the given index inside this operation. + - RegionKind::Graph - represents a graph region without control flow semantics + - RegionKind::SSACFG - represents an [SSA-style control flow](LangRef.md#modeling-control-flow) region with basic blocks and reachability + - `hasSSADominance(unsigned index)` - Return true if the region with the given index inside this operation requires dominance. diff --git a/mlir/docs/LangRef.md b/mlir/docs/LangRef.md --- a/mlir/docs/LangRef.md +++ b/mlir/docs/LangRef.md @@ -11,34 +11,63 @@ continuous design provides a framework to lower from dataflow graphs to high-performance target-specific code. -This document defines and describes the key concepts in MLIR, and is intended to -be a dry reference document - the [rationale documentation](Rationale/Rationale.md), -[glossary](../getting_started/Glossary.md), and other content are hosted elsewhere. +This document defines and describes the key concepts in MLIR, and is intended +to be a dry reference document - the [rationale +documentation](Rationale/Rationale.md), +[glossary](../getting_started/Glossary.md), and other content are hosted +elsewhere. MLIR is designed to be used in three different forms: a human-readable textual form suitable for debugging, an in-memory form suitable for programmatic -transformations and analysis, and a compact serialized form suitable for storage -and transport. The different forms all describe the same semantic content. This -document describes the human-readable textual form. +transformations and analysis, and a compact serialized form suitable for +storage and transport. The different forms all describe the same semantic +content. This document describes the human-readable textual form. [TOC] ## High-Level Structure -MLIR is an +MLIR is fundamentally based on a graph-like data structure of nodes, called +*Operations*, and edges, called *Values*. Each Value is the result of exactly +one Operation or Block Argument, and has a *Value Type* defined by the [type +system](#type-system). [Operations](#operations) are contained in +[Blocks](#blocks) and Blocks are contained in [Regions](#regions). Operations +are also ordered within their containing block and Blocks are ordered in their +containing region, although this order may or may not be semantically +meaningful in a given [kind of region](Interfaces.md#regionkindinterface)). +Operations may also contain regions, enabling hierarchical structures to be +represented. + +Operations can represent many different concepts, from higher-level concepts +like function definitions, function calls, buffer allocations, view or slices +of buffers, and process creation, to lower-level concepts like +target-independent arithmetic, target-specific instructions, configuration +registers, and logic gates. These different concepts are represented by +different operations in MLIR and the set of operations usable in MLIR can be +arbitrarily extended. + +MLIR also provides an extensible framework for transformations on operations, +using familiar concepts of compiler [Passes](Passes.md). Enabling an arbitrary +set of passes on an arbitrary set of operations results in a significant +scaling challenge, since each transformation must potentially take into +account the semantics of any operation. MLIR addresses this complexity by +allowing operation semantics to be described abstractly using +[Traits](Traits.md) and [Interfaces](Interfaces.md), enabling transformations +to operate on operations more generically. Traits often describe verification +constraints on valid IR, enabling complex invariants to be captured and +checked. (see +[docs/Tutorials/Toy/Ch-2/#op-vs-operation-using-mlir-operations]) + +One obvious application of MLIR is to represent an [SSA-based](https://en.wikipedia.org/wiki/Static_single_assignment_form) IR, -which means that values are defined before use and have scope defined by their -dominance relations. Operations may produce zero or more results, and each is a -distinct SSA value with its own type defined by the [type system](#type-system). - -The unit of code in MLIR is an [Operation](#operations). Operations allow for -representing many different concepts: allocating buffers, producing views to -transform them, target-independent arithmetic, target-specific operations, and -even arbitrary user-defined high-level operations including the -[Module](#module) and [Function](#functions) operations. Operations may contain -[Regions](#regions) that represent a Control Flow Graph (CFG) of -[Blocks](#blocks), that contain operations and end with a -[terminator operation](#terminator-operations) (like branches). +like the LLVM core IR, with appropriate choice of Operation Types to define +[Modules](#module), [Functions](#functions), Branches, Allocations, and +verification constraints to ensure the SSA Dominance property. MLIR includes a +'standard' dialect which defines just such structures. However, MLIR is +intended to be general enough to represent other compiler-like data +structures, such as Abstract Syntax Trees in a language frontend, generated +instructions in a target-specific backend, or circuits in a High-Level +Synthesis tool. Here's an example of an MLIR module: @@ -106,9 +135,9 @@ ## Notation MLIR has a simple and unambiguous grammar, allowing it to reliably round-trip -through a textual form. This is important for development of the compiler - e.g. -for understanding the state of code as it is being transformed and writing test -cases. +through a textual form. This is important for development of the compiler - +e.g. for understanding the state of code as it is being transformed and +writing test cases. This document describes the grammar using [Extended Backus-Naur Form (EBNF)](https://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_form). @@ -162,21 +191,21 @@ // Identifiers bare-id ::= (letter|[_]) (letter|digit|[_$.])* bare-id-list ::= bare-id (`,` bare-id)* -ssa-id ::= `%` suffix-id +value-id ::= `%` suffix-id suffix-id ::= (digit+ | ((letter|id-punct) (letter|id-punct|digit)*)) symbol-ref-id ::= `@` (suffix-id | string-literal) -ssa-id-list ::= ssa-id (`,` ssa-id)* +value-id-list ::= value-id (`,` value-id)* -// Uses of an SSA value, e.g. in an operand list to an operation. -ssa-use ::= ssa-id -ssa-use-list ::= ssa-use (`,` ssa-use)* +// Uses of value, e.g. in an operand list to an operation. +value-use ::= value-id +value-use-list ::= value-use (`,` value-use)* ``` -Identifiers name entities such as SSA values, types and functions, and are +Identifiers name entities such as values, types and functions, and are chosen by the writer of MLIR code. Identifiers may be descriptive (e.g. `%batch_size`, `@matmul`), or may be non-descriptive when they are -auto-generated (e.g. `%23`, `@func42`). Identifier names for SSA values may be +auto-generated (e.g. `%23`, `@func42`). Identifier names for values may be used in an MLIR text file but are not persisted as part of the IR - the printer will give them anonymous names like `%42`. @@ -186,10 +215,22 @@ keywords may be added to future versions of MLIR without danger of collision with existing identifiers. -The scope of SSA values is defined based on the standard definition of -[dominance](https://en.wikipedia.org/wiki/Dominator_\(graph_theory\)). Argument -identifiers in mapping functions are in scope for the mapping body. Function -identifiers and mapping identifiers are visible across the entire module. +Value identifiers are only [in scope](#value-scoping) for the (nested) +region in which they are defined and cannot be accessed or referenced +outside of that region. Argument identifiers in mapping functions are +in scope for the mapping body. Particular operations may further limit +which identifiers are in scope in their regions. For instance, the +scope of values in a region with [SSA control flow +semantics](#control-flow-and-ssacfg-regions) is constrained according +to the standard definition of [SSA +dominance](https://en.wikipedia.org/wiki/Dominator_\(graph_theory\)). Another +example is the [IsolatedFromAbove trait](Traits.md#isolatedfromabove), +which restricts directly accessing values defined in containing +regions. + +Function identifiers and mapping identifiers are associated with +[Symbols](SymbolsAndSymbolTables) and have scoping rules dependent on +symbol attributes. ## Dialects @@ -220,9 +261,9 @@ operations directly through to MLIR. As an example, some targets go through LLVM. LLVM has a rich set of intrinsics for certain target-independent operations (e.g. addition with overflow check) as well as providing access to -target-specific operations for the targets it supports (e.g. vector permutation -operations). LLVM intrinsics in MLIR are represented via operations that start -with an "llvm." name. +target-specific operations for the targets it supports (e.g. vector +permutation operations). LLVM intrinsics in MLIR are represented via +operations that start with an "llvm." name. Example: @@ -241,28 +282,28 @@ ``` operation ::= op-result-list? (generic-operation | custom-operation) trailing-location? -generic-operation ::= string-literal `(` ssa-use-list? `)` successor-list? +generic-operation ::= string-literal `(` value-use-list? `)` successor-list? (`(` region-list `)`)? attribute-dict? `:` function-type custom-operation ::= bare-id custom-operation-format op-result-list ::= op-result (`,` op-result)* `=` -op-result ::= ssa-id (`:` integer-literal) +op-result ::= value-id (`:` integer-literal) successor-list ::= successor (`,` successor)* successor ::= caret-id (`:` bb-arg-list)? region-list ::= region (`,` region)* trailing-location ::= (`loc` `(` location `)`)? ``` -MLIR introduces a uniform concept called _operations_ to enable describing many -different levels of abstractions and computations. Operations in MLIR are fully -extensible (there is no fixed list of operations) and have application-specific -semantics. For example, MLIR supports -[target-independent operations](Dialects/Standard.md#memory-operations), -[affine operations](Dialects/Affine.md), and -[target-specific machine operations](#target-specific-operations). +MLIR introduces a uniform concept called _operations_ to enable describing +many different levels of abstractions and computations. Operations in MLIR are +fully extensible (there is no fixed list of operations) and have +application-specific semantics. For example, MLIR supports [target-independent +operations](Dialects/Standard.md#memory-operations), [affine +operations](Dialects/Affine.md), and [target-specific machine +operations](#target-specific-operations). The internal representation of an operation is simple: an operation is identified by a unique string (e.g. `dim`, `tf.Conv2d`, `x86.repmovsb`, -`ppc.eieio`, etc), can return zero or more results, take zero or more SSA +`ppc.eieio`, etc), can return zero or more results, take zero or more operands, may have zero or more attributes, may have zero or more successors, and zero or more enclosed [regions](#regions). The generic printing form includes all these elements literally, with a function type to indicate the @@ -307,19 +348,23 @@ module ::= `module` symbol-ref-id? (`attributes` attribute-dict)? region ``` -An MLIR Module represents a top-level container operation. It contains -a single region containing a single block which can contain any -operations. Operations within this region must not implicitly capture -values defined outside the module. Modules have an optional symbol -name that can be used to refer to them in operations. +An MLIR Module represents a top-level container operation. It contains a single +[SSACFG region](#control-flow-and-ssacfg-regions) containing a single block +which can contain any operations. Operations within this region cannot +implicitly capture values defined outside the module, i.e. Modules are +[IsolatedFromAbove](Traits.md#isolatedfromabove). Modules have an optional +[symbol name](SymbolsAndSymbolTables.md) which can be used to refer to them in +operations. ### Functions -An MLIR Function is an operation with a name containing one [region](#regions). -The region of a function is not allowed to implicitly capture values defined -outside of the function, and all external references must use function arguments -or attributes that establish a symbolic connection (e.g. symbols referenced by -name via a string attribute like [SymbolRefAttr](#symbol-reference-attribute)): +An MLIR Function is an operation with a name containing a single [SSACFG +region)[#control-flow-and-ssacfg-regions]. Operations within this region +cannot implicitly capture values defined outside of the function, +i.e. Functions are [IsolatedFromAbove](Traits.md#isolatedfromabove). All +external references must use function arguments or attributes that establish a +symbolic connection (e.g. symbols referenced by name via a string attribute +like [SymbolRefAttr](#symbol-reference-attribute)): ``` function ::= `func` function-signature function-attributes? function-body? @@ -329,7 +374,7 @@ argument-list ::= (named-argument (`,` named-argument)*) | /*empty*/ argument-list ::= (type attribute-dict? (`,` type attribute-dict?)*) | /*empty*/ -named-argument ::= ssa-id `:` type attribute-dict? +named-argument ::= value-id `:` type attribute-dict? function-result-list ::= function-result-list-parens | non-function-type @@ -342,13 +387,13 @@ function-body ::= region ``` -An external function declaration (used when referring to a function declared in -some other module) has no body. While the MLIR textual form provides a nice -inline syntax for function arguments, they are internally represented as "block -arguments" to the first block in the region. +An external function declaration (used when referring to a function declared +in some other module) has no body. While the MLIR textual form provides a nice +inline syntax for function arguments, they are internally represented as +"block arguments" to the first block in the region. -Only dialect attribute names may be specified in the attribute dictionaries for -function arguments, results, or the function itself. +Only dialect attribute names may be specified in the attribute dictionaries +for function arguments, results, or the function itself. Examples: @@ -382,23 +427,33 @@ block-label ::= block-id block-arg-list? `:` block-id ::= caret-id caret-id ::= `^` suffix-id -ssa-id-and-type ::= ssa-id `:` type +value-id-and-type ::= value-id `:` type // Non-empty list of names and types. -ssa-id-and-type-list ::= ssa-id-and-type (`,` ssa-id-and-type)* - -block-arg-list ::= `(` ssa-id-and-type-list? `)` -``` - -A [block](https://en.wikipedia.org/wiki/Basic_block) is a sequential list of -operations without control flow (a call or entering an op's region is not -considered control flow for this purpose) that are executed from top to bottom. -The last operation in a block is a -[terminator operation](#terminator-operations), which ends the block. - -Blocks in MLIR take a list of block arguments, which represent SSA PHI nodes in -a functional notation. The arguments are defined by the block, and values are -provided for these block arguments by branches that go to the block. +value-id-and-type-list ::= value-id-and-type (`,` value-id-and-type)* + +block-arg-list ::= `(` value-id-and-type-list? `)` +``` + +A *Block* is an ordered list of operations, concluding with a single +[terminator operation](#terminator-operations). In [SSACFG +regions](#control-flow-and-ssacfg-regions), each block represents a compiler +[basic block] (https://en.wikipedia.org/wiki/Basic_block) where instructions +inside the block are executed in order and terminator operations implement +control flow branches between basic blocks. + +Blocks in MLIR take a list of block arguments, notated in a function-like +way. Block arguments are bound to values specified by the semantics of +individual operations. Block arguments of the entry block of a region are also +arguments to the region and the values bound to these arguments are determined +by the semantics of the containing operation. Block arguments of other blocks +are determined by the semantics of terminator operations, e.g. Branches, which +have the block as a successor. In regions with [control +flow](#control-flow-and-ssacfg-regions), MLIR leverages this structure to +implicitly represent the passage of control-flow dependent values without the +complex nuances of PHI nodes in traditional SSA representations. Note that +values which are not control-flow dependent can be referenced directly and do +not need to be passed through block arguments. Here is a simple example function showing branches, returns, and block arguments: @@ -416,61 +471,134 @@ br ^bb3(%b: i64) // Branch passes %b as the argument // ^bb3 receives an argument, named %c, from predecessors -// and passes it on to bb4 twice. +// and passes it on to bb4 along with %a. %a is referenced +// directly from its defining operation and is not passed through +// an argument of ^bb3. ^bb3(%c: i64): - br ^bb4(%c, %c : i64, i64) + br ^bb4(%c, %a : i64, i64) ^bb4(%d : i64, %e : i64): %0 = addi %d, %e : i64 - return %0 : i64 + return %0 : i64 // Return is also a terminator. } ``` -**Context:** The "block argument" representation eliminates a number of special -cases from the IR compared to traditional "PHI nodes are operations" SSA IRs -(like LLVM). For example, the -[parallel copy semantics](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.524.5461&rep=rep1&type=pdf) -of SSA is immediately apparent, and function arguments are no longer a special -case: they become arguments to the entry block -[[more rationale](Rationale/Rationale.md#block-arguments-vs-phi-nodes)]. +**Context:** The "block argument" representation eliminates a number +of special cases from the IR compared to traditional "PHI nodes are +operations" SSA IRs (like LLVM). For example, the [parallel copy +semantics](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.524.5461&rep=rep1&type=pdf) +of SSA is immediately apparent, and function arguments are no longer a +special case: they become arguments to the entry block [[more +rationale](Rationale/Rationale.md#block-arguments-vs-phi-nodes)]. Blocks +are also a fundamental concept that cannot be represented by +operations because values defined in an operation cannot be accessed +outside the operation. ## Regions ### Definition -A region is a CFG of MLIR [Blocks](#blocks). Regions serve to group semantically -connected blocks, where the semantics is not imposed by the IR. Instead, the -containing operation defines the semantics of the regions it contains. Regions -do not have a name or an address, only the blocks contained in a region do. -Regions are meaningless outside of the containing entity and have no type or -attributes. +A region is an ordered list of MLIR [Blocks](#blocks). The semantics within a +region is not imposed by the IR. Instead, the containing operation defines the +semantics of the regions it contains. MLIR currently defines two kinds of +regions: [SSACFG regions](#control-flow-and-ssacfg-regions), which describe +control flow between blocks, and [Graph regions](#graph-regions), which do not +require control flow between block. The kinds of regions within an operation +are described using the +[RegionKindInterface](Interfaces.md#regionkindinterface). -The first block in the region cannot be a successor of any other block. The -syntax for the region is as follows: +Regions do not have a name or an address, only the blocks contained in a +region do. Regions must be contained within operations and have no type or +attributes. The first block in the region is a special block called the 'entry +block'. The arguments to the entry block are also the arguments of the region +itself. The entry block cannot be listed as a successor of any other +block. The syntax for a region is as follows: ``` region ::= `{` block* `}` ``` -The function body is an example of a region: it consists of a CFG of blocks and -has additional semantic restrictions that other types of regions may not have -(block terminators must either branch to a different block, or return from a -function where the types of the `return` arguments must match the result types -of the function signature). +A function body is an example of a region: it consists of a CFG of blocks and +has additional semantic restrictions that other types of regions may not have. +For example, in a function body, block terminators must either branch to a +different block, or return from a function where the types of the `return` +arguments must match the result types of the function signature. Similarly, +the function arguments must match the types and count of the region arguments. +In general, operations with regions can define these correspondances +arbitrarily. + +### Value Scoping + +Regions provide hierarchical encapsulation of programs: it is impossible to +reference, i.e. branch to, a block which is not in the same region as the +source of the reference, i.e. a terminator operation. Similarly, regions +provides a natural scoping for value visibility: values defined in a region +don't escape to the enclosing region, if any. By default, operations inside a +region can reference values defined outside of the region whenever it would +have been legal for operands of the enclosing operation to reference those +values, but this can be restricted using traits, such as +[OpTrait::IsolatedFromAbove](Traits.md#isolatedfromabove), or a custom +verifier. -### Control and Value Scoping +Example: -Regions provide nested control isolation: it is impossible to branch to a block -within a region from outside it or to branch from within a region to a block -outside it. Similarly, it provides a natural scoping for value visibility: SSA -values defined in a region don't escape to the enclosing region, if any. By -default, a region can reference values defined outside of the region whenever it -would have been legal to use them as operands to the enclosing operation. +```mlir + "any_op"(%a) ({ // if %a is in-scope in the containing region... + // then %a is in-scope here too. + %new_value = "another_op"(%a) : (i64) -> (i64) + }) : (i64) -> (i64) +``` + +MLIR defines a generalized 'hierarchical dominance' concept that operates +across hierarchy and defines whether a value is 'in scope' and can be used by +a particular operation. Whether a value can be used by another operation in +the same region is defined by the kind of region. A value defined in a region +can be used by an operation which has a parent in the same region, if and only +if the parent could use the value. A value defined by an argument to a region +can always be used by any operation deeply contained in the region. A value +defined in a region can never be used outside of the region. + +### Control Flow and SSACFG Regions + +In MLIR, control flow semantics of a region is indicated by +[RegionKind::SSACFG](Interfaces.md#regionkindinterface). Informally, these +regions support semantics where operations in a region 'execute +sequentially'. Before an operation executes, its operands have well-defined +values. After an operation executes, the operands have the same values and +results also have well-defined values. After an operation executes, the next +operation in the block executes until the operation is the terminator operation +at the end of a block, in which case some other operation will execute. The +determination of the next instruction to execute is the 'passing of control +flow'. + +In general, when control flow is passed to an operation, MLIR does not +restrict when control flow enters or exits the regions contained in that +operation. However, when control flow enters a region, it always begins in the +first block of the region, called the *entry* block. Terminator operations +ending each block represent control flow by explicitly specifying the +successor blocks of the block. Control flow can only pass to one of the +specified successor blocks as in a `branch` operation, or back to the +containing operation as in a `return` operation. Terminator operations without +successors can only pass control back to the containing operation. Within +these restrictions, the particular semantics of terminator operations is +determined by the specific dialect operations involved. Blocks (other than the +entry block) that are not listed as a successor of a terminator operation are +defined to be unreachable and can be removed without affecting the semantics +of the containing operation. + +Although control flow always enters a region through the entry block, control +flow may exit a region through any block with an appropriate terminator. The +standard dialect leverages this capability to define operations with +Single-Entry-Multiple-Exit (SEME) regions, possibly flowing through different +blocks in the region and exiting through any block with a `return` +operation. This behavior is similar to that of a function body in most +programming languages. In addition, control flow may also not reach the end of +a block or region, for example if a function call does not return. Example: ```mlir -func @accelerator_compute(i64, i1) -> i64 { +func @accelerator_compute(i64, i1) -> i64 { // An SSACFG region ^bb0(%a: i64, %cond: i1): // Code dominated by ^bb0 may refer to %a cond_br %cond, ^bb1, ^bb2 @@ -480,7 +608,7 @@ br ^bb3(%a: i64) // Branch passes %a as the argument ^bb2: - "accelerator.launch"() { + accelerator.launch() { // An SSACFG region ^bb0: // Region of code nested under "accelerator.launch", it can reference %a but // not %value. @@ -493,35 +621,19 @@ } ``` -This can be further restricted using the custom verifier associated with the -enclosing operation, for example, disallowing references to values defined -outside the region completely. - -### Control Flow - -Regions are Single-Entry-Multiple-Exit (SEME). This means that control can only -flow into the first block of the region, but can flow out of the region at the -end of any of the contained blocks (This behavior is similar to that of a -function body in most programming languages). A terminator of a block within a -region may transfer the control flow to another block in this region, or return -it to the immediately enclosing op. The semantics of the enclosing op defines -where the control flow is transmitted next. It may, for example, enter a region -of the same op, including the same region that returned the control flow. - -The enclosing operation determines the way in which control is transmitted into -the entry block of a Region. The successor to a Region’s exit points may not -necessarily exist: for example a call to a function that does not return. -Concurrent or asynchronous execution of Regions is unspecified. Operations may -define specific rules of execution, e.g. sequential loops or switch cases. - -A Region may also enter another region within the enclosing operation. If an -operation has multiple regions, the semantics of the operation defines into -which regions the control flows and in which order, if any. An operation may -transmit control into Regions that were specified in other operations, in -particular those that defined the values the given operation uses. Thus, such -operations can be treated opaquely in the enclosing control flow graph, -providing a level of control flow isolation similar to that of the call -operation. +#### Operations with Multiple Regions + +An operation containing multiple regions also completely determines the +semantics of those regions. In particular, when control flow is passed to an +operation, it may transfer control flow to any contained region. When control +flow exits a region and is returned to the containing operation, the +containing operation may pass control flow to any region in the same +operation. An operation may also pass control flow to multiple contained +regions concurrently. An operation may also pass control flow into regions +that were specified in other operations, in particular those that defined the +values or symbols the given operation uses as in a call operation. This +passage of control is generally independent of passage of control flow through +the basic blocks of the containing region. #### Closure @@ -532,6 +644,51 @@ operation caller to wait for the region to be executed guaranteeing that any directly used values remain live. +### Graph Regions + +In MLIR, graph-like semantics in a region is indicated by +[RegionKind::Graph](Interfaces.md#regionkindinterface). Graph regions are +appropriate for concurrent semantics without control flow, or for modeling +generic directed graph data structures. Graph regions are appropriate for +representing cyclic relationships between coupled values where there is no +fundamental order to the relationships. For instance, operations in a graph +region may represent independent threads of control with values representing +streams of data. As usual in MLIR, the particular semantics of a region is +completely determined by its containing operation. Graph regions may only +contain a single basic block (the entry block). + +**Rationale:** Currently graph regions are arbitrarily limited to a single +basic block, although there is no particular semantic reason for this +limitation. This limitation has been added to make it easier to stabilize the +pass infrastructure and commonly used passes for processing graph regions to +properly handle feedback loops. Multi-block regions may be allowed in the +future if use cases that require it arise. + +In graph regions, MLIR operations naturally represent nodes, while each MLIR +value represents a multi-edge connecting a single source node and multiple +destination nodes. All values defined in the region as results of operations +are in scope within the region and can be accessed by any other operation in +the region. In graph regions, the order of operations within a block and the +order of blocks in a region is not semantically meaningful and non-terminator +operations may be freely reordered, for instance, by canonicalization. Other +kinds of graphs, such as graphs with multiple source nodes and multiple +destination nodes, can also be represented by representing graph edges as MLIR +operations. + +Note that cycles can occur within a single block in a graph region, or between +basic blocks. + +```mlir +"test.graph_region"() ({ // A Graph region + %1 = "op1"(%1, %3) : (i32, i32) -> (i32) // OK: %1, %3 allowed here + %2 = "test.ssacfg_region"() ({ + %5 = "op2"(%1, %2, %3, %4) : (i32, i32, i32, i32) -> (i32) // OK: %1, %2, %3, %4 all defined in the containing region + }) : () -> (i32) + %3 = "op2"(%1, %4) : (i32, i32) -> (i32) // OK: %4 allowed here + %4 = "op3"(%1) : (i32) -> (i32) +}) : () -> () +``` + ### Arguments and Results The arguments of the first block of a region are treated as arguments of the @@ -543,7 +700,7 @@ ## Type System -Each SSA value in MLIR has a type defined by the type system below. There are a +Each value in MLIR has a type defined by the type system below. There are a number of primitive types (like integers) and also aggregate types for tensors and memory buffers. MLIR [standard types](#standard-types) do not include structures, arrays, or dictionaries. @@ -559,7 +716,7 @@ type-list-parens ::= `(` `)` | `(` type-list-no-parens `)` -// This is a common way to refer to an SSA value with a specified type. +// This is a common way to refer to a value with a specified type. ssa-use-and-type ::= ssa-use `:` type // Non-empty list of names and types. @@ -713,7 +870,7 @@ MLIR supports first-class functions: for example, the [`constant` operation](Dialects/Standard.md#constant-operation) produces the -address of a function as an SSA value. This SSA value may be passed to and +address of a function as a value. This value may be passed to and returned from functions, merged across control flow boundaries with [block arguments](#blocks), and called with the [`call_indirect` operation](Dialects/Standard.md#call-indirect-operation). @@ -1052,7 +1209,7 @@ dimension ::= `?` | decimal-literal ``` -SSA values of tensor type represents aggregate N-dimensional data values, and +Values with tensor type represents aggregate N-dimensional data values, and have a known element type. It may have an unknown rank (indicated by `*`) or may have a fixed rank with a list of dimensions. Each dimension may be a static non-negative decimal constant or be dynamically determined (indicated by `?`). @@ -1467,7 +1624,7 @@ extended attribute kinds. **Rationale:** Identifying accesses to global data is critical to -enabling efficient multi-threaded compilation. Restricting global +enabling efficient multi-threaded compilation. Restricting global data access to occur through symbols and limiting the places that can legally hold a symbol reference simplifies reasoning about these data accesses. diff --git a/mlir/include/mlir/IR/CMakeLists.txt b/mlir/include/mlir/IR/CMakeLists.txt --- a/mlir/include/mlir/IR/CMakeLists.txt +++ b/mlir/include/mlir/IR/CMakeLists.txt @@ -1,2 +1,3 @@ add_mlir_interface(OpAsmInterface) add_mlir_interface(SymbolInterfaces) +add_mlir_interface(RegionKindInterface) diff --git a/mlir/include/mlir/IR/Dominance.h b/mlir/include/mlir/IR/Dominance.h --- a/mlir/include/mlir/IR/Dominance.h +++ b/mlir/include/mlir/IR/Dominance.h @@ -39,6 +39,11 @@ /// nullptr. Block *findNearestCommonDominator(Block *a, Block *b) const; + /// Return true if there is dominanceInfo for the given region. + bool hasDominanceInfo(Region *region) { + return dominanceInfos.count(region) != 0; + } + /// Get the root dominance node of the given region. DominanceInfoNode *getRootNode(Region *region) { assert(dominanceInfos.count(region) != 0); @@ -63,39 +68,58 @@ }; } // end namespace detail -/// A class for computing basic dominance information. +/// A class for computing basic dominance information. Note that this +/// class is aware of different types of regions and returns a +/// region-kind specific concept of dominance. See RegionKindInterface. class DominanceInfo : public detail::DominanceInfoBase { public: using super::super; - /// Return true if the specified block is reachable from the entry - /// block of its region. + /// Return true if the specified block is reachable from the entry block of + /// its region. In an SSACFG region, a block is reachable from the entry block + /// if it is the successor of the entry block or another reachable block. In a + /// Graph region, all blocks are reachable. bool isReachableFromEntry(Block *a) const { return super::isReachableFromEntry(a); } - /// Return true if operation A properly dominates operation B. + /// Return true if operation A properly dominates operation B, i.e. if A and B + /// are in the same block and A properly dominates B within the block, or if + /// the block that contains A properly dominates the block that contains B. In + /// an SSACFG region, Operation A dominates Operation B in the same block if A + /// preceeds B. In a Graph region, all operations in a block dominate all + /// other operations in the same block. bool properlyDominates(Operation *a, Operation *b) const; - /// Return true if operation A dominates operation B. + /// Return true if operation A dominates operation B, i.e. if A and B are the + /// same operation or A properly dominates B. bool dominates(Operation *a, Operation *b) const { return a == b || properlyDominates(a, b); } - /// Return true if value A properly dominates operation B. + /// Return true if value A properly dominates operation B, i.e if the + /// operation that defines A properlyDominates B and the operation that + /// defines A does not contain B. bool properlyDominates(Value a, Operation *b) const; - /// Return true if operation A dominates operation B. + /// Return true if operation A dominates operation B, i.e if the operation + /// that defines A dominates B. bool dominates(Value a, Operation *b) const { return (Operation *)a.getDefiningOp() == b || properlyDominates(a, b); } - /// Return true if the specified block A dominates block B. + /// Return true if the specified block A dominates block B, i.e. if block A + /// and block B are the same block or block A properly dominates block B. bool dominates(Block *a, Block *b) const { return a == b || properlyDominates(a, b); } - /// Return true if the specified block A properly dominates block B. + /// Return true if the specified block A properly dominates block B, i.e.: if + /// block A contains block B, or if the region which contains block A also + /// contains block B or some parent of block B and block A dominates that + /// block in that kind of region. In an SSACFG region, block A dominates + /// block B if all control flow paths from the entry block to block B flow + /// through block A. In a Graph region, all blocks dominate all other blocks. bool properlyDominates(Block *a, Block *b) const { return super::properlyDominates(a, b); } diff --git a/mlir/include/mlir/IR/RegionKindInterface.h b/mlir/include/mlir/IR/RegionKindInterface.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/IR/RegionKindInterface.h @@ -0,0 +1,35 @@ +//===- RegionKindInterface.h - Region Kind Interfaces -----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains the definitions of the infer op interfaces defined in +// `RegionKindInterface.td`. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_IR_REGIONKINDINTERFACE_H_ +#define MLIR_IR_REGIONKINDINTERFACE_H_ + +#include "mlir/IR/OpDefinition.h" + +namespace mlir { + +/// The kinds of regions contained in an operation. SSACFG regions +/// require the SSA-Dominance property to hold. Graph regions do not +/// require SSA-Dominance. If a registered operation does not implement +/// RegionKindInterface, then any regions it contains are assumed to be +/// SSACFG regions. +enum class RegionKind { + SSACFG, + Graph, +}; + +} // namespace mlir + +#include "mlir/IR/RegionKindInterface.h.inc" + +#endif // MLIR_IR_REGIONKINDINTERFACE_H_ diff --git a/mlir/include/mlir/IR/RegionKindInterface.td b/mlir/include/mlir/IR/RegionKindInterface.td new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/IR/RegionKindInterface.td @@ -0,0 +1,53 @@ +//===- RegionKindInterface.td - Region kind interfaces -----*- tablegen -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains a set of interfaces to query the properties of regions +// in an operation. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_IR_REGIONKINDINTERFACE +#define MLIR_IR_REGIONKINDINTERFACE + +include "mlir/IR/OpBase.td" + +// OpInterface to query the properties of regions in an operation +def RegionKindInterface : OpInterface<"RegionKindInterface"> { + let description = [{ + Interface for operations to describe the abstract semantics of + their regions. Currently, two kinds of regions are + supported. RegionKind::Graph represents a graph region without + control flow semantics. RegionKind::SSACFG represents an + [SSA-style control flow](LangRef.md#modeling-control-flow) region + with basic blocks, sequential semantics, and reachability. + }]; + let cppNamespace = "::mlir"; + + let methods = [ + StaticInterfaceMethod< + /*desc=*/[{ + Return the kind of the region with the given index inside this operation. + }], + /*retTy=*/"RegionKind", + /*methodName=*/"getRegionKind", + /*args=*/(ins "unsigned":$index) + >, + StaticInterfaceMethod< + /*desc=*/"Return true if the kind of the given region requires the " + "SSA-Dominance property", + /*retTy=*/"bool", + /*methodName=*/"hasSSADominance", + /*args=*/(ins "unsigned":$index), + /*methodBody=*/[{ + return getRegionKind(index) == RegionKind::SSACFG; + }] + >, + ]; +} + +#endif // MLIR_IR_REGIONKINDINTERFACE diff --git a/mlir/lib/IR/CMakeLists.txt b/mlir/lib/IR/CMakeLists.txt --- a/mlir/lib/IR/CMakeLists.txt +++ b/mlir/lib/IR/CMakeLists.txt @@ -18,6 +18,7 @@ OperationSupport.cpp PatternMatch.cpp Region.cpp + RegionKindInterface.cpp StandardTypes.cpp SymbolTable.cpp Types.cpp @@ -33,6 +34,7 @@ MLIRCallInterfacesIncGen MLIROpAsmInterfaceIncGen MLIRSymbolInterfacesIncGen + MLIRRegionKindInterfaceIncGen LINK_LIBS PUBLIC MLIRSupport diff --git a/mlir/lib/IR/Dominance.cpp b/mlir/lib/IR/Dominance.cpp --- a/mlir/lib/IR/Dominance.cpp +++ b/mlir/lib/IR/Dominance.cpp @@ -13,6 +13,7 @@ #include "mlir/IR/Dominance.h" #include "mlir/IR/Operation.h" +#include "mlir/IR/RegionKindInterface.h" #include "llvm/ADT/DenseMap.h" #include "llvm/Support/GenericDomTreeConstruction.h" @@ -23,6 +24,14 @@ template class llvm::DominatorTreeBase; template class llvm::DomTreeNodeBase; +/// Return true if the region with the given index inside the operation +/// has SSA dominance. +static bool hasSSADominance(Operation *op, unsigned index) { + auto kindInterface = dyn_cast(op); + return op->isRegistered() && + (!kindInterface || kindInterface.hasSSADominance(index)); +} + //===----------------------------------------------------------------------===// // DominanceInfoBase //===----------------------------------------------------------------------===// @@ -31,15 +40,30 @@ void DominanceInfoBase::recalculate(Operation *op) { dominanceInfos.clear(); - /// Build the dominance for each of the operation regions. + // Build the dominance for each of the operation regions. op->walk([&](Operation *op) { - for (auto ®ion : op->getRegions()) { + auto kindInterface = dyn_cast(op); + unsigned numRegions = op->getNumRegions(); + for (unsigned i = 0; i < numRegions; i++) { + Region ®ion = op->getRegion(i); // Don't compute dominance if the region is empty. if (region.empty()) continue; - auto opDominance = std::make_unique(); - opDominance->recalculate(region); - dominanceInfos.try_emplace(®ion, std::move(opDominance)); + + // Dominance changes based on the region type. Avoid the helper + // function here so we don't do the region cast repeatedly. + bool hasSSADominance = + op->isRegistered() && + (!kindInterface || kindInterface.hasSSADominance(i)); + // If a region has SSADominance, then compute detailed dominance + // info. Otherwise, all values in the region are live anywhere + // in the region, which is represented as an empty entry in the + // dominanceInfos map. + if (hasSSADominance) { + auto opDominance = std::make_unique(); + opDominance->recalculate(region); + dominanceInfos.try_emplace(®ion, std::move(opDominance)); + } } }); } @@ -132,7 +156,7 @@ template DominanceInfoNode *DominanceInfoBase::getNode(Block *a) { - auto *region = a->getParent(); + Region *region = a->getParent(); assert(dominanceInfos.count(region) != 0); return dominanceInfos[region]->getNode(a); } @@ -151,7 +175,7 @@ // If both blocks are not in the same region, 'a' properly dominates 'b' if // 'b' is defined in an operation region that (recursively) ends up being // dominated by 'a'. Walk up the list of containers enclosing B. - auto *regionA = a->getParent(); + Region *regionA = a->getParent(); if (regionA != b->getParent()) { b = traverseAncestors( b, [&](Block *block) { return block->getParent() == regionA; }); @@ -180,15 +204,15 @@ /// region. template bool DominanceInfoBase::isReachableFromEntry(Block *a) const { - auto *regionA = a->getParent(); + Region *regionA = a->getParent(); auto baseInfoIt = dominanceInfos.find(regionA); if (baseInfoIt == dominanceInfos.end()) return true; return baseInfoIt->second->isReachableFromEntry(a); } -template class mlir::detail::DominanceInfoBase; -template class mlir::detail::DominanceInfoBase; +template class detail::DominanceInfoBase; +template class detail::DominanceInfoBase; //===----------------------------------------------------------------------===// // DominanceInfo @@ -196,15 +220,25 @@ /// Return true if operation A properly dominates operation B. bool DominanceInfo::properlyDominates(Operation *a, Operation *b) const { - auto *aBlock = a->getBlock(), *bBlock = b->getBlock(); + Block *aBlock = a->getBlock(), *bBlock = b->getBlock(); + Region *aRegion = a->getParentRegion(); + unsigned aRegionNum = aRegion->getRegionNumber(); + Operation *ancestor = aRegion->getParentOp(); // If a or b are not within a block, then a does not dominate b. if (!aBlock || !bBlock) return false; - // If the blocks are the same, then check if b is before a in the block. - if (aBlock == bBlock) - return a->isBeforeInBlock(b); + if (aBlock == bBlock) { + // Dominance changes based on the region type. In a region with SSA + // dominance, uses inside the same block must follow defs. In other + // regions kinds, uses and defs can come in any order inside a block. + if (hasSSADominance(ancestor, aRegionNum)) { + // If the blocks are the same, then check if b is before a in the block. + return a->isBeforeInBlock(b); + } + return true; + } // Traverse up b's hierarchy to check if b's block is contained in a's. if (auto *bAncestor = aBlock->findAncestorOpInBlock(*b)) { @@ -221,10 +255,19 @@ /// Return true if value A properly dominates operation B. bool DominanceInfo::properlyDominates(Value a, Operation *b) const { if (auto *aOp = a.getDefiningOp()) { - // The values defined by an operation do *not* dominate any nested - // operations. - if (aOp->getParentRegion() != b->getParentRegion() && aOp->isAncestor(b)) - return false; + // Dominance changes based on the region type. + auto *aRegion = aOp->getParentRegion(); + unsigned aRegionNum = aRegion->getRegionNumber(); + Operation *ancestor = aRegion->getParentOp(); + // Dominance changes based on the region type. In a region with SSA + // dominance, values defined by an operation cannot be used by the + // operation. In other regions kinds they can be used the operation. + if (hasSSADominance(ancestor, aRegionNum)) { + // The values defined by an operation do *not* dominate any nested + // operations. + if (aOp->getParentRegion() != b->getParentRegion() && aOp->isAncestor(b)) + return false; + } return properlyDominates(aOp, b); } @@ -245,14 +288,23 @@ /// Returns true if statement 'a' properly postdominates statement b. bool PostDominanceInfo::properlyPostDominates(Operation *a, Operation *b) { auto *aBlock = a->getBlock(), *bBlock = b->getBlock(); + auto *aRegion = a->getParentRegion(); + unsigned aRegionNum = aRegion->getRegionNumber(); + Operation *ancestor = aRegion->getParentOp(); // If a or b are not within a block, then a does not post dominate b. if (!aBlock || !bBlock) return false; // If the blocks are the same, check if b is before a in the block. - if (aBlock == bBlock) - return b->isBeforeInBlock(a); + if (aBlock == bBlock) { + // Dominance changes based on the region type. + if (hasSSADominance(ancestor, aRegionNum)) { + // If the blocks are the same, then check if b is before a in the block. + return b->isBeforeInBlock(a); + } + return true; + } // Traverse up b's hierarchy to check if b's block is contained in a's. if (auto *bAncestor = a->getBlock()->findAncestorOpInBlock(*b)) diff --git a/mlir/lib/IR/RegionKindInterface.cpp b/mlir/lib/IR/RegionKindInterface.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/IR/RegionKindInterface.cpp @@ -0,0 +1,18 @@ +//===- RegionKindInterface.cpp - Region Kind Interfaces ---------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file contains the definitions of the region kind interfaces defined in +// `RegionKindInterface.td`. +// +//===----------------------------------------------------------------------===// + +#include "mlir/IR/RegionKindInterface.h" + +using namespace mlir; + +#include "mlir/IR/RegionKindInterface.cpp.inc" diff --git a/mlir/lib/IR/Verifier.cpp b/mlir/lib/IR/Verifier.cpp --- a/mlir/lib/IR/Verifier.cpp +++ b/mlir/lib/IR/Verifier.cpp @@ -29,6 +29,7 @@ #include "mlir/IR/Dialect.h" #include "mlir/IR/Dominance.h" #include "mlir/IR/Operation.h" +#include "mlir/IR/RegionKindInterface.h" #include "llvm/ADT/StringMap.h" #include "llvm/Support/FormatVariadic.h" #include "llvm/Support/PrettyStackTrace.h" @@ -58,9 +59,12 @@ LogicalResult verifyBlock(Block &block); LogicalResult verifyOperation(Operation &op); - /// Verify the dominance within the given IR unit. + /// Verify the dominance property of operations within the given Region. LogicalResult verifyDominance(Region ®ion); - LogicalResult verifyDominance(Operation &op); + + /// Verify the dominance property of regions contained within the given + /// Operation. + LogicalResult verifyDominanceOfContainedRegions(Operation &op); /// Emit an error for the given block. InFlightDiagnostic emitError(Block &bb, const Twine &message) { @@ -96,9 +100,8 @@ // verifier to be resilient to malformed code. DominanceInfo theDomInfo(&op); domInfo = &theDomInfo; - for (auto ®ion : op.getRegions()) - if (failed(verifyDominance(region))) - return failure(); + if (failed(verifyDominanceOfContainedRegions(op))) + return failure(); domInfo = nullptr; return success(); @@ -115,7 +118,7 @@ "entry block of region may not have predecessors"); // Verify each of the blocks within the region. - for (auto &block : region) + for (Block &block : region) if (failed(verifyBlock(block))) return failure(); return success(); @@ -178,10 +181,31 @@ if (opInfo && failed(opInfo->verifyInvariants(&op))) return failure(); + auto kindInterface = dyn_cast(op); + // Verify that all child regions are ok. - for (auto ®ion : op.getRegions()) + unsigned numRegions = op.getNumRegions(); + for (unsigned i = 0; i < numRegions; i++) { + Region ®ion = op.getRegion(i); + // Check that Graph Regions only have a single basic block. This is + // similar to the code in SingleBlockImplicitTerminator, but doesn't + // require the trait to be specified. This arbitrary limitation is + // designed to limit the number of cases that have to be handled by + // transforms and conversions until the concept stabilizes. + if (op.isRegistered() && kindInterface && + kindInterface.getRegionKind(i) == RegionKind::Graph) { + // Empty regions are fine. + if (region.empty()) + continue; + + // Non-empty regions must contain a single basic block. + if (std::next(region.begin()) != region.end()) + return op.emitOpError("expects graph region #") + << i << " to have 0 or 1 blocks"; + } if (failed(verifyRegion(region))) return failure(); + } // If this is a registered operation, there is nothing left to do. if (opInfo) @@ -223,43 +247,40 @@ LogicalResult OperationVerifier::verifyDominance(Region ®ion) { // Verify the dominance of each of the held operations. - for (auto &block : region) - // Dominance is only reachable inside reachable blocks. + for (Block &block : region) { + // Dominance is only meaningful inside reachable blocks. if (domInfo->isReachableFromEntry(&block)) - for (auto &op : block) { - if (failed(verifyDominance(op))) + for (Operation &op : block) + // Check that operands properly dominate this use. + for (unsigned operandNo = 0, e = op.getNumOperands(); operandNo != e; + ++operandNo) { + auto operand = op.getOperand(operandNo); + if (domInfo->properlyDominates(operand, &op)) + continue; + + auto diag = op.emitError("operand #") + << operandNo << " does not dominate this use"; + if (auto *useOp = operand.getDefiningOp()) + diag.attachNote(useOp->getLoc()) << "operand defined here"; return failure(); - } - else - // Verify the dominance of each of the nested blocks within this - // operation, even if the operation itself is not reachable. - for (auto &op : block) - for (auto ®ion : op.getRegions()) - if (failed(verifyDominance(region))) - return failure(); + } + // Recursively verify dominance within each operation in the + // block, even if the block itself is not reachable, or we are in + // a region which doesn't respect dominance. + for (Operation &op : block) + if (failed(verifyDominanceOfContainedRegions(op))) + return failure(); + } return success(); } -LogicalResult OperationVerifier::verifyDominance(Operation &op) { - // Check that operands properly dominate this use. - for (unsigned operandNo = 0, e = op.getNumOperands(); operandNo != e; - ++operandNo) { - auto operand = op.getOperand(operandNo); - if (domInfo->properlyDominates(operand, &op)) - continue; - - auto diag = op.emitError("operand #") - << operandNo << " does not dominate this use"; - if (auto *useOp = operand.getDefiningOp()) - diag.attachNote(useOp->getLoc()) << "operand defined here"; - return failure(); - } - - // Verify the dominance of each of the nested blocks within this operation. - for (auto ®ion : op.getRegions()) +/// Verify the dominance of each of the nested blocks within the given operation +LogicalResult +OperationVerifier::verifyDominanceOfContainedRegions(Operation &op) { + for (Region ®ion : op.getRegions()) { if (failed(verifyDominance(region))) return failure(); - + } return success(); } diff --git a/mlir/lib/Transforms/CSE.cpp b/mlir/lib/Transforms/CSE.cpp --- a/mlir/lib/Transforms/CSE.cpp +++ b/mlir/lib/Transforms/CSE.cpp @@ -171,6 +171,12 @@ return; } + // If the region does not have dominanceInfo, then skip it. + // TODO: Regions without SSA dominance should define a different + // traversal order which is appropriate and can be used here. + if (!domInfo.hasDominanceInfo(®ion)) + return; + // Note, deque is being used here because there was significant performance // gains over vector when the container becomes very large due to the // specific access patterns. If/when these performance issues are no diff --git a/mlir/test/CMakeLists.txt b/mlir/test/CMakeLists.txt --- a/mlir/test/CMakeLists.txt +++ b/mlir/test/CMakeLists.txt @@ -97,5 +97,5 @@ set_target_properties(check-mlir PROPERTIES FOLDER "Tests") add_lit_testsuites(MLIR ${CMAKE_CURRENT_SOURCE_DIR} - DEPENDS ${MLIR_TEST_DEPS} + DEPENDS ${MLIR_TEST_DEPENDS} ) diff --git a/mlir/test/IR/invalid.mlir b/mlir/test/IR/invalid.mlir --- a/mlir/test/IR/invalid.mlir +++ b/mlir/test/IR/invalid.mlir @@ -918,7 +918,7 @@ // ----- func @invalid_nested_dominance() { - "foo.region"() ({ + "test.ssacfg_region"() ({ // expected-error @+1 {{operand #0 does not dominate this use}} "foo.use" (%1) : (i32) -> () br ^bb2 @@ -1106,7 +1106,7 @@ // ----- func @invalid_region_dominance() { - "foo.region"() ({ + "test.ssacfg_region"() ({ // expected-error @+1 {{operand #0 does not dominate this use}} "foo.use" (%def) : (i32) -> () "foo.yield" () : () -> () @@ -1121,7 +1121,7 @@ func @invalid_region_dominance() { // expected-note @+1 {{operand defined here}} - %def = "foo.region_with_def"() ({ + %def = "test.ssacfg_region"() ({ // expected-error @+1 {{operand #0 does not dominate this use}} "foo.use" (%def) : (i32) -> () "foo.yield" () : () -> () @@ -1534,7 +1534,7 @@ %c = constant false return %c : i1 ^bb0: - "dummy" () ({ // unreachable + "test.ssacfg_region" () ({ // unreachable ^bb1: // expected-error @+1 {{operand #0 does not dominate this use}} %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) @@ -1546,3 +1546,19 @@ }) : () -> () return %c : i1 } + +// ----- + +func @invalid_region_dominance_with_dominance_free_regions() { + test.graph_region { + "foo.use" (%1) : (i32) -> () + "foo.region"() ({ + %1 = constant 0 : i32 // This value is used outside of the region. + "foo.yield" () : () -> () + }, { + // expected-error @+1 {{expected operation name in quotes}} + %2 = constant 1 i32 // Syntax error causes region deletion. + }) : () -> () + } + return +} diff --git a/mlir/test/IR/parser.mlir b/mlir/test/IR/parser.mlir --- a/mlir/test/IR/parser.mlir +++ b/mlir/test/IR/parser.mlir @@ -1244,16 +1244,131 @@ return } +// CHECK-LABEL: func @unreachable_dominance_violation_ok func @unreachable_dominance_violation_ok() -> i1 { - %c = constant false // CHECK: [[VAL:%.*]] = constant false - return %c : i1 // CHECK: return [[VAL]] : i1 -^bb1: // CHECK: ^bb1: // no predecessors +// CHECK: [[VAL:%.*]] = constant false +// CHECK: return [[VAL]] : i1 +// CHECK: ^bb1: // no predecessors +// CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) +// CHECK: br ^bb3 +// CHECK: ^bb2: // pred: ^bb2 +// CHECK: br ^bb2 +// CHECK: ^bb3: // pred: ^bb1 +// CHECK: [[VAL3]] = "foo"() : () -> i64 +// CHECK: return [[VAL2]]#1 : i1 +// CHECK: } + %c = constant false + return %c : i1 +^bb1: // %1 is not dominated by it's definition, but block is not reachable. - %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) - br ^bb4 // CHECK: br ^bb3 -^bb2: // CHECK: ^bb2: // pred: ^bb2 - br ^bb2 // CHECK: br ^bb2 -^bb4: // CHECK: ^bb3: // pred: ^bb1 - %1 = "foo"() : ()->i64 // CHECK: [[VAL3]] = "foo"() : () -> i64 - return %2#1 : i1 // CHECK: return [[VAL2]]#1 : i1 -} // CHECK: } + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + br ^bb3 +^bb2: + br ^bb2 +^bb3: + %1 = "foo"() : ()->i64 + return %2#1 : i1 +} + +// CHECK-LABEL: func @graph_region_in_hierarchy_ok +func @graph_region_in_hierarchy_ok() -> i64 { +// CHECK: br ^bb2 +// CHECK: ^bb1: +// CHECK: test.graph_region { +// CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) +// CHECK: } +// CHECK: br ^bb3 +// CHECK: ^bb2: // pred: ^bb0 +// CHECK: [[VAL3]] = "foo"() : () -> i64 +// CHECK: br ^bb1 +// CHECK: ^bb3: // pred: ^bb1 +// CHECK: return [[VAL3]] : i64 +// CHECK: } + br ^bb2 +^bb1: + test.graph_region { + // %1 is well-defined here, since bb2 dominates bb1. + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + } + br ^bb4 +^bb2: + %1 = "foo"() : ()->i64 + br ^bb1 +^bb4: + return %1 : i64 +} + +// CHECK-LABEL: func @graph_region_kind +func @graph_region_kind() -> () { +// CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) +// CHECK: [[VAL3]] = "baz"([[VAL2]]#0) : (i1) -> i64 + test.graph_region { + // %1 OK here in in graph region. + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + %1 = "baz"(%2#0) : (i1) -> (i64) + } + return +} + +// CHECK-LABEL: func @graph_region_inside_ssacfg_region +func @graph_region_inside_ssacfg_region() -> () { +// CHECK: "test.ssacfg_region" +// CHECK: [[VAL3:%.*]] = "baz"() : () -> i64 +// CHECK: test.graph_region { +// CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3]]) : (i64) -> (i1, i1, i1) +// CHECK: } +// CHECK: [[VAL4:.*]] = "baz"() : () -> i64 + "test.ssacfg_region"() ({ + %1 = "baz"() : () -> (i64) + test.graph_region { + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + } + %3 = "baz"() : () -> (i64) + }) : () -> () + return +} + +// CHECK-LABEL: func @graph_region_in_graph_region_ok +func @graph_region_in_graph_region_ok() -> () { +// CHECK: test.graph_region { +// CHECK: test.graph_region { +// CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) +// CHECK: } +// CHECK: [[VAL3]] = "foo"() : () -> i64 +// CHECK: } +test.graph_region { + test.graph_region { + // %1 is well-defined here since defined in graph region + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + } + %1 = "foo"() : ()->i64 + "test.terminator"() : ()->() + } + return +} + +// CHECK: test.graph_region { +test.graph_region { +// CHECK: [[VAL1:%.*]] = "op1"([[VAL3:%.*]]) : (i32) -> i32 +// CHECK: [[VAL2:%.*]] = "test.ssacfg_region"([[VAL1]], [[VAL2]], [[VAL3]], [[VAL4:%.*]]) ( { +// CHECK: [[VAL5:%.*]] = "op2"([[VAL1]], [[VAL2]], [[VAL3]], [[VAL4]]) : (i32, i32, i32, i32) -> i32 +// CHECK: }) : (i32, i32, i32, i32) -> i32 +// CHECK: [[VAL3]] = "op2"([[VAL1]], [[VAL4]]) : (i32, i32) -> i32 +// CHECK: [[VAL4]] = "op3"([[VAL1]]) : (i32) -> i32 + %1 = "op1"(%3) : (i32) -> (i32) + %2 = "test.ssacfg_region"(%1, %2, %3, %4) ({ + %5 = "op2"(%1, %2, %3, %4) : + (i32, i32, i32, i32) -> (i32) + }) : (i32, i32, i32, i32) -> (i32) + %3 = "op2"(%1, %4) : (i32, i32) -> (i32) + %4 = "op3"(%1) : (i32) -> (i32) +} + +// CHECK: "unregistered_func_might_have_graph_region"() ( { +// CHECK: [[VAL1:%.*]] = "foo"([[VAL1]], [[VAL2:%.*]]) : (i64, i64) -> i64 +// CHECK: [[VAL2]] = "bar"([[VAL1]]) +"unregistered_func_might_have_graph_region"() ( { + %1 = "foo"(%1, %2) : (i64, i64) -> i64 + %2 = "bar"(%1) : (i64) -> i64 + "unregistered_terminator"() : () -> () +}) {sym_name = "unregistered_op_dominance_violation_ok", type = () -> i1} : () -> () diff --git a/mlir/test/IR/traits.mlir b/mlir/test/IR/traits.mlir --- a/mlir/test/IR/traits.mlir +++ b/mlir/test/IR/traits.mlir @@ -383,3 +383,82 @@ %0:4 = "test.attr_sized_results"() {result_segment_sizes = dense<[0, 2, 1, 1]>: vector<4xi32>} : () -> (i32, i32, i32, i32) return } + +// ----- + +func @failedHasDominanceScopeOutsideDominanceFreeScope() -> () { + "test.ssacfg_region"() ({ + test.graph_region { + // expected-error @+1 {{operand #0 does not dominate this use}} + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + } + // expected-note @+1 {{operand defined here}} + %1 = "baz"() : () -> (i64) + }) : () -> () + return +} + +// ----- + +// Ensure that SSACFG regions of operations in GRAPH regions are +// checked for dominance +func @illegalInsideDominanceFreeScope() -> () { + test.graph_region { + func @test() -> i1 { + ^bb1: + // expected-error @+1 {{operand #0 does not dominate this use}} + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + // expected-note @+1 {{operand defined here}} + %1 = "baz"(%2#0) : (i1) -> (i64) + return %2#1 : i1 + } + "terminator"() : () -> () + } + return +} + +// ----- + +// Ensure that SSACFG regions of operations in GRAPH regions are +// checked for dominance +func @illegalCDFGInsideDominanceFreeScope() -> () { + test.graph_region { + func @test() -> i1 { + ^bb1: + // expected-error @+1 {{operand #0 does not dominate this use}} + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + br ^bb4 + ^bb2: + br ^bb2 + ^bb4: + %1 = "foo"() : ()->i64 // expected-note {{operand defined here}} + return %2#1 : i1 + } + "terminator"() : () -> () + } + return +} + +// ----- + +// Ensure that GRAPH regions still have all values defined somewhere. +func @illegalCDFGInsideDominanceFreeScope() -> () { + test.graph_region { + // expected-error @+1 {{use of undeclared SSA value name}} + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) + "terminator"() : () -> () + } + return +} + +// ----- + +func @graph_region_cant_have_blocks() { + test.graph_region { + // expected-error@-1 {{'test.graph_region' op expects graph region #0 to have 0 or 1 blocks}} + ^bb42: + br ^bb43 + ^bb43: + "terminator"() : () -> () + } +} diff --git a/mlir/test/lib/Dialect/Test/TestDialect.h b/mlir/test/lib/Dialect/Test/TestDialect.h --- a/mlir/test/lib/Dialect/Test/TestDialect.h +++ b/mlir/test/lib/Dialect/Test/TestDialect.h @@ -18,6 +18,7 @@ #include "mlir/IR/Dialect.h" #include "mlir/IR/OpDefinition.h" #include "mlir/IR/OpImplementation.h" +#include "mlir/IR/RegionKindInterface.h" #include "mlir/IR/StandardTypes.h" #include "mlir/IR/SymbolTable.h" #include "mlir/Interfaces/CallInterfaces.h" diff --git a/mlir/test/lib/Dialect/Test/TestDialect.cpp b/mlir/test/lib/Dialect/Test/TestDialect.cpp --- a/mlir/test/lib/Dialect/Test/TestDialect.cpp +++ b/mlir/test/lib/Dialect/Test/TestDialect.cpp @@ -236,6 +236,34 @@ p.printRegion(op.region(), /*printEntryBlockArgs=*/false); } +//===----------------------------------------------------------------------===// +// Test SSACFGRegionOp +//===----------------------------------------------------------------------===// + +RegionKind SSACFGRegionOp::getRegionKind(unsigned index) { + return RegionKind::SSACFG; +} + +//===----------------------------------------------------------------------===// +// Test GraphRegionOp +//===----------------------------------------------------------------------===// + +static ParseResult parseGraphRegionOp(OpAsmParser &parser, + OperationState &result) { + // Parse the body region, and reuse the operand info as the argument info. + Region *body = result.addRegion(); + return parser.parseRegion(*body, /*arguments=*/{}, /*argTypes=*/{}); +} + +static void print(OpAsmPrinter &p, GraphRegionOp op) { + p << "test.graph_region "; + p.printRegion(op.region(), /*printEntryBlockArgs=*/false); +} + +RegionKind GraphRegionOp::getRegionKind(unsigned index) { + return RegionKind::Graph; +} + //===----------------------------------------------------------------------===// // Test AffineScopeOp //===----------------------------------------------------------------------===// @@ -368,7 +396,7 @@ return {}; } -LogicalResult mlir::OpWithInferTypeInterfaceOp::inferReturnTypes( +LogicalResult OpWithInferTypeInterfaceOp::inferReturnTypes( MLIRContext *, Optional location, ValueRange operands, DictionaryAttr attributes, RegionRange regions, SmallVectorImpl &inferredReturnTypes) { @@ -401,7 +429,7 @@ LogicalResult OpWithShapedTypeInferTypeInterfaceOp::reifyReturnTypeShapes( OpBuilder &builder, llvm::SmallVectorImpl &shapes) { shapes = SmallVector{ - builder.createOrFold(getLoc(), getOperand(0), 0)}; + builder.createOrFold(getLoc(), getOperand(0), 0)}; return success(); } @@ -608,7 +636,7 @@ //===----------------------------------------------------------------------===// // Static initialization for Test dialect registration. -static mlir::DialectRegistration testDialect; +static DialectRegistration testDialect; #include "TestOpEnums.cpp.inc" #include "TestOpStructs.cpp.inc" diff --git a/mlir/test/lib/Dialect/Test/TestOps.td b/mlir/test/lib/Dialect/Test/TestOps.td --- a/mlir/test/lib/Dialect/Test/TestOps.td +++ b/mlir/test/lib/Dialect/Test/TestOps.td @@ -12,6 +12,7 @@ include "mlir/Dialect/Affine/IR/AffineOpsBase.td" include "mlir/IR/OpBase.td" include "mlir/IR/OpAsmInterface.td" +include "mlir/IR/RegionKindInterface.td" include "mlir/IR/SymbolInterfaces.td" include "mlir/Interfaces/SideEffectInterfaces.td" include "mlir/Interfaces/CallInterfaces.td" @@ -1188,6 +1189,30 @@ let printer = [{ return ::print(p, *this); }]; } +def SSACFGRegionOp : TEST_Op<"ssacfg_region", [ + DeclareOpInterfaceMethods]> { + let summary = "operation with an SSACFG region"; + let description = [{ + Test op that defines an SSACFG region. + }]; + + let regions = (region VariadicRegion:$regions); + let arguments = (ins Variadic); + let results = (outs Variadic); +} + +def GraphRegionOp : TEST_Op<"graph_region", [ + DeclareOpInterfaceMethods]> { + let summary = "operation with a graph region"; + let description = [{ + Test op that defines a graph region. + }]; + + let regions = (region AnyRegion:$region); + let parser = [{ return ::parse$cppClass(parser, result); }]; + let printer = [{ return ::print(p, *this); }]; +} + def AffineScopeOp : TEST_Op<"affine_scope", [AffineScope]> { let summary = "affine scope operation"; let description = [{