; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; Test merging of blocks with phi nodes.
;
; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s
;

; ModuleID = '<stdin>'
declare i1 @foo()

declare i1 @bar(i32)

define i32 @test(i1 %a) {
; CHECK-LABEL: @test(
; CHECK-NEXT:  Q:
; CHECK-NEXT:    [[R:%.*]] = add i32 2, 1
; CHECK-NEXT:    ret i32 [[R]]
;
Q:
  br i1 %a, label %N, label %M
N:              ; preds = %Q
  br label %M
M:              ; preds = %N, %Q
  ; It's ok to merge N and M because the incoming values for W are the
  ; same for both cases...
  %W = phi i32 [ 2, %N ], [ 2, %Q ]               ; <i32> [#uses=1]
  %R = add i32 %W, 1              ; <i32> [#uses=1]
  ret i32 %R
}

; Test merging of blocks with phi nodes where at least one incoming value
; in the successor is undef.
define i8 @testundef(i32 %u) {
; CHECK-LABEL: @testundef(
; CHECK-NEXT:  R:
; CHECK-NEXT:    [[U_OFF:%.*]] = add i32 [[U:%.*]], -1
; CHECK-NEXT:    [[SWITCH:%.*]] = icmp ult i32 [[U_OFF]], 2
; CHECK-NEXT:    [[SPEC_SELECT:%.*]] = select i1 [[SWITCH]], i8 1, i8 0
; CHECK-NEXT:    ret i8 [[SPEC_SELECT]]
;
R:
  switch i32 %u, label %U [
  i32 0, label %S
  i32 1, label %T
  i32 2, label %T
  ]

S:                                            ; preds = %R
  br label %U

T:                                           ; preds = %R, %R
  br label %U

U:                                        ; preds = %T, %S, %R
  ; We should be able to merge either the S or T block into U by rewriting
  ; R's incoming value with the incoming value of that predecessor since
  ; R's incoming value is undef and both of those predecessors are simple
  ; unconditional branches.
  %val.0 = phi i8 [ undef, %R ], [ 1, %T ], [ 0, %S ]
  ret i8 %val.0
}

; Test merging of blocks with phi nodes where at least one incoming value
; in the successor is undef.
define i8 @testundef2(i32 %u, i32* %A) {
; CHECK-LABEL: @testundef2(
; CHECK-NEXT:  V:
; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32 [[U:%.*]], 3
; CHECK-NEXT:    br i1 [[COND]], label [[Z:%.*]], label [[U:%.*]]
; CHECK:       Z:
; CHECK-NEXT:    store i32 0, i32* [[A:%.*]], align 4
; CHECK-NEXT:    br label [[U]]
; CHECK:       U:
; CHECK-NEXT:    ret i8 1
;
V:
  switch i32 %u, label %U [
  i32 0, label %W
  i32 1, label %X
  i32 2, label %X
  i32 3, label %Z
  ]

W:                                            ; preds = %V
  br label %U

Z:
  store i32 0, i32* %A, align 4
  br label %X

X:                                           ; preds = %V, %V, %Z
  br label %U

U:                                        ; preds = %X, %W, %V
  ; We should be able to merge either the W or X block into U by rewriting
  ; V's incoming value with the incoming value of that predecessor since
  ; V's incoming value is undef and both of those predecessors are simple
  ; unconditional branches. Note that X has predecessors beyond
  ; the direct predecessors of U.
  %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 1, %W ]
  ret i8 %val.0
}

define i8 @testmergesome(i32 %u, i32* %A) {
; CHECK-LABEL: @testmergesome(
; CHECK-NEXT:  V:
; CHECK-NEXT:    switch i32 [[U:%.*]], label [[Y:%.*]] [
; CHECK-NEXT:    i32 0, label [[W:%.*]]
; CHECK-NEXT:    i32 3, label [[Z:%.*]]
; CHECK-NEXT:    ]
; CHECK:       W:
; CHECK-NEXT:    store i32 1, i32* [[A:%.*]], align 4
; CHECK-NEXT:    br label [[Y]]
; CHECK:       Z:
; CHECK-NEXT:    store i32 0, i32* [[A]], align 4
; CHECK-NEXT:    br label [[Y]]
; CHECK:       Y:
; CHECK-NEXT:    [[VAL_0:%.*]] = phi i8 [ 2, [[W]] ], [ 1, [[Z]] ], [ 1, [[V:%.*]] ]
; CHECK-NEXT:    ret i8 [[VAL_0]]
;
V:
  switch i32 %u, label %Y [
  i32 0, label %W
  i32 1, label %X
  i32 2, label %X
  i32 3, label %Z
  ]

W:                                            ; preds = %V
  store i32 1, i32* %A, align 4
  br label %Y

Z:
  store i32 0, i32* %A, align 4
  br label %X

X:                                           ; preds = %V, %Z
  br label %Y

Y:                                        ; preds = %X, %W, %V
  ; After merging X into Y, we should have 5 predecessors
  ; and thus 5 incoming values to the phi.
  %val.0 = phi i8 [ 1, %V ], [ 1, %X ], [ 2, %W ]
  ret i8 %val.0
}


define i8 @testmergesome2(i32 %u, i32* %A) {
; CHECK-LABEL: @testmergesome2(
; CHECK-NEXT:  V:
; CHECK-NEXT:    switch i32 [[U:%.*]], label [[W:%.*]] [
; CHECK-NEXT:    i32 4, label [[Y:%.*]]
; CHECK-NEXT:    i32 1, label [[Y]]
; CHECK-NEXT:    i32 2, label [[Y]]
; CHECK-NEXT:    ]
; CHECK:       W:
; CHECK-NEXT:    store i32 1, i32* [[A:%.*]], align 4
; CHECK-NEXT:    br label [[Y]]
; CHECK:       Y:
; CHECK-NEXT:    [[VAL_0:%.*]] = phi i8 [ 1, [[V:%.*]] ], [ 2, [[W]] ], [ 1, [[V]] ], [ 1, [[V]] ]
; CHECK-NEXT:    ret i8 [[VAL_0]]
;
V:
  switch i32 %u, label %W [
  i32 0, label %W
  i32 1, label %Y
  i32 2, label %X
  i32 4, label %Y
  ]

W:                                            ; preds = %V
  store i32 1, i32* %A, align 4
  br label %Y

X:                                           ; preds = %V, %Z
  br label %Y

Y:                                        ; preds = %X, %W, %V
  ; Ensure that we deal with both undef inputs for V when we merge in X.
  %val.0 = phi i8 [ undef, %V ], [ 1, %X ], [ 2, %W ], [ undef, %V ]
  ret i8 %val.0
}

; This function can't be merged
define void @a() {
; CHECK-LABEL: @a(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
; CHECK:       BB.nomerge:
; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[COMMON:%.*]] ]
; CHECK-NEXT:    br label [[SUCC:%.*]]
; CHECK:       Succ:
; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[A]], [[BB_NOMERGE]] ], [ 2, [[COMMON]] ]
; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[EXIT:%.*]]
; CHECK:       Common:
; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
; CHECK:       Exit:
; CHECK-NEXT:    ret void
;
entry:
  br label %BB.nomerge

BB.nomerge:		; preds = %Common, %entry
  ; This phi has a conflicting value (0) with below phi (2), so blocks
  ; can't be merged.
  %a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
  br label %Succ

Succ:		; preds = %Common, %BB.nomerge
  %b = phi i32 [ %a, %BB.nomerge ], [ 2, %Common ]		; <i32> [#uses=0]
  %conde = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %conde, label %Common, label %Exit

Common:		; preds = %Succ
  %cond = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %cond, label %BB.nomerge, label %Succ

Exit:		; preds = %Succ
  ret void
}

; This function can't be merged
define void @b() {
; CHECK-LABEL: @b(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
; CHECK:       BB.nomerge:
; CHECK-NEXT:    br label [[SUCC:%.*]]
; CHECK:       Succ:
; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 1, [[BB_NOMERGE]] ], [ 2, [[COMMON:%.*]] ]
; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[EXIT:%.*]]
; CHECK:       Common:
; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
; CHECK:       Exit:
; CHECK-NEXT:    ret void
;
entry:
  br label %BB.nomerge

BB.nomerge:		; preds = %Common, %entry
  br label %Succ

Succ:		; preds = %Common, %BB.nomerge
  ; This phi has confliction values for Common and (through BB) Common,
  ; blocks can't be merged
  %b = phi i32 [ 1, %BB.nomerge ], [ 2, %Common ]		; <i32> [#uses=0]
  %conde = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %conde, label %Common, label %Exit

Common:		; preds = %Succ
  %cond = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %cond, label %BB.nomerge, label %Succ

Exit:		; preds = %Succ
  ret void
}

; This function can't be merged (for keeping canonical loop structures)
define void @c() {
; CHECK-LABEL: @c(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
; CHECK:       BB.nomerge:
; CHECK-NEXT:    br label [[SUCC:%.*]]
; CHECK:       Succ:
; CHECK-NEXT:    [[B:%.*]] = phi i32 [ 1, [[BB_NOMERGE]] ], [ 1, [[COMMON:%.*]] ], [ 2, [[PRE_EXIT:%.*]] ]
; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[PRE_EXIT]]
; CHECK:       Common:
; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
; CHECK:       Pre-Exit:
; CHECK-NEXT:    [[COND2:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[COND2]], label [[SUCC]], label [[EXIT:%.*]]
; CHECK:       Exit:
; CHECK-NEXT:    ret void
;
entry:
  br label %BB.nomerge

BB.nomerge:		; preds = %Common, %entry
  br label %Succ

Succ:		; preds = %Common, %BB.tomerge, %Pre-Exit
  ; This phi has identical values for Common and (through BB) Common,
  ; blocks can't be merged
  %b = phi i32 [ 1, %BB.nomerge ], [ 1, %Common ], [ 2, %Pre-Exit ]
  %conde = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %conde, label %Common, label %Pre-Exit

Common:		; preds = %Succ
  %cond = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %cond, label %BB.nomerge, label %Succ

Pre-Exit:       ; preds = %Succ
  ; This adds a backedge, so the %b phi node gets a third branch and is
  ; not completely trivial
  %cond2 = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %cond2, label %Succ, label %Exit

Exit:		; preds = %Pre-Exit
  ret void
}

; This function can't be merged (for keeping canonical loop structures)
define void @d() {
; CHECK-LABEL: @d(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[BB_NOMERGE:%.*]]
; CHECK:       BB.nomerge:
; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[COMMON:%.*]] ]
; CHECK-NEXT:    br label [[SUCC:%.*]]
; CHECK:       Succ:
; CHECK-NEXT:    [[B:%.*]] = phi i32 [ [[A]], [[BB_NOMERGE]] ], [ 0, [[COMMON]] ]
; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[CONDE]], label [[COMMON]], label [[EXIT:%.*]]
; CHECK:       Common:
; CHECK-NEXT:    [[COND:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[COND]], label [[BB_NOMERGE]], label [[SUCC]]
; CHECK:       Exit:
; CHECK-NEXT:    ret void
;
entry:
  br label %BB.nomerge

BB.nomerge:		; preds = %Common, %entry
  ; This phi has a matching value (0) with below phi (0), so blocks
  ; can be merged.
  %a = phi i32 [ 1, %entry ], [ 0, %Common ]		; <i32> [#uses=1]
  br label %Succ

Succ:		; preds = %Common, %BB.tomerge
  %b = phi i32 [ %a, %BB.nomerge ], [ 0, %Common ]		; <i32> [#uses=0]
  %conde = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %conde, label %Common, label %Exit

Common:		; preds = %Succ
  %cond = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %cond, label %BB.nomerge, label %Succ

Exit:		; preds = %Succ
  ret void
}

; This function can be merged
define void @e() {
; CHECK-LABEL: @e(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[SUCC:%.*]]
; CHECK:       Succ:
; CHECK-NEXT:    [[A:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ 0, [[USE:%.*]] ]
; CHECK-NEXT:    [[CONDE:%.*]] = call i1 @foo()
; CHECK-NEXT:    br i1 [[CONDE]], label [[USE]], label [[EXIT:%.*]]
; CHECK:       Use:
; CHECK-NEXT:    [[COND:%.*]] = call i1 @bar(i32 [[A]])
; CHECK-NEXT:    br i1 [[COND]], label [[SUCC]], label [[EXIT]]
; CHECK:       Exit:
; CHECK-NEXT:    ret void
;
entry:
  br label %Succ

Succ:		; preds = %Use, %entry
  ; This phi is used somewhere else than Succ, but this should not prevent
  ; merging this block
  %a = phi i32 [ 1, %entry ], [ 0, %Use ]		; <i32> [#uses=1]
  br label %BB.tomerge

BB.tomerge:		; preds = %Succ
  %conde = call i1 @foo( )		; <i1> [#uses=1]
  br i1 %conde, label %Use, label %Exit

Use:		; preds = %Succ
  %cond = call i1 @bar( i32 %a )		; <i1> [#uses=1]
  br i1 %cond, label %Succ, label %Exit

Exit:		; preds = %Use, %Succ
  ret void
}