diff options
Diffstat (limited to 'contrib/llvm/lib/Transforms/Vectorize')
| -rw-r--r-- | contrib/llvm/lib/Transforms/Vectorize/BBVectorize.cpp | 90 | ||||
| -rw-r--r-- | contrib/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp | 2795 | ||||
| -rw-r--r-- | contrib/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp | 2529 | ||||
| -rw-r--r-- | contrib/llvm/lib/Transforms/Vectorize/VecUtils.cpp | 730 | ||||
| -rw-r--r-- | contrib/llvm/lib/Transforms/Vectorize/VecUtils.h | 164 |
5 files changed, 4560 insertions, 1748 deletions
diff --git a/contrib/llvm/lib/Transforms/Vectorize/BBVectorize.cpp b/contrib/llvm/lib/Transforms/Vectorize/BBVectorize.cpp index 17900da..c5e1dcb 100644 --- a/contrib/llvm/lib/Transforms/Vectorize/BBVectorize.cpp +++ b/contrib/llvm/lib/Transforms/Vectorize/BBVectorize.cpp @@ -356,7 +356,7 @@ namespace { Instruction *J, unsigned o, bool IBeforeJ); void getReplacementInputsForPair(LLVMContext& Context, Instruction *I, - Instruction *J, SmallVector<Value *, 3> &ReplacedOperands, + Instruction *J, SmallVectorImpl<Value *> &ReplacedOperands, bool IBeforeJ); void replaceOutputsOfPair(LLVMContext& Context, Instruction *I, @@ -533,7 +533,7 @@ namespace { default: break; case Instruction::GetElementPtr: // We mark this instruction as zero-cost because scalar GEPs are usually - // lowered to the intruction addressing mode. At the moment we don't + // lowered to the instruction addressing mode. At the moment we don't // generate vector GEPs. return 0; case Instruction::Br: @@ -625,10 +625,10 @@ namespace { ConstantInt *IntOff = ConstOffSCEV->getValue(); int64_t Offset = IntOff->getSExtValue(); - Type *VTy = cast<PointerType>(IPtr->getType())->getElementType(); + Type *VTy = IPtr->getType()->getPointerElementType(); int64_t VTyTSS = (int64_t) TD->getTypeStoreSize(VTy); - Type *VTy2 = cast<PointerType>(JPtr->getType())->getElementType(); + Type *VTy2 = JPtr->getType()->getPointerElementType(); if (VTy != VTy2 && Offset < 0) { int64_t VTy2TSS = (int64_t) TD->getTypeStoreSize(VTy2); OffsetInElmts = Offset/VTy2TSS; @@ -1182,6 +1182,8 @@ namespace { // Look for an instruction with which to pair instruction *I... DenseSet<Value *> Users; AliasSetTracker WriteSet(*AA); + if (I->mayWriteToMemory()) WriteSet.add(I); + bool JAfterStart = IAfterStart; BasicBlock::iterator J = llvm::next(I); for (unsigned ss = 0; J != E && ss <= Config.SearchLimit; ++J, ++ss) { @@ -1403,6 +1405,8 @@ namespace { DenseSet<Value *> Users; AliasSetTracker WriteSet(*AA); + if (I->mayWriteToMemory()) WriteSet.add(I); + for (BasicBlock::iterator J = llvm::next(I); J != E; ++J) { (void) trackUsesOfI(Users, WriteSet, I, J); @@ -1602,7 +1606,7 @@ namespace { DenseSet<ValuePair> CurrentPairs; bool CanAdd = true; - for (SmallVector<ValuePairWithDepth, 8>::iterator C2 + for (SmallVectorImpl<ValuePairWithDepth>::iterator C2 = BestChildren.begin(), E2 = BestChildren.end(); C2 != E2; ++C2) { if (C2->first.first == C->first.first || @@ -1642,7 +1646,7 @@ namespace { if (!CanAdd) continue; // And check the queue too... - for (SmallVector<ValuePairWithDepth, 32>::iterator C2 = Q.begin(), + for (SmallVectorImpl<ValuePairWithDepth>::iterator C2 = Q.begin(), E2 = Q.end(); C2 != E2; ++C2) { if (C2->first.first == C->first.first || C2->first.first == C->first.second || @@ -1691,7 +1695,7 @@ namespace { // to an already-selected child. Check for this here, and if a // conflict is found, then remove the previously-selected child // before adding this one in its place. - for (SmallVector<ValuePairWithDepth, 8>::iterator C2 + for (SmallVectorImpl<ValuePairWithDepth>::iterator C2 = BestChildren.begin(); C2 != BestChildren.end();) { if (C2->first.first == C->first.first || C2->first.first == C->first.second || @@ -1706,7 +1710,7 @@ namespace { BestChildren.push_back(ValuePairWithDepth(C->first, C->second)); } - for (SmallVector<ValuePairWithDepth, 8>::iterator C + for (SmallVectorImpl<ValuePairWithDepth>::iterator C = BestChildren.begin(), E2 = BestChildren.end(); C != E2; ++C) { size_t DepthF = getDepthFactor(C->first.first); @@ -2227,11 +2231,12 @@ namespace { // The pointer value is taken to be the one with the lowest offset. Value *VPtr = IPtr; - Type *ArgTypeI = cast<PointerType>(IPtr->getType())->getElementType(); - Type *ArgTypeJ = cast<PointerType>(JPtr->getType())->getElementType(); + Type *ArgTypeI = IPtr->getType()->getPointerElementType(); + Type *ArgTypeJ = JPtr->getType()->getPointerElementType(); Type *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ); - Type *VArgPtrType = PointerType::get(VArgType, - cast<PointerType>(IPtr->getType())->getAddressSpace()); + Type *VArgPtrType + = PointerType::get(VArgType, + IPtr->getType()->getPointerAddressSpace()); return new BitCastInst(VPtr, VArgPtrType, getReplacementName(I, true, o), /* insert before */ I); } @@ -2240,7 +2245,7 @@ namespace { unsigned MaskOffset, unsigned NumInElem, unsigned NumInElem1, unsigned IdxOffset, std::vector<Constant*> &Mask) { - unsigned NumElem1 = cast<VectorType>(J->getType())->getNumElements(); + unsigned NumElem1 = J->getType()->getVectorNumElements(); for (unsigned v = 0; v < NumElem1; ++v) { int m = cast<ShuffleVectorInst>(J)->getMaskValue(v); if (m < 0) { @@ -2267,18 +2272,18 @@ namespace { Type *ArgTypeJ = J->getType(); Type *VArgType = getVecTypeForPair(ArgTypeI, ArgTypeJ); - unsigned NumElemI = cast<VectorType>(ArgTypeI)->getNumElements(); + unsigned NumElemI = ArgTypeI->getVectorNumElements(); // Get the total number of elements in the fused vector type. // By definition, this must equal the number of elements in // the final mask. - unsigned NumElem = cast<VectorType>(VArgType)->getNumElements(); + unsigned NumElem = VArgType->getVectorNumElements(); std::vector<Constant*> Mask(NumElem); Type *OpTypeI = I->getOperand(0)->getType(); - unsigned NumInElemI = cast<VectorType>(OpTypeI)->getNumElements(); + unsigned NumInElemI = OpTypeI->getVectorNumElements(); Type *OpTypeJ = J->getOperand(0)->getType(); - unsigned NumInElemJ = cast<VectorType>(OpTypeJ)->getNumElements(); + unsigned NumInElemJ = OpTypeJ->getVectorNumElements(); // The fused vector will be: // ----------------------------------------------------- @@ -2340,6 +2345,12 @@ namespace { return ExpandedIEChain; } + static unsigned getNumScalarElements(Type *Ty) { + if (VectorType *VecTy = dyn_cast<VectorType>(Ty)) + return VecTy->getNumElements(); + return 1; + } + // Returns the value to be used as the specified operand of the vector // instruction that fuses I with J. Value *BBVectorize::getReplacementInput(LLVMContext& Context, Instruction *I, @@ -2355,17 +2366,8 @@ namespace { Instruction *L = I, *H = J; Type *ArgTypeL = ArgTypeI, *ArgTypeH = ArgTypeJ; - unsigned numElemL; - if (ArgTypeL->isVectorTy()) - numElemL = cast<VectorType>(ArgTypeL)->getNumElements(); - else - numElemL = 1; - - unsigned numElemH; - if (ArgTypeH->isVectorTy()) - numElemH = cast<VectorType>(ArgTypeH)->getNumElements(); - else - numElemH = 1; + unsigned numElemL = getNumScalarElements(ArgTypeL); + unsigned numElemH = getNumScalarElements(ArgTypeH); Value *LOp = L->getOperand(o); Value *HOp = H->getOperand(o); @@ -2426,11 +2428,12 @@ namespace { if (CanUseInputs) { unsigned LOpElem = - cast<VectorType>(cast<Instruction>(LOp)->getOperand(0)->getType()) - ->getNumElements(); + cast<Instruction>(LOp)->getOperand(0)->getType() + ->getVectorNumElements(); + unsigned HOpElem = - cast<VectorType>(cast<Instruction>(HOp)->getOperand(0)->getType()) - ->getNumElements(); + cast<Instruction>(HOp)->getOperand(0)->getType() + ->getVectorNumElements(); // We have one or two input vectors. We need to map each index of the // operands to the index of the original vector. @@ -2646,14 +2649,14 @@ namespace { getReplacementName(IBeforeJ ? I : J, true, o, 1)); } - + NHOp->insertBefore(IBeforeJ ? J : I); HOp = NHOp; } } if (ArgType->isVectorTy()) { - unsigned numElem = cast<VectorType>(VArgType)->getNumElements(); + unsigned numElem = VArgType->getVectorNumElements(); std::vector<Constant*> Mask(numElem); for (unsigned v = 0; v < numElem; ++v) { unsigned Idx = v; @@ -2687,7 +2690,7 @@ namespace { // to the vector instruction that fuses I with J. void BBVectorize::getReplacementInputsForPair(LLVMContext& Context, Instruction *I, Instruction *J, - SmallVector<Value *, 3> &ReplacedOperands, + SmallVectorImpl<Value *> &ReplacedOperands, bool IBeforeJ) { unsigned NumOperands = I->getNumOperands(); @@ -2746,16 +2749,8 @@ namespace { VectorType *VType = getVecTypeForPair(IType, JType); unsigned numElem = VType->getNumElements(); - unsigned numElemI, numElemJ; - if (IType->isVectorTy()) - numElemI = cast<VectorType>(IType)->getNumElements(); - else - numElemI = 1; - - if (JType->isVectorTy()) - numElemJ = cast<VectorType>(JType)->getNumElements(); - else - numElemJ = 1; + unsigned numElemI = getNumScalarElements(IType); + unsigned numElemJ = getNumScalarElements(JType); if (IType->isVectorTy()) { std::vector<Constant*> Mask1(numElemI), Mask2(numElemI); @@ -2804,6 +2799,8 @@ namespace { DenseSet<Value *> Users; AliasSetTracker WriteSet(*AA); + if (I->mayWriteToMemory()) WriteSet.add(I); + for (; cast<Instruction>(L) != J; ++L) (void) trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSetPairs); @@ -2824,6 +2821,8 @@ namespace { DenseSet<Value *> Users; AliasSetTracker WriteSet(*AA); + if (I->mayWriteToMemory()) WriteSet.add(I); + for (; cast<Instruction>(L) != J;) { if (trackUsesOfI(Users, WriteSet, I, L, true, &LoadMoveSetPairs)) { // Move this instruction @@ -2853,6 +2852,7 @@ namespace { DenseSet<Value *> Users; AliasSetTracker WriteSet(*AA); + if (I->mayWriteToMemory()) WriteSet.add(I); // Note: We cannot end the loop when we reach J because J could be moved // farther down the use chain by another instruction pairing. Also, J diff --git a/contrib/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/contrib/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index 08d3725..5e75871 100644 --- a/contrib/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/contrib/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -47,13 +47,15 @@ #include "llvm/Transforms/Vectorize.h" #include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/EquivalenceClasses.h" +#include "llvm/ADT/Hashing.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopIterator.h" @@ -119,11 +121,14 @@ static const unsigned TinyTripCountUnrollThreshold = 128; /// than this number of comparisons. static const unsigned RuntimeMemoryCheckThreshold = 8; -/// We use a metadata with this name to indicate that a scalar loop was -/// vectorized and that we don't need to re-vectorize it if we run into it -/// again. -static const char* -AlreadyVectorizedMDName = "llvm.vectorizer.already_vectorized"; +/// Maximum simd width. +static const unsigned MaxVectorWidth = 64; + +/// Maximum vectorization unroll count. +static const unsigned MaxUnrollFactor = 16; + +/// The cost of a loop that is considered 'small' by the unroller. +static const unsigned SmallLoopCost = 20; namespace { @@ -166,7 +171,9 @@ public: updateAnalysis(); } -private: + virtual ~InnerLoopVectorizer() {} + +protected: /// A small list of PHINodes. typedef SmallVector<PHINode*, 4> PhiVector; /// When we unroll loops we have multiple vector values for each scalar. @@ -174,6 +181,11 @@ private: /// originated from one scalar instruction. typedef SmallVector<Value*, 2> VectorParts; + // When we if-convert we need create edge masks. We have to cache values so + // that we don't end up with exponential recursion/IR. + typedef DenseMap<std::pair<BasicBlock*, BasicBlock*>, + VectorParts> EdgeMaskCache; + /// Add code that checks at runtime if the accessed arrays overlap. /// Returns the comparator value or NULL if no check is needed. Instruction *addRuntimeCheck(LoopVectorizationLegality *Legal, @@ -181,7 +193,13 @@ private: /// Create an empty loop, based on the loop ranges of the old loop. void createEmptyLoop(LoopVectorizationLegality *Legal); /// Copy and widen the instructions from the old loop. - void vectorizeLoop(LoopVectorizationLegality *Legal); + virtual void vectorizeLoop(LoopVectorizationLegality *Legal); + + /// \brief The Loop exit block may have single value PHI nodes where the + /// incoming value is 'Undef'. While vectorizing we only handled real values + /// that were defined inside the loop. Here we fix the 'undef case'. + /// See PR14725. + void fixLCSSAPHIs(); /// A helper function that computes the predicate of the block BB, assuming /// that the header block of the loop is set to True. It returns the *entry* @@ -195,16 +213,23 @@ private: void vectorizeBlockInLoop(LoopVectorizationLegality *Legal, BasicBlock *BB, PhiVector *PV); + /// Vectorize a single PHINode in a block. This method handles the induction + /// variable canonicalization. It supports both VF = 1 for unrolled loops and + /// arbitrary length vectors. + void widenPHIInstruction(Instruction *PN, VectorParts &Entry, + LoopVectorizationLegality *Legal, + unsigned UF, unsigned VF, PhiVector *PV); + /// Insert the new loop to the loop hierarchy and pass manager /// and update the analysis passes. void updateAnalysis(); /// This instruction is un-vectorizable. Implement it as a sequence /// of scalars. - void scalarizeInstruction(Instruction *Instr); + virtual void scalarizeInstruction(Instruction *Instr); /// Vectorize Load and Store instructions, - void vectorizeMemoryInstruction(Instruction *Instr, + virtual void vectorizeMemoryInstruction(Instruction *Instr, LoopVectorizationLegality *Legal); /// Create a broadcast instruction. This method generates a broadcast @@ -212,12 +237,12 @@ private: /// value. If this is the induction variable then we extend it to N, N+1, ... /// this is needed because each iteration in the loop corresponds to a SIMD /// element. - Value *getBroadcastInstrs(Value *V); + virtual Value *getBroadcastInstrs(Value *V); /// This function adds 0, 1, 2 ... to each vector element, starting at zero. /// If Negate is set then negative numbers are added e.g. (0, -1, -2, ...). /// The sequence starts at StartIndex. - Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate); + virtual Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate); /// When we go over instructions in the basic block we rely on previous /// values within the current basic block or on loop invariant values. @@ -227,7 +252,7 @@ private: VectorParts &getVectorValue(Value *V); /// Generate a shuffle sequence that will reverse the vector Vec. - Value *reverseVector(Value *Vec); + virtual Value *reverseVector(Value *Vec); /// This is a helper class that holds the vectorizer state. It maps scalar /// instructions to vector instructions. When the code is 'unrolled' then @@ -285,6 +310,8 @@ private: /// The vectorization SIMD factor to use. Each vector will have this many /// vector elements. unsigned VF; + +protected: /// The vectorization unroll factor to use. Each scalar is vectorized to this /// many different vector instructions. unsigned UF; @@ -313,10 +340,57 @@ private: PHINode *Induction; /// The induction variable of the old basic block. PHINode *OldInduction; + /// Holds the extended (to the widest induction type) start index. + Value *ExtendedIdx; /// Maps scalars to widened vectors. ValueMap WidenMap; + EdgeMaskCache MaskCache; }; +class InnerLoopUnroller : public InnerLoopVectorizer { +public: + InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI, + DominatorTree *DT, DataLayout *DL, + const TargetLibraryInfo *TLI, unsigned UnrollFactor) : + InnerLoopVectorizer(OrigLoop, SE, LI, DT, DL, TLI, 1, UnrollFactor) { } + +private: + virtual void scalarizeInstruction(Instruction *Instr); + virtual void vectorizeMemoryInstruction(Instruction *Instr, + LoopVectorizationLegality *Legal); + virtual Value *getBroadcastInstrs(Value *V); + virtual Value *getConsecutiveVector(Value* Val, int StartIdx, bool Negate); + virtual Value *reverseVector(Value *Vec); +}; + +/// \brief Look for a meaningful debug location on the instruction or it's +/// operands. +static Instruction *getDebugLocFromInstOrOperands(Instruction *I) { + if (!I) + return I; + + DebugLoc Empty; + if (I->getDebugLoc() != Empty) + return I; + + for (User::op_iterator OI = I->op_begin(), OE = I->op_end(); OI != OE; ++OI) { + if (Instruction *OpInst = dyn_cast<Instruction>(*OI)) + if (OpInst->getDebugLoc() != Empty) + return OpInst; + } + + return I; +} + +/// \brief Set the debug location in the builder using the debug location in the +/// instruction. +static void setDebugLocFromInst(IRBuilder<> &B, const Value *Ptr) { + if (const Instruction *Inst = dyn_cast_or_null<Instruction>(Ptr)) + B.SetCurrentDebugLocation(Inst->getDebugLoc()); + else + B.SetCurrentDebugLocation(DebugLoc()); +} + /// LoopVectorizationLegality checks if it is legal to vectorize a loop, and /// to what vectorization factor. /// This class does not look at the profitability of vectorization, only the @@ -333,10 +407,10 @@ private: class LoopVectorizationLegality { public: LoopVectorizationLegality(Loop *L, ScalarEvolution *SE, DataLayout *DL, - DominatorTree *DT, TargetTransformInfo* TTI, - AliasAnalysis *AA, TargetLibraryInfo *TLI) - : TheLoop(L), SE(SE), DL(DL), DT(DT), TTI(TTI), AA(AA), TLI(TLI), - Induction(0), HasFunNoNaNAttr(false) {} + DominatorTree *DT, TargetLibraryInfo *TLI) + : TheLoop(L), SE(SE), DL(DL), DT(DT), TLI(TLI), + Induction(0), WidestIndTy(0), HasFunNoNaNAttr(false), + MaxSafeDepDistBytes(-1U) {} /// This enum represents the kinds of reductions that we support. enum ReductionKind { @@ -372,7 +446,7 @@ public: MRK_FloatMax }; - /// This POD struct holds information about reduction variables. + /// This struct holds information about reduction variables. struct ReductionDescriptor { ReductionDescriptor() : StartValue(0), LoopExitInstr(0), Kind(RK_NoReduction), MinMaxKind(MRK_Invalid) {} @@ -409,8 +483,8 @@ public: MinMaxReductionKind MinMaxKind; }; - // This POD struct holds information about the memory runtime legality - // check that a group of pointers do not overlap. + /// This struct holds information about the memory runtime legality + /// check that a group of pointers do not overlap. struct RuntimePointerCheck { RuntimePointerCheck() : Need(false) {} @@ -420,10 +494,13 @@ public: Pointers.clear(); Starts.clear(); Ends.clear(); + IsWritePtr.clear(); + DependencySetId.clear(); } /// Insert a pointer and calculate the start and end SCEVs. - void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr); + void insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, bool WritePtr, + unsigned DepSetId); /// This flag indicates if we need to add the runtime check. bool Need; @@ -435,9 +512,12 @@ public: SmallVector<const SCEV*, 2> Ends; /// Holds the information if this pointer is used for writing to memory. SmallVector<bool, 2> IsWritePtr; + /// Holds the id of the set of pointers that could be dependent because of a + /// shared underlying object. + SmallVector<unsigned, 2> DependencySetId; }; - /// A POD for saving information about induction variables. + /// A struct for saving information about induction variables. struct InductionInfo { InductionInfo(Value *Start, InductionKind K) : StartValue(Start), IK(K) {} InductionInfo() : StartValue(0), IK(IK_NoInduction) {} @@ -455,11 +535,6 @@ public: /// induction descriptor. typedef MapVector<PHINode*, InductionInfo> InductionList; - /// Alias(Multi)Map stores the values (GEPs or underlying objects and their - /// respective Store/Load instruction(s) to calculate aliasing. - typedef MapVector<Value*, Instruction* > AliasMap; - typedef DenseMap<Value*, std::vector<Instruction*> > AliasMultiMap; - /// Returns true if it is legal to vectorize this loop. /// This does not mean that it is profitable to vectorize this /// loop, only that it is legal to do so. @@ -474,6 +549,9 @@ public: /// Returns the induction variables found in the loop. InductionList *getInductionVars() { return &Inductions; } + /// Returns the widest induction type. + Type *getWidestInductionType() { return WidestIndTy; } + /// Returns True if V is an induction variable in this loop. bool isInductionVariable(const Value *V); @@ -503,6 +581,9 @@ public: /// This function returns the identity element (or neutral element) for /// the operation K. static Constant *getReductionIdentity(ReductionKind K, Type *Tp); + + unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } + private: /// Check if a single basic block loop is vectorizable. /// At this point we know that this is a loop with a constant trip count @@ -523,8 +604,9 @@ private: void collectLoopUniforms(); /// Return true if all of the instructions in the block can be speculatively - /// executed. - bool blockCanBePredicated(BasicBlock *BB); + /// executed. \p SafePtrs is a list of addresses that are known to be legal + /// and we know that we can read from them without segfault. + bool blockCanBePredicated(BasicBlock *BB, SmallPtrSet<Value *, 8>& SafePtrs); /// Returns True, if 'Phi' is the kind of reduction variable for type /// 'Kind'. If this is a reduction variable, it adds it to ReductionList. @@ -543,16 +625,6 @@ private: /// Returns the induction kind of Phi. This function may return NoInduction /// if the PHI is not an induction variable. InductionKind isInductionVariable(PHINode *Phi); - /// Return true if can compute the address bounds of Ptr within the loop. - bool hasComputableBounds(Value *Ptr); - /// Return true if there is the chance of write reorder. - bool hasPossibleGlobalWriteReorder(Value *Object, - Instruction *Inst, - AliasMultiMap &WriteObjects, - unsigned MaxByteWidth); - /// Return the AA location for a load or a store. - AliasAnalysis::Location getLoadStoreLocation(Instruction *Inst); - /// The loop that we evaluate. Loop *TheLoop; @@ -562,10 +634,6 @@ private: DataLayout *DL; /// Dominators. DominatorTree *DT; - /// Target Info. - TargetTransformInfo *TTI; - /// Alias Analysis. - AliasAnalysis *AA; /// Target Library Info. TargetLibraryInfo *TLI; @@ -580,6 +648,8 @@ private: /// Notice that inductions don't need to start at zero and that induction /// variables can be pointers. InductionList Inductions; + /// Holds the widest induction type encountered. + Type *WidestIndTy; /// Allowed outside users. This holds the reduction /// vars which can be accessed from outside the loop. @@ -592,6 +662,8 @@ private: RuntimePointerCheck PtrRtCheck; /// Can we assume the absence of NaNs. bool HasFunNoNaNAttr; + + unsigned MaxSafeDepDistBytes; }; /// LoopVectorizationCostModel - estimates the expected speedups due to @@ -684,12 +756,140 @@ private: const TargetLibraryInfo *TLI; }; +/// Utility class for getting and setting loop vectorizer hints in the form +/// of loop metadata. +struct LoopVectorizeHints { + /// Vectorization width. + unsigned Width; + /// Vectorization unroll factor. + unsigned Unroll; + + LoopVectorizeHints(const Loop *L, bool DisableUnrolling) + : Width(VectorizationFactor) + , Unroll(DisableUnrolling ? 1 : VectorizationUnroll) + , LoopID(L->getLoopID()) { + getHints(L); + // The command line options override any loop metadata except for when + // width == 1 which is used to indicate the loop is already vectorized. + if (VectorizationFactor.getNumOccurrences() > 0 && Width != 1) + Width = VectorizationFactor; + if (VectorizationUnroll.getNumOccurrences() > 0) + Unroll = VectorizationUnroll; + + DEBUG(if (DisableUnrolling && Unroll == 1) + dbgs() << "LV: Unrolling disabled by the pass manager\n"); + } + + /// Return the loop vectorizer metadata prefix. + static StringRef Prefix() { return "llvm.vectorizer."; } + + MDNode *createHint(LLVMContext &Context, StringRef Name, unsigned V) { + SmallVector<Value*, 2> Vals; + Vals.push_back(MDString::get(Context, Name)); + Vals.push_back(ConstantInt::get(Type::getInt32Ty(Context), V)); + return MDNode::get(Context, Vals); + } + + /// Mark the loop L as already vectorized by setting the width to 1. + void setAlreadyVectorized(Loop *L) { + LLVMContext &Context = L->getHeader()->getContext(); + + Width = 1; + + // Create a new loop id with one more operand for the already_vectorized + // hint. If the loop already has a loop id then copy the existing operands. + SmallVector<Value*, 4> Vals(1); + if (LoopID) + for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) + Vals.push_back(LoopID->getOperand(i)); + + Vals.push_back(createHint(Context, Twine(Prefix(), "width").str(), Width)); + Vals.push_back(createHint(Context, Twine(Prefix(), "unroll").str(), 1)); + + MDNode *NewLoopID = MDNode::get(Context, Vals); + // Set operand 0 to refer to the loop id itself. + NewLoopID->replaceOperandWith(0, NewLoopID); + + L->setLoopID(NewLoopID); + if (LoopID) + LoopID->replaceAllUsesWith(NewLoopID); + + LoopID = NewLoopID; + } + +private: + MDNode *LoopID; + + /// Find hints specified in the loop metadata. + void getHints(const Loop *L) { + if (!LoopID) + return; + + // First operand should refer to the loop id itself. + assert(LoopID->getNumOperands() > 0 && "requires at least one operand"); + assert(LoopID->getOperand(0) == LoopID && "invalid loop id"); + + for (unsigned i = 1, ie = LoopID->getNumOperands(); i < ie; ++i) { + const MDString *S = 0; + SmallVector<Value*, 4> Args; + + // The expected hint is either a MDString or a MDNode with the first + // operand a MDString. + if (const MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i))) { + if (!MD || MD->getNumOperands() == 0) + continue; + S = dyn_cast<MDString>(MD->getOperand(0)); + for (unsigned i = 1, ie = MD->getNumOperands(); i < ie; ++i) + Args.push_back(MD->getOperand(i)); + } else { + S = dyn_cast<MDString>(LoopID->getOperand(i)); + assert(Args.size() == 0 && "too many arguments for MDString"); + } + + if (!S) + continue; + + // Check if the hint starts with the vectorizer prefix. + StringRef Hint = S->getString(); + if (!Hint.startswith(Prefix())) + continue; + // Remove the prefix. + Hint = Hint.substr(Prefix().size(), StringRef::npos); + + if (Args.size() == 1) + getHint(Hint, Args[0]); + } + } + + // Check string hint with one operand. + void getHint(StringRef Hint, Value *Arg) { + const ConstantInt *C = dyn_cast<ConstantInt>(Arg); + if (!C) return; + unsigned Val = C->getZExtValue(); + + if (Hint == "width") { + if (isPowerOf2_32(Val) && Val <= MaxVectorWidth) + Width = Val; + else + DEBUG(dbgs() << "LV: ignoring invalid width hint metadata\n"); + } else if (Hint == "unroll") { + if (isPowerOf2_32(Val) && Val <= MaxUnrollFactor) + Unroll = Val; + else + DEBUG(dbgs() << "LV: ignoring invalid unroll hint metadata\n"); + } else { + DEBUG(dbgs() << "LV: ignoring unknown hint " << Hint << '\n'); + } + } +}; + /// The LoopVectorize Pass. struct LoopVectorize : public LoopPass { /// Pass identification, replacement for typeid static char ID; - explicit LoopVectorize() : LoopPass(ID) { + explicit LoopVectorize(bool NoUnrolling = false) + : LoopPass(ID), DisableUnrolling(NoUnrolling) { initializeLoopVectorizePass(*PassRegistry::getPassRegistry()); } @@ -698,8 +898,8 @@ struct LoopVectorize : public LoopPass { LoopInfo *LI; TargetTransformInfo *TTI; DominatorTree *DT; - AliasAnalysis *AA; TargetLibraryInfo *TLI; + bool DisableUnrolling; virtual bool runOnLoop(Loop *L, LPPassManager &LPM) { // We only vectorize innermost loops. @@ -711,19 +911,30 @@ struct LoopVectorize : public LoopPass { LI = &getAnalysis<LoopInfo>(); TTI = &getAnalysis<TargetTransformInfo>(); DT = &getAnalysis<DominatorTree>(); - AA = getAnalysisIfAvailable<AliasAnalysis>(); TLI = getAnalysisIfAvailable<TargetLibraryInfo>(); + // If the target claims to have no vector registers don't attempt + // vectorization. + if (!TTI->getNumberOfRegisters(true)) + return false; + if (DL == NULL) { - DEBUG(dbgs() << "LV: Not vectorizing because of missing data layout"); + DEBUG(dbgs() << "LV: Not vectorizing because of missing data layout\n"); return false; } DEBUG(dbgs() << "LV: Checking a loop in \"" << L->getHeader()->getParent()->getName() << "\"\n"); + LoopVectorizeHints Hints(L, DisableUnrolling); + + if (Hints.Width == 1 && Hints.Unroll == 1) { + DEBUG(dbgs() << "LV: Not vectorizing.\n"); + return false; + } + // Check if it is legal to vectorize the loop. - LoopVectorizationLegality LVL(L, SE, DL, DT, TTI, AA, TLI); + LoopVectorizationLegality LVL(L, SE, DL, DT, TLI); if (!LVL.canVectorize()) { DEBUG(dbgs() << "LV: Not vectorizing.\n"); return false; @@ -749,23 +960,30 @@ struct LoopVectorize : public LoopPass { // Select the optimal vectorization factor. LoopVectorizationCostModel::VectorizationFactor VF; - VF = CM.selectVectorizationFactor(OptForSize, VectorizationFactor); + VF = CM.selectVectorizationFactor(OptForSize, Hints.Width); // Select the unroll factor. - unsigned UF = CM.selectUnrollFactor(OptForSize, VectorizationUnroll, - VF.Width, VF.Cost); + unsigned UF = CM.selectUnrollFactor(OptForSize, Hints.Unroll, VF.Width, + VF.Cost); + + DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF.Width << ") in "<< + F->getParent()->getModuleIdentifier() << '\n'); + DEBUG(dbgs() << "LV: Unroll Factor is " << UF << '\n'); if (VF.Width == 1) { DEBUG(dbgs() << "LV: Vectorization is possible but not beneficial.\n"); - return false; + if (UF == 1) + return false; + // We decided not to vectorize, but we may want to unroll. + InnerLoopUnroller Unroller(L, SE, LI, DT, DL, TLI, UF); + Unroller.vectorize(&LVL); + } else { + // If we decided that it is *legal* to vectorize the loop then do it. + InnerLoopVectorizer LB(L, SE, LI, DT, DL, TLI, VF.Width, UF); + LB.vectorize(&LVL); } - DEBUG(dbgs() << "LV: Found a vectorizable loop ("<< VF.Width << ") in "<< - F->getParent()->getModuleIdentifier()<<"\n"); - DEBUG(dbgs() << "LV: Unroll Factor is " << UF << "\n"); - - // If we decided that it is *legal* to vectorize the loop then do it. - InnerLoopVectorizer LB(L, SE, LI, DT, DL, TLI, VF.Width, UF); - LB.vectorize(&LVL); + // Mark the loop as already vectorized to avoid vectorizing again. + Hints.setAlreadyVectorized(L); DEBUG(verifyFunction(*L->getHeader()->getParent())); return true; @@ -795,38 +1013,34 @@ struct LoopVectorize : public LoopPass { void LoopVectorizationLegality::RuntimePointerCheck::insert(ScalarEvolution *SE, Loop *Lp, Value *Ptr, - bool WritePtr) { + bool WritePtr, + unsigned DepSetId) { const SCEV *Sc = SE->getSCEV(Ptr); const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Sc); assert(AR && "Invalid addrec expression"); - const SCEV *Ex = SE->getExitCount(Lp, Lp->getLoopLatch()); + const SCEV *Ex = SE->getBackedgeTakenCount(Lp); const SCEV *ScEnd = AR->evaluateAtIteration(Ex, *SE); Pointers.push_back(Ptr); Starts.push_back(AR->getStart()); Ends.push_back(ScEnd); IsWritePtr.push_back(WritePtr); + DependencySetId.push_back(DepSetId); } Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) { - // Save the current insertion location. - Instruction *Loc = Builder.GetInsertPoint(); - // We need to place the broadcast of invariant variables outside the loop. Instruction *Instr = dyn_cast<Instruction>(V); bool NewInstr = (Instr && Instr->getParent() == LoopVectorBody); bool Invariant = OrigLoop->isLoopInvariant(V) && !NewInstr; // Place the code for broadcasting invariant variables in the new preheader. + IRBuilder<>::InsertPointGuard Guard(Builder); if (Invariant) Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator()); // Broadcast the scalar into all locations in the vector. Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast"); - // Restore the builder insertion point. - if (Invariant) - Builder.SetInsertPoint(Loc); - return Shuf; } @@ -853,10 +1067,35 @@ Value *InnerLoopVectorizer::getConsecutiveVector(Value* Val, int StartIdx, return Builder.CreateAdd(Val, Cv, "induction"); } +/// \brief Find the operand of the GEP that should be checked for consecutive +/// stores. This ignores trailing indices that have no effect on the final +/// pointer. +static unsigned getGEPInductionOperand(DataLayout *DL, + const GetElementPtrInst *Gep) { + unsigned LastOperand = Gep->getNumOperands() - 1; + unsigned GEPAllocSize = DL->getTypeAllocSize( + cast<PointerType>(Gep->getType()->getScalarType())->getElementType()); + + // Walk backwards and try to peel off zeros. + while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) { + // Find the type we're currently indexing into. + gep_type_iterator GEPTI = gep_type_begin(Gep); + std::advance(GEPTI, LastOperand - 1); + + // If it's a type with the same allocation size as the result of the GEP we + // can peel off the zero index. + if (DL->getTypeAllocSize(*GEPTI) != GEPAllocSize) + break; + --LastOperand; + } + + return LastOperand; +} + int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) { assert(Ptr->getType()->isPointerTy() && "Unexpected non ptr"); // Make sure that the pointer does not point to structs. - if (cast<PointerType>(Ptr->getType())->getElementType()->isAggregateType()) + if (Ptr->getType()->getPointerElementType()->isAggregateType()) return 0; // If this value is a pointer induction variable we know it is consecutive. @@ -874,8 +1113,6 @@ int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) { return 0; unsigned NumOperands = Gep->getNumOperands(); - Value *LastIndex = Gep->getOperand(NumOperands - 1); - Value *GpPtr = Gep->getPointerOperand(); // If this GEP value is a consecutive pointer induction variable and all of // the indices are constant then we know it is consecutive. We can @@ -899,14 +1136,18 @@ int LoopVectorizationLegality::isConsecutivePtr(Value *Ptr) { return -1; } - // Check that all of the gep indices are uniform except for the last. - for (unsigned i = 0; i < NumOperands - 1; ++i) - if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop)) + unsigned InductionOperand = getGEPInductionOperand(DL, Gep); + + // Check that all of the gep indices are uniform except for our induction + // operand. + for (unsigned i = 0; i != NumOperands; ++i) + if (i != InductionOperand && + !SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop)) return 0; - // We can emit wide load/stores only if the last index is the induction - // variable. - const SCEV *Last = SE->getSCEV(LastIndex); + // We can emit wide load/stores only if the last non-zero index is the + // induction variable. + const SCEV *Last = SE->getSCEV(Gep->getOperand(InductionOperand)); if (const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(Last)) { const SCEV *Step = AR->getStepRecurrence(*SE); @@ -964,7 +1205,11 @@ void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr, Type *DataTy = VectorType::get(ScalarDataTy, VF); Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand(); unsigned Alignment = LI ? LI->getAlignment() : SI->getAlignment(); - + // An alignment of 0 means target abi alignment. We need to use the scalar's + // target abi alignment in such a case. + if (!Alignment) + Alignment = DL->getABITypeAlignment(ScalarDataTy); + unsigned AddressSpace = Ptr->getType()->getPointerAddressSpace(); unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ScalarDataTy); unsigned VectorElementSize = DL->getTypeStoreSize(DataTy)/VF; @@ -985,6 +1230,7 @@ void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr, // Handle consecutive loads/stores. GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); if (Gep && Legal->isInductionVariable(Gep->getPointerOperand())) { + setDebugLocFromInst(Builder, Gep); Value *PtrOperand = Gep->getPointerOperand(); Value *FirstBasePtr = getVectorValue(PtrOperand)[0]; FirstBasePtr = Builder.CreateExtractElement(FirstBasePtr, Zero); @@ -995,26 +1241,40 @@ void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr, Gep2->setName("gep.indvar.base"); Ptr = Builder.Insert(Gep2); } else if (Gep) { + setDebugLocFromInst(Builder, Gep); assert(SE->isLoopInvariant(SE->getSCEV(Gep->getPointerOperand()), OrigLoop) && "Base ptr must be invariant"); // The last index does not have to be the induction. It can be // consecutive and be a function of the index. For example A[I+1]; unsigned NumOperands = Gep->getNumOperands(); - - Value *LastGepOperand = Gep->getOperand(NumOperands - 1); - VectorParts &GEPParts = getVectorValue(LastGepOperand); - Value *LastIndex = GEPParts[0]; - LastIndex = Builder.CreateExtractElement(LastIndex, Zero); - + unsigned InductionOperand = getGEPInductionOperand(DL, Gep); // Create the new GEP with the new induction variable. GetElementPtrInst *Gep2 = cast<GetElementPtrInst>(Gep->clone()); - Gep2->setOperand(NumOperands - 1, LastIndex); - Gep2->setName("gep.indvar.idx"); + + for (unsigned i = 0; i < NumOperands; ++i) { + Value *GepOperand = Gep->getOperand(i); + Instruction *GepOperandInst = dyn_cast<Instruction>(GepOperand); + + // Update last index or loop invariant instruction anchored in loop. + if (i == InductionOperand || + (GepOperandInst && OrigLoop->contains(GepOperandInst))) { + assert((i == InductionOperand || + SE->isLoopInvariant(SE->getSCEV(GepOperandInst), OrigLoop)) && + "Must be last index or loop invariant"); + + VectorParts &GEPParts = getVectorValue(GepOperand); + Value *Index = GEPParts[0]; + Index = Builder.CreateExtractElement(Index, Zero); + Gep2->setOperand(i, Index); + Gep2->setName("gep.indvar.idx"); + } + } Ptr = Builder.Insert(Gep2); } else { // Use the induction element ptr. assert(isa<PHINode>(Ptr) && "Invalid induction ptr"); + setDebugLocFromInst(Builder, Ptr); VectorParts &PtrVal = getVectorValue(Ptr); Ptr = Builder.CreateExtractElement(PtrVal[0], Zero); } @@ -1023,8 +1283,11 @@ void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr, if (SI) { assert(!Legal->isUniform(SI->getPointerOperand()) && "We do not allow storing to uniform addresses"); + setDebugLocFromInst(Builder, SI); + // We don't want to update the value in the map as it might be used in + // another expression. So don't use a reference type for "StoredVal". + VectorParts StoredVal = getVectorValue(SI->getValueOperand()); - VectorParts &StoredVal = getVectorValue(SI->getValueOperand()); for (unsigned Part = 0; Part < UF; ++Part) { // Calculate the pointer for the specific unroll-part. Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF)); @@ -1039,11 +1302,16 @@ void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr, PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF)); } - Value *VecPtr = Builder.CreateBitCast(PartPtr, DataTy->getPointerTo()); + Value *VecPtr = Builder.CreateBitCast(PartPtr, + DataTy->getPointerTo(AddressSpace)); Builder.CreateStore(StoredVal[Part], VecPtr)->setAlignment(Alignment); } + return; } + // Handle loads. + assert(LI && "Must have a load instruction"); + setDebugLocFromInst(Builder, LI); for (unsigned Part = 0; Part < UF; ++Part) { // Calculate the pointer for the specific unroll-part. Value *PartPtr = Builder.CreateGEP(Ptr, Builder.getInt32(Part * VF)); @@ -1055,7 +1323,8 @@ void InnerLoopVectorizer::vectorizeMemoryInstruction(Instruction *Instr, PartPtr = Builder.CreateGEP(PartPtr, Builder.getInt32(1 - VF)); } - Value *VecPtr = Builder.CreateBitCast(PartPtr, DataTy->getPointerTo()); + Value *VecPtr = Builder.CreateBitCast(PartPtr, + DataTy->getPointerTo(AddressSpace)); Value *LI = Builder.CreateLoad(VecPtr, "wide.load"); cast<LoadInst>(LI)->setAlignment(Alignment); Entry[Part] = Reverse ? reverseVector(LI) : LI; @@ -1067,6 +1336,8 @@ void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr) { // Holds vector parameters or scalars, in case of uniform vals. SmallVector<VectorParts, 4> Params; + setDebugLocFromInst(Builder, Instr); + // Find all of the vectorized parameters. for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { Value *SrcOp = Instr->getOperand(op); @@ -1112,7 +1383,7 @@ void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr) { Instruction *Cloned = Instr->clone(); if (!IsVoidRetTy) Cloned->setName(Instr->getName() + ".cloned"); - // Replace the operands of the cloned instrucions with extracted scalars. + // Replace the operands of the cloned instructions with extracted scalars. for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { Value *Op = Params[op][Part]; // Param is a vector. Need to extract the right lane. @@ -1142,16 +1413,13 @@ InnerLoopVectorizer::addRuntimeCheck(LoopVectorizationLegality *Legal, if (!PtrRtCheck->Need) return NULL; - Instruction *MemoryRuntimeCheck = 0; unsigned NumPointers = PtrRtCheck->Pointers.size(); - SmallVector<Value* , 2> Starts; - SmallVector<Value* , 2> Ends; + SmallVector<TrackingVH<Value> , 2> Starts; + SmallVector<TrackingVH<Value> , 2> Ends; + LLVMContext &Ctx = Loc->getContext(); SCEVExpander Exp(*SE, "induction"); - // Use this type for pointer arithmetic. - Type* PtrArithTy = Type::getInt8PtrTy(Loc->getContext(), 0); - for (unsigned i = 0; i < NumPointers; ++i) { Value *Ptr = PtrRtCheck->Pointers[i]; const SCEV *Sc = SE->getSCEV(Ptr); @@ -1162,7 +1430,11 @@ InnerLoopVectorizer::addRuntimeCheck(LoopVectorizationLegality *Legal, Starts.push_back(Ptr); Ends.push_back(Ptr); } else { - DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr <<"\n"); + DEBUG(dbgs() << "LV: Adding RT check for range:" << *Ptr << '\n'); + unsigned AS = Ptr->getType()->getPointerAddressSpace(); + + // Use this type for pointer arithmetic. + Type *PtrArithTy = Type::getInt8PtrTy(Ctx, AS); Value *Start = Exp.expandCodeFor(PtrRtCheck->Starts[i], PtrArithTy, Loc); Value *End = Exp.expandCodeFor(PtrRtCheck->Ends[i], PtrArithTy, Loc); @@ -1172,17 +1444,32 @@ InnerLoopVectorizer::addRuntimeCheck(LoopVectorizationLegality *Legal, } IRBuilder<> ChkBuilder(Loc); - + // Our instructions might fold to a constant. + Value *MemoryRuntimeCheck = 0; for (unsigned i = 0; i < NumPointers; ++i) { for (unsigned j = i+1; j < NumPointers; ++j) { // No need to check if two readonly pointers intersect. if (!PtrRtCheck->IsWritePtr[i] && !PtrRtCheck->IsWritePtr[j]) continue; - Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy, "bc"); - Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy, "bc"); - Value *End0 = ChkBuilder.CreateBitCast(Ends[i], PtrArithTy, "bc"); - Value *End1 = ChkBuilder.CreateBitCast(Ends[j], PtrArithTy, "bc"); + // Only need to check pointers between two different dependency sets. + if (PtrRtCheck->DependencySetId[i] == PtrRtCheck->DependencySetId[j]) + continue; + + unsigned AS0 = Starts[i]->getType()->getPointerAddressSpace(); + unsigned AS1 = Starts[j]->getType()->getPointerAddressSpace(); + + assert((AS0 == Ends[j]->getType()->getPointerAddressSpace()) && + (AS1 == Ends[i]->getType()->getPointerAddressSpace()) && + "Trying to bounds check pointers with different address spaces"); + + Type *PtrArithTy0 = Type::getInt8PtrTy(Ctx, AS0); + Type *PtrArithTy1 = Type::getInt8PtrTy(Ctx, AS1); + + Value *Start0 = ChkBuilder.CreateBitCast(Starts[i], PtrArithTy0, "bc"); + Value *Start1 = ChkBuilder.CreateBitCast(Starts[j], PtrArithTy1, "bc"); + Value *End0 = ChkBuilder.CreateBitCast(Ends[i], PtrArithTy1, "bc"); + Value *End1 = ChkBuilder.CreateBitCast(Ends[j], PtrArithTy0, "bc"); Value *Cmp0 = ChkBuilder.CreateICmpULE(Start0, End1, "bound0"); Value *Cmp1 = ChkBuilder.CreateICmpULE(Start1, End0, "bound1"); @@ -1190,12 +1477,17 @@ InnerLoopVectorizer::addRuntimeCheck(LoopVectorizationLegality *Legal, if (MemoryRuntimeCheck) IsConflict = ChkBuilder.CreateOr(MemoryRuntimeCheck, IsConflict, "conflict.rdx"); - - MemoryRuntimeCheck = cast<Instruction>(IsConflict); + MemoryRuntimeCheck = IsConflict; } } - return MemoryRuntimeCheck; + // We have to do this trickery because the IRBuilder might fold the check to a + // constant expression in which case there is no Instruction anchored in a + // the block. + Instruction *Check = BinaryOperator::CreateAnd(MemoryRuntimeCheck, + ConstantInt::getTrue(Ctx)); + ChkBuilder.Insert(Check, "memcheck.conflict"); + return Check; } void @@ -1234,23 +1526,27 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { BasicBlock *ExitBlock = OrigLoop->getExitBlock(); assert(ExitBlock && "Must have an exit block"); - // Mark the old scalar loop with metadata that tells us not to vectorize this - // loop again if we run into it. - MDNode *MD = MDNode::get(OldBasicBlock->getContext(), None); - OldBasicBlock->getTerminator()->setMetadata(AlreadyVectorizedMDName, MD); - // Some loops have a single integer induction variable, while other loops // don't. One example is c++ iterators that often have multiple pointer // induction variables. In the code below we also support a case where we // don't have a single induction variable. OldInduction = Legal->getInduction(); - Type *IdxTy = OldInduction ? OldInduction->getType() : - DL->getIntPtrType(SE->getContext()); + Type *IdxTy = Legal->getWidestInductionType(); // Find the loop boundaries. - const SCEV *ExitCount = SE->getExitCount(OrigLoop, OrigLoop->getLoopLatch()); + const SCEV *ExitCount = SE->getBackedgeTakenCount(OrigLoop); assert(ExitCount != SE->getCouldNotCompute() && "Invalid loop count"); + // The exit count might have the type of i64 while the phi is i32. This can + // happen if we have an induction variable that is sign extended before the + // compare. The only way that we get a backedge taken count is that the + // induction variable was signed and as such will not overflow. In such a case + // truncation is legal. + if (ExitCount->getType()->getPrimitiveSizeInBits() > + IdxTy->getPrimitiveSizeInBits()) + ExitCount = SE->getTruncateOrNoop(ExitCount, IdxTy); + + ExitCount = SE->getNoopOrZeroExtend(ExitCount, IdxTy); // Get the total trip count from the count by adding 1. ExitCount = SE->getAddExpr(ExitCount, SE->getConstant(ExitCount->getType(), 1)); @@ -1266,9 +1562,11 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { // The loop index does not have to start at Zero. Find the original start // value from the induction PHI node. If we don't have an induction variable // then we know that it starts at zero. - Value *StartIdx = OldInduction ? - OldInduction->getIncomingValueForBlock(BypassBlock): - ConstantInt::get(IdxTy, 0); + Builder.SetInsertPoint(BypassBlock->getTerminator()); + Value *StartIdx = ExtendedIdx = OldInduction ? + Builder.CreateZExt(OldInduction->getIncomingValueForBlock(BypassBlock), + IdxTy): + ConstantInt::get(IdxTy, 0); assert(BypassBlock && "Invalid loop structure"); LoopBypassBlocks.push_back(BypassBlock); @@ -1283,11 +1581,28 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { BasicBlock *ScalarPH = MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph"); + // Create and register the new vector loop. + Loop* Lp = new Loop(); + Loop *ParentLoop = OrigLoop->getParentLoop(); + + // Insert the new loop into the loop nest and register the new basic blocks + // before calling any utilities such as SCEV that require valid LoopInfo. + if (ParentLoop) { + ParentLoop->addChildLoop(Lp); + ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase()); + ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase()); + ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase()); + } else { + LI->addTopLevelLoop(Lp); + } + Lp->addBasicBlockToLoop(VecBody, LI->getBase()); + // Use this IR builder to create the loop instructions (Phi, Br, Cmp) // inside the loop. - Builder.SetInsertPoint(VecBody->getFirstInsertionPt()); + Builder.SetInsertPoint(VecBody->getFirstNonPHI()); // Generate the induction variable. + setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction)); Induction = Builder.CreatePHI(IdxTy, 2, "index"); // The loop step is equal to the vectorization factor (num of SIMD elements) // times the unroll factor (num of SIMD instructions). @@ -1296,6 +1611,8 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { // This is the IR builder that we use to add all of the logic for bypassing // the new vector loop. IRBuilder<> BypassBuilder(BypassBlock->getTerminator()); + setDebugLocFromInst(BypassBuilder, + getDebugLocFromInstOrOperands(OldInduction)); // We may need to extend the index in case there is a type mismatch. // We know that the count starts at zero and does not overflow. @@ -1334,6 +1651,8 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { // Create a new block containing the memory check. BasicBlock *CheckBlock = BypassBlock->splitBasicBlock(MemRuntimeCheck, "vector.memcheck"); + if (ParentLoop) + ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase()); LoopBypassBlocks.push_back(CheckBlock); // Replace the branch into the memory check block with a conditional branch @@ -1362,76 +1681,101 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { PHINode *ResumeIndex = 0; LoopVectorizationLegality::InductionList::iterator I, E; LoopVectorizationLegality::InductionList *List = Legal->getInductionVars(); + // Set builder to point to last bypass block. + BypassBuilder.SetInsertPoint(LoopBypassBlocks.back()->getTerminator()); for (I = List->begin(), E = List->end(); I != E; ++I) { PHINode *OrigPhi = I->first; LoopVectorizationLegality::InductionInfo II = I->second; - PHINode *ResumeVal = PHINode::Create(OrigPhi->getType(), 2, "resume.val", + + Type *ResumeValTy = (OrigPhi == OldInduction) ? IdxTy : OrigPhi->getType(); + PHINode *ResumeVal = PHINode::Create(ResumeValTy, 2, "resume.val", MiddleBlock->getTerminator()); + // We might have extended the type of the induction variable but we need a + // truncated version for the scalar loop. + PHINode *TruncResumeVal = (OrigPhi == OldInduction) ? + PHINode::Create(OrigPhi->getType(), 2, "trunc.resume.val", + MiddleBlock->getTerminator()) : 0; + Value *EndValue = 0; switch (II.IK) { case LoopVectorizationLegality::IK_NoInduction: llvm_unreachable("Unknown induction"); case LoopVectorizationLegality::IK_IntInduction: { - // Handle the integer induction counter: + // Handle the integer induction counter. assert(OrigPhi->getType()->isIntegerTy() && "Invalid type"); - assert(OrigPhi == OldInduction && "Unknown integer PHI"); - // We know what the end value is. - EndValue = IdxEndRoundDown; - // We also know which PHI node holds it. - ResumeIndex = ResumeVal; + + // We have the canonical induction variable. + if (OrigPhi == OldInduction) { + // Create a truncated version of the resume value for the scalar loop, + // we might have promoted the type to a larger width. + EndValue = + BypassBuilder.CreateTrunc(IdxEndRoundDown, OrigPhi->getType()); + // The new PHI merges the original incoming value, in case of a bypass, + // or the value at the end of the vectorized loop. + for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) + TruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); + TruncResumeVal->addIncoming(EndValue, VecBody); + + // We know what the end value is. + EndValue = IdxEndRoundDown; + // We also know which PHI node holds it. + ResumeIndex = ResumeVal; + break; + } + + // Not the canonical induction variable - add the vector loop count to the + // start value. + Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown, + II.StartValue->getType(), + "cast.crd"); + EndValue = BypassBuilder.CreateAdd(CRD, II.StartValue , "ind.end"); break; } case LoopVectorizationLegality::IK_ReverseIntInduction: { // Convert the CountRoundDown variable to the PHI size. - unsigned CRDSize = CountRoundDown->getType()->getScalarSizeInBits(); - unsigned IISize = II.StartValue->getType()->getScalarSizeInBits(); - Value *CRD = CountRoundDown; - if (CRDSize > IISize) - CRD = CastInst::Create(Instruction::Trunc, CountRoundDown, - II.StartValue->getType(), "tr.crd", - LoopBypassBlocks.back()->getTerminator()); - else if (CRDSize < IISize) - CRD = CastInst::Create(Instruction::SExt, CountRoundDown, - II.StartValue->getType(), - "sext.crd", - LoopBypassBlocks.back()->getTerminator()); - // Handle reverse integer induction counter: - EndValue = - BinaryOperator::CreateSub(II.StartValue, CRD, "rev.ind.end", - LoopBypassBlocks.back()->getTerminator()); + Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown, + II.StartValue->getType(), + "cast.crd"); + // Handle reverse integer induction counter. + EndValue = BypassBuilder.CreateSub(II.StartValue, CRD, "rev.ind.end"); break; } case LoopVectorizationLegality::IK_PtrInduction: { // For pointer induction variables, calculate the offset using // the end index. - EndValue = - GetElementPtrInst::Create(II.StartValue, CountRoundDown, "ptr.ind.end", - LoopBypassBlocks.back()->getTerminator()); + EndValue = BypassBuilder.CreateGEP(II.StartValue, CountRoundDown, + "ptr.ind.end"); break; } case LoopVectorizationLegality::IK_ReversePtrInduction: { // The value at the end of the loop for the reverse pointer is calculated // by creating a GEP with a negative index starting from the start value. Value *Zero = ConstantInt::get(CountRoundDown->getType(), 0); - Value *NegIdx = BinaryOperator::CreateSub(Zero, CountRoundDown, - "rev.ind.end", - LoopBypassBlocks.back()->getTerminator()); - EndValue = GetElementPtrInst::Create(II.StartValue, NegIdx, - "rev.ptr.ind.end", - LoopBypassBlocks.back()->getTerminator()); + Value *NegIdx = BypassBuilder.CreateSub(Zero, CountRoundDown, + "rev.ind.end"); + EndValue = BypassBuilder.CreateGEP(II.StartValue, NegIdx, + "rev.ptr.ind.end"); break; } }// end of case // The new PHI merges the original incoming value, in case of a bypass, // or the value at the end of the vectorized loop. - for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) - ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); + for (unsigned I = 0, E = LoopBypassBlocks.size(); I != E; ++I) { + if (OrigPhi == OldInduction) + ResumeVal->addIncoming(StartIdx, LoopBypassBlocks[I]); + else + ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); + } ResumeVal->addIncoming(EndValue, VecBody); // Fix the scalar body counter (PHI node). unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH); - OrigPhi->setIncomingValue(BlockIdx, ResumeVal); + // The old inductions phi node in the scalar body needs the truncated value. + if (OrigPhi == OldInduction) + OrigPhi->setIncomingValue(BlockIdx, TruncResumeVal); + else + OrigPhi->setIncomingValue(BlockIdx, ResumeVal); } // If we are generating a new induction variable then we also need to @@ -1476,24 +1820,6 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { // Get ready to start creating new instructions into the vectorized body. Builder.SetInsertPoint(VecBody->getFirstInsertionPt()); - // Create and register the new vector loop. - Loop* Lp = new Loop(); - Loop *ParentLoop = OrigLoop->getParentLoop(); - - // Insert the new loop into the loop nest and register the new basic blocks. - if (ParentLoop) { - ParentLoop->addChildLoop(Lp); - for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I) - ParentLoop->addBasicBlockToLoop(LoopBypassBlocks[I], LI->getBase()); - ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase()); - ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase()); - ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase()); - } else { - LI->addTopLevelLoop(Lp); - } - - Lp->addBasicBlockToLoop(VecBody, LI->getBase()); - // Save the state. LoopVectorPreHeader = VectorPH; LoopScalarPreHeader = ScalarPH; @@ -1501,6 +1827,9 @@ InnerLoopVectorizer::createEmptyLoop(LoopVectorizationLegality *Legal) { LoopExitBlock = ExitBlock; LoopVectorBody = VecBody; LoopScalarBody = OldBasicBlock; + + LoopVectorizeHints Hints(Lp, true); + Hints.setAlreadyVectorized(Lp); } /// This function returns the identity element (or neutral element) for @@ -1530,6 +1859,31 @@ LoopVectorizationLegality::getReductionIdentity(ReductionKind K, Type *Tp) { } } +static Intrinsic::ID checkUnaryFloatSignature(const CallInst &I, + Intrinsic::ID ValidIntrinsicID) { + if (I.getNumArgOperands() != 1 || + !I.getArgOperand(0)->getType()->isFloatingPointTy() || + I.getType() != I.getArgOperand(0)->getType() || + !I.onlyReadsMemory()) + return Intrinsic::not_intrinsic; + + return ValidIntrinsicID; +} + +static Intrinsic::ID checkBinaryFloatSignature(const CallInst &I, + Intrinsic::ID ValidIntrinsicID) { + if (I.getNumArgOperands() != 2 || + !I.getArgOperand(0)->getType()->isFloatingPointTy() || + !I.getArgOperand(1)->getType()->isFloatingPointTy() || + I.getType() != I.getArgOperand(0)->getType() || + I.getType() != I.getArgOperand(1)->getType() || + !I.onlyReadsMemory()) + return Intrinsic::not_intrinsic; + + return ValidIntrinsicID; +} + + static Intrinsic::ID getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) { // If we have an intrinsic call, check if it is trivially vectorizable. @@ -1544,14 +1898,18 @@ getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) { case Intrinsic::log10: case Intrinsic::log2: case Intrinsic::fabs: + case Intrinsic::copysign: case Intrinsic::floor: case Intrinsic::ceil: case Intrinsic::trunc: case Intrinsic::rint: case Intrinsic::nearbyint: + case Intrinsic::round: case Intrinsic::pow: case Intrinsic::fma: case Intrinsic::fmuladd: + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: return II->getIntrinsicID(); default: return Intrinsic::not_intrinsic; @@ -1564,8 +1922,9 @@ getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) { LibFunc::Func Func; Function *F = CI->getCalledFunction(); // We're going to make assumptions on the semantics of the functions, check - // that the target knows that it's available in this environment. - if (!F || !TLI->getLibFunc(F->getName(), Func)) + // that the target knows that it's available in this environment and it does + // not have local linkage. + if (!F || F->hasLocalLinkage() || !TLI->getLibFunc(F->getName(), Func)) return Intrinsic::not_intrinsic; // Otherwise check if we have a call to a function that can be turned into a @@ -1576,59 +1935,67 @@ getIntrinsicIDForCall(CallInst *CI, const TargetLibraryInfo *TLI) { case LibFunc::sin: case LibFunc::sinf: case LibFunc::sinl: - return Intrinsic::sin; + return checkUnaryFloatSignature(*CI, Intrinsic::sin); case LibFunc::cos: case LibFunc::cosf: case LibFunc::cosl: - return Intrinsic::cos; + return checkUnaryFloatSignature(*CI, Intrinsic::cos); case LibFunc::exp: case LibFunc::expf: case LibFunc::expl: - return Intrinsic::exp; + return checkUnaryFloatSignature(*CI, Intrinsic::exp); case LibFunc::exp2: case LibFunc::exp2f: case LibFunc::exp2l: - return Intrinsic::exp2; + return checkUnaryFloatSignature(*CI, Intrinsic::exp2); case LibFunc::log: case LibFunc::logf: case LibFunc::logl: - return Intrinsic::log; + return checkUnaryFloatSignature(*CI, Intrinsic::log); case LibFunc::log10: case LibFunc::log10f: case LibFunc::log10l: - return Intrinsic::log10; + return checkUnaryFloatSignature(*CI, Intrinsic::log10); case LibFunc::log2: case LibFunc::log2f: case LibFunc::log2l: - return Intrinsic::log2; + return checkUnaryFloatSignature(*CI, Intrinsic::log2); case LibFunc::fabs: case LibFunc::fabsf: case LibFunc::fabsl: - return Intrinsic::fabs; + return checkUnaryFloatSignature(*CI, Intrinsic::fabs); + case LibFunc::copysign: + case LibFunc::copysignf: + case LibFunc::copysignl: + return checkBinaryFloatSignature(*CI, Intrinsic::copysign); case LibFunc::floor: case LibFunc::floorf: case LibFunc::floorl: - return Intrinsic::floor; + return checkUnaryFloatSignature(*CI, Intrinsic::floor); case LibFunc::ceil: case LibFunc::ceilf: case LibFunc::ceill: - return Intrinsic::ceil; + return checkUnaryFloatSignature(*CI, Intrinsic::ceil); case LibFunc::trunc: case LibFunc::truncf: case LibFunc::truncl: - return Intrinsic::trunc; + return checkUnaryFloatSignature(*CI, Intrinsic::trunc); case LibFunc::rint: case LibFunc::rintf: case LibFunc::rintl: - return Intrinsic::rint; + return checkUnaryFloatSignature(*CI, Intrinsic::rint); case LibFunc::nearbyint: case LibFunc::nearbyintf: case LibFunc::nearbyintl: - return Intrinsic::nearbyint; + return checkUnaryFloatSignature(*CI, Intrinsic::nearbyint); + case LibFunc::round: + case LibFunc::roundf: + case LibFunc::roundl: + return checkUnaryFloatSignature(*CI, Intrinsic::round); case LibFunc::pow: case LibFunc::powf: case LibFunc::powl: - return Intrinsic::pow; + return checkBinaryFloatSignature(*CI, Intrinsic::pow); } return Intrinsic::not_intrinsic; @@ -1690,7 +2057,8 @@ Value *createMinMaxOp(IRBuilder<> &Builder, } Value *Cmp; - if (RK == LoopVectorizationLegality::MRK_FloatMin || RK == LoopVectorizationLegality::MRK_FloatMax) + if (RK == LoopVectorizationLegality::MRK_FloatMin || + RK == LoopVectorizationLegality::MRK_FloatMax) Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); else Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); @@ -1699,6 +2067,54 @@ Value *createMinMaxOp(IRBuilder<> &Builder, return Select; } +namespace { +struct CSEDenseMapInfo { + static bool canHandle(Instruction *I) { + return isa<InsertElementInst>(I) || isa<ExtractElementInst>(I) || + isa<ShuffleVectorInst>(I) || isa<GetElementPtrInst>(I); + } + static inline Instruction *getEmptyKey() { + return DenseMapInfo<Instruction *>::getEmptyKey(); + } + static inline Instruction *getTombstoneKey() { + return DenseMapInfo<Instruction *>::getTombstoneKey(); + } + static unsigned getHashValue(Instruction *I) { + assert(canHandle(I) && "Unknown instruction!"); + return hash_combine(I->getOpcode(), hash_combine_range(I->value_op_begin(), + I->value_op_end())); + } + static bool isEqual(Instruction *LHS, Instruction *RHS) { + if (LHS == getEmptyKey() || RHS == getEmptyKey() || + LHS == getTombstoneKey() || RHS == getTombstoneKey()) + return LHS == RHS; + return LHS->isIdenticalTo(RHS); + } +}; +} + +///\brief Perform cse of induction variable instructions. +static void cse(BasicBlock *BB) { + // Perform simple cse. + SmallDenseMap<Instruction *, Instruction *, 4, CSEDenseMapInfo> CSEMap; + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E;) { + Instruction *In = I++; + + if (!CSEDenseMapInfo::canHandle(In)) + continue; + + // Check if we can replace this instruction with any of the + // visited instructions. + if (Instruction *V = CSEMap.lookup(In)) { + In->replaceAllUsesWith(V); + In->eraseFromParent(); + continue; + } + + CSEMap[In] = In; + } +} + void InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { //===------------------------------------------------===// @@ -1750,6 +2166,8 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { LoopVectorizationLegality::ReductionDescriptor RdxDesc = (*Legal->getReductionVars())[RdxPhi]; + setDebugLocFromInst(Builder, RdxDesc.StartValue); + // We need to generate a reduction vector from the incoming scalar. // To do so, we need to generate the 'identity' vector and overide // one of the elements with the incoming scalar reduction. We need @@ -1767,18 +2185,31 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax || RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) { // MinMax reduction have the start value as their identify. - VectorStart = Identity = Builder.CreateVectorSplat(VF, RdxDesc.StartValue, - "minmax.ident"); + if (VF == 1) { + VectorStart = Identity = RdxDesc.StartValue; + } else { + VectorStart = Identity = Builder.CreateVectorSplat(VF, + RdxDesc.StartValue, + "minmax.ident"); + } } else { + // Handle other reduction kinds: Constant *Iden = - LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind, - VecTy->getScalarType()); - Identity = ConstantVector::getSplat(VF, Iden); - - // This vector is the Identity vector where the first element is the - // incoming scalar reduction. - VectorStart = Builder.CreateInsertElement(Identity, - RdxDesc.StartValue, Zero); + LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind, + VecTy->getScalarType()); + if (VF == 1) { + Identity = Iden; + // This vector is the Identity vector where the first element is the + // incoming scalar reduction. + VectorStart = RdxDesc.StartValue; + } else { + Identity = ConstantVector::getSplat(VF, Iden); + + // This vector is the Identity vector where the first element is the + // incoming scalar reduction. + VectorStart = Builder.CreateInsertElement(Identity, + RdxDesc.StartValue, Zero); + } } // Fix the vector-loop phi. @@ -1793,7 +2224,7 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { Value *LoopVal = RdxPhi->getIncomingValueForBlock(Latch); VectorParts &Val = getVectorValue(LoopVal); for (unsigned part = 0; part < UF; ++part) { - // Make sure to add the reduction stat value only to the + // Make sure to add the reduction stat value only to the // first unroll part. Value *StartVal = (part == 0) ? VectorStart : Identity; cast<PHINode>(VecRdxPhi[part])->addIncoming(StartVal, VecPreheader); @@ -1807,6 +2238,7 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt()); VectorParts RdxParts; + setDebugLocFromInst(Builder, RdxDesc.LoopExitInstr); for (unsigned part = 0; part < UF; ++part) { // This PHINode contains the vectorized reduction variable, or // the initial value vector, if we bypass the vector loop. @@ -1822,6 +2254,7 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { // Reduce all of the unrolled parts into a single vector. Value *ReducedPartRdx = RdxParts[0]; unsigned Op = getReductionBinOp(RdxDesc.Kind); + setDebugLocFromInst(Builder, ReducedPartRdx); for (unsigned part = 1; part < UF; ++part) { if (Op != Instruction::ICmp && Op != Instruction::FCmp) ReducedPartRdx = Builder.CreateBinOp((Instruction::BinaryOps)Op, @@ -1832,37 +2265,40 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { ReducedPartRdx, RdxParts[part]); } - // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles - // and vector ops, reducing the set of values being computed by half each - // round. - assert(isPowerOf2_32(VF) && - "Reduction emission only supported for pow2 vectors!"); - Value *TmpVec = ReducedPartRdx; - SmallVector<Constant*, 32> ShuffleMask(VF, 0); - for (unsigned i = VF; i != 1; i >>= 1) { - // Move the upper half of the vector to the lower half. - for (unsigned j = 0; j != i/2; ++j) - ShuffleMask[j] = Builder.getInt32(i/2 + j); - - // Fill the rest of the mask with undef. - std::fill(&ShuffleMask[i/2], ShuffleMask.end(), - UndefValue::get(Builder.getInt32Ty())); - - Value *Shuf = + if (VF > 1) { + // VF is a power of 2 so we can emit the reduction using log2(VF) shuffles + // and vector ops, reducing the set of values being computed by half each + // round. + assert(isPowerOf2_32(VF) && + "Reduction emission only supported for pow2 vectors!"); + Value *TmpVec = ReducedPartRdx; + SmallVector<Constant*, 32> ShuffleMask(VF, 0); + for (unsigned i = VF; i != 1; i >>= 1) { + // Move the upper half of the vector to the lower half. + for (unsigned j = 0; j != i/2; ++j) + ShuffleMask[j] = Builder.getInt32(i/2 + j); + + // Fill the rest of the mask with undef. + std::fill(&ShuffleMask[i/2], ShuffleMask.end(), + UndefValue::get(Builder.getInt32Ty())); + + Value *Shuf = Builder.CreateShuffleVector(TmpVec, UndefValue::get(TmpVec->getType()), ConstantVector::get(ShuffleMask), "rdx.shuf"); - if (Op != Instruction::ICmp && Op != Instruction::FCmp) - TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf, - "bin.rdx"); - else - TmpVec = createMinMaxOp(Builder, RdxDesc.MinMaxKind, TmpVec, Shuf); - } + if (Op != Instruction::ICmp && Op != Instruction::FCmp) + TmpVec = Builder.CreateBinOp((Instruction::BinaryOps)Op, TmpVec, Shuf, + "bin.rdx"); + else + TmpVec = createMinMaxOp(Builder, RdxDesc.MinMaxKind, TmpVec, Shuf); + } - // The result is in the first element of the vector. - Value *Scalar0 = Builder.CreateExtractElement(TmpVec, Builder.getInt32(0)); + // The result is in the first element of the vector. + ReducedPartRdx = Builder.CreateExtractElement(TmpVec, + Builder.getInt32(0)); + } // Now, we need to fix the users of the reduction variable // inside and outside of the scalar remainder loop. @@ -1871,7 +2307,7 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { for (BasicBlock::iterator LEI = LoopExitBlock->begin(), LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) { PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI); - if (!LCSSAPhi) continue; + if (!LCSSAPhi) break; // All PHINodes need to have a single entry edge, or two if // we already fixed them. @@ -1881,7 +2317,7 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { // incoming bypass edge. if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) { // Add an edge coming from the bypass. - LCSSAPhi->addIncoming(Scalar0, LoopMiddleBlock); + LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock); break; } }// end of the LCSSA phi scan. @@ -1893,29 +2329,38 @@ InnerLoopVectorizer::vectorizeLoop(LoopVectorizationLegality *Legal) { assert(IncomingEdgeBlockIdx >= 0 && "Invalid block index"); // Pick the other block. int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1); - (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, Scalar0); + (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, ReducedPartRdx); (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr); }// end of for each redux variable. - // The Loop exit block may have single value PHI nodes where the incoming - // value is 'undef'. While vectorizing we only handled real values that - // were defined inside the loop. Here we handle the 'undef case'. - // See PR14725. + fixLCSSAPHIs(); + + // Remove redundant induction instructions. + cse(LoopVectorBody); +} + +void InnerLoopVectorizer::fixLCSSAPHIs() { for (BasicBlock::iterator LEI = LoopExitBlock->begin(), LEE = LoopExitBlock->end(); LEI != LEE; ++LEI) { PHINode *LCSSAPhi = dyn_cast<PHINode>(LEI); - if (!LCSSAPhi) continue; + if (!LCSSAPhi) break; if (LCSSAPhi->getNumIncomingValues() == 1) LCSSAPhi->addIncoming(UndefValue::get(LCSSAPhi->getType()), LoopMiddleBlock); } -} +} InnerLoopVectorizer::VectorParts InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) { assert(std::find(pred_begin(Dst), pred_end(Dst), Src) != pred_end(Dst) && "Invalid edge"); + // Look for cached value. + std::pair<BasicBlock*, BasicBlock*> Edge(Src, Dst); + EdgeMaskCache::iterator ECEntryIt = MaskCache.find(Edge); + if (ECEntryIt != MaskCache.end()) + return ECEntryIt->second; + VectorParts SrcMask = createBlockInMask(Src); // The terminator has to be a branch inst! @@ -1931,9 +2376,12 @@ InnerLoopVectorizer::createEdgeMask(BasicBlock *Src, BasicBlock *Dst) { for (unsigned part = 0; part < UF; ++part) EdgeMask[part] = Builder.CreateAnd(EdgeMask[part], SrcMask[part]); + + MaskCache[Edge] = EdgeMask; return EdgeMask; } + MaskCache[Edge] = SrcMask; return SrcMask; } @@ -1961,154 +2409,185 @@ InnerLoopVectorizer::createBlockInMask(BasicBlock *BB) { return BlockMask; } -void -InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, - BasicBlock *BB, PhiVector *PV) { - // For each instruction in the old loop. - for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { - VectorParts &Entry = WidenMap.get(it); - switch (it->getOpcode()) { - case Instruction::Br: - // Nothing to do for PHIs and BR, since we already took care of the - // loop control flow instructions. - continue; - case Instruction::PHI:{ - PHINode* P = cast<PHINode>(it); - // Handle reduction variables: - if (Legal->getReductionVars()->count(P)) { - for (unsigned part = 0; part < UF; ++part) { - // This is phase one of vectorizing PHIs. - Type *VecTy = VectorType::get(it->getType(), VF); - Entry[part] = PHINode::Create(VecTy, 2, "vec.phi", - LoopVectorBody-> getFirstInsertionPt()); - } - PV->push_back(P); - continue; - } +void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN, + InnerLoopVectorizer::VectorParts &Entry, + LoopVectorizationLegality *Legal, + unsigned UF, unsigned VF, PhiVector *PV) { + PHINode* P = cast<PHINode>(PN); + // Handle reduction variables: + if (Legal->getReductionVars()->count(P)) { + for (unsigned part = 0; part < UF; ++part) { + // This is phase one of vectorizing PHIs. + Type *VecTy = (VF == 1) ? PN->getType() : + VectorType::get(PN->getType(), VF); + Entry[part] = PHINode::Create(VecTy, 2, "vec.phi", + LoopVectorBody-> getFirstInsertionPt()); + } + PV->push_back(P); + return; + } - // Check for PHI nodes that are lowered to vector selects. - if (P->getParent() != OrigLoop->getHeader()) { - // We know that all PHIs in non header blocks are converted into - // selects, so we don't have to worry about the insertion order and we - // can just use the builder. - // At this point we generate the predication tree. There may be - // duplications since this is a simple recursive scan, but future - // optimizations will clean it up. - - unsigned NumIncoming = P->getNumIncomingValues(); - assert(NumIncoming > 1 && "Invalid PHI"); - - // Generate a sequence of selects of the form: - // SELECT(Mask3, In3, - // SELECT(Mask2, In2, - // ( ...))) - for (unsigned In = 0; In < NumIncoming; In++) { - VectorParts Cond = createEdgeMask(P->getIncomingBlock(In), - P->getParent()); - VectorParts &In0 = getVectorValue(P->getIncomingValue(In)); - - for (unsigned part = 0; part < UF; ++part) { - // We don't need to 'select' the first PHI operand because it is - // the default value if all of the other masks don't match. - if (In == 0) - Entry[part] = In0[part]; - else - // Select between the current value and the previous incoming edge - // based on the incoming mask. - Entry[part] = Builder.CreateSelect(Cond[part], In0[part], - Entry[part], "predphi"); - } - } - continue; + setDebugLocFromInst(Builder, P); + // Check for PHI nodes that are lowered to vector selects. + if (P->getParent() != OrigLoop->getHeader()) { + // We know that all PHIs in non header blocks are converted into + // selects, so we don't have to worry about the insertion order and we + // can just use the builder. + // At this point we generate the predication tree. There may be + // duplications since this is a simple recursive scan, but future + // optimizations will clean it up. + + unsigned NumIncoming = P->getNumIncomingValues(); + + // Generate a sequence of selects of the form: + // SELECT(Mask3, In3, + // SELECT(Mask2, In2, + // ( ...))) + for (unsigned In = 0; In < NumIncoming; In++) { + VectorParts Cond = createEdgeMask(P->getIncomingBlock(In), + P->getParent()); + VectorParts &In0 = getVectorValue(P->getIncomingValue(In)); + + for (unsigned part = 0; part < UF; ++part) { + // We might have single edge PHIs (blocks) - use an identity + // 'select' for the first PHI operand. + if (In == 0) + Entry[part] = Builder.CreateSelect(Cond[part], In0[part], + In0[part]); + else + // Select between the current value and the previous incoming edge + // based on the incoming mask. + Entry[part] = Builder.CreateSelect(Cond[part], In0[part], + Entry[part], "predphi"); } + } + return; + } - // This PHINode must be an induction variable. - // Make sure that we know about it. - assert(Legal->getInductionVars()->count(P) && - "Not an induction variable"); + // This PHINode must be an induction variable. + // Make sure that we know about it. + assert(Legal->getInductionVars()->count(P) && + "Not an induction variable"); - LoopVectorizationLegality::InductionInfo II = - Legal->getInductionVars()->lookup(P); + LoopVectorizationLegality::InductionInfo II = + Legal->getInductionVars()->lookup(P); - switch (II.IK) { - case LoopVectorizationLegality::IK_NoInduction: - llvm_unreachable("Unknown induction"); - case LoopVectorizationLegality::IK_IntInduction: { - assert(P == OldInduction && "Unexpected PHI"); - Value *Broadcasted = getBroadcastInstrs(Induction); + switch (II.IK) { + case LoopVectorizationLegality::IK_NoInduction: + llvm_unreachable("Unknown induction"); + case LoopVectorizationLegality::IK_IntInduction: { + assert(P->getType() == II.StartValue->getType() && "Types must match"); + Type *PhiTy = P->getType(); + Value *Broadcasted; + if (P == OldInduction) { + // Handle the canonical induction variable. We might have had to + // extend the type. + Broadcasted = Builder.CreateTrunc(Induction, PhiTy); + } else { + // Handle other induction variables that are now based on the + // canonical one. + Value *NormalizedIdx = Builder.CreateSub(Induction, ExtendedIdx, + "normalized.idx"); + NormalizedIdx = Builder.CreateSExtOrTrunc(NormalizedIdx, PhiTy); + Broadcasted = Builder.CreateAdd(II.StartValue, NormalizedIdx, + "offset.idx"); + } + Broadcasted = getBroadcastInstrs(Broadcasted); + // After broadcasting the induction variable we need to make the vector + // consecutive by adding 0, 1, 2, etc. + for (unsigned part = 0; part < UF; ++part) + Entry[part] = getConsecutiveVector(Broadcasted, VF * part, false); + return; + } + case LoopVectorizationLegality::IK_ReverseIntInduction: + case LoopVectorizationLegality::IK_PtrInduction: + case LoopVectorizationLegality::IK_ReversePtrInduction: + // Handle reverse integer and pointer inductions. + Value *StartIdx = ExtendedIdx; + // This is the normalized GEP that starts counting at zero. + Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx, + "normalized.idx"); + + // Handle the reverse integer induction variable case. + if (LoopVectorizationLegality::IK_ReverseIntInduction == II.IK) { + IntegerType *DstTy = cast<IntegerType>(II.StartValue->getType()); + Value *CNI = Builder.CreateSExtOrTrunc(NormalizedIdx, DstTy, + "resize.norm.idx"); + Value *ReverseInd = Builder.CreateSub(II.StartValue, CNI, + "reverse.idx"); + + // This is a new value so do not hoist it out. + Value *Broadcasted = getBroadcastInstrs(ReverseInd); // After broadcasting the induction variable we need to make the - // vector consecutive by adding 0, 1, 2 ... + // vector consecutive by adding ... -3, -2, -1, 0. for (unsigned part = 0; part < UF; ++part) - Entry[part] = getConsecutiveVector(Broadcasted, VF * part, false); - continue; + Entry[part] = getConsecutiveVector(Broadcasted, -(int)VF * part, + true); + return; } - case LoopVectorizationLegality::IK_ReverseIntInduction: - case LoopVectorizationLegality::IK_PtrInduction: - case LoopVectorizationLegality::IK_ReversePtrInduction: - // Handle reverse integer and pointer inductions. - Value *StartIdx = 0; - // If we have a single integer induction variable then use it. - // Otherwise, start counting at zero. - if (OldInduction) { - LoopVectorizationLegality::InductionInfo OldII = - Legal->getInductionVars()->lookup(OldInduction); - StartIdx = OldII.StartValue; - } else { - StartIdx = ConstantInt::get(Induction->getType(), 0); - } - // This is the normalized GEP that starts counting at zero. - Value *NormalizedIdx = Builder.CreateSub(Induction, StartIdx, - "normalized.idx"); - // Handle the reverse integer induction variable case. - if (LoopVectorizationLegality::IK_ReverseIntInduction == II.IK) { - IntegerType *DstTy = cast<IntegerType>(II.StartValue->getType()); - Value *CNI = Builder.CreateSExtOrTrunc(NormalizedIdx, DstTy, - "resize.norm.idx"); - Value *ReverseInd = Builder.CreateSub(II.StartValue, CNI, - "reverse.idx"); - - // This is a new value so do not hoist it out. - Value *Broadcasted = getBroadcastInstrs(ReverseInd); - // After broadcasting the induction variable we need to make the - // vector consecutive by adding ... -3, -2, -1, 0. - for (unsigned part = 0; part < UF; ++part) - Entry[part] = getConsecutiveVector(Broadcasted, -(int)VF * part, - true); + // Handle the pointer induction variable case. + assert(P->getType()->isPointerTy() && "Unexpected type."); + + // Is this a reverse induction ptr or a consecutive induction ptr. + bool Reverse = (LoopVectorizationLegality::IK_ReversePtrInduction == + II.IK); + + // This is the vector of results. Notice that we don't generate + // vector geps because scalar geps result in better code. + for (unsigned part = 0; part < UF; ++part) { + if (VF == 1) { + int EltIndex = (part) * (Reverse ? -1 : 1); + Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex); + Value *GlobalIdx; + if (Reverse) + GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx"); + else + GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx"); + + Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx, + "next.gep"); + Entry[part] = SclrGep; continue; } - // Handle the pointer induction variable case. - assert(P->getType()->isPointerTy() && "Unexpected type."); - - // Is this a reverse induction ptr or a consecutive induction ptr. - bool Reverse = (LoopVectorizationLegality::IK_ReversePtrInduction == - II.IK); - - // This is the vector of results. Notice that we don't generate - // vector geps because scalar geps result in better code. - for (unsigned part = 0; part < UF; ++part) { - Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF)); - for (unsigned int i = 0; i < VF; ++i) { - int EltIndex = (i + part * VF) * (Reverse ? -1 : 1); - Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex); - Value *GlobalIdx; - if (!Reverse) - GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx"); - else - GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx"); - - Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx, - "next.gep"); - VecVal = Builder.CreateInsertElement(VecVal, SclrGep, - Builder.getInt32(i), - "insert.gep"); - } - Entry[part] = VecVal; + Value *VecVal = UndefValue::get(VectorType::get(P->getType(), VF)); + for (unsigned int i = 0; i < VF; ++i) { + int EltIndex = (i + part * VF) * (Reverse ? -1 : 1); + Constant *Idx = ConstantInt::get(Induction->getType(), EltIndex); + Value *GlobalIdx; + if (!Reverse) + GlobalIdx = Builder.CreateAdd(NormalizedIdx, Idx, "gep.idx"); + else + GlobalIdx = Builder.CreateSub(Idx, NormalizedIdx, "gep.ridx"); + + Value *SclrGep = Builder.CreateGEP(II.StartValue, GlobalIdx, + "next.gep"); + VecVal = Builder.CreateInsertElement(VecVal, SclrGep, + Builder.getInt32(i), + "insert.gep"); } - continue; + Entry[part] = VecVal; } + return; + } +} +void +InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, + BasicBlock *BB, PhiVector *PV) { + // For each instruction in the old loop. + for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { + VectorParts &Entry = WidenMap.get(it); + switch (it->getOpcode()) { + case Instruction::Br: + // Nothing to do for PHIs and BR, since we already took care of the + // loop control flow instructions. + continue; + case Instruction::PHI:{ + // Vectorize PHINodes. + widenPHIInstruction(it, Entry, Legal, UF, VF, PV); + continue; }// End of PHI. case Instruction::Add: @@ -2131,6 +2610,7 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, case Instruction::Xor: { // Just widen binops. BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it); + setDebugLocFromInst(Builder, BinOp); VectorParts &A = getVectorValue(it->getOperand(0)); VectorParts &B = getVectorValue(it->getOperand(1)); @@ -2157,6 +2637,7 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, // instruction with a scalar condition. Otherwise, use vector-select. bool InvariantCond = SE->isLoopInvariant(SE->getSCEV(it->getOperand(0)), OrigLoop); + setDebugLocFromInst(Builder, it); // The condition can be loop invariant but still defined inside the // loop. This means that we can't just use the original 'cond' value. @@ -2165,8 +2646,10 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, VectorParts &Cond = getVectorValue(it->getOperand(0)); VectorParts &Op0 = getVectorValue(it->getOperand(1)); VectorParts &Op1 = getVectorValue(it->getOperand(2)); - Value *ScalarCond = Builder.CreateExtractElement(Cond[0], - Builder.getInt32(0)); + + Value *ScalarCond = (VF == 1) ? Cond[0] : + Builder.CreateExtractElement(Cond[0], Builder.getInt32(0)); + for (unsigned Part = 0; Part < UF; ++Part) { Entry[Part] = Builder.CreateSelect( InvariantCond ? ScalarCond : Cond[Part], @@ -2181,6 +2664,7 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, // Widen compares. Generate vector compares. bool FCmp = (it->getOpcode() == Instruction::FCmp); CmpInst *Cmp = dyn_cast<CmpInst>(it); + setDebugLocFromInst(Builder, it); VectorParts &A = getVectorValue(it->getOperand(0)); VectorParts &B = getVectorValue(it->getOperand(1)); for (unsigned Part = 0; Part < UF; ++Part) { @@ -2211,6 +2695,7 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, case Instruction::FPTrunc: case Instruction::BitCast: { CastInst *CI = dyn_cast<CastInst>(it); + setDebugLocFromInst(Builder, it); /// Optimize the special case where the source is the induction /// variable. Notice that we can only optimize the 'trunc' case /// because: a. FP conversions lose precision, b. sext/zext may wrap, @@ -2225,7 +2710,8 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, break; } /// Vectorize casts. - Type *DestTy = VectorType::get(CI->getType()->getScalarType(), VF); + Type *DestTy = (VF == 1) ? CI->getType() : + VectorType::get(CI->getType(), VF); VectorParts &A = getVectorValue(it->getOperand(0)); for (unsigned Part = 0; Part < UF; ++Part) @@ -2237,20 +2723,32 @@ InnerLoopVectorizer::vectorizeBlockInLoop(LoopVectorizationLegality *Legal, // Ignore dbg intrinsics. if (isa<DbgInfoIntrinsic>(it)) break; + setDebugLocFromInst(Builder, it); Module *M = BB->getParent()->getParent(); CallInst *CI = cast<CallInst>(it); Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI); assert(ID && "Not an intrinsic call!"); - for (unsigned Part = 0; Part < UF; ++Part) { - SmallVector<Value*, 4> Args; - for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) { - VectorParts &Arg = getVectorValue(CI->getArgOperand(i)); - Args.push_back(Arg[Part]); + switch (ID) { + case Intrinsic::lifetime_end: + case Intrinsic::lifetime_start: + scalarizeInstruction(it); + break; + default: + for (unsigned Part = 0; Part < UF; ++Part) { + SmallVector<Value *, 4> Args; + for (unsigned i = 0, ie = CI->getNumArgOperands(); i != ie; ++i) { + VectorParts &Arg = getVectorValue(CI->getArgOperand(i)); + Args.push_back(Arg[Part]); + } + Type *Tys[] = {CI->getType()}; + if (VF > 1) + Tys[0] = VectorType::get(CI->getType()->getScalarType(), VF); + + Function *F = Intrinsic::getDeclaration(M, ID, Tys); + Entry[Part] = Builder.CreateCall(F, Args); } - Type *Tys[] = { VectorType::get(CI->getType()->getScalarType(), VF) }; - Function *F = Intrinsic::getDeclaration(M, ID, Tys); - Entry[Part] = Builder.CreateCall(F, Args); + break; } break; } @@ -2283,24 +2781,65 @@ void InnerLoopVectorizer::updateAnalysis() { DEBUG(DT->verifyAnalysis()); } +/// \brief Check whether it is safe to if-convert this phi node. +/// +/// Phi nodes with constant expressions that can trap are not safe to if +/// convert. +static bool canIfConvertPHINodes(BasicBlock *BB) { + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + PHINode *Phi = dyn_cast<PHINode>(I); + if (!Phi) + return true; + for (unsigned p = 0, e = Phi->getNumIncomingValues(); p != e; ++p) + if (Constant *C = dyn_cast<Constant>(Phi->getIncomingValue(p))) + if (C->canTrap()) + return false; + } + return true; +} + bool LoopVectorizationLegality::canVectorizeWithIfConvert() { if (!EnableIfConversion) return false; assert(TheLoop->getNumBlocks() > 1 && "Single block loops are vectorizable"); - std::vector<BasicBlock*> &LoopBlocks = TheLoop->getBlocksVector(); + + // A list of pointers that we can safely read and write to. + SmallPtrSet<Value *, 8> SafePointes; + + // Collect safe addresses. + for (Loop::block_iterator BI = TheLoop->block_begin(), + BE = TheLoop->block_end(); BI != BE; ++BI) { + BasicBlock *BB = *BI; + + if (blockNeedsPredication(BB)) + continue; + + for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { + if (LoadInst *LI = dyn_cast<LoadInst>(I)) + SafePointes.insert(LI->getPointerOperand()); + else if (StoreInst *SI = dyn_cast<StoreInst>(I)) + SafePointes.insert(SI->getPointerOperand()); + } + } // Collect the blocks that need predication. - for (unsigned i = 0, e = LoopBlocks.size(); i < e; ++i) { - BasicBlock *BB = LoopBlocks[i]; + BasicBlock *Header = TheLoop->getHeader(); + for (Loop::block_iterator BI = TheLoop->block_begin(), + BE = TheLoop->block_end(); BI != BE; ++BI) { + BasicBlock *BB = *BI; // We don't support switch statements inside loops. if (!isa<BranchInst>(BB->getTerminator())) return false; // We must be able to predicate all blocks that need to be predicated. - if (blockNeedsPredication(BB) && !blockCanBePredicated(BB)) + if (blockNeedsPredication(BB)) { + if (!blockCanBePredicated(BB, SafePointes)) + return false; + } else if (BB != Header && !canIfConvertPHINodes(BB)) return false; + } // We can if-convert this loop. @@ -2325,27 +2864,26 @@ bool LoopVectorizationLegality::canVectorize() { if (!TheLoop->getExitingBlock()) return false; - unsigned NumBlocks = TheLoop->getNumBlocks(); + // We need to have a loop header. + DEBUG(dbgs() << "LV: Found a loop: " << + TheLoop->getHeader()->getName() << '\n'); // Check if we can if-convert non single-bb loops. + unsigned NumBlocks = TheLoop->getNumBlocks(); if (NumBlocks != 1 && !canVectorizeWithIfConvert()) { DEBUG(dbgs() << "LV: Can't if-convert the loop.\n"); return false; } - // We need to have a loop header. - BasicBlock *Latch = TheLoop->getLoopLatch(); - DEBUG(dbgs() << "LV: Found a loop: " << - TheLoop->getHeader()->getName() << "\n"); - // ScalarEvolution needs to be able to find the exit count. - const SCEV *ExitCount = SE->getExitCount(TheLoop, Latch); + const SCEV *ExitCount = SE->getBackedgeTakenCount(TheLoop); if (ExitCount == SE->getCouldNotCompute()) { DEBUG(dbgs() << "LV: SCEV could not compute the loop exit count.\n"); return false; } // Do not loop-vectorize loops with a tiny trip count. + BasicBlock *Latch = TheLoop->getLoopLatch(); unsigned TC = SE->getSmallConstantTripCount(TheLoop, Latch); if (TC > 0u && TC < TinyTripCountVectorThreshold) { DEBUG(dbgs() << "LV: Found a loop with a very small trip count. " << @@ -2378,6 +2916,26 @@ bool LoopVectorizationLegality::canVectorize() { return true; } +static Type *convertPointerToIntegerType(DataLayout &DL, Type *Ty) { + if (Ty->isPointerTy()) + return DL.getIntPtrType(Ty); + + // It is possible that char's or short's overflow when we ask for the loop's + // trip count, work around this by changing the type size. + if (Ty->getScalarSizeInBits() < 32) + return Type::getInt32Ty(Ty->getContext()); + + return Ty; +} + +static Type* getWiderType(DataLayout &DL, Type *Ty0, Type *Ty1) { + Ty0 = convertPointerToIntegerType(DL, Ty0); + Ty1 = convertPointerToIntegerType(DL, Ty1); + if (Ty0->getScalarSizeInBits() > Ty1->getScalarSizeInBits()) + return Ty0; + return Ty1; +} + /// \brief Check that the instruction has outside loop users and is not an /// identified reduction variable. static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst, @@ -2391,7 +2949,7 @@ static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst, Instruction *U = cast<Instruction>(*I); // This user may be a reduction exit value. if (!TheLoop->contains(U)) { - DEBUG(dbgs() << "LV: Found an outside user for : "<< *U << "\n"); + DEBUG(dbgs() << "LV: Found an outside user for : " << *U << '\n'); return true; } } @@ -2402,13 +2960,6 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { BasicBlock *PreHeader = TheLoop->getLoopPreheader(); BasicBlock *Header = TheLoop->getHeader(); - // If we marked the scalar loop as "already vectorized" then no need - // to vectorize it again. - if (Header->getTerminator()->getMetadata(AlreadyVectorizedMDName)) { - DEBUG(dbgs() << "LV: This loop was vectorized before\n"); - return false; - } - // Look for the attribute signaling the absence of NaNs. Function &F = *Header->getParent(); if (F.hasFnAttribute("no-nans-fp-math")) @@ -2425,10 +2976,11 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { ++it) { if (PHINode *Phi = dyn_cast<PHINode>(it)) { + Type *PhiTy = Phi->getType(); // Check that this PHI type is allowed. - if (!Phi->getType()->isIntegerTy() && - !Phi->getType()->isFloatingPointTy() && - !Phi->getType()->isPointerTy()) { + if (!PhiTy->isIntegerTy() && + !PhiTy->isFloatingPointTy() && + !PhiTy->isPointerTy()) { DEBUG(dbgs() << "LV: Found an non-int non-pointer PHI.\n"); return false; } @@ -2456,17 +3008,29 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { InductionKind IK = isInductionVariable(Phi); if (IK_NoInduction != IK) { + // Get the widest type. + if (!WidestIndTy) + WidestIndTy = convertPointerToIntegerType(*DL, PhiTy); + else + WidestIndTy = getWiderType(*DL, PhiTy, WidestIndTy); + // Int inductions are special because we only allow one IV. if (IK == IK_IntInduction) { - if (Induction) { - DEBUG(dbgs() << "LV: Found too many inductions."<< *Phi <<"\n"); - return false; - } - Induction = Phi; + // Use the phi node with the widest type as induction. Use the last + // one if there are multiple (no good reason for doing this other + // than it is expedient). + if (!Induction || PhiTy == WidestIndTy) + Induction = Phi; } DEBUG(dbgs() << "LV: Found an induction variable.\n"); Inductions[Phi] = InductionInfo(StartValue, IK); + + // Until we explicitly handle the case of an induction variable with + // an outside loop user we have to give up vectorizing this loop. + if (hasOutsideLoopUser(TheLoop, it, AllowedExit)) + return false; + continue; } @@ -2503,7 +3067,8 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { continue; } if (AddReductionVar(Phi, RK_FloatMinMax)) { - DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi <<"\n"); + DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi << + "\n"); continue; } @@ -2520,9 +3085,10 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { } // Check that the instruction return type is vectorizable. - if (!VectorType::isValidElementType(it->getType()) && - !it->getType()->isVoidTy()) { - DEBUG(dbgs() << "LV: Found unvectorizable type." << "\n"); + // Also, we can't vectorize extractelement instructions. + if ((!VectorType::isValidElementType(it->getType()) && + !it->getType()->isVoidTy()) || isa<ExtractElementInst>(it)) { + DEBUG(dbgs() << "LV: Found unvectorizable type.\n"); return false; } @@ -2544,7 +3110,8 @@ bool LoopVectorizationLegality::canVectorizeInstrs() { if (!Induction) { DEBUG(dbgs() << "LV: Did not find one integer induction var.\n"); - assert(getInductionVars()->size() && "No induction variables"); + if (Inductions.empty()) + return false; } return true; @@ -2573,59 +3140,715 @@ void LoopVectorizationLegality::collectLoopUniforms() { Uniforms.insert(I); // Insert all operands. - for (int i = 0, Op = I->getNumOperands(); i < Op; ++i) { - Worklist.push_back(I->getOperand(i)); - } + Worklist.insert(Worklist.end(), I->op_begin(), I->op_end()); } } -AliasAnalysis::Location -LoopVectorizationLegality::getLoadStoreLocation(Instruction *Inst) { - if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) - return AA->getLocation(Store); - else if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) - return AA->getLocation(Load); +namespace { +/// \brief Analyses memory accesses in a loop. +/// +/// Checks whether run time pointer checks are needed and builds sets for data +/// dependence checking. +class AccessAnalysis { +public: + /// \brief Read or write access location. + typedef PointerIntPair<Value *, 1, bool> MemAccessInfo; + typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet; + + /// \brief Set of potential dependent memory accesses. + typedef EquivalenceClasses<MemAccessInfo> DepCandidates; + + AccessAnalysis(DataLayout *Dl, DepCandidates &DA) : + DL(Dl), DepCands(DA), AreAllWritesIdentified(true), + AreAllReadsIdentified(true), IsRTCheckNeeded(false) {} + + /// \brief Register a load and whether it is only read from. + void addLoad(Value *Ptr, bool IsReadOnly) { + Accesses.insert(MemAccessInfo(Ptr, false)); + if (IsReadOnly) + ReadOnlyPtr.insert(Ptr); + } - llvm_unreachable("Should be either load or store instruction"); + /// \brief Register a store. + void addStore(Value *Ptr) { + Accesses.insert(MemAccessInfo(Ptr, true)); + } + + /// \brief Check whether we can check the pointers at runtime for + /// non-intersection. + bool canCheckPtrAtRT(LoopVectorizationLegality::RuntimePointerCheck &RtCheck, + unsigned &NumComparisons, ScalarEvolution *SE, + Loop *TheLoop, bool ShouldCheckStride = false); + + /// \brief Goes over all memory accesses, checks whether a RT check is needed + /// and builds sets of dependent accesses. + void buildDependenceSets() { + // Process read-write pointers first. + processMemAccesses(false); + // Next, process read pointers. + processMemAccesses(true); + } + + bool isRTCheckNeeded() { return IsRTCheckNeeded; } + + bool isDependencyCheckNeeded() { return !CheckDeps.empty(); } + void resetDepChecks() { CheckDeps.clear(); } + + MemAccessInfoSet &getDependenciesToCheck() { return CheckDeps; } + +private: + typedef SetVector<MemAccessInfo> PtrAccessSet; + typedef DenseMap<Value*, MemAccessInfo> UnderlyingObjToAccessMap; + + /// \brief Go over all memory access or only the deferred ones if + /// \p UseDeferred is true and check whether runtime pointer checks are needed + /// and build sets of dependency check candidates. + void processMemAccesses(bool UseDeferred); + + /// Set of all accesses. + PtrAccessSet Accesses; + + /// Set of access to check after all writes have been processed. + PtrAccessSet DeferredAccesses; + + /// Map of pointers to last access encountered. + UnderlyingObjToAccessMap ObjToLastAccess; + + /// Set of accesses that need a further dependence check. + MemAccessInfoSet CheckDeps; + + /// Set of pointers that are read only. + SmallPtrSet<Value*, 16> ReadOnlyPtr; + + /// Set of underlying objects already written to. + SmallPtrSet<Value*, 16> WriteObjects; + + DataLayout *DL; + + /// Sets of potentially dependent accesses - members of one set share an + /// underlying pointer. The set "CheckDeps" identfies which sets really need a + /// dependence check. + DepCandidates &DepCands; + + bool AreAllWritesIdentified; + bool AreAllReadsIdentified; + bool IsRTCheckNeeded; +}; + +} // end anonymous namespace + +/// \brief Check whether a pointer can participate in a runtime bounds check. +static bool hasComputableBounds(ScalarEvolution *SE, Value *Ptr) { + const SCEV *PtrScev = SE->getSCEV(Ptr); + const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev); + if (!AR) + return false; + + return AR->isAffine(); } -bool -LoopVectorizationLegality::hasPossibleGlobalWriteReorder( - Value *Object, - Instruction *Inst, - AliasMultiMap& WriteObjects, - unsigned MaxByteWidth) { +/// \brief Check the stride of the pointer and ensure that it does not wrap in +/// the address space. +static int isStridedPtr(ScalarEvolution *SE, DataLayout *DL, Value *Ptr, + const Loop *Lp); + +bool AccessAnalysis::canCheckPtrAtRT( + LoopVectorizationLegality::RuntimePointerCheck &RtCheck, + unsigned &NumComparisons, ScalarEvolution *SE, + Loop *TheLoop, bool ShouldCheckStride) { + // Find pointers with computable bounds. We are going to use this information + // to place a runtime bound check. + unsigned NumReadPtrChecks = 0; + unsigned NumWritePtrChecks = 0; + bool CanDoRT = true; + + bool IsDepCheckNeeded = isDependencyCheckNeeded(); + // We assign consecutive id to access from different dependence sets. + // Accesses within the same set don't need a runtime check. + unsigned RunningDepId = 1; + DenseMap<Value *, unsigned> DepSetId; + + for (PtrAccessSet::iterator AI = Accesses.begin(), AE = Accesses.end(); + AI != AE; ++AI) { + const MemAccessInfo &Access = *AI; + Value *Ptr = Access.getPointer(); + bool IsWrite = Access.getInt(); + + // Just add write checks if we have both. + if (!IsWrite && Accesses.count(MemAccessInfo(Ptr, true))) + continue; + + if (IsWrite) + ++NumWritePtrChecks; + else + ++NumReadPtrChecks; + + if (hasComputableBounds(SE, Ptr) && + // When we run after a failing dependency check we have to make sure we + // don't have wrapping pointers. + (!ShouldCheckStride || isStridedPtr(SE, DL, Ptr, TheLoop) == 1)) { + // The id of the dependence set. + unsigned DepId; + + if (IsDepCheckNeeded) { + Value *Leader = DepCands.getLeaderValue(Access).getPointer(); + unsigned &LeaderId = DepSetId[Leader]; + if (!LeaderId) + LeaderId = RunningDepId++; + DepId = LeaderId; + } else + // Each access has its own dependence set. + DepId = RunningDepId++; + + RtCheck.insert(SE, TheLoop, Ptr, IsWrite, DepId); + + DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *Ptr << '\n'); + } else { + CanDoRT = false; + } + } - AliasAnalysis::Location ThisLoc = getLoadStoreLocation(Inst); + if (IsDepCheckNeeded && CanDoRT && RunningDepId == 2) + NumComparisons = 0; // Only one dependence set. + else { + NumComparisons = (NumWritePtrChecks * (NumReadPtrChecks + + NumWritePtrChecks - 1)); + } - std::vector<Instruction*>::iterator - it = WriteObjects[Object].begin(), - end = WriteObjects[Object].end(); + // If the pointers that we would use for the bounds comparison have different + // address spaces, assume the values aren't directly comparable, so we can't + // use them for the runtime check. We also have to assume they could + // overlap. In the future there should be metadata for whether address spaces + // are disjoint. + unsigned NumPointers = RtCheck.Pointers.size(); + for (unsigned i = 0; i < NumPointers; ++i) { + for (unsigned j = i + 1; j < NumPointers; ++j) { + // Only need to check pointers between two different dependency sets. + if (RtCheck.DependencySetId[i] == RtCheck.DependencySetId[j]) + continue; + + Value *PtrI = RtCheck.Pointers[i]; + Value *PtrJ = RtCheck.Pointers[j]; + + unsigned ASi = PtrI->getType()->getPointerAddressSpace(); + unsigned ASj = PtrJ->getType()->getPointerAddressSpace(); + if (ASi != ASj) { + DEBUG(dbgs() << "LV: Runtime check would require comparison between" + " different address spaces\n"); + return false; + } + } + } + + return CanDoRT; +} + +static bool isFunctionScopeIdentifiedObject(Value *Ptr) { + return isNoAliasArgument(Ptr) || isNoAliasCall(Ptr) || isa<AllocaInst>(Ptr); +} - for (; it != end; ++it) { - Instruction* I = *it; - if (I == Inst) +void AccessAnalysis::processMemAccesses(bool UseDeferred) { + // We process the set twice: first we process read-write pointers, last we + // process read-only pointers. This allows us to skip dependence tests for + // read-only pointers. + + PtrAccessSet &S = UseDeferred ? DeferredAccesses : Accesses; + for (PtrAccessSet::iterator AI = S.begin(), AE = S.end(); AI != AE; ++AI) { + const MemAccessInfo &Access = *AI; + Value *Ptr = Access.getPointer(); + bool IsWrite = Access.getInt(); + + DepCands.insert(Access); + + // Memorize read-only pointers for later processing and skip them in the + // first round (they need to be checked after we have seen all write + // pointers). Note: we also mark pointer that are not consecutive as + // "read-only" pointers (so that we check "a[b[i]] +="). Hence, we need the + // second check for "!IsWrite". + bool IsReadOnlyPtr = ReadOnlyPtr.count(Ptr) && !IsWrite; + if (!UseDeferred && IsReadOnlyPtr) { + DeferredAccesses.insert(Access); continue; + } + + bool NeedDepCheck = false; + // Check whether there is the possiblity of dependency because of underlying + // objects being the same. + typedef SmallVector<Value*, 16> ValueVector; + ValueVector TempObjects; + GetUnderlyingObjects(Ptr, TempObjects, DL); + for (ValueVector::iterator UI = TempObjects.begin(), UE = TempObjects.end(); + UI != UE; ++UI) { + Value *UnderlyingObj = *UI; + + // If this is a write then it needs to be an identified object. If this a + // read and all writes (so far) are identified function scope objects we + // don't need an identified underlying object but only an Argument (the + // next write is going to invalidate this assumption if it is + // unidentified). + // This is a micro-optimization for the case where all writes are + // identified and we have one argument pointer. + // Otherwise, we do need a runtime check. + if ((IsWrite && !isFunctionScopeIdentifiedObject(UnderlyingObj)) || + (!IsWrite && (!AreAllWritesIdentified || + !isa<Argument>(UnderlyingObj)) && + !isIdentifiedObject(UnderlyingObj))) { + DEBUG(dbgs() << "LV: Found an unidentified " << + (IsWrite ? "write" : "read" ) << " ptr: " << *UnderlyingObj << + "\n"); + IsRTCheckNeeded = (IsRTCheckNeeded || + !isIdentifiedObject(UnderlyingObj) || + !AreAllReadsIdentified); + + if (IsWrite) + AreAllWritesIdentified = false; + if (!IsWrite) + AreAllReadsIdentified = false; + } + + // If this is a write - check other reads and writes for conflicts. If + // this is a read only check other writes for conflicts (but only if there + // is no other write to the ptr - this is an optimization to catch "a[i] = + // a[i] + " without having to do a dependence check). + if ((IsWrite || IsReadOnlyPtr) && WriteObjects.count(UnderlyingObj)) + NeedDepCheck = true; + + if (IsWrite) + WriteObjects.insert(UnderlyingObj); + + // Create sets of pointers connected by shared underlying objects. + UnderlyingObjToAccessMap::iterator Prev = + ObjToLastAccess.find(UnderlyingObj); + if (Prev != ObjToLastAccess.end()) + DepCands.unionSets(Access, Prev->second); + + ObjToLastAccess[UnderlyingObj] = Access; + } + + if (NeedDepCheck) + CheckDeps.insert(Access); + } +} + +namespace { +/// \brief Checks memory dependences among accesses to the same underlying +/// object to determine whether there vectorization is legal or not (and at +/// which vectorization factor). +/// +/// This class works under the assumption that we already checked that memory +/// locations with different underlying pointers are "must-not alias". +/// We use the ScalarEvolution framework to symbolically evalutate access +/// functions pairs. Since we currently don't restructure the loop we can rely +/// on the program order of memory accesses to determine their safety. +/// At the moment we will only deem accesses as safe for: +/// * A negative constant distance assuming program order. +/// +/// Safe: tmp = a[i + 1]; OR a[i + 1] = x; +/// a[i] = tmp; y = a[i]; +/// +/// The latter case is safe because later checks guarantuee that there can't +/// be a cycle through a phi node (that is, we check that "x" and "y" is not +/// the same variable: a header phi can only be an induction or a reduction, a +/// reduction can't have a memory sink, an induction can't have a memory +/// source). This is important and must not be violated (or we have to +/// resort to checking for cycles through memory). +/// +/// * A positive constant distance assuming program order that is bigger +/// than the biggest memory access. +/// +/// tmp = a[i] OR b[i] = x +/// a[i+2] = tmp y = b[i+2]; +/// +/// Safe distance: 2 x sizeof(a[0]), and 2 x sizeof(b[0]), respectively. +/// +/// * Zero distances and all accesses have the same size. +/// +class MemoryDepChecker { +public: + typedef PointerIntPair<Value *, 1, bool> MemAccessInfo; + typedef SmallPtrSet<MemAccessInfo, 8> MemAccessInfoSet; + + MemoryDepChecker(ScalarEvolution *Se, DataLayout *Dl, const Loop *L) + : SE(Se), DL(Dl), InnermostLoop(L), AccessIdx(0), + ShouldRetryWithRuntimeCheck(false) {} + + /// \brief Register the location (instructions are given increasing numbers) + /// of a write access. + void addAccess(StoreInst *SI) { + Value *Ptr = SI->getPointerOperand(); + Accesses[MemAccessInfo(Ptr, true)].push_back(AccessIdx); + InstMap.push_back(SI); + ++AccessIdx; + } + + /// \brief Register the location (instructions are given increasing numbers) + /// of a write access. + void addAccess(LoadInst *LI) { + Value *Ptr = LI->getPointerOperand(); + Accesses[MemAccessInfo(Ptr, false)].push_back(AccessIdx); + InstMap.push_back(LI); + ++AccessIdx; + } + + /// \brief Check whether the dependencies between the accesses are safe. + /// + /// Only checks sets with elements in \p CheckDeps. + bool areDepsSafe(AccessAnalysis::DepCandidates &AccessSets, + MemAccessInfoSet &CheckDeps); + + /// \brief The maximum number of bytes of a vector register we can vectorize + /// the accesses safely with. + unsigned getMaxSafeDepDistBytes() { return MaxSafeDepDistBytes; } + + /// \brief In same cases when the dependency check fails we can still + /// vectorize the loop with a dynamic array access check. + bool shouldRetryWithRuntimeCheck() { return ShouldRetryWithRuntimeCheck; } + +private: + ScalarEvolution *SE; + DataLayout *DL; + const Loop *InnermostLoop; + + /// \brief Maps access locations (ptr, read/write) to program order. + DenseMap<MemAccessInfo, std::vector<unsigned> > Accesses; + + /// \brief Memory access instructions in program order. + SmallVector<Instruction *, 16> InstMap; + + /// \brief The program order index to be used for the next instruction. + unsigned AccessIdx; + + // We can access this many bytes in parallel safely. + unsigned MaxSafeDepDistBytes; + + /// \brief If we see a non constant dependence distance we can still try to + /// vectorize this loop with runtime checks. + bool ShouldRetryWithRuntimeCheck; + + /// \brief Check whether there is a plausible dependence between the two + /// accesses. + /// + /// Access \p A must happen before \p B in program order. The two indices + /// identify the index into the program order map. + /// + /// This function checks whether there is a plausible dependence (or the + /// absence of such can't be proved) between the two accesses. If there is a + /// plausible dependence but the dependence distance is bigger than one + /// element access it records this distance in \p MaxSafeDepDistBytes (if this + /// distance is smaller than any other distance encountered so far). + /// Otherwise, this function returns true signaling a possible dependence. + bool isDependent(const MemAccessInfo &A, unsigned AIdx, + const MemAccessInfo &B, unsigned BIdx); + + /// \brief Check whether the data dependence could prevent store-load + /// forwarding. + bool couldPreventStoreLoadForward(unsigned Distance, unsigned TypeByteSize); +}; + +} // end anonymous namespace + +static bool isInBoundsGep(Value *Ptr) { + if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) + return GEP->isInBounds(); + return false; +} - AliasAnalysis::Location ThatLoc = getLoadStoreLocation(I); - if (AA->alias(ThisLoc.getWithNewSize(MaxByteWidth), - ThatLoc.getWithNewSize(MaxByteWidth))) +/// \brief Check whether the access through \p Ptr has a constant stride. +static int isStridedPtr(ScalarEvolution *SE, DataLayout *DL, Value *Ptr, + const Loop *Lp) { + const Type *Ty = Ptr->getType(); + assert(Ty->isPointerTy() && "Unexpected non ptr"); + + // Make sure that the pointer does not point to aggregate types. + const PointerType *PtrTy = cast<PointerType>(Ty); + if (PtrTy->getElementType()->isAggregateType()) { + DEBUG(dbgs() << "LV: Bad stride - Not a pointer to a scalar type" << *Ptr << + "\n"); + return 0; + } + + const SCEV *PtrScev = SE->getSCEV(Ptr); + const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PtrScev); + if (!AR) { + DEBUG(dbgs() << "LV: Bad stride - Not an AddRecExpr pointer " + << *Ptr << " SCEV: " << *PtrScev << "\n"); + return 0; + } + + // The accesss function must stride over the innermost loop. + if (Lp != AR->getLoop()) { + DEBUG(dbgs() << "LV: Bad stride - Not striding over innermost loop " << + *Ptr << " SCEV: " << *PtrScev << "\n"); + } + + // The address calculation must not wrap. Otherwise, a dependence could be + // inverted. + // An inbounds getelementptr that is a AddRec with a unit stride + // cannot wrap per definition. The unit stride requirement is checked later. + // An getelementptr without an inbounds attribute and unit stride would have + // to access the pointer value "0" which is undefined behavior in address + // space 0, therefore we can also vectorize this case. + bool IsInBoundsGEP = isInBoundsGep(Ptr); + bool IsNoWrapAddRec = AR->getNoWrapFlags(SCEV::NoWrapMask); + bool IsInAddressSpaceZero = PtrTy->getAddressSpace() == 0; + if (!IsNoWrapAddRec && !IsInBoundsGEP && !IsInAddressSpaceZero) { + DEBUG(dbgs() << "LV: Bad stride - Pointer may wrap in the address space " + << *Ptr << " SCEV: " << *PtrScev << "\n"); + return 0; + } + + // Check the step is constant. + const SCEV *Step = AR->getStepRecurrence(*SE); + + // Calculate the pointer stride and check if it is consecutive. + const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); + if (!C) { + DEBUG(dbgs() << "LV: Bad stride - Not a constant strided " << *Ptr << + " SCEV: " << *PtrScev << "\n"); + return 0; + } + + int64_t Size = DL->getTypeAllocSize(PtrTy->getElementType()); + const APInt &APStepVal = C->getValue()->getValue(); + + // Huge step value - give up. + if (APStepVal.getBitWidth() > 64) + return 0; + + int64_t StepVal = APStepVal.getSExtValue(); + + // Strided access. + int64_t Stride = StepVal / Size; + int64_t Rem = StepVal % Size; + if (Rem) + return 0; + + // If the SCEV could wrap but we have an inbounds gep with a unit stride we + // know we can't "wrap around the address space". In case of address space + // zero we know that this won't happen without triggering undefined behavior. + if (!IsNoWrapAddRec && (IsInBoundsGEP || IsInAddressSpaceZero) && + Stride != 1 && Stride != -1) + return 0; + + return Stride; +} + +bool MemoryDepChecker::couldPreventStoreLoadForward(unsigned Distance, + unsigned TypeByteSize) { + // If loads occur at a distance that is not a multiple of a feasible vector + // factor store-load forwarding does not take place. + // Positive dependences might cause troubles because vectorizing them might + // prevent store-load forwarding making vectorized code run a lot slower. + // a[i] = a[i-3] ^ a[i-8]; + // The stores to a[i:i+1] don't align with the stores to a[i-3:i-2] and + // hence on your typical architecture store-load forwarding does not take + // place. Vectorizing in such cases does not make sense. + // Store-load forwarding distance. + const unsigned NumCyclesForStoreLoadThroughMemory = 8*TypeByteSize; + // Maximum vector factor. + unsigned MaxVFWithoutSLForwardIssues = MaxVectorWidth*TypeByteSize; + if(MaxSafeDepDistBytes < MaxVFWithoutSLForwardIssues) + MaxVFWithoutSLForwardIssues = MaxSafeDepDistBytes; + + for (unsigned vf = 2*TypeByteSize; vf <= MaxVFWithoutSLForwardIssues; + vf *= 2) { + if (Distance % vf && Distance / vf < NumCyclesForStoreLoadThroughMemory) { + MaxVFWithoutSLForwardIssues = (vf >>=1); + break; + } + } + + if (MaxVFWithoutSLForwardIssues< 2*TypeByteSize) { + DEBUG(dbgs() << "LV: Distance " << Distance << + " that could cause a store-load forwarding conflict\n"); + return true; + } + + if (MaxVFWithoutSLForwardIssues < MaxSafeDepDistBytes && + MaxVFWithoutSLForwardIssues != MaxVectorWidth*TypeByteSize) + MaxSafeDepDistBytes = MaxVFWithoutSLForwardIssues; + return false; +} + +bool MemoryDepChecker::isDependent(const MemAccessInfo &A, unsigned AIdx, + const MemAccessInfo &B, unsigned BIdx) { + assert (AIdx < BIdx && "Must pass arguments in program order"); + + Value *APtr = A.getPointer(); + Value *BPtr = B.getPointer(); + bool AIsWrite = A.getInt(); + bool BIsWrite = B.getInt(); + + // Two reads are independent. + if (!AIsWrite && !BIsWrite) + return false; + + const SCEV *AScev = SE->getSCEV(APtr); + const SCEV *BScev = SE->getSCEV(BPtr); + + int StrideAPtr = isStridedPtr(SE, DL, APtr, InnermostLoop); + int StrideBPtr = isStridedPtr(SE, DL, BPtr, InnermostLoop); + + const SCEV *Src = AScev; + const SCEV *Sink = BScev; + + // If the induction step is negative we have to invert source and sink of the + // dependence. + if (StrideAPtr < 0) { + //Src = BScev; + //Sink = AScev; + std::swap(APtr, BPtr); + std::swap(Src, Sink); + std::swap(AIsWrite, BIsWrite); + std::swap(AIdx, BIdx); + std::swap(StrideAPtr, StrideBPtr); + } + + const SCEV *Dist = SE->getMinusSCEV(Sink, Src); + + DEBUG(dbgs() << "LV: Src Scev: " << *Src << "Sink Scev: " << *Sink + << "(Induction step: " << StrideAPtr << ")\n"); + DEBUG(dbgs() << "LV: Distance for " << *InstMap[AIdx] << " to " + << *InstMap[BIdx] << ": " << *Dist << "\n"); + + // Need consecutive accesses. We don't want to vectorize + // "A[B[i]] += ..." and similar code or pointer arithmetic that could wrap in + // the address space. + if (!StrideAPtr || !StrideBPtr || StrideAPtr != StrideBPtr){ + DEBUG(dbgs() << "Non-consecutive pointer access\n"); + return true; + } + + const SCEVConstant *C = dyn_cast<SCEVConstant>(Dist); + if (!C) { + DEBUG(dbgs() << "LV: Dependence because of non constant distance\n"); + ShouldRetryWithRuntimeCheck = true; + return true; + } + + Type *ATy = APtr->getType()->getPointerElementType(); + Type *BTy = BPtr->getType()->getPointerElementType(); + unsigned TypeByteSize = DL->getTypeAllocSize(ATy); + + // Negative distances are not plausible dependencies. + const APInt &Val = C->getValue()->getValue(); + if (Val.isNegative()) { + bool IsTrueDataDependence = (AIsWrite && !BIsWrite); + if (IsTrueDataDependence && + (couldPreventStoreLoadForward(Val.abs().getZExtValue(), TypeByteSize) || + ATy != BTy)) return true; + + DEBUG(dbgs() << "LV: Dependence is negative: NoDep\n"); + return false; + } + + // Write to the same location with the same size. + // Could be improved to assert type sizes are the same (i32 == float, etc). + if (Val == 0) { + if (ATy == BTy) + return false; + DEBUG(dbgs() << "LV: Zero dependence difference but different types\n"); + return true; + } + + assert(Val.isStrictlyPositive() && "Expect a positive value"); + + // Positive distance bigger than max vectorization factor. + if (ATy != BTy) { + DEBUG(dbgs() << + "LV: ReadWrite-Write positive dependency with different types\n"); + return false; } + + unsigned Distance = (unsigned) Val.getZExtValue(); + + // Bail out early if passed-in parameters make vectorization not feasible. + unsigned ForcedFactor = VectorizationFactor ? VectorizationFactor : 1; + unsigned ForcedUnroll = VectorizationUnroll ? VectorizationUnroll : 1; + + // The distance must be bigger than the size needed for a vectorized version + // of the operation and the size of the vectorized operation must not be + // bigger than the currrent maximum size. + if (Distance < 2*TypeByteSize || + 2*TypeByteSize > MaxSafeDepDistBytes || + Distance < TypeByteSize * ForcedUnroll * ForcedFactor) { + DEBUG(dbgs() << "LV: Failure because of Positive distance " + << Val.getSExtValue() << '\n'); + return true; + } + + MaxSafeDepDistBytes = Distance < MaxSafeDepDistBytes ? + Distance : MaxSafeDepDistBytes; + + bool IsTrueDataDependence = (!AIsWrite && BIsWrite); + if (IsTrueDataDependence && + couldPreventStoreLoadForward(Distance, TypeByteSize)) + return true; + + DEBUG(dbgs() << "LV: Positive distance " << Val.getSExtValue() << + " with max VF = " << MaxSafeDepDistBytes / TypeByteSize << '\n'); + return false; } +bool +MemoryDepChecker::areDepsSafe(AccessAnalysis::DepCandidates &AccessSets, + MemAccessInfoSet &CheckDeps) { + + MaxSafeDepDistBytes = -1U; + while (!CheckDeps.empty()) { + MemAccessInfo CurAccess = *CheckDeps.begin(); + + // Get the relevant memory access set. + EquivalenceClasses<MemAccessInfo>::iterator I = + AccessSets.findValue(AccessSets.getLeaderValue(CurAccess)); + + // Check accesses within this set. + EquivalenceClasses<MemAccessInfo>::member_iterator AI, AE; + AI = AccessSets.member_begin(I), AE = AccessSets.member_end(); + + // Check every access pair. + while (AI != AE) { + CheckDeps.erase(*AI); + EquivalenceClasses<MemAccessInfo>::member_iterator OI = llvm::next(AI); + while (OI != AE) { + // Check every accessing instruction pair in program order. + for (std::vector<unsigned>::iterator I1 = Accesses[*AI].begin(), + I1E = Accesses[*AI].end(); I1 != I1E; ++I1) + for (std::vector<unsigned>::iterator I2 = Accesses[*OI].begin(), + I2E = Accesses[*OI].end(); I2 != I2E; ++I2) { + if (*I1 < *I2 && isDependent(*AI, *I1, *OI, *I2)) + return false; + if (*I2 < *I1 && isDependent(*OI, *I2, *AI, *I1)) + return false; + } + ++OI; + } + AI++; + } + } + return true; +} + bool LoopVectorizationLegality::canVectorizeMemory() { typedef SmallVector<Value*, 16> ValueVector; typedef SmallPtrSet<Value*, 16> ValueSet; + // Holds the Load and Store *instructions*. ValueVector Loads; ValueVector Stores; + + // Holds all the different accesses in the loop. + unsigned NumReads = 0; + unsigned NumReadWrites = 0; + PtrRtCheck.Pointers.clear(); PtrRtCheck.Need = false; const bool IsAnnotatedParallel = TheLoop->isAnnotatedParallel(); + MemoryDepChecker DepChecker(SE, DL, TheLoop); // For each block. for (Loop::block_iterator bb = TheLoop->block_begin(), @@ -2639,6 +3862,13 @@ bool LoopVectorizationLegality::canVectorizeMemory() { // but is not a load, then we quit. Notice that we don't handle function // calls that read or write. if (it->mayReadFromMemory()) { + // Many math library functions read the rounding mode. We will only + // vectorize a loop if it contains known function calls that don't set + // the flag. Therefore, it is safe to ignore this read from memory. + CallInst *Call = dyn_cast<CallInst>(it); + if (Call && getIntrinsicIDForCall(Call, TLI)) + continue; + LoadInst *Ld = dyn_cast<LoadInst>(it); if (!Ld) return false; if (!Ld->isSimple() && !IsAnnotatedParallel) { @@ -2646,6 +3876,7 @@ bool LoopVectorizationLegality::canVectorizeMemory() { return false; } Loads.push_back(Ld); + DepChecker.addAccess(Ld); continue; } @@ -2658,9 +3889,10 @@ bool LoopVectorizationLegality::canVectorizeMemory() { return false; } Stores.push_back(St); + DepChecker.addAccess(St); } - } // next instr. - } // next block. + } // Next instr. + } // Next block. // Now we have two lists that hold the loads and the stores. // Next, we find the pointers that they use. @@ -2672,10 +3904,8 @@ bool LoopVectorizationLegality::canVectorizeMemory() { return true; } - // Holds the read and read-write *pointers* that we find. These maps hold - // unique values for pointers (so no need for multi-map). - AliasMap Reads; - AliasMap ReadWrites; + AccessAnalysis::DepCandidates DependentAccesses; + AccessAnalysis Accesses(DL, DependentAccesses); // Holds the analyzed pointers. We don't want to call GetUnderlyingObjects // multiple times on the same object. If the ptr is accessed twice, once @@ -2694,10 +3924,12 @@ bool LoopVectorizationLegality::canVectorizeMemory() { return false; } - // If we did *not* see this pointer before, insert it to - // the read-write list. At this phase it is only a 'write' list. - if (Seen.insert(Ptr)) - ReadWrites.insert(std::make_pair(Ptr, ST)); + // If we did *not* see this pointer before, insert it to the read-write + // list. At this phase it is only a 'write' list. + if (Seen.insert(Ptr)) { + ++NumReadWrites; + Accesses.addStore(Ptr); + } } if (IsAnnotatedParallel) { @@ -2718,51 +3950,44 @@ bool LoopVectorizationLegality::canVectorizeMemory() { // If the address of i is unknown (for example A[B[i]]) then we may // read a few words, modify, and write a few words, and some of the // words may be written to the same address. - if (Seen.insert(Ptr) || 0 == isConsecutivePtr(Ptr)) - Reads.insert(std::make_pair(Ptr, LD)); + bool IsReadOnlyPtr = false; + if (Seen.insert(Ptr) || !isStridedPtr(SE, DL, Ptr, TheLoop)) { + ++NumReads; + IsReadOnlyPtr = true; + } + Accesses.addLoad(Ptr, IsReadOnlyPtr); } // If we write (or read-write) to a single destination and there are no // other reads in this loop then is it safe to vectorize. - if (ReadWrites.size() == 1 && Reads.size() == 0) { + if (NumReadWrites == 1 && NumReads == 0) { DEBUG(dbgs() << "LV: Found a write-only loop!\n"); return true; } - unsigned NumReadPtrs = 0; - unsigned NumWritePtrs = 0; + // Build dependence sets and check whether we need a runtime pointer bounds + // check. + Accesses.buildDependenceSets(); + bool NeedRTCheck = Accesses.isRTCheckNeeded(); // Find pointers with computable bounds. We are going to use this information // to place a runtime bound check. - bool CanDoRT = true; - AliasMap::iterator MI, ME; - for (MI = ReadWrites.begin(), ME = ReadWrites.end(); MI != ME; ++MI) { - Value *V = (*MI).first; - if (hasComputableBounds(V)) { - PtrRtCheck.insert(SE, TheLoop, V, true); - NumWritePtrs++; - DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *V <<"\n"); - } else { - CanDoRT = false; - break; - } - } - for (MI = Reads.begin(), ME = Reads.end(); MI != ME; ++MI) { - Value *V = (*MI).first; - if (hasComputableBounds(V)) { - PtrRtCheck.insert(SE, TheLoop, V, false); - NumReadPtrs++; - DEBUG(dbgs() << "LV: Found a runtime check ptr:" << *V <<"\n"); - } else { - CanDoRT = false; - break; - } - } + unsigned NumComparisons = 0; + bool CanDoRT = false; + if (NeedRTCheck) + CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, TheLoop); + + + DEBUG(dbgs() << "LV: We need to do " << NumComparisons << + " pointer comparisons.\n"); - // Check that we did not collect too many pointers or found a - // unsizeable pointer. - unsigned NumComparisons = (NumWritePtrs * (NumReadPtrs + NumWritePtrs - 1)); - DEBUG(dbgs() << "LV: We need to compare " << NumComparisons << " ptrs.\n"); + // If we only have one set of dependences to check pointers among we don't + // need a runtime check. + if (NumComparisons == 0 && NeedRTCheck) + NeedRTCheck = false; + + // Check that we did not collect too many pointers or found an unsizeable + // pointer. if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) { PtrRtCheck.reset(); CanDoRT = false; @@ -2772,122 +3997,69 @@ bool LoopVectorizationLegality::canVectorizeMemory() { DEBUG(dbgs() << "LV: We can perform a memory runtime check if needed.\n"); } - bool NeedRTCheck = false; - - // Biggest vectorized access possible, vector width * unroll factor. - // TODO: We're being very pessimistic here, find a way to know the - // real access width before getting here. - unsigned MaxByteWidth = (TTI->getRegisterBitWidth(true) / 8) * - TTI->getMaximumUnrollFactor(); - // Now that the pointers are in two lists (Reads and ReadWrites), we - // can check that there are no conflicts between each of the writes and - // between the writes to the reads. - // Note that WriteObjects duplicates the stores (indexed now by underlying - // objects) to avoid pointing to elements inside ReadWrites. - // TODO: Maybe create a new type where they can interact without duplication. - AliasMultiMap WriteObjects; - ValueVector TempObjects; - - // Check that the read-writes do not conflict with other read-write - // pointers. - bool AllWritesIdentified = true; - for (MI = ReadWrites.begin(), ME = ReadWrites.end(); MI != ME; ++MI) { - Value *Val = (*MI).first; - Instruction *Inst = (*MI).second; - - GetUnderlyingObjects(Val, TempObjects, DL); - for (ValueVector::iterator UI=TempObjects.begin(), UE=TempObjects.end(); - UI != UE; ++UI) { - if (!isIdentifiedObject(*UI)) { - DEBUG(dbgs() << "LV: Found an unidentified write ptr:"<< **UI <<"\n"); - NeedRTCheck = true; - AllWritesIdentified = false; - } + if (NeedRTCheck && !CanDoRT) { + DEBUG(dbgs() << "LV: We can't vectorize because we can't find " << + "the array bounds.\n"); + PtrRtCheck.reset(); + return false; + } - // Never seen it before, can't alias. - if (WriteObjects[*UI].empty()) { - DEBUG(dbgs() << "LV: Adding Underlying value:" << **UI <<"\n"); - WriteObjects[*UI].push_back(Inst); - continue; - } - // Direct alias found. - if (!AA || dyn_cast<GlobalValue>(*UI) == NULL) { - DEBUG(dbgs() << "LV: Found a possible write-write reorder:" - << **UI <<"\n"); - return false; - } - DEBUG(dbgs() << "LV: Found a conflicting global value:" - << **UI <<"\n"); - DEBUG(dbgs() << "LV: While examining store:" << *Inst <<"\n"); - DEBUG(dbgs() << "LV: On value:" << *Val <<"\n"); - - // If global alias, make sure they do alias. - if (hasPossibleGlobalWriteReorder(*UI, - Inst, - WriteObjects, - MaxByteWidth)) { - DEBUG(dbgs() << "LV: Found a possible write-write reorder:" << **UI - << "\n"); + PtrRtCheck.Need = NeedRTCheck; + + bool CanVecMem = true; + if (Accesses.isDependencyCheckNeeded()) { + DEBUG(dbgs() << "LV: Checking memory dependencies\n"); + CanVecMem = DepChecker.areDepsSafe(DependentAccesses, + Accesses.getDependenciesToCheck()); + MaxSafeDepDistBytes = DepChecker.getMaxSafeDepDistBytes(); + + if (!CanVecMem && DepChecker.shouldRetryWithRuntimeCheck()) { + DEBUG(dbgs() << "LV: Retrying with memory checks\n"); + NeedRTCheck = true; + + // Clear the dependency checks. We assume they are not needed. + Accesses.resetDepChecks(); + + PtrRtCheck.reset(); + PtrRtCheck.Need = true; + + CanDoRT = Accesses.canCheckPtrAtRT(PtrRtCheck, NumComparisons, SE, + TheLoop, true); + // Check that we did not collect too many pointers or found an unsizeable + // pointer. + if (!CanDoRT || NumComparisons > RuntimeMemoryCheckThreshold) { + DEBUG(dbgs() << "LV: Can't vectorize with memory checks\n"); + PtrRtCheck.reset(); return false; } - // Didn't alias, insert into map for further reference. - WriteObjects[*UI].push_back(Inst); + CanVecMem = true; } - TempObjects.clear(); } - /// Check that the reads don't conflict with the read-writes. - for (MI = Reads.begin(), ME = Reads.end(); MI != ME; ++MI) { - Value *Val = (*MI).first; - GetUnderlyingObjects(Val, TempObjects, DL); - for (ValueVector::iterator UI=TempObjects.begin(), UE=TempObjects.end(); - UI != UE; ++UI) { - // If all of the writes are identified then we don't care if the read - // pointer is identified or not. - if (!AllWritesIdentified && !isIdentifiedObject(*UI)) { - DEBUG(dbgs() << "LV: Found an unidentified read ptr:"<< **UI <<"\n"); - NeedRTCheck = true; - } + DEBUG(dbgs() << "LV: We" << (NeedRTCheck ? "" : " don't") << + " need a runtime memory check.\n"); - // Never seen it before, can't alias. - if (WriteObjects[*UI].empty()) - continue; - // Direct alias found. - if (!AA || dyn_cast<GlobalValue>(*UI) == NULL) { - DEBUG(dbgs() << "LV: Found a possible write-write reorder:" - << **UI <<"\n"); - return false; - } - DEBUG(dbgs() << "LV: Found a global value: " - << **UI <<"\n"); - Instruction *Inst = (*MI).second; - DEBUG(dbgs() << "LV: While examining load:" << *Inst <<"\n"); - DEBUG(dbgs() << "LV: On value:" << *Val <<"\n"); - - // If global alias, make sure they do alias. - if (hasPossibleGlobalWriteReorder(*UI, - Inst, - WriteObjects, - MaxByteWidth)) { - DEBUG(dbgs() << "LV: Found a possible read-write reorder:" << **UI - << "\n"); - return false; - } - } - TempObjects.clear(); - } + return CanVecMem; +} - PtrRtCheck.Need = NeedRTCheck; - if (NeedRTCheck && !CanDoRT) { - DEBUG(dbgs() << "LV: We can't vectorize because we can't find " << - "the array bounds.\n"); - PtrRtCheck.reset(); - return false; +static bool hasMultipleUsesOf(Instruction *I, + SmallPtrSet<Instruction *, 8> &Insts) { + unsigned NumUses = 0; + for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) { + if (Insts.count(dyn_cast<Instruction>(*Use))) + ++NumUses; + if (NumUses > 1) + return true; } - DEBUG(dbgs() << "LV: We "<< (NeedRTCheck ? "" : "don't") << - " need a runtime memory check.\n"); + return false; +} + +static bool areAllUsesIn(Instruction *I, SmallPtrSet<Instruction *, 8> &Set) { + for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) + if (!Set.count(dyn_cast<Instruction>(*Use))) + return false; return true; } @@ -2909,116 +4081,154 @@ bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi, // This includes users of the reduction, variables (which form a cycle // which ends in the phi node). Instruction *ExitInstruction = 0; - // Indicates that we found a binary operation in our scan. - bool FoundBinOp = false; + // Indicates that we found a reduction operation in our scan. + bool FoundReduxOp = false; - // Iter is our iterator. We start with the PHI node and scan for all of the - // users of this instruction. All users must be instructions that can be - // used as reduction variables (such as ADD). We may have a single - // out-of-block user. The cycle must end with the original PHI. - Instruction *Iter = Phi; + // We start with the PHI node and scan for all of the users of this + // instruction. All users must be instructions that can be used as reduction + // variables (such as ADD). We must have a single out-of-block user. The cycle + // must include the original PHI. + bool FoundStartPHI = false; // To recognize min/max patterns formed by a icmp select sequence, we store // the number of instruction we saw from the recognized min/max pattern, - // such that we don't stop when we see the phi has two uses (one by the select - // and one by the icmp) and to make sure we only see exactly the two - // instructions. + // to make sure we only see exactly the two instructions. unsigned NumCmpSelectPatternInst = 0; ReductionInstDesc ReduxDesc(false, 0); - // Avoid cycles in the chain. SmallPtrSet<Instruction *, 8> VisitedInsts; - while (VisitedInsts.insert(Iter)) { - // If the instruction has no users then this is a broken - // chain and can't be a reduction variable. - if (Iter->use_empty()) + SmallVector<Instruction *, 8> Worklist; + Worklist.push_back(Phi); + VisitedInsts.insert(Phi); + + // A value in the reduction can be used: + // - By the reduction: + // - Reduction operation: + // - One use of reduction value (safe). + // - Multiple use of reduction value (not safe). + // - PHI: + // - All uses of the PHI must be the reduction (safe). + // - Otherwise, not safe. + // - By one instruction outside of the loop (safe). + // - By further instructions outside of the loop (not safe). + // - By an instruction that is not part of the reduction (not safe). + // This is either: + // * An instruction type other than PHI or the reduction operation. + // * A PHI in the header other than the initial PHI. + while (!Worklist.empty()) { + Instruction *Cur = Worklist.back(); + Worklist.pop_back(); + + // No Users. + // If the instruction has no users then this is a broken chain and can't be + // a reduction variable. + if (Cur->use_empty()) return false; - // Did we find a user inside this loop already ? - bool FoundInBlockUser = false; - // Did we reach the initial PHI node already ? - bool FoundStartPHI = false; + bool IsAPhi = isa<PHINode>(Cur); - // Is this a bin op ? - FoundBinOp |= !isa<PHINode>(Iter); + // A header PHI use other than the original PHI. + if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) + return false; - // For each of the *users* of iter. - for (Value::use_iterator it = Iter->use_begin(), e = Iter->use_end(); - it != e; ++it) { - Instruction *U = cast<Instruction>(*it); - // We already know that the PHI is a user. - if (U == Phi) { - FoundStartPHI = true; - continue; - } + // Reductions of instructions such as Div, and Sub is only possible if the + // LHS is the reduction variable. + if (!Cur->isCommutative() && !IsAPhi && !isa<SelectInst>(Cur) && + !isa<ICmpInst>(Cur) && !isa<FCmpInst>(Cur) && + !VisitedInsts.count(dyn_cast<Instruction>(Cur->getOperand(0)))) + return false; + + // Any reduction instruction must be of one of the allowed kinds. + ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc); + if (!ReduxDesc.IsReduction) + return false; + + // A reduction operation must only have one use of the reduction value. + if (!IsAPhi && Kind != RK_IntegerMinMax && Kind != RK_FloatMinMax && + hasMultipleUsesOf(Cur, VisitedInsts)) + return false; + + // All inputs to a PHI node must be a reduction value. + if(IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) + return false; + + if (Kind == RK_IntegerMinMax && (isa<ICmpInst>(Cur) || + isa<SelectInst>(Cur))) + ++NumCmpSelectPatternInst; + if (Kind == RK_FloatMinMax && (isa<FCmpInst>(Cur) || + isa<SelectInst>(Cur))) + ++NumCmpSelectPatternInst; + + // Check whether we found a reduction operator. + FoundReduxOp |= !IsAPhi; + + // Process users of current instruction. Push non PHI nodes after PHI nodes + // onto the stack. This way we are going to have seen all inputs to PHI + // nodes once we get to them. + SmallVector<Instruction *, 8> NonPHIs; + SmallVector<Instruction *, 8> PHIs; + for (Value::use_iterator UI = Cur->use_begin(), E = Cur->use_end(); UI != E; + ++UI) { + Instruction *Usr = cast<Instruction>(*UI); // Check if we found the exit user. - BasicBlock *Parent = U->getParent(); + BasicBlock *Parent = Usr->getParent(); if (!TheLoop->contains(Parent)) { - // Exit if you find multiple outside users. - if (ExitInstruction != 0) + // Exit if you find multiple outside users or if the header phi node is + // being used. In this case the user uses the value of the previous + // iteration, in which case we would loose "VF-1" iterations of the + // reduction operation if we vectorize. + if (ExitInstruction != 0 || Cur == Phi) return false; - ExitInstruction = Iter; - } - // We allow in-loop PHINodes which are not the original reduction PHI - // node. If this PHI is the only user of Iter (happens in IF w/ no ELSE - // structure) then don't skip this PHI. - if (isa<PHINode>(Iter) && isa<PHINode>(U) && - U->getParent() != TheLoop->getHeader() && - TheLoop->contains(U) && - Iter->hasNUsesOrMore(2)) - continue; + // The instruction used by an outside user must be the last instruction + // before we feed back to the reduction phi. Otherwise, we loose VF-1 + // operations on the value. + if (std::find(Phi->op_begin(), Phi->op_end(), Cur) == Phi->op_end()) + return false; - // We can't have multiple inside users except for a combination of - // icmp/select both using the phi. - if (FoundInBlockUser && !NumCmpSelectPatternInst) - return false; - FoundInBlockUser = true; - - // Any reduction instr must be of one of the allowed kinds. - ReduxDesc = isReductionInstr(U, Kind, ReduxDesc); - if (!ReduxDesc.IsReduction) - return false; + ExitInstruction = Cur; + continue; + } - if (Kind == RK_IntegerMinMax && (isa<ICmpInst>(U) || isa<SelectInst>(U))) - ++NumCmpSelectPatternInst; - if (Kind == RK_FloatMinMax && (isa<FCmpInst>(U) || isa<SelectInst>(U))) - ++NumCmpSelectPatternInst; + // Process instructions only once (termination). + if (VisitedInsts.insert(Usr)) { + if (isa<PHINode>(Usr)) + PHIs.push_back(Usr); + else + NonPHIs.push_back(Usr); + } + // Remember that we completed the cycle. + if (Usr == Phi) + FoundStartPHI = true; + } + Worklist.append(PHIs.begin(), PHIs.end()); + Worklist.append(NonPHIs.begin(), NonPHIs.end()); + } - // Reductions of instructions such as Div, and Sub is only - // possible if the LHS is the reduction variable. - if (!U->isCommutative() && !isa<PHINode>(U) && !isa<SelectInst>(U) && - !isa<ICmpInst>(U) && !isa<FCmpInst>(U) && U->getOperand(0) != Iter) - return false; + // This means we have seen one but not the other instruction of the + // pattern or more than just a select and cmp. + if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && + NumCmpSelectPatternInst != 2) + return false; - Iter = ReduxDesc.PatternLastInst; - } + if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) + return false; - // This means we have seen one but not the other instruction of the - // pattern or more than just a select and cmp. - if ((Kind == RK_IntegerMinMax || Kind == RK_FloatMinMax) && - NumCmpSelectPatternInst != 2) - return false; + // We found a reduction var if we have reached the original phi node and we + // only have a single instruction with out-of-loop users. - // We found a reduction var if we have reached the original - // phi node and we only have a single instruction with out-of-loop - // users. - if (FoundStartPHI) { - // This instruction is allowed to have out-of-loop users. - AllowedExit.insert(ExitInstruction); + // This instruction is allowed to have out-of-loop users. + AllowedExit.insert(ExitInstruction); - // Save the description of this reduction variable. - ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, - ReduxDesc.MinMaxKind); - Reductions[Phi] = RD; - // We've ended the cycle. This is a reduction variable if we have an - // outside user and it has a binary op. - return FoundBinOp && ExitInstruction; - } - } + // Save the description of this reduction variable. + ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, + ReduxDesc.MinMaxKind); + Reductions[Phi] = RD; + // We've ended the cycle. This is a reduction variable if we have an + // outside user and it has a binary op. - return false; + return true; } /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction @@ -3169,12 +4379,28 @@ bool LoopVectorizationLegality::blockNeedsPredication(BasicBlock *BB) { return !DT->dominates(BB, Latch); } -bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB) { +bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB, + SmallPtrSet<Value *, 8>& SafePtrs) { for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { - // We don't predicate loads/stores at the moment. - if (it->mayReadFromMemory() || it->mayWriteToMemory() || it->mayThrow()) + // We might be able to hoist the load. + if (it->mayReadFromMemory()) { + LoadInst *LI = dyn_cast<LoadInst>(it); + if (!LI || !SafePtrs.count(LI->getPointerOperand())) + return false; + } + + // We don't predicate stores at the moment. + if (it->mayWriteToMemory() || it->mayThrow()) return false; + // Check that we don't have a constant expression that can trap as operand. + for (Instruction::op_iterator OI = it->op_begin(), OE = it->op_end(); + OI != OE; ++OI) { + if (Constant *C = dyn_cast<Constant>(*OI)) + if (C->canTrap()) + return false; + } + // The instructions below can trap. switch (it->getOpcode()) { default: continue; @@ -3189,15 +4415,6 @@ bool LoopVectorizationLegality::blockCanBePredicated(BasicBlock *BB) { return true; } -bool LoopVectorizationLegality::hasComputableBounds(Value *Ptr) { - const SCEV *PhiScev = SE->getSCEV(Ptr); - const SCEVAddRecExpr *AR = dyn_cast<SCEVAddRecExpr>(PhiScev); - if (!AR) - return false; - - return AR->isAffine(); -} - LoopVectorizationCostModel::VectorizationFactor LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize, unsigned UserVF) { @@ -3210,13 +4427,19 @@ LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize, // Find the trip count. unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch()); - DEBUG(dbgs() << "LV: Found trip count:"<<TC<<"\n"); + DEBUG(dbgs() << "LV: Found trip count: " << TC << '\n'); unsigned WidestType = getWidestType(); unsigned WidestRegister = TTI.getRegisterBitWidth(true); + unsigned MaxSafeDepDist = -1U; + if (Legal->getMaxSafeDepDistBytes() != -1U) + MaxSafeDepDist = Legal->getMaxSafeDepDistBytes() * 8; + WidestRegister = ((WidestRegister < MaxSafeDepDist) ? + WidestRegister : MaxSafeDepDist); unsigned MaxVectorSize = WidestRegister / WidestType; DEBUG(dbgs() << "LV: The Widest type: " << WidestType << " bits.\n"); - DEBUG(dbgs() << "LV: The Widest register is:" << WidestRegister << "bits.\n"); + DEBUG(dbgs() << "LV: The Widest register is: " + << WidestRegister << " bits.\n"); if (MaxVectorSize == 0) { DEBUG(dbgs() << "LV: The target has no vector registers.\n"); @@ -3252,7 +4475,7 @@ LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize, if (UserVF != 0) { assert(isPowerOf2_32(UserVF) && "VF needs to be a power of two"); - DEBUG(dbgs() << "LV: Using user VF "<<UserVF<<".\n"); + DEBUG(dbgs() << "LV: Using user VF " << UserVF << ".\n"); Factor.Width = UserVF; return Factor; @@ -3260,13 +4483,13 @@ LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize, float Cost = expectedCost(1); unsigned Width = 1; - DEBUG(dbgs() << "LV: Scalar loop costs: "<< (int)Cost << ".\n"); + DEBUG(dbgs() << "LV: Scalar loop costs: " << (int)Cost << ".\n"); for (unsigned i=2; i <= VF; i*=2) { // Notice that the vector loop needs to be executed less times, so // we need to divide the cost of the vector loops by the width of // the vector elements. float VectorCost = expectedCost(i) / (float)i; - DEBUG(dbgs() << "LV: Vector loop of width "<< i << " costs: " << + DEBUG(dbgs() << "LV: Vector loop of width " << i << " costs: " << (int)VectorCost << ".\n"); if (VectorCost < Cost) { Cost = VectorCost; @@ -3347,6 +4570,10 @@ LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize, if (OptForSize) return 1; + // We used the distance for the unroll factor. + if (Legal->getMaxSafeDepDistBytes() != -1U) + return 1; + // Do not unroll loops with a relatively small trip count. unsigned TC = SE->getSmallConstantTripCount(TheLoop, TheLoop->getLoopLatch()); @@ -3386,8 +4613,20 @@ LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize, else if (UF < 1) UF = 1; - if (Legal->getReductionVars()->size()) { - DEBUG(dbgs() << "LV: Unrolling because of reductions. \n"); + bool HasReductions = Legal->getReductionVars()->size(); + + // Decide if we want to unroll if we decided that it is legal to vectorize + // but not profitable. + if (VF == 1) { + if (TheLoop->getNumBlocks() > 1 || !HasReductions || + LoopCost > SmallLoopCost) + return 1; + + return UF; + } + + if (HasReductions) { + DEBUG(dbgs() << "LV: Unrolling because of reductions.\n"); return UF; } @@ -3395,14 +4634,14 @@ LoopVectorizationCostModel::selectUnrollFactor(bool OptForSize, // We assume that the cost overhead is 1 and we use the cost model // to estimate the cost of the loop and unroll until the cost of the // loop overhead is about 5% of the cost of the loop. - DEBUG(dbgs() << "LV: Loop cost is "<< LoopCost <<" \n"); - if (LoopCost < 20) { - DEBUG(dbgs() << "LV: Unrolling to reduce branch cost. \n"); - unsigned NewUF = 20/LoopCost + 1; + DEBUG(dbgs() << "LV: Loop cost is " << LoopCost << '\n'); + if (LoopCost < SmallLoopCost) { + DEBUG(dbgs() << "LV: Unrolling to reduce branch cost.\n"); + unsigned NewUF = SmallLoopCost / (LoopCost + 1); return std::min(NewUF, UF); } - DEBUG(dbgs() << "LV: Not Unrolling. \n"); + DEBUG(dbgs() << "LV: Not Unrolling.\n"); return 1; } @@ -3503,16 +4742,16 @@ LoopVectorizationCostModel::calculateRegisterUsage() { MaxUsage = std::max(MaxUsage, OpenIntervals.size()); DEBUG(dbgs() << "LV(REG): At #" << i << " Interval # " << - OpenIntervals.size() <<"\n"); + OpenIntervals.size() << '\n'); // Add the current instruction to the list of open intervals. OpenIntervals.insert(I); } unsigned Invariant = LoopInvariants.size(); - DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << " \n"); - DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << " \n"); - DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << " \n"); + DEBUG(dbgs() << "LV(REG): Found max usage: " << MaxUsage << '\n'); + DEBUG(dbgs() << "LV(REG): Found invariant usage: " << Invariant << '\n'); + DEBUG(dbgs() << "LV(REG): LoopSize: " << R.NumInstructions << '\n'); R.LoopInvariantRegs = Invariant; R.MaxLocalUsers = MaxUsage; @@ -3535,15 +4774,15 @@ unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) { continue; unsigned C = getInstructionCost(it, VF); - Cost += C; - DEBUG(dbgs() << "LV: Found an estimated cost of "<< C <<" for VF " << - VF << " For instruction: "<< *it << "\n"); + BlockCost += C; + DEBUG(dbgs() << "LV: Found an estimated cost of " << C << " for VF " << + VF << " For instruction: " << *it << '\n'); } // We assume that if-converted blocks have a 50% chance of being executed. // When the code is scalar then some of the blocks are avoided due to CF. // When the code is vectorized we execute all code paths. - if (Legal->blockNeedsPredication(*bb) && VF == 1) + if (VF == 1 && Legal->blockNeedsPredication(*bb)) BlockCost /= 2; Cost += BlockCost; @@ -3552,6 +4791,59 @@ unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) { return Cost; } +/// \brief Check whether the address computation for a non-consecutive memory +/// access looks like an unlikely candidate for being merged into the indexing +/// mode. +/// +/// We look for a GEP which has one index that is an induction variable and all +/// other indices are loop invariant. If the stride of this access is also +/// within a small bound we decide that this address computation can likely be +/// merged into the addressing mode. +/// In all other cases, we identify the address computation as complex. +static bool isLikelyComplexAddressComputation(Value *Ptr, + LoopVectorizationLegality *Legal, + ScalarEvolution *SE, + const Loop *TheLoop) { + GetElementPtrInst *Gep = dyn_cast<GetElementPtrInst>(Ptr); + if (!Gep) + return true; + + // We are looking for a gep with all loop invariant indices except for one + // which should be an induction variable. + unsigned NumOperands = Gep->getNumOperands(); + for (unsigned i = 1; i < NumOperands; ++i) { + Value *Opd = Gep->getOperand(i); + if (!SE->isLoopInvariant(SE->getSCEV(Opd), TheLoop) && + !Legal->isInductionVariable(Opd)) + return true; + } + + // Now we know we have a GEP ptr, %inv, %ind, %inv. Make sure that the step + // can likely be merged into the address computation. + unsigned MaxMergeDistance = 64; + + const SCEVAddRecExpr *AddRec = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(Ptr)); + if (!AddRec) + return true; + + // Check the step is constant. + const SCEV *Step = AddRec->getStepRecurrence(*SE); + // Calculate the pointer stride and check if it is consecutive. + const SCEVConstant *C = dyn_cast<SCEVConstant>(Step); + if (!C) + return true; + + const APInt &APStepVal = C->getValue()->getValue(); + + // Huge step value - give up. + if (APStepVal.getBitWidth() > 64) + return true; + + int64_t StepVal = APStepVal.getSExtValue(); + + return StepVal > MaxMergeDistance; +} + unsigned LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) { // If we know that this instruction will remain uniform, check the cost of @@ -3647,6 +4939,8 @@ LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) { unsigned ScalarAllocatedSize = DL->getTypeAllocSize(ValTy); unsigned VectorElementSize = DL->getTypeStoreSize(VectorTy)/VF; if (!ConsecutiveStride || ScalarAllocatedSize != VectorElementSize) { + bool IsComplexComputation = + isLikelyComplexAddressComputation(Ptr, Legal, SE, TheLoop); unsigned Cost = 0; // The cost of extracting from the value vector and pointer vector. Type *PtrTy = ToVectorTy(Ptr->getType(), VF); @@ -3662,7 +4956,7 @@ LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) { } // The cost of the scalar loads/stores. - Cost += VF * TTI.getAddressComputationCost(ValTy->getScalarType()); + Cost += VF * TTI.getAddressComputationCost(PtrTy, IsComplexComputation); Cost += VF * TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(), Alignment, AS); return Cost; @@ -3743,15 +5037,17 @@ Type* LoopVectorizationCostModel::ToVectorTy(Type *Scalar, unsigned VF) { char LoopVectorize::ID = 0; static const char lv_name[] = "Loop Vectorization"; INITIALIZE_PASS_BEGIN(LoopVectorize, LV_NAME, lv_name, false, false) -INITIALIZE_AG_DEPENDENCY(AliasAnalysis) INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) +INITIALIZE_PASS_DEPENDENCY(DominatorTree) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) +INITIALIZE_PASS_DEPENDENCY(LCSSA) +INITIALIZE_PASS_DEPENDENCY(LoopInfo) INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_END(LoopVectorize, LV_NAME, lv_name, false, false) namespace llvm { - Pass *createLoopVectorizePass() { - return new LoopVectorize(); + Pass *createLoopVectorizePass(bool NoUnrolling) { + return new LoopVectorize(NoUnrolling); } } @@ -3766,3 +5062,96 @@ bool LoopVectorizationCostModel::isConsecutiveLoadOrStore(Instruction *Inst) { return false; } + + +void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr) { + assert(!Instr->getType()->isAggregateType() && "Can't handle vectors"); + // Holds vector parameters or scalars, in case of uniform vals. + SmallVector<VectorParts, 4> Params; + + setDebugLocFromInst(Builder, Instr); + + // Find all of the vectorized parameters. + for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { + Value *SrcOp = Instr->getOperand(op); + + // If we are accessing the old induction variable, use the new one. + if (SrcOp == OldInduction) { + Params.push_back(getVectorValue(SrcOp)); + continue; + } + + // Try using previously calculated values. + Instruction *SrcInst = dyn_cast<Instruction>(SrcOp); + + // If the src is an instruction that appeared earlier in the basic block + // then it should already be vectorized. + if (SrcInst && OrigLoop->contains(SrcInst)) { + assert(WidenMap.has(SrcInst) && "Source operand is unavailable"); + // The parameter is a vector value from earlier. + Params.push_back(WidenMap.get(SrcInst)); + } else { + // The parameter is a scalar from outside the loop. Maybe even a constant. + VectorParts Scalars; + Scalars.append(UF, SrcOp); + Params.push_back(Scalars); + } + } + + assert(Params.size() == Instr->getNumOperands() && + "Invalid number of operands"); + + // Does this instruction return a value ? + bool IsVoidRetTy = Instr->getType()->isVoidTy(); + + Value *UndefVec = IsVoidRetTy ? 0 : + UndefValue::get(Instr->getType()); + // Create a new entry in the WidenMap and initialize it to Undef or Null. + VectorParts &VecResults = WidenMap.splat(Instr, UndefVec); + + // For each vector unroll 'part': + for (unsigned Part = 0; Part < UF; ++Part) { + // For each scalar that we create: + + Instruction *Cloned = Instr->clone(); + if (!IsVoidRetTy) + Cloned->setName(Instr->getName() + ".cloned"); + // Replace the operands of the cloned instructions with extracted scalars. + for (unsigned op = 0, e = Instr->getNumOperands(); op != e; ++op) { + Value *Op = Params[op][Part]; + Cloned->setOperand(op, Op); + } + + // Place the cloned scalar in the new loop. + Builder.Insert(Cloned); + + // If the original scalar returns a value we need to place it in a vector + // so that future users will be able to use it. + if (!IsVoidRetTy) + VecResults[Part] = Cloned; + } +} + +void +InnerLoopUnroller::vectorizeMemoryInstruction(Instruction *Instr, + LoopVectorizationLegality*) { + return scalarizeInstruction(Instr); +} + +Value *InnerLoopUnroller::reverseVector(Value *Vec) { + return Vec; +} + +Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { + return V; +} + +Value *InnerLoopUnroller::getConsecutiveVector(Value* Val, int StartIdx, + bool Negate) { + // When unrolling and the VF is 1, we only need to add a simple scalar. + Type *ITy = Val->getType(); + assert(!ITy->isVectorTy() && "Val must be a scalar"); + Constant *C = ConstantInt::get(ITy, StartIdx, Negate); + return Builder.CreateAdd(Val, C, "induction"); +} + diff --git a/contrib/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/contrib/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp index cc30cc9..c72b51f 100644 --- a/contrib/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/contrib/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -16,18 +16,23 @@ // //===----------------------------------------------------------------------===// #define SV_NAME "slp-vectorizer" -#define DEBUG_TYPE SV_NAME +#define DEBUG_TYPE "SLP" -#include "VecUtils.h" #include "llvm/Transforms/Vectorize.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/SetVector.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/ValueTracking.h" #include "llvm/Analysis/Verifier.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/IRBuilder.h" #include "llvm/IR/Module.h" #include "llvm/IR/Type.h" #include "llvm/IR/Value.h" @@ -35,19 +40,1717 @@ #include "llvm/Support/CommandLine.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include <algorithm> #include <map> using namespace llvm; static cl::opt<int> -SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden, - cl::desc("Only vectorize trees if the gain is above this " - "number. (gain = -cost of vectorization)")); + SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden, + cl::desc("Only vectorize if you gain more than this " + "number ")); + +static cl::opt<bool> +ShouldVectorizeHor("slp-vectorize-hor", cl::init(false), cl::Hidden, + cl::desc("Attempt to vectorize horizontal reductions")); + +static cl::opt<bool> ShouldStartVectorizeHorAtStore( + "slp-vectorize-hor-store", cl::init(false), cl::Hidden, + cl::desc( + "Attempt to vectorize horizontal reductions feeding into a store")); + namespace { +static const unsigned MinVecRegSize = 128; + +static const unsigned RecursionMaxDepth = 12; + +/// A helper class for numbering instructions in multiple blocks. +/// Numbers start at zero for each basic block. +struct BlockNumbering { + + BlockNumbering(BasicBlock *Bb) : BB(Bb), Valid(false) {} + + BlockNumbering() : BB(0), Valid(false) {} + + void numberInstructions() { + unsigned Loc = 0; + InstrIdx.clear(); + InstrVec.clear(); + // Number the instructions in the block. + for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { + InstrIdx[it] = Loc++; + InstrVec.push_back(it); + assert(InstrVec[InstrIdx[it]] == it && "Invalid allocation"); + } + Valid = true; + } + + int getIndex(Instruction *I) { + assert(I->getParent() == BB && "Invalid instruction"); + if (!Valid) + numberInstructions(); + assert(InstrIdx.count(I) && "Unknown instruction"); + return InstrIdx[I]; + } + + Instruction *getInstruction(unsigned loc) { + if (!Valid) + numberInstructions(); + assert(InstrVec.size() > loc && "Invalid Index"); + return InstrVec[loc]; + } + + void forget() { Valid = false; } + +private: + /// The block we are numbering. + BasicBlock *BB; + /// Is the block numbered. + bool Valid; + /// Maps instructions to numbers and back. + SmallDenseMap<Instruction *, int> InstrIdx; + /// Maps integers to Instructions. + SmallVector<Instruction *, 32> InstrVec; +}; + +/// \returns the parent basic block if all of the instructions in \p VL +/// are in the same block or null otherwise. +static BasicBlock *getSameBlock(ArrayRef<Value *> VL) { + Instruction *I0 = dyn_cast<Instruction>(VL[0]); + if (!I0) + return 0; + BasicBlock *BB = I0->getParent(); + for (int i = 1, e = VL.size(); i < e; i++) { + Instruction *I = dyn_cast<Instruction>(VL[i]); + if (!I) + return 0; + + if (BB != I->getParent()) + return 0; + } + return BB; +} + +/// \returns True if all of the values in \p VL are constants. +static bool allConstant(ArrayRef<Value *> VL) { + for (unsigned i = 0, e = VL.size(); i < e; ++i) + if (!isa<Constant>(VL[i])) + return false; + return true; +} + +/// \returns True if all of the values in \p VL are identical. +static bool isSplat(ArrayRef<Value *> VL) { + for (unsigned i = 1, e = VL.size(); i < e; ++i) + if (VL[i] != VL[0]) + return false; + return true; +} + +/// \returns The opcode if all of the Instructions in \p VL have the same +/// opcode, or zero. +static unsigned getSameOpcode(ArrayRef<Value *> VL) { + Instruction *I0 = dyn_cast<Instruction>(VL[0]); + if (!I0) + return 0; + unsigned Opcode = I0->getOpcode(); + for (int i = 1, e = VL.size(); i < e; i++) { + Instruction *I = dyn_cast<Instruction>(VL[i]); + if (!I || Opcode != I->getOpcode()) + return 0; + } + return Opcode; +} + +/// \returns \p I after propagating metadata from \p VL. +static Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL) { + Instruction *I0 = cast<Instruction>(VL[0]); + SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata; + I0->getAllMetadataOtherThanDebugLoc(Metadata); + + for (unsigned i = 0, n = Metadata.size(); i != n; ++i) { + unsigned Kind = Metadata[i].first; + MDNode *MD = Metadata[i].second; + + for (int i = 1, e = VL.size(); MD && i != e; i++) { + Instruction *I = cast<Instruction>(VL[i]); + MDNode *IMD = I->getMetadata(Kind); + + switch (Kind) { + default: + MD = 0; // Remove unknown metadata + break; + case LLVMContext::MD_tbaa: + MD = MDNode::getMostGenericTBAA(MD, IMD); + break; + case LLVMContext::MD_fpmath: + MD = MDNode::getMostGenericFPMath(MD, IMD); + break; + } + } + I->setMetadata(Kind, MD); + } + return I; +} + +/// \returns The type that all of the values in \p VL have or null if there +/// are different types. +static Type* getSameType(ArrayRef<Value *> VL) { + Type *Ty = VL[0]->getType(); + for (int i = 1, e = VL.size(); i < e; i++) + if (VL[i]->getType() != Ty) + return 0; + + return Ty; +} + +/// \returns True if the ExtractElement instructions in VL can be vectorized +/// to use the original vector. +static bool CanReuseExtract(ArrayRef<Value *> VL) { + assert(Instruction::ExtractElement == getSameOpcode(VL) && "Invalid opcode"); + // Check if all of the extracts come from the same vector and from the + // correct offset. + Value *VL0 = VL[0]; + ExtractElementInst *E0 = cast<ExtractElementInst>(VL0); + Value *Vec = E0->getOperand(0); + + // We have to extract from the same vector type. + unsigned NElts = Vec->getType()->getVectorNumElements(); + + if (NElts != VL.size()) + return false; + + // Check that all of the indices extract from the correct offset. + ConstantInt *CI = dyn_cast<ConstantInt>(E0->getOperand(1)); + if (!CI || CI->getZExtValue()) + return false; + + for (unsigned i = 1, e = VL.size(); i < e; ++i) { + ExtractElementInst *E = cast<ExtractElementInst>(VL[i]); + ConstantInt *CI = dyn_cast<ConstantInt>(E->getOperand(1)); + + if (!CI || CI->getZExtValue() != i || E->getOperand(0) != Vec) + return false; + } + + return true; +} + +static void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL, + SmallVectorImpl<Value *> &Left, + SmallVectorImpl<Value *> &Right) { + + SmallVector<Value *, 16> OrigLeft, OrigRight; + + bool AllSameOpcodeLeft = true; + bool AllSameOpcodeRight = true; + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + Instruction *I = cast<Instruction>(VL[i]); + Value *V0 = I->getOperand(0); + Value *V1 = I->getOperand(1); + + OrigLeft.push_back(V0); + OrigRight.push_back(V1); + + Instruction *I0 = dyn_cast<Instruction>(V0); + Instruction *I1 = dyn_cast<Instruction>(V1); + + // Check whether all operands on one side have the same opcode. In this case + // we want to preserve the original order and not make things worse by + // reordering. + AllSameOpcodeLeft = I0; + AllSameOpcodeRight = I1; + + if (i && AllSameOpcodeLeft) { + if(Instruction *P0 = dyn_cast<Instruction>(OrigLeft[i-1])) { + if(P0->getOpcode() != I0->getOpcode()) + AllSameOpcodeLeft = false; + } else + AllSameOpcodeLeft = false; + } + if (i && AllSameOpcodeRight) { + if(Instruction *P1 = dyn_cast<Instruction>(OrigRight[i-1])) { + if(P1->getOpcode() != I1->getOpcode()) + AllSameOpcodeRight = false; + } else + AllSameOpcodeRight = false; + } + + // Sort two opcodes. In the code below we try to preserve the ability to use + // broadcast of values instead of individual inserts. + // vl1 = load + // vl2 = phi + // vr1 = load + // vr2 = vr2 + // = vl1 x vr1 + // = vl2 x vr2 + // If we just sorted according to opcode we would leave the first line in + // tact but we would swap vl2 with vr2 because opcode(phi) > opcode(load). + // = vl1 x vr1 + // = vr2 x vl2 + // Because vr2 and vr1 are from the same load we loose the opportunity of a + // broadcast for the packed right side in the backend: we have [vr1, vl2] + // instead of [vr1, vr2=vr1]. + if (I0 && I1) { + if(!i && I0->getOpcode() > I1->getOpcode()) { + Left.push_back(I1); + Right.push_back(I0); + } else if (i && I0->getOpcode() > I1->getOpcode() && Right[i-1] != I1) { + // Try not to destroy a broad cast for no apparent benefit. + Left.push_back(I1); + Right.push_back(I0); + } else if (i && I0->getOpcode() == I1->getOpcode() && Right[i-1] == I0) { + // Try preserve broadcasts. + Left.push_back(I1); + Right.push_back(I0); + } else if (i && I0->getOpcode() == I1->getOpcode() && Left[i-1] == I1) { + // Try preserve broadcasts. + Left.push_back(I1); + Right.push_back(I0); + } else { + Left.push_back(I0); + Right.push_back(I1); + } + continue; + } + // One opcode, put the instruction on the right. + if (I0) { + Left.push_back(V1); + Right.push_back(I0); + continue; + } + Left.push_back(V0); + Right.push_back(V1); + } + + bool LeftBroadcast = isSplat(Left); + bool RightBroadcast = isSplat(Right); + + // Don't reorder if the operands where good to begin with. + if (!(LeftBroadcast || RightBroadcast) && + (AllSameOpcodeRight || AllSameOpcodeLeft)) { + Left = OrigLeft; + Right = OrigRight; + } +} + +/// Bottom Up SLP Vectorizer. +class BoUpSLP { +public: + typedef SmallVector<Value *, 8> ValueList; + typedef SmallVector<Instruction *, 16> InstrList; + typedef SmallPtrSet<Value *, 16> ValueSet; + typedef SmallVector<StoreInst *, 8> StoreList; + + BoUpSLP(Function *Func, ScalarEvolution *Se, DataLayout *Dl, + TargetTransformInfo *Tti, AliasAnalysis *Aa, LoopInfo *Li, + DominatorTree *Dt) : + F(Func), SE(Se), DL(Dl), TTI(Tti), AA(Aa), LI(Li), DT(Dt), + Builder(Se->getContext()) { + // Setup the block numbering utility for all of the blocks in the + // function. + for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it) { + BasicBlock *BB = it; + BlocksNumbers[BB] = BlockNumbering(BB); + } + } + + /// \brief Vectorize the tree that starts with the elements in \p VL. + /// Returns the vectorized root. + Value *vectorizeTree(); + + /// \returns the vectorization cost of the subtree that starts at \p VL. + /// A negative number means that this is profitable. + int getTreeCost(); + + /// Construct a vectorizable tree that starts at \p Roots and is possibly + /// used by a reduction of \p RdxOps. + void buildTree(ArrayRef<Value *> Roots, ValueSet *RdxOps = 0); + + /// Clear the internal data structures that are created by 'buildTree'. + void deleteTree() { + RdxOps = 0; + VectorizableTree.clear(); + ScalarToTreeEntry.clear(); + MustGather.clear(); + ExternalUses.clear(); + MemBarrierIgnoreList.clear(); + } + + /// \returns true if the memory operations A and B are consecutive. + bool isConsecutiveAccess(Value *A, Value *B); + + /// \brief Perform LICM and CSE on the newly generated gather sequences. + void optimizeGatherSequence(); +private: + struct TreeEntry; + + /// \returns the cost of the vectorizable entry. + int getEntryCost(TreeEntry *E); + + /// This is the recursive part of buildTree. + void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth); + + /// Vectorize a single entry in the tree. + Value *vectorizeTree(TreeEntry *E); + + /// Vectorize a single entry in the tree, starting in \p VL. + Value *vectorizeTree(ArrayRef<Value *> VL); + + /// \returns the pointer to the vectorized value if \p VL is already + /// vectorized, or NULL. They may happen in cycles. + Value *alreadyVectorized(ArrayRef<Value *> VL) const; + + /// \brief Take the pointer operand from the Load/Store instruction. + /// \returns NULL if this is not a valid Load/Store instruction. + static Value *getPointerOperand(Value *I); + + /// \brief Take the address space operand from the Load/Store instruction. + /// \returns -1 if this is not a valid Load/Store instruction. + static unsigned getAddressSpaceOperand(Value *I); + + /// \returns the scalarization cost for this type. Scalarization in this + /// context means the creation of vectors from a group of scalars. + int getGatherCost(Type *Ty); + + /// \returns the scalarization cost for this list of values. Assuming that + /// this subtree gets vectorized, we may need to extract the values from the + /// roots. This method calculates the cost of extracting the values. + int getGatherCost(ArrayRef<Value *> VL); + + /// \returns the AA location that is being access by the instruction. + AliasAnalysis::Location getLocation(Instruction *I); + + /// \brief Checks if it is possible to sink an instruction from + /// \p Src to \p Dst. + /// \returns the pointer to the barrier instruction if we can't sink. + Value *getSinkBarrier(Instruction *Src, Instruction *Dst); + + /// \returns the index of the last instruction in the BB from \p VL. + int getLastIndex(ArrayRef<Value *> VL); + + /// \returns the Instruction in the bundle \p VL. + Instruction *getLastInstruction(ArrayRef<Value *> VL); + + /// \brief Set the Builder insert point to one after the last instruction in + /// the bundle + void setInsertPointAfterBundle(ArrayRef<Value *> VL); + + /// \returns a vector from a collection of scalars in \p VL. + Value *Gather(ArrayRef<Value *> VL, VectorType *Ty); + + /// \returns whether the VectorizableTree is fully vectoriable and will + /// be beneficial even the tree height is tiny. + bool isFullyVectorizableTinyTree(); + + struct TreeEntry { + TreeEntry() : Scalars(), VectorizedValue(0), LastScalarIndex(0), + NeedToGather(0) {} + + /// \returns true if the scalars in VL are equal to this entry. + bool isSame(ArrayRef<Value *> VL) const { + assert(VL.size() == Scalars.size() && "Invalid size"); + return std::equal(VL.begin(), VL.end(), Scalars.begin()); + } + + /// A vector of scalars. + ValueList Scalars; + + /// The Scalars are vectorized into this value. It is initialized to Null. + Value *VectorizedValue; + + /// The index in the basic block of the last scalar. + int LastScalarIndex; + + /// Do we need to gather this sequence ? + bool NeedToGather; + }; + + /// Create a new VectorizableTree entry. + TreeEntry *newTreeEntry(ArrayRef<Value *> VL, bool Vectorized) { + VectorizableTree.push_back(TreeEntry()); + int idx = VectorizableTree.size() - 1; + TreeEntry *Last = &VectorizableTree[idx]; + Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end()); + Last->NeedToGather = !Vectorized; + if (Vectorized) { + Last->LastScalarIndex = getLastIndex(VL); + for (int i = 0, e = VL.size(); i != e; ++i) { + assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!"); + ScalarToTreeEntry[VL[i]] = idx; + } + } else { + Last->LastScalarIndex = 0; + MustGather.insert(VL.begin(), VL.end()); + } + return Last; + } + + /// -- Vectorization State -- + /// Holds all of the tree entries. + std::vector<TreeEntry> VectorizableTree; + + /// Maps a specific scalar to its tree entry. + SmallDenseMap<Value*, int> ScalarToTreeEntry; + + /// A list of scalars that we found that we need to keep as scalars. + ValueSet MustGather; + + /// This POD struct describes one external user in the vectorized tree. + struct ExternalUser { + ExternalUser (Value *S, llvm::User *U, int L) : + Scalar(S), User(U), Lane(L){}; + // Which scalar in our function. + Value *Scalar; + // Which user that uses the scalar. + llvm::User *User; + // Which lane does the scalar belong to. + int Lane; + }; + typedef SmallVector<ExternalUser, 16> UserList; + + /// A list of values that need to extracted out of the tree. + /// This list holds pairs of (Internal Scalar : External User). + UserList ExternalUses; + + /// A list of instructions to ignore while sinking + /// memory instructions. This map must be reset between runs of getCost. + ValueSet MemBarrierIgnoreList; + + /// Holds all of the instructions that we gathered. + SetVector<Instruction *> GatherSeq; + /// A list of blocks that we are going to CSE. + SmallSet<BasicBlock *, 8> CSEBlocks; + + /// Numbers instructions in different blocks. + DenseMap<BasicBlock *, BlockNumbering> BlocksNumbers; + + /// Reduction operators. + ValueSet *RdxOps; + + // Analysis and block reference. + Function *F; + ScalarEvolution *SE; + DataLayout *DL; + TargetTransformInfo *TTI; + AliasAnalysis *AA; + LoopInfo *LI; + DominatorTree *DT; + /// Instruction builder to construct the vectorized tree. + IRBuilder<> Builder; +}; + +void BoUpSLP::buildTree(ArrayRef<Value *> Roots, ValueSet *Rdx) { + deleteTree(); + RdxOps = Rdx; + if (!getSameType(Roots)) + return; + buildTree_rec(Roots, 0); + + // Collect the values that we need to extract from the tree. + for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) { + TreeEntry *Entry = &VectorizableTree[EIdx]; + + // For each lane: + for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) { + Value *Scalar = Entry->Scalars[Lane]; + + // No need to handle users of gathered values. + if (Entry->NeedToGather) + continue; + + for (Value::use_iterator User = Scalar->use_begin(), + UE = Scalar->use_end(); User != UE; ++User) { + DEBUG(dbgs() << "SLP: Checking user:" << **User << ".\n"); + + // Skip in-tree scalars that become vectors. + if (ScalarToTreeEntry.count(*User)) { + DEBUG(dbgs() << "SLP: \tInternal user will be removed:" << + **User << ".\n"); + int Idx = ScalarToTreeEntry[*User]; (void) Idx; + assert(!VectorizableTree[Idx].NeedToGather && "Bad state"); + continue; + } + Instruction *UserInst = dyn_cast<Instruction>(*User); + if (!UserInst) + continue; + + // Ignore uses that are part of the reduction. + if (Rdx && std::find(Rdx->begin(), Rdx->end(), UserInst) != Rdx->end()) + continue; + + DEBUG(dbgs() << "SLP: Need to extract:" << **User << " from lane " << + Lane << " from " << *Scalar << ".\n"); + ExternalUses.push_back(ExternalUser(Scalar, *User, Lane)); + } + } + } +} + + +void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) { + bool SameTy = getSameType(VL); (void)SameTy; + assert(SameTy && "Invalid types!"); + + if (Depth == RecursionMaxDepth) { + DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n"); + newTreeEntry(VL, false); + return; + } + + // Don't handle vectors. + if (VL[0]->getType()->isVectorTy()) { + DEBUG(dbgs() << "SLP: Gathering due to vector type.\n"); + newTreeEntry(VL, false); + return; + } + + if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) + if (SI->getValueOperand()->getType()->isVectorTy()) { + DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n"); + newTreeEntry(VL, false); + return; + } + + // If all of the operands are identical or constant we have a simple solution. + if (allConstant(VL) || isSplat(VL) || !getSameBlock(VL) || + !getSameOpcode(VL)) { + DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n"); + newTreeEntry(VL, false); + return; + } + + // We now know that this is a vector of instructions of the same type from + // the same block. + + // Check if this is a duplicate of another entry. + if (ScalarToTreeEntry.count(VL[0])) { + int Idx = ScalarToTreeEntry[VL[0]]; + TreeEntry *E = &VectorizableTree[Idx]; + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n"); + if (E->Scalars[i] != VL[i]) { + DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n"); + newTreeEntry(VL, false); + return; + } + } + DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *VL[0] << ".\n"); + return; + } + + // Check that none of the instructions in the bundle are already in the tree. + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + if (ScalarToTreeEntry.count(VL[i])) { + DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] << + ") is already in tree.\n"); + newTreeEntry(VL, false); + return; + } + } + + // If any of the scalars appears in the table OR it is marked as a value that + // needs to stat scalar then we need to gather the scalars. + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + if (ScalarToTreeEntry.count(VL[i]) || MustGather.count(VL[i])) { + DEBUG(dbgs() << "SLP: Gathering due to gathered scalar. \n"); + newTreeEntry(VL, false); + return; + } + } + + // Check that all of the users of the scalars that we want to vectorize are + // schedulable. + Instruction *VL0 = cast<Instruction>(VL[0]); + int MyLastIndex = getLastIndex(VL); + BasicBlock *BB = cast<Instruction>(VL0)->getParent(); + + for (unsigned i = 0, e = VL.size(); i != e; ++i) { + Instruction *Scalar = cast<Instruction>(VL[i]); + DEBUG(dbgs() << "SLP: Checking users of " << *Scalar << ". \n"); + for (Value::use_iterator U = Scalar->use_begin(), UE = Scalar->use_end(); + U != UE; ++U) { + DEBUG(dbgs() << "SLP: \tUser " << **U << ". \n"); + Instruction *User = dyn_cast<Instruction>(*U); + if (!User) { + DEBUG(dbgs() << "SLP: Gathering due unknown user. \n"); + newTreeEntry(VL, false); + return; + } + + // We don't care if the user is in a different basic block. + BasicBlock *UserBlock = User->getParent(); + if (UserBlock != BB) { + DEBUG(dbgs() << "SLP: User from a different basic block " + << *User << ". \n"); + continue; + } + + // If this is a PHINode within this basic block then we can place the + // extract wherever we want. + if (isa<PHINode>(*User)) { + DEBUG(dbgs() << "SLP: \tWe can schedule PHIs:" << *User << ". \n"); + continue; + } + + // Check if this is a safe in-tree user. + if (ScalarToTreeEntry.count(User)) { + int Idx = ScalarToTreeEntry[User]; + int VecLocation = VectorizableTree[Idx].LastScalarIndex; + if (VecLocation <= MyLastIndex) { + DEBUG(dbgs() << "SLP: Gathering due to unschedulable vector. \n"); + newTreeEntry(VL, false); + return; + } + DEBUG(dbgs() << "SLP: In-tree user (" << *User << ") at #" << + VecLocation << " vector value (" << *Scalar << ") at #" + << MyLastIndex << ".\n"); + continue; + } + + // This user is part of the reduction. + if (RdxOps && RdxOps->count(User)) + continue; + + // Make sure that we can schedule this unknown user. + BlockNumbering &BN = BlocksNumbers[BB]; + int UserIndex = BN.getIndex(User); + if (UserIndex < MyLastIndex) { + + DEBUG(dbgs() << "SLP: Can't schedule extractelement for " + << *User << ". \n"); + newTreeEntry(VL, false); + return; + } + } + } + + // Check that every instructions appears once in this bundle. + for (unsigned i = 0, e = VL.size(); i < e; ++i) + for (unsigned j = i+1; j < e; ++j) + if (VL[i] == VL[j]) { + DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n"); + newTreeEntry(VL, false); + return; + } + + // Check that instructions in this bundle don't reference other instructions. + // The runtime of this check is O(N * N-1 * uses(N)) and a typical N is 4. + for (unsigned i = 0, e = VL.size(); i < e; ++i) { + for (Value::use_iterator U = VL[i]->use_begin(), UE = VL[i]->use_end(); + U != UE; ++U) { + for (unsigned j = 0; j < e; ++j) { + if (i != j && *U == VL[j]) { + DEBUG(dbgs() << "SLP: Intra-bundle dependencies!" << **U << ". \n"); + newTreeEntry(VL, false); + return; + } + } + } + } + + DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n"); + + unsigned Opcode = getSameOpcode(VL); + + // Check if it is safe to sink the loads or the stores. + if (Opcode == Instruction::Load || Opcode == Instruction::Store) { + Instruction *Last = getLastInstruction(VL); + + for (unsigned i = 0, e = VL.size(); i < e; ++i) { + if (VL[i] == Last) + continue; + Value *Barrier = getSinkBarrier(cast<Instruction>(VL[i]), Last); + if (Barrier) { + DEBUG(dbgs() << "SLP: Can't sink " << *VL[i] << "\n down to " << *Last + << "\n because of " << *Barrier << ". Gathering.\n"); + newTreeEntry(VL, false); + return; + } + } + } + + switch (Opcode) { + case Instruction::PHI: { + PHINode *PH = dyn_cast<PHINode>(VL0); + + // Check for terminator values (e.g. invoke). + for (unsigned j = 0; j < VL.size(); ++j) + for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { + TerminatorInst *Term = dyn_cast<TerminatorInst>(cast<PHINode>(VL[j])->getIncomingValue(i)); + if (Term) { + DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n"); + newTreeEntry(VL, false); + return; + } + } + + newTreeEntry(VL, true); + DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n"); + + for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { + ValueList Operands; + // Prepare the operand vector. + for (unsigned j = 0; j < VL.size(); ++j) + Operands.push_back(cast<PHINode>(VL[j])->getIncomingValue(i)); + + buildTree_rec(Operands, Depth + 1); + } + return; + } + case Instruction::ExtractElement: { + bool Reuse = CanReuseExtract(VL); + if (Reuse) { + DEBUG(dbgs() << "SLP: Reusing extract sequence.\n"); + } + newTreeEntry(VL, Reuse); + return; + } + case Instruction::Load: { + // Check if the loads are consecutive or of we need to swizzle them. + for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) { + LoadInst *L = cast<LoadInst>(VL[i]); + if (!L->isSimple() || !isConsecutiveAccess(VL[i], VL[i + 1])) { + newTreeEntry(VL, false); + DEBUG(dbgs() << "SLP: Need to swizzle loads.\n"); + return; + } + } + newTreeEntry(VL, true); + DEBUG(dbgs() << "SLP: added a vector of loads.\n"); + return; + } + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::FPExt: + case Instruction::PtrToInt: + case Instruction::IntToPtr: + case Instruction::SIToFP: + case Instruction::UIToFP: + case Instruction::Trunc: + case Instruction::FPTrunc: + case Instruction::BitCast: { + Type *SrcTy = VL0->getOperand(0)->getType(); + for (unsigned i = 0; i < VL.size(); ++i) { + Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType(); + if (Ty != SrcTy || Ty->isAggregateType() || Ty->isVectorTy()) { + newTreeEntry(VL, false); + DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n"); + return; + } + } + newTreeEntry(VL, true); + DEBUG(dbgs() << "SLP: added a vector of casts.\n"); + + for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { + ValueList Operands; + // Prepare the operand vector. + for (unsigned j = 0; j < VL.size(); ++j) + Operands.push_back(cast<Instruction>(VL[j])->getOperand(i)); + + buildTree_rec(Operands, Depth+1); + } + return; + } + case Instruction::ICmp: + case Instruction::FCmp: { + // Check that all of the compares have the same predicate. + CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate(); + Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType(); + for (unsigned i = 1, e = VL.size(); i < e; ++i) { + CmpInst *Cmp = cast<CmpInst>(VL[i]); + if (Cmp->getPredicate() != P0 || + Cmp->getOperand(0)->getType() != ComparedTy) { + newTreeEntry(VL, false); + DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n"); + return; + } + } + + newTreeEntry(VL, true); + DEBUG(dbgs() << "SLP: added a vector of compares.\n"); + + for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { + ValueList Operands; + // Prepare the operand vector. + for (unsigned j = 0; j < VL.size(); ++j) + Operands.push_back(cast<Instruction>(VL[j])->getOperand(i)); + + buildTree_rec(Operands, Depth+1); + } + return; + } + case Instruction::Select: + 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: { + newTreeEntry(VL, true); + DEBUG(dbgs() << "SLP: added a vector of bin op.\n"); + + // Sort operands of the instructions so that each side is more likely to + // have the same opcode. + if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) { + ValueList Left, Right; + reorderInputsAccordingToOpcode(VL, Left, Right); + buildTree_rec(Left, Depth + 1); + buildTree_rec(Right, Depth + 1); + return; + } + + for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { + ValueList Operands; + // Prepare the operand vector. + for (unsigned j = 0; j < VL.size(); ++j) + Operands.push_back(cast<Instruction>(VL[j])->getOperand(i)); + + buildTree_rec(Operands, Depth+1); + } + return; + } + case Instruction::Store: { + // Check if the stores are consecutive or of we need to swizzle them. + for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) + if (!isConsecutiveAccess(VL[i], VL[i + 1])) { + newTreeEntry(VL, false); + DEBUG(dbgs() << "SLP: Non consecutive store.\n"); + return; + } + + newTreeEntry(VL, true); + DEBUG(dbgs() << "SLP: added a vector of stores.\n"); + + ValueList Operands; + for (unsigned j = 0; j < VL.size(); ++j) + Operands.push_back(cast<Instruction>(VL[j])->getOperand(0)); + + // We can ignore these values because we are sinking them down. + MemBarrierIgnoreList.insert(VL.begin(), VL.end()); + buildTree_rec(Operands, Depth + 1); + return; + } + default: + newTreeEntry(VL, false); + DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n"); + return; + } +} + +int BoUpSLP::getEntryCost(TreeEntry *E) { + ArrayRef<Value*> VL = E->Scalars; + + Type *ScalarTy = VL[0]->getType(); + if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) + ScalarTy = SI->getValueOperand()->getType(); + VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); + + if (E->NeedToGather) { + if (allConstant(VL)) + return 0; + if (isSplat(VL)) { + return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0); + } + return getGatherCost(E->Scalars); + } + + assert(getSameOpcode(VL) && getSameType(VL) && getSameBlock(VL) && + "Invalid VL"); + Instruction *VL0 = cast<Instruction>(VL[0]); + unsigned Opcode = VL0->getOpcode(); + switch (Opcode) { + case Instruction::PHI: { + return 0; + } + case Instruction::ExtractElement: { + if (CanReuseExtract(VL)) + return 0; + return getGatherCost(VecTy); + } + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::FPExt: + case Instruction::PtrToInt: + case Instruction::IntToPtr: + case Instruction::SIToFP: + case Instruction::UIToFP: + case Instruction::Trunc: + case Instruction::FPTrunc: + case Instruction::BitCast: { + Type *SrcTy = VL0->getOperand(0)->getType(); + + // Calculate the cost of this instruction. + int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(), + VL0->getType(), SrcTy); + + VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size()); + int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy); + return VecCost - ScalarCost; + } + case Instruction::FCmp: + case Instruction::ICmp: + case Instruction::Select: + 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: { + // Calculate the cost of this instruction. + int ScalarCost = 0; + int VecCost = 0; + if (Opcode == Instruction::FCmp || Opcode == Instruction::ICmp || + Opcode == Instruction::Select) { + VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size()); + ScalarCost = VecTy->getNumElements() * + TTI->getCmpSelInstrCost(Opcode, ScalarTy, Builder.getInt1Ty()); + VecCost = TTI->getCmpSelInstrCost(Opcode, VecTy, MaskTy); + } else { + // Certain instructions can be cheaper to vectorize if they have a + // constant second vector operand. + TargetTransformInfo::OperandValueKind Op1VK = + TargetTransformInfo::OK_AnyValue; + TargetTransformInfo::OperandValueKind Op2VK = + TargetTransformInfo::OK_UniformConstantValue; + + // Check whether all second operands are constant. + for (unsigned i = 0; i < VL.size(); ++i) + if (!isa<ConstantInt>(cast<Instruction>(VL[i])->getOperand(1))) { + Op2VK = TargetTransformInfo::OK_AnyValue; + break; + } + + ScalarCost = + VecTy->getNumElements() * + TTI->getArithmeticInstrCost(Opcode, ScalarTy, Op1VK, Op2VK); + VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy, Op1VK, Op2VK); + } + return VecCost - ScalarCost; + } + case Instruction::Load: { + // Cost of wide load - cost of scalar loads. + int ScalarLdCost = VecTy->getNumElements() * + TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0); + int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, VecTy, 1, 0); + return VecLdCost - ScalarLdCost; + } + case Instruction::Store: { + // We know that we can merge the stores. Calculate the cost. + int ScalarStCost = VecTy->getNumElements() * + TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0); + int VecStCost = TTI->getMemoryOpCost(Instruction::Store, VecTy, 1, 0); + return VecStCost - ScalarStCost; + } + default: + llvm_unreachable("Unknown instruction"); + } +} + +bool BoUpSLP::isFullyVectorizableTinyTree() { + DEBUG(dbgs() << "SLP: Check whether the tree with height " << + VectorizableTree.size() << " is fully vectorizable .\n"); + + // We only handle trees of height 2. + if (VectorizableTree.size() != 2) + return false; + + // Gathering cost would be too much for tiny trees. + if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather) + return false; + + return true; +} + +int BoUpSLP::getTreeCost() { + int Cost = 0; + DEBUG(dbgs() << "SLP: Calculating cost for tree of size " << + VectorizableTree.size() << ".\n"); + + // We only vectorize tiny trees if it is fully vectorizable. + if (VectorizableTree.size() < 3 && !isFullyVectorizableTinyTree()) { + if (!VectorizableTree.size()) { + assert(!ExternalUses.size() && "We should not have any external users"); + } + return INT_MAX; + } + + unsigned BundleWidth = VectorizableTree[0].Scalars.size(); + + for (unsigned i = 0, e = VectorizableTree.size(); i != e; ++i) { + int C = getEntryCost(&VectorizableTree[i]); + DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with " + << *VectorizableTree[i].Scalars[0] << " .\n"); + Cost += C; + } + + int ExtractCost = 0; + for (UserList::iterator I = ExternalUses.begin(), E = ExternalUses.end(); + I != E; ++I) { + + VectorType *VecTy = VectorType::get(I->Scalar->getType(), BundleWidth); + ExtractCost += TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, + I->Lane); + } + + + DEBUG(dbgs() << "SLP: Total Cost " << Cost + ExtractCost<< ".\n"); + return Cost + ExtractCost; +} + +int BoUpSLP::getGatherCost(Type *Ty) { + int Cost = 0; + for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i) + Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i); + return Cost; +} + +int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) { + // Find the type of the operands in VL. + Type *ScalarTy = VL[0]->getType(); + if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) + ScalarTy = SI->getValueOperand()->getType(); + VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); + // Find the cost of inserting/extracting values from the vector. + return getGatherCost(VecTy); +} + +AliasAnalysis::Location BoUpSLP::getLocation(Instruction *I) { + if (StoreInst *SI = dyn_cast<StoreInst>(I)) + return AA->getLocation(SI); + if (LoadInst *LI = dyn_cast<LoadInst>(I)) + return AA->getLocation(LI); + return AliasAnalysis::Location(); +} + +Value *BoUpSLP::getPointerOperand(Value *I) { + if (LoadInst *LI = dyn_cast<LoadInst>(I)) + return LI->getPointerOperand(); + if (StoreInst *SI = dyn_cast<StoreInst>(I)) + return SI->getPointerOperand(); + return 0; +} + +unsigned BoUpSLP::getAddressSpaceOperand(Value *I) { + if (LoadInst *L = dyn_cast<LoadInst>(I)) + return L->getPointerAddressSpace(); + if (StoreInst *S = dyn_cast<StoreInst>(I)) + return S->getPointerAddressSpace(); + return -1; +} + +bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B) { + Value *PtrA = getPointerOperand(A); + Value *PtrB = getPointerOperand(B); + unsigned ASA = getAddressSpaceOperand(A); + unsigned ASB = getAddressSpaceOperand(B); + + // Check that the address spaces match and that the pointers are valid. + if (!PtrA || !PtrB || (ASA != ASB)) + return false; + + // Make sure that A and B are different pointers of the same type. + if (PtrA == PtrB || PtrA->getType() != PtrB->getType()) + return false; + + unsigned PtrBitWidth = DL->getPointerSizeInBits(ASA); + Type *Ty = cast<PointerType>(PtrA->getType())->getElementType(); + APInt Size(PtrBitWidth, DL->getTypeStoreSize(Ty)); + + APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0); + PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(*DL, OffsetA); + PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(*DL, OffsetB); + + APInt OffsetDelta = OffsetB - OffsetA; + + // Check if they are based on the same pointer. That makes the offsets + // sufficient. + if (PtrA == PtrB) + return OffsetDelta == Size; + + // Compute the necessary base pointer delta to have the necessary final delta + // equal to the size. + APInt BaseDelta = Size - OffsetDelta; + + // Otherwise compute the distance with SCEV between the base pointers. + const SCEV *PtrSCEVA = SE->getSCEV(PtrA); + const SCEV *PtrSCEVB = SE->getSCEV(PtrB); + const SCEV *C = SE->getConstant(BaseDelta); + const SCEV *X = SE->getAddExpr(PtrSCEVA, C); + return X == PtrSCEVB; +} + +Value *BoUpSLP::getSinkBarrier(Instruction *Src, Instruction *Dst) { + assert(Src->getParent() == Dst->getParent() && "Not the same BB"); + BasicBlock::iterator I = Src, E = Dst; + /// Scan all of the instruction from SRC to DST and check if + /// the source may alias. + for (++I; I != E; ++I) { + // Ignore store instructions that are marked as 'ignore'. + if (MemBarrierIgnoreList.count(I)) + continue; + if (Src->mayWriteToMemory()) /* Write */ { + if (!I->mayReadOrWriteMemory()) + continue; + } else /* Read */ { + if (!I->mayWriteToMemory()) + continue; + } + AliasAnalysis::Location A = getLocation(&*I); + AliasAnalysis::Location B = getLocation(Src); + + if (!A.Ptr || !B.Ptr || AA->alias(A, B)) + return I; + } + return 0; +} + +int BoUpSLP::getLastIndex(ArrayRef<Value *> VL) { + BasicBlock *BB = cast<Instruction>(VL[0])->getParent(); + assert(BB == getSameBlock(VL) && BlocksNumbers.count(BB) && "Invalid block"); + BlockNumbering &BN = BlocksNumbers[BB]; + + int MaxIdx = BN.getIndex(BB->getFirstNonPHI()); + for (unsigned i = 0, e = VL.size(); i < e; ++i) + MaxIdx = std::max(MaxIdx, BN.getIndex(cast<Instruction>(VL[i]))); + return MaxIdx; +} + +Instruction *BoUpSLP::getLastInstruction(ArrayRef<Value *> VL) { + BasicBlock *BB = cast<Instruction>(VL[0])->getParent(); + assert(BB == getSameBlock(VL) && BlocksNumbers.count(BB) && "Invalid block"); + BlockNumbering &BN = BlocksNumbers[BB]; + + int MaxIdx = BN.getIndex(cast<Instruction>(VL[0])); + for (unsigned i = 1, e = VL.size(); i < e; ++i) + MaxIdx = std::max(MaxIdx, BN.getIndex(cast<Instruction>(VL[i]))); + Instruction *I = BN.getInstruction(MaxIdx); + assert(I && "bad location"); + return I; +} + +void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) { + Instruction *VL0 = cast<Instruction>(VL[0]); + Instruction *LastInst = getLastInstruction(VL); + BasicBlock::iterator NextInst = LastInst; + ++NextInst; + Builder.SetInsertPoint(VL0->getParent(), NextInst); + Builder.SetCurrentDebugLocation(VL0->getDebugLoc()); +} + +Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) { + Value *Vec = UndefValue::get(Ty); + // Generate the 'InsertElement' instruction. + for (unsigned i = 0; i < Ty->getNumElements(); ++i) { + Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i)); + if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) { + GatherSeq.insert(Insrt); + CSEBlocks.insert(Insrt->getParent()); + + // Add to our 'need-to-extract' list. + if (ScalarToTreeEntry.count(VL[i])) { + int Idx = ScalarToTreeEntry[VL[i]]; + TreeEntry *E = &VectorizableTree[Idx]; + // Find which lane we need to extract. + int FoundLane = -1; + for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) { + // Is this the lane of the scalar that we are looking for ? + if (E->Scalars[Lane] == VL[i]) { + FoundLane = Lane; + break; + } + } + assert(FoundLane >= 0 && "Could not find the correct lane"); + ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane)); + } + } + } + + return Vec; +} + +Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const { + SmallDenseMap<Value*, int>::const_iterator Entry + = ScalarToTreeEntry.find(VL[0]); + if (Entry != ScalarToTreeEntry.end()) { + int Idx = Entry->second; + const TreeEntry *En = &VectorizableTree[Idx]; + if (En->isSame(VL) && En->VectorizedValue) + return En->VectorizedValue; + } + return 0; +} + +Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) { + if (ScalarToTreeEntry.count(VL[0])) { + int Idx = ScalarToTreeEntry[VL[0]]; + TreeEntry *E = &VectorizableTree[Idx]; + if (E->isSame(VL)) + return vectorizeTree(E); + } + + Type *ScalarTy = VL[0]->getType(); + if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) + ScalarTy = SI->getValueOperand()->getType(); + VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); + + return Gather(VL, VecTy); +} + +Value *BoUpSLP::vectorizeTree(TreeEntry *E) { + IRBuilder<>::InsertPointGuard Guard(Builder); + + if (E->VectorizedValue) { + DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n"); + return E->VectorizedValue; + } + + Instruction *VL0 = cast<Instruction>(E->Scalars[0]); + Type *ScalarTy = VL0->getType(); + if (StoreInst *SI = dyn_cast<StoreInst>(VL0)) + ScalarTy = SI->getValueOperand()->getType(); + VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size()); + + if (E->NeedToGather) { + setInsertPointAfterBundle(E->Scalars); + return Gather(E->Scalars, VecTy); + } + + unsigned Opcode = VL0->getOpcode(); + assert(Opcode == getSameOpcode(E->Scalars) && "Invalid opcode"); + + switch (Opcode) { + case Instruction::PHI: { + PHINode *PH = dyn_cast<PHINode>(VL0); + Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI()); + Builder.SetCurrentDebugLocation(PH->getDebugLoc()); + PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues()); + E->VectorizedValue = NewPhi; + + // PHINodes may have multiple entries from the same block. We want to + // visit every block once. + SmallSet<BasicBlock*, 4> VisitedBBs; + + for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) { + ValueList Operands; + BasicBlock *IBB = PH->getIncomingBlock(i); + + if (!VisitedBBs.insert(IBB)) { + NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB); + continue; + } + + // Prepare the operand vector. + for (unsigned j = 0; j < E->Scalars.size(); ++j) + Operands.push_back(cast<PHINode>(E->Scalars[j])-> + getIncomingValueForBlock(IBB)); + + Builder.SetInsertPoint(IBB->getTerminator()); + Builder.SetCurrentDebugLocation(PH->getDebugLoc()); + Value *Vec = vectorizeTree(Operands); + NewPhi->addIncoming(Vec, IBB); + } + + assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() && + "Invalid number of incoming values"); + return NewPhi; + } + + case Instruction::ExtractElement: { + if (CanReuseExtract(E->Scalars)) { + Value *V = VL0->getOperand(0); + E->VectorizedValue = V; + return V; + } + return Gather(E->Scalars, VecTy); + } + case Instruction::ZExt: + case Instruction::SExt: + case Instruction::FPToUI: + case Instruction::FPToSI: + case Instruction::FPExt: + case Instruction::PtrToInt: + case Instruction::IntToPtr: + case Instruction::SIToFP: + case Instruction::UIToFP: + case Instruction::Trunc: + case Instruction::FPTrunc: + case Instruction::BitCast: { + ValueList INVL; + for (int i = 0, e = E->Scalars.size(); i < e; ++i) + INVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0)); + + setInsertPointAfterBundle(E->Scalars); + + Value *InVec = vectorizeTree(INVL); + + if (Value *V = alreadyVectorized(E->Scalars)) + return V; + + CastInst *CI = dyn_cast<CastInst>(VL0); + Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy); + E->VectorizedValue = V; + return V; + } + case Instruction::FCmp: + case Instruction::ICmp: { + ValueList LHSV, RHSV; + for (int i = 0, e = E->Scalars.size(); i < e; ++i) { + LHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0)); + RHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1)); + } + + setInsertPointAfterBundle(E->Scalars); + + Value *L = vectorizeTree(LHSV); + Value *R = vectorizeTree(RHSV); + + if (Value *V = alreadyVectorized(E->Scalars)) + return V; + + CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate(); + Value *V; + if (Opcode == Instruction::FCmp) + V = Builder.CreateFCmp(P0, L, R); + else + V = Builder.CreateICmp(P0, L, R); + + E->VectorizedValue = V; + return V; + } + case Instruction::Select: { + ValueList TrueVec, FalseVec, CondVec; + for (int i = 0, e = E->Scalars.size(); i < e; ++i) { + CondVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0)); + TrueVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1)); + FalseVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(2)); + } + + setInsertPointAfterBundle(E->Scalars); + + Value *Cond = vectorizeTree(CondVec); + Value *True = vectorizeTree(TrueVec); + Value *False = vectorizeTree(FalseVec); + + if (Value *V = alreadyVectorized(E->Scalars)) + return V; + + Value *V = Builder.CreateSelect(Cond, True, False); + E->VectorizedValue = V; + return V; + } + 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: { + ValueList LHSVL, RHSVL; + if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) + reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL); + else + for (int i = 0, e = E->Scalars.size(); i < e; ++i) { + LHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0)); + RHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1)); + } + + setInsertPointAfterBundle(E->Scalars); + + Value *LHS = vectorizeTree(LHSVL); + Value *RHS = vectorizeTree(RHSVL); + + if (LHS == RHS && isa<Instruction>(LHS)) { + assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order"); + } + + if (Value *V = alreadyVectorized(E->Scalars)) + return V; + + BinaryOperator *BinOp = cast<BinaryOperator>(VL0); + Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS); + E->VectorizedValue = V; + + if (Instruction *I = dyn_cast<Instruction>(V)) + return propagateMetadata(I, E->Scalars); + + return V; + } + case Instruction::Load: { + // Loads are inserted at the head of the tree because we don't want to + // sink them all the way down past store instructions. + setInsertPointAfterBundle(E->Scalars); + + LoadInst *LI = cast<LoadInst>(VL0); + unsigned AS = LI->getPointerAddressSpace(); + + Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(), + VecTy->getPointerTo(AS)); + unsigned Alignment = LI->getAlignment(); + LI = Builder.CreateLoad(VecPtr); + LI->setAlignment(Alignment); + E->VectorizedValue = LI; + return propagateMetadata(LI, E->Scalars); + } + case Instruction::Store: { + StoreInst *SI = cast<StoreInst>(VL0); + unsigned Alignment = SI->getAlignment(); + unsigned AS = SI->getPointerAddressSpace(); + + ValueList ValueOp; + for (int i = 0, e = E->Scalars.size(); i < e; ++i) + ValueOp.push_back(cast<StoreInst>(E->Scalars[i])->getValueOperand()); + + setInsertPointAfterBundle(E->Scalars); + + Value *VecValue = vectorizeTree(ValueOp); + Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(), + VecTy->getPointerTo(AS)); + StoreInst *S = Builder.CreateStore(VecValue, VecPtr); + S->setAlignment(Alignment); + E->VectorizedValue = S; + return propagateMetadata(S, E->Scalars); + } + default: + llvm_unreachable("unknown inst"); + } + return 0; +} + +Value *BoUpSLP::vectorizeTree() { + Builder.SetInsertPoint(F->getEntryBlock().begin()); + vectorizeTree(&VectorizableTree[0]); + + DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n"); + + // Extract all of the elements with the external uses. + for (UserList::iterator it = ExternalUses.begin(), e = ExternalUses.end(); + it != e; ++it) { + Value *Scalar = it->Scalar; + llvm::User *User = it->User; + + // Skip users that we already RAUW. This happens when one instruction + // has multiple uses of the same value. + if (std::find(Scalar->use_begin(), Scalar->use_end(), User) == + Scalar->use_end()) + continue; + assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar"); + + int Idx = ScalarToTreeEntry[Scalar]; + TreeEntry *E = &VectorizableTree[Idx]; + assert(!E->NeedToGather && "Extracting from a gather list"); + + Value *Vec = E->VectorizedValue; + assert(Vec && "Can't find vectorizable value"); + + Value *Lane = Builder.getInt32(it->Lane); + // Generate extracts for out-of-tree users. + // Find the insertion point for the extractelement lane. + if (PHINode *PN = dyn_cast<PHINode>(Vec)) { + Builder.SetInsertPoint(PN->getParent()->getFirstInsertionPt()); + Value *Ex = Builder.CreateExtractElement(Vec, Lane); + CSEBlocks.insert(PN->getParent()); + User->replaceUsesOfWith(Scalar, Ex); + } else if (isa<Instruction>(Vec)){ + if (PHINode *PH = dyn_cast<PHINode>(User)) { + for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) { + if (PH->getIncomingValue(i) == Scalar) { + Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator()); + Value *Ex = Builder.CreateExtractElement(Vec, Lane); + CSEBlocks.insert(PH->getIncomingBlock(i)); + PH->setOperand(i, Ex); + } + } + } else { + Builder.SetInsertPoint(cast<Instruction>(User)); + Value *Ex = Builder.CreateExtractElement(Vec, Lane); + CSEBlocks.insert(cast<Instruction>(User)->getParent()); + User->replaceUsesOfWith(Scalar, Ex); + } + } else { + Builder.SetInsertPoint(F->getEntryBlock().begin()); + Value *Ex = Builder.CreateExtractElement(Vec, Lane); + CSEBlocks.insert(&F->getEntryBlock()); + User->replaceUsesOfWith(Scalar, Ex); + } + + DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n"); + } + + // For each vectorized value: + for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) { + TreeEntry *Entry = &VectorizableTree[EIdx]; + + // For each lane: + for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) { + Value *Scalar = Entry->Scalars[Lane]; + + // No need to handle users of gathered values. + if (Entry->NeedToGather) + continue; + + assert(Entry->VectorizedValue && "Can't find vectorizable value"); + + Type *Ty = Scalar->getType(); + if (!Ty->isVoidTy()) { + for (Value::use_iterator User = Scalar->use_begin(), + UE = Scalar->use_end(); User != UE; ++User) { + DEBUG(dbgs() << "SLP: \tvalidating user:" << **User << ".\n"); + + assert((ScalarToTreeEntry.count(*User) || + // It is legal to replace the reduction users by undef. + (RdxOps && RdxOps->count(*User))) && + "Replacing out-of-tree value with undef"); + } + Value *Undef = UndefValue::get(Ty); + Scalar->replaceAllUsesWith(Undef); + } + DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n"); + cast<Instruction>(Scalar)->eraseFromParent(); + } + } + + for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it) { + BlocksNumbers[it].forget(); + } + Builder.ClearInsertionPoint(); + + return VectorizableTree[0].VectorizedValue; +} + +class DTCmp { + const DominatorTree *DT; + +public: + DTCmp(const DominatorTree *DT) : DT(DT) {} + bool operator()(const BasicBlock *A, const BasicBlock *B) const { + return DT->properlyDominates(A, B); + } +}; + +void BoUpSLP::optimizeGatherSequence() { + DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size() + << " gather sequences instructions.\n"); + // LICM InsertElementInst sequences. + for (SetVector<Instruction *>::iterator it = GatherSeq.begin(), + e = GatherSeq.end(); it != e; ++it) { + InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it); + + if (!Insert) + continue; + + // Check if this block is inside a loop. + Loop *L = LI->getLoopFor(Insert->getParent()); + if (!L) + continue; + + // Check if it has a preheader. + BasicBlock *PreHeader = L->getLoopPreheader(); + if (!PreHeader) + continue; + + // If the vector or the element that we insert into it are + // instructions that are defined in this basic block then we can't + // hoist this instruction. + Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0)); + Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1)); + if (CurrVec && L->contains(CurrVec)) + continue; + if (NewElem && L->contains(NewElem)) + continue; + + // We can hoist this instruction. Move it to the pre-header. + Insert->moveBefore(PreHeader->getTerminator()); + } + + // Sort blocks by domination. This ensures we visit a block after all blocks + // dominating it are visited. + SmallVector<BasicBlock *, 8> CSEWorkList(CSEBlocks.begin(), CSEBlocks.end()); + std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(), DTCmp(DT)); + + // Perform O(N^2) search over the gather sequences and merge identical + // instructions. TODO: We can further optimize this scan if we split the + // instructions into different buckets based on the insert lane. + SmallVector<Instruction *, 16> Visited; + for (SmallVectorImpl<BasicBlock *>::iterator I = CSEWorkList.begin(), + E = CSEWorkList.end(); + I != E; ++I) { + assert((I == CSEWorkList.begin() || !DT->dominates(*I, *llvm::prior(I))) && + "Worklist not sorted properly!"); + BasicBlock *BB = *I; + // For all instructions in blocks containing gather sequences: + for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) { + Instruction *In = it++; + if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In)) + continue; + + // Check if we can replace this instruction with any of the + // visited instructions. + for (SmallVectorImpl<Instruction *>::iterator v = Visited.begin(), + ve = Visited.end(); + v != ve; ++v) { + if (In->isIdenticalTo(*v) && + DT->dominates((*v)->getParent(), In->getParent())) { + In->replaceAllUsesWith(*v); + In->eraseFromParent(); + In = 0; + break; + } + } + if (In) { + assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end()); + Visited.push_back(In); + } + } + } + CSEBlocks.clear(); + GatherSeq.clear(); +} + /// The SLPVectorizer Pass. struct SLPVectorizer : public FunctionPass { - typedef std::map<Value*, BoUpSLP::StoreList> StoreListMap; + typedef SmallVector<StoreInst *, 8> StoreList; + typedef MapVector<Value *, StoreList> StoreListMap; /// Pass identification, replacement for typeid static char ID; @@ -61,6 +1764,7 @@ struct SLPVectorizer : public FunctionPass { TargetTransformInfo *TTI; AliasAnalysis *AA; LoopInfo *LI; + DominatorTree *DT; virtual bool runOnFunction(Function &F) { SE = &getAnalysis<ScalarEvolution>(); @@ -68,41 +1772,50 @@ struct SLPVectorizer : public FunctionPass { TTI = &getAnalysis<TargetTransformInfo>(); AA = &getAnalysis<AliasAnalysis>(); LI = &getAnalysis<LoopInfo>(); + DT = &getAnalysis<DominatorTree>(); StoreRefs.clear(); bool Changed = false; + // If the target claims to have no vector registers don't attempt + // vectorization. + if (!TTI->getNumberOfRegisters(true)) + return false; + // Must have DataLayout. We can't require it because some tests run w/o // triple. if (!DL) return false; - for (Function::iterator it = F.begin(), e = F.end(); it != e; ++it) { - BasicBlock *BB = it; - bool BBChanged = false; + // Don't vectorize when the attribute NoImplicitFloat is used. + if (F.hasFnAttribute(Attribute::NoImplicitFloat)) + return false; - // Use the bollom up slp vectorizer to construct chains that start with - // he store instructions. - BoUpSLP R(BB, SE, DL, TTI, AA, LI->getLoopFor(BB)); + DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n"); - // Vectorize trees that end at reductions. - BBChanged |= vectorizeReductions(BB, R); + // Use the bollom up slp vectorizer to construct chains that start with + // he store instructions. + BoUpSLP R(&F, SE, DL, TTI, AA, LI, DT); + + // Scan the blocks in the function in post order. + for (po_iterator<BasicBlock*> it = po_begin(&F.getEntryBlock()), + e = po_end(&F.getEntryBlock()); it != e; ++it) { + BasicBlock *BB = *it; // Vectorize trees that end at stores. if (unsigned count = collectStores(BB, R)) { (void)count; - DEBUG(dbgs()<<"SLP: Found " << count << " stores to vectorize.\n"); - BBChanged |= vectorizeStoreChains(R); + DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n"); + Changed |= vectorizeStoreChains(R); } - // Try to hoist some of the scalarization code to the preheader. - if (BBChanged) hoistGatherSequence(LI, BB, R); - - Changed |= BBChanged; + // Vectorize trees that end at reductions. + Changed |= vectorizeChainsInBlock(BB, R); } if (Changed) { - DEBUG(dbgs()<<"SLP: vectorized \""<<F.getName()<<"\"\n"); + R.optimizeGatherSequence(); + DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n"); DEBUG(verifyFunction(F)); } return Changed; @@ -114,6 +1827,10 @@ struct SLPVectorizer : public FunctionPass { AU.addRequired<AliasAnalysis>(); AU.addRequired<TargetTransformInfo>(); AU.addRequired<LoopInfo>(); + AU.addRequired<DominatorTree>(); + AU.addPreserved<LoopInfo>(); + AU.addPreserved<DominatorTree>(); + AU.setPreservesCFG(); } private: @@ -125,29 +1842,149 @@ private: unsigned collectStores(BasicBlock *BB, BoUpSLP &R); /// \brief Try to vectorize a chain that starts at two arithmetic instrs. - bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R); + bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R); /// \brief Try to vectorize a list of operands. + /// \returns true if a value was vectorized. bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R); /// \brief Try to vectorize a chain that may start at the operands of \V; - bool tryToVectorize(BinaryOperator *V, BoUpSLP &R); + bool tryToVectorize(BinaryOperator *V, BoUpSLP &R); /// \brief Vectorize the stores that were collected in StoreRefs. bool vectorizeStoreChains(BoUpSLP &R); - /// \brief Try to hoist gather sequences outside of the loop in cases where - /// all of the sources are loop invariant. - void hoistGatherSequence(LoopInfo *LI, BasicBlock *BB, BoUpSLP &R); + /// \brief Scan the basic block and look for patterns that are likely to start + /// a vectorization chain. + bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R); - /// \brief Scan the basic block and look for reductions that may start a - /// vectorization chain. - bool vectorizeReductions(BasicBlock *BB, BoUpSLP &R); + bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold, + BoUpSLP &R); + bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold, + BoUpSLP &R); private: StoreListMap StoreRefs; }; +/// \brief Check that the Values in the slice in VL array are still existant in +/// the WeakVH array. +/// Vectorization of part of the VL array may cause later values in the VL array +/// to become invalid. We track when this has happened in the WeakVH array. +static bool hasValueBeenRAUWed(ArrayRef<Value *> &VL, + SmallVectorImpl<WeakVH> &VH, + unsigned SliceBegin, + unsigned SliceSize) { + for (unsigned i = SliceBegin; i < SliceBegin + SliceSize; ++i) + if (VH[i] != VL[i]) + return true; + + return false; +} + +bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain, + int CostThreshold, BoUpSLP &R) { + unsigned ChainLen = Chain.size(); + DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen + << "\n"); + Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType(); + unsigned Sz = DL->getTypeSizeInBits(StoreTy); + unsigned VF = MinVecRegSize / Sz; + + if (!isPowerOf2_32(Sz) || VF < 2) + return false; + + // Keep track of values that were delete by vectorizing in the loop below. + SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end()); + + bool Changed = false; + // Look for profitable vectorizable trees at all offsets, starting at zero. + for (unsigned i = 0, e = ChainLen; i < e; ++i) { + if (i + VF > e) + break; + + // Check that a previous iteration of this loop did not delete the Value. + if (hasValueBeenRAUWed(Chain, TrackValues, i, VF)) + continue; + + DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i + << "\n"); + ArrayRef<Value *> Operands = Chain.slice(i, VF); + + R.buildTree(Operands); + + int Cost = R.getTreeCost(); + + DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n"); + if (Cost < CostThreshold) { + DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n"); + R.vectorizeTree(); + + // Move to the next bundle. + i += VF - 1; + Changed = true; + } + } + + return Changed; +} + +bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores, + int costThreshold, BoUpSLP &R) { + SetVector<Value *> Heads, Tails; + SmallDenseMap<Value *, Value *> ConsecutiveChain; + + // We may run into multiple chains that merge into a single chain. We mark the + // stores that we vectorized so that we don't visit the same store twice. + BoUpSLP::ValueSet VectorizedStores; + bool Changed = false; + + // Do a quadratic search on all of the given stores and find + // all of the pairs of stores that follow each other. + for (unsigned i = 0, e = Stores.size(); i < e; ++i) { + for (unsigned j = 0; j < e; ++j) { + if (i == j) + continue; + + if (R.isConsecutiveAccess(Stores[i], Stores[j])) { + Tails.insert(Stores[j]); + Heads.insert(Stores[i]); + ConsecutiveChain[Stores[i]] = Stores[j]; + } + } + } + + // For stores that start but don't end a link in the chain: + for (SetVector<Value *>::iterator it = Heads.begin(), e = Heads.end(); + it != e; ++it) { + if (Tails.count(*it)) + continue; + + // We found a store instr that starts a chain. Now follow the chain and try + // to vectorize it. + BoUpSLP::ValueList Operands; + Value *I = *it; + // Collect the chain into a list. + while (Tails.count(I) || Heads.count(I)) { + if (VectorizedStores.count(I)) + break; + Operands.push_back(I); + // Move to the next value in the chain. + I = ConsecutiveChain[I]; + } + + bool Vectorized = vectorizeStoreChain(Operands, costThreshold, R); + + // Mark the vectorized stores so that we don't vectorize them again. + if (Vectorized) + VectorizedStores.insert(Operands.begin(), Operands.end()); + Changed |= Vectorized; + } + + return Changed; +} + + unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) { unsigned count = 0; StoreRefs.clear(); @@ -156,15 +1993,17 @@ unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) { if (!SI) continue; + // Don't touch volatile stores. + if (!SI->isSimple()) + continue; + // Check that the pointer points to scalars. Type *Ty = SI->getValueOperand()->getType(); if (Ty->isAggregateType() || Ty->isVectorTy()) return 0; - // Find the base of the GEP. - Value *Ptr = SI->getPointerOperand(); - if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) - Ptr = GEP->getPointerOperand(); + // Find the base pointer. + Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), DL); // Save the store locations. StoreRefs[Ptr].push_back(SI); @@ -173,34 +2012,83 @@ unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) { return count; } -bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) { - if (!A || !B) return false; +bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) { + if (!A || !B) + return false; Value *VL[] = { A, B }; return tryToVectorizeList(VL, R); } bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R) { - DEBUG(dbgs()<<"SLP: Vectorizing a list of length = " << VL.size() << ".\n"); + if (VL.size() < 2) + return false; + + DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n"); + + // Check that all of the parts are scalar instructions of the same type. + Instruction *I0 = dyn_cast<Instruction>(VL[0]); + if (!I0) + return false; + + unsigned Opcode0 = I0->getOpcode(); + + Type *Ty0 = I0->getType(); + unsigned Sz = DL->getTypeSizeInBits(Ty0); + unsigned VF = MinVecRegSize / Sz; - // Check that all of the parts are scalar. for (int i = 0, e = VL.size(); i < e; ++i) { Type *Ty = VL[i]->getType(); if (Ty->isAggregateType() || Ty->isVectorTy()) - return 0; + return false; + Instruction *Inst = dyn_cast<Instruction>(VL[i]); + if (!Inst || Inst->getOpcode() != Opcode0) + return false; } - int Cost = R.getTreeCost(VL); - int ExtrCost = R.getScalarizationCost(VL); - DEBUG(dbgs()<<"SLP: Cost of pair:" << Cost << - " Cost of extract:" << ExtrCost << ".\n"); - if ((Cost+ExtrCost) >= -SLPCostThreshold) return false; - DEBUG(dbgs()<<"SLP: Vectorizing pair.\n"); - R.vectorizeArith(VL); - return true; + bool Changed = false; + + // Keep track of values that were delete by vectorizing in the loop below. + SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end()); + + for (unsigned i = 0, e = VL.size(); i < e; ++i) { + unsigned OpsWidth = 0; + + if (i + VF > e) + OpsWidth = e - i; + else + OpsWidth = VF; + + if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2) + break; + + // Check that a previous iteration of this loop did not delete the Value. + if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth)) + continue; + + DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations " + << "\n"); + ArrayRef<Value *> Ops = VL.slice(i, OpsWidth); + + R.buildTree(Ops); + int Cost = R.getTreeCost(); + + if (Cost < -SLPCostThreshold) { + DEBUG(dbgs() << "SLP: Vectorizing pair at cost:" << Cost << ".\n"); + R.vectorizeTree(); + + // Move to the next bundle. + i += VF - 1; + Changed = true; + } + } + + return Changed; } -bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) { - if (!V) return false; +bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) { + if (!V) + return false; + // Try to vectorize V. if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R)) return true; @@ -237,38 +2125,502 @@ bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) { return 0; } -bool SLPVectorizer::vectorizeReductions(BasicBlock *BB, BoUpSLP &R) { +/// \brief Generate a shuffle mask to be used in a reduction tree. +/// +/// \param VecLen The length of the vector to be reduced. +/// \param NumEltsToRdx The number of elements that should be reduced in the +/// vector. +/// \param IsPairwise Whether the reduction is a pairwise or splitting +/// reduction. A pairwise reduction will generate a mask of +/// <0,2,...> or <1,3,..> while a splitting reduction will generate +/// <2,3, undef,undef> for a vector of 4 and NumElts = 2. +/// \param IsLeft True will generate a mask of even elements, odd otherwise. +static Value *createRdxShuffleMask(unsigned VecLen, unsigned NumEltsToRdx, + bool IsPairwise, bool IsLeft, + IRBuilder<> &Builder) { + assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask"); + + SmallVector<Constant *, 32> ShuffleMask( + VecLen, UndefValue::get(Builder.getInt32Ty())); + + if (IsPairwise) + // Build a mask of 0, 2, ... (left) or 1, 3, ... (right). + for (unsigned i = 0; i != NumEltsToRdx; ++i) + ShuffleMask[i] = Builder.getInt32(2 * i + !IsLeft); + else + // Move the upper half of the vector to the lower half. + for (unsigned i = 0; i != NumEltsToRdx; ++i) + ShuffleMask[i] = Builder.getInt32(NumEltsToRdx + i); + + return ConstantVector::get(ShuffleMask); +} + + +/// Model horizontal reductions. +/// +/// A horizontal reduction is a tree of reduction operations (currently add and +/// fadd) that has operations that can be put into a vector as its leaf. +/// For example, this tree: +/// +/// mul mul mul mul +/// \ / \ / +/// + + +/// \ / +/// + +/// This tree has "mul" as its reduced values and "+" as its reduction +/// operations. A reduction might be feeding into a store or a binary operation +/// feeding a phi. +/// ... +/// \ / +/// + +/// | +/// phi += +/// +/// Or: +/// ... +/// \ / +/// + +/// | +/// *p = +/// +class HorizontalReduction { + SmallPtrSet<Value *, 16> ReductionOps; + SmallVector<Value *, 32> ReducedVals; + + BinaryOperator *ReductionRoot; + PHINode *ReductionPHI; + + /// The opcode of the reduction. + unsigned ReductionOpcode; + /// The opcode of the values we perform a reduction on. + unsigned ReducedValueOpcode; + /// The width of one full horizontal reduction operation. + unsigned ReduxWidth; + /// Should we model this reduction as a pairwise reduction tree or a tree that + /// splits the vector in halves and adds those halves. + bool IsPairwiseReduction; + +public: + HorizontalReduction() + : ReductionRoot(0), ReductionPHI(0), ReductionOpcode(0), + ReducedValueOpcode(0), ReduxWidth(0), IsPairwiseReduction(false) {} + + /// \brief Try to find a reduction tree. + bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B, + DataLayout *DL) { + assert((!Phi || + std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) && + "Thi phi needs to use the binary operator"); + + // We could have a initial reductions that is not an add. + // r *= v1 + v2 + v3 + v4 + // In such a case start looking for a tree rooted in the first '+'. + if (Phi) { + if (B->getOperand(0) == Phi) { + Phi = 0; + B = dyn_cast<BinaryOperator>(B->getOperand(1)); + } else if (B->getOperand(1) == Phi) { + Phi = 0; + B = dyn_cast<BinaryOperator>(B->getOperand(0)); + } + } + + if (!B) + return false; + + Type *Ty = B->getType(); + if (Ty->isVectorTy()) + return false; + + ReductionOpcode = B->getOpcode(); + ReducedValueOpcode = 0; + ReduxWidth = MinVecRegSize / DL->getTypeSizeInBits(Ty); + ReductionRoot = B; + ReductionPHI = Phi; + + if (ReduxWidth < 4) + return false; + + // We currently only support adds. + if (ReductionOpcode != Instruction::Add && + ReductionOpcode != Instruction::FAdd) + return false; + + // Post order traverse the reduction tree starting at B. We only handle true + // trees containing only binary operators. + SmallVector<std::pair<BinaryOperator *, unsigned>, 32> Stack; + Stack.push_back(std::make_pair(B, 0)); + while (!Stack.empty()) { + BinaryOperator *TreeN = Stack.back().first; + unsigned EdgeToVist = Stack.back().second++; + bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode; + + // Only handle trees in the current basic block. + if (TreeN->getParent() != B->getParent()) + return false; + + // Each tree node needs to have one user except for the ultimate + // reduction. + if (!TreeN->hasOneUse() && TreeN != B) + return false; + + // Postorder vist. + if (EdgeToVist == 2 || IsReducedValue) { + if (IsReducedValue) { + // Make sure that the opcodes of the operations that we are going to + // reduce match. + if (!ReducedValueOpcode) + ReducedValueOpcode = TreeN->getOpcode(); + else if (ReducedValueOpcode != TreeN->getOpcode()) + return false; + ReducedVals.push_back(TreeN); + } else { + // We need to be able to reassociate the adds. + if (!TreeN->isAssociative()) + return false; + ReductionOps.insert(TreeN); + } + // Retract. + Stack.pop_back(); + continue; + } + + // Visit left or right. + Value *NextV = TreeN->getOperand(EdgeToVist); + BinaryOperator *Next = dyn_cast<BinaryOperator>(NextV); + if (Next) + Stack.push_back(std::make_pair(Next, 0)); + else if (NextV != Phi) + return false; + } + return true; + } + + /// \brief Attempt to vectorize the tree found by + /// matchAssociativeReduction. + bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) { + if (ReducedVals.empty()) + return false; + + unsigned NumReducedVals = ReducedVals.size(); + if (NumReducedVals < ReduxWidth) + return false; + + Value *VectorizedTree = 0; + IRBuilder<> Builder(ReductionRoot); + FastMathFlags Unsafe; + Unsafe.setUnsafeAlgebra(); + Builder.SetFastMathFlags(Unsafe); + unsigned i = 0; + + for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) { + ArrayRef<Value *> ValsToReduce(&ReducedVals[i], ReduxWidth); + V.buildTree(ValsToReduce, &ReductionOps); + + // Estimate cost. + int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]); + if (Cost >= -SLPCostThreshold) + break; + + DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost + << ". (HorRdx)\n"); + + // Vectorize a tree. + DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc(); + Value *VectorizedRoot = V.vectorizeTree(); + + // Emit a reduction. + Value *ReducedSubTree = emitReduction(VectorizedRoot, Builder); + if (VectorizedTree) { + Builder.SetCurrentDebugLocation(Loc); + VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree, + ReducedSubTree, "bin.rdx"); + } else + VectorizedTree = ReducedSubTree; + } + + if (VectorizedTree) { + // Finish the reduction. + for (; i < NumReducedVals; ++i) { + Builder.SetCurrentDebugLocation( + cast<Instruction>(ReducedVals[i])->getDebugLoc()); + VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree, + ReducedVals[i]); + } + // Update users. + if (ReductionPHI) { + assert(ReductionRoot != NULL && "Need a reduction operation"); + ReductionRoot->setOperand(0, VectorizedTree); + ReductionRoot->setOperand(1, ReductionPHI); + } else + ReductionRoot->replaceAllUsesWith(VectorizedTree); + } + return VectorizedTree != 0; + } + +private: + + /// \brief Calcuate the cost of a reduction. + int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) { + Type *ScalarTy = FirstReducedVal->getType(); + Type *VecTy = VectorType::get(ScalarTy, ReduxWidth); + + int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true); + int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false); + + IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost; + int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost; + + int ScalarReduxCost = + ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy); + + DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost + << " for reduction that starts with " << *FirstReducedVal + << " (It is a " + << (IsPairwiseReduction ? "pairwise" : "splitting") + << " reduction)\n"); + + return VecReduxCost - ScalarReduxCost; + } + + static Value *createBinOp(IRBuilder<> &Builder, unsigned Opcode, Value *L, + Value *R, const Twine &Name = "") { + if (Opcode == Instruction::FAdd) + return Builder.CreateFAdd(L, R, Name); + return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name); + } + + /// \brief Emit a horizontal reduction of the vectorized value. + Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder) { + assert(VectorizedValue && "Need to have a vectorized tree node"); + Instruction *ValToReduce = dyn_cast<Instruction>(VectorizedValue); + assert(isPowerOf2_32(ReduxWidth) && + "We only handle power-of-two reductions for now"); + + Value *TmpVec = ValToReduce; + for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) { + if (IsPairwiseReduction) { + Value *LeftMask = + createRdxShuffleMask(ReduxWidth, i, true, true, Builder); + Value *RightMask = + createRdxShuffleMask(ReduxWidth, i, true, false, Builder); + + Value *LeftShuf = Builder.CreateShuffleVector( + TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l"); + Value *RightShuf = Builder.CreateShuffleVector( + TmpVec, UndefValue::get(TmpVec->getType()), (RightMask), + "rdx.shuf.r"); + TmpVec = createBinOp(Builder, ReductionOpcode, LeftShuf, RightShuf, + "bin.rdx"); + } else { + Value *UpperHalf = + createRdxShuffleMask(ReduxWidth, i, false, false, Builder); + Value *Shuf = Builder.CreateShuffleVector( + TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf"); + TmpVec = createBinOp(Builder, ReductionOpcode, TmpVec, Shuf, "bin.rdx"); + } + } + + // The result is in the first element of the vector. + return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0)); + } +}; + +/// \brief Recognize construction of vectors like +/// %ra = insertelement <4 x float> undef, float %s0, i32 0 +/// %rb = insertelement <4 x float> %ra, float %s1, i32 1 +/// %rc = insertelement <4 x float> %rb, float %s2, i32 2 +/// %rd = insertelement <4 x float> %rc, float %s3, i32 3 +/// +/// Returns true if it matches +/// +static bool findBuildVector(InsertElementInst *IE, + SmallVectorImpl<Value *> &Ops) { + if (!isa<UndefValue>(IE->getOperand(0))) + return false; + + while (true) { + Ops.push_back(IE->getOperand(1)); + + if (IE->use_empty()) + return false; + + InsertElementInst *NextUse = dyn_cast<InsertElementInst>(IE->use_back()); + if (!NextUse) + return true; + + // If this isn't the final use, make sure the next insertelement is the only + // use. It's OK if the final constructed vector is used multiple times + if (!IE->hasOneUse()) + return false; + + IE = NextUse; + } + + return false; +} + +static bool PhiTypeSorterFunc(Value *V, Value *V2) { + return V->getType() < V2->getType(); +} + +bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) { bool Changed = false; - for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) { - if (isa<DbgInfoIntrinsic>(it)) continue; + SmallVector<Value *, 4> Incoming; + SmallSet<Value *, 16> VisitedInstrs; + + bool HaveVectorizedPhiNodes = true; + while (HaveVectorizedPhiNodes) { + HaveVectorizedPhiNodes = false; + + // Collect the incoming values from the PHIs. + Incoming.clear(); + for (BasicBlock::iterator instr = BB->begin(), ie = BB->end(); instr != ie; + ++instr) { + PHINode *P = dyn_cast<PHINode>(instr); + if (!P) + break; + + if (!VisitedInstrs.count(P)) + Incoming.push_back(P); + } + + // Sort by type. + std::stable_sort(Incoming.begin(), Incoming.end(), PhiTypeSorterFunc); + + // Try to vectorize elements base on their type. + for (SmallVector<Value *, 4>::iterator IncIt = Incoming.begin(), + E = Incoming.end(); + IncIt != E;) { + + // Look for the next elements with the same type. + SmallVector<Value *, 4>::iterator SameTypeIt = IncIt; + while (SameTypeIt != E && + (*SameTypeIt)->getType() == (*IncIt)->getType()) { + VisitedInstrs.insert(*SameTypeIt); + ++SameTypeIt; + } + + // Try to vectorize them. + unsigned NumElts = (SameTypeIt - IncIt); + DEBUG(errs() << "SLP: Trying to vectorize starting at PHIs (" << NumElts << ")\n"); + if (NumElts > 1 && + tryToVectorizeList(ArrayRef<Value *>(IncIt, NumElts), R)) { + // Success start over because instructions might have been changed. + HaveVectorizedPhiNodes = true; + Changed = true; + break; + } + + // Start over at the next instruction of a differnt type (or the end). + IncIt = SameTypeIt; + } + } + + VisitedInstrs.clear(); + + for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) { + // We may go through BB multiple times so skip the one we have checked. + if (!VisitedInstrs.insert(it)) + continue; + + if (isa<DbgInfoIntrinsic>(it)) + continue; // Try to vectorize reductions that use PHINodes. if (PHINode *P = dyn_cast<PHINode>(it)) { // Check that the PHI is a reduction PHI. - if (P->getNumIncomingValues() != 2) return Changed; - Value *Rdx = (P->getIncomingBlock(0) == BB ? P->getIncomingValue(0) : - (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1) : - 0)); + if (P->getNumIncomingValues() != 2) + return Changed; + Value *Rdx = + (P->getIncomingBlock(0) == BB + ? (P->getIncomingValue(0)) + : (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1) : 0)); // Check if this is a Binary Operator. BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx); if (!BI) continue; - Value *Inst = BI->getOperand(0); - if (Inst == P) Inst = BI->getOperand(1); - Changed |= tryToVectorize(dyn_cast<BinaryOperator>(Inst), R); + // Try to match and vectorize a horizontal reduction. + HorizontalReduction HorRdx; + if (ShouldVectorizeHor && + HorRdx.matchAssociativeReduction(P, BI, DL) && + HorRdx.tryToReduce(R, TTI)) { + Changed = true; + it = BB->begin(); + e = BB->end(); + continue; + } + + Value *Inst = BI->getOperand(0); + if (Inst == P) + Inst = BI->getOperand(1); + + if (tryToVectorize(dyn_cast<BinaryOperator>(Inst), R)) { + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + Changed = true; + it = BB->begin(); + e = BB->end(); + continue; + } + continue; } + // Try to vectorize horizontal reductions feeding into a store. + if (ShouldStartVectorizeHorAtStore) + if (StoreInst *SI = dyn_cast<StoreInst>(it)) + if (BinaryOperator *BinOp = + dyn_cast<BinaryOperator>(SI->getValueOperand())) { + HorizontalReduction HorRdx; + if (((HorRdx.matchAssociativeReduction(0, BinOp, DL) && + HorRdx.tryToReduce(R, TTI)) || + tryToVectorize(BinOp, R))) { + Changed = true; + it = BB->begin(); + e = BB->end(); + continue; + } + } + // Try to vectorize trees that start at compare instructions. if (CmpInst *CI = dyn_cast<CmpInst>(it)) { if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) { - Changed |= true; + Changed = true; + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + it = BB->begin(); + e = BB->end(); continue; } - for (int i = 0; i < 2; ++i) - if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i))) - Changed |= tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R); + + for (int i = 0; i < 2; ++i) { + if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i))) { + if (tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R)) { + Changed = true; + // We would like to start over since some instructions are deleted + // and the iterator may become invalid value. + it = BB->begin(); + e = BB->end(); + } + } + } + continue; + } + + // Try to vectorize trees that start at insertelement instructions. + if (InsertElementInst *IE = dyn_cast<InsertElementInst>(it)) { + SmallVector<Value *, 8> Ops; + if (!findBuildVector(IE, Ops)) + continue; + + if (tryToVectorizeList(Ops, R)) { + Changed = true; + it = BB->begin(); + e = BB->end(); + } + continue; } } @@ -284,51 +2636,19 @@ bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) { if (it->second.size() < 2) continue; - DEBUG(dbgs()<<"SLP: Analyzing a store chain of length " << - it->second.size() << ".\n"); + DEBUG(dbgs() << "SLP: Analyzing a store chain of length " + << it->second.size() << ".\n"); - Changed |= R.vectorizeStores(it->second, -SLPCostThreshold); + // Process the stores in chunks of 16. + for (unsigned CI = 0, CE = it->second.size(); CI < CE; CI+=16) { + unsigned Len = std::min<unsigned>(CE - CI, 16); + ArrayRef<StoreInst *> Chunk(&it->second[CI], Len); + Changed |= vectorizeStores(Chunk, -SLPCostThreshold, R); + } } return Changed; } -void SLPVectorizer::hoistGatherSequence(LoopInfo *LI, BasicBlock *BB, - BoUpSLP &R) { - // Check if this block is inside a loop. - Loop *L = LI->getLoopFor(BB); - if (!L) - return; - - // Check if it has a preheader. - BasicBlock *PreHeader = L->getLoopPreheader(); - if (!PreHeader) - return; - - // Mark the insertion point for the block. - Instruction *Location = PreHeader->getTerminator(); - - BoUpSLP::ValueList &Gathers = R.getGatherSeqInstructions(); - for (BoUpSLP::ValueList::iterator it = Gathers.begin(), e = Gathers.end(); - it != e; ++it) { - InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it); - - // The InsertElement sequence can be simplified into a constant. - if (!Insert) - continue; - - // If the vector or the element that we insert into it are - // instructions that are defined in this basic block then we can't - // hoist this instruction. - Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0)); - Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1)); - if (CurrVec && L->contains(CurrVec)) continue; - if (NewElem && L->contains(NewElem)) continue; - - // We can hoist this instruction. Move it to the pre-header. - Insert->moveBefore(Location); - } -} - } // end anonymous namespace char SLPVectorizer::ID = 0; @@ -341,8 +2661,5 @@ INITIALIZE_PASS_DEPENDENCY(LoopSimplify) INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false) namespace llvm { - Pass *createSLPVectorizerPass() { - return new SLPVectorizer(); - } +Pass *createSLPVectorizerPass() { return new SLPVectorizer(); } } - diff --git a/contrib/llvm/lib/Transforms/Vectorize/VecUtils.cpp b/contrib/llvm/lib/Transforms/Vectorize/VecUtils.cpp deleted file mode 100644 index 9b94366..0000000 --- a/contrib/llvm/lib/Transforms/Vectorize/VecUtils.cpp +++ /dev/null @@ -1,730 +0,0 @@ -//===- VecUtils.cpp --- Vectorization Utilities ---------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -#define DEBUG_TYPE "SLP" - -#include "VecUtils.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/ScalarEvolution.h" -#include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Analysis/TargetTransformInfo.h" -#include "llvm/Analysis/Verifier.h" -#include "llvm/Analysis/LoopInfo.h" -#include "llvm/IR/Constants.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/Function.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/Type.h" -#include "llvm/IR/Value.h" -#include "llvm/Pass.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Debug.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Target/TargetLibraryInfo.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Utils/Local.h" -#include <algorithm> -#include <map> - -using namespace llvm; - -static const unsigned MinVecRegSize = 128; - -static const unsigned RecursionMaxDepth = 6; - -namespace llvm { - -BoUpSLP::BoUpSLP(BasicBlock *Bb, ScalarEvolution *S, DataLayout *Dl, - TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp) : - BB(Bb), SE(S), DL(Dl), TTI(Tti), AA(Aa), L(Lp) { - numberInstructions(); -} - -void BoUpSLP::numberInstructions() { - int Loc = 0; - InstrIdx.clear(); - InstrVec.clear(); - // Number the instructions in the block. - for (BasicBlock::iterator it=BB->begin(), e=BB->end(); it != e; ++it) { - InstrIdx[it] = Loc++; - InstrVec.push_back(it); - assert(InstrVec[InstrIdx[it]] == it && "Invalid allocation"); - } -} - -Value *BoUpSLP::getPointerOperand(Value *I) { - if (LoadInst *LI = dyn_cast<LoadInst>(I)) return LI->getPointerOperand(); - if (StoreInst *SI = dyn_cast<StoreInst>(I)) return SI->getPointerOperand(); - return 0; -} - -unsigned BoUpSLP::getAddressSpaceOperand(Value *I) { - if (LoadInst *L=dyn_cast<LoadInst>(I)) return L->getPointerAddressSpace(); - if (StoreInst *S=dyn_cast<StoreInst>(I)) return S->getPointerAddressSpace(); - return -1; -} - -bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B) { - Value *PtrA = getPointerOperand(A); - Value *PtrB = getPointerOperand(B); - unsigned ASA = getAddressSpaceOperand(A); - unsigned ASB = getAddressSpaceOperand(B); - - // Check that the address spaces match and that the pointers are valid. - if (!PtrA || !PtrB || (ASA != ASB)) return false; - - // Check that A and B are of the same type. - if (PtrA->getType() != PtrB->getType()) return false; - - // Calculate the distance. - const SCEV *PtrSCEVA = SE->getSCEV(PtrA); - const SCEV *PtrSCEVB = SE->getSCEV(PtrB); - const SCEV *OffsetSCEV = SE->getMinusSCEV(PtrSCEVA, PtrSCEVB); - const SCEVConstant *ConstOffSCEV = dyn_cast<SCEVConstant>(OffsetSCEV); - - // Non constant distance. - if (!ConstOffSCEV) return false; - - int64_t Offset = ConstOffSCEV->getValue()->getSExtValue(); - Type *Ty = cast<PointerType>(PtrA->getType())->getElementType(); - // The Instructions are connsecutive if the size of the first load/store is - // the same as the offset. - int64_t Sz = DL->getTypeStoreSize(Ty); - return ((-Offset) == Sz); -} - -bool BoUpSLP::vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold) { - Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType(); - unsigned Sz = DL->getTypeSizeInBits(StoreTy); - unsigned VF = MinVecRegSize / Sz; - - if (!isPowerOf2_32(Sz) || VF < 2) return false; - - bool Changed = false; - // Look for profitable vectorizable trees at all offsets, starting at zero. - for (unsigned i = 0, e = Chain.size(); i < e; ++i) { - if (i + VF > e) return Changed; - DEBUG(dbgs()<<"SLP: Analyzing " << VF << " stores at offset "<< i << "\n"); - ArrayRef<Value *> Operands = Chain.slice(i, VF); - - int Cost = getTreeCost(Operands); - DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n"); - if (Cost < CostThreshold) { - DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n"); - vectorizeTree(Operands, VF); - i += VF - 1; - Changed = true; - } - } - - return Changed; -} - -bool BoUpSLP::vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold) { - ValueSet Heads, Tails; - SmallDenseMap<Value*, Value*> ConsecutiveChain; - - // We may run into multiple chains that merge into a single chain. We mark the - // stores that we vectorized so that we don't visit the same store twice. - ValueSet VectorizedStores; - bool Changed = false; - - // Do a quadratic search on all of the given stores and find - // all of the pairs of loads that follow each other. - for (unsigned i = 0, e = Stores.size(); i < e; ++i) - for (unsigned j = 0; j < e; ++j) { - if (i == j) continue; - if (isConsecutiveAccess(Stores[i], Stores[j])) { - Tails.insert(Stores[j]); - Heads.insert(Stores[i]); - ConsecutiveChain[Stores[i]] = Stores[j]; - } - } - - // For stores that start but don't end a link in the chain: - for (ValueSet::iterator it = Heads.begin(), e = Heads.end();it != e; ++it) { - if (Tails.count(*it)) continue; - - // We found a store instr that starts a chain. Now follow the chain and try - // to vectorize it. - ValueList Operands; - Value *I = *it; - // Collect the chain into a list. - while (Tails.count(I) || Heads.count(I)) { - if (VectorizedStores.count(I)) break; - Operands.push_back(I); - // Move to the next value in the chain. - I = ConsecutiveChain[I]; - } - - bool Vectorized = vectorizeStoreChain(Operands, costThreshold); - - // Mark the vectorized stores so that we don't vectorize them again. - if (Vectorized) - VectorizedStores.insert(Operands.begin(), Operands.end()); - Changed |= Vectorized; - } - - return Changed; -} - -int BoUpSLP::getScalarizationCost(ArrayRef<Value *> VL) { - // Find the type of the operands in VL. - Type *ScalarTy = VL[0]->getType(); - if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) - ScalarTy = SI->getValueOperand()->getType(); - VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); - // Find the cost of inserting/extracting values from the vector. - return getScalarizationCost(VecTy); -} - -int BoUpSLP::getScalarizationCost(Type *Ty) { - int Cost = 0; - for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i) - Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i); - return Cost; -} - -AliasAnalysis::Location BoUpSLP::getLocation(Instruction *I) { - if (StoreInst *SI = dyn_cast<StoreInst>(I)) return AA->getLocation(SI); - if (LoadInst *LI = dyn_cast<LoadInst>(I)) return AA->getLocation(LI); - return AliasAnalysis::Location(); -} - -Value *BoUpSLP::isUnsafeToSink(Instruction *Src, Instruction *Dst) { - assert(Src->getParent() == Dst->getParent() && "Not the same BB"); - BasicBlock::iterator I = Src, E = Dst; - /// Scan all of the instruction from SRC to DST and check if - /// the source may alias. - for (++I; I != E; ++I) { - // Ignore store instructions that are marked as 'ignore'. - if (MemBarrierIgnoreList.count(I)) continue; - if (Src->mayWriteToMemory()) /* Write */ { - if (!I->mayReadOrWriteMemory()) continue; - } else /* Read */ { - if (!I->mayWriteToMemory()) continue; - } - AliasAnalysis::Location A = getLocation(&*I); - AliasAnalysis::Location B = getLocation(Src); - - if (!A.Ptr || !B.Ptr || AA->alias(A, B)) - return I; - } - return 0; -} - -void BoUpSLP::vectorizeArith(ArrayRef<Value *> Operands) { - Value *Vec = vectorizeTree(Operands, Operands.size()); - BasicBlock::iterator Loc = cast<Instruction>(Vec); - IRBuilder<> Builder(++Loc); - // After vectorizing the operands we need to generate extractelement - // instructions and replace all of the uses of the scalar values with - // the values that we extracted from the vectorized tree. - for (unsigned i = 0, e = Operands.size(); i != e; ++i) { - Value *S = Builder.CreateExtractElement(Vec, Builder.getInt32(i)); - Operands[i]->replaceAllUsesWith(S); - } -} - -int BoUpSLP::getTreeCost(ArrayRef<Value *> VL) { - // Get rid of the list of stores that were removed, and from the - // lists of instructions with multiple users. - MemBarrierIgnoreList.clear(); - LaneMap.clear(); - MultiUserVals.clear(); - MustScalarize.clear(); - - // Scan the tree and find which value is used by which lane, and which values - // must be scalarized. - getTreeUses_rec(VL, 0); - - // Check that instructions with multiple users can be vectorized. Mark unsafe - // instructions. - for (ValueSet::iterator it = MultiUserVals.begin(), - e = MultiUserVals.end(); it != e; ++it) { - // Check that all of the users of this instr are within the tree - // and that they are all from the same lane. - int Lane = -1; - for (Value::use_iterator I = (*it)->use_begin(), E = (*it)->use_end(); - I != E; ++I) { - if (LaneMap.find(*I) == LaneMap.end()) { - MustScalarize.insert(*it); - DEBUG(dbgs()<<"SLP: Adding " << **it << - " to MustScalarize because of an out of tree usage.\n"); - break; - } - if (Lane == -1) Lane = LaneMap[*I]; - if (Lane != LaneMap[*I]) { - MustScalarize.insert(*it); - DEBUG(dbgs()<<"Adding " << **it << - " to MustScalarize because multiple lane use it: " - << Lane << " and " << LaneMap[*I] << ".\n"); - break; - } - } - } - - // Now calculate the cost of vectorizing the tree. - return getTreeCost_rec(VL, 0); -} - -void BoUpSLP::getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth) { - if (Depth == RecursionMaxDepth) return; - - // Don't handle vectors. - if (VL[0]->getType()->isVectorTy()) return; - if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) - if (SI->getValueOperand()->getType()->isVectorTy()) return; - - // Check if all of the operands are constants. - bool AllConst = true; - bool AllSameScalar = true; - for (unsigned i = 0, e = VL.size(); i < e; ++i) { - AllConst &= isa<Constant>(VL[i]); - AllSameScalar &= (VL[0] == VL[i]); - Instruction *I = dyn_cast<Instruction>(VL[i]); - // If one of the instructions is out of this BB, we need to scalarize all. - if (I && I->getParent() != BB) return; - } - - // If all of the operands are identical or constant we have a simple solution. - if (AllConst || AllSameScalar) return; - - // Scalarize unknown structures. - Instruction *VL0 = dyn_cast<Instruction>(VL[0]); - if (!VL0) return; - - unsigned Opcode = VL0->getOpcode(); - for (unsigned i = 0, e = VL.size(); i < e; ++i) { - Instruction *I = dyn_cast<Instruction>(VL[i]); - // If not all of the instructions are identical then we have to scalarize. - if (!I || Opcode != I->getOpcode()) return; - } - - // Mark instructions with multiple users. - for (unsigned i = 0, e = VL.size(); i < e; ++i) { - Instruction *I = dyn_cast<Instruction>(VL[i]); - // Remember to check if all of the users of this instr are vectorized - // within our tree. - if (I && I->getNumUses() > 1) MultiUserVals.insert(I); - } - - for (int i = 0, e = VL.size(); i < e; ++i) { - // Check that the instruction is only used within - // one lane. - if (LaneMap.count(VL[i]) && LaneMap[VL[i]] != i) return; - // Make this instruction as 'seen' and remember the lane. - LaneMap[VL[i]] = i; - } - - switch (Opcode) { - case Instruction::ZExt: - case Instruction::SExt: - case Instruction::FPToUI: - case Instruction::FPToSI: - case Instruction::FPExt: - case Instruction::PtrToInt: - case Instruction::IntToPtr: - case Instruction::SIToFP: - case Instruction::UIToFP: - case Instruction::Trunc: - case Instruction::FPTrunc: - case Instruction::BitCast: - 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: { - for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { - ValueList Operands; - // Prepare the operand vector. - for (unsigned j = 0; j < VL.size(); ++j) - Operands.push_back(cast<Instruction>(VL[j])->getOperand(i)); - - getTreeUses_rec(Operands, Depth+1); - } - return; - } - case Instruction::Store: { - ValueList Operands; - for (unsigned j = 0; j < VL.size(); ++j) - Operands.push_back(cast<Instruction>(VL[j])->getOperand(0)); - getTreeUses_rec(Operands, Depth+1); - return; - } - default: - return; - } -} - -int BoUpSLP::getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth) { - Type *ScalarTy = VL[0]->getType(); - - if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) - ScalarTy = SI->getValueOperand()->getType(); - - /// Don't mess with vectors. - if (ScalarTy->isVectorTy()) return max_cost; - VectorType *VecTy = VectorType::get(ScalarTy, VL.size()); - - if (Depth == RecursionMaxDepth) return getScalarizationCost(VecTy); - - // Check if all of the operands are constants. - bool AllConst = true; - bool AllSameScalar = true; - bool MustScalarizeFlag = false; - for (unsigned i = 0, e = VL.size(); i < e; ++i) { - AllConst &= isa<Constant>(VL[i]); - AllSameScalar &= (VL[0] == VL[i]); - // Must have a single use. - Instruction *I = dyn_cast<Instruction>(VL[i]); - MustScalarizeFlag |= MustScalarize.count(VL[i]); - // This instruction is outside the basic block. - if (I && I->getParent() != BB) - return getScalarizationCost(VecTy); - } - - // Is this a simple vector constant. - if (AllConst) return 0; - - // If all of the operands are identical we can broadcast them. - Instruction *VL0 = dyn_cast<Instruction>(VL[0]); - if (AllSameScalar) { - // If we are in a loop, and this is not an instruction (e.g. constant or - // argument) or the instruction is defined outside the loop then assume - // that the cost is zero. - if (L && (!VL0 || !L->contains(VL0))) - return 0; - - // We need to broadcast the scalar. - return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0); - } - - // If this is not a constant, or a scalar from outside the loop then we - // need to scalarize it. - if (MustScalarizeFlag) - return getScalarizationCost(VecTy); - - if (!VL0) return getScalarizationCost(VecTy); - assert(VL0->getParent() == BB && "Wrong BB"); - - unsigned Opcode = VL0->getOpcode(); - for (unsigned i = 0, e = VL.size(); i < e; ++i) { - Instruction *I = dyn_cast<Instruction>(VL[i]); - // If not all of the instructions are identical then we have to scalarize. - if (!I || Opcode != I->getOpcode()) return getScalarizationCost(VecTy); - } - - // Check if it is safe to sink the loads or the stores. - if (Opcode == Instruction::Load || Opcode == Instruction::Store) { - int MaxIdx = InstrIdx[VL0]; - for (unsigned i = 1, e = VL.size(); i < e; ++i ) - MaxIdx = std::max(MaxIdx, InstrIdx[VL[i]]); - - Instruction *Last = InstrVec[MaxIdx]; - for (unsigned i = 0, e = VL.size(); i < e; ++i ) { - if (VL[i] == Last) continue; - Value *Barrier = isUnsafeToSink(cast<Instruction>(VL[i]), Last); - if (Barrier) { - DEBUG(dbgs() << "SLP: Can't sink " << *VL[i] << "\n down to " << - *Last << "\n because of " << *Barrier << "\n"); - return max_cost; - } - } - } - - switch (Opcode) { - case Instruction::ZExt: - case Instruction::SExt: - case Instruction::FPToUI: - case Instruction::FPToSI: - case Instruction::FPExt: - case Instruction::PtrToInt: - case Instruction::IntToPtr: - case Instruction::SIToFP: - case Instruction::UIToFP: - case Instruction::Trunc: - case Instruction::FPTrunc: - case Instruction::BitCast: { - int Cost = 0; - ValueList Operands; - Type *SrcTy = VL0->getOperand(0)->getType(); - // Prepare the operand vector. - for (unsigned j = 0; j < VL.size(); ++j) { - Operands.push_back(cast<Instruction>(VL[j])->getOperand(0)); - // Check that the casted type is the same for all users. - if (cast<Instruction>(VL[j])->getOperand(0)->getType() != SrcTy) - return getScalarizationCost(VecTy); - } - - Cost += getTreeCost_rec(Operands, Depth+1); - if (Cost >= max_cost) return max_cost; - - // Calculate the cost of this instruction. - int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(), - VL0->getType(), SrcTy); - - VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size()); - int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy); - Cost += (VecCost - ScalarCost); - return Cost; - } - 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: { - int Cost = 0; - // Calculate the cost of all of the operands. - for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) { - ValueList Operands; - // Prepare the operand vector. - for (unsigned j = 0; j < VL.size(); ++j) - Operands.push_back(cast<Instruction>(VL[j])->getOperand(i)); - - Cost += getTreeCost_rec(Operands, Depth+1); - if (Cost >= max_cost) return max_cost; - } - - // Calculate the cost of this instruction. - int ScalarCost = VecTy->getNumElements() * - TTI->getArithmeticInstrCost(Opcode, ScalarTy); - - int VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy); - Cost += (VecCost - ScalarCost); - return Cost; - } - case Instruction::Load: { - // If we are scalarize the loads, add the cost of forming the vector. - for (unsigned i = 0, e = VL.size()-1; i < e; ++i) - if (!isConsecutiveAccess(VL[i], VL[i+1])) - return getScalarizationCost(VecTy); - - // Cost of wide load - cost of scalar loads. - int ScalarLdCost = VecTy->getNumElements() * - TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0); - int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0); - return VecLdCost - ScalarLdCost; - } - case Instruction::Store: { - // We know that we can merge the stores. Calculate the cost. - int ScalarStCost = VecTy->getNumElements() * - TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0); - int VecStCost = TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1,0); - int StoreCost = VecStCost - ScalarStCost; - - ValueList Operands; - for (unsigned j = 0; j < VL.size(); ++j) { - Operands.push_back(cast<Instruction>(VL[j])->getOperand(0)); - MemBarrierIgnoreList.insert(VL[j]); - } - - int TotalCost = StoreCost + getTreeCost_rec(Operands, Depth + 1); - return TotalCost; - } - default: - // Unable to vectorize unknown instructions. - return getScalarizationCost(VecTy); - } -} - -Instruction *BoUpSLP::GetLastInstr(ArrayRef<Value *> VL, unsigned VF) { - int MaxIdx = InstrIdx[BB->getFirstNonPHI()]; - for (unsigned i = 0; i < VF; ++i ) - MaxIdx = std::max(MaxIdx, InstrIdx[VL[i]]); - return InstrVec[MaxIdx + 1]; -} - -Value *BoUpSLP::Scalarize(ArrayRef<Value *> VL, VectorType *Ty) { - IRBuilder<> Builder(GetLastInstr(VL, Ty->getNumElements())); - Value *Vec = UndefValue::get(Ty); - for (unsigned i=0; i < Ty->getNumElements(); ++i) { - // Generate the 'InsertElement' instruction. - Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i)); - // Remember that this instruction is used as part of a 'gather' sequence. - // The caller of the bottom-up slp vectorizer can try to hoist the sequence - // if the users are outside of the basic block. - GatherInstructions.push_back(Vec); - } - - return Vec; -} - -Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL, int VF) { - Value *V = vectorizeTree_rec(VL, VF); - // We moved some instructions around. We have to number them again - // before we can do any analysis. - numberInstructions(); - MustScalarize.clear(); - return V; -} - -Value *BoUpSLP::vectorizeTree_rec(ArrayRef<Value *> VL, int VF) { - Type *ScalarTy = VL[0]->getType(); - if (StoreInst *SI = dyn_cast<StoreInst>(VL[0])) - ScalarTy = SI->getValueOperand()->getType(); - VectorType *VecTy = VectorType::get(ScalarTy, VF); - - // Check if all of the operands are constants or identical. - bool AllConst = true; - bool AllSameScalar = true; - for (unsigned i = 0, e = VF; i < e; ++i) { - AllConst &= isa<Constant>(VL[i]); - AllSameScalar &= (VL[0] == VL[i]); - // The instruction must be in the same BB, and it must be vectorizable. - Instruction *I = dyn_cast<Instruction>(VL[i]); - if (MustScalarize.count(VL[i]) || (I && I->getParent() != BB)) - return Scalarize(VL, VecTy); - } - - // Check that this is a simple vector constant. - if (AllConst || AllSameScalar) return Scalarize(VL, VecTy); - - // Scalarize unknown structures. - Instruction *VL0 = dyn_cast<Instruction>(VL[0]); - if (!VL0) return Scalarize(VL, VecTy); - - if (VectorizedValues.count(VL0)) return VectorizedValues[VL0]; - - unsigned Opcode = VL0->getOpcode(); - for (unsigned i = 0, e = VF; i < e; ++i) { - Instruction *I = dyn_cast<Instruction>(VL[i]); - // If not all of the instructions are identical then we have to scalarize. - if (!I || Opcode != I->getOpcode()) return Scalarize(VL, VecTy); - } - - switch (Opcode) { - case Instruction::ZExt: - case Instruction::SExt: - case Instruction::FPToUI: - case Instruction::FPToSI: - case Instruction::FPExt: - case Instruction::PtrToInt: - case Instruction::IntToPtr: - case Instruction::SIToFP: - case Instruction::UIToFP: - case Instruction::Trunc: - case Instruction::FPTrunc: - case Instruction::BitCast: { - ValueList INVL; - for (int i = 0; i < VF; ++i) - INVL.push_back(cast<Instruction>(VL[i])->getOperand(0)); - Value *InVec = vectorizeTree_rec(INVL, VF); - IRBuilder<> Builder(GetLastInstr(VL, VF)); - CastInst *CI = dyn_cast<CastInst>(VL0); - Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy); - VectorizedValues[VL0] = V; - return V; - } - 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: { - ValueList LHSVL, RHSVL; - for (int i = 0; i < VF; ++i) { - RHSVL.push_back(cast<Instruction>(VL[i])->getOperand(0)); - LHSVL.push_back(cast<Instruction>(VL[i])->getOperand(1)); - } - - Value *RHS = vectorizeTree_rec(RHSVL, VF); - Value *LHS = vectorizeTree_rec(LHSVL, VF); - IRBuilder<> Builder(GetLastInstr(VL, VF)); - BinaryOperator *BinOp = cast<BinaryOperator>(VL0); - Value *V = Builder.CreateBinOp(BinOp->getOpcode(), RHS,LHS); - VectorizedValues[VL0] = V; - return V; - } - case Instruction::Load: { - LoadInst *LI = cast<LoadInst>(VL0); - unsigned Alignment = LI->getAlignment(); - - // Check if all of the loads are consecutive. - for (unsigned i = 1, e = VF; i < e; ++i) - if (!isConsecutiveAccess(VL[i-1], VL[i])) - return Scalarize(VL, VecTy); - - IRBuilder<> Builder(GetLastInstr(VL, VF)); - Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(), - VecTy->getPointerTo()); - LI = Builder.CreateLoad(VecPtr); - LI->setAlignment(Alignment); - VectorizedValues[VL0] = LI; - return LI; - } - case Instruction::Store: { - StoreInst *SI = cast<StoreInst>(VL0); - unsigned Alignment = SI->getAlignment(); - - ValueList ValueOp; - for (int i = 0; i < VF; ++i) - ValueOp.push_back(cast<StoreInst>(VL[i])->getValueOperand()); - - Value *VecValue = vectorizeTree_rec(ValueOp, VF); - - IRBuilder<> Builder(GetLastInstr(VL, VF)); - Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(), - VecTy->getPointerTo()); - Builder.CreateStore(VecValue, VecPtr)->setAlignment(Alignment); - - for (int i = 0; i < VF; ++i) - cast<Instruction>(VL[i])->eraseFromParent(); - return 0; - } - default: - Value *S = Scalarize(VL, VecTy); - VectorizedValues[VL0] = S; - return S; - } -} - -} // end of namespace diff --git a/contrib/llvm/lib/Transforms/Vectorize/VecUtils.h b/contrib/llvm/lib/Transforms/Vectorize/VecUtils.h deleted file mode 100644 index 5456c6c..0000000 --- a/contrib/llvm/lib/Transforms/Vectorize/VecUtils.h +++ /dev/null @@ -1,164 +0,0 @@ -//===- VecUtils.h - Vectorization Utilities -------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This family of classes and functions manipulate vectors and chains of -// vectors. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H -#define LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H - -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/SmallVector.h" -#include "llvm/Analysis/AliasAnalysis.h" -#include <vector> - -namespace llvm { - -class BasicBlock; class Instruction; class Type; -class VectorType; class StoreInst; class Value; -class ScalarEvolution; class DataLayout; -class TargetTransformInfo; class AliasAnalysis; -class Loop; - -/// Bottom Up SLP vectorization utility class. -struct BoUpSLP { - typedef SmallVector<Value*, 8> ValueList; - typedef SmallPtrSet<Value*, 16> ValueSet; - typedef SmallVector<StoreInst*, 8> StoreList; - static const int max_cost = 1<<20; - - // \brief C'tor. - BoUpSLP(BasicBlock *Bb, ScalarEvolution *Se, DataLayout *Dl, - TargetTransformInfo *Tti, AliasAnalysis *Aa, Loop *Lp); - - /// \brief Take the pointer operand from the Load/Store instruction. - /// \returns NULL if this is not a valid Load/Store instruction. - static Value *getPointerOperand(Value *I); - - /// \brief Take the address space operand from the Load/Store instruction. - /// \returns -1 if this is not a valid Load/Store instruction. - static unsigned getAddressSpaceOperand(Value *I); - - /// \returns true if the memory operations A and B are consecutive. - bool isConsecutiveAccess(Value *A, Value *B); - - /// \brief Vectorize the tree that starts with the elements in \p VL. - /// \returns the vectorized value. - Value *vectorizeTree(ArrayRef<Value *> VL, int VF); - - /// \returns the vectorization cost of the subtree that starts at \p VL. - /// A negative number means that this is profitable. - int getTreeCost(ArrayRef<Value *> VL); - - /// \returns the scalarization cost for this list of values. Assuming that - /// this subtree gets vectorized, we may need to extract the values from the - /// roots. This method calculates the cost of extracting the values. - int getScalarizationCost(ArrayRef<Value *> VL); - - /// \brief Attempts to order and vectorize a sequence of stores. This - /// function does a quadratic scan of the given stores. - /// \returns true if the basic block was modified. - bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold); - - /// \brief Vectorize a group of scalars into a vector tree. - void vectorizeArith(ArrayRef<Value *> Operands); - - /// \returns the list of new instructions that were added in order to collect - /// scalars into vectors. This list can be used to further optimize the gather - /// sequences. - ValueList &getGatherSeqInstructions() {return GatherInstructions; } - -private: - /// \brief This method contains the recursive part of getTreeCost. - int getTreeCost_rec(ArrayRef<Value *> VL, unsigned Depth); - - /// \brief This recursive method looks for vectorization hazards such as - /// values that are used by multiple users and checks that values are used - /// by only one vector lane. It updates the variables LaneMap, MultiUserVals. - void getTreeUses_rec(ArrayRef<Value *> VL, unsigned Depth); - - /// \brief This method contains the recursive part of vectorizeTree. - Value *vectorizeTree_rec(ArrayRef<Value *> VL, int VF); - - /// \brief Number all of the instructions in the block. - void numberInstructions(); - - /// \brief Vectorize a sorted sequence of stores. - bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold); - - /// \returns the scalarization cost for this type. Scalarization in this - /// context means the creation of vectors from a group of scalars. - int getScalarizationCost(Type *Ty); - - /// \returns the AA location that is being access by the instruction. - AliasAnalysis::Location getLocation(Instruction *I); - - /// \brief Checks if it is possible to sink an instruction from - /// \p Src to \p Dst. - /// \returns the pointer to the barrier instruction if we can't sink. - Value *isUnsafeToSink(Instruction *Src, Instruction *Dst); - - /// \returns the instruction that appears last in the BB from \p VL. - /// Only consider the first \p VF elements. - Instruction *GetLastInstr(ArrayRef<Value *> VL, unsigned VF); - - /// \returns a vector from a collection of scalars in \p VL. - Value *Scalarize(ArrayRef<Value *> VL, VectorType *Ty); - -private: - /// Maps instructions to numbers and back. - SmallDenseMap<Value*, int> InstrIdx; - /// Maps integers to Instructions. - std::vector<Instruction*> InstrVec; - - // -- containers that are used during getTreeCost -- // - - /// Contains values that must be scalarized because they are used - /// by multiple lanes, or by users outside the tree. - /// NOTICE: The vectorization methods also use this set. - ValueSet MustScalarize; - - /// Contains a list of values that are used outside the current tree. This - /// set must be reset between runs. - ValueSet MultiUserVals; - /// Maps values in the tree to the vector lanes that uses them. This map must - /// be reset between runs of getCost. - std::map<Value*, int> LaneMap; - /// A list of instructions to ignore while sinking - /// memory instructions. This map must be reset between runs of getCost. - SmallPtrSet<Value *, 8> MemBarrierIgnoreList; - - // -- Containers that are used during vectorizeTree -- // - - /// Maps between the first scalar to the vector. This map must be reset - ///between runs. - DenseMap<Value*, Value*> VectorizedValues; - - // -- Containers that are used after vectorization by the caller -- // - - /// A list of instructions that are used when gathering scalars into vectors. - /// In many cases these instructions can be hoisted outside of the BB. - /// Iterating over this list is faster than calling LICM. - ValueList GatherInstructions; - - // Analysis and block reference. - BasicBlock *BB; - ScalarEvolution *SE; - DataLayout *DL; - TargetTransformInfo *TTI; - AliasAnalysis *AA; - Loop *L; -}; - -} // end of namespace - -#endif // LLVM_TRANSFORMS_VECTORIZE_VECUTILS_H |
