[InstCombine] (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1

[xbolva00]

Summary

%a = sub i32 31, %x
%r = shl i32 1, %a
  =>
%d = shl i32 1, 31
%r = lshr i32 %d, %x

Done: 1
Optimization is correct!

https://rise4fun.com/Alive/btZm

[nikic]

lib/Transforms/InstCombine/InstCombineShifts.cpp

677 ↗

(On Diff #206005)

getSExtValue will assert if the value is too large. You can use ShlOp0->isOneValue() here.

679 ↗

(On Diff #206005)

Same issue here. I think just doing *C == BitWidth - 1 should work.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineShifts.cpp

677 ↗

(On Diff #206005)

m_One()

678–679 ↗

(On Diff #206005)

m_SpecificInt(BitWidth - 1)

680 ↗

(On Diff #206005)

ConstantInt::get(Ty, APInt::getSignMask(BitWidth))

[nikic]

lib/Transforms/InstCombine/InstCombineShifts.cpp

677 ↗

(On Diff #206005)

Or maybe even simpler, use match(Op0, m_One()).

[xbolva00]

Simplified code.

Thanks for cool notes, @nikic, @lebedev.ri !

[lebedev.ri]

Please mark fixed comments as such

[lebedev.ri]

Please precommit those 3 extra tests first though

test/Transforms/InstCombine/shl-sub.ll

56 ↗

(On Diff #206010)

missing 3 tests with undef:

define <3 x i64> @shl_sub_i64_vec_undef0(<3 x i64> %x) {
  %s = sub <3 x i64> <i64 63, i64 undef, i64 63>, %x
  %r = shl <3 x i64> <i64 1, i64 1, i64 1>, %s
  ret <3 x i64> %r
}

define <3 x i64> @shl_sub_i64_vec_undef1(<3 x i64> %x) {
  %s = sub <3 x i64> <i64 63, undef, i64 63>, %x
  %r = shl <3 x i64> <i64 1, i64 undef, i64 1>, %s
  ret <3 x i64> %r
}

define <3 x i64> @shl_sub_i64_vec_undef2(<3 x i64> %x) {
  %s = sub <3 x i64> <i64 63, i64 undef, i64 63>, %x
  %r = shl <3 x i64> <i64 1, i64 undef, i64 1>, %s
  ret <3 x i64> %r
}

[xbolva00]

Updated tests

llvm/trunk/lib/Transforms/InstCombine/InstCombineShifts.cpp

Instruction *InstCombiner::visitShl(BinaryOperator &I) {
   if (Instruction *X = foldVectorBinop(I))
     return X;
 
   if (Instruction *V = commonShiftTransforms(I))
     return V;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Type *Ty = I.getType();
+  unsigned BitWidth = Ty->getScalarSizeInBits();
+
   const APInt *ShAmtAPInt;
   if (match(Op1, m_APInt(ShAmtAPInt))) {
     unsigned ShAmt = ShAmtAPInt->getZExtValue();
     unsigned BitWidth = Ty->getScalarSizeInBits();
 
     // shl (zext X), ShAmt --> zext (shl X, ShAmt)
     // This is only valid if X would have zeros shifted out.
     Value *X;
if (match(Op1, m_Constant(C1))) {
     if (match(Op0, m_OneUse(m_Shl(m_Constant(C2), m_Value(X)))))
       return BinaryOperator::CreateShl(ConstantExpr::getShl(C2, C1), X);
 
     // (X * C2) << C1 --> X * (C2 << C1)
     if (match(Op0, m_Mul(m_Value(X), m_Constant(C2))))
       return BinaryOperator::CreateMul(X, ConstantExpr::getShl(C2, C1));
   }
 
+  // (1 << (C - x)) -> ((1 << C) >> x) if C is bitwidth - 1
+  if (match(Op0, m_One()) &&
+      match(Op1, m_Sub(m_SpecificInt(BitWidth - 1), m_Value(X))))
+    return BinaryOperator::CreateLShr(
+        ConstantInt::get(Ty, APInt::getSignMask(BitWidth)), X);
+
   return nullptr;
 }
 
 Instruction *InstCombiner::visitLShr(BinaryOperator &I) {
   if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1), I.isExact(),
                                   SQ.getWithInstruction(&I)))
     return replaceInstUsesWith(I, V);
 

llvm/trunk/test/Transforms/InstCombine/shl-sub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 define i32 @shl_sub_i32(i32 %x) {
 ; CHECK-LABEL: @shl_sub_i32(
-; CHECK-NEXT:    [[S:%.*]] = sub i32 31, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = shl i32 1, [[S]]
+; CHECK-NEXT:    [[R:%.*]] = lshr i32 -2147483648, [[X:%.*]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %s = sub i32 31, %x
   %r = shl i32 1, %s
   ret i32 %r
 }
 
 define i32 @shl_sub_multiuse_i32(i32 %x) {
 ; CHECK-LABEL: @shl_sub_multiuse_i32(
 ; CHECK-NEXT:    [[S:%.*]] = sub i32 31, [[X:%.*]]
 ; CHECK-NEXT:    call void @use(i32 [[S]])
-; CHECK-NEXT:    [[R:%.*]] = shl i32 1, [[S]]
+; CHECK-NEXT:    [[R:%.*]] = lshr i32 -2147483648, [[X]]
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %s = sub i32 31, %x
   call void @use(i32 %s)
   %r = shl i32 1, %s
   ret i32 %r
 }
 
 define i8 @shl_sub_i8(i8 %x) {
 ; CHECK-LABEL: @shl_sub_i8(
-; CHECK-NEXT:    [[S:%.*]] = sub i8 7, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = shl i8 1, [[S]]
+; CHECK-NEXT:    [[R:%.*]] = lshr i8 -128, [[X:%.*]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %s = sub i8 7, %x
   %r = shl i8 1, %s
   ret i8 %r
 }
 
 define i64 @shl_sub_i64(i64 %x) {
 ; CHECK-LABEL: @shl_sub_i64(
-; CHECK-NEXT:    [[S:%.*]] = sub i64 63, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = shl i64 1, [[S]]
+; CHECK-NEXT:    [[R:%.*]] = lshr i64 -9223372036854775808, [[X:%.*]]
 ; CHECK-NEXT:    ret i64 [[R]]
 ;
   %s = sub i64 63, %x
   %r = shl i64 1, %s
   ret i64 %r
 }
 
 define <2 x i64> @shl_sub_i64_vec(<2 x i64> %x) {
 ; CHECK-LABEL: @shl_sub_i64_vec(
-; CHECK-NEXT:    [[S:%.*]] = sub <2 x i64> <i64 63, i64 63>, [[X:%.*]]
-; CHECK-NEXT:    [[R:%.*]] = shl <2 x i64> <i64 1, i64 1>, [[S]]
+; CHECK-NEXT:    [[R:%.*]] = lshr <2 x i64> <i64 -9223372036854775808, i64 -9223372036854775808>, [[X:%.*]]
 ; CHECK-NEXT:    ret <2 x i64> [[R]]
 ;
   %s = sub <2 x i64> <i64 63, i64 63>, %x
   %r = shl <2 x i64> <i64 1, i64 1>, %s
   ret <2 x i64> %r
 }
 
 ; Negative tests