LoopVectorizer: Disallow reductions whose header phi is used outside the loop

If an outside loop user of the reduction value uses the header phi node we
cannot just reduce the vectorized phi value in the vector code epilog because
we would loose VF-1 reductions.

lp:
  p = phi (0, lv)
  lv = lv + 1
  ...
  brcond , lp, outside

outside:
  usr = add 0, p

(Say the loop iterates two times, the value of p coming out of the loop is one).

We cannot just transform this to:

vlp:
  p = phi (<0,0>, lv)
  lv = lv + <1,1>
  ..
  brcond , lp, outside

outside:
  p_reduced = p[0] + [1];
  usr = add 0, p_reduced

(Because the original loop iterated two times the vectorized loop would iterate
one time, but p_reduced ends up being zero instead of one).

We would have to execute VF-1 iterations in the scalar remainder loop in such
cases. For now, just disable vectorization.

PR16522

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@186256 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 31 insertions, 2 deletions

diff --git a/lib/Transforms/Vectorize/LoopVectorize.cpp b/lib/Transforms/Vectorize/LoopVectorize.cpp
index 0d910d1559..4f6ab069b2 100644
--- a/lib/Transforms/Vectorize/LoopVectorize.cpp
+++ b/lib/Transforms/Vectorize/LoopVectorize.cpp
@@ -3818,9 +3818,13 @@ bool LoopVectorizationLegality::AddReductionVar(PHINode *Phi,
       // Check if we found the exit user.
       BasicBlock *Parent = Usr->getParent();
       if (!TheLoop->contains(Parent)) {
-        // Exit if you find multiple outside users.
-        if (ExitInstruction != 0)
+        // 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 != 0 || Cur == Phi)
           return false;
+
         ExitInstruction = Cur;
         continue;
       }
diff --git a/test/Transforms/LoopVectorize/reduction.ll b/test/Transforms/LoopVectorize/reduction.ll
index 286b736c92..fbc584994f 100644
--- a/test/Transforms/LoopVectorize/reduction.ll
+++ b/test/Transforms/LoopVectorize/reduction.ll
@@ -442,3 +442,28 @@ for.end:
   %add2 = fadd fast float %add.lcssa, %add1.lcssa
   ret float %add2
 }
+
+
+; When vectorizing a reduction whose loop header phi value is used outside the
+; loop special care must be taken. Otherwise, the reduced value feeding into the
+; outside user misses a few iterations (VF-1) of the loop.
+; PR16522
+
+; CHECK: @phivalueredux
+; CHECK-NOT: x i32>
+
+define i32 @phivalueredux(i32 %p) {
+entry:
+  br label %for.body
+
+for.body:
+  %t.03 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %p.addr.02 = phi i32 [ %p, %entry ], [ %xor, %for.body ]
+  %xor = xor i32 %p.addr.02, -1
+  %inc = add nsw i32 %t.03, 1
+  %exitcond = icmp eq i32 %inc, 16
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+  ret i32 %p.addr.02
+}