[Raised in error] Understanding array bounds checking optimisation

carlos42421 · June 20, 2024, 6:01pm

I'm trying to understand (and debug) the optimisation of array subscript bounds checking.

I'm building this code...

import AVR

var array3: [StaticString] = ["first time","lucky"]

print(array3[1 as Int])
print(array3[0 as Int])
print(array3[9 as Int])

And I'm expecting to see an array bounds check fail on the last call and trap, but it looked like the bounds check wasn't happening, it had been optimised away. I couldn't see any sign of the check in canonical SIL. I tried running the compiler debugged with lldb and putting a breakpoint on ArraySemantic.cpp line 535 void swift::ArraySemanticsCall::removeCall() as it looked like that was probably the place that might be called by the optimiser to remove this call. But the breakpoint was never hit.

Can anyone give some advice on how/where to debug this optimisation? I'm trying to work out why it's going wrong on my platform.

Thanks!
Carl

kubamracek · June 22, 2024, 1:46am

When you say you that the bounds check isn't present, what are you seeing instead? In your example...

var array3: [StaticString] = ["first time","lucky"]
print(array3[1 as Int])
print(array3[0 as Int])
print(array3[9 as Int])

...the last line is always an out-of-bounds access into the array, so I would expect it to get turned into an unconditional trap (and yes, without a bounds check).

carlos42421 · June 22, 2024, 11:28am

I would expect exactly what you said.

What I'm seeing instead is the checks all being removed and an out of bounds memory access done on the last array access, beyond the bounds of the array, a buffer overrun.

This is the RAW SIL (with some attempt to cut out irrelevant bits)...

sil_stage raw

import Builtin
import Swift
import SwiftShims

import AVR

@_hasStorage @_hasInitialValue var array3: [StaticString] { get set }

// array3
sil_global hidden @$s4main6array3Says12StaticStringVGvp : $Array<StaticString>

// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s4main6array3Says12StaticStringVGvp // id: %2
  %3 = global_addr @$s4main6array3Says12StaticStringVGvp : $*Array<StaticString> // users: %62, %47, %32, %27
  %4 = integer_literal $Builtin.Word, 2           // user: %6
  // function_ref _allocateUninitializedArray<A>(_:)
  %5 = function_ref @$ss27_allocateUninitializedArrayySayxG_BptBwlF : $@convention(thin) <τ_0_0> (Builtin.Word) -> (@owned Array<τ_0_0>, Builtin.RawPointer) // user: %6
  %6 = apply %5<StaticString>(%4) : $@convention(thin) <τ_0_0> (Builtin.Word) -> (@owned Array<τ_0_0>, Builtin.RawPointer) // user: %7
  (%7, %8) = destructure_tuple %6 : $(Array<StaticString>, Builtin.RawPointer) // users: %27, %9, %9
  %9 = mark_dependence %8 : $Builtin.RawPointer on %7 : $Array<StaticString> // user: %10
  %10 = pointer_to_address %9 : $Builtin.RawPointer to [strict] $*StaticString // users: %19, %17
  %11 = string_literal utf8 "first time"          // user: %16
  %12 = integer_literal $Builtin.Word, 10         // user: %16
  %13 = integer_literal $Builtin.Int1, -1         // user: %16
  %14 = metatype $@thin StaticString.Type         // user: %16
  // function_ref StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)
  %15 = function_ref @$ss12StaticStringV08_builtinB7Literal17utf8CodeUnitCount7isASCIIABBp_BwBi1_tcfC : $@convention(method) (Builtin.RawPointer, Builtin.Word, Builtin.Int1, @thin StaticString.Type) -> StaticString // user: %16
  %16 = apply %15(%11, %12, %13, %14) : $@convention(method) (Builtin.RawPointer, Builtin.Word, Builtin.Int1, @thin StaticString.Type) -> StaticString // user: %17
  store %16 to [trivial] %10 : $*StaticString     // id: %17
  %18 = integer_literal $Builtin.Word, 1          // user: %19
  %19 = index_addr %10 : $*StaticString, %18 : $Builtin.Word // user: %26
  %20 = string_literal utf8 "lucky"               // user: %25
  %21 = integer_literal $Builtin.Word, 5          // user: %25
  %22 = integer_literal $Builtin.Int1, -1         // user: %25
  %23 = metatype $@thin StaticString.Type         // user: %25
  // function_ref StaticString.init(_builtinStringLiteral:utf8CodeUnitCount:isASCII:)
  %24 = function_ref @$ss12StaticStringV08_builtinB7Literal17utf8CodeUnitCount7isASCIIABBp_BwBi1_tcfC : $@convention(method) (Builtin.RawPointer, Builtin.Word, Builtin.Int1, @thin StaticString.Type) -> StaticString // user: %25
  %25 = apply %24(%20, %21, %22, %23) : $@convention(method) (Builtin.RawPointer, Builtin.Word, Builtin.Int1, @thin StaticString.Type) -> StaticString // user: %26
  store %25 to [trivial] %19 : $*StaticString     // id: %26
  store %7 to [init] %3 : $*Array<StaticString>   // id: %27
  %28 = integer_literal $Builtin.IntLiteral, 1    // user: %31
  %29 = metatype $@thin Int.Type                  // user: %31
  // function_ref Int.init(_builtinIntegerLiteral:)
  %30 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %31
  %31 = apply %30(%28, %29) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %35
  %32 = load_borrow %3 : $*Array<StaticString>    // users: %37, %35
  %33 = alloc_stack $StaticString                 // users: %42, %36, %35
  // function_ref Array.subscript.getter
  %34 = function_ref @$sSayxSicig : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0 // user: %35
  %35 = apply %34<StaticString>(%33, %31, %32) : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0
  %36 = load [trivial] %33 : $*StaticString       // user: %41
  end_borrow %32 : $Array<StaticString>           // id: %37
  // function_ref default argument 1 of print(_:addNewline:)
  %38 = function_ref @$s3AVR5print_10addNewlineys12StaticStringV_SbtFfA0_ : $@convention(thin) () -> Bool // user: %39
  %39 = apply %38() : $@convention(thin) () -> Bool // user: %41
  // function_ref print(_:addNewline:)
  %40 = function_ref @$s3AVR5print_10addNewlineys12StaticStringV_SbtF : $@convention(thin) (StaticString, Bool) -> () // user: %41
  %41 = apply %40(%36, %39) : $@convention(thin) (StaticString, Bool) -> ()
  dealloc_stack %33 : $*StaticString              // id: %42
  %43 = integer_literal $Builtin.IntLiteral, 0    // user: %46
  %44 = metatype $@thin Int.Type                  // user: %46
  // function_ref Int.init(_builtinIntegerLiteral:)
  %45 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %46
  %46 = apply %45(%43, %44) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %50
  %47 = load_borrow %3 : $*Array<StaticString>    // users: %52, %50
  %48 = alloc_stack $StaticString                 // users: %57, %51, %50
  // function_ref Array.subscript.getter
  %49 = function_ref @$sSayxSicig : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0 // user: %50
  %50 = apply %49<StaticString>(%48, %46, %47) : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0
  %51 = load [trivial] %48 : $*StaticString       // user: %56
  end_borrow %47 : $Array<StaticString>           // id: %52
  // function_ref default argument 1 of print(_:addNewline:)
  %53 = function_ref @$s3AVR5print_10addNewlineys12StaticStringV_SbtFfA0_ : $@convention(thin) () -> Bool // user: %54
  %54 = apply %53() : $@convention(thin) () -> Bool // user: %56
  // function_ref print(_:addNewline:)
  %55 = function_ref @$s3AVR5print_10addNewlineys12StaticStringV_SbtF : $@convention(thin) (StaticString, Bool) -> () // user: %56
  %56 = apply %55(%51, %54) : $@convention(thin) (StaticString, Bool) -> ()
  dealloc_stack %48 : $*StaticString              // id: %57
  %58 = integer_literal $Builtin.IntLiteral, 9    // user: %61
  %59 = metatype $@thin Int.Type                  // user: %61
  // function_ref Int.init(_builtinIntegerLiteral:)
  %60 = function_ref @$sSi22_builtinIntegerLiteralSiBI_tcfC : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %61
  %61 = apply %60(%58, %59) : $@convention(method) (Builtin.IntLiteral, @thin Int.Type) -> Int // user: %65
  %62 = load_borrow %3 : $*Array<StaticString>    // users: %67, %65
  %63 = alloc_stack $StaticString                 // users: %72, %66, %65
  // function_ref Array.subscript.getter
  %64 = function_ref @$sSayxSicig : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0 // user: %65
  %65 = apply %64<StaticString>(%63, %61, %62) : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0
  %66 = load [trivial] %63 : $*StaticString       // user: %71
  end_borrow %62 : $Array<StaticString>           // id: %67
  // function_ref default argument 1 of print(_:addNewline:)
  %68 = function_ref @$s3AVR5print_10addNewlineys12StaticStringV_SbtFfA0_ : $@convention(thin) () -> Bool // user: %69
  %69 = apply %68() : $@convention(thin) () -> Bool // user: %71
  // function_ref print(_:addNewline:)
  %70 = function_ref @$s3AVR5print_10addNewlineys12StaticStringV_SbtF : $@convention(thin) (StaticString, Bool) -> () // user: %71
  %71 = apply %70(%66, %69) : $@convention(thin) (StaticString, Bool) -> ()
  dealloc_stack %63 : $*StaticString              // id: %72
  %73 = integer_literal $Builtin.Int32, 0         // user: %74
  %74 = struct $Int32 (%73 : $Builtin.Int32)      // user: %75
  return %74 : $Int32                             // id: %75
} // end sil function 'main'


