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
35namespace tvm {
36namespace relay {
37
38using support::LinkedList;
39using 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 */
45class 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