[Bug tree-optimization/33099] New: Scalar evolutions confusing VRP with pointer values that wrap around

[Bug tree-optimization/33099] New: Scalar evolutions confusing VRP with pointer values that wrap around

[dnovillo at gcc dot gnu dot org]

The following test case is miscompiled with GCC 4.2:

extern void abort (void);

volatile int N = 5;

void foo (void)
{
  int i;
  char *p, value[10];

  value[0] = 0x42;
  for (i = 0; i < N; i++)
    if (i > 0)
      {
        p = (char *)i - 1;
        *(value + (int) p) = (char) i;
      }

  if (value[0] != 1)
    abort ();
}

main()
{
  foo ();
  return 0;
}

$ gcc --version
gcc (GCC) 4.2.2 20070816 (prerelease)
Copyright (C) 2007 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

$ gcc -O2 -o a a.c
$ ./a
Aborted (core dumped)

This was originally a C++ program which I converted into this C snippet from
GIMPLE.  I believe it's valid C, but I am not actually sure.  The original C++
code *is* valid, though.

The problem here starts in tree-vrp.c:adjust_range_with_scev() when we ask for
the scalar evolution of p_8 in the loop

<L0>:;
  i_24 = ASSERT_EXPR <i_1, i_1 < N.1_6>;
  if (i_24 > 0) goto <L1>; else goto <L7>;
[ ... ]
<L1>:;
  i_4 = ASSERT_EXPR <i_24, i_24 > 0>;
  i.0_7 = (char *) i_4;
  p_8 = i.0_7 - 1B;

[...]

<L2>:;
  i_11 = i_24 + 1;
  # i_1 = PHI <0(2), i_11(5)>;
<L3>:;
  if (i_1 < N.1_6) goto <L0>; else goto <L4>;

The call to analyze_scalar_evolution(loop, p_8) returns the chrec {-1B, +, 1B}
which is more or less understandable because the initial value i.0_7 can be
traced all the way back to the start of the loop to 0.

However:

1- SCEV has not realized that there is an ASSERT_EXPR in the path.  The initial
value of i.0_7 is actually 1, not 0.

2- When VRP sees the chrec {-1B, +, 1B} it asks whether it may wrap.  Since we
assumes that pointers never wrap, scev_probably_wraps_p returns false.  Which
is understandable, I guess, but in this case we get burnt by the logic that
follows in adjust_range_with_scev:

  * Since the range we have is VARYING, we take the initial value of the given
chrec and set it as the min value for the range.  So, the minimum value for the
new range is set to -1B.

  * Since the scalar evolution goes forward, we set the maximum value to the
max value for the type (upper_bound_in_type).  Which also happens to be -1B.

  * So, we end up with the range [-1B, -1B] which we later propagate into the
pointer dereference, causing the failure.

This problem does not happen in mainline because of the PTR_PLUS_EXPR cleanup.
Pointer arithmetic uses unsigned types and all this is avoided.

I think that the core problem is that we are tripping over the fact that while
we don't consider pointers to wrap, the instantiation of the chrec is giving
wrapped-around pointer values.  This confuses VRP.

So far, I see the following options for fixing this:

1- Teach SCEV that subtracting pointer values from 0 yields an unkown
chrec.  Similarly, adding to upper_bound_in_type will yield an unkown
chrec.  What's the wording in the standard wrt pointer arithmetic?  Is
the following undefined, implementation defined, or valid?

        char *p = 0;
        --p;
        *p = 'x';

2- Teach SCEV about ASSERT_EXPRs when instantiating chrecs.  Would
benefit both mainline and 4.2.  May hide other bugs that occur when
there are no assertions around. But that's unlikely.

3- Tell VRP to refuse to do anything with pointer chrecs that have a constant
initial value.  This may prove suboptimal in some cases where we could've
gotten a good range, but they should be few and far between.

4- In mainline, the representation of pointer arithmetic has been
cleaned up considerably with the PTR_PLUS_EXPR patches.  Bringing those
in to 4.2 is IMO out of the question because of the sheer invasiveness.
But if the problem was widespread enough maybe we could consider it.  I
don't think it is, though.


