[PATCH] Fix optimization regression in constant folder

[PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 532 bytes --]

Hi,

The fix for PR middle-end/30364 disabled association of expressions with more 
than 1 variable if the type doesn't wrap.  This is a bit problematic for Ada 
because variable-sized types generate lots of size calculations and we want 
to simplify them at compile time as much as possible.

Bootstrapped/regtested on i586-suse-linux, OK for mainline?


2007-09-17  Eric Botcazou  <ebotcazou@adacore.com>

	* fold-const.c (fold_binary): Associate again expressions with more
	than one variable for size types.


-- 
Eric Botcazou

[-- Attachment #2: p.diff --]
[-- Type: text/x-diff, Size: 860 bytes --]

Index: fold-const.c
===================================================================
--- fold-const.c	(revision 128432)
+++ fold-const.c	(working copy)
@@ -9924,10 +9924,13 @@ fold_binary (enum tree_code code, tree t
 	  var1 = split_tree (arg1, code, &con1, &lit1, &minus_lit1,
 			     code == MINUS_EXPR);
 
-	  /* With undefined overflow we can only associate constants
-	     with one variable.  */
+	  /* With undefined overflow we can only associate constants with one
+	     variable, but this restriction doesn't apply to size types.  */
 	  if ((POINTER_TYPE_P (type)
-	       || (INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type)))
+	       || (INTEGRAL_TYPE_P (type)
+		   && !TYPE_OVERFLOW_WRAPS (type)
+		   && !(TREE_CODE (type) == INTEGER_TYPE
+			&& TYPE_IS_SIZETYPE (type))))
 	      && var0 && var1)
 	    {
 	      tree tmp0 = var0;

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/17/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> Hi,
>
> The fix for PR middle-end/30364 disabled association of expressions with more
> than 1 variable if the type doesn't wrap.  This is a bit problematic for Ada
> because variable-sized types generate lots of size calculations and we want
> to simplify them at compile time as much as possible.
>
> Bootstrapped/regtested on i586-suse-linux, OK for mainline?

I don't think this is correct.  [Note: all this TYPE_IS_SIZETYPE
specialities have
to go somewhen - they really confuse things]

First of all, this misses a (optimization) testcase.  Second, why do we use
signed sizetype calculations when we want unsigned semantics as far as
overflow behavior is concerned?

Richard.

> 2007-09-17  Eric Botcazou  <ebotcazou@adacore.com>
>
>         * fold-const.c (fold_binary): Associate again expressions with more
>         than one variable for size types.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> I don't think this is correct.  [Note: all this TYPE_IS_SIZETYPE
> specialities have to go somewhen - they really confuse things]

Well, this is the documented behaviour of TYPE_IS_SIZETYPE:

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

and we really need this to simplify complex size calculations in Ada.

> First of all, this misses a (optimization) testcase.  Second, why do we use
> signed sizetype calculations when we want unsigned semantics as far as
> overflow behavior is concerned?

I don't think we want unsigned semantics, we want "size" semantics, i.e we 
don't care about overflow in size calculations.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/17/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > I don't think this is correct.  [Note: all this TYPE_IS_SIZETYPE
> > specialities have to go somewhen - they really confuse things]
>
> Well, this is the documented behaviour of TYPE_IS_SIZETYPE:
>
> /* 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.  */
>
> and we really need this to simplify complex size calculations in Ada.
>
> > First of all, this misses a (optimization) testcase.  Second, why do we use
> > signed sizetype calculations when we want unsigned semantics as far as
> > overflow behavior is concerned?
>
> I don't think we want unsigned semantics, we want "size" semantics, i.e we
> don't care about overflow in size calculations.

Well, we need to be consistent and the above documentation is not clear
what happens on overflow.  Either assume overflow of size types wrap or
overflow on them is undefined - if you stick to one or the other behavior
then I'd rather have you update all the TYPE_OVERFLOW_* predicates
than fixing this one single place.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Well, we need to be consistent and the above documentation is not clear
> what happens on overflow.  Either assume overflow of size types wrap or
> overflow on them is undefined - if you stick to one or the other behavior
> then I'd rather have you update all the TYPE_OVERFLOW_* predicates
> than fixing this one single place.

The point is precisely not to choose between wrapping and not wrapping 
arithmetics: we want to allow *all* optimizations by pretending that
overflow doesn't exist for size types.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/18/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > Well, we need to be consistent and the above documentation is not clear
> > what happens on overflow.  Either assume overflow of size types wrap or
> > overflow on them is undefined - if you stick to one or the other behavior
> > then I'd rather have you update all the TYPE_OVERFLOW_* predicates
> > than fixing this one single place.
>
> The point is precisely not to choose between wrapping and not wrapping
> arithmetics: we want to allow *all* optimizations by pretending that
> overflow doesn't exist for size types.

That only works if you know that there is no overflow.  You will have a hard
time arguing that we never hit the case that sizetype calculations do overflow.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> That only works if you know that there is no overflow.  You will
> have a hard time arguing that we never hit the case that sizetype
> calculations do overflow.

You don't have to prove there's no overflow of sizetype, merely that it's
OK if the results are undefined if one should occur.  And that's certainly
the case.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> That only works if you know that there is no overflow.  You will have a
> hard time arguing that we never hit the case that sizetype calculations do
> overflow.

The premise is that the behavior of the program is undefined in this case.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/19/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > That only works if you know that there is no overflow.  You will have a
> > hard time arguing that we never hit the case that sizetype calculations do
> > overflow.
>
> The premise is that the behavior of the program is undefined in this case.

Sure, but only GCC itself creates arithmetic in types with TYPE_IS_SIZETYPE
set.  Do you guarantee we that those never result in overflow?

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> > The premise is that the behavior of the program is undefined in this case.
> 
> Sure, but only GCC itself creates arithmetic in types with TYPE_IS_SIZETYPE
> set.  Do you guarantee we that those never result in overflow?

Again, we don't have to.  We just have to guarantee that it would only
overflow if ANY form of the computation would overflow, meaning that
the program is undefined.

The issue here is arithmetic of the form (A + B) + C where A and B both
have large absolute values but opposite signs, so reassociating it as
A + (B + C) might overflow were the former wouldn't.  But that sort of thing
just doesn't come up in size computations of objects: any negative values
are known to be very small.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Sure, but only GCC itself creates arithmetic in types with TYPE_IS_SIZETYPE
> set.

Right, and it's a very important point, i.e. we don't have to abide by rules 
of some standards for this arithmetic, it's purely internal stuff.

> Do you guarantee we that those never result in overflow? 

My understanding is that of Richard K., i.e. we guarantee that we don't create 
overflow in size calculations unless the program would result in undefined 
behavior.  I agree that it's quite strong a guarantee and we have this famous 
(pathological but valid) Ada testcase c380004 for which we used to generate 
an overflow in a size calculation at some point.

And I can add that the various simplifications performed in these calculations 
are needed to be able to give this guarantee in Ada, because it's every easy 
to create "artifical" overflows with Ada types whose size is variable.  See 
for example utils.c:max_size where we don't exactly care about overflow 
semantics. :-)

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Sure, but only GCC itself creates arithmetic in types with TYPE_IS_SIZETYPE
> set.

So, in the end, may I install the patch?  It restores a transformation that 
has been present in the compiler for ages, but only in valid cases, and I'm 
convinced that this can only help the compiler.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/29/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > Sure, but only GCC itself creates arithmetic in types with TYPE_IS_SIZETYPE
> > set.
>
> So, in the end, may I install the patch?  It restores a transformation that
> has been present in the compiler for ages, but only in valid cases, and I'm
> convinced that this can only help the compiler.

You still didn't come up with an optimization testcase which I asked for
in the initial reply.  And I won't make the decision on the patch (because
I'm not convinced), but defer that to Ian.

Thanks,
Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> You still didn't come up with an optimization testcase which I asked for
> in the initial reply.

Because it's time consuming.  The problem was identified on a 4.1-based 
compiler (you applied the patch on the 4.1 branch too so it was picked for 
our pre-production compiler and broke 2 big proprietary testcases there).

Things have changed between 4.1 and 4.3 so the 2 testcases don't fail with the 
latter like with the former and further work would be required.

> And I won't make the decision on the patch (because I'm not convinced), but
> defer that to Ian. 

OK.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/29/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > You still didn't come up with an optimization testcase which I asked for
> > in the initial reply.
>
> Because it's time consuming.  The problem was identified on a 4.1-based
> compiler (you applied the patch on the 4.1 branch too so it was picked for
> our pre-production compiler and broke 2 big proprietary testcases there).
>
> Things have changed between 4.1 and 4.3 so the 2 testcases don't fail with the
> latter like with the former and further work would be required.

I'm happy with a testcase that only fails on 4.1 - that is, I don't see why
either the code in fold is special, or why you don't need to adjust for
example tree-ssa-reassoc.c on trunk with the same logic.  A testcase
would give me something to look at myself, rather than trying to
imagine what actually happens ;)

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/29/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> On 9/29/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > > You still didn't come up with an optimization testcase which I asked for
> > > in the initial reply.
> >
> > Because it's time consuming.  The problem was identified on a 4.1-based
> > compiler (you applied the patch on the 4.1 branch too so it was picked for
> > our pre-production compiler and broke 2 big proprietary testcases there).
> >
> > Things have changed between 4.1 and 4.3 so the 2 testcases don't fail with the
> > latter like with the former and further work would be required.
>
> I'm happy with a testcase that only fails on 4.1 - that is, I don't see why
> either the code in fold is special, or why you don't need to adjust for
> example tree-ssa-reassoc.c on trunk with the same logic.  A testcase
> would give me something to look at myself, rather than trying to
> imagine what actually happens ;)

To make it clear - you seem to have a compelling case preserving
the special size types because we otherwise miss optimization opportunities.
I (and Roger in the past) try to get rid of them completely, so introducing
new dependence on this feature is exactly the opposite what I thought was
consensus.  Now, a testcase would maybe support your view.

[Getting rid of the special size types would also automatically get rid
of another source of confusion, namely that those special types are
sign-extended independent of their signedness]

Thanks,
Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> I (and Roger in the past) try to get rid of them completely, so introducing
> new dependence on this feature is exactly the opposite what I thought was
> consensus. 

Are you sure about the "completely"?

> [Getting rid of the special size types would also automatically get rid
> of another source of confusion, namely that those special types are
> sign-extended independent of their signedness]

That, I do recall, was an agreed-upon goal.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/29/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > I (and Roger in the past) try to get rid of them completely, so introducing
> > new dependence on this feature is exactly the opposite what I thought was
> > consensus.
>
> Are you sure about the "completely"?

Yes.  There is one thing we might need (or add, or retain), that is an
internal integral type of pointer size (for the sake of POINTER_PLUS_EXPR).
This type should have the same overflow behavior as pointers.  _BUT_,
conversion to or from integers should be disallowed.  Maybe this is the
real point of the badness of the current sizetype (and its interesting state
of overflow-is-defined-or-not) - we happily convert to/from it from/to other
integer types (and pointer types).  This makes it somewhat interesting
to speak about overflow that can never happen.

So, if you can make fold_convert assert that we never convert back
from sizetype to another integral type then the situation wrt overflow
may be fine ;)  But I bet you will get ICEs all over the place.
(Conversions to sizetype are fine, of course; conversions to pointer-type
from sizetype might be not avoidable as well)

Richard.

> > [Getting rid of the special size types would also automatically get rid
> > of another source of confusion, namely that those special types are
> > sign-extended independent of their signedness]
>
> That, I do recall, was an agreed-upon goal.
>
> --
> Eric Botcazou
>

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Yes.

Do you happen to have some references at hand?  I'd be interested in trying to 
understand the plan.  Note that we have to be able to reorder/simplify size 
calculations in Ada, and Roger helped us to do it better in max_size.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Yes.

Do you happen to have some references at hand?  I'd be interested in trying to 
understand the plan.  Note that we have to be able to reorder/simplify size 
calculations in Ada, and Roger helped us to do it better in max_size.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

[-- Attachment #1: Type: text/plain, Size: 795 bytes --]

On 9/30/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > Yes.
>
> Do you happen to have some references at hand?  I'd be interested in trying to
> understand the plan.  Note that we have to be able to reorder/simplify size
> calculations in Ada, and Roger helped us to do it better in max_size.

No.

I tried to bootstrap & test the attached, but it fails in libjava:

../../../../../../trunk/libjava/classpath/gnu/java/awt/font/opentype/truetype/TrueTypeScaler.java:0:
internal compiler error: in fold_overflow_warning, at
fold-const.c:1018
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

if we really want to specialize sizetypes, then this would be the way to go
(after making it work, of course).

Richard.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: p.patch --]
[-- Type: text/x-patch; name="p.patch", Size: 1483 bytes --]

Index: flags.h
===================================================================
--- flags.h	(revision 128885)
+++ flags.h	(working copy)
@@ -314,7 +314,7 @@ extern bool flag_instrument_functions_ex
 /* True if overflow wraps around for the given integral type.  That
    is, TYPE_MAX + 1 == TYPE_MIN.  */
 #define TYPE_OVERFLOW_WRAPS(TYPE) \
-  (TYPE_UNSIGNED (TYPE) || flag_wrapv)
+  ((TYPE_UNSIGNED (TYPE) || flag_wrapv) && (TREE_CODE (TYPE) != INTEGER_TYPE || !TYPE_IS_SIZETYPE (TYPE)))
 
 /* True if overflow is undefined for the given integral type.  We may
    optimize on the assumption that values in the type never overflow.
@@ -325,12 +325,12 @@ extern bool flag_instrument_functions_ex
    other cases it will be appropriate to simply set a flag and let the
    caller decide whether a warning is appropriate or not.  */
 #define TYPE_OVERFLOW_UNDEFINED(TYPE) \
-  (!TYPE_UNSIGNED (TYPE) && !flag_wrapv && !flag_trapv && flag_strict_overflow)
+  ((!TYPE_UNSIGNED (TYPE) && !flag_wrapv && !flag_trapv && flag_strict_overflow) || (TREE_CODE (TYPE) == INTEGER_TYPE && TYPE_IS_SIZETYPE (TYPE)))
 
 /* True if overflow for the given integral type should issue a
    trap.  */
 #define TYPE_OVERFLOW_TRAPS(TYPE) \
-  (!TYPE_UNSIGNED (TYPE) && flag_trapv)
+	 ((!TYPE_UNSIGNED (TYPE) && flag_trapv) && (TREE_CODE (TYPE) != INTEGER_TYPE || !TYPE_IS_SIZETYPE (TYPE)))
 
 /* Names for the different levels of -Wstrict-overflow=N.  The numeric
    values here correspond to N.  */

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> I tried to bootstrap & test the attached, but it fails in libjava:
>
> ../../../../../../trunk/libjava/classpath/gnu/java/awt/font/opentype/truety
>pe/TrueTypeScaler.java:0: internal compiler error: in fold_overflow_warning,
> at
> fold-const.c:1018
> Please submit a full bug report,
> with preprocessed source if appropriate.
> See <http://gcc.gnu.org/bugs.html> for instructions.

The assertion checks that there is no undefined overflow in Java and your 
patch arranges for TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED, so that's not 
very surprising.  The assertion would need to be weakened too.

> if we really want to specialize sizetypes, then this would be the way to go
> (after making it work, of course).

Yes, I think that we need to keep them specialized.  However, your patch is 
not sufficient because TYPE_IS_SIZETYPE => !TYPE_OVERFLOW_WRAPS with it so 
the pessimization in fold_binary won't be undone for example.

It sounds like you really want to have TYPE_IS_SIZETYPE subsumed into the 3 
macros TYPE_OVERFLOW_WRAPS, TYPE_OVERFLOW_UNDEFINED, TYPE_OVERFLOW_TRAPS.

Then I think that we should have

  TYPE_IS_SIZETYPE => TYPE_OVERFLOW_WRAPS
  TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED
  TYPE_IS_SIZETYPE => !TYPE_OVERFLOW_TRAPS

Note that, in all languages except Ada, size types are unsigned so the first 
assertion is almost already true.  A first step would be to make it true in 
Ada too, which would fix the performance regression in fold_binary.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/30/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > I tried to bootstrap & test the attached, but it fails in libjava:
> >
> > ../../../../../../trunk/libjava/classpath/gnu/java/awt/font/opentype/truety
> >pe/TrueTypeScaler.java:0: internal compiler error: in fold_overflow_warning,
> > at
> > fold-const.c:1018
> > Please submit a full bug report,
> > with preprocessed source if appropriate.
> > See <http://gcc.gnu.org/bugs.html> for instructions.
>
> The assertion checks that there is no undefined overflow in Java and your
> patch arranges for TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED, so that's not
> very surprising.  The assertion would need to be weakened too.

