Signed integer overflow in Constraint Elimination pass

[aeubanks]

$ cat /tmp/a.ll
define double @f() {
entry:
  %0 = shl nuw i64 4503599627370496, 11
  %cmp3.not.1.i.i856 = icmp eq i64 %0, 0
  br i1 %cmp3.not.1.i.i856, label %if.end23.sink.split.i894, label %lor.lhs.false.i858

lor.lhs.false.i858:                               ; preds = %entry
  br label %if.end23.sink.split.i894

if.end23.sink.split.i894:                         ; preds = %lor.lhs.false.i858, %entry
  ret double 0.000000e+00
}
# opt built with ubsan
$ opt -p constraint-elimination -disable-output /tmp/a.ll
../../llvm/lib/Transforms/Scalar/ConstraintElimination.cpp:700:11: runtime error: signed integer overflow: -9223372036854775808 * -1 cannot be represented in type 'int64_t' (aka 'long')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../llvm/lib/Transforms/Scalar/ConstraintElimination.cpp:700:11

@fhahn

[llvmbot]

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1. Check that no other contributor has already been assigned to this issue. If you believe that no one is actually working on it despite an assignment, ping the person. After one week without a response, the assignee may be changed.
2. In the comments of this issue, request for it to be assigned to you, or just create a pull request after following the steps below. Mention this issue in the description of the pull request.
3. Fix the issue locally.
4. Run the test suite locally. Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests.
5. Create a Git commit.
6. Run git clang-format HEAD~1 to format your changes.
7. Open a pull request to the upstream repository on GitHub. Detailed instructions can be found in GitHub's documentation. Mention this issue in the description of the pull request.

If you have any further questions about this issue, don't hesitate to ask via a comment in the thread below.

[llvmbot]

@llvm/issue-subscribers-good-first-issue

Author: Arthur Eubanks (aeubanks)

``` $ cat /tmp/a.ll define double @f() { entry: %0 = shl nuw i64 4503599627370496, 11 %cmp3.not.1.i.i856 = icmp eq i64 %0, 0 br i1 %cmp3.not.1.i.i856, label %if.end23.sink.split.i894, label %lor.lhs.false.i858

lor.lhs.false.i858: ; preds = %entry
br label %if.end23.sink.split.i894

if.end23.sink.split.i894: ; preds = %lor.lhs.false.i858, %entry
ret double 0.000000e+00
}

opt built with ubsan

$ opt -p constraint-elimination -disable-output /tmp/a.ll
../../llvm/lib/Transforms/Scalar/ConstraintElimination.cpp:700:11: runtime error: signed integer overflow: -9223372036854775808 * -1 cannot be represented in type 'int64_t' (aka 'long')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ../../llvm/lib/Transforms/Scalar/ConstraintElimination.cpp:700:11

@<!-- -->fhahn 
</details>

[houngkoungting]

Hi @aeubanks and LLVM team,

I'm interested in taking a stab at fixing this issue (#133156) regarding the signed integer overflow in the Constraint Elimination pass. It looks like a great opportunity to dive into LLVM's optimization passes, and I’d like to contribute to resolving this undefined behavior.

To get started, could you please confirm if there’s a specific test case or reproducer available that triggers this overflow? The description mentions it’s in the Constraint Elimination pass, but any additional details (e.g., a minimal IR example or steps to reproduce) would be super helpful. Also, if there’s a preferred approach for fixing this (like using APInt for safe arithmetic or adding overflow checks), I’d appreciate any pointers.

Looking forward to working on this—thanks for marking it as a "good first issue"! Let me know if I should claim it formally or if there’s anything else I need to do to proceed.

[fhahn]

@houngkoungting great! You can see from @aeubanks description that the issue is surfaced by the undefined behavior sanitizer here https://github.com/llvm/llvm-project/blob/main/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp#L700

The minimal example is the test case @aeubanks provided:

define double @f() {
entry:
  %0 = shl nuw i64 4503599627370496, 11
  %cmp3.not.1.i.i856 = icmp eq i64 %0, 0
  br i1 %cmp3.not.1.i.i856, label %if.end23.sink.split.i894, label %lor.lhs.false.i858

lor.lhs.false.i858:                               ; preds = %entry
  br label %if.end23.sink.split.i894

if.end23.sink.split.i894:                         ; preds = %lor.lhs.false.i858, %entry
  ret double 0.000000e+00
}

To reproduce the crash you'd need to build LLVM with UBSan, you should be able to do so by adding -DLLVM_USE_SANITIZER='Address' to you cmake invocation

[fhahn]

To fix this, you probably need to use MulOverflow (https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Support/MathExtras.h#L763) instead of of a regular multiply

[houngkoungting]

@fhahn Thanks for the pointer! I’ll update the patch to use MulOverflow and test it with UBSan enabled. Appreciate the clear explanation and the example!

[houngkoungting]

@aeubanks @fhahn Thanks you . Let me take the first step with this pull request (#133629) .