| Message ID | alpine.LNX.2.00.1108311055480.2130@zhemvz.fhfr.qr |
|---|---|
| State | New |
| Headers | show |
> Well, the comment for that folding is totally odd - of _course_ > unsigned sizetype things can overflow (we hid that issue merely > by pretending all unsigned sizetype constants (yes, only constants) > are signed. Huh.) It's again the special semantics of sizetypes whereby we pretend that they don't overflow. I know your opinion about this, but this is documented: /* In an INTEGER_TYPE, it means the type represents a size. We use this both for validity checking and to permit optimizations that are unsafe for other types. Note that the C `size_t' type should *not* have this flag set. The `size_t' type is simply a typedef for an ordinary integer type that happens to be the type of an expression returned by `sizeof'; `size_t' has no special properties. Expressions whose type have TYPE_IS_SIZETYPE set are always actual sizes. */ #define TYPE_IS_SIZETYPE(NODE) \ (INTEGER_TYPE_CHECK (NODE)->type_common.no_force_blk_flag) and we rely on these optimizations to simplify size computations in Ada. > 2011-08-31 Richard Guenther <rguenther@suse.de> > > * fold-const.c (extract_muldiv_1): Remove bogus TYPE_IS_SIZETYPE > special-casing. IMO you shouldn't commit this kind of patchlets without the final big patch.
On Fri, 2 Sep 2011, Eric Botcazou wrote: > > Well, the comment for that folding is totally odd - of _course_ > > unsigned sizetype things can overflow (we hid that issue merely > > by pretending all unsigned sizetype constants (yes, only constants) > > are signed. Huh.) > > It's again the special semantics of sizetypes whereby we pretend that they > don't overflow. I know your opinion about this, but this is documented: But they _do_ overflow as my debugging showed, caused by that exact same extract_muldiv_1 function here: case PLUS_EXPR: case MINUS_EXPR: /* See if we can eliminate the operation on both sides. If we can, we can return a new PLUS or MINUS. If we can't, the only remaining cases where we can do anything are if the second operand is a constant. */ ... /* If this was a subtraction, negate OP1 and set it to be an addition. This simplifies the logic below. */ if (tcode == MINUS_EXPR) { tcode = PLUS_EXPR, op1 = negate_expr (op1); the unconditional negation of op1 for tcode == MINUS_EXPR overflows all sizetype values (well, all unsigned values). So you might argue I should have fixed the "bug" here instead of removing a TYPE_IS_SIZETYPE check (which I very much like to do, as you know ;)). > /* In an INTEGER_TYPE, it means the type represents a size. We use > this both for validity checking and to permit optimizations that > are unsafe for other types. Note that the C `size_t' type should > *not* have this flag set. The `size_t' type is simply a typedef > for an ordinary integer type that happens to be the type of an > expression returned by `sizeof'; `size_t' has no special > properties. Expressions whose type have TYPE_IS_SIZETYPE set are > always actual sizes. */ > #define TYPE_IS_SIZETYPE(NODE) \ > (INTEGER_TYPE_CHECK (NODE)->type_common.no_force_blk_flag) Well, this only says "and to permit optimizations that are unsafe for other types." but it doesn't say what constraints apply to sizetypes. We can't at the same time possibly introduce overflow and rely on no overflow at the same time. > and we rely on these optimizations to simplify size computations in Ada. Please please add some _testcases_ then that would fail when I test this kind of patches. > > 2011-08-31 Richard Guenther <rguenther@suse.de> > > > > * fold-const.c (extract_muldiv_1): Remove bogus TYPE_IS_SIZETYPE > > special-casing. > > IMO you shouldn't commit this kind of patchlets without the final big patch. The patch fixed a real bug (it's just that it is hard (for me) to produce testcases that involve sizetype computations - it always requires Ada to expose those bugs). So, I beg to differ. Richard.
> But they _do_ overflow as my debugging showed, caused by that exact > same extract_muldiv_1 function here: > > case PLUS_EXPR: case MINUS_EXPR: > /* See if we can eliminate the operation on both sides. If we can, > we > can return a new PLUS or MINUS. If we can't, the only remaining > cases where we can do anything are if the second operand is a > constant. */ > ... > /* If this was a subtraction, negate OP1 and set it to be an > addition. > This simplifies the logic below. */ > if (tcode == MINUS_EXPR) > { > tcode = PLUS_EXPR, op1 = negate_expr (op1); > > the unconditional negation of op1 for tcode == MINUS_EXPR overflows > all sizetype values (well, all unsigned values). Only if sizetypes are no longer sign-extended, though; otherwise, I don't see the problem (and we certainly never detected one). Does something really go wrong with the unpatched compiler? > Please please add some _testcases_ then that would fail when I test > this kind of patches. Performance testcases are hard to extract beforehand. It's only when you have a regression that you really start to dig. > The patch fixed a real bug (it's just that it is hard (for me) to > produce testcases that involve sizetype computations - it always > requires Ada to expose those bugs). So, I beg to differ. Well, on the one hand you ask for testcases in difficult cases, and on the other hand you don't provide one when you already have something at hand. The elimination of the sign-extension for sizetypes is probably a progress overall, although this will very likely cause a few problems in Ada. But removing working code (albeit admittedly hard to grasp) without testcases or real experiments is a different thing.
On Fri, 2 Sep 2011, Eric Botcazou wrote: > > But they _do_ overflow as my debugging showed, caused by that exact > > same extract_muldiv_1 function here: > > > > case PLUS_EXPR: case MINUS_EXPR: > > /* See if we can eliminate the operation on both sides. If we can, > > we > > can return a new PLUS or MINUS. If we can't, the only remaining > > cases where we can do anything are if the second operand is a > > constant. */ > > ... > > /* If this was a subtraction, negate OP1 and set it to be an > > addition. > > This simplifies the logic below. */ > > if (tcode == MINUS_EXPR) > > { > > tcode = PLUS_EXPR, op1 = negate_expr (op1); > > > > the unconditional negation of op1 for tcode == MINUS_EXPR overflows > > all sizetype values (well, all unsigned values). > > Only if sizetypes are no longer sign-extended, though; otherwise, I don't see > the problem (and we certainly never detected one). Does something really go > wrong with the unpatched compiler? Well, even when sign-extended there is a constant you can't negate without overflow. I would start digging for a testcase with such case - but as said, testcases involving TYPE_IS_SIZETYPE are very hard to generate for me. > > Please please add some _testcases_ then that would fail when I test > > this kind of patches. > > Performance testcases are hard to extract beforehand. It's only when you have > a regression that you really start to dig. Well, but I'd expect you can have a set of Ada types, a function that returns just its size and some scan-tree-dumps that check those sizes are folded to a constant. Or to just N statements. I at least did verify that the case producing the error still folds to a constant size, even after my patch. > > The patch fixed a real bug (it's just that it is hard (for me) to > > produce testcases that involve sizetype computations - it always > > requires Ada to expose those bugs). So, I beg to differ. > > Well, on the one hand you ask for testcases in difficult cases, and on the > other hand you don't provide one when you already have something at hand. > > The elimination of the sign-extension for sizetypes is probably a progress > overall, although this will very likely cause a few problems in Ada. But > removing working code (albeit admittedly hard to grasp) without testcases or > real experiments is a different thing. It definitely makes it easier to later point to this patch causing issues compared to lumping all the "fixes" into the final patch, which, btw. I just sent out. If you insist I can revert the patch and apply it together with the sign-extension change. Richard.
> Well, even when sign-extended there is a constant you can't negate > without overflow. I would start digging for a testcase with > such case - but as said, testcases involving TYPE_IS_SIZETYPE are > very hard to generate for me. We run thousands of Ada tests every night on many platforms and never detected a problem here, so finding a testcase with the unpatched compiler is probably very hard - if there is really something to be found, which I doubt. > Well, but I'd expect you can have a set of Ada types, a function that > returns just its size and some scan-tree-dumps that check those sizes > are folded to a constant. Or to just N statements. We probably should, but we don't have them (yet). Like for the vast majority of the transformations made by the folder I guess, so... > If you insist I can revert the patch and apply it together with the > sign-extension change. Yes, IMHO it should be part of the final patch.
On Sat, Sep 3, 2011 at 11:24 AM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> Well, even when sign-extended there is a constant you can't negate >> without overflow. I would start digging for a testcase with >> such case - but as said, testcases involving TYPE_IS_SIZETYPE are >> very hard to generate for me. > > We run thousands of Ada tests every night on many platforms and never detected > a problem here, so finding a testcase with the unpatched compiler is probably > very hard - if there is really something to be found, which I doubt. Well, for real-world code I believe that. But see all the recent testcases for corner-cases of our signed-overflow stuff, they all require hand-crafted testcases involving INT_MIN, no inlining and even -ftrapv. What I meant to say is, given Ada can construct arbitrary layouted types it should be possible to have testcases for all the corner-cases - after all you cannot have both, undefined overflow and wrapping overflow, at the same time. That extract_muldiv_1 code is wrong for TYPE_OVERFLOW_UNDEFINED types as well, btw. >> Well, but I'd expect you can have a set of Ada types, a function that >> returns just its size and some scan-tree-dumps that check those sizes >> are folded to a constant. Or to just N statements. > > We probably should, but we don't have them (yet). Like for the vast majority > of the transformations made by the folder I guess, so... > >> If you insist I can revert the patch and apply it together with the >> sign-extension change. > > Yes, IMHO it should be part of the final patch. Ok, I'll revert it on monday. Richard. > -- > Eric Botcazou >
> Well, for real-world code I believe that. But see all the recent testcases > for corner-cases of our signed-overflow stuff, they all require > hand-crafted testcases involving INT_MIN, no inlining and even -ftrapv. > What I meant to say is, given Ada can construct arbitrary layouted types it > should be possible to have testcases for all the corner-cases - after all > you cannot have both, undefined overflow and wrapping overflow, at the same > time. Don't forget that we pretend that sizetypes don't overflow; in other words, we don't support arbitrarily-sized types, so no INT_MAX or something like that. > Ok, I'll revert it on monday. Thanks. I'll give the complete patch a try on our internal testsuite.
On Sat, Sep 3, 2011 at 5:08 PM, Eric Botcazou <ebotcazou@adacore.com> wrote: >> Well, for real-world code I believe that. But see all the recent testcases >> for corner-cases of our signed-overflow stuff, they all require >> hand-crafted testcases involving INT_MIN, no inlining and even -ftrapv. >> What I meant to say is, given Ada can construct arbitrary layouted types it >> should be possible to have testcases for all the corner-cases - after all >> you cannot have both, undefined overflow and wrapping overflow, at the same >> time. > > Don't forget that we pretend that sizetypes don't overflow; in other words, we > don't support arbitrarily-sized types, so no INT_MAX or something like that. I know what we "pretend", but "pretending" is far from a rigorous specification of behavior. What's the range of valid sizes we support? Are all sizetype (sub-)expressions always of value in that range? What do we do about the fact that sizetype is unsigned, so -x always overflows for x != 0? Thus, do we need to disable all a - b -> a + -b kind of foldings for sizetypes? (we don't) What I see we pretend is that "sizetype" is supposed to be of infinite precision (well, infinite "enugh" to handle all (sub-)expressions of sizetype that may occur). An unsigned type isn't well-suited for that, of course. A type that is of the same precision as pointers possibly neither, considering sub-expressions. Given the restriction we impose in the C fronted (objects can be max convering half of the address-space) making all sizetypes signed would probably make sense (but that isn't easy, I've tried that already - keeping them unsigned but no longer sign-extending was way easier ;)) >> Ok, I'll revert it on monday. > > Thanks. I'll give the complete patch a try on our internal testsuite. Thanks. I'll expect some fallout. Richard. > -- > Eric Botcazou >
Let me jump in on this a little bit, since much of the code in this area was originally written by me. > Are all sizetype (sub-)expressions always of value in that range? > What do we do about the fact that sizetype is unsigned, so -x always > overflows for x != 0? Thus, do we need to disable all a - b -> a + > -b kind of foldings for sizetypes? (we don't) The basic idea is that an overflow of sizetype is either: (1) Detected at a higher level (e.g., testing for maximum sizes of objects) or; (2) Is an undetected error and hence the result of such overflow is undefined. What this means from a practical point of view (but indeed a bit hard to define from a formal point of view) is that the normal addition and subtraction operations (on a 2's complement machines, which all are now) will "do the right thing" in all cases so we can perform all those sorts of folding operations.
On Sat, Sep 3, 2011 at 9:47 PM, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote: > Let me jump in on this a little bit, since much of the code in this area > was originally written by me. > >> Are all sizetype (sub-)expressions always of value in that range? >> What do we do about the fact that sizetype is unsigned, so -x always >> overflows for x != 0? Thus, do we need to disable all a - b -> a + >> -b kind of foldings for sizetypes? (we don't) > > The basic idea is that an overflow of sizetype is either: > > (1) Detected at a higher level (e.g., testing for maximum sizes of objects) or; > (2) Is an undetected error and hence the result of such overflow is undefined. > > What this means from a practical point of view (but indeed a bit hard > to define from a formal point of view) is that the normal addition and > subtraction operations (on a 2's complement machines, which all are > now) will "do the right thing" in all cases so we can perform all > those sorts of folding operations. So what's your opinion on the "bug" that triggered the patch in question?\ Namely extract_muldiv_1 folding (((10240 - (sizetype) first) + 1) * 8) /[cl] 8 to ((sizetype) first * 0x0fffffffffffffff8 + 81928) /[cl] 8 to ((sizetype) first * 2305843009213693951 + 10241) thus, folding A - B to -B + A, which is valid for unsigned types only if overflow wraps. But the 2nd folding is only valid if overflow is undefined. Both foldings happen in extract_muldiv_1, the latter is especially enabled for TYPE_IS_SIZETYPE. The reasoning why both transforms are valid is bogus IMHO. Can you give a formal definition of sizetype behavior that can be used to prove that both transforms are valid? Richard.
On Sat, Sep 3, 2011 at 10:37 PM, Richard Guenther <richard.guenther@gmail.com> wrote: > On Sat, Sep 3, 2011 at 9:47 PM, Richard Kenner > <kenner@vlsi1.ultra.nyu.edu> wrote: >> Let me jump in on this a little bit, since much of the code in this area >> was originally written by me. >> >>> Are all sizetype (sub-)expressions always of value in that range? >>> What do we do about the fact that sizetype is unsigned, so -x always >>> overflows for x != 0? Thus, do we need to disable all a - b -> a + >>> -b kind of foldings for sizetypes? (we don't) >> >> The basic idea is that an overflow of sizetype is either: >> >> (1) Detected at a higher level (e.g., testing for maximum sizes of objects) or; >> (2) Is an undetected error and hence the result of such overflow is undefined. >> >> What this means from a practical point of view (but indeed a bit hard >> to define from a formal point of view) is that the normal addition and >> subtraction operations (on a 2's complement machines, which all are >> now) will "do the right thing" in all cases so we can perform all >> those sorts of folding operations. > > So what's your opinion on the "bug" that triggered the patch in question?\ > Namely extract_muldiv_1 folding > > (((10240 - (sizetype) first) + 1) * 8) /[cl] 8 > > to > > ((sizetype) first * 0x0fffffffffffffff8 + 81928) /[cl] 8 > > to > > ((sizetype) first * 2305843009213693951 + 10241) > > thus, folding A - B to -B + A, which is valid for unsigned types only > if overflow wraps. But the 2nd folding is only valid if overflow is undefined. > Both foldings happen in extract_muldiv_1, the latter is especially > enabled for TYPE_IS_SIZETYPE. > > The reasoning why both transforms are valid is bogus IMHO. > Can you give a formal definition of sizetype behavior that can be > used to prove that both transforms are valid? And as you are here now, can you shed some light on the weird decision to make sizetype TYPE_UNSIGNED but sign-extended at the same time? ;) Richard. > Richard. >
> So what's your opinion on the "bug" that triggered the patch in question? > Namely extract_muldiv_1 folding > > (((10240 - (sizetype) first) + 1) * 8) /[cl] 8 > > to > > ((sizetype) first * 0x0fffffffffffffff8 + 81928) /[cl] 8 > > to > > ((sizetype) first * 2305843009213693951 + 10241) > > thus, folding A - B to -B + A, which is valid for unsigned types only > if overflow wraps. I think the tricky part is the optimization of (-X) * 8 to (-8 * X), especially if you then try to compute the -8 as unsigned. I don't think that's valid no matter what overflow does, but I still have a hard time reasoning about these things. > Can you give a formal definition of sizetype behavior that can be > used to prove that both transforms are valid? No, that's what I said before: I don't now have and never did have a formal definition. Which was not good.
> And as you are here now, can you shed some light on the weird > decision to make sizetype TYPE_UNSIGNED but sign-extended > at the same time? ;) Basically, to make division work properly given that the type is unsigned.
> So what's your opinion on the "bug" that triggered the patch in question?\ > Namely extract_muldiv_1 folding > > (((10240 - (sizetype) first) + 1) * 8) /[cl] 8 > > to > > ((sizetype) first * 0x0fffffffffffffff8 + 81928) /[cl] 8 > > to > > ((sizetype) first * 2305843009213693951 + 10241) I think this optimization "works" if you sign-extend the constant when you do division by 8.
On Sat, 3 Sep 2011, Eric Botcazou wrote: > > Well, even when sign-extended there is a constant you can't negate > > without overflow. I would start digging for a testcase with > > such case - but as said, testcases involving TYPE_IS_SIZETYPE are > > very hard to generate for me. > > We run thousands of Ada tests every night on many platforms and never detected > a problem here, so finding a testcase with the unpatched compiler is probably > very hard - if there is really something to be found, which I doubt. > > > Well, but I'd expect you can have a set of Ada types, a function that > > returns just its size and some scan-tree-dumps that check those sizes > > are folded to a constant. Or to just N statements. > > We probably should, but we don't have them (yet). Like for the vast majority > of the transformations made by the folder I guess, so... > > > If you insist I can revert the patch and apply it together with the > > sign-extension change. > > Yes, IMHO it should be part of the final patch. Reverted now. Richard.
Index: trunk/gcc/fold-const.c =================================================================== --- trunk.orig/gcc/fold-const.c 2011-08-31 10:53:58.000000000 +0200 +++ trunk/gcc/fold-const.c 2011-08-31 10:45:09.000000000 +0200 @@ -5894,11 +5894,9 @@ extract_muldiv_1 (tree t, tree c, enum t multiple of the other, in which case we replace this with either an operation or CODE or TCODE. - If we have an unsigned type that is not a sizetype, we cannot do - this since it will change the result if the original computation - overflowed. */ - if ((TYPE_OVERFLOW_UNDEFINED (ctype) - || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype))) + If we have an unsigned type, we cannot do this since it will change + the result if the original computation overflowed. */ + if (TYPE_OVERFLOW_UNDEFINED (ctype) && ((code == MULT_EXPR && tcode == EXACT_DIV_EXPR) || (tcode == MULT_EXPR && code != TRUNC_MOD_EXPR && code != CEIL_MOD_EXPR