// RUN: %target-sil-opt -enable-sil-verify-all %s -function-order-printer -o /dev/null | %FileCheck --check-prefix=CHECK %s

sil_stage canonical

import Builtin

// CHECK: Bottom up function order:
// CHECK-NEXT: private_bottom
// CHECK-NEXT: private_middle
// CHECK-NEXT: private_top
// CHECK-NEXT: internal_bottom
// CHECK-NEXT: internal_middle
// CHECK-NEXT: internal_top
// CHECK-NEXT: public_bottom
// CHECK-NEXT: public_middle
// CHECK-NEXT: public_top
// CHECK-NEXT: private_base_foo
// CHECK-NEXT: private_derived_foo
// CHECK-NEXT: call_private
// CHECK-NEXT: internal_base_foo
// CHECK-NEXT: internal_derived_foo
// CHECK-NEXT: internal_base_bar
// CHECK-NEXT: internal_derived_bar
// CHECK-NEXT: call_internal
// CHECK-NEXT: public_base_foo
// CHECK-NEXT: public_derived_foo
// CHECK-NEXT: public_base_bar
// CHECK-NEXT: public_derived_bar
// CHECK-NEXT: public_base_baz
// CHECK-NEXT: public_derived_baz
// CHECK-NEXT: call_public
// CHECK-NEXT: private_proto_private_class_theMethod
// CHECK-NEXT: private_proto_1_private_class_witness
// CHECK-NEXT: call_through_private_proto_1
// CHECK-NEXT: private_proto_internal_class_theMethod
// CHECK-NEXT: private_proto_2_internal_class_witness
// CHECK-NEXT: call_through_private_proto_2
// CHECK-NEXT: private_proto_public_class_theMethod
// CHECK-NEXT: private_proto_3_public_class_witness
// CHECK-NEXT: call_through_private_proto_3
// CHECK-NEXT: private_proto_public_class_private_method_theMethod
// CHECK-NEXT: private_proto_4_public_class_private_method_witness
// CHECK-NEXT: call_through_private_proto_4
// CHECK-NEXT: Non-trivial SCC:
// CHECK-NEXT:   second_recursive
// CHECK-NEXT:   first_recursive

sil private @private_top : $@convention(thin) () -> () {
bb0:
  %0 = function_ref @private_middle : $@convention(thin) () -> ()
  %1 = apply %0() : $@convention(thin) () -> ()
  %2 = tuple ()
  return %2 : $()
}

sil private @private_middle : $@convention(thin) () -> () {
bb0:
  %0 = function_ref @private_bottom : $@convention(thin) () -> ()
  %1 = apply %0() : $@convention(thin) () -> ()
  %2 = tuple ()
  return %2 : $()
}

sil private @private_bottom : $@convention(thin) () -> () {
bb0:
  %0 = tuple ()
  return %0 : $()
}


sil hidden @internal_top : $@convention(thin) () -> () {
bb0:
  %0 = function_ref @internal_middle : $@convention(thin) () -> ()
  %1 = apply %0() : $@convention(thin) () -> ()
  %2 = tuple ()
  return %2 : $()
}

sil hidden @internal_middle : $@convention(thin) () -> () {
bb0:
  %0 = function_ref @internal_bottom : $@convention(thin) () -> ()
  %1 = apply %0() : $@convention(thin) () -> ()
  %2 = tuple ()
  return %2 : $()
}

sil hidden @internal_bottom : $@convention(thin) () -> () {
bb0:
  %0 = tuple ()
  return %0 : $()
}

sil @public_top : $@convention(thin) () -> () {
bb0:
  %0 = function_ref @public_middle : $@convention(thin) () -> ()
  %1 = apply %0() : $@convention(thin) () -> ()
  %2 = tuple ()
  return %2 : $()
}

sil @public_middle : $@convention(thin) () -> () {
bb0:
  %0 = function_ref @public_bottom : $@convention(thin) () -> ()
  %1 = apply %0() : $@convention(thin) () -> ()
  %2 = tuple ()
  return %2 : $()
}

sil @public_bottom : $@convention(thin) () -> () {
bb0:
  %0 = tuple ()
  return %0 : $()
}

private class private_base {
  func foo()
}

private class private_derived : private_base {
  override func foo()
}

@inline(never) private func call_private(b: private_base)

class internal_base {
  func foo()
  private func bar()
}

class internal_derived : internal_base {
  override func foo()
  override func bar()
}

@inline(never) func call_internal(b: internal_base)

