Reorder shuffle and binary operation.

[sepavloff]

Summary

This patch allows simplification:

BinOp(shuffle(v1), shuffle(v2)) -> shuffle(BinOp(v1, v2))

if both shuffles use the same mask, and both shuffle within a single vector.

[sepavloff]

Updated patch, added new pattern.

With this patch instcombiner tries making transformation like:

BinOp(shuffle(v1), const1) -> shuffle(BinOp(V1, const2))

This reordering allows removal of extra shuffles, for instance the code:

%t1 = shufflevector <4 x i32> %v, <4 x i32> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>
%t2 = mul <4 x i32> %t1, %t1
%r = shufflevector <4 x i32> %t2, <4 x i32> undef, <4 x i32> <i32 3, i32 2, i32 1, i32 0>

transforms to:

%1 = mul <4 x i32> %v, %v

[bkramer]

lib/Transforms/InstCombine/InstructionCombining.cpp

1125–1131

This could be

std::equal(LHSMask.begin(), LHSMask.end(), RHSMask.begin())

1143–1148

If you have a binary operator with a shuffle and a constant, the constant will always be canonicalized to the RHS.

[sepavloff]

Updated patch

[sepavloff]

Thank you for feedback!

lib/Transforms/InstCombine/InstructionCombining.cpp

1125–1131

Indeed. Replaced.

1143–1148

This transformation should also be applicable to non-commutative operations such as div, sub.

[bkramer]

I think this is good now. Adding nadav to make sure I didn't miss some shufflevector lowering issue.

[sepavloff]

Thank you for review!
Waiting nadav's opinion.

--Serge

2014-05-10 0:42 GMT+07:00 Benjamin Kramer <[e-mail]>:

I think this is good now. Adding nadav to make sure I didn't miss some
shufflevector lowering issue.

http://reviews.llvm.org/D3525

[andreadb]

lib/Transforms/InstCombine/InstructionCombining.cpp

1123–1125

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of the two shuffle masks?

As far as I understand, the shuffle mask (third operand of a ShuffleVectorInst) is always a Constant; therefore, you should be able to check if two masks are equal by simply comparing their addresses. I expect that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() == cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent constants will always have the same address". Also, "The shuffle mask operand is required to be a constant vector with either constant integer or undef values".

I hope this helps.

[nadav]

I did not review the code carefully but I think it looks fine. We are not generating new shuffle masks so there should not be any lowering problems.

[sepavloff]

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio <[e-mail]>:

