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 "guocju (via GitHub)" <gi...@apache.org> on 2026/01/29 08:11:59 UTC

[PR] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

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

   …loormod
   
   This patch fixes an issue in the LowerIntrin pass where incorrect optimizations were applied to floordiv and floormod operations.
   
   The root cause is that the pass attempts to find an equivalent representation for floordiv(a, b) by calculating the expression (op->b - 1) - a_min. This expression, when subjected to constant folding, can potentially overflow the range of int32 or int16. When this overflow occurs, the transformation becomes invalid and no longer equivalent to the original operation.
   
   To fix this, we enhanced the condition under which the transformation is applied. The new condition ensures that the transformation is only performed when (b_max - a_min) is less than INT_MAX + 2. If this condition is not met, the transformation is skipped and the common lowering steps are followed to ensure correctness.
   
   A regression test has been added to cover this case.
   
   Fixes #18684


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen commented on PR #18694:
URL: https://github.com/apache/tvm/pull/18694#issuecomment-3823656102

   /gemini review


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen commented on PR #18694:
URL: https://github.com/apache/tvm/pull/18694#issuecomment-3824220925

   https://github.com/apache/tvm/pull/18699 contains some followups to further clean things up and robustify the scenario. thanks @guocju for bringing up the initial case


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

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


##########
src/tir/transforms/lower_intrin.cc:
##########
@@ -118,10 +118,20 @@ class IntrinInjecter : public tvm::arith::IRMutatorWithAnalyzer {
 
       // If the numerator's lower bound is known, express the floordiv
       // in terms of truncdiv using only positive operands.
-      arith::ConstIntBound const_int_bound = analyzer_->const_int_bound(op->a);
-      if (const_int_bound->min_value < 0 &&
-          const_int_bound->min_value >
-              -(Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value)) {
+
+      // The optimization below rewrites expressions involving `-a_min + (b - 1)`.
+      // Without proper bounds checking, this expression may overflow the dtype
+      // maximum, leading to non-equivalent transformations.
+      // To ensure safety, we require:
+      //   b_max - a_min <= max_value_of_dtype + 1
+      // This provides a conservative upper bound that prevents overflow and
+      // preserves the original semantics.
+      arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
+      arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(op->b);
+      const int64_t max_value_of_dtype =
+          Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value;
+      if (const_int_bound_a->min_value < 0 &&
+          const_int_bound_b->max_value - const_int_bound_a->min_value <= max_value_of_dtype + 1) {

Review Comment:
   ![medium](https://www.gstatic.com/codereviewagent/medium-priority.svg)
   
   This block of logic for checking the safety of the optimization is duplicated in `VisitExpr_(const FloorModNode* op)` at lines 228-240. To improve maintainability and reduce code duplication, consider extracting this logic into a private helper function within the `IntrinInjecter` class.
   
   For example, you could create a helper function like this:
   
   ```cpp
    private:
     bool IsFloorDivModOptSafe(const PrimExpr& a, const PrimExpr& b) {
       arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(a);
       if (const_int_bound_a->min_value >= 0) {
         return false;
       }
   
       // The optimization below rewrites expressions involving `-a_min + (b - 1)`.
       // Without proper bounds checking, this expression may overflow the dtype
       // maximum, leading to non-equivalent transformations.
       // To ensure safety, we require:
       //   b_max - a_min <= max_value_of_dtype + 1
       // This provides a conservative upper bound that prevents overflow and
       // preserves the original semantics.
       arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(b);
       const int64_t max_value_of_dtype =
           Downcast<IntImm>(tvm::max_value(a->dtype.element_of()))->value;
       return const_int_bound_b->max_value - const_int_bound_a->min_value <= max_value_of_dtype + 1;
     }
   ```
   
   Then, you could simplify the call sites:
   
   ```cpp
   // in VisitExpr_(const FloorDivNode* op)
   if (IsFloorDivModOptSafe(op->a, op->b)) {
     arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
     // ... rest of the logic
   }
   
   // in VisitExpr_(const FloorModNode* op)
   if (IsFloorDivModOptSafe(op->a, op->b)) {
     arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
     // ... rest of the logic
   }
   ```
   This would centralize the safety check and make the code cleaner.



-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen commented on PR #18694:
URL: https://github.com/apache/tvm/pull/18694#issuecomment-3823688622

   Thanks @guocju for the bugfix!


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

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


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

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


##########
src/tir/transforms/lower_intrin.cc:
##########
@@ -118,10 +118,11 @@ class IntrinInjecter : public tvm::arith::IRMutatorWithAnalyzer {
 
       // If the numerator's lower bound is known, express the floordiv
       // in terms of truncdiv using only positive operands.
-      arith::ConstIntBound const_int_bound = analyzer_->const_int_bound(op->a);
-      if (const_int_bound->min_value < 0 &&
-          const_int_bound->min_value >
-              -(Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value)) {
+      arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
+      arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(op->b);

Review Comment:
   would be great to explicitly list out `(Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value)` as a variable and have comment documenting why +2 is needed, so future changes have the right context



-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen commented on PR #18694:
URL: https://github.com/apache/tvm/pull/18694#issuecomment-3817848603

   Thanks @guocju please cross check genimi review, and add explicit comment for context, the ci issue should be fixed by https://github.com/apache/tvm/pull/18695 thanks a lot for the contribution


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

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


##########
src/tir/transforms/lower_intrin.cc:
##########
@@ -214,10 +215,11 @@ class IntrinInjecter : public tvm::arith::IRMutatorWithAnalyzer {
 
       // If the numerator's lower bound is known, express the floormod
       // in terms of truncmod using only positive operands.
-      arith::ConstIntBound const_int_bound = analyzer_->const_int_bound(op->a);
-      if (const_int_bound->min_value < 0 &&
-          const_int_bound->min_value >
-              -(Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value)) {
+      arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
+      arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(op->b);
+      if (const_int_bound_a->min_value < 0 &&
+          const_int_bound_b->max_value - const_int_bound_a->min_value <
+              (Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value) + 2) {

Review Comment:
   ![medium](https://www.gstatic.com/codereviewagent/medium-priority.svg)
   
   Similar to the `FloorDiv` case, extracting the maximum value of the type into a local variable here would improve readability and avoid re-computation.
   
   ```suggestion
         arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
         arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(op->b);
         const int64_t max_value_of_type =
             Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value;
         if (const_int_bound_a->min_value < 0 &&
             const_int_bound_b->max_value - const_int_bound_a->min_value < max_value_of_type + 2) {
   ```



##########
src/tir/transforms/lower_intrin.cc:
##########
@@ -118,10 +118,11 @@ class IntrinInjecter : public tvm::arith::IRMutatorWithAnalyzer {
 
       // If the numerator's lower bound is known, express the floordiv
       // in terms of truncdiv using only positive operands.
-      arith::ConstIntBound const_int_bound = analyzer_->const_int_bound(op->a);
-      if (const_int_bound->min_value < 0 &&
-          const_int_bound->min_value >
-              -(Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value)) {
+      arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
+      arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(op->b);
+      if (const_int_bound_a->min_value < 0 &&
+          const_int_bound_b->max_value - const_int_bound_a->min_value <
+              (Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value) + 2) {

Review Comment:
   ![medium](https://www.gstatic.com/codereviewagent/medium-priority.svg)
   
   For improved readability and to avoid repeating a complex expression, consider extracting the maximum value of the type into a local `const` variable before the `if` statement.
   
   ```suggestion
         arith::ConstIntBound const_int_bound_a = analyzer_->const_int_bound(op->a);
         arith::ConstIntBound const_int_bound_b = analyzer_->const_int_bound(op->b);
         const int64_t max_value_of_type =
             Downcast<IntImm>(tvm::max_value(op->a->dtype.element_of()))->value;
         if (const_int_bound_a->min_value < 0 &&
             const_int_bound_b->max_value - const_int_bound_a->min_value < max_value_of_type + 2) {
   ```



-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

Posted by "tqchen (via GitHub)" <gi...@apache.org>.
tqchen commented on PR #18694:
URL: https://github.com/apache/tvm/pull/18694#issuecomment-3823662553

   Thanks, one final nit, can you also add your original regression of ceildiv(n, 4), where n is unbounded i32


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

Posted by "guocju (via GitHub)" <gi...@apache.org>.
guocju commented on PR #18694:
URL: https://github.com/apache/tvm/pull/18694#issuecomment-3822545427

   Yes, I’ve updated the check to explicitly extract max_value_of_dtype as a variable, and added a comment documenting why the condition is <= max_value_of_dtype + 1.
   
   


-- 
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] [BugFix][TIR] Fix incorrect optimization when lowering floordiv and f… [tvm]

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

   ## Summary of Changes
   
   Hello @guocju, I'm Gemini Code Assist[^1]! I'm currently reviewing this pull request and will post my feedback shortly. In the meantime, here's a summary to help you and other reviewers quickly get up to speed!
   
   This pull request addresses a critical bug within the `LowerIntrin` pass that caused erroneous optimizations for `floordiv` and `floormod` operations. The root cause was an integer overflow during constant folding of an intermediate expression, leading to invalid transformations. The solution involves refining the conditions under which these optimizations are applied, specifically by adding a check to prevent the transformation when the bounds could lead to overflow. This ensures that the lowering steps are correctly followed, and a new test case has been included to validate the fix.
   
   ### Highlights
   
   * **Bug Fix for Floordiv/Floormod Optimization**: This pull request resolves an issue in the `LowerIntrin` pass where incorrect optimizations were applied to `floordiv` and `floormod` operations due to potential integer overflow during constant folding.
   * **Improved Optimization Condition**: The fix introduces an enhanced condition for applying the optimization, ensuring it only proceeds when `(b_max - a_min)` is less than `INT_MAX + 2`, thereby preventing overflow and maintaining correctness.
   * **Regression Test Added**: A new regression test has been added to specifically cover the scenario that previously led to the incorrect optimization, ensuring the fix is robust.
   
   🧠 **New Feature in Public Preview:** You can now enable **Memory** to help **Gemini Code Assist** learn from your team's feedback. This makes future code reviews more consistent and personalized to your project's style. **Click [here](https://codeassist.google/code-review/login) to enable Memory in your admin console.**
   
   
   
   
   
   
   
   <details>
   <summary><b>Using Gemini Code Assist</b></summary>
   <br>
   
   The full guide for Gemini Code Assist can be found on our [documentation page](https://developers.google.com/gemini-code-assist/docs/review-github-code), here are some quick tips.
   
   <b>Invoking Gemini</b>
   
   You can request assistance from Gemini at any point by creating a comment using either `/gemini <command>` or `@gemini-code-assist <command>`. Below is a summary of the supported commands on the current page.
   
   Feature | Command | Description
   --- | --- | ---
   Code Review | `/gemini review` | Performs a code review for the current pull request in its current state.
   Pull Request Summary | `/gemini summary` | Provides a summary of the current pull request in its current state.
   Comment | @gemini-code-assist | Responds in comments when explicitly tagged, both in pull request comments and review comments.
   Help | `/gemini help` | Displays a list of available commands.
   
   <b>Customization</b>
   
   To customize Gemini Code Assist for GitHub experience, repository maintainers can create a configuration file and/or provide a custom code review style guide (such as PEP-8 for Python) by creating and adding files to a `.gemini/` folder in the base of the repository. Detailed instructions can be found [here](https://developers.google.com/gemini-code-assist/docs/customize-gemini-behavior-github).
   
   <b>Limitations & Feedback</b>
   
   Gemini Code Assist may make mistakes. Please leave feedback on any instances where its feedback is incorrect or counter productive. You can react with :thumbsup: and :thumbsdown: on @gemini-code-assist comments. If you're interested in giving your feedback about your experience with Gemini Code Assist for Github and other Google products, sign up [here](https://google.qualtrics.com/jfe/form/SV_2cyuGuTWsEw84yG).
   
   <b>You can also get AI-powered code generation, chat, as well as code reviews directly in the IDE at no cost with the [Gemini Code Assist IDE Extension](https://cloud.google.com/products/gemini/code-assist).</b>
   </details>
   
   
   
   
   [^1]: Review the [Privacy Notices](https://policies.google.com/privacy), [Generative AI Prohibited Use Policy](https://policies.google.com/terms/generative-ai/use-policy), [Terms of Service](https://policies.google.com/terms), and learn how to configure Gemini Code Assist in GitHub [here](https://developers.google.com/gemini-code-assist/docs/customize-gemini-behavior-github). Gemini can make mistakes, so double check it and [use code with caution](https://support.google.com/legal/answer/13505487).
   


-- 
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