; REQUIRES: asserts
; RUN: opt -S -passes=dfa-jump-threading -verify-dom-info=1 -debug-only=dfa-jump-threading -disable-output %s 2>&1 | FileCheck %s
; RUN: opt -S -passes=dfa-jump-threading -verify-dom-info=1 -print-prof-data %s -o - | FileCheck %s --check-prefix=PROFILE

; This test checks that the analysis identifies all threadable paths in a
; simple CFG. A threadable path includes a list of basic blocks, the exit
; state, and the block that determines the next state.
; < path of BBs that form a cycle > [ state, determinator ]
define i32 @test1(i32 %num) !prof !0{
; CHECK: < case2, for.inc, for.body > [ 1, for.inc ]
; CHECK-NEXT: < for.inc, for.body > [ 1, for.inc ]
; CHECK-NEXT: < case1, for.inc, for.body > [ 2, for.inc ]
; CHECK-NEXT: < case2, sel.si.unfold.false, for.inc, for.body > [ 2, sel.si.unfold.false ]
entry:
  br label %for.body

for.body:
  %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
  %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ]
  switch i32 %state, label %for.inc [
    i32 1, label %case1
    i32 2, label %case2
  ]

case1:
  br label %for.inc

case2:
  ; PROFILE-LABEL: @test1
  ; PROFILE-LABEL: case2:
  ; PROFILE: br i1 %cmp, label %for.inc.jt1, label %sel.si.unfold.false.jt2, !prof !1 ; !1 = !{!"branch_weights", i32 3, i32 5}
  %cmp = icmp eq i32 %count, 50
  %sel = select i1 %cmp, i32 1, i32 2, !prof !1
  br label %for.inc

for.inc:
  %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ]
  %inc = add nsw i32 %count, 1
  %cmp.exit = icmp slt i32 %inc, %num
  br i1 %cmp.exit, label %for.body, label %for.end

for.end:
  ret i32 0
}

; This test checks that the analysis finds threadable paths in a more
; complicated CFG. Here the FSM is represented as a nested loop, with
; fallthrough cases.
define i32 @test2(i32 %init) {
; CHECK: < loop.1.backedge, loop.1, loop.2, loop.3 > [ 1, loop.1 ]
; CHECK-NEXT: < case4, loop.1.backedge, state.1.be2.si.unfold.false, loop.1, loop.2, loop.3 > [ 2, loop.1.backedge ]
; CHECK-NEXT: < case2, loop.1.backedge, state.1.be2.si.unfold.false, loop.1, loop.2, loop.3 > [ 4, loop.1.backedge ]
; CHECK-NEXT: < case4, loop.2.backedge, loop.2, loop.3 > [ 3, loop.2.backedge ]
; CHECK-NEXT: < case3, loop.2.backedge, loop.2, loop.3 > [ 0, loop.2.backedge ]
; CHECK-NEXT: < case2, loop.3 > [ 3, loop.3 ]
entry:
  %cmp = icmp eq i32 %init, 0
  %sel = select i1 %cmp, i32 0, i32 2
  br label %loop.1

loop.1:
  %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ]
  br label %loop.2

loop.2:
  %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
  br label %loop.3

loop.3:
  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
  switch i32 %state, label %infloop.i [
    i32 2, label %case2
    i32 3, label %case3
    i32 4, label %case4
    i32 0, label %case0
    i32 1, label %case1
  ]

case2:
  br i1 %cmp, label %loop.3, label %loop.1.backedge

case3:
  br i1 %cmp, label %loop.2.backedge, label %case4

case4:
  br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge

loop.1.backedge:
  %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
  %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
  br label %loop.1

loop.2.backedge:
  %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
  br label %loop.2

case0:
  br label %exit

case1:
  br label %exit

infloop.i:
  br label %infloop.i

exit:
  ret i32 0
}

declare void @baz()

