xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp (revision 833a452e9f082a7982a31c21f0da437dbbe0a39d)
1 //===- InstCombineVectorOps.cpp -------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements instcombine for ExtractElement, InsertElement and
10 // ShuffleVector.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "InstCombineInternal.h"
15 #include "llvm/ADT/APInt.h"
16 #include "llvm/ADT/ArrayRef.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallBitVector.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/InstructionSimplify.h"
23 #include "llvm/Analysis/VectorUtils.h"
24 #include "llvm/IR/BasicBlock.h"
25 #include "llvm/IR/Constant.h"
26 #include "llvm/IR/Constants.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/InstrTypes.h"
29 #include "llvm/IR/Instruction.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/Operator.h"
32 #include "llvm/IR/PatternMatch.h"
33 #include "llvm/IR/Type.h"
34 #include "llvm/IR/User.h"
35 #include "llvm/IR/Value.h"
36 #include "llvm/Support/Casting.h"
37 #include "llvm/Support/ErrorHandling.h"
38 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
39 #include "llvm/Transforms/InstCombine/InstCombiner.h"
40 #include <cassert>
41 #include <cstdint>
42 #include <iterator>
43 #include <utility>
44 
45 using namespace llvm;
46 using namespace PatternMatch;
47 
48 #define DEBUG_TYPE "instcombine"
49 
50 STATISTIC(NumAggregateReconstructionsSimplified,
51           "Number of aggregate reconstructions turned into reuse of the "
52           "original aggregate");
53 
54 /// Return true if the value is cheaper to scalarize than it is to leave as a
55 /// vector operation. IsConstantExtractIndex indicates whether we are extracting
56 /// one known element from a vector constant.
57 ///
58 /// FIXME: It's possible to create more instructions than previously existed.
59 static bool cheapToScalarize(Value *V, bool IsConstantExtractIndex) {
60   // If we can pick a scalar constant value out of a vector, that is free.
61   if (auto *C = dyn_cast<Constant>(V))
62     return IsConstantExtractIndex || C->getSplatValue();
63 
64   // An insertelement to the same constant index as our extract will simplify
65   // to the scalar inserted element. An insertelement to a different constant
66   // index is irrelevant to our extract.
67   if (match(V, m_InsertElt(m_Value(), m_Value(), m_ConstantInt())))
68     return IsConstantExtractIndex;
69 
70   if (match(V, m_OneUse(m_Load(m_Value()))))
71     return true;
72 
73   if (match(V, m_OneUse(m_UnOp())))
74     return true;
75 
76   Value *V0, *V1;
77   if (match(V, m_OneUse(m_BinOp(m_Value(V0), m_Value(V1)))))
78     if (cheapToScalarize(V0, IsConstantExtractIndex) ||
79         cheapToScalarize(V1, IsConstantExtractIndex))
80       return true;
81 
82   CmpInst::Predicate UnusedPred;
83   if (match(V, m_OneUse(m_Cmp(UnusedPred, m_Value(V0), m_Value(V1)))))
84     if (cheapToScalarize(V0, IsConstantExtractIndex) ||
85         cheapToScalarize(V1, IsConstantExtractIndex))
86       return true;
87 
88   return false;
89 }
90 
91 // If we have a PHI node with a vector type that is only used to feed
92 // itself and be an operand of extractelement at a constant location,
93 // try to replace the PHI of the vector type with a PHI of a scalar type.
94 Instruction *InstCombinerImpl::scalarizePHI(ExtractElementInst &EI,
95                                             PHINode *PN) {
96   SmallVector<Instruction *, 2> Extracts;
97   // The users we want the PHI to have are:
98   // 1) The EI ExtractElement (we already know this)
99   // 2) Possibly more ExtractElements with the same index.
100   // 3) Another operand, which will feed back into the PHI.
101   Instruction *PHIUser = nullptr;
102   for (auto U : PN->users()) {
103     if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
104       if (EI.getIndexOperand() == EU->getIndexOperand())
105         Extracts.push_back(EU);
106       else
107         return nullptr;
108     } else if (!PHIUser) {
109       PHIUser = cast<Instruction>(U);
110     } else {
111       return nullptr;
112     }
113   }
114 
115   if (!PHIUser)
116     return nullptr;
117 
118   // Verify that this PHI user has one use, which is the PHI itself,
119   // and that it is a binary operation which is cheap to scalarize.
120   // otherwise return nullptr.
121   if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
122       !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
123     return nullptr;
124 
125   // Create a scalar PHI node that will replace the vector PHI node
126   // just before the current PHI node.
127   PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
128       PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
129   // Scalarize each PHI operand.
130   for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
131     Value *PHIInVal = PN->getIncomingValue(i);
132     BasicBlock *inBB = PN->getIncomingBlock(i);
133     Value *Elt = EI.getIndexOperand();
134     // If the operand is the PHI induction variable:
135     if (PHIInVal == PHIUser) {
136       // Scalarize the binary operation. Its first operand is the
137       // scalar PHI, and the second operand is extracted from the other
138       // vector operand.
139       BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
140       unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
141       Value *Op = InsertNewInstWith(
142           ExtractElementInst::Create(B0->getOperand(opId), Elt,
143                                      B0->getOperand(opId)->getName() + ".Elt"),
144           *B0);
145       Value *newPHIUser = InsertNewInstWith(
146           BinaryOperator::CreateWithCopiedFlags(B0->getOpcode(),
147                                                 scalarPHI, Op, B0), *B0);
148       scalarPHI->addIncoming(newPHIUser, inBB);
149     } else {
150       // Scalarize PHI input:
151       Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
152       // Insert the new instruction into the predecessor basic block.
153       Instruction *pos = dyn_cast<Instruction>(PHIInVal);
154       BasicBlock::iterator InsertPos;
155       if (pos && !isa<PHINode>(pos)) {
156         InsertPos = ++pos->getIterator();
157       } else {
158         InsertPos = inBB->getFirstInsertionPt();
159       }
160 
161       InsertNewInstWith(newEI, *InsertPos);
162 
163       scalarPHI->addIncoming(newEI, inBB);
164     }
165   }
166 
167   for (auto E : Extracts)
168     replaceInstUsesWith(*E, scalarPHI);
169 
170   return &EI;
171 }
172 
173 static Instruction *foldBitcastExtElt(ExtractElementInst &Ext,
174                                       InstCombiner::BuilderTy &Builder,
175                                       bool IsBigEndian) {
176   Value *X;
177   uint64_t ExtIndexC;
178   if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) ||
179       !X->getType()->isVectorTy() ||
180       !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC)))
181     return nullptr;
182 
183   // If this extractelement is using a bitcast from a vector of the same number
184   // of elements, see if we can find the source element from the source vector:
185   // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
186   auto *SrcTy = cast<VectorType>(X->getType());
187   Type *DestTy = Ext.getType();
188   ElementCount NumSrcElts = SrcTy->getElementCount();
189   ElementCount NumElts =
190       cast<VectorType>(Ext.getVectorOperandType())->getElementCount();
191   if (NumSrcElts == NumElts)
192     if (Value *Elt = findScalarElement(X, ExtIndexC))
193       return new BitCastInst(Elt, DestTy);
194 
195   assert(NumSrcElts.isScalable() == NumElts.isScalable() &&
196          "Src and Dst must be the same sort of vector type");
197 
198   // If the source elements are wider than the destination, try to shift and
199   // truncate a subset of scalar bits of an insert op.
200   if (NumSrcElts.getKnownMinValue() < NumElts.getKnownMinValue()) {
201     Value *Scalar;
202     uint64_t InsIndexC;
203     if (!match(X, m_InsertElt(m_Value(), m_Value(Scalar),
204                               m_ConstantInt(InsIndexC))))
205       return nullptr;
206 
207     // The extract must be from the subset of vector elements that we inserted
208     // into. Example: if we inserted element 1 of a <2 x i64> and we are
209     // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
210     // of elements 4-7 of the bitcasted vector.
211     unsigned NarrowingRatio =
212         NumElts.getKnownMinValue() / NumSrcElts.getKnownMinValue();
213     if (ExtIndexC / NarrowingRatio != InsIndexC)
214       return nullptr;
215 
216     // We are extracting part of the original scalar. How that scalar is
217     // inserted into the vector depends on the endian-ness. Example:
218     //              Vector Byte Elt Index:    0  1  2  3  4  5  6  7
219     //                                       +--+--+--+--+--+--+--+--+
220     // inselt <2 x i32> V, <i32> S, 1:       |V0|V1|V2|V3|S0|S1|S2|S3|
221     // extelt <4 x i16> V', 3:               |                 |S2|S3|
222     //                                       +--+--+--+--+--+--+--+--+
223     // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
224     // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
225     // In this example, we must right-shift little-endian. Big-endian is just a
226     // truncate.
227     unsigned Chunk = ExtIndexC % NarrowingRatio;
228     if (IsBigEndian)
229       Chunk = NarrowingRatio - 1 - Chunk;
230 
231     // Bail out if this is an FP vector to FP vector sequence. That would take
232     // more instructions than we started with unless there is no shift, and it
233     // may not be handled as well in the backend.
234     bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
235     bool NeedDestBitcast = DestTy->isFloatingPointTy();
236     if (NeedSrcBitcast && NeedDestBitcast)
237       return nullptr;
238 
239     unsigned SrcWidth = SrcTy->getScalarSizeInBits();
240     unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
241     unsigned ShAmt = Chunk * DestWidth;
242 
243     // TODO: This limitation is more strict than necessary. We could sum the
244     // number of new instructions and subtract the number eliminated to know if
245     // we can proceed.
246     if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
247       if (NeedSrcBitcast || NeedDestBitcast)
248         return nullptr;
249 
250     if (NeedSrcBitcast) {
251       Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth);
252       Scalar = Builder.CreateBitCast(Scalar, SrcIntTy);
253     }
254 
255     if (ShAmt) {
256       // Bail out if we could end with more instructions than we started with.
257       if (!Ext.getVectorOperand()->hasOneUse())
258         return nullptr;
259       Scalar = Builder.CreateLShr(Scalar, ShAmt);
260     }
261 
262     if (NeedDestBitcast) {
263       Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth);
264       return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy);
265     }
266     return new TruncInst(Scalar, DestTy);
267   }
268 
269   return nullptr;
270 }
271 
272 /// Find elements of V demanded by UserInstr.
273 static APInt findDemandedEltsBySingleUser(Value *V, Instruction *UserInstr) {
274   unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
275 
276   // Conservatively assume that all elements are needed.
277   APInt UsedElts(APInt::getAllOnesValue(VWidth));
278 
279   switch (UserInstr->getOpcode()) {
280   case Instruction::ExtractElement: {
281     ExtractElementInst *EEI = cast<ExtractElementInst>(UserInstr);
282     assert(EEI->getVectorOperand() == V);
283     ConstantInt *EEIIndexC = dyn_cast<ConstantInt>(EEI->getIndexOperand());
284     if (EEIIndexC && EEIIndexC->getValue().ult(VWidth)) {
285       UsedElts = APInt::getOneBitSet(VWidth, EEIIndexC->getZExtValue());
286     }
287     break;
288   }
289   case Instruction::ShuffleVector: {
290     ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(UserInstr);
291     unsigned MaskNumElts =
292         cast<FixedVectorType>(UserInstr->getType())->getNumElements();
293 
294     UsedElts = APInt(VWidth, 0);
295     for (unsigned i = 0; i < MaskNumElts; i++) {
296       unsigned MaskVal = Shuffle->getMaskValue(i);
297       if (MaskVal == -1u || MaskVal >= 2 * VWidth)
298         continue;
299       if (Shuffle->getOperand(0) == V && (MaskVal < VWidth))
300         UsedElts.setBit(MaskVal);
301       if (Shuffle->getOperand(1) == V &&
302           ((MaskVal >= VWidth) && (MaskVal < 2 * VWidth)))
303         UsedElts.setBit(MaskVal - VWidth);
304     }
305     break;
306   }
307   default:
308     break;
309   }
310   return UsedElts;
311 }
312 
313 /// Find union of elements of V demanded by all its users.
314 /// If it is known by querying findDemandedEltsBySingleUser that
315 /// no user demands an element of V, then the corresponding bit
316 /// remains unset in the returned value.
317 static APInt findDemandedEltsByAllUsers(Value *V) {
318   unsigned VWidth = cast<FixedVectorType>(V->getType())->getNumElements();
319 
320   APInt UnionUsedElts(VWidth, 0);
321   for (const Use &U : V->uses()) {
322     if (Instruction *I = dyn_cast<Instruction>(U.getUser())) {
323       UnionUsedElts |= findDemandedEltsBySingleUser(V, I);
324     } else {
325       UnionUsedElts = APInt::getAllOnesValue(VWidth);
326       break;
327     }
328 
329     if (UnionUsedElts.isAllOnesValue())
330       break;
331   }
332 
333   return UnionUsedElts;
334 }
335 
336 Instruction *InstCombinerImpl::visitExtractElementInst(ExtractElementInst &EI) {
337   Value *SrcVec = EI.getVectorOperand();
338   Value *Index = EI.getIndexOperand();
339   if (Value *V = SimplifyExtractElementInst(SrcVec, Index,
340                                             SQ.getWithInstruction(&EI)))
341     return replaceInstUsesWith(EI, V);
342 
343   // If extracting a specified index from the vector, see if we can recursively
344   // find a previously computed scalar that was inserted into the vector.
345   auto *IndexC = dyn_cast<ConstantInt>(Index);
346   if (IndexC) {
347     ElementCount EC = EI.getVectorOperandType()->getElementCount();
348     unsigned NumElts = EC.getKnownMinValue();
349 
350     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(SrcVec)) {
351       Intrinsic::ID IID = II->getIntrinsicID();
352       // Index needs to be lower than the minimum size of the vector, because
353       // for scalable vector, the vector size is known at run time.
354       if (IID == Intrinsic::experimental_stepvector &&
355           IndexC->getValue().ult(NumElts)) {
356         Type *Ty = EI.getType();
357         unsigned BitWidth = Ty->getIntegerBitWidth();
358         Value *Idx;
359         // Return index when its value does not exceed the allowed limit
360         // for the element type of the vector, otherwise return undefined.
361         if (IndexC->getValue().getActiveBits() <= BitWidth)
362           Idx = ConstantInt::get(Ty, IndexC->getValue().zextOrTrunc(BitWidth));
363         else
364           Idx = UndefValue::get(Ty);
365         return replaceInstUsesWith(EI, Idx);
366       }
367     }
368 
369     // InstSimplify should handle cases where the index is invalid.
370     // For fixed-length vector, it's invalid to extract out-of-range element.
371     if (!EC.isScalable() && IndexC->getValue().uge(NumElts))
372       return nullptr;
373 
374     // This instruction only demands the single element from the input vector.
375     // Skip for scalable type, the number of elements is unknown at
376     // compile-time.
377     if (!EC.isScalable() && NumElts != 1) {
378       // If the input vector has a single use, simplify it based on this use
379       // property.
380       if (SrcVec->hasOneUse()) {
381         APInt UndefElts(NumElts, 0);
382         APInt DemandedElts(NumElts, 0);
383         DemandedElts.setBit(IndexC->getZExtValue());
384         if (Value *V =
385                 SimplifyDemandedVectorElts(SrcVec, DemandedElts, UndefElts))
386           return replaceOperand(EI, 0, V);
387       } else {
388         // If the input vector has multiple uses, simplify it based on a union
389         // of all elements used.
390         APInt DemandedElts = findDemandedEltsByAllUsers(SrcVec);
391         if (!DemandedElts.isAllOnesValue()) {
392           APInt UndefElts(NumElts, 0);
393           if (Value *V = SimplifyDemandedVectorElts(
394                   SrcVec, DemandedElts, UndefElts, 0 /* Depth */,
395                   true /* AllowMultipleUsers */)) {
396             if (V != SrcVec) {
397               SrcVec->replaceAllUsesWith(V);
398               return &EI;
399             }
400           }
401         }
402       }
403     }
404 
405     if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
406       return I;
407 
408     // If there's a vector PHI feeding a scalar use through this extractelement
409     // instruction, try to scalarize the PHI.
410     if (auto *Phi = dyn_cast<PHINode>(SrcVec))
411       if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
412         return ScalarPHI;
413   }
414 
415   // TODO come up with a n-ary matcher that subsumes both unary and
416   // binary matchers.
417   UnaryOperator *UO;
418   if (match(SrcVec, m_UnOp(UO)) && cheapToScalarize(SrcVec, IndexC)) {
419     // extelt (unop X), Index --> unop (extelt X, Index)
420     Value *X = UO->getOperand(0);
421     Value *E = Builder.CreateExtractElement(X, Index);
422     return UnaryOperator::CreateWithCopiedFlags(UO->getOpcode(), E, UO);
423   }
424 
425   BinaryOperator *BO;
426   if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) {
427     // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
428     Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
429     Value *E0 = Builder.CreateExtractElement(X, Index);
430     Value *E1 = Builder.CreateExtractElement(Y, Index);
431     return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO);
432   }
433 
434   Value *X, *Y;
435   CmpInst::Predicate Pred;
436   if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) &&
437       cheapToScalarize(SrcVec, IndexC)) {
438     // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
439     Value *E0 = Builder.CreateExtractElement(X, Index);
440     Value *E1 = Builder.CreateExtractElement(Y, Index);
441     return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1);
442   }
443 
444   if (auto *I = dyn_cast<Instruction>(SrcVec)) {
445     if (auto *IE = dyn_cast<InsertElementInst>(I)) {
446       // Extracting the inserted element?
447       if (IE->getOperand(2) == Index)
448         return replaceInstUsesWith(EI, IE->getOperand(1));
449       // If the inserted and extracted elements are constants, they must not
450       // be the same value, extract from the pre-inserted value instead.
451       if (isa<Constant>(IE->getOperand(2)) && IndexC)
452         return replaceOperand(EI, 0, IE->getOperand(0));
453     } else if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
454       auto *VecType = cast<VectorType>(GEP->getType());
455       ElementCount EC = VecType->getElementCount();
456       uint64_t IdxVal = IndexC ? IndexC->getZExtValue() : 0;
457       if (IndexC && IdxVal < EC.getKnownMinValue() && GEP->hasOneUse()) {
458         // Find out why we have a vector result - these are a few examples:
459         //  1. We have a scalar pointer and a vector of indices, or
460         //  2. We have a vector of pointers and a scalar index, or
461         //  3. We have a vector of pointers and a vector of indices, etc.
462         // Here we only consider combining when there is exactly one vector
463         // operand, since the optimization is less obviously a win due to
464         // needing more than one extractelements.
465 
466         unsigned VectorOps =
467             llvm::count_if(GEP->operands(), [](const Value *V) {
468               return isa<VectorType>(V->getType());
469             });
470         if (VectorOps > 1)
471           return nullptr;
472         assert(VectorOps == 1 && "Expected exactly one vector GEP operand!");
473 
474         Value *NewPtr = GEP->getPointerOperand();
475         if (isa<VectorType>(NewPtr->getType()))
476           NewPtr = Builder.CreateExtractElement(NewPtr, IndexC);
477 
478         SmallVector<Value *> NewOps;
479         for (unsigned I = 1; I != GEP->getNumOperands(); ++I) {
480           Value *Op = GEP->getOperand(I);
481           if (isa<VectorType>(Op->getType()))
482             NewOps.push_back(Builder.CreateExtractElement(Op, IndexC));
483           else
484             NewOps.push_back(Op);
485         }
486 
487         GetElementPtrInst *NewGEP = GetElementPtrInst::Create(
488             cast<PointerType>(NewPtr->getType())->getElementType(), NewPtr,
489             NewOps);
490         NewGEP->setIsInBounds(GEP->isInBounds());
491         return NewGEP;
492       }
493       return nullptr;
494     } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
495       // If this is extracting an element from a shufflevector, figure out where
496       // it came from and extract from the appropriate input element instead.
497       // Restrict the following transformation to fixed-length vector.
498       if (isa<FixedVectorType>(SVI->getType()) && isa<ConstantInt>(Index)) {
499         int SrcIdx =
500             SVI->getMaskValue(cast<ConstantInt>(Index)->getZExtValue());
501         Value *Src;
502         unsigned LHSWidth = cast<FixedVectorType>(SVI->getOperand(0)->getType())
503                                 ->getNumElements();
504 
505         if (SrcIdx < 0)
506           return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
507         if (SrcIdx < (int)LHSWidth)
508           Src = SVI->getOperand(0);
509         else {
510           SrcIdx -= LHSWidth;
511           Src = SVI->getOperand(1);
512         }
513         Type *Int32Ty = Type::getInt32Ty(EI.getContext());
514         return ExtractElementInst::Create(
515             Src, ConstantInt::get(Int32Ty, SrcIdx, false));
516       }
517     } else if (auto *CI = dyn_cast<CastInst>(I)) {
518       // Canonicalize extractelement(cast) -> cast(extractelement).
519       // Bitcasts can change the number of vector elements, and they cost
520       // nothing.
521       if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
522         Value *EE = Builder.CreateExtractElement(CI->getOperand(0), Index);
523         return CastInst::Create(CI->getOpcode(), EE, EI.getType());
524       }
525     }
526   }
527   return nullptr;
528 }
529 
530 /// If V is a shuffle of values that ONLY returns elements from either LHS or
531 /// RHS, return the shuffle mask and true. Otherwise, return false.
532 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
533                                          SmallVectorImpl<int> &Mask) {
534   assert(LHS->getType() == RHS->getType() &&
535          "Invalid CollectSingleShuffleElements");
536   unsigned NumElts = cast<FixedVectorType>(V->getType())->getNumElements();
537 
538   if (match(V, m_Undef())) {
539     Mask.assign(NumElts, -1);
540     return true;
541   }
542 
543   if (V == LHS) {
544     for (unsigned i = 0; i != NumElts; ++i)
545       Mask.push_back(i);
546     return true;
547   }
548 
549   if (V == RHS) {
550     for (unsigned i = 0; i != NumElts; ++i)
551       Mask.push_back(i + NumElts);
552     return true;
553   }
554 
555   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
556     // If this is an insert of an extract from some other vector, include it.
557     Value *VecOp    = IEI->getOperand(0);
558     Value *ScalarOp = IEI->getOperand(1);
559     Value *IdxOp    = IEI->getOperand(2);
560 
561     if (!isa<ConstantInt>(IdxOp))
562       return false;
563     unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
564 
565     if (isa<UndefValue>(ScalarOp)) {  // inserting undef into vector.
566       // We can handle this if the vector we are inserting into is
567       // transitively ok.
568       if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
569         // If so, update the mask to reflect the inserted undef.
570         Mask[InsertedIdx] = -1;
571         return true;
572       }
573     } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
574       if (isa<ConstantInt>(EI->getOperand(1))) {
575         unsigned ExtractedIdx =
576         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
577         unsigned NumLHSElts =
578             cast<FixedVectorType>(LHS->getType())->getNumElements();
579 
580         // This must be extracting from either LHS or RHS.
581         if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
582           // We can handle this if the vector we are inserting into is
583           // transitively ok.
584           if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
585             // If so, update the mask to reflect the inserted value.
586             if (EI->getOperand(0) == LHS) {
587               Mask[InsertedIdx % NumElts] = ExtractedIdx;
588             } else {
589               assert(EI->getOperand(0) == RHS);
590               Mask[InsertedIdx % NumElts] = ExtractedIdx + NumLHSElts;
591             }
592             return true;
593           }
594         }
595       }
596     }
597   }
598 
599   return false;
600 }
601 
602 /// If we have insertion into a vector that is wider than the vector that we
603 /// are extracting from, try to widen the source vector to allow a single
604 /// shufflevector to replace one or more insert/extract pairs.
605 static void replaceExtractElements(InsertElementInst *InsElt,
606                                    ExtractElementInst *ExtElt,
607                                    InstCombinerImpl &IC) {
608   auto *InsVecType = cast<FixedVectorType>(InsElt->getType());
609   auto *ExtVecType = cast<FixedVectorType>(ExtElt->getVectorOperandType());
610   unsigned NumInsElts = InsVecType->getNumElements();
611   unsigned NumExtElts = ExtVecType->getNumElements();
612 
613   // The inserted-to vector must be wider than the extracted-from vector.
614   if (InsVecType->getElementType() != ExtVecType->getElementType() ||
615       NumExtElts >= NumInsElts)
616     return;
617 
618   // Create a shuffle mask to widen the extended-from vector using poison
619   // values. The mask selects all of the values of the original vector followed
620   // by as many poison values as needed to create a vector of the same length
621   // as the inserted-to vector.
622   SmallVector<int, 16> ExtendMask;
623   for (unsigned i = 0; i < NumExtElts; ++i)
624     ExtendMask.push_back(i);
625   for (unsigned i = NumExtElts; i < NumInsElts; ++i)
626     ExtendMask.push_back(-1);
627 
628   Value *ExtVecOp = ExtElt->getVectorOperand();
629   auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
630   BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
631                                    ? ExtVecOpInst->getParent()
632                                    : ExtElt->getParent();
633 
634   // TODO: This restriction matches the basic block check below when creating
635   // new extractelement instructions. If that limitation is removed, this one
636   // could also be removed. But for now, we just bail out to ensure that we
637   // will replace the extractelement instruction that is feeding our
638   // insertelement instruction. This allows the insertelement to then be
639   // replaced by a shufflevector. If the insertelement is not replaced, we can
640   // induce infinite looping because there's an optimization for extractelement
641   // that will delete our widening shuffle. This would trigger another attempt
642   // here to create that shuffle, and we spin forever.
643   if (InsertionBlock != InsElt->getParent())
644     return;
645 
646   // TODO: This restriction matches the check in visitInsertElementInst() and
647   // prevents an infinite loop caused by not turning the extract/insert pair
648   // into a shuffle. We really should not need either check, but we're lacking
649   // folds for shufflevectors because we're afraid to generate shuffle masks
650   // that the backend can't handle.
651   if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
652     return;
653 
654   auto *WideVec =
655       new ShuffleVectorInst(ExtVecOp, PoisonValue::get(ExtVecType), ExtendMask);
656 
657   // Insert the new shuffle after the vector operand of the extract is defined
658   // (as long as it's not a PHI) or at the start of the basic block of the
659   // extract, so any subsequent extracts in the same basic block can use it.
660   // TODO: Insert before the earliest ExtractElementInst that is replaced.
661   if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
662     WideVec->insertAfter(ExtVecOpInst);
663   else
664     IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
665 
666   // Replace extracts from the original narrow vector with extracts from the new
667   // wide vector.
668   for (User *U : ExtVecOp->users()) {
669     ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U);
670     if (!OldExt || OldExt->getParent() != WideVec->getParent())
671       continue;
672     auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
673     NewExt->insertAfter(OldExt);
674     IC.replaceInstUsesWith(*OldExt, NewExt);
675   }
676 }
677 
678 /// We are building a shuffle to create V, which is a sequence of insertelement,
679 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
680 /// not rely on the second vector source. Return a std::pair containing the
681 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
682 /// parameter as required.
683 ///
684 /// Note: we intentionally don't try to fold earlier shuffles since they have
685 /// often been chosen carefully to be efficiently implementable on the target.
686 using ShuffleOps = std::pair<Value *, Value *>;
687 
688 static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl<int> &Mask,
689                                          Value *PermittedRHS,
690                                          InstCombinerImpl &IC) {
691   assert(V->getType()->isVectorTy() && "Invalid shuffle!");
692   unsigned NumElts = cast<FixedVectorType>(V->getType())->getNumElements();
693 
694   if (match(V, m_Undef())) {
695     Mask.assign(NumElts, -1);
696     return std::make_pair(
697         PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
698   }
699 
700   if (isa<ConstantAggregateZero>(V)) {
701     Mask.assign(NumElts, 0);
702     return std::make_pair(V, nullptr);
703   }
704 
705   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
706     // If this is an insert of an extract from some other vector, include it.
707     Value *VecOp    = IEI->getOperand(0);
708     Value *ScalarOp = IEI->getOperand(1);
709     Value *IdxOp    = IEI->getOperand(2);
710 
711     if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
712       if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
713         unsigned ExtractedIdx =
714           cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
715         unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
716 
717         // Either the extracted from or inserted into vector must be RHSVec,
718         // otherwise we'd end up with a shuffle of three inputs.
719         if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
720           Value *RHS = EI->getOperand(0);
721           ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
722           assert(LR.second == nullptr || LR.second == RHS);
723 
724           if (LR.first->getType() != RHS->getType()) {
725             // Although we are giving up for now, see if we can create extracts
726             // that match the inserts for another round of combining.
727             replaceExtractElements(IEI, EI, IC);
728 
729             // We tried our best, but we can't find anything compatible with RHS
730             // further up the chain. Return a trivial shuffle.
731             for (unsigned i = 0; i < NumElts; ++i)
732               Mask[i] = i;
733             return std::make_pair(V, nullptr);
734           }
735 
736           unsigned NumLHSElts =
737               cast<FixedVectorType>(RHS->getType())->getNumElements();
738           Mask[InsertedIdx % NumElts] = NumLHSElts + ExtractedIdx;
739           return std::make_pair(LR.first, RHS);
740         }
741 
742         if (VecOp == PermittedRHS) {
743           // We've gone as far as we can: anything on the other side of the
744           // extractelement will already have been converted into a shuffle.
745           unsigned NumLHSElts =
746               cast<FixedVectorType>(EI->getOperand(0)->getType())
747                   ->getNumElements();
748           for (unsigned i = 0; i != NumElts; ++i)
749             Mask.push_back(i == InsertedIdx ? ExtractedIdx : NumLHSElts + i);
750           return std::make_pair(EI->getOperand(0), PermittedRHS);
751         }
752 
753         // If this insertelement is a chain that comes from exactly these two
754         // vectors, return the vector and the effective shuffle.
755         if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
756             collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
757                                          Mask))
758           return std::make_pair(EI->getOperand(0), PermittedRHS);
759       }
760     }
761   }
762 
763   // Otherwise, we can't do anything fancy. Return an identity vector.
764   for (unsigned i = 0; i != NumElts; ++i)
765     Mask.push_back(i);
766   return std::make_pair(V, nullptr);
767 }
768 
769 /// Look for chain of insertvalue's that fully define an aggregate, and trace
770 /// back the values inserted, see if they are all were extractvalue'd from
771 /// the same source aggregate from the exact same element indexes.
772 /// If they were, just reuse the source aggregate.
773 /// This potentially deals with PHI indirections.
774 Instruction *InstCombinerImpl::foldAggregateConstructionIntoAggregateReuse(
775     InsertValueInst &OrigIVI) {
776   Type *AggTy = OrigIVI.getType();
777   unsigned NumAggElts;
778   switch (AggTy->getTypeID()) {
779   case Type::StructTyID:
780     NumAggElts = AggTy->getStructNumElements();
781     break;
782   case Type::ArrayTyID:
783     NumAggElts = AggTy->getArrayNumElements();
784     break;
785   default:
786     llvm_unreachable("Unhandled aggregate type?");
787   }
788 
789   // Arbitrary aggregate size cut-off. Motivation for limit of 2 is to be able
790   // to handle clang C++ exception struct (which is hardcoded as {i8*, i32}),
791   // FIXME: any interesting patterns to be caught with larger limit?
792   assert(NumAggElts > 0 && "Aggregate should have elements.");
793   if (NumAggElts > 2)
794     return nullptr;
795 
796   static constexpr auto NotFound = None;
797   static constexpr auto FoundMismatch = nullptr;
798 
799   // Try to find a value of each element of an aggregate.
800   // FIXME: deal with more complex, not one-dimensional, aggregate types
801   SmallVector<Optional<Instruction *>, 2> AggElts(NumAggElts, NotFound);
802 
803   // Do we know values for each element of the aggregate?
804   auto KnowAllElts = [&AggElts]() {
805     return all_of(AggElts,
806                   [](Optional<Instruction *> Elt) { return Elt != NotFound; });
807   };
808 
809   int Depth = 0;
810 
811   // Arbitrary `insertvalue` visitation depth limit. Let's be okay with
812   // every element being overwritten twice, which should never happen.
813   static const int DepthLimit = 2 * NumAggElts;
814 
815   // Recurse up the chain of `insertvalue` aggregate operands until either we've
816   // reconstructed full initializer or can't visit any more `insertvalue`'s.
817   for (InsertValueInst *CurrIVI = &OrigIVI;
818        Depth < DepthLimit && CurrIVI && !KnowAllElts();
819        CurrIVI = dyn_cast<InsertValueInst>(CurrIVI->getAggregateOperand()),
820                        ++Depth) {
821     auto *InsertedValue =
822         dyn_cast<Instruction>(CurrIVI->getInsertedValueOperand());
823     if (!InsertedValue)
824       return nullptr; // Inserted value must be produced by an instruction.
825 
826     ArrayRef<unsigned int> Indices = CurrIVI->getIndices();
827 
828     // Don't bother with more than single-level aggregates.
829     if (Indices.size() != 1)
830       return nullptr; // FIXME: deal with more complex aggregates?
831 
832     // Now, we may have already previously recorded the value for this element
833     // of an aggregate. If we did, that means the CurrIVI will later be
834     // overwritten with the already-recorded value. But if not, let's record it!
835     Optional<Instruction *> &Elt = AggElts[Indices.front()];
836     Elt = Elt.getValueOr(InsertedValue);
837 
838     // FIXME: should we handle chain-terminating undef base operand?
839   }
840 
841   // Was that sufficient to deduce the full initializer for the aggregate?
842   if (!KnowAllElts())
843     return nullptr; // Give up then.
844 
845   // We now want to find the source[s] of the aggregate elements we've found.
846   // And with "source" we mean the original aggregate[s] from which
847   // the inserted elements were extracted. This may require PHI translation.
848 
849   enum class AggregateDescription {
850     /// When analyzing the value that was inserted into an aggregate, we did
851     /// not manage to find defining `extractvalue` instruction to analyze.
852     NotFound,
853     /// When analyzing the value that was inserted into an aggregate, we did
854     /// manage to find defining `extractvalue` instruction[s], and everything
855     /// matched perfectly - aggregate type, element insertion/extraction index.
856     Found,
857     /// When analyzing the value that was inserted into an aggregate, we did
858     /// manage to find defining `extractvalue` instruction, but there was
859     /// a mismatch: either the source type from which the extraction was didn't
860     /// match the aggregate type into which the insertion was,
861     /// or the extraction/insertion channels mismatched,
862     /// or different elements had different source aggregates.
863     FoundMismatch
864   };
865   auto Describe = [](Optional<Value *> SourceAggregate) {
866     if (SourceAggregate == NotFound)
867       return AggregateDescription::NotFound;
868     if (*SourceAggregate == FoundMismatch)
869       return AggregateDescription::FoundMismatch;
870     return AggregateDescription::Found;
871   };
872 
873   // Given the value \p Elt that was being inserted into element \p EltIdx of an
874   // aggregate AggTy, see if \p Elt was originally defined by an
875   // appropriate extractvalue (same element index, same aggregate type).
876   // If found, return the source aggregate from which the extraction was.
877   // If \p PredBB is provided, does PHI translation of an \p Elt first.
878   auto FindSourceAggregate =
879       [&](Instruction *Elt, unsigned EltIdx, Optional<BasicBlock *> UseBB,
880           Optional<BasicBlock *> PredBB) -> Optional<Value *> {
881     // For now(?), only deal with, at most, a single level of PHI indirection.
882     if (UseBB && PredBB)
883       Elt = dyn_cast<Instruction>(Elt->DoPHITranslation(*UseBB, *PredBB));
884     // FIXME: deal with multiple levels of PHI indirection?
885 
886     // Did we find an extraction?
887     auto *EVI = dyn_cast_or_null<ExtractValueInst>(Elt);
888     if (!EVI)
889       return NotFound;
890 
891     Value *SourceAggregate = EVI->getAggregateOperand();
892 
893     // Is the extraction from the same type into which the insertion was?
894     if (SourceAggregate->getType() != AggTy)
895       return FoundMismatch;
896     // And the element index doesn't change between extraction and insertion?
897     if (EVI->getNumIndices() != 1 || EltIdx != EVI->getIndices().front())
898       return FoundMismatch;
899 
900     return SourceAggregate; // AggregateDescription::Found
901   };
902 
903   // Given elements AggElts that were constructing an aggregate OrigIVI,
904   // see if we can find appropriate source aggregate for each of the elements,
905   // and see it's the same aggregate for each element. If so, return it.
906   auto FindCommonSourceAggregate =
907       [&](Optional<BasicBlock *> UseBB,
908           Optional<BasicBlock *> PredBB) -> Optional<Value *> {
909     Optional<Value *> SourceAggregate;
910 
911     for (auto I : enumerate(AggElts)) {
912       assert(Describe(SourceAggregate) != AggregateDescription::FoundMismatch &&
913              "We don't store nullptr in SourceAggregate!");
914       assert((Describe(SourceAggregate) == AggregateDescription::Found) ==
915                  (I.index() != 0) &&
916              "SourceAggregate should be valid after the the first element,");
917 
918       // For this element, is there a plausible source aggregate?
919       // FIXME: we could special-case undef element, IFF we know that in the
920       //        source aggregate said element isn't poison.
921       Optional<Value *> SourceAggregateForElement =
922           FindSourceAggregate(*I.value(), I.index(), UseBB, PredBB);
923 
924       // Okay, what have we found? Does that correlate with previous findings?
925 
926       // Regardless of whether or not we have previously found source
927       // aggregate for previous elements (if any), if we didn't find one for
928       // this element, passthrough whatever we have just found.
929       if (Describe(SourceAggregateForElement) != AggregateDescription::Found)
930         return SourceAggregateForElement;
931 
932       // Okay, we have found source aggregate for this element.
933       // Let's see what we already know from previous elements, if any.
934       switch (Describe(SourceAggregate)) {
935       case AggregateDescription::NotFound:
936         // This is apparently the first element that we have examined.
937         SourceAggregate = SourceAggregateForElement; // Record the aggregate!
938         continue; // Great, now look at next element.
939       case AggregateDescription::Found:
940         // We have previously already successfully examined other elements.
941         // Is this the same source aggregate we've found for other elements?
942         if (*SourceAggregateForElement != *SourceAggregate)
943           return FoundMismatch;
944         continue; // Still the same aggregate, look at next element.
945       case AggregateDescription::FoundMismatch:
946         llvm_unreachable("Can't happen. We would have early-exited then.");
947       };
948     }
949 
950     assert(Describe(SourceAggregate) == AggregateDescription::Found &&
951            "Must be a valid Value");
952     return *SourceAggregate;
953   };
954 
955   Optional<Value *> SourceAggregate;
956 
957   // Can we find the source aggregate without looking at predecessors?
958   SourceAggregate = FindCommonSourceAggregate(/*UseBB=*/None, /*PredBB=*/None);
959   if (Describe(SourceAggregate) != AggregateDescription::NotFound) {
960     if (Describe(SourceAggregate) == AggregateDescription::FoundMismatch)
961       return nullptr; // Conflicting source aggregates!
962     ++NumAggregateReconstructionsSimplified;
963     return replaceInstUsesWith(OrigIVI, *SourceAggregate);
964   }
965 
966   // Okay, apparently we need to look at predecessors.
967 
968   // We should be smart about picking the "use" basic block, which will be the
969   // merge point for aggregate, where we'll insert the final PHI that will be
970   // used instead of OrigIVI. Basic block of OrigIVI is *not* the right choice.
971   // We should look in which blocks each of the AggElts is being defined,
972   // they all should be defined in the same basic block.
973   BasicBlock *UseBB = nullptr;
974 
975   for (const Optional<Instruction *> &I : AggElts) {
976     BasicBlock *BB = (*I)->getParent();
977     // If it's the first instruction we've encountered, record the basic block.
978     if (!UseBB) {
979       UseBB = BB;
980       continue;
981     }
982     // Otherwise, this must be the same basic block we've seen previously.
983     if (UseBB != BB)
984       return nullptr;
985   }
986 
987   // If *all* of the elements are basic-block-independent, meaning they are
988   // either function arguments, or constant expressions, then if we didn't
989   // handle them without predecessor-aware handling, we won't handle them now.
990   if (!UseBB)
991     return nullptr;
992 
993   // If we didn't manage to find source aggregate without looking at
994   // predecessors, and there are no predecessors to look at, then we're done.
995   if (pred_empty(UseBB))
996     return nullptr;
997 
998   // Arbitrary predecessor count limit.
999   static const int PredCountLimit = 64;
1000 
1001   // Cache the (non-uniqified!) list of predecessors in a vector,
1002   // checking the limit at the same time for efficiency.
1003   SmallVector<BasicBlock *, 4> Preds; // May have duplicates!
1004   for (BasicBlock *Pred : predecessors(UseBB)) {
1005     // Don't bother if there are too many predecessors.
1006     if (Preds.size() >= PredCountLimit) // FIXME: only count duplicates once?
1007       return nullptr;
1008     Preds.emplace_back(Pred);
1009   }
1010 
1011   // For each predecessor, what is the source aggregate,
1012   // from which all the elements were originally extracted from?
1013   // Note that we want for the map to have stable iteration order!
1014   SmallDenseMap<BasicBlock *, Value *, 4> SourceAggregates;
1015   for (BasicBlock *Pred : Preds) {
1016     std::pair<decltype(SourceAggregates)::iterator, bool> IV =
1017         SourceAggregates.insert({Pred, nullptr});
1018     // Did we already evaluate this predecessor?
1019     if (!IV.second)
1020       continue;
1021 
1022     // Let's hope that when coming from predecessor Pred, all elements of the
1023     // aggregate produced by OrigIVI must have been originally extracted from
1024     // the same aggregate. Is that so? Can we find said original aggregate?
1025     SourceAggregate = FindCommonSourceAggregate(UseBB, Pred);
1026     if (Describe(SourceAggregate) != AggregateDescription::Found)
1027       return nullptr; // Give up.
1028     IV.first->second = *SourceAggregate;
1029   }
1030 
1031   // All good! Now we just need to thread the source aggregates here.
1032   // Note that we have to insert the new PHI here, ourselves, because we can't
1033   // rely on InstCombinerImpl::run() inserting it into the right basic block.
1034   // Note that the same block can be a predecessor more than once,
1035   // and we need to preserve that invariant for the PHI node.
1036   BuilderTy::InsertPointGuard Guard(Builder);
1037   Builder.SetInsertPoint(UseBB->getFirstNonPHI());
1038   auto *PHI =
1039       Builder.CreatePHI(AggTy, Preds.size(), OrigIVI.getName() + ".merged");
1040   for (BasicBlock *Pred : Preds)
1041     PHI->addIncoming(SourceAggregates[Pred], Pred);
1042 
1043   ++NumAggregateReconstructionsSimplified;
1044   return replaceInstUsesWith(OrigIVI, PHI);
1045 }
1046 
1047 /// Try to find redundant insertvalue instructions, like the following ones:
1048 ///  %0 = insertvalue { i8, i32 } undef, i8 %x, 0
1049 ///  %1 = insertvalue { i8, i32 } %0,    i8 %y, 0
1050 /// Here the second instruction inserts values at the same indices, as the
1051 /// first one, making the first one redundant.
1052 /// It should be transformed to:
1053 ///  %0 = insertvalue { i8, i32 } undef, i8 %y, 0
1054 Instruction *InstCombinerImpl::visitInsertValueInst(InsertValueInst &I) {
1055   bool IsRedundant = false;
1056   ArrayRef<unsigned int> FirstIndices = I.getIndices();
1057 
1058   // If there is a chain of insertvalue instructions (each of them except the
1059   // last one has only one use and it's another insertvalue insn from this
1060   // chain), check if any of the 'children' uses the same indices as the first
1061   // instruction. In this case, the first one is redundant.
1062   Value *V = &I;
1063   unsigned Depth = 0;
1064   while (V->hasOneUse() && Depth < 10) {
1065     User *U = V->user_back();
1066     auto UserInsInst = dyn_cast<InsertValueInst>(U);
1067     if (!UserInsInst || U->getOperand(0) != V)
1068       break;
1069     if (UserInsInst->getIndices() == FirstIndices) {
1070       IsRedundant = true;
1071       break;
1072     }
1073     V = UserInsInst;
1074     Depth++;
1075   }
1076 
1077   if (IsRedundant)
1078     return replaceInstUsesWith(I, I.getOperand(0));
1079 
1080   if (Instruction *NewI = foldAggregateConstructionIntoAggregateReuse(I))
1081     return NewI;
1082 
1083   return nullptr;
1084 }
1085 
1086 static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) {
1087   // Can not analyze scalable type, the number of elements is not a compile-time
1088   // constant.
1089   if (isa<ScalableVectorType>(Shuf.getOperand(0)->getType()))
1090     return false;
1091 
1092   int MaskSize = Shuf.getShuffleMask().size();
1093   int VecSize =
1094       cast<FixedVectorType>(Shuf.getOperand(0)->getType())->getNumElements();
1095 
1096   // A vector select does not change the size of the operands.
1097   if (MaskSize != VecSize)
1098     return false;
1099 
1100   // Each mask element must be undefined or choose a vector element from one of
1101   // the source operands without crossing vector lanes.
1102   for (int i = 0; i != MaskSize; ++i) {
1103     int Elt = Shuf.getMaskValue(i);
1104     if (Elt != -1 && Elt != i && Elt != i + VecSize)
1105       return false;
1106   }
1107 
1108   return true;
1109 }
1110 
1111 /// Turn a chain of inserts that splats a value into an insert + shuffle:
1112 /// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
1113 /// shufflevector(insertelt(X, %k, 0), poison, zero)
1114 static Instruction *foldInsSequenceIntoSplat(InsertElementInst &InsElt) {
1115   // We are interested in the last insert in a chain. So if this insert has a
1116   // single user and that user is an insert, bail.
1117   if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
1118     return nullptr;
1119 
1120   VectorType *VecTy = InsElt.getType();
1121   // Can not handle scalable type, the number of elements is not a compile-time
1122   // constant.
1123   if (isa<ScalableVectorType>(VecTy))
1124     return nullptr;
1125   unsigned NumElements = cast<FixedVectorType>(VecTy)->getNumElements();
1126 
1127   // Do not try to do this for a one-element vector, since that's a nop,
1128   // and will cause an inf-loop.
1129   if (NumElements == 1)
1130     return nullptr;
1131 
1132   Value *SplatVal = InsElt.getOperand(1);
1133   InsertElementInst *CurrIE = &InsElt;
1134   SmallBitVector ElementPresent(NumElements, false);
1135   InsertElementInst *FirstIE = nullptr;
1136 
1137   // Walk the chain backwards, keeping track of which indices we inserted into,
1138   // until we hit something that isn't an insert of the splatted value.
1139   while (CurrIE) {
1140     auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
1141     if (!Idx || CurrIE->getOperand(1) != SplatVal)
1142       return nullptr;
1143 
1144     auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
1145     // Check none of the intermediate steps have any additional uses, except
1146     // for the root insertelement instruction, which can be re-used, if it
1147     // inserts at position 0.
1148     if (CurrIE != &InsElt &&
1149         (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
1150       return nullptr;
1151 
1152     ElementPresent[Idx->getZExtValue()] = true;
1153     FirstIE = CurrIE;
1154     CurrIE = NextIE;
1155   }
1156 
1157   // If this is just a single insertelement (not a sequence), we are done.
1158   if (FirstIE == &InsElt)
1159     return nullptr;
1160 
1161   // If we are not inserting into an undef vector, make sure we've seen an
1162   // insert into every element.
1163   // TODO: If the base vector is not undef, it might be better to create a splat
1164   //       and then a select-shuffle (blend) with the base vector.
1165   if (!match(FirstIE->getOperand(0), m_Undef()))
1166     if (!ElementPresent.all())
1167       return nullptr;
1168 
1169   // Create the insert + shuffle.
1170   Type *Int32Ty = Type::getInt32Ty(InsElt.getContext());
1171   PoisonValue *PoisonVec = PoisonValue::get(VecTy);
1172   Constant *Zero = ConstantInt::get(Int32Ty, 0);
1173   if (!cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
1174     FirstIE = InsertElementInst::Create(PoisonVec, SplatVal, Zero, "", &InsElt);
1175 
1176   // Splat from element 0, but replace absent elements with undef in the mask.
1177   SmallVector<int, 16> Mask(NumElements, 0);
1178   for (unsigned i = 0; i != NumElements; ++i)
1179     if (!ElementPresent[i])
1180       Mask[i] = -1;
1181 
1182   return new ShuffleVectorInst(FirstIE, PoisonVec, Mask);
1183 }
1184 
1185 /// Try to fold an insert element into an existing splat shuffle by changing
1186 /// the shuffle's mask to include the index of this insert element.
1187 static Instruction *foldInsEltIntoSplat(InsertElementInst &InsElt) {
1188   // Check if the vector operand of this insert is a canonical splat shuffle.
1189   auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
1190   if (!Shuf || !Shuf->isZeroEltSplat())
1191     return nullptr;
1192 
1193   // Bail out early if shuffle is scalable type. The number of elements in
1194   // shuffle mask is unknown at compile-time.
1195   if (isa<ScalableVectorType>(Shuf->getType()))
1196     return nullptr;
1197 
1198   // Check for a constant insertion index.
1199   uint64_t IdxC;
1200   if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
1201     return nullptr;
1202 
1203   // Check if the splat shuffle's input is the same as this insert's scalar op.
1204   Value *X = InsElt.getOperand(1);
1205   Value *Op0 = Shuf->getOperand(0);
1206   if (!match(Op0, m_InsertElt(m_Undef(), m_Specific(X), m_ZeroInt())))
1207     return nullptr;
1208 
1209   // Replace the shuffle mask element at the index of this insert with a zero.
1210   // For example:
1211   // inselt (shuf (inselt undef, X, 0), undef, <0,undef,0,undef>), X, 1
1212   //   --> shuf (inselt undef, X, 0), undef, <0,0,0,undef>
1213   unsigned NumMaskElts =
1214       cast<FixedVectorType>(Shuf->getType())->getNumElements();
1215   SmallVector<int, 16> NewMask(NumMaskElts);
1216   for (unsigned i = 0; i != NumMaskElts; ++i)
1217     NewMask[i] = i == IdxC ? 0 : Shuf->getMaskValue(i);
1218 
1219   return new ShuffleVectorInst(Op0, UndefValue::get(Op0->getType()), NewMask);
1220 }
1221 
1222 /// Try to fold an extract+insert element into an existing identity shuffle by
1223 /// changing the shuffle's mask to include the index of this insert element.
1224 static Instruction *foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt) {
1225   // Check if the vector operand of this insert is an identity shuffle.
1226   auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
1227   if (!Shuf || !match(Shuf->getOperand(1), m_Undef()) ||
1228       !(Shuf->isIdentityWithExtract() || Shuf->isIdentityWithPadding()))
1229     return nullptr;
1230 
1231   // Bail out early if shuffle is scalable type. The number of elements in
1232   // shuffle mask is unknown at compile-time.
1233   if (isa<ScalableVectorType>(Shuf->getType()))
1234     return nullptr;
1235 
1236   // Check for a constant insertion index.
1237   uint64_t IdxC;
1238   if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
1239     return nullptr;
1240 
1241   // Check if this insert's scalar op is extracted from the identity shuffle's
1242   // input vector.
1243   Value *Scalar = InsElt.getOperand(1);
1244   Value *X = Shuf->getOperand(0);
1245   if (!match(Scalar, m_ExtractElt(m_Specific(X), m_SpecificInt(IdxC))))
1246     return nullptr;
1247 
1248   // Replace the shuffle mask element at the index of this extract+insert with
1249   // that same index value.
1250   // For example:
1251   // inselt (shuf X, IdMask), (extelt X, IdxC), IdxC --> shuf X, IdMask'
1252   unsigned NumMaskElts =
1253       cast<FixedVectorType>(Shuf->getType())->getNumElements();
1254   SmallVector<int, 16> NewMask(NumMaskElts);
1255   ArrayRef<int> OldMask = Shuf->getShuffleMask();
1256   for (unsigned i = 0; i != NumMaskElts; ++i) {
1257     if (i != IdxC) {
1258       // All mask elements besides the inserted element remain the same.
1259       NewMask[i] = OldMask[i];
1260     } else if (OldMask[i] == (int)IdxC) {
1261       // If the mask element was already set, there's nothing to do
1262       // (demanded elements analysis may unset it later).
1263       return nullptr;
1264     } else {
1265       assert(OldMask[i] == UndefMaskElem &&
1266              "Unexpected shuffle mask element for identity shuffle");
1267       NewMask[i] = IdxC;
1268     }
1269   }
1270 
1271   return new ShuffleVectorInst(X, Shuf->getOperand(1), NewMask);
1272 }
1273 
1274 /// If we have an insertelement instruction feeding into another insertelement
1275 /// and the 2nd is inserting a constant into the vector, canonicalize that
1276 /// constant insertion before the insertion of a variable:
1277 ///
1278 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
1279 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
1280 ///
1281 /// This has the potential of eliminating the 2nd insertelement instruction
1282 /// via constant folding of the scalar constant into a vector constant.
1283 static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
1284                                      InstCombiner::BuilderTy &Builder) {
1285   auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
1286   if (!InsElt1 || !InsElt1->hasOneUse())
1287     return nullptr;
1288 
1289   Value *X, *Y;
1290   Constant *ScalarC;
1291   ConstantInt *IdxC1, *IdxC2;
1292   if (match(InsElt1->getOperand(0), m_Value(X)) &&
1293       match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
1294       match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
1295       match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
1296       match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
1297     Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
1298     return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
1299   }
1300 
1301   return nullptr;
1302 }
1303 
1304 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
1305 /// --> shufflevector X, CVec', Mask'
1306 static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
1307   auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
1308   // Bail out if the parent has more than one use. In that case, we'd be
1309   // replacing the insertelt with a shuffle, and that's not a clear win.
1310   if (!Inst || !Inst->hasOneUse())
1311     return nullptr;
1312   if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
1313     // The shuffle must have a constant vector operand. The insertelt must have
1314     // a constant scalar being inserted at a constant position in the vector.
1315     Constant *ShufConstVec, *InsEltScalar;
1316     uint64_t InsEltIndex;
1317     if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
1318         !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
1319         !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
1320       return nullptr;
1321 
1322     // Adding an element to an arbitrary shuffle could be expensive, but a
1323     // shuffle that selects elements from vectors without crossing lanes is
1324     // assumed cheap.
1325     // If we're just adding a constant into that shuffle, it will still be
1326     // cheap.
1327     if (!isShuffleEquivalentToSelect(*Shuf))
1328       return nullptr;
1329 
1330     // From the above 'select' check, we know that the mask has the same number
1331     // of elements as the vector input operands. We also know that each constant
1332     // input element is used in its lane and can not be used more than once by
1333     // the shuffle. Therefore, replace the constant in the shuffle's constant
1334     // vector with the insertelt constant. Replace the constant in the shuffle's
1335     // mask vector with the insertelt index plus the length of the vector
1336     // (because the constant vector operand of a shuffle is always the 2nd
1337     // operand).
1338     ArrayRef<int> Mask = Shuf->getShuffleMask();
1339     unsigned NumElts = Mask.size();
1340     SmallVector<Constant *, 16> NewShufElts(NumElts);
1341     SmallVector<int, 16> NewMaskElts(NumElts);
1342     for (unsigned I = 0; I != NumElts; ++I) {
1343       if (I == InsEltIndex) {
1344         NewShufElts[I] = InsEltScalar;
1345         NewMaskElts[I] = InsEltIndex + NumElts;
1346       } else {
1347         // Copy over the existing values.
1348         NewShufElts[I] = ShufConstVec->getAggregateElement(I);
1349         NewMaskElts[I] = Mask[I];
1350       }
1351     }
1352 
1353     // Create new operands for a shuffle that includes the constant of the
1354     // original insertelt. The old shuffle will be dead now.
1355     return new ShuffleVectorInst(Shuf->getOperand(0),
1356                                  ConstantVector::get(NewShufElts), NewMaskElts);
1357   } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
1358     // Transform sequences of insertelements ops with constant data/indexes into
1359     // a single shuffle op.
1360     // Can not handle scalable type, the number of elements needed to create
1361     // shuffle mask is not a compile-time constant.
1362     if (isa<ScalableVectorType>(InsElt.getType()))
1363       return nullptr;
1364     unsigned NumElts =
1365         cast<FixedVectorType>(InsElt.getType())->getNumElements();
1366 
1367     uint64_t InsertIdx[2];
1368     Constant *Val[2];
1369     if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
1370         !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
1371         !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
1372         !match(IEI->getOperand(1), m_Constant(Val[1])))
1373       return nullptr;
1374     SmallVector<Constant *, 16> Values(NumElts);
1375     SmallVector<int, 16> Mask(NumElts);
1376     auto ValI = std::begin(Val);
1377     // Generate new constant vector and mask.
1378     // We have 2 values/masks from the insertelements instructions. Insert them
1379     // into new value/mask vectors.
1380     for (uint64_t I : InsertIdx) {
1381       if (!Values[I]) {
1382         Values[I] = *ValI;
1383         Mask[I] = NumElts + I;
1384       }
1385       ++ValI;
1386     }
1387     // Remaining values are filled with 'undef' values.
1388     for (unsigned I = 0; I < NumElts; ++I) {
1389       if (!Values[I]) {
1390         Values[I] = UndefValue::get(InsElt.getType()->getElementType());
1391         Mask[I] = I;
1392       }
1393     }
1394     // Create new operands for a shuffle that includes the constant of the
1395     // original insertelt.
1396     return new ShuffleVectorInst(IEI->getOperand(0),
1397                                  ConstantVector::get(Values), Mask);
1398   }
1399   return nullptr;
1400 }
1401 
1402 Instruction *InstCombinerImpl::visitInsertElementInst(InsertElementInst &IE) {
1403   Value *VecOp    = IE.getOperand(0);
1404   Value *ScalarOp = IE.getOperand(1);
1405   Value *IdxOp    = IE.getOperand(2);
1406 
1407   if (auto *V = SimplifyInsertElementInst(
1408           VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
1409     return replaceInstUsesWith(IE, V);
1410 
1411   // If the scalar is bitcast and inserted into undef, do the insert in the
1412   // source type followed by bitcast.
1413   // TODO: Generalize for insert into any constant, not just undef?
1414   Value *ScalarSrc;
1415   if (match(VecOp, m_Undef()) &&
1416       match(ScalarOp, m_OneUse(m_BitCast(m_Value(ScalarSrc)))) &&
1417       (ScalarSrc->getType()->isIntegerTy() ||
1418        ScalarSrc->getType()->isFloatingPointTy())) {
1419     // inselt undef, (bitcast ScalarSrc), IdxOp -->
1420     //   bitcast (inselt undef, ScalarSrc, IdxOp)
1421     Type *ScalarTy = ScalarSrc->getType();
1422     Type *VecTy = VectorType::get(ScalarTy, IE.getType()->getElementCount());
1423     UndefValue *NewUndef = UndefValue::get(VecTy);
1424     Value *NewInsElt = Builder.CreateInsertElement(NewUndef, ScalarSrc, IdxOp);
1425     return new BitCastInst(NewInsElt, IE.getType());
1426   }
1427 
1428   // If the vector and scalar are both bitcast from the same element type, do
1429   // the insert in that source type followed by bitcast.
1430   Value *VecSrc;
1431   if (match(VecOp, m_BitCast(m_Value(VecSrc))) &&
1432       match(ScalarOp, m_BitCast(m_Value(ScalarSrc))) &&
1433       (VecOp->hasOneUse() || ScalarOp->hasOneUse()) &&
1434       VecSrc->getType()->isVectorTy() && !ScalarSrc->getType()->isVectorTy() &&
1435       cast<VectorType>(VecSrc->getType())->getElementType() ==
1436           ScalarSrc->getType()) {
1437     // inselt (bitcast VecSrc), (bitcast ScalarSrc), IdxOp -->
1438     //   bitcast (inselt VecSrc, ScalarSrc, IdxOp)
1439     Value *NewInsElt = Builder.CreateInsertElement(VecSrc, ScalarSrc, IdxOp);
1440     return new BitCastInst(NewInsElt, IE.getType());
1441   }
1442 
1443   // If the inserted element was extracted from some other fixed-length vector
1444   // and both indexes are valid constants, try to turn this into a shuffle.
1445   // Can not handle scalable vector type, the number of elements needed to
1446   // create shuffle mask is not a compile-time constant.
1447   uint64_t InsertedIdx, ExtractedIdx;
1448   Value *ExtVecOp;
1449   if (isa<FixedVectorType>(IE.getType()) &&
1450       match(IdxOp, m_ConstantInt(InsertedIdx)) &&
1451       match(ScalarOp,
1452             m_ExtractElt(m_Value(ExtVecOp), m_ConstantInt(ExtractedIdx))) &&
1453       isa<FixedVectorType>(ExtVecOp->getType()) &&
1454       ExtractedIdx <
1455           cast<FixedVectorType>(ExtVecOp->getType())->getNumElements()) {
1456     // TODO: Looking at the user(s) to determine if this insert is a
1457     // fold-to-shuffle opportunity does not match the usual instcombine
1458     // constraints. We should decide if the transform is worthy based only
1459     // on this instruction and its operands, but that may not work currently.
1460     //
1461     // Here, we are trying to avoid creating shuffles before reaching
1462     // the end of a chain of extract-insert pairs. This is complicated because
1463     // we do not generally form arbitrary shuffle masks in instcombine
1464     // (because those may codegen poorly), but collectShuffleElements() does
1465     // exactly that.
1466     //
1467     // The rules for determining what is an acceptable target-independent
1468     // shuffle mask are fuzzy because they evolve based on the backend's
1469     // capabilities and real-world impact.
1470     auto isShuffleRootCandidate = [](InsertElementInst &Insert) {
1471       if (!Insert.hasOneUse())
1472         return true;
1473       auto *InsertUser = dyn_cast<InsertElementInst>(Insert.user_back());
1474       if (!InsertUser)
1475         return true;
1476       return false;
1477     };
1478 
1479     // Try to form a shuffle from a chain of extract-insert ops.
1480     if (isShuffleRootCandidate(IE)) {
1481       SmallVector<int, 16> Mask;
1482       ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
1483 
1484       // The proposed shuffle may be trivial, in which case we shouldn't
1485       // perform the combine.
1486       if (LR.first != &IE && LR.second != &IE) {
1487         // We now have a shuffle of LHS, RHS, Mask.
1488         if (LR.second == nullptr)
1489           LR.second = UndefValue::get(LR.first->getType());
1490         return new ShuffleVectorInst(LR.first, LR.second, Mask);
1491       }
1492     }
1493   }
1494 
1495   if (auto VecTy = dyn_cast<FixedVectorType>(VecOp->getType())) {
1496     unsigned VWidth = VecTy->getNumElements();
1497     APInt UndefElts(VWidth, 0);
1498     APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1499     if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
1500       if (V != &IE)
1501         return replaceInstUsesWith(IE, V);
1502       return &IE;
1503     }
1504   }
1505 
1506   if (Instruction *Shuf = foldConstantInsEltIntoShuffle(IE))
1507     return Shuf;
1508 
1509   if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
1510     return NewInsElt;
1511 
1512   if (Instruction *Broadcast = foldInsSequenceIntoSplat(IE))
1513     return Broadcast;
1514 
1515   if (Instruction *Splat = foldInsEltIntoSplat(IE))
1516     return Splat;
1517 
1518   if (Instruction *IdentityShuf = foldInsEltIntoIdentityShuffle(IE))
1519     return IdentityShuf;
1520 
1521   return nullptr;
1522 }
1523 
1524 /// Return true if we can evaluate the specified expression tree if the vector
1525 /// elements were shuffled in a different order.
1526 static bool canEvaluateShuffled(Value *V, ArrayRef<int> Mask,
1527                                 unsigned Depth = 5) {
1528   // We can always reorder the elements of a constant.
1529   if (isa<Constant>(V))
1530     return true;
1531 
1532   // We won't reorder vector arguments. No IPO here.
1533   Instruction *I = dyn_cast<Instruction>(V);
1534   if (!I) return false;
1535 
1536   // Two users may expect different orders of the elements. Don't try it.
1537   if (!I->hasOneUse())
1538     return false;
1539 
1540   if (Depth == 0) return false;
1541 
1542   switch (I->getOpcode()) {
1543     case Instruction::UDiv:
1544     case Instruction::SDiv:
1545     case Instruction::URem:
1546     case Instruction::SRem:
1547       // Propagating an undefined shuffle mask element to integer div/rem is not
1548       // allowed because those opcodes can create immediate undefined behavior
1549       // from an undefined element in an operand.
1550       if (llvm::is_contained(Mask, -1))
1551         return false;
1552       LLVM_FALLTHROUGH;
1553     case Instruction::Add:
1554     case Instruction::FAdd:
1555     case Instruction::Sub:
1556     case Instruction::FSub:
1557     case Instruction::Mul:
1558     case Instruction::FMul:
1559     case Instruction::FDiv:
1560     case Instruction::FRem:
1561     case Instruction::Shl:
1562     case Instruction::LShr:
1563     case Instruction::AShr:
1564     case Instruction::And:
1565     case Instruction::Or:
1566     case Instruction::Xor:
1567     case Instruction::ICmp:
1568     case Instruction::FCmp:
1569     case Instruction::Trunc:
1570     case Instruction::ZExt:
1571     case Instruction::SExt:
1572     case Instruction::FPToUI:
1573     case Instruction::FPToSI:
1574     case Instruction::UIToFP:
1575     case Instruction::SIToFP:
1576     case Instruction::FPTrunc:
1577     case Instruction::FPExt:
1578     case Instruction::GetElementPtr: {
1579       // Bail out if we would create longer vector ops. We could allow creating
1580       // longer vector ops, but that may result in more expensive codegen.
1581       Type *ITy = I->getType();
1582       if (ITy->isVectorTy() &&
1583           Mask.size() > cast<FixedVectorType>(ITy)->getNumElements())
1584         return false;
1585       for (Value *Operand : I->operands()) {
1586         if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
1587           return false;
1588       }
1589       return true;
1590     }
1591     case Instruction::InsertElement: {
1592       ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2));
1593       if (!CI) return false;
1594       int ElementNumber = CI->getLimitedValue();
1595 
1596       // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
1597       // can't put an element into multiple indices.
1598       bool SeenOnce = false;
1599       for (int i = 0, e = Mask.size(); i != e; ++i) {
1600         if (Mask[i] == ElementNumber) {
1601           if (SeenOnce)
1602             return false;
1603           SeenOnce = true;
1604         }
1605       }
1606       return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1);
1607     }
1608   }
1609   return false;
1610 }
1611 
1612 /// Rebuild a new instruction just like 'I' but with the new operands given.
1613 /// In the event of type mismatch, the type of the operands is correct.
1614 static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) {
1615   // We don't want to use the IRBuilder here because we want the replacement
1616   // instructions to appear next to 'I', not the builder's insertion point.
1617   switch (I->getOpcode()) {
1618     case Instruction::Add:
1619     case Instruction::FAdd:
1620     case Instruction::Sub:
1621     case Instruction::FSub:
1622     case Instruction::Mul:
1623     case Instruction::FMul:
1624     case Instruction::UDiv:
1625     case Instruction::SDiv:
1626     case Instruction::FDiv:
1627     case Instruction::URem:
1628     case Instruction::SRem:
1629     case Instruction::FRem:
1630     case Instruction::Shl:
1631     case Instruction::LShr:
1632     case Instruction::AShr:
1633     case Instruction::And:
1634     case Instruction::Or:
1635     case Instruction::Xor: {
1636       BinaryOperator *BO = cast<BinaryOperator>(I);
1637       assert(NewOps.size() == 2 && "binary operator with #ops != 2");
1638       BinaryOperator *New =
1639           BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
1640                                  NewOps[0], NewOps[1], "", BO);
1641       if (isa<OverflowingBinaryOperator>(BO)) {
1642         New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
1643         New->setHasNoSignedWrap(BO->hasNoSignedWrap());
1644       }
1645       if (isa<PossiblyExactOperator>(BO)) {
1646         New->setIsExact(BO->isExact());
1647       }
1648       if (isa<FPMathOperator>(BO))
1649         New->copyFastMathFlags(I);
1650       return New;
1651     }
1652     case Instruction::ICmp:
1653       assert(NewOps.size() == 2 && "icmp with #ops != 2");
1654       return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
1655                           NewOps[0], NewOps[1]);
1656     case Instruction::FCmp:
1657       assert(NewOps.size() == 2 && "fcmp with #ops != 2");
1658       return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
1659                           NewOps[0], NewOps[1]);
1660     case Instruction::Trunc:
1661     case Instruction::ZExt:
1662     case Instruction::SExt:
1663     case Instruction::FPToUI:
1664     case Instruction::FPToSI:
1665     case Instruction::UIToFP:
1666     case Instruction::SIToFP:
1667     case Instruction::FPTrunc:
1668     case Instruction::FPExt: {
1669       // It's possible that the mask has a different number of elements from
1670       // the original cast. We recompute the destination type to match the mask.
1671       Type *DestTy = VectorType::get(
1672           I->getType()->getScalarType(),
1673           cast<VectorType>(NewOps[0]->getType())->getElementCount());
1674       assert(NewOps.size() == 1 && "cast with #ops != 1");
1675       return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
1676                               "", I);
1677     }
1678     case Instruction::GetElementPtr: {
1679       Value *Ptr = NewOps[0];
1680       ArrayRef<Value*> Idx = NewOps.slice(1);
1681       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1682           cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1683       GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1684       return GEP;
1685     }
1686   }
1687   llvm_unreachable("failed to rebuild vector instructions");
1688 }
1689 
1690 static Value *evaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
1691   // Mask.size() does not need to be equal to the number of vector elements.
1692 
1693   assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1694   Type *EltTy = V->getType()->getScalarType();
1695   Type *I32Ty = IntegerType::getInt32Ty(V->getContext());
1696   if (match(V, m_Undef()))
1697     return UndefValue::get(FixedVectorType::get(EltTy, Mask.size()));
1698 
1699   if (isa<ConstantAggregateZero>(V))
1700     return ConstantAggregateZero::get(FixedVectorType::get(EltTy, Mask.size()));
1701 
1702   if (Constant *C = dyn_cast<Constant>(V))
1703     return ConstantExpr::getShuffleVector(C, PoisonValue::get(C->getType()),
1704                                           Mask);
1705 
1706   Instruction *I = cast<Instruction>(V);
1707   switch (I->getOpcode()) {
1708     case Instruction::Add:
1709     case Instruction::FAdd:
1710     case Instruction::Sub:
1711     case Instruction::FSub:
1712     case Instruction::Mul:
1713     case Instruction::FMul:
1714     case Instruction::UDiv:
1715     case Instruction::SDiv:
1716     case Instruction::FDiv:
1717     case Instruction::URem:
1718     case Instruction::SRem:
1719     case Instruction::FRem:
1720     case Instruction::Shl:
1721     case Instruction::LShr:
1722     case Instruction::AShr:
1723     case Instruction::And:
1724     case Instruction::Or:
1725     case Instruction::Xor:
1726     case Instruction::ICmp:
1727     case Instruction::FCmp:
1728     case Instruction::Trunc:
1729     case Instruction::ZExt:
1730     case Instruction::SExt:
1731     case Instruction::FPToUI:
1732     case Instruction::FPToSI:
1733     case Instruction::UIToFP:
1734     case Instruction::SIToFP:
1735     case Instruction::FPTrunc:
1736     case Instruction::FPExt:
1737     case Instruction::Select:
1738     case Instruction::GetElementPtr: {
1739       SmallVector<Value*, 8> NewOps;
1740       bool NeedsRebuild =
1741           (Mask.size() !=
1742            cast<FixedVectorType>(I->getType())->getNumElements());
1743       for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1744         Value *V;
1745         // Recursively call evaluateInDifferentElementOrder on vector arguments
1746         // as well. E.g. GetElementPtr may have scalar operands even if the
1747         // return value is a vector, so we need to examine the operand type.
1748         if (I->getOperand(i)->getType()->isVectorTy())
1749           V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1750         else
1751           V = I->getOperand(i);
1752         NewOps.push_back(V);
1753         NeedsRebuild |= (V != I->getOperand(i));
1754       }
1755       if (NeedsRebuild) {
1756         return buildNew(I, NewOps);
1757       }
1758       return I;
1759     }
1760     case Instruction::InsertElement: {
1761       int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1762 
1763       // The insertelement was inserting at Element. Figure out which element
1764       // that becomes after shuffling. The answer is guaranteed to be unique
1765       // by CanEvaluateShuffled.
1766       bool Found = false;
1767       int Index = 0;
1768       for (int e = Mask.size(); Index != e; ++Index) {
1769         if (Mask[Index] == Element) {
1770           Found = true;
1771           break;
1772         }
1773       }
1774 
1775       // If element is not in Mask, no need to handle the operand 1 (element to
1776       // be inserted). Just evaluate values in operand 0 according to Mask.
1777       if (!Found)
1778         return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1779 
1780       Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1781       return InsertElementInst::Create(V, I->getOperand(1),
1782                                        ConstantInt::get(I32Ty, Index), "", I);
1783     }
1784   }
1785   llvm_unreachable("failed to reorder elements of vector instruction!");
1786 }
1787 
1788 // Returns true if the shuffle is extracting a contiguous range of values from
1789 // LHS, for example:
1790 //                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1791 //   Input:        |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1792 //   Shuffles to:  |EE|FF|GG|HH|
1793 //                 +--+--+--+--+
1794 static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
1795                                        ArrayRef<int> Mask) {
1796   unsigned LHSElems =
1797       cast<FixedVectorType>(SVI.getOperand(0)->getType())->getNumElements();
1798   unsigned MaskElems = Mask.size();
1799   unsigned BegIdx = Mask.front();
1800   unsigned EndIdx = Mask.back();
1801   if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1802     return false;
1803   for (unsigned I = 0; I != MaskElems; ++I)
1804     if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1805       return false;
1806   return true;
1807 }
1808 
1809 /// These are the ingredients in an alternate form binary operator as described
1810 /// below.
1811 struct BinopElts {
1812   BinaryOperator::BinaryOps Opcode;
1813   Value *Op0;
1814   Value *Op1;
1815   BinopElts(BinaryOperator::BinaryOps Opc = (BinaryOperator::BinaryOps)0,
1816             Value *V0 = nullptr, Value *V1 = nullptr) :
1817       Opcode(Opc), Op0(V0), Op1(V1) {}
1818   operator bool() const { return Opcode != 0; }
1819 };
1820 
1821 /// Binops may be transformed into binops with different opcodes and operands.
1822 /// Reverse the usual canonicalization to enable folds with the non-canonical
1823 /// form of the binop. If a transform is possible, return the elements of the
1824 /// new binop. If not, return invalid elements.
1825 static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL) {
1826   Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1827   Type *Ty = BO->getType();
1828   switch (BO->getOpcode()) {
1829     case Instruction::Shl: {
1830       // shl X, C --> mul X, (1 << C)
1831       Constant *C;
1832       if (match(BO1, m_Constant(C))) {
1833         Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1834         return { Instruction::Mul, BO0, ShlOne };
1835       }
1836       break;
1837     }
1838     case Instruction::Or: {
1839       // or X, C --> add X, C (when X and C have no common bits set)
1840       const APInt *C;
1841       if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1842         return { Instruction::Add, BO0, BO1 };
1843       break;
1844     }
1845     default:
1846       break;
1847   }
1848   return {};
1849 }
1850 
1851 static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf) {
1852   assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1853 
1854   // Are we shuffling together some value and that same value after it has been
1855   // modified by a binop with a constant?
1856   Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1857   Constant *C;
1858   bool Op0IsBinop;
1859   if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1860     Op0IsBinop = true;
1861   else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1862     Op0IsBinop = false;
1863   else
1864     return nullptr;
1865 
1866   // The identity constant for a binop leaves a variable operand unchanged. For
1867   // a vector, this is a splat of something like 0, -1, or 1.
1868   // If there's no identity constant for this binop, we're done.
1869   auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1870   BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1871   Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1872   if (!IdC)
1873     return nullptr;
1874 
1875   // Shuffle identity constants into the lanes that return the original value.
1876   // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1877   // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1878   // The existing binop constant vector remains in the same operand position.
1879   ArrayRef<int> Mask = Shuf.getShuffleMask();
1880   Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1881                                 ConstantExpr::getShuffleVector(IdC, C, Mask);
1882 
1883   bool MightCreatePoisonOrUB =
1884       is_contained(Mask, UndefMaskElem) &&
1885       (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1886   if (MightCreatePoisonOrUB)
1887     NewC = InstCombiner::getSafeVectorConstantForBinop(BOpcode, NewC, true);
1888 
1889   // shuf (bop X, C), X, M --> bop X, C'
1890   // shuf X, (bop X, C), M --> bop X, C'
1891   Value *X = Op0IsBinop ? Op1 : Op0;
1892   Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1893   NewBO->copyIRFlags(BO);
1894 
1895   // An undef shuffle mask element may propagate as an undef constant element in
1896   // the new binop. That would produce poison where the original code might not.
1897   // If we already made a safe constant, then there's no danger.
1898   if (is_contained(Mask, UndefMaskElem) && !MightCreatePoisonOrUB)
1899     NewBO->dropPoisonGeneratingFlags();
1900   return NewBO;
1901 }
1902 
1903 /// If we have an insert of a scalar to a non-zero element of an undefined
1904 /// vector and then shuffle that value, that's the same as inserting to the zero
1905 /// element and shuffling. Splatting from the zero element is recognized as the
1906 /// canonical form of splat.
1907 static Instruction *canonicalizeInsertSplat(ShuffleVectorInst &Shuf,
1908                                             InstCombiner::BuilderTy &Builder) {
1909   Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1910   ArrayRef<int> Mask = Shuf.getShuffleMask();
1911   Value *X;
1912   uint64_t IndexC;
1913 
1914   // Match a shuffle that is a splat to a non-zero element.
1915   if (!match(Op0, m_OneUse(m_InsertElt(m_Undef(), m_Value(X),
1916                                        m_ConstantInt(IndexC)))) ||
1917       !match(Op1, m_Undef()) || match(Mask, m_ZeroMask()) || IndexC == 0)
1918     return nullptr;
1919 
1920   // Insert into element 0 of an undef vector.
1921   UndefValue *UndefVec = UndefValue::get(Shuf.getType());
1922   Constant *Zero = Builder.getInt32(0);
1923   Value *NewIns = Builder.CreateInsertElement(UndefVec, X, Zero);
1924 
1925   // Splat from element 0. Any mask element that is undefined remains undefined.
1926   // For example:
1927   // shuf (inselt undef, X, 2), undef, <2,2,undef>
1928   //   --> shuf (inselt undef, X, 0), undef, <0,0,undef>
1929   unsigned NumMaskElts =
1930       cast<FixedVectorType>(Shuf.getType())->getNumElements();
1931   SmallVector<int, 16> NewMask(NumMaskElts, 0);
1932   for (unsigned i = 0; i != NumMaskElts; ++i)
1933     if (Mask[i] == UndefMaskElem)
1934       NewMask[i] = Mask[i];
1935 
1936   return new ShuffleVectorInst(NewIns, UndefVec, NewMask);
1937 }
1938 
1939 /// Try to fold shuffles that are the equivalent of a vector select.
1940 static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf,
1941                                       InstCombiner::BuilderTy &Builder,
1942                                       const DataLayout &DL) {
1943   if (!Shuf.isSelect())
1944     return nullptr;
1945 
1946   // Canonicalize to choose from operand 0 first unless operand 1 is undefined.
1947   // Commuting undef to operand 0 conflicts with another canonicalization.
1948   unsigned NumElts = cast<FixedVectorType>(Shuf.getType())->getNumElements();
1949   if (!match(Shuf.getOperand(1), m_Undef()) &&
1950       Shuf.getMaskValue(0) >= (int)NumElts) {
1951     // TODO: Can we assert that both operands of a shuffle-select are not undef
1952     // (otherwise, it would have been folded by instsimplify?
1953     Shuf.commute();
1954     return &Shuf;
1955   }
1956 
1957   if (Instruction *I = foldSelectShuffleWith1Binop(Shuf))
1958     return I;
1959 
1960   BinaryOperator *B0, *B1;
1961   if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1962       !match(Shuf.getOperand(1), m_BinOp(B1)))
1963     return nullptr;
1964 
1965   Value *X, *Y;
1966   Constant *C0, *C1;
1967   bool ConstantsAreOp1;
1968   if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1969       match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1970     ConstantsAreOp1 = true;
1971   else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1972            match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1973     ConstantsAreOp1 = false;
1974   else
1975     return nullptr;
1976 
1977   // We need matching binops to fold the lanes together.
1978   BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1979   BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1980   bool DropNSW = false;
1981   if (ConstantsAreOp1 && Opc0 != Opc1) {
1982     // TODO: We drop "nsw" if shift is converted into multiply because it may
1983     // not be correct when the shift amount is BitWidth - 1. We could examine
1984     // each vector element to determine if it is safe to keep that flag.
1985     if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1986       DropNSW = true;
1987     if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1988       assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1989       Opc0 = AltB0.Opcode;
1990       C0 = cast<Constant>(AltB0.Op1);
1991     } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1992       assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1993       Opc1 = AltB1.Opcode;
1994       C1 = cast<Constant>(AltB1.Op1);
1995     }
1996   }
1997 
1998   if (Opc0 != Opc1)
1999     return nullptr;
2000 
2001   // The opcodes must be the same. Use a new name to make that clear.
2002   BinaryOperator::BinaryOps BOpc = Opc0;
2003 
2004   // Select the constant elements needed for the single binop.
2005   ArrayRef<int> Mask = Shuf.getShuffleMask();
2006   Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
2007 
2008   // We are moving a binop after a shuffle. When a shuffle has an undefined
2009   // mask element, the result is undefined, but it is not poison or undefined
2010   // behavior. That is not necessarily true for div/rem/shift.
2011   bool MightCreatePoisonOrUB =
2012       is_contained(Mask, UndefMaskElem) &&
2013       (Instruction::isIntDivRem(BOpc) || Instruction::isShift(BOpc));
2014   if (MightCreatePoisonOrUB)
2015     NewC = InstCombiner::getSafeVectorConstantForBinop(BOpc, NewC,
2016                                                        ConstantsAreOp1);
2017 
2018   Value *V;
2019   if (X == Y) {
2020     // Remove a binop and the shuffle by rearranging the constant:
2021     // shuffle (op V, C0), (op V, C1), M --> op V, C'
2022     // shuffle (op C0, V), (op C1, V), M --> op C', V
2023     V = X;
2024   } else {
2025     // If there are 2 different variable operands, we must create a new shuffle
2026     // (select) first, so check uses to ensure that we don't end up with more
2027     // instructions than we started with.
2028     if (!B0->hasOneUse() && !B1->hasOneUse())
2029       return nullptr;
2030 
2031     // If we use the original shuffle mask and op1 is *variable*, we would be
2032     // putting an undef into operand 1 of div/rem/shift. This is either UB or
2033     // poison. We do not have to guard against UB when *constants* are op1
2034     // because safe constants guarantee that we do not overflow sdiv/srem (and
2035     // there's no danger for other opcodes).
2036     // TODO: To allow this case, create a new shuffle mask with no undefs.
2037     if (MightCreatePoisonOrUB && !ConstantsAreOp1)
2038       return nullptr;
2039 
2040     // Note: In general, we do not create new shuffles in InstCombine because we
2041     // do not know if a target can lower an arbitrary shuffle optimally. In this
2042     // case, the shuffle uses the existing mask, so there is no additional risk.
2043 
2044     // Select the variable vectors first, then perform the binop:
2045     // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
2046     // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
2047     V = Builder.CreateShuffleVector(X, Y, Mask);
2048   }
2049 
2050   Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
2051                                          BinaryOperator::Create(BOpc, NewC, V);
2052 
2053   // Flags are intersected from the 2 source binops. But there are 2 exceptions:
2054   // 1. If we changed an opcode, poison conditions might have changed.
2055   // 2. If the shuffle had undef mask elements, the new binop might have undefs
2056   //    where the original code did not. But if we already made a safe constant,
2057   //    then there's no danger.
2058   NewBO->copyIRFlags(B0);
2059   NewBO->andIRFlags(B1);
2060   if (DropNSW)
2061     NewBO->setHasNoSignedWrap(false);
2062   if (is_contained(Mask, UndefMaskElem) && !MightCreatePoisonOrUB)
2063     NewBO->dropPoisonGeneratingFlags();
2064   return NewBO;
2065 }
2066 
2067 /// Convert a narrowing shuffle of a bitcasted vector into a vector truncate.
2068 /// Example (little endian):
2069 /// shuf (bitcast <4 x i16> X to <8 x i8>), <0, 2, 4, 6> --> trunc X to <4 x i8>
2070 static Instruction *foldTruncShuffle(ShuffleVectorInst &Shuf,
2071                                      bool IsBigEndian) {
2072   // This must be a bitcasted shuffle of 1 vector integer operand.
2073   Type *DestType = Shuf.getType();
2074   Value *X;
2075   if (!match(Shuf.getOperand(0), m_BitCast(m_Value(X))) ||
2076       !match(Shuf.getOperand(1), m_Undef()) || !DestType->isIntOrIntVectorTy())
2077     return nullptr;
2078 
2079   // The source type must have the same number of elements as the shuffle,
2080   // and the source element type must be larger than the shuffle element type.
2081   Type *SrcType = X->getType();
2082   if (!SrcType->isVectorTy() || !SrcType->isIntOrIntVectorTy() ||
2083       cast<FixedVectorType>(SrcType)->getNumElements() !=
2084           cast<FixedVectorType>(DestType)->getNumElements() ||
2085       SrcType->getScalarSizeInBits() % DestType->getScalarSizeInBits() != 0)
2086     return nullptr;
2087 
2088   assert(Shuf.changesLength() && !Shuf.increasesLength() &&
2089          "Expected a shuffle that decreases length");
2090 
2091   // Last, check that the mask chooses the correct low bits for each narrow
2092   // element in the result.
2093   uint64_t TruncRatio =
2094       SrcType->getScalarSizeInBits() / DestType->getScalarSizeInBits();
2095   ArrayRef<int> Mask = Shuf.getShuffleMask();
2096   for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
2097     if (Mask[i] == UndefMaskElem)
2098       continue;
2099     uint64_t LSBIndex = IsBigEndian ? (i + 1) * TruncRatio - 1 : i * TruncRatio;
2100     assert(LSBIndex <= INT32_MAX && "Overflowed 32-bits");
2101     if (Mask[i] != (int)LSBIndex)
2102       return nullptr;
2103   }
2104 
2105   return new TruncInst(X, DestType);
2106 }
2107 
2108 /// Match a shuffle-select-shuffle pattern where the shuffles are widening and
2109 /// narrowing (concatenating with undef and extracting back to the original
2110 /// length). This allows replacing the wide select with a narrow select.
2111 static Instruction *narrowVectorSelect(ShuffleVectorInst &Shuf,
2112                                        InstCombiner::BuilderTy &Builder) {
2113   // This must be a narrowing identity shuffle. It extracts the 1st N elements
2114   // of the 1st vector operand of a shuffle.
2115   if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
2116     return nullptr;
2117 
2118   // The vector being shuffled must be a vector select that we can eliminate.
2119   // TODO: The one-use requirement could be eased if X and/or Y are constants.
2120   Value *Cond, *X, *Y;
2121   if (!match(Shuf.getOperand(0),
2122              m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
2123     return nullptr;
2124 
2125   // We need a narrow condition value. It must be extended with undef elements
2126   // and have the same number of elements as this shuffle.
2127   unsigned NarrowNumElts =
2128       cast<FixedVectorType>(Shuf.getType())->getNumElements();
2129   Value *NarrowCond;
2130   if (!match(Cond, m_OneUse(m_Shuffle(m_Value(NarrowCond), m_Undef()))) ||
2131       cast<FixedVectorType>(NarrowCond->getType())->getNumElements() !=
2132           NarrowNumElts ||
2133       !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
2134     return nullptr;
2135 
2136   // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
2137   // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
2138   Value *NarrowX = Builder.CreateShuffleVector(X, Shuf.getShuffleMask());
2139   Value *NarrowY = Builder.CreateShuffleVector(Y, Shuf.getShuffleMask());
2140   return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
2141 }
2142 
2143 /// Try to fold an extract subvector operation.
2144 static Instruction *foldIdentityExtractShuffle(ShuffleVectorInst &Shuf) {
2145   Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
2146   if (!Shuf.isIdentityWithExtract() || !match(Op1, m_Undef()))
2147     return nullptr;
2148 
2149   // Check if we are extracting all bits of an inserted scalar:
2150   // extract-subvec (bitcast (inselt ?, X, 0) --> bitcast X to subvec type
2151   Value *X;
2152   if (match(Op0, m_BitCast(m_InsertElt(m_Value(), m_Value(X), m_Zero()))) &&
2153       X->getType()->getPrimitiveSizeInBits() ==
2154           Shuf.getType()->getPrimitiveSizeInBits())
2155     return new BitCastInst(X, Shuf.getType());
2156 
2157   // Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
2158   Value *Y;
2159   ArrayRef<int> Mask;
2160   if (!match(Op0, m_Shuffle(m_Value(X), m_Value(Y), m_Mask(Mask))))
2161     return nullptr;
2162 
2163   // Be conservative with shuffle transforms. If we can't kill the 1st shuffle,
2164   // then combining may result in worse codegen.
2165   if (!Op0->hasOneUse())
2166     return nullptr;
2167 
2168   // We are extracting a subvector from a shuffle. Remove excess elements from
2169   // the 1st shuffle mask to eliminate the extract.
2170   //
2171   // This transform is conservatively limited to identity extracts because we do
2172   // not allow arbitrary shuffle mask creation as a target-independent transform
2173   // (because we can't guarantee that will lower efficiently).
2174   //
2175   // If the extracting shuffle has an undef mask element, it transfers to the
2176   // new shuffle mask. Otherwise, copy the original mask element. Example:
2177   //   shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
2178   //   shuf X, Y, <C0, undef, C2, undef>
2179   unsigned NumElts = cast<FixedVectorType>(Shuf.getType())->getNumElements();
2180   SmallVector<int, 16> NewMask(NumElts);
2181   assert(NumElts < Mask.size() &&
2182          "Identity with extract must have less elements than its inputs");
2183 
2184   for (unsigned i = 0; i != NumElts; ++i) {
2185     int ExtractMaskElt = Shuf.getMaskValue(i);
2186     int MaskElt = Mask[i];
2187     NewMask[i] = ExtractMaskElt == UndefMaskElem ? ExtractMaskElt : MaskElt;
2188   }
2189   return new ShuffleVectorInst(X, Y, NewMask);
2190 }
2191 
2192 /// Try to replace a shuffle with an insertelement or try to replace a shuffle
2193 /// operand with the operand of an insertelement.
2194 static Instruction *foldShuffleWithInsert(ShuffleVectorInst &Shuf,
2195                                           InstCombinerImpl &IC) {
2196   Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1);
2197   SmallVector<int, 16> Mask;
2198   Shuf.getShuffleMask(Mask);
2199 
2200   // The shuffle must not change vector sizes.
2201   // TODO: This restriction could be removed if the insert has only one use
2202   //       (because the transform would require a new length-changing shuffle).
2203   int NumElts = Mask.size();
2204   if (NumElts != (int)(cast<FixedVectorType>(V0->getType())->getNumElements()))
2205     return nullptr;
2206 
2207   // This is a specialization of a fold in SimplifyDemandedVectorElts. We may
2208   // not be able to handle it there if the insertelement has >1 use.
2209   // If the shuffle has an insertelement operand but does not choose the
2210   // inserted scalar element from that value, then we can replace that shuffle
2211   // operand with the source vector of the insertelement.
2212   Value *X;
2213   uint64_t IdxC;
2214   if (match(V0, m_InsertElt(m_Value(X), m_Value(), m_ConstantInt(IdxC)))) {
2215     // shuf (inselt X, ?, IdxC), ?, Mask --> shuf X, ?, Mask
2216     if (!is_contained(Mask, (int)IdxC))
2217       return IC.replaceOperand(Shuf, 0, X);
2218   }
2219   if (match(V1, m_InsertElt(m_Value(X), m_Value(), m_ConstantInt(IdxC)))) {
2220     // Offset the index constant by the vector width because we are checking for
2221     // accesses to the 2nd vector input of the shuffle.
2222     IdxC += NumElts;
2223     // shuf ?, (inselt X, ?, IdxC), Mask --> shuf ?, X, Mask
2224     if (!is_contained(Mask, (int)IdxC))
2225       return IC.replaceOperand(Shuf, 1, X);
2226   }
2227 
2228   // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
2229   auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
2230     // We need an insertelement with a constant index.
2231     if (!match(V0, m_InsertElt(m_Value(), m_Value(Scalar),
2232                                m_ConstantInt(IndexC))))
2233       return false;
2234 
2235     // Test the shuffle mask to see if it splices the inserted scalar into the
2236     // operand 1 vector of the shuffle.
2237     int NewInsIndex = -1;
2238     for (int i = 0; i != NumElts; ++i) {
2239       // Ignore undef mask elements.
2240       if (Mask[i] == -1)
2241         continue;
2242 
2243       // The shuffle takes elements of operand 1 without lane changes.
2244       if (Mask[i] == NumElts + i)
2245         continue;
2246 
2247       // The shuffle must choose the inserted scalar exactly once.
2248       if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
2249         return false;
2250 
2251       // The shuffle is placing the inserted scalar into element i.
2252       NewInsIndex = i;
2253     }
2254 
2255     assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?");
2256 
2257     // Index is updated to the potentially translated insertion lane.
2258     IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex);
2259     return true;
2260   };
2261 
2262   // If the shuffle is unnecessary, insert the scalar operand directly into
2263   // operand 1 of the shuffle. Example:
2264   // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
2265   Value *Scalar;
2266   ConstantInt *IndexC;
2267   if (isShufflingScalarIntoOp1(Scalar, IndexC))
2268     return InsertElementInst::Create(V1, Scalar, IndexC);
2269 
2270   // Try again after commuting shuffle. Example:
2271   // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
2272   // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
2273   std::swap(V0, V1);
2274   ShuffleVectorInst::commuteShuffleMask(Mask, NumElts);
2275   if (isShufflingScalarIntoOp1(Scalar, IndexC))
2276     return InsertElementInst::Create(V1, Scalar, IndexC);
2277 
2278   return nullptr;
2279 }
2280 
2281 static Instruction *foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf) {
2282   // Match the operands as identity with padding (also known as concatenation
2283   // with undef) shuffles of the same source type. The backend is expected to
2284   // recreate these concatenations from a shuffle of narrow operands.
2285   auto *Shuffle0 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(0));
2286   auto *Shuffle1 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(1));
2287   if (!Shuffle0 || !Shuffle0->isIdentityWithPadding() ||
2288       !Shuffle1 || !Shuffle1->isIdentityWithPadding())
2289     return nullptr;
2290 
2291   // We limit this transform to power-of-2 types because we expect that the
2292   // backend can convert the simplified IR patterns to identical nodes as the
2293   // original IR.
2294   // TODO: If we can verify the same behavior for arbitrary types, the
2295   //       power-of-2 checks can be removed.
2296   Value *X = Shuffle0->getOperand(0);
2297   Value *Y = Shuffle1->getOperand(0);
2298   if (X->getType() != Y->getType() ||
2299       !isPowerOf2_32(cast<FixedVectorType>(Shuf.getType())->getNumElements()) ||
2300       !isPowerOf2_32(
2301           cast<FixedVectorType>(Shuffle0->getType())->getNumElements()) ||
2302       !isPowerOf2_32(cast<FixedVectorType>(X->getType())->getNumElements()) ||
2303       match(X, m_Undef()) || match(Y, m_Undef()))
2304     return nullptr;
2305   assert(match(Shuffle0->getOperand(1), m_Undef()) &&
2306          match(Shuffle1->getOperand(1), m_Undef()) &&
2307          "Unexpected operand for identity shuffle");
2308 
2309   // This is a shuffle of 2 widening shuffles. We can shuffle the narrow source
2310   // operands directly by adjusting the shuffle mask to account for the narrower
2311   // types:
2312   // shuf (widen X), (widen Y), Mask --> shuf X, Y, Mask'
2313   int NarrowElts = cast<FixedVectorType>(X->getType())->getNumElements();
2314   int WideElts = cast<FixedVectorType>(Shuffle0->getType())->getNumElements();
2315   assert(WideElts > NarrowElts && "Unexpected types for identity with padding");
2316 
2317   ArrayRef<int> Mask = Shuf.getShuffleMask();
2318   SmallVector<int, 16> NewMask(Mask.size(), -1);
2319   for (int i = 0, e = Mask.size(); i != e; ++i) {
2320     if (Mask[i] == -1)
2321       continue;
2322 
2323     // If this shuffle is choosing an undef element from 1 of the sources, that
2324     // element is undef.
2325     if (Mask[i] < WideElts) {
2326       if (Shuffle0->getMaskValue(Mask[i]) == -1)
2327         continue;
2328     } else {
2329       if (Shuffle1->getMaskValue(Mask[i] - WideElts) == -1)
2330         continue;
2331     }
2332 
2333     // If this shuffle is choosing from the 1st narrow op, the mask element is
2334     // the same. If this shuffle is choosing from the 2nd narrow op, the mask
2335     // element is offset down to adjust for the narrow vector widths.
2336     if (Mask[i] < WideElts) {
2337       assert(Mask[i] < NarrowElts && "Unexpected shuffle mask");
2338       NewMask[i] = Mask[i];
2339     } else {
2340       assert(Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask");
2341       NewMask[i] = Mask[i] - (WideElts - NarrowElts);
2342     }
2343   }
2344   return new ShuffleVectorInst(X, Y, NewMask);
2345 }
2346 
2347 Instruction *InstCombinerImpl::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
2348   Value *LHS = SVI.getOperand(0);
2349   Value *RHS = SVI.getOperand(1);
2350   SimplifyQuery ShufQuery = SQ.getWithInstruction(&SVI);
2351   if (auto *V = SimplifyShuffleVectorInst(LHS, RHS, SVI.getShuffleMask(),
2352                                           SVI.getType(), ShufQuery))
2353     return replaceInstUsesWith(SVI, V);
2354 
2355   // Bail out for scalable vectors
2356   if (isa<ScalableVectorType>(LHS->getType()))
2357     return nullptr;
2358 
2359   unsigned VWidth = cast<FixedVectorType>(SVI.getType())->getNumElements();
2360   unsigned LHSWidth = cast<FixedVectorType>(LHS->getType())->getNumElements();
2361 
2362   // shuffle (bitcast X), (bitcast Y), Mask --> bitcast (shuffle X, Y, Mask)
2363   //
2364   // if X and Y are of the same (vector) type, and the element size is not
2365   // changed by the bitcasts, we can distribute the bitcasts through the
2366   // shuffle, hopefully reducing the number of instructions. We make sure that
2367   // at least one bitcast only has one use, so we don't *increase* the number of
2368   // instructions here.
2369   Value *X, *Y;
2370   if (match(LHS, m_BitCast(m_Value(X))) && match(RHS, m_BitCast(m_Value(Y))) &&
2371       X->getType()->isVectorTy() && X->getType() == Y->getType() &&
2372       X->getType()->getScalarSizeInBits() ==
2373           SVI.getType()->getScalarSizeInBits() &&
2374       (LHS->hasOneUse() || RHS->hasOneUse())) {
2375     Value *V = Builder.CreateShuffleVector(X, Y, SVI.getShuffleMask(),
2376                                            SVI.getName() + ".uncasted");
2377     return new BitCastInst(V, SVI.getType());
2378   }
2379 
2380   ArrayRef<int> Mask = SVI.getShuffleMask();
2381   Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
2382 
2383   // Peek through a bitcasted shuffle operand by scaling the mask. If the
2384   // simulated shuffle can simplify, then this shuffle is unnecessary:
2385   // shuf (bitcast X), undef, Mask --> bitcast X'
2386   // TODO: This could be extended to allow length-changing shuffles.
2387   //       The transform might also be obsoleted if we allowed canonicalization
2388   //       of bitcasted shuffles.
2389   if (match(LHS, m_BitCast(m_Value(X))) && match(RHS, m_Undef()) &&
2390       X->getType()->isVectorTy() && VWidth == LHSWidth) {
2391     // Try to create a scaled mask constant.
2392     auto *XType = cast<FixedVectorType>(X->getType());
2393     unsigned XNumElts = XType->getNumElements();
2394     SmallVector<int, 16> ScaledMask;
2395     if (XNumElts >= VWidth) {
2396       assert(XNumElts % VWidth == 0 && "Unexpected vector bitcast");
2397       narrowShuffleMaskElts(XNumElts / VWidth, Mask, ScaledMask);
2398     } else {
2399       assert(VWidth % XNumElts == 0 && "Unexpected vector bitcast");
2400       if (!widenShuffleMaskElts(VWidth / XNumElts, Mask, ScaledMask))
2401         ScaledMask.clear();
2402     }
2403     if (!ScaledMask.empty()) {
2404       // If the shuffled source vector simplifies, cast that value to this
2405       // shuffle's type.
2406       if (auto *V = SimplifyShuffleVectorInst(X, UndefValue::get(XType),
2407                                               ScaledMask, XType, ShufQuery))
2408         return BitCastInst::Create(Instruction::BitCast, V, SVI.getType());
2409     }
2410   }
2411 
2412   // shuffle x, x, mask --> shuffle x, undef, mask'
2413   if (LHS == RHS) {
2414     assert(!match(RHS, m_Undef()) &&
2415            "Shuffle with 2 undef ops not simplified?");
2416     // Remap any references to RHS to use LHS.
2417     SmallVector<int, 16> Elts;
2418     for (unsigned i = 0; i != VWidth; ++i) {
2419       // Propagate undef elements or force mask to LHS.
2420       if (Mask[i] < 0)
2421         Elts.push_back(UndefMaskElem);
2422       else
2423         Elts.push_back(Mask[i] % LHSWidth);
2424     }
2425     return new ShuffleVectorInst(LHS, UndefValue::get(RHS->getType()), Elts);
2426   }
2427 
2428   // shuffle undef, x, mask --> shuffle x, undef, mask'
2429   if (match(LHS, m_Undef())) {
2430     SVI.commute();
2431     return &SVI;
2432   }
2433 
2434   if (Instruction *I = canonicalizeInsertSplat(SVI, Builder))
2435     return I;
2436 
2437   if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
2438     return I;
2439 
2440   if (Instruction *I = foldTruncShuffle(SVI, DL.isBigEndian()))
2441     return I;
2442 
2443   if (Instruction *I = narrowVectorSelect(SVI, Builder))
2444     return I;
2445 
2446   APInt UndefElts(VWidth, 0);
2447   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
2448   if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
2449     if (V != &SVI)
2450       return replaceInstUsesWith(SVI, V);
2451     return &SVI;
2452   }
2453 
2454   if (Instruction *I = foldIdentityExtractShuffle(SVI))
2455     return I;
2456 
2457   // These transforms have the potential to lose undef knowledge, so they are
2458   // intentionally placed after SimplifyDemandedVectorElts().
2459   if (Instruction *I = foldShuffleWithInsert(SVI, *this))
2460     return I;
2461   if (Instruction *I = foldIdentityPaddedShuffles(SVI))
2462     return I;
2463 
2464   if (match(RHS, m_Undef()) && canEvaluateShuffled(LHS, Mask)) {
2465     Value *V = evaluateInDifferentElementOrder(LHS, Mask);
2466     return replaceInstUsesWith(SVI, V);
2467   }
2468 
2469   // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
2470   // a non-vector type. We can instead bitcast the original vector followed by
2471   // an extract of the desired element:
2472   //
2473   //   %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
2474   //                         <4 x i32> <i32 0, i32 1, i32 2, i32 3>
2475   //   %1 = bitcast <4 x i8> %sroa to i32
2476   // Becomes:
2477   //   %bc = bitcast <16 x i8> %in to <4 x i32>
2478   //   %ext = extractelement <4 x i32> %bc, i32 0
2479   //
2480   // If the shuffle is extracting a contiguous range of values from the input
2481   // vector then each use which is a bitcast of the extracted size can be
2482   // replaced. This will work if the vector types are compatible, and the begin
2483   // index is aligned to a value in the casted vector type. If the begin index
2484   // isn't aligned then we can shuffle the original vector (keeping the same
2485   // vector type) before extracting.
2486   //
2487   // This code will bail out if the target type is fundamentally incompatible
2488   // with vectors of the source type.
2489   //
2490   // Example of <16 x i8>, target type i32:
2491   // Index range [4,8):         v-----------v Will work.
2492   //                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
2493   //     <16 x i8>: |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
2494   //     <4 x i32>: |           |           |           |           |
2495   //                +-----------+-----------+-----------+-----------+
2496   // Index range [6,10):              ^-----------^ Needs an extra shuffle.
2497   // Target type i40:           ^--------------^ Won't work, bail.
2498   bool MadeChange = false;
2499   if (isShuffleExtractingFromLHS(SVI, Mask)) {
2500     Value *V = LHS;
2501     unsigned MaskElems = Mask.size();
2502     auto *SrcTy = cast<FixedVectorType>(V->getType());
2503     unsigned VecBitWidth = SrcTy->getPrimitiveSizeInBits().getFixedSize();
2504     unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
2505     assert(SrcElemBitWidth && "vector elements must have a bitwidth");
2506     unsigned SrcNumElems = SrcTy->getNumElements();
2507     SmallVector<BitCastInst *, 8> BCs;
2508     DenseMap<Type *, Value *> NewBCs;
2509     for (User *U : SVI.users())
2510       if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
2511         if (!BC->use_empty())
2512           // Only visit bitcasts that weren't previously handled.
2513           BCs.push_back(BC);
2514     for (BitCastInst *BC : BCs) {
2515       unsigned BegIdx = Mask.front();
2516       Type *TgtTy = BC->getDestTy();
2517       unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
2518       if (!TgtElemBitWidth)
2519         continue;
2520       unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
2521       bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
2522       bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
2523       if (!VecBitWidthsEqual)
2524         continue;
2525       if (!VectorType::isValidElementType(TgtTy))
2526         continue;
2527       auto *CastSrcTy = FixedVectorType::get(TgtTy, TgtNumElems);
2528       if (!BegIsAligned) {
2529         // Shuffle the input so [0,NumElements) contains the output, and
2530         // [NumElems,SrcNumElems) is undef.
2531         SmallVector<int, 16> ShuffleMask(SrcNumElems, -1);
2532         for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
2533           ShuffleMask[I] = Idx;
2534         V = Builder.CreateShuffleVector(V, ShuffleMask,
2535                                         SVI.getName() + ".extract");
2536         BegIdx = 0;
2537       }
2538       unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
2539       assert(SrcElemsPerTgtElem);
2540       BegIdx /= SrcElemsPerTgtElem;
2541       bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
2542       auto *NewBC =
2543           BCAlreadyExists
2544               ? NewBCs[CastSrcTy]
2545               : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
2546       if (!BCAlreadyExists)
2547         NewBCs[CastSrcTy] = NewBC;
2548       auto *Ext = Builder.CreateExtractElement(
2549           NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
2550       // The shufflevector isn't being replaced: the bitcast that used it
2551       // is. InstCombine will visit the newly-created instructions.
2552       replaceInstUsesWith(*BC, Ext);
2553       MadeChange = true;
2554     }
2555   }
2556 
2557   // If the LHS is a shufflevector itself, see if we can combine it with this
2558   // one without producing an unusual shuffle.
2559   // Cases that might be simplified:
2560   // 1.
2561   // x1=shuffle(v1,v2,mask1)
2562   //  x=shuffle(x1,undef,mask)
2563   //        ==>
2564   //  x=shuffle(v1,undef,newMask)
2565   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
2566   // 2.
2567   // x1=shuffle(v1,undef,mask1)
2568   //  x=shuffle(x1,x2,mask)
2569   // where v1.size() == mask1.size()
2570   //        ==>
2571   //  x=shuffle(v1,x2,newMask)
2572   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
2573   // 3.
2574   // x2=shuffle(v2,undef,mask2)
2575   //  x=shuffle(x1,x2,mask)
2576   // where v2.size() == mask2.size()
2577   //        ==>
2578   //  x=shuffle(x1,v2,newMask)
2579   // newMask[i] = (mask[i] < x1.size())
2580   //              ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
2581   // 4.
2582   // x1=shuffle(v1,undef,mask1)
2583   // x2=shuffle(v2,undef,mask2)
2584   //  x=shuffle(x1,x2,mask)
2585   // where v1.size() == v2.size()
2586   //        ==>
2587   //  x=shuffle(v1,v2,newMask)
2588   // newMask[i] = (mask[i] < x1.size())
2589   //              ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
2590   //
2591   // Here we are really conservative:
2592   // we are absolutely afraid of producing a shuffle mask not in the input
2593   // program, because the code gen may not be smart enough to turn a merged
2594   // shuffle into two specific shuffles: it may produce worse code.  As such,
2595   // we only merge two shuffles if the result is either a splat or one of the
2596   // input shuffle masks.  In this case, merging the shuffles just removes
2597   // one instruction, which we know is safe.  This is good for things like
2598   // turning: (splat(splat)) -> splat, or
2599   // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
2600   ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
2601   ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
2602   if (LHSShuffle)
2603     if (!match(LHSShuffle->getOperand(1), m_Undef()) && !match(RHS, m_Undef()))
2604       LHSShuffle = nullptr;
2605   if (RHSShuffle)
2606     if (!match(RHSShuffle->getOperand(1), m_Undef()))
2607       RHSShuffle = nullptr;
2608   if (!LHSShuffle && !RHSShuffle)
2609     return MadeChange ? &SVI : nullptr;
2610 
2611   Value* LHSOp0 = nullptr;
2612   Value* LHSOp1 = nullptr;
2613   Value* RHSOp0 = nullptr;
2614   unsigned LHSOp0Width = 0;
2615   unsigned RHSOp0Width = 0;
2616   if (LHSShuffle) {
2617     LHSOp0 = LHSShuffle->getOperand(0);
2618     LHSOp1 = LHSShuffle->getOperand(1);
2619     LHSOp0Width = cast<FixedVectorType>(LHSOp0->getType())->getNumElements();
2620   }
2621   if (RHSShuffle) {
2622     RHSOp0 = RHSShuffle->getOperand(0);
2623     RHSOp0Width = cast<FixedVectorType>(RHSOp0->getType())->getNumElements();
2624   }
2625   Value* newLHS = LHS;
2626   Value* newRHS = RHS;
2627   if (LHSShuffle) {
2628     // case 1
2629     if (match(RHS, m_Undef())) {
2630       newLHS = LHSOp0;
2631       newRHS = LHSOp1;
2632     }
2633     // case 2 or 4
2634     else if (LHSOp0Width == LHSWidth) {
2635       newLHS = LHSOp0;
2636     }
2637   }
2638   // case 3 or 4
2639   if (RHSShuffle && RHSOp0Width == LHSWidth) {
2640     newRHS = RHSOp0;
2641   }
2642   // case 4
2643   if (LHSOp0 == RHSOp0) {
2644     newLHS = LHSOp0;
2645     newRHS = nullptr;
2646   }
2647 
2648   if (newLHS == LHS && newRHS == RHS)
2649     return MadeChange ? &SVI : nullptr;
2650 
2651   ArrayRef<int> LHSMask;
2652   ArrayRef<int> RHSMask;
2653   if (newLHS != LHS)
2654     LHSMask = LHSShuffle->getShuffleMask();
2655   if (RHSShuffle && newRHS != RHS)
2656     RHSMask = RHSShuffle->getShuffleMask();
2657 
2658   unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
2659   SmallVector<int, 16> newMask;
2660   bool isSplat = true;
2661   int SplatElt = -1;
2662   // Create a new mask for the new ShuffleVectorInst so that the new
2663   // ShuffleVectorInst is equivalent to the original one.
2664   for (unsigned i = 0; i < VWidth; ++i) {
2665     int eltMask;
2666     if (Mask[i] < 0) {
2667       // This element is an undef value.
2668       eltMask = -1;
2669     } else if (Mask[i] < (int)LHSWidth) {
2670       // This element is from left hand side vector operand.
2671       //
2672       // If LHS is going to be replaced (case 1, 2, or 4), calculate the
2673       // new mask value for the element.
2674       if (newLHS != LHS) {
2675         eltMask = LHSMask[Mask[i]];
2676         // If the value selected is an undef value, explicitly specify it
2677         // with a -1 mask value.
2678         if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
2679           eltMask = -1;
2680       } else
2681         eltMask = Mask[i];
2682     } else {
2683       // This element is from right hand side vector operand
2684       //
2685       // If the value selected is an undef value, explicitly specify it
2686       // with a -1 mask value. (case 1)
2687       if (match(RHS, m_Undef()))
2688         eltMask = -1;
2689       // If RHS is going to be replaced (case 3 or 4), calculate the
2690       // new mask value for the element.
2691       else if (newRHS != RHS) {
2692         eltMask = RHSMask[Mask[i]-LHSWidth];
2693         // If the value selected is an undef value, explicitly specify it
2694         // with a -1 mask value.
2695         if (eltMask >= (int)RHSOp0Width) {
2696           assert(match(RHSShuffle->getOperand(1), m_Undef()) &&
2697                  "should have been check above");
2698           eltMask = -1;
2699         }
2700       } else
2701         eltMask = Mask[i]-LHSWidth;
2702 
2703       // If LHS's width is changed, shift the mask value accordingly.
2704       // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
2705       // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
2706       // If newRHS == newLHS, we want to remap any references from newRHS to
2707       // newLHS so that we can properly identify splats that may occur due to
2708       // obfuscation across the two vectors.
2709       if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
2710         eltMask += newLHSWidth;
2711     }
2712 
2713     // Check if this could still be a splat.
2714     if (eltMask >= 0) {
2715       if (SplatElt >= 0 && SplatElt != eltMask)
2716         isSplat = false;
2717       SplatElt = eltMask;
2718     }
2719 
2720     newMask.push_back(eltMask);
2721   }
2722 
2723   // If the result mask is equal to one of the original shuffle masks,
2724   // or is a splat, do the replacement.
2725   if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
2726     if (!newRHS)
2727       newRHS = UndefValue::get(newLHS->getType());
2728     return new ShuffleVectorInst(newLHS, newRHS, newMask);
2729   }
2730 
2731   return MadeChange ? &SVI : nullptr;
2732 }
2733