-
Notifications
You must be signed in to change notification settings - Fork 3.5k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
[Simplifier] [Regression] Bounds checks for variable-extent loops not eliminated by simplifier #3770
Comments
Git bisect blames to 75c29c6, #3463. I identified the issue in the PR, 75c29c6#r34683949. @tqchen do you have any ideas on how to cleanly get the simplifier to recognize this pattern? I would propose: diff --git a/src/arithmetic/int_set.cc b/src/arithmetic/int_set.cc
index 0dae8198..e1785125 100644
--- a/src/arithmetic/int_set.cc
+++ b/src/arithmetic/int_set.cc
@@ -375,7 +375,9 @@ class IntervalSetEvaluator :
IntervalSet min_set = this->Eval(val->min_value);
IntervalSet max_set = this->Eval(val->max_value);
--recur_depth_;
- return IntervalSet(min_set->min_value, max_set->max_value);
+ return IntervalSet(
+ min_set->IsEverything() && !val->IsEverything() ? val->min_value : min_set->min_value,
+ max_set->IsEverything() && !val->IsEverything() ? val->max_value : max_set->max_value);
}
IntervalSet VisitExpr_(const IntImm* op) final { which avoids further pessimization of the bounds to |
Great observation! I think the main reason here is that when comparing the bounds, we can try different relaxations. While in our normal cases it is fine to just relax i, in this particular case, the best way is to not do so and makes the bound of r dependent on i. We might want to think about whether or not if we can try both, if we can list the other failure case you mentioned, we can also dig a bit deeper |
specifically to that PR, I think one possible change is not to eagerly resolve the bound that is context depend, but marks it to be so, and then try to recursively simplify min and max after we get a bound that we know is context dependent(so we will do simplification that involves i dependent first, then relax i if necessary) |
@tqchen I don't fully understand your idea. In general, how robust do you think that approach is? One thing I was thinking of adding would be a trivial step in Simplifier which, when visiting a Range(min, extent) node, adds the constraints |
To elaborate, in the example below, we have the following range bound to to the loop vars
Our previous approach eagerly expand the bound of each variable, so we use bind to bind the bound of r, it get relaxed to The proposed idea is to make such expansion lazy. i.e. when we evaluate r, we would return the bound |
@ajtulloch after thinking a bit more about the issue. I think your idea of adding bound constraints may be the best way to go, can you send in a PR? |
ping @ajtulloch can you follow up on this thread:) |
@tqchen sure - are you saying you want something like ajtulloch@ca1088c? |
looks great! Although this is a solution that only works for the exact condition, it fits our purpose and is a pragmatic solution |
Reproduction script:
At 60607ef, the output is:
Where we have an unnecessary bounds check on the inner loop.
at 5217933, the output is:
That is, we avoid any bounds checks in the inner loop. The loop partition pass makes no difference here.
This seems to be a bug in the new simplifier infrastructure? cc @tqchen.
https://github.com/ajtulloch/tvm/tree/fix-cond-in-variable-extent-loo is a fix, but it's quite ugly and there should be a better fix in the simplifier.
The text was updated successfully, but these errors were encountered: