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

; Both the stores in %then and %else can be eliminated by translating %p
; through the phi.
define void @memoryphi_translate_1(i1 %c) {
; CHECK-LABEL: @memoryphi_translate_1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    br label [[END:%.*]]
; CHECK:       else:
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
; CHECK-NEXT:    store i8 10, ptr [[P]], align 1
; CHECK-NEXT:    ret void
;
entry:
  %a.1 = alloca i8
  %a.2 = alloca i8
  br i1 %c, label %then, label %else

then:
  store i8 0, ptr %a.1
  br label %end

else:
  store i8 9, ptr %a.2
  br label %end

end:
  %p = phi ptr [ %a.1, %then ], [ %a.2, %else ]
  store i8 10, ptr %p
  ret void
}

; The store in %else can be eliminated by translating %p through the phi.
; The store in %then cannot be eliminated, because %a.1 is read before the final
; store.
define i8 @memoryphi_translate_2(i1 %c) {
; CHECK-LABEL: @memoryphi_translate_2(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    store i8 0, ptr [[A_1]], align 1
; CHECK-NEXT:    br label [[END:%.*]]
; CHECK:       else:
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
; CHECK-NEXT:    [[L:%.*]] = load i8, ptr [[A_1]], align 1
; CHECK-NEXT:    store i8 10, ptr [[P]], align 1
; CHECK-NEXT:    ret i8 [[L]]
;
entry:
  %a.1 = alloca i8
  %a.2 = alloca i8
  br i1 %c, label %then, label %else

then:
  store i8 0, ptr %a.1
  br label %end

else:
  store i8 9, ptr %a.2
  br label %end

end:
  %p = phi ptr [ %a.1, %then ], [ %a.2, %else ]
  %l = load i8, ptr %a.1
  store i8 10, ptr %p
  ret i8 %l
}

; The store in %then can be eliminated by translating %p through the phi.
; The store in %else cannot be eliminated, because %a.2 is read before the final
; store.
define i8 @memoryphi_translate_3(i1 %c) {
; CHECK-LABEL: @memoryphi_translate_3(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    br label [[END:%.*]]
; CHECK:       else:
; CHECK-NEXT:    store i8 9, ptr [[A_2]], align 1
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
; CHECK-NEXT:    [[L:%.*]] = load i8, ptr [[A_2]], align 1
; CHECK-NEXT:    store i8 10, ptr [[P]], align 1
; CHECK-NEXT:    ret i8 [[L]]
;
entry:
  %a.1 = alloca i8
  %a.2 = alloca i8
  br i1 %c, label %then, label %else

then:
  store i8 0, ptr %a.1
  br label %end

else:
  store i8 9, ptr %a.2
  br label %end

end:
  %p = phi ptr [ %a.1, %then ], [ %a.2, %else ]
  %l = load i8, ptr %a.2
  store i8 10, ptr %p
  ret i8 %l
}

; No stores can be eliminated, because there's a load from the phi.
define i8 @memoryphi_translate_4(i1 %c) {
; CHECK-LABEL: @memoryphi_translate_4(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A_1:%.*]] = alloca i8, align 1
; CHECK-NEXT:    [[A_2:%.*]] = alloca i8, align 1
; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    store i8 0, ptr [[A_1]], align 1
; CHECK-NEXT:    br label [[END:%.*]]
; CHECK:       else:
; CHECK-NEXT:    store i8 9, ptr [[A_2]], align 1
; CHECK-NEXT:    br label [[END]]
; CHECK:       end:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[A_1]], [[THEN]] ], [ [[A_2]], [[ELSE]] ]
; CHECK-NEXT:    [[L:%.*]] = load i8, ptr [[P]], align 1
; CHECK-NEXT:    store i8 10, ptr [[P]], align 1
; CHECK-NEXT:    ret i8 [[L]]
;
entry:
  %a.1 = alloca i8
  %a.2 = alloca i8
  br i1 %c, label %then, label %else

then:
  store i8 0, ptr %a.1
  br label %end

else:
  store i8 9, ptr %a.2
  br label %end

end:
  %p = phi ptr [ %a.1, %then ], [ %a.2, %else ]
  %l = load i8, ptr %p
  store i8 10, ptr %p
  ret i8 %l
}

