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:
us...@infra.apache.org
