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;
1175  // Recursively call evaluateInDifferentElementOrder on vector arguments
1176  // as well. E.g. GetElementPtr may have scalar operands even if the
1177  // return value is a vector, so we need to examine the operand type.
1178  if (I->getOperand(i)->getType()->isVectorTy())
1179  V = evaluateInDifferentElementOrder(I->getOperand(i), Mask);
1180  else
1181  V = I->getOperand(i);
1182  NewOps.push_back(V);
1183  NeedsRebuild |= (V != I->getOperand(i));
1184  }
1185  if (NeedsRebuild) {
1186  return buildNew(I, NewOps);
1187  }
1188  return I;
1189  }
1190  case Instruction::InsertElement: {
1191  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1192 
1193  // The insertelement was inserting at Element. Figure out which element
1194  // that becomes after shuffling. The answer is guaranteed to be unique
1195  // by CanEvaluateShuffled.
1196  bool Found = false;
1197  int Index = 0;
1198  for (int e = Mask.size(); Index != e; ++Index) {
1199  if (Mask[Index] == Element) {
1200  Found = true;
1201  break;
1202  }
1203  }
1204 
1205  // If element is not in Mask, no need to handle the operand 1 (element to
1206  // be inserted). Just evaluate values in operand 0 according to Mask.
1207  if (!Found)
1208  return evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1209 
1210  Value *V = evaluateInDifferentElementOrder(I->getOperand(0), Mask);
1211  return InsertElementInst::Create(V, I->getOperand(1),
1212  ConstantInt::get(I32Ty, Index), "", I);
1213  }
1214  }
1215  llvm_unreachable("failed to reorder elements of vector instruction!");
1216 }
1217 
1219  bool &isLHSID, bool &isRHSID) {
1220  isLHSID = isRHSID = true;
1221 
1222  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1223  if (Mask[i] < 0) continue; // Ignore undef values.
1224  // Is this an identity shuffle of the LHS value?
1225  isLHSID &= (Mask[i] == (int)i);
1226 
1227  // Is this an identity shuffle of the RHS value?
1228  isRHSID &= (Mask[i]-e == i);
1229  }
1230 }
1231 
1232 // Returns true if the shuffle is extracting a contiguous range of values from
1233 // LHS, for example:
1234 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1235 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1236 // Shuffles to: |EE|FF|GG|HH|
1237 // +--+--+--+--+
1240  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1241  unsigned MaskElems = Mask.size();
1242  unsigned BegIdx = Mask.front();
1243  unsigned EndIdx = Mask.back();
1244  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1245  return false;
1246  for (unsigned I = 0; I != MaskElems; ++I)
1247  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1248  return false;
1249  return true;
1250 }
1251 
1252 /// These are the ingredients in an alternate form binary operator as described
1253 /// below.
1254 struct BinopElts {
1259  Value *V0 = nullptr, Value *V1 = nullptr) :
1260  Opcode(Opc), Op0(V0), Op1(V1) {}
1261  operator bool() const { return Opcode != 0; }
1262 };
1263 
1264 /// Binops may be transformed into binops with different opcodes and operands.
1265 /// Reverse the usual canonicalization to enable folds with the non-canonical
1266 /// form of the binop. If a transform is possible, return the elements of the
1267 /// new binop. If not, return invalid elements.
1269  Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1270  Type *Ty = BO->getType();
1271  switch (BO->getOpcode()) {
1272  case Instruction::Shl: {
1273  // shl X, C --> mul X, (1 << C)
1274  Constant *C;
1275  if (match(BO1, m_Constant(C))) {
1276  Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1277  return { Instruction::Mul, BO0, ShlOne };
1278  }
1279  break;
1280  }
1281  case Instruction::Or: {
1282  // or X, C --> add X, C (when X and C have no common bits set)
1283  const APInt *C;
1284  if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1285  return { Instruction::Add, BO0, BO1 };
1286  break;
1287  }
1288  default:
1289  break;
1290  }
1291  return {};
1292 }
1293 
1295  assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1296 
1297  // Are we shuffling together some value and that same value after it has been
1298  // modified by a binop with a constant?
1299  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1300  Constant *C;
1301  bool Op0IsBinop;
1302  if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1303  Op0IsBinop = true;
1304  else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1305  Op0IsBinop = false;
1306  else
1307  return nullptr;
1308 
1309  // The identity constant for a binop leaves a variable operand unchanged. For
1310  // a vector, this is a splat of something like 0, -1, or 1.
1311  // If there's no identity constant for this binop, we're done.
1312  auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1313  BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1314  Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1315  if (!IdC)
1316  return nullptr;
1317 
1318  // Shuffle identity constants into the lanes that return the original value.
1319  // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1320  // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1321  // The existing binop constant vector remains in the same operand position.
1322  Constant *Mask = Shuf.getMask();
1323  Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1324  ConstantExpr::getShuffleVector(IdC, C, Mask);
1325 
1326  bool MightCreatePoisonOrUB =
1327  Mask->containsUndefElement() &&
1328  (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1329  if (MightCreatePoisonOrUB)
1330  NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1331 
1332  // shuf (bop X, C), X, M --> bop X, C'
1333  // shuf X, (bop X, C), M --> bop X, C'
1334  Value *X = Op0IsBinop ? Op1 : Op0;
1335  Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1336  NewBO->copyIRFlags(BO);
1337 
1338  // An undef shuffle mask element may propagate as an undef constant element in
1339  // the new binop. That would produce poison where the original code might not.
1340  // If we already made a safe constant, then there's no danger.
1341  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1342  NewBO->dropPoisonGeneratingFlags();
1343  return NewBO;
1344 }
1345 
1346 /// Try to fold shuffles that are the equivalent of a vector select.
1348  InstCombiner::BuilderTy &Builder,
1349  const DataLayout &DL) {
1350  if (!Shuf.isSelect())
1351  return nullptr;
1352 
1353  // Canonicalize to choose from operand 0 first.
1354  unsigned NumElts = Shuf.getType()->getVectorNumElements();
1355  if (Shuf.getMaskValue(0) >= (int)NumElts) {
1356  // TODO: Can we assert that both operands of a shuffle-select are not undef
1357  // (otherwise, it would have been folded by instsimplify?
1358  Shuf.commute();
1359  return &Shuf;
1360  }
1361 
1363  return I;
1364 
1365  BinaryOperator *B0, *B1;
1366  if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1367  !match(Shuf.getOperand(1), m_BinOp(B1)))
1368  return nullptr;
1369 
1370  Value *X, *Y;
1371  Constant *C0, *C1;
1372  bool ConstantsAreOp1;
1373  if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1374  match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1375  ConstantsAreOp1 = true;
1376  else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1377  match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1378  ConstantsAreOp1 = false;
1379  else
1380  return nullptr;
1381 
1382  // We need matching binops to fold the lanes together.
1383  BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1384  BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1385  bool DropNSW = false;
1386  if (ConstantsAreOp1 && Opc0 != Opc1) {
1387  // TODO: We drop "nsw" if shift is converted into multiply because it may
1388  // not be correct when the shift amount is BitWidth - 1. We could examine
1389  // each vector element to determine if it is safe to keep that flag.
1390  if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1391  DropNSW = true;
1392  if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1393  assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1394  Opc0 = AltB0.Opcode;
1395  C0 = cast<Constant>(AltB0.Op1);
1396  } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1397  assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1398  Opc1 = AltB1.Opcode;
1399  C1 = cast<Constant>(AltB1.Op1);
1400  }
1401  }
1402 
1403  if (Opc0 != Opc1)
1404  return nullptr;
1405 
1406  // The opcodes must be the same. Use a new name to make that clear.
1407  BinaryOperator::BinaryOps BOpc = Opc0;
1408 
1409  // Select the constant elements needed for the single binop.
1410  Constant *Mask = Shuf.getMask();
1411  Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1412 
1413  // We are moving a binop after a shuffle. When a shuffle has an undefined
1414  // mask element, the result is undefined, but it is not poison or undefined
1415  // behavior. That is not necessarily true for div/rem/shift.
1416  bool MightCreatePoisonOrUB =
1417  Mask->containsUndefElement() &&
1419  if (MightCreatePoisonOrUB)
1420  NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1421 
1422  Value *V;
1423  if (X == Y) {
1424  // Remove a binop and the shuffle by rearranging the constant:
1425  // shuffle (op V, C0), (op V, C1), M --> op V, C'
1426  // shuffle (op C0, V), (op C1, V), M --> op C', V
1427  V = X;
1428  } else {
1429  // If there are 2 different variable operands, we must create a new shuffle
1430  // (select) first, so check uses to ensure that we don't end up with more
1431  // instructions than we started with.
1432  if (!B0->hasOneUse() && !B1->hasOneUse())
1433  return nullptr;
1434 
1435  // If we use the original shuffle mask and op1 is *variable*, we would be
1436  // putting an undef into operand 1 of div/rem/shift. This is either UB or
1437  // poison. We do not have to guard against UB when *constants* are op1
1438  // because safe constants guarantee that we do not overflow sdiv/srem (and
1439  // there's no danger for other opcodes).
1440  // TODO: To allow this case, create a new shuffle mask with no undefs.
1441  if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1442  return nullptr;
1443 
1444  // Note: In general, we do not create new shuffles in InstCombine because we
1445  // do not know if a target can lower an arbitrary shuffle optimally. In this
1446  // case, the shuffle uses the existing mask, so there is no additional risk.
1447 
1448  // Select the variable vectors first, then perform the binop:
1449  // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1450  // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1451  V = Builder.CreateShuffleVector(X, Y, Mask);
1452  }
1453 
1454  Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1455  BinaryOperator::Create(BOpc, NewC, V);
1456 
1457  // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1458  // 1. If we changed an opcode, poison conditions might have changed.
1459  // 2. If the shuffle had undef mask elements, the new binop might have undefs
1460  // where the original code did not. But if we already made a safe constant,
1461  // then there's no danger.
1462  NewBO->copyIRFlags(B0);
1463  NewBO->andIRFlags(B1);
1464  if (DropNSW)
1465  NewBO->setHasNoSignedWrap(false);
1466  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1467  NewBO->dropPoisonGeneratingFlags();
1468  return NewBO;
1469 }
1470 
1471 /// Match a shuffle-select-shuffle pattern where the shuffles are widening and
1472 /// narrowing (concatenating with undef and extracting back to the original
1473 /// length). This allows replacing the wide select with a narrow select.
1475  InstCombiner::BuilderTy &Builder) {
1476  // This must be a narrowing identity shuffle. It extracts the 1st N elements
1477  // of the 1st vector operand of a shuffle.
1478  if (!match(Shuf.getOperand(1), m_Undef()) || !Shuf.isIdentityWithExtract())
1479  return nullptr;
1480 
1481  // The vector being shuffled must be a vector select that we can eliminate.
1482  // TODO: The one-use requirement could be eased if X and/or Y are constants.
1483  Value *Cond, *X, *Y;
1484  if (!match(Shuf.getOperand(0),
1485  m_OneUse(m_Select(m_Value(Cond), m_Value(X), m_Value(Y)))))
1486  return nullptr;
1487 
1488  // We need a narrow condition value. It must be extended with undef elements
1489  // and have the same number of elements as this shuffle.
1490  unsigned NarrowNumElts = Shuf.getType()->getVectorNumElements();
1491  Value *NarrowCond;
1492  if (!match(Cond, m_OneUse(m_ShuffleVector(m_Value(NarrowCond), m_Undef(),
1493  m_Constant()))) ||
1494  NarrowCond->getType()->getVectorNumElements() != NarrowNumElts ||
1495  !cast<ShuffleVectorInst>(Cond)->isIdentityWithPadding())
1496  return nullptr;
1497 
1498  // shuf (sel (shuf NarrowCond, undef, WideMask), X, Y), undef, NarrowMask) -->
1499  // sel NarrowCond, (shuf X, undef, NarrowMask), (shuf Y, undef, NarrowMask)
1501  Value *NarrowX = Builder.CreateShuffleVector(X, Undef, Shuf.getMask());
1502  Value *NarrowY = Builder.CreateShuffleVector(Y, Undef, Shuf.getMask());
1503  return SelectInst::Create(NarrowCond, NarrowX, NarrowY);
1504 }
1505 
1506 /// Try to combine 2 shuffles into 1 shuffle by concatenating a shuffle mask.
1508  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1509  if (!Shuf.isIdentityWithExtract() || !isa<UndefValue>(Op1))
1510  return nullptr;
1511 
1512  Value *X, *Y;
1513  Constant *Mask;
1514  if (!match(Op0, m_ShuffleVector(m_Value(X), m_Value(Y), m_Constant(Mask))))
1515  return nullptr;
1516 
1517  // Be conservative with shuffle transforms. If we can't kill the 1st shuffle,
1518  // then combining may result in worse codegen.
1519  if (!Op0->hasOneUse())
1520  return nullptr;
1521 
1522  // We are extracting a subvector from a shuffle. Remove excess elements from
1523  // the 1st shuffle mask to eliminate the extract.
1524  //
1525  // This transform is conservatively limited to identity extracts because we do
1526  // not allow arbitrary shuffle mask creation as a target-independent transform
1527  // (because we can't guarantee that will lower efficiently).
1528  //
1529  // If the extracting shuffle has an undef mask element, it transfers to the
1530  // new shuffle mask. Otherwise, copy the original mask element. Example:
1531  // shuf (shuf X, Y, <C0, C1, C2, undef, C4>), undef, <0, undef, 2, 3> -->
1532  // shuf X, Y, <C0, undef, C2, undef>
1533  unsigned NumElts = Shuf.getType()->getVectorNumElements();
1534  SmallVector<Constant *, 16> NewMask(NumElts);
1535  assert(NumElts < Mask->getType()->getVectorNumElements() &&
1536  "Identity with extract must have less elements than its inputs");
1537 
1538  for (unsigned i = 0; i != NumElts; ++i) {
1539  Constant *ExtractMaskElt = Shuf.getMask()->getAggregateElement(i);
1540  Constant *MaskElt = Mask->getAggregateElement(i);
1541  NewMask[i] = isa<UndefValue>(ExtractMaskElt) ? ExtractMaskElt : MaskElt;
1542  }
1543  return new ShuffleVectorInst(X, Y, ConstantVector::get(NewMask));
1544 }
1545 
1546 /// Try to replace a shuffle with an insertelement.
1548  Value *V0 = Shuf.getOperand(0), *V1 = Shuf.getOperand(1);
1550 
1551  // The shuffle must not change vector sizes.
1552  // TODO: This restriction could be removed if the insert has only one use
1553  // (because the transform would require a new length-changing shuffle).
1554  int NumElts = Mask.size();
1555  if (NumElts != (int)(V0->getType()->getVectorNumElements()))
1556  return nullptr;
1557 
1558  // shuffle (insert ?, Scalar, IndexC), V1, Mask --> insert V1, Scalar, IndexC'
1559  auto isShufflingScalarIntoOp1 = [&](Value *&Scalar, ConstantInt *&IndexC) {
1560  // We need an insertelement with a constant index.
1561  if (!match(V0, m_InsertElement(m_Value(), m_Value(Scalar),
1562  m_ConstantInt(IndexC))))
1563  return false;
1564 
1565  // Test the shuffle mask to see if it splices the inserted scalar into the
1566  // operand 1 vector of the shuffle.
1567  int NewInsIndex = -1;
1568  for (int i = 0; i != NumElts; ++i) {
1569  // Ignore undef mask elements.
1570  if (Mask[i] == -1)
1571  continue;
1572 
1573  // The shuffle takes elements of operand 1 without lane changes.
1574  if (Mask[i] == NumElts + i)
1575  continue;
1576 
1577  // The shuffle must choose the inserted scalar exactly once.
1578  if (NewInsIndex != -1 || Mask[i] != IndexC->getSExtValue())
1579  return false;
1580 
1581  // The shuffle is placing the inserted scalar into element i.
1582  NewInsIndex = i;
1583  }
1584 
1585  assert(NewInsIndex != -1 && "Did not fold shuffle with unused operand?");
1586 
1587  // Index is updated to the potentially translated insertion lane.
1588  IndexC = ConstantInt::get(IndexC->getType(), NewInsIndex);
1589  return true;
1590  };
1591 
1592  // If the shuffle is unnecessary, insert the scalar operand directly into
1593  // operand 1 of the shuffle. Example:
1594  // shuffle (insert ?, S, 1), V1, <1, 5, 6, 7> --> insert V1, S, 0
1595  Value *Scalar;
1596  ConstantInt *IndexC;
1597  if (isShufflingScalarIntoOp1(Scalar, IndexC))
1598  return InsertElementInst::Create(V1, Scalar, IndexC);
1599 
1600  // Try again after commuting shuffle. Example:
1601  // shuffle V0, (insert ?, S, 0), <0, 1, 2, 4> -->
1602  // shuffle (insert ?, S, 0), V0, <4, 5, 6, 0> --> insert V0, S, 3
1603  std::swap(V0, V1);
1605  if (isShufflingScalarIntoOp1(Scalar, IndexC))
1606  return InsertElementInst::Create(V1, Scalar, IndexC);
1607 
1608  return nullptr;
1609 }
1610 
1612  Value *LHS = SVI.getOperand(0);
1613  Value *RHS = SVI.getOperand(1);
1614  if (auto *V = SimplifyShuffleVectorInst(
1615  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1616  return replaceInstUsesWith(SVI, V);
1617 
1618  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1619  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1620  unsigned VWidth = SVI.getType()->getVectorNumElements();
1621  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1624  if (LHS == RHS || isa<UndefValue>(LHS)) {
1625  // Remap any references to RHS to use LHS.
1627  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1628  if (Mask[i] < 0) {
1629  Elts.push_back(UndefValue::get(Int32Ty));
1630  continue;
1631  }
1632 
1633  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1634  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1635  Mask[i] = -1; // Turn into undef.
1636  Elts.push_back(UndefValue::get(Int32Ty));
1637  } else {
1638  Mask[i] = Mask[i] % e; // Force to LHS.
1639  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1640  }
1641  }
1642  SVI.setOperand(0, SVI.getOperand(1));
1643  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1644  SVI.setOperand(2, ConstantVector::get(Elts));
1645  return &SVI;
1646  }
1647 
1648  if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
1649  return I;
1650 
1651  if (Instruction *I = narrowVectorSelect(SVI, Builder))
1652  return I;
1653 
1654  APInt UndefElts(VWidth, 0);
1655  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1656  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1657  if (V != &SVI)
1658  return replaceInstUsesWith(SVI, V);
1659  return &SVI;
1660  }
1661 
1663  return I;
1664 
1665  // This transform has the potential to lose undef knowledge, so it is
1666  // intentionally placed after SimplifyDemandedVectorElts().
1667  if (Instruction *I = foldShuffleWithInsert(SVI))
1668  return I;
1669 
1670  if (VWidth == LHSWidth) {
1671  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1672  bool isLHSID, isRHSID;
1673  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1674 
1675  // Eliminate identity shuffles.
1676  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1677  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1678  }
1679 
1680  if (isa<UndefValue>(RHS) && canEvaluateShuffled(LHS, Mask)) {
1681  Value *V = evaluateInDifferentElementOrder(LHS, Mask);
1682  return replaceInstUsesWith(SVI, V);
1683  }
1684 
1685  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1686  // a non-vector type. We can instead bitcast the original vector followed by
1687  // an extract of the desired element:
1688  //
1689  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1690  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1691  // %1 = bitcast <4 x i8> %sroa to i32
1692  // Becomes:
1693  // %bc = bitcast <16 x i8> %in to <4 x i32>
1694  // %ext = extractelement <4 x i32> %bc, i32 0
1695  //
1696  // If the shuffle is extracting a contiguous range of values from the input
1697  // vector then each use which is a bitcast of the extracted size can be
1698  // replaced. This will work if the vector types are compatible, and the begin
1699  // index is aligned to a value in the casted vector type. If the begin index
1700  // isn't aligned then we can shuffle the original vector (keeping the same
1701  // vector type) before extracting.
1702  //
1703  // This code will bail out if the target type is fundamentally incompatible
1704  // with vectors of the source type.
1705  //
1706  // Example of <16 x i8>, target type i32:
1707  // Index range [4,8): v-----------v Will work.
1708  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1709  // <16 x i8>: | | | | | | | | | | | | | | | | |
1710  // <4 x i32>: | | | | |
1711  // +-----------+-----------+-----------+-----------+
1712  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1713  // Target type i40: ^--------------^ Won't work, bail.
1714  bool MadeChange = false;
1715  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1716  Value *V = LHS;
1717  unsigned MaskElems = Mask.size();
1718  VectorType *SrcTy = cast<VectorType>(V->getType());
1719  unsigned VecBitWidth = SrcTy->getBitWidth();
1720  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1721  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1722  unsigned SrcNumElems = SrcTy->getNumElements();
1725  for (User *U : SVI.users())
1726  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1727  if (!BC->use_empty())
1728  // Only visit bitcasts that weren't previously handled.
1729  BCs.push_back(BC);
1730  for (BitCastInst *BC : BCs) {
1731  unsigned BegIdx = Mask.front();
1732  Type *TgtTy = BC->getDestTy();
1733  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1734  if (!TgtElemBitWidth)
1735  continue;
1736  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1737  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1738  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1739  if (!VecBitWidthsEqual)
1740  continue;
1741  if (!VectorType::isValidElementType(TgtTy))
1742  continue;
1743  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1744  if (!BegIsAligned) {
1745  // Shuffle the input so [0,NumElements) contains the output, and
1746  // [NumElems,SrcNumElems) is undef.
1747  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1748  UndefValue::get(Int32Ty));
1749  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1750  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1751  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1752  ConstantVector::get(ShuffleMask),
1753  SVI.getName() + ".extract");
1754  BegIdx = 0;
1755  }
1756  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1757  assert(SrcElemsPerTgtElem);
1758  BegIdx /= SrcElemsPerTgtElem;
1759  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1760  auto *NewBC =
1761  BCAlreadyExists
1762  ? NewBCs[CastSrcTy]
1763  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1764  if (!BCAlreadyExists)
1765  NewBCs[CastSrcTy] = NewBC;
1766  auto *Ext = Builder.CreateExtractElement(
1767  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1768  // The shufflevector isn't being replaced: the bitcast that used it
1769  // is. InstCombine will visit the newly-created instructions.
1770  replaceInstUsesWith(*BC, Ext);
1771  MadeChange = true;
1772  }
1773  }
1774 
1775  // If the LHS is a shufflevector itself, see if we can combine it with this
1776  // one without producing an unusual shuffle.
1777  // Cases that might be simplified:
1778  // 1.
1779  // x1=shuffle(v1,v2,mask1)
1780  // x=shuffle(x1,undef,mask)
1781  // ==>
1782  // x=shuffle(v1,undef,newMask)
1783  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1784  // 2.
1785  // x1=shuffle(v1,undef,mask1)
1786  // x=shuffle(x1,x2,mask)
1787  // where v1.size() == mask1.size()
1788  // ==>
1789  // x=shuffle(v1,x2,newMask)
1790  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1791  // 3.
1792  // x2=shuffle(v2,undef,mask2)
1793  // x=shuffle(x1,x2,mask)
1794  // where v2.size() == mask2.size()
1795  // ==>
1796  // x=shuffle(x1,v2,newMask)
1797  // newMask[i] = (mask[i] < x1.size())
1798  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1799  // 4.
1800  // x1=shuffle(v1,undef,mask1)
1801  // x2=shuffle(v2,undef,mask2)
1802  // x=shuffle(x1,x2,mask)
1803  // where v1.size() == v2.size()
1804  // ==>
1805  // x=shuffle(v1,v2,newMask)
1806  // newMask[i] = (mask[i] < x1.size())
1807  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1808  //
1809  // Here we are really conservative:
1810  // we are absolutely afraid of producing a shuffle mask not in the input
1811  // program, because the code gen may not be smart enough to turn a merged
1812  // shuffle into two specific shuffles: it may produce worse code. As such,
1813  // we only merge two shuffles if the result is either a splat or one of the
1814  // input shuffle masks. In this case, merging the shuffles just removes
1815  // one instruction, which we know is safe. This is good for things like
1816  // turning: (splat(splat)) -> splat, or
1817  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1818  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1819  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1820  if (LHSShuffle)
1821  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1822  LHSShuffle = nullptr;
1823  if (RHSShuffle)
1824  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1825  RHSShuffle = nullptr;
1826  if (!LHSShuffle && !RHSShuffle)
1827  return MadeChange ? &SVI : nullptr;
1828 
1829  Value* LHSOp0 = nullptr;
1830  Value* LHSOp1 = nullptr;
1831  Value* RHSOp0 = nullptr;
1832  unsigned LHSOp0Width = 0;
1833  unsigned RHSOp0Width = 0;
1834  if (LHSShuffle) {
1835  LHSOp0 = LHSShuffle->getOperand(0);
1836  LHSOp1 = LHSShuffle->getOperand(1);
1837  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1838  }
1839  if (RHSShuffle) {
1840  RHSOp0 = RHSShuffle->getOperand(0);
1841  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1842  }
1843  Value* newLHS = LHS;
1844  Value* newRHS = RHS;
1845  if (LHSShuffle) {
1846  // case 1
1847  if (isa<UndefValue>(RHS)) {
1848  newLHS = LHSOp0;
1849  newRHS = LHSOp1;
1850  }
1851  // case 2 or 4
1852  else if (LHSOp0Width == LHSWidth) {
1853  newLHS = LHSOp0;
1854  }
1855  }
1856  // case 3 or 4
1857  if (RHSShuffle && RHSOp0Width == LHSWidth) {
1858  newRHS = RHSOp0;
1859  }
1860  // case 4
1861  if (LHSOp0 == RHSOp0) {
1862  newLHS = LHSOp0;
1863  newRHS = nullptr;
1864  }
1865 
1866  if (newLHS == LHS && newRHS == RHS)
1867  return MadeChange ? &SVI : nullptr;
1868 
1869  SmallVector<int, 16> LHSMask;
1870  SmallVector<int, 16> RHSMask;
1871  if (newLHS != LHS)
1872  LHSMask = LHSShuffle->getShuffleMask();
1873  if (RHSShuffle && newRHS != RHS)
1874  RHSMask = RHSShuffle->getShuffleMask();
1875 
1876  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1877  SmallVector<int, 16> newMask;
1878  bool isSplat = true;
1879  int SplatElt = -1;
1880  // Create a new mask for the new ShuffleVectorInst so that the new
1881  // ShuffleVectorInst is equivalent to the original one.
1882  for (unsigned i = 0; i < VWidth; ++i) {
1883  int eltMask;
1884  if (Mask[i] < 0) {
1885  // This element is an undef value.
1886  eltMask = -1;
1887  } else if (Mask[i] < (int)LHSWidth) {
1888  // This element is from left hand side vector operand.
1889  //
1890  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1891  // new mask value for the element.
1892  if (newLHS != LHS) {
1893  eltMask = LHSMask[Mask[i]];
1894  // If the value selected is an undef value, explicitly specify it
1895  // with a -1 mask value.
1896  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1897  eltMask = -1;
1898  } else
1899  eltMask = Mask[i];
1900  } else {
1901  // This element is from right hand side vector operand
1902  //
1903  // If the value selected is an undef value, explicitly specify it
1904  // with a -1 mask value. (case 1)
1905  if (isa<UndefValue>(RHS))
1906  eltMask = -1;
1907  // If RHS is going to be replaced (case 3 or 4), calculate the
1908  // new mask value for the element.
1909  else if (newRHS != RHS) {
1910  eltMask = RHSMask[Mask[i]-LHSWidth];
1911  // If the value selected is an undef value, explicitly specify it
1912  // with a -1 mask value.
1913  if (eltMask >= (int)RHSOp0Width) {
1914  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1915  && "should have been check above");
1916  eltMask = -1;
1917  }
1918  } else
1919  eltMask = Mask[i]-LHSWidth;
1920 
1921  // If LHS's width is changed, shift the mask value accordingly.
1922  // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
1923  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1924  // If newRHS == newLHS, we want to remap any references from newRHS to
1925  // newLHS so that we can properly identify splats that may occur due to
1926  // obfuscation across the two vectors.
1927  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1928  eltMask += newLHSWidth;
1929  }
1930 
1931  // Check if this could still be a splat.
1932  if (eltMask >= 0) {
1933  if (SplatElt >= 0 && SplatElt != eltMask)
1934  isSplat = false;
1935  SplatElt = eltMask;
1936  }
1937 
1938  newMask.push_back(eltMask);
1939  }
1940 
1941  // If the result mask is equal to one of the original shuffle masks,
1942  // or is a splat, do the replacement.
1943  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1945  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1946  if (newMask[i] < 0) {
1947  Elts.push_back(UndefValue::get(Int32Ty));
1948  } else {
1949  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1950  }
1951  }
1952  if (!newRHS)
1953  newRHS = UndefValue::get(newLHS->getType());
1954  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1955  }
1956 
1957  // If the result mask is an identity, replace uses of this instruction with
1958  // corresponding argument.
1959  bool isLHSID, isRHSID;
1960  recognizeIdentityMask(newMask, isLHSID, isRHSID);
1961  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1962  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1963 
1964  return MadeChange ? &SVI : nullptr;
1965 }
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:224
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:1341
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:709
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
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:416
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:344
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:2157
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:2335
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:1424
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 commute()
Swap the first 2 operands and adjust the mask to preserve the semantics of the instruction.
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:841
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:631
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:332
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:2318
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:1088
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.