[InstCombine] canShiftBinOpWithConstantRHS(): drop bogus(?) signbit check

[lebedev.ri]

Summary

In D61918 i was looking at dropping it in DAGCombiner visitShiftByConstant(),
but as @craig.topper pointed out, it was copied from here.

That check claims that the transform is illegal otherwise.
That isn't true:

1. For ISD::ADD, we only process ISD::SHL outer shift => sign bit does not matter https://rise4fun.com/Alive/K4A
2. For ISD::AND, there is no restriction on constants: https://rise4fun.com/Alive/Wy3
3. For ISD::OR, there is no restriction on constants: https://rise4fun.com/Alive/GOH
4. For ISD::XOR, there is no restriction on constants: https://rise4fun.com/Alive/ml6

So, why is it there then?
As far as i can tell, it dates all the way back to original check-in rL7793.
I think we should just drop it.

[spatel]

I don't see a reason for the constant limitation, but either way, we should have some minimal tests to verify (and change assuming this patch is committed):

define i32 @or_ashr(i32 %x) {
  %b = or i32 %x, 2147483648 ; 0x80000000
  %r = ashr i32 %b, 8
  ret i32 %r
}
define i32 @xor_ashr(i32 %x) {
  %b = xor i32 %x, 2147483648 ; 0x80000000
  %r = ashr i32 %b, 8
  ret i32 %r
}
; and with ashr is unreachable because it always get converted to lshr?

Also, add the related patterns with a 'select'?

lib/Transforms/InstCombine/InstCombineShifts.cpp

319

Remove unreachable 'break'.

[lebedev.ri]

Added proper full test coverage.

[lebedev.ri]

I have manually checked these changed tests in alive, and they are all good.

[spatel]

LGTM

lib/Transforms/InstCombine/InstCombineShifts.cpp

case Instruction::PHI: {
     return PN;
   }
   }
 }
 
 // If this is a bitwise operator or add with a constant RHS we might be able
 // to pull it through a shift.
 static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
