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 //
52 // FIXME: It's possible to create more instructions that previously existed.
53 static bool cheapToScalarize(Value *V, bool isConstant) {
54  if (Constant *C = dyn_cast<Constant>(V)) {
55  if (isConstant) return true;
56 
57  // If all elts are the same, we can extract it and use any of the values.
58  if (Constant *Op0 = C->getAggregateElement(0U)) {
59  for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e;
60  ++i)
61  if (C->getAggregateElement(i) != Op0)
62  return false;
63  return true;
64  }
65  }
67  if (!I) return false;
68 
69  // Insert element gets simplified to the inserted element or is deleted if
70  // this is constant idx extract element and its a constant idx insertelt.
71  if (I->getOpcode() == Instruction::InsertElement && isConstant &&
72  isa<ConstantInt>(I->getOperand(2)))
73  return true;
74  if (I->getOpcode() == Instruction::Load && I->hasOneUse())
75  return true;
76  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
77  if (BO->hasOneUse() &&
78  (cheapToScalarize(BO->getOperand(0), isConstant) ||
79  cheapToScalarize(BO->getOperand(1), isConstant)))
80  return true;
81  if (CmpInst *CI = dyn_cast<CmpInst>(I))
82  if (CI->hasOneUse() &&
83  (cheapToScalarize(CI->getOperand(0), isConstant) ||
84  cheapToScalarize(CI->getOperand(1), isConstant)))
85  return true;
86 
87  return false;
88 }
89 
90 // If we have a PHI node with a vector type that is only used to feed
91 // itself and be an operand of extractelement at a constant location,
92 // try to replace the PHI of the vector type with a PHI of a scalar type.
93 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
95  // The users we want the PHI to have are:
96  // 1) The EI ExtractElement (we already know this)
97  // 2) Possibly more ExtractElements with the same index.
98  // 3) Another operand, which will feed back into the PHI.
99  Instruction *PHIUser = nullptr;
100  for (auto U : PN->users()) {
101  if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
102  if (EI.getIndexOperand() == EU->getIndexOperand())
103  Extracts.push_back(EU);
104  else
105  return nullptr;
106  } else if (!PHIUser) {
107  PHIUser = cast<Instruction>(U);
108  } else {
109  return nullptr;
110  }
111  }
112 
113  if (!PHIUser)
114  return nullptr;
115 
116  // Verify that this PHI user has one use, which is the PHI itself,
117  // and that it is a binary operation which is cheap to scalarize.
118  // otherwise return nullptr.
119  if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
120  !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
121  return nullptr;
122 
123  // Create a scalar PHI node that will replace the vector PHI node
124  // just before the current PHI node.
125  PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
126  PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
127  // Scalarize each PHI operand.
128  for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
129  Value *PHIInVal = PN->getIncomingValue(i);
130  BasicBlock *inBB = PN->getIncomingBlock(i);
131  Value *Elt = EI.getIndexOperand();
132  // If the operand is the PHI induction variable:
133  if (PHIInVal == PHIUser) {
134  // Scalarize the binary operation. Its first operand is the
135  // scalar PHI, and the second operand is extracted from the other
136  // vector operand.
137  BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
138  unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
139  Value *Op = InsertNewInstWith(
140  ExtractElementInst::Create(B0->getOperand(opId), Elt,
141  B0->getOperand(opId)->getName() + ".Elt"),
142  *B0);
143  Value *newPHIUser = InsertNewInstWith(
145  scalarPHI, Op, B0), *B0);
146  scalarPHI->addIncoming(newPHIUser, inBB);
147  } else {
148  // Scalarize PHI input:
149  Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
150  // Insert the new instruction into the predecessor basic block.
151  Instruction *pos = dyn_cast<Instruction>(PHIInVal);
152  BasicBlock::iterator InsertPos;
153  if (pos && !isa<PHINode>(pos)) {
154  InsertPos = ++pos->getIterator();
155  } else {
156  InsertPos = inBB->getFirstInsertionPt();
157  }
158 
159  InsertNewInstWith(newEI, *InsertPos);
160 
161  scalarPHI->addIncoming(newEI, inBB);
162  }
163  }
164 
165  for (auto E : Extracts)
166  replaceInstUsesWith(*E, scalarPHI);
167 
168  return &EI;
169 }
170 
172  InstCombiner::BuilderTy &Builder,
173  bool IsBigEndian) {
174  Value *X;
175  uint64_t ExtIndexC;
176  if (!match(Ext.getVectorOperand(), m_BitCast(m_Value(X))) ||
177  !X->getType()->isVectorTy() ||
178  !match(Ext.getIndexOperand(), m_ConstantInt(ExtIndexC)))
179  return nullptr;
180 
181  // If this extractelement is using a bitcast from a vector of the same number
182  // of elements, see if we can find the source element from the source vector:
183  // extelt (bitcast VecX), IndexC --> bitcast X[IndexC]
184  Type *SrcTy = X->getType();
185  Type *DestTy = Ext.getType();
186  unsigned NumSrcElts = SrcTy->getVectorNumElements();
187  unsigned NumElts = Ext.getVectorOperandType()->getNumElements();
188  if (NumSrcElts == NumElts)
189  if (Value *Elt = findScalarElement(X, ExtIndexC))
190  return new BitCastInst(Elt, DestTy);
191 
192  // If the source elements are wider than the destination, try to shift and
193  // truncate a subset of scalar bits of an insert op.
194  if (NumSrcElts < NumElts) {
195  Value *Scalar;
196  uint64_t InsIndexC;
197  if (!match(X, m_InsertElement(m_Value(), m_Value(Scalar),
198  m_ConstantInt(InsIndexC))))
199  return nullptr;
200 
201  // The extract must be from the subset of vector elements that we inserted
202  // into. Example: if we inserted element 1 of a <2 x i64> and we are
203  // extracting an i16 (narrowing ratio = 4), then this extract must be from 1
204  // of elements 4-7 of the bitcasted vector.
205  unsigned NarrowingRatio = NumElts / NumSrcElts;
206  if (ExtIndexC / NarrowingRatio != InsIndexC)
207  return nullptr;
208 
209  // We are extracting part of the original scalar. How that scalar is
210  // inserted into the vector depends on the endian-ness. Example:
211  // Vector Byte Elt Index: 0 1 2 3 4 5 6 7
212  // +--+--+--+--+--+--+--+--+
213  // inselt <2 x i32> V, <i32> S, 1: |V0|V1|V2|V3|S0|S1|S2|S3|
214  // extelt <4 x i16> V', 3: | |S2|S3|
215  // +--+--+--+--+--+--+--+--+
216  // If this is little-endian, S2|S3 are the MSB of the 32-bit 'S' value.
217  // If this is big-endian, S2|S3 are the LSB of the 32-bit 'S' value.
218  // In this example, we must right-shift little-endian. Big-endian is just a
219  // truncate.
220  unsigned Chunk = ExtIndexC % NarrowingRatio;
221  if (IsBigEndian)
222  Chunk = NarrowingRatio - 1 - Chunk;
223 
224  // Bail out if this is an FP vector to FP vector sequence. That would take
225  // more instructions than we started with unless there is no shift, and it
226  // may not be handled as well in the backend.
227  bool NeedSrcBitcast = SrcTy->getScalarType()->isFloatingPointTy();
228  bool NeedDestBitcast = DestTy->isFloatingPointTy();
229  if (NeedSrcBitcast && NeedDestBitcast)
230  return nullptr;
231 
232  unsigned SrcWidth = SrcTy->getScalarSizeInBits();
233  unsigned DestWidth = DestTy->getPrimitiveSizeInBits();
234  unsigned ShAmt = Chunk * DestWidth;
235 
236  // TODO: This limitation is more strict than necessary. We could sum the
237  // number of new instructions and subtract the number eliminated to know if
238  // we can proceed.
239  if (!X->hasOneUse() || !Ext.getVectorOperand()->hasOneUse())
240  if (NeedSrcBitcast || NeedDestBitcast)
241  return nullptr;
242 
243  if (NeedSrcBitcast) {
244  Type *SrcIntTy = IntegerType::getIntNTy(Scalar->getContext(), SrcWidth);
245  Scalar = Builder.CreateBitCast(Scalar, SrcIntTy);
246  }
247 
248  if (ShAmt) {
249  // Bail out if we could end with more instructions than we started with.
250  if (!Ext.getVectorOperand()->hasOneUse())
251  return nullptr;
252  Scalar = Builder.CreateLShr(Scalar, ShAmt);
253  }
254 
255  if (NeedDestBitcast) {
256  Type *DestIntTy = IntegerType::getIntNTy(Scalar->getContext(), DestWidth);
257  return new BitCastInst(Builder.CreateTrunc(Scalar, DestIntTy), DestTy);
258  }
259  return new TruncInst(Scalar, DestTy);
260  }
261 
262  return nullptr;
263 }
264 
266  Value *SrcVec = EI.getVectorOperand();
267  Value *Index = EI.getIndexOperand();
268  if (Value *V = SimplifyExtractElementInst(SrcVec, Index,
269  SQ.getWithInstruction(&EI)))
270  return replaceInstUsesWith(EI, V);
271 
272  // If extracting a specified index from the vector, see if we can recursively
273  // find a previously computed scalar that was inserted into the vector.
274  auto *IndexC = dyn_cast<ConstantInt>(Index);
275  if (IndexC) {
276  unsigned NumElts = EI.getVectorOperandType()->getNumElements();
277 
278  // InstSimplify should handle cases where the index is invalid.
279  if (!IndexC->getValue().ule(NumElts))
280  return nullptr;
281 
282  // This instruction only demands the single element from the input vector.
283  // If the input vector has a single use, simplify it based on this use
284  // property.
285  if (SrcVec->hasOneUse() && NumElts != 1) {
286  APInt UndefElts(NumElts, 0);
287  APInt DemandedElts(NumElts, 0);
288  DemandedElts.setBit(IndexC->getZExtValue());
289  if (Value *V = SimplifyDemandedVectorElts(SrcVec, DemandedElts,
290  UndefElts)) {
291  EI.setOperand(0, V);
292  return &EI;
293  }
294  }
295 
296  if (Instruction *I = foldBitcastExtElt(EI, Builder, DL.isBigEndian()))
297  return I;
298 
299  // If there's a vector PHI feeding a scalar use through this extractelement
300  // instruction, try to scalarize the PHI.
301  if (auto *Phi = dyn_cast<PHINode>(SrcVec))
302  if (Instruction *ScalarPHI = scalarizePHI(EI, Phi))
303  return ScalarPHI;
304  }
305 
306  BinaryOperator *BO;
307  if (match(SrcVec, m_BinOp(BO)) && cheapToScalarize(SrcVec, IndexC)) {
308  // extelt (binop X, Y), Index --> binop (extelt X, Index), (extelt Y, Index)
309  Value *X = BO->getOperand(0), *Y = BO->getOperand(1);
310  Value *E0 = Builder.CreateExtractElement(X, Index);
311  Value *E1 = Builder.CreateExtractElement(Y, Index);
312  return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(), E0, E1, BO);
313  }
314 
315  Value *X, *Y;
316  CmpInst::Predicate Pred;
317  if (match(SrcVec, m_Cmp(Pred, m_Value(X), m_Value(Y))) &&
318  cheapToScalarize(SrcVec, IndexC)) {
319  // extelt (cmp X, Y), Index --> cmp (extelt X, Index), (extelt Y, Index)
320  Value *E0 = Builder.CreateExtractElement(X, Index);
321  Value *E1 = Builder.CreateExtractElement(Y, Index);
322  return CmpInst::Create(cast<CmpInst>(SrcVec)->getOpcode(), Pred, E0, E1);
323  }
324 
325  if (auto *I = dyn_cast<Instruction>(SrcVec)) {
326  if (auto *IE = dyn_cast<InsertElementInst>(I)) {
327  // Extracting the inserted element?
328  if (IE->getOperand(2) == Index)
329  return replaceInstUsesWith(EI, IE->getOperand(1));
330  // If the inserted and extracted elements are constants, they must not
331  // be the same value, extract from the pre-inserted value instead.
332  if (isa<Constant>(IE->getOperand(2)) && IndexC) {
333  Worklist.AddValue(SrcVec);
334  EI.setOperand(0, IE->getOperand(0));
335  return &EI;
336  }
337  } else if (auto *SVI = dyn_cast<ShuffleVectorInst>(I)) {
338  // If this is extracting an element from a shufflevector, figure out where
339  // it came from and extract from the appropriate input element instead.
340  if (auto *Elt = dyn_cast<ConstantInt>(Index)) {
341  int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
342  Value *Src;
343  unsigned LHSWidth =
344  SVI->getOperand(0)->getType()->getVectorNumElements();
345 
346  if (SrcIdx < 0)
347  return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
348  if (SrcIdx < (int)LHSWidth)
349  Src = SVI->getOperand(0);
350  else {
351  SrcIdx -= LHSWidth;
352  Src = SVI->getOperand(1);
353  }
355  return ExtractElementInst::Create(Src,
356  ConstantInt::get(Int32Ty,
357  SrcIdx, false));
358  }
359  } else if (auto *CI = dyn_cast<CastInst>(I)) {
360  // Canonicalize extractelement(cast) -> cast(extractelement).
361  // Bitcasts can change the number of vector elements, and they cost
362  // nothing.
363  if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
364  Value *EE = Builder.CreateExtractElement(CI->getOperand(0), Index);
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 both
880  // indexes are constant, try to turn this into a shuffle.
881  uint64_t InsertedIdx, ExtractedIdx;
882  Value *ExtVecOp;
883  if (match(IdxOp, m_ConstantInt(InsertedIdx)) &&
884  match(ScalarOp, m_ExtractElement(m_Value(ExtVecOp),
885  m_ConstantInt(ExtractedIdx)))) {
886  unsigned NumInsertVectorElts = IE.getType()->getNumElements();
887  unsigned NumExtractVectorElts = ExtVecOp->getType()->getVectorNumElements();
888  if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
889  return replaceInstUsesWith(IE, VecOp);
890 
891  if (InsertedIdx >= NumInsertVectorElts) // Out of range insert.
892  return replaceInstUsesWith(IE, UndefValue::get(IE.getType()));
893 
894  // If we are extracting a value from a vector, then inserting it right
895  // back into the same place, just use the input vector.
896  if (ExtVecOp == VecOp && ExtractedIdx == InsertedIdx)
897  return replaceInstUsesWith(IE, VecOp);
898 
899  // TODO: Looking at the user(s) to determine if this insert is a
900  // fold-to-shuffle opportunity does not match the usual instcombine
901  // constraints. We should decide if the transform is worthy based only
902  // on this instruction and its operands, but that may not work currently.
903  //
904  // Here, we are trying to avoid creating shuffles before reaching
905  // the end of a chain of extract-insert pairs. This is complicated because
906  // we do not generally form arbitrary shuffle masks in instcombine
907  // (because those may codegen poorly), but collectShuffleElements() does
908  // exactly that.
909  //
910  // The rules for determining what is an acceptable target-independent
911  // shuffle mask are fuzzy because they evolve based on the backend's
912  // capabilities and real-world impact.
913  auto isShuffleRootCandidate = [](InsertElementInst &Insert) {
914  if (!Insert.hasOneUse())
915  return true;
916  auto *InsertUser = dyn_cast<InsertElementInst>(Insert.user_back());
917  if (!InsertUser)
918  return true;
919  return false;
920  };
921 
922  // Try to form a shuffle from a chain of extract-insert ops.
923  if (isShuffleRootCandidate(IE)) {
925  ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
926 
927  // The proposed shuffle may be trivial, in which case we shouldn't
928  // perform the combine.
929  if (LR.first != &IE && LR.second != &IE) {
930  // We now have a shuffle of LHS, RHS, Mask.
931  if (LR.second == nullptr)
932  LR.second = UndefValue::get(LR.first->getType());
933  return new ShuffleVectorInst(LR.first, LR.second,
934  ConstantVector::get(Mask));
935  }
936  }
937  }
938 
939  unsigned VWidth = VecOp->getType()->getVectorNumElements();
940  APInt UndefElts(VWidth, 0);
941  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
942  if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
943  if (V != &IE)
944  return replaceInstUsesWith(IE, V);
945  return &IE;
946  }
947 
949  return Shuf;
950 
951  if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
952  return NewInsElt;
953 
954  // Turn a sequence of inserts that broadcasts a scalar into a single
955  // insert + shufflevector.
956  if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE))
957  return Broadcast;
958 
959  return nullptr;
960 }
961 
962 /// Return true if we can evaluate the specified expression tree if the vector
963 /// elements were shuffled in a different order.
965  unsigned Depth = 5) {
966  // We can always reorder the elements of a constant.
967  if (isa<Constant>(V))
968  return true;
969 
970  // We won't reorder vector arguments. No IPO here.
972  if (!I) return false;
973 
974  // Two users may expect different orders of the elements. Don't try it.
975  if (!I->hasOneUse())
976  return false;
977 
978  if (Depth == 0) return false;
979 
980  switch (I->getOpcode()) {
981  case Instruction::Add:
982  case Instruction::FAdd:
983  case Instruction::Sub:
984  case Instruction::FSub:
985  case Instruction::Mul:
986  case Instruction::FMul:
987  case Instruction::UDiv:
988  case Instruction::SDiv:
989  case Instruction::FDiv:
990  case Instruction::URem:
991  case Instruction::SRem:
992  case Instruction::FRem:
993  case Instruction::Shl:
994  case Instruction::LShr:
995  case Instruction::AShr:
996  case Instruction::And:
997  case Instruction::Or:
998  case Instruction::Xor:
999  case Instruction::ICmp:
1000  case Instruction::FCmp:
1001  case Instruction::Trunc:
1002  case Instruction::ZExt:
1003  case Instruction::SExt:
1004  case Instruction::FPToUI:
1005  case Instruction::FPToSI:
1006  case Instruction::UIToFP:
1007  case Instruction::SIToFP:
1008  case Instruction::FPTrunc:
1009  case Instruction::FPExt:
1010  case Instruction::GetElementPtr: {
1011  // Bail out if we would create longer vector ops. We could allow creating
1012  // longer vector ops, but that may result in more expensive codegen. We
1013  // would also need to limit the transform to avoid undefined behavior for
1014  // integer div/rem.
1015  Type *ITy = I->getType();
1016  if (ITy->isVectorTy() && Mask.size() > ITy->getVectorNumElements())
1017  return false;
1018  for (Value *Operand : I->operands()) {
1019  if (!canEvaluateShuffled(Operand, Mask, Depth - 1))
1020  return false;
1021  }
1022  return true;
1023  }
1024  case Instruction::InsertElement: {
1026  if (!CI) return false;
1027  int ElementNumber = CI->getLimitedValue();
1028 
1029  // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
1030  // can't put an element into multiple indices.
1031  bool SeenOnce = false;
1032  for (int i = 0, e = Mask.size(); i != e; ++i) {
1033  if (Mask[i] == ElementNumber) {
1034  if (SeenOnce)
1035  return false;
1036  SeenOnce = true;
1037  }
1038  }
1039  return canEvaluateShuffled(I->getOperand(0), Mask, Depth - 1);
1040  }
1041  }
1042  return false;
1043 }
1044 
1045 /// Rebuild a new instruction just like 'I' but with the new operands given.
1046 /// In the event of type mismatch, the type of the operands is correct.
1048  // We don't want to use the IRBuilder here because we want the replacement
1049  // instructions to appear next to 'I', not the builder's insertion point.
1050  switch (I->getOpcode()) {
1051  case Instruction::Add:
1052  case Instruction::FAdd:
1053  case Instruction::Sub:
1054  case Instruction::FSub:
1055  case Instruction::Mul:
1056  case Instruction::FMul:
1057  case Instruction::UDiv:
1058  case Instruction::SDiv:
1059  case Instruction::FDiv:
1060  case Instruction::URem:
1061  case Instruction::SRem:
1062  case Instruction::FRem:
1063  case Instruction::Shl:
1064  case Instruction::LShr:
1065  case Instruction::AShr:
1066  case Instruction::And:
1067  case Instruction::Or:
1068  case Instruction::Xor: {
1069  BinaryOperator *BO = cast<BinaryOperator>(I);
1070  assert(NewOps.size() == 2 && "binary operator with #ops != 2");
1071  BinaryOperator *New =
1072  BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
1073  NewOps[0], NewOps[1], "", BO);
1074  if (isa<OverflowingBinaryOperator>(BO)) {
1075  New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
1076  New->setHasNoSignedWrap(BO->hasNoSignedWrap());
1077  }
1078  if (isa<PossiblyExactOperator>(BO)) {
1079  New->setIsExact(BO->isExact());
1080  }
1081  if (isa<FPMathOperator>(BO))
1082  New->copyFastMathFlags(I);
1083  return New;
1084  }
1085  case Instruction::ICmp:
1086  assert(NewOps.size() == 2 && "icmp with #ops != 2");
1087  return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
1088  NewOps[0], NewOps[1]);
1089  case Instruction::FCmp:
1090  assert(NewOps.size() == 2 && "fcmp with #ops != 2");
1091  return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
1092  NewOps[0], NewOps[1]);
1093  case Instruction::Trunc:
1094  case Instruction::ZExt:
1095  case Instruction::SExt:
1096  case Instruction::FPToUI:
1097  case Instruction::FPToSI:
1098  case Instruction::UIToFP:
1099  case Instruction::SIToFP:
1100  case Instruction::FPTrunc:
1101  case Instruction::FPExt: {
1102  // It's possible that the mask has a different number of elements from
1103  // the original cast. We recompute the destination type to match the mask.
1104  Type *DestTy =
1106  NewOps[0]->getType()->getVectorNumElements());
1107  assert(NewOps.size() == 1 && "cast with #ops != 1");
1108  return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
1109  "", I);
1110  }
1111  case Instruction::GetElementPtr: {
1112  Value *Ptr = NewOps[0];
1113  ArrayRef<Value*> Idx = NewOps.slice(1);
1115  cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1116  GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1117  return GEP;
1118  }
1119  }
1120  llvm_unreachable("failed to rebuild vector instructions");
1121 }
1122 
1124  // Mask.size() does not need to be equal to the number of vector elements.
1125 
1126  assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1127  Type *EltTy = V->getType()->getScalarType();
1128  Type *I32Ty = IntegerType::getInt32Ty(V->getContext());
1129  if (isa<UndefValue>(V))
1130  return UndefValue::get(VectorType::get(EltTy, Mask.size()));
1131 
1132  if (isa<ConstantAggregateZero>(V))
1133  return ConstantAggregateZero::get(VectorType::get(EltTy, Mask.size()));
1134 
1135  if (Constant *C = dyn_cast<Constant>(V)) {
1136  SmallVector<Constant *, 16> MaskValues;
1137  for (int i = 0, e = Mask.size(); i != e; ++i) {
1138  if (Mask[i] == -1)
1139  MaskValues.push_back(UndefValue::get(I32Ty));
1140  else
1141  MaskValues.push_back(ConstantInt::get(I32Ty, Mask[i]));
1142  }
1144  ConstantVector::get(MaskValues));
1145  }
1146 
1147  Instruction *I = cast<Instruction>(V);
1148  switch (I->getOpcode()) {
1149  case Instruction::Add:
1150  case Instruction::FAdd:
1151  case Instruction::Sub:
1152  case Instruction::FSub:
1153  case Instruction::Mul:
1154  case Instruction::FMul:
1155  case Instruction::UDiv:
1156  case Instruction::SDiv:
1157  case Instruction::FDiv:
1158  case Instruction::URem:
1159  case Instruction::SRem:
1160  case Instruction::FRem:
1161  case Instruction::Shl:
1162  case Instruction::LShr:
1163  case Instruction::AShr:
1164  case Instruction::And:
1165  case Instruction::Or:
1166  case Instruction::Xor:
1167  case Instruction::ICmp:
1168  case Instruction::FCmp:
1169  case Instruction::Trunc:
1170  case Instruction::ZExt:
1171  case Instruction::SExt:
1172  case Instruction::FPToUI:
1173  case Instruction::FPToSI:
1174  case Instruction::UIToFP:
1175  case Instruction::SIToFP:
1176  case Instruction::FPTrunc:
1177  case Instruction::FPExt:
1178  case Instruction::Select:
1179  case Instruction::GetElementPtr: {
1180  SmallVector<Value*, 8> NewOps;
1181  bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1182  for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1183  Value *V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1184  NewOps.push_back(V);
1185  NeedsRebuild |= (V != I->getOperand(i));
1186  }
1187  if (NeedsRebuild) {
1188  return buildNew(I, NewOps);
1189  }
1190  return I;
1191  }
1192  case Instruction::InsertElement: {
1193  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1194 
1195  // The insertelement was inserting at Element. Figure out which element
1196  // that becomes after shuffling. The answer is guaranteed to be unique
1197  // by CanEvaluateShuffled.
1198  bool Found = false;
1199  int Index = 0;
1200  for (int e = Mask.size(); Index != e; ++Index) {
1201  if (Mask[Index] == Element) {
1202  Found = true;
1203  break;
1204  }
1205  }
1206 
1207  // If element is not in Mask, no need to handle the operand 1 (element to
1208  // be inserted). Just evaluate values in operand 0 according to Mask.
1209  if (!Found)
1210  return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1211 
1212  Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1213  return InsertElementInst::Create(V, I->getOperand(1),
1214  ConstantInt::get(I32Ty, Index), "", I);
1215  }
1216  }
1217  llvm_unreachable("failed to reorder elements of vector instruction!");
1218 }
1219 
1221  bool &isLHSID, bool &isRHSID) {
1222  isLHSID = isRHSID = true;
1223 
1224  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1225  if (Mask[i] < 0) continue; // Ignore undef values.
1226  // Is this an identity shuffle of the LHS value?
1227  isLHSID &= (Mask[i] == (int)i);
1228 
1229  // Is this an identity shuffle of the RHS value?
1230  isRHSID &= (Mask[i]-e == i);
1231  }
1232 }
1233 
1234 // Returns true if the shuffle is extracting a contiguous range of values from
1235 // LHS, for example:
1236 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1237 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1238 // Shuffles to: |EE|FF|GG|HH|
1239 // +--+--+--+--+
1242  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1243  unsigned MaskElems = Mask.size();
1244  unsigned BegIdx = Mask.front();
1245  unsigned EndIdx = Mask.back();
1246  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1247  return false;
1248  for (unsigned I = 0; I != MaskElems; ++I)
1249  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1250  return false;
1251  return true;
1252 }
1253 
1254 /// These are the ingredients in an alternate form binary operator as described
1255 /// below.
1256 struct BinopElts {
1261  Value *V0 = nullptr, Value *V1 = nullptr) :
1262  Opcode(Opc), Op0(V0), Op1(V1) {}
1263  operator bool() const { return Opcode != 0; }
1264 };
1265 
1266 /// Binops may be transformed into binops with different opcodes and operands.
1267 /// Reverse the usual canonicalization to enable folds with the non-canonical
1268 /// form of the binop. If a transform is possible, return the elements of the
1269 /// new binop. If not, return invalid elements.
1271  Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1272  Type *Ty = BO->getType();
1273  switch (BO->getOpcode()) {
1274  case Instruction::Shl: {
1275  // shl X, C --> mul X, (1 << C)
1276  Constant *C;
1277  if (match(BO1, m_Constant(C))) {
1278  Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1279  return { Instruction::Mul, BO0, ShlOne };
1280  }
1281  break;
1282  }
1283  case Instruction::Or: {
1284  // or X, C --> add X, C (when X and C have no common bits set)
1285  const APInt *C;
1286  if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1287  return { Instruction::Add, BO0, BO1 };
1288  break;
1289  }
1290  default:
1291  break;
1292  }
1293  return {};
1294 }
1295 
1297  assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1298 
1299  // Are we shuffling together some value and that same value after it has been
1300  // modified by a binop with a constant?
1301  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1302  Constant *C;
1303  bool Op0IsBinop;
1304  if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1305  Op0IsBinop = true;
1306  else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1307  Op0IsBinop = false;
1308  else
1309  return nullptr;
1310 
1311  // The identity constant for a binop leaves a variable operand unchanged. For
1312  // a vector, this is a splat of something like 0, -1, or 1.
1313  // If there's no identity constant for this binop, we're done.
1314  auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1315  BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1316  Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1317  if (!IdC)
1318  return nullptr;
1319 
1320  // Shuffle identity constants into the lanes that return the original value.
1321  // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1322  // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1323  // The existing binop constant vector remains in the same operand position.
1324  Constant *Mask = Shuf.getMask();
1325  Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1326  ConstantExpr::getShuffleVector(IdC, C, Mask);
1327 
1328  bool MightCreatePoisonOrUB =
1329  Mask->containsUndefElement() &&
1330  (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1331  if (MightCreatePoisonOrUB)
1332  NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1333 
1334  // shuf (bop X, C), X, M --> bop X, C'
1335  // shuf X, (bop X, C), M --> bop X, C'
1336  Value *X = Op0IsBinop ? Op1 : Op0;
1337  Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1338  NewBO->copyIRFlags(BO);
1339 
1340  // An undef shuffle mask element may propagate as an undef constant element in
1341  // the new binop. That would produce poison where the original code might not.
1342  // If we already made a safe constant, then there's no danger.
1343  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1344  NewBO->dropPoisonGeneratingFlags();
1345  return NewBO;
1346 }
1347 
1348 /// Try to fold shuffles that are the equivalent of a vector select.
1350  InstCombiner::BuilderTy &Builder,
1351  const DataLayout &DL) {
1352  if (!Shuf.isSelect())
1353  return nullptr;
1354 
1356  return I;
1357 
1358  BinaryOperator *B0, *B1;
1359  if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1360  !match(Shuf.getOperand(1), m_BinOp(B1)))
1361  return nullptr;
1362 
1363  Value *X, *Y;
1364  Constant *C0, *C1;
1365  bool ConstantsAreOp1;
1366  if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1367  match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1368  ConstantsAreOp1 = true;
1369  else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1370  match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1371  ConstantsAreOp1 = false;
1372  else
1373  return nullptr;
1374 
1375  // We need matching binops to fold the lanes together.
1376  BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1377  BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1378  bool DropNSW = false;
1379  if (ConstantsAreOp1 && Opc0 != Opc1) {
1380  // TODO: We drop "nsw" if shift is converted into multiply because it may
1381  // not be correct when the shift amount is BitWidth - 1. We could examine
1382  // each vector element to determine if it is safe to keep that flag.
1383  if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1384  DropNSW = true;
1385  if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1386  assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1387  Opc0 = AltB0.Opcode;
1388  C0 = cast<Constant>(AltB0.Op1);
1389  } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1390  assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1391  Opc1 = AltB1.Opcode;
1392  C1 = cast<Constant>(AltB1.Op1);
1393  }
1394  }
1395 
1396  if (Opc0 != Opc1)
1397  return nullptr;
1398 
1399  // The opcodes must be the same. Use a new name to make that clear.
1400  BinaryOperator::BinaryOps BOpc = Opc0;
1401 
1402  // Select the constant elements needed for the single binop.
1403  Constant *Mask = Shuf.getMask();
1404  Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1405 
1406  // We are moving a binop after a shuffle. When a shuffle has an undefined
1407  // mask element, the result is undefined, but it is not poison or undefined
1408  // behavior. That is not necessarily true for div/rem/shift.
1409  bool MightCreatePoisonOrUB =
1410  Mask->containsUndefElement() &&
1412  if (MightCreatePoisonOrUB)
1413  NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1414 
1415  Value *V;
1416  if (X == Y) {
1417  // Remove a binop and the shuffle by rearranging the constant:
1418  // shuffle (op V, C0), (op V, C1), M --> op V, C'
1419  // shuffle (op C0, V), (op C1, V), M --> op C', V
1420  V = X;
1421  } else {
1422  // If there are 2 different variable operands, we must create a new shuffle
1423  // (select) first, so check uses to ensure that we don't end up with more
1424  // instructions than we started with.
1425  if (!B0->hasOneUse() && !B1->hasOneUse())
1426  return nullptr;
1427 
1428  // If we use the original shuffle mask and op1 is *variable*, we would be
1429  // putting an undef into operand 1 of div/rem/shift. This is either UB or
1430  // poison. We do not have to guard against UB when *constants* are op1
1431  // because safe constants guarantee that we do not overflow sdiv/srem (and
1432  // there's no danger for other opcodes).
1433  // TODO: To allow this case, create a new shuffle mask with no undefs.
1434  if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1435  return nullptr;
1436 
1437  // Note: In general, we do not create new shuffles in InstCombine because we
1438  // do not know if a target can lower an arbitrary shuffle optimally. In this
1439  // case, the shuffle uses the existing mask, so there is no additional risk.
1440 
1441  // Select the variable vectors first, then perform the binop:
1442  // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1443  // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1444  V = Builder.CreateShuffleVector(X, Y, Mask);
1445  }
1446 
1447  Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1448  BinaryOperator::Create(BOpc, NewC, V);
1449 
1450  // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1451  // 1. If we changed an opcode, poison conditions might have changed.
1452  // 2. If the shuffle had undef mask elements, the new binop might have undefs
1453  // where the original code did not. But if we already made a safe constant,
1454  // then there's no danger.
1455  NewBO->copyIRFlags(B0);
1456  NewBO->andIRFlags(B1);
1457  if (DropNSW)
1458  NewBO->setHasNoSignedWrap(false);
1459  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1460  NewBO->dropPoisonGeneratingFlags();
1461  return NewBO;
1462 }
1463 
1464 /// Match a shuffle-select-shuffle pattern where the shuffles are widening and
1465 /// narrowing (concatenating with undef and extracting back to the original
1466 /// length). This allows replacing the wide select with a narrow select.
1468  InstCombiner::BuilderTy &Builder) {
1469  // This must be a narrowing identity shuffle. It extracts the 1st N elements
1470  // of the 1st vector operand of a shuffle.
1471  if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
1472  return nullptr;
1473 
1474  // The vector being shuffled must be a vector select that we can eliminate.
1475  // TODO: The one-use requirement could be eased if X and/or Y are constants.
1476  Value *Cond, *X, *Y;
1477  if (!match(Shuf.getOperand(0),
1478  m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
1479  return nullptr;
1480 
1481  // We need a narrow condition value. It must be extended with undef elements
1482  // and have the same number of elements as this shuffle.
1483  unsigned NarrowNumElts = Shuf.getType()->getVectorNumElements();
1484  Value *NarrowCond;
1485  if (!match(Cond, m_OneUse(m_ShuffleVector(m_Value(NarrowCond), m_Undef(),
1486  m_Constant()))) ||
1487  NarrowCond->getType()->getVectorNumElements() != NarrowNumElts ||
1488  !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
1489  return nullptr;
1490 
1491  // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
1492  // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
1494  Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getMask());
1495  Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getMask());
1496  return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
1497 }
1498 
1499 /// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
1501  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1502  if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1))
1503  return nullptr;
1504 
1505  Value *X, *Y;
1506  Constant *Mask;
1507  if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask))))
1508  return nullptr;
1509 
1510  // We are extracting a subvector from a shuffle. Remove excess elements from
1511  // the 1st shuffle mask to eliminate the extract.
1512  //
1513  // This transform is conservatively limited to identity extracts because we do
1514  // not allow arbitrary shuffle mask creation as a target-independent transform
1515  // (because we can't guarantee that will lower efficiently).
1516  //
1517  // If the extracting shuffle has an undef mask element, it transfers to the
1518  // new shuffle mask. Otherwise, copy the original mask element. Example:
1519  // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
1520  // shuf X, Y, <C0, undef, C2, undef>
1521  unsigned NumElts = Shuf.getType()->getVectorNumElements();
1522  SmallVector<Constant *, 16> NewMask(NumElts);
1523  assert(NumElts < Mask->getType()->getVectorNumElements() &&
1524  "Identity with extract must have less elements than its inputs");
1525 
1526  for (unsigned i = 0; i != NumElts; ++i) {
1527  Constant *ExtractMaskElt = Shuf.getMask()->getAggregateElement(i);
1528  Constant *MaskElt = Mask->getAggregateElement(i);
1529  NewMask[i] = isa<UndefValue>(ExtractMaskElt) ? ExtractMaskElt : MaskElt;
1530  }
1531  return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1532 }
1533 
1534 /// Try to replace a shuffle with an insertelement.
1536  Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1);
1538 
1539  // The shuffle must not change vector sizes.
1540  // TODO: This restriction could be removed if the insert has only one use
1541  // (because the transform would require a new length-changing shuffle).
1542  int NumElts = Mask.size();
1543  if (NumElts != (int)(V0->getType()->getVectorNumElements()))
1544  return nullptr;
1545 
1546  // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
1547  auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
1548  // We need an insertelement with a constant index.
1549  if (!match(V0, m_InsertElement(m_Value(), m_Value(Scalar),
1550  m_ConstantInt(IndexC))))
1551  return false;
1552 
1553  // Test the shuffle mask to see if it splices the inserted scalar into the
1554  // operand 1 vector of the shuffle.
1555  int NewInsIndex = -1;
1556  for (int i = 0; i != NumElts; ++i) {
1557  // Ignore undef mask elements.
1558  if (Mask[i] == -1)
1559  continue;
1560 
1561  // The shuffle takes elements of operand 1 without lane changes.
1562  if (Mask[i] == NumElts + i)
1563  continue;
1564 
1565  // The shuffle must choose the inserted scalar exactly once.
1566  if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
1567  return false;
1568 
1569  // The shuffle is placing the inserted scalar into element i.
1570  NewInsIndex = i;
1571  }
1572 
1573  assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?");
1574 
1575  // Index is updated to the potentially translated insertion lane.
1576  IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex);
1577  return true;
1578  };
1579 
1580  // If the shuffle is unnecessary, insert the scalar operand directly into
1581  // operand 1 of the shuffle. Example:
1582  // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
1583  Value *Scalar;
1584  ConstantInt *IndexC;
1585  if (isShufflingScalarIntoOp1(Scalar, IndexC))
1586  return InsertElementInst::Create(V1, Scalar, IndexC);
1587 
1588  // Try again after commuting shuffle. Example:
1589  // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
1590  // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
1591  std::swap(V0, V1);
1593  if (isShufflingScalarIntoOp1(Scalar, IndexC))
1594  return InsertElementInst::Create(V1, Scalar, IndexC);
1595 
1596  return nullptr;
1597 }
1598 
1600  Value *LHS = SVI.getOperand(0);
1601  Value *RHS = SVI.getOperand(1);
1602  if (auto *V = SimplifyShuffleVectorInst(
1603  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1604  return replaceInstUsesWith(SVI, V);
1605 
1606  if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
1607  return I;
1608 
1609  if (Instruction *I = narrowVectorSelect(SVI, Builder))
1610  return I;
1611 
1612  unsigned VWidth = SVI.getType()->getVectorNumElements();
1613  APInt UndefElts(VWidth, 0);
1614  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1615  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1616  if (V != &SVI)
1617  return replaceInstUsesWith(SVI, V);
1618  return &SVI;
1619  }
1620 
1622  return I;
1623 
1624  // This transform has the potential to lose undef knowledge, so it is
1625  // intentionally placed after SimplifyDemandedVectorElts().
1626  if (Instruction *I = foldShuffleWithInsert(SVI))
1627  return I;
1628 
1631  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1632  bool MadeChange = false;
1633 
1634  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1635  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1636  if (LHS == RHS || isa<UndefValue>(LHS)) {
1637  // Remap any references to RHS to use LHS.
1639  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1640  if (Mask[i] < 0) {
1641  Elts.push_back(UndefValue::get(Int32Ty));
1642  continue;
1643  }
1644 
1645  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1646  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1647  Mask[i] = -1; // Turn into undef.
1648  Elts.push_back(UndefValue::get(Int32Ty));
1649  } else {
1650  Mask[i] = Mask[i] % e; // Force to LHS.
1651  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1652  }
1653  }
1654  SVI.setOperand(0, SVI.getOperand(1));
1655  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1656  SVI.setOperand(2, ConstantVector::get(Elts));
1657  LHS = SVI.getOperand(0);
1658  RHS = SVI.getOperand(1);
1659  MadeChange = true;
1660  }
1661 
1662  if (VWidth == LHSWidth) {
1663  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1664  bool isLHSID, isRHSID;
1665  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1666 
1667  // Eliminate identity shuffles.
1668  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1669  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1670  }
1671 
1672  if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) {
1673  Value *V = evaluateInDifferentElementOrder(LHS, Mask);
1674  return replaceInstUsesWith(SVI, V);
1675  }
1676 
1677  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1678  // a non-vector type. We can instead bitcast the original vector followed by
1679  // an extract of the desired element:
1680  //
1681  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1682  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1683  // %1 = bitcast <4 x i8> %sroa to i32
1684  // Becomes:
1685  // %bc = bitcast <16 x i8> %in to <4 x i32>
1686  // %ext = extractelement <4 x i32> %bc, i32 0
1687  //
1688  // If the shuffle is extracting a contiguous range of values from the input
1689  // vector then each use which is a bitcast of the extracted size can be
1690  // replaced. This will work if the vector types are compatible, and the begin
1691  // index is aligned to a value in the casted vector type. If the begin index
1692  // isn't aligned then we can shuffle the original vector (keeping the same
1693  // vector type) before extracting.
1694  //
1695  // This code will bail out if the target type is fundamentally incompatible
1696  // with vectors of the source type.
1697  //
1698  // Example of <16 x i8>, target type i32:
1699  // Index range [4,8): v-----------v Will work.
1700  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1701  // <16 x i8>: | | | | | | | | | | | | | | | | |
1702  // <4 x i32>: | | | | |
1703  // +-----------+-----------+-----------+-----------+
1704  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1705  // Target type i40: ^--------------^ Won't work, bail.
1706  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1707  Value *V = LHS;
1708  unsigned MaskElems = Mask.size();
1709  VectorType *SrcTy = cast<VectorType>(V->getType());
1710  unsigned VecBitWidth = SrcTy->getBitWidth();
1711  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1712  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1713  unsigned SrcNumElems = SrcTy->getNumElements();
1716  for (User *U : SVI.users())
1717  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1718  if (!BC->use_empty())
1719  // Only visit bitcasts that weren't previously handled.
1720  BCs.push_back(BC);
1721  for (BitCastInst *BC : BCs) {
1722  unsigned BegIdx = Mask.front();
1723  Type *TgtTy = BC->getDestTy();
1724  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1725  if (!TgtElemBitWidth)
1726  continue;
1727  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1728  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1729  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1730  if (!VecBitWidthsEqual)
1731  continue;
1732  if (!VectorType::isValidElementType(TgtTy))
1733  continue;
1734  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1735  if (!BegIsAligned) {
1736  // Shuffle the input so [0,NumElements) contains the output, and
1737  // [NumElems,SrcNumElems) is undef.
1738  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1739  UndefValue::get(Int32Ty));
1740  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1741  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1742  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1743  ConstantVector::get(ShuffleMask),
1744  SVI.getName() + ".extract");
1745  BegIdx = 0;
1746  }
1747  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1748  assert(SrcElemsPerTgtElem);
1749  BegIdx /= SrcElemsPerTgtElem;
1750  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1751  auto *NewBC =
1752  BCAlreadyExists
1753  ? NewBCs[CastSrcTy]
1754  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1755  if (!BCAlreadyExists)
1756  NewBCs[CastSrcTy] = NewBC;
1757  auto *Ext = Builder.CreateExtractElement(
1758  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1759  // The shufflevector isn't being replaced: the bitcast that used it
1760  // is. InstCombine will visit the newly-created instructions.
1761  replaceInstUsesWith(*BC, Ext);
1762  MadeChange = true;
1763  }
1764  }
1765 
1766  // If the LHS is a shufflevector itself, see if we can combine it with this
1767  // one without producing an unusual shuffle.
1768  // Cases that might be simplified:
1769  // 1.
1770  // x1=shuffle(v1,v2,mask1)
1771  // x=shuffle(x1,undef,mask)
1772  // ==>
1773  // x=shuffle(v1,undef,newMask)
1774  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1775  // 2.
1776  // x1=shuffle(v1,undef,mask1)
1777  // x=shuffle(x1,x2,mask)
1778  // where v1.size() == mask1.size()
1779  // ==>
1780  // x=shuffle(v1,x2,newMask)
1781  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1782  // 3.
1783  // x2=shuffle(v2,undef,mask2)
1784  // x=shuffle(x1,x2,mask)
1785  // where v2.size() == mask2.size()
1786  // ==>
1787  // x=shuffle(x1,v2,newMask)
1788  // newMask[i] = (mask[i] < x1.size())
1789  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1790  // 4.
1791  // x1=shuffle(v1,undef,mask1)
1792  // x2=shuffle(v2,undef,mask2)
1793  // x=shuffle(x1,x2,mask)
1794  // where v1.size() == v2.size()
1795  // ==>
1796  // x=shuffle(v1,v2,newMask)
1797  // newMask[i] = (mask[i] < x1.size())
1798  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1799  //
1800  // Here we are really conservative:
1801  // we are absolutely afraid of producing a shuffle mask not in the input
1802  // program, because the code gen may not be smart enough to turn a merged
1803  // shuffle into two specific shuffles: it may produce worse code. As such,
1804  // we only merge two shuffles if the result is either a splat or one of the
1805  // input shuffle masks. In this case, merging the shuffles just removes
1806  // one instruction, which we know is safe. This is good for things like
1807  // turning: (splat(splat)) -> splat, or
1808  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1809  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1810  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1811  if (LHSShuffle)
1812  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1813  LHSShuffle = nullptr;
1814  if (RHSShuffle)
1815  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1816  RHSShuffle = nullptr;
1817  if (!LHSShuffle && !RHSShuffle)
1818  return MadeChange ? &SVI : nullptr;
1819 
1820  Value* LHSOp0 = nullptr;
1821  Value* LHSOp1 = nullptr;
1822  Value* RHSOp0 = nullptr;
1823  unsigned LHSOp0Width = 0;
1824  unsigned RHSOp0Width = 0;
1825  if (LHSShuffle) {
1826  LHSOp0 = LHSShuffle->getOperand(0);
1827  LHSOp1 = LHSShuffle->getOperand(1);
1828  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1829  }
1830  if (RHSShuffle) {
1831  RHSOp0 = RHSShuffle->getOperand(0);
1832  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1833  }
1834  Value* newLHS = LHS;
1835  Value* newRHS = RHS;
1836  if (LHSShuffle) {
1837  // case 1
1838  if (isa<UndefValue>(RHS)) {
1839  newLHS = LHSOp0;
1840  newRHS = LHSOp1;
1841  }
1842  // case 2 or 4
1843  else if (LHSOp0Width == LHSWidth) {
1844  newLHS = LHSOp0;
1845  }
1846  }
1847  // case 3 or 4
1848  if (RHSShuffle && RHSOp0Width == LHSWidth) {
1849  newRHS = RHSOp0;
1850  }
1851  // case 4
1852  if (LHSOp0 == RHSOp0) {
1853  newLHS = LHSOp0;
1854  newRHS = nullptr;
1855  }
1856 
1857  if (newLHS == LHS && newRHS == RHS)
1858  return MadeChange ? &SVI : nullptr;
1859 
1860  SmallVector<int, 16> LHSMask;
1861  SmallVector<int, 16> RHSMask;
1862  if (newLHS != LHS)
1863  LHSMask = LHSShuffle->getShuffleMask();
1864  if (RHSShuffle && newRHS != RHS)
1865  RHSMask = RHSShuffle->getShuffleMask();
1866 
1867  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1868  SmallVector<int, 16> newMask;
1869  bool isSplat = true;
1870  int SplatElt = -1;
1871  // Create a new mask for the new ShuffleVectorInst so that the new
1872  // ShuffleVectorInst is equivalent to the original one.
1873  for (unsigned i = 0; i < VWidth; ++i) {
1874  int eltMask;
1875  if (Mask[i] < 0) {
1876  // This element is an undef value.
1877  eltMask = -1;
1878  } else if (Mask[i] < (int)LHSWidth) {
1879  // This element is from left hand side vector operand.
1880  //
1881  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1882  // new mask value for the element.
1883  if (newLHS != LHS) {
1884  eltMask = LHSMask[Mask[i]];
1885  // If the value selected is an undef value, explicitly specify it
1886  // with a -1 mask value.
1887  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1888  eltMask = -1;
1889  } else
1890  eltMask = Mask[i];
1891  } else {
1892  // This element is from right hand side vector operand
1893  //
1894  // If the value selected is an undef value, explicitly specify it
1895  // with a -1 mask value. (case 1)
1896  if (isa<UndefValue>(RHS))
1897  eltMask = -1;
1898  // If RHS is going to be replaced (case 3 or 4), calculate the
1899  // new mask value for the element.
1900  else if (newRHS != RHS) {
1901  eltMask = RHSMask[Mask[i]-LHSWidth];
1902  // If the value selected is an undef value, explicitly specify it
1903  // with a -1 mask value.
1904  if (eltMask >= (int)RHSOp0Width) {
1905  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1906  && "should have been check above");
1907  eltMask = -1;
1908  }
1909  } else
1910  eltMask = Mask[i]-LHSWidth;
1911 
1912  // If LHS's width is changed, shift the mask value accordingly.
1913  // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
1914  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1915  // If newRHS == newLHS, we want to remap any references from newRHS to
1916  // newLHS so that we can properly identify splats that may occur due to
1917  // obfuscation across the two vectors.
1918  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1919  eltMask += newLHSWidth;
1920  }
1921 
1922  // Check if this could still be a splat.
1923  if (eltMask >= 0) {
1924  if (SplatElt >= 0 && SplatElt != eltMask)
1925  isSplat = false;
1926  SplatElt = eltMask;
1927  }
1928 
1929  newMask.push_back(eltMask);
1930  }
1931 
1932  // If the result mask is equal to one of the original shuffle masks,
1933  // or is a splat, do the replacement.
1934  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1936  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1937  if (newMask[i] < 0) {
1938  Elts.push_back(UndefValue::get(Int32Ty));
1939  } else {
1940  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1941  }
1942  }
1943  if (!newRHS)
1944  newRHS = UndefValue::get(newLHS->getType());
1945  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1946  }
1947 
1948  // If the result mask is an identity, replace uses of this instruction with
1949  // corresponding argument.
1950  bool isLHSID, isRHSID;
1951  recognizeIdentityMask(newMask, isLHSID, isRHSID);
1952  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1953  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1954 
1955  return MadeChange ? &SVI : nullptr;
1956 }
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:632
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)
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
Definition: PatternMatch.h:80
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...
This class represents lattice values for constants.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:312
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:1332
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:705
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:1403
TwoOps_match< Val_t, Idx_t, Instruction::ExtractElement > m_ExtractElement(const Val_t &Val, const Idx_t &Idx)
Matches ExtractElementInst.
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:197
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 Instruction * foldShuffleWithInsert(ShuffleVectorInst &Shuf)
Try to replace a shuffle with an insertelement.
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:621
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.
static CmpInst * Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2, const Twine &Name="", Instruction *InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
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:335
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:219
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
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:503
static Constant * getShuffleVector(Constant *V1, Constant *V2, Constant *Mask, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2149
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:1187
This instruction compares its operands according to the predicate given to the constructor.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:642
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2327
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:1415
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:254
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:622
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
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:941
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:159
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:215
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:107
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:2310
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:606
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:132
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:1079
static void commuteShuffleMask(MutableArrayRef< int > Mask, unsigned InVecNumElts)
Change values in a shuffle permute mask assuming the two vector operands of length InVecNumElts have ...
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.