I prefer option B. It does imply extra complexity in compiler passes, but it’s more general. One advantage of it is that more assertions can be added to an existing variable (for example, by some compiler analysis).
I definitely prefer option B. Although I understand Haichen’s point that A is more flexible, I think that adding complexity for users should be avoided. A user might expect shape variables to naturally be non-negative and requiring them to specify it will trip up many new users.
Thanks for everyone’s discussion. @haichen@yzhliu do you think if you can go with option B? At the moment it seems that technically option B is easier for us to get in right now and has better composibility and future compatibility as @kparzysz
If the wrapper can be applied to any expression, then there will be additional complexities in simplifier etc.
If we restrict the wrapper to var, likely we won’t add additional complexity to passes as well, because the expression will always be transformed as a whole
Hi, I’m new here, though I’ve been involved with similar issues in other compilers. So please allow me to ask some potentially stupid questions:
Doesn’t B also complicate simplification? A rule like X - X -> 0 should presumably also apply to e.g. X - assert_lower_bound(X, 0). Or is the idea that X could never appear both with and without its assertion? These kind of wrapper no-op-ish ops generally lead to trouble.
Aren’t we going to be sad to have this encoded as lower_bound and upper_bound fields on an op? Would be nice to have an object that represents a set of constraints and allows queries like “is X >= Y?” and the implementation can right now be just lower_bound and upper_bound but is easy to modify later, also without changing the API, or at least not much.
If only vars can be tagged and I want to do a replacement of X -> X’ + 1 as part of some optimization, then I can’t just replace uses of X with the new value X’ + 1, because that might create an instance like assert_foo(X’ + 1) which would be malformed. I’d have to figure out how to push the + 1 (or whatever it is) through the assertion and update it correspondingly. Is this a cause for concern?
If we wrap assertions on ops/vars, then where do I put a constraint like X >= Y for two vars, does that wrap the X op or the Y op or both or neither? Or are we not looking to support that kind of constraint (for now)?
A question I have here is what the semantics are if the assertion is not satisfied. Is that undefined behavior and anything could happen? Might an error be issued? If so, is that error guaranteed to be issued? If so, is there an ordering guarantee between two failing asserts of which one is checked first? “assert” suggests a guarantee of an error being issued. Is there a sanitizer mode where the errors are guaranteed, if not otherwise? (in my experience this is a difficult part of this kind of thing)
I understand the need to tag these constraints to parameters to functions, where inside the function you don’t know what values will come in. The examples here are things like a var bound to a loop with a defined range. Couldn’t any optimization interested in that var look up its definition and analyze from that what the range is? (I’m sure I’m missing something here)
Bjarke
Thanks for sharing insights. These are great points.
First of all, we do have alternative ways to add additional constraints like X>= Y in the context via AssertStmt, the only drawbacks is that we do need to populate these constraints of vat in the context before we perform simplification. The proposals only sought to complement the existing approaches.
Also the main usecase is to tag the non-negative property of a input shape variable(rows of a matrix). In the above example, the nonnegative info about variable n. and such information is not yet available from loop ranges(although we can add asserts to provide context dependent information-proposal 1 in the first post)
In terms of the mixing asserts with vars without asserts. Most vars we care about are shape variables of input tensors, if we wrap them
during input argument creation time, all the related expression using the var are going to be wrapped by the asserts, there won’t be a mixture of vars that are wrapped and vars that are not(although such form is a valid IR).
If we end up replacing the var by an expression (the assert(X+1) case), the assertion is still valid, but we just don’t construct the wrapping in the first place if it is not a var, so it is mainly a convention to avoid over complicated nested assertions. So the proposal is to allow asserts about expressions as valid IR, but adopts the convention to not construct these wrapping at the first place
Finally, in terms of the semantics, we could explicitly translate these assertions to a runtime assertion, or ignore them and treat it as undefined
Thanks for the background, I have a better idea about it now.
*** Option A
Setting the range on the var flows the information in effect backwards in time, since it is set for the lifetime of the var, also before calling placeholder(). Is there any way that this could go wrong? E.g. maybe someone checks to see if the n is negative, before creating the shape, and halts the program if it is (or if-then-else it out or some such), and then that gets optimized out when it shouldn’t because n is known to be non-negative at a later point in time and that is flowed backwards in time?
*** Option B
I understand the premise to be that by letting placeholder() wrap its array sizes internally, the user will be automatically using the wrapped n. If the user accesses n only through the shape, then I follow how that works. At the top here, in the first post, I see “floormod(i, n)” seemingly using the original n, not a wrapped one. Is that a cause for concern?
If you expect that substitutions will violate the invariant that only vars are wrapped, I think the statement would be that 1) substitutions of that kind shouldn’t be done, or 2) such substitutions should always remove or fix up any wrappers, or 3) the compiler should handle non-vars that are wrapped just fine (which was what we’re trying to avoid) or 4) such cases just won’t be optimized as well. Are we aiming at one of these possibilities with option B, or another possibility that I missed?
I don’t know TVM well enough to have a real opinion here, but I have seen before that no-op-ish wrappers tend to lead to trouble in optimizing compilers.
For what happens when the condition is violated, I’d just point out that it’s a huge difference what is guaranteed. Guaranteeing an in-order error makes everything side-effecting and can be a big burden that prevents optimizations (e.g. dead code elimination - if the error is guaranteed, then you still have to check error cases for ops that you don’t need the value of otherwise) - I’m told this is a big burden for Java compilers. On the other hand it’s confusing if an error is not reported, or only sometimes reported, though that’s how llvm.assume works anyway (https://llvm.org/docs/LangRef.html#llvm-assume-intrinsic). In XLA you might note that most ops are defined even for non-sense input, just so that there is never an error condition, thus getting around this whole question, though that probably isn’t an approach that they can keep up indefinitely. I’d like to suggest some sort of hybrid solution here, maybe along with a sanitizer, but I don’t know TVM well enough to really have an opinion.
Good summary of the discussion
Option A: The main problem of allowing mutating an IR nodes is that sometimes we might have context dependent info like if_then_else. It is also an explicit design choice we made in general(make nodes immutable for other gains – shallow copy, thread-safety).
Option B: My current thought is that compiler will handle non-var wrapping cases, but 4) such cases just won’t be optimized as well. Note that we do have the alternative to create a context constraint instead of wrapping them in an expression(which I think should be used for nested expression), i.e.
AssertStmt(n >= 0,
for (i) {
result = floordiv(i, n)
})
The context assertion enjoys the benefit of not having to created a nested assertion op(makes the expression easier for simplification).
The main challenge of this alternative approach is that sometimes developers are not careful enough to populate the context, or if these expression are in a fragment of DSL(in which case we only have result = floordiv(i, n)) rather than the entire IR. Only constructing such wrapping expression on vars seems to be a good trade-off.
In terms of in-order error, I don’t think we want to guarantee that. As a matter of fact, in most cases the shape of tensors should be positive and the only cases the error occur is when the programmer did something wrong, and the order of error does not matter.
Whatever approach we take, it will complicate optimizations. The focus here is to add the functionality to express conditions in such a way that this complication is added once, and is not compounded with each additional type of condition.
Points to consider:
- The conditions should not be needed for correctness, they should only be there to aid optimizations. In particular, if the conditions are dropped we should still generate correct code (although possibly less efficient).
- Each optimization that generates new variables should be responsible for correctly maintaining the conditions. In particular, code that replaces variables should handle their enclosing conditions.
- Conditions should be context-sensitive, i.e. an instance of a condition should apply to the particular occurrence of a variable, not to all occurrences of it.
- There should be a single builtin that can contain all possible conditions, e.g.
builtin_condition(x, non_negative, multiple_of(8), ...). This is to avoid expressions likecondition1(condition2(x)).
I think option B puts too much limitation that it might be only good for asserting non-neg property. But I can imagine that we need more properties on shapes to perform other optimization. At that time, we will be back on this discussion again whether we add another intrinsic or we will add property to var. For example, people may want to add likely property to a var that expresses the likely size of a shape as a hint to AutoTVM. Allowing var to have properties will benefit in long term, IMO.
I agree with @kparzysz that having such builtin_condition or other helper function for developers to easily add properties to var is good for usability.
Let me try to summarize the point. Seems we are converging to a common ground.
I think currently the closest thing possible would be add an assert_expr that assets the non-negative condition to the expression as well as other conditions(chained by and). Alternatively, we can go for the assert_lower_bound, which is more specialized.
assert_expr(x, x>=0)
@haichen would you like to volunteer to summarize, send a formal RFC and land this feature? It would be relevant to dynamic shapes
Sure, I’ll follow up with a RFC.
Another requirement is we may need a reduction infor in Variable, since we’ve seen we need to identify if axes are reduce or not in passes. Also orignal Halide has reduce domain infor, we may just need a boolean flag.
I think the requirement’s valid.
MLIR uses solution similar to 2&3: index type It also describes some design rationale and the relation with its affine dialect.
Thinking about the problem a bit more during the holiday. Now that we have a flexible Object system whichi supports runtime dynamic checks, one variant of Option A might start to become interesting.
Option A+
class IterVarNode : public Variable {
public:
Range dom;
static constexpr const char* _type_key = "IterVar";
}
Instead of directly enforcing the variable types on the Variable, we could build extension of Var that contains additional information. In order for the visitor/functor to work for this types, we just need to set the default dispatching strategy to
R VisitExpr_(const IterVarNode* obj, Args... args ) {
return VisitExpr_(static_cast<const Variable*>(obj), std::forward<Args>(args)...);
}
So all the visitors that are based on the functor will work out of the box. This will allow us to introduce a few variants of Vars that can add additional information, while not having to change the rest part of the codebase to accomodate them(things will fallback to normal var) and perhaps it could be complementary to option B
1 Like
I’m know I’m quite late to this discussion, but is there a way to embed bound information on variables now.
I know that we have tvm.tir.SizeVar which defines a bound of >= 0, but couldn’t find a way to directly embed bound information on variables without writing a pass through TIR.
Thanks,
Anirudh
So can we embed bound infomation into te.var now? Maybe assert_stmt?
using assert_stmt is a valid approach
OK. So can you give an example about using assert_stmt to embed bound infomation? And can this infomation be propagated to simplfy codegen? Thank you so much