[InstSimplify] Fix addo/subo undef folds (PR42209)

[nikic]

Summary

Fix folds of addo and subo with an undef operand to be:

• subo(X, undef) folds to { 0, false } (holds for undef = X).
• addo(X, undef) folds to { -1, false } (holds for undef = ~X).
• Same for commuted variants.

These are consistent with the folds we use for subsat and addsat.

Fixes PR42209

[lebedev.ri]

I wonder if we should instead fold to { i8 undef, i1 false } ?

[nikic]

@lebedev.ri It's not possible to fold to { i8 undef, i1 false }. As a counter-example uaddo(1, undef) can never have the value { 0, false }. Reaching the zero value would have required overflow, which is precluded by the overflow result. Similar cases exist for the other intrinsics as well.

[lebedev.ri]

In D63065#1544780, @nikic wrote:

@lebedev.ri It's not possible to fold to { i8 undef, i1 false }. As a counter-example uaddo(1, undef) can never have the value { 0, false }. Reaching the zero value would have required overflow, which is precluded by the overflow result. Similar cases exist for the other intrinsics as well.

Ok so. I *think* i'm finally holding alive the right way, gently-enough, and breathing in other direction to not disturb it.
And it does not agree with that statement:

$ .../alive  -root-only /tmp/test.opt  
OMP: Info #270: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
Processing /tmp/test.opt..

----------------------------------------
Name: zz
  %undef0 = udiv i8 %a, 0
  %X = uadd_overflow i8 1, %undef0
  %Y = extractvalue {i8, i1} %X, 0
  %Z = extractvalue {i8, i1} %X, 1
  ret %Y
=>
  %undef0 = udiv i8 %a, 0
  %X = uadd_overflow i8 1, %undef0
  %Y = 0
  %Z = 0
  ret %Y

Done: 64
Optimization is correct!

----------------------------------------
Name: zz 2
  %undef0 = udiv i8 %a, 0
  %X = uadd_overflow i8 1, %undef0
  %Y = extractvalue {i8, i1} %X, 0
  %Z = extractvalue {i8, i1} %X, 1
  ret %Z
=>
  %undef0 = udiv i8 %a, 0
  %X = uadd_overflow i8 1, %undef0
  %Y = 0
  %Z = 0
  ret %Z

Done: 64
Optimization is correct!

In fact, it tells me that my suggestion about folding all 4 of @llvm.{u,s}{add,sub}.with.overflow to {undef, false} is correct.
And the @llvm.{u,s}mul.with.overflow can all be folded to {0, false}

[nikic]

@lebedev.ri Not familiar with what exactly alive proves, but assuming you're using two separate proofs for a reason: It is possible to make the result zero, yes. But only if the overflow flag is chosen as true (rather than false) at the same time. Both result & overflow need to be checked together for the result to be meaningful.

(Additionally, if alive models udiv semantics correctly, any transformation will be correct by definition (IUB) after a udiv 0 -- I'm assuming that's not how it works though.)

[lebedev.ri]

In D63065#1545036, @nikic wrote:

@lebedev.ri Not familiar with what exactly alive proves, but assuming you're using two separate proofs for a reason: It is possible to make the result zero, yes. But only if the overflow flag is chosen as true (rather than false) at the same time. Both result & overflow need to be checked together for the result to be meaningful.

Good observarvation. Close, but nope:

$ ./src/alive2/build-Clang-release/alive -root-only /tmp/test.opt 
OMP: Info #270: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
Processing /tmp/test.opt..

----------------------------------------
Name: uadd_overflow
  %X = uadd_overflow i8 %a, undef
  %Op = extractvalue {i8, i1} %X, 0
  %Ov = extractvalue {i8, i1} %X, 1
  %OpIsZero = icmp eq %Op, 0
  %NoOverflow = icmp eq %Ov, 0
  %Zero = and i1 %OpIsZero, %NoOverflow
  ret i1 %Zero
=>
  ret i1 1

Done: 1
Optimization is correct!

$ ./src/alive2/build-Clang-release/alive -root-only /tmp/test.opt 
OMP: Info #270: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
Processing /tmp/test.opt..

----------------------------------------
Name: uadd_overflow
  %X = uadd_overflow i8 %a, %b
  %Op = extractvalue {i8, i1} %X, 0
  %Ov = extractvalue {i8, i1} %X, 1
  %OpIsZero = icmp eq %Op, 0
  %NoOverflow = icmp eq %Ov, 0
  %Zero = and i1 %OpIsZero, %NoOverflow
  ret i1 %Zero
=>
  ret i1 1

ERROR: Value mismatch

Example:
i8 %a = #xa0 (160)
i8 %b = #x80 (128)

