gemini-code-assist[bot] commented on code in PR #19670:
URL: https://github.com/apache/tvm/pull/19670#discussion_r3352682601
##########
tests/python/arith/test_arith_intset.py:
##########
@@ -394,5 +394,35 @@ def test_modular_set():
)
+def test_relax_deep_variable_dependency_chain():
+ """Regression test for exponential variable-relaxation blowup.
+
+ When a variable's interval bound references another variable that is also
in
+ the domain map, the evaluator relaxes it transitively. A diamond-shaped
+ chain -- where each variable's bound references the next one in *both* its
+ min and its max -- used to be re-expanded along every path, costing
+ O(2^depth) and hanging indefinitely. The relaxation is now memoized per
+ variable, so this completes in linear time.
+ """
+ ck = IntSetChecker()
+ n = 64 # 2^64 expansions without memoization; trivially fast with it.
+ xs = [tvm.tirx.Var(f"x{i}", "int32") for i in range(n + 1)]
+ dmap = {xs[i]: tvm.arith.IntervalSet(xs[i + 1] - 1, xs[i + 1] + 1) for i
in range(n)}
+ dmap[xs[n]] = tvm.arith.IntervalSet(0, 100)
+ # x0 relaxes through the whole chain: [0 - n, 100 + n].
+ ck.verify(xs[0], dmap, (-n, 100 + n))
+
+
+def test_relax_cyclic_variable_dependency():
+ """A cyclic variable dependency must terminate (and stay symbolic)."""
+ ana = tvm.arith.Analyzer()
+ x = tvm.tirx.Var("x", "int32")
+ y = tvm.tirx.Var("y", "int32")
+ # x depends on y and y depends on x: relaxation must not loop forever.
+ dmap = {x: tvm.arith.IntervalSet(y, y), y: tvm.arith.IntervalSet(x, x)}
+ res = ana.int_set(x, dmap)
+ assert res is not None
Review Comment:
Instead of just asserting `res is not None`, we can use the existing
`IntSetChecker` helper to verify that the cyclic dependency correctly
terminates and resolves to the expected symbolic interval `(y, y)`. This makes
the test assertion much stronger and more precise.
```suggestion
def test_relax_cyclic_variable_dependency():
"""A cyclic variable dependency must terminate (and stay symbolic)."""
ck = IntSetChecker()
x = tvm.tirx.Var("x", "int32")
y = tvm.tirx.Var("y", "int32")
# x depends on y and y depends on x: relaxation must not loop forever.
dmap = {x: tvm.arith.IntervalSet(y, y), y: tvm.arith.IntervalSet(x, x)}
ck.verify(x, dmap, (y, y))
```
--
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.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
