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,28 @@ /// 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 + ///< 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 + ///< loop invariant, and both x and y are integer type. + // TODO: Any_of reduction need not be restricted to integer type only. }; /// The RecurrenceDescriptor is used to identify recurrences variables in a @@ -149,8 +150,8 @@ /// where one of (X, Y) is a loop invariant integer and the other is a PHI /// value. \p Prev specifies the description of an already processed select /// instruction, so its corresponding cmp can be matched to it. - static InstDesc isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi, - Instruction *I, InstDesc &Prev); + static InstDesc isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, Instruction *I, + InstDesc &Prev); /// Returns a struct describing if the instruction is a /// Select(FCmp(X, Y), (Z = X op PHINode), PHINode) instruction pattern. @@ -236,8 +237,8 @@ /// Returns true if the recurrence kind is of the form /// select(cmp(),x,y) where one of (x,y) is loop invariant. - static bool isSelectCmpRecurrenceKind(RecurKind Kind) { - return Kind == RecurKind::SelectICmp || Kind == RecurKind::SelectFCmp; + static bool isAnyOfRecurrenceKind(RecurKind Kind) { + return Kind == RecurKind::IAnyOf || Kind == RecurKind::FAnyOf; } /// 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 @@ -363,14 +363,14 @@ /// Returns the comparison predicate used when expanding a min/max reduction. CmpInst::Predicate getMinMaxReductionPredicate(RecurKind RK); -/// See RecurrenceDescriptor::isSelectCmpPattern for a description of the -/// pattern we are trying to match. In this pattern we are only ever selecting -/// between two values: 1) an initial PHI start value, and 2) a loop invariant -/// value. This function uses \p LoopExitInst to determine 2), which we then use -/// to select between \p Left and \p Right. Any lane value in \p Left that -/// matches 2) will be merged into \p Right. -Value *createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, - Value *Left, Value *Right); +/// See RecurrenceDescriptor::isAnyOfPattern for a description of the pattern we +/// are trying to match. In this pattern, we are only ever selecting between two +/// values: 1) an initial start value \p StartVal of the reduction PHI, and 2) a +/// loop invariant value. If any of lane value in \p Left, \p Right is not equal +/// to \p StartVal, select the loop invariant value. This is done by selecting +/// \p Right iff \p Left is equal to \p StartVal. +Value *createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, RecurKind RK, + Value *Left, Value *Right); /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind. /// The Builder's fast-math-flags must be set to propagate the expected values. @@ -397,13 +397,12 @@ 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, - const TargetTransformInfo *TTI, - Value *Src, - const RecurrenceDescriptor &Desc, - PHINode *OrigPhi); +/// 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, + PHINode *OrigPhi); /// Create a generic target reduction using a recurrence descriptor \p Desc /// The target is queried to determine if intrinsics or shuffle sequences are 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; @@ -411,18 +411,17 @@ // A reduction operation must only have one use of the reduction value. if (!IsAPhi && !IsASelect && !isMinMaxRecurrenceKind(Kind) && - !isSelectCmpRecurrenceKind(Kind) && - hasMultipleUsesOf(Cur, VisitedInsts, 1)) + !isAnyOfRecurrenceKind(Kind) && hasMultipleUsesOf(Cur, VisitedInsts, 1)) return false; // All inputs to a PHI node must be a reduction value. 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; @@ -488,7 +487,7 @@ ((!isa(UI) && !isa(UI) && !isa(UI)) || (!isConditionalRdxPattern(Kind, UI).isRecurrence() && - !isSelectCmpPattern(TheLoop, Phi, UI, IgnoredVal) + !isAnyOfPattern(TheLoop, Phi, UI, IgnoredVal) .isRecurrence() && !isMinMaxPattern(UI, Kind, IgnoredVal).isRecurrence()))) return false; @@ -508,7 +507,7 @@ NumCmpSelectPatternInst != 0) return false; - if (isSelectCmpRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1) + if (isAnyOfRecurrenceKind(Kind) && NumCmpSelectPatternInst != 1) return false; if (IntermediateStore) { @@ -628,8 +627,8 @@ // value if nothing changed (0 in the example above) or the other selected // value (3 in the example above). RecurrenceDescriptor::InstDesc -RecurrenceDescriptor::isSelectCmpPattern(Loop *Loop, PHINode *OrigPhi, - Instruction *I, InstDesc &Prev) { +RecurrenceDescriptor::isAnyOfPattern(Loop *Loop, PHINode *OrigPhi, + Instruction *I, InstDesc &Prev) { // We must handle the select(cmp(),x,y) as a single instruction. Advance to // the select. CmpInst::Predicate Pred; @@ -659,8 +658,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 @@ -803,8 +802,8 @@ case Instruction::FCmp: case Instruction::ICmp: case Instruction::Call: - if (isSelectCmpRecurrenceKind(Kind)) - return isSelectCmpPattern(L, OrigPhi, I, Prev); + if (isAnyOfRecurrenceKind(Kind)) + return isAnyOfPattern(L, OrigPhi, I, Prev); auto HasRequiredFMF = [&]() { if (FuncFMF.noNaNs() && FuncFMF.noSignedZeros()) return true; @@ -897,8 +896,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 +922,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 +1087,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 +1117,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 @@ -937,8 +937,8 @@ } } -Value *llvm::createSelectCmpOp(IRBuilderBase &Builder, Value *StartVal, - RecurKind RK, Value *Left, Value *Right) { +Value *llvm::createAnyOfOp(IRBuilderBase &Builder, Value *StartVal, + RecurKind RK, Value *Left, Value *Right) { if (auto VTy = dyn_cast(Left->getType())) StartVal = Builder.CreateVectorSplat(VTy->getElementCount(), StartVal); Value *Cmp = @@ -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/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -3996,9 +3996,9 @@ if (Op != Instruction::ICmp && Op != Instruction::FCmp) ReducedPartRdx = Builder.CreateBinOp( (Instruction::BinaryOps)Op, RdxPart, ReducedPartRdx, "bin.rdx"); - else if (RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) - ReducedPartRdx = createSelectCmpOp(Builder, ReductionStartValue, RK, - ReducedPartRdx, RdxPart); + else if (RecurrenceDescriptor::isAnyOfRecurrenceKind(RK)) + ReducedPartRdx = createAnyOfOp(Builder, ReductionStartValue, RK, + ReducedPartRdx, RdxPart); else ReducedPartRdx = createMinMaxOp(Builder, RK, ReducedPartRdx, RdxPart); } @@ -5919,7 +5919,7 @@ HasReductions && any_of(Legal->getReductionVars(), [&](auto &Reduction) -> bool { const RecurrenceDescriptor &RdxDesc = Reduction.second; - return RecurrenceDescriptor::isSelectCmpRecurrenceKind( + return RecurrenceDescriptor::isAnyOfRecurrenceKind( RdxDesc.getRecurrenceKind()); }); if (HasSelectCmpReductions) { @@ -9144,8 +9144,8 @@ for (VPReductionPHIRecipe *PhiR : InLoopReductionPhis) { const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor(); RecurKind Kind = RdxDesc.getRecurrenceKind(); - assert(!RecurrenceDescriptor::isSelectCmpRecurrenceKind(Kind) && - "select/cmp reductions are not allowed for in-loop reductions"); + assert(!RecurrenceDescriptor::isAnyOfRecurrenceKind(Kind) && + "AnyOf reductions are not allowed for in-loop reductions"); // Collect the chain of "link" recipes for the reduction starting at PhiR. SetVector Worklist; 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 @@ -14070,8 +14070,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."); } @@ -14159,8 +14159,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,8 +1269,8 @@ Value *Iden = nullptr; RecurKind RK = RdxDesc.getRecurrenceKind(); if (RecurrenceDescriptor::isMinMaxRecurrenceKind(RK) || - RecurrenceDescriptor::isSelectCmpRecurrenceKind(RK)) { - // MinMax reduction have the start value as their identify. + RecurrenceDescriptor::isAnyOfRecurrenceKind(RK)) { + // MinMax and AnyOf reductions have the start value as their identity. if (ScalarPHI) { Iden = StartV; } else { 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 by 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 duplicated. ; 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(