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 IndexVal = IdxC->getZExtValue();
 185     unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
 186
 187     // InstSimplify handles cases where the index is invalid.
 188     assert(IndexVal < VectorWidth);
 189
 190     // This instruction only demands the single element from the input vector.
 191     // If the input vector has a single use, simplify it based on this use
 192     // property.
 193     if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
 194       APInt UndefElts(VectorWidth, 0);
 195       APInt DemandedMask(VectorWidth, 0);
 196       DemandedMask.setBit(IndexVal);
 197       if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask,
 198                                                 UndefElts)) {
 199         EI.setOperand(0, V);
 200         return &EI;
 201       }
 202     }
 203
 204     // If this extractelement is directly using a bitcast from a vector of
 205     // the same number of elements, see if we can find the source element from
 206     // it.  In this case, we will end up needing to bitcast the scalars.
 207     if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
 208       if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
 209         if (VT->getNumElements() == VectorWidth)
 210           if (Value *Elt = findScalarElement(BCI->getOperand(0), IndexVal))
 211             return new BitCastInst(Elt, EI.getType());
 212     }
 213
 214     // If there's a vector PHI feeding a scalar use through this extractelement
 215     // instruction, try to scalarize the PHI.
 216     if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) {
 217       Instruction *scalarPHI = scalarizePHI(EI, PN);
 218       if (scalarPHI)
 219         return scalarPHI;
 220     }
 221   }
 222
 223   if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
 224     // Push extractelement into predecessor operation if legal and
 225     // profitable to do so.
 226     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 227       if (I->hasOneUse() &&
 228           cheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
 229         Value *newEI0 =
 230           Builder.CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
 231                                        EI.getName()+".lhs");
 232         Value *newEI1 =
 233           Builder.CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
 234                                        EI.getName()+".rhs");
 235         return BinaryOperator::CreateWithCopiedFlags(BO->getOpcode(),
 236                                                      newEI0, newEI1, BO);
 237       }
 238     } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
 239       // Extracting the inserted element?
 240       if (IE->getOperand(2) == EI.getOperand(1))
 241         return replaceInstUsesWith(EI, IE->getOperand(1));
 242       // If the inserted and extracted elements are constants, they must not
 243       // be the same value, extract from the pre-inserted value instead.
 244       if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
 245         Worklist.AddValue(EI.getOperand(0));
 246         EI.setOperand(0, IE->getOperand(0));
 247         return &EI;
 248       }
 249     } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
 250       // If this is extracting an element from a shufflevector, figure out where
 251       // it came from and extract from the appropriate input element instead.
 252       if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 253         int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
 254         Value *Src;
 255         unsigned LHSWidth =
 256           SVI->getOperand(0)->getType()->getVectorNumElements();
 257
 258         if (SrcIdx < 0)
 259           return replaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 260         if (SrcIdx < (int)LHSWidth)
 261           Src = SVI->getOperand(0);
 262         else {
 263           SrcIdx -= LHSWidth;
 264           Src = SVI->getOperand(1);
 265         }
 266         Type *Int32Ty = Type::getInt32Ty(EI.getContext());
 267         return ExtractElementInst::Create(Src,
 268                                           ConstantInt::get(Int32Ty,
 269                                                            SrcIdx, false));
 270       }
 271     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 272       // Canonicalize extractelement(cast) -> cast(extractelement).
 273       // Bitcasts can change the number of vector elements, and they cost
 274       // nothing.
 275       if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) {
 276         Value *EE = Builder.CreateExtractElement(CI->getOperand(0),
 277                                                  EI.getIndexOperand());
 278         Worklist.AddValue(EE);
 279         return CastInst::Create(CI->getOpcode(), EE, EI.getType());
 280       }
 281     }
 282   }
 283   return nullptr;
 284 }
 285
 286 /// If V is a shuffle of values that ONLY returns elements from either LHS or
 287 /// RHS, return the shuffle mask and true. Otherwise, return false.
 288 static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
 289                                          SmallVectorImpl<Constant*> &Mask) {
 290   assert(LHS->getType() == RHS->getType() &&
 291          "Invalid CollectSingleShuffleElements");
 292   unsigned NumElts = V->getType()->getVectorNumElements();
 293
 294   if (isa<UndefValue>(V)) {
 295     Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 296     return true;
 297   }
 298
 299   if (V == LHS) {
 300     for (unsigned i = 0; i != NumElts; ++i)
 301       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 302     return true;
 303   }
 304
 305   if (V == RHS) {
 306     for (unsigned i = 0; i != NumElts; ++i)
 307       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
 308                                       i+NumElts));
 309     return true;
 310   }
 311
 312   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 313     // If this is an insert of an extract from some other vector, include it.
 314     Value *VecOp    = IEI->getOperand(0);
 315     Value *ScalarOp = IEI->getOperand(1);
 316     Value *IdxOp    = IEI->getOperand(2);
 317
 318     if (!isa<ConstantInt>(IdxOp))
 319       return false;
 320     unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 321
 322     if (isa<UndefValue>(ScalarOp)) {  // inserting undef into vector.
 323       // We can handle this if the vector we are inserting into is
 324       // transitively ok.
 325       if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 326         // If so, update the mask to reflect the inserted undef.
 327         Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
 328         return true;
 329       }
 330     } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
 331       if (isa<ConstantInt>(EI->getOperand(1))) {
 332         unsigned ExtractedIdx =
 333         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 334         unsigned NumLHSElts = LHS->getType()->getVectorNumElements();
 335
 336         // This must be extracting from either LHS or RHS.
 337         if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
 338           // We can handle this if the vector we are inserting into is
 339           // transitively ok.
 340           if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 341             // If so, update the mask to reflect the inserted value.
 342             if (EI->getOperand(0) == LHS) {
 343               Mask[InsertedIdx % NumElts] =
 344               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 345                                ExtractedIdx);
 346             } else {
 347               assert(EI->getOperand(0) == RHS);
 348               Mask[InsertedIdx % NumElts] =
 349               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 350                                ExtractedIdx + NumLHSElts);
 351             }
 352             return true;
 353           }
 354         }
 355       }
 356     }
 357   }
 358
 359   return false;
 360 }
 361
 362 /// If we have insertion into a vector that is wider than the vector that we
 363 /// are extracting from, try to widen the source vector to allow a single
 364 /// shufflevector to replace one or more insert/extract pairs.
 365 static void replaceExtractElements(InsertElementInst *InsElt,
 366                                    ExtractElementInst *ExtElt,
 367                                    InstCombiner &IC) {
 368   VectorType *InsVecType = InsElt->getType();
 369   VectorType *ExtVecType = ExtElt->getVectorOperandType();
 370   unsigned NumInsElts = InsVecType->getVectorNumElements();
 371   unsigned NumExtElts = ExtVecType->getVectorNumElements();
 372
 373   // The inserted-to vector must be wider than the extracted-from vector.
 374   if (InsVecType->getElementType() != ExtVecType->getElementType() ||
 375       NumExtElts >= NumInsElts)
 376     return;
 377
 378   // Create a shuffle mask to widen the extended-from vector using undefined
 379   // values. The mask selects all of the values of the original vector followed
 380   // by as many undefined values as needed to create a vector of the same length
 381   // as the inserted-to vector.
 382   SmallVector<Constant *, 16> ExtendMask;
 383   IntegerType *IntType = Type::getInt32Ty(InsElt->getContext());
 384   for (unsigned i = 0; i < NumExtElts; ++i)
 385     ExtendMask.push_back(ConstantInt::get(IntType, i));
 386   for (unsigned i = NumExtElts; i < NumInsElts; ++i)
 387     ExtendMask.push_back(UndefValue::get(IntType));
 388
 389   Value *ExtVecOp = ExtElt->getVectorOperand();
 390   auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp);
 391   BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
 392                                    ? ExtVecOpInst->getParent()
 393                                    : ExtElt->getParent();
 394
 395   // TODO: This restriction matches the basic block check below when creating
 396   // new extractelement instructions. If that limitation is removed, this one
 397   // could also be removed. But for now, we just bail out to ensure that we
 398   // will replace the extractelement instruction that is feeding our
 399   // insertelement instruction. This allows the insertelement to then be
 400   // replaced by a shufflevector. If the insertelement is not replaced, we can
 401   // induce infinite looping because there's an optimization for extractelement
 402   // that will delete our widening shuffle. This would trigger another attempt
 403   // here to create that shuffle, and we spin forever.
 404   if (InsertionBlock != InsElt->getParent())
 405     return;
 406
 407   // TODO: This restriction matches the check in visitInsertElementInst() and
 408   // prevents an infinite loop caused by not turning the extract/insert pair
 409   // into a shuffle. We really should not need either check, but we're lacking
 410   // folds for shufflevectors because we're afraid to generate shuffle masks
 411   // that the backend can't handle.
 412   if (InsElt->hasOneUse() && isa<InsertElementInst>(InsElt->user_back()))
 413     return;
 414
 415   auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType),
 416                                         ConstantVector::get(ExtendMask));
 417
 418   // Insert the new shuffle after the vector operand of the extract is defined
 419   // (as long as it's not a PHI) or at the start of the basic block of the
 420   // extract, so any subsequent extracts in the same basic block can use it.
 421   // TODO: Insert before the earliest ExtractElementInst that is replaced.
 422   if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst))
 423     WideVec->insertAfter(ExtVecOpInst);
 424   else
 425     IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt());
 426
 427   // Replace extracts from the original narrow vector with extracts from the new
 428   // wide vector.
 429   for (User *U : ExtVecOp->users()) {
 430     ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U);
 431     if (!OldExt || OldExt->getParent() != WideVec->getParent())
 432       continue;
 433     auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1));
 434     NewExt->insertAfter(OldExt);
 435     IC.replaceInstUsesWith(*OldExt, NewExt);
 436   }
 437 }
 438
 439 /// We are building a shuffle to create V, which is a sequence of insertelement,
 440 /// extractelement pairs. If PermittedRHS is set, then we must either use it or
 441 /// not rely on the second vector source. Return a std::pair containing the
 442 /// left and right vectors of the proposed shuffle (or 0), and set the Mask
 443 /// parameter as required.
 444 ///
 445 /// Note: we intentionally don't try to fold earlier shuffles since they have
 446 /// often been chosen carefully to be efficiently implementable on the target.
 447 using ShuffleOps = std::pair<Value *, Value *>;
 448
 449 static ShuffleOps collectShuffleElements(Value *V,
 450                                          SmallVectorImpl<Constant *> &Mask,
 451                                          Value *PermittedRHS,
 452                                          InstCombiner &IC) {
 453   assert(V->getType()->isVectorTy() && "Invalid shuffle!");
 454   unsigned NumElts = V->getType()->getVectorNumElements();
 455
 456   if (isa<UndefValue>(V)) {
 457     Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 458     return std::make_pair(
 459         PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr);
 460   }
 461
 462   if (isa<ConstantAggregateZero>(V)) {
 463     Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
 464     return std::make_pair(V, nullptr);
 465   }
 466
 467   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 468     // If this is an insert of an extract from some other vector, include it.
 469     Value *VecOp    = IEI->getOperand(0);
 470     Value *ScalarOp = IEI->getOperand(1);
 471     Value *IdxOp    = IEI->getOperand(2);
 472
 473     if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 474       if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
 475         unsigned ExtractedIdx =
 476           cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 477         unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 478
 479         // Either the extracted from or inserted into vector must be RHSVec,
 480         // otherwise we'd end up with a shuffle of three inputs.
 481         if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) {
 482           Value *RHS = EI->getOperand(0);
 483           ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC);
 484           assert(LR.second == nullptr || LR.second == RHS);
 485
 486           if (LR.first->getType() != RHS->getType()) {
 487             // Although we are giving up for now, see if we can create extracts
 488             // that match the inserts for another round of combining.
 489             replaceExtractElements(IEI, EI, IC);
 490
 491             // We tried our best, but we can't find anything compatible with RHS
 492             // further up the chain. Return a trivial shuffle.
 493             for (unsigned i = 0; i < NumElts; ++i)
 494               Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i);
 495             return std::make_pair(V, nullptr);
 496           }
 497
 498           unsigned NumLHSElts = RHS->getType()->getVectorNumElements();
 499           Mask[InsertedIdx % NumElts] =
 500             ConstantInt::get(Type::getInt32Ty(V->getContext()),
 501                              NumLHSElts+ExtractedIdx);
 502           return std::make_pair(LR.first, RHS);
 503         }
 504
 505         if (VecOp == PermittedRHS) {
 506           // We've gone as far as we can: anything on the other side of the
 507           // extractelement will already have been converted into a shuffle.
 508           unsigned NumLHSElts =
 509               EI->getOperand(0)->getType()->getVectorNumElements();
 510           for (unsigned i = 0; i != NumElts; ++i)
 511             Mask.push_back(ConstantInt::get(
 512                 Type::getInt32Ty(V->getContext()),
 513                 i == InsertedIdx ? ExtractedIdx : NumLHSElts + i));
 514           return std::make_pair(EI->getOperand(0), PermittedRHS);
 515         }
 516
 517         // If this insertelement is a chain that comes from exactly these two
 518         // vectors, return the vector and the effective shuffle.
 519         if (EI->getOperand(0)->getType() == PermittedRHS->getType() &&
 520             collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS,
 521                                          Mask))
 522           return std::make_pair(EI->getOperand(0), PermittedRHS);
 523       }
 524     }
 525   }
 526
 527   // Otherwise, we can't do anything fancy. Return an identity vector.
 528   for (unsigned i = 0; i != NumElts; ++i)
 529     Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 530   return std::make_pair(V, nullptr);
 531 }
 532
 533 /// Try to find redundant insertvalue instructions, like the following ones:
 534 ///  %0 = insertvalue { i8, i32 } undef, i8 %x, 0
 535 ///  %1 = insertvalue { i8, i32 } %0,    i8 %y, 0
 536 /// Here the second instruction inserts values at the same indices, as the
 537 /// first one, making the first one redundant.
 538 /// It should be transformed to:
 539 ///  %0 = insertvalue { i8, i32 } undef, i8 %y, 0
 540 Instruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) {
 541   bool IsRedundant = false;
 542   ArrayRef<unsigned int> FirstIndices = I.getIndices();
 543
 544   // If there is a chain of insertvalue instructions (each of them except the
 545   // last one has only one use and it's another insertvalue insn from this
 546   // chain), check if any of the 'children' uses the same indices as the first
 547   // instruction. In this case, the first one is redundant.
 548   Value *V = &I;
 549   unsigned Depth = 0;
 550   while (V->hasOneUse() && Depth < 10) {
 551     User *U = V->user_back();
 552     auto UserInsInst = dyn_cast<InsertValueInst>(U);
 553     if (!UserInsInst || U->getOperand(0) != V)
 554       break;
 555     if (UserInsInst->getIndices() == FirstIndices) {
 556       IsRedundant = true;
 557       break;
 558     }
 559     V = UserInsInst;
 560     Depth++;
 561   }
 562
 563   if (IsRedundant)
 564     return replaceInstUsesWith(I, I.getOperand(0));
 565   return nullptr;
 566 }
 567
 568 static bool isShuffleEquivalentToSelect(ShuffleVectorInst &Shuf) {
 569   int MaskSize = Shuf.getMask()->getType()->getVectorNumElements();
 570   int VecSize = Shuf.getOperand(0)->getType()->getVectorNumElements();
 571
 572   // A vector select does not change the size of the operands.
 573   if (MaskSize != VecSize)
 574     return false;
 575
 576   // Each mask element must be undefined or choose a vector element from one of
 577   // the source operands without crossing vector lanes.
 578   for (int i = 0; i != MaskSize; ++i) {
 579     int Elt = Shuf.getMaskValue(i);
 580     if (Elt != -1 && Elt != i && Elt != i + VecSize)
 581       return false;
 582   }
 583
 584   return true;
 585 }
 586
 587 // Turn a chain of inserts that splats a value into a canonical insert + shuffle
 588 // splat. That is:
 589 // insertelt(insertelt(insertelt(insertelt X, %k, 0), %k, 1), %k, 2) ... ->
 590 // shufflevector(insertelt(X, %k, 0), undef, zero)
 591 static Instruction *foldInsSequenceIntoBroadcast(InsertElementInst &InsElt) {
 592   // We are interested in the last insert in a chain. So, if this insert
 593   // has a single user, and that user is an insert, bail.
 594   if (InsElt.hasOneUse() && isa<InsertElementInst>(InsElt.user_back()))
 595     return nullptr;
 596
 597   VectorType *VT = cast<VectorType>(InsElt.getType());
 598   int NumElements = VT->getNumElements();
 599
 600   // Do not try to do this for a one-element vector, since that's a nop,
 601   // and will cause an inf-loop.
 602   if (NumElements == 1)
 603     return nullptr;
 604
 605   Value *SplatVal = InsElt.getOperand(1);
 606   InsertElementInst *CurrIE = &InsElt;
 607   SmallVector<bool, 16> ElementPresent(NumElements, false);
 608   InsertElementInst *FirstIE = nullptr;
 609
 610   // Walk the chain backwards, keeping track of which indices we inserted into,
 611   // until we hit something that isn't an insert of the splatted value.
 612   while (CurrIE) {
 613     auto *Idx = dyn_cast<ConstantInt>(CurrIE->getOperand(2));
 614     if (!Idx || CurrIE->getOperand(1) != SplatVal)
 615       return nullptr;
 616
 617     auto *NextIE = dyn_cast<InsertElementInst>(CurrIE->getOperand(0));
 618     // Check none of the intermediate steps have any additional uses, except
 619     // for the root insertelement instruction, which can be re-used, if it
 620     // inserts at position 0.
 621     if (CurrIE != &InsElt &&
 622         (!CurrIE->hasOneUse() && (NextIE != nullptr || !Idx->isZero())))
 623       return nullptr;
 624
 625     ElementPresent[Idx->getZExtValue()] = true;
 626     FirstIE = CurrIE;
 627     CurrIE = NextIE;
 628   }
 629
 630   // Make sure we've seen an insert into every element.
 631   if (llvm::any_of(ElementPresent, [](bool Present) { return !Present; }))
 632     return nullptr;
 633
 634   // All right, create the insert + shuffle.
 635   Instruction *InsertFirst;
 636   if (cast<ConstantInt>(FirstIE->getOperand(2))->isZero())
 637     InsertFirst = FirstIE;
 638   else
 639     InsertFirst = InsertElementInst::Create(
 640         UndefValue::get(VT), SplatVal,
 641         ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), 0),
 642         "", &InsElt);
 643
 644   Constant *ZeroMask = ConstantAggregateZero::get(
 645       VectorType::get(Type::getInt32Ty(InsElt.getContext()), NumElements));
 646
 647   return new ShuffleVectorInst(InsertFirst, UndefValue::get(VT), ZeroMask);
 648 }
 649
 650 /// If we have an insertelement instruction feeding into another insertelement
 651 /// and the 2nd is inserting a constant into the vector, canonicalize that
 652 /// constant insertion before the insertion of a variable:
 653 ///
 654 /// insertelement (insertelement X, Y, IdxC1), ScalarC, IdxC2 -->
 655 /// insertelement (insertelement X, ScalarC, IdxC2), Y, IdxC1
 656 ///
 657 /// This has the potential of eliminating the 2nd insertelement instruction
 658 /// via constant folding of the scalar constant into a vector constant.
 659 static Instruction *hoistInsEltConst(InsertElementInst &InsElt2,
 660                                      InstCombiner::BuilderTy &Builder) {
 661   auto *InsElt1 = dyn_cast<InsertElementInst>(InsElt2.getOperand(0));
 662   if (!InsElt1 || !InsElt1->hasOneUse())
 663     return nullptr;
 664
 665   Value *X, *Y;
 666   Constant *ScalarC;
 667   ConstantInt *IdxC1, *IdxC2;
 668   if (match(InsElt1->getOperand(0), m_Value(X)) &&
 669       match(InsElt1->getOperand(1), m_Value(Y)) && !isa<Constant>(Y) &&
 670       match(InsElt1->getOperand(2), m_ConstantInt(IdxC1)) &&
 671       match(InsElt2.getOperand(1), m_Constant(ScalarC)) &&
 672       match(InsElt2.getOperand(2), m_ConstantInt(IdxC2)) && IdxC1 != IdxC2) {
 673     Value *NewInsElt1 = Builder.CreateInsertElement(X, ScalarC, IdxC2);
 674     return InsertElementInst::Create(NewInsElt1, Y, IdxC1);
 675   }
 676
 677   return nullptr;
 678 }
 679
 680 /// insertelt (shufflevector X, CVec, Mask|insertelt X, C1, CIndex1), C, CIndex
 681 /// --> shufflevector X, CVec', Mask'
 682 static Instruction *foldConstantInsEltIntoShuffle(InsertElementInst &InsElt) {
 683   auto *Inst = dyn_cast<Instruction>(InsElt.getOperand(0));
 684   // Bail out if the parent has more than one use. In that case, we'd be
 685   // replacing the insertelt with a shuffle, and that's not a clear win.
 686   if (!Inst || !Inst->hasOneUse())
 687     return nullptr;
 688   if (auto *Shuf = dyn_cast<ShuffleVectorInst>(InsElt.getOperand(0))) {
 689     // The shuffle must have a constant vector operand. The insertelt must have
 690     // a constant scalar being inserted at a constant position in the vector.
 691     Constant *ShufConstVec, *InsEltScalar;
 692     uint64_t InsEltIndex;
 693     if (!match(Shuf->getOperand(1), m_Constant(ShufConstVec)) ||
 694         !match(InsElt.getOperand(1), m_Constant(InsEltScalar)) ||
 695         !match(InsElt.getOperand(2), m_ConstantInt(InsEltIndex)))
 696       return nullptr;
 697
 698     // Adding an element to an arbitrary shuffle could be expensive, but a
 699     // shuffle that selects elements from vectors without crossing lanes is
 700     // assumed cheap.
 701     // If we're just adding a constant into that shuffle, it will still be
 702     // cheap.
 703     if (!isShuffleEquivalentToSelect(*Shuf))
 704       return nullptr;
 705
 706     // From the above 'select' check, we know that the mask has the same number
 707     // of elements as the vector input operands. We also know that each constant
 708     // input element is used in its lane and can not be used more than once by
 709     // the shuffle. Therefore, replace the constant in the shuffle's constant
 710     // vector with the insertelt constant. Replace the constant in the shuffle's
 711     // mask vector with the insertelt index plus the length of the vector
 712     // (because the constant vector operand of a shuffle is always the 2nd
 713     // operand).
 714     Constant *Mask = Shuf->getMask();
 715     unsigned NumElts = Mask->getType()->getVectorNumElements();
 716     SmallVector<Constant *, 16> NewShufElts(NumElts);
 717     SmallVector<Constant *, 16> NewMaskElts(NumElts);
 718     for (unsigned I = 0; I != NumElts; ++I) {
 719       if (I == InsEltIndex) {
 720         NewShufElts[I] = InsEltScalar;
 721         Type *Int32Ty = Type::getInt32Ty(Shuf->getContext());
 722         NewMaskElts[I] = ConstantInt::get(Int32Ty, InsEltIndex + NumElts);
 723       } else {
 724         // Copy over the existing values.
 725         NewShufElts[I] = ShufConstVec->getAggregateElement(I);
 726         NewMaskElts[I] = Mask->getAggregateElement(I);
 727       }
 728     }
 729
 730     // Create new operands for a shuffle that includes the constant of the
 731     // original insertelt. The old shuffle will be dead now.
 732     return new ShuffleVectorInst(Shuf->getOperand(0),
 733                                  ConstantVector::get(NewShufElts),
 734                                  ConstantVector::get(NewMaskElts));
 735   } else if (auto *IEI = dyn_cast<InsertElementInst>(Inst)) {
 736     // Transform sequences of insertelements ops with constant data/indexes into
 737     // a single shuffle op.
 738     unsigned NumElts = InsElt.getType()->getNumElements();
 739
 740     uint64_t InsertIdx[2];
 741     Constant *Val[2];
 742     if (!match(InsElt.getOperand(2), m_ConstantInt(InsertIdx[0])) ||
 743         !match(InsElt.getOperand(1), m_Constant(Val[0])) ||
 744         !match(IEI->getOperand(2), m_ConstantInt(InsertIdx[1])) ||
 745         !match(IEI->getOperand(1), m_Constant(Val[1])))
 746       return nullptr;
 747     SmallVector<Constant *, 16> Values(NumElts);
 748     SmallVector<Constant *, 16> Mask(NumElts);
 749     auto ValI = std::begin(Val);
 750     // Generate new constant vector and mask.
 751     // We have 2 values/masks from the insertelements instructions. Insert them
 752     // into new value/mask vectors.
 753     for (uint64_t I : InsertIdx) {
 754       if (!Values[I]) {
 755         assert(!Mask[I]);
 756         Values[I] = *ValI;
 757         Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()),
 758                                    NumElts + I);
 759       }
 760       ++ValI;
 761     }
 762     // Remaining values are filled with 'undef' values.
 763     for (unsigned I = 0; I < NumElts; ++I) {
 764       if (!Values[I]) {
 765         assert(!Mask[I]);
 766         Values[I] = UndefValue::get(InsElt.getType()->getElementType());
 767         Mask[I] = ConstantInt::get(Type::getInt32Ty(InsElt.getContext()), I);
 768       }
 769     }
 770     // Create new operands for a shuffle that includes the constant of the
 771     // original insertelt.
 772     return new ShuffleVectorInst(IEI->getOperand(0),
 773                                  ConstantVector::get(Values),
 774                                  ConstantVector::get(Mask));
 775   }
 776   return nullptr;
 777 }
 778
 779 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
 780   Value *VecOp    = IE.getOperand(0);
 781   Value *ScalarOp = IE.getOperand(1);
 782   Value *IdxOp    = IE.getOperand(2);
 783
 784   if (auto *V = SimplifyInsertElementInst(
 785           VecOp, ScalarOp, IdxOp, SQ.getWithInstruction(&IE)))
 786     return replaceInstUsesWith(IE, V);
 787
 788   // Inserting an undef or into an undefined place, remove this.
 789   if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
 790     replaceInstUsesWith(IE, VecOp);
 791
 792   // If the inserted element was extracted from some other vector, and if the
 793   // indexes are constant, try to turn this into a shufflevector operation.
 794   if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 795     if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) {
 796       unsigned NumInsertVectorElts = IE.getType()->getNumElements();
 797       unsigned NumExtractVectorElts =
 798           EI->getOperand(0)->getType()->getVectorNumElements();
 799       unsigned ExtractedIdx =
 800         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 801       unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 802
 803       if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract.
 804         return replaceInstUsesWith(IE, VecOp);
 805
 806       if (InsertedIdx >= NumInsertVectorElts)  // Out of range insert.
 807         return replaceInstUsesWith(IE, UndefValue::get(IE.getType()));
 808
 809       // If we are extracting a value from a vector, then inserting it right
 810       // back into the same place, just use the input vector.
 811       if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
 812         return replaceInstUsesWith(IE, VecOp);
 813
 814       // If this insertelement isn't used by some other insertelement, turn it
 815       // (and any insertelements it points to), into one big shuffle.
 816       if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) {
 817         SmallVector<Constant*, 16> Mask;
 818         ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this);
 819
 820         // The proposed shuffle may be trivial, in which case we shouldn't
 821         // perform the combine.
 822         if (LR.first != &IE && LR.second != &IE) {
 823           // We now have a shuffle of LHS, RHS, Mask.
 824           if (LR.second == nullptr)
 825             LR.second = UndefValue::get(LR.first->getType());
 826           return new ShuffleVectorInst(LR.first, LR.second,
 827                                        ConstantVector::get(Mask));
 828         }
 829       }
 830     }
 831   }
 832
 833   unsigned VWidth = VecOp->getType()->getVectorNumElements();
 834   APInt UndefElts(VWidth, 0);
 835   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 836   if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
 837     if (V != &IE)
 838       return replaceInstUsesWith(IE, V);
 839     return &IE;
 840   }
 841
 842   if (Instruction *Shuf = foldConstantInsEltIntoShuffle(IE))
 843     return Shuf;
 844
 845   if (Instruction *NewInsElt = hoistInsEltConst(IE, Builder))
 846     return NewInsElt;
 847
 848   // Turn a sequence of inserts that broadcasts a scalar into a single
 849   // insert + shufflevector.
 850   if (Instruction *Broadcast = foldInsSequenceIntoBroadcast(IE))
 851     return Broadcast;
 852
 853   return nullptr;
 854 }
 855
 856 /// Return true if we can evaluate the specified expression tree if the vector
 857 /// elements were shuffled in a different order.
 858 static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask,
 859                                 unsigned Depth = 5) {
 860   // We can always reorder the elements of a constant.
 861   if (isa<Constant>(V))
 862     return true;
 863
 864   // We won't reorder vector arguments. No IPO here.
 865   Instruction *I = dyn_cast<Instruction>(V);
 866   if (!I) return false;
 867
 868   // Two users may expect different orders of the elements. Don't try it.
 869   if (!I->hasOneUse())
 870     return false;
 871
 872   if (Depth == 0) return false;
 873
 874   switch (I->getOpcode()) {
 875     case Instruction::Add:
 876     case Instruction::FAdd:
 877     case Instruction::Sub:
 878     case Instruction::FSub:
 879     case Instruction::Mul:
 880     case Instruction::FMul:
 881     case Instruction::UDiv:
 882     case Instruction::SDiv:
 883     case Instruction::FDiv:
 884     case Instruction::URem:
 885     case Instruction::SRem:
 886     case Instruction::FRem:
 887     case Instruction::Shl:
 888     case Instruction::LShr:
 889     case Instruction::AShr:
 890     case Instruction::And:
 891     case Instruction::Or:
 892     case Instruction::Xor:
 893     case Instruction::ICmp:
 894     case Instruction::FCmp:
 895     case Instruction::Trunc:
 896     case Instruction::ZExt:
 897     case Instruction::SExt:
 898     case Instruction::FPToUI:
 899     case Instruction::FPToSI:
 900     case Instruction::UIToFP:
 901     case Instruction::SIToFP:
 902     case Instruction::FPTrunc:
 903     case Instruction::FPExt:
 904     case Instruction::GetElementPtr: {
 905       for (Value *Operand : I->operands()) {
 906         if (!CanEvaluateShuffled(Operand, Mask, Depth-1))
 907           return false;
 908       }
 909       return true;
 910     }
 911     case Instruction::InsertElement: {
 912       ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2));
 913       if (!CI) return false;
 914       int ElementNumber = CI->getLimitedValue();
 915
 916       // Verify that 'CI' does not occur twice in Mask. A single 'insertelement'
 917       // can't put an element into multiple indices.
 918       bool SeenOnce = false;
 919       for (int i = 0, e = Mask.size(); i != e; ++i) {
 920         if (Mask[i] == ElementNumber) {
 921           if (SeenOnce)
 922             return false;
 923           SeenOnce = true;
 924         }
 925       }
 926       return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1);
 927     }
 928   }
 929   return false;
 930 }
 931
 932 /// Rebuild a new instruction just like 'I' but with the new operands given.
 933 /// In the event of type mismatch, the type of the operands is correct.
 934 static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) {
 935   // We don't want to use the IRBuilder here because we want the replacement
 936   // instructions to appear next to 'I', not the builder's insertion point.
 937   switch (I->getOpcode()) {
 938     case Instruction::Add:
 939     case Instruction::FAdd:
 940     case Instruction::Sub:
 941     case Instruction::FSub:
 942     case Instruction::Mul:
 943     case Instruction::FMul:
 944     case Instruction::UDiv:
 945     case Instruction::SDiv:
 946     case Instruction::FDiv:
 947     case Instruction::URem:
 948     case Instruction::SRem:
 949     case Instruction::FRem:
 950     case Instruction::Shl:
 951     case Instruction::LShr:
 952     case Instruction::AShr:
 953     case Instruction::And:
 954     case Instruction::Or:
 955     case Instruction::Xor: {
 956       BinaryOperator *BO = cast<BinaryOperator>(I);
 957       assert(NewOps.size() == 2 && "binary operator with #ops != 2");
 958       BinaryOperator *New =
 959           BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(),
 960                                  NewOps[0], NewOps[1], "", BO);
 961       if (isa<OverflowingBinaryOperator>(BO)) {
 962         New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap());
 963         New->setHasNoSignedWrap(BO->hasNoSignedWrap());
 964       }
 965       if (isa<PossiblyExactOperator>(BO)) {
 966         New->setIsExact(BO->isExact());
 967       }
 968       if (isa<FPMathOperator>(BO))
 969         New->copyFastMathFlags(I);
 970       return New;
 971     }
 972     case Instruction::ICmp:
 973       assert(NewOps.size() == 2 && "icmp with #ops != 2");
 974       return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(),
 975                           NewOps[0], NewOps[1]);
 976     case Instruction::FCmp:
 977       assert(NewOps.size() == 2 && "fcmp with #ops != 2");
 978       return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(),
 979                           NewOps[0], NewOps[1]);
 980     case Instruction::Trunc:
 981     case Instruction::ZExt:
 982     case Instruction::SExt:
 983     case Instruction::FPToUI:
 984     case Instruction::FPToSI:
 985     case Instruction::UIToFP:
 986     case Instruction::SIToFP:
 987     case Instruction::FPTrunc:
 988     case Instruction::FPExt: {
 989       // It's possible that the mask has a different number of elements from
 990       // the original cast. We recompute the destination type to match the mask.
 991       Type *DestTy =
 992           VectorType::get(I->getType()->getScalarType(),
 993                           NewOps[0]->getType()->getVectorNumElements());
 994       assert(NewOps.size() == 1 && "cast with #ops != 1");
 995       return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy,
 996                               "", I);
 997     }
 998     case Instruction::GetElementPtr: {
 999       Value *Ptr = NewOps[0];
1000       ArrayRef<Value*> Idx = NewOps.slice(1);
1001       GetElementPtrInst *GEP = GetElementPtrInst::Create(
1002           cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I);
1003       GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds());
1004       return GEP;
1005     }
1006   }
1007   llvm_unreachable("failed to rebuild vector instructions");
1008 }
1009
1010 Value *
1011 InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) {
1012   // Mask.size() does not need to be equal to the number of vector elements.
1013
1014   assert(V->getType()->isVectorTy() && "can't reorder non-vector elements");
1015   Type *EltTy = V->getType()->getScalarType();
1016   if (isa<UndefValue>(V))
1017     return UndefValue::get(VectorType::get(EltTy, Mask.size()));
1018
1019   if (isa<ConstantAggregateZero>(V))
1020     return ConstantAggregateZero::get(VectorType::get(EltTy, Mask.size()));
1021
1022   if (Constant *C = dyn_cast<Constant>(V)) {
1023     SmallVector<Constant *, 16> MaskValues;
1024     for (int i = 0, e = Mask.size(); i != e; ++i) {
1025       if (Mask[i] == -1)
1026         MaskValues.push_back(UndefValue::get(Builder.getInt32Ty()));
1027       else
1028         MaskValues.push_back(Builder.getInt32(Mask[i]));
1029     }
1030     return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()),
1031                                           ConstantVector::get(MaskValues));
1032   }
1033
1034   Instruction *I = cast<Instruction>(V);
1035   switch (I->getOpcode()) {
1036     case Instruction::Add:
1037     case Instruction::FAdd:
1038     case Instruction::Sub:
1039     case Instruction::FSub:
1040     case Instruction::Mul:
1041     case Instruction::FMul:
1042     case Instruction::UDiv:
1043     case Instruction::SDiv:
1044     case Instruction::FDiv:
1045     case Instruction::URem:
1046     case Instruction::SRem:
1047     case Instruction::FRem:
1048     case Instruction::Shl:
1049     case Instruction::LShr:
1050     case Instruction::AShr:
1051     case Instruction::And:
1052     case Instruction::Or:
1053     case Instruction::Xor:
1054     case Instruction::ICmp:
1055     case Instruction::FCmp:
1056     case Instruction::Trunc:
1057     case Instruction::ZExt:
1058     case Instruction::SExt:
1059     case Instruction::FPToUI:
1060     case Instruction::FPToSI:
1061     case Instruction::UIToFP:
1062     case Instruction::SIToFP:
1063     case Instruction::FPTrunc:
1064     case Instruction::FPExt:
1065     case Instruction::Select:
1066     case Instruction::GetElementPtr: {
1067       SmallVector<Value*, 8> NewOps;
1068       bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements());
1069       for (int i = 0, e = I->getNumOperands(); i != e; ++i) {
1070         Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask);
1071         NewOps.push_back(V);
1072         NeedsRebuild |= (V != I->getOperand(i));
1073       }
1074       if (NeedsRebuild) {
1075         return buildNew(I, NewOps);
1076       }
1077       return I;
1078     }
1079     case Instruction::InsertElement: {
1080       int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue();
1081
1082       // The insertelement was inserting at Element. Figure out which element
1083       // that becomes after shuffling. The answer is guaranteed to be unique
1084       // by CanEvaluateShuffled.
1085       bool Found = false;
1086       int Index = 0;
1087       for (int e = Mask.size(); Index != e; ++Index) {
1088         if (Mask[Index] == Element) {
1089           Found = true;
1090           break;
1091         }
1092       }
1093
1094       // If element is not in Mask, no need to handle the operand 1 (element to
1095       // be inserted). Just evaluate values in operand 0 according to Mask.
1096       if (!Found)
1097         return EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1098
1099       Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask);
1100       return InsertElementInst::Create(V, I->getOperand(1),
1101                                        Builder.getInt32(Index), "", I);
1102     }
1103   }
1104   llvm_unreachable("failed to reorder elements of vector instruction!");
1105 }
1106
1107 static void recognizeIdentityMask(const SmallVectorImpl<int> &Mask,
1108                                   bool &isLHSID, bool &isRHSID) {
1109   isLHSID = isRHSID = true;
1110
1111   for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
1112     if (Mask[i] < 0) continue;  // Ignore undef values.
1113     // Is this an identity shuffle of the LHS value?
1114     isLHSID &= (Mask[i] == (int)i);
1115
1116     // Is this an identity shuffle of the RHS value?
1117     isRHSID &= (Mask[i]-e == i);
1118   }
1119 }
1120
1121 // Returns true if the shuffle is extracting a contiguous range of values from
1122 // LHS, for example:
1123 //                 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1124 //   Input:        |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP|
1125 //   Shuffles to:  |EE|FF|GG|HH|
1126 //                 +--+--+--+--+
1127 static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI,
1128                                        SmallVector<int, 16> &Mask) {
1129   unsigned LHSElems = SVI.getOperand(0)->getType()->getVectorNumElements();
1130   unsigned MaskElems = Mask.size();
1131   unsigned BegIdx = Mask.front();
1132   unsigned EndIdx = Mask.back();
1133   if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1)
1134     return false;
1135   for (unsigned I = 0; I != MaskElems; ++I)
1136     if (static_cast<unsigned>(Mask[I]) != BegIdx + I)
1137       return false;
1138   return true;
1139 }
1140
1141 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
1142   Value *LHS = SVI.getOperand(0);
1143   Value *RHS = SVI.getOperand(1);
1144   SmallVector<int, 16> Mask = SVI.getShuffleMask();
1145   Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
1146
1147   if (auto *V = SimplifyShuffleVectorInst(
1148           LHS, RHS, SVI.getMask(), SVI.getType(), SQ.getWithInstruction(&SVI)))
1149     return replaceInstUsesWith(SVI, V);
1150
1151   bool MadeChange = false;
1152   unsigned VWidth = SVI.getType()->getVectorNumElements();
1153
1154   APInt UndefElts(VWidth, 0);
1155   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
1156   if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
1157     if (V != &SVI)
1158       return replaceInstUsesWith(SVI, V);
1159     return &SVI;
1160   }
1161
1162   unsigned LHSWidth = LHS->getType()->getVectorNumElements();
1163
1164   // Canonicalize shuffle(x    ,x,mask) -> shuffle(x, undef,mask')
1165   // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
1166   if (LHS == RHS || isa<UndefValue>(LHS)) {
1167     if (isa<UndefValue>(LHS) && LHS == RHS) {
1168       // shuffle(undef,undef,mask) -> undef.
1169       Value *Result = (VWidth == LHSWidth)
1170                       ? LHS : UndefValue::get(SVI.getType());
1171       return replaceInstUsesWith(SVI, Result);
1172     }
1173
1174     // Remap any references to RHS to use LHS.
1175     SmallVector<Constant*, 16> Elts;
1176     for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
1177       if (Mask[i] < 0) {
1178         Elts.push_back(UndefValue::get(Int32Ty));
1179         continue;
1180       }
1181
1182       if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
1183           (Mask[i] <  (int)e && isa<UndefValue>(LHS))) {
1184         Mask[i] = -1;     // Turn into undef.
1185         Elts.push_back(UndefValue::get(Int32Ty));
1186       } else {
1187         Mask[i] = Mask[i] % e;  // Force to LHS.
1188         Elts.push_back(ConstantInt::get(Int32Ty, Mask[i]));
1189       }
1190     }
1191     SVI.setOperand(0, SVI.getOperand(1));
1192     SVI.setOperand(1, UndefValue::get(RHS->getType()));
1193     SVI.setOperand(2, ConstantVector::get(Elts));
1194     LHS = SVI.getOperand(0);
1195     RHS = SVI.getOperand(1);
1196     MadeChange = true;
1197   }
1198
1199   if (VWidth == LHSWidth) {
1200     // Analyze the shuffle, are the LHS or RHS and identity shuffles?
1201     bool isLHSID, isRHSID;
1202     recognizeIdentityMask(Mask, isLHSID, isRHSID);
1203
1204     // Eliminate identity shuffles.
1205     if (isLHSID) return replaceInstUsesWith(SVI, LHS);
1206     if (isRHSID) return replaceInstUsesWith(SVI, RHS);
1207   }
1208
1209   if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) {
1210     Value *V = EvaluateInDifferentElementOrder(LHS, Mask);
1211     return replaceInstUsesWith(SVI, V);
1212   }
1213
1214   // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to
1215   // a non-vector type. We can instead bitcast the original vector followed by
1216   // an extract of the desired element:
1217   //
1218   //   %sroa = shufflevector <16 x i8> %in, <16 x i8> undef,
1219   //                         <4 x i32> <i32 0, i32 1, i32 2, i32 3>
1220   //   %1 = bitcast <4 x i8> %sroa to i32
1221   // Becomes:
1222   //   %bc = bitcast <16 x i8> %in to <4 x i32>
1223   //   %ext = extractelement <4 x i32> %bc, i32 0
1224   //
1225   // If the shuffle is extracting a contiguous range of values from the input
1226   // vector then each use which is a bitcast of the extracted size can be
1227   // replaced. This will work if the vector types are compatible, and the begin
1228   // index is aligned to a value in the casted vector type. If the begin index
1229   // isn't aligned then we can shuffle the original vector (keeping the same
1230   // vector type) before extracting.
1231   //
1232   // This code will bail out if the target type is fundamentally incompatible
1233   // with vectors of the source type.
1234   //
1235   // Example of <16 x i8>, target type i32:
1236   // Index range [4,8):         v-----------v Will work.
1237   //                +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
1238   //     <16 x i8>: |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
1239   //     <4 x i32>: |           |           |           |           |
1240   //                +-----------+-----------+-----------+-----------+
1241   // Index range [6,10):              ^-----------^ Needs an extra shuffle.
1242   // Target type i40:           ^--------------^ Won't work, bail.
1243   if (isShuffleExtractingFromLHS(SVI, Mask)) {
1244     Value *V = LHS;
1245     unsigned MaskElems = Mask.size();
1246     VectorType *SrcTy = cast<VectorType>(V->getType());
1247     unsigned VecBitWidth = SrcTy->getBitWidth();
1248     unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType());
1249     assert(SrcElemBitWidth && "vector elements must have a bitwidth");
1250     unsigned SrcNumElems = SrcTy->getNumElements();
1251     SmallVector<BitCastInst *, 8> BCs;
1252     DenseMap<Type *, Value *> NewBCs;
1253     for (User *U : SVI.users())
1254       if (BitCastInst *BC = dyn_cast<BitCastInst>(U))
1255         if (!BC->use_empty())
1256           // Only visit bitcasts that weren't previously handled.
1257           BCs.push_back(BC);
1258     for (BitCastInst *BC : BCs) {
1259       unsigned BegIdx = Mask.front();
1260       Type *TgtTy = BC->getDestTy();
1261       unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy);
1262       if (!TgtElemBitWidth)
1263         continue;
1264       unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth;
1265       bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth;
1266       bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth);
1267       if (!VecBitWidthsEqual)
1268         continue;
1269       if (!VectorType::isValidElementType(TgtTy))
1270         continue;
1271       VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems);
1272       if (!BegIsAligned) {
1273         // Shuffle the input so [0,NumElements) contains the output, and
1274         // [NumElems,SrcNumElems) is undef.
1275         SmallVector<Constant *, 16> ShuffleMask(SrcNumElems,
1276                                                 UndefValue::get(Int32Ty));
1277         for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I)
1278           ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx);
1279         V = Builder.CreateShuffleVector(V, UndefValue::get(V->getType()),
1280                                         ConstantVector::get(ShuffleMask),
1281                                         SVI.getName() + ".extract");
1282         BegIdx = 0;
1283       }
1284       unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth;
1285       assert(SrcElemsPerTgtElem);
1286       BegIdx /= SrcElemsPerTgtElem;
1287       bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end();
1288       auto *NewBC =
1289           BCAlreadyExists
1290               ? NewBCs[CastSrcTy]
1291               : Builder.CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc");
1292       if (!BCAlreadyExists)
1293         NewBCs[CastSrcTy] = NewBC;
1294       auto *Ext = Builder.CreateExtractElement(
1295           NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract");
1296       // The shufflevector isn't being replaced: the bitcast that used it
1297       // is. InstCombine will visit the newly-created instructions.
1298       replaceInstUsesWith(*BC, Ext);
1299       MadeChange = true;
1300     }
1301   }
1302
1303   // If the LHS is a shufflevector itself, see if we can combine it with this
1304   // one without producing an unusual shuffle.
1305   // Cases that might be simplified:
1306   // 1.
1307   // x1=shuffle(v1,v2,mask1)
1308   //  x=shuffle(x1,undef,mask)
1309   //        ==>
1310   //  x=shuffle(v1,undef,newMask)
1311   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
1312   // 2.
1313   // x1=shuffle(v1,undef,mask1)
1314   //  x=shuffle(x1,x2,mask)
1315   // where v1.size() == mask1.size()
1316   //        ==>
1317   //  x=shuffle(v1,x2,newMask)
1318   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
1319   // 3.
1320   // x2=shuffle(v2,undef,mask2)
1321   //  x=shuffle(x1,x2,mask)
1322   // where v2.size() == mask2.size()
1323   //        ==>
1324   //  x=shuffle(x1,v2,newMask)
1325   // newMask[i] = (mask[i] < x1.size())
1326   //              ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
1327   // 4.
1328   // x1=shuffle(v1,undef,mask1)
1329   // x2=shuffle(v2,undef,mask2)
1330   //  x=shuffle(x1,x2,mask)
1331   // where v1.size() == v2.size()
1332   //        ==>
1333   //  x=shuffle(v1,v2,newMask)
1334   // newMask[i] = (mask[i] < x1.size())
1335   //              ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
1336   //
1337   // Here we are really conservative:
1338   // we are absolutely afraid of producing a shuffle mask not in the input
1339   // program, because the code gen may not be smart enough to turn a merged
1340   // shuffle into two specific shuffles: it may produce worse code.  As such,
1341   // we only merge two shuffles if the result is either a splat or one of the
1342   // input shuffle masks.  In this case, merging the shuffles just removes
1343   // one instruction, which we know is safe.  This is good for things like
1344   // turning: (splat(splat)) -> splat, or
1345   // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
1346   ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
1347   ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
1348   if (LHSShuffle)
1349     if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
1350       LHSShuffle = nullptr;
1351   if (RHSShuffle)
1352     if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
1353       RHSShuffle = nullptr;
1354   if (!LHSShuffle && !RHSShuffle)
1355     return MadeChange ? &SVI : nullptr;
1356
1357   Value* LHSOp0 = nullptr;
1358   Value* LHSOp1 = nullptr;
1359   Value* RHSOp0 = nullptr;
1360   unsigned LHSOp0Width = 0;
1361   unsigned RHSOp0Width = 0;
1362   if (LHSShuffle) {
1363     LHSOp0 = LHSShuffle->getOperand(0);
1364     LHSOp1 = LHSShuffle->getOperand(1);
1365     LHSOp0Width = LHSOp0->getType()->getVectorNumElements();
1366   }
1367   if (RHSShuffle) {
1368     RHSOp0 = RHSShuffle->getOperand(0);
1369     RHSOp0Width = RHSOp0->getType()->getVectorNumElements();
1370   }
1371   Value* newLHS = LHS;
1372   Value* newRHS = RHS;
1373   if (LHSShuffle) {
1374     // case 1
1375     if (isa<UndefValue>(RHS)) {
1376       newLHS = LHSOp0;
1377       newRHS = LHSOp1;
1378     }
1379     // case 2 or 4
1380     else if (LHSOp0Width == LHSWidth) {
1381       newLHS = LHSOp0;
1382     }
1383   }
1384   // case 3 or 4
1385   if (RHSShuffle && RHSOp0Width == LHSWidth) {
1386     newRHS = RHSOp0;
1387   }
1388   // case 4
1389   if (LHSOp0 == RHSOp0) {
1390     newLHS = LHSOp0;
1391     newRHS = nullptr;
1392   }
1393
1394   if (newLHS == LHS && newRHS == RHS)
1395     return MadeChange ? &SVI : nullptr;
1396
1397   SmallVector<int, 16> LHSMask;
1398   SmallVector<int, 16> RHSMask;
1399   if (newLHS != LHS)
1400     LHSMask = LHSShuffle->getShuffleMask();
1401   if (RHSShuffle && newRHS != RHS)
1402     RHSMask = RHSShuffle->getShuffleMask();
1403
1404   unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
1405   SmallVector<int, 16> newMask;
1406   bool isSplat = true;
1407   int SplatElt = -1;
1408   // Create a new mask for the new ShuffleVectorInst so that the new
1409   // ShuffleVectorInst is equivalent to the original one.
1410   for (unsigned i = 0; i < VWidth; ++i) {
1411     int eltMask;
1412     if (Mask[i] < 0) {
1413       // This element is an undef value.
1414       eltMask = -1;
1415     } else if (Mask[i] < (int)LHSWidth) {
1416       // This element is from left hand side vector operand.
1417       //
1418       // If LHS is going to be replaced (case 1, 2, or 4), calculate the
1419       // new mask value for the element.
1420       if (newLHS != LHS) {
1421         eltMask = LHSMask[Mask[i]];
1422         // If the value selected is an undef value, explicitly specify it
1423         // with a -1 mask value.
1424         if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
1425           eltMask = -1;
1426       } else
1427         eltMask = Mask[i];
1428     } else {
1429       // This element is from right hand side vector operand
1430       //
1431       // If the value selected is an undef value, explicitly specify it
1432       // with a -1 mask value. (case 1)
1433       if (isa<UndefValue>(RHS))
1434         eltMask = -1;
1435       // If RHS is going to be replaced (case 3 or 4), calculate the
1436       // new mask value for the element.
1437       else if (newRHS != RHS) {
1438         eltMask = RHSMask[Mask[i]-LHSWidth];
1439         // If the value selected is an undef value, explicitly specify it
1440         // with a -1 mask value.
1441         if (eltMask >= (int)RHSOp0Width) {
1442           assert(isa<UndefValue>(RHSShuffle->getOperand(1))
1443                  && "should have been check above");
1444           eltMask = -1;
1445         }
1446       } else
1447         eltMask = Mask[i]-LHSWidth;
1448
1449       // If LHS's width is changed, shift the mask value accordingly.
1450       // If newRHS == nullptr, i.e. LHSOp0 == RHSOp0, we want to remap any
1451       // references from RHSOp0 to LHSOp0, so we don't need to shift the mask.
1452       // If newRHS == newLHS, we want to remap any references from newRHS to
1453       // newLHS so that we can properly identify splats that may occur due to
1454       // obfuscation across the two vectors.
1455       if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS)
1456         eltMask += newLHSWidth;
1457     }
1458
1459     // Check if this could still be a splat.
1460     if (eltMask >= 0) {
1461       if (SplatElt >= 0 && SplatElt != eltMask)
1462         isSplat = false;
1463       SplatElt = eltMask;
1464     }
1465
1466     newMask.push_back(eltMask);
1467   }
1468
1469   // If the result mask is equal to one of the original shuffle masks,
1470   // or is a splat, do the replacement.
1471   if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
1472     SmallVector<Constant*, 16> Elts;
1473     for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
1474       if (newMask[i] < 0) {
1475         Elts.push_back(UndefValue::get(Int32Ty));
1476       } else {
1477         Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
1478       }
1479     }
1480     if (!newRHS)
1481       newRHS = UndefValue::get(newLHS->getType());
1482     return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
1483   }
1484
1485   // If the result mask is an identity, replace uses of this instruction with
1486   // corresponding argument.
1487   bool isLHSID, isRHSID;
1488   recognizeIdentityMask(newMask, isLHSID, isRHSID);
1489   if (isLHSID && VWidth == LHSOp0Width) return replaceInstUsesWith(SVI, newLHS);
1490   if (isRHSID && VWidth == RHSOp0Width) return replaceInstUsesWith(SVI, newRHS);
1491
1492   return MadeChange ? &SVI : nullptr;
1493 }