[InstCombine] Transform abs pattern using multiplication to abs intrinsic (PR45691)

[xbolva00]

Summary

unsigned r(int v)
{
    return (1 | -(v < 0)) * v;
}

`r` is equivalent to `abs(v)`.

define <4 x i8> @src(<4 x i8> %0) {
%1:
  %2 = ashr <4 x i8> %0, { 31, undef, 31, 31 }
  %3 = or <4 x i8> %2, { 1, 1, 1, undef }
  %4 = mul nsw <4 x i8> %3, %0
  ret <4 x i8> %4
}
=>
define <4 x i8> @tgt(<4 x i8> %0) {
%1:
  %2 = icmp slt <4 x i8> %0, { 0, 0, 0, 0 }
  %3 = sub nsw <4 x i8> { 0, 0, 0, 0 }, %0
  %4 = select <4 x i1> %2, <4 x i8> %3, <4 x i8> %0
  ret <4 x i8> %4
}
Transformation seems to be correct!

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

375

Doesn't just return Builder.CreateBinaryIntrinsic work here?

llvm/test/Transforms/InstCombine/ashr-or-mul-abs.ll

37

git grep thwart llvm/test/Transforms/InstCombine. Your current test is effectively equivalent to the previous one due to complexity canonicalization.

102–115

Missing a test where the two %X are not the same.

[xbolva00]

Addressed review comments

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

375

