// RUN: %target-sil-opt %s -dead-store-elimination -enable-sil-verify-all | %FileCheck %s
// RUN: %target-sil-opt %s -compute-side-effects -dead-store-elimination -enable-sil-verify-all | %FileCheck %s --check-prefix=CHECK-SEA-DSE

// REQUIRES: swift_in_compiler

sil_stage canonical

import Swift
import Builtin

///////////////////////
// Type Declarations //
///////////////////////

struct Int {
  var value : Builtin.Int64
}

struct Int64 {
  var value : Builtin.Int64
}

struct Bool {
  var value : Builtin.Int1
}

struct A {
  var i : Builtin.Int32
}

struct AA {
  var a : A
  var i : Builtin.Int32
}

struct S1 {
  var a: Int
  init(a: Int, b: Int)
  init()
}

struct S2 {
  var x: S1
  var a: Int
  var b: Int
  init(x: S1, a: Int, b: Int)
  init()
}

struct S3 {
  var a: Int
  var b: Int
  init(a: Int, b: Int)
  init()
}

struct S4 {
 var a: Int
 var b: Int
 init(a: Int, b: Int)
 init()
}

struct S5 {
 var x: S4
 var y: Int
 init(x: S4, y: Int)
 init()
}

struct S6 {
  var x: Int
  var y: Int
  var z: Int
  init(x: Int, y: Int, z: Int)
  init()
}

struct S7 {
  var x: Int
  var y: Int
  var z: Int
  var a: Int
  var b: Int
  var c: Int
  init(x: Int, y: Int, z: Int, a: Int, b: Int, c: Int)
  init()
}


class SelfLoop {
  var a: SelfLoop
  init()
   deinit
}

struct S8 {
  var i: SelfLoop
  var k: Int
  init(i: SelfLoop, k: Int)
  init()
}

class foo {
  var a: Int
   deinit
  init()
}

struct IntAndFoo {
  var i: Int
  var f: foo
}

class AB {
  var value: Int
  init(value: Int)
   deinit
}


class B {
  var i : Builtin.Int32
  init()
}

enum Example {
  case A(Int64, Int64)
  case B(Int64)
  case C
  case D
}

struct S9 {
  var x : S3
  init(x : S3)
  init()
}

sil @foo_user : $@convention(thin) (@guaranteed foo) -> ()
sil @S1_init : $@convention(thin) (@thin S1.Type) -> S1
sil @S2_init : $@convention(thin) (@thin S2.Type) -> S2
sil @S3_init : $@convention(thin) (@thin S3.Type) -> S3
sil @S5_init : $@convention(thin) (@thin S5.Type) -> S5
sil @S6_init : $@convention(thin) (@thin S6.Type) -> S6
sil @S7_init : $@convention(thin) (@thin S7.Type) -> S7
sil @S8_init : $@convention(thin) (@thin S8.Type) -> @owned S8
sil @S9_init : $@convention(thin) (@thin S9.Type) -> S9
sil @escaped_a : $@convention(thin) () -> Builtin.RawPointer

// CHECK-LABEL: sil hidden @dead_store_across_fixlifetime_inst
// CHECK: bb0
// CHECK-NOT: {{ store}}
// CHECK: {{ store}}
sil hidden @dead_store_across_fixlifetime_inst : $@convention(thin) (@owned AB, Int) -> () {
bb0(%0 : $AB, %1 : $Int):
  %2 = ref_element_addr %0 : $AB, #AB.value
  store %1 to %2 : $*Int
  %4 = ref_element_addr %0 : $AB, #AB.value
  fix_lifetime %0 : $AB
  store %1 to %2 : $*Int
  %18 = tuple ()
  return %18 : $()
}

// We should be able to remove the local store that is not read.
//
// CHECK-LABEL: trivial_local_dead_store
// CHECK: bb0
// CHECK-NOT: {{ store}}
// CHECK: return
sil hidden @trivial_local_dead_store : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $Int, var, name "a"
  %1 = integer_literal $Builtin.Int64, 1
  %2 = struct $Int (%1 : $Builtin.Int64)
  store %2 to %0 : $*Int
  %4 = tuple ()
  dealloc_stack %0 : $*Int
  return %4 : $()
}

// We should be able to remove the local store into alloc_ref [stack] locations
// that is not read.
//
// CHECK-LABEL: trivial_local_dead_store_into_alloc_ref
// CHECK: bb0
// CHECK-NOT: {{ store}}
// CHECK: tuple
// CHECK: return
sil hidden @trivial_local_dead_store_into_alloc_ref_stack : $@convention(thin) () -> () {
bb0:
  %0 = alloc_ref [stack] $foo
  %1 = integer_literal $Builtin.Int64, 1
  %2 = struct $Int (%1 : $Builtin.Int64)
  %3 = ref_element_addr %0 : $foo, #foo.a
  store %2 to %3 : $*Int
  %4 = tuple ()
  dealloc_stack_ref %0 : $foo
  return %4 : $()
}

// We cannot remove the local store that is potentially read by the deinit of foo.
//
// CHECK-LABEL: sil hidden @blocking_read_on_local_store_into_alloc_ref_stack
// CHECK: bb0
// CHECK: alloc_ref
// CHECK: store
// CHECK: dealloc_stack_ref
// CHECK: return
sil hidden @blocking_read_on_local_store_into_alloc_ref_stack : $@convention(thin) () -> () {
bb0:
  %0 = alloc_ref [stack] $foo
  %1 = integer_literal $Builtin.Int64, 1
  %2 = struct $Int (%1 : $Builtin.Int64)
  %3 = ref_element_addr %0 : $foo, #foo.a
  store %2 to %3 : $*Int
  %4 = tuple ()
  strong_release %0 : $foo
  dealloc_stack_ref %0 : $foo
  return %4 : $()
}

// We cannot remove the local store that is read.
//
// CHECK-LABEL: blocking_read_on_local_store
// CHECK: bb0
// CHECK: {{ store}}
// CHECK: return
sil hidden @blocking_read_on_local_store : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $Int, var, name "a"
  %1 = integer_literal $Builtin.Int64, 1
  %2 = struct $Int (%1 : $Builtin.Int64)
  store %2 to %0 : $*Int
  %4 = tuple ()
  %99 = load %0 : $*Int
  dealloc_stack %0 : $*Int
  return %4 : $()
}

// CHECK-LABEL: sil @store_after_store
// CHECK: bb0
// CHECK: {{ store}}
// CHECK-NOT: {{ store}}
// CHECK: return
sil @store_after_store : $@convention(thin) (@owned B) -> () {
bb0(%0 : $B):
  %1 = alloc_box $<τ_0_0> { var τ_0_0 } <B>
  %1a = project_box %1 : $<τ_0_0> { var τ_0_0 } <B>, 0
  store %0 to %1a : $*B
  store %0 to %1a : $*B
  %4 = tuple()
  return %4 : $()
}

// CHECK-LABEL: sil @dead_store_elimination_over_noread_builtins
// CHECK: bb0
// CHECK-NEXT: load
// CHECK-NEXT: integer_literal
// CHECK-NEXT: builtin
// CHECK-NEXT: tuple_extract
// CHECK-NEXT: builtin
// CHECK-NEXT: tuple_extract
// CHECK-NEXT: {{ store}}
// CHECK-NEXT: tuple
// CHECK-NEXT: return
sil @dead_store_elimination_over_noread_builtins : $@convention(thin) (@inout Builtin.Int64, @inout Builtin.Int64) -> () {
bb0(%0 : $*Builtin.Int64, %1 : $*Builtin.Int64):
  %2 = load %0 : $*Builtin.Int64
  %4 = integer_literal $Builtin.Int1, 0
  %5 = builtin "sadd_with_overflow_Int64"(%2 : $Builtin.Int64, %2 : $Builtin.Int64, %4 : $Builtin.Int1) : $(Builtin.Int64, Builtin.Int1)
  %6 = tuple_extract %5 : $(Builtin.Int64, Builtin.Int1), 0
  store %6 to %1 : $*Builtin.Int64
  %8 = builtin "smul_with_overflow_Int64"(%2 : $Builtin.Int64, %2 : $Builtin.Int64, %4 : $Builtin.Int1) : $(Builtin.Int64, Builtin.Int1)
  %9 = tuple_extract %8 : $(Builtin.Int64, Builtin.Int1), 0
  store %9 to %1 : $*Builtin.Int64
  %10 = tuple()
  return %10 : $()
}

