Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -16,6 +16,7 @@ #include "llvm/ADT/SmallVector.h" #include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" namespace llvm { class AliasAnalysis; @@ -42,6 +43,132 @@ {} }; +/// This POD struct holds information about a potential reduction operation. +class ReductionInstDesc { + +public: + // This enum represents the kind of minmax reduction. + enum MinMaxReductionKind { + MRK_Invalid, + MRK_UIntMin, + MRK_UIntMax, + MRK_SIntMin, + MRK_SIntMax, + MRK_FloatMin, + MRK_FloatMax + }; + ReductionInstDesc(bool IsRedux, Instruction *I) + : IsReduction(IsRedux), PatternLastInst(I), MinMaxKind(MRK_Invalid) {} + + ReductionInstDesc(Instruction *I, MinMaxReductionKind K) + : IsReduction(true), PatternLastInst(I), MinMaxKind(K) {} + + bool isReduction() { return IsReduction; } + + MinMaxReductionKind getMinMaxKind() { return MinMaxKind; } + +private: + // 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; +}; + +/// This struct holds information about reduction variables. +class ReductionDescriptor { + +public: + /// 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()). + }; + + ReductionDescriptor() + : StartValue(nullptr), LoopExitInstr(nullptr), Kind(RK_NoReduction), + MinMaxKind(ReductionInstDesc::MRK_Invalid) {} + + ReductionDescriptor(Value *Start, Instruction *Exit, ReductionKind K, + ReductionInstDesc::MinMaxReductionKind MK) + : StartValue(Start), LoopExitInstr(Exit), Kind(K), MinMaxKind(MK) {} + + /// 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. + static ReductionInstDesc isReductionInstr(Instruction *I, ReductionKind Kind, + ReductionInstDesc &Prev, + bool HasFunNoNaNAttr); + + /// Returns true if instuction I has multiple uses in Insts + static bool hasMultipleUsesOf(Instruction *I, + SmallPtrSetImpl &Insts); + + /// Returns true if all uses of the instruction I is within the Set. + static bool areAllUsesIn(Instruction *I, SmallPtrSetImpl &Set); + + /// 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). + static ReductionInstDesc isMinMaxSelectCmpPattern(Instruction *I, + ReductionInstDesc &Prev); + + /// Returns identity corresponding to the ReductionKind. + static Constant *getReductionIdentity(ReductionKind K, Type *Tp); + + /// Returns the opcode of binary operation corresponding to the ReductionKind. + static unsigned getReductionBinOp(ReductionKind Kind); + + /// Returns a Min/Max operation corresponding to MinMaxReductionKind. + static Value *createMinMaxOp(IRBuilder<> &Builder, + ReductionInstDesc::MinMaxReductionKind RK, + Value *Left, Value *Right); + + /// Returns true if Phi is a reduction of type Kind and adds it to the + /// ReductionDescriptor. + static bool AddReductionVar(PHINode *Phi, ReductionKind Kind, Loop *TheLoop, + bool HasFunNoNaNAttr, + ReductionDescriptor &RedDes); + + /// Returns true if Phi is a reduction in TheLoop. The ReductionDescriptor is + /// returned in RedDes. + static bool isReductionPHI(PHINode *Phi, Loop *TheLoop, + ReductionDescriptor &RedDes); + + ReductionKind getReductionKind() { return Kind; } + + ReductionInstDesc::MinMaxReductionKind getMinMaxReductionKind() { + return MinMaxKind; + } + + TrackingVH getReductionStartValue() { return StartValue; } + + Instruction *getLoopExitInstr() { return LoopExitInstr; } + +private: + // 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. + ReductionInstDesc::MinMaxReductionKind MinMaxKind; +}; + BasicBlock *InsertPreheaderForLoop(Loop *L, Pass *P); /// \brief Simplify each loop in a loop nest recursively. Index: lib/Transforms/Utils/CMakeLists.txt =================================================================== --- lib/Transforms/Utils/CMakeLists.txt +++ lib/Transforms/Utils/CMakeLists.txt @@ -21,6 +21,7 @@ LoopSimplify.cpp LoopUnroll.cpp LoopUnrollRuntime.cpp + LoopUtils.cpp LowerInvoke.cpp LowerSwitch.cpp Mem2Reg.cpp Index: lib/Transforms/Utils/LoopUtils.cpp =================================================================== --- lib/Transforms/Utils/LoopUtils.cpp +++ lib/Transforms/Utils/LoopUtils.cpp @@ -0,0 +1,453 @@ +//===-- LoopUtils.cpp - Loop Utility functions -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines common loop utility functions. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/PatternMatch.h" +#include "llvm/IR/ValueHandle.h" +#include "llvm/Support/Debug.h" +#include "llvm/Transforms/Utils/LoopUtils.h" + +using namespace llvm; +using namespace llvm::PatternMatch; + +#define DEBUG_TYPE "loop-utils" + +bool ReductionDescriptor::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 ReductionDescriptor::AddReductionVar(PHINode *Phi, ReductionKind Kind, + Loop *TheLoop, bool HasFunNoNaNAttr, + ReductionDescriptor &RedDes) { + if (Phi->getNumIncomingValues() != 2) + return false; + + // Reduction variables are only found in the loop header block. + if (Phi->getParent() != TheLoop->getHeader()) + return false; + + // Obtain the reduction start value from the value that comes from the loop + // preheader. + Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); + + // ExitInstruction is the single value which is used outside the loop. + // We only allow for a single reduction value to be used outside the loop. + // This includes users of the reduction, variables (which form a cycle + // which ends in the phi node). + Instruction *ExitInstruction = nullptr; + // Indicates that we found a reduction operation in our scan. + bool FoundReduxOp = false; + + // 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, + // to make sure we only see exactly the two instructions. + unsigned NumCmpSelectPatternInst = 0; + ReductionInstDesc ReduxDesc(false, nullptr); + + SmallPtrSet VisitedInsts; + SmallVector 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; + + bool IsAPhi = isa(Cur); + + // A header PHI use other than the original PHI. + if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) + return false; + + // Reductions of instructions such as Div, and Sub is only possible if the + // LHS is the reduction variable. + if (!Cur->isCommutative() && !IsAPhi && !isa(Cur) && + !isa(Cur) && !isa(Cur) && + !VisitedInsts.count(dyn_cast(Cur->getOperand(0)))) + return false; + + // Any reduction instruction must be of one of the allowed kinds. + ReduxDesc = isReductionInstr(Cur, Kind, ReduxDesc, HasFunNoNaNAttr); + 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(Cur) || isa(Cur))) + ++NumCmpSelectPatternInst; + if (Kind == RK_FloatMinMax && (isa(Cur) || isa(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 NonPHIs; + SmallVector PHIs; + for (User *U : Cur->users()) { + Instruction *UI = cast(U); + + // Check if we found the exit user. + BasicBlock *Parent = UI->getParent(); + if (!TheLoop->contains(Parent)) { + // 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 != nullptr || Cur == Phi) + return false; + + // 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; + + ExitInstruction = Cur; + continue; + } + + // Process instructions only once (termination). Each reduction cycle + // value must only be used once, except by phi nodes and min/max + // reductions which are represented as a cmp followed by a select. + ReductionInstDesc IgnoredVal(false, nullptr); + if (VisitedInsts.insert(UI).second) { + if (isa(UI)) + PHIs.push_back(UI); + else + NonPHIs.push_back(UI); + } else if (!isa(UI) && + ((!isa(UI) && !isa(UI) && + !isa(UI)) || + !isMinMaxSelectCmpPattern(UI, IgnoredVal).isReduction())) + return false; + + // Remember that we completed the cycle. + if (UI == Phi) + FoundStartPHI = true; + } + Worklist.append(PHIs.begin(), PHIs.end()); + Worklist.append(NonPHIs.begin(), NonPHIs.end()); + } + + // 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; + + if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) + 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. + + // The ExitInstruction(Instruction which is allowed to have out-of-loop users) + // is saved as part of the ReductionDescriptor. + + // Save the description of this reduction variable. + ReductionDescriptor RD(RdxStart, ExitInstruction, Kind, + ReduxDesc.getMinMaxKind()); + + 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). +ReductionInstDesc +ReductionDescriptor::isMinMaxSelectCmpPattern(Instruction *I, + ReductionInstDesc &Prev) { + + assert((isa(I) || isa(I) || isa(I)) && + "Expect a select instruction"); + Instruction *Cmp = nullptr; + SelectInst *Select = nullptr; + + // We must handle the select(cmp()) as a single instruction. Advance to the + // select. + if ((Cmp = dyn_cast(I)) || (Cmp = dyn_cast(I))) { + if (!Cmp->hasOneUse() || !(Select = dyn_cast(*I->user_begin()))) + return ReductionInstDesc(false, I); + return ReductionInstDesc(Select, Prev.getMinMaxKind()); + } + + // Only handle single use cases for now. + if (!(Select = dyn_cast(I))) + return ReductionInstDesc(false, I); + if (!(Cmp = dyn_cast(I->getOperand(0))) && + !(Cmp = dyn_cast(I->getOperand(0)))) + return ReductionInstDesc(false, I); + if (!Cmp->hasOneUse()) + return ReductionInstDesc(false, I); + + Value *CmpLeft; + Value *CmpRight; + + // Look for a min/max pattern. + if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_UIntMin); + else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_UIntMax); + else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_SIntMax); + else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_SIntMin); + else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMin); + else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMax); + else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMin); + else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) + return ReductionInstDesc(Select, ReductionInstDesc::MRK_FloatMax); + + return ReductionInstDesc(false, I); +} + +ReductionInstDesc ReductionDescriptor::isReductionInstr(Instruction *I, + ReductionKind Kind, + ReductionInstDesc &Prev, + bool HasFunNoNaNAttr) { + bool FP = I->getType()->isFloatingPointTy(); + bool FastMath = FP && I->hasUnsafeAlgebra(); + switch (I->getOpcode()) { + default: + return ReductionInstDesc(false, I); + case Instruction::PHI: + if (FP && + (Kind != RK_FloatMult && Kind != RK_FloatAdd && Kind != RK_FloatMinMax)) + return ReductionInstDesc(false, I); + return ReductionInstDesc(I, Prev.getMinMaxKind()); + case Instruction::Sub: + case Instruction::Add: + return ReductionInstDesc(Kind == RK_IntegerAdd, I); + case Instruction::Mul: + return ReductionInstDesc(Kind == RK_IntegerMult, I); + case Instruction::And: + return ReductionInstDesc(Kind == RK_IntegerAnd, I); + case Instruction::Or: + return ReductionInstDesc(Kind == RK_IntegerOr, I); + case Instruction::Xor: + return ReductionInstDesc(Kind == RK_IntegerXor, I); + case Instruction::FMul: + return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I); + case Instruction::FSub: + case Instruction::FAdd: + return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I); + case Instruction::FCmp: + case Instruction::ICmp: + case Instruction::Select: + if (Kind != RK_IntegerMinMax && + (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) + return ReductionInstDesc(false, I); + return isMinMaxSelectCmpPattern(I, Prev); + } +} + +bool ReductionDescriptor::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))) + ++NumUses; + if (NumUses > 1) + return true; + } + + return false; +} +bool ReductionDescriptor::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() << "Found an ADD reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found a MUL reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerOr, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found an OR reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerAnd, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found an AND reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerXor, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found a XOR reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_IntegerMinMax, TheLoop, HasFunNoNaNAttr, + RedDes)) { + DEBUG(dbgs() << "Found a MINMAX reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatMult, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found an FMult reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatAdd, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found an FAdd reduction PHI." << *Phi << "\n"); + return true; + } + if (AddReductionVar(Phi, RK_FloatMinMax, TheLoop, HasFunNoNaNAttr, RedDes)) { + DEBUG(dbgs() << "Found an float MINMAX reduction PHI." << *Phi << "\n"); + return true; + } + // Not a reduction of known type. + return false; +} + +/// This function returns the identity element (or neutral element) for +/// the operation K. +Constant *ReductionDescriptor::getReductionIdentity(ReductionKind K, Type *Tp) { + switch (K) { + case RK_IntegerXor: + case RK_IntegerAdd: + case RK_IntegerOr: + // Adding, Xoring, Oring zero to a number does not change it. + return ConstantInt::get(Tp, 0); + case RK_IntegerMult: + // Multiplying a number by 1 does not change it. + return ConstantInt::get(Tp, 1); + case RK_IntegerAnd: + // AND-ing a number with an all-1 value does not change it. + return ConstantInt::get(Tp, -1, true); + case RK_FloatMult: + // Multiplying a number by 1 does not change it. + return ConstantFP::get(Tp, 1.0L); + case RK_FloatAdd: + // Adding zero to a number does not change it. + return ConstantFP::get(Tp, 0.0L); + default: + llvm_unreachable("Unknown reduction kind"); + } +} + +/// This function translates the reduction kind to an LLVM binary operator. +unsigned ReductionDescriptor::getReductionBinOp(ReductionKind Kind) { + switch (Kind) { + case RK_IntegerAdd: + return Instruction::Add; + case RK_IntegerMult: + return Instruction::Mul; + case RK_IntegerOr: + return Instruction::Or; + case RK_IntegerAnd: + return Instruction::And; + case RK_IntegerXor: + return Instruction::Xor; + case RK_FloatMult: + return Instruction::FMul; + case RK_FloatAdd: + return Instruction::FAdd; + case RK_IntegerMinMax: + return Instruction::ICmp; + case RK_FloatMinMax: + return Instruction::FCmp; + default: + llvm_unreachable("Unknown reduction operation"); + } +} + +Value * +ReductionDescriptor::createMinMaxOp(IRBuilder<> &Builder, + ReductionInstDesc::MinMaxReductionKind RK, + Value *Left, Value *Right) { + CmpInst::Predicate P = CmpInst::ICMP_NE; + switch (RK) { + default: + llvm_unreachable("Unknown min/max reduction kind"); + case ReductionInstDesc::MRK_UIntMin: + P = CmpInst::ICMP_ULT; + break; + case ReductionInstDesc::MRK_UIntMax: + P = CmpInst::ICMP_UGT; + break; + case ReductionInstDesc::MRK_SIntMin: + P = CmpInst::ICMP_SLT; + break; + case ReductionInstDesc::MRK_SIntMax: + P = CmpInst::ICMP_SGT; + break; + case ReductionInstDesc::MRK_FloatMin: + P = CmpInst::FCMP_OLT; + break; + case ReductionInstDesc::MRK_FloatMax: + P = CmpInst::FCMP_OGT; + break; + } + + Value *Cmp; + if (RK == ReductionInstDesc::MRK_FloatMin || + RK == ReductionInstDesc::MRK_FloatMax) + Cmp = Builder.CreateFCmp(P, Left, Right, "rdx.minmax.cmp"); + else + Cmp = Builder.CreateICmp(P, Left, Right, "rdx.minmax.cmp"); + + Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); + return Select; +} 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) @@ -759,10 +697,6 @@ return LAI; } - /// This function returns the identity element (or neutral element) for - /// the operation K. - static Constant *getReductionIdentity(ReductionKind K, Type *Tp); - unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); } bool hasStride(Value *V) { return StrideSet.count(V); } @@ -820,20 +754,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); @@ -2469,98 +2389,6 @@ Hints.setAlreadyVectorized(); } -/// This function returns the identity element (or neutral element) for -/// the operation K. -Constant* -LoopVectorizationLegality::getReductionIdentity(ReductionKind K, Type *Tp) { - switch (K) { - case RK_IntegerXor: - case RK_IntegerAdd: - case RK_IntegerOr: - // Adding, Xoring, Oring zero to a number does not change it. - return ConstantInt::get(Tp, 0); - case RK_IntegerMult: - // Multiplying a number by 1 does not change it. - return ConstantInt::get(Tp, 1); - case RK_IntegerAnd: - // AND-ing a number with an all-1 value does not change it. - return ConstantInt::get(Tp, -1, true); - case RK_FloatMult: - // Multiplying a number by 1 does not change it. - return ConstantFP::get(Tp, 1.0L); - case RK_FloatAdd: - // Adding zero to a number does not change it. - return ConstantFP::get(Tp, 0.0L); - default: - llvm_unreachable("Unknown reduction kind"); - } -} - -/// This function translates the reduction kind to an LLVM binary operator. -static unsigned -getReductionBinOp(LoopVectorizationLegality::ReductionKind Kind) { - switch (Kind) { - case LoopVectorizationLegality::RK_IntegerAdd: - return Instruction::Add; - case LoopVectorizationLegality::RK_IntegerMult: - return Instruction::Mul; - case LoopVectorizationLegality::RK_IntegerOr: - return Instruction::Or; - case LoopVectorizationLegality::RK_IntegerAnd: - return Instruction::And; - case LoopVectorizationLegality::RK_IntegerXor: - return Instruction::Xor; - case LoopVectorizationLegality::RK_FloatMult: - return Instruction::FMul; - case LoopVectorizationLegality::RK_FloatAdd: - return Instruction::FAdd; - case LoopVectorizationLegality::RK_IntegerMinMax: - return Instruction::ICmp; - case LoopVectorizationLegality::RK_FloatMinMax: - return Instruction::FCmp; - default: - llvm_unreachable("Unknown reduction operation"); - } -} - -static Value *createMinMaxOp(IRBuilder<> &Builder, - LoopVectorizationLegality::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: - P = CmpInst::ICMP_ULT; - break; - case LoopVectorizationLegality::MRK_UIntMax: - P = CmpInst::ICMP_UGT; - break; - case LoopVectorizationLegality::MRK_SIntMin: - P = CmpInst::ICMP_SLT; - break; - case LoopVectorizationLegality::MRK_SIntMax: - P = CmpInst::ICMP_SGT; - break; - case LoopVectorizationLegality::MRK_FloatMin: - P = CmpInst::FCMP_OLT; - break; - case LoopVectorizationLegality::MRK_FloatMax: - P = CmpInst::FCMP_OGT; - break; - } - - Value *Cmp; - 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"); - - Value *Select = Builder.CreateSelect(Cmp, Left, Right, "rdx.minmax.select"); - return Select; -} - namespace { struct CSEDenseMapInfo { static bool canHandle(Instruction *I) { @@ -2772,10 +2600,14 @@ // 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); + ReductionDescriptor::ReductionKind RK = RdxDesc.getReductionKind(); + TrackingVH ReductionStartValue = RdxDesc.getReductionStartValue(); + Instruction *LoopExitInst = RdxDesc.getLoopExitInstr(); + ReductionInstDesc::MinMaxReductionKind MinMaxKind = + RdxDesc.getMinMaxReductionKind(); + setDebugLocFromInst(Builder, ReductionStartValue); // We need to generate a reduction vector from the incoming scalar. // To do so, we need to generate the 'identity' vector and override @@ -2784,40 +2616,38 @@ Builder.SetInsertPoint(LoopBypassBlocks[1]->getTerminator()); // This is the vector-clone of the value that leaves the loop. - VectorParts &VectorExit = getVectorValue(RdxDesc.LoopExitInstr); + VectorParts &VectorExit = getVectorValue(LoopExitInst); Type *VecTy = VectorExit[0]->getType(); // Find the reduction identity variable. Zero for addition, or, xor, // one for multiplication, -1 for And. Value *Identity; Value *VectorStart; - if (RdxDesc.Kind == LoopVectorizationLegality::RK_IntegerMinMax || - RdxDesc.Kind == LoopVectorizationLegality::RK_FloatMinMax) { + if (RK == ReductionDescriptor::RK_IntegerMinMax || + RK == ReductionDescriptor::RK_FloatMinMax) { // MinMax reduction have the start value as their identify. if (VF == 1) { - VectorStart = Identity = RdxDesc.StartValue; + VectorStart = Identity = ReductionStartValue; } else { - VectorStart = Identity = Builder.CreateVectorSplat(VF, - RdxDesc.StartValue, - "minmax.ident"); + VectorStart = Identity = + Builder.CreateVectorSplat(VF, ReductionStartValue, "minmax.ident"); } } else { // Handle other reduction kinds: Constant *Iden = - LoopVectorizationLegality::getReductionIdentity(RdxDesc.Kind, - VecTy->getScalarType()); + ReductionDescriptor::getReductionIdentity(RK, 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; + VectorStart = ReductionStartValue; } 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); + VectorStart = + Builder.CreateInsertElement(Identity, ReductionStartValue, Zero); } } @@ -2846,11 +2676,11 @@ Builder.SetInsertPoint(LoopMiddleBlock->getFirstInsertionPt()); VectorParts RdxParts; - setDebugLocFromInst(Builder, RdxDesc.LoopExitInstr); + setDebugLocFromInst(Builder, LoopExitInst); 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. - VectorParts &RdxExitVal = getVectorValue(RdxDesc.LoopExitInstr); + VectorParts &RdxExitVal = getVectorValue(LoopExitInst); PHINode *NewPhi = Builder.CreatePHI(VecTy, 2, "rdx.vec.exit.phi"); Value *StartVal = (part == 0) ? VectorStart : Identity; for (unsigned I = 1, E = LoopBypassBlocks.size(); I != E; ++I) @@ -2862,7 +2692,7 @@ // Reduce all of the unrolled parts into a single vector. Value *ReducedPartRdx = RdxParts[0]; - unsigned Op = getReductionBinOp(RdxDesc.Kind); + unsigned Op = ReductionDescriptor::getReductionBinOp(RK); setDebugLocFromInst(Builder, ReducedPartRdx); for (unsigned part = 1; part < UF; ++part) { if (Op != Instruction::ICmp && Op != Instruction::FCmp) @@ -2871,8 +2701,8 @@ Builder.CreateBinOp((Instruction::BinaryOps)Op, RdxParts[part], ReducedPartRdx, "bin.rdx")); else - ReducedPartRdx = createMinMaxOp(Builder, RdxDesc.MinMaxKind, - ReducedPartRdx, RdxParts[part]); + ReducedPartRdx = ReductionDescriptor::createMinMaxOp( + Builder, MinMaxKind, ReducedPartRdx, RdxParts[part]); } if (VF > 1) { @@ -2903,7 +2733,8 @@ TmpVec = addFastMathFlag(Builder.CreateBinOp( (Instruction::BinaryOps)Op, TmpVec, Shuf, "bin.rdx")); else - TmpVec = createMinMaxOp(Builder, RdxDesc.MinMaxKind, TmpVec, Shuf); + TmpVec = ReductionDescriptor::createMinMaxOp(Builder, MinMaxKind, + TmpVec, Shuf); } // The result is in the first element of the vector. @@ -2915,7 +2746,7 @@ // block and the middle block. PHINode *BCBlockPhi = PHINode::Create(RdxPhi->getType(), 2, "bc.merge.rdx", LoopScalarPreHeader->getTerminator()); - BCBlockPhi->addIncoming(RdxDesc.StartValue, LoopBypassBlocks[0]); + BCBlockPhi->addIncoming(ReductionStartValue, LoopBypassBlocks[0]); BCBlockPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock); // Now, we need to fix the users of the reduction variable @@ -2933,7 +2764,7 @@ // We found our reduction value exit-PHI. Update it with the // incoming bypass edge. - if (LCSSAPhi->getIncomingValue(0) == RdxDesc.LoopExitInstr) { + if (LCSSAPhi->getIncomingValue(0) == LoopExitInst) { // Add an edge coming from the bypass. LCSSAPhi->addIncoming(ReducedPartRdx, LoopMiddleBlock); break; @@ -2948,7 +2779,7 @@ // Pick the other block. int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1); (RdxPhi)->setIncomingValue(SelfEdgeBlockIdx, BCBlockPhi); - (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, RdxDesc.LoopExitInstr); + (RdxPhi)->setIncomingValue(IncomingEdgeBlockIdx, LoopExitInst); }// end of for each redux variable. fixLCSSAPHIs(); @@ -3712,41 +3543,9 @@ 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 (ReductionDescriptor::isReductionPHI(Phi, TheLoop, + Reductions[Phi])) { + AllowedExit.insert(Reductions[Phi].getLoopExitInstr()); continue; } @@ -4029,294 +3828,6 @@ return true; } -static bool 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))) - ++NumUses; - if (NumUses > 1) - return true; - } - - return false; -} - -static bool 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) { - if (Phi->getNumIncomingValues() != 2) - return false; - - // Reduction variables are only found in the loop header block. - if (Phi->getParent() != TheLoop->getHeader()) - return false; - - // Obtain the reduction start value from the value that comes from the loop - // preheader. - Value *RdxStart = Phi->getIncomingValueForBlock(TheLoop->getLoopPreheader()); - - // ExitInstruction is the single value which is used outside the loop. - // We only allow for a single reduction value to be used outside the loop. - // This includes users of the reduction, variables (which form a cycle - // which ends in the phi node). - Instruction *ExitInstruction = nullptr; - // Indicates that we found a reduction operation in our scan. - bool FoundReduxOp = false; - - // 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, - // to make sure we only see exactly the two instructions. - unsigned NumCmpSelectPatternInst = 0; - ReductionInstDesc ReduxDesc(false, nullptr); - - SmallPtrSet VisitedInsts; - SmallVector 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; - - bool IsAPhi = isa(Cur); - - // A header PHI use other than the original PHI. - if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) - return false; - - // Reductions of instructions such as Div, and Sub is only possible if the - // LHS is the reduction variable. - if (!Cur->isCommutative() && !IsAPhi && !isa(Cur) && - !isa(Cur) && !isa(Cur) && - !VisitedInsts.count(dyn_cast(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(Cur) || - isa(Cur))) - ++NumCmpSelectPatternInst; - if (Kind == RK_FloatMinMax && (isa(Cur) || - isa(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 NonPHIs; - SmallVector PHIs; - for (User *U : Cur->users()) { - Instruction *UI = cast(U); - - // Check if we found the exit user. - BasicBlock *Parent = UI->getParent(); - if (!TheLoop->contains(Parent)) { - // 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 != nullptr || Cur == Phi) - return false; - - // 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; - - ExitInstruction = Cur; - continue; - } - - // Process instructions only once (termination). Each reduction cycle - // value must only be used once, except by phi nodes and min/max - // reductions which are represented as a cmp followed by a select. - ReductionInstDesc IgnoredVal(false, nullptr); - if (VisitedInsts.insert(UI).second) { - if (isa(UI)) - PHIs.push_back(UI); - else - NonPHIs.push_back(UI); - } else if (!isa(UI) && - ((!isa(UI) && - !isa(UI) && - !isa(UI)) || - !isMinMaxSelectCmpPattern(UI, IgnoredVal).IsReduction)) - return false; - - // Remember that we completed the cycle. - if (UI == Phi) - FoundStartPHI = true; - } - Worklist.append(PHIs.begin(), PHIs.end()); - Worklist.append(NonPHIs.begin(), NonPHIs.end()); - } - - // 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; - - if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) - 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. - - // 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 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) { - - assert((isa(I) || isa(I) || isa(I)) && - "Expect a select instruction"); - Instruction *Cmp = nullptr; - SelectInst *Select = nullptr; - - // We must handle the select(cmp()) as a single instruction. Advance to the - // select. - if ((Cmp = dyn_cast(I)) || (Cmp = dyn_cast(I))) { - if (!Cmp->hasOneUse() || !(Select = dyn_cast(*I->user_begin()))) - return ReductionInstDesc(false, I); - return ReductionInstDesc(Select, Prev.MinMaxKind); - } - - // Only handle single use cases for now. - if (!(Select = dyn_cast(I))) - return ReductionInstDesc(false, I); - if (!(Cmp = dyn_cast(I->getOperand(0))) && - !(Cmp = dyn_cast(I->getOperand(0)))) - return ReductionInstDesc(false, I); - if (!Cmp->hasOneUse()) - return ReductionInstDesc(false, I); - - Value *CmpLeft; - Value *CmpRight; - - // Look for a min/max pattern. - if (m_UMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_UIntMin); - else if (m_UMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_UIntMax); - else if (m_SMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_SIntMax); - else if (m_SMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_SIntMin); - else if (m_OrdFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_FloatMin); - else if (m_OrdFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_FloatMax); - else if (m_UnordFMin(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_FloatMin); - else if (m_UnordFMax(m_Value(CmpLeft), m_Value(CmpRight)).match(Select)) - return ReductionInstDesc(Select, MRK_FloatMax); - - return ReductionInstDesc(false, I); -} - -LoopVectorizationLegality::ReductionInstDesc -LoopVectorizationLegality::isReductionInstr(Instruction *I, - ReductionKind Kind, - ReductionInstDesc &Prev) { - bool FP = I->getType()->isFloatingPointTy(); - bool FastMath = FP && I->hasUnsafeAlgebra(); - switch (I->getOpcode()) { - default: - return ReductionInstDesc(false, I); - case Instruction::PHI: - if (FP && (Kind != RK_FloatMult && Kind != RK_FloatAdd && - Kind != RK_FloatMinMax)) - return ReductionInstDesc(false, I); - return ReductionInstDesc(I, Prev.MinMaxKind); - case Instruction::Sub: - case Instruction::Add: - return ReductionInstDesc(Kind == RK_IntegerAdd, I); - case Instruction::Mul: - return ReductionInstDesc(Kind == RK_IntegerMult, I); - case Instruction::And: - return ReductionInstDesc(Kind == RK_IntegerAnd, I); - case Instruction::Or: - return ReductionInstDesc(Kind == RK_IntegerOr, I); - case Instruction::Xor: - return ReductionInstDesc(Kind == RK_IntegerXor, I); - case Instruction::FMul: - return ReductionInstDesc(Kind == RK_FloatMult && FastMath, I); - case Instruction::FSub: - case Instruction::FAdd: - return ReductionInstDesc(Kind == RK_FloatAdd && FastMath, I); - case Instruction::FCmp: - case Instruction::ICmp: - case Instruction::Select: - if (Kind != RK_IntegerMinMax && - (!HasFunNoNaNAttr || Kind != RK_FloatMinMax)) - return ReductionInstDesc(false, I); - return isMinMaxSelectCmpPattern(I, Prev); - } -} - bool llvm::isInductionPHI(PHINode *Phi, ScalarEvolution *SE, ConstantInt *&StepValue) { Type *PhiTy = Phi->getType();