[Bug tree-optimization/63641] New: Invalid shift leads to incorrect code on 32-bit system

[Bug tree-optimization/63641] New: Invalid shift leads to incorrect code on 32-bit system

[ian at airs dot com]

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

            Bug ID: 63641
           Summary: Invalid shift leads to incorrect code on 32-bit system
           Product: gcc
           Version: 5.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: ian at airs dot com

Compile and run this program with -m32 -O2 on an x86 system.

#include <stdio.h>

int f (unsigned char) __attribute__ ((noinline));

int
f (unsigned char b)
{
  if (0x0 <= b && b <= 0x8)
    goto L;
  if (b == 0x0b)
    goto L;
  if (0x0e <= b && b <= 0x1a)
    goto L;
  if (0x1c <= b && b <= 0x1f)
    goto L;
  return 0;
 L:
  return 1;
}

int
main ()
{
  printf ("%d\n", f (' '));
}

The program should print 0.  However, when compiled with -m32 -O2 with current
mainline (revision 216611) it prints 1.

The generated code for f is:

00000000 <f>:
   0:   8b 4c 24 04             mov    0x4(%esp),%ecx
   4:   31 c0                   xor    %eax,%eax
   6:   80 f9 20                cmp    $0x20,%cl
   9:   77 0a                   ja     15 <f+0x15>
   b:   b8 ff c9 ff f7          mov    $0xf7ffc9ff,%eax
  10:   d3 e8                   shr    %cl,%eax
  12:   83 e0 01                and    $0x1,%eax
  15:   f3 c3                   repz ret 

The bug is obvious: when the value in %cl is 0x20, the shr does nothing.  The
ja needs to be a jae.

[Bug tree-optimization/63641] Invalid shift leads to incorrect code on 32-bit system

[ian at airs dot com]

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

Ian Lance Taylor <ian at airs dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at redhat dot com

--- Comment #1 from Ian Lance Taylor <ian at airs dot com> ---
I'm guessing that this change is the cause of the problem:

2014-10-17  Jakub Jelinek  <jakub@redhat.com>

    PR tree-optimization/63464
    * gimple.h (gimple_seq_discard): New prototype.
    * gimple.c: Include stringpool.h and tree-ssanames.h.
    (gimple_seq_discard): New function.
    * optabs.h (lshift_cheap_p): New prototype.
    * optabs.c (lshift_cheap_p): New function, moved from...
    * tree-switch-conversion.c (lshift_cheap_p): ... here.
    * tree-ssa-reassoc.c: Include gimplify.h and optabs.h.
    (reassoc_branch_fixups): New variable.
    (update_range_test): Add otherrangep and seq arguments.
    Unshare exp.  If otherrange is NULL, use for other ranges
    array of pointers pointed by otherrangep instead.
    Emit seq before gimplified statements for tem.
    (optimize_range_tests_diff): Adjust update_range_test
    caller.
    (optimize_range_tests_xor): Likewise.  Fix up comment.
    (extract_bit_test_mask, optimize_range_tests_to_bit_test): New
    functions.
    (optimize_range_tests): Adjust update_range_test caller.
    Call optimize_range_tests_to_bit_test.
    (branch_fixup): New function.
    (execute_reassoc): Call branch_fixup.

[Bug tree-optimization/63641] Invalid shift leads to incorrect code on 32-bit system

[ian at airs dot com]

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

--- Comment #2 from Ian Lance Taylor <ian at airs dot com> ---
Created attachment 33805
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=33805&action=edit
sample patch

This patch seems to fix the problem, and the new tests still pass.  But I
haven't done full testing and I'm not entirely sure whether this is the right
approach.

[Bug tree-optimization/63641] Invalid shift leads to incorrect code on 32-bit system

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2014-10-24
                 CC|                            |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I'd say the right fix would be instead:
--- gcc/tree-ssa-reassoc.c    2014-10-17 12:53:59.286321210 +0200
+++ gcc/tree-ssa-reassoc.c    2014-10-24 22:38:55.762859480 +0200
@@ -2513,7 +2513,7 @@ optimize_range_tests_to_bit_test (enum t
     {
       tree high = wide_int_to_tree (TREE_TYPE (lowi),
                     wi::to_widest (lowi)
-                    + prec - wi::clz (mask));
+                    + prec - 1 - wi::clz (mask));
       operand_entry_t oe = (*ops)[ranges[i].idx];
       tree op = oe->op;
       gimple stmt = op ? SSA_NAME_DEF_STMT (op)
there is no need to build further trees, and the other use of high also wants
the one smaller value.
The thing is, bit 0 of mask is value lowi, if e.g. wi::clz(mask) is 0, then
it means the topmost bit of mask is set, so the highest value in the interval
is
lowi + prec - 1.  If only lowest bit of mask would be set (not possible, at
least 3 ranges of bits need to be there), then wi::clz(mask) would be prec - 1
and we'd want high to be equal to lowi.  Mask is never zero.

[Bug tree-optimization/63641] [5 Regression] Invalid shift leads to incorrect code on 32-bit system

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
   Target Milestone|---                         |5.0
            Summary|Invalid shift leads to      |[5 Regression] Invalid
                   |incorrect code on 32-bit    |shift leads to incorrect
                   |system                      |code on 32-bit system

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Will also try to tweak testcase so that we have also something that fails on
64-bit targets.  Is Monday ok to resolve this?

[Bug tree-optimization/63641] [5 Regression] Invalid shift leads to incorrect code on 32-bit system

[ian at airs dot com]

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

--- Comment #5 from Ian Lance Taylor <ian at airs dot com> ---
Monday is fine.  Thanks.

[Bug tree-optimization/63641] [5 Regression] Invalid shift leads to incorrect code on 32-bit system

[jakub at gcc dot gnu.org]

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

--- Comment #6 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Author: jakub
Date: Sat Oct 25 20:21:47 2014
New Revision: 216693

URL: https://gcc.gnu.org/viewcvs?rev=216693&root=gcc&view=rev
Log:
    PR tree-optimization/63641
    * tree-ssa-reassoc.c (optimize_range_tests_to_bit_test): Set high
    to low + prec - 1 - clz (mask) instead of low + prec - clz (mask).

    * gcc.c-torture/execute/pr63641.c: New test.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr63641.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-reassoc.c

[Bug tree-optimization/63641] [5 Regression] Invalid shift leads to incorrect code on 32-bit system

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #7 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed.