On Fri, Jan 31, 2020 at 1:05 PM Uecker, Martin <martin.uec...@med.uni-goettingen.de> wrote: > > Am Freitag, den 31.01.2020, 09:02 +0100 schrieb Richard Biener: > > On Thu, Jan 30, 2020 at 6:09 PM Uecker, Martin > > <martin.uec...@med.uni-goettingen.de> wrote: > > > > > > Am Donnerstag, den 30.01.2020, 16:50 +0000 schrieb Michael Matz: > > > > Hi, > > > > > > > > On Thu, 30 Jan 2020, Uecker, Martin wrote: > > > > > > > > > > guarantees face serious implementation difficulties I think > > > > > > so the only alternative to PVNI (which I think is implementable > > > > > > but at a optimization opportunity cost) is one that makes > > > > > > two pointers with the same value always have the same > > > > > > provenance (and otherwise make the behavior undefined). > > > > > > > > > > This would need to come with precise rules about > > > > > when the occurance of two such pointers is UB, > > > > > e.g. comparisons of such pointers, or that > > > > > two such pointers are cast to int in the same > > > > > execution. > > > > > > > > > > The mere existance of such pointers should be > > > > > quite common and should not already be UB. > > > > > > > > > > But I am uncomfortable with the idea that > > > > > comparison of pointers is always allowed except > > > > > for some special case which then is UB. This > > > > > might cause are and very difficult to find bugs. > > > > > > > > As Richi said, the comparison itself wouldn't be UB, all comparisons > > > > would > > > > be allowed. But _if_ the pointers compare equal, they must have same > > > > (or > > > > overlapping) provenance (i.e. when they have not, then _that_ is UB). > > > > > > Sorry, I still don't get it. In the following example, > > > > > > int a[1]; > > > int b[1]; > > > > > > it is often the case that &a[1] and &b[0] compare equal > > > because they have the same address but the pointer > > > have different provenance. > > > > > > Or does there need to be an actual evaluation of a comparison > > > operations? In this case, I do not see the difference to what > > > I said. > > > > I guess I wanted to say that if you do > > > > if (&a[1] == &b[0]) > > if (&a[1] != &b[0]) > > abort (); > > > > then the abort might happen. I'm using the term "undefined behavior" > > here. So whenever you create a value based on two pointers with > > the same value and different provenance you invoke undefined behavior. > > Yes, but it is tricky because one needs to define > "create a value based on two pointers with..." > > Assuming one does not track provenance through integers, > the only way to create expressions using two pointers > are comparisons, pointer subtraction, and the tertiary > operator. > > The tertiary operator seems unproblematic. For pointer > subtraction, the standard already requires same provenance. > > For comparisons, one could consider making this case UB. > But I fear this could be the source of subtle bugs. > > Then there is the question about what happens if a > programm inspects the representation bytes of a > pointer directly...
At least the pointer is then no longer a register ;) > > That allows the compiler to optimize > > > > int *q, *r; > > if (q == r) > > *r = 1; > > > > into > > > > if (q == r) > > *q = 1; > > > > which it is currently not allowed to do because of that dread one-after-the > > object equality compare, not because of PNVI, but similar cases > > Yes, but as provenance is tracked at compile-time, you could still > do the optimization if you assign the right provenance to the > replaced variable, i.e. you replace 'r' with 'q' but keep the > provenance of 'r'. So while this puts a burden on the compiler > writers, it seems feasible. Or am I missing something? With SSA it's not easy since q before the comparison is the same so it's *q_1 = 2; if (q_1 == r_2) *r_2 = 1; -> *q_1 = 1; and we cannot change the provenance of q_1 since that affects the earlier store. We'd have to somehow attach provenance to all _operations_ where it matters (the dereference in this case). That's a much larger change. > > obviously can be constructed with integers (and make our live difficult > > as we're tracking provenance through integers). > > As in PVNI integers do not have provenance, such an optimization would > always be valid for integers as would all other natural algebraic > optimizations for integers. I consider this a major strength of > the proposal and I kind of hoped that compiler writers would agree. Yes, sure - it avoids this class of problems. PVNI is probably the very simplest approach to fix whatever problem it tries to fix ;) > > Compilers fundamentally work with value-equivalences, the above example > > shows we may not. That's IMHO a defect in the standard. > > I consider provenance to be part of the value. Think about > architectures with descriptors that actually trap if you use > the wrong pointer. This nicely corresponds to a concept > of abstract pointers which not simple the address of a > memory location. > > The problems we have that we can not (cheaply) track provenance > at runtime on modern CPUs and only the address part of the pointer > is available ar runtime. For the standard, this implies > that the rules must work both abstract pointers with provenance > and address-only pointers where information about provenance > is not available. Whenever there is a discrepancy between > these two models, we can either make it UB or use the semantics > of the address-only case. > > The only real problematic case we have with PVNI is comparisons > for one-after-the object pointers with a pointer of different > provenance. The only choices we have is to make this UB or > to make the result well-defined and based on the address. > Both choices have disadvantages. > > If we track provenance through integers, there are many > other difficult problems. The reason is that you then > cannot work with value-equivalences anymore even for > integer expressions which are much more complex. > The amount of additional problems we create here > is the main reason we want to have PVNI and not > track provenance through integers. I understand that. Richard. > Best, > Martin > >