public class public_base {
  func foo()
  public func bar()
  private func baz()
}

public class public_derived : public_base {
  override func foo()
  public override func bar()
  public override func baz()
}

sil private [noinline] @call_private : $@convention(thin) (@owned private_base) -> () {
bb0(%0 : $private_base):
  debug_value %0 : $private_base
  %2 = class_method %0 : $private_base, #private_base.foo!1 : (private_base) -> () -> (), $@convention(method) (@guaranteed private_base) -> ()
  %3 = apply %2(%0) : $@convention(method) (@guaranteed private_base) -> ()
  strong_release %0 : $private_base
  %5 = tuple ()
  return %5 : $()
}


sil private @private_derived_foo : $@convention(method) (@guaranteed private_derived) -> () {
bb0(%0 : $private_derived):
  debug_value %0 : $private_derived
  %2 = tuple ()
  return %2 : $()
}

sil private @private_base_foo : $@convention(method) (@guaranteed private_base) -> () {
bb0(%0 : $private_base):
  debug_value %0 : $private_base
  %2 = tuple ()
  return %2 : $()
}


sil hidden [noinline] @call_internal : $@convention(thin) (@owned internal_base) -> () {
bb0(%0 : $internal_base):
  debug_value %0 : $internal_base
  %2 = class_method %0 : $internal_base, #internal_base.foo!1 : (internal_base) -> () -> (), $@convention(method) (@guaranteed internal_base) -> ()
  %3 = apply %2(%0) : $@convention(method) (@guaranteed internal_base) -> ()
  %4 = class_method %0 : $internal_base, #internal_base.bar!1 : (internal_base) -> () -> (), $@convention(method) (@guaranteed internal_base) -> ()
  %5 = apply %4(%0) : $@convention(method) (@guaranteed internal_base) -> ()
  strong_release %0 : $internal_base
  %7 = tuple ()
  return %7 : $()
}

sil hidden @internal_base_foo : $@convention(method) (@guaranteed internal_base) -> () {
bb0(%0 : $internal_base):
  debug_value %0 : $internal_base
  %2 = tuple ()
  return %2 : $()
}

sil private @internal_base_bar : $@convention(method) (@guaranteed internal_base) -> () {
bb0(%0 : $internal_base):
  debug_value %0 : $internal_base
  %2 = tuple ()
  return %2 : $()
}


sil hidden @internal_derived_foo : $@convention(method) (@guaranteed internal_derived) -> () {
bb0(%0 : $internal_derived):
  debug_value %0 : $internal_derived
  %2 = tuple ()
  return %2 : $()
}

sil hidden @internal_derived_bar : $@convention(method) (@guaranteed internal_derived) -> () {
bb0(%0 : $internal_derived):
  debug_value %0 : $internal_derived
  %2 = tuple ()
  return %2 : $()
}

sil hidden [noinline] @call_public : $@convention(thin) (@owned public_base) -> () {
bb0(%0 : $public_base):
  debug_value %0 : $public_base
  %2 = class_method %0 : $public_base, #public_base.foo!1 : (public_base) -> () -> (), $@convention(method) (@guaranteed public_base) -> ()
  %3 = apply %2(%0) : $@convention(method) (@guaranteed public_base) -> ()
  %4 = class_method %0 : $public_base, #public_base.bar!1 : (public_base) -> () -> (), $@convention(method) (@guaranteed public_base) -> ()
  %5 = apply %4(%0) : $@convention(method) (@guaranteed public_base) -> ()
  %6 = class_method %0 : $public_base, #public_base.baz!1 : (public_base) -> () -> (), $@convention(method) (@guaranteed public_base) -> ()
  %7 = apply %6(%0) : $@convention(method) (@guaranteed public_base) -> ()
  strong_release %0 : $public_base
  %9 = tuple ()
  return %9 : $()
}

sil hidden @public_base_foo : $@convention(method) (@guaranteed public_base) -> () {
bb0(%0 : $public_base):
  debug_value %0 : $public_base
  %2 = tuple ()
  return %2 : $()
}


sil @public_base_bar : $@convention(method) (@guaranteed public_base) -> () {
bb0(%0 : $public_base):
  debug_value %0 : $public_base
  %2 = tuple ()
  return %2 : $()
}


sil private @public_base_baz : $@convention(method) (@guaranteed public_base) -> () {
bb0(%0 : $public_base):
  debug_value %0 : $public_base
  %2 = tuple ()
  return %2 : $()
}


