; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt -passes='loop(loop-idiom)' < %s -S | FileCheck %s

declare void @other()
declare void @use(ptr)
declare void @usei(i32)
declare void @usel(i64)

; size_t basic_strlen(const char* str) {
;     while (*str != '\0') {
;         ++str;
;     }
;     return str - base;
; }
define i64 @valid_basic_strlen(ptr %str) {
; CHECK-LABEL: define i64 @valid_basic_strlen(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[STR]])
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[STR]], i64 [[STRLEN]]
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR_ADDR_0]], align 1
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    br i1 true, label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[SCEVGEP]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    ret i64 [[SUB_PTR_SUB]]
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %0 = load i8, ptr %str.addr.0, align 1
  %cmp.not = icmp eq i8 %0, 0
  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 1
  br i1 %cmp.not, label %while.end, label %while.cond

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}

; int valid_basic_strlen_rotated(const char* str) {
;     const char* base = str;
;     if (!*str) return 0;
;     do {
;         ++str;
;     } while (*str);
;     return str - base;
; }
define i32 @valid_basic_strlen_rotated(ptr %str) {
; CHECK-LABEL: define i32 @valid_basic_strlen_rotated(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    br i1 [[TOBOOL_NOT]], label %[[CLEANUP:.*]], label %[[DO_BODY_PREHEADER:.*]]
; CHECK:       [[DO_BODY_PREHEADER]]:
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[STR]], i64 1
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[SCEVGEP]])
; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[STRLEN]], 1
; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[STR]], i64 [[TMP1]]
; CHECK-NEXT:    br label %[[DO_BODY:.*]]
; CHECK:       [[DO_BODY]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[INCDEC_PTR:%.*]], %[[DO_BODY]] ], [ [[STR]], %[[DO_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr inbounds nuw i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[INCDEC_PTR]], align 1
; CHECK-NEXT:    [[TOBOOL1_NOT:%.*]] = icmp eq i8 [[TMP2]], 0
; CHECK-NEXT:    br i1 true, label %[[DO_END:.*]], label %[[DO_BODY]]
; CHECK:       [[DO_END]]:
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[SCEVGEP1]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    [[CONV:%.*]] = trunc i64 [[SUB_PTR_SUB]] to i32
; CHECK-NEXT:    br label %[[CLEANUP]]
; CHECK:       [[CLEANUP]]:
; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CONV]], %[[DO_END]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    ret i32 [[RETVAL_0]]
;
entry:
  %0 = load i8, ptr %str, align 1
  %tobool.not = icmp eq i8 %0, 0
  br i1 %tobool.not, label %cleanup, label %do.body

do.body:
  %str.addr.0 = phi ptr [ %incdec.ptr, %do.body ], [ %str, %entry ]
  %incdec.ptr = getelementptr inbounds nuw i8, ptr %str.addr.0, i64 1
  %1 = load i8, ptr %incdec.ptr, align 1
  %tobool1.not = icmp eq i8 %1, 0
  br i1 %tobool1.not, label %do.end, label %do.body

do.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %incdec.ptr to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  %conv = trunc i64 %sub.ptr.sub to i32
  br label %cleanup

cleanup:
  %retval.0 = phi i32 [ %conv, %do.end ], [ 0, %entry ]
  ret i32 %retval.0
}