// CHECK-LABEL: sil @post_dominating_dead_store : $@convention(thin) (@inout Builtin.Int32) -> () {
// CHECK: {{ store}}
// CHECK-NOT: {{ store}}
// CHECK: return
sil @post_dominating_dead_store : $@convention(thin) (@inout Builtin.Int32) -> () {
bb0(%0 : $*Builtin.Int32):
  %1 = integer_literal $Builtin.Int32, 0
  store %1 to %0 : $*Builtin.Int32
  cond_br undef, bb1, bb2

bb1:
  br bb3

bb2:
  br bb3

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

// CHECK-LABEL: sil @handle_unreachable : $@convention(thin) (@inout Builtin.Int32) -> () {
// CHECK: bb0
// CHECK-NEXT: integer_literal
// CHECK-NEXT: cond_br
// CHECK: return
sil @handle_unreachable : $@convention(thin) (@inout Builtin.Int32) -> () {
bb0(%0 : $*Builtin.Int32):
  %1 = integer_literal $Builtin.Int32, 0
  store %1 to %0 : $*Builtin.Int32
  cond_br undef, bb1, bb2

bb1:
  unreachable

bb2:
  br bb3

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

// CHECK-LABEL: sil @post_dominating_dead_store_partial : $@convention(thin) (@inout Builtin.Int32) -> () {
// CHECK: bb0(
// CHECK-NOT: {{ store}}
// CHECK: bb1:
// CHECK-NOT: store
// CHECK: bb2:
// CHECK: bb3:
// CHECK: {{ store}}
// CHECK: return
sil @post_dominating_dead_store_partial : $@convention(thin) (@inout Builtin.Int32) -> () {
bb0(%0 : $*Builtin.Int32):
  %1 = integer_literal $Builtin.Int32, 0
  %2 = integer_literal $Builtin.Int32, 1
  %3 = integer_literal $Builtin.Int32, 2
  store %1 to %0 : $*Builtin.Int32
  cond_br undef, bb1, bb2

bb1:
  store %2 to %0 : $*Builtin.Int32
  br bb3

bb2:
  br bb3

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

// We can't eliminate any stores here.
// CHECK-LABEL: sil @post_dominating_dead_store_fail : $@convention(thin) (@inout Builtin.Int32) -> () {
// CHECK: {{ store}}
// CHECK: {{ store}}
// CHECK-NOT: {{ store}}
// CHECK: return
sil @post_dominating_dead_store_fail : $@convention(thin) (@inout Builtin.Int32) -> () {
bb0(%0 : $*Builtin.Int32):
  %1 = integer_literal $Builtin.Int32, 0
  %2 = integer_literal $Builtin.Int32, 1
  store %1 to %0 : $*Builtin.Int32
  cond_br undef, bb1, bb2

bb1:
  store %2 to %0 : $*Builtin.Int32
  br bb2

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

// We cannot remove the local store as the debug_value w/ address value
// could be promoted and thus act as a read on the memory location..
//
// CHECK-LABEL: blocking_debug_value_addr_on_dead_store
// CHECK: bb0
// CHECK: {{ store}}
// CHECK: debug_value %{{.*}} : $*Int
sil hidden @blocking_debug_value_addr_on_dead_store : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $Int, var, name "a"
  %1 = integer_literal $Builtin.Int64, 1
  %2 = struct $Int (%1 : $Builtin.Int64)
  store %2 to %0 : $*Int
  debug_value %0 : $*Int
  %4 = tuple ()
  dealloc_stack %0 : $*Int
  return %4 : $()
}

// CHECK-LABEL: sil @test_read_dependence_allows_forwarding : $@convention(thin) (@inout A, A) -> A {
// CHECK: bb0
// CHECK-NEXT: {{ store}}
// CHECK-NEXT: unchecked_addr_cast
// CHECK-NEXT: unchecked_addr_cast
// CHECK-NEXT: load
// CHECK-NEXT: {{ store}}
// CHECK-NEXT: return
sil @test_read_dependence_allows_forwarding : $@convention(thin) (@inout A, A) -> A {
bb0(%0 : $*A, %1 : $A):
  store %1 to %0 : $*A
  %2 = unchecked_addr_cast %0 : $*A to $*A
  %3 = unchecked_addr_cast %2 : $*A to $*A
  // This means that the first store is not dead.
  %4 = load %3 : $*A
  store %1 to %0 : $*A
  return %4 : $A
}

// Make sure that we do not eliminate a partially dead store as if it
// was a full dead store.
//
// CHECK-LABEL: sil @partially_dead_store1 : $@convention(thin) (@inout AA, AA, A) -> () {
// CHECK: {{ store}}
// CHECK: {{ store}}
sil @partially_dead_store1 : $@convention(thin) (@inout AA, AA, A) -> () {
bb0(%0 : $*AA, %1 : $AA, %2 : $A):
  store %1 to %0 : $*AA
  %3 = unchecked_addr_cast %0 : $*AA to $*A
  store %2 to %3 : $*A
  %9999 = tuple()
  return %9999 : $()
}

// Make sure that we do not eliminate a partially dead store as if it
// was a full dead store.
//
// CHECK-LABEL: sil @partially_dead_store2 : $@convention(thin) (@inout AA, AA, A) -> () {
// CHECK: {{ store}}
// CHECK: {{ store}}
sil @partially_dead_store2 : $@convention(thin) (@inout AA, AA, A) -> () {
bb0(%0 : $*AA, %1 : $AA, %2 : $A):
  store %1 to %0 : $*AA
  %3 = struct_element_addr %0 : $*AA, #AA.a
  store %2 to %3 : $*A
  %9999 = tuple()
  return %9999 : $()
}

// Make sure that we properly eliminate the stores in bb1, bb2 from StoreMap.
//
// CHECK-LABEL: sil @store_map_failed_dead_object_elim_invalidation : $@convention(thin) () -> () {
// CHECK: bb1:
// CHECK: {{ store}}
// CHECK: bb2:
// CHECK: {{ store}}
// CHECK: bb3:
// CHECK: {{ store}}
sil @store_map_failed_dead_object_elim_invalidation : $@convention(thin) () -> () {
bb0:
  %0 = integer_literal $Builtin.Int32, 32
  %1 = integer_literal $Builtin.Int32, 64
  %2 = function_ref @escaped_a : $@convention(thin) () -> Builtin.RawPointer
  %3 = apply %2() : $@convention(thin) () -> Builtin.RawPointer
  %4 = pointer_to_address %3 : $Builtin.RawPointer to [strict] $*Builtin.Int32
  %5 = apply %2() : $@convention(thin) () -> Builtin.RawPointer
  %6 = pointer_to_address %5 : $Builtin.RawPointer to [strict] $*Builtin.Int32
  cond_br undef, bb1, bb2

bb1:
  store %0 to %4 : $*Builtin.Int32
  br bb3

bb2:
  store %1 to %4 : $*Builtin.Int32
  br bb3

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

sil @read_from_raw_pointer : $@convention(thin) (Builtin.RawPointer) -> UInt8 {
bb0(%0 : $Builtin.RawPointer):
  %1 = pointer_to_address %0 : $Builtin.RawPointer to [strict] $*UInt8
  %2 = load %1 : $*UInt8
  return %2 : $UInt8
}

// CHECK-LABEL: sil @dont_remove_store_to_escaping_allocstack_to_known_function : $@convention(thin) (UInt8) -> UInt8
// CHECK:        alloc_stack
// CHECK-NEXT:   store
// CHECK:      } // end sil function 'dont_remove_store_to_escaping_allocstack_to_known_function'
sil @dont_remove_store_to_escaping_allocstack_to_known_function : $@convention(thin) (UInt8) -> UInt8 {
bb0(%0 : $UInt8):
  %1 = alloc_stack $UInt8
  store %0 to %1 : $*UInt8
  %3 = address_to_pointer %1 : $*UInt8 to $Builtin.RawPointer
  %4 = function_ref @read_from_raw_pointer : $@convention(thin) (Builtin.RawPointer) -> UInt8
  %5 = apply %4(%3) : $@convention(thin) (Builtin.RawPointer) -> UInt8
  dealloc_stack %1 : $*UInt8
  return %5 : $UInt8
}

sil @unknown : $@convention(thin) () -> ()

// CHECK-LABEL: sil @inout_is_not_aliasing : $@convention(thin) (@inout Builtin.Int32) -> () {
// CHECK: bb0
// CHECK-NEXT: integer_literal
// CHECK-NEXT: function_ref
// CHECK: return
sil @inout_is_not_aliasing : $@convention(thin) (@inout Builtin.Int32) -> () {
bb0(%0 : $*Builtin.Int32):
  %1 = integer_literal $Builtin.Int32, 0
  store %1 to %0 : $*Builtin.Int32
  %f = function_ref @unknown : $@convention(thin) () -> ()
  %3 = apply %f() : $@convention(thin) () -> ()
  store %1 to %0 : $*Builtin.Int32
  %9999 = tuple()
  return %9999 : $()
}

// We should be able to remove the store in bb0, but we currently
// can't due to deficiency in alias analysis.
//
// CHECK-LABEL: dead_store_with_aliasing_base_in_simple_class
// CHECK: bb0([[RET0:%.+]] : $Bool):
// CHECK: {{ store}}
// CHECK: {{ store}}
sil hidden @dead_store_with_aliasing_base_in_simple_class : $@convention(thin) (Bool) -> () {
bb0(%0 : $Bool):
  %1 = alloc_ref $foo
  %2 = alloc_stack $foo
  store %1 to %2 : $*foo
  %8 = load %2 : $*foo
  %4 = integer_literal $Builtin.Int64, 12
  %5 = struct $Int (%4 : $Builtin.Int64)
  %6 = ref_element_addr %1 : $foo, #foo.a
  store %5 to %6 : $*Int
  %9 = ref_element_addr %8 : $foo, #foo.a
  store %5 to %9 : $*Int
  %14 = tuple ()
  dealloc_stack %2 : $*foo
  return %14 : $()
}

// Remove dead stores in if-else block on a simple struct as there are stores
// in the joint block.
//
// CHECK-LABEL: dead_store_diamond_control_flow
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: bb2:
// CHECK-NOT: {{ store}}
// CHECK: br
sil hidden @dead_store_diamond_control_flow : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  %7 = struct_extract %0 : $Bool, #Bool.value
  cond_br %7, bb1, bb2

bb1:
  %9 = integer_literal $Builtin.Int64, 0
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = struct_element_addr %2 : $*S1, #S1.a
  store %10 to %11 : $*Int
  br bb3

bb2:
  %14 = integer_literal $Builtin.Int64, 1
  %15 = struct $Int (%14 : $Builtin.Int64)
  %16 = struct_element_addr %2 : $*S1, #S1.a
  store %15 to %16 : $*Int
  br bb3

bb3:
  %19 = integer_literal $Builtin.Int64, 2
  %20 = struct $Int (%19 : $Builtin.Int64)
  %21 = struct_element_addr %2 : $*S1, #S1.a
  store %20 to %21 : $*Int
  %23 = tuple ()
  dealloc_stack %2 : $*S1
  return %23 : $()
}

// Remove a dead store in the split block as there are stores in the if-else
// blocks.
//
// CHECK-LABEL: dead_store_in_split_block_simple_struct
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: cond_br
sil hidden @dead_store_in_split_block_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  br bb1

bb1:
  %8 = struct_extract %0 : $Bool, #Bool.value
  %9 = integer_literal $Builtin.Int64, 0
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = struct_element_addr %2 : $*S1, #S1.a
  store %10 to %11 : $*Int
  cond_br %8, bb2, bb3

bb2:
  %14 = integer_literal $Builtin.Int64, 0
  %15 = struct $Int (%14 : $Builtin.Int64)
  %16 = struct_element_addr %2 : $*S1, #S1.a
  store %15 to %16 : $*Int
  br bb4

bb3:
  %19 = integer_literal $Builtin.Int64, 1
  %20 = struct $Int (%19 : $Builtin.Int64)
  %21 = struct_element_addr %2 : $*S1, #S1.a
  store %20 to %21 : $*Int
  br bb4

bb4:
  %24 = tuple ()
  dealloc_stack %2 : $*S1
  return %24 : $()
}

// Remove dead stores in split and else block.
//
// CHECK-LABEL: dead_store_split_else_block_simple_struct
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: cond_br
sil hidden @dead_store_split_else_block_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  br bb1

bb1:
  %8 = struct_extract %0 : $Bool, #Bool.value
  %9 = integer_literal $Builtin.Int64, 0
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = struct_element_addr %2 : $*S1, #S1.a
  store %10 to %11 : $*Int
  cond_br %8, bb2, bb3

bb2:
  br bb4

bb3:
  %15 = integer_literal $Builtin.Int64, 1
  %16 = struct $Int (%15 : $Builtin.Int64)
  %17 = struct_element_addr %2 : $*S1, #S1.a
  store %16 to %17 : $*Int
  br bb4

bb4:
  %20 = integer_literal $Builtin.Int64, 0
  %21 = struct $Int (%20 : $Builtin.Int64)
  %22 = struct_element_addr %2 : $*S1, #S1.a
  store %21 to %22 : $*Int
  %24 = tuple ()
  dealloc_stack %2 : $*S1
  return %24 : $()
}

// Remove dead stores in else block, store is only partially dead
// for split block.
//
// CHECK-LABEL: partial_dead_store_in_split_block_simple_struct
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: cond_br
sil hidden @partial_dead_store_in_split_block_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  br bb1

bb1:
  %8 = struct_extract %0 : $Bool, #Bool.value
  %9 = integer_literal $Builtin.Int64, 0
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = struct_element_addr %2 : $*S1, #S1.a
  %12 = load %11 : $*Int
  store %10 to %11 : $*Int
  cond_br %8, bb2, bb3

bb2:
  br bb4

bb3:
  %16 = integer_literal $Builtin.Int64, 1
  %17 = struct $Int (%16 : $Builtin.Int64)
  %18 = struct_element_addr %2 : $*S1, #S1.a
  store %17 to %18 : $*Int
  br bb4

bb4:
  %21 = integer_literal $Builtin.Int64, 0
  %22 = struct $Int (%21 : $Builtin.Int64)
  %23 = struct_element_addr %2 : $*S1, #S1.a
  store %22 to %23 : $*Int
  %25 = tuple ()
  dealloc_stack %2 : $*S1
  return %25 : $()
}

