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

[Sanjoy Das via llvm-dev]

Hi Richard,

On April 12, 2017 at 1:24:55 PM, Richard Smith via llvm-dev
(llvm-dev at lists.llvm.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.

That's an interesting idea!  Is it correct to rephrase what you said
as "barrier(x) returns the most recent abstract object inhabiting the
physical address x"?

The two caveats I see are:

 - This won't allow some pointer to integer conversions, since you're
   relying on the IR types to decided when to insert barrier calls.

 - malloc's return value won't be noalias with values that may have
   been produced by other threads.

To elaborate the second point, I mean in

T0:
  a = malloc();
  b = relaxed_load ptr

a has to MayAlias b, because you could have a second thread do:

T1:
  x = malloc()
  free(x)
  t = barrier(x)
  relaxed store t to ptr

since a possible execution is:

  x = malloc()
  free(x)
  a = malloc();
  // Now the newest value inhabiting the physical address x
  // is `a`, because malloc reused the storage
  t = barrier(x) = a
  relaxed store a to ptr
  b = relaxed_load ptr = a

However, I've not thought about how to make T1 happen from a well
defined C/C++ program -- perhaps that's impossible (maybe we can
somehow rule it out in the IR level too).  Secondly, I'm not convinced
that I'll actually be able to show the above problem (if it is one)
manifest as a miscompile.

Another way to look at it is: barrier provides a way for threads to
"guess" abstract heap locations in some cases, which may be
problematic.

-- Sanjoy