Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -198,6 +198,54 @@ Instruction *UnsafeAlgebraInst; }; +/// A struct for saving information about induction variables. +class InductionDescriptor { +public: + /// This enum represents the kinds of inductions that we support. + enum InductionKind { + IK_NoInduction, ///< Not an induction variable. + IK_IntInduction, ///< Integer induction variable. Step = C. + IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem). + }; + +private: + /// Private constructor - use \c isInductionPHI. + InductionDescriptor(Value *Start, InductionKind K, ConstantInt *Step); +public: + /// Default constructor made public for convenience. + InductionDescriptor() + : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {} + + /// Get the consecutive direction. Returns: + /// 0 - unknown or non-consecutive. + /// 1 - consecutive and increasing. + /// -1 - consecutive and decreasing. + int getConsecutiveDirection() const; + + /// Compute the transformed value of Index at offset StartValue using step + /// StepValue. + /// For integer induction, returns StartValue + Index * StepValue. + /// For pointer induction, returns StartValue[Index * StepValue]. + /// FIXME: The newly created binary instructions should contain nsw/nuw + /// flags, which can be found from the original scalar operations. + Value *transform(IRBuilder<> &B, Value *Index) const; + + Value *getStartValue() const { return StartValue; } + InductionKind getKind() const { return IK; } + ConstantInt *getStepValue() const { return StepValue; } + + static bool isInductionPHI(PHINode *Phi, ScalarEvolution *SE, + InductionDescriptor &D); + +private: + /// Start value. + TrackingVH StartValue; + /// Induction kind. + InductionKind IK; + /// Step value. + ConstantInt *StepValue; +}; + BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P); /// \brief Simplify each loop in a loop nest recursively. @@ -276,11 +324,6 @@ /// exception, it takes LICMSafetyInfo and loop as argument. /// Updates safety information in LICMSafetyInfo argument. void computeLICMSafetyInfo(LICMSafetyInfo *, Loop *); - -/// \brief Checks if the given PHINode in a loop header is an induction -/// variable. Returns true if this is an induction PHI along with the step -/// value. -bool isInductionPHI(PHINode *, ScalarEvolution *, ConstantInt *&); } #endif Index: lib/Transforms/Scalar/LoopInterchange.cpp =================================================================== --- lib/Transforms/Scalar/LoopInterchange.cpp +++ lib/Transforms/Scalar/LoopInterchange.cpp @@ -698,9 +698,9 @@ return false; for (BasicBlock::iterator I = L->getHeader()->begin(); isa(I); ++I) { RecurrenceDescriptor RD; + InductionDescriptor ID; PHINode *PHI = cast(I); - ConstantInt *StepValue = nullptr; - if (isInductionPHI(PHI, SE, StepValue)) + if (InductionDescriptor::isInductionPHI(PHI, SE, ID)) Inductions.push_back(PHI); else if (RecurrenceDescriptor::isReductionPHI(PHI, L, RD)) Reductions.push_back(PHI); Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -456,8 +456,54 @@ return Select; } -bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE, - ConstantInt *&StepValue) { +InductionDescriptor::InductionDescriptor(Value *Start, InductionKind K, + ConstantInt *Step) + : StartValue(Start), IK(K), StepValue(Step) { + assert(IK != IK_NoInduction && "Not an induction"); + assert(StartValue && "StartValue is null"); + assert(StepValue && !StepValue->isZero() && "StepValue is zero"); + assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && + "StartValue is not a pointer for pointer induction"); + assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && + "StartValue is not an integer for integer induction"); + assert(StepValue->getType()->isIntegerTy() && + "StepValue is not an integer"); +} + +int InductionDescriptor::getConsecutiveDirection() const { + if (StepValue && (StepValue->isOne() || StepValue->isMinusOne())) + return StepValue->getSExtValue(); + return 0; +} + +Value *InductionDescriptor::transform(IRBuilder<> &B, Value *Index) const { + switch (IK) { + case IK_IntInduction: + assert(Index->getType() == StartValue->getType() && + "Index type does not match StartValue type"); + if (StepValue->isMinusOne()) + return B.CreateSub(StartValue, Index); + if (!StepValue->isOne()) + Index = B.CreateMul(Index, StepValue); + return B.CreateAdd(StartValue, Index); + + case IK_PtrInduction: + assert(Index->getType() == StepValue->getType() && + "Index type does not match StepValue type"); + if (StepValue->isMinusOne()) + Index = B.CreateNeg(Index); + else if (!StepValue->isOne()) + Index = B.CreateMul(Index, StepValue); + return B.CreateGEP(nullptr, StartValue, Index); + + case IK_NoInduction: + return nullptr; + } + llvm_unreachable("invalid enum"); +} + +bool InductionDescriptor::isInductionPHI(PHINode *Phi, ScalarEvolution *SE, + InductionDescriptor &D) { Type *PhiTy = Phi->getType(); // We only handle integer and pointer inductions variables. if (!PhiTy->isIntegerTy() && !PhiTy->isPointerTy()) @@ -471,6 +517,8 @@ return false; } + Value *StartValue = + Phi->getIncomingValueForBlock(AR->getLoop()->getLoopPreheader()); const SCEV *Step = AR->getStepRecurrence(*SE); // Calculate the pointer stride and check if it is consecutive. const SCEVConstant *C = dyn_cast(Step); @@ -479,7 +527,7 @@ ConstantInt *CV = C->getValue(); if (PhiTy->isIntegerTy()) { - StepValue = CV; + D = InductionDescriptor(StartValue, IK_IntInduction, CV); return true; } @@ -498,6 +546,8 @@ int64_t CVSize = CV->getSExtValue(); if (CVSize % Size) return false; - StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size); + auto *StepValue = ConstantInt::getSigned(CV->getType(), CVSize / Size); + + D = InductionDescriptor(StartValue, IK_PtrInduction, StepValue); return true; } Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1086,87 +1086,13 @@ Induction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false), Requirements(R), Hints(H) {} - /// This enum represents the kinds of inductions that we support. - enum InductionKind { - IK_NoInduction, ///< Not an induction variable. - IK_IntInduction, ///< Integer induction variable. Step = C. - IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem). - }; - - /// A struct for saving information about induction variables. - struct InductionInfo { - InductionInfo(Value *Start, InductionKind K, ConstantInt *Step) - : StartValue(Start), IK(K), StepValue(Step) { - assert(IK != IK_NoInduction && "Not an induction"); - assert(StartValue && "StartValue is null"); - assert(StepValue && !StepValue->isZero() && "StepValue is zero"); - assert((IK != IK_PtrInduction || StartValue->getType()->isPointerTy()) && - "StartValue is not a pointer for pointer induction"); - assert((IK != IK_IntInduction || StartValue->getType()->isIntegerTy()) && - "StartValue is not an integer for integer induction"); - assert(StepValue->getType()->isIntegerTy() && - "StepValue is not an integer"); - } - InductionInfo() - : StartValue(nullptr), IK(IK_NoInduction), StepValue(nullptr) {} - - /// Get the consecutive direction. Returns: - /// 0 - unknown or non-consecutive. - /// 1 - consecutive and increasing. - /// -1 - consecutive and decreasing. - int getConsecutiveDirection() const { - if (StepValue && (StepValue->isOne() || StepValue->isMinusOne())) - return StepValue->getSExtValue(); - return 0; - } - - /// Compute the transformed value of Index at offset StartValue using step - /// StepValue. - /// For integer induction, returns StartValue + Index * StepValue. - /// For pointer induction, returns StartValue[Index * StepValue]. - /// FIXME: The newly created binary instructions should contain nsw/nuw - /// flags, which can be found from the original scalar operations. - Value *transform(IRBuilder<> &B, Value *Index) const { - switch (IK) { - case IK_IntInduction: - assert(Index->getType() == StartValue->getType() && - "Index type does not match StartValue type"); - if (StepValue->isMinusOne()) - return B.CreateSub(StartValue, Index); - if (!StepValue->isOne()) - Index = B.CreateMul(Index, StepValue); - return B.CreateAdd(StartValue, Index); - - case IK_PtrInduction: - assert(Index->getType() == StepValue->getType() && - "Index type does not match StepValue type"); - if (StepValue->isMinusOne()) - Index = B.CreateNeg(Index); - else if (!StepValue->isOne()) - Index = B.CreateMul(Index, StepValue); - return B.CreateGEP(nullptr, StartValue, Index); - - case IK_NoInduction: - return nullptr; - } - llvm_unreachable("invalid enum"); - } - - /// Start value. - TrackingVH StartValue; - /// Induction kind. - InductionKind IK; - /// Step value. - ConstantInt *StepValue; - }; - /// ReductionList contains the reduction descriptors for all /// of the reductions that were found in the loop. typedef DenseMap ReductionList; /// InductionList saves induction variables and maps them to the /// induction descriptor. - typedef MapVector InductionList; + typedef MapVector InductionList; /// Returns true if it is legal to vectorize this loop. /// This does not mean that it is profitable to vectorize this @@ -1284,10 +1210,6 @@ /// and we know that we can read from them without segfault. bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl &SafePtrs); - /// Returns the induction kind of Phi and record the step. This function may - /// return NoInduction if the PHI is not an induction variable. - InductionKind isInductionVariable(PHINode *Phi, ConstantInt *&StepValue); - /// \brief Collect memory access with loop invariant strides. /// /// Looks for accesses like "a[i * StrideA]" where "StrideA" is loop @@ -1937,7 +1859,7 @@ // If this value is a pointer induction variable we know it is consecutive. PHINode *Phi = dyn_cast_or_null(Ptr); if (Phi && Inductions.count(Phi)) { - InductionInfo II = Inductions[Phi]; + InductionDescriptor II = Inductions[Phi]; return II.getConsecutiveDirection(); } @@ -1962,7 +1884,7 @@ if (!SE->isLoopInvariant(SE->getSCEV(Gep->getOperand(i)), TheLoop)) return 0; - InductionInfo II = Inductions[Phi]; + InductionDescriptor II = Inductions[Phi]; return II.getConsecutiveDirection(); } @@ -2866,7 +2788,7 @@ BypassBuilder.SetInsertPoint(LoopBypassBlocks.back()->getTerminator()); for (I = List->begin(), E = List->end(); I != E; ++I) { PHINode *OrigPhi = I->first; - LoopVectorizationLegality::InductionInfo II = I->second; + InductionDescriptor II = I->second; Type *ResumeValTy = (OrigPhi == OldInduction) ? IdxTy : OrigPhi->getType(); PHINode *ResumeVal = PHINode::Create(ResumeValTy, 2, "resume.val", @@ -2891,10 +2813,10 @@ } Value *EndValue = nullptr; - switch (II.IK) { - case LoopVectorizationLegality::IK_NoInduction: + switch (II.getKind()) { + case InductionDescriptor::IK_NoInduction: llvm_unreachable("Unknown induction"); - case LoopVectorizationLegality::IK_IntInduction: { + case InductionDescriptor::IK_IntInduction: { // Handle the integer induction counter. assert(OrigPhi->getType()->isIntegerTy() && "Invalid type"); @@ -2907,10 +2829,10 @@ // 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 = 1, E = LoopBypassBlocks.size(); I != E; ++I) - TruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); + TruncResumeVal->addIncoming(II.getStartValue(), LoopBypassBlocks[I]); TruncResumeVal->addIncoming(EndValue, VecBody); - BCTruncResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[0]); + BCTruncResumeVal->addIncoming(II.getStartValue(), LoopBypassBlocks[0]); // We know what the end value is. EndValue = IdxEndRoundDown; @@ -2922,15 +2844,15 @@ // Not the canonical induction variable - add the vector loop count to the // start value. Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown, - II.StartValue->getType(), + II.getStartValue()->getType(), "cast.crd"); EndValue = II.transform(BypassBuilder, CRD); EndValue->setName("ind.end"); break; } - case LoopVectorizationLegality::IK_PtrInduction: { + case InductionDescriptor::IK_PtrInduction: { Value *CRD = BypassBuilder.CreateSExtOrTrunc(CountRoundDown, - II.StepValue->getType(), + II.getStepValue()->getType(), "cast.crd"); EndValue = II.transform(BypassBuilder, CRD); EndValue->setName("ptr.ind.end"); @@ -2944,7 +2866,7 @@ if (OrigPhi == OldInduction) ResumeVal->addIncoming(StartIdx, LoopBypassBlocks[I]); else - ResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[I]); + ResumeVal->addIncoming(II.getStartValue(), LoopBypassBlocks[I]); } ResumeVal->addIncoming(EndValue, VecBody); @@ -2957,7 +2879,7 @@ BCResumeVal->addIncoming(StartIdx, LoopBypassBlocks[0]); OrigPhi->setIncomingValue(BlockIdx, BCTruncResumeVal); } else { - BCResumeVal->addIncoming(II.StartValue, LoopBypassBlocks[0]); + BCResumeVal->addIncoming(II.getStartValue(), LoopBypassBlocks[0]); OrigPhi->setIncomingValue(BlockIdx, BCResumeVal); } } @@ -3542,16 +3464,15 @@ assert(Legal->getInductionVars()->count(P) && "Not an induction variable"); - LoopVectorizationLegality::InductionInfo II = - Legal->getInductionVars()->lookup(P); + InductionDescriptor II = Legal->getInductionVars()->lookup(P); // FIXME: The newly created binary instructions should contain nsw/nuw flags, // which can be found from the original scalar operations. - switch (II.IK) { - case LoopVectorizationLegality::IK_NoInduction: + switch (II.getKind()) { + case InductionDescriptor::IK_NoInduction: llvm_unreachable("Unknown induction"); - case LoopVectorizationLegality::IK_IntInduction: { - assert(P->getType() == II.StartValue->getType() && "Types must match"); + case InductionDescriptor::IK_IntInduction: { + assert(P->getType() == II.getStartValue()->getType() && "Types must match"); Type *PhiTy = P->getType(); Value *Broadcasted; if (P == OldInduction) { @@ -3571,17 +3492,17 @@ // 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] = getStepVector(Broadcasted, VF * part, II.StepValue); + Entry[part] = getStepVector(Broadcasted, VF * part, II.getStepValue()); return; } - case LoopVectorizationLegality::IK_PtrInduction: + case InductionDescriptor::IK_PtrInduction: // Handle the pointer induction variable case. assert(P->getType()->isPointerTy() && "Unexpected type."); // This is the normalized GEP that starts counting at zero. Value *NormalizedIdx = Builder.CreateSub(Induction, ExtendedIdx, "normalized.idx"); NormalizedIdx = - Builder.CreateSExtOrTrunc(NormalizedIdx, II.StepValue->getType()); + Builder.CreateSExtOrTrunc(NormalizedIdx, II.getStepValue()->getType()); // 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) { @@ -3742,10 +3663,9 @@ Value *ScalarCast = Builder.CreateCast(CI->getOpcode(), Induction, CI->getType()); Value *Broadcasted = getBroadcastInstrs(ScalarCast); - LoopVectorizationLegality::InductionInfo II = - Legal->getInductionVars()->lookup(OldInduction); + InductionDescriptor II = Legal->getInductionVars()->lookup(OldInduction); Constant *Step = - ConstantInt::getSigned(CI->getType(), II.StepValue->getSExtValue()); + ConstantInt::getSigned(CI->getType(), II.getStepValue()->getSExtValue()); for (unsigned Part = 0; Part < UF; ++Part) Entry[Part] = getStepVector(Broadcasted, VF * Part, Step); propagateMetadata(Entry, it); @@ -4092,7 +4012,6 @@ } bool LoopVectorizationLegality::canVectorizeInstrs() { - BasicBlock *PreHeader = TheLoop->getLoopPreheader(); BasicBlock *Header = TheLoop->getHeader(); // Look for the attribute signaling the absence of NaNs. @@ -4144,13 +4063,9 @@ return false; } - // This is the value coming from the preheader. - Value *StartValue = Phi->getIncomingValueForBlock(PreHeader); - ConstantInt *StepValue = nullptr; - // Check if this is an induction variable. - InductionKind IK = isInductionVariable(Phi, StepValue); - - if (IK_NoInduction != IK) { + InductionDescriptor ID; + if (InductionDescriptor::isInductionPHI(Phi, SE, ID)) { + Inductions[Phi] = ID; // Get the widest type. if (!WidestIndTy) WidestIndTy = convertPointerToIntegerType(DL, PhiTy); @@ -4158,7 +4073,8 @@ WidestIndTy = getWiderType(DL, PhiTy, WidestIndTy); // Int inductions are special because we only allow one IV. - if (IK == IK_IntInduction && StepValue->isOne()) { + if (ID.getKind() == InductionDescriptor::IK_IntInduction && + ID.getStepValue()->isOne()) { // 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). @@ -4167,7 +4083,6 @@ } DEBUG(dbgs() << "LV: Found an induction variable.\n"); - Inductions[Phi] = InductionInfo(StartValue, IK, StepValue); // Until we explicitly handle the case of an induction variable with // an outside loop user we have to give up vectorizing this loop. @@ -4350,20 +4265,6 @@ return true; } -LoopVectorizationLegality::InductionKind -LoopVectorizationLegality::isInductionVariable(PHINode *Phi, - ConstantInt *&StepValue) { - if (!isInductionPHI(Phi, SE, StepValue)) - return IK_NoInduction; - - Type *PhiTy = Phi->getType(); - // Found an Integer induction variable. - if (PhiTy->isIntegerTy()) - return IK_IntInduction; - // Found an Pointer induction variable. - return IK_PtrInduction; -} - bool LoopVectorizationLegality::isInductionVariable(const Value *V) { Value *In0 = const_cast(V); PHINode *PN = dyn_cast_or_null(In0);