[LangRef] Always allow getelementptr inbounds with zero offset

[nikic]

Summary

Currently, our GEP specification has a special case that makes gep inbounds (null, 0) legal. This patch proposes to expand this special case to all gep inbounds (ptr, 0), where ptr is no longer requires to point to an allocated object.

This was previously discussed in some detail at https://discourse.llvm.org/t/question-about-getelementptr-inbounds-with-offset-0/62533.

The motivation for this change is twofold:

• Rust relies on getelementptr inbounds with zero offset to be legal for arbitrary pointers to support zero-sized types. The current rules are unclear on whether this is legal or not (saying that there is a zero-size "allocated object" at every address may be consistent with our current rules, but more clarity is desired here).
• The current semantics require us to drop the inbounds flag when materializing zero-index GEPs, which is done by some InstCombine transforms. Preserving the inbounds flag can substantially improve optimization quality in some cases, as illustrated in D154055.

As far as I know, the only analysis/transforms affected by this semantics change are:

• A special-case for comparisons with null in CaptureTracking, which is fixed by D154054. As far as I can tell, that special case is not particularly valuable and should be recovered by other transforms.
• Folding gep inbounds undef, idx to poison. We now need to fold to undef instead (D154215).

[RalfJung]

For Rust this would be a great change, since we'd like to allow offset-by-0 for arbitrary pointers in the language and are currently blocked on how to best lower such an operation to LLVM. :)

llvm/docs/LangRef.rst

10931

This might be a good opportunity to clarify that the allocated objects does not have to be live.

10946

Are negative indices supported? If yes, is it possible that multiple indices "cancel" to leave the total effective offset as 0 despite there being non-0 indices?

[nikic]

llvm/docs/LangRef.rst

10931

That seems orthogonal to the change here, so I'd rather not include it. Properly specifying the notion of a dead allocated object seems pretty tricky.

10946

Multiple indices are not allowed to cancel. The "any non-zero" and "all-zero" wordings here are intentional. This is consistent with usual inbounds semantics, which also do not allow "temporarily" going out of bounds.

(We do have optimizations that depend on this.)

[RalfJung]

llvm/docs/LangRef.rst

10931

Even without properly specifying it, just mentioning this seems useful -- when reading the docs I never even considered that a dead pointer might be considered inbounds of anything.

