[LangRef] Describe why the pointer aliasing rules are currently unsound.

[efriedma]

Summary

I'd like some short description in LangRef we can point to when questions come up, rather than the complicated discussion in https://bugs.llvm.org/show_bug.cgi?id=34548 .

[jdoerfert]

I'm not sure if I'd be any wiser after reading this. I mean, except that I might think "it seems to be complicated".

[efriedma]

I'll try to think about whether there's any way to make this more readable. Maybe some examples would help?

[jdoerfert]

In D88860#2313288, @efriedma wrote:

I'll try to think about whether there's any way to make this more readable. Maybe some examples would help?

Yes. Some text and the one example that shows why int2ptr->ptr2int is not a no-op would suffice in addition to a link to the other resources.

[aqjune]

llvm/docs/LangRef.rst

2558

The contents below talk about loads that produce pointers as well - maybe the title should be more comprehensive?

2571

Let's talk about inttoptr in this paragraph first, and talk about load pointers as separate paragraph(s). I believe inttoptr already has quite a few things to talk about.

I think it is important to mention that, with this inttoptr semantics, inttoptr isn't a scalar operation anymore. It cannot be freely hoisted or sunk across pointer escaping instructions, but it is currently done by LLVM.
Considering that a function with inttoptr is currently tagged as readnone, this will bring a non trivial change in performance, so it will be desirable to keep inttoptr as scalar ops. I suggest making this explicit in the text.

Another possible semantics that would be good to mention here too is to make inttoptr i simply based on i.
The caveat of the semantics is that requires defining based-on relation between non-pointer values as well, which is super tricky; for example, given two integers i and j, if (i == j) use(i) cannot be optimized to if (i == j) use(j) anymore because i and j may be based on different objects. Also, there are big amount of int/float operations (shift, icmp, fptosi, ...) to deal with.

2578

FYI: Alive2 uses this semantics, and it returns poison when a pointer-byte is read as a non-pointer type (and vice versa). The main blocker is a load type canonicalization in InstCombine, which changes load pointer to load i64.

[lebedev.ri]

Thank you for the patch!

[lebedev.ri]

llvm/docs/LangRef.rst

2578

... which i just purged in D88789 / rGe00f189d392dd9bf95f6a98f05f2d341d06cd65c.

[aqjune]

llvm/docs/LangRef.rst

2578

Wow, this is super nice!!

[nlopes]

My meta-comment about this patch is that I'm not sure LangRef is the right place for this content. I see LangRef as the stuff that is set in stone, not necessarily for ongoing discussions.
However, since LangRef doesn't get these bits right, it might be ok to have a warning section about stuff that is disputed/under discussion so that readers know that part is not set in stone.

llvm/docs/LangRef.rst

2586

my understanding is that for C we need to allow a pointer to be at the end of the object (not past, just at the end; you can't dereference it still). This is, for example, because of loops that increment pointers and check them against the end ptr.

That end pointer can have the same underlying machine value as the beginning of another object, thus making inttoptr complicated.
If the allocator guaranteed that this case didn't happen, it would make things easier, but for small objects that's probably a big penalty. And LLVM can't assume that would hold for custom allocators.

We support this semantics of control-flow contributing to the aliasing of an inttoptr result. To fold inttoptr(ptrtoint(ptr)) -> ptr one needs to prove that ptr is dereferenceable though.

[efriedma]

My meta-comment about this patch is that I'm not sure LangRef is the right place for this content. I see LangRef as the stuff that is set in stone, not necessarily for ongoing discussions. However, since LangRef doesn't get these bits right, it might be ok to have a warning section about stuff that is disputed/under discussion so that readers know that part is not set in stone.

Given the feedback, I'm going to cut the bits describing the potential solutions, to try to keep it more readable.

[efriedma]

llvm/docs/LangRef.rst

2586

my understanding is that for C we need to allow a pointer to be at the end of the object

Well, for pointers we know are dereferenced, we could mark up the GEPs more aggressively. But yes, that's where this sort of model breaks down.

To fold inttoptr(ptrtoint(ptr)) -> ptr one needs to prove that ptr is dereferenceable though.

I guess if you have load(inttoptr(ptrtoint(ptr))), you can optimize that to load(ptr) if ptr is dereferenceable: the load would be UB if it wasn't equivalent. I don't think it helps more generally, though.

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/docs/LangRef.rst

 alignment of the store.
 
 Consequently, type-based alias analysis, aka TBAA, aka
 ``-fstrict-aliasing``, is not applicable to general unadorned LLVM IR.
 :ref:`Metadata <metadata>` may be used to encode additional information
 which specialized optimization passes may use to implement type-based
 alias analysis.
 
+The inttoptr hole
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+The pointer aliasing rules currently don't have a consistent interpretation in
+LLVM. The issue is the semantics of ``inttoptr``, and loads that produce a
+pointer.  It's not clear what it means for a pointer value to "contribute".
+
+Suppose the strictest possible interpretation: all computations and control
+flow are relevant to whether a pointer value "contributes". Then if an integer
+is converted to a pointer, it depends on all pointers which have escaped at
+that point.  This is true even if we can prove the pointer value is equal to
+the address of some specific object. This makes a bunch of transforms LLVM
+currently performs illegal. For example, an inttoptr of a ptrtoint can't be
+simplified to the operand of the ptrtoint. Or if you have a store of a
+pointer, followed by a load of the same pointer, it can't be simplified to
+the operand of the store.
+
+There are various ways this could be relaxed. The most likely solution is some
+sort of invisible provenance indicator. At its core, this says that if a store
+writes a pointer value, then a load reads that pointer value, the load is only
+based on the value operand of the store that stored the value, not any other
+escaped pointer. This description leaves a lot of open questions regarding the
+interaction between pointer operations and non-pointer operations.
+
+Another possibility is that we could drop the notion of "based-on", and come
+up with some other approach for alias analysis focused around "inbounds".
+Suppose we had a stricter version of "inbounds" that didn't allow computing
+the address of the byte one past the end of an object.  Then we end up with a
+pretty simple model: pointers themselves are just integers, but GEPs still
+preserve something roughly equivalent to "based on".  The problem here is
+the current "inbounds" allows pointers one byte past the end of an object; that
+pointer could point to another object, so analyzing that is a lot more
+complicated.
+
+https://bugs.llvm.org/show_bug.cgi?id=34548 discusses various related issues
+in LLVM. http://www.open-std.org/jtc1/sc22/wg14/www/docs/n2311.pdf goes over
+related issues in the C standard.
+
 .. _volatile:
 
 Volatile Memory Accesses
 ------------------------
 
 Certain memory accesses, such as :ref:`load <i_load>`'s,
 :ref:`store <i_store>`'s, and :ref:`llvm.memcpy <int_memcpy>`'s may be
 marked ``volatile``. The optimizers must not change the number of