[MLIR] Add RegionKindInterface

[stephenneuendorffer]

Summary

Some dialects have semantics which is not well represented by common
SSA structures with dominance constraints. This patch allows
operations to declare the 'kind' of their contained regions.
Currently, two kinds are allowed: "SSACFG" and "Graph". The only
difference between them at the moment is that SSACFG regions are
required to have dominance, while Graph regions are not required to
have dominance. The intention is that this Interface would be
generated by ODS for existing operations, although this has not yet
been implemented. Presumably, if someone were interested in code
generation, we might also have a "CFG" dialect, which defines control
flow, but does not require SSA.

The new behavior is mostly identical to the previous behavior, since
registered operations without a RegionKindInterface are assumed to
contain SSACFG regions. However, the behavior has changed for
unregistered operations. Previously, these were checked for
dominance, however the new behavior allows dominance violations, in
order to allow the processing of unregistered dialects with Graph
regions. One implication of this is that regions in unregistered
operations with more than one op are no longer CSE'd (since it
requires dominance info).

I've also reorganized the LangRef documentation to remove assertions
about "sequential execution", "SSA Values", and "Dominance". Instead,
the core IR is simply "ordered" (i.e. totally ordered) and consists of
"Values". I've also clarified some things about how control flow
passes between blocks in an SSACFG region. Control Flow must enter a
region at the entry block and follow terminator operation successors
or be returned to the containing op. Graph regions do not define a
notion of control flow.

see discussion here:
https://llvm.discourse.group/t/rfc-allowing-dialects-to-relax-the-ssa-dominance-condition/833/53

[rriddle]

mlir/docs/LangRef.md

30

nit: I find this definition confusing given that arguments to blocks are also values.

41

I feel the same way as Mehdi. I would rephrase to something like:

Operations can be arbitrarily extended in MLIR, and may represent many different concepts ...
...

I would even consider removing the bit about verification. Feels a bit out of place here.

204–211

nit: are only in scope

206

This isn't true. This goes into symbol table semantics, which scopes the visibility with its own set of rules. https://mlir.llvm.org/docs/SymbolsAndSymbolTables/

420

Can you reword this? It gives off the vibe that the terminator is actually generating the value, but terminator operations don't generally have results. Some terminator operations may produce the PHI value internally, but those are not very common. I would rephrase to "provided" or something similar.

497

nit: Can you mention IsolatedFromAbove here and link to the doc on it?

535

However, the particular semantics of operations are
unspecified and completely specify the behavior of an operation and
inside the regions of an operation.

Can you rephrase this? I'm having trouble parsing it.

538

nit: Link to the documentation for this.

540

I don't agree on the principal here. We only have to be conservative if it "could" be something that has valid semantics when registered. For example, we have to be conservative about unregistered operations that "could" be symbol tables, but that doesn't mean we error out if we see any unregistered region holding operation. Being unregistered IMO is just having the capability of being anything legal. If something isn't legal when registered, why should we guard against it when unregistered?

545

nit: the potential successor blocks

547

Correct. There is no modeling ATM for indirect branches where you have no idea what the potential destination could be.

553

nit: are treated as unreachable and may be

577

nit: Regions -> regions

mlir/include/mlir/IR/RegionKindInterface.h

2

This line looks like it is one character to short.

15

Please fix the header guard style.

18

Can you trim these?

27

Please add documentation here on what these are and what they mean.

30

Graph? SSACFG contains acronyms so I see why they are capitalized.

mlir/include/mlir/IR/RegionKindInterface.td

28

nit: Can you reflow this and move it to the next line? The doc formatter can handle this automatically.

28

Missing period at the end of the summary.

31

nit: Remove double space.

40

nit: Please use multi line string for this description.

48

Leftover debugging?

56

Please remove.

61

Please fix the header guard style.

mlir/include/mlir/Interfaces/CMakeLists.txt

7

Seems unrelated.

mlir/lib/IR/RegionKindInterface.cpp

19

I don't think this is necessary.

mlir/lib/IR/Verifier.cpp

31

I don't think this is necessary.

[rriddle]

mlir/test/lib/Dialect/Test/TestDialect.cpp

227

Please remove the mlir:: from each of these.

[stephenneuendorffer]

Update after review changes

mlir/docs/Interfaces.md

232

Certainly! I figure writing a few by hand would lead us to that.

mlir/docs/LangRef.md

33

Yes, exactly. The point of this is that the order of instructions in the IR does not need to correspond to the execution order of instructions in a sequential machine. Even in a graph, the IR still maintains an order, which enables deterministic round-tripping, for instance.

41

What is an "Operation Definition" other than traits, interfaces, and verification constraints? operand and result names? successor names? I've reworded this section.

468–474

How so? The point of this is to show the structures that are important and that are the requirements on those structures, so I'm trying to define a region structurally separate from the CFG semantics. What would you add to this, other than "it's a CFG?"

540

@rriddle I don't understand whether you are disagreeing with Mehdi or me.

I think that if ops are unregistered we should be pretty liberal about what should be allowed. Structually, the only requirement I've imposed on regions of unregistered ops is that all value identifiers must be defined. In particular, I have not required that regions of unregistered operations must be either 1) a single block or 2) a valid SSACFG region with dominance. (I think this was suggested in the discussion)

545

we don't call them "potential successors' anywhere else. I think the meaning is clear from the following sentence

547

I was also thinking about something co-routine like where Blocks could yield to another block chosen by the containing operation.

[rriddle]

mlir/docs/LangRef.md

547

You could also implement coroutines with an explicit switch in the entry block that contains each of the potential resume points.

[rriddle]

mlir/lib/IR/Verifier.cpp

236