// Remove a dead store in the split block as there are stores in the if-else
// blocks.
//
// Store in bb1 is still alive as post-order does not iterate over unreachable
// block.
//
// CHECK-LABEL: dead_store_unreachable_predecessor_simple_struct
// CHECK: bb0
// CHECK-NOT: {{ store}}
// CHECK: br
// CHECK: bb1
// CHECK-NOT: {{ store}}
// CHECK: br
sil hidden @dead_store_unreachable_predecessor_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  br bb1

bb1:
  %8 = struct_extract %0 : $Bool, #Bool.value
  %9 = integer_literal $Builtin.Int64, 0
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = struct_element_addr %2 : $*S1, #S1.a
  store %10 to %11 : $*Int
  br bb3

bb2:
  %14 = integer_literal $Builtin.Int64, 0
  %15 = struct $Int (%14 : $Builtin.Int64)
  %16 = struct_element_addr %2 : $*S1, #S1.a
  store %15 to %16 : $*Int
  br bb3

bb3:
  %19 = integer_literal $Builtin.Int64, 1
  %20 = struct $Int (%19 : $Builtin.Int64)
  %21 = struct_element_addr %2 : $*S1, #S1.a
  store %20 to %21 : $*Int
  br bb4

bb4:
  %24 = tuple ()
  dealloc_stack %2 : $*S1
  return %24 : $()
}

// CHECK-LABEL: dead_store_split_block_complex_struct
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: br
// CHECK: bb2:
// CHECK-NOT: {{ store}}
// CHECK: br
sil hidden @dead_store_split_block_complex_struct : $@convention(thin) (Bool) -> () {
bb0(%0 : $Bool):
  %1 = alloc_stack $S2
  %2 = function_ref @S2_init : $@convention(thin) (@thin S2.Type) -> S2
  %3 = metatype $@thin S2.Type
  %4 = apply %2(%3) : $@convention(thin) (@thin S2.Type) -> S2
  store %4 to %1 : $*S2
  %6 = struct_extract %0 : $Bool, #Bool.value
  cond_br %6, bb1, bb2

bb1:
  %8 = integer_literal $Builtin.Int64, 0
  %9 = struct $Int (%8 : $Builtin.Int64)
  %10 = struct_element_addr %1 : $*S2, #S2.x
  %11 = struct_element_addr %10 : $*S1, #S1.a
  store %9 to %11 : $*Int
  br bb3

bb2:
  %14 = integer_literal $Builtin.Int64, 1
  %15 = struct $Int (%14 : $Builtin.Int64)
  %16 = struct_element_addr %1 : $*S2, #S2.x
  %17 = struct_element_addr %16 : $*S1, #S1.a
  store %15 to %17 : $*Int
  br bb3

bb3:
  %20 = integer_literal $Builtin.Int64, 2
  %21 = struct $Int (%20 : $Builtin.Int64)
  %22 = struct_element_addr %1 : $*S2, #S2.x
  %23 = struct_element_addr %22 : $*S1, #S1.a
  store %21 to %23 : $*Int
  %25 = tuple ()
  dealloc_stack %1 : $*S2
  return %25 : $()
}

// Remove dead stores in split and else block on a complex struct.
//
// CHECK-LABEL: dead_store_split_else_block_complex_struct
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: br
// CHECK: bb3:
// CHECK-NOT: {{ store}}
// CHECK: br
sil hidden @dead_store_split_else_block_complex_struct : $@convention(thin) (Bool) -> () {
bb0(%0 : $Bool):
  %1 = alloc_stack $S2
  %2 = function_ref @S2_init : $@convention(thin) (@thin S2.Type) -> S2
  %3 = metatype $@thin S2.Type
  %4 = apply %2(%3) : $@convention(thin) (@thin S2.Type) -> S2
  store %4 to %1 : $*S2
  br bb1

bb1:
  %7 = integer_literal $Builtin.Int64, 0
  %8 = struct $Int (%7 : $Builtin.Int64)
  %9 = struct_element_addr %1 : $*S2, #S2.x
  %10 = struct_element_addr %9 : $*S1, #S1.a
  store %8 to %10 : $*Int
  %12 = struct_extract %0 : $Bool, #Bool.value
  cond_br %12, bb2, bb3

bb2:
  br bb4

bb3:
  %15 = integer_literal $Builtin.Int64, 1
  %16 = struct $Int (%15 : $Builtin.Int64)
  %17 = struct_element_addr %1 : $*S2, #S2.x
  %18 = struct_element_addr %17 : $*S1, #S1.a
  store %16 to %18 : $*Int
  br bb4

bb4:
  %21 = integer_literal $Builtin.Int64, 2
  %22 = struct $Int (%21 : $Builtin.Int64)
  %23 = struct_element_addr %1 : $*S2, #S2.x
  %24 = struct_element_addr %23 : $*S1, #S1.a
  store %22 to %24 : $*Int
  %26 = tuple ()
  dealloc_stack %1 : $*S2
  return %26 : $()
}

// Remove dead store in 1 loop block, as the store in exit block kills it.
//
// CHECK-LABEL: dead_store_single_loop_block_simple_struct
// CHECK: bb2:
// CHECK: {{ store}}
// CHECK: br
sil hidden @dead_store_single_loop_block_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1, var, name "x"
  %5 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %6 = metatype $@thin S1.Type
  %7 = apply %5(%6) : $@convention(thin) (@thin S1.Type) -> S1
  store %7 to %2 : $*S1
  br bb1

bb1:
  %11 = integer_literal $Builtin.Int64, 0
  %12 = struct $Int (%11 : $Builtin.Int64)
  %13 = struct_element_addr %2 : $*S1, #S1.a
  %14 = load %13 : $*Int
  br bb2

bb2:
  %16 = integer_literal $Builtin.Int64, 1
  %17 = struct $Int (%16 : $Builtin.Int64)
  %18 = struct_element_addr %2 : $*S1, #S1.a
  store %17 to %18 : $*Int
  %9 = struct_extract %0 : $Bool, #Bool.value
  cond_br %9, bb1, bb3

bb3:
  %21 = integer_literal $Builtin.Int64, 2
  %22 = struct $Int (%21 : $Builtin.Int64)
  %23 = struct_element_addr %2 : $*S1, #S1.a
  store %22 to %23 : $*Int
  %25 = tuple ()
  dealloc_stack %2 : $*S1
  return %25 : $()
}

// Remove dead stores in loop blocks, as the store in exit block kills them.
//
// CHECK-LABEL: dead_store_multi_loop_blocks_simple_struct
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: br
// CHECK: bb2:
// CHECK-NOT: {{ store}}
// CHECK: br
sil hidden @dead_store_multi_loop_blocks_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1, var, name "x"
  %5 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %6 = metatype $@thin S1.Type
  %7 = apply %5(%6) : $@convention(thin) (@thin S1.Type) -> S1
  store %7 to %2 : $*S1
  br bb1

bb1:
  %11 = integer_literal $Builtin.Int64, 0
  %12 = struct $Int (%11 : $Builtin.Int64)
  %13 = struct_element_addr %2 : $*S1, #S1.a
  store %12 to %13 : $*Int
  br bb2

bb2:
  %16 = integer_literal $Builtin.Int64, 1
  %17 = struct $Int (%16 : $Builtin.Int64)
  %18 = struct_element_addr %2 : $*S1, #S1.a
  store %17 to %18 : $*Int
  %9 = struct_extract %0 : $Bool, #Bool.value
  cond_br %9, bb1, bb3

bb3:
  %21 = integer_literal $Builtin.Int64, 2
  %22 = struct $Int (%21 : $Builtin.Int64)
  %23 = struct_element_addr %2 : $*S1, #S1.a
  store %22 to %23 : $*Int
  %25 = tuple ()
  dealloc_stack %2 : $*S1
  return %25 : $()
}

