The GitHub Actions job "tvm-bot" on tvm.git/main has succeeded. Run started by GitHub user cchung100m (triggered by cchung100m).
Head commit for run: 96b825700288d568ca6ea67351c0b035f7170f43 / Hongyi Jin <[email protected]> [Arith] Memoize IntervalSet variable relaxation to avoid exponential blowup (#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). Co-authored-by: Claude Opus 4.8 <[email protected]> Report URL: https://github.com/apache/tvm/actions/runs/26953313533 With regards, GitHub Actions via GitBox --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