But yeah it is orthogonal. I might make a PR for that (probably only once I can do that on github so that it's not so painful^^).

10946

Oh, that is very surprising and not clear from the docs. The docs talk about adding the offsets to each other without the base address (3rd bullet) which strongly indicates that first offsets are added up, and then the final accumulated offset is added to the base, and then the result has to be inbounds. If that's not the semantics I think it needs clarification.

[nikic]

llvm/docs/LangRef.rst

10946

This is covered by the 4th bullet point:

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.

[RalfJung]

llvm/docs/LangRef.rst

10946

That's not clear at all IMO. It says "an offset", singular -- so I figured just a single offset is added to the current address, namely the sum that was computed in step 3.

This is why we need more than English prose in such a spec...

[nlopes]

I've implemented this semantics in Alive2 and run it over LLVM's test suite.
There are only 2 regressions, and they seem ok:

+  LLVM :: Transforms/InstCombine/gep-inbounds-null.ll
define i1 @test_eq(ptr %base, i64 %idx) {
  %gep = gep inbounds ptr %base, 1 x i64 %idx
  %cnd = icmp eq ptr %gep, null
  ret i1 %cnd
}
=>
define i1 @test_eq(ptr %base, i64 %idx) {
  %cnd = icmp eq ptr %base, null                ; wrong since %base can be OOB
  ret i1 %cnd
}


+  LLVM :: Transforms/InstSimplify/gep.ll
define ptr @undef_inbounds_var_idx(i64 %idx) {
  %el = gep inbounds ptr undef, 8 x i64 %idx
  ret ptr %el
}
=>
define ptr @undef_inbounds_var_idx(i64 %idx) {
  ret ptr poison                                 ; only ok if %idx != 0
}

Therefore, if this change helps Rust, let's do it. It's backwards compatible since it's removing some UB behavior from before.

[nikic]

In D154051#4463038, @nlopes wrote:

I've implemented this semantics in Alive2 and run it over LLVM's test suite.

Thanks for testing!

There are only 2 regressions, and they seem ok:

+  LLVM :: Transforms/InstCombine/gep-inbounds-null.ll
define i1 @test_eq(ptr %base, i64 %idx) {
  %gep = gep inbounds ptr %base, 1 x i64 %idx
  %cnd = icmp eq ptr %gep, null
  ret i1 %cnd
}
=>
define i1 @test_eq(ptr %base, i64 %idx) {
  %cnd = icmp eq ptr %base, null                ; wrong since %base can be OOB
  ret i1 %cnd
}

Hm, I don't think I understand why that transform is not valid anymore. Going through the different cases here:

• %base == null, %idx == 0 -> %cnd == true.
• %base == null, %idx != 0 -> %cnd == poison.
• %base != null, %idx == 0 -> %cnd == false (by assumption).
• %base != null, %idx != 0 -> %cnd == false. This is because it can only be true for %idx = -ptrtoint(%base), which cannot be inbounds in the default address space, as no allocated object can start at address zero.

So I think reducing this to %base == null remains correct?

+  LLVM :: Transforms/InstSimplify/gep.ll
define ptr @undef_inbounds_var_idx(i64 %idx) {
  %el = gep inbounds ptr undef, 8 x i64 %idx
  ret ptr %el
}
=>
define ptr @undef_inbounds_var_idx(i64 %idx) {
  ret ptr poison                                 ; only ok if %idx != 0
}

Agree that this is no longer correct, we need to return undef instead. That's okay as we can still return poison for a poison base.

[nlopes]

In D154051#4463060, @nikic wrote:

In D154051#4463038, @nlopes wrote:

+  LLVM :: Transforms/InstCombine/gep-inbounds-null.ll
define i1 @test_eq(ptr %base, i64 %idx) {
  %gep = gep inbounds ptr %base, 1 x i64 %idx
  %cnd = icmp eq ptr %gep, null
  ret i1 %cnd
}
=>
define i1 @test_eq(ptr %base, i64 %idx) {
  %cnd = icmp eq ptr %base, null                ; wrong since %base can be OOB
  ret i1 %cnd
}

Hm, I don't think I understand why that transform is not valid anymore. Going through the different cases here:

• %base == null, %idx == 0 -> %cnd == true.
• %base == null, %idx != 0 -> %cnd == poison.
• %base != null, %idx == 0 -> %cnd == false (by assumption).
• %base != null, %idx != 0 -> %cnd == false. This is because it can only be true for %idx = -ptrtoint(%base), which cannot be inbounds in the default address space, as no allocated object can start at address zero.

So I think reducing this to %base == null remains correct?

You're right. I overlooked this. Alive2 was doing an internal optimization that is no longer valid with this semantics.
So we're down to 1 easy regression then.

I'll run Alive2 over a few larger programs just in case, but I think we can move on. I'll report back if it finds more regressions.

llvm/docs/LangRef.rst

define ptr @foo(ptr %s) {
       %t1 = getelementptr %struct.ST, ptr %s, i32 1
       %t2 = getelementptr %struct.ST, ptr %t1, i32 0, i32 2
       %t3 = getelementptr %struct.RT, ptr %t2, i32 0, i32 1
       %t4 = getelementptr [10 x [20 x i32]], ptr %t3, i32 0, i32 5
       %t5 = getelementptr [20 x i32], ptr %t4, i32 0, i32 13
       ret ptr %t5
     }
 
-If the ``inbounds`` keyword is present, the result value of the
-``getelementptr`` is a :ref:`poison value <poisonvalues>` if one of the
-following rules is violated:
+If the ``inbounds`` keyword is present, the result value of a
+``getelementptr`` with any non-zero indices 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.
+   means that it points into an allocated object, or to its end.
 *  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.
 
+Note that ``getelementptr`` with all-zero indices is always considered to be
+``inbounds``, even if the base pointer does not point to an allocated object.
+As a corollary, the only pointer in bounds of the null pointer in the default
+address space is the null pointer itself.
+
 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's index type, they are
 sign-extended or truncated to the width of the pointer's index type. The result