; int valid_strlen_with_aux_indvar(const char* str) {
;   int count = 0;
;   int count_offset = -10;
;   int count_multiple = 0;
;
;   while (*str) {
;     ++str;
;     ++count;
;     ++count_offset;
;     count_multiple += 2;
;     ++foo;
;   }
;
;   usei(count);
;   usei(count_offset);
;   usei(count_multiple);
;   use(str);
;   use(foo);
; }
define dso_local void @valid_strlen_with_aux_indvar(ptr noundef %str, ptr noundef %foo) local_unnamed_addr {
; CHECK-LABEL: define dso_local void @valid_strlen_with_aux_indvar(
; CHECK-SAME: ptr noundef [[STR:%.*]], ptr noundef [[FOO:%.*]]) local_unnamed_addr {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT9:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    br i1 [[TOBOOL_NOT9]], label %[[WHILE_END:.*]], label %[[WHILE_BODY_PREHEADER:.*]]
; CHECK:       [[WHILE_BODY_PREHEADER]]:
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[STR]], i64 1
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[SCEVGEP]])
; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[STRLEN]], 1
; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[STR]], i64 [[TMP1]]
; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[STRLEN]] to i32
; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 1
; CHECK-NEXT:    [[TMP4:%.*]] = trunc i64 [[STRLEN]] to i32
; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[TMP4]], -9
; CHECK-NEXT:    [[TMP6:%.*]] = trunc i64 [[STRLEN]] to i32
; CHECK-NEXT:    [[TMP7:%.*]] = shl i32 [[TMP6]], 1
; CHECK-NEXT:    [[TMP8:%.*]] = add i32 [[TMP7]], 2
; CHECK-NEXT:    [[TMP9:%.*]] = add i64 [[STRLEN]], 1
; CHECK-NEXT:    [[SCEVGEP2:%.*]] = getelementptr i8, ptr [[FOO]], i64 [[TMP9]]
; CHECK-NEXT:    br label %[[WHILE_BODY:.*]]
; CHECK:       [[WHILE_BODY]]:
; CHECK-NEXT:    [[COUNT_MULTIPLE_014:%.*]] = phi i32 [ [[ADD:%.*]], %[[WHILE_BODY]] ], [ 0, %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[COUNT_OFFSET_013:%.*]] = phi i32 [ [[INC1:%.*]], %[[WHILE_BODY]] ], [ -10, %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[COUNT_012:%.*]] = phi i32 [ [[INC:%.*]], %[[WHILE_BODY]] ], [ 0, %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[FOO_ADDR_011:%.*]] = phi ptr [ [[INCDEC_PTR2:%.*]], %[[WHILE_BODY]] ], [ [[FOO]], %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[STR_ADDR_010:%.*]] = phi ptr [ [[INCDEC_PTR:%.*]], %[[WHILE_BODY]] ], [ [[STR]], %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr inbounds nuw i8, ptr [[STR_ADDR_010]], i64 1
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[COUNT_012]], 1
; CHECK-NEXT:    [[INC1]] = add nsw i32 [[COUNT_OFFSET_013]], 1
; CHECK-NEXT:    [[ADD]] = add nuw nsw i32 [[COUNT_MULTIPLE_014]], 2
; CHECK-NEXT:    [[INCDEC_PTR2]] = getelementptr inbounds nuw i8, ptr [[FOO_ADDR_011]], i64 1
; CHECK-NEXT:    [[TMP10:%.*]] = load i8, ptr [[INCDEC_PTR]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP10]], 0
; CHECK-NEXT:    br i1 true, label %[[WHILE_END_LOOPEXIT:.*]], label %[[WHILE_BODY]]
; CHECK:       [[WHILE_END_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[WHILE_END]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[STR_ADDR_0_LCSSA:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[SCEVGEP1]], %[[WHILE_END_LOOPEXIT]] ]
; CHECK-NEXT:    [[FOO_ADDR_0_LCSSA:%.*]] = phi ptr [ [[FOO]], %[[ENTRY]] ], [ [[SCEVGEP2]], %[[WHILE_END_LOOPEXIT]] ]
; CHECK-NEXT:    [[COUNT_0_LCSSA:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[TMP3]], %[[WHILE_END_LOOPEXIT]] ]
; CHECK-NEXT:    [[COUNT_OFFSET_0_LCSSA:%.*]] = phi i32 [ -10, %[[ENTRY]] ], [ [[TMP5]], %[[WHILE_END_LOOPEXIT]] ]
; CHECK-NEXT:    [[COUNT_MULTIPLE_0_LCSSA:%.*]] = phi i32 [ 0, %[[ENTRY]] ], [ [[TMP8]], %[[WHILE_END_LOOPEXIT]] ]
; CHECK-NEXT:    tail call void @usei(i32 noundef [[COUNT_0_LCSSA]])
; CHECK-NEXT:    tail call void @usei(i32 noundef [[COUNT_OFFSET_0_LCSSA]])
; CHECK-NEXT:    tail call void @usei(i32 noundef [[COUNT_MULTIPLE_0_LCSSA]])
; CHECK-NEXT:    tail call void @use(ptr noundef nonnull [[STR_ADDR_0_LCSSA]])
; CHECK-NEXT:    tail call void @use(ptr noundef [[FOO_ADDR_0_LCSSA]])
; CHECK-NEXT:    ret void
;
entry:
  %0 = load i8, ptr %str, align 1
  %tobool.not9 = icmp eq i8 %0, 0
  br i1 %tobool.not9, label %while.end, label %while.body

while.body:
  %count_multiple.014 = phi i32 [ %add, %while.body ], [ 0, %entry ]
  %count_offset.013 = phi i32 [ %inc1, %while.body ], [ -10, %entry ]
  %count.012 = phi i32 [ %inc, %while.body ], [ 0, %entry ]
  %foo.addr.011 = phi ptr [ %incdec.ptr2, %while.body ], [ %foo, %entry ]
  %str.addr.010 = phi ptr [ %incdec.ptr, %while.body ], [ %str, %entry ]
  %incdec.ptr = getelementptr inbounds nuw i8, ptr %str.addr.010, i64 1
  %inc = add nuw nsw i32 %count.012, 1
  %inc1 = add nsw i32 %count_offset.013, 1
  %add = add nuw nsw i32 %count_multiple.014, 2
  %incdec.ptr2 = getelementptr inbounds nuw i8, ptr %foo.addr.011, i64 1
  %1 = load i8, ptr %incdec.ptr, align 1
  %tobool.not = icmp eq i8 %1, 0
  br i1 %tobool.not, label %while.end, label %while.body

while.end:
  %str.addr.0.lcssa = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.body ]
  %foo.addr.0.lcssa = phi ptr [ %foo, %entry ], [ %incdec.ptr2, %while.body ]
  %count.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.body ]
  %count_offset.0.lcssa = phi i32 [ -10, %entry ], [ %inc1, %while.body ]
  %count_multiple.0.lcssa = phi i32 [ 0, %entry ], [ %add, %while.body ]
  tail call void @usei(i32 noundef %count.0.lcssa) #3
  tail call void @usei(i32 noundef %count_offset.0.lcssa) #3
  tail call void @usei(i32 noundef %count_multiple.0.lcssa) #3
  tail call void @use(ptr noundef nonnull %str.addr.0.lcssa) #3
  tail call void @use(ptr noundef %foo.addr.0.lcssa) #3
  ret void
}

; int valid_strlen_index(const char* str) {
;     int i = 0;
;     while (str[i]) {
;         ++i;
;     }
;     return i;
; }
define i32 @valid_strlen_index(ptr %str) {
; CHECK-LABEL: define i32 @valid_strlen_index(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[STR]])
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[INDVARS_IV:%.*]] = phi i64 [ [[INDVARS_IV_NEXT:%.*]], %[[WHILE_COND]] ], [ 0, %[[ENTRY]] ]
; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds i8, ptr [[STR]], i64 [[INDVARS_IV]]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[ARRAYIDX]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    [[INDVARS_IV_NEXT]] = add nuw nsw i64 [[INDVARS_IV]], 1
; CHECK-NEXT:    br i1 true, label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[TMP1:%.*]] = trunc nuw nsw i64 [[STRLEN]] to i32
; CHECK-NEXT:    ret i32 [[TMP1]]
;
entry:
  br label %while.cond

while.cond:
  %indvars.iv = phi i64 [ %indvars.iv.next, %while.cond ], [ 0, %entry ]
  %arrayidx = getelementptr inbounds i8, ptr %str, i64 %indvars.iv
  %0 = load i8, ptr %arrayidx, align 1
  %tobool.not = icmp eq i8 %0, 0
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  br i1 %tobool.not, label %while.end, label %while.cond

while.end:
  %1 = trunc nuw nsw i64 %indvars.iv to i32
  ret i32 %1
}

