[LV] Fix insertion point for shuffle vectors in first order recurrence

[anna]

Summary

In first order recurrence vectorization, when the previous value is a phi node, we need to
set the insertion point to the first non-phi node.
We can have the previous value being a phi node, due to the generation of new
IVs as part of trunc optimization [1].

[1] https://reviews.llvm.org/rL294967

[mkuper]

LGTM

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::fixFirstOrderRecurrence(PHINode *Phi) {
   auto *VecPhi = Builder.CreatePHI(VectorInit->getType(), 2, "vector.recur");
   VecPhi->addIncoming(VectorInit, LoopVectorPreHeader);
 
   // Get the vectorized previous value.
   auto &PreviousParts = getVectorValue(Previous);
 
   // Set the insertion point after the previous value if it is an instruction.
   // Note that the previous value may have been constant-folded so it is not
-  // guaranteed to be an instruction in the vector loop.
-  if (LI->getLoopFor(LoopVectorBody)->isLoopInvariant(PreviousParts[UF - 1]))
+  // guaranteed to be an instruction in the vector loop. Also, if the previous
+  // value is a phi node, we should insert after all the phi nodes to avoid
+  // breaking basic block verification.
+  if (LI->getLoopFor(LoopVectorBody)->isLoopInvariant(PreviousParts[UF - 1]) ||
+      isa<PHINode>(PreviousParts[UF - 1]))
     Builder.SetInsertPoint(&*LoopVectorBody->getFirstInsertionPt());
   else
     Builder.SetInsertPoint(
         &*++BasicBlock::iterator(cast<Instruction>(PreviousParts[UF - 1])));
 
   // We will construct a vector for the recurrence by combining the values for
   // the current and previous iterations. This is the required shuffle mask.
   SmallVector<Constant *, 8> ShuffleMask(VF);

llvm/trunk/test/Transforms/LoopVectorize/induction.ll

for.inc:
   %i.next = add nsw i32 %i, 1
   %cond = icmp eq i32 %i.next, 0
   br i1 %cond, label %for.end, label %for.body
 
 for.end:
   %tmp7 = phi i32 [ %tmp6, %for.inc ]
   ret i32 %tmp7
 }
+
+; Ensure that the shuffle vector for first order recurrence is inserted
+; correctly after all the phis. These new phis correspond to new IVs 
+; that are generated by optimizing non-free truncs of IVs to IVs themselves 
+define i64 @trunc_with_first_order_recurrence() {
+; CHECK-LABEL: trunc_with_first_order_recurrence
+; CHECK-LABEL: vector.body:
+; CHECK-NEXT:    %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; CHECK-NEXT:    %vec.phi = phi <2 x i64>
+; CHECK-NEXT:    %vec.ind = phi <2 x i64> [ <i64 1, i64 2>, %vector.ph ], [ %vec.ind.next, %vector.body ]
+; CHECK-NEXT:    %vec.ind2 = phi <2 x i32> [ <i32 1, i32 2>, %vector.ph ], [ %vec.ind.next3, %vector.body ]
+; CHECK-NEXT:    %vector.recur = phi <2 x i32> [ <i32 undef, i32 42>, %vector.ph ], [ %vec.ind5, %vector.body ]
+; CHECK-NEXT:    %vec.ind5 = phi <2 x i32> [ <i32 1, i32 2>, %vector.ph ], [ %vec.ind.next6, %vector.body ]
+; CHECK-NEXT:    %vec.ind7 = phi <2 x i32> [ <i32 1, i32 2>, %vector.ph ], [ %vec.ind.next8, %vector.body ]
+; CHECK-NEXT:    shufflevector <2 x i32> %vector.recur, <2 x i32> %vec.ind5, <2 x i32> <i32 1, i32 2>
+entry:
+  br label %loop
+
+exit:                                        ; preds = %loop
+  %.lcssa = phi i64 [ %c23, %loop ]
+  ret i64 %.lcssa
+
+loop:                                         ; preds = %loop, %entry
+  %c5 = phi i64 [ %c23, %loop ], [ 0, %entry ]
+  %indvars.iv = phi i64 [ %indvars.iv.next, %loop ], [ 1, %entry ]
+  %x = phi i32 [ %c24, %loop ], [ 1, %entry ]
+  %y = phi i32 [ %c6, %loop ], [ 42, %entry ]
+  %c6 = trunc i64 %indvars.iv to i32
+  %c8 = mul i32 %x, %c6
+  %c9 = add i32 %c8, 42
+  %c10 = add i32 %y, %c6
+  %c11 = add i32 %c10, %c9
+  %c12 = sext i32 %c11 to i64
+  %c13 = add i64 %c5, %c12
+  %indvars.iv.tr = trunc i64 %indvars.iv to i32
+  %c14 = shl i32 %indvars.iv.tr, 1
+  %c15 = add i32 %c9, %c14
+  %c16 = sext i32 %c15 to i64
+  %c23 = add i64 %c13, %c16
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %c24 = add nuw nsw i32 %x, 1
+  %exitcond.i = icmp eq i64 %indvars.iv.next, 114
+  br i1 %exitcond.i, label %exit, label %loop
+
+}