For non-null pointer checks, do not descend through out-of-bounds GEPs

[chill]

Summary

In LazyValueInfoImpl::isNonNullAtEndOfBlock we populate a set of
pointers, known to be non-null at the end of a block (e.g. because we
did a load through them). We then infer that any pointer, based on an
element of this set is non-null as well ("based" here meaning a
non-null pointer is the underlying object). This is incorrect, even if
the base pointer was non-null, the value of a GEP, that lacks the
inbounds` attribute, may be null.

This issue appeared as miscompilation of the following test case:

int puts(const char *);
    
typedef struct iter {
  int *val;
} iter_t;
    
static long distance(iter_t first, iter_t last) {
  long r = 0;
  for (; first.val != last.val; first.val++)
    ++r;
  return r;
}
    
int main() {
  int arr[2] = {0};
  iter_t i, j;
  i.val = arr;
  j.val = arr + 1;
  if (distance(i, j) >= 2)
    puts("failed");
  else
    puts("passed");
}

This fixes PR49662.

[lebedev.ri]

alive2 again doesn't agree that non-inbounds GEP is allowed to produce null pointer: https://alive2.llvm.org/ce/z/9wfL5x

[fhahn]

In D99642#2660824, @lebedev.ri wrote:

alive2 again doesn't agree that non-inbounds GEP is allowed to produce null pointer: https://alive2.llvm.org/ce/z/9wfL5x

Interesting, but also surprising, especially because the LangRef explicitly calls out GEPs without inbounds to wrap silently?

llvm/lib/Analysis/ValueTracking.cpp

4275 ↗

(On Diff #334378)

According to https://llvm.org/docs/LangRef.html#pointer-aliasing-rules, inbounds should not impact the underlying object property IIUC. But probably can only rely on that, if the pointer gets actually dereferenced?

llvm/test/Analysis/ValueTracking/unknown-nonnull-gep-out-of-bounds.ll

17

do we need the sub & ptrtoint bits here? We also shouldn't the the transform if the index is an arbitrary value, e.g. an argument, right?

[lebedev.ri]

In D99642#2660849, @fhahn wrote:

In D99642#2660824, @lebedev.ri wrote:

alive2 again doesn't agree that non-inbounds GEP is allowed to produce null pointer: https://alive2.llvm.org/ce/z/9wfL5x

Interesting, but also surprising, especially because the LangRef explicitly calls out GEPs without inbounds to wrap silently?

Yes.
I think it's another example of alive2 trying to invent a memory model that isn't fit for the real world.

[nikic]

I think this should be using Val->stripInBoundsOffsets() rather than modify the getUnderlyingObject() API.

[nlopes]

In D99642#2660864, @lebedev.ri wrote:

In D99642#2660849, @fhahn wrote:

In D99642#2660824, @lebedev.ri wrote:

alive2 again doesn't agree that non-inbounds GEP is allowed to produce null pointer: https://alive2.llvm.org/ce/z/9wfL5x

Interesting, but also surprising, especially because the LangRef explicitly calls out GEPs without inbounds to wrap silently?

Yes.
I think it's another example of alive2 trying to invent a memory model that isn't fit for the real world.

Let me try to explain our reasoning:

• GEP doesn't change the object of a pointer, just the offset within that object. Having this rule enables a lot of optimizations (e.g. you know "for free" that gep %p, %x and gep %q, %y can't alias if %p/%q are the result of e.g. distinct alloca/malloc, even if you know nothing about %x/%y).
• Pointer comparisons need to account for the previous rule plus how we lower pointer comparisons (an integer comparison in assembly). For pointers whose offsets are inbounds, integer comparison == object/offset comparison. If one of the pointers is OOB, then things get complicated because in assembly an OOB pointer may be equal to an inbounds pointer, while in IR we would rather not have that situation to enable optimizations. This lead us to pursue a semantics where the result of a comparison with an OOB ptr is non-deterministic, such that the IR can assume it's always false and assembly can sometimes produce true. The implementation in Alive2 is not complete FYI.

This model has some disadvantages, namely inhibiting some optimizations that LLVM does around null (and only that AFAICT). @aqjune is actively working on this, and testing different models to try to find out a good solution, but I can't say when it'll be ready. Hopefully within a couple of weeks. We are still collecting pointer comparison optimizations done by LLVM ATM (instcombine, SCEV, AA, etc).
This is our list of things that need to be taken into account: https://docs.google.com/document/d/1n2Hqw0bkWK_mUi1xEcK4ruLKE-xxTdQ4426KnWY1nHI/edit?usp=sharing

llvm/lib/Analysis/ValueTracking.cpp

4275 ↗

(On Diff #334378)

Agreed. GEP doesn't change the object even without inbounds.

[fhahn]

In D99642#2660952, @nlopes wrote:

In D99642#2660864, @lebedev.ri wrote:

In D99642#2660849, @fhahn wrote:

In D99642#2660824, @lebedev.ri wrote:

alive2 again doesn't agree that non-inbounds GEP is allowed to produce null pointer: https://alive2.llvm.org/ce/z/9wfL5x

Interesting, but also surprising, especially because the LangRef explicitly calls out GEPs without inbounds to wrap silently?

Yes.
I think it's another example of alive2 trying to invent a memory model that isn't fit for the real world.

Let me try to explain our reasoning:

• GEP doesn't change the object of a pointer, just the offset within that object. Having this rule enables a lot of optimizations (e.g. you know "for free" that gep %p, %x and gep %q, %y can't alias if %p/%q are the result of e.g. distinct alloca/malloc, even if you know nothing about %x/%y).

I think that's fine for AA, which generally looks at pointers that are dereferenced. It seems a bit unfortunate though that we determine that the pointer is based on object but still may not be de-referenceable if the object is though.

• Pointer comparisons need to account for the previous rule plus how we lower pointer comparisons (an integer comparison in assembly). For pointers whose offsets are inbounds, integer comparison == object/offset comparison. If one of the pointers is OOB, then things get complicated because in assembly an OOB pointer may be equal to an inbounds pointer, while in IR we would rather not have that situation to enable optimizations. This lead us to pursue a semantics where the result of a comparison with an OOB ptr is non-deterministic, such that the IR can assume it's always false and assembly can sometimes produce true. The implementation in Alive2 is not complete FYI.

I think we need the capability to express arbitrary pointer arithmetic without the assumption that it cannot point to potentially a different object, e.g. for runtime checks that a pointer does not wrap or go out-of-bounds of a certain object. An answer could of course be that you have to use ptrtoint/inttoptr for that case, but I think in practice this is not what is used today for such cases. (and not what the LangRef suggests, at least as long as the pointer is not dereferenced).

[nlopes]

In D99642#2660961, @fhahn wrote:

In D99642#2660952, @nlopes wrote:

In D99642#2660864, @lebedev.ri wrote:

In D99642#2660849, @fhahn wrote:

In D99642#2660824, @lebedev.ri wrote:

alive2 again doesn't agree that non-inbounds GEP is allowed to produce null pointer: https://alive2.llvm.org/ce/z/9wfL5x

Interesting, but also surprising, especially because the LangRef explicitly calls out GEPs without inbounds to wrap silently?

Yes.
I think it's another example of alive2 trying to invent a memory model that isn't fit for the real world.

Let me try to explain our reasoning:

• GEP doesn't change the object of a pointer, just the offset within that object. Having this rule enables a lot of optimizations (e.g. you know "for free" that gep %p, %x and gep %q, %y can't alias if %p/%q are the result of e.g. distinct alloca/malloc, even if you know nothing about %x/%y).

I think that's fine for AA, which generally looks at pointers that are dereferenced. It seems a bit unfortunate though that we determine that the pointer is based on object but still may not be de-referenceable if the object is though.

That case only happens if some form of UB happens (e.g., gep inbounds that goes OOB, passing a pointer as argument with some incorrect attribute, etc).
The warning in the alias FAQ is because of pointer replacement AFAIR. Just because 2 pointers compare equal, you can't replace one with the other blindly, because one might be dereferenceable and the other not (because one overflowed inbounds, for example).
Pointer comparisons are just tricky.

• Pointer comparisons need to account for the previous rule plus how we lower pointer comparisons (an integer comparison in assembly). For pointers whose offsets are inbounds, integer comparison == object/offset comparison. If one of the pointers is OOB, then things get complicated because in assembly an OOB pointer may be equal to an inbounds pointer, while in IR we would rather not have that situation to enable optimizations. This lead us to pursue a semantics where the result of a comparison with an OOB ptr is non-deterministic, such that the IR can assume it's always false and assembly can sometimes produce true. The implementation in Alive2 is not complete FYI.

I think we need the capability to express arbitrary pointer arithmetic without the assumption that it cannot point to potentially a different object, e.g. for runtime checks that a pointer does not wrap or go out-of-bounds of a certain object. An answer could of course be that you have to use ptrtoint/inttoptr for that case, but I think in practice this is not what is used today for such cases. (and not what the LangRef suggests, at least as long as the pointer is not dereferenced).

That's true. I'm aware of the loop vectorizer that inserts runtime checks to only dispatch to the vectorized loop if some pointers don't alias at runtime. We probably don't want to use ptr2int for this.

[fhahn]

In D99642#2660970, @nlopes wrote:

In D99642#2660961, @fhahn wrote:

In D99642#2660952, @nlopes wrote:

[snip]

Let me try to explain our reasoning:

• GEP doesn't change the object of a pointer, just the offset within that object. Having this rule enables a lot of optimizations (e.g. you know "for free" that gep %p, %x and gep %q, %y can't alias if %p/%q are the result of e.g. distinct alloca/malloc, even if you know nothing about %x/%y).

I think that's fine for AA, which generally looks at pointers that are dereferenced. It seems a bit unfortunate though that we determine that the pointer is based on object but still may not be de-referenceable if the object is though.

That case only happens if some form of UB happens (e.g., gep inbounds that goes OOB, passing a pointer as argument with some incorrect attribute, etc).
The warning in the alias FAQ is because of pointer replacement AFAIR. Just because 2 pointers compare equal, you can't replace one with the other blindly, because one might be dereferenceable and the other not (because one overflowed inbounds, for example).
Pointer comparisons are just tricky.

Agreed! To circle back to the specific case this patch tries to address: Given what we currently have in the LangRef, I think the transformation LLVM does at the moment (eliminate non-null check) is incorrect and should be fixed. WDYT? But having Alive2 disagree here certainly seems unfortunate.

• Pointer comparisons need to account for the previous rule plus how we lower pointer comparisons (an integer comparison in assembly). For pointers whose offsets are inbounds, integer comparison == object/offset comparison. If one of the pointers is OOB, then things get complicated because in assembly an OOB pointer may be equal to an inbounds pointer, while in IR we would rather not have that situation to enable optimizations. This lead us to pursue a semantics where the result of a comparison with an OOB ptr is non-deterministic, such that the IR can assume it's always false and assembly can sometimes produce true. The implementation in Alive2 is not complete FYI.

I think we need the capability to express arbitrary pointer arithmetic without the assumption that it cannot point to potentially a different object, e.g. for runtime checks that a pointer does not wrap or go out-of-bounds of a certain object. An answer could of course be that you have to use ptrtoint/inttoptr for that case, but I think in practice this is not what is used today for such cases. (and not what the LangRef suggests, at least as long as the pointer is not dereferenced).

That's true. I'm aware of the loop vectorizer that inserts runtime checks to only dispatch to the vectorized loop if some pointers don't alias at runtime. We probably don't want to use ptr2int for this.

Yep, there probably are other places as well as IR coming from different frontends.

[chill]

In D99642#2660895, @nikic wrote:

I think this should be using Val->stripInBoundsOffsets() rather than modify the getUnderlyingObject() API.

Thanks, indeed!

llvm/lib/Analysis/ValueTracking.cpp

4275 ↗

(On Diff #334378)

Yeah, it was just my clumsy attempt to reuse the implementation (InBoundsparam was defaulted to false).

[nikic]

LGTM, just some suggestions for the test.

llvm/test/Analysis/ValueTracking/unknown-nonnull-gep-out-of-bounds.ll

1

This test should be in llvm/test/Transform/JumpThreading.

11

I'd pass in an i64* %a here -- the alloca case is less straightforward to me (because you'd have to guess the alloca offset to reach null).

21

The puts calls don't seem relevant, I'd just replace these with ret i32 0 and ret i32 1 or so.

[fhahn]

LGTM, thanks!

@nlopes do you have any more thoughts on the difference between LLVM & Alive2 on this topic?

llvm/test/Analysis/ValueTracking/unknown-nonnull-gep-out-of-bounds.ll

4

This should also not be needed, right? Otherwise we would need to make sure this only runs when the X86 backend is built.

[aqjune]

In D99642#2674663, @fhahn wrote:

LGTM, thanks!

@nlopes do you have any more thoughts on the difference between LLVM & Alive2 on this topic?

Hi, currently the bottleneck is on me due to a few busy things, sorry. I am discussing with Nuno and the conclusion will be shared soon.

[nlopes]

In D99642#2674663, @fhahn wrote:

LGTM, thanks!

@nlopes do you have any more thoughts on the difference between LLVM & Alive2 on this topic?

Not yet, sorry. But it's unfair to block this patch as we don't have an ETA yet.
At most, this patch is making things more conservative, not introducing a miscompilation, and so it's ok.

The icmp in the test case can be true only if we assume that pointer comparison is equal to integer comparison. Which is something that LLVM assumes in a few places. Though it's not a consistent design choice. We are still trying to understand the pros and cons of the different solutions.

[chill]

I did minor test updates, following reviewers' suggestions, don't think another review is warranted, going to commit.

llvm/lib/Analysis/LazyValueInfo.cpp

static void AddNonNullPointersByInstruction(
   }
 }
 
 bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
   if (NullPointerIsDefined(BB->getParent(),
                            Val->getType()->getPointerAddressSpace()))
     return false;
 
-  Val = getUnderlyingObject(Val);
+  Val = Val->stripInBoundsOffsets();
   return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
     NonNullPointerSet NonNullPointers;
     for (Instruction &I : *BB)
       AddNonNullPointersByInstruction(&I, NonNullPointers);
     return NonNullPointers;
   });
 }
 

llvm/test/Analysis/ValueTracking/unknown-nonnull-gep-out-of-bounds.ll

+; RUN: opt -jump-threading -S %s -o - | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@.str = private unnamed_addr constant [5 x i8] c"fail\00", align 1
+@.str.1 = private unnamed_addr constant [5 x i8] c"pass\00", align 1
+
+define dso_local i32 @f(i64 %i) local_unnamed_addr {
+entry:
+  %a = alloca i64, align 8
+  store i64 0, i64* %a, align 8
+  %p = getelementptr i64, i64* %a, i64 %i
+  %c = icmp eq i64* %p, null
+  ; `%a` is non-null at the end of the block, because we store through it.
+  ; However, `%p` is derived from `%a` via a GEP that is not `inbounds`, therefore we cannot judge `%p` is non-null as well
+  ; and must retain the `icmp` instruction.
+  ; CHECK: %c = icmp eq i64* %p, null
+  br i1 %c, label %if.else, label %if.then
+if.then:
+  %call0 = call i32 @puts(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([5 x i8], [5 x i8]* @.str, i64 0, i64 0))
+  br label %if.end
+
+if.else:
+  %call1 = call i32 @puts(i8* noundef nonnull dereferenceable(1) getelementptr inbounds ([5 x i8], [5 x i8]* @.str.1, i64 0, i64 0))
+  br label %if.end
+
+if.end:
+  ret i32 0
+}
+
+declare dso_local i32 @puts(i8*) local_unnamed_addr