Re: Revisiting the TYPE_IS_SIZETYPE issue

["Richard Guenther" <richard dot guenther at gmail dot com>]

On Mon, May 26, 2008 at 10:47 AM, Eric Botcazou <ebotcazou@adacore.com> wrote:
> Hi,
>
> I think now would be a good time to settle the TYPE_IS_SIZETYPE controversy
> and come up with a reasonably well documented semantics for this flag.
>
> To recap, the flag is currently documented in tree.h like so:
>
> /* In an INTEGER_TYPE, it means the type represents a size.  We use
>   this both for validity checking and to permit optimizations that
>   are unsafe for other types.  Note that the C `size_t' type should
>   *not* have this flag set.  The `size_t' type is simply a typedef
>   for an ordinary integer type that happens to be the type of an
>   expression returned by `sizeof'; `size_t' has no special
>   properties.  Expressions whose type have TYPE_IS_SIZETYPE set are
>   always actual sizes.  */
> #define TYPE_IS_SIZETYPE(NODE) \
>
> The most important part (at least for the Ada compiler) is "to permit
> optimizations that are unsafe for other types" and, among them, to permit
> bypassing overflow issues for this type by considering that overflow will
> never happen for it.  That's mentioned in the C front-end too:
>
> /* Compute the value of 'sizeof (TYPE)' or '__alignof__ (TYPE)', where the
>   second parameter indicates which OPERATOR is being applied.  The COMPLAIN
>   flag controls whether we should diagnose possibly ill-formed
>   constructs or not.  */
>
> tree
> c_sizeof_or_alignof_type (tree type, bool is_sizeof, int complain)
>
> [...]
>
>  /* VALUE will have an integer type with TYPE_IS_SIZETYPE set.
>     TYPE_IS_SIZETYPE means that certain things (like overflow) will
>     never happen.  However, this node should really have type
>     `size_t', which is just a typedef for an ordinary integer type.  */
>  value = fold_convert (size_type_node, value);
>  gcc_assert (!TYPE_IS_SIZETYPE (TREE_TYPE (value)));
>
>
> The issue was raised by the fix for PR middle-end/30364 which has disabled
> certain forms of reassociation for signed types on the grounds that they can
> introduce undefined overflow:
>  http://gcc.gnu.org/ml/gcc-patches/2007-09/msg01376.html
> But we want to reassociate for TYPE_IS_SIZETYPE because variable-sized types
> in Ada generate a lot of size calculations and we want to simplify them at
> compile time as much as possible.
>
>
> An interesting proposition (in my opinion) was to wrap up the flag in a new
> macro, e.g. TYPE_OVERFLOW_IGNORED, and use it alongside TYPE_OVERFLOW_WRAPS,
> TYPE_OVERFLOW_TRAPS and TYPE_OVERFLOW_UNDEFINED.
>
> Thoughts?

Note that for a thing like TYPE_OVERFLOW_IGNORED (rather
TYPE_OVERFLOW_NEVER_HAPPENS?!) you need to change
useless_type_conversion_p_1 to preserve conversions between
types that differ in TYPE_IS_SIZETYPEness.  This will have a
bad impact on optimizations I believe as we insert _lots_ of
conversions to sizetype because POINTER_PLUS_EXPR uses
sizetype as offset operand type.

I think that rather than trying to special case sizetype again too much
we should try to sort out a plan on how to move the
TYPE_OVERFLOW_WRAPS and TYPE_OVERFLOW_UNDEFINED
semantics away from types down to the operators - which is needed
anyway for LTO of TUs with different setting of -fwrapv for example.
This would also allow passes like VRP to keep which expressions
may overflow and thus enable further optimizations.

Rather than the two flags TYPE_OVERFLOW_WRAPS and
TYPE_OVERFLOW_UNDEFINED we should make it more explicit
(and conveniently match intended sizetype behavior) and distinguish
between operations that may overflow and operations that we know
do not ('does not overflow' is a valid interpretation of 'undefined overflow').

So initially (for C) signed arithmetic would be 'does not overflow' and
unsigned arithmetic would be 'may overflow'.  Sizetype arithmetic
would fall in the 'does not overflow' category here.

The key is that obviously for 'does not overflow' operations in
(a - b) + (c - d), reassociating that to (a + c) - (b + d) will lose
this property unless we can prove otherwise.  (***)

So my idea (I have this for some time now, but there's always lack
of time to implement it ...) is to make the existing tree codes
'may overflow' operations and introduce new tree code variants
with the 'does not overflow' semantics.  This way we conservatively
preserve 'may overflow' in legacy code.

The middle-end would then _never_ look at the types to determine
overflow behavior, but only at the properties of the operands involved.

Thoughts?
Richard.

(***) This is the reason I think this TYPE_OVERFLOW_IGNORED on
sizetypes is semantically wrong -- the best thing you can do is make
it wrapping (as it is for the C frontend family).