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

declare {ptr, i64} @bar(i64)

; Basic test.
define {ptr, i64} @test1(i1 %cond1, ptr %p1, ptr %p2) {
; CHECK-LABEL: define { ptr, i64 } @test1(
; CHECK-SAME: i1 [[COND1:%.*]], ptr [[P1:%.*]], ptr [[P2:%.*]]) {
; CHECK-NEXT:    br i1 [[COND1]], label %[[BBB1:.*]], label %[[BBB2:.*]]
; CHECK:       [[BBB1]]:
; CHECK-NEXT:    [[CALL1:%.*]] = call { ptr, i64 } @bar(i64 0)
; CHECK-NEXT:    br label %[[EXIT:.*]]
; CHECK:       [[BBB2]]:
; CHECK-NEXT:    [[VAL21:%.*]] = load ptr, ptr [[P1]], align 8
; CHECK-NEXT:    [[VAL22:%.*]] = load i64, ptr [[P2]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { ptr, i64 } poison, ptr [[VAL21]], 0
; CHECK-NEXT:    [[TMP2:%.*]] = insertvalue { ptr, i64 } [[TMP1]], i64 [[VAL22]], 1
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[RES_MERGED:%.*]] = phi { ptr, i64 } [ [[CALL1]], %[[BBB1]] ], [ [[TMP2]], %[[BBB2]] ]
; CHECK-NEXT:    ret { ptr, i64 } [[RES_MERGED]]
;
  br i1 %cond1, label %bbb1, label %bbb2

bbb1:
  %call1 = call {ptr, i64} @bar(i64 0)
  %val11 = extractvalue { ptr, i64 } %call1, 0
  %val12 = extractvalue { ptr, i64 } %call1, 1
  br label %exit

bbb2:
  %val21 = load ptr, ptr %p1
  %val22 = load i64, ptr %p2
  br label %exit

exit:
  %val1 = phi ptr [%val11, %bbb1], [%val21, %bbb2]
  %val2 = phi i64 [%val12, %bbb1], [%val22, %bbb2]
  %tmp = insertvalue { ptr, i64 } poison, ptr %val1, 0
  %res = insertvalue { ptr, i64 } %tmp, i64 %val2, 1
  ret {ptr, i64} %res
}

; Test with more predecessors.
define {ptr, i64} @test2(i1 %cond1, i1 %cond2, ptr %p1, ptr %p2) {
; CHECK-LABEL: define { ptr, i64 } @test2(
; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]], ptr [[P1:%.*]], ptr [[P2:%.*]]) {
; CHECK-NEXT:    br i1 [[COND1]], label %[[BBB1:.*]], label %[[BBB4:.*]]
; CHECK:       [[BBB1]]:
; CHECK-NEXT:    br i1 [[COND2]], label %[[BBB2:.*]], label %[[BBB3:.*]]
; CHECK:       [[BBB2]]:
; CHECK-NEXT:    [[CALL1:%.*]] = call { ptr, i64 } @bar(i64 0)
; CHECK-NEXT:    br label %[[EXIT:.*]]
; CHECK:       [[BBB3]]:
; CHECK-NEXT:    [[CALL2:%.*]] = call { ptr, i64 } @bar(i64 1)
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[BBB4]]:
; CHECK-NEXT:    [[VAL31:%.*]] = load ptr, ptr [[P1]], align 8
; CHECK-NEXT:    [[VAL32:%.*]] = load i64, ptr [[P2]], align 4
; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { ptr, i64 } poison, ptr [[VAL31]], 0
; CHECK-NEXT:    [[TMP2:%.*]] = insertvalue { ptr, i64 } [[TMP1]], i64 [[VAL32]], 1
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[RES_MERGED:%.*]] = phi { ptr, i64 } [ [[CALL1]], %[[BBB2]] ], [ [[CALL2]], %[[BBB3]] ], [ [[TMP2]], %[[BBB4]] ]
; CHECK-NEXT:    ret { ptr, i64 } [[RES_MERGED]]
;
  br i1 %cond1, label %bbb1, label %bbb4

bbb1:
  br i1 %cond2, label %bbb2, label %bbb3

bbb2:
  %call1 = call {ptr, i64} @bar(i64 0)
  %val11 = extractvalue { ptr, i64 } %call1, 0
  %val12 = extractvalue { ptr, i64 } %call1, 1
  br label %exit

