<table border="1" cellspacing="0" cellpadding="8">
<tr>
<th>Issue</th>
<td>
<a href=https://github.com/llvm/llvm-project/issues/62441>62441</a>
</td>
</tr>
<tr>
<th>Summary</th>
<td>
LLVM fails to remove bounds check if value is guaranteed to be less than value smaller than length.
</td>
</tr>
<tr>
<th>Labels</th>
<td>
new issue
</td>
</tr>
<tr>
<th>Assignees</th>
<td>
</td>
</tr>
<tr>
<th>Reporter</th>
<td>
AngelicosPhosphoros
</td>
</tr>
</table>
<pre>
I tried this code:
```c++
#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:
```asm
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](https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:39,endLineNumber:22,positionColumn:39,positionLineNumber:22,selectionStartColumn:39,selectionStartLineNumber:22,startColumn:39,startLineNumber:22),source:'%23include+%3Ccstdint%3E%0A%23include+%3Cvector%3E%0A%0Aint+get_idx_half(%0A++++const+std::size_t+idx,%0A++++const+std::vector%3Cint%3E%26+__restrict__+nums%0A)+%7B%0A++++if+(idx+%3E%3D+nums.size()+/+2)%7B%0A++++++++return+0%3B%0A++++%7D%0A++++//+Bounds+check+here+is+not+optimized.%0A++++return+nums.at(idx)%3B%0A%7D%0A%0Aint+get_idx_full(%0A++++const+std::size_t+idx,%0A++++const+std::vector%3Cint%3E%26+__restrict__+nums%0A)+%7B%0A++++if+(idx+%3E%3D+nums.size())%7B%0A++++++++return+0%3B%0A++++%7D%0A++++//+Bounds+check+here+is+eliminated.%0A++++return+nums.at(idx)%3B%0A%7D'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:49.40438871473354,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:clang1600,deviceViewOpen:'1',filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'-O3+-std%3Dc%2B%2B20',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+clang+16.0.0+(Editor+%231)',t:'0')),k:50.595611285266465,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4)
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzcWF-PozgS_zTOi9UIDOTPQx6a9LRupd6bkXZvX5FjiuBZY-dsk870pz_ZhgQSume1N7crXQsR4frrKv-qyk2N4QcJsEV5gfKnBe1so_T2UR5AcKbMl0aZY6O0Mou9qr5tf8JWc6iwbbjBTFWA0kcUP6F4eC_j8DBECveEVZJyyURXAUbpjhlbcWlR-mmOegJmlb4S_ZtLiw9gS16dy4aKGpF1IGCMMVPSWGxs5XxJHw1_g9JiXp0R2b3LNZjZ9Z6QJS5LDcZqzmxZYtm1ZnBvg9Gq3wnmNUZkzaszdlLpk2eMnE3nk2Mlz5ggsrmK9H8abKcljlE6IqDV0-iDPDvpQnWyMpg1wH7HDWjA3GCpLFZHy1v-BlV0lem1ei-oDa4564ORi4H7QNadEH9fIDH-bix_fBRB8JZLav9kCIfDHT5_HTCADyBBUwsm4KKlrOESPsQHNW1YuTnWnfSArLBQ8oDI7p1AjwlUCMXoOAkuniFPiCz9Vh59YFKMsvgvMTjJ2bEzjQ80PfeEVp1CNpk7W1hXfCpxoVfc0f_9qnSFj1ZjlBfacJQ_3fNrf07veDEiBV7fSZhu31uY98BQPaaTd_wzPEifb6QbfaFPCGcVCEC9WqA3gqw9ThSzG_rXPfjf6KUo4jK9Fx7287FgNr-d3qtqEsIqhDBD5NFpHQI5eDCc70uy1fGS2lvkjiWzq6QAOs62M8qP3mj0EhmrZ9P9UZRclN-NMBXCp2g4zWVpG61eS9XZUtWlpvIAZd26QsAaqodj_ei0RVHkTncWf3n5dQrfvpj-dfD9nxqcjzabBdg1O1fU_jdIvCTzYwj-YSTdAnyMhKR8B9izSGDnKxIqPkGCU3SLhNGB96f4lh5Rw_gbRoQMqfLH8ef-CPrO5VJfltL1ydeGs8Y1MUTyt84309A1Xc95QOmnyRByz44ImW1j4_dPEtsGsAGmZIXrTjLLlXSR2I_bKbUYLeO7hrmMb3os_od6hRNop4DbYYy5MmAucc21sRdTuAJz5Ba8GzVlFtsmWHM2ggEn7oStwq6HYVVjAfJgG3zZ86GjmkoLgWsPztCJCl5hH1tcK425rDgD48RD_KNJPPLioKq9EhYLLn93ySbrxtqjcWnyI0ZPj5Q--IX04EmJz8H6_Y8GpY9uNPhUcZd1suOeuq65AElbPzKQVYLICpFdraT9hVHhVpOsX_iXgS_nwBYHtq-OjMhOUOlsMURyN3_7186AgJBIbwdktVOia91nukFkB7J64RL-2bV7cKeQEER2R2W4k5myDqv3_Bcjv1iq7VRqSpuRnRGZ5fQU1WnWB8ntcLg8-AtHfr1ekNxNo7mbO--ZesSNefxwjEhxe88I5OLy9HWyuJmTESn6Sfm7Alfju5GjrvIW49EZkcIPz0HfJri-Ku7089r_BhQWg7r0qZefDNSFP6lFCOWcsvETBmNEitjpm-PNV08zq8_BSJjAXQB8JSOFm8Kdv25NKheS0Y3mVs3F-F2ZGflytX-XvuF283-Vvr85aePr05_P1yrgWAQI56GAyUk5U-FrNy5jRQ_8sJD29dGO5UKEdq5rZpsoi7N0vV4l2SpN8-xqMfvAYvhwNT6eUb6bL-XtkQsYFfLLSvrIXEFOlrHTVsGJM_iNw-vnI8hplefCgg6tZb2fOLbnkupvE-6w9Hn_FZidEJhqW5D2sxTfJjoqaKk8CJgucu2K8gnMZBnOwDo7bUJcWhATLsH3mupvu_6Ge1m3mrdjURe0WtCDmd_2D2hugu_NKCXOoKsqSvbbevicIlI8OPQ6VI2ESa_-g_aYzHTHZK45Ju_1xuT91nhPupe8F5jjm7TF5A_DC5HivF4-LDMHdx9cUiTLKI7iUJGGAeUCuM3HmMvjKN_kyyQh65wsl9ky_xGgG22GfFfJnPAJtAnZzRDZLKptWm3SDV3ANlmuySqNU0IWzTZmS7LerOr1uoZ9nK1yuoE4Z2m82awISdcLviUxSeOMbOIkzgmJNlm63mQJzVcEsryuUBZDS7mIhDi1bixccGM62C5JliULQfcgjP9HKyESXrEnuqk8f1rorZN52HcHg7JYcGPNVYvlVsD25eW3n3FNuTBuptXQqhNMx3JeuyG3g9kJWIAxbpiWPY9pqRCgw1KYn6NFp8X2Zsjltun2EVMtIs_Oo_7n4aiVrz_k2e_DIPLs9_mfAAAA__-tpTxo">