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