[InstCombine] Fold (-a >> b) and/or/xor (~a >> b) into (-a and/or/xor ~a) >> b

[kitaisreal]

Summary

Fold (-a >> b) and/or/xor (~a >> b) into (-a and/or/xor ~a) >> b https://github.com/llvm/llvm-project/issues/64304.
This optimization was already performed for unsigned arguments https://godbolt.org/z/xvvnxc4Ys, but for signed integers optimization could not be performed because of ashr (xor %x, -1), %y --> xor (ashr %x, %y), -1 transform that was introduced in https://github.com/llvm/llvm-project/commit/485c4b552b71aff21fc27ce958c2d8ea4cebba99#diff-8c60c0e9a2dee740856faa4e8c8e5545e3236565d003f85fec4650841c976268.
Alive proofs https://alive2.llvm.org/ce/z/HU-MJn, https://alive2.llvm.org/ce/z/pcXVgU, https://alive2.llvm.org/ce/z/RVqr_P.
Depends on D157289.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

1008

Imo the LHS/RHS logic are similiar enough it should be a lambda. Will make the code a lot cleaner.

1022

This codeblock needs some comments.

[nikic]

Can we generalize foldBinOpShiftWithShift() to handle this? Or alternatively, can be fold foldBinOpShiftWithShift() into the special factorization case you're adding here? I'm not willing to have both. We also shouldn't be creating temporary instructions.

[kitaisreal]

Updated implementation.

[kitaisreal]

In D157290#4570531, @nikic wrote:

Can we generalize foldBinOpShiftWithShift() to handle this? Or alternatively, can be fold foldBinOpShiftWithShift() into the special factorization case you're adding here? I'm not willing to have both. We also shouldn't be creating temporary instructions.

Moved implementation to foldBinOpShiftWithShift().

[nikic]

As far as I can tell the sub 0, x is irrelevant for the transform. Can you please remove it from the proofs (and tests)?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

757

There's just one kind of arithmetic shift, so it can't not match.

854

Maybe match(Mask, m_AllOnes()) and leave CMask alone? This will also match splat vectors with undef values, so we'd need a test for that.

856

Might as well CreateNot?

858

Cast shouldn't be needed.

[kitaisreal]

Updated implementation.

[kitaisreal]

In D157290#4582227, @nikic wrote:

As far as I can tell the sub 0, x is irrelevant for the transform. Can you please remove it from the proofs (and tests)?

Yes, sub 0, x is irrelevant for the transform. I need to use some instruction to transform x so that whole expression will not be optimized by other transformations. I updated tests to use mul, it seems from other tests mul and div are usually used for this.

[nikic]

In D157290#4582439, @kitaisreal wrote:

In D157290#4582227, @nikic wrote:

As far as I can tell the sub 0, x is irrelevant for the transform. Can you please remove it from the proofs (and tests)?

Yes, sub 0, x is irrelevant for the transform. I need to use some instruction to transform x so that whole expression will not be optimized by other transformations. I updated tests to use mul, it seems from other tests mul and div are usually used for this.

Can't you just make it a separate argument? Like this: https://alive2.llvm.org/ce/z/ptdCGU

[kitaisreal]

Updated implementation.

[kitaisreal]

In D157290#4582498, @nikic wrote:

In D157290#4582439, @kitaisreal wrote:

In D157290#4582227, @nikic wrote:

As far as I can tell the sub 0, x is irrelevant for the transform. Can you please remove it from the proofs (and tests)?

Yes, sub 0, x is irrelevant for the transform. I need to use some instruction to transform x so that whole expression will not be optimized by other transformations. I updated tests to use mul, it seems from other tests mul and div are usually used for this.

Can't you just make it a separate argument? Like this: https://alive2.llvm.org/ce/z/ptdCGU

Sure, updated implementation, tests and proofs.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

788

Can you add assert ShOpc != Instruction::AShr here. Your code is fine in that regard, but now that the match logic supports AShr but much of the existing logic doesn't think we should have a fail-loudly check incase someone updates in the future.

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

783

Also assert in here.

[nikic]

LGTM apart from @goldstein.w.n's nits.

[kitaisreal]

Added asserts.

[kitaisreal]

Updated tests.

[kitaisreal]

@nikic can you accept this revision again after I changed tests ?

[nikic]

