// RUN: %target-sil-opt -enforce-exclusivity=none -enable-sil-verify-all %s -licm | %FileCheck %s

// Declare this SIL to be canonical because some tests break raw SIL
// conventions. e.g. address-type block args. -enforce-exclusivity=none is also
// required to allow address-type block args in canonical SIL.
sil_stage canonical

import Builtin
import Swift

// CHECK-LABEL: @memset

// CHECK: bb0
// CHECK:  load %0
// CHECK: br bb2

// CHECK: bb2({{.*}}):
// CHECK-NOT: load
// CHECK-NOT: fix_lifetime
// CHECK: cond_br

sil @memset : $@convention(thin) (@inout Builtin.NativeObject, Int) -> () {
bb0(%0 : $*Builtin.NativeObject, %1 : $Int):
  %5 = integer_literal $Builtin.Int1, -1
  %46 = integer_literal $Builtin.Word, 0
  br bb2(%46 : $Builtin.Word)

bb1:
  %52 = tuple ()
  return %52 : $()

bb2(%54 : $Builtin.Word):
  %55 = integer_literal $Builtin.Word, 1
  %57 = builtin "sadd_with_overflow_Word"(%54 : $Builtin.Word, %55 : $Builtin.Word, %5 : $Builtin.Int1) : $(Builtin.Word, Builtin.Int1)
  %58 = tuple_extract %57 : $(Builtin.Word, Builtin.Int1), 0
  %59 = load %0 : $*Builtin.NativeObject
  %60 = integer_literal $Builtin.Word, 100
  %96 = ref_to_raw_pointer %59 : $Builtin.NativeObject to $Builtin.RawPointer
  %97 = index_raw_pointer %96 : $Builtin.RawPointer, %58 : $Builtin.Word
  %98 = pointer_to_address %97 : $Builtin.RawPointer to [strict] $*Int
  %99 = index_addr %98 : $*Int, %54 : $Builtin.Word
  fix_lifetime %59: $Builtin.NativeObject
  store %1 to %99 : $*Int
  %101 = builtin "cmp_eq_Word"(%58 : $Builtin.Word, %60 : $Builtin.Word) : $Builtin.Int1
  cond_br %101, bb1, bb2(%58 : $Builtin.Word)
}

// CHECK-LABEL: @must_move_condfail

// CHECK: bb0
// CHECK: load %0
// CHECK: cond_fail
// CHECK: [[INVARIANTADDR:%.*]] = pointer_to_address
// CHECK: load [[INVARIANTADDR]]
// CHECK: br bb2

// CHECK: bb2({{.*}}):
// The address computation of the load was guarded by the cond_fail. If we hoist
// the load we must also hoist the cond_fail.
// CHECK-NOT: cond_fail
// CHECK-NOT: load
// CHECK: cond_br

sil @must_move_condfail : $@convention(thin) (@inout Builtin.NativeObject, Int, Builtin.Word) -> () {
bb0(%0 : $*Builtin.NativeObject, %1 : $Int, %2: $Builtin.Word):
  %5 = integer_literal $Builtin.Int1, -1
  %6 = load %0 : $*Builtin.NativeObject
  %46 = integer_literal $Builtin.Word, 0
  br bb2(%46 : $Builtin.Word)

bb1:
  %102 = tuple ()
  return %102 : $()

bb2(%48 : $Builtin.Word):
  %51 = builtin "sadd_with_overflow_Word"(%2 : $Builtin.Word, %46 : $Builtin.Word, %5 : $Builtin.Int1) : $(Builtin.Word, Builtin.Int1)
  %52 = tuple_extract %51 : $(Builtin.Word, Builtin.Int1), 0
  %53 = tuple_extract %51 : $(Builtin.Word, Builtin.Int1), 1
  cond_fail %53 : $Builtin.Int1
  %55 = integer_literal $Builtin.Word, 1
  %57 = builtin "sadd_with_overflow_Word"(%48 : $Builtin.Word, %55 : $Builtin.Word, %5 : $Builtin.Int1) : $(Builtin.Word, Builtin.Int1)
  %58 = tuple_extract %57 : $(Builtin.Word, Builtin.Int1), 0
  %60 = integer_literal $Builtin.Word, 100
  %61 = ref_to_raw_pointer %6 : $Builtin.NativeObject to $Builtin.RawPointer
  %62 = index_raw_pointer %61 : $Builtin.RawPointer, %52 : $Builtin.Word
  %63 = pointer_to_address %62 : $Builtin.RawPointer to [strict] $*Builtin.NativeObject
  %64 = load %63 : $*Builtin.NativeObject
  %96 = ref_to_raw_pointer %64 : $Builtin.NativeObject to $Builtin.RawPointer
  %97 = index_raw_pointer %96 : $Builtin.RawPointer, %58 : $Builtin.Word
  %98 = pointer_to_address %97 : $Builtin.RawPointer to [strict] $*Int
  %99 = index_addr %98 : $*Int, %48 : $Builtin.Word
  store %1 to %99 : $*Int
  %101 = builtin "cmp_eq_Word"(%58 : $Builtin.Word, %60 : $Builtin.Word) : $Builtin.Int1
  cond_br %101, bb1, bb2(%58 : $Builtin.Word)
}


