[InstCombine] icmp eq/ne (gep inbounds P, Idx..), null -> icmp eq/ne P, null

[reames]

Summary

This generalizes the isGEPKnownNonNull rule from ValueTracking to apply when we do not know if the base is non-null, and thus need to replace one condition with another.

This is an alternative, much more aggressive, approach to the same problem as https://reviews.llvm.org/D64533.

The core notion is that since an inbounds GEP can only form null if the base pointer is null and the offset is zero. However, if the offset is non-zero, the the "inbounds" marker makes the result poison. Thus, we're free to ignore the case where the offset is non-zero. Similarly, there's no case under which a non-null base can result in a null result without generating poison.

Reviewers - I'd appreciate careful review of the reasoning here. It's subtle, and I found several bugs in early versions of this patch. I'm not at all certain there aren't some left.

[reames]

Fix a typo in one of the tests and add clarifying comments.

[jdoerfert]

lib/Transforms/InstCombine/InstCombineCompares.cpp

882

Side note: This should probably be RHS->stripPointerCastsSameRepresentation() as we below argue about nullness of values and address spaces.

915

I drew up the following table to convince myself this is valid given the restrictions checked in the conditional above: inbounds, rhs = zero, null is not valid.

base/offset	zero	not zero
zero	b = zero	poison
not zero	b	not zero or poison

[nikic]

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

[jdoerfert]

In D66608#1641754, @nikic wrote:

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

Here it could cause problems, different other places we actually accumulate the index and decide based on the value, e.g., Offset != 0, which should avoid the problem.
Long story short, I guess we need another check in the if condition here.

[reames]

In D66608#1641754, @nikic wrote:

As mentioned on the previous review, do we need to handle getelementptr inbounds {}, {}* %p, i32 %idx? That is, an inbounds GEP on a zero-sized type, which may be null for a non-zero index. It looks like this case is not handled in the existing code either though, so possibly this construction isn't legal (though I don't see anything to that effect in langref)?

I'm happy to add another bailout. To be honest, the exact semantics of unsized types are not all clear to me.

[reames]

When I went to add the suggested size-0 type bailout, I realized the existing code was correct for this case. I added tests and a comment to show this.

[jdoerfert]

In D66608#1642250, @reames wrote:

When I went to add the suggested size-0 type bailout, I realized the existing code was correct for this case. I added tests and a comment to show this.

The comment is helpful, thanks!

I'm good with this but I'm also tired. Let's wait for others to voice their opinion or at least till I can take another look with fresh eyes.

[nikic]

LGTM

lib/Transforms/InstCombine/InstCombineCompares.cpp

911

I'd suggest changing Index -> Offset in these comments.

test/Transforms/InstCombine/gep-inbounds-null.ll

36

Should be eq?

[xbolva00]

lib/Transforms/InstCombine/InstCombineCompares.cpp

907

Four?

[xbolva00]

lib/Transforms/InstCombine/InstCombineCompares.cpp

900

isa<ConstantPointerNull>(...)

[reames]

I noticed a bug in what got committed, and fixed that in rL369795.

[reames]

A vector extension of this is now posted for review: https://reviews.llvm.org/D66671

lib/Transforms/InstCombine/InstCombineCompares.cpp

900

Left as is for the vector patch now posted.

[mstorsjo]

Thanks for taking the time doing this! Now the compile times for glew are back to more tolerable levels (down to 1 minute in my case, from 6 minutes before), despite the excessive unrolling.

lib/Transforms/InstCombine/InstCombineCompares.cpp

