// RUN: %target-sil-opt -enable-sil-verify-all %s -jumpthread-simplify-cfg | %FileCheck %s

// Test dominator-based jump-threading with OSSA. This requires
// -jumpthread-simplify-cfg to enable dominator-based
// jump-threading.

sil_stage canonical

import Builtin
import Swift
import SwiftShims

// Includes an OSSA form of a test from simplify_cfg_opaque.sil
// ...along with new OSSA test cases.

class C {
  @_hasStorage @_hasInitialValue var field: Int { get set }
  init()

  func method() -> Any
  func f() -> FakeOptional<T>
}

sil @getC : $@convention(thin) () -> C

// Test multiple uses and cloned allocation.
//
// project_box and struct_extract_addr will be sunk into three
// different blocks, but only once per block.
struct S {
  @_hasStorage @_hasInitialValue var x: Int { get set }
  init(x: Int = 0)
  init()
}
sil @doNothing : $@convention(thin) (@inout Int) -> ()

enum FakeOptional<T> {
case some(T)
case none
}

struct T {
    let s: S
}

enum E {
	case A
	case B
	case C
}

class Base { }

class Derived1 : Base { }

class Derived2 : Base { }

// Test that jump threading sinks a
// ref_tail_addr->index_addr->struct_element_addr chain and generates
// a phi for the index_addr's index operand.
//
// The retain on separate paths followed by a merged release, and
// target block with a conditional branch are necessary just to get
// jump threading to kick in.
//
// CHECK-LABEL: sil @testJumpThreadIndex : $@convention(thin) (__ContiguousArrayStorageBase, Builtin.Int64) -> Builtin.Int32 {
// CHECK: bb0(%0 : $__ContiguousArrayStorageBase, %1 : $Builtin.Int64):
// CHECK:   cond_br undef, bb2, bb1
// CHECK: bb1:
// CHECK:   apply
// CHECK:   strong_retain
// CHECK:   strong_release
// CHECK:   [[IDX2:%.*]] = builtin "truncOrBitCast_Int64_Word"(%1 : $Builtin.Int64) : $Builtin.Word
// CHECK:   br bb3([[IDX2]] : $Builtin.Word)
// CHECK: bb2:
// CHECK:   apply
// CHECK:   strong_retain
// CHECK:   strong_release
// CHECK:   [[IDX1:%.*]] = builtin "truncOrBitCast_Int64_Word"(%1 : $Builtin.Int64) : $Builtin.Word
// CHECK:   br bb3([[IDX1]] : $Builtin.Word)
// CHECK: bb3([[PHI:%.*]] : $Builtin.Word):
// CHECK:   [[TAIL:%.*]] = ref_tail_addr %0 : $__ContiguousArrayStorageBase, $Int32
// CHECK:   [[ELT:%.*]] = index_addr [[TAIL]] : $*Int32, %14 : $Builtin.Word
// CHECK:   [[ADR:%.*]] = struct_element_addr [[ELT]] : $*Int32, #Int32._value
// CHECK:   load [[ADR]] : $*Builtin.Int32
// CHECK:   cond_br undef, bb4, bb5
// CHECK-LABEL: } // end sil function 'testJumpThreadIndex'
sil @testJumpThreadIndex : $@convention(thin) (__ContiguousArrayStorageBase, Builtin.Int64) -> Builtin.Int32 {
bb0(%0 : $__ContiguousArrayStorageBase, %1 : $Builtin.Int64):
  %f = function_ref @getC : $@convention(thin) () -> C
  cond_br undef, bb1, bb2

bb1:
  %c1 = apply %f() : $@convention(thin) ()->C
  strong_retain %c1 : $C
  br bb3(%c1 : $C)

bb2:
  %c2 = apply %f() : $@convention(thin) ()->C
  strong_retain %c2 : $C
  br bb3(%c2 : $C)

bb3(%arg : $C):
  strong_release %arg : $C
  %tail = ref_tail_addr %0 : $__ContiguousArrayStorageBase, $Int32
  %idx = builtin "truncOrBitCast_Int64_Word"(%1 : $Builtin.Int64) : $Builtin.Word
  %elt = index_addr %tail : $*Int32, %idx : $Builtin.Word
  %adr = struct_element_addr %elt : $*Int32, #Int32._value
  br bb4

bb4:
  %val = load %adr : $*Builtin.Int32
  cond_br undef, bb4, bb5

bb5:
  return %val : $Builtin.Int32
}

