[InstCombine] Extracting common and-mask for shift operands of Or instruction

[opaparo]

Summary

Adding an InstCombine transformation:
((V<<C3)&C1) | ((V<<C4)&C2) --> ((V&C5)<<C3) | ((V&C5)<<C4), if C5 = C1>>C3 == C2>>C4, for both logical shifts.
When executed, this transforms five instructions into four, saving one instruction.

These patterns will also be transformed:
((V&C5)<<C3) | ((V<<C4)&C2) --> ((V&C5)<<C3) | ((V&C5)<<C4)
((V<<C3)&C1) | ((V&C5)<<C4) --> ((V&C5)<<C3) | ((V&C5)<<C4)

[opaparo]

Adding a pattern match for a shift of and ((V&C1)<<C2).
Although and of shift is the canonical form, this new form is also required in some cases. The new test multiuse3 demonstrate such a case.

[spatel]

Why do we canonicalize shift-left before 'and'?

Ie, shouldn't we prefer this:

define i8 @andshl(i8 %x) {
  %and = and i8 %x, 1
  %shl = shl i8 %and, 3
  ret i8 %shl
}

instead of this:

define i8 @andshl(i8 %x) {
  %and = shl i8 %x, 3
  %shl = and i8 %and, 8
  ret i8 %shl
}

...because doing the 'and' before the shift always uses a smaller constant?

[zvi]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

18

May be a nitpick of mine, but i would find it easier to follow these helpers if the argument and variable names would match the comments. E.g. Source -> V, ShifyBy -> C2, PreShiftMask ->C1 ...

[lsaba]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

11

both logical shifts (shl / lshr)

81

Check that it's the same logical shift

[lsaba]

LGTM after fixing the minor comments

[spatel]

Please answer my question. It seems like that canonicalization might simplify or obviate the need for this patch.

[opaparo]

In D39421#923308, @spatel wrote:

Why do we canonicalize shift-left before 'and'?

Ie, shouldn't we prefer this:

define i8 @andshl(i8 %x) {
  %and = and i8 %x, 1
  %shl = shl i8 %and, 3
  ret i8 %shl
}

instead of this:

define i8 @andshl(i8 %x) {
  %and = shl i8 %x, 3
  %shl = and i8 %and, 8
  ret i8 %shl
}

...because doing the 'and' before the shift always uses a smaller constant?

Hi,
Sorry for the delayed response.

I'm not sure I understand why the suggested canonization might simplify or obviate the need for this patch.
Consider my use case "multiuse3". Although InstCombine normally recognizes and canonize something of the form

%1 = and i32 %x, 96
%2 = shl nuw nsw i32 %1, 6

It will not in this case as '%1' has more than one use, and having one use is a condition for this transformation. If my transformation wouldn't consider the non-canonical in addition to the canonical form it could not handle this case.
One may argue that changing the canonical form will yield this code:

%1 = and i32 %x, 96
%2 = shl nuw nsw i32 %1, 6
%3 = lshr exact i32 %1, 1
%4 = and i32 %x, 30
%5 = shl nuw nsw i32 %4, 6
%6 = or i32 %2, %5
%7 = lshr exact i32 %4, 1
%8 = or i32 %3, %7
%9 = or i32 %8, %6
ret i32 %9

Which will then simplify the patch as I will not be required to consider the non-canonical form. However:

1. This will be true only if the two shifts are shl. In this example one of them is a lshr, so the transformation will not actually happen and the non-canonical form still needs to be considered.
2. This canonization will only occur if the intermediate results, i.e. "%4 = shl i32 %x, 6" and "%7 = lshr i32 %x, 1" have only one use. Suppose the scenario was a bit different and those values were used somewhere along the road. In this case the canonization would not happen and again I'll have to consider the non-canonical form.

As far as I understand this is the way that the suggested canonization might simplify or obviate the need for this patch. If you meant something else, could you please elaborate?

[spatel]

In D39421#935341, @opaparo wrote:

I'm not sure I understand why the suggested canonization might simplify or obviate the need for this patch.
Consider my use case "multiuse3". Although InstCombine normally recognizes and canonize something of the form

I think inverting the canonicalization of shl+and would make your first test case optimize without this patch, so that's actually where I paused in reviewing the patch. Have you investigated that possibility? Currently, we end up inverting the canonicalization in the x86 backend (because a smaller constant mask can be created in less instruction bytes), so it would be better to "get it right" here in IR in the first place.

I understand the multi-use case better now with your explanation, so I agree that we want this patch to handle those cases too. But I don't think we should ignore the underlying canonicalization choices just because we know we want to catch the larger patterns.

[opaparo]

In D39421#937705, @spatel wrote:

I think inverting the canonicalization of shl+and would make your first test case optimize without this patch

Could you please explain why? I'm not sure I'm seeing it.

Currently, we end up inverting the canonicalization in the x86 backend (because a smaller constant mask can be created in less instruction bytes), so it would be better to "get it right" here in IR in the first place.
I understand the multi-use case better now with your explanation, so I agree that we want this patch to handle those cases too. But I don't think we should ignore the underlying canonicalization choices just because we know we want to catch the larger patterns.

I agree that this alternative canonization could prove to be beneficial and more correct. However, I feel that this discussion is orthogonal to this patch, and if it would indeed be decided to switch to the new form then some of the code of this patch, along with several other pieces of code, may need to change accordingly.

[spatel]

In D39421#937773, @opaparo wrote:

In D39421#937705, @spatel wrote:

I think inverting the canonicalization of shl+and would make your first test case optimize without this patch

Could you please explain why? I'm not sure I'm seeing it.

If we invert the shl+and transform, we don't need this patch to reach optimal code for 3 out of the 6 tests:

define i32 @or_and_shifts1(i32 %x) {
  %1 = and i32 %x, 1
  %2 = shl nuw nsw i32 %1, 3
  %3 = and i32 %x, 1   <-- CSE will eliminate this
  %4 = shl nuw nsw i32 %3, 5
  %5 = or i32 %2, %4
  ret i32 %5
}

Similarly (what does this test check that is different from the above?):

define i32 @or_and_shift_shift_and(i32 %x) {
  %1 = and i32 %x, 7
  %2 = shl nuw nsw i32 %1, 3
  %3 = and i32 %x, 7  <-- CSE will eliminate this
  %4 = shl nuw nsw i32 %3, 2
  %5 = or i32 %2, %4
  ret i32 %5
}

