Index: llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp
===================================================================
--- llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp
+++ llvm/lib/Transforms/Vectorize/LoopVectorizationLegality.cpp
@@ -668,6 +668,7 @@
 
         if (RecurrenceDescriptor::isFirstOrderRecurrence(Phi, TheLoop,
                                                          SinkAfter, DT)) {
+          AllowedExit.insert(Phi);
           FirstOrderRecurrences.insert(Phi);
           continue;
         }
Index: llvm/test/Transforms/LoopVectorize/optsize.ll
===================================================================
--- llvm/test/Transforms/LoopVectorize/optsize.ll
+++ llvm/test/Transforms/LoopVectorize/optsize.ll
@@ -121,6 +121,27 @@
   br i1 %cmp26, label %for.body29, label %for.cond.cleanup28
 }
 
+; PR45526: don't vectorize with fold-tail if first-order-recurrence is live-out.
+;
+define i32 @pr45526() optsize {
+;
+; CHECK-LABEL: @pr45526
+; CHECK-NOT: <
+;
+entry:
+  br label %loop
+
+loop:
+  %piv = phi i32 [ 0, %entry ], [ %pivPlus1, %loop ]
+  %for = phi i32 [ 5, %entry ], [ %pivPlus1, %loop ]
+  %pivPlus1 = add nuw nsw i32 %piv, 1
+  %cond = icmp ult i32 %piv, 510
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret i32 %for
+}
+
 !llvm.module.flags = !{!0}
 !0 = !{i32 1, !"ProfileSummary", !1}
 !1 = !{!2, !3, !4, !5, !6, !7, !8, !9}