Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -42,6 +42,93 @@ {} }; +/// This enum represents the kinds of reductions that we support. +enum ReductionKind { + RK_NoReduction, ///< Not a reduction. + RK_IntegerAdd, ///< Sum of integers. + RK_IntegerMult, ///< Product of integers. + RK_IntegerOr, ///< Bitwise or logical OR of numbers. + RK_IntegerAnd, ///< Bitwise or logical AND of numbers. + RK_IntegerXor, ///< Bitwise or logical XOR of numbers. + RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). + RK_FloatAdd, ///< Sum of floats. + RK_FloatMult, ///< Product of floats. + RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). +}; + +// This enum represents the kind of minmax reduction. +enum MinMaxReductionKind { + MRK_Invalid, + MRK_UIntMin, + MRK_UIntMax, + MRK_SIntMin, + MRK_SIntMax, + MRK_FloatMin, + MRK_FloatMax +}; + +/// This struct holds information about reduction variables. +struct ReductionDescriptor { + ReductionDescriptor() + : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoReduction), + MinMaxKind(MRK_Invalid) {} + + ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K, + MinMaxReductionKind MK) + : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {} + + // The starting value of the reduction. + // It does not have to be zero! + TrackingVH StartValue; + // The instruction who's value is used outside the loop. + Instruction *LoopExitInstr; + // The kind of the reduction. + ReductionKind Kind; + // If this a min/max reduction the kind of reduction. + MinMaxReductionKind MinMaxKind; +}; + +/// This POD struct holds information about a potential reduction operation. +struct ReductionInstDesc { + ReductionInstDesc(bool IsRedux, Instruction *I) + : IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {} + + ReductionInstDesc(Instruction *I, MinMaxReductionKind K) + : IsReduction(true), PatternLastInst(I), MinMaxKind(K) {} + + // Is this instruction a reduction candidate. + bool IsReduction; + // The last instruction in a min/max pattern (select of the select(icmp()) + // pattern), or the current reduction instruction otherwise. + Instruction *PatternLastInst; + // If this is a min/max pattern the comparison predicate. + MinMaxReductionKind MinMaxKind; +}; + +/// Returns a struct describing if the instruction if the instruction is a +/// Select(ICmp(X, Y), X, Y) instruction pattern corresponding to a min(X, Y) +/// or max(X, Y). +ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I, + ReductionInstDesc &Prev); + +/// Returns a struct describing if the instruction 'I' can be a reduction +/// variable of type 'Kind'. If the reduction is a min/max pattern of +/// select(icmp()) this function advances the instruction pointer 'I' from the +/// compare instruction to the select instruction and stores this pointer in +/// 'PatternLastInst' member of the returned struct. +ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind, + ReductionInstDesc &Prev, + bool HasFunNoNaNAttr); + +bool AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop, + bool HasFunNoNaNAttr, ReductionDescriptor &RedDes); + +bool isReductionPHI(PHINode *Phi, Loop *TheLoop, ReductionDescriptor &RedDes); + +bool hasMultipleUsesOf(Instruction *I, SmallPtrSetImpl &Insts); + +bool areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set); + BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P); /// \brief Simplify each loop in a loop nest recursively. Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -568,20 +568,6 @@ TTI(TTI), DT(DT), LAA(LAA), LAI(nullptr), Induction(nullptr), WidestIndTy(nullptr), HasFunNoNaNAttr(false) {} - /// This enum represents the kinds of reductions that we support. - enum ReductionKind { - RK_NoReduction, ///< Not a reduction. - RK_IntegerAdd, ///< Sum of integers. - RK_IntegerMult, ///< Product of integers. - RK_IntegerOr, ///< Bitwise or logical OR of numbers. - RK_IntegerAnd, ///< Bitwise or logical AND of numbers. - RK_IntegerXor, ///< Bitwise or logical XOR of numbers. - RK_IntegerMinMax, ///< Min/max implemented in terms of select(cmp()). - RK_FloatAdd, ///< Sum of floats. - RK_FloatMult, ///< Product of floats. - RK_FloatMinMax ///< Min/max implemented in terms of select(cmp()). - }; - /// This enum represents the kinds of inductions that we support. enum InductionKind { IK_NoInduction, ///< Not an induction variable. @@ -589,54 +575,6 @@ IK_PtrInduction ///< Pointer induction var. Step = C / sizeof(elem). }; - // This enum represents the kind of minmax reduction. - enum MinMaxReductionKind { - MRK_Invalid, - MRK_UIntMin, - MRK_UIntMax, - MRK_SIntMin, - MRK_SIntMax, - MRK_FloatMin, - MRK_FloatMax - }; - - /// This struct holds information about reduction variables. - struct ReductionDescriptor { - ReductionDescriptor() : StartValue(nullptr), LoopExitInstr(nullptr), - Kind(RK_NoReduction), MinMaxKind(MRK_Invalid) {} - - ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K, - MinMaxReductionKind MK) - : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {} - - // The starting value of the reduction. - // It does not have to be zero! - TrackingVH StartValue; - // The instruction who's value is used outside the loop. - Instruction *LoopExitInstr; - // The kind of the reduction. - ReductionKind Kind; - // If this a min/max reduction the kind of reduction. - MinMaxReductionKind MinMaxKind; - }; - - /// This POD struct holds information about a potential reduction operation. - struct ReductionInstDesc { - ReductionInstDesc(bool IsRedux, Instruction *I) : - IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {} - - ReductionInstDesc(Instruction *I, MinMaxReductionKind K) : - IsReduction(true), PatternLastInst(I), MinMaxKind(K) {} - - // Is this instruction a reduction candidate. - bool IsReduction; - // The last instruction in a min/max pattern (select of the select(icmp()) - // pattern), or the current reduction instruction otherwise. - Instruction *PatternLastInst; - // If this is a min/max pattern the comparison predicate. - MinMaxReductionKind MinMaxKind; - }; - /// A struct for saving information about induction variables. struct InductionInfo { InductionInfo(Value *Start, InductionKind K, ConstantInt *Step) @@ -820,20 +758,6 @@ /// and we know that we can read from them without segfault. bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl &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. - bool AddReductionVar(PHINode *Phi, ReductionKind Kind); - /// Returns a struct describing if the instruction 'I' can be a reduction - /// variable of type 'Kind'. If the reduction is a min/max pattern of - /// select(icmp()) this function advances the instruction pointer 'I' from the - /// compare instruction to the select instruction and stores this pointer in - /// 'PatternLastInst' member of the returned struct. - ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind, - ReductionInstDesc &Desc); - /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction - /// pattern corresponding to a min(X, Y) or max(X, Y). - static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I, - ReductionInstDesc &Prev); /// 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); @@ -2497,62 +2421,59 @@ } /// This function translates the reduction kind to an LLVM binary operator. -static unsigned -getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) { +static unsigned getReductionBinOp(ReductionKind Kind) { switch (Kind) { - case LoopVectorizationLegality::RK_IntegerAdd: + case RK_IntegerAdd: return Instruction::Add; - case LoopVectorizationLegality::RK_IntegerMult: + case RK_IntegerMult: return Instruction::Mul; - case LoopVectorizationLegality::RK_IntegerOr: + case RK_IntegerOr: return Instruction::Or; - case LoopVectorizationLegality::RK_IntegerAnd: + case RK_IntegerAnd: return Instruction::And; - case LoopVectorizationLegality::RK_IntegerXor: + case RK_IntegerXor: return Instruction::Xor; - case LoopVectorizationLegality::RK_FloatMult: + case RK_FloatMult: return Instruction::FMul; - case LoopVectorizationLegality::RK_FloatAdd: + case RK_FloatAdd: return Instruction::FAdd; - case LoopVectorizationLegality::RK_IntegerMinMax: + case RK_IntegerMinMax: return Instruction::ICmp; - case LoopVectorizationLegality::RK_FloatMinMax: + case RK_FloatMinMax: return Instruction::FCmp; default: llvm_unreachable("Unknown reduction operation"); } } -static Value *createMinMaxOp(IRBuilder<> &Builder, - LoopVectorizationLegality::MinMaxReductionKind RK, +static Value *createMinMaxOp(IRBuilder<> &Builder, MinMaxReductionKind RK, Value *Left, Value *Right) { CmpInst::Predicate P = CmpInst::ICMP_NE; switch (RK) { default: llvm_unreachable("Unknown min/max reduction kind"); - case LoopVectorizationLegality::MRK_UIntMin: + case MRK_UIntMin: P = CmpInst::ICMP_ULT; break; - case LoopVectorizationLegality::MRK_UIntMax: + case MRK_UIntMax: P = CmpInst::ICMP_UGT; break; - case LoopVectorizationLegality::MRK_SIntMin: + case MRK_SIntMin: P = CmpInst::ICMP_SLT; break; - case LoopVectorizationLegality::MRK_SIntMax: + case MRK_SIntMax: P = CmpInst::ICMP_SGT; break; - case LoopVectorizationLegality::MRK_FloatMin: + case MRK_FloatMin: P = CmpInst::FCMP_OLT; break; - case LoopVectorizationLegality::MRK_FloatMax: + case MRK_FloatMax: P = CmpInst::FCMP_OGT; break; } Value *Cmp; - if (RK == LoopVectorizationLegality::MRK_FloatMin || - RK == LoopVectorizationLegality::MRK_FloatMax) + if (RK == MRK_FloatMin || RK == MRK_FloatMax) Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); else Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); @@ -2772,8 +2693,7 @@ // Find the reduction variable descriptor. assert(Legal->getReductionVars()->count(RdxPhi) && "Unable to find the reduction variable"); - LoopVectorizationLegality::ReductionDescriptor RdxDesc = - (*Legal->getReductionVars())[RdxPhi]; + ReductionDescriptor RdxDesc = (*Legal->getReductionVars())[RdxPhi]; setDebugLocFromInst(Builder, RdxDesc.StartValue); @@ -2791,8 +2711,7 @@ // one for multiplication, -1 for And. Value *Identity; Value *VectorStart; - if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax || - RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) { + if (RdxDesc.Kind == RK_IntegerMinMax || RdxDesc.Kind == RK_FloatMinMax) { // MinMax reduction have the start value as their identify. if (VF == 1) { VectorStart = Identity = RdxDesc.StartValue; @@ -3622,6 +3541,57 @@ return false; } +bool llvm::isReductionPHI(PHINode *Phi, Loop *TheLoop, + ReductionDescriptor &RedDes) { + + bool HasFunNoNaNAttr = false; + BasicBlock *Header = TheLoop->getHeader(); + Function &F = *Header->getParent(); + if (F.hasFnAttribute("no-nans-fp-math")) + HasFunNoNaNAttr = + F.getFnAttribute("no-nans-fp-math").getValueAsString() == "true"; + + if (AddReductionVar(Phi, RK_IntegerAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found an ADD reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found a MUL reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found an OR reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found an AND reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found a XOR reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, + RedDes)) { + DEBUG(dbgs() << "LV: Found a MINMAX reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found an FMult reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found an FAdd reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI." << *Phi << "\n"); + return true; + } + // Not a reduction of known type. + return false; +} + bool LoopVectorizationLegality::canVectorizeInstrs() { BasicBlock *PreHeader = TheLoop->getLoopPreheader(); BasicBlock *Header = TheLoop->getHeader(); @@ -3711,42 +3681,8 @@ continue; } - - if (AddReductionVar(Phi, RK_IntegerAdd)) { - DEBUG(dbgs() << "LV: Found an ADD reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_IntegerMult)) { - DEBUG(dbgs() << "LV: Found a MUL reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_IntegerOr)) { - DEBUG(dbgs() << "LV: Found an OR reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_IntegerAnd)) { - DEBUG(dbgs() << "LV: Found an AND reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_IntegerXor)) { - DEBUG(dbgs() << "LV: Found a XOR reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_IntegerMinMax)) { - DEBUG(dbgs() << "LV: Found a MINMAX reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_FloatMult)) { - DEBUG(dbgs() << "LV: Found an FMult reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_FloatAdd)) { - DEBUG(dbgs() << "LV: Found an FAdd reduction PHI."<< *Phi <<"\n"); - continue; - } - if (AddReductionVar(Phi, RK_FloatMinMax)) { - DEBUG(dbgs() << "LV: Found an float MINMAX reduction PHI."<< *Phi << - "\n"); + if (isReductionPHI(Phi, TheLoop, Reductions[Phi])) { + AllowedExit.insert(Reductions[Phi].LoopExitInstr); continue; } @@ -4029,8 +3965,8 @@ return true; } -static bool hasMultipleUsesOf(Instruction *I, - SmallPtrSetImpl &Insts) { +bool llvm::hasMultipleUsesOf(Instruction *I, + SmallPtrSetImpl &Insts) { unsigned NumUses = 0; for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) { if (Insts.count(dyn_cast(*Use))) @@ -4042,15 +3978,15 @@ return false; } -static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set) { +bool llvm::areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set) { for(User::op_iterator Use = I->op_begin(), E = I->op_end(); Use != E; ++Use) if (!Set.count(dyn_cast(*Use))) return false; return true; } -bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi, - ReductionKind Kind) { +bool llvm::AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop, + bool HasFunNoNaNAttr, ReductionDescriptor &RedDes) { if (Phi->getNumIncomingValues() != 2) return false; @@ -4125,7 +4061,7 @@ return false; // Any reduction instruction must be of one of the allowed kinds. - ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc); + ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); if (!ReduxDesc.IsReduction) return false; @@ -4213,23 +4149,20 @@ // only have a single instruction with out-of-loop users. // 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. + + RedDes = RD; return true; } /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction /// pattern corresponding to a min(X, Y) or max(X, Y). -LoopVectorizationLegality::ReductionInstDesc -LoopVectorizationLegality::isMinMaxSelectCmpPattern(Instruction *I, - ReductionInstDesc &Prev) { +ReductionInstDesc llvm::isMinMaxSelectCmpPattern(Instruction *I, + ReductionInstDesc &Prev) { assert((isa(I) || isa(I) || isa(I)) && "Expect a select instruction"); @@ -4277,10 +4210,9 @@ return ReductionInstDesc(false, I); } -LoopVectorizationLegality::ReductionInstDesc -LoopVectorizationLegality::isReductionInstr(Instruction *I, - ReductionKind Kind, - ReductionInstDesc &Prev) { +ReductionInstDesc llvm::isReductionInstr(Instruction *I, ReductionKind Kind, + ReductionInstDesc &Prev, + bool HasFunNoNaNAttr) { bool FP = I->getType()->isFloatingPointTy(); bool FastMath = FP && I->hasUnsafeAlgebra(); switch (I->getOpcode()) {