; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes=loop-vectorize < %s -S -o - | FileCheck %s

target datalayout = "e-m:e-p:32:32-Fi8-i64:64-v128:64:128-a:0:32-n32-S64"
target triple = "thumbv8.1m.main-arm-none-eabi"

; Fixed order recurrences currently require a shuffle that is expensive to
; codegenerate. These examples should not vectorize.

define void @firstorderrec(ptr nocapture noundef readonly %x, ptr noalias nocapture noundef writeonly %y, i32 noundef %n) #0 {
; CHECK-LABEL: @firstorderrec(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP18:%.*]] = icmp sgt i32 [[N:%.*]], 1
; CHECK-NEXT:    br i1 [[CMP18]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
; CHECK:       for.body.preheader:
; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT:    [[DOTPRE:%.*]] = load i8, ptr [[X:%.*]], align 1
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.cond.cleanup.loopexit:
; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    ret void
; CHECK:       for.body:
; CHECK-NEXT:    [[TMP0:%.*]] = phi i8 [ [[DOTPRE]], [[FOR_BODY_PREHEADER]] ], [ [[TMP1:%.*]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 1, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[ARRAYIDX4:%.*]] = getelementptr inbounds i8, ptr [[X]], i64 [[INDVARS_IV]]
; CHECK-NEXT:    [[TMP1]] = load i8, ptr [[ARRAYIDX4]], align 1
; CHECK-NEXT:    [[ADD7:%.*]] = add i8 [[TMP1]], [[TMP0]]
; CHECK-NEXT:    [[ARRAYIDX10:%.*]] = getelementptr inbounds i8, ptr [[Y:%.*]], i64 [[INDVARS_IV]]
; CHECK-NEXT:    store i8 [[ADD7]], ptr [[ARRAYIDX10]], align 1
; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]]
;
entry:
  %cmp18 = icmp sgt i32 %n, 1
  br i1 %cmp18, label %for.body.preheader, label %for.cond.cleanup

for.body.preheader:                               ; preds = %entry
  %wide.trip.count = zext i32 %n to i64
  %.pre = load i8, ptr %x, align 1
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body, %entry
  ret void

for.body:                                         ; preds = %for.body.preheader, %for.body
  %0 = phi i8 [ %.pre, %for.body.preheader ], [ %1, %for.body ]
  %indvars.iv = phi i64 [ 1, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
  %arrayidx4 = getelementptr inbounds i8, ptr %x, i64 %indvars.iv
  %1 = load i8, ptr %arrayidx4, align 1
  %add7 = add i8 %1, %0
  %arrayidx10 = getelementptr inbounds i8, ptr %y, i64 %indvars.iv
  store i8 %add7, ptr %arrayidx10, align 1
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

define void @thirdorderrec(ptr nocapture noundef readonly %x, ptr noalias nocapture noundef writeonly %y, i32 noundef %n) #0 {
; CHECK-LABEL: @thirdorderrec(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[CMP38:%.*]] = icmp sgt i32 [[N:%.*]], 3
; CHECK-NEXT:    br i1 [[CMP38]], label [[FOR_BODY_PREHEADER:%.*]], label [[FOR_COND_CLEANUP:%.*]]
; CHECK:       for.body.preheader:
; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext i32 [[N]] to i64
; CHECK-NEXT:    [[DOTPRE:%.*]] = load i8, ptr [[X:%.*]], align 1
; CHECK-NEXT:    [[ARRAYIDX5_PHI_TRANS_INSERT:%.*]] = getelementptr inbounds i8, ptr [[X]], i64 1
; CHECK-NEXT:    [[DOTPRE44:%.*]] = load i8, ptr [[ARRAYIDX5_PHI_TRANS_INSERT]], align 1
; CHECK-NEXT:    [[ARRAYIDX12_PHI_TRANS_INSERT:%.*]] = getelementptr inbounds i8, ptr [[X]], i64 2
; CHECK-NEXT:    [[DOTPRE45:%.*]] = load i8, ptr [[ARRAYIDX12_PHI_TRANS_INSERT]], align 1
; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
; CHECK:       for.cond.cleanup.loopexit:
; CHECK-NEXT:    br label [[FOR_COND_CLEANUP]]
; CHECK:       for.cond.cleanup:
; CHECK-NEXT:    ret void
; CHECK:       for.body:
; CHECK-NEXT:    [[TMP0:%.*]] = phi i8 [ [[DOTPRE45]], [[FOR_BODY_PREHEADER]] ], [ [[TMP3:%.*]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[TMP1:%.*]] = phi i8 [ [[DOTPRE44]], [[FOR_BODY_PREHEADER]] ], [ [[TMP0]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[TMP2:%.*]] = phi i8 [ [[DOTPRE]], [[FOR_BODY_PREHEADER]] ], [ [[TMP1]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ 3, [[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], [[FOR_BODY]] ]
; CHECK-NEXT:    [[ADD8:%.*]] = add i8 [[TMP1]], [[TMP2]]
; CHECK-NEXT:    [[ADD15:%.*]] = add i8 [[ADD8]], [[TMP0]]
; CHECK-NEXT:    [[ARRAYIDX18:%.*]] = getelementptr inbounds i8, ptr [[X]], i64 [[INDVARS_IV]]
; CHECK-NEXT:    [[TMP3]] = load i8, ptr [[ARRAYIDX18]], align 1
; CHECK-NEXT:    [[ADD21:%.*]] = add i8 [[ADD15]], [[TMP3]]
; CHECK-NEXT:    [[ARRAYIDX24:%.*]] = getelementptr inbounds i8, ptr [[Y:%.*]], i64 [[INDVARS_IV]]
; CHECK-NEXT:    store i8 [[ADD21]], ptr [[ARRAYIDX24]], align 1
; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i64 [[INDVARS_IV_NEXT]], [[WIDE_TRIP_COUNT]]
; CHECK-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP_LOOPEXIT:%.*]], label [[FOR_BODY]]
;
entry:
  %cmp38 = icmp sgt i32 %n, 3
  br i1 %cmp38, label %for.body.preheader, label %for.cond.cleanup

for.body.preheader:                               ; preds = %entry
  %wide.trip.count = zext i32 %n to i64
  %.pre = load i8, ptr %x, align 1
  %arrayidx5.phi.trans.insert = getelementptr inbounds i8, ptr %x, i64 1
  %.pre44 = load i8, ptr %arrayidx5.phi.trans.insert, align 1
  %arrayidx12.phi.trans.insert = getelementptr inbounds i8, ptr %x, i64 2
  %.pre45 = load i8, ptr %arrayidx12.phi.trans.insert, align 1
  br label %for.body

for.cond.cleanup:                                 ; preds = %for.body, %entry
  ret void

for.body:                                         ; preds = %for.body.preheader, %for.body
  %0 = phi i8 [ %.pre45, %for.body.preheader ], [ %3, %for.body ]
  %1 = phi i8 [ %.pre44, %for.body.preheader ], [ %0, %for.body ]
  %2 = phi i8 [ %.pre, %for.body.preheader ], [ %1, %for.body ]
  %indvars.iv = phi i64 [ 3, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
  %add8 = add i8 %1, %2
  %add15 = add i8 %add8, %0
  %arrayidx18 = getelementptr inbounds i8, ptr %x, i64 %indvars.iv
  %3 = load i8, ptr %arrayidx18, align 1
  %add21 = add i8 %add15, %3
  %arrayidx24 = getelementptr inbounds i8, ptr %y, i64 %indvars.iv
  store i8 %add21, ptr %arrayidx24, align 1
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
}

attributes #0 = { "target-features"="+mve" }