LG

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 //    -> (logic_shift (Binop1 (Binop2 X, inv_logic_shift(C1, C)), Y), C)
 //
 // (Binop1 (Binop2 (logic_shift X, Amt), Mask), (logic_shift Y, Amt))
 //   IFF
 //    1) the logic_shifts match
 //    2) BinOp1 == BinOp2 (if BinOp ==  `add`, then also requires `shl`).
 //
 //    -> (BinOp (logic_shift (BinOp X, Y)), Mask)
+//
+// (Binop1 (Binop2 (arithmetic_shift X, Amt), Mask), (arithmetic_shift Y, Amt))
+//   IFF
+//   1) Binop1 is bitwise logical operator `and`, `or` or `xor`
+//   2) Binop2 is `not`
+//
+//   -> (arithmetic_shift Binop1((not X), Y), Amt)
+
 Instruction *InstCombinerImpl::foldBinOpShiftWithShift(BinaryOperator &I) {
   auto IsValidBinOpc = [](unsigned Opc) {
     switch (Opc) {
     default:
       return false;
     case Instruction::And:
     case Instruction::Or:
     case Instruction::Xor:
     case Instruction::Add:
       // Skip Sub as we only match constant masks which will canonicalize to use
       // add.
       return true;
     }
   };
 
   // Check if we can distribute binop arbitrarily. `add` + `lshr` has extra
   // constraints.
   auto IsCompletelyDistributable = [](unsigned BinOpc1, unsigned BinOpc2,
                                       unsigned ShOpc) {
+    assert(ShOpc != Instruction::AShr);
     return (BinOpc1 != Instruction::Add && BinOpc2 != Instruction::Add) ||
            ShOpc == Instruction::Shl;
   };
 
   auto GetInvShift = [](unsigned ShOpc) {
+    assert(ShOpc != Instruction::AShr);
     return ShOpc == Instruction::LShr ? Instruction::Shl : Instruction::LShr;
   };
 
   auto CanDistributeBinops = [&](unsigned BinOpc1, unsigned BinOpc2,
                                  unsigned ShOpc, Constant *CMask,
                                  Constant *CShift) {
     // If the BinOp1 is `and` we don't need to check the mask.
     if (BinOpc1 == Instruction::And)
       return true;
return ConstantExpr::get(
                ShOpc, ConstantExpr::get(GetInvShift(ShOpc), CMask, CShift),
                CShift) == CMask;
   };
 
   auto MatchBinOp = [&](unsigned ShOpnum) -> Instruction * {
     Constant *CMask, *CShift;
     Value *X, *Y, *ShiftedX, *Mask, *Shift;
     if (!match(I.getOperand(ShOpnum),
-               m_OneUse(m_LogicalShift(m_Value(Y), m_Value(Shift)))))
+               m_OneUse(m_Shift(m_Value(Y), m_Value(Shift)))))
       return nullptr;
     if (!match(I.getOperand(1 - ShOpnum),
                m_BinOp(m_Value(ShiftedX), m_Value(Mask))))
       return nullptr;
 
-    if (!match(ShiftedX,
-               m_OneUse(m_LogicalShift(m_Value(X), m_Specific(Shift)))))
+    if (!match(ShiftedX, m_OneUse(m_Shift(m_Value(X), m_Specific(Shift)))))
       return nullptr;
 
     // Make sure we are matching instruction shifts and not ConstantExpr
     auto *IY = dyn_cast<Instruction>(I.getOperand(ShOpnum));
     auto *IX = dyn_cast<Instruction>(ShiftedX);
     if (!IY || !IX)
       return nullptr;
 
     // LHS and RHS need same shift opcode
     unsigned ShOpc = IY->getOpcode();
     if (ShOpc != IX->getOpcode())
       return nullptr;
 
     // Make sure binop is real instruction and not ConstantExpr
     auto *BO2 = dyn_cast<Instruction>(I.getOperand(1 - ShOpnum));
     if (!BO2)
       return nullptr;
 
     unsigned BinOpc = BO2->getOpcode();
     // Make sure we have valid binops.
     if (!IsValidBinOpc(I.getOpcode()) || !IsValidBinOpc(BinOpc))
       return nullptr;
 
