[llvm-dev] Potential issue with noalias @malloc and @realloc

[Richard Smith via llvm-dev]

On 12 April 2017 at 12:19, Daniel Berlin <dberlin at dberlin.org> wrote:

>
>> It seems to me that there are two ways of thinking about this: either the
>> value of a pointer in IR is richer than its bit sequence, in which case
>> replacing p1 with p0 in a block predicated by p0 == p1 is an incorrect
>> transformation if you cannot prove that one pointer was based on the other,
>>
>
> Which would be a non-starter just from the cost of doing so, not to
> mention the allowable optimization you lose :)
>

It may be possible to modify the optimization rather than losing it, such
as by replacing p1 with barrier(p0) rather than with simply p0, where
barrier(p) returns some pointer that is bitwise identical to p but may
carry different ancillary data.

The way I'm thinking of this is that we have a semilattice of virtual
values for each bit-pattern, where it's generally correct to move a value
up in the lattice but not down; the barrier would return the top element of
the lattice. Viewed this way, the problem is that replacing p1 with p0 may
change to a value that is not at or above the original value in the
semilattice. We could preserve more information when doing these value
replacements by inserting an intrinsic representing join(p0, p1) instead of
barrier(p0), but that seems like it would hinder further optimization
rather than help it.

or the value of a pointer in IR is exactly its bit sequence, in which case
>> the code performing the transformation incorrectly updated the IR and a
>> correct transformation would need to somehow remove the noalias from the
>> malloc calls.
>>
>
> Sure, but noalias is just a symptom here. You can make the same thing
> occur in other ways.  It's fundamentally an issue of being able to express
> when the abstract identity of a pointer has changed even when the bit-value
> has not.
>

I agree. Is it reasonable and feasible to require every optimization that
replaces one (pointer) value with another value that is known to be
bitwise-equal but not known to be semantically equivalent to -- somehow --
express that in the resulting IR?

IE there are enough transformation updates that need to occur that we
> probably need to do something different than try to band-aid/patch all the
> places that will have this issue.
>
>
> The C++ object model formally takes the former standpoint; its pointers
>> notionally point to objects, which are abstract entities occupying storage,
>> rather than pointing to the storage itself.
>>
>
>
> Which, i get why they do (in fact i would do the same), but saying the
> abstract objects have an identity outside of the bit values of the pointers
> means that the IR's need to be able to represent identity changes
> separately from value changes (this is what i meant by "add support for
> describing lifetimes that has semantic meaning").
> I'm not aware of any compiler that does this effectively, and it's a
> fairly large semantic change.
>
> They all pretty much hack it and hope they don't break too much shit.
>
> Separately, changing noalias would just band-aid it. You can make the same
> thing occur with TBAA, placement new, or really, any way we have where the
> abstract identity may change but llvm doesn't express it.
>

Right. Even just for the noalias case, allocas would seem have the same
problem as malloc:

int *f() { int n; return &n; };
int g(int *p) {
  int n, v;
  for (int k = 0; k != 1; ++k) {
    n = 20;
    v = n;
    if (false) // obscured, as per Sanjoy's example
      if (&n == p) // noalias but may evaluate to true
        a();
      else
        b();
  }
}
void h() { g(f()); }
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170412/554f4f8a/attachment-0001.html>