[LangRef] Clarify GEP inbounds wrapping semantics

[nikic]

Summary

The current LangRef wording for GEP inbounds is not very clear in what it implies in terms of wrapping restrictions for the underlying additions and multiplications. This updates LangRef with my understanding of how this is currently being interpreted in practice.

For example, there's this SCEV comment: https://github.com/llvm/llvm-project/blob/7f34aca083b528db1d880b406f1a1953eeb6aa95/llvm/lib/Analysis/ScalarEvolution.cpp#L5061-L5066

Another indication is the fact that clang emits pointer comparisons using unsigned predicates, so we must be assuming that allocated objects cannot wrap the unsigned address space. (For address space 0 this is automatically given because there may be no allocated object containing the null pointer.)

However, I do wonder if we could get away with saying that no allocated object may wrap the signed address space, in which case inbounds would just map cleanly to nsw, which would both allow more optimization and be easier to reason about. We have at least one important target (x86-64) where this is a given by hardware constraints. But I don't know if we can get away with making that a general limitation. (I don't think it's a good idea to make core GEP semantics target-dependent.)

[hiraditya]

LGTM, an example of a gep with inbounds wouldbe nice. there are some test cases like: CodeGen/2009-02-13-zerosize-union-field.c, CodeGen/2010-07-14-ref-off-end.c etc from where we can take a reduced example for the doc.

[aqjune]

However, I do wonder if we could get away with saying that no allocated object may wrap the signed address space, in which case inbounds would just map cleanly to nsw, which would both allow more optimization and be easier to reason about. We have at least one important target (x86-64) where this is a given by hardware constraints. But I don't know if we can get away with making that a general limitation. (I don't think it's a good idea to make core GEP semantics target-dependent.)

It seems sbrk() assume an address space is unsigned:
https://code.woboq.org/userspace/glibc/misc/sbrk.c.html

Since it is frequently used to implement malloc(), I guess malloc can in general return an allocation whose address is something like [0x7fffffff, 0x80000001]. Does this make sense?

[nlopes]

LGTM modulo the two comments. Thanks for writing this down!

llvm/docs/LangRef.rst

9798

I think the "one byte past" can be misleading. A pointer can point to the end of an object, or as the C++ standard puts it, it may point to a hypothetical next element n if the object has n elements.
http://eel.is/c++draft/basic.compound#3.4

9808

one more case is that offsets must fit (signed-wise) in the address space's size. So a GEP with 64 bits offsets on a 32-bit address space is OK as long as those offsets fit in 32 bits.

[nikic]

• Try to use clearer wording for the address to the end of the object.
• Mention that the truncation to the DL index type must preserve the signed value.
• Merge the two bullet lists. I think the nsw requirement for the offset addition needs to be listed as an explicit requirement, it's not a direct consequence of the other rules.
• Mention that these rules assume that no allocated object wraps the unsigned address space, and no object is larger than half the address space.

[nikic]

Clarify that the nsw offset wrapping restrictions are relative to the pointer index type (which may have smaller size than the pointer).

[nhaehnle]

This makes sense to me.

However, I do wonder if we could get away with saying that no allocated object may wrap the signed address space, in which case inbounds would just map cleanly to nsw, which would both allow more optimization and be easier to reason about.

Unfortunately, that wouldn't work for us. We have 32-bit address spaces that are treated as the unsigned range [0, 0xffffffff], and there's no limitation as to where objects can appear in that range.

llvm/docs/LangRef.rst

9811–9812

As a second corollary, the addition wraps in an unsigned sense if and only if the added offset is negative?

[nikic]

In D90708#2375628, @nhaehnle wrote:

This makes sense to me.

However, I do wonder if we could get away with saying that no allocated object may wrap the signed address space, in which case inbounds would just map cleanly to nsw, which would both allow more optimization and be easier to reason about.

Unfortunately, that wouldn't work for us. We have 32-bit address spaces that are treated as the unsigned range [0, 0xffffffff], and there's no limitation as to where objects can appear in that range.

Yeah, doesn't look like we can require this in the general case. I also checked that malloc does indeed return allocations that cross the sign boundary for -m32 binaries, using the following code:

