diff --git a/llvm/include/llvm/Analysis/IVDescriptors.h b/llvm/include/llvm/Analysis/IVDescriptors.h --- a/llvm/include/llvm/Analysis/IVDescriptors.h +++ b/llvm/include/llvm/Analysis/IVDescriptors.h @@ -33,27 +33,29 @@ /// These are the kinds of recurrences that we support. enum class RecurKind { - None, ///< Not a recurrence. - Add, ///< Sum of integers. - Mul, ///< Product of integers. - Or, ///< Bitwise or logical OR of integers. - And, ///< Bitwise or logical AND of integers. - Xor, ///< Bitwise or logical XOR of integers. - SMin, ///< Signed integer min implemented in terms of select(cmp()). - SMax, ///< Signed integer max implemented in terms of select(cmp()). - UMin, ///< Unsigned integer min implemented in terms of select(cmp()). - UMax, ///< Unsigned integer max implemented in terms of select(cmp()). - FAdd, ///< Sum of floats. - FMul, ///< Product of floats. - FMin, ///< FP min implemented in terms of select(cmp()). - FMax, ///< FP max implemented in terms of select(cmp()). - FMinimum, ///< FP min with llvm.minimum semantics - FMaximum, ///< FP max with llvm.maximum semantics - FMulAdd, ///< Sum of float products with llvm.fmuladd(a * b + sum). - SelectICmp, ///< Integer select(icmp(),x,y) where one of (x,y) is loop - ///< invariant - SelectFCmp ///< Integer select(fcmp(),x,y) where one of (x,y) is loop - ///< invariant + None, ///< Not a recurrence. + Add, ///< Sum of integers. + Mul, ///< Product of integers. + Or, ///< Bitwise or logical OR of integers. + And, ///< Bitwise or logical AND of integers. + Xor, ///< Bitwise or logical XOR of integers. + SMin, ///< Signed integer min implemented in terms of select(cmp()). + SMax, ///< Signed integer max implemented in terms of select(cmp()). + UMin, ///< Unsigned integer min implemented in terms of select(cmp()). + UMax, ///< Unsigned integer max implemented in terms of select(cmp()). + FAdd, ///< Sum of floats. + FMul, ///< Product of floats. + FMin, ///< FP min implemented in terms of select(cmp()). + FMax, ///< FP max implemented in terms of select(cmp()). + FMinimum, ///< FP min with llvm.minimum semantics + FMaximum, ///< FP max with llvm.maximum semantics + FMulAdd, ///< Sum of float products with llvm.fmuladd(a * b + sum). + IAnyOf, ///< Any_of reduction with select(icmp(),x,y) where one of (x,y) is an + ///< loop invariant, and both x and y are integer type. + FAnyOf ///< Any_of reduction with select(fcmp(),x,y) where one of (x,y) is an + ///< loop invariant, and both x and y are integer type. + // TODO: Any_of reduction can be applied not only to integer types, but also + // to float types. In other words, x and y can also be of float type. }; /// The RecurrenceDescriptor is used to identify recurrences variables in a @@ -236,8 +238,14 @@ /// Returns true if the recurrence kind is of the form /// select(cmp(),x,y) where one of (x,y) is loop invariant. + static bool isAnyOfRecurrenceKind(RecurKind Kind) { + return Kind == RecurKind::IAnyOf || Kind == RecurKind::FAnyOf; + } + + /// Returns true if the recurrence kind is of the form + /// select(cmp(),x,y). static bool isSelectCmpRecurrenceKind(RecurKind Kind) { - return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp; + return isAnyOfRecurrenceKind(Kind); } /// Returns the type of the recurrence. This type can be narrower than the diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -397,9 +397,9 @@ RecurKind RdxKind); /// Create a target reduction of the given vector \p Src for a reduction of the -/// kind RecurKind::SelectICmp or RecurKind::SelectFCmp. The reduction operation -/// is described by \p Desc. -Value *createSelectCmpTargetReduction(IRBuilderBase &B, +/// kind RecurKind::IAnyOf or RecurKind::FAnyOf. The reduction operation is +/// described by \p Desc. +Value *createAnyOfTargetReduction(IRBuilderBase &B, const TargetTransformInfo *TTI, Value *Src, const RecurrenceDescriptor &Desc, diff --git a/llvm/lib/Analysis/IVDescriptors.cpp b/llvm/lib/Analysis/IVDescriptors.cpp --- a/llvm/lib/Analysis/IVDescriptors.cpp +++ b/llvm/lib/Analysis/IVDescriptors.cpp @@ -52,8 +52,8 @@ case RecurKind::SMin: case RecurKind::UMax: case RecurKind::UMin: - case RecurKind::SelectICmp: - case RecurKind::SelectFCmp: + case RecurKind::IAnyOf: + case RecurKind::FAnyOf: return true; } return false; @@ -419,10 +419,10 @@ if (IsAPhi && Cur != Phi && !areAllUsesIn(Cur, VisitedInsts)) return false; - if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectICmp) && + if ((isIntMinMaxRecurrenceKind(Kind) || Kind == RecurKind::IAnyOf) && (isa(Cur) || isa(Cur))) ++NumCmpSelectPatternInst; - if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::SelectFCmp) && + if ((isFPMinMaxRecurrenceKind(Kind) || Kind == RecurKind::FAnyOf) && (isa(Cur) || isa(Cur))) ++NumCmpSelectPatternInst; @@ -659,8 +659,8 @@ if (!Loop->isLoopInvariant(NonPhi)) return InstDesc(false, I); - return InstDesc(I, isa(I->getOperand(0)) ? RecurKind::SelectICmp - : RecurKind::SelectFCmp); + return InstDesc(I, isa(I->getOperand(0)) ? RecurKind::IAnyOf + : RecurKind::FAnyOf); } RecurrenceDescriptor::InstDesc @@ -897,8 +897,8 @@ LLVM_DEBUG(dbgs() << "Found a UMIN reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RecurKind::SelectICmp, TheLoop, FMF, RedDes, DB, AC, - DT, SE)) { + if (AddReductionVar(Phi, RecurKind::IAnyOf, TheLoop, FMF, RedDes, DB, AC, DT, + SE)) { LLVM_DEBUG(dbgs() << "Found an integer conditional select reduction PHI." << *Phi << "\n"); return true; @@ -923,8 +923,8 @@ LLVM_DEBUG(dbgs() << "Found a float MIN reduction PHI." << *Phi << "\n"); return true; } - if (AddReductionVar(Phi, RecurKind::SelectFCmp, TheLoop, FMF, RedDes, DB, AC, - DT, SE)) { + if (AddReductionVar(Phi, RecurKind::FAnyOf, TheLoop, FMF, RedDes, DB, AC, DT, + SE)) { LLVM_DEBUG(dbgs() << "Found a float conditional select reduction PHI." << " PHI." << *Phi << "\n"); return true; @@ -1088,8 +1088,8 @@ return ConstantFP::getInfinity(Tp, false /*Negative*/); case RecurKind::FMaximum: return ConstantFP::getInfinity(Tp, true /*Negative*/); - case RecurKind::SelectICmp: - case RecurKind::SelectFCmp: + case RecurKind::IAnyOf: + case RecurKind::FAnyOf: return getRecurrenceStartValue(); break; default: @@ -1118,13 +1118,13 @@ case RecurKind::SMin: case RecurKind::UMax: case RecurKind::UMin: - case RecurKind::SelectICmp: + case RecurKind::IAnyOf: return Instruction::ICmp; case RecurKind::FMax: case RecurKind::FMin: case RecurKind::FMaximum: case RecurKind::FMinimum: - case RecurKind::SelectFCmp: + case RecurKind::FAnyOf: return Instruction::FCmp; default: llvm_unreachable("Unknown recurrence operation"); diff --git a/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp b/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp --- a/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp +++ b/llvm/lib/Target/AArch64/AArch64TargetTransformInfo.cpp @@ -3284,9 +3284,9 @@ case RecurKind::UMax: case RecurKind::FMin: case RecurKind::FMax: - case RecurKind::SelectICmp: - case RecurKind::SelectFCmp: case RecurKind::FMulAdd: + case RecurKind::IAnyOf: + case RecurKind::FAnyOf: return true; default: return false; diff --git a/llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h b/llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h --- a/llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h +++ b/llvm/lib/Target/RISCV/RISCVTargetTransformInfo.h @@ -288,9 +288,9 @@ case RecurKind::UMax: case RecurKind::FMin: case RecurKind::FMax: - case RecurKind::SelectICmp: - case RecurKind::SelectFCmp: case RecurKind::FMulAdd: + case RecurKind::IAnyOf: + case RecurKind::FAnyOf: return true; default: return false; diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1028,14 +1028,14 @@ return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0)); } -Value *llvm::createSelectCmpTargetReduction(IRBuilderBase &Builder, - const TargetTransformInfo *TTI, - Value *Src, - const RecurrenceDescriptor &Desc, - PHINode *OrigPhi) { - assert(RecurrenceDescriptor::isSelectCmpRecurrenceKind( - Desc.getRecurrenceKind()) && - "Unexpected reduction kind"); +Value *llvm::createAnyOfTargetReduction(IRBuilderBase &Builder, + const TargetTransformInfo *TTI, + Value *Src, + const RecurrenceDescriptor &Desc, + PHINode *OrigPhi) { + assert( + RecurrenceDescriptor::isAnyOfRecurrenceKind(Desc.getRecurrenceKind()) && + "Unexpected reduction kind"); Value *InitVal = Desc.getRecurrenceStartValue(); Value *NewVal = nullptr; @@ -1121,8 +1121,8 @@ B.setFastMathFlags(Desc.getFastMathFlags()); RecurKind RK = Desc.getRecurrenceKind(); - if (RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) - return createSelectCmpTargetReduction(B, TTI, Src, Desc, OrigPhi); + if (RecurrenceDescriptor::isAnyOfRecurrenceKind(RK)) + return createAnyOfTargetReduction(B, TTI, Src, Desc, OrigPhi); return createSimpleTargetReduction(B, TTI, Src, RK); } diff --git a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp --- a/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp +++ b/llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -14028,8 +14028,8 @@ case RecurKind::Mul: case RecurKind::FMul: case RecurKind::FMulAdd: - case RecurKind::SelectICmp: - case RecurKind::SelectFCmp: + case RecurKind::IAnyOf: + case RecurKind::FAnyOf: case RecurKind::None: llvm_unreachable("Unexpected reduction kind for repeated scalar."); } @@ -14117,8 +14117,8 @@ case RecurKind::Mul: case RecurKind::FMul: case RecurKind::FMulAdd: - case RecurKind::SelectICmp: - case RecurKind::SelectFCmp: + case RecurKind::IAnyOf: + case RecurKind::FAnyOf: case RecurKind::None: llvm_unreachable("Unexpected reduction kind for reused scalars."); } diff --git a/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp b/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp --- a/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp +++ b/llvm/lib/Transforms/Vectorize/VPlanRecipes.cpp @@ -1269,7 +1269,7 @@ Value *Iden = nullptr; RecurKind RK = RdxDesc.getRecurrenceKind(); if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK) || - RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) { + RecurrenceDescriptor::isAnyOfRecurrenceKind(RK)) { // MinMax reduction have the start value as their identify. if (ScalarPHI) { Iden = StartV; diff --git a/llvm/test/Transforms/LoopVectorize/smax-idx.ll b/llvm/test/Transforms/LoopVectorize/smax-idx.ll --- a/llvm/test/Transforms/LoopVectorize/smax-idx.ll +++ b/llvm/test/Transforms/LoopVectorize/smax-idx.ll @@ -55,11 +55,13 @@ ret i64 %spec.select7 } -; Check if it is a MMI when smax is not used outside the loop. +; Check if it is a min/max with index (MMI) pattern when the +; min/max value is not used outside the loop. ; -; Currently at the end, it will check if smax has exitInstruction. -; But in fact MMI should be possible to use the exitInstruction of -; SelectICmp be the exitInstruction. +; Currently, the vectorizer checks if smax value is used outside +; the loop. However, even if only the index part has external users, +; and smax itself does not have external users, it can still form a +; MMI pattern. ; define i64 @smax_idx_max_no_exit_user(ptr nocapture readonly %a, i64 %mm, i64 %ii, i64 %n) { ; CHECK-LABEL: @smax_idx_max_no_exit_user( @@ -86,11 +88,11 @@ ret i64 %spec.select7 } -; Check smax implemented in terms of select(cmp()). +; Check smax implemented in format of select(cmp()). ; -; Currently SelectICmp does not support icmp with multiple users. -; It may be possible to reuse some of the methods in Combination pass to check -; whether icmp can be copied. +; Currently, MMI pattern does not support icmp with multiple users. +; TODO: It may be possible to reuse some of the methods in instcombine pass to +; check whether icmp can be dupicated. ; define i64 @smax_idx_select_cmp(ptr nocapture readonly %a, i64 %mm, i64 %ii, ptr nocapture writeonly %res_max, i64 %n) { ; CHECK-LABEL: @smax_idx_select_cmp(