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 tvm/relay/analysis.h
22 * \brief The set of Relay analysis passes written in C++.
23 */
24#ifndef TVM_RELAY_ANALYSIS_H_
25#define TVM_RELAY_ANALYSIS_H_
26
27#include <tvm/ir/module.h>
28#include <tvm/relay/adt.h>
29#include <tvm/relay/expr.h>
30#include <tvm/relay/function.h>
31#include <tvm/relay/type.h>
32#include <tvm/runtime/logging.h>
33
34#include <string>
35#include <unordered_map>
36
37namespace tvm {
38namespace relay {
39
40/*!
41 * \brief Check that types are well kinded by applying "kinding rules".
42 *
43 * This pass ensures we do not do things that violate the design of the
44 * type system when writing down types.
45 *
46 * For example tensors are not allowed to contain functions in Relay.
47 *
48 * We check this by ensuring the `dtype` field of a Tensor always contains
49 * a data type such as `int`, `float`, `uint`.
50 *
51 * \param t The type to check.
52 * \param mod The global module.
53 * \param diag_ctx The Diagnostic context.
54 *
55 * \return The kind of the passed type.
56 */
57TVM_DLL Kind KindCheck(const Type& t, const IRModule& mod,
58 Optional<DiagnosticContext> diag_ctx = Optional<DiagnosticContext>());
59
60/*!
61 * \brief Check whether an expression is constant.
62 *
63 * If the inputs of an expression are all constant, it means the expression
64 * itself is constant also.
65 *
66 * \param e the expression.
67 *
68 * \return whether the expression is constant.
69 */
70TVM_DLL bool ConstantCheck(const Expr& e);
71
72/*!
73 * \brief Check whether an expression is in the basic block normal form.
74 *
75 * \param e the expression.
76 *
77 * \return whether the expression is in the basic block normal form.
78 */
79TVM_DLL bool BasicBlockNormalFormCheck(const Expr& e);
80
81/*!
82 * \brief Check that each Var is only bound once.
83 *
84 * For example, the expression `let x = 1 in let x = 2 in 3` bound x twice.
85 *
86 * `let f = (x -> x) in let g = (x -> x + 1) in f(g(2))` also bound x twice,
87 * although x is not shadowed.
88 *
89 * \param expr the expression to check.
90 * \param diag_ctx the diagnostic context
91 *
92 * \return true iff all Var in expr is bound at most once.
93 */
94TVM_DLL bool WellFormed(const Expr& expr,
95 Optional<DiagnosticContext> diag_ctx = Optional<DiagnosticContext>());
96
97/*!
98 * \brief Get all bound variables from expression expr.
99 *
100 * Bound variables are all variables that are declared in the expr.
101 * They only have meaning inside that expr, and can only be used in it.
102 *
103 * \param expr the expression.
104 *
105 * \return List of bound vars, in the PostDFS order in the expression.
106 */
107TVM_DLL tvm::Array<Var> BoundVars(const Expr& expr);
108
109/*!
110 * \brief Get all bound variables from pattern pat.
111 *
112 * Bound variables are all variables that got bound by the pat.
113 * They only have meaning inside that expr, and can only be used in it.
114 *
115 * \param pat the Pattern.
116 *
117 * \return List of bound vars, in the PostDFS order in the expression.
118 */
119TVM_DLL tvm::Array<Var> BoundVars(const Pattern& pat);
120
121/*!
122 * \brief Get free type parameters from expression expr.
123 *
124 * Free variables are variables that are not bound by a
125 * let or a function parameter in the context.
126 *
127 * \param expr the expression.
128 *
129 * \return List of free vars, in the PostDFS order in the expression.
130 */
131TVM_DLL tvm::Array<Var> FreeVars(const Expr& expr);
132
133/*!
134 * \brief Get all variables from expression expr.
135 *
136 * \param expr the expression.
137 *
138 * \return List of all vars, in the PostDFS order in the expression.
139 */
140TVM_DLL tvm::Array<Var> AllVars(const Expr& expr);
141
142/*!
143 * \brief Get free TypeVars from expression expr.
144 *
145 * Free type parameters are type parameters that are not bound by a function
146 * type in the context.
147 *
148 * \param expr the expression.
149 * \param mod the module.
150 *
151 * \return List of free vars, in the PostDFS order visited by expr.
152 */
153TVM_DLL tvm::Array<TypeVar> FreeTypeVars(const Expr& expr, const IRModule& mod);
154
155/*!
156 * \brief Get free TypeVars from type t.
157 *
158 * Free type parameters are type parameters that are not bound by a function
159 * type in the context.
160 *
161 * \param t the type.
162 * \param mod the module.
163 *
164 * \return List of free type vars, in the PostDFS order visited by type.
165 */
166TVM_DLL tvm::Array<TypeVar> FreeTypeVars(const Type& t, const IRModule& mod);
167
168/*!
169 * \brief Get all bound type variables from expression expr.
170 *
171 * Bound variables are all type variables that are declared in the expr.
172 * They only have meaning inside that expr, and can only be used in it.
173 *
174 * \param expr the expression.
175 * \param mod the module.
176 *
177 * \return List of bound type vars, in the PostDFS order in the expression.
178 */
179TVM_DLL tvm::Array<TypeVar> BoundTypeVars(const Expr& expr, const IRModule& mod);
180
181/*!
182 * \brief Get all bound type variables from type t.
183 *
184 * Bound variables are all type variables that are declared in the type.
185 * They only have meaning inside that type, and can only be used in it.
186 *
187 * \param t the type
188 * \param mod the module.
189 *
190 * \return List of bound type vars, in the PostDFS order visited by type.
191 */
192TVM_DLL tvm::Array<TypeVar> BoundTypeVars(const Type& t, const IRModule& mod);
193
194/*!
195 * \brief Get all type variables in expression expr.
196 *
197 * \param expr the expression.
198 * \param mod the module.
199 *
200 * \return List of type vars, in the PostDFS order in the expression.
201 */
202TVM_DLL tvm::Array<TypeVar> AllTypeVars(const Expr& expr, const IRModule& mod);
203
204/*!
205 * \brief Get all type variables in type t.
206 *
207 * \param t the type.
208 * \param mod the module.
209 *
210 * \return List of type vars, in the PostDFS order visited by type.
211 */
212TVM_DLL tvm::Array<TypeVar> AllTypeVars(const Type& t, const IRModule& mod);
213
214/*!
215 * \brief Finds cases that the given match expression does not catch, if any.
216 *
217 * \param match the match expression to test
218 *
219 * \param mod The module used for accessing global type var definitions, can be None.
220 *
221 * \return Returns a list of cases (as patterns) that are not handled by the match
222 * expression.
223 */
224TVM_DLL Array<Pattern> UnmatchedCases(const Match& match, const IRModule& mod);
225
226/*!
227 * \brief Get reference counter of each internal ExprNode in body.
228 *
229 * \param body The body expression.
230 *
231 * \return The reference count mapping.
232 */
233TVM_DLL std::unordered_map<const Object*, size_t> GetExprRefCount(const Expr& body);
234
235/*!
236 * \brief Get the updated module for collecting calibration data.
237 *
238 * \param mod The module to be updated.
239 *
240 * \return The updated module.
241 */
242TVM_DLL IRModule GetCalibrateModule(IRModule mod);
243
244/*!
245 * \brief Get the output map between subgrpahs and its inputs/output.
246 *
247 * \param mod The module for running calibration.
248 *
249 * \return The mapping between a subgraph name and its postition in the output tuple.
250 */
251TVM_DLL Map<GlobalVar, Array<Integer>> GetCalibrateOutputMap(const IRModule& mod);
252
253} // namespace relay
254} // namespace tvm
255
256#endif // TVM_RELAY_ANALYSIS_H_
257