Yes, I saw this as well.

> > if we really want to specialize sizetypes, then this would be the way to go
> > (after making it work, of course).
>
> Yes, I think that we need to keep them specialized.  However, your patch is
> not sufficient because TYPE_IS_SIZETYPE => !TYPE_OVERFLOW_WRAPS with it so
> the pessimization in fold_binary won't be undone for example.

well, you cannot have both as in...

> It sounds like you really want to have TYPE_IS_SIZETYPE subsumed into the 3
> macros TYPE_OVERFLOW_WRAPS, TYPE_OVERFLOW_UNDEFINED, TYPE_OVERFLOW_TRAPS.
>
> Then I think that we should have
>
>   TYPE_IS_SIZETYPE => TYPE_OVERFLOW_WRAPS
>   TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED
>   TYPE_IS_SIZETYPE => !TYPE_OVERFLOW_TRAPS

...
  TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED
  TYPE_IS_SIZETYPE => TYPE_OVERFLOW_WRAPS
would mean that for sizetype overflow wraps and is undefined at the
same time.  That doesn't make very much sense.

> Note that, in all languages except Ada, size types are unsigned so the first
> assertion is almost already true.  A first step would be to make it true in
> Ada too, which would fix the performance regression in fold_binary.

Yes, IMHO allowing sizetype to be signed is flawed - we have ssizetype
for that (which we don't allow to be unsigned either).

It also doesn't make sense to initialize all the (compiler internal!)
sizetypes from the frontends.  This should be done by the middle-end
instead.  After all, this is _not_ what the languages use for their
size_t.  [IMHO as we use sizetype for POINTER_PLUS_EXPR, the
compiler-internal sizetypes should have the size of the pointers, not
something else]

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

>   TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED
>   TYPE_IS_SIZETYPE => TYPE_OVERFLOW_WRAPS
> would mean that for sizetype overflow wraps and is undefined at the
> same time.  That doesn't make very much sense.

Well, the semantics of TYPE_IS_SIZETYPE being "we don't care about overflow" 
and you wanting to stuff it into TYPE_OVERFLOW_*, we don't have other choices 
than to select the laxest combination.

Otherwise we weed TYPE_OVERFLOW_MATTERS.

> Yes, IMHO allowing sizetype to be signed is flawed - we have ssizetype
> for that (which we don't allow to be unsigned either).

You misunderstood, I don't want to change the signedness of size types, I just 
want something like

Index: flags.h
===================================================================
--- flags.h     (revision 128881)
+++ flags.h     (working copy)
@@ -314,7 +314,8 @@ extern bool flag_instrument_functions_ex
 /* True if overflow wraps around for the given integral type.  That
    is, TYPE_MAX + 1 == TYPE_MIN.  */
 #define TYPE_OVERFLOW_WRAPS(TYPE) \
-  (TYPE_UNSIGNED (TYPE) || flag_wrapv)
+  (TYPE_UNSIGNED (TYPE) || flag_wrapv \
+   || (TREE_CODE (TYPE) == INTEGER_TYPE && TYPE_IS_SIZETYPE (TYPE)))

 /* True if overflow is undefined for the given integral type.  We may
    optimize on the assumption that values in the type never overflow.

> It also doesn't make sense to initialize all the (compiler internal!)
> sizetypes from the frontends.  This should be done by the middle-end
> instead.  After all, this is _not_ what the languages use for their
> size_t.  [IMHO as we use sizetype for POINTER_PLUS_EXPR, the
> compiler-internal sizetypes should have the size of the pointers, not
> something else]

The front-ends probably need to retain some control though.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Yes, I think that we need to keep them specialized.  

I agree because they are both always known to be much better behaved than any
user type and one of the most critical types to optimize.  It will always
be the case that many more optimizations are both safe and important for
those types than for user types.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 9/30/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > Yes, I think that we need to keep them specialized.
>
> I agree because they are both always known to be much better behaved than any
> user type and one of the most critical types to optimize.  It will always
> be the case that many more optimizations are both safe and important for
> those types than for user types.

Please show testcases.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> > I agree because they are both always known to be much better behaved than
> > any user type and one of the most critical types to optimize.  It will
> > always be the case that many more optimizations are both safe and
> > important for those types than for user types.
> 
> Please show testcases.

I'm making a general comment about strategies, not a specific optimization.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Please show testcases.

OK, we'll try.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

Eric Botcazou <ebotcazou@adacore.com> writes:

> > That doesn't make sense: a type either wraps on overflow or is
> > undefined on overflow.
> 
> Well, I've given the rationale and I stand by it.  We already have the 
> property that, if flag_strict_overflow is not set, signed types are neither 
> TYPE_OVERFLOW_WRAPS nor TYPE_OVERFLOW_UNDEFINED.

Right.  A type can be neither.  But you were asking for sizetypes to
be both, and that does not make sense.


> > Richard's patch for PR 30364 should test TYPE_OVERFLOW_UNDEFINED, not
> > TYPE_OVERFLOW_WRAPS.
> 
> Makes sense, but that won't change anything as far as Ada is concerned.

Then I don't understand what change you want to make.

I want to move toward eliminating TYPE_IS_SIZETYPE checks from the
middle-end, and capture them entirely in TYPE_OVERFLOW_UNDEFINED: a
sizetype is an unsigned type with undefined overflow.

What prevents us from doing that?

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Right.  A type can be neither.  But you were asking for sizetypes to
> be both, and that does not make sense.

No, the claim is that a sizetype can *act like* both and that's different.

In other words, when we say a type has undefined overflow, we need to be
careful to not do operations that could create an overflow when one
couldn't previously have occurred.  But those sorts of pathalogical cases
can't occur for sizetypes because all operations on them are generated
by the compiler, not explicitly by the programmer, and we know we're not
generating the pathalogical cases.

So we want to allow *all* optimizations on such types.

You can't capture that concept with flags that talk about language-defined
concepts such as undefined overflows or wrapping because sizetypes are
*not* language-defined but internal.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Sun, 30 Sep 2007, Richard Kenner wrote:

> > Right.  A type can be neither.  But you were asking for sizetypes to
> > be both, and that does not make sense.
> 
> No, the claim is that a sizetype can *act like* both and that's different.

Clearly a type can not be both at the same time, no matter how much you 
want.  I think the problem comes from the fact that we can use those 
type predicates for different things, namely to 1) infer some knowledge 
about past operations on values of that type (which in turn then might to 
lead to other transformations), and 2) guide which operations we allow on 
values of this type (e.g. that we have to add overflow checks or not).

From what Eric and you told us up to now it seems you want this type to 
have the following properties:
1) overflows don't occur (because you make sure that the compiler never 
   produces overflows on such values)
2) if overflow were to occur, then it wraps (given the first 
   property this is weird, but that is what you said)
3) you want to optimize based on both assumptions, i.e. that overflow
   can't occur, and that the type has wrap-around

I think you need to make up your mind about the property (2) above: why 
_exactly_ (meaning test situations) do you care for how overflow happens 
if you already defined that it can not happen.  Everything will follow 
from that.

What I think you should want is that the type is simply an unsigned type, 
with overflow undefined.  But given the internal inconsistency in your 
current wishes I can't be sure if that really solves your problems.

An unsigned type with undefined overflow does have a place in a 
middle-end.  A type with your current conflicting semantics does _not_ 
have a place in the middle-end IMHO, so it's time invested very well in 
thinking hard about your exact requirements.

> You can't capture that concept with flags that talk about 
> language-defined concepts such as undefined overflows or wrapping 
> because sizetypes are *not* language-defined but internal.

The type flags reflect (or better are meant to reflect eventually) 
properties for the middle-end type system.  Languages types are required 
to map to those we have (of course we can increase the set of properties 
of middle-end types).

It's true that the type flags still are pretty much coming directly from 
language semantics, simply because the middle-end type system is in its 
infancy.  But it will change in one or the other way (cross language LTO 
needs that), and it would be better if it's a well thought out way.  
That's why this discussion is important.  So, if the middle end would give 
you an unsigned, overflow undefined type, would that satisfy you (at least 
when the optimization you want to happen on them, do happen then, which 
also requires some example situations from you)?

Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> From what Eric and you told us up to now it seems you want this type to 
> have the following properties:
> 1) overflows don't occur (because you make sure that the compiler never 
>    produces overflows on such values)
> 2) if overflow were to occur, then it wraps (given the first 
>    property this is weird, but that is what you said)

No, that's wrong.  As I said, the above is thinking in terms of them
as if they were types visible to the user and you are thinking in
programming language terms.  But they *are not* user-visible types,
so I don't think of them in those terms.

Sizetypes have always had the the following properties:

(1) They can only overflow in a case where the program is clearly illegal:
e.g., where the programmer is attempting to construct an object whose size
is larger than can be represented by the machine being coded for.

(2) Computations on sizetype are "well behaved" in the sense that they do
not contain pathalogical cases that require us to supress some optimizations
on other integer types.

> 3) you want to optimize based on both assumptions, i.e. that overflow
>    can't occur, and that the type has wrap-around

More precisely, you want to do *all* optimizations.  For what I'll call
"user-visible" types, you may need to restrict certain optimizations to only
those types that has some particular flag bits relating to overflow
semantics, but for sizetypes, you *always* want to do each of them.

> What I think you should want is that the type is simply an unsigned type, 
> with overflow undefined.  

(1) sizetype in Ada needs to be signed.
(2) if overflow is viewed as undefined, there are optimizations that we
would be suppressed but we want to suppress *none* of them.

But I don't understand why we need (or want!) to define sizetypes in terms
that we'd use for user-visible types: they *aren't* user-visible types,
but instead are very special types used for very specific purposes in
the compiler.  Trying to treat them as if they were user-visible types
seems *very* wrong to me, for numerous reasons (among them being
tree consistency checking: making sure that the appropriate tree operands
are always sizetypes).

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Sun, 30 Sep 2007, Richard Kenner wrote:

> > From what Eric and you told us up to now it seems you want this type to 
> > have the following properties:
> > 1) overflows don't occur (because you make sure that the compiler never 
> >    produces overflows on such values)
> > 2) if overflow were to occur, then it wraps (given the first 
> >    property this is weird, but that is what you said)
> 
> No, that's wrong.  As I said, the above is thinking in terms of them
> as if they were types visible to the user and you are thinking in
> programming language terms.

Not at all.  I'm thinking in middle-end operations possible on those 
types.  I don't care for front-end semantics (to the extent that a mapping 
must be reasonably possible), only what needs to be done by the 
middle-end, what it can assume, what it needs to ensure.

> Sizetypes have always had the the following properties:
> 
> (1) They can only overflow in a case where the program is clearly illegal:
> e.g., where the programmer is attempting to construct an object whose size
> is larger than can be represented by the machine being coded for.

Okay, so overflow can not happen (except in illformed programs, in which 
case we don't need to care).  That seems to hint to a OVERFLOW_UNDEFINED 
type.

> (2) Computations on sizetype are "well behaved" in the sense that they do
> not contain pathalogical cases that require us to supress some optimizations
> on other integer types.

Be more specific.  Much more.  What pathological cases, what optimizations 
do we suppress currently, which of those are allowed in your system.  What 
properties of the type guarantee this.

> > 3) you want to optimize based on both assumptions, i.e. that overflow
> >    can't occur, and that the type has wrap-around
> 
> More precisely, you want to do *all* optimizations.

Too unspecific.

> For what I'll call "user-visible" types, you may need to restrict 
> certain optimizations to only those types that has some particular flag 
> bits relating to overflow semantics, but for sizetypes, you *always* 
> want to do each of them.

But we don't talk about user-visible types.  I never did, and it seems you 
also don't want to talk about them, so let's not do that :-)  As I tried 
to express already, the flag bits are _not_ only for user-visible types.

That this type isn't user-visible doesn't relieve us from defining exactly 
what (middle-end) operations are defined on it, though.  That's what we 
ask from you with at least providing some test situations where an 
unsigned overflow-undefined type doesn't help.

> > What I think you should want is that the type is simply an unsigned type, 
> > with overflow undefined.  
> 
> (1) sizetype in Ada needs to be signed.

That's frontend semantic then, which you explicitely did not want to get 
into.  So why do you say that?  You need to find a mapping from 
whatever frontend types you have to the middle end types.  _If_ 
that mapping is too suboptimal we might have to extend the middle-end 
types.  But consistently so.

> (2) if overflow is viewed as undefined, there are optimizations that we
> would be suppressed but we want to suppress *none* of them.

Like?  For now I only see optimizations enabled by 
TYPE_OVERFLOW_UNDEFINED.

> But I don't understand why we need (or want!) to define sizetypes in terms
> that we'd use for user-visible types: they *aren't* user-visible types,
> but instead are very special types used for very specific purposes in
> the compiler.  Trying to treat them as if they were user-visible types
> seems *very* wrong to me,

I really have a hard time understanding why you're so obsessed (sorry) 
about the user-visible thingy.  Nobody is talking about that.  We are 
talking about the semantic of the middle end sizetype type.  At least I am 
(I'm 99.9% sure Richard G. is, and reasonably sure Ian is too), only you 
keep talking about it.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Not at all.  I'm thinking in middle-end operations possible on those types.

So am I.  They are used to define the sizes of objects and offsets into
objects in the middle-end and I agree that it's important to get well-defined
semantics for them. 

> Okay, so overflow can not happen (except in illformed programs, in which 
> case we don't need to care).  That seems to hint to a OVERFLOW_UNDEFINED 
> type.

Somewhat, though I'm trying hard not to define the sizetype semantics in
the same way we would for a user-visible type since it *isn't* user-visible.
It would be *close* to that, except that this will suppress critical
optimizations that must be done for sizetypes.

> Be more specific.  Much more.  What pathological cases, what optimizations 
> do we suppress currently, which of those are allowed in your system.  What 
> properties of the type guarantee this.

We supress reassociation.  For a type with undefined overflow, we can't
convert (a + b) + c into a + (b + c) for fear of the latter expression
overflowing where the former couldn't.  However, this can only very rarely
happen in practice and only in circumstance I'm calling "pathalogical",
where A and B have opposite signs, both are large, and where B and C have
the same sign.  But this just can't come up in size and offset computations:
any negative values are always small.

> > > 3) you want to optimize based on both assumptions, i.e. that overflow
> > >    can't occur, and that the type has wrap-around
> > 
> > More precisely, you want to do *all* optimizations.
> 
> Too unspecific.

See below.

> > For what I'll call "user-visible" types, you may need to restrict 
> > certain optimizations to only those types that has some particular flag 
> > bits relating to overflow semantics, but for sizetypes, you *always* 
> > want to do each of them.

This is what I meant.

> But we don't talk about user-visible types.  I never did, and it seems you 
> also don't want to talk about them, so let's not do that :-)  As I tried 
> to express already, the flag bits are _not_ only for user-visible types.

And that, I think, is the problem.  They should not apply to sizetypes
since sizetypes have a unique semantics that we don't need to express in
terms of those flags.  For each optimization that we want to supress for
some values of those flags we say we do it for some setting of those
flags *or* if the type is a sizetype.

> > (1) sizetype in Ada needs to be signed.
> 
> That's frontend semantic then, which you explicitely did not want to get 
> into.  So why do you say that?

It's not "front end semantics", but an implemenation issue.  Sizetypes
aren't visible at the user level for Ada either.

> You need to find a mapping from whatever frontend types you have to
> the middle end types.

Of course, but sizetypes are *never* visible at the language level and are
*only* used to communuicate size and position information to the middle-end,
so I lost you here.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/1/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > Not at all.  I'm thinking in middle-end operations possible on those types.
>
> So am I.  They are used to define the sizes of objects and offsets into
> objects in the middle-end and I agree that it's important to get well-defined
> semantics for them.
>
> > Okay, so overflow can not happen (except in illformed programs, in which
> > case we don't need to care).  That seems to hint to a OVERFLOW_UNDEFINED
> > type.
>
> Somewhat, though I'm trying hard not to define the sizetype semantics in
> the same way we would for a user-visible type since it *isn't* user-visible.
> It would be *close* to that, except that this will suppress critical
> optimizations that must be done for sizetypes.

It sounds like you define sizetypes to have infinite precision.  Which
is the only
way overflow cannot occur.  Of course in this case converting a
unsigned sizetype
to a signed one will never produce a negative value (which we rely on,
for example
with POINTER_PLUS_EXPR which takes a unsigned sizetype argument but
perfectly well handles effective MINUS by using wrapping semantics - or rather,
by effectively assuming signedness.  It's another thing I opposed to,
as it hints
at POINTER_PLUS_EXPR wants the same sort of thing you want - do the
right thing in the right situation, which is not very well defined).

Oh, and did I ask for testcases?

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> It sounds like you define sizetypes to have infinite precision.  

No.  Where did I say that?

> Oh, and did I ask for testcases?

I'm talking about how to define the semantics of a certain middle-end
object (in this case sizetypes).  That doesn't involve test cases.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/1/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > It sounds like you define sizetypes to have infinite precision.
>
> No.  Where did I say that?

It matches undefined overflow && wrapping overflow, as for infinite precision
overflow really cannot happen.

> > Oh, and did I ask for testcases?
>
> I'm talking about how to define the semantics of a certain middle-end
> object (in this case sizetypes).  That doesn't involve test cases.

You say you need special semantics because otherwise optimization won't work.
This needs testcases.  Otherwise just mapping sizetype semantics to an
_existing_ semantic makes most sense as it reduces diversity of semantics
and causes less confusion.  Look at all the places we _don't_ specialize
sizetypes!  You want to audit all these?

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> You say you need special semantics because otherwise optimization won't
> work. This needs testcases.  Otherwise just mapping sizetype semantics to
> an _existing_ semantic makes most sense as it reduces diversity of
> semantics and causes less confusion.

You're rewriting history, sizetype semantics already exists, just look at the 
definition of TYPE_IS_SIZETYPE in tree.h and its uses in fold-const.c.

> Look at all the places we _don't_specialize sizetypes!  You want to audit
> all these? 

No, we just want to avoid consciously harming the compiler.  In my experience,
a single line in fold-const.c can sometimes be more effective than an entire 
optimization pass.

--
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> It matches undefined overflow && wrapping overflow, as for infinite precision
> overflow really cannot happen.

But it can happen: in the case of illegal programs when the programmer tries
to make an object that's too big.

> You say you need special semantics because otherwise optimization won't work.

Actually, I didn't say that.  I said that sizetypes *already have* and
always have had different semantics than user-visible types and that trying
to map those semantics onto a new set of semantics being defined for
user-visible types is not correct.

> This needs testcases.  

Eric and I have both given you an example of an optimization that should
apply to sizetypes but which won't if you try to change their semantics to
match those of a user-visible type.

> Otherwise just mapping sizetype semantics to an _existing_ semantic makes
> most sense as it reduces diversity of semantics and causes less
> confusion.

I'm not proposing changing the semantics of sizetypes!  Quite the contrary:
I'm saying that we keep them as they are and *not* try to map them to these
new flags which are meant for user-visible types.

> Look at all the places we _don't_ specialize sizetypes!  You want to audit
> all these?

I don't follow.  All these optimizations used to be done for sizetypes and
I'm saying they need to continue to work.  It's the proposal to use these
new flags that's changing things.  And I also don't understand what "audit"
means in this context.  The semantics of these various types (sizetypes and
the different user-visible type semantics) only differ in overflow
handling.  So we only need to "audit" those cases where overflow tests are
involved.

A good analogy to sizetypes are EXACT_DIV_EXPR.  That doesn't correspond to
any user-visible construct but is used in the compiler when we know that
the division will have an exact result and we don't have to worry about
special cases for the remainder.  You can ask (definitionally, at least)
which of the other rounding types it's equivalent to and the answer is that
it's not equivalent to *any* of them because the compiler is free to
generate, in a case-by-case manner, whatever code is more efficient knowing
that it doesn't have to worry about remainder semantics.

It's the same for sizetypes.  We're not making them equivalent to any other
type of overflow behavior, but instead saying that, in each case, the
compiler is free to generate the best code it can for them knowing that it
doesn't have to worry about overflow semantics concerns.

This is not a new definition: sizetypes have *always* been defined this
way.  We just never needed to specify this as part of their definition
before.

Note that I'm the one who added TYPE_IS_SIZETYPE flag back in 2000 and made
the concept of treating sizetypes specially so I know what my intent was
then.  Indeed there was no documentation then about the overflow issue
because nobody was thinking in those terms at that point.

What you're proposing to do is to *change* the semantics of sizetypes from
those in 2000 to match that of some variant of flags that can be specified
on user-visible types.  That proposal would need some evidence that it's
beneficial to do that.

But Eric's patch that started this thread is just implementing the
*present* definition of sizetypes.  stage3 is not the appropriate time to
change the semantics of something, so his patch seems appropriate to me.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/1/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > It matches undefined overflow && wrapping overflow, as for infinite precision
> > overflow really cannot happen.
>
> But it can happen: in the case of illegal programs when the programmer tries
> to make an object that's too big.
>
> > You say you need special semantics because otherwise optimization won't work.
>
> Actually, I didn't say that.  I said that sizetypes *already have* and
> always have had different semantics than user-visible types and that trying
> to map those semantics onto a new set of semantics being defined for
> user-visible types is not correct.
>
> > This needs testcases.
>
> Eric and I have both given you an example of an optimization that should
> apply to sizetypes but which won't if you try to change their semantics to
> match those of a user-visible type.
>
> > Otherwise just mapping sizetype semantics to an _existing_ semantic makes
> > most sense as it reduces diversity of semantics and causes less
> > confusion.
>
> I'm not proposing changing the semantics of sizetypes!  Quite the contrary:
> I'm saying that we keep them as they are and *not* try to map them to these
> new flags which are meant for user-visible types.
>
> > Look at all the places we _don't_ specialize sizetypes!  You want to audit
> > all these?
>
> I don't follow.  All these optimizations used to be done for sizetypes and
> I'm saying they need to continue to work.  It's the proposal to use these
> new flags that's changing things.  And I also don't understand what "audit"
> means in this context.  The semantics of these various types (sizetypes and
> the different user-visible type semantics) only differ in overflow
> handling.  So we only need to "audit" those cases where overflow tests are
> involved.

I see exactly 6 places in the middle-end that check TYPE_IS_SIZETYPE.  All
of them in fold-const.c.  What I say is that if sizetypes are worth to
be special
for optimization, why don't optimization passes like VRP or tree-ssa-reassoc.c
not check for TYPE_IS_SIZETYPE?  I say, that TYPE_IS_SIZETYPE can't
be very important as its only used in _very_ few places.  Instead I
ask for testcases
where it _matters_ that we do the optimization in the few places in fold-const.c
that check for TYPE_IS_SIZETYPE because no other optimization pass does
the required transformation.  I argue we should fix optimization passes instead
of fold.  Or if you rely on sizetype in a so different way in Ada than other
frontends maybe using fold () to simplify sizetype operations is not the best
way to ensure proper optimization?

Two of the 6 places are to check if sizetypes are sign-extended, one is to not
mark results TREE_OVERFLOW in int_const_binop for sizetypes.  One is in
extract_multdiv_1 and it needs a comment - it's not exactly clear why sizetype
is special here.  One is with widening which is somehow special for sizetypes,
one is for optimizing div/mult sequences.  That's it.

You seem to have a testcase that shows that re-association is very important
for you for sizetypes.  Why can't you produce something out of it that you
can show us?

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I see exactly 6 places in the middle-end that check TYPE_IS_SIZETYPE.  All
> of them in fold-const.c.  What I say is that if sizetypes are worth to
> be special for optimization, why don't optimization passes like VRP or =
> tree-ssa-reassoc.c not check for TYPE_IS_SIZETYPE?

Do they check for overflow properties?  If not, why should they check for
sizetype: the only difference is overflow properties.

> You seem to have a testcase that shows that re-association is very important
> for you for sizetypes.  Why can't you produce something out of it that you
> can show us?

I think Eric is working on that (these tend to be very large test
cases), but that's orthogonal to the definitional issue here.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/1/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > I see exactly 6 places in the middle-end that check TYPE_IS_SIZETYPE.  All
> > of them in fold-const.c.  What I say is that if sizetypes are worth to
> > be special for optimization, why don't optimization passes like VRP or =
> > tree-ssa-reassoc.c not check for TYPE_IS_SIZETYPE?
>
> Do they check for overflow properties?  If not, why should they check for
> sizetype: the only difference is overflow properties.

Sure they do.  tree-ssa-reassoc.c does, err, re-association, which is only valid
for wrapping overflow (or as you define it, for sizetypes).  VRP
simplifies things
based on for example undefined overflow.  In _most_ of the cases the middle-end
now checks via the appropriate TYPE_OVERFLOW_* macros, but there are
probably places left that just use TYPE_UNSIGNED to decide on overflow
behavior.

Which is why, if at all, sizetype should be specialized in the overflow checking
macros, because then a lot more optimizations benefit from it.  Instead they
now change optimization behavior on sizetypes based on their sign, flag
setting such as -fstrict-overflow or -fwrapv, which clearly does not match
not exposing sizetype semantics to the user.

> > You seem to have a testcase that shows that re-association is very important
> > for you for sizetypes.  Why can't you produce something out of it that you
> > can show us?
>
> I think Eric is working on that (these tend to be very large test
> cases), but that's orthogonal to the definitional issue here.

Thanks,
Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Sure they do.  tree-ssa-reassoc.c does, err, re-association, which is
> only valid for wrapping overflow (or as you define it, for sizetypes).
> VRP simplifies things based on for example undefined overflow.  In _most_
> of the cases the middle-end now checks via the appropriate
> TYPE_OVERFLOW_* macros, but there are probably places left that just use
> TYPE_UNSIGNED to decide on overflow behavior.

Then indeed those places perhaps also have bugs and need to check
TYPE_IS_SIZETYPE too.

> Which is why, if at all, sizetype should be specialized in the overflow
> checking macros, because then a lot more optimizations benefit from it.
> Instead they now change optimization behavior on sizetypes based on their
> sign, flag setting such as -fstrict-overflow or -fwrapv, which clearly
> does not match not exposing sizetype semantics to the user.

Yes, that's *very* wrong, in my opinion.  -fstrict-overflow or -fwrapv
certainly shouldn't affect sizetypes.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> > You say you need special semantics because otherwise optimization won't work.
> 
> Actually, I didn't say that.  I said that sizetypes *already have* and
> always have had different semantics than user-visible types and that trying
> to map those semantics onto a new set of semantics being defined for
> user-visible types is not correct.

The rest of don't us really understand what the semantics of sizetypes
are.  The only documentation is in tree.h, and it only says what
sizetypes are, it doesn't say what semantics they should have.

That is why we must have test cases.  If we don't have test cases, we
will certainly break those semantics going forward.  We don't need
description, we need code.

In particular I don't understand why sizetypes are sign extended.  Why
do we have negative sizetype values?


That said, I take your point that TYPE_OVERFLOW_UNDEFINED is not quite
right for sizetypes, since it does not permit us to introduce overflow
where it was not present (i.e., it does not permit us to reassociate).
And TYPE_OVERFLOW_WRAPS is not quite sufficient, since it does not
permit canonicalizations.

TYPE_OVERFLOW_WRAPS seems clearly correct for sizetypes (if not, why
not, and give us an example).

So it seems that we should do is separate TYPE_OVERFLOW_UNDEFINED into
two different meanings:

1) We can assume that computations in this type will never overflow,
   but we should be careful not to introduce overflow where it was not
   present.  (TYPE_OVERFLOW_UNDEFINED)

2) We can assume that computations in this type will never overflow,
   no matter what we do.  (TYPE_IGNORE_OVERFLOWS)

Then a few places which currently check TYPE_OVERFLOW_WRAPS can check
TYPE_IGNORE_OVERFLOWS instead.


I really want to move toward a semantics for sizetypes which does not
involve mysterious checks for TYPE_IS_SIZETYPE.  If we can't do that,
we are going to keep breaking the way you want it to work.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> The rest of don't us really understand what the semantics of sizetypes
> are.  The only documentation is in tree.h, and it only says what
> sizetypes are, it doesn't say what semantics they should have.

Right, because nobody was thinking about these issues back when they
were created.

> In particular I don't understand why sizetypes are sign extended.  Why
> do we have negative sizetype values?

Think about virtual origins for arrays or similar such.  There are a
few cases that come up in Ada where DECL_FIELD_OFFSET (which must be
of sizetype) is a small negative value.

> And TYPE_OVERFLOW_WRAPS is not quite sufficient, since it does not
> permit canonicalizations.
> 
> TYPE_OVERFLOW_WRAPS seems clearly correct for sizetypes (if not, why
> not, and give us an example).

For the reason you just gave: it suppresses some optimizations.

> So it seems that we should do is separate TYPE_OVERFLOW_UNDEFINED into
> two different meanings:
> 
> 1) We can assume that computations in this type will never overflow,
>    but we should be careful not to introduce overflow where it was not
>    present.  (TYPE_OVERFLOW_UNDEFINED)
> 
> 2) We can assume that computations in this type will never overflow,
>    no matter what we do.  (TYPE_IGNORE_OVERFLOWS)
> 
> Then a few places which currently check TYPE_OVERFLOW_WRAPS can check
> TYPE_IGNORE_OVERFLOWS instead.

That would probably work.

> I really want to move toward a semantics for sizetypes which does not
> involve mysterious checks for TYPE_IS_SIZETYPE.  If we can't do that,
> we are going to keep breaking the way you want it to work.

I see it exactly the opposite way around: sizetype means "handle this
computations in the most efficient way possible" (like my EXACT_DIV_EXPR).
So any optimization conditionalized on an attribute of the type can simply
can "|| TYPE_IS_SIZETYPE".  But if we go the approach of defining flags in
a special way to deal with case and then get rid of TYPE_IS_SIZETYPE, we 
have to go through exactly the same problem as now if some other 
attributes are added to types that suppress only some optimizations.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> > TYPE_OVERFLOW_WRAPS seems clearly correct for sizetypes (if not, why
> > not, and give us an example).
> 
> For the reason you just gave: it suppresses some optimizations.

It doesn't, though.  Having TYPE_OVERFLOW_WRAPS be true for a type
does not cause gcc to avoid any optimizations.

(Not having TYPE_OVERFLOW_UNDEFINED be true does avoid optimizations;
having TYPE_OVERFLOW_WRAPS be true does not.)


> > I really want to move toward a semantics for sizetypes which does not
> > involve mysterious checks for TYPE_IS_SIZETYPE.  If we can't do that,
> > we are going to keep breaking the way you want it to work.
> 
> I see it exactly the opposite way around: sizetype means "handle this
> computations in the most efficient way possible" (like my EXACT_DIV_EXPR).
> So any optimization conditionalized on an attribute of the type can simply
> can "|| TYPE_IS_SIZETYPE".  But if we go the approach of defining flags in
> a special way to deal with case and then get rid of TYPE_IS_SIZETYPE, we 
> have to go through exactly the same problem as now if some other 
> attributes are added to types that suppress only some optimizations.

I think that approach winds up being confusing.  We have to think
about types in terms of what operations are permitted on them.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> It doesn't, though.  Having TYPE_OVERFLOW_WRAPS be true for a type
> does not cause gcc to avoid any optimizations.

Forever or just currently?  That's my concern.

I'm not trying to figure out a way to make things work now, but to establish
a framework for the future.  The semantics of sizetypes mean "don't
suppress *any* optimizations".  TYPE_OVERFLOW_WRAPS has different semantics.
Right now the implementation of those are the same.  But do we want to
guarantee that by defining things that way?

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Mon, 1 Oct 2007, Richard Kenner wrote:

> I'm not trying to figure out a way to make things work now, but to establish
> a framework for the future.  The semantics of sizetypes mean "don't
> suppress *any* optimizations".

Let me show you why the predicate "don't suppress any optimizations" is 
non-sensical by a constructed example: Suppose we were to introduce a type 
flag which can be applied to integral types ensuring that all values of 
that type are even integers, TYPE_EVEN_VALUED.

Presumably we did so because we saw the need for some worthwhile 
transformation applied to such values.  For instance we could use the low 
bit for something else, or increase the range of that type to be twice the 
nominal range.  Let one of these transformations be an optimization.

You are probably not going to argue that such optimization should also be 
applied to your sizetype.  Hence "all" optimizations is a useless 
predicate.  You need to spell out what operations are allowed on that 
type, and what the invariants for them are.  There really is no way around 
this.  Because otherwise someone somewhere will break what you think the 
semantics of it should be, but neglected to specify.

So, there's your path to the future, ensuring nobody will break your 
wishes; spell out what operations are required for your type.  To make 
that easy start with the most similar existing type (probably signed 
integer), and say what the new invariants of operations are.  Then destill 
those invariants (or better the diff to the invariants from the starting 
type) to a small set of orthogonal properties which can then be flags on 
types (and perhaps that will simply lead to only the IGNORE_OVERFLOW from 
Ian).  TYPE_IS_SIZETYPE is not such element of an orthogonal set of 
properties.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> That said, I take your point that TYPE_OVERFLOW_UNDEFINED is not quite
> right for sizetypes, since it does not permit us to introduce overflow
> where it was not present (i.e., it does not permit us to reassociate).
> And TYPE_OVERFLOW_WRAPS is not quite sufficient, since it does not
> permit canonicalizations.
>
> TYPE_OVERFLOW_WRAPS seems clearly correct for sizetypes (if not, why
> not, and give us an example).
>
> So it seems that we should do is separate TYPE_OVERFLOW_UNDEFINED into
> two different meanings:
>
> 1) We can assume that computations in this type will never overflow,
>    but we should be careful not to introduce overflow where it was not
>    present.  (TYPE_OVERFLOW_UNDEFINED)
>
> 2) We can assume that computations in this type will never overflow,
>    no matter what we do.  (TYPE_IGNORE_OVERFLOWS)

Yes, TYPE_IGNORE_OVERFLOWS is what I'm asking for from the very beginning.

> Then a few places which currently check TYPE_OVERFLOW_WRAPS can check
> TYPE_IGNORE_OVERFLOWS instead.

What about places where we check TYPE_OVERFLOW_UNDEFINED?  Or do we keep 
TYPE_OVERFLOW_UNDEFINED on size types too (it is set for Ada)?

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

Eric Botcazou <ebotcazou@adacore.com> writes:

> > That said, I take your point that TYPE_OVERFLOW_UNDEFINED is not quite
> > right for sizetypes, since it does not permit us to introduce overflow
> > where it was not present (i.e., it does not permit us to reassociate).
> > And TYPE_OVERFLOW_WRAPS is not quite sufficient, since it does not
> > permit canonicalizations.
> >
> > TYPE_OVERFLOW_WRAPS seems clearly correct for sizetypes (if not, why
> > not, and give us an example).
> >
> > So it seems that we should do is separate TYPE_OVERFLOW_UNDEFINED into
> > two different meanings:
> >
> > 1) We can assume that computations in this type will never overflow,
> >    but we should be careful not to introduce overflow where it was not
> >    present.  (TYPE_OVERFLOW_UNDEFINED)
> >
> > 2) We can assume that computations in this type will never overflow,
> >    no matter what we do.  (TYPE_IGNORE_OVERFLOWS)
> 
> Yes, TYPE_IGNORE_OVERFLOWS is what I'm asking for from the very beginning.
> 
> > Then a few places which currently check TYPE_OVERFLOW_WRAPS can check
> > TYPE_IGNORE_OVERFLOWS instead.
> 
> What about places where we check TYPE_OVERFLOW_UNDEFINED?  Or do we keep 
> TYPE_OVERFLOW_UNDEFINED on size types too (it is set for Ada)?

In some of the places where we currently check
TYPE_OVERFLOW_UNDEFINED, we would also check TYPE_IGNORE_OVERFLOWS (or
we introduce yet another flag which is the intersection).  In the
proposal above, it doesn't make sense to me to set
TYPE_OVERFLOW_UNDEFINED for sizetypes.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> In some of the places where we currently check
> TYPE_OVERFLOW_UNDEFINED, we would also check TYPE_IGNORE_OVERFLOWS (or
> we introduce yet another flag which is the intersection).

Probably most of them.

> In the proposal above, it doesn't make sense to me to set
> TYPE_OVERFLOW_UNDEFINED for sizetypes.

OK, so TYPE_IGNORE_OVERFLOWS + TYPE_OVERFLOW_WRAPS for sizetypes?

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

Eric Botcazou <ebotcazou@adacore.com> writes:

> > In some of the places where we currently check
> > TYPE_OVERFLOW_UNDEFINED, we would also check TYPE_IGNORE_OVERFLOWS (or
> > we introduce yet another flag which is the intersection).
> 
> Probably most of them.
> 
> > In the proposal above, it doesn't make sense to me to set
> > TYPE_OVERFLOW_UNDEFINED for sizetypes.
> 
> OK, so TYPE_IGNORE_OVERFLOWS + TYPE_OVERFLOW_WRAPS for sizetypes?

That makes sense to me.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> > OK, so TYPE_IGNORE_OVERFLOWS + TYPE_OVERFLOW_WRAPS for sizetypes?
>
> That makes sense to me.

Agreed.

Next question: independently of the underlying type of not?  For all languages 
minus Ada sizetypes are unsigned so TYPE_IGNORE_OVERFLOWS+TYPE_OVERFLOW_WRAPS 
is kind of natural.  For Ada, sizetypes are signed (Richard explained why) so
TYPE_IGNORE_OVERFLOWS+TYPE_OVERFLOW_WRAPS is not natural.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Wed, 3 Oct 2007, Eric Botcazou wrote:

> > > OK, so TYPE_IGNORE_OVERFLOWS + TYPE_OVERFLOW_WRAPS for sizetypes?
> >
> > That makes sense to me.
> 
> Agreed.
> 
> Next question: independently of the underlying type of not?

If you determined, that yes you indeed want that behaviour of your type X, 
then yes, independend of the other properties like signedness (of course 
if the combination makes sense, which it does here).

> For all languages minus Ada sizetypes are unsigned so 
> TYPE_IGNORE_OVERFLOWS+TYPE_OVERFLOW_WRAPS is kind of natural.  For Ada, 
> sizetypes are signed (Richard explained why) so 
> TYPE_IGNORE_OVERFLOWS+TYPE_OVERFLOW_WRAPS is not natural.

That shouldn't bother us.  It might of course be that we have some 
transformations which explicitely look for unsignedness, whereas you also 
want them to apply to your sizetypes.  We simply have to find and fix 
them.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Richard Kenner wrote:

>> Be more specific.  Much more.  What pathological cases, what optimizations 
>> do we suppress currently, which of those are allowed in your system.  What 
>> properties of the type guarantee this.
> 
> We supress reassociation.  For a type with undefined overflow, we can't
> convert (a + b) + c into a + (b + c) for fear of the latter expression
> overflowing where the former couldn't.  However, this can only very rarely
> happen in practice and only in circumstance I'm calling "pathalogical",
> where A and B have opposite signs, both are large, and where B and C have
> the same sign.  But this just can't come up in size and offset computations:
> any negative values are always small.

I've seen people declare C++ objects that map on to huge chunks of the
entire object space, e.g.:

  class Everything {
    char [2 * 1024 * 1024 * 1024];
  };

Then, all you need is a derived class, and the offsets from that to the
base class will be very large negative numbers.  I'm not sure whether we
give those ptrdiff_t type or a signed sizetype type -- but if we're
going to have a special type for sizetype, this ought to be one.

Where does this "negative values are always small" guarantee come from?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I've seen people declare C++ objects that map on to huge chunks of the
> entire object space, e.g.:
> 
>   class Everything {
>     char [2 * 1024 * 1024 * 1024];
>   };
> 
> Then, all you need is a derived class, and the offsets from that to the
> base class will be very large negative numbers.  I'm not sure whether we
> give those ptrdiff_t type or a signed sizetype type -- but if we're
> going to have a special type for sizetype, this ought to be one.
> 
> Where does this "negative values are always small" guarantee come from?

It wasn't a "guarantee", more a statement of typical usage, but you're
right that they can be large in some cases.  However, I still believe that
even in those cases, the thing we DO have to guarantee is indeed true: that
all the numbers involved have the property that they are well-behaved
enough that unless there is a too-large item, so an overflow will occur, no
reassociation will produce an overflow.

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Richard Kenner wrote:

> It wasn't a "guarantee", more a statement of typical usage, but you're
> right that they can be large in some cases.  However, I still believe that
> even in those cases, the thing we DO have to guarantee is indeed true: that
> all the numbers involved have the property that they are well-behaved
> enough that unless there is a too-large item, so an overflow will occur, no
> reassociation will produce an overflow.

I don't see why that would be.  Suppose we have a very large class, and
a derived class of that.  So, the object is at (small) A, the size is
(large) B, and the derived class is at (large) A + B.  Suppose further
that we have a field F in A with an offset C.  So, if we want to talk
about F relative to the derived class (i.e., a C++ expression like
derived->f) we'll compute that address as ((A + B) - B) + C.
"Optimizing" that as (A + B) + (C - B) is likely to result in underflow
in the second expression.

In general, I see no basis for assuming this kind of constraint on a
sizetype, unless you assume all sizes are significantly smaller than the
total address space.  But, we don't get to assume that, even though it
is true in practice on most workstation/server systems running typical
workloads.

I see no reason not to assume that sizetypes wrap around, even when
signed, if that's convenient to us.  After all, that's how hardware
operations work on virtually all machines.  So, I think it's fine to
reassociate -- but not to simultaneously assume that we never get overflow.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I don't see why that would be.  Suppose we have a very large class, and
> a derived class of that.  So, the object is at (small) A, the size is
> (large) B, and the derived class is at (large) A + B.  Suppose further
> that we have a field F in A with an offset C.  So, if we want to talk
> about F relative to the derived class (i.e., a C++ expression like
> derived->f) we'll compute that address as ((A + B) - B) + C.
> "Optimizing" that as (A + B) + (C - B) is likely to result in underflow
> in the second expression.

I think you're right.  I was thinking of the virtual-origin case, where
you might have large negative and positive values, but reassociation
can't overfow unless a size is either too large or an index out of range.
I wasn't thinking of the sort of case above.

> In general, I see no basis for assuming this kind of constraint on a
> sizetype, unless you assume all sizes are significantly smaller than the
> total address space.  But, we don't get to assume that, even though it
> is true in practice on most workstation/server systems running typical
> workloads.

I wouldn't want to make that assumption either, and wasn't thinking of
doing so.

> I see no reason not to assume that sizetypes wrap around, even when
> signed, if that's convenient to us.  After all, that's how hardware
> operations work on virtually all machines.  So, I think it's fine to
> reassociate -- but not to simultaneously assume that we never get overflow.

Indeed on the way home, I was thinking the same thing.  The only downside
to applying wrapping semantics is in the area of loop optimizations,
where we have to limit things in those cases.  But, as I understand it,
that's only true if bivs are of a wrapping type, and it's hard to see
having a sizetype as a biv.  But if having givs that wrap ALSO supresses
optimizations, then I think there is an issue.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Wed, 10 Oct 2007, Mark Mitchell wrote:

> I've seen people declare C++ objects that map on to huge chunks of the
> entire object space, e.g.:
> 
>   class Everything {
>     char [2 * 1024 * 1024 * 1024];
>   };
> 
> Then, all you need is a derived class, and the offsets from that to the 
> base class will be very large negative numbers.  I'm not sure whether we 
> give those ptrdiff_t type or a signed sizetype type -- but if we're 
> going to have a special type for sizetype, this ought to be one.
> 
> Where does this "negative values are always small" guarantee come from?

It was my understanding during this whole thread, that this sizetype with 
the funny guarantees only can come out of the Ada frontend (and therefore 
needs to be dealt with in the middle end), and should never be produced by 
the other languages, in particular not C or C++.  I realize that this 
currently is not the case (i.e. C/C++ do produce TYPE_IS_SIZETYPE types) 
and my understanding was that this actually is a bug.

It's obvious that C and C++ could _not_ make use of a type with the 
properties that Eric and Richard K. proposed, and as I don't know Ada well 
enough I simply assumed they know what they want and can ensure the 
guarantees they need for that type due to magic restrictions of the 
language itself.

My understanding is supported by the comment in front of the 
TYPE_IS_SIZETYPE definition in tree.h where it explicitely mentions that 
size_t should not have this flag set.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Wed, 10 Oct 2007, Mark Mitchell wrote:
>
> > I've seen people declare C++ objects that map on to huge chunks of the
> > entire object space, e.g.:
> >
> >   class Everything {
> >     char [2 * 1024 * 1024 * 1024];
> >   };
> >
> > Then, all you need is a derived class, and the offsets from that to the
> > base class will be very large negative numbers.  I'm not sure whether we
> > give those ptrdiff_t type or a signed sizetype type -- but if we're
> > going to have a special type for sizetype, this ought to be one.
> >
> > Where does this "negative values are always small" guarantee come from?
>
> It was my understanding during this whole thread, that this sizetype with
> the funny guarantees only can come out of the Ada frontend (and therefore
> needs to be dealt with in the middle end), and should never be produced by
> the other languages, in particular not C or C++.  I realize that this
> currently is not the case (i.e. C/C++ do produce TYPE_IS_SIZETYPE types)
> and my understanding was that this actually is a bug.
>
> It's obvious that C and C++ could _not_ make use of a type with the
> properties that Eric and Richard K. proposed, and as I don't know Ada well
> enough I simply assumed they know what they want and can ensure the
> guarantees they need for that type due to magic restrictions of the
> language itself.
>
> My understanding is supported by the comment in front of the
> TYPE_IS_SIZETYPE definition in tree.h where it explicitely mentions that
> size_t should not have this flag set.

It's used for "internal" calculations in C++ as well.  Which, as I said at the
very beginning in this thread makes it hard to argue that such a type is more
than a usual integral type (with the only exception that possibly even signed
sizetypes wrap).

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Guenther wrote:

> It's used for "internal" calculations in C++ as well.

As I wrote:

"I realize that this currently is not the case (i.e. C/C++ do produce 
TYPE_IS_SIZETYPE types) and my understanding was that this actually is a 
bug"

> Which, as I said at the very beginning in this thread makes it hard to 
> argue that such a type is more than a usual integral type (with the only 
> exception that possibly even signed sizetypes wrap).

Exactly.  This type should not be produced or used by anything else than 
Ada.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Thu, 11 Oct 2007, Richard Guenther wrote:
>
> > It's used for "internal" calculations in C++ as well.
>
> As I wrote:
>
> "I realize that this currently is not the case (i.e. C/C++ do produce
> TYPE_IS_SIZETYPE types) and my understanding was that this actually is a
> bug"
>
> > Which, as I said at the very beginning in this thread makes it hard to
> > argue that such a type is more than a usual integral type (with the only
> > exception that possibly even signed sizetypes wrap).
>
> Exactly.  This type should not be produced or used by anything else than
> Ada.

No - either it should be produced by no-one or it can be produced by everyone
in which case it needs defined (and sane) semantics.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> No - either it should be produced by no-one or it can be produced by everyone
> in which case it needs defined (and sane) semantics.

It is and always has been produced by everybody.  It has always had defined
semantics except that back then we weren't thinking of terms of overflow,
so we have to expand the definition to include thinking about that.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Exactly.  This type should not be produced or used by anything else than 
> Ada.

Huh?  sizetype has nothing whatsoever to do with Ada or any other language.
It's the type that we use for the trees in TYPE_SIZE, TYPE_SIZE_UNIT,
DECL_SIZE, DECL_SIZE_UNIT, DECL_FIELD_OFFSET, the component size in an
ARRAY_REF and the offset in a COMPONENT_REF.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > Exactly.  This type should not be produced or used by anything else than
> > Ada.
>
> Huh?  sizetype has nothing whatsoever to do with Ada or any other language.
> It's the type that we use for the trees in TYPE_SIZE, TYPE_SIZE_UNIT,
> DECL_SIZE, DECL_SIZE_UNIT, DECL_FIELD_OFFSET, the component size in an
> ARRAY_REF and the offset in a COMPONENT_REF.

Yes.  What makes Ada somewhat special is that it is quite common for Ada that
those are not integer constants (of sizetype), but variables or
expressions (of sizetype).
My understanding is that this whole issue is only about optimizing
these sizetype
expressions.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Yes.  What makes Ada somewhat special is that it is quite common for Ada that
> those are not integer constants (of sizetype), but variables or
> expressions (of sizetype).

No.  If you have a[i], in any language, the computation of the offset from
the start of A is done in sizetype and that's normally an expression.

It's certaily true that you can have *more complex* sizetype expressions
in Ada than in C, but that's relative and Mark's example yesterday showed
that sizetype expressions can be even more complex in C++ than Ada.

We're seeing the *optimization* issue more in Ada because very long
expressions occur more there, but the definitional issue is very much
language-independent, which is what many of us have been trying to 
explain for a while.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > Yes.  What makes Ada somewhat special is that it is quite common for Ada that
> > those are not integer constants (of sizetype), but variables or
> > expressions (of sizetype).
>
> No.  If you have a[i], in any language, the computation of the offset from
> the start of A is done in sizetype and that's normally an expression.
>
> It's certaily true that you can have *more complex* sizetype expressions
> in Ada than in C, but that's relative and Mark's example yesterday showed
> that sizetype expressions can be even more complex in C++ than Ada.
>
> We're seeing the *optimization* issue more in Ada because very long
> expressions occur more there, but the definitional issue is very much
> language-independent, which is what many of us have been trying to
> explain for a while.

Sure.  Just we didn't see the optimization issue in C code (yet).  Of course
a C testcase is even more appreciated than an Ada one ;)

Another difference that might contribute to this optimization difference between
C and Ada is that appearantly sizetype in Ada is signed compared to other
languages where it is unsigned.  Now, if it is a great idea to allow the FEs to
specify signedness of a middle-end internal type is another question ;)

So I propose to define all sizetypes as having undefined overflow (the same
as for pointers) as this will likely cause the least problems with mismatched
semantics of involved types in expressions.  If we do that we should see the
optimization issues in C as well.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> So I propose to define all sizetypes as having undefined overflow (the same
> as for pointers) as this will likely cause the least problems with mismatched
> semantics of involved types in expressions.  If we do that we should see the
> optimization issues in C as well.

No you won't because people don't use variable-length arrays in C that much:
it's rare to see them *at all*.  But it's not at all uncomon in real Ada
code to have a dozen or more variable-length arrays in a single record.

But I also don't understand why pointers and sizetypes should have anything
like similar properties.  Sizetypes talk about sizes and offsets and 
pointers talk about addresses: those seem very different to me.

As a pragmatic matter, the reason you want pointers to have undefined
overflow semantics are so that you don't lose loop optimizations when pointers
are used as bivs, which is very common while computations involving the
addition and subtraction of pointers don't get very complicated.

It's exactly the other way around for sizetypes: they aren't bivs, so
there's no advantage in having undefined overflow semantics, but they ARE
used in complex computations, where having wrapping semantics will allow
better optimizations.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > So I propose to define all sizetypes as having undefined overflow (the same
> > as for pointers) as this will likely cause the least problems with mismatched
> > semantics of involved types in expressions.  If we do that we should see the
> > optimization issues in C as well.
>
> No you won't because people don't use variable-length arrays in C that much:
> it's rare to see them *at all*.  But it's not at all uncomon in real Ada
> code to have a dozen or more variable-length arrays in a single record.
>
> But I also don't understand why pointers and sizetypes should have anything
> like similar properties.  Sizetypes talk about sizes and offsets and
> pointers talk about addresses: those seem very different to me.
>
> As a pragmatic matter, the reason you want pointers to have undefined
> overflow semantics are so that you don't lose loop optimizations when pointers
> are used as bivs, which is very common while computations involving the
> addition and subtraction of pointers don't get very complicated.

Yes.

> It's exactly the other way around for sizetypes: they aren't bivs, so
> there's no advantage in having undefined overflow semantics, but they ARE
> used in complex computations, where having wrapping semantics will allow
> better optimizations.

The problem I see is that we mix pointers and sizetype variables and in that
way effectively have both, undefined overflow and wrapping which will likely
cause problems.  Of course these problems would exist right now, so maybe
they do not happen, or at least they happen very seldom and don't yet cause
miscompilations.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> The problem I see is that we mix pointers and sizetype variables

I think that's a bug and we try not to do that.  The idea is that you
compute the entire offset as a sizetype and then add it, ONCE, to a pointer.
Indeed we shouldn't be doing all sorts of calculations involving both, but
I don't think we do, at least not commonly, since most code is careful to
do it the above way.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> It was my understanding during this whole thread, that this sizetype with 
> the funny guarantees only can come out of the Ada frontend (and therefore 
> needs to be dealt with in the middle end), and should never be produced by 
> the other languages, in particular not C or C++.  

EVERY front end produces sizetypes because that's what we put in TYPE_SIZE,
etc of types!

> My understanding is supported by the comment in front of the 
> TYPE_IS_SIZETYPE definition in tree.h where it explicitely mentions that 
> size_t should not have this flag set.

Right, it shouldn't.  sizetypes are NOT those types, but are INTERNAL
types used to communicate size and offset information between the front
end and the middle end.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > It was my understanding during this whole thread, that this sizetype with 
> > the funny guarantees only can come out of the Ada frontend (and therefore 
> > needs to be dealt with in the middle end), and should never be produced by 
> > the other languages, in particular not C or C++.  
> 
> EVERY front end produces sizetypes because that's what we put in TYPE_SIZE,
> etc of types!

Yes, and that's arguably a bug.  I don't see any reasons why the values 
in TYPE_SIZE should be of a type with these properties instead of being a 
simple internal unsigned integer type.

> > My understanding is supported by the comment in front of the 
> > TYPE_IS_SIZETYPE definition in tree.h where it explicitely mentions 
> > that size_t should not have this flag set.
> 
> Right, it shouldn't.  sizetypes are NOT those types, but are INTERNAL 
> types used to communicate size and offset information between the front 
> end and the middle end.

We can use a normal type representing whole numbers for that, _and_ do it 
right at that.  E.g. that offsets of course need to be represented by some 
other type than sizes (the latter being unsigned, the former being 
signed).

As shown we can't calculate with sizetypes in C anyway, so would have to 
convert back and forth between them and unsigned for any arithmetic, which 
seems dubious at best.  The only use for it seems to be for the Ada 
frontend to communicate its size and offset information to the middle end.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> On Thu, 11 Oct 2007, Richard Kenner wrote:
>
> > > It was my understanding during this whole thread, that this sizetype with
> > > the funny guarantees only can come out of the Ada frontend (and therefore
> > > needs to be dealt with in the middle end), and should never be produced by
> > > the other languages, in particular not C or C++.
> >
> > EVERY front end produces sizetypes because that's what we put in TYPE_SIZE,
> > etc of types!
>
> Yes, and that's arguably a bug.  I don't see any reasons why the values
> in TYPE_SIZE should be of a type with these properties instead of being a
> simple internal unsigned integer type.

The only reason to have sizetype is that there may be no language defined
integral type of the required precision (which is the precision of
pointers AFAIK).
So it does make sense to have this special sizetype (you could call it
intptr_t of course), and it might also make sense to treat overflow of
the signed
variant as wrapping (though I'd argue we should match overflow behavior of
pointers as we mainly use sizetypes to offset pointers or compute differences
of them - which would make overflow of sizetypes undefined and not wrapping).

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> The only reason to have sizetype is that there may be no language defined
> integral type of the required precision (which is the precision of
> pointers AFAIK).

No, it's needed to be sure that there's a consistent type used for all
sizing calculations in the middle-end.  In fact, it is normally REQUIRED
that there be a user-visible type with the same precision and signedness.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Guenther wrote:

> The only reason to have sizetype is that there may be no language defined
> integral type of the required precision (which is the precision of
> pointers AFAIK).

I'm not argueing against the existence of a type-tree stored in a global 
variable named 's?sizetype'.  I'm arguing against that type-tree being an 
integer type with strange semantics like the current ill-defined 
TYPE_IS_SIZETYPE property.  It unfortunately doesn't help that the strange 
properties are called "sizetype" and the variable is called "sizetype" and 
the expected semantics and use-case also is best conveyed with the single 
word "sizetype".

Actually I'm arguing for that type-tree being an unsigned integer type 
of the same width as pointers, without a name, throughout the whole 
compiler, and be done with this.

> So it does make sense to have this special sizetype (you could call it
> intptr_t of course), and it might also make sense to treat overflow of
> the signed
> variant as wrapping (though I'd argue we should match overflow behavior of
> pointers as we mainly use sizetypes to offset pointers or compute differences
> of them - which would make overflow of sizetypes undefined and not wrapping).

The difference is, that we don't calculate with pointers (so it's okay 
that overflow is undefined, as this simply can't happen), but we do have 
to calculate with sizetype and offsettype (I'm making up the latter), and 
the kind of arithmetics we do on them (e.g. what Mark has shown) argues 
for wrapping on overflow, even on the conceptually signed offsettype.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Yes, and that's arguably a bug.  I don't see any reasons why the values 
> in TYPE_SIZE should be of a type with these properties instead of being a 
> simple internal unsigned integer type.

You lost me here.  What are "these properties"?  And you can't have it be
unsigned in cases when some of the values might be negative!

sizetypes have been around in GCC since day one and have been the way that
front ends communicate sizing information to the rest of the compiler.
It's been a key to how the layout routines work.  If you're proposing some
massive change here, it's important that you have a clear idea of what's
happening currently.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > Yes, and that's arguably a bug.  I don't see any reasons why the values 
> > in TYPE_SIZE should be of a type with these properties instead of being a 
> > simple internal unsigned integer type.
> 
> You lost me here.  What are "these properties"?  And you can't have it be
> unsigned in cases when some of the values might be negative!

"these properties" are those which you and Eric expected sizetype to have, 
and where we then had this very thread to actually try and spell out the 
properties, i.e. those properties which you initially "defined" as "all 
optimizations are allowed".  We later came up with the overflow_ignored 
property IIRC, but I'm still arguing that we probably don't need that for 
our sizetypes.  You still weren't able to show a testcase where it 
matters I believe.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> "these properties" are those which you and Eric expected sizetype to have, 
> and where we then had this very thread to actually try and spell out the 
> properties, i.e. those properties which you initially "defined" as "all 
> optimizations are allowed".  

One can argue about what those properties ought to be, but they clearly
have *some* properties!  And there's no particular reason to believe those
should match those of any user-visible type, since they are used in very
different ways than any user-visible type.

> You still weren't able to show a testcase where it matters I believe.

Being able to *show* a test case and *having* one aren't the same!  The
problem here is that it's only going to occur in large programs and those
are proprietary.  It's a lot of work to sanitize such a large test case.
Conceptually, it's easy to describe: we're talking about records where
there are a large number of variable-length arrays, some of which have the
same index and some of which do not, and we're trying to simplify the
computation of the offset of the later fields ni the record.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > "these properties" are those which you and Eric expected sizetype to have, 
> > and where we then had this very thread to actually try and spell out the 
> > properties, i.e. those properties which you initially "defined" as "all 
> > optimizations are allowed".  
> 
> One can argue about what those properties ought to be, but they clearly 
> have *some* properties!

Of course.  I think "unsigned, wrapping overflow" are these properties, 
hence no need for a special sizetypiness.

> And there's no particular reason to believe those should match those of 
> any user-visible type, since they are used in very different ways than 
> any user-visible type.

Please, don't go that route again.  I'm not talking about user-visible 
types.  I never was.  I'm talking about the properties of sizetype (the 
global tree node), and I'm arguing that it simply should be an unsigned 
integer type without other special properties.  Don't repeat the argument 
of Ada needing negative values there, I think it's a red herring as  
negative values can be represented in unsigned types just fine, it's just 
a matter of interpreting it correctly.

> Being able to *show* a test case and *having* one aren't the same!  The 
> problem here is that it's only going to occur in large programs and 
> those are proprietary.  It's a lot of work to sanitize such a large test 
> case. Conceptually, it's easy to describe: we're talking about records 
> where there are a large number of variable-length arrays, some of which 
> have the same index and some of which do not, and we're trying to 
> simplify the computation of the offset of the later fields ni the 
> record.

Okay, so conceptually it's like:

struct S {
  int a1[n1*n2];
  int a2[n2*n1];
  int a3[n3];
} s;  /* so a1 and a2 have the same number of elements */

And then you access this in e.g. such way:

for (i = start; i <= end; i++)
  use (s.a1[i], s.a2[i+2], s.a3[i]);

And you of course want that the necessary index calculations are done as 
optimally as possible, i.e. that the three expressions (i), 
((i+1)+(n1*n2)) and (i+(n1*n2)+(n2*n1)) are optimized.  Would that be 
a correct description of the situation (I'm assuming it's more complicated 
of course)?


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

Michael Matz <matz@suse.de> writes:

> > One can argue about what those properties ought to be, but they clearly 
> > have *some* properties!
> 
> Of course.  I think "unsigned, wrapping overflow" are these properties, 
> hence no need for a special sizetypiness.

Look for the case
      if ((TYPE_OVERFLOW_UNDEFINED (ctype)
	   || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
in fold-const.c.

That is an optimization that sizetypes should have but that unsigned
wrapping types do not.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Ian Lance Taylor wrote:

> Michael Matz <matz@suse.de> writes:
> 
> > > One can argue about what those properties ought to be, but they clearly 
> > > have *some* properties!
> > 
> > Of course.  I think "unsigned, wrapping overflow" are these properties, 
> > hence no need for a special sizetypiness.
> 
> Look for the case
>       if ((TYPE_OVERFLOW_UNDEFINED (ctype)
> 	   || (TREE_CODE (ctype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (ctype)))
> in fold-const.c.
> 
> That is an optimization that sizetypes should have but that unsigned
> wrapping types do not.

Hmm, so how do these transformation behave if presented with values (in 
sizetype) which _do_ overflow, e.g. from the reassociated example of Mark?
They will carry out the transformation and the resulting value then will 
be different?

E.g. one transformation it does is (X*c1)/c2 to X*(c1/c2) if c1%c2==0, for 
sizetypes (und OVERFLOW_UNDEFINED ones).

Suppose that X is the latter part of Marks reassociated expression, C-B, 
with B large, so that (C-B)*c1 would overflow.  Nevertheless the 
transformation would be done, resulting in a different outcome.  The 
reassoc was okay because this was in sizetype (or as I argue in any 
overflow wrapping unsigned type), but the fold-const transformation was 
invalid.  _Even_ with sizetype.  So, I'm not sure if that special-casing 
of sizetype in fold-const is even correct.  If you disagree, why?


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> E.g. one transformation it does is (X*c1)/c2 to X*(c1/c2) if c1%c2==0, for 
> sizetypes (und OVERFLOW_UNDEFINED ones).
> 
> Suppose that X is the latter part of Marks reassociated expression, C-B, 
> with B large, so that (C-B)*c1 would overflow.

I'm having trouble following your example.  It seems it would be converting
an expression that *did* overflow into one that doesn't.  Indeed, how could
it ever be doing otherwise since the product is always smaller in the
resulting transformation.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > E.g. one transformation it does is (X*c1)/c2 to X*(c1/c2) if c1%c2==0, for 
> > sizetypes (und OVERFLOW_UNDEFINED ones).
> > 
> > Suppose that X is the latter part of Marks reassociated expression, C-B, 
> > with B large, so that (C-B)*c1 would overflow.
> 
> I'm having trouble following your example.  It seems it would be 
> converting an expression that *did* overflow into one that doesn't.  

The point is that (X*c1)/c2 and X*(c1/c2) are _different_ for some values 
of X,c1 and c2 (namely sometimes but not all the time when X*c1 
overflows).  Assuming that the first value was the correct one (for 
instance zero) we will have introduced a miscompilation.  We have two ways 
for fixing this:
1) declare the precondition (the initial overflow) to be invalid.
2) don't do the transformation in flow

Solution (1) would require that overflow in sizetype is not ignored, but 
undefined.  Then we couldn't have done the reassociation which created 
this problem.  But that is something you explicitely didn't want.

Solution (2) would require removing the exception for sizetype, at which 
point it again looks more like an unsigned wrapping type.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> The point is that (X*c1)/c2 and X*(c1/c2) are _different_ for some values 
> of X,c1 and c2 (namely sometimes but not all the time when X*c1 
> overflows).  Assuming that the first value was the correct one (for 
> instance zero) we will have introduced a miscompilation.  We have two ways 
> for fixing this:
> 1) declare the precondition (the initial overflow) to be invalid.
> 2) don't do the transformation in flow
> 
> Solution (1) would require that overflow in sizetype is not ignored, but 
> undefined.  Then we couldn't have done the reassociation which created 
> this problem.  But that is something you explicitely didn't want.
> 
> Solution (2) would require removing the exception for sizetype, at which 
> point it again looks more like an unsigned wrapping type.

Again, you are trying to interpret the semantics of sizetypes in terms of
those more-properly used for user-defined types.  As you say, sizetypes
have the property that if the "complete" expression would overflow, the
program is illegal, so the above transformation is fine.  But for the
association operations, we want to act as if it wrapped.

But what's the problem here?  We have a flag, TYPE_IS_SIZETYPE.  We have
a transformation and we want to decide if it's safe for sizetypes.  So we
look at it and figure it out, knowing what we know about sizetypes.  If it's
safe, we say "|| TYPE_IS_SIZETYPE" and if not we say "&& !TYPE_IS_SIZETYPE".
It's as simple as that.  There's no reason why we have to try to invent
yet another flag that describes the semantics: we already have one that
does the job just fine!

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > The point is that (X*c1)/c2 and X*(c1/c2) are _different_ for some values 
> > of X,c1 and c2 (namely sometimes but not all the time when X*c1 
> > overflows).  Assuming that the first value was the correct one (for 
> > instance zero) we will have introduced a miscompilation.  We have two ways 
> > for fixing this:
> > 1) declare the precondition (the initial overflow) to be invalid.
> > 2) don't do the transformation in flow
> > 
> > Solution (1) would require that overflow in sizetype is not ignored, but 
> > undefined.  Then we couldn't have done the reassociation which created 
> > this problem.  But that is something you explicitely didn't want.
> > 
> > Solution (2) would require removing the exception for sizetype, at which 
> > point it again looks more like an unsigned wrapping type.
> 
> Again, you are trying to interpret the semantics of sizetypes in terms of
> those more-properly used for user-defined types.  As you say, sizetypes
> have the property that if the "complete" expression would overflow, the
> program is illegal, so the above transformation is fine.

