[InstSimplify] folds for negation of sign-bit

[spatel]

Summary

0 - X --> X, if X is 0 or the minimum signed value
0 - X --> 0, if X is 0 or the minimum signed value and the sub is NSW

I noticed this pattern might be created in the backend after the change from D25485, so if I haven't flubbed the logic, we'll want to add a similar fold for the DAG.

[efriedma]

LGTM.

lib/Analysis/InstructionSimplify.cpp

692

I'm sort of concerned that calling computeKnownBits here could lead to compile-time performance problems, given that instsimplify is supposed to be inexpensive, and the condition is very unlikely to succeed in most code. I don't have any evidence it's actually an issue, though; maybe computeKnownBits is cheap enough that it doesn't matter.

[spatel]

lib/Analysis/InstructionSimplify.cpp

692

Yes, I wasn't sure about doing a specific match for 'and' or 'shl' instead. I saw that we are using computeKnownBits in other places in this file though, so I thought it would be ok.

[efriedma]

It's probably fine, but something to watch out for in the future if someone ever spends some time digging into instcombine/instsimplify compile-time.

lib/Analysis/InstructionSimplify.cpp

static Value *SimplifySubInst(Value *Op0, Value *Op1, bool isNSW, bool isNUW,
   // X - 0 -> X
   if (match(Op1, m_Zero()))
     return Op0;
 
   // X - X -> 0
   if (Op0 == Op1)
     return Constant::getNullValue(Op0->getType());
 
+  // Is this a negation?
+  if (match(Op0, m_Zero())) {
     // 0 - X -> 0 if the sub is NUW.
-  if (isNUW && match(Op0, m_Zero()))
+    if (isNUW)
       return Op0;
 
+    unsigned BitWidth = Op1->getType()->getScalarSizeInBits();
+    APInt KnownZero(BitWidth, 0);
+    APInt KnownOne(BitWidth, 0);
+    computeKnownBits(Op1, KnownZero, KnownOne, Q.DL, 0, Q.AC, Q.CxtI, Q.DT);
+    if (KnownZero == ~APInt::getSignBit(BitWidth)) {
+      // Op1 is either 0 or the minimum signed value. If the sub is NSW, then
+      // Op1 must be 0 because negating the minimum signed value is undefined.
+      if (isNSW)
+        return Op0;
+
+      // 0 - X -> X if X is 0 or the minimum signed value.
+      return Op1;
+    }
+  }
+
   // (X + Y) - Z -> X + (Y - Z) or Y + (X - Z) if everything simplifies.
   // For example, (X + Y) - Y -> X; (Y + X) - Y -> X
   Value *X = nullptr, *Y = nullptr, *Z = Op1;
   if (MaxRecurse && match(Op0, m_Add(m_Value(X), m_Value(Y)))) { // (X + Y) - Z
     // See if "V === Y - Z" simplifies.
     if (Value *V = SimplifyBinOp(Instruction::Sub, Y, Z, Q, MaxRecurse-1))
       // It does!  Now see if "X + V" simplifies.
       if (Value *W = SimplifyBinOp(Instruction::Add, X, V, Q, MaxRecurse-1)) {

test/Transforms/InstSimplify/negate.ll

 ; CHECK-NEXT:    ret <2 x i32> zeroinitializer
 ;
   %neg = sub nuw <2 x i32> zeroinitializer, %x
   ret <2 x i32> %neg
 }
 
 define i8 @negate_zero_or_minsigned_nsw(i8 %x) {
 ; CHECK-LABEL: @negate_zero_or_minsigned_nsw(
-; CHECK-NEXT:    [[SIGNBIT:%.*]] = and i8 %x, -128
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i8 0, [[SIGNBIT]]
-; CHECK-NEXT:    ret i8 [[NEG]]
+; CHECK-NEXT:    ret i8 0
 ;
   %signbit = and i8 %x, 128
   %neg = sub nsw i8 0, %signbit
   ret i8 %neg
 }
 
 define <2 x i8> @negate_zero_or_minsigned_nsw_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @negate_zero_or_minsigned_nsw_vec(
-; CHECK-NEXT:    [[SIGNBIT:%.*]] = shl <2 x i8> %x, <i8 7, i8 7>
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <2 x i8> zeroinitializer, [[SIGNBIT]]
-; CHECK-NEXT:    ret <2 x i8> [[NEG]]
+; CHECK-NEXT:    ret <2 x i8> zeroinitializer
 ;
   %signbit = shl <2 x i8> %x, <i8 7, i8 7>
   %neg = sub nsw <2 x i8> zeroinitializer, %signbit
   ret <2 x i8> %neg
 }
 
 define i8 @negate_zero_or_minsigned(i8 %x) {
 ; CHECK-LABEL: @negate_zero_or_minsigned(
 ; CHECK-NEXT:    [[SIGNBIT:%.*]] = shl i8 %x, 7
-; CHECK-NEXT:    [[NEG:%.*]] = sub i8 0, [[SIGNBIT]]
-; CHECK-NEXT:    ret i8 [[NEG]]
+; CHECK-NEXT:    ret i8 [[SIGNBIT]]
 ;
   %signbit = shl i8 %x, 7
   %neg = sub i8 0, %signbit
   ret i8 %neg
 }
 
 define <2 x i8> @negate_zero_or_minsigned_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @negate_zero_or_minsigned_vec(
 ; CHECK-NEXT:    [[SIGNBIT:%.*]] = and <2 x i8> %x, <i8 -128, i8 -128>
-; CHECK-NEXT:    [[NEG:%.*]] = sub <2 x i8> zeroinitializer, [[SIGNBIT]]
-; CHECK-NEXT:    ret <2 x i8> [[NEG]]
+; CHECK-NEXT:    ret <2 x i8> [[SIGNBIT]]
 ;
   %signbit = and <2 x i8> %x, <i8 128, i8 128>
   %neg = sub <2 x i8> zeroinitializer, %signbit
   ret <2 x i8> %neg
 }