You are viewing a plain text version of this content. The canonical link for it is here.

Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2022/02/10 13:56:51 UTC

[GitHub] [tvm] masahi opened a new issue #10211: [Tracking Issue] TIR-level CSE follow up

masahi opened a new issue #10211:
URL: https://github.com/apache/tvm/issues/10211


   Follow up items after https://github.com/apache/tvm/pull/9482
   
   * Extend the notion of expression equality to take advantage of the purity annotation of TIR intrinsics. See the discussion in https://github.com/apache/tvm/pull/9482#issuecomment-964681835 and below for the motivation.
   * Rewrite the test case using TVMScript. https://github.com/apache/tvm/pull/9482#discussion_r746255687
   * Explore possibilities of refactoring existing TIR utility functions as a special case of the new functionality in the PR. Examples https://github.com/apache/tvm/pull/9482#discussion_r790200526, https://github.com/apache/tvm/blob/e785b26a41d846570616ccab2600416b47db886c/include/tvm/tir/stmt_functor.h#L353-L359
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [tvm] FranckQC edited a comment on issue #10211: [Tracking Issue] TIR-level CSE follow up

Posted by GitBox <gi...@apache.org>.

FranckQC edited a comment on issue #10211:
URL: https://github.com/apache/tvm/issues/10211#issuecomment-1057160549

Hi @yuanfz98

Thanks for your interest in the pass!
That's great, I didn't know that there was an arith::Analyzer which was already able to algebraic simplifications of terms!

When I worked on the CSE pass, I designed it with the idea that it should be easy to extend it for working with terms modulo some equations (by just replacing the EquivalentTerms() function as you did), but I though that we would have to write the normalization procedures on terms for doing that (which would simplify terms within an algebraic structure). And writing such normalization functions is quite a bit annoying to do (it implies deciding on some order terms, sorting them, etc). So I left it for a potential future work. I wasn't even sure that the efforts to implement such normalization procedures would be worth it, because I didn't know how often semantically equivalent computations appear in a TIR program. But as we already have this Simplify() method from arith::Analyzer that does simplification work, we can indeed reuse it without even thinking about it. That's great!

Too bad that arith::Analyzer can't deal with commutativity. I had a quick look at how RewriteSimplifier (which is used by Simplify()) is implemented, and it works by stating rewriting rules that could be applied. They are tried in the order in which they appear with the TVM_TRY_REWRITE() directive.
So instead of computing a normal form in an algebraic structure as I described above, it seems that they try to apply rewriting rules (in a specific order), and they keep applying them, hoping that it will converge to the simplified term. I guess it often does some interesting simplifications, but it is not guaranteed to lead to the simplified term if it exists (unlike a normalization procedure simplifying a term in an algrebraic structure like a Monoid, a Group or a Ring). And without limiting the number of rewriting steps, it would not even be guaranteed to terminate.

The reason why they can't define a commutativity rule is therefore likely because it would create infinite loops of rewriting:
With the rule x+y --> y+x,
the term a+b can be rewritten to b+a, which can again be rewritten to a+b, etc.
Of course, we could limit the rewriting to a fixed number of steps (and they already do it : Simplify() calls the RewriteSimplifier a fixed amount of times, by default 2) to avoid the infinite rewriting, but then this rule for commutativity would be useless. In order to deal with commutativity, one really has to decide an order on subterms and to re-order terms using this order.

In short, for rewriting rules that can be applied again and which lead back to the original term (i.e, A --> B --> A), this strategy of just stating rewrite rules by priority won't work unfortunately.
I guess it's just a limitation of the approach they have used for implementing Simplify() (which was a very good idea for TVM, as they deal with much more than the axioms of algebraic structures!).

Simplify() will do the amount of work that it can do and it will be better than nothing.
Very well spotted @yuanfz98 !

--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [tvm] yuanfz98 commented on issue #10211: [Tracking Issue] TIR-level CSE follow up

Posted by GitBox <gi...@apache.org>.

yuanfz98 commented on issue #10211:
URL: https://github.com/apache/tvm/issues/10211#issuecomment-1061535406


   > Would you like to make a PR for this @yuanfz98 ? It's great that we can have comparisons modulo associativity and modulo distributivity. It's probably pretty rare in practice, but as we can have it for free, it's probably good to take.
   > 
   > Many thanks again for your interest in the pass!
   
   Sure, I will make a PR this week ! 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [tvm] yuanfz98 commented on issue #10211: [Tracking Issue] TIR-level CSE follow up

Posted by GitBox <gi...@apache.org>.