sil hidden @public_derived_foo : $@convention(method) (@guaranteed public_derived) -> () {
bb0(%0 : $public_derived):
  debug_value %0 : $public_derived
  %2 = tuple ()
  return %2 : $()
}


sil @public_derived_bar : $@convention(method) (@guaranteed public_derived) -> () {
bb0(%0 : $public_derived):
  debug_value %0 : $public_derived
  %2 = tuple ()
  return %2 : $()
}


sil @public_derived_baz : $@convention(method) (@guaranteed public_derived) -> () {
bb0(%0 : $public_derived):
  debug_value %0 : $public_derived
  %2 = tuple ()
  return %2 : $()
}


sil_vtable private_base {
  #private_base.foo!1: @private_base_foo
}

sil_vtable private_derived {
  #private_base.foo!1: @private_derived_foo
}

sil_vtable internal_base {
  #internal_base.foo!1: @internal_base_foo
  #internal_base.bar!1: @internal_base_bar
}

sil_vtable internal_derived {
  #internal_base.foo!1: @internal_derived_foo
  #internal_base.bar!1: @internal_derived_bar
}

sil_vtable public_base {
  #public_base.foo!1: @public_base_foo
  #public_base.bar!1: @public_base_bar
  #public_base.baz!1: @public_base_baz
}

sil_vtable public_derived {
  #public_base.foo!1: @public_derived_foo
  #public_base.bar!1: @public_derived_bar
  #public_base.baz!1: @public_derived_baz
}

private protocol private_proto_1 {
  func theMethod()
}

private class private_proto_private_class : private_proto_1 {
  func theMethod()
}

private func call_through_private_proto_1<T : private_proto_1>(x: T)

private protocol private_proto_2 {
  func theMethod()
}

class private_proto_internal_class : private_proto_2 {
  func theMethod()
}

private func call_through_private_proto_2<T : private_proto_2>(x: T)

private protocol private_proto_3 {
  func theMethod()
}

public class private_proto_public_class : private_proto_3 {
  public func theMethod()
}

private func call_through_private_proto_3<T : private_proto_3>(x: T)

private protocol private_proto_4 {
  func theMethod()
}

public class private_proto_public_class_private_method : private_proto_4 {
  fileprivate func theMethod()
}

private func call_through_private_proto_4<T : private_proto_4>(x: T)

sil private @private_proto_private_class_theMethod : $@convention(method) (@guaranteed private_proto_private_class) -> () {
bb0(%0 : $private_proto_private_class):
  debug_value %0 : $private_proto_private_class
  %2 = tuple ()
  return %2 : $()
}


sil private [transparent] [thunk] @private_proto_1_private_class_witness : $@convention(witness_method: private_proto_1) (@in_guaranteed private_proto_private_class) -> () {
bb0(%0 : $*private_proto_private_class):
  %1 = load %0 : $*private_proto_private_class
  strong_retain %1 : $private_proto_private_class
  %3 = class_method %1 : $private_proto_private_class, #private_proto_private_class.theMethod!1 : (private_proto_private_class) -> () -> (), $@convention(method) (@guaranteed private_proto_private_class) -> ()
  %4 = apply %3(%1) : $@convention(method) (@guaranteed private_proto_private_class) -> ()
  strong_release %1 : $private_proto_private_class
  return %4 : $()
}

sil private @call_through_private_proto_1 : $@convention(thin) <T where T : private_proto_1> (@in T) -> () {
bb0(%0 : $*T):
  debug_value_addr %0 : $*T
  %2 = witness_method $T, #private_proto_1.theMethod!1 : $@convention(witness_method: private_proto_1) <τ_0_0 where τ_0_0 : private_proto_1> (@in_guaranteed τ_0_0) -> ()
  %3 = apply %2<T>(%0) : $@convention(witness_method: private_proto_1) <τ_0_0 where τ_0_0 : private_proto_1> (@in_guaranteed τ_0_0) -> ()
  destroy_addr %0 : $*T
  %5 = tuple ()
  return %5 : $()
}

sil hidden @private_proto_internal_class_theMethod : $@convention(method) (@guaranteed private_proto_internal_class) -> () {
bb0(%0 : $private_proto_internal_class):
  debug_value %0 : $private_proto_internal_class
  %2 = tuple ()
  return %2 : $()
}