-                                         BinaryOperator *BO,
-                                         const APInt &C) {
-  bool IsValid = true;     // Valid only for And, Or Xor,
-  bool HighBitSet = false; // Transform ifhigh bit of constant set?
-
+                                         BinaryOperator *BO) {
   switch (BO->getOpcode()) {
-  default: IsValid = false; break;   // Do not perform transform!
+  default:
+    return false; // Do not perform transform!
   case Instruction::Add:
-    IsValid = Shift.getOpcode() == Instruction::Shl;
-    break;
+    return Shift.getOpcode() == Instruction::Shl;
   case Instruction::Or:
   case Instruction::Xor:
-    HighBitSet = false;
-    break;
   case Instruction::And:
-    HighBitSet = true;
-    break;
+    return true;
   }
-
-  // If this is a signed shift right, and the high bit is modified
-  // by the logical operation, do not perform the transformation.
-  // The HighBitSet boolean indicates the value of the high bit of
-  // the constant which would cause it to be modified for this
-  // operation.
-  //
-  if (IsValid && Shift.getOpcode() == Instruction::AShr)
-    IsValid = C.isNegative() == HighBitSet;
-
-  return IsValid;
 }
 
 Instruction *InstCombiner::FoldShiftByConstant(Value *Op0, Constant *Op1,
                                                BinaryOperator &I) {
   bool isLeftShift = I.getOpcode() == Instruction::Shl;
 
   const APInt *Op1C;
   if (!match(Op1, m_APInt(Op1C)))
if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
       }
       }
 
 
       // If the operand is a bitwise operator with a constant RHS, and the
       // shift is the only use, we can pull it out of the shift.
       const APInt *Op0C;
       if (match(Op0BO->getOperand(1), m_APInt(Op0C))) {
-        if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) {
+        if (canShiftBinOpWithConstantRHS(I, Op0BO)) {
           Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
                                      cast<Constant>(Op0BO->getOperand(1)), Op1);
 
           Value *NewShift =
             Builder.CreateBinOp(I.getOpcode(), Op0BO->getOperand(0), Op1);
           NewShift->takeName(Op0BO);
 
           return BinaryOperator::Create(Op0BO->getOpcode(), NewShift,
if (Op0->hasOneUse()) {
     Value *Cond;
     BinaryOperator *TBO;
     Value *FalseVal;
     if (match(Op0, m_Select(m_Value(Cond), m_OneUse(m_BinOp(TBO)),
                             m_Value(FalseVal)))) {
       const APInt *C;
       if (!isa<Constant>(FalseVal) && TBO->getOperand(0) == FalseVal &&
           match(TBO->getOperand(1), m_APInt(C)) &&
-          canShiftBinOpWithConstantRHS(I, TBO, *C)) {
+          canShiftBinOpWithConstantRHS(I, TBO)) {
         Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
                                        cast<Constant>(TBO->getOperand(1)), Op1);
 
         Value *NewShift =
           Builder.CreateBinOp(I.getOpcode(), FalseVal, Op1);
         Value *NewOp = Builder.CreateBinOp(TBO->getOpcode(), NewShift,
                                            NewRHS);
         return SelectInst::Create(Cond, NewOp, NewShift);
       }
     }
 
     BinaryOperator *FBO;
     Value *TrueVal;
     if (match(Op0, m_Select(m_Value(Cond), m_Value(TrueVal),
                             m_OneUse(m_BinOp(FBO))))) {
       const APInt *C;
       if (!isa<Constant>(TrueVal) && FBO->getOperand(0) == TrueVal &&
           match(FBO->getOperand(1), m_APInt(C)) &&
-          canShiftBinOpWithConstantRHS(I, FBO, *C)) {
+          canShiftBinOpWithConstantRHS(I, FBO)) {
         Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
                                        cast<Constant>(FBO->getOperand(1)), Op1);
 
         Value *NewShift =
           Builder.CreateBinOp(I.getOpcode(), TrueVal, Op1);
         Value *NewOp = Builder.CreateBinOp(FBO->getOpcode(), NewShift,
                                            NewRHS);
         return SelectInst::Create(Cond, NewShift, NewOp);

test/Transforms/InstCombine/pull-binop-through-shift.ll

 ;
   %t0 = and i32 %x, 2147418112 ; 0x7FFF0000
   %r = ashr i32 %t0, 8
   ret i32 %r
 }
 
 define i32 @or_signbit_ashr(i32 %x) {
 ; CHECK-LABEL: @or_signbit_ashr(
-; CHECK-NEXT:    [[T0:%.*]] = or i32 [[X:%.*]], -65536
-; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[T0]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[R:%.*]] = or i32 [[TMP1]], -256
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = or i32 %x, 4294901760 ; 0xFFFF0000
   %r = ashr i32 %t0, 8
   ret i32 %r
 }
 define i32 @or_nosignbit_ashr(i32 %x) {
 ; CHECK-LABEL: @or_nosignbit_ashr(
 ; CHECK-NEXT:    [[T0:%.*]] = ashr i32 [[X:%.*]], 8
 ; CHECK-NEXT:    [[R:%.*]] = or i32 [[T0]], 8388352
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = or i32 %x, 2147418112 ; 0x7FFF0000
   %r = ashr i32 %t0, 8
   ret i32 %r
 }
 
 define i32 @xor_signbit_ashr(i32 %x) {
 ; CHECK-LABEL: @xor_signbit_ashr(
-; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -65536
-; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[T0]], 8
+; CHECK-NEXT:    [[T0:%.*]] = ashr i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[R:%.*]] = xor i32 [[T0]], -256
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = xor i32 %x, 4294901760 ; 0xFFFF0000
   %r = ashr i32 %t0, 8
   ret i32 %r
 }
 define i32 @xor_nosignbit_ashr(i32 %x) {
 ; CHECK-LABEL: @xor_nosignbit_ashr(

test/Transforms/InstCombine/pull-conditional-binop-through-shift.ll

 ;
   %t0 = and i32 %x, 4294901760 ; 0xFFFF0000
   %t1 = select i1 %cond, i32 %t0, i32 %x
   %r = ashr i32 %t1, 8
   ret i32 %r
 }
 define i32 @and_nosignbit_select_ashr(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @and_nosignbit_select_ashr(
-; CHECK-NEXT:    [[T0:%.*]] = and i32 [[X:%.*]], 2147418112
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[COND:%.*]], i32 [[T0]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[T1]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 8388352
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = and i32 %x, 2147418112 ; 0x7FFF0000
   %t1 = select i1 %cond, i32 %t0, i32 %x
   %r = ashr i32 %t1, 8
   ret i32 %r
 }
 
 define i32 @or_signbit_select_ashr(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @or_signbit_select_ashr(
-; CHECK-NEXT:    [[T0:%.*]] = or i32 [[X:%.*]], -65536
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[COND:%.*]], i32 [[T0]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[T1]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], -256
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = or i32 %x, 4294901760 ; 0xFFFF0000
   %t1 = select i1 %cond, i32 %t0, i32 %x
   %r = ashr i32 %t1, 8
   ret i32 %r
 }
 define i32 @or_nosignbit_select_ashr(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @or_nosignbit_select_ashr(
 ; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 8
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], 8388352
 ; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = or i32 %x, 2147418112 ; 0x7FFF0000
   %t1 = select i1 %cond, i32 %t0, i32 %x
   %r = ashr i32 %t1, 8
   ret i32 %r
 }
 
 define i32 @xor_signbit_select_ashr(i32 %x, i1 %cond) {
 ; CHECK-LABEL: @xor_signbit_select_ashr(
-; CHECK-NEXT:    [[T0:%.*]] = xor i32 [[X:%.*]], -65536
-; CHECK-NEXT:    [[T1:%.*]] = select i1 [[COND:%.*]], i32 [[T0]], i32 [[X]]
-; CHECK-NEXT:    [[R:%.*]] = ashr i32 [[T1]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = ashr i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -256
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[COND:%.*]], i32 [[TMP2]], i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = xor i32 %x, 4294901760 ; 0xFFFF0000
   %t1 = select i1 %cond, i32 %t0, i32 %x
   %r = ashr i32 %t1, 8
   ret i32 %r
 }
 define i32 @xor_nosignbit_select_ashr(i32 %x, i1 %cond) {

test/Transforms/InstCombine/trunc.ll

;
   %C = mul i20 %A, %B
   %D = ashr i20 %C, 8
   %E = trunc i20 %D to i16
   ret i16 %E
 }
 
 define i32 @trunc_ashr(i32 %X) {
 ; CHECK-LABEL: @trunc_ashr(
-; CHECK-NEXT:    [[B:%.*]] = or i32 [[X:%.*]], -2147483648
-; CHECK-NEXT:    [[C:%.*]] = ashr i32 [[B]], 8
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 8
+; CHECK-NEXT:    [[C:%.*]] = or i32 [[TMP1]], -8388608
 ; CHECK-NEXT:    ret i32 [[C]]
 ;
   %A = zext i32 %X to i36
   %B = or i36 %A, -2147483648 ; 0xF80000000
   %C = ashr i36 %B, 8
   %T = trunc i36 %C to i32
   ret i32  %T
 }
 
 define <2 x i32> @trunc_ashr_vec(<2 x i32> %X) {
 ; CHECK-LABEL: @trunc_ashr_vec(
-; CHECK-NEXT:    [[B:%.*]] = or <2 x i32> [[X:%.*]], <i32 -2147483648, i32 -2147483648>
-; CHECK-NEXT:    [[C:%.*]] = ashr <2 x i32> [[B]], <i32 8, i32 8>
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 8, i32 8>
+; CHECK-NEXT:    [[C:%.*]] = or <2 x i32> [[TMP1]], <i32 -8388608, i32 -8388608>
 ; CHECK-NEXT:    ret <2 x i32> [[C]]
 ;
   %A = zext <2 x i32> %X to <2 x i36>
   %B = or <2 x i36> %A, <i36 -2147483648, i36 -2147483648> ; 0xF80000000
   %C = ashr <2 x i36> %B, <i36 8, i36 8>
   %T = trunc <2 x i36> %C to <2 x i32>
   ret <2 x i32>  %T
 }