Ehh?  Above I'm explicitely showing why the transformation is _not_ fine, 
yet you read it as the opposite?


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Ehh?  Above I'm explicitely showing why the transformation is _not_ fine, 
> yet you read it as the opposite?

It *is* fine because we know that the overflow that would prevent the
transformation from being valid can't happen for valid programs.  You
always need to go back to what sizetypes are supposed to represent to
decide whether a transformation is valid or not.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> But what's the problem here?  We have a flag, TYPE_IS_SIZETYPE.  We have
> a transformation and we want to decide if it's safe for sizetypes.  So we
> look at it and figure it out, knowing what we know about sizetypes.  If it's
> safe, we say "|| TYPE_IS_SIZETYPE" and if not we say "&& !TYPE_IS_SIZETYPE".
> It's as simple as that.  There's no reason why we have to try to invent
> yet another flag that describes the semantics: we already have one that
> does the job just fine!

But the rest of us don't understand the semantics of sizetypes.  That
is why we are trying to pin it down in terms of other flags.  We
understand what those other flags mean.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> But the rest of us don't understand the semantics of sizetypes.  That
> is why we are trying to pin it down in terms of other flags.  We
> understand what those other flags mean.

The problem is that it's becoming clearer and clearer that the semantics of
sizetypes CAN'T be expressed in terms of those other flags!

