[MLIR] Introduce join/meet type interface.

[arames]

Summary

Introduce ::mlir::join(Type, Type) and ::mlir::meet(Type, Type), for the
partial order "less specialized than or equal".
Types can participate by implementing the JoinMeetTypeInterface. Today,
tensor types and memref types participate.

[silvas]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

30

Many folks using MLIR are not familiar with lattice theory / dataflow formalism). So maybe just for clarity say something like "in other words, the top of the lattice represents "any possible type" and the bottom is "no possible type"". And also maybe say "if types are viewed as sets of values, this function is equivalent to the union of such sets."

(and make corresponding comments on "meet".

61

I think you have this reversed. Should be ty1 <= m.

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.td

32

"If null" -> "if the contained Type is null" for clarity

33

the meaning of "result of the join is null" here is somewhat unclear (I get what it says, just worried that others might not). Maybe "trivial" is a better word than null?

49

Maybe add "for context about join/meet operations on lattices, see: https://en.wikipedia.org/wiki/Lattice_(order) "

mlir/lib/IR/BuiltinTypes.cpp

440

use static for functions: https://llvm.org/docs/CodingStandards.html#anonymous-namespaces

445

maybe return None to be clear this is creating a None optional ({} might initialize a null Type as well, so it's less clear when reading).

459

::mlir::join/meet already check these two cases, so we should omit them here. (it messes up your dyn_cast_or_null trick in the code that calls this, but switching that to an if (!other.isa<TensorType>()) return None seems worth it to remove these lines -- keep in mind that many folks will probably look at/copy this code with less context, and so we don't want them to see these redundant checks and copy that)

mlir/lib/Interfaces/JoinMeetTypeInterface.cpp

30

add message "commutativity violated" or someting like that.

[silvas]

mlir/test/Interfaces/JoinMeetTypeInterface/TestJoinMeetTypeInterface.cpp

71

mem8 is too terse. memspace8?

[silvas]

mlir/lib/IR/BuiltinTypes.cpp

454

For RankedTensorType, you also need to check the "encoding"

[rriddle]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

54

Can you rename these to something specific to types? meet is a very general name that I wouldn't want polluting the mlir namespace. (Same with join)

mlir/test/Interfaces/JoinMeetTypeInterface/TestJoinMeetTypeInterface.cpp

23

This file is a bit of an awkward thing to look at. Can you just write a simple pass that checks for a unregistered op with two types and tries to join or meet them? You can then have actual IR instead of parsing it yourself on the fly and using macros (which has a bad code smell to it).

Also, if you were to keep this kind of test it would make more sense as a unit test than a lit test IMO.

[vinograd47]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

30

≤ is non-ANSI character. AFAIK, they might cause issues with some compilers.

[arames]

Thanks for the review.

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

54

Renamed to joinTypes and meetTypes.

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.td

33

Since I already say "the contained type is null", I changed to say

[...], and someType and otherType do not join; that is, there is no type that is both less specialized than someType and less specialized than otherType.

mlir/lib/IR/BuiltinTypes.cpp

454

I missed that this was available on RankedTensorType.
Since it is not on UnrankedTensorType, I assume we can safely join tensor<*xf32> and tensor<2xf32, #any_encoding>, correct ?

mlir/test/Interfaces/JoinMeetTypeInterface/TestJoinMeetTypeInterface.cpp

23

Moved to a pass as you suggested.

71

Not applicable now that this file was removed in favor of an MLIR filecheck test.

[silvas]

mlir/lib/IR/BuiltinTypes.cpp

454

If there is a non-null encoding then joining with UnrankedTensorType should return null (the "encoding" is considered load-bearing for correctness and must be preserved).

[silvas]

btw, I think you might need to reupload the patch. I don't see the new code.

[arames]

In D101859#2740494, @silvas wrote:

btw, I think you might need to reupload the patch. I don't see the new code.

Double-checking before uploading, sorry about that. I realize it's probably better to publish comments only after uploading the update in phabricator.

[arames]

mlir/lib/IR/BuiltinTypes.cpp

454

Conversely, I suppose meetTypes(tensor<*xi32>, tensor<?xi32, #some_map>) should return tensor<?xi32, #some_map> then.

This leads to some funny asymmetry.

join(tensor<1xi32, #encoding1>, tensor<2x2xi32>) == tensor<*xi32>
join(tensor<1xi32, #encoding1>, tensor<2x2xi32, #encoding1>) == <null> != tensor<*xi32, #encoding1>

[arames]

mlir/lib/IR/BuiltinTypes.cpp

454

Or maybe this is simply not possible due to how encoding works. Looking into it.

[silvas]

mlir/lib/IR/BuiltinTypes.cpp

454

It should be: join(tensor<1xi32, #encoding1>, tensor<2x2xi32>) == null

You can consider the lattice as a product lattice of tuples (TensorType's ignoring encoding, encoding), where encoding for the moment is a constant lattice (either top, bottom, or a single element set).

That is, unless two types have the same non-null encoding, their join/meet is null. (a null encoding is its own distinct encoding, not "any encoding")

[mehdi_amini]

mlir/lib/IR/BuiltinTypes.cpp

454

Having a shape-centric interface be bothered by encodings seems like a red flag to me.

It seems to me that this indicates that working with "Type" isn't the right level of abstraction and the API should work with a "shape" object instead.

[silvas]

mlir/lib/IR/BuiltinTypes.cpp

454

There's nothing shape-centric about this interface.

[arames]

mlir/lib/IR/BuiltinTypes.cpp

454

Maybe we need to talk about this more then.

I think the premise that this is a shape-centric interface only holds for what we have with builtin types.

With custom types, this is not limited to shapes. For example, it would be useful for dialects that want to do type inference with some kind of custom !any_type element type. (It makes me think we probably want to join or meet the element types instead of having a comparison.)

My feeling was the logic will be useful or needed in various places. For example in type inference, or to update the control-flow interfaces be more flexible.

[mehdi_amini]

mlir/lib/IR/BuiltinTypes.cpp

454

There's nothing shape-centric about this interface.

Fair enough: you could imagine this as a type-lattice interface only. But then I'll object that it won't be useful for modeling a shape inference lattice: it would mix on the same lattice properties of the type that looks orthogonal to each other as I see it.

[arames]

Address review comments.

[arames]

mlir/lib/IR/BuiltinTypes.cpp

441

We may want to do

Type elementTy = joinTypes(ty1.getElementType(), ty2.getElementType());
if (!elementTy)
  return Type();

here and in other places.

[silvas]

mlir/lib/IR/BuiltinTypes.cpp

454

I'm pretty happy with the current design. I view this as a type lattice only, e.g. using it to model that NoneType is a subtype of Optional[T] in Python is what I want to use it for (or refine AnyType to a more specific type).

Indeed, it is not the most useful lattice for shape inference, but that's fine! We can have separate lattice structures for that.

[silvas]

mlir/lib/IR/BuiltinTypes.cpp

441

I don't think we define whether tensor is covariant/contravariant/invariant in the element type (I'm referring to the definitions here, which I think are pretty common in type theory: https://www.python.org/dev/peps/pep-0483/#covariance-and-contravariance). For example, if I have a tensor<optional<T>> is tensor<None> a valid subtype? I don't think we want to guarantee that (it would have implications for bufferization that I would have to think through more fully, for example), so making tensor invariant on the element type would be best for now I think.

[arames]

For reference, related discussion at https://llvm.discourse.group/t/rfc-join-meet-type-interface/3416.

[jpienaar]

mlir/include/mlir/IR/TypeUtilities.h

70

This is the inverse of Shape_JoinOp (and joinShapes was defined as), we went for least generalized there. Lets keep these consistent.

80

Without seeing the use, it is unclear whether populating or returning a SmallVector is most useful.

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

48

What happens with element type mismatches? Also does this extend to dialects with element types with subtypes?

76

i8?

81

Why is this not tensor<*xf32> ?

mlir/lib/IR/BuiltinTypes.cpp

454

I think this is very good question on encoding. E.g., is no encoding less constrained than tensor with encoding. If so, then join/meet with encoding or without has an answer.

[silvas]

mlir/include/mlir/IR/TypeUtilities.h

70

But DataFlowAnalysis.h has the opposite convention (that's why I liked this one), and seems more centrally positioned.

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

48

See below about my notes on tensor being covariant/contravariant/invariant on the element type. I think it makes sense to be invariant.

In the case of element type mismatches the result is null because the native tensor type has no intrinsic way to represent "any dtype is ok".

mlir/lib/IR/BuiltinTypes.cpp

454

As I described above, I think that "no encoding" is itself an encoding distinct from any explicitly specified encoding.

[silvas]

mlir/include/mlir/IR/TypeUtilities.h

70

I agree we should keep it consistent. We should either rename the functions in DataFlowAnalysis.h or Shape_JoinOp.

[arames]

mlir/include/mlir/IR/TypeUtilities.h

70

Although I am accustomed to the naming in this patch, it seems to me changing the internals is easier than changing the op.

80

At this point it is of course only used in this patch.
I would think passing the SmallVectorImpl is more efficient, but I the return-by-value version easier to use.

Do you prefer

LogicalResult joinShapes(ArrayRef<int64_t> shape1, ArrayRef<int64_t> shape2, SmallVectorImpl<int64_t> &join);

?

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

81

tensor<*xf32> is less specialized than both tensor<4x5xf32> and tensor<6xf32>.
The join (with the current conventions) would yield tensor<*xf32>.

[arames]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

48

Couldn't some dialects have a way to represent it though ?
This relates to https://llvm.discourse.group/t/rfc-tensors-with-unknown-element-types/1039.

[arames]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

48

(Reading your other comments about this.)

[silvas]

mlir/include/mlir/IR/TypeUtilities.h

80

I think returning by value is fine here. NRVO should do a great job of optimizing this I think: https://www.fluentcpp.com/2016/11/28/return-value-optimizations/

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

48

I've changed my mind about this since writing that (thanks Chris Lattner for pushing back on it!). I have been working in npcomp using tensor<...x!numpy.any_dtype> and it is a big pain to use, and I don't feel it is worth standardizing. I will be defining my own !torch.tensor type to deal with it (plus there are other considerations like mutability there which I can roll in), and then I can properly define my join/meet functions there.

My experience is that tensor type is mostly useful for ranked tensors of known element type. The unranked version happens to be useful for modeling certain concepts in TensorFlow (which always knows the element type due to how GraphDef work, which is a happy coincidence), but in my experience has very limited utility there, and even less utility in situations where the element type might be unknown, such as numpy/torch/etc. which generally have other considerations, such as mutabilty.

Or let me say it like this. I'm not aware of any situation where an immutable tensor of "unknown element type" that is modeled with a special "!any_element_type" element type feels like the right design. It's more of a "happens to work" design point, which is below the bar for MLIR core.

81

Can you update the code?

81

s/code/comment/

[mehdi_amini]

mlir/include/mlir/IR/TypeUtilities.h

80

The only advantage of the output parameter is the pattern where you can reuse the same container over and over on the caller side to avoid reallocating memory.
(I'm not saying it'll have an impact here)

[arames]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

81

???

I was trying to say the current example is fine.
With the current naming conventions,

join(tensor<4x5xf32>, tensor<6xf32>) == tensor<*xf32>
meet(tensor<4x5xf32>, tensor<6xf32>) == Type()

[arames]

mlir/include/mlir/IR/TypeUtilities.h

70

I have not looked much yet at DataFlowAnalysis files. Isn't "join" term used generically to indicate the combination of the states ? The actual implementation of it depends on what the analysis does. It would be "nice" if it matches the "join" used for join/meet type interface, but it does not have to, does it ?
In that case I could only update this patch to match the shape ops.

I don't feel I am in a position to make the decision here.

@silvas @jpienaar

[silvas]

mlir/include/mlir/IR/TypeUtilities.h

70

It doesn't have a super strict dataflow formalism, but it implements a pessimistic* sparse dataflow analysis where getPessimisticValueState is "top" and "join" is least-upper-bound.

*note: it has a hardcoded optimistic treatment of backedges proven unreachable.

I think that both renamings should be easy. For shape.join it's literally just sed'ing shape.join to shape.meet. For DataFlowAnalysis it is renaming that join method.

From a quick survey, my favorite dataflow analysis reference sources both use "top of the lattice is the full set, bottom of the lattice is the empty set" behavior, which corresponds to your current join/meet conventions, so I prefer that, since those are the resources that I tend to point newbies at.

https://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec02-Dataflow.pdf
https://cs.au.dk/~amoeller/spa/3-lattices-and-fixpoints.pdf

[arames]

Rebase on parent patches.

[rriddle]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.td

55–56

mlir/lib/IR/BuiltinTypes.cpp

466–467

Doesn't this ignore the encoding aspect?

mlir/lib/IR/TypeUtilities.cpp

161–163

178–180

mlir/lib/Interfaces/JoinMeetTypeInterface.cpp

20–21

Can we just assert this? (Although, I'd honestly just not check this at all)

27–29

Can we avoid computing the second join in opt builds if we can (i.e. if the first join succeeded, only compute the second inside of the assert)? (You could also realistically compare the TypeIDs of the two types and avoid the second join altogether).

40–41

Same here.

43–53

Same here.

[arames]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

81

Why is this (tensor<1xi32> ^ i32) not tensor<*xf32> ?

I don't think we want scalar and tensor types to join/meet on the type lattice.
Why would i32 be more specialized than tensor<i32>, and not the opposite ?

We would not expect an op accepting tensors only could not take an i32 where a tensor<*xi32> is expected.

mlir/lib/IR/BuiltinTypes.cpp

454

Yes. Now fixed.

466–467

Doesn't this ignore the encoding aspect?

Absolutely. I had not addressed the earlier comments yet.
This is not fixed, with the associated test

"meet"(%tensor_1xi32_encoding1, %tensor_unranked_i32) : (tensor<1xi32, #encoding1>, tensor<*xi32>) -> i1
// expected-error@-1 {{types do not meet}}

mlir/lib/Interfaces/JoinMeetTypeInterface.cpp

20–21

Do you mean assert(ty1 && ty2) ?

I think we explicitly want to allow null input types, because it allows trivially chaining calls to joinTypes and meetTypes without having to check for null. It

27–29

I like the idea.
Changing to do that. Others can comment if they disagree.

[arames]

Address review comments:

• Fix join/meet for tensors with encodings
• misc style fixes

[arames]

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

81

This should have been:
We would not expect an op accepting tensors only could take an i32 where a tensor<*xi32> is expected.

[arames]

Rebase on top of tree.

[arames]

Fix clang-format warning.

[arames]

Rebase on top of tree.

mlir/include/mlir/IR/BuiltinTypes.h

 //===- BuiltinTypes.h - MLIR Builtin Type Classes ---------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef MLIR_IR_BUILTINTYPES_H
 #define MLIR_IR_BUILTINTYPES_H
 
 #include "mlir/IR/Attributes.h"
 #include "mlir/IR/Types.h"
+#include "mlir/Interfaces/JoinMeetTypeInterface.h"
 
 namespace llvm {
 struct fltSemantics;
 } // namespace llvm
 
 namespace mlir {
 class AffineExpr;
 class AffineMap;

mlir/include/mlir/IR/BuiltinTypes.td

 // validity of and defining the IR.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef BUILTIN_TYPES
 #define BUILTIN_TYPES
 
 include "mlir/IR/BuiltinDialect.td"
+include "mlir/Interfaces/JoinMeetTypeInterface.td"
 
 // TODO: Currently the types defined in this file are prefixed with `Builtin_`.
 // This is to differentiate the types here with the ones in OpBase.td. We should
 // remove the definitions in OpBase.td, and repoint users to this file instead.
 
 // Base class for Builtin dialect types.
-class Builtin_Type<string name, string baseCppClass = "::mlir::Type">
-    : TypeDef<Builtin_Dialect, name, [], baseCppClass> {
+class Builtin_Type<string name,
+                   string baseCppClass = "::mlir::Type",
+                   list<Trait> traits = []>
+    : TypeDef<Builtin_Dialect, name, traits, baseCppClass> {
   let mnemonic = ?;
 }
 
 //===----------------------------------------------------------------------===//
 // ComplexType
 //===----------------------------------------------------------------------===//
 
 def Builtin_Complex : Builtin_Type<"Complex"> {
let extraClassDeclaration = [{
     static constexpr unsigned kMaxWidth = (1 << 24) - 1;
   }];
 }
 
 //===----------------------------------------------------------------------===//
 // MemRefType
 //===----------------------------------------------------------------------===//
 
-def Builtin_MemRef : Builtin_Type<"MemRef", "BaseMemRefType"> {
+def Builtin_MemRef
+    : Builtin_Type<"MemRef", "BaseMemRefType",
+                   [DeclareTypeInterfaceMethods<JoinMeetTypeInterface>]> {
   let summary = "Shaped reference to a region of memory";
   let description = [{
     Syntax:
 
     ```
     memref-type ::= `memref` `<` dimension-list-ranked type
                     (`,` layout-specification)? (`,` memory-space)? `>`
 
def Builtin_Opaque : Builtin_Type<"Opaque"> {
   let skipDefaultBuilders = 1;
   let genVerifyDecl = 1;
 }
 
 //===----------------------------------------------------------------------===//
 // RankedTensorType
 //===----------------------------------------------------------------------===//
 
-def Builtin_RankedTensor : Builtin_Type<"RankedTensor", "TensorType"> {
+def Builtin_RankedTensor
+    : Builtin_Type<"RankedTensor", "TensorType",
+                   [DeclareTypeInterfaceMethods<JoinMeetTypeInterface>]> {
   let summary = "Multi-dimensional array with a fixed number of dimensions";
   let description = [{
     Syntax:
 
     ```
     tensor-type ::= `tensor` `<` dimension-list type (`,` encoding)? `>`
     dimension-list ::= (dimension `x`)*
     dimension ::= `?` | decimal-literal
let extraClassDeclaration = [{
     }
   }];
 }
 
 //===----------------------------------------------------------------------===//
 // UnrankedMemRefType
 //===----------------------------------------------------------------------===//
 
-def Builtin_UnrankedMemRef : Builtin_Type<"UnrankedMemRef", "BaseMemRefType"> {
+def Builtin_UnrankedMemRef
+    : Builtin_Type<"UnrankedMemRef", "BaseMemRefType",
+                   [DeclareTypeInterfaceMethods<JoinMeetTypeInterface>]> {
   let summary = "Shaped reference, with unknown rank, to a region of memory";
   let description = [{
     Syntax:
 
     ```
     unranked-memref-type ::= `memref` `<*x` type (`,` memory-space)? `>`
     memory-space ::= attribute-value
     ```
def Builtin_UnrankedMemRef
   let skipDefaultBuilders = 1;
   let genVerifyDecl = 1;
 }
 
 //===----------------------------------------------------------------------===//
 // UnrankedTensorType
 //===----------------------------------------------------------------------===//
 
-def Builtin_UnrankedTensor : Builtin_Type<"UnrankedTensor", "TensorType"> {
+def Builtin_UnrankedTensor
+    : Builtin_Type<"UnrankedTensor", "TensorType",
+                   [DeclareTypeInterfaceMethods<JoinMeetTypeInterface>]> {
   let summary = "Multi-dimensional array with unknown dimensions";
   let description = [{
     Syntax:
 
     ```
     tensor-type ::= `tensor` `<` `*` `x` type `>`
     ```
 

mlir/include/mlir/IR/TypeUtilities.h

 
 /// Returns success if all given types have compatible shapes. That is, they are
 /// all scalars (not shaped), or they are all shaped types and any ranked shapes
 /// have compatible dimensions. The element type does not matter.
 LogicalResult verifyCompatibleShapes(TypeRange types);
 
 /// Dimensions are compatible if all non-dynamic dims are equal.
 LogicalResult verifyCompatibleDims(ArrayRef<int64_t> dims);
+
+/// The element-wise `join` function for shapes, and the partial order "less
+/// specialized than or equal". It returns an error if the shapes have different
+/// sizes.
+/// The `join` relationship for two dimensions is:
+///     dim1    | dim2    | join
+///     n       | n       | n
+///     n       | k       | dynamic
+///     dynamic | k       | dynamic
+///     n       | dynamic | dynamic
+FailureOr<SmallVector<int64_t, 4>>
+joinShapes(ArrayRef<int64_t> shape1, ArrayRef<int64_t> shape2,
+           Optional<Location> location = None);
+
+/// The element-wise `meet` function for shapes, and the partial order "less
+/// specialized than or equal". It returns an error if the shapes have different
+/// sizes or do not meet.
+/// The `meet` relationship for two dimensions is:
+///     dim1     | dim2    | meet
+///     n        | n       | n
+///     n        | k       | error
+///     dynamic  | k       | k
+///     n        | dynamic | n
+FailureOr<SmallVector<int64_t, 4>> meetShapes(ArrayRef<int64_t> shape1,
+                                              ArrayRef<int64_t> shape2,
+                                              Optional<Location> = None);
+
 //===----------------------------------------------------------------------===//
 // Utility Iterators
 //===----------------------------------------------------------------------===//
 
 // An iterator for the element types of an op's operands of shaped types.
 class OperandElementTypeIterator final
     : public llvm::mapped_iterator<Operation::operand_iterator,
                                    Type (*)(Value)> {

mlir/include/mlir/Interfaces/CMakeLists.txt

add_mlir_doc(DataLayoutInterfaces
   DataLayoutTypeInterface
   Interfaces/
   -gen-type-interface-docs)
 
 add_mlir_doc(DataLayoutInterfaces
   DataLayoutOpInterface
   Interfaces/
   -gen-op-interface-docs)
+
+set(LLVM_TARGET_DEFINITIONS JoinMeetTypeInterface.td)
+mlir_tablegen(JoinMeetTypeInterface.h.inc -gen-type-interface-decls)
+mlir_tablegen(JoinMeetTypeInterface.cpp.inc -gen-type-interface-defs)
+add_public_tablegen_target(MLIRJoinMeetTypeInterfaceIncGen)
+add_dependencies(mlir-generic-headers MLIRJoinMeetTypeInterfaceIncGen)
+
+add_mlir_doc(JoinMeetTypeInterface
+  JoinMeetTypeInterface
+  Interfaces/
+  -gen-type-interface-docs)
+

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.h

+//===- JoinMeetTypeInterface.h - Join/Meet Type Interface Decls -*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the interface for type join and meet relationships.
+// Types can inherit and implement the `JoinMeetTypeInterface::Trait` trait to
+// participate in `join` and `meet` functions.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_INTERFACES_JOINMEETTYPEINTERFACE_H
+#define MLIR_INTERFACES_JOINMEETTYPEINTERFACE_H
+
+#include "mlir/IR/Location.h"
+#include "mlir/IR/Types.h"
+
+#include "mlir/Interfaces/JoinMeetTypeInterface.h.inc"
+
+namespace mlir {
+
+//===----------------------------------------------------------------------===//
+// Join and Meet Types
+//===----------------------------------------------------------------------===//
+
+/// The join function for types, and the partial order "less specialized than or
+/// equal", noted `≤`.
+/// It returns the most specialized type that is less specialized than both
+/// `ty1` and `ty2`, if it exists, and `Type()` otherwise.
+/// The join `j` of `ty1` and `ty2` is such that:
+/// * j ≤ ty1, and j ≤ ty2
+/// * For any type t such that t ≤ ty1 and t ≤ ty2, t ≤ j.
+/// For example:
+///  ty1               | ty2               | ty1 v ty2
+///  ------------------+-------------------+-------------------
+///  i8                | i8                | i8
+///  i8                | i32               | <none> (null type)
+///  tensor<1xf32>     | tensor<?xf32>     | tensor<?xf32>
+///  tensor<1x2x?xf32> | tensor<1x?x3xf32> | tensor<1x?x?xf32>
+///  tensor<4x5xf32>   | tensor<6xf32>     | tensor<*xf32>
+///  tensor<1xi32>     | i32               | <none> (null type)
+///  tensor<1xi32>     | tensor<i32>       | tensor<*xi32>
+///
+/// The function is monotonic:
+///   * idempotence:   join(x,x) == x
+///   * commutativity: join(x,y) == join(y,x)
+///   * associativity: join(x,join(y,z)) == join(join(x,y),z)
+///
+/// Types can participate in this function by implementing
+/// `JoinMeetTypeInterface`.
+Type join(Type ty1, Type ty2);
+
+/// The meet function for types, and the partial order "less specialized than or
+/// equal", noted `≤`.
+/// It returns the least specialized type, that is more specialized than both
+/// `ty1` and `ty2`, if it exists, and `Type()` otherwise.
+/// The meet `m` of `ty1` and `ty2` is such that:
+/// * m ≤ ty1, and m ≤ ty2
+/// * For any type t such that t ≤ ty1 and t ≤ ty2, t ≤ m.
+/// For example:
+///  i8                | i8                | i8
+///  ------------------+-------------------+-------------------
+///  i8                | i32               | <none> (null type)
+///  tensor<1xf32>     | tensor<?xf32>     | tensor<1xf32>
+///  tensor<1x2x?xf32> | tensor<1x?x3xf32> | tensor<1x2x3xf32>
+///  tensor<4x5xf32>   | tensor<6xf32>     | <none> (null type)
+///  tensor<1xi32>     | i32               | <none> (null type)
+///  tensor<1xi32>     | tensor<i32>       | <none> (null type)
+///
+/// The function is monotonic:
+///   * idempotence:   join(x,x) == x
+///   * commutativity: join(x,y) == join(y,x)
+///   * associativity: join(x,join(y,z)) == join(join(x,y),z)
+///
+/// Types can participate in this function by implementing
+/// `JoinMeetTypeInterface`.
+Type meet(Type ty1, Type ty2);
+
+/// Indicates whether `ty1` is compatible with `ty2`, and less specialized than
+/// `ty2`.
+inline bool isLessSpecialized(Type ty1, Type ty2) {
+  return join(ty1, ty2) == ty2;
+}
+
+/// Indicates whether `ty1` is compatible with `ty2`, and more specialized than
+/// `ty2`.
+inline bool isMoreSpecialized(Type ty1, Type ty2) {
+  return meet(ty1, ty2) == ty1;
+}
+
+} // namespace mlir
+
+#endif // MLIR_INTERFACES_JOINMEETTYPEINTERFACE_H

mlir/include/mlir/Interfaces/JoinMeetTypeInterface.td

+//===- JoinMeetTypeInterface.td - Join/Meet Type Interface ----*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// Defines the interface for join and meet type relathionships.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef MLIR_JOINMEETTYPEINTERFACE
+#define MLIR_JOINMEETTYPEINTERFACE
+
+include "mlir/IR/OpBase.td"
+
+def JoinMeetTypeInterface : TypeInterface<"JoinMeetTypeInterface"> {
+  let cppNamespace = "::mlir";
+
+  let description = [{
+    Interface for types participating in the `join` and `meet` relationships.
+
+    Types willing to participate in the `::mlir::join(Type, Type)` and
+    `::mlir::meet(Type, Type)` functions should implement this interface by
+    providing implementations of `join` and `meet` functions handling types they
+    can join or meet with.
+
+    The return value of the interface method `someType.join(otherType)` is
+    interpreted as follows:
+    - A result with a value (`Optional<Type>::hasValue()` is true) represents
+      the result of the `join`. If null, it indicates `otherType` was handled,
+      and the result of the `join` is null.
+    - A result without a value (`Optional<Type>::hasValue()` is false) indicates
+      `sometype` does not know (or ignores) the `other` type.
+
+    Returning an `Optional<Type>` with no value allows for extensibility of
+    types. `Type1::join` may handle `Type2` while `Type2::join` ignores `Type1`
+    or simply does not implement this interface.
+
+    The interface `join` method must participate to guarantee the monotonicity
+    of `::mlir::join`. It must be idempotent (`join(x, x) = x`). Associativity,
+    though it should flow naturally, must be maintained. Commutativity is
+    guaranteed by `::mlir::join` itself, as it queries both
+    `sometype.join(othertype)` and `othertype.join(sometype)`. One type may
+    ignore the other; in that case the result with a value is used. If both
+    results have a value, they must match.
+
+    The same comments apply to `meet`.
+  }];
+
+  let methods = [
+    InterfaceMethod<
+      /*description=*/"Return the join with the `other` type.",
+      /*retTy=*/"Optional<Type>",
+      /*methodName=*/"join",
+      /*args=*/(ins "Type":$other)
+    >,
+    InterfaceMethod<
+      /*description=*/"Return the meet with the `other` type.",
+      /*retTy=*/"Optional<Type>",
+      /*methodName=*/"meet",
+      /*args=*/(ins "Type":$other)
+    >,
+  ];
+}
+
+#endif // MLIR_JOINMEETTYPEINTERFACE

mlir/lib/Dialect/Tensor/IR/CMakeLists.txt

 add_mlir_dialect_library(MLIRTensor
   TensorDialect.cpp
   TensorOps.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${PROJECT_SOURCE_DIR}/include/mlir/Dialect/Tensor
 
   DEPENDS
   MLIRTensorOpsIncGen
 
   LINK_COMPONENTS
   Core
 
   LINK_LIBS PUBLIC
   MLIRCastInterfaces
   MLIRIR
+  MLIRJoinMeetTypeInterface
   MLIRSideEffectInterfaces
   MLIRSupport
   )

mlir/lib/Dialect/Tensor/IR/TensorOps.cpp

if (!aT || !bT)
     return false;
 
   if (aT.getElementType() != bT.getElementType())
     return false;
 
   return succeeded(verifyCompatibleShape(aT, bT));
 }
 
-/// Compute a TensorType that has the joined shape knowledge of the two
-/// given TensorTypes. The element types need to match.
-static TensorType joinShapes(TensorType one, TensorType two) {
-  assert(one.getElementType() == two.getElementType());
-
-  if (!one.hasRank())
-    return two;
-  if (!two.hasRank())
-    return one;
-
-  int64_t rank = one.getRank();
-  if (rank != two.getRank())
-    return {};
-
-  SmallVector<int64_t, 4> join;
-  join.reserve(rank);
-  for (int64_t i = 0; i < rank; ++i) {
-    if (one.isDynamicDim(i)) {
-      join.push_back(two.getDimSize(i));
-      continue;
-    }
-    if (two.isDynamicDim(i)) {
-      join.push_back(one.getDimSize(i));
-      continue;
-    }
-    if (one.getDimSize(i) != two.getDimSize(i))
-      return {};
-    join.push_back(one.getDimSize(i));
-  }
-  return RankedTensorType::get(join, one.getElementType());
-}
-
 namespace {
 
 /// Replaces chains of two tensor.cast operations by a single tensor.cast
 /// operation if doing so does not remove runtime constraints.
 struct ChainedTensorCast : public OpRewritePattern<CastOp> {
   using OpRewritePattern<CastOp>::OpRewritePattern;
 
   LogicalResult matchAndRewrite(CastOp tensorCast,
                                 PatternRewriter &rewriter) const final {
     auto tensorCastOperand = tensorCast.getOperand().getDefiningOp<CastOp>();
 
     if (!tensorCastOperand)
       return failure();
 
     auto sourceType =
         tensorCastOperand.getOperand().getType().cast<TensorType>();
     auto intermediateType = tensorCastOperand.getType().cast<TensorType>();
     auto resultType = tensorCast.getType().cast<TensorType>();
 
-    // We can remove the intermediate cast if joining all three produces the
-    // same result as just joining the source and result shapes.
-    auto firstJoin =
-        joinShapes(joinShapes(sourceType, intermediateType), resultType);
+    // We can remove the intermediate cast if meeting all three produces the
+    // same result as just meeting the source and result shapes.
+    auto firstMeet = meet(meet(sourceType, intermediateType), resultType);
 
-    // The join might not exist if the cast sequence would fail at runtime.
-    if (!firstJoin)
+    // The meet might not exist if the cast sequence would fail at runtime.
+    if (!firstMeet)
       return failure();
 
-    // The newJoin always exists if the above join exists, it might just contain
+    // The newMeet always exists if the above meet exists, it might just contain
     // less information. If so, we cannot drop the intermediate cast, as doing
     // so would remove runtime checks.
-    auto newJoin = joinShapes(sourceType, resultType);
-    if (firstJoin != newJoin)
+    auto newMeet = meet(sourceType, resultType);
+    if (firstMeet != newMeet)
       return failure();
 
     rewriter.replaceOpWithNewOp<CastOp>(tensorCast, resultType,
                                         tensorCastOperand.getOperand());
     return success();
   }
 };
 

mlir/lib/IR/BuiltinTypes.cpp

 #include "TypeDetail.h"
 #include "mlir/IR/AffineExpr.h"
 #include "mlir/IR/AffineMap.h"
 #include "mlir/IR/BuiltinAttributes.h"
 #include "mlir/IR/BuiltinDialect.h"
 #include "mlir/IR/Diagnostics.h"
 #include "mlir/IR/Dialect.h"
 #include "mlir/IR/TensorEncoding.h"
+#include "mlir/IR/TypeUtilities.h"
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/TypeSwitch.h"
 
 using namespace mlir;
 using namespace mlir::detail;
bool TensorType::isValidElementType(Type type) {
   // Note: Non standard/builtin types are allowed to exist within tensor
   // types. Dialects are expected to verify that tensor types have a valid
   // element type within that dialect.
   return type.isa<ComplexType, FloatType, IntegerType, OpaqueType, VectorType,
                   IndexType>() ||
          !type.getDialect().getNamespace().empty();
 }
 
+namespace {
+Optional<Type> join(TensorType ty1, TensorType ty2) {
+  if (ty1 == ty2)
+    return ty1;
+  if (!ty1 || !ty2)
+    return {};
+
+  Type elementTy = ty1.getElementType();
+  if (ty2.getElementType() != elementTy)
+    return Type();
+
+  if (!ty1.hasRank() || !ty2.hasRank() || ty1.getRank() != ty2.getRank())
+    return UnrankedTensorType::get(elementTy);
+
+  auto shape = joinShapes(ty1.getShape(), ty2.getShape()).getValue();
+  return RankedTensorType::get(shape, elementTy);
+}
+
+Optional<Type> meet(TensorType ty1, TensorType ty2) {
+  if (ty1 == ty2)
+    return ty1;
+  if (!ty1 || !ty2)
+    return {};
+
+  Type elementTy = ty1.getElementType();
+  if (ty2.getElementType() != elementTy)
+    return Type();
+
+  if (!ty1.hasRank() || !ty2.hasRank())
+    return ty1.hasRank() ? ty1 : ty2;
+
+  if (ty1.getRank() != ty2.getRank())
+    return Type();
+
+  auto shape = meetShapes(ty1.getShape(), ty2.getShape());
+  if (succeeded(shape))
+    return RankedTensorType::get(shape.getValue(), elementTy);
+  return Type();
+}
+} // namespace
+
 //===----------------------------------------------------------------------===//
 // RankedTensorType
 //===----------------------------------------------------------------------===//
 
 LogicalResult
 RankedTensorType::verify(function_ref<InFlightDiagnostic()> emitError,
                          ArrayRef<int64_t> shape, Type elementType,
                          Attribute encoding) {
   for (int64_t s : shape)
     if (s < -1)
       return emitError() << "invalid tensor dimension size";
   if (auto v = encoding.dyn_cast_or_null<VerifiableTensorEncoding>())
     if (failed(v.verifyEncoding(shape, elementType, emitError)))
       return failure();
   return checkTensorElementType(emitError, elementType);
 }
 
+Optional<Type> RankedTensorType::join(Type other) const {
+  return ::join(*this, other.dyn_cast_or_null<TensorType>());
+}
+
+Optional<Type> RankedTensorType::meet(Type other) const {
+  return ::meet(*this, other.dyn_cast_or_null<TensorType>());
+}
+
 //===----------------------------------------------------------------------===//
 // UnrankedTensorType
 //===----------------------------------------------------------------------===//
 
 LogicalResult
 UnrankedTensorType::verify(function_ref<InFlightDiagnostic()> emitError,
                            Type elementType) {
   return checkTensorElementType(emitError, elementType);
 }
 
+Optional<Type> UnrankedTensorType::join(Type other) const {
+  return ::join(*this, other.dyn_cast_or_null<TensorType>());
+}
+
+Optional<Type> UnrankedTensorType::meet(Type other) const {
+  return ::meet(*this, other.dyn_cast_or_null<TensorType>());
+}
+
 //===----------------------------------------------------------------------===//
 // BaseMemRefType
 //===----------------------------------------------------------------------===//
 
 Attribute BaseMemRefType::getMemorySpace() const {
   if (auto rankedMemRefTy = dyn_cast<MemRefType>())
     return rankedMemRefTy.getMemorySpace();
   return cast<UnrankedMemRefType>().getMemorySpace();
 }
 
 unsigned BaseMemRefType::getMemorySpaceAsInt() const {
   if (auto rankedMemRefTy = dyn_cast<MemRefType>())
     return rankedMemRefTy.getMemorySpaceAsInt();
   return cast<UnrankedMemRefType>().getMemorySpaceAsInt();
 }
 
+namespace {
+LogicalResult commonMemRefJoinMeetChecks(BaseMemRefType ty1,
+                                         BaseMemRefType ty2) {
+  if (ty1.getElementType() != ty2.getElementType())
+    return failure();
+
+  if (ty1.getMemorySpace() != ty2.getMemorySpace())
+    return failure();
+
+  auto memRefTy1 = ty1.dyn_cast<MemRefType>();
+  auto memRefTy2 = ty2.dyn_cast<MemRefType>();
+  if (memRefTy1 && memRefTy2 &&
+      memRefTy1.getAffineMaps() != memRefTy2.getAffineMaps())
+    return failure();
+
+  return success();
+}
+
+Optional<Type> join(BaseMemRefType ty1, BaseMemRefType ty2) {
+  if (ty1 == ty2)
+    return ty1;
+  if (!ty1 || !ty2)
+    return {};
+
+  if (failed(commonMemRefJoinMeetChecks(ty1, ty2)))
+    return Type();
+
+  if (!ty1.hasRank() || !ty2.hasRank() || ty1.getRank() != ty2.getRank())
+    return UnrankedMemRefType::get(ty1.getElementType(), ty1.getMemorySpace());
+
+  auto shape = joinShapes(ty1.getShape(), ty2.getShape()).getValue();
+  return MemRefType::get(shape, ty1.getElementType(),
+                         ty1.cast<MemRefType>().getAffineMaps(),
+                         ty1.getMemorySpace());
+}
+
+Optional<Type> meet(BaseMemRefType ty1, BaseMemRefType ty2) {
+  if (ty1 == ty2)
+    return ty1;
+  if (!ty1 || !ty2)
+    return {};
+
+  if (failed(commonMemRefJoinMeetChecks(ty1, ty2)))
+    return Type();
+
+  if (!ty1.hasRank() || !ty2.hasRank())
+    return ty1.hasRank() ? ty1 : ty2;
+
+  if (ty1.getRank() != ty2.getRank())
+    return Type();
+
+  auto shape = meetShapes(ty1.getShape(), ty2.getShape());
+  if (succeeded(shape))
+    return MemRefType::get(shape.getValue(), ty1.getElementType(),
+                           ty1.cast<MemRefType>().getAffineMaps(),
+                           ty1.getMemorySpace());
+  return Type();
+}
+} // namespace
+
 //===----------------------------------------------------------------------===//
 // MemRefType
 //===----------------------------------------------------------------------===//
 
 /// Given an `originalShape` and a `reducedShape` assumed to be a subset of
 /// `originalShape` with some `1` entries erased, return the set of indices
 /// that specifies which of the entries of `originalShape` are dropped to obtain
 /// `reducedShape`. The returned mask can be applied as a projection to
LogicalResult MemRefType::verify(function_ref<InFlightDiagnostic()> emitError,
 
   if (!isSupportedMemorySpace(memorySpace)) {
     return emitError() << "unsupported memory space Attribute";
   }
 
   return success();
 }
 
+Optional<Type> MemRefType::join(Type other) const {
+  return ::join(*this, other.dyn_cast_or_null<BaseMemRefType>());
+}
+
+Optional<Type> MemRefType::meet(Type other) const {
+  return ::meet(*this, other.dyn_cast_or_null<BaseMemRefType>());
+}
+
 //===----------------------------------------------------------------------===//
 // UnrankedMemRefType
 //===----------------------------------------------------------------------===//
 
 unsigned UnrankedMemRefType::getMemorySpaceAsInt() const {
   return detail::getMemorySpaceAsInt(getMemorySpace());
 }
 
for (auto e : strideExprs) {
     if (auto c = e.dyn_cast<AffineConstantExpr>())
       strides.push_back(c.getValue());
     else
       strides.push_back(ShapedType::kDynamicStrideOrOffset);
   }
   return success();
 }
 
+Optional<Type> UnrankedMemRefType::join(Type other) const {
+  return ::join(*this, other.dyn_cast_or_null<BaseMemRefType>());
+}
+
+Optional<Type> UnrankedMemRefType::meet(Type other) const {
+  return ::meet(*this, other.dyn_cast_or_null<BaseMemRefType>());
+}
+
 //===----------------------------------------------------------------------===//
 /// TupleType
 //===----------------------------------------------------------------------===//
 
 /// Return the elements types for this tuple.
 ArrayRef<Type> TupleType::getTypes() const { return getImpl()->getTypes(); }
 
 /// Accumulate the types contained in this tuple and tuples nested within it.

mlir/lib/IR/CMakeLists.txt

add_mlir_library(MLIRIR
   MLIRBuiltinAttributesIncGen
   MLIRBuiltinDialectIncGen
   MLIRBuiltinLocationAttributesIncGen
   MLIRBuiltinOpsIncGen
   MLIRBuiltinTypesIncGen
   MLIRCallInterfacesIncGen
   MLIRCastInterfacesIncGen
   MLIRDataLayoutInterfacesIncGen
+  MLIRJoinMeetTypeInterfaceIncGen
   MLIROpAsmInterfaceIncGen
   MLIRRegionKindInterfaceIncGen
   MLIRSideEffectInterfacesIncGen
   MLIRSymbolInterfacesIncGen
   MLIRTensorEncodingIncGen
 
   LINK_LIBS PUBLIC
   MLIRSupport
   )

mlir/lib/IR/TypeUtilities.cpp

 #include "mlir/IR/TypeUtilities.h"
 
 #include <numeric>
 
 #include "mlir/IR/Attributes.h"
 #include "mlir/IR/BuiltinTypes.h"
 #include "mlir/IR/Types.h"
 #include "mlir/IR/Value.h"
+#include "mlir/Interfaces/JoinMeetTypeInterface.h"
 
 using namespace mlir;
 
 Type mlir::getElementTypeOrSelf(Type type) {
   if (auto st = type.dyn_cast<ShapedType>())
     return st.getElementType();
   return type;
 }
auto dims = llvm::to_vector<8>(llvm::map_range(
         [&](auto shape) { return shape.getDimSize(i); }));
     if (verifyCompatibleDims(dims).failed())
       return failure();
   }
 
   return success();
 }
 
+FailureOr<SmallVector<int64_t, 4>>
+mlir::joinShapes(ArrayRef<int64_t> shape1, ArrayRef<int64_t> shape2,
+                 Optional<Location> location) {
+  if (shape1.size() != shape2.size())
+    return emitOptionalError(location, "shapes' sizes differ");
+
+  SmallVector<int64_t, 4> shape(shape1.size());
+
+  for (size_t i = 0, e = shape1.size(); i != e; ++i) {
+    int64_t dim1 = shape1[i];
+    int64_t dim2 = shape2[i];
+    shape[i] = dim1 == dim2 ? dim1 : ShapedType::kDynamicSize;
+  }
+
+  return shape;
+}
+
+FailureOr<SmallVector<int64_t, 4>>
+mlir::meetShapes(ArrayRef<int64_t> shape1, ArrayRef<int64_t> shape2,
+                 Optional<Location> location) {
+  if (shape1.size() != shape2.size())
+    return emitOptionalError(location, "shapes' sizes differ");
+
+  SmallVector<int64_t, 4> shape(shape1.size());
+
+  for (size_t i = 0, e = shape1.size(); i != e; ++i) {
+    int64_t dim1 = shape1[i];
+    int64_t dim2 = shape2[i];
+    if (dim1 == dim2 || ShapedType::isDynamic(dim1) ||
+        ShapedType::isDynamic(dim2)) {
+      shape[i] = ShapedType::isDynamic(dim1) ? dim2 : dim1;
+    } else {
+      return emitOptionalError(location, "dimensions at index ", i,
+                               " are incompatible: ", dim1, ", ", dim2);
+    }
+  }
+
+  return shape;
+}
+
 OperandElementTypeIterator::OperandElementTypeIterator(
     Operation::operand_iterator it)
     : llvm::mapped_iterator<Operation::operand_iterator, Type (*)(Value)>(
           it, &unwrap) {}
 
 Type OperandElementTypeIterator::unwrap(Value value) {
   return value.getType().cast<ShapedType>().getElementType();
 }

mlir/lib/Interfaces/CMakeLists.txt

 set(LLVM_OPTIONAL_SOURCES
   CallInterfaces.cpp
   CastInterfaces.cpp
   ControlFlowInterfaces.cpp
   CopyOpInterface.cpp
   DataLayoutInterfaces.cpp
   DerivedAttributeOpInterface.cpp
   InferTypeOpInterface.cpp
+  JoinMeetTypeInterface.cpp
   LoopLikeInterface.cpp
   SideEffectInterfaces.cpp
   VectorInterfaces.cpp
   ViewLikeInterface.cpp
   )
 
 function(add_mlir_interface_library name)
   add_mlir_library(MLIR${name}

 
 add_mlir_interface_library(CallInterfaces)
 add_mlir_interface_library(CastInterfaces)
 add_mlir_interface_library(ControlFlowInterfaces)
 add_mlir_interface_library(CopyOpInterface)
 add_mlir_interface_library(DataLayoutInterfaces)
 add_mlir_interface_library(DerivedAttributeOpInterface)
 add_mlir_interface_library(InferTypeOpInterface)
+add_mlir_interface_library(JoinMeetTypeInterface)
 add_mlir_interface_library(LoopLikeInterface)
 add_mlir_interface_library(SideEffectInterfaces)
 add_mlir_interface_library(VectorInterfaces)
 add_mlir_interface_library(ViewLikeInterface)
 

mlir/lib/Interfaces/JoinMeetTypeInterface.cpp

+//===- JoinMeetTypeInterface.cpp - Join/Meet Type Interface Implementation ===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "mlir/Interfaces/JoinMeetTypeInterface.h"
+#include "mlir/IR/Diagnostics.h"
+
+using namespace mlir;
+
+#include "mlir/Interfaces/JoinMeetTypeInterface.cpp.inc"
+
+Type mlir::join(Type ty1, Type ty2) {
+  if (ty1 == ty2)
+    return ty1;
+  if (!ty1 || !ty2)
+    return Type();
+
+  Optional<Type> join1;
+  if (auto interface1 = ty1.dyn_cast<JoinMeetTypeInterface>())
+    join1 = interface1.join(ty2);
+
+  Optional<Type> join2;
+  if (auto interface2 = ty2.dyn_cast<JoinMeetTypeInterface>())
+    join2 = interface2.join(ty1);
+
+  assert(!join1 || !join2 || join1.getValue() == join2.getValue());
+
+  return join1.hasValue() ? join1.getValue() : join2.getValueOr(Type());
+}
+
+Type mlir::meet(Type ty1, Type ty2) {
+  if (ty1 == ty2)
+    return ty1;
+  if (!ty1 || !ty2)
+    return Type();
+
+  Optional<Type> meet1;
+  if (auto interface1 = ty1.dyn_cast<JoinMeetTypeInterface>())
+    meet1 = interface1.meet(ty2);
+
+  Optional<Type> meet2;
+  if (auto interface2 = ty2.dyn_cast<JoinMeetTypeInterface>())
+    meet2 = interface2.meet(ty1);
+
+  assert(!meet1 || !meet2 || meet1.getValue() == meet2.getValue());
+
+  return meet1.hasValue() ? meet1.getValue() : meet2.getValueOr(Type());
+}

mlir/test/CMakeLists.txt

 add_subdirectory(CAPI)
 add_subdirectory(EDSC)
+add_subdirectory(Interfaces)
 add_subdirectory(SDBM)
 add_subdirectory(lib)
 
 if(MLIR_BINDINGS_PYTHON_ENABLED)
   add_subdirectory(python)
 endif()
 
 llvm_canonicalize_cmake_booleans(

mlir/test/Interfaces/CMakeLists.txt

+add_subdirectory(JoinMeetTypeInterface)

mlir/test/Interfaces/JoinMeetTypeInterface/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_llvm_executable(mlir-test-join-meet-type-interface
+  TestJoinMeetTypeInterface.cpp
+  )
+llvm_update_compile_flags(mlir-test-join-meet-type-interface)
+target_link_libraries(mlir-test-join-meet-type-interface
+  PRIVATE
+  MLIRIR
+  MLIRParser
+  MLIRJoinMeetTypeInterface
+  )
+target_include_directories(mlir-test-join-meet-type-interface PRIVATE ../..)
+

mlir/test/Interfaces/JoinMeetTypeInterface/TestJoinMeetTypeInterface.cpp

+//===- TestJoinMeetTypeInterface.cpp - Test Join/Meet interface -----------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// RUN: mlir-test-join-meet-type-interface
+
+#include "APITest.h"
+#include "mlir/IR/AffineMap.h"
+#include "mlir/IR/BuiltinTypes.h"
+#include "mlir/IR/Diagnostics.h"
+#include "mlir/IR/TypeUtilities.h"
+#include "mlir/Interfaces/JoinMeetTypeInterface.h"
+#include "mlir/Parser.h"
+
+using namespace mlir;
+
+int errors = 0;
+
+#define PARSE(str)                                                             \
+  ((std::string("null") == str) ? Type() : parseType(str, &context))
+
+TEST_FUNC(join_meet) {
+#define CHECK(func, ty1, ty2, expected)                                        \
+  do {                                                                         \
+    Type found = func(ty1, ty2);                                               \
+    if (found != expected) {                                                   \
+      emitError(FileLineColLoc::get(&context, __FILE__, __LINE__, 0),          \
+                #func "(" #ty1 ", " #ty2 ") = ")                               \
+          << found << " != " #expected;                                        \
+      ++errors;                                                                \
+    }                                                                          \
+  } while (false)
+
+#define CHECKP(func, ty1, ty2, expected)                                       \
+  CHECK(func, PARSE(#ty1), PARSE(#ty2), PARSE(#expected))
+
+  MLIRContext context;
+
+  CHECKP(join, i8, i8, i8);
+  CHECKP(join, i8, i32, null);
+  CHECKP(join, tensor<*xi8>, tensor<*xi32>, null);
+  CHECKP(join, tensor<1xi32>, i32, null);
+  CHECKP(join, tensor<1xi32>, tensor<i32>, tensor<*xi32>);
+  CHECKP(join, tensor<1xi32>, tensor<2x3xi32>, tensor<*xi32>);
+  CHECKP(join, tensor<*xi32>, tensor<*xi32>, tensor<*xi32>);
+  CHECKP(join, tensor<?xi32>, tensor<?xi32>, tensor<?xi32>);
+  CHECKP(join, tensor<1xi32>, tensor<1xi32>, tensor<1xi32>);
+  CHECKP(join, tensor<1x2x?xi32>, tensor<1x?x3xi32>, tensor<1x?x?xi32>);
+  CHECKP(join, tensor<*xi32>, tensor<4x?xi32>, tensor<*xi32>);
+
+  CHECKP(meet, i8, i8, i8);
+  CHECKP(meet, i8, i32, null);
+  CHECKP(meet, tensor<1xi32>, i32, null);
+  CHECKP(meet, tensor<1xi32>, tensor<i32>, null);
+  CHECKP(meet, tensor<1xi32>, tensor<2x3xi32>, null);
+  CHECKP(meet, tensor<*xi8>, tensor<*xi32>, null);
+  CHECKP(meet, tensor<1xi8>, tensor<1xi32>, null);
+  CHECKP(meet, tensor<*xi32>, tensor<*xi32>, tensor<*xi32>);
+  CHECKP(meet, tensor<?xi32>, tensor<?xi32>, tensor<?xi32>);
+  CHECKP(meet, tensor<1xi32>, tensor<1xi32>, tensor<1xi32>);
+  CHECKP(meet, tensor<1x2x?xi32>, tensor<1x?x3xi32>, tensor<1x2x3xi32>);
+  CHECKP(meet, tensor<*xi32>, tensor<4x?xi32>, tensor<4x?xi32>);
+  CHECKP(meet, tensor<4xi32>, tensor<5x6xi32>, null);
+
+  auto null = Type();
+  auto i32 = IntegerType::get(&context, 32);
+  auto memref_mem8 = MemRefType::get(1, i32, {}, 8);
+  auto memref_mem9 = MemRefType::get(1, i32, {}, 9);
+  CHECK(join, memref_mem8, memref_mem9, null);
+  CHECK(join, memref_mem8, memref_mem8, memref_mem8);
+  CHECK(meet, memref_mem8, memref_mem9, null);
+  CHECK(meet, memref_mem8, memref_mem8, memref_mem8);
+
+  auto memref_nomap = MemRefType::get(1, i32, {});
+  auto memref_map = MemRefType::get(1, i32, {AffineMap::get(1, 2, &context)});
+  CHECK(join, memref_nomap, memref_map, null);
+  CHECK(join, memref_map, memref_map, memref_map);
+  CHECK(meet, memref_nomap, memref_map, null);
+  CHECK(meet, memref_map, memref_map, memref_map);
+
+#undef CHECKP
+#undef CHECK
+}
+
+int main(void) {
+  RUN_TESTS();
+  return errors;
+}

mlir/test/Interfaces/JoinMeetTypeInterface/lit.local.cfg

+config.suffixes.add('.cpp')