// CHECK-LABEL: sil @hoist_outer_loop
// CHECK: bb0([[ADDR:%.*]] : $*Builtin.Int1
// CHECK:  load [[ADDR]]
// CHECK:  integer_literal $Builtin.Word, 101
// CHECK: br bb1
// CHECK: return

sil @hoist_outer_loop : $@convention(thin) (@inout Builtin.Int1, Int) -> () {
bb0(%0 : $*Builtin.Int1, %1 : $Int):
  %2 = integer_literal $Builtin.Int1, -1
  %3 = integer_literal $Builtin.Word, 0
  br bb1

// Outer loop.
bb1:
  %5 = load %0 : $*Builtin.Int1
  %6 = integer_literal $Builtin.Word, 101
  cond_br %5, bb2, bb3

bb2:
  cond_br %5, bb4, bb1

// Inner loop.
bb3:
  cond_br %5, bb2, bb3

bb4:
  %10 = tuple ()
  return %10 : $()
}

// CHECK-LABEL: sil @dont_hoist_outer_loop
// CHECK: bb0([[ADDR:%.*]] : $*Builtin.Int1
// CHECK:  integer_literal $Builtin.Word, 101
// CHECK: br bb1
// CHECK: bb1:
// CHECK:  load [[ADDR]]
// CHECK: return

sil @dont_hoist_outer_loop : $@convention(thin) (@inout Builtin.Int1, Int) -> () {
bb0(%0 : $*Builtin.Int1, %1 : $Int):
  %2 = integer_literal $Builtin.Int1, -1
  %3 = integer_literal $Builtin.Word, 0
  br bb1

// Outer loop.
bb1:
  %5 = load %0 : $*Builtin.Int1
  %6 = integer_literal $Builtin.Word, 101
  cond_br %5, bb2, bb3

bb2:
  cond_br %5, bb4, bb1

// Inner loop.
bb3:
  store %2 to %0 : $*Builtin.Int1
  cond_br %5, bb2, bb3

bb4:
  %10 = tuple ()
  return %10 : $()
}

sil [_semantics "array.get_count"] @getCount : $@convention(method) (@guaranteed Array<Int>) -> Int
sil @user : $@convention(thin) (Int) -> ()

// CHECK-LABEL:   sil @dont_hoist_get_count_on_low_level_sil
// CHECK:         {{^}}bb1:
// CHECK:           apply
// CHECK:           apply
// CHECK:         {{^}}bb2:
// CHECK:           return
sil @dont_hoist_get_count_on_low_level_sil : $@convention(thin) (@guaranteed Array<Int>) -> () {
bb0(%0 : $Array<Int>):
  br bb1

bb1:
  %f1 = function_ref @getCount : $@convention(method) (@guaranteed Array<Int>) -> Int
  %f2 = function_ref @user : $@convention(thin) (Int) -> ()
  %c1 = apply %f1(%0) : $@convention(method) (@guaranteed Array<Int>) -> Int
  %c2 = apply %f2(%c1) : $@convention(thin) (Int) -> ()
  cond_br undef, bb1, bb2

bb2:
  %r1 = tuple ()
  return %r1 : $()
}

// CHECK-LABEL:   sil @dont_hoist_aliased_stack_location
// CHECK:         {{^}}bb0
// CHECK-NOT:       load
// CHECK:         {{^}}bb1:
// CHECK:           store
// CHECK:           load
// CHECK:         {{^}}bb2:
// CHECK:           return
sil @dont_hoist_aliased_stack_location : $@convention(thin) (Int32) -> () {
bb0(%0 : $Int32):
  %313 = alloc_stack $Int32
  br bb1

bb1:
  store %0 to %313 : $*Int32
  %l1 = load %313 : $*Int32
  cond_br undef, bb1, bb2

bb2:
  dealloc_stack %313 : $*Int32
  %52 = tuple ()
  return %52 : $()
}

public protocol P : class {
  func foo() -> Int32
  func boo() -> Int32
}