One thing to remember is that the vast majority of operations in sizetypes
aren't generated by the front end, but instead by the middle end itself in
stor-layout.c!  So it's primarily optimizing its own operations and
therefore can do so in a consistent manner.

Essentially, what we have to do when we see a transformation that might 
potentially be applied to sizetypes is to rely on our understanding of
the semantics of those operations to see whether or not that transformation
is safe or not.

That set of decisions may or may not corespond to some other set of flags
that we're using for other (unrelated) types.  I don't see it as a big deal
if it doesn't.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> > But the rest of us don't understand the semantics of sizetypes.  That
> > is why we are trying to pin it down in terms of other flags.  We
> > understand what those other flags mean.
> 
> The problem is that it's becoming clearer and clearer that the semantics of
> sizetypes CAN'T be expressed in terms of those other flags!

The flags aren't fixed in stone.  In fact, I just introduced them
earlier this year.  So all this tells me is that we need to change the
flags.  I already proposed such a change
(http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00053.html).  Nobody has
yet explained why my proposal wouldn't work.

> Essentially, what we have to do when we see a transformation that might 
> potentially be applied to sizetypes is to rely on our understanding of
> the semantics of those operations to see whether or not that transformation
> is safe or not.
> 
> That set of decisions may or may not corespond to some other set of flags
> that we're using for other (unrelated) types.  I don't see it as a big deal
> if it doesn't.

