[Bug middle-end/109637] New: unnecessary range check in complete switch on bitfield

[Bug middle-end/109637] New: unnecessary range check in complete switch on bitfield

[mattiase at acm dot org]

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

            Bug ID: 109637
           Summary: unnecessary range check in complete switch on bitfield
           Product: gcc
           Version: 13.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: mattiase at acm dot org
  Target Milestone: ---

This fully populated switch still produces some kind of useless range check:

struct S { unsigned x : 2; };
int f (struct S *s) {
    switch(s->x) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 2;
        case 3: return 3;
    }
}

->
        movzbl  (%rdi), %eax
        andl    $3, %eax
        leal    -1(%rax), %edx
        movzbl  %al, %eax
        cmpb    $3, %dl
        movl    $0, %edx
        cmovnb  %edx, %eax
        ret

GCC apparently understands that the switch is complete at some level since
anything after the switch is recognised as dead code, so the range check is a
bit puzzling.

The code is fine if we explicitly mask the switch value as in `switch(s->x &
3)`:

        movzbl  (%rdi), %eax
        andl    $3, %eax
        ret

[Bug middle-end/109637] unnecessary range check in complete switch on bitfield

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-04-26
          Component|middle-end                  |tree-optimization
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
  # RANGE [irange] unsigned char [0, 3] NONZERO 0x3
  _6 = (unsigned charD.30) _1;
  # RANGE [irange] unsigned char [0, 2][+INF, +INF]
  _2 = _6 + 255;

  if (_2 <= 2)

VRP Should have changed _2 <= 2 to just _2 != 255 which then gets folded into
_6 != 0 which then will get folded into _1 != 0

and then phiopt could also have sunk the cast:
  if (_2 <= 2)
    goto <bb 3>; [50.00%]
  else
    goto <bb 4>; [50.00%]

  <bb 3> [local count: 536870913]:
<L7>:
  _9 = (int) _1;

  <bb 4> [local count: 1073741824]:
  # _3 = PHI <0(2), _9(3)>

Which then would get simplified into just:
_3 = (int)_1;

So there are a few things that needed to be done here ...

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[amacleod at redhat dot com]

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

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> ---
I think the bigger questions is why did switch conv change:

  1 = s_5(D)->x;
  switch (_1) <default: <L5> [INV], case 1: <L1> [INV], case 2: <L2> [INV],
case 3: <L3> [INV]>

  <bb 3> :
<L1>:
  goto <bb 6>; [INV]

  <bb 4> :
<L2>:
  goto <bb 6>; [INV]

  <bb 5> :
<L3>:

  <bb 6> :
  # _3 = PHI <0(2), 1(3), 2(4), 3(5)>
<L5>:
  return _3;


to 


  <bb 2> :
  _1 = s_5(D)->x;
  _6 = (unsigned char) _1;
  _2 = _6 + 255;
  if (_2 <= 2)
    goto <bb 4>; [INV]
  else
    goto <bb 3>; [INV]

  <bb 3> :
<L6>:
  _10 = 0;
  goto <bb 5>; [100.00%]

  <bb 4> :
<L7>:
  _8 = (unsigned int) _1;
  _9 = (int) _1;
  _7 = _9;

  <bb 5> :
  # _3 = PHI <_10(3), _7(4)>
<L8>:
<L5>:
  return _3;


Why are we adding -1 to [0,3] ?  Thats the root of this issue I think?  seems
strange

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[amacleod at redhat dot com]

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

--- Comment #3 from Andrew Macleod <amacleod at redhat dot com> ---
Just to add:

040.evrp:
_2  : [irange] int [0, 3] NONZERO 0x3
_3  : [irange] int [0, 3] NONZERO 0x3

  <bb 2> :
  _1 = s_5(D)->x;
  _2 = (int) _1;
  switch (_1) <default: <L5> [INV], case 1: <L1> [INV], case 2: <L2> [INV],
case 3: <L3> [INV]>


we know the range of _2 is [0, 3].. wonder why we don't know that about _1... 
having a look

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #3)
> we know the range of _2 is [0, 3].. wonder why we don't know that about
> _1...  having a look

I assume the range of _1 is [-INF, +INF] (aka [0, 3] aka varrying) really as _1
has a type of unnamed-unsigned:2 so it would cover the whole range of the type.

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[amacleod at redhat dot com]

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

--- Comment #5 from Andrew Macleod <amacleod at redhat dot com> ---
Perhaps switch conv just needs to look at it...

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Mine.

For the simple example in comment #0, I have a patch.  This is the updating of
test_for_singularity patch.

For the GIMPLE_SWITCH issue in EVRP, I suspect the code in vr-values.c needs to
update and/or added to see if the default was taken or not.  I will handle this
too.

[Bug tree-optimization/109637] unnecessary range check in complete switch on bitfield

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Macleod from comment #2)
> 
> Why are we adding -1 to [0,3] ?  Thats the root of this issue I think? 
> seems strange

if we ignore the range for a second.

When switch conversion happens we have:
  switch (_1) <default: <L5> [INV], case 1: <L1> [INV], case 2: <L2> [INV],
case 3: <L3> [INV]>

So when _1 is either 0 or > 3, default case will happen.

The real problem is switch conversion promotes to a 8 bit type when it does the
comparisons and does not take into the ranges.

Related testcase (ignoring that there is a bogus warning, see PR 95513 for that
and not fixed even with my VRP patch):
```
int f (unsigned t) {
    switch(t & 0x3) {
        case 0: return 0;
        case 1: return 1;
        case 2: return 2;
        case 3: return 3;
    }
}
```
my VRP patch also fixes the above. Now switch conversion should use the range
info too. I will look into adding that .... But at least we get decent code for
the orginal and related cases now.