tqchen opened a new pull request, #18886:
URL: https://github.com/apache/tvm/pull/18886
## Summary
Clean-room rewrite of TIR Common Subexpression Elimination (CSE) using a
two-phase architecture:
- **Phase 1 — CSEPlanner**: Read-only visitor that builds a scope tree and
expression DAG. Computes a plan (InsertBeforeTable + ExprRemapTable) in a
single pass using shallower-first processing with repr propagation — no cascade
loop needed.
- **Phase 2 — CSERewriter**: Mechanical mutator that inserts `Bind(cse_var,
expr)` statements and substitutes expressions per the plan.
Key improvements over the old implementation:
- **Simpler architecture**: Two clean classes (planner + rewriter) instead
of interleaved analysis/mutation
- **No cascade loop**: Shallower-first processing with repr propagation
resolves all CSE opportunities in one plan + one rewrite
- **Incremental DAG construction**: Expression depth, children, and consumed
counts computed during bottom-up scan — no separate traversals
- **No single-use bindings**: Consumed count tracking avoids introducing
bindings that would only be used once
- **Unified insertion via VisitStmt**: SeqStmt flattening handles all
insertion contexts uniformly
Other changes:
- Rename `CommonSubexprElimTIR` → `CommonSubexprElim`, remove
`enable_cse_tir` and `identify_equiv_terms` params
- Move old CSE tools (used by cache_index) to `cache_index_helpers.{cc,h}`
- Remove unused `arith.detect_common_subexpr` API
- Add `T.bind` as lowercase alias for `T.Bind`
## Test plan
- [x] 15 test cases covering: basic CSE, if-branch scoping, cascade,
for-loop, hoisting, ineligible expressions (BufferLoad/Call), nested if LCA,
multiple candidates, if-condition, no single-use binding, determinism, no-op
- [x] Build passes
- [x] Ruff lint passes
--
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]
