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 "InstCombine.h"
  16 using namespace llvm;
  17
  18 /// CheapToScalarize - Return true if the value is cheaper to scalarize than it
  19 /// is to leave as a vector operation.  isConstant indicates whether we're
  20 /// extracting one known element.  If false we're extracting a variable index.
  21 static bool CheapToScalarize(Value *V, bool isConstant) {
  22   if (isa<ConstantAggregateZero>(V))
  23     return true;
  24   if (ConstantVector *C = dyn_cast<ConstantVector>(V)) {
  25     if (isConstant) return true;
  26     // If all elts are the same, we can extract.
  27     Constant *Op0 = C->getOperand(0);
  28     for (unsigned i = 1; i < C->getNumOperands(); ++i)
  29       if (C->getOperand(i) != Op0)
  30         return false;
  31     return true;
  32   }
  33   Instruction *I = dyn_cast<Instruction>(V);
  34   if (!I) return false;
  35
  36   // Insert element gets simplified to the inserted element or is deleted if
  37   // this is constant idx extract element and its a constant idx insertelt.
  38   if (I->getOpcode() == Instruction::InsertElement && isConstant &&
  39       isa<ConstantInt>(I->getOperand(2)))
  40     return true;
  41   if (I->getOpcode() == Instruction::Load && I->hasOneUse())
  42     return true;
  43   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I))
  44     if (BO->hasOneUse() &&
  45         (CheapToScalarize(BO->getOperand(0), isConstant) ||
  46          CheapToScalarize(BO->getOperand(1), isConstant)))
  47       return true;
  48   if (CmpInst *CI = dyn_cast<CmpInst>(I))
  49     if (CI->hasOneUse() &&
  50         (CheapToScalarize(CI->getOperand(0), isConstant) ||
  51          CheapToScalarize(CI->getOperand(1), isConstant)))
  52       return true;
  53
  54   return false;
  55 }
  56
  57 /// getShuffleMask - Read and decode a shufflevector mask.
  58 /// Turn undef elements into negative values.
  59 static SmallVector<int, 16> getShuffleMask(const ShuffleVectorInst *SVI) {
  60   unsigned NElts = SVI->getType()->getNumElements();
  61   if (isa<ConstantAggregateZero>(SVI->getOperand(2)))
  62     return SmallVector<int, 16>(NElts, 0);
  63   if (isa<UndefValue>(SVI->getOperand(2)))
  64     return SmallVector<int, 16>(NElts, -1);
  65
  66   SmallVector<int, 16> Result;
  67   const ConstantVector *CP = cast<ConstantVector>(SVI->getOperand(2));
  68   for (User::const_op_iterator i = CP->op_begin(), e = CP->op_end(); i!=e; ++i)
  69     if (isa<UndefValue>(*i))
  70       Result.push_back(-1);  // undef
  71     else
  72       Result.push_back(cast<ConstantInt>(*i)->getZExtValue());
  73   return Result;
  74 }
  75
  76 /// FindScalarElement - Given a vector and an element number, see if the scalar
  77 /// value is already around as a register, for example if it were inserted then
  78 /// extracted from the vector.
  79 static Value *FindScalarElement(Value *V, unsigned EltNo) {
  80   assert(V->getType()->isVectorTy() && "Not looking at a vector?");
  81   VectorType *PTy = cast<VectorType>(V->getType());
  82   unsigned Width = PTy->getNumElements();
  83   if (EltNo >= Width)  // Out of range access.
  84     return UndefValue::get(PTy->getElementType());
  85
  86   if (isa<UndefValue>(V))
  87     return UndefValue::get(PTy->getElementType());
  88   if (isa<ConstantAggregateZero>(V))
  89     return Constant::getNullValue(PTy->getElementType());
  90   if (ConstantVector *CP = dyn_cast<ConstantVector>(V))
  91     return CP->getOperand(EltNo);
  92
  93   if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
  94     // If this is an insert to a variable element, we don't know what it is.
  95     if (!isa<ConstantInt>(III->getOperand(2)))
  96       return 0;
  97     unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
  98
  99     // If this is an insert to the element we are looking for, return the
 100     // inserted value.
 101     if (EltNo == IIElt)
 102       return III->getOperand(1);
 103
 104     // Otherwise, the insertelement doesn't modify the value, recurse on its
 105     // vector input.
 106     return FindScalarElement(III->getOperand(0), EltNo);
 107   }
 108
 109   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
 110     unsigned LHSWidth =
 111       cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
 112     int InEl = SVI->getMaskValue(EltNo);
 113     if (InEl < 0)
 114       return UndefValue::get(PTy->getElementType());
 115     if (InEl < (int)LHSWidth)
 116       return FindScalarElement(SVI->getOperand(0), InEl);
 117     return FindScalarElement(SVI->getOperand(1), InEl - LHSWidth);
 118   }
 119
 120   // Otherwise, we don't know.
 121   return 0;
 122 }
 123
 124 Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) {
 125   // If vector val is undef, replace extract with scalar undef.
 126   if (isa<UndefValue>(EI.getOperand(0)))
 127     return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 128
 129   // If vector val is constant 0, replace extract with scalar 0.
 130   if (isa<ConstantAggregateZero>(EI.getOperand(0)))
 131     return ReplaceInstUsesWith(EI, Constant::getNullValue(EI.getType()));
 132
 133   if (ConstantVector *C = dyn_cast<ConstantVector>(EI.getOperand(0))) {
 134     // If vector val is constant with all elements the same, replace EI with
 135     // that element. When the elements are not identical, we cannot replace yet
 136     // (we do that below, but only when the index is constant).
 137     Constant *op0 = C->getOperand(0);
 138     for (unsigned i = 1; i != C->getNumOperands(); ++i)
 139       if (C->getOperand(i) != op0) {
 140         op0 = 0;
 141         break;
 142       }
 143     if (op0)
 144       return ReplaceInstUsesWith(EI, op0);
 145   }
 146
 147   // If extracting a specified index from the vector, see if we can recursively
 148   // find a previously computed scalar that was inserted into the vector.
 149   if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 150     unsigned IndexVal = IdxC->getZExtValue();
 151     unsigned VectorWidth = EI.getVectorOperandType()->getNumElements();
 152
 153     // If this is extracting an invalid index, turn this into undef, to avoid
 154     // crashing the code below.
 155     if (IndexVal >= VectorWidth)
 156       return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 157
 158     // This instruction only demands the single element from the input vector.
 159     // If the input vector has a single use, simplify it based on this use
 160     // property.
 161     if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) {
 162       APInt UndefElts(VectorWidth, 0);
 163       APInt DemandedMask(VectorWidth, 0);
 164       DemandedMask.setBit(IndexVal);
 165       if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0),
 166                                                 DemandedMask, UndefElts)) {
 167         EI.setOperand(0, V);
 168         return &EI;
 169       }
 170     }
 171
 172     if (Value *Elt = FindScalarElement(EI.getOperand(0), IndexVal))
 173       return ReplaceInstUsesWith(EI, Elt);
 174
 175     // If the this extractelement is directly using a bitcast from a vector of
 176     // the same number of elements, see if we can find the source element from
 177     // it.  In this case, we will end up needing to bitcast the scalars.
 178     if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) {
 179       if (VectorType *VT =
 180           dyn_cast<VectorType>(BCI->getOperand(0)->getType()))
 181         if (VT->getNumElements() == VectorWidth)
 182           if (Value *Elt = FindScalarElement(BCI->getOperand(0), IndexVal))
 183             return new BitCastInst(Elt, EI.getType());
 184     }
 185   }
 186
 187   if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) {
 188     // Push extractelement into predecessor operation if legal and
 189     // profitable to do so
 190     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) {
 191       if (I->hasOneUse() &&
 192           CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) {
 193         Value *newEI0 =
 194           Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1),
 195                                         EI.getName()+".lhs");
 196         Value *newEI1 =
 197           Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1),
 198                                         EI.getName()+".rhs");
 199         return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1);
 200       }
 201     } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) {
 202       // Extracting the inserted element?
 203       if (IE->getOperand(2) == EI.getOperand(1))
 204         return ReplaceInstUsesWith(EI, IE->getOperand(1));
 205       // If the inserted and extracted elements are constants, they must not
 206       // be the same value, extract from the pre-inserted value instead.
 207       if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) {
 208         Worklist.AddValue(EI.getOperand(0));
 209         EI.setOperand(0, IE->getOperand(0));
 210         return &EI;
 211       }
 212     } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) {
 213       // If this is extracting an element from a shufflevector, figure out where
 214       // it came from and extract from the appropriate input element instead.
 215       if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) {
 216         int SrcIdx = SVI->getMaskValue(Elt->getZExtValue());
 217         Value *Src;
 218         unsigned LHSWidth =
 219           cast<VectorType>(SVI->getOperand(0)->getType())->getNumElements();
 220
 221         if (SrcIdx < 0)
 222           return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType()));
 223         if (SrcIdx < (int)LHSWidth)
 224           Src = SVI->getOperand(0);
 225         else {
 226           SrcIdx -= LHSWidth;
 227           Src = SVI->getOperand(1);
 228         }
 229         Type *Int32Ty = Type::getInt32Ty(EI.getContext());
 230         return ExtractElementInst::Create(Src,
 231                                           ConstantInt::get(Int32Ty,
 232                                                            SrcIdx, false));
 233       }
 234     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 235       // Canonicalize extractelement(cast) -> cast(extractelement)
 236       // bitcasts can change the number of vector elements and they cost nothing
 237       if (CI->hasOneUse() && EI.hasOneUse() &&
 238           (CI->getOpcode() != Instruction::BitCast)) {
 239         Value *EE = Builder->CreateExtractElement(CI->getOperand(0),
 240                                                   EI.getIndexOperand());
 241         return CastInst::Create(CI->getOpcode(), EE, EI.getType());
 242       }
 243     }
 244   }
 245   return 0;
 246 }
 247
 248 /// CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns
 249 /// elements from either LHS or RHS, return the shuffle mask and true.
 250 /// Otherwise, return false.
 251 static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS,
 252                                          std::vector<Constant*> &Mask) {
 253   assert(V->getType() == LHS->getType() && V->getType() == RHS->getType() &&
 254          "Invalid CollectSingleShuffleElements");
 255   unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 256
 257   if (isa<UndefValue>(V)) {
 258     Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 259     return true;
 260   }
 261
 262   if (V == LHS) {
 263     for (unsigned i = 0; i != NumElts; ++i)
 264       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 265     return true;
 266   }
 267
 268   if (V == RHS) {
 269     for (unsigned i = 0; i != NumElts; ++i)
 270       Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()),
 271                                       i+NumElts));
 272     return true;
 273   }
 274
 275   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 276     // If this is an insert of an extract from some other vector, include it.
 277     Value *VecOp    = IEI->getOperand(0);
 278     Value *ScalarOp = IEI->getOperand(1);
 279     Value *IdxOp    = IEI->getOperand(2);
 280
 281     if (!isa<ConstantInt>(IdxOp))
 282       return false;
 283     unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 284
 285     if (isa<UndefValue>(ScalarOp)) {  // inserting undef into vector.
 286       // Okay, we can handle this if the vector we are insertinting into is
 287       // transitively ok.
 288       if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 289         // If so, update the mask to reflect the inserted undef.
 290         Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext()));
 291         return true;
 292       }
 293     } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){
 294       if (isa<ConstantInt>(EI->getOperand(1)) &&
 295           EI->getOperand(0)->getType() == V->getType()) {
 296         unsigned ExtractedIdx =
 297         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 298
 299         // This must be extracting from either LHS or RHS.
 300         if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) {
 301           // Okay, we can handle this if the vector we are insertinting into is
 302           // transitively ok.
 303           if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) {
 304             // If so, update the mask to reflect the inserted value.
 305             if (EI->getOperand(0) == LHS) {
 306               Mask[InsertedIdx % NumElts] =
 307               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 308                                ExtractedIdx);
 309             } else {
 310               assert(EI->getOperand(0) == RHS);
 311               Mask[InsertedIdx % NumElts] =
 312               ConstantInt::get(Type::getInt32Ty(V->getContext()),
 313                                ExtractedIdx+NumElts);
 314             }
 315             return true;
 316           }
 317         }
 318       }
 319     }
 320   }
 321   // TODO: Handle shufflevector here!
 322
 323   return false;
 324 }
 325
 326 /// CollectShuffleElements - We are building a shuffle of V, using RHS as the
 327 /// RHS of the shuffle instruction, if it is not null.  Return a shuffle mask
 328 /// that computes V and the LHS value of the shuffle.
 329 static Value *CollectShuffleElements(Value *V, std::vector<Constant*> &Mask,
 330                                      Value *&RHS) {
 331   assert(V->getType()->isVectorTy() &&
 332          (RHS == 0 || V->getType() == RHS->getType()) &&
 333          "Invalid shuffle!");
 334   unsigned NumElts = cast<VectorType>(V->getType())->getNumElements();
 335
 336   if (isa<UndefValue>(V)) {
 337     Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext())));
 338     return V;
 339   }
 340
 341   if (isa<ConstantAggregateZero>(V)) {
 342     Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0));
 343     return V;
 344   }
 345
 346   if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) {
 347     // If this is an insert of an extract from some other vector, include it.
 348     Value *VecOp    = IEI->getOperand(0);
 349     Value *ScalarOp = IEI->getOperand(1);
 350     Value *IdxOp    = IEI->getOperand(2);
 351
 352     if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 353       if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
 354           EI->getOperand(0)->getType() == V->getType()) {
 355         unsigned ExtractedIdx =
 356           cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 357         unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 358
 359         // Either the extracted from or inserted into vector must be RHSVec,
 360         // otherwise we'd end up with a shuffle of three inputs.
 361         if (EI->getOperand(0) == RHS || RHS == 0) {
 362           RHS = EI->getOperand(0);
 363           Value *V = CollectShuffleElements(VecOp, Mask, RHS);
 364           Mask[InsertedIdx % NumElts] =
 365             ConstantInt::get(Type::getInt32Ty(V->getContext()),
 366                              NumElts+ExtractedIdx);
 367           return V;
 368         }
 369
 370         if (VecOp == RHS) {
 371           Value *V = CollectShuffleElements(EI->getOperand(0), Mask, RHS);
 372           // Everything but the extracted element is replaced with the RHS.
 373           for (unsigned i = 0; i != NumElts; ++i) {
 374             if (i != InsertedIdx)
 375               Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()),
 376                                          NumElts+i);
 377           }
 378           return V;
 379         }
 380
 381         // If this insertelement is a chain that comes from exactly these two
 382         // vectors, return the vector and the effective shuffle.
 383         if (CollectSingleShuffleElements(IEI, EI->getOperand(0), RHS, Mask))
 384           return EI->getOperand(0);
 385       }
 386     }
 387   }
 388   // TODO: Handle shufflevector here!
 389
 390   // Otherwise, can't do anything fancy.  Return an identity vector.
 391   for (unsigned i = 0; i != NumElts; ++i)
 392     Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i));
 393   return V;
 394 }
 395
 396 Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) {
 397   Value *VecOp    = IE.getOperand(0);
 398   Value *ScalarOp = IE.getOperand(1);
 399   Value *IdxOp    = IE.getOperand(2);
 400
 401   // Inserting an undef or into an undefined place, remove this.
 402   if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp))
 403     ReplaceInstUsesWith(IE, VecOp);
 404
 405   // If the inserted element was extracted from some other vector, and if the
 406   // indexes are constant, try to turn this into a shufflevector operation.
 407   if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) {
 408     if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp) &&
 409         EI->getOperand(0)->getType() == IE.getType()) {
 410       unsigned NumVectorElts = IE.getType()->getNumElements();
 411       unsigned ExtractedIdx =
 412         cast<ConstantInt>(EI->getOperand(1))->getZExtValue();
 413       unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue();
 414
 415       if (ExtractedIdx >= NumVectorElts) // Out of range extract.
 416         return ReplaceInstUsesWith(IE, VecOp);
 417
 418       if (InsertedIdx >= NumVectorElts)  // Out of range insert.
 419         return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType()));
 420
 421       // If we are extracting a value from a vector, then inserting it right
 422       // back into the same place, just use the input vector.
 423       if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx)
 424         return ReplaceInstUsesWith(IE, VecOp);
 425
 426       // If this insertelement isn't used by some other insertelement, turn it
 427       // (and any insertelements it points to), into one big shuffle.
 428       if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.use_back())) {
 429         std::vector<Constant*> Mask;
 430         Value *RHS = 0;
 431         Value *LHS = CollectShuffleElements(&IE, Mask, RHS);
 432         if (RHS == 0) RHS = UndefValue::get(LHS->getType());
 433         // We now have a shuffle of LHS, RHS, Mask.
 434         return new ShuffleVectorInst(LHS, RHS, ConstantVector::get(Mask));
 435       }
 436     }
 437   }
 438
 439   unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements();
 440   APInt UndefElts(VWidth, 0);
 441   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 442   if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) {
 443     if (V != &IE)
 444       return ReplaceInstUsesWith(IE, V);
 445     return &IE;
 446   }
 447
 448   return 0;
 449 }
 450
 451
 452 Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) {
 453   Value *LHS = SVI.getOperand(0);
 454   Value *RHS = SVI.getOperand(1);
 455   SmallVector<int, 16> Mask = getShuffleMask(&SVI);
 456
 457   bool MadeChange = false;
 458
 459   // Undefined shuffle mask -> undefined value.
 460   if (isa<UndefValue>(SVI.getOperand(2)))
 461     return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType()));
 462
 463   unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements();
 464
 465   APInt UndefElts(VWidth, 0);
 466   APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth));
 467   if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) {
 468     if (V != &SVI)
 469       return ReplaceInstUsesWith(SVI, V);
 470     LHS = SVI.getOperand(0);
 471     RHS = SVI.getOperand(1);
 472     MadeChange = true;
 473   }
 474
 475   unsigned LHSWidth = cast<VectorType>(LHS->getType())->getNumElements();
 476
 477   // Canonicalize shuffle(x    ,x,mask) -> shuffle(x, undef,mask')
 478   // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask').
 479   if (LHS == RHS || isa<UndefValue>(LHS)) {
 480     if (isa<UndefValue>(LHS) && LHS == RHS) {
 481       // shuffle(undef,undef,mask) -> undef.
 482       Value* result = (VWidth == LHSWidth)
 483                       ? LHS : UndefValue::get(SVI.getType());
 484       return ReplaceInstUsesWith(SVI, result);
 485     }
 486
 487     // Remap any references to RHS to use LHS.
 488     std::vector<Constant*> Elts;
 489     for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) {
 490       if (Mask[i] < 0)
 491         Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
 492       else {
 493         if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) ||
 494             (Mask[i] <  (int)e && isa<UndefValue>(LHS))) {
 495           Mask[i] = -1;     // Turn into undef.
 496           Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext())));
 497         } else {
 498           Mask[i] = Mask[i] % e;  // Force to LHS.
 499           Elts.push_back(ConstantInt::get(Type::getInt32Ty(SVI.getContext()),
 500                                           Mask[i]));
 501         }
 502       }
 503     }
 504     SVI.setOperand(0, SVI.getOperand(1));
 505     SVI.setOperand(1, UndefValue::get(RHS->getType()));
 506     SVI.setOperand(2, ConstantVector::get(Elts));
 507     LHS = SVI.getOperand(0);
 508     RHS = SVI.getOperand(1);
 509     MadeChange = true;
 510   }
 511
 512   if (VWidth == LHSWidth) {
 513     // Analyze the shuffle, are the LHS or RHS and identity shuffles?
 514     bool isLHSID = true, isRHSID = true;
 515
 516     for (unsigned i = 0, e = Mask.size(); i != e; ++i) {
 517       if (Mask[i] < 0) continue;  // Ignore undef values.
 518       // Is this an identity shuffle of the LHS value?
 519       isLHSID &= (Mask[i] == (int)i);
 520
 521       // Is this an identity shuffle of the RHS value?
 522       isRHSID &= (Mask[i]-e == i);
 523     }
 524
 525     // Eliminate identity shuffles.
 526     if (isLHSID) return ReplaceInstUsesWith(SVI, LHS);
 527     if (isRHSID) return ReplaceInstUsesWith(SVI, RHS);
 528   }
 529
 530   // If the LHS is a shufflevector itself, see if we can combine it with this
 531   // one without producing an unusual shuffle.
 532   // Cases that might be simplified:
 533   // 1.
 534   // x1=shuffle(v1,v2,mask1)
 535   //  x=shuffle(x1,undef,mask)
 536   //        ==>
 537   //  x=shuffle(v1,undef,newMask)
 538   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1
 539   // 2.
 540   // x1=shuffle(v1,undef,mask1)
 541   //  x=shuffle(x1,x2,mask)
 542   // where v1.size() == mask1.size()
 543   //        ==>
 544   //  x=shuffle(v1,x2,newMask)
 545   // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i]
 546   // 3.
 547   // x2=shuffle(v2,undef,mask2)
 548   //  x=shuffle(x1,x2,mask)
 549   // where v2.size() == mask2.size()
 550   //        ==>
 551   //  x=shuffle(x1,v2,newMask)
 552   // newMask[i] = (mask[i] < x1.size())
 553   //              ? mask[i] : mask2[mask[i]-x1.size()]+x1.size()
 554   // 4.
 555   // x1=shuffle(v1,undef,mask1)
 556   // x2=shuffle(v2,undef,mask2)
 557   //  x=shuffle(x1,x2,mask)
 558   // where v1.size() == v2.size()
 559   //        ==>
 560   //  x=shuffle(v1,v2,newMask)
 561   // newMask[i] = (mask[i] < x1.size())
 562   //              ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size()
 563   //
 564   // Here we are really conservative:
 565   // we are absolutely afraid of producing a shuffle mask not in the input
 566   // program, because the code gen may not be smart enough to turn a merged
 567   // shuffle into two specific shuffles: it may produce worse code.  As such,
 568   // we only merge two shuffles if the result is either a splat or one of the
 569   // input shuffle masks.  In this case, merging the shuffles just removes
 570   // one instruction, which we know is safe.  This is good for things like
 571   // turning: (splat(splat)) -> splat, or
 572   // merge(V[0..n], V[n+1..2n]) -> V[0..2n]
 573   ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS);
 574   ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS);
 575   if (LHSShuffle)
 576     if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS))
 577       LHSShuffle = NULL;
 578   if (RHSShuffle)
 579     if (!isa<UndefValue>(RHSShuffle->getOperand(1)))
 580       RHSShuffle = NULL;
 581   if (!LHSShuffle && !RHSShuffle)
 582     return MadeChange ? &SVI : 0;
 583
 584   Value* LHSOp0 = NULL;
 585   Value* LHSOp1 = NULL;
 586   Value* RHSOp0 = NULL;
 587   unsigned LHSOp0Width = 0;
 588   unsigned RHSOp0Width = 0;
 589   if (LHSShuffle) {
 590     LHSOp0 = LHSShuffle->getOperand(0);
 591     LHSOp1 = LHSShuffle->getOperand(1);
 592     LHSOp0Width = cast<VectorType>(LHSOp0->getType())->getNumElements();
 593   }
 594   if (RHSShuffle) {
 595     RHSOp0 = RHSShuffle->getOperand(0);
 596     RHSOp0Width = cast<VectorType>(RHSOp0->getType())->getNumElements();
 597   }
 598   Value* newLHS = LHS;
 599   Value* newRHS = RHS;
 600   if (LHSShuffle) {
 601     // case 1
 602     if (isa<UndefValue>(RHS)) {
 603       newLHS = LHSOp0;
 604       newRHS = LHSOp1;
 605     }
 606     // case 2 or 4
 607     else if (LHSOp0Width == LHSWidth) {
 608       newLHS = LHSOp0;
 609     }
 610   }
 611   // case 3 or 4
 612   if (RHSShuffle && RHSOp0Width == LHSWidth) {
 613     newRHS = RHSOp0;
 614   }
 615   // case 4
 616   if (LHSOp0 == RHSOp0) {
 617     newLHS = LHSOp0;
 618     newRHS = NULL;
 619   }
 620
 621   if (newLHS == LHS && newRHS == RHS)
 622     return MadeChange ? &SVI : 0;
 623
 624   SmallVector<int, 16> LHSMask;
 625   SmallVector<int, 16> RHSMask;
 626   if (newLHS != LHS) {
 627     LHSMask = getShuffleMask(LHSShuffle);
 628   }
 629   if (RHSShuffle && newRHS != RHS) {
 630     RHSMask = getShuffleMask(RHSShuffle);
 631   }
 632   unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth;
 633   SmallVector<int, 16> newMask;
 634   bool isSplat = true;
 635   int SplatElt = -1;
 636   // Create a new mask for the new ShuffleVectorInst so that the new
 637   // ShuffleVectorInst is equivalent to the original one.
 638   for (unsigned i = 0; i < VWidth; ++i) {
 639     int eltMask;
 640     if (Mask[i] == -1) {
 641       // This element is an undef value.
 642       eltMask = -1;
 643     } else if (Mask[i] < (int)LHSWidth) {
 644       // This element is from left hand side vector operand.
 645       //
 646       // If LHS is going to be replaced (case 1, 2, or 4), calculate the
 647       // new mask value for the element.
 648       if (newLHS != LHS) {
 649         eltMask = LHSMask[Mask[i]];
 650         // If the value selected is an undef value, explicitly specify it
 651         // with a -1 mask value.
 652         if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1))
 653           eltMask = -1;
 654       }
 655       else
 656         eltMask = Mask[i];
 657     } else {
 658       // This element is from right hand side vector operand
 659       //
 660       // If the value selected is an undef value, explicitly specify it
 661       // with a -1 mask value. (case 1)
 662       if (isa<UndefValue>(RHS))
 663         eltMask = -1;
 664       // If RHS is going to be replaced (case 3 or 4), calculate the
 665       // new mask value for the element.
 666       else if (newRHS != RHS) {
 667         eltMask = RHSMask[Mask[i]-LHSWidth];
 668         // If the value selected is an undef value, explicitly specify it
 669         // with a -1 mask value.
 670         if (eltMask >= (int)RHSOp0Width) {
 671           assert(isa<UndefValue>(RHSShuffle->getOperand(1))
 672                  && "should have been check above");
 673           eltMask = -1;
 674         }
 675       }
 676       else
 677         eltMask = Mask[i]-LHSWidth;
 678
 679       // If LHS's width is changed, shift the mask value accordingly.
 680       // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any
 681       // references to RHSOp0 to LHSOp0, so we don't need to shift the mask.
 682       if (eltMask >= 0 && newRHS != NULL)
 683         eltMask += newLHSWidth;
 684     }
 685
 686     // Check if this could still be a splat.
 687     if (eltMask >= 0) {
 688       if (SplatElt >= 0 && SplatElt != eltMask)
 689         isSplat = false;
 690       SplatElt = eltMask;
 691     }
 692
 693     newMask.push_back(eltMask);
 694   }
 695
 696   // If the result mask is equal to one of the original shuffle masks,
 697   // or is a splat, do the replacement.
 698   if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) {
 699     SmallVector<Constant*, 16> Elts;
 700     Type *Int32Ty = Type::getInt32Ty(SVI.getContext());
 701     for (unsigned i = 0, e = newMask.size(); i != e; ++i) {
 702       if (newMask[i] < 0) {
 703         Elts.push_back(UndefValue::get(Int32Ty));
 704       } else {
 705         Elts.push_back(ConstantInt::get(Int32Ty, newMask[i]));
 706       }
 707     }
 708     if (newRHS == NULL)
 709       newRHS = UndefValue::get(newLHS->getType());
 710     return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts));
 711   }
 712
 713   return MadeChange ? &SVI : 0;
 714 }