You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tvm.apache.org by GitBox <gi...@apache.org> on 2020/06/24 18:21:21 UTC
[GitHub] [incubator-tvm] ANSHUMAN87 commented on a change in pull request #5618: [Arith] Inequalities solver
ANSHUMAN87 commented on a change in pull request #5618:
URL: https://github.com/apache/incubator-tvm/pull/5618#discussion_r445020887
##########
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);
Review comment:
As the API does not produce Range type, may be we change the name SolveInequalitiesToRange() --> SolveInequalities()
##########
File path: tests/python/unittest/test_arith_solve_linear_inequality.py
##########
@@ -0,0 +1,187 @@
+# 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.
+import random
+import sys
+import pytest
+import tvm
+from tvm import te, arith, ir, tir, testing
+
+
+def test_solution_consistency():
+ seed = random.randrange(sys.maxsize)
+ print("\nThis test is intentionally non-deterministic, "
+ "if it fails please report it in github issue together with this seed {}\n".format(seed))
+ random.seed(seed)
+
+ def _check(variables, formulas, coef=(-5, 5), bounds=(-20, 20)):
+ vs = [te.var("x" + str(i)) for i in range(variables)]
+
+ fs = []
+ for i in range(formulas):
+ s1 = sum([v*random.randint(coef[0], coef[1]) for v in vs])
+ s1 += random.randint(coef[0], coef[1])
+ s2 = sum([v*random.randint(coef[0], coef[1]) for v in vs])
+ s2 += random.randint(coef[0], coef[1])
+ op = random.choice([tir.expr.EQ, tir.expr.LE, tir.expr.LT, tir.expr.GE, tir.expr.GT])
+ fs.append(op(s1, s2))
+
+ vranges = {v: tvm.ir.expr.Range(bounds[0], bounds[1] + 1) for v in vs}
+ before = te.all(tir.const(1, 'bool'), *fs)
+ after = arith._ffi_api.SolveInequalitiesAsCondition(vs, vranges, fs)
+ after = te.all(tir.const(1, 'bool'), *after)
+ testing.check_bool_expr_is_true(before == after, vranges)
+
+ solution = arith.solve_linear_inequalities(fs, vs, vranges, deskew_range=True)
+ testing.check_int_constraints_trans_consistency(solution)
+
+ for i in range(3):
+ _check(1, 1)
+ for i in range(3):
+ _check(1, 2)
+
+ for i in range(3):
+ _check(2, 1)
+ for i in range(3):
+ _check(2, 2)
+ for i in range(3):
+ _check(2, 3)
+
+ # Somewhere here coefficients in the results become too large, leading to overflow,
+ # so we use smaller initial coefficients
+ for i in range(5):
+ _check(3, 3, coef=(-2, 2))
+ for i in range(5):
+ _check(3, 4, coef=(-2, 2))
+
+ for i in range(5):
+ _check(4, 3, coef=(-1, 1))
+
+ for i in range(5):
+ _check(10, 2, coef=(-1, 1), bounds=(0, 4))
+ for i in range(5):
+ _check(10, 3, coef=(0, 1), bounds=(0, 4))
+
+
+def test_dual_variable():
+ x, y = te.var("x"), te.var("y")
+
+ variables = [x, y]
+ ranges = {
+ x: tvm.ir.Range(-100, 100),
+ y: tvm.ir.Range(0, 10),
+ }
+ problem = [
+ tvm.tir.LE(x + y, 20),
+ tvm.tir.GE(x - y, 10),
+ ]
+
+ # solution as conditions
+ solution = arith._ffi_api.SolveInequalitiesAsCondition(variables, ranges, problem)
+ assert ir.structural_equal(solution[0], x >= (y + 10))
+ assert ir.structural_equal(solution[1], x <= (20 - y))
+ assert ir.structural_equal(solution[2], y >= 0)
+ assert ir.structural_equal(solution[3], y <= 5)
+
+ # solve and get the ranges
+ solution = arith.solve_linear_inequalities([
+ tvm.tir.LE(x + y, 20),
+ tvm.tir.GE(x - y, 10),
+ ], [x, y], ranges)
+ # 0 <= y <=5
+ assert solution.ranges[y].min == 0
+ assert solution.ranges[y].extent == 6
+ # y + 10 <= x <= 20 - y
+ assert ir.structural_equal(solution.ranges[x].min, y + 10)
+ assert solution.ranges[x].extent == 11 # max(10 - 2y)
+
+ # deskew the solved ranges to be starting from zero
+ solution = arith.solve_linear_inequalities(problem, variables, ranges, deskew_range=True)
+ [x_new, y_new] = solution.dst.variables
+ [rel] = solution.dst.relations
+ assert ir.structural_equal(rel, (y_new*2) + x_new <= 10)
+ assert ir.structural_equal(solution.dst.ranges[x_new].min, 0)
+ assert ir.structural_equal(solution.dst.ranges[x_new].extent, 11)
+ assert ir.structural_equal(solution.dst.ranges[y_new].min, 0)
+ assert ir.structural_equal(solution.dst.ranges[y_new].extent, 6)
+ assert ir.structural_equal(solution.src_to_dst[x], x_new + (y_new + 10))
+ assert ir.structural_equal(solution.src_to_dst[y], y_new)
+ assert ir.structural_equal(solution.dst_to_src[x_new], x - y - 10)
+ assert ir.structural_equal(solution.dst_to_src[y_new], y)
+
+
+def test_equal():
+ x, y = te.var("x"), te.var("y")
+ problem = [
+ tvm.tir.GE(x + y, 10),
+ tvm.tir.GE(x - y, 2),
+ tvm.tir.LE(x, 6),
+ ]
+
+ solution = arith.solve_linear_inequalities(problem, [x, y])
+ assert solution.ranges[x].min == 6
+ assert solution.ranges[x].extent == 1
+ assert solution.ranges[y].min == 4
+ assert solution.ranges[y].extent == 1
+
+ solution = arith.solve_linear_inequalities(problem, [x, y], deskew_range=True)
+ assert len(solution.dst.variables) == 0
+ assert len(solution.dst.ranges) == 0
+ assert len(solution.dst.relations) == 0
+ assert solution.src_to_dst[x] == 6
+ assert solution.src_to_dst[y] == 4
+
+
+def test_multi_equal():
+ x, y, z = te.var("x"), te.var("y"), te.var("z")
+ problem = [
+ tvm.tir.LE(x, 6),
+ tvm.tir.GE(x, 6),
+ tvm.tir.GE(x - z * y, 0),
+ tvm.tir.LE(x - z * y, 0),
+ ]
+
+ solution = arith.solve_linear_inequalities(problem, [x, y, z])
+ assert solution.ranges[x].min == 6
+ assert solution.ranges[x].extent == 1
+
+ solution = arith.solve_linear_inequalities(problem, [x, y, z], deskew_range=True)
+ assert solution.src_to_dst[y] == y
+ assert solution.src_to_dst[z] == z
+ assert solution.src_to_dst[x] == 6
+
+
+def test_no_solution():
+ x = te.var("x0")
+ vranges = {x: tvm.ir.Range.make_by_min_extent(-20, 41)}
+ problem = [-x - 4 <= -5*x + 2, x*4 + 5 <= x*5]
Review comment:
No solution with more variables can be added.
##########
File path: src/arith/analyzer.cc
##########
@@ -115,11 +115,15 @@ bool Analyzer::CanProve(const PrimExpr& expr) {
return false;
}
-PrimExpr Analyzer::Simplify(const PrimExpr& expr) {
+PrimExpr Analyzer::Simplify(const PrimExpr& expr, size_t steps) {
Review comment:
steps is not exposed to user controlled now in packed func. May be we need to handle that?
##########
File path: python/tvm/testing.py
##########
@@ -188,5 +189,96 @@ def assert_prim_expr_equal(lhs, rhs):
raise ValueError("{} and {} are not equal".format(lhs, rhs))
+def check_bool_expr_is_true(bool_expr, vranges, cond=None):
+ """ Check that bool_expr holds given the condition cond
+ for every value of free variables from vranges.
+
+ Parameters
+ ----------
+ bool_expr : tvm.ir.expr.PrimExpr
+ Boolean expression to check
+ vranges: Dict[tvm.tir.expr.Var, tvm.ir.Range]
+ Free variables and their ranges
+ cond: tvm.ir.expr.PrimExpr
+ extra conditions needs to be satisfied.
+ """
+ if cond is not None:
+ bool_expr = tvm.te.any(tvm.tir.Not(cond), bool_expr)
Review comment:
Why Not(cond) ? The description contradicts i think. Please check once.
##########
File path: tests/python/unittest/test_arith_solve_linear_inequality.py
##########
@@ -0,0 +1,187 @@
+# 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.
+import random
+import sys
+import pytest
+import tvm
+from tvm import te, arith, ir, tir, testing
+
+
+def test_solution_consistency():
+ seed = random.randrange(sys.maxsize)
+ print("\nThis test is intentionally non-deterministic, "
+ "if it fails please report it in github issue together with this seed {}\n".format(seed))
+ random.seed(seed)
+
+ def _check(variables, formulas, coef=(-5, 5), bounds=(-20, 20)):
+ vs = [te.var("x" + str(i)) for i in range(variables)]
+
+ fs = []
+ for i in range(formulas):
+ s1 = sum([v*random.randint(coef[0], coef[1]) for v in vs])
+ s1 += random.randint(coef[0], coef[1])
+ s2 = sum([v*random.randint(coef[0], coef[1]) for v in vs])
+ s2 += random.randint(coef[0], coef[1])
+ op = random.choice([tir.expr.EQ, tir.expr.LE, tir.expr.LT, tir.expr.GE, tir.expr.GT])
+ fs.append(op(s1, s2))
+
+ vranges = {v: tvm.ir.expr.Range(bounds[0], bounds[1] + 1) for v in vs}
+ before = te.all(tir.const(1, 'bool'), *fs)
+ after = arith._ffi_api.SolveInequalitiesAsCondition(vs, vranges, fs)
+ after = te.all(tir.const(1, 'bool'), *after)
+ testing.check_bool_expr_is_true(before == after, vranges)
+
+ solution = arith.solve_linear_inequalities(fs, vs, vranges, deskew_range=True)
+ testing.check_int_constraints_trans_consistency(solution)
+
+ for i in range(3):
+ _check(1, 1)
+ for i in range(3):
+ _check(1, 2)
+
+ for i in range(3):
+ _check(2, 1)
+ for i in range(3):
+ _check(2, 2)
+ for i in range(3):
+ _check(2, 3)
+
+ # Somewhere here coefficients in the results become too large, leading to overflow,
+ # so we use smaller initial coefficients
+ for i in range(5):
+ _check(3, 3, coef=(-2, 2))
+ for i in range(5):
+ _check(3, 4, coef=(-2, 2))
+
+ for i in range(5):
+ _check(4, 3, coef=(-1, 1))
+
+ for i in range(5):
+ _check(10, 2, coef=(-1, 1), bounds=(0, 4))
+ for i in range(5):
+ _check(10, 3, coef=(0, 1), bounds=(0, 4))
+
+
+def test_dual_variable():
+ x, y = te.var("x"), te.var("y")
+
+ variables = [x, y]
+ ranges = {
+ x: tvm.ir.Range(-100, 100),
+ y: tvm.ir.Range(0, 10),
+ }
+ problem = [
+ tvm.tir.LE(x + y, 20),
+ tvm.tir.GE(x - y, 10),
+ ]
+
+ # solution as conditions
+ solution = arith._ffi_api.SolveInequalitiesAsCondition(variables, ranges, problem)
+ assert ir.structural_equal(solution[0], x >= (y + 10))
+ assert ir.structural_equal(solution[1], x <= (20 - y))
+ assert ir.structural_equal(solution[2], y >= 0)
+ assert ir.structural_equal(solution[3], y <= 5)
+
+ # solve and get the ranges
+ solution = arith.solve_linear_inequalities([
+ tvm.tir.LE(x + y, 20),
+ tvm.tir.GE(x - y, 10),
+ ], [x, y], ranges)
+ # 0 <= y <=5
+ assert solution.ranges[y].min == 0
+ assert solution.ranges[y].extent == 6
+ # y + 10 <= x <= 20 - y
+ assert ir.structural_equal(solution.ranges[x].min, y + 10)
+ assert solution.ranges[x].extent == 11 # max(10 - 2y)
+
+ # deskew the solved ranges to be starting from zero
+ solution = arith.solve_linear_inequalities(problem, variables, ranges, deskew_range=True)
+ [x_new, y_new] = solution.dst.variables
+ [rel] = solution.dst.relations
+ assert ir.structural_equal(rel, (y_new*2) + x_new <= 10)
+ assert ir.structural_equal(solution.dst.ranges[x_new].min, 0)
+ assert ir.structural_equal(solution.dst.ranges[x_new].extent, 11)
+ assert ir.structural_equal(solution.dst.ranges[y_new].min, 0)
+ assert ir.structural_equal(solution.dst.ranges[y_new].extent, 6)
+ assert ir.structural_equal(solution.src_to_dst[x], x_new + (y_new + 10))
+ assert ir.structural_equal(solution.src_to_dst[y], y_new)
+ assert ir.structural_equal(solution.dst_to_src[x_new], x - y - 10)
+ assert ir.structural_equal(solution.dst_to_src[y_new], y)
+
+
+def test_equal():
+ x, y = te.var("x"), te.var("y")
+ problem = [
+ tvm.tir.GE(x + y, 10),
+ tvm.tir.GE(x - y, 2),
+ tvm.tir.LE(x, 6),
+ ]
+
+ solution = arith.solve_linear_inequalities(problem, [x, y])
+ assert solution.ranges[x].min == 6
+ assert solution.ranges[x].extent == 1
+ assert solution.ranges[y].min == 4
+ assert solution.ranges[y].extent == 1
+
+ solution = arith.solve_linear_inequalities(problem, [x, y], deskew_range=True)
+ assert len(solution.dst.variables) == 0
+ assert len(solution.dst.ranges) == 0
+ assert len(solution.dst.relations) == 0
+ assert solution.src_to_dst[x] == 6
+ assert solution.src_to_dst[y] == 4
+
+
+def test_multi_equal():
+ x, y, z = te.var("x"), te.var("y"), te.var("z")
+ problem = [
+ tvm.tir.LE(x, 6),
+ tvm.tir.GE(x, 6),
+ tvm.tir.GE(x - z * y, 0),
+ tvm.tir.LE(x - z * y, 0),
+ ]
+
+ solution = arith.solve_linear_inequalities(problem, [x, y, z])
Review comment:
Can we add validation for relation as well?
##########
File path: include/tvm/arith/analyzer.h
##########
@@ -464,11 +464,16 @@ class TVM_DLL Analyzer {
* \brief Simplify expr.
*
* \param expr The expression to be simplified.
+ * \param steps The simplification runs in the order of
+ * rewrite_simplify (step 1) -> canonical_simplify (step 2) ->
+ * rewrite_simplify (step 3) -> canonical_simplify (step 4) -> ...
+ * param steps controls how many steps to run.
+ * Default is 2, i.e., rewrite_simplify + canonical_simplify.
* \return The result.
*
* \note Analyzer will call into sub-analyzers to get the result.
*/
- PrimExpr Simplify(const PrimExpr& expr);
+ PrimExpr Simplify(const PrimExpr& expr, size_t steps = 2);
Review comment:
May be size_t -> int ? (I think integer would be sufficient in this case).
##########
File path: tests/python/unittest/test_arith_solve_linear_inequality.py
##########
@@ -0,0 +1,187 @@
+# 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.
+import random
+import sys
+import pytest
+import tvm
+from tvm import te, arith, ir, tir, testing
+
+
+def test_solution_consistency():
+ seed = random.randrange(sys.maxsize)
+ print("\nThis test is intentionally non-deterministic, "
+ "if it fails please report it in github issue together with this seed {}\n".format(seed))
+ random.seed(seed)
+
+ def _check(variables, formulas, coef=(-5, 5), bounds=(-20, 20)):
+ vs = [te.var("x" + str(i)) for i in range(variables)]
+
+ fs = []
+ for i in range(formulas):
+ s1 = sum([v*random.randint(coef[0], coef[1]) for v in vs])
+ s1 += random.randint(coef[0], coef[1])
+ s2 = sum([v*random.randint(coef[0], coef[1]) for v in vs])
+ s2 += random.randint(coef[0], coef[1])
+ op = random.choice([tir.expr.EQ, tir.expr.LE, tir.expr.LT, tir.expr.GE, tir.expr.GT])
+ fs.append(op(s1, s2))
+
+ vranges = {v: tvm.ir.expr.Range(bounds[0], bounds[1] + 1) for v in vs}
+ before = te.all(tir.const(1, 'bool'), *fs)
+ after = arith._ffi_api.SolveInequalitiesAsCondition(vs, vranges, fs)
+ after = te.all(tir.const(1, 'bool'), *after)
+ testing.check_bool_expr_is_true(before == after, vranges)
+
+ solution = arith.solve_linear_inequalities(fs, vs, vranges, deskew_range=True)
+ testing.check_int_constraints_trans_consistency(solution)
+
+ for i in range(3):
+ _check(1, 1)
+ for i in range(3):
+ _check(1, 2)
+
+ for i in range(3):
+ _check(2, 1)
+ for i in range(3):
+ _check(2, 2)
+ for i in range(3):
+ _check(2, 3)
+
+ # Somewhere here coefficients in the results become too large, leading to overflow,
+ # so we use smaller initial coefficients
+ for i in range(5):
+ _check(3, 3, coef=(-2, 2))
+ for i in range(5):
+ _check(3, 4, coef=(-2, 2))
+
+ for i in range(5):
+ _check(4, 3, coef=(-1, 1))
+
+ for i in range(5):
+ _check(10, 2, coef=(-1, 1), bounds=(0, 4))
+ for i in range(5):
+ _check(10, 3, coef=(0, 1), bounds=(0, 4))
+
+
+def test_dual_variable():
+ x, y = te.var("x"), te.var("y")
+
+ variables = [x, y]
+ ranges = {
+ x: tvm.ir.Range(-100, 100),
+ y: tvm.ir.Range(0, 10),
+ }
+ problem = [
+ tvm.tir.LE(x + y, 20),
+ tvm.tir.GE(x - y, 10),
+ ]
+
+ # solution as conditions
+ solution = arith._ffi_api.SolveInequalitiesAsCondition(variables, ranges, problem)
+ assert ir.structural_equal(solution[0], x >= (y + 10))
+ assert ir.structural_equal(solution[1], x <= (20 - y))
+ assert ir.structural_equal(solution[2], y >= 0)
+ assert ir.structural_equal(solution[3], y <= 5)
+
+ # solve and get the ranges
+ solution = arith.solve_linear_inequalities([
Review comment:
maybe use problem ?
##########
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:
Same as above comment.
I have one small query here. Why do we actually need IntConstraintsTransform ?
Is there any case, we need to retain the previous mapping?
##########
File path: include/tvm/arith/int_solver.h
##########
@@ -26,17 +26,110 @@
#include <tvm/ir/expr.h>
#include <tvm/tir/expr.h>
+#include <tvm/tir/op.h>
#include <unordered_map>
+#include <utility>
#include <vector>
+#include "analyzer.h"
+
namespace tvm {
namespace arith {
using tir::IterVar;
using tir::Var;
using tir::VarNode;
+/*!
+ * \brief Represent integer grouped bounds which are classified into
+ * lower bounds (inclusive), upper bounds (inclusive) and equalities.
+ * It also contains coefficient as a multiplier for the bounds, i.e.,
+ * coef * var >= lower
+ * coef * var == equal
+ * coef * var <= upper
+ * \sa IntGrpBounds
+ */
+class IntGrpBoundsNode : public Object {
+ public:
+ PrimExpr coef;
+ Array<PrimExpr> lower;
+ Array<PrimExpr> equal;
+ Array<PrimExpr> upper;
+
+ void VisitAttrs(tvm::AttrVisitor* v) {
+ v->Visit("coef", &coef);
+ v->Visit("lower", &lower);
+ v->Visit("equal", &equal);
+ v->Visit("upper", &upper);
+ }
+
+ bool SEqualReduce(const IntGrpBoundsNode* other, SEqualReducer eq) const {
+ return eq(coef, other->coef) && eq(lower, other->lower) && eq(equal, other->equal) &&
+ eq(upper, other->upper);
+ }
+
+ void SHashReduce(SHashReducer hash_reduce) const {
+ hash_reduce(coef);
+ hash_reduce(lower);
+ hash_reduce(equal);
+ hash_reduce(upper);
+ }
+
+ static constexpr const bool _type_has_method_sequal_reduce = true;
+ static constexpr const char* _type_key = "arith.IntGrpBounds";
+ TVM_DECLARE_FINAL_OBJECT_INFO(IntGrpBoundsNode, Object);
+};
+
+/*!
+ * \brief Managed reference to IntGrpBoundsNode.
+ * \sa IntGrpBoundsNode
+ */
+class IntGrpBounds : public ObjectRef {
+ public:
+ /*!
+ * \brief Constructor by fields
+ * \param coef The coefficient. Must be integer.
+ * coef * var >= lower
+ * coef * var == equal
+ * coef * var >= upper
+ * \param lower the lower bounds (include)
+ * \param equal equalities
+ * \param upper the upper bounds (include)
+ */
+ TVM_DLL IntGrpBounds(PrimExpr coef, Array<PrimExpr> lower, Array<PrimExpr> equal,
+ Array<PrimExpr> upper);
+
+ /*!
+ * \brief Construct bounds from a range.
+ * \param r The range
+ * \return constructed bounds.
+ */
+ static IntGrpBounds range(const Range& r);
Review comment:
Maybe range --> CreateIntGrpBounds (Or something like that, as we are creating Bounds from Range)?
##########
File path: python/tvm/testing.py
##########
@@ -188,5 +189,96 @@ def assert_prim_expr_equal(lhs, rhs):
raise ValueError("{} and {} are not equal".format(lhs, rhs))
+def check_bool_expr_is_true(bool_expr, vranges, cond=None):
+ """ Check that bool_expr holds given the condition cond
+ for every value of free variables from vranges.
+
+ Parameters
+ ----------
+ bool_expr : tvm.ir.expr.PrimExpr
Review comment:
nit: tvm.ir.expr.PrimExpr -> tvm.ir.PrimExpr
Please handle for other similar cases too :)
----------------------------------------------------------------
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:
users@infra.apache.org