Files
swift-mirror/test/SILOptimizer/borrow_introducer_unit.sil
Erik Eckstein 0f0aa0c17b Optimizer: require that there are no unreachable blocks and infinite loops in OSSA
These two new invariants eliminate corner cases which caused bugs if optimization didn't handle them.
Also, it will significantly simplify lifetime completion.

The implementation basically consists of these changes:
* add a flag in SILFunction which tells optimization if they need to take care of infinite loops
* add a utility to break infinite loops
* let all optimizations remove unreachable blocks and break infinite loops if necessary
* add verification to check the new SIL invariants

The new `breakIfniniteLoops` utility breaks infinite loops in the control flow by inserting an "artificial" loop exit to a new dead-end block with an `unreachable`.
It inserts a `cond_br` with a `builtin "infinite_loop_true_condition"`:
```
bb0:
  br bb1
bb1:
  br bb1              // back-end branch
```
->
```
bb0:
  br bb1
bb1:
  %1 = builtin "infinite_loop_true_condition"() // always true, but the compiler doesn't know
  cond_br %1, bb2, bb3
bb2:                  // new back-end block
  br bb1
bb3:                  // new dead-end block
  unreachable
```
2026-01-22 17:41:23 +01:00

438 lines
17 KiB
Plaintext

// RUN: %target-sil-opt -sil-print-types -test-runner -sil-disable-input-verify %s -o /dev/null 2>&1 | %FileCheck %s
//
// REQUIRES: swift_in_compiler
sil_stage canonical
import Builtin
import Swift
struct Trivial {
var value: Builtin.Int32
}
enum FakeOptional<T> {
case none
case some(T)
}
struct PairC {
var first: C
var second: C
}
class C {
var field: C
}
class D : C {}
sil @coro : $@yield_once @convention(thin) () -> @yields @guaranteed C
// The introducer of an introducer is always itself.
// CHECK-LABEL: introducer_identity: find_borrow_introducers with: %0
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Introducers:
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_identity: find_borrow_introducers with: %0
// CHECK-LABEL: introducer_identity: borrow_introducers with: %0
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Borrow introducers for: %0 = argument of bb0 : $C
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_identity: borrow_introducers with: %0
// CHECK-LABEL: introducer_identity: find_borrow_introducers with: %borrow1
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Introducers:
// CHECK-NEXT: begin_borrow %0 : $C
// CHECK-NEXT: introducer_identity: find_borrow_introducers with: %borrow1
// CHECK-LABEL: introducer_identity: borrow_introducers with: %borrow1
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Borrow introducers for: %{{.*}} = begin_borrow %0 : $C
// CHECK-NEXT: begin_borrow %0 : $C
// CHECK-NEXT: introducer_identity: borrow_introducers with: %borrow1
// CHECK-LABEL: introducer_identity: find_borrow_introducers with: %borrow2
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Introducers:
// CHECK-NEXT: load_borrow %1 : $*C
// CHECK-NEXT: introducer_identity: find_borrow_introducers with: %borrow2
// CHECK-LABEL: introducer_identity: borrow_introducers with: %borrow2
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Borrow introducers for: {{.*}} = load_borrow %1 : $*C
// CHECK-NEXT: load_borrow %1 : $*C
// CHECK-NEXT: introducer_identity: borrow_introducers with: %borrow2
// CHECK-LABEL: introducer_identity: find_borrow_introducers with: %reborrow
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Introducers:
// CHECK-NEXT: argument of bb1 : $C
// CHECK-NEXT: introducer_identity: find_borrow_introducers with: %reborrow
// CHECK-LABEL: introducer_identity: borrow_introducers with: %reborrow
// CHECK: } // end sil function 'introducer_identity'
// CHECK: Borrow introducers for: %7 = borrowed %6 : $C from (%0 : $C)
// CHECK-NEXT: argument of bb1 : $C
// CHECK-NEXT: introducer_identity: borrow_introducers with: %reborrow
sil [ossa] @introducer_identity : $@convention(thin) (@guaranteed C, @in C) -> () {
entry(%0 : @guaranteed $C, %1 : $*C):
specify_test "find_borrow_introducers %0"
specify_test "borrow_introducers %0"
%borrow1 = begin_borrow %0 : $C
specify_test "find_borrow_introducers %borrow1"
specify_test "borrow_introducers %borrow1"
%borrow2 = load_borrow %1 : $*C
specify_test "find_borrow_introducers %borrow2"
specify_test "borrow_introducers %borrow2"
end_borrow %borrow2 : $C
br exit(%borrow1 : $C)
exit(%12 : @guaranteed $C):
%reborrow = borrowed %12 from (%0)
specify_test "find_borrow_introducers %reborrow"
specify_test "borrow_introducers %reborrow"
end_borrow %reborrow : $C
destroy_addr %1 : $*C
%retval = tuple ()
return %retval : $()
}
// There is no introducer if the guaranteed value is produced from a
// trivial value.
// CHECK-LABEL: introducer_trivial: find_borrow_introducers with: %phi
// CHECK: } // end sil function 'introducer_trivial'
// CHECK: Introducers:
// CHECK-NEXT: introducer_trivial: find_borrow_introducers with: %phi
// CHECK-LABEL: introducer_trivial: borrow_introducers with: %phi
// CHECK: } // end sil function 'introducer_trivial'
// CHECK: Borrow introducers for: %3 = borrowed %2 : $FakeOptional<C> from ()
// CHECK-NEXT: introducer_trivial: borrow_introducers with: %phi
sil [ossa] @introducer_trivial : $@convention(thin) () -> () {
entry:
%trivial = enum $FakeOptional<C>, #FakeOptional.none!enumelt
br none(%trivial : $FakeOptional<C>)
none(%2 : @guaranteed $FakeOptional<C>):
%phi = borrowed %2 from ()
specify_test "find_borrow_introducers %phi"
specify_test "borrow_introducers %phi"
%retval = tuple ()
return %retval : $()
}
// All data flow paths through phis and aggregates originate from the
// same function argument.
// CHECK-LABEL: introducer_single: find_borrow_introducers with: %aggregate2
// CHECK: } // end sil function 'introducer_single'
// CHECK: Introducers:
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_single: find_borrow_introducers with: %aggregate2
// CHECK-LABEL: introducer_single: borrow_introducers with: %aggregate2
// CHECK: } // end sil function 'introducer_single'
// CHECK: Borrow introducers for: %12 = struct $PairC (%10 : $C, %11 : $C)
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_single: borrow_introducers with: %aggregate2
sil [ossa] @introducer_single : $@convention(thin) (@guaranteed C) -> () {
entry(%0 : @guaranteed $C):
%cast = unconditional_checked_cast %0 : $C to D
%some = enum $FakeOptional<D>, #FakeOptional.some!enumelt, %cast : $D
br switch(%some : $FakeOptional<D>)
switch(%4 : @guaranteed $FakeOptional<D>):
%somePhi = borrowed %4 from (%0)
switch_enum %somePhi : $FakeOptional<D>, case #FakeOptional.some!enumelt: bb1, case #FakeOptional.none!enumelt: bb2
bb1(%payload : @guaranteed $D):
%upcast = upcast %payload : $D to $C
%aggregate = struct $PairC(%upcast : $C, %0 : $C)
%first = struct_extract %aggregate : $PairC, #PairC.first
%second = struct_extract %aggregate : $PairC, #PairC.second
%aggregate2 = struct $PairC(%first : $C, %second : $C)
specify_test "find_borrow_introducers %aggregate2"
specify_test "borrow_introducers %aggregate2"
br exit
bb2:
br exit
exit:
%retval = tuple ()
return %retval : $()
}
// %reborrow introduces multiple borrow scopes. But it should only appear
// in the list once.
// The forwarding %phi originates from %borrow1 and %0. But
// %borrow1 cannot be an introducer in bb2 because it's scope ends at
// %reborrow. Therefore, %reborrow is an introducer from separate phi
// paths, but should only appear in the introducer list once.
//
// CHECK-LABEL: introducer_revisit_reborrow: find_borrow_introducers with: %aggregate2
// CHECK: bb1([[REBORROW:%.*]] : @reborrow $C
// CHECK: } // end sil function 'introducer_revisit_reborrow'
// CHECK: Introducers:
// CHECK-NEXT: [[REBORROW]] = argument of bb1 : $C
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_revisit_reborrow: find_borrow_introducers with: %aggregate2
// CHECK-LABEL: introducer_revisit_reborrow: borrow_introducers with: %aggregate2
// CHECK: bb1([[REBORROW:%.*]] : @reborrow $C
// CHECK: } // end sil function 'introducer_revisit_reborrow'
// CHECK: Borrow introducers for: %{{.*}} = struct $PairC (%{{.*}} : $C, %{{.*}} : $C)
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: [[REBORROW]] = argument of bb1 : $C
// CHECK-NEXT: introducer_revisit_reborrow: borrow_introducers with: %aggregate2
sil [ossa] @introducer_revisit_reborrow : $@convention(thin) (@guaranteed C) -> () {
entry(%0 : @guaranteed $C):
%borrow1 = begin_borrow %0 : $C
%aggregate = struct $PairC(%0 : $C, %borrow1 : $C)
br bb2(%borrow1 : $C, %aggregate : $PairC)
bb2(%4 : @guaranteed $C, %5 : @guaranteed $PairC):
%phi = borrowed %5 from (%4, %0)
%reborrow = borrowed %4 from (%0)
%first = struct_extract %phi : $PairC, #PairC.first
%aggregate2 = struct $PairC(%reborrow : $C, %first : $C)
specify_test "find_borrow_introducers %aggregate2"
specify_test "borrow_introducers %aggregate2"
br exit
exit:
end_borrow %reborrow : $C
%retval = tuple ()
return %retval : $()
}
// %phi originates from %0, %borrow1, & %borrow2. %borrow1 is, however,
// reborrowed in bb2.
// CHECK-LABEL: introducer_multiple_borrow: find_borrow_introducers with: %aggregate2
// CHECK: begin_borrow %0 : $C
// CHECK: [[BORROW2:%.*]] = begin_borrow %0 : $C
// CHECK: bb1([[REBORROW:%.*]] : @reborrow $C
// CHECK: } // end sil function 'introducer_multiple_borrow'
// CHECK: Introducers:
// CHECK-NEXT: [[REBORROW]] = argument of bb1 : $C
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: [[BORROW2]] = begin_borrow %0 : $C
// CHECK-NEXT: introducer_multiple_borrow: find_borrow_introducers with: %aggregate2
// CHECK-LABEL: introducer_multiple_borrow: borrow_introducers with: %aggregate2
// CHECK: begin_borrow %0 : $C
// CHECK: [[BORROW2:%.*]] = begin_borrow %0 : $C
// CHECK: bb1([[REBORROW:%.*]] : @reborrow $C
// CHECK: } // end sil function 'introducer_multiple_borrow'
// CHECK: Borrow introducers for: %{{.*}} = struct $PairC (%{{.*}} : $C, %{{.*}} : $C)
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: [[BORROW2]] = begin_borrow %0 : $C
// CHECK-NEXT: [[REBORROW]] = argument of bb1 : $C
// CHECK-NEXT: introducer_multiple_borrow: borrow_introducers with: %aggregate2
sil [ossa] @introducer_multiple_borrow : $@convention(thin) (@guaranteed C) -> () {
entry(%0 : @guaranteed $C):
%borrow1 = begin_borrow %0 : $C
%borrow2 = begin_borrow %0 : $C
%aggregate = struct $PairC(%0 : $C, %borrow2 : $C)
br bb2(%borrow1 : $C, %aggregate : $PairC)
bb2(%5 : @guaranteed $C, %6 : @guaranteed $PairC):
%phi = borrowed %6 from (%borrow2, %0)
%reborrow = borrowed %5 from (%0)
%first = struct_extract %phi : $PairC, #PairC.first
%aggregate2 = struct $PairC(%reborrow : $C, %first : $C)
specify_test "find_borrow_introducers %aggregate2"
specify_test "borrow_introducers %aggregate2"
br exit
exit:
end_borrow %reborrow : $C
end_borrow %borrow2 : $C
%retval = tuple ()
return %retval : $()
}
// CHECK-LABEL: introducer_dependence: find_borrow_introducers with: %dependent
// CHECK: Introducers:
// CHECK: %0 = argument of bb0 : $C
// CHECK-LABEL: introducer_dependence: find_borrow_introducers with: %dependent
// CHECK-LABEL: introducer_dependence: borrow_introducers with: %dependent
// CHECK: Borrow introducers for: %{{.*}} = mark_dependence %0 : $C on %1 : $Builtin.NativeObject
// CHECK: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_dependence: borrow_introducers with: %dependent
sil [ossa] @introducer_dependence : $@convention(thin) (@guaranteed C, @guaranteed Builtin.NativeObject) -> () {
entry(%0 : @guaranteed $C, %1 : @guaranteed $Builtin.NativeObject):
specify_test "find_borrow_introducers %dependent"
specify_test "borrow_introducers %dependent"
%dependent = mark_dependence %0 : $C on %1 : $Builtin.NativeObject
%retval = tuple ()
return %retval : $()
}
// CHECK-LABEL: introducer_bridge: find_borrow_introducers with: %bridge
// CHECK: Introducers:
// CHECK: %0 = argument of bb0 : $C
// CHECK-LABEL: introducer_bridge: find_borrow_introducers with: %bridge
// CHECK-LABEL: introducer_bridge: borrow_introducers with: %bridge
// CHECK: Borrow introducers for: %{{.*}} = ref_to_bridge_object %0 : $C, %1 : $Builtin.Word
// CHECK: %0 = argument of bb0 : $C
// CHECK-NEXT: introducer_bridge: borrow_introducers with: %bridge
sil [ossa] @introducer_bridge : $@convention(thin) (@guaranteed C, Builtin.Word) -> () {
entry(%0 : @guaranteed $C, %1 : $Builtin.Word):
specify_test "find_borrow_introducers %bridge"
specify_test "borrow_introducers %bridge"
%bridge = ref_to_bridge_object %0 : $C, %1 : $Builtin.Word
%retval = tuple ()
return %retval : $()
}
// CHECK-LABEL: introducer_begin_apply: borrow_introducers with: %bridge
// CHECK: Borrow introducers for: %{{.*}} = ref_to_bridge_object %{{.*}} : $C, %0 : $Builtin.Word
// CHECK-NEXT: (**%{{.*}}**, %{{.*}}) = begin_apply %{{.*}}() : $@yield_once @convention(thin) () -> @yields @guaranteed C
// CHECK-NEXT: introducer_begin_apply: borrow_introducers with: %bridge
sil [ossa] @introducer_begin_apply : $@convention(thin) (Builtin.Word) -> () {
bb0(%0 : $Builtin.Word):
%f = function_ref @coro : $@yield_once @convention(thin) () -> @yields @guaranteed C
(%c, %t) = begin_apply %f() : $@yield_once @convention(thin) () -> @yields @guaranteed C
specify_test "borrow_introducers %bridge"
%bridge = ref_to_bridge_object %c : $C, %0 : $Builtin.Word
cond_br undef, bb1, bb2
bb1:
end_apply %t as $()
%r = tuple ()
return %r : $()
bb2:
abort_apply %t
unreachable
}
// CHECK-LABEL: introducer_example: borrow_introducers with: %borrow0
// CHECK: Borrow introducers for: %{{.*}} = begin_borrow %0 : $C
// CHECK-NEXT: %{{.*}} = begin_borrow %0 : $C
// CHECK-NEXT: introducer_example: borrow_introducers with: %borrow0
// CHECK-LABEL: introducer_example: borrow_introducers with: %first
// CHECK: Borrow introducers for: %{{.*}} = struct_extract %{{.*}} : $PairC, #PairC.first
// CHECK-NEXT: %{{.*}} = argument of bb0 : $C
// CHECK-NEXT: %{{.*}} = begin_borrow %0 : $C
// CHECK-NEXT: introducer_example: borrow_introducers with: %first
// CHECK-LABEL: introducer_example: borrow_introducers with: %load
// CHECK-LABEL: Borrow introducers for: %{{.*}} = load_borrow %{{.*}} : $*C
// CHECK-NEXT: %{{.*}} = load_borrow %{{.*}} : $*C
// CHECK-NEXT: introducer_example: borrow_introducers with: %
sil [ossa] @introducer_example : $@convention(thin) (@owned C, @guaranteed C) -> () {
bb0(%0 : @owned $C,
%1 : @guaranteed $C):
%borrow0 = begin_borrow %0 : $C
specify_test "borrow_introducers %borrow0"
%pair = struct $PairC(%borrow0 : $C, %1 : $C)
%first = struct_extract %pair : $PairC, #PairC.first
specify_test "borrow_introducers %first"
%field = ref_element_addr %first : $C, #C.field
%load = load_borrow %field : $*C
specify_test "borrow_introducers %load"
end_borrow %load : $C
end_borrow %borrow0 : $C
destroy_value %0 : $C
%retval = tuple ()
return %retval : $()
}
// CHECK-LABEL: testSelfIntroducer: borrow_introducers with: %phi
// CHECK: Borrow introducers for: %6 = borrowed %5 : $D from (%4 : $C)
// CHECK-NEXT: %{{.*}} = argument of bb1 : $C
// CHECK-NEXT: testSelfIntroducer: borrow_introducers with: %phi
// CHECK-LABEL: testSelfIntroducer: enclosing_values with: %reborrow
// CHECK: Enclosing values for: %7 = borrowed %4 : $C from (%0 : $C)
// CHECK-NEXT: %0 = argument of bb0 : $C
// CHECK-NEXT: testSelfIntroducer: enclosing_values with: %reborrow
sil [ossa] @testSelfIntroducer : $@convention(thin) (@guaranteed C) -> () {
bb0(%0 : @guaranteed $C):
%borrow = begin_borrow %0 : $C
%d = unconditional_checked_cast %borrow : $C to D
br bb1(%borrow : $C, %d : $D)
bb1(%4 : @guaranteed $C, %5 : @guaranteed $D):
%phi = borrowed %5 from (%4)
%reborrow = borrowed %4 from (%0)
specify_test "borrow_introducers %phi"
specify_test "enclosing_values %reborrow"
cond_br undef, bb2, bb3
bb2:
br bb1(%reborrow : $C, %phi : $D)
bb3:
end_borrow %reborrow : $C
%99 = tuple()
return %99 : $()
}
// Test the reborrow cache in EnclosingValues. Here, %reborrow must be
// visited once on each path, and each time the recursive algorithm
// must find the enclosing def %0, which maps to a %outer0 on one path
// and %outer1 on another path. If the cache fails, then we only find
// one of the outer adjacent phis as an enclosing value for %inner.
//
// CHECK-LABEL: testEnclosingRevisitReborrow: enclosing_values with: %inner
// CHECK: Enclosing values for: %12 = borrowed %11 : $C from (%10 : $C, %9 : $C)
// CHECK-NEXT: %{{.*}} = argument of bb4 : $C
// CHECK-NEXT: %{{.*}} = argument of bb4 : $C
// CHECK-NEXT: end running test 1 of 1 on testEnclosingRevisitReborrow: enclosing_values with: %inner
sil [ossa] @testEnclosingRevisitReborrow : $@convention(thin) (@owned C, @owned C) -> () {
bb0(%0 : @owned $C, %1 : @owned $C):
%borrow = begin_borrow %0 : $C
br bb1(%borrow : $C)
bb1(%4 : @guaranteed $C):
%reborrow = borrowed %4 from (%0)
cond_br undef, bb2, bb3
bb2:
br bb4(%0 : $C, %1 : $C, %reborrow : $C)
bb3:
br bb4(%1 : $C, %0 : $C, %reborrow : $C)
bb4(%outer0 : @owned $C, %outer1 : @owned $C, %11 : @guaranteed $C):
%inner = borrowed %11 from (%outer1, %outer0)
specify_test "enclosing_values %inner"
end_borrow %inner : $C
destroy_value %outer0 : $C
destroy_value %outer1 : $C
%99 = tuple()
return %99 : $()
}
// CHECK-LABEL: Borrow introducers for: %3 = unchecked_ownership_conversion %2
// CHECK-NEXT: %3 = unchecked_ownership_conversion %2
// CHECK-NEXT: end running test 1 of 2 on testUncheckedOwnershipConversion: borrow_introducers with: %3
// CHECK-LABEL: Enclosing values for: %3 = unchecked_ownership_conversion %2
// CHECK-NEXT: end running test 2 of 2 on testUncheckedOwnershipConversion: enclosing_values with: %3
sil [ossa] @testUncheckedOwnershipConversion : $@convention(thin) (Unmanaged<C>) -> () {
bb0(%0 : $Unmanaged<C>):
%1 = struct_extract %0, #Unmanaged._value
%2 = unmanaged_to_ref %1 to $C
%3 = unchecked_ownership_conversion %2, @unowned to @guaranteed
specify_test "borrow_introducers %3"
specify_test "enclosing_values %3"
end_borrow %3
%8 = tuple ()
return %8
}