tvm-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From GitBox <...@apache.org>
Subject [GitHub] [incubator-tvm] masahi commented on a change in pull request #5653: [PatternLang] Convert PatternGrouper to do pre-order, non-recursive analysis
Date Fri, 22 May 2020 22:21:22 GMT

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



##########
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:
       Ah sorry you are right. What I suggested may get a warning from compiler I think (size_t
to int conversion). Moreover, `matcher_->expr_graph_.topological_order_.size() - 1` would
wrap around if `matcher_->expr_graph_.topological_order_` is empty (not sure if this is
possible).  
   
   So I think your original code is safer. Can you undo the last commit? Sorry about this.




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



Mime
View raw message