And again:

define i32 @multiuse2(i32 %x) {
  %1 = and i32 %x, 126
  %2 = shl nuw nsw i32 %1, 8
  %3 = and i32 %x, 126 <-- CSE will eliminate this
  %4 = shl nuw nsw i32 %3, 1
  %5 = or i32 %2, %4
  ret i32 %5
}

Currently, we end up inverting the canonicalization in the x86 backend (because a smaller constant mask can be created in less instruction bytes), so it would be better to "get it right" here in IR in the first place.
I understand the multi-use case better now with your explanation, so I agree that we want this patch to handle those cases too. But I don't think we should ignore the underlying canonicalization choices just because we know we want to catch the larger patterns.

I agree that this alternative canonization could prove to be beneficial and more correct. However, I feel that this discussion is orthogonal to this patch, and if it would indeed be decided to switch to the new form then some of the code of this patch, along with several other pieces of code, may need to change accordingly.

Since we can eliminate the need for this patch in half of the tests (note: I checked in the tests at rL319182 , so we can see what they look like currently), I don't think the underlying transform is orthogonal. If this patch would change with the inverted canonicalization, then that's more reason to view the inversion as a preliminary step for this patch. Otherwise, we're adding code unnecessarily. It's possible that inverting shl+and inhibits other folds, and if that's the case, then why not fix that too?

Here's the draft patch I used to check the tests above:

Index: lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAndOrXor.cpp	(revision 319170)
+++ lib/Transforms/InstCombine/InstCombineAndOrXor.cpp	(working copy)
@@ -1212,6 +1212,13 @@
       return BinaryOperator::CreateOr(And, ConstantInt::get(I.getType(),
                                                             Together));
     }
+    const APInt *ShlC;
+    if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(ShlC))))) {
+      Constant *NewMask = ConstantInt::get(I.getType(), C->lshr(*ShlC));
+      Value *NewAnd = Builder.CreateAnd(X, NewMask);
+      return BinaryOperator::CreateShl(NewAnd, ConstantInt::get(I.getType(),
+                                                                *ShlC));
+    }
 
     // If the mask is only needed on one incoming arm, push the 'and' op up.
     if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
Index: lib/Transforms/InstCombine/InstCombineShifts.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineShifts.cpp	(revision 319170)
+++ lib/Transforms/InstCombine/InstCombineShifts.cpp	(working copy)
@@ -505,7 +505,7 @@
       // 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 (match(Op0BO->getOperand(1), m_APInt(Op0C)) && !isLeftShift) {
         if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) {
           Constant *NewRHS = ConstantExpr::get(I.getOpcode(),
                                      cast<Constant>(Op0BO->getOperand(1)), Op1);

[spatel]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

69

Why are we looking for a pattern that early-cse can simplify? I think this is beyond the scope of instcombine.

[spatel]

Both this and D38037 are trying to start a pattern match with an 'or', but I'm curious if there's a 'trunc' in the larger source that creates these patterns? Either way, we're missing something bigger than patterns that start with 'or'.

For example, I was looking at PR31667:
https://bugs.llvm.org/show_bug.cgi?id=31667

Name: sub_mask_shift

%and1 = lshr i32 %x, 3
%shr1 = and i32 %and1, 8191
%and2 = lshr i32 %x, 1
%shr2 = and i32 %and2, 32767
%r = sub i32 %shr1, %shr2

...which was filed as a backend bug, but we wouldn't handle that in IR either:
https://rise4fun.com/Alive/id4

So I think there's some more general sequence that we want to capture and optimize, but it may be difficult to justify as part of instcombine?

Note that there is a proposal for a new pass where all of these might find a home:
D38313

[opaparo]

Rebasing on parent revision and adding more test cases.

[opaparo]

In D39421#945064, @spatel wrote:

Both this and D38037 are trying to start a pattern match with an 'or', but I'm curious if there's a 'trunc' in the larger source that creates these patterns? Either way, we're missing something bigger than patterns that start with 'or'.

For example, I was looking at PR31667:
https://bugs.llvm.org/show_bug.cgi?id=31667

Name: sub_mask_shift

%and1 = lshr i32 %x, 3
%shr1 = and i32 %and1, 8191
%and2 = lshr i32 %x, 1
%shr2 = and i32 %and2, 32767
%r = sub i32 %shr1, %shr2

...which was filed as a backend bug, but we wouldn't handle that in IR either:
https://rise4fun.com/Alive/id4

So I think there's some more general sequence that we want to capture and optimize, but it may be difficult to justify as part of instcombine?

Note that there is a proposal for a new pass where all of these might find a home:
D38313

(Now abandoned) D38037 was a the first draft of this review.
There is no 'trunc' in the larger source that creates these patterns. My patch may address these issues you mentioned, but it is not directly related to them.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

69

Please check out the newly added tests multiuse4 and multiuse5.
I believe they illustrate that this is indeed an instcombine transformation.

[opaparo]

Rebasing on top of the new parent review D41354

[opaparo]

Ping

[opaparo]

Ping

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

 //===- InstCombineAndOrXor.cpp --------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visitAnd, visitOr, and visitXor functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InstCombineInternal.h"
 #include "llvm/Analysis/CmpInstAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 
 /// Similar to getICmpCode but for FCmpInst. This encodes a fcmp predicate into
static Value *getNewICmpValue(bool Sign, unsigned Code, Value *LHS, Value *RHS,
   return Builder.CreateICmp(NewPred, LHS, RHS);
 }
 
 /// This is the complement of getFCmpCode, which turns an opcode and two
 /// operands into either a FCmp instruction, or a true/false constant.
 static Value *getFCmpValue(unsigned Code, Value *LHS, Value *RHS,
                            InstCombiner::BuilderTy &Builder) {
   const auto Pred = static_cast<FCmpInst::Predicate>(Code);
   assert(FCmpInst::FCMP_FALSE <= Pred && Pred <= FCmpInst::FCMP_TRUE &&
          "Unexpected FCmp predicate!");
   if (Pred == FCmpInst::FCMP_FALSE)
     return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 0);
   if (Pred == FCmpInst::FCMP_TRUE)
     return ConstantInt::get(CmpInst::makeCmpResultType(LHS->getType()), 1);
   return Builder.CreateFCmp(Pred, LHS, RHS);
 }
 
 /// \brief Transform BITWISE_OP(BSWAP(A),BSWAP(B)) or
 /// BITWISE_OP(BSWAP(A), Constant) to BSWAP(BITWISE_OP(A, B))
 /// \param I Binary operator to transform.
 /// \return Pointer to node that must replace the original binary operator, or
 ///         null pointer if no transformation was made.
 static Value *SimplifyBSwap(BinaryOperator &I,
                             InstCombiner::BuilderTy &Builder) {
   assert(I.isBitwiseLogicOp() && "Unexpected opcode for bswap simplifying");
 
   Value *OldLHS = I.getOperand(0);
   Value *OldRHS = I.getOperand(1);
 
if (match(Op0, m_OneUse(m_Or(m_Value(X), m_APInt(OrC))))) {
       // above, but this feels safer.
       APInt Together = *C & *OrC;
       Value *And = Builder.CreateAnd(X, ConstantInt::get(I.getType(),
                                                          Together ^ *C));
       And->takeName(Op0);
       return BinaryOperator::CreateOr(And, ConstantInt::get(I.getType(),
                                                             Together));
     }
+    const APInt *ShlC;
+    if (match(Op0, m_OneUse(m_Shl(m_Value(X), m_APInt(ShlC))))) {
+      if (!isa<Instruction>(X) || !cast<Instruction>(X)->isShift()) {
+        Constant *NewMask = ConstantInt::get(I.getType(), C->lshr(*ShlC));
+        Value *NewAnd = Builder.CreateAnd(X, NewMask);
+        return BinaryOperator::CreateShl(NewAnd,
+                                         ConstantInt::get(I.getType(), *ShlC));
+      }
+    }
 
     // If the mask is only needed on one incoming arm, push the 'and' op up.
     if (match(Op0, m_OneUse(m_Xor(m_Value(X), m_Value(Y)))) ||
         match(Op0, m_OneUse(m_Or(m_Value(X), m_Value(Y))))) {
       APInt NotAndMask(~(*C));
       BinaryOperator::BinaryOps BinOp = cast<BinaryOperator>(Op0)->getOpcode();
       if (MaskedValueIsZero(X, NotAndMask, 0, &I)) {
         // Not masking anything out for the LHS, move mask to RHS.

lib/Transforms/InstCombine/InstCombineShifts.cpp

if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0)) {
         break;
       }
       }
 
 
       // 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 (match(Op0BO->getOperand(1), m_APInt(Op0C)) &&
