jinhongyii opened a new pull request, #19670:
URL: https://github.com/apache/tvm/pull/19670
## Problem
`Analyzer::Bind` could hang indefinitely (>300s, ~200% CPU, no GPU work)
while binding a small expression for one variable. The root cause is general
and lives in `src/arith/int_set.cc`.
Diagnosis: 100% of the time is spent in `arith::Analyzer::Bind` →
`IntSetAnalyzer` → `IntervalSetEvaluator`, evaluating a **5-node** bound
expression. A counter showed **>2^20 `VisitExpr` calls at recursion depth 67**
with no end in sight.
## Root cause
`IntervalSetEvaluator::VisitExpr_(VarNode)` relaxes a variable's bounds by
recursively evaluating **both** the `min` and `max` sub-expressions of its
mapped interval. For diamond-shaped variable dependency chains (`a → {b, c}`,
`b → {d, e}`, …) the shared sub-expressions are re-expanded along every path,
so cost is **O(2^depth)** in the length of the dependency chain — bounded only
by `dom_map_.size()` (~67 interdependent vars in the failing case).
## Fix
Memoize the fully-relaxed interval **per variable** (`relax_memo_`) and
break cyclic dependencies with an in-progress set (`relax_in_progress_`). A
variable's relaxed interval is deterministic for a given evaluator instance
(`dom_map_`/`dom_constraints_` are fixed), so memoizing collapses the diamonds
to linear cost. Short chains — the common case, which never reached the old
`recur_depth_ >= dom_map_.size()` cutoff — are unaffected, so the change is
behavior-preserving outside the pathological case.
## Tests
New regression tests in `tests/python/arith/test_arith_intset.py`:
- `test_relax_deep_variable_dependency_chain` — a 64-deep diamond (`O(2^64)`
without the fix; verified to hang on a clean build), also asserting the relaxed
result is correct (`x0 → [-n, 100+n]`).
- `test_relax_cyclic_variable_dependency` — a cyclic `x↔y` dependency must
terminate.
## Verification
- `tests/python/arith/test_arith_intset.py` — 20 passed (the deep-chain test
completes instantly).
- Full `tests/python/arith/` — 933 passed (1 pre-existing flaky random-seed
failure in `test_arith_solve_linear_equations.py` unrelated to this change,
passes on rerun).
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
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]