Instruction *InstCombiner::foldGEPICmp(GEPOperator *GEPLHS, Value *RHS,
   // e.g. "&foo[0] <s &foo[1]" can't be folded to "true" because "foo" could be
   // the maximum signed value for the pointer type.
   if (ICmpInst::isSigned(Cond))
     return nullptr;
 
   // Look through bitcasts and addrspacecasts. We do not however want to remove
   // 0 GEPs.
   if (!isa<GetElementPtrInst>(RHS))
     RHS = RHS->stripPointerCasts();
 
   Value *PtrBase = GEPLHS->getOperand(0);
   if (PtrBase == RHS && GEPLHS->isInBounds()) {
     // ((gep Ptr, OFFSET) cmp Ptr)   ---> (OFFSET cmp 0).
     // This transformation (ignoring the base and scales) is valid because we
     // know pointers can't overflow since the gep is inbounds.  See if we can
     // output an optimized form.
     Value *Offset = evaluateGEPOffsetExpression(GEPLHS, *this, DL);
 
     // If not, synthesize the offset the hard way.
     if (!Offset)
       Offset = EmitGEPOffset(GEPLHS);
     return new ICmpInst(ICmpInst::getSignedPredicate(Cond), Offset,
                         Constant::getNullValue(Offset->getType()));
+
+
+  } else if (GEPLHS->isInBounds() && ICmpInst::isEquality(Cond) &&
+             GEPLHS->getType()->isPointerTy() && // TODO: extend to vector geps
+             isa<Constant>(RHS) && cast<Constant>(RHS)->isNullValue() &&
+             !NullPointerIsDefined(I.getFunction(),
+                                   RHS->getType()->getPointerAddressSpace())) {
+    // For most address spaces, an allocation can't be placed at null, but null
+    // itself is treated as a 0 size allocation in the in bounds rules.  Thus,
+    // the only valid inbounds address derived from null, is null itself.
+    // Thus, we have three cases to consider:
+    // 1) Base == nullptr, Index == 0 -> inbounds, null
+    // 2) Base == nullptr, Index != 0 -> poison as the result is out of bounds
+    // 3) Base != nullptr, Index == (-base) -> poison (crossing allocations)
+    // 4) Base != nullptr, Index != (-base) -> nonnull (and possibly poison)
+    //
+    // (Note if we're indexing a type of size 0, that simply collapses into one
+    //  of the buckets above.)
+    //
+    // In general, we're allowed to make values less poison (i.e. remove
+    //   sources of full UB), so in this case, we just select between the two
+    //   non-poison cases (1 and 4 above).
+    return new ICmpInst(Cond, GEPLHS->getPointerOperand(), RHS);
   } else if (GEPOperator *GEPRHS = dyn_cast<GEPOperator>(RHS)) {
     // If the base pointers are different, but the indices are the same, just
     // compare the base pointer.
     if (PtrBase != GEPRHS->getOperand(0)) {
       bool IndicesTheSame = GEPLHS->getNumOperands()==GEPRHS->getNumOperands();
       IndicesTheSame &= GEPLHS->getOperand(0)->getType() ==
                         GEPRHS->getOperand(0)->getType();
       if (IndicesTheSame)

test/Transforms/InstCombine/gep-inbounds-null.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s -instcombine | FileCheck %s
+
+;; Start by showing the results of constant folding (which doesn't use
+;; the poison implied by gep for the nonnull cases).
+
+define i1 @test_ne_constants_null() {
+; CHECK-LABEL: @test_ne_constants_null(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* null, i64 0
+  %cnd = icmp ne i8* %gep, null
+  ret i1 %cnd
+}
+
+define i1 @test_ne_constants_nonnull() {
+; CHECK-LABEL: @test_ne_constants_nonnull(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 true
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* null, i64 1
+  %cnd = icmp ne i8* %gep, null
+  ret i1 %cnd
+}
+
+define i1 @test_eq_constants_null() {
+; CHECK-LABEL: @test_eq_constants_null(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* null, i64 0
+  %cnd = icmp ne i8* %gep, null
+  ret i1 %cnd
+}
+
+define i1 @test_eq_constants_nonnull() {
+; CHECK-LABEL: @test_eq_constants_nonnull(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* null, i64 1
+  %cnd = icmp eq i8* %gep, null
+  ret i1 %cnd
+}
+
+;; Then show the results for non-constants.  These use the inbounds provided
+;; UB fact to ignore the possible overflow cases.
+
+define i1 @test_ne(i8* %base, i64 %idx) {
+; CHECK-LABEL: @test_ne(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CND:%.*]] = icmp ne i8* [[BASE:%.*]], null
+; CHECK-NEXT:    ret i1 [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* %base, i64 %idx
+  %cnd = icmp ne i8* %gep, null
+  ret i1 %cnd
+}
+
+define i1 @test_eq(i8* %base, i64 %idx) {
+; CHECK-LABEL: @test_eq(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CND:%.*]] = icmp eq i8* [[BASE:%.*]], null
+; CHECK-NEXT:    ret i1 [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* %base, i64 %idx
+  %cnd = icmp eq i8* %gep, null
+  ret i1 %cnd
+}
+
+;; TODO: vectors not yet handled
+define <2 x i1> @test_vector_base(<2 x i8*> %base, i64 %idx) {
+; CHECK-LABEL: @test_vector_base(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, <2 x i8*> [[BASE:%.*]], i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[CND:%.*]] = icmp eq <2 x i8*> [[GEP]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds i8, <2 x i8*> %base, i64 %idx
+  %cnd = icmp eq <2 x i8*> %gep, zeroinitializer
+  ret <2 x i1> %cnd
+}
+
+define <2 x i1> @test_vector_index(i8* %base, <2 x i64> %idx) {
+; CHECK-LABEL: @test_vector_index(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8* [[BASE:%.*]], <2 x i64> [[IDX:%.*]]
+; CHECK-NEXT:    [[CND:%.*]] = icmp eq <2 x i8*> [[GEP]], zeroinitializer
+; CHECK-NEXT:    ret <2 x i1> [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* %base, <2 x i64> %idx
+  %cnd = icmp eq <2 x i8*> %gep, zeroinitializer
+  ret <2 x i1> %cnd
+}
+
+;; These two show instsimplify's reasoning getting to the non-zero offsets
+;; before instcombine does.
+
+define i1 @test_eq_pos_idx(i8* %base) {
+; CHECK-LABEL: @test_eq_pos_idx(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* %base, i64 1
+  %cnd = icmp eq i8* %gep, null
+  ret i1 %cnd
+}
+
+define i1 @test_eq_neg_idx(i8* %base) {
+; CHECK-LABEL: @test_eq_neg_idx(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret i1 false
+;
+entry:
+  %gep = getelementptr inbounds i8, i8* %base, i64 -1
+  %cnd = icmp eq i8* %gep, null
+  ret i1 %cnd
+}
+
+;; Show an example with a zero sized type since that's
+;; a cornercase which keeps getting mentioned.  The GEP
+;; produces %base regardless of the value of the index
+;; expression.
+define i1 @test_size0({}* %base, i64 %idx) {
+; CHECK-LABEL: @test_size0(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CND:%.*]] = icmp ne {}* [[BASE:%.*]], null
+; CHECK-NEXT:    ret i1 [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds {}, {}* %base, i64 %idx
+  %cnd = icmp ne {}* %gep, null
+  ret i1 %cnd
+}
+define i1 @test_size0_nonzero_offset({}* %base) {
+; CHECK-LABEL: @test_size0_nonzero_offset(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CND:%.*]] = icmp ne {}* [[BASE:%.*]], null
+; CHECK-NEXT:    ret i1 [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds {}, {}* %base, i64 15
+  %cnd = icmp ne {}* %gep, null
+  ret i1 %cnd
+}
+
+
+;; Finally, some negative tests for sanity checking.
+
+define i1 @neq_noinbounds(i8* %base, i64 %idx) {
+; CHECK-LABEL: @neq_noinbounds(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i8, i8* [[BASE:%.*]], i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[CND:%.*]] = icmp ne i8* [[GEP]], null
+; CHECK-NEXT:    ret i1 [[CND]]
+;
+entry:
+  %gep = getelementptr i8, i8* %base, i64 %idx
+  %cnd = icmp ne i8* %gep, null
+  ret i1 %cnd
+}
+
+define i1 @neg_objectatnull(i8 addrspace(2)* %base, i64 %idx) {
+; CHECK-LABEL: @neg_objectatnull(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i8, i8 addrspace(2)* [[BASE:%.*]], i64 [[IDX:%.*]]
+; CHECK-NEXT:    [[CND:%.*]] = icmp eq i8 addrspace(2)* [[GEP]], null
+; CHECK-NEXT:    ret i1 [[CND]]
+;
+entry:
+  %gep = getelementptr inbounds i8, i8 addrspace(2)* %base, i64 %idx
+  %cnd = icmp eq i8 addrspace(2)* %gep, null
+  ret i1 %cnd
+}