FranckQC commented on PR #11423: URL: https://github.com/apache/tvm/pull/11423#issuecomment-1136548163
Hi, Thank you for your interest in improving the pass! I haven't worked on the CSE pass for a while, so I am probably a little bit rusty on it, but I think there are quite a few problems with this PR. **1)** The role of this function `SyntacticToSemanticComputations()` is to transform a `ComputationTable` (that is to say, a `std::unordered_map<PrimExpr, size_t, StructuralHash, ExprDeepEqual>`, ie a hashtable mapping `PrimExpr` to `size_t`, using `StructuralHash` for the hashing, and `ExprDeepEqual` for the equality test) into a `vector of std::pair<PrimExpr, size_t>` **where semantically equivalent elements have been merged**. The whole need for this function is due to having collected **syntactical entities** (using an efficient structure for that, the ComputationTable, where it's fast to retrieve an element (in constant time), as it's a hashtable), which latter of course needs to be transformed into a collection (a vector), where equivalent terms (like x+y and y+x) are merged together (and their counters added), which I then call **semantical entities**. This notion of being semantically equivalent could be anything, like identifying terms modulo associativity [(x+y)+z with x+(y+z)], modulo commutatitvity [x+y with y+x], or anything else, with any equivalence relation. It's completely customizable by just changing the `EquivalentTerms()` function. Sure, at the moment, this function `EquivalentTerms()` just calls the syntactical equality `EqualTerms()`, but the whole pass has been written with the idea that we could latter-on replace it with anything else, for making it even more powerful. You can see that the function `SyntacticToSemanticComputations()` that you have changed used to call `std::find_if` with the predicate being precisely this very customizable `EquivalentTerms()`. This is lost with these changes, and it no longer identifies equivalent terms. **2)** There is something else which I don't quite get about your changes. Why do you even bother to transform the ComputationTable (which is a `std::unordered_map<PrimExpr, size_t, StructuralHash, ExprDeepEqual>`) into a `std::unordered_map<PrimExpr, size_t, ExprDeepHashStruct, ExprDeepEqual>`? The lines 753 to 763 (https://github.com/apache/tvm/pull/11423/files#diff-f83c46530e92c628fd309499ceffa32cb2fb0505633ac0e754e2bdef4d518962R753-R762) are basically transforming a hashtable (table) into the exact same hashtable (equiv_computations)). This code is doing nothing. If the pass is really taking too long for many people, I could try to help to improve it, if that's needed. There will necessary be a limit in what we can gain at compile time, as improving the runtime speed (or creating opportunities for it, which CSE is doing) often has a price to pay at compile time. But we can see what we can do, for sure. What do you think? -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