void llvm::SymbolTableListTraits<ValueSubClass>::addNodeToList(ValueSubClass*) [with ValueSubClass = llvm::Instruction]: Assertion `!V->getParent() && "Value already in a container!!"' failed.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

375

Oh right. Thanks for checking.

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

if (SimplifyAssociativeOrCommutative(I))
     return &I;
 
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
-  // X * -1 == 0 - X
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
+  unsigned BitWidth = I.getType()->getScalarSizeInBits();
+
+  // X * -1 == 0 - X
   if (match(Op1, m_AllOnes())) {
     BinaryOperator *BO = BinaryOperator::CreateNeg(Op0, I.getName());
     if (I.hasNoSignedWrap())
       BO->setHasNoSignedWrap();
     return BO;
   }
 
   // Also allow combining multiply instructions on vectors.
Instruction *InstCombinerImpl::visitMul(BinaryOperator &I) {
   // TODO: Should we canonicalize to '(X < 0) ? Y : 0' instead? That would be
   //       more similar to what we're doing above.
   const APInt *C;
   if (match(Op0, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
     return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op1);
   if (match(Op1, m_LShr(m_Value(X), m_APInt(C))) && *C == C->getBitWidth() - 1)
     return BinaryOperator::CreateAnd(Builder.CreateAShr(X, *C), Op0);
 
+  // ((ashr X, 31) | 1) * X --> abs(X)
+  // X * ((ashr X, 31) | 1) --> abs(X)
+  if (match(&I, m_c_BinOp(m_Or(m_AShr(m_Value(X),
+                                    m_SpecificIntAllowUndef(BitWidth - 1)),
+                             m_One()),
+                        m_Deferred(X)))) {
+    Value *Abs = Builder.CreateBinaryIntrinsic(
+        Intrinsic::abs, X,
+        ConstantInt::getBool(I.getContext(), I.hasNoSignedWrap()));
+    Abs->takeName(&I);
+    return replaceInstUsesWith(I, Abs);
+  }
+
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedMul(Op0, Op1, I)) {
     Changed = true;
     I.setHasNoSignedWrap(true);
   }

llvm/test/Transforms/InstCombine/ashr-or-mul-abs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; ((ashr X, 31) | 1 ) * X --> abs(X)
 ; X * ((ashr X, 31) | 1 ) --> abs(X)
 
 define i32 @ashr_or_mul_to_abs(i32 %X) {
 ; CHECK-LABEL: @ashr_or_mul_to_abs(
-; CHECK-NEXT:    [[I:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[I1:%.*]] = or i32 [[I]], 1
-; CHECK-NEXT:    [[I2:%.*]] = mul nsw i32 [[I1]], [[X]]
+; CHECK-NEXT:    [[I2:%.*]] = call i32 @llvm.abs.i32(i32 [[X:%.*]], i1 true)
 ; CHECK-NEXT:    ret i32 [[I2]]
 ;
   %i = ashr i32 %X, 31
   %i1 = or i32 %i, 1
   %i2 = mul nsw i32 %i1, %X
   ret i32 %i2
 }
 
 define i32 @ashr_or_mul_to_abs2(i32 %X) {
 ; CHECK-LABEL: @ashr_or_mul_to_abs2(
-; CHECK-NEXT:    [[I:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[I1:%.*]] = or i32 [[I]], 1
-; CHECK-NEXT:    [[I2:%.*]] = mul i32 [[I1]], [[X]]
+; CHECK-NEXT:    [[I2:%.*]] = call i32 @llvm.abs.i32(i32 [[X:%.*]], i1 false)
 ; CHECK-NEXT:    ret i32 [[I2]]
 ;
   %i = ashr i32 %X, 31
   %i1 = or i32 %i, 1
   %i2 = mul i32 %i1, %X
   ret i32 %i2
 }
 
-define i32 @ashr_or_mul_to_abs3(i32 %X) {
+define i32 @ashr_or_mul_to_abs3(i32 %PX) {
 ; CHECK-LABEL: @ashr_or_mul_to_abs3(
-; CHECK-NEXT:    [[I:%.*]] = ashr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[I1:%.*]] = or i32 [[I]], 1
-; CHECK-NEXT:    [[I2:%.*]] = mul i32 [[I1]], [[X]]
+; CHECK-NEXT:    [[X:%.*]] = sdiv i32 42, [[PX:%.*]]
+; CHECK-NEXT:    [[I2:%.*]] = call i32 @llvm.abs.i32(i32 [[X]], i1 false)
 ; CHECK-NEXT:    ret i32 [[I2]]
 ;
+  %X = sdiv i32 42, %PX ; thwart complexity-based canonicalization
   %i = ashr i32 %X, 31
   %i1 = or i32 %i, 1
   %i2 = mul i32 %X, %i1
   ret i32 %i2
 }
 
 
 define <4 x i32> @ashr_or_mul_to_abs_vec(<4 x i32> %X) {
 ; CHECK-LABEL: @ashr_or_mul_to_abs_vec(
-; CHECK-NEXT:    [[I:%.*]] = ashr <4 x i32> [[X:%.*]], <i32 31, i32 31, i32 31, i32 31>
-; CHECK-NEXT:    [[I1:%.*]] = or <4 x i32> [[I]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[I2:%.*]] = mul <4 x i32> [[I1]], [[X]]
+; CHECK-NEXT:    [[I2:%.*]] = call <4 x i32> @llvm.abs.v4i32(<4 x i32> [[X:%.*]], i1 false)
 ; CHECK-NEXT:    ret <4 x i32> [[I2]]
 ;
   %i = ashr <4 x i32> %X, <i32 31, i32 31, i32 31, i32 31>
   %i1 = or <4 x i32> %i, <i32 1, i32 1, i32 1, i32 1>
   %i2 = mul <4 x i32> %i1, %X
   ret <4 x i32> %i2
 }
 
 define <4 x i32> @ashr_or_mul_to_abs_vec2(<4 x i32> %X) {
 ; CHECK-LABEL: @ashr_or_mul_to_abs_vec2(
-; CHECK-NEXT:    [[I:%.*]] = ashr <4 x i32> [[X:%.*]], <i32 31, i32 31, i32 31, i32 31>
-; CHECK-NEXT:    [[I1:%.*]] = or <4 x i32> [[I]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[I2:%.*]] = mul nsw <4 x i32> [[I1]], [[X]]
+; CHECK-NEXT:    [[I2:%.*]] = call <4 x i32> @llvm.abs.v4i32(<4 x i32> [[X:%.*]], i1 true)
 ; CHECK-NEXT:    ret <4 x i32> [[I2]]
 ;
   %i = ashr <4 x i32> %X, <i32 31, i32 31, i32 31, i32 31>
   %i1 = or <4 x i32> %i, <i32 1, i32 1, i32 1, i32 1>
   %i2 = mul nsw <4 x i32> %i1, %X
   ret <4 x i32> %i2
 }
 
 define <4 x i32> @ashr_or_mul_to_abs_vec3_undef(<4 x i32> %X) {
 ; CHECK-LABEL: @ashr_or_mul_to_abs_vec3_undef(
-; CHECK-NEXT:    [[I:%.*]] = ashr <4 x i32> [[X:%.*]], <i32 31, i32 undef, i32 31, i32 31>
-; CHECK-NEXT:    [[I1:%.*]] = or <4 x i32> [[I]], <i32 1, i32 1, i32 1, i32 undef>
-; CHECK-NEXT:    [[I2:%.*]] = mul <4 x i32> [[I1]], [[X]]
+; CHECK-NEXT:    [[I2:%.*]] = call <4 x i32> @llvm.abs.v4i32(<4 x i32> [[X:%.*]], i1 false)
 ; CHECK-NEXT:    ret <4 x i32> [[I2]]
 ;
   %i = ashr <4 x i32> %X, <i32 31, i32 undef, i32 31, i32 31>
   %i1 = or <4 x i32> %i, <i32 1, i32 1, i32 1, i32 undef>
   %i2 = mul <4 x i32> %i1, %X
   ret <4 x i32> %i2
 }
 

 ; CHECK-NEXT:    [[I1:%.*]] = or i32 [[I]], 2
 ; CHECK-NEXT:    [[I2:%.*]] = mul nsw i32 [[I1]], [[X]]
 ; CHECK-NEXT:    ret i32 [[I2]]
 ;
   %i = ashr i32 %X, 31
   %i1 = or i32 %i, 2
   %i2 = mul nsw i32 %i1, %X
   ret i32 %i2
 }
+
+define i32 @ashr_or_mul_to_abs_neg3(i32 %X, i32 %Y) {
+; CHECK-LABEL: @ashr_or_mul_to_abs_neg3(
+; CHECK-NEXT:    [[I:%.*]] = ashr i32 [[X:%.*]], 31
+; CHECK-NEXT:    [[I1:%.*]] = or i32 [[I]], 1
+; CHECK-NEXT:    [[I2:%.*]] = mul nsw i32 [[I1]], [[Y:%.*]]
+; CHECK-NEXT:    ret i32 [[I2]]
+;
+  %i = ashr i32 %X, 31
+  %i1 = or i32 %i, 1
+  %i2 = mul nsw i32 %i1, %Y
+  ret i32 %i2
+}