[SR-12805] Overflow checks not eliminated in simple loop

[karwa]

Previous ID	SR-12805
Radar	None
Original Reporter	@karwa
Type	Bug

Environment

Swift version 5.3-dev (LLVM 4a0dfa0, Swift eaa1051)

Additional Detail from JIRA

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

md5: adf743091ada51cb01f5ef12b82ccd74

Issue Description:

Test case:

func containsFortyTwo(_ input: UnsafeBufferPointer<UInt8>) -> Bool {
    var idx = input.startIndex
    while idx != input.endIndex {        
        if input[idx] == 42 { return false }
        idx = input.index(after: idx)
    }
    return true
}

Results in overflow checks:

output.containsFortyTwo(Swift.UnsafeBufferPointer<Swift.UInt8>) -> Swift.Bool:
        push    rbp
        mov     rbp, rsp
        mov     al, 1
        test    rsi, rsi
        je      .LBB1_7
        cmp     byte ptr [rdi], 42
        je      .LBB1_6
        xor     ecx, ecx
.LBB1_3:
        mov     rdx, rcx
        inc     rdx
        jo      .LBB1_8          ; <------- Here
        cmp     rdx, rsi
        je      .LBB1_7
        add     rcx, 1
        cmp     byte ptr [rdi + rdx], 42
        jne     .LBB1_3
.LBB1_6:
        xor     eax, eax
.LBB1_7:
        pop     rbp
        ret
.LBB1_8:
        ud2

Now, in practice, the only way this code could possibly overflow is if UnsafeBufferPointer<T>.count were negative (i.e. endIndex < startIndex, which violates the Collection protocol semantics but is nonetheless possible to write).

Fortunately, UBP validates its count in all initialisers, which is the only time it is set (or it copies the count of something which is known to also validate its count), so this situation will never happen. Unfortunately, the compiler doesn't know this, and must assume that a value of type `Int` may be negative.

The result is that we pay in code size and runtime performance, and there is no way to eliminate it (other than -Ounchecked, which is not practical; it is not possible on a per-file basis in SwiftPM projects, for instance).

Could we perhaps add some kind of attribute or property wrapper which validates that a value of type "Int" is never negative? The compiler could then use that knowledge to treat the value as effectively unsigned and eliminate the above overflow check. Alternatively (at least for the unsafe pointers), it seems reasonable to add a version of "index(after🙂" which uses wrapping arithmetic.

[karwa]

FWIW, I've actually found a suuuuuuper-hacky way to eliminate this check:

@inline(__always)
public func unreachable() -> Never {
    return unsafeBitCast((), to: Never.self)
}

func containsFortyTwo(_ input: UnsafeBufferPointer<UInt8>) -> Bool {
    var idx = input.startIndex
    while idx != input.endIndex {        
        if input[idx] == 42 { return false }
        if idx == .max { unreachable() }      // <-- This.
        idx = input.index(after: idx)        
    }
    return true
}

It actually makes some amount of sense - "idx" cannot be Int.max at that point, given that we just subscripted from it (and if Int.max were a valid index for any Collection, what would that Collection's endIndex be?). I tried to use similar tricks to hint to the compiler that endIndex > startIndex (i.e. that we can increment from startIndex, checking that we != endIndex on every iteration, and we will never overflow), but it didn't seem to pick that up.

Obviously this is super-suspicious-looking, and I wouldn't dare ship this. We've added a "no traps" promise, but at the cost of riskier-looking code. This was just an exercise to investigate what kind of additional knowledge the compiler might need to eliminate this by itself.

output.containsFortyTwo(Swift.UnsafeBufferPointer<Swift.UInt8>) -> Swift.Bool:
        push    rbp
        mov     rbp, rsp
        mov     al, 1
        test    rsi, rsi
        je      .LBB2_7
        cmp     byte ptr [rdi], 42
        je      .LBB2_2
        cmp     rsi, 1
        je      .LBB2_7
        add     rsi, -1
        xor     ecx, ecx
.LBB2_5:
        cmp     byte ptr [rdi + rcx + 1], 42
        je      .LBB2_2
        add     rcx, 1        ; Wooo!
        cmp     rsi, rcx
        jne     .LBB2_5
.LBB2_7:
        pop     rbp
        ret
.LBB2_2:
        xor     eax, eax
        pop     rbp
        ret

; No traps!

https://godbolt.org/z/pJiQhG

[lorentey]

The standard library has `_unreachable(<condition>)` and `_conditionallyUnreachable` for this purpose – these are dangerous tools, but they might be appropriate for use in this case.

For these to not cause significant headaches, there must be no way (outside of -Ounchecked or manually manipulating memory) to create a buffer pointer with a negative count.