C provenance semantics proposal

[Richard Biener]

On Wed, Apr 24, 2019 at 11:18 PM Peter Sewell <Peter.Sewell@cl.cam.ac.uk> wrote:
>
> On 24/04/2019, Jeff Law <law@redhat.com> wrote:
> > On 4/24/19 4:19 AM, Richard Biener wrote:
> >> On Thu, Apr 18, 2019 at 3:42 PM Jeff Law <law@redhat.com> wrote:
> >>>
> >>> On 4/18/19 6:20 AM, Uecker, Martin wrote:
> >>>> Am Donnerstag, den 18.04.2019, 11:45 +0100 schrieb Peter Sewell:
> >>>>> On Thu, 18 Apr 2019 at 10:32, Richard Biener
> >>>>> <richard.guenther@gmail.com> wrote:
> >>>>
> >>>>
> >>>>> An equality test of two pointers, on the other hand, doesn't
> >>>>> necessarily
> >>>>> mean that they are interchangeable.  I don't see any good way to
> >>>>> avoid that in a provenance semantics, where a one-past
> >>>>> pointer might sometimes compare equal to a pointer to an
> >>>>> adjacent object but be illegal for accessing it.
> >>>>
> >>>> As I see it, there are essentially four options:
> >>>>
> >>>> 1.) Compilers do not use conditional equivalences for
> >>>> optimizations of pointers (or only when additional
> >>>> conditions apply which make it safe)
> >>> I know this will hit DOM and CSE.  I wouldn't be surprised if it touches
> >>> VRP as well, maybe PTA.  It seems simple enough though :-)
> >>
> >> Also touches fundamental PHI-OPT transforms like
> >>
> >>  if (a == b)
> >> ...
> >>
> >>  # c = PHI <a, b>
> >>
> >> where we'd lose eliding such a conditional.  IMHO that's bad
> >> and very undesirable.
> > But if we only suppress this optimization for pointers is it that terrible?
>
> As far as I can see right now, there isn't a serious alternative.
> Suppose x and y are adjacent, p=&x+1, and q=&y, so p==q might
> be true (either in a semantics for the source-language == that just
> compares the concrete representations or in one that's allowed
> but not required to be provenance-sensitive).   It's not possible
> to simultaneously have *p UB (which AIUI the compiler has to
> have in the intermediate language, to make alias analysis sound),
> *q not UB, and p interchangeable with q.    Am I missing something?

No, you are not missing anything.  We do have this issue right now,
independent of standard wordings.  But the standard has that, too,
not allowing *(&x + 1), allowing the compare and allowing *&y.
Isn't that a defect as well?

Richard.

> Peter
>
>
> >
> >>>>
> >>>> 3.) We make comparison have the side effect that
> >>>> afterwards any of the two pointers could have any
> >>>> of the two provenances. (with disambiguitation
> >>>> similar to what we have for casts).
> >>> This could have some interesting effects on PTA.  Richi?
> >>
> >> I played with this and doing this in an incomplete way like
> >> just handling
> >>
> >>   if (a == b)
> >>
> >> as two-way assignment during constraint building is possible.
> >> But that's not enough of course since every call is implicitely
> >> producing equivalences between everything [escaped] ...
> >> which makes points-to degrade to a point where it is useless.
> > But the calls aren't generating conditional equivalences.  I must be
> > missing something here.  You're the expert in this space, so if you say
> > it totally degrades PTA, then it's a non-starter.
> >
> >>
> >> So I think we need a working scheme where points-to doesn't
> >> degrade from equivalencies being computed and the compiler
> >> being free to introduce equivalences as well as copy-propagate
> >> those.
> >>
> >> Honestly I can't come up with a working solution to this
> >> problem.
> >>
> >>>
> >>>>
> >>>> 4.) Compilers make sure that exposed objects never
> >>>> are allocated next to each other (as Jens proposed).
> >>> Ugh.  Not sure how you enforce that.  Consider that the compiler may
> >>> ultimately have no control over layout of data in static storage.
> >>
> >> Make everything 1 byte larger.
> > Not a bad idea.  I suspect the embedded folks would go bananas though.
> >
> > jeff
> >
> >