1//===- InstCombineVectorOps.cpp -------------------------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements instcombine for ExtractElement, InsertElement and 11// ShuffleVector. 12// 13//===----------------------------------------------------------------------===// 14 15#include "InstCombineInternal.h" 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/Analysis/InstructionSimplify.h" 18#include "llvm/Analysis/VectorUtils.h" 19#include "llvm/IR/PatternMatch.h" 20using namespace llvm; 21using namespace PatternMatch; 22 23#define DEBUG_TYPE "instcombine" 24 25/// Return true if the value is cheaper to scalarize than it is to leave as a 26/// vector operation. isConstant indicates whether we're extracting one known 27/// element. If false we're extracting a variable index. 28static bool cheapToScalarize(Value *V, bool isConstant) { 29 if (Constant *C = dyn_cast<Constant>(V)) { 30 if (isConstant) return true; 31 32 // If all elts are the same, we can extract it and use any of the values. 33 if (Constant *Op0 = C->getAggregateElement(0U)) { 34 for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e; 35 ++i) 36 if (C->getAggregateElement(i) != Op0) 37 return false; 38 return true; 39 } 40 } 41 Instruction *I = dyn_cast<Instruction>(V); 42 if (!I) return false; 43 44 // Insert element gets simplified to the inserted element or is deleted if 45 // this is constant idx extract element and its a constant idx insertelt. 46 if (I->getOpcode() == Instruction::InsertElement && isConstant && 47 isa<ConstantInt>(I->getOperand(2))) 48 return true; 49 if (I->getOpcode() == Instruction::Load && I->hasOneUse()) 50 return true; 51 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) 52 if (BO->hasOneUse() && 53 (cheapToScalarize(BO->getOperand(0), isConstant) || 54 cheapToScalarize(BO->getOperand(1), isConstant))) 55 return true; 56 if (CmpInst *CI = dyn_cast<CmpInst>(I)) 57 if (CI->hasOneUse() && 58 (cheapToScalarize(CI->getOperand(0), isConstant) || 59 cheapToScalarize(CI->getOperand(1), isConstant))) 60 return true; 61 62 return false; 63} 64 65// If we have a PHI node with a vector type that has only 2 uses: feed 66// itself and be an operand of extractelement at a constant location, 67// try to replace the PHI of the vector type with a PHI of a scalar type. 68Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) { 69 // Verify that the PHI node has exactly 2 uses. Otherwise return NULL. 70 if (!PN->hasNUses(2)) 71 return nullptr; 72 73 // If so, it's known at this point that one operand is PHI and the other is 74 // an extractelement node. Find the PHI user that is not the extractelement 75 // node. 76 auto iu = PN->user_begin(); 77 Instruction *PHIUser = dyn_cast<Instruction>(*iu); 78 if (PHIUser == cast<Instruction>(&EI)) 79 PHIUser = cast<Instruction>(*(++iu)); 80 81 // Verify that this PHI user has one use, which is the PHI itself, 82 // and that it is a binary operation which is cheap to scalarize. 83 // otherwise return NULL. 84 if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) || 85 !(isa<BinaryOperator>(PHIUser)) || !cheapToScalarize(PHIUser, true)) 86 return nullptr; 87 88 // Create a scalar PHI node that will replace the vector PHI node 89 // just before the current PHI node. 90 PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith( 91 PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN)); 92 // Scalarize each PHI operand. 93 for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) { 94 Value *PHIInVal = PN->getIncomingValue(i); 95 BasicBlock *inBB = PN->getIncomingBlock(i); 96 Value *Elt = EI.getIndexOperand(); 97 // If the operand is the PHI induction variable: 98 if (PHIInVal == PHIUser) { 99 // Scalarize the binary operation. Its first operand is the 100 // scalar PHI, and the second operand is extracted from the other 101 // vector operand. 102 BinaryOperator *B0 = cast<BinaryOperator>(PHIUser); 103 unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0; 104 Value *Op = InsertNewInstWith( 105 ExtractElementInst::Create(B0->getOperand(opId), Elt, 106 B0->getOperand(opId)->getName() + ".Elt"), 107 *B0); 108 Value *newPHIUser = InsertNewInstWith( 109 BinaryOperator::Create(B0->getOpcode(), scalarPHI, Op), *B0); 110 scalarPHI->addIncoming(newPHIUser, inBB); 111 } else { 112 // Scalarize PHI input: 113 Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, ""); 114 // Insert the new instruction into the predecessor basic block. 115 Instruction *pos = dyn_cast<Instruction>(PHIInVal); 116 BasicBlock::iterator InsertPos; 117 if (pos && !isa<PHINode>(pos)) { 118 InsertPos = ++pos->getIterator(); 119 } else { 120 InsertPos = inBB->getFirstInsertionPt(); 121 } 122 123 InsertNewInstWith(newEI, *InsertPos); 124 125 scalarPHI->addIncoming(newEI, inBB); 126 } 127 } 128 return ReplaceInstUsesWith(EI, scalarPHI); 129} 130 131Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { 132 if (Value *V = SimplifyExtractElementInst( 133 EI.getVectorOperand(), EI.getIndexOperand(), DL, TLI, DT, AC)) 134 return ReplaceInstUsesWith(EI, V); 135 136 // If vector val is constant with all elements the same, replace EI with 137 // that element. We handle a known element # below. 138 if (Constant *C = dyn_cast<Constant>(EI.getOperand(0))) 139 if (cheapToScalarize(C, false)) 140 return ReplaceInstUsesWith(EI, C->getAggregateElement(0U)); 141 142 // If extracting a specified index from the vector, see if we can recursively 143 // find a previously computed scalar that was inserted into the vector. 144 if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) { 145 unsigned IndexVal = IdxC->getZExtValue(); 146 unsigned VectorWidth = EI.getVectorOperandType()->getNumElements(); 147 148 // InstSimplify handles cases where the index is invalid. 149 assert(IndexVal < VectorWidth); 150 151 // This instruction only demands the single element from the input vector. 152 // If the input vector has a single use, simplify it based on this use 153 // property. 154 if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) { 155 APInt UndefElts(VectorWidth, 0); 156 APInt DemandedMask(VectorWidth, 0); 157 DemandedMask.setBit(IndexVal); 158 if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), DemandedMask, 159 UndefElts)) { 160 EI.setOperand(0, V); 161 return &EI; 162 } 163 } 164 165 // If this extractelement is directly using a bitcast from a vector of 166 // the same number of elements, see if we can find the source element from 167 // it. In this case, we will end up needing to bitcast the scalars. 168 if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) { 169 if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType())) 170 if (VT->getNumElements() == VectorWidth) 171 if (Value *Elt = findScalarElement(BCI->getOperand(0), IndexVal)) 172 return new BitCastInst(Elt, EI.getType()); 173 } 174 175 // If there's a vector PHI feeding a scalar use through this extractelement 176 // instruction, try to scalarize the PHI. 177 if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) { 178 Instruction *scalarPHI = scalarizePHI(EI, PN); 179 if (scalarPHI) 180 return scalarPHI; 181 } 182 } 183 184 if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) { 185 // Push extractelement into predecessor operation if legal and 186 // profitable to do so. 187 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { 188 if (I->hasOneUse() && 189 cheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) { 190 Value *newEI0 = 191 Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1), 192 EI.getName()+".lhs"); 193 Value *newEI1 = 194 Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1), 195 EI.getName()+".rhs"); 196 return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1); 197 } 198 } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) { 199 // Extracting the inserted element? 200 if (IE->getOperand(2) == EI.getOperand(1)) 201 return ReplaceInstUsesWith(EI, IE->getOperand(1)); 202 // If the inserted and extracted elements are constants, they must not 203 // be the same value, extract from the pre-inserted value instead. 204 if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) { 205 Worklist.AddValue(EI.getOperand(0)); 206 EI.setOperand(0, IE->getOperand(0)); 207 return &EI; 208 } 209 } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) { 210 // If this is extracting an element from a shufflevector, figure out where 211 // it came from and extract from the appropriate input element instead. 212 if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) { 213 int SrcIdx = SVI->getMaskValue(Elt->getZExtValue()); 214 Value *Src; 215 unsigned LHSWidth = 216 SVI->getOperand(0)->getType()->getVectorNumElements(); 217 218 if (SrcIdx < 0) 219 return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType())); 220 if (SrcIdx < (int)LHSWidth) 221 Src = SVI->getOperand(0); 222 else { 223 SrcIdx -= LHSWidth; 224 Src = SVI->getOperand(1); 225 } 226 Type *Int32Ty = Type::getInt32Ty(EI.getContext()); 227 return ExtractElementInst::Create(Src, 228 ConstantInt::get(Int32Ty, 229 SrcIdx, false)); 230 } 231 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 232 // Canonicalize extractelement(cast) -> cast(extractelement). 233 // Bitcasts can change the number of vector elements, and they cost 234 // nothing. 235 if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) { 236 Value *EE = Builder->CreateExtractElement(CI->getOperand(0), 237 EI.getIndexOperand()); 238 Worklist.AddValue(EE); 239 return CastInst::Create(CI->getOpcode(), EE, EI.getType()); 240 } 241 } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) { 242 if (SI->hasOneUse()) { 243 // TODO: For a select on vectors, it might be useful to do this if it 244 // has multiple extractelement uses. For vector select, that seems to 245 // fight the vectorizer. 246 247 // If we are extracting an element from a vector select or a select on 248 // vectors, create a select on the scalars extracted from the vector 249 // arguments. 250 Value *TrueVal = SI->getTrueValue(); 251 Value *FalseVal = SI->getFalseValue(); 252 253 Value *Cond = SI->getCondition(); 254 if (Cond->getType()->isVectorTy()) { 255 Cond = Builder->CreateExtractElement(Cond, 256 EI.getIndexOperand(), 257 Cond->getName() + ".elt"); 258 } 259 260 Value *V1Elem 261 = Builder->CreateExtractElement(TrueVal, 262 EI.getIndexOperand(), 263 TrueVal->getName() + ".elt"); 264 265 Value *V2Elem 266 = Builder->CreateExtractElement(FalseVal, 267 EI.getIndexOperand(), 268 FalseVal->getName() + ".elt"); 269 return SelectInst::Create(Cond, 270 V1Elem, 271 V2Elem, 272 SI->getName() + ".elt"); 273 } 274 } 275 } 276 return nullptr; 277} 278 279/// If V is a shuffle of values that ONLY returns elements from either LHS or 280/// RHS, return the shuffle mask and true. Otherwise, return false. 281static bool collectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, 282 SmallVectorImpl<Constant*> &Mask) { 283 assert(LHS->getType() == RHS->getType() && 284 "Invalid CollectSingleShuffleElements"); 285 unsigned NumElts = V->getType()->getVectorNumElements(); 286 287 if (isa<UndefValue>(V)) { 288 Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext()))); 289 return true; 290 } 291 292 if (V == LHS) { 293 for (unsigned i = 0; i != NumElts; ++i) 294 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i)); 295 return true; 296 } 297 298 if (V == RHS) { 299 for (unsigned i = 0; i != NumElts; ++i) 300 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), 301 i+NumElts)); 302 return true; 303 } 304 305 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) { 306 // If this is an insert of an extract from some other vector, include it. 307 Value *VecOp = IEI->getOperand(0); 308 Value *ScalarOp = IEI->getOperand(1); 309 Value *IdxOp = IEI->getOperand(2); 310 311 if (!isa<ConstantInt>(IdxOp)) 312 return false; 313 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); 314 315 if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector. 316 // We can handle this if the vector we are inserting into is 317 // transitively ok. 318 if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) { 319 // If so, update the mask to reflect the inserted undef. 320 Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext())); 321 return true; 322 } 323 } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){ 324 if (isa<ConstantInt>(EI->getOperand(1))) { 325 unsigned ExtractedIdx = 326 cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); 327 unsigned NumLHSElts = LHS->getType()->getVectorNumElements(); 328 329 // This must be extracting from either LHS or RHS. 330 if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) { 331 // We can handle this if the vector we are inserting into is 332 // transitively ok. 333 if (collectSingleShuffleElements(VecOp, LHS, RHS, Mask)) { 334 // If so, update the mask to reflect the inserted value. 335 if (EI->getOperand(0) == LHS) { 336 Mask[InsertedIdx % NumElts] = 337 ConstantInt::get(Type::getInt32Ty(V->getContext()), 338 ExtractedIdx); 339 } else { 340 assert(EI->getOperand(0) == RHS); 341 Mask[InsertedIdx % NumElts] = 342 ConstantInt::get(Type::getInt32Ty(V->getContext()), 343 ExtractedIdx + NumLHSElts); 344 } 345 return true; 346 } 347 } 348 } 349 } 350 } 351 352 return false; 353} 354 355/// If we have insertion into a vector that is wider than the vector that we 356/// are extracting from, try to widen the source vector to allow a single 357/// shufflevector to replace one or more insert/extract pairs. 358static void replaceExtractElements(InsertElementInst *InsElt, 359 ExtractElementInst *ExtElt, 360 InstCombiner &IC) { 361 VectorType *InsVecType = InsElt->getType(); 362 VectorType *ExtVecType = ExtElt->getVectorOperandType(); 363 unsigned NumInsElts = InsVecType->getVectorNumElements(); 364 unsigned NumExtElts = ExtVecType->getVectorNumElements(); 365 366 // The inserted-to vector must be wider than the extracted-from vector. 367 if (InsVecType->getElementType() != ExtVecType->getElementType() || 368 NumExtElts >= NumInsElts) 369 return; 370 371 // Create a shuffle mask to widen the extended-from vector using undefined 372 // values. The mask selects all of the values of the original vector followed 373 // by as many undefined values as needed to create a vector of the same length 374 // as the inserted-to vector. 375 SmallVector<Constant *, 16> ExtendMask; 376 IntegerType *IntType = Type::getInt32Ty(InsElt->getContext()); 377 for (unsigned i = 0; i < NumExtElts; ++i) 378 ExtendMask.push_back(ConstantInt::get(IntType, i)); 379 for (unsigned i = NumExtElts; i < NumInsElts; ++i) 380 ExtendMask.push_back(UndefValue::get(IntType)); 381 382 Value *ExtVecOp = ExtElt->getVectorOperand(); 383 auto *ExtVecOpInst = dyn_cast<Instruction>(ExtVecOp); 384 BasicBlock *InsertionBlock = (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst)) 385 ? ExtVecOpInst->getParent() 386 : ExtElt->getParent(); 387 388 // TODO: This restriction matches the basic block check below when creating 389 // new extractelement instructions. If that limitation is removed, this one 390 // could also be removed. But for now, we just bail out to ensure that we 391 // will replace the extractelement instruction that is feeding our 392 // insertelement instruction. This allows the insertelement to then be 393 // replaced by a shufflevector. If the insertelement is not replaced, we can 394 // induce infinite looping because there's an optimization for extractelement 395 // that will delete our widening shuffle. This would trigger another attempt 396 // here to create that shuffle, and we spin forever. 397 if (InsertionBlock != InsElt->getParent()) 398 return; 399 400 auto *WideVec = new ShuffleVectorInst(ExtVecOp, UndefValue::get(ExtVecType), 401 ConstantVector::get(ExtendMask)); 402 403 // Insert the new shuffle after the vector operand of the extract is defined 404 // (as long as it's not a PHI) or at the start of the basic block of the 405 // extract, so any subsequent extracts in the same basic block can use it. 406 // TODO: Insert before the earliest ExtractElementInst that is replaced. 407 if (ExtVecOpInst && !isa<PHINode>(ExtVecOpInst)) 408 WideVec->insertAfter(ExtVecOpInst); 409 else 410 IC.InsertNewInstWith(WideVec, *ExtElt->getParent()->getFirstInsertionPt()); 411 412 // Replace extracts from the original narrow vector with extracts from the new 413 // wide vector. 414 for (User *U : ExtVecOp->users()) { 415 ExtractElementInst *OldExt = dyn_cast<ExtractElementInst>(U); 416 if (!OldExt || OldExt->getParent() != WideVec->getParent()) 417 continue; 418 auto *NewExt = ExtractElementInst::Create(WideVec, OldExt->getOperand(1)); 419 NewExt->insertAfter(WideVec); 420 IC.ReplaceInstUsesWith(*OldExt, NewExt); 421 } 422} 423 424/// We are building a shuffle to create V, which is a sequence of insertelement, 425/// extractelement pairs. If PermittedRHS is set, then we must either use it or 426/// not rely on the second vector source. Return a std::pair containing the 427/// left and right vectors of the proposed shuffle (or 0), and set the Mask 428/// parameter as required. 429/// 430/// Note: we intentionally don't try to fold earlier shuffles since they have 431/// often been chosen carefully to be efficiently implementable on the target. 432typedef std::pair<Value *, Value *> ShuffleOps; 433 434static ShuffleOps collectShuffleElements(Value *V, 435 SmallVectorImpl<Constant *> &Mask, 436 Value *PermittedRHS, 437 InstCombiner &IC) { 438 assert(V->getType()->isVectorTy() && "Invalid shuffle!"); 439 unsigned NumElts = cast<VectorType>(V->getType())->getNumElements(); 440 441 if (isa<UndefValue>(V)) { 442 Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext()))); 443 return std::make_pair( 444 PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr); 445 } 446 447 if (isa<ConstantAggregateZero>(V)) { 448 Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0)); 449 return std::make_pair(V, nullptr); 450 } 451 452 if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) { 453 // If this is an insert of an extract from some other vector, include it. 454 Value *VecOp = IEI->getOperand(0); 455 Value *ScalarOp = IEI->getOperand(1); 456 Value *IdxOp = IEI->getOperand(2); 457 458 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) { 459 if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) { 460 unsigned ExtractedIdx = 461 cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); 462 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); 463 464 // Either the extracted from or inserted into vector must be RHSVec, 465 // otherwise we'd end up with a shuffle of three inputs. 466 if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) { 467 Value *RHS = EI->getOperand(0); 468 ShuffleOps LR = collectShuffleElements(VecOp, Mask, RHS, IC); 469 assert(LR.second == nullptr || LR.second == RHS); 470 471 if (LR.first->getType() != RHS->getType()) { 472 // Although we are giving up for now, see if we can create extracts 473 // that match the inserts for another round of combining. 474 replaceExtractElements(IEI, EI, IC); 475 476 // We tried our best, but we can't find anything compatible with RHS 477 // further up the chain. Return a trivial shuffle. 478 for (unsigned i = 0; i < NumElts; ++i) 479 Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i); 480 return std::make_pair(V, nullptr); 481 } 482 483 unsigned NumLHSElts = RHS->getType()->getVectorNumElements(); 484 Mask[InsertedIdx % NumElts] = 485 ConstantInt::get(Type::getInt32Ty(V->getContext()), 486 NumLHSElts+ExtractedIdx); 487 return std::make_pair(LR.first, RHS); 488 } 489 490 if (VecOp == PermittedRHS) { 491 // We've gone as far as we can: anything on the other side of the 492 // extractelement will already have been converted into a shuffle. 493 unsigned NumLHSElts = 494 EI->getOperand(0)->getType()->getVectorNumElements(); 495 for (unsigned i = 0; i != NumElts; ++i) 496 Mask.push_back(ConstantInt::get( 497 Type::getInt32Ty(V->getContext()), 498 i == InsertedIdx ? ExtractedIdx : NumLHSElts + i)); 499 return std::make_pair(EI->getOperand(0), PermittedRHS); 500 } 501 502 // If this insertelement is a chain that comes from exactly these two 503 // vectors, return the vector and the effective shuffle. 504 if (EI->getOperand(0)->getType() == PermittedRHS->getType() && 505 collectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS, 506 Mask)) 507 return std::make_pair(EI->getOperand(0), PermittedRHS); 508 } 509 } 510 } 511 512 // Otherwise, we can't do anything fancy. Return an identity vector. 513 for (unsigned i = 0; i != NumElts; ++i) 514 Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i)); 515 return std::make_pair(V, nullptr); 516} 517 518/// Try to find redundant insertvalue instructions, like the following ones: 519/// %0 = insertvalue { i8, i32 } undef, i8 %x, 0 520/// %1 = insertvalue { i8, i32 } %0, i8 %y, 0 521/// Here the second instruction inserts values at the same indices, as the 522/// first one, making the first one redundant. 523/// It should be transformed to: 524/// %0 = insertvalue { i8, i32 } undef, i8 %y, 0 525Instruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) { 526 bool IsRedundant = false; 527 ArrayRef<unsigned int> FirstIndices = I.getIndices(); 528 529 // If there is a chain of insertvalue instructions (each of them except the 530 // last one has only one use and it's another insertvalue insn from this 531 // chain), check if any of the 'children' uses the same indices as the first 532 // instruction. In this case, the first one is redundant. 533 Value *V = &I; 534 unsigned Depth = 0; 535 while (V->hasOneUse() && Depth < 10) { 536 User *U = V->user_back(); 537 auto UserInsInst = dyn_cast<InsertValueInst>(U); 538 if (!UserInsInst || U->getOperand(0) != V) 539 break; 540 if (UserInsInst->getIndices() == FirstIndices) { 541 IsRedundant = true; 542 break; 543 } 544 V = UserInsInst; 545 Depth++; 546 } 547 548 if (IsRedundant) 549 return ReplaceInstUsesWith(I, I.getOperand(0)); 550 return nullptr; 551} 552 553Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { 554 Value *VecOp = IE.getOperand(0); 555 Value *ScalarOp = IE.getOperand(1); 556 Value *IdxOp = IE.getOperand(2); 557 558 // Inserting an undef or into an undefined place, remove this. 559 if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp)) 560 ReplaceInstUsesWith(IE, VecOp); 561 562 // If the inserted element was extracted from some other vector, and if the 563 // indexes are constant, try to turn this into a shufflevector operation. 564 if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) { 565 if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) { 566 unsigned NumInsertVectorElts = IE.getType()->getNumElements(); 567 unsigned NumExtractVectorElts = 568 EI->getOperand(0)->getType()->getVectorNumElements(); 569 unsigned ExtractedIdx = 570 cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); 571 unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); 572 573 if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract. 574 return ReplaceInstUsesWith(IE, VecOp); 575 576 if (InsertedIdx >= NumInsertVectorElts) // Out of range insert. 577 return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType())); 578 579 // If we are extracting a value from a vector, then inserting it right 580 // back into the same place, just use the input vector. 581 if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx) 582 return ReplaceInstUsesWith(IE, VecOp); 583 584 // If this insertelement isn't used by some other insertelement, turn it 585 // (and any insertelements it points to), into one big shuffle. 586 if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) { 587 SmallVector<Constant*, 16> Mask; 588 ShuffleOps LR = collectShuffleElements(&IE, Mask, nullptr, *this); 589 590 // The proposed shuffle may be trivial, in which case we shouldn't 591 // perform the combine. 592 if (LR.first != &IE && LR.second != &IE) { 593 // We now have a shuffle of LHS, RHS, Mask. 594 if (LR.second == nullptr) 595 LR.second = UndefValue::get(LR.first->getType()); 596 return new ShuffleVectorInst(LR.first, LR.second, 597 ConstantVector::get(Mask)); 598 } 599 } 600 } 601 } 602 603 unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements(); 604 APInt UndefElts(VWidth, 0); 605 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); 606 if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) { 607 if (V != &IE) 608 return ReplaceInstUsesWith(IE, V); 609 return &IE; 610 } 611 612 return nullptr; 613} 614 615/// Return true if we can evaluate the specified expression tree if the vector 616/// elements were shuffled in a different order. 617static bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask, 618 unsigned Depth = 5) { 619 // We can always reorder the elements of a constant. 620 if (isa<Constant>(V)) 621 return true; 622 623 // We won't reorder vector arguments. No IPO here. 624 Instruction *I = dyn_cast<Instruction>(V); 625 if (!I) return false; 626 627 // Two users may expect different orders of the elements. Don't try it. 628 if (!I->hasOneUse()) 629 return false; 630 631 if (Depth == 0) return false; 632 633 switch (I->getOpcode()) { 634 case Instruction::Add: 635 case Instruction::FAdd: 636 case Instruction::Sub: 637 case Instruction::FSub: 638 case Instruction::Mul: 639 case Instruction::FMul: 640 case Instruction::UDiv: 641 case Instruction::SDiv: 642 case Instruction::FDiv: 643 case Instruction::URem: 644 case Instruction::SRem: 645 case Instruction::FRem: 646 case Instruction::Shl: 647 case Instruction::LShr: 648 case Instruction::AShr: 649 case Instruction::And: 650 case Instruction::Or: 651 case Instruction::Xor: 652 case Instruction::ICmp: 653 case Instruction::FCmp: 654 case Instruction::Trunc: 655 case Instruction::ZExt: 656 case Instruction::SExt: 657 case Instruction::FPToUI: 658 case Instruction::FPToSI: 659 case Instruction::UIToFP: 660 case Instruction::SIToFP: 661 case Instruction::FPTrunc: 662 case Instruction::FPExt: 663 case Instruction::GetElementPtr: { 664 for (Value *Operand : I->operands()) { 665 if (!CanEvaluateShuffled(Operand, Mask, Depth-1)) 666 return false; 667 } 668 return true; 669 } 670 case Instruction::InsertElement: { 671 ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2)); 672 if (!CI) return false; 673 int ElementNumber = CI->getLimitedValue(); 674 675 // Verify that 'CI' does not occur twice in Mask. A single 'insertelement' 676 // can't put an element into multiple indices. 677 bool SeenOnce = false; 678 for (int i = 0, e = Mask.size(); i != e; ++i) { 679 if (Mask[i] == ElementNumber) { 680 if (SeenOnce) 681 return false; 682 SeenOnce = true; 683 } 684 } 685 return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1); 686 } 687 } 688 return false; 689} 690 691/// Rebuild a new instruction just like 'I' but with the new operands given. 692/// In the event of type mismatch, the type of the operands is correct. 693static Value *buildNew(Instruction *I, ArrayRef<Value*> NewOps) { 694 // We don't want to use the IRBuilder here because we want the replacement 695 // instructions to appear next to 'I', not the builder's insertion point. 696 switch (I->getOpcode()) { 697 case Instruction::Add: 698 case Instruction::FAdd: 699 case Instruction::Sub: 700 case Instruction::FSub: 701 case Instruction::Mul: 702 case Instruction::FMul: 703 case Instruction::UDiv: 704 case Instruction::SDiv: 705 case Instruction::FDiv: 706 case Instruction::URem: 707 case Instruction::SRem: 708 case Instruction::FRem: 709 case Instruction::Shl: 710 case Instruction::LShr: 711 case Instruction::AShr: 712 case Instruction::And: 713 case Instruction::Or: 714 case Instruction::Xor: { 715 BinaryOperator *BO = cast<BinaryOperator>(I); 716 assert(NewOps.size() == 2 && "binary operator with #ops != 2"); 717 BinaryOperator *New = 718 BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(), 719 NewOps[0], NewOps[1], "", BO); 720 if (isa<OverflowingBinaryOperator>(BO)) { 721 New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap()); 722 New->setHasNoSignedWrap(BO->hasNoSignedWrap()); 723 } 724 if (isa<PossiblyExactOperator>(BO)) { 725 New->setIsExact(BO->isExact()); 726 } 727 if (isa<FPMathOperator>(BO)) 728 New->copyFastMathFlags(I); 729 return New; 730 } 731 case Instruction::ICmp: 732 assert(NewOps.size() == 2 && "icmp with #ops != 2"); 733 return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(), 734 NewOps[0], NewOps[1]); 735 case Instruction::FCmp: 736 assert(NewOps.size() == 2 && "fcmp with #ops != 2"); 737 return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(), 738 NewOps[0], NewOps[1]); 739 case Instruction::Trunc: 740 case Instruction::ZExt: 741 case Instruction::SExt: 742 case Instruction::FPToUI: 743 case Instruction::FPToSI: 744 case Instruction::UIToFP: 745 case Instruction::SIToFP: 746 case Instruction::FPTrunc: 747 case Instruction::FPExt: { 748 // It's possible that the mask has a different number of elements from 749 // the original cast. We recompute the destination type to match the mask. 750 Type *DestTy = 751 VectorType::get(I->getType()->getScalarType(), 752 NewOps[0]->getType()->getVectorNumElements()); 753 assert(NewOps.size() == 1 && "cast with #ops != 1"); 754 return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy, 755 "", I); 756 } 757 case Instruction::GetElementPtr: { 758 Value *Ptr = NewOps[0]; 759 ArrayRef<Value*> Idx = NewOps.slice(1); 760 GetElementPtrInst *GEP = GetElementPtrInst::Create( 761 cast<GetElementPtrInst>(I)->getSourceElementType(), Ptr, Idx, "", I); 762 GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds()); 763 return GEP; 764 } 765 } 766 llvm_unreachable("failed to rebuild vector instructions"); 767} 768 769Value * 770InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { 771 // Mask.size() does not need to be equal to the number of vector elements. 772 773 assert(V->getType()->isVectorTy() && "can't reorder non-vector elements"); 774 if (isa<UndefValue>(V)) { 775 return UndefValue::get(VectorType::get(V->getType()->getScalarType(), 776 Mask.size())); 777 } 778 if (isa<ConstantAggregateZero>(V)) { 779 return ConstantAggregateZero::get( 780 VectorType::get(V->getType()->getScalarType(), 781 Mask.size())); 782 } 783 if (Constant *C = dyn_cast<Constant>(V)) { 784 SmallVector<Constant *, 16> MaskValues; 785 for (int i = 0, e = Mask.size(); i != e; ++i) { 786 if (Mask[i] == -1) 787 MaskValues.push_back(UndefValue::get(Builder->getInt32Ty())); 788 else 789 MaskValues.push_back(Builder->getInt32(Mask[i])); 790 } 791 return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()), 792 ConstantVector::get(MaskValues)); 793 } 794 795 Instruction *I = cast<Instruction>(V); 796 switch (I->getOpcode()) { 797 case Instruction::Add: 798 case Instruction::FAdd: 799 case Instruction::Sub: 800 case Instruction::FSub: 801 case Instruction::Mul: 802 case Instruction::FMul: 803 case Instruction::UDiv: 804 case Instruction::SDiv: 805 case Instruction::FDiv: 806 case Instruction::URem: 807 case Instruction::SRem: 808 case Instruction::FRem: 809 case Instruction::Shl: 810 case Instruction::LShr: 811 case Instruction::AShr: 812 case Instruction::And: 813 case Instruction::Or: 814 case Instruction::Xor: 815 case Instruction::ICmp: 816 case Instruction::FCmp: 817 case Instruction::Trunc: 818 case Instruction::ZExt: 819 case Instruction::SExt: 820 case Instruction::FPToUI: 821 case Instruction::FPToSI: 822 case Instruction::UIToFP: 823 case Instruction::SIToFP: 824 case Instruction::FPTrunc: 825 case Instruction::FPExt: 826 case Instruction::Select: 827 case Instruction::GetElementPtr: { 828 SmallVector<Value*, 8> NewOps; 829 bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements()); 830 for (int i = 0, e = I->getNumOperands(); i != e; ++i) { 831 Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask); 832 NewOps.push_back(V); 833 NeedsRebuild |= (V != I->getOperand(i)); 834 } 835 if (NeedsRebuild) { 836 return buildNew(I, NewOps); 837 } 838 return I; 839 } 840 case Instruction::InsertElement: { 841 int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue(); 842 843 // The insertelement was inserting at Element. Figure out which element 844 // that becomes after shuffling. The answer is guaranteed to be unique 845 // by CanEvaluateShuffled. 846 bool Found = false; 847 int Index = 0; 848 for (int e = Mask.size(); Index != e; ++Index) { 849 if (Mask[Index] == Element) { 850 Found = true; 851 break; 852 } 853 } 854 855 // If element is not in Mask, no need to handle the operand 1 (element to 856 // be inserted). Just evaluate values in operand 0 according to Mask. 857 if (!Found) 858 return EvaluateInDifferentElementOrder(I->getOperand(0), Mask); 859 860 Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask); 861 return InsertElementInst::Create(V, I->getOperand(1), 862 Builder->getInt32(Index), "", I); 863 } 864 } 865 llvm_unreachable("failed to reorder elements of vector instruction!"); 866} 867 868static void recognizeIdentityMask(const SmallVectorImpl<int> &Mask, 869 bool &isLHSID, bool &isRHSID) { 870 isLHSID = isRHSID = true; 871 872 for (unsigned i = 0, e = Mask.size(); i != e; ++i) { 873 if (Mask[i] < 0) continue; // Ignore undef values. 874 // Is this an identity shuffle of the LHS value? 875 isLHSID &= (Mask[i] == (int)i); 876 877 // Is this an identity shuffle of the RHS value? 878 isRHSID &= (Mask[i]-e == i); 879 } 880} 881 882// Returns true if the shuffle is extracting a contiguous range of values from 883// LHS, for example: 884// +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 885// Input: |AA|BB|CC|DD|EE|FF|GG|HH|II|JJ|KK|LL|MM|NN|OO|PP| 886// Shuffles to: |EE|FF|GG|HH| 887// +--+--+--+--+ 888static bool isShuffleExtractingFromLHS(ShuffleVectorInst &SVI, 889 SmallVector<int, 16> &Mask) { 890 unsigned LHSElems = 891 cast<VectorType>(SVI.getOperand(0)->getType())->getNumElements(); 892 unsigned MaskElems = Mask.size(); 893 unsigned BegIdx = Mask.front(); 894 unsigned EndIdx = Mask.back(); 895 if (BegIdx > EndIdx || EndIdx >= LHSElems || EndIdx - BegIdx != MaskElems - 1) 896 return false; 897 for (unsigned I = 0; I != MaskElems; ++I) 898 if (static_cast<unsigned>(Mask[I]) != BegIdx + I) 899 return false; 900 return true; 901} 902 903Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { 904 Value *LHS = SVI.getOperand(0); 905 Value *RHS = SVI.getOperand(1); 906 SmallVector<int, 16> Mask = SVI.getShuffleMask(); 907 Type *Int32Ty = Type::getInt32Ty(SVI.getContext()); 908 909 bool MadeChange = false; 910 911 // Undefined shuffle mask -> undefined value. 912 if (isa<UndefValue>(SVI.getOperand(2))) 913 return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType())); 914 915 unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements(); 916 917 APInt UndefElts(VWidth, 0); 918 APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); 919 if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) { 920 if (V != &SVI) 921 return ReplaceInstUsesWith(SVI, V); 922 LHS = SVI.getOperand(0); 923 RHS = SVI.getOperand(1); 924 MadeChange = true; 925 } 926 927 unsigned LHSWidth = cast<VectorType>(LHS->getType())->getNumElements(); 928 929 // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask') 930 // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask'). 931 if (LHS == RHS || isa<UndefValue>(LHS)) { 932 if (isa<UndefValue>(LHS) && LHS == RHS) { 933 // shuffle(undef,undef,mask) -> undef. 934 Value *Result = (VWidth == LHSWidth) 935 ? LHS : UndefValue::get(SVI.getType()); 936 return ReplaceInstUsesWith(SVI, Result); 937 } 938 939 // Remap any references to RHS to use LHS. 940 SmallVector<Constant*, 16> Elts; 941 for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) { 942 if (Mask[i] < 0) { 943 Elts.push_back(UndefValue::get(Int32Ty)); 944 continue; 945 } 946 947 if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) || 948 (Mask[i] < (int)e && isa<UndefValue>(LHS))) { 949 Mask[i] = -1; // Turn into undef. 950 Elts.push_back(UndefValue::get(Int32Ty)); 951 } else { 952 Mask[i] = Mask[i] % e; // Force to LHS. 953 Elts.push_back(ConstantInt::get(Int32Ty, Mask[i])); 954 } 955 } 956 SVI.setOperand(0, SVI.getOperand(1)); 957 SVI.setOperand(1, UndefValue::get(RHS->getType())); 958 SVI.setOperand(2, ConstantVector::get(Elts)); 959 LHS = SVI.getOperand(0); 960 RHS = SVI.getOperand(1); 961 MadeChange = true; 962 } 963 964 if (VWidth == LHSWidth) { 965 // Analyze the shuffle, are the LHS or RHS and identity shuffles? 966 bool isLHSID, isRHSID; 967 recognizeIdentityMask(Mask, isLHSID, isRHSID); 968 969 // Eliminate identity shuffles. 970 if (isLHSID) return ReplaceInstUsesWith(SVI, LHS); 971 if (isRHSID) return ReplaceInstUsesWith(SVI, RHS); 972 } 973 974 if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) { 975 Value *V = EvaluateInDifferentElementOrder(LHS, Mask); 976 return ReplaceInstUsesWith(SVI, V); 977 } 978 979 // SROA generates shuffle+bitcast when the extracted sub-vector is bitcast to 980 // a non-vector type. We can instead bitcast the original vector followed by 981 // an extract of the desired element: 982 // 983 // %sroa = shufflevector <16 x i8> %in, <16 x i8> undef, 984 // <4 x i32> <i32 0, i32 1, i32 2, i32 3> 985 // %1 = bitcast <4 x i8> %sroa to i32 986 // Becomes: 987 // %bc = bitcast <16 x i8> %in to <4 x i32> 988 // %ext = extractelement <4 x i32> %bc, i32 0 989 // 990 // If the shuffle is extracting a contiguous range of values from the input 991 // vector then each use which is a bitcast of the extracted size can be 992 // replaced. This will work if the vector types are compatible, and the begin 993 // index is aligned to a value in the casted vector type. If the begin index 994 // isn't aligned then we can shuffle the original vector (keeping the same 995 // vector type) before extracting. 996 // 997 // This code will bail out if the target type is fundamentally incompatible 998 // with vectors of the source type. 999 // 1000 // Example of <16 x i8>, target type i32: 1001 // Index range [4,8): v-----------v Will work. 1002 // +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ 1003 // <16 x i8>: | | | | | | | | | | | | | | | | | 1004 // <4 x i32>: | | | | | 1005 // +-----------+-----------+-----------+-----------+ 1006 // Index range [6,10): ^-----------^ Needs an extra shuffle. 1007 // Target type i40: ^--------------^ Won't work, bail. 1008 if (isShuffleExtractingFromLHS(SVI, Mask)) { 1009 Value *V = LHS; 1010 unsigned MaskElems = Mask.size(); 1011 unsigned BegIdx = Mask.front(); 1012 VectorType *SrcTy = cast<VectorType>(V->getType()); 1013 unsigned VecBitWidth = SrcTy->getBitWidth(); 1014 unsigned SrcElemBitWidth = DL.getTypeSizeInBits(SrcTy->getElementType()); 1015 assert(SrcElemBitWidth && "vector elements must have a bitwidth"); 1016 unsigned SrcNumElems = SrcTy->getNumElements(); 1017 SmallVector<BitCastInst *, 8> BCs; 1018 DenseMap<Type *, Value *> NewBCs; 1019 for (User *U : SVI.users()) 1020 if (BitCastInst *BC = dyn_cast<BitCastInst>(U)) 1021 if (!BC->use_empty()) 1022 // Only visit bitcasts that weren't previously handled. 1023 BCs.push_back(BC); 1024 for (BitCastInst *BC : BCs) { 1025 Type *TgtTy = BC->getDestTy(); 1026 unsigned TgtElemBitWidth = DL.getTypeSizeInBits(TgtTy); 1027 if (!TgtElemBitWidth) 1028 continue; 1029 unsigned TgtNumElems = VecBitWidth / TgtElemBitWidth; 1030 bool VecBitWidthsEqual = VecBitWidth == TgtNumElems * TgtElemBitWidth; 1031 bool BegIsAligned = 0 == ((SrcElemBitWidth * BegIdx) % TgtElemBitWidth); 1032 if (!VecBitWidthsEqual) 1033 continue; 1034 if (!VectorType::isValidElementType(TgtTy)) 1035 continue; 1036 VectorType *CastSrcTy = VectorType::get(TgtTy, TgtNumElems); 1037 if (!BegIsAligned) { 1038 // Shuffle the input so [0,NumElements) contains the output, and 1039 // [NumElems,SrcNumElems) is undef. 1040 SmallVector<Constant *, 16> ShuffleMask(SrcNumElems, 1041 UndefValue::get(Int32Ty)); 1042 for (unsigned I = 0, E = MaskElems, Idx = BegIdx; I != E; ++Idx, ++I) 1043 ShuffleMask[I] = ConstantInt::get(Int32Ty, Idx); 1044 V = Builder->CreateShuffleVector(V, UndefValue::get(V->getType()), 1045 ConstantVector::get(ShuffleMask), 1046 SVI.getName() + ".extract"); 1047 BegIdx = 0; 1048 } 1049 unsigned SrcElemsPerTgtElem = TgtElemBitWidth / SrcElemBitWidth; 1050 assert(SrcElemsPerTgtElem); 1051 BegIdx /= SrcElemsPerTgtElem; 1052 bool BCAlreadyExists = NewBCs.find(CastSrcTy) != NewBCs.end(); 1053 auto *NewBC = 1054 BCAlreadyExists 1055 ? NewBCs[CastSrcTy] 1056 : Builder->CreateBitCast(V, CastSrcTy, SVI.getName() + ".bc"); 1057 if (!BCAlreadyExists) 1058 NewBCs[CastSrcTy] = NewBC; 1059 auto *Ext = Builder->CreateExtractElement( 1060 NewBC, ConstantInt::get(Int32Ty, BegIdx), SVI.getName() + ".extract"); 1061 // The shufflevector isn't being replaced: the bitcast that used it 1062 // is. InstCombine will visit the newly-created instructions. 1063 ReplaceInstUsesWith(*BC, Ext); 1064 MadeChange = true; 1065 } 1066 } 1067 1068 // If the LHS is a shufflevector itself, see if we can combine it with this 1069 // one without producing an unusual shuffle. 1070 // Cases that might be simplified: 1071 // 1. 1072 // x1=shuffle(v1,v2,mask1) 1073 // x=shuffle(x1,undef,mask) 1074 // ==> 1075 // x=shuffle(v1,undef,newMask) 1076 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1 1077 // 2. 1078 // x1=shuffle(v1,undef,mask1) 1079 // x=shuffle(x1,x2,mask) 1080 // where v1.size() == mask1.size() 1081 // ==> 1082 // x=shuffle(v1,x2,newMask) 1083 // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i] 1084 // 3. 1085 // x2=shuffle(v2,undef,mask2) 1086 // x=shuffle(x1,x2,mask) 1087 // where v2.size() == mask2.size() 1088 // ==> 1089 // x=shuffle(x1,v2,newMask) 1090 // newMask[i] = (mask[i] < x1.size()) 1091 // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size() 1092 // 4. 1093 // x1=shuffle(v1,undef,mask1) 1094 // x2=shuffle(v2,undef,mask2) 1095 // x=shuffle(x1,x2,mask) 1096 // where v1.size() == v2.size() 1097 // ==> 1098 // x=shuffle(v1,v2,newMask) 1099 // newMask[i] = (mask[i] < x1.size()) 1100 // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size() 1101 // 1102 // Here we are really conservative: 1103 // we are absolutely afraid of producing a shuffle mask not in the input 1104 // program, because the code gen may not be smart enough to turn a merged 1105 // shuffle into two specific shuffles: it may produce worse code. As such, 1106 // we only merge two shuffles if the result is either a splat or one of the 1107 // input shuffle masks. In this case, merging the shuffles just removes 1108 // one instruction, which we know is safe. This is good for things like 1109 // turning: (splat(splat)) -> splat, or 1110 // merge(V[0..n], V[n+1..2n]) -> V[0..2n] 1111 ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS); 1112 ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS); 1113 if (LHSShuffle) 1114 if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS)) 1115 LHSShuffle = nullptr; 1116 if (RHSShuffle) 1117 if (!isa<UndefValue>(RHSShuffle->getOperand(1))) 1118 RHSShuffle = nullptr; 1119 if (!LHSShuffle && !RHSShuffle) 1120 return MadeChange ? &SVI : nullptr; 1121 1122 Value* LHSOp0 = nullptr; 1123 Value* LHSOp1 = nullptr; 1124 Value* RHSOp0 = nullptr; 1125 unsigned LHSOp0Width = 0; 1126 unsigned RHSOp0Width = 0; 1127 if (LHSShuffle) { 1128 LHSOp0 = LHSShuffle->getOperand(0); 1129 LHSOp1 = LHSShuffle->getOperand(1); 1130 LHSOp0Width = cast<VectorType>(LHSOp0->getType())->getNumElements(); 1131 } 1132 if (RHSShuffle) { 1133 RHSOp0 = RHSShuffle->getOperand(0); 1134 RHSOp0Width = cast<VectorType>(RHSOp0->getType())->getNumElements(); 1135 } 1136 Value* newLHS = LHS; 1137 Value* newRHS = RHS; 1138 if (LHSShuffle) { 1139 // case 1 1140 if (isa<UndefValue>(RHS)) { 1141 newLHS = LHSOp0; 1142 newRHS = LHSOp1; 1143 } 1144 // case 2 or 4 1145 else if (LHSOp0Width == LHSWidth) { 1146 newLHS = LHSOp0; 1147 } 1148 } 1149 // case 3 or 4 1150 if (RHSShuffle && RHSOp0Width == LHSWidth) { 1151 newRHS = RHSOp0; 1152 } 1153 // case 4 1154 if (LHSOp0 == RHSOp0) { 1155 newLHS = LHSOp0; 1156 newRHS = nullptr; 1157 } 1158 1159 if (newLHS == LHS && newRHS == RHS) 1160 return MadeChange ? &SVI : nullptr; 1161 1162 SmallVector<int, 16> LHSMask; 1163 SmallVector<int, 16> RHSMask; 1164 if (newLHS != LHS) 1165 LHSMask = LHSShuffle->getShuffleMask(); 1166 if (RHSShuffle && newRHS != RHS) 1167 RHSMask = RHSShuffle->getShuffleMask(); 1168 1169 unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth; 1170 SmallVector<int, 16> newMask; 1171 bool isSplat = true; 1172 int SplatElt = -1; 1173 // Create a new mask for the new ShuffleVectorInst so that the new 1174 // ShuffleVectorInst is equivalent to the original one. 1175 for (unsigned i = 0; i < VWidth; ++i) { 1176 int eltMask; 1177 if (Mask[i] < 0) { 1178 // This element is an undef value. 1179 eltMask = -1; 1180 } else if (Mask[i] < (int)LHSWidth) { 1181 // This element is from left hand side vector operand. 1182 // 1183 // If LHS is going to be replaced (case 1, 2, or 4), calculate the 1184 // new mask value for the element. 1185 if (newLHS != LHS) { 1186 eltMask = LHSMask[Mask[i]]; 1187 // If the value selected is an undef value, explicitly specify it 1188 // with a -1 mask value. 1189 if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1)) 1190 eltMask = -1; 1191 } else 1192 eltMask = Mask[i]; 1193 } else { 1194 // This element is from right hand side vector operand 1195 // 1196 // If the value selected is an undef value, explicitly specify it 1197 // with a -1 mask value. (case 1) 1198 if (isa<UndefValue>(RHS)) 1199 eltMask = -1; 1200 // If RHS is going to be replaced (case 3 or 4), calculate the 1201 // new mask value for the element. 1202 else if (newRHS != RHS) { 1203 eltMask = RHSMask[Mask[i]-LHSWidth]; 1204 // If the value selected is an undef value, explicitly specify it 1205 // with a -1 mask value. 1206 if (eltMask >= (int)RHSOp0Width) { 1207 assert(isa<UndefValue>(RHSShuffle->getOperand(1)) 1208 && "should have been check above"); 1209 eltMask = -1; 1210 } 1211 } else 1212 eltMask = Mask[i]-LHSWidth; 1213 1214 // If LHS's width is changed, shift the mask value accordingly. 1215 // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any 1216 // references from RHSOp0 to LHSOp0, so we don't need to shift the mask. 1217 // If newRHS == newLHS, we want to remap any references from newRHS to 1218 // newLHS so that we can properly identify splats that may occur due to 1219 // obfuscation across the two vectors. 1220 if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS) 1221 eltMask += newLHSWidth; 1222 } 1223 1224 // Check if this could still be a splat. 1225 if (eltMask >= 0) { 1226 if (SplatElt >= 0 && SplatElt != eltMask) 1227 isSplat = false; 1228 SplatElt = eltMask; 1229 } 1230 1231 newMask.push_back(eltMask); 1232 } 1233 1234 // If the result mask is equal to one of the original shuffle masks, 1235 // or is a splat, do the replacement. 1236 if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) { 1237 SmallVector<Constant*, 16> Elts; 1238 for (unsigned i = 0, e = newMask.size(); i != e; ++i) { 1239 if (newMask[i] < 0) { 1240 Elts.push_back(UndefValue::get(Int32Ty)); 1241 } else { 1242 Elts.push_back(ConstantInt::get(Int32Ty, newMask[i])); 1243 } 1244 } 1245 if (!newRHS) 1246 newRHS = UndefValue::get(newLHS->getType()); 1247 return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts)); 1248 } 1249 1250 // If the result mask is an identity, replace uses of this instruction with 1251 // corresponding argument. 1252 bool isLHSID, isRHSID; 1253 recognizeIdentityMask(newMask, isLHSID, isRHSID); 1254 if (isLHSID && VWidth == LHSOp0Width) return ReplaceInstUsesWith(SVI, newLHS); 1255 if (isRHSID && VWidth == RHSOp0Width) return ReplaceInstUsesWith(SVI, newRHS); 1256 1257 return MadeChange ? &SVI : nullptr; 1258} 1259