+          ((!isLeftShift || Op0BO->getOpcode() != Instruction::And) ||
+           (isa<Instruction>(Op0BO->getOperand(0)) &&
+            cast<Instruction>(Op0BO->getOperand(0))->isShift()))) {
         if (canShiftBinOpWithConstantRHS(I, Op0BO, *Op0C)) {
           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);
 

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

 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; <rdar://problem/8606771>
 define i32 @main(i32 %argc) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:    [[TMP3151:%.*]] = trunc i32 %argc to i8
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 [[TMP3151]], 5
-; CHECK-NEXT:    [[TMP4126:%.*]] = and i8 [[TMP1]], 64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[TMP3151]], 2
+; CHECK-NEXT:    [[TMP4126:%.*]] = shl nuw nsw i8 [[TMP1]], 5
 ; CHECK-NEXT:    [[TMP4127:%.*]] = xor i8 [[TMP4126]], 64
 ; CHECK-NEXT:    [[TMP4086:%.*]] = zext i8 [[TMP4127]] to i32
 ; CHECK-NEXT:    ret i32 [[TMP4086]]
 ;
   %tmp3151 = trunc i32 %argc to i8
   %tmp3161 = or i8 %tmp3151, -17
   %tmp3162 = and i8 %tmp3151, 122
   %tmp3163 = xor i8 %tmp3162, -17

test/Transforms/InstCombine/bswap.ll

;
   %tmp6 = lshr i32 %x, 24
   %tmp7 = or i32 %tmp5, %tmp6
   ret i32 %tmp7
 }
 
 ; PR23863
 define i32 @test7(i32 %x) {
 ; CHECK-LABEL: @test7(
-; CHECK-NEXT:    [[OR6:%.*]] = call i32 @llvm.bswap.i32(i32 %x)
+; CHECK-NEXT:    [[SHL:%.*]] = shl i32 %x, 16
+; CHECK-NEXT:    [[SHR:%.*]] = lshr i32 %x, 16
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], [[SHR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR]], 16711935
+; CHECK-NEXT:    [[SHL3:%.*]] = shl nuw i32 [[TMP1]], 8
+; CHECK-NEXT:    [[AND4:%.*]] = lshr i32 [[OR]], 8
+; CHECK-NEXT:    [[SHR5:%.*]] = and i32 [[AND4]], 16711935
+; CHECK-NEXT:    [[OR6:%.*]] = or i32 [[SHL3]], [[SHR5]]
 ; CHECK-NEXT:    ret i32 [[OR6]]
 ;
   %shl = shl i32 %x, 16
   %shr = lshr i32 %x, 16
   %or = or i32 %shl, %shr
   %and2 = shl i32 %or, 8
   %shl3 = and i32 %and2, -16711936
   %and4 = lshr i32 %or, 8
;
   %shl = shl i32 %conv, 8
   %or = or i32 %shr, %shl
   %conv2 = trunc i32 %or to i16
   ret i16 %conv2
 }
 
 define i16 @test10(i32 %a) {
 ; CHECK-LABEL: @test10(
-; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 %a to i16
-; CHECK-NEXT:    [[REV:%.*]] = call i16 @llvm.bswap.i16(i16 [[TRUNC]])
-; CHECK-NEXT:    ret i16 [[REV]]
+; CHECK-NEXT:    [[SHR1:%.*]] = lshr i32 %a, 8
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[SHR1]], 255
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %a, 255
+; CHECK-NEXT:    [[SHL1:%.*]] = shl nuw nsw i32 [[TMP1]], 8
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[AND1]], [[SHL1]]
+; CHECK-NEXT:    [[CONV:%.*]] = trunc i32 [[OR]] to i16
+; CHECK-NEXT:    ret i16 [[CONV]]
 ;
   %shr1 = lshr i32 %a, 8
   %and1 = and i32 %shr1, 255
   %and2 = shl i32 %a, 8
   %shl1 = and i32 %and2, 65280
   %or = or i32 %and1, %shl1
   %conv = trunc i32 %or to i16
   ret i16 %conv
 }
 

