analysis.h 8.66 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

20
/*!
Zhi committed
21 22 23 24 25
 * \file tvm/relay/analysis.h
 * \brief The set of Relay analysis passes written in C++.
 */
#ifndef TVM_RELAY_ANALYSIS_H_
#define TVM_RELAY_ANALYSIS_H_
26

Zhi committed
27
#include <tvm/relay/adt.h>
28
#include <tvm/relay/expr.h>
29
#include <tvm/relay/function.h>
30
#include <tvm/ir/module.h>
Zhi committed
31
#include <tvm/relay/type.h>
32
#include <string>
33 34 35 36

namespace tvm {
namespace relay {

37
/*!
38
 * \brief Check that types are well kinded by applying "kinding rules".
39 40 41 42 43 44 45 46 47 48
 *
 * This pass ensures we do not do things that violate the design of the
 * type system when writing down types.
 *
 * For example tensors are not allowed to contain functions in Relay.
 *
 * We check this by ensuring the `dtype` field of a Tensor always contains
 * a data type such as `int`, `float`, `uint`.
 *
 * \param t The type to check.
49
 * \param mod The global module.
50
 *
51
 * \return The kind of the passed type.
52
 */
53
TVM_DLL Kind KindCheck(const Type& t, const IRModule& mod);
54

55
/*!
56 57 58 59 60 61 62 63 64 65 66 67
 * \brief Check whether an expression is constant.
 *
 * If the inputs of an expression are all constant, it means the expression
 * itself is constant also.
 *
 * \param e the expression.
 *
 * \return whether the expression is constant.
 */
TVM_DLL bool ConstantCheck(const Expr& e);

/*!
68
 * \brief Compare two expressions for structural equivalence.
69 70 71 72 73 74 75 76 77 78 79 80 81 82
 *
 * This comparison operator respects scoping and compares
 * expressions without regard to variable choice.
 *
 * For example: `let x = 1 in x` is equal to `let y = 1 in y`.
 *
 *   See https://en.wikipedia.org/wiki/Lambda_calculus#Alpha_equivalence
 *   for more details.
 *
 *   \param e1 The left hand expression.
 *   \param e2 The right hand expression.
 *
 *   \return true if equal, otherwise false
 */
83
TVM_DLL bool AlphaEqual(const Expr& e1, const Expr& e2);
84

85 86
/*!
 * \brief Compare two types for structural equivalence.
87 88 89 90 91 92
 *
 * This comparison operator respects scoping and compares
 * expressions without regard to variable choice.
 *
 * For example: `forall s, Tensor[f32, s]` is equal to
 * `forall w, Tensor[f32, w]`.
93
 *
94 95 96 97 98 99 100 101
 * See https://en.wikipedia.org/wiki/Lambda_calculus#Alpha_equivalence
 * for more details.
 *
 * \param t1 The left hand type.
 * \param t2 The right hand type.
 *
 * \return true if equal, otherwise false
 */
102
TVM_DLL bool AlphaEqual(const Type& t1, const Type& t2);
103

104
/*!
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
 * \brief Compare two patterns for structural equivalence.
 *
 * This comparison operator respects scoping and compares
 * patterns without regard to variable choice.
 *
 * For example: `A(x, _, y)` is equal to `A(z, _, a)`.
 *
 * See https://en.wikipedia.org/wiki/Lambda_calculus#Alpha_equivalence
 * for more details.
 *
 * \param t1 The left hand pattern.
 * \param t2 The right hand pattern.
 *
 * \return true if equal, otherwise false
 */
TVM_DLL bool AlphaEqual(const Pattern& t1, const Pattern& t2);

/*!
123
 * \brief Check that each Var is only bound once.
124 125 126
 *
 * For example, the expression `let x = 1 in let x = 2 in 3` bound x twice.
 *
127 128
 * `let f = (\x -> x) in let g = (\x -> x + 1) in f(g(2))` also bound x twice,
 * although x is not shadowed.
129
 *
130
  * \param expr the expression to check.
131
 *
132
  * \return true iff all Var in expr is bound at most once.
133
 */
134
TVM_DLL bool WellFormed(const Expr& expr);
135

136 137
/*!
 * \brief Get all bound variables from expression expr.
138 139 140 141 142 143 144 145
 *
 * Bound variables are all variables that are declared in the expr.
 * They only have meaning inside that expr, and can only be used in it.
 *
 * \param expr the expression.
 *
 * \return List of bound vars, in the PostDFS order in the expression.
 */
146
TVM_DLL tvm::Array<Var> BoundVars(const Expr& expr);
147

148 149
/*!
 * \brief Get all bound variables from pattern pat.
雾雨魔理沙 committed
150 151 152 153 154 155 156 157 158 159
 *
 * Bound variables are all variables that got bound by the pat.
 * They only have meaning inside that expr, and can only be used in it.
 *
 * \param pat the Pattern.
 *
 * \return List of bound vars, in the PostDFS order in the expression.
 */
TVM_DLL tvm::Array<Var> BoundVars(const Pattern& pat);

160 161
/*!
 * \brief Get free type parameters from expression expr.
162
 *
163 164
 * Free variables are variables that are not bound by a
 * let or a function parameter in the context.
165
 *
166
 * \param expr the expression.
167
 *
168
 * \return List of free vars, in the PostDFS order in the expression.
169
 */
170
TVM_DLL tvm::Array<Var> FreeVars(const Expr& expr);
171

172 173
/*!
 * \brief Get all variables from expression expr.
174 175 176 177 178
 *
 * \param expr the expression.
 *
 * \return List of all vars, in the PostDFS order in the expression.
 */
179
TVM_DLL tvm::Array<Var> AllVars(const Expr& expr);
180

181 182
/*!
 * \brief Get free TypeVars from expression expr.
183
 *
184 185
 * Free type parameters are type parameters that are not bound by a function
 * type in the context.
186
 *
187
 * \param expr the expression.
188
 * \param mod the module.
189
 *
190
 * \return List of free vars, in the PostDFS order visited by expr.
191
 */
192
TVM_DLL tvm::Array<TypeVar> FreeTypeVars(const Expr& expr, const IRModule& mod);
193

194 195
/*!
 * \brief Get free TypeVars from type t.
196 197 198 199 200
 *
 * Free type parameters are type parameters that are not bound by a function
 * type in the context.
 *
 * \param t the type.
201
 * \param mod the module.
202 203 204
 *
 * \return List of free type vars, in the PostDFS order visited by type.
 */
205
TVM_DLL tvm::Array<TypeVar> FreeTypeVars(const Type& t, const IRModule& mod);
206

207 208
/*!
 * \brief Get all bound type variables from expression expr.
209 210 211 212 213
 *
 * Bound variables are all type variables that are declared in the expr.
 * They only have meaning inside that expr, and can only be used in it.
 *
 * \param expr the expression.
214
 * \param mod the module.
215 216 217
 *
 * \return List of bound type vars, in the PostDFS order in the expression.
 */
218
TVM_DLL tvm::Array<TypeVar> BoundTypeVars(const Expr& expr, const IRModule& mod);
219

220 221
/*!
 * \brief Get all bound type variables from type t.
222 223 224 225 226
 *
 * Bound variables are all type variables that are declared in the type.
 * They only have meaning inside that type, and can only be used in it.
 *
 * \param t the type
227
 * \param mod the module.
228 229 230
 *
 * \return List of bound type vars, in the PostDFS order visited by type.
 */
231
TVM_DLL tvm::Array<TypeVar> BoundTypeVars(const Type& t, const IRModule& mod);
232

233 234
/*!
 * \brief Get all type variables in expression expr.
235 236
 *
 * \param expr the expression.
237
 * \param mod the module.
238 239 240
 *
 * \return List of type vars, in the PostDFS order in the expression.
 */
241
TVM_DLL tvm::Array<TypeVar> AllTypeVars(const Expr& expr, const IRModule& mod);
242

243 244
/*!
 * \brief Get all type variables in type t.
245 246
 *
 * \param t the type.
247
 * \param mod the module.
248 249 250
 *
 * \return List of type vars, in the PostDFS order visited by type.
 */
251
TVM_DLL tvm::Array<TypeVar> AllTypeVars(const Type& t, const IRModule& mod);
252

253
/*!
254
 * \brief Collect the device mapping information of each expression.
255
 *
256
 * \param expr The expression.
257
 *
258 259
 * \return The device mapping.
 */
260
TVM_DLL Map<Expr, Integer> CollectDeviceInfo(const Expr& expr);
261

262
/*!
263 264 265 266 267 268 269 270 271
 * \brief Collect the device anntation operators.
 *
 * \param expr The expression.
 *
 * \return The annotated expression to device type mapping for annotation ops.
 */
TVM_DLL Map<Expr, Integer> CollectDeviceAnnotationOps(const Expr& expr);

/*!
272 273 274 275 276
 * \brief Finds cases that the given match expression does not catch, if any.
 *
 * \param match the match expression to test
 *
 * \param mod The module used for accessing global type var definitions, can be None.
277
 *
278 279 280
 * \return Returns a list of cases (as patterns) that are not handled by the match
 * expression.
 */
281
TVM_DLL Array<Pattern> UnmatchedCases(const Match& match, const IRModule& mod);
282

283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303
/*! \brief A hashing structure in the style of std::hash. */
struct StructuralHash {
  /*! \brief Hash a Relay type.
   *
   * Implements structural hashing of a Relay type.
   *
   * \param type the type to hash.
   *
   * \return the hash value.
   */
  size_t operator()(const Type& type) const;
  /*! \brief Hash a Relay expression.
   *
   * Implements structural hashing of a Relay expression.
   *
   * \param expr the expression to hash.
   *
   * \return the hash value.
   */
  size_t operator()(const Expr& expr) const;
};
304

305 306
}  // namespace relay
}  // namespace tvm
307

Zhi committed
308
#endif  // TVM_RELAY_ANALYSIS_H_