; Do not jump-thread those paths where the determinator basic block does not
; precede the basic block that defines the switch condition.
;
; Otherwise, it is possible that the state defined in the determinator block
; defines the state for the next iteration of the loop, rather than for the
; current one.
define i32 @wrong_bb_order() {
; CHECK-LABEL: DFA Jump threading: wrong_bb_order
; CHECK-NOT: [ 77, bb43 ]
; CHECK-NOT: [ 77, bb43 ]
bb:
  %i = alloca [420 x i8], align 1
  %i2 = getelementptr inbounds [420 x i8], ptr %i, i64 0, i64 390
  br label %bb3

bb3:                                              ; preds = %bb59, %bb
  %i4 = phi ptr [ %i2, %bb ], [ %i60, %bb59 ]
  %i5 = phi i8 [ 77, %bb ], [ %i64, %bb59 ]
  %i6 = phi i32 [ 2, %bb ], [ %i63, %bb59 ]
  %i7 = phi i32 [ 26, %bb ], [ %i62, %bb59 ]
  %i8 = phi i32 [ 25, %bb ], [ %i61, %bb59 ]
  %i9 = icmp sgt i32 %i7, 2
  %i10 = select i1 %i9, i32 %i7, i32 2
  %i11 = add i32 %i8, 2
  %i12 = sub i32 %i11, %i10
  %i13 = mul nsw i32 %i12, 3
  %i14 = add nsw i32 %i13, %i6
  %i15 = sext i32 %i14 to i64
  %i16 = getelementptr inbounds i8, ptr %i4, i64 %i15
  %i17 = load i8, ptr %i16, align 1
  %i18 = icmp sgt i8 %i17, 0
  br i1 %i18, label %bb21, label %bb31

bb21:                                             ; preds = %bb3
  br i1 true, label %bb59, label %bb43

bb59:                                             ; preds = %bb49, %bb43, %bb31, %bb21
  %i60 = phi ptr [ %i44, %bb49 ], [ %i44, %bb43 ], [ %i34, %bb31 ], [ %i4, %bb21 ]
  %i61 = phi i32 [ %i45, %bb49 ], [ %i45, %bb43 ], [ %i33, %bb31 ], [ %i8, %bb21 ]
  %i62 = phi i32 [ %i47, %bb49 ], [ %i47, %bb43 ], [ %i32, %bb31 ], [ %i7, %bb21 ]
  %i63 = phi i32 [ %i48, %bb49 ], [ %i48, %bb43 ], [ 2, %bb31 ], [ %i6, %bb21 ]
  %i64 = phi i8 [ %i46, %bb49 ], [ %i46, %bb43 ], [ 77, %bb31 ], [ %i5, %bb21 ]
  %i65 = icmp sgt i32 %i62, 0
  br i1 %i65, label %bb3, label %bb66

bb31:                                             ; preds = %bb3
  %i32 = add nsw i32 %i7, -1
  %i33 = add nsw i32 %i8, -1
  %i34 = getelementptr inbounds i8, ptr %i4, i64 -15
  %i35 = icmp eq i8 %i5, 77
  br i1 %i35, label %bb59, label %bb41

bb41:                                             ; preds = %bb31
  tail call void @baz()
  br label %bb43

bb43:                                             ; preds = %bb41, %bb21
  %i44 = phi ptr [ %i34, %bb41 ], [ %i4, %bb21 ]
  %i45 = phi i32 [ %i33, %bb41 ], [ %i8, %bb21 ]
  %i46 = phi i8 [ 77, %bb41 ], [ %i5, %bb21 ]
  %i47 = phi i32 [ %i32, %bb41 ], [ %i7, %bb21 ]
  %i48 = phi i32 [ 2, %bb41 ], [ %i6, %bb21 ]
  tail call void @baz()
  switch i8 %i5, label %bb59 [
    i8 68, label %bb49
    i8 73, label %bb49
  ]

bb49:                                             ; preds = %bb43, %bb43
  tail call void @baz()
  br label %bb59

bb66:                                             ; preds = %bb59
  ret i32 0
}

; Value %init is not predictable but it's okay since it is the value initial to the switch.
define i32 @initial.value.positive1(i32 %init) !prof !0 {
; CHECK: < loop.1.backedge, loop.1, loop.2, loop.3 > [ 1, loop.1 ]
; CHECK-NEXT: < case4, loop.1.backedge, state.1.be2.si.unfold.false, loop.1, loop.2, loop.3 > [ 2, loop.1.backedge ]
; CHECK-NEXT: < case2, loop.1.backedge, state.1.be2.si.unfold.false, loop.1, loop.2, loop.3 > [ 4, loop.1.backedge ]
; CHECK-NEXT: < case4, loop.2.backedge, loop.2, loop.3 > [ 3, loop.2.backedge ]
; CHECK-NEXT: < case3, loop.2.backedge, loop.2, loop.3 > [ 0, loop.2.backedge ]
; CHECK-NEXT: < case2, loop.3 > [ 3, loop.3 ]
entry:
  %cmp = icmp eq i32 %init, 0
  br label %loop.1

loop.1:
  %state.1 = phi i32 [ %init, %entry ], [ %state.1.be2, %loop.1.backedge ]
  br label %loop.2

loop.2:
  %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ]
  br label %loop.3