-- 
           Summary: Scalar evolutions confusing VRP with pointer values that
                    wrap around
           Product: gcc
           Version: 4.2.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dnovillo at gcc dot gnu dot org


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2007-08-17 20:18 -------
Confirmed (and yes this was fixed by PtrPlus).


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
      Known to fail|                            |4.2.1
      Known to work|                            |4.3.0 4.1.1
   Last reconfirmed|0000-00-00 00:00:00         |2007-08-17 20:18:57
               date|                            |
            Summary|Scalar evolutions confusing |[4.2 Regression] Scalar
                   |VRP with pointer values that|evolutions confusing VRP
                   |wrap around                 |with pointer values that
                   |                            |wrap around
   Target Milestone|---                         |4.2.2


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2007-08-17 20:20 -------
Exposed by:
2006-02-07  Jeff Law  <law@redhat.com>


Which added VRP after IV-OPTs.


-- 

pinskia at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[dnovillo at google dot com]

------- Comment #3 from dnovillo at google dot com  2007-08-17 20:27 -------
Subject: Re:  [4.2 Regression] Scalar evolutions
 confusing VRP with pointer values that wrap around

On 8/17/07 4:20 PM, pinskia at gcc dot gnu dot org wrote:
> ------- Comment #2 from pinskia at gcc dot gnu dot org  2007-08-17 20:20 -------
> Exposed by:
> 2006-02-07  Jeff Law  <law@redhat.com>
> 
> 
> Which added VRP after IV-OPTs.

No, no that is completely unrelated.  This happens in the first VRP
pass.  It's all inside adjust_range_with_scev which specifically calls
scalar evolutions code.


-- 


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[pinskia at gcc dot gnu dot org]

------- Comment #4 from pinskia at gcc dot gnu dot org  2007-08-17 20:34 -------
Oh you are correct but this still worked in 4.1.1 though, I have not looked
into what changed between 4.1.1 and 4.2.0 with respect of scev yet.


-- 

pinskia at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[dnovillo at google dot com]

------- Comment #5 from dnovillo at google dot com  2007-08-17 20:37 -------
Subject: Re:  [4.2 Regression] Scalar evolutions
 confusing VRP with pointer values that wrap around

On 8/17/07 4:34 PM, pinskia at gcc dot gnu dot org wrote:
> ------- Comment #4 from pinskia at gcc dot gnu dot org  2007-08-17 20:34 -------
> Oh you are correct but this still worked in 4.1.1 though, I have not looked
> into what changed between 4.1.1 and 4.2.0 with respect of scev yet.

Since you are looking, two things to check for: (1) IL representation
for the pointer subtraction, and (2) SCEV may have returned an unknown
chrec back in 4.1.  Or maybe we still didn't consider pointers to not-wrap.


-- 


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2007-08-17 20:42 -------
The IR is the same but scev did something different:
Visiting statement:
p_10 = i.0_9 - 1B;

(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = p_10)
(get_scalar_evolution 
  (scalar = p_10)
  (scalar_evolution = ))
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i.0_9)
(get_scalar_evolution 
  (scalar = i.0_9)
  (scalar_evolution = {0B, +, 1B}_1))
(set_scalar_evolution 
  (scalar = i.0_9)
  (scalar_evolution = {0B, +, 1B}_1))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = 1B)
(get_scalar_evolution 
  (scalar = 1B)
  (scalar_evolution = 1B))
)
(set_scalar_evolution 
  (scalar = p_10)
  (scalar_evolution = {4294967295B, +, 1B}_1))
)
(instantiate_parameters 
  (loop_nb = 1)
  (chrec = {4294967295B, +, 1B}_1)
  (res = {4294967295B, +, 1B}_1))
Found new range for p_10: VARYING

vs (in 4.2):
 Visiting statement:
i.0_4 = (char *) i_23;

(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i.0_4)
(get_scalar_evolution 
  (scalar = i.0_4)
  (scalar_evolution = ))
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i_23)
(get_scalar_evolution 
  (scalar = i_23)
  (scalar_evolution = {0, +, 1}_1))
(set_scalar_evolution 
  (scalar = i_23)
  (scalar_evolution = {0, +, 1}_1))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i_1)
(get_scalar_evolution 
  (scalar = i_1)
  (scalar_evolution = {0, +, 1}_1))
