LLVM fails to remove bounds check if value is guaranteed to be less than value smaller than length.

[AngelicosPhosphoros]

I tried this code:

#include <cstdint>
#include <vector>

int get_idx_half(
    const std::size_t idx,
    const std::vector<int>& __restrict__ nums
) {
    if (idx >= nums.size() / 2){
        return 0;
    }
    // Bounds check here is not optimized.
    return nums.at(idx);
}

int get_idx_full(
    const std::size_t idx,
    const std::vector<int>& __restrict__ nums
) {
    if (idx >= nums.size()){
        return 0;
    }
    // Bounds check here is eliminated.
    return nums.at(idx);
}

This code generates this machine code:

get_idx_half(unsigned long, std::vector<int, std::allocator<int> > const&):   # @get_idx_half(unsigned long, std::vector<int, std::allocator<int> > const&)
        push    rax
        mov     rcx, rdi
        mov     rdi, qword ptr [rsi]
        mov     rdx, qword ptr [rsi + 8]
        sub     rdx, rdi
        sar     rdx, 2
        mov     rsi, rdx
        shr     rsi
        xor     eax, eax
        cmp     rsi, rcx
        jbe     .LBB0_3
        cmp     rdx, rcx
        jbe     .LBB0_4
        mov     eax, dword ptr [rdi + 4*rcx]
.LBB0_3:
        pop     rcx
        ret
.LBB0_4:
        lea     rdi, [rip + .L.str]
        mov     rsi, rcx
        xor     eax, eax
        call    std::__throw_out_of_range_fmt(char const*, ...)@PLT
get_idx_full(unsigned long, std::vector<int, std::allocator<int> > const&):   # @get_idx_full(unsigned long, std::vector<int, std::allocator<int> > const&)
        mov     rcx, qword ptr [rsi]
        mov     rdx, qword ptr [rsi + 8]
        sub     rdx, rcx
        sar     rdx, 2
        xor     eax, eax
        cmp     rdx, rdi
        jbe     .LBB1_2
        mov     eax, dword ptr [rcx + 4*rdi]
.LBB1_2:
        ret
.L.str:
        .asciz  "vector::_M_range_check: __n (which is %zu) >= this->size() (which is %zu)"

In the second function, bounds check at nums.at(idx) is eliminated. However, it is not eliminated in first function despite the fact that idx is limited to half of length which is guaranteed to be in valid range for indices of vector.

godbolt link

[floatshadow]

I think it is similar to #61393 @nikic.
When the pass pipeline reaches isImpliedCondICmps (in simplifyICmpInst), the full case will find LHS and RHS shared the operands and do the fold, but the half case will not.

isTruePredicate , isImpliedCondOperands, isImpliedCondICmps seem leave out some cases, I'll fix it.

[caojoshua]

Submitted fix for review https://reviews.llvm.org/D151541

[caojoshua]

Fixed by cb9f1aa. See https://godbolt.org/z/jaocbn83K.

Note that the patch only can eliminate the bounds check when dividing by a power of 2. If dividing by 3 or some unknown, we still can't remove the bounds checks. See the same godbolt link above for an example. I'll create a separate patch for that.