[Bug middle-end/53986] New: missing vrp on bit-mask test

[Bug middle-end/53986] New: missing vrp on bit-mask test

[vries at gcc dot gnu.org]

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

             Bug #: 53986
           Summary: missing vrp on bit-mask test
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: vries@gcc.gnu.org


Consider the following test-case:
...
/* { dg-do link } */
/* { dg-options "-O2" } */

/* Based on f3 from vrp63.c, but with switch instead of if-chain.  */

extern void link_error (void);

void
f3 (int s)
{
  if (s >> 3 == -2)
    /* s in range [ -16, -9].  */
    ;
  else
    {
      /* s in range ~[-16, -9], so none of the case labels can be taken.  */
      switch (s)
    {
    case -16:
    case -12:
    case -9:
      link_error ();
      break;
    default:
      break;
    }
    }
}

int
main ()
{
  return 0;
}
...

the switchconv dump shows that the switch is converted to a bit-test:
...
;; Function f3 (f3, funcdef_no=0, decl_uid=1710, cgraph_uid=0)

beginning to process the following SWITCH statement (vrp72.c:18) : ------- 
switch (s_1(D)) <default: <L8>, case -16: <L2>, case -12: <L2>, case -9: <L2>>

  expanding as bit test is preferable
Switch converted
--------------------------------
f3 (int s)
{
  _Bool D.1736;
  long unsigned int D.1735;
  long unsigned int D.1734;
  long unsigned int csui.1;
  _Bool D.1732;
  int D.1730;
  unsigned int D.1731;
  int D.1720;

<bb 2>:
  D.1720_2 = s_1(D) >> 3;
  if (D.1720_2 == -2)
    goto <bb 5> (<L8>);
  else
    goto <bb 3>;

<bb 3>:
  D.1730_6 = s_1(D) + 16;
  D.1731_7 = (unsigned int) D.1730_6;
  D.1732_8 = D.1731_7 > 7;
  if (D.1732_8 != 0)
    goto <bb 6> (<L9>);
  else
    goto <bb 7>;

<bb 7>:
  D.1734_10 = (long unsigned int) D.1731_7;
  csui.1_9 = 1 << D.1734_10;
  D.1735_11 = csui.1_9 & 145;
  D.1736_12 = D.1735_11 != 0;
  if (D.1736_12 != 0)
    goto <bb 4> (<L2>);
  else
    goto <bb 8>;

<bb 8>:

<L9>:
  goto <bb 5> (<L8>);

<L2>:
  link_error ();

<L8>:
  return;

}
...


vrp doesn't manage to remove the path to function link_error.

Test-case vrp63 uses 'if (s == -16 || s == -12 || s == -9)' instead of a
switch. In that case, the path to link_error is removed.

Btw, if the switch is not converted to a bit-test the path to link_error is
also not removed by vrp, because it doesn't handle anti-ranges for switches.

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-07-17
                 CC|                            |rguenth at gcc dot gnu.org
          Component|middle-end                  |tree-optimization
            Summary|missing vrp on bit-mask     |missing vrp on bit-mask
                   |test                        |test, LSHIFT_EXPR not
                   |                            |handled
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-17 09:19:34 UTC ---
VRP does not handle LSHIFT like

  D.1734_10 = (long unsigned int) D.1731_7;
  csui.1_9 = 1 << D.1734_10;

it only handles LSHIFTs with a constant shift amount:

Visiting statement:
D.1734_10 = (long unsigned int) D.1731_8;

Found new range for D.1734_10: [0, 7]


Visiting statement:
csui.1_9 = 1 << D.1734_10;

Found new range for csui.1_9: [0, +INF]


Visiting statement:
D.1735_11 = csui.1_9 & 145;

Found new range for D.1735_11: [0, 145]

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #2 from vries at gcc dot gnu.org 2012-07-23 06:29:51 UTC ---
> Btw, if the switch is not converted to a bit-test the path to link_error is
> also not removed by vrp, because it doesn't handle anti-ranges for switches

submitted patch for this:
http://gcc.gnu.org/ml/gcc-patches/2012-07/msg01056.html

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

vries at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
                 CC|                            |steven at gcc dot gnu.org

