Open MLIR Meeting 6/2/2022: IRDL, a dialect to represent IR definitions

This Thursday, June 2nd (9am California Time, 16:00 UTC), @math-fehr (University of Edinburgh) will present IRDL, a dialect to represent IR definitions.

IRDL can represent types, attributes, and operations in a similar manner than TableGen, and register them at runtime without having to compile to C++. IRDL also compiles to IRDL-SSA, which is an SSA-based representation of dialect definitions that are easier to generate and modify. The hope is that IRDL and IRDL-SSA will allow users to more easily define dialects from other languages and projects, as well as to more easily reason about the dialect definitions.

!! Changing the platform for the meeting: we’ll use Zoom this week:

Meeting ID: 851 5109 0498
Passcode: 828404

Edit: here are the slides and the recording for this meeting

4 Likes

Thanks a lot for all your questions.
Here is a link to the slides.
The current code for IRDL is on github: GitHub - opencompl/dyn-dialect: A repository to test dialects defined dynamically.

I’ll update soon the github with (more) documentation. Note that the project rely on a fork of MLIR, but this is because I am currently working on the dynamic dialects patches at the same time.

Feel free to ask any remaining questions or follow-up here or in Discord (@Mathieu Fehr).

2 Likes

Thank you Mathieu!

@AlexEichenberger emailed me with some of his thoughts on the issue I raised of mixing SSA with side effects along with ideas on what improvements/changes could be made to IRDL-SSA to support simpler custom constraint rules. At his suggestion, I’ve copied the emails below. My reply is a doozy, so be warned!

Alexandre’s initial email

Ryan,

sorry if I do not express the ideas below in proper IRDL dialect, hopefully it is clear enough for you to make sense of it.