test/Transforms/InstCombine/cast.ll

;
   %C = or i32 %B, %D
   %E = zext i32 %C to i64
   ret i64 %E
 }
 
 
 define i64 @test46(i64 %A) {
 ; CHECK-LABEL: @test46(
-; CHECK-NEXT:    [[C:%.*]] = shl i64 %A, 8
-; CHECK-NEXT:    [[D:%.*]] = and i64 [[C]], 10752
+; CHECK-NEXT:    [[C:%.*]] = and i64 %A, 42
+; CHECK-NEXT:    [[D:%.*]] = shl nuw nsw i64 [[C]], 8
 ; CHECK-NEXT:    ret i64 [[D]]
 ;
   %B = trunc i64 %A to i32
   %C = and i32 %B, 42
   %D = shl i32 %C, 8
   %E = zext i32 %D to i64
   ret i64 %E
 }
 
 define <2 x i64> @test46vec(<2 x i64> %A) {
 ; CHECK-LABEL: @test46vec(
-; CHECK-NEXT:    [[C:%.*]] = shl <2 x i64> [[A:%.*]], <i64 8, i64 8>
-; CHECK-NEXT:    [[D:%.*]] = and <2 x i64> [[C]], <i64 10752, i64 10752>
+; CHECK-NEXT:    [[C:%.*]] = and <2 x i64> %A, <i64 42, i64 42>
+; CHECK-NEXT:    [[D:%.*]] = shl nuw nsw <2 x i64> [[C]], <i64 8, i64 8>
 ; CHECK-NEXT:    ret <2 x i64> [[D]]
 ;
   %B = trunc <2 x i64> %A to <2 x i32>
   %C = and <2 x i32> %B, <i32 42, i32 42>
   %D = shl <2 x i32> %C, <i32 8, i32 8>
   %E = zext <2 x i32> %D to <2 x i64>
   ret <2 x i64> %E
 }
;
   %D = or i32 %C, 128
   %E = zext i32 %D to i64
   ret i64 %E
 
 }
 
 define i64 @test59(i8 %A, i8 %B) nounwind {
 ; CHECK-LABEL: @test59(
-; CHECK-NEXT:    [[C:%.*]] = zext i8 %A to i64
-; CHECK-NEXT:    [[D:%.*]] = shl nuw nsw i64 [[C]], 4
-; CHECK-NEXT:    [[E:%.*]] = and i64 [[D]], 48
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 %B, 4
-; CHECK-NEXT:    [[G:%.*]] = zext i8 [[TMP1]] to i64
-; CHECK-NEXT:    [[H:%.*]] = or i64 [[E]], [[G]]
-; CHECK-NEXT:    ret i64 [[H]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %A, 3
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i8 [[TMP1]], 4
+; CHECK-NEXT:    [[TMP3:%.*]] = lshr i8 %B, 4
+; CHECK-NEXT:    [[H:%.*]] = or i8 [[TMP3]], [[TMP2]]
+; CHECK-NEXT:    [[I:%.*]] = zext i8 [[H]] to i64
+; CHECK-NEXT:    ret i64 [[I]]
 ;
   %C = zext i8 %A to i32
   %D = shl i32 %C, 4
   %E = and i32 %D, 48
   %F = zext i8 %B to i32
   %G = lshr i32 %F, 4
   %H = or i32 %G, %E
   %I = zext i32 %H to i64
;
   %pp = getelementptr i8, i8* %q, i64 %i
   %r = bitcast i8* %pp to double*
   %l = load double, double* %r
   ret double %l
 }
 
 define i64 @test82(i64 %A) nounwind {
 ; CHECK-LABEL: @test82(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 %A, 1
-; CHECK-NEXT:    [[E:%.*]] = and i64 [[TMP1]], 4294966784
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 %A, 2147483392
+; CHECK-NEXT:    [[E:%.*]] = shl nuw nsw i64 %1, 1
 ; CHECK-NEXT:    ret i64 [[E]]
 ;
   %B = trunc i64 %A to i32
   %C = lshr i32 %B, 8
   %D = shl i32 %C, 9
   %E = zext i32 %D to i64
   ret i64 %E
 }

test/Transforms/InstCombine/or-shifted-masks.ll

 ; RUN: opt -S -instcombine < %s | FileCheck %s
 
 define i32 @or_and_shifts1(i32 %x) {
 ; CHECK-LABEL: @or_and_shifts1(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 8
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 %x, 5
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 32
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 5
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = shl i32 %x, 3
   %2 = and i32 %1, 15
   %3 = shl i32 %x, 5
   %4 = and i32 %3, 60
   %5 = or i32 %2, %4
   ret i32 %5
 }
 
 define i32 @or_and_shifts2(i32 %x) {
 ; CHECK-LABEL: @or_and_shifts2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 896
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 112
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 %x, 4
 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 7
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = shl i32 %x, 3
   %2 = and i32 %1, 896
   %3 = lshr i32 %x, 4
   %4 = and i32 %3, 7
   %5 = or i32 %2, %4
   ret i32 %5
 }
 
 define i32 @or_and_shift_shift_and(i32 %x) {
 ; CHECK-LABEL: @or_and_shift_shift_and(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 56
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 %x, 2
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 28
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 7
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 3
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 7
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 2
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i32 %x, 7
   %2 = shl i32 %1, 3
   %3 = shl i32 %x, 2
   %4 = and i32 %3, 28
   %5 = or i32 %2, %4
   ret i32 %5
 }
 
 define i32 @multiuse1(i32 %x) {
 ; CHECK-LABEL: @multiuse1(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 6
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 384
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 6
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 6
 ; CHECK-NEXT:    [[TMP3:%.*]] = lshr i32 %x, 1
 ; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 3
 ; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP4]], [[TMP2]]
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i32 %x, 2
   %2 = and i32 %x, 4
   %3 = shl nuw nsw i32 %1, 6
   %4 = lshr exact i32 %1, 1
   %5 = shl nuw nsw i32 %2, 6
   %6 = lshr exact i32 %2, 1
   %7 = or i32 %3, %5
   %8 = or i32 %4, %6
   %9 = or i32 %8, %7
   ret i32 %9
 }
 
 define i32 @multiuse2(i32 %x) {
 ; CHECK-LABEL: @multiuse2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 1
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 12
-; CHECK-NEXT:    [[TMP3:%.*]] = shl i32 %x, 8
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], 24576
-; CHECK-NEXT:    [[TMP5:%.*]] = shl i32 %x, 8
-; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 7680
-; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP4]], [[TMP6]]
-; CHECK-NEXT:    [[TMP8:%.*]] = shl i32 %x, 1
-; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP8]], 240
-; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP2]], [[TMP9]]
-; CHECK-NEXT:    [[TMP11:%.*]] = or i32 [[TMP7]], [[TMP10]]
-; CHECK-NEXT:    ret i32 [[TMP11]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 126
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 8
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 126
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 1
+; CHECK-NEXT:    [[TMP5:%.*]] = or i32 [[TMP2]], [[TMP4]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i32 %x, 6
   %2 = shl nuw nsw i32 %1, 8
   %3 = shl nuw nsw i32 %1, 1
   %4 = and i32 %x, 24
   %5 = shl nuw nsw i32 %4, 8
   %6 = shl nuw nsw i32 %4, 1
   %7 = and i32 %x, 96
   %8 = shl nuw nsw i32 %7, 8
   %9 = shl nuw nsw i32 %7, 1
   %10 = or i32 %2, %5
   %11 = or i32 %8, %10
   %12 = or i32 %9, %6
   %13 = or i32 %3, %12
   %14 = or i32 %11, %13
   ret i32 %14
 }
 
 define i32 @multiuse3(i32 %x) {
 ; CHECK-LABEL: @multiuse3(
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 96
-; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 6
-; CHECK-NEXT:    [[TMP3:%.*]] = lshr exact i32 [[TMP1]], 1
-; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 %x, 6
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 1920
-; CHECK-NEXT:    [[TMP6:%.*]] = or i32 [[TMP2]], [[TMP5]]
-; CHECK-NEXT:    [[TMP7:%.*]] = lshr i32 %x, 1
-; CHECK-NEXT:    [[TMP8:%.*]] = and i32 [[TMP7]], 15
-; CHECK-NEXT:    [[TMP9:%.*]] = or i32 [[TMP3]], [[TMP8]]
-; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP6]]
-; CHECK-NEXT:    ret i32 [[TMP10]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 %x, 1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 48
+; CHECK-NEXT:    [[TMP3:%.*]] = and i32 %x, 126
+; CHECK-NEXT:    [[TMP4:%.*]] = shl nuw nsw i32 [[TMP3]], 6
+; CHECK-NEXT:    [[TMP5:%.*]] = lshr i32 %x, 1
+; CHECK-NEXT:    [[TMP6:%.*]] = and i32 [[TMP5]], 15
+; CHECK-NEXT:    [[TMP7:%.*]] = or i32 [[TMP2]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = or i32 [[TMP7]], [[TMP4]]
+; CHECK-NEXT:    ret i32 [[TMP8]]
 ;
   %1 = and i32 %x, 96
   %2 = shl nuw nsw i32 %1, 6
   %3 = lshr exact i32 %1, 1
   %4 = shl i32 %x, 6
   %5 = and i32 %4, 1920
   %6 = or i32 %2, %5
   %7 = lshr i32 %x, 1

 
 define i32 @multiuse5(i32 %x) local_unnamed_addr #0 {
 ; CHECK-LABEL: @multiuse5(
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 5
 ; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 %x, -1
 ; CHECK-NEXT:    br i1 [[TMP2]], label %if, label %else
 ; CHECK:         {{.*}}if:{{.*}}
 ; CHECK-NEXT:    [[TMP3:%.*]] = and i32 [[TMP1]], 21760
-; CHECK-NEXT:    [[TMP4:%.*]] = shl i32 %x, 5
-; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], 43520
+; CHECK-NEXT:    [[TMP4:%.*]] = and i32 %x, 1360
+; CHECK-NEXT:    [[TMP5:%.*]] = shl nuw nsw i32 [[TMP4]], 5
 ; CHECK-NEXT:    [[TMP6:%.*]] = or i32 [[TMP5]], [[TMP3]]
 ; CHECK-NEXT:    br label %end
 ; CHECK:         {{.*}}else:{{.*}}
 ; CHECK-NEXT:    [[TMP7:%.*]] = and i32 [[TMP1]], 5570560
-; CHECK-NEXT:    [[TMP8:%.*]] = shl i32 %x, 5
-; CHECK-NEXT:    [[TMP9:%.*]] = and i32 [[TMP8]], 11141120
+; CHECK-NEXT:    [[TMP8:%.*]] = and i32 %x, 348160
+; CHECK-NEXT:    [[TMP9:%.*]] = shl nuw nsw i32 [[TMP8]], 5
 ; CHECK-NEXT:    [[TMP10:%.*]] = or i32 [[TMP9]], [[TMP7]]
 ; CHECK-NEXT:    br label %end
 ; CHECK:         {{.*}}end{{.*}}
 ; CHECK-NEXT:    [[TMP11:%.*]] = phi i32 [ [[TMP6]], %if ], [ [[TMP10]], %else ]
 ; CHECK-NEXT:    ret i32 [[TMP11]]
 ;
   %1 = shl i32 %x, 5
   %2 = icmp sgt i32 %x, -1

test/Transforms/InstCombine/pr17827.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 ; With left shift, the comparison should not be modified.
 define i1 @test_shift_and_cmp_not_changed1(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_not_changed1(
-; CHECK-NEXT:    [[SHLP:%.*]] = shl i8 %p, 5
-; CHECK-NEXT:    [[ANDP:%.*]] = and i8 [[SHLP]], -64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[ANDP:%.*]] = shl nuw i8 [[TMP1]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ANDP]], 32
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp slt i8 %andp, 32
   ret i1 %cmp
 }
;
   %cmp = icmp slt i8 %andp, 32
   ret i1 %cmp
 }
 
 ; This should simplify functionally to the left shift case.
 ; The extra input parameter should be optimized away.
 define i1 @test_shift_and_cmp_changed1(i8 %p, i8 %q) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed1(
-; CHECK-NEXT:    [[ANDP:%.*]] = shl i8 %p, 5
-; CHECK-NEXT:    [[SHL:%.*]] = and i8 [[ANDP]], -64
+; CHECK-NEXT:    [[ANDP:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i8 %andp, 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[SHL]], 32
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %andp = and i8 %p, 6
   %andq = and i8 %q, 8
   %or = or i8 %andq, %andp
   %shl = shl i8 %or, 5
   %ashr = ashr i8 %shl, 5
   %cmp = icmp slt i8 %ashr, 1
   ret i1 %cmp
 }
 
 define <2 x i1> @test_shift_and_cmp_changed1_vec(<2 x i8> %p, <2 x i8> %q) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed1_vec(
-; CHECK-NEXT:    [[ANDP:%.*]] = shl <2 x i8> [[P:%.*]], <i8 5, i8 5>
-; CHECK-NEXT:    [[SHL:%.*]] = and <2 x i8> [[ANDP]], <i8 -64, i8 -64>
+; CHECK-NEXT:    [[ANDP:%.*]] = and <2 x i8> %p, <i8 6, i8 6>
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw <2 x i8> [[ANDP]], <i8 5, i8 5>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt <2 x i8> [[SHL]], <i8 32, i8 32>
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %andp = and <2 x i8> %p, <i8 6, i8 6>
   %andq = and <2 x i8> %q, <i8 8, i8 8>
   %or = or <2 x i8> %andq, %andp
   %shl = shl <2 x i8> %or, <i8 5, i8 5>
   %ashr = ashr <2 x i8> %shl, <i8 5, i8 5>
   %cmp = icmp slt <2 x i8> %ashr, <i8 1, i8 1>
   ret <2 x i1> %cmp
 }
 
 ; Unsigned compare allows a transformation to compare against 0.
 define i1 @test_shift_and_cmp_changed2(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed2(
-; CHECK-NEXT:    [[ANDP:%.*]] = and i8 %p, 6
-; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[ANDP]], 0
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP1]], 0
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp ult i8 %andp, 32
   ret i1 %cmp
 }
 
 define <2 x i1> @test_shift_and_cmp_changed2_vec(<2 x i8> %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed2_vec(
 ; CHECK-NEXT:    [[ANDP:%.*]] = and <2 x i8> %p, <i8 6, i8 6>
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp eq <2 x i8> [[ANDP]], zeroinitializer
 ; CHECK-NEXT:    ret <2 x i1> [[CMP]]
 ;
   %shlp = shl <2 x i8> %p, <i8 5, i8 5>
   %andp = and <2 x i8> %shlp, <i8 -64, i8 -64>
   %cmp = icmp ult <2 x i8> %andp, <i8 32, i8 32>
   ret <2 x i1> %cmp
 }
 
 ; nsw on the shift should not affect the comparison.
 define i1 @test_shift_and_cmp_changed3(i8 %p) {
 ; CHECK-LABEL: @test_shift_and_cmp_changed3(
-; CHECK-NEXT:    [[SHLP:%.*]] = shl nsw i8 %p, 5
-; CHECK-NEXT:    [[ANDP:%.*]] = and i8 [[SHLP]], -64
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %p, 6
+; CHECK-NEXT:    [[ANDP:%.*]] = shl nuw i8 [[TMP1]], 5
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i8 [[ANDP]], 32
 ; CHECK-NEXT:    ret i1 [[CMP]]
 ;
   %shlp = shl nsw i8 %p, 5
   %andp = and i8 %shlp, -64
   %cmp = icmp slt i8 %andp, 32
   ret i1 %cmp
 }

test/Transforms/InstCombine/rem.ll

 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %A = urem i32 1, %X
   ret i32 %A
 }
 
 define i32 @test18(i16 %x, i32 %y) {
 ; CHECK-LABEL: @test18(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i16 %x, 3
-; CHECK-NEXT:    [[TMP2:%.*]] = and i16 [[TMP1]], 32
+; CHECK-NEXT:    [[TMP1:%.*]] = and i16 %x, 4
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i16 [[TMP1]], 3
 ; CHECK-NEXT:    [[TMP3:%.*]] = xor i16 [[TMP2]], 63
 ; CHECK-NEXT:    [[TMP4:%.*]] = zext i16 [[TMP3]] to i32
 ; CHECK-NEXT:    [[TMP5:%.*]] = and i32 [[TMP4]], %y
 ; CHECK-NEXT:    ret i32 [[TMP5]]
 ;
   %1 = and i16 %x, 4
   %2 = icmp ne i16 %1, 0
   %3 = select i1 %2, i32 32, i32 64

test/Transforms/InstCombine/select-bitext-bitwise-ops.ll

;
   %4 = icmp eq i32 %1, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6
 }
 
 define i64 @sel_false_val_is_a_masked_shl_of_true_val2(i32 %x, i64 %y) {
 ; CHECK-LABEL: @sel_false_val_is_a_masked_shl_of_true_val2(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 2
-; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 60
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 15
+; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i32 [[TMP1]], 2
 ; CHECK-NEXT:    [[TMP3:%.*]] = zext i32 [[TMP2]] to i64
-; CHECK-NEXT:    [[TMP4:%.*]] = ashr i64 %y, [[TMP3]]
-; CHECK-NEXT:    ret i64 [[TMP4]]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[TMP1]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i64 0, i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP6:%.*]] = ashr i64 %y, [[TMP5]]
+; CHECK-NEXT:    ret i64 [[TMP6]]
 ;
   %1 = and i32 %x, 15
   %2 = shl nuw nsw i32 %1, 2
   %3 = zext i32 %2 to i64
   %4 = icmp eq i32 %2, 0
   %5 = ashr i64 %y, %3
   %6 = select i1 %4, i64 %y, i64 %5
   ret i64 %6

test/Transforms/InstCombine/select-with-bitwise-ops.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -instcombine -S | FileCheck %s
 
 target datalayout = "n8:16:32:64"
 
 define i32 @select_icmp_eq_and_1_0_or_2(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_1_0_or_2(
-; CHECK-NEXT:    [[AND:%.*]] = shl i32 %x, 1
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 1
 ; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], %y
 ; CHECK-NEXT:    ret i32 [[TMP2]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %or = or i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %or
   ret i32 %select
 }
 
 define <2 x i32> @select_icmp_eq_and_1_0_or_2_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @select_icmp_eq_and_1_0_or_2_vec(
-; CHECK-NEXT:    [[AND:%.*]] = shl <2 x i32> [[X:%.*]], <i32 1, i32 1>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[AND]], <i32 2, i32 2>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> %x, <i32 1, i32 1>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw <2 x i32> [[AND]], <i32 1, i32 1>
 ; CHECK-NEXT:    [[TMP2:%.*]] = or <2 x i32> [[TMP1]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP2]]
 ;
   %and = and <2 x i32> %x, <i32 1, i32 1>
   %cmp = icmp eq <2 x i32> %and, zeroinitializer
   %or = or <2 x i32> %y, <i32 2, i32 2>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or
   ret <2 x i32> %select
;
   %cmp = icmp ne i32 0, %and
   %and2 = and i32 %y, -33
   %select = select i1 %cmp, i32 %y, i32 %and2
   ret i32 %select
 }
 
 define i32 @select_icmp_ne_0_and_32_or_4096(i32 %x, i32 %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_32_or_4096(
-; CHECK-NEXT:    [[AND:%.*]] = shl i32 %x, 7
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 4096
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 32
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 7
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[TMP1]], 4096
 ; CHECK-NEXT:    [[TMP3:%.*]] = or i32 [[TMP2]], %y
 ; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
   %and = and i32 %x, 32
   %cmp = icmp ne i32 0, %and
   %or = or i32 %y, 4096
   %select = select i1 %cmp, i32 %y, i32 %or
   ret i32 %select
 }
 
 define <2 x i32> @select_icmp_ne_0_and_32_or_4096_vec(<2 x i32> %x, <2 x i32> %y) {
 ; CHECK-LABEL: @select_icmp_ne_0_and_32_or_4096_vec(
-; CHECK-NEXT:    [[AND:%.*]] = shl <2 x i32> [[X:%.*]], <i32 7, i32 7>
-; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> [[AND]], <i32 4096, i32 4096>
+; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> %x, <i32 32, i32 32>
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw <2 x i32> [[AND]], <i32 7, i32 7>
 ; CHECK-NEXT:    [[TMP2:%.*]] = xor <2 x i32> [[TMP1]], <i32 4096, i32 4096>
 ; CHECK-NEXT:    [[TMP3:%.*]] = or <2 x i32> [[TMP2]], [[Y:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[TMP3]]
 ;
   %and = and <2 x i32> %x, <i32 32, i32 32>
   %cmp = icmp ne <2 x i32> zeroinitializer, %and
   %or = or <2 x i32> %y, <i32 4096, i32 4096>
   %select = select <2 x i1> %cmp, <2 x i32> %y, <2 x i32> %or

 ;
   %1 = icmp sgt <2 x i32> %x, <i32 -1, i32 -1>
   %2 = select <2 x i1> %1, <2 x i32> <i32 40, i32 40>, <2 x i32> <i32 42, i32 42>
   ret <2 x i32> %2
 }
 
 define i32 @shift_no_xor_multiuse_or(i32 %x, i32 %y) {
 ; CHECK-LABEL: @shift_no_xor_multiuse_or(
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[Y:%.*]], 2
-; CHECK-NEXT:    [[AND:%.*]] = shl i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[AND]], 2
-; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[Y]]
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[OR:%.*]] = or i32 %y, 2
+; CHECK-NEXT:    [[TMP1:%.*]] = shl nuw nsw i32 [[AND]], 1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], %y
 ; CHECK-NEXT:    [[RES:%.*]] = mul i32 [[TMP2]], [[OR]]
 ; CHECK-NEXT:    ret i32 [[RES]]
 ;
   %and = and i32 %x, 1
   %cmp = icmp eq i32 %and, 0
   %or = or i32 %y, 2
   %select = select i1 %cmp, i32 %y, i32 %or
   %res = mul i32 %select, %or ; to bump up use count of the Or

