# tvm-commits mailing list archives

##### Site index · List index
Message view
Top
From GitBox <...@apache.org>
Subject [GitHub] [incubator-tvm] yzhliu commented on a change in pull request #5618: [Arith] Inequalities solver
Date Fri, 26 Jun 2020 18:50:00 GMT
```
yzhliu commented on a change in pull request #5618:
URL: https://github.com/apache/incubator-tvm/pull/5618#discussion_r446351576

##########
File path: include/tvm/arith/int_solver.h
##########
@@ -191,6 +286,56 @@ void SmithNormalFormDiag(std::vector<std::vector<int64_t>>*
S, std::vector<std::
*/
IntConstraintsTransform SolveLinearEquations(const IntConstraints& system_to_solve);

+/*!
+ * \brief Solve linear inequalities.
+ * \param system_to_solve the variables to solve, their ranges, and a list of inequalities.
+ *        The inequalities are rewritten using Fourier-Motzkin elimination.
+ *        This function takes an array of (in)equalities and an array of variables, and essentially
+ *        rewrites the (in)equalities into an array of (in)equalities of the following form,
+ *
+ *        x0 >= f0(x1, x2, ..., xn)
+ *        x0 <= g0(x1, x2, ..., xn)
+ *        x1 >= f1(x2, ..., xn)
+ *        x1 <= g1(x2, ..., xn)
+ *        ...
+ *        xn >= fn()  // just a constant
+ *        xn <= gn()  // just a constant
+ *
+ * \return A map of variables and their solved bounds,
+ *         and constrains that cannot be solved to bounds.
+ */
+PartialSolvedInequalities SolveLinearInequalities(const IntConstraints& system_to_solve);
+
+/*!
+ * \brief Solve linear inequalities and infer the range of each variable.
+ * \param system_to_solve the variables to solve, their ranges, and a list of inequalities.
+ * \return The result ranges for each variables.
+ *         The returned IntConstraints(variables, ranges, relations) contains,
+ *         1. variables  - the variables that have been solved.
+ *         2. ranges     - the best range of each variable.
+ *         3. relations  - constraints that cannot be transformed to
+ *                         Range will be stored in relations.
+ */
+IntConstraints SolveInequalitiesToRange(const IntConstraints& system_to_solve);
+
+/*!
+ * \brief Solve linear inequalities and deskew the ranges towards zero.
+ * \param system_to_solve the variables to solve, their ranges, and a list of inequalities.
+ * \return A transform (src IntConstraints -> dst IntConstraints)
+ *         from original variables to a set of new variables.
+ *         The ranges of new variables always start from zero,
+ *         their extents are solved from \p system_to_solve.
+ *         src IntConstraints is the same as \p system_to_solve.
+ *         dst IntConstraints(variables, ranges, relations) contains,
+ *         1. variables  - the variables that have been solved.
+ *         2. ranges     - the best range (start from zero) of each variable.
+ *         3. relations  - constraints that cannot be transformed to
+ *                         Range will be stored in relations.
+ *         Variable mapping can be obtained from
+ *         IntConstraintsTransform.src_to_dst and IntConstraintsTransform.dst_to_src.
+ */
+IntConstraintsTransform SolveInequalitiesDeskewRange(const IntConstraints& system_to_solve);

Review comment:
`SolveInequalitiesToRange` finds the best range for the inequalities, and stores in
`IntConstraints.ranges`. the reason we need `IntConstraints` instead of `Map<Var, Range>`
is that, there might be some equations/inequalities that we can not deal, we don't silently
drop but store them in `IntConstraints.relations`.

`SolveInequalitiesDeskewRange` does one more step to create new variables which satisfy
the original inequality constraints, yet always starts from zero. This is very useful when
we deal with iteration indices in tvm compute. And maintaining the mapping between old&new
variables is necessary for 1) transform the old expression (tvm compute) to the new. 2) `SolveInequalitiesDeskewRange`
can be run multiple times (until they converge) to get better results, thus a chain of mapping
is needed.

You might have question why can't user invoke `SolveInequalitiesToRange` first and deskew
to zero themselves? It's because variable ranges are solved iteratively, one variable's range
depends on the previous solved range. `FindBestRange of var a  -> Deskew a -> FindBestRange
of var b (given deskewed a) -> Deskew b (given deskewed a)  -> ...` is much more precise
than `FindBestRange of var a  -> FindBestRange of var b (given range a) -> Deskew a
& b independently`.

----------------------------------------------------------------
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.