Comment at: lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
@@ +1122,5 @@
+ isa<UndefValue>(RShuf->getOperand(1))) {
+ SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+ SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+ if (std::equal(LHSMask.begin(), LHSMask.end(), RHSMask.begin())) {
+ BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,

LShuf->getOperand(0),

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of the two
shuffle masks?

As far as I understand, the shuffle mask (third operand of a
ShuffleVectorInst) is always a Constant; therefore, you should be able to
check if two masks are equal by simply comparing their addresses. I expect
that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() ==
cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent
constants will always have the same address". Also, "The shuffle mask
operand is required to be a constant vector with either constant integer or
undef values".

I hope this helps.

http://reviews.llvm.org/D3525

[• HaoLiu]

Hi Serge,

It seems that your patch introduces a bug when two shuffles have different
operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Serge Pavlov
Sent: Sunday, May 11, 2014 4:42 PM
To: [e-mail]; [e-mail]; [e-mail];
[e-mail]
Cc: [e-mail]
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
<[e-mail]>:

Comment at:
lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
@@ +1122,5 @@
+ isa<UndefValue>(RShuf->getOperand(1))) {
+ SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+ SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+ if (std::equal(LHSMask.begin(), LHSMask.end(), RHSMask.begin()))

{

+ BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,

LShuf->getOperand(0),

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of the
two shuffle masks?

As far as I understand, the shuffle mask (third operand of a
ShuffleVectorInst) is always a Constant; therefore, you should be able
to check if two masks are equal by simply comparing their addresses. I
expect that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() ==
cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent
constants will always have the same address". Also, "The shuffle mask
operand is required to be a constant vector with either constant
integer or undef values".

I hope this helps.

http://reviews.llvm.org/D3525

http://reviews.llvm.org/D3525

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[sepavloff]

Thank you for catching that.
In the revision 208518 this problem must be fixed.

[• HaoLiu]

Hi Serge,

It seems there is another bug. Also see http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

[• HaoLiu]

Hi Serge,

It seems that there is another bug http://llvm.org/bugs/show_bug.cgi?id=19730.
When two shuffles have different types and the same mask, there may be an assertion failure.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Hao Liu
Sent: Monday, May 12, 2014 11:20 AM
To: [e-mail];
[e-mail]; [e-mail]; [e-mail]
Cc: [e-mail]
Subject: RE: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

It seems that your patch introduces a bug when two shuffles have different
operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Serge Pavlov
Sent: Sunday, May 11, 2014 4:42 PM
To: [e-mail]; [e-mail]; [e-mail];
[e-mail]
Cc: [e-mail]
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
<[e-mail]>:

Comment at:
lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
@@ +1122,5 @@
+ isa<UndefValue>(RShuf->getOperand(1))) {
+ SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+ SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+ if (std::equal(LHSMask.begin(), LHSMask.end(),
+ RHSMask.begin()))

{

+ BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,

LShuf->getOperand(0),

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of
the two shuffle masks?

As far as I understand, the shuffle mask (third operand of a
ShuffleVectorInst) is always a Constant; therefore, you should be
able to check if two masks are equal by simply comparing their
addresses. I expect that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() ==
cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent
constants will always have the same address". Also, "The shuffle
mask operand is required to be a constant vector with either
constant integer or undef values".

I hope this helps.

http://reviews.llvm.org/D3525

http://reviews.llvm.org/D3525

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

• IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.

ARM Limited, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2557590
ARM Holdings plc, Registered office 110 Fulbourn Road, Cambridge CB1 9NJ, Registered in England & Wales, Company No: 2548782

[• HaoLiu]

Hi Serge,

Sorry to bother you again.
It seems there is still a bug http://llvm.org/bugs/show_bug.cgi?id=19737
when creating binary operator.
I've looked at your code. Except this minor bug, your patch may not have any
other problems.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Hao Liu
Sent: Monday, May 12, 2014 11:20 AM
To: [e-mail];
[e-mail]; [e-mail]; [e-mail]
Cc: [e-mail]
Subject: RE: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

It seems that your patch introduces a bug when two shuffles have different
operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Serge Pavlov
Sent: Sunday, May 11, 2014 4:42 PM
To: [e-mail]; [e-mail]; [e-mail];
[e-mail]
Cc: [e-mail]
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
<[e-mail]>:

Comment at:
lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
@@ +1122,5 @@
+ isa<UndefValue>(RShuf->getOperand(1))) {
+ SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+ SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+ if (std::equal(LHSMask.begin(), LHSMask.end(),
+ RHSMask.begin()))

{

+ BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,

LShuf->getOperand(0),

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of
the two shuffle masks?

As far as I understand, the shuffle mask (third operand of a
ShuffleVectorInst) is always a Constant; therefore, you should be
able to check if two masks are equal by simply comparing their
addresses. I expect that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() ==
cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent
constants will always have the same address". Also, "The shuffle
mask operand is required to be a constant vector with either
constant integer or undef values".

I hope this helps.

http://reviews.llvm.org/D3525

http://reviews.llvm.org/D3525

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[jmolloy]

Hi Serge,

This patch has been breaking our internal builders since Sunday - it breaks
all random vector intrinsics tests.

Thanks for responding so quickly to the first reported bug but we've had one
outstanding since Monday morning. As it is now Wednesday, I think unless you
can address this soon we should start thinking about reverting this change
until you fix it.

Do you have any idea when you could get around to it?

Cheers,

James

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Hao Liu
Sent: 14 May 2014 07:30
To: [e-mail]; [e-mail]; [e-mail];
[e-mail]
Cc: [e-mail]
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

Sorry to bother you again.
It seems there is still a bug http://llvm.org/bugs/show_bug.cgi?id=19737
when creating binary operator.
I've looked at your code. Except this minor bug, your patch may not have

any

other problems.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Hao Liu
Sent: Monday, May 12, 2014 11:20 AM
To: [e-mail];
[e-mail]; [e-mail]; [e-mail]
Cc: [e-mail]
Subject: RE: [PATCH] Reorder shuffle and binary operation.

Hi Serge,

It seems that your patch introduces a bug when two shuffles have

different

operand types.
See more details in http://llvm.org/bugs/show_bug.cgi?id=19717.

Thanks,
-Hao

-----Original Message-----
From: [e-mail] [mailto:llvm-commits-
[e-mail]] On Behalf Of Serge Pavlov
Sent: Sunday, May 11, 2014 4:42 PM
To: [e-mail]; [e-mail];

[e-mail];

[e-mail]
Cc: [e-mail]
Subject: Re: [PATCH] Reorder shuffle and binary operation.

Thank you for advice and detailed explanation!
I updated the patch according your recommendation.

--Serge

2014-05-10 1:17 GMT+07:00 Andrea Di Biagio
<[e-mail]>:

Comment at:
lib/Transforms/InstCombine/InstructionCombining.cpp:1123-1125
@@ +1122,5 @@
+ isa<UndefValue>(RShuf->getOperand(1))) {
+ SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+ SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+ if (std::equal(LHSMask.begin(), LHSMask.end(),
+ RHSMask.begin()))

{

+ BinaryOperator *NewBO = CreateBinOpAsGiven(Inst,

LShuf->getOperand(0),

I might be wrong but,
wouldn't be easier in this case to simply compare the addresses of
the two shuffle masks?

As far as I understand, the shuffle mask (third operand of a
ShuffleVectorInst) is always a Constant; therefore, you should be
able to check if two masks are equal by simply comparing their
addresses. I expect that something like this should work:

cast<ShuffleVectorInst>(LHS)->getMask() ==
cast<ShuffleVectorInst>(RHS)->getMask().

quoting what is written in Constant.h, "two structurally equivalent
constants will always have the same address". Also, "The shuffle
mask operand is required to be a constant vector with either
constant integer or undef values".

I hope this helps.

http://reviews.llvm.org/D3525

http://reviews.llvm.org/D3525

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

http://reviews.llvm.org/D3525

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[sepavloff]

Hi James,

I regret that the fix makes you troubles. Nor llvm tests neither test-suit discovered any problems, you have a nice test suit and I am thankful to Hao for providing test cases. All reported problems were resolved in < 4 hours, did you reported the problem that is outstanding since Monday morning?

Thanks,
--Serge

[sepavloff]

Closed by commit rL208488 (authored by @sepavloff).

lib/Transforms/InstCombine/InstCombine.h

private:
   /// SimplifyDemandedInstructionBits - Inst is an integer instruction that
   /// SimplifyDemandedBits knows about.  See if the instruction has any
   /// properties that allow us to simplify its operands.
   bool SimplifyDemandedInstructionBits(Instruction &Inst);
 
   Value *SimplifyDemandedVectorElts(Value *V, APInt DemandedElts,
                                     APInt& UndefElts, unsigned Depth = 0);
 
+  Value *SimplifyVectorOp(BinaryOperator &Inst);
+
   // FoldOpIntoPhi - Given a binary operator, cast instruction, or select
   // which has a PHI node as operand #0, see if we can fold the instruction
   // into the PHI (which is only possible if all operands to the PHI are
   // constants).
   //
   Instruction *FoldOpIntoPhi(Instruction &I);
 
   // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"

lib/Transforms/InstCombine/InstCombineAddSub.cpp

bool InstCombiner::WillNotOverflowSignedAdd(Value *LHS, Value *RHS) {
 
   return false;
 }
 
 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
                                  I.hasNoUnsignedWrap(), DL))
     return ReplaceInstUsesWith(I, V);
 
   // (A*B)+(A*C) -> A*(B+C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombiner::visitFAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyFAddInst(LHS, RHS, I.getFastMathFlags(), DL))
     return ReplaceInstUsesWith(I, V);
 
   if (isa<Constant>(RHS)) {
     if (isa<PHINode>(LHS))
       if (Instruction *NV = FoldOpIntoPhi(I))
         return NV;
 
Value *InstCombiner::OptimizePointerDifference(Value *LHS, Value *RHS,
 
   return Builder->CreateIntCast(Result, Ty, true);
 }
 
 
 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifySubInst(Op0, Op1, I.hasNoSignedWrap(),
                                  I.hasNoUnsignedWrap(), DL))
     return ReplaceInstUsesWith(I, V);
 
   // (A*B)-(A*C) -> A*(B-C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
Instruction *InstCombiner::visitSub(BinaryOperator &I) {
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitFSub(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyFSubInst(Op0, Op1, I.getFastMathFlags(), DL))
     return ReplaceInstUsesWith(I, V);
 
   if (isa<Constant>(Op0))
     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
       if (Instruction *NV = FoldOpIntoSelect(I, SI))
         return NV;
 

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Value *InstCombiner::FoldAndOfFCmps(FCmpInst *LHS, FCmpInst *RHS) {
   return nullptr;
 }
 
 
 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyAndInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // (A|B)&(A|C) -> A|(B&C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
   // See if we can simplify any instructions used by the instruction whose sole
Instruction *InstCombiner::FoldOrWithConstants(BinaryOperator &I, Value *Op,
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyOrInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // (A&B)|(A&C) -> A&(B|C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
   // See if we can simplify any instructions used by the instruction whose sole
Instruction *InstCombiner::visitOr(BinaryOperator &I) {
 
   return Changed ? &I : nullptr;
 }
 
 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyXorInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // (A&B)^(A&C) -> A&(B^C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
   // See if we can simplify any instructions used by the instruction whose sole

lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

static Constant *getLogBase2Vector(ConstantDataVector *CV) {
 
   return ConstantVector::get(Elts);
 }
 
 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyMulInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return ReplaceInstUsesWith(I, V);
 
   if (match(Op1, m_AllOnes()))  // X * -1 == 0 - X
     return BinaryOperator::CreateNeg(Op0, I.getName());
Value *InstCombiner::foldFMulConst(Instruction *FMulOrDiv, Constant *C,
 
   return R;
 }
 
 Instruction *InstCombiner::visitFMul(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (isa<Constant>(Op0))
     std::swap(Op0, Op1);
 
   if (Value *V = SimplifyFMulInst(Op0, Op1, I.getFastMathFlags(), DL))
     return ReplaceInstUsesWith(I, V);
 
   bool AllowReassociate = I.hasUnsafeAlgebra();
 
if (size_t LHSIdx = visitUDivOperand(Op0, SI->getOperand(1), I, Actions))
       }
 
   return 0;
 }
 
 Instruction *InstCombiner::visitUDiv(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyUDivInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // Handle the integer div common cases
   if (Instruction *Common = commonIDivTransforms(I))
     return Common;
 
   // (x lshr C1) udiv C2 --> x udiv (C2 << C1)
if (visitUDivOperand(Op0, Op1, I, UDivActions))
     }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSDiv(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifySDivInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // Handle the integer div common cases
   if (Instruction *Common = commonIDivTransforms(I))
     return Common;
 
   // sdiv X, -1 == -X
static Instruction *CvtFDivConstToReciprocal(Value *Dividend,
   ConstantFP *R;
   R = ConstantFP::get(Dividend->getType()->getContext(), Reciprocal);
   return BinaryOperator::CreateFMul(Dividend, R);
 }
 
 Instruction *InstCombiner::visitFDiv(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyFDivInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   if (isa<Constant>(Op0))
     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
       if (Instruction *R = FoldOpIntoSelect(I, SI))
         return R;
 
Instruction *InstCombiner::commonIRemTransforms(BinaryOperator &I) {
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitURem(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyURemInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   if (Instruction *common = commonIRemTransforms(I))
     return common;
 
   // (zext A) urem (zext B) --> zext (A urem B)
   if (ZExtInst *ZOp0 = dyn_cast<ZExtInst>(Op0))
Instruction *InstCombiner::visitURem(BinaryOperator &I) {
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifySRemInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // Handle the integer rem common cases
   if (Instruction *Common = commonIRemTransforms(I))
     return Common;
 
   if (Value *RHSNeg = dyn_castNegVal(Op1))
Instruction *InstCombiner::visitSRem(BinaryOperator &I) {
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitFRem(BinaryOperator &I) {
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyFRemInst(Op0, Op1, DL))
     return ReplaceInstUsesWith(I, V);
 
   // Handle cases involving: rem X, (select Cond, Y, Z)
   if (isa<SelectInst>(Op1) && SimplifyDivRemOfSelect(I))
     return &I;
 
   return nullptr;
 }

lib/Transforms/InstCombine/InstCombineShifts.cpp

if (ShiftAmt1 == ShiftAmt2) {
         }
       }
     }
   }
   return nullptr;
 }
 
 Instruction *InstCombiner::visitShl(BinaryOperator &I) {
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyShlInst(I.getOperand(0), I.getOperand(1),
                                  I.hasNoSignedWrap(), I.hasNoUnsignedWrap(),
                                  DL))
     return ReplaceInstUsesWith(I, V);
 
   if (Instruction *V = commonShiftTransforms(I))
     return V;
 
Instruction *InstCombiner::visitShl(BinaryOperator &I) {
   if (match(I.getOperand(0), m_OneUse(m_Shl(m_Constant(C1), m_Value(A)))) &&
       match(I.getOperand(1), m_Constant(C2)))
     return BinaryOperator::CreateShl(ConstantExpr::getShl(C1, C2), A);
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitLShr(BinaryOperator &I) {
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyLShrInst(I.getOperand(0), I.getOperand(1),
                                   I.isExact(), DL))
     return ReplaceInstUsesWith(I, V);
 
   if (Instruction *R = commonShiftTransforms(I))
     return R;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
if (!I.isExact() &&
       return &I;
     }
   }
 
   return nullptr;
 }
 
 Instruction *InstCombiner::visitAShr(BinaryOperator &I) {
+  if (Value *V = SimplifyVectorOp(I))
+    return ReplaceInstUsesWith(I, V);
+
   if (Value *V = SimplifyAShrInst(I.getOperand(0), I.getOperand(1),
                                   I.isExact(), DL))
     return ReplaceInstUsesWith(I, V);
 
   if (Instruction *R = commonShiftTransforms(I))
     return R;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);

lib/Transforms/InstCombine/InstCombineVectorOps.cpp

case Instruction::InsertElement: {
       Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
       return InsertElementInst::Create(V, I->getOperand(1),
                                        Builder->getInt32(Index), "", I);
     }
   }
   llvm_unreachable("failed to reorder elements of vector instruction!");
 }
 
+static void RecognizeIdentityMask(const SmallVectorImpl<int> &Mask,
+                                  bool &isLHSID, bool &isRHSID) {
+  isLHSID = isRHSID = true;
+
+  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
+    if (Mask[i] < 0) continue;  // Ignore undef values.
+    // Is this an identity shuffle of the LHS value?
+    isLHSID &= (Mask[i] == (int)i);
+
+    // Is this an identity shuffle of the RHS value?
+    isRHSID &= (Mask[i]-e == i);
+  }
+}
+
 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
   Value *LHS = SVI.getOperand(0);
   Value *RHS = SVI.getOperand(1);
   SmallVector<int, 16> Mask = SVI.getShuffleMask();
 
   bool MadeChange = false;
 
   // Undefined shuffle mask -> undefined value.
if (LHS == RHS || isa<UndefValue>(LHS)) {
     SVI.setOperand(2, ConstantVector::get(Elts));
     LHS = SVI.getOperand(0);
     RHS = SVI.getOperand(1);
     MadeChange = true;
   }
 
   if (VWidth == LHSWidth) {
     // Analyze the shuffle, are the LHS or RHS and identity shuffles?
-    bool isLHSID = true, isRHSID = true;
-
-    for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
-      if (Mask[i] < 0) continue;  // Ignore undef values.
-      // Is this an identity shuffle of the LHS value?
-      isLHSID &= (Mask[i] == (int)i);
-
-      // Is this an identity shuffle of the RHS value?
-      isRHSID &= (Mask[i]-e == i);
-    }
+    bool isLHSID, isRHSID;
+    RecognizeIdentityMask(Mask, isLHSID, isRHSID);
 
     // Eliminate identity shuffles.
     if (isLHSID) return ReplaceInstUsesWith(SVI, LHS);
     if (isRHSID) return ReplaceInstUsesWith(SVI, RHS);
   }
 
   if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
     Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
         Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
       }
     }
     if (!newRHS)
       newRHS = UndefValue::get(newLHS->getType());
     return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
   }
 
