#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; } https://godbolt.org/z/Ksecrec11 Clang is able to eliminate the the check when using -mllvm -enable-constraint-elimination https://godbolt.org/z/K67b8PTM9
For the testcase the issue is that the range check is inside the loop and eliminating it requires symbolic range propagation to work "better". We arrive at i_28: long unsigned int [_32, +INF] EQUIVALENCES: { i_1 i_12 } (2 elements) i_12: size_t VARYING for <bb 2> [local count: 118253447]: if (start_4(D) < end_5(D)) goto <bb 3>; [99.96%] else goto <bb 4>; [0.04%] <bb 3> [local count: 118206146]: _9 = MEM[(const struct vector *)data_7(D)].D.18843._M_impl.D.18156._M_finish; _8 = MEM[(const struct vector *)data_7(D)].D.18843._M_impl.D.18156._M_start; _14 = _9 - _8; _15 = _14 /[ex] 8; _16 = (long unsigned int) _15; _33 = _16 >= end_5(D); _34 = _16 > start_4(D); _22 = _33 & _34; if (_22 != 0) goto <bb 7>; [99.92%] else goto <bb 4>; [0.08%] <bb 4> [local count: 141847]: __assert_fail ("start < end && start < data.size() && end <= data.size()", "t.C", 7, "uint64_t f(std::vector<long unsigned int>&, size_t, size_t)"); <bb 5> [local count: 834435851]: if (i_12 >= _16) goto <bb 6>; [0.05%] else goto <bb 7>; [99.95%] <bb 6> [local count: 381018]: # i_38 = PHI <i_12(5)> std::__throw_out_of_range_fmt ("vector::_M_range_check: __n (which is %zu) >= this->size() (which is %zu)", i_38, _16); <bb 7> [local count: 952166435]: # total_3 = PHI <total_11(5), 0(3)> # i_2 = PHI <i_12(5), start_4(D)(3)> _10 = MEM[(value_type &)_8 + i_2 * 8]; total_11 = total_3 + _10; i_12 = i_2 + 1; if (i_12 != end_5(D)) goto <bb 5>; [87.64%] else goto <bb 8>; [12.36%] <bb 8> [local count: 117730583]: # total_37 = PHI <total_11(7)> return total_37;
looking at VRP2: the initial assert provides: Relational : (start_4(D) < end_5(D)) Relational : (_16 > start_4(D)) Relational : (end_5(D) <= _16) unfortunately, the loop back edge is: i_12 = i_17 + 1; if (end_5(D) != i_12) goto <bb 5>; [89.00%] else goto <bb 8>; [11.00%] so it only registers what it knows from the branch: Relational : (i_12 != end_5(D)) so when it gets to the bounds check at: if (i_12 >= _16) goto <bb 6>; [0.04%] else goto <bb 10>; [99.96%] It doesn't really know the answer. If the loop branch had remained if (i_12 < end_5) instead of being changed, then we would instead get the relation: Relational : (i_12 < end_5(D)) which combined with the earlier Relational : (end_5(D) <= _16), should register the transitive relation (i_12 < _16), and enable removal of the check. This is transformed in ivopts, which runs after vrp1. A quick check shows at VRP1 time, the bounds are still using the < format... In fact... running with --param=vrp1-mode=ranger registers this exact transitive relation, and produces: Relational : (i_2 < _16) Relational : (i_2 < end_5(D)) <bb 6> [local count: 952547451]: if (0 != 0) goto <bb 7>; [0.04%] else goto <bb 8>; [99.96%] and eliminates the bounds check. So we can close this PR when we turn ranger on by default for VRP1.
Fixed by commit e7310e24b1c0ca67b1bb507c1330b2bf39e59e32 Author: Andrew MacLeod <amacleod@redhat.com> Date: Tue Oct 25 16:42:41 2022 -0400 Make ranger vrp1 default.