Again, it's a big deal because at the moment most of the gcc
maintainers don't understand the semantics.  After all this discussion
I still barely have a handle on what you want.  You are talking in
vague generalities, and you are unable to give us any actual code.
It's no wonder we remain confused.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Ian Lance Taylor wrote:

>>> But the rest of us don't understand the semantics of sizetypes.  That
>>> is why we are trying to pin it down in terms of other flags.  We
>>> understand what those other flags mean.

Right.  I don't think it's important per se whether or not we have a
TYPE_IS_SIZETYPE flag or not.  But, I do think it's important that we
define the semantics of sizetypes, if we're going to use them.

I agree with others in this thread that I don't understand what you
think the semantics are.  I do understand the goal: permit more
optimizations of expressions involving sizetypes.  But, I don't
understand what the semantics are that achieve that goal.

Kenner, perhaps you could define the semantics as differences from an
ordinary integer type?  "A sizetype is like an ordinary INTEGER_TYPE,
except that ..."?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Right.  I don't think it's important per se whether or not we have a
> TYPE_IS_SIZETYPE flag or not.  But, I do think it's important that we
> define the semantics of sizetypes, if we're going to use them.

Agreed.

> Kenner, perhaps you could define the semantics as differences from an
> ordinary integer type?  "A sizetype is like an ordinary INTEGER_TYPE,
> except that ..."?