// CHECK-LABEL: sil @testMultiUse : $@convention(method) (Bool, @inout Int) -> () {
// CHECK: bb0(%0 : $Bool, %1 : $*Int):
// CHECK:   cond_br %{{.*}}, bb1, bb2
// CHECK: bb1:
// CHECK:   apply %{{.*}}(%1) : $@convention(thin) (@inout Int) -> ()
// CHECK:   [[ALLOC2:%.*]] = alloc_box ${ var S }, var, name "s"
// CHECK:   [[PROJ2:%.*]] = project_box [[ALLOC2]] : ${ var S }, 0
// CHECK:   [[ADR2:%.*]] = struct_element_addr [[PROJ2]] : $*S, #S.x
// CHECK:   store %{{.*}} to [[ADR2]] : $*Int
// CHECK:   apply %{{.*}}([[ADR2]]) : $@convention(thin) (@inout Int) -> ()
// CHECK:   br bb3([[ALLOC2]] : ${ var S })
// CHECK: bb2:
// CHECK:   [[ALLOC1:%.*]] = alloc_box ${ var S }, var, name "s"
// CHECK:   [[PROJ1:%.*]] = project_box [[ALLOC1]] : ${ var S }, 0
// CHECK:   [[ADR1:%.*]] = struct_element_addr [[PROJ1]] : $*S, #S.x
// CHECK:   store %{{.*}} to [[ADR1]] : $*Int
// CHECK:   br bb3([[ALLOC1]] : ${ var S })
// CHECK: bb3([[BOXARG:%.*]] : ${ var S }):
// CHECK:   [[PROJ3:%.*]] = project_box [[BOXARG]] : ${ var S }, 0
// CHECK:   [[ADR3:%.*]] = struct_element_addr [[PROJ3]] : $*S, #S.x
// CHECK:   apply %{{.*}}([[ADR3]]) : $@convention(thin) (@inout Int) -> ()
// CHECK:   release_value [[BOXARG]] : ${ var S }
// CHECK-LABEL: } // end sil function 'testMultiUse'
sil @testMultiUse : $@convention(method) (Bool, @inout Int) -> () {
bb0(%0 : $Bool, %1 : $*Int):
  %bool = struct_extract %0 : $Bool, #Bool._value
  cond_br %bool, bb1, bb2

bb1:
  %f1 = function_ref @doNothing : $@convention(thin) (@inout Int) -> ()
  %call1 = apply %f1(%1) : $@convention(thin) (@inout Int) -> ()
  br bb3

bb2:
  br bb3

bb3:
  %box3 = alloc_box ${ var S }, var, name "s"
  %proj3 = project_box %box3 : ${ var S }, 0
  %adr3 = struct_element_addr %proj3 : $*S, #S.x
  cond_br %bool, bb4, bb5

bb4:
  %i4 = load %1 : $*Int
  store %i4 to %adr3 : $*Int
  %f2 = function_ref @doNothing : $@convention(thin) (@inout Int) -> ()
  %call2 = apply %f2(%adr3) : $@convention(thin) (@inout Int) -> ()
  br bb6

bb5:
  %i5 = load %1 : $*Int
  store %i5 to %adr3 : $*Int
  br bb6

bb6:
  %f6 = function_ref @doNothing : $@convention(thin) (@inout Int) -> ()
  %call6 = apply %f6(%adr3) : $@convention(thin) (@inout Int) -> ()
  release_value %box3 : ${ var S }
  %z = tuple ()
  return %z : $()
}

// CHECK-LABEL: sil @test_jump_threading
// CHECK: bb5(%{{[0-9]+}} : $Builtin.Int64):
// CHECK-NEXT: br bb1
sil @test_jump_threading : $@convention(thin)  (Builtin.Int1) -> () {
bb0(%0 : $Builtin.Int1):
  cond_br %0, bb2, bb3

// Blocks are handled from last to first. Block bb1 is placed here so that its argument
// is not optimized before jump threading is done in bb2 and bb3.
bb1(%i4 : $Builtin.Int64):
  %f3 = function_ref @get_condition : $@convention(thin)  (Builtin.Int64) -> Builtin.Int1
  %c1 = apply %f3(%i3) : $@convention(thin)  (Builtin.Int64) -> Builtin.Int1
  %i5 = integer_literal $Builtin.Int64, 27
  cond_br %c1, bb1(%i5 : $Builtin.Int64), bb5

bb2:
  %f1 = function_ref @get_int1 : $@convention(thin)  () -> Builtin.Int64
  %i1 = apply %f1() : $@convention(thin)  () -> Builtin.Int64
  br bb4(%i1 : $Builtin.Int64)

bb3:
  %f2 = function_ref @get_int1 : $@convention(thin)  () -> Builtin.Int64
  %i2 = apply %f2() : $@convention(thin)  () -> Builtin.Int64
  br bb4(%i2 : $Builtin.Int64)

// Jump threading must not be done for this block because the argument %i3 is also
// used in bb1.
bb4(%i3 : $Builtin.Int64):
  br bb1(%i3 : $Builtin.Int64)

bb5:
  %r1 = tuple ()
  return %r1 : $()

}

