[Bug tree-optimization/99966] New: Bounds check not eliminated by assert

[Bug tree-optimization/99966] New: Bounds check not eliminated by assert

[jmuizelaar at mozilla dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99966

            Bug ID: 99966
           Summary: Bounds check not eliminated by assert
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: jmuizelaar at mozilla dot com
  Target Milestone: ---

#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

[Bug tree-optimization/99966] Bounds check not eliminated by assert

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99966

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-04-08
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
             Blocks|                            |85316

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
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;


Referenced Bugs:

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85316
[Bug 85316] [meta-bug] VRP range propagation missed cases

[Bug tree-optimization/99966] Bounds check not eliminated by assert

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99966

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
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.

[Bug tree-optimization/99966] Bounds check not eliminated by assert

[amacleod at redhat dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99966

Andrew Macleod <amacleod at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|NEW                         |RESOLVED

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Fixed by
commit e7310e24b1c0ca67b1bb507c1330b2bf39e59e32
Author: Andrew MacLeod <amacleod@redhat.com>
Date:   Tue Oct 25 16:42:41 2022 -0400

    Make ranger vrp1 default.

[Bug tree-optimization/99966] Bounds check not eliminated by assert

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99966

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
           Keywords|                            |missed-optimization