You are viewing a plain text version of this content. The canonical link for it is here.
Posted to discuss-archive@tvm.apache.org by "tqchen (via GitHub)" <gi...@apache.org> on 2026/07/06 13:19:30 UTC

[PR] Phase out Relax-specific Id aliases [tvm]

tqchen opened a new pull request, #19959:
URL: https://github.com/apache/tvm/pull/19959

   Remove the Relax-specific Id indirection and use Var/DataflowVar object identity directly.
   
   Type-changing rewrites now remap definitions, uses, and binding lookups coherently while preserving reflection, serialization, and the DataflowVar subtype. Existing tests are adjusted for the API change; no new test files or test cases are added.
   
   Validation: the compiler and C++ tests build successfully; focused C++ coverage passes 4/4; the affected existing Python matrix passes 527 tests with 2 expected xfails; source censuses, diff checks, and applicable hooks pass.


-- 
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: discuss-archive-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org


Re: [PR] Phase out Relax-specific Id aliases [tvm]

Posted by "gemini-code-assist[bot] (via GitHub)" <gi...@apache.org>.
gemini-code-assist[bot] commented on code in PR #19959:
URL: https://github.com/apache/tvm/pull/19959#discussion_r3529174159


##########
src/relax/ir/expr_functor.cc:
##########
@@ -544,19 +544,36 @@ PrimExpr ExprMutatorBase::VisitTypePrimExprField(const PrimExpr& expr) {
 // ==================
 // ExprMutator
 
+namespace {
+
+template <typename TMap>
+void RedirectVarRemapTargets(TMap* var_remap, const Var& old_target, const Var& new_target) {
+  if (old_target.same_as(new_target)) {
+    return;
+  }
+  for (auto& entry : *var_remap) {
+    if (entry.second.same_as(old_target)) {
+      entry.second = new_target;
+    }
+  }
+}
+
+}  // namespace

Review Comment:
   ![high](https://www.gstatic.com/codereviewagent/high-priority.svg)
   
   ### Efficiency Issue: $O(N^2)$ Complexity in Variable Remapping\n\nThe helper function "RedirectVarRemapTargets" performs a linear scan over the entire "var_remap" map to update any entries pointing to "old_target". Since this is called during "ReEmitBinding" and "VisitBinding_" (which are executed for every binding in a block), this introduces an $O(N^2)$ complexity bottleneck, where $N$ is the number of bindings. For large models with thousands of bindings, this can cause significant compilation overhead.\n\n#### Suggested Alternative: Transitive Lookup\nInstead of eagerly updating all targets via a linear scan, we can resolve the remappings transitively on lookup. This completely eliminates the need for "RedirectVarRemapTargets" and reduces the remapping overhead to $O(1)$ amortized time.\n\nWe can define a helper method in "ExprMutator" (e.g., in "include/tvm/relax/expr_functor.h" or as a protected method):\n\n```cpp\nVar ExprMutator::GetVarRemap(const Var& var) const {\n  Var
  current = var;\n  while (true) {\n    auto it = var_remap_.find(current);\n    if (it == var_remap_.end() || it->second.same_as(current)) {\n      break;\n    }\n    current = it->second;\n  }\n  return current;\n}\n```\n\nAnd then use "GetVarRemap" in "VisitExpr_", "LookupBinding", and other lookup sites instead of direct "var_remap_.find(var)".



-- 
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: discuss-archive-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org


Re: [PR] Phase out Relax-specific Id aliases [tvm]

Posted by "tlopex (via GitHub)" <gi...@apache.org>.
tlopex merged PR #19959:
URL: https://github.com/apache/tvm/pull/19959


-- 
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: discuss-archive-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org


Re: [PR] Phase out Relax-specific Id aliases [tvm]

Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen commented on code in PR #19959:
URL: https://github.com/apache/tvm/pull/19959#discussion_r3530339336


##########
src/relax/ir/expr_functor.cc:
##########
@@ -544,19 +544,36 @@ PrimExpr ExprMutatorBase::VisitTypePrimExprField(const PrimExpr& expr) {
 // ==================
 // ExprMutator
 
+namespace {
+
+template <typename TMap>
+void RedirectVarRemapTargets(TMap* var_remap, const Var& old_target, const Var& new_target) {
+  if (old_target.same_as(new_target)) {
+    return;
+  }
+  for (auto& entry : *var_remap) {
+    if (entry.second.same_as(old_target)) {
+      entry.second = new_target;
+    }
+  }
+}
+
+}  // namespace

Review Comment:
   Resolved by c180e9e293. The full-map RedirectVarRemapTargets scan is removed entirely. var_remap_ remains a direct one-hop map: ReEmitBinding and MatchCast record the original, visited, and final variables with constant-time unordered-map writes, while downstream mutators retain ownership of any recursive remapping they need. User-defined A-to-B/B-to-A mappings are therefore never traversed recursively and cannot loop. Validation rebuilt tvm_compiler and cpptest; 4/4 C++ expression tests passed; 214 existing focused Python tests passed with one expected xfail across ExprMutator, canonicalization/type updates, layout, CSE, LambdaLift, lazy transform params, CUDA graph, mixed precision, and script builder. No tests were added.



-- 
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: discuss-archive-unsubscribe@tvm.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: discuss-archive-unsubscribe@tvm.apache.org
For additional commands, e-mail: discuss-archive-help@tvm.apache.org