[PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

When making sizetypes no longer sign-extended (they are unsigned)
we run into extract_muldiv_1 miscompiling the Ada RTS during
secondary stack initialization while folding sizes for an allocation.

From

((sizetype) (_GLOBAL.SZ4_system.secondary_stack (<PLACEHOLDER_EXPR struct 
system__secondary_stack__chunk_id>.last, <PLACEHOLDER_EXPR struct 
system__secondary_stack__chunk_id>.first) /[cl] 8) + 15 & 
0x0fffffffffffffff0) + 32

we eventually generate 2305843009213704224.  Oops.

This is because extract_multiv_1 happily transforms

(((10240 - (sizetype) first) + 1) * 8) /[cl] 8

through

((sizetype) first * 0x0fffffffffffffff8 + 81928) /[cl] 8

to

((sizetype) first * 2305843009213693951 + 10241)

and then substitute 1 for first.

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.)

Off it goes.

Bootstrap and regtest pending on x86_64-unknown-linux-gnu.

Richard.

2011-08-31  Richard Guenther  <rguenther@suse.de>

	* fold-const.c (extract_muldiv_1): Remove bogus TYPE_IS_SIZETYPE
	special-casing.

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

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Eric Botcazou]

> 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.

-- 
Eric Botcazou

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Eric Botcazou]

> 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.

-- 
Eric Botcazou

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Eric Botcazou]

> 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.

-- 
Eric Botcazou

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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
>

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[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.

-- 
Eric Botcazou

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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
>

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Kenner]

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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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.
>

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Kenner]

> 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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Kenner]

> 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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Kenner]

> 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.

Re: [PATCH] Remove bogus TYPE_IS_SIZETYPE special-casing in extract_muldiv_1

[Richard Guenther]

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.