LLVM  8.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 
170  InstCombiner::BuilderTy &Builder,
171  bool IsBigEndian) {
172  Value *X;
173  uint64_t ExtIndexC;
174  if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) ||
175  !X->getType()->isVectorTy() ||
176  !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC)))
177  return nullptr;
178 
179  // If this extractelement is using a bitcast from a vector of the same number
180  // of elements, see if we can find the source element from the source vector:
181  // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
182  Type *SrcTy = X->getType();
183  Type *DestTy = Ext.getType();
184  unsigned NumSrcElts = SrcTy->getVectorNumElements();
185  unsigned NumElts = Ext.getVectorOperandType()->getNumElements();
186  if (NumSrcElts == NumElts)
187  if (Value *Elt = findScalarElement(X, ExtIndexC))
188  return new BitCastInst(Elt, DestTy);
189 
190  // If the source elements are wider than the destination, try to shift and
191  // truncate a subset of scalar bits of an insert op.
192  if (NumSrcElts < NumElts) {
193  Value *Scalar;
194  uint64_t InsIndexC;
195  if (!match(X, m_InsertElement(m_Value(), m_Value(Scalar),
196  m_ConstantInt(InsIndexC))))
197  return nullptr;
198 
199  // The extract must be from the subset of vector elements that we inserted
200  // into. Example: if we inserted element 1 of a <2 x i64> and we are
201  // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
202  // of elements 4-7 of the bitcasted vector.
203  unsigned NarrowingRatio = NumElts / NumSrcElts;
204  if (ExtIndexC / NarrowingRatio != InsIndexC)
205  return nullptr;
206 
207  // We are extracting part of the original scalar. How that scalar is
208  // inserted into the vector depends on the endian-ness. Example:
209  // Vector Byte Elt Index: 0 1 2 3 4 5 6 7
210  // +--+--+--+--+--+--+--+--+
211  // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3|
212  // extelt <4 x i16> V', 3: | |S2|S3|
213  // +--+--+--+--+--+--+--+--+
214  // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
215  // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
216  // In this example, we must right-shift little-endian. Big-endian is just a
217  // truncate.
218  unsigned Chunk = ExtIndexC % NarrowingRatio;
219  if (IsBigEndian)
220  Chunk = NarrowingRatio - 1 - Chunk;
221 
222  // Bail out if this is an FP vector to FP vector sequence. That would take
223  // more instructions than we started with unless there is no shift, and it
224  // may not be handled as well in the backend.
225  bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
226  bool NeedDestBitcast = DestTy->isFloatingPointTy();
227  if (NeedSrcBitcast && NeedDestBitcast)
228  return nullptr;
229 
230  unsigned SrcWidth = SrcTy->getScalarSizeInBits();
231  unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
232  unsigned ShAmt = Chunk * DestWidth;
233 
234  // TODO: This limitation is more strict than necessary. We could sum the
235  // number of new instructions and subtract the number eliminated to know if
236  // we can proceed.
237  if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
238  if (NeedSrcBitcast || NeedDestBitcast)
239  return nullptr;
240 
241  if (NeedSrcBitcast) {
242  Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth);
243  Scalar = Builder.CreateBitCast(Scalar, SrcIntTy);
244  }
245 
246  if (ShAmt) {
247  // Bail out if we could end with more instructions than we started with.
248  if (!Ext.getVectorOperand()->hasOneUse())
249  return nullptr;
250  Scalar = Builder.CreateLShr(Scalar, ShAmt);
251  }
252 
253  if (NeedDestBitcast) {
254  Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth);
255  return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy);
256  }
257  return new TruncInst(Scalar, DestTy);
258  }
259 
260  return nullptr;
261 }
262 
265  EI.getIndexOperand(),
266  SQ.getWithInstruction(&EI)))
267  return replaceInstUsesWith(EI, V);
268 
269  // If vector val is constant with all elements the same, replace EI with
270  // that element. We handle a known element # below.
271  if (Constant *C = dyn_cast<Constant>(EI.getOperand(0)))
272  if (cheapToScalarize(C, false))
273  return replaceInstUsesWith(EI, C->getAggregateElement(0U));
274 
275  // If extracting a specified index from the vector, see if we can recursively
276  // find a previously computed scalar that was inserted into the vector.
277  if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
278  unsigned NumElts = EI.getVectorOperandType()->getNumElements();
279 
280  // InstSimplify should handle cases where the index is invalid.
281  if (!IdxC->getValue().ule(NumElts))
282  return nullptr;
283 
284  // This instruction only demands the single element from the input vector.
285  // If the input vector has a single use, simplify it based on this use
286  // property.
287  if (EI.getOperand(0)->hasOneUse() && NumElts != 1) {
288  APInt UndefElts(NumElts, 0);
289  APInt DemandedMask(NumElts, 0);
290  DemandedMask.setBit(IdxC->getZExtValue());
291  if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask,
292  UndefElts)) {
293  EI.setOperand(0, V);
294  return &EI;
295  }
296  }
297 
298  if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
299  return I;
300 
301  // If there's a vector PHI feeding a scalar use through this extractelement
302  // instruction, try to scalarize the PHI.
303  if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) {
304  Instruction *scalarPHI = scalarizePHI(EI, PN);
305  if (scalarPHI)
306  return scalarPHI;
307  }
308  }
309 
310  if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
311  // Push extractelement into predecessor operation if legal and
312  // profitable to do so.
313  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
314  if (I->hasOneUse() &&
315  cheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
316  Value *newEI0 =
317  Builder.CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
318  EI.getName()+".lhs");
319  Value *newEI1 =
320  Builder.CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
321  EI.getName()+".rhs");
322  return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(),
323  newEI0, newEI1, BO);
324  }
325  } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
326  // Extracting the inserted element?
327  if (IE->getOperand(2) == EI.getOperand(1))
328  return replaceInstUsesWith(EI, IE->getOperand(1));
329  // If the inserted and extracted elements are constants, they must not
330  // be the same value, extract from the pre-inserted value instead.
331  if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
332  Worklist.AddValue(EI.getOperand(0));
333  EI.setOperand(0, IE->getOperand(0));
334  return &EI;
335  }
336  } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
337  // If this is extracting an element from a shufflevector, figure out where
338  // it came from and extract from the appropriate input element instead.
339  if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
340  int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
341  Value *Src;
342  unsigned LHSWidth =
343  SVI->getOperand(0)->getType()->getVectorNumElements();
344 
345  if (SrcIdx < 0)
346  return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
347  if (SrcIdx < (int)LHSWidth)
348  Src = SVI->getOperand(0);
349  else {
350  SrcIdx -= LHSWidth;
351  Src = SVI->getOperand(1);
352  }
354  return ExtractElementInst::Create(Src,
355  ConstantInt::get(Int32Ty,
356  SrcIdx, false));
357  }
358  } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
359  // Canonicalize extractelement(cast) -> cast(extractelement).
360  // Bitcasts can change the number of vector elements, and they cost
361  // nothing.
362  if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
363  Value *EE = Builder.CreateExtractElement(CI->getOperand(0),
364  EI.getIndexOperand());
365  Worklist.AddValue(EE);
366  return CastInst::Create(CI->getOpcode(), EE, EI.getType());
367  }
368  }
369  }
370  return nullptr;
371 }
372 
373 /// If V is a shuffle of values that ONLY returns elements from either LHS or
374 /// RHS, return the shuffle mask and true. Otherwise, return false.
375 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
377  assert(LHS->getType() == RHS->getType() &&
378  "Invalid CollectSingleShuffleElements");
379  unsigned NumElts = V->getType()->getVectorNumElements();
380 
381  if (isa<UndefValue>(V)) {
382  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
383  return true;
384  }
385 
386  if (V == LHS) {
387  for (unsigned i = 0; i != NumElts; ++i)
389  return true;
390  }
391 
392  if (V == RHS) {
393  for (unsigned i = 0; i != NumElts; ++i)
395  i+NumElts));
396  return true;
397  }
398 
399  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
400  // If this is an insert of an extract from some other vector, include it.
401  Value *VecOp = IEI->getOperand(0);
402  Value *ScalarOp = IEI->getOperand(1);
403  Value *IdxOp = IEI->getOperand(2);
404 
405  if (!isa<ConstantInt>(IdxOp))
406  return false;
407  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
408 
409  if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
410  // We can handle this if the vector we are inserting into is
411  // transitively ok.
412  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
413  // If so, update the mask to reflect the inserted undef.
414  Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
415  return true;
416  }
417  } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
418  if (isa<ConstantInt>(EI->getOperand(1))) {
419  unsigned ExtractedIdx =
420  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
421  unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
422 
423  // This must be extracting from either LHS or RHS.
424  if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
425  // We can handle this if the vector we are inserting into is
426  // transitively ok.
427  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
428  // If so, update the mask to reflect the inserted value.
429  if (EI->getOperand(0) == LHS) {
430  Mask[InsertedIdx % NumElts] =
432  ExtractedIdx);
433  } else {
434  assert(EI->getOperand(0) == RHS);
435  Mask[InsertedIdx % NumElts] =
437  ExtractedIdx + NumLHSElts);
438  }
439  return true;
440  }
441  }
442  }
443  }
444  }
445 
446  return false;
447 }
448 
449 /// If we have insertion into a vector that is wider than the vector that we
450 /// are extracting from, try to widen the source vector to allow a single
451 /// shufflevector to replace one or more insert/extract pairs.
453  ExtractElementInst *ExtElt,
454  InstCombiner &IC) {
455  VectorType *InsVecType = InsElt->getType();
456  VectorType *ExtVecType = ExtElt->getVectorOperandType();
457  unsigned NumInsElts = InsVecType->getVectorNumElements();
458  unsigned NumExtElts = ExtVecType->getVectorNumElements();
459 
460  // The inserted-to vector must be wider than the extracted-from vector.
461  if (InsVecType->getElementType() != ExtVecType->getElementType() ||
462  NumExtElts >= NumInsElts)
463  return;
464 
465  // Create a shuffle mask to widen the extended-from vector using undefined
466  // values. The mask selects all of the values of the original vector followed
467  // by as many undefined values as needed to create a vector of the same length
468  // as the inserted-to vector.
469  SmallVector<Constant *, 16> ExtendMask;
470  IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
471  for (unsigned i = 0; i < NumExtElts; ++i)
472  ExtendMask.push_back(ConstantInt::get(IntType, i));
473  for (unsigned i = NumExtElts; i < NumInsElts; ++i)
474  ExtendMask.push_back(UndefValue::get(IntType));
475 
476  Value *ExtVecOp = ExtElt->getVectorOperand();
477  auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
478  BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
479  ? ExtVecOpInst->getParent()
480  : ExtElt->getParent();
481 
482  // TODO: This restriction matches the basic block check below when creating
483  // new extractelement instructions. If that limitation is removed, this one
484  // could also be removed. But for now, we just bail out to ensure that we
485  // will replace the extractelement instruction that is feeding our
486  // insertelement instruction. This allows the insertelement to then be
487  // replaced by a shufflevector. If the insertelement is not replaced, we can
488  // induce infinite looping because there's an optimization for extractelement
489  // that will delete our widening shuffle. This would trigger another attempt
490  // here to create that shuffle, and we spin forever.
491  if (InsertionBlock != InsElt->getParent())
492  return;
493 
494  // TODO: This restriction matches the check in visitInsertElementInst() and
495  // prevents an infinite loop caused by not turning the extract/insert pair
496  // into a shuffle. We really should not need either check, but we're lacking
497  // folds for shufflevectors because we're afraid to generate shuffle masks
498  // that the backend can't handle.
499  if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
500  return;
501 
502  auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
503  ConstantVector::get(ExtendMask));
504 
505  // Insert the new shuffle after the vector operand of the extract is defined
506  // (as long as it's not a PHI) or at the start of the basic block of the
507  // extract, so any subsequent extracts in the same basic block can use it.
508  // TODO: Insert before the earliest ExtractElementInst that is replaced.
509  if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
510  WideVec->insertAfter(ExtVecOpInst);
511  else
512  IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
513 
514  // Replace extracts from the original narrow vector with extracts from the new
515  // wide vector.
516  for (User *U : ExtVecOp->users()) {
518  if (!OldExt || OldExt->getParent() != WideVec->getParent())
519  continue;
520  auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
521  NewExt->insertAfter(OldExt);
522  IC.replaceInstUsesWith(*OldExt, NewExt);
523  }
524 }
525 
526 /// We are building a shuffle to create V, which is a sequence of insertelement,
527 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
528 /// not rely on the second vector source. Return a std::pair containing the
529 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
530 /// parameter as required.
531 ///
532 /// Note: we intentionally don't try to fold earlier shuffles since they have
533 /// often been chosen carefully to be efficiently implementable on the target.
534 using ShuffleOps = std::pair<Value *, Value *>;
535 
538  Value *PermittedRHS,
539  InstCombiner &IC) {
540  assert(V->getType()->isVectorTy() && "Invalid shuffle!");
541  unsigned NumElts = V->getType()->getVectorNumElements();
542 
543  if (isa<UndefValue>(V)) {
544  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
545  return std::make_pair(
546  PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
547  }
548 
549  if (isa<ConstantAggregateZero>(V)) {
550  Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
551  return std::make_pair(V, nullptr);
552  }
553 
554  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
555  // If this is an insert of an extract from some other vector, include it.
556  Value *VecOp = IEI->getOperand(0);
557  Value *ScalarOp = IEI->getOperand(1);
558  Value *IdxOp = IEI->getOperand(2);
559 
560  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
561  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
562  unsigned ExtractedIdx =
563  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
564  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
565 
566  // Either the extracted from or inserted into vector must be RHSVec,
567  // otherwise we'd end up with a shuffle of three inputs.
568  if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
569  Value *RHS = EI->getOperand(0);
570  ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
571  assert(LR.second == nullptr || LR.second == RHS);
572 
573  if (LR.first->getType() != RHS->getType()) {
574  // Although we are giving up for now, see if we can create extracts
575  // that match the inserts for another round of combining.
576  replaceExtractElements(IEI, EI, IC);
577 
578  // We tried our best, but we can't find anything compatible with RHS
579  // further up the chain. Return a trivial shuffle.
580  for (unsigned i = 0; i < NumElts; ++i)
581  Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
582  return std::make_pair(V, nullptr);
583  }
584 
585  unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
586  Mask[InsertedIdx % NumElts] =
588  NumLHSElts+ExtractedIdx);
589  return std::make_pair(LR.first, RHS);
590  }
591 
592  if (VecOp == PermittedRHS) {
593  // We've gone as far as we can: anything on the other side of the
594  // extractelement will already have been converted into a shuffle.
595  unsigned NumLHSElts =
597  for (unsigned i = 0; i != NumElts; ++i)
600  i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
601  return std::make_pair(EI->getOperand(0), PermittedRHS);
602  }
603 
604  // If this insertelement is a chain that comes from exactly these two
605  // vectors, return the vector and the effective shuffle.
606  if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
607  collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
608  Mask))
609  return std::make_pair(EI->getOperand(0), PermittedRHS);
610  }
611  }
612  }
613 
614  // Otherwise, we can't do anything fancy. Return an identity vector.
615  for (unsigned i = 0; i != NumElts; ++i)
617  return std::make_pair(V, nullptr);
618 }
619 
620 /// Try to find redundant insertvalue instructions, like the following ones:
621 /// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
622 /// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
623 /// Here the second instruction inserts values at the same indices, as the
624 /// first one, making the first one redundant.
625 /// It should be transformed to:
626 /// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
628  bool IsRedundant = false;
629  ArrayRef<unsigned int> FirstIndices = I.getIndices();
630 
631  // If there is a chain of insertvalue instructions (each of them except the
632  // last one has only one use and it's another insertvalue insn from this
633  // chain), check if any of the 'children' uses the same indices as the first
634  // instruction. In this case, the first one is redundant.
635  Value *V = &I;
636  unsigned Depth = 0;
637  while (V->hasOneUse() && Depth < 10) {
638  User *U = V->user_back();
639  auto UserInsInst = dyn_cast<InsertValueInst>(U);
640  if (!UserInsInst || U->getOperand(0) != V)
641  break;
642  if (UserInsInst->getIndices() == FirstIndices) {
643  IsRedundant = true;
644  break;
645  }
646  V = UserInsInst;
647  Depth++;
648  }
649 
650  if (IsRedundant)
651  return replaceInstUsesWith(I, I.getOperand(0));
652  return nullptr;
653 }
654 
656  int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
657  int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
658 
659  // A vector select does not change the size of the operands.
660  if (MaskSize != VecSize)
661  return false;
662 
663  // Each mask element must be undefined or choose a vector element from one of
664  // the source operands without crossing vector lanes.
665  for (int i = 0; i != MaskSize; ++i) {
666  int Elt = Shuf.getMaskValue(i);
667  if (Elt != -1 && Elt != i && Elt != i + VecSize)
668  return false;
669  }
670 
671  return true;
672 }
673 
674 // Turn a chain of inserts that splats a value into a canonical insert + shuffle
675 // splat. That is:
676 // insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
677 // shufflevector(insertelt(X, %k, 0), undef, zero)
679  // We are interested in the last insert in a chain. So, if this insert
680  // has a single user, and that user is an insert, bail.
681  if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
682  return nullptr;
683 
684  VectorType *VT = cast<VectorType>(InsElt.getType());
685  int NumElements = VT->getNumElements();
686 
687  // Do not try to do this for a one-element vector, since that's a nop,
688  // and will cause an inf-loop.
689  if (NumElements == 1)
690  return nullptr;
691 
692  Value *SplatVal = InsElt.getOperand(1);
693  InsertElementInst *CurrIE = &InsElt;
694  SmallVector<bool, 16> ElementPresent(NumElements, false);
695  InsertElementInst *FirstIE = nullptr;
696 
697  // Walk the chain backwards, keeping track of which indices we inserted into,
698  // until we hit something that isn't an insert of the splatted value.
699  while (CurrIE) {
700  auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
701  if (!Idx || CurrIE->getOperand(1) != SplatVal)
702  return nullptr;
703 
704  auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
705  // Check none of the intermediate steps have any additional uses, except
706  // for the root insertelement instruction, which can be re-used, if it
707  // inserts at position 0.
708  if (CurrIE != &InsElt &&
709  (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
710  return nullptr;
711 
712  ElementPresent[Idx->getZExtValue()] = true;
713  FirstIE = CurrIE;
714  CurrIE = NextIE;
715  }
716 
717  // Make sure we've seen an insert into every element.
718  if (llvm::any_of(ElementPresent, [](bool Present) { return !Present; }))
719  return nullptr;
720 
721  // All right, create the insert + shuffle.
722  Instruction *InsertFirst;
723  if (cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
724  InsertFirst = FirstIE;
725  else
726  InsertFirst = InsertElementInst::Create(
727  UndefValue::get(VT), SplatVal,
729  "", &InsElt);
730 
732  VectorType::get(Type::getInt32Ty(InsElt.getContext()), NumElements));
733 
734  return new ShuffleVectorInst(InsertFirst, UndefValue::get(VT), ZeroMask);
735 }
736 
737 /// If we have an insertelement instruction feeding into another insertelement
738 /// and the 2nd is inserting a constant into the vector, canonicalize that
739 /// constant insertion before the insertion of a variable:
740 ///
741 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
742 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
743 ///
744 /// This has the potential of eliminating the 2nd insertelement instruction
745 /// via constant folding of the scalar constant into a vector constant.
747  InstCombiner::BuilderTy &Builder) {
748  auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
749  if (!InsElt1 || !InsElt1->hasOneUse())
750  return nullptr;
751 
752  Value *X, *Y;
753  Constant *ScalarC;
754  ConstantInt *IdxC1, *IdxC2;
755  if (match(InsElt1->getOperand(0), m_Value(X)) &&
756  match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
757  match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
758  match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
759  match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
760  Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
761  return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
762  }
763 
764  return nullptr;
765 }
766 
767 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
768 /// --> shufflevector X, CVec', Mask'
770  auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
771  // Bail out if the parent has more than one use. In that case, we'd be
772  // replacing the insertelt with a shuffle, and that's not a clear win.
773  if (!Inst || !Inst->hasOneUse())
774  return nullptr;
775  if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
776  // The shuffle must have a constant vector operand. The insertelt must have
777  // a constant scalar being inserted at a constant position in the vector.
778  Constant *ShufConstVec, *InsEltScalar;
779  uint64_t InsEltIndex;
780  if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
781  !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
782  !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
783  return nullptr;
784 
785  // Adding an element to an arbitrary shuffle could be expensive, but a
786  // shuffle that selects elements from vectors without crossing lanes is
787  // assumed cheap.
788  // If we're just adding a constant into that shuffle, it will still be
789  // cheap.
790  if (!isShuffleEquivalentToSelect(*Shuf))
791  return nullptr;
792 
793  // From the above 'select' check, we know that the mask has the same number
794  // of elements as the vector input operands. We also know that each constant
795  // input element is used in its lane and can not be used more than once by
796  // the shuffle. Therefore, replace the constant in the shuffle's constant
797  // vector with the insertelt constant. Replace the constant in the shuffle's
798  // mask vector with the insertelt index plus the length of the vector
799  // (because the constant vector operand of a shuffle is always the 2nd
800  // operand).
801  Constant *Mask = Shuf->getMask();
802  unsigned NumElts = Mask->getType()->getVectorNumElements();
803  SmallVector<Constant *, 16> NewShufElts(NumElts);
804  SmallVector<Constant *, 16> NewMaskElts(NumElts);
805  for (unsigned I = 0; I != NumElts; ++I) {
806  if (I == InsEltIndex) {
807  NewShufElts[I] = InsEltScalar;
808  Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
809  NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
810  } else {
811  // Copy over the existing values.
812  NewShufElts[I] = ShufConstVec->getAggregateElement(I);
813  NewMaskElts[I] = Mask->getAggregateElement(I);
814  }
815  }
816 
817  // Create new operands for a shuffle that includes the constant of the
818  // original insertelt. The old shuffle will be dead now.
819  return new ShuffleVectorInst(Shuf->getOperand(0),
820  ConstantVector::get(NewShufElts),
821  ConstantVector::get(NewMaskElts));
822  } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
823  // Transform sequences of insertelements ops with constant data/indexes into
824  // a single shuffle op.
825  unsigned NumElts = InsElt.getType()->getNumElements();
826 
827  uint64_t InsertIdx[2];
828  Constant *Val[2];
829  if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
830  !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
831  !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
832  !match(IEI->getOperand(1), m_Constant(Val[1])))
833  return nullptr;
834  SmallVector<Constant *, 16> Values(NumElts);
836  auto ValI = std::begin(Val);
837  // Generate new constant vector and mask.
838  // We have 2 values/masks from the insertelements instructions. Insert them
839  // into new value/mask vectors.
840  for (uint64_t I : InsertIdx) {
841  if (!Values[I]) {
842  assert(!Mask[I]);
843  Values[I] = *ValI;
844  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
845  NumElts + I);
846  }
847  ++ValI;
848  }
849  // Remaining values are filled with 'undef' values.
850  for (unsigned I = 0; I < NumElts; ++I) {
851  if (!Values[I]) {
852  assert(!Mask[I]);
853  Values[I] = UndefValue::get(InsElt.getType()->getElementType());
854  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
855  }
856  }
857  // Create new operands for a shuffle that includes the constant of the
858  // original insertelt.
859  return new ShuffleVectorInst(IEI->getOperand(0),
860  ConstantVector::get(Values),
861  ConstantVector::get(Mask));
862  }
863  return nullptr;
864 }
865 
867  Value *VecOp = IE.getOperand(0);
868  Value *ScalarOp = IE.getOperand(1);
869  Value *IdxOp = IE.getOperand(2);
870 
871  if (auto *V = SimplifyInsertElementInst(
872  VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
873  return replaceInstUsesWith(IE, V);
874 
875  // Inserting an undef or into an undefined place, remove this.
876  if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
877  replaceInstUsesWith(IE, VecOp);
878 
879  // If the inserted element was extracted from some other vector, and if the
880  // indexes are constant, try to turn this into a shufflevector operation.
881  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
882  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
883  unsigned NumInsertVectorElts = IE.getType()->getNumElements();
884  unsigned NumExtractVectorElts =
886  unsigned ExtractedIdx =
887  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
888  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
889 
890  if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
891  return replaceInstUsesWith(IE, VecOp);
892 
893  if (InsertedIdx >= NumInsertVectorElts) // Out of range insert.
894  return replaceInstUsesWith(IE, UndefValue::get(IE.getType()));
895 
896  // If we are extracting a value from a vector, then inserting it right
897  // back into the same place, just use the input vector.
898  if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
899  return replaceInstUsesWith(IE, VecOp);
900 
901  // If this insertelement isn't used by some other insertelement, turn it
902  // (and any insertelements it points to), into one big shuffle.
903  if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) {
905  ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
906 
907  // The proposed shuffle may be trivial, in which case we shouldn't
908  // perform the combine.
909  if (LR.first != &IE && LR.second != &IE) {
910  // We now have a shuffle of LHS, RHS, Mask.
911  if (LR.second == nullptr)
912  LR.second = UndefValue::get(LR.first->getType());
913  return new ShuffleVectorInst(LR.first, LR.second,
914  ConstantVector::get(Mask));
915  }
916  }
917  }
918  }
919 
920  unsigned VWidth = VecOp->getType()->getVectorNumElements();
921  APInt UndefElts(VWidth, 0);
922  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
923  if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
924  if (V != &IE)
925  return replaceInstUsesWith(IE, V);
926  return &IE;
927  }
928 
930  return Shuf;
931 
932  if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
933  return NewInsElt;
934 
935  // Turn a sequence of inserts that broadcasts a scalar into a single
936  // insert + shufflevector.
937  if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE))
938  return Broadcast;
939 
940  return nullptr;
941 }
942 
943 /// Return true if we can evaluate the specified expression tree if the vector
944 /// elements were shuffled in a different order.
946  unsigned Depth = 5) {
947  // We can always reorder the elements of a constant.
948  if (isa<Constant>(V))
949  return true;
950 
951  // We won't reorder vector arguments. No IPO here.
953  if (!I) return false;
954 
955  // Two users may expect different orders of the elements. Don't try it.
956  if (!I->hasOneUse())
957  return false;
958 
959  if (Depth == 0) return false;
960 
961  switch (I->getOpcode()) {
962  case Instruction::Add:
963  case Instruction::FAdd:
964  case Instruction::Sub:
965  case Instruction::FSub:
966  case Instruction::Mul:
967  case Instruction::FMul:
968  case Instruction::UDiv:
969  case Instruction::SDiv:
970  case Instruction::FDiv:
971  case Instruction::URem:
972  case Instruction::SRem:
973  case Instruction::FRem:
974  case Instruction::Shl:
975  case Instruction::LShr:
976  case Instruction::AShr:
977  case Instruction::And:
978  case Instruction::Or:
979  case Instruction::Xor:
980  case Instruction::ICmp:
981  case Instruction::FCmp:
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  case Instruction::GetElementPtr: {
992  // Bail out if we would create longer vector ops. We could allow creating
993  // longer vector ops, but that may result in more expensive codegen. We
994  // would also need to limit the transform to avoid undefined behavior for
995  // integer div/rem.
996  Type *ITy = I->getType();
997  if (ITy->isVectorTy() && Mask.size() > ITy->getVectorNumElements())
998  return false;
999  for (Value *Operand : I->operands()) {
1000  if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
1001  return false;
1002  }
1003  return true;
1004  }
1005  case Instruction::InsertElement: {
1007  if (!CI) return false;
1008  int ElementNumber = CI->getLimitedValue();
1009 
1010  // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
1011  // can't put an element into multiple indices.
1012  bool SeenOnce = false;
1013  for (int i = 0, e = Mask.size(); i != e; ++i) {
1014  if (Mask[i] == ElementNumber) {
1015  if (SeenOnce)
1016  return false;
1017  SeenOnce = true;
1018  }
1019  }
1020  return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1);
1021  }
1022  }
1023  return false;
1024 }
1025 
1026 /// Rebuild a new instruction just like 'I' but with the new operands given.
1027 /// In the event of type mismatch, the type of the operands is correct.
1029  // We don't want to use the IRBuilder here because we want the replacement
1030  // instructions to appear next to 'I', not the builder's insertion point.
1031  switch (I->getOpcode()) {
1032  case Instruction::Add:
1033  case Instruction::FAdd:
1034  case Instruction::Sub:
1035  case Instruction::FSub:
1036  case Instruction::Mul:
1037  case Instruction::FMul:
1038  case Instruction::UDiv:
1039  case Instruction::SDiv:
1040  case Instruction::FDiv:
1041  case Instruction::URem:
1042  case Instruction::SRem:
1043  case Instruction::FRem:
1044  case Instruction::Shl:
1045  case Instruction::LShr:
1046  case Instruction::AShr:
1047  case Instruction::And:
1048  case Instruction::Or:
1049  case Instruction::Xor: {
1050  BinaryOperator *BO = cast<BinaryOperator>(I);
1051  assert(NewOps.size() == 2 && "binary operator with #ops != 2");
1052  BinaryOperator *New =
1053  BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
1054  NewOps[0], NewOps[1], "", BO);
1055  if (isa<OverflowingBinaryOperator>(BO)) {
1056  New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
1057  New->setHasNoSignedWrap(BO->hasNoSignedWrap());
1058  }
1059  if (isa<PossiblyExactOperator>(BO)) {
1060  New->setIsExact(BO->isExact());
1061  }
1062  if (isa<FPMathOperator>(BO))
1063  New->copyFastMathFlags(I);
1064  return New;
1065  }
1066  case Instruction::ICmp:
1067  assert(NewOps.size() == 2 && "icmp with #ops != 2");
1068  return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
1069  NewOps[0], NewOps[1]);
1070  case Instruction::FCmp:
1071  assert(NewOps.size() == 2 && "fcmp with #ops != 2");
1072  return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
1073  NewOps[0], NewOps[1]);
1074  case Instruction::Trunc:
1075  case Instruction::ZExt:
1076  case Instruction::SExt:
1077  case Instruction::FPToUI:
1078  case Instruction::FPToSI:
1079  case Instruction::UIToFP:
1080  case Instruction::SIToFP:
1081  case Instruction::FPTrunc:
1082  case Instruction::FPExt: {
1083  // It's possible that the mask has a different number of elements from
1084  // the original cast. We recompute the destination type to match the mask.
1085  Type *DestTy =
1087  NewOps[0]->getType()->getVectorNumElements());
1088  assert(NewOps.size() == 1 && "cast with #ops != 1");
1089  return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
1090  "", I);
1091  }
1092  case Instruction::GetElementPtr: {
1093  Value *Ptr = NewOps[0];
1094  ArrayRef<Value*> Idx = NewOps.slice(1);
1096  cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1097  GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1098  return GEP;
1099  }
1100  }
1101  llvm_unreachable("failed to rebuild vector instructions");
1102 }
1103 
1105  // Mask.size() does not need to be equal to the number of vector elements.
1106 
1107  assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1108  Type *EltTy = V->getType()->getScalarType();
1109  Type *I32Ty = IntegerType::getInt32Ty(V->getContext());
1110  if (isa<UndefValue>(V))
1111  return UndefValue::get(VectorType::get(EltTy, Mask.size()));
1112 
1113  if (isa<ConstantAggregateZero>(V))
1114  return ConstantAggregateZero::get(VectorType::get(EltTy, Mask.size()));
1115 
1116  if (Constant *C = dyn_cast<Constant>(V)) {
1117  SmallVector<Constant *, 16> MaskValues;
1118  for (int i = 0, e = Mask.size(); i != e; ++i) {
1119  if (Mask[i] == -1)
1120  MaskValues.push_back(UndefValue::get(I32Ty));
1121  else
1122  MaskValues.push_back(ConstantInt::get(I32Ty, Mask[i]));
1123  }
1125  ConstantVector::get(MaskValues));
1126  }
1127 
1128  Instruction *I = cast<Instruction>(V);
1129  switch (I->getOpcode()) {
1130  case Instruction::Add:
1131  case Instruction::FAdd:
1132  case Instruction::Sub:
1133  case Instruction::FSub:
1134  case Instruction::Mul:
1135  case Instruction::FMul:
1136  case Instruction::UDiv:
1137  case Instruction::SDiv:
1138  case Instruction::FDiv:
1139  case Instruction::URem:
1140  case Instruction::SRem:
1141  case Instruction::FRem:
1142  case Instruction::Shl:
1143  case Instruction::LShr:
1144  case Instruction::AShr:
1145  case Instruction::And:
1146  case Instruction::Or:
1147  case Instruction::Xor:
1148  case Instruction::ICmp:
1149  case Instruction::FCmp:
1150  case Instruction::Trunc:
1151  case Instruction::ZExt:
1152  case Instruction::SExt:
1153  case Instruction::FPToUI:
1154  case Instruction::FPToSI:
1155  case Instruction::UIToFP:
1156  case Instruction::SIToFP:
1157  case Instruction::FPTrunc:
1158  case Instruction::FPExt:
1159  case Instruction::Select:
1160  case Instruction::GetElementPtr: {
1161  SmallVector<Value*, 8> NewOps;
1162  bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1163  for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1164  Value *V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1165  NewOps.push_back(V);
1166  NeedsRebuild |= (V != I->getOperand(i));
1167  }
1168  if (NeedsRebuild) {
1169  return buildNew(I, NewOps);
1170  }
1171  return I;
1172  }
1173  case Instruction::InsertElement: {
1174  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1175 
1176  // The insertelement was inserting at Element. Figure out which element
1177  // that becomes after shuffling. The answer is guaranteed to be unique
1178  // by CanEvaluateShuffled.
1179  bool Found = false;
1180  int Index = 0;
1181  for (int e = Mask.size(); Index != e; ++Index) {
1182  if (Mask[Index] == Element) {
1183  Found = true;
1184  break;
1185  }
1186  }
1187 
1188  // If element is not in Mask, no need to handle the operand 1 (element to
1189  // be inserted). Just evaluate values in operand 0 according to Mask.
1190  if (!Found)
1191  return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1192 
1193  Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1194  return InsertElementInst::Create(V, I->getOperand(1),
1195  ConstantInt::get(I32Ty, Index), "", I);
1196  }
1197  }
1198  llvm_unreachable("failed to reorder elements of vector instruction!");
1199 }
1200 
1202  bool &isLHSID, bool &isRHSID) {
1203  isLHSID = isRHSID = true;
1204 
1205  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1206  if (Mask[i] < 0) continue; // Ignore undef values.
1207  // Is this an identity shuffle of the LHS value?
1208  isLHSID &= (Mask[i] == (int)i);
1209 
1210  // Is this an identity shuffle of the RHS value?
1211  isRHSID &= (Mask[i]-e == i);
1212  }
1213 }
1214 
1215 // Returns true if the shuffle is extracting a contiguous range of values from
1216 // LHS, for example:
1217 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1218 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1219 // Shuffles to: |EE|FF|GG|HH|
1220 // +--+--+--+--+
1223  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1224  unsigned MaskElems = Mask.size();
1225  unsigned BegIdx = Mask.front();
1226  unsigned EndIdx = Mask.back();
1227  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1228  return false;
1229  for (unsigned I = 0; I != MaskElems; ++I)
1230  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1231  return false;
1232  return true;
1233 }
1234 
1235 /// These are the ingredients in an alternate form binary operator as described
1236 /// below.
1237 struct BinopElts {
1242  Value *V0 = nullptr, Value *V1 = nullptr) :
1243  Opcode(Opc), Op0(V0), Op1(V1) {}
1244  operator bool() const { return Opcode != 0; }
1245 };
1246 
1247 /// Binops may be transformed into binops with different opcodes and operands.
1248 /// Reverse the usual canonicalization to enable folds with the non-canonical
1249 /// form of the binop. If a transform is possible, return the elements of the
1250 /// new binop. If not, return invalid elements.
1252  Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1253  Type *Ty = BO->getType();
1254  switch (BO->getOpcode()) {
1255  case Instruction::Shl: {
1256  // shl X, C --> mul X, (1 << C)
1257  Constant *C;
1258  if (match(BO1, m_Constant(C))) {
1259  Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1260  return { Instruction::Mul, BO0, ShlOne };
1261  }
1262  break;
1263  }
1264  case Instruction::Or: {
1265  // or X, C --> add X, C (when X and C have no common bits set)
1266  const APInt *C;
1267  if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1268  return { Instruction::Add, BO0, BO1 };
1269  break;
1270  }
1271  default:
1272  break;
1273  }
1274  return {};
1275 }
1276 
1278  assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1279 
1280  // Are we shuffling together some value and that same value after it has been
1281  // modified by a binop with a constant?
1282  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1283  Constant *C;
1284  bool Op0IsBinop;
1285  if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1286  Op0IsBinop = true;
1287  else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1288  Op0IsBinop = false;
1289  else
1290  return nullptr;
1291 
1292  // The identity constant for a binop leaves a variable operand unchanged. For
1293  // a vector, this is a splat of something like 0, -1, or 1.
1294  // If there's no identity constant for this binop, we're done.
1295  auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1296  BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1297  Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1298  if (!IdC)
1299  return nullptr;
1300 
1301  // Shuffle identity constants into the lanes that return the original value.
1302  // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1303  // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1304  // The existing binop constant vector remains in the same operand position.
1305  Constant *Mask = Shuf.getMask();
1306  Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1307  ConstantExpr::getShuffleVector(IdC, C, Mask);
1308 
1309  bool MightCreatePoisonOrUB =
1310  Mask->containsUndefElement() &&
1311  (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1312  if (MightCreatePoisonOrUB)
1313  NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1314 
1315  // shuf (bop X, C), X, M --> bop X, C'
1316  // shuf X, (bop X, C), M --> bop X, C'
1317  Value *X = Op0IsBinop ? Op1 : Op0;
1318  Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1319  NewBO->copyIRFlags(BO);
1320 
1321  // An undef shuffle mask element may propagate as an undef constant element in
1322  // the new binop. That would produce poison where the original code might not.
1323  // If we already made a safe constant, then there's no danger.
1324  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1325  NewBO->dropPoisonGeneratingFlags();
1326  return NewBO;
1327 }
1328 
1329 /// Try to fold shuffles that are the equivalent of a vector select.
1331  InstCombiner::BuilderTy &Builder,
1332  const DataLayout &DL) {
1333  if (!Shuf.isSelect())
1334  return nullptr;
1335 
1337  return I;
1338 
1339  BinaryOperator *B0, *B1;
1340  if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1341  !match(Shuf.getOperand(1), m_BinOp(B1)))
1342  return nullptr;
1343 
1344  Value *X, *Y;
1345  Constant *C0, *C1;
1346  bool ConstantsAreOp1;
1347  if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1348  match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1349  ConstantsAreOp1 = true;
1350  else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1351  match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1352  ConstantsAreOp1 = false;
1353  else
1354  return nullptr;
1355 
1356  // We need matching binops to fold the lanes together.
1357  BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1358  BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1359  bool DropNSW = false;
1360  if (ConstantsAreOp1 && Opc0 != Opc1) {
1361  // TODO: We drop "nsw" if shift is converted into multiply because it may
1362  // not be correct when the shift amount is BitWidth - 1. We could examine
1363  // each vector element to determine if it is safe to keep that flag.
1364  if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1365  DropNSW = true;
1366  if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1367  assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1368  Opc0 = AltB0.Opcode;
1369  C0 = cast<Constant>(AltB0.Op1);
1370  } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1371  assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1372  Opc1 = AltB1.Opcode;
1373  C1 = cast<Constant>(AltB1.Op1);
1374  }
1375  }
1376 
1377  if (Opc0 != Opc1)
1378  return nullptr;
1379 
1380  // The opcodes must be the same. Use a new name to make that clear.
1381  BinaryOperator::BinaryOps BOpc = Opc0;
1382 
1383  // Select the constant elements needed for the single binop.
1384  Constant *Mask = Shuf.getMask();
1385  Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1386 
1387  // We are moving a binop after a shuffle. When a shuffle has an undefined
1388  // mask element, the result is undefined, but it is not poison or undefined
1389  // behavior. That is not necessarily true for div/rem/shift.
1390  bool MightCreatePoisonOrUB =
1391  Mask->containsUndefElement() &&
1393  if (MightCreatePoisonOrUB)
1394  NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1395 
1396  Value *V;
1397  if (X == Y) {
1398  // Remove a binop and the shuffle by rearranging the constant:
1399  // shuffle (op V, C0), (op V, C1), M --> op V, C'
1400  // shuffle (op C0, V), (op C1, V), M --> op C', V
1401  V = X;
1402  } else {
1403  // If there are 2 different variable operands, we must create a new shuffle
1404  // (select) first, so check uses to ensure that we don't end up with more
1405  // instructions than we started with.
1406  if (!B0->hasOneUse() && !B1->hasOneUse())
1407  return nullptr;
1408 
1409  // If we use the original shuffle mask and op1 is *variable*, we would be
1410  // putting an undef into operand 1 of div/rem/shift. This is either UB or
1411  // poison. We do not have to guard against UB when *constants* are op1
1412  // because safe constants guarantee that we do not overflow sdiv/srem (and
1413  // there's no danger for other opcodes).
1414  // TODO: To allow this case, create a new shuffle mask with no undefs.
1415  if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1416  return nullptr;
1417 
1418  // Note: In general, we do not create new shuffles in InstCombine because we
1419  // do not know if a target can lower an arbitrary shuffle optimally. In this
1420  // case, the shuffle uses the existing mask, so there is no additional risk.
1421 
1422  // Select the variable vectors first, then perform the binop:
1423  // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1424  // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1425  V = Builder.CreateShuffleVector(X, Y, Mask);
1426  }
1427 
1428  Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1429  BinaryOperator::Create(BOpc, NewC, V);
1430 
1431  // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1432  // 1. If we changed an opcode, poison conditions might have changed.
1433  // 2. If the shuffle had undef mask elements, the new binop might have undefs
1434  // where the original code did not. But if we already made a safe constant,
1435  // then there's no danger.
1436  NewBO->copyIRFlags(B0);
1437  NewBO->andIRFlags(B1);
1438  if (DropNSW)
1439  NewBO->setHasNoSignedWrap(false);
1440  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1441  NewBO->dropPoisonGeneratingFlags();
1442  return NewBO;
1443 }
1444 
1445 /// Match a shuffle-select-shuffle pattern where the shuffles are widening and
1446 /// narrowing (concatenating with undef and extracting back to the original
1447 /// length). This allows replacing the wide select with a narrow select.
1449  InstCombiner::BuilderTy &Builder) {
1450  // This must be a narrowing identity shuffle. It extracts the 1st N elements
1451  // of the 1st vector operand of a shuffle.
1452  if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
1453  return nullptr;
1454 
1455  // The vector being shuffled must be a vector select that we can eliminate.
1456  // TODO: The one-use requirement could be eased if X and/or Y are constants.
1457  Value *Cond, *X, *Y;
1458  if (!match(Shuf.getOperand(0),
1459  m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
1460  return nullptr;
1461 
1462  // We need a narrow condition value. It must be extended with undef elements
1463  // and have the same number of elements as this shuffle.
1464  unsigned NarrowNumElts = Shuf.getType()->getVectorNumElements();
1465  Value *NarrowCond;
1466  if (!match(Cond, m_OneUse(m_ShuffleVector(m_Value(NarrowCond), m_Undef(),
1467  m_Constant()))) ||
1468  NarrowCond->getType()->getVectorNumElements() != NarrowNumElts ||
1469  !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
1470  return nullptr;
1471 
1472  // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
1473  // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
1475  Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getMask());
1476  Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getMask());
1477  return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
1478 }
1479 
1480 /// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
1482  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1483  if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1))
1484  return nullptr;
1485 
1486  Value *X, *Y;
1487  Constant *Mask;
1488  if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask))))
1489  return nullptr;
1490 
1491  // We are extracting a subvector from a shuffle. Remove excess elements from
1492  // the 1st shuffle mask to eliminate the extract.
1493  //
1494  // This transform is conservatively limited to identity extracts because we do
1495  // not allow arbitrary shuffle mask creation as a target-independent transform
1496  // (because we can't guarantee that will lower efficiently).
1497  //
1498  // If the extracting shuffle has an undef mask element, it transfers to the
1499  // new shuffle mask. Otherwise, copy the original mask element. Example:
1500  // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
1501  // shuf X, Y, <C0, undef, C2, undef>
1502  unsigned NumElts = Shuf.getType()->getVectorNumElements();
1503  SmallVector<Constant *, 16> NewMask(NumElts);
1504  assert(NumElts < Mask->getType()->getVectorNumElements() &&
1505  "Identity with extract must have less elements than its inputs");
1506 
1507  for (unsigned i = 0; i != NumElts; ++i) {
1508  Constant *ExtractMaskElt = Shuf.getMask()->getAggregateElement(i);
1509  Constant *MaskElt = Mask->getAggregateElement(i);
1510  NewMask[i] = isa<UndefValue>(ExtractMaskElt) ? ExtractMaskElt : MaskElt;
1511  }
1512  return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1513 }
1514 
1516  Value *LHS = SVI.getOperand(0);
1517  Value *RHS = SVI.getOperand(1);
1518  if (auto *V = SimplifyShuffleVectorInst(
1519  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1520  return replaceInstUsesWith(SVI, V);
1521 
1522  if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
1523  return I;
1524 
1525  if (Instruction *I = narrowVectorSelect(SVI, Builder))
1526  return I;
1527 
1528  unsigned VWidth = SVI.getType()->getVectorNumElements();
1529  APInt UndefElts(VWidth, 0);
1530  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1531  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1532  if (V != &SVI)
1533  return replaceInstUsesWith(SVI, V);
1534  return &SVI;
1535  }
1536 
1538  return I;
1539 
1542  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1543  bool MadeChange = false;
1544 
1545  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1546  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1547  if (LHS == RHS || isa<UndefValue>(LHS)) {
1548  // Remap any references to RHS to use LHS.
1550  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1551  if (Mask[i] < 0) {
1552  Elts.push_back(UndefValue::get(Int32Ty));
1553  continue;
1554  }
1555 
1556  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1557  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1558  Mask[i] = -1; // Turn into undef.
1559  Elts.push_back(UndefValue::get(Int32Ty));
1560  } else {
1561  Mask[i] = Mask[i] % e; // Force to LHS.
1562  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1563  }
1564  }
1565  SVI.setOperand(0, SVI.getOperand(1));
1566  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1567  SVI.setOperand(2, ConstantVector::get(Elts));
1568  LHS = SVI.getOperand(0);
1569  RHS = SVI.getOperand(1);
1570  MadeChange = true;
1571  }
1572 
1573  if (VWidth == LHSWidth) {
1574  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1575  bool isLHSID, isRHSID;
1576  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1577 
1578  // Eliminate identity shuffles.
1579  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1580  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1581  }
1582 
1583  if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) {
1584  Value *V = evaluateInDifferentElementOrder(LHS, Mask);
1585  return replaceInstUsesWith(SVI, V);
1586  }
1587 
1588  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1589  // a non-vector type. We can instead bitcast the original vector followed by
1590  // an extract of the desired element:
1591  //
1592  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1593  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1594  // %1 = bitcast <4 x i8> %sroa to i32
1595  // Becomes:
1596  // %bc = bitcast <16 x i8> %in to <4 x i32>
1597  // %ext = extractelement <4 x i32> %bc, i32 0
1598  //
1599  // If the shuffle is extracting a contiguous range of values from the input
1600  // vector then each use which is a bitcast of the extracted size can be
1601  // replaced. This will work if the vector types are compatible, and the begin
1602  // index is aligned to a value in the casted vector type. If the begin index
1603  // isn't aligned then we can shuffle the original vector (keeping the same
1604  // vector type) before extracting.
1605  //
1606  // This code will bail out if the target type is fundamentally incompatible
1607  // with vectors of the source type.
1608  //
1609  // Example of <16 x i8>, target type i32:
1610  // Index range [4,8): v-----------v Will work.
1611  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1612  // <16 x i8>: | | | | | | | | | | | | | | | | |
1613  // <4 x i32>: | | | | |
1614  // +-----------+-----------+-----------+-----------+
1615  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1616  // Target type i40: ^--------------^ Won't work, bail.
1617  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1618  Value *V = LHS;
1619  unsigned MaskElems = Mask.size();
1620  VectorType *SrcTy = cast<VectorType>(V->getType());
1621  unsigned VecBitWidth = SrcTy->getBitWidth();
1622  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1623  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1624  unsigned SrcNumElems = SrcTy->getNumElements();
1627  for (User *U : SVI.users())
1628  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1629  if (!BC->use_empty())
1630  // Only visit bitcasts that weren't previously handled.
1631  BCs.push_back(BC);
1632  for (BitCastInst *BC : BCs) {
1633  unsigned BegIdx = Mask.front();
1634  Type *TgtTy = BC->getDestTy();
1635  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1636  if (!TgtElemBitWidth)
1637  continue;
1638  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1639  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1640  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1641  if (!VecBitWidthsEqual)
1642  continue;
1643  if (!VectorType::isValidElementType(TgtTy))
1644  continue;
1645  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1646  if (!BegIsAligned) {
1647  // Shuffle the input so [0,NumElements) contains the output, and
1648  // [NumElems,SrcNumElems) is undef.
1649  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1650  UndefValue::get(Int32Ty));
1651  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1652  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1653  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1654  ConstantVector::get(ShuffleMask),
1655  SVI.getName() + ".extract");
1656  BegIdx = 0;
1657  }
1658  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1659  assert(SrcElemsPerTgtElem);
1660  BegIdx /= SrcElemsPerTgtElem;
1661  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1662  auto *NewBC =
1663  BCAlreadyExists
1664  ? NewBCs[CastSrcTy]
1665  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1666  if (!BCAlreadyExists)
1667  NewBCs[CastSrcTy] = NewBC;
1668  auto *Ext = Builder.CreateExtractElement(
1669  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1670  // The shufflevector isn't being replaced: the bitcast that used it
1671  // is. InstCombine will visit the newly-created instructions.
1672  replaceInstUsesWith(*BC, Ext);
1673  MadeChange = true;
1674  }
1675  }
1676 
1677  // If the LHS is a shufflevector itself, see if we can combine it with this
1678  // one without producing an unusual shuffle.
1679  // Cases that might be simplified:
1680  // 1.
1681  // x1=shuffle(v1,v2,mask1)
1682  // x=shuffle(x1,undef,mask)
1683  // ==>
1684  // x=shuffle(v1,undef,newMask)
1685  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1686  // 2.
1687  // x1=shuffle(v1,undef,mask1)
1688  // x=shuffle(x1,x2,mask)
1689  // where v1.size() == mask1.size()
1690  // ==>
1691  // x=shuffle(v1,x2,newMask)
1692  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1693  // 3.
1694  // x2=shuffle(v2,undef,mask2)
1695  // x=shuffle(x1,x2,mask)
1696  // where v2.size() == mask2.size()
1697  // ==>
1698  // x=shuffle(x1,v2,newMask)
1699  // newMask[i] = (mask[i] < x1.size())
1700  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1701  // 4.
1702  // x1=shuffle(v1,undef,mask1)
1703  // x2=shuffle(v2,undef,mask2)
1704  // x=shuffle(x1,x2,mask)
1705  // where v1.size() == v2.size()
1706  // ==>
1707  // x=shuffle(v1,v2,newMask)
1708  // newMask[i] = (mask[i] < x1.size())
1709  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1710  //
1711  // Here we are really conservative:
1712  // we are absolutely afraid of producing a shuffle mask not in the input
1713  // program, because the code gen may not be smart enough to turn a merged
1714  // shuffle into two specific shuffles: it may produce worse code. As such,
1715  // we only merge two shuffles if the result is either a splat or one of the
1716  // input shuffle masks. In this case, merging the shuffles just removes
1717  // one instruction, which we know is safe. This is good for things like
1718  // turning: (splat(splat)) -> splat, or
1719  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1720  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1721  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1722  if (LHSShuffle)
1723  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1724  LHSShuffle = nullptr;
1725  if (RHSShuffle)
1726  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1727  RHSShuffle = nullptr;
1728  if (!LHSShuffle && !RHSShuffle)
1729  return MadeChange ? &SVI : nullptr;
1730 
1731  Value* LHSOp0 = nullptr;
1732  Value* LHSOp1 = nullptr;
1733  Value* RHSOp0 = nullptr;
1734  unsigned LHSOp0Width = 0;
1735  unsigned RHSOp0Width = 0;
1736  if (LHSShuffle) {
1737  LHSOp0 = LHSShuffle->getOperand(0);
1738  LHSOp1 = LHSShuffle->getOperand(1);
1739  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1740  }
1741  if (RHSShuffle) {
1742  RHSOp0 = RHSShuffle->getOperand(0);
1743  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1744  }
1745  Value* newLHS = LHS;
1746  Value* newRHS = RHS;
1747  if (LHSShuffle) {
1748  // case 1
1749  if (isa<UndefValue>(RHS)) {
1750  newLHS = LHSOp0;
1751  newRHS = LHSOp1;
1752  }
1753  // case 2 or 4
1754  else if (LHSOp0Width == LHSWidth) {
1755  newLHS = LHSOp0;
1756  }
1757  }
1758  // case 3 or 4
1759  if (RHSShuffle && RHSOp0Width == LHSWidth) {
1760  newRHS = RHSOp0;
1761  }
1762  // case 4
1763  if (LHSOp0 == RHSOp0) {
1764  newLHS = LHSOp0;
1765  newRHS = nullptr;
1766  }
1767 
1768  if (newLHS == LHS && newRHS == RHS)
1769  return MadeChange ? &SVI : nullptr;
1770 
1771  SmallVector<int, 16> LHSMask;
1772  SmallVector<int, 16> RHSMask;
1773  if (newLHS != LHS)
1774  LHSMask = LHSShuffle->getShuffleMask();
1775  if (RHSShuffle && newRHS != RHS)
1776  RHSMask = RHSShuffle->getShuffleMask();
1777 
1778  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1779  SmallVector<int, 16> newMask;
1780  bool isSplat = true;
1781  int SplatElt = -1;
1782  // Create a new mask for the new ShuffleVectorInst so that the new
1783  // ShuffleVectorInst is equivalent to the original one.
1784  for (unsigned i = 0; i < VWidth; ++i) {
1785  int eltMask;
1786  if (Mask[i] < 0) {
1787  // This element is an undef value.
1788  eltMask = -1;
1789  } else if (Mask[i] < (int)LHSWidth) {
1790  // This element is from left hand side vector operand.
1791  //
1792  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1793  // new mask value for the element.
1794  if (newLHS != LHS) {
1795  eltMask = LHSMask[Mask[i]];
1796  // If the value selected is an undef value, explicitly specify it
1797  // with a -1 mask value.
1798  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1799  eltMask = -1;
1800  } else
1801  eltMask = Mask[i];
1802  } else {
1803  // This element is from right hand side vector operand
1804  //
1805  // If the value selected is an undef value, explicitly specify it
1806  // with a -1 mask value. (case 1)
1807  if (isa<UndefValue>(RHS))
1808  eltMask = -1;
1809  // If RHS is going to be replaced (case 3 or 4), calculate the
1810  // new mask value for the element.
1811  else if (newRHS != RHS) {
1812  eltMask = RHSMask[Mask[i]-LHSWidth];
1813  // If the value selected is an undef value, explicitly specify it
1814  // with a -1 mask value.
1815  if (eltMask >= (int)RHSOp0Width) {
1816  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1817  && "should have been check above");
1818  eltMask = -1;
1819  }
1820  } else
1821  eltMask = Mask[i]-LHSWidth;
1822 
1823  // If LHS's width is changed, shift the mask value accordingly.
1824  // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
1825  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1826  // If newRHS == newLHS, we want to remap any references from newRHS to
1827  // newLHS so that we can properly identify splats that may occur due to
1828  // obfuscation across the two vectors.
1829  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1830  eltMask += newLHSWidth;
1831  }
1832 
1833  // Check if this could still be a splat.
1834  if (eltMask >= 0) {
1835  if (SplatElt >= 0 && SplatElt != eltMask)
1836  isSplat = false;
1837  SplatElt = eltMask;
1838  }
1839 
1840  newMask.push_back(eltMask);
1841  }
1842 
1843  // If the result mask is equal to one of the original shuffle masks,
1844  // or is a splat, do the replacement.
1845  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1847  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1848  if (newMask[i] < 0) {
1849  Elts.push_back(UndefValue::get(Int32Ty));
1850  } else {
1851  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1852  }
1853  }
1854  if (!newRHS)
1855  newRHS = UndefValue::get(newLHS->getType());
1856  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1857  }
1858 
1859  // If the result mask is an identity, replace uses of this instruction with
1860  // corresponding argument.
1861  bool isLHSID, isRHSID;
1862  recognizeIdentityMask(newMask, isLHSID, isRHSID);
1863  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1864  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1865 
1866  return MadeChange ? &SVI : nullptr;
1867 }
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...
bool isIdentityWithExtract() const
Return true if this shuffle extracts the first N elements of exactly one source vector.
uint64_t CallInst * C
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:675
class_match< UndefValue > m_Undef()
Match an arbitrary undef constant.
Definition: PatternMatch.h:88
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.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:562
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
static Value * evaluateInDifferentElementOrder(Value *V, ArrayRef< int > Mask)
static Instruction * foldSelectShuffle(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder, const DataLayout &DL)
Try to fold shuffles that are the equivalent of a vector select.
Value * findScalarElement(Value *V, unsigned EltNo)
Given a vector and an element number, see if the scalar value is already around as a register...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:355
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:1309
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:869
static Instruction * foldIdentityExtractShuffle(ShuffleVectorInst &Shuf)
Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElement(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
This instruction constructs a fixed permutation of two input vectors.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
ThreeOps_match< V1_t, V2_t, Mask_t, Instruction::ShuffleVector > m_ShuffleVector(const V1_t &v1, const V2_t &v2, const Mask_t &m)
Matches ShuffleVectorInst.
static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI, SmallVector< int, 16 > &Mask)
Hexagon Common GEP
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
static Instruction * hoistInsEltConst(InsertElementInst &InsElt2, InstCombiner::BuilderTy &Builder)
If we have an insertelement instruction feeding into another insertelement and the 2nd is inserting a...
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL)
Binops may be transformed into binops with different opcodes and operands.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h: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:1397
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:392
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
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:743
The core instruction combiner logic.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs...
bool MaskedValueIsZero(const Value *V, const APInt &Mask, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if &#39;V & Mask&#39; is known to be zero.
uint64_t getNumElements() const
Definition: DerivedTypes.h:359
BinopElts(BinaryOperator::BinaryOps Opc=(BinaryOperator::BinaryOps) 0, Value *V0=nullptr, Value *V1=nullptr)
This file implements a class to represent arbitrary precision integral constant values and operations...
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:423
static Instruction * foldInsSequenceIntoBroadcast(InsertElementInst &InsElt)
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1641
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
static bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
Definition: Type.cpp:608
This instruction compares its operands according to the predicate given to the constructor.
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
This class represents a no-op cast from one type to another.
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)
These are the ingredients in an alternate form binary operator as described below.
static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, SmallVectorImpl< Constant *> &Mask)
If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mas...
bool isSelect() const
Return true if this shuffle chooses elements from its source vectors without lane crossings and all o...
VectorType * getType() const
Overload to return most specific vector type.
This class represents a truncation of integer types.
Value * getOperand(unsigned i) const
Definition: User.h:170
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:338
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return &#39;this&#39;.
Definition: Type.h:304
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:843
OneUse_match< T > m_OneUse(const T &SubPattern)
Definition: PatternMatch.h:63
This instruction inserts a single (scalar) element into a VectorType value.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:177
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
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:499
static Constant * getShuffleVector(Constant *V1, Constant *V2, Constant *Mask, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2096
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:1049
This instruction compares its operands according to the predicate given to the constructor.
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2274
op_range operands()
Definition: User.h:238
self_iterator getIterator()
Definition: ilist_node.h:82
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:75
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:1392
size_t size() const
Definition: SmallVector.h:53
static wasm::ValType getType(const TargetRegisterClass *RC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
bool isExact() const
Determine whether the exact flag is set.
static int getMaskValue(const Constant *Mask, unsigned Elt)
Return the shuffle mask value for the specified element of the mask.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Value * CreateTrunc(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1564
Value * SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q)
Given operands for a ShuffleVectorInst, fold the result or return null.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:88
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
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type...
Definition: Type.cpp:130
BinaryOperator::BinaryOps Opcode
bool containsUndefElement() const
Return true if this is a vector constant that includes any undefined elements.
Definition: Constants.cpp:257
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:1946
static Instruction * foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf)
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
Definition: Type.cpp:180
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:1960
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:621
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:70
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:400
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:186
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.
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2257
static bool canEvaluateShuffled(Value *V, ArrayRef< int > Mask, unsigned Depth=5)
Return true if we can evaluate the specified expression tree if the vector elements were shuffled in ...
static Instruction * foldBitcastExtElt(ExtractElementInst &Ext, InstCombiner::BuilderTy &Builder, bool IsBigEndian)
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:115
static Instruction * narrowVectorSelect(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder)
Match a shuffle-select-shuffle pattern where the shuffles are widening and narrowing (concatenating w...
ArrayRef< unsigned > getIndices() const
LLVM Value Representation.
Definition: Value.h: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
Value * CreateLShr(Value *LHS, Value *RHS, const Twine &Name="", bool isExact=false)
Definition: IRBuilder.h:1084
Type * getElementType() const
Definition: DerivedTypes.h:360
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
bool isIntDivRem() const
Definition: Instruction.h:131
static bool isSplat(ArrayRef< Value *> VL)
static void recognizeIdentityMask(const SmallVectorImpl< int > &Mask, bool &isLHSID, bool &isRHSID)
static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl< Constant *> &Mask, Value *PermittedRHS, InstCombiner &IC)
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
VectorType * getType() const
Overload to return most specific vector type.
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1056
IntegerType * Int32Ty
User * user_back()
Definition: Value.h:386
const BasicBlock * getParent() const
Definition: Instruction.h:67
This instruction inserts a struct field of array element value into an aggregate value.