[mlir][arith] `arith.floordivsi -(2^n -1), -1` generates wrong code with UB

[pingshiyu]

The code below tries to calculate: arith.floordivsi (1 - 2^63), -1, which should give a well defined result equalling 2^63 - 1 (as far as I can tell from the documentation). But instead generates code that crashes when compiled with:

mlir-opt --arith-expand --test-lower-to-llvm out.mlir | mlir-cpu-runner -e main --shared-libs ~/lib/mlir_c_runner --entry-point-result void

"builtin.module"() ({
    ^bb0(): 
        "func.func"() ({
            ^bb0(): 
                "func.call"() {callee=@func0} : () -> ()
                "func.return"() : () -> ()
            }) {sym_name="main", function_type=() -> ()} : () -> ()
        "func.func"() ({
            ^bb0(): 
                %nMaxInt, %n1 = "func.call"() {callee=@func1} : () -> (i64, i64)
                vector.print %nMaxInt : i64 // -(2^n - 1)
                vector.print %n1 : i64      // -1

                %BUG = "arith.floordivsi"(%nMaxInt, %n1) : (i64, i64) -> (i64) 
                vector.print %BUG : i64 // // should == 2^n - 1, but crashes here
                "func.return"() : () -> ()
            }) {sym_name="func0", function_type=() -> ()} : () -> ()
        "func.func"() ({
            ^bb0(): 
                %nMaxInt = arith.constant -9223372036854775807 : i64
                %n1 = arith.constant -1 : i64
                "func.return"(%nMaxInt, %n1) : (i64, i64) -> ()
            }) {sym_name="func1", function_type=() -> (i64, i64)} : () -> ()
    }) : () -> ()

[lipracer]

A more streamlined test is as follows:

module {
  func.func @main() {
    %n1 = arith.constant -1 : i64
    %nMaxInt = arith.constant -9223372036854775807 : i64
    %BUG = arith.floordivsi %nMaxInt, %n1 : i64 
    vector.print %BUG : i64 // // should == 2^n - 1, but crashes here
    return
  }
}

with command:

./build/bin/mlir-opt --arith-expand --test-lower-to-llvm  83079.mlir | ./build/bin/mlir-cpu-runner \
-e main --entry-point-result void --shared-libs ./build/lib/libmlir_c_runner_utils.so

git commit:512a8a78a7f3bffc41cd7c00788eb099519f4625
and it's work well.
Can you post here the complete IR that reproduces this problem? thanks.

[pingshiyu]

@lipracer the bug only seems to occur when the functions aren't inlined. Otherwise, the erroneous code is never generated, as the floordivsi gets folded away

Here's the godbolt for reproduction: https://godbolt.org/z/59xrxY5oz

I don't know how to execute mlir-c-runner on godbolt though, so I ran the godbolt-compiled IR locally on 33b6b674620d77e615d569f504b306aac528bab7, please let me know if you could reproduce it on your side as well!

[lipracer]

I think crashing is a normal behavior because MinInt / -1 will overflow here. On the contrary, I think there is a problem here where fold's behavior is abnormal.You can try the following code and it will crash normally.

int main() {
    int64_t a = -9223372036854775808;
    int64_t b = -1;
    int64_t c = a / b;
    return 0;
}

I will fix this fold.Thanks.

[pingshiyu]

@lipracer I believe the correct behaviour isn't a crash, and the constant folder is correct here.

The valid value range for n bit signed integers is [-2^n, 2^n - 1]. In 64 bits this is [-9223372036854775808, 9223372036854775807]

The original code computes (-2^n + 1) / -1 (-9223372036854775807/-1 == 9223372036854775807), which is not an overflow.

Looking at the compiled code, -arith-expand compiles floordivsi into the following ops:

// floordiv a bfloordiv
%a, %b = call @func1() : () -> (i64, i64)
%1 = arith.constant 1 : i64
%0 = arith.constant 0 : i64
%n1 = arith.constant -1 : i64
%bLt0 = arith.cmpi slt, %b, %0 : i64 
%c = arith.select %bLt0, %1, %n1 : i64 // c == 1
%a-c = arith.subi %c, %a : i64 // a - c == a - 1 == -2^n
%error = arith.divsi %3, %b : i64  // (a-c)/b == -2^n / -1 ----- UB: OVERFLOW
// ... more

(variables renamed for readability), and it's apparent when a == -2^n + 1, b == -1, UB will be triggered (according to the Arith docs anyways). So this looks to me like a problem in how floordivsi is implemented within arith-expand.

[lipracer]

@pingshiyu You are right, there is indeed an issue with the expand here. I will add it later in the PR, but there is also an issue with the folding here.

[pingshiyu]

@pingshiyu You are right, there is indeed an issue with the expand here. I will add it later in the PR, but there is also an issue with the folding here.

thank you! appreciate your help :)