IMA vs tree-ssa

IMA vs tree-ssa

[Dale Johannesen]

.When compiling intermodule (IMA), objects that are defined in multiple
files have their types unified so that all copies of the object refer 
to the
same TYPE_DECL.  This is not done for objects local to a function,
which has the effect that the same type can have multiple TYPE_DECL
nodes used for it, even within the same function.  The example at  the
end demonstrates; compile with IMA, and the first assignment statement
winds up referring to different nodes for struct rtx_def on the two 
sides.
(This causes no problem in this particular example.)

There are several places where tree-ssa does type comparison by
comparing TYPE_MAIN_VARIANT() for equality.  This doesn't work with
IMA, and leads to several different ICEs in various SPECmarks (you
can probably figure out which one the example came from :)

Has anyone else run into this, and thought about fixing it?

My first thought was that this should be fixed by having IMA unify all
copies of the type.  But looking at the code, I don't think this would 
be easy
to get right, and Geoff, the author of IMA, doesn't like it:

> I don't think that would work:
>
> - You'd need to be sure it doesn't change language semantics
> - You'd need to make debugging information correct
> - I'd like to get rid of this final 'merging' pass; it's slow, it 
> doesn't work with -fno-unit-at-a-time, and now that we've thrown out 
> the GCC-specific features that required it, it's not necessary.
>
> I would ask why code in tree-ssa seems to need to compare types.  
> Maybe it needs a language-independent comptypes() that looks at things 
> like field sizes and offsets.  Maybe the language frontend, should be 
> responsible for casting types so that the middle-end doesn't need to 
> be concerned by any of this.

Now I'm thinking along these lines:  make a langhook that calls 
comptypes() for C-based languages,
and devolves to x==y for the others (or calls the comptype-equivalent 
if there is one; I know nothing
about those language FEs).  That will not make the non-C languages any 
worse, and since IMA isn't
implemented for them, there isn't currently a problem there.  Whoever 
implements it for those languages
will need to provide a comptypes() equivalent.

Comments?

/**  s1.c  */
#include "s1.h"
extern rtx recog_operand;

/** s1.h **/
typedef struct rtx_def { int a; int b; } *rtx;
extern rtx recog_operand;

/** s2.c  */
rtx recog_operand;
int foo() {
   rtx *r0, t1;
   r0 = &recog_operand;
   t1 = *r0;
   return t1->a;
}

Re: IMA vs tree-ssa

[law]

In message <F0209661-68A9-11D8-8C0E-000A95D7CD40@apple.com>, Dale Johannesen wr
ites:
 >There are several places where tree-ssa does type comparison by
 >comparing TYPE_MAIN_VARIANT() for equality. 
Yup.

 > This doesn't work with IMA, and leads to several different ICEs in
 > various SPECmarks (you can probably figure out which one the example
 > came from :)
When the tree-ssa optimizers look at TYPE_MAIN_VARIANT, they are trying to
determine if they can either eliminate an expression or eliminate a copy.
If the main variants are not equal, then all that ought to happen is a 
optimization opportunity is missed.

If we're getting aborts and such, then I'd be very curious to know precisely
how the TYPE_MAIN_VARIANTs are being used and how the mis-matched types
lead to failures.

jeff

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 26, 2004, at 2:42 PM, law@redhat.com wrote:
> In message <F0209661-68A9-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
> Johannesen wr
> ites:
>> There are several places where tree-ssa does type comparison by
>> comparing TYPE_MAIN_VARIANT() for equality.
> Yup.
>
>> This doesn't work with IMA, and leads to several different ICEs in
>> various SPECmarks (you can probably figure out which one the example
>> came from :)
> When the tree-ssa optimizers look at TYPE_MAIN_VARIANT, they are 
> trying to
> determine if they can either eliminate an expression or eliminate a 
> copy.
> If the main variants are not equal, then all that ought to happen is a
> optimization opportunity is missed.
>
> If we're getting aborts and such, then I'd be very curious to know 
> precisely
> how the TYPE_MAIN_VARIANTs are being used and how the mis-matched types
> lead to failures.

Hmm, I may have been too optimistic in thinking these were all the same 
bug then,
although everything passes without IMA...the one I analyzed in detail 
is 176.gcc.
Source looks like this:

rtx recog_operand[MAX_RECOG_OPERANDS];
   register rtx *ro = &recog_operand[0];
   rtx x2;
       ro[0] = x2;

It propagates &recog_operand into *r0, then tries to simplify 
*&recog_operand
in maybe_fold_stmt_indirect().  It ought to trigger this case:

       /* Try folding *(&B+O) to B[X].  */
       t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE 
(expr));

but the node for struct rtx_def under the array type is not 
pointer-equivalent to the one
on the indirect node,  so that fails, and it falls through into

       /* Fold *&B to B.  */
       if (integer_zerop (offset))
         return base;

instead which is wrong.  Now we may be able to prevent the ICE by 
checking for
ARRAY_TYPE there, but surely what you want to do is get the B[0] case 
to be recognized...
Thanks, at least now I understand the intent.

Re: IMA vs tree-ssa

[Richard Henderson]

On Thu, Feb 26, 2004 at 03:05:19PM -0800, Dale Johannesen wrote:
> ...  so that fails, and it falls through into
> 
>       /* Fold *&B to B.  */
>       if (integer_zerop (offset))
>         return base;
> 
> instead which is wrong.  Now we may be able to prevent the ICE by 
> checking for ARRAY_TYPE there ...

Indeed, the correct solution is to make sure that BASE matches the
type we're looking for.  I.e. yet another T_M_V pointer comparison.


r~

Re: IMA vs tree-ssa

[law]

In message <3F7FB8C0-68B0-11D8-8C0E-000A95D7CD40@apple.com>, Dale Johannesen wr
ites:
 >On Feb 26, 2004, at 2:42 PM, law@redhat.com wrote:
 >> In message <F0209661-68A9-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
 >> Johannesen wr
 >> ites:
 >>> There are several places where tree-ssa does type comparison by
 >>> comparing TYPE_MAIN_VARIANT() for equality.
 >> Yup.
 >>
 >>> This doesn't work with IMA, and leads to several different ICEs in
 >>> various SPECmarks (you can probably figure out which one the example
 >>> came from :)
 >> When the tree-ssa optimizers look at TYPE_MAIN_VARIANT, they are 
 >> trying to
 >> determine if they can either eliminate an expression or eliminate a 
 >> copy.
 >> If the main variants are not equal, then all that ought to happen is a
 >> optimization opportunity is missed.
 >>
 >> If we're getting aborts and such, then I'd be very curious to know 
 >> precisely
 >> how the TYPE_MAIN_VARIANTs are being used and how the mis-matched types
 >> lead to failures.
 >
 >Hmm, I may have been too optimistic in thinking these were all the same 
 >bug then,
 >although everything passes without IMA...the one I analyzed in detail 
 >is 176.gcc.
 >Source looks like this:
 >
 >rtx recog_operand[MAX_RECOG_OPERANDS];
 >   register rtx *ro = &recog_operand[0];
 >   rtx x2;
 >       ro[0] = x2;
 >
 >It propagates &recog_operand into *r0, then tries to simplify 
 >*&recog_operand
 >in maybe_fold_stmt_indirect().  It ought to trigger this case:
 >
 >       /* Try folding *(&B+O) to B[X].  */
 >       t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE 
 >(expr));
 >
 >but the node for struct rtx_def under the array type is not 
 >pointer-equivalent to the one
 >on the indirect node,  so that fails, and it falls through into
 >
 >       /* Fold *&B to B.  */
 >       if (integer_zerop (offset))
 >         return base;
I must still be missing something.  If OFFSET is zero, then why is returning
BASE wrong?

If OFFSET is nonzero, then we'll fall out returning NULL_TREE which 
indicates that we couldn't simplify -- which ought to just inhibit
an optimization.

