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