C++ Logo


Advanced search

Re: [std-proposals] P2815 breaks all provenance-related optimizations

From: connor horman <chorman64_at_[hidden]>
Date: Wed, 22 Feb 2023 11:54:55 -0500
On Wed, 22 Feb 2023 at 09:31, Anthony Williams <
anthony_at_[hidden]> wrote:

> Hi,
> Thanks for forwarding the email to me Arthur.
> On 22/02/2023 12:57, Arthur O'Dwyer wrote:
> On Tue, Feb 21, 2023 at 9:53 PM connor horman via Std-Proposals <
> std-proposals_at_[hidden]> wrote:
>> I just learned of P2815, and I do not know of another place I can respond
>> to it, so I'm going to answer here.
> The presentation's title slide (and unfortunately nowhere else — I missed
> it the first time too!) refers to P2188:
> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p2188r1.html
> which, being a WG21 paper, contains contact info for the author. I've
> cc'ed him here.
> In my opinion, the proposal in question eliminates all provenance based
>> alias analysis, used to eliminate memory accesses when unanalyzed code is
>> present.
> These were the slides of the presentation I did for EWG. They are in the
> mailing as a record; as the title suggests, this is a presentation of the
> paper that Arthur linked to. As for most presentations, there were a lot of
> things I said that are not on the slides.
> Also, as Thiago points out, this is my opinion, not an accepted proposal
> or statement by the committee as a whole.
> The fundamental point of the paper, and thus the presentation, is that the
> standard is inconsistent. The paper and presentation present a series of
> things that are true about trivially copyable types, by the wording of the
> standard. The problem is that the standard then says that (a) pointers are
> trivially copyable types, and (b) some of these properties don't apply to
> them.
> We need to fix it. Ideally in a way that (a) doesn't break too much
> preexisting code that relies on these properties applying to pointers (and
> there is a lot that has been written over the years, and is currently in
> production, working just fine), and (b) doesn't rule out too many
> optimization techniques and opportunities.
>> Consider the following example code:
>> int foo(int* p){
>> int i;
>> opaque_operation(&i,p);
>> i = 0;
>> *p = 1;
>> return i;
>> }
>> (Where the optimizer is unable to analyze `opaque_operation`
>> In current compilers, this can be optimized to [...
> int foo(int *p) {
> int i; opaque_operation(&i, p);
> *p = 1; return 0;
> }
> ...]. Under the proposal, however, `opaque_operation` could observe that
>> `&i` and `p` have the same *value representation*, which means that they
>> must be equal (it may do so with defined behaviour in all executions, for
>> example, by terminating if they are bytewise unequal). Thus the write to
>> `p` may modify the value of `i`. This would make the transformation [...]
>> invalid under the proposal.
> This isn't a proposal (yet), it's my interpretation of current words in
> the standard. If you agree with my analysis, and the conclusion that this
> rules out optimizations, *they have always been ruled out*, and any
> compiler that did them would always have been non-conforming.
> If you disagree with my interpretation, I would love to see specific
> references to where my logic is wrong, and/or how you would fix the
> inconsistency.
The main thing that solves this in the current standard, *I believe*, is
the wording that the operations (which includes comparison, copying, and
presumably bytewise analysis) on invalid pointer values that have defined
behaviour are unspecified (or implementation-defined). That being said, if
my interpretation is indeed wrong, then I concede that, as you say, the
optimizations were always ruled out. In the latter case, it is likely
necessary to then propose changes to the standard that rule them in
(perhaps retroactively). I would refer to my point from a Rust Language
Team Design Meeting (I was going to give a citation, but apparently the
statement didn't end up in the minutes from that meeting), that these
optimizations are relied upon by anyone writing any code that has any kind
of performance requirements. I don't believe that banning them wholesale is
an option for C++ any more than I thought it was an option for Rust.

> Anyway, in this case, the optimization cannot be permitted if &i could
> have the same bytes as the value passed as p. It would be easy for the
> compiler to check that prior to calling opaque_operation, but that would
> change the codegen.
It certainly could, but the extra branch that would entail is fun. The
compiler would have to determine whether the address it gives `i` for `&i`
is actually the same as `p`, then add `alignof(int)` to the address of `i`
instead. In which case, in the hypothetical, the program aborts
consistently. However, the compiler doing that would likely have a greater
cost than the memory accesses it saves, when it is actually fairly trivial
on compilers today to maliciously guess the address `i` will get.

> So I don't think you're correct to worry that P2188 / P2815 would
> completely destroy *all* provenance-based optimizations. It needs to
> propose some wording before we can say anything concrete about it, of
> course. And it might end up destroying some optimizations. But it needn't
> destroy all of them. And at first glance it doesn't seem out-of-keeping
> with the direction of C++.
> (Likewise, the existence of `reinterpret_cast` doesn't destroy all
> type-based alias analysis. And `const_cast` famously destroys some-
> *but-not-all* const-based optimizations.)
> Here I agree with Arthur. If people agree with my conclusions, then some
> provenance-based optimizations are ruled out. Not all of them, but maybe a
> lot. That's a price I'm willing to pay for the knowledge that the language
> is self-consistent in what it means for something to be a trivially
> copyable type.
Reading this full email, C++ adopting a solution like like the one I cited
from Rust might even be viable solution to both problems - copying the
object representation preserves the pointer value (including the compiler's
magic shadow state provenance) , but observing the object representation
via `memcmp` doesn't necessarily give you all the information to
distinguish the value. I've even thought of potential wording that could

1. A pointer value is *distinguishable by bitwise comparison *if:
(1.1) One is a null pointer, and the other is not a null pointer,
(1.2) One is a pointer to a function, and the other is a pointer to an
object or one past the end of an object,
(1.3) Both are pointers to objects within their storage duration, or
(1.4) Both are pointers past the end of objects within their storage
2. Certain operations compare pointer values by examining their *value
representation*. These operations are known as *bitwise comparison* or *bitwise
equality* operations.
[Note 1: For example, the function memcmp ([cstr.syn]),
compare_exchange_strong or compare_exchange_weak
3. When applying a *bitwise comparison *or *bitwise equality* operation to
the complete *value representation* of two pointer objects with *compatible
pointer types* Then the result is as follows:
(3.1) If two pointers compare equal, then a *bitwise equality* operation
applied to those pointers shall treat the pointers as equivalent.
(3.2) Otherwise, the pointers shall be treated as not-equivalent if the
pointers are *distinguishable by bitwise comparison*.
(3.3) If two pointers participate in the partial order for comparing
pointers ([expr.rel]), then a *bitwise comparison* operation shall return a
result consistent with that partial order.
(3.4) Otherwise, the *bitwise comparison* shall order the pointers
according to some *unspecified* total order if the pointers are
by bitwise comparison. *
(3.5) In all other cases for these operations, the result is *unspecified*.
4. If two pointers are *distinguishable by bitwise comparison* and treated
as equivalent by a *bitwise comparison* or *bitwise equality* operation,
then they are identical pointer values
[Note 2: This means that the two pointers may be used for the same
operations, and will have the same results]

And then allow copying invalid pointers, in a way that preserves the *value

> Cheers,
> Anthony

Received on 2023-02-22 16:55:09