From 280e1df8585e62f0c801de8e4b625a7e73178d85 Mon Sep 17 00:00:00 2001 From: Arnold Schwaighofer Date: Tue, 7 May 2013 21:55:37 +0000 Subject: [PATCH] LoopVectorizer: Improve reduction variable identification The two nested loops were confusing and also conservative in identifying reduction variables. This patch replaces them by a worklist based approach. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@181369 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Vectorize/LoopVectorize.cpp | 216 +++++++++++++-------- test/Transforms/LoopVectorize/reduction.ll | 119 ++++++++++++ 2 files changed, 251 insertions(+), 84 deletions(-) diff --git a/lib/Transforms/Vectorize/LoopVectorize.cpp b/lib/Transforms/Vectorize/LoopVectorize.cpp index ad4a6c7c419..e7da695d503 100644 --- a/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -2870,6 +2870,26 @@ bool LoopVectorizationLegality::canVectorizeMemory() { return true; } +static bool hasMultipleUsesOf(Instruction *I, + SmallPtrSet &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, SmallPtrSet &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) @@ -2888,116 +2908,144 @@ bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi, // This includes users of the reduction, variables (which form a cycle // which ends in the phi node). Instruction *ExitInstruction = 0; - // Indicates that we found a binary operation in our scan. - bool FoundBinOp = false; + // Indicates that we found a reduction operation in our scan. + bool FoundReduxOp = false; - // Iter is our iterator. 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 may have a single - // out-of-block user. The cycle must end with the original PHI. - Instruction *Iter = Phi; + // 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, - // such that we don't stop when we see the phi has two uses (one by the select - // and one by the icmp) and to make sure we only see exactly the two - // instructions. + // to make sure we only see exactly the two instructions. unsigned NumCmpSelectPatternInst = 0; ReductionInstDesc ReduxDesc(false, 0); - // Avoid cycles in the chain. SmallPtrSet VisitedInsts; - while (VisitedInsts.insert(Iter)) { - // If the instruction has no users then this is a broken - // chain and can't be a reduction variable. - if (Iter->use_empty()) + 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; - // Did we find a user inside this loop already ? - bool FoundInBlockUser = false; - // Did we reach the initial PHI node already ? - bool FoundStartPHI = false; + bool IsAPhi = isa(Cur); - // Is this a bin op ? - FoundBinOp |= !isa(Iter); + // A header PHI use other than the original PHI. + if (Cur != Phi && IsAPhi && Cur->getParent() == Phi->getParent()) + return false; - // For each of the *users* of iter. - for (Value::use_iterator it = Iter->use_begin(), e = Iter->use_end(); - it != e; ++it) { - Instruction *U = cast(*it); - // We already know that the PHI is a user. - if (U == Phi) { - FoundStartPHI = true; - continue; - } + // 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 (Value::use_iterator UI = Cur->use_begin(), E = Cur->use_end(); UI != E; + ++UI) { + Instruction *Usr = cast(*UI); // Check if we found the exit user. - BasicBlock *Parent = U->getParent(); + BasicBlock *Parent = Usr->getParent(); if (!TheLoop->contains(Parent)) { // Exit if you find multiple outside users. if (ExitInstruction != 0) return false; - ExitInstruction = Iter; - } - - // We allow in-loop PHINodes which are not the original reduction PHI - // node. If this PHI is the only user of Iter (happens in IF w/ no ELSE - // structure) then don't skip this PHI. - if (isa(Iter) && isa(U) && - U->getParent() != TheLoop->getHeader() && - TheLoop->contains(U) && - Iter->hasNUsesOrMore(2)) + ExitInstruction = Cur; continue; + } - // We can't have multiple inside users except for a combination of - // icmp/select both using the phi. - if (FoundInBlockUser && !NumCmpSelectPatternInst) - return false; - FoundInBlockUser = true; - - // Any reduction instr must be of one of the allowed kinds. - ReduxDesc = isReductionInstr(U, Kind, ReduxDesc); - if (!ReduxDesc.IsReduction) - return false; + // Process instructions only once (termination). + if (VisitedInsts.insert(Usr)) { + if (isa(Usr)) + PHIs.push_back(Usr); + else + NonPHIs.push_back(Usr); + } + // Remember that we completed the cycle. + if (Usr == Phi) + FoundStartPHI = true; + } + Worklist.append(PHIs.begin(), PHIs.end()); + Worklist.append(NonPHIs.begin(), NonPHIs.end()); + } - if (Kind == RK_IntegerMinMax && (isa(U) || isa(U))) - ++NumCmpSelectPatternInst; - if (Kind == RK_FloatMinMax && (isa(U) || isa(U))) - ++NumCmpSelectPatternInst; + // 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; - // Reductions of instructions such as Div, and Sub is only - // possible if the LHS is the reduction variable. - if (!U->isCommutative() && !isa(U) && !isa(U) && - !isa(U) && !isa(U) && U->getOperand(0) != Iter) - return false; + if (!FoundStartPHI || !FoundReduxOp || !ExitInstruction) + return false; - Iter = ReduxDesc.PatternLastInst; - } + // 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 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; + // This instruction is allowed to have out-of-loop users. + AllowedExit.insert(ExitInstruction); - // 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. - if (FoundStartPHI) { - // 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 FoundBinOp && 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 false; + return true; } /// Returns true if the instruction is a Select(ICmp(X, Y), X, Y) instruction diff --git a/test/Transforms/LoopVectorize/reduction.ll b/test/Transforms/LoopVectorize/reduction.ll index 08b7b27e425..286b736c926 100644 --- a/test/Transforms/LoopVectorize/reduction.ll +++ b/test/Transforms/LoopVectorize/reduction.ll @@ -323,3 +323,122 @@ for.end: ; preds = %for.body, %entry %x.0.lcssa = phi i32 [ 0, %entry ], [ %sub, %for.body ] ret i32 %x.0.lcssa } + +; We can vectorize conditional reductions with multi-input phis. +; CHECK: reduction_conditional +; CHECK: fadd <4 x float> + +define float @reduction_conditional(float* %A, float* %B, float* %C, float %S) { +entry: + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ] + %sum.033 = phi float [ %S, %entry ], [ %sum.1, %for.inc ] + %arrayidx = getelementptr inbounds float* %A, i64 %indvars.iv + %0 = load float* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds float* %B, i64 %indvars.iv + %1 = load float* %arrayidx2, align 4 + %cmp3 = fcmp ogt float %0, %1 + br i1 %cmp3, label %if.then, label %for.inc + +if.then: + %cmp6 = fcmp ogt float %1, 1.000000e+00 + br i1 %cmp6, label %if.then8, label %if.else + +if.then8: + %add = fadd fast float %sum.033, %0 + br label %for.inc + +if.else: + %cmp14 = fcmp ogt float %0, 2.000000e+00 + br i1 %cmp14, label %if.then16, label %for.inc + +if.then16: + %add19 = fadd fast float %sum.033, %1 + br label %for.inc + +for.inc: + %sum.1 = phi float [ %add, %if.then8 ], [ %add19, %if.then16 ], [ %sum.033, %if.else ], [ %sum.033, %for.body ] + %indvars.iv.next = add i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp ne i32 %lftr.wideiv, 128 + br i1 %exitcond, label %for.body, label %for.end + +for.end: + %sum.1.lcssa = phi float [ %sum.1, %for.inc ] + ret float %sum.1.lcssa +} + +; We can't vectorize reductions with phi inputs from outside the reduction. +; CHECK: noreduction_phi +; CHECK-NOT: fadd <4 x float> +define float @noreduction_phi(float* %A, float* %B, float* %C, float %S) { +entry: + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ] + %sum.033 = phi float [ %S, %entry ], [ %sum.1, %for.inc ] + %arrayidx = getelementptr inbounds float* %A, i64 %indvars.iv + %0 = load float* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds float* %B, i64 %indvars.iv + %1 = load float* %arrayidx2, align 4 + %cmp3 = fcmp ogt float %0, %1 + br i1 %cmp3, label %if.then, label %for.inc + +if.then: + %cmp6 = fcmp ogt float %1, 1.000000e+00 + br i1 %cmp6, label %if.then8, label %if.else + +if.then8: + %add = fadd fast float %sum.033, %0 + br label %for.inc + +if.else: + %cmp14 = fcmp ogt float %0, 2.000000e+00 + br i1 %cmp14, label %if.then16, label %for.inc + +if.then16: + %add19 = fadd fast float %sum.033, %1 + br label %for.inc + +for.inc: + %sum.1 = phi float [ %add, %if.then8 ], [ %add19, %if.then16 ], [ 0.000000e+00, %if.else ], [ %sum.033, %for.body ] + %indvars.iv.next = add i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp ne i32 %lftr.wideiv, 128 + br i1 %exitcond, label %for.body, label %for.end + +for.end: + %sum.1.lcssa = phi float [ %sum.1, %for.inc ] + ret float %sum.1.lcssa +} + +; We can't vectorize reductions that feed another header PHI. +; CHECK: noredux_header_phi +; CHECK-NOT: fadd <4 x float> + +define float @noredux_header_phi(float* %A, float* %B, float* %C, float %S) { +entry: + br label %for.body + +for.body: + %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ] + %sum2.09 = phi float [ 0.000000e+00, %entry ], [ %add1, %for.body ] + %sum.08 = phi float [ %S, %entry ], [ %add, %for.body ] + %arrayidx = getelementptr inbounds float* %B, i64 %indvars.iv + %0 = load float* %arrayidx, align 4 + %add = fadd fast float %sum.08, %0 + %add1 = fadd fast float %sum2.09, %add + %indvars.iv.next = add i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp ne i32 %lftr.wideiv, 128 + br i1 %exitcond, label %for.body, label %for.end + +for.end: + %add1.lcssa = phi float [ %add1, %for.body ] + %add.lcssa = phi float [ %add, %for.body ] + %add2 = fadd fast float %add.lcssa, %add1.lcssa + ret float %add2 +} -- 2.34.1