X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FInstCombine%2FInstCombineVectorOps.cpp;h=12837eed16812e74ee441e5e5124d873a4d0798e;hb=96363d50018da6e9cfa549695f01aa0d4d2d6a31;hp=bbfad8693ebc3b3ed8ccd0c030fc07f9005de93c;hpb=c37cb66e6ee256bcb3ba138383e4cb9aab55ddb9;p=oota-llvm.git diff --git a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp index bbfad8693eb..12837eed168 100644 --- a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp +++ b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp @@ -13,10 +13,12 @@ //===----------------------------------------------------------------------===// #include "InstCombine.h" -#include "llvm/Support/PatternMatch.h" +#include "llvm/IR/PatternMatch.h" using namespace llvm; using namespace PatternMatch; +#define DEBUG_TYPE "instcombine" + /// CheapToScalarize - Return true if the value is cheaper to scalarize than it /// is to leave as a vector operation. isConstant indicates whether we're /// extracting one known element. If false we're extracting a variable index. @@ -25,11 +27,13 @@ static bool CheapToScalarize(Value *V, bool isConstant) { if (isConstant) return true; // If all elts are the same, we can extract it and use any of the values. - Constant *Op0 = C->getAggregateElement(0U); - for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e; ++i) - if (C->getAggregateElement(i) != Op0) - return false; - return true; + if (Constant *Op0 = C->getAggregateElement(0U)) { + for (unsigned i = 1, e = V->getType()->getVectorNumElements(); i != e; + ++i) + if (C->getAggregateElement(i) != Op0) + return false; + return true; + } } Instruction *I = dyn_cast(V); if (!I) return false; @@ -105,6 +109,73 @@ static Value *FindScalarElement(Value *V, unsigned EltNo) { return 0; } +// If we have a PHI node with a vector type that has only 2 uses: feed +// itself and be an operand of extractelement at a constant location, +// try to replace the PHI of the vector type with a PHI of a scalar type. +Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) { + // Verify that the PHI node has exactly 2 uses. Otherwise return NULL. + if (!PN->hasNUses(2)) + return NULL; + + // If so, it's known at this point that one operand is PHI and the other is + // an extractelement node. Find the PHI user that is not the extractelement + // node. + auto iu = PN->user_begin(); + Instruction *PHIUser = dyn_cast(*iu); + if (PHIUser == cast(&EI)) + PHIUser = cast(*(++iu)); + + // Verify that this PHI user has one use, which is the PHI itself, + // and that it is a binary operation which is cheap to scalarize. + // otherwise return NULL. + if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) || + !(isa(PHIUser)) || !CheapToScalarize(PHIUser, true)) + return NULL; + + // Create a scalar PHI node that will replace the vector PHI node + // just before the current PHI node. + PHINode *scalarPHI = cast(InsertNewInstWith( + PHINode::Create(EI.getType(), PN->getNumIncomingValues(), ""), *PN)); + // Scalarize each PHI operand. + for (unsigned i = 0; i < PN->getNumIncomingValues(); i++) { + Value *PHIInVal = PN->getIncomingValue(i); + BasicBlock *inBB = PN->getIncomingBlock(i); + Value *Elt = EI.getIndexOperand(); + // If the operand is the PHI induction variable: + if (PHIInVal == PHIUser) { + // Scalarize the binary operation. Its first operand is the + // scalar PHI and the second operand is extracted from the other + // vector operand. + BinaryOperator *B0 = cast(PHIUser); + unsigned opId = (B0->getOperand(0) == PN) ? 1 : 0; + Value *Op = InsertNewInstWith( + ExtractElementInst::Create(B0->getOperand(opId), Elt, + B0->getOperand(opId)->getName() + ".Elt"), + *B0); + Value *newPHIUser = InsertNewInstWith( + BinaryOperator::Create(B0->getOpcode(), scalarPHI, Op), *B0); + scalarPHI->addIncoming(newPHIUser, inBB); + } else { + // Scalarize PHI input: + Instruction *newEI = ExtractElementInst::Create(PHIInVal, Elt, ""); + // Insert the new instruction into the predecessor basic block. + Instruction *pos = dyn_cast(PHIInVal); + BasicBlock::iterator InsertPos; + if (pos && !isa(pos)) { + InsertPos = pos; + ++InsertPos; + } else { + InsertPos = inBB->getFirstInsertionPt(); + } + + InsertNewInstWith(newEI, *InsertPos); + + scalarPHI->addIncoming(newEI, inBB); + } + } + return ReplaceInstUsesWith(EI, scalarPHI); +} + Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { // If vector val is constant with all elements the same, replace EI with // that element. We handle a known element # below. @@ -149,6 +220,14 @@ Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { if (Value *Elt = FindScalarElement(BCI->getOperand(0), IndexVal)) return new BitCastInst(Elt, EI.getType()); } + + // If there's a vector PHI feeding a scalar use through this extractelement + // instruction, try to scalarize the PHI. + if (PHINode *PN = dyn_cast(EI.getOperand(0))) { + Instruction *scalarPHI = scalarizePHI(EI, PN); + if (scalarPHI) + return scalarPHI; + } } if (Instruction *I = dyn_cast(EI.getOperand(0))) { @@ -201,12 +280,44 @@ Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { } else if (CastInst *CI = dyn_cast(I)) { // Canonicalize extractelement(cast) -> cast(extractelement) // bitcasts can change the number of vector elements and they cost nothing - if (CI->hasOneUse() && EI.hasOneUse() && - (CI->getOpcode() != Instruction::BitCast)) { + if (CI->hasOneUse() && (CI->getOpcode() != Instruction::BitCast)) { Value *EE = Builder->CreateExtractElement(CI->getOperand(0), EI.getIndexOperand()); + Worklist.AddValue(EE); return CastInst::Create(CI->getOpcode(), EE, EI.getType()); } + } else if (SelectInst *SI = dyn_cast(I)) { + if (SI->hasOneUse()) { + // TODO: For a select on vectors, it might be useful to do this if it + // has multiple extractelement uses. For vector select, that seems to + // fight the vectorizer. + + // If we are extracting an element from a vector select or a select on + // vectors, a select on the scalars extracted from the vector arguments. + Value *TrueVal = SI->getTrueValue(); + Value *FalseVal = SI->getFalseValue(); + + Value *Cond = SI->getCondition(); + if (Cond->getType()->isVectorTy()) { + Cond = Builder->CreateExtractElement(Cond, + EI.getIndexOperand(), + Cond->getName() + ".elt"); + } + + Value *V1Elem + = Builder->CreateExtractElement(TrueVal, + EI.getIndexOperand(), + TrueVal->getName() + ".elt"); + + Value *V2Elem + = Builder->CreateExtractElement(FalseVal, + EI.getIndexOperand(), + FalseVal->getName() + ".elt"); + return SelectInst::Create(Cond, + V1Elem, + V2Elem, + SI->getName() + ".elt"); + } } } return 0; @@ -217,9 +328,9 @@ Instruction *InstCombiner::visitExtractElementInst(ExtractElementInst &EI) { /// Otherwise, return false. static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, SmallVectorImpl &Mask) { - assert(V->getType() == LHS->getType() && V->getType() == RHS->getType() && + assert(LHS->getType() == RHS->getType() && "Invalid CollectSingleShuffleElements"); - unsigned NumElts = cast(V->getType())->getNumElements(); + unsigned NumElts = V->getType()->getVectorNumElements(); if (isa(V)) { Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext()))); @@ -258,10 +369,10 @@ static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, return true; } } else if (ExtractElementInst *EI = dyn_cast(ScalarOp)){ - if (isa(EI->getOperand(1)) && - EI->getOperand(0)->getType() == V->getType()) { + if (isa(EI->getOperand(1))) { unsigned ExtractedIdx = cast(EI->getOperand(1))->getZExtValue(); + unsigned NumLHSElts = LHS->getType()->getVectorNumElements(); // This must be extracting from either LHS or RHS. if (EI->getOperand(0) == LHS || EI->getOperand(0) == RHS) { @@ -277,7 +388,7 @@ static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, assert(EI->getOperand(0) == RHS); Mask[InsertedIdx % NumElts] = ConstantInt::get(Type::getInt32Ty(V->getContext()), - ExtractedIdx+NumElts); + ExtractedIdx + NumLHSElts); } return true; } @@ -285,29 +396,36 @@ static bool CollectSingleShuffleElements(Value *V, Value *LHS, Value *RHS, } } } - // TODO: Handle shufflevector here! return false; } -/// CollectShuffleElements - We are building a shuffle of V, using RHS as the -/// RHS of the shuffle instruction, if it is not null. Return a shuffle mask -/// that computes V and the LHS value of the shuffle. -static Value *CollectShuffleElements(Value *V, SmallVectorImpl &Mask, - Value *&RHS) { - assert(V->getType()->isVectorTy() && - (RHS == 0 || V->getType() == RHS->getType()) && - "Invalid shuffle!"); + +/// We are building a shuffle to create V, which is a sequence of insertelement, +/// extractelement pairs. If PermittedRHS is set, then we must either use it or +/// not rely on the second vector source. Return an std::pair containing the +/// left and right vectors of the proposed shuffle (or 0), and set the Mask +/// parameter as required. +/// +/// Note: we intentionally don't try to fold earlier shuffles since they have +/// often been chosen carefully to be efficiently implementable on the target. +typedef std::pair ShuffleOps; + +static ShuffleOps CollectShuffleElements(Value *V, + SmallVectorImpl &Mask, + Value *PermittedRHS) { + assert(V->getType()->isVectorTy() && "Invalid shuffle!"); unsigned NumElts = cast(V->getType())->getNumElements(); if (isa(V)) { Mask.assign(NumElts, UndefValue::get(Type::getInt32Ty(V->getContext()))); - return V; + return std::make_pair( + PermittedRHS ? UndefValue::get(PermittedRHS->getType()) : V, nullptr); } if (isa(V)) { Mask.assign(NumElts, ConstantInt::get(Type::getInt32Ty(V->getContext()),0)); - return V; + return std::make_pair(V, nullptr); } if (InsertElementInst *IEI = dyn_cast(V)) { @@ -317,51 +435,59 @@ static Value *CollectShuffleElements(Value *V, SmallVectorImpl &Mask, Value *IdxOp = IEI->getOperand(2); if (ExtractElementInst *EI = dyn_cast(ScalarOp)) { - if (isa(EI->getOperand(1)) && isa(IdxOp) && - EI->getOperand(0)->getType() == V->getType()) { + if (isa(EI->getOperand(1)) && isa(IdxOp)) { unsigned ExtractedIdx = cast(EI->getOperand(1))->getZExtValue(); unsigned InsertedIdx = cast(IdxOp)->getZExtValue(); // Either the extracted from or inserted into vector must be RHSVec, // otherwise we'd end up with a shuffle of three inputs. - if (EI->getOperand(0) == RHS || RHS == 0) { - RHS = EI->getOperand(0); - Value *V = CollectShuffleElements(VecOp, Mask, RHS); + if (EI->getOperand(0) == PermittedRHS || PermittedRHS == 0) { + Value *RHS = EI->getOperand(0); + ShuffleOps LR = CollectShuffleElements(VecOp, Mask, RHS); + assert(LR.second == 0 || LR.second == RHS); + + if (LR.first->getType() != RHS->getType()) { + // We tried our best, but we can't find anything compatible with RHS + // further up the chain. Return a trivial shuffle. + for (unsigned i = 0; i < NumElts; ++i) + Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), i); + return std::make_pair(V, nullptr); + } + + unsigned NumLHSElts = RHS->getType()->getVectorNumElements(); Mask[InsertedIdx % NumElts] = ConstantInt::get(Type::getInt32Ty(V->getContext()), - NumElts+ExtractedIdx); - return V; + NumLHSElts+ExtractedIdx); + return std::make_pair(LR.first, RHS); } - if (VecOp == RHS) { - Value *V = CollectShuffleElements(EI->getOperand(0), Mask, RHS); - // Update Mask to reflect that `ScalarOp' has been inserted at - // position `InsertedIdx' within the vector returned by IEI. - Mask[InsertedIdx % NumElts] = Mask[ExtractedIdx]; - - // Everything but the extracted element is replaced with the RHS. - for (unsigned i = 0; i != NumElts; ++i) { - if (i != InsertedIdx) - Mask[i] = ConstantInt::get(Type::getInt32Ty(V->getContext()), - NumElts+i); - } - return V; + if (VecOp == PermittedRHS) { + // We've gone as far as we can: anything on the other side of the + // extractelement will already have been converted into a shuffle. + unsigned NumLHSElts = + EI->getOperand(0)->getType()->getVectorNumElements(); + for (unsigned i = 0; i != NumElts; ++i) + Mask.push_back(ConstantInt::get( + Type::getInt32Ty(V->getContext()), + i == InsertedIdx ? ExtractedIdx : NumLHSElts + i)); + return std::make_pair(EI->getOperand(0), PermittedRHS); } // If this insertelement is a chain that comes from exactly these two // vectors, return the vector and the effective shuffle. - if (CollectSingleShuffleElements(IEI, EI->getOperand(0), RHS, Mask)) - return EI->getOperand(0); + if (EI->getOperand(0)->getType() == PermittedRHS->getType() && + CollectSingleShuffleElements(IEI, EI->getOperand(0), PermittedRHS, + Mask)) + return std::make_pair(EI->getOperand(0), PermittedRHS); } } } - // TODO: Handle shufflevector here! // Otherwise, can't do anything fancy. Return an identity vector. for (unsigned i = 0; i != NumElts; ++i) Mask.push_back(ConstantInt::get(Type::getInt32Ty(V->getContext()), i)); - return V; + return std::make_pair(V, nullptr); } Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { @@ -376,17 +502,18 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { // If the inserted element was extracted from some other vector, and if the // indexes are constant, try to turn this into a shufflevector operation. if (ExtractElementInst *EI = dyn_cast(ScalarOp)) { - if (isa(EI->getOperand(1)) && isa(IdxOp) && - EI->getOperand(0)->getType() == IE.getType()) { - unsigned NumVectorElts = IE.getType()->getNumElements(); + if (isa(EI->getOperand(1)) && isa(IdxOp)) { + unsigned NumInsertVectorElts = IE.getType()->getNumElements(); + unsigned NumExtractVectorElts = + EI->getOperand(0)->getType()->getVectorNumElements(); unsigned ExtractedIdx = cast(EI->getOperand(1))->getZExtValue(); unsigned InsertedIdx = cast(IdxOp)->getZExtValue(); - if (ExtractedIdx >= NumVectorElts) // Out of range extract. + if (ExtractedIdx >= NumExtractVectorElts) // Out of range extract. return ReplaceInstUsesWith(IE, VecOp); - if (InsertedIdx >= NumVectorElts) // Out of range insert. + if (InsertedIdx >= NumInsertVectorElts) // Out of range insert. return ReplaceInstUsesWith(IE, UndefValue::get(IE.getType())); // If we are extracting a value from a vector, then inserting it right @@ -396,13 +523,18 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { // If this insertelement isn't used by some other insertelement, turn it // (and any insertelements it points to), into one big shuffle. - if (!IE.hasOneUse() || !isa(IE.use_back())) { + if (!IE.hasOneUse() || !isa(IE.user_back())) { SmallVector Mask; - Value *RHS = 0; - Value *LHS = CollectShuffleElements(&IE, Mask, RHS); - if (RHS == 0) RHS = UndefValue::get(LHS->getType()); - // We now have a shuffle of LHS, RHS, Mask. - return new ShuffleVectorInst(LHS, RHS, ConstantVector::get(Mask)); + ShuffleOps LR = CollectShuffleElements(&IE, Mask, 0); + + // The proposed shuffle may be trivial, in which case we shouldn't + // perform the combine. + if (LR.first != &IE && LR.second != &IE) { + // We now have a shuffle of LHS, RHS, Mask. + if (LR.second == 0) LR.second = UndefValue::get(LR.first->getType()); + return new ShuffleVectorInst(LR.first, LR.second, + ConstantVector::get(Mask)); + } } } } @@ -419,6 +551,257 @@ Instruction *InstCombiner::visitInsertElementInst(InsertElementInst &IE) { return 0; } +/// Return true if we can evaluate the specified expression tree if the vector +/// elements were shuffled in a different order. +static bool CanEvaluateShuffled(Value *V, ArrayRef Mask, + unsigned Depth = 5) { + // We can always reorder the elements of a constant. + if (isa(V)) + return true; + + // We won't reorder vector arguments. No IPO here. + Instruction *I = dyn_cast(V); + if (!I) return false; + + // Two users may expect different orders of the elements. Don't try it. + if (!I->hasOneUse()) + return false; + + if (Depth == 0) return false; + + switch (I->getOpcode()) { + case Instruction::Add: + case Instruction::FAdd: + case Instruction::Sub: + case Instruction::FSub: + case Instruction::Mul: + case Instruction::FMul: + case Instruction::UDiv: + case Instruction::SDiv: + case Instruction::FDiv: + case Instruction::URem: + case Instruction::SRem: + case Instruction::FRem: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + case Instruction::ICmp: + case Instruction::FCmp: + case Instruction::Trunc: + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::UIToFP: + case Instruction::SIToFP: + case Instruction::FPTrunc: + case Instruction::FPExt: + case Instruction::GetElementPtr: { + for (int i = 0, e = I->getNumOperands(); i != e; ++i) { + if (!CanEvaluateShuffled(I->getOperand(i), Mask, Depth-1)) + return false; + } + return true; + } + case Instruction::InsertElement: { + ConstantInt *CI = dyn_cast(I->getOperand(2)); + if (!CI) return false; + int ElementNumber = CI->getLimitedValue(); + + // Verify that 'CI' does not occur twice in Mask. A single 'insertelement' + // can't put an element into multiple indices. + bool SeenOnce = false; + for (int i = 0, e = Mask.size(); i != e; ++i) { + if (Mask[i] == ElementNumber) { + if (SeenOnce) + return false; + SeenOnce = true; + } + } + return CanEvaluateShuffled(I->getOperand(0), Mask, Depth-1); + } + } + return false; +} + +/// Rebuild a new instruction just like 'I' but with the new operands given. +/// In the event of type mismatch, the type of the operands is correct. +static Value *BuildNew(Instruction *I, ArrayRef NewOps) { + // We don't want to use the IRBuilder here because we want the replacement + // instructions to appear next to 'I', not the builder's insertion point. + switch (I->getOpcode()) { + case Instruction::Add: + case Instruction::FAdd: + case Instruction::Sub: + case Instruction::FSub: + case Instruction::Mul: + case Instruction::FMul: + case Instruction::UDiv: + case Instruction::SDiv: + case Instruction::FDiv: + case Instruction::URem: + case Instruction::SRem: + case Instruction::FRem: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: { + BinaryOperator *BO = cast(I); + assert(NewOps.size() == 2 && "binary operator with #ops != 2"); + BinaryOperator *New = + BinaryOperator::Create(cast(I)->getOpcode(), + NewOps[0], NewOps[1], "", BO); + if (isa(BO)) { + New->setHasNoUnsignedWrap(BO->hasNoUnsignedWrap()); + New->setHasNoSignedWrap(BO->hasNoSignedWrap()); + } + if (isa(BO)) { + New->setIsExact(BO->isExact()); + } + if (isa(BO)) + New->copyFastMathFlags(I); + return New; + } + case Instruction::ICmp: + assert(NewOps.size() == 2 && "icmp with #ops != 2"); + return new ICmpInst(I, cast(I)->getPredicate(), + NewOps[0], NewOps[1]); + case Instruction::FCmp: + assert(NewOps.size() == 2 && "fcmp with #ops != 2"); + return new FCmpInst(I, cast(I)->getPredicate(), + NewOps[0], NewOps[1]); + case Instruction::Trunc: + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::UIToFP: + case Instruction::SIToFP: + case Instruction::FPTrunc: + case Instruction::FPExt: { + // It's possible that the mask has a different number of elements from + // the original cast. We recompute the destination type to match the mask. + Type *DestTy = + VectorType::get(I->getType()->getScalarType(), + NewOps[0]->getType()->getVectorNumElements()); + assert(NewOps.size() == 1 && "cast with #ops != 1"); + return CastInst::Create(cast(I)->getOpcode(), NewOps[0], DestTy, + "", I); + } + case Instruction::GetElementPtr: { + Value *Ptr = NewOps[0]; + ArrayRef Idx = NewOps.slice(1); + GetElementPtrInst *GEP = GetElementPtrInst::Create(Ptr, Idx, "", I); + GEP->setIsInBounds(cast(I)->isInBounds()); + return GEP; + } + } + llvm_unreachable("failed to rebuild vector instructions"); +} + +Value * +InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef Mask) { + // Mask.size() does not need to be equal to the number of vector elements. + + assert(V->getType()->isVectorTy() && "can't reorder non-vector elements"); + if (isa(V)) { + return UndefValue::get(VectorType::get(V->getType()->getScalarType(), + Mask.size())); + } + if (isa(V)) { + return ConstantAggregateZero::get( + VectorType::get(V->getType()->getScalarType(), + Mask.size())); + } + if (Constant *C = dyn_cast(V)) { + SmallVector MaskValues; + for (int i = 0, e = Mask.size(); i != e; ++i) { + if (Mask[i] == -1) + MaskValues.push_back(UndefValue::get(Builder->getInt32Ty())); + else + MaskValues.push_back(Builder->getInt32(Mask[i])); + } + return ConstantExpr::getShuffleVector(C, UndefValue::get(C->getType()), + ConstantVector::get(MaskValues)); + } + + Instruction *I = cast(V); + switch (I->getOpcode()) { + case Instruction::Add: + case Instruction::FAdd: + case Instruction::Sub: + case Instruction::FSub: + case Instruction::Mul: + case Instruction::FMul: + case Instruction::UDiv: + case Instruction::SDiv: + case Instruction::FDiv: + case Instruction::URem: + case Instruction::SRem: + case Instruction::FRem: + case Instruction::Shl: + case Instruction::LShr: + case Instruction::AShr: + case Instruction::And: + case Instruction::Or: + case Instruction::Xor: + case Instruction::ICmp: + case Instruction::FCmp: + case Instruction::Trunc: + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::UIToFP: + case Instruction::SIToFP: + case Instruction::FPTrunc: + case Instruction::FPExt: + case Instruction::Select: + case Instruction::GetElementPtr: { + SmallVector NewOps; + bool NeedsRebuild = (Mask.size() != I->getType()->getVectorNumElements()); + for (int i = 0, e = I->getNumOperands(); i != e; ++i) { + Value *V = EvaluateInDifferentElementOrder(I->getOperand(i), Mask); + NewOps.push_back(V); + NeedsRebuild |= (V != I->getOperand(i)); + } + if (NeedsRebuild) { + return BuildNew(I, NewOps); + } + return I; + } + case Instruction::InsertElement: { + int Element = cast(I->getOperand(2))->getLimitedValue(); + + // The insertelement was inserting at Element. Figure out which element + // that becomes after shuffling. The answer is guaranteed to be unique + // by CanEvaluateShuffled. + bool Found = false; + int Index = 0; + for (int e = Mask.size(); Index != e; ++Index) { + if (Mask[Index] == Element) { + Found = true; + break; + } + } + + // If element is not in Mask, no need to handle the operand 1 (element to + // be inserted). Just evaluate values in operand 0 according to Mask. + if (!Found) + return EvaluateInDifferentElementOrder(I->getOperand(0), Mask); + + Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask); + return InsertElementInst::Create(V, I->getOperand(1), + Builder->getInt32(Index), "", I); + } + } + llvm_unreachable("failed to reorder elements of vector instruction!"); +} Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { Value *LHS = SVI.getOperand(0); @@ -450,9 +833,9 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { if (LHS == RHS || isa(LHS)) { if (isa(LHS) && LHS == RHS) { // shuffle(undef,undef,mask) -> undef. - Value* result = (VWidth == LHSWidth) + Value *Result = (VWidth == LHSWidth) ? LHS : UndefValue::get(SVI.getType()); - return ReplaceInstUsesWith(SVI, result); + return ReplaceInstUsesWith(SVI, Result); } // Remap any references to RHS to use LHS. @@ -499,6 +882,11 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { if (isRHSID) return ReplaceInstUsesWith(SVI, RHS); } + if (isa(RHS) && CanEvaluateShuffled(LHS, Mask)) { + Value *V = EvaluateInDifferentElementOrder(LHS, Mask); + return ReplaceInstUsesWith(SVI, V); + } + // If the LHS is a shufflevector itself, see if we can combine it with this // one without producing an unusual shuffle. // Cases that might be simplified: @@ -650,7 +1038,7 @@ Instruction *InstCombiner::visitShuffleVectorInst(ShuffleVectorInst &SVI) { // references from RHSOp0 to LHSOp0, so we don't need to shift the mask. // If newRHS == newLHS, we want to remap any references from newRHS to // newLHS so that we can properly identify splats that may occur due to - // obfuscation accross the two vectors. + // obfuscation across the two vectors. if (eltMask >= 0 && newRHS != NULL && newLHS != newRHS) eltMask += newLHSWidth; }