[Bug tree-optimization/110131] New: [13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[Bug tree-optimization/110131] New: [13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[theodort at inf dot ethz.ch]

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

            Bug ID: 110131
           Summary: [13/14 Regression] Missed Dead Code Elimination when
                    using __builtin_unreachable since
                    r12-6924-gc2b610e7c6c
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: theodort at inf dot ethz.ch
  Target Milestone: ---

https://godbolt.org/z/xr8Ka91rr

Given:

void foo(void);
static int a, d, g, m, *h = &a, *i = &a;
static char j, l, *n = &j;
static short k;
static short o(short b, short c) { return c == 0 || b && c == 1 ?: b / c; }
static char p(unsigned char e, char f) {
    if (!(((e) >= 1) && ((e) <= 255))) {
        __builtin_unreachable();
    }
    return e + f;
}
int main() {
    g = *h;
    *n = 0;
    int q = *i;
    l = p((k >= 0 ^ q >= k) - 1, 3);
    if (o(l >= j, g) + (unsigned)4294967291)
        o(0, d);
    else
        foo();
    p(&m != 0, 0);
}

gcc-11.4 -O2 generates:

main:
        movb    $0, j(%rip)
        xorl    %eax, %eax
        ret

but gcc-trunk -O2 generates:


main:
        movl    a(%rip), %eax
        movb    $0, j(%rip)
        cmpw    $1, %ax
        ja      .L8
.L4:
        xorl    %eax, %eax
        ret
.L8:
        cwtl
        leal    1(%rax), %edx
        cmpl    $2, %edx
        movl    $0, %edx
        cmova   %edx, %eax
        cmpl    $5, %eax
        jne     .L4
        pushq   %rax
        call    foo
        xorl    %eax, %eax
        popq    %rdx
        ret

(12 and 13 generate similar code)

Started with r12-6924-gc2b610e7c6c

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |12.4

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2023-06-05
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  _33 = (intD.6) _13;
  # RANGE [irange] unsigned int [2, 32767][4294934528, +INF]
  _29 = (unsigned int) _13;
  # RANGE [irange] unsigned int [0, 0][3, 32768][4294934529, +INF]
  _37 = _29 + 1;
  _21 = _37 <= 2;
  # RANGE [irange] int [-32768, 0][2, 32767]
  _34 = _21 ? _33 : 0;
  if (_34 != 5)

First:
_t = _33 != 5
_t1 = _21 & _t
if (_t1 != 0)

Second:
_21 = _37 == 0 (because that is the only value that is less than or equal to 2
it could be)

So:
_21 = _29 == UINT_MAX
or:
_21 = _33 == -1

But since _33 != 5

so _t1 is 0.

Confirmed.

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #1)
>   _33 = (intD.6) _13;
>   # RANGE [irange] unsigned int [2, 32767][4294934528, +INF]
>   _29 = (unsigned int) _13;
>   # RANGE [irange] unsigned int [0, 0][3, 32768][4294934529, +INF]
>   _37 = _29 + 1;
>   _21 = _37 <= 2;
>   # RANGE [irange] int [-32768, 0][2, 32767]
>   _34 = _21 ? _33 : 0;
>   if (_34 != 5)
> 
> First:
> _t = _33 != 5
> _t1 = _21 & _t
> if (_t1 != 0)
> 
> Second:
> _21 = _37 == 0 (because that is the only value that is less than or equal to
> 2 it could be)
> 
> So:
> _21 = _29 == UINT_MAX
> or:
> _21 = _33 == -1
> 
> But since _33 != 5
> 
> so _t1 is 0.


Actually I got this wrong.
It should just be _33 == -1 here. But that can't be true as _33's range should
not include -1.

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So the biggest issue here is:
Global Exported: _37 = [irange] unsigned int [0, 0][3, 32768][4294934529, +INF]
Not folded
Folding statement: _21 = _37 <= 2;

_21 not being folded into _21 = _37 == 0

That is for:
```
bool g();

bool f1(unsigned t)
{
        if ((t + 1) < 2 || t > 2000)
          return (t < 3);
        return g();
}

bool f(unsigned t)
{
        if ((t + 1) < 2 || t > 2000)
          return t == 0;
        return g();
}
```
These two functions should have the same assembly code (for the above case, it
is not as important but for other cases it might be like in this one).

The other part of the issue I can fix if someone handles the VRP part.

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amacleod at redhat dot com
           Priority|P3                          |P2

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org
   Target Milestone|12.4                        |14.0

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
So I have a VRP patch which gets us to:
```
  # RANGE [irange] int [-32768, -1][2, 32767]
  _34 = (intD.6) _13;
  # RANGE [irange] unsigned int [2, 32767][4294934528, +INF]
  _30 = (unsigned int) _13;
  _22 = _30 == 4294967295;
  # RANGE [irange] int [-32768, 0][2, 32767]
  _35 = _22 ? _34 : 0;

```

Which is:
`(unsigned int)_13 == 4294967295 ? (intD.6) _13 : 0`

or rather `_13 == -1 ? -1 : 0`
or rather just `-(_13 == -1)`


  if (_35 != 5)

And obvious [-1,0] != 5.

So maybe:
```
(simplify
 (cond
  (eq:c@3 (convert1? @0) INTEGER_CST@1)
  (convert2? @0)
  INTEGER_CST@2
 )
 (if (INTEGRAL_TYPE_P (type))
  (cond @3 (convert @1) @2)
 )
)
```
There might be a few more checks dealing with @1 though.

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> So I have a VRP patch which gets us to:

  /* If the value range is defined by more than one pair,
     try to optimize to a singularity if either
     the first or last pair is a singleton.  */

That is if we have:
a range like: [0, 0][3, 32768][4294934529, +INF]

and we the comparison like `_37 <= 2`
Since 2 is a value between the first 2 pairs, we can just say this should be
the same as `_37 == 0` because that is the only value that is valid here.

The same idea happens for the last 2 pairs (and the last pair is a singleton).

Also if we only 2 pairs prefer the one which is 0 (since 0 is always simplier).

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[amacleod at redhat dot com]

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

--- Comment #6 from Andrew Macleod <amacleod at redhat dot com> ---
(In reply to Andrew Pinski from comment #5)
> (In reply to Andrew Pinski from comment #4)
> > So I have a VRP patch which gets us to:
> 
>   /* If the value range is defined by more than one pair,
>      try to optimize to a singularity if either
>      the first or last pair is a singleton.  */
> 
> That is if we have:
> a range like: [0, 0][3, 32768][4294934529, +INF]
> 
> and we the comparison like `_37 <= 2`
> Since 2 is a value between the first 2 pairs, we can just say this should be
> the same as `_37 == 0` because that is the only value that is valid here.
> 
> The same idea happens for the last 2 pairs (and the last pair is a
> singleton).
> 
> Also if we only 2 pairs prefer the one which is 0 (since 0 is always
> simplier).

hmm.  you should be able to trim out the "untrue" parts of the range. lets see.
do you have the comparison stmt, or is it just an expression?
maybe it doesnt matter.  if you know the expression is "_37 <= 2" you can ask
range-ops what the range of _37 is and intessect it with your range, and ask if
the result is a singleton.   then this will work for all kinds of things.

the format is 
op1_range (result_range, result_type, lhs_range, op2_range)

so it looks like:
range_op_handler handler (LT_EXPR);
if (handler)
  {
    Value_Range vr(TREE_TYPE (_37));
    if (handler->op1_range (vr, TREE_TYPE (_37), bool_one_range, [2,2]))
      _37_range.intersect (vr);
  }
if (_37.singleton_p ())
    blah()

you have a _37_range of [0, 0][3, 32768][4294934529, +INF]
op1_range for  [1, 1] = OP1 LT_EXPR [2,2] will return [0,2]
the intersection result will be [0,0]   

this would work for any condition/type  and both false and true LHS if you
provide [0,0] or [1,1] for the lhs.

in particular this may help with things like  x != 15,   where the pair that is
relevant to produce a singleton maybe wont be at one end or the other.

poking around for a minute, it looks like simplify_using_ranges from vr_values
calls a routine called test_for_singularity which has never been converted to
multi-ranges.  I wonder if reworking it might resolve this class of issues as
well?  Eventually we planned to get to simplify_using-ranges and friends, but
it hasnt happened yet

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #6)
> poking around for a minute, it looks like simplify_using_ranges from
> vr_values calls a routine called test_for_singularity which has never been
> converted to multi-ranges.  I wonder if reworking it might resolve this
> class of issues as well?  Eventually we planned to get to
> simplify_using-ranges and friends, but it hasnt happened yet

Yes that is actually better to change
simplify_compare_using_ranges_1/test_for_singularity use range_op_handler and
such. I have a new patch which does exactly that and it works .

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=110982

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
With https://gcc.gnu.org/pipermail/gcc-patches/2023-September/629128.html we
get:
  _34 = (int) _13;
  _30 = (unsigned int) _13;
  _22 = _30 == 4294967295;
  _35 = _22 ? _34 : 0;

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

--- Comment #9 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> So maybe:
> ```
> (simplify
>  (cond
>   (eq:c@3 (convert1? @0) INTEGER_CST@1)
>   (convert2? @0)
>   INTEGER_CST@2
>  )
>  (if (INTEGRAL_TYPE_P (type))
>   (cond @3 (convert @1) @2)
>  )
> )
> ```
> There might be a few more checks dealing with @1 though.

Oh we already have the above pattern except it uses int_fits_type_p which
returns false for -1. 

Similar issue as PR 110982  .

[Bug tree-optimization/110131] [12/13/14 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #8)
> With https://gcc.gnu.org/pipermail/gcc-patches/2023-September/629128.html we
> get:
>   _34 = (int) _13;
>   _30 = (unsigned int) _13;
>   _22 = _30 == 4294967295;
>   _35 = _22 ? _34 : 0;

Maybe:
(simplify
 (cond (eq (convert1?@4 @0) INTEGER_CST@1)
  (convert2? @0) INTEGER_CST@3)
  (if (type is a nop_conversion type from @1)
   (cond! @4 (convert @1) @3)))

This should give:
_30 = (unsigned int) _13;
_22 = _30 == 4294967295;
_35 = _22 ? -1 : 0;
if (_35 != 5)

_35 will -(convert)_22 really.
Anyways VRP will notice that _35 can't be 5 and optimize it out.

[Bug tree-optimization/110131] [12/13/14/15 Regression] Missed Dead Code Elimination when using __builtin_unreachable since r12-6924-gc2b610e7c6c

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|14.0                        |14.2

--- Comment #11 from Richard Biener <rguenth at gcc dot gnu.org> ---
GCC 14.1 is being released, retargeting bugs to GCC 14.2.