; void valid_strlen_offset(const my_char* str) {
;     if (*(str++) == '\0') return;
;     if (*(str++) == '\0') return;
;     if (*(str++) == '\0') return;
;     while (*str) {
;         ++str;
;     }
;     use(str);
; }
define dso_local void @valid_strlen_offset(ptr noundef %str) local_unnamed_addr {
; CHECK-LABEL: define dso_local void @valid_strlen_offset(
; CHECK-SAME: ptr noundef [[STR:%.*]]) local_unnamed_addr {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR]], align 1
; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    br i1 [[CMP]], label %[[RETURN:.*]], label %[[IF_END:.*]]
; CHECK:       [[IF_END]]:
; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds nuw i8, ptr [[STR]], i64 1
; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[INCDEC_PTR]], align 1
; CHECK-NEXT:    [[CMP4:%.*]] = icmp eq i8 [[TMP1]], 0
; CHECK-NEXT:    br i1 [[CMP4]], label %[[RETURN]], label %[[IF_END7:.*]]
; CHECK:       [[IF_END7]]:
; CHECK-NEXT:    [[INCDEC_PTR2:%.*]] = getelementptr inbounds nuw i8, ptr [[STR]], i64 2
; CHECK-NEXT:    [[TMP2:%.*]] = load i8, ptr [[INCDEC_PTR2]], align 1
; CHECK-NEXT:    [[CMP10:%.*]] = icmp eq i8 [[TMP2]], 0
; CHECK-NEXT:    br i1 [[CMP10]], label %[[RETURN]], label %[[WHILE_COND_PREHEADER:.*]]
; CHECK:       [[WHILE_COND_PREHEADER]]:
; CHECK-NEXT:    [[INCDEC_PTR8:%.*]] = getelementptr i8, ptr [[STR]], i64 3
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[INCDEC_PTR8]])
; CHECK-NEXT:    [[TMP3:%.*]] = add i64 [[STRLEN]], 3
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[STR]], i64 [[TMP3]]
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[INCDEC_PTR14:%.*]], %[[WHILE_COND]] ], [ [[INCDEC_PTR8]], %[[WHILE_COND_PREHEADER]] ]
; CHECK-NEXT:    [[TMP4:%.*]] = load i8, ptr [[STR_ADDR_0]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP4]], 0
; CHECK-NEXT:    [[INCDEC_PTR14]] = getelementptr inbounds nuw i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    br i1 true, label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    tail call void @use(ptr noundef nonnull [[SCEVGEP]])
; CHECK-NEXT:    br label %[[RETURN]]
; CHECK:       [[RETURN]]:
; CHECK-NEXT:    ret void
;
entry:
  %0 = load i8, ptr %str, align 1
  %cmp = icmp eq i8 %0, 0
  br i1 %cmp, label %return, label %if.end

if.end:
  %incdec.ptr = getelementptr inbounds nuw i8, ptr %str, i64 1
  %1 = load i8, ptr %incdec.ptr, align 1
  %cmp4 = icmp eq i8 %1, 0
  br i1 %cmp4, label %return, label %if.end7

if.end7:
  %incdec.ptr2 = getelementptr inbounds nuw i8, ptr %str, i64 2
  %2 = load i8, ptr %incdec.ptr2, align 1
  %cmp10 = icmp eq i8 %2, 0
  br i1 %cmp10, label %return, label %while.cond.preheader

while.cond.preheader:
  %incdec.ptr8 = getelementptr inbounds nuw i8, ptr %str, i64 3
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %incdec.ptr14, %while.cond ], [ %incdec.ptr8, %while.cond.preheader ]
  %3 = load i8, ptr %str.addr.0, align 1
  %tobool.not = icmp eq i8 %3, 0
  %incdec.ptr14 = getelementptr inbounds nuw i8, ptr %str.addr.0, i64 1
  br i1 %tobool.not, label %while.end, label %while.cond

while.end:
  tail call void @use(ptr noundef nonnull %str.addr.0) #3
  br label %return

return:
  ret void
}

