tkonolige commented on code in PR #11574:
URL: https://github.com/apache/tvm/pull/11574#discussion_r890339084
##########
src/tir/transforms/common_subexpr_elim_tools.cc:
##########
@@ -762,21 +807,40 @@ std::vector<std::pair<PrimExpr, size_t>>
SyntacticToSemanticComputations(
return a_stream.str().compare(b_stream.str()) < 0;
});
- // For each element in the hashtable
- for (auto elem : sorted_map_items) {
- // We try to see if a semantically equivalent term is already in the
resulting vector
- auto it_found = std::find_if(result.begin(), result.end(),
- [elem](std::pair<PrimExpr, size_t>
already_seen) {
- return EquivalentTerms(already_seen.first,
elem.first);
- });
- // And if so, we increase (by `elem.second`) its count
- if (it_found != result.end()) {
- it_found->second += elem.second;
+ for (const auto& elem : sorted_items_of_table) {
+ PrimExpr norm_elem = NormalizeTerm(elem.first, identify_equiv_terms);
+ // If the normalized term is not already a key in the normalized table
+ auto it_found = norm_table.find(norm_elem);
Review Comment:
if identify_equiv_terms=false then we never find the elem in the table
right? So this would just be copying from one hash table to another (as you
pointed out in my PR). Would it make sense to skip this whole loop and just
copy from the input table into the output vector if identify_equiv_terms=false?
##########
src/tir/transforms/common_subexpr_elim.cc:
##########
@@ -120,6 +120,39 @@ bool
CommonSubexpressionEliminator::CanContainEligibleComputations(const PrimExp
return true;
}
+/*!
+ * \brief Implements an order on pairs (expression,frequency). First attempts
to compare them
+ using the size of the expression. If the is the same, decides
something else still
+ deterministic.
+ * \param a The first pair
+ * \param b The second pair
+ * \return A boolean telling if the first pair `a` comes before the second
pair `b`
+ * \note We need this order to be deterministic in order to have a fully
deterministic pass,
+ * as we will deal with elements that are coming from a hashtable, but
the order in which
+ * they appeared in the hashtable was based on some runtime addresses,
so it can potentially
+ * change with every execution.
+ */
+bool
CommonSubexpressionEliminator::OrderOnExprAndFrequency(std::pair<PrimExpr,
size_t> a,
+
std::pair<PrimExpr, size_t> b) {
+ size_t a_size = CalculateExprComplexity(a.first);
+ size_t b_size = CalculateExprComplexity(b.first);
+
+ // Criteria 1 - Size of the expression comes first
+ // `a` comes before `b` if the size of `a` is bigger
+ if (a_size > b_size) return true;
+ // `a` does NOT come before `b` if the size of `b` is bigger
+ else if (b_size > a_size)
+ return false;
Review Comment:
Can you add braces as per our style guide.
##########
src/tir/transforms/common_subexpr_elim_tools.cc:
##########
@@ -822,17 +886,19 @@ void
InsertElemToSortedSemanticComputations(std::vector<std::pair<PrimExpr, size
decreasing size of the expression) and maintain the vector sorted
while doing so.
*/
void InsertVectorToSortedSemanticComputations(std::vector<std::pair<PrimExpr,
size_t>>* sorted_vec,
- const std::vector<PrimExpr>&
vec_to_add) {
+ const std::vector<PrimExpr>&
vec_to_add,
+ bool identify_equiv_terms) {
if (sorted_vec == nullptr) {
return;
}
for (auto elem_to_add : vec_to_add) {
// See if the current element to add (or an equivalent one) is already
present
// in the sorted vector
- auto it_found = std::find_if(sorted_vec->begin(), sorted_vec->end(),
- [elem_to_add](std::pair<PrimExpr, size_t>
elem) {
- return EquivalentTerms(elem.first,
elem_to_add);
- });
+ auto it_found =
+ std::find_if(sorted_vec->begin(), sorted_vec->end(),
+ [elem_to_add, identify_equiv_terms](std::pair<PrimExpr,
size_t> elem) {
+ return EquivalentTerms(elem.first, elem_to_add,
identify_equiv_terms);
+ });
Review Comment:
Seems like this could still O(N^2)? I'm not quite clear or how this is
called (seems like it is when we are visiting the ast) so it could not b an
issue.
--
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-unsubscr...@tvm.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