sil @get_int1 : $@convention(thin)  () -> Builtin.Int64
sil @get_int2 : $@convention(thin)  () -> Builtin.Int64
sil @get_condition : $@convention(thin)  (Builtin.Int64) -> Builtin.Int1


public final class AA {
}
public final class BB {
  @_hasStorage internal weak final var n:  BB!
  @_hasStorage internal final var o: AA!
}

// Test that SimplifyCFG does not hang when compiling an infinite loop with switch_enum.
// CHECK-LABEL: test_infinite_loop
sil hidden @test_infinite_loop : $@convention(method) (@owned BB) -> () {
bb0(%0 : $BB):
  %31 = enum $Optional<BB>, #Optional.some!enumelt, %0 : $BB
  br bb4(%31 : $Optional<BB>)

bb4(%36 : $Optional<BB>):
  switch_enum %36 : $Optional<BB>, case #Optional.some!enumelt: bb6, default bb5

bb5:
  br bb7

bb6:
  %39 = unchecked_enum_data %36 : $Optional<BB>, #Optional.some!enumelt
  %40 = ref_element_addr %39 : $BB, #BB.o
  %41 = load %40 : $*Optional<AA>
  release_value %41 : $Optional<AA>
  br bb7

bb7:
  switch_enum %36 : $Optional<BB>, case #Optional.none!enumelt: bb8, case #Optional.some!enumelt: bb9

bb8:
  br bb4(%36 : $Optional<BB>)

bb9:
  %48 = unchecked_enum_data %36 : $Optional<BB>, #Optional.some!enumelt
  %49 = ref_element_addr %48 : $BB, #BB.n
  %50 = load_weak %49 : $*@sil_weak Optional<BB>
  release_value %36 : $Optional<BB>
  switch_enum %50 : $Optional<BB>, case #Optional.some!enumelt: bb11, case #Optional.none!enumelt: bb10

bb10:
  br bb4(%50 : $Optional<BB>)

bb11:
  %54 = unchecked_enum_data %50 : $Optional<BB>, #Optional.some!enumelt
  %55 = ref_to_raw_pointer %54 : $BB to $Builtin.RawPointer
  %56 = ref_to_raw_pointer %0 : $BB to $Builtin.RawPointer
  %57 = builtin "cmp_eq_RawPointer"(%55 : $Builtin.RawPointer, %56 : $Builtin.RawPointer) : $Builtin.Int1
  cond_br %57, bb13, bb12

bb12:
  br bb4(%50 : $Optional<BB>)

bb13:
  release_value %50 : $Optional<BB>
  strong_release %0 : $BB
  %65 = tuple ()
  return %65 : $()
}

sil @some_function : $@convention(thin) (AA) -> Optional<AA>

// Another test for checking that SimplifyCFG does not hang.
// CHECK-LABEL: test_other_infinite_loop
sil hidden @test_other_infinite_loop : $@convention(method) (@owned AA) -> () {
bb0(%5 : $AA):
  strong_retain %5 : $AA
  %6 = enum $Optional<AA>, #Optional.some!enumelt, %5 : $AA
  br bb1(%6 : $Optional<AA>)

bb1(%8 : $Optional<AA>):
  retain_value %8 : $Optional<AA>
  switch_enum %8 : $Optional<AA>, case #Optional.some!enumelt: bb3, default bb2

bb2:
  release_value %8 : $Optional<AA>
  br bb6

bb3:
  cond_br undef, bb4, bb5

bb4:
  %85 = tuple ()
  return %85 : $()

bb5:
  br bb6

bb6:
  switch_enum %8 : $Optional<AA>, case #Optional.none!enumelt: bb7, default bb8

bb7:
  br bb9(%8 : $Optional<AA>)

bb8:
  %23 = unchecked_enum_data %8 : $Optional<AA>, #Optional.some!enumelt
  strong_retain %23 : $AA
  %25 = function_ref @some_function : $@convention(thin) (AA) -> Optional<AA>
  %26 = apply %25(%23) : $@convention(thin) (AA) -> Optional<AA>
  strong_release %23 : $AA
  br bb9(%26 : $Optional<AA>)

bb9(%29 : $Optional<AA>):
  release_value %8 : $Optional<AA>
  br bb1(%29 : $Optional<AA>)

}

// -----------------------------------------------------------------------------
// Test jump-threading through a non-pure address producer.
//
// BB3 cannot (currently) be cloned because the block cloner does not
// know how to sink address producers unless they are pure address
// projections. init_existential_addr is not a pure projection. It's
// address is transitively used outside bb3 via %17 =
// tuple_element_addr. Test that cloning is inhibited. If cloning did
// happen, then it would either need to sink init_existential_addr, or
// SSA would be incorrectly updated.