The problem is that all I can do now is offer an *operational* definition,
so it would be "... except that all the operations on it are generated by
the compiler as part of computations of sizes and offsets so that we can
prove certain properties of those expressions that would not be true for
integer types in more general usages".

Yes, it might be nice to enumerate that list of properties, but I don't see
it as critical that we do so, since instead we can just ask the question
for each case (optimization) that comes up.  For each such, either we feel
we can make the proof, meaning the optimization is safe, or we can't make
the proof, meaning it isn't safe.  For a first approximation, we can
certainly say that if the optimization is safe assuming a wrapping
semantics than it's safe for sizetypes.  But we also know that the converse
is NOT true and there may be some individual transformations that we know
ARE safe for sizetypes (e.g, the (a*c1)/c2 example) even though they aren't
true for general integer types that wrap. 

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Richard Kenner wrote:

> The problem is that all I can do now is offer an *operational* definition,
> so it would be "... except that all the operations on it are generated by
> the compiler as part of computations of sizes and offsets so that we can
> prove certain properties of those expressions that would not be true for
> integer types in more general usages".
> 
> Yes, it might be nice to enumerate that list of properties, but I don't see
> it as critical that we do so, since instead we can just ask the question
> for each case (optimization) that comes up. 

I don't think that's good enough.  If we can't specify this better, then
I suspect that, over time, it's going to break, and people will
eventually just rip it out.  So far, we've got no test cases and no
explanation of the semantics.  So, I don't think you should be surprised
if the middle-end maintainers decide they don't understand the point and
replace it with, essentially, the user-level size_t.

That's going to hurt Ada hardest because in C/C++, there aren't very
many run-time computations involving sizes; most of what we do with
sizes is folded away at compile-time, or is converted from sizetype to
the user-level size_t anyhow.  (For example, calling an inline C++ new
operator converts to size_t before doing the inlining, so any
computations on the size done within the body of the operator are going
to be done on the user-level type, and optimization limitations that
apply to ordinary unsigned integer types will end up applying here too.)

The only place I can actually see uses of TYPE_IS_SIZETYPE are
fold-const.c and tree.c.  And, in both cases, it looks like we do
exactly one thing: treat sizetypes are sign-extended even when
TYPE_UNSIGNED.  That begs the question: why aren't they signed, or why
do we care about bits outside their precision?  Where are the extra
optimizations happening that you're talking about?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I don't think that's good enough.  If we can't specify this better, then
> I suspect that, over time, it's going to break, and people will
> eventually just rip it out.  

I think we CAN specific it better, but it's just not that easy.

> That begs the question: why aren't they signed

I think because you run into problems in corner cases in C if size_t and
sizetype don't have the same precision and signedness or, more precisely,
if you can't encode a value that's a valid result of size_t in sizetype.

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Richard Kenner wrote:

>> That begs the question: why aren't they signed
> 
> I think because you run into problems in corner cases in C if size_t and
> sizetype don't have the same precision and signedness or, more precisely,
> if you can't encode a value that's a valid result of size_t in sizetype.

That's why C has size_t and ptrdiff_t.  I'd expect that DECL_SIZE and
friends to have an unsigned sizetype.  I'd expect things like the
difference between two field offsets to have a signed sizetype.
Obviously, if we need to represent all possible differences, then you
need a wider type than sizetype to represent that -- just as ptrdiff_t
cannot represent all possible differences between pointers in C.

In any case, I think we've just about answered what the semantics of the
current sizetype are:

1. Unsigned sizetypes are sign-extended, as if they were signed.  (See
fit_double_type.)

So, in particular, when you pass (0, 0xffffffff) to fit_double_type,
using an unsigned sizetype as a the type, you end up with (0xffffffff,
0xffffffff) as your representation, assuming 32-bit HOST_WIDE_INT and
32-bit sizetype.  Other checks seem to be consequences of that; you
cannot make certain assumptions about widening, you can ignore the
sign-extended bits when doing host_integerp, etc.

2. TREE_OVERFLOW is set for operations that overflow on an unsigned
sizetype, as if they were signed.  (See int_const_binop.)

3. Unsigned sizetypes are treated as if TYPE_OVERFLOW_UNDEFINED (i.e.,
as if they were signed) was defined in the case of multiply/division
that cancel.  (See extract_muldiv_1.)

I don't think we know the *why* for (1) and (2) at this point.  We do
have a justification for (3); this is your claim that when we generate
these combinations we mean to allow reassociation.

I'm not sure how sizetype is a win over representing sizes as size_t,
differences between sizes as ptrdiff_t, and performing operations on
sizes by first doing a bit-preserving cast from size_t to ptrdiff_t,
then doing all the operations on ptrdiff_t, and then casting back if
necessary.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> So, in particular, when you pass (0, 0xffffffff) to fit_double_type,
> using an unsigned sizetype as a the type, you end up with (0xffffffff,
> 0xffffffff) as your representation, assuming 32-bit HOST_WIDE_INT and
> 32-bit sizetype. 

I wasn't aware we do that and it seems peculiar to me.  I doubt it matters
either way how we handle that, though.

> 3. Unsigned sizetypes are treated as if TYPE_OVERFLOW_UNDEFINED (i.e.,
> as if they were signed) was defined in the case of multiply/division
> that cancel.  (See extract_muldiv_1.)

In that case, yes, but treated as if overflow wraps for the other case
(the association cases).

> I'm not sure how sizetype is a win over representing sizes as size_t,
> differences between sizes as ptrdiff_t, and performing operations on
> sizes by first doing a bit-preserving cast from size_t to ptrdiff_t,
> then doing all the operations on ptrdiff_t, and then casting back if
> necessary.

Because size_t, being user-visible, has to have a consistent view of
the handling of overflow (whether it's defined or wraps) and sizetypes
don't and the latter allows more optimizations.  As to conversions, I
don't see much code that computes the difference between sizes (indeed I
can't think of any such at the moment), so I can't really comment on
it, but I do worry about adding too many conversions for lots of reasons.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/12/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Kenner wrote:
>
> >> That begs the question: why aren't they signed
> >
> > I think because you run into problems in corner cases in C if size_t and
> > sizetype don't have the same precision and signedness or, more precisely,
> > if you can't encode a value that's a valid result of size_t in sizetype.
>
> That's why C has size_t and ptrdiff_t.  I'd expect that DECL_SIZE and
> friends to have an unsigned sizetype.  I'd expect things like the
> difference between two field offsets to have a signed sizetype.
> Obviously, if we need to represent all possible differences, then you
> need a wider type than sizetype to represent that -- just as ptrdiff_t
> cannot represent all possible differences between pointers in C.
>
> In any case, I think we've just about answered what the semantics of the
> current sizetype are:
>
> 1. Unsigned sizetypes are sign-extended, as if they were signed.  (See
> fit_double_type.)
>
> So, in particular, when you pass (0, 0xffffffff) to fit_double_type,
> using an unsigned sizetype as a the type, you end up with (0xffffffff,
> 0xffffffff) as your representation, assuming 32-bit HOST_WIDE_INT and
> 32-bit sizetype.  Other checks seem to be consequences of that; you
> cannot make certain assumptions about widening, you can ignore the
> sign-extended bits when doing host_integerp, etc.

I am going to try to get rid of this behavior in the 4.4 timeframe.  It doesn't
really make sense.

> 2. TREE_OVERFLOW is set for operations that overflow on an unsigned
> sizetype, as if they were signed.  (See int_const_binop.)

Likewise.  The effect of removing this is that we get some diagnostic
regressions in the C frontend which I need to look at.

> 3. Unsigned sizetypes are treated as if TYPE_OVERFLOW_UNDEFINED (i.e.,
> as if they were signed) was defined in the case of multiply/division
> that cancel.  (See extract_muldiv_1.)

There are places that use the signedness of the sizetype to determine
overflow behavior and there are places that use TYPE_IS_SIZETYPE
to override that.  I think this is bad and needs to be generalized.
IMHO preferably by getting rid of TYPE_IS_SIZETYPE.

> I don't think we know the *why* for (1) and (2) at this point.  We do
> have a justification for (3); this is your claim that when we generate
> these combinations we mean to allow reassociation.

Note that for all frontends apart from Ada sizetype is unsigned and
thus we allow reassociation based on the fact that unsigned types
have wrapping overflow semantics.  Ada has a signed sizetype for
a reason that is unknown to me.  I like to get rid of this particular
difference - after all, sizetype is supposed to be a middle-end type.

> I'm not sure how sizetype is a win over representing sizes as size_t,
> differences between sizes as ptrdiff_t, and performing operations on
> sizes by first doing a bit-preserving cast from size_t to ptrdiff_t,
> then doing all the operations on ptrdiff_t, and then casting back if
> necessary.

The semantics are mostly hidden in the size_binop and size_diffop
functions which make sure to return results in proper signedness.
That is, the difference of two sizetypes has type signed sizetype.  So,
with the lack of testcases I see no clear win of a special sizetype.  And
if the optimization opportunities are all from expressions generated by
stor-layout then we can do the optimizations there, based on the fact
that at this point we should know most about the actual values
involved and can prove validity of optimizations best.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> The only place I can actually see uses of TYPE_IS_SIZETYPE are
> fold-const.c and tree.c.  And, in both cases, it looks like we do
> exactly one thing: treat sizetypes are sign-extended even when
> TYPE_UNSIGNED.

We also allow more optimizations if TYPE_IS_SIZETYPE is set.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> The flags aren't fixed in stone.  In fact, I just introduced them
> earlier this year.  So all this tells me is that we need to change the
> flags.

Why?  As I keep saying, we already HAVE a flag to denote sizetypes: we
don't need another one but can just use THAT one.  Why muck around with
flags that are designed for an entirely different purpose, namely to
characterize user-visible types.

> Again, it's a big deal because at the moment most of the gcc
> maintainers don't understand the semantics.  After all this discussion
> I still barely have a handle on what you want.  You are talking in
> vague generalities, and you are unable to give us any actual code.
> It's no wonder we remain confused.

It is indeed hard to characterize the semantics of sizetypes in anything
other than a case-by-case manner, as this discussion has shown.  But, as I
said, "the code" is in stor-layout.c: that's where the vast majority of the
sizetype operations are found.  I think the C front end has almost none,
the Ada front end has only a few (mostly related to zero-length arrays),
and I don't know how many the C++ front-end has, but I doubt it's very many
either.  So if we need to understand what types of operations are being
done and what those operations are entitled to assume, stor-layout is the
place to look.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> The flags aren't fixed in stone.  In fact, I just introduced them
> earlier this year.  So all this tells me is that we need to change the
> flags.  I already proposed such a change
> (http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00053.html).  Nobody has
> yet explained why my proposal wouldn't work.

From my point of view, your proposal (TYPE_IGNORE_OVERFLOWS + 
TYPE_OVERFLOW_WRAPS) is OK.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/14/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > The flags aren't fixed in stone.  In fact, I just introduced them
> > earlier this year.  So all this tells me is that we need to change the
> > flags.  I already proposed such a change
> > (http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00053.html).  Nobody has
> > yet explained why my proposal wouldn't work.
>
> From my point of view, your proposal (TYPE_IGNORE_OVERFLOWS +
> TYPE_OVERFLOW_WRAPS) is OK.

I don't want to have TYPE_IGNORE_OVERFLOWS.  Matters are complicated
enough already.  I also like you to revisit the decision to make Ada sizetype
signed.  If there are optimization regressions for expressions created by
stor-layout.c solve them there, as that is the place where enough knowledge
about the involved magnitudes is available.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> I don't want to have TYPE_IGNORE_OVERFLOWS.  Matters are complicated
> enough already.

Strange argument, all the more so than this subsumes an already existing flag.
So we're ready to invent CHANGE_DYNAMIC_TYPE_EXPR for some quirks of C++ and 
balk at encapsulating an existing flag into a new macro?

> I also like you to revisit the decision to make Ada sizetype signed.

Well, we can have negative values for such types in Ada.

> If there are optimization regressions for expressions created by
> stor-layout.c solve them there, as that is the place where enough knowledge
> about the involved magnitudes is available. 

So we duplicate fold-const.c in stor-layout.c?

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I don't want to have TYPE_IGNORE_OVERFLOWS.  Matters are complicated
> enough already.  

I don't follow.  But it doesn't matter if the flag is actually set or not
since TYPE_IS_SIZETYPE can imply it.

> I also like you to revisit the decision to make Ada sizetype signed.

I don't think that's a *decision* but is instead required.  The current
code assumes that, using C terms, size_t and sizetype have the same signedness.
That forces sizetype to be signed in Ada.  But why is this an issue? What
code cares whether it's signed or not?  We already have a flag we can
use to determine what optimizatins get done: TYPE_IS_SIZETYPE.  That's
set in both the signed and unsigned case and is completely unambiguous.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/14/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > I don't want to have TYPE_IGNORE_OVERFLOWS.  Matters are complicated
> > enough already.
>
> I don't follow.  But it doesn't matter if the flag is actually set or not
> since TYPE_IS_SIZETYPE can imply it.

Set?  I thought we would have

#define TYPE_IGNORE_OVERFLOW (type) TYPE_IS_SIZETYPE (type)

I am opposing to TYPE_IGNORED_OVERFLOW because with the
definition above its semantics are as unclear as sizetypes.

> > I also like you to revisit the decision to make Ada sizetype signed.
>
> I don't think that's a *decision* but is instead required.  The current
> code assumes that, using C terms, size_t and sizetype have the same signedness.

Where does it do that?  I am not aware of any such relation in
middle-end code.

> That forces sizetype to be signed in Ada.  But why is this an issue? What
> code cares whether it's signed or not?

It's an "issue" because it makes optimizations performed on Ada
sizetype expressions different than C sizetype expressions.  It's an "issue"
because we have code looking at the sign of types (arguably also a
bug for pointer types).  If no code cares whether it's signed or not we
can as well make its sign consistent.  After all we also have
ssizetype - with Ada we do not have _any_ unsigned "sizetype".

> We already have a flag we can
> use to determine what optimizatins get done: TYPE_IS_SIZETYPE.  That's
> set in both the signed and unsigned case and is completely unambiguous.

Right.  So ssizetype and sizetype have the same semantics?  Why do
we have both of them if nobody cares about signedness of sizetype?
Why don't we simply drop ssizetype and make sizetype signed?  This
would "sizetypes are sign-extended" the natural thing.

The point is the current situation is 1) confusing 2) redundant 3) a mess
(IMHO).  I want to reduce the mess, not add to it.  It is already hard
enough to judge what flags you need to test on optimizations on integer
types, now you want to add another one that should be considered?
No thanks.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Set?  I thought we would have
> 
> #define TYPE_IGNORE_OVERFLOW (type) TYPE_IS_SIZETYPE (type)

