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  }
259  }
260  return nullptr;
261 }
262 
263 /// If V is a shuffle of values that ONLY returns elements from either LHS or
264 /// RHS, return the shuffle mask and true. Otherwise, return false.
265 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
267  assert(LHS->getType() == RHS->getType() &&
268  "Invalid CollectSingleShuffleElements");
269  unsigned NumElts = V->getType()->getVectorNumElements();
270 
271  if (isa<UndefValue>(V)) {
272  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
273  return true;
274  }
275 
276  if (V == LHS) {
277  for (unsigned i = 0; i != NumElts; ++i)
279  return true;
280  }
281 
282  if (V == RHS) {
283  for (unsigned i = 0; i != NumElts; ++i)
285  i+NumElts));
286  return true;
287  }
288 
289  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
290  // If this is an insert of an extract from some other vector, include it.
291  Value *VecOp = IEI->getOperand(0);
292  Value *ScalarOp = IEI->getOperand(1);
293  Value *IdxOp = IEI->getOperand(2);
294 
295  if (!isa<ConstantInt>(IdxOp))
296  return false;
297  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
298 
299  if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
300  // We can handle this if the vector we are inserting into is
301  // transitively ok.
302  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
303  // If so, update the mask to reflect the inserted undef.
304  Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
305  return true;
306  }
307  } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
308  if (isa<ConstantInt>(EI->getOperand(1))) {
309  unsigned ExtractedIdx =
310  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
311  unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
312 
313  // This must be extracting from either LHS or RHS.
314  if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
315  // We can handle this if the vector we are inserting into is
316  // transitively ok.
317  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
318  // If so, update the mask to reflect the inserted value.
319  if (EI->getOperand(0) == LHS) {
320  Mask[InsertedIdx % NumElts] =
322  ExtractedIdx);
323  } else {
324  assert(EI->getOperand(0) == RHS);
325  Mask[InsertedIdx % NumElts] =
327  ExtractedIdx + NumLHSElts);
328  }
329  return true;
330  }
331  }
332  }
333  }
334  }
335 
336  return false;
337 }
338 
339 /// If we have insertion into a vector that is wider than the vector that we
340 /// are extracting from, try to widen the source vector to allow a single
341 /// shufflevector to replace one or more insert/extract pairs.
343  ExtractElementInst *ExtElt,
344  InstCombiner &IC) {
345  VectorType *InsVecType = InsElt->getType();
346  VectorType *ExtVecType = ExtElt->getVectorOperandType();
347  unsigned NumInsElts = InsVecType->getVectorNumElements();
348  unsigned NumExtElts = ExtVecType->getVectorNumElements();
349 
350  // The inserted-to vector must be wider than the extracted-from vector.
351  if (InsVecType->getElementType() != ExtVecType->getElementType() ||
352  NumExtElts >= NumInsElts)
353  return;
354 
355  // Create a shuffle mask to widen the extended-from vector using undefined
356  // values. The mask selects all of the values of the original vector followed
357  // by as many undefined values as needed to create a vector of the same length
358  // as the inserted-to vector.
359  SmallVector<Constant *, 16> ExtendMask;
360  IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
361  for (unsigned i = 0; i < NumExtElts; ++i)
362  ExtendMask.push_back(ConstantInt::get(IntType, i));
363  for (unsigned i = NumExtElts; i < NumInsElts; ++i)
364  ExtendMask.push_back(UndefValue::get(IntType));
365 
366  Value *ExtVecOp = ExtElt->getVectorOperand();
367  auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
368  BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
369  ? ExtVecOpInst->getParent()
370  : ExtElt->getParent();
371 
372  // TODO: This restriction matches the basic block check below when creating
373  // new extractelement instructions. If that limitation is removed, this one
374  // could also be removed. But for now, we just bail out to ensure that we
375  // will replace the extractelement instruction that is feeding our
376  // insertelement instruction. This allows the insertelement to then be
377  // replaced by a shufflevector. If the insertelement is not replaced, we can
378  // induce infinite looping because there's an optimization for extractelement
379  // that will delete our widening shuffle. This would trigger another attempt
380  // here to create that shuffle, and we spin forever.
381  if (InsertionBlock != InsElt->getParent())
382  return;
383 
384  // TODO: This restriction matches the check in visitInsertElementInst() and
385  // prevents an infinite loop caused by not turning the extract/insert pair
386  // into a shuffle. We really should not need either check, but we're lacking
387  // folds for shufflevectors because we're afraid to generate shuffle masks
388  // that the backend can't handle.
389  if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
390  return;
391 
392  auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
393  ConstantVector::get(ExtendMask));
394 
395  // Insert the new shuffle after the vector operand of the extract is defined
396  // (as long as it's not a PHI) or at the start of the basic block of the
397  // extract, so any subsequent extracts in the same basic block can use it.
398  // TODO: Insert before the earliest ExtractElementInst that is replaced.
399  if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
400  WideVec->insertAfter(ExtVecOpInst);
401  else
402  IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
403 
404  // Replace extracts from the original narrow vector with extracts from the new
405  // wide vector.
406  for (User *U : ExtVecOp->users()) {
408  if (!OldExt || OldExt->getParent() != WideVec->getParent())
409  continue;
410  auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
411  NewExt->insertAfter(OldExt);
412  IC.replaceInstUsesWith(*OldExt, NewExt);
413  }
414 }
415 
416 /// We are building a shuffle to create V, which is a sequence of insertelement,
417 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
418 /// not rely on the second vector source. Return a std::pair containing the
419 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
420 /// parameter as required.
421 ///
422 /// Note: we intentionally don't try to fold earlier shuffles since they have
423 /// often been chosen carefully to be efficiently implementable on the target.
424 typedef std::pair<Value *, Value *> ShuffleOps;
425 
428  Value *PermittedRHS,
429  InstCombiner &IC) {
430  assert(V->getType()->isVectorTy() && "Invalid shuffle!");
431  unsigned NumElts = V->getType()->getVectorNumElements();
432 
433  if (isa<UndefValue>(V)) {
434  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
435  return std::make_pair(
436  PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
437  }
438 
439  if (isa<ConstantAggregateZero>(V)) {
440  Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
441  return std::make_pair(V, nullptr);
442  }
443 
444  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
445  // If this is an insert of an extract from some other vector, include it.
446  Value *VecOp = IEI->getOperand(0);
447  Value *ScalarOp = IEI->getOperand(1);
448  Value *IdxOp = IEI->getOperand(2);
449 
450  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
451  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
452  unsigned ExtractedIdx =
453  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
454  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
455 
456  // Either the extracted from or inserted into vector must be RHSVec,
457  // otherwise we'd end up with a shuffle of three inputs.
458  if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
459  Value *RHS = EI->getOperand(0);
460  ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
461  assert(LR.second == nullptr || LR.second == RHS);
462 
463  if (LR.first->getType() != RHS->getType()) {
464  // Although we are giving up for now, see if we can create extracts
465  // that match the inserts for another round of combining.
466  replaceExtractElements(IEI, EI, IC);
467 
468  // We tried our best, but we can't find anything compatible with RHS
469  // further up the chain. Return a trivial shuffle.
470  for (unsigned i = 0; i < NumElts; ++i)
471  Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
472  return std::make_pair(V, nullptr);
473  }
474 
475  unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
476  Mask[InsertedIdx % NumElts] =
478  NumLHSElts+ExtractedIdx);
479  return std::make_pair(LR.first, RHS);
480  }
481 
482  if (VecOp == PermittedRHS) {
483  // We've gone as far as we can: anything on the other side of the
484  // extractelement will already have been converted into a shuffle.
485  unsigned NumLHSElts =
487  for (unsigned i = 0; i != NumElts; ++i)
490  i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
491  return std::make_pair(EI->getOperand(0), PermittedRHS);
492  }
493 
494  // If this insertelement is a chain that comes from exactly these two
495  // vectors, return the vector and the effective shuffle.
496  if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
497  collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
498  Mask))
499  return std::make_pair(EI->getOperand(0), PermittedRHS);
500  }
501  }
502  }
503 
504  // Otherwise, we can't do anything fancy. Return an identity vector.
505  for (unsigned i = 0; i != NumElts; ++i)
507  return std::make_pair(V, nullptr);
508 }
509 
510 /// Try to find redundant insertvalue instructions, like the following ones:
511 /// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
512 /// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
513 /// Here the second instruction inserts values at the same indices, as the
514 /// first one, making the first one redundant.
515 /// It should be transformed to:
516 /// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
518  bool IsRedundant = false;
519  ArrayRef<unsigned int> FirstIndices = I.getIndices();
520 
521  // If there is a chain of insertvalue instructions (each of them except the
522  // last one has only one use and it's another insertvalue insn from this
523  // chain), check if any of the 'children' uses the same indices as the first
524  // instruction. In this case, the first one is redundant.
525  Value *V = &I;
526  unsigned Depth = 0;
527  while (V->hasOneUse() && Depth < 10) {
528  User *U = V->user_back();
529  auto UserInsInst = dyn_cast<InsertValueInst>(U);
530  if (!UserInsInst || U->getOperand(0) != V)
531  break;
532  if (UserInsInst->getIndices() == FirstIndices) {
533  IsRedundant = true;
534  break;
535  }
536  V = UserInsInst;
537  Depth++;
538  }
539 
540  if (IsRedundant)
541  return replaceInstUsesWith(I, I.getOperand(0));
542  return nullptr;
543 }
544 
546  int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
547  int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
548 
549  // A vector select does not change the size of the operands.
550  if (MaskSize != VecSize)
551  return false;
552 
553  // Each mask element must be undefined or choose a vector element from one of
554  // the source operands without crossing vector lanes.
555  for (int i = 0; i != MaskSize; ++i) {
556  int Elt = Shuf.getMaskValue(i);
557  if (Elt != -1 && Elt != i && Elt != i + VecSize)
558  return false;
559  }
560 
561  return true;
562 }
563 
564 // Turn a chain of inserts that splats a value into a canonical insert + shuffle
565 // splat. That is:
566 // insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
567 // shufflevector(insertelt(X, %k, 0), undef, zero)
569  // We are interested in the last insert in a chain. So, if this insert
570  // has a single user, and that user is an insert, bail.
571  if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
572  return nullptr;
573 
574  VectorType *VT = cast<VectorType>(InsElt.getType());
575  int NumElements = VT->getNumElements();
576 
577  // Do not try to do this for a one-element vector, since that's a nop,
578  // and will cause an inf-loop.
579  if (NumElements == 1)
580  return nullptr;
581 
582  Value *SplatVal = InsElt.getOperand(1);
583  InsertElementInst *CurrIE = &InsElt;
584  SmallVector<bool, 16> ElementPresent(NumElements, false);
585  InsertElementInst *FirstIE = nullptr;
586 
587  // Walk the chain backwards, keeping track of which indices we inserted into,
588  // until we hit something that isn't an insert of the splatted value.
589  while (CurrIE) {
590  ConstantInt *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
591  if (!Idx || CurrIE->getOperand(1) != SplatVal)
592  return nullptr;
593 
594  InsertElementInst *NextIE =
596  // Check none of the intermediate steps have any additional uses, except
597  // for the root insertelement instruction, which can be re-used, if it
598  // inserts at position 0.
599  if (CurrIE != &InsElt &&
600  (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
601  return nullptr;
602 
603  ElementPresent[Idx->getZExtValue()] = true;
604  FirstIE = CurrIE;
605  CurrIE = NextIE;
606  }
607 
608  // Make sure we've seen an insert into every element.
609  if (llvm::any_of(ElementPresent, [](bool Present) { return !Present; }))
610  return nullptr;
611 
612  // All right, create the insert + shuffle.
613  Instruction *InsertFirst;
614  if (cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
615  InsertFirst = FirstIE;
616  else
617  InsertFirst = InsertElementInst::Create(
618  UndefValue::get(VT), SplatVal,
620  "", &InsElt);
621 
623  VectorType::get(Type::getInt32Ty(InsElt.getContext()), NumElements));
624 
625  return new ShuffleVectorInst(InsertFirst, UndefValue::get(VT), ZeroMask);
626 }
627 
628 /// If we have an insertelement instruction feeding into another insertelement
629 /// and the 2nd is inserting a constant into the vector, canonicalize that
630 /// constant insertion before the insertion of a variable:
631 ///
632 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
633 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
634 ///
635 /// This has the potential of eliminating the 2nd insertelement instruction
636 /// via constant folding of the scalar constant into a vector constant.
638  InstCombiner::BuilderTy &Builder) {
639  auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
640  if (!InsElt1 || !InsElt1->hasOneUse())
641  return nullptr;
642 
643  Value *X, *Y;
644  Constant *ScalarC;
645  ConstantInt *IdxC1, *IdxC2;
646  if (match(InsElt1->getOperand(0), m_Value(X)) &&
647  match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
648  match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
649  match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
650  match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
651  Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
652  return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
653  }
654 
655  return nullptr;
656 }
657 
658 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
659 /// --> shufflevector X, CVec', Mask'
661  auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
662  // Bail out if the parent has more than one use. In that case, we'd be
663  // replacing the insertelt with a shuffle, and that's not a clear win.
664  if (!Inst || !Inst->hasOneUse())
665  return nullptr;
666  if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
667  // The shuffle must have a constant vector operand. The insertelt must have
668  // a constant scalar being inserted at a constant position in the vector.
669  Constant *ShufConstVec, *InsEltScalar;
670  uint64_t InsEltIndex;
671  if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
672  !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
673  !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
674  return nullptr;
675 
676  // Adding an element to an arbitrary shuffle could be expensive, but a
677  // shuffle that selects elements from vectors without crossing lanes is
678  // assumed cheap.
679  // If we're just adding a constant into that shuffle, it will still be
680  // cheap.
681  if (!isShuffleEquivalentToSelect(*Shuf))
682  return nullptr;
683 
684  // From the above 'select' check, we know that the mask has the same number
685  // of elements as the vector input operands. We also know that each constant
686  // input element is used in its lane and can not be used more than once by
687  // the shuffle. Therefore, replace the constant in the shuffle's constant
688  // vector with the insertelt constant. Replace the constant in the shuffle's
689  // mask vector with the insertelt index plus the length of the vector
690  // (because the constant vector operand of a shuffle is always the 2nd
691  // operand).
692  Constant *Mask = Shuf->getMask();
693  unsigned NumElts = Mask->getType()->getVectorNumElements();
694  SmallVector<Constant *, 16> NewShufElts(NumElts);
695  SmallVector<Constant *, 16> NewMaskElts(NumElts);
696  for (unsigned I = 0; I != NumElts; ++I) {
697  if (I == InsEltIndex) {
698  NewShufElts[I] = InsEltScalar;
699  Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
700  NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
701  } else {
702  // Copy over the existing values.
703  NewShufElts[I] = ShufConstVec->getAggregateElement(I);
704  NewMaskElts[I] = Mask->getAggregateElement(I);
705  }
706  }
707 
708  // Create new operands for a shuffle that includes the constant of the
709  // original insertelt. The old shuffle will be dead now.
710  return new ShuffleVectorInst(Shuf->getOperand(0),
711  ConstantVector::get(NewShufElts),
712  ConstantVector::get(NewMaskElts));
713  } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
714  // Transform sequences of insertelements ops with constant data/indexes into
715  // a single shuffle op.
716  unsigned NumElts = InsElt.getType()->getNumElements();
717 
718  uint64_t InsertIdx[2];
719  Constant *Val[2];
720  if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
721  !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
722  !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
723  !match(IEI->getOperand(1), m_Constant(Val[1])))
724  return nullptr;
725  SmallVector<Constant *, 16> Values(NumElts);
727  auto ValI = std::begin(Val);
728  // Generate new constant vector and mask.
729  // We have 2 values/masks from the insertelements instructions. Insert them
730  // into new value/mask vectors.
731  for (uint64_t I : InsertIdx) {
732  if (!Values[I]) {
733  assert(!Mask[I]);
734  Values[I] = *ValI;
735  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
736  NumElts + I);
737  }
738  ++ValI;
739  }
740  // Remaining values are filled with 'undef' values.
741  for (unsigned I = 0; I < NumElts; ++I) {
742  if (!Values[I]) {
743  assert(!Mask[I]);
744  Values[I] = UndefValue::get(InsElt.getType()->getElementType());
745  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
746  }
747  }
748  // Create new operands for a shuffle that includes the constant of the
749  // original insertelt.
750  return new ShuffleVectorInst(IEI->getOperand(0),
751  ConstantVector::get(Values),
752  ConstantVector::get(Mask));
753  }
754  return nullptr;
755 }
756 
758  Value *VecOp = IE.getOperand(0);
759  Value *ScalarOp = IE.getOperand(1);
760  Value *IdxOp = IE.getOperand(2);
761 
762  // Inserting an undef or into an undefined place, remove this.
763  if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
764  replaceInstUsesWith(IE, VecOp);
765 
766  // If the inserted element was extracted from some other vector, and if the
767  // indexes are constant, try to turn this into a shufflevector operation.
768  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
769  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
770  unsigned NumInsertVectorElts = IE.getType()->getNumElements();
771  unsigned NumExtractVectorElts =
773  unsigned ExtractedIdx =
774  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
775  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
776 
777  if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
778  return replaceInstUsesWith(IE, VecOp);
779 
780  if (InsertedIdx >= NumInsertVectorElts) // Out of range insert.
781  return replaceInstUsesWith(IE, UndefValue::get(IE.getType()));
782 
783  // If we are extracting a value from a vector, then inserting it right
784  // back into the same place, just use the input vector.
785  if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
786  return replaceInstUsesWith(IE, VecOp);
787 
788  // If this insertelement isn't used by some other insertelement, turn it
789  // (and any insertelements it points to), into one big shuffle.
790  if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) {
792  ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
793 
794  // The proposed shuffle may be trivial, in which case we shouldn't
795  // perform the combine.
796  if (LR.first != &IE && LR.second != &IE) {
797  // We now have a shuffle of LHS, RHS, Mask.
798  if (LR.second == nullptr)
799  LR.second = UndefValue::get(LR.first->getType());
800  return new ShuffleVectorInst(LR.first, LR.second,
801  ConstantVector::get(Mask));
802  }
803  }
804  }
805  }
806 
807  unsigned VWidth = VecOp->getType()->getVectorNumElements();
808  APInt UndefElts(VWidth, 0);
809  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
810  if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
811  if (V != &IE)
812  return replaceInstUsesWith(IE, V);
813  return &IE;
814  }
815 
817  return Shuf;
818 
819  if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
820  return NewInsElt;
821 
822  // Turn a sequence of inserts that broadcasts a scalar into a single
823  // insert + shufflevector.
824  if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE))
825  return Broadcast;
826 
827  return nullptr;
828 }
829 
830 /// Return true if we can evaluate the specified expression tree if the vector
831 /// elements were shuffled in a different order.
833  unsigned Depth = 5) {
834  // We can always reorder the elements of a constant.
835  if (isa<Constant>(V))
836  return true;
837 
838  // We won't reorder vector arguments. No IPO here.
840  if (!I) return false;
841 
842  // Two users may expect different orders of the elements. Don't try it.
843  if (!I->hasOneUse())
844  return false;
845 
846  if (Depth == 0) return false;
847 
848  switch (I->getOpcode()) {
849  case Instruction::Add:
850  case Instruction::FAdd:
851  case Instruction::Sub:
852  case Instruction::FSub:
853  case Instruction::Mul:
854  case Instruction::FMul:
855  case Instruction::UDiv:
856  case Instruction::SDiv:
857  case Instruction::FDiv:
858  case Instruction::URem:
859  case Instruction::SRem:
860  case Instruction::FRem:
861  case Instruction::Shl:
862  case Instruction::LShr:
863  case Instruction::AShr:
864  case Instruction::And:
865  case Instruction::Or:
866  case Instruction::Xor:
867  case Instruction::ICmp:
868  case Instruction::FCmp:
869  case Instruction::Trunc:
870  case Instruction::ZExt:
871  case Instruction::SExt:
872  case Instruction::FPToUI:
873  case Instruction::FPToSI:
874  case Instruction::UIToFP:
875  case Instruction::SIToFP:
876  case Instruction::FPTrunc:
877  case Instruction::FPExt:
878  case Instruction::GetElementPtr: {
879  for (Value *Operand : I->operands()) {
880  if (!CanEvaluateShuffled(Operand, Mask, Depth-1))
881  return false;
882  }
883  return true;
884  }
885  case Instruction::InsertElement: {
887  if (!CI) return false;
888  int ElementNumber = CI->getLimitedValue();
889 
890  // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
891  // can't put an element into multiple indices.
892  bool SeenOnce = false;
893  for (int i = 0, e = Mask.size(); i != e; ++i) {
894  if (Mask[i] == ElementNumber) {
895  if (SeenOnce)
896  return false;
897  SeenOnce = true;
898  }
899  }
900  return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1);
901  }
902  }
903  return false;
904 }
905 
906 /// Rebuild a new instruction just like 'I' but with the new operands given.
907 /// In the event of type mismatch, the type of the operands is correct.
909  // We don't want to use the IRBuilder here because we want the replacement
910  // instructions to appear next to 'I', not the builder's insertion point.
911  switch (I->getOpcode()) {
912  case Instruction::Add:
913  case Instruction::FAdd:
914  case Instruction::Sub:
915  case Instruction::FSub:
916  case Instruction::Mul:
917  case Instruction::FMul:
918  case Instruction::UDiv:
919  case Instruction::SDiv:
920  case Instruction::FDiv:
921  case Instruction::URem:
922  case Instruction::SRem:
923  case Instruction::FRem:
924  case Instruction::Shl:
925  case Instruction::LShr:
926  case Instruction::AShr:
927  case Instruction::And:
928  case Instruction::Or:
929  case Instruction::Xor: {
930  BinaryOperator *BO = cast<BinaryOperator>(I);
931  assert(NewOps.size() == 2 && "binary operator with #ops != 2");
932  BinaryOperator *New =
933  BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
934  NewOps[0], NewOps[1], "", BO);
935  if (isa<OverflowingBinaryOperator>(BO)) {
936  New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
937  New->setHasNoSignedWrap(BO->hasNoSignedWrap());
938  }
939  if (isa<PossiblyExactOperator>(BO)) {
940  New->setIsExact(BO->isExact());
941  }
942  if (isa<FPMathOperator>(BO))
943  New->copyFastMathFlags(I);
944  return New;
945  }
946  case Instruction::ICmp:
947  assert(NewOps.size() == 2 && "icmp with #ops != 2");
948  return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
949  NewOps[0], NewOps[1]);
950  case Instruction::FCmp:
951  assert(NewOps.size() == 2 && "fcmp with #ops != 2");
952  return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
953  NewOps[0], NewOps[1]);
954  case Instruction::Trunc:
955  case Instruction::ZExt:
956  case Instruction::SExt:
957  case Instruction::FPToUI:
958  case Instruction::FPToSI:
959  case Instruction::UIToFP:
960  case Instruction::SIToFP:
961  case Instruction::FPTrunc:
962  case Instruction::FPExt: {
963  // It's possible that the mask has a different number of elements from
964  // the original cast. We recompute the destination type to match the mask.
965  Type *DestTy =
967  NewOps[0]->getType()->getVectorNumElements());
968  assert(NewOps.size() == 1 && "cast with #ops != 1");
969  return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
970  "", I);
971  }
972  case Instruction::GetElementPtr: {
973  Value *Ptr = NewOps[0];
974  ArrayRef<Value*> Idx = NewOps.slice(1);
976  cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
977  GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
978  return GEP;
979  }
980  }
981  llvm_unreachable("failed to rebuild vector instructions");
982 }
983 
984 Value *
985 InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
986  // Mask.size() does not need to be equal to the number of vector elements.
987 
988  assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
989  if (isa<UndefValue>(V)) {
991  Mask.size()));
992  }
993  if (isa<ConstantAggregateZero>(V)) {
996  Mask.size()));
997  }
998  if (Constant *C = dyn_cast<Constant>(V)) {
999  SmallVector<Constant *, 16> MaskValues;
1000  for (int i = 0, e = Mask.size(); i != e; ++i) {
1001  if (Mask[i] == -1)
1002  MaskValues.push_back(UndefValue::get(Builder.getInt32Ty()));
1003  else
1004  MaskValues.push_back(Builder.getInt32(Mask[i]));
1005  }
1007  ConstantVector::get(MaskValues));
1008  }
1009 
1010  Instruction *I = cast<Instruction>(V);
1011  switch (I->getOpcode()) {
1012  case Instruction::Add:
1013  case Instruction::FAdd:
1014  case Instruction::Sub:
1015  case Instruction::FSub:
1016  case Instruction::Mul:
1017  case Instruction::FMul:
1018  case Instruction::UDiv:
1019  case Instruction::SDiv:
1020  case Instruction::FDiv:
1021  case Instruction::URem:
1022  case Instruction::SRem:
1023  case Instruction::FRem:
1024  case Instruction::Shl:
1025  case Instruction::LShr:
1026  case Instruction::AShr:
1027  case Instruction::And:
1028  case Instruction::Or:
1029  case Instruction::Xor:
1030  case Instruction::ICmp:
1031  case Instruction::FCmp:
1032  case Instruction::Trunc:
1033  case Instruction::ZExt:
1034  case Instruction::SExt:
1035  case Instruction::FPToUI:
1036  case Instruction::FPToSI:
1037  case Instruction::UIToFP:
1038  case Instruction::SIToFP:
1039  case Instruction::FPTrunc:
1040  case Instruction::FPExt:
1041  case Instruction::Select:
1042  case Instruction::GetElementPtr: {
1043  SmallVector<Value*, 8> NewOps;
1044  bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1045  for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1046  Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask);
1047  NewOps.push_back(V);
1048  NeedsRebuild |= (V != I->getOperand(i));
1049  }
1050  if (NeedsRebuild) {
1051  return buildNew(I, NewOps);
1052  }
1053  return I;
1054  }
1055  case Instruction::InsertElement: {
1056  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1057 
1058  // The insertelement was inserting at Element. Figure out which element
1059  // that becomes after shuffling. The answer is guaranteed to be unique
1060  // by CanEvaluateShuffled.
1061  bool Found = false;
1062  int Index = 0;
1063  for (int e = Mask.size(); Index != e; ++Index) {
1064  if (Mask[Index] == Element) {
1065  Found = true;
1066  break;
1067  }
1068  }
1069 
1070  // If element is not in Mask, no need to handle the operand 1 (element to
1071  // be inserted). Just evaluate values in operand 0 according to Mask.
1072  if (!Found)
1073  return EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1074 
1075  Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1076  return InsertElementInst::Create(V, I->getOperand(1),
1077  Builder.getInt32(Index), "", I);
1078  }
1079  }
1080  llvm_unreachable("failed to reorder elements of vector instruction!");
1081 }
1082 
1084  bool &isLHSID, bool &isRHSID) {
1085  isLHSID = isRHSID = true;
1086 
1087  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1088  if (Mask[i] < 0) continue; // Ignore undef values.
1089  // Is this an identity shuffle of the LHS value?
1090  isLHSID &= (Mask[i] == (int)i);
1091 
1092  // Is this an identity shuffle of the RHS value?
1093  isRHSID &= (Mask[i]-e == i);
1094  }
1095 }
1096 
1097 // Returns true if the shuffle is extracting a contiguous range of values from
1098 // LHS, for example:
1099 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1100 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1101 // Shuffles to: |EE|FF|GG|HH|
1102 // +--+--+--+--+
1104  SmallVector<int, 16> &Mask) {
1105  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1106  unsigned MaskElems = Mask.size();
1107  unsigned BegIdx = Mask.front();
1108  unsigned EndIdx = Mask.back();
1109  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1110  return false;
1111  for (unsigned I = 0; I != MaskElems; ++I)
1112  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1113  return false;
1114  return true;
1115 }
1116 
1118  Value *LHS = SVI.getOperand(0);
1119  Value *RHS = SVI.getOperand(1);
1120  SmallVector<int, 16> Mask = SVI.getShuffleMask();
1122 
1123  if (auto *V = SimplifyShuffleVectorInst(
1124  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1125  return replaceInstUsesWith(SVI, V);
1126 
1127  bool MadeChange = false;
1128  unsigned VWidth = SVI.getType()->getVectorNumElements();
1129 
1130  APInt UndefElts(VWidth, 0);
1131  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1132  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1133  if (V != &SVI)
1134  return replaceInstUsesWith(SVI, V);
1135  return &SVI;
1136  }
1137 
1138  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1139 
1140  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1141  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1142  if (LHS == RHS || isa<UndefValue>(LHS)) {
1143  if (isa<UndefValue>(LHS) && LHS == RHS) {
1144  // shuffle(undef,undef,mask) -> undef.
1145  Value *Result = (VWidth == LHSWidth)
1146  ? LHS : UndefValue::get(SVI.getType());
1147  return replaceInstUsesWith(SVI, Result);
1148  }
1149 
1150  // Remap any references to RHS to use LHS.
1152  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1153  if (Mask[i] < 0) {
1154  Elts.push_back(UndefValue::get(Int32Ty));
1155  continue;
1156  }
1157 
1158  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1159  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1160  Mask[i] = -1; // Turn into undef.
1161  Elts.push_back(UndefValue::get(Int32Ty));
1162  } else {
1163  Mask[i] = Mask[i] % e; // Force to LHS.
1164  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1165  }
1166  }
1167  SVI.setOperand(0, SVI.getOperand(1));
1168  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1169  SVI.setOperand(2, ConstantVector::get(Elts));
1170  LHS = SVI.getOperand(0);
1171  RHS = SVI.getOperand(1);
1172  MadeChange = true;
1173  }
1174 
1175  if (VWidth == LHSWidth) {
1176  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1177  bool isLHSID, isRHSID;
1178  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1179 
1180  // Eliminate identity shuffles.
1181  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1182  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1183  }
1184 
1185  if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
1186  Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
1187  return replaceInstUsesWith(SVI, V);
1188  }
1189 
1190  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1191  // a non-vector type. We can instead bitcast the original vector followed by
1192  // an extract of the desired element:
1193  //
1194  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1195  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1196  // %1 = bitcast <4 x i8> %sroa to i32
1197  // Becomes:
1198  // %bc = bitcast <16 x i8> %in to <4 x i32>
1199  // %ext = extractelement <4 x i32> %bc, i32 0
1200  //
1201  // If the shuffle is extracting a contiguous range of values from the input
1202  // vector then each use which is a bitcast of the extracted size can be
1203  // replaced. This will work if the vector types are compatible, and the begin
1204  // index is aligned to a value in the casted vector type. If the begin index
1205  // isn't aligned then we can shuffle the original vector (keeping the same
1206  // vector type) before extracting.
1207  //
1208  // This code will bail out if the target type is fundamentally incompatible
1209  // with vectors of the source type.
1210  //
1211  // Example of <16 x i8>, target type i32:
1212  // Index range [4,8): v-----------v Will work.
1213  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1214  // <16 x i8>: | | | | | | | | | | | | | | | | |
1215  // <4 x i32>: | | | | |
1216  // +-----------+-----------+-----------+-----------+
1217  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1218  // Target type i40: ^--------------^ Won't work, bail.
1219  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1220  Value *V = LHS;
1221  unsigned MaskElems = Mask.size();
1222  VectorType *SrcTy = cast<VectorType>(V->getType());
1223  unsigned VecBitWidth = SrcTy->getBitWidth();
1224  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1225  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1226  unsigned SrcNumElems = SrcTy->getNumElements();
1229  for (User *U : SVI.users())
1230  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1231  if (!BC->use_empty())
1232  // Only visit bitcasts that weren't previously handled.
1233  BCs.push_back(BC);
1234  for (BitCastInst *BC : BCs) {
1235  unsigned BegIdx = Mask.front();
1236  Type *TgtTy = BC->getDestTy();
1237  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1238  if (!TgtElemBitWidth)
1239  continue;
1240  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1241  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1242  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1243  if (!VecBitWidthsEqual)
1244  continue;
1245  if (!VectorType::isValidElementType(TgtTy))
1246  continue;
1247  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1248  if (!BegIsAligned) {
1249  // Shuffle the input so [0,NumElements) contains the output, and
1250  // [NumElems,SrcNumElems) is undef.
1251  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1252  UndefValue::get(Int32Ty));
1253  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1254  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1255  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1256  ConstantVector::get(ShuffleMask),
1257  SVI.getName() + ".extract");
1258  BegIdx = 0;
1259  }
1260  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1261  assert(SrcElemsPerTgtElem);
1262  BegIdx /= SrcElemsPerTgtElem;
1263  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1264  auto *NewBC =
1265  BCAlreadyExists
1266  ? NewBCs[CastSrcTy]
1267  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1268  if (!BCAlreadyExists)
1269  NewBCs[CastSrcTy] = NewBC;
1270  auto *Ext = Builder.CreateExtractElement(
1271  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1272  // The shufflevector isn't being replaced: the bitcast that used it
1273  // is. InstCombine will visit the newly-created instructions.
1274  replaceInstUsesWith(*BC, Ext);
1275  MadeChange = true;
1276  }
1277  }
1278 
1279  // If the LHS is a shufflevector itself, see if we can combine it with this
1280  // one without producing an unusual shuffle.
1281  // Cases that might be simplified:
1282  // 1.
1283  // x1=shuffle(v1,v2,mask1)
1284  // x=shuffle(x1,undef,mask)
1285  // ==>
1286  // x=shuffle(v1,undef,newMask)
1287  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1288  // 2.
1289  // x1=shuffle(v1,undef,mask1)
1290  // x=shuffle(x1,x2,mask)
1291  // where v1.size() == mask1.size()
1292  // ==>
1293  // x=shuffle(v1,x2,newMask)
1294  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1295  // 3.
1296  // x2=shuffle(v2,undef,mask2)
1297  // x=shuffle(x1,x2,mask)
1298  // where v2.size() == mask2.size()
1299  // ==>
1300  // x=shuffle(x1,v2,newMask)
1301  // newMask[i] = (mask[i] < x1.size())
1302  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1303  // 4.
1304  // x1=shuffle(v1,undef,mask1)
1305  // x2=shuffle(v2,undef,mask2)
1306  // x=shuffle(x1,x2,mask)
1307  // where v1.size() == v2.size()
1308  // ==>
1309  // x=shuffle(v1,v2,newMask)
1310  // newMask[i] = (mask[i] < x1.size())
1311  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1312  //
1313  // Here we are really conservative:
1314  // we are absolutely afraid of producing a shuffle mask not in the input
1315  // program, because the code gen may not be smart enough to turn a merged
1316  // shuffle into two specific shuffles: it may produce worse code. As such,
1317  // we only merge two shuffles if the result is either a splat or one of the
1318  // input shuffle masks. In this case, merging the shuffles just removes
1319  // one instruction, which we know is safe. This is good for things like
1320  // turning: (splat(splat)) -> splat, or
1321  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1322  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1323  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1324  if (LHSShuffle)
1325  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1326  LHSShuffle = nullptr;
1327  if (RHSShuffle)
1328  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1329  RHSShuffle = nullptr;
1330  if (!LHSShuffle && !RHSShuffle)
1331  return MadeChange ? &SVI : nullptr;
1332 
1333  Value* LHSOp0 = nullptr;
1334  Value* LHSOp1 = nullptr;
1335  Value* RHSOp0 = nullptr;
1336  unsigned LHSOp0Width = 0;
1337  unsigned RHSOp0Width = 0;
1338  if (LHSShuffle) {
1339  LHSOp0 = LHSShuffle->getOperand(0);
1340  LHSOp1 = LHSShuffle->getOperand(1);
1341  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1342  }
1343  if (RHSShuffle) {
1344  RHSOp0 = RHSShuffle->getOperand(0);
1345  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1346  }
1347  Value* newLHS = LHS;
1348  Value* newRHS = RHS;
1349  if (LHSShuffle) {
1350  // case 1
1351  if (isa<UndefValue>(RHS)) {
1352  newLHS = LHSOp0;
1353  newRHS = LHSOp1;
1354  }
1355  // case 2 or 4
1356  else if (LHSOp0Width == LHSWidth) {
1357  newLHS = LHSOp0;
1358  }
1359  }
1360  // case 3 or 4
1361  if (RHSShuffle && RHSOp0Width == LHSWidth) {
1362  newRHS = RHSOp0;
1363  }
1364  // case 4
1365  if (LHSOp0 == RHSOp0) {
1366  newLHS = LHSOp0;
1367  newRHS = nullptr;
1368  }
1369 
1370  if (newLHS == LHS && newRHS == RHS)
1371  return MadeChange ? &SVI : nullptr;
1372 
1373  SmallVector<int, 16> LHSMask;
1374  SmallVector<int, 16> RHSMask;
1375  if (newLHS != LHS)
1376  LHSMask = LHSShuffle->getShuffleMask();
1377  if (RHSShuffle && newRHS != RHS)
1378  RHSMask = RHSShuffle->getShuffleMask();
1379 
1380  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1381  SmallVector<int, 16> newMask;
1382  bool isSplat = true;
1383  int SplatElt = -1;
1384  // Create a new mask for the new ShuffleVectorInst so that the new
1385  // ShuffleVectorInst is equivalent to the original one.
1386  for (unsigned i = 0; i < VWidth; ++i) {
1387  int eltMask;
1388  if (Mask[i] < 0) {
1389  // This element is an undef value.
1390  eltMask = -1;
1391  } else if (Mask[i] < (int)LHSWidth) {
1392  // This element is from left hand side vector operand.
1393  //
1394  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1395  // new mask value for the element.
1396  if (newLHS != LHS) {
1397  eltMask = LHSMask[Mask[i]];
1398  // If the value selected is an undef value, explicitly specify it
1399  // with a -1 mask value.
1400  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1401  eltMask = -1;
1402  } else
1403  eltMask = Mask[i];
1404  } else {
1405  // This element is from right hand side vector operand
1406  //
1407  // If the value selected is an undef value, explicitly specify it
1408  // with a -1 mask value. (case 1)
1409  if (isa<UndefValue>(RHS))
1410  eltMask = -1;
1411  // If RHS is going to be replaced (case 3 or 4), calculate the
1412  // new mask value for the element.
1413  else if (newRHS != RHS) {
1414  eltMask = RHSMask[Mask[i]-LHSWidth];
1415  // If the value selected is an undef value, explicitly specify it
1416  // with a -1 mask value.
1417  if (eltMask >= (int)RHSOp0Width) {
1418  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1419  && "should have been check above");
1420  eltMask = -1;
1421  }
1422  } else
1423  eltMask = Mask[i]-LHSWidth;
1424 
1425  // If LHS's width is changed, shift the mask value accordingly.
1426  // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any
1427  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1428  // If newRHS == newLHS, we want to remap any references from newRHS to
1429  // newLHS so that we can properly identify splats that may occur due to
1430  // obfuscation across the two vectors.
1431  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1432  eltMask += newLHSWidth;
1433  }
1434 
1435  // Check if this could still be a splat.
1436  if (eltMask >= 0) {
1437  if (SplatElt >= 0 && SplatElt != eltMask)
1438  isSplat = false;
1439  SplatElt = eltMask;
1440  }
1441 
1442  newMask.push_back(eltMask);
1443  }
1444 
1445  // If the result mask is equal to one of the original shuffle masks,
1446  // or is a splat, do the replacement.
1447  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1449  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1450  if (newMask[i] < 0) {
1451  Elts.push_back(UndefValue::get(Int32Ty));
1452  } else {
1453  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1454  }
1455  }
1456  if (!newRHS)
1457  newRHS = UndefValue::get(newLHS->getType());
1458  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1459  }
1460 
1461  // If the result mask is an identity, replace uses of this instruction with
1462  // corresponding argument.
1463  bool isLHSID, isRHSID;
1464  recognizeIdentityMask(newMask, isLHSID, isRHSID);
1465  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1466  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1467 
1468  return MadeChange ? &SVI : nullptr;
1469 }
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.
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 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:125
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
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:823
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.
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:85
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
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 bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:529
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)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
Definition: Constants.h:193
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)
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.