sil private [transparent] [thunk] @private_proto_2_internal_class_witness : $@convention(witness_method: private_proto_2) (@in_guaranteed private_proto_internal_class) -> () {
bb0(%0 : $*private_proto_internal_class):
  %1 = load %0 : $*private_proto_internal_class
  strong_retain %1 : $private_proto_internal_class
  %3 = class_method %1 : $private_proto_internal_class, #private_proto_internal_class.theMethod!1 : (private_proto_internal_class) -> () -> (), $@convention(method) (@guaranteed private_proto_internal_class) -> ()
  %4 = apply %3(%1) : $@convention(method) (@guaranteed private_proto_internal_class) -> ()
  strong_release %1 : $private_proto_internal_class
  return %4 : $()
}


sil private @call_through_private_proto_2 : $@convention(thin) <T where T : private_proto_2> (@in T) -> () {
bb0(%0 : $*T):
  debug_value_addr %0 : $*T
  %2 = witness_method $T, #private_proto_2.theMethod!1 : $@convention(witness_method: private_proto_2) <τ_0_0 where τ_0_0 : private_proto_2> (@in_guaranteed τ_0_0) -> ()
  %3 = apply %2<T>(%0) : $@convention(witness_method: private_proto_2) <τ_0_0 where τ_0_0 : private_proto_2> (@in_guaranteed τ_0_0) -> ()
  destroy_addr %0 : $*T
  %5 = tuple ()
  return %5 : $()
}

sil @private_proto_public_class_theMethod : $@convention(method) (@guaranteed private_proto_public_class) -> () {
bb0(%0 : $private_proto_public_class):
  debug_value %0 : $private_proto_public_class
  %2 = tuple ()
  return %2 : $()
}


sil private [transparent] [thunk] @private_proto_3_public_class_witness : $@convention(witness_method: private_proto_3) (@in_guaranteed private_proto_public_class) -> () {
bb0(%0 : $*private_proto_public_class):
  %1 = load %0 : $*private_proto_public_class
  strong_retain %1 : $private_proto_public_class
  %3 = class_method %1 : $private_proto_public_class, #private_proto_public_class.theMethod!1 : (private_proto_public_class) -> () -> (), $@convention(method) (@guaranteed private_proto_public_class) -> ()
  %4 = apply %3(%1) : $@convention(method) (@guaranteed private_proto_public_class) -> ()
  strong_release %1 : $private_proto_public_class
  return %4 : $()
}


sil private @call_through_private_proto_3 : $@convention(thin) <T where T : private_proto_3> (@in T) -> () {
bb0(%0 : $*T):
  debug_value_addr %0 : $*T
  %2 = witness_method $T, #private_proto_3.theMethod!1 : $@convention(witness_method: private_proto_3) <τ_0_0 where τ_0_0 : private_proto_3> (@in_guaranteed τ_0_0) -> ()
  %3 = apply %2<T>(%0) : $@convention(witness_method: private_proto_3) <τ_0_0 where τ_0_0 : private_proto_3> (@in_guaranteed τ_0_0) -> ()
  destroy_addr %0 : $*T
  %5 = tuple ()
  return %5 : $()
}

sil private @private_proto_public_class_private_method_theMethod : $@convention(method) (@guaranteed private_proto_public_class_private_method) -> () {
bb0(%0 : $private_proto_public_class_private_method):
  debug_value %0 : $private_proto_public_class_private_method
  %2 = tuple ()
  return %2 : $()
}

sil private [transparent] [thunk] @private_proto_4_public_class_private_method_witness : $@convention(witness_method: private_proto_4) (@in_guaranteed private_proto_public_class_private_method) -> () {
bb0(%0 : $*private_proto_public_class_private_method):
  %1 = load %0 : $*private_proto_public_class_private_method
  strong_retain %1 : $private_proto_public_class_private_method
  %3 = class_method %1 : $private_proto_public_class_private_method, #private_proto_public_class_private_method.theMethod!1 : (private_proto_public_class_private_method) -> () -> (), $@convention(method) (@guaranteed private_proto_public_class_private_method) -> ()
  %4 = apply %3(%1) : $@convention(method) (@guaranteed private_proto_public_class_private_method) -> ()
  strong_release %1 : $private_proto_public_class_private_method
  return %4 : $()
}


