Re: g++ and aliasing bools

[Daniel Berlin <dan at dberlin dot org>]

On Fri, 25 Jan 2002, Robert Dewar wrote:

> <<> The problem before us is to narrow down the may-alias relationship as far
> > as possible statically. There is no issue of undecidability here.
> Of course there is, which is why you conservatively assume that everything
> aliases everything else until you prove otherwise.
> I've been told i need to come up with a formal proof that given certain
> relationships between C++ types, that may-alias is always determinable
> statically correctly, or that we always correctly determine that we can't
> determine it (IE never claim wrong that things may not alias).
> I've said before, and i'll say again, that i'm not going to do that.
> >>
> 
> Nope, this is plain confused. 
No, once again, it's not.
> It is undecidable in general whether two
> objects will be aliased at run time (that's so trivial to prove that it
> is a silly and useless observation).
> 
> But it is not a problem, it merely says that the alias sets we create are
> simply conservative estimates. 
Yes.
> And we need to prove that they are indeed
> conservative estimates. We need to be able to prove that elements of
> separate sets are indeed never aliased. 
Herein lies the point you've ignored.  Using only the C++ language 
standard, we can't do that, and it's quite possible we may place 
things into separate sets that do in fact alias, because of the 
implementation specific details.
> The fact that we can't prove that
> elements of the *same* set *are* aliased is obvioulsy and trivially true,
> but quite irrelevant.
Yes.

> 
> <<But claiming that undecidability doesn't enter anyway is simply wrong.
> I'm claiming that undecidability enters the picture in another way as
> well. The C++ language specification does not give you enough information
> in our case to determine that we can determine it or not. We can't always
> say whether or not we can say whether two pieces of two types alias.
> >>
> 
> You are still hung up on the idea that the problem we are trying to solve
> is to determine whether two items are aliased. That's NOT the problem here.
> THe problem is to determine sets of items that are provably not aliased. These
> are quite different problems, and you are getting confused between them.
No, i'm not confused at all, or hung up at all.
You have simply missed the point that the language semantics of C++ alone 
don't give you enough to get the sets of items that don't alias 
*correctly*, because they don't tell you the implementation specific details.
The question is whether our ABI gives us enough, and is written in such a 
way that does enable us to determine the sets of non-aliasing items 
*correctly*.

>