bbb3:
  %call2 = call {ptr, i64} @bar(i64 1)
  %val21 = extractvalue { ptr, i64 } %call2, 0
  %val22 = extractvalue { ptr, i64 } %call2, 1
  br label %exit

bbb4:
  %val31 = load ptr, ptr %p1
  %val32 = load i64, ptr %p2
  br label %exit

exit:
  %val1 = phi ptr [%val11, %bbb2], [%val21, %bbb3], [%val31, %bbb4]
  %val2 = phi i64 [%val12, %bbb2], [%val22, %bbb3], [%val32, %bbb4]
  %tmp = insertvalue { ptr, i64 } poison, ptr %val1, 0
  %res = insertvalue { ptr, i64 } %tmp, i64 %val2, 1
  ret {ptr, i64} %res
}

; Test with multiple PHI instructions.
define {ptr, i64} @test3(i1 %cond1, i1 %cond2, ptr %val31, i64 %val32) {
; CHECK-LABEL: define { ptr, i64 } @test3(
; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]], ptr [[VAL31:%.*]], i64 [[VAL32:%.*]]) {
; CHECK-NEXT:    br i1 [[COND1]], label %[[BBB1:.*]], label %[[BBB4:.*]]
; CHECK:       [[BBB1]]:
; CHECK-NEXT:    br i1 [[COND2]], label %[[BBB2:.*]], label %[[BBB3:.*]]
; CHECK:       [[BBB2]]:
; CHECK-NEXT:    [[CALL1:%.*]] = call { ptr, i64 } @bar(i64 0)
; CHECK-NEXT:    br label %[[EXIT:.*]]
; CHECK:       [[BBB3]]:
; CHECK-NEXT:    [[CALL2:%.*]] = call { ptr, i64 } @bar(i64 1)
; CHECK-NEXT:    br label %[[BBB5:.*]]
; CHECK:       [[BBB4]]:
; CHECK-NEXT:    [[CALL3:%.*]] = call { ptr, i64 } @bar(i64 2)
; CHECK-NEXT:    [[TMP1:%.*]] = insertvalue { ptr, i64 } poison, ptr [[VAL31]], 0
; CHECK-NEXT:    [[TMP2:%.*]] = insertvalue { ptr, i64 } [[TMP1]], i64 [[VAL32]], 1
; CHECK-NEXT:    br label %[[BBB5]]
; CHECK:       [[BBB5]]:
; CHECK-NEXT:    [[DOTMERGED:%.*]] = phi { ptr, i64 } [ [[CALL2]], %[[BBB3]] ], [ [[TMP2]], %[[BBB4]] ]
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[RES_MERGED:%.*]] = phi { ptr, i64 } [ [[CALL1]], %[[BBB2]] ], [ [[DOTMERGED]], %[[BBB5]] ]
; CHECK-NEXT:    ret { ptr, i64 } [[RES_MERGED]]
;
  br i1 %cond1, label %bbb1, label %bbb4

bbb1:
  br i1 %cond2, label %bbb2, label %bbb3

bbb2:
  %call1 = call {ptr, i64} @bar(i64 0)
  %val11 = extractvalue { ptr, i64 } %call1, 0
  %val12 = extractvalue { ptr, i64 } %call1, 1
  br label %exit

bbb3:
  %call2 = call {ptr, i64} @bar(i64 1)
  %val21 = extractvalue { ptr, i64 } %call2, 0
  %val22 = extractvalue { ptr, i64 } %call2, 1
  br label %bbb5

bbb4:
  %call3 = call {ptr, i64} @bar(i64 2)
  br label %bbb5

bbb5:
  %val41 = phi ptr [%val21, %bbb3], [%val31, %bbb4]
  %val42 = phi i64 [%val22, %bbb3], [%val32, %bbb4]
  br label %exit

exit:
  %val1 = phi ptr [%val11, %bbb2], [%val41, %bbb5]
  %val2 = phi i64 [%val12, %bbb2], [%val42, %bbb5]
  %tmp = insertvalue { ptr, i64 } poison, ptr %val1, 0
  %res = insertvalue { ptr, i64 } %tmp, i64 %val2, 1
  ret {ptr, i64} %res
}

