[Bug tree-optimization/39870] New: VRP can't see through cast to unsigned

[Bug tree-optimization/39870] New: VRP can't see through cast to unsigned

[aph at gcc dot gnu dot org]

A common way to do array bounds checking is to cast the index i to unsigned and
then check

  if ((unsigned)i > (unsigned)length)
    abort();

instead of

  if (i >= length || i < 0)
    abort();

The phrases are equivalent, but VRP doesn't know that so the bounds check is
not eliminated.

The problem is that this is such a common idiom that it will affect many
programs.


-- 
           Summary: VRP can't see through cast to unsigned
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: aph at gcc dot gnu dot org
  GCC host triplet: x86_64-linux-gnu
OtherBugsDependingO 21855
             nThis:


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[aph at gcc dot gnu dot org]

------- Comment #1 from aph at gcc dot gnu dot org  2009-04-23 15:46 -------
Sorry, typo'd the first expression.  Should be

  if ((unsigned)i >= (unsigned)length)
    abort();


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[aph at gcc dot gnu dot org]

------- Comment #2 from aph at gcc dot gnu dot org  2009-04-23 15:47 -------
typedef struct
{
  int length;
  int data[];
} t_m;

t_m *m;

int foo()
{
  int val = 0;
  int i;

  for (i = 0; i < m->length; i++)
    {
#ifdef BORKED
      if ((unsigned int)i >= (unsigned int)m->length)
#else
      if (i >= m->length || i < 0)
#endif
        abort();
      val += m->data[i];
    }
  return val;
}


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[aph at gcc dot gnu dot org]

------- Comment #3 from aph at gcc dot gnu dot org  2009-04-23 15:49 -------
-DBORKED on the left

foo:                             foo:
.LFB0:                           .LFB0:
        .cfi_startproc                   .cfi_startproc
        subq    $8, %rsp       <
        .cfi_def_cfa_offset 1  <
        movq    m(%rip), %rcx            movq    m(%rip), %rcx
        xorl    %eax, %eax               xorl    %eax, %eax
        movl    (%rcx), %esi   |         movl    (%rcx), %edx
        testl   %esi, %esi     |         testl   %edx, %edx
        jle     .L3                      jle     .L3
                               >         subl    $1, %edx
                               >         leaq    4(,%rdx,4), %rsi
        xorl    %edx, %edx               xorl    %edx, %edx
        jmp     .L4            <
        .p2align 4,,10                   .p2align 4,,10
        .p2align 3                       .p2align 3
.L5:                           <
        addq    $4, %rcx       <
        cmpl    %esi, %edx     <
        jae     .L9            <
.L4:                             .L4:
        addl    $1, %edx       |         addl    4(%rcx,%rdx), %eax
        addl    4(%rcx), %eax  |         addq    $4, %rdx
        cmpl    %esi, %edx     |         cmpq    %rsi, %rdx
        jl      .L5            |         jne     .L4
.L3:                             .L3:
        addq    $8, %rsp       |         rep
        ret                              ret
.L9:                           <
        call    abort          <
        .cfi_endproc                     .cfi_endproc
.LFE0:                           .LFE0:
        .size   foo, .-foo               .size   foo, .-foo


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[paolo dot carlini at oracle dot com]

------- Comment #4 from paolo dot carlini at oracle dot com  2009-04-23 15:51 -------
Interesting. Out of curiosity, why people don't naturally use an unsigned type
for an index?


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[ebotcazou at gcc dot gnu dot org]

------- Comment #5 from ebotcazou at gcc dot gnu dot org  2009-04-23 15:54 -------
> The problem is that this is such a common idiom that it will affect many
> programs.

Even worse: the folder synthesizes the problematic form from the original one.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ebotcazou at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2009-04-23 15:54:45
               date|                            |


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[paolo dot carlini at oracle dot com]