sil private @call_through_private_proto_4 : $@convention(thin) <T where T : private_proto_4> (@in T) -> () {
bb0(%0 : $*T):
  debug_value_addr %0 : $*T
  %2 = witness_method $T, #private_proto_4.theMethod!1 : $@convention(witness_method: private_proto_4) <τ_0_0 where τ_0_0 : private_proto_4> (@in_guaranteed τ_0_0) -> ()
  %3 = apply %2<T>(%0) : $@convention(witness_method: private_proto_4) <τ_0_0 where τ_0_0 : private_proto_4> (@in_guaranteed τ_0_0) -> ()
  destroy_addr %0 : $*T
  %5 = tuple ()
  return %5 : $()
}


sil_vtable private_proto_private_class {
  #private_proto_private_class.theMethod!1: @private_proto_private_class_theMethod
}

sil_vtable private_proto_internal_class {
  #private_proto_internal_class.theMethod!1: @private_proto_internal_class_theMethod
}

sil_vtable private_proto_public_class {
  #private_proto_public_class.theMethod!1: @private_proto_public_class_theMethod
}

sil_vtable private_proto_public_class_private_method {
  #private_proto_public_class_private_method.theMethod!1: @private_proto_public_class_private_method_theMethod
}

sil_witness_table private private_proto_private_class: private_proto_1 module witness {
  method #private_proto_1.theMethod!1: @private_proto_1_private_class_witness
}

sil_witness_table private private_proto_internal_class: private_proto_2 module witness {
  method #private_proto_2.theMethod!1: @private_proto_2_internal_class_witness
}

sil_witness_table private private_proto_public_class: private_proto_3 module witness {
  method #private_proto_3.theMethod!1: @private_proto_3_public_class_witness
}

sil_witness_table private private_proto_public_class_private_method: private_proto_4 module witness {
  method #private_proto_4.theMethod!1: @private_proto_4_public_class_private_method_witness
}

sil hidden @first_recursive : $@convention(thin) (Builtin.Int32) -> Builtin.Int32 {
bb0(%0 : $Builtin.Int32):
  %2 = integer_literal $Builtin.Int32, 0
  %4 = builtin "cmp_sgt_Int32"(%0 : $Builtin.Int32, %2 : $Builtin.Int32) : $Builtin.Int1
  cond_br %4, bb1, bb2

bb1:
  %8 = function_ref @second_recursive : $@convention(thin) (Builtin.Int32) -> Builtin.Int32
  %9 = integer_literal $Builtin.Int32, 1
  %11 = integer_literal $Builtin.Int1, -1
  %12 = builtin "ssub_with_overflow_Int32"(%0 : $Builtin.Int32, %9 : $Builtin.Int32, %11 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %13 = tuple_extract %12 : $(Builtin.Int32, Builtin.Int1), 0
  %14 = tuple_extract %12 : $(Builtin.Int32, Builtin.Int1), 1
  cond_fail %14 : $Builtin.Int1
  %17 = apply %8(%13) : $@convention(thin) (Builtin.Int32) -> Builtin.Int32
  br bb3(%17 : $Builtin.Int32)

bb2:
  %19 = integer_literal $Builtin.Int32, 27
  br bb3(%19 : $Builtin.Int32)

bb3(%22 : $Builtin.Int32):
  return %22 : $Builtin.Int32
}

sil hidden @second_recursive : $@convention(thin) (Builtin.Int32) -> Builtin.Int32 {
bb0(%0 : $Builtin.Int32):
  %2 = integer_literal $Builtin.Int32, 0
  %4 = builtin "cmp_sgt_Int32"(%0 : $Builtin.Int32, %2 : $Builtin.Int32) : $Builtin.Int1
  cond_br %4, bb1, bb2

bb1:
  %8 = function_ref @first_recursive : $@convention(thin) (Builtin.Int32) -> Builtin.Int32
  %9 = integer_literal $Builtin.Int32, 3
  %11 = integer_literal $Builtin.Int1, -1
  %12 = builtin "ssub_with_overflow_Int32"(%0 : $Builtin.Int32, %9 : $Builtin.Int32, %11 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %13 = tuple_extract %12 : $(Builtin.Int32, Builtin.Int1), 0
  %14 = tuple_extract %12 : $(Builtin.Int32, Builtin.Int1), 1
  cond_fail %14 : $Builtin.Int1
  %17 = apply %8(%13) : $@convention(thin) (Builtin.Int32) -> Builtin.Int32
  br bb3(%17 : $Builtin.Int32)

bb2:
  %19 = integer_literal $Builtin.Int32, 9
  br bb3(%19 : $Builtin.Int32)

bb3(%22 : $Builtin.Int32):
  return %22 : $Builtin.Int32
}