; Negative test, bbb4 has multiple successors, so we don't add insertvalue to it.
define {ptr, i64} @test4(i1 %cond1, i1 %cond2, ptr %p1, ptr %p2) {
; CHECK-LABEL: define { ptr, i64 } @test4(
; CHECK-SAME: i1 [[COND1:%.*]], i1 [[COND2:%.*]], ptr [[P1:%.*]], ptr [[P2:%.*]]) {
; CHECK-NEXT:    br i1 [[COND1]], label %[[BBB1:.*]], label %[[BBB4:.*]]
; CHECK:       [[BBB1]]:
; CHECK-NEXT:    br i1 [[COND2]], label %[[BBB2:.*]], label %[[BBB3:.*]]
; CHECK:       [[BBB2]]:
; CHECK-NEXT:    [[CALL1:%.*]] = call { ptr, i64 } @bar(i64 0)
; CHECK-NEXT:    [[VAL11:%.*]] = extractvalue { ptr, i64 } [[CALL1]], 0
; CHECK-NEXT:    [[VAL12:%.*]] = extractvalue { ptr, i64 } [[CALL1]], 1
; CHECK-NEXT:    br label %[[EXIT:.*]]
; CHECK:       [[BBB3]]:
; CHECK-NEXT:    [[CALL2:%.*]] = call { ptr, i64 } @bar(i64 1)
; CHECK-NEXT:    [[VAL21:%.*]] = extractvalue { ptr, i64 } [[CALL2]], 0
; CHECK-NEXT:    [[VAL22:%.*]] = extractvalue { ptr, i64 } [[CALL2]], 1
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[BBB4]]:
; CHECK-NEXT:    [[VAL31:%.*]] = load ptr, ptr [[P1]], align 8
; CHECK-NEXT:    [[VAL32:%.*]] = load i64, ptr [[P2]], align 4
; CHECK-NEXT:    [[COND3_NOT:%.*]] = icmp eq i64 [[VAL32]], 0
; CHECK-NEXT:    br i1 [[COND3_NOT]], label %[[EXIT]], label %[[BBB4]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[VAL1:%.*]] = phi ptr [ [[VAL11]], %[[BBB2]] ], [ [[VAL21]], %[[BBB3]] ], [ [[VAL31]], %[[BBB4]] ]
; CHECK-NEXT:    [[VAL2:%.*]] = phi i64 [ [[VAL12]], %[[BBB2]] ], [ [[VAL22]], %[[BBB3]] ], [ [[VAL32]], %[[BBB4]] ]
; CHECK-NEXT:    [[TMP:%.*]] = insertvalue { ptr, i64 } poison, ptr [[VAL1]], 0
; CHECK-NEXT:    [[RES:%.*]] = insertvalue { ptr, i64 } [[TMP]], i64 [[VAL2]], 1
; CHECK-NEXT:    ret { ptr, i64 } [[RES]]
;
  br i1 %cond1, label %bbb1, label %bbb4

bbb1:
  br i1 %cond2, label %bbb2, label %bbb3

bbb2:
  %call1 = call {ptr, i64} @bar(i64 0)
  %val11 = extractvalue { ptr, i64 } %call1, 0
  %val12 = extractvalue { ptr, i64 } %call1, 1
  br label %exit

bbb3:
  %call2 = call {ptr, i64} @bar(i64 1)
  %val21 = extractvalue { ptr, i64 } %call2, 0
  %val22 = extractvalue { ptr, i64 } %call2, 1
  br label %exit

bbb4:
  %val31 = load ptr, ptr %p1
  %val32 = load i64, ptr %p2
  %cond3 = icmp ne i64 %val32, 0
  br i1 %cond3, label %bbb4, label %exit

exit:
  %val1 = phi ptr [%val11, %bbb2], [%val21, %bbb3], [%val31, %bbb4]
  %val2 = phi i64 [%val12, %bbb2], [%val22, %bbb3], [%val32, %bbb4]
  %tmp = insertvalue { ptr, i64 } poison, ptr %val1, 0
  %res = insertvalue { ptr, i64 } %tmp, i64 %val2, 1
  ret {ptr, i64} %res
}

