Am Mittwoch, den 29.01.2020, 09:45 +0100 schrieb Richard Biener:
> On Tue, Jan 28, 2020 at 1:24 PM Uecker, Martin
> <martin.uec...@med.uni-goettingen.de> wrote:
> > >
> > > Note for the current PTA implementation there's almost no cases we can
> > > handle conservatively enough. Consider the simple
> > >
> > > int a[4];
> > > int *p = &a[1];
> > > uintptr_t pi = (uintptr_t)p;
> > > pi += 4;
> > > int *q = (int *)pi;
> > >
> > > our PTA knows that p points to a (but not the exact offset), same for pi
> > > (the cast doesn't change the value). Now you add 4 - this could lead
> > > you outside of 'a' so the points-to set becomes 'a and anything'.
> >
> > PVNI would say that 'a' gets exposed in the first case and
> > then 'q' can point to all exposed objects because of the
> > second cast.
> >
> > A correct and conservative implementation would do this:
> > In the PTA you would need to mark the address of a escaped
> > and then later assign a conservative points-to set (all
> > escaped objects) to q.
>
> I see (I'm asking all these questions to see what implementing -fpta-pnvi
> would mean).
Thank you for looking into this.
> That might be a feasible implementation route. How
> does "escaped" as used in your answer apply when doing inter-procedural
> analysis? I guess we would need to assume points-to sets include
> automatic variables that escaped in the caller.
Yes. Is this not something the compiler assumes in general?
If you have code like this:
int pi = foo(p);
int *q = bar(pi);
where 'foo' and 'bar' are unknown to the compiler, it
should have the same semantics with regard to PTA
as needed for the casts in PVNI.
(except that one knows that q and p have the same
value which could be exploited for optimization)
> > Yes, this limits optimizations, but I do not think this is
> > terrible. (optimizations could be re-enabled with a compiler
> > option)
>
> We'll see.
>
> > > I'm also not sure what PVNI does to
> > >
> > > int a[4];
> > > int *p = &a[1];
> > > p += 10;
> > > uintptr_t pi = (uintptr_t)p;
> > > p = (int *)pi;
> > >
> > > we assume that p points to a even after p += 10 (but it of course points
> > > outside of the object - obvious here, but not necessarily in more
> > > obfuscated cases).
> >
> > This is UB because a pointer to outside of the object is formed.
> >
> > > Now, can we assume pi points to a? The cast isn't value-changing. Do we
> > > have
> > > to assume (int *)pi points to anything? So, is
> > >
> > > p = (int *)(uintptr_t)p;
> > >
> > > something like "laundering" a pointer? We don't preserve such simple
> > > round-trip
> > > casts since they are value-preserving. Are they provenance preserving?
> >
> > Yes, such a pair would be "laundering" as it allows 'p' to then
> > point to any exposed object provenance-wise.
> >
> > For such casts the FE would maybe add a marker. Maybe a calls
> > to builtin functions 'builtin_expose(a)' and 'builting_bless'.
> > (having those builtins would be interesting on its own, btw).
>
> Uh, ok.
For testing, I implemented builtin_expose by adding
in 'find_func_aliases_for_builtin_call'
case BUILT_IN_ESCAPE:
{
make_escape_constraint (gimple_call_arg (t, 0));
return true;
}
which seems to work, but I wasn't sure about
the other function.
There are concurrent algorithms which revive dead pointers.
They might also need explicit control to work around provenance
issues.
> > Having said this, some optimizations could still be allowed using
> > the "as-if" rule and other lines of reasoning. Specifally, PVNI
> > states that 'p' gets assigned the provenance of the object the
> > integer values is the address of. So if the compiler can proof
> > that the address belongs to certain objects it can reassign the
> > points-to set to the new 'p'. Only if there is ambiguity between
> > which objects the address belongs to, the reasoning needs to
> > be more conservative.
> >
> > For example:
> > int a[3];
> > int b[3];
> >
> > &b; // b also exposed
Correction: this should be:
(intptr_t)&b;
as it is the cast to integers and not just the address-taken
operation that marks the object exposed.
> > int *p = (int*)(uintptr_t)&a[3];
> >
> > Here, p could point to the one-after address of 'a' or the
> > first element of 'b'. (but only because 'b' was also exposed).
> >
> > If the compiler can prove that something like this can not
> > happen (e.g. by considering offsets), it can still do some
> > tracking of points-to sets.
>
> That's probably the very case that we'll get wrong since
> we definitely won't be able to reliably preserve these
> kind of laundering points...
Maybe the FE could add the builtins ?
> I guess they could be obfuscated like
>
> union { void *p; long l; } u;
>
> u.p = p;
> u.l = u.l;
> p = u.p;
>
> where GCC (and IIRC also now the standard) allows the
> type-punning when reading u.p via u.l and vice versa.
It is allowed in C but not in C++.
> That is, the "conversions" might be hidden in the
> memory access types. That means (our PTA tracks
> points-to sets of memory) that all stores of pointers
> (even to automatic vars that are themselves not exposed)
> make them escaped and CSE would need to desperately
> avoid CSEing the load from u.p to p or insert laundering
> operations.
I am not sure I fully understand the proposal.
> I guess I'd me much more happy if PVNI said that when
> an integer is converted to a pointer and the integer
> is value-equivalent to pointers { p1, p2, ... } then
> the provenance of the resulting pointer is
> that of p1 (or p2, ... which is semantically equivalent)
(if the provenance is the same)
> and when two pointers p1 and p2 are
> value-equivalent and their provenance is not the
> same then the behavior is undefined.
I see. Then here..
int a[3];
int b[3];
(uintptr_t)&b[0]; // b also exposed
int *p = (int*)(uintptr_t)&a[3];
..the behavior is undefined because the
two pointers have identical addresses
but different provenance.
I agree, from a compiler writer's point-of-view
this would be a good solution. But to a programmer,
this would be quite difficult to explain.
The preference of the working group was that the casts
should just work in all cases and do what the
programmer intended, even if this prevents some
optimization. But I will see that this is
added to the list of options under consideration.
PVNI-ae-ud assigns the provenance of an
exposed object at the address. If there
are two possible objects (as in the example
above), the pointer could point to both but
then has to be used consistently only with
only one object. Essentially, we want the
pointer to have exactly one provenance but
we might delay the decision. The idea is
that a compiler might figure out the correct
provenance later, e.g. by observing accesses.
It is possible to formulate
some conditions about when a pointer converted
from an integer could get assigned the
points-to-set of a value-equivalent pointer:
1) using knowledge about object location in
memory: If there is no adjacent object which
was exposed, one can conclude that the
provenance is the object at this address.
2) based on offsets: If the pointer points
in the middle of an object, there is also
no ambiguity.
3) a mix of both, to differentiate objects
before and after in memory.
> That is,
>
> int a, b;
> int *p = &a + 1;
> int *q = &b;
> if (p == q)
> ... undefined ...
We considered making the comparison undefined in the
specific situation where one of the pointer is one-after
pointer and the other a pointer to the beginning of a
different object. This would solve the problems with
conditional equivalences.
Others proposed to make the result of the comparison
unspecified, but I think this does not help.
At the moment, the consensus is that pointer
comparison should be always allowed and the
result should only depend on the address. Again,
the idea is to make is simpler and more consistent
for the programmer. But yes, this makes it more
difficult for the compiler writer.
Best,
Martin
