public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug tree-optimization/33099]  New: Scalar evolutions confusing VRP with pointer values that wrap around
@ 2007-08-17 19:47 dnovillo at gcc dot gnu dot org
  2007-08-17 20:19 ` [Bug tree-optimization/33099] [4.2 Regression] " pinskia at gcc dot gnu dot org
                   ` (11 more replies)
  0 siblings, 12 replies; 13+ messages in thread
From: dnovillo at gcc dot gnu dot org @ 2007-08-17 19:47 UTC (permalink / raw)
  To: gcc-bugs

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


^ permalink raw reply	[flat|nested] 13+ messages in thread
end of thread, other threads:[~2007-10-10  9:25 UTC | newest]

Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-08-17 19:47 [Bug tree-optimization/33099] New: Scalar evolutions confusing VRP with pointer values that wrap around dnovillo at gcc dot gnu dot org
2007-08-17 20:19 ` [Bug tree-optimization/33099] [4.2 Regression] " pinskia at gcc dot gnu dot org
2007-08-17 20:21 ` pinskia at gcc dot gnu dot org
2007-08-17 20:28 ` dnovillo at google dot com
2007-08-17 20:34 ` pinskia at gcc dot gnu dot org
2007-08-17 20:38 ` dnovillo at google dot com
2007-08-17 20:43 ` pinskia at gcc dot gnu dot org
2007-08-18 13:55 ` rguenth at gcc dot gnu dot org
2007-09-05  1:05 ` mmitchel at gcc dot gnu dot org
2007-09-21 13:55 ` rguenth at gcc dot gnu dot org
2007-10-09 19:27 ` mmitchel at gcc dot gnu dot org
2007-10-10  9:25 ` rguenth at gcc dot gnu dot org
2007-10-10  9:25 ` rguenth at gcc dot gnu dot org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).