[InstCombine] Fold sub(Y,and(lshr(X,C),1)) --> add(ashr(shl(X,(BW-1)-C),BW-1),Y) (PR53610)

[RKSimon]

Summary

As noted on PR53610, we can fold a 'bit splat' negation of a shifted bitmask pattern into a pair of shifts.

https://alive2.llvm.org/ce/z/eGrsoN

[lebedev.ri]

Please add tests w/ subtraction from a value, and then double the amount of tests by adding all the missing extra-use tests.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

193

Use m_ImmConstant unless there's a test/need to match a constant expression.

[RKSimon]

Use m_ImmConstant and oneUse checks

[lebedev.ri]

Hm, please also add an assortment of tests where there is a trunc inbetween, we really should handle that.

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

192

Since one-use check is required, this should go into the next switch which is use-constrained.

193

I think just plain m_c_And() would make more sense here.

194

SplattingShAmt

[RKSimon]

Add optional and(trunc(lshr(x,c)),1) support

[lebedev.ri]

LGTM, thank you.

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

253

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

case Instruction::Xor:
     if (match(I, m_Not(m_Value(X))))
       return Builder.CreateAdd(X, ConstantInt::get(X->getType(), 1),
                                I->getName() + ".neg");
     break;
   case Instruction::AShr:
   case Instruction::LShr: {
     // Right-shift sign bit smear is negatible.
     const APInt *Op1Val;
     if (match(I->getOperand(1), m_APInt(Op1Val)) && *Op1Val == BitWidth - 1) {
       Value *BO = I->getOpcode() == Instruction::AShr
                       ? Builder.CreateLShr(I->getOperand(0), I->getOperand(1))
                       : Builder.CreateAShr(I->getOperand(0), I->getOperand(1));
       if (auto *NewInstr = dyn_cast<Instruction>(BO)) {
         NewInstr->copyIRFlags(I);
         NewInstr->setName(I->getName() + ".neg");
       }
       return BO;
     }
     // While we could negate exact arithmetic shift:
LLVM_NODISCARD Value *Negator::visitImpl(Value *V, unsigned Depth) {
   }
 
   // Some other cases, while still don't require recursion,
   // are restricted to the one-use case.
   if (!V->hasOneUse())
     return nullptr;
 
   switch (I->getOpcode()) {
+  case Instruction::And: {
+    Constant *ShAmt;
+    // sub(y,and(lshr(x,C),1)) --> add(ashr(shl(x,(BW-1)-C),BW-1),y)
+    if (match(I, m_c_And(m_OneUse(m_TruncOrSelf(
+                             m_LShr(m_Value(X), m_ImmConstant(ShAmt)))),
+                         m_One()))) {
+      unsigned BW = X->getType()->getScalarSizeInBits();
+      Constant *BWMinusOne = ConstantInt::get(X->getType(), BW - 1);
+      Value *R = Builder.CreateShl(X, Builder.CreateSub(BWMinusOne, ShAmt));
+      R = Builder.CreateAShr(R, BWMinusOne);
+      return Builder.CreateTruncOrBitCast(R, I->getType());
+    }
+    break;
+  }
   case Instruction::SDiv:
     // `sdiv` is negatible if divisor is not undef/INT_MIN/1.
     // While this is normally not behind a use-check,
     // let's consider division to be special since it's costly.
     if (auto *Op1C = dyn_cast<Constant>(I->getOperand(1))) {
       if (!Op1C->containsUndefOrPoisonElement() &&
           Op1C->isNotMinSignedValue() && Op1C->isNotOneValue()) {
         Value *BO =

llvm/test/Transforms/InstCombine/negated-bitmask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 ; PR53610 - sub(0,and(lshr(X,C1),1)) --> ashr(shl(X,(BW-1)-C1),BW-1)
 ; PR53610 - sub(C2,and(lshr(X,C1),1)) --> add(ashr(shl(X,(BW-1)-C1),BW-1),C2)
 
 define i8 @neg_mask1_lshr(i8 %a0) {
 ; CHECK-LABEL: @neg_mask1_lshr(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr i8 [[A0:%.*]], 3
-; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[SHIFT]], 1
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw i8 0, [[MASK]]
-; CHECK-NEXT:    ret i8 [[NEG]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[A0:%.*]], 4
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr i8 [[TMP1]], 7
+; CHECK-NEXT:    ret i8 [[TMP2]]
 ;
   %shift = lshr i8 %a0, 3
   %mask = and i8 %shift, 1
   %neg = sub i8 0, %mask
   ret i8 %neg
 }
 
 define i8 @sub_mask1_lshr(i8 %a0) {
 ; CHECK-LABEL: @sub_mask1_lshr(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr i8 [[A0:%.*]], 1
-; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[SHIFT]], 1
-; CHECK-NEXT:    [[NEG:%.*]] = sub nuw nsw i8 10, [[MASK]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[A0:%.*]], 6
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr i8 [[TMP1]], 7
+; CHECK-NEXT:    [[NEG:%.*]] = add nsw i8 [[TMP2]], 10
 ; CHECK-NEXT:    ret i8 [[NEG]]
 ;
   %shift = lshr i8 %a0, 1
   %mask = and i8 %shift, 1
   %neg = sub i8 10, %mask
   ret i8 %neg
 }
 
 define <4 x i32> @neg_mask1_lshr_vector_uniform(<4 x i32> %a0) {
 ; CHECK-LABEL: @neg_mask1_lshr_vector_uniform(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr <4 x i32> [[A0:%.*]], <i32 3, i32 3, i32 3, i32 3>
-; CHECK-NEXT:    [[MASK:%.*]] = and <4 x i32> [[SHIFT]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <4 x i32> zeroinitializer, [[MASK]]
-; CHECK-NEXT:    ret <4 x i32> [[NEG]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <4 x i32> [[A0:%.*]], <i32 28, i32 28, i32 28, i32 28>
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr <4 x i32> [[TMP1]], <i32 31, i32 31, i32 31, i32 31>
+; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
 ;
   %shift = lshr <4 x i32> %a0, <i32 3, i32 3, i32 3, i32 3>
   %mask = and <4 x i32> %shift, <i32 1, i32 1, i32 1, i32 1>
   %neg = sub <4 x i32> zeroinitializer, %mask
   ret <4 x i32> %neg
 }
 
 define <4 x i32> @neg_mask1_lshr_vector_nonuniform(<4 x i32> %a0) {
 ; CHECK-LABEL: @neg_mask1_lshr_vector_nonuniform(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr <4 x i32> [[A0:%.*]], <i32 3, i32 4, i32 5, i32 6>
-; CHECK-NEXT:    [[MASK:%.*]] = and <4 x i32> [[SHIFT]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <4 x i32> zeroinitializer, [[MASK]]
-; CHECK-NEXT:    ret <4 x i32> [[NEG]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <4 x i32> [[A0:%.*]], <i32 28, i32 27, i32 26, i32 25>
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr <4 x i32> [[TMP1]], <i32 31, i32 31, i32 31, i32 31>
+; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
 ;
   %shift = lshr <4 x i32> %a0, <i32 3, i32 4, i32 5, i32 6>
   %mask = and <4 x i32> %shift, <i32 1, i32 1, i32 1, i32 1>
   %neg = sub <4 x i32> zeroinitializer, %mask
   ret <4 x i32> %neg
 }
 
 define <4 x i32> @sub_mask1_lshr_vector_nonuniform(<4 x i32> %a0) {
 ; CHECK-LABEL: @sub_mask1_lshr_vector_nonuniform(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr <4 x i32> [[A0:%.*]], <i32 3, i32 4, i32 5, i32 6>
-; CHECK-NEXT:    [[MASK:%.*]] = and <4 x i32> [[SHIFT]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[NEG:%.*]] = sub nsw <4 x i32> <i32 5, i32 0, i32 -1, i32 65556>, [[MASK]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl <4 x i32> [[A0:%.*]], <i32 28, i32 27, i32 26, i32 25>
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr <4 x i32> [[TMP1]], <i32 31, i32 31, i32 31, i32 31>
+; CHECK-NEXT:    [[NEG:%.*]] = add nsw <4 x i32> [[TMP2]], <i32 5, i32 0, i32 -1, i32 65556>
 ; CHECK-NEXT:    ret <4 x i32> [[NEG]]
 ;
   %shift = lshr <4 x i32> %a0, <i32 3, i32 4, i32 5, i32 6>
   %mask = and <4 x i32> %shift, <i32 1, i32 1, i32 1, i32 1>
   %neg = sub <4 x i32> <i32 5, i32 0, i32 -1, i32 65556>, %mask
   ret <4 x i32> %neg
 }
 
 define i8 @sub_mask1_trunc_lshr(i64 %a0) {
 ; CHECK-LABEL: @sub_mask1_trunc_lshr(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr i64 [[A0:%.*]], 15
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[SHIFT]] to i8
-; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[TRUNC]], 1
-; CHECK-NEXT:    [[NEG:%.*]] = sub nuw nsw i8 10, [[MASK]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[A0:%.*]], 48
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr i64 [[TMP1]], 63
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP2]] to i8
+; CHECK-NEXT:    [[NEG:%.*]] = add i8 [[TMP3]], 10
 ; CHECK-NEXT:    ret i8 [[NEG]]
 ;
   %shift = lshr i64 %a0, 15
   %trunc = trunc i64 %shift to i8
   %mask = and i8 %trunc, 1
   %neg = sub i8 10, %mask
   ret i8 %neg
 }
 
 define i32 @sub_sext_mask1_trunc_lshr(i64 %a0) {
 ; CHECK-LABEL: @sub_sext_mask1_trunc_lshr(
-; CHECK-NEXT:    [[SHIFT:%.*]] = lshr i64 [[A0:%.*]], 15
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i64 [[SHIFT]] to i8
-; CHECK-NEXT:    [[MASK:%.*]] = and i8 [[TRUNC]], 1
-; CHECK-NEXT:    [[NARROW:%.*]] = sub nuw nsw i8 10, [[MASK]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[A0:%.*]], 48
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr i64 [[TMP1]], 63
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP2]] to i8
+; CHECK-NEXT:    [[NARROW:%.*]] = add i8 [[TMP3]], 10
 ; CHECK-NEXT:    [[NEG:%.*]] = zext i8 [[NARROW]] to i32
 ; CHECK-NEXT:    ret i32 [[NEG]]
 ;
   %shift = lshr i64 %a0, 15
   %trunc = trunc i64 %shift to i8
   %mask = and i8 %trunc, 1
   %sext = sext i8 %mask to i32
   %neg = sub i32 10, %sext
   ret i32 %neg
 }
 
 define i32 @sub_zext_trunc_lshr(i64 %a0) {
 ; CHECK-LABEL: @sub_zext_trunc_lshr(
 ; CHECK-NEXT:    [[TMP1:%.*]] = trunc i64 [[A0:%.*]] to i32
-; CHECK-NEXT:    [[TMP2:%.*]] = lshr i32 [[TMP1]], 15
-; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP2]], 1
-; CHECK-NEXT:    [[NEG:%.*]] = sub nuw nsw i32 10, [[TMP3]]
+; CHECK-NEXT:    [[TMP2:%.*]] = shl i32 [[TMP1]], 16
+; CHECK-NEXT:    [[TMP3:%.*]] = ashr i32 [[TMP2]], 31
+; CHECK-NEXT:    [[NEG:%.*]] = add nsw i32 [[TMP3]], 10
 ; CHECK-NEXT:    ret i32 [[NEG]]
 ;
   %shift = lshr i64 %a0, 15
   %trunc = trunc i64 %shift to i1
   %sext = zext i1 %trunc to i32
   %neg = sub i32 10, %sext
   ret i32 %neg
 }