jeff

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 26, 2004, at 3:25 PM, law@redhat.com wrote:
> In message <3F7FB8C0-68B0-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
> Johannesen wr
> ites:
>>
>> rtx recog_operand[MAX_RECOG_OPERANDS];
>>   register rtx *ro = &recog_operand[0];
>>   rtx x2;
>>       ro[0] = x2;
>>
>>       /* Fold *&B to B.  */
>>       if (integer_zerop (offset))
>>         return base;
> I must still be missing something.  If OFFSET is zero, then why is 
> returning
> BASE wrong?

Because it's an array, so you get array = scalar.

> If OFFSET is nonzero, then we'll fall out returning NULL_TREE which
> indicates that we couldn't simplify -- which ought to just inhibit
> an optimization.

Actually, I applied the fix rth suggested and now get an abort earlier 
building 176.gcc.
Stay tuned.

Re: IMA vs tree-ssa

[law]

In message <6BFC7E80-68B3-11D8-8C0E-000A95D7CD40@apple.com>, Dale Johannesen wr
ites:
 >On Feb 26, 2004, at 3:25 PM, law@redhat.com wrote:
 >> In message <3F7FB8C0-68B0-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
 >> Johannesen wr
 >> ites:
 >>>
 >>> rtx recog_operand[MAX_RECOG_OPERANDS];
 >>>   register rtx *ro = &recog_operand[0];
 >>>   rtx x2;
 >>>       ro[0] = x2;
 >>>
 >>>       /* Fold *&B to B.  */
 >>>       if (integer_zerop (offset))
 >>>         return base;
 >> I must still be missing something.  If OFFSET is zero, then why is 
 >> returning
 >> BASE wrong?
 >
 >Because it's an array, so you get array = scalar.
Ahhh.  Then we ought to have a type test before returning base in that
code.  


 >> If OFFSET is nonzero, then we'll fall out returning NULL_TREE which
 >> indicates that we couldn't simplify -- which ought to just inhibit
 >> an optimization.
 >
 >Actually, I applied the fix rth suggested and now get an abort earlier 
 >building 176.gcc.
 >Stay tuned.
OK.  Eagerly awaiting the next issue.

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 26, 2004, at 3:47 PM, law@redhat.com wrote:
>> Because it's an array, so you get array = scalar.
> Ahhh.  Then we ought to have a type test before returning base in that
> code.
>
>>> If OFFSET is nonzero, then we'll fall out returning NULL_TREE which
>>> indicates that we couldn't simplify -- which ought to just inhibit
>>> an optimization.
>>
>> Actually, I applied the fix rth suggested and now get an abort earlier
>> building 176.gcc.
>> Stay tuned.
> OK.  Eagerly awaiting the next issue.

The code in get_expr_operands() expects that *&x will get simplified,
and aborts if it isn't.  Both suggested fixes run into this.

Perhaps maybe_fold_offset_to_array_ref ought to ignore the type 
"mismatch",
at least when offset is 0.    I can't see that *&x (for x an array) 
should ever be
anything but x[0].  Let me try that...

Re: IMA vs tree-ssa

[law]

In message <47CEA8A4-68B9-11D8-8C0E-000A95D7CD40@apple.com>, Dale Johannesen wr
ites:
 >
 >On Feb 26, 2004, at 3:47 PM, law@redhat.com wrote:
 >>> Because it's an array, so you get array = scalar.
 >> Ahhh.  Then we ought to have a type test before returning base in that
 >> code.
 >>
 >>>> If OFFSET is nonzero, then we'll fall out returning NULL_TREE which
 >>>> indicates that we couldn't simplify -- which ought to just inhibit
 >>>> an optimization.
 >>>
 >>> Actually, I applied the fix rth suggested and now get an abort earlier
 >>> building 176.gcc.
 >>> Stay tuned.
 >> OK.  Eagerly awaiting the next issue.
 >
 >The code in get_expr_operands() expects that *&x will get simplified,
 >and aborts if it isn't.
I had a concern this might happen.

 > Both suggested fixes run into this.
 >
 >Perhaps maybe_fold_offset_to_array_ref ought to ignore the type 
 >"mismatch",
 >at least when offset is 0.    I can't see that *&x (for x an array) 
 >should ever be anything but x[0].  Let me try that...
My only concern would be that you might get a bad operand type mis-match;
though for this code I don't really see how that could happen.

jeff

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 26, 2004, at 4:21 PM, law@redhat.com wrote:
> In message <47CEA8A4-68B9-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
> Johannesen wr
> ites:
>>
>> Perhaps maybe_fold_offset_to_array_ref ought to ignore the type
>> "mismatch",
>> at least when offset is 0.    I can't see that *&x (for x an array)
>> should ever be anything but x[0].  Let me try that...
> My only concern would be that you might get a bad operand type 
> mis-match;
> though for this code I don't really see how that could happen.

This gets farther than before in 176.gcc; there's an apparently 
unrelated BE crash later.
As you're OK with the idea, I'll bootstrap/test this overnight.

Just fyi, we're getting 6 failures on SPEC with IMA.    This one, one 
in the IMA code itself,
3 ICEs at various places in tree-ssa (may well be other manifestations 
of unequal type info),
one miscompare.  Working on it.

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 26, 2004, at 5:02 PM, Dale Johannesen wrote:
> On Feb 26, 2004, at 4:21 PM, law@redhat.com wrote:
>> In message <47CEA8A4-68B9-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
>> Johannesen wr
>> ites:
>>>
>>> Perhaps maybe_fold_offset_to_array_ref ought to ignore the type
>>> "mismatch",
>>> at least when offset is 0.    I can't see that *&x (for x an array)
>>> should ever be anything but x[0].  Let me try that...
>> My only concern would be that you might get a bad operand type 
>> mis-match;
>> though for this code I don't really see how that could happen.
>
> This gets farther than before in 176.gcc; there's an apparently 
> unrelated BE crash later.
> As you're OK with the idea, I'll bootstrap/test this overnight.

Bootstrap and test passed but given rth's comments I'll look at a 
langhook for
comptypes (as I was going to do originally) instead of submitting this.

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 27, 2004, at 10:35 AM, Dale Johannesen wrote:
> On Feb 26, 2004, at 5:02 PM, Dale Johannesen wrote:
>> On Feb 26, 2004, at 4:21 PM, law@redhat.com wrote:
>>> In message <47CEA8A4-68B9-11D8-8C0E-000A95D7CD40@apple.com>, Dale 
>>> Johannesen wr
>>> ites:
>>>>
>>>> Perhaps maybe_fold_offset_to_array_ref ought to ignore the type
>>>> "mismatch",
>>>> at least when offset is 0.    I can't see that *&x (for x an array)
>>>> should ever be anything but x[0].  Let me try that...
>>> My only concern would be that you might get a bad operand type 
>>> mis-match;
>>> though for this code I don't really see how that could happen.
>>
>> This gets farther than before in 176.gcc; there's an apparently 
>> unrelated BE crash later.
>> As you're OK with the idea, I'll bootstrap/test this overnight.
>
> Bootstrap and test passed but given rth's comments I'll look at a 
> langhook for
> comptypes  instead of submitting this.

This bit seems to be working, but doesn't solve the entire problem by 
any means.
The tree-based aliasing and structure-scalarizing code also think 
there's only
one copy of a struct type node, and work off pointers.   There may be 
more places
I haven't found yet; can you think of any?  (Most of the SPEC failures 
seem to be
due to aliasing; it thinks different copies of a struct from different 
files do not
alias, when in fact they do.  This breaks lots of things.)

Re: IMA vs tree-ssa

[Mark Mitchell]

Dale Johannesen wrote:

>
> This bit seems to be working, but doesn't solve the entire problem by 
> any means.
> The tree-based aliasing and structure-scalarizing code also think 
> there's only
> one copy of a struct type node, and work off pointers.   There may be 
> more places
> I haven't found yet; can you think of any?  (Most of the SPEC failures 
> seem to be
> due to aliasing; it thinks different copies of a struct from different 
> files do not
> alias, when in fact they do.  This breaks lots of things.)
>
I believe that we should not hold up the tree-ssa merge for IMA.

