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