[GitHub] [tvm] FranckQC commented on pull request #10663: [TIR] CSE-TIR Pass - More deterministic behavior

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

FranckQC commented on pull request #10663:
URL: https://github.com/apache/tvm/pull/10663#issuecomment-1073440581


   Hi,
   
   Sorry I couldn't discuss this with you last Thursday/Friday. Thanks for improving the CSE!
   
   Yes, indeed, iterating through the hash table will not necessary lead to accessing its elements always in the same order. That's because the iteration order depends on the hashes (and we use `structural_hash` for that), which themselves are based on pointers, so different run will give different addresses, which will give different hashes, and thus a different order in which elements are accessed.
   
   I guess it is not an issue as far as the CSE is concerned, because after producing this hashtable, we use it to produce a vector of semantic entities (which are pairs <expr, count>).
   The main loop of the CSE will later iterate through the elements of this vector.
   But before that, this vector gets sorted by the size (called "complexity") of the expression (the first component).
   
   So the order of the end result (the vector) is non-deterministic only for elements with the same size / complexity, for which it does not matter (again, only for the CSE) in which order we common them. (i.e. it should not add or remove opportunities for commoning more later). Said differently, this non-determinism should appear for orthogonal choices.
   I guess as in:
   ```
   Mem[i1] = (a+b)+ (c+d);
   Mem[i2] = a+b;               // We can common this one before or after
   Mem[i3] = c+d;               // this one, it does not matter for the CSE
   Mem[i4] = (a+b) + (c+d) + e;
   ```
   
   for which we could produce: 
   
   ```
   let cse_var_2 = a+b in
   let cse_var_3 = c+d in
   let cse_var_1 = cse_var_2 + cse_var_3 in
   Mem[i1] = cse_var_1;
   Mem[i2] = cse_var_2 in
   Mem[i3] = cse_var_3 in
   Mem[i4] = cse_var_1
   ```
   
   Or the alternative version were (c+d) gets introduced before (a+b).
   
   I did not think that having this level of non-determinism would be an issue, but you're clearly right that its better to always produce exactly the same resulting TIR code, that just makes testing easier.
   Your way of making it deterministic (by first transitioning the hashtable into an array, which you then sort using the actual syntax that the expressions represent) is perfectly fine to me.
   
   According to the doc about `structural_hash` ( here : https://tvm.apache.org/docs/reference/api/python/ir.html ), it seems an alternative could have been to set `map_free_vars` to true, as that's the reason the hashes use pointers. If that was the only place were addresses are used in the hashes, it should make everything deterministic too. I'll see if that works too, out of curiosity.
   
   Many thanks for having spotted that and for having fixed it!
   
   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