Skip to content
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

[ARITH] Simplifier Improvement #2173

Closed
sgrechanik-h opened this issue Nov 26, 2018 · 5 comments
Closed

[ARITH] Simplifier Improvement #2173

sgrechanik-h opened this issue Nov 26, 2018 · 5 comments

Comments

@sgrechanik-h
Copy link
Contributor

  • The simplifier does not simplify (y - x) - y. Interestingly, (y - x) - y < 0 is simplified, but (y - x) - y > 0 is not:
    x = tvm.var('x')
    y = tvm.var('y')
    print(tvm.ir_pass.Simplify((y - x) - y))
    print(tvm.ir_pass.Simplify((y - x) - y > 0))
    print(tvm.ir_pass.Simplify((y - x) - y < 0))
    
    Output:
    ((y - x) - y)
    (0 < ((y - x) - y))
    (0 < x)
    
    CanonicalSimplify works well on this example though.
  • The simplifier rewrites (3*x + y)/3 into x + (y/3). Since tvm uses C/C++ truncated division instead of flooring or euclidean division, this is wrong (e.g. x = 1, y = -1). Recently there was a related issue here. However, instead of disabling another simplification rule I would suggest discussing another option: using Euclidean division in TVM, since the Euclidean definition has some advantages regarding program transformations, and it was originally used in Halide.
@tqchen
Copy link
Member

tqchen commented Nov 26, 2018

Some of these are not as problematic, because they can be caught by CanonicalSimplify.
Eventually, we will need a new simplifier that takes all of these into consideration, and do reasonable integer set analysis (hopefully in the next release cycle).

@tqchen tqchen changed the title [TVM] A couple of problems with the simplifier [ARITH] Simplifier Improvement Nov 26, 2018
@tqchen
Copy link
Member

tqchen commented Nov 27, 2018

To follow-up on Euclidean divisions, I agree that euclidean div is nice for analysis. The main problem of Euclidean div generation is it is relatively hard to generate efficient low-level code for it, and the developer might make implicit assumption of the semantics of div to be same as LLVM/C. Unless we have a strict analysis of positiveness of the index, in which case the definition of division won't matter. So the case now is we would just stick to trunc div as it is close to machine code, improve the integer set analysis to cover the range of the variable and then revisit the issue later

@sgrechanik-h
Copy link
Contributor Author

By the way, turned out the HalideIR submodule hasn't been updated for a while, so the fix of @xqdan is not in TVM yet. (Unfortunately it doesn't solve my case of incorrect simplification anyway).

I would still vote for Euclidean division, and concerning its problems, I would suggest the following plan:

  • Rename Div and Mod in IR to EuclideanDiv and EuclideanMod
  • Add explicit functions like euclidean_div, truncated_div, etc into the python interface. The ordinary / and % operators should be translated into expressions checking that their arguments are non-negative and throwing an exception or something like that when they are negative.
  • Add a pass rewriting EuclideanDiv in terms of truncated div. As a result, select expressions will appear, but I think they can be effectively eliminated in most cases even with the existing integer set analysis and simplification. Of course, we have to think about some kind of performance regression testing before doing this.

If we choose truncated division, then we should do something with the HalideIR simplifier, because it is used everywhere and is heavily relied upon, and we cannot just replace it with CanonicalSimplify yet.

@tqchen
Copy link
Member

tqchen commented Nov 29, 2018

Given that truncate div is the current way and the limited simplification works fine for now, I propose us to do the following thing, from pragmatic point of view:

  • Upgrade the integer set analysis to cover most cases on positiveness testing
  • Keep Div/Mod as truncated version as developers in c++/LLVM are more familar with this semantics(no surprise principle).
    • If necessary, I wont mind disabling some of the rules temporary, given that the div rules in the index simplification do not play an important role for perf.
  • Add CeilDiv or EuclideanDiv to the IR.
  • Do the truncated rewriting pass as @sgrechanik-h suggested.

Since this would be a major change to the analysis pipeline, we might want to do it in the next release cycle.

@tqchen
Copy link
Member

tqchen commented Feb 18, 2019

move to #2588

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants