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