test/Transforms/InstCombine/select.ll

 
 ;; (a & 128) ? 256 : 0
 define i32 @test15e(i32 %X) {
         %t1 = and i32 %X, 128
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 256, i32 0
         ret i32 %t3
 ; CHECK-LABEL: @test15e(
-; CHECK: %t1 = shl i32 %X, 1
-; CHECK: and i32 %t1, 256
+; CHECK: %t1 = and i32 %X, 128
+; CHECK: shl nuw nsw i32 %t1, 1
 ; CHECK: ret i32
 }
 
 ;; (a & 128) ? 0 : 256
 define i32 @test15f(i32 %X) {
         %t1 = and i32 %X, 128
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 0, i32 256
         ret i32 %t3
 ; CHECK-LABEL: @test15f(
-; CHECK: %t1 = shl i32 %X, 1
-; CHECK: and i32 %t1, 256
+; CHECK: %t1 = and i32 %X, 128
+; CHECK: shl nuw nsw i32 %t1, 1
 ; CHECK: xor i32 %{{.*}}, 256
 ; CHECK: ret i32
 }
 
 ;; (a & 8) ? -1 : -9
 define i32 @test15g(i32 %X) {
         %t1 = and i32 %X, 8
         %t2 = icmp ne i32 %t1, 0

 
 ;; (a & 2) ? 577 : 1089
 define i32 @test15i(i32 %X) {
         %t1 = and i32 %X, 2
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 577, i32 1089
         ret i32 %t3
 ; CHECK-LABEL: @test15i(
-; CHECK-NEXT: %t1 = shl i32 %X, 8
-; CHECK-NEXT: %1 = and i32 %t1, 512
+; CHECK-NEXT: %t1 = and i32 %X, 2
+; CHECK-NEXT: %1 = shl nuw nsw i32 %t1, 8
 ; CHECK-NEXT: %2 = xor i32 %1, 512
 ; CHECK-NEXT: %3 = add nuw nsw i32 %2, 577
 ; CHECK-NEXT: ret i32 %3
 }
 
 ;; (a & 2) ? 1089 : 577
 define i32 @test15j(i32 %X) {
         %t1 = and i32 %X, 2
         %t2 = icmp ne i32 %t1, 0
         %t3 = select i1 %t2, i32 1089, i32 577
         ret i32 %t3
 ; CHECK-LABEL: @test15j(
-; CHECK-NEXT: %t1 = shl i32 %X, 8
-; CHECK-NEXT: %1 = and i32 %t1, 512
+; CHECK-NEXT: %t1 = and i32 %X, 2
+; CHECK-NEXT: %1 = shl nuw nsw i32 %t1, 8
 ; CHECK-NEXT: %2 = add nuw nsw i32 %1, 577
 ; CHECK-NEXT: ret i32 %2
 }
 
 define i32 @test16(i1 %C, i32* %P) {
         %P2 = select i1 %C, i32* %P, i32* null
         %V = load i32, i32* %P2
         ret i32 %V

test/Transforms/InstCombine/shift-shift.ll

 
 define i32 @pr8547(i32* %g) {
 ; CHECK-LABEL: @pr8547(
 ; CHECK-NEXT:  codeRepl:
 ; CHECK-NEXT:    br label %for.cond
 ; CHECK:       for.cond:
 ; CHECK-NEXT:    [[STOREMERGE:%.*]] = phi i32 [ 0, %codeRepl ], [ 5, %for.cond ]
 ; CHECK-NEXT:    store i32 [[STOREMERGE]], i32* %g, align 4
-; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw nsw i32 [[STOREMERGE]], 6
-; CHECK-NEXT:    [[CONV2:%.*]] = and i32 [[TMP0]], 64
-; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[CONV2]], 0
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[STOREMERGE]], 1
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TMP0]], 0
 ; CHECK-NEXT:    br i1 [[TOBOOL]], label %for.cond, label %codeRepl2
 ; CHECK:       codeRepl2:
+; CHECK-NEXT:    [[CONV2:%.*]] = shl nuw nsw i32 [[TMP0]], 6
 ; CHECK-NEXT:    ret i32 [[CONV2]]
 ;
 codeRepl:
   br label %for.cond
 
 for.cond:
   %storemerge = phi i32 [ 0, %codeRepl ], [ 5, %for.cond ]
   store i32 %storemerge, i32* %g, align 4

test/Transforms/InstCombine/shift.ll

 }
 
 ; <rdar://problem/8756731>
 define i8 @test39(i32 %a0) {
 ; CHECK-LABEL: @test39(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP4:%.*]] = trunc i32 %a0 to i8
 ; CHECK-NEXT:    [[TMP5:%.*]] = shl i8 [[TMP4]], 5
-; CHECK-NEXT:    [[TMP49:%.*]] = shl i8 [[TMP4]], 6
-; CHECK-NEXT:    [[TMP50:%.*]] = and i8 [[TMP49]], 64
+; CHECK-NEXT:    [[TMP49:%.*]] = and i8 [[TMP4]], 1
+; CHECK-NEXT:    [[TMP50:%.*]] = shl nuw nsw i8 [[TMP49]], 6
 ; CHECK-NEXT:    [[TMP51:%.*]] = xor i8 [[TMP50]], [[TMP5]]
-; CHECK-NEXT:    [[TMP0:%.*]] = shl i8 [[TMP4]], 2
-; CHECK-NEXT:    [[TMP54:%.*]] = and i8 [[TMP0]], 16
+; CHECK-NEXT:    [[TMP0:%.*]] = and i8 [[TMP4]], 4
+; CHECK-NEXT:    [[TMP54:%.*]] = shl nuw nsw i8 [[TMP0]], 2
 ; CHECK-NEXT:    [[TMP551:%.*]] = or i8 [[TMP54]], [[TMP51]]
 ; CHECK-NEXT:    ret i8 [[TMP551]]
 ;
 entry:
   %tmp4 = trunc i32 %a0 to i8
   %tmp5 = shl i8 %tmp4, 5
   %tmp48 = and i8 %tmp5, 32
   %tmp49 = lshr i8 %tmp48, 5
;
   %B = lshr <2 x i32> %A, <i32 1, i32 1>
   ret <2 x i32> %B
 }
 
 ; (X << C1) >>u C2  --> X << (C1 - C2) & (-1 >> C2)
 
 define i8 @test53_no_nuw(i8 %x) {
 ; CHECK-LABEL: @test53_no_nuw(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i8 %x, 2
-; CHECK-NEXT:    [[B:%.*]] = and i8 [[TMP1]], 124
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 %x, 31
+; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw i8 [[TMP1]], 2
 ; CHECK-NEXT:    ret i8 [[B]]
 ;
   %A = shl i8 %x, 3
   %B = lshr i8 %A, 1
   ret i8 %B
 }
 
 ; (X << C1) >>u C2  --> X << (C1 - C2) & (-1 >> C2)
 
 define <2 x i8> @test53_no_nuw_splat_vec(<2 x i8> %x) {
 ; CHECK-LABEL: @test53_no_nuw_splat_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i8> %x, <i8 2, i8 2>
-; CHECK-NEXT:    [[B:%.*]] = and <2 x i8> [[TMP1]], <i8 124, i8 124>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i8> %x, <i8 31, i8 31>
+; CHECK-NEXT:    [[B:%.*]] = shl nuw nsw <2 x i8> [[TMP1]], <i8 2, i8 2>
 ; CHECK-NEXT:    ret <2 x i8> [[B]]
 ;
   %A = shl <2 x i8> %x, <i8 3, i8 3>
   %B = lshr <2 x i8> %A, <i8 1, i8 1>
   ret <2 x i8> %B
 }
 
 define i32 @test54(i32 %x) {
 ; CHECK-LABEL: @test54(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 %x, 3
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[TMP1]], 16
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 %x, 2
+; CHECK-NEXT:    [[AND:%.*]] = shl nuw nsw i32 [[TMP1]], 3
 ; CHECK-NEXT:    ret i32 [[AND]]
 ;
   %shr2 = lshr i32 %x, 1
   %shl = shl i32 %shr2, 4
   %and = and i32 %shl, 16
   ret i32 %and
 }
 
 define <2 x i32> @test54_splat_vec(<2 x i32> %x) {
 ; CHECK-LABEL: @test54_splat_vec(
-; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i32> %x, <i32 3, i32 3>
-; CHECK-NEXT:    [[AND:%.*]] = and <2 x i32> [[TMP1]], <i32 16, i32 16>
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i32> %x, <i32 2, i32 2>
+; CHECK-NEXT:    [[AND:%.*]] = shl nuw nsw <2 x i32> [[TMP1]], <i32 3, i32 3>
 ; CHECK-NEXT:    ret <2 x i32> [[AND]]
 ;
   %shr2 = lshr <2 x i32> %x, <i32 1, i32 1>
   %shl = shl <2 x i32> %shr2, <i32 4, i32 4>
   %and = and <2 x i32> %shl, <i32 16, i32 16>
   ret <2 x i32> %and
 }