I don't think this is correct. You are missing checks for how dominance interacts across different regions. Even if there is no intra-region dominance, there are still constraints how values may be used across regions. For example, the operand values have to be defined in this region or an ancestor region. This is also missing checks on how verification happens when the value is defined in a region with dominance and used in a region without. The dominance relationship between the ancestor operation in the region with dominance must still be checked, i.e.,

// region with dominance
func @foo() {
  // region without dominance
  bar.non_dominance_region {
    // Verifier failure: This is a non-dominating use.
    bar.use %foo_value
    bar.return
  }
  %foo_value = constant true

[mehdi_amini]

mlir/docs/LangRef.md

33

Yes, exactly

I was pointing out something that seems contradictory, so I'm puzzled by your answer here?

Even in a graph, the IR still maintains an order, which enables deterministic round-tripping, for instance.

Yes but there is still no total order since you have cycles.

The point of this is that the order of instructions in the IR does not need to correspond to the execution order of instructions in a sequential machine.

OK but the way it is written is still confusing to me. You're also using "Region" as if it is a well defined term while it is the first use in the doc.
I'll look for an alternative writing after we settle on the description of multi-blocks region below.

Operations are also organized into [Blocks](#blocks) and are totally ordered
within their containing [Region](#regions)

540

In particular, I have not required that regions of unregistered operations must be either 1) a single block or 2) a valid SSACFG region with dominance. (I think this was suggested in the discussion)

This complicates the design, and I don't believe your specification is complete right now with respect to non-CFG multi-blocks region.

The paragraph that follows is a good example, when it says that when control flow enters a region, it always begins in the first block of the region, called the *entry* block we already have a notion of control for the blocks. Then 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.
In your example above:

"unregistered_op" () ({
^bb1:
  %2 = %1
  %1 = %2
^bb2:
  %3 = %2
}

The second block is clearly unreachable and can just be deleted.

It also means that:

"unregistered_op" () ({
^bb1:
  %2 = %3
  %1 = %2
^bb2:
  %3 = ...
}

Would be invalid IR.

[stephenneuendorffer]

mlir/docs/LangRef.md

33

OK.. I see there being several relationships here. One is the total order of operations in a block and blocks in a region. There is a separate relationship which is the data dependence relationship, which I don't think is actually a partial order on operations in Graph regions or SSACFG regions. Certainly not if terminator edges are included.

540

My intention is that the "Control Flow" section here only applies to SSACFG regions. Maybe there needs to be a separate section on Graph regions. Your example illustrates why 'reachability' of basic blocks is probably not a great concept in graph regions.

mlir/lib/IR/Verifier.cpp

236

Right... I think some more test cases are in order here.

[mehdi_amini]

mlir/docs/LangRef.md

468–474

I see the structure as trivial: only the semantics is complex (i.e. reachability, control-flow, etc.).

So I'm not sure what's the point of long description of what could be shown with a few lines of grammar specification (or even 10 lines of C++).

[stephenneuendorffer]

mlir/docs/LangRef.md

468–474

I think the structure is actually harder to grok than you might think for outsiders. Also, I think the syntactic issues of how it is represented as a grammar doesn't necessarily reflect what you need to know to use it from c++. (In fact, I've been considering if these need to be separated further, having a separate page for an abstract description and leave most of what is currently in LangRef.md as a description of the concrete grammar syntax.)

I think one of the things that is missing right now is that the semantics is quite flexible, but not without bounds. Also the syntax is quite flexible, but also not without bounds. I see this as a step towards being explicit about those bounds, at least on the semantic side.

mlir/lib/IR/Dominance.cpp

37–56 ↗

(On Diff #274277)

FYI: This is a significant departure from the previous patch, which attempted to put the 'smarts' in the Verifier. It seems like in order to deal properly with Mehdi's testcase where a graph region encloses an SSACFG region, without duplicating alot of the traversal, that all kinds of regions need a notion of dominance. It seems to me that the right notion of dominance for graph regions is that all values are in-scope in all blocks. so: all blocks dominate all other blocks and all values within a block dominate all other values. This also highlights the fact that CSE needs some different machinery to properly handle Graph Regions, since it currently traverses using DominatorTrees.

mlir/lib/IR/Verifier.cpp

236

I've added some tests for this. The more problematic case is the reverse:

// region without dominance
bar.non_dominance_region() {
  // region with dominance
  bar.dominance_region {
    // Should this be illegal?
    bar.use %foo_value
    bar.return
  }
  %foo_value = constant true

It's not clear to me that there is a useful interpretation for this. At the moment I've made this illegal, but it's something that could conceivably be relaxed.

[stephenneuendorffer]

mlir/lib/IR/Verifier.cpp

236

The code above is actually legal, since "%foo_value" is legal to use as an argument to bar.dominance_region

[rriddle]

mlir/lib/IR/Verifier.cpp

236

The fairly simple rule that I've always applied to dominance is that the parent operations act as dominance synch points. The parent operation of the definition has to dominate the ancestor of the user that is within that region.

[stephenneuendorffer]

mlir/lib/IR/Verifier.cpp

236

Agreed. And I think this lifts immediately to Graph Regions: In a Graph Region, everything dominates everything else.

[mehdi_amini]

mlir/docs/LangRef.md

426

This defines block in a way that does not seem to me to be compatible with graph regions.

480

You define a notion of successor here, does it generalize to graph region?

521

in which case some other operation will execute

That does not read well to me right now.

530–581

It is interesting that this ends up nested under the SSACFG region case

599

typo: relatinoships

601

I think it should be either with values representing streams of data. or where values represent streams of data.

629

The story about block terminators, successors, etc. isn't clear to me with respect to graph region. Even the relationship between blocks isn't entirely clear here actually.

mlir/include/mlir/IR/Dominance.h

63 ↗

(On Diff #274283)

The concept of entry block is no longer a guarantee

[stephenneuendorffer]

mlir/docs/LangRef.md

480

Currently we keep around blocks in a graph region after transforming from an SSACFG region. The blocks aren't semantically meaningful (and can be eliminated in our current model without changing the semantics), but are at least useful bookkeeping.

521

I agree it's a little vague, but it's trying to bridge into the next section which talks about control flow and terminators. Do you have a suggestion?

530–581

It's all about control flow with multiple regions. Graph regions don't have a notion of control flow.

629

Correct, I haven't defined any semantic requirements about blocks in graph regions.

mlir/include/mlir/IR/Dominance.h

63 ↗

(On Diff #274283)

There are some aspects of the interface of this class which are awkward. If regions define their own concept of dominance, then there probably needs to be an abstract interface exposing different implementations of the 'local' concept of dominance. Currently, the two implementations are somewhat awkwardly tangled together along with the hierarchy traversing code. I see that there should be some additional refactoring of this code which might push the local concept of dominance into RegionKindInterface, but I'd like to get the concepts agreed to first.

Another example is that getRootNode() has to be guarded by hasDominanceInfo(). getRootNode() isn't really appropriate for regions without an entry block.

[mehdi_amini]

mlir/docs/LangRef.md

33

In the definition of Blocks, we just wrote A *Block* is an ordered list of operations, can we just do the same here and avoid "totally ordered"?
Maybe like the following:

Operations are also organized into [Blocks](#blocks) as ordered list  (the order may or may not have a semantics important, see [Region Kinds](link)).  Blocks are themselves organized as an ordered list within their containing [Region](#regions).

45

each transformation on operations to be designed with the semantics in mind

I don't understand what this means here.

205

Argument identifiers in mapping functions

Not sure what "mapping function" refers to here? It is in the existing doc, but this is the only place it is used. I wonder if it isn't something remaining from before functions were regular Operations?

Is this about block argument? Can you just write "Block argument" instead?

Edit: I wonder if this is about affine maps?
(we can leave this out of this revision, but we should probably revisit this)

207

Particular operations may further limit the valid scope of identifiers

I think this is not specific enough: the scope is only limited by the region kind and I'd rather spell it out this way.
With how you wrote it, one could think that we could have an operation restricting the scope of the value it produces (for example to be block-local).

333

It isn't clear to me why a module wouldn't be a graph region?
Do we put any meaning to the order of operations in a module?

414

Is "commonly" intended to express that this isn't always the case?
What about spelling out the exact case: "In a SSACFG region, blocks represent ...`

421

i.e. Branches

Shouldn't this be e.g. instead?

463

I feel the section here isn't entirely complete with respect to non CFG region with multiple blocks: are these still having terminator? What's the contract on block arguments?

An example would be worthwhile as well.

[mehdi_amini]

mlir/docs/LangRef.md

629

To me this is like my comment above about terminator, successor, etc.
Even if it isn't requires, let's make it explicit.

[stephenneuendorffer]

mlir/docs/LangRef.md

45

I've rewritten this section.

205

Yes, I believe this is talking about affine maps.

207

You're right, that could be misleading. I've rewritten it.

333

I suppose it could be, although it's somewhat of a degenerate kind of region anyway, since modules don't define any values and don't contain blocks. Maybe this should be another kind of region?

463

I added an additional note about the Graph Region rationale, but I'm really not sure how to provide an example here of something that I don't have a good example of :). Let's chat offline about this.

[mehdi_amini]

mlir/docs/LangRef.md

628

The indentation does not seem right in this example?
The reuse of %2 does not help readability either, just like %4 before %2

[rriddle]

Thanks for all of the work on this! Mostly nits, so I think this looks good enough to land for now after resolving. We can iterate on the other necessary aspects afterwards.

mlir/docs/Interfaces.md

206

nit: Drop the newline here.

232

ODS can already generate the documentation. I'll take a look at hooking it into here after this lands.

https://github.com/llvm/llvm-project/blob/bf74c3838904b2df2a0f31bc457af1bdb811953f/mlir/tools/mlir-tblgen/OpInterfacesGen.cpp#L414

mlir/docs/LangRef.md

29

nit: *Operations* to match the *Values* later.

30

nit: I would clarify Argument ->Block Argument here.

33

nit: Regions to match the tense of the others.

206

nit: You may want to clarify here that nested regions count as being within the parent region.

333

Should a module be an SSA CFG region? It could very well be a graph region.

(This is not meant to block anything, but something to consider for the future).

338

nit: Could you please you link symbol name to the symbol doc again here?

414

typo: represent represents

420

Seems like this only applies to non-entry blocks, as the entry block(s) may have values provided the parent operation.

480

nit: Can you remove the double space before The.

494

nit; Same here, seems to be a few double space sentences in this paragraph.

503

nit: Remove the indent of this code snippet.

515

nitL Double space here.

529

nit: Double space here.

542

typo: ot.

605

nit: Can you wrap this in a Context or Rationale section? I think there are other examples in this doc.

617

nit: I would likely mention that terminator operations cannot be re-ordered.

632

Remove this now?

mlir/include/mlir/IR/Dominance.h

71 ↗

(On Diff #277631)

nit: Can you remove the double space sentences in this file?

89 ↗

(On Diff #277631)

nit: B, i.e.

97 ↗

(On Diff #277631)

Same here and below: B, i.e.

mlir/include/mlir/IR/RegionKindInterface.h

19

I don't think this one is necessary.

23

nit: Please use /// here.

mlir/include/mlir/IR/RegionKindInterface.td

23

There is a good doc for this in Interfaces.md, can you paste that here?

25

nit: You should be able to set the namespace(via cppNamespace) now.

31

Unresolved?

41

nit: the strings are slightly misaligned here.

mlir/lib/IR/Dominance.cpp

38 ↗

(On Diff #277631)

nit: Cache the end iterator of this loop.

39 ↗

(On Diff #277631)

nit: Spell out auto here.

231 ↗

(On Diff #277631)

nit: Drop else after return.

255 ↗

(On Diff #277631)

nit: Please drop the uses of mlir:: in this file.

257 ↗

(On Diff #277631)

nit: Can you define a static helper for this in this file?

static bool hasSSADominance(Operation *op, RegionKindInterface interface, unsigned regionNum) {
    return ancestor->isRegistered() &&
          (!kindInterface || kindInterface.hasSSADominance(aRegionNum));
}

303 ↗

(On Diff #277631)

Same here, drop else after return.

mlir/lib/IR/Verifier.cpp

189

nit: Cache the end iterator here.

190

nit: Spell out auto here.

204

nit: expected graph region?

254

nit: Spell out auto here.

263

nit: Cache the end iterator here, and can you inline the region variable below into its use?

mlir/lib/Transforms/CSE.cpp

174 ↗

(On Diff #277631)

Can you reword the second part of this into a TODO:?

175 ↗

(On Diff #277631)

nit: Drop the double space here.

177 ↗

(On Diff #277631)

nit: Drop trivial braces.

mlir/test/IR/parser.mlir

1248

Can you move the CHECK lines to non-IR lines to match the other tests? Ends up being much cleaner IMO.

mlir/test/IR/traits.mlir

373

nit: Please remove the CHECK lines that don't relate to what you are checking. This applies to the other tests as well. e.g. You don't really need to check return or the braces here.

382

nit: This comment seems wrong.

395

nit: Can you indent these expected lines? Same below.

409

nit: Please remove the explicit SSA value names, and please remove the unnecessary bits of this test.

472

nit: Indent the graph region.

mlir/test/lib/Dialect/Test/TestDialect.cpp

227

Unresolved here?

mlir/test/lib/Dialect/Test/TestOps.td

1158

nit: You could use a "" for the descriptions as well.

[stephenneuendorffer]

If there are no further comments, I'd like to commit this. @bondhugula @mehdi_amini Do you want to accept?

Note that there's a small amount of new text under "### Regions" where I tried to capture the understanding about how Region Arguments are shared with the Block Arguments of the entry block, but that operation arguments/return values are explicitly decoupled from region arguments and terminators. Also terminator arguments do not need to match the block arguments of their successor blocks. All of this is under the control of specific operations and may be arbitrarily defined.

mlir/docs/LangRef.md

553

I've reworded this.

628

Actually, there were a few other minor problems with this testcase, including the fact that it missed out on the fact that:

%1 = op(%1)

should be valid, along with:

%1 = op() { otherop(%1) }

I also turned this into another testcase.

[mehdi_amini]

LGTM

[bondhugula]

mlir/include/mlir/IR/Dominance.h

87–93 ↗

(On Diff #277998)

Reflow: I think you aren't using the whole width.

mlir/lib/IR/Dominance.cpp

27 ↗

(On Diff #277998)

These should be ///

43 ↗

(On Diff #277998)

Nit: This should be //.

263–265 ↗

(On Diff #277998)

Nit: reflow to use width.

mlir/lib/IR/Verifier.cpp

65

Nit: terminate comment with period.

[bondhugula]

Quick question: how do we know in printed IR if something is a graph region or an SSA one?

mlir/docs/LangRef.md

30

a Block Argument?

42–72

Nit: Reflow to use width.

[stephenneuendorffer]

In D80358#2153978, @bondhugula wrote:

Quick question: how do we know in printed IR if something is a graph region or an SSA one?

You don't. Syntactically, there is no distinction for unregistered ops. Unregistered ops are handled conservatively as graph regions, so they are allowed to violate SSA dominance. Passes that require dominance-order traversal (i.e. CSE) won't operate on regions inside unregistered ops.

mlir/docs/LangRef.md

30

I parse it as 'exactly one (Operation or Block Argument)', so I think it makes sense as is?

mlir/docs/Interfaces.md

def ExampleOpInterface : OpInterface<"ExampleOpInterface"> {
   let methods = [
     InterfaceMethod<
       "Get the number of inputs for the current operation.",
       "unsigned", "getNumInputs"
     >,
   ];
 }
 ```
+
+
+#### Operation Interface List
+
+MLIR provides a suite of interface that provide various functionalities that are
+common across many different operations. Below is a list of some key traits that
+may be used directly by any dialect. The format of the header for each trait
+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<Type> 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 
+     - `hasDominance(unsigned index)` - Return true if the region with the given index inside this operation requires dominance.
+

mlir/docs/LangRef.md

 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
-[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 defined as the result of exactly one Operation, and has a
+*Value Type* defined by the [type system](#type-system). Operations
+are also organized into [Blocks](#blocks) and are totally ordered
+within their containing [Region](#regions). 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 *Operation Types*,
+which can be arbitrarily extended in MLIR. Verification constraints on
+valid data structures are part of the an Operation Type, 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:
 
 ```mlir
 // Compute A*B using an implementation of multiply kernel and print the
 // result using a TensorFlow op. The dimensions of A and B are partially
 // known. The shapes are assumed to match.
 func @mul(%A: tensor<100x?xf32>, %B: tensor<?x50xf32>) -> (tensor<100x50xf32>) {
   // Compute the inner dimension of %A using the dim operation.
   %n = dim %A, 1 : tensor<100x?xf32>
 
   // Allocate addressable "buffers" and copy tensors %A and %B into them.
   %A_m = alloc(%n) : memref<100x?xf32>
   tensor_store %A to %A_m : memref<100x?xf32>
 
   %B_m = alloc(%n) : memref<?x50xf32>
   tensor_store %B to %B_m : memref<?x50xf32>
 
   // Call function @multiply passing memrefs as arguments,
   // and getting returned the result of the multiplication.
   %C_m = call @multiply(%A_m, %B_m)
           : (memref<100x?xf32>, memref<?x50xf32>) -> (memref<100x50xf32>)
 
   dealloc %A_m : memref<100x?xf32>

 ### Identifiers and keywords
 
 Syntax:
 
 ```
 // 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)*
+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`.
 
 MLIR guarantees identifiers never collide with keywords by prefixing identifiers
 with a sigil (e.g. `%`, `#`, `@`, `^`, `!`). In certain unambiguous contexts
 (e.g. affine expressions), identifiers are not prefixed, for brevity. New
 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 in scope for the region in which they are
+defined. Argument identifiers in mapping functions are in scope for
+the mapping body. Function identifiers and mapping identifiers are
+visible across the entire module. Particular operations may further
+limit the valid scope of identifiers. For instance, the scope of
+values in a region with SSA control flow semantics may be constrained
+according to the standard definition of
+[dominance](https://en.wikipedia.org/wiki/Dominator_\(graph_theory\)).
 
 ## Dialects
 
 Dialects are the mechanism by which to engage with and extend the MLIR
 ecosystem. They allow for defining new [operations](#operations), as well as
 [attributes](#attributes) and [types](#type-system). Each dialect is given a
 unique `namespace` that is prefixed to each defined attribute/operation/type.
 For example, the [Affine dialect](Dialects/Affine.md) defines the namespace:

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

 ### Module
 
 ```
 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
+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.
 
 ### 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)):
 
 ```
 function ::= `func` function-signature function-attributes? function-body?
 
 function-signature ::= symbol-ref-id `(` argument-list `)`
                        (`->` function-result-list)?
 
 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
 function-result-list-parens ::= `(` `)`
                               | `(` function-result-list-no-parens `)`
 function-result-list-no-parens ::= function-result (`,` function-result)*
 function-result ::= type attribute-dict?
 

 
 Syntax:
 
 ```
 block           ::= block-label operation+
 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.
-
-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.
+A [block] is an ordered list of operations, concluding with a single
+[terminator operation](#terminator-operations). Blocks commonly
+represent a compiler [basic block]
+(https://en.wikipedia.org/wiki/Basic_block) where instructions inside
+the block are executed in the given 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 produced by
+all terminator operations, i.e. Branches, which connect to the
+block. In this way, MLIR implicitly represents 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:
 
 ```mlir
 func @simple(i64, i1) -> i64 {
 ^bb0(%a: i64, %cond: i1): // Code dominated by ^bb0 may refer to %a
   cond_br %cond, ^bb1, ^bb2
 
 ^bb1:
   br ^bb3(%a: i64)    // Branch passes %a as the argument
 
 ^bb2:
   %b = addi %a, %a : i64
   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)].
 
 ## 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 sequence of MLIR [Blocks](#blocks), commonly
+used to represent a Control-Flow Graph (CFG). 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 their containing operation and have no type or attributes.
 
 The first block in the region cannot be a successor of any other block. The
 syntax for the 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
 of the function signature).
 
 ### 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 nested control isolation: 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, 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.
 
 Example:
 
 ```mlir
 func @accelerator_compute(i64, i1) -> i64 {
 ^bb0(%a: i64, %cond: i1): // Code dominated by ^bb0 may refer to %a
   cond_br %cond, ^bb1, ^bb2
 
 ^bb1:
   // This def for %value does not dominate ^bb2
   %value = "op.convert"(%a) : (i64) -> i64
   br ^bb3(%a: i64)    // Branch passes %a as the argument
 
 ^bb2:
   "accelerator.launch"() {
     ^bb0:
       // Region of code nested under "accelerator.launch", it can reference %a but
       // not %value.
       %new_value = "accelerator.do_something"(%a) : (i64) -> ()
   }
   // %new_value cannot be referenced outside of the region
 
 ^bb3:
   ...
 }
 ```
 
 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
+### Modeling 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.
+MLIR blocks and regions are intended to be syntactically rich,
+enabling the modeling of a wide variety of semantics, including the
+standard notion of sequential control flow through basic
+blocks. However, the particular semantics of operations are
+unspecified and completely specify the behavior of an operation and
+inside the regions of an operation. In MLIR, control flow semantics of
+a region is indicated by `RegionKindInterface::SSACFG`.
+
+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, as in a
+`branch` operation. Control flow can only pass to the specified
+successor block, or back to the containing operation, as in a `return`
+operation. 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.
+
+#### 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. 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 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
 
 Regions allow defining an operation that creates a closure, for example by
 “boxing” the body of the region into a value they produce. It remains up to the
 operation to define its semantics. Note that if an operation triggers
 asynchronous execution of the region, it is under the responsibility of the
 operation caller to wait for the region to be executed guaranteeing that any
 directly used values remain live.
 
 ### Arguments and Results
 
 The arguments of the first block of a region are treated as arguments of the
 region. The source of these arguments is defined by the semantics of the parent
 operation. They may correspond to some of the values the operation itself uses.
 
 Regions produce a (possibly empty) list of values. The operation semantics
 defines the relation between the region results and the operation results.
 
 ## 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.
 
 MLIR has an open type system (i.e. there is no fixed list of types), and types
 may have application-specific semantics. For example, MLIR supports a set of
 [dialect types](#dialect-types).
 
 ```
 type ::= type-alias | dialect-type | standard-type
 
 type-list-no-parens ::=  type (`,` type)*
 type-list-parens ::= `(` `)`
                    | `(` type-list-no-parens `)`
 
 // This is a common way to refer to an SSA value with a specified type.
 ssa-use-and-type ::= ssa-use `:` type
 
 // Non-empty list of names and types.
 ssa-use-and-type-list ::= ssa-use-and-type (`,` ssa-use-and-type)*
 ```
 
 ### Type Aliases
 
 ```
 type-alias-def ::= '!' alias-name '=' 'type' type
 type-alias ::= '!' alias-name
 ```
 
 MLIR supports defining named aliases for types. A type alias is an identifier
 that can be used in the place of the type that it defines. These aliases *must*
 be defined before their uses. Alias names may not contain a '.', since those
 names are reserved for [dialect types](#dialect-types).
 
 Example:
 
 ```mlir

 
 This attribute can only be held internally by
 [array attributes](#array-attribute) and
 [dictionary attributes](#dictionary-attribute)(including the top-level operation
 attribute dictionary), i.e. no other attribute kinds such as Locations or
 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.
 
 See [`Symbols And SymbolTables`](SymbolsAndSymbolTables.md) for more
 information.
 
 #### Type Attribute

mlir/include/mlir/IR/CMakeLists.txt

 add_mlir_interface(OpAsmInterface)
 add_mlir_interface(SymbolInterfaces)
+add_mlir_interface(RegionKindInterface)

mlir/include/mlir/IR/RegionKindInterface.h

+//===- RegionKindInterface.h - Infer Type 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_INTERFACES_REGIONKINDINTERFACE_H_
+#define MLIR_INTERFACES_REGIONKINDINTERFACE_H_
+
+#include "mlir/IR/Attributes.h"
+#include "mlir/IR/Builders.h"
+#include "mlir/IR/Location.h"
+#include "mlir/IR/OpDefinition.h"
+#include "mlir/Support/LLVM.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace mlir {
+
+enum class RegionKind {
+  Unknown,
+  SSACFG,
+  GRAPH,
+};
+
+#include "mlir/IR/RegionKindInterface.h.inc"
+
+} // namespace mlir
+
+#endif // MLIR_INTERFACES_REGIONKINDINTERFACE_H_

mlir/include/mlir/IR/RegionKindInterface.td

+//===- 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_REGIONKINDOPINTERFACE
+#define MLIR_REGIONKINDOPINTERFACE
+
+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=*/"hasDominance",
+      /*args=*/(ins "unsigned":$index),
+      /*methodBody=*/[{
+        return getRegionKind(index) == RegionKind::SSACFG;
+      }]
+      // /*defaultImplementation=*/[{
+      //   /// Returns whether two arrays are equal as strongest check for
+      //   /// compatibility by default.
+      //   return lhs == rhs;
+      // }]
+    >,
+  ];
+
+  // let verify = [{
+  //   return detail::verifyInferredResultTypes($_op);
+  // }];
+}
+
+#endif // MLIR_REGIONKINDOPINTERFACE

mlir/include/mlir/Interfaces/CMakeLists.txt

 add_mlir_interface(CallInterfaces)
 add_mlir_interface(ControlFlowInterfaces)
 add_mlir_interface(DerivedAttributeOpInterface)
 add_mlir_interface(InferTypeOpInterface)
 add_mlir_interface(LoopLikeInterface)
 add_mlir_interface(SideEffectInterfaces)
 add_mlir_interface(ViewLikeInterface)
-

mlir/lib/IR/CMakeLists.txt

add_mlir_library(MLIRIR
   IntegerSet.cpp
   Location.cpp
   MLIRContext.cpp
   Module.cpp
   Operation.cpp
   OperationSupport.cpp
   PatternMatch.cpp
   Region.cpp
+  RegionKindInterface.cpp
   StandardTypes.cpp
   SymbolTable.cpp
   Types.cpp
   TypeUtilities.cpp
   Value.cpp
   Verifier.cpp
   Visitors.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${MLIR_MAIN_INCLUDE_DIR}/mlir/IR
 
   DEPENDS
   MLIRCallInterfacesIncGen
   MLIROpAsmInterfaceIncGen
   MLIRSymbolInterfacesIncGen
+  MLIRRegionKindInterfaceIncGen
 
   LINK_LIBS PUBLIC
   MLIRSupport
   )

mlir/lib/IR/RegionKindInterface.cpp

+//===- 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;
+
+namespace mlir {
+#include "mlir/IR/RegionKindInterface.cpp.inc"
+} // namespace mlir

mlir/lib/IR/Verifier.cpp

 // are not mutable and can be checked at time of construction.
 //
 //===----------------------------------------------------------------------===//
 
 #include "mlir/IR/Verifier.h"
 #include "mlir/IR/Attributes.h"
 #include "mlir/IR/Dialect.h"
 #include "mlir/IR/Dominance.h"
+#include "mlir/IR/OpDefinition.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"
 #include "llvm/Support/Regex.h"
 
 using namespace mlir;
 
 namespace {
public:
   }
 
 private:
   /// Verify the given potentially nested region or block.
   LogicalResult verifyRegion(Region &region);
   LogicalResult verifyBlock(Block &block);
   LogicalResult verifyOperation(Operation &op);
 
-  /// Verify the dominance within the given IR unit.
-  LogicalResult verifyDominance(Region &region);
-  LogicalResult verifyDominance(Operation &op);
+  /// Verify the dominance property of operations within the given
+  /// Region.  If hasDominance is false, then this simply recurses
+  /// through the contained operations.  if hasDominance is set, then
+  /// the dominance property of contained operations is also checked.
+  LogicalResult verifyDominance(Region &region, bool hasDominance);
+
+  /// 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) {
     // Take the location information for the first operation in the block.
     if (!bb.empty())
       return bb.front().emitError(message);
 
     // Worst case, fall back to using the parent's location.
     return mlir::emitError(bb.getParent()->getLoc(), message);
if (failed(verifyOperation(op)))
     return failure();
 
   // Since everything looks structurally ok to this point, we do a dominance
   // check for any nested regions. We do this as a second pass since malformed
   // CFG's can cause dominator analysis constructure to crash and we want the
   // verifier to be resilient to malformed code.
   DominanceInfo theDomInfo(&op);
   domInfo = &theDomInfo;
-  for (auto &region : op.getRegions())
-    if (failed(verifyDominance(region)))
-      return failure();
+  if (failed(verifyDominanceOfContainedRegions(op)))
 
   domInfo = nullptr;
   return success();
 }
 
 LogicalResult OperationVerifier::verifyRegion(Region &region) {
   if (region.empty())
     return success();
LogicalResult OperationVerifier::verifyOperation(Operation &op) {
   }
 
   // If we can get operation info for this, check the custom hook.
   auto *opInfo = op.getAbstractOperation();
   if (opInfo && failed(opInfo->verifyInvariants(&op)))
     return failure();
 
   // Verify that all child regions are ok.
   for (auto &region : op.getRegions())
     if (failed(verifyRegion(region)))
       return failure();
 
   // If this is a registered operation, there is nothing left to do.
   if (opInfo)
     return success();
 
   // Otherwise, verify that the parent dialect allows un-registered operations.
   auto dialectPrefix = op.getName().getDialect();
 
   // Check for an existing answer for the operation dialect.
   auto it = dialectAllowsUnknownOps.find(dialectPrefix);
   if (it == dialectAllowsUnknownOps.end()) {
     // If the operation dialect is registered, query it directly.
     if (auto *dialect = ctx->getRegisteredDialect(dialectPrefix))
       it = dialectAllowsUnknownOps
                .try_emplace(dialectPrefix, dialect->allowsUnknownOperations())
                .first;
     // Otherwise, unregistered dialects (when allowed by the context)
     // conservatively allow unknown operations.
     else {
       if (!op.getContext()->allowsUnregisteredDialects() && !op.getDialect())
         return op.emitOpError()
if (!it->second) {
     return op.emitError("unregistered operation '")
            << op.getName() << "' found in dialect ('" << dialectPrefix
            << "') that does not allow unknown operations";
   }
 
   return success();
 }
 
-LogicalResult OperationVerifier::verifyDominance(Region &region) {
+LogicalResult OperationVerifier::verifyDominance(Region &region,
+                                                 bool hasDominance) {
   // Verify the dominance of each of the held operations.
-  for (auto &block : region)
-    // Dominance is only reachable 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 &block : region) {
+    // Dominance is only meaningful inside reachable blocks.
+    if (hasDominance && domInfo->isReachableFromEntry(&block))
       for (auto &op : block)
-        for (auto &region : op.getRegions())
-          if (failed(verifyDominance(region)))
-            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 &region : op.getRegions())
-    if (failed(verifyDominance(region)))
+    // 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();
+}
 
+/// Verify the dominance of each of the nested blocks within this
+/// operation.  Dominance is checked inside registered operations
+/// which don't have a RegionKindInterface, and those which do have a
+/// RegionKindInterface and report that they require dominance.  After
+/// ODS generates a RegionKindInterface, this should perhaps be
+/// simplified so that registered operation without a
+/// RegionKindInterface are not checked for dominance.
+LogicalResult
+OperationVerifier::verifyDominanceOfContainedRegions(Operation &op) {
+  auto kindInterface = dyn_cast<mlir::RegionKindInterface>(&op);
+  for (unsigned i = 0; i < op.getNumRegions(); i++) {
+    auto &region = op.getRegion(i);
+    bool hasDominance =
+        op.isRegistered() && (!kindInterface || kindInterface.hasDominance(i));
+    if (failed(verifyDominance(region, hasDominance)))
+      return failure();
+  }
   return success();
 }
 
 //===----------------------------------------------------------------------===//
 // Entrypoint
 //===----------------------------------------------------------------------===//
 
 /// Perform (potentially expensive) checks of invariants, used to detect
 /// compiler bugs.  On error, this reports the error through the MLIRContext and
 /// returns failure.
 LogicalResult mlir::verify(Operation *op) {
   return OperationVerifier(op->getContext()).verify(*op);
 }

mlir/test/IR/invalid.mlir

 // -----
 
 // expected-error @+1 {{expected non-function type}}
 func @negative_in_tensor_size() -> tensor<1x-1xi32>
 
 // -----
 
 func @invalid_nested_dominance() {
-  "foo.region"() ({
+  "test.has_dominance_scope"() ({
     // expected-error @+1 {{operand #0 does not dominate this use}}
     "foo.use" (%1) : (i32) -> ()
     br ^bb2
 
   ^bb2:
     // expected-note @+1 {{operand defined here}}
     %1 = constant 0 : i32
     "foo.yield" () : () -> ()

 // -----
 
 // expected-error @+1 {{attribute names with a '.' are reserved for dialect-defined names}}
 #foo.attr = i32
 
 // -----
 
 func @invalid_region_dominance() {
-  "foo.region"() ({
+  "test.has_dominance_scope"() ({
     // expected-error @+1 {{operand #0 does not dominate this use}}
     "foo.use" (%def) : (i32) -> ()
     "foo.yield" () : () -> ()
   }, {
     // expected-note @+1 {{operand defined here}}
     %def = "foo.def" () : () -> i32
   }) : () -> ()
   return
 }
 
 // -----
 
 func @invalid_region_dominance() {
   // expected-note @+1 {{operand defined here}}
-  %def = "foo.region_with_def"() ({
+  %def = "test.has_dominance_scope"() ({
     // expected-error @+1 {{operand #0 does not dominate this use}}
     "foo.use" (%def) : (i32) -> ()
     "foo.yield" () : () -> ()
   }) : () -> (i32)
   return
 }
 
 // -----

 }
 
 // -----
 
 func @dominance_error_in_unreachable_op() -> i1 {
   %c = constant false
   return %c : i1
 ^bb0:
-  "dummy" () ({  // unreachable
+  "test.has_dominance_scope" () ({ // unreachable
     ^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 %c : i1
 }
+

mlir/test/IR/parser.mlir

func @pretty_names() {
 
   // CHECK: return
   return
 }
 
 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
   // %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: }
+
+"unregistered_func"() ( {
+  %1 = "foo"(%2) : (i64) -> i64
+  %2 = "bar"(%1) : (i64) -> i64
+  "unregistered_terminator"() : () -> ()
+}) {sym_name = "unregistered_op_dominance_violation_ok", type = () -> i1} : () -> ()

mlir/test/IR/traits.mlir

 
 // -----
 
 func @succeededResultSizeAttr() {
   // CHECK: test.attr_sized_results
   %0:4 = "test.attr_sized_results"() {result_segment_sizes = dense<[0, 2, 1, 1]>: vector<4xi32>} : () -> (i32, i32, i32, i32)
   return
 }
+
+// -----
+
+func @succeededDominanceFreeScope() -> () {
+  test.dominance_free_scope {
+  // %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 @succeededCDFGInDominanceFreeScope() -> () {
+  test.dominance_free_scope {
+  // %1 is not dominated by its definition.
+    %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1) // CHECK: [[VAL2:%.*]]:3 = "bar"([[VAL3:%.*]]) : (i64) -> (i1, i1, i1)
+    br ^bb4                                // CHECK:   br ^bb2
+^bb2:                                      // CHECK: ^bb1:   // pred: ^bb1
+    br ^bb2                                // CHECK:   br ^bb1
+^bb4:                                      // CHECK: ^bb2:   // pred: ^bb0
+    %1 = "foo"() : ()->i64                 // CHECK: [[VAL3]] = "foo"() : () -> i64
+  }
+  return
+}                                          // CHECK: }
+
+// -----
+
+// Ensure that SSACFG regions of operations in GRAPH regions are
+// checked for dominance
+func @illegalInsideDominanceFreeScope() -> () {
+  test.dominance_free_scope {
+    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.dominance_free_scope {
+    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.dominance_free_scope {
+// expected-error @+1 {{use of undeclared SSA value name}}
+    %2:3 = "bar"(%1) : (i64) -> (i1,i1,i1)
+    "terminator"() : () -> ()
+  }
+  return
+}
+
+// -----
+
+func @blocks_in_dominance_free_scope_require_entry_block() {
+test.dominance_free_scope {
+// expected-error@-1 {{entry block of region may not have predecessors}}
+^bb42:
+  br ^bb43
+^bb43:
+  br ^bb42
+}
+}

mlir/test/lib/Dialect/Test/TestDialect.h

 
 #ifndef MLIR_TESTDIALECT_H
 #define MLIR_TESTDIALECT_H
 
 #include "mlir/Dialect/Traits.h"
 #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"
 #include "mlir/Interfaces/ControlFlowInterfaces.h"
 #include "mlir/Interfaces/DerivedAttributeOpInterface.h"
 #include "mlir/Interfaces/InferTypeOpInterface.h"
 #include "mlir/Interfaces/SideEffectInterfaces.h"
 

mlir/test/lib/Dialect/Test/TestDialect.cpp

 static void print(OpAsmPrinter &p, IsolatedRegionOp op) {
   p << "test.isolated_region ";
   p.printOperand(op.getOperand());
   p.shadowRegionArgs(op.region(), op.getOperand());
   p.printRegion(op.region(), /*printEntryBlockArgs=*/false);
 }
 
 //===----------------------------------------------------------------------===//
+// Test HasDominanceScopeOp
+//===----------------------------------------------------------------------===//
+
+RegionKind mlir::HasDominanceScopeOp::getRegionKind(unsigned index) {
+  return RegionKind::SSACFG;
+}
+
+//===----------------------------------------------------------------------===//
+// Test DominanceFreeScopeOp
+//===----------------------------------------------------------------------===//
+
+static ParseResult parseDominanceFreeScopeOp(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, DominanceFreeScopeOp op) {
+  p << "test.dominance_free_scope ";
+  p.printRegion(op.region(), /*printEntryBlockArgs=*/false);
+}
+
+RegionKind mlir::DominanceFreeScopeOp::getRegionKind(unsigned index) {
+  return RegionKind::GRAPH;
+}
+
+//===----------------------------------------------------------------------===//
 // Test AffineScopeOp
 //===----------------------------------------------------------------------===//
 
 static ParseResult parseAffineScopeOp(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=*/{});

mlir/test/lib/Dialect/Test/TestOps.td

 //===-- TestOps.td - Test dialect operation definitions ----*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef TEST_OPS
 #define TEST_OPS
 
 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"
 include "mlir/Interfaces/ControlFlowInterfaces.td"
 include "mlir/Interfaces/InferTypeOpInterface.td"
 include "mlir/Interfaces/SideEffectInterfaces.td"
 
 def Test_Dialect : Dialect {
def IsolatedRegionOp : TEST_Op<"isolated_region", [IsolatedFromAbove]> {
   }];
 
   let arguments = (ins Index);
   let regions = (region SizedRegion<1>:$region);
   let parser = [{ return ::parse$cppClass(parser, result); }];
   let printer = [{ return ::print(p, *this); }];
 }
 
+def HasDominanceScopeOp : TEST_Op<"has_dominance_scope",  [
+    DeclareOpInterfaceMethods<RegionKindInterface>]> {
+  let summary =  "has dominance scope operation";
+  let description = [{
+    Test op that defines a new scope with dominance scope.
+  }];
+
+  let regions = (region VariadicRegion<AnyRegion>:$regions);
+  let results = (outs Variadic<AnyType>);
+}
+
+def DominanceFreeScopeOp : TEST_Op<"dominance_free_scope",  [
+    DeclareOpInterfaceMethods<RegionKindInterface>]> {
+  let summary =  "dominance-free scope operation";
+  let description = [{
+    Test op that defines a new dominance-free scope.
+  }];
+
+  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 = [{
     Test op that defines a new affine scope.
   }];
 
   let regions = (region SizedRegion<1>:$region);
   let parser = [{ return ::parse$cppClass(parser, result); }];