loop.3:
  %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ]
  switch i32 %state, label %infloop.i [
    i32 2, label %case2
    i32 3, label %case3
    i32 4, label %case4
    i32 0, label %case0
    i32 1, label %case1
  ]

case2:
  br i1 %cmp, label %loop.3, label %loop.1.backedge

case3:
  br i1 %cmp, label %loop.2.backedge, label %case4

case4:
  br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge

loop.1.backedge:
  %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ]
  %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be
  br label %loop.1

loop.2.backedge:
  %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ]
  br label %loop.2

case0:
  br label %exit

case1:
  br label %exit

infloop.i:
  br label %infloop.i

exit:
  ret i32 0
}

define i8 @cyclesInPaths1(i1 %call12, i1 %cmp18) {
; CHECK-LABEL: DFA Jump threading: cyclesInPaths1
; CHECK-NOT: <{{.*}}> [{{.*}}]

entry:
  br label %switchPhiDef.for.body

switchPhiDef.for.body:                                         ; preds = %detBB2, %entry
  %switchPhi.curState = phi i32 [ %curState.1, %detBB2 ], [ 0, %entry ]
  br i1 %call12, label %detBB1, label %if.else

if.else:                                          ; preds = %switchPhiDef.for.body
  br label %detBB1

detBB1:                                         ; preds = %if.else, %switchPhiDef.for.body
  %newState.02 = phi i32 [ 2, %switchPhiDef.for.body ], [ 4, %if.else ]
  br i1 %cmp18, label %detBB2, label %if.end20

if.end20:                                         ; preds = %detBB1
  br i1 %call12, label %if.end23, label %switchBB

switchBB:                                        ; preds = %if.end20
  switch i32 %switchPhi.curState, label %if.end23 [
    i32 4, label %ret1
    i32 0, label %ret2
  ]

ret1:                                       ; preds = %switchBB
  ret i8 1

ret2:                                       ; preds = %switchBB
  ret i8 2

if.end23:                                         ; preds = %switchBB, %if.end20
  br label %detBB2

detBB2:                                          ; preds = %if.end23, %detBB1
  %curState.1 = phi i32 [ %newState.02, %if.end23 ], [ 0, %detBB1 ]
  br label %switchPhiDef.for.body
}

define void @cyclesInPaths2(i1 %tobool5.not.i) {
; CHECK-LABEL: DFA Jump threading: cyclesInPaths2
; CHECK: < sw.bb.i, bb.exit, if.end5, if.end.i > [ 1, bb.exit ]
; CHECK-NEXT: < bb.exit, if.end5, if.end.i > [ 0, bb.exit ]

entry:
  br label %if.end5

if.end5:                                          ; preds = %bb.exit, %entry
  %P.sroa.8.051 = phi i16 [ %retval.sroa.6.0.i, %bb.exit ], [ 0, %entry ]
  call void @foo3()
  br i1 %tobool5.not.i, label %if.end.i, label %bb.exit

if.end.i:                                         ; preds = %if.end5
  switch i16 %P.sroa.8.051, label %sw.default.i [
    i16 1, label %sw.bb.i
    i16 0, label %bb.exit
  ]

sw.bb.i:                                          ; preds = %if.end.i
  call void @foo1()
  br label %bb.exit

sw.default.i:                                     ; preds = %if.end.i
  unreachable

bb.exit: ; preds = %sw.bb.i, %if.end.i, %if.end5
  %retval.sroa.6.0.i = phi i16 [ 1, %sw.bb.i ], [ 0, %if.end5 ], [ 0, %if.end.i ]
  call void @foo2()
  br label %if.end5
}

declare void @foo1()
declare void @foo2()
declare void @foo3()

!0 = !{!"function_entry_count", i32 10}
!1 = !{!"branch_weights", i32 3, i32 5}