operation(%0: Anyof<F32, F64>, %1: Anyof<F32, F64>

where %0 and %1 must have the same type.

A simple way to express your SSA


# constraints for the first param ($0)

%2 = isType<F32> (%0) # added the actual parameter, testing if first param is f32 resulting in a true/false boolean.

%3 = isType<F64> (%0)

%4 = anyOf(%2, %3)

# constraints for the second param ($1)

%5 = isType<F32> (%1)

%6 = isType<F64> (%1)

%7 = anyOf(%5, %6)

SameValue(%4, %7)

And now you can do common sub-expression elimination that show %2 and %5 must have the same value, and %3 and %6 must have the same value.

You could then add multiple input params to `isType<F32)(%0, %1) where true is set only when all the operands have the same type.

Then naturally, if you have a 3rd input parameter that is not bound to the same value, by the fact that you would not have a “sameValue” then none of the CSA applies and you would naturally keep a different side-effect free isType for the %0 and %1, and one for %2 (which would be the 3rd param).

Hope this helps.

Basically the message is that I believe one could use pure SSA and derive to the same results. Using traditional SSA might be good in this context as the MLIR dialects use SSA everywhere (but for the memory ops, obviously)

I think it would also simplify the analysis as you can straightforwardly analyse top down each statement and processing all inputs at once without having to keep track of multiple side-effect values.

Summarizing the constraints we often have in higher level dialects (for us ONNX dialect, part of GitHub - onnx/onnx-mlir: Representation and Reference Lowering of ONNX Models in MLIR Compiler Infrastructure

rank(input 1) == rank(input 2)

x = rank(input 1) and y = scalar value input 3 (compile time or runtime value) where constraint x < y <= x must hold.

another thing that we have is we have ops that have simple and other complex rules. It would be nice if we could then use IRDL for all the easy ones (so that we don’t have to write c++ code for it) and then use custom c++ code just for the complex rules… Basically composing old and new.

Thanks for the nice presentation and work, quite interesting

Let me know if there is a discussion already about this, and you or I can paste this there.

Alexandre

My reply:

Hi Alexandre,

I see what you’re getting at.

I’ve written a lot in this email (please forgive me, I’m known to be verbose). I’m going to cross-post this to Discourse (omitting some of your personal information), as I think that’s a great idea!

By the way, you should thank Mathieu and his collaborators for their (agreed) nice presentation, as I was just asking questions in the presentation!

High level summary: I really like your idea to allow “simple” compile-time checks. I see your point about rewriting the syntax of IRDL-SSA to rearrange it so that it reads in a different top-down vs bottom-up manner, but I’m not sure about how much that would require changing the language.

I think the way that IRDL-SSA actually expresses local constraints does matter for this syntax discussion (since we’re talking about IRDL-SSA as it currently exists). It’s new to me too though, so I get it.

operation(%0: Anyof<F32, F64>, %1: Anyof<F32, F64>

where %0 and %1 must have the same type.

A simple way to express your SSA

# constraints for the first param ($0)
%2 = isType<F32> (%0) # added the actual parameter, testing if first param is f32 resulting in a true/false boolean.
%3 = isType<F64> (%0)
%4 = anyOf(%2, %3)

# constraints for the second param ($1)
%5 = isType<F32> (%1)
%6 = isType<F64> (%1)
%7 = anyOf(%5, %6)

SameValue(%4, %7)

I believe the way to express this in IRDL-SSA is as such (I’ll try to reuse your numbering as much as possible):

%2 = irdlssa.is_type : f32
%3 = irdlssa.is_type : f64
%4 = irdlssa.any_of(%2, %3) # %4 is now usable as a constraint
%5 = irdlssa.is_type : f32
%6 = irdlssa.is_type : f64
%7 = irdlssa.any_of(%5, %6)
# I don't have a way to say %4 and %7 must be same here
irdlssa.operands(percent0: %4, percent1: %7)
# I assumed that %0 and %1 represented the actual values passed in as parameters, so I did not put them in SSA values since they're runtime params.

​At this point, I’m not sure how to represent that %4 and %7 must be the same (when bound against an operator) assuming that we wrote them as separate SSA values. If the programmer wrote them as separate SSA values, then they probably wanted to use them separately.

To achieve the effect that the two parameters to the operation must be using the same type, I would do this:

irdlssa.operands(percent0: %4, percent1: %4)

So that percent0 will bind %4 to a specific bound type and then percent1 must match that type exactly.

I like your proposed syntax though, but it’s a pretty big change to the syntax structure as it appears to me even though it looks visually similar to the current IRDL-SSA.

As I understand it, IRDL-SSA involves constructing local constraints from other local constraints, then they get applied to arguments automatically by the syntax of:

argument_name : <local constraint>

A side effect of this use of a local constraint is that this use “binds” (that’s the word I’m going to use instead of “define”) the local constraint (which could be an SSA value like %0) to a specific type.

Here’s the relevant first-class members/different types of “things” as I see it in IRDL-SSA (I’ll be ignoring attributes for now since I can’t figure out what they are):

  • Value - an SSA value. something marked with %(number). Can hold or be set to anything (other than an operator since I don’t know if there’s syntax to use a value as an operator). Corresponds to a SINGLE type/constraint/attribute, but it appears that the underlying constraint can convert to a type by binding (details below). Ex: %0

  • Bound Type - an actual, concrete, “bound” type. I say bound because it is the past tense (and past participle) of “bind” which is what can make a bound type. Ex: f32

  • (Local) Constraint (a.k.a. Unbound Type) - a constraint/condition that can be used to check something else. A type used as a constraint is understood as exactly that type. This is basically an unbound type since “binding” this constraint creates a bound type. Examples:

    • irdlssa.is_type : f32
    • !f64 (anything that is equivalent to f64)
    • irdlssa.any_of(%5, irdlssa.is_type : "cmath.complex"<!f32>)
  • Operators - keywords/calls that can create values and cause side effects (holding constraints, bound/unbound types, etc.) Examples:

    * irdlssa.any_of - creates a constraint that takes in some types and will bind to the one that matches (no details yet on how this matching works in edge cases)

    • !<type> - anything equivalent to this type (note: I believe if this is used with a constraint, then it will be used as what the constraint binds to)
    • irdlssa.parametric_type - allows you to use a constraint that’s not yet become a bound type (e.g. %2, any_of(…), etc.) in the parameters of another type. this creates a constraint that will bind all its parameters as well as itself to a bound type when it’s used.
      • irdlssa.parametric_type : "cmath.complex"<%2> is necessary since just using "cmath.complex"<%2> is (apparently) not legal since
    • "named type"<parameters> - creates a bound type defined elsewhere by you that takes in some types for parameters. if you want these types to be constraints (which will bind to a type when this is actually used by a side effect-causing operator), then use this in parametric_type
    • operands(argName: <constraint/type>, ...) - will bind the constraint of each arg to the bound type that matches whatever logic the constraint defined. if the constraint is just a type, then it’s exactly that type. this causes side effects! if the constraint is an SSA value, then it can somehow bind that SSA value to a specific bound type (and it may side effect other, unmentioned SSA values)

Based on the discussion in the call, it appears that “binding” a constraint to a type is applied at something like the lowest level possible. So in this case:

 %1 = <some bound type>
 %2 = <some bound type>
 %3 = any_of(%1, %2)
 %4 = parametric_type: "mytype"<%3>
 %5 = parametric_type: "mytype"<%3>

When you use %4 in some operator that binds it to the actual named type, then it will actually bind %3 to either %1 or %2. That allows the redundant optimization of %5 since it will point to %3 (which by the side effects of the operator on %4 has been bound to a type).

My original proposal in the call was something along the lines of:

operands(lhs: %3 -> %4, rhs: %4)

Where I change the meaning of using the constraint such that it doesn’t actually change the underlying constraint to the type of lhs (e.g. changing %3 from complex<any_of(f32, f64)> to complex<f32> by binding the any_of) but instead stores that new type of lhs into %4.

I’m amenable to the syntax, but it’s a tricky thing to express without adding many new idioms. I’d like to use the = sign to show that %4 is actually being assigned, but then I’d have to put %4 on the left which would make it seem like the constraint is not %3. Additionally, I’m not sure if omitting the -> should mean that %3 will now be bound, as it is in IRDL-SSA currently, or if it means that %3 won’t be bound at all. I have issues with both of those approaches.

However, I’m not sure how one would potentially capture nested any_ofs. I’ll post about this on Discourse though.

Regarding ONNX and the more complicated custom constraints:

rank(input 1) == rank(input 2)
x = rank(input 1) and y = scalar value input 3 (compile time or runtime value) where constraint x < y <= x must hold.

I don’t think I follow for this example. Maybe this is some partial ordering or other non-integer system, but this would appear to constrain “x < y <= x” to “x == y”. Is this a typo, or am I misunderstanding?

So inputs 1 and 2 have this introspective/inferred trait/attribute/aspect called “rank”. I’ll assume that this kind of trait is analogous to how a type like a char (in C) can be known to have some property that states it can represent at least 8 bits worth of values. So this would mean that rank can be calculated statically based on the templated type of input 1 (e.g. if input 1 is of type matrix<rank = 5> and input 2 is of type matrix<rank = 6> then we can know that their ranks don’t match without know the actual values inside the inputs).

So the issue is that you also need to support input 3 which is a scalar value that has to relate to the “statically known” traits of the other inputs (through the templated type) but input 3 might not be known until runtime. So you might not know at compile time if something you wrote is horribly wrong.

I believe this is analogous to indexing into a fixed-length vs variable-length array (e.g. ArrayList or Vector, not a variadic array like some crazy people use). With a fixed-length array, the compiler can statically check that the index is within the bounds (e.g. if you declare int a[5] then try to do a[6], you can warn the user or compile error on this if desired). You know this because the length of the array is somehow captured as part of the type of the array class (even though in C it’s not a template but whatever). But if you have a variable length array, then you can’t check this at compile time (unless you can do some fancy math and prove that it will always be out of bounds).

I agree that being able to write “simple” rules (like rank(input 1) == rank(input 2)) should be possible in IRDL-SSA. I think this shouldn’t be too complex to add if the “API” for accessing the data of these simple rules/attributes is well-defined (but defining the API is probably the hard part). For example, if you have some templated type like matrix<int rank, type datatype> then (assuming you can access the rank in IRDL-SSA) you should be able to say that two instances which have non-matching types (e.g. a matrix<5, float> and matrix<5, int>) but are compatible based on your simple logic are compatible at compile time. So, if you know the rank at compile time since it’s part of the static type of the matrix (and assuming, for example, that you specified that rank as a constant), then you can compare the two ranks statically at compile time.

I imagine that this could go well with constant propagation where the IRDL-SSA will try to check on the rules it knows if the traits (like rank) are available at compile time (which could be based on if it’s constant or not). The same checks could be performed at runtime by autogenerated C++ code if IRDL-SSA can easily generate/convert its checks to C++ run-time checks.

Thank you for reaching out! I’ll try to look at ONNX when I get a chance, as I’m also trying to write a new dialect using the MLIR and ODS tools but not in MLIR proper (part of the CIRCT incubator project).

Pax,
Ryan

Go Jackets!

I’d like feedback on my understanding of some of the members/“things” in IRDL-SSA and how they interact.

I recommend sharing your thoughts on this thread!
However, if you’d like to contact me directly, email me at ryan.lynch@gatech.edu and ryan.lynch@amd.com. I’m also on the LLVM discord as emosy#6420

From my incredibly long email above, here’s a proposed syntax to handle removing some side effects from the IRDL-SSA code. Fair warning, this is way longer than I expected (even after cutting out two or three other syntaxes that I considered but rejected involving equals signs).


Original (from slide 44 of the IRDL slides linked by Mathieu):

irdlssa.operation mul {
  %0 = irdlssa.is_type : f32
  %1 = irdlssa.is_type : f64
  %2 = irdlssa.any_of(%0, %1) //f64
  %3 = irdlssa.parametric_type : "cmath.complex"<%2>
  irdlssa.operands(lhs: %3, rhs: %3)
  irdlssa.results(res: %3)
}

When you call this in MLIR with this code:

%2 = cmath.mul(%0, %1) :
  (!cmath.complex<f64>, !cmath.complex<f64>) ->
   !cmath.complex<f64>

Then IRDL-SSA, upon seeing lhs: %3 with lhs of type cmath.complex<f64> (since the ! is not part of the type, as I learned), will “bind” (that’s the word I’ve chosen) the constraint %3 to the actual type cmath.complex<f64>. Now %3 for the other argument and for the result will be cmath.complex<f64>.
As I understand it (based on the explanation someone other than Mathieu [I don’t recall who] gave in the call when I asked about the optimization example on the following slide, slide 45), this actually changes and “binds” %2 from irdlssa.any_of(%0, %1) to just %1 (since that is f64). Now %3 is still of type irdlssa.parametric_type : "cmath.complex"<%2> but since %2 now expands to f64, then this requires that rhs and res are of type "cmath.complex"<f64>.

My issue with this present behavior (and why I’m proposing this new behavior) is that not only are there side effects from this use of an SSA value (which could confuse many who aren’t very familiar with SSA like myself), but that the side effects may (depending on the actual specification of the language) be on another SSA value which isn’t directly mentioned in this line of code.

Basically, a new user will not be able to readily see that SSA value %2 is affected by the use of %3 in the operands call.


Here is the new behavior and syntax I was thinking when I proposed this in the call:

irdlssa.operation mul {
  # Everything else the same in %0 to %3
  irdlssa.operands(lhs: %3 -> %4, rhs: %4)
  irdlssa.results(res: %4)
}

Note that there is now a new SSA variable %4 and that it is explicitly used as the rhs and res local constraints.

I propose that %2 and %3 remain entirely unchanged after the operands call. Assuming the MLIR code from above, %4 will just hold "cmath.complex"<f64>.

If one wanted to capture the type that %2 would have bound to, then maybe you could do this:

%3 = irdlssa.parametric_type : "cmath.complex"<%2 -> %5>

So then %5 would become f64. I think %3 should then be equal to irdlssa.parametric_type : "cmath.complex"<%5> that way a later use of %3 is explicitly understood to use the type that %5 became, f64 for this example.

I also like that this explicitly shows that a new SSA value is being created because of the use of some other SSA value and that it’s based on the other one. I think this is the logical place to define what the new value should be called.

I believe that, under this system, we should enforce that SSA values defined with -> (not sure what to call this, maybe side-effected values?) can only be set by one use of one other SSA value. Basically, for every SSA value defined with -> %<SSA value>, only one other SSA value should be allowed to set it. This is because the value can only be defined in one location and it’s defined when another value is used, hence the 1:1 relationship. However, I believe it could be possible to allow one use to set multiple SSA values.

So for example this would not be allowed:

%0 = irdlsaa.any_of(f32, f64)
%1 = irdlssa.parametric_type : "cmath.complex"<%0 -> %2>
# at this point, a use of %1 can set %2 (if it's binding)
%3 = irdlssa.any_of(%1, i32)
# at this point, a use of %3 can set %2.
# %1 cannot be used now (other than by %3) since using %1 is supposed to set %2
%4 = irdlssa.any_of(%1, i64) # ILLEGAL
# this line is illegal since %3 has already used %1
# which means that a use of %3 will set %2.
irdlssa.operands(first: %3 -> %5, second: %5)
# this operands call could be allowed if we allow using %3 to set %2 and %5
# regardless, %3 MUST set %2 here and leave every other SSA value unchanged
# one could then reuse %0 and set it to another SSA value to effectively reuse %3
%6 = irdlssa.parametric_type : "mydialect.matrix"<%2>
irdlssa.results(res: %6)
# this is the powerful part. we can specify that we return a matrix
# which is parameterized with the same type as the complex parameter type of operand first

I actually now think that having a different syntax for an SSA value which is set by the use of another SSA value is actually kind of helpful. That way, you know if you used the -> symbol then this can only be set in a certain way and that it constrains other values. This even signals that the SSA value has not actually been assigned yet, but it can be statically known when it is assigned based on when the one SSA value allowed to set it is used (e.g. when %3 is used, then %2 is assigned and becomes live/available/valid/whatever word you want to use).

The default behavior if there is no other SSA value assigned with -> is that the original SSA value and all others not being explicitly set should remain unchanged in every way. This makes the SSA more “pure” since the value will always hold one thing and might not change to a narrower type. I could see this having an advantage in analysis in multiple ways since it provides more information to the compiler/analyzer with less difficult dataflow analysis.

There’s a separate discussion to be had about what operations qualify as causing side effects that will set the other SSA value, but I think these could be handpicked or otherwise well-defined explicitly so that it can be truly known when the other SSA value will be assigned.

I’d love to hear feedback on this suggested new syntax and behavior. I had to wrestle with it along the way, but I think it’s workable.

Last post for now, I swear. This is a short one too!

@math-fehr I forgot to ask during the call, but what’s the exact relationship between IDRL and IDRL-SSA?
Are they intended to be equivalent in expressive power and completely convertible/interchangeable? Is IDRL-SSA necessarily more expressive than IDRL? Is IDRL-SSA the way that IDRL works in the underlying implementation/definition?

Thanks for the feedback!

Members of IRDL-SSA

Here are my thoughts on what are the members of IRDL-SSA, and how they interact:
To me, there is only one kind of thing in IRDL-SSA, and that is a constraint. The current type of constraints I presented are:

  • is_type, a type equality
  • parametric_type, a constraint that checks that the given type is an instance of some type constructor, and also has parameters that are satisfied by the given constraints.
  • any_of, which will check that a type is satisfying one of the given constraints.
  • and, which checks that a type is satisfying all given constraints.
  • not, which checks that a type is not satisfying a constraint

We have in practice more builtin constraints in mind (around 20 of them), but the key ones are here.
The whole idea about the verifier algorithm, is that each of these constraints is associated with an SSA-value. The algorithm to verify an operation/type/attribute is looking like this (pseudocode):

bool verify(IRDLConstraint constraint, Type typ, std::map<IRDLConstraint, Type> matching)  {
  auto previous_type = matching.find(constraint);
  if (previous_type)
    return previous_type == typ;
  // Here, this is the check for an is_type
  if (constraint.isa<IsType>()) {
    if(typ != constraint.typ)
      return false;
  }
  // This is a check for an any_of
  if (constraint.isa<AnyOf>()) {
    bool hasMatch = false;
    for (auto anyofconstraint : constraint.constraints) {
      // We make sure to not create a new matching when the case fail
      auto oldMatch = matching;
      if (!verify(anyofconstraint, typ, oldMatch))
        continue;
      matching = oldMatch;
      hasMatch = true;
      break;
    }
    if (!hasMatch) return false;
  }
  // Other cases
  ...
  // Here, we associate the constraint with a value
  matching[constraint] = typ;
  return true;
}

Essentially, every time we match a type to a constraint, we associate its type to the constraint. So when checking a constraint, we first look if the constraint was already matched before during the verification process.

So this is why irdlssa.operands(lhs: %4, rhs: %4) have both the same type for each operand. This is because they have the same constraints, thus have the same type. This is also why parametric_type has a NoSideEffect interface. This is because the type of its SSA-value is exactly defined by the type of its parameters. This is similar to is_type. However, this is not the case for any_of, since any_of(%0, %1) depends on the type match, and not only on %0 and %1.

I hope this makes it a bit clearer!

ONNX constraints

Otherwise, relative to your constraints with rank(input_1) == rank(input_2):
There are two ways of encoding this in IRDL-SSA. One is to explicitly say:

%rank = irdl.Any
%datatype1 = irdl.Any
%datatype2 = irdl.Any
%input1 = %irdl.parametric_type<%rank, %datatype1>
%input2 = %irdl.parametric_type<%rank, %datatype2>

which gives you the equality between rank(input1) and rank(input2).

The other way, which I haven’t talked about in the talk, would be to use custom constraints. Essentially, custom constraints can also not return a type, and they act as an additional verifier. For instance, you could also have something like:

%input1 = irdl.base_type "matrix"
%input2 = irdl.base_type "matrix"
irdl.custom<check_rank_equality>(%input1, input2)
irdl.operands(input1: %input1, input2: %input2)

This can check the equality you want on the rank without having to deal with specifying the equality structuraly.

I hope this helps as well!

Got it. I see why it’s straightforward now to just make a constraint like %4 become a specific type.

The way I was thinking about constraints was that they were more definitional than objects. So the idea of changing a constraint by using it didn’t make much sense to me at first. I imagined that multiple uses of a constraint working like just duplicating the same definition from earlier, rather than enforcing that all types matching a specific constraint are actually the exact same type.

I believe that one could easily adapt the lookup of the previous type to a lookup for each constraint that matches from a type to the true/false bool of it verifying. If you were to consider the approach I suggested (where one can explicitly assign the type that matches a constraint into an SSA value holding the new strict constraint which is just the type), then you could just perform this lookup and create a new constraint which is just isa of typ and put that in the side-effected SSA value. You could then have a different verify and set method which will verify the type against the old constraint and then set it in a new constraint in the new SSA value. But that’s getting into the software design.

So the any_of operation is the one that actually causes side effects where the SSA value it is assigned to becomes one of the specific types listed. Is that correct?


I like the way you did the matching rank of inputs. Makes sense.

Overall, the current approach where one would have to duplicate a lot of the constraints to avoid them restricting each other (like %datatype1 and %datatype2) isn’t strictly worse in my opinion than what I’ve suggested. However, I believe that it may present comprehension issues for new users (like explained before) and that there may be optimizations that are more difficult to perform or not as relevant (e.g. the redundant computation example from slide 45 would require the compiler to know that %3, %4, and %5 are not all used, which would mean they’re just dead code).

What do you think?

Response to your first message (the one about the implementation idea)

Hmm, I’m not quite sure I like this approach :confused:
So one of the major drawback I see is that you have to keep the constraint that once an SSA-value is bound (with %1 -> %2), you cannot use it in the rest of the program. This feels really weird (and is also hard to verify).
One thing I could try to see, is if we can have an operation like %1 = irdl.match %2, where %2 is a constraint type, and %1 is a type. This would essentially do the matching part, though I am not sure how would this work when there is multiple things to match.
I’ll check with Theo tomorrow, he might have a better insight (he worked the most on the SSA part of IRDL).

Response to your 2nd message

The relationship between IRDL and IRDL-SSA is that IRDL is used as a fronted to users, a bit like ODS, while IRDL-SSA is meant to be the underlying implementation, and also probably the best way to introspect and generate dialects.

Response to your 3rd message

Technically, all constraints will assign a type to the constraint. The main difference is that any_of may assign different types depending on the type matched. This is the same for any. is_type, for instance, will also assign a type, but since is_type will always match the same type, it does not complexify anything.

For the duplication of %datatype1 and %datatype2, I feel that not duplicating it would be a problem. Since we associate a type for each SSA-value, using twice the same SSA-value should yield the same value. To be fair, I think that this is the approach taken by PDL, which I try to follow.

1 Like

Video is online FYI: MLIR Open Meeting 2022-06-02: IRDL, a dialect to represent IR definitions - YouTube

1 Like

Assuming we have something of the form %3 = op(%1 -> %2)

I could see it where you just mark %3 as dead/unusable after its first use. Upon encountering this line (the one where %3 is set), attach %2 to %3 so that the live/available analysis of %2 can be done correctly. It might be difficult to properly pass that along whenever %3 is used elsewhere, but if you can get a list of used SSA values in each assignment/statement then iterate through each of them and do this logic:

  • Example statements for clarity:
%1 = any_of(f32, f64)
%3 = complex<%1 -> %2> # note: %3 will eventually hold complex<%2>... ouch!
%4 = composite_type<%3>
  • If the SSA values (e.g. %3) binds another (e.g. %2, which I’ll call a “dependent” SSA value), then now the SSA value on the left-hand side of the assignment (e.g. %4) will bind that dependent value (like %2). Additionally, mark the used SSA value (%1) as dead or unusable. This can be extended to one value binding multiple dependent values, without loss of generality (I think). If there’s no left-hand side of the assignment (e.g. it’s an op like operands), then it probably means that the dependent value is now live since we’re actually matching the constraint to a type. It’s likely there are exceptions to this general rule though.
    • For clarity, Let’s call %1 a “yielding value” since it can yield another value through its use, %2 a “dependent value”, %3 a “binding value” until it’s used then it’s a “used binding value” (need a clearer name to communicate illegality of future use), and %4 a “binding value”.
    • A binding value is any value that will cause dependent values to become bound. A dependent value is not live until a binding value that is associated with it is used in an operation with “side effect” (loosely speaking) that will bind values by matching against a type. A binding value that’s used in any way becomes a used binding value. If a binding value is used in an assignment, then it can make the assigned value a binding value. If a binding value is used in an operation that does not assign a value (in the regular way), then it probably means that all the associated dependent values become live. Do these state transitions make sense?
  • If the SSA value does NOT bind another, then it’s all good. Continue as normal. Should be fine.

The issue I see is that this still violates the idea that “asking a question should not change the answer”, which I think is a simplified way that people (this means me) understand SSA. I say this because in my example, %3 first points to complex<%1> but then it becomes complex<%2>, a stricter version of the original value. I stated that it would have to change to the newly bound dependent value since it would be more complicated if it still pointed to the old one (unless you modified the meaning to say that on the first use %3 will end up binding %2 but afterwards won’t bind anything). I think it’s fine if we don’t use fully mathematically pure SSA, but I’d rather be closer to SSA if possible to simplify the assumptions.

I can see the argument that the SSA value doesn’t technically change since it’s still assigned to the same constraint, it’s just that the semantics of the constraint are that it will match to a type on the first match then always match that exact type after the first match. I just don’t like that since it feels non-static/inconsistent (first use vs subsequent uses aren’t identical). How I see a constraint working is that asking “does this type match this constraint” doesn’t affect the type or constraint, though I see the value in having that feature.

I see your point that my suggestion could be more difficult to verify, but I think it’s possible. I think I just prefer this method so I’m biased to believe it’s easier/more consistent. It still has flaws as I’m designing this in the void without truly understanding how it will be used (due to my lack of experience), so more refinement is definitely needed.

Makes sense. Do you plan to allow users to directly define in IRDL-SSA? It’s possible that down the line it might be easier to specify some very obscure/complicated things in the SSA form or that the SSA form might be more powerful by necessity. I don’t think it’s too unfriendly at this point, and I like the idea of using it (not sure why I like it though).

I haven’t looked into PDL yet. I’ve been meaning to as I think it may be useful for me.

That said, I agree that de-duplication is not possible with the current semantics that an SSA value’s constraint will be assigned to a specific type after it’s matched the first time. I think this is an example where the current semantics of the language provide a limitation on optimization. Imagine a situation as such:

%1 = any_of<complex<f32>,complex<f64>>
%2 = any_of<complex<f32>,complex<f64>>
%3 = any_of<complex<f32>,complex<f64>>
operands(num1: %1, num2: %2, num3: %3)

In the current IRDL-SSA, it is necessary to duplicate the constraint 3 times if it is desired that num1, num2, and num3 be allowed to be different types that still match the constraint. I’m not sure how the generator/compiler/backend implementation will work, but I imagine that it will probably have to either

  • (a) duplicate the same Constraint object three times

or

  • (b) implement something similar to what I’ve proposed where it then replaces %2 and %3 with some copy of %1 that isn’t specifically tied to one of the types.

In case (a), I believe this is strictly less efficient than what I’ve proposed (which would allow the user to reuse %1 for all three operands with the same semantics). In case (b), it sounds like this would involve implementing logic similar to what I’ve proposed, as the backend would now need to have a different version of the constraint that doesn’t set it to a type when it matches. In my opinion, you should just expose that functionality to the user if you’re already going to implement it.
It’s possible there’s ways around this, but that’s how I see it. I believe it’s likely that de-duplication will be more possible under my suggestion to redefine the semantics of constraints and matching.

Hey! Thank you for all the feedback!
To give a bit more context and maybe clarify a few things about the semantics of IRDL-SSA, I made a little video explaining in more details how constraint verification works in IRDL-SSA.

1 Like

Thanks for sending the video @Moxinilian!

I think I’m starting to understand the current problem we are having.
My mistake is having named the dialect IRDL-SSA. A better name could have been IRDL-Constraints for instance.

Our current abstraction is not really meant to represent a procedure to be executed, but more of a description of the constraints. This is following the way PDL is defining things (you should definitely check it out). This representation is easy to generate, and to “reason with” in a mathematical way. This is because each operation represent really an equation, rather than a match or a proceduce.
So, when we write %0 = irdl.is_type i32, we mean %0 = i32. When we write %2 = irdl.parametric "cmath.complex"<%0>, what we mean is %2 = cmath.complex<%1>. This makes then sense that irdl.operands(%2, %2) is representing two operands with the same value, since they are defined by the same variable.

However, it seems that the abstraction you are thinking of is a “procedure” abstraction, where we represent a computation. I’m thinking more and more if we could derive such abstraction, and compile our IRDL-SSA to this abstraction. This IRDLInterp abstraction would be top-down, so it would kind of look like what you want. As a parallel, this is how PDL works, by compiling the PDL dialect (representing equations) to PDLInterp (representing the computation). However, this IRDLInterp would still look different than your proposal, but will probably look more like something you want!

I don’t think we currently want to change that dramatically our design to be honest, though I’m open to add one layer of abstraction to represent the computation we will have in our verifier. I’m not quite sure how would that help though, but if we have some use cases then I would be fine having it!

1 Like

PDL vs PLD interpreter dialects is definitely how I see it as well! (I pointed it out during the meeting)

1 Like

slides link is broken for me

1 Like

Should be fixed in Fix link to IRDL talk (missing leading /) · llvm/mlir-www@bf055d8 · GitHub

I like the idea to rename it to make it more clear. I don’t know if IRDLInterp would be the best name (I’m not familiar with PDL vs PDLInterp so I’m not sure how analogous the relationship is), but I like that it’s more clear than IRDL-SSA (which can confuse people like me xD).

You could later add another layer of abstraction like we’ve discussed here. But I see the purpose of your design now, and I like the simplicity. The current IRDL and IRDL-SSA/IRDLInterp would both be a declarative statement of what the dialect must be, and then a lower level could be produced that’s an imperative form showing how the dialect is verified to meet those statements. A benefit of creating an imperative lower level (which is human-readable and communicable between tools) which verifies the dialect would be that it may be easier to demonstrate that the verifier actually verifies what the declarative IRDL states. However, adding a third layer/version of IRDL may be too complicated and I’m not sure what situations would benefit from this.

How much does the team plan to work on automatically generating C++ (or possible TableGen/ODS if possible) verification code from IRDL? I believe that would be a killer feature, so I’d love to help craft that or help guide it to improve IRDL.

The “Interp” is not what IRDLSSA is, it is the “interpreter IR” which more what you’re looking for I think. PDL is the declarative IR (using SSA just like @math-fehr proposal).
See here for PDL: 'pdl' Dialect - MLIR
and here for the “interp”: 'pdl_interp' Dialect - MLIR

Here is an example of PDL declarative matching (written “top-down”):

  pdl.pattern : benefit(1) {
    %type = type : i64
    %attr = attribute = 10 : i64
    %attr1 = attribute : %type
    %root = operation {"attr" = %attr, "attr1" = %attr1}
    rewrite %root with "rewriter"
  }

And how it’s lowered to the interp (bottom-up):

$ ./bin/mlir-opt /tmp/pdl.mlir  -convert-pdl-to-pdl-interp
module {
  pdl_interp.func @matcher(%arg0: !pdl.operation) {
    pdl_interp.check_operand_count of %arg0 is 0 -> ^bb2, ^bb1
  ^bb1:  // 7 preds: ^bb0, ^bb2, ^bb3, ^bb4, ^bb5, ^bb6, ^bb7
    pdl_interp.finalize
  ^bb2:  // pred: ^bb0
    pdl_interp.check_result_count of %arg0 is 0 -> ^bb3, ^bb1
  ^bb3:  // pred: ^bb2
    %0 = pdl_interp.get_attribute "attr" of %arg0
    pdl_interp.is_not_null %0 : !pdl.attribute -> ^bb4, ^bb1
  ^bb4:  // pred: ^bb3
    %1 = pdl_interp.get_attribute "attr1" of %arg0
    pdl_interp.is_not_null %1 : !pdl.attribute -> ^bb5, ^bb1
  ^bb5:  // pred: ^bb4
    pdl_interp.check_attribute %0 is 10 : i64 -> ^bb6, ^bb1
  ^bb6:  // pred: ^bb5
    %2 = pdl_interp.get_attribute_type of %1
    pdl_interp.check_type %2 is i64 -> ^bb7, ^bb1
  ^bb7:  // pred: ^bb6
    pdl_interp.record_match @rewriters::@pdl_generated_rewriter(%arg0 : !pdl.operation) : benefit(1), loc([%arg0]) -> ^bb1
  }
  module @rewriters {
    pdl_interp.func @pdl_generated_rewriter(%arg0: !pdl.operation) {
      pdl_interp.apply_rewrite "rewriter"(%arg0 : !pdl.operation)
      pdl_interp.finalize
    }
  }
}

Yes, for now, we will stick with our current design of IRDL-SSA, though we are planning to modify slightly some aspects so we can represent some use cases we have in mind (that we talked by email with Jacques).

So one big aspect of IRDL is that we can reason with the code. If we had another abstraction, it would make this probably way harder. However, having another layer for which we compile to would maybe be nice, if we can gain something from it (either performance, or expressivity, though writing things in IRDL/IRDL-SSA should be the objective).

I am currently interested in getting use cases that people have, to see how much expressive IRDL and IRDL-SSA have to be. Though having at some point a generation to ODS would be fantastic. (We prefer generating ODS than C++ since we do not want to duplicate most of the code ODS has, though we will add custom C++ verifiers). Any help would be welcome, though we haven’t started this yet (we first want to figure out the best way to generate our verifiers, since our algorithm is more complex than the ones used in ODS).

Best,
Mathieu

Your presentation mentioned you had a semi-automatic translation from ODS to IRDL. Looking at your codebase, I believe this is the tblgen-extract tool. Surprising just how much you could get out of ODS with this relatively short code. What’s the non-automatic part?

It sounds like you’d like to leverage the verifiers that ODS can already generate. That makes sense. I guess you’d need to find out how much C++ it can generate as you convert IRDL to ODS.

Do you have the .irdl outputs of the tblgen-extract tool from running on the MLIR ODS dialects? Or are they simple to generate? These might be helpful examples (or instructions) for someone
to use as reference when writing their dialect in IRDL.

Sorry for the delay, I was quite busy the last few days (still am for this week though).

I am currently rebuilding the translation in the repo, so what you are seeing is very minimal, and is almost doing nothing. The previous version I had a better translation, but was entirely in Python (and redefined IRDL in Python). Here is the older version: tablegen-stats/analyze-tblgen/src/analyze_tablegen at main · opencompl/tablegen-stats · GitHub

I don’t think I pushed the files in the repo though, but I should have time next week!

1 Like