[Bug middle-end/96397] New: GCC Fails to exploit ranges from overflow tests

[Bug middle-end/96397] New: GCC Fails to exploit ranges from overflow tests

[law at redhat dot com]

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

            Bug ID: 96397
           Summary: GCC Fails to exploit ranges from overflow tests
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: law at redhat dot com
  Target Milestone: ---

Compile with -O2.  We should be able to eliminate the x > p1 test if we were
smart about back propagating equivalences to generate a range from the
__builtin_add_overflow.

This was derived from a bogus warning in tpm2-pkcs11's testsuite.

#include <stddef.h>
#include <stdlib.h>
extern void frob (void);

void
foo(size_t p1)
{
  size_t x = p1 - 4;
  size_t y;
  if (__builtin_add_overflow (x, 8, &y))
    {
      frob ();
    }
  else
    {
      if (x > p1)
        abort ();
    }
}

[Bug tree-optimization/96397] GCC Fails to exploit ranges from overflow tests

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |aldyh at gcc dot gnu.org,
                   |                            |amacleod at redhat dot com

--- Comment #1 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
>From a previous conversation with Jeff, I believe the corresponding IL is this:

;;   basic block 11, loop depth 0, count 487351684 (estimated locally), maybe
hot
;;   Invalid sum of incoming counts 749887186 (estimated locally), should be
487351684 (estimated locally)
;;    prev block 10, next block 12, flags: (NEW, REACHABLE, VISITED)
;;    pred:       18 [82.6% (guessed)]  count:749887186 (estimated locally)
(FALSE_VALUE,EXECUTABLE)
  _109 = .ADD_OVERFLOW (_106, 1);
  _110 = REALPART_EXPR <_109>;
  # DEBUG size => _110
  _111 = IMAGPART_EXPR <_109>;
  # DEBUG fail => (_Bool) _111
  if (_111 != 0)
    goto <bb 17>; [17.38%]
  else
    goto <bb 12>; [82.62%]

The ranger knows that _111 can only be [0,1], but we don't currently have a
backwards solver for the IMAGPART_EXPR code.  Currently it's unimplemented as
"op_unknown".  I suppose we could implement it, and the ranger should be then
able to solve for _109 (and eventually _106).

It would take a little twiddling, since range-ops currently doesn't look at
USE/DEF chains, and it would have to for the IMAGPART_EXPR since not all
IMAGPART_EXPR's are created equal.  E.g. for DEF's of .ADD_OVERFLOW, it means
something totally different than the IMAGPART_EXPR of a complex number.

Andrew, can you verify this is doable with minor tweaks?

[Bug tree-optimization/96397] GCC Fails to exploit ranges from overflow tests

[amacleod at redhat dot com]

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

--- Comment #2 from Andrew Macleod <amacleod at redhat dot com> ---
if I read this right, the basic premise is:
 x = p1 - 4, so if x + 8 doesn't overflow, then p1 - 4 couldn't have
underflowed, and therefore x must be > p1

which is a little more complicated than just back propagation.

Firstly, we have to understand that builtin_add_overflow is actually x + 8 and
that the IMAG_PART is in fact the overflow flag. we currently understand that
the IMAG_PART is a boolean, but we dont "understand" the add yet.   so we'll
eventually start treating those built-ins like tree-codes and provide the
appropriate understanding.

secondly, the x = p1 - 4 + 8 calculation is handle-able by rangeops, we just
need slightly better range tracking of overflows on unsigned values.. which is
already on my todo list.

and then the if (x > p1) would be handled by the upcoming relational code
automatically once we get the calculation right.

so its not quite as simple as back propagation, but it is on the radar,
possibly during this stage 1.

[Bug tree-optimization/96397] GCC Fails to exploit ranges from overflow tests

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2021-10-02
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed.