[GitHub] [tvm] masahi commented on a change in pull request #9482: Implementation of Common Subexpression Elimination for TIR

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

masahi commented on a change in pull request #9482:
URL: https://github.com/apache/tvm/pull/9482#discussion_r796196735



##########
File path: src/tir/transforms/common_subexpr_elim_tools.h
##########
@@ -0,0 +1,216 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+/*!
+ * \file common_subexpr_elim_tools.h
+ * \brief Interface of analysis tools and utility functions used
+           by the Common Subexpression Elimination (CSE) pass.
+ */
+
+#ifndef TVM_TIR_TRANSFORMS_COMMON_SUBEXPR_ELIM_TOOLS_H_
+#define TVM_TIR_TRANSFORMS_COMMON_SUBEXPR_ELIM_TOOLS_H_
+
+#include <tvm/runtime/container/string.h>
+#include <tvm/tir/analysis.h>  // For the ExprDeepEqual analysis
+#include <tvm/tir/expr.h>
+#include <tvm/tir/expr_functor.h>
+#include <tvm/tir/stmt.h>
+#include <tvm/tir/stmt_functor.h>  // For the class StmtExprVisitor
+
+#include <unordered_map>  // For the hashtable datatype
+#include <vector>
+
+#include "../../../3rdparty/dmlc-core/include/dmlc/optional.h"
+
+namespace tvm {
+namespace tir {
+
+/*!
+ * \brief A table of computations is a hashtable which associates to each expression being computed
+          a number (which is the number of time that it is computed)
+					It is important to note that the hash used is a StructuralHash (and not an ObjectPtrHash)
+					as we need to hash similarly deeply equal terms.
+					The comparison used is ExprDeepEqual, which is stricter than StructuralEqual (as it does
+					not do variables remapping), so it is compatible with StructuralHash (intended to be used
+					with StructuralEqual).
+ */
+using TableOfComputations = std::unordered_map<PrimExpr, size_t, StructuralHash, ExprDeepEqual>;
+
+/*!
+ * \brief A cache of computations is made of a pair of two hashtables, which respectively associate
+          to each statement or expression of the program its table of computations. Its purpose is
+          to avoid the CSE pass from recomputing repeatedly the same tables of computations.
+ */
+struct CacheOfComputations {
+  // Part of the cache for statements
+  // It maps each known statement to its table of computations
+  std::unordered_map<Stmt, TableOfComputations, ObjectPtrHash, ObjectPtrEqual>
+      cache_stmt_table_computations_;
+
+  // Part of the cache for expressions
+  // It maps each known expression to its table of computations
+  std::unordered_map<PrimExpr, TableOfComputations, ObjectPtrHash, ObjectPtrEqual>
+      cache_expr_table_computations_;
+};
+
+/*!
+ * \brief Visitor which returns in a hashtable the (syntatic) computations done by an expression
+          or by a statement.
+ * \note Computations here are considered syntactically, meaning that semantically equivalent
+          computations that are not syntactically the same are not merged together.
+ */
+class ComputationsDoneBy : public StmtExprVisitor {

Review comment:
       Ah ok, if these functions / classes are intended to be reusable and not internal to `common_subexpr_elim_tools.cc`, I'm fine with that. I'm more of a "minimize public API" camp.




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