[SR-8773] Regression in codegen for bounds-check-avoiding subscript?

[stephentyrone]

Previous ID	SR-8773
Radar	None
Original Reporter	@stephentyrone
Type	Bug
Status	Closed
Resolution	Invalid

Additional Detail from JIRA

Votes	0
Component/s	Compiler, Standard Library
Labels	Bug, 5.0Regression, Performance
Assignee	None
Priority	Medium

md5: 1047d6cb8df254319d55fdb596cba74c

Issue Description:

@jepers asked a question about avoiding bounds checks in array subscripts: https://forums.swift.org/t/subscript-array-without-bounds-check/16222

His proposed solution .withUnsafeBufferPointer{ $0[i] } works on 4.1.2, but falls over rather dramatically on master. If this is not a deliberate semantic change, it appears to be a pretty severe optimization regression.

[stephentyrone]

@airspeedswift Did the semantics of this change in 4.2 / 5.0?

[airspeedswift]

I'm not seeing a problem on master myself, what were you seeing?

This code should behave as follows and seems to from my recent master build:

let a = [1,2,3]}}
// works in both -O and -Onone
a.withUnsafeBufferPointer { print($0[0]) } 
// traps in -Onone, accesses uninitialized memory in -O
a.withUnsafeBufferPointer { print($0[3]) }

[stephentyrone]

The problem I'm seeing is that we went from a single instruction to about 50.

[airspeedswift]

Ah. Hmm. @atrick or @eeckstein might know if that's related to pinning removal.

[stephentyrone]

Here's the codegen with -O on master:

_$S5array3fooAA5indexSiSaySiG_SitF:
0000000000000010    pushq   %rbp
0000000000000011    movq    %rsp, %rbp
0000000000000014    movabsq $-0x3fffffffffffffff, %rax
000000000000001e    testq   %rax, %rdi
0000000000000021    jne 0x40
0000000000000023    movabsq $0x7f00000000000006, %rax
000000000000002d    testq   %rax, %rdi
0000000000000030    jne 0x75
0000000000000032    cmpq    $0x0, 0x10(%rdi)
0000000000000037    js  0xae
0000000000000039    movq    0x20(%rdi,%rsi,8), %rax
000000000000003e    popq    %rbp
000000000000003f    retq
0000000000000040    subq    $0x8, %rsp
0000000000000044    leaq    0xb5(%rip), %rax ## literal pool for: "/Volumes/Data/Checkouts/Swift/swift/stdlib/public/core/BridgeStorage.swift"
000000000000004b    leaq    0xfa(%rip), %rdi ## literal pool for: "Fatal error"
0000000000000052    leaq    0xf2(%rip), %rcx ## literal pool for: ""
0000000000000059    movl    $0xb, %esi
000000000000005e    movl    $0x2, %edx
0000000000000063    movl    $_main, %r8d
0000000000000069    movl    $0x2, %r9d
000000000000006f    pushq   $0x0
0000000000000071    pushq   $0x79
0000000000000073    jmp 0xa8
0000000000000075    subq    $0x8, %rsp
0000000000000079    leaq    0x80(%rip), %rax ## literal pool for: "/Volumes/Data/Checkouts/Swift/swift/stdlib/public/core/BridgeStorage.swift"
0000000000000080    leaq    0xc5(%rip), %rdi ## literal pool for: "Fatal error"
0000000000000087    leaq    0xbd(%rip), %rcx ## literal pool for: ""
000000000000008e    movl    $0xb, %esi
0000000000000093    movl    $0x2, %edx
0000000000000098    movl    $_main, %r8d
000000000000009e    movl    $0x2, %r9d
00000000000000a4    pushq   $0x0
00000000000000a6    pushq   $0x7a
00000000000000a8    pushq   $0x2
00000000000000aa    pushq   $0x4a
00000000000000ac    jmp 0xe8
00000000000000ae    subq    $0x8, %rsp
00000000000000b2    leaq    0xa7(%rip), %rax ## literal pool for: "/Volumes/Data/Checkouts/Swift/build/Ninja-RelWithDebInfoAssert/swift-macosx-x86_64/stdlib/public/core/8/IntegerTypes.swift"
00000000000000b9    leaq    0x8c(%rip), %rdi ## literal pool for: "Fatal error"
00000000000000c0    leaq    0x84(%rip), %rcx ## literal pool for: ""
00000000000000c7    movl    $0xb, %esi
00000000000000cc    movl    $0x2, %edx
00000000000000d1    movl    $_main, %r8d
00000000000000d7    movl    $0x2, %r9d
00000000000000dd    pushq   $0x0
00000000000000df    pushq   $0x4182
00000000000000e4    pushq   $0x2
00000000000000e6    pushq   $0x7a
00000000000000e8    pushq   %rax
00000000000000e9    callq   _$Ss18_fatalErrorMessage__4file4line5flagss5NeverOs12StaticStringV_A2HSus6UInt32VtF
00000000000000ee    addq    $0x30, %rsp
00000000000000f2    ud2

[airspeedswift]

That looks like it's still trapping then. I suspect this could be because _debugPrecondition went from being public to internal (while still being @_transparent)

[stephentyrone]

Here's the fast-path, isolated:

0000000000000014    movabsq $-0x3fffffffffffffff, %rax
000000000000001e    testq   %rax, %rdi
0000000000000021    jne 0x40
0000000000000023    movabsq $0x7f00000000000006, %rax
000000000000002d    testq   %rax, %rdi
0000000000000030    jne 0x75
0000000000000032    cmpq    $0x0, 0x10(%rdi)
0000000000000037    js  0xae
0000000000000039    movq    0x20(%rdi,%rsi,8), %rax

• checks if either of the high two bits or the low bit of array address is set.

• checks if bits 60:62 or 1:2 of array address is set (we should at least be able to fuse this with the previous test).

• tests if adding 16B to array pointer overflows(?!)

• dereferences array pointer + 8*index + 20B.

[belkadan]

Changing from public to internal shouldn't make a difference for an @_transparent function, but that doesn't mean we don't have a bug. This sounds like what we were talking about on Friday.

[stephentyrone]

This is another "we should have a test that verifies that we can compile this idiom down to single instruction" case.

[airspeedswift]

Looks like your master is an asserting build tho. Do you get the same results with a release-no-asserts compiler?

[airspeedswift]

Certainly doesn't look like we have good coverage of withUnsafe(Mutable)BufferPointer in the benchmarks.

[stephentyrone]

Ah, good point about release-no-asserts, I'll check that.

For things like this and .rounded( ), I think we should go beyond benchmarks and actually do validation of the generated assembly.

[stephentyrone]

Ok, so this looks fine with a non-asserts build, so there's at least no regression.