// Make BB3 is not jump-threaded. And init_existential_addr is not cloned
//
// CHECK-LABEL: sil hidden @nonPureAddressProducer : $@convention(method) (@guaranteed C) -> @out Any {
// CHECK: bb0(%0 : $*Any, %1 : $C):
// CHECK:   switch_enum %{{.*}} : $FakeOptional<T>, case #FakeOptional.some!enumelt: bb1, case #FakeOptional.none!enumelt: bb2
// CHECK: bb3(%{{.*}} : $FakeOptional<Int64>):
// CHECK:   init_existential_addr %0 : $*Any, $(FakeOptional<Int64>, FakeOptional<S>)
// CHECK:   switch_enum %{{.*}} : $FakeOptional<T>, case #FakeOptional.some!enumelt: bb4, case #FakeOptional.none!enumelt: bb6
// CHECK-LABEL: } // end sil function 'nonPureAddressProducer'
sil hidden @nonPureAddressProducer : $@convention(method) (@guaranteed C) -> @out Any {
bb0(%0 : $*Any, %1 : $C):
  %3 = class_method %1 : $C, #C.f : (C) -> () -> FakeOptional<T>, $@convention(method) (@guaranteed C) -> FakeOptional<T>
  %4 = apply %3(%1) : $@convention(method) (@guaranteed C) -> FakeOptional<T>
  switch_enum %4 : $FakeOptional<T>, case #FakeOptional.some!enumelt: bb1, case #FakeOptional.none!enumelt: bb2

bb1:
  %7 = integer_literal $Builtin.Int64, 1
  %8 = struct $Int64 (%7 : $Builtin.Int64)
  %9 = enum $FakeOptional<Int64>, #FakeOptional.some!enumelt, %8 : $Int64
  br bb3(%9 : $FakeOptional<Int64>)

bb2:
  %11 = enum $FakeOptional<Int64>, #FakeOptional.none!enumelt
  br bb3(%11 : $FakeOptional<Int64>)

bb3(%13 : $FakeOptional<Int64>):
  %15 = init_existential_addr %0 : $*Any, $(FakeOptional<Int64>, FakeOptional<S>)
  %16 = tuple_element_addr %15 : $*(FakeOptional<Int64>, FakeOptional<S>), 0
  %17 = tuple_element_addr %15 : $*(FakeOptional<Int64>, FakeOptional<S>), 1
  store %13 to %16 : $*FakeOptional<Int64>
  switch_enum %4 : $FakeOptional<T>, case #FakeOptional.some!enumelt: bb4, case #FakeOptional.none!enumelt: bb6

bb4(%20 : $T):
  %21 = struct_extract %20 : $T, #T.s
  %22 = enum $FakeOptional<S>, #FakeOptional.some!enumelt, %21 : $S
  store %22 to %17 : $*FakeOptional<S>
  br bb5

bb5:
  %25 = tuple ()
  return %25 : $()

bb6:
  %27 = enum $FakeOptional<S>, #FakeOptional.none!enumelt
  store %27 to %17 : $*FakeOptional<S>
  br bb5
}

// -----------------------------------------------------------------------------
// Test select_enum correctness
// -----------------------------------------------------------------------------

// Two select_enum instructions must not be considered as the same "condition",
// even if they have the same enum operand.
// This test checks that SimplifyCFG does not remove a dominated terminator with
// such a condition.

// CHECK-LABEL: sil @test_cond_br
// CHECK: select_enum
// CHECK: cond_br
// CHECK: integer_literal $Builtin.Int64, 1
// CHECK: select_enum
// CHECK: cond_br
// CHECK: integer_literal $Builtin.Int64, 2
// CHECK: integer_literal $Builtin.Int64, 3
// CHECK: return
sil @test_cond_br : $@convention(thin) (E) -> Builtin.Int64 {
bb0(%0 : $E):
  %t1 = integer_literal $Builtin.Int1, -1
  %f1 = integer_literal $Builtin.Int1, 0
  %s1 = select_enum %0 : $E, case #E.A!enumelt: %t1, default %f1 : $Builtin.Int1
  cond_br %s1, bb1, bb2

bb1:
  %i1 = integer_literal $Builtin.Int64, 1
  br bb5(%i1 : $Builtin.Int64)

bb2:
  %s2 = select_enum %0 : $E, case #E.B!enumelt: %t1, default %f1 : $Builtin.Int1
  cond_br %s2, bb3, bb4

bb3:
  %i2 = integer_literal $Builtin.Int64, 2
  br bb5(%i2 : $Builtin.Int64)

bb4:
  %i3 = integer_literal $Builtin.Int64, 3
  br bb5(%i3 : $Builtin.Int64)

bb5(%a3 : $Builtin.Int64):
  return %a3 : $Builtin.Int64
}