------- Comment #6 from paolo dot carlini at oracle dot com  2009-04-23 15:56 -------
:(


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[bonzini at gnu dot org]

------- Comment #8 from bonzini at gnu dot org  2009-04-23 16:10 -------
Eric, fold only does it for constant C1 and C2 in "a >= C1 && a <= C2", not for
variable C1 and C2.  in fact, in the other case it would be illegal to do the
transformation.  the front-end can do it because it knows that m->length is
positive.


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[bonzini at gnu dot org]

------- Comment #7 from bonzini at gnu dot org  2009-04-23 16:09 -------
Eric, fold only does it for a >= C1 && a <= C2, not for variable C1 and C2.  in
fact, in this case it would be illegal to do the transformation if the
front-end did not know that m->length is positive.


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[aph at gcc dot gnu dot org]

------- Comment #9 from aph at gcc dot gnu dot org  2009-04-23 16:16 -------
2 reasons:

1.  Habit.
2.  The original test case is written in Java: no unsigned types!


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[ebotcazou at gcc dot gnu dot org]

------- Comment #10 from ebotcazou at gcc dot gnu dot org  2009-04-23 16:49 -------
> Eric, fold only does it for constant C1 and C2 in "a >= C1 && a <= C2", not for
> variable C1 and C2.

Yes, but this fools VRP the same way.


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2009-04-24 09:21 -------
The folded a >= C1 && a <= C2 case is correctly handled by VRP btw (I added
that long time ago).


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[ebotcazou at gcc dot gnu dot org]

------- Comment #12 from ebotcazou at gcc dot gnu dot org  2009-04-24 16:15 -------
> The folded a >= C1 && a <= C2 case is correctly handled by VRP btw (I added
> that long time ago).

eric@atlantis:~/build/gcc/native32> cat t.c
extern void link_failure (void);

static int __attribute__ ((noinline)) foo (int x)
{
  if (x >= 1)
    if (x <= 10)
      {
        if (x < 1 || x > 10)
          link_failure ();
        x = x + 1;
      }
  return x;
}

int main (void)
{
  int i = foo (0);
  return 0;
}
eric@atlantis:~/build/gcc/native32> gcc/xgcc -Bgcc -o t t.c -O2
/tmp/ccMEXYFN.o: In function `foo':
t.c:(.text+0x24): undefined reference to `link_failure'
collect2: ld returned 1 exit status
eric@atlantis:~/build/gcc/native32>


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2009-04-24 16:41 -------
<bb 4>:
  x_11 = ASSERT_EXPR <x_13, x_13 <= 10>;
  x.0_3 = (unsigned int) x_11;
  D.1241_4 = x.0_3 + 0x0ffffffff;
  if (D.1241_4 > 9)

x.0_3: [1, 10]
D.1241_4: [0, +INF]

so it's only only the usual case of not handling overflow properly during
evaluation.  [1, 10] + -1U is [0(overflow), 9(overflow)] for VRP and so
it falls back to VARYING.  To fix this we need to know the direction
of overflow.  See also PR30318.

The patch I was refering to made VRP able to derive a range from
the D.1241_4 > 9 test.


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[rguenth at gcc dot gnu dot org]

------- Comment #14 from rguenth at gcc dot gnu dot org  2009-04-24 16:47 -------
May be worth fixing this simple case without fully fixing PR30318.  Like with

Index: tree-vrp.c
===================================================================
--- tree-vrp.c  (revision 146590)
+++ tree-vrp.c  (working copy)
@@ -2248,6 +2248,22 @@ extract_range_from_binary_expr (value_ra
         the same end of each range.  */
       min = vrp_int_const_binop (code, vr0.min, vr1.min);
       max = vrp_int_const_binop (code, vr0.max, vr1.max);
+
+      /* If both additions overflowed the range kind is still correct.
+        This happens regularly with subtracting something in unsigned
+        arithmetic.
+         ???  See PR30318 for all the cases we do not handle.  */
+      if (code == PLUS_EXPR
+         && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+         && (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+       {
+         min = build_int_cst_wide (TREE_TYPE (min),
+                                   TREE_INT_CST_LOW (min),
+                                   TREE_INT_CST_HIGH (min));
+         max = build_int_cst_wide (TREE_TYPE (max),
+                                   TREE_INT_CST_LOW (max),
+                                   TREE_INT_CST_HIGH (max));
+       }
     }
   else if (code == MULT_EXPR
           || code == TRUNC_DIV_EXPR


I am testing that patch.


-- 


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

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2009-04-23 15:54:45         |2021-6-2

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
apinski@xeond:~/src/upstream-gcc$ ~/upstream-gcc/bin/gcc -O2 t8.c -S -include
stdlib.h -o - |grep abort
apinski@xeond:~/src/upstream-gcc$ ~/upstream-gcc/bin/gcc -O2 t8.c -S -include
stdlib.h -o - -DBORKED |grep abort
        call    abort

[Bug tree-optimization/39870] VRP can't see through cast to unsigned

[rguenth at gcc dot gnu.org]

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

--- Comment #15 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-08-09 14:58:53 UTC ---
VRP optimizes the testcase form comment #12, it doesn't optimize the original
one because there we deal with symbolic ranges.