// RUN: %target-sil-opt -enable-sil-verify-all -dce %s | %FileCheck %s

sil_stage canonical

import Builtin
import Swift

public struct S {
  var o: AnyObject
}

typealias Int1 = Builtin.Int1

class C {}

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

struct CAndBit {
    var c: C
    var bit: Int1
}

@_moveOnly
struct MO {
    deinit
}

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

// CHECK-LABEL: sil [ossa] @dead1 :
// CHECK: bb0
// CHECK-NEXT: return %0
// CHECK-LABEL: } // end sil function 'dead1'
sil [ossa] @dead1 : $@convention(thin) (Int32, Int32) -> Int32 {
bb0(%0 : $Int32, %1 : $Int32):
  %3 = struct_extract %0 : $Int32, #Int32._value
  %4 = struct_extract %1 : $Int32, #Int32._value
  %5 = integer_literal $Builtin.Int1, -1
  %6 = builtin "sadd_with_overflow_Int32"(%3 : $Builtin.Int32, %4 : $Builtin.Int32, %5 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %7 = tuple_extract %6 : $(Builtin.Int32, Builtin.Int1), 0
  %8 = struct $Int32 (%7 : $Builtin.Int32)
  return %0 : $Int32
}

// CHECK-LABEL: sil [ossa] @dead2 :
sil [ossa] @dead2 : $@convention(thin) () -> () {
bb0:
  %0 = integer_literal $Builtin.Int32, 2
  %1 = integer_literal $Builtin.Int32, 0
  br bb1(%0 : $Builtin.Int32, %1 : $Builtin.Int32)

bb1(%3 : $Builtin.Int32, %4 : $Builtin.Int32):
  %5 = integer_literal $Builtin.Int32, 100
  %7 = builtin "cmp_slt_Int32"(%4 : $Builtin.Int32, %5 : $Builtin.Int32) : $Builtin.Int1
  cond_br %7, bb2, bb3

bb2:
  %9 = integer_literal $Builtin.Int32, 3
  %11 = integer_literal $Builtin.Int1, -1
  %12 = builtin "sadd_with_overflow_Int32"(%3 : $Builtin.Int32, %9 : $Builtin.Int32, %11 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %13 = tuple_extract %12 : $(Builtin.Int32, Builtin.Int1), 0
  %14 = integer_literal $Builtin.Int32, 1
  %15 = builtin "sadd_with_overflow_Int32"(%4 : $Builtin.Int32, %14 : $Builtin.Int32, %11 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %16 = tuple_extract %15 : $(Builtin.Int32, Builtin.Int1), 0
  br bb1(%13 : $Builtin.Int32, %16 : $Builtin.Int32)

bb3:
  %18 = tuple ()
  return %18 : $()
}
// CHECK-LABEL: } // end sil function 'dead2'

// CHECK-LABEL: sil [ossa] @dead3 :
sil [ossa] @dead3 : $@convention(thin) () -> () {
bb0:
// CHECK: bb0
  br bb1
// CHECK: bb1
bb1:
// CHECK:      bb1:
// CHECK-NEXT:   br bb1
  %0 = integer_literal $Builtin.Int32, 0
  br bb1
}
// CHECK-LABEL: } // end sil function 'dead3'

// CHECK-LABEL: sil [ossa] @test_dce_bbargs :
sil [ossa] @test_dce_bbargs : $@convention(thin) () -> () {
bb0:
  %0 = integer_literal $Builtin.Int32, 0
  %1 = struct $Int32 (%0 : $Builtin.Int32)
  %2 = integer_literal $Builtin.Int32, 0
  %3 = struct $Int32 (%2 : $Builtin.Int32)
  %4 = integer_literal $Builtin.Int32, 0
  %5 = struct $Int32 (%4 : $Builtin.Int32)
  %6 = integer_literal $Builtin.Int32, 0
  %7 = struct $Int32 (%6 : $Builtin.Int32)
  %8 = integer_literal $Builtin.Int32, 0
  %9 = struct $Int32 (%8 : $Builtin.Int32)
  %10 = integer_literal $Builtin.Int32, 0
  %11 = struct $Int32 (%10 : $Builtin.Int32)
  br bb1(%1 : $Int32, %3 : $Int32, %11 : $Int32, %7 : $Int32, %9 : $Int32)

bb1(%13 : $Int32, %14 : $Int32, %15 : $Int32, %16 : $Int32, %17 : $Int32):
  %18 = integer_literal $Builtin.Int32, 11
  %20 = struct_extract %15 : $Int32, #Int32._value
  %21 = builtin "cmp_slt_Int32"(%20 : $Builtin.Int32, %18 : $Builtin.Int32) : $Builtin.Int1
  %22 = struct $Bool (%21 : $Builtin.Int1)
  %23 = struct_extract %22 : $Bool, #Bool._value
  cond_br %23, bb2, bb12

// CHECK: bb2:
bb2:
  %25 = integer_literal $Builtin.Int32, 0
  %26 = struct $Int32 (%25 : $Builtin.Int32)
  br bb3(%13 : $Int32, %14 : $Int32, %26 : $Int32, %17 : $Int32)

bb3(%28 : $Int32, %29 : $Int32, %30 : $Int32, %31 : $Int32):
  %32 = integer_literal $Builtin.Int32, 22
  %34 = struct_extract %30 : $Int32, #Int32._value
  %35 = builtin "cmp_slt_Int32"(%34 : $Builtin.Int32, %32 : $Builtin.Int32) : $Builtin.Int1
  %36 = struct $Bool (%35 : $Builtin.Int1)
  %37 = struct_extract %36 : $Bool, #Bool._value
  cond_br %37, bb4, bb11

// CHECK: bb4:
bb4:
  %39 = integer_literal $Builtin.Int32, 0
  %41 = struct_extract %28 : $Int32, #Int32._value
  %42 = builtin "cmp_eq_Int32"(%39 : $Builtin.Int32, %41 : $Builtin.Int32) : $Builtin.Int1
  %43 = struct $Bool (%42 : $Builtin.Int1)
  %44 = struct_extract %43 : $Bool, #Bool._value
// CHECK-NOT: cond_br
// CHECK: br bb5
  cond_br %44, bb5, bb6

bb5:
  %46 = integer_literal $Builtin.Int32, 0
  %47 = struct $Int32 (%46 : $Builtin.Int32)
  br bb7(%47 : $Int32)

bb6:
 br bb7(%28 : $Int32)

bb7(%49 : $Int32):
  %50 = integer_literal $Builtin.Int32, 10
  %52 = struct_extract %29 : $Int32, #Int32._value
  %53 = builtin "cmp_eq_Int32"(%50 : $Builtin.Int32, %52 : $Builtin.Int32) : $Builtin.Int1
  %54 = struct $Bool (%53 : $Builtin.Int1)
  %55 = struct_extract %54 : $Bool, #Bool._value
  cond_br %55, bb8, bb9

bb8:
  %57 = integer_literal $Builtin.Int32, 0
  %58 = struct $Int32 (%57 : $Builtin.Int32)
  br bb10(%58 : $Int32)

bb9:
  br bb10(%29 : $Int32)

// CHECK: bb5([[BBARG:%.*]]):
bb10(%60 : $Int32):
  %61 = struct_extract %31 : $Int32, #Int32._value
  %62 = integer_literal $Builtin.Int32, 1
  %64 = integer_literal $Builtin.Int1, -1
// CHECK-NOT: builtin "sadd_with_overflow_Int32"
// CHECK-NOT: cond_fail
  %65 = builtin "sadd_with_overflow_Int32"(%61 : $Builtin.Int32, %62 : $Builtin.Int32, %64 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %66 = tuple_extract %65 : $(Builtin.Int32, Builtin.Int1), 0
  %67 = tuple_extract %65 : $(Builtin.Int32, Builtin.Int1), 1
  cond_fail %67 : $Builtin.Int1
  %69 = struct $Int32 (%66 : $Builtin.Int32)
  %70 = struct_extract %30 : $Int32, #Int32._value
  %71 = integer_literal $Builtin.Int32, 1
  %73 = integer_literal $Builtin.Int1, -1
// CHECK: builtin "ssub_with_overflow_Int32"
  %74 = builtin "ssub_with_overflow_Int32"(%70 : $Builtin.Int32, %71 : $Builtin.Int32, %73 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %75 = tuple_extract %74 : $(Builtin.Int32, Builtin.Int1), 0
  %76 = tuple_extract %74 : $(Builtin.Int32, Builtin.Int1), 1
// CHECK: cond_fail
  cond_fail %76 : $Builtin.Int1
  %78 = struct $Int32 (%75 : $Builtin.Int32)
  %tif = function_ref @take_int32 : $@convention(thin) (Int32) -> ()
  %atif = apply %tif(%78) : $@convention(thin) (Int32) -> ()
// CHECK: br bb3
  br bb3(%49 : $Int32, %60 : $Int32, %78 : $Int32, %69 : $Int32)

// CHECK: bb6:
bb11:
  %80 = struct_extract %15 : $Int32, #Int32._value
  %81 = integer_literal $Builtin.Int32, 1
  %83 = integer_literal $Builtin.Int1, -1
  %84 = builtin "sadd_with_overflow_Int32"(%80 : $Builtin.Int32, %81 : $Builtin.Int32, %83 : $Builtin.Int1) : $(Builtin.Int32, Builtin.Int1)
  %85 = tuple_extract %84 : $(Builtin.Int32, Builtin.Int1), 0
  %86 = tuple_extract %84 : $(Builtin.Int32, Builtin.Int1), 1
  cond_fail %86 : $Builtin.Int1
  %88 = struct $Int32 (%85 : $Builtin.Int32)
// CHECK: br bb1
  br bb1(%28 : $Int32, %29 : $Int32, %88 : $Int32, %30 : $Int32, %31 : $Int32)

// CHECK: bb7:
bb12:
  %90 = tuple ()
// CHECK: return
  return %90 : $()
}
// CHECK-LABEL: } // end sil function 'test_dce_bbargs'

sil [ossa] @take_int32 : $@convention(thin) (Int32) -> ()

// CHECK-LABEL: sil [ossa] @remove_fix_lifetime :
// CHECK: bb0:
// CHECK-NEXT: tuple
// CHECK-NEXT: return
// CHECK-LABEL: } // end sil function 'remove_fix_lifetime'
sil [ossa] @remove_fix_lifetime : $@convention(thin) () -> () {
bb0:
  %0 = integer_literal $Builtin.Int32, 0
  %1 = struct $Int32 (%0 : $Builtin.Int32)

  fix_lifetime %1 : $Int32
  fix_lifetime %1 : $Int32

  %90 = tuple ()
  return %90 : $()
}

// CHECK-LABEL: sil [ossa] @dont_remove_fix_lifetime :
// CHECK: fix_lifetime
// CHECK: fix_lifetime
// CHECK: return
// CHECK-LABEL: } // end sil function 'dont_remove_fix_lifetime'
sil [ossa] @dont_remove_fix_lifetime : $@convention(thin) () -> Int32 {
bb0:
  %0 = integer_literal $Builtin.Int32, 0
  %1 = struct $Int32 (%0 : $Builtin.Int32)

  fix_lifetime %1 : $Int32
  fix_lifetime %1 : $Int32

  return %1 : $Int32
}

struct Container {
	var i: Int32
}

// CHECK-LABEL: sil [ossa] @dont_remove_addr_fix_lifetime :
// CHECK: fix_lifetime
// CHECK: fix_lifetime
// CHECK: return
// CHECK-LABEL: } // end sil function 'dont_remove_addr_fix_lifetime'
sil [ossa] @dont_remove_addr_fix_lifetime : $@convention(thin) (@in Container) -> () {
bb0(%0 : $*Container):
  %1 = struct_element_addr %0 : $*Container, #Container.i

  fix_lifetime %1 : $*Int32
  fix_lifetime %1 : $*Int32

  %90 = tuple ()
  return %90 : $()
}

// Check that DCE does not crash with an infinite loop through a cond_br.
// CHECK-LABEL: sil [ossa] @deal_with_infinite_loop :
// CHECK: cond_br
// CHECK-LABEL: } // end sil function 'deal_with_infinite_loop'
sil [ossa] @deal_with_infinite_loop : $@convention(thin) () -> () {
bb0:
  br bb1

bb1:
  cond_br undef, bb2, bb3

bb2:
  br bb1

bb3:
  br bb1
}

// Check that DCE eliminates dead access instructions.
// CHECK-LABEL: sil [ossa] @dead_access :
// CHECK: bb0
// CHECK-NEXT: tuple
// CHECK-NEXT: return
// CHECK-LABEL: } // end sil function 'dead_access'
sil [ossa] @dead_access : $@convention(thin) (@in Container) -> () {
bb0(%0 : $*Container):
  %1 = begin_access [modify] [dynamic] %0 : $*Container
  end_access %1 : $*Container

  %3 = begin_access [read] [static] %0 : $*Container
  end_access %3 : $*Container

  %999 = tuple ()
  return %999 : $()
}

// CHECK-LABEL: sil [ossa] @nested_destructure_tuple :
// CHECK:      bb0(%0 : @owned $(String, (Int, Int, String))):
// CHECK-NEXT:   (%1, %2) = destructure_tuple %0 : $(String, (Int, Int, String))
// CHECK-NEXT:   destroy_value %2
// CHECK-NEXT:   return %1
// CHECK:      } // end sil function 'nested_destructure_tuple'
sil [ossa] @nested_destructure_tuple : $@convention(thin) (@owned (String, (Int, Int, String))) -> @owned String {
bb0(%0 : @owned $(String, (Int, Int, String))):
  (%1, %2) = destructure_tuple %0 : $(String, (Int, Int, String))
  (%3, %4, %5) = destructure_tuple %2 : $(Int, Int, String)
  destroy_value %5 : $String
  return %1 : $String
}

// Test fix_lifetime of a struct and tuple. It cannot be removed
// without proving reference uniqueness first.
// rdar://36038096
// https://github.com/apple/swift/issues/49158
//
// CHECK-LABEL: @testFixLifetimeTuple : $@convention(thin) (@owned S, @owned AnyObject) -> () {
// CHECK: bb0(%0 : $S, %1 : $AnyObject):
// CHECK:   [[TUPLE:%.*]] = tuple (%0 : $S, %1 : $AnyObject)
// CHECK:   apply
// CHECK:   fix_lifetime [[TUPLE]] : $(S, AnyObject)
// CHECK:   strong_release %1 : $AnyObject
// CHECK:   strong_release %{{.*}} : $AnyObject
// CHECK-LABEL: } // end sil function 'testFixLifetimeTuple'
sil @testFixLifetimeTuple : $@convention(thin) (@owned S, @owned AnyObject) -> () {
bb0(%0 : $S, %1 : $AnyObject):
  %4 = struct_extract %0 : $S, #S.o
  %7 = tuple (%0 : $S, %1 : $AnyObject)
  %8 = function_ref @dummy : $@convention(thin) () -> ()
  %9 = apply %8() : $@convention(thin) () -> ()
  fix_lifetime %7 : $(S, AnyObject)
  strong_release %1 : $AnyObject
  strong_release %4 : $AnyObject
  %15 = tuple ()
  return %15 : $()
}

// Test fix_lifetime of a load_borrow. It cannot be removed without
// proving reference uniqueness first.
// rdar://74759728 (The compiler/optimizer seems to be shortening the lifetime too early)
//
// Test case derived from $defer #1 <A><A1>() in _ArrayBuffer.withUnsafeBufferPointer<A>(_:)
//
// Original source that exposed the issue with -Ounchecked -sanitize=address:
//
// public func makeRawData(name: String) -> UnsafeMutableRawPointer {
//   var array: [UInt8] = []
//   array.append(contentsOf: name.utf8)
//   array.append(0)
//
//   let rawData = array.withUnsafeBytes { (buffer: UnsafeRawBufferPointer) -> UnsafeMutableRawPointer in
//     let rawData = malloc(Int(buffer.count))!
//     rawData.copyMemory(from: buffer.baseAddress!, byteCount: buffer.count)
//     return rawData
//   }
//   return rawData
// }
//
// CHECK-LABEL: sil [ossa] @testDCEFixLifetime : $@convention(thin) (@guaranteed S) -> () {
// %0 "self"                                      // users: %3, %1
// CHECK: bb0(%0 : @guaranteed $S):
// CHECK:   [[LD:%.*]] = load_borrow
// CHECK:   fix_lifetime [[LD]] : $S
// CHECK:   end_borrow [[LD]] : $S
// CHECK-LABEL: } // end sil function 'testDCEFixLifetime'
sil [ossa] @testDCEFixLifetime : $@convention(thin) (@guaranteed S) -> () {
// %0 "self"
bb0(%0 : @guaranteed $S):
  debug_value %0 : $S, let, name "self", argno 1
  %2 = alloc_stack $S
  %3 = store_borrow %0 to %2 : $*S
  %4 = load_borrow %3 : $*S
  fix_lifetime %4 : $S
  end_borrow %4 : $S
  end_borrow %3 : $*S
  dealloc_stack %2 : $*S
  %8 = tuple ()
  return %8 : $()
}

// CHECK-LABEL: sil [ossa] @dce_destroy_of_live_copy : {{.*}} {
// CHECK:         [[COPY:%[^,]+]] = copy_value
// CHECK:         cond_br {{%[^,]+}}, [[LEFT:bb[0-9]+]], [[RIGHT:bb[0-9]+]]
// CHECK:       [[LEFT]]:
// CHECK:         destroy_value [[COPY]]
// CHECK:         br [[EXIT:bb[0-9]+]]
// CHECK:       [[RIGHT]]:
// CHECK:         destroy_value [[COPY]]
// CHECK:         br [[EXIT]]
// CHECK:       [[EXIT]]:
// CHECK-LABEL: } // end sil function 'dce_destroy_of_live_copy'
sil [ossa] @dce_destroy_of_live_copy : $@convention(thin) (Int1) -> () {
entry(%condition : $Int1):
  %instance = apply undef() : $@convention(thin) () -> (@owned C)
  %borrow = begin_borrow %instance : $C
  %aggregate = struct $CAndBit(%borrow : $C, %condition : $Int1)
  %copy = copy_value %aggregate : $CAndBit
  end_borrow %borrow : $C
  %borrow2 = begin_borrow %copy : $CAndBit
  %bit = struct_extract %borrow2 : $CAndBit, #CAndBit.bit
  end_borrow %borrow2 : $CAndBit
  apply undef(%bit) : $@convention(thin) (Int1) -> ()
  cond_br %condition, left, right
left:
  destroy_value %copy : $CAndBit
  br exit
right:
  destroy_value %copy : $CAndBit
  br exit
exit:
  destroy_value %instance : $C
  %retval = tuple ()
  return %retval : $()
}

// Test that DCE does not eliminate a drop_deinit.
//
// rdar://109863801 ([move-only] DCE removes drop_deinit, so
// user-defined deinitializers call themselves recursively at -O)
//
// CHECK-LABEL: sil hidden [ossa] @testDropDeinit : $@convention(method) (@owned MO) -> () {
// CHECK: [[DROP:%.*]] = drop_deinit %0 : $MO
// CHECK: end_lifetime [[DROP]] : $MO
// CHECK-LABEL: } // end sil function 'testDropDeinit'
//
// MO.deinit
sil hidden [ossa] @testDropDeinit : $@convention(method) (@owned MO) -> () {
bb0(%0 : @owned $MO):
  debug_value %0 : $MO, let, name "self", argno 1
  %61 = drop_deinit %0 : $MO
  end_lifetime %61 : $MO
  %63 = tuple ()
  return %63 : $()
}

// The InstructionDeleter will delete the `load [take]` and insert a
// `destroy_addr`.  Observe the creation of the new destroy_addr instruction
// that occurs when deleting the `load [take]` and mark it live.  Prevents a
// leak.
// CHECK-LABEL: sil [ossa] @keep_new_destroy_addr : {{.*}} {
// CHECK:         destroy_addr
// CHECK-LABEL: } // end sil function 'keep_new_destroy_addr'
sil [ossa] @keep_new_destroy_addr : $@convention(thin) () -> () {
bb0:
  try_apply undef() : $@convention(thin) () -> @error any Error, normal bb1, error bb5

bb1(%4 : $()):
  %err = alloc_stack $any Error
  try_apply undef<any Error>(%err) : $@convention(method) <τ_1_1 where τ_1_1 : Error> () -> (@error_indirect τ_1_1), normal bb2, error bb6

bb2(%15 : $()):
  dealloc_stack %err : $*any Error
  br bb3

bb4(%24 : @owned $any Error):
  destroy_value %24 : $any Error
  br bb3

bb5(%30 : @owned $any Error):
  br bb4(%30 : $any Error)

bb6:
  %33 = load [take] %err : $*any Error
  dealloc_stack %err : $*any Error
  br bb4(%33 : $any Error)

bb3:
  %22 = tuple ()
  return %22 : $()
}

// CHECK-LABEL: sil [ossa] @dont_delete_move_value_lexical : {{.*}} {
// CHECK:         [[LEXICAL:%[^,]+]] = move_value [lexical]
// CHECK:         [[DUMMY:%[^,]+]] = function_ref @dummy
// CHECK:         apply [[DUMMY]]()
// CHECK:         destroy_value [[LEXICAL]]
// CHECK-LABEL: } // end sil function 'dont_delete_move_value_lexical'
sil [ossa] @dont_delete_move_value_lexical : $@convention(thin) () -> () {
  %getC = function_ref @getC : $@convention(thin) () -> @owned C
  %c = apply %getC() : $@convention(thin) () -> @owned C
  %m = move_value [lexical] %c : $C
  %dummy = function_ref @dummy : $@convention(thin) () -> ()
  apply %dummy() : $@convention(thin) () -> ()
  destroy_value %m : $C
  %retval = tuple ()
  return %retval : $()
}