Re: g++ and aliasing bools

[Daniel Berlin <dan at dberlin dot org>]

On Fri, 25 Jan 2002, Robert Dewar wrote:

> <<Undecidability is not just based on run-time behavior of the program.
> It's also undecidable in the static case.
> may-alias is undecidable statically, as is must-alias (Unless i'm
> misremembering).
> >>
> 
> This is confused.
No, it's not, it's perfectly true.
> 
> May-alias is a predicate with many possible solutions. One not very useful
> solution is that anything may alias anything else. We are not interested
> in whether something actually IS aliased at run time. We are interested
> just in the subset of cases that we can prove do NOT alias. 
Well, duh.
> 
> 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.

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.
Our C++ ABI may or may not allow us to do it, since it gives us some, 
possibly all, of the information  the C++ standard leaves to 
implementations.
I'm not going to spend time trying to formally prove it one way or the 
other.

Which brings us back to the reason i suggested we improve it for a 
restricted subset of C++ classes that we already handle properly for C.

--Dan