--- Comment #3 from vries at gcc dot gnu.org 2012-08-05 09:36:43 UTC ---
(In reply to comment #1)
> VRP does not handle LSHIFT like
> 
>   D.1734_10 = (long unsigned int) D.1731_7;
>   csui.1_9 = 1 << D.1734_10;
> 
> it only handles LSHIFTs with a constant shift amount:
> 

That's true, but AFAIU that's not the reason tree-vrp doesn't optimize this
example.

The example is optimized with -fwrapv:
...
Found new range for s_12: ~[-16, -9]


Visiting statement:
D.1731_6 = sD.1710_12 + 16;

Meeting
  [-2147483632, -1]
and
  ~[-2147483632, 7]
to
  ~[0, 7]
Found new range for D.1731_6: ~[0, 7]


Visiting statement:
D.1732_7 = (unsigned int) D.1731_6;

Meeting
  [2147483648, +INF]
and
  [8, 2147483647]
to
  [8, +INF]
Found new range for D.1732_7: [8, +INF]


Visiting statement:
if (D.1732_7 > 7)


Visiting conditional with predicate: if (D.1732_7 > 7)

With known ranges
        D.1732_7: [8, +INF]

Predicate evaluates to: 1
...

but not with -fno-wrapv:
...
Found new range for s_12: ~[-16, -9]


Visiting statement:
D.1731_6 = sD.1710_12 + 16;

Meeting
  [-2147483632, -1]
and
  [8, +INF(OVF)]
to
  [-2147483632, +INF(OVF)]
Found new range for D.1731_6: [-2147483632, +INF(OVF)]


Visiting statement:
D.1732_7 = (unsigned int) D.1731_6;

Found new range for D.1732_7: [0, +INF]


Visiting statement:
if (D.1732_7 > 7)


Visiting conditional with predicate: if (D.1732_7 > 7)

With known ranges
        D.1732_7: [0, +INF]

Predicate evaluates to: DON'T KNOW
...

AFAIU, introducing the + 16 in emit_case_bit_tests on a signed type introduces
potential signed overflow, which is undefined with -fno-wrapv, so this is a
correctness bug as well:
...
 int D.1730;
 unsigned int D.1731;

<bb 3>:
  D.1730_6 = s_1(D) + 16;
  D.1731_7 = (unsigned int) D.1730_6;
...

I think we should cast to unsigned first, then add. That will solve the
correctness bug, and probably will allow tree-vrp to handle this even with
-fno-wrapv.

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[steven at gcc dot gnu.org]

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

--- Comment #4 from Steven Bosscher <steven at gcc dot gnu.org> 2012-08-05 11:05:56 UTC ---
(In reply to comment #3)
> I think we should cast to unsigned first, then add.

No, see what happens to "case -12" if you use ((unsigned)s_1+16).

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[steven at gcc dot gnu.org]

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

--- Comment #5 from Steven Bosscher <steven at gcc dot gnu.org> 2012-08-05 11:35:40 UTC ---
Just to illustrate:
$ cat t.c
#include <stdio.h>
int
main (void)
{
  int cases[] = { -16, -12, -9, -17 };
  int i, v;
  printf ("Show why cast must happen after add. T==1 iff (D.1732_8 != 0)\n");
  printf ("%-12s%-12s%-12s%-12s\t T T\n",
          "s_1", "(u)s_1", "s_1+16", "((u)s_1)+16");
  for (i = 0; i < 4; i++)
    {
      int v = cases[i];
      unsigned int uv = (unsigned) v;
      printf ("%-12d%-12u%-12d%-12u\t%2d%2d\n",
          v, uv, v+16, uv+16,
          (v+16) > 7, (uv+16) > 7);
    }
  return 0;
}
$ gcc t.c
$ ./a.out 
Show why cast must happen after add. T==1 iff (D.1732_8 != 0)
s_1         (u)s_1      s_1+16      ((u)s_1)+16      T T
-16         4294967280  0           0                0 0
-12         4294967284  4           4                0 0
-9          4294967287  7           7                0 0
-17         4294967279  -1          4294967295       0 1
$

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #6 from vries at gcc dot gnu.org 2012-08-05 13:32:15 UTC ---
> s_1         (u)s_1      s_1+16      ((u)s_1)+16      T T
> -16         4294967280  0           0                0 0
> -12         4294967284  4           4                0 0
> -9          4294967287  7           7                0 0
> -17         4294967279  -1          4294967295       0 1
> $

I think you forgot the cast to unsigned after the add that represents the
currently generated code:
...
@@ -13,7 +13,7 @@
       unsigned int uv = (unsigned) v;
       printf ("%-12d%-12u%-12d%-12u\t%2d%2d\n",
           v, uv, v+16, uv+16,
-          (v+16) > 7, (uv+16) > 7);
+          (unsigned int)(v+16) > 7, (uv+16) > 7);
     }
   return 0;
 }
...

With that added I see:
...
s_1         (u)s_1      s_1+16      ((u)s_1)+16      T T
-16         4294967280  0           0                0 0
-12         4294967284  4           4                0 0
-9          4294967287  7           7                0 0
-17         4294967279  -1          4294967295       1 1
...

We now see the correct result for all 4 cases for both methods.

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[stevenb.gcc at gmail dot com]

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

