[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request #5653: [PatternLang] Convert PatternGrouper to do pre-order, non-recursive analysis
mbrookhart commented on a change in pull request #5653:
URL: https://github.com/apache/incubator-tvm/pull/5653#discussion_r429477690
##
File path: src/relay/ir/dataflow_matcher.cc
##
@@ -432,26 +432,39 @@ class PatternGrouper : protected MixedModeVisitor {
const std::vector& 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_ =
-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 pre_partitioned;
+for (size_t i = matcher_->expr_graph_.topological_order_.size(); i != 0;
--i) {
+ size_t index = i - 1;
Review comment:
No worries! Undid it.
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
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request #5653: [PatternLang] Convert PatternGrouper to do pre-order, non-recursive analysis
mbrookhart commented on a change in pull request #5653:
URL: https://github.com/apache/incubator-tvm/pull/5653#discussion_r429468918
##
File path: src/relay/ir/dataflow_matcher.cc
##
@@ -432,26 +432,39 @@ class PatternGrouper : protected MixedModeVisitor {
const std::vector& 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_ =
-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 pre_partitioned;
+for (size_t i = matcher_->expr_graph_.topological_order_.size(); i != 0;
--i) {
+ size_t index = i - 1;
Review comment:
This is something I was too lazy to debug.
If I iterate over something of size 4 with the constraint `i > 0`, I get 3
iterations with i = 3, 2, 1
If I use the line you gave me, I get 5 iterations, with i = 3, 2, 1, 0,
18446744073709551615 as the size_t underflows.
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
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request #5653: [PatternLang] Convert PatternGrouper to do pre-order, non-recursive analysis
mbrookhart commented on a change in pull request #5653:
URL: https://github.com/apache/incubator-tvm/pull/5653#discussion_r429471161
##
File path: src/relay/ir/dataflow_matcher.cc
##
@@ -432,26 +432,39 @@ class PatternGrouper : protected MixedModeVisitor {
const std::vector& 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_ =
-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 pre_partitioned;
+for (size_t i = matcher_->expr_graph_.topological_order_.size(); i != 0;
--i) {
+ size_t index = i - 1;
Review comment:
Ah, nvm, I see. Of course i >=0, it's a size_t. I need to use an int.
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
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request #5653: [PatternLang] Convert PatternGrouper to do pre-order, non-recursive analysis
mbrookhart commented on a change in pull request #5653:
URL: https://github.com/apache/incubator-tvm/pull/5653#discussion_r429468918
##
File path: src/relay/ir/dataflow_matcher.cc
##
@@ -432,26 +432,39 @@ class PatternGrouper : protected MixedModeVisitor {
const std::vector& 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_ =
-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 pre_partitioned;
+for (size_t i = matcher_->expr_graph_.topological_order_.size(); i != 0;
--i) {
+ size_t index = i - 1;
Review comment:
This is something I was too lazy to debug.
If I iterate over something of size 4 with the constraint `i > 0`, I get 3
iterations with i = 3, 2, 1
If I use the line you gave me, I get 5 iterations, with i = 3, 2, 1, 0,
18446744073709551615 as the size_t underflows.
I can't figure out _why_ that line screws up
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