// Remove dead store in the tuple data structure.
//
// CHECK-LABEL: dead_store_simple_tuple
// CHECK: bb0:
// CHECK: {{ store}}
// CHECK: {{ store}}
// CHECK-NOT: {{ store}}
// CHECK: load
sil hidden @dead_store_simple_tuple : $@convention(thin) () -> Int {
bb0:
  %0 = alloc_stack $(a: Int, b: Int), var, name "x"
  %1 = tuple_element_addr %0 : $*(a: Int, b: Int), 0
  %2 = tuple_element_addr %0 : $*(a: Int, b: Int), 1
  %3 = integer_literal $Builtin.Int64, 2
  %4 = struct $Int (%3 : $Builtin.Int64)
  store %4 to %1 : $*Int
  %6 = integer_literal $Builtin.Int64, 2
  %7 = struct $Int (%6 : $Builtin.Int64)
  store %7 to %2 : $*Int
  %9 = integer_literal $Builtin.Int64, 10
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = tuple_element_addr %0 : $*(a: Int, b: Int), 0
  store %10 to %11 : $*Int
  %13 = integer_literal $Builtin.Int64, 12
  %14 = struct $Int (%13 : $Builtin.Int64)
  %15 = tuple_element_addr %0 : $*(a: Int, b: Int), 1
  store %14 to %15 : $*Int
  %22 = load %15 : $*Int
  %23 = load %11 : $*Int
  %24 = load %2 : $*Int
  %25 = load %1 : $*Int
  %17 = integer_literal $Builtin.Int64, 22
  %18 = tuple ()
  %19 = struct $Int (%17 : $Builtin.Int64)
  dealloc_stack %0 : $*(a: Int, b: Int)
  return %19 : $Int
}

// Cannot remove partially dead store in split block for simple class.
//
// CHECK-LABEL: partial_dead_store_simple_class
// CHECK: bb1:
// CHECK: {{ store}}
// CHECK: cond_br
sil hidden @partial_dead_store_simple_class : $@convention(thin) (Bool) -> () {
bb0(%0 : $Bool):
  %1 = alloc_stack $foo
  %2 = alloc_ref $foo
  store %2 to %1 : $*foo
  br bb1

bb1:
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = ref_element_addr %2 : $foo, #foo.a
  store %6 to %7 : $*Int
  %9 = struct_extract %0 : $Bool, #Bool.value
  cond_br %9, bb2, bb3

bb2:
  br bb4

bb3:
  %12 = integer_literal $Builtin.Int64, 12
  %13 = struct $Int (%12 : $Builtin.Int64)
  %14 = ref_element_addr %2 : $foo, #foo.a
  store %13 to %14 : $*Int
  %16 = tuple ()
  br bb4

bb4:
  strong_release %2 : $foo
  %19 = tuple ()
  dealloc_stack %1 : $*foo
  return %19 : $()
}

// Cannot remove partially dead store in split block for simple class.
//
// CHECK-LABEL: partial_dead_store_with_function_call
// CHECK: bb1:
// CHECK: {{ store}}
// CHECK: cond_br
sil hidden @partial_dead_store_with_function_call : $@convention(thin) (Bool) -> () {
bb0(%0 : $Bool):
  %1 = alloc_stack $foo
  %3 = alloc_ref $foo
  store %3 to %1 : $*foo
  br bb1

bb1:
  %4 = integer_literal $Builtin.Int64, 10
  %5 = struct $Int (%4 : $Builtin.Int64)
  %6 = ref_element_addr %3 : $foo, #foo.a
  store %5 to %6 : $*Int
  %9 = struct_extract %0 : $Bool, #Bool.value
  cond_br %9, bb2, bb3

bb2:
  %32 = function_ref @foo_user : $@convention(thin) (@guaranteed foo) -> ()
  %33 = apply %32(%3) : $@convention(thin) (@guaranteed foo) -> ()
  %120 = integer_literal $Builtin.Int64, 12
  %121 = struct $Int (%120 : $Builtin.Int64)
  store %121 to %6 : $*Int
  %124 = tuple ()
  br bb4

bb3:
  %20 = integer_literal $Builtin.Int64, 12
  %21 = struct $Int (%20 : $Builtin.Int64)
  store %21 to %6 : $*Int
  %24 = tuple ()
  br bb4

bb4:
  strong_release %3 : $foo
  %35 = tuple ()
  dealloc_stack %1 : $*foo
  return %35 : $()
}

// Remove dead store in same basic block, test for alias analysis/side effect.
// Currently, %14 = apply %13(%10) is marked as having side effect on the
// store %8 to %9 : $*Int                          // id: %15
//
// CHECK-LABEL: dead_store_across_function_call
// CHECK: bb1:
// CHECK-NOT: {{ store}}
// CHECK: function_ref
sil hidden @dead_store_across_function_call : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  %7 = integer_literal $Builtin.Int64, 0
  %8 = struct $Int (%7 : $Builtin.Int64)
  %9 = struct_element_addr %2 : $*S1, #S1.a
  %10 = alloc_ref $foo
  br bb1

bb1:
  store %8 to %9 : $*Int
  %13 = function_ref @foo_user : $@convention(thin) (@guaranteed foo) -> ()
  %14 = apply %13(%10) : $@convention(thin) (@guaranteed foo) -> ()
  store %8 to %9 : $*Int
  br bb2

bb2:
  %17 = tuple ()
  dealloc_stack %2 : $*S1
  return %17 : $()
}


// store to stack allocated memory cannot alias with incoming argument.
//
// CHECK-LABEL: dead_store_inout_stack_alias
// CHECK: bb0
// CHECK: struct_element_addr
// CHECK-NOT: {{ store}}
// CHECK: load
sil hidden @dead_store_inout_stack_alias : $@convention(thin) (@inout A) -> () {
bb0(%0 : $*A):
  %1 = alloc_stack $A
  %2 = integer_literal $Builtin.Int32, 0
  %3 = struct_element_addr %0 : $*A, #A.i
  %4 = struct_element_addr %1 : $*A, #A.i
  store %2 to %4 : $*Builtin.Int32
  %6 = load %3 : $*Builtin.Int32
  store %2 to %4 : $*Builtin.Int32
  dealloc_stack %1 : $*A
  %9 = tuple ()
  return %9 : $()
}

// test dead store for enums. there should be only 1 store left.
//
// CHECK-LABEL: dead_store_enum_same_case
// CHECK: {{ store}}
// CHECK-NOT: {{ store}}
// CHECK: return
sil hidden @dead_store_enum_same_case : $@convention(thin) (@inout Example) -> Int64 {
bb0(%0 : $*Example):
  %1 = integer_literal $Builtin.Int64, 64
  %2 = struct $Int64 (%1 : $Builtin.Int64)
  %3 = integer_literal $Builtin.Int64, 64
  %4 = struct $Int64 (%3 : $Builtin.Int64)
  %5 = tuple (%2 : $Int64, %4 : $Int64)
  %6 = enum $Example, #Example.A!enumelt, %5 : $(Int64, Int64)
  store %6 to %0 : $*Example
  %8 = integer_literal $Builtin.Int64, 64
  %9 = struct $Int64 (%8 : $Builtin.Int64)
  %10 = integer_literal $Builtin.Int64, 64
  %11 = struct $Int64 (%10 : $Builtin.Int64)
  %12 = tuple (%9 : $Int64, %11 : $Int64)
  %13 = enum $Example, #Example.A!enumelt, %12 : $(Int64, Int64)
  store %13 to %0 : $*Example
  release_value %6 : $Example
  %16 = integer_literal $Builtin.Int64, 0
  %17 = struct $Int64 (%16 : $Builtin.Int64)
  release_value %13 : $Example
  return %17 : $Int64
}

/// Make sure we can coalesce the 2 live stores to the 2 fields in S4.
///
/// CHECK-LABEL: partial_dead_store_struct_in_struct
/// CHECK: [[RET0:%.+]] = struct_extract
/// CHECK: [[RET1:%.+]] = struct_element_addr
/// CHECK: {{ store}} [[RET0:%.+]] to [[RET1:%.+]] : $*S4
sil hidden @partial_dead_store_struct_in_struct : $@convention(thin) (@inout S5) -> () {
bb0(%0 : $*S5):
  %1 = function_ref @S5_init : $@convention(thin) (@thin S5.Type) -> S5
  %2 = metatype $@thin S5.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S5.Type) -> S5
  store %3 to %0 : $*S5
  %5 = integer_literal $Builtin.Int64, 11
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S5, #S5.y
  store %6 to %7 : $*Int
  %9 = tuple ()
  return %9 : $()
}

