LLVM  6.0.0svn
InstCombineVectorOps.cpp
Go to the documentation of this file.
1 //===- InstCombineVectorOps.cpp -------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements instcombine for ExtractElement, InsertElement and
11 // ShuffleVector.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "InstCombineInternal.h"
16 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/IR/PatternMatch.h"
20 using namespace llvm;
21 using namespace PatternMatch;
22 
23 #define DEBUG_TYPE "instcombine"
24 
25 /// Return true if the value is cheaper to scalarize than it is to leave as a
26 /// vector operation. isConstant indicates whether we're extracting one known
27 /// element. If false we're extracting a variable index.
28 static bool cheapToScalarize(Value *V, bool isConstant) {
29  if (Constant *C = dyn_cast<Constant>(V)) {
30  if (isConstant) return true;
31 
32  // If all elts are the same, we can extract it and use any of the values.
33  if (Constant *Op0 = C->getAggregateElement(0U)) {
34  for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e;
35  ++i)
36  if (C->getAggregateElement(i) != Op0)
37  return false;
38  return true;
39  }
40  }
42  if (!I) return false;
43 
44  // Insert element gets simplified to the inserted element or is deleted if
45  // this is constant idx extract element and its a constant idx insertelt.
46  if (I->getOpcode() == Instruction::InsertElement && isConstant &&
47  isa<ConstantInt>(I->getOperand(2)))
48  return true;
49  if (I->getOpcode() == Instruction::Load && I->hasOneUse())
50  return true;
51  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
52  if (BO->hasOneUse() &&
53  (cheapToScalarize(BO->getOperand(0), isConstant) ||
54  cheapToScalarize(BO->getOperand(1), isConstant)))
55  return true;
56  if (CmpInst *CI = dyn_cast<CmpInst>(I))
57  if (CI->hasOneUse() &&
58  (cheapToScalarize(CI->getOperand(0), isConstant) ||
59  cheapToScalarize(CI->getOperand(1), isConstant)))
60  return true;
61 
62  return false;
63 }
64 
65 // If we have a PHI node with a vector type that is only used to feed
66 // itself and be an operand of extractelement at a constant location,
67 // try to replace the PHI of the vector type with a PHI of a scalar type.
68 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
70  // The users we want the PHI to have are:
71  // 1) The EI ExtractElement (we already know this)
72  // 2) Possibly more ExtractElements with the same index.
73  // 3) Another operand, which will feed back into the PHI.
74  Instruction *PHIUser = nullptr;
75  for (auto U : PN->users()) {
76  if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
77  if (EI.getIndexOperand() == EU->getIndexOperand())
78  Extracts.push_back(EU);
79  else
80  return nullptr;
81  } else if (!PHIUser) {
82  PHIUser = cast<Instruction>(U);
83  } else {
84  return nullptr;
85  }
86  }
87 
88  if (!PHIUser)
89  return nullptr;
90 
91  // Verify that this PHI user has one use, which is the PHI itself,
92  // and that it is a binary operation which is cheap to scalarize.
93  // otherwise return NULL.
94  if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
95  !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
96  return nullptr;
97 
98  // Create a scalar PHI node that will replace the vector PHI node
99  // just before the current PHI node.
100  PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
101  PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
102  // Scalarize each PHI operand.
103  for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
104  Value *PHIInVal = PN->getIncomingValue(i);
105  BasicBlock *inBB = PN->getIncomingBlock(i);
106  Value *Elt = EI.getIndexOperand();
107  // If the operand is the PHI induction variable:
108  if (PHIInVal == PHIUser) {
109  // Scalarize the binary operation. Its first operand is the
110  // scalar PHI, and the second operand is extracted from the other
111  // vector operand.
112  BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
113  unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
114  Value *Op = InsertNewInstWith(
115  ExtractElementInst::Create(B0->getOperand(opId), Elt,
116  B0->getOperand(opId)->getName() + ".Elt"),
117  *B0);
118  Value *newPHIUser = InsertNewInstWith(
120  scalarPHI, Op, B0), *B0);
121  scalarPHI->addIncoming(newPHIUser, inBB);
122  } else {
123  // Scalarize PHI input:
124  Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
125  // Insert the new instruction into the predecessor basic block.
126  Instruction *pos = dyn_cast<Instruction>(PHIInVal);
127  BasicBlock::iterator InsertPos;
128  if (pos && !isa<PHINode>(pos)) {
129  InsertPos = ++pos->getIterator();
130  } else {
131  InsertPos = inBB->getFirstInsertionPt();
132  }
133 
134  InsertNewInstWith(newEI, *InsertPos);
135 
136  scalarPHI->addIncoming(newEI, inBB);
137  }
138  }
139 
140  for (auto E : Extracts)
141  replaceInstUsesWith(*E, scalarPHI);
142 
143  return &EI;
144 }
145 
148  EI.getIndexOperand(),
149  SQ.getWithInstruction(&EI)))
150  return replaceInstUsesWith(EI, V);
151 
152  // If vector val is constant with all elements the same, replace EI with
153  // that element. We handle a known element # below.
154  if (Constant *C = dyn_cast<Constant>(EI.getOperand(0)))
155  if (cheapToScalarize(C, false))
156  return replaceInstUsesWith(EI, C->getAggregateElement(0U));
157 
158  // If extracting a specified index from the vector, see if we can recursively
159  // find a previously computed scalar that was inserted into the vector.
160  if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
161  unsigned IndexVal = IdxC->getZExtValue();
162  unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
163 
164  // InstSimplify handles cases where the index is invalid.
165  assert(IndexVal < VectorWidth);
166 
167  // This instruction only demands the single element from the input vector.
168  // If the input vector has a single use, simplify it based on this use
169  // property.
170  if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
171  APInt UndefElts(VectorWidth, 0);
172  APInt DemandedMask(VectorWidth, 0);
173  DemandedMask.setBit(IndexVal);
174  if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask,
175  UndefElts)) {
176  EI.setOperand(0, V);
177  return &EI;
178  }
179  }
180 
181  // If this extractelement is directly using a bitcast from a vector of
182  // the same number of elements, see if we can find the source element from
183  // it. In this case, we will end up needing to bitcast the scalars.
184  if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
185  if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
186  if (VT->getNumElements() == VectorWidth)
187  if (Value *Elt = findScalarElement(BCI->getOperand(0), IndexVal))
188  return new BitCastInst(Elt, EI.getType());
189  }
190 
191  // If there's a vector PHI feeding a scalar use through this extractelement
192  // instruction, try to scalarize the PHI.
193  if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) {
194  Instruction *scalarPHI = scalarizePHI(EI, PN);
195  if (scalarPHI)
196  return scalarPHI;
197  }
198  }
199 
200  if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
201  // Push extractelement into predecessor operation if legal and
202  // profitable to do so.
203  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
204  if (I->hasOneUse() &&
205  cheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
206  Value *newEI0 =
207  Builder.CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
208  EI.getName()+".lhs");
209  Value *newEI1 =
210  Builder.CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
211  EI.getName()+".rhs");
212  return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(),
213  newEI0, newEI1, BO);
214  }
215  } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
216  // Extracting the inserted element?
217  if (IE->getOperand(2) == EI.getOperand(1))
218  return replaceInstUsesWith(EI, IE->getOperand(1));
219  // If the inserted and extracted elements are constants, they must not
220  // be the same value, extract from the pre-inserted value instead.
221  if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
222  Worklist.AddValue(EI.getOperand(0));
223  EI.setOperand(0, IE->getOperand(0));
224  return &EI;
225  }
226  } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
227  // If this is extracting an element from a shufflevector, figure out where
228  // it came from and extract from the appropriate input element instead.
229  if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
230  int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
231  Value *Src;
232  unsigned LHSWidth =
233  SVI->getOperand(0)->getType()->getVectorNumElements();
234 
235  if (SrcIdx < 0)
236  return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
237  if (SrcIdx < (int)LHSWidth)
238  Src = SVI->getOperand(0);
239  else {
240  SrcIdx -= LHSWidth;
241  Src = SVI->getOperand(1);
242  }
244  return ExtractElementInst::Create(Src,
245  ConstantInt::get(Int32Ty,
246  SrcIdx, false));
247  }
248  } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
249  // Canonicalize extractelement(cast) -> cast(extractelement).
250  // Bitcasts can change the number of vector elements, and they cost
251  // nothing.
252  if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
253  Value *EE = Builder.CreateExtractElement(CI->getOperand(0),
254  EI.getIndexOperand());
255  Worklist.AddValue(EE);
256  return CastInst::Create(CI->getOpcode(), EE, EI.getType());
257  }
258  } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
259  if (SI->hasOneUse()) {
260  // TODO: For a select on vectors, it might be useful to do this if it
261  // has multiple extractelement uses. For vector select, that seems to
262  // fight the vectorizer.
263 
264  // If we are extracting an element from a vector select or a select on
265  // vectors, create a select on the scalars extracted from the vector
266  // arguments.
267  Value *TrueVal = SI->getTrueValue();
268  Value *FalseVal = SI->getFalseValue();
269 
270  Value *Cond = SI->getCondition();
271  if (Cond->getType()->isVectorTy()) {
272  Cond = Builder.CreateExtractElement(Cond,
273  EI.getIndexOperand(),
274  Cond->getName() + ".elt");
275  }
276 
277  Value *V1Elem
278  = Builder.CreateExtractElement(TrueVal,
279  EI.getIndexOperand(),
280  TrueVal->getName() + ".elt");
281 
282  Value *V2Elem
283  = Builder.CreateExtractElement(FalseVal,
284  EI.getIndexOperand(),
285  FalseVal->getName() + ".elt");
286  return SelectInst::Create(Cond,
287  V1Elem,
288  V2Elem,
289  SI->getName() + ".elt");
290  }
291  }
292  }
293  return nullptr;
294 }
295 
296 /// If V is a shuffle of values that ONLY returns elements from either LHS or
297 /// RHS, return the shuffle mask and true. Otherwise, return false.
298 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
300  assert(LHS->getType() == RHS->getType() &&
301  "Invalid CollectSingleShuffleElements");
302  unsigned NumElts = V->getType()->getVectorNumElements();
303 
304  if (isa<UndefValue>(V)) {
305  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
306  return true;
307  }
308 
309  if (V == LHS) {
310  for (unsigned i = 0; i != NumElts; ++i)
312  return true;
313  }
314 
315  if (V == RHS) {
316  for (unsigned i = 0; i != NumElts; ++i)
318  i+NumElts));
319  return true;
320  }
321 
322  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
323  // If this is an insert of an extract from some other vector, include it.
324  Value *VecOp = IEI->getOperand(0);
325  Value *ScalarOp = IEI->getOperand(1);
326  Value *IdxOp = IEI->getOperand(2);
327 
328  if (!isa<ConstantInt>(IdxOp))
329  return false;
330  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
331 
332  if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
333  // We can handle this if the vector we are inserting into is
334  // transitively ok.
335  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
336  // If so, update the mask to reflect the inserted undef.
337  Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
338  return true;
339  }
340  } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
341  if (isa<ConstantInt>(EI->getOperand(1))) {
342  unsigned ExtractedIdx =
343  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
344  unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
345 
346  // This must be extracting from either LHS or RHS.
347  if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
348  // We can handle this if the vector we are inserting into is
349  // transitively ok.
350  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
351  // If so, update the mask to reflect the inserted value.
352  if (EI->getOperand(0) == LHS) {
353  Mask[InsertedIdx % NumElts] =
355  ExtractedIdx);
356  } else {
357  assert(EI->getOperand(0) == RHS);
358  Mask[InsertedIdx % NumElts] =
360  ExtractedIdx + NumLHSElts);
361  }
362  return true;
363  }
364  }
365  }
366  }
367  }
368 
369  return false;
370 }
371 
372 /// If we have insertion into a vector that is wider than the vector that we
373 /// are extracting from, try to widen the source vector to allow a single
374 /// shufflevector to replace one or more insert/extract pairs.
376  ExtractElementInst *ExtElt,
377  InstCombiner &IC) {
378  VectorType *InsVecType = InsElt->getType();
379  VectorType *ExtVecType = ExtElt->getVectorOperandType();
380  unsigned NumInsElts = InsVecType->getVectorNumElements();
381  unsigned NumExtElts = ExtVecType->getVectorNumElements();
382 
383  // The inserted-to vector must be wider than the extracted-from vector.
384  if (InsVecType->getElementType() != ExtVecType->getElementType() ||
385  NumExtElts >= NumInsElts)
386  return;
387 
388  // Create a shuffle mask to widen the extended-from vector using undefined
389  // values. The mask selects all of the values of the original vector followed
390  // by as many undefined values as needed to create a vector of the same length
391  // as the inserted-to vector.
392  SmallVector<Constant *, 16> ExtendMask;
393  IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
394  for (unsigned i = 0; i < NumExtElts; ++i)
395  ExtendMask.push_back(ConstantInt::get(IntType, i));
396  for (unsigned i = NumExtElts; i < NumInsElts; ++i)
397  ExtendMask.push_back(UndefValue::get(IntType));
398 
399  Value *ExtVecOp = ExtElt->getVectorOperand();
400  auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
401  BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
402  ? ExtVecOpInst->getParent()
403  : ExtElt->getParent();
404 
405  // TODO: This restriction matches the basic block check below when creating
406  // new extractelement instructions. If that limitation is removed, this one
407  // could also be removed. But for now, we just bail out to ensure that we
408  // will replace the extractelement instruction that is feeding our
409  // insertelement instruction. This allows the insertelement to then be
410  // replaced by a shufflevector. If the insertelement is not replaced, we can
411  // induce infinite looping because there's an optimization for extractelement
412  // that will delete our widening shuffle. This would trigger another attempt
413  // here to create that shuffle, and we spin forever.
414  if (InsertionBlock != InsElt->getParent())
415  return;
416 
417  // TODO: This restriction matches the check in visitInsertElementInst() and
418  // prevents an infinite loop caused by not turning the extract/insert pair
419  // into a shuffle. We really should not need either check, but we're lacking
420  // folds for shufflevectors because we're afraid to generate shuffle masks
421  // that the backend can't handle.
422  if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
423  return;
424 
425  auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
426  ConstantVector::get(ExtendMask));
427 
428  // Insert the new shuffle after the vector operand of the extract is defined
429  // (as long as it's not a PHI) or at the start of the basic block of the
430  // extract, so any subsequent extracts in the same basic block can use it.
431  // TODO: Insert before the earliest ExtractElementInst that is replaced.
432  if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
433  WideVec->insertAfter(ExtVecOpInst);
434  else
435  IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
436 
437  // Replace extracts from the original narrow vector with extracts from the new
438  // wide vector.
439  for (User *U : ExtVecOp->users()) {
441  if (!OldExt || OldExt->getParent() != WideVec->getParent())
442  continue;
443  auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
444  NewExt->insertAfter(OldExt);
445  IC.replaceInstUsesWith(*OldExt, NewExt);
446  }
447 }
448 
449 /// We are building a shuffle to create V, which is a sequence of insertelement,
450 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
451 /// not rely on the second vector source. Return a std::pair containing the
452 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
453 /// parameter as required.
454 ///
455 /// Note: we intentionally don't try to fold earlier shuffles since they have
456 /// often been chosen carefully to be efficiently implementable on the target.
457 typedef std::pair<Value *, Value *> ShuffleOps;
458 
461  Value *PermittedRHS,
462  InstCombiner &IC) {
463  assert(V->getType()->isVectorTy() && "Invalid shuffle!");
464  unsigned NumElts = V->getType()->getVectorNumElements();
465 
466  if (isa<UndefValue>(V)) {
467  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
468  return std::make_pair(
469  PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
470  }
471 
472  if (isa<ConstantAggregateZero>(V)) {
473  Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
474  return std::make_pair(V, nullptr);
475  }
476 
477  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
478  // If this is an insert of an extract from some other vector, include it.
479  Value *VecOp = IEI->getOperand(0);
480  Value *ScalarOp = IEI->getOperand(1);
481  Value *IdxOp = IEI->getOperand(2);
482 
483  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
484  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
485  unsigned ExtractedIdx =
486  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
487  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
488 
489  // Either the extracted from or inserted into vector must be RHSVec,
490  // otherwise we'd end up with a shuffle of three inputs.
491  if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
492  Value *RHS = EI->getOperand(0);
493  ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
494  assert(LR.second == nullptr || LR.second == RHS);
495 
496  if (LR.first->getType() != RHS->getType()) {
497  // Although we are giving up for now, see if we can create extracts
498  // that match the inserts for another round of combining.
499  replaceExtractElements(IEI, EI, IC);
500 
501  // We tried our best, but we can't find anything compatible with RHS
502  // further up the chain. Return a trivial shuffle.
503  for (unsigned i = 0; i < NumElts; ++i)
504  Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
505  return std::make_pair(V, nullptr);
506  }
507 
508  unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
509  Mask[InsertedIdx % NumElts] =
511  NumLHSElts+ExtractedIdx);
512  return std::make_pair(LR.first, RHS);
513  }
514 
515  if (VecOp == PermittedRHS) {
516  // We've gone as far as we can: anything on the other side of the
517  // extractelement will already have been converted into a shuffle.
518  unsigned NumLHSElts =
520  for (unsigned i = 0; i != NumElts; ++i)
523  i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
524  return std::make_pair(EI->getOperand(0), PermittedRHS);
525  }
526 
527  // If this insertelement is a chain that comes from exactly these two
528  // vectors, return the vector and the effective shuffle.
529  if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
530  collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
531  Mask))
532  return std::make_pair(EI->getOperand(0), PermittedRHS);
533  }
534  }
535  }
536 
537  // Otherwise, we can't do anything fancy. Return an identity vector.
538  for (unsigned i = 0; i != NumElts; ++i)
540  return std::make_pair(V, nullptr);
541 }
542 
543 /// Try to find redundant insertvalue instructions, like the following ones:
544 /// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
545 /// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
546 /// Here the second instruction inserts values at the same indices, as the
547 /// first one, making the first one redundant.
548 /// It should be transformed to:
549 /// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
551  bool IsRedundant = false;
552  ArrayRef<unsigned int> FirstIndices = I.getIndices();
553 
554  // If there is a chain of insertvalue instructions (each of them except the
555  // last one has only one use and it's another insertvalue insn from this
556  // chain), check if any of the 'children' uses the same indices as the first
557  // instruction. In this case, the first one is redundant.
558  Value *V = &I;
559  unsigned Depth = 0;
560  while (V->hasOneUse() && Depth < 10) {
561  User *U = V->user_back();
562  auto UserInsInst = dyn_cast<InsertValueInst>(U);
563  if (!UserInsInst || U->getOperand(0) != V)
564  break;
565  if (UserInsInst->getIndices() == FirstIndices) {
566  IsRedundant = true;
567  break;
568  }
569  V = UserInsInst;
570  Depth++;
571  }
572 
573  if (IsRedundant)
574  return replaceInstUsesWith(I, I.getOperand(0));
575  return nullptr;
576 }
577 
579  int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
580  int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
581 
582  // A vector select does not change the size of the operands.
583  if (MaskSize != VecSize)
584  return false;
585 
586  // Each mask element must be undefined or choose a vector element from one of
587  // the source operands without crossing vector lanes.
588  for (int i = 0; i != MaskSize; ++i) {
589  int Elt = Shuf.getMaskValue(i);
590  if (Elt != -1 && Elt != i && Elt != i + VecSize)
591  return false;
592  }
593 
594  return true;
595 }
596 
597 // Turn a chain of inserts that splats a value into a canonical insert + shuffle
598 // splat. That is:
599 // insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
600 // shufflevector(insertelt(X, %k, 0), undef, zero)
602  // We are interested in the last insert in a chain. So, if this insert
603  // has a single user, and that user is an insert, bail.
604  if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
605  return nullptr;
606 
607  VectorType *VT = cast<VectorType>(InsElt.getType());
608  int NumElements = VT->getNumElements();
609 
610  // Do not try to do this for a one-element vector, since that's a nop,
611  // and will cause an inf-loop.
612  if (NumElements == 1)
613  return nullptr;
614 
615  Value *SplatVal = InsElt.getOperand(1);
616  InsertElementInst *CurrIE = &InsElt;
617  SmallVector<bool, 16> ElementPresent(NumElements, false);
618 
619  // Walk the chain backwards, keeping track of which indices we inserted into,
620  // until we hit something that isn't an insert of the splatted value.
621  while (CurrIE) {
622  ConstantInt *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
623  if (!Idx || CurrIE->getOperand(1) != SplatVal)
624  return nullptr;
625 
626  // Check none of the intermediate steps have any additional uses.
627  if ((CurrIE != &InsElt) && !CurrIE->hasOneUse())
628  return nullptr;
629 
630  ElementPresent[Idx->getZExtValue()] = true;
631  CurrIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
632  }
633 
634  // Make sure we've seen an insert into every element.
635  if (llvm::any_of(ElementPresent, [](bool Present) { return !Present; }))
636  return nullptr;
637 
638  // All right, create the insert + shuffle.
639  Instruction *InsertFirst = InsertElementInst::Create(
640  UndefValue::get(VT), SplatVal,
641  ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), 0), "", &InsElt);
642 
644  VectorType::get(Type::getInt32Ty(InsElt.getContext()), NumElements));
645 
646  return new ShuffleVectorInst(InsertFirst, UndefValue::get(VT), ZeroMask);
647 }
648 
649 /// If we have an insertelement instruction feeding into another insertelement
650 /// and the 2nd is inserting a constant into the vector, canonicalize that
651 /// constant insertion before the insertion of a variable:
652 ///
653 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
654 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
655 ///
656 /// This has the potential of eliminating the 2nd insertelement instruction
657 /// via constant folding of the scalar constant into a vector constant.
659  InstCombiner::BuilderTy &Builder) {
660  auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
661  if (!InsElt1 || !InsElt1->hasOneUse())
662  return nullptr;
663 
664  Value *X, *Y;
665  Constant *ScalarC;
666  ConstantInt *IdxC1, *IdxC2;
667  if (match(InsElt1->getOperand(0), m_Value(X)) &&
668  match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
669  match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
670  match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
671  match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
672  Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
673  return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
674  }
675 
676  return nullptr;
677 }
678 
679 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
680 /// --> shufflevector X, CVec', Mask'
682  auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
683  // Bail out if the parent has more than one use. In that case, we'd be
684  // replacing the insertelt with a shuffle, and that's not a clear win.
685  if (!Inst || !Inst->hasOneUse())
686  return nullptr;
687  if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
688  // The shuffle must have a constant vector operand. The insertelt must have
689  // a constant scalar being inserted at a constant position in the vector.
690  Constant *ShufConstVec, *InsEltScalar;
691  uint64_t InsEltIndex;
692  if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
693  !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
694  !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
695  return nullptr;
696 
697  // Adding an element to an arbitrary shuffle could be expensive, but a
698  // shuffle that selects elements from vectors without crossing lanes is
699  // assumed cheap.
700  // If we're just adding a constant into that shuffle, it will still be
701  // cheap.
702  if (!isShuffleEquivalentToSelect(*Shuf))
703  return nullptr;
704 
705  // From the above 'select' check, we know that the mask has the same number
706  // of elements as the vector input operands. We also know that each constant
707  // input element is used in its lane and can not be used more than once by
708  // the shuffle. Therefore, replace the constant in the shuffle's constant
709  // vector with the insertelt constant. Replace the constant in the shuffle's
710  // mask vector with the insertelt index plus the length of the vector
711  // (because the constant vector operand of a shuffle is always the 2nd
712  // operand).
713  Constant *Mask = Shuf->getMask();
714  unsigned NumElts = Mask->getType()->getVectorNumElements();
715  SmallVector<Constant *, 16> NewShufElts(NumElts);
716  SmallVector<Constant *, 16> NewMaskElts(NumElts);
717  for (unsigned I = 0; I != NumElts; ++I) {
718  if (I == InsEltIndex) {
719  NewShufElts[I] = InsEltScalar;
720  Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
721  NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
722  } else {
723  // Copy over the existing values.
724  NewShufElts[I] = ShufConstVec->getAggregateElement(I);
725  NewMaskElts[I] = Mask->getAggregateElement(I);
726  }
727  }
728 
729  // Create new operands for a shuffle that includes the constant of the
730  // original insertelt. The old shuffle will be dead now.
731  return new ShuffleVectorInst(Shuf->getOperand(0),
732  ConstantVector::get(NewShufElts),
733  ConstantVector::get(NewMaskElts));
734  } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
735  // Transform sequences of insertelements ops with constant data/indexes into
736  // a single shuffle op.
737  unsigned NumElts = InsElt.getType()->getNumElements();
738 
739  uint64_t InsertIdx[2];
740  Constant *Val[2];
741  if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
742  !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
743  !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
744  !match(IEI->getOperand(1), m_Constant(Val[1])))
745  return nullptr;
746  SmallVector<Constant *, 16> Values(NumElts);
748  auto ValI = std::begin(Val);
749  // Generate new constant vector and mask.
750  // We have 2 values/masks from the insertelements instructions. Insert them
751  // into new value/mask vectors.
752  for (uint64_t I : InsertIdx) {
753  if (!Values[I]) {
754  assert(!Mask[I]);
755  Values[I] = *ValI;
756  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
757  NumElts + I);
758  }
759  ++ValI;
760  }
761  // Remaining values are filled with 'undef' values.
762  for (unsigned I = 0; I < NumElts; ++I) {
763  if (!Values[I]) {
764  assert(!Mask[I]);
765  Values[I] = UndefValue::get(InsElt.getType()->getElementType());
766  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
767  }
768  }
769  // Create new operands for a shuffle that includes the constant of the
770  // original insertelt.
771  return new ShuffleVectorInst(IEI->getOperand(0),
772  ConstantVector::get(Values),
773  ConstantVector::get(Mask));
774  }
775  return nullptr;
776 }
777 
779  Value *VecOp = IE.getOperand(0);
780  Value *ScalarOp = IE.getOperand(1);
781  Value *IdxOp = IE.getOperand(2);
782 
783  // Inserting an undef or into an undefined place, remove this.
784  if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
785  replaceInstUsesWith(IE, VecOp);
786 
787  // If the inserted element was extracted from some other vector, and if the
788  // indexes are constant, try to turn this into a shufflevector operation.
789  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
790  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
791  unsigned NumInsertVectorElts = IE.getType()->getNumElements();
792  unsigned NumExtractVectorElts =
794  unsigned ExtractedIdx =
795  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
796  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
797 
798  if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
799  return replaceInstUsesWith(IE, VecOp);
800 
801  if (InsertedIdx >= NumInsertVectorElts) // Out of range insert.
802  return replaceInstUsesWith(IE, UndefValue::get(IE.getType()));
803 
804  // If we are extracting a value from a vector, then inserting it right
805  // back into the same place, just use the input vector.
806  if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
807  return replaceInstUsesWith(IE, VecOp);
808 
809  // If this insertelement isn't used by some other insertelement, turn it
810  // (and any insertelements it points to), into one big shuffle.
811  if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) {
813  ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
814 
815  // The proposed shuffle may be trivial, in which case we shouldn't
816  // perform the combine.
817  if (LR.first != &IE && LR.second != &IE) {
818  // We now have a shuffle of LHS, RHS, Mask.
819  if (LR.second == nullptr)
820  LR.second = UndefValue::get(LR.first->getType());
821  return new ShuffleVectorInst(LR.first, LR.second,
822  ConstantVector::get(Mask));
823  }
824  }
825  }
826  }
827 
828  unsigned VWidth = VecOp->getType()->getVectorNumElements();
829  APInt UndefElts(VWidth, 0);
830  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
831  if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
832  if (V != &IE)
833  return replaceInstUsesWith(IE, V);
834  return &IE;
835  }
836 
838  return Shuf;
839 
840  if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
841  return NewInsElt;
842 
843  // Turn a sequence of inserts that broadcasts a scalar into a single
844  // insert + shufflevector.
845  if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE))
846  return Broadcast;
847 
848  return nullptr;
849 }
850 
851 /// Return true if we can evaluate the specified expression tree if the vector
852 /// elements were shuffled in a different order.
854  unsigned Depth = 5) {
855  // We can always reorder the elements of a constant.
856  if (isa<Constant>(V))
857  return true;
858 
859  // We won't reorder vector arguments. No IPO here.
861  if (!I) return false;
862 
863  // Two users may expect different orders of the elements. Don't try it.
864  if (!I->hasOneUse())
865  return false;
866 
867  if (Depth == 0) return false;
868 
869  switch (I->getOpcode()) {
870  case Instruction::Add:
871  case Instruction::FAdd:
872  case Instruction::Sub:
873  case Instruction::FSub:
874  case Instruction::Mul:
875  case Instruction::FMul:
876  case Instruction::UDiv:
877  case Instruction::SDiv:
878  case Instruction::FDiv:
879  case Instruction::URem:
880  case Instruction::SRem:
881  case Instruction::FRem:
882  case Instruction::Shl:
883  case Instruction::LShr:
884  case Instruction::AShr:
885  case Instruction::And:
886  case Instruction::Or:
887  case Instruction::Xor:
888  case Instruction::ICmp:
889  case Instruction::FCmp:
890  case Instruction::Trunc:
891  case Instruction::ZExt:
892  case Instruction::SExt:
893  case Instruction::FPToUI:
894  case Instruction::FPToSI:
895  case Instruction::UIToFP:
896  case Instruction::SIToFP:
897  case Instruction::FPTrunc:
898  case Instruction::FPExt:
899  case Instruction::GetElementPtr: {
900  for (Value *Operand : I->operands()) {
901  if (!CanEvaluateShuffled(Operand, Mask, Depth-1))
902  return false;
903  }
904  return true;
905  }
906  case Instruction::InsertElement: {
908  if (!CI) return false;
909  int ElementNumber = CI->getLimitedValue();
910 
911  // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
912  // can't put an element into multiple indices.
913  bool SeenOnce = false;
914  for (int i = 0, e = Mask.size(); i != e; ++i) {
915  if (Mask[i] == ElementNumber) {
916  if (SeenOnce)
917  return false;
918  SeenOnce = true;
919  }
920  }
921  return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1);
922  }
923  }
924  return false;
925 }
926 
927 /// Rebuild a new instruction just like 'I' but with the new operands given.
928 /// In the event of type mismatch, the type of the operands is correct.
930  // We don't want to use the IRBuilder here because we want the replacement
931  // instructions to appear next to 'I', not the builder's insertion point.
932  switch (I->getOpcode()) {
933  case Instruction::Add:
934  case Instruction::FAdd:
935  case Instruction::Sub:
936  case Instruction::FSub:
937  case Instruction::Mul:
938  case Instruction::FMul:
939  case Instruction::UDiv:
940  case Instruction::SDiv:
941  case Instruction::FDiv:
942  case Instruction::URem:
943  case Instruction::SRem:
944  case Instruction::FRem:
945  case Instruction::Shl:
946  case Instruction::LShr:
947  case Instruction::AShr:
948  case Instruction::And:
949  case Instruction::Or:
950  case Instruction::Xor: {
951  BinaryOperator *BO = cast<BinaryOperator>(I);
952  assert(NewOps.size() == 2 && "binary operator with #ops != 2");
953  BinaryOperator *New =
954  BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
955  NewOps[0], NewOps[1], "", BO);
956  if (isa<OverflowingBinaryOperator>(BO)) {
957  New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
958  New->setHasNoSignedWrap(BO->hasNoSignedWrap());
959  }
960  if (isa<PossiblyExactOperator>(BO)) {
961  New->setIsExact(BO->isExact());
962  }
963  if (isa<FPMathOperator>(BO))
964  New->copyFastMathFlags(I);
965  return New;
966  }
967  case Instruction::ICmp:
968  assert(NewOps.size() == 2 && "icmp with #ops != 2");
969  return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
970  NewOps[0], NewOps[1]);
971  case Instruction::FCmp:
972  assert(NewOps.size() == 2 && "fcmp with #ops != 2");
973  return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
974  NewOps[0], NewOps[1]);
975  case Instruction::Trunc:
976  case Instruction::ZExt:
977  case Instruction::SExt:
978  case Instruction::FPToUI:
979  case Instruction::FPToSI:
980  case Instruction::UIToFP:
981  case Instruction::SIToFP:
982  case Instruction::FPTrunc:
983  case Instruction::FPExt: {
984  // It's possible that the mask has a different number of elements from
985  // the original cast. We recompute the destination type to match the mask.
986  Type *DestTy =
988  NewOps[0]->getType()->getVectorNumElements());
989  assert(NewOps.size() == 1 && "cast with #ops != 1");
990  return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
991  "", I);
992  }
993  case Instruction::GetElementPtr: {
994  Value *Ptr = NewOps[0];
995  ArrayRef<Value*> Idx = NewOps.slice(1);
997  cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
998  GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
999  return GEP;
1000  }
1001  }
1002  llvm_unreachable("failed to rebuild vector instructions");
1003 }
1004 
1005 Value *
1006 InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
1007  // Mask.size() does not need to be equal to the number of vector elements.
1008 
1009  assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1010  if (isa<UndefValue>(V)) {
1012  Mask.size()));
1013  }
1014  if (isa<ConstantAggregateZero>(V)) {
1017  Mask.size()));
1018  }
1019  if (Constant *C = dyn_cast<Constant>(V)) {
1020  SmallVector<Constant *, 16> MaskValues;
1021  for (int i = 0, e = Mask.size(); i != e; ++i) {
1022  if (Mask[i] == -1)
1023  MaskValues.push_back(UndefValue::get(Builder.getInt32Ty()));
1024  else
1025  MaskValues.push_back(Builder.getInt32(Mask[i]));
1026  }
1028  ConstantVector::get(MaskValues));
1029  }
1030 
1031  Instruction *I = cast<Instruction>(V);
1032  switch (I->getOpcode()) {
1033  case Instruction::Add:
1034  case Instruction::FAdd:
1035  case Instruction::Sub:
1036  case Instruction::FSub:
1037  case Instruction::Mul:
1038  case Instruction::FMul:
1039  case Instruction::UDiv:
1040  case Instruction::SDiv:
1041  case Instruction::FDiv:
1042  case Instruction::URem:
1043  case Instruction::SRem:
1044  case Instruction::FRem:
1045  case Instruction::Shl:
1046  case Instruction::LShr:
1047  case Instruction::AShr:
1048  case Instruction::And:
1049  case Instruction::Or:
1050  case Instruction::Xor:
1051  case Instruction::ICmp:
1052  case Instruction::FCmp:
1053  case Instruction::Trunc:
1054  case Instruction::ZExt:
1055  case Instruction::SExt:
1056  case Instruction::FPToUI:
1057  case Instruction::FPToSI:
1058  case Instruction::UIToFP:
1059  case Instruction::SIToFP:
1060  case Instruction::FPTrunc:
1061  case Instruction::FPExt:
1062  case Instruction::Select:
1063  case Instruction::GetElementPtr: {
1064  SmallVector<Value*, 8> NewOps;
1065  bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1066  for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1067  Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask);
1068  NewOps.push_back(V);
1069  NeedsRebuild |= (V != I->getOperand(i));
1070  }
1071  if (NeedsRebuild) {
1072  return buildNew(I, NewOps);
1073  }
1074  return I;
1075  }
1076  case Instruction::InsertElement: {
1077  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1078 
1079  // The insertelement was inserting at Element. Figure out which element
1080  // that becomes after shuffling. The answer is guaranteed to be unique
1081  // by CanEvaluateShuffled.
1082  bool Found = false;
1083  int Index = 0;
1084  for (int e = Mask.size(); Index != e; ++Index) {
1085  if (Mask[Index] == Element) {
1086  Found = true;
1087  break;
1088  }
1089  }
1090 
1091  // If element is not in Mask, no need to handle the operand 1 (element to
1092  // be inserted). Just evaluate values in operand 0 according to Mask.
1093  if (!Found)
1094  return EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1095 
1096  Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1097  return InsertElementInst::Create(V, I->getOperand(1),
1098  Builder.getInt32(Index), "", I);
1099  }
1100  }
1101  llvm_unreachable("failed to reorder elements of vector instruction!");
1102 }
1103 
1105  bool &isLHSID, bool &isRHSID) {
1106  isLHSID = isRHSID = true;
1107 
1108  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1109  if (Mask[i] < 0) continue; // Ignore undef values.
1110  // Is this an identity shuffle of the LHS value?
1111  isLHSID &= (Mask[i] == (int)i);
1112 
1113  // Is this an identity shuffle of the RHS value?
1114  isRHSID &= (Mask[i]-e == i);
1115  }
1116 }
1117 
1118 // Returns true if the shuffle is extracting a contiguous range of values from
1119 // LHS, for example:
1120 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1121 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1122 // Shuffles to: |EE|FF|GG|HH|
1123 // +--+--+--+--+
1125  SmallVector<int, 16> &Mask) {
1126  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1127  unsigned MaskElems = Mask.size();
1128  unsigned BegIdx = Mask.front();
1129  unsigned EndIdx = Mask.back();
1130  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1131  return false;
1132  for (unsigned I = 0; I != MaskElems; ++I)
1133  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1134  return false;
1135  return true;
1136 }
1137 
1139  Value *LHS = SVI.getOperand(0);
1140  Value *RHS = SVI.getOperand(1);
1141  SmallVector<int, 16> Mask = SVI.getShuffleMask();
1143 
1144  if (auto *V = SimplifyShuffleVectorInst(
1145  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1146  return replaceInstUsesWith(SVI, V);
1147 
1148  bool MadeChange = false;
1149  unsigned VWidth = SVI.getType()->getVectorNumElements();
1150 
1151  APInt UndefElts(VWidth, 0);
1152  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1153  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1154  if (V != &SVI)
1155  return replaceInstUsesWith(SVI, V);
1156  LHS = SVI.getOperand(0);
1157  RHS = SVI.getOperand(1);
1158  MadeChange = true;
1159  }
1160 
1161  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1162 
1163  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1164  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1165  if (LHS == RHS || isa<UndefValue>(LHS)) {
1166  if (isa<UndefValue>(LHS) && LHS == RHS) {
1167  // shuffle(undef,undef,mask) -> undef.
1168  Value *Result = (VWidth == LHSWidth)
1169  ? LHS : UndefValue::get(SVI.getType());
1170  return replaceInstUsesWith(SVI, Result);
1171  }
1172 
1173  // Remap any references to RHS to use LHS.
1175  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1176  if (Mask[i] < 0) {
1177  Elts.push_back(UndefValue::get(Int32Ty));
1178  continue;
1179  }
1180 
1181  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1182  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1183  Mask[i] = -1; // Turn into undef.
1184  Elts.push_back(UndefValue::get(Int32Ty));
1185  } else {
1186  Mask[i] = Mask[i] % e; // Force to LHS.
1187  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1188  }
1189  }
1190  SVI.setOperand(0, SVI.getOperand(1));
1191  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1192  SVI.setOperand(2, ConstantVector::get(Elts));
1193  LHS = SVI.getOperand(0);
1194  RHS = SVI.getOperand(1);
1195  MadeChange = true;
1196  }
1197 
1198  if (VWidth == LHSWidth) {
1199  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1200  bool isLHSID, isRHSID;
1201  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1202 
1203  // Eliminate identity shuffles.
1204  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1205  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1206  }
1207 
1208  if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
1209  Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
1210  return replaceInstUsesWith(SVI, V);
1211  }
1212 
1213  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1214  // a non-vector type. We can instead bitcast the original vector followed by
1215  // an extract of the desired element:
1216  //
1217  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1218  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1219  // %1 = bitcast <4 x i8> %sroa to i32
1220  // Becomes:
1221  // %bc = bitcast <16 x i8> %in to <4 x i32>
1222  // %ext = extractelement <4 x i32> %bc, i32 0
1223  //
1224  // If the shuffle is extracting a contiguous range of values from the input
1225  // vector then each use which is a bitcast of the extracted size can be
1226  // replaced. This will work if the vector types are compatible, and the begin
1227  // index is aligned to a value in the casted vector type. If the begin index
1228  // isn't aligned then we can shuffle the original vector (keeping the same
1229  // vector type) before extracting.
1230  //
1231  // This code will bail out if the target type is fundamentally incompatible
1232  // with vectors of the source type.
1233  //
1234  // Example of <16 x i8>, target type i32:
1235  // Index range [4,8): v-----------v Will work.
1236  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1237  // <16 x i8>: | | | | | | | | | | | | | | | | |
1238  // <4 x i32>: | | | | |
1239  // +-----------+-----------+-----------+-----------+
1240  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1241  // Target type i40: ^--------------^ Won't work, bail.
1242  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1243  Value *V = LHS;
1244  unsigned MaskElems = Mask.size();
1245  VectorType *SrcTy = cast<VectorType>(V->getType());
1246  unsigned VecBitWidth = SrcTy->getBitWidth();
1247  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1248  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1249  unsigned SrcNumElems = SrcTy->getNumElements();
1252  for (User *U : SVI.users())
1253  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1254  if (!BC->use_empty())
1255  // Only visit bitcasts that weren't previously handled.
1256  BCs.push_back(BC);
1257  for (BitCastInst *BC : BCs) {
1258  unsigned BegIdx = Mask.front();
1259  Type *TgtTy = BC->getDestTy();
1260  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1261  if (!TgtElemBitWidth)
1262  continue;
1263  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1264  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1265  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1266  if (!VecBitWidthsEqual)
1267  continue;
1268  if (!VectorType::isValidElementType(TgtTy))
1269  continue;
1270  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1271  if (!BegIsAligned) {
1272  // Shuffle the input so [0,NumElements) contains the output, and
1273  // [NumElems,SrcNumElems) is undef.
1274  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1275  UndefValue::get(Int32Ty));
1276  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1277  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1278  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1279  ConstantVector::get(ShuffleMask),
1280  SVI.getName() + ".extract");
1281  BegIdx = 0;
1282  }
1283  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1284  assert(SrcElemsPerTgtElem);
1285  BegIdx /= SrcElemsPerTgtElem;
1286  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1287  auto *NewBC =
1288  BCAlreadyExists
1289  ? NewBCs[CastSrcTy]
1290  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1291  if (!BCAlreadyExists)
1292  NewBCs[CastSrcTy] = NewBC;
1293  auto *Ext = Builder.CreateExtractElement(
1294  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1295  // The shufflevector isn't being replaced: the bitcast that used it
1296  // is. InstCombine will visit the newly-created instructions.
1297  replaceInstUsesWith(*BC, Ext);
1298  MadeChange = true;
1299  }
1300  }
1301 
1302  // If the LHS is a shufflevector itself, see if we can combine it with this
1303  // one without producing an unusual shuffle.
1304  // Cases that might be simplified:
1305  // 1.
1306  // x1=shuffle(v1,v2,mask1)
1307  // x=shuffle(x1,undef,mask)
1308  // ==>
1309  // x=shuffle(v1,undef,newMask)
1310  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1311  // 2.
1312  // x1=shuffle(v1,undef,mask1)
1313  // x=shuffle(x1,x2,mask)
1314  // where v1.size() == mask1.size()
1315  // ==>
1316  // x=shuffle(v1,x2,newMask)
1317  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1318  // 3.
1319  // x2=shuffle(v2,undef,mask2)
1320  // x=shuffle(x1,x2,mask)
1321  // where v2.size() == mask2.size()
1322  // ==>
1323  // x=shuffle(x1,v2,newMask)
1324  // newMask[i] = (mask[i] < x1.size())
1325  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1326  // 4.
1327  // x1=shuffle(v1,undef,mask1)
1328  // x2=shuffle(v2,undef,mask2)
1329  // x=shuffle(x1,x2,mask)
1330  // where v1.size() == v2.size()
1331  // ==>
1332  // x=shuffle(v1,v2,newMask)
1333  // newMask[i] = (mask[i] < x1.size())
1334  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1335  //
1336  // Here we are really conservative:
1337  // we are absolutely afraid of producing a shuffle mask not in the input
1338  // program, because the code gen may not be smart enough to turn a merged
1339  // shuffle into two specific shuffles: it may produce worse code. As such,
1340  // we only merge two shuffles if the result is either a splat or one of the
1341  // input shuffle masks. In this case, merging the shuffles just removes
1342  // one instruction, which we know is safe. This is good for things like
1343  // turning: (splat(splat)) -> splat, or
1344  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1345  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1346  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1347  if (LHSShuffle)
1348  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1349  LHSShuffle = nullptr;
1350  if (RHSShuffle)
1351  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1352  RHSShuffle = nullptr;
1353  if (!LHSShuffle && !RHSShuffle)
1354  return MadeChange ? &SVI : nullptr;
1355 
1356  Value* LHSOp0 = nullptr;
1357  Value* LHSOp1 = nullptr;
1358  Value* RHSOp0 = nullptr;
1359  unsigned LHSOp0Width = 0;
1360  unsigned RHSOp0Width = 0;
1361  if (LHSShuffle) {
1362  LHSOp0 = LHSShuffle->getOperand(0);
1363  LHSOp1 = LHSShuffle->getOperand(1);
1364  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1365  }
1366  if (RHSShuffle) {
1367  RHSOp0 = RHSShuffle->getOperand(0);
1368  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1369  }
1370  Value* newLHS = LHS;
1371  Value* newRHS = RHS;
1372  if (LHSShuffle) {
1373  // case 1
1374  if (isa<UndefValue>(RHS)) {
1375  newLHS = LHSOp0;
1376  newRHS = LHSOp1;
1377  }
1378  // case 2 or 4
1379  else if (LHSOp0Width == LHSWidth) {
1380  newLHS = LHSOp0;
1381  }
1382  }
1383  // case 3 or 4
1384  if (RHSShuffle && RHSOp0Width == LHSWidth) {
1385  newRHS = RHSOp0;
1386  }
1387  // case 4
1388  if (LHSOp0 == RHSOp0) {
1389  newLHS = LHSOp0;
1390  newRHS = nullptr;
1391  }
1392 
1393  if (newLHS == LHS && newRHS == RHS)
1394  return MadeChange ? &SVI : nullptr;
1395 
1396  SmallVector<int, 16> LHSMask;
1397  SmallVector<int, 16> RHSMask;
1398  if (newLHS != LHS)
1399  LHSMask = LHSShuffle->getShuffleMask();
1400  if (RHSShuffle && newRHS != RHS)
1401  RHSMask = RHSShuffle->getShuffleMask();
1402 
1403  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1404  SmallVector<int, 16> newMask;
1405  bool isSplat = true;
1406  int SplatElt = -1;
1407  // Create a new mask for the new ShuffleVectorInst so that the new
1408  // ShuffleVectorInst is equivalent to the original one.
1409  for (unsigned i = 0; i < VWidth; ++i) {
1410  int eltMask;
1411  if (Mask[i] < 0) {
1412  // This element is an undef value.
1413  eltMask = -1;
1414  } else if (Mask[i] < (int)LHSWidth) {
1415  // This element is from left hand side vector operand.
1416  //
1417  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1418  // new mask value for the element.
1419  if (newLHS != LHS) {
1420  eltMask = LHSMask[Mask[i]];
1421  // If the value selected is an undef value, explicitly specify it
1422  // with a -1 mask value.
1423  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1424  eltMask = -1;
1425  } else
1426  eltMask = Mask[i];
1427  } else {
1428  // This element is from right hand side vector operand
1429  //
1430  // If the value selected is an undef value, explicitly specify it
1431  // with a -1 mask value. (case 1)
1432  if (isa<UndefValue>(RHS))
1433  eltMask = -1;
1434  // If RHS is going to be replaced (case 3 or 4), calculate the
1435  // new mask value for the element.
1436  else if (newRHS != RHS) {
1437  eltMask = RHSMask[Mask[i]-LHSWidth];
1438  // If the value selected is an undef value, explicitly specify it
1439  // with a -1 mask value.
1440  if (eltMask >= (int)RHSOp0Width) {
1441  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1442  && "should have been check above");
1443  eltMask = -1;
1444  }
1445  } else
1446  eltMask = Mask[i]-LHSWidth;
1447 
1448  // If LHS's width is changed, shift the mask value accordingly.
1449  // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any
1450  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1451  // If newRHS == newLHS, we want to remap any references from newRHS to
1452  // newLHS so that we can properly identify splats that may occur due to
1453  // obfuscation across the two vectors.
1454  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1455  eltMask += newLHSWidth;
1456  }
1457 
1458  // Check if this could still be a splat.
1459  if (eltMask >= 0) {
1460  if (SplatElt >= 0 && SplatElt != eltMask)
1461  isSplat = false;
1462  SplatElt = eltMask;
1463  }
1464 
1465  newMask.push_back(eltMask);
1466  }
1467 
1468  // If the result mask is equal to one of the original shuffle masks,
1469  // or is a splat, do the replacement.
1470  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1472  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1473  if (newMask[i] < 0) {
1474  Elts.push_back(UndefValue::get(Int32Ty));
1475  } else {
1476  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1477  }
1478  }
1479  if (!newRHS)
1480  newRHS = UndefValue::get(newLHS->getType());
1481  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1482  }
1483 
1484  // If the result mask is an identity, replace uses of this instruction with
1485  // corresponding argument.
1486  bool isLHSID, isRHSID;
1487  recognizeIdentityMask(newMask, isLHSID, isRHSID);
1488  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1489  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1490 
1491  return MadeChange ? &SVI : nullptr;
1492 }
static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf)
Instruction * visitInsertValueInst(InsertValueInst &IV)
Try to find redundant insertvalue instructions, like the following ones: %0 = insertvalue { i8...
uint64_t CallInst * C
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:850
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isConstant(const MachineInstr &MI)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:555
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:234
Value * findScalarElement(Value *V, unsigned EltNo)
Given a vector and an element number, see if the scalar value is already around as a register...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:523
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
static Instruction * foldConstantInsEltIntoShuffle(InsertElementInst &InsElt)
insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex –> shufflevector X...
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1237
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:863
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
std::pair< Value *, Value * > ShuffleOps
We are building a shuffle to create V, which is a sequence of insertelement, extractelement pairs...
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:697
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:227
static Instruction * hoistInsEltConst(InsertElementInst &InsElt2, InstCombiner::BuilderTy &Builder)
If we have an insertelement instruction feeding into another insertelement and the 2nd is inserting a...
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
Constant * getMask() const
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
unsigned getBitWidth() const
Return the number of bits in the Vector type.
Definition: DerivedTypes.h:452
void setBit(unsigned BitPosition)
Set a given bit to 1.
Definition: APInt.h:1382
This class represents the LLVM &#39;select&#39; instruction.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
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:42
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
The core instruction combiner logic.
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 ...
uint64_t getNumElements() const
Definition: DerivedTypes.h:359
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:427
static Instruction * foldInsSequenceIntoBroadcast(InsertElementInst &InsElt)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
Definition: Type.cpp:608
This instruction compares its operands according to the predicate given to the constructor.
This class represents a no-op cast from one type to another.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:121
Instruction * visitExtractElementInst(ExtractElementInst &EI)
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...
VectorType * getType() const
Overload to return most specific vector type.
Value * getOperand(unsigned i) const
Definition: User.h:154
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:277
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return &#39;this&#39;.
Definition: Type.h:301
Instruction * visitInsertElementInst(InsertElementInst &IE)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
This instruction inserts a single (scalar) element into a VectorType value.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:149
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:200
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
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:149
This is an important base class in LLVM.
Definition: Constant.h:42
static Constant * getShuffleVector(Constant *V1, Constant *V2, Constant *Mask, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2025
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:825
This instruction compares its operands according to the predicate given to the constructor.
op_range operands()
Definition: User.h:222
self_iterator getIterator()
Definition: ilist_node.h:82
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...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1320
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isExact() const
Determine whether the exact flag is set.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q)
Given operands for a ShuffleVectorInst, fold the result or return null.
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:251
#define E
Definition: LargeTest.cpp:27
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
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
Value * CreateInsertElement(Value *Vec, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:1722
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:560
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:159
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
Class to represent vector types.
Definition: DerivedTypes.h:393
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:395
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:179
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 int getMaskValue(Constant *Mask, unsigned Elt)
Return the shuffle mask value for the specified element of the mask.
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, BinaryOperator *CopyBO, const Twine &Name="")
Definition: InstrTypes.h:385
static bool cheapToScalarize(Value *V, bool isConstant)
Return true if the value is cheaper to scalarize than it is to leave as a vector operation.
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
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:108
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:81
#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:323
This instruction extracts a single (scalar) element from a VectorType value.
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.
ArrayRef< unsigned > getIndices() const
LLVM Value Representation.
Definition: Value.h:73
This file provides internal interfaces used to implement the InstCombine.
static VectorType * get(Type *ElementType, unsigned NumElements)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:593
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:81
Type * getElementType() const
Definition: DerivedTypes.h:360
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:408
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)
int * Ptr
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
static void getShuffleMask(Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
VectorType * getType() const
Overload to return most specific vector type.
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:984
IntegerType * Int32Ty
User * user_back()
Definition: Value.h:381
const BasicBlock * getParent() const
Definition: Instruction.h:66
This instruction inserts a struct field of array element value into an aggregate value.