Instead, we should just let IMA be broken for a while.

It's a new feature, not one that people have gotten used to at this 
point.  It's a valuable optimization, but it's a problem, we should move 
on without it and then add it back later.

That's my opinion, not an official SC position by any means.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Dale Johannesen]

On Mar 8, 2004, at 2:32 PM, Mark Mitchell wrote:
> Dale Johannesen wrote:
>> This bit seems to be working, but doesn't solve the entire problem by 
>> any means.
>> The tree-based aliasing and structure-scalarizing code also think 
>> there's only
>> one copy of a struct type node, and work off pointers.   There may be 
>> more places
>> I haven't found yet; can you think of any?  (Most of the SPEC 
>> failures seem to be
>> due to aliasing; it thinks different copies of a struct from 
>> different files do not
>> alias, when in fact they do.  This breaks lots of things.)
>>
> I believe that we should not hold up the tree-ssa merge for IMA.
>
> Instead, we should just let IMA be broken for a while.

That's a regression.  Just pointing it out.

I don't mind not making it be a requirement, provided patches that fix 
these problems
are still eligible despite the freeze.   (I have made some progress, 
including fixes for
both the points I listed above.  Perhaps there is enough that I should 
prepare a patch,
but there are still problems.)

> It's a new feature, not one that people have gotten used to at this 
> point.
> It's a valuable optimization, but it's a problem, we should move on 
> without it and then add it back later.
>
> That's my opinion, not an official SC position by any means.

Re: IMA vs tree-ssa

[Mark Mitchell]

Dale Johannesen wrote:

> On Mar 8, 2004, at 2:32 PM, Mark Mitchell wrote:
>
>> Dale Johannesen wrote:
>>
>>> This bit seems to be working, but doesn't solve the entire problem 
>>> by any means.
>>> The tree-based aliasing and structure-scalarizing code also think 
>>> there's only
>>> one copy of a struct type node, and work off pointers.   There may 
>>> be more places
>>> I haven't found yet; can you think of any?  (Most of the SPEC 
>>> failures seem to be
>>> due to aliasing; it thinks different copies of a struct from 
>>> different files do not
>>> alias, when in fact they do.  This breaks lots of things.)
>>>
>> I believe that we should not hold up the tree-ssa merge for IMA.
>>
>> Instead, we should just let IMA be broken for a while.
>
>
> That's a regression.  Just pointing it out.

Yes, I understand, and it's a good point.

I think the right tradeoff is to temporarily sacrifice IMA on the altar 
of tree-ssa, and try to resurrect IMA later.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Richard Henderson]

On Thu, Feb 26, 2004 at 04:09:59PM -0800, Dale Johannesen wrote:
> The code in get_expr_operands() expects that *&x will get simplified,
> and aborts if it isn't.  Both suggested fixes run into this.

We cope with *(&x + c) not being folded; we should probably
do the same for *&x.

> Perhaps maybe_fold_offset_to_array_ref ought to ignore the type 
> "mismatch", at least when offset is 0.

I'm *really* uncomfortable with leaving these mismatches around.
We absolutely need to address them in some way that preserves,
rather than hacks around, the type system.


r~

Re: IMA vs tree-ssa

[Richard Henderson]

On Thu, Feb 26, 2004 at 02:20:09PM -0800, Dale Johannesen wrote:
> There are several places where tree-ssa does type comparison by
> comparing TYPE_MAIN_VARIANT() for equality.  This doesn't work with
> IMA, and leads to several different ICEs in various SPECmarks (you
> can probably figure out which one the example came from :)

This is a bug in IMA.  When unifying the types, you should either
replace all of them or make all copies be variants.  Clearly the
later is much easier than the former.


r~

Re: IMA vs tree-ssa

[Dale Johannesen]

On Feb 26, 2004, at 3:08 PM, Richard Henderson wrote:

> On Thu, Feb 26, 2004 at 02:20:09PM -0800, Dale Johannesen wrote:
>> There are several places where tree-ssa does type comparison by
>> comparing TYPE_MAIN_VARIANT() for equality.  This doesn't work with
>> IMA, and leads to several different ICEs in various SPECmarks (you
>> can probably figure out which one the example came from :)
>
> This is a bug in IMA.  When unifying the types, you should either
> replace all of them or make all copies be variants.  Clearly the
> later is much easier than the former.

That's what Geoff thought wouldn't work.  Terrific.

Re: IMA vs tree-ssa

[Geoff Keating]

Richard Henderson <rth@redhat.com> writes:

> On Thu, Feb 26, 2004 at 02:20:09PM -0800, Dale Johannesen wrote:
> > There are several places where tree-ssa does type comparison by
> > comparing TYPE_MAIN_VARIANT() for equality.  This doesn't work with
> > IMA, and leads to several different ICEs in various SPECmarks (you
> > can probably figure out which one the example came from :)
> 
> This is a bug in IMA.  When unifying the types, you should either
> replace all of them or make all copies be variants.  Clearly the
> later is much easier than the former.

As I commented, will this really work?

Consider:

a.c:

struct bar {
  int x;
};

extern void foo (struct bar *bp);

// call foo()

b.c:

struct not_bar {
  int x;
};

void foo (struct not_bar *bp) {
  ...
}


This is valid C89.

Also, consider:

a.c:

union x_u {
  int i[2];
  double d;
};

union x_u x_u_i = { 0x1234, 0x5678 };

b.c:

extern union {
  double d;
  int i[2];
} x_u_i;

// use x_u_i

which is also valid in C89.  The rules got tightened significantly in
C99, but even then you can have one anonymous structure and another
which has a tag.

In addition, structure compatilibity between modules is not
transitive, even in C99.  For instance,

struct { int x; }

is compatible with both

struct x_1 { int x; }
and
struct x_2 { int x; }

but x_1 and x_2 are not compatible with each other.


The relevant paragraphs in the standards are 6.1.2.6 para 1 in C89,
and 6.2.7 para 1 in C99; note that the paragraphs are quite different,
this is one of the more significant changes between C89 and C99.


If it does work, I agree this is the best solution.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: IMA vs tree-ssa

[Richard Henderson]

On Thu, Feb 26, 2004 at 03:34:13PM -0800, Geoff Keating wrote:
> As I commented, will this really work?

I guess not.

