From: Peter Sewell <Peter.Sewell@cl.cam.ac.uk>
To: Jeff Law <law@redhat.com>
Cc: Richard Biener <richard.guenther@gmail.com>,
"Uecker, Martin" <Martin.Uecker@med.uni-goettingen.de>,
"gcc@gcc.gnu.org" <gcc@gcc.gnu.org>,
"cl-c-memory-object-model@lists.cam.ac.uk"
<cl-c-memory-object-model@lists.cam.ac.uk>
Subject: Re: C provenance semantics proposal
Date: Wed, 24 Apr 2019 21:19:00 -0000 [thread overview]
Message-ID: <CAHWkzRQkg+WNWENOonuJhOsGnzJnM2ec+pz6KLiX_F5JHjVnVw@mail.gmail.com> (raw)
In-Reply-To: <917e49da-bc4f-80a8-3399-30fff4a573f0@redhat.com>
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?
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
>
>
next prev parent reply other threads:[~2019-04-24 21:19 UTC|newest]
Thread overview: 56+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-04-02 8:11 Peter Sewell
2019-04-12 14:51 ` Jeff Law
2019-04-12 15:31 ` Peter Sewell
2019-04-17 9:06 ` Richard Biener
2019-04-17 9:15 ` Peter Sewell
2019-04-17 9:41 ` Richard Biener
2019-04-17 11:53 ` Uecker, Martin
2019-04-17 12:41 ` Richard Biener
2019-04-17 12:56 ` Uecker, Martin
2019-04-17 13:35 ` Richard Biener
2019-04-17 14:12 ` Uecker, Martin
2019-04-17 17:31 ` Peter Sewell
2019-04-18 9:32 ` Richard Biener
2019-04-18 9:56 ` Richard Biener
2019-04-18 10:48 ` Peter Sewell
2019-04-18 11:57 ` Uecker, Martin
2019-04-18 12:31 ` Richard Biener
2019-04-18 13:25 ` Uecker, Martin
2019-04-18 10:45 ` Peter Sewell
2019-04-18 12:20 ` Uecker, Martin
2019-04-18 12:42 ` Richard Biener
2019-04-18 12:47 ` Jakub Jelinek
2019-04-18 12:51 ` Jakub Jelinek
2019-04-18 13:29 ` Jeff Law
2019-04-24 10:12 ` Richard Biener
2019-04-18 13:49 ` Uecker, Martin
2019-04-19 8:19 ` Jens Gustedt
2019-04-19 8:49 ` Jakub Jelinek
2019-04-19 9:09 ` Jens Gustedt
2019-04-19 9:34 ` Jakub Jelinek
2019-04-21 8:15 ` Jens Gustedt
2019-04-24 10:24 ` Richard Biener
2019-04-24 18:43 ` Jeff Law
2019-04-24 19:21 ` Jens Gustedt
2019-04-19 9:11 ` Peter Sewell
2019-04-19 9:15 ` Jens Gustedt
2019-04-19 9:35 ` Peter Sewell
2019-04-19 10:35 ` Uecker, Martin
2019-04-19 10:01 ` Uecker, Martin
2019-04-18 13:42 ` Jeff Law
2019-04-18 13:54 ` Uecker, Martin
2019-04-18 14:49 ` Peter Sewell
2019-04-18 15:09 ` Uecker, Martin
2019-04-24 10:19 ` Richard Biener
2019-04-24 18:41 ` Jeff Law
2019-04-24 19:30 ` Philipp Klaus Krause
2019-04-24 19:55 ` Uecker, Martin
2019-04-24 19:33 ` Jakub Jelinek
2019-04-24 21:19 ` Peter Sewell [this message]
2019-04-25 12:42 ` Richard Biener
2019-04-25 13:03 ` Peter Sewell
2019-04-25 13:13 ` Richard Biener
2019-04-25 13:20 ` Peter Sewell
2019-04-29 14:31 ` Joseph Myers
2019-04-25 12:39 ` Richard Biener
2019-05-09 11:26 ` Ralf Jung
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CAHWkzRQkg+WNWENOonuJhOsGnzJnM2ec+pz6KLiX_F5JHjVnVw@mail.gmail.com \
--to=peter.sewell@cl.cam.ac.uk \
--cc=Martin.Uecker@med.uni-goettingen.de \
--cc=cl-c-memory-object-model@lists.cam.ac.uk \
--cc=gcc@gcc.gnu.org \
--cc=law@redhat.com \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).