--- Comment #7 from stevenb.gcc at gmail dot com <stevenb.gcc at gmail dot com> 2012-08-05 13:53:30 UTC ---
On Sun, Aug 5, 2012 at 3:32 PM, vries at gcc dot gnu.org
<gcc-bugzilla@gcc.gnu.org> wrote:
> I think you forgot the cast to unsigned after the add that represents the
> currently generated code:

It would seem so...

Anyway, I am quite sure to remember correctly that I had the unsigned
before the add, and it caused bootstrap or test issues. But as always,
patches welcome :-)

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #8 from vries at gcc dot gnu.org 2012-08-05 15:31:39 UTC ---
Created attachment 27944
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27944
tree-switch-conversion-fix-undefined-overflow-introduction.patch, tentative
patch

> Anyway, I am quite sure to remember correctly that I had the unsigned
> before the add, and it caused bootstrap or test issues. But as always,
> patches welcome :-)

This tentative patch fixes the problem. I'm currently testing it, let's see if
I run into any trouble.

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #9 from vries at gcc dot gnu.org 2012-08-05 18:16:21 UTC ---
test-case for LSHIFT_EXPR vrp:
...
extern void link_error (void);

void
f3 (int s, int b)
{
  if (s >> 3 == -2)
    /* s in range [-16, -9].  */
    {
      s += 17;
      /* s in range [1, 8].  */
      b = (b & 1) + 1;
      /* b in range [1, 2].  */
      b =  b << s;
      /* b in range [bmin << smin, bmax << smax]
                    == [1 << 1, 2 << 8]
                    == [1, 512].  */
      if (b == 0|| b == 513)
        link_error ();
    }
}

int
main ()
{
  return 0;
}
...

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #10 from vries at gcc dot gnu.org 2012-08-06 08:37:51 UTC ---
> This tentative patch fixes the problem. I'm currently testing it, let's see if
> I run into any trouble.

Committed in r190168.

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #11 from vries at gcc dot gnu.org 2012-09-07 09:21:18 UTC ---
Author: vries
Date: Fri Sep  7 09:21:11 2012
New Revision: 191057

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=191057
Log:
2012-09-07  Tom de Vries  <tom@codesourcery.com>

    PR tree-optimization/53986
    * tree-vrp.c (extract_range_from_multiplicative_op_1): Allow
    LSHIFT_EXPR.
    (extract_range_from_binary_expr_1): Handle LSHIFT with constant range as
    shift amount.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-vrp.c

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #11 from vries at gcc dot gnu.org 2012-09-07 09:21:18 UTC ---
Author: vries
Date: Fri Sep  7 09:21:11 2012
New Revision: 191057

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=191057
Log:
2012-09-07  Tom de Vries  <tom@codesourcery.com>

    PR tree-optimization/53986
    * tree-vrp.c (extract_range_from_multiplicative_op_1): Allow
    LSHIFT_EXPR.
    (extract_range_from_binary_expr_1): Handle LSHIFT with constant range as
    shift amount.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-vrp.c

--- Comment #12 from vries at gcc dot gnu.org 2012-09-07 09:21:31 UTC ---
Author: vries
Date: Fri Sep  7 09:21:21 2012
New Revision: 191058

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=191058
Log:
2012-09-07  Tom de Vries  <tom@codesourcery.com>

    PR tree-optimization/53986
    * gcc.dg/tree-ssa/vrp80.c: New test.
    * gcc.dg/tree-ssa/vrp80-2.c: Same.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp80-2.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp80.c
Modified:
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

--- Comment #12 from vries at gcc dot gnu.org 2012-09-07 09:21:31 UTC ---
Author: vries
Date: Fri Sep  7 09:21:21 2012
New Revision: 191058

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=191058
Log:
2012-09-07  Tom de Vries  <tom@codesourcery.com>

    PR tree-optimization/53986
    * gcc.dg/tree-ssa/vrp80.c: New test.
    * gcc.dg/tree-ssa/vrp80-2.c: Same.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp80-2.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/vrp80.c
Modified:
    trunk/gcc/testsuite/ChangeLog

[Bug tree-optimization/53986] missing vrp on bit-mask test, LSHIFT_EXPR not handled

[vries at gcc dot gnu.org]

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

vries at gcc dot gnu.org changed:

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

--- Comment #13 from vries at gcc dot gnu.org 2012-09-07 09:25:34 UTC ---
(In reply to comment #1)
> VRP does not handle LSHIFT like
> 
>   D.1734_10 = (long unsigned int) D.1731_7;
>   csui.1_9 = 1 << D.1734_10;
> 
> it only handles LSHIFTs with a constant shift amount:
> 

This is handled in the commit in comment 11. All other issues in the report
have been addressed, closing bug.