[GitHub] [incubator-tvm] masahi commented on a change in pull request #5653: [PatternLang] Convert PatternGrouper to do pre-order, non-recursive analysis

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

masahi commented on a change in pull request #5653:
URL: https://github.com/apache/incubator-tvm/pull/5653#discussion_r429449194



##########
File path: src/relay/ir/dataflow_matcher.cc
##########
@@ -432,26 +432,39 @@ class PatternGrouper : protected MixedModeVisitor {
   const std::vector<Group>& GroupMatches(const DFPattern& pattern, const Expr& pre) {
     groups_ = {Group()};
     gid_assignments_.clear();
-    visit_counter_.clear();
 
     pattern_ = pattern;
     pattern_graph_ = CreateIndexedGraph(pattern_);
     auto matcher = DFPatternMatcher(pre);
     matcher_ = &matcher;
-    this->VisitExpr(pre);
+    this->VisitExprs();
     return this->groups_;
   }
 
  protected:
-  using ExprVisitor::VisitExpr_;
-  void VisitLeaf(const Expr& pre) override {
-    if (matcher_->Match(pattern_, pre)) {
-      CreateGroup(pre);
-    }
-  }
-  void VisitExpr_(const FunctionNode* op) override {
-    if (op->attrs->dict.count(attr::kPartitionedFromPattern) == 0) {
-      ExprVisitor::VisitExpr_(op);
+  /* \brief Iteratively traverse the Expression in pre-order to find subgraphs
+   *
+   * If we traverse the graph in post-order, we can run into situtations where a small subgraph will
+   * match the pattern. Due to options like AltPattern, a larger subgraph with more nodes later in
+   * the graph may also match the pattern. With post-order traversal, we mark the smaller subgraph
+   * as matched and fail to catch the larger subgraph. This problem is fixed by using pre-order
+   * traversal.
+   */
+  void VisitExprs() {
+    std::unordered_set<Expr, ObjectHash, ObjectEqual> pre_partitioned;
+    for (size_t i = matcher_->expr_graph_.topological_order_.size(); i != 0; --i) {
+      size_t index = i - 1;

Review comment:
       Having both `i` and `index` seems redundant.




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

For queries about this service, please contact Infrastructure at:
users@infra.apache.org