I don't see what that would serve.

> Where does it do that?  I am not aware of any such relation in
> middle-end code.

Not middle-end code, but front end.  The point is that sizetype must
have the same signedness and precision as the C size_t.

> It's an "issue" because it makes optimizations performed on Ada
> sizetype expressions different than C sizetype expressions.  

But that's wrong and where this whole thread started: if the code tests
TYPE_IS_SIZETYPE then it doesn't matter if it's signed or unsigned.

> Right.  So ssizetype and sizetype have the same semantics?  

Not sure what "semantics" means in this context.  One might be signed
and one might be unsigned.  If you mean "same semantics in the way
we generate expressions for them", then yes.

> Why do we have both of them if nobody cares about signedness of
> sizetype?

Who said nobody cares?  We don't care about it for optimization purposes
but we certainly do in terms of the types themselves.

> The point is the current situation is 1) confusing 2) redundant 3) a mess
> (IMHO).  

It's not confusing to me and it's been this way for decades.  There's
a major burden that must be met on a proposal to change it.

> I want to reduce the mess, not add to it.  It is already hard
> enough to judge what flags you need to test on optimizations on integer
> types, now you want to add another one that should be considered?

No.  I want the optimizations to correctly take into account a flag that's
been around for decades.  I am *not* proposing linking these with the other
flags: indeed I'm specifically *against* doing that for just the reasons you
mention.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Sun, 14 Oct 2007, Richard Kenner wrote:

> > The point is the current situation is 1) confusing 2) redundant 3) a 
> > mess (IMHO).
> 
> It's not confusing to me and it's been this way for decades.  There's a 
> major burden that must be met on a proposal to change it.

But it wasn't you who fixed the last dozen bugs which involved sizetypes 
in some way or another.  It was Richard G., and for some of those fixes I 
sat besides him, and we know that sizetypes _definitely_ are a problem for 
the middle-end because of their peculiar semantics.  No matter if you 
agree or not agree that the semantics, in so far as they exist, are 
peculiar.  I.e. I question your assertion that you _really_ understand 
where sizetypes are involved or not, or should be involved.  A point to 
support that is http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00038.html , 
where you couldn't even be bothered to look at the current GCC sources 
yourself, to look for where sizetypes should have been used too.  They 
aren't special cased in any of the new optimization passes, new being 
something like newer than 5 years.  And that trend will continue as long 
as sizetypes stay in their current form.

> No.  I want the optimizations to correctly take into account a flag 
> that's been around for decades.

Well, obviously that flag was ignored for exactly that long already by 
everyone ever producing a transformation, except for the one introducing 
it and hacking it into fold-const.c .  That doesn't exactly speak for (1) 
the necessity and (2) clarity of the flag.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> we know that sizetypes _definitely_ are a problem for the middle-end
> because of their peculiar semantics.

That may be, but those are the properties and semantics that they such
objects DO have from a conceptual point of view and any other way we
do it they would have the same semantics!  (I'm not saying this very
well, but what I'm trying to say is that those semantics are intrinsic
to the type of calculations that need to be done.)

One can argue that it's too hard to implement them properly, so we ought
to do some subsetting.  But if we do that, then we CERTAINLY should leave
the flag the way it is so that if somebody later wants to do it properly,
they at least have the data to do so.


> I question your assertion that you _really_ understand 
> where sizetypes are involved or not, or should be involved.  A point to 
> support that is http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00038.html , 
> where you couldn't even be bothered to look at the current GCC sources 
> yourself, to look for where sizetypes should have been used too.

I'm sorry, I don't understand the above.  Sizetypes are used for sizes and
positions, so I understand your point.

> They aren't special cased in any of the new optimization passes, new
> being something like newer than 5 years.

And that's a bug that we're trying to fix by this thread.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/15/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > we know that sizetypes _definitely_ are a problem for the middle-end
> > because of their peculiar semantics.
>
> That may be, but those are the properties and semantics that they such
> objects DO have from a conceptual point of view and any other way we
> do it they would have the same semantics!  (I'm not saying this very
> well, but what I'm trying to say is that those semantics are intrinsic
> to the type of calculations that need to be done.)
>
> One can argue that it's too hard to implement them properly, so we ought
> to do some subsetting.  But if we do that, then we CERTAINLY should leave
> the flag the way it is so that if somebody later wants to do it properly,
> they at least have the data to do so.

Let's say it this way - every simplification to the middle-end helps avoiding
(and fixing) obscure bugs in fold-const.  For an example, as exercise for the
reader try to fix PR33779 which we just produced by looking at the
conversion handling from extract_muldiv (which is one "heavy" user of
TYPE_IS_SIZETYPE).  The condition above the transformation that goes
wrong is not exactly easy to understand (nor to fix without
essentially disabling
all of the transformation):

<quote>
    case CONVERT_EXPR:  case NON_LVALUE_EXPR:  case NOP_EXPR:
      /* If op0 is an expression ...  */
      if ((COMPARISON_CLASS_P (op0)
           || UNARY_CLASS_P (op0)
           || BINARY_CLASS_P (op0)
           || VL_EXP_CLASS_P (op0)
           || EXPRESSION_CLASS_P (op0))
          /* ... and is unsigned, and its type is smaller than ctype,
             then we cannot pass through as widening.  */
          && ((TYPE_UNSIGNED (TREE_TYPE (op0))
               && ! (TREE_CODE (TREE_TYPE (op0)) == INTEGER_TYPE
                     && TYPE_IS_SIZETYPE (TREE_TYPE (op0)))
               && (GET_MODE_SIZE (TYPE_MODE (ctype))
                   > GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0)))))
              /* ... or this is a truncation (t is narrower than op0),
                 then we cannot pass through this narrowing.  */
              || (GET_MODE_SIZE (TYPE_MODE (type))
                  < GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (op0))))
              /* ... or signedness changes for division or modulus,
                 then we cannot pass through this conversion.  */
              || (code != MULT_EXPR
                  && (TYPE_UNSIGNED (ctype)
                      != TYPE_UNSIGNED (TREE_TYPE (op0))))))
        break;

      /* Pass the constant down and see if we can make a simplification.  If
         we can, replace this expression with the inner simplification for
         possible later conversion to our or some other type.  */
      if ((t2 = fold_convert (TREE_TYPE (op0), c)) != 0
          && TREE_CODE (t2) == INTEGER_CST
          && !TREE_OVERFLOW (t2)
         && (0 != (t1 = extract_muldiv (op0, t2, code,
                                         code == MULT_EXPR
                                         ? ctype : NULL_TREE,
                                         strict_overflow_p))))
        return t1;
      break;

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Let's say it this way - every simplification to the middle-end helps avoiding
> (and fixing) obscure bugs in fold-const.  

But a sizetype is what it is.  Nothing we do is going to change that.
All we can talk about doing is chosing to ignore certain properties of it
(such as that some optimizations on it are safe).  But in that case,
we should do it by ignoring the flag for those optimizations, not in 
any other way.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

"Richard Guenther" <richard.guenther@gmail.com> writes:

> On 10/14/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > > The flags aren't fixed in stone.  In fact, I just introduced them
> > > earlier this year.  So all this tells me is that we need to change the
> > > flags.  I already proposed such a change
> > > (http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00053.html).  Nobody has
> > > yet explained why my proposal wouldn't work.
> >
> > From my point of view, your proposal (TYPE_IGNORE_OVERFLOWS +
> > TYPE_OVERFLOW_WRAPS) is OK.
> 
> I don't want to have TYPE_IGNORE_OVERFLOWS.  Matters are complicated
> enough already.  I also like you to revisit the decision to make Ada sizetype
> signed.  If there are optimization regressions for expressions created by
> stor-layout.c solve them there, as that is the place where enough knowledge
> about the involved magnitudes is available.

The point of TYPE_IGNORE_OVERFLOWS is not for signed vs. unsigned, but
is rather to permit retaining the optimization currently done for
TYPE_IS_SIZE_TYPE in extract_muldiv_1.

	 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.

We don't want to set TYPE_OVERFLOW_UNDEFINED for sizetypes, because we
want to overflow to wrap, and in particular because we want to permit
reassociation.  We need some way to indicate that this type does not
overflow.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 14 Oct 2007 08:45:53 -0700, Ian Lance Taylor <iant@google.com> wrote:
> "Richard Guenther" <richard.guenther@gmail.com> writes:
>
> > On 10/14/07, Eric Botcazou <ebotcazou@adacore.com> wrote:
> > > > The flags aren't fixed in stone.  In fact, I just introduced them
> > > > earlier this year.  So all this tells me is that we need to change the
> > > > flags.  I already proposed such a change
> > > > (http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00053.html).  Nobody has
> > > > yet explained why my proposal wouldn't work.
> > >
> > > From my point of view, your proposal (TYPE_IGNORE_OVERFLOWS +
> > > TYPE_OVERFLOW_WRAPS) is OK.
> >
> > I don't want to have TYPE_IGNORE_OVERFLOWS.  Matters are complicated
> > enough already.  I also like you to revisit the decision to make Ada sizetype
> > signed.  If there are optimization regressions for expressions created by
> > stor-layout.c solve them there, as that is the place where enough knowledge
> > about the involved magnitudes is available.
>
> The point of TYPE_IGNORE_OVERFLOWS is not for signed vs. unsigned, but
> is rather to permit retaining the optimization currently done for
> TYPE_IS_SIZE_TYPE in extract_muldiv_1.
>
>          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.
>
> We don't want to set TYPE_OVERFLOW_UNDEFINED for sizetypes, because we
> want to overflow to wrap, and in particular because we want to permit
> reassociation.  We need some way to indicate that this type does not
> overflow.

In which case sizetypes semantics are that of an infinite precision
integral type.  In which case an always signed sizetype makes sense.

Of course I don't believe in infinite precision for sizetype as it only
has the precision of pointers [so we'd truncate integer constants too
eagerly].  It looks like giving sizetype mode_for_size (GET_MODE_SIZE
(Pmode)) (or similar) while raising its precision to cover the full
2 * HWI could do the right thing for constants and expansion.  Supposed
that we only ever expand to things that do not overflow - but this is
what Kenner and friends insist on anyway.

Still I don't like at all that sizetype is a frontend-specific type.  Still
I don't like that sign-extension is somehow special for sizetypes.  Still
I will be not the one to audit optimizations if they will go wrong on
sizetypes because they ask for the wrong properties of the types involved.

Why not take the opportunity to clean up the current stuff a bit before
introducing more [lacking a proper noun]?

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Still I don't like at all that sizetype is a frontend-specific type.

Why?  It has to be.  It needs to match the signedness and precision of
size_t and figuring out what that is doesn't seem something that the
middle end should take over from the C front end.

More fundamentally, knowing what the valid range of sizes valid for types
is more a *language* issue, which only the front end can know about,
than one based on modes and sizes that are defined for the middle end.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/15/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > Still I don't like at all that sizetype is a frontend-specific type.
>
> Why?  It has to be.  It needs to match the signedness and precision of
> size_t and figuring out what that is doesn't seem something that the
> middle end should take over from the C front end.
>
> More fundamentally, knowing what the valid range of sizes valid for types
> is more a *language* issue, which only the front end can know about,
> than one based on modes and sizes that are defined for the middle end.

I don't see a reason that sizetype has to match size_t.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I don't see a reason that sizetype has to match size_t.

I'm not sure I correctly remember what the original reason for that
is, but the one that I'm aware of is this: it can't be smaller than
size_t because then you can't represent all sizes that are valid in
the language (which is what the range of size_t is supposed to mean).
But if it's larger than size_t, you are doing run-time calculations in
a wider mode and that's (usually) less efficient.  Since it can't be
smaller and shouldn't be wider, it has to be the same size.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/15/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > I don't see a reason that sizetype has to match size_t.
>
> I'm not sure I correctly remember what the original reason for that
> is, but the one that I'm aware of is this: it can't be smaller than
> size_t because then you can't represent all sizes that are valid in
> the language (which is what the range of size_t is supposed to mean).
> But if it's larger than size_t, you are doing run-time calculations in
> a wider mode and that's (usually) less efficient.  Since it can't be
> smaller and shouldn't be wider, it has to be the same size.

As we use sizetype for offsets of pointers choosing the size of pointers
as the size of sizetypes would make sense for the middle-end.  If that
happens to be the precision of size_t, fine.  I still don't see the connection
to the signedness of sizetype though.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> As we use sizetype for offsets of pointers choosing the size of pointers
> as the size of sizetypes would make sense for the middle-end.  

No, because there's no necessary reason why the size of addresses and
the sizes of offsets for addresses are the same!  That's true from a
definitional point of view, but also consider some of the mixed 32/64
systems, such as Alpha/VMS.  For example, in such a case do you mean
Pmode or ptr_mode?  There seems no reason to me to mix these
unrelated concepts (size of pointer and size of size_t).  And realize
that ptr_mode (which is most likely what you'd want, is ALSO a
front-end concept).

> I still don't see the connection to the signedness of sizetype though.

The range of a type (what values it can hold) is determined by both the
precision and the signedness.  size_t and sizetype must have the same range.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> It looks like giving sizetype mode_for_size (GET_MODE_SIZE
> (Pmode)) (or similar) while raising its precision to cover the full
> 2 * HWI could do the right thing for constants and expansion.