+    if (ShOpc == Instruction::AShr) {
+      if (Instruction::isBitwiseLogicOp(I.getOpcode()) &&
+          BinOpc == Instruction::Xor && match(Mask, m_AllOnes())) {
+        Value *NotX = Builder.CreateNot(X);
+        Value *NewBinOp = Builder.CreateBinOp(I.getOpcode(), Y, NotX);
+        return BinaryOperator::Create(
+            static_cast<Instruction::BinaryOps>(ShOpc), NewBinOp, Shift);
+      }
+
+      return nullptr;
+    }
+
     // If BinOp1 == BinOp2 and it's bitwise or shl with add, then just
     // distribute to drop the shift irrelevant of constants.
     if (BinOpc == I.getOpcode() &&
         IsCompletelyDistributable(I.getOpcode(), BinOpc, ShOpc)) {
       Value *NewBinOp2 = Builder.CreateBinOp(I.getOpcode(), X, Y);
       Value *NewBinOp1 = Builder.CreateBinOp(
           static_cast<Instruction::BinaryOps>(ShOpc), NewBinOp2, Shift);
       return BinaryOperator::Create(I.getOpcode(), NewBinOp1, Mask);

 /// distributes over either by factorizing out common terms
 /// (eg "(A*B)+(A*C)" -> "A*(B+C)") or expanding out if this results in
 /// simplifications (eg: "A & (B | C) -> (A&B) | (A&C)" if this is a win).
 /// Returns the simplified value, or null if it didn't simplify.
 Value *InstCombinerImpl::foldUsingDistributiveLaws(BinaryOperator &I) {
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
   BinaryOperator *Op0 = dyn_cast<BinaryOperator>(LHS);
   BinaryOperator *Op1 = dyn_cast<BinaryOperator>(RHS);
   Instruction::BinaryOps TopLevelOpcode = I.getOpcode();
 
   // Factorization.
   if (Value *R = tryFactorizationFolds(I))
     return R;
 
   // Expansion.
   if (Op0 && rightDistributesOverLeft(Op0->getOpcode(), TopLevelOpcode)) {
     // The instruction has the form "(A op' B) op C".  See if expanding it out
     // to "(A op C) op' (B op C)" results in simplifications.
     Value *A = Op0->getOperand(0), *B = Op0->getOperand(1), *C = RHS;
     Instruction::BinaryOps InnerOpcode = Op0->getOpcode(); // op'
 
     // Disable the use of undef because it's not safe to distribute undef.
     auto SQDistributive = SQ.getWithInstruction(&I).getWithoutUndef();
     Value *L = simplifyBinOp(TopLevelOpcode, A, C, SQDistributive);
     Value *R = simplifyBinOp(TopLevelOpcode, B, C, SQDistributive);
 
     // Do "A op C" and "B op C" both simplify?
     if (L && R) {
       // They do! Return "L op' R".
       ++NumExpand;
       C = Builder.CreateBinOp(InnerOpcode, L, R);

llvm/test/Transforms/InstCombine/binop-and-shifts.ll

;
   %bw1 = and i8 %shift1, %bw2
   ret i8 %bw1
 }
 
 ; Fold (-x >> y) & ((x >> y) ^ -1) -> (-x & ~x) >> y
 
 define i8 @and_ashr_not(i8 %x, i8 %y, i8 %shamt) {
 ; CHECK-LABEL: @and_ashr_not(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor i8 [[Y_SHIFT]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = ashr i8 [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret i8 [[AND]]
 ;
   %x.shift = ashr i8 %x, %shamt
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -1
   %and = and i8 %x.shift, %y.shift.not
   ret i8 %and
 }
 
 define i8 @and_ashr_not_commuted(i8 %x, i8 %y, i8 %shamt) {
 ; CHECK-LABEL: @and_ashr_not_commuted(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor i8 [[Y_SHIFT]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i8 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = ashr i8 [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret i8 [[AND]]
 ;
   %x.shift = ashr i8 %x, %shamt
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -1
   %and = and i8 %y.shift.not, %x.shift
   ret i8 %and
 }
;
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -2
   %and = and i8 %x.shift, %y.shift.not
   ret i8 %and
 }
 
 define <4 x i8> @and_ashr_not_vec(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @and_ashr_not_vec(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr <4 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr <4 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor <4 x i8> [[Y_SHIFT]], <i8 -1, i8 -1, i8 -1, i8 -1>
-; CHECK-NEXT:    [[AND:%.*]] = and <4 x i8> [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i8> [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = ashr <4 x i8> [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[AND]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 -1, i8 -1, i8 -1>
   %and = and <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %and
 }
 
 define <4 x i8> @and_ashr_not_vec_commuted(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @and_ashr_not_vec_commuted(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr <4 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr <4 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor <4 x i8> [[Y_SHIFT]], <i8 -1, i8 -1, i8 -1, i8 -1>
-; CHECK-NEXT:    [[AND:%.*]] = and <4 x i8> [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i8> [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = ashr <4 x i8> [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[AND]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 -1, i8 -1, i8 -1>
   %and = and <4 x i8> %y.shift.not, %x.shift
   ret <4 x i8> %and
 }
 
 define <4 x i8> @and_ashr_not_vec_undef_1(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @and_ashr_not_vec_undef_1(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr <4 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr <4 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor <4 x i8> [[Y_SHIFT]], <i8 -1, i8 undef, i8 undef, i8 undef>
-; CHECK-NEXT:    [[AND:%.*]] = and <4 x i8> [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <4 x i8> [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[AND:%.*]] = ashr <4 x i8> [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[AND]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 undef, i8 undef, i8 undef>
   %and = and <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %and
 }
 
 define <4 x i8> @and_ashr_not_vec_undef_2(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @and_ashr_not_vec_undef_2(
 ; CHECK-NEXT:    ret <4 x i8> zeroinitializer
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 undef, i8 undef, i8 undef, i8 undef>
   %and = and <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %and
 }
 
 ; Fold (-x >> y) | ((x >> y) ^ -1) -> (-x | ~x) >> y
 
 define i8 @or_ashr_not(i8 %x, i8 %y, i8 %shamt) {
 ; CHECK-LABEL: @or_ashr_not(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor i8 [[Y_SHIFT]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i8 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = ashr i8 [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret i8 [[OR]]
 ;
   %x.shift = ashr i8 %x, %shamt
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -1
   %or = or i8 %x.shift, %y.shift.not
   ret i8 %or
 }
 
 define i8 @or_ashr_not_commuted(i8 %x, i8 %y, i8 %shamt) {
 ; CHECK-LABEL: @or_ashr_not_commuted(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr i8 [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr i8 [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor i8 [[Y_SHIFT]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[Y:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i8 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = ashr i8 [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret i8 [[OR]]
 ;
   %x.shift = ashr i8 %x, %shamt
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -1
   %or = or i8 %y.shift.not, %x.shift
   ret i8 %or
 }
;
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -2
   %or = or i8 %x.shift, %y.shift.not
   ret i8 %or
 }
 
 define <4 x i8> @or_ashr_not_vec(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @or_ashr_not_vec(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr <4 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr <4 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor <4 x i8> [[Y_SHIFT]], <i8 -1, i8 -1, i8 -1, i8 -1>
-; CHECK-NEXT:    [[OR:%.*]] = or <4 x i8> [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = or <4 x i8> [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = ashr <4 x i8> [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[OR]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 -1, i8 -1, i8 -1>
   %or = or <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %or
 }
 
 define <4 x i8> @or_ashr_not_vec_commuted(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @or_ashr_not_vec_commuted(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr <4 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr <4 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor <4 x i8> [[Y_SHIFT]], <i8 -1, i8 -1, i8 -1, i8 -1>
-; CHECK-NEXT:    [[OR:%.*]] = or <4 x i8> [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = or <4 x i8> [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = ashr <4 x i8> [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[OR]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 -1, i8 -1, i8 -1>
   %or = or <4 x i8> %y.shift.not, %x.shift
   ret <4 x i8> %or
 }
 
 define <4 x i8> @or_ashr_not_vec_undef_1(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @or_ashr_not_vec_undef_1(
-; CHECK-NEXT:    [[X_SHIFT:%.*]] = ashr <4 x i8> [[X:%.*]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[Y_SHIFT:%.*]] = ashr <4 x i8> [[Y:%.*]], [[SHAMT]]
-; CHECK-NEXT:    [[Y_SHIFT_NOT:%.*]] = xor <4 x i8> [[Y_SHIFT]], <i8 -1, i8 undef, i8 undef, i8 undef>
-; CHECK-NEXT:    [[OR:%.*]] = or <4 x i8> [[X_SHIFT]], [[Y_SHIFT_NOT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP2:%.*]] = or <4 x i8> [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[OR:%.*]] = ashr <4 x i8> [[TMP2]], [[SHAMT:%.*]]
 ; CHECK-NEXT:    ret <4 x i8> [[OR]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 undef, i8 undef, i8 undef>
   %or = or <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %or
 }
 
 define <4 x i8> @or_ashr_not_vec_undef_2(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @or_ashr_not_vec_undef_2(
 ; CHECK-NEXT:    ret <4 x i8> <i8 -1, i8 -1, i8 -1, i8 -1>
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 undef, i8 undef, i8 undef, i8 undef>
   %or = or <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %or
 }
 
 ; Fold (-x >> y) ^ ((x >> y) ^ -1) -> (-x ^ ~x) >> y
 
 define i8 @xor_ashr_not(i8 %x, i8 %y, i8 %shamt) {
 ; CHECK-LABEL: @xor_ashr_not(
-; CHECK-NEXT:    [[Y_SHIFT1:%.*]] = xor i8 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i8 [[Y_SHIFT1]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = ashr i8 [[TMP1]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[DOTNOT]], -1
 ; CHECK-NEXT:    ret i8 [[XOR]]
 ;
   %x.shift = ashr i8 %x, %shamt
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -1
   %xor = xor i8 %x.shift, %y.shift.not
   ret i8 %xor
 }
 
 define i8 @xor_ashr_not_commuted(i8 %x, i8 %y, i8 %shamt) {
 ; CHECK-LABEL: @xor_ashr_not_commuted(
-; CHECK-NEXT:    [[Y_SHIFT1:%.*]] = xor i8 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr i8 [[Y_SHIFT1]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[TMP1]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i8 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = ashr i8 [[TMP1]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[DOTNOT]], -1
 ; CHECK-NEXT:    ret i8 [[XOR]]
 ;
   %x.shift = ashr i8 %x, %shamt
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -1
   %xor = xor i8 %y.shift.not, %x.shift
   ret i8 %xor
 }
;
   %y.shift = ashr i8 %y, %shamt
   %y.shift.not = xor i8 %y.shift, -2
   %xor = xor i8 %x.shift, %y.shift.not
   ret i8 %xor
 }
 
 define <4 x i8> @xor_ashr_not_vec(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @xor_ashr_not_vec(
-; CHECK-NEXT:    [[Y_SHIFT1:%.*]] = xor <4 x i8> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <4 x i8> [[Y_SHIFT1]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <4 x i8> [[TMP1]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = ashr <4 x i8> [[TMP1]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor <4 x i8> [[DOTNOT]], <i8 -1, i8 -1, i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <4 x i8> [[XOR]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 -1, i8 -1, i8 -1>
   %xor = xor <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %xor
 }
 
 define <4 x i8> @xor_ashr_not_vec_commuted(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @xor_ashr_not_vec_commuted(
-; CHECK-NEXT:    [[Y_SHIFT1:%.*]] = xor <4 x i8> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <4 x i8> [[Y_SHIFT1]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <4 x i8> [[TMP1]], <i8 -1, i8 -1, i8 -1, i8 -1>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = ashr <4 x i8> [[TMP1]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor <4 x i8> [[DOTNOT]], <i8 -1, i8 -1, i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <4 x i8> [[XOR]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 -1, i8 -1, i8 -1>
   %xor = xor <4 x i8> %y.shift.not, %x.shift
   ret <4 x i8> %xor
 }
 
 define <4 x i8> @xor_ashr_not_vec_undef_1(<4 x i8> %x, <4 x i8> %y, <4 x i8> %shamt) {
 ; CHECK-LABEL: @xor_ashr_not_vec_undef_1(
-; CHECK-NEXT:    [[Y_SHIFT1:%.*]] = xor <4 x i8> [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[TMP1:%.*]] = ashr <4 x i8> [[Y_SHIFT1]], [[SHAMT:%.*]]
-; CHECK-NEXT:    [[XOR:%.*]] = xor <4 x i8> [[TMP1]], <i8 -1, i8 undef, i8 undef, i8 undef>
+; CHECK-NEXT:    [[TMP1:%.*]] = xor <4 x i8> [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[DOTNOT:%.*]] = ashr <4 x i8> [[TMP1]], [[SHAMT:%.*]]
+; CHECK-NEXT:    [[XOR:%.*]] = xor <4 x i8> [[DOTNOT]], <i8 -1, i8 -1, i8 -1, i8 -1>
 ; CHECK-NEXT:    ret <4 x i8> [[XOR]]
 ;
   %x.shift = ashr <4 x i8> %x, %shamt
   %y.shift = ashr <4 x i8> %y, %shamt
   %y.shift.not = xor <4 x i8> %y.shift, <i8 -1, i8 undef, i8 undef, i8 undef>
   %xor = xor <4 x i8> %x.shift, %y.shift.not
   ret <4 x i8> %xor
 }