Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

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

Closed
stephentyrone opened this issue Sep 17, 2018 · 13 comments
Closed

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

stephentyrone opened this issue Sep 17, 2018 · 13 comments
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself performance regression standard library Area: Standard library umbrella swift 5.0

Comments

@stephentyrone
Copy link
Member

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
Copy link
Member Author

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

@airspeedswift
Copy link
Member

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
Copy link
Member Author

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

@airspeedswift
Copy link
Member

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

@stephentyrone
Copy link
Member Author

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
Copy link
Member

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
Copy link
Member Author

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
Copy link
Contributor

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
Copy link
Member Author

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

@airspeedswift
Copy link
Member

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

@airspeedswift
Copy link
Member

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

@stephentyrone
Copy link
Member Author

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
Copy link
Member Author

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

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug A deviation from expected or documented behavior. Also: expected but undesirable behavior. compiler The Swift compiler in itself performance regression standard library Area: Standard library umbrella swift 5.0
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
4 participants
@stephentyrone @belkadan @airspeedswift @AnthonyLatsis