+  // If the result mask is an identity, replace uses of this instruction with
+  // corresponding argument.
+  if (VWidth == LHSWidth) {
+    bool isLHSID, isRHSID;
+    RecognizeIdentityMask(newMask, isLHSID, isRHSID);
+    if (isLHSID) return ReplaceInstUsesWith(SVI, newLHS);
+    if (isRHSID) return ReplaceInstUsesWith(SVI, newRHS);
+  }
+
   return MadeChange ? &SVI : nullptr;
 }

lib/Transforms/InstCombine/InstructionCombining.cpp

if (Ancestor == Val)
       return Val;
 
     // Move up one level in the expression.
     assert(Ancestor->hasOneUse() && "Drilled down when more than one use!");
     Ancestor = Ancestor->user_back();
   } while (1);
 }
 
+/// \brief Makes transformation of binary operation specific for vector types.
+/// \param Inst Binary operator to transform.
+/// \return Pointer to node that must replace the original binary operator, or
+///         null pointer if no transformation was made.
+Value *InstCombiner::SimplifyVectorOp(BinaryOperator &Inst) {
+  if (!Inst.getType()->isVectorTy()) return nullptr;
+  unsigned VWidth = cast<VectorType>(Inst.getType())->getNumElements();
+  Value *LHS = Inst.getOperand(0), *RHS = Inst.getOperand(1);
+  assert(cast<VectorType>(LHS->getType())->getNumElements() == VWidth);
+  assert(cast<VectorType>(RHS->getType())->getNumElements() == VWidth);
+
+  // If both arguments of binary operation are shuffles, which use the same
+  // mask and shuffle within a single vector, it is worthwhile to move the
+  // shuffle after binary operation:
+  //   Op(shuffle(v1, m), shuffle(v2, m)) -> shuffle(Op(v1, v2), m)
+  if (isa<ShuffleVectorInst>(LHS) && isa<ShuffleVectorInst>(RHS)) {
+    ShuffleVectorInst *LShuf = cast<ShuffleVectorInst>(LHS);
+    ShuffleVectorInst *RShuf = cast<ShuffleVectorInst>(RHS);
+    if (isa<UndefValue>(LShuf->getOperand(1)) &&
+        isa<UndefValue>(RShuf->getOperand(1))) {
+      SmallVector<int, 16> LHSMask = LShuf->getShuffleMask();
+      SmallVector<int, 16> RHSMask = RShuf->getShuffleMask();
+      bool MasksEqual = true;
+      for (unsigned I = 0; I < VWidth; ++I)
+        if (LHSMask[I] != RHSMask[I]) {
+          MasksEqual = false;
+          break;
+        }
+      if (MasksEqual) {
+        BinaryOperator *NewBO = cast<BinaryOperator>(
+            Builder->CreateBinOp(Inst.getOpcode(), LShuf->getOperand(0),
+            RShuf->getOperand(0)));
+        if (isa<OverflowingBinaryOperator>(NewBO)) {
+          NewBO->setHasNoSignedWrap(Inst.hasNoSignedWrap());
+          NewBO->setHasNoUnsignedWrap(Inst.hasNoUnsignedWrap());
+        }
+        Value *Res = Builder->CreateShuffleVector(NewBO,
+            UndefValue::get(Inst.getType()), LShuf->getMask());
+        return Res;
+      }
+    }
+  }
+  return nullptr;
+}
+
 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
   SmallVector<Value*, 8> Ops(GEP.op_begin(), GEP.op_end());
 
   if (Value *V = SimplifyGEPInst(Ops, DL))
     return ReplaceInstUsesWith(GEP, V);
 
   Value *PtrOp = GEP.getOperand(0);
 
   // Eliminate unneeded casts for indices, and replace indices which displace
   // by multiples of a zero size type with zero.
   if (DL) {
     bool MadeChange = false;
     Type *IntPtrTy = DL->getIntPtrType(GEP.getPointerOperandType());
 
     gep_type_iterator GTI = gep_type_begin(GEP);
     for (User::op_iterator I = GEP.op_begin() + 1, E = GEP.op_end();
          I != E; ++I, ++GTI) {
       // Skip indices into struct types.
       SequentialType *SeqTy = dyn_cast<SequentialType>(*GTI);
       if (!SeqTy) continue;
 
       // If the element type has zero size then any index over it is equivalent
       // to an index of zero, so replace it with zero if it is not zero already.
       if (SeqTy->getElementType()->isSized() &&
           DL->getTypeAllocSize(SeqTy->getElementType()) == 0)
         if (!isa<Constant>(*I) || !cast<Constant>(*I)->isNullValue()) {

test/Transforms/InstCombine/vec_shuffle.ll

 
 define <4 x i8> @test16b(i8 %ele) {
 ; CHECK-LABEL: @test16b(
 ; CHECK-NEXT: ret <4 x i8> <i8 2, i8 2, i8 2, i8 2>
   %tmp0 = insertelement <8 x i8> <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 undef, i8 1>, i8 %ele, i32 6
   %tmp1 = shl <8 x i8> %tmp0, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>
   %tmp2 = shufflevector <8 x i8> %tmp1, <8 x i8> undef, <4 x i32> <i32 1, i32 2, i32 3, i32 4>
   ret <4 x i8> %tmp2
-}
+}
+
+; If composition of two shuffles is identity, shuffles can be removed.
+define <4 x i32> @shuffle_17ident(<4 x i32> %v) nounwind uwtable {
+; CHECK-LABEL: @shuffle_17ident(
+; CHECK-NOT: shufflevector
+  %shuffle = shufflevector <4 x i32> %v, <4 x i32> zeroinitializer,
+                           <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %shuffle2 = shufflevector <4 x i32> %shuffle, <4 x i32> zeroinitializer,
+                            <4 x i32> <i32 3, i32 0, i32 1, i32 2>
+  ret <4 x i32> %shuffle2
+}
+
+; swizzle can be put after operation
+define <4 x i32> @shuffle_17and(<4 x i32> %v1, <4 x i32> %v2) nounwind uwtable {
+; CHECK-LABEL: @shuffle_17and(
+; CHECK-NOT: shufflevector
+; CHECK: and <4 x i32> %v1, %v2
+; CHECK: shufflevector
+  %t1 = shufflevector <4 x i32> %v1, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %t2 = shufflevector <4 x i32> %v2, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %r = and <4 x i32> %t1, %t2
+  ret <4 x i32> %r
+}
+
+define <4 x i32> @shuffle_17add(<4 x i32> %v1, <4 x i32> %v2) nounwind uwtable {
+; CHECK-LABEL: @shuffle_17add(
+; CHECK-NOT: shufflevector
+; CHECK: add <4 x i32> %v1, %v2
+; CHECK: shufflevector
+  %t1 = shufflevector <4 x i32> %v1, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %t2 = shufflevector <4 x i32> %v2, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %r = add <4 x i32> %t1, %t2
+  ret <4 x i32> %r
+}
+
+define <4 x i32> @shuffle_17addnsw(<4 x i32> %v1, <4 x i32> %v2) nounwind uwtable {
+; CHECK-LABEL: @shuffle_17addnsw(
+; CHECK-NOT: shufflevector
+; CHECK: add nsw <4 x i32> %v1, %v2
+; CHECK: shufflevector
+  %t1 = shufflevector <4 x i32> %v1, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %t2 = shufflevector <4 x i32> %v2, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %r = add nsw <4 x i32> %t1, %t2
+  ret <4 x i32> %r
+}
+
+define <4 x i32> @shuffle_17addnuw(<4 x i32> %v1, <4 x i32> %v2) nounwind uwtable {
+; CHECK-LABEL: @shuffle_17addnuw(
+; CHECK-NOT: shufflevector
+; CHECK: add nuw <4 x i32> %v1, %v2
+; CHECK: shufflevector
+  %t1 = shufflevector <4 x i32> %v1, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %t2 = shufflevector <4 x i32> %v2, <4 x i32> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %r = add nuw <4 x i32> %t1, %t2
+  ret <4 x i32> %r
+}
+
+define <4 x float> @shuffle_17fsub(<4 x float> %v1, <4 x float> %v2) nounwind uwtable {
+; CHECK-LABEL: @shuffle_17fsub(
+; CHECK-NOT: shufflevector
+; CHECK: fsub <4 x float> %v1, %v2
+; CHECK: shufflevector
+  %t1 = shufflevector <4 x float> %v1, <4 x float> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %t2 = shufflevector <4 x float> %v2, <4 x float> zeroinitializer,
+                      <4 x i32> <i32 1, i32 2, i32 3, i32 0>
+  %r = fsub <4 x float> %t1, %t2
+  ret <4 x float> %r
+}

test/Transforms/LoopVectorize/store-shuffle-bug.ll

 ; a shuffle too many.
 
 define void @t()  {
 entry:
   br label %for.body
 
 ; CHECK-LABEL: @t(
 ; CHECK: vector.body:
-; CHECK: load <4 x i32>
-; CHECK: [[VAR1:%[a-zA-Z0-9]+]] = shufflevector
-; CHECK: load <4 x i32>
-; CHECK: [[VAR2:%[a-zA-Z0-9]+]] = shufflevector
+; CHECK: [[VAR1:%[a-zA-Z0-9.]+]] = load <4 x i32>
+; CHECK: [[VAR2:%[a-zA-Z0-9.]+]] = load <4 x i32>
 ; CHECK: [[VAR3:%[a-zA-Z0-9]+]] = add nsw <4 x i32> [[VAR2]], [[VAR1]]
-; CHECK: [[VAR4:%[a-zA-Z0-9]+]] = shufflevector <4 x i32> [[VAR3]]
-; CHECK: store <4 x i32> [[VAR4]]
-; CHECK: load <4 x i32>
-; CHECK: [[VAR5:%[a-zA-Z0-9]+]] = shufflevector
-; CHECK-NOT: add nsw <4 x i32> [[VAR4]], [[VAR5]]
-; CHECK-NOT: add nsw <4 x i32> [[VAR5]], [[VAR4]]
-; CHECK: add nsw <4 x i32> [[VAR3]], [[VAR5]]
+; CHECK: store <4 x i32> [[VAR3]]
+; CHECK: [[VAR4:%[a-zA-Z0-9.]+]] = load <4 x i32>
+; CHECK: add nsw <4 x i32> [[VAR3]], [[VAR4]]
+; CHECK-NOT: shufflevector
 
 for.body:
   %indvars.iv = phi i64 [ 93, %entry ], [ %indvars.iv.next, %for.body ]
   %0 = add i64 %indvars.iv, 1
   %arrayidx = getelementptr inbounds [100 x i32]* @uf, i64 0, i64 %0
   %arrayidx3 = getelementptr inbounds [100 x i32]* @xi, i64 0, i64 %0
   %1 = load i32* %arrayidx3, align 4
   %2 = load i32* %arrayidx, align 4