[Bug tree-optimization/52267] New: a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[Bug tree-optimization/52267] New: a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

             Bug #: 52267
           Summary: a&~N where N has all the bits set up till a specific
                    point can be folded to ((unsigned)a) < N
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: pinskia@gcc.gnu.org


Take the following two functions.
int f(int a, int b)
{
  if (a>3||a<0) return a;
  a&=3;
  return a&3;
}

int f1(int a)
{
  if (a&~03)  return a;
  return a&3;
}

They should return just the argument.  Right now the first function does but
not the second.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |missed-optimization
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2012-02-16
         AssignedTo|unassigned at gcc dot       |pinskia at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-02-16 19:58:51 UTC ---
Mine, I am handling this.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |NEW

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-09 04:14:59 UTC ---
I hear Jakub has a patch for VRP to do ranges for (a&N)==/!=0 case.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |jakub at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-03-09 17:52:47 UTC ---
Created attachment 26867
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26867
gcc48-pr52267.patch

Unfinished, WIP, patch.  Will continue working on this next week.
On top of the two VRP patches I've posted today to gcc-patches.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #26867|0                           |1
        is obsolete|                            |

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-03-13 17:51:48 UTC ---
Created attachment 26885
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26885
gcc48-pr52267.patch

Updated patch.  This now passes the testcases (and has two of them, one that
tests whether we optimize as much as we want, the other that we don't
misoptimize), but I'd still like to write more tests tomorrow.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

--- Comment #5 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-03-15 10:37:31 UTC ---
Author: jakub
Date: Thu Mar 15 10:37:27 2012
New Revision: 185427

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=185427
Log:
    PR tree-optimization/52267
    * tree-vrp.c (masked_increment): New function.
    (register_edge_assert_for_2): Derive ASSERT_EXPRs
    from (X & CST1) cmp CST2 tests.

    * gcc.dg/pr52267.c: New test.
    * gcc.dg/tree-ssa/vrp65.c: New test.
    * gcc.dg/tree-ssa/vrp66.c: New test.

Added:
    trunk/gcc/testsuite/gcc.dg/pr52267.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp65.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp66.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

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

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-03-15 10:42:56 UTC ---
Fixed for 4.8+.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[gjl at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

Georg-Johann Lay <gjl at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |gjl at gcc dot gnu.org

--- Comment #7 from Georg-Johann Lay <gjl at gcc dot gnu.org> 2012-03-22 12:28:54 UTC ---
(In reply to comment #5)

> Added:
>     trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp66.c

In that test case there is:

int svals[] = {
  ...
  0x3cc0, // = 15552
  ...
};

and then in f2() this runs on abort. The if tests for the 3 upper bits in s
which are not all clear for 0x3cc0 if sizeof(int) = 2.

Thus the else part is entered where there is no test for 0x3cc0 or 15552 and
then abort is entered.

void
f2 (int s)
{
  if ((s & (7U << (BITSM1 - 2))) == 0)
    {
      if (s == 0 || s == 0x1cbf || s == 0x1cc0 || s == 0x1fff || s == 0x2000
      || s == 0x20 || s == 0x3cbf || s == 0x3cc0 || s == 0x3f || s == 1
      || s == (1 << (BITSM1 - 2)) - 1 || s == 2 || s == 24 || s == 5)
    return;
    }
  else
    {
      if (s == (-0x4000 << BITSH) - 1 || s == (-0x1000 << BITSH) - 1
      || s == (-0x7000 << BITSH) - 1 || s == (-0x5fcf << BITSH) - 1
      || s == (-0x4041 << BITSH) || s == (-0x4000 << BITSH)
      || s == (-0x1000 << BITSH) || s == (-0x7000 << BITSH)
      || s == (-0x4000 << BITSH) + 1 || s == -1 || s == -15 || s == -15550
      || s == -15552 || s == (0x7000 << BITSH) - 1
      || s == (0x7000 << BITSH) || s == (1 << (BITSM1 - 2))
      || s == -__INT_MAX__ - 1 || s == -32 || s == (3 << (BITSM1 - 2)) + 2
      || s == -5 || s == -63 || s == -64 || s == -65
      || s == -__INT_MAX__ + 4 || s == -8189 || s == -8191 || s == -8192
      || s == -8193 || s == -8250 || s == -8255 || s == -8256
      || s == -8257 || s == __INT_MAX__ || s == -__INT_MAX__ + 7)
    return;

I just rediced the test case to find this thinko; I don't know if there are
more because of the sheer amount of values in this program.

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |amylaar at gcc dot gnu.org

--- Comment #8 from Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> ---
(In reply to Georg-Johann Lay from comment #7)

> I just rediced the test case to find this thinko; I don't know if there are
> more because of the sheer amount of values in this program.

Here is a summary of the failing subtests / iteration counts:
f2,f1: i == 6,7
f4,f5,f3: i == 13,15,16,24,25,31
f7,f8,f6: i == 10..12,23
f11,f9: i == 11,13,15,24,25,31
f12,f10: i == 11,13,15,24,25,26,31
f17: i == 12,13
f21: i == 21,22,38..45

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.8.0

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

--- Comment #9 from Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> ---
(In reply to Jorn Wolfgang Rennecke from comment #8)
> (In reply to Georg-Johann Lay from comment #7)
> 
> > I just rediced the test case to find this thinko; I don't know if there are
> > more because of the sheer amount of values in this program.
> 
> Here is a summary of the failing subtests / iteration counts:
> f2,f1: i == 6,7
> f4,f5,f3: i == 13,15,16,24,25,31
> f7,f8,f6: i == 10..12,23
> f11,f9: i == 11,13,15,24,25,31
> f12,f10: i == 11,13,15,24,25,26,31
> f17: i == 12,13
> f21: i == 21,22,38..45

I've tried to shift/mask the values / tests to fit 16 bit ints while keeping
to the spirit of the tests and leaving the int >= 32 bit case unchanged,
but the various leading bits, 0000/ffff masking, and 16 bit value comparisons
are just to intertwined for this to make any sense.

I think we should simply restrict the test to target { ! int16 } .

[Bug tree-optimization/52267] a&~N where N has all the bits set up till a specific point can be folded to ((unsigned)a) < N

[amylaar at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=52267

--- Comment #10 from Jorn Wolfgang Rennecke <amylaar at gcc dot gnu.org> ---
The patch to fix the testsuite is here:
http://gcc.gnu.org/ml/gcc-patches/2013-07/msg00079.html