[InstCombine] canonicalize 'not' ops before logical shifts

[spatel]

Summary

This reverses the existing transform that would uniformly canonicalize any 'xor' after any shift. In the case of logical shifts, that turns a 'not' into an arbitrary 'xor' with constant, and that's probably not as good for analysis, SCEV, or codegen.

The SCEV motivating case is discussed in:
http://bugs.llvm.org/PR47136

There's an analysis motivating case at:
http://bugs.llvm.org/PR38781

I did draft a patch that would do the same for 'ashr' but that's questionable because it's just swapping the position of a 'not' and uncovers at least 2 missing folds that we would probably need to deal with as preliminary steps.

Alive proofs:
https://rise4fun.com/Alive/BBV

Name: shift right of 'not'
Pre: C2 == (-1 u>> C1)
%a = lshr i8 %x, C1
%r = xor i8 %a, C2
  =>
%n = xor i8 %x, -1
%r = lshr i8 %n, C1

Name: shift left of 'not'
Pre: C2 == (-1 << C1)
%a = shl i8 %x, C1
%r = xor i8 %a, C2
  =>
%n = xor i8 %x, -1
%r = shl i8 %n, C1

Name: ashr of 'not'
%a = ashr i8 %x, 1
%r = xor i8 %a, -1
  =>
%n = xor i8 %x, -1
%r = ashr i8 %n, 1

[xbolva00]

Some SCEV/pipeline tests?

Maybe from https://reviews.llvm.org/D85969#change-8DkHYel6Y1JK ?

[bjope]

I've verified that this resolves https://bugs.llvm.org/show_bug.cgi?id=47136 in the sense that our downstream benchmark result is back to the original result for the tests that had a regression. And without any new regressions. So that is perfect!

[bjope]

In D86243#2227038, @xbolva00 wrote:

Some SCEV/pipeline tests?

Maybe from https://reviews.llvm.org/D85969#change-8DkHYel6Y1JK ?

I figure we want to move forward with D85969 and land that as well. Right?
I mean, can't ScalarEvolution analysis be used by some pass before instcombine in the pass pipeline. Then I assume it is nice if SCEV treats the two different forms of the equivalent expressions the same way.

[spatel]

In D86243#2227038, @xbolva00 wrote:

Some SCEV/pipeline tests?

Maybe from https://reviews.llvm.org/D85969#change-8DkHYel6Y1JK ?

I think if we are going to add tests to show that instcombine and SCEV are cooperating as expected, that would go in PhaseOrdering. But we need a larger example than what we have in D85969 to show that the IR for some loop is better with this change?

In D86243#2228399, @bjope wrote:

In D86243#2227038, @xbolva00 wrote:

Some SCEV/pipeline tests?

Maybe from https://reviews.llvm.org/D85969#change-8DkHYel6Y1JK ?

I figure we want to move forward with D85969 and land that as well. Right?
I mean, can't ScalarEvolution analysis be used by some pass before instcombine in the pass pipeline. Then I assume it is nice if SCEV treats the two different forms of the equivalent expressions the same way.

I don't know the answer. I agree that making SCEV handle more patterns makes it less brittle, but how much redundancy is needed?

[lebedev.ri]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3279