(set_scalar_evolution 
  (scalar = i_1)
  (scalar_evolution = {0, +, 1}_1))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = N.1_3)
(get_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = ))
(set_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = N.1_3)
(get_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
(set_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = N.1_3)
(get_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
(set_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
)
(instantiate_parameters 
  (loop_nb = 1)
  (chrec = N.1_3)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = N.1_3)
(get_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
(set_scalar_evolution 
  (scalar = N.1_3)
  (scalar_evolution = N.1_3))
)
  (res = scev_not_known))
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i_8)
(get_scalar_evolution 
  (scalar = i_8)
  (scalar_evolution = ))
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i_25)
(get_scalar_evolution 
  (scalar = i_25)
  (scalar_evolution = {0, +, 1}_1))
(set_scalar_evolution 
  (scalar = i_25)
  (scalar_evolution = {0, +, 1}_1))
)
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = 1)
(get_scalar_evolution 
  (scalar = 1)
  (scalar_evolution = 1))
)
(set_scalar_evolution 
  (scalar = i_8)
  (scalar_evolution = {1, +, 1}_1))
)
(instantiate_parameters 
  (loop_nb = 1)
  (chrec = {1, +, 1}_1)
  (res = {1, +, 1}_1))
Induction variable (int) 1 + 1 * iteration does not wrap in statement i_8 =
i_25 + 1 in loop 1.
Statement i_8 = i_25 + 1 is executed at most 2147483646 (bounded by 2147483646)
+ 1 times in loop 1.
(analyze_scalar_evolution 
  (loop_nb = 1)
  (scalar = i_25)
(get_scalar_evolution 
  (scalar = i_25)
  (scalar_evolution = {0, +, 1}_1))
(set_scalar_evolution 
  (scalar = i_25)
  (scalar_evolution = {0, +, 1}_1))
)
(instantiate_parameters 
  (loop_nb = 1)
  (chrec = {0, +, 1}_1)
  (res = {0, +, 1}_1))
Induction variable (int) 0 + 1 * iteration does not wrap in statement i_25 =
ASSERT_EXPR <i_1, i_1 < N.1_3> in loop 1.
Statement i_25 = ASSERT_EXPR <i_1, i_1 < N.1_3> is executed at most 2147483647
(bounded by 2147483647) + 1 times in loop 1.
(set_scalar_evolution 
  (scalar = i.0_4)
  (scalar_evolution = {0B, +, 1B}_1))
)
(instantiate_parameters 
  (loop_nb = 1)
  (chrec = {0B, +, 1B}_1)
  (res = {0B, +, 1B}_1))
Found new range for i.0_4: [0B, -1B]


-- 


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2007-08-18 13:55 -------
SCEV shouldn't generate wrapping pointer chrecs.


-- 

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=33099

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[mmitchel at gcc dot gnu dot org]

-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[rguenth at gcc dot gnu dot org]

-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-08-17 20:18:57         |2007-09-21 13:55:36
               date|                            |


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[mmitchel at gcc dot gnu dot org]

------- Comment #8 from mmitchel at gcc dot gnu dot org  2007-10-09 19:20 -------
Change target milestone to 4.2.3, as 4.2.2 has been released.


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.2                       |4.2.3


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2007-10-10 09:25 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/33099] [4.2 Regression] Scalar evolutions confusing VRP with pointer values that wrap around

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2007-10-10 09:24 -------
Subject: Bug 33099

Author: rguenth
Date: Wed Oct 10 09:24:43 2007
New Revision: 129197

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=129197
Log:
2007-10-10  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/33099
        PR tree-optimization/33381
        * tree-vrp.c (adjust_range_with_scev): Do not adjust ranges
        from pointer typed chrecs.

        * gcc.c-torture/execute/pr33099.c: New testcase.
        * gcc.c-torture/execute/pr33381.c: Likewise.

Added:
    branches/gcc-4_2-branch/gcc/testsuite/gcc.c-torture/execute/pr33099.c
    branches/gcc-4_2-branch/gcc/testsuite/gcc.c-torture/execute/pr33381.c
Modified:
    branches/gcc-4_2-branch/gcc/ChangeLog
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_2-branch/gcc/tree-vrp.c


-- 


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