[ValueTracking] Teach computeKnownBits that the result of an absolute value pattern that uses nsw flag is always positive.

[craig.topper]

Summary

If the nsw flag is used in the absolute value then it is undefined for INT_MIN. For all other value it will produce a positive number. So we can assume the result is positive.

This breaks some InstCombine abs/nabs combining tests because we simplify the second compare from known bits rather than as the whole pattern. Looks like we can probably fix it by adding a neg+abs/nabs combine to just swap the select operands. Need to check alive to make sure there are no corner cases.

[efriedma]

lib/Analysis/ValueTracking.cpp

1086

Can you write a similar pattern for SPF_NABS?

We could save a bit of computation by not calling ComputeKnownBits on both x and -x, but it's probably not worth bothering...

[craig.topper]

lib/Analysis/ValueTracking.cpp

1086

I don't think SPF_NABS has a sign bit guarantee. NABS of 0 is still 0. NABS of anything else is negative.

[dmgreen]

lib/Analysis/ValueTracking.cpp

1085

Can't RHS be a const?

[craig.topper]

lib/Analysis/ValueTracking.cpp

1085

This patch is dependent on another patch where I made matchSelectPattern return the negation portion in RHS. Previously it always returned a 0, 1, or -1 constant which was failry useless.

[craig.topper]

Add a combine to negate ABS/NABS to recover the broken tests.

[craig.topper]

Add a simple test case to show (abs(x)) > 0 is always true.

[craig.topper]

That should have said abs(x) >= 0 is always true.

[spatel]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1636–1637

We should copy and then swapProfMetadata for the new select rather than dropping that. Alternatively, we could swap the operands and metadata on the existing select and return it. Since we're checking hasOneUse(), I think it's ok to recycle.

This part can be a separate commit with independent tests like:

define i8 @negate_abs(i8 %x) {
  %n = sub i8 0, %x
  %c = icmp slt i8 %x, 0
  %s = select i1 %c, i8 %n, i8 %x
  %r = sub i8 0, %s
  ret i8 %r
}

define <2 x i8> @negate_nabs(<2 x i8> %x) {
  %n = sub <2 x i8> zeroinitializer, %x
  %c = icmp slt <2 x i8> %x, zeroinitializer
  %s = select <2 x i1> %c, <2 x i8> %x, <2 x i8> %n
  %r = sub <2 x i8> zeroinitializer, %s
  ret <2 x i8> %r
}

[spatel]

On 2nd thought, we're not actually changing the implicit branch here, so this should just propagate the metadata of the existing select.

[craig.topper]

Rebase to remvoe the InstCombine changes that were split off to another patch and have now been committed

[spatel]

LGTM.

[vitalybuka]

Reverted in r333253

[vitalybuka]

It should be safe to reland after r333295

lib/Analysis/ValueTracking.cpp

if (SPF == SPF_SMAX) {
       // leading one bits.
       MaxHighOnes =
           std::max(Known.countMinLeadingOnes(), Known2.countMinLeadingOnes());
     } else if (SPF == SPF_UMIN) {
       // We can derive an upper bound on the result by taking the max of the
       // leading zero bits.
       MaxHighZeros =
           std::max(Known.countMinLeadingZeros(), Known2.countMinLeadingZeros());
+    } else if (SPF == SPF_ABS) {
+      // RHS from matchSelectPattern returns the negation part of abs pattern.
+      // If the negate has an NSW flag we can assume the sign bit of the result
+      // will be 0 because that makes abs(INT_MIN) undefined.
+      if (cast<Instruction>(RHS)->hasNoSignedWrap())
+        MaxHighZeros = 1;
     }
 
     // Only known if known in both the LHS and RHS.
     Known.One &= Known2.One;
     Known.Zero &= Known2.Zero;
     if (MaxHighOnes > 0)
       Known.One.setHighBits(MaxHighOnes);
     if (MaxHighZeros > 0)

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Op0C->isNullValue()) {
         Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1);
         return BinaryOperator::CreateAShr(X, ShAmtOp);
       }
       if (match(Op1, m_AShr(m_Value(X), m_APInt(ShAmt))) &&
           *ShAmt == BitWidth - 1) {
         Value *ShAmtOp = cast<Instruction>(Op1)->getOperand(1);
         return BinaryOperator::CreateLShr(X, ShAmtOp);
       }
