[PATCH] doc: clarify the situation with pointer arithmetic

[Uecker, Martin]

Hi Richard,

thank you for your response. 


Am Montag, den 27.01.2020, 15:42 +0100 schrieb Richard Biener:
> On Fri, Jan 24, 2020 at 12:46 AM Uecker, Martin
> <Martin.Uecker@med.uni-goettingen.de> wrote:
> > 
> > Am Donnerstag, den 23.01.2020, 14:18 +0100 schrieb Richard Biener:
> > > On Wed, Jan 22, 2020 at 12:40 PM Martin Sebor <msebor@gmail.com> wrote:
> > > > 
> > > > On 1/22/20 8:32 AM, Richard Biener wrote:
> > > > > On Tue, 21 Jan 2020, Alexander Monakov wrote:
> > > > > 
> > > > > > On Tue, 21 Jan 2020, Richard Biener wrote:
> > > > > > 
> > > > > > > Fourth.  That PNVI (I assume it's the whole pointer-provenance stuff)
> > > > > > > wants to get the "best" of both which can never be done since a compiler
> > > > > > > needs to have a way to be conservative - in this area it's conflicting
> > > > > > > conservative treatment which is impossible.
> > > > > > 
> > > > > > This paragraph is unclear, I don't immediately see what the conflicting goals
> > > > > > are. The rest is clear enough given the previous discussions I saw.
> > > > > > 
> > > > > > Did you mean the restriction that you cannot do arithmetic involving two
> > > > > > integers based on pointers, get a value corresponding to one of them,
> > > > > > cast it back and get a pointer suitable for accessing either of two
> > > > > > originally pointed-to objects? I don't see that as a conflict because
> > > > > > it places a restriction on users, not the compiler.
> > > > > 
> > > > > As far as I remember the discussions PNVI requires to track
> > > > > provenance for correctness, you may not miss or attach wrong provenance
> > > > > to a pointer and there's only "single" provenance, not "many"
> > > > > (aka, may point to A and B).  I don't see how you can ever implement that.
> > 
> > I have not idea how you came to that conclusion. PNVI is perfectly
> > compatible with a naive compiler who does not track provenance at
> > all as well as an abstract machine that actually carries run-time
> > provenance around with each pointer and checks every operation.
> > It was designed specifically to allow both cases and everything
> > in between (especially compilers who track provenance during
> > compile time but the programs then do not track provenance at
> > run-time).
> > 
> > You may be confused by the abstract formulation that indeed
> > assigns a single provenance to each pointer. A compiler would
> > track its *knowledge about provenance*, which would be a set
> > of possible targets.
> 
> Well, the question is whether PVNI allows the compiler to put any
> additional restriction on what the provenance of an interger is.  It
> appears not, so any attempt to track provenance through integers
> is doomed until the cases are very simple.  I'm not sure that's desirable (*).

PVNI makes something which is now implementation
defined have well defined semantics. This is not possible to do
without putting additional restrictions on the compiler and
this will make some optimizations non-compliant. In both
committees  (C and C++) there is a consensus that the
rules about provenance should be made clear and explicit.
So far, this is the only well-developed proposal.

....

> > > Well, PNVI limits optimization opportunities of GCC which currently
> > > _does_ track provenance through integers and thus only allows
> > > a very limited set(*) of "unrelated" pointers to appear here (documented
> > > is that none are, implementation details differ from version to version).
> > > 
> > > There are no optimization "opportunities" by making pointer <-> integer
> > > conversions lose information.
> > 
> > You are right: It is meant to constrain optimizations.
> > 
> > The reasoning behind this that currently all compilers behave
> > inconsistently and this is not terrible useful to anybody.
> > 
> > At the same time, there does not appear to
> > be any reasonable way how integers can have provenance.
> > Any rules we came up with really got complicated and are
> > also fundamentally at odds with the usual mathematical
> > properties of integers one would naively expect.
> 
> So the original point where GCC started to track provenance through
> non-pointers (PVNI should really be PVNNP since I guess tracking
> provenance through floats isn't to be done either ;)) was a testcase
> showing that Matlab (IIRC) generated C code funneled pointers through
> a pair of floats (obviously a single float isn't enough for 64bit pointers ...)
> and that prevents a good deal of optimization due to missed alias analysis.
> I fixed that and now GCC happily tracks provenance through a pair of
> floats ...

Yes,  this is impressive. And yes, the proposal would
forbid this (i.e. doing aliasing analysis based on the provenance
tracked through integers). 

PVNI would make the Matlab code well-defined (under some
conditions), but break the optimization based on tracking
provenance through floats. But as the currently the code is not
portable at all, I do not think it is really a problem if
we compiler offers this optimization only as a non-standard
compiler option.


> (*) this also shows the level of "obfuscation" needed to fool compilers
> to lose provenance knowledge is hard to predict.

Well, this is exactly the problem we want to address by defining
a clear way to do this. Casting to an integer would be the way
to state: "consider the pointer as escaped and forget the 
provenance"  and casting an integer to a  pointer would
mean "this pointer may point to all objects whose pointer has
escaped". This would give the programmer explicit control about
this aspect and make most existing code using pointer-to-integer
casts well-defined. At the same time, this should be simple
to add to existing points-to analysis.

Best,
Martin