Between 20060207 and 20060209 the testcase started failing like this: 1.exe: /usr/src/pcarlini/gcc-head/gcc/libstdc++-v3/testsuite/25_algorithms/prev_permutation/1.cc:75: void test4(): Assertion `array[i] == 5 - i' failed. FAIL: 25_algorithms/prev_permutation/1.cc execution test Seems a miscompilation: the problem goes away at -O1. By the way, the failing test4 is pretty easy to make self contained, I'm attaching it for convenience.
Created attachment 10855 [details] Reduced failing test
This also shows up on powerpc-darwin since at least 20060208.
-O2 -fno-tree-vrp cures the wrong code which either means VRP is messing up or some other pass is messing up after VRP. Though I should note: - ivtmp.209 = ivtmp.209 - 1; + ivtmp.211 = ivtmp.211 - 1; ivtmp.214 = ivtmp.214 + 4B; - goto <bb 11> (<L22>); + if (ivtmp.211 != 4294967295) goto <L9>; else goto <L13>; Which looks more like VRP messing up.
Also -O2 -fno-ivopts cures the problem too.
Folding predicate ivtmp.209_41 != 4294967295 to 1 Folded statement: if (ivtmp.209_41 != 4294967295) goto <L24>; else goto <L13>; into: if (1) goto <L24>; else goto <L13>;
The part which is being miscompiled is: for(int i = 0; i < 6; ++i) assert(array[i] == 5 - i); which is funny.
Here is a self contained program without using libstdc++: int array[10] = {5, 4, 3, 2, 1, 0}; int array1[10] = {5, 4, 3, 2, 1, 0}; int array2[10] = {5, 4, 3, 2, 1, 0}; #include <cassert> void g(int *a) { *a = 0; } void test4() { g(array+6); for(int i = 0; i < 6; ++i) assert(array[i] == 5 - i); for(int i = 0; i < 6; ++i) { assert(array[i] == 5 - i); assert(array1[i] == 5 - i); assert(array2[i] == 5 - i); } } int main() { test4(); }
Subject: Re: [4.2 Regression] 25_algorithms/prev_permutation/1.cc on powerpc{64,}-linux and powerpc-darwin On Wed, 2006-02-15 at 15:19 +0000, pinskia at gcc dot gnu dot org wrote: > > ------- Comment #3 from pinskia at gcc dot gnu dot org 2006-02-15 15:18 ------- > -O2 -fno-tree-vrp cures the wrong code which either means VRP is messing up or > some other pass is messing up after VRP. Though I should note: > - ivtmp.209 = ivtmp.209 - 1; > + ivtmp.211 = ivtmp.211 - 1; > ivtmp.214 = ivtmp.214 + 4B; > - goto <bb 11> (<L22>); > + if (ivtmp.211 != 4294967295) goto <L9>; else goto <L13>; > > Which looks more like VRP messing up. Can you check something for me. Is sizetype an unsigned type on this platform? And what type is ivtmp? jeff
(In reply to comment #8) > > Which looks more like VRP messing up. > Can you check something for me. Is sizetype an unsigned type on > this platform? And what type is ivtmp? sizetype should be "unsigned long int" but I am not 100% sure. unsigned int ivtmp.60;
Subject: Re: [4.2 Regression] 25_algorithms/prev_permutation/1.cc on powerpc{64,}-linux and powerpc-darwin On Thu, 2006-02-16 at 02:59 +0000, pinskia at gcc dot gnu dot org wrote: > > ------- Comment #9 from pinskia at gcc dot gnu dot org 2006-02-16 02:59 ------- > (In reply to comment #8) > > > Which looks more like VRP messing up. > > Can you check something for me. Is sizetype an unsigned type on > > this platform? And what type is ivtmp? > sizetype should be "unsigned long int" but I am not 100% sure. > > unsigned int ivtmp.60; Thanks. There's a reasonable possibility this is the same bug I'm already working in. It's a latent problem in how we set up TYPE_MAX_VALUE on targets which have an unsigned sizetype. jeff
Subject: Re: [4.2 Regression] 25_algorithms/prev_permutation/1.cc on powerpc{64,}-linux and powerpc-darwin On Wed, 2006-02-15 at 15:37 +0000, pinskia at gcc dot gnu dot org wrote: > > ------- Comment #7 from pinskia at gcc dot gnu dot org 2006-02-15 15:37 ------- > Here is a self contained program without using libstdc++: > int array[10] = {5, 4, 3, 2, 1, 0}; > int array1[10] = {5, 4, 3, 2, 1, 0}; > int array2[10] = {5, 4, 3, 2, 1, 0}; > #include <cassert> > > void g(int *a) > { > *a = 0; > } > > void > test4() > { > g(array+6); > for(int i = 0; i < 6; ++i) > assert(array[i] == 5 - i); > for(int i = 0; i < 6; ++i) > { > assert(array[i] == 5 - i); > assert(array1[i] == 5 - i); > assert(array2[i] == 5 - i); > } > } > > int main() > { > test4(); I've just checked in a patch which may (or may not) fix this problem; can you update your stor-layout.c and see if that change happens to fix this problem. Thanks, jeff
(In reply to comment #11) > I've just checked in a patch which may (or may not) fix this problem; > can you update your stor-layout.c and see if that change happens to > fix this problem. Nope, sorry it does not fix the problem: - if (ivtmp.60_19 != 4294967295) goto <L5>; else goto <L13>; - -<L13>:; - return; + goto <bb 7> (<L22>); +ivtmp.60_19: [0, 4] EQUIVALENCES: { } (0 elements) the C testcase (changing cassert to assert.h) fails the same way.
Subject: Re: [4.2 Regression] 25_algorithms/prev_permutation/1.cc on powerpc{64,}-linux and powerpc-darwin On Fri, 2006-02-17 at 01:17 +0000, pinskia at gcc dot gnu dot org wrote: > > ------- Comment #12 from pinskia at gcc dot gnu dot org 2006-02-17 01:17 ------- > (In reply to comment #11) > > I've just checked in a patch which may (or may not) fix this problem; > > can you update your stor-layout.c and see if that change happens to > > fix this problem. > > Nope, sorry it does not fix the problem: > - if (ivtmp.60_19 != 4294967295) goto <L5>; else goto <L13>; > - > -<L13>:; > - return; > + goto <bb 7> (<L22>); > > > +ivtmp.60_19: [0, 4] EQUIVALENCES: { } (0 elements) > > the C testcase (changing cassert to assert.h) fails the same way. I'm pretty sure this is an SCEV problem. scev_probably_wraps_p is returning false even though the loop iteration variable clearly wraps. The iteration variable will have the values 4, 3, 2, 1, 0, 0xffffffff, then the loop terminates. This in turn causes us to use the SCEV information to refine a range improperly. Someone who knows/understands the SCEV code should be assigned this bug. jeff
Hmm, I wonder if the following loop in scev_probably_wraps_p is wrong. estimate_numbers_of_iterations_loop (loop); for (bound = loop->bounds; bound; bound = bound->next) if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) return false; it says that if one bounds does not wrap, then all variables asked about don't which is not true.
*** Bug 26911 has been marked as a duplicate of this bug. ***
I verified that the failure starts with Jeff's patch: r110705 | law | 2006-02-07 10:31:27 -0800 (Tue, 07 Feb 2006) http://gcc.gnu.org/viewcvs?view=rev&rev=110705
Rewritting that loop like: [kudzu:local/trunk/gcc] pinskia% svn diff tree-ssa-loop-niter.c Index: tree-ssa-loop-niter.c =================================================================== --- tree-ssa-loop-niter.c (revision 113199) +++ tree-ssa-loop-niter.c (working copy) @@ -1939,6 +1939,7 @@ scev_probably_wraps_p (tree type, tree b tree unsigned_type, valid_niter; tree base_plus_step, bpsps; int cps, cpsps; + bool known_not_to_wrap; /* FIXME: The following code will not be used anymore once http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is @@ -2077,8 +2078,10 @@ scev_probably_wraps_p (tree type, tree b estimate_numbers_of_iterations_loop (loop); for (bound = loop->bounds; bound; bound = bound->next) - if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) - return false; + if (!proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) + known_not_to_wrap = false; + if (known_not_to_wrap) + return false; /* At this point we still don't have a proof that the iv does not overflow: give up. */ ---------------------------- Makes it work, Now I am not going to say this is the "correct" fix or not. What I am going to say, this is the most logical fix in that we know one iv can not overflow does not mean all will not.
Oh, I did not test the patch at all except on the testcase I gave in comment #7.
Subject: Re: [4.2 Regression] 25_algorithms/prev_permutation/1.cc on powerpc{64,}-linux and powerpc-darwin On Sun, 2006-04-23 at 23:14 +0000, pinskia at gcc dot gnu dot org wrote: > > ------- Comment #17 from pinskia at gcc dot gnu dot org 2006-04-23 23:14 ------- > Rewritting that loop like: > [kudzu:local/trunk/gcc] pinskia% svn diff tree-ssa-loop-niter.c > Index: tree-ssa-loop-niter.c > =================================================================== > --- tree-ssa-loop-niter.c (revision 113199) > +++ tree-ssa-loop-niter.c (working copy) > @@ -1939,6 +1939,7 @@ scev_probably_wraps_p (tree type, tree b > tree unsigned_type, valid_niter; > tree base_plus_step, bpsps; > int cps, cpsps; > + bool known_not_to_wrap; > > /* FIXME: The following code will not be used anymore once > http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02025.html is > @@ -2077,8 +2078,10 @@ scev_probably_wraps_p (tree type, tree b > > estimate_numbers_of_iterations_loop (loop); > for (bound = loop->bounds; bound; bound = bound->next) > - if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) > - return false; > + if (!proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) > + known_not_to_wrap = false; > + if (known_not_to_wrap) > + return false; > > /* At this point we still don't have a proof that the iv does not > overflow: give up. */ > known_to_wrap may be uninitialized at the if statement here. You need to init it to true.
The code which I replaced here is changed.
This still fails even after the code change. CCing the person who changed the code: http://gcc.gnu.org/ml/gcc-cvs/2006-05/msg00024.html
(In reply to comment #14) > Hmm, I wonder if the following loop in scev_probably_wraps_p is wrong. > > estimate_numbers_of_iterations_loop (loop); > for (bound = loop->bounds; bound; bound = bound->next) > if (proved_non_wrapping_p (at_stmt, bound, type, valid_niter)) > return false; > > it says that if one bounds does not wrap, then all variables asked about don't > which is not true. this piece of code seems OK to me (modulo that proved_non_wrapping_p was quite missleading way to name that function). What it does is that we know that the loop is executed at most BOUND times, and that the variable will not wrap for at least VALID_NITER iterations; therefore, if we are able to prove that VALID_NITER > BOUND for any of the bounds, we know that the variable does not wrap. There is probaby off-by-one error in one of the functions.
Somehow, we record that the loop iterates at most once, which obviously leads to problems.
Patch: http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00290.html
This was fixed by the patch for PR 27603. *** This bug has been marked as a duplicate of 27603 ***