; TODO: The store in %entry can be removed by translating %p through the phi.
define void @memoryphi_translate_5(i1 %cond) {
; CHECK-LABEL: @memoryphi_translate_5(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A:%.*]] = alloca i8, align 1
; CHECK-NEXT:    [[B:%.*]] = alloca i8, align 1
; CHECK-NEXT:    store i8 0, ptr [[A]], align 1
; CHECK-NEXT:    br i1 [[COND:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
; CHECK:       cond.true:
; CHECK-NEXT:    br label [[COND_END]]
; CHECK:       cond.end:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[B]], [[COND_TRUE]] ], [ [[A]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    store i8 0, ptr [[P]], align 1
; CHECK-NEXT:    call void @use(ptr [[P]])
; CHECK-NEXT:    ret void
;
entry:
  %a = alloca i8
  %b = alloca i8
  %c = alloca i8
  store i8 0, ptr %a
  br i1 %cond, label %cond.true, label %cond.end

cond.true:
  store i8 0, ptr %c
  br label %cond.end

cond.end:
  %p = phi ptr [ %b, %cond.true ], [ %a, %entry ]
  store i8 0, ptr %p
  call void @use(ptr %p)
  ret void
}

; TODO: The store in %entry can be removed by translating %p through the phi.
; Same as @memoryphi_translate_5, but without stores in %cond.true, so there
; is no MemoryPhi.
define void @translate_without_memoryphi_1(i1 %cond) {
; CHECK-LABEL: @translate_without_memoryphi_1(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    [[A:%.*]] = alloca i8, align 1
; CHECK-NEXT:    [[B:%.*]] = alloca i8, align 1
; CHECK-NEXT:    store i8 0, ptr [[A]], align 1
; CHECK-NEXT:    br i1 [[COND:%.*]], label [[COND_TRUE:%.*]], label [[COND_END:%.*]]
; CHECK:       cond.true:
; CHECK-NEXT:    br label [[COND_END]]
; CHECK:       cond.end:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[B]], [[COND_TRUE]] ], [ [[A]], [[ENTRY:%.*]] ]
; CHECK-NEXT:    store i8 0, ptr [[P]], align 1
; CHECK-NEXT:    call void @use(ptr [[P]])
; CHECK-NEXT:    ret void
;
entry:
  %a = alloca i8
  %b = alloca i8
  store i8 0, ptr %a
  br i1 %cond, label %cond.true, label %cond.end

cond.true:
  br label %cond.end

cond.end:
  %p = phi ptr [ %b, %cond.true ], [ %a, %entry ]
  store i8 0, ptr %p
  call void @use(ptr %p)
  ret void
}

; In the test, translating through the phi results in a null address. Make sure
; this does not cause a crash.
define void @test_trans_null(i1 %c, ptr %ptr) {
; CHECK-LABEL: @test_trans_null(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br i1 [[C:%.*]], label [[THEN:%.*]], label [[ELSE:%.*]]
; CHECK:       then:
; CHECK-NEXT:    br label [[EXIT:%.*]]
; CHECK:       else:
; CHECK-NEXT:    call void @fn()
; CHECK-NEXT:    [[GEP_1:%.*]] = getelementptr inbounds i16, ptr undef, i64 2
; CHECK-NEXT:    store i16 8, ptr [[GEP_1]], align 2
; CHECK-NEXT:    br label [[EXIT]]
; CHECK:       exit:
; CHECK-NEXT:    [[P:%.*]] = phi ptr [ [[PTR:%.*]], [[THEN]] ], [ undef, [[ELSE]] ]
; CHECK-NEXT:    [[GEP_2:%.*]] = getelementptr inbounds i16, ptr [[P]], i64 2
; CHECK-NEXT:    store i16 8, ptr [[GEP_2]], align 2
; CHECK-NEXT:    ret void
;
entry:
  br i1 %c, label %then, label %else

then:
  br label %exit

else:
  call void @fn()
  %gep.1 = getelementptr inbounds i16, ptr undef, i64 2
  store i16 8, ptr %gep.1, align 2
  br label %exit

exit:
  %p = phi ptr [ %ptr, %then ], [ undef, %else ]
  %gep.2 = getelementptr inbounds i16, ptr %p, i64 2
  store i16 8, ptr %gep.2, align 2
  ret void
}


declare void @use(ptr)
declare void @fn()