LLVM  10.0.0svn
InstCombineVectorOps.cpp
Go to the documentation of this file.
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/SmallVector.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DerivedTypes.h"
26 #include "llvm/IR/InstrTypes.h"
27 #include "llvm/IR/Instruction.h"
28 #include "llvm/IR/Instructions.h"
29 #include "llvm/IR/Operator.h"
30 #include "llvm/IR/PatternMatch.h"
31 #include "llvm/IR/Type.h"
32 #include "llvm/IR/User.h"
33 #include "llvm/IR/Value.h"
34 #include "llvm/Support/Casting.h"
37 #include <cassert>
38 #include <cstdint>
39 #include <iterator>
40 #include <utility>
41 
42 using namespace llvm;
43 using namespace PatternMatch;
44 
45 #define DEBUG_TYPE "instcombine"
46 
47 /// Return true if the value is cheaper to scalarize than it is to leave as a
48 /// vector operation. IsConstantExtractIndex indicates whether we are extracting
49 /// one known element from a vector constant.
50 ///
51 /// FIXME: It's possible to create more instructions than previously existed.
52 static bool cheapToScalarize(Value *V, bool IsConstantExtractIndex) {
53  // If we can pick a scalar constant value out of a vector, that is free.
54  if (auto *C = dyn_cast<Constant>(V))
55  return IsConstantExtractIndex || C->getSplatValue();
56 
57  // An insertelement to the same constant index as our extract will simplify
58  // to the scalar inserted element. An insertelement to a different constant
59  // index is irrelevant to our extract.
61  return IsConstantExtractIndex;
62 
63  if (match(V, m_OneUse(m_Load(m_Value()))))
64  return true;
65 
66  Value *V0, *V1;
67  if (match(V, m_OneUse(m_BinOp(m_Value(V0), m_Value(V1)))))
68  if (cheapToScalarize(V0, IsConstantExtractIndex) ||
69  cheapToScalarize(V1, IsConstantExtractIndex))
70  return true;
71 
72  CmpInst::Predicate UnusedPred;
73  if (match(V, m_OneUse(m_Cmp(UnusedPred, m_Value(V0), m_Value(V1)))))
74  if (cheapToScalarize(V0, IsConstantExtractIndex) ||
75  cheapToScalarize(V1, IsConstantExtractIndex))
76  return true;
77 
78  return false;
79 }
80 
81 // If we have a PHI node with a vector type that is only used to feed
82 // itself and be an operand of extractelement at a constant location,
83 // try to replace the PHI of the vector type with a PHI of a scalar type.
84 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
86  // The users we want the PHI to have are:
87  // 1) The EI ExtractElement (we already know this)
88  // 2) Possibly more ExtractElements with the same index.
89  // 3) Another operand, which will feed back into the PHI.
90  Instruction *PHIUser = nullptr;
91  for (auto U : PN->users()) {
92  if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
93  if (EI.getIndexOperand() == EU->getIndexOperand())
94  Extracts.push_back(EU);
95  else
96  return nullptr;
97  } else if (!PHIUser) {
98  PHIUser = cast<Instruction>(U);
99  } else {
100  return nullptr;
101  }
102  }
103 
104  if (!PHIUser)
105  return nullptr;
106 
107  // Verify that this PHI user has one use, which is the PHI itself,
108  // and that it is a binary operation which is cheap to scalarize.
109  // otherwise return nullptr.
110  if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
111  !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
112  return nullptr;
113 
114  // Create a scalar PHI node that will replace the vector PHI node
115  // just before the current PHI node.
116  PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
117  PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
118  // Scalarize each PHI operand.
119  for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
120  Value *PHIInVal = PN->getIncomingValue(i);
121  BasicBlock *inBB = PN->getIncomingBlock(i);
122  Value *Elt = EI.getIndexOperand();
123  // If the operand is the PHI induction variable:
124  if (PHIInVal == PHIUser) {
125  // Scalarize the binary operation. Its first operand is the
126  // scalar PHI, and the second operand is extracted from the other
127  // vector operand.
128  BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
129  unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
130  Value *Op = InsertNewInstWith(
131  ExtractElementInst::Create(B0->getOperand(opId), Elt,
132  B0->getOperand(opId)->getName() + ".Elt"),
133  *B0);
134  Value *newPHIUser = InsertNewInstWith(
136  scalarPHI, Op, B0), *B0);
137  scalarPHI->addIncoming(newPHIUser, inBB);
138  } else {
139  // Scalarize PHI input:
140  Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
141  // Insert the new instruction into the predecessor basic block.
142  Instruction *pos = dyn_cast<Instruction>(PHIInVal);
143  BasicBlock::iterator InsertPos;
144  if (pos && !isa<PHINode>(pos)) {
145  InsertPos = ++pos->getIterator();
146  } else {
147  InsertPos = inBB->getFirstInsertionPt();
148  }
149 
150  InsertNewInstWith(newEI, *InsertPos);
151 
152  scalarPHI->addIncoming(newEI, inBB);
153  }
154  }
155 
156  for (auto E : Extracts)
157  replaceInstUsesWith(*E, scalarPHI);
158 
159  return &EI;
160 }
161 
163  InstCombiner::BuilderTy &Builder,
164  bool IsBigEndian) {
165  Value *X;
166  uint64_t ExtIndexC;
167  if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) ||
168  !X->getType()->isVectorTy() ||
169  !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC)))
170  return nullptr;
171 
172  // If this extractelement is using a bitcast from a vector of the same number
173  // of elements, see if we can find the source element from the source vector:
174  // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
175  Type *SrcTy = X->getType();
176  Type *DestTy = Ext.getType();
177  unsigned NumSrcElts = SrcTy->getVectorNumElements();
178  unsigned NumElts = Ext.getVectorOperandType()->getNumElements();
179  if (NumSrcElts == NumElts)
180  if (Value *Elt = findScalarElement(X, ExtIndexC))
181  return new BitCastInst(Elt, DestTy);
182 
183  // If the source elements are wider than the destination, try to shift and
184  // truncate a subset of scalar bits of an insert op.
185  if (NumSrcElts < NumElts) {
186  Value *Scalar;
187  uint64_t InsIndexC;
188  if (!match(X, m_InsertElement(m_Value(), m_Value(Scalar),
189  m_ConstantInt(InsIndexC))))
190  return nullptr;
191 
192  // The extract must be from the subset of vector elements that we inserted
193  // into. Example: if we inserted element 1 of a <2 x i64> and we are
194  // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
195  // of elements 4-7 of the bitcasted vector.
196  unsigned NarrowingRatio = NumElts / NumSrcElts;
197  if (ExtIndexC / NarrowingRatio != InsIndexC)
198  return nullptr;
199 
200  // We are extracting part of the original scalar. How that scalar is
201  // inserted into the vector depends on the endian-ness. Example:
202  // Vector Byte Elt Index: 0 1 2 3 4 5 6 7
203  // +--+--+--+--+--+--+--+--+
204  // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3|
205  // extelt <4 x i16> V', 3: | |S2|S3|
206  // +--+--+--+--+--+--+--+--+
207  // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
208  // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
209  // In this example, we must right-shift little-endian. Big-endian is just a
210  // truncate.
211  unsigned Chunk = ExtIndexC % NarrowingRatio;
212  if (IsBigEndian)
213  Chunk = NarrowingRatio - 1 - Chunk;
214 
215  // Bail out if this is an FP vector to FP vector sequence. That would take
216  // more instructions than we started with unless there is no shift, and it
217  // may not be handled as well in the backend.
218  bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
219  bool NeedDestBitcast = DestTy->isFloatingPointTy();
220  if (NeedSrcBitcast && NeedDestBitcast)
221  return nullptr;
222 
223  unsigned SrcWidth = SrcTy->getScalarSizeInBits();
224  unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
225  unsigned ShAmt = Chunk * DestWidth;
226 
227  // TODO: This limitation is more strict than necessary. We could sum the
228  // number of new instructions and subtract the number eliminated to know if
229  // we can proceed.
230  if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
231  if (NeedSrcBitcast || NeedDestBitcast)
232  return nullptr;
233 
234  if (NeedSrcBitcast) {
235  Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth);
236  Scalar = Builder.CreateBitCast(Scalar, SrcIntTy);
237  }
238 
239  if (ShAmt) {
240  // Bail out if we could end with more instructions than we started with.
241  if (!Ext.getVectorOperand()->hasOneUse())
242  return nullptr;
243  Scalar = Builder.CreateLShr(Scalar, ShAmt);
244  }
245 
246  if (NeedDestBitcast) {
247  Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth);
248  return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy);
249  }
250  return new TruncInst(Scalar, DestTy);
251  }
252 
253  return nullptr;
254 }
255 
256 /// Find elements of V demanded by UserInstr.
258  unsigned VWidth = V->getType()->getVectorNumElements();
259 
260  // Conservatively assume that all elements are needed.
261  APInt UsedElts(APInt::getAllOnesValue(VWidth));
262 
263  switch (UserInstr->getOpcode()) {
264  case Instruction::ExtractElement: {
265  ExtractElementInst *EEI = cast<ExtractElementInst>(UserInstr);
266  assert(EEI->getVectorOperand() == V);
267  ConstantInt *EEIIndexC = dyn_cast<ConstantInt>(EEI->getIndexOperand());
268  if (EEIIndexC && EEIIndexC->getValue().ult(VWidth)) {
269  UsedElts = APInt::getOneBitSet(VWidth, EEIIndexC->getZExtValue());
270  }
271  break;
272  }
273  case Instruction::ShuffleVector: {
274  ShuffleVectorInst *Shuffle = cast<ShuffleVectorInst>(UserInstr);
275  unsigned MaskNumElts = UserInstr->getType()->getVectorNumElements();
276 
277  UsedElts = APInt(VWidth, 0);
278  for (unsigned i = 0; i < MaskNumElts; i++) {
279  unsigned MaskVal = Shuffle->getMaskValue(i);
280  if (MaskVal == -1u || MaskVal >= 2 * VWidth)
281  continue;
282  if (Shuffle->getOperand(0) == V && (MaskVal < VWidth))
283  UsedElts.setBit(MaskVal);
284  if (Shuffle->getOperand(1) == V &&
285  ((MaskVal >= VWidth) && (MaskVal < 2 * VWidth)))
286  UsedElts.setBit(MaskVal - VWidth);
287  }
288  break;
289  }
290  default:
291  break;
292  }
293  return UsedElts;
294 }
295 
296 /// Find union of elements of V demanded by all its users.
297 /// If it is known by querying findDemandedEltsBySingleUser that
298 /// no user demands an element of V, then the corresponding bit
299 /// remains unset in the returned value.
301  unsigned VWidth = V->getType()->getVectorNumElements();
302 
303  APInt UnionUsedElts(VWidth, 0);
304  for (const Use &U : V->uses()) {
305  if (Instruction *I = dyn_cast<Instruction>(U.getUser())) {
306  UnionUsedElts |= findDemandedEltsBySingleUser(V, I);
307  } else {
308  UnionUsedElts = APInt::getAllOnesValue(VWidth);
309  break;
310  }
311 
312  if (UnionUsedElts.isAllOnesValue())
313  break;
314  }
315 
316  return UnionUsedElts;
317 }
318 
320  Value *SrcVec = EI.getVectorOperand();
321  Value *Index = EI.getIndexOperand();
322  if (Value *V = SimplifyExtractElementInst(SrcVec, Index,
323  SQ.getWithInstruction(&EI)))
324  return replaceInstUsesWith(EI, V);
325 
326  // If extracting a specified index from the vector, see if we can recursively
327  // find a previously computed scalar that was inserted into the vector.
328  auto *IndexC = dyn_cast<ConstantInt>(Index);
329  if (IndexC) {
330  unsigned NumElts = EI.getVectorOperandType()->getNumElements();
331 
332  // InstSimplify should handle cases where the index is invalid.
333  if (!IndexC->getValue().ule(NumElts))
334  return nullptr;
335 
336  // This instruction only demands the single element from the input vector.
337  if (NumElts != 1) {
338  // If the input vector has a single use, simplify it based on this use
339  // property.
340  if (SrcVec->hasOneUse()) {
341  APInt UndefElts(NumElts, 0);
342  APInt DemandedElts(NumElts, 0);
343  DemandedElts.setBit(IndexC->getZExtValue());
344  if (Value *V =
345  SimplifyDemandedVectorElts(SrcVec, DemandedElts, UndefElts)) {
346  EI.setOperand(0, V);
347  return &EI;
348  }
349  } else {
350  // If the input vector has multiple uses, simplify it based on a union
351  // of all elements used.
352  APInt DemandedElts = findDemandedEltsByAllUsers(SrcVec);
353  if (!DemandedElts.isAllOnesValue()) {
354  APInt UndefElts(NumElts, 0);
355  if (Value *V = SimplifyDemandedVectorElts(
356  SrcVec, DemandedElts, UndefElts, 0 /* Depth */,
357  true /* AllowMultipleUsers */)) {
358  if (V != SrcVec) {
359  SrcVec->replaceAllUsesWith(V);
360  return &EI;
361  }
362  }
363  }
364  }
365  }
366  if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
367  return I;
368 
369  // If there's a vector PHI feeding a scalar use through this extractelement
370  // instruction, try to scalarize the PHI.
371  if (auto *Phi = dyn_cast<PHINode>(SrcVec))
372  if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
373  return ScalarPHI;
374  }
375 
376  BinaryOperator *BO;
377  if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) {
378  // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
379  Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
380  Value *E0 = Builder.CreateExtractElement(X, Index);
381  Value *E1 = Builder.CreateExtractElement(Y, Index);
382  return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO);
383  }
384 
385  Value *X, *Y;
386  CmpInst::Predicate Pred;
387  if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) &&
388  cheapToScalarize(SrcVec, IndexC)) {
389  // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
390  Value *E0 = Builder.CreateExtractElement(X, Index);
391  Value *E1 = Builder.CreateExtractElement(Y, Index);
392  return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1);
393  }
394 
395  if (auto *I = dyn_cast<Instruction>(SrcVec)) {
396  if (auto *IE = dyn_cast<InsertElementInst>(I)) {
397  // Extracting the inserted element?
398  if (IE->getOperand(2) == Index)
399  return replaceInstUsesWith(EI, IE->getOperand(1));
400  // If the inserted and extracted elements are constants, they must not
401  // be the same value, extract from the pre-inserted value instead.
402  if (isa<Constant>(IE->getOperand(2)) && IndexC) {
403  Worklist.AddValue(SrcVec);
404  EI.setOperand(0, IE->getOperand(0));
405  return &EI;
406  }
407  } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
408  // If this is extracting an element from a shufflevector, figure out where
409  // it came from and extract from the appropriate input element instead.
410  if (auto *Elt = dyn_cast<ConstantInt>(Index)) {
411  int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
412  Value *Src;
413  unsigned LHSWidth =
414  SVI->getOperand(0)->getType()->getVectorNumElements();
415 
416  if (SrcIdx < 0)
417  return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
418  if (SrcIdx < (int)LHSWidth)
419  Src = SVI->getOperand(0);
420  else {
421  SrcIdx -= LHSWidth;
422  Src = SVI->getOperand(1);
423  }
425  return ExtractElementInst::Create(Src,
426  ConstantInt::get(Int32Ty,
427  SrcIdx, false));
428  }
429  } else if (auto *CI = dyn_cast<CastInst>(I)) {
430  // Canonicalize extractelement(cast) -> cast(extractelement).
431  // Bitcasts can change the number of vector elements, and they cost
432  // nothing.
433  if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
434  Value *EE = Builder.CreateExtractElement(CI->getOperand(0), Index);
435  Worklist.AddValue(EE);
436  return CastInst::Create(CI->getOpcode(), EE, EI.getType());
437  }
438  }
439  }
440  return nullptr;
441 }
442 
443 /// If V is a shuffle of values that ONLY returns elements from either LHS or
444 /// RHS, return the shuffle mask and true. Otherwise, return false.
445 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
447  assert(LHS->getType() == RHS->getType() &&
448  "Invalid CollectSingleShuffleElements");
449  unsigned NumElts = V->getType()->getVectorNumElements();
450 
451  if (isa<UndefValue>(V)) {
452  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
453  return true;
454  }
455 
456  if (V == LHS) {
457  for (unsigned i = 0; i != NumElts; ++i)
459  return true;
460  }
461 
462  if (V == RHS) {
463  for (unsigned i = 0; i != NumElts; ++i)
465  i+NumElts));
466  return true;
467  }
468 
469  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
470  // If this is an insert of an extract from some other vector, include it.
471  Value *VecOp = IEI->getOperand(0);
472  Value *ScalarOp = IEI->getOperand(1);
473  Value *IdxOp = IEI->getOperand(2);
474 
475  if (!isa<ConstantInt>(IdxOp))
476  return false;
477  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
478 
479  if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
480  // We can handle this if the vector we are inserting into is
481  // transitively ok.
482  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
483  // If so, update the mask to reflect the inserted undef.
484  Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
485  return true;
486  }
487  } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
488  if (isa<ConstantInt>(EI->getOperand(1))) {
489  unsigned ExtractedIdx =
490  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
491  unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
492 
493  // This must be extracting from either LHS or RHS.
494  if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
495  // We can handle this if the vector we are inserting into is
496  // transitively ok.
497  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
498  // If so, update the mask to reflect the inserted value.
499  if (EI->getOperand(0) == LHS) {
500  Mask[InsertedIdx % NumElts] =
502  ExtractedIdx);
503  } else {
504  assert(EI->getOperand(0) == RHS);
505  Mask[InsertedIdx % NumElts] =
507  ExtractedIdx + NumLHSElts);
508  }
509  return true;
510  }
511  }
512  }
513  }
514  }
515 
516  return false;
517 }
518 
519 /// If we have insertion into a vector that is wider than the vector that we
520 /// are extracting from, try to widen the source vector to allow a single
521 /// shufflevector to replace one or more insert/extract pairs.
523  ExtractElementInst *ExtElt,
524  InstCombiner &IC) {
525  VectorType *InsVecType = InsElt->getType();
526  VectorType *ExtVecType = ExtElt->getVectorOperandType();
527  unsigned NumInsElts = InsVecType->getVectorNumElements();
528  unsigned NumExtElts = ExtVecType->getVectorNumElements();
529 
530  // The inserted-to vector must be wider than the extracted-from vector.
531  if (InsVecType->getElementType() != ExtVecType->getElementType() ||
532  NumExtElts >= NumInsElts)
533  return;
534 
535  // Create a shuffle mask to widen the extended-from vector using undefined
536  // values. The mask selects all of the values of the original vector followed
537  // by as many undefined values as needed to create a vector of the same length
538  // as the inserted-to vector.
539  SmallVector<Constant *, 16> ExtendMask;
540  IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
541  for (unsigned i = 0; i < NumExtElts; ++i)
542  ExtendMask.push_back(ConstantInt::get(IntType, i));
543  for (unsigned i = NumExtElts; i < NumInsElts; ++i)
544  ExtendMask.push_back(UndefValue::get(IntType));
545 
546  Value *ExtVecOp = ExtElt->getVectorOperand();
547  auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
548  BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
549  ? ExtVecOpInst->getParent()
550  : ExtElt->getParent();
551 
552  // TODO: This restriction matches the basic block check below when creating
553  // new extractelement instructions. If that limitation is removed, this one
554  // could also be removed. But for now, we just bail out to ensure that we
555  // will replace the extractelement instruction that is feeding our
556  // insertelement instruction. This allows the insertelement to then be
557  // replaced by a shufflevector. If the insertelement is not replaced, we can
558  // induce infinite looping because there's an optimization for extractelement
559  // that will delete our widening shuffle. This would trigger another attempt
560  // here to create that shuffle, and we spin forever.
561  if (InsertionBlock != InsElt->getParent())
562  return;
563 
564  // TODO: This restriction matches the check in visitInsertElementInst() and
565  // prevents an infinite loop caused by not turning the extract/insert pair
566  // into a shuffle. We really should not need either check, but we're lacking
567  // folds for shufflevectors because we're afraid to generate shuffle masks
568  // that the backend can't handle.
569  if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
570  return;
571 
572  auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
573  ConstantVector::get(ExtendMask));
574 
575  // Insert the new shuffle after the vector operand of the extract is defined
576  // (as long as it's not a PHI) or at the start of the basic block of the
577  // extract, so any subsequent extracts in the same basic block can use it.
578  // TODO: Insert before the earliest ExtractElementInst that is replaced.
579  if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
580  WideVec->insertAfter(ExtVecOpInst);
581  else
582  IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
583 
584  // Replace extracts from the original narrow vector with extracts from the new
585  // wide vector.
586  for (User *U : ExtVecOp->users()) {
588  if (!OldExt || OldExt->getParent() != WideVec->getParent())
589  continue;
590  auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
591  NewExt->insertAfter(OldExt);
592  IC.replaceInstUsesWith(*OldExt, NewExt);
593  }
594 }
595 
596 /// We are building a shuffle to create V, which is a sequence of insertelement,
597 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
598 /// not rely on the second vector source. Return a std::pair containing the
599 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
600 /// parameter as required.
601 ///
602 /// Note: we intentionally don't try to fold earlier shuffles since they have
603 /// often been chosen carefully to be efficiently implementable on the target.
604 using ShuffleOps = std::pair<Value *, Value *>;
605 
608  Value *PermittedRHS,
609  InstCombiner &IC) {
610  assert(V->getType()->isVectorTy() && "Invalid shuffle!");
611  unsigned NumElts = V->getType()->getVectorNumElements();
612 
613  if (isa<UndefValue>(V)) {
614  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
615  return std::make_pair(
616  PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
617  }
618 
619  if (isa<ConstantAggregateZero>(V)) {
620  Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
621  return std::make_pair(V, nullptr);
622  }
623 
624  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
625  // If this is an insert of an extract from some other vector, include it.
626  Value *VecOp = IEI->getOperand(0);
627  Value *ScalarOp = IEI->getOperand(1);
628  Value *IdxOp = IEI->getOperand(2);
629 
630  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
631  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
632  unsigned ExtractedIdx =
633  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
634  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
635 
636  // Either the extracted from or inserted into vector must be RHSVec,
637  // otherwise we'd end up with a shuffle of three inputs.
638  if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
639  Value *RHS = EI->getOperand(0);
640  ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
641  assert(LR.second == nullptr || LR.second == RHS);
642 
643  if (LR.first->getType() != RHS->getType()) {
644  // Although we are giving up for now, see if we can create extracts
645  // that match the inserts for another round of combining.
646  replaceExtractElements(IEI, EI, IC);
647 
648  // We tried our best, but we can't find anything compatible with RHS
649  // further up the chain. Return a trivial shuffle.
650  for (unsigned i = 0; i < NumElts; ++i)
651  Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
652  return std::make_pair(V, nullptr);
653  }
654 
655  unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
656  Mask[InsertedIdx % NumElts] =
658  NumLHSElts+ExtractedIdx);
659  return std::make_pair(LR.first, RHS);
660  }
661 
662  if (VecOp == PermittedRHS) {
663  // We've gone as far as we can: anything on the other side of the
664  // extractelement will already have been converted into a shuffle.
665  unsigned NumLHSElts =
667  for (unsigned i = 0; i != NumElts; ++i)
670  i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
671  return std::make_pair(EI->getOperand(0), PermittedRHS);
672  }
673 
674  // If this insertelement is a chain that comes from exactly these two
675  // vectors, return the vector and the effective shuffle.
676  if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
677  collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
678  Mask))
679  return std::make_pair(EI->getOperand(0), PermittedRHS);
680  }
681  }
682  }
683 
684  // Otherwise, we can't do anything fancy. Return an identity vector.
685  for (unsigned i = 0; i != NumElts; ++i)
687  return std::make_pair(V, nullptr);
688 }
689 
690 /// Try to find redundant insertvalue instructions, like the following ones:
691 /// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
692 /// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
693 /// Here the second instruction inserts values at the same indices, as the
694 /// first one, making the first one redundant.
695 /// It should be transformed to:
696 /// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
698  bool IsRedundant = false;
699  ArrayRef<unsigned int> FirstIndices = I.getIndices();
700 
701  // If there is a chain of insertvalue instructions (each of them except the
702  // last one has only one use and it's another insertvalue insn from this
703  // chain), check if any of the 'children' uses the same indices as the first
704  // instruction. In this case, the first one is redundant.
705  Value *V = &I;
706  unsigned Depth = 0;
707  while (V->hasOneUse() && Depth < 10) {
708  User *U = V->user_back();
709  auto UserInsInst = dyn_cast<InsertValueInst>(U);
710  if (!UserInsInst || U->getOperand(0) != V)
711  break;
712  if (UserInsInst->getIndices() == FirstIndices) {
713  IsRedundant = true;
714  break;
715  }
716  V = UserInsInst;
717  Depth++;
718  }
719 
720  if (IsRedundant)
721  return replaceInstUsesWith(I, I.getOperand(0));
722  return nullptr;
723 }
724 
726  int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
727  int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
728 
729  // A vector select does not change the size of the operands.
730  if (MaskSize != VecSize)
731  return false;
732 
733  // Each mask element must be undefined or choose a vector element from one of
734  // the source operands without crossing vector lanes.
735  for (int i = 0; i != MaskSize; ++i) {
736  int Elt = Shuf.getMaskValue(i);
737  if (Elt != -1 && Elt != i && Elt != i + VecSize)
738  return false;
739  }
740 
741  return true;
742 }
743 
744 /// Turn a chain of inserts that splats a value into an insert + shuffle:
745 /// insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
746 /// shufflevector(insertelt(X, %k, 0), undef, zero)
748  // We are interested in the last insert in a chain. So if this insert has a
749  // single user and that user is an insert, bail.
750  if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
751  return nullptr;
752 
753  auto *VecTy = cast<VectorType>(InsElt.getType());
754  unsigned NumElements = VecTy->getNumElements();
755 
756  // Do not try to do this for a one-element vector, since that's a nop,
757  // and will cause an inf-loop.
758  if (NumElements == 1)
759  return nullptr;
760 
761  Value *SplatVal = InsElt.getOperand(1);
762  InsertElementInst *CurrIE = &InsElt;
763  SmallVector<bool, 16> ElementPresent(NumElements, false);
764  InsertElementInst *FirstIE = nullptr;
765 
766  // Walk the chain backwards, keeping track of which indices we inserted into,
767  // until we hit something that isn't an insert of the splatted value.
768  while (CurrIE) {
769  auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
770  if (!Idx || CurrIE->getOperand(1) != SplatVal)
771  return nullptr;
772 
773  auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
774  // Check none of the intermediate steps have any additional uses, except
775  // for the root insertelement instruction, which can be re-used, if it
776  // inserts at position 0.
777  if (CurrIE != &InsElt &&
778  (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
779  return nullptr;
780 
781  ElementPresent[Idx->getZExtValue()] = true;
782  FirstIE = CurrIE;
783  CurrIE = NextIE;
784  }
785 
786  // If this is just a single insertelement (not a sequence), we are done.
787  if (FirstIE == &InsElt)
788  return nullptr;
789 
790  // If we are not inserting into an undef vector, make sure we've seen an
791  // insert into every element.
792  // TODO: If the base vector is not undef, it might be better to create a splat
793  // and then a select-shuffle (blend) with the base vector.
794  if (!isa<UndefValue>(FirstIE->getOperand(0)))
795  if (any_of(ElementPresent, [](bool Present) { return !Present; }))
796  return nullptr;
797 
798  // Create the insert + shuffle.
800  UndefValue *UndefVec = UndefValue::get(VecTy);
801  Constant *Zero = ConstantInt::get(Int32Ty, 0);
802  if (!cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
803  FirstIE = InsertElementInst::Create(UndefVec, SplatVal, Zero, "", &InsElt);
804 
805  // Splat from element 0, but replace absent elements with undef in the mask.
806  SmallVector<Constant *, 16> Mask(NumElements, Zero);
807  for (unsigned i = 0; i != NumElements; ++i)
808  if (!ElementPresent[i])
809  Mask[i] = UndefValue::get(Int32Ty);
810 
811  return new ShuffleVectorInst(FirstIE, UndefVec, ConstantVector::get(Mask));
812 }
813 
814 /// Try to fold an insert element into an existing splat shuffle by changing
815 /// the shuffle's mask to include the index of this insert element.
817  // Check if the vector operand of this insert is a canonical splat shuffle.
818  auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
819  if (!Shuf || !Shuf->isZeroEltSplat())
820  return nullptr;
821 
822  // Check for a constant insertion index.
823  uint64_t IdxC;
824  if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
825  return nullptr;
826 
827  // Check if the splat shuffle's input is the same as this insert's scalar op.
828  Value *X = InsElt.getOperand(1);
829  Value *Op0 = Shuf->getOperand(0);
830  if (!match(Op0, m_InsertElement(m_Undef(), m_Specific(X), m_ZeroInt())))
831  return nullptr;
832 
833  // Replace the shuffle mask element at the index of this insert with a zero.
834  // For example:
835  // inselt (shuf (inselt undef, X, 0), undef, <0,undef,0,undef>), X, 1
836  // --> shuf (inselt undef, X, 0), undef, <0,0,0,undef>
837  unsigned NumMaskElts = Shuf->getType()->getVectorNumElements();
838  SmallVector<Constant *, 16> NewMaskVec(NumMaskElts);
839  Type *I32Ty = IntegerType::getInt32Ty(Shuf->getContext());
840  Constant *Zero = ConstantInt::getNullValue(I32Ty);
841  for (unsigned i = 0; i != NumMaskElts; ++i)
842  NewMaskVec[i] = i == IdxC ? Zero : Shuf->getMask()->getAggregateElement(i);
843 
844  Constant *NewMask = ConstantVector::get(NewMaskVec);
845  return new ShuffleVectorInst(Op0, UndefValue::get(Op0->getType()), NewMask);
846 }
847 
848 /// Try to fold an extract+insert element into an existing identity shuffle by
849 /// changing the shuffle's mask to include the index of this insert element.
851  // Check if the vector operand of this insert is an identity shuffle.
852  auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0));
853  if (!Shuf || !isa<UndefValue>(Shuf->getOperand(1)) ||
854  !(Shuf->isIdentityWithExtract() || Shuf->isIdentityWithPadding()))
855  return nullptr;
856 
857  // Check for a constant insertion index.
858  uint64_t IdxC;
859  if (!match(InsElt.getOperand(2), m_ConstantInt(IdxC)))
860  return nullptr;
861 
862  // Check if this insert's scalar op is extracted from the identity shuffle's
863  // input vector.
864  Value *Scalar = InsElt.getOperand(1);
865  Value *X = Shuf->getOperand(0);
866  if (!match(Scalar, m_ExtractElement(m_Specific(X), m_SpecificInt(IdxC))))
867  return nullptr;
868 
869  // Replace the shuffle mask element at the index of this extract+insert with
870  // that same index value.
871  // For example:
872  // inselt (shuf X, IdMask), (extelt X, IdxC), IdxC --> shuf X, IdMask'
873  unsigned NumMaskElts = Shuf->getType()->getVectorNumElements();
874  SmallVector<Constant *, 16> NewMaskVec(NumMaskElts);
875  Type *I32Ty = IntegerType::getInt32Ty(Shuf->getContext());
876  Constant *NewMaskEltC = ConstantInt::get(I32Ty, IdxC);
877  Constant *OldMask = Shuf->getMask();
878  for (unsigned i = 0; i != NumMaskElts; ++i) {
879  if (i != IdxC) {
880  // All mask elements besides the inserted element remain the same.
881  NewMaskVec[i] = OldMask->getAggregateElement(i);
882  } else if (OldMask->getAggregateElement(i) == NewMaskEltC) {
883  // If the mask element was already set, there's nothing to do
884  // (demanded elements analysis may unset it later).
885  return nullptr;
886  } else {
887  assert(isa<UndefValue>(OldMask->getAggregateElement(i)) &&
888  "Unexpected shuffle mask element for identity shuffle");
889  NewMaskVec[i] = NewMaskEltC;
890  }
891  }
892 
893  Constant *NewMask = ConstantVector::get(NewMaskVec);
894  return new ShuffleVectorInst(X, Shuf->getOperand(1), NewMask);
895 }
896 
897 /// If we have an insertelement instruction feeding into another insertelement
898 /// and the 2nd is inserting a constant into the vector, canonicalize that
899 /// constant insertion before the insertion of a variable:
900 ///
901 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
902 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
903 ///
904 /// This has the potential of eliminating the 2nd insertelement instruction
905 /// via constant folding of the scalar constant into a vector constant.
907  InstCombiner::BuilderTy &Builder) {
908  auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
909  if (!InsElt1 || !InsElt1->hasOneUse())
910  return nullptr;
911 
912  Value *X, *Y;
913  Constant *ScalarC;
914  ConstantInt *IdxC1, *IdxC2;
915  if (match(InsElt1->getOperand(0), m_Value(X)) &&
916  match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
917  match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
918  match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
919  match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
920  Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
921  return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
922  }
923 
924  return nullptr;
925 }
926 
927 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
928 /// --> shufflevector X, CVec', Mask'
930  auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
931  // Bail out if the parent has more than one use. In that case, we'd be
932  // replacing the insertelt with a shuffle, and that's not a clear win.
933  if (!Inst || !Inst->hasOneUse())
934  return nullptr;
935  if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
936  // The shuffle must have a constant vector operand. The insertelt must have
937  // a constant scalar being inserted at a constant position in the vector.
938  Constant *ShufConstVec, *InsEltScalar;
939  uint64_t InsEltIndex;
940  if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
941  !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
942  !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
943  return nullptr;
944 
945  // Adding an element to an arbitrary shuffle could be expensive, but a
946  // shuffle that selects elements from vectors without crossing lanes is
947  // assumed cheap.
948  // If we're just adding a constant into that shuffle, it will still be
949  // cheap.
950  if (!isShuffleEquivalentToSelect(*Shuf))
951  return nullptr;
952 
953  // From the above 'select' check, we know that the mask has the same number
954  // of elements as the vector input operands. We also know that each constant
955  // input element is used in its lane and can not be used more than once by
956  // the shuffle. Therefore, replace the constant in the shuffle's constant
957  // vector with the insertelt constant. Replace the constant in the shuffle's
958  // mask vector with the insertelt index plus the length of the vector
959  // (because the constant vector operand of a shuffle is always the 2nd
960  // operand).
961  Constant *Mask = Shuf->getMask();
962  unsigned NumElts = Mask->getType()->getVectorNumElements();
963  SmallVector<Constant *, 16> NewShufElts(NumElts);
964  SmallVector<Constant *, 16> NewMaskElts(NumElts);
965  for (unsigned I = 0; I != NumElts; ++I) {
966  if (I == InsEltIndex) {
967  NewShufElts[I] = InsEltScalar;
968  Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
969  NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
970  } else {
971  // Copy over the existing values.
972  NewShufElts[I] = ShufConstVec->getAggregateElement(I);
973  NewMaskElts[I] = Mask->getAggregateElement(I);
974  }
975  }
976 
977  // Create new operands for a shuffle that includes the constant of the
978  // original insertelt. The old shuffle will be dead now.
979  return new ShuffleVectorInst(Shuf->getOperand(0),
980  ConstantVector::get(NewShufElts),
981  ConstantVector::get(NewMaskElts));
982  } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
983  // Transform sequences of insertelements ops with constant data/indexes into
984  // a single shuffle op.
985  unsigned NumElts = InsElt.getType()->getNumElements();
986 
987  uint64_t InsertIdx[2];
988  Constant *Val[2];
989  if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
990  !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
991  !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
992  !match(IEI->getOperand(1), m_Constant(Val[1])))
993  return nullptr;
994  SmallVector<Constant *, 16> Values(NumElts);
996  auto ValI = std::begin(Val);
997  // Generate new constant vector and mask.
998  // We have 2 values/masks from the insertelements instructions. Insert them
999  // into new value/mask vectors.
1000  for (uint64_t I : InsertIdx) {
1001  if (!Values[I]) {
1002  assert(!Mask[I]);
1003  Values[I] = *ValI;
1004  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
1005  NumElts + I);
1006  }
1007  ++ValI;
1008  }
1009  // Remaining values are filled with 'undef' values.
1010  for (unsigned I = 0; I < NumElts; ++I) {
1011  if (!Values[I]) {
1012  assert(!Mask[I]);
1013  Values[I] = UndefValue::get(InsElt.getType()->getElementType());
1014  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
1015  }
1016  }
1017  // Create new operands for a shuffle that includes the constant of the
1018  // original insertelt.
1019  return new ShuffleVectorInst(IEI->getOperand(0),
1020  ConstantVector::get(Values),
1021  ConstantVector::get(Mask));
1022  }
1023  return nullptr;
1024 }
1025 
1027  Value *VecOp = IE.getOperand(0);
1028  Value *ScalarOp = IE.getOperand(1);
1029  Value *IdxOp = IE.getOperand(2);
1030 
1031  if (auto *V = SimplifyInsertElementInst(
1032  VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
1033  return replaceInstUsesWith(IE, V);
1034 
1035  // If the vector and scalar are both bitcast from the same element type, do
1036  // the insert in that source type followed by bitcast.
1037  Value *VecSrc, *ScalarSrc;
1038  if (match(VecOp, m_BitCast(m_Value(VecSrc))) &&
1039  match(ScalarOp, m_BitCast(m_Value(ScalarSrc))) &&
1040  (VecOp->hasOneUse() || ScalarOp->hasOneUse()) &&
1041  VecSrc->getType()->isVectorTy() && !ScalarSrc->getType()->isVectorTy() &&
1042  VecSrc->getType()->getVectorElementType() == ScalarSrc->getType()) {
1043  // inselt (bitcast VecSrc), (bitcast ScalarSrc), IdxOp -->
1044  // bitcast (inselt VecSrc, ScalarSrc, IdxOp)
1045  Value *NewInsElt = Builder.CreateInsertElement(VecSrc, ScalarSrc, IdxOp);
1046  return new BitCastInst(NewInsElt, IE.getType());
1047  }
1048 
1049  // If the inserted element was extracted from some other vector and both
1050  // indexes are valid constants, try to turn this into a shuffle.
1051  uint64_t InsertedIdx, ExtractedIdx;
1052  Value *ExtVecOp;
1053  if (match(IdxOp, m_ConstantInt(InsertedIdx)) &&
1054  match(ScalarOp, m_ExtractElement(m_Value(ExtVecOp),
1055  m_ConstantInt(ExtractedIdx))) &&
1056  ExtractedIdx < ExtVecOp->getType()->getVectorNumElements()) {
1057  // TODO: Looking at the user(s) to determine if this insert is a
1058  // fold-to-shuffle opportunity does not match the usual instcombine
1059  // constraints. We should decide if the transform is worthy based only
1060  // on this instruction and its operands, but that may not work currently.
1061  //
1062  // Here, we are trying to avoid creating shuffles before reaching
1063  // the end of a chain of extract-insert pairs. This is complicated because
1064  // we do not generally form arbitrary shuffle masks in instcombine
1065  // (because those may codegen poorly), but collectShuffleElements() does
1066  // exactly that.
1067  //
1068  // The rules for determining what is an acceptable target-independent
1069  // shuffle mask are fuzzy because they evolve based on the backend's
1070  // capabilities and real-world impact.
1071  auto isShuffleRootCandidate = [](InsertElementInst &Insert) {
1072  if (!Insert.hasOneUse())
1073  return true;
1074  auto *InsertUser = dyn_cast<InsertElementInst>(Insert.user_back());
1075  if (!InsertUser)
1076  return true;
1077  return false;
1078  };
1079 
1080  // Try to form a shuffle from a chain of extract-insert ops.
1081  if (isShuffleRootCandidate(IE)) {
1083  ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
1084 
1085  // The proposed shuffle may be trivial, in which case we shouldn't
1086  // perform the combine.
1087  if (LR.first != &IE && LR.second != &IE) {
1088  // We now have a shuffle of LHS, RHS, Mask.
1089  if (LR.second == nullptr)
1090  LR.second = UndefValue::get(LR.first->getType());
1091  return new ShuffleVectorInst(LR.first, LR.second,
1092  ConstantVector::get(Mask));
1093  }
1094  }
1095  }
1096 
1097  unsigned VWidth = VecOp->getType()->getVectorNumElements();
1098  APInt UndefElts(VWidth, 0);
1099  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1100  if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
1101  if (V != &IE)
1102  return replaceInstUsesWith(IE, V);
1103  return &IE;
1104  }
1105 
1107  return Shuf;
1108 
1109  if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
1110  return NewInsElt;
1111 
1112  if (Instruction *Broadcast = foldInsSequenceIntoSplat(IE))
1113  return Broadcast;
1114 
1115  if (Instruction *Splat = foldInsEltIntoSplat(IE))
1116  return Splat;
1117 
1118  if (Instruction *IdentityShuf = foldInsEltIntoIdentityShuffle(IE))
1119  return IdentityShuf;
1120 
1121  return nullptr;
1122 }
1123 
1124 /// Return true if we can evaluate the specified expression tree if the vector
1125 /// elements were shuffled in a different order.
1127  unsigned Depth = 5) {
1128  // We can always reorder the elements of a constant.
1129  if (isa<Constant>(V))
1130  return true;
1131 
1132  // We won't reorder vector arguments. No IPO here.
1134  if (!I) return false;
1135 
1136  // Two users may expect different orders of the elements. Don't try it.
1137  if (!I->hasOneUse())
1138  return false;
1139 
1140  if (Depth == 0) return false;
1141 
1142  switch (I->getOpcode()) {
1143  case Instruction::UDiv:
1144  case Instruction::SDiv:
1145  case Instruction::URem:
1146  case Instruction::SRem:
1147  // Propagating an undefined shuffle mask element to integer div/rem is not
1148  // allowed because those opcodes can create immediate undefined behavior
1149  // from an undefined element in an operand.
1150  if (llvm::any_of(Mask, [](int M){ return M == -1; }))
1151  return false;
1153  case Instruction::Add:
1154  case Instruction::FAdd:
1155  case Instruction::Sub:
1156  case Instruction::FSub:
1157  case Instruction::Mul:
1158  case Instruction::FMul:
1159  case Instruction::FDiv:
1160  case Instruction::FRem:
1161  case Instruction::Shl:
1162  case Instruction::LShr:
1163  case Instruction::AShr:
1164  case Instruction::And:
1165  case Instruction::Or:
1166  case Instruction::Xor:
1167  case Instruction::ICmp:
1168  case Instruction::FCmp:
1169  case Instruction::Trunc:
1170  case Instruction::ZExt:
1171  case Instruction::SExt:
1172  case Instruction::FPToUI:
1173  case Instruction::FPToSI:
1174  case Instruction::UIToFP:
1175  case Instruction::SIToFP:
1176  case Instruction::FPTrunc:
1177  case Instruction::FPExt:
1178  case Instruction::GetElementPtr: {
1179  // Bail out if we would create longer vector ops. We could allow creating
1180  // longer vector ops, but that may result in more expensive codegen.
1181  Type *ITy = I->getType();
1182  if (ITy->isVectorTy() && Mask.size() > ITy->getVectorNumElements())
1183  return false;
1184  for (Value *Operand : I->operands()) {
1185  if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
1186  return false;
1187  }
1188  return true;
1189  }
1190  case Instruction::InsertElement: {
1192  if (!CI) return false;
1193  int ElementNumber = CI->getLimitedValue();
1194 
1195  // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
1196  // can't put an element into multiple indices.
1197  bool SeenOnce = false;
1198  for (int i = 0, e = Mask.size(); i != e; ++i) {
1199  if (Mask[i] == ElementNumber) {
1200  if (SeenOnce)
1201  return false;
1202  SeenOnce = true;
1203  }
1204  }
1205  return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1);
1206  }
1207  }
1208  return false;
1209 }
1210 
1211 /// Rebuild a new instruction just like 'I' but with the new operands given.
1212 /// In the event of type mismatch, the type of the operands is correct.
1214  // We don't want to use the IRBuilder here because we want the replacement
1215  // instructions to appear next to 'I', not the builder's insertion point.
1216  switch (I->getOpcode()) {
1217  case Instruction::Add:
1218  case Instruction::FAdd:
1219  case Instruction::Sub:
1220  case Instruction::FSub:
1221  case Instruction::Mul:
1222  case Instruction::FMul:
1223  case Instruction::UDiv:
1224  case Instruction::SDiv:
1225  case Instruction::FDiv:
1226  case Instruction::URem:
1227  case Instruction::SRem:
1228  case Instruction::FRem:
1229  case Instruction::Shl:
1230  case Instruction::LShr:
1231  case Instruction::AShr:
1232  case Instruction::And:
1233  case Instruction::Or:
1234  case Instruction::Xor: {
1235  BinaryOperator *BO = cast<BinaryOperator>(I);
1236  assert(NewOps.size() == 2 && "binary operator with #ops != 2");
1237  BinaryOperator *New =
1238  BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
1239  NewOps[0], NewOps[1], "", BO);
1240  if (isa<OverflowingBinaryOperator>(BO)) {
1241  New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
1242  New->setHasNoSignedWrap(BO->hasNoSignedWrap());
1243  }
1244  if (isa<PossiblyExactOperator>(BO)) {
1245  New->setIsExact(BO->isExact());
1246  }
1247  if (isa<FPMathOperator>(BO))
1248  New->copyFastMathFlags(I);
1249  return New;
1250  }
1251  case Instruction::ICmp:
1252  assert(NewOps.size() == 2 && "icmp with #ops != 2");
1253  return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
1254  NewOps[0], NewOps[1]);
1255  case Instruction::FCmp:
1256  assert(NewOps.size() == 2 && "fcmp with #ops != 2");
1257  return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
1258  NewOps[0], NewOps[1]);
1259  case Instruction::Trunc:
1260  case Instruction::ZExt:
1261  case Instruction::SExt:
1262  case Instruction::FPToUI:
1263  case Instruction::FPToSI:
1264  case Instruction::UIToFP:
1265  case Instruction::SIToFP:
1266  case Instruction::FPTrunc:
1267  case Instruction::FPExt: {
1268  // It's possible that the mask has a different number of elements from
1269  // the original cast. We recompute the destination type to match the mask.
1270  Type *DestTy =
1272  NewOps[0]->getType()->getVectorNumElements());
1273  assert(NewOps.size() == 1 && "cast with #ops != 1");
1274  return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
1275  "", I);
1276  }
1277  case Instruction::GetElementPtr: {
1278  Value *Ptr = NewOps[0];
1279  ArrayRef<Value*> Idx = NewOps.slice(1);
1281  cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1282  GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1283  return GEP;
1284  }
1285  }
1286  llvm_unreachable("failed to rebuild vector instructions");
1287 }
1288 
1290  // Mask.size() does not need to be equal to the number of vector elements.
1291 
1292  assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1293  Type *EltTy = V->getType()->getScalarType();
1294  Type *I32Ty = IntegerType::getInt32Ty(V->getContext());
1295  if (isa<UndefValue>(V))
1296  return UndefValue::get(VectorType::get(EltTy, Mask.size()));
1297 
1298  if (isa<ConstantAggregateZero>(V))
1299  return ConstantAggregateZero::get(VectorType::get(EltTy, Mask.size()));
1300 
1301  if (Constant *C = dyn_cast<Constant>(V)) {
1302  SmallVector<Constant *, 16> MaskValues;
1303  for (int i = 0, e = Mask.size(); i != e; ++i) {
1304  if (Mask[i] == -1)
1305  MaskValues.push_back(UndefValue::get(I32Ty));
1306  else
1307  MaskValues.push_back(ConstantInt::get(I32Ty, Mask[i]));
1308  }
1310  ConstantVector::get(MaskValues));
1311  }
1312 
1313  Instruction *I = cast<Instruction>(V);
1314  switch (I->getOpcode()) {
1315  case Instruction::Add:
1316  case Instruction::FAdd:
1317  case Instruction::Sub:
1318  case Instruction::FSub:
1319  case Instruction::Mul:
1320  case Instruction::FMul:
1321  case Instruction::UDiv:
1322  case Instruction::SDiv:
1323  case Instruction::FDiv:
1324  case Instruction::URem:
1325  case Instruction::SRem:
1326  case Instruction::FRem:
1327  case Instruction::Shl:
1328  case Instruction::LShr:
1329  case Instruction::AShr:
1330  case Instruction::And:
1331  case Instruction::Or:
1332  case Instruction::Xor:
1333  case Instruction::ICmp:
1334  case Instruction::FCmp:
1335  case Instruction::Trunc:
1336  case Instruction::ZExt:
1337  case Instruction::SExt:
1338  case Instruction::FPToUI:
1339  case Instruction::FPToSI:
1340  case Instruction::UIToFP:
1341  case Instruction::SIToFP:
1342  case Instruction::FPTrunc:
1343  case Instruction::FPExt:
1344  case Instruction::Select:
1345  case Instruction::GetElementPtr: {
1346  SmallVector<Value*, 8> NewOps;
1347  bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1348  for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1349  Value *V;
1350  // Recursively call evaluateInDifferentElementOrder on vector arguments
1351  // as well. E.g. GetElementPtr may have scalar operands even if the
1352  // return value is a vector, so we need to examine the operand type.
1353  if (I->getOperand(i)->getType()->isVectorTy())
1354  V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1355  else
1356  V = I->getOperand(i);
1357  NewOps.push_back(V);
1358  NeedsRebuild |= (V != I->getOperand(i));
1359  }
1360  if (NeedsRebuild) {
1361  return buildNew(I, NewOps);
1362  }
1363  return I;
1364  }
1365  case Instruction::InsertElement: {
1366  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1367 
1368  // The insertelement was inserting at Element. Figure out which element
1369  // that becomes after shuffling. The answer is guaranteed to be unique
1370  // by CanEvaluateShuffled.
1371  bool Found = false;
1372  int Index = 0;
1373  for (int e = Mask.size(); Index != e; ++Index) {
1374  if (Mask[Index] == Element) {
1375  Found = true;
1376  break;
1377  }
1378  }
1379 
1380  // If element is not in Mask, no need to handle the operand 1 (element to
1381  // be inserted). Just evaluate values in operand 0 according to Mask.
1382  if (!Found)
1383  return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1384 
1385  Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1386  return InsertElementInst::Create(V, I->getOperand(1),
1387  ConstantInt::get(I32Ty, Index), "", I);
1388  }
1389  }
1390  llvm_unreachable("failed to reorder elements of vector instruction!");
1391 }
1392 
1394  bool &isLHSID, bool &isRHSID) {
1395  isLHSID = isRHSID = true;
1396 
1397  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1398  if (Mask[i] < 0) continue; // Ignore undef values.
1399  // Is this an identity shuffle of the LHS value?
1400  isLHSID &= (Mask[i] == (int)i);
1401 
1402  // Is this an identity shuffle of the RHS value?
1403  isRHSID &= (Mask[i]-e == i);
1404  }
1405 }
1406 
1407 // Returns true if the shuffle is extracting a contiguous range of values from
1408 // LHS, for example:
1409 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1410 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1411 // Shuffles to: |EE|FF|GG|HH|
1412 // +--+--+--+--+
1415  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1416  unsigned MaskElems = Mask.size();
1417  unsigned BegIdx = Mask.front();
1418  unsigned EndIdx = Mask.back();
1419  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1420  return false;
1421  for (unsigned I = 0; I != MaskElems; ++I)
1422  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1423  return false;
1424  return true;
1425 }
1426 
1427 /// These are the ingredients in an alternate form binary operator as described
1428 /// below.
1429 struct BinopElts {
1434  Value *V0 = nullptr, Value *V1 = nullptr) :
1435  Opcode(Opc), Op0(V0), Op1(V1) {}
1436  operator bool() const { return Opcode != 0; }
1437 };
1438 
1439 /// Binops may be transformed into binops with different opcodes and operands.
1440 /// Reverse the usual canonicalization to enable folds with the non-canonical
1441 /// form of the binop. If a transform is possible, return the elements of the
1442 /// new binop. If not, return invalid elements.
1444  Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1445  Type *Ty = BO->getType();
1446  switch (BO->getOpcode()) {
1447  case Instruction::Shl: {
1448  // shl X, C --> mul X, (1 << C)
1449  Constant *C;
1450  if (match(BO1, m_Constant(C))) {
1451  Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1452  return { Instruction::Mul, BO0, ShlOne };
1453  }
1454  break;
1455  }
1456  case Instruction::Or: {
1457  // or X, C --> add X, C (when X and C have no common bits set)
1458  const APInt *C;
1459  if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1460  return { Instruction::Add, BO0, BO1 };
1461  break;
1462  }
1463  default:
1464  break;
1465  }
1466  return {};
1467 }
1468 
1470  assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1471 
1472  // Are we shuffling together some value and that same value after it has been
1473  // modified by a binop with a constant?
1474  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1475  Constant *C;
1476  bool Op0IsBinop;
1477  if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1478  Op0IsBinop = true;
1479  else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1480  Op0IsBinop = false;
1481  else
1482  return nullptr;
1483 
1484  // The identity constant for a binop leaves a variable operand unchanged. For
1485  // a vector, this is a splat of something like 0, -1, or 1.
1486  // If there's no identity constant for this binop, we're done.
1487  auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1488  BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1489  Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1490  if (!IdC)
1491  return nullptr;
1492 
1493  // Shuffle identity constants into the lanes that return the original value.
1494  // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1495  // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1496  // The existing binop constant vector remains in the same operand position.
1497  Constant *Mask = Shuf.getMask();
1498  Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1499  ConstantExpr::getShuffleVector(IdC, C, Mask);
1500 
1501  bool MightCreatePoisonOrUB =
1502  Mask->containsUndefElement() &&
1503  (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1504  if (MightCreatePoisonOrUB)
1505  NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1506 
1507  // shuf (bop X, C), X, M --> bop X, C'
1508  // shuf X, (bop X, C), M --> bop X, C'
1509  Value *X = Op0IsBinop ? Op1 : Op0;
1510  Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1511  NewBO->copyIRFlags(BO);
1512 
1513  // An undef shuffle mask element may propagate as an undef constant element in
1514  // the new binop. That would produce poison where the original code might not.
1515  // If we already made a safe constant, then there's no danger.
1516  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1517  NewBO->dropPoisonGeneratingFlags();
1518  return NewBO;
1519 }
1520 
1521 /// If we have an insert of a scalar to a non-zero element of an undefined
1522 /// vector and then shuffle that value, that's the same as inserting to the zero
1523 /// element and shuffling. Splatting from the zero element is recognized as the
1524 /// canonical form of splat.
1526  InstCombiner::BuilderTy &Builder) {
1527  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1528  Constant *Mask = Shuf.getMask();
1529  Value *X;
1530  uint64_t IndexC;
1531 
1532  // Match a shuffle that is a splat to a non-zero element.
1533  if (!match(Op0, m_OneUse(m_InsertElement(m_Undef(), m_Value(X),
1534  m_ConstantInt(IndexC)))) ||
1535  !match(Op1, m_Undef()) || match(Mask, m_ZeroInt()) || IndexC == 0)
1536  return nullptr;
1537 
1538  // Insert into element 0 of an undef vector.
1539  UndefValue *UndefVec = UndefValue::get(Shuf.getType());
1540  Constant *Zero = Builder.getInt32(0);
1541  Value *NewIns = Builder.CreateInsertElement(UndefVec, X, Zero);
1542 
1543  // Splat from element 0. Any mask element that is undefined remains undefined.
1544  // For example:
1545  // shuf (inselt undef, X, 2), undef, <2,2,undef>
1546  // --> shuf (inselt undef, X, 0), undef, <0,0,undef>
1547  unsigned NumMaskElts = Shuf.getType()->getVectorNumElements();
1548  SmallVector<Constant *, 16> NewMask(NumMaskElts, Zero);
1549  for (unsigned i = 0; i != NumMaskElts; ++i)
1550  if (isa<UndefValue>(Mask->getAggregateElement(i)))
1551  NewMask[i] = Mask->getAggregateElement(i);
1552 
1553  return new ShuffleVectorInst(NewIns, UndefVec, ConstantVector::get(NewMask));
1554 }
1555 
1556 /// Try to fold shuffles that are the equivalent of a vector select.
1558  InstCombiner::BuilderTy &Builder,
1559  const DataLayout &DL) {
1560  if (!Shuf.isSelect())
1561  return nullptr;
1562 
1563  // Canonicalize to choose from operand 0 first.
1564  unsigned NumElts = Shuf.getType()->getVectorNumElements();
1565  if (Shuf.getMaskValue(0) >= (int)NumElts) {
1566  // TODO: Can we assert that both operands of a shuffle-select are not undef
1567  // (otherwise, it would have been folded by instsimplify?
1568  Shuf.commute();
1569  return &Shuf;
1570  }
1571 
1573  return I;
1574 
1575  BinaryOperator *B0, *B1;
1576  if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1577  !match(Shuf.getOperand(1), m_BinOp(B1)))
1578  return nullptr;
1579 
1580  Value *X, *Y;
1581  Constant *C0, *C1;
1582  bool ConstantsAreOp1;
1583  if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1584  match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1585  ConstantsAreOp1 = true;
1586  else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1587  match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1588  ConstantsAreOp1 = false;
1589  else
1590  return nullptr;
1591 
1592  // We need matching binops to fold the lanes together.
1593  BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1594  BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1595  bool DropNSW = false;
1596  if (ConstantsAreOp1 && Opc0 != Opc1) {
1597  // TODO: We drop "nsw" if shift is converted into multiply because it may
1598  // not be correct when the shift amount is BitWidth - 1. We could examine
1599  // each vector element to determine if it is safe to keep that flag.
1600  if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1601  DropNSW = true;
1602  if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1603  assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1604  Opc0 = AltB0.Opcode;
1605  C0 = cast<Constant>(AltB0.Op1);
1606  } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1607  assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1608  Opc1 = AltB1.Opcode;
1609  C1 = cast<Constant>(AltB1.Op1);
1610  }
1611  }
1612 
1613  if (Opc0 != Opc1)
1614  return nullptr;
1615 
1616  // The opcodes must be the same. Use a new name to make that clear.
1617  BinaryOperator::BinaryOps BOpc = Opc0;
1618 
1619  // Select the constant elements needed for the single binop.
1620  Constant *Mask = Shuf.getMask();
1621  Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1622 
1623  // We are moving a binop after a shuffle. When a shuffle has an undefined
1624  // mask element, the result is undefined, but it is not poison or undefined
1625  // behavior. That is not necessarily true for div/rem/shift.
1626  bool MightCreatePoisonOrUB =
1627  Mask->containsUndefElement() &&
1629  if (MightCreatePoisonOrUB)
1630  NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1631 
1632  Value *V;
1633  if (X == Y) {
1634  // Remove a binop and the shuffle by rearranging the constant:
1635  // shuffle (op V, C0), (op V, C1), M --> op V, C'
1636  // shuffle (op C0, V), (op C1, V), M --> op C', V
1637  V = X;
1638  } else {
1639  // If there are 2 different variable operands, we must create a new shuffle
1640  // (select) first, so check uses to ensure that we don't end up with more
1641  // instructions than we started with.
1642  if (!B0->hasOneUse() && !B1->hasOneUse())
1643  return nullptr;
1644 
1645  // If we use the original shuffle mask and op1 is *variable*, we would be
1646  // putting an undef into operand 1 of div/rem/shift. This is either UB or
1647  // poison. We do not have to guard against UB when *constants* are op1
1648  // because safe constants guarantee that we do not overflow sdiv/srem (and
1649  // there's no danger for other opcodes).
1650  // TODO: To allow this case, create a new shuffle mask with no undefs.
1651  if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1652  return nullptr;
1653 
1654  // Note: In general, we do not create new shuffles in InstCombine because we
1655  // do not know if a target can lower an arbitrary shuffle optimally. In this
1656  // case, the shuffle uses the existing mask, so there is no additional risk.
1657 
1658  // Select the variable vectors first, then perform the binop:
1659  // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1660  // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1661  V = Builder.CreateShuffleVector(X, Y, Mask);
1662  }
1663 
1664  Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1665  BinaryOperator::Create(BOpc, NewC, V);
1666 
1667  // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1668  // 1. If we changed an opcode, poison conditions might have changed.
1669  // 2. If the shuffle had undef mask elements, the new binop might have undefs
1670  // where the original code did not. But if we already made a safe constant,
1671  // then there's no danger.
1672  NewBO->copyIRFlags(B0);
1673  NewBO->andIRFlags(B1);
1674  if (DropNSW)
1675  NewBO->setHasNoSignedWrap(false);
1676  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1677  NewBO->dropPoisonGeneratingFlags();
1678  return NewBO;
1679 }
1680 
1681 /// Match a shuffle-select-shuffle pattern where the shuffles are widening and
1682 /// narrowing (concatenating with undef and extracting back to the original
1683 /// length). This allows replacing the wide select with a narrow select.
1685  InstCombiner::BuilderTy &Builder) {
1686  // This must be a narrowing identity shuffle. It extracts the 1st N elements
1687  // of the 1st vector operand of a shuffle.
1688  if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
1689  return nullptr;
1690 
1691  // The vector being shuffled must be a vector select that we can eliminate.
1692  // TODO: The one-use requirement could be eased if X and/or Y are constants.
1693  Value *Cond, *X, *Y;
1694  if (!match(Shuf.getOperand(0),
1695  m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
1696  return nullptr;
1697 
1698  // We need a narrow condition value. It must be extended with undef elements
1699  // and have the same number of elements as this shuffle.
1700  unsigned NarrowNumElts = Shuf.getType()->getVectorNumElements();
1701  Value *NarrowCond;
1702  if (!match(Cond, m_OneUse(m_ShuffleVector(m_Value(NarrowCond), m_Undef(),
1703  m_Constant()))) ||
1704  NarrowCond->getType()->getVectorNumElements() != NarrowNumElts ||
1705  !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
1706  return nullptr;
1707 
1708  // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
1709  // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
1711  Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getMask());
1712  Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getMask());
1713  return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
1714 }
1715 
1716 /// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
1718  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1719  if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1))
1720  return nullptr;
1721 
1722  Value *X, *Y;
1723  Constant *Mask;
1724  if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask))))
1725  return nullptr;
1726 
1727  // Be conservative with shuffle transforms. If we can't kill the 1st shuffle,
1728  // then combining may result in worse codegen.
1729  if (!Op0->hasOneUse())
1730  return nullptr;
1731 
1732  // We are extracting a subvector from a shuffle. Remove excess elements from
1733  // the 1st shuffle mask to eliminate the extract.
1734  //
1735  // This transform is conservatively limited to identity extracts because we do
1736  // not allow arbitrary shuffle mask creation as a target-independent transform
1737  // (because we can't guarantee that will lower efficiently).
1738  //
1739  // If the extracting shuffle has an undef mask element, it transfers to the
1740  // new shuffle mask. Otherwise, copy the original mask element. Example:
1741  // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
1742  // shuf X, Y, <C0, undef, C2, undef>
1743  unsigned NumElts = Shuf.getType()->getVectorNumElements();
1744  SmallVector<Constant *, 16> NewMask(NumElts);
1745  assert(NumElts < Mask->getType()->getVectorNumElements() &&
1746  "Identity with extract must have less elements than its inputs");
1747 
1748  for (unsigned i = 0; i != NumElts; ++i) {
1749  Constant *ExtractMaskElt = Shuf.getMask()->getAggregateElement(i);
1750  Constant *MaskElt = Mask->getAggregateElement(i);
1751  NewMask[i] = isa<UndefValue>(ExtractMaskElt) ? ExtractMaskElt : MaskElt;
1752  }
1753  return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1754 }
1755 
1756 /// Try to replace a shuffle with an insertelement.
1758  Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1);
1760 
1761  // The shuffle must not change vector sizes.
1762  // TODO: This restriction could be removed if the insert has only one use
1763  // (because the transform would require a new length-changing shuffle).
1764  int NumElts = Mask.size();
1765  if (NumElts != (int)(V0->getType()->getVectorNumElements()))
1766  return nullptr;
1767 
1768  // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
1769  auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
1770  // We need an insertelement with a constant index.
1771  if (!match(V0, m_InsertElement(m_Value(), m_Value(Scalar),
1772  m_ConstantInt(IndexC))))
1773  return false;
1774 
1775  // Test the shuffle mask to see if it splices the inserted scalar into the
1776  // operand 1 vector of the shuffle.
1777  int NewInsIndex = -1;
1778  for (int i = 0; i != NumElts; ++i) {
1779  // Ignore undef mask elements.
1780  if (Mask[i] == -1)
1781  continue;
1782 
1783  // The shuffle takes elements of operand 1 without lane changes.
1784  if (Mask[i] == NumElts + i)
1785  continue;
1786 
1787  // The shuffle must choose the inserted scalar exactly once.
1788  if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
1789  return false;
1790 
1791  // The shuffle is placing the inserted scalar into element i.
1792  NewInsIndex = i;
1793  }
1794 
1795  assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?");
1796 
1797  // Index is updated to the potentially translated insertion lane.
1798  IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex);
1799  return true;
1800  };
1801 
1802  // If the shuffle is unnecessary, insert the scalar operand directly into
1803  // operand 1 of the shuffle. Example:
1804  // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
1805  Value *Scalar;
1806  ConstantInt *IndexC;
1807  if (isShufflingScalarIntoOp1(Scalar, IndexC))
1808  return InsertElementInst::Create(V1, Scalar, IndexC);
1809 
1810  // Try again after commuting shuffle. Example:
1811  // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
1812  // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
1813  std::swap(V0, V1);
1815  if (isShufflingScalarIntoOp1(Scalar, IndexC))
1816  return InsertElementInst::Create(V1, Scalar, IndexC);
1817 
1818  return nullptr;
1819 }
1820 
1822  // Match the operands as identity with padding (also known as concatenation
1823  // with undef) shuffles of the same source type. The backend is expected to
1824  // recreate these concatenations from a shuffle of narrow operands.
1825  auto *Shuffle0 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(0));
1826  auto *Shuffle1 = dyn_cast<ShuffleVectorInst>(Shuf.getOperand(1));
1827  if (!Shuffle0 || !Shuffle0->isIdentityWithPadding() ||
1828  !Shuffle1 || !Shuffle1->isIdentityWithPadding())
1829  return nullptr;
1830 
1831  // We limit this transform to power-of-2 types because we expect that the
1832  // backend can convert the simplified IR patterns to identical nodes as the
1833  // original IR.
1834  // TODO: If we can verify the same behavior for arbitrary types, the
1835  // power-of-2 checks can be removed.
1836  Value *X = Shuffle0->getOperand(0);
1837  Value *Y = Shuffle1->getOperand(0);
1838  if (X->getType() != Y->getType() ||
1840  !isPowerOf2_32(Shuffle0->getType()->getVectorNumElements()) ||
1842  isa<UndefValue>(X) || isa<UndefValue>(Y))
1843  return nullptr;
1844  assert(isa<UndefValue>(Shuffle0->getOperand(1)) &&
1845  isa<UndefValue>(Shuffle1->getOperand(1)) &&
1846  "Unexpected operand for identity shuffle");
1847 
1848  // This is a shuffle of 2 widening shuffles. We can shuffle the narrow source
1849  // operands directly by adjusting the shuffle mask to account for the narrower
1850  // types:
1851  // shuf (widen X), (widen Y), Mask --> shuf X, Y, Mask'
1852  int NarrowElts = X->getType()->getVectorNumElements();
1853  int WideElts = Shuffle0->getType()->getVectorNumElements();
1854  assert(WideElts > NarrowElts && "Unexpected types for identity with padding");
1855 
1856  Type *I32Ty = IntegerType::getInt32Ty(Shuf.getContext());
1858  SmallVector<Constant *, 16> NewMask(Mask.size(), UndefValue::get(I32Ty));
1859  for (int i = 0, e = Mask.size(); i != e; ++i) {
1860  if (Mask[i] == -1)
1861  continue;
1862 
1863  // If this shuffle is choosing an undef element from 1 of the sources, that
1864  // element is undef.
1865  if (Mask[i] < WideElts) {
1866  if (Shuffle0->getMaskValue(Mask[i]) == -1)
1867  continue;
1868  } else {
1869  if (Shuffle1->getMaskValue(Mask[i] - WideElts) == -1)
1870  continue;
1871  }
1872 
1873  // If this shuffle is choosing from the 1st narrow op, the mask element is
1874  // the same. If this shuffle is choosing from the 2nd narrow op, the mask
1875  // element is offset down to adjust for the narrow vector widths.
1876  if (Mask[i] < WideElts) {
1877  assert(Mask[i] < NarrowElts && "Unexpected shuffle mask");
1878  NewMask[i] = ConstantInt::get(I32Ty, Mask[i]);
1879  } else {
1880  assert(Mask[i] < (WideElts + NarrowElts) && "Unexpected shuffle mask");
1881  NewMask[i] = ConstantInt::get(I32Ty, Mask[i] - (WideElts - NarrowElts));
1882  }
1883  }
1884  return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1885 }
1886 
1888  Value *LHS = SVI.getOperand(0);
1889  Value *RHS = SVI.getOperand(1);
1890  if (auto *V = SimplifyShuffleVectorInst(
1891  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1892  return replaceInstUsesWith(SVI, V);
1893 
1894  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1895  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1896  unsigned VWidth = SVI.getType()->getVectorNumElements();
1897  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1900  if (LHS == RHS || isa<UndefValue>(LHS)) {
1901  // Remap any references to RHS to use LHS.
1903  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1904  if (Mask[i] < 0) {
1905  Elts.push_back(UndefValue::get(Int32Ty));
1906  continue;
1907  }
1908 
1909  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1910  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1911  Mask[i] = -1; // Turn into undef.
1912  Elts.push_back(UndefValue::get(Int32Ty));
1913  } else {
1914  Mask[i] = Mask[i] % e; // Force to LHS.
1915  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1916  }
1917  }
1918  SVI.setOperand(0, SVI.getOperand(1));
1919  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1920  SVI.setOperand(2, ConstantVector::get(Elts));
1921  return &SVI;
1922  }
1923 
1924  if (Instruction *I = canonicalizeInsertSplat(SVI, Builder))
1925  return I;
1926 
1927  if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
1928  return I;
1929 
1930  if (Instruction *I = narrowVectorSelect(SVI, Builder))
1931  return I;
1932 
1933  APInt UndefElts(VWidth, 0);
1934  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1935  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1936  if (V != &SVI)
1937  return replaceInstUsesWith(SVI, V);
1938  return &SVI;
1939  }
1940 
1942  return I;
1943 
1944  // These transforms have the potential to lose undef knowledge, so they are
1945  // intentionally placed after SimplifyDemandedVectorElts().
1946  if (Instruction *I = foldShuffleWithInsert(SVI))
1947  return I;
1949  return I;
1950 
1951  if (VWidth == LHSWidth) {
1952  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1953  bool isLHSID, isRHSID;
1954  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1955 
1956  // Eliminate identity shuffles.
1957  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1958  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1959  }
1960 
1961  if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) {
1962  Value *V = evaluateInDifferentElementOrder(LHS, Mask);
1963  return replaceInstUsesWith(SVI, V);
1964  }
1965 
1966  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1967  // a non-vector type. We can instead bitcast the original vector followed by
1968  // an extract of the desired element:
1969  //
1970  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1971  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1972  // %1 = bitcast <4 x i8> %sroa to i32
1973  // Becomes:
1974  // %bc = bitcast <16 x i8> %in to <4 x i32>
1975  // %ext = extractelement <4 x i32> %bc, i32 0
1976  //
1977  // If the shuffle is extracting a contiguous range of values from the input
1978  // vector then each use which is a bitcast of the extracted size can be
1979  // replaced. This will work if the vector types are compatible, and the begin
1980  // index is aligned to a value in the casted vector type. If the begin index
1981  // isn't aligned then we can shuffle the original vector (keeping the same
1982  // vector type) before extracting.
1983  //
1984  // This code will bail out if the target type is fundamentally incompatible
1985  // with vectors of the source type.
1986  //
1987  // Example of <16 x i8>, target type i32:
1988  // Index range [4,8): v-----------v Will work.
1989  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1990  // <16 x i8>: | | | | | | | | | | | | | | | | |
1991  // <4 x i32>: | | | | |
1992  // +-----------+-----------+-----------+-----------+
1993  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1994  // Target type i40: ^--------------^ Won't work, bail.
1995  bool MadeChange = false;
1996  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1997  Value *V = LHS;
1998  unsigned MaskElems = Mask.size();
1999  VectorType *SrcTy = cast<VectorType>(V->getType());
2000  unsigned VecBitWidth = SrcTy->getBitWidth();
2001  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
2002  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
2003  unsigned SrcNumElems = SrcTy->getNumElements();
2006  for (User *U : SVI.users())
2007  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
2008  if (!BC->use_empty())
2009  // Only visit bitcasts that weren't previously handled.
2010  BCs.push_back(BC);
2011  for (BitCastInst *BC : BCs) {
2012  unsigned BegIdx = Mask.front();
2013  Type *TgtTy = BC->getDestTy();
2014  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
2015  if (!TgtElemBitWidth)
2016  continue;
2017  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
2018  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
2019  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
2020  if (!VecBitWidthsEqual)
2021  continue;
2022  if (!VectorType::isValidElementType(TgtTy))
2023  continue;
2024  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
2025  if (!BegIsAligned) {
2026  // Shuffle the input so [0,NumElements) contains the output, and
2027  // [NumElems,SrcNumElems) is undef.
2028  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
2029  UndefValue::get(Int32Ty));
2030  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
2031  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
2032  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
2033  ConstantVector::get(ShuffleMask),
2034  SVI.getName() + ".extract");
2035  BegIdx = 0;
2036  }
2037  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
2038  assert(SrcElemsPerTgtElem);
2039  BegIdx /= SrcElemsPerTgtElem;
2040  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
2041  auto *NewBC =
2042  BCAlreadyExists
2043  ? NewBCs[CastSrcTy]
2044  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
2045  if (!BCAlreadyExists)
2046  NewBCs[CastSrcTy] = NewBC;
2047  auto *Ext = Builder.CreateExtractElement(
2048  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
2049  // The shufflevector isn't being replaced: the bitcast that used it
2050  // is. InstCombine will visit the newly-created instructions.
2051  replaceInstUsesWith(*BC, Ext);
2052  MadeChange = true;
2053  }
2054  }
2055 
2056  // If the LHS is a shufflevector itself, see if we can combine it with this
2057  // one without producing an unusual shuffle.
2058  // Cases that might be simplified:
2059  // 1.
2060  // x1=shuffle(v1,v2,mask1)
2061  // x=shuffle(x1,undef,mask)
2062  // ==>
2063  // x=shuffle(v1,undef,newMask)
2064  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
2065  // 2.
2066  // x1=shuffle(v1,undef,mask1)
2067  // x=shuffle(x1,x2,mask)
2068  // where v1.size() == mask1.size()
2069  // ==>
2070  // x=shuffle(v1,x2,newMask)
2071  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
2072  // 3.
2073  // x2=shuffle(v2,undef,mask2)
2074  // x=shuffle(x1,x2,mask)
2075  // where v2.size() == mask2.size()
2076  // ==>
2077  // x=shuffle(x1,v2,newMask)
2078  // newMask[i] = (mask[i] < x1.size())
2079  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
2080  // 4.
2081  // x1=shuffle(v1,undef,mask1)
2082  // x2=shuffle(v2,undef,mask2)
2083  // x=shuffle(x1,x2,mask)
2084  // where v1.size() == v2.size()
2085  // ==>
2086  // x=shuffle(v1,v2,newMask)
2087  // newMask[i] = (mask[i] < x1.size())
2088  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
2089  //
2090  // Here we are really conservative:
2091  // we are absolutely afraid of producing a shuffle mask not in the input
2092  // program, because the code gen may not be smart enough to turn a merged
2093  // shuffle into two specific shuffles: it may produce worse code. As such,
2094  // we only merge two shuffles if the result is either a splat or one of the
2095  // input shuffle masks. In this case, merging the shuffles just removes
2096  // one instruction, which we know is safe. This is good for things like
2097  // turning: (splat(splat)) -> splat, or
2098  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
2099  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
2100  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
2101  if (LHSShuffle)
2102  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
2103  LHSShuffle = nullptr;
2104  if (RHSShuffle)
2105  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
2106  RHSShuffle = nullptr;
2107  if (!LHSShuffle && !RHSShuffle)
2108  return MadeChange ? &SVI : nullptr;
2109 
2110  Value* LHSOp0 = nullptr;
2111  Value* LHSOp1 = nullptr;
2112  Value* RHSOp0 = nullptr;
2113  unsigned LHSOp0Width = 0;
2114  unsigned RHSOp0Width = 0;
2115  if (LHSShuffle) {
2116  LHSOp0 = LHSShuffle->getOperand(0);
2117  LHSOp1 = LHSShuffle->getOperand(1);
2118  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
2119  }
2120  if (RHSShuffle) {
2121  RHSOp0 = RHSShuffle->getOperand(0);
2122  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
2123  }
2124  Value* newLHS = LHS;
2125  Value* newRHS = RHS;
2126  if (LHSShuffle) {
2127  // case 1
2128  if (isa<UndefValue>(RHS)) {
2129  newLHS = LHSOp0;
2130  newRHS = LHSOp1;
2131  }
2132  // case 2 or 4
2133  else if (LHSOp0Width == LHSWidth) {
2134  newLHS = LHSOp0;
2135  }
2136  }
2137  // case 3 or 4
2138  if (RHSShuffle && RHSOp0Width == LHSWidth) {
2139  newRHS = RHSOp0;
2140  }
2141  // case 4
2142  if (LHSOp0 == RHSOp0) {
2143  newLHS = LHSOp0;
2144  newRHS = nullptr;
2145  }
2146 
2147  if (newLHS == LHS && newRHS == RHS)
2148  return MadeChange ? &SVI : nullptr;
2149 
2150  SmallVector<int, 16> LHSMask;
2151  SmallVector<int, 16> RHSMask;
2152  if (newLHS != LHS)
2153  LHSMask = LHSShuffle->getShuffleMask();
2154  if (RHSShuffle && newRHS != RHS)
2155  RHSMask = RHSShuffle->getShuffleMask();
2156 
2157  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
2158  SmallVector<int, 16> newMask;
2159  bool isSplat = true;
2160  int SplatElt = -1;
2161  // Create a new mask for the new ShuffleVectorInst so that the new
2162  // ShuffleVectorInst is equivalent to the original one.
2163  for (unsigned i = 0; i < VWidth; ++i) {
2164  int eltMask;
2165  if (Mask[i] < 0) {
2166  // This element is an undef value.
2167  eltMask = -1;
2168  } else if (Mask[i] < (int)LHSWidth) {
2169  // This element is from left hand side vector operand.
2170  //
2171  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
2172  // new mask value for the element.
2173  if (newLHS != LHS) {
2174  eltMask = LHSMask[Mask[i]];
2175  // If the value selected is an undef value, explicitly specify it
2176  // with a -1 mask value.
2177  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
2178  eltMask = -1;
2179  } else
2180  eltMask = Mask[i];
2181  } else {
2182  // This element is from right hand side vector operand
2183  //
2184  // If the value selected is an undef value, explicitly specify it
2185  // with a -1 mask value. (case 1)
2186  if (isa<UndefValue>(RHS))
2187  eltMask = -1;
2188  // If RHS is going to be replaced (case 3 or 4), calculate the
2189  // new mask value for the element.
2190  else if (newRHS != RHS) {
2191  eltMask = RHSMask[Mask[i]-LHSWidth];
2192  // If the value selected is an undef value, explicitly specify it
2193  // with a -1 mask value.
2194  if (eltMask >= (int)RHSOp0Width) {
2195  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
2196  && "should have been check above");
2197  eltMask = -1;
2198  }
2199  } else
2200  eltMask = Mask[i]-LHSWidth;
2201 
2202  // If LHS's width is changed, shift the mask value accordingly.
2203  // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
2204  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
2205  // If newRHS == newLHS, we want to remap any references from newRHS to
2206  // newLHS so that we can properly identify splats that may occur due to
2207  // obfuscation across the two vectors.
2208  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
2209  eltMask += newLHSWidth;
2210  }
2211 
2212  // Check if this could still be a splat.
2213  if (eltMask >= 0) {
2214  if (SplatElt >= 0 && SplatElt != eltMask)
2215  isSplat = false;
2216  SplatElt = eltMask;
2217  }
2218 
2219  newMask.push_back(eltMask);
2220  }
2221 
2222  // If the result mask is equal to one of the original shuffle masks,
2223  // or is a splat, do the replacement.
2224  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
2226  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
2227  if (newMask[i] < 0) {
2228  Elts.push_back(UndefValue::get(Int32Ty));
2229  } else {
2230  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
2231  }
2232  }
2233  if (!newRHS)
2234  newRHS = UndefValue::get(newLHS->getType());
2235  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
2236  }
2237 
2238  // If the result mask is an identity, replace uses of this instruction with
2239  // corresponding argument.
2240  bool isLHSID, isRHSID;
2241  recognizeIdentityMask(newMask, isLHSID, isRHSID);
2242  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
2243  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
2244 
2245  return MadeChange ? &SVI : nullptr;
2246 }
static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf)
std::pair< Value *, Value * > ShuffleOps
We are building a shuffle to create V, which is a sequence of insertelement, extractelement pairs...
Instruction * visitInsertValueInst(InsertValueInst &IV)
Try to find redundant insertvalue instructions, like the following ones: %0 = insertvalue { i8...
Type * getVectorElementType() const
Definition: Type.h:376
bool isIdentityWithExtract() const
Return true if this shuffle extracts the first N elements of exactly one source vector.
uint64_t CallInst * C
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:70
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:86
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
iterator_range< use_iterator > uses()
Definition: Value.h:375
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:78
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:561
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:224
static Value * evaluateInDifferentElementOrder(Value *V, ArrayRef< int > Mask)
static Instruction * foldSelectShuffle(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder, const DataLayout &DL)
Try to fold shuffles that are the equivalent of a vector select.
Value * findScalarElement(Value *V, unsigned EltNo)
Given a vector and an element number, see if the scalar value is already around as a register...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:402
static Instruction * foldConstantInsEltIntoShuffle(InsertElementInst &InsElt)
insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex –> shufflevector X...
static Instruction * foldInsEltIntoSplat(InsertElementInst &InsElt)
Try to fold an insert element into an existing splat shuffle by changing the shuffle&#39;s mask to includ...
static bool cheapToScalarize(Value *V, bool IsConstantExtractIndex)
Return true if the value is cheaper to scalarize than it is to leave as a vector operation.
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1363
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:907
static Instruction * foldIdentityExtractShuffle(ShuffleVectorInst &Shuf)
Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:89
This instruction constructs a fixed permutation of two input vectors.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:743
ThreeOps_match< V1_t, V2_t, Mask_t, Instruction::ShuffleVector > m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m)
Matches ShuffleVectorInst.
static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI, SmallVector< int, 16 > &Mask)
Hexagon Common GEP
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
static Instruction * hoistInsEltConst(InsertElementInst &InsElt2, InstCombiner::BuilderTy &Builder)
If we have an insertelement instruction feeding into another insertelement and the 2nd is inserting a...
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
Definition: PatternMatch.h:391
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:289
static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL)
Binops may be transformed into binops with different opcodes and operands.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
Constant * getMask() const
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
unsigned getBitWidth() const
Return the minimum number of bits in the Vector type.
Definition: DerivedTypes.h:556
void setBit(unsigned BitPosition)
Set a given bit to 1.
Definition: APInt.h:1402
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElement(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
&#39;undef&#39; values are things that do not have specified contents.
Definition: Constants.h:1285
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:196
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:41
The core instruction combiner logic.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs...
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if &#39;V & Mask&#39; is known to be zero.
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, Instruction *CopyO, const Twine &Name="")
Definition: InstrTypes.h:249
static APInt findDemandedEltsByAllUsers(Value *V)
Find union of elements of V demanded by all its users.
uint64_t getNumElements() const
For scalable vectors, this will return the minimum number of elements in the vector.
Definition: DerivedTypes.h:398
BinopElts(BinaryOperator::BinaryOps Opc=(BinaryOperator::BinaryOps) 0, Value *V0=nullptr, Value *V1=nullptr)
This file implements a class to represent arbitrary precision integral constant values and operations...
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:412
static APInt findDemandedEltsBySingleUser(Value *V, Instruction *UserInstr)
Find elements of V demanded by UserInstr.
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1963
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:246
static Instruction * canonicalizeInsertSplat(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder)
If we have an insert of a scalar to a non-zero element of an undefined vector and then shuffle that v...
static Instruction * foldShuffleWithInsert(ShuffleVectorInst &Shuf)
Try to replace a shuffle with an insertelement.
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
static bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
Definition: Type.cpp:628
This instruction compares its operands according to the predicate given to the constructor.
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
This class represents a no-op cast from one type to another.
static CmpInst * Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2, const Twine &Name="", Instruction *InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:81
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
Instruction * visitExtractElementInst(ExtractElementInst &EI)
These are the ingredients in an alternate form binary operator as described below.
static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, SmallVectorImpl< Constant *> &Mask)
If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mas...
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:429
bool isSelect() const
Return true if this shuffle chooses elements from its source vectors without lane crossings and all o...
VectorType * getType() const
Overload to return most specific vector type.
This class represents a truncation of integer types.
Value * getOperand(unsigned i) const
Definition: User.h:169
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:359
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return &#39;this&#39;.
Definition: Type.h:307
Instruction * visitInsertElementInst(InsertElementInst &IE)
Value * SimplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx, const SimplifyQuery &Q)
Given operands for an InsertElement, fold the result or return null.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:881
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:61
This instruction inserts a single (scalar) element into a VectorType value.
bool isAllOnesValue() const
Determine if all bits are set.
Definition: APInt.h:395
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:194
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:223
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:465
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:148
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
This file contains the declarations for the subclasses of Constant, which represent the different fla...
specific_intval m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
Definition: PatternMatch.h:664
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
Definition: APInt.h:587
static Instruction * foldIdentityPaddedShuffles(ShuffleVectorInst &Shuf)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:587
static Constant * getShuffleVector(Constant *V1, Constant *V2, Constant *Mask, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2160
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1172
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:732
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2338
constexpr double e
Definition: MathExtras.h:57
op_range operands()
Definition: User.h:237
self_iterator getIterator()
Definition: ilist_node.h:81
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:73
Class to represent integer types.
Definition: DerivedTypes.h:40
VectorType * getVectorOperandType() const
static void replaceExtractElements(InsertElementInst *InsElt, ExtractElementInst *ExtElt, InstCombiner &IC)
If we have insertion into a vector that is wider than the vector that we are extracting from...
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
static Instruction * foldInsSequenceIntoSplat(InsertElementInst &InsElt)
Turn a chain of inserts that splats a value into an insert + shuffle: insertelt(insertelt(insertelt(i...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1446
size_t size() const
Definition: SmallVector.h:52
static wasm::ValType getType(const TargetRegisterClass *RC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isExact() const
Determine whether the exact flag is set.
static int getMaskValue(const Constant *Mask, unsigned Elt)
Return the shuffle mask value for the specified element of the mask.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1873
Value * SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q)
Given operands for a ShuffleVectorInst, fold the result or return null.
void commute()
Swap the first 2 operands and adjust the mask to preserve the semantics of the instruction.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:87
Iterator for intrusive lists based on ilist_node.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
Definition: Constants.h:250
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:134
BinaryOperator::BinaryOps Opcode
bool containsUndefElement() const
Return true if this is a vector constant that includes any undefined elements.
Definition: Constants.cpp:268
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
static void getShuffleMask(const Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
Value * CreateInsertElement(Value *Vec, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:2322
static Instruction * foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf)
ConstantInt * getInt32(uint32_t C)
Get a constant 32-bit value.
Definition: IRBuilder.h:343
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:184
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:2336
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:653
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:566
Class to represent vector types.
Definition: DerivedTypes.h:432
Class for arbitrary precision integers.
Definition: APInt.h:69
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:420
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array...
Definition: ArrayRef.h:178
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:549
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:180
static VectorType * get(Type *ElementType, ElementCount EC)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:614
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:79
#define I(x, y, z)
Definition: MD5.cpp:58
Instruction * visitShuffleVectorInst(ShuffleVectorInst &SVI)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:332
This instruction extracts a single (scalar) element from a VectorType value.
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2321
static bool canEvaluateShuffled(Value *V, ArrayRef< int > Mask, unsigned Depth=5)
Return true if we can evaluate the specified expression tree if the vector elements were shuffled in ...
static Instruction * foldBitcastExtElt(ExtractElementInst &Ext, InstCombiner::BuilderTy &Builder, bool IsBigEndian)
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
static Instruction * narrowVectorSelect(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder)
Match a shuffle-select-shuffle pattern where the shuffles are widening and narrowing (concatenating w...
ArrayRef< unsigned > getIndices() const
LLVM Value Representation.
Definition: Value.h:74
This file provides internal interfaces used to implement the InstCombine.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:273
Value * SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &Q)
Given operands for an ExtractElementInst, fold the result or return null.
static Value * buildNew(Instruction *I, ArrayRef< Value *> NewOps)
Rebuild a new instruction just like &#39;I&#39; but with the new operands given.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:80
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1228
Type * getElementType() const
Definition: DerivedTypes.h:399
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:433
bool isIntDivRem() const
Definition: Instruction.h:131
static bool isSplat(ArrayRef< Value *> VL)
static void recognizeIdentityMask(const SmallVectorImpl< int > &Mask, bool &isLHSID, bool &isRHSID)
static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl< Constant *> &Mask, Value *PermittedRHS, InstCombiner &IC)
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
VectorType * getType() const
Overload to return most specific vector type.
static Instruction * foldInsEltIntoIdentityShuffle(InsertElementInst &InsElt)
Try to fold an extract+insert element into an existing identity shuffle by changing the shuffle&#39;s mas...
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1110
static void commuteShuffleMask(MutableArrayRef< int > Mask, unsigned InVecNumElts)
Change values in a shuffle permute mask assuming the two vector operands of length InVecNumElts have ...
IntegerType * Int32Ty
User * user_back()
Definition: Value.h:406
const BasicBlock * getParent() const
Definition: Instruction.h:66
This instruction inserts a struct field of array element value into an aggregate value.