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
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.