// Check that LICM does not hoist a metatype instruction before
// the open_existential instruction which creates the archtype,
// because this would break the dominance relation between them.
// CHECK-LABEL: sil @dont_hoist_metatype
// CHECK-NOT: metatype
// CHECK-NOT: witness_method
// CHECK: bb1({{%.*}} : $P)
// CHECK-NOT: metatype
// CHECK-NOT: witness_method
// CHECK: open_existential_ref
// CHECK: metatype
// CHECK: witness_method
// CHECK: cond_br
sil @dont_hoist_metatype : $@convention(thin) (@inout Builtin.Int1, @owned P) -> () {
bb0(%0 : $*Builtin.Int1, %1 : $P):
  br bb1(%1 : $P)

// Loop
bb1(%existential : $P):
  %2 = open_existential_ref %existential : $P to $@opened("C4960DBA-02C5-11E6-BE1B-B8E856428C60") P
  %3 = metatype $@thick (@opened("C4960DBA-02C5-11E6-BE1B-B8E856428C60") P).Type
  %4 = witness_method $@opened("C4960DBA-02C5-11E6-BE1B-B8E856428C60") P, #P.foo!1, %2 : $@opened("C4960DBA-02C5-11E6-BE1B-B8E856428C60") P : $@convention(witness_method: P) <τ_0_0 where τ_0_0 : P> (@guaranteed τ_0_0) -> Int32
  %5 = apply %4<@opened("C4960DBA-02C5-11E6-BE1B-B8E856428C60") P>(%2) : $@convention(witness_method: P) <τ_0_0 where τ_0_0 : P> (@guaranteed τ_0_0) -> Int32
  %6 = load %0 : $*Builtin.Int1
  cond_br %6, bb3, bb1(%existential : $P)

bb3:
  br bb4

bb4:
  strong_release %1 : $P
  %10 = tuple ()
  return %10 : $()
}

// CHECK-LABEL: dont_hoist_existential_meta_type
// CHECK: bb0({{.*}}:
// CHECK-NOT: existential_metatype
// CHECK: bb1:
// CHECK: existential_metatype
// CHECK: cond_br
// CHECK: bb2:
sil @dont_hoist_existential_meta_type : $@convention(thin) (@in P) -> () {
bb0(%0 : $*P):
  %1 = alloc_stack $P
  br bb1

bb1:
  copy_addr %0 to [initialization] %1 : $*P
  %2 = existential_metatype $@thick P.Type, %1 : $*P
  cond_br undef, bb1, bb2

bb2:
  dealloc_stack %1 : $*P
  destroy_addr %0 : $*P
  %52 = tuple ()
  return %52 : $()
}


sil @get_unknown_value : $@convention(thin) () -> Builtin.Int32
sil @get_unknown_value2 : $@convention(thin) () -> Builtin.Int32

sil @callee : $@convention(thin) (@inout Builtin.Int32) -> () {
bb0(%0 : $*Builtin.Int32):
  %1 = function_ref @get_unknown_value : $@convention(thin) () -> Builtin.Int32
  %2 = apply %1() : $@convention(thin) () -> Builtin.Int32
  store %2 to %0 : $*Builtin.Int32
  %9999 = tuple()
  return %9999 : $()
}

sil @use_value : $@convention(thin) (Builtin.Int32) -> ()

// Check if escape analysis figures out that the alloc_stack escapes to callee.
//
// CHECK-LABEL: sil @dont_hoist_aliased_load
// CHECK:      bb2:
// CHECK-NEXT:   apply
// CHECK-NEXT:   load
// CHECK-NEXT:   apply
sil @dont_hoist_aliased_load : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $Builtin.Int32
  %1 = integer_literal $Builtin.Int32, 0
  %3 = function_ref @callee : $@convention(thin) (@inout Builtin.Int32) -> ()
  %5 = function_ref @use_value : $@convention(thin) (Builtin.Int32) -> ()
  %unknown_value_fn = function_ref @get_unknown_value2 : $@convention(thin) () -> Builtin.Int32
  store %1 to %0 : $*Builtin.Int32
  br bb1(%0 : $*Builtin.Int32)

bb1(%phi1 : $*Builtin.Int32):
  br bb2

bb2:
  apply %3(%0) : $@convention(thin) (@inout Builtin.Int32) -> ()
  %4 = load %phi1 : $*Builtin.Int32
  %6 = apply %unknown_value_fn() : $@convention(thin) () -> Builtin.Int32
  %33 = builtin "cmp_eq_Int32"(%4 : $Builtin.Int32, %6 : $Builtin.Int32) : $Builtin.Int1
  cond_br %33, bb2, bb3

bb3:
  %9999 = tuple()
  dealloc_stack %0 : $*Builtin.Int32
  return %9999 : $()
}

class RefElemClass {
  var x : Int32

  init()
}

// Check hoisting of ref_element_addr in conditional control flow (for exclusivity)
//
// CHECK-LABEL: sil @hoist_ref_elem
// CHECK: bb0(%0 : $RefElemClass):
// CHECK-NEXT:   ref_element_addr %0 : $RefElemClass, #RefElemClass.x
// CHECK-NEXT:   br bb1
sil @hoist_ref_elem : $@convention(thin) (RefElemClass) -> () {
bb0(%0 : $RefElemClass):
  br bb1

// loop.
bb1:
  cond_br undef, bb2, bb3

bb2:
  cond_br undef, bb4, bb1

bb3:
  %x = ref_element_addr %0 : $RefElemClass, #RefElemClass.x
  br bb1

bb4:
  %10 = tuple ()
  return %10 : $()
}