// Array.subscript.getter
sil [serialized] @$sSayxSicig : $@convention(method) <τ_0_0> (Int, @guaranteed Array<τ_0_0>) -> @out τ_0_0



// Mappings from '#fileID' to '#filePath':
//   'main/main.swift' => 'main.swift'


Emitted build/main.sil

...this is the canonical SIL (again some attempts to remove irrelevant bits...

sil_stage canonical

import Builtin
import Swift
import SwiftShims

import AVR

@_hasStorage @_hasInitialValue var array3: [StaticString] { get set }

// array3
sil_global [serialized] @$s4main6array3Says12StaticStringVGvp : $Array<StaticString>



// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
[%1: noescape **]
[global: read,write,copy,destroy,allocate,deinit_barrier]
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s4main6array3Says12StaticStringVGvp // id: %2
  %3 = global_addr @$s4main6array3Says12StaticStringVGvp : $*Array<StaticString> // users: %46, %34
  %4 = integer_literal $Builtin.Word, 2           // user: %7
  %5 = integer_literal $Builtin.Int16, 2          // user: %6
  %6 = struct $Int (%5 : $Builtin.Int16)          // user: %12
  %7 = alloc_ref [tail_elems $StaticString * %4 : $Builtin.Word] $_ContiguousArrayStorage<StaticString> // user: %8
  %8 = upcast %7 : $_ContiguousArrayStorage<StaticString> to $__ContiguousArrayStorageBase // users: %17, %14, %9
  %9 = struct $_ContiguousArrayBuffer<StaticString> (%8 : $__ContiguousArrayStorageBase) // user: %16
  %10 = integer_literal $Builtin.Int16, 4         // user: %11
  %11 = struct $UInt (%10 : $Builtin.Int16)       // user: %12
  %12 = struct $_SwiftArrayBodyStorage (%6 : $Int, %11 : $UInt) // user: %13
  %13 = struct $_ArrayBody (%12 : $_SwiftArrayBodyStorage) // user: %15
  %14 = ref_element_addr %8 : $__ContiguousArrayStorageBase, #__ContiguousArrayStorageBase.countAndCapacity // user: %15
  store %13 to %14 : $*_ArrayBody                 // id: %15
  %16 = struct $Array<StaticString> (%9 : $_ContiguousArrayBuffer<StaticString>) // users: %19, %34
  %17 = ref_tail_addr %8 : $__ContiguousArrayStorageBase, $StaticString // users: %35, %18
  %18 = address_to_pointer %17 : $*StaticString to $Builtin.RawPointer // users: %61, %19
  %19 = mark_dependence %18 : $Builtin.RawPointer on %16 : $Array<StaticString> // user: %20
  %20 = pointer_to_address %19 : $Builtin.RawPointer to [strict] $*StaticString // users: %26, %28
  %21 = string_literal utf8 "first time"          // user: %23
  %22 = integer_literal $Builtin.Word, 10         // user: %25
  %23 = builtin "ptrtoint_Word"(%21 : $Builtin.RawPointer) : $Builtin.Word // user: %25
  %24 = integer_literal $Builtin.Int8, 2          // users: %32, %25
  %25 = struct $StaticString (%23 : $Builtin.Word, %22 : $Builtin.Word, %24 : $Builtin.Int8) // user: %26
  store %25 to %20 : $*StaticString               // id: %26
  %27 = integer_literal $Builtin.Word, 1          // users: %35, %28
  %28 = index_addr %20 : $*StaticString, %27 : $Builtin.Word // user: %33
  %29 = string_literal utf8 "lucky"               // user: %31
  %30 = integer_literal $Builtin.Word, 5          // user: %32
  %31 = builtin "ptrtoint_Word"(%29 : $Builtin.RawPointer) : $Builtin.Word // user: %32
  %32 = struct $StaticString (%31 : $Builtin.Word, %30 : $Builtin.Word, %24 : $Builtin.Int8) // user: %33
  store %32 to %28 : $*StaticString               // id: %33
  store %16 to %3 : $*Array<StaticString>         // id: %34
  %35 = index_addr [stack_protection] %17 : $*StaticString, %27 : $Builtin.Word // user: %36
  %36 = address_to_pointer [stack_protection] %35 : $*StaticString to $Builtin.RawPointer // users: %62, %42, %37
  %37 = builtin "ptrtoint_Word"(%36 : $Builtin.RawPointer) : $Builtin.Word // user: %38
  %38 = builtin "truncOrBitCast_Word_Int16"(%37 : $Builtin.Word) : $Builtin.Int16 // users: %43, %40
  %39 = integer_literal $Builtin.Int16, 0         // users: %77, %83, %59, %64, %43, %40
  %40 = builtin "cmp_slt_Int16"(%38 : $Builtin.Int16, %39 : $Builtin.Int16) : $Builtin.Int1 // user: %41
  cond_br %40, bb1, bb2                           // id: %41

bb1:                                              // Preds: bb0
  br bb3(%36 : $Builtin.RawPointer)               // id: %42

bb2:                                              // Preds: bb0
  %43 = builtin "cmp_eq_Int16"(%38 : $Builtin.Int16, %39 : $Builtin.Int16) : $Builtin.Int1 // user: %44
  cond_br %43, bb4, bb5                           // id: %44

// %45                                            // user: %48
bb3(%45 : $Builtin.RawPointer):                   // Preds: bb5 bb4 bb1
  %46 = struct_element_addr %3 : $*Array<StaticString>, #Array._buffer // user: %47
  %47 = struct_element_addr %46 : $*_ContiguousArrayBuffer<StaticString>, #_ContiguousArrayBuffer._storage // users: %70, %54
  %48 = pointer_to_address %45 : $Builtin.RawPointer to [strict] $*StaticString // user: %49
  %49 = load %48 : $*StaticString                 // user: %53
  %50 = integer_literal $Builtin.Int1, -1         // user: %51
  %51 = struct $Bool (%50 : $Builtin.Int1)        // users: %88, %69, %53
  // function_ref print(staticString:addNewline:)
  %52 = function_ref @$s3AVR5print12staticString10addNewlineys06StaticD0V_SbtF : $@convention(thin) (StaticString, Bool) -> () // users: %88, %69, %53
  %53 = apply %52(%49, %51) : $@convention(thin) (StaticString, Bool) -> ()
  %54 = load %47 : $*__ContiguousArrayStorageBase // user: %55
  %55 = ref_tail_addr [immutable] %54 : $__ContiguousArrayStorageBase, $StaticString // users: %56, %79
  %56 = address_to_pointer [stack_protection] %55 : $*StaticString to $Builtin.RawPointer // users: %81, %63, %57
  %57 = builtin "ptrtoint_Word"(%56 : $Builtin.RawPointer) : $Builtin.Word // user: %58
  %58 = builtin "truncOrBitCast_Word_Int16"(%57 : $Builtin.Word) : $Builtin.Int16 // users: %64, %59
  %59 = builtin "cmp_slt_Int16"(%58 : $Builtin.Int16, %39 : $Builtin.Int16) : $Builtin.Int1 // user: %60
  cond_br %59, bb6, bb7                           // id: %60

bb4:                                              // Preds: bb2
  br bb3(%18 : $Builtin.RawPointer)               // id: %61

bb5:                                              // Preds: bb2
  br bb3(%36 : $Builtin.RawPointer)               // id: %62

bb6:                                              // Preds: bb3
  br bb8(%56 : $Builtin.RawPointer)               // id: %63

bb7:                                              // Preds: bb3
  %64 = builtin "cmp_eq_Int16"(%58 : $Builtin.Int16, %39 : $Builtin.Int16) : $Builtin.Int1 // user: %65
  cond_br %64, bb9, bb10                          // id: %65

// %66                                            // user: %67
bb8(%66 : $Builtin.RawPointer):                   // Preds: bb10 bb9 bb6
  %67 = pointer_to_address %66 : $Builtin.RawPointer to [strict] $*StaticString // user: %68
  %68 = load %67 : $*StaticString                 // user: %69
  %69 = apply %52(%68, %51) : $@convention(thin) (StaticString, Bool) -> ()
  %70 = load %47 : $*__ContiguousArrayStorageBase // user: %71
  %71 = ref_tail_addr [immutable] %70 : $__ContiguousArrayStorageBase, $StaticString // users: %73, %92
  %72 = integer_literal $Builtin.Word, 9          // user: %73
  %73 = index_addr [stack_protection] %71 : $*StaticString, %72 : $Builtin.Word // user: %74
  %74 = address_to_pointer [stack_protection] %73 : $*StaticString to $Builtin.RawPointer // users: %94, %82, %75
  %75 = builtin "ptrtoint_Word"(%74 : $Builtin.RawPointer) : $Builtin.Word // user: %76
  %76 = builtin "truncOrBitCast_Word_Int16"(%75 : $Builtin.Word) : $Builtin.Int16 // users: %83, %77
  %77 = builtin "cmp_slt_Int16"(%76 : $Builtin.Int16, %39 : $Builtin.Int16) : $Builtin.Int1 // user: %78
  cond_br %77, bb11, bb12                         // id: %78

bb9:                                              // Preds: bb7
  %79 = address_to_pointer %55 : $*StaticString to $Builtin.RawPointer // user: %80
  br bb8(%79 : $Builtin.RawPointer)               // id: %80

bb10:                                             // Preds: bb7
  br bb8(%56 : $Builtin.RawPointer)               // id: %81

bb11:                                             // Preds: bb8
  br bb13(%74 : $Builtin.RawPointer)              // id: %82

bb12:                                             // Preds: bb8
  %83 = builtin "cmp_eq_Int16"(%76 : $Builtin.Int16, %39 : $Builtin.Int16) : $Builtin.Int1 // user: %84
  cond_br %83, bb14, bb15                         // id: %84

// %85                                            // user: %86
bb13(%85 : $Builtin.RawPointer):                  // Preds: bb15 bb14 bb11
  %86 = pointer_to_address %85 : $Builtin.RawPointer to [strict] $*StaticString // user: %87
  %87 = load %86 : $*StaticString                 // user: %88
  %88 = apply %52(%87, %51) : $@convention(thin) (StaticString, Bool) -> ()
  %89 = integer_literal $Builtin.Int32, 0         // user: %90
  %90 = struct $Int32 (%89 : $Builtin.Int32)      // user: %91
  return %90 : $Int32                             // id: %91

bb14:                                             // Preds: bb12
  %92 = address_to_pointer %71 : $*StaticString to $Builtin.RawPointer // user: %93
  br bb13(%92 : $Builtin.RawPointer)              // id: %93

bb15:                                             // Preds: bb12
  br bb13(%74 : $Builtin.RawPointer)              // id: %94
} // end sil function 'main'