For c89, the squishy rules (if it looks ok, it's ok) means
that we do have transitivity, and so things really ought to
be ok to just chain together the TYPE_MAIN_VARIANT lists.

For c99, we can't.  I guess we'll need some sort of language
callback in order to determine type compatibility.  Given that,
it seems silly to treat c89 and c99 differently.


r~

Re: IMA vs tree-ssa

[Neil Booth]

Geoff Keating wrote:-

> In addition, structure compatilibity between modules is not
> transitive, even in C99.  For instance,
> 
> struct { int x; }
> 
> is compatible with both
> 
> struct x_1 { int x; }
> and
> struct x_2 { int x; }
> 
> but x_1 and x_2 are not compatible with each other.

I disagree.  The relevant line is

If one is declared with a tag, the other shall be declared with the
same tag.

which clearly implies all 3 are mutually incompatible.

Neil.

Re: IMA vs tree-ssa

[Geoff Keating]

Neil Booth <neil@daikokuya.co.uk> writes:

> Geoff Keating wrote:-
> 
> > In addition, structure compatilibity between modules is not
> > transitive, even in C99.  For instance,
> > 
> > struct { int x; }
> > 
> > is compatible with both
> > 
> > struct x_1 { int x; }
> > and
> > struct x_2 { int x; }
> > 
> > but x_1 and x_2 are not compatible with each other.
> 
> I disagree.  The relevant line is
> 
> If one is declared with a tag, the other shall be declared with the
> same tag.
> 
> which clearly implies all 3 are mutually incompatible.

Hey, I think you're right!  You should check to see whether that's
what the code implements.


In any case, it's still not transitive, because 'bar' in:

struct foo;
struct bar { 
  struct foo *f;
};

is compatible with

struct foo { int a; };
struct bar { 
  struct foo *f;
};

and

struct foo { int b; };
struct bar { 
  struct foo *f;
};

but they are not compatible with each other.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: IMA vs tree-ssa

[Neil Booth]

Geoff Keating wrote:-

> In any case, it's still not transitive, because 'bar' in:
> 
> struct foo;
> struct bar { 
>   struct foo *f;
> };
> 
> is compatible with
> 
> struct foo { int a; };
> struct bar { 
>   struct foo *f;
> };
> 
> and
> 
> struct foo { int b; };
> struct bar { 
>   struct foo *f;
> };
> 
> but they are not compatible with each other.

Yah, nice counterexample.  What a mess.

Neil.

Re: IMA vs tree-ssa

[Mark Mitchell]

Neil Booth wrote:

>Geoff Keating wrote:-
>
>  
>
>>In any case, it's still not transitive, because 'bar' in:
>>
>>struct foo;
>>struct bar { 
>>  struct foo *f;
>>};
>>
>>is compatible with
>>
>>struct foo { int a; };
>>struct bar { 
>>  struct foo *f;
>>};
>>
>>and
>>
>>struct foo { int b; };
>>struct bar { 
>>  struct foo *f;
>>};
>>
>>but they are not compatible with each other.
>>    
>>
Has anyone asked the C committee what they think about this?

I strongly expect that their intention was to create a requirement that 
compatibility be an equivalence relation.  Certainly, there's no reason 
to suspect that passing pointers to "struct foo" from the second to 
third translation unit above would work, at least if the two "struct 
foo" objects were not themselves so similar.  I would expect that this 
is a defect in the standard.

If so, IMA could just "break" this code in the same way that 
strict-aliasing "broke" lots of other "always-worked-for-me" code.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

| Neil Booth wrote:
| 
| >Geoff Keating wrote:-
| >
| >
| >>In any case, it's still not transitive, because 'bar' in:
| >>
| >>struct foo;
| >> struct bar {  struct foo *f;
| >>};
| >>
| >>is compatible with
| >>
| >>struct foo { int a; };
| >> struct bar {  struct foo *f;
| >>};
| >>
| >>and
| >>
| >>struct foo { int b; };
| >> struct bar {  struct foo *f;
| >>};
| >>
| >>but they are not compatible with each other.
| >>
| Has anyone asked the C committee what they think about this?
| 
| I strongly expect that their intention was to create a requirement
| that compatibility be an equivalence relation.  Certainly, there's no
| reason to suspect that passing pointers to "struct foo" from the
| second to third translation unit above would work, at least if the two
| "struct foo" objects were not themselves so similar.  I would expect
| that this is a defect in the standard.

I suspect your C++ brackground is showing up :-)