#include <stdio.h>
#include <stdlib.h>
#define BLOCK_SIZE (128 * 1024 * 1024)
int main() {
    while (1) {
        char *ptr = malloc(BLOCK_SIZE);
        if (!ptr) {
            printf("OOM!\n");
            return 0;
        }
        printf("%p - %p\n", ptr, ptr + BLOCK_SIZE);
    }
}

So if we wanted to make use of the x86-64 address space layout, we'd have to do that based on a datalayout property or so, and that's out of scope of this change (and likely generally not worthwhile).

llvm/docs/LangRef.rst

9811–9812

I agree that this statement is true, but is it also useful for something? Not sure in what way optimizations would make use of the fact that the calculation always wraps.

[jrtc27]

In D90708#2372698, @aqjune wrote:

It seems sbrk() assume an address space is unsigned:
https://code.woboq.org/userspace/glibc/misc/sbrk.c.html

Since it is frequently used to implement malloc(), I guess malloc can in general return an allocation whose address is something like [0x7fffffff, 0x80000001]. Does this make sense?

It's also an ancient deprecated interface, rather dodgy in terms of pointer provenance (sbrk returns the _old_ program break), and does not exist on some modern OS ports (notably, FreeBSD/arm64 and FreeBSD/riscv do not provide it). Whilst some best-of-1990s allocators that make use of it are still rather more pervasive than they should be, it really needs to be consigned to the history books...

[aqjune]

In D90708#2377237, @jrtc27 wrote:

In D90708#2372698, @aqjune wrote:

It seems sbrk() assume an address space is unsigned:
https://code.woboq.org/userspace/glibc/misc/sbrk.c.html

Since it is frequently used to implement malloc(), I guess malloc can in general return an allocation whose address is something like [0x7fffffff, 0x80000001]. Does this make sense?

It's also an ancient deprecated interface, rather dodgy in terms of pointer provenance (sbrk returns the _old_ program break), and does not exist on some modern OS ports (notably, FreeBSD/arm64 and FreeBSD/riscv do not provide it). Whilst some best-of-1990s allocators that make use of it are still rather more pervasive than they should be, it really needs to be consigned to the history books...

