contrib/llvm/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/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"
  21 #include "llvm/Analysis/InstructionSimplify.h"
  22 #include "llvm/Analysis/VectorUtils.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"
  36 #include "llvm/Support/ErrorHandling.h"
  37 #include "llvm/Transforms/InstCombine/InstCombineWorklist.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   }
  64   Instruction *I = dyn_cast<Instruction>(V);
  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) {
  92   SmallVector<Instruction *, 2> Extracts;
  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(
 142           BinaryOperator::CreateWithCopiedFlags(B0->getOpcode(),
 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
 169 Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
 170   if (Value *V = SimplifyExtractElementInst(EI.getVectorOperand(),
 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         }
 268         Type *Int32Ty = Type::getInt32Ty(EI.getContext());
 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,
 291                                          SmallVectorImpl<Constant*> &Mask) {
 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)
 303       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 304     return true;
 305   }
 306
 307   if (V == RHS) {
 308     for (unsigned i = 0; i != NumElts; ++i)
 309       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
 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] =
 346               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 347                                ExtractedIdx);
 348             } else {
 349               assert(EI->getOperand(0) == RHS);
 350               Mask[InsertedIdx % NumElts] =
 351               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 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.
 367 static void replaceExtractElements(InsertElementInst *InsElt,
 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()) {
 432     ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U);
 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
 451 static ShuffleOps collectShuffleElements(Value *V,
 452                                          SmallVectorImpl<Constant *> &Mask,
 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] =
 502             ConstantInt::get(Type::getInt32Ty(V->getContext()),
 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 =
 511               EI->getOperand(0)->getType()->getVectorNumElements();
 512           for (unsigned i = 0; i != NumElts; ++i)
 513             Mask.push_back(ConstantInt::get(
 514                 Type::getInt32Ty(V->getContext()),
 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)
 531     Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), 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
 542 Instruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) {
 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
 570 static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) {
 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)
 593 static Instruction *foldInsSequenceIntoBroadcast(InsertElementInst &InsElt) {
 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,
 643         ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), 0),
 644         "", &InsElt);
 645
 646   Constant *ZeroMask = ConstantAggregateZero::get(
 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.
 661 static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
 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'
 684 static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
 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);
 750     SmallVector<Constant *, 16> Mask(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
 781 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
 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 =
 800           EI->getOperand(0)->getType()->getVectorNumElements();
 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())) {
 819         SmallVector<Constant*, 16> Mask;
 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
 844   if (Instruction *Shuf = foldConstantInsEltIntoShuffle(IE))
 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.
 860 static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask,
 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.
 867   Instruction *I = dyn_cast<Instruction>(V);
 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: {
 914       ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2));
 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.
 936 static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) {
 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");
 960       BinaryOperator *New =
 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 =
 994           VectorType::get(I->getType()->getScalarType(),
 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);
1003       GetElementPtrInst *GEP = GetElementPtrInst::Create(
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     }
1032     return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()),
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
1109 static void recognizeIdentityMask(const SmallVectorImpl<int> &Mask,
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 //                 +--+--+--+--+
1129 static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
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 {
1146   BinaryOperator::BinaryOps Opcode;
1147   Value *Op0;
1148   Value *Op1;
1149   BinopElts(BinaryOperator::BinaryOps Opc = (BinaryOperator::BinaryOps)0,
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.
1159 static BinopElts getAlternateBinop(BinaryOperator *BO, const DataLayout &DL) {
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
1185 static Instruction *foldSelectShuffleWith1Binop(ShuffleVectorInst &Shuf) {
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.
1238 static Instruction *foldSelectShuffle(ShuffleVectorInst &Shuf,
1239                                       InstCombiner::BuilderTy &Builder,
1240                                       const DataLayout &DL) {
1241   if (!Shuf.isSelect())
1242     return nullptr;
1243
1244   if (Instruction *I = foldSelectShuffleWith1Binop(Shuf))
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() &&
1300       (Instruction::isIntDivRem(BOpc) || Instruction::isShift(BOpc));
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
1353 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
1354   Value *LHS = SVI.getOperand(0);
1355   Value *RHS = SVI.getOperand(1);
1356   SmallVector<int, 16> Mask = SVI.getShuffleMask();
1357   Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
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.
1390     SmallVector<Constant*, 16> Elts;
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();
1466     SmallVector<BitCastInst *, 8> BCs;
1467     DenseMap<Type *, Value *> NewBCs;
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) {
1687     SmallVector<Constant*, 16> Elts;
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 }