I believe Neil is right. See 

    6.2.7  Compatible type and composite type
       [#1] Two types have compatible type if their types  are  the
       same.   Additional  rules  for determining whether two types
       are compatible are described in 6.7.2 for  type  specifiers,
       in   6.7.3   for   type   qualifiers,   and   in  6.7.5  for
       declarators.46)   Moreover,   two   structure,   union,   or
       enumerated  types declared in separate translation units are
       compatible if their tags and members satisfy  the  following
       requirements:   If  one  is  declared  with a tag, the other
       shall be declared with the same tag.  If both  are  complete
       types,  then  the  following  additional requirements apply:
       there shall be a  one-to-one  correspondence  between  their
       members  such  that  each  pair of corresponding members are
       declared with compatible types, and such that if one  member
       of  a  corresponding pair is declared with a name, the other
       member is declared with the same name.  For two  structures,
       corresponding  members  shall be declared in the same order.
       For two structures or unions, corresponding bit-fields shall
       have  the  same widths.  For two enumerations, corresponding
       members shall have the same values.

       [#2] All declarations that  refer  to  the  same  object  or
       function shall have compatible type; otherwise, the behavior
       is undefined.

       [#3] A composite type can be constructed from two types that
       are compatible; it is a type that is compatible with both of
       the two types and satisfies the following conditions:

         -- If one type is an array of  known  constant  size,  the
            composite  type is an array of that size; otherwise, if
            one type is a variable length array, the composite type
            is that type.

         -- If  only  one  type is a function type with a parameter
            type list (a function prototype), the composite type is
            a function prototype with the parameter type list.

         -- If  both  types  are function types with parameter type
            lists, the type of  each  parameter  in  the  composite
            parameter  type  list  is  the  composite  type  of the
            corresponding parameters.

       These rules apply recursively to the types  from  which  the
       two types are derived.



from the C standard.

Or course, in C++, that is ODR violation.

-- Gaby

Re: IMA vs tree-ssa

[Joe Buck]

Mark Mitchell <mark@codesourcery.com> writes:
> | I strongly expect that their intention was to create a requirement
> | that compatibility be an equivalence relation.

I'm just going to highlight one section of Gaby's reply:
On Mon, Mar 08, 2004 at 11:57:00PM +0100, Gabriel Dos Reis wrote:
>        [#2] All declarations that  refer  to  the  same  object  or
>        function shall have compatible type; otherwise, the behavior
>        is undefined.

This would seem to suggest that in the situations where non-transitive
behavior would otherwise result (for example, an incomplete struct type is
compatible with two distinct and incompatible definitions of that struct
type), and this matters (for the purpose of aliasing analysis, for
example), we have undefined behavior, so the compiler should be able to
act as though this situation does not arise and assume transitivity.

Re: IMA vs tree-ssa

[Dale Johannesen]

On Mar 8, 2004, at 3:32 PM, Joe Buck wrote:
> On Mon, Mar 08, 2004 at 11:57:00PM +0100, Gabriel Dos Reis wrote:
>>        [#2] All declarations that  refer  to  the  same  object  or
>>        function shall have compatible type; otherwise, the behavior
>>        is undefined.
> This would seem to suggest that in the situations where non-transitive
> behavior would otherwise result (for example, an incomplete struct 
> type is
> compatible with two distinct and incompatible definitions of that 
> struct
> type), and this matters (for the purpose of aliasing analysis, for
> example), we have undefined behavior, so the compiler should be able to
> act as though this situation does not arise and assume transitivity.

Suppose we have 3 types T1, T2, Tcom such that T1 and T2
are not compatible, but Tcom is compatible with either T1 or T2.
Let's call the relationship between T1 and T2 "pseudo-compatible".
Then:

Tcom x;
T1 * p = (T1 *)&x;
T2 * q = (T2 *)&x;

foo()
{
    T1 x = *p;
    *q = ...
}

This is not undefined behavior, and the standard says that p and q 
don't alias
in foo.  But they do.  However, we are probably OK assuming that
pseudo-compatible types alias, even though the standard says they don't.

I can't construct an example of pseudo-compatible types where T1 and T2 
are visible in the
same scope, and believe this to be impossible.  So without IMI, there 
is no problem.
But this sort of thing can happen with crossfile inlining.

The more I think about this, the more I think Mark is right, this can 
of worms can't
be intentional.

Re: IMA vs tree-ssa

[Joseph S. Myers]

On Mon, 8 Mar 2004, Dale Johannesen wrote:

> I can't construct an example of pseudo-compatible types where T1 and T2 
> are visible in the
> same scope, and believe this to be impossible.  So without IMI, there 
> is no problem.
> But this sort of thing can happen with crossfile inlining.

Two distinct enumeration types in the same translation unit compatible
with the same integer type are nevertheless not compatible with each
other.  Implemented by

2004-01-07  Joseph S. Myers  <jsm@polyomino.org.uk>

        PR c/6024
        * c-typeck.c (comptypes): Only treat enumerated types in the same
        translation unit as compatible with each other when they are the
        same type.
        * doc/extend.texi: Update.

A VLA type is compatible with any fixed-size array of compatible element
type, with runtime undefined behavior if code requiring this compatibility
is executed when the runtime size of the VLA doesn't equal the fixed size
of the non-VLA.

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: IMA vs tree-ssa

[Mark Mitchell]

Dale Johannesen wrote:

> Suppose we have 3 types T1, T2, Tcom such that T1 and T2
> are not compatible, but Tcom is compatible with either T1 or T2.
> Let's call the relationship between T1 and T2 "pseudo-compatible".
> Then:
>
> Tcom x;
> T1 * p = (T1 *)&x;
> T2 * q = (T2 *)&x;
>
> foo()
> {
>    T1 x = *p;
>    *q = ...
> }
>
> This is not undefined behavior, and the standard says that p and q 
> don't alias
> in foo.  But they do.

Yes, this is precisely why I think that this is a defect in the C 
standard, not an intentional decision.  Surely if you only cast between 
compatible types then things that really do alias in practice should 
alias according to the standard. 

The fact that this situation is not dealt with appropriately is, I 
believe, simply an oversight.  Your example should have undefined behavior.

A type system with non-transitive type-equality breaks all the standard 
mathematical models for type theory.  (And, yes, I know the C type 
system is ugly, but most of it can actually be modeled in pretty 
conventional ways.)  The category-theoretician in me is befuddled by 
what a non-transitive type-equality model could possibly mean.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Joseph S. Myers]

On Mon, 8 Mar 2004, Mark Mitchell wrote:

> A type system with non-transitive type-equality breaks all the standard 
> mathematical models for type theory.  (And, yes, I know the C type 
> system is ugly, but most of it can actually be modeled in pretty 
> conventional ways.)  The category-theoretician in me is befuddled by 
> what a non-transitive type-equality model could possibly mean.

It's not type-equality, it's type-compatibility.  Equality of types also
exists, and behaves transitively.

Most of the problem cases involve incomplete types; e.g., int[] is
compatible with int[3] and int[5] which are not compatible with each
other.  But the existence of such cases means there is no general
principle of transitivity of compatibility and is what caused me to
conclude that the standard really did intend that enums compatible with
the same integer type are not compatible with each other.

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: IMA vs tree-ssa

[Joe Buck]

On Mon, 8 Mar 2004, Mark Mitchell wrote:

On Tue, Mar 09, 2004 at 12:48:58AM +0000, Joseph S. Myers wrote:
> > A type system with non-transitive type-equality breaks all the standard 
> > mathematical models for type theory.  (And, yes, I know the C type 
> > system is ugly, but most of it can actually be modeled in pretty 
> > conventional ways.)  The category-theoretician in me is befuddled by 
> > what a non-transitive type-equality model could possibly mean.
> 
> It's not type-equality, it's type-compatibility.  Equality of types also
> exists, and behaves transitively.
> 
> Most of the problem cases involve incomplete types; e.g., int[] is
> compatible with int[3] and int[5] which are not compatible with each
> other.

Such a relationship can still be transitive if there is a direction.
For example, we can have a transitive "is_a" relationship such that

    int[3] is_a int[]
    int[5] is_a int[]

but there is no is_a relationship between int[3] and int[5], or between
int[] and int[3] in the reverse direction.

Re: IMA vs tree-ssa

[Mark Mitchell]

Joseph S. Myers wrote:

>On Mon, 8 Mar 2004, Mark Mitchell wrote:
>
>  
>
>>A type system with non-transitive type-equality breaks all the standard 
>>mathematical models for type theory.  (And, yes, I know the C type 
>>system is ugly, but most of it can actually be modeled in pretty 
>>conventional ways.)  The category-theoretician in me is befuddled by 
>>what a non-transitive type-equality model could possibly mean.
>>    
>>
>
>It's not type-equality, it's type-compatibility.  Equality of types also
>exists, and behaves transitively.
>  
>
Well, yes, that's true. 

But the way that the C standard uses compatibility somtimes implies 
something very much like equality.  In particular, the fact that you can 
assign in both directions, for example, is an equality-style 
requirement.  Using enums:

  enum A { x = 6 }; /* Assume compatible with "int" on this system.  */
  enum A a;
  int i;
  
  a = i; /* OK */
  i = a; /* Also OK. */

With a standard partial-order (e.g., for derived/base types in C++) only 
one of those assignments would be valid.  If both are valid, then you 
have type equality between "A" and "i", under most models.

You claim that in C two enums can be incompatible even if the underlying 
type is identicial.  The version of the EDG front end that I have does 
not seem to agree with you, but let's assume that you are right.  (I 
don't really know.)  One type-theoretic way of understanding that would 
be that both enums are subtypes of the underlying type, and that the 
first assignment above is just syntactic sugar for "a = (enum A)i;".  
You also have to adjust the memory-access rules for pointer types in 
some funny, theoretically inconvenient ways, but it could be done.

The incomplete array example, is not nearly so messy.  In that case you 
can think of both "int [5]" and "int [3]" as subtypes of "int []".  
Things are easier because there are no objects of type "int []", 
although there are objects of type "int (*)[]" and so forth.

In any case, with incomplete structure types (Geoff's example), we're 
positing that the standard means for you to be able to complete a single 
type in more than one way.  I don't believe that anyone ever intended that.

This would be the first major case I know of in C where you could write 
code that was valid across translation units that was not valid within a 
translation unit, and I see no evidence that was intended. 

Certainly, things like:

  extern int i[];
  int i[3];

are valid whether within one translation unit or across two.  But, you 
cannot complete the same structure type in two different ways in the 
same translation unit.  The idea that in C you could not validly combine 
all your translation units into a single translation unit (with  
appropriate alpha-renaming of things with internal linkage, and with 
appropriate merger of tentative definitions, if you've adopted that 
(optional) behavior) is, to me, in contradiction with the spirit of the 
language requiring declarations to have compatible types across 
translation units.

In any case, we could probably debate here until we are blue in the 
face: we really ought to ask the C committee and get something 
approaching a definitive opinion.  Would you please do that?

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

| Joseph S. Myers wrote:
| 
| >On Mon, 8 Mar 2004, Mark Mitchell wrote:
| >
| >
| >> A type system with non-transitive type-equality breaks all the
| >> standard mathematical models for type theory.  (And, yes, I know
| >> the C type system is ugly, but most of it can actually be modeled
| >> in pretty conventional ways.)  The category-theoretician in me is
| >> befuddled by what a non-transitive type-equality model could
| >> possibly mean.
| >>
| >
| >It's not type-equality, it's type-compatibility.  Equality of types also
| >exists, and behaves transitively.
| >
| Well, yes, that's true. But the way that the C standard uses
| compatibility somtimes implies something very much like equality.  In

Footnote 46) from the C standard is even more explicit as to what
the intent of type-compatibility is:

       46)Two types need not be identical to be compatible.

meaning you may have compatible types that are not equal.

| particular, the fact that you can assign in both directions, for
| example, is an equality-style requirement.  Using enums:
| 
|   enum A { x = 6 }; /* Assume compatible with "int" on this system.  */
|   enum A a;
|   int i;
|   a = i; /* OK */
|   i = a; /* Also OK. */
| 
| With a standard partial-order (e.g., for derived/base types in C++)
| only one of those assignments would be valid.  If both are valid, then
| you have type equality between "A" and "i", under most models.

  (1) But C is not C++, and that is NOT quibbling.  You get all kinds
      of troubles when you start applying C++ logic to the C type
      system (but in fact here, it is not even C++ logic). 

  (2) you can apply your reasoning to int and double and conclude there
      is equality between int and double despite the standard
      explicitly saying they are different.

  (3) Suppose a plateform where char is signed.  You can repeat your
      reasoning and conclude there is equality between char and signed
      char.  Yet, the C standard says char is distinct from signed char.
      Ditto if char is unsigned on the plateform.

| You claim that in C two enums can be incompatible even if the
| underlying type is identicial.

I think Joseph is right.

-- Gaby

Re: IMA vs tree-ssa

[Paul Jarc]

Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
>        46)Two types need not be identical to be compatible.
>
> meaning you may have compatible types that are not equal.

Equality is not the only equivalence relation.  Compatibility might be
intended to be an equivalence relation, without being intended to be
the same as equality.


paul

Re: IMA vs tree-ssa

[Gabriel Dos Reis]

prj@po.cwru.edu (Paul Jarc) writes:

| Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| >        46)Two types need not be identical to be compatible.
| >
| > meaning you may have compatible types that are not equal.
| 
| Equality is not the only equivalence relation.

