This is an automated email from the ASF dual-hosted git repository.
tqchen pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/tvm-tirx.git
The following commit(s) were added to refs/heads/main by this push:
new 041dd6d70 [Sym] Enable Z3 fallback for default proof queries (#132)
041dd6d70 is described below
commit 041dd6d7031f1764b8c9eecbfc88d43966f6e545
Author: Lei Wang <[email protected]>
AuthorDate: Fri Oct 30 21:03:43 2026 +0800
[Sym] Enable Z3 fallback for default proof queries (#132)
The default `Analyzer::CanProve` path can miss proofs that were
available through TileLang's TVM fork because it only reaches Z3 at
`SYMBOLIC_BOUND` strength. For example, native analysis cannot prove
`x*x + y*y >= 2*x*y`, although the existing Z3 prover can establish it
under the signed-index arithmetic model.
Use Z3 as the final fallback at every proof strength, including
recursive default queries, after native analysis has not established the
result. Keep symbolic-bound analysis separately gated by
`SYMBOLIC_BOUND`, and retain the existing solver limits and conservative
handling of unknown results. Call sites use the default policy without
an additional option.
Update the existing Z3 tests for the default policy and add coverage for
the nonlinear inequality, its strict-inequality counterexample,
constraint-scope cleanup, cloned resource limits, and builds without Z3.
The unsigned-index scope test now observes native rewriting directly,
since a successful default proof can also come from Z3.
---
include/tvm/sym/analyzer.h | 6 +-
python/tvm_tirx/sym/analyzer.py | 12 +--
src/sym/analyzer.cc | 7 +-
tests/python/sym/test_rewrite_simplify.py | 16 ++--
tests/python/sym/test_z3.py | 128 ++++++++++++++++++++----------
5 files changed, 109 insertions(+), 60 deletions(-)
diff --git a/include/tvm/sym/analyzer.h b/include/tvm/sym/analyzer.h
index 7a1923efa..f59a7acbc 100644
--- a/include/tvm/sym/analyzer.h
+++ b/include/tvm/sym/analyzer.h
@@ -78,7 +78,7 @@ enum DivMode {
* analysis and only use it at top-level simplification to avoid speed issues.
*/
enum class ProofStrength : int {
- /*! \brief Default simplification-based proof, suitable for recursive
analysis. */
+ /*! \brief Default analysis followed by the optional Z3 fallback. */
kDefault = 0,
/*!
* \brief Prove using symbolic bound analysis
@@ -651,13 +651,15 @@ class TVM_TIRX_DLL AnalyzerObj : public ffi::Object {
* \brief Attempt to prove a condition under the current premises.
*
* \param cond The expression to be proved.
- * \param strength Proof effort; stronger modes may use symbolic bounds and
optional Z3.
+ * \param strength Proof effort; kSymbolicBound additionally enables
symbolic bound analysis.
*
* \return True if proved; false includes unsupported or inconclusive
queries.
*
* \note Analyzer will call into sub-analyzers to get the result.
* Do not use strength beyond default in sub-analyzers and
* only use it in top-level predicate analysis.
+ * When built with Z3, all strengths try it after native analysis fails.
+ * Z3's existing resource limit and timeout apply; unknown means cannot
prove.
*/
bool CanProve(const PrimExpr& cond, ProofStrength strength =
ProofStrength::kDefault);
diff --git a/python/tvm_tirx/sym/analyzer.py b/python/tvm_tirx/sym/analyzer.py
index 9a2fdb34f..1123e7a94 100644
--- a/python/tvm_tirx/sym/analyzer.py
+++ b/python/tvm_tirx/sym/analyzer.py
@@ -323,14 +323,16 @@ class Analyzer(tvm_ffi.Object):
The expression.
strength: ProofStrength
- The proof strength. When TVM is built with Z3 (``USE_Z3=ON``), the
- optional Z3 fallback is only consulted at ``SYMBOLIC_BOUND`` or
- higher, after the native analyzers fail to prove the predicate.
+ The proof strength. ``SYMBOLIC_BOUND`` additionally enables
symbolic
+ bound analysis. When built with Z3 (``TVM_TIRX_USE_Z3=ON``), all
+ strengths, including ``DEFAULT``, try Z3 after native analysis
fails
+ to prove the predicate. The existing Z3 timeout and resource limits
+ apply; an unknown solver result means the predicate cannot be
proved.
Returns
-------
- result : Expr
- The result.
+ result : bool
+ Whether the predicate can be proved.
"""
return _ffi_api.AnalyzerCanProve(self, expr, strength)
diff --git a/src/sym/analyzer.cc b/src/sym/analyzer.cc
index b3da3cfde..cf96a3040 100644
--- a/src/sym/analyzer.cc
+++ b/src/sym/analyzer.cc
@@ -313,10 +313,9 @@ bool AnalyzerObj::CanProve(const PrimExpr& expr,
ProofStrength strength) {
}
}
- // Z3 is an expensive best-effort fallback. Gate it behind the higher
- // kSymbolicBound strength so the common kDefault path (including deeply
- // recursive internal CanProve calls) never pays the prover cost.
- if (strength >= ProofStrength::kSymbolicBound &&
z3_prover.CanProve(simplified)) {
+ // Native analysis runs first. Z3 is the final best-effort fallback at every
+ // strength, including default queries from recursive simplification.
+ if (z3_prover.CanProve(simplified)) {
return true;
}
return false;
diff --git a/tests/python/sym/test_rewrite_simplify.py
b/tests/python/sym/test_rewrite_simplify.py
index f22409963..d9555ad7d 100644
--- a/tests/python/sym/test_rewrite_simplify.py
+++ b/tests/python/sym/test_rewrite_simplify.py
@@ -1814,9 +1814,7 @@ if __name__ == "__main__":
def test_allow_uint_as_index():
- """Opt-in no-overflow domain: unsigned index terms are not analyzed by
- default; within allow_uint_as_index() the signed rule set applies and the
- swizzle-style floordiv-quotient bit checks over uint32 offsets
discharge."""
+ """The no-overflow rewrite rules for unsigned indices are scoped."""
w = tirx.Var("w", "int32")
lane = tirx.Var("lane", "int32")
x = tirx.Var("x", "uint32")
@@ -1836,18 +1834,24 @@ def test_allow_uint_as_index():
+ (lane % 8 * 64).astype("uint32")
)
check = flm(fld(s_off, T.uint32(512)), T.uint32(2))
- assert not analyzer.can_prove_equal(check, 0)
+ # Default queries may now use Z3 without this mode. Inspect native
+ # rewriting to test the scope of the no-overflow rewrite rules.
+ unscoped = analyzer.rewrite_simplify(check)
+ assert not tvm_ffi.structural_equal(unscoped, T.uint32(0))
# a non-pow2 divisor never folds, inside or outside the mode... unless
# the flag is on: under the no-overflow assertion any c2 != 0 works.
np2 = flm(x * T.uint32(12), T.uint32(12))
- assert not analyzer.can_prove_equal(np2, 0)
+ assert not tvm_ffi.structural_equal(analyzer.rewrite_simplify(np2),
T.uint32(0))
with tvm_tirx.sym.allow_uint_as_index():
+ assert not tvm_ffi.structural_equal(analyzer.rewrite_simplify(check),
unscoped)
assert analyzer.can_prove_equal(check, 0)
assert analyzer.can_prove_equal(flm(fld(s_off, T.uint32(32)),
T.uint32(2)), 0)
+ assert tvm_ffi.structural_equal(analyzer.rewrite_simplify(np2),
T.uint32(0))
assert analyzer.can_prove_equal(np2, 0)
# nested scopes compose
with tvm_tirx.sym.allow_uint_as_index():
assert analyzer.can_prove_equal(check, 0)
assert analyzer.can_prove_equal(check, 0)
# the mode is scoped: disabled again afterwards
- assert not analyzer.can_prove_equal(check, 0)
+ assert tvm_ffi.structural_equal(analyzer.rewrite_simplify(check), unscoped)
+ assert not tvm_ffi.structural_equal(analyzer.rewrite_simplify(np2),
T.uint32(0))
diff --git a/tests/python/sym/test_z3.py b/tests/python/sym/test_z3.py
index 2be8fae27..bbde37e69 100644
--- a/tests/python/sym/test_z3.py
+++ b/tests/python/sym/test_z3.py
@@ -26,8 +26,8 @@ import tvm_tirx.testing
from tvm_tirx import tirx
from tvm_tirx.sym import Analyzer, ProofStrength
-# The Z3 prover is only consulted at the kSymbolicBound strength so the common
-# default path never pays the prover cost.
+# Both strengths use Z3 after native analysis; SYMBOLIC_BOUND additionally
+# enables symbolic interval reasoning.
SB = ProofStrength.SYMBOLIC_BOUND
@@ -136,10 +136,9 @@ def test_z3_context_clone_lifetime():
# ---------------------------------------------------------------------------
# Examples the native analyzer cannot prove but Z3 can.
#
-# Most cases assert both that the native analyzers (kDefault, Z3 gated off)
-# fail and that Z3 (kSymbolicBound) succeeds. This demonstrates the added value
-# of the Z3 backend and that it is correctly gated behind kSymbolicBound. Cases
-# the native analyzer learns to prove remain here as Z3 translation
regressions.
+# These predicates can use Z3 at both DEFAULT and SYMBOLIC_BOUND. Cases the
+# native analyzer learns to prove remain here as translation regressions.
+# Wide signed arithmetic uses the existing no-overflow index-analysis model.
# ---------------------------------------------------------------------------
@@ -158,7 +157,7 @@ def test_z3_floor_division_identity_constraint():
analyzer_context.append(tvm_tirx.sym.PredicateConstraint(tirx.all(a > 0, b
> 0, c > 0)))
analyzer.sync_constraint_context(analyzer_context)
try:
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
finally:
analyzer_context = parent_context_1
@@ -195,7 +194,7 @@ def test_z3_multiplication_monotonicity():
d = tirx.Var("d", "int32")
expr = implies(tirx.all(a < b, b < c, a * d < b * d), b * d < c * d)
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -255,7 +254,7 @@ def test_z3_select_absolute_value_nonneg():
x = tirx.Var("x", "int32")
expr = tirx.Select(x >= 0, x, -x) >= 0
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -283,7 +282,7 @@ def test_z3_square_expansion_nonneg():
analyzer_context.append(tvm_tirx.sym.PredicateConstraint(tirx.all(a >= 0,
b >= 0)))
analyzer.sync_constraint_context(analyzer_context)
try:
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
finally:
analyzer_context = parent_context_2
@@ -297,7 +296,7 @@ def test_z3_square_monotonicity():
a = tirx.Var("a", "int32")
b = tirx.Var("b", "int32")
expr = implies(tirx.all(0 <= a, a <= b), a * a <= b * b)
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -309,7 +308,7 @@ def test_z3_strict_multiplication():
b = tirx.Var("b", "int32")
d = tirx.Var("d", "int32")
expr = implies(tirx.all(a < b, d > 0), a * d < b * d)
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -321,8 +320,8 @@ def test_z3_floor_division_monotonicity():
b = tirx.Var("b", "int32")
c = tirx.Var("c", "int32")
expr = implies(tirx.all(a <= b, c > 0), tirx.floordiv(a, c) <=
tirx.floordiv(b, c))
- assert not analyzer.can_prove(expr)
analyzer.set_z3_rlimit(0)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -333,7 +332,7 @@ def test_z3_floor_division_lower_bound():
a = tirx.Var("a", "int32")
b = tirx.Var("b", "int32")
expr = implies(b > 0, tirx.floordiv(a, b) * b <= a)
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -344,7 +343,7 @@ def test_z3_floor_modulo_range():
a = tirx.Var("a", "int32")
b = tirx.Var("b", "int32")
expr = implies(b > 0, tirx.all(0 <= tirx.floormod(a, b), tirx.floormod(a,
b) < b))
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -368,8 +367,8 @@ def test_z3_flattened_index_bound():
)
analyzer.sync_constraint_context(analyzer_context)
try:
- assert not analyzer.can_prove(expr)
analyzer.set_z3_rlimit(0)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
finally:
analyzer_context = parent_context_3
@@ -395,7 +394,7 @@ def test_z3_modular_combination():
)
analyzer.sync_constraint_context(analyzer_context)
try:
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
finally:
analyzer_context = parent_context_4
@@ -407,7 +406,7 @@ def test_z3_square_non_negative():
_require_z3(analyzer)
a = tirx.Var("a", "int32")
- assert not analyzer.can_prove(a * a >= 0)
+ assert analyzer.can_prove(a * a >= 0)
assert analyzer.can_prove(a * a >= 0, SB)
@@ -417,7 +416,7 @@ def test_z3_min_max_average_bounds():
a = tirx.Var("a", "int32")
b = tirx.Var("b", "int32")
- assert not analyzer.can_prove(tirx.max(a, b) * 2 >= a + b)
+ assert analyzer.can_prove(tirx.max(a, b) * 2 >= a + b)
assert analyzer.can_prove(tirx.max(a, b) * 2 >= a + b, SB)
assert analyzer.can_prove(tirx.min(a, b) * 2 <= a + b, SB)
@@ -438,8 +437,17 @@ def test_z3_symbolic_bind_range_with_constraint():
analyzer_context.append(tvm_tirx.sym.PredicateConstraint(n <= 8))
analyzer.sync_constraint_context(analyzer_context)
try:
+ # Z3 does not restrict x to an empty range, and n <= 8 still permits
+ # n <= 0. Default fallback does not enable symbolic-bound analysis.
assert not analyzer.can_prove(x < 8)
assert analyzer.can_prove(x < 8, SB)
+ positive_context = analyzer_context.snapshot()
+ positive_context.append(tvm_tirx.sym.PredicateConstraint(n > 0))
+ analyzer.sync_constraint_context(positive_context)
+ try:
+ assert analyzer.can_prove(x < 8)
+ finally:
+ analyzer.sync_constraint_context(analyzer_context)
finally:
analyzer_context = parent_context_5
analyzer.sync_constraint_context(analyzer_context)
@@ -452,7 +460,7 @@ def test_z3_equality_congruence():
a = tirx.Var("a", "int32")
b = tirx.Var("b", "int32")
expr = implies(a == b, a * a == b * b)
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -465,7 +473,7 @@ def test_z3_integer_strict_transitivity():
c = tirx.Var("c", "int32")
# Over the integers, a < b and b < c implies a + 1 < c.
expr = implies(tirx.all(a < b, b < c), a + 1 < c)
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -475,7 +483,7 @@ def test_z3_if_then_else_absolute_value():
x = tirx.Var("x", "int32")
expr = tirx.if_then_else(x >= 0, x, -x) >= 0
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -484,7 +492,7 @@ def test_z3_unsigned_non_negative():
_require_z3(analyzer)
u = tirx.Var("u", "uint32")
- assert not analyzer.can_prove(u >= 0)
+ assert analyzer.can_prove(u >= 0)
assert analyzer.can_prove(u >= 0, SB)
@@ -494,7 +502,7 @@ def test_z3_unsigned64_non_negative():
_require_z3(analyzer)
u = tirx.Var("u", "uint64")
- assert not analyzer.can_prove(u >= 0)
+ assert analyzer.can_prove(u >= 0)
assert analyzer.can_prove(u >= 0, SB)
@@ -511,7 +519,7 @@ def test_z3_int64_square_expansion():
analyzer_context.append(tvm_tirx.sym.PredicateConstraint(tirx.all(a >= 0,
b >= 0)))
analyzer.sync_constraint_context(analyzer_context)
try:
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
finally:
analyzer_context = parent_context_6
@@ -525,7 +533,7 @@ def test_z3_boolean_variable_reasoning():
p = tirx.Var("p", "bool")
q = tirx.Var("q", "bool")
expr = implies(tirx.And(p, q), tirx.Or(p, q))
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -536,7 +544,7 @@ def test_z3_not_equal_from_strict_less():
x = tirx.Var("x", "int32")
y = tirx.Var("y", "int32")
expr = implies(x < y, tirx.NE(x, y))
- assert not analyzer.can_prove(expr)
+ assert analyzer.can_prove(expr)
assert analyzer.can_prove(expr, SB)
@@ -547,7 +555,7 @@ def test_z3_let_expression():
y = tirx.Var("y", "int32")
t = tirx.Var("t", "int32")
let = tirx.Let(t, y * 2, t)
- assert not analyzer.can_prove(let == y * 2)
+ assert analyzer.can_prove(let == y * 2)
assert analyzer.can_prove(let == y * 2, SB)
@@ -884,26 +892,60 @@ def test_z3_repeated_can_prove_is_consistent():
assert analyzer.can_prove(x >= 5, SB)
-def test_z3_is_gated_behind_symbolic_bound():
- # The Z3 fallback must not run at the default strength.
+def test_z3_default_fallback_nonlinear_inequality():
+ analyzer = Analyzer()
+ x = tirx.Var("x", "int32")
+ y = tirx.Var("y", "int32")
+ # x*x + y*y - 2*x*y == (x-y)**2 >= 0 in the mathematical integer
+ # model used for wide signed indices. This does not model int32 overflow.
+ # A fresh analyzer must prove this without an option or explicit strength
+ # when Z3 is available. Native analysis alone cannot currently prove it.
+ expr = x * x + y * y >= 2 * (x * y)
+ assert analyzer.can_prove(expr) == analyzer.is_z3_enabled
+ assert analyzer.can_prove(x == x)
+ # Equality at x == y is a counterexample to the strict inequality.
+ assert not analyzer.can_prove(x * x + y * y > 2 * (x * y))
+
+
+def test_z3_default_fallback_clone_preserves_independent_resource_limit():
analyzer = Analyzer()
- analyzer_context = tvm_tirx.sym.ConstraintContext()
_require_z3(analyzer)
+ x = tirx.Var("x", "int32")
+ y = tirx.Var("y", "int32")
+ expr = x * x + y * y >= 2 * (x * y)
+ analyzer.set_z3_rlimit(1)
+ cloned = analyzer.clone()
+ analyzer.set_z3_rlimit(0)
+ assert analyzer.can_prove(expr)
+ assert not cloned.can_prove(expr)
+ assert cloned.can_prove(x == x)
+ assert Analyzer().can_prove(expr)
- a = tirx.Var("a", "int32")
- b = tirx.Var("b", "int32")
- c = tirx.Var("c", "int32")
- expr = ((b - a) // c) * c + a <= b
- parent_context_11 = analyzer_context
- analyzer_context = analyzer_context.snapshot()
- analyzer_context.append(tvm_tirx.sym.PredicateConstraint(tirx.all(a > 0, b
> 0, c > 0)))
- analyzer.sync_constraint_context(analyzer_context)
+
+def test_z3_default_fallback_scopes_and_resource_limit():
+ analyzer = Analyzer()
+ _require_z3(analyzer)
+ x = tirx.Var("x", "int32")
+ positive_square = x * x > 0
+ # In the signed-index arithmetic model, x != 0 is sufficient and x == 0
+ # is a counterexample. The constraint must not survive its scope.
+ assert not analyzer.can_prove(positive_square)
+ parent_context = tvm_tirx.sym.ConstraintContext()
+ child_context = parent_context.snapshot()
+ child_context.append(tvm_tirx.sym.PredicateConstraint(x != 0))
+ analyzer.sync_constraint_context(child_context)
try:
- assert not analyzer.can_prove(expr, ProofStrength.DEFAULT)
- assert analyzer.can_prove(expr, SB)
+ assert analyzer.can_prove(positive_square)
finally:
- analyzer_context = parent_context_11
- analyzer.sync_constraint_context(analyzer_context)
+ analyzer.sync_constraint_context(parent_context)
+ assert not analyzer.can_prove(positive_square)
+
+ limited = Analyzer()
+ limited.set_z3_rlimit(1)
+ a, b = tirx.Var("a", "int32"), tirx.Var("b", "int32")
+ assert not limited.can_prove(a * a + b * b >= 2 * a * b)
+ # A native literal proof still succeeds before the exhausted SMT fallback.
+ assert limited.can_prove(a == a)
# ---------------------------------------------------------------------------