[ValueTracking] Mark GEP operand as nonnull if the result was loaded or stored

[danlark]

Summary

Nonnull inbounds GEP cannot be obtained from null pointer. So I decided to mark the GEP operand as non null if this happens. This saves around 0.05%-0.1% of the binary size at Google and 0.06% of binary size of clang. I don't have commit rights. Danila Kutenin. [e-mail]

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

2134

Doesn't this cause endless recursion back into isKnownNonNullFromDominatingCondition()
for the very same value we've started with?
(and we happen to not deadloop just because of depth cutoff)

[danlark]

Add gep after check test to test DominatorTree

[danlark]

llvm/lib/Analysis/ValueTracking.cpp

2134

isKnownNonZero has Depth cutoff before isKnownNonNullFromDominatingCondition

https://github.com/llvm/llvm-project/blob/e38ccb729b205b076356684e055efb7dfc673963/llvm/lib/Analysis/ValueTracking.cpp#L2304-L2336

[lebedev.ri]

llvm/lib/Analysis/ValueTracking.cpp

2134

Sure, but before that cutoff triggers, won't we waste time mutually recursing with no progress?

[danlark]

llvm/lib/Analysis/ValueTracking.cpp

2134

Not to compute the same values we may not go recursively and only look for constants, I believe this is the most popular case

[danlark]

Don't compute isKnownNonZero for operand

[danlark]

llvm/lib/Analysis/ValueTracking.cpp

2134

Done.

[danlark]

Fix clang-tidy warning

[nikic]

I'm somewhat concerned about the general direction here. This looks through a GEP, but what about bitcasts? What about a bitcast of a GEP? A GEP of a bitcast? A longer chain of GEPs and bitcasts? We can't reasonably walk the whole use graph and this is really pushing the bounds of what it appropriate for a ValueTracking helper.

We have a more principled version of this optimization in LVI, which scans whole blocks for pointer dereferences and records their underlying objects, thus handling this in full generality. The only caveat is that LVI only uses this information to optimize the terminator instruction, because it does not store where exactly inside the block the first dereference occurs. If the motivation here is handling of non-terminator comparisons, then that might be a better avenue to explore?

llvm/lib/Analysis/ValueTracking.cpp

2132

How can a GEP not have pointer type?

2134

I don't get it. What is this isGEPKnownNonNull() check here for? Why do the GEP indices matter at all?

2135

This effectively raises the maximum uses walked from DomConditionsMaxUses to DomConditionsMaxUses^2, because you can walk that many GEPs, and then that many uses of each GEP.

Shouldn't this be counting towards the main NumUsesExplored, rather than a separate limit?

[danlark]

Remove unnecessary checks

[danlark]

Fix compilation issues

[danlark]

In D102550#2761412, @nikic wrote:

I'm somewhat concerned about the general direction here. This looks through a GEP, but what about bitcasts? What about a bitcast of a GEP? A GEP of a bitcast? A longer chain of GEPs and bitcasts? We can't reasonably walk the whole use graph and this is really pushing the bounds of what it appropriate for a ValueTracking helper.

We have a more principled version of this optimization in LVI, which scans whole blocks for pointer dereferences and records their underlying objects, thus handling this in full generality. The only caveat is that LVI only uses this information to optimize the terminator instruction, because it does not store where exactly inside the block the first dereference occurs. If the motivation here is handling of non-terminator comparisons, then that might be a better avenue to explore?

I was looking at LVI and haven't come up with anything meaningful, probably because I am not familiar with that part.

I was following more a statistical approach at Google -- what the users do more with pointers, it turned out that dereferencing + check and pointer arithmetic+deref+check are the most common ones by far. That said, I found that deref+check is already optimized in ValueTracking and I decided to do the same with pointer arithmetic, however, yes, it starts to be a little bloaty. Also GCC does these kind of things with C/C++ code consistently and llvm is far behind in tracking the (non)nullness of pointers. 0.1% in big binaries looks like a big low hanging win.

Currently I don't want to go to LVI if I have a choice.

[lebedev.ri]

I basically agree with @nikic here.
There is a huge number of low-hanging fruit like this,
but the approach just doesn't seem viable to me.

I would instead like to see the Attributor finally enabled,
there such things would be much more straight-forward.

Sorry for a very not helpful feedback.

[danlark]

In D102550#2761483, @lebedev.ri wrote:

I basically agree with @nikic here.
There is a huge number of low-hanging fruit like this,
but the approach just doesn't seem viable to me.

I would instead like to see the Attributor finally enabled,
there such things would be much more straight-forward.

Sorry for a very not helpful feedback.

Okay, thanks. Probably I am abandoning this then.

