lib/Transforms/InstCombine/InstCombineVectorOps.cpp

   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/DenseMap.h"
  17 #include "llvm/Analysis/InstructionSimplify.h"
  18 #include "llvm/Analysis/VectorUtils.h"
  19 #include "llvm/IR/PatternMatch.h"
  20 using namespace llvm;
  21 using namespace PatternMatch;
  22
  23 #define DEBUG_TYPE "instcombine"
  24
  25 /// Return true if the value is cheaper to scalarize than it is to leave as a
  26 /// vector operation. isConstant indicates whether we're extracting one known
  27 /// element. If false we're extracting a variable index.
  28 static bool CheapToScalarize(Value *V, bool isConstant) {
  29   if (Constant *C = dyn_cast<Constant>(V)) {
  30     if (isConstant) return true;
  31
  32     // If all elts are the same, we can extract it and use any of the values.
  33     if (Constant *Op0 = C->getAggregateElement(0U)) {
  34       for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e;
  35            ++i)
  36         if (C->getAggregateElement(i) != Op0)
  37           return false;
  38       return true;
  39     }
  40   }
  41   Instruction *I = dyn_cast<Instruction>(V);
  42   if (!I) return false;
  43
  44   // Insert element gets simplified to the inserted element or is deleted if
  45   // this is constant idx extract element and its a constant idx insertelt.
  46   if (I->getOpcode() == Instruction::InsertElement && isConstant &&
  47       isa<ConstantInt>(I->getOperand(2)))
  48     return true;
  49   if (I->getOpcode() == Instruction::Load && I->hasOneUse())
  50     return true;
  51   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
  52     if (BO->hasOneUse() &&
  53         (CheapToScalarize(BO->getOperand(0), isConstant) ||
  54          CheapToScalarize(BO->getOperand(1), isConstant)))
  55       return true;
  56   if (CmpInst *CI = dyn_cast<CmpInst>(I))
  57     if (CI->hasOneUse() &&
  58         (CheapToScalarize(CI->getOperand(0), isConstant) ||
  59          CheapToScalarize(CI->getOperand(1), isConstant)))
  60       return true;
  61
  62   return false;
  63 }
  64
  65 // If we have a PHI node with a vector type that has only 2 uses: feed
  66 // itself and be an operand of extractelement at a constant location,
  67 // try to replace the PHI of the vector type with a PHI of a scalar type.
  68 Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) {
  69   // Verify that the PHI node has exactly 2 uses. Otherwise return NULL.
  70   if (!PN->hasNUses(2))
  71     return nullptr;
  72
  73   // If so, it's known at this point that one operand is PHI and the other is
  74   // an extractelement node. Find the PHI user that is not the extractelement
  75   // node.
  76   auto iu = PN->user_begin();
  77   Instruction *PHIUser = dyn_cast<Instruction>(*iu);
  78   if (PHIUser == cast<Instruction>(&EI))
  79     PHIUser = cast<Instruction>(*(++iu));
  80
  81   // Verify that this PHI user has one use, which is the PHI itself,
  82   // and that it is a binary operation which is cheap to scalarize.
  83   // otherwise return NULL.
  84   if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) ||
  85       !(isa<BinaryOperator>(PHIUser)) || !CheapToScalarize(PHIUser, true))
  86     return nullptr;
  87
  88   // Create a scalar PHI node that will replace the vector PHI node
  89   // just before the current PHI node.
  90   PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith(
  91       PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN));
  92   // Scalarize each PHI operand.
  93   for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) {
  94     Value *PHIInVal = PN->getIncomingValue(i);
  95     BasicBlock *inBB = PN->getIncomingBlock(i);
  96     Value *Elt = EI.getIndexOperand();
  97     // If the operand is the PHI induction variable:
  98     if (PHIInVal == PHIUser) {
  99       // Scalarize the binary operation. Its first operand is the
 100       // scalar PHI, and the second operand is extracted from the other
 101       // vector operand.
 102       BinaryOperator *B0 = cast<BinaryOperator>(PHIUser);
 103       unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0;
 104       Value *Op = InsertNewInstWith(
 105           ExtractElementInst::Create(B0->getOperand(opId), Elt,
 106                                      B0->getOperand(opId)->getName() + ".Elt"),
 107           *B0);
 108       Value *newPHIUser = InsertNewInstWith(
 109           BinaryOperator::Create(B0->getOpcode(), scalarPHI, Op), *B0);
 110       scalarPHI->addIncoming(newPHIUser, inBB);
 111     } else {
 112       // Scalarize PHI input:
 113       Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, "");
 114       // Insert the new instruction into the predecessor basic block.
 115       Instruction *pos = dyn_cast<Instruction>(PHIInVal);
 116       BasicBlock::iterator InsertPos;
 117       if (pos && !isa<PHINode>(pos)) {
 118         InsertPos = pos;
 119         ++InsertPos;
 120       } else {
 121         InsertPos = inBB->getFirstInsertionPt();
 122       }
 123
 124       InsertNewInstWith(newEI, *InsertPos);
 125
 126       scalarPHI->addIncoming(newEI, inBB);
 127     }
 128   }
 129   return ReplaceInstUsesWith(EI, scalarPHI);
 130 }
 131
 132 Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
 133   if (Value *V = SimplifyExtractElementInst(
 134           EI.getVectorOperand(), EI.getIndexOperand(), DL, TLI, DT, AC))
 135     return ReplaceInstUsesWith(EI, V);
 136
 137   // If vector val is constant with all elements the same, replace EI with
 138   // that element.  We handle a known element # below.
 139   if (Constant *C = dyn_cast<Constant>(EI.getOperand(0)))
 140     if (CheapToScalarize(C, false))
 141       return ReplaceInstUsesWith(EI, C->getAggregateElement(0U));
 142
 143   // If extracting a specified index from the vector, see if we can recursively
 144   // find a previously computed scalar that was inserted into the vector.
 145   if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 146     unsigned IndexVal = IdxC->getZExtValue();
 147     unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
 148
 149     // InstSimplify handles cases where the index is invalid.
 150     assert(IndexVal < VectorWidth);
 151
 152     // This instruction only demands the single element from the input vector.
 153     // If the input vector has a single use, simplify it based on this use
 154     // property.
 155     if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
 156       APInt UndefElts(VectorWidth, 0);
 157       APInt DemandedMask(VectorWidth, 0);
 158       DemandedMask.setBit(IndexVal);
 159       if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask,
 160                                                 UndefElts)) {
 161         EI.setOperand(0, V);
 162         return &EI;
 163       }
 164     }
 165
 166     // If the this extractelement is directly using a bitcast from a vector of
 167     // the same number of elements, see if we can find the source element from
 168     // it.  In this case, we will end up needing to bitcast the scalars.
 169     if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
 170       if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
 171         if (VT->getNumElements() == VectorWidth)
 172           if (Value *Elt = findScalarElement(BCI->getOperand(0), IndexVal))
 173             return new BitCastInst(Elt, EI.getType());
 174     }
 175
 176     // If there's a vector PHI feeding a scalar use through this extractelement
 177     // instruction, try to scalarize the PHI.
 178     if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) {
 179       Instruction *scalarPHI = scalarizePHI(EI, PN);
 180       if (scalarPHI)
 181         return scalarPHI;
 182     }
 183   }
 184
 185   if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
 186     // Push extractelement into predecessor operation if legal and
 187     // profitable to do so
 188     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 189       if (I->hasOneUse() &&
 190           CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
 191         Value *newEI0 =
 192           Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
 193                                         EI.getName()+".lhs");
 194         Value *newEI1 =
 195           Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
 196                                         EI.getName()+".rhs");
 197         return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
 198       }
 199     } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
 200       // Extracting the inserted element?
 201       if (IE->getOperand(2) == EI.getOperand(1))
 202         return ReplaceInstUsesWith(EI, IE->getOperand(1));
 203       // If the inserted and extracted elements are constants, they must not
 204       // be the same value, extract from the pre-inserted value instead.
 205       if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
 206         Worklist.AddValue(EI.getOperand(0));
 207         EI.setOperand(0, IE->getOperand(0));
 208         return &EI;
 209       }
 210     } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
 211       // If this is extracting an element from a shufflevector, figure out where
 212       // it came from and extract from the appropriate input element instead.
 213       if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 214         int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
 215         Value *Src;
 216         unsigned LHSWidth =
 217           SVI->getOperand(0)->getType()->getVectorNumElements();
 218
 219         if (SrcIdx < 0)
 220           return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 221         if (SrcIdx < (int)LHSWidth)
 222           Src = SVI->getOperand(0);
 223         else {
 224           SrcIdx -= LHSWidth;
 225           Src = SVI->getOperand(1);
 226         }
 227         Type *Int32Ty = Type::getInt32Ty(EI.getContext());
 228         return ExtractElementInst::Create(Src,
 229                                           ConstantInt::get(Int32Ty,
 230                                                            SrcIdx, false));
 231       }
 232     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 233       // Canonicalize extractelement(cast) -> cast(extractelement)
 234       // bitcasts can change the number of vector elements and they cost nothing
 235       if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
 236         Value *EE = Builder->CreateExtractElement(CI->getOperand(0),
 237                                                   EI.getIndexOperand());
 238         Worklist.AddValue(EE);
 239         return CastInst::Create(CI->getOpcode(), EE, EI.getType());
 240       }
 241     } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
 242       if (SI->hasOneUse()) {
 243         // TODO: For a select on vectors, it might be useful to do this if it
 244         // has multiple extractelement uses. For vector select, that seems to
 245         // fight the vectorizer.
 246
 247         // If we are extracting an element from a vector select or a select on
 248         // vectors, a select on the scalars extracted from the vector arguments.
 249         Value *TrueVal = SI->getTrueValue();
 250         Value *FalseVal = SI->getFalseValue();
 251
 252         Value *Cond = SI->getCondition();
 253         if (Cond->getType()->isVectorTy()) {
 254           Cond = Builder->CreateExtractElement(Cond,
 255                                                EI.getIndexOperand(),
 256                                                Cond->getName() + ".elt");
 257         }
 258
 259         Value *V1Elem
 260           = Builder->CreateExtractElement(TrueVal,
 261                                           EI.getIndexOperand(),
 262                                           TrueVal->getName() + ".elt");
 263
 264         Value *V2Elem
 265           = Builder->CreateExtractElement(FalseVal,
 266                                           EI.getIndexOperand(),
 267                                           FalseVal->getName() + ".elt");
 268         return SelectInst::Create(Cond,
 269                                   V1Elem,
 270                                   V2Elem,
 271                                   SI->getName() + ".elt");
 272       }
 273     }
 274   }
 275   return nullptr;
 276 }
 277
 278 /// If V is a shuffle of values that ONLY returns elements from either LHS or
 279 /// RHS, return the shuffle mask and true. Otherwise, return false.
 280 static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
 281                                          SmallVectorImpl<Constant*> &Mask) {
 282   assert(LHS->getType() == RHS->getType() &&
 283          "Invalid CollectSingleShuffleElements");
 284   unsigned NumElts = V->getType()->getVectorNumElements();
 285
 286   if (isa<UndefValue>(V)) {
 287     Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 288     return true;
 289   }
 290
 291   if (V == LHS) {
 292     for (unsigned i = 0; i != NumElts; ++i)
 293       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 294     return true;
 295   }
 296
 297   if (V == RHS) {
 298     for (unsigned i = 0; i != NumElts; ++i)
 299       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
 300                                       i+NumElts));
 301     return true;
 302   }
 303
 304   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 305     // If this is an insert of an extract from some other vector, include it.
 306     Value *VecOp    = IEI->getOperand(0);
 307     Value *ScalarOp = IEI->getOperand(1);
 308     Value *IdxOp    = IEI->getOperand(2);
 309
 310     if (!isa<ConstantInt>(IdxOp))
 311       return false;
 312     unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 313
 314     if (isa<UndefValue>(ScalarOp)) {  // inserting undef into vector.
 315       // We can handle this if the vector we are inserting into is
 316       // transitively ok.
 317       if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 318         // If so, update the mask to reflect the inserted undef.
 319         Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
 320         return true;
 321       }
 322     } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
 323       if (isa<ConstantInt>(EI->getOperand(1))) {
 324         unsigned ExtractedIdx =
 325         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 326         unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
 327
 328         // This must be extracting from either LHS or RHS.
 329         if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
 330           // We can handle this if the vector we are inserting into is
 331           // transitively ok.
 332           if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 333             // If so, update the mask to reflect the inserted value.
 334             if (EI->getOperand(0) == LHS) {
 335               Mask[InsertedIdx % NumElts] =
 336               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 337                                ExtractedIdx);
 338             } else {
 339               assert(EI->getOperand(0) == RHS);
 340               Mask[InsertedIdx % NumElts] =
 341               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 342                                ExtractedIdx + NumLHSElts);
 343             }
 344             return true;
 345           }
 346         }
 347       }
 348     }
 349   }
 350
 351   return false;
 352 }
 353
 354
 355 /// We are building a shuffle to create V, which is a sequence of insertelement,
 356 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
 357 /// not rely on the second vector source. Return a std::pair containing the
 358 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
 359 /// parameter as required.
 360 ///
 361 /// Note: we intentionally don't try to fold earlier shuffles since they have
 362 /// often been chosen carefully to be efficiently implementable on the target.
 363 typedef std::pair<Value *, Value *> ShuffleOps;
 364
 365 static ShuffleOps CollectShuffleElements(Value *V,
 366                                          SmallVectorImpl<Constant *> &Mask,
 367                                          Value *PermittedRHS) {
 368   assert(V->getType()->isVectorTy() && "Invalid shuffle!");
 369   unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 370
 371   if (isa<UndefValue>(V)) {
 372     Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 373     return std::make_pair(
 374         PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
 375   }
 376
 377   if (isa<ConstantAggregateZero>(V)) {
 378     Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
 379     return std::make_pair(V, nullptr);
 380   }
 381
 382   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 383     // If this is an insert of an extract from some other vector, include it.
 384     Value *VecOp    = IEI->getOperand(0);
 385     Value *ScalarOp = IEI->getOperand(1);
 386     Value *IdxOp    = IEI->getOperand(2);
 387
 388     if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 389       if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
 390         unsigned ExtractedIdx =
 391           cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 392         unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 393
 394         // Either the extracted from or inserted into vector must be RHSVec,
 395         // otherwise we'd end up with a shuffle of three inputs.
 396         if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
 397           Value *RHS = EI->getOperand(0);
 398           ShuffleOps LR = CollectShuffleElements(VecOp, Mask, RHS);
 399           assert(LR.second == nullptr || LR.second == RHS);
 400
 401           if (LR.first->getType() != RHS->getType()) {
 402             // We tried our best, but we can't find anything compatible with RHS
 403             // further up the chain. Return a trivial shuffle.
 404             for (unsigned i = 0; i < NumElts; ++i)
 405               Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
 406             return std::make_pair(V, nullptr);
 407           }
 408
 409           unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
 410           Mask[InsertedIdx % NumElts] =
 411             ConstantInt::get(Type::getInt32Ty(V->getContext()),
 412                              NumLHSElts+ExtractedIdx);
 413           return std::make_pair(LR.first, RHS);
 414         }
 415
 416         if (VecOp == PermittedRHS) {
 417           // We've gone as far as we can: anything on the other side of the
 418           // extractelement will already have been converted into a shuffle.
 419           unsigned NumLHSElts =
 420               EI->getOperand(0)->getType()->getVectorNumElements();
 421           for (unsigned i = 0; i != NumElts; ++i)
 422             Mask.push_back(ConstantInt::get(
 423                 Type::getInt32Ty(V->getContext()),
 424                 i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
 425           return std::make_pair(EI->getOperand(0), PermittedRHS);
 426         }
 427
 428         // If this insertelement is a chain that comes from exactly these two
 429         // vectors, return the vector and the effective shuffle.
 430         if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
 431             CollectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
 432                                          Mask))
 433           return std::make_pair(EI->getOperand(0), PermittedRHS);
 434       }
 435     }
 436   }
 437
 438   // Otherwise, can't do anything fancy.  Return an identity vector.
 439   for (unsigned i = 0; i != NumElts; ++i)
 440     Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 441   return std::make_pair(V, nullptr);
 442 }
 443
 444 /// Try to find redundant insertvalue instructions, like the following ones:
 445 ///  %0 = insertvalue { i8, i32 } undef, i8 %x, 0
 446 ///  %1 = insertvalue { i8, i32 } %0,    i8 %y, 0
 447 /// Here the second instruction inserts values at the same indices, as the
 448 /// first one, making the first one redundant.
 449 /// It should be transformed to:
 450 ///  %0 = insertvalue { i8, i32 } undef, i8 %y, 0
 451 Instruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) {
 452   bool IsRedundant = false;
 453   ArrayRef<unsigned int> FirstIndices = I.getIndices();
 454
 455   // If there is a chain of insertvalue instructions (each of them except the
 456   // last one has only one use and it's another insertvalue insn from this
 457   // chain), check if any of the 'children' uses the same indices as the first
 458   // instruction. In this case, the first one is redundant.
 459   Value *V = &I;
 460   unsigned Depth = 0;
 461   while (V->hasOneUse() && Depth < 10) {
 462     User *U = V->user_back();
 463     auto UserInsInst = dyn_cast<InsertValueInst>(U);
 464     if (!UserInsInst || U->getOperand(0) != V)
 465       break;
 466     if (UserInsInst->getIndices() == FirstIndices) {
 467       IsRedundant = true;
 468       break;
 469     }
 470     V = UserInsInst;
 471     Depth++;
 472   }
 473
 474   if (IsRedundant)
 475     return ReplaceInstUsesWith(I, I.getOperand(0));
 476   return nullptr;
 477 }
 478
 479 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
 480   Value *VecOp    = IE.getOperand(0);
 481   Value *ScalarOp = IE.getOperand(1);
 482   Value *IdxOp    = IE.getOperand(2);
 483
 484   // Inserting an undef or into an undefined place, remove this.
 485   if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
 486     ReplaceInstUsesWith(IE, VecOp);
 487
 488   // If the inserted element was extracted from some other vector, and if the
 489   // indexes are constant, try to turn this into a shufflevector operation.
 490   if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 491     if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
 492       unsigned NumInsertVectorElts = IE.getType()->getNumElements();
 493       unsigned NumExtractVectorElts =
 494           EI->getOperand(0)->getType()->getVectorNumElements();
 495       unsigned ExtractedIdx =
 496         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 497       unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 498
 499       if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
 500         return ReplaceInstUsesWith(IE, VecOp);
 501
 502       if (InsertedIdx >= NumInsertVectorElts)  // Out of range insert.
 503         return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType()));
 504
 505       // If we are extracting a value from a vector, then inserting it right
 506       // back into the same place, just use the input vector.
 507       if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
 508         return ReplaceInstUsesWith(IE, VecOp);
 509
 510       // If this insertelement isn't used by some other insertelement, turn it
 511       // (and any insertelements it points to), into one big shuffle.
 512       if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) {
 513         SmallVector<Constant*, 16> Mask;
 514         ShuffleOps LR = CollectShuffleElements(&IE, Mask, nullptr);
 515
 516         // The proposed shuffle may be trivial, in which case we shouldn't
 517         // perform the combine.
 518         if (LR.first != &IE && LR.second != &IE) {
 519           // We now have a shuffle of LHS, RHS, Mask.
 520           if (LR.second == nullptr)
 521             LR.second = UndefValue::get(LR.first->getType());
 522           return new ShuffleVectorInst(LR.first, LR.second,
 523                                        ConstantVector::get(Mask));
 524         }
 525       }
 526     }
 527   }
 528
 529   unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements();
 530   APInt UndefElts(VWidth, 0);
 531   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 532   if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
 533     if (V != &IE)
 534       return ReplaceInstUsesWith(IE, V);
 535     return &IE;
 536   }
 537
 538   return nullptr;
 539 }
 540
 541 /// Return true if we can evaluate the specified expression tree if the vector
 542 /// elements were shuffled in a different order.
 543 static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask,
 544                                 unsigned Depth = 5) {
 545   // We can always reorder the elements of a constant.
 546   if (isa<Constant>(V))
 547     return true;
 548
 549   // We won't reorder vector arguments. No IPO here.
 550   Instruction *I = dyn_cast<Instruction>(V);
 551   if (!I) return false;
 552
 553   // Two users may expect different orders of the elements. Don't try it.
 554   if (!I->hasOneUse())
 555     return false;
 556
 557   if (Depth == 0) return false;
 558
 559   switch (I->getOpcode()) {
 560     case Instruction::Add:
 561     case Instruction::FAdd:
 562     case Instruction::Sub:
 563     case Instruction::FSub:
 564     case Instruction::Mul:
 565     case Instruction::FMul:
 566     case Instruction::UDiv:
 567     case Instruction::SDiv:
 568     case Instruction::FDiv:
 569     case Instruction::URem:
 570     case Instruction::SRem:
 571     case Instruction::FRem:
 572     case Instruction::Shl:
 573     case Instruction::LShr:
 574     case Instruction::AShr:
 575     case Instruction::And:
 576     case Instruction::Or:
 577     case Instruction::Xor:
 578     case Instruction::ICmp:
 579     case Instruction::FCmp:
 580     case Instruction::Trunc:
 581     case Instruction::ZExt:
 582     case Instruction::SExt:
 583     case Instruction::FPToUI:
 584     case Instruction::FPToSI:
 585     case Instruction::UIToFP:
 586     case Instruction::SIToFP:
 587     case Instruction::FPTrunc:
 588     case Instruction::FPExt:
 589     case Instruction::GetElementPtr: {
 590       for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
 591         if (!CanEvaluateShuffled(I->getOperand(i), Mask, Depth-1))
 592           return false;
 593       }
 594       return true;
 595     }
 596     case Instruction::InsertElement: {
 597       ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2));
 598       if (!CI) return false;
 599       int ElementNumber = CI->getLimitedValue();
 600
 601       // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
 602       // can't put an element into multiple indices.
 603       bool SeenOnce = false;
 604       for (int i = 0, e = Mask.size(); i != e; ++i) {
 605         if (Mask[i] == ElementNumber) {
 606           if (SeenOnce)
 607             return false;
 608           SeenOnce = true;
 609         }
 610       }
 611       return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1);
 612     }
 613   }
 614   return false;
 615 }
 616
 617 /// Rebuild a new instruction just like 'I' but with the new operands given.
 618 /// In the event of type mismatch, the type of the operands is correct.
 619 static Value *BuildNew(Instruction *I, ArrayRef<Value*> NewOps) {
 620   // We don't want to use the IRBuilder here because we want the replacement
 621   // instructions to appear next to 'I', not the builder's insertion point.
 622   switch (I->getOpcode()) {
 623     case Instruction::Add:
 624     case Instruction::FAdd:
 625     case Instruction::Sub:
 626     case Instruction::FSub:
 627     case Instruction::Mul:
 628     case Instruction::FMul:
 629     case Instruction::UDiv:
 630     case Instruction::SDiv:
 631     case Instruction::FDiv:
 632     case Instruction::URem:
 633     case Instruction::SRem:
 634     case Instruction::FRem:
 635     case Instruction::Shl:
 636     case Instruction::LShr:
 637     case Instruction::AShr:
 638     case Instruction::And:
 639     case Instruction::Or:
 640     case Instruction::Xor: {
 641       BinaryOperator *BO = cast<BinaryOperator>(I);
 642       assert(NewOps.size() == 2 && "binary operator with #ops != 2");
 643       BinaryOperator *New =
 644           BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
 645                                  NewOps[0], NewOps[1], "", BO);
 646       if (isa<OverflowingBinaryOperator>(BO)) {
 647         New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
 648         New->setHasNoSignedWrap(BO->hasNoSignedWrap());
 649       }
 650       if (isa<PossiblyExactOperator>(BO)) {
 651         New->setIsExact(BO->isExact());
 652       }
 653       if (isa<FPMathOperator>(BO))
 654         New->copyFastMathFlags(I);
 655       return New;
 656     }
 657     case Instruction::ICmp:
 658       assert(NewOps.size() == 2 && "icmp with #ops != 2");
 659       return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
 660                           NewOps[0], NewOps[1]);
 661     case Instruction::FCmp:
 662       assert(NewOps.size() == 2 && "fcmp with #ops != 2");
 663       return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
 664                           NewOps[0], NewOps[1]);
 665     case Instruction::Trunc:
 666     case Instruction::ZExt:
 667     case Instruction::SExt:
 668     case Instruction::FPToUI:
 669     case Instruction::FPToSI:
 670     case Instruction::UIToFP:
 671     case Instruction::SIToFP:
 672     case Instruction::FPTrunc:
 673     case Instruction::FPExt: {
 674       // It's possible that the mask has a different number of elements from
 675       // the original cast. We recompute the destination type to match the mask.
 676       Type *DestTy =
 677           VectorType::get(I->getType()->getScalarType(),
 678                           NewOps[0]->getType()->getVectorNumElements());
 679       assert(NewOps.size() == 1 && "cast with #ops != 1");
 680       return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
 681                               "", I);
 682     }
 683     case Instruction::GetElementPtr: {
 684       Value *Ptr = NewOps[0];
 685       ArrayRef<Value*> Idx = NewOps.slice(1);
 686       GetElementPtrInst *GEP = GetElementPtrInst::Create(
 687           cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
 688       GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
 689       return GEP;
 690     }
 691   }
 692   llvm_unreachable("failed to rebuild vector instructions");
 693 }
 694
 695 Value *
 696 InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
 697   // Mask.size() does not need to be equal to the number of vector elements.
 698
 699   assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
 700   if (isa<UndefValue>(V)) {
 701     return UndefValue::get(VectorType::get(V->getType()->getScalarType(),
 702                                            Mask.size()));
 703   }
 704   if (isa<ConstantAggregateZero>(V)) {
 705     return ConstantAggregateZero::get(
 706                VectorType::get(V->getType()->getScalarType(),
 707                                Mask.size()));
 708   }
 709   if (Constant *C = dyn_cast<Constant>(V)) {
 710     SmallVector<Constant *, 16> MaskValues;
 711     for (int i = 0, e = Mask.size(); i != e; ++i) {
 712       if (Mask[i] == -1)
 713         MaskValues.push_back(UndefValue::get(Builder->getInt32Ty()));
 714       else
 715         MaskValues.push_back(Builder->getInt32(Mask[i]));
 716     }
 717     return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()),
 718                                           ConstantVector::get(MaskValues));
 719   }
 720
 721   Instruction *I = cast<Instruction>(V);
 722   switch (I->getOpcode()) {
 723     case Instruction::Add:
 724     case Instruction::FAdd:
 725     case Instruction::Sub:
 726     case Instruction::FSub:
 727     case Instruction::Mul:
 728     case Instruction::FMul:
 729     case Instruction::UDiv:
 730     case Instruction::SDiv:
 731     case Instruction::FDiv:
 732     case Instruction::URem:
 733     case Instruction::SRem:
 734     case Instruction::FRem:
 735     case Instruction::Shl:
 736     case Instruction::LShr:
 737     case Instruction::AShr:
 738     case Instruction::And:
 739     case Instruction::Or:
 740     case Instruction::Xor:
 741     case Instruction::ICmp:
 742     case Instruction::FCmp:
 743     case Instruction::Trunc:
 744     case Instruction::ZExt:
 745     case Instruction::SExt:
 746     case Instruction::FPToUI:
 747     case Instruction::FPToSI:
 748     case Instruction::UIToFP:
 749     case Instruction::SIToFP:
 750     case Instruction::FPTrunc:
 751     case Instruction::FPExt:
 752     case Instruction::Select:
 753     case Instruction::GetElementPtr: {
 754       SmallVector<Value*, 8> NewOps;
 755       bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
 756       for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
 757         Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask);
 758         NewOps.push_back(V);
 759         NeedsRebuild |= (V != I->getOperand(i));
 760       }
 761       if (NeedsRebuild) {
 762         return BuildNew(I, NewOps);
 763       }
 764       return I;
 765     }
 766     case Instruction::InsertElement: {
 767       int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
 768
 769       // The insertelement was inserting at Element. Figure out which element
 770       // that becomes after shuffling. The answer is guaranteed to be unique
 771       // by CanEvaluateShuffled.
 772       bool Found = false;
 773       int Index = 0;
 774       for (int e = Mask.size(); Index != e; ++Index) {
 775         if (Mask[Index] == Element) {
 776           Found = true;
 777           break;
 778         }
 779       }
 780
 781       // If element is not in Mask, no need to handle the operand 1 (element to
 782       // be inserted). Just evaluate values in operand 0 according to Mask.
 783       if (!Found)
 784         return EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
 785
 786       Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
 787       return InsertElementInst::Create(V, I->getOperand(1),
 788                                        Builder->getInt32(Index), "", I);
 789     }
 790   }
 791   llvm_unreachable("failed to reorder elements of vector instruction!");
 792 }
 793
 794 static void RecognizeIdentityMask(const SmallVectorImpl<int> &Mask,
 795                                   bool &isLHSID, bool &isRHSID) {
 796   isLHSID = isRHSID = true;
 797
 798   for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
 799     if (Mask[i] < 0) continue;  // Ignore undef values.
 800     // Is this an identity shuffle of the LHS value?
 801     isLHSID &= (Mask[i] == (int)i);
 802
 803     // Is this an identity shuffle of the RHS value?
 804     isRHSID &= (Mask[i]-e == i);
 805   }
 806 }
 807
 808 // Returns true if the shuffle is extracting a contiguous range of values from
 809 // LHS, for example:
 810 //                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 811 //   Input:        |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
 812 //   Shuffles to:  |EE|FF|GG|HH|
 813 //                 +--+--+--+--+
 814 static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
 815                                        SmallVector<int, 16> &Mask) {
 816   unsigned LHSElems =
 817       cast<VectorType>(SVI.getOperand(0)->getType())->getNumElements();
 818   unsigned MaskElems = Mask.size();
 819   unsigned BegIdx = Mask.front();
 820   unsigned EndIdx = Mask.back();
 821   if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
 822     return false;
 823   for (unsigned I = 0; I != MaskElems; ++I)
 824     if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
 825       return false;
 826   return true;
 827 }
 828
 829 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
 830   Value *LHS = SVI.getOperand(0);
 831   Value *RHS = SVI.getOperand(1);
 832   SmallVector<int, 16> Mask = SVI.getShuffleMask();
 833   Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
 834
 835   bool MadeChange = false;
 836
 837   // Undefined shuffle mask -> undefined value.
 838   if (isa<UndefValue>(SVI.getOperand(2)))
 839     return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType()));
 840
 841   unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements();
 842
 843   APInt UndefElts(VWidth, 0);
 844   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 845   if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
 846     if (V != &SVI)
 847       return ReplaceInstUsesWith(SVI, V);
 848     LHS = SVI.getOperand(0);
 849     RHS = SVI.getOperand(1);
 850     MadeChange = true;
 851   }
 852
 853   unsigned LHSWidth = cast<VectorType>(LHS->getType())->getNumElements();
 854
 855   // Canonicalize shuffle(x    ,x,mask) -> shuffle(x, undef,mask')
 856   // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
 857   if (LHS == RHS || isa<UndefValue>(LHS)) {
 858     if (isa<UndefValue>(LHS) && LHS == RHS) {
 859       // shuffle(undef,undef,mask) -> undef.
 860       Value *Result = (VWidth == LHSWidth)
 861                       ? LHS : UndefValue::get(SVI.getType());
 862       return ReplaceInstUsesWith(SVI, Result);
 863     }
 864
 865     // Remap any references to RHS to use LHS.
 866     SmallVector<Constant*, 16> Elts;
 867     for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
 868       if (Mask[i] < 0) {
 869         Elts.push_back(UndefValue::get(Int32Ty));
 870         continue;
 871       }
 872
 873       if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
 874           (Mask[i] <  (int)e && isa<UndefValue>(LHS))) {
 875         Mask[i] = -1;     // Turn into undef.
 876         Elts.push_back(UndefValue::get(Int32Ty));
 877       } else {
 878         Mask[i] = Mask[i] % e;  // Force to LHS.
 879         Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
 880       }
 881     }
 882     SVI.setOperand(0, SVI.getOperand(1));
 883     SVI.setOperand(1, UndefValue::get(RHS->getType()));
 884     SVI.setOperand(2, ConstantVector::get(Elts));
 885     LHS = SVI.getOperand(0);
 886     RHS = SVI.getOperand(1);
 887     MadeChange = true;
 888   }
 889
 890   if (VWidth == LHSWidth) {
 891     // Analyze the shuffle, are the LHS or RHS and identity shuffles?
 892     bool isLHSID, isRHSID;
 893     RecognizeIdentityMask(Mask, isLHSID, isRHSID);
 894
 895     // Eliminate identity shuffles.
 896     if (isLHSID) return ReplaceInstUsesWith(SVI, LHS);
 897     if (isRHSID) return ReplaceInstUsesWith(SVI, RHS);
 898   }
 899
 900   if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
 901     Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
 902     return ReplaceInstUsesWith(SVI, V);
 903   }
 904
 905   // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
 906   // a non-vector type. We can instead bitcast the original vector followed by
 907   // an extract of the desired element:
 908   //
 909   //   %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
 910   //                         <4 x i32> <i32 0, i32 1, i32 2, i32 3>
 911   //   %1 = bitcast <4 x i8> %sroa to i32
 912   // Becomes:
 913   //   %bc = bitcast <16 x i8> %in to <4 x i32>
 914   //   %ext = extractelement <4 x i32> %bc, i32 0
 915   //
 916   // If the shuffle is extracting a contiguous range of values from the input
 917   // vector then each use which is a bitcast of the extracted size can be
 918   // replaced. This will work if the vector types are compatible, and the begin
 919   // index is aligned to a value in the casted vector type. If the begin index
 920   // isn't aligned then we can shuffle the original vector (keeping the same
 921   // vector type) before extracting.
 922   //
 923   // This code will bail out if the target type is fundamentally incompatible
 924   // with vectors of the source type.
 925   //
 926   // Example of <16 x i8>, target type i32:
 927   // Index range [4,8):         v-----------v Will work.
 928   //                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
 929   //     <16 x i8>: |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
 930   //     <4 x i32>: |           |           |           |           |
 931   //                +-----------+-----------+-----------+-----------+
 932   // Index range [6,10):              ^-----------^ Needs an extra shuffle.
 933   // Target type i40:           ^--------------^ Won't work, bail.
 934   if (isShuffleExtractingFromLHS(SVI, Mask)) {
 935     Value *V = LHS;
 936     unsigned MaskElems = Mask.size();
 937     unsigned BegIdx = Mask.front();
 938     VectorType *SrcTy = cast<VectorType>(V->getType());
 939     unsigned VecBitWidth = SrcTy->getBitWidth();
 940     unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
 941     assert(SrcElemBitWidth && "vector elements must have a bitwidth");
 942     unsigned SrcNumElems = SrcTy->getNumElements();
 943     SmallVector<BitCastInst *, 8> BCs;
 944     DenseMap<Type *, Value *> NewBCs;
 945     for (User *U : SVI.users())
 946       if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
 947         if (!BC->use_empty())
 948           // Only visit bitcasts that weren't previously handled.
 949           BCs.push_back(BC);
 950     for (BitCastInst *BC : BCs) {
 951       Type *TgtTy = BC->getDestTy();
 952       unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
 953       if (!TgtElemBitWidth)
 954         continue;
 955       unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
 956       bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
 957       bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
 958       if (!VecBitWidthsEqual)
 959         continue;
 960       if (!VectorType::isValidElementType(TgtTy))
 961         continue;
 962       VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
 963       if (!BegIsAligned) {
 964         // Shuffle the input so [0,NumElements) contains the output, and
 965         // [NumElems,SrcNumElems) is undef.
 966         SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
 967                                                 UndefValue::get(Int32Ty));
 968         for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
 969           ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
 970         V = Builder->CreateShuffleVector(V, UndefValue::get(V->getType()),
 971                                          ConstantVector::get(ShuffleMask),
 972                                          SVI.getName() + ".extract");
 973         BegIdx = 0;
 974       }
 975       unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
 976       assert(SrcElemsPerTgtElem);
 977       BegIdx /= SrcElemsPerTgtElem;
 978       bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
 979       auto *NewBC =
 980           BCAlreadyExists
 981               ? NewBCs[CastSrcTy]
 982               : Builder->CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
 983       if (!BCAlreadyExists)
 984         NewBCs[CastSrcTy] = NewBC;
 985       auto *Ext = Builder->CreateExtractElement(
 986           NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
 987       // The shufflevector isn't being replaced: the bitcast that used it
 988       // is. InstCombine will visit the newly-created instructions.
 989       ReplaceInstUsesWith(*BC, Ext);
 990       MadeChange = true;
 991     }
 992   }
 993
 994   // If the LHS is a shufflevector itself, see if we can combine it with this
 995   // one without producing an unusual shuffle.
 996   // Cases that might be simplified:
 997   // 1.
 998   // x1=shuffle(v1,v2,mask1)
 999   //  x=shuffle(x1,undef,mask)
