From 36b56886974eae4f9c5ebc96befd3e7bfe5de338 Mon Sep 17 00:00:00 2001 From: Stephen Hines Date: Wed, 23 Apr 2014 16:57:46 -0700 Subject: Update to LLVM 3.5a. Change-Id: Ifadecab779f128e62e430c2b4f6ddd84953ed617 --- .../InstCombine/InstCombineVectorOps.cpp | 148 ++++++++++++--------- 1 file changed, 87 insertions(+), 61 deletions(-) (limited to 'lib/Transforms/InstCombine/InstCombineVectorOps.cpp') diff --git a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp index 1e72410..521dc9c 100644 --- a/lib/Transforms/InstCombine/InstCombineVectorOps.cpp +++ b/lib/Transforms/InstCombine/InstCombineVectorOps.cpp @@ -13,7 +13,7 @@ //===----------------------------------------------------------------------===// #include "InstCombine.h" -#include "llvm/Support/PatternMatch.h" +#include "llvm/IR/PatternMatch.h" using namespace llvm; using namespace PatternMatch; @@ -25,11 +25,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; @@ -116,7 +118,7 @@ Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) { // 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. - Value::use_iterator iu = PN->use_begin(); + auto iu = PN->user_begin(); Instruction *PHIUser = dyn_cast(*iu); if (PHIUser == cast(&EI)) PHIUser = cast(*(++iu)); @@ -124,7 +126,7 @@ Instruction *InstCombiner::scalarizePHI(ExtractElementInst &EI, PHINode *PN) { // 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->use_back() == PN) || + if (!PHIUser->hasOneUse() || !(PHIUser->user_back() == PN) || !(isa(PHIUser)) || !CheapToScalarize(PHIUser, true)) return NULL; @@ -324,7 +326,7 @@ 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 = V->getType()->getVectorNumElements(); @@ -365,10 +367,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) { @@ -384,7 +386,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; } @@ -392,29 +394,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)) { @@ -424,51 +433,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) { @@ -483,17 +500,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 @@ -503,13 +521,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)); + } } } } @@ -638,6 +661,8 @@ static Value *BuildNew(Instruction *I, ArrayRef NewOps) { if (isa(BO)) { New->setIsExact(BO->isExact()); } + if (isa(BO)) + New->copyFastMathFlags(I); return New; } case Instruction::ICmp: @@ -763,9 +788,10 @@ InstCombiner::EvaluateInDifferentElementOrder(Value *V, ArrayRef Mask) { } } + // 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 UndefValue::get( - VectorType::get(V->getType()->getScalarType(), Mask.size())); + return EvaluateInDifferentElementOrder(I->getOperand(0), Mask); Value *V = EvaluateInDifferentElementOrder(I->getOperand(0), Mask); return InsertElementInst::Create(V, I->getOperand(1), @@ -1010,7 +1036,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; } -- cgit v1.1