; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
; RUN: opt -passes='require<phi-values>,gvn' -S < %s | FileCheck %s --check-prefixes=CHECK-MEMDEP
; RUN: opt -passes='require<phi-values>,gvn<memoryssa>' -S < %s | FileCheck %s --check-prefixes=CHECK-MEMSSA

declare noalias ptr @malloc(i64)

; Detecting that %s is fully redundant should let us detect that %w is partially
; redundant.
define void @fn1(ptr noalias %start, ptr %width, i32 %h) {
; CHECK-MEMDEP-LABEL: define void @fn1(
; CHECK-MEMDEP-SAME: ptr noalias [[START:%.*]], ptr [[WIDTH:%.*]], i32 [[H:%.*]]) {
; CHECK-MEMDEP-NEXT:  [[ENTRY:.*:]]
; CHECK-MEMDEP-NEXT:    [[CALL:%.*]] = tail call noalias ptr @malloc(i64 1024)
; CHECK-MEMDEP-NEXT:    store ptr [[CALL]], ptr [[START]], align 8
; CHECK-MEMDEP-NEXT:    br label %[[PREHEADER:.*]]
; CHECK-MEMDEP:       [[PREHEADER]]:
; CHECK-MEMDEP-NEXT:    [[CMP:%.*]] = icmp slt i32 1, [[H]]
; CHECK-MEMDEP-NEXT:    br i1 [[CMP]], label %[[PREHEADER_BODY_CRIT_EDGE:.*]], label %[[EXIT:.*]]
; CHECK-MEMDEP:       [[PREHEADER_BODY_CRIT_EDGE]]:
; CHECK-MEMDEP-NEXT:    [[W_PRE:%.*]] = load i32, ptr [[WIDTH]], align 8
; CHECK-MEMDEP-NEXT:    br label %[[BODY:.*]]
; CHECK-MEMDEP:       [[BODY]]:
; CHECK-MEMDEP-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[PREHEADER_BODY_CRIT_EDGE]] ], [ [[J_NEXT:%.*]], %[[BODY]] ]
; CHECK-MEMDEP-NEXT:    store i32 0, ptr [[CALL]], align 4
; CHECK-MEMDEP-NEXT:    [[J_NEXT]] = add nuw nsw i32 [[J]], 1
; CHECK-MEMDEP-NEXT:    [[CMP3:%.*]] = icmp slt i32 [[J_NEXT]], [[W_PRE]]
; CHECK-MEMDEP-NEXT:    br i1 [[CMP3]], label %[[BODY]], label %[[PREHEADER]]
; CHECK-MEMDEP:       [[EXIT]]:
; CHECK-MEMDEP-NEXT:    ret void
;
; CHECK-MEMSSA-LABEL: define void @fn1(
; CHECK-MEMSSA-SAME: ptr noalias [[START:%.*]], ptr [[WIDTH:%.*]], i32 [[H:%.*]]) {
; CHECK-MEMSSA-NEXT:  [[ENTRY:.*:]]
; CHECK-MEMSSA-NEXT:    [[CALL:%.*]] = tail call noalias ptr @malloc(i64 1024)
; CHECK-MEMSSA-NEXT:    store ptr [[CALL]], ptr [[START]], align 8
; CHECK-MEMSSA-NEXT:    br label %[[PREHEADER:.*]]
; CHECK-MEMSSA:       [[PREHEADER]]:
; CHECK-MEMSSA-NEXT:    [[CMP:%.*]] = icmp slt i32 1, [[H]]
; CHECK-MEMSSA-NEXT:    br i1 [[CMP]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK-MEMSSA:       [[BODY]]:
; CHECK-MEMSSA-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[PREHEADER]] ], [ [[J_NEXT:%.*]], %[[BODY]] ]
; CHECK-MEMSSA-NEXT:    [[S:%.*]] = load ptr, ptr [[START]], align 8
; CHECK-MEMSSA-NEXT:    store i32 0, ptr [[S]], align 4
; CHECK-MEMSSA-NEXT:    [[J_NEXT]] = add nuw nsw i32 [[J]], 1
; CHECK-MEMSSA-NEXT:    [[W:%.*]] = load i32, ptr [[WIDTH]], align 8
; CHECK-MEMSSA-NEXT:    [[CMP3:%.*]] = icmp slt i32 [[J_NEXT]], [[W]]
; CHECK-MEMSSA-NEXT:    br i1 [[CMP3]], label %[[BODY]], label %[[PREHEADER]]
; CHECK-MEMSSA:       [[EXIT]]:
; CHECK-MEMSSA-NEXT:    ret void
;
entry:
  %call = tail call noalias ptr @malloc(i64 1024)
  store ptr %call, ptr %start, align 8
  br label %preheader