; Negative test, %.elt2 is defined in bb %end, it can't be accessed from %then,
; so we can't add insertvalue to %then.
define { ptr, i64 } @test5({ ptr, i64 } %src, ptr %pointer, i1 %cond) {
; CHECK-LABEL: define { ptr, i64 } @test5(
; CHECK-SAME: { ptr, i64 } [[SRC:%.*]], ptr [[POINTER:%.*]], i1 [[COND:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*:]]
; CHECK-NEXT:    br i1 [[COND]], label %[[THEN:.*]], label %[[ELSE:.*]]
; CHECK:       [[THEN]]:
; CHECK-NEXT:    store ptr null, ptr [[POINTER]], align 8
; CHECK-NEXT:    br label %[[END:.*]]
; CHECK:       [[ELSE]]:
; CHECK-NEXT:    [[DOTELT1:%.*]] = extractvalue { ptr, i64 } [[SRC]], 0
; CHECK-NEXT:    br label %[[END]]
; CHECK:       [[END]]:
; CHECK-NEXT:    [[TMP6:%.*]] = phi ptr [ [[DOTELT1]], %[[ELSE]] ], [ null, %[[THEN]] ]
; CHECK-NEXT:    [[DOTELT2:%.*]] = extractvalue { ptr, i64 } [[SRC]], 1
; CHECK-NEXT:    [[TMP7:%.*]] = insertvalue { ptr, i64 } zeroinitializer, ptr [[TMP6]], 0
; CHECK-NEXT:    [[TMP8:%.*]] = insertvalue { ptr, i64 } [[TMP7]], i64 [[DOTELT2]], 1
; CHECK-NEXT:    ret { ptr, i64 } [[TMP8]]
;
entry:
  br i1 %cond, label %then, label %else

then:
  store ptr null, ptr %pointer, align 8
  br label %end

else:
  %.elt1 = extractvalue { ptr, i64 } %src, 0
  br label %end

end:
  %elt = phi ptr [ %.elt1, %else ], [ null, %then ]
  %.elt2 = extractvalue { ptr, i64 } %src, 1
  %agg1 = insertvalue { ptr, i64 } zeroinitializer, ptr %elt, 0
  %res = insertvalue { ptr, i64 } %agg1, i64 %.elt2, 1
  ret { ptr, i64 } %res
}

; Negative test, we should not add insertvalue to inner loops.
define { i64, ptr } @test6({ i64, ptr } %agg1, i1 %cond1, i1 %cond2, { i64, ptr } %agg3) {
; CHECK-LABEL: define { i64, ptr } @test6(
; CHECK-SAME: { i64, ptr } [[AGG1:%.*]], i1 [[COND1:%.*]], i1 [[COND2:%.*]], { i64, ptr } [[AGG3:%.*]]) {
; CHECK-NEXT:  [[ENTRY:.*]]:
; CHECK-NEXT:    [[F10:%.*]] = extractvalue { i64, ptr } [[AGG1]], 0
; CHECK-NEXT:    [[F11:%.*]] = extractvalue { i64, ptr } [[AGG1]], 1
; CHECK-NEXT:    br label %[[HEADER:.*]]
; CHECK:       [[HEADER]]:
; CHECK-NEXT:    [[DOTSROA_01_0:%.*]] = phi i64 [ [[F10]], %[[ENTRY]] ], [ [[DOTSROA_01_1:%.*]], %[[LATCH:.*]] ]
; CHECK-NEXT:    [[DOTSROA_3_0:%.*]] = phi ptr [ [[F11]], %[[ENTRY]] ], [ [[DOTSROA_3_1:%.*]], %[[LATCH]] ]
; CHECK-NEXT:    br i1 [[COND1]], label %[[CHECK:.*]], label %[[EXIT:.*]]
; CHECK:       [[CHECK]]:
; CHECK-NEXT:    br i1 [[COND2]], label %[[THEN:.*]], label %[[ELSE:.*]]
; CHECK:       [[THEN]]:
; CHECK-NEXT:    [[F30:%.*]] = extractvalue { i64, ptr } [[AGG3]], 0
; CHECK-NEXT:    [[F31:%.*]] = extractvalue { i64, ptr } [[AGG3]], 1
; CHECK-NEXT:    br label %[[LATCH]]
; CHECK:       [[ELSE]]:
; CHECK-NEXT:    br label %[[LATCH]]
; CHECK:       [[LATCH]]:
; CHECK-NEXT:    [[DOTSROA_01_1]] = phi i64 [ [[F30]], %[[THEN]] ], [ [[DOTSROA_01_0]], %[[ELSE]] ]
; CHECK-NEXT:    [[DOTSROA_3_1]] = phi ptr [ [[F31]], %[[THEN]] ], [ [[DOTSROA_3_0]], %[[ELSE]] ]
; CHECK-NEXT:    br label %[[HEADER]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[DOTFCA_0_INSERT:%.*]] = insertvalue { i64, ptr } zeroinitializer, i64 [[DOTSROA_01_0]], 0
; CHECK-NEXT:    [[DOTFCA_1_INSERT:%.*]] = insertvalue { i64, ptr } [[DOTFCA_0_INSERT]], ptr [[DOTSROA_3_0]], 1
; CHECK-NEXT:    ret { i64, ptr } [[DOTFCA_1_INSERT]]
;
entry:
  %f10 = extractvalue { i64, ptr } %agg1, 0
  %f11 = extractvalue { i64, ptr } %agg1, 1
  br label %header

header:
  %.sroa.01.0 = phi i64 [ %f10, %entry ], [ %.sroa.01.1, %latch ]
  %.sroa.3.0 = phi ptr [ %f11, %entry ], [ %.sroa.3.1, %latch ]
  br i1 %cond1, label %check, label %exit

check:
  br i1 %cond2, label %then, label %else

then:
  %f30 = extractvalue { i64, ptr } %agg3, 0
  %f31 = extractvalue { i64, ptr } %agg3, 1
  br label %latch

else:
  br label %latch

latch:
  %.sroa.01.1 = phi i64 [ %f30, %then ], [ %.sroa.01.0, %else ]
  %.sroa.3.1 = phi ptr [ %f31, %then ], [ %.sroa.3.0, %else ]
  br label %header

exit:
  %.fca.0.insert = insertvalue { i64, ptr } zeroinitializer, i64 %.sroa.01.0, 0
  %.fca.1.insert = insertvalue { i64, ptr } %.fca.0.insert, ptr %.sroa.3.0, 1
  ret { i64, ptr } %.fca.1.insert
}

; Negative test, don't construct constant aggregate.
define {ptr, i64} @test7(i1 %cond1, ptr %p1) {
; CHECK-LABEL: define { ptr, i64 } @test7(
; CHECK-SAME: i1 [[COND1:%.*]], ptr [[P1:%.*]]) {
; CHECK-NEXT:    br i1 [[COND1]], label %[[BBB1:.*]], label %[[BBB2:.*]]
; CHECK:       [[BBB1]]:
; CHECK-NEXT:    [[CALL1:%.*]] = call { ptr, i64 } @bar(i64 0)
; CHECK-NEXT:    [[VAL11:%.*]] = extractvalue { ptr, i64 } [[CALL1]], 0
; CHECK-NEXT:    [[VAL12:%.*]] = extractvalue { ptr, i64 } [[CALL1]], 1
; CHECK-NEXT:    br label %[[EXIT:.*]]
; CHECK:       [[BBB2]]:
; CHECK-NEXT:    br label %[[EXIT]]
; CHECK:       [[EXIT]]:
; CHECK-NEXT:    [[VAL1:%.*]] = phi ptr [ [[VAL11]], %[[BBB1]] ], [ undef, %[[BBB2]] ]
; CHECK-NEXT:    [[VAL2:%.*]] = phi i64 [ [[VAL12]], %[[BBB1]] ], [ 1, %[[BBB2]] ]
; CHECK-NEXT:    [[TMP:%.*]] = insertvalue { ptr, i64 } poison, ptr [[VAL1]], 0
; CHECK-NEXT:    [[RES:%.*]] = insertvalue { ptr, i64 } [[TMP]], i64 [[VAL2]], 1
; CHECK-NEXT:    ret { ptr, i64 } [[RES]]
;
  br i1 %cond1, label %bbb1, label %bbb2

bbb1:
  %call1 = call {ptr, i64} @bar(i64 0)
  %val11 = extractvalue { ptr, i64 } %call1, 0
  %val12 = extractvalue { ptr, i64 } %call1, 1
  br label %exit

bbb2:
  br label %exit

exit:
  %val1 = phi ptr [%val11, %bbb1], [undef, %bbb2]
  %val2 = phi i64 [%val12, %bbb1], [1, %bbb2]
  %tmp = insertvalue { ptr, i64 } poison, ptr %val1, 0
  %res = insertvalue { ptr, i64 } %tmp, i64 %val2, 1
  ret {ptr, i64} %res
}