[InstCombine] Shift amount reassociation in bittest (PR42399)

[lebedev.ri]

Summary

Given pattern:
icmp eq/ne (and ((x shift Q), (y oppositeshift K))), 0
we should move shifts to the same hand of 'and', i.e. rewrite as
icmp eq/ne (and (x shift (Q+K)), y), 0 iff (Q+K) u< bitwidth(x)

It might be tempting to not restrict this to situations where we know
we'd fold two shifts together, but i'm not sure what rules should there be
to avoid endless combine loops.

We pick the same shift that was originally used to shift the variable we picked to shift:
https://rise4fun.com/Alive/6x1v

Should fix PR42399.

[lebedev.ri]

To answer the obvious question, no, i don't believe we can preserve nuw/nsw/exact flags here.

[spatel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3267–3277 ↗

(On Diff #206709)

This would be easier to read for me if we did the simple icmp checks first:

if (!I.isEquality() || !match(I.getOperand(1), m_Zero()))
  return nullptr;

And then do a mega-match on only I.getOperand(0).

...although that match raises a question if the one-use checks are balanced:
Do we prefer to shift left or right?
https://rise4fun.com/Alive/

%t0 = lshr i32 %x, 2
%t1 = and i32 %t0, %y
%t3 = icmp ne i32 %t1, 0
  =>
%v0 = shl i32 %y, 2
%v1 = and i32 %v0, %x
%t3 = icmp ne i32 %v1, 0

[spatel]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3267–3277 ↗

(On Diff #206709)

Incomplete Alive link in previous comment:
https://rise4fun.com/Alive/9Kp

[lebedev.ri]

Thanks for taking a look, will post updated patch in a bit.

lib/Transforms/InstCombine/InstCombineCompares.cpp

3267–3277 ↗

(On Diff #206709)

...although that match raises a question if the one-use checks are balanced:

I think they are currently.
We will produce 3 instructions: icmp + and + shift.
Therefore we need to get rid of 2 instructions (since the root icmp is always good to go).
Given the nature of the pattern the icmp is comparing and with 0, so and must go.
And thus we only need to get rid of one more instruction.
We know that both hands of an and are shifts.
Since the pattern is bi-directional, we don't really care which one of these two shifts
will be left, only one of those 2 shifts *has* to be one-use.
And that's what is currently enforced via m_OneUse().

Do we prefer to shift left or right?

I'm not sure we can answer that here.
If we can do this fold as per one-use checks - we should.
Do you have anything specific in mind here?
I'd say this should be a separate fold.

[lebedev.ri]

Tidy code up a bit.

[spatel]

LGTM - but see inline comment. It might simplify the code here if we implement the other fold first.

lib/Transforms/InstCombine/InstCombineCompares.cpp

3267–3277 ↗

(On Diff #206709)

Yes, I agree that choosing the shift op is a separate fold. My guess is that 'lshr' gives us better analysis because it clears the sign bit, but that's just a hunch - would have to try it and see what breaks. :)

If we make that decision first, then we could adjust this patch to go directly to the preferred form. As it stands now, we're arbitrarily choosing the shift opcode based on operand ordering (when both sides have one use).

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3267–3277 ↗

(On Diff #206709)

I agree. I *think* lshr will indeed be the correct choice.
At least that would be my choice based on the pattern in question i'm seeing in my code.

[lebedev.ri]

Thank you for the review!

[lebedev.ri]

NFC, test coverage.

[lebedev.ri]

Prefer to create lshr if possible.

[lebedev.ri]

Filed https://bugs.llvm.org/show_bug.cgi?id=42466 to track the shift direction question.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineCompares.cpp

3267–3277 ↗

(On Diff #206709)

Apparently only 2 tests break:

LLVM :: Transforms/InstCombine/shl-and-negC-icmpeq-zero.ll
LLVM :: Transforms/InstCombine/shl-and-signbit-icmpeq-zero.ll

D62818 is related, but failures there are not limited to sign-bit constants.

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

foldICmpWithTruncSignExtendedVal(ICmpInst &I,
   // T0 = add %x, AddCst
   Value *T0 = Builder.CreateAdd(X, ConstantInt::get(XType, AddCst));
   // T1 = T0 DstPred ICmpCst
   Value *T1 = Builder.CreateICmp(DstPred, T0, ConstantInt::get(XType, ICmpCst));
 
   return T1;
 }
 
+// Given pattern:
+//   icmp eq/ne (and ((x shift Q), (y oppositeshift K))), 0
+// we should move shifts to the same hand of 'and', i.e. rewrite as
+//   icmp eq/ne (and (x shift (Q+K)), y), 0  iff (Q+K) u< bitwidth(x)
+// We are only interested in opposite logical shifts here.
+// If we can, we want to end up creating 'lshr' shift.
+static Value *
+foldShiftIntoShiftInAnotherHandOfAndInICmp(ICmpInst &I, const SimplifyQuery SQ,
+                                           InstCombiner::BuilderTy &Builder) {
+  if (!I.isEquality() || !match(I.getOperand(1), m_Zero()) ||
+      !I.getOperand(0)->hasOneUse())
+    return nullptr;
+
+  auto m_AnyLogicalShift = m_LogicalShift(m_Value(), m_Value());
+  auto m_AnyLShr = m_LShr(m_Value(), m_Value());
+
+  // Look for an 'and' of two (opposite) logical shifts.
+  // Pick the single-use shift as XShift.
+  Value *XShift, *YShift;
+  if (!match(I.getOperand(0),
+             m_c_And(m_OneUse(m_CombineAnd(m_AnyLogicalShift, m_Value(XShift))),
+                     m_CombineAnd(m_AnyLogicalShift, m_Value(YShift)))))
+    return nullptr;
+
+  // If YShift is a single-use 'lshr', swap the shifts around.
+  if (match(YShift, m_OneUse(m_AnyLShr)))
+    std::swap(XShift, YShift);
+
+  // The shifts must be in opposite directions.
+  Instruction::BinaryOps XShiftOpcode =
+      cast<BinaryOperator>(XShift)->getOpcode();
+  if (XShiftOpcode == cast<BinaryOperator>(YShift)->getOpcode())
+    return nullptr; // Do not care about same-direction shifts here.
+
+  Value *X, *XShAmt, *Y, *YShAmt;
+  match(XShift, m_BinOp(m_Value(X), m_Value(XShAmt)));
+  match(YShift, m_BinOp(m_Value(Y), m_Value(YShAmt)));
+
+  // Can we fold (XShAmt+YShAmt) ?
+  Value *NewShAmt = SimplifyBinOp(Instruction::BinaryOps::Add, XShAmt, YShAmt,
+                                  SQ.getWithInstruction(&I));
+  if (!NewShAmt)
+    return nullptr;
+  // Is the new shift amount smaller than the bit width?
+  // FIXME: could also rely on ConstantRange.
+  unsigned BitWidth = X->getType()->getScalarSizeInBits();
+  if (!match(NewShAmt, m_SpecificInt_ULT(APInt(BitWidth, BitWidth))))
+    return nullptr;
+  // All good, we can do this fold. The shift is the same that was for X.
+  Value *T0 = XShiftOpcode == Instruction::BinaryOps::LShr
+                  ? Builder.CreateLShr(X, NewShAmt)
+                  : Builder.CreateShl(X, NewShAmt);
+  Value *T1 = Builder.CreateAnd(T0, Y);
+  return Builder.CreateICmp(I.getPredicate(), T1,
+                            Constant::getNullValue(X->getType()));
+}
+
 /// Try to fold icmp (binop), X or icmp X, (binop).
 /// TODO: A large part of this logic is duplicated in InstSimplify's
 /// simplifyICmpWithBinOp(). We should be able to share that and avoid the code
 /// duplication.
 Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
   // Special logic for binary operators.
Instruction *InstCombiner::foldICmpBinOp(ICmpInst &I) {
   }
 
   if (Value *V = foldICmpWithLowBitMaskedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 
   if (Value *V = foldICmpWithTruncSignExtendedVal(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  if (Value *V = foldShiftIntoShiftInAnotherHandOfAndInICmp(I, SQ, Builder))
+    return replaceInstUsesWith(I, V);
+
   return nullptr;
 }
 
 /// Fold icmp Pred min|max(X, Y), X.
 static Instruction *foldICmpWithMinMax(ICmpInst &Cmp) {
   ICmpInst::Predicate Pred = Cmp.getPredicate();
   Value *Op0 = Cmp.getOperand(0);
   Value *X = Cmp.getOperand(1);

llvm/trunk/test/Transforms/InstCombine/shift-amount-reassociation-in-bittest.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt %s -instcombine -S | FileCheck %s
 
 ; Given pattern:
 ;   icmp eq/ne (and ((x shift Q), (y oppositeshift K))), 0
 ; we should move shifts to the same hand of 'and', i.e. e.g. rewrite as
 ;   icmp eq/ne (and (((x shift Q) shift K), y)), 0
 ; We are only interested in opposite logical shifts here.
 
 ; Basic scalar test with constants
 
 define i1 @t0_const_lshr_shl_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t0_const_lshr_shl_ne(
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 define i1 @t1_const_shl_lshr_ne(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t1_const_shl_lshr_ne(
-; CHECK-NEXT:    [[T0:%.*]] = shl i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = shl i32 %x, 1
   %t1 = lshr i32 %y, 1
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 
 ; We are ok with 'eq' predicate too.
 define i1 @t2_const_lshr_shl_eq(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t2_const_lshr_shl_eq(
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp eq i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t1, %t0
   %t3 = icmp eq i32 %t2, 0
   ret i1 %t3
 }
 
 ; Basic scalar test with constants after folding
 
 define i1 @t3_const_after_fold_lshr_shl_ne(i32 %x, i32 %y, i32 %len) {
 ; CHECK-LABEL: @t3_const_after_fold_lshr_shl_ne(
-; CHECK-NEXT:    [[T0:%.*]] = sub i32 32, [[LEN:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = lshr i32 [[X:%.*]], [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[LEN]], -1
-; CHECK-NEXT:    [[T3:%.*]] = shl i32 [[Y:%.*]], [[T2]]
-; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T1]], [[T3]]
-; CHECK-NEXT:    [[T5:%.*]] = icmp ne i32 [[T4]], 0
-; CHECK-NEXT:    ret i1 [[T5]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 31
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = sub i32 32, %len
   %t1 = lshr i32 %x, %t0
   %t2 = add i32 %len, -1
   %t3 = shl i32 %y, %t2
   %t4 = and i32 %t1, %t3
   %t5 = icmp ne i32 %t4, 0
   ret i1 %t5
 }
 define i1 @t4_const_after_fold_lshr_shl_ne(i32 %x, i32 %y, i32 %len) {
 ; CHECK-LABEL: @t4_const_after_fold_lshr_shl_ne(
-; CHECK-NEXT:    [[T0:%.*]] = sub i32 32, [[LEN:%.*]]
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[X:%.*]], [[T0]]
-; CHECK-NEXT:    [[T2:%.*]] = add i32 [[LEN]], -1
-; CHECK-NEXT:    [[T3:%.*]] = lshr i32 [[Y:%.*]], [[T2]]
-; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T1]], [[T3]]
-; CHECK-NEXT:    [[T5:%.*]] = icmp ne i32 [[T4]], 0
-; CHECK-NEXT:    ret i1 [[T5]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], 31
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = sub i32 32, %len
   %t1 = shl i32 %x, %t0
   %t2 = add i32 %len, -1
   %t3 = lshr i32 %y, %t2
   %t4 = and i32 %t1, %t3
   %t5 = icmp ne i32 %t4, 0
   ret i1 %t5
;
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 
 ; Very basic vector tests
 
 define <2 x i1> @t7_const_lshr_shl_ne_vec_splat(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @t7_const_lshr_shl_ne_vec_splat(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <2 x i32> [[Y:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <2 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <2 x i32> [[T2]], zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 2, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[TMP3]]
 ;
   %t0 = lshr <2 x i32> %x, <i32 1, i32 1>
   %t1 = shl <2 x i32> %y, <i32 1, i32 1>
   %t2 = and <2 x i32> %t1, %t0
   %t3 = icmp ne <2 x i32> %t2, <i32 0, i32 0>
   ret <2 x i1> %t3
 }
 define <2 x i1> @t8_const_lshr_shl_ne_vec_nonsplat(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @t8_const_lshr_shl_ne_vec_nonsplat(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 1, i32 2>
-; CHECK-NEXT:    [[T1:%.*]] = shl <2 x i32> [[Y:%.*]], <i32 3, i32 4>
-; CHECK-NEXT:    [[T2:%.*]] = and <2 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <2 x i32> [[T2]], zeroinitializer
-; CHECK-NEXT:    ret <2 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 4, i32 6>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <2 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[TMP3]]
 ;
   %t0 = lshr <2 x i32> %x, <i32 1, i32 2>
   %t1 = shl <2 x i32> %y, <i32 3, i32 4>
   %t2 = and <2 x i32> %t1, %t0
   %t3 = icmp ne <2 x i32> %t2, <i32 0, i32 0>
   ret <2 x i1> %t3
 }
 define <3 x i1> @t9_const_lshr_shl_ne_vec_undef0(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t9_const_lshr_shl_ne_vec_undef0(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], zeroinitializer
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 undef, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 undef, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 1, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 0, i32 0>
   ret <3 x i1> %t3
 }
 define <3 x i1> @t10_const_lshr_shl_ne_vec_undef1(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t10_const_lshr_shl_ne_vec_undef1(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], zeroinitializer
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 undef, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 1, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 undef, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 0, i32 0>
   ret <3 x i1> %t3
 }
 define <3 x i1> @t11_const_lshr_shl_ne_vec_undef2(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t11_const_lshr_shl_ne_vec_undef2(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], <i32 0, i32 undef, i32 0>
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 2, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 1, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 1, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 undef, i32 0>
   ret <3 x i1> %t3
 }
 define <3 x i1> @t12_const_lshr_shl_ne_vec_undef3(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t12_const_lshr_shl_ne_vec_undef3(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], zeroinitializer
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 undef, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 undef, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 undef, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 0, i32 0>
   ret <3 x i1> %t3
 }
 define <3 x i1> @t13_const_lshr_shl_ne_vec_undef4(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t13_const_lshr_shl_ne_vec_undef4(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], <i32 0, i32 undef, i32 0>
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 undef, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 1, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 undef, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 undef, i32 0>
   ret <3 x i1> %t3
 }
 define <3 x i1> @t14_const_lshr_shl_ne_vec_undef5(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t14_const_lshr_shl_ne_vec_undef5(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], <i32 0, i32 undef, i32 0>
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 undef, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 undef, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 1, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 undef, i32 0>
   ret <3 x i1> %t3
 }
 define <3 x i1> @t15_const_lshr_shl_ne_vec_undef6(<3 x i32> %x, <3 x i32> %y) {
 ; CHECK-LABEL: @t15_const_lshr_shl_ne_vec_undef6(
-; CHECK-NEXT:    [[T0:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> [[Y:%.*]], <i32 1, i32 undef, i32 1>
-; CHECK-NEXT:    [[T2:%.*]] = and <3 x i32> [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne <3 x i32> [[T2]], <i32 0, i32 undef, i32 0>
-; CHECK-NEXT:    ret <3 x i1> [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr <3 x i32> [[X:%.*]], <i32 2, i32 undef, i32 2>
+; CHECK-NEXT:    [[TMP2:%.*]] = and <3 x i32> [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne <3 x i32> [[TMP2]], zeroinitializer
+; CHECK-NEXT:    ret <3 x i1> [[TMP3]]
 ;
   %t0 = lshr <3 x i32> %x, <i32 1, i32 undef, i32 1>
   %t1 = shl <3 x i32> %y, <i32 1, i32 undef, i32 1>
   %t2 = and <3 x i32> %t1, %t0
   %t3 = icmp ne <3 x i32> %t2, <i32 0, i32 undef, i32 0>
   ret <3 x i1> %t3
 }
 
 ; Commutativity tests
 
 declare i32 @gen32()
 
 define i1 @t16_commutativity0(i32 %x) {
 ; CHECK-LABEL: @t16_commutativity0(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %y = call i32 @gen32()
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 
 define i1 @t17_commutativity1(i32 %y) {
 ; CHECK-LABEL: @t17_commutativity1(
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @gen32()
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X]], 1
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T0]], [[T1]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %x = call i32 @gen32()
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t0, %t1 ; "swapped"
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 
 ; One-use tests
 
 declare void @use32(i32)
 
 define i1 @t18_const_oneuse0(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t18_const_oneuse0(
 ; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[Y:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = lshr i32 %x, 1
   call void @use32(i32 %t0)
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 define i1 @t19_const_oneuse1(i32 %x, i32 %y) {
 ; CHECK-LABEL: @t19_const_oneuse1(
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   call void @use32(i32 %t1)
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }

 
 ; Commutativity with extra uses
 
 define i1 @t32_commutativity0_oneuse0(i32 %x) {
 ; CHECK-LABEL: @t32_commutativity0_oneuse0(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
 ; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[Y]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %y = call i32 @gen32()
   %t0 = lshr i32 %x, 1
   call void @use32(i32 %t0)
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 define i1 @t33_commutativity0_oneuse1(i32 %x) {
 ; CHECK-LABEL: @t33_commutativity0_oneuse1(
 ; CHECK-NEXT:    [[Y:%.*]] = call i32 @gen32()
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X:%.*]], 1
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y]], 1
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[T0]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %y = call i32 @gen32()
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   call void @use32(i32 %t1)
   %t2 = and i32 %t1, %t0
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 
 define i1 @t34_commutativity1_oneuse0(i32 %y) {
 ; CHECK-LABEL: @t34_commutativity1_oneuse0(
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @gen32()
 ; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X]], 1
 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
-; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T0]], [[T1]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[Y:%.*]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %x = call i32 @gen32()
   %t0 = lshr i32 %x, 1
   call void @use32(i32 %t0)
   %t1 = shl i32 %y, 1
   %t2 = and i32 %t0, %t1 ; "swapped"
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3
 }
 define i1 @t35_commutativity1_oneuse1(i32 %y) {
 ; CHECK-LABEL: @t35_commutativity1_oneuse1(
 ; CHECK-NEXT:    [[X:%.*]] = call i32 @gen32()
-; CHECK-NEXT:    [[T0:%.*]] = lshr i32 [[X]], 1
 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 [[Y:%.*]], 1
 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
-; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T0]], [[T1]]
-; CHECK-NEXT:    [[T3:%.*]] = icmp ne i32 [[T2]], 0
-; CHECK-NEXT:    ret i1 [[T3]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X]], 2
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i32 [[TMP2]], 0
+; CHECK-NEXT:    ret i1 [[TMP3]]
 ;
   %x = call i32 @gen32()
   %t0 = lshr i32 %x, 1
   %t1 = shl i32 %y, 1
   call void @use32(i32 %t1)
   %t2 = and i32 %t0, %t1 ; "swapped"
   %t3 = icmp ne i32 %t2, 0
   ret i1 %t3