preheader:
  %cmp = icmp slt i32 1, %h
  br i1 %cmp, label %body, label %exit

body:
  %j = phi i32 [ 0, %preheader ], [ %j.next, %body ]
  %s = load ptr, ptr %start, align 8
  store i32 0, ptr %s, align 4
  %j.next = add nuw nsw i32 %j, 1
  %w = load i32, ptr %width, align 8
  %cmp3 = icmp slt i32 %j.next, %w
  br i1 %cmp3, label %body, label %preheader

exit:
  ret void
}

; %s is fully redundant but has more than one available value. Detecting that
; %w is partially redundant requires alias analysis that can analyze those
; values.
define void @fn2(ptr noalias %start, ptr %width, i32 %h, i32 %arg) {
; CHECK-MEMDEP-LABEL: define void @fn2(
; CHECK-MEMDEP-SAME: ptr noalias [[START:%.*]], ptr [[WIDTH:%.*]], i32 [[H:%.*]], i32 [[ARG:%.*]]) {
; CHECK-MEMDEP-NEXT:  [[ENTRY:.*:]]
; CHECK-MEMDEP-NEXT:    [[CALL:%.*]] = tail call noalias ptr @malloc(i64 1024)
; CHECK-MEMDEP-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ARG]], 0
; CHECK-MEMDEP-NEXT:    br i1 [[CMP1]], label %[[IF:.*]], label %[[ELSE:.*]]
; CHECK-MEMDEP:       [[IF]]:
; CHECK-MEMDEP-NEXT:    store ptr [[CALL]], ptr [[START]], align 8
; CHECK-MEMDEP-NEXT:    br label %[[PREHEADER:.*]]
; CHECK-MEMDEP:       [[ELSE]]:
; CHECK-MEMDEP-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[CALL]], i32 [[ARG]]
; CHECK-MEMDEP-NEXT:    store ptr [[GEP]], ptr [[START]], align 8
; CHECK-MEMDEP-NEXT:    br label %[[PREHEADER]]
; CHECK-MEMDEP:       [[PREHEADER]]:
; CHECK-MEMDEP-NEXT:    [[S:%.*]] = phi ptr [ [[S]], %[[BODY:.*]] ], [ [[GEP]], %[[ELSE]] ], [ [[CALL]], %[[IF]] ]
; CHECK-MEMDEP-NEXT:    [[CMP:%.*]] = icmp slt i32 1, [[H]]
; CHECK-MEMDEP-NEXT:    br i1 [[CMP]], label %[[PREHEADER_BODY_CRIT_EDGE:.*]], label %[[EXIT:.*]]
; CHECK-MEMDEP:       [[PREHEADER_BODY_CRIT_EDGE]]:
; CHECK-MEMDEP-NEXT:    [[W_PRE:%.*]] = load i32, ptr [[WIDTH]], align 8
; CHECK-MEMDEP-NEXT:    br label %[[BODY]]
; CHECK-MEMDEP:       [[BODY]]:
; CHECK-MEMDEP-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[PREHEADER_BODY_CRIT_EDGE]] ], [ [[J_NEXT:%.*]], %[[BODY]] ]
; CHECK-MEMDEP-NEXT:    store i32 0, ptr [[S]], align 4
; CHECK-MEMDEP-NEXT:    [[J_NEXT]] = add nuw nsw i32 [[J]], 1
; CHECK-MEMDEP-NEXT:    [[CMP3:%.*]] = icmp slt i32 [[J_NEXT]], [[W_PRE]]
; CHECK-MEMDEP-NEXT:    br i1 [[CMP3]], label %[[BODY]], label %[[PREHEADER]]
; CHECK-MEMDEP:       [[EXIT]]:
; CHECK-MEMDEP-NEXT:    ret void
;
; CHECK-MEMSSA-LABEL: define void @fn2(
; CHECK-MEMSSA-SAME: ptr noalias [[START:%.*]], ptr [[WIDTH:%.*]], i32 [[H:%.*]], i32 [[ARG:%.*]]) {
; CHECK-MEMSSA-NEXT:  [[ENTRY:.*:]]
; CHECK-MEMSSA-NEXT:    [[CALL:%.*]] = tail call noalias ptr @malloc(i64 1024)
; CHECK-MEMSSA-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ARG]], 0
; CHECK-MEMSSA-NEXT:    br i1 [[CMP1]], label %[[IF:.*]], label %[[ELSE:.*]]
; CHECK-MEMSSA:       [[IF]]:
; CHECK-MEMSSA-NEXT:    store ptr [[CALL]], ptr [[START]], align 8
; CHECK-MEMSSA-NEXT:    br label %[[PREHEADER:.*]]
; CHECK-MEMSSA:       [[ELSE]]:
; CHECK-MEMSSA-NEXT:    [[GEP:%.*]] = getelementptr inbounds i32, ptr [[CALL]], i32 [[ARG]]
; CHECK-MEMSSA-NEXT:    store ptr [[GEP]], ptr [[START]], align 8
; CHECK-MEMSSA-NEXT:    br label %[[PREHEADER]]
; CHECK-MEMSSA:       [[PREHEADER]]:
; CHECK-MEMSSA-NEXT:    [[CMP:%.*]] = icmp slt i32 1, [[H]]
; CHECK-MEMSSA-NEXT:    br i1 [[CMP]], label %[[BODY:.*]], label %[[EXIT:.*]]
; CHECK-MEMSSA:       [[BODY]]:
; CHECK-MEMSSA-NEXT:    [[J:%.*]] = phi i32 [ 0, %[[PREHEADER]] ], [ [[J_NEXT:%.*]], %[[BODY]] ]
; CHECK-MEMSSA-NEXT:    [[S:%.*]] = load ptr, ptr [[START]], align 8
; CHECK-MEMSSA-NEXT:    store i32 0, ptr [[S]], align 4
; CHECK-MEMSSA-NEXT:    [[J_NEXT]] = add nuw nsw i32 [[J]], 1
; CHECK-MEMSSA-NEXT:    [[W:%.*]] = load i32, ptr [[WIDTH]], align 8
; CHECK-MEMSSA-NEXT:    [[CMP3:%.*]] = icmp slt i32 [[J_NEXT]], [[W]]
; CHECK-MEMSSA-NEXT:    br i1 [[CMP3]], label %[[BODY]], label %[[PREHEADER]]
; CHECK-MEMSSA:       [[EXIT]]:
; CHECK-MEMSSA-NEXT:    ret void
;
entry:
  %call = tail call noalias ptr @malloc(i64 1024)
  %cmp1 = icmp slt i32 %arg, 0
  br i1 %cmp1, label %if, label %else

if:
  store ptr %call, ptr %start, align 8
  br label %preheader

else:
  %gep = getelementptr inbounds i32, ptr %call, i32 %arg
  store ptr %gep, ptr %start, align 8
  br label %preheader

preheader:
  %cmp = icmp slt i32 1, %h
  br i1 %cmp, label %body, label %exit

body:
  %j = phi i32 [ 0, %preheader ], [ %j.next, %body ]
  %s = load ptr, ptr %start, align 8
  store i32 0, ptr %s, align 4
  %j.next = add nuw nsw i32 %j, 1
  %w = load i32, ptr %width, align 8
  %cmp3 = icmp slt i32 %j.next, %w
  br i1 %cmp3, label %body, label %preheader

exit:
  ret void
}