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, but always starts from zero.
This is very useful when we deal with iteration indices in tvm compute. And
maintaining the transform 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 transform 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.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