That is right.  But, Mark was referring to equality.

-- Gaby

Re: IMA vs tree-ssa

[Paul Jarc]

Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
> prj@po.cwru.edu (Paul Jarc) writes:
>| Equality is not the only equivalence relation.
>
> That is right.  But, Mark was referring to equality.

I don't think so.  He said:

| But the way that the C standard uses compatibility somtimes implies
| something very much like equality.

I read that as "similar to equality", specifically in the quality of
being an equivalence relation, not as "exactly equality".


paul

Re: IMA vs tree-ssa

[Gabriel Dos Reis]

prj@po.cwru.edu (Paul Jarc) writes:

| Gabriel Dos Reis <gdr@integrable-solutions.net> wrote:
| > prj@po.cwru.edu (Paul Jarc) writes:
| >| Equality is not the only equivalence relation.
| >
| > That is right.  But, Mark was referring to equality.
| 
| I don't think so.  He said:
| 
| | But the way that the C standard uses compatibility somtimes implies
| | something very much like equality.
| 
| I read that as "similar to equality", specifically in the quality of
| being an equivalence relation, not as "exactly equality".

Aha, I see.  It is using mathematics without using mathematics.  That
can mislead more than one mathematicians :-)
Thanks.

-- Gaby

Re: IMA vs tree-ssa

[Joseph S. Myers]

On Mon, 8 Mar 2004, Mark Mitchell wrote:

> are valid whether within one translation unit or across two.  But, you 
> cannot complete the same structure type in two different ways in the 
> same translation unit.  The idea that in C you could not validly combine 
> all your translation units into a single translation unit (with  
> appropriate alpha-renaming of things with internal linkage, and with 
> appropriate merger of tentative definitions, if you've adopted that 
> (optional) behavior) is, to me, in contradiction with the spirit of the 
> language requiring declarations to have compatible types across 
> translation units.

As far as I know you can combine translation units.  Any object or
function must have compatible complete type in all translation units.  It
may, however, be necessary to split up named structure or union types into
several separate such named types, one for each incompatible completion of
that type, but each object or function defined using such a type can be
unambiguously assigned at most one completion (otherwise there is
undefined behavior).

In the example of aliasing given, if this is applied with enums and the
corresponding integer type it shows the enums *can* alias each other: the
enums are both compatible with the effective type of the object (the
compatible integer type) which is its declared type.  This may need to be
applied in general for aliasing among types which could be composite types
arising from the same type.

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: IMA vs tree-ssa

[Mark Mitchell]

Joseph S. Myers wrote:

>On Mon, 8 Mar 2004, Mark Mitchell wrote:
>
>  
>
>>are valid whether within one translation unit or across two.  But, you 
>>cannot complete the same structure type in two different ways in the 
>>same translation unit.  The idea that in C you could not validly combine 
>>all your translation units into a single translation unit (with  
>>appropriate alpha-renaming of things with internal linkage, and with 
>>appropriate merger of tentative definitions, if you've adopted that 
>>(optional) behavior) is, to me, in contradiction with the spirit of the 
>>language requiring declarations to have compatible types across 
>>translation units.
>>    
>>
>
>As far as I know you can combine translation units.  Any object or
>function must have compatible complete type in all translation units.  It
>may, however, be necessary to split up named structure or union types into
>several separate such named types, one for each incompatible completion of
>that type, but each object or function defined using such a type can be
>unambiguously assigned at most one completion (otherwise there is
>undefined behavior).
>
I intentionally did not include that operation above.

That's alpha-renaming of structure types, not of things with internal linkage.  That's exactly what I mean by saying that positing that multiple completions are simultaneously valid breaks the idea that you combine things into one translation unit.

However, I don't think there's any point in all of us debating this issue.  We don't agree on the answer, and none of us has a particularly good way of backing up our position.  To me, this idea of multiple completions of the same incomplete type is ghastly.  You, however, believe it is what the standard requires, and apparently that it is also what the committe intended.

I would appreciate it if you would communicate with the C committee to find out what they really intend.  Ultimately, it's their opinion that matters.  We can't resolve this issue just by talking among ourselves.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Joseph S. Myers]

On Tue, 9 Mar 2004, Mark Mitchell wrote:

> However, I don't think there's any point in all of us debating this
> issue.  We don't agree on the answer, and none of us has a particularly
> good way of backing up our position.  To me, this idea of multiple
> completions of the same incomplete type is ghastly.  You, however,
> believe it is what the standard requires, and apparently that it is also
> what the committe intended.

This seems simply to be a difference between C and C++ backgrounds.  
Types in C do not have linkage; those in C++ do.  I don't know whether
this is a deliberate difference, but it is a fairly fundamental one.

C and C++ are different languages - and different levels of language -
with both intentional and unintentional differences in the interpretation
of code that appears to be in the intersection.  While a lot more could
and should be shared between the implementations than presently is (and in
this context I'd hope a common intermediate representation for multiple
translation units could be shared between C and C++, providing intermodule
support for C++, though I don't know whether inlining between languages
could work), the handling of declarations, name lookup etc. seems so
different I don't think there is much scope for sharing there.  The
differences here about multiple completions of the same incomplete type
are simply examples of this.

> I would appreciate it if you would communicate with the C committee to
> find out what they really intend.  Ultimately, it's their opinion that
> matters.  We can't resolve this issue just by talking among ourselves.

What is the actual concrete defect here?  (As far as I know the only
relevant procedure here is sending DRs - there isn't one for "requests to
identify intent".  Asking the WG14 reflector a question may get answers
"obviously yes", "obviously no" and "it's obvious, but I won't say which
way" to the same question, but doesn't get a good indicator of committee
intent.)  It looks more like a C/C++ divergence to me, and so a matter for
a C/C++ liaison.  It takes long enough to argue about what the UK should
submit as a defect report even when we're agreed there is a defect, let
alone to work things out where it isn't clear that there is a defect or
lack of clarity in the standard at all.  (Meetings spent largely
discussing whether to support the registration of WG14 work items and with
little time left for DRs don't help here.)

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: IMA vs tree-ssa

[Mark Mitchell]

Joseph S. Myers wrote:

>On Tue, 9 Mar 2004, Mark Mitchell wrote:
>
>  
>
>>However, I don't think there's any point in all of us debating this
>>issue.  We don't agree on the answer, and none of us has a particularly
>>good way of backing up our position.  To me, this idea of multiple
>>completions of the same incomplete type is ghastly.  You, however,
>>believe it is what the standard requires, and apparently that it is also
>>what the committe intended.
>>    
>>
>
>This seems simply to be a difference between C and C++ backgrounds.  
>Types in C do not have linkage; those in C++ do.  I don't know whether
>this is a deliberate difference, but it is a fairly fundamental one.
>  
>
You and Gaby keep telling me this and I believe you.  I worked on C 
stuff for years before I worked on C++ stuff -- I have roughly as much C 
background as C++ background.

I know that CenterLine's error-checking tools would have complained 
about trying to complete the same type in two different ways in a single 
program, and that our stuff was very widely used, including by AT&T in 
tons of code.  Our design priority was to issue no errors that would 
annoy real users (so, for example, we didn't warn about int/long 
mismatches on systems where they were the same size).  Therefore, the 
fact that we did warn about multiple completions and that we did not get 
complaints suggests that either (a) this doesn't happen very often, or 
(b) users consider it to be a bug when informed that it is happened.

>>I would appreciate it if you would communicate with the C committee to
>>find out what they really intend.  Ultimately, it's their opinion that
>>matters.  We can't resolve this issue just by talking among ourselves.
>>    
>>
>
>What is the actual concrete defect here?  (As far as I know the only
>relevant procedure here is sending DRs - there isn't one for "requests to
>identify intent".  Asking the WG14 reflector a question may get answers
>"obviously yes", "obviously no" and "it's obvious, but I won't say which
>way" to the same question, but doesn't get a good indicator of committee
>intent.) 
>
Well, it would get a good indicator of what other experts on C think the 
intent was.  It can't hurt to get more input, so let's get it!   If all 
the replies agree with one position or the other, we'll have a clear 
indicator.

The defect, in my opinion, is that the standard does not say:

  If there exists a translation unit A such that a tagged type named T 
is incomplete in
  that translation unit, then the program has undefined behavior if 
there is more than
  one translation unit where a tagged type named T is complete and any 
of the
  complete types is not compatible with any of the other complete types.

You are very good with wording such things; you might be able to 
wordsmith that statement more accurately than I, even if you do not 
agree with it.

Note that those words do not imply that there may not exist two 
definitions of a tagged type with the same name; just that if so there 
may not be translation units in which that tag type appears as an 
incomplete type.  The intuition is that either the type is being used 
privately in one or more translation units (in which case it is OK for 
multiple types to have the same name) or it is used publicly (in which 
case all definitions must agree).  If you are using the opaque 
(incomplete) type in a header, then all definitions must match.

I believe that the example that Geoff posted is a compelling argument in 
favor of such a rule.  It is hard for me to believe that the C commitee 
intended that the code he posted have defined behavior.  I'm willing to 
shown otherwise, but I'd like to hear  that some collection of commitee 
members agree that this code is valid before committing us to complex 
machinations in the compiler to deal with this corner case.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Joseph S. Myers]