/// Make sure we do not coalesce the 2 live stores to the 2 fields in S6.
///
/// CHECK-LABEL: sil hidden @discontiguous_partial_dead_store_simple_struct
/// CHECK: store
/// CHECK: store
sil hidden @discontiguous_partial_dead_store_simple_struct : $@convention(thin) (@inout S6) -> () {
bb0(%0 : $*S6):
  %1 = function_ref @S6_init : $@convention(thin) (@thin S6.Type) -> S6
  %2 = metatype $@thin S6.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S6.Type) -> S6
  store %3 to %0 : $*S6
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S6, #S6.y
  store %6 to %7 : $*Int
  %9 = tuple ()
  return %9 : $()
}

/// Make sure we generate the store to field x first.
///
/// CHECK-LABEL: sil hidden @discontiguous_partial_dead_store_lives_insert_deterministically
/// CHECK: bb0([[A:%.*]] : $*S6):
/// CHECK: [[IN:%.*]] = apply
/// CHECK: [[EXT1:%.*]] = struct_extract [[IN]] : $S6, #S6.x
/// CHECK: [[EXT2:%.*]] =  struct_element_addr [[A]] : $*S6, #S6.x
/// CHECK: store [[EXT1]] to [[EXT2]] : $*Int
sil hidden @discontiguous_partial_dead_store_lives_insert_deterministically : $@convention(thin) (@inout S6) -> () {
bb0(%0 : $*S6):
  %1 = function_ref @S6_init : $@convention(thin) (@thin S6.Type) -> S6
  %2 = metatype $@thin S6.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S6.Type) -> S6
  store %3 to %0 : $*S6
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S6, #S6.y
  store %6 to %7 : $*Int
  %9 = tuple ()
  return %9 : $()
}

/// Make sure we do not generate too many stores from a large store that
/// is partially dead.
///
/// CHECK-LABEL: sil hidden @discontiguous_partial_dead_store_simple_large_struct
/// CHECK: store
/// CHECK: store
sil hidden @discontiguous_partial_dead_store_simple_large_struct : $@convention(thin) (@inout S7) -> () {
bb0(%0 : $*S7):
  %1 = function_ref @S7_init : $@convention(thin) (@thin S7.Type) -> S7
  %2 = metatype $@thin S7.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S7.Type) -> S7
  store %3 to %0 : $*S7
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S7, #S7.y
  store %6 to %7 : $*Int
  %9 = tuple ()
  return %9 : $()
}

/// We are not performing partial dead store for store %3 to %0#1 : $*S7,
/// i.e. too many stores generated, but make sure we track the store correctly
/// so that we can get rid of store %56 to %57 : $*Int.
///
/// CHECK-LABEL: partial_dead_store_bail_out_proper_propagation
/// CHECK: bb0
/// CHECK-NOT: {{ store}}
/// CHECK: function_ref
sil hidden @partial_dead_store_bail_out_proper_propagation : $@convention(thin) () -> () {
bb0:
  %0 = alloc_stack $S7, var, name "a"
  %55 = integer_literal $Builtin.Int64, 10
  %56 = struct $Int (%55 : $Builtin.Int64)
  %57 = struct_element_addr %0 : $*S7, #S7.a
  store %56 to %57 : $*Int
  %1 = function_ref @S7_init : $@convention(thin) (@thin S7.Type) -> S7
  %2 = metatype $@thin S7.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S7.Type) -> S7
  store %3 to %0 : $*S7
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S7, #S7.y
  store %6 to %7 : $*Int
  %9 = tuple ()
  dealloc_stack %0 : $*S7
  return %9 : $()
}

/// Make sure we do perform partial dead store for the first store.
/// we have a case which partial dead store miscompiles a program,
/// in that case the bitvector is not tracked correctly and we end
/// up deleting the entire larger store, store %3 to %0#1 : $*S3 in
/// this case.
///
/// CHECK-LABEL: partial_dead_store_simple_struct
/// CHECK: apply
/// CHECK-NEXT: struct_extract
sil hidden @partial_dead_store_simple_struct : $@convention(thin) (@inout S3) -> () {
bb0(%0 : $*S3):
  %1 = function_ref @S3_init : $@convention(thin) (@thin S3.Type) -> S3
  %2 = metatype $@thin S3.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S3.Type) -> S3
  store %3 to %0 : $*S3
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S3, #S3.a
  store %6 to %7 : $*Int
  %9 = tuple ()
  return %9 : $()
}

/// Make sure we do not hang in this test case. Test for Location::expand.
/// expand should stop on class type. Also need to get rid of the partial
/// dead store.
///
/// CHECK-LABEL: self_loop_class_type_expansion
/// CHECK: [[RET0:%.+]] = struct_extract
/// CHECK: [[RET1:%.+]] = struct_element_addr
/// CHECK-NEXT: store [[RET0:%.+]] to [[RET1:%.+]] : $*SelfLoop
sil hidden @self_loop_class_type_expansion : $@convention(thin) (@inout S8) -> () {
bb0(%0 : $*S8):
  %1 = function_ref @S8_init : $@convention(thin) (@thin S8.Type) -> @owned S8
  %2 = metatype $@thin S8.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S8.Type) -> @owned S8
  store %3 to %0 : $*S8
  %5 = integer_literal $Builtin.Int64, 12
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S8, #S8.k
  store %6 to %7 : $*Int
  %9 = struct_extract %3 : $S8, #S8.i
  %10 = struct $S8 (%9 : $SelfLoop, %6 : $Int)
  release_value %10 : $S8
  %12 = tuple ()
  return %12 : $()
}

/// Make sure we do not remove the first store as there is no way to prove
/// %0 and %1 cannot alias here.
///
/// CHECK-LABEL: no_dead_store_with_interfering_load
/// CHECK: {{ store}}
/// CHECK: load
/// CHECK: {{ store}}
sil hidden @no_dead_store_with_interfering_load : $@convention(thin) (@owned foo, @owned foo) -> () {
bb0(%0 : $foo, %1 : $foo):
  %4 = integer_literal $Builtin.Int64, 10
  %5 = struct $Int (%4 : $Builtin.Int64)
  %6 = ref_element_addr %0 : $foo, #foo.a
  store %5 to %6 : $*Int
  %9 = integer_literal $Builtin.Int64, 12
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = ref_element_addr %1 : $foo, #foo.a
  %99 = load %11 : $*Int
  %14 = integer_literal $Builtin.Int64, 10
  %15 = struct $Int (%14 : $Builtin.Int64)
  %16 = ref_element_addr %0 : $foo, #foo.a
  store %15 to %16 : $*Int
  strong_release %1 : $foo
  strong_release %0 : $foo
  %21 = tuple ()
  return %21 : $()
}

// Remove the dead stores in the entry block as the store in bb2
// kills them. This test how the optimistic data flow works.
//
// CHECK-LABEL: dead_store_across_loop_simple_struct
// CHECK: bb0
// CHECK-NOT: {{ store}}
// CHECK: br
sil hidden @dead_store_across_loop_simple_struct : $@convention(thin) (Bool, Int) -> () {
bb0(%0 : $Bool, %1 : $Int):
  %2 = alloc_stack $S1
  %3 = function_ref @S1_init : $@convention(thin) (@thin S1.Type) -> S1
  %4 = metatype $@thin S1.Type
  %5 = apply %3(%4) : $@convention(thin) (@thin S1.Type) -> S1
  store %5 to %2 : $*S1
  %7 = integer_literal $Builtin.Int64, 2
  %8 = struct $Int (%7 : $Builtin.Int64)
  %9 = struct_element_addr %2 : $*S1, #S1.a
  store %8 to %9 : $*Int
  br bb1

bb1:
  %12 = struct_extract %0 : $Bool, #Bool.value
  cond_br %12, bb1, bb2

bb2:
  %14 = integer_literal $Builtin.Int64, 2
  %15 = struct $Int (%14 : $Builtin.Int64)
  %16 = struct_element_addr %2 : $*S1, #S1.a
  store %15 to %16 : $*Int
  %18 = tuple ()
  dealloc_stack %2 : $*S1
  return %18 : $()
}

