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,30 @@ ]; } ``` + + +#### 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 @@ -25,20 +25,50 @@ ## High-Level Structure -MLIR is 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). +MLIR is fundamentally based on a graph-like data structure of nodes, +called [Operation](#operations), and edges, called *Values*. Each +Value is the result of exactly one Operation or external Argument, and +has a *Value Type* defined by the [type +system](#type-system). Operations are contained in [Blocks](#blocks) +and Blocks are contained in [Region](#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, 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: @@ -162,21 +192,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 +216,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 for the 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 @@ -241,11 +283,11 @@ ``` 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)* @@ -262,7 +304,7 @@ 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 @@ -308,18 +350,23 @@ ``` 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. +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 that 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 +376,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 @@ -382,23 +429,31 @@ 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)* +value-id-and-type-list ::= value-id-and-type (`,` value-id-and-type)* -block-arg-list ::= `(` ssa-id-and-type-list? `)` +block-arg-list ::= `(` value-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. +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 represent +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, 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. +Blocks in MLIR take a list of block arguments, notated in a +function-like way. Block arguments are bound to values specified by +the 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,43 +471,54 @@ 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 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 +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 (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 @@ -460,17 +526,80 @@ ### Control and Value Scoping -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. +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. Example: ```mlir -func @accelerator_compute(i64, i1) -> i64 { + "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 ot the containing operation. Within these restrictions, +the particular semantics of terminator operations is determined by the +specific dialect operations involved. Note that blocks other than the +entry block which are not listed as a successor of a terminator +operation are 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 { // An SSACFG region ^bb0(%a: i64, %cond: i1): // Code dominated by ^bb0 may refer to %a cond_br %cond, ^bb1, ^bb2 @@ -480,7 +609,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 +622,20 @@ } ``` -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 +646,52 @@ 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. + +Currently graph regions are arbitrarily limited to a single basic +block (the entry block), although this may be expanded to allow +multi-block regions in the future. 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. + +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 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 +^bb2: + %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 +703,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 +719,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 +873,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 +1212,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 +1627,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,63 @@ }; } // 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. + /// 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. + /// 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,36 @@ +//===- 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" +#include "mlir/Support/LLVM.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, +}; + +#include "mlir/IR/RegionKindInterface.h.inc" + +} // namespace mlir + +#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,51 @@ +//===- 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 properties of their regions. + }]; + + let methods = [ + StaticInterfaceMethod< + /*desc=*/[{ + Return the types of regions in an operation. By default, + operations of registered dialects contain regions with CFG + semantics. This implies that they must satisfy the SSA + dominance property. However, other kinds of regions are often + used which may not require SSA dominance. + }], + /*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" @@ -33,13 +34,26 @@ /// Build the dominance for each of the operation regions. op->walk([&](Operation *op) { - for (auto ®ion : op->getRegions()) { + auto kindInterface = dyn_cast(op); + for (unsigned i = 0; i < op->getNumRegions(); i++) { + auto ®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. + 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)); + } } }); } @@ -197,14 +211,31 @@ /// Return true if operation A properly dominates operation B. bool DominanceInfo::properlyDominates(Operation *a, Operation *b) const { auto *aBlock = a->getBlock(), *bBlock = b->getBlock(); + auto *aRegion = a->getParentRegion(); + Operation *ancestor = aRegion->getParentOp(); + auto kindInterface = dyn_cast(ancestor); // 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) { + int i = 0; + for (auto ®ion : ancestor->getRegions()) { + if (aRegion == ®ion) + break; + i++; + } + // Dominance changes based on the region type. + bool hasSSADominance = ancestor->isRegistered() && + (!kindInterface || kindInterface.hasSSADominance(i)); + if (hasSSADominance) { + // If the blocks are the same, then check if b is before a in the block. + return a->isBeforeInBlock(b); + } else { + 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 +252,24 @@ /// 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(); + Operation *ancestor = aRegion->getParentOp(); + auto kindInterface = dyn_cast(ancestor); + int i = 0; + for (auto ®ion : ancestor->getRegions()) { + if (aRegion == ®ion) + break; + i++; + } + bool hasSSADominance = ancestor->isRegistered() && + (!kindInterface || kindInterface.hasSSADominance(i)); + if (hasSSADominance) { + // 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 +290,32 @@ /// 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(); + Operation *ancestor = aRegion->getParentOp(); + auto kindInterface = dyn_cast(ancestor); // 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) { + int i = 0; + for (auto ®ion : ancestor->getRegions()) { + if (aRegion == ®ion) + break; + i++; + } + // Dominance changes based on the region type. + bool hasSSADominance = ancestor->isRegistered() && + (!kindInterface || kindInterface.hasSSADominance(i)); + if (hasSSADominance) { + // If the blocks are the same, then check if b is before a in the block. + return b->isBeforeInBlock(a); + } else { + 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,13 @@ 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 +101,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(); @@ -178,10 +182,30 @@ 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()) + for (unsigned i = 0; i < op.getNumRegions(); i++) { + auto ®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 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,41 @@ 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 (auto &block : region) { + // Dominance is only meaningful inside reachable blocks. if (domInfo->isReachableFromEntry(&block)) - for (auto &op : block) { - if (failed(verifyDominance(op))) - 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(); + // 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(); + } + // 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 (auto &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 (unsigned i = 0; i < op.getNumRegions(); i++) { + auto ®ion = op.getRegion(i); 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,13 @@ return; } + // If the region does not have dominanceInfo, then skip it. This is + // a temporary step. Probably, we just need to apply a different + // traversal method. + 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 @@ -1245,15 +1245,58 @@ } 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 + %c = constant false // CHECK: [[VAL:%.*]] = constant false + return %c : i1 // CHECK: return [[VAL]] : i1 +^bb1: // CHECK: ^bb1: // no predecessors // %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: } + 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: } + +func @graph_region_in_hierarchy_ok() -> i64 { + br ^bb2 // CHECK: br ^bb2 +^bb1: // CHECK: ^bb1: + test.graph_region { + // %1 is well-defined here, since bb2 dominance bb1. + %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: ^bb0 + %1 = "foo"() : ()->i64 // CHECK: [[VAL3]] = "foo"() : () -> i64 + br ^bb1 // CHECK: br ^bb1 +^bb4: // CHECK: ^bb3: // pred: ^bb1 + return %1 : i64 // CHECK: return [[VAL3]] : i64 +} // CHECK: } + +func @graph_region_in_dominance_free_hierarchy_ok() -> () { + test.graph_region { + test.graph_region { + // %1 is well-defined here since defined in graph region + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) + } + %1 = "foo"() : ()->i64 // CHECK: [[VAL3]] = "foo"() : () -> i64 + "test.terminator"() : ()->() + } // CHECK: } + return // CHECK: return +} + +"test.graph_region"() ({ // CHECK: test.graph_region { + %1 = "op1"(%3) : (i32) -> (i32) // CHECK: [[VAL1:%.*]] = "op1"([[VAL3:%.*]]) : (i32) -> i32 + %2 = "test.ssacfg_region"(%1, %2, %3, %4) ({ // CHECK: [[VAL2:%.*]] = "test.ssacfg_region"([[VAL1]], [[VAL2]], [[VAL3]], [[VAL4:%.*]]) ( { + %5 = "op2"(%1, %2, %3, %4) : + (i32, i32, i32, i32) -> (i32) // CHECK: [[VAL5:%.*]] = "op2"([[VAL1]], [[VAL2]], [[VAL3]], [[VAL4]]) : (i32, i32, i32, i32) -> i32 + }) : (i32, i32, i32, i32) -> (i32) // CHECK: }) : (i32, i32, i32, i32) -> i32 + %3 = "op2"(%1, %4) : (i32, i32) -> (i32) // CHECK: [[VAL3]] = "op2"([[VAL1]], [[VAL4]]) : (i32, i32) -> i32 + %4 = "op3"(%1) : (i32) -> (i32) // CHECK: [[VAL4]] = "op3"([[VAL1]]) : (i32) -> i32 +}) : () -> () + +"unregistered_func"() ( { // CHECK: "unregistered_func"() ( { + %1 = "foo"(%1, %2) : (i64, i64) -> i64 // CHECK: [[VAL1:%.*]] = "foo"([[VAL1]], [[VAL2:%.*]]) : (i64, i64) -> i64 + %2 = "bar"(%1) : (i64) -> i64 // CHECK: [[VAL2]] = "bar"([[VAL1]]) + "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,130 @@ %0:4 = "test.attr_sized_results"() {result_segment_sizes = dense<[0, 2, 1, 1]>: vector<4xi32>} : () -> (i32, i32, i32, i32) return } + +// ----- + +func @succeededDominanceFreeScope() -> () { + test.graph_region { + // %1 is not dominated by its definition. + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) + %1 = "baz"(%2#0) : (i1) -> (i64) // CHECK: [[VAL3]] = "baz"([[VAL2]]#0) : (i1) -> i64 + } + return +} // CHECK: } + +// ----- + +func @succeededFeedbackInDominanceFreeScope() -> () { + test.graph_region { + // %1 is not dominated by its definition. + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1) + %1 = "foo"() : ()->i64 // CHECK: [[VAL3]] = "foo"() : () -> i64 + } + return // CHECK: return +} // CHECK: } + +// ----- + +func @succeededHasDominanceScopeOutsideDominanceFreeScope() -> () { + "test.ssacfg_region"() ({ + %1 = "baz"() : () -> (i64) // CHECK: [[VAL3:%.*]] = "baz"() : () -> i64 + test.graph_region { // CHECK: test.graph_region { + // %1 is not dominated by its definition. + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3]]) : (i64) -> (i1, i1, i1) + } // CHECK: } + %3 = "baz"() : () -> (i64) // CHECK: [[VAL4:.*]] = "baz"() : () -> i64 + }) : () -> () // CHECK: } + 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 +} + +// ----- + +func @succeeededDominanceFreeScopeOutsideHasDominanceScope() -> () { + test.graph_region { // CHECK: test.graph_region { + "test.ssacfg_region"() ({ // CHECK: "test.ssacfg_region"() ( { + %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: %1:3 = "bar"(%0) : (i64) -> (i1, i1, i1) + }) : () -> () // CHECK: }) : () -> () + %1 = "baz"() : () -> (i64) // CHECK: %0 = "baz"() : () -> i64 + } // CHECK: } + return // CHECK: return +} // CHECK: } + +// ----- + +// 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 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 @@ -237,6 +237,34 @@ } //===----------------------------------------------------------------------===// +// 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 mlir::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 = [{