I'm not sure what you mean.  That mode has a lower precision, but if
you use that wider precision it become VERY expensive do all
arithmetic at run time in that wider precision.  sizetype needs to be
at least as wide as needed for correctness purposes but no wider than
needed for efficiency purposes.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> We need some way to indicate that this type does not overflow.

What's wrong with using TYPE_IS_SIZETYPE for that?

I'm quite mystified by this thread: we have a flag that indicates exactly
what we need but kepe trying to find other flags to do that.

Re: [PATCH] Fix optimization regression in constant folder

[Ian Lance Taylor]

kenner@vlsi1.ultra.nyu.edu (Richard Kenner) writes:

> > We need some way to indicate that this type does not overflow.
> 
> What's wrong with using TYPE_IS_SIZETYPE for that?
> 
> I'm quite mystified by this thread: we have a flag that indicates exactly
> what we need but kepe trying to find other flags to do that.

Because, as we've said again and again, TYPE_IS_SIZETYPE doesn't imply
any semantics to the rest of us.  You are the oracle of
TYPE_IS_SIZETYPE.  The rest of us don't know what it means.  That's we
keep going around and around this circle.

TYPE_IGNORE_OVERFLOW does have semantics.

Ian

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Because, as we've said again and again, TYPE_IS_SIZETYPE doesn't imply
> any semantics to the rest of us.  

Yes, but we're trying to develop those semantics now.  When we finish
figuring out what they are, it seems best to use that flag to mean that
rather than invent some other flag.

> You are the oracle of TYPE_IS_SIZETYPE.  The rest of us don't know
> what it means.  That's we keep going around and around this circle.

I've said "what it means" but somehow that's not good enough.  It
means that these are values that are used only in very specific
calculations so we're able to prove things about those calculations
that we can't for other expressions.  That means we know whether or
not certain optimizations are safe.  This thread is all about one of those.

> TYPE_IGNORE_OVERFLOW does have semantics.

Yes, but those semantics don't happen to agree with what sizetypes mean!

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> negative values can be represented in unsigned types just fine, it's just 
> a matter of interpreting it correctly.

I suppose, though the idea of purposely putting a negative value in an
unsigned type because we know that overflow will do the right thing seems
dubious to me.

> Okay, so conceptually it's like:
> 
> struct S {
>   int a1[n1*n2];
>   int a2[n2*n1];
>   int a3[n3];
> } s;  /* so a1 and a2 have the same number of elements */
> 
> And then you access this in e.g. such way:
> 
> for (i = start; i <= end; i++)
>   use (s.a1[i], s.a2[i+2], s.a3[i]);

Somewhat, though a more common case is when you have multiple arrays
that are of the same size (though usually different component sizes)
and the index in each of them is the same value (sounds contrived, but
this happens in Ada discriminated records all the time).  So you know
that the computations for any offset must be a*i+b, for some A and B,
but getting there from the expressions you actually have can be tricky.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> As shown we can't calculate with sizetypes in C anyway, 

We're not calculating them *in C*, but in the middle-end, as an
*implementation* of C-language features, such as indexing.

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > As shown we can't calculate with sizetypes in C anyway, 
> 
> We're not calculating them *in C*, but in the middle-end, as an 
> *implementation* of C-language features, such as indexing.

Yes I understand that.  But what we have to do in the middle-end from C++ 
constructs like Mark has shown has to be done in a type which does not 
have the ignore_overflow "semantic" (because the justification for that 
semantic, namely negative values have small magnitude simply doesn't 
hold).  In fact the most natural choice for a type to calculate that 
expression would have been unsigned because that allows all rearrangements 
of the operands.  But when the natural type for doing arithmetics on such 
operands is type X it simply doesn't make sense to store those operands as 
having type Y, as conversions would be required all the time we actually 
look at the operands.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Yes I understand that.  But what we have to do in the middle-end from C++ 
> constructs like Mark has shown has to be done in a type which does not 
> have the ignore_overflow "semantic" (because the justification for that 
> semantic, namely negative values have small magnitude simply doesn't 
> hold).  In fact the most natural choice for a type to calculate that 
> expression would have been unsigned because that allows all rearrangements 
> of the operands.  But when the natural type for doing arithmetics on such 
> operands is type X it simply doesn't make sense to store those operands as 
> having type Y, as conversions would be required all the time we actually 
> look at the operands.

But I thought that we agreed yesterday that, unless there are some surprises
coming from givs in loop optimization, we should treat sizetypes as 
wrapping on overflow, whether signed or unsigned.  So I'm not sure what you
mean above.

Certainly the point is to do the entire sizing computation in ONE type
and not convert back and forth: that's the whole point of sizetype!

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > Yes I understand that.  But what we have to do in the middle-end from C++
> > constructs like Mark has shown has to be done in a type which does not
> > have the ignore_overflow "semantic" (because the justification for that
> > semantic, namely negative values have small magnitude simply doesn't
> > hold).  In fact the most natural choice for a type to calculate that
> > expression would have been unsigned because that allows all rearrangements
> > of the operands.  But when the natural type for doing arithmetics on such
> > operands is type X it simply doesn't make sense to store those operands as
> > having type Y, as conversions would be required all the time we actually
> > look at the operands.
>
> But I thought that we agreed yesterday that, unless there are some surprises
> coming from givs in loop optimization, we should treat sizetypes as
> wrapping on overflow, whether signed or unsigned.  So I'm not sure what you
> mean above.
>
> Certainly the point is to do the entire sizing computation in ONE type
> and not convert back and forth: that's the whole point of sizetype!

Yes - one excercise we should carry out is to put in place some checks that
we only convert _to_ sizetype, but never _from_ it.  The only place we go
"backward" is using POINTER_PLUS_EXPR which doesn't require an
explicit conversion.  Of course there might be optimization passes
that propagate
the offset from POINTER_PLUS_EXPR in interesting ways back to user-visible
integer types - think of &a[i] - &a[j] which we even fold to i - j (of
user integer
type, that is).  So I don't really think such a check is practical.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Yes - one excercise we should carry out is to put in place some checks that
> we only convert _to_ sizetype, but never _from_ it.  

Unfortunately, we convert from it all the time: that's what sizeof does!

Re: [PATCH] Fix optimization regression in constant folder

[Michael Matz]

Hi,

On Thu, 11 Oct 2007, Richard Kenner wrote:

> > Yes I understand that.  But what we have to do in the middle-end from C++ 
> > constructs like Mark has shown has to be done in a type which does not 
> > have the ignore_overflow "semantic" (because the justification for that 
> > semantic, namely negative values have small magnitude simply doesn't 
> > hold).  In fact the most natural choice for a type to calculate that 
> > expression would have been unsigned because that allows all rearrangements 
> > of the operands.  But when the natural type for doing arithmetics on such 
> > operands is type X it simply doesn't make sense to store those operands as 
> > having type Y, as conversions would be required all the time we actually 
> > look at the operands.
> 
> But I thought that we agreed yesterday that,

Yesterday?  I don't see such agreement anywhere.  It would be nice to have 
this agreement, but the last time we really talked about the semantics of 
sizetype was on October 4. and there Ian proposed to have 
TYPE_IGNORE_OVERFLOWS at all, and Eric proposed TYPE_IGNORE_OVERFLOWS + 
TYPE_OVERFLOW_WRAPS for sizetypes 
(http://gcc.gnu.org/ml/gcc-patches/2007-10/msg00177.html).

But the justification for the validity of TYPE_IGNORE_OVERFLOWS on 
sizetype follows from "negative values have small magnitude".  If we don't 
have this justification (and I don't see that we have it), only 
TYPE_OVERFLOW_WRAPS can stay.

And I would agree that yes, this is a usefull property of sizetype.

But if that is the only justifieable property of sizetype, why not use a 
type which naturally has this property, like some unsigned type?

> unless there are some surprises coming from givs in loop optimization, 
> we should treat sizetypes as wrapping on overflow, whether signed or 
> unsigned.  So I'm not sure what you mean above.

Depends on if you agree to the above or not.  If you agree (and you seem 
to) that the important thing is wrapping overflow, I'm also going to say 
that sizetype should not be allowed to be a signed type.


Ciao,
Michael.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> But if that is the only justifieable property of sizetype, why not use a 
> type which naturally has this property, like some unsigned type?

Because there exist signed types that have that property too.

But I'm having trouble understanding what you're trying to do here.
Clearly we need the TYPE_IS_SIZETYPE flag and clearly the type must
be unique (for validity purposes, if nothing else).  So what we're talking
about is how we interpret the TYPE_IS_SIZETYPE flag.  I don't understand
why it has to be interpreted in terms of some *other* flags (ones that
are used for non-internal types).

> Depends on if you agree to the above or not.  If you agree (and you seem 
> to) that the important thing is wrapping overflow, I'm also going to say 
> that sizetype should not be allowed to be a signed type.

I *really* have a problem with purposely putting a negative value into an
unsigned type.  I think it's bad software engineering and completely
unnecessary.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > But if that is the only justifieable property of sizetype, why not use a
> > type which naturally has this property, like some unsigned type?
>
> Because there exist signed types that have that property too.
>
> But I'm having trouble understanding what you're trying to do here.
> Clearly we need the TYPE_IS_SIZETYPE flag and clearly the type must
> be unique (for validity purposes, if nothing else).  So what we're talking
> about is how we interpret the TYPE_IS_SIZETYPE flag.  I don't understand
> why it has to be interpreted in terms of some *other* flags (ones that
> are used for non-internal types).
>
> > Depends on if you agree to the above or not.  If you agree (and you seem
> > to) that the important thing is wrapping overflow, I'm also going to say
> > that sizetype should not be allowed to be a signed type.
>
> I *really* have a problem with purposely putting a negative value into an
> unsigned type.  I think it's bad software engineering and completely
> unnecessary.

We do that all the time now with POINTER_PLUS_EXPR which takes an
unsigned sizetype as its offset parameter.  There is nothing bad about this.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Paolo Bonzini]

> We do that all the time now with POINTER_PLUS_EXPR which takes an
> unsigned sizetype as its offset parameter.  There is nothing bad about this.

We also did it before, when PLUS_EXPR of a pointer used unsigned 
pointer-type INTEGER_CST.  POINTER_PLUS_EXPR just changed the type of 
the second operand from pointer to sizetype.

Paolo

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> We do that all the time now with POINTER_PLUS_EXPR which takes an
> unsigned sizetype as its offset parameter.  There is nothing bad about this.

It's one thing if we have an expression with an offset that just MIGHT
be negative, but quite another to do so with an expression that we KNOW
will be negative, in my opinion.  Does the spec of POINTER_PLUS_EXPR really
require that its offset parameter be an unsigned type?  It should be
any sizetype.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/12/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > We do that all the time now with POINTER_PLUS_EXPR which takes an
> > unsigned sizetype as its offset parameter.  There is nothing bad about this.
>
> It's one thing if we have an expression with an offset that just MIGHT
> be negative, but quite another to do so with an expression that we KNOW
> will be negative, in my opinion.  Does the spec of POINTER_PLUS_EXPR really
> require that its offset parameter be an unsigned type?  It should be
> any sizetype.

It requires that it is exactly 'sizetype'.  Which makes it signed for Ada again.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Michael Matz wrote:

> It was my understanding during this whole thread, that this sizetype with 
> the funny guarantees only can come out of the Ada frontend (and therefore 
> needs to be dealt with in the middle end), and should never be produced by 
> the other languages, in particular not C or C++.  I realize that this 
> currently is not the case (i.e. C/C++ do produce TYPE_IS_SIZETYPE types) 
> and my understanding was that this actually is a bug.

I don't think that's true.  My understanding was that sizetype was the
type that internal expressions for sizes (such as those stored in
DECL_SIZE) should have.

It's true that this is a different type from size_t, the user-visible
type.  The latter is just a typedef for some unsigned integral type, and
might be wider than sizetype, and might not have other special
properties of sizetype, whatever those might be.

Now, perhaps it would be possible to eliminate the special sizetype
stuff, and just use the size_t type throughout the compiler.  But, if we
don't do that, then I think C/C++ should continue to use sizetype for
DECL_SIZE, etc.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> It's true that this is a different type from size_t, the user-visible
> type.  The latter is just a typedef for some unsigned integral type, and
> might be wider than sizetype, and might not have other special
> properties of sizetype, whatever those might be.

No, I think it's required that it's the same size, and possibly signedness,
as size_t, but they are very definitely different types, with different
properties.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 10/11/07, Richard Kenner <kenner@vlsi1.ultra.nyu.edu> wrote:
> > It's true that this is a different type from size_t, the user-visible
> > type.  The latter is just a typedef for some unsigned integral type, and
> > might be wider than sizetype, and might not have other special
> > properties of sizetype, whatever those might be.
>
> No, I think it's required that it's the same size, and possibly signedness,
> as size_t, but they are very definitely different types, with different
> properties.

I think it's required that it matches the size of pointers, in C speak
that would
be intptr_t, not size_t.

Richard.

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> I think it's required that it matches the size of pointers, in C
> speak that would be intptr_t, not size_t.

I'm not up-to-date on all the various types in the current C standard, but
sizetype must match the precision and signedness of the result of "sizeof",
which, I thought, was size_t.   This is more important than it matching
the size of a pointer (it may well be that those are the same size too: I
just don't know).

Re: [PATCH] Fix optimization regression in constant folder

[Mark Mitchell]

Richard Kenner wrote:
>> It's true that this is a different type from size_t, the user-visible
>> type.  The latter is just a typedef for some unsigned integral type, and
>> might be wider than sizetype, and might not have other special
>> properties of sizetype, whatever those might be.
> 
> No, I think it's required that it's the same size, and possibly signedness,
> as size_t

Why?  I understand that's usually the way it is, but (to my knowledge)
nothing in C says that I can't have a 16-bit address space and a 32-bit
size_t.  Why should DECL_SIZE be a 32-bit type in that case?  Anyhow,
that's probably an academic question; in practice, they are the same.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [PATCH] Fix optimization regression in constant folder

[Richard Kenner]

> Why?  I understand that's usually the way it is, but (to my knowledge)
> nothing in C says that I can't have a 16-bit address space and a 32-bit
> size_t.  Why should DECL_SIZE be a 32-bit type in that case?  Anyhow,
> that's probably an academic question; in practice, they are the same.

It seems quite natural that the result of "sizeof" ought to be just
taking TYPE_SIZE_UNIT and converting it to the user-level type.
You're right that it's not strictly *required*, but it would seem best
if no sizing or signedness conversion were required in that case.

I don't think we're disagreeing from a "language lawyer" perspective,
though.

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> Be more specific.  Much more.  What pathological cases, what optimizations
> do we suppress currently, which of those are allowed in your system.  What
> properties of the type guarantee this.

See the very first message in this thread.  This optimization is now 
suppressed if !TYPE_OVERFLOW_WRAPS (or TYPE_OVERFLOW_UNDEFINED as Ian 
proposed), but we want to retain it for sizetypes.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Eric Botcazou]

> I want to move toward eliminating TYPE_IS_SIZETYPE checks from the
> middle-end, and capture them entirely in TYPE_OVERFLOW_UNDEFINED: a
> sizetype is an unsigned type with undefined overflow.

TYPE_OVERFLOW_WRAPS or not?

> What prevents us from doing that?

We'd lose either TYPE_OVERFLOW_WRAPS optimizations or TYPE_OVERFLOW_UNDEFINED 
optimizations.

-- 
Eric Botcazou

Re: [PATCH] Fix optimization regression in constant folder

[Richard Guenther]

On 30 Sep 2007 15:51:02 -0700, Ian Lance Taylor <iant@google.com> wrote:
> Eric Botcazou <ebotcazou@adacore.com> writes:
>
> > Then I think that we should have
> >
> >   TYPE_IS_SIZETYPE => TYPE_OVERFLOW_WRAPS
> >   TYPE_IS_SIZETYPE => TYPE_OVERFLOW_UNDEFINED
> >   TYPE_IS_SIZETYPE => !TYPE_OVERFLOW_TRAPS
>
> That doesn't make sense: a type either wraps on overflow or is
> undefined on overflow.  I think TYPE_IS_SIZETYPE should imply
> TYPE_OVERFLOW_UNDEFINED.
>
> Richard's patch for PR 30364 should test TYPE_OVERFLOW_UNDEFINED, not
> TYPE_OVERFLOW_WRAPS.

No, it should test !TYPE_OVERFLOW_WRAPS as it does.  The transformation
we do is only valid, if the overflow wraps.  It is not valid if it is merely not
undefined (for example it is invalid if overflow would saturate).

Sorry,
Richard.