// Make sure the load in bb1 prevents the store in bb0 to be eliminated. we have a bug
// in constructing kill set when it is not conservative enough. i.e. this test case
// makes sure the killset for bb1 includes the kill for the store in bb2.
//
// CHECK-LABEL: conservative_kill_set_class
// CHECK: bb0
// CHECK: {{ store}}
// CHECK: br bb1
sil hidden @conservative_kill_set_class : $@convention(thin) (@owned foo, @owned foo) -> () {
bb0(%0 : $foo, %1 : $foo):
  %4 = integer_literal $Builtin.Int64, 10
  %5 = struct $Int (%4 : $Builtin.Int64)
  %6 = ref_element_addr %0 : $foo, #foo.a
  store %5 to %6 : $*Int
  br bb1

bb1:
  %7 = ref_element_addr %1 : $foo, #foo.a
  %8 = load %7 : $*Int
  br bb2

bb2:
  %9 = integer_literal $Builtin.Int64, 10
  %10 = struct $Int (%9 : $Builtin.Int64)
  %11 = ref_element_addr %0 : $foo, #foo.a
  store %5 to %6 : $*Int
  %18 = tuple ()
  return %18 : $()
}

/// Make sure we DO NOT get rid of the first store as a dead store.
///
/// CHECK-LABEL: tbaa_no_alias_no_dead_store
/// CHECK: {{ store}}
/// CHECK: load
sil @tbaa_no_alias_no_dead_store : $@convention(thin) (Optional<@thick Any.Type>) -> Int {
bb0(%0 : $Optional<@thick Any.Type>):
  %2 = alloc_stack $Optional<@thick Any.Type>
  store %0 to %2 : $*Optional<@thick Any.Type>
  %17 = unchecked_addr_cast %2 : $*Optional<@thick Any.Type> to $*Int
  %18 = load %17 : $*Int
  dealloc_stack %2 : $*Optional<@thick Any.Type>
  return %18 : $Int
}

/// Make sure we DO get rid of the store as a dead store, i.e. no read to a store
/// to a local variable.
///
/// CHECK-LABEL: local_dead_store
/// CHECK: load
/// CHECK-NOT: {{ store}}
/// CHECK: return
sil @local_dead_store : $@convention(thin) (Optional<@thick Any.Type>) -> Int {
bb0(%0 : $Optional<@thick Any.Type>):
  %2 = alloc_stack $Optional<@thick Any.Type>
  %17 = unchecked_addr_cast %2 : $*Optional<@thick Any.Type> to $*Int
  %18 = load %17 : $*Int
  store %0 to %2 : $*Optional<@thick Any.Type>
  dealloc_stack %2 : $*Optional<@thick Any.Type>
  return %18 : $Int
}

/// Make sure we do perform partial dead store for the first store.
/// we have a case which partial dead store miscompiles a program,
/// in that case the bitvector is not tracked correctly and we end
/// up deleting the entire larger store, store %3 to %0#1 : $*S3 in
/// this case.
///
/// CHECK-LABEL: partial_dead_store_in_nested_struct
/// CHECK: apply
/// CHECK-NEXT: struct_extract
sil hidden @partial_dead_store_in_nested_struct : $@convention(thin) (@inout S9) -> () {
bb0(%0 : $*S9):
  %1 = function_ref @S9_init : $@convention(thin) (@thin S9.Type) -> S9
  %2 = metatype $@thin S9.Type
  %3 = apply %1(%2) : $@convention(thin) (@thin S9.Type) -> S9
  store %3 to %0 : $*S9
  %5 = integer_literal $Builtin.Int64, 10
  %6 = struct $Int (%5 : $Builtin.Int64)
  %7 = struct_element_addr %0 : $*S9, #S9.x
  %8 = struct_element_addr %7 : $*S3, #S3.a
  store %6 to %8 : $*Int
  %9 = tuple ()
  return %9 : $()
}

// CHECK-LABEL: dont_remove_store_to_stack_used_as_partial_apply_indirect_parameter
// CHECK:      [[S:%[0-9]+]] = alloc_stack
// CHECK-NEXT: store %0 to [[S]]
sil @dont_remove_store_to_stack_used_as_partial_apply_indirect_parameter : $@convention(thin) (Int) ->  @owned @callee_owned (Bool) -> Int {
bb0(%0 : $Int):
  %s = alloc_stack $Int
  store %0 to %s : $*Int
  %f = function_ref @callee : $@convention(thin) (@in Int) ->  @owned @callee_owned (Bool) -> Int
  %a = apply %f(%s) : $@convention(thin) (@in Int) ->  @owned @callee_owned (Bool) -> Int
  dealloc_stack %s : $*Int
  return %a : $@callee_owned (Bool) -> Int
}

sil @callee : $@convention(thin) (@in Int) ->  @owned @callee_owned (Bool) -> Int {
bb0(%0 : $*Int):
  %2 = function_ref @closure : $@convention(thin) (Bool, @in Int) -> Int
  %3 = partial_apply %2(%0) : $@convention(thin) (Bool, @in Int) -> Int
  return %3 : $@callee_owned (Bool) -> Int
}

sil @closure : $@convention(thin) (Bool, @in Int) -> Int

// Make sure we invalidate the store in bb1 when we process the SILargument. If not
// we could remove the store in bb1 which is incorrect.
//
// CHECK-LABEL: invalidate_base_for_silargument
// CHECK: bb1([[A0:%.+]] : $foo):
// CHECK: {{ store}}
// CHECK: bb2:
// CHECK: {{ store}}
sil hidden @invalidate_base_for_silargument : $@convention(thin) () -> () {
bb0:
  %1 = alloc_ref $foo
  %4 = integer_literal $Builtin.Int64, 12
  %5 = struct $Int (%4 : $Builtin.Int64)
  br bb1(%1 : $foo)

bb1(%2 : $foo):
  %6 = ref_element_addr %2 : $foo, #foo.a
  store %5 to %6 : $*Int
  %9 = alloc_ref $foo
  cond_br undef, bb1(%9: $foo), bb2

bb2:
  %7 = ref_element_addr %2 : $foo, #foo.a
  store %5 to %7 : $*Int
  %14 = tuple ()
  return %14 : $()
}

// CHECK-LABEL: test_is_unique
// CHECK: %1 = alloc_stack
// CHECK: store %0 to %1 
// CHECK: is_unique
// CHECK: return
sil @test_is_unique : $@convention(thin) (@guaranteed AB) -> Builtin.Int1 {
bb0(%0 : $AB):                     // Preds: bb6 bb5 bb4 bb3
  %1 = alloc_stack $AB
  store %0 to %1 : $*AB
  %2 = is_unique %1 : $*AB
  dealloc_stack %1 : $*AB
  return %2 : $Builtin.Int1
}

// CHECK-LABEL: dont_remove_store
// CHECK: load
// CHECK: store
// CHECK: value_metatype
// CHECK: return
sil @dont_remove_store : $@convention(thin) (@in_guaranteed foo) -> () {
bb0(%0 : $*foo):
  %1 = alloc_stack $foo
  %2 = load %0 : $*foo
  store %2 to %1 : $*foo
  %3 = value_metatype $@thick foo.Type, %1 : $*foo
  dealloc_stack %1 : $*foo
  %20 = tuple()
  return %20 : $()
}

// Check that begin_access, end_access, strong_release, set_deallocating, and dealloc_ref don't prevent optimization.
// CHECK-LABEL: ignore_read_write
// CHECK: bb0
// CHECK-NOT: store
// CHECK-LABEL: end sil function 'ignore_read_write'
sil @ignore_read_write : $@convention(thin) () -> Int {
bb0:
  %1 = alloc_ref [stack] $foo
  %2 = integer_literal $Builtin.Int64, 0
  %3 = struct $Int (%2 : $Builtin.Int64)
  %4 = ref_element_addr %1 : $foo, #foo.a
  store %3 to %4 : $*Int
  %6 = begin_dealloc_ref %1 : $foo of %1 : $foo
  dealloc_ref %6 : $foo
  dealloc_stack_ref %1 : $foo
  return %3 : $Int
}

