1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, 13 * software distributed under the License is distributed on an 14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 15 * KIND, either express or implied. See the License for the 16 * specific language governing permissions and limitations 17 * under the License. 18 */ 19 20 /*! 21 * \file src/relay/analysis/dependency_graph.h 22 * \brief create a dependency graph. 23 */ 24 #ifndef TVM_RELAY_ANALYSIS_DEPENDENCY_GRAPH_H_ 25 #define TVM_RELAY_ANALYSIS_DEPENDENCY_GRAPH_H_ 26 27 #include <tvm/relay/expr.h> 28 29 #include <unordered_map> 30 #include <vector> 31 32 #include "../../support/arena.h" 33 #include "../transforms/let_list.h" 34 35 namespace tvm { 36 namespace relay { 37 38 using support::LinkedList; 39 using support::LinkNode; 40 41 /* DependencyGraph track input and output of an Expr. 42 * Additionally, dummy scope is created to model scope. 43 * It allow us to traverse the graph in reverse order. 44 */ 45 class DependencyGraph { 46 public: 47 /*! \brief A node in the graph. */ 48 struct Node { 49 // Determine scope boundaries. Used for calculating scopes, not for 50 // constructing dependency graph. 51 bool new_scope = false; 52 // incoming edges 53 LinkedList<Node*> children; 54 // outgoing edges 55 LinkedList<Node*> parents; 56 }; 57 58 /*! \brief Maps a Relay Expr to its node in the dependency graph. */ 59 std::unordered_map<Expr, Node*, ObjectPtrHash, ObjectPtrEqual> expr_node; 60 61 /*! \brief The dependency graph in post DFS order. */ 62 std::vector<Node*> post_dfs_order; 63 64 /*! 65 * \brief Create a dependency graph. 66 * \param arena The arena used for data allocation. 67 * \param body The body of the expression to create a graph. 68 */ 69 static DependencyGraph Create(support::Arena* arena, const Expr& body); 70 71 private: 72 class Creator; 73 }; 74 75 } // namespace relay 76 } // namespace tvm 77 #endif // TVM_RELAY_ANALYSIS_DEPENDENCY_GRAPH_H_ 78