You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2020/02/14 18:52:03 UTC
[GitHub] [incubator-tvm] mbrookhart opened a new pull request #4886: First
pass a defining a non-recursive Graph Vistor and Rewriter
mbrookhart opened a new pull request #4886: First pass a defining a non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886
@jroesch @tqchen
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on issue #4886: [RELAY]
Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on issue #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#issuecomment-608561939
cc @icemelon9 re let node, let us not expand letnode for now, as they could be useful in Dataflow normal form and marks boundries of the dataflow regions and effect
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] icemelon9 commented on a change in pull request
#4886: [RELAY] Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
icemelon9 commented on a change in pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403160592
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,188 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * MixedModeVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * MixedModeVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class MixedModeVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ /*! \brief The constructor of MixedModeVisitor
+ * \param visit_limit The number of times to allow visitation to a note. Usually 1, ocassionally
+ * higher (i.e., 2 for dead code elimiation), limited to 10 as a sanity check.
+ */
+ MixedModeVisitor(int visit_limit = 1);
+
+ /*!
+ * \brief VisitExpr is finalized to preserve call expansion of dataflow regions
+ */
+ void VisitExpr(const Expr& expr) final;
+ void VisitExpr_(const CallNode* op) override;
+ void VisitExpr_(const TupleNode* op) override;
+ void VisitExpr_(const TupleGetItemNode* op) override;
+
+ protected:
+ /*!
+ * \brief A function to apply when reaching a leaf of the graph non-recursively
+ */
+ virtual void VisitLeaf(const Expr& expr);
+ /*!
+ * \brief A function to determine if an expression has already been visited or needs to be
+ * re-visited
+ */
+ virtual bool CheckVisited(const Expr& expr);
+ /*!
+ * \brief The max number of times to visit a node
+ */
+ size_t visit_limit_;
+};
+
+/*! \brief Non-recursive DFS Graph Traversal for Custom Rewriting Passes
+ *
+ * MixedModeMutator treats Expr as dataflow graph, and only Rewrites each Expr once.
+ * The mutated results are memoized in a map and reused so that
+ * local transformation on the dataflow preserves the graph structure.
+ *
+ * MixedModeMutator provides the same recursive API as ExprMutator, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ *
+ * Uses Rewrite_ API of ExprRewriter for a cleaner split between recrusive and non-recursive behavior.
+ */
+class MixedModeMutator : public ::tvm::relay::ExprMutator {
+ public:
+ Expr VisitExpr(const Expr& expr) final;
+ virtual Expr DispatchVisitExpr(const Expr& expr);
+ Expr VisitExpr_(const TupleNode* op) final { return Rewrite(op); };
+ Expr VisitExpr_(const CallNode* call_node) final { return Rewrite(call_node); };
+ Expr VisitExpr_(const TupleGetItemNode* op) final { return Rewrite(op); };
+ /*!
+ * Users should override Rewrite_ methods to implement their pass. Rewrite_ functions will be
+ * able to rewrite the op only with data about the original node `pre` and the same node with
+ * modified inputs `post` and should not recurse.
+ *
+ * \param pre The expression node before rewriting.
+ * \param post The expression with rewritten inputs.
+ */
+ virtual Expr Rewrite_(const TupleNode* pre, const Expr& post) { return post;}
+ virtual Expr Rewrite_(const CallNode* pre, const Expr& post) { return post; }
+ virtual Expr Rewrite_(const TupleGetItemNode* pre, const Expr& post) { return post; }
+
+ protected:
+ /*! \brief Implement Rewrite API by calling ExprMutator's VisitExpr_(op) to get a `post` node with
+ * changed inputs.
+ */
+ template <typename T>
+ Expr Rewrite(const T* op) {
+ Expr post = ExprMutator::VisitExpr_(op);
+ return Rewrite_(op, post);
+ }
+
+ virtual void VisitLeaf(const Expr& expr);
+ virtual bool CheckVisited(const Expr& expr);
+};
+
+/*! \brief A non-iterating Expression Rewriter
+ *
+ * ExprRewriter provides a Rewrite interface for modifying graphs in Post-DFS order.
+ * The expectation is that ExprRewriter objects will be passed to PostOrderRewrite, which will
+ * non-recursively unroll the graph and call Rewriting on inputs. It will then pass the original
+ * node, called `pre`, and a node recreated with any alterned inputs, called `post`, to the
+ * ExprRewriter. The ExprRewriter can then use the information in those two nodes to do more complex
+ * graph rewriting.
+ */
Review comment:
move this document to directly on top of `class ExprRewriter`? also fix the indent starting from line 325
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401313355
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushes those arguments to the stack
+ * and continues iteratively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ if (fcheck_visited(expr)) {
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children have already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
+ // No need to expand the children directly run visit.
+ fvisit_leaf(node);
+ stack.pop();
+ }
+ }
+}
+
+DataflowVisitor::DataflowVisitor(int visit_limit) {
+ CHECK(visit_limit > 0) << "Dataflow visit limit must be greater than 0";
+ CHECK(visit_limit < 10) << "Dataflow visit limit must be less than 10";
Review comment:
This is primarily in here to support Dead Code Elimination, which visits every node twice. The limit of 10 is what I considered an absurdly high number with no use case to prevent things like overflow error or misuse. I expect almost everyone to use the default of 1.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403096442
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,188 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * MixedModeVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * MixedModeVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class MixedModeVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ /*! \brief The constructor of MixedModeVisitor
+ * \param visit_limit The number of times to allow visitation to a note. Usually 1, ocassionally
+ * higher (i.e., 2 for dead code elimiation), limited to 10 as a sanity check.
+ */
+ MixedModeVisitor(int visit_limit = 1);
Review comment:
Use explicit constructor for constructors with one argument
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r379602582
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -197,7 +198,7 @@ class ExprMutator
* \brief Mutate is alias for VisitExpr
* \return expr.
*/
- Expr Mutate(const Expr& expr) {
+ virtual Expr Mutate(const Expr& expr) {
Review comment:
Can directly overload VisitExpr, no need to overload mutate
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r379618563
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -197,7 +198,7 @@ class ExprMutator
* \brief Mutate is alias for VisitExpr
* \return expr.
*/
- Expr Mutate(const Expr& expr) {
+ virtual Expr Mutate(const Expr& expr) {
Review comment:
Mmm, the way it's current written I need a way to distinguish when I'm actually visiting and when I'm just querying for the updated child. I'm using VisitExpr to actually process a node and Mutate to query for the child. I'll think about a cleaner way to do that.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] anijain2305 commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
anijain2305 commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r395789429
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushed those arguments to the stack
+ * and continues non-recursively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
Review comment:
Very minor - Bring the comments inside the if for consistency
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401903046
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushes those arguments to the stack
+ * and continues iteratively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ if (fcheck_visited(expr)) {
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children have already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
Review comment:
I don't think so, we haven't seen MatchNode in deep dataflow regions, do you have a use case in mind?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] yzhliu commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
yzhliu commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r394726606
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushed those arguments to the stack
+ * and continues non-recursively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ if (fcheck_visited(expr)) {
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children has already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
+ // No need to expand the children directly run visit.
+ // terminal leaf, directly use visited.
+ fvisit_leaf(node);
+ stack.pop();
+ }
+ }
+}
+
+DataflowVisitor::DataflowVisitor(int visit_limit) {
+ CHECK(visit_limit > 0) << "Dataflow visit limit must be greater than 0";
+ CHECK(visit_limit < 10) << "Dataflow visit limit must be less than 10";
+ visit_limit_ = visit_limit;
+}
+
+void DataflowVisitor::VisitLeaf(const Expr& expr) {
+ if (visit_counter_[expr.get()] == 0) {
+ ExprFunctor::VisitExpr(expr);
+ }
+ visit_counter_[expr.get()]++;
+}
+
+bool DataflowVisitor::CheckVisited(const Expr& expr) {
+ if (visit_counter_[expr.get()] < visit_limit_) {
+ return false;
+ } else {
+ visit_counter_[expr.get()]++;
+ return true;
+ }
+}
+
+void DataflowVisitor::VisitExpr(const Expr& expr) {
+ auto fcheck_visited = [this](const Expr& expr) { return this->CheckVisited(expr); };
+ auto fvisit_leaf = [this](const Expr& expr) { return this->VisitLeaf(expr); };
+ if (visit_counter_[expr.get()] < 1) {
Review comment:
not sure, do we need to respect `visit_limit_` here?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r379618563
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -197,7 +198,7 @@ class ExprMutator
* \brief Mutate is alias for VisitExpr
* \return expr.
*/
- Expr Mutate(const Expr& expr) {
+ virtual Expr Mutate(const Expr& expr) {
Review comment:
:+1:
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] anijain2305 commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
anijain2305 commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r395789817
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushed those arguments to the stack
+ * and continues non-recursively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ if (fcheck_visited(expr)) {
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children has already been expanded.
Review comment:
has -> have
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] zhiics commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
zhiics commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401248550
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushes those arguments to the stack
+ * and continues iteratively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ if (fcheck_visited(expr)) {
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children have already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
Review comment:
also need to handle `MatchNode` and ref nodes?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] yzhliu commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
yzhliu commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r394726756
##########
File path: src/relay/analysis/util.cc
##########
@@ -330,12 +330,15 @@ TVM_REGISTER_GLOBAL("relay.analysis.all_type_vars")
*/
std::unordered_map<const Object*, size_t>
GetExprRefCount(const Expr& body) {
- class ExprRefCounter : private ExprVisitor {
+ class ExprRefCounter : private DataflowVisitor {
public:
std::unordered_map<const Object*, size_t>
Get(const Expr& body) {
this->VisitExpr(body);
- return std::move(this->visit_counter_);
+ for (auto kv : visit_counter_) {
+ std::cout << kv.first << '\t' << kv.second << std::endl;
+ }
Review comment:
remember to remove debug code.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] zhiics commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
zhiics commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401352114
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushes those arguments to the stack
+ * and continues iteratively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ if (fcheck_visited(expr)) {
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children have already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
+ // No need to expand the children directly run visit.
+ fvisit_leaf(node);
+ stack.pop();
+ }
+ }
+}
+
+DataflowVisitor::DataflowVisitor(int visit_limit) {
+ CHECK(visit_limit > 0) << "Dataflow visit limit must be greater than 0";
+ CHECK(visit_limit < 10) << "Dataflow visit limit must be less than 10";
Review comment:
I see. Let's then add some comments before `visit_limit_` defined in the class and a comment here before the `CHECK`.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] icemelon9 commented on a change in pull request
#4886: [RELAY] Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
icemelon9 commented on a change in pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403162390
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,188 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * MixedModeVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * MixedModeVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class MixedModeVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ /*! \brief The constructor of MixedModeVisitor
+ * \param visit_limit The number of times to allow visitation to a note. Usually 1, ocassionally
+ * higher (i.e., 2 for dead code elimiation), limited to 10 as a sanity check.
+ */
+ MixedModeVisitor(int visit_limit = 1);
+
+ /*!
+ * \brief VisitExpr is finalized to preserve call expansion of dataflow regions
+ */
+ void VisitExpr(const Expr& expr) final;
+ void VisitExpr_(const CallNode* op) override;
+ void VisitExpr_(const TupleNode* op) override;
+ void VisitExpr_(const TupleGetItemNode* op) override;
+
+ protected:
+ /*!
+ * \brief A function to apply when reaching a leaf of the graph non-recursively
+ */
+ virtual void VisitLeaf(const Expr& expr);
+ /*!
+ * \brief A function to determine if an expression has already been visited or needs to be
+ * re-visited
+ */
+ virtual bool CheckVisited(const Expr& expr);
+ /*!
+ * \brief The max number of times to visit a node
+ */
+ size_t visit_limit_;
+};
+
+/*! \brief Non-recursive DFS Graph Traversal for Custom Rewriting Passes
+ *
+ * MixedModeMutator treats Expr as dataflow graph, and only Rewrites each Expr once.
+ * The mutated results are memoized in a map and reused so that
+ * local transformation on the dataflow preserves the graph structure.
+ *
+ * MixedModeMutator provides the same recursive API as ExprMutator, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ *
+ * Uses Rewrite_ API of ExprRewriter for a cleaner split between recrusive and non-recursive behavior.
+ */
+class MixedModeMutator : public ::tvm::relay::ExprMutator {
+ public:
+ Expr VisitExpr(const Expr& expr) final;
+ virtual Expr DispatchVisitExpr(const Expr& expr);
+ Expr VisitExpr_(const TupleNode* op) final { return Rewrite(op); };
+ Expr VisitExpr_(const CallNode* call_node) final { return Rewrite(call_node); };
+ Expr VisitExpr_(const TupleGetItemNode* op) final { return Rewrite(op); };
+ /*!
+ * Users should override Rewrite_ methods to implement their pass. Rewrite_ functions will be
+ * able to rewrite the op only with data about the original node `pre` and the same node with
+ * modified inputs `post` and should not recurse.
+ *
+ * \param pre The expression node before rewriting.
+ * \param post The expression with rewritten inputs.
+ */
+ virtual Expr Rewrite_(const TupleNode* pre, const Expr& post) { return post;}
+ virtual Expr Rewrite_(const CallNode* pre, const Expr& post) { return post; }
+ virtual Expr Rewrite_(const TupleGetItemNode* pre, const Expr& post) { return post; }
+
+ protected:
+ /*! \brief Implement Rewrite API by calling ExprMutator's VisitExpr_(op) to get a `post` node with
+ * changed inputs.
+ */
+ template <typename T>
+ Expr Rewrite(const T* op) {
+ Expr post = ExprMutator::VisitExpr_(op);
+ return Rewrite_(op, post);
+ }
+
+ virtual void VisitLeaf(const Expr& expr);
+ virtual bool CheckVisited(const Expr& expr);
+};
+
+/*! \brief A non-iterating Expression Rewriter
+ *
+ * ExprRewriter provides a Rewrite interface for modifying graphs in Post-DFS order.
+ * The expectation is that ExprRewriter objects will be passed to PostOrderRewrite, which will
+ * non-recursively unroll the graph and call Rewriting on inputs. It will then pass the original
+ * node, called `pre`, and a node recreated with any alterned inputs, called `post`, to the
+ * ExprRewriter. The ExprRewriter can then use the information in those two nodes to do more complex
+ * graph rewriting.
+ */
Review comment:
We should also provide a guidance when to use `ExprRewriter` and when to use `MixedModeMutator` in the document/tutorial in a followup 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen merged pull request #4886: [RELAY]
Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen merged pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on issue #4886: [WIP][POC]First
pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on issue #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#issuecomment-606873195
cc @icemelon9 @yzhliu @anijain2305 @zhiics please help to review this PR, let us bring aim to bring it in this week.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401213764
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,181 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * DataflowVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * DataflowVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class DataflowVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ DataflowVisitor(int visit_limit = 1);
+
+ /*!
+ * \brief VisitExpr is finalized to preserve call expansion of dataflow regions
+ */
+ void VisitExpr(const Expr& expr) final;
+ void VisitExpr_(const CallNode* op) override;
+ void VisitExpr_(const TupleNode* op) override;
+ void VisitExpr_(const TupleGetItemNode* op) override;
+
+
Review comment:
One empty line
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401214283
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,181 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * DataflowVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * DataflowVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class DataflowVisitor : public ::tvm::relay::ExprVisitor {
Review comment:
Shall we unify the naming convention of DataflowVisitor and ScopeMutator? Perhaps ScopeVisitor?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r379618563
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -197,7 +198,7 @@ class ExprMutator
* \brief Mutate is alias for VisitExpr
* \return expr.
*/
- Expr Mutate(const Expr& expr) {
+ virtual Expr Mutate(const Expr& expr) {
Review comment:
Mmm, the way it's current written I need a way to distinguish when I'm actually visiting and when I'm just querying for the updated child. I'm using VisitExpr to actually process a node and Mutate to query for the child. I'll think about a cleaner way to do that.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401213597
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -196,7 +196,7 @@ class ExprMutator
* \brief Mutate is alias for VisitExpr
* \return expr.
*/
- Expr Mutate(const Expr& expr) {
+ virtual Expr Mutate(const Expr& expr) {
Review comment:
I still think it is better to not subclass Mutate, instead, override VisitExpr in the ScopeMutator, which calls into DispatchVisitExpr that does the dispatching.
This way we do not have to change a lot of calls of VisitExpr into Mutate in the subclasses, which can be confusing(for user to think about which one to call).
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] zhiics commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
zhiics commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401249373
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushes those arguments to the stack
+ * and continues iteratively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ if (fcheck_visited(expr)) {
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children have already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
+ // No need to expand the children directly run visit.
+ fvisit_leaf(node);
+ stack.pop();
+ }
+ }
+}
+
+DataflowVisitor::DataflowVisitor(int visit_limit) {
+ CHECK(visit_limit > 0) << "Dataflow visit limit must be greater than 0";
+ CHECK(visit_limit < 10) << "Dataflow visit limit must be less than 10";
Review comment:
Could you explain why it must be less than 10 here? I think I don't well understand the functionality of `visit_limit`. So we will just stop visiting if it reaches the limit?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] anijain2305 commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
anijain2305 commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r395788182
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
Review comment:
Non-recursive is same as iterative, right? Maybe, just write iterative?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r395916371
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushed those arguments to the stack
+ * and continues non-recursively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ if (fcheck_visited(expr)) {
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children has already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
+ // No need to expand the children directly run visit.
+ // terminal leaf, directly use visited.
+ fvisit_leaf(node);
+ stack.pop();
+ }
+ }
+}
+
+DataflowVisitor::DataflowVisitor(int visit_limit) {
+ CHECK(visit_limit > 0) << "Dataflow visit limit must be greater than 0";
+ CHECK(visit_limit < 10) << "Dataflow visit limit must be less than 10";
+ visit_limit_ = visit_limit;
+}
+
+void DataflowVisitor::VisitLeaf(const Expr& expr) {
+ if (visit_counter_[expr.get()] == 0) {
+ ExprFunctor::VisitExpr(expr);
+ }
+ visit_counter_[expr.get()]++;
+}
+
+bool DataflowVisitor::CheckVisited(const Expr& expr) {
+ if (visit_counter_[expr.get()] < visit_limit_) {
+ return false;
+ } else {
+ visit_counter_[expr.get()]++;
+ return true;
+ }
+}
+
+void DataflowVisitor::VisitExpr(const Expr& expr) {
+ auto fcheck_visited = [this](const Expr& expr) { return this->CheckVisited(expr); };
+ auto fvisit_leaf = [this](const Expr& expr) { return this->VisitLeaf(expr); };
+ if (visit_counter_[expr.get()] < 1) {
Review comment:
Found a better solution :)
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] anijain2305 commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
anijain2305 commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r395787924
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushed those arguments to the stack
Review comment:
pushed --> pushes
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on issue #4886: [RELAY]
Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on issue #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#issuecomment-608695628
Thanks @icemelon9 @yzhliu @anijain2305 @jroesch @MarisaKirisame, and @mbrookhart ! It would be great if we can followup to convert more passes to the non-recursive form
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r394748894
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,135 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to non-recursively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushed those arguments to the stack
+ * and continues non-recursively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ if (fcheck_visited(expr)) {
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children has already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
+ // No need to expand the children directly run visit.
+ // terminal leaf, directly use visited.
+ fvisit_leaf(node);
+ stack.pop();
+ }
+ }
+}
+
+DataflowVisitor::DataflowVisitor(int visit_limit) {
+ CHECK(visit_limit > 0) << "Dataflow visit limit must be greater than 0";
+ CHECK(visit_limit < 10) << "Dataflow visit limit must be less than 10";
+ visit_limit_ = visit_limit;
+}
+
+void DataflowVisitor::VisitLeaf(const Expr& expr) {
+ if (visit_counter_[expr.get()] == 0) {
+ ExprFunctor::VisitExpr(expr);
+ }
+ visit_counter_[expr.get()]++;
+}
+
+bool DataflowVisitor::CheckVisited(const Expr& expr) {
+ if (visit_counter_[expr.get()] < visit_limit_) {
+ return false;
+ } else {
+ visit_counter_[expr.get()]++;
+ return true;
+ }
+}
+
+void DataflowVisitor::VisitExpr(const Expr& expr) {
+ auto fcheck_visited = [this](const Expr& expr) { return this->CheckVisited(expr); };
+ auto fvisit_leaf = [this](const Expr& expr) { return this->VisitLeaf(expr); };
+ if (visit_counter_[expr.get()] < 1) {
Review comment:
Dead Code Elimination fails if I respect visit_limit here along with everywhere else, has to do with a double count. I'm a little concerned about the magic number, still thinking about possible edge cases with this, might find a cleaner solution.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] icemelon9 commented on a change in pull request
#4886: [RELAY] Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
icemelon9 commented on a change in pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403135767
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,188 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * MixedModeVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * MixedModeVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class MixedModeVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ /*! \brief The constructor of MixedModeVisitor
+ * \param visit_limit The number of times to allow visitation to a note. Usually 1, ocassionally
Review comment:
note -> 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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
With regards,
Apache Git Services
[GitHub] [incubator-tvm] zhiics commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
zhiics commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401246595
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
Review comment:
ExpandDataflow
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401904820
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,181 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * DataflowVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * DataflowVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class DataflowVisitor : public ::tvm::relay::ExprVisitor {
Review comment:
MixedModeVisitor?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] jroesch commented on a change in pull request
#4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and
Rewriter
Posted by GitBox <gi...@apache.org>.
jroesch commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401236242
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,181 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * DataflowVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * DataflowVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class DataflowVisitor : public ::tvm::relay::ExprVisitor {
Review comment:
I don't think ScopeVisitor is a very good name, i.e what is the property that the visitor is maintaining respecting? it is not just scoping.
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] jroesch commented on issue #4886: [WIP][POC]First
pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
jroesch commented on issue #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#issuecomment-598860385
cc @MarisaKirisame
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] icemelon9 commented on a change in pull request
#4886: [RELAY] Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
icemelon9 commented on a change in pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403141507
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,188 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * MixedModeVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * MixedModeVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class MixedModeVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ /*! \brief The constructor of MixedModeVisitor
+ * \param visit_limit The number of times to allow visitation to a note. Usually 1, ocassionally
+ * higher (i.e., 2 for dead code elimiation), limited to 10 as a sanity check.
+ */
+ MixedModeVisitor(int visit_limit = 1);
+
+ /*!
+ * \brief VisitExpr is finalized to preserve call expansion of dataflow regions
+ */
+ void VisitExpr(const Expr& expr) final;
+ void VisitExpr_(const CallNode* op) override;
+ void VisitExpr_(const TupleNode* op) override;
+ void VisitExpr_(const TupleGetItemNode* op) override;
+
+ protected:
+ /*!
+ * \brief A function to apply when reaching a leaf of the graph non-recursively
+ */
+ virtual void VisitLeaf(const Expr& expr);
+ /*!
+ * \brief A function to determine if an expression has already been visited or needs to be
+ * re-visited
+ */
+ virtual bool CheckVisited(const Expr& expr);
+ /*!
+ * \brief The max number of times to visit a node
+ */
+ size_t visit_limit_;
+};
+
+/*! \brief Non-recursive DFS Graph Traversal for Custom Rewriting Passes
+ *
+ * MixedModeMutator treats Expr as dataflow graph, and only Rewrites each Expr once.
+ * The mutated results are memoized in a map and reused so that
+ * local transformation on the dataflow preserves the graph structure.
+ *
+ * MixedModeMutator provides the same recursive API as ExprMutator, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ *
+ * Uses Rewrite_ API of ExprRewriter for a cleaner split between recrusive and non-recursive behavior.
+ */
+class MixedModeMutator : public ::tvm::relay::ExprMutator {
+ public:
+ Expr VisitExpr(const Expr& expr) final;
+ virtual Expr DispatchVisitExpr(const Expr& expr);
+ Expr VisitExpr_(const TupleNode* op) final { return Rewrite(op); };
+ Expr VisitExpr_(const CallNode* call_node) final { return Rewrite(call_node); };
+ Expr VisitExpr_(const TupleGetItemNode* op) final { return Rewrite(op); };
+ /*!
+ * Users should override Rewrite_ methods to implement their pass. Rewrite_ functions will be
Review comment:
```suggestion
* \brief Users should override Rewrite_ methods to implement their pass. Rewrite_ functions will be
```
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] icemelon9 commented on a change in pull request
#4886: [RELAY] Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
icemelon9 commented on a change in pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403145987
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -29,8 +29,158 @@
#include <tvm/relay/expr_functor.h>
#include <tvm/relay/pattern_functor.h>
+#include <stack>
+
namespace tvm {
namespace relay {
+/*!
+ * \brief A function to iteratively traverse dataflow regions of a graph
+ *
+ * ExpandDatflow manually manages a stack and performs DFS to determine the processing
+ * order of nodes in an input graph.
+ *
+ * If it finds a dataflow node (Call, Tuple, TupleGetItem), it checks if the arguments to that node
+ * need to be processed via fcheck_visited. If so, the function pushes those arguments to the stack
+ * and continues iteratively to process the top of the stack. When it finds a node that doesn't
+ * match the dataflow types, or a node who's inputs have all been processed, it visits the current
+ * leaf via fvisit_leaf.
+ *
+ * This function should be used internally to other classes to implement mixed-mode traversals. The
+ * expectation is that fvisit_leaf will perform recursive analysis within mixed-mode traversal if it
+ * hits a non-dataflow node.
+ *
+ * fcheck_visited and fvisit_leaf are templated to encourage compiler inlining.
+ */
+template <typename FCheckVisited, typename FVisitLeaf>
+void ExpandDataflow(Expr expr, FCheckVisited fcheck_visited, FVisitLeaf fvisit_leaf) {
+ std::stack<std::pair<Expr, bool>> stack;
+ auto fpush_to_stack = [&fcheck_visited, &stack](const Expr& expr) {
+ // The second state of the stack indicate whether the child has been
+ // expanded in the pre-order.
+ // NOTE: function will be inlined.
+ if (!fcheck_visited(expr)) {
+ stack.push({expr, false});
+ }
+ };
+ fpush_to_stack(expr);
+ while (stack.size() > 0) {
+ auto node = stack.top().first;
+ if (fcheck_visited(expr)) {
+ // if this node was visited through another path
+ // after being added to the stack ignore it.
+ stack.pop();
+ } else if (stack.top().second) {
+ // all the children have already been expanded.
+ // we can just run post order visit on it.
+ fvisit_leaf(node);
+ stack.pop();
+ } else if (const CallNode* op = node.as<CallNode>()) {
+ // mark expanded = true
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->args.rbegin(); it != op->args.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ fpush_to_stack(op->op);
+ } else if (const TupleNode* op = node.as<TupleNode>()) {
+ stack.top().second = true;
+ // push the children to the stack in reverse order
+ // to match recursive processing order
+ for (auto it = op->fields.rbegin(); it != op->fields.rend(); ++it) {
+ fpush_to_stack(*it);
+ }
+ } else if (const TupleGetItemNode* op = node.as<TupleGetItemNode>()) {
+ stack.top().second = true;
+ fpush_to_stack(op->tuple);
+ } else {
Review comment:
Should we expand `LetNode` as it could easily lead to deep dataflow?
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r401215336
##########
File path: include/tvm/relay/expr_functor.h
##########
@@ -232,6 +232,181 @@ class ExprMutator
std::unordered_map<Expr, Expr, ObjectHash, ObjectEqual> memo_;
};
+/*!
+ * \brief A wrapper around ExprVisitor which traverses the Dataflow Normal AST.
+ *
+ * DataflowVisitor treats Expr as dataflow graph, and visits in post-DFS order
+ *
+ * DataflowVisitor provides the same recursive API as ExprVisitor, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ */
+class DataflowVisitor : public ::tvm::relay::ExprVisitor {
+ public:
+ DataflowVisitor(int visit_limit = 1);
+
+ /*!
+ * \brief VisitExpr is finalized to preserve call expansion of dataflow regions
+ */
+ void VisitExpr(const Expr& expr) final;
+ void VisitExpr_(const CallNode* op) override;
+ void VisitExpr_(const TupleNode* op) override;
+ void VisitExpr_(const TupleGetItemNode* op) override;
+
+
+ protected:
+ /*!
+ * \brief A function to apply when reaching a leaf of the graph non-recursively
+ */
+ virtual void VisitLeaf(const Expr& expr);
+ /*!
+ * \brief A function to determine if an expression has already been visited or needs to be
+ * re-visited
+ */
+ virtual bool CheckVisited(const Expr& expr);
+ /*!
+ * \brief The max number of times to visit a node
+ */
+ size_t visit_limit_;
+};
+
+/*! \brief Non-recursive DFS Graph Traversal for Custom Rewriting Passes
+ *
+ * ScopeMutator treats Expr as dataflow graph, and only Rewrites each Expr once.
+ * The mutated results are memoized in a map and reused so that
+ * local transformation on the dataflow preserves the graph structure.
+ *
+ * ScopeMutator provides the same recursive API as ExprMutator, and uses
+ * recursion to traverse most forms of the IR, but under the hood it expands nested dataflow regions
+ * of the graph and processes them iteratatively to prevent stack overflows
+ *
+ * Uses Rewrite_ API of ExprRewriter for a cleaner split between recrusive and non-recursive behavior.
+ */
+class ScopeMutator : public ::tvm::relay::ExprMutator {
+ public:
+ Expr Mutate(const Expr& expr) final;
+ Expr VisitExpr_(const TupleNode* op) final { return Rewrite(op); };
+ Expr VisitExpr_(const CallNode* call_node) final { return Rewrite(call_node); };
+ Expr VisitExpr_(const TupleGetItemNode* op) final { return Rewrite(op); };
+ /*!
+ * Users should override Rewrite_ methods to implement their pass. Rewrite_ functions will be
+ * able to rewrite the op only with data about the original node `pre` and the same node with
Review comment:
document all the arguments
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on issue #4886: [WIP][POC]First
pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on issue #4886: [WIP][POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#issuecomment-608513598
@zhiics @jroesch @anijain2305 @yzhliu @icemelon9 please take a final look and https://tvm.apache.org/docs/contribute/code_review.html#approve-and-request-changes-explicitly
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] tqchen commented on a change in pull request #4886:
[POC]First pass a defining at non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
tqchen commented on a change in pull request #4886: [POC]First pass a defining at non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403097594
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -211,12 +365,12 @@ Expr ExprMutator::VisitExpr_(const MatchNode* m) {
for (const Clause& p : m->clauses) {
clauses.push_back(VisitClause(p));
}
- return Match(VisitExpr(m->data), clauses, m->complete);
Review comment:
The changes from VisitExpr -> Mutate is no longer necessary, please change them back
----------------------------------------------------------------
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
With regards,
Apache Git Services
[GitHub] [incubator-tvm] mbrookhart commented on a change in pull request
#4886: [RELAY] Non-recursive Graph Vistor and Rewriter
Posted by GitBox <gi...@apache.org>.
mbrookhart commented on a change in pull request #4886: [RELAY] Non-recursive Graph Vistor and Rewriter
URL: https://github.com/apache/incubator-tvm/pull/4886#discussion_r403100509
##########
File path: src/relay/ir/expr_functor.cc
##########
@@ -211,12 +365,12 @@ Expr ExprMutator::VisitExpr_(const MatchNode* m) {
for (const Clause& p : m->clauses) {
clauses.push_back(VisitClause(p));
}
- return Match(VisitExpr(m->data), clauses, m->complete);
Review comment:
@tqchen Every other method in this class already uses mutate instead of VisitExpr, this makes ExprMutator more internally consistent, even if it's not strictly needed. I prefer it for that reason, but it doesn't need to be part of the PR, if you really want me to remove 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:
users@infra.apache.org
With regards,
Apache Git Services