sil @read_from_argument : $@convention(thin) (@in_guaranteed Int) -> ()

// CHECK-LABEL: sil @test_ref_tail_addr  :
// CHECK-NOT:     store
// CHECK:       end sil function 'test_ref_tail_addr'
sil @test_ref_tail_addr : $@convention(thin) (Int) -> () {
bb0(%0 : $Int):
  %1 = integer_literal $Builtin.Word, 1
  %2 = alloc_ref [stack] [tail_elems $Int * %1 : $Builtin.Word] $foo
  %3 = ref_element_addr %2 : $foo, #foo.a
  store %0 to %3 : $*Int
  %5 = ref_tail_addr %2 : $foo, $Int
  %6 = function_ref @read_from_argument : $@convention(thin) (@in_guaranteed Int) -> ()
  %7 = apply %6(%5) : $@convention(thin) (@in_guaranteed Int) -> ()
  dealloc_stack_ref %2 : $foo
  %r = tuple ()
  return %r : $()
}

// CHECK-LABEL: sil @test_split_tuple  :
// CHECK:         [[T1:%.*]] = tuple_element_addr %1 : $*(Int, Int), 0 
// CHECK-NEXT:    store {{.*}} to [[T1]]
// CHECK-NOT:     store
// CHECK:         fix_lifetime
// CHECK-NEXT:    [[T2:%.*]] = tuple_element_addr %1 : $*(Int, Int), 1
// CHECK-NEXT:    store %0 to [[T2]]
// CHECK-NOT:     store
// CHECK:       end sil function 'test_split_tuple'
sil @test_split_tuple : $@convention(thin) (Int, @inout (Int, Int)) -> () {
bb0(%0 : $Int, %1 : $*(Int, Int)):
  %2 = tuple (%0 : $Int, %0 : $Int)
  store %2 to %1 : $*(Int, Int)
  fix_lifetime %0 : $Int
  %4 = tuple_element_addr %1 : $*(Int, Int), 1
  store %0 to %4 : $*Int
  %r = tuple ()
  return %r : $()
}

// CHECK-LABEL: sil [ossa] @test_ossa_not_trivial  :
// CHECK:         store %0
// CHECK:         store %1
// CHECK:       end sil function 'test_ossa_not_trivial'
sil [ossa] @test_ossa_not_trivial : $@convention(thin) (@owned foo, @owned foo, @inout foo) -> () {
bb0(%0 : @owned $foo, %1 : @owned $foo, %2 : $*foo):
  store %0 to [assign] %2 : $*foo
  store %1 to [assign] %2 : $*foo
  %r = tuple ()
  return %r : $()
}

// CHECK-LABEL: sil [ossa] @test_ossa_partial_trivial  :
// CHECK-NOT:     store %0
// CHECK:         store %1
// CHECK:       end sil function 'test_ossa_partial_trivial'
sil [ossa] @test_ossa_partial_trivial : $@convention(thin) (Int, @owned IntAndFoo, @inout IntAndFoo) -> () {
bb0(%0 : $Int, %1 : @owned $IntAndFoo, %2 : $*IntAndFoo):
  %3 = struct_element_addr %2 : $*IntAndFoo, #IntAndFoo.i
  store %0 to [trivial] %3 : $*Int
  store %1 to [assign] %2 : $*IntAndFoo
  %r = tuple ()
  return %r : $()
}

// CHECK-LABEL: sil @test_bind_memory  :
// CHECK:         store %0
// CHECK:       end sil function 'test_bind_memory'
sil @test_bind_memory : $@convention(thin) (UInt64, Builtin.Word) -> Builtin.Int8 {
bb0(%0 : $UInt64, %1 : $Builtin.Word):
  %35 = alloc_stack $(UInt64, UInt64)
  %36 = tuple_element_addr %35 : $*(UInt64, UInt64), 0
  store %0 to %36 : $*UInt64
  %50 = address_to_pointer %35 : $*(UInt64, UInt64) to $Builtin.RawPointer
  %52 = bind_memory %50 : $Builtin.RawPointer, %1 : $Builtin.Word to $*UInt8
  %72 = pointer_to_address %50 : $Builtin.RawPointer to [strict] $*UInt8
  %75 = struct_element_addr %72 : $*UInt8, #UInt8._value
  %76 = load %75 : $*Builtin.Int8
  dealloc_stack %35 : $*(UInt64, UInt64)
  return %76 : $Builtin.Int8
}

class Klass {}

sil @klassClosure : $@convention(thin) (@in_guaranteed Klass) -> ()

sil @test_pa_without_apply : $@convention(thin) (@in Klass) -> @callee_guaranteed () -> () {
bb0(%0 : $*Klass):
  %3 = function_ref @klassClosure : $@convention(thin) (@in_guaranteed Klass) -> ()
  %4 = partial_apply [callee_guaranteed] %3(%0) : $@convention(thin) (@in_guaranteed Klass) -> ()
  return %4 : $@callee_guaranteed ()  -> ()
}

// CHECK-SEA-DSE: sil @dont_dead_store_capture :
// CHECK-SEA-DSE: store
// CHECK-SEA-DSE: } // end sil function 'dont_dead_store_capture'
sil @dont_dead_store_capture : $@convention(thin) (@in_guaranteed (Klass, Klass)) -> () {
bb0(%0 : $*(Klass, Klass)):
  %ele = tuple_element_addr %0 : $*(Klass, Klass), 1
  %1 = load %ele : $*Klass
  %3 = alloc_stack $Klass
  store %1 to %3 : $*Klass
  strong_retain %1 : $Klass
  %4 = function_ref @test_pa_without_apply : $@convention(thin) (@in Klass) -> @callee_guaranteed () -> ()
  %5 = apply %4(%3) : $@convention(thin) (@in Klass) -> @callee_guaranteed () -> ()
  %6 = apply %5() : $@callee_guaranteed () -> ()
  dealloc_stack %3 : $*Klass
  %7 = tuple ()
  return %7 : $()
}

// CHECK-LABEL: sil @indexing_is_not_overlapping :
// CHECK:         store %0
// CHECK:         store %0
// CHECK:       end sil function 'indexing_is_not_overlapping'
sil @indexing_is_not_overlapping : $@convention(thin) (Int, Builtin.RawPointer) -> () {
bb0(%0 : $Int, %1 : $Builtin.RawPointer):
  %2 = pointer_to_address %1 : $Builtin.RawPointer to [strict] $*Int
  %3 = integer_literal $Builtin.Word, 3
  %4 = index_addr [stack_protection] %2 : $*Int, %3 : $Builtin.Word
  store %0 to %4 : $*Int
  store %0 to %2 : $*Int
  %r = tuple ()
  return %r : $()
}

// CHECK-LABEL: sil @indexing_is_not_overlapping2 :
// CHECK:         store %1
// CHECK:         store %0
// CHECK:       end sil function 'indexing_is_not_overlapping2'
sil @indexing_is_not_overlapping2 : $@convention(thin) (Int, Builtin.Int64, Builtin.RawPointer) -> () {
bb0(%0 : $Int, %1 : $Builtin.Int64, %2 : $Builtin.RawPointer):
  %3 = pointer_to_address %2 : $Builtin.RawPointer to [strict] $*Int
  %4 = integer_literal $Builtin.Word, 3
  %5 = index_addr [stack_protection] %3 : $*Int, %4 : $Builtin.Word
  %6 = struct_element_addr %5 : $*Int, #Int.value
  store %1 to %6 : $*Builtin.Int64
  store %0 to %3 : $*Int
  %r = tuple ()
  return %r : $()
}