Re: g++ and aliasing bools

[Daniel Berlin <dan at dberlin dot org>]

On Fri, 25 Jan 2002, Daniel Berlin wrote:

> 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.
Pardon, Actually, the other Dan suggested it, and I said I thought it was 
a good idea, which is what started the whole discussion.

In hindsight, i should never have replied to mark, and just left C++ TBAA 
in the mostly non-existent state it is in now, for another 5 years.

To give you some idea about how annoying it is to prove it one way or 
another, it would likely take less time, and more productive, to implement 
one of the newer interprocedural, incremental, pointer analysis algorithms (be 
they flow-sensitive or flow-insensitive), and use the TBAA as a 
disambiguation, rather than *as* our  points-to sets.

That way, you'd both improve our aliasing for C, as well as give us some 
information on aliasing for C++, without dealing with type issues at all.

Which, if i wasn't busy with law school and the bugzilla stuff, is likely 
what i'd do instead of writing up proofs, since these algorithms have 
already been proven, and I think most of them can handle structure field 
aliasing as a basic case anway, without any regards as to the actual type 
of the structure field. Though obviously not as well as you can do once 
you've got type based disambiguation to tell you for certain either way.


--Dan