1000   //        ==>
1001   //  x=shuffle(v1,undef,newMask)
1002   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1003   // 2.
1004   // x1=shuffle(v1,undef,mask1)
1005   //  x=shuffle(x1,x2,mask)
1006   // where v1.size() == mask1.size()
1007   //        ==>
1008   //  x=shuffle(v1,x2,newMask)
1009   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1010   // 3.
1011   // x2=shuffle(v2,undef,mask2)
1012   //  x=shuffle(x1,x2,mask)
1013   // where v2.size() == mask2.size()
1014   //        ==>
1015   //  x=shuffle(x1,v2,newMask)
1016   // newMask[i] = (mask[i] < x1.size())
1017   //              ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1018   // 4.
1019   // x1=shuffle(v1,undef,mask1)
1020   // x2=shuffle(v2,undef,mask2)
1021   //  x=shuffle(x1,x2,mask)
1022   // where v1.size() == v2.size()
1023   //        ==>
1024   //  x=shuffle(v1,v2,newMask)
1025   // newMask[i] = (mask[i] < x1.size())
1026   //              ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1027   //
1028   // Here we are really conservative:
1029   // we are absolutely afraid of producing a shuffle mask not in the input
1030   // program, because the code gen may not be smart enough to turn a merged
1031   // shuffle into two specific shuffles: it may produce worse code.  As such,
1032   // we only merge two shuffles if the result is either a splat or one of the
1033   // input shuffle masks.  In this case, merging the shuffles just removes
1034   // one instruction, which we know is safe.  This is good for things like
1035   // turning: (splat(splat)) -> splat, or
1036   // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1037   ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1038   ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1039   if (LHSShuffle)
1040     if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1041       LHSShuffle = nullptr;
1042   if (RHSShuffle)
1043     if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1044       RHSShuffle = nullptr;
1045   if (!LHSShuffle && !RHSShuffle)
1046     return MadeChange ? &SVI : nullptr;
1047
1048   Value* LHSOp0 = nullptr;
1049   Value* LHSOp1 = nullptr;
1050   Value* RHSOp0 = nullptr;
1051   unsigned LHSOp0Width = 0;
1052   unsigned RHSOp0Width = 0;
1053   if (LHSShuffle) {
1054     LHSOp0 = LHSShuffle->getOperand(0);
1055     LHSOp1 = LHSShuffle->getOperand(1);
1056     LHSOp0Width = cast<VectorType>(LHSOp0->getType())->getNumElements();
1057   }
1058   if (RHSShuffle) {
1059     RHSOp0 = RHSShuffle->getOperand(0);
1060     RHSOp0Width = cast<VectorType>(RHSOp0->getType())->getNumElements();
1061   }
1062   Value* newLHS = LHS;
1063   Value* newRHS = RHS;
1064   if (LHSShuffle) {
1065     // case 1
1066     if (isa<UndefValue>(RHS)) {
1067       newLHS = LHSOp0;
1068       newRHS = LHSOp1;
1069     }
1070     // case 2 or 4
1071     else if (LHSOp0Width == LHSWidth) {
1072       newLHS = LHSOp0;
1073     }
1074   }
1075   // case 3 or 4
1076   if (RHSShuffle && RHSOp0Width == LHSWidth) {
1077     newRHS = RHSOp0;
1078   }
1079   // case 4
1080   if (LHSOp0 == RHSOp0) {
1081     newLHS = LHSOp0;
1082     newRHS = nullptr;
1083   }
1084
1085   if (newLHS == LHS && newRHS == RHS)
1086     return MadeChange ? &SVI : nullptr;
1087
1088   SmallVector<int, 16> LHSMask;
1089   SmallVector<int, 16> RHSMask;
1090   if (newLHS != LHS)
1091     LHSMask = LHSShuffle->getShuffleMask();
1092   if (RHSShuffle && newRHS != RHS)
1093     RHSMask = RHSShuffle->getShuffleMask();
1094
1095   unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1096   SmallVector<int, 16> newMask;
1097   bool isSplat = true;
1098   int SplatElt = -1;
1099   // Create a new mask for the new ShuffleVectorInst so that the new
1100   // ShuffleVectorInst is equivalent to the original one.
1101   for (unsigned i = 0; i < VWidth; ++i) {
1102     int eltMask;
1103     if (Mask[i] < 0) {
1104       // This element is an undef value.
1105       eltMask = -1;
1106     } else if (Mask[i] < (int)LHSWidth) {
1107       // This element is from left hand side vector operand.
1108       //
1109       // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1110       // new mask value for the element.
1111       if (newLHS != LHS) {
1112         eltMask = LHSMask[Mask[i]];
1113         // If the value selected is an undef value, explicitly specify it
1114         // with a -1 mask value.
1115         if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1116           eltMask = -1;
1117       } else
1118         eltMask = Mask[i];
1119     } else {
1120       // This element is from right hand side vector operand
1121       //
1122       // If the value selected is an undef value, explicitly specify it
1123       // with a -1 mask value. (case 1)
1124       if (isa<UndefValue>(RHS))
1125         eltMask = -1;
1126       // If RHS is going to be replaced (case 3 or 4), calculate the
1127       // new mask value for the element.
1128       else if (newRHS != RHS) {
1129         eltMask = RHSMask[Mask[i]-LHSWidth];
1130         // If the value selected is an undef value, explicitly specify it
1131         // with a -1 mask value.
1132         if (eltMask >= (int)RHSOp0Width) {
1133           assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1134                  && "should have been check above");
1135           eltMask = -1;
1136         }
1137       } else
1138         eltMask = Mask[i]-LHSWidth;
1139
1140       // If LHS's width is changed, shift the mask value accordingly.
1141       // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any
1142       // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1143       // If newRHS == newLHS, we want to remap any references from newRHS to
1144       // newLHS so that we can properly identify splats that may occur due to
1145       // obfuscation across the two vectors.
1146       if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1147         eltMask += newLHSWidth;
1148     }
1149
1150     // Check if this could still be a splat.
1151     if (eltMask >= 0) {
1152       if (SplatElt >= 0 && SplatElt != eltMask)
1153         isSplat = false;
1154       SplatElt = eltMask;
1155     }
1156
1157     newMask.push_back(eltMask);
1158   }
1159
1160   // If the result mask is equal to one of the original shuffle masks,
1161   // or is a splat, do the replacement.
1162   if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1163     SmallVector<Constant*, 16> Elts;
1164     for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1165       if (newMask[i] < 0) {
1166         Elts.push_back(UndefValue::get(Int32Ty));
1167       } else {
1168         Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1169       }
1170     }
1171     if (!newRHS)
1172       newRHS = UndefValue::get(newLHS->getType());
1173     return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1174   }
1175
1176   // If the result mask is an identity, replace uses of this instruction with
1177   // corresponding argument.
1178   bool isLHSID, isRHSID;
1179   RecognizeIdentityMask(newMask, isLHSID, isRHSID);
1180   if (isLHSID && VWidth == LHSOp0Width) return ReplaceInstUsesWith(SVI, newLHS);
1181   if (isRHSID && VWidth == RHSOp0Width) return ReplaceInstUsesWith(SVI, newRHS);
1182
1183   return MadeChange ? &SVI : nullptr;
1184 }