[Bug tree-optimization/98028] New: __builtin_sub_overflow_p not folded to const when some constraints are known

[Bug tree-optimization/98028] New: __builtin_sub_overflow_p not folded to const when some constraints are known

[denis.campredon at gmail dot com]

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

            Bug ID: 98028
           Summary: __builtin_sub_overflow_p not folded to const when some
                    constraints are known
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: denis.campredon at gmail dot com
  Target Milestone: ---

According to godbolt, f1 used to be optimised with gcc 7.

The same problem can be seen with signed types (and maybe more conditions?).
All the following functions should be only one instruction plus ret with O2

-----------------
unsigned f1(unsigned i, unsigned j) {
  if (j != i) __builtin_unreachable();
  return __builtin_sub_overflow_p(i, j, (unsigned)0);
}

unsigned f2(unsigned i, unsigned j) {
  if (j > i) __builtin_unreachable();
  return __builtin_sub_overflow_p(i, j, (unsigned)0);
}

unsigned f3(unsigned i, unsigned j) {
  if (j >= i) __builtin_unreachable();
  return __builtin_sub_overflow_p(i, j, (unsigned)0);
}

unsigned f4(unsigned i, unsigned j) {
  if (j < i) __builtin_unreachable();
  return __builtin_sub_overflow_p(i, j, (unsigned)0);
}
-----------------

[Bug tree-optimization/98028] [8/9/10/11 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|__builtin_sub_overflow_p    |[8/9/10/11 Regression]
                   |not folded to const when    |__builtin_sub_overflow_p
                   |some constraints are known  |not folded to const when
                   |                            |some constraints are known
   Last reconfirmed|                            |2020-11-27
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW
   Target Milestone|---                         |8.5
                 CC|                            |amacleod at redhat dot com,
                   |                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
f1 changed with r8-2630-g0db8ddfcb660397bab428ce0d271967d24c23177, until then
dom propagated one of those SSA_NAMEs, so we ended up with
__builtin_sub_overflow_p (i, i, (unsigned) 0) which we can still even on the
trunk optimize.

Anyway, I guess all this is a task for the symbolic value ranges in the ranger.

[Bug tree-optimization/98028] [8/9/10/11 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Blocks|                            |85316
      Known to work|                            |7.5.0
           Priority|P3                          |P2


Referenced Bugs:

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

[Bug tree-optimization/98028] [8/9/10/11 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
I see
=========== BB 2 ============
    <bb 2> :
    if (j_3(D) > i_4(D))
      goto <bb 3>; [INV]
    else
      goto <bb 4>; [INV]
=========== BB 3 ============
    <bb 3> :
    __builtin_unreachable ();
=========== BB 4 ============
j_3(D)  unsigned int VARYING
i_4(D)  unsigned int VARYING
    <bb 4> :
    _5 = .SUB_OVERFLOW (i_4(D), j_3(D));
    _1 = IMAGPART_EXPR <_5>;
    _2 = (_Bool) _1;
    _8 = _1;
    return _8;

gimple_range_adjustment currently recognizes the SUB_OVERFLOW/IMAGPART_EXPR
pattern and marks _1 as having range [0,1].

Once we can query if i_4 >= j_3, it should be pretty straightforward to change
the range of _1 to [0,0] or [1,1] as appropriate, which should then propagate
to the return.

[Bug tree-optimization/98028] [8/9/10/11 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Note, for
unsigned f1(unsigned i, unsigned j) {
  if (j != i) __builtin_unreachable();
  return i - j;
}
this is already optimized through:
  if (vr->varying_p ()
      && (code == PLUS_EXPR || code == MINUS_EXPR)
      && TREE_CODE (op1) == SSA_NAME
      && vr0.kind () == VR_RANGE
      && symbolic_range_based_on_p (&vr0, op1))
    {
      const bool minus_p = (code == MINUS_EXPR);
      value_range n_vr1;

      /* Try with VR0 and [-INF, OP1].  */
      if (is_gimple_min_invariant (minus_p ? vr0.max () : vr0.min ()))
        n_vr1.set (vrp_val_min (expr_type), op1);

      /* Try with VR0 and [OP1, +INF].  */
      else if (is_gimple_min_invariant (minus_p ? vr0.min () : vr0.max ()))
        n_vr1.set (op1, vrp_val_max (expr_type));

      /* Try with VR0 and [OP1, OP1].  */
      else
        n_vr1.set (op1, op1);

      range_fold_binary_expr (vr, code, expr_type, &vr0, &n_vr1);
    }
(and matching if below for the other range/operand pair) + the symbolic
handling
in range_fold_binary_symbolics_p -> extract_range_from_plus_minus_expr.
And that is also able to optimize
unsigned f1(unsigned i, unsigned j, unsigned *r) {
  if (j >= i) __builtin_unreachable();
  return __builtin_sub_overflow (i, j, r);
}
*r setting to 0.
But we don't have any such support for symbolics in
check_for_binary_op_overflow.

I guess it could be added even for GCC 11, the question is if it would be then
usable even for GCC 12 with smbolic ranges in ranger, or not.

[Bug tree-optimization/98028] [8/9/10/11 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[amacleod at redhat dot com]

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

--- Comment #4 from Andrew Macleod <amacleod at redhat dot com> ---
I would expect in gcc 12 we'll be handling it differently than that.

I have equivalences/relations up and running and will eventually get to
applying those to general statements... which I haven't gotten to yet.

the gimple_fold() routine uses fold_range () via range-ops to calculate a
result. I plan to additionally check if there is a relation between the
operands, and if so, invoke another range_ops routine to see if that relation
makes any further adjustments.

in this case, we'd have VARYING - VARYING, so ranges would resolve as expected
to VARYING.

A query if there is a relation between j_1 and i_2
=========== BB 4 ============
j_1(D)  unsigned int VARYING
i_2(D)  unsigned int VARYING
Equivalence set : [j_1(D), i_2(D)]
    <bb 4> :
    _3 = i_2(D) - j_1(D);
    return _3;
shows they are in an equivalence set, so that would be trivial to fold to 0 for
MINUS_EXPR.

as well, if we see other relations
 if (j > i) __builtin_unreachable();
  return i - j;

=========== BB 4 ============
j_1(D)  unsigned int VARYING
i_2(D)  unsigned int VARYING
Relational : (j_1(D) <= i_2(D))
    <bb 4> :
    _3 = i_2(D) - j_1(D);
    return _3;

it would likewise be pretty straightforward to add the restriction that _3 will
be [0, +INF]  (or [1, +INF] if it were j_1 < i_2)
If the relation is !=, we could also provide ~[0,0]

I'd expect the routine for MINUS_EXPR to simply switch on the possible
relations and intersect the current result with this reduced possible outcome.

I hope to get most of this in early in stage 1 and we can begin
enhancing/finding opportunities.
.

[Bug tree-optimization/98028] [9/10/11/12 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|8.5                         |9.4

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 8 branch is being closed.

[Bug tree-optimization/98028] [9/10/11/12 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.4                         |9.5

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9.4 is being released, retargeting bugs to GCC 9.5.

[Bug tree-optimization/98028] [10/11/12/13 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|9.5                         |10.4

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 9 branch is being closed

[Bug tree-optimization/98028] [10/11/12/13 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.4                        |10.5

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 10.4 is being released, retargeting bugs to GCC 10.5.

[Bug tree-optimization/98028] [11/12/13/14 Regression] __builtin_sub_overflow_p not folded to const when some constraints are known

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|10.5                        |11.5

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 10 branch is being closed.