[GitHub] [tvm] ganler commented on a diff in pull request #14440: [Unity][Graph matching] Clean up undo stack for parent and child nodes properly

["ganler (via GitHub)" <gi...@apache.org>]

ganler commented on code in PR #14440:
URL: https://github.com/apache/tvm/pull/14440#discussion_r1153883716


##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -540,33 +541,48 @@ struct RNode {
 /**
  * \brief This method try to match a real node and a pattern node along with its neighbors.
  */
-static bool try_match(PNode* p, RNode* r, DFPatternMatcher* m,
-                      const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
-                      const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
-  if (p->matched != nullptr && p->matched == r->ptr) return true;  // matched before.
-  if (!m->Match(GetRef<DFPattern>(p->ptr), GetRef<Var>(r->ptr))) return false;
+using UndoStack = std::stack<std::pair<PNode*, RNode*>>;

Review Comment:
   If we have perf consideration, we can do `std::vector` and do `std::copy` in L580.



##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -540,33 +541,48 @@ struct RNode {
 /**
  * \brief This method try to match a real node and a pattern node along with its neighbors.
  */
-static bool try_match(PNode* p, RNode* r, DFPatternMatcher* m,
-                      const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
-                      const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
-  if (p->matched != nullptr && p->matched == r->ptr) return true;  // matched before.
-  if (!m->Match(GetRef<DFPattern>(p->ptr), GetRef<Var>(r->ptr))) return false;
+using UndoStack = std::stack<std::pair<PNode*, RNode*>>;
+static std::optional<UndoStack> try_match(
+    PNode* p, RNode* r, DFPatternMatcher* m,
+    const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
+    const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
+  if (p->matched != nullptr && p->matched == r->ptr) return {};  // matched before.
+  if (!m->Match(GetRef<DFPattern>(p->ptr), GetRef<Var>(r->ptr))) return std::nullopt;
 
-  std::stack<std::pair<PNode*, RNode*>> undo_stack{};
+  UndoStack undo;
 
-  const auto commit = [&undo_stack](PNode* p, RNode* r) {
+  const auto commit = [&undo](PNode* p, RNode* r) {
     // match with each other.
     // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
     if (p->ptr == r->matched) {
       ICHECK_EQ(p->matched, r->ptr);
       return;
     }
-    ICHECK(r->matched == nullptr);
+    // TODO(ganler, masahi): Why this condition can fail?

Review Comment:
   In practice they won't, it's like a debugging check that I did not remove. Thanks for optimizing it.



##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -540,33 +541,48 @@ struct RNode {
 /**
  * \brief This method try to match a real node and a pattern node along with its neighbors.
  */
-static bool try_match(PNode* p, RNode* r, DFPatternMatcher* m,
-                      const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
-                      const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
-  if (p->matched != nullptr && p->matched == r->ptr) return true;  // matched before.
-  if (!m->Match(GetRef<DFPattern>(p->ptr), GetRef<Var>(r->ptr))) return false;
+using UndoStack = std::stack<std::pair<PNode*, RNode*>>;

Review Comment:
   Consider `std::stack<std::pair<PNode*, RNode*>, std::vector<std::pair<PNode*, RNode*>>>` for cache-friendliness.



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