+
+      if (Op1->hasOneUse()) {
+        Value *LHS, *RHS;
+        SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor;
+        if (SPF == SPF_ABS || SPF == SPF_NABS) {
+          // This is a negate of an ABS/NABS pattern. Just swap the operands
+          // of the select.
+          SelectInst *SI = cast<SelectInst>(Op1);
+          return SelectInst::Create(SI->getCondition(), SI->getFalseValue(),
+                                    SI->getTrueValue());
+        }
+      }
     }
 
     // Turn this into a xor if LHS is 2^n-1 and the remaining bits are known
     // zero.
     if (Op0C->isMask()) {
       KnownBits RHSKnown = computeKnownBits(Op1, 0, &I);
       if ((*Op0C | RHSKnown.Zero).isAllOnesValue())
         return BinaryOperator::CreateXor(Op1, Op0);

test/Transforms/InstCombine/abs_abs.ll

;
   %cond18 = select i1 %cmp1, i32 %sub9, i32 %cond
   ret i32 %cond18
 }
 
 define i32 @nabs_abs_x09(i32 %x) {
 ; CHECK-LABEL: @nabs_abs_x09(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
-; CHECK-NEXT:    ret i32 [[COND1]]
+; CHECK-NEXT:    [[SUB16:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
+; CHECK-NEXT:    ret i32 [[SUB16]]
 ;
   %cmp = icmp sgt i32 %x, -1
   %sub = sub nsw i32 0, %x
   %cond = select i1 %cmp, i32 %x, i32 %sub
   %cmp1 = icmp slt i32 %cond, 0
   %sub16 = sub nsw i32 0, %cond
   %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
   ret i32 %cond18
 }
 
 define i32 @nabs_abs_x10(i32 %x) {
 ; CHECK-LABEL: @nabs_abs_x10(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
-; CHECK-NEXT:    ret i32 [[COND1]]
+; CHECK-NEXT:    [[SUB16:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
+; CHECK-NEXT:    ret i32 [[SUB16]]
 ;
   %cmp = icmp sgt i32 %x, 0
   %sub = sub nsw i32 0, %x
   %cond = select i1 %cmp, i32 %x, i32 %sub
   %cmp1 = icmp slt i32 %cond, 0
   %sub16 = sub nsw i32 0, %cond
   %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
   ret i32 %cond18
 }
 
 define i32 @nabs_abs_x11(i32 %x) {
 ; CHECK-LABEL: @nabs_abs_x11(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
-; CHECK-NEXT:    ret i32 [[COND1]]
+; CHECK-NEXT:    [[SUB16:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
+; CHECK-NEXT:    ret i32 [[SUB16]]
 ;
   %cmp = icmp slt i32 %x, 0
   %sub = sub nsw i32 0, %x
   %cond = select i1 %cmp, i32 %sub, i32 %x
   %cmp1 = icmp slt i32 %cond, 0
   %sub16 = sub nsw i32 0, %cond
   %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
   ret i32 %cond18
 }
 
 define i32 @nabs_abs_x12(i32 %x) {
 ; CHECK-LABEL: @nabs_abs_x12(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 0, [[X]]
-; CHECK-NEXT:    [[COND1:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
-; CHECK-NEXT:    ret i32 [[COND1]]
+; CHECK-NEXT:    [[SUB16:%.*]] = select i1 [[CMP]], i32 [[X]], i32 [[SUB]]
+; CHECK-NEXT:    ret i32 [[SUB16]]
 ;
   %cmp = icmp slt i32 %x, 1
   %sub = sub nsw i32 0, %x
   %cond = select i1 %cmp, i32 %sub, i32 %x
   %cmp1 = icmp slt i32 %cond, 0
   %sub16 = sub nsw i32 0, %cond
   %cond18 = select i1 %cmp1, i32 %cond, i32 %sub16
   ret i32 %cond18