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