1b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner//===- InstCombineVectorOps.cpp -------------------------------------------===// 2b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// 3b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// The LLVM Compiler Infrastructure 4b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// 5b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// This file is distributed under the University of Illinois Open Source 6b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// License. See LICENSE.TXT for details. 7b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// 8b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner//===----------------------------------------------------------------------===// 9b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// 10b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// This file implements instcombine for ExtractElement, InsertElement and 11b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// ShuffleVector. 12b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner// 13b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner//===----------------------------------------------------------------------===// 14b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 15b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner#include "InstCombine.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PatternMatch.h" 17b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattnerusing namespace llvm; 1883d585383345b84ae4a9590e97135f95ae39406bNadav Rotemusing namespace PatternMatch; 19b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 20dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "instcombine" 21dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 22b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner/// CheapToScalarize - Return true if the value is cheaper to scalarize than it 23bec2d03c4d774e67ebc586b3a00792d996f26140Chris Lattner/// is to leave as a vector operation. isConstant indicates whether we're 24bec2d03c4d774e67ebc586b3a00792d996f26140Chris Lattner/// extracting one known element. If false we're extracting a variable index. 25b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattnerstatic bool CheapToScalarize(Value *V, bool isConstant) { 26230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) { 27b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isConstant) return true; 28230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner 29230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner // If all elts are the same, we can extract it and use any of the values. 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Constant *Op0 = C->getAggregateElement(0U)) { 3136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e; 3236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++i) 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (C->getAggregateElement(i) != Op0) 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 3536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 3636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 37b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 38b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Instruction *I = dyn_cast<Instruction>(V); 39b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (!I) return false; 4009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 41b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Insert element gets simplified to the inserted element or is deleted if 42b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // this is constant idx extract element and its a constant idx insertelt. 43b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (I->getOpcode() == Instruction::InsertElement && isConstant && 44b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner isa<ConstantInt>(I->getOperand(2))) 45b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 46b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (I->getOpcode() == Instruction::Load && I->hasOneUse()) 47b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 48b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) 49b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (BO->hasOneUse() && 50b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner (CheapToScalarize(BO->getOperand(0), isConstant) || 51b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner CheapToScalarize(BO->getOperand(1), isConstant))) 52b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 53b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (CmpInst *CI = dyn_cast<CmpInst>(I)) 54b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (CI->hasOneUse() && 55b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner (CheapToScalarize(CI->getOperand(0), isConstant) || 56b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner CheapToScalarize(CI->getOperand(1), isConstant))) 57b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 5809fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 59b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return false; 60b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 61b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 62b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner/// FindScalarElement - Given a vector and an element number, see if the scalar 63b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner/// value is already around as a register, for example if it were inserted then 64b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner/// extracted from the vector. 65b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattnerstatic Value *FindScalarElement(Value *V, unsigned EltNo) { 661df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands assert(V->getType()->isVectorTy() && "Not looking at a vector?"); 67230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner VectorType *VTy = cast<VectorType>(V->getType()); 68230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner unsigned Width = VTy->getNumElements(); 69b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (EltNo >= Width) // Out of range access. 70230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner return UndefValue::get(VTy->getElementType()); 7109fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 72230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (Constant *C = dyn_cast<Constant>(V)) 73230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner return C->getAggregateElement(EltNo); 7409fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 75d5da27186350345794b82f036d75f6d1e9bfbbbdChris Lattner if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) { 76b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this is an insert to a variable element, we don't know what it is. 7709fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson if (!isa<ConstantInt>(III->getOperand(2))) 78dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 79b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue(); 8009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 81b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this is an insert to the element we are looking for, return the 82b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // inserted value. 8309fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson if (EltNo == IIElt) 84b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return III->getOperand(1); 8509fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 86b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Otherwise, the insertelement doesn't modify the value, recurse on its 87b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // vector input. 88b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return FindScalarElement(III->getOperand(0), EltNo); 89d5da27186350345794b82f036d75f6d1e9bfbbbdChris Lattner } 9009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 91d5da27186350345794b82f036d75f6d1e9bfbbbdChris Lattner if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) { 92230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements(); 938d992f5c2c90ebc8963679de51f461dc5d54fae1Eli Friedman int InEl = SVI->getMaskValue(EltNo); 9409fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson if (InEl < 0) 95230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner return UndefValue::get(VTy->getElementType()); 96822cb58d087ab67804037807e130273481b86137Bob Wilson if (InEl < (int)LHSWidth) 97822cb58d087ab67804037807e130273481b86137Bob Wilson return FindScalarElement(SVI->getOperand(0), InEl); 98822cb58d087ab67804037807e130273481b86137Bob Wilson return FindScalarElement(SVI->getOperand(1), InEl - LHSWidth); 99b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 10009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 10183d585383345b84ae4a9590e97135f95ae39406bNadav Rotem // Extract a value from a vector add operation with a constant zero. 102dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *Val = nullptr; Constant *Con = nullptr; 10383d585383345b84ae4a9590e97135f95ae39406bNadav Rotem if (match(V, m_Add(m_Value(Val), m_Constant(Con)))) { 10483d585383345b84ae4a9590e97135f95ae39406bNadav Rotem if (Con->getAggregateElement(EltNo)->isNullValue()) 10583d585383345b84ae4a9590e97135f95ae39406bNadav Rotem return FindScalarElement(Val, EltNo); 10683d585383345b84ae4a9590e97135f95ae39406bNadav Rotem } 10783d585383345b84ae4a9590e97135f95ae39406bNadav Rotem 108b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Otherwise, we don't know. 109dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 110b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 111b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 11277e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer// If we have a PHI node with a vector type that has only 2 uses: feed 113b70d79e7e93cbca738130a71c9431e104acd317bMatt Arsenault// itself and be an operand of extractelement at a constant location, 114b70d79e7e93cbca738130a71c9431e104acd317bMatt Arsenault// try to replace the PHI of the vector type with a PHI of a scalar type. 11577e95d04c430bc849aa1898cbd820517ec0f7465Anat ShemerInstruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) { 11677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Verify that the PHI node has exactly 2 uses. Otherwise return NULL. 11777e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer if (!PN->hasNUses(2)) 118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 11977e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 12077e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // If so, it's known at this point that one operand is PHI and the other is 12177e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // an extractelement node. Find the PHI user that is not the extractelement 12277e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // node. 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines auto iu = PN->user_begin(); 12477e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer Instruction *PHIUser = dyn_cast<Instruction>(*iu); 12577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer if (PHIUser == cast<Instruction>(&EI)) 12677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer PHIUser = cast<Instruction>(*(++iu)); 12777e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 12877e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Verify that this PHI user has one use, which is the PHI itself, 12977e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // and that it is a binary operation which is cheap to scalarize. 13077e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // otherwise return NULL. 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) || 1327ab9fb02f821806de5e27d01a123260dca799575Joey Gouly !(isa<BinaryOperator>(PHIUser)) || !CheapToScalarize(PHIUser, true)) 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 13477e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 13577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Create a scalar PHI node that will replace the vector PHI node 13677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // just before the current PHI node. 1377ab9fb02f821806de5e27d01a123260dca799575Joey Gouly PHINode *scalarPHI = cast<PHINode>(InsertNewInstWith( 1387ab9fb02f821806de5e27d01a123260dca799575Joey Gouly PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN)); 13977e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Scalarize each PHI operand. 1407ab9fb02f821806de5e27d01a123260dca799575Joey Gouly for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) { 14177e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer Value *PHIInVal = PN->getIncomingValue(i); 14277e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer BasicBlock *inBB = PN->getIncomingBlock(i); 14377e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer Value *Elt = EI.getIndexOperand(); 14477e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // If the operand is the PHI induction variable: 14577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer if (PHIInVal == PHIUser) { 14677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Scalarize the binary operation. Its first operand is the 147cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // scalar PHI, and the second operand is extracted from the other 14877e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // vector operand. 14977e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer BinaryOperator *B0 = cast<BinaryOperator>(PHIUser); 1507ab9fb02f821806de5e27d01a123260dca799575Joey Gouly unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0; 1514a941316cdcfbc3671c806c9c40df1bad09ba6adJoey Gouly Value *Op = InsertNewInstWith( 1524a941316cdcfbc3671c806c9c40df1bad09ba6adJoey Gouly ExtractElementInst::Create(B0->getOperand(opId), Elt, 1534a941316cdcfbc3671c806c9c40df1bad09ba6adJoey Gouly B0->getOperand(opId)->getName() + ".Elt"), 1544a941316cdcfbc3671c806c9c40df1bad09ba6adJoey Gouly *B0); 15577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer Value *newPHIUser = InsertNewInstWith( 1567ab9fb02f821806de5e27d01a123260dca799575Joey Gouly BinaryOperator::Create(B0->getOpcode(), scalarPHI, Op), *B0); 15777e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer scalarPHI->addIncoming(newPHIUser, inBB); 15877e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer } else { 15977e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Scalarize PHI input: 1607ab9fb02f821806de5e27d01a123260dca799575Joey Gouly Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, ""); 16177e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // Insert the new instruction into the predecessor basic block. 16277e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer Instruction *pos = dyn_cast<Instruction>(PHIInVal); 16377e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer BasicBlock::iterator InsertPos; 16477e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer if (pos && !isa<PHINode>(pos)) { 16577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer InsertPos = pos; 16677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer ++InsertPos; 16777e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer } else { 16877e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer InsertPos = inBB->getFirstInsertionPt(); 16977e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer } 17077e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 17177e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer InsertNewInstWith(newEI, *InsertPos); 17277e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 17377e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer scalarPHI->addIncoming(newEI, inBB); 17477e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer } 17577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer } 17677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer return ReplaceInstUsesWith(EI, scalarPHI); 17777e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer} 17877e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 179b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris LattnerInstruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { 180230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner // If vector val is constant with all elements the same, replace EI with 181230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner // that element. We handle a known element # below. 182230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (Constant *C = dyn_cast<Constant>(EI.getOperand(0))) 183230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (CheapToScalarize(C, false)) 184230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner return ReplaceInstUsesWith(EI, C->getAggregateElement(0U)); 18509fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 186b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If extracting a specified index from the vector, see if we can recursively 187b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // find a previously computed scalar that was inserted into the vector. 188b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (ConstantInt *IdxC = dyn_cast<ConstantInt>(EI.getOperand(1))) { 189b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned IndexVal = IdxC->getZExtValue(); 190b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned VectorWidth = EI.getVectorOperandType()->getNumElements(); 19109fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 192b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this is extracting an invalid index, turn this into undef, to avoid 193b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // crashing the code below. 194b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (IndexVal >= VectorWidth) 195b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType())); 19609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 197b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // This instruction only demands the single element from the input vector. 198b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If the input vector has a single use, simplify it based on this use 199b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // property. 200b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (EI.getOperand(0)->hasOneUse() && VectorWidth != 1) { 201b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner APInt UndefElts(VectorWidth, 0); 2028609fda0f7e4446de85f882755601ffcbd540324Chris Lattner APInt DemandedMask(VectorWidth, 0); 2037a874ddda037349184fbeb22838cc11a1a9bb78fJay Foad DemandedMask.setBit(IndexVal); 204b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (Value *V = SimplifyDemandedVectorElts(EI.getOperand(0), 205b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner DemandedMask, UndefElts)) { 206b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner EI.setOperand(0, V); 207b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return &EI; 208b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 209b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 21009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 211b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (Value *Elt = FindScalarElement(EI.getOperand(0), IndexVal)) 212b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ReplaceInstUsesWith(EI, Elt); 21309fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 214b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If the this extractelement is directly using a bitcast from a vector of 215b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // the same number of elements, see if we can find the source element from 216b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // it. In this case, we will end up needing to bitcast the scalars. 217b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (BitCastInst *BCI = dyn_cast<BitCastInst>(EI.getOperand(0))) { 218230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (VectorType *VT = dyn_cast<VectorType>(BCI->getOperand(0)->getType())) 219b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (VT->getNumElements() == VectorWidth) 220b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (Value *Elt = FindScalarElement(BCI->getOperand(0), IndexVal)) 221b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return new BitCastInst(Elt, EI.getType()); 222b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 22377e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer 22477e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // If there's a vector PHI feeding a scalar use through this extractelement 22577e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer // instruction, try to scalarize the PHI. 22677e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer if (PHINode *PN = dyn_cast<PHINode>(EI.getOperand(0))) { 227cd4e5e9b34c1f155cf4495431f7cc6e10e2d390bNick Lewycky Instruction *scalarPHI = scalarizePHI(EI, PN); 228cd4e5e9b34c1f155cf4495431f7cc6e10e2d390bNick Lewycky if (scalarPHI) 2297ab9fb02f821806de5e27d01a123260dca799575Joey Gouly return scalarPHI; 23077e95d04c430bc849aa1898cbd820517ec0f7465Anat Shemer } 231b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 23209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 233b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (Instruction *I = dyn_cast<Instruction>(EI.getOperand(0))) { 234b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Push extractelement into predecessor operation if legal and 235b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // profitable to do so 236b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (BinaryOperator *BO = dyn_cast<BinaryOperator>(I)) { 237b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (I->hasOneUse() && 238b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner CheapToScalarize(BO, isa<ConstantInt>(EI.getOperand(1)))) { 239b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *newEI0 = 240db1da8ed42cbe50945acfaca514864723999150aBob Wilson Builder->CreateExtractElement(BO->getOperand(0), EI.getOperand(1), 241db1da8ed42cbe50945acfaca514864723999150aBob Wilson EI.getName()+".lhs"); 242b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *newEI1 = 243db1da8ed42cbe50945acfaca514864723999150aBob Wilson Builder->CreateExtractElement(BO->getOperand(1), EI.getOperand(1), 244db1da8ed42cbe50945acfaca514864723999150aBob Wilson EI.getName()+".rhs"); 245b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return BinaryOperator::Create(BO->getOpcode(), newEI0, newEI1); 246b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 247b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } else if (InsertElementInst *IE = dyn_cast<InsertElementInst>(I)) { 248b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Extracting the inserted element? 249b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (IE->getOperand(2) == EI.getOperand(1)) 250b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ReplaceInstUsesWith(EI, IE->getOperand(1)); 251b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If the inserted and extracted elements are constants, they must not 252b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // be the same value, extract from the pre-inserted value instead. 253b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isa<Constant>(IE->getOperand(2)) && isa<Constant>(EI.getOperand(1))) { 254b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Worklist.AddValue(EI.getOperand(0)); 255b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner EI.setOperand(0, IE->getOperand(0)); 256b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return &EI; 257b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 258b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } else if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(I)) { 259b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this is extracting an element from a shufflevector, figure out where 260b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // it came from and extract from the appropriate input element instead. 261b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (ConstantInt *Elt = dyn_cast<ConstantInt>(EI.getOperand(1))) { 2628d992f5c2c90ebc8963679de51f461dc5d54fae1Eli Friedman int SrcIdx = SVI->getMaskValue(Elt->getZExtValue()); 263b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *Src; 264b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned LHSWidth = 265230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner SVI->getOperand(0)->getType()->getVectorNumElements(); 26609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 267822cb58d087ab67804037807e130273481b86137Bob Wilson if (SrcIdx < 0) 268822cb58d087ab67804037807e130273481b86137Bob Wilson return ReplaceInstUsesWith(EI, UndefValue::get(EI.getType())); 269822cb58d087ab67804037807e130273481b86137Bob Wilson if (SrcIdx < (int)LHSWidth) 270b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Src = SVI->getOperand(0); 271822cb58d087ab67804037807e130273481b86137Bob Wilson else { 272b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner SrcIdx -= LHSWidth; 273b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Src = SVI->getOperand(1); 274b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 275db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *Int32Ty = Type::getInt32Ty(EI.getContext()); 276b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ExtractElementInst::Create(Src, 277f0b48f836e85e4e9ae3b5f94c47500d40e3dc16eBob Wilson ConstantInt::get(Int32Ty, 278b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner SrcIdx, false)); 279b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 2800ff8a4fa35db853dfc3dbe54535aa326d8e742a2Nadav Rotem } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 2810ff8a4fa35db853dfc3dbe54535aa326d8e742a2Nadav Rotem // Canonicalize extractelement(cast) -> cast(extractelement) 2820ff8a4fa35db853dfc3dbe54535aa326d8e742a2Nadav Rotem // bitcasts can change the number of vector elements and they cost nothing 28386dc3f3739eedc26f2fd1f6ade1633c1fa84bd7dAnat Shemer if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) { 284c9090b0723bdbeba65dc6b4771ca166e4a99a9ccAnat Shemer Value *EE = Builder->CreateExtractElement(CI->getOperand(0), 285c9090b0723bdbeba65dc6b4771ca166e4a99a9ccAnat Shemer EI.getIndexOperand()); 286c9090b0723bdbeba65dc6b4771ca166e4a99a9ccAnat Shemer Worklist.AddValue(EE); 2870ff8a4fa35db853dfc3dbe54535aa326d8e742a2Nadav Rotem return CastInst::Create(CI->getOpcode(), EE, EI.getType()); 2880ff8a4fa35db853dfc3dbe54535aa326d8e742a2Nadav Rotem } 289eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) { 290eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault if (SI->hasOneUse()) { 291eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault // TODO: For a select on vectors, it might be useful to do this if it 292eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault // has multiple extractelement uses. For vector select, that seems to 293eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault // fight the vectorizer. 294eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault 295eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault // If we are extracting an element from a vector select or a select on 296eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault // vectors, a select on the scalars extracted from the vector arguments. 297eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Value *TrueVal = SI->getTrueValue(); 298eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Value *FalseVal = SI->getFalseValue(); 299eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault 300eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Value *Cond = SI->getCondition(); 301eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault if (Cond->getType()->isVectorTy()) { 302eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Cond = Builder->CreateExtractElement(Cond, 303eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault EI.getIndexOperand(), 304eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Cond->getName() + ".elt"); 305eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault } 306eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault 307eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Value *V1Elem 308eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault = Builder->CreateExtractElement(TrueVal, 309eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault EI.getIndexOperand(), 310eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault TrueVal->getName() + ".elt"); 311eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault 312eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault Value *V2Elem 313eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault = Builder->CreateExtractElement(FalseVal, 314eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault EI.getIndexOperand(), 315eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault FalseVal->getName() + ".elt"); 316eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault return SelectInst::Create(Cond, 317eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault V1Elem, 318eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault V2Elem, 319eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault SI->getName() + ".elt"); 320eba6d384489be4e56718186aa7ed7e484df24613Matt Arsenault } 321b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 322b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 324b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 325b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 326b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner/// CollectSingleShuffleElements - If V is a shuffle of values that ONLY returns 32709fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson/// elements from either LHS or RHS, return the shuffle mask and true. 328b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner/// Otherwise, return false. 329b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattnerstatic bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, 330a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner SmallVectorImpl<Constant*> &Mask) { 33136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(LHS->getType() == RHS->getType() && 332b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner "Invalid CollectSingleShuffleElements"); 3334598bd53ab89c3d120ad8249abbfdc7e2d64d291Matt Arsenault unsigned NumElts = V->getType()->getVectorNumElements(); 33409fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 335b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isa<UndefValue>(V)) { 336b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext()))); 337b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 338b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 33909fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 340b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (V == LHS) { 341b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner for (unsigned i = 0; i != NumElts; ++i) 342b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i)); 343b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 344b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 34509fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 346b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (V == RHS) { 347b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner for (unsigned i = 0; i != NumElts; ++i) 348b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), 349b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner i+NumElts)); 350b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 351b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 35209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 353b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) { 354b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this is an insert of an extract from some other vector, include it. 355b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *VecOp = IEI->getOperand(0); 356b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *ScalarOp = IEI->getOperand(1); 357b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *IdxOp = IEI->getOperand(2); 35809fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 359b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (!isa<ConstantInt>(IdxOp)) 360b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return false; 361b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); 36209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 363b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isa<UndefValue>(ScalarOp)) { // inserting undef into vector. 364cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // We can handle this if the vector we are inserting into is 365b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // transitively ok. 366b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) { 367b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If so, update the mask to reflect the inserted undef. 368b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask[InsertedIdx] = UndefValue::get(Type::getInt32Ty(V->getContext())); 369b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 37009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson } 371b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } else if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)){ 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<ConstantInt>(EI->getOperand(1))) { 373b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned ExtractedIdx = 374b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); 37536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumLHSElts = LHS->getType()->getVectorNumElements(); 37609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 377b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // This must be extracting from either LHS or RHS. 378b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) { 379cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // We can handle this if the vector we are inserting into is 380b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // transitively ok. 381b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (CollectSingleShuffleElements(VecOp, LHS, RHS, Mask)) { 382b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If so, update the mask to reflect the inserted value. 383b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (EI->getOperand(0) == LHS) { 38409fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson Mask[InsertedIdx % NumElts] = 385b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner ConstantInt::get(Type::getInt32Ty(V->getContext()), 386b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner ExtractedIdx); 387b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } else { 388b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner assert(EI->getOperand(0) == RHS); 38909fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson Mask[InsertedIdx % NumElts] = 390b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner ConstantInt::get(Type::getInt32Ty(V->getContext()), 39136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ExtractedIdx + NumLHSElts); 392b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 393b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return true; 394b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 395b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 396b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 397b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 398b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 39909fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 400b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return false; 401b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 402b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 40336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 40436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// We are building a shuffle to create V, which is a sequence of insertelement, 40536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// extractelement pairs. If PermittedRHS is set, then we must either use it or 406cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines/// not rely on the second vector source. Return a std::pair containing the 40736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// left and right vectors of the proposed shuffle (or 0), and set the Mask 40836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// parameter as required. 40936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// 41036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Note: we intentionally don't try to fold earlier shuffles since they have 41136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// often been chosen carefully to be efficiently implementable on the target. 41236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinestypedef std::pair<Value *, Value *> ShuffleOps; 41336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 41436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic ShuffleOps CollectShuffleElements(Value *V, 41536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVectorImpl<Constant *> &Mask, 41636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *PermittedRHS) { 41736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(V->getType()->isVectorTy() && "Invalid shuffle!"); 418b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned NumElts = cast<VectorType>(V->getType())->getNumElements(); 41909fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 420b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isa<UndefValue>(V)) { 421b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext()))); 42236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair( 42336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr); 424bec2d03c4d774e67ebc586b3a00792d996f26140Chris Lattner } 42537d093f0b0e4b4d1c49efbf2bdcc9827527e3b9fCraig Topper 426bec2d03c4d774e67ebc586b3a00792d996f26140Chris Lattner if (isa<ConstantAggregateZero>(V)) { 427b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0)); 42836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(V, nullptr); 429bec2d03c4d774e67ebc586b3a00792d996f26140Chris Lattner } 43037d093f0b0e4b4d1c49efbf2bdcc9827527e3b9fCraig Topper 431bec2d03c4d774e67ebc586b3a00792d996f26140Chris Lattner if (InsertElementInst *IEI = dyn_cast<InsertElementInst>(V)) { 432b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this is an insert of an extract from some other vector, include it. 433b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *VecOp = IEI->getOperand(0); 434b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *ScalarOp = IEI->getOperand(1); 435b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *IdxOp = IEI->getOperand(2); 43609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 437b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) { 43836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) { 439b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned ExtractedIdx = 440db1da8ed42cbe50945acfaca514864723999150aBob Wilson cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); 441b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); 44209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 443b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Either the extracted from or inserted into vector must be RHSVec, 444b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // otherwise we'd end up with a shuffle of three inputs. 445dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (EI->getOperand(0) == PermittedRHS || PermittedRHS == nullptr) { 44636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *RHS = EI->getOperand(0); 44736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ShuffleOps LR = CollectShuffleElements(VecOp, Mask, RHS); 448dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines assert(LR.second == nullptr || LR.second == RHS); 44936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 45036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (LR.first->getType() != RHS->getType()) { 45136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We tried our best, but we can't find anything compatible with RHS 45236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // further up the chain. Return a trivial shuffle. 45336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned i = 0; i < NumElts; ++i) 45436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i); 45536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(V, nullptr); 45636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 45736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 45836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumLHSElts = RHS->getType()->getVectorNumElements(); 45909fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson Mask[InsertedIdx % NumElts] = 460db1da8ed42cbe50945acfaca514864723999150aBob Wilson ConstantInt::get(Type::getInt32Ty(V->getContext()), 46136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NumLHSElts+ExtractedIdx); 46236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(LR.first, RHS); 463b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 46409fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 46536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (VecOp == PermittedRHS) { 46636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We've gone as far as we can: anything on the other side of the 46736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // extractelement will already have been converted into a shuffle. 46836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumLHSElts = 46936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EI->getOperand(0)->getType()->getVectorNumElements(); 47036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned i = 0; i != NumElts; ++i) 47136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Mask.push_back(ConstantInt::get( 47236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Type::getInt32Ty(V->getContext()), 47336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines i == InsertedIdx ? ExtractedIdx : NumLHSElts + i)); 47436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(EI->getOperand(0), PermittedRHS); 475b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 47609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 477b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this insertelement is a chain that comes from exactly these two 478b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // vectors, return the vector and the effective shuffle. 47936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (EI->getOperand(0)->getType() == PermittedRHS->getType() && 48036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines CollectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS, 48136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Mask)) 48236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(EI->getOperand(0), PermittedRHS); 483b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 484b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 485b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 48609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 487b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Otherwise, can't do anything fancy. Return an identity vector. 488b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner for (unsigned i = 0; i != NumElts; ++i) 489b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i)); 49036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return std::make_pair(V, nullptr); 491b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 492b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 493dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Try to find redundant insertvalue instructions, like the following ones: 494dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// %0 = insertvalue { i8, i32 } undef, i8 %x, 0 495dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// %1 = insertvalue { i8, i32 } %0, i8 %y, 0 496dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// Here the second instruction inserts values at the same indices, as the 497dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// first one, making the first one redundant. 498dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// It should be transformed to: 499dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines/// %0 = insertvalue { i8, i32 } undef, i8 %y, 0 500dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesInstruction *InstCombiner::visitInsertValueInst(InsertValueInst &I) { 501dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool IsRedundant = false; 502dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ArrayRef<unsigned int> FirstIndices = I.getIndices(); 503dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 504dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If there is a chain of insertvalue instructions (each of them except the 505dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // last one has only one use and it's another insertvalue insn from this 506dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // chain), check if any of the 'children' uses the same indices as the first 507dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // instruction. In this case, the first one is redundant. 508dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value *V = &I; 509dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines unsigned Depth = 0; 510dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines while (V->hasOneUse() && Depth < 10) { 511dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines User *U = V->user_back(); 512dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines auto UserInsInst = dyn_cast<InsertValueInst>(U); 513dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!UserInsInst || U->getOperand(0) != V) 514dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 515dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (UserInsInst->getIndices() == FirstIndices) { 516dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines IsRedundant = true; 517dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines break; 518dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 519dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines V = UserInsInst; 520dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Depth++; 521dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 522dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 523dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (IsRedundant) 524dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return ReplaceInstUsesWith(I, I.getOperand(0)); 525dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 526dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 527dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 528b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris LattnerInstruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { 529b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *VecOp = IE.getOperand(0); 530b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *ScalarOp = IE.getOperand(1); 531b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *IdxOp = IE.getOperand(2); 53209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 533b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Inserting an undef or into an undefined place, remove this. 534b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isa<UndefValue>(ScalarOp) || isa<UndefValue>(IdxOp)) 535b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner ReplaceInstUsesWith(IE, VecOp); 53609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 53709fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson // If the inserted element was extracted from some other vector, and if the 538b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // indexes are constant, try to turn this into a shufflevector operation. 539b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (ExtractElementInst *EI = dyn_cast<ExtractElementInst>(ScalarOp)) { 54036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<ConstantInt>(EI->getOperand(1)) && isa<ConstantInt>(IdxOp)) { 54136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumInsertVectorElts = IE.getType()->getNumElements(); 54236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines unsigned NumExtractVectorElts = 54336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines EI->getOperand(0)->getType()->getVectorNumElements(); 544b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned ExtractedIdx = 545db1da8ed42cbe50945acfaca514864723999150aBob Wilson cast<ConstantInt>(EI->getOperand(1))->getZExtValue(); 546b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned InsertedIdx = cast<ConstantInt>(IdxOp)->getZExtValue(); 54709fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 54836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract. 549b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ReplaceInstUsesWith(IE, VecOp); 55009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 55136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InsertedIdx >= NumInsertVectorElts) // Out of range insert. 552b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType())); 55309fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 554b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If we are extracting a value from a vector, then inserting it right 555b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // back into the same place, just use the input vector. 556b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (EI->getOperand(0) == VecOp && ExtractedIdx == InsertedIdx) 55709fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson return ReplaceInstUsesWith(IE, VecOp); 55809fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 559b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // If this insertelement isn't used by some other insertelement, turn it 560b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // (and any insertelements it points to), into one big shuffle. 56136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!IE.hasOneUse() || !isa<InsertElementInst>(IE.user_back())) { 562a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner SmallVector<Constant*, 16> Mask; 563dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines ShuffleOps LR = CollectShuffleElements(&IE, Mask, nullptr); 56436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 56536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The proposed shuffle may be trivial, in which case we shouldn't 56636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // perform the combine. 56736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (LR.first != &IE && LR.second != &IE) { 56836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // We now have a shuffle of LHS, RHS, Mask. 569dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (LR.second == nullptr) 570dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LR.second = UndefValue::get(LR.first->getType()); 57136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return new ShuffleVectorInst(LR.first, LR.second, 57236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ConstantVector::get(Mask)); 57336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 574b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 575b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 576b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 57709fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 578b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner unsigned VWidth = cast<VectorType>(VecOp->getType())->getNumElements(); 579b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner APInt UndefElts(VWidth, 0); 580b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); 5811347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman if (Value *V = SimplifyDemandedVectorElts(&IE, AllOnesEltMask, UndefElts)) { 5821347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman if (V != &IE) 5831347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman return ReplaceInstUsesWith(IE, V); 584b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return &IE; 5851347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman } 58609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 587dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return nullptr; 588b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 589b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 590903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky/// Return true if we can evaluate the specified expression tree if the vector 591903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky/// elements were shuffled in a different order. 592903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewyckystatic bool CanEvaluateShuffled(Value *V, ArrayRef<int> Mask, 593e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky unsigned Depth = 5) { 594903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // We can always reorder the elements of a constant. 595903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (isa<Constant>(V)) 596903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return true; 597903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 598903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // We won't reorder vector arguments. No IPO here. 599903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Instruction *I = dyn_cast<Instruction>(V); 600903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (!I) return false; 601903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 602903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // Two users may expect different orders of the elements. Don't try it. 603903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (!I->hasOneUse()) 604903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return false; 605903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 606903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (Depth == 0) return false; 607903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 608903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky switch (I->getOpcode()) { 609903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Add: 610903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FAdd: 611903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Sub: 612903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FSub: 613903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Mul: 614903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FMul: 615903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::UDiv: 616903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SDiv: 617903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FDiv: 618903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::URem: 619903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SRem: 620903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FRem: 621903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Shl: 622903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::LShr: 623903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::AShr: 624903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::And: 625903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Or: 626903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Xor: 627903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::ICmp: 628903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FCmp: 629903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Trunc: 630903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::ZExt: 631903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SExt: 632903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPToUI: 633903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPToSI: 634903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::UIToFP: 635903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SIToFP: 636903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPTrunc: 637903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPExt: 638903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::GetElementPtr: { 639903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky for (int i = 0, e = I->getNumOperands(); i != e; ++i) { 640903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (!CanEvaluateShuffled(I->getOperand(i), Mask, Depth-1)) 641903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return false; 642903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 643903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return true; 644903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 645903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::InsertElement: { 646903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(2)); 647903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (!CI) return false; 648903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky int ElementNumber = CI->getLimitedValue(); 649903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 650903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // Verify that 'CI' does not occur twice in Mask. A single 'insertelement' 651903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // can't put an element into multiple indices. 652903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky bool SeenOnce = false; 653903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky for (int i = 0, e = Mask.size(); i != e; ++i) { 654903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (Mask[i] == ElementNumber) { 655903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (SeenOnce) 656903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return false; 657903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky SeenOnce = true; 658903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 659903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 660903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1); 661903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 662903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 663903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return false; 664903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky} 665903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 666903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky/// Rebuild a new instruction just like 'I' but with the new operands given. 667903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky/// In the event of type mismatch, the type of the operands is correct. 668903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewyckystatic Value *BuildNew(Instruction *I, ArrayRef<Value*> NewOps) { 669903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // We don't want to use the IRBuilder here because we want the replacement 670903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // instructions to appear next to 'I', not the builder's insertion point. 671903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky switch (I->getOpcode()) { 672903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Add: 673903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FAdd: 674903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Sub: 675903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FSub: 676903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Mul: 677903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FMul: 678903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::UDiv: 679903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SDiv: 680903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FDiv: 681903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::URem: 682903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SRem: 683903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FRem: 684903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Shl: 685903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::LShr: 686903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::AShr: 687903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::And: 688903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Or: 689903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Xor: { 690903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky BinaryOperator *BO = cast<BinaryOperator>(I); 691903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky assert(NewOps.size() == 2 && "binary operator with #ops != 2"); 692903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky BinaryOperator *New = 693903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky BinaryOperator::Create(cast<BinaryOperator>(I)->getOpcode(), 694903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky NewOps[0], NewOps[1], "", BO); 695903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (isa<OverflowingBinaryOperator>(BO)) { 696903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap()); 697903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky New->setHasNoSignedWrap(BO->hasNoSignedWrap()); 698903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 699903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (isa<PossiblyExactOperator>(BO)) { 700903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky New->setIsExact(BO->isExact()); 701903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 70236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<FPMathOperator>(BO)) 70336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines New->copyFastMathFlags(I); 704903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return New; 705903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 706903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::ICmp: 707903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky assert(NewOps.size() == 2 && "icmp with #ops != 2"); 708903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return new ICmpInst(I, cast<ICmpInst>(I)->getPredicate(), 709903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky NewOps[0], NewOps[1]); 710903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FCmp: 711903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky assert(NewOps.size() == 2 && "fcmp with #ops != 2"); 712903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return new FCmpInst(I, cast<FCmpInst>(I)->getPredicate(), 713903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky NewOps[0], NewOps[1]); 714903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Trunc: 715903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::ZExt: 716903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SExt: 717903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPToUI: 718903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPToSI: 719903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::UIToFP: 720903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SIToFP: 721903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPTrunc: 722903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPExt: { 723903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // It's possible that the mask has a different number of elements from 724903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // the original cast. We recompute the destination type to match the mask. 725903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Type *DestTy = 726903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky VectorType::get(I->getType()->getScalarType(), 727903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky NewOps[0]->getType()->getVectorNumElements()); 728903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky assert(NewOps.size() == 1 && "cast with #ops != 1"); 729903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return CastInst::Create(cast<CastInst>(I)->getOpcode(), NewOps[0], DestTy, 730903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky "", I); 731903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 732903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::GetElementPtr: { 733903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Value *Ptr = NewOps[0]; 734903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky ArrayRef<Value*> Idx = NewOps.slice(1); 735903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky GetElementPtrInst *GEP = GetElementPtrInst::Create(Ptr, Idx, "", I); 736903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky GEP->setIsInBounds(cast<GetElementPtrInst>(I)->isInBounds()); 737903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return GEP; 738903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 739903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 740903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky llvm_unreachable("failed to rebuild vector instructions"); 741903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky} 742903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 743903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick LewyckyValue * 744903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick LewyckyInstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef<int> Mask) { 745903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // Mask.size() does not need to be equal to the number of vector elements. 746903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 747903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky assert(V->getType()->isVectorTy() && "can't reorder non-vector elements"); 748903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (isa<UndefValue>(V)) { 749903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return UndefValue::get(VectorType::get(V->getType()->getScalarType(), 750903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Mask.size())); 751903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 752903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (isa<ConstantAggregateZero>(V)) { 753903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return ConstantAggregateZero::get( 754903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky VectorType::get(V->getType()->getScalarType(), 755903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Mask.size())); 756903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 757903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (Constant *C = dyn_cast<Constant>(V)) { 758903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky SmallVector<Constant *, 16> MaskValues; 759903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky for (int i = 0, e = Mask.size(); i != e; ++i) { 760903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (Mask[i] == -1) 761903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky MaskValues.push_back(UndefValue::get(Builder->getInt32Ty())); 762903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky else 763903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky MaskValues.push_back(Builder->getInt32(Mask[i])); 764903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 765903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()), 766903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky ConstantVector::get(MaskValues)); 767903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 768903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 769903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Instruction *I = cast<Instruction>(V); 770903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky switch (I->getOpcode()) { 771903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Add: 772903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FAdd: 773903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Sub: 774903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FSub: 775903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Mul: 776903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FMul: 777903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::UDiv: 778903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SDiv: 779903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FDiv: 780903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::URem: 781903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SRem: 782903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FRem: 783903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Shl: 784903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::LShr: 785903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::AShr: 786903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::And: 787903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Or: 788903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Xor: 789903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::ICmp: 790903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FCmp: 791903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Trunc: 792903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::ZExt: 793903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SExt: 794903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPToUI: 795903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPToSI: 796903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::UIToFP: 797903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::SIToFP: 798903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPTrunc: 799903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::FPExt: 800903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::Select: 801903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::GetElementPtr: { 802903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky SmallVector<Value*, 8> NewOps; 803903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements()); 804903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky for (int i = 0, e = I->getNumOperands(); i != e; ++i) { 805903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask); 806903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky NewOps.push_back(V); 807903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky NeedsRebuild |= (V != I->getOperand(i)); 808903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 809903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky if (NeedsRebuild) { 810903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return BuildNew(I, NewOps); 811903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 812903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return I; 813903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 814903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky case Instruction::InsertElement: { 815903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky int Element = cast<ConstantInt>(I->getOperand(2))->getLimitedValue(); 816903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 817903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // The insertelement was inserting at Element. Figure out which element 818903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // that becomes after shuffling. The answer is guaranteed to be unique 819903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky // by CanEvaluateShuffled. 820e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky bool Found = false; 821903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky int Index = 0; 822e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky for (int e = Mask.size(); Index != e; ++Index) { 823e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky if (Mask[Index] == Element) { 824e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky Found = true; 825903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky break; 826e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky } 827e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky } 828903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 82936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If element is not in Mask, no need to handle the operand 1 (element to 83036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // be inserted). Just evaluate values in operand 0 according to Mask. 831e4546cb71e14baa0cde8f85a12cfa8b2d44fe708Nick Lewycky if (!Found) 83236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return EvaluateInDifferentElementOrder(I->getOperand(0), Mask); 833ebe11477225cc2793b43073bddc17f484839e006Joey Gouly 834903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask); 835903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return InsertElementInst::Create(V, I->getOperand(1), 836903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Builder->getInt32(Index), "", I); 837903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 838903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 839903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky llvm_unreachable("failed to reorder elements of vector instruction!"); 840903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky} 841b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner 842dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesstatic void RecognizeIdentityMask(const SmallVectorImpl<int> &Mask, 843dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool &isLHSID, bool &isRHSID) { 844dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isLHSID = isRHSID = true; 845dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 846dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines for (unsigned i = 0, e = Mask.size(); i != e; ++i) { 847dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (Mask[i] < 0) continue; // Ignore undef values. 848dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Is this an identity shuffle of the LHS value? 849dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isLHSID &= (Mask[i] == (int)i); 850dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 851dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // Is this an identity shuffle of the RHS value? 852dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isRHSID &= (Mask[i]-e == i); 853dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 854dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 855dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 856b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris LattnerInstruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { 857b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *LHS = SVI.getOperand(0); 858b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Value *RHS = SVI.getOperand(1); 859230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner SmallVector<int, 16> Mask = SVI.getShuffleMask(); 86009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 861b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner bool MadeChange = false; 86209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 863b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Undefined shuffle mask -> undefined value. 864b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (isa<UndefValue>(SVI.getOperand(2))) 865b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner return ReplaceInstUsesWith(SVI, UndefValue::get(SVI.getType())); 86609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 86768c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher unsigned VWidth = cast<VectorType>(SVI.getType())->getNumElements(); 86809fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 869b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner APInt UndefElts(VWidth, 0); 870b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner APInt AllOnesEltMask(APInt::getAllOnesValue(VWidth)); 8711347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman if (Value *V = SimplifyDemandedVectorElts(&SVI, AllOnesEltMask, UndefElts)) { 8721347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman if (V != &SVI) 8731347623aaf25b7fe6486479353fc87bd7541a5f7Eli Friedman return ReplaceInstUsesWith(SVI, V); 874b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner LHS = SVI.getOperand(0); 875b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner RHS = SVI.getOperand(1); 876b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner MadeChange = true; 877b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 87809fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 879d2822e7572e75287db66acb14b2d988a80faebddEli Friedman unsigned LHSWidth = cast<VectorType>(LHS->getType())->getNumElements(); 880d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 881b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Canonicalize shuffle(x ,x,mask) -> shuffle(x, undef,mask') 882b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Canonicalize shuffle(undef,x,mask) -> shuffle(x, undef,mask'). 883b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner if (LHS == RHS || isa<UndefValue>(LHS)) { 88468c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher if (isa<UndefValue>(LHS) && LHS == RHS) { 88568c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher // shuffle(undef,undef,mask) -> undef. 886903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Value *Result = (VWidth == LHSWidth) 887d2822e7572e75287db66acb14b2d988a80faebddEli Friedman ? LHS : UndefValue::get(SVI.getType()); 888903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return ReplaceInstUsesWith(SVI, Result); 88968c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher } 89009fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 891b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner // Remap any references to RHS to use LHS. 892a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner SmallVector<Constant*, 16> Elts; 893d2822e7572e75287db66acb14b2d988a80faebddEli Friedman for (unsigned i = 0, e = LHSWidth; i != VWidth; ++i) { 894a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if (Mask[i] < 0) { 895b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext()))); 896a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner continue; 897a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner } 898a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner 899a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner if ((Mask[i] >= (int)e && isa<UndefValue>(RHS)) || 900a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner (Mask[i] < (int)e && isa<UndefValue>(LHS))) { 901a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Mask[i] = -1; // Turn into undef. 902a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Elts.push_back(UndefValue::get(Type::getInt32Ty(SVI.getContext()))); 903a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner } else { 904a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Mask[i] = Mask[i] % e; // Force to LHS. 905a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Elts.push_back(ConstantInt::get(Type::getInt32Ty(SVI.getContext()), 906a78fa8cc2dd6d2ffe5e4fe605f38aae7b3d2fb7aChris Lattner Mask[i])); 907b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 908b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 909b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner SVI.setOperand(0, SVI.getOperand(1)); 910b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner SVI.setOperand(1, UndefValue::get(RHS->getType())); 911b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner SVI.setOperand(2, ConstantVector::get(Elts)); 912b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner LHS = SVI.getOperand(0); 913b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner RHS = SVI.getOperand(1); 914b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner MadeChange = true; 915b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner } 91609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 917d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (VWidth == LHSWidth) { 918d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // Analyze the shuffle, are the LHS or RHS and identity shuffles? 919dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool isLHSID, isRHSID; 920dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RecognizeIdentityMask(Mask, isLHSID, isRHSID); 92109fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 922d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // Eliminate identity shuffles. 923d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (isLHSID) return ReplaceInstUsesWith(SVI, LHS); 924d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (isRHSID) return ReplaceInstUsesWith(SVI, RHS); 92595743d8748a85bbb03aff3b3baae728c138acbabNate Begeman } 92609fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 9274526d1cd4a4238f67710f98a1e44688b99fc3ba7Nick Lewycky if (isa<UndefValue>(RHS) && CanEvaluateShuffled(LHS, Mask)) { 928903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky Value *V = EvaluateInDifferentElementOrder(LHS, Mask); 929903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky return ReplaceInstUsesWith(SVI, V); 930903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky } 931903f26d904cb7eba9b57ed85b2dc6147a8811bd7Nick Lewycky 93268c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher // If the LHS is a shufflevector itself, see if we can combine it with this 933d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // one without producing an unusual shuffle. 934d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // Cases that might be simplified: 935d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // 1. 936d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x1=shuffle(v1,v2,mask1) 937d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(x1,undef,mask) 938d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ==> 939d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(v1,undef,newMask) 940d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : -1 941d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // 2. 942d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x1=shuffle(v1,undef,mask1) 943d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(x1,x2,mask) 944d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // where v1.size() == mask1.size() 945d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ==> 946d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(v1,x2,newMask) 947d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // newMask[i] = (mask[i] < x1.size()) ? mask1[mask[i]] : mask[i] 948d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // 3. 949d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x2=shuffle(v2,undef,mask2) 950d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(x1,x2,mask) 951d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // where v2.size() == mask2.size() 952d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ==> 953d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(x1,v2,newMask) 954d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // newMask[i] = (mask[i] < x1.size()) 955d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ? mask[i] : mask2[mask[i]-x1.size()]+x1.size() 956d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // 4. 957d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x1=shuffle(v1,undef,mask1) 958d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x2=shuffle(v2,undef,mask2) 959d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(x1,x2,mask) 960d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // where v1.size() == v2.size() 961d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ==> 962d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // x=shuffle(v1,v2,newMask) 963d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // newMask[i] = (mask[i] < x1.size()) 964d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ? mask1[mask[i]] : mask2[mask[i]-x1.size()]+v1.size() 965d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // 966d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // Here we are really conservative: 96768c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher // we are absolutely afraid of producing a shuffle mask not in the input 96868c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher // program, because the code gen may not be smart enough to turn a merged 96968c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher // shuffle into two specific shuffles: it may produce worse code. As such, 97010cc563bfe330cf4118b2f0db6706c244e77ebb3Jim Grosbach // we only merge two shuffles if the result is either a splat or one of the 97110cc563bfe330cf4118b2f0db6706c244e77ebb3Jim Grosbach // input shuffle masks. In this case, merging the shuffles just removes 97210cc563bfe330cf4118b2f0db6706c244e77ebb3Jim Grosbach // one instruction, which we know is safe. This is good for things like 973d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // turning: (splat(splat)) -> splat, or 974d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // merge(V[0..n], V[n+1..2n]) -> V[0..2n] 975d2822e7572e75287db66acb14b2d988a80faebddEli Friedman ShuffleVectorInst* LHSShuffle = dyn_cast<ShuffleVectorInst>(LHS); 976d2822e7572e75287db66acb14b2d988a80faebddEli Friedman ShuffleVectorInst* RHSShuffle = dyn_cast<ShuffleVectorInst>(RHS); 977d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (LHSShuffle) 978d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (!isa<UndefValue>(LHSShuffle->getOperand(1)) && !isa<UndefValue>(RHS)) 979dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LHSShuffle = nullptr; 980d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (RHSShuffle) 981d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (!isa<UndefValue>(RHSShuffle->getOperand(1))) 982dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RHSShuffle = nullptr; 983d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (!LHSShuffle && !RHSShuffle) 984dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return MadeChange ? &SVI : nullptr; 985d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 986dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value* LHSOp0 = nullptr; 987dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value* LHSOp1 = nullptr; 988dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Value* RHSOp0 = nullptr; 989d2822e7572e75287db66acb14b2d988a80faebddEli Friedman unsigned LHSOp0Width = 0; 990d2822e7572e75287db66acb14b2d988a80faebddEli Friedman unsigned RHSOp0Width = 0; 991d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (LHSShuffle) { 992d2822e7572e75287db66acb14b2d988a80faebddEli Friedman LHSOp0 = LHSShuffle->getOperand(0); 993d2822e7572e75287db66acb14b2d988a80faebddEli Friedman LHSOp1 = LHSShuffle->getOperand(1); 994d2822e7572e75287db66acb14b2d988a80faebddEli Friedman LHSOp0Width = cast<VectorType>(LHSOp0->getType())->getNumElements(); 995d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 996d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (RHSShuffle) { 997d2822e7572e75287db66acb14b2d988a80faebddEli Friedman RHSOp0 = RHSShuffle->getOperand(0); 998d2822e7572e75287db66acb14b2d988a80faebddEli Friedman RHSOp0Width = cast<VectorType>(RHSOp0->getType())->getNumElements(); 999d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1000d2822e7572e75287db66acb14b2d988a80faebddEli Friedman Value* newLHS = LHS; 1001d2822e7572e75287db66acb14b2d988a80faebddEli Friedman Value* newRHS = RHS; 1002d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (LHSShuffle) { 1003d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // case 1 100468c23f861694f7b06df2ce39ced01d1d39fc5809Eric Christopher if (isa<UndefValue>(RHS)) { 1005d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newLHS = LHSOp0; 1006d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newRHS = LHSOp1; 1007d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1008d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // case 2 or 4 1009d2822e7572e75287db66acb14b2d988a80faebddEli Friedman else if (LHSOp0Width == LHSWidth) { 1010d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newLHS = LHSOp0; 1011d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1012d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1013d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // case 3 or 4 1014d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (RHSShuffle && RHSOp0Width == LHSWidth) { 1015d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newRHS = RHSOp0; 1016d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1017d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // case 4 1018d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (LHSOp0 == RHSOp0) { 1019d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newLHS = LHSOp0; 1020dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines newRHS = nullptr; 1021d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 102209fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 1023d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (newLHS == LHS && newRHS == RHS) 1024dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return MadeChange ? &SVI : nullptr; 1025d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 1026d2822e7572e75287db66acb14b2d988a80faebddEli Friedman SmallVector<int, 16> LHSMask; 1027d2822e7572e75287db66acb14b2d988a80faebddEli Friedman SmallVector<int, 16> RHSMask; 1028230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (newLHS != LHS) 1029230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner LHSMask = LHSShuffle->getShuffleMask(); 1030230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner if (RHSShuffle && newRHS != RHS) 1031230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner RHSMask = RHSShuffle->getShuffleMask(); 1032230cdab2205d051cc11c565b69ca8c2106904a76Chris Lattner 1033d2822e7572e75287db66acb14b2d988a80faebddEli Friedman unsigned newLHSWidth = (newLHS != LHS) ? LHSOp0Width : LHSWidth; 1034d2822e7572e75287db66acb14b2d988a80faebddEli Friedman SmallVector<int, 16> newMask; 1035d2822e7572e75287db66acb14b2d988a80faebddEli Friedman bool isSplat = true; 1036d2822e7572e75287db66acb14b2d988a80faebddEli Friedman int SplatElt = -1; 1037d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // Create a new mask for the new ShuffleVectorInst so that the new 1038d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // ShuffleVectorInst is equivalent to the original one. 1039d2822e7572e75287db66acb14b2d988a80faebddEli Friedman for (unsigned i = 0; i < VWidth; ++i) { 1040d2822e7572e75287db66acb14b2d988a80faebddEli Friedman int eltMask; 1041081c29b25696006bb72a7ac1035e05f8f935513fCraig Topper if (Mask[i] < 0) { 1042d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // This element is an undef value. 1043d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = -1; 1044d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } else if (Mask[i] < (int)LHSWidth) { 1045d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // This element is from left hand side vector operand. 104637d093f0b0e4b4d1c49efbf2bdcc9827527e3b9fCraig Topper // 1047d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If LHS is going to be replaced (case 1, 2, or 4), calculate the 1048d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // new mask value for the element. 1049d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (newLHS != LHS) { 1050d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = LHSMask[Mask[i]]; 1051d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If the value selected is an undef value, explicitly specify it 1052d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // with a -1 mask value. 1053d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (eltMask >= (int)LHSOp0Width && isa<UndefValue>(LHSOp1)) 1054d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = -1; 105537d093f0b0e4b4d1c49efbf2bdcc9827527e3b9fCraig Topper } else 1056d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = Mask[i]; 1057d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } else { 1058d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // This element is from right hand side vector operand 1059d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // 1060d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If the value selected is an undef value, explicitly specify it 1061d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // with a -1 mask value. (case 1) 1062d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (isa<UndefValue>(RHS)) 1063d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = -1; 1064d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If RHS is going to be replaced (case 3 or 4), calculate the 1065d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // new mask value for the element. 1066d2822e7572e75287db66acb14b2d988a80faebddEli Friedman else if (newRHS != RHS) { 1067d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = RHSMask[Mask[i]-LHSWidth]; 1068d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If the value selected is an undef value, explicitly specify it 1069d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // with a -1 mask value. 1070d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (eltMask >= (int)RHSOp0Width) { 1071d2822e7572e75287db66acb14b2d988a80faebddEli Friedman assert(isa<UndefValue>(RHSShuffle->getOperand(1)) 1072d2822e7572e75287db66acb14b2d988a80faebddEli Friedman && "should have been check above"); 1073d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = -1; 10747f1f4089a142e4f0081ac25699bf682a68247a35Nate Begeman } 107537d093f0b0e4b4d1c49efbf2bdcc9827527e3b9fCraig Topper } else 1076d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask = Mask[i]-LHSWidth; 1077d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 1078d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If LHS's width is changed, shift the mask value accordingly. 1079d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If newRHS == NULL, i.e. LHSOp0 == RHSOp0, we want to remap any 10804932bbe20c4b96552dcab332503b80ff3b56ad93Michael Gottesman // references from RHSOp0 to LHSOp0, so we don't need to shift the mask. 10814932bbe20c4b96552dcab332503b80ff3b56ad93Michael Gottesman // If newRHS == newLHS, we want to remap any references from newRHS to 10824932bbe20c4b96552dcab332503b80ff3b56ad93Michael Gottesman // newLHS so that we can properly identify splats that may occur due to 108336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // obfuscation across the two vectors. 1084dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (eltMask >= 0 && newRHS != nullptr && newLHS != newRHS) 1085d2822e7572e75287db66acb14b2d988a80faebddEli Friedman eltMask += newLHSWidth; 1086d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1087d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 1088d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // Check if this could still be a splat. 1089d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (eltMask >= 0) { 1090d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (SplatElt >= 0 && SplatElt != eltMask) 1091d2822e7572e75287db66acb14b2d988a80faebddEli Friedman isSplat = false; 1092d2822e7572e75287db66acb14b2d988a80faebddEli Friedman SplatElt = eltMask; 1093d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1094d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 1095d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newMask.push_back(eltMask); 1096d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 1097d2822e7572e75287db66acb14b2d988a80faebddEli Friedman 1098d2822e7572e75287db66acb14b2d988a80faebddEli Friedman // If the result mask is equal to one of the original shuffle masks, 109910cc563bfe330cf4118b2f0db6706c244e77ebb3Jim Grosbach // or is a splat, do the replacement. 110010cc563bfe330cf4118b2f0db6706c244e77ebb3Jim Grosbach if (isSplat || newMask == LHSMask || newMask == RHSMask || newMask == Mask) { 1101d2822e7572e75287db66acb14b2d988a80faebddEli Friedman SmallVector<Constant*, 16> Elts; 1102d2822e7572e75287db66acb14b2d988a80faebddEli Friedman Type *Int32Ty = Type::getInt32Ty(SVI.getContext()); 1103d2822e7572e75287db66acb14b2d988a80faebddEli Friedman for (unsigned i = 0, e = newMask.size(); i != e; ++i) { 1104d2822e7572e75287db66acb14b2d988a80faebddEli Friedman if (newMask[i] < 0) { 1105d2822e7572e75287db66acb14b2d988a80faebddEli Friedman Elts.push_back(UndefValue::get(Int32Ty)); 1106d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } else { 1107d2822e7572e75287db66acb14b2d988a80faebddEli Friedman Elts.push_back(ConstantInt::get(Int32Ty, newMask[i])); 1108d2822e7572e75287db66acb14b2d988a80faebddEli Friedman } 11097f1f4089a142e4f0081ac25699bf682a68247a35Nate Begeman } 1110dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!newRHS) 1111d2822e7572e75287db66acb14b2d988a80faebddEli Friedman newRHS = UndefValue::get(newLHS->getType()); 1112d2822e7572e75287db66acb14b2d988a80faebddEli Friedman return new ShuffleVectorInst(newLHS, newRHS, ConstantVector::get(Elts)); 11137f1f4089a142e4f0081ac25699bf682a68247a35Nate Begeman } 111409fd64644d5da2dacc0916790082ac0dd5d9696dBob Wilson 1115dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // If the result mask is an identity, replace uses of this instruction with 1116dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // corresponding argument. 1117dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool isLHSID, isRHSID; 1118dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines RecognizeIdentityMask(newMask, isLHSID, isRHSID); 1119dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isLHSID && VWidth == LHSOp0Width) return ReplaceInstUsesWith(SVI, newLHS); 1120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (isRHSID && VWidth == RHSOp0Width) return ReplaceInstUsesWith(SVI, newRHS); 1121dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 1122dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return MadeChange ? &SVI : nullptr; 1123b8a5cecd6bc74d6c1c256263f857f79f383e53bdChris Lattner} 1124