[GitHub] [tvm] Lunderberg commented on pull request #12942: [Arith][Refactor] Extract And/Or/Not handling from RewriteSimplifier

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

Lunderberg commented on PR #12942:
URL: https://github.com/apache/tvm/pull/12942#issuecomment-1262778477

   @tqchen Thank you, and I definitely agree that any changes to RewriteSimplifier should be done with care, because of how foundational it is, but also any improvements to it may yield improvements across the codebase.  I didn't do so for this PR, because it isn't intended to alter any functionality, but any that do are going to be behind feature flags to avoid incidental breakage or unnecessary CPU usage.
   
   > For example, in some of our cases we have recursive calls into simplify that further triggers other rewrite simplifications of the expressions within the boolean expr (TVM_TRY_RECURSIVE_REWRITE), so refactoring booleaning simplfication into a separate function may not retain that deep recursive behavior.
   
   Regarding the `TVM_TRY_RECURSIVE_REWRITE` functionality, the behavior was considered and should be preserved by this refactor.  The recursive rewrites used for boolean expressions are to move a `Not` to be internal to `Or`/`And`, regardless of the depth of the or/and chain contained in the `Not`.  The refactor allows a `Not` to be recursively propagated into the chain, using `TVM_TRY_RECURSIVE_REWRITE`, recursively visiting the And/Or as needed.
   
   This should also improve the performance.  On the main branch, the expression `!(a && (b || c))`, the expressions `a` is visited twice, and both `b` and `c` are visited three times, even though I think only the first visit is necessary.  I wrote out and validated the sequence of visits to convince myself, shown below.
   
   <summary>
   Sequence of visits on main branch
   
   <details>
   1. Visit `!(a && (b || c))`
       1. Visit `a && (b || c)`
           1. Visit `a`
           2. Visit `b || c`
               1. Visit `b`
               2. Visit `c`
               3. Return `b || c`
           3. Return `a && (b || c)`
       2. Recursive rewrite, `!(a && (b || c))` becomes `(!a) || (!(b||c))`
       3. Visit `(!a) || (!(b||c))`
           1. Visit of `!a`
               1. Visit `a`
               2. Return `!a`
           2. Visit `(!(b||c))`
               1. Visit `b||c`
                  1. Visit `b`
                  2. Visit `c`
                  3. Return `b||c`
               2. Recursive rewrite, `!(b||c)` becomes `(!b) && (!c)`
               3. Visit `(!b) && (!c)`
                  1. Visit `!b`
                     1. Visit `b`
                     2. Return `!b`
                  2. Visit `!c`
                     1. Visit `c`
                     2. Return `!c`
                  3. Return `(!b) && (!c)`
               4. Return `(!b) && (!c)`
           3. Return `(!a) || ((!b) && (!c))`
       4. Return `(!a) || ((!b) && (!c))`
   </details>
   </summary>    
      
   <summary>
   Sequence of visits after PR#12942
   
   <details>    
   1. RW, Visit `!(a && (b || c))`
       1. RW, Visit `a && (b || c)`
           1. RW, Visit `a`
           2. RW, Visit `b || c`
               1. RW, Visit `b`
               2. RW, Visit `c`
               3. Return `b || c`
           3. Return `a && (b || c)`
       2. Delegate to BoolRW 
       3. Recursive rewrite, `!(a && (b || c))` becomes `(!a) || (!(b||c))`
       4. BoolRW, Visit `(!a) || (!(b||c))`
           1. BoolRW, Visit `!a`
           2. BoolRW, Visit `(!(b||c))`
               1. BoolRW, Visit `b||c`
               2. Recursive rewrite, `!(b||c)` becomes `(!b) && (!c)`
               3. BoolRW, Visit `(!b) && (!c)`
                  1. Visit `!b`
                  2. Visit `!c`
                  3. Return `(!b) && (!c)`
               4. Return `(!b) && (!c)`
           3. Return `(!a) || ((!b) && (!c))`
       5. Return `(!a) || ((!b) && (!c))`
   </details>
   </summary>
   
   > For extra caution, it might be helpful to simply introduce a bit of duplication of rules and have an independent implementation here.
   
   In the short-term, I agree that a copy/paste of the relevant portions would be the safest, and would minimize the scope of any changes.  In the long-term, I'd worry about having multiple duplicate implementations, whether improvements/bugfixes in one get propagated over to the other, or the impact of requiring a developer to know which of multiple related implementations should be called.
   
   > Additionally, is it OK to simply invoke the full simplification instead?
   
   For the test cases I've run, it is okay to use the full simplification rather than limiting it to boolean expressions.  That said, the test cases were designed to test the functionality being added, and so I'm not sure the final cost of the additional visits.


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