yuanfz98 commented on issue #10211:
URL: https://github.com/apache/tvm/issues/10211#issuecomment-1057078163


   Hello,
   
   For semantic extension, I listed some items:
   - commutativity (identifying for instance (x+y) with (y+x))
   - associativity (identifying for instance (x+y)+z with x+(y+z))
   - distributivity (x*(y+z) and x\*y+x\*z)
   
   We may call tvm/arith library to do the job.
   ```cpp
   bool EquivalentTerms(const PrimExpr& a, const PrimExpr& b) {
     // For now, we just check the syntactic equality, but that could later become a semantic test,
     // for instance identifying computations modulo commutativity (like x+y and y+x), or modulo
     // associativity (like (x+y)+z and x+(y+z)), etc.
     arith::Analyzer analyser;
     PrimExpr a_simplified = analyser.Simplify(a);
     PrimExpr b_simplified = analyser.Simplify(b);
     return EqualTerms(a_simplified, b_simplified);
   }
   
   ```
   
   An example test :
   ```
   def test_semantic_equiv_distributivity():
       i1 = te.var("i1")
       i2 = te.var("i2")
       x = te.var("x")
       y = te.var("y")
       z = te.var("z")
       dtype = "int32"
       buffer = tvm.tir.decl_buffer((50,), dtype)
       body = tvm.tir.SeqStmt(
           [
               tvm.tir.Store(buffer.data, x*(y+z), i1),
               tvm.tir.Store(buffer.data, x*y+x*z, i2),
           ]
       )
   
       mod = tvm.IRModule.from_expr(tvm.tir.PrimFunc([i1, i2, x, y, z], body))
       body = tvm.tir.transform.CommonSubexprElimTIR()(mod)
   
       tvm.transform.PrintIR()(body)
   ```
   
   And I got:
   ```
   [15:10:03] /home/yuan/Coding/compiler/repos/tvm/src/ir/transform.cc:566: PrintIR():
   #[version = "0.0.5"]
   @main = primfn(i1: int32, i2: int32, x: int32, y: int32, z: int32) -> () {
     let cse_var_1: int32 = (x*(y + z))
      {
       buffer: Pointer(int32)[i1] = cse_var_1
       buffer[i2] = cse_var_1
     }
   }
   ```
   
   However I found that the arith system may not be able to do the commutativity (x+y != y+x and x\*y != y\*x). 
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [tvm] FranckQC commented on issue #10211: [Tracking Issue] TIR-level CSE follow up

Posted by GitBox <gi...@apache.org>.

FranckQC commented on issue #10211:
URL: https://github.com/apache/tvm/issues/10211#issuecomment-1057160549

Hi @yuanfz98

Thanks for your interest in the pass!
That's great, I didn't know that there was an arith::Analyzer which was already able to algebraic simplifications of terms!

When I worked on the CSE pass, I designed it with the idea that it should be easy to extend it for working with terms modulo some equations (by just replacing the EquivalentTerms() function as you did), but I though that we would have to write the normalization procedures on terms for doing that (which would simplify terms within an algebraic structure). And writing such normalization functions is quite a bit annoying to do (it implies deciding on some order terms, sorting them, etc). So I left it for a potential future work. I wasn't even sure that the efforts to implement such normalization procedures would be worth it, because I didn't know how often semantically equivalent computations appear in a TIR program. But as we already have this Simplify() method from arith::Analyzer that does simplification work, we can reuse it without even thinking about it. That's great!

Simplify() will do the amount of work that it can do and it will be better than nothing.
Very well spotted @yuanfz98 !

--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [tvm] FranckQC commented on issue #10211: [Tracking Issue] TIR-level CSE follow up

Posted by GitBox <gi...@apache.org>.

FranckQC commented on issue #10211:
URL: https://github.com/apache/tvm/issues/10211#issuecomment-1061119872


   Would you like to make a PR for this @yuanfz98 ?
   It's great that we can have comparisons modulo associativity and modulo distributivity. It's probably pretty rare in practice, but as we can have it for free, it's probably good to take.
   
   Many thanks again for your interest in the pass!


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org

[GitHub] [tvm] FranckQC commented on issue #10211: [Tracking Issue] TIR-level CSE follow up

Posted by GitBox <gi...@apache.org>.

FranckQC commented on issue #10211:
URL: https://github.com/apache/tvm/issues/10211#issuecomment-1035025164


   Thanks @masahi for the summary.
   I'll be more than happy to look into these (in particular item 1 on commoning pure functions and item 3 on refactoring some existing functions as special cases of some news functions from the CSE) as soon as I have some time!
   I know item 1 would make the CSE pass useful for you @masahi, so I'll do that as soon as possible.
   
   Kind regards,
   Franck


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: commits-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org