[GitHub] [tvm] FranckQC commented on pull request #12761: [TIR, analysis] Add expr hash sort in ExprDeepEqual

[GitBox <gi...@apache.org>]

FranckQC commented on PR #12761:
URL: https://github.com/apache/tvm/pull/12761#issuecomment-1247109999

   Hello!
   
   Thank you for the discussion and the PR.
   Just a few thoughts here:
   
   - **1.** Indeed, we knew that `Analyzer::Simplify()` would not deal with commutativity, because it does not implement a normalization procedure that is guaranteed to converge towards the normal form (which would indeed imply sorting sub-terms, etc). Rather, all it does is it tries to "do its best" by rewriting some known patterns, with no guarantees to converge to a normal form. It often works fairly well in practice, but there is no guarantee of being complete (this behaves like a heuristic). However, it really must be correct (i.e, the result of simplify() must rely be equivalent to its input with algebraic laws).
   
   - **2.** Before trying to make `Analyzer::Simplify()` able to deal with with commutativity, it could be useful to **see if people are in practice facing the issue where a lot of redundant computations appear, but written differently due to the commutativity of some operators (like + and *)**. If so, it would be cool to see such concrete examples. To be honest, I don't even think that that many people are turning ON the already existing `bool identify_equiv_terms` of the CSE pass `Pass CommonSubexprElimTIR`, which uses `Analyzer::Simplify()`, which itself does what it can with associativity, neutral elements, etc. These things are probably pretty rare, and commutativity is probably too.
   
   Although I designed the pass in a way that it can potentially identify terms that are equivalent [according to any equivalence relation](https://github.com/apache/tvm/blob/main/src/tir/transforms/common_subexpr_elim_tools.cc#L730-#L750) (instead of just the syntactical equality `ExprDeepEqual`), it might not necessary be often needed in practice. This design that allows to use a custom equivalence relation did not cost much more, so I went for it, in case it could become useful to someone one day for a particular case, so that it would not be needed to write another CSE pass for dealing with that. But I don't necessary think that we should do comparisons modulo equivalence often, and this is why by default `bool identify_equiv_terms` of the CSE pass `Pass CommonSubexprElimTIR` is set to false.
   
   - **3.** If we decide that `Analyzer::Simplify()` (or another new Analyzer!) should deal with commutativity, then it should itself deal with commutativity, rather than baking commutativity into `ExprDeepEqual` which is supposed to be just a deep **syntactical** equality, and is used as such in many many places of TVM's codebase (not just the CSE). So clearly it should not being changed (as @tqchen noted too).
   
   - **4.** Remember that normalizing terms properly in order to deal with commutativity (which indeed includes sorting sub-terms) will likely be computationally expensive, which will make compilation of ML models longer. Actually, just the smaller work that `Analyzer::Simplify()` does is already time consuming, and that's probably why people leave the `bool identify_equiv_terms` of the CSE pass `Pass CommonSubexprElimTIR` set to false (which is the default behavior, as I wrote earlier). It might make people want even less to turn on this `bool identify_equiv_terms`. Perhaps the pseudo-normalization that `Analyzer::Simplify()` does is not too bad as a compromise: still usable in practice when needed (i.e does not take too long), and deals with most simplifications needed.
   
   - **5.** If all the other algebraic properties (associativity, simplification of neutral elements, etc) are still done by the **pseudo**-normalization `Analyzer::Simplify()` that is not guaranteed to find a normal form, I am not sure that the commutativity simplified build on top would be complete -even just in regard to commutativity. Is it worth it to then make `Analyzer::Simplify()` slower while still being incomplete?
   
   Thanks!


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