llvm/lib/Analysis/ValueTracking.cpp

 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/ConstantRange.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/GlobalAlias.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/GlobalVariable.h"
for (auto *U : V->users()) {
     if (V == getLoadStorePointerOperand(U)) {
       const Instruction *I = cast<Instruction>(U);
       if (!NullPointerIsDefined(I->getFunction(),
                                 V->getType()->getPointerAddressSpace()) &&
           DT->dominates(I, CtxI))
         return true;
     }
 
+    if (const GEPOperator *GEP = dyn_cast<GEPOperator>(U)) {
+      const Instruction *I = cast<Instruction>(U);
+      if (DT->dominates(I, CtxI) && V == GEP->getPointerOperand() &&
+          GEP->isInBounds()) {
+        for (const auto *UGEP : GEP->users()) {
+          if (NumUsesExplored >= DomConditionsMaxUses)
+            break;
+          NumUsesExplored++;
+          if (U == getLoadStorePointerOperand(UGEP)) {
+            const Instruction *IGEP = cast<Instruction>(UGEP);
+            if (!NullPointerIsDefined(IGEP->getFunction(),
+                                      U->getType()->getPointerAddressSpace()) &&
+                DT->dominates(IGEP, CtxI)) {
+              return true;
+            }
+          }
+        }
+      }
+    }
+
     // Consider only compare instructions uniquely controlling a branch
     Value *RHS;
     CmpInst::Predicate Pred;
     if (!match(U, m_c_ICmp(Pred, m_Specific(V), m_Value(RHS))))
       continue;
 
     bool NonNullIfTrue;
     if (cmpExcludesZero(Pred, RHS))

llvm/test/Analysis/ValueTracking/known-nonnull-at.ll

 if.end:
   store i8 7, i8* %1
   br label %return
 
 return:
   %retval.0 = phi i8* [ %1, %if.end ], [ null, %entry ]
   ret i8* %retval.0
 }
