GCC Bugzilla – Bug 27039
[4.1 Regression] Unable to determine # of iterations for a simple loop
Last modified: 2008-07-04 15:27:09 UTC
With the fix for PR 26763, we are unable to determine # of iterations of the following loop, more precisely, we are unable to determine that it rolls -- for that, we would need to fold p_4 + 4B > p_4 + 8B. int foo (int *p) { int i = 0, *x; for (x = p; x < p + 2; x++) i++; return i; }
Confirmed. That gives us a testcase at least. Now, back to the folding problem of PTR +- CST CMP PTR +- CST where all of PTR / CST are of pointer type naturally and unsigned usually. The problem was that the frontends/middle-end introduce pointer overflow via presenting us with PTR + (unsigned)-CST. Now, we may argue that if (signed)CST is positive, that this didn't happen, and we can do the comparison in either signed or unsigned mode. Of course this won't help for p - 4 < p + 4, because this is exactly where the above condition would trigger. Does this sound reasonable? Can anyone punch a hole in this argument?
Subject: Re: Unable to determine # of iterations for a simple loop > Confirmed. That gives us a testcase at least. > > Now, back to the folding problem of > > PTR +- CST CMP PTR +- CST > > where all of PTR / CST are of pointer type naturally and unsigned usually. > The problem was that the frontends/middle-end introduce pointer overflow via > presenting us with PTR + (unsigned)-CST. Now, we may argue that if (signed)CST > is positive, that this didn't happen, and we can do the comparison in either > signed or unsigned mode. If p points to the end of the array whose size is more than range of signed, then this would make you mistakenly consider p - size > p.
Subject: Re: [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop On Wed, 5 Apr 2006, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote: > Subject: Re: Unable to determine # of iterations for a simple loop > > > Confirmed. That gives us a testcase at least. > > > > Now, back to the folding problem of > > > > PTR +- CST CMP PTR +- CST > > > > where all of PTR / CST are of pointer type naturally and unsigned usually. > > The problem was that the frontends/middle-end introduce pointer overflow via > > presenting us with PTR + (unsigned)-CST. Now, we may argue that if (signed)CST > > is positive, that this didn't happen, and we can do the comparison in either > > signed or unsigned mode. > > If p points to the end of the array whose size is more than range of > signed, then this would make you mistakenly consider p - size > p. Umm. Correct :/ I guess the only way to "fix" the mess is to make the frontends _not_ generate these spurious pointer overflows in the first place. Like I asked for in http://gcc.gnu.org/ml/gcc/2006-03/msg00866.html where nobody commented. :/
Subject: Re: [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop > > > Confirmed. That gives us a testcase at least. > > > > > > Now, back to the folding problem of > > > > > > PTR +- CST CMP PTR +- CST > > > > > > where all of PTR / CST are of pointer type naturally and unsigned usually. > > > The problem was that the frontends/middle-end introduce pointer overflow via > > > presenting us with PTR + (unsigned)-CST. Now, we may argue that if (signed)CST > > > is positive, that this didn't happen, and we can do the comparison in either > > > signed or unsigned mode. > > > > If p points to the end of the array whose size is more than range of > > signed, then this would make you mistakenly consider p - size > p. > > Umm. Correct :/ I guess the only way to "fix" the mess is to make the > frontends _not_ generate these spurious pointer overflows in the first > place. Like I asked for in > > http://gcc.gnu.org/ml/gcc/2006-03/msg00866.html > > where nobody commented. :/ the problem is that it is a bit hard to avoid this. What code should we produce for signed i; char *x; x + i? In order to avoid overflows when the addition is casted to an unsigned type, we would have to translate it to (i < 0) ? x - (char *) (-i) : x + (char *) i, which would be really bad.
Subject: Re: [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop On Wed, 5 Apr 2006, rakdver at atrey dot karlin dot mff dot cuni dot cz wrote: > > Umm. Correct :/ I guess the only way to "fix" the mess is to make the > > frontends _not_ generate these spurious pointer overflows in the first > > place. Like I asked for in > > > > http://gcc.gnu.org/ml/gcc/2006-03/msg00866.html > > > > where nobody commented. :/ > > the problem is that it is a bit hard to avoid this. What code should we > produce for > > signed i; > char *x; > > x + i? > > In order to avoid overflows when the addition is casted to an > unsigned type, we would have to translate it to > (i < 0) ? x - (char *) (-i) : x + (char *) i, > which would be really bad. At the moment the C frontend does in the x + i case x + (char *)(size_t)i so, now this would be problematic for x + i < x which would then become (effectively) (size_t)i < 0 which is false even for negative i. Now, the frontend makes it worse, because for constant offsets I believe we _can_ fold if we know the constant didn't overflow. I.e. at the moment for x - 1 we get x + (char *)(size_t)-1 which is bad, instead x - (char *)(size_t)1 would be much better here. The question is of course, if the programmer is allowed to write x + (size_t)-1 and expect the result to be defined.
Subject: Re: [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop > would be much better here. The question is of course, if the programmer > is allowed to write > > x + (size_t)-1 > > and expect the result to be defined. if I understand the C standard correctly, no, this has undefined behavior.
Subject: Re: [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop > > would be much better here. The question is of course, if the programmer > > is allowed to write > > > > x + (size_t)-1 > > > > and expect the result to be defined. > > if I understand the C standard correctly, no, this has undefined behavior. This is also my understanding, so we should try to avoid creating the above in the frontends. But of course, as discussed, this doesn't solve the problem (does it, for constant offsets?).
Wording of 6.5.6/8 and /9 suggests that array objects larger than the maximum value that fits in ptrdiff_t (which needs to be signed) invoke undefined behavior, not last because of "the expression ((Q)+1)-(P) has the same value as ((Q)-(P))+1 and as -((P)-((Q)+1))" and "The size of the result is implementation-defined, and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> header. If the result is not representable in an object of that type, the behavior is undefined." So for this reason I believe that folding PTR +- CST CMP PTR +- CST (with CST being of pointer type, as represented by the middle-end) as +- (ptrdiff_t)CST CMP +- (ptrdiff_t)CST is valid. Now the intel compiler f.i. does _not_ do this.
Subject: Re: [4.1/4.2 Regression] Unable to determine # of iterations for a simple loop > Wording of 6.5.6/8 and /9 suggests that array objects larger than the maximum > value that fits in ptrdiff_t (which needs to be signed) invoke undefined > behavior, > not last because of "the expression ((Q)+1)-(P) has the same value as > ((Q)-(P))+1 and as -((P)-((Q)+1))" and "The size of the result is > implementation-defined, > and its type (a signed integer type) is ptrdiff_t defined in the <stddef.h> > header. If the result is not representable in an object of that type, the > behavior is undefined." However, this only concerns difference of pointers. In particular, the way semantics of comparison of pointers is defined in 6.5.8/5 does make no reference to the difference of pointers, and it is well defined even for objects whose size does not fit into ptrdiff_t. Gcc actually does not allow arrays whose size does not fit into ptrdiff_t, so the problem might only appear for malloc-ated objects. But perhaps it is allowed to actually not support such large objects; I think we should just submit patch for the transformation as described below, and let someone with better knowledge of the standards decide whether this is correct or not. > So for this reason I believe that folding > > PTR +- CST CMP PTR +- CST > > (with CST being of pointer type, as represented by the middle-end) as > > +- (ptrdiff_t)CST CMP +- (ptrdiff_t)CST > > is valid. Now the intel compiler f.i. does _not_ do this.
I have a patch that needs PR27529 fixed first, that needs PR27532 fixed first.
Subject: Bug number PR27039 A patch for this bug has been added to the patch tracker. The mailing list url for the patch is http://gcc.gnu.org/ml/gcc-patches/2006-05/msg00452.html
Will not be fixed in 4.1.1; adjust target milestone to 4.1.2.
Subject: Bug 27039 Author: rguenth Date: Sun Jun 4 12:59:40 2006 New Revision: 114357 URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=114357 Log: 2006-06-04 Richard Guenther <rguenther@suse.de> PR tree-optimization/27039 * fold-const.c (fold_comparison): Handle pointer comparison again for all comparison codes. Compare offsets in signed size type. (fold_binary): Move code from here. * gcc.dg/tree-ssa/loop-17.c: New testcase. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-17.c Modified: trunk/gcc/ChangeLog trunk/gcc/fold-const.c trunk/gcc/testsuite/ChangeLog
Fixed on the mainline.
Closing 4.1 branch.