Missed optimization leading to inability to remove bounds check #49229

alex · 2021-04-07T21:11:52Z


Bugzilla Link	49885
Version	unspecified
OS	All
CC	@comex,@fhahn,@jrmuizel,@rotateright

Extended Description

(All content available as godbolt: https://godbolt.org/z/s6deqs71h)

Given the following code, llvm should be able to prove that the bounds checks within the loop are never necessary:

#include <cassert>
#include <cstdint>
#include <cstddef>
#include <vector>

uint64_t f(std::vector<uint64_t>& data, size_t start, size_t end){
    assert(start < end && start < data.size() && end <= data.size());

    uint64_t total = 0;
    for (size_t i = start; i < end; i++) {
        total += data.at(i);
    }
    return total;
}

However the following code is generated:

f(std::vector<unsigned long, std::allocator<unsigned long> >&, unsigned long, unsigned long):               # @&#8203;f(std::vector<unsigned long, std::allocator<unsigned long> >&, unsigned long, unsigned long)
        push    rax
        cmp     rsi, rdx
        jae     .LBB0_6
        mov     r9, qword ptr [rdi]
        mov     r10, qword ptr [rdi + 8]
        mov     rax, r10
        sub     rax, r9
        mov     r8, rax
        sar     r8, 3
        cmp     r8, rsi
        jbe     .LBB0_6
        cmp     r8, rdx
        jb      .LBB0_6
        test    rax, rax
        mov     rcx, -1
        cmovns  rcx, rax
        test    rcx, rcx
        mov     edi, 1
        cmovle  rdi, rcx
        mov     rcx, r9
        sub     rcx, r10
        cmp     rcx, rax
        cmovle  rcx, rax
        shr     rcx, 3
        imul    rcx, rdi
        cmp     rsi, rcx
        cmova   rcx, rsi
        xor     eax, eax
.LBB0_4:                                # =>This Inner Loop Header: Depth=1
        cmp     rcx, rsi
        je      .LBB0_5
        add     rax, qword ptr [r9 + 8*rsi]
        add     rsi, 1
        cmp     rdx, rsi
        jne     .LBB0_4
        pop     rcx
        ret
.LBB0_5:
        mov     edi, offset .L.str.2
        mov     rsi, rcx
        mov     rdx, r8
        xor     eax, eax
        call    std::__throw_out_of_range_fmt(char const*, ...)
.LBB0_6:
        mov     edi, offset .L.str
        mov     esi, offset .L.str.1
        mov     ecx, offset .L__PRETTY_FUNCTION__.f(std::vector<unsigned long, std::allocator<unsigned long> >&, unsigned long, unsigned long)
        mov     edx, 7
        call    __assert_fail
.L.str:
        .asciz  "start < end && start < data.size() && end <= data.size()"

.L.str.1:
        .asciz  "/app/example.cpp"

.L__PRETTY_FUNCTION__.f(std::vector<unsigned long, std::allocator<unsigned long> >&, unsigned long, unsigned long):
        .asciz  "uint64_t f(std::vector<uint64_t> &, size_t, size_t)"

.L.str.2:
        .asciz  "vector::_M_range_check: __n (which is %zu) >= this->size() (which is %zu)"

The throw_out_of_range exception code should be able to be optimized out.

jrmuizel · 2021-04-08T01:24:30Z

Add -mllvm -enable-constraint-elimination seems to eliminate the bounds check:
https://godbolt.org/z/EM7ra6TnW

However, adding:

if (end > data.size())
        end = data.size();

adds the bounds check back.

Interestingly enough, adding:

if (end >= data.size())
        end = data.size();

is fine.

fhahn · 2022-10-21T09:22:29Z

https://godbolt.org/z/136sWEcj3

Add -mllvm -enable-constraint-elimination seems to eliminate the bounds check: https://godbolt.org/z/EM7ra6TnW

However, adding:
if (end > data.size())
        end = data.size();
adds the bounds check back.

@jrmuizel could you check this again? I think the latest version should work fine with the check: https://godbolt.org/z/rno6K1eTs

This reverts commit 695ce48. The compile-time regression causing the revert has been fixed. Recommit the original patch. Original commit message: The pass should help to close a functional gap when it comes to reasoning about related conditions in a relatively general way. It addresses multiple existing issues (linked below) and the need for a more powerful reasoning system was also discussed recently in https://discourse.llvm.org/t/rfc-alternative-approach-of-dealing-with-implications-from-comparisons-through-pos-analysis/65601/7 On AArch64, the new pass performs ~2000 simplifications on MultiSource,SPEC2006,SPEC2017 with -O3. Compile-time impact: NewPM-O3: +0.20% NewPM-ReleaseThinLTO: +0.32% NewPM-ReleaseLTO-g: +0.28% https://llvm-compile-time-tracker.com/compare.php?from=f01a3a893c147c1594b9a3fbd817456b209dabbf&to=577688758ef64fb044215ec3e497ea901bb2db28&stat=instructions:u Fixes #49344. Fixes #47888. Fixes #48253. Fixes #49229. Fixes #58074. Reviewed By: asbirlea Differential Revision: https://reviews.llvm.org/D135915

llvmbot transferred this issue from llvm/llvm-bugzilla-archive Dec 11, 2021

cynecx mentioned this issue Dec 27, 2021

LLVM doesn't eliminate bounds check inside loop #51358

Open

fhahn mentioned this issue Feb 4, 2022

Enable constraint-elimination by default #49344

Closed

EugeneZelenko added the llvm:optimizations label Oct 21, 2022

thesamesam added the missed-optimization label Nov 5, 2022

fhahn closed this as completed in fb13dcf Jan 4, 2023

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Missed optimization leading to inability to remove bounds check #49229

Missed optimization leading to inability to remove bounds check #49229

alex mannequin commented Apr 7, 2021 •

edited by fhahn

jrmuizel commented Apr 8, 2021 •

edited by fhahn

fhahn commented Oct 21, 2022

Missed optimization leading to inability to remove bounds check #49229

Missed optimization leading to inability to remove bounds check #49229

Comments

alex mannequin commented Apr 7, 2021 • edited by fhahn

Extended Description

jrmuizel commented Apr 8, 2021 • edited by fhahn

fhahn commented Oct 21, 2022

alex mannequin commented Apr 7, 2021 •

edited by fhahn

jrmuizel commented Apr 8, 2021 •

edited by fhahn