[InstCombine] Fold abs of known negative operand

[nikic]

Summary

If we know that the abs operand is known negative, we can replace it with a neg.

To avoid computing known bits twice, I've removed the fold for the non-negative case from InstSimplify. Both the non-negative and the negative case are handled by InstCombine now, with one known bits call.

[nikic]

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

230

I've duplicated the relevant InstSimplify tests above here, to make sure they still fold in InstCombine.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

664–665

Either the function should have other name, or the return value pattern should be inverted,
because if the value is negative, we for sure know that the sign is 1, not 0.

[nikic]

Invert return value of getKnownSign().

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

664–665

Uh yeah, this didn't make sense. I couldn't think of a good name, so I ended up inverting the return value.

[spatel]

LGTM

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *simplifyBinaryIntrinsic(Function *F, Value *Op0, Value *Op1,
   unsigned BitWidth = ReturnType->getScalarSizeInBits();
   switch (IID) {
   case Intrinsic::abs:
     // abs(abs(x)) -> abs(x). We don't need to worry about the nsw arg here.
     // It is always ok to pick the earlier abs. We'll just lose nsw if its only
     // on the outer abs.
     if (match(Op0, m_Intrinsic<Intrinsic::abs>(m_Value(), m_Value())))
       return Op0;
-    // If the sign bit is clear already, then abs does not do anything.
-    if (isKnownNonNegative(Op0, Q.DL, 0, Q.AC, Q.CxtI, Q.DT))
-      return Op0;
     break;
 
   case Intrinsic::smax:
   case Intrinsic::smin:
   case Intrinsic::umax:
   case Intrinsic::umin: {
     // If the arguments are the same, this is a no-op.
     if (Op0 == Op1)

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

InstCombinerImpl::foldIntrinsicWithOverflowCommon(IntrinsicInst *II) {
   Value *OperationResult = nullptr;
   Constant *OverflowResult = nullptr;
   if (OptimizeOverflowCheck(WO->getBinaryOp(), WO->isSigned(), WO->getLHS(),
                             WO->getRHS(), *WO, OperationResult, OverflowResult))
     return createOverflowTuple(WO, OperationResult, OverflowResult);
   return nullptr;
 }
 
+static Optional<bool> getKnownSign(Value *Op, Instruction *CxtI,
+                                   const DataLayout &DL, AssumptionCache *AC,
+                                   DominatorTree *DT) {
+  KnownBits Known = computeKnownBits(Op, DL, 0, AC, CxtI, DT);
+  if (Known.isNonNegative())
+    return false;
+  if (Known.isNegative())
+    return true;
+
+  return isImpliedByDomCondition(
+      ICmpInst::ICMP_SLT, Op, Constant::getNullValue(Op->getType()), CxtI, DL);
+}
+
 /// CallInst simplification. This mostly only handles folding of intrinsic
 /// instructions. For normal calls, it allows visitCallBase to do the heavy
 /// lifting.
 Instruction *InstCombinerImpl::visitCallInst(CallInst &CI) {
   // Don't try to simplify calls without uses. It will not do anything useful,
   // but will result in the following folds being skipped.
   if (!CI.use_empty())
     if (Value *V = SimplifyCall(&CI, SQ.getWithInstruction(&CI)))
case Intrinsic::abs: {
     Value *X;
     if (match(IIOperand, m_Neg(m_Value(X))))
       return replaceOperand(*II, 0, X);
     if (match(IIOperand, m_Select(m_Value(), m_Value(X), m_Neg(m_Deferred(X)))))
       return replaceOperand(*II, 0, X);
     if (match(IIOperand, m_Select(m_Value(), m_Neg(m_Value(X)), m_Deferred(X))))
       return replaceOperand(*II, 0, X);
 
-    if (Optional<bool> Imp = isImpliedByDomCondition(
-            ICmpInst::ICMP_SGE, IIOperand,
-            Constant::getNullValue(IIOperand->getType()), II, DL)) {
+    if (Optional<bool> Sign = getKnownSign(IIOperand, II, DL, &AC, &DT)) {
       // abs(x) -> x if x >= 0
-      if (*Imp)
+      if (!*Sign)
         return replaceInstUsesWith(*II, IIOperand);
 
       // abs(x) -> -x if x < 0
       if (IntMinIsPoison)
         return BinaryOperator::CreateNSWNeg(IIOperand);
       return BinaryOperator::CreateNeg(IIOperand);
     }
 

llvm/test/Transforms/InstCombine/abs-intrinsic.ll

 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %assume = icmp sge i32 %x, 0
   call void @llvm.assume(i1 %assume)
   %abs = call i32 @llvm.abs.i32(i32 %x, i1 true)
   ret i32 %abs
 }
 
 ; Abs argument negative based on known bits.
 
 define i32 @abs_assume_neg(i32 %x) {
 ; CHECK-LABEL: @abs_assume_neg(
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP]])
-; CHECK-NEXT:    [[ABS:%.*]] = call i32 @llvm.abs.i32(i32 [[X]], i1 false)
+; CHECK-NEXT:    [[ABS:%.*]] = sub i32 0, [[X]]
 ; CHECK-NEXT:    ret i32 [[ABS]]
 ;
   %cmp = icmp slt i32 %x, 0
   call void @llvm.assume(i1 %cmp)
   %abs = call i32 @llvm.abs.i32(i32 %x, i1 false)
   ret i32 %abs
 }
 
 define i32 @abs_known_neg(i16 %x) {
 ; CHECK-LABEL: @abs_known_neg(
 ; CHECK-NEXT:    [[EXT:%.*]] = zext i16 [[X:%.*]] to i32
-; CHECK-NEXT:    [[NEG:%.*]] = xor i32 [[EXT]], -1
-; CHECK-NEXT:    [[ABS:%.*]] = call i32 @llvm.abs.i32(i32 [[NEG]], i1 false)
-; CHECK-NEXT:    ret i32 [[ABS]]
+; CHECK-NEXT:    [[NEG_NEG:%.*]] = add nuw nsw i32 [[EXT]], 1
+; CHECK-NEXT:    ret i32 [[NEG_NEG]]
 ;
   %ext = zext i16 %x to i32
   %neg = sub nsw i32 -1, %ext
   %abs = call i32 @llvm.abs.i32(i32 %neg, i1 false)
   ret i32 %abs
 }

llvm/test/Transforms/InstSimplify/abs_intrinsic.ll

 ; CHECK-NEXT:    ret i32 [[A]]
 ;
   %a = call i32 @llvm.abs.i32(i32 %x, i1 true)
   %b = call i32 @llvm.abs.i32(i32 %a, i1 true)
   ret i32 %b
 }
 
 ; If the sign bit is known zero, the abs is not needed.
+; These cases are only folded by InstCombine, to avoid computing known bits
+; twice, for the non-negative and the negative case.
 
 define i32 @zext_abs(i31 %x) {
 ; CHECK-LABEL: @zext_abs(
 ; CHECK-NEXT:    [[ZEXT:%.*]] = zext i31 [[X:%.*]] to i32
-; CHECK-NEXT:    ret i32 [[ZEXT]]
+; CHECK-NEXT:    [[ABS:%.*]] = call i32 @llvm.abs.i32(i32 [[ZEXT]], i1 false)
+; CHECK-NEXT:    ret i32 [[ABS]]
 ;
   %zext = zext i31 %x to i32
   %abs = call i32 @llvm.abs.i32(i32 %zext, i1 false)
   ret i32 %abs
 }
 
 define <3 x i82> @lshr_abs(<3 x i82> %x) {
 ; CHECK-LABEL: @lshr_abs(
 ; CHECK-NEXT:    [[LSHR:%.*]] = lshr <3 x i82> [[X:%.*]], <i82 1, i82 1, i82 1>
-; CHECK-NEXT:    ret <3 x i82> [[LSHR]]
+; CHECK-NEXT:    [[ABS:%.*]] = call <3 x i82> @llvm.abs.v3i82(<3 x i82> [[LSHR]], i1 true)
+; CHECK-NEXT:    ret <3 x i82> [[ABS]]
 ;
   %lshr = lshr <3 x i82> %x, <i82 1, i82 1, i82 1>
   %abs = call <3 x i82> @llvm.abs.v3i82(<3 x i82> %lshr, i1 true)
   ret <3 x i82> %abs
 }
 
 define i32 @and_abs(i32 %x) {
 ; CHECK-LABEL: @and_abs(
 ; CHECK-NEXT:    [[AND:%.*]] = and i32 [[X:%.*]], 2147483644
-; CHECK-NEXT:    ret i32 [[AND]]
+; CHECK-NEXT:    [[ABS:%.*]] = call i32 @llvm.abs.i32(i32 [[AND]], i1 true)
+; CHECK-NEXT:    ret i32 [[ABS]]
 ;
   %and = and i32 %x, 2147483644
   %abs = call i32 @llvm.abs.i32(i32 %and, i1 true)
   ret i32 %abs
 }
 
 define <3 x i82> @select_abs(<3 x i1> %cond) {
 ; CHECK-LABEL: @select_abs(
 ; CHECK-NEXT:    [[SEL:%.*]] = select <3 x i1> [[COND:%.*]], <3 x i82> zeroinitializer, <3 x i82> <i82 2147483647, i82 42, i82 1>
-; CHECK-NEXT:    ret <3 x i82> [[SEL]]
+; CHECK-NEXT:    [[ABS:%.*]] = call <3 x i82> @llvm.abs.v3i82(<3 x i82> [[SEL]], i1 false)
+; CHECK-NEXT:    ret <3 x i82> [[ABS]]
 ;
   %sel = select <3 x i1> %cond, <3 x i82> zeroinitializer, <3 x i82> <i82 2147483647, i82 42, i82 1>
   %abs = call <3 x i82> @llvm.abs.v3i82(<3 x i82> %sel, i1 false)
   ret <3 x i82> %abs
 }
 
 declare void @llvm.assume(i1)
 
 define i32 @assume_abs(i32 %x) {
 ; CHECK-LABEL: @assume_abs(
 ; CHECK-NEXT:    [[ASSUME:%.*]] = icmp sge i32 [[X:%.*]], 0
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[ASSUME]])
-; CHECK-NEXT:    ret i32 [[X]]
+; CHECK-NEXT:    [[ABS:%.*]] = call i32 @llvm.abs.i32(i32 [[X]], i1 true)
+; CHECK-NEXT:    ret i32 [[ABS]]
 ;
   %assume = icmp sge i32 %x, 0
   call void @llvm.assume(i1 %assume)
   %abs = call i32 @llvm.abs.i32(i32 %x, i1 true)
   ret i32 %abs
 }
 
 define i1 @abs_nsw_must_be_positive(i32 %x) {