Index: include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h =================================================================== --- include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h +++ include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h @@ -278,6 +278,12 @@ /// Returns True if Phi is a first-order recurrence in this loop. bool isFirstOrderRecurrence(const PHINode *Phi); + /// Returns True if the value which is not defined in loop header (and hence + /// not an induction/reduction/first order recurrence) is allowed outside the loop. + bool isAllowedNonHeaderExit(const Value *V) { + return AllowedNonHdrExits.count(V); + } + /// Return true if the block BB needs to be predicated in order for the loop /// to be vectorized. bool blockNeedsPredication(BasicBlock *BB); @@ -455,6 +461,9 @@ /// vars which can be accessed from outside the loop. SmallPtrSet AllowedExit; + /// Allowed non header phis which can be accessed from outside the loop. + SmallPtrSet AllowedNonHdrExits; + /// Can we assume the absence of NaNs. bool HasFunNoNaNAttr = false; Index: lib/Transforms/Vectorize/LoopVectorizationLegality.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorizationLegality.cpp +++ lib/Transforms/Vectorize/LoopVectorizationLegality.cpp @@ -601,6 +601,17 @@ // identified reduction value with an outside user. if (!hasOutsideLoopUser(TheLoop, Phi, AllowedExit)) continue; + // Outside users for phi where the phi does not have a cyclic + // dependence with a header phi (reduction/induction/first order + // recurrences). We conservatively check this by checking if the only + // user of the phi is outside the loop. + // TODO: The two incoming value check is to make sure we can + // if-convert the phi. May not be needed. + if (Phi->getNumIncomingValues() == 2 && Phi->hasNUses(1)) { + AllowedExit.insert(Phi); + AllowedNonHdrExits.insert(Phi); + continue; + } ORE->emit(createMissedAnalysis("NeitherInductionNorReduction", Phi) << "value could not be identified as " "an induction or reduction variable"); Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -3720,9 +3720,24 @@ void InnerLoopVectorizer::fixLCSSAPHIs() { for (PHINode &LCSSAPhi : LoopExitBlock->phis()) { if (LCSSAPhi.getNumIncomingValues() == 1) { - assert(OrigLoop->isLoopInvariant(LCSSAPhi.getIncomingValue(0)) && - "Incoming value isn't loop invariant"); - LCSSAPhi.addIncoming(LCSSAPhi.getIncomingValue(0), LoopMiddleBlock); + auto *IncomingValue = LCSSAPhi.getIncomingValue(0); + if (!Legal->isAllowedNonHeaderExit(IncomingValue)) { + assert(OrigLoop->isLoopInvariant(LCSSAPhi.getIncomingValue(0)) && + "Incoming value isn't loop invariant"); + LCSSAPhi.addIncoming(LCSSAPhi.getIncomingValue(0), LoopMiddleBlock); + } else { + Value *lastValueOfVectorizedLoop = + getOrCreateVectorValue(IncomingValue, UF - 1); + Value *ExtractForPreviousUsedOutsideLoop = lastValueOfVectorizedLoop; + if (VF > 1) { + Builder.SetInsertPoint(LoopMiddleBlock->getTerminator()); + ExtractForPreviousUsedOutsideLoop = Builder.CreateExtractElement( + lastValueOfVectorizedLoop, Builder.getInt32(VF - 1), + "vector.extract.outside.phi"); + } + LCSSAPhi.addIncoming(ExtractForPreviousUsedOutsideLoop, + LoopMiddleBlock); + } } } } Index: test/Transforms/LoopVectorize/no_outside_user.ll =================================================================== --- test/Transforms/LoopVectorize/no_outside_user.ll +++ test/Transforms/LoopVectorize/no_outside_user.ll @@ -1,7 +1,5 @@ ; RUN: opt -S -loop-vectorize -force-vector-interleave=1 -force-vector-width=2 < %s 2>&1 | FileCheck %s -; CHECK: remark: {{.*}}: loop not vectorized: value could not be identified as an induction or reduction variable - target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128" @f = common global i32 0, align 4 @@ -11,11 +9,14 @@ @b = common global i32 0, align 4 @e = common global i32 0, align 4 -; We used to vectorize this loop. But it has a value that is used outside of the +; It has a value that is used outside of the ; and is not a recognized reduction variable "tmp17". +; However, tmp17 does not have a cyclic dependence with any header phis. So, the +; iteration dependence distance for tmp17 can also be widened to VF (just like +; we do for reduction/induction). ; CHECK-LABEL: @main( -; CHECK-NOT: <2 x i32> +; CHECK: <2 x i32> define i32 @main() { bb: @@ -40,3 +41,68 @@ %.lcssa = phi i32 [ %tmp17, %bb16 ] ret i32 %.lcssa } + +; non-hdr phi depends on header phi. +; CHECK-LABEL: @test2( +; CHECK: <2 x i32> +define i32 @test2() { +bb: + %b.promoted = load i32, i32* @b, align 4 + br label %.lr.ph.i + +.lr.ph.i: + %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ] + %tmp2 = icmp sgt i32 %tmp8, 10 + br i1 %tmp2, label %bb16, label %bb10 + +bb10: + br label %bb16 + +bb16: + %tmp17 = phi i32 [ %tmp8, %bb10 ], [ 1, %.lr.ph.i ] + %tmp18 = add nsw i32 %tmp8, 1 + %tmp19 = icmp slt i32 %tmp18, 4 + br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit + +f1.exit.loopexit: + %.lcssa = phi i32 [ %tmp17, %bb16 ] + ret i32 %.lcssa +} + +; non hdr phi that depends on reduction and is used outside the loop. +; FIXME: Because of the lcssa creation for tmp17, we will have two uses of tmp17 +; outside the loop. We need to extend the above process to multiple uses. +define i32 @reduction_sum(i32 %n, i32* noalias nocapture %A, i32* noalias nocapture %B) nounwind uwtable readonly noinline ssp { +entry: + %c1 = icmp sgt i32 %n, 0 + br i1 %c1, label %header, label %._crit_edge + +header: ; preds = %0, %.lr.ph + %indvars.iv = phi i64 [ %indvars.iv.next, %bb16 ], [ 0, %entry ] + %sum.02 = phi i32 [ %c9, %bb16 ], [ 0, %entry ] + %c2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %c3 = load i32, i32* %c2, align 4 + %c4 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv + %c5 = load i32, i32* %c4, align 4 + %tmp2 = icmp sgt i32 %sum.02, 10 + br i1 %tmp2, label %bb16, label %bb10 + +bb10: + br label %bb16 + +bb16: + %tmp17 = phi i32 [ %sum.02, %bb10 ], [ 1, %header ] + %c6 = trunc i64 %indvars.iv to i32 + %c7 = add i32 %sum.02, %c6 + %c8 = add i32 %c7, %c3 + %c9 = add i32 %c8, %c5 + %indvars.iv.next = add i64 %indvars.iv, 1 + %lftr.wideiv = trunc i64 %indvars.iv.next to i32 + %exitcond = icmp eq i32 %lftr.wideiv, %n + br i1 %exitcond, label %._crit_edge, label %header + +._crit_edge: ; preds = %.lr.ph, %0 + %sum.0.lcssa = phi i32 [ 0, %entry ], [ %c9, %bb16 ] + %nonhdr.lcssa = phi i32 [ 1, %entry], [ %tmp17, %bb16 ] + ret i32 %sum.0.lcssa +}