+
+
+define i32 @test_null_after_gep_load(i32* %0) {
+; CHECK-LABEL: @test_null_after_gep_load(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %2 = getelementptr inbounds i32, i32* %0, i64 1
+  %3 = load i32, i32* %2, align 4
+  %4 = icmp eq i32* %0, null
+  %5 = select i1 %4, i32 42, i32 %3
+  ret i32 %5
+}
+
+define i32 @test_null_after_gep_store(i32* %0) {
+; CHECK-LABEL: @test_null_after_gep_store(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 1
+; CHECK-NEXT:    store i32 42, i32* [[TMP2]], align 4
+; CHECK-NEXT:    ret i32 42
+;
+  %2 = getelementptr inbounds i32, i32* %0, i64 1
+  store i32 42, i32* %2, align 4
+  %3 = icmp eq i32* %0, null
+  %4 = select i1 %3, i32 4242, i32 42
+  ret i32 %4
+}
+
+define i32 @test_null_after_gep_load_addrspace(i32 addrspace(1)* %0) {
+; CHECK-LABEL: @test_null_after_gep_load_addrspace(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32 addrspace(1)* [[TMP0:%.*]], i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32 addrspace(1)* [[TMP2]], align 4
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 addrspace(1)* [[TMP0]], null
+; CHECK-NEXT:    [[TMP5:%.*]] = select i1 [[TMP4]], i32 42, i32 [[TMP3]]
+; CHECK-NEXT:    ret i32 [[TMP5]]
+;
+  %2 = getelementptr inbounds i32, i32 addrspace(1)* %0, i64 1
+  %3 = load i32, i32 addrspace(1)* %2, align 4
+  %4 = icmp eq i32 addrspace(1)* %0, null
+  %5 = select i1 %4, i32 42, i32 %3
+  ret i32 %5
+}
+
+define i32 @test_null_after_gep_store_addrspace(i32 addrspace(1)* %0) {
+; CHECK-LABEL: @test_null_after_gep_store_addrspace(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32 addrspace(1)* [[TMP0:%.*]], i64 1
+; CHECK-NEXT:    store i32 42, i32 addrspace(1)* [[TMP2]], align 4
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 addrspace(1)* [[TMP0]], null
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i32 4242, i32 42
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %2 = getelementptr inbounds i32, i32 addrspace(1)* %0, i64 1
+  store i32 42, i32 addrspace(1)* %2, align 4
+  %3 = icmp eq i32 addrspace(1)* %0, null
+  %4 = select i1 %3, i32 4242, i32 42
+  ret i32 %4
+}
+
+define i32* @test_null_gep_without_load(i32* %0) {
+; CHECK-LABEL: @test_null_gep_without_load(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 1
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32* [[TMP0]], null
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i32* null, i32* [[TMP2]]
+; CHECK-NEXT:    ret i32* [[TMP4]]
+;
+  %2 = getelementptr inbounds i32, i32* %0, i64 1
+  %3 = icmp eq i32* %0, null
+  %4 = select i1 %3, i32* null, i32* %2
+  ret i32* %4
+}
+
+
+%struct.X = type { i32, i32 }
+
+define i32 @test_gep_struct_load(%struct.X* %0) {
+; CHECK-LABEL: @test_gep_struct_load(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_X:%.*]], %struct.X* [[TMP0:%.*]], i64 0, i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %2 = getelementptr inbounds %struct.X, %struct.X* %0, i64 0, i32 1
+  %3 = load i32, i32* %2, align 4
+  %4 = icmp eq %struct.X* %0, null
+  %5 = select i1 %4, i32 0, i32 %3
+  ret i32 %5
+}
+
+define i32 @test_gep_struct_load_zero(%struct.X* %0) {
+; CHECK-LABEL: @test_gep_struct_load_zero(
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds [[STRUCT_X:%.*]], %struct.X* [[TMP0:%.*]], i64 0, i32 0
+; CHECK-NEXT:    [[TMP3:%.*]] = load i32, i32* [[TMP2]], align 4
+; CHECK-NEXT:    ret i32 [[TMP3]]
+;
+  %2 = getelementptr inbounds %struct.X, %struct.X* %0, i64 0, i32 0
+  %3 = load i32, i32* %2, align 4
+  %4 = icmp eq %struct.X* %0, null
+  %5 = select i1 %4, i32 0, i32 %3
+  ret i32 %5
+}
+
+define dso_local i32 @test_null_gep_from_assume(i32* %0, i64 %1) {
+; CHECK-LABEL: @test_null_gep_from_assume(
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ne i64 [[TMP1:%.*]], 0
+; CHECK-NEXT:    tail call void @llvm.assume(i1 [[TMP3]])
+; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds i32, i32* [[TMP0:%.*]], i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP5:%.*]] = load i32, i32* [[TMP4]], align 4
+; CHECK-NEXT:    ret i32 [[TMP5]]
+;
+  %3 = icmp ne i64 %1, 0
+  tail call void @llvm.assume(i1 %3)
+  %4 = getelementptr inbounds i32, i32* %0, i64 %1
+  %5 = load i32, i32* %4, align 4
+  %6 = icmp eq i32* %0, null
+  %7 = select i1 %6, i32 0, i32 %5
+  ret i32 %7
+}
+
+declare void @llvm.assume(i1)
+
+define i8* @test_null_gep_load_store_after_check(i8* %0) {
+; CHECK-LABEL: @test_null_gep_load_store_after_check(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8* @func(i64 0)
+; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* [[TMP1]], null
+; CHECK-NEXT:    br i1 [[NULL_CHECK]], label [[RETURN:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.end:
+; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i8, i8* [[TMP1]], i64 1
+; CHECK-NEXT:    store i8 7, i8* [[TMP2]], align 1
+; CHECK-NEXT:    br label [[RETURN]]
+; CHECK:       return:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i8* [ [[TMP1]], [[IF_END]] ], [ null, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i8* [[RETVAL_0]]
+;
+entry:
+  %1 = call i8* @func(i64 0)
+  %null_check = icmp eq i8* %1, null
+  br i1 %null_check, label %return, label %if.end
+
+if.end:
+  %2 = getelementptr inbounds i8, i8* %1, i64 1
+  store i8 7, i8* %2
+  br label %return
+
+return:
+  %retval.0 = phi i8* [ %1, %if.end ], [ null, %entry ]
+  ret i8* %retval.0
+}
+
+define i8 @test_vector_null_gep([4 x i8]* %v) {
+; CHECK-LABEL: @test_vector_null_gep(
+; CHECK-NEXT:    store [4 x i8] zeroinitializer, [4 x i8]* [[V:%.*]], align 1
+; CHECK-NEXT:    ret i8 1
+;
+  %A = getelementptr [4 x i8], [4 x i8]* %v, i32 0
+  store [4 x i8] zeroinitializer, [4 x i8]* %v
+  %B = icmp eq [4 x i8]* %v, null
+  %S = select i1 %B, i8 0, i8 1
+  ret i8 %S
+}
+
+; FIXME: provide a more generic approach to dealing with bitcasts and others
+define i32 @test_bitcast(i32* %0) {
+; CHECK-LABEL: @test_bitcast(
+; CHECK-NEXT:    [[TMP2:%.*]] = bitcast i32* [[TMP0:%.*]] to i8*
+; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds i8, i8* [[TMP2]], i64 1
+; CHECK-NEXT:    [[TMP4:%.*]] = load i8, i8* [[TMP3]], align 1
+; CHECK-NEXT:    [[TMP5:%.*]] = sext i8 [[TMP4]] to i32
+; CHECK-NEXT:    [[TMP6:%.*]] = icmp eq i32* [[TMP0]], null
+; CHECK-NEXT:    [[TMP7:%.*]] = select i1 [[TMP6]], i32 0, i32 [[TMP5]]
+; CHECK-NEXT:    ret i32 [[TMP7]]
+;
+  %2 = bitcast i32* %0 to i8*
+  %3 = getelementptr inbounds i8, i8* %2, i64 1
+  %4 = load i8, i8* %3, align 1
+  %5 = sext i8 %4 to i32
+  %6 = icmp eq i32* %0, null
+  %7 = select i1 %6, i32 0, i32 %5
+  ret i32 %7
+}
+

llvm/test/Transforms/InstCombine/select-cmp-br.ll

 
 define void @test1(%C* %arg) {
 ; CHECK-LABEL: @test1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds [[C:%.*]], %C* [[ARG:%.*]], i64 0, i32 0, i32 0
 ; CHECK-NEXT:    [[M:%.*]] = load i64*, i64** [[TMP]], align 8
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 1, i32 0, i32 0
 ; CHECK-NEXT:    [[N:%.*]] = load i64*, i64** [[TMP1]], align 8
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i64* [[M]], [[N]]
-; CHECK-NEXT:    [[TMP71:%.*]] = icmp eq %C* [[ARG]], null
-; CHECK-NEXT:    [[TMP7:%.*]] = select i1 [[TMP5]], i1 true, i1 [[TMP71]]
-; CHECK-NEXT:    br i1 [[TMP7]], label [[BB10:%.*]], label [[BB8:%.*]]
+; CHECK-NEXT:    [[TMP5_NOT:%.*]] = icmp eq i64* [[M]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP5_NOT]], label [[BB8:%.*]], label [[BB10:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb8:
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 0, i32 0
-; CHECK-NEXT:    tail call void @bar(%struct.S* [[TMP9]])
+; CHECK-NEXT:    tail call void @bar(%struct.S* nonnull [[TMP9]])
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i64, i64* [[M]], i64 9
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[TMP2]] to i64 (%C*)**
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i64 (%C*)*, i64 (%C*)** [[TMP3]], align 8
-; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* [[ARG]])
+; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* nonnull [[ARG]])
 ; CHECK-NEXT:    br label [[BB]]
 ;
 entry:
   %tmp = getelementptr inbounds %C, %C* %arg, i64 0, i32 0, i32 0
   %m = load i64*, i64** %tmp, align 8
   %tmp1 = getelementptr inbounds %C, %C* %arg, i64 1, i32 0, i32 0
   %n = load i64*, i64** %tmp1, align 8
   %tmp2 = getelementptr inbounds i64, i64* %m, i64 9

 define void @test2(%C* %arg) {
 ; CHECK-LABEL: @test2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds [[C:%.*]], %C* [[ARG:%.*]], i64 0, i32 0, i32 0
 ; CHECK-NEXT:    [[M:%.*]] = load i64*, i64** [[TMP]], align 8
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 1, i32 0, i32 0
 ; CHECK-NEXT:    [[N:%.*]] = load i64*, i64** [[TMP1]], align 8
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64* [[M]], [[N]]
-; CHECK-NEXT:    [[TMP71:%.*]] = icmp eq %C* [[ARG]], null
-; CHECK-NEXT:    [[TMP7:%.*]] = select i1 [[TMP5]], i1 true, i1 [[TMP71]]
-; CHECK-NEXT:    br i1 [[TMP7]], label [[BB10:%.*]], label [[BB8:%.*]]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB10:%.*]], label [[BB8:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb8:
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 0, i32 0
-; CHECK-NEXT:    tail call void @bar(%struct.S* [[TMP9]])
+; CHECK-NEXT:    tail call void @bar(%struct.S* nonnull [[TMP9]])
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i64, i64* [[M]], i64 9
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[TMP2]] to i64 (%C*)**
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i64 (%C*)*, i64 (%C*)** [[TMP3]], align 8
-; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* [[ARG]])
+; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* nonnull [[ARG]])
 ; CHECK-NEXT:    br label [[BB]]
 ;
 entry:
   %tmp = getelementptr inbounds %C, %C* %arg, i64 0, i32 0, i32 0
   %m = load i64*, i64** %tmp, align 8
   %tmp1 = getelementptr inbounds %C, %C* %arg, i64 1, i32 0, i32 0
   %n = load i64*, i64** %tmp1, align 8
   %tmp2 = getelementptr inbounds i64, i64* %m, i64 9

 
 define void @test3(%C* %arg) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds [[C:%.*]], %C* [[ARG:%.*]], i64 0, i32 0, i32 0
 ; CHECK-NEXT:    [[M:%.*]] = load i64*, i64** [[TMP]], align 8
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 1, i32 0, i32 0
 ; CHECK-NEXT:    [[N:%.*]] = load i64*, i64** [[TMP1]], align 8
-; CHECK-NEXT:    [[TMP5:%.*]] = icmp ne i64* [[M]], [[N]]
-; CHECK-NEXT:    [[TMP7_NOT1:%.*]] = icmp eq %C* [[ARG]], null
-; CHECK-NEXT:    [[TMP7_NOT:%.*]] = select i1 [[TMP5]], i1 true, i1 [[TMP7_NOT1]]
-; CHECK-NEXT:    br i1 [[TMP7_NOT]], label [[BB10:%.*]], label [[BB8:%.*]]
+; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64* [[M]], [[N]]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB8:%.*]], label [[BB10:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb8:
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 0, i32 0
-; CHECK-NEXT:    tail call void @bar(%struct.S* [[TMP9]])
+; CHECK-NEXT:    tail call void @bar(%struct.S* nonnull [[TMP9]])
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i64, i64* [[M]], i64 9
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[TMP2]] to i64 (%C*)**
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i64 (%C*)*, i64 (%C*)** [[TMP3]], align 8
-; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* [[ARG]])
+; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* nonnull [[ARG]])
 ; CHECK-NEXT:    br label [[BB]]
 ;
 entry:
   %tmp = getelementptr inbounds %C, %C* %arg, i64 0, i32 0, i32 0
   %m = load i64*, i64** %tmp, align 8
   %tmp1 = getelementptr inbounds %C, %C* %arg, i64 1, i32 0, i32 0
   %n = load i64*, i64** %tmp1, align 8
   %tmp2 = getelementptr inbounds i64, i64* %m, i64 9

 define void @test4(%C* %arg) {
 ; CHECK-LABEL: @test4(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP:%.*]] = getelementptr inbounds [[C:%.*]], %C* [[ARG:%.*]], i64 0, i32 0, i32 0
 ; CHECK-NEXT:    [[M:%.*]] = load i64*, i64** [[TMP]], align 8
 ; CHECK-NEXT:    [[TMP1:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 1, i32 0, i32 0
 ; CHECK-NEXT:    [[N:%.*]] = load i64*, i64** [[TMP1]], align 8
 ; CHECK-NEXT:    [[TMP5:%.*]] = icmp eq i64* [[M]], [[N]]
-; CHECK-NEXT:    [[TMP7_NOT1:%.*]] = icmp eq %C* [[ARG]], null
-; CHECK-NEXT:    [[TMP7_NOT:%.*]] = select i1 [[TMP5]], i1 true, i1 [[TMP7_NOT1]]
-; CHECK-NEXT:    br i1 [[TMP7_NOT]], label [[BB10:%.*]], label [[BB8:%.*]]
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB10:%.*]], label [[BB8:%.*]]
 ; CHECK:       bb:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb8:
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds [[C]], %C* [[ARG]], i64 0, i32 0
-; CHECK-NEXT:    tail call void @bar(%struct.S* [[TMP9]])
+; CHECK-NEXT:    tail call void @bar(%struct.S* nonnull [[TMP9]])
 ; CHECK-NEXT:    br label [[BB:%.*]]
 ; CHECK:       bb10:
 ; CHECK-NEXT:    [[TMP2:%.*]] = getelementptr inbounds i64, i64* [[M]], i64 9
 ; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[TMP2]] to i64 (%C*)**
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i64 (%C*)*, i64 (%C*)** [[TMP3]], align 8
-; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* [[ARG]])
+; CHECK-NEXT:    [[TMP11:%.*]] = tail call i64 [[TMP4]](%C* nonnull [[ARG]])
 ; CHECK-NEXT:    br label [[BB]]
 ;
 entry:
   %tmp = getelementptr inbounds %C, %C* %arg, i64 0, i32 0, i32 0
   %m = load i64*, i64** %tmp, align 8
   %tmp1 = getelementptr inbounds %C, %C* %arg, i64 1, i32 0, i32 0
   %n = load i64*, i64** %tmp1, align 8
   %tmp2 = getelementptr inbounds i64, i64* %m, i64 9