Wow, thanks for the info! :) It seems the man page (https://www.freebsd.org/cgi/man.cgi?query=sbrk&sektion=2 ) is saying the same thing as well.

[nikic]

Any further feedback here?

[jrtc27]

llvm/docs/LangRef.rst

9797

Minor tweak to not assume that pointers are integers

[nikic]

Apply suggestion by jrtc27.

[aqjune]

I like the change, so LGTM

[aqjune]

(..but one more LGTM might be better to make things sure)

[nlopes]

llvm/docs/LangRef.rst

9799

I still don't like the current writing. I would need to see some evidence from language standards that they require pointers past the end of objects.

9802

than than

9806

It's a bit stronger than that. The addition of each offset to the preceding pointer should not overflow. You can't do e.g.:
gep inbounds %p, -1, 1

because %p-1 is OOB, even though the result is in bounds (because %p must be in bounds).

[jrtc27]

llvm/docs/LangRef.rst

9799

If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

https://port70.net/~nsz/c/c11/n1570.html#6.5.6p8

9806

It's more nuanced than that, no? %p could be a pointer part-way through (or one past the end of) an object, in which case %p-1 would still be in bounds?

[nikic]

llvm/docs/LangRef.rst

9799

What would be a better wording? "One past the end" is a term of art, and as such should be well understood: https://www.google.com/search?q=one+past+the+end

9806

This is specified in the next bullet point (successive addition to the base pointer must remain in bounds of the allocated object).

[nlopes]

llvm/docs/LangRef.rst

9799

Thanks for the reference. Though that paragraph doesn't say that a pointer 1 byte past the end is valid.
It says that the following is valid:
int x[n]
q = p+(n-1); points to the last element
q = p+1; points to one element past the last

Doesn't say that (char*)(p+n)+1 is valid, which is what it means for a pointer 1 byte past the end to be valid.

So AFAICT, both the C & C++ standards agree that p+n is the max one needs to support.

My suggestion is simply to remove the part in parenthesis "(which is one byte past the last byte contained in the object)". Or replace it with similar wording of the C++ standard (corresponds to a hypothetical next element or something like that).

9806

Ok, right. Then this is more of a corollary of the point below. Sounds correct at least. I'm happy to keep it.

[jrtc27]

llvm/docs/LangRef.rst

9799

Assuming

q = p+1; /* points to one element past the last */

was meant to be

q = p+n; /* points to one element past the last */

It depends whether you define end as being p + n or (char *)(p + n) - 1. C/C++ use the latter (as do people when they talk about "one past the end" pointers), whereas you seem to be using the former. To C/C++, (char*)(p+n)+1 would be OOB as it's one byte after one past the last element.

So I think we are on the same page in terms of semantics, we just have different ideas of what certain terms mean.

[nikic]

• Remove parenthetical about end.
• Fix "than than" typo.

[nikic]

llvm/docs/LangRef.rst

9799

Okay, I've dropped the part in the parentheses.

[nlopes]

LGTM!
Thanks a lot for working on this!

llvm/docs/LangRef.rst

define i32* @foo(%struct.ST* %s) {
       %t2 = getelementptr %struct.ST, %struct.ST* %t1, i32 0, i32 2                ; yields %struct.RT*:%t2
       %t3 = getelementptr %struct.RT, %struct.RT* %t2, i32 0, i32 1                ; yields [10 x [20 x i32]]*:%t3
       %t4 = getelementptr [10 x [20 x i32]], [10 x [20 x i32]]* %t3, i32 0, i32 5  ; yields [20 x i32]*:%t4
       %t5 = getelementptr [20 x i32], [20 x i32]* %t4, i32 0, i32 13               ; yields i32*:%t5
       ret i32* %t5
     }
 
 If the ``inbounds`` keyword is present, the result value of the
-``getelementptr`` is a :ref:`poison value <poisonvalues>` if the base
-pointer is not an *in bounds* address of an allocated object, or if any
-of the addresses that would be formed by successive addition of the
-offsets implied by the indices to the base address with infinitely
-precise signed arithmetic are not an *in bounds* address of that
-allocated object. The *in bounds* addresses for an allocated object are
-all the addresses that point into the object, plus the address one byte
-past the end. The only *in bounds* address for a null pointer in the
-default address-space is the null pointer itself. In cases where the
-base is a vector of pointers the ``inbounds`` keyword applies to each
-of the computations element-wise.
+``getelementptr`` is a :ref:`poison value <poisonvalues>` if one of the
+following rules is violated:
+
+*  The base pointer has an *in bounds* address of an allocated object, which
+   means that it points into an allocated object, or to its end. The only
+   *in bounds* address for a null pointer in the default address-space is the
+   null pointer itself.
+*  If the type of an index is larger than the pointer index type, the
+   truncation to the pointer index type preserves the signed value.
+*  The multiplication of an index by the type size does not wrap the pointer
+   index type in a signed sense (``nsw``).
+*  The successive addition of offsets (without adding the base address) does
+   not wrap the pointer index type in a signed sense (``nsw``).
+*  The successive addition of the current address, interpreted as an unsigned
+   number, and an offset, interpreted as a signed number, does not wrap the
+   unsigned address space and remains *in bounds* of the allocated object.
+   As a corollary, if the added offset is non-negative, the addition does not
+   wrap in an unsigned sense (``nuw``).
+*  In cases where the base is a vector of pointers, the ``inbounds`` keyword
+   applies to each of the computations element-wise.
+
+These rules are based on the assumption that no allocated object may cross
+the unsigned address space boundary, and no allocated object may be larger
+than half the pointer index type space.
 
 If the ``inbounds`` keyword is not present, the offsets are added to the
 base address with silently-wrapping two's complement arithmetic. If the
 offsets have a different width from the pointer, they are sign-extended
 or truncated to the width of the pointer. The result value of the
 ``getelementptr`` may be outside the object pointed to by the base
 pointer. The result value may not necessarily be used to access memory
 though, even if it happens to point into allocated storage. See the