// (X l>> C) ^ RHSC --> ~X l>> C

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op1, m_APInt(RHSC))) {
       // (X + C) ^ signmaskC --> X + (C + signmaskC)
       if (RHSC->isSignMask() && match(Op0, m_Add(m_Value(X), m_APInt(C))))
         return BinaryOperator::CreateAdd(X, ConstantInt::get(Ty, *C + *RHSC));
 
       // (X | C) ^ RHSC --> X ^ (C ^ RHSC) iff X & C == 0
       if (match(Op0, m_Or(m_Value(X), m_APInt(C))) &&
           MaskedValueIsZero(X, *C, 0, &I))
         return BinaryOperator::CreateXor(X, ConstantInt::get(Ty, *C ^ *RHSC));
+
+      // If RHSC is inverting the remaining bits of shifted X,
+      // canonicalize to a 'not' before the shift to help SCEV and codegen:
+      // (X << C) ^ RHSC --> ~X << C
+      if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(C)))) &&
+          *RHSC == APInt::getAllOnesValue(Ty->getScalarSizeInBits()).shl(*C)) {
+        Value *NotX = Builder.CreateNot(X);
+        return BinaryOperator::CreateShl(NotX, ConstantInt::get(Ty, *C));
+      }
+      // (X >>u C) ^ RHSC --> ~X >>u C
+      if (match(Op0, m_OneUse(m_LShr(m_Value(X), m_APInt(C)))) &&
+          *RHSC == APInt::getAllOnesValue(Ty->getScalarSizeInBits()).lshr(*C)) {
+        Value *NotX = Builder.CreateNot(X);
+        return BinaryOperator::CreateLShr(NotX, ConstantInt::get(Ty, *C));
+      }
+      // TODO: We could handle 'ashr' here as well. That would be matching
+      //       a 'not' op and moving it before the shift. Doing that requires
+      //       preventing the inverse fold in canShiftBinOpWithConstantRHS().
     }
   }
 
   // FIXME: This should not be limited to scalar (pull into APInt match above).
   if (ConstantInt *RHSC = dyn_cast<ConstantInt>(Op1)) {
     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
         if (Op0I->getOpcode() == Instruction::LShr) {

llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

 static bool canShiftBinOpWithConstantRHS(BinaryOperator &Shift,
                                          BinaryOperator *BO) {
   switch (BO->getOpcode()) {
   default:
     return false; // Do not perform transform!
   case Instruction::Add:
     return Shift.getOpcode() == Instruction::Shl;
   case Instruction::Or:
-  case Instruction::Xor:
   case Instruction::And:
     return true;
+  case Instruction::Xor:
+    // Do not change a 'not' of logical shift because that would create a normal
+    // 'xor'. The 'not' is likely better for analysis, SCEV, and codegen.
+    return !(Shift.isLogicalShift() && match(BO, m_Not(m_Value())));
   }
 }
 
 Instruction *InstCombinerImpl::FoldShiftByConstant(Value *Op0, Constant *Op1,
                                                    BinaryOperator &I) {
   bool isLeftShift = I.getOpcode() == Instruction::Shl;
 
   const APInt *Op1C;

llvm/test/Transforms/InstCombine/2010-11-01-lshr-mask.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -instcombine-infinite-loop-threshold=2 -S < %s | FileCheck %s
 
 ; <rdar://problem/8606771>
 define i32 @main(i32 %argc) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:    [[T3151:%.*]] = trunc i32 [[ARGC:%.*]] to i8
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[T3151]], 5
-; CHECK-NEXT:    [[T4126:%.*]] = and i8 [[TMP1]], 64
-; CHECK-NEXT:    [[T4127:%.*]] = xor i8 [[T4126]], 64
+; CHECK-NEXT:    [[T3163:%.*]] = xor i8 [[T3151]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[T3163]], 5
+; CHECK-NEXT:    [[T4127:%.*]] = and i8 [[TMP1]], 64
 ; CHECK-NEXT:    [[T4086:%.*]] = zext i8 [[T4127]] to i32
 ; CHECK-NEXT:    ret i32 [[T4086]]
 ;
   %t3151 = trunc i32 %argc to i8
   %t3161 = or i8 %t3151, -17
   %t3162 = and i8 %t3151, 122
   %t3163 = xor i8 %t3162, -17
   %t4114 = shl i8 %t3163, 6

llvm/test/Transforms/InstCombine/and-xor-merge.ll

;
   %t3 = and i32 %y, %x
   %t6 = or i32 %y, %x
   %t7 = xor i32 %t3, %t6
   ret i32 %t7
 }
 
 define i32 @PR38761(i32 %a, i32 %b) {
 ; CHECK-LABEL: @PR38761(
-; CHECK-NEXT:    [[A_LOBIT:%.*]] = lshr i32 [[A:%.*]], 31
-; CHECK-NEXT:    [[A_LOBIT_NOT:%.*]] = xor i32 [[A_LOBIT]], 1
-; CHECK-NEXT:    [[B_LOBIT:%.*]] = lshr i32 [[B:%.*]], 31
-; CHECK-NEXT:    [[B_LOBIT_NOT:%.*]] = xor i32 [[B_LOBIT]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[A_LOBIT_NOT]], [[B_LOBIT_NOT]]
+; CHECK-NEXT:    [[B_LOBIT_NOT1_DEMORGAN:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[B_LOBIT_NOT1:%.*]] = xor i32 [[B_LOBIT_NOT1_DEMORGAN]], -1
+; CHECK-NEXT:    [[AND:%.*]] = lshr i32 [[B_LOBIT_NOT1]], 31
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %a.lobit = lshr i32 %a, 31
   %a.lobit.not = xor i32 %a.lobit, 1
   %b.lobit = lshr i32 %b, 31
   %b.lobit.not = xor i32 %b.lobit, 1
   %and = and i32 %b.lobit.not, %a.lobit.not
   ret i32 %and
 }

llvm/test/Transforms/InstCombine/compare-signs.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; PR5438
 
 define i32 @test1(i32 %a, i32 %b) nounwind readnone {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[DOTLOBIT:%.*]] = lshr i32 [[TMP1]], 31
-; CHECK-NEXT:    [[DOTLOBIT_NOT:%.*]] = xor i32 [[DOTLOBIT]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    [[DOTLOBIT_NOT:%.*]] = lshr i32 [[TMP2]], 31
 ; CHECK-NEXT:    ret i32 [[DOTLOBIT_NOT]]
 ;
   %t0 = icmp sgt i32 %a, -1
   %t1 = icmp slt i32 %b, 0
   %t2 = xor i1 %t1, %t0
   %t3 = zext i1 %t2 to i32
   ret i32 %t3
 }
;
   %t2 = icmp eq i32 %t0, %t1
   %t3 = zext i1 %t2 to i32
   ret i32 %t3
 }
 
 define i32 @test3(i32 %a, i32 %b) nounwind readnone {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:    [[T2_UNSHIFTED:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[T2_UNSHIFTED_LOBIT:%.*]] = lshr i32 [[T2_UNSHIFTED]], 31
-; CHECK-NEXT:    [[T2_UNSHIFTED_LOBIT_NOT:%.*]] = xor i32 [[T2_UNSHIFTED_LOBIT]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[T2_UNSHIFTED]], -1
+; CHECK-NEXT:    [[T2_UNSHIFTED_LOBIT_NOT:%.*]] = lshr i32 [[TMP1]], 31
 ; CHECK-NEXT:    ret i32 [[T2_UNSHIFTED_LOBIT_NOT]]
 ;
   %t0 = lshr i32 %a, 31
   %t1 = lshr i32 %b, 31
   %t2 = icmp eq i32 %t0, %t1
   %t3 = zext i1 %t2 to i32
   ret i32 %t3
 }
;
   ret <2 x i32> %t3
 }
 
 ; Variation on @test3: checking the 2nd bit in a situation where the 5th bit
 ; is one, not zero.
 define i32 @test3i(i32 %a, i32 %b) nounwind readnone {
 ; CHECK-LABEL: @test3i(
 ; CHECK-NEXT:    [[T01:%.*]] = xor i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[T01]], 31
-; CHECK-NEXT:    [[T4:%.*]] = xor i32 [[TMP1]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[T01]], -1
+; CHECK-NEXT:    [[T4:%.*]] = lshr i32 [[TMP1]], 31
 ; CHECK-NEXT:    ret i32 [[T4]]
 ;
   %t0 = lshr i32 %a, 29
   %t1 = lshr i32 %b, 29
   %t2 = or i32 %t0, 35
   %t3 = or i32 %t1, 35
   %t4 = icmp eq i32 %t2, %t3
   %t5 = zext i1 %t4 to i32

llvm/test/Transforms/InstCombine/icmp.ll

 ;
   %a = icmp slt <2 x i32> %X, zeroinitializer
   %b = zext <2 x i1> %a to <2 x i32>
   ret <2 x i32> %b
 }
 
 define i32 @test2(i32 %X) {
 ; CHECK-LABEL: @test2(
-; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr i32 [[X:%.*]], 31
-; CHECK-NEXT:    [[X_LOBIT_NOT:%.*]] = xor i32 [[X_LOBIT]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[X_LOBIT_NOT:%.*]] = lshr i32 [[TMP1]], 31
 ; CHECK-NEXT:    ret i32 [[X_LOBIT_NOT]]
 ;
   %a = icmp ult i32 %X, -2147483648
   %b = zext i1 %a to i32
   ret i32 %b
 }
 
 define <2 x i32> @test2vec(<2 x i32> %X) {
 ; CHECK-LABEL: @test2vec(
-; CHECK-NEXT:    [[X_LOBIT:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 31, i32 31>
-; CHECK-NEXT:    [[X_LOBIT_NOT:%.*]] = xor <2 x i32> [[X_LOBIT]], <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i32> [[X:%.*]], <i32 -1, i32 -1>
+; CHECK-NEXT:    [[X_LOBIT_NOT:%.*]] = lshr <2 x i32> [[TMP1]], <i32 31, i32 31>
 ; CHECK-NEXT:    ret <2 x i32> [[X_LOBIT_NOT]]
 ;
   %a = icmp ult <2 x i32> %X, <i32 -2147483648, i32 -2147483648>
   %b = zext <2 x i1> %a to <2 x i32>
   ret <2 x i32> %b
 }
 
 define i32 @test3(i32 %X) {

llvm/test/Transforms/InstCombine/xor.ll

;
   %sub = xor i32 %x, 1073741823
   %add = add i32 %sub, %y
   %mul = shl i32 %add, 2
   ret i32 %mul
 }
 
 define i8 @not_shl(i8 %x) {
 ; CHECK-LABEL: @not_shl(
-; CHECK-NEXT:    [[A:%.*]] = shl i8 [[X:%.*]], 7
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], -128
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[R:%.*]] = shl i8 [[TMP1]], 7
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = shl i8 %x, 7
   %r = xor i8 %a, 128
   ret i8 %r
 }
 
 define <2 x i8> @not_shl_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @not_shl_vec(
-; CHECK-NEXT:    [[A:%.*]] = shl <2 x i8> [[X:%.*]], <i8 5, i8 5>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], <i8 -32, i8 -32>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[R:%.*]] = shl <2 x i8> [[TMP1]], <i8 5, i8 5>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %a = shl <2 x i8> %x, <i8 5, i8 5>
   %r = xor <2 x i8> %a, <i8 224, i8 224>
   ret <2 x i8> %r
 }
 
+; negative test
+
 define i8 @not_shl_extra_use(i8 %x) {
 ; CHECK-LABEL: @not_shl_extra_use(
 ; CHECK-NEXT:    [[A:%.*]] = shl i8 [[X:%.*]], 7
 ; CHECK-NEXT:    call void @use(i8 [[A]])
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], -128
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = shl i8 %x, 7
   call void @use(i8 %a)
   %r = xor i8 %a, 128
   ret i8 %r
 }
 
+; negative test
+
 define i8 @not_shl_wrong_const(i8 %x) {
 ; CHECK-LABEL: @not_shl_wrong_const(
 ; CHECK-NEXT:    [[A:%.*]] = shl i8 [[X:%.*]], 6
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], -128
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = shl i8 %x, 6
   %r = xor i8 %a, 128
   ret i8 %r
 }
 
 define i8 @not_lshr(i8 %x) {
 ; CHECK-LABEL: @not_lshr(
-; CHECK-NEXT:    [[A:%.*]] = lshr i8 [[X:%.*]], 5
-; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], 7
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[R:%.*]] = lshr i8 [[TMP1]], 5
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = lshr i8 %x, 5
   %r = xor i8 %a, 7
   ret i8 %r
 }
 
 define <2 x i8> @not_lshr_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @not_lshr_vec(
-; CHECK-NEXT:    [[A:%.*]] = lshr <2 x i8> [[X:%.*]], <i8 7, i8 7>
-; CHECK-NEXT:    [[R:%.*]] = xor <2 x i8> [[A]], <i8 1, i8 1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <2 x i8> [[X:%.*]], <i8 -1, i8 -1>
+; CHECK-NEXT:    [[R:%.*]] = lshr <2 x i8> [[TMP1]], <i8 7, i8 7>
 ; CHECK-NEXT:    ret <2 x i8> [[R]]
 ;
   %a = lshr <2 x i8> %x, <i8 7, i8 7>
   %r = xor <2 x i8> %a, <i8 1, i8 1>
   ret <2 x i8> %r
 }
 
+; negative test
+
 define i8 @not_lshr_extra_use(i8 %x) {
 ; CHECK-LABEL: @not_lshr_extra_use(
 ; CHECK-NEXT:    [[A:%.*]] = lshr i8 [[X:%.*]], 5
 ; CHECK-NEXT:    call void @use(i8 [[A]])
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], 7
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = lshr i8 %x, 5
   call void @use(i8 %a)
   %r = xor i8 %a, 7
   ret i8 %r
 }
 
+; negative test
+
 define i8 @not_lshr_wrong_const(i8 %x) {
 ; CHECK-LABEL: @not_lshr_wrong_const(
 ; CHECK-NEXT:    [[A:%.*]] = lshr i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], 3
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = lshr i8 %x, 5
   %r = xor i8 %a, 3
   ret i8 %r
 }
 
 define i8 @ashr_not(i8 %x) {
 ; CHECK-LABEL: @ashr_not(
 ; CHECK-NEXT:    [[N:%.*]] = ashr i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[N]], -1
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %n = xor i8 %x, -1
   %r = ashr i8 %n, 5
   ret i8 %r
 }
 
+; Unlike the logicial shifts, 'not' is canonicalized after ashr.
+
 define i8 @not_ashr(i8 %x) {
 ; CHECK-LABEL: @not_ashr(
 ; CHECK-NEXT:    [[A:%.*]] = ashr i8 [[X:%.*]], 5
 ; CHECK-NEXT:    [[R:%.*]] = xor i8 [[A]], -1
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %a = ashr i8 %x, 5
   %r = xor i8 %a, -1