On Tue, 9 Mar 2004, Mark Mitchell wrote:

> I know that CenterLine's error-checking tools would have complained 
> about trying to complete the same type in two different ways in a single 
> program, and that our stuff was very widely used, including by AT&T in 
> tons of code.  Our design priority was to issue no errors that would 
> annoy real users (so, for example, we didn't warn about int/long 
> mismatches on systems where they were the same size).  Therefore, the 
> fact that we did warn about multiple completions and that we did not get 
> complaints suggests that either (a) this doesn't happen very often, or 
> (b) users consider it to be a bug when informed that it is happened.

There are many cases of bad coding style for which users will want
warnings but which a conforming implementation is meant to accept
(possibly with such a warning).  Making a conforming implementation
involves making all these strange cases work right.  We don't yet have a
conforming implementation in GCC, either for C90 or C99 (though few users
notice the nonconformance to C90), though I hope in future we will be able
to complete the conforming implementations.

> I believe that the example that Geoff posted is a compelling argument in 
> favor of such a rule.  It is hard for me to believe that the C commitee 
> intended that the code he posted have defined behavior.  I'm willing to 
> shown otherwise, but I'd like to hear  that some collection of commitee 
> members agree that this code is valid before committing us to complex 
> machinations in the compiler to deal with this corner case.

Whereas I think that if this example shows any problem, it is that the
requirement that all declarations of an object or function have compatible
type is not explicit about whether the compatibility required is of all 
the types any of the declarations have at any point in their scope.  That 
is, as long as there is only one completed type of an object, including 
the completions of all structure types pointed to within it, recursively, 
there can be no problem.  In his example, an object might be declared of 
type struct bar, and struct foo only afterwards completed (in some 
translation units but not all), and the question would be whether it is 
undefined if the completions of struct foo are incompatible - remembering 
it might only get completed outside the scope of the object declared.  Can 
we say noone would want to implement some form of abstraction this way 
(struct foo being incomplete in most places, but some calls being 
dispatched to different translation units with different completions of 
it, depending on other values in struct bar)?

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: IMA vs tree-ssa

[Mark Mitchell]

>Whereas I think that if this example shows any problem, it is that the
>requirement that all declarations of an object or function have compatible
>type is not explicit about whether the compatibility required is of all 
>the types any of the declarations have at any point in their scope.  That 
>is, as long as there is only one completed type of an object, including 
>the completions of all structure types pointed to within it, recursively, 
>there can be no problem.  In his example, an object might be declared of 
>type struct bar, and struct foo only afterwards completed (in some 
>translation units but not all), and the question would be whether it is 
>undefined if the completions of struct foo are incompatible - remembering 
>it might only get completed outside the scope of the object declared.  Can 
>we say noone would want to implement some form of abstraction this way 
>(struct foo being incomplete in most places, but some calls being 
>dispatched to different translation units with different completions of 
>it, depending on other values in struct bar)?
>  
>
I'm trying to stop debating the issue.

I'm not arguing about what the current standard says; I'm arguing that 
if this example is well-defined, I don't think the commitee intended 
that.  That's one of the common causes of defects: the committee's words 
turn out not to match its intention due to some oversight.  You and Gaby 
and I cannot answer the question of whether or not the commitee intended 
Geoff's example to have defined behavior.  Nor can we answer the 
question of whether or not the commitee would think that, to the extent 
it has defined behavior, that represents a defect in the standard.

I'd appreciate it if you would, rather than trying to convince me, get 
some additional input.  You'd be an excellent choice for that because 
you know the standard very well and write clearly.  You could definitely 
explain the test case and why it is problematic; you could also  offer 
your interpretation and ask whether or not that is what other readers of 
the reflector believe.  The reason I've asked you several times to 
assist in this way is because you would be very good at it.

Are you willing to help in this way?

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Joseph S. Myers]

On Tue, 9 Mar 2004, Mark Mitchell wrote:

> I'd appreciate it if you would, rather than trying to convince me, get 
> some additional input.  You'd be an excellent choice for that because 
> you know the standard very well and write clearly.  You could definitely 
> explain the test case and why it is problematic; you could also  offer 
> your interpretation and ask whether or not that is what other readers of 
> the reflector believe.  The reason I've asked you several times to 
> assist in this way is because you would be very good at it.
> 
> Are you willing to help in this way?

I've added this issue (inconsistent completions of a type involved in a
declaration of an object or function) to my list of pre-DR issues to bring
up for the next UK C Panel meeting.

-- 
Joseph S. Myers
jsm@polyomino.org.uk

Re: IMA vs tree-ssa

[Mark Mitchell]

Joseph S. Myers wrote:

>I've added this issue (inconsistent completions of a type involved in a
>declaration of an object or function) to my list of pre-DR issues to bring
>up for the next UK C Panel meeting.
>  
>
Thank you.

-- 
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com

Re: IMA vs tree-ssa

[Gabriel Dos Reis]

"Joseph S. Myers" <jsm@polyomino.org.uk> writes:

| On Tue, 9 Mar 2004, Mark Mitchell wrote:
| 
| > However, I don't think there's any point in all of us debating this
| > issue.  We don't agree on the answer, and none of us has a particularly
| > good way of backing up our position.  To me, this idea of multiple
| > completions of the same incomplete type is ghastly.  You, however,
| > believe it is what the standard requires, and apparently that it is also
| > what the committe intended.
| 
| This seems simply to be a difference between C and C++ backgrounds.  
| Types in C do not have linkage; those in C++ do.  I don't know whether
| this is a deliberate difference, but it is a fairly fundamental one.

It is a deliberate difference.  But some types in C++ don't have
linkage (but they are not in consideration here).

-- Gaby

Re: IMA vs tree-ssa

[Matthias Benkmann]

On Tue, 9 Mar 2004 10:41:01 +0000 (UTC) "Joseph S. Myers"
<jsm@polyomino.org.uk> wrote:

> > I would appreciate it if you would communicate with the C committee to
> > find out what they really intend.  Ultimately, it's their opinion that
> > matters.  We can't resolve this issue just by talking among ourselves.
> 
> What is the actual concrete defect here?  (As far as I know the only
> relevant procedure here is sending DRs - there isn't one for "requests
> to identify intent".  

You could ask on comp.std.c. I'd assume that you would find some people
who've worked on the standard there.

MSB

-- 
Depression is merely anger without enthusiasm.

Re: IMA vs tree-ssa

[Geoff Keating]

Dale Johannesen <dalej@apple.com> writes:

> On Mar 8, 2004, at 3:32 PM, Joe Buck wrote:
> > On Mon, Mar 08, 2004 at 11:57:00PM +0100, Gabriel Dos Reis wrote:
> >>        [#2] All declarations that  refer  to  the  same  object  or
> >>        function shall have compatible type; otherwise, the behavior
> >>        is undefined.
> > This would seem to suggest that in the situations where non-transitive
> > behavior would otherwise result (for example, an incomplete struct
> > type is
> > compatible with two distinct and incompatible definitions of that
> > struct
> > type), and this matters (for the purpose of aliasing analysis, for
> > example), we have undefined behavior, so the compiler should be able to
> > act as though this situation does not arise and assume transitivity.
> 
> Suppose we have 3 types T1, T2, Tcom such that T1 and T2
> are not compatible, but Tcom is compatible with either T1 or T2.
> Let's call the relationship between T1 and T2 "pseudo-compatible".
> Then:
> 
> Tcom x;
> T1 * p = (T1 *)&x;
> T2 * q = (T2 *)&x;
> 
> foo()
> {
>     T1 x = *p;
>     *q = ...
> }

Could you elaborate a bit on this example?  I don't believe you can write

     T1 x = *p;
     *q = ...

in this case, because one of *p or *q will be incomplete.

> This is not undefined behavior, and the standard says that p and q
> don't alias in foo.

It does, that it says that if you write

  p = &x;
  q = &y;

then you can interchange those two assignments.  It does not, however,
say that *p and *q don't alias.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: IMA vs tree-ssa

[Dale Johannesen]

On Apr 1, 2004, at 4:35 PM, Geoff Keating wrote:

> Dale Johannesen <dalej@apple.com> writes:
>
>> On Mar 8, 2004, at 3:32 PM, Joe Buck wrote:
>>> On Mon, Mar 08, 2004 at 11:57:00PM +0100, Gabriel Dos Reis wrote:
>>>>        [#2] All declarations that  refer  to  the  same  object  or
>>>>        function shall have compatible type; otherwise, the behavior
>>>>        is undefined.
>>> This would seem to suggest that in the situations where 
>>> non-transitive
>>> behavior would otherwise result (for example, an incomplete struct
>>> type is
>>> compatible with two distinct and incompatible definitions of that
>>> struct
>>> type), and this matters (for the purpose of aliasing analysis, for
>>> example), we have undefined behavior, so the compiler should be able 
>>> to
>>> act as though this situation does not arise and assume transitivity.
>>
>> Suppose we have 3 types T1, T2, Tcom such that T1 and T2
>> are not compatible, but Tcom is compatible with either T1 or T2.
>> Let's call the relationship between T1 and T2 "pseudo-compatible".
>> Then:
>>
>> Tcom x;
>> T1 * p = (T1 *)&x;
>> T2 * q = (T2 *)&x;
>>
>> foo()
>> {
>>     T1 x = *p;
>>     *q = ...
>> }
>
> Could you elaborate a bit on this example?  I don't believe you can 
> write
>
>      T1 x = *p;
>      *q = ...
>
> in this case, because one of *p or *q will be incomplete.

Indeed when I wrote this the only examples I could construct used 
multiple
files and IMA.   But see Joseph Myers' response for a single-file case.

>> This is not undefined behavior, and the standard says that p and q
>> don't alias in foo.
>
> It does, that it says that if you write
>
>   p = &x;
>   q = &y;
>
> then you can interchange those two assignments.  It does not, however,
> say that *p and *q don't alias.

Restricting p and q to be non-char, it does; *p and *q have 
non-compatible types.

Re: IMA vs tree-ssa

[Geoff Keating]

> From: Dale Johannesen <dalej@apple.com>
> Date: Thu, 1 Apr 2004 16:53:54 -0800

...
> Indeed when I wrote this the only examples I could construct used 
> multiple
> files and IMA.   But see Joseph Myers' response for a single-file case.

Yes, Joseph's example is good.

> >> This is not undefined behavior, and the standard says that p and q
> >> don't alias in foo.
> >
> > It does, that it says that if you write
> >
> >   p = &x;
> >   q = &y;
> >
> > then you can interchange those two assignments.  It does not, however,
> > say that *p and *q don't alias.
> 
> Restricting p and q to be non-char, it does; *p and *q have 
> non-compatible types.

They have non-compatible types with each other, but that's not the
test for whether two things can't alias; the standard talks about the
'effective type of the object'.  So two accesses can alias if there
could be a type which is compatible with both of the types involved,
even if the two types are not themselves compatible.  If you can work
out what the object's effective type is (which is not always possible
at compile time, since it's a run-time property) then you could test
for compatibility with that, which would be a more precise test.

I don't think this will hurt optimisation much.  The cases involved
are not common.  It's annoying to code, though.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: IMA vs tree-ssa

[Dale Johannesen]

On Apr 2, 2004, at 10:18 AM, Geoff Keating wrote:
>> Restricting p and q to be non-char, it does; *p and *q have
>> non-compatible types.
>
> They have non-compatible types with each other, but that's not the
> test for whether two things can't alias; the standard talks about the
> 'effective type of the object'.  So two accesses can alias if there
> could be a type which is compatible with both of the types involved,
> even if the two types are not themselves compatible.  If you can work
> out what the object's effective type is (which is not always possible
> at compile time, since it's a run-time property) then you could test
> for compatibility with that, which would be a more precise test.

OK, I believe that.  Then what we have is a bug.  Do you agree the
following is standard-conforming?  It gets different results with 
different
options on ppc; the pointer  derefs in foo have different alias classes,
and the scheduler does not find a dependency between them.

unsigned int a, b;
enum e1 { x, y, z };
enum e2 {t,u,v};
void foo (enum e1* e1p, enum e2* e2p, int x)
{ *e1p = x;
   b = *e2p; }

main() {
   enum e1* e1p = (enum e1*) &a;
   enum e2* e2p = (enum e2*) &a;
   foo (e1p, e2p, 3);
   printf("%d\n", b);
}

Re: IMA vs tree-ssa

[Geoff Keating]

Dale Johannesen <dalej@apple.com> writes:

> On Apr 2, 2004, at 10:18 AM, Geoff Keating wrote:
> >> Restricting p and q to be non-char, it does; *p and *q have
> >> non-compatible types.
> >
> > They have non-compatible types with each other, but that's not the
> > test for whether two things can't alias; the standard talks about the
> > 'effective type of the object'.  So two accesses can alias if there
> > could be a type which is compatible with both of the types involved,
> > even if the two types are not themselves compatible.  If you can work
> > out what the object's effective type is (which is not always possible
> > at compile time, since it's a run-time property) then you could test
> > for compatibility with that, which would be a more precise test.
> 
> OK, I believe that.  Then what we have is a bug.  Do you agree the
> following is standard-conforming?  It gets different results with
> different
> options on ppc; the pointer  derefs in foo have different alias classes,
> and the scheduler does not find a dependency between them.

Yes, I agree, this is conforming:

> unsigned int a, b;
> enum e1 { x, y, z };
> enum e2 {t,u,v};
> void foo (enum e1* e1p, enum e2* e2p, int x)
> { *e1p = x;
>    b = *e2p; }
> 
> main() {
>    enum e1* e1p = (enum e1*) &a;
>    enum e2* e2p = (enum e2*) &a;
>    foo (e1p, e2p, 3);
>    printf("%d\n", b);
> }

It should be easy to fix, just assign enums the same alias set as
their underlying type.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: IMA vs tree-ssa

[Mark Mitchell]

Gabriel Dos Reis wrote:

>I suspect your C++ brackground is showing up :-)
>
>I believe Neil is right. See 
>  
>
[standard clipped]

Thanks for forwarding that, but, as it happens, I'd read it before I 
replied.

I'm not so much questioning what it actually says as I am questioning 
what it meant to say.

In other words, I'm saying I think that this non-transitivity is a defect in the standard, rather than an intentional thing.

--
Mark Mitchell
CodeSourcery, LLC
(916) 791-8304
mark@codesourcery.com