LLVM  8.0.0svn
InstCombineVectorOps.cpp
Go to the documentation of this file.
1 //===- InstCombineVectorOps.cpp -------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements instcombine for ExtractElement, InsertElement and
11 // ShuffleVector.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "InstCombineInternal.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/IR/BasicBlock.h"
24 #include "llvm/IR/Constant.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/InstrTypes.h"
28 #include "llvm/IR/Instruction.h"
29 #include "llvm/IR/Instructions.h"
30 #include "llvm/IR/Operator.h"
31 #include "llvm/IR/PatternMatch.h"
32 #include "llvm/IR/Type.h"
33 #include "llvm/IR/User.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
38 #include <cassert>
39 #include <cstdint>
40 #include <iterator>
41 #include <utility>
42 
43 using namespace llvm;
44 using namespace PatternMatch;
45 
46 #define DEBUG_TYPE "instcombine"
47 
48 /// Return true if the value is cheaper to scalarize than it is to leave as a
49 /// vector operation. isConstant indicates whether we're extracting one known
50 /// element. If false we're extracting a variable index.
51 static bool cheapToScalarize(Value *V, bool isConstant) {
52  if (Constant *C = dyn_cast<Constant>(V)) {
53  if (isConstant) return true;
54 
55  // If all elts are the same, we can extract it and use any of the values.
56  if (Constant *Op0 = C->getAggregateElement(0U)) {
57  for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e;
58  ++i)
59  if (C->getAggregateElement(i) != Op0)
60  return false;
61  return true;
62  }
63  }
65  if (!I) return false;
66 
67  // Insert element gets simplified to the inserted element or is deleted if
68  // this is constant idx extract element and its a constant idx insertelt.
69  if (I->getOpcode() == Instruction::InsertElement && isConstant &&
70  isa<ConstantInt>(I->getOperand(2)))
71  return true;
72  if (I->getOpcode() == Instruction::Load && I->hasOneUse())
73  return true;
74  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
75  if (BO->hasOneUse() &&
76  (cheapToScalarize(BO->getOperand(0), isConstant) ||
77  cheapToScalarize(BO->getOperand(1), isConstant)))
78  return true;
79  if (CmpInst *CI = dyn_cast<CmpInst>(I))
80  if (CI->hasOneUse() &&
81  (cheapToScalarize(CI->getOperand(0), isConstant) ||
82  cheapToScalarize(CI->getOperand(1), isConstant)))
83  return true;
84 
85  return false;
86 }
87 
88 // If we have a PHI node with a vector type that is only used to feed
89 // itself and be an operand of extractelement at a constant location,
90 // try to replace the PHI of the vector type with a PHI of a scalar type.
91 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
93  // The users we want the PHI to have are:
94  // 1) The EI ExtractElement (we already know this)
95  // 2) Possibly more ExtractElements with the same index.
96  // 3) Another operand, which will feed back into the PHI.
97  Instruction *PHIUser = nullptr;
98  for (auto U : PN->users()) {
99  if (ExtractElementInst *EU = dyn_cast<ExtractElementInst>(U)) {
100  if (EI.getIndexOperand() == EU->getIndexOperand())
101  Extracts.push_back(EU);
102  else
103  return nullptr;
104  } else if (!PHIUser) {
105  PHIUser = cast<Instruction>(U);
106  } else {
107  return nullptr;
108  }
109  }
110 
111  if (!PHIUser)
112  return nullptr;
113 
114  // Verify that this PHI user has one use, which is the PHI itself,
115  // and that it is a binary operation which is cheap to scalarize.
116  // otherwise return nullptr.
117  if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
118  !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true))
119  return nullptr;
120 
121  // Create a scalar PHI node that will replace the vector PHI node
122  // just before the current PHI node.
123  PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
124  PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
125  // Scalarize each PHI operand.
126  for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
127  Value *PHIInVal = PN->getIncomingValue(i);
128  BasicBlock *inBB = PN->getIncomingBlock(i);
129  Value *Elt = EI.getIndexOperand();
130  // If the operand is the PHI induction variable:
131  if (PHIInVal == PHIUser) {
132  // Scalarize the binary operation. Its first operand is the
133  // scalar PHI, and the second operand is extracted from the other
134  // vector operand.
135  BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
136  unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
137  Value *Op = InsertNewInstWith(
138  ExtractElementInst::Create(B0->getOperand(opId), Elt,
139  B0->getOperand(opId)->getName() + ".Elt"),
140  *B0);
141  Value *newPHIUser = InsertNewInstWith(
143  scalarPHI, Op, B0), *B0);
144  scalarPHI->addIncoming(newPHIUser, inBB);
145  } else {
146  // Scalarize PHI input:
147  Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
148  // Insert the new instruction into the predecessor basic block.
149  Instruction *pos = dyn_cast<Instruction>(PHIInVal);
150  BasicBlock::iterator InsertPos;
151  if (pos && !isa<PHINode>(pos)) {
152  InsertPos = ++pos->getIterator();
153  } else {
154  InsertPos = inBB->getFirstInsertionPt();
155  }
156 
157  InsertNewInstWith(newEI, *InsertPos);
158 
159  scalarPHI->addIncoming(newEI, inBB);
160  }
161  }
162 
163  for (auto E : Extracts)
164  replaceInstUsesWith(*E, scalarPHI);
165 
166  return &EI;
167 }
168 
171  EI.getIndexOperand(),
172  SQ.getWithInstruction(&EI)))
173  return replaceInstUsesWith(EI, V);
174 
175  // If vector val is constant with all elements the same, replace EI with
176  // that element. We handle a known element # below.
177  if (Constant *C = dyn_cast<Constant>(EI.getOperand(0)))
178  if (cheapToScalarize(C, false))
179  return replaceInstUsesWith(EI, C->getAggregateElement(0U));
180 
181  // If extracting a specified index from the vector, see if we can recursively
182  // find a previously computed scalar that was inserted into the vector.
183  if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
184  unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
185 
186  // InstSimplify should handle cases where the index is invalid.
187  if (!IdxC->getValue().ule(VectorWidth))
188  return nullptr;
189 
190  unsigned IndexVal = IdxC->getZExtValue();
191 
192  // This instruction only demands the single element from the input vector.
193  // If the input vector has a single use, simplify it based on this use
194  // property.
195  if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
196  APInt UndefElts(VectorWidth, 0);
197  APInt DemandedMask(VectorWidth, 0);
198  DemandedMask.setBit(IndexVal);
199  if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask,
200  UndefElts)) {
201  EI.setOperand(0, V);
202  return &EI;
203  }
204  }
205 
206  // If this extractelement is directly using a bitcast from a vector of
207  // the same number of elements, see if we can find the source element from
208  // it. In this case, we will end up needing to bitcast the scalars.
209  if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
210  if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
211  if (VT->getNumElements() == VectorWidth)
212  if (Value *Elt = findScalarElement(BCI->getOperand(0), IndexVal))
213  return new BitCastInst(Elt, EI.getType());
214  }
215 
216  // If there's a vector PHI feeding a scalar use through this extractelement
217  // instruction, try to scalarize the PHI.
218  if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) {
219  Instruction *scalarPHI = scalarizePHI(EI, PN);
220  if (scalarPHI)
221  return scalarPHI;
222  }
223  }
224 
225  if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
226  // Push extractelement into predecessor operation if legal and
227  // profitable to do so.
228  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
229  if (I->hasOneUse() &&
230  cheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
231  Value *newEI0 =
232  Builder.CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
233  EI.getName()+".lhs");
234  Value *newEI1 =
235  Builder.CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
236  EI.getName()+".rhs");
237  return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(),
238  newEI0, newEI1, BO);
239  }
240  } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
241  // Extracting the inserted element?
242  if (IE->getOperand(2) == EI.getOperand(1))
243  return replaceInstUsesWith(EI, IE->getOperand(1));
244  // If the inserted and extracted elements are constants, they must not
245  // be the same value, extract from the pre-inserted value instead.
246  if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
247  Worklist.AddValue(EI.getOperand(0));
248  EI.setOperand(0, IE->getOperand(0));
249  return &EI;
250  }
251  } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
252  // If this is extracting an element from a shufflevector, figure out where
253  // it came from and extract from the appropriate input element instead.
254  if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
255  int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
256  Value *Src;
257  unsigned LHSWidth =
258  SVI->getOperand(0)->getType()->getVectorNumElements();
259 
260  if (SrcIdx < 0)
261  return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
262  if (SrcIdx < (int)LHSWidth)
263  Src = SVI->getOperand(0);
264  else {
265  SrcIdx -= LHSWidth;
266  Src = SVI->getOperand(1);
267  }
269  return ExtractElementInst::Create(Src,
270  ConstantInt::get(Int32Ty,
271  SrcIdx, false));
272  }
273  } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
274  // Canonicalize extractelement(cast) -> cast(extractelement).
275  // Bitcasts can change the number of vector elements, and they cost
276  // nothing.
277  if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
278  Value *EE = Builder.CreateExtractElement(CI->getOperand(0),
279  EI.getIndexOperand());
280  Worklist.AddValue(EE);
281  return CastInst::Create(CI->getOpcode(), EE, EI.getType());
282  }
283  }
284  }
285  return nullptr;
286 }
287 
288 /// If V is a shuffle of values that ONLY returns elements from either LHS or
289 /// RHS, return the shuffle mask and true. Otherwise, return false.
290 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
292  assert(LHS->getType() == RHS->getType() &&
293  "Invalid CollectSingleShuffleElements");
294  unsigned NumElts = V->getType()->getVectorNumElements();
295 
296  if (isa<UndefValue>(V)) {
297  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
298  return true;
299  }
300 
301  if (V == LHS) {
302  for (unsigned i = 0; i != NumElts; ++i)
304  return true;
305  }
306 
307  if (V == RHS) {
308  for (unsigned i = 0; i != NumElts; ++i)
310  i+NumElts));
311  return true;
312  }
313 
314  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
315  // If this is an insert of an extract from some other vector, include it.
316  Value *VecOp = IEI->getOperand(0);
317  Value *ScalarOp = IEI->getOperand(1);
318  Value *IdxOp = IEI->getOperand(2);
319 
320  if (!isa<ConstantInt>(IdxOp))
321  return false;
322  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
323 
324  if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector.
325  // We can handle this if the vector we are inserting into is
326  // transitively ok.
327  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
328  // If so, update the mask to reflect the inserted undef.
329  Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
330  return true;
331  }
332  } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
333  if (isa<ConstantInt>(EI->getOperand(1))) {
334  unsigned ExtractedIdx =
335  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
336  unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
337 
338  // This must be extracting from either LHS or RHS.
339  if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
340  // We can handle this if the vector we are inserting into is
341  // transitively ok.
342  if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
343  // If so, update the mask to reflect the inserted value.
344  if (EI->getOperand(0) == LHS) {
345  Mask[InsertedIdx % NumElts] =
347  ExtractedIdx);
348  } else {
349  assert(EI->getOperand(0) == RHS);
350  Mask[InsertedIdx % NumElts] =
352  ExtractedIdx + NumLHSElts);
353  }
354  return true;
355  }
356  }
357  }
358  }
359  }
360 
361  return false;
362 }
363 
364 /// If we have insertion into a vector that is wider than the vector that we
365 /// are extracting from, try to widen the source vector to allow a single
366 /// shufflevector to replace one or more insert/extract pairs.
368  ExtractElementInst *ExtElt,
369  InstCombiner &IC) {
370  VectorType *InsVecType = InsElt->getType();
371  VectorType *ExtVecType = ExtElt->getVectorOperandType();
372  unsigned NumInsElts = InsVecType->getVectorNumElements();
373  unsigned NumExtElts = ExtVecType->getVectorNumElements();
374 
375  // The inserted-to vector must be wider than the extracted-from vector.
376  if (InsVecType->getElementType() != ExtVecType->getElementType() ||
377  NumExtElts >= NumInsElts)
378  return;
379 
380  // Create a shuffle mask to widen the extended-from vector using undefined
381  // values. The mask selects all of the values of the original vector followed
382  // by as many undefined values as needed to create a vector of the same length
383  // as the inserted-to vector.
384  SmallVector<Constant *, 16> ExtendMask;
385  IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
386  for (unsigned i = 0; i < NumExtElts; ++i)
387  ExtendMask.push_back(ConstantInt::get(IntType, i));
388  for (unsigned i = NumExtElts; i < NumInsElts; ++i)
389  ExtendMask.push_back(UndefValue::get(IntType));
390 
391  Value *ExtVecOp = ExtElt->getVectorOperand();
392  auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
393  BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
394  ? ExtVecOpInst->getParent()
395  : ExtElt->getParent();
396 
397  // TODO: This restriction matches the basic block check below when creating
398  // new extractelement instructions. If that limitation is removed, this one
399  // could also be removed. But for now, we just bail out to ensure that we
400  // will replace the extractelement instruction that is feeding our
401  // insertelement instruction. This allows the insertelement to then be
402  // replaced by a shufflevector. If the insertelement is not replaced, we can
403  // induce infinite looping because there's an optimization for extractelement
404  // that will delete our widening shuffle. This would trigger another attempt
405  // here to create that shuffle, and we spin forever.
406  if (InsertionBlock != InsElt->getParent())
407  return;
408 
409  // TODO: This restriction matches the check in visitInsertElementInst() and
410  // prevents an infinite loop caused by not turning the extract/insert pair
411  // into a shuffle. We really should not need either check, but we're lacking
412  // folds for shufflevectors because we're afraid to generate shuffle masks
413  // that the backend can't handle.
414  if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
415  return;
416 
417  auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
418  ConstantVector::get(ExtendMask));
419 
420  // Insert the new shuffle after the vector operand of the extract is defined
421  // (as long as it's not a PHI) or at the start of the basic block of the
422  // extract, so any subsequent extracts in the same basic block can use it.
423  // TODO: Insert before the earliest ExtractElementInst that is replaced.
424  if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
425  WideVec->insertAfter(ExtVecOpInst);
426  else
427  IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
428 
429  // Replace extracts from the original narrow vector with extracts from the new
430  // wide vector.
431  for (User *U : ExtVecOp->users()) {
433  if (!OldExt || OldExt->getParent() != WideVec->getParent())
434  continue;
435  auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
436  NewExt->insertAfter(OldExt);
437  IC.replaceInstUsesWith(*OldExt, NewExt);
438  }
439 }
440 
441 /// We are building a shuffle to create V, which is a sequence of insertelement,
442 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
443 /// not rely on the second vector source. Return a std::pair containing the
444 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
445 /// parameter as required.
446 ///
447 /// Note: we intentionally don't try to fold earlier shuffles since they have
448 /// often been chosen carefully to be efficiently implementable on the target.
449 using ShuffleOps = std::pair<Value *, Value *>;
450 
453  Value *PermittedRHS,
454  InstCombiner &IC) {
455  assert(V->getType()->isVectorTy() && "Invalid shuffle!");
456  unsigned NumElts = V->getType()->getVectorNumElements();
457 
458  if (isa<UndefValue>(V)) {
459  Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
460  return std::make_pair(
461  PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
462  }
463 
464  if (isa<ConstantAggregateZero>(V)) {
465  Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
466  return std::make_pair(V, nullptr);
467  }
468 
469  if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
470  // If this is an insert of an extract from some other vector, include it.
471  Value *VecOp = IEI->getOperand(0);
472  Value *ScalarOp = IEI->getOperand(1);
473  Value *IdxOp = IEI->getOperand(2);
474 
475  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
476  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
477  unsigned ExtractedIdx =
478  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
479  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
480 
481  // Either the extracted from or inserted into vector must be RHSVec,
482  // otherwise we'd end up with a shuffle of three inputs.
483  if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
484  Value *RHS = EI->getOperand(0);
485  ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
486  assert(LR.second == nullptr || LR.second == RHS);
487 
488  if (LR.first->getType() != RHS->getType()) {
489  // Although we are giving up for now, see if we can create extracts
490  // that match the inserts for another round of combining.
491  replaceExtractElements(IEI, EI, IC);
492 
493  // We tried our best, but we can't find anything compatible with RHS
494  // further up the chain. Return a trivial shuffle.
495  for (unsigned i = 0; i < NumElts; ++i)
496  Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
497  return std::make_pair(V, nullptr);
498  }
499 
500  unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
501  Mask[InsertedIdx % NumElts] =
503  NumLHSElts+ExtractedIdx);
504  return std::make_pair(LR.first, RHS);
505  }
506 
507  if (VecOp == PermittedRHS) {
508  // We've gone as far as we can: anything on the other side of the
509  // extractelement will already have been converted into a shuffle.
510  unsigned NumLHSElts =
512  for (unsigned i = 0; i != NumElts; ++i)
515  i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
516  return std::make_pair(EI->getOperand(0), PermittedRHS);
517  }
518 
519  // If this insertelement is a chain that comes from exactly these two
520  // vectors, return the vector and the effective shuffle.
521  if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
522  collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
523  Mask))
524  return std::make_pair(EI->getOperand(0), PermittedRHS);
525  }
526  }
527  }
528 
529  // Otherwise, we can't do anything fancy. Return an identity vector.
530  for (unsigned i = 0; i != NumElts; ++i)
532  return std::make_pair(V, nullptr);
533 }
534 
535 /// Try to find redundant insertvalue instructions, like the following ones:
536 /// %0 = insertvalue { i8, i32 } undef, i8 %x, 0
537 /// %1 = insertvalue { i8, i32 } %0, i8 %y, 0
538 /// Here the second instruction inserts values at the same indices, as the
539 /// first one, making the first one redundant.
540 /// It should be transformed to:
541 /// %0 = insertvalue { i8, i32 } undef, i8 %y, 0
543  bool IsRedundant = false;
544  ArrayRef<unsigned int> FirstIndices = I.getIndices();
545 
546  // If there is a chain of insertvalue instructions (each of them except the
547  // last one has only one use and it's another insertvalue insn from this
548  // chain), check if any of the 'children' uses the same indices as the first
549  // instruction. In this case, the first one is redundant.
550  Value *V = &I;
551  unsigned Depth = 0;
552  while (V->hasOneUse() && Depth < 10) {
553  User *U = V->user_back();
554  auto UserInsInst = dyn_cast<InsertValueInst>(U);
555  if (!UserInsInst || U->getOperand(0) != V)
556  break;
557  if (UserInsInst->getIndices() == FirstIndices) {
558  IsRedundant = true;
559  break;
560  }
561  V = UserInsInst;
562  Depth++;
563  }
564 
565  if (IsRedundant)
566  return replaceInstUsesWith(I, I.getOperand(0));
567  return nullptr;
568 }
569 
571  int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
572  int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
573 
574  // A vector select does not change the size of the operands.
575  if (MaskSize != VecSize)
576  return false;
577 
578  // Each mask element must be undefined or choose a vector element from one of
579  // the source operands without crossing vector lanes.
580  for (int i = 0; i != MaskSize; ++i) {
581  int Elt = Shuf.getMaskValue(i);
582  if (Elt != -1 && Elt != i && Elt != i + VecSize)
583  return false;
584  }
585 
586  return true;
587 }
588 
589 // Turn a chain of inserts that splats a value into a canonical insert + shuffle
590 // splat. That is:
591 // insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
592 // shufflevector(insertelt(X, %k, 0), undef, zero)
594  // We are interested in the last insert in a chain. So, if this insert
595  // has a single user, and that user is an insert, bail.
596  if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
597  return nullptr;
598 
599  VectorType *VT = cast<VectorType>(InsElt.getType());
600  int NumElements = VT->getNumElements();
601 
602  // Do not try to do this for a one-element vector, since that's a nop,
603  // and will cause an inf-loop.
604  if (NumElements == 1)
605  return nullptr;
606 
607  Value *SplatVal = InsElt.getOperand(1);
608  InsertElementInst *CurrIE = &InsElt;
609  SmallVector<bool, 16> ElementPresent(NumElements, false);
610  InsertElementInst *FirstIE = nullptr;
611 
612  // Walk the chain backwards, keeping track of which indices we inserted into,
613  // until we hit something that isn't an insert of the splatted value.
614  while (CurrIE) {
615  auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
616  if (!Idx || CurrIE->getOperand(1) != SplatVal)
617  return nullptr;
618 
619  auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
620  // Check none of the intermediate steps have any additional uses, except
621  // for the root insertelement instruction, which can be re-used, if it
622  // inserts at position 0.
623  if (CurrIE != &InsElt &&
624  (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
625  return nullptr;
626 
627  ElementPresent[Idx->getZExtValue()] = true;
628  FirstIE = CurrIE;
629  CurrIE = NextIE;
630  }
631 
632  // Make sure we've seen an insert into every element.
633  if (llvm::any_of(ElementPresent, [](bool Present) { return !Present; }))
634  return nullptr;
635 
636  // All right, create the insert + shuffle.
637  Instruction *InsertFirst;
638  if (cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
639  InsertFirst = FirstIE;
640  else
641  InsertFirst = InsertElementInst::Create(
642  UndefValue::get(VT), SplatVal,
644  "", &InsElt);
645 
647  VectorType::get(Type::getInt32Ty(InsElt.getContext()), NumElements));
648 
649  return new ShuffleVectorInst(InsertFirst, UndefValue::get(VT), ZeroMask);
650 }
651 
652 /// If we have an insertelement instruction feeding into another insertelement
653 /// and the 2nd is inserting a constant into the vector, canonicalize that
654 /// constant insertion before the insertion of a variable:
655 ///
656 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
657 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
658 ///
659 /// This has the potential of eliminating the 2nd insertelement instruction
660 /// via constant folding of the scalar constant into a vector constant.
662  InstCombiner::BuilderTy &Builder) {
663  auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
664  if (!InsElt1 || !InsElt1->hasOneUse())
665  return nullptr;
666 
667  Value *X, *Y;
668  Constant *ScalarC;
669  ConstantInt *IdxC1, *IdxC2;
670  if (match(InsElt1->getOperand(0), m_Value(X)) &&
671  match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
672  match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
673  match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
674  match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
675  Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
676  return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
677  }
678 
679  return nullptr;
680 }
681 
682 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
683 /// --> shufflevector X, CVec', Mask'
685  auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
686  // Bail out if the parent has more than one use. In that case, we'd be
687  // replacing the insertelt with a shuffle, and that's not a clear win.
688  if (!Inst || !Inst->hasOneUse())
689  return nullptr;
690  if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
691  // The shuffle must have a constant vector operand. The insertelt must have
692  // a constant scalar being inserted at a constant position in the vector.
693  Constant *ShufConstVec, *InsEltScalar;
694  uint64_t InsEltIndex;
695  if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
696  !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
697  !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
698  return nullptr;
699 
700  // Adding an element to an arbitrary shuffle could be expensive, but a
701  // shuffle that selects elements from vectors without crossing lanes is
702  // assumed cheap.
703  // If we're just adding a constant into that shuffle, it will still be
704  // cheap.
705  if (!isShuffleEquivalentToSelect(*Shuf))
706  return nullptr;
707 
708  // From the above 'select' check, we know that the mask has the same number
709  // of elements as the vector input operands. We also know that each constant
710  // input element is used in its lane and can not be used more than once by
711  // the shuffle. Therefore, replace the constant in the shuffle's constant
712  // vector with the insertelt constant. Replace the constant in the shuffle's
713  // mask vector with the insertelt index plus the length of the vector
714  // (because the constant vector operand of a shuffle is always the 2nd
715  // operand).
716  Constant *Mask = Shuf->getMask();
717  unsigned NumElts = Mask->getType()->getVectorNumElements();
718  SmallVector<Constant *, 16> NewShufElts(NumElts);
719  SmallVector<Constant *, 16> NewMaskElts(NumElts);
720  for (unsigned I = 0; I != NumElts; ++I) {
721  if (I == InsEltIndex) {
722  NewShufElts[I] = InsEltScalar;
723  Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
724  NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
725  } else {
726  // Copy over the existing values.
727  NewShufElts[I] = ShufConstVec->getAggregateElement(I);
728  NewMaskElts[I] = Mask->getAggregateElement(I);
729  }
730  }
731 
732  // Create new operands for a shuffle that includes the constant of the
733  // original insertelt. The old shuffle will be dead now.
734  return new ShuffleVectorInst(Shuf->getOperand(0),
735  ConstantVector::get(NewShufElts),
736  ConstantVector::get(NewMaskElts));
737  } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
738  // Transform sequences of insertelements ops with constant data/indexes into
739  // a single shuffle op.
740  unsigned NumElts = InsElt.getType()->getNumElements();
741 
742  uint64_t InsertIdx[2];
743  Constant *Val[2];
744  if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
745  !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
746  !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
747  !match(IEI->getOperand(1), m_Constant(Val[1])))
748  return nullptr;
749  SmallVector<Constant *, 16> Values(NumElts);
751  auto ValI = std::begin(Val);
752  // Generate new constant vector and mask.
753  // We have 2 values/masks from the insertelements instructions. Insert them
754  // into new value/mask vectors.
755  for (uint64_t I : InsertIdx) {
756  if (!Values[I]) {
757  assert(!Mask[I]);
758  Values[I] = *ValI;
759  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
760  NumElts + I);
761  }
762  ++ValI;
763  }
764  // Remaining values are filled with 'undef' values.
765  for (unsigned I = 0; I < NumElts; ++I) {
766  if (!Values[I]) {
767  assert(!Mask[I]);
768  Values[I] = UndefValue::get(InsElt.getType()->getElementType());
769  Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
770  }
771  }
772  // Create new operands for a shuffle that includes the constant of the
773  // original insertelt.
774  return new ShuffleVectorInst(IEI->getOperand(0),
775  ConstantVector::get(Values),
776  ConstantVector::get(Mask));
777  }
778  return nullptr;
779 }
780 
782  Value *VecOp = IE.getOperand(0);
783  Value *ScalarOp = IE.getOperand(1);
784  Value *IdxOp = IE.getOperand(2);
785 
786  if (auto *V = SimplifyInsertElementInst(
787  VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
788  return replaceInstUsesWith(IE, V);
789 
790  // Inserting an undef or into an undefined place, remove this.
791  if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
792  replaceInstUsesWith(IE, VecOp);
793 
794  // If the inserted element was extracted from some other vector, and if the
795  // indexes are constant, try to turn this into a shufflevector operation.
796  if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
797  if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
798  unsigned NumInsertVectorElts = IE.getType()->getNumElements();
799  unsigned NumExtractVectorElts =
801  unsigned ExtractedIdx =
802  cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
803  unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
804 
805  if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
806  return replaceInstUsesWith(IE, VecOp);
807 
808  if (InsertedIdx >= NumInsertVectorElts) // Out of range insert.
809  return replaceInstUsesWith(IE, UndefValue::get(IE.getType()));
810 
811  // If we are extracting a value from a vector, then inserting it right
812  // back into the same place, just use the input vector.
813  if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
814  return replaceInstUsesWith(IE, VecOp);
815 
816  // If this insertelement isn't used by some other insertelement, turn it
817  // (and any insertelements it points to), into one big shuffle.
818  if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) {
820  ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
821 
822  // The proposed shuffle may be trivial, in which case we shouldn't
823  // perform the combine.
824  if (LR.first != &IE && LR.second != &IE) {
825  // We now have a shuffle of LHS, RHS, Mask.
826  if (LR.second == nullptr)
827  LR.second = UndefValue::get(LR.first->getType());
828  return new ShuffleVectorInst(LR.first, LR.second,
829  ConstantVector::get(Mask));
830  }
831  }
832  }
833  }
834 
835  unsigned VWidth = VecOp->getType()->getVectorNumElements();
836  APInt UndefElts(VWidth, 0);
837  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
838  if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
839  if (V != &IE)
840  return replaceInstUsesWith(IE, V);
841  return &IE;
842  }
843 
845  return Shuf;
846 
847  if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
848  return NewInsElt;
849 
850  // Turn a sequence of inserts that broadcasts a scalar into a single
851  // insert + shufflevector.
852  if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE))
853  return Broadcast;
854 
855  return nullptr;
856 }
857 
858 /// Return true if we can evaluate the specified expression tree if the vector
859 /// elements were shuffled in a different order.
861  unsigned Depth = 5) {
862  // We can always reorder the elements of a constant.
863  if (isa<Constant>(V))
864  return true;
865 
866  // We won't reorder vector arguments. No IPO here.
868  if (!I) return false;
869 
870  // Two users may expect different orders of the elements. Don't try it.
871  if (!I->hasOneUse())
872  return false;
873 
874  if (Depth == 0) return false;
875 
876  switch (I->getOpcode()) {
877  case Instruction::Add:
878  case Instruction::FAdd:
879  case Instruction::Sub:
880  case Instruction::FSub:
881  case Instruction::Mul:
882  case Instruction::FMul:
883  case Instruction::UDiv:
884  case Instruction::SDiv:
885  case Instruction::FDiv:
886  case Instruction::URem:
887  case Instruction::SRem:
888  case Instruction::FRem:
889  case Instruction::Shl:
890  case Instruction::LShr:
891  case Instruction::AShr:
892  case Instruction::And:
893  case Instruction::Or:
894  case Instruction::Xor:
895  case Instruction::ICmp:
896  case Instruction::FCmp:
897  case Instruction::Trunc:
898  case Instruction::ZExt:
899  case Instruction::SExt:
900  case Instruction::FPToUI:
901  case Instruction::FPToSI:
902  case Instruction::UIToFP:
903  case Instruction::SIToFP:
904  case Instruction::FPTrunc:
905  case Instruction::FPExt:
906  case Instruction::GetElementPtr: {
907  for (Value *Operand : I->operands()) {
908  if (!CanEvaluateShuffled(Operand, Mask, Depth-1))
909  return false;
910  }
911  return true;
912  }
913  case Instruction::InsertElement: {
915  if (!CI) return false;
916  int ElementNumber = CI->getLimitedValue();
917 
918  // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
919  // can't put an element into multiple indices.
920  bool SeenOnce = false;
921  for (int i = 0, e = Mask.size(); i != e; ++i) {
922  if (Mask[i] == ElementNumber) {
923  if (SeenOnce)
924  return false;
925  SeenOnce = true;
926  }
927  }
928  return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1);
929  }
930  }
931  return false;
932 }
933 
934 /// Rebuild a new instruction just like 'I' but with the new operands given.
935 /// In the event of type mismatch, the type of the operands is correct.
937  // We don't want to use the IRBuilder here because we want the replacement
938  // instructions to appear next to 'I', not the builder's insertion point.
939  switch (I->getOpcode()) {
940  case Instruction::Add:
941  case Instruction::FAdd:
942  case Instruction::Sub:
943  case Instruction::FSub:
944  case Instruction::Mul:
945  case Instruction::FMul:
946  case Instruction::UDiv:
947  case Instruction::SDiv:
948  case Instruction::FDiv:
949  case Instruction::URem:
950  case Instruction::SRem:
951  case Instruction::FRem:
952  case Instruction::Shl:
953  case Instruction::LShr:
954  case Instruction::AShr:
955  case Instruction::And:
956  case Instruction::Or:
957  case Instruction::Xor: {
958  BinaryOperator *BO = cast<BinaryOperator>(I);
959  assert(NewOps.size() == 2 && "binary operator with #ops != 2");
961  BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
962  NewOps[0], NewOps[1], "", BO);
963  if (isa<OverflowingBinaryOperator>(BO)) {
964  New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
965  New->setHasNoSignedWrap(BO->hasNoSignedWrap());
966  }
967  if (isa<PossiblyExactOperator>(BO)) {
968  New->setIsExact(BO->isExact());
969  }
970  if (isa<FPMathOperator>(BO))
971  New->copyFastMathFlags(I);
972  return New;
973  }
974  case Instruction::ICmp:
975  assert(NewOps.size() == 2 && "icmp with #ops != 2");
976  return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
977  NewOps[0], NewOps[1]);
978  case Instruction::FCmp:
979  assert(NewOps.size() == 2 && "fcmp with #ops != 2");
980  return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
981  NewOps[0], NewOps[1]);
982  case Instruction::Trunc:
983  case Instruction::ZExt:
984  case Instruction::SExt:
985  case Instruction::FPToUI:
986  case Instruction::FPToSI:
987  case Instruction::UIToFP:
988  case Instruction::SIToFP:
989  case Instruction::FPTrunc:
990  case Instruction::FPExt: {
991  // It's possible that the mask has a different number of elements from
992  // the original cast. We recompute the destination type to match the mask.
993  Type *DestTy =
995  NewOps[0]->getType()->getVectorNumElements());
996  assert(NewOps.size() == 1 && "cast with #ops != 1");
997  return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
998  "", I);
999  }
1000  case Instruction::GetElementPtr: {
1001  Value *Ptr = NewOps[0];
1002  ArrayRef<Value*> Idx = NewOps.slice(1);
1004  cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1005  GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1006  return GEP;
1007  }
1008  }
1009  llvm_unreachable("failed to rebuild vector instructions");
1010 }
1011 
1012 Value *
1013 InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
1014  // Mask.size() does not need to be equal to the number of vector elements.
1015 
1016  assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1017  Type *EltTy = V->getType()->getScalarType();
1018  if (isa<UndefValue>(V))
1019  return UndefValue::get(VectorType::get(EltTy, Mask.size()));
1020 
1021  if (isa<ConstantAggregateZero>(V))
1022  return ConstantAggregateZero::get(VectorType::get(EltTy, Mask.size()));
1023 
1024  if (Constant *C = dyn_cast<Constant>(V)) {
1025  SmallVector<Constant *, 16> MaskValues;
1026  for (int i = 0, e = Mask.size(); i != e; ++i) {
1027  if (Mask[i] == -1)
1028  MaskValues.push_back(UndefValue::get(Builder.getInt32Ty()));
1029  else
1030  MaskValues.push_back(Builder.getInt32(Mask[i]));
1031  }
1033  ConstantVector::get(MaskValues));
1034  }
1035 
1036  Instruction *I = cast<Instruction>(V);
1037  switch (I->getOpcode()) {
1038  case Instruction::Add:
1039  case Instruction::FAdd:
1040  case Instruction::Sub:
1041  case Instruction::FSub:
1042  case Instruction::Mul:
1043  case Instruction::FMul:
1044  case Instruction::UDiv:
1045  case Instruction::SDiv:
1046  case Instruction::FDiv:
1047  case Instruction::URem:
1048  case Instruction::SRem:
1049  case Instruction::FRem:
1050  case Instruction::Shl:
1051  case Instruction::LShr:
1052  case Instruction::AShr:
1053  case Instruction::And:
1054  case Instruction::Or:
1055  case Instruction::Xor:
1056  case Instruction::ICmp:
1057  case Instruction::FCmp:
1058  case Instruction::Trunc:
1059  case Instruction::ZExt:
1060  case Instruction::SExt:
1061  case Instruction::FPToUI:
1062  case Instruction::FPToSI:
1063  case Instruction::UIToFP:
1064  case Instruction::SIToFP:
1065  case Instruction::FPTrunc:
1066  case Instruction::FPExt:
1067  case Instruction::Select:
1068  case Instruction::GetElementPtr: {
1069  SmallVector<Value*, 8> NewOps;
1070  bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1071  for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1072  Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask);
1073  NewOps.push_back(V);
1074  NeedsRebuild |= (V != I->getOperand(i));
1075  }
1076  if (NeedsRebuild) {
1077  return buildNew(I, NewOps);
1078  }
1079  return I;
1080  }
1081  case Instruction::InsertElement: {
1082  int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1083 
1084  // The insertelement was inserting at Element. Figure out which element
1085  // that becomes after shuffling. The answer is guaranteed to be unique
1086  // by CanEvaluateShuffled.
1087  bool Found = false;
1088  int Index = 0;
1089  for (int e = Mask.size(); Index != e; ++Index) {
1090  if (Mask[Index] == Element) {
1091  Found = true;
1092  break;
1093  }
1094  }
1095 
1096  // If element is not in Mask, no need to handle the operand 1 (element to
1097  // be inserted). Just evaluate values in operand 0 according to Mask.
1098  if (!Found)
1099  return EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1100 
1101  Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1102  return InsertElementInst::Create(V, I->getOperand(1),
1103  Builder.getInt32(Index), "", I);
1104  }
1105  }
1106  llvm_unreachable("failed to reorder elements of vector instruction!");
1107 }
1108 
1110  bool &isLHSID, bool &isRHSID) {
1111  isLHSID = isRHSID = true;
1112 
1113  for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1114  if (Mask[i] < 0) continue; // Ignore undef values.
1115  // Is this an identity shuffle of the LHS value?
1116  isLHSID &= (Mask[i] == (int)i);
1117 
1118  // Is this an identity shuffle of the RHS value?
1119  isRHSID &= (Mask[i]-e == i);
1120  }
1121 }
1122 
1123 // Returns true if the shuffle is extracting a contiguous range of values from
1124 // LHS, for example:
1125 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1126 // Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1127 // Shuffles to: |EE|FF|GG|HH|
1128 // +--+--+--+--+
1130  SmallVector<int, 16> &Mask) {
1131  unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1132  unsigned MaskElems = Mask.size();
1133  unsigned BegIdx = Mask.front();
1134  unsigned EndIdx = Mask.back();
1135  if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1136  return false;
1137  for (unsigned I = 0; I != MaskElems; ++I)
1138  if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1139  return false;
1140  return true;
1141 }
1142 
1143 /// These are the ingredients in an alternate form binary operator as described
1144 /// below.
1145 struct BinopElts {
1150  Value *V0 = nullptr, Value *V1 = nullptr) :
1151  Opcode(Opc), Op0(V0), Op1(V1) {}
1152  operator bool() const { return Opcode != 0; }
1153 };
1154 
1155 /// Binops may be transformed into binops with different opcodes and operands.
1156 /// Reverse the usual canonicalization to enable folds with the non-canonical
1157 /// form of the binop. If a transform is possible, return the elements of the
1158 /// new binop. If not, return invalid elements.
1160  Value *BO0 = BO->getOperand(0), *BO1 = BO->getOperand(1);
1161  Type *Ty = BO->getType();
1162  switch (BO->getOpcode()) {
1163  case Instruction::Shl: {
1164  // shl X, C --> mul X, (1 << C)
1165  Constant *C;
1166  if (match(BO1, m_Constant(C))) {
1167  Constant *ShlOne = ConstantExpr::getShl(ConstantInt::get(Ty, 1), C);
1168  return { Instruction::Mul, BO0, ShlOne };
1169  }
1170  break;
1171  }
1172  case Instruction::Or: {
1173  // or X, C --> add X, C (when X and C have no common bits set)
1174  const APInt *C;
1175  if (match(BO1, m_APInt(C)) && MaskedValueIsZero(BO0, *C, DL))
1176  return { Instruction::Add, BO0, BO1 };
1177  break;
1178  }
1179  default:
1180  break;
1181  }
1182  return {};
1183 }
1184 
1186  assert(Shuf.isSelect() && "Must have select-equivalent shuffle");
1187 
1188  // Are we shuffling together some value and that same value after it has been
1189  // modified by a binop with a constant?
1190  Value *Op0 = Shuf.getOperand(0), *Op1 = Shuf.getOperand(1);
1191  Constant *C;
1192  bool Op0IsBinop;
1193  if (match(Op0, m_BinOp(m_Specific(Op1), m_Constant(C))))
1194  Op0IsBinop = true;
1195  else if (match(Op1, m_BinOp(m_Specific(Op0), m_Constant(C))))
1196  Op0IsBinop = false;
1197  else
1198  return nullptr;
1199 
1200  // The identity constant for a binop leaves a variable operand unchanged. For
1201  // a vector, this is a splat of something like 0, -1, or 1.
1202  // If there's no identity constant for this binop, we're done.
1203  auto *BO = cast<BinaryOperator>(Op0IsBinop ? Op0 : Op1);
1204  BinaryOperator::BinaryOps BOpcode = BO->getOpcode();
1205  Constant *IdC = ConstantExpr::getBinOpIdentity(BOpcode, Shuf.getType(), true);
1206  if (!IdC)
1207  return nullptr;
1208 
1209  // Shuffle identity constants into the lanes that return the original value.
1210  // Example: shuf (mul X, {-1,-2,-3,-4}), X, {0,5,6,3} --> mul X, {-1,1,1,-4}
1211  // Example: shuf X, (add X, {-1,-2,-3,-4}), {0,1,6,7} --> add X, {0,0,-3,-4}
1212  // The existing binop constant vector remains in the same operand position.
1213  Constant *Mask = Shuf.getMask();
1214  Constant *NewC = Op0IsBinop ? ConstantExpr::getShuffleVector(C, IdC, Mask) :
1215  ConstantExpr::getShuffleVector(IdC, C, Mask);
1216 
1217  bool MightCreatePoisonOrUB =
1218  Mask->containsUndefElement() &&
1219  (Instruction::isIntDivRem(BOpcode) || Instruction::isShift(BOpcode));
1220  if (MightCreatePoisonOrUB)
1221  NewC = getSafeVectorConstantForBinop(BOpcode, NewC, true);
1222 
1223  // shuf (bop X, C), X, M --> bop X, C'
1224  // shuf X, (bop X, C), M --> bop X, C'
1225  Value *X = Op0IsBinop ? Op1 : Op0;
1226  Instruction *NewBO = BinaryOperator::Create(BOpcode, X, NewC);
1227  NewBO->copyIRFlags(BO);
1228 
1229  // An undef shuffle mask element may propagate as an undef constant element in
1230  // the new binop. That would produce poison where the original code might not.
1231  // If we already made a safe constant, then there's no danger.
1232  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1233  NewBO->dropPoisonGeneratingFlags();
1234  return NewBO;
1235 }
1236 
1237 /// Try to fold shuffles that are the equivalent of a vector select.
1239  InstCombiner::BuilderTy &Builder,
1240  const DataLayout &DL) {
1241  if (!Shuf.isSelect())
1242  return nullptr;
1243 
1245  return I;
1246 
1247  BinaryOperator *B0, *B1;
1248  if (!match(Shuf.getOperand(0), m_BinOp(B0)) ||
1249  !match(Shuf.getOperand(1), m_BinOp(B1)))
1250  return nullptr;
1251 
1252  Value *X, *Y;
1253  Constant *C0, *C1;
1254  bool ConstantsAreOp1;
1255  if (match(B0, m_BinOp(m_Value(X), m_Constant(C0))) &&
1256  match(B1, m_BinOp(m_Value(Y), m_Constant(C1))))
1257  ConstantsAreOp1 = true;
1258  else if (match(B0, m_BinOp(m_Constant(C0), m_Value(X))) &&
1259  match(B1, m_BinOp(m_Constant(C1), m_Value(Y))))
1260  ConstantsAreOp1 = false;
1261  else
1262  return nullptr;
1263 
1264  // We need matching binops to fold the lanes together.
1265  BinaryOperator::BinaryOps Opc0 = B0->getOpcode();
1266  BinaryOperator::BinaryOps Opc1 = B1->getOpcode();
1267  bool DropNSW = false;
1268  if (ConstantsAreOp1 && Opc0 != Opc1) {
1269  // TODO: We drop "nsw" if shift is converted into multiply because it may
1270  // not be correct when the shift amount is BitWidth - 1. We could examine
1271  // each vector element to determine if it is safe to keep that flag.
1272  if (Opc0 == Instruction::Shl || Opc1 == Instruction::Shl)
1273  DropNSW = true;
1274  if (BinopElts AltB0 = getAlternateBinop(B0, DL)) {
1275  assert(isa<Constant>(AltB0.Op1) && "Expecting constant with alt binop");
1276  Opc0 = AltB0.Opcode;
1277  C0 = cast<Constant>(AltB0.Op1);
1278  } else if (BinopElts AltB1 = getAlternateBinop(B1, DL)) {
1279  assert(isa<Constant>(AltB1.Op1) && "Expecting constant with alt binop");
1280  Opc1 = AltB1.Opcode;
1281  C1 = cast<Constant>(AltB1.Op1);
1282  }
1283  }
1284 
1285  if (Opc0 != Opc1)
1286  return nullptr;
1287 
1288  // The opcodes must be the same. Use a new name to make that clear.
1289  BinaryOperator::BinaryOps BOpc = Opc0;
1290 
1291  // Select the constant elements needed for the single binop.
1292  Constant *Mask = Shuf.getMask();
1293  Constant *NewC = ConstantExpr::getShuffleVector(C0, C1, Mask);
1294 
1295  // We are moving a binop after a shuffle. When a shuffle has an undefined
1296  // mask element, the result is undefined, but it is not poison or undefined
1297  // behavior. That is not necessarily true for div/rem/shift.
1298  bool MightCreatePoisonOrUB =
1299  Mask->containsUndefElement() &&
1301  if (MightCreatePoisonOrUB)
1302  NewC = getSafeVectorConstantForBinop(BOpc, NewC, ConstantsAreOp1);
1303 
1304  Value *V;
1305  if (X == Y) {
1306  // Remove a binop and the shuffle by rearranging the constant:
1307  // shuffle (op V, C0), (op V, C1), M --> op V, C'
1308  // shuffle (op C0, V), (op C1, V), M --> op C', V
1309  V = X;
1310  } else {
1311  // If there are 2 different variable operands, we must create a new shuffle
1312  // (select) first, so check uses to ensure that we don't end up with more
1313  // instructions than we started with.
1314  if (!B0->hasOneUse() && !B1->hasOneUse())
1315  return nullptr;
1316 
1317  // If we use the original shuffle mask and op1 is *variable*, we would be
1318  // putting an undef into operand 1 of div/rem/shift. This is either UB or
1319  // poison. We do not have to guard against UB when *constants* are op1
1320  // because safe constants guarantee that we do not overflow sdiv/srem (and
1321  // there's no danger for other opcodes).
1322  // TODO: To allow this case, create a new shuffle mask with no undefs.
1323  if (MightCreatePoisonOrUB && !ConstantsAreOp1)
1324  return nullptr;
1325 
1326  // Note: In general, we do not create new shuffles in InstCombine because we
1327  // do not know if a target can lower an arbitrary shuffle optimally. In this
1328  // case, the shuffle uses the existing mask, so there is no additional risk.
1329 
1330  // Select the variable vectors first, then perform the binop:
1331  // shuffle (op X, C0), (op Y, C1), M --> op (shuffle X, Y, M), C'
1332  // shuffle (op C0, X), (op C1, Y), M --> op C', (shuffle X, Y, M)
1333  V = Builder.CreateShuffleVector(X, Y, Mask);
1334  }
1335 
1336  Instruction *NewBO = ConstantsAreOp1 ? BinaryOperator::Create(BOpc, V, NewC) :
1337  BinaryOperator::Create(BOpc, NewC, V);
1338 
1339  // Flags are intersected from the 2 source binops. But there are 2 exceptions:
1340  // 1. If we changed an opcode, poison conditions might have changed.
1341  // 2. If the shuffle had undef mask elements, the new binop might have undefs
1342  // where the original code did not. But if we already made a safe constant,
1343  // then there's no danger.
1344  NewBO->copyIRFlags(B0);
1345  NewBO->andIRFlags(B1);
1346  if (DropNSW)
1347  NewBO->setHasNoSignedWrap(false);
1348  if (Mask->containsUndefElement() && !MightCreatePoisonOrUB)
1349  NewBO->dropPoisonGeneratingFlags();
1350  return NewBO;
1351 }
1352 
1354  Value *LHS = SVI.getOperand(0);
1355  Value *RHS = SVI.getOperand(1);
1356  SmallVector<int, 16> Mask = SVI.getShuffleMask();
1358 
1359  if (auto *V = SimplifyShuffleVectorInst(
1360  LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1361  return replaceInstUsesWith(SVI, V);
1362 
1363  if (Instruction *I = foldSelectShuffle(SVI, Builder, DL))
1364  return I;
1365 
1366  bool MadeChange = false;
1367  unsigned VWidth = SVI.getType()->getVectorNumElements();
1368 
1369  APInt UndefElts(VWidth, 0);
1370  APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1371  if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1372  if (V != &SVI)
1373  return replaceInstUsesWith(SVI, V);
1374  return &SVI;
1375  }
1376 
1377  unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1378 
1379  // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask')
1380  // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1381  if (LHS == RHS || isa<UndefValue>(LHS)) {
1382  if (isa<UndefValue>(LHS) && LHS == RHS) {
1383  // shuffle(undef,undef,mask) -> undef.
1384  Value *Result = (VWidth == LHSWidth)
1385  ? LHS : UndefValue::get(SVI.getType());
1386  return replaceInstUsesWith(SVI, Result);
1387  }
1388 
1389  // Remap any references to RHS to use LHS.
1391  for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1392  if (Mask[i] < 0) {
1393  Elts.push_back(UndefValue::get(Int32Ty));
1394  continue;
1395  }
1396 
1397  if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1398  (Mask[i] < (int)e && isa<UndefValue>(LHS))) {
1399  Mask[i] = -1; // Turn into undef.
1400  Elts.push_back(UndefValue::get(Int32Ty));
1401  } else {
1402  Mask[i] = Mask[i] % e; // Force to LHS.
1403  Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1404  }
1405  }
1406  SVI.setOperand(0, SVI.getOperand(1));
1407  SVI.setOperand(1, UndefValue::get(RHS->getType()));
1408  SVI.setOperand(2, ConstantVector::get(Elts));
1409  LHS = SVI.getOperand(0);
1410  RHS = SVI.getOperand(1);
1411  MadeChange = true;
1412  }
1413 
1414  if (VWidth == LHSWidth) {
1415  // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1416  bool isLHSID, isRHSID;
1417  recognizeIdentityMask(Mask, isLHSID, isRHSID);
1418 
1419  // Eliminate identity shuffles.
1420  if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1421  if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1422  }
1423 
1424  if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
1425  Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
1426  return replaceInstUsesWith(SVI, V);
1427  }
1428 
1429  // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1430  // a non-vector type. We can instead bitcast the original vector followed by
1431  // an extract of the desired element:
1432  //
1433  // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1434  // <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1435  // %1 = bitcast <4 x i8> %sroa to i32
1436  // Becomes:
1437  // %bc = bitcast <16 x i8> %in to <4 x i32>
1438  // %ext = extractelement <4 x i32> %bc, i32 0
1439  //
1440  // If the shuffle is extracting a contiguous range of values from the input
1441  // vector then each use which is a bitcast of the extracted size can be
1442  // replaced. This will work if the vector types are compatible, and the begin
1443  // index is aligned to a value in the casted vector type. If the begin index
1444  // isn't aligned then we can shuffle the original vector (keeping the same
1445  // vector type) before extracting.
1446  //
1447  // This code will bail out if the target type is fundamentally incompatible
1448  // with vectors of the source type.
1449  //
1450  // Example of <16 x i8>, target type i32:
1451  // Index range [4,8): v-----------v Will work.
1452  // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1453  // <16 x i8>: | | | | | | | | | | | | | | | | |
1454  // <4 x i32>: | | | | |
1455  // +-----------+-----------+-----------+-----------+
1456  // Index range [6,10): ^-----------^ Needs an extra shuffle.
1457  // Target type i40: ^--------------^ Won't work, bail.
1458  if (isShuffleExtractingFromLHS(SVI, Mask)) {
1459  Value *V = LHS;
1460  unsigned MaskElems = Mask.size();
1461  VectorType *SrcTy = cast<VectorType>(V->getType());
1462  unsigned VecBitWidth = SrcTy->getBitWidth();
1463  unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1464  assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1465  unsigned SrcNumElems = SrcTy->getNumElements();
1468  for (User *U : SVI.users())
1469  if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1470  if (!BC->use_empty())
1471  // Only visit bitcasts that weren't previously handled.
1472  BCs.push_back(BC);
1473  for (BitCastInst *BC : BCs) {
1474  unsigned BegIdx = Mask.front();
1475  Type *TgtTy = BC->getDestTy();
1476  unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1477  if (!TgtElemBitWidth)
1478  continue;
1479  unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1480  bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1481  bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1482  if (!VecBitWidthsEqual)
1483  continue;
1484  if (!VectorType::isValidElementType(TgtTy))
1485  continue;
1486  VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1487  if (!BegIsAligned) {
1488  // Shuffle the input so [0,NumElements) contains the output, and
1489  // [NumElems,SrcNumElems) is undef.
1490  SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1491  UndefValue::get(Int32Ty));
1492  for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1493  ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1494  V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1495  ConstantVector::get(ShuffleMask),
1496  SVI.getName() + ".extract");
1497  BegIdx = 0;
1498  }
1499  unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1500  assert(SrcElemsPerTgtElem);
1501  BegIdx /= SrcElemsPerTgtElem;
1502  bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1503  auto *NewBC =
1504  BCAlreadyExists
1505  ? NewBCs[CastSrcTy]
1506  : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1507  if (!BCAlreadyExists)
1508  NewBCs[CastSrcTy] = NewBC;
1509  auto *Ext = Builder.CreateExtractElement(
1510  NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1511  // The shufflevector isn't being replaced: the bitcast that used it
1512  // is. InstCombine will visit the newly-created instructions.
1513  replaceInstUsesWith(*BC, Ext);
1514  MadeChange = true;
1515  }
1516  }
1517 
1518  // If the LHS is a shufflevector itself, see if we can combine it with this
1519  // one without producing an unusual shuffle.
1520  // Cases that might be simplified:
1521  // 1.
1522  // x1=shuffle(v1,v2,mask1)
1523  // x=shuffle(x1,undef,mask)
1524  // ==>
1525  // x=shuffle(v1,undef,newMask)
1526  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1527  // 2.
1528  // x1=shuffle(v1,undef,mask1)
1529  // x=shuffle(x1,x2,mask)
1530  // where v1.size() == mask1.size()
1531  // ==>
1532  // x=shuffle(v1,x2,newMask)
1533  // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1534  // 3.
1535  // x2=shuffle(v2,undef,mask2)
1536  // x=shuffle(x1,x2,mask)
1537  // where v2.size() == mask2.size()
1538  // ==>
1539  // x=shuffle(x1,v2,newMask)
1540  // newMask[i] = (mask[i] < x1.size())
1541  // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1542  // 4.
1543  // x1=shuffle(v1,undef,mask1)
1544  // x2=shuffle(v2,undef,mask2)
1545  // x=shuffle(x1,x2,mask)
1546  // where v1.size() == v2.size()
1547  // ==>
1548  // x=shuffle(v1,v2,newMask)
1549  // newMask[i] = (mask[i] < x1.size())
1550  // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1551  //
1552  // Here we are really conservative:
1553  // we are absolutely afraid of producing a shuffle mask not in the input
1554  // program, because the code gen may not be smart enough to turn a merged
1555  // shuffle into two specific shuffles: it may produce worse code. As such,
1556  // we only merge two shuffles if the result is either a splat or one of the
1557  // input shuffle masks. In this case, merging the shuffles just removes
1558  // one instruction, which we know is safe. This is good for things like
1559  // turning: (splat(splat)) -> splat, or
1560  // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1561  ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1562  ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1563  if (LHSShuffle)
1564  if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1565  LHSShuffle = nullptr;
1566  if (RHSShuffle)
1567  if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1568  RHSShuffle = nullptr;
1569  if (!LHSShuffle && !RHSShuffle)
1570  return MadeChange ? &SVI : nullptr;
1571 
1572  Value* LHSOp0 = nullptr;
1573  Value* LHSOp1 = nullptr;
1574  Value* RHSOp0 = nullptr;
1575  unsigned LHSOp0Width = 0;
1576  unsigned RHSOp0Width = 0;
1577  if (LHSShuffle) {
1578  LHSOp0 = LHSShuffle->getOperand(0);
1579  LHSOp1 = LHSShuffle->getOperand(1);
1580  LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1581  }
1582  if (RHSShuffle) {
1583  RHSOp0 = RHSShuffle->getOperand(0);
1584  RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1585  }
1586  Value* newLHS = LHS;
1587  Value* newRHS = RHS;
1588  if (LHSShuffle) {
1589  // case 1
1590  if (isa<UndefValue>(RHS)) {
1591  newLHS = LHSOp0;
1592  newRHS = LHSOp1;
1593  }
1594  // case 2 or 4
1595  else if (LHSOp0Width == LHSWidth) {
1596  newLHS = LHSOp0;
1597  }
1598  }
1599  // case 3 or 4
1600  if (RHSShuffle && RHSOp0Width == LHSWidth) {
1601  newRHS = RHSOp0;
1602  }
1603  // case 4
1604  if (LHSOp0 == RHSOp0) {
1605  newLHS = LHSOp0;
1606  newRHS = nullptr;
1607  }
1608 
1609  if (newLHS == LHS && newRHS == RHS)
1610  return MadeChange ? &SVI : nullptr;
1611 
1612  SmallVector<int, 16> LHSMask;
1613  SmallVector<int, 16> RHSMask;
1614  if (newLHS != LHS)
1615  LHSMask = LHSShuffle->getShuffleMask();
1616  if (RHSShuffle && newRHS != RHS)
1617  RHSMask = RHSShuffle->getShuffleMask();
1618 
1619  unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1620  SmallVector<int, 16> newMask;
1621  bool isSplat = true;
1622  int SplatElt = -1;
1623  // Create a new mask for the new ShuffleVectorInst so that the new
1624  // ShuffleVectorInst is equivalent to the original one.
1625  for (unsigned i = 0; i < VWidth; ++i) {
1626  int eltMask;
1627  if (Mask[i] < 0) {
1628  // This element is an undef value.
1629  eltMask = -1;
1630  } else if (Mask[i] < (int)LHSWidth) {
1631  // This element is from left hand side vector operand.
1632  //
1633  // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1634  // new mask value for the element.
1635  if (newLHS != LHS) {
1636  eltMask = LHSMask[Mask[i]];
1637  // If the value selected is an undef value, explicitly specify it
1638  // with a -1 mask value.
1639  if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1640  eltMask = -1;
1641  } else
1642  eltMask = Mask[i];
1643  } else {
1644  // This element is from right hand side vector operand
1645  //
1646  // If the value selected is an undef value, explicitly specify it
1647  // with a -1 mask value. (case 1)
1648  if (isa<UndefValue>(RHS))
1649  eltMask = -1;
1650  // If RHS is going to be replaced (case 3 or 4), calculate the
1651  // new mask value for the element.
1652  else if (newRHS != RHS) {
1653  eltMask = RHSMask[Mask[i]-LHSWidth];
1654  // If the value selected is an undef value, explicitly specify it
1655  // with a -1 mask value.
1656  if (eltMask >= (int)RHSOp0Width) {
1657  assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1658  && "should have been check above");
1659  eltMask = -1;
1660  }
1661  } else
1662  eltMask = Mask[i]-LHSWidth;
1663 
1664  // If LHS's width is changed, shift the mask value accordingly.
1665  // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
1666  // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1667  // If newRHS == newLHS, we want to remap any references from newRHS to
1668  // newLHS so that we can properly identify splats that may occur due to
1669  // obfuscation across the two vectors.
1670  if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1671  eltMask += newLHSWidth;
1672  }
1673 
1674  // Check if this could still be a splat.
1675  if (eltMask >= 0) {
1676  if (SplatElt >= 0 && SplatElt != eltMask)
1677  isSplat = false;
1678  SplatElt = eltMask;
1679  }
1680 
1681  newMask.push_back(eltMask);
1682  }
1683 
1684  // If the result mask is equal to one of the original shuffle masks,
1685  // or is a splat, do the replacement.
1686  if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1688  for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1689  if (newMask[i] < 0) {
1690  Elts.push_back(UndefValue::get(Int32Ty));
1691  } else {
1692  Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1693  }
1694  }
1695  if (!newRHS)
1696  newRHS = UndefValue::get(newLHS->getType());
1697  return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1698  }
1699 
1700  // If the result mask is an identity, replace uses of this instruction with
1701  // corresponding argument.
1702  bool isLHSID, isRHSID;
1703  recognizeIdentityMask(newMask, isLHSID, isRHSID);
1704  if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1705  if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1706 
1707  return MadeChange ? &SVI : nullptr;
1708 }
static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf)
std::pair< Value *, Value * > ShuffleOps
We are building a shuffle to create V, which is a sequence of insertelement, extractelement pairs...
Instruction * visitInsertValueInst(InsertValueInst &IV)
Try to find redundant insertvalue instructions, like the following ones: %0 = insertvalue { i8...
uint64_t CallInst * C
Instruction * InsertNewInstWith(Instruction *New, Instruction &Old)
Same as InsertNewInstBefore, but also sets the debug loc.
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:875
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isConstant(const MachineInstr &MI)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:562
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
Definition: Path.cpp:250
static Instruction * foldSelectShuffle(ShuffleVectorInst &Shuf, InstCombiner::BuilderTy &Builder, const DataLayout &DL)
Try to fold shuffles that are the equivalent of a vector select.
Value * findScalarElement(Value *V, unsigned EltNo)
Given a vector and an element number, see if the scalar value is already around as a register...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
BinaryOps getOpcode() const
Definition: InstrTypes.h:555
static Instruction * foldConstantInsEltIntoShuffle(InsertElementInst &InsElt)
insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex –> shufflevector X...
static ConstantAggregateZero * get(Type *Ty)
Definition: Constants.cpp:1309
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:867
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
Definition: PatternMatch.h:91
This instruction constructs a fixed permutation of two input vectors.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI, SmallVector< int, 16 > &Mask)
Hexagon Common GEP
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
static Instruction * hoistInsEltConst(InsertElementInst &InsElt2, InstCombiner::BuilderTy &Builder)
If we have an insertelement instruction feeding into another insertelement and the 2nd is inserting a...
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
bool hasNoSignedWrap() const
Determine whether the no signed wrap flag is set.
static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL)
Binops may be transformed into binops with different opcodes and operands.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
Constant * getMask() const
static InsertElementInst * Create(Value *Vec, Value *NewElt, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
unsigned getBitWidth() const
Return the number of bits in the Vector type.
Definition: DerivedTypes.h:452
void setBit(unsigned BitPosition)
Set a given bit to 1.
Definition: APInt.h:1397
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:592
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:731
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.
static bool CanEvaluateShuffled(Value *V, ArrayRef< int > Mask, unsigned Depth=5)
Return true if we can evaluate the specified expression tree if the vector elements were shuffled in ...
uint64_t getNumElements() const
Definition: DerivedTypes.h:359
BinopElts(BinaryOperator::BinaryOps Opc=(BinaryOperator::BinaryOps) 0, Value *V0=nullptr, Value *V1=nullptr)
This file implements a class to represent arbitrary precision integral constant values and operations...
void assign(size_type NumElts, const T &Elt)
Definition: SmallVector.h:423
static Instruction * foldInsSequenceIntoBroadcast(InsertElementInst &InsElt)
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static Constant * getSafeVectorConstantForBinop(BinaryOperator::BinaryOps Opcode, Constant *In, bool IsRHSConstant)
Some binary operators require special handling to avoid poison and undefined behavior.
static bool isValidElementType(Type *ElemTy)
Return true if the specified type is valid as a element type.
Definition: Type.cpp:608
This instruction compares its operands according to the predicate given to the constructor.
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
This class represents a no-op cast from one type to another.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:126
Instruction * visitExtractElementInst(ExtractElementInst &EI)
These are the ingredients in an alternate form binary operator as described below.
static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, SmallVectorImpl< Constant *> &Mask)
If V is a shuffle of values that ONLY returns elements from either LHS or RHS, return the shuffle mas...
bool isSelect() const
Return true if this shuffle chooses elements from its source vectors without lane crossings and all o...
VectorType * getType() const
Overload to return most specific vector type.
Value * getOperand(unsigned i) const
Definition: User.h:170
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:338
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return &#39;this&#39;.
Definition: Type.h:304
Instruction * visitInsertElementInst(InsertElementInst &IE)
Value * SimplifyInsertElementInst(Value *Vec, Value *Elt, Value *Idx, const SimplifyQuery &Q)
Given operands for an InsertElement, fold the result or return null.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:841
This instruction inserts a single (scalar) element into a VectorType value.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt...
Definition: PatternMatch.h:177
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:218
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
This file contains the declarations for the subclasses of Constant, which represent the different fla...
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
Definition: PatternMatch.h:499
static Constant * getShuffleVector(Constant *V1, Constant *V2, Constant *Mask, Type *OnlyIfReducedTy=nullptr)
Definition: Constants.cpp:2096
bool any_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1037
This instruction compares its operands according to the predicate given to the constructor.
static Constant * getBinOpIdentity(unsigned Opcode, Type *Ty, bool AllowRHSConstant=false)
Return the identity constant for a binary opcode.
Definition: Constants.cpp:2274
op_range operands()
Definition: User.h:238
self_iterator getIterator()
Definition: ilist_node.h:82
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
Definition: PatternMatch.h:75
Class to represent integer types.
Definition: DerivedTypes.h:40
VectorType * getVectorOperandType() const
static void replaceExtractElements(InsertElementInst *InsElt, ExtractElementInst *ExtElt, InstCombiner &IC)
If we have insertion into a vector that is wider than the vector that we are extracting from...
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
size_t size() const
Definition: SmallVector.h:53
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 * SimplifyShuffleVectorInst(Value *Op0, Value *Op1, Constant *Mask, Type *RetTy, const SimplifyQuery &Q)
Given operands for a ShuffleVectorInst, fold the result or return null.
void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag...
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:88
Iterator for intrusive lists based on ilist_node.
uint64_t getLimitedValue(uint64_t Limit=~0ULL) const
getLimitedValue - If the value is smaller than the specified limit, return it, otherwise return the l...
Definition: Constants.h:251
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
BinaryOperator::BinaryOps Opcode
bool containsUndefElement() const
Return true if this is a vector constant that includes any undefined elements.
Definition: Constants.cpp:257
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:64
static void getShuffleMask(const Constant *Mask, SmallVectorImpl< int > &Result)
Convert the input shuffle mask operand to a vector of integers.
Value * CreateInsertElement(Value *Vec, Value *NewElt, Value *Idx, const Twine &Name="")
Definition: IRBuilder.h:1934
static Instruction * foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf)
Value * CreateShuffleVector(Value *V1, Value *V2, Value *Mask, const Twine &Name="")
Definition: IRBuilder.h:1948
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:621
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void setOperand(unsigned i, Value *Val)
Definition: User.h:175
unsigned getVectorNumElements() const
Definition: DerivedTypes.h:462
Class to represent vector types.
Definition: DerivedTypes.h:393
Class for arbitrary precision integers.
Definition: APInt.h:70
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:400
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array...
Definition: ArrayRef.h:179
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:546
static BinaryOperator * CreateWithCopiedFlags(BinaryOps Opc, Value *V1, Value *V2, BinaryOperator *CopyBO, const Twine &Name="")
Definition: InstrTypes.h:386
static bool cheapToScalarize(Value *V, bool isConstant)
Return true if the value is cheaper to scalarize than it is to leave as a vector operation.
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction...
Definition: Instruction.cpp:80
#define I(x, y, z)
Definition: MD5.cpp:58
Instruction * visitShuffleVectorInst(ShuffleVectorInst &SVI)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
This instruction extracts a single (scalar) element from a VectorType value.
static Constant * getShl(Constant *C1, Constant *C2, bool HasNUW=false, bool HasNSW=false)
Definition: Constants.cpp:2257
bool hasNoUnsignedWrap() const
Determine whether the no unsigned wrap flag is set.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Instruction * replaceInstUsesWith(Instruction &I, Value *V)
A combiner-aware RAUW-like routine.
ArrayRef< unsigned > getIndices() const
LLVM Value Representation.
Definition: Value.h:73
This file provides internal interfaces used to implement the InstCombine.
static VectorType * get(Type *ElementType, unsigned NumElements)
This static method is the primary way to construct an VectorType.
Definition: Type.cpp:593
Value * SimplifyExtractElementInst(Value *Vec, Value *Idx, const SimplifyQuery &Q)
Given operands for an ExtractElementInst, fold the result or return null.
static Value * buildNew(Instruction *I, ArrayRef< Value *> NewOps)
Rebuild a new instruction just like &#39;I&#39; but with the new operands given.
std::underlying_type< E >::type Mask()
Get a bitmask with 1s in all places up to the high-order bit of E&#39;s largest value.
Definition: BitmaskEnum.h:81
Type * getElementType() const
Definition: DerivedTypes.h:360
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
bool isIntDivRem() const
Definition: Instruction.h:131
static bool isSplat(ArrayRef< Value *> VL)
static void recognizeIdentityMask(const SmallVectorImpl< int > &Mask, bool &isLHSID, bool &isRHSID)
static ShuffleOps collectShuffleElements(Value *V, SmallVectorImpl< Constant *> &Mask, Value *PermittedRHS, InstCombiner &IC)
static ExtractElementInst * Create(Value *Vec, Value *Idx, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
VectorType * getType() const
Overload to return most specific vector type.
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1056
IntegerType * Int32Ty
User * user_back()
Definition: Value.h:386
const BasicBlock * getParent() const
Definition: Instruction.h:67
This instruction inserts a struct field of array element value into an aggregate value.