; void valid_nested_idiom(const char** strs, int n) {
;     for (int i = 0; i < n; ++i) {
;         const char* s = strs[i];
;         int count = 0;
;         while (*s) {
;             ++s;
;             ++count;
;         }
;         usei(count);
;     }
; }
define void @valid_nested_idiom(ptr %strs, i32 %n) {
; CHECK-LABEL: define void @valid_nested_idiom(
; CHECK-SAME: ptr [[STRS:%.*]], i32 [[N:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    [[CMP9:%.*]] = icmp sgt i32 [[N]], 0
; CHECK-NEXT:    br i1 [[CMP9]], label %[[FOR_BODY_PREHEADER:.*]], label %[[FOR_COND_CLEANUP:.*]]
; CHECK:       [[FOR_BODY_PREHEADER]]:
; CHECK-NEXT:    [[WIDE_TRIP_COUNT:%.*]] = zext nneg i32 [[N]] to i64
; 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:    [[INDVARS_IV:%.*]] = phi i64 [ 0, %[[FOR_BODY_PREHEADER]] ], [ [[INDVARS_IV_NEXT:%.*]], %[[WHILE_END:.*]] ]
; CHECK-NEXT:    [[ARRAYIDX:%.*]] = getelementptr inbounds ptr, ptr [[STRS]], i64 [[INDVARS_IV]]
; CHECK-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[ARRAYIDX]], align 8
; CHECK-NEXT:    [[TMP1:%.*]] = load i8, ptr [[TMP0]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT6:%.*]] = icmp eq i8 [[TMP1]], 0
; CHECK-NEXT:    br i1 [[TOBOOL_NOT6]], label %[[WHILE_END]], label %[[WHILE_BODY_PREHEADER:.*]]
; CHECK:       [[WHILE_BODY_PREHEADER]]:
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[TMP0]], i64 1
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[SCEVGEP]])
; CHECK-NEXT:    [[TMP2:%.*]] = trunc i64 [[STRLEN]] to i32
; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 1
; CHECK-NEXT:    br label %[[WHILE_BODY:.*]]
; CHECK:       [[WHILE_BODY]]:
; CHECK-NEXT:    [[COUNT_08:%.*]] = phi i32 [ [[INC:%.*]], %[[WHILE_BODY]] ], [ 0, %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[S_07:%.*]] = phi ptr [ [[INCDEC_PTR:%.*]], %[[WHILE_BODY]] ], [ [[TMP0]], %[[WHILE_BODY_PREHEADER]] ]
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr inbounds nuw i8, ptr [[S_07]], i64 1
; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[COUNT_08]], 1
; CHECK-NEXT:    [[TMP4:%.*]] = load i8, ptr [[INCDEC_PTR]], align 1
; CHECK-NEXT:    [[TOBOOL_NOT:%.*]] = icmp eq i8 [[TMP4]], 0
; CHECK-NEXT:    br i1 true, label %[[WHILE_END_LOOPEXIT:.*]], label %[[WHILE_BODY]]
; CHECK:       [[WHILE_END_LOOPEXIT]]:
; CHECK-NEXT:    br label %[[WHILE_END]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[COUNT_0_LCSSA:%.*]] = phi i32 [ 0, %[[FOR_BODY]] ], [ [[TMP3]], %[[WHILE_END_LOOPEXIT]] ]
; CHECK-NEXT:    tail call void @usei(i32 [[COUNT_0_LCSSA]])
; 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:
  %cmp9 = icmp sgt i32 %n, 0
  br i1 %cmp9, label %for.body.preheader, label %for.cond.cleanup

for.body.preheader:
  %wide.trip.count = zext nneg i32 %n to i64
  br label %for.body

for.cond.cleanup:
  ret void

for.body:
  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %while.end ]
  %arrayidx = getelementptr inbounds ptr, ptr %strs, i64 %indvars.iv
  %0 = load ptr, ptr %arrayidx, align 8
  %1 = load i8, ptr %0, align 1
  %tobool.not6 = icmp eq i8 %1, 0
  br i1 %tobool.not6, label %while.end, label %while.body

while.body:
  %count.08 = phi i32 [ %inc, %while.body ], [ 0, %for.body ]
  %s.07 = phi ptr [ %incdec.ptr, %while.body ], [ %0, %for.body ]
  %incdec.ptr = getelementptr inbounds nuw i8, ptr %s.07, i64 1
  %inc = add nuw nsw i32 %count.08, 1
  %2 = load i8, ptr %incdec.ptr, align 1
  %tobool.not = icmp eq i8 %2, 0
  br i1 %tobool.not, label %while.end, label %while.body

while.end:
  %count.0.lcssa = phi i32 [ 0, %for.body ], [ %inc, %while.body ]
  tail call void @usei(i32 %count.0.lcssa) #2
  %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 i64 @invalid_strlen_has_side_effects(ptr %str) {
; CHECK-LABEL: define i64 @invalid_strlen_has_side_effects(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = load volatile i8, ptr [[STR_ADDR_0]], align 1
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    br i1 [[CMP_NOT]], label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[STR_ADDR_0_LCSSA:%.*]] = phi ptr [ [[STR_ADDR_0]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[STR_ADDR_0_LCSSA]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    ret i64 [[SUB_PTR_SUB]]
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %0 = load volatile i8, ptr %str.addr.0, align 1
  %cmp.not = icmp eq i8 %0, 0
  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 1
  br i1 %cmp.not, label %while.end, label %while.cond

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}


define i8 @invalid_exit_phi_scev(ptr %str) {
; CHECK-LABEL: define i8 @invalid_exit_phi_scev(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR_ADDR_0]], align 1
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    br i1 [[CMP_NOT]], label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[STR_ADDR_0_LCSSA:%.*]] = phi ptr [ [[STR_ADDR_0]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i8 [ [[TMP0]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[STR_ADDR_0_LCSSA]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    ret i8 [[DOTLCSSA]]
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %0 = load i8, ptr %str.addr.0, align 1
  %cmp.not = icmp eq i8 %0, 0
  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 1
  br i1 %cmp.not, label %while.end, label %while.cond

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast

  ; %0.lcssa has invalid scev rec {%0} expected to be {%str,+,constant}
  ret i8 %0
}


define i64 @invalid_branch_cond(ptr %str) {
; CHECK-LABEL: define i64 @invalid_branch_cond(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR_ADDR_0]], align 1
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 10
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    br i1 [[CMP_NOT]], label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[STR_ADDR_0_LCSSA:%.*]] = phi ptr [ [[STR_ADDR_0]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[STR_ADDR_0_LCSSA]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    ret i64 [[SUB_PTR_SUB]]
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %0 = load i8, ptr %str.addr.0, align 1

  ; We compare against '\n' instead of '\0'
  %cmp.not = icmp eq i8 %0, 10

  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 1
  br i1 %cmp.not, label %while.end, label %while.cond

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}

define i64 @invalid_unknown_step_size(ptr %str, i64 %step) {
; CHECK-LABEL: define i64 @invalid_unknown_step_size(
; CHECK-SAME: ptr [[STR:%.*]], i64 [[STEP:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR_ADDR_0]], align 1
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 [[STEP]]
; CHECK-NEXT:    br i1 [[CMP_NOT]], label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[STR_ADDR_0_LCSSA:%.*]] = phi ptr [ [[STR_ADDR_0]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[STR_ADDR_0_LCSSA]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    ret i64 [[SUB_PTR_SUB]]
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %0 = load i8, ptr %str.addr.0, align 1
  %cmp.not = icmp eq i8 %0, 0
  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 %step
  br i1 %cmp.not, label %while.end, label %while.cond

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}

declare ptr @pure(ptr) #0;
attributes #0 = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) }

define i64 @invalid_add_rec(ptr %str) {
; CHECK-LABEL: define i64 @invalid_add_rec(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[INDIRECT:%.*]] = tail call ptr @pure(ptr [[STR_ADDR_0]])
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[INDIRECT]], align 1
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 1
; CHECK-NEXT:    br i1 [[CMP_NOT]], label %[[WHILE_END:.*]], label %[[WHILE_COND]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[STR_ADDR_0_LCSSA:%.*]] = phi ptr [ [[STR_ADDR_0]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[STR_ADDR_0_LCSSA]] to i64
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]]
; CHECK-NEXT:    ret i64 [[SUB_PTR_SUB]]
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %indirect = tail call ptr @pure(ptr %str.addr.0)
  %0 = load i8, ptr %indirect, align 1
  %cmp.not = icmp eq i8 %0, 0
  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 1
  br i1 %cmp.not, label %while.end, label %while.cond

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  ret i64 %sub.ptr.sub
}

define i64 @valid_basic_strlen_with_dbg(ptr %str) {
; Make sure that the call to strlen has debug info attached.
; CHECK-LABEL: define i64 @valid_basic_strlen_with_dbg(
; CHECK-SAME: ptr [[STR:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(ptr [[STR]]), !dbg [[DBGLOC1:![0-9]+]]
; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[STR]], i64 [[STRLEN]]
; CHECK-NEXT:    br label %[[WHILE_COND:.*]]
; CHECK:       [[WHILE_COND]]:
; CHECK-NEXT:    [[STR_ADDR_0:%.*]] = phi ptr [ [[STR]], %[[ENTRY]] ], [ [[INCDEC_PTR:%.*]], %[[WHILE_COND]] ]
; CHECK-NEXT:    [[TMP0:%.*]] = load i8, ptr [[STR_ADDR_0]], align 1, !dbg [[DBGLOC2:![0-9]+]]
; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp eq i8 [[TMP0]], 0, !dbg [[DBGLOC2]]
; CHECK-NEXT:    [[INCDEC_PTR]] = getelementptr i8, ptr [[STR_ADDR_0]], i64 1, !dbg [[DBGLOC2]]
; CHECK-NEXT:    br i1 true, label %[[WHILE_END:.*]], label %[[WHILE_COND]], !dbg [[DBGLOC1]]
; CHECK:       [[WHILE_END]]:
; CHECK-NEXT:    [[SUB_PTR_LHS_CAST:%.*]] = ptrtoint ptr [[SCEVGEP]] to i64, !dbg [[DBGLOC2]]
; CHECK-NEXT:    [[SUB_PTR_RHS_CAST:%.*]] = ptrtoint ptr [[STR]] to i64, !dbg [[DBGLOC2]]
; CHECK-NEXT:    [[SUB_PTR_SUB:%.*]] = sub i64 [[SUB_PTR_LHS_CAST]], [[SUB_PTR_RHS_CAST]], !dbg [[DBGLOC2]]
; CHECK-NEXT:    ret i64 [[SUB_PTR_SUB]], !dbg [[DBGLOC2]]
;
; CHECK: [[DBGLOC1]] = !DILocation(line: 3, column: 3
; CHECK: [[DBGLOC2]] = !DILocation(line: 5, column: 3
;
entry:
  br label %while.cond

while.cond:
  %str.addr.0 = phi ptr [ %str, %entry ], [ %incdec.ptr, %while.cond ]
  %0 = load i8, ptr %str.addr.0, align 1, !dbg !8
  %cmp.not = icmp eq i8 %0, 0, !dbg !8
  %incdec.ptr = getelementptr i8, ptr %str.addr.0, i64 1, !dbg !8
  br i1 %cmp.not, label %while.end, label %while.cond, !dbg !4

while.end:
  %sub.ptr.lhs.cast = ptrtoint ptr %str.addr.0 to i64, !dbg !8
  %sub.ptr.rhs.cast = ptrtoint ptr %str to i64, !dbg !8
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast, !dbg !8
  ret i64 %sub.ptr.sub, !dbg !8
}

!llvm.module.flags = !{!0}
!llvm.dbg.cu = !{!1}

!0 = !{i32 1, !"Debug Info Version", i32 3}
!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "clang version 2.9 (trunk 127165:127174)", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !3, retainedTypes: !3)
!2 = !DIFile(filename: "strlen.c", directory: "/tmp")
!3 = !{}
!4 = !DILocation(line: 3, column: 3, scope: !5)
!5 = distinct !DILexicalBlock(scope: !6, file: !2, line: 2, column: 21)
!6 = distinct !DISubprogram(name: "foo", scope: !2, file: !2, line: 2, type: !7, virtualIndex: 6, flags: DIFlagPrototyped, spFlags: DISPFlagDefinition, unit: !1)
!7 = !DISubroutineType(types: !3)
!8 = !DILocation(line: 5, column: 3, scope: !5)