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.
Confirmed (and yes this was fixed by PtrPlus).
Exposed by: 2006-02-07 Jeff Law <law@redhat.com> Which added VRP after IV-OPTs.
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.
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.
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.
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]
SCEV shouldn't generate wrapping pointer chrecs.
Change target milestone to 4.2.3, as 4.2.2 has been released.
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
Fixed.