You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by "masahi (via GitHub)" <gi...@apache.org> on 2023/03/28 21:54:51 UTC
[GitHub] [tvm] masahi opened a new pull request, #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
masahi opened a new pull request, #14417:
URL: https://github.com/apache/tvm/pull/14417
Graph pattern matching uses `std::map` and `std::set` keyed on pointers, which leads to non-deterministic matching result. This PR removed all non-determinism.
For example, consider matching against QKV projection before attention. Given a sequence of bindings,
```
with R.dataflow():
lv0 = R.matmul(x, w0)
lv1 = R.matmul(x, w1)
lv2 = R.matmul(x, w2)
...
```
and patterns,
```
with PatternContext() as ctx:
inp_pat = wildcard()
Q_weight_pat = wildcard()
K_weight_pat = wildcard()
V_weight_pat = wildcard()
matmul1 = is_op("relax.matmul")(inp_pat, Q_weight_pat)
matmul2 = is_op("relax.matmul")(inp_pat, K_weight_pat)
matmul3 = is_op("relax.matmul")(inp_pat, V_weight_pat)
```
intuitively I expect the following matching result:
```
Q_weight_pat - w0
K_weight_pat - w1
V_weight_pat - w2
```
But since three matmul patterns are independent of each other, each pattern can match any of three matmuls in the bindings. And since graph pattern matching processes patterns and variables in the bindings in a non-deterministic order, matching result becomes non deterministic as well.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152471948
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
ok :) I'll share my thought in the meantime.
Looking at an example in https://github.com/apache/tvm/blob/unity/tests/python/relax/test_dataflow_pattern.py#L540-L545, I cannot imagine how one would use `start_hint` in practice. Here, you wrote the input mod by hand, so you know `dfb.bindings[0].var` is associated to the "left" branch of the CBRx2. But in general, we don't have such information, especially in e2e scenarios for real world models.
Even if there was a good use case for it, I claim that it doesn't justify making API and the implementation more complicated (two additional params + `try_match` loop on parants). If one has such advanced knowledge of model structure and variables, they may as well have a different way to match & extract such subgraph.
--
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
[GitHub] [tvm] ganler commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152460549
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
Sorry, I need some time to illustrate but my flight is taking off now. I will get you back probably after 8 hours. 🥲
--
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
[GitHub] [tvm] masahi commented on pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on PR #14417:
URL: https://github.com/apache/tvm/pull/14417#issuecomment-1490049917
Just hit an interesting bug in the graph matcher.
The following fake QKV projection mod and pattern should not match. Without this PR I get segfault. With this PR, it incorrectly matches with the result
`{*: x2, *: w1, Op(relax.matmul)(*, *): lv1, *: w2, Op(relax.matmul)(*, *): lv2, Op(relax.matmul)(*, *): lv0, *: w0}`
```
@R.function
def main(...) -> R.Tensor:
with R.dataflow():
lv0 = R.matmul(x1, w0)
lv1 = R.matmul(x2, w1)
lv2 = R.matmul(x2, w2)
...
with PatternContext() as ctx:
inp_pat = wildcard()
...
matmul1 = is_op("relax.matmul")(inp_pat, Q_weight_pat)
matmul2 = is_op("relax.matmul")(inp_pat, K_weight_pat)
matmul3 = is_op("relax.matmul")(inp_pat, V_weight_pat)
```
I'll work on a fix in a separate PR.
--
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
[GitHub] [tvm] ganler commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1153615575
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
BTW, also to explain why I was using the code style of `CONSTANT logic_op VAR`. This is just a practice to avoid writing `VAR = CONSTANT` which causes silent logic errors. But yeah it is nice to normalize the code style.
--
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
[GitHub] [tvm] ganler commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152449966
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
I see. Because the constraint or relation between nodes may or may not be single-way so in the beginning I made it bidirectional such that the pattern can be matched as long as you can let any node of the matched subgraph be start hint and get the pattern matched eventually. Specifying certain matching order definitely makes the code logic and debugging easier but I am afraid it also cuts the flexibility in some way. Not sure if it is worth to have some flexibility or if we can keep them both.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152471948
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
ok :) I'll share my thought in the meantime.
Looking at an example in https://github.com/apache/tvm/blob/unity/tests/python/relax/test_dataflow_pattern.py#L540-L545, I cannot imagine how one would use `start_hint` in practice. Here, you wrote the input mod by hand, so you know `dfb.bindings[0].var` is associated to the "left" branch of the CBRx2. But in general, we don't have such information, especially in e2e scenarios for real world models.
Even if there was a good use case for it, I claim that it doesn't justify making API and the implementation more complicated. And to me personally, `start_hint` stuff and its use in the implementation look very hacky. If one has such advanced knowledge of model structure and variables, they may as well have a different way to match & extract such subgraph.
--
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
[GitHub] [tvm] ganler commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152431567
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
I guess in either way the eventual results are the same. But yeah doing a pre-check could be faster (avoid the overhead of `undo_stack.emplace(p, r)`).
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1151194183
##########
tests/python/relax/test_dataflow_pattern.py:
##########
@@ -1006,5 +1006,50 @@ def rewriter(_, matchings):
tvm.ir.assert_structural_equal(rewritten, expected)
+def test_attention_qkv():
+ @tvm.script.ir_module
+ class QKV_proj:
+ @R.function
+ def main(
+ x: R.Tensor((2, 1024, 640), "float32"),
+ w0: R.Tensor((640, 640), "float32"),
+ w1: R.Tensor((640, 640), "float32"),
+ w2: R.Tensor((640, 640), "float32"),
+ ) -> R.Tensor:
+ with R.dataflow():
+ lv0 = R.matmul(x, w0)
+ lv1 = R.matmul(x, w1)
+ lv2 = R.matmul(x, w2)
+ out = (lv0, lv1, lv2)
+ R.output(out)
+ return out
+
+ with PatternContext() as ctx:
+ inp_pat = wildcard()
+ Q_weight_pat = wildcard()
+ K_weight_pat = wildcard()
+ V_weight_pat = wildcard()
+
+ matmul1 = is_op("relax.matmul")(inp_pat, Q_weight_pat)
+ matmul2 = is_op("relax.matmul")(inp_pat, K_weight_pat)
+ matmul3 = is_op("relax.matmul")(inp_pat, V_weight_pat)
+
+ # TODO(masahi): Automate addition of used_by constraints during is_op
Review Comment:
I have a follow-up PR to address this, which removes all used_by stuff below @ganler
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152456712
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
Do you have an example in `test_dataflow_pattern.py` that **requires** such flexibility? Similarly to how I don't understand the need for `start_hint`, I don't understand why we might want to start matching from B in A -> B.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152471948
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
ok :) I'll share my thought in the meantime.
Looking at an example in https://github.com/apache/tvm/blob/unity/tests/python/relax/test_dataflow_pattern.py#L540-L545, I cannot imagine how one would use `start_hint` in practice. Here, you wrote the input mod by hand, so you know `dfb.bindings[0].var` is associated to the "left" branch of the CBRx2. But in general, we don't have such information, especially in e2e scenarios for real world models.
Even if there was a good use case for it, I claim that it doesn't justify making API and the implementation more complicated (two additional params). And to me personally, `start_hint` stuff and its use in the implementation look very hacky. If one has such advanced knowledge of model structure and variables, they may as well have a different way to match & extract such subgraph.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1151194183
##########
tests/python/relax/test_dataflow_pattern.py:
##########
@@ -1006,5 +1006,50 @@ def rewriter(_, matchings):
tvm.ir.assert_structural_equal(rewritten, expected)
+def test_attention_qkv():
+ @tvm.script.ir_module
+ class QKV_proj:
+ @R.function
+ def main(
+ x: R.Tensor((2, 1024, 640), "float32"),
+ w0: R.Tensor((640, 640), "float32"),
+ w1: R.Tensor((640, 640), "float32"),
+ w2: R.Tensor((640, 640), "float32"),
+ ) -> R.Tensor:
+ with R.dataflow():
+ lv0 = R.matmul(x, w0)
+ lv1 = R.matmul(x, w1)
+ lv2 = R.matmul(x, w2)
+ out = (lv0, lv1, lv2)
+ R.output(out)
+ return out
+
+ with PatternContext() as ctx:
+ inp_pat = wildcard()
+ Q_weight_pat = wildcard()
+ K_weight_pat = wildcard()
+ V_weight_pat = wildcard()
+
+ matmul1 = is_op("relax.matmul")(inp_pat, Q_weight_pat)
+ matmul2 = is_op("relax.matmul")(inp_pat, K_weight_pat)
+ matmul3 = is_op("relax.matmul")(inp_pat, V_weight_pat)
+
+ # TODO(masahi): Automate addition of used_by constraints during is_op
Review Comment:
I have a follow-up PR to address this, which removes all `used_by` stuff below @ganler
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1151195533
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -568,18 +574,13 @@ static bool try_match(PNode* p, RNode* r, DFPatternMatcher* m,
commit(p, r);
// match parent patterns.
- for (auto& pparent_pairs : p->parents) {
- PNode* pparent = pparent_pairs.first;
- const std::vector<PairCons>& constraints = pparent_pairs.second;
-
+ for (auto& [pparent, constraints] : p->parents) {
bool any_cons_sat = false;
for (auto& rparent : r->parents) {
// skip if mismatch.
if (rparent->matched && rparent->matched != pparent->ptr) continue;
const auto& uses = def2use.at(rparent->ptr);
- // skip if `rparent` is not used by `r`.
- if (uses.cend() == uses.find(r->ptr)) continue;
Review Comment:
This has been removed since it seems to be always false.
--
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
[GitHub] [tvm] ganler commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1153613456
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
Thanks for bringing it up. When designing the usages it was my bad that I did not know enough use cases and I made it "more capable" by compromising simplicity. masa you have more professional experience with how patterns look in practice so I strongly agree that we should cut off the implementation/complexity for such long-tail use cases.
--
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
[GitHub] [tvm] ganler commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152449966
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
I see. Because the constraint or relation between nodes may or may not be single-way so in the beginning I made it bidirectional such that the pattern can be matched as long as you can let any node of the matched subgraph be start hint.
For example, for A->B pattern, you can start matching from either A or B (forward or backward).
Specifying certain matching order definitely makes the code logic and debugging easier but I am afraid it also cuts the flexibility in some way. Not sure if it is worth to have some flexibility or if we can keep them both.
--
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
[GitHub] [tvm] masahi commented on pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on PR #14417:
URL: https://github.com/apache/tvm/pull/14417#issuecomment-1487654668
@ganler Is `start_hint` stuff necessary? I want to remove it, since matching is now deterministic. Some tests depend on the use of `start_hint`.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152458535
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
I'm also going to look at how similar projects like MLIR, OpenVINO etc implements general graph pattern matching.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152471948
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
ok :) I'll share my thought in the meantime.
Looking at an example in https://github.com/apache/tvm/blob/unity/tests/python/relax/test_dataflow_pattern.py#L540-L545, I cannot imagine how one would use `start_hint` in practice. Here, you wrote the input mod by hand, so you know `dfb.bindings[0].var` is associated to the "left" branch of the CBRx2. But in general, we don't have such information, especially in e2e scenarios for real world models.
Even if there was a good use case for it, I claim that it doesn't justify making API and the implementation more complicated (two additional params + `try_match` loop on parants). And to me personally, `start_hint` stuff and its use in the implementation look very hacky. If one has such advanced knowledge of model structure and variables, they may as well have a different way to match & extract such subgraph.
--
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
[GitHub] [tvm] tvm-bot commented on pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "tvm-bot (via GitHub)" <gi...@apache.org>.
tvm-bot commented on PR #14417:
URL: https://github.com/apache/tvm/pull/14417#issuecomment-1487642609
<!---bot-comment-->
Thanks for contributing to TVM! Please refer to the contributing guidelines https://tvm.apache.org/docs/contribute/ for useful information and tips. Please request code reviews from [Reviewers](https://github.com/apache/incubator-tvm/blob/master/CONTRIBUTORS.md#reviewers) by @-ing them in a comment.
<!--bot-comment-ccs-start-->
* cc @quic-sanirudh <sub>See [#10317](https://github.com/apache/tvm/issues/10317) for details</sub><!--bot-comment-ccs-end-->
<sub>Generated by [tvm-bot](https://github.com/apache/tvm/blob/main/ci/README.md#github-actions)</sub>
--
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
[GitHub] [tvm] ganler commented on pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on PR #14417:
URL: https://github.com/apache/tvm/pull/14417#issuecomment-1488064209
(Traveling) if you can wait I can file a review after 10 hours but definitely within 24 hours. :). Hope it won't get you blocked.
--
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
[GitHub] [tvm] ganler commented on pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "ganler (via GitHub)" <gi...@apache.org>.
ganler commented on PR #14417:
URL: https://github.com/apache/tvm/pull/14417#issuecomment-1487724330
@masahi Thanks. Start hint means the start point of graph matching. It is useful when you have multiple matchable patterns and want to explicitly match one of them which are close to / subsuming certain node.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152471948
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
ok :) I'll share my thought in the meantime.
Looking at an example in https://github.com/apache/tvm/blob/unity/tests/python/relax/test_dataflow_pattern.py#L540-L545, I cannot imagine how one would use `start_hint` in practice. Here, you wrote the input mod by hand, so you know `dfb.bindings[0].var` is associated to the "left" branch of the CBRx2. But in general, we don't have such information, especially in e2e scenarios for real world models.
Even if there was a good use case for it, I claim that it doesn't justify making API and the implementation more complicated. If one has such advanced knowledge of model structure and variables, they may as well have a different way to match & extract such subgraph.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152443315
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
Here my concern is not about performance. If the same pair is committed more than once, I think there is something odd about the matching algorithm.
Later I'll try to improve the matching algorithm implementation. In particular, I want to remove `try_match` loop on parents, https://github.com/apache/tvm/blob/278bc9bbdf7d9b12c44bb78b71f91e4872b14353/src/relax/ir/dataflow_matcher.cc#L577-L607. This bidirectional matching has been a source of confusion to me (and debugging is very hard) - Since the constraint graph is assumed to be a DAG, I think we can start matching from the root nodes in a topo-sorted order, and matching should be able to proceed purely in one direction.
--
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
[GitHub] [tvm] masahi commented on a diff in pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "masahi (via GitHub)" <gi...@apache.org>.
masahi commented on code in PR #14417:
URL: https://github.com/apache/tvm/pull/14417#discussion_r1152443315
##########
src/relax/ir/dataflow_matcher.cc:
##########
@@ -541,15 +541,21 @@ 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::set<const VarNode*>>& def2use,
+ const std::map<const VarNode*, std::vector<const VarNode*>>& def2use,
const std::map<const VarNode*, std::vector<const VarNode*>>& use2def) {
- if (nullptr != p->matched && p->matched == r->ptr) return true; // matched before.
+ 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;
std::stack<std::pair<PNode*, RNode*>> undo_stack{};
const auto commit = [&undo_stack](PNode* p, RNode* r) {
// match with each other.
+ // TODO(ganler, masahi): Why commit on the same p-r pair happens more than once?
Review Comment:
Here my concern is not about performance. If the same pair is committed more than once, I think there is something odd about the matching algorithm.
Later I'll try to improve the matching algorithm implementation. In particular, I want to remove `try_match` loop on parents, https://github.com/apache/tvm/blob/278bc9bbdf7d9b12c44bb78b71f91e4872b14353/src/relax/ir/dataflow_matcher.cc#L577-L607. This bidirectional matching has been a source of confusion to me - Since the constraint graph is assumed to be a DAG, I think we can start matching from the root nodes in a topo-sorted order, and matching should be able to proceed purely in one direction.
--
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
[GitHub] [tvm] vinx13 merged pull request #14417: [Unity] Remove non-deterministic behavior from graph pattern matching
Posted by "vinx13 (via GitHub)" <gi...@apache.org>.
vinx13 merged PR #14417:
URL: https://github.com/apache/tvm/pull/14417
--
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