Source:
{i8, i1} %X = { #x20 (32), #x1 (0) }
i8 %Op = #x20 (32)
i1 %Ov = #x1 (1)
i1 %OpIsZero = #x0 (0)
i1 %NoOverflow = #x0 (0)
i1 %Zero = #x0 (0)

Target:
Source value: #x0 (0)
Target value: #x1 (1)

(Additionally, if alive models udiv semantics correctly, any transformation will be correct by definition (IUB) after a udiv 0 -- I'm assuming that's not how it works though.)

[nikic]

In D63065#1545052, @lebedev.ri wrote:

In D63065#1545036, @nikic wrote:

@lebedev.ri Not familiar with what exactly alive proves, but assuming you're using two separate proofs for a reason: It is possible to make the result zero, yes. But only if the overflow flag is chosen as true (rather than false) at the same time. Both result & overflow need to be checked together for the result to be meaningful.

Good observarvation. Close, but nope:

$ ./src/alive2/build-Clang-release/alive -root-only /tmp/test.opt 
OMP: Info #270: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
Processing /tmp/test.opt..

----------------------------------------
Name: uadd_overflow
  %X = uadd_overflow i8 %a, undef
  %Op = extractvalue {i8, i1} %X, 0
  %Ov = extractvalue {i8, i1} %X, 1
  %OpIsZero = icmp eq %Op, 0
  %NoOverflow = icmp eq %Ov, 0
  %Zero = and i1 %OpIsZero, %NoOverflow
  ret i1 %Zero
=>
  ret i1 1

Done: 1
Optimization is correct!

Isn't this checking exactly the transform proposed here?

[nikic]

In D63065#1545065, @nikic wrote:

Isn't this checking exactly the transform proposed here?

Ah no it isn't, got confused between addo and subo there.

[lebedev.ri]

Ok, so {undef, 0} it is?

[nikic]

Sorry, I'm still not convinced. Alive evaluates a single atomic with_overflow operation by computing the operation result and the overflow flag independently, which is usually okay but in my eyes not right when it comes to undef modeling, because it artificially increases the number of undef users over what exists in IR. (For reference, some of the discussion is in https://github.com/AliveToolkit/alive2/issues/71.)

I'll leave this to someone else. Undef and I clearly don't get along...

[lebedev.ri]

Hm, not sure how to reclaim the differential, there is no such thing in "Add Action" dropdown.

llvm/lib/Analysis/InstructionSimplify.cpp

 static Value *simplifyBinaryIntrinsic(Function *F, Value *Op0, Value *Op1,
                                       const SimplifyQuery &Q) {
   Intrinsic::ID IID = F->getIntrinsicID();
   Type *ReturnType = F->getReturnType();
   switch (IID) {
   case Intrinsic::usub_with_overflow:
   case Intrinsic::ssub_with_overflow:
     // X - X -> { 0, false }
-    if (Op0 == Op1)
+    // X - undef -> { 0, false } for undef = X.
+    // undef - X -> { 0, false } for undef = X.
+    if (Op0 == Op1 || isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
       return Constant::getNullValue(ReturnType);
-    // X - undef -> undef
-    // undef - X -> undef
-    if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
-      return UndefValue::get(ReturnType);
     break;
   case Intrinsic::uadd_with_overflow:
   case Intrinsic::sadd_with_overflow:
-    // X + undef -> undef
-    if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1))
-      return UndefValue::get(ReturnType);
+    // X + undef -> { -1, false } for undef = ~X.
+    // undef + X -> { -1, false } for undef = ~X.
+    if (isa<UndefValue>(Op0) || isa<UndefValue>(Op1)) {
+      StructType *ST = cast<StructType>(ReturnType);
+      Constant *Elems[] = {
+        Constant::getAllOnesValue(ST->getElementType(0)),
+        getFalse(ST->getElementType(1)),
+      };
+      return ConstantStruct::get(ST, Elems);
+    }
     break;
   case Intrinsic::umul_with_overflow:
   case Intrinsic::smul_with_overflow:
     // 0 * X -> { 0, false }
     // X * 0 -> { 0, false }
     if (match(Op0, m_Zero()) || match(Op1, m_Zero()))
       return Constant::getNullValue(ReturnType);
     // undef * X -> { 0, false }

llvm/test/Transforms/InstCombine/with_overflow.ll

;
   %y = extractvalue { i8, i1 } %x, 0
   %z = extractvalue { i8, i1 } %x, 1
   store i1 %z, i1* %overflowPtr
   ret i8 %y
 }
 
 define i8 @uaddtest4(i8 %A, i1* %overflowPtr) {
 ; CHECK-LABEL: @uaddtest4(
-; CHECK-NEXT:    ret i8 undef
+; CHECK-NEXT:    store i1 false, i1* [[OVERFLOWPTR:%.*]], align 1
+; CHECK-NEXT:    ret i8 -1
 ;
   %x = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 undef, i8 %A)
   %y = extractvalue { i8, i1 } %x, 0
   %z = extractvalue { i8, i1 } %x, 1
   store i1 %z, i1* %overflowPtr
   ret i8 %y
 }
 

llvm/test/Transforms/InstSimplify/call.ll

 ;
   %x = call {i8, i1} @llvm.uadd.with.overflow.i8(i8 254, i8 44)
   %result = extractvalue {i8, i1} %x, 0
   ret i8 %result
 }
 
 define {i8, i1} @test_uadd3(i8 %v) {
 ; CHECK-LABEL: @test_uadd3(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } { i8 -1, i1 false }
 ;
   %result = call {i8, i1} @llvm.uadd.with.overflow.i8(i8 %v, i8 undef)
   ret {i8, i1} %result
 }
 
 define {i8, i1} @test_uadd4(i8 %v) {
 ; CHECK-LABEL: @test_uadd4(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } { i8 -1, i1 false }
 ;
   %result = call {i8, i1} @llvm.uadd.with.overflow.i8(i8 undef, i8 %v)
   ret {i8, i1} %result
 }
 
 define i1 @test_sadd1() {
 ; CHECK-LABEL: @test_sadd1(
 ; CHECK-NEXT:    ret i1 true

 ;
   %x = call {i8, i1} @llvm.sadd.with.overflow.i8(i8 126, i8 44)
   %result = extractvalue {i8, i1} %x, 0
   ret i8 %result
 }
 
 define {i8, i1} @test_sadd3(i8 %v) {
 ; CHECK-LABEL: @test_sadd3(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } { i8 -1, i1 false }
 ;
   %result = call {i8, i1} @llvm.sadd.with.overflow.i8(i8 %v, i8 undef)
   ret {i8, i1} %result
 }
 
 define {i8, i1} @test_sadd4(i8 %v) {
 ; CHECK-LABEL: @test_sadd4(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } { i8 -1, i1 false }
 ;
   %result = call {i8, i1} @llvm.sadd.with.overflow.i8(i8 undef, i8 %v)
   ret {i8, i1} %result
 }
 
 define {i8, i1} @test_usub1(i8 %V) {
 ; CHECK-LABEL: @test_usub1(
 ; CHECK-NEXT:    ret { i8, i1 } zeroinitializer
 ;
   %x = call {i8, i1} @llvm.usub.with.overflow.i8(i8 %V, i8 %V)
   ret {i8, i1} %x
 }
 
 define {i8, i1} @test_usub2(i8 %V) {
 ; CHECK-LABEL: @test_usub2(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } zeroinitializer
 ;
   %x = call {i8, i1} @llvm.usub.with.overflow.i8(i8 %V, i8 undef)
   ret {i8, i1} %x
 }
 
 define {i8, i1} @test_usub3(i8 %V) {
 ; CHECK-LABEL: @test_usub3(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } zeroinitializer
 ;
   %x = call {i8, i1} @llvm.usub.with.overflow.i8(i8 undef, i8 %V)
   ret {i8, i1} %x
 }
 
 define {i8, i1} @test_ssub1(i8 %V) {
 ; CHECK-LABEL: @test_ssub1(
 ; CHECK-NEXT:    ret { i8, i1 } zeroinitializer
 ;
   %x = call {i8, i1} @llvm.ssub.with.overflow.i8(i8 %V, i8 %V)
   ret {i8, i1} %x
 }
 
 define {i8, i1} @test_ssub2(i8 %V) {
 ; CHECK-LABEL: @test_ssub2(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } zeroinitializer
 ;
   %x = call {i8, i1} @llvm.ssub.with.overflow.i8(i8 %V, i8 undef)
   ret {i8, i1} %x
 }
 
 define {i8, i1} @test_ssub3(i8 %V) {
 ; CHECK-LABEL: @test_ssub3(
-; CHECK-NEXT:    ret { i8, i1 } undef
+; CHECK-NEXT:    ret { i8, i1 } zeroinitializer
 ;
   %x = call {i8, i1} @llvm.ssub.with.overflow.i8(i8 undef, i8 %V)
   ret {i8, i1} %x
 }
 
 define {i8, i1} @test_umul1(i8 %V) {
 ; CHECK-LABEL: @test_umul1(
 ; CHECK-NEXT:    ret { i8, i1 } zeroinitializer