// _ContiguousArrayStorage._elementPointer.getter
sil public_external @$ss23_ContiguousArrayStorageC15_elementPointerSpyxGvg : $@convention(method) <Element> (@guaranteed _ContiguousArrayStorage<Element>) -> UnsafeMutablePointer<Element> {
[%0: noescape, escape c*.v** => %r.s0.v**]
[global: ]
// %0                                             // user: %1
bb0(%0 : $_ContiguousArrayStorage<Element>):
  %1 = ref_tail_addr %0 : $_ContiguousArrayStorage<Element>, $Element // user: %2
  %2 = address_to_pointer %1 : $*Element to $Builtin.RawPointer // user: %3
  %3 = struct $UnsafeMutablePointer<Element> (%2 : $Builtin.RawPointer) // user: %4
  return %3 : $UnsafeMutablePointer<Element>      // id: %4
} // end sil function '$ss23_ContiguousArrayStorageC15_elementPointerSpyxGvg'

...I just noticed an issue with my code that I'm going to correct and re-try the above, just to check.

Carl

carlos42421 · June 22, 2024, 11:44am

Ha. Ignore me. I had somehow commented out the body of internal func _precondition in my standard library.

So I guess the array checking existed and was all inline, optimised, with constant propagation, dead code elimination, etc.

Excellent. I'll change the title to reflect it's my mistake!

Carl