; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -loop-idiom -verify -verify-each -verify-dom-info -verify-loop-info < %s -S | FileCheck %s --implicit-check-not=bcmp --implicit-check-not=memcmp

; CHECK: source_filename

target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64"

define i1 @three_blocks_and_two_latches_in_loop(i8* %ptr0, i8* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ], [ 0, %for.passthrough ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp eq i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.passthrough, label %cleanup

for.passthrough:
  br i1 true, label %for.cond, label %for.body

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @three_blocks_in_loop(i8* %ptr0, i8* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp eq i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.passthrough, label %cleanup

for.passthrough:
  br label %for.cond

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @body_cmp_is_not_equality(i8* %ptr0, i8* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp ult i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @only_one_load(i8* %ptr0, i8* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %cmp3 = icmp eq i8 %v0, 0
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @loads_of_less_than_byte(i7* %ptr0, i7* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i7, i7* %ptr0, i64 %i.08
  %v0 = load i7, i7* %arrayidx
  %arrayidx1 = getelementptr inbounds i7, i7* %ptr1, i64 %i.08
  %v1 = load i7, i7* %arrayidx1
  %cmp3 = icmp ult i7 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @loads_of_not_multiple_of_a_byte(i9* %ptr0, i9* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i9, i9* %ptr0, i64 %i.08
  %v0 = load i9, i9* %arrayidx
  %arrayidx1 = getelementptr inbounds i9, i9* %ptr1, i64 %i.08
  %v1 = load i9, i9* %arrayidx1
  %cmp3 = icmp ult i9 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @loop_instruction_used_in_phi_node_outside_loop(i8* %ptr0, i8* %ptr1) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp eq i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ %cmp3, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @loop_has_write(i8* %ptr0, i8* %ptr1, i32* %write) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp eq i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  store i32 0, i32* %write
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

declare void @sink()
define i1 @loop_has_call(i8* %ptr0, i8* %ptr1, i32* %load) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp eq i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  tail call void @sink()
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @loop_has_atomic_load(i8* %ptr0, i8* %ptr1, i32* %load) {
entry:
  br label %for.body

for.body:
  %i.08 = phi i64 [ 0, %entry ], [ %inc, %for.cond ]
  %arrayidx = getelementptr inbounds i8, i8* %ptr0, i64 %i.08
  %v0 = load i8, i8* %arrayidx
  %arrayidx1 = getelementptr inbounds i8, i8* %ptr1, i64 %i.08
  %v1 = load i8, i8* %arrayidx1
  %cmp3 = icmp eq i8 %v0, %v1
  %inc = add nuw nsw i64 %i.08, 1
  br i1 %cmp3, label %for.cond, label %cleanup

for.cond:
  %cmp = icmp ult i64 %inc, 8
  %tmp = load atomic i32, i32* %load unordered, align 1
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.cond ]
  ret i1 %res
}

define i1 @different_load_step(i8* %ptr) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.015 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.014 = phi i8* [ %add.ptr, %entry ], [ %add.ptr3, %for.inc ]
  %ptr0.013 = phi i8* [ %ptr, %entry ], [ %incdec.ptr, %for.inc ]
  %v0 = load i8, i8* %ptr0.013
  %v1 = load i8, i8* %ptr1.014
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.015, 1
  %incdec.ptr = getelementptr inbounds i8, i8* %ptr0.013, i64 1
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr1.014, i64 2
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @step_is_variable(i8* %ptr, i64 %step) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.015 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.014 = phi i8* [ %add.ptr, %entry ], [ %add.ptr3, %for.inc ]
  %ptr0.013 = phi i8* [ %ptr, %entry ], [ %incdec.ptr, %for.inc ]
  %v0 = load i8, i8* %ptr0.013
  %v1 = load i8, i8* %ptr1.014
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.015, %step
  %incdec.ptr = getelementptr inbounds i8, i8* %ptr0.013, i64 1
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr1.014, i64 1
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @load_step_is_variable(i8* %ptr, i64 %step) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.015 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.014 = phi i8* [ %add.ptr, %entry ], [ %add.ptr3, %for.inc ]
  %ptr0.013 = phi i8* [ %ptr, %entry ], [ %incdec.ptr, %for.inc ]
  %v0 = load i8, i8* %ptr0.013
  %v1 = load i8, i8* %ptr1.014
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.015, 1
  %incdec.ptr = getelementptr inbounds i8, i8* %ptr0.013, i64 %step
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr1.014, i64 %step
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @step_and_load_step_is_variable(i8* %ptr, i64 %step) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.015 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.014 = phi i8* [ %add.ptr, %entry ], [ %add.ptr3, %for.inc ]
  %ptr0.013 = phi i8* [ %ptr, %entry ], [ %incdec.ptr, %for.inc ]
  %v0 = load i8, i8* %ptr0.013
  %v1 = load i8, i8* %ptr1.014
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.015, %step
  %incdec.ptr = getelementptr inbounds i8, i8* %ptr0.013, i64 %step
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr1.014, i64 %step
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @load_step_not_affine(i8* %ptr) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.018 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.017 = phi i8* [ %add.ptr, %entry ], [ %add.ptr4, %for.inc ]
  %ptr0.016 = phi i8* [ %ptr, %entry ], [ %add.ptr3, %for.inc ]
  %v0 = load i8, i8* %ptr0.016
  %v1 = load i8, i8* %ptr1.017
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.018, 1
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr0.016, i64 %inc
  %add.ptr4 = getelementptr inbounds i8, i8* %ptr1.017, i64 %inc
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @no_overlap_between_loads(i8* %ptr) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.016 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.015 = phi i8* [ %add.ptr, %entry ], [ %add.ptr4, %for.inc ]
  %ptr0.014 = phi i8* [ %ptr, %entry ], [ %add.ptr3, %for.inc ]
  %v0 = load i8, i8* %ptr0.014
  %v1 = load i8, i8* %ptr1.015
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.016, 1
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr0.014, i64 2
  %add.ptr4 = getelementptr inbounds i8, i8* %ptr1.015, i64 2
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @volatile_loads(i8* %ptr) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.016 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.015 = phi i8* [ %add.ptr, %entry ], [ %add.ptr4, %for.inc ]
  %ptr0.014 = phi i8* [ %ptr, %entry ], [ %add.ptr3, %for.inc ]
  %v0 = load volatile i8, i8* %ptr0.014
  %v1 = load volatile i8, i8* %ptr1.015
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.016, 1
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr0.014, i64 1
  %add.ptr4 = getelementptr inbounds i8, i8* %ptr1.015, i64 1
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @atomic_loads(i8* %ptr) {
entry:
  %add.ptr = getelementptr inbounds i8, i8* %ptr, i64 8
  br label %for.body

for.body:
  %i.016 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.015 = phi i8* [ %add.ptr, %entry ], [ %add.ptr4, %for.inc ]
  %ptr0.014 = phi i8* [ %ptr, %entry ], [ %add.ptr3, %for.inc ]
  %v0 = load atomic i8, i8* %ptr0.014 unordered, align 1
  %v1 = load atomic i8, i8* %ptr1.015 unordered, align 1
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.016, 1
  %add.ptr3 = getelementptr inbounds i8, i8* %ptr0.014, i64 1
  %add.ptr4 = getelementptr inbounds i8, i8* %ptr1.015, i64 1
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

define i1 @address_space(i8 addrspace(1)* %ptr) {
entry:
  %add.ptr = getelementptr inbounds i8, i8 addrspace(1)* %ptr, i64 8
  br label %for.body

for.body:
  %i.016 = phi i64 [ 0, %entry ], [ %inc, %for.inc ]
  %ptr1.015 = phi i8 addrspace(1)* [ %add.ptr, %entry ], [ %add.ptr4, %for.inc ]
  %ptr0.014 = phi i8 addrspace(1)* [ %ptr, %entry ], [ %add.ptr3, %for.inc ]
  %v0 = load i8, i8 addrspace(1)* %ptr0.014
  %v1 = load i8, i8 addrspace(1)* %ptr1.015
  %cmp2 = icmp eq i8 %v0, %v1
  br i1 %cmp2, label %for.inc, label %cleanup

for.inc:
  %inc = add nuw nsw i64 %i.016, 1
  %add.ptr3 = getelementptr inbounds i8, i8 addrspace(1)* %ptr0.014, i64 1
  %add.ptr4 = getelementptr inbounds i8, i8 addrspace(1)* %ptr1.015, i64 1
  %cmp = icmp ult i64 %inc, 16
  br i1 %cmp, label %for.body, label %cleanup

cleanup:
  %res = phi i1 [ false, %for.body ], [ true, %for.inc ]
  ret i1 %res
}

; See https://bugs.llvm.org/show_bug.cgi?id=43206 for original reduced (but runnable) test:
;
; bool do_check(int i_max, int j_max, int**bptr, int* fillch) {
;   for (int i = 0; i < i_max; i++)
;       for (int j = 0; j < j_max; j++)
;         if (bptr[i][j] != fillch[i])
;           return 1;
;   return 0;
; }
; The loads proceed differently here - fillch[i] changes once per outer loop,
; while bptr[i][j] changes both in inner loop, and in outer loop.
define i1 @pr43206_different_loops(i32 %i_max, i32 %j_max, i32** %bptr, i32* %fillch) {
entry:
  %cmp31 = icmp sgt i32 %i_max, 0
  %cmp229 = icmp sgt i32 %j_max, 0
  %or.cond = and i1 %cmp31, %cmp229
  br i1 %or.cond, label %for.cond1.preheader.us.preheader, label %cleanup12

for.cond1.preheader.us.preheader:                 ; preds = %entry
  %wide.trip.count38 = zext i32 %i_max to i64
  %wide.trip.count = zext i32 %j_max to i64
  br label %for.cond1.preheader.us

for.cond1.preheader.us:                           ; preds = %for.cond1.for.inc10_crit_edge.us, %for.cond1.preheader.us.preheader
  %indvars.iv36 = phi i64 [ 0, %for.cond1.preheader.us.preheader ], [ %indvars.iv.next37, %for.cond1.for.inc10_crit_edge.us ]
  %arrayidx.us = getelementptr inbounds i32*, i32** %bptr, i64 %indvars.iv36
  %v0 = load i32*, i32** %arrayidx.us, align 8
  %arrayidx8.us = getelementptr inbounds i32, i32* %fillch, i64 %indvars.iv36
  %v1 = load i32, i32* %arrayidx8.us, align 4
  br label %for.body4.us

for.cond1.us:                                     ; preds = %for.body4.us
  %exitcond = icmp eq i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond, label %for.cond1.for.inc10_crit_edge.us, label %for.body4.us

for.body4.us:                                     ; preds = %for.cond1.us, %for.cond1.preheader.us
  %indvars.iv = phi i64 [ 0, %for.cond1.preheader.us ], [ %indvars.iv.next, %for.cond1.us ]
  %arrayidx6.us = getelementptr inbounds i32, i32* %v0, i64 %indvars.iv
  %v2 = load i32, i32* %arrayidx6.us, align 4
  %cmp9.us = icmp eq i32 %v2, %v1
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  br i1 %cmp9.us, label %for.cond1.us, label %cleanup12

for.cond1.for.inc10_crit_edge.us:                 ; preds = %for.cond1.us
  %indvars.iv.next37 = add nuw nsw i64 %indvars.iv36, 1
  %exitcond39 = icmp eq i64 %indvars.iv.next37, %wide.trip.count38
  br i1 %exitcond39, label %cleanup12, label %for.cond1.preheader.us

cleanup12:                                        ; preds = %for.cond1.for.inc10_crit_edge.us, %for.body4.us, %entry
  %v3 = phi i1 [ false, %entry ], [ true, %for.body4.us ], [ false, %for.cond1.for.inc10_crit_edge.us ]
  ret i1 %v3
}