From acf3279a037ff9c8591f551e92b8e7a8c27b61a4 Mon Sep 17 00:00:00 2001
From: Momchil Velikov <momchil.velikov@arm.com>
Date: Fri, 9 Apr 2021 13:54:39 +0100
Subject: [PATCH] For non-null pointer checks, do not descend through
 out-of-bounds GEPs

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.

Differential Revision: https://reviews.llvm.org/D99642
---
 llvm/lib/Analysis/LazyValueInfo.cpp                    |  2 +-
 .../JumpThreading/nonnull-gep-out-of-bounds.ll         | 18 ++++++++++++++++++
 2 files changed, 19 insertions(+), 1 deletion(-)
 create mode 100644 llvm/test/Transforms/JumpThreading/nonnull-gep-out-of-bounds.ll

diff --git a/llvm/lib/Analysis/LazyValueInfo.cpp b/llvm/lib/Analysis/LazyValueInfo.cpp
index 75fef34..6bf03e8 100644
--- a/llvm/lib/Analysis/LazyValueInfo.cpp
+++ b/llvm/lib/Analysis/LazyValueInfo.cpp
@@ -658,7 +658,7 @@ bool LazyValueInfoImpl::isNonNullAtEndOfBlock(Value *Val, BasicBlock *BB) {
                            Val->getType()->getPointerAddressSpace()))
     return false;
 
-  Val = getUnderlyingObject(Val);
+  Val = Val->stripInBoundsOffsets();
   return TheCache.isNonNullAtEndOfBlock(Val, BB, [](BasicBlock *BB) {
     NonNullPointerSet NonNullPointers;
     for (Instruction &I : *BB)
diff --git a/llvm/test/Transforms/JumpThreading/nonnull-gep-out-of-bounds.ll b/llvm/test/Transforms/JumpThreading/nonnull-gep-out-of-bounds.ll
new file mode 100644
index 0000000..37737bb
--- /dev/null
+++ b/llvm/test/Transforms/JumpThreading/nonnull-gep-out-of-bounds.ll
@@ -0,0 +1,18 @@
+; RUN: opt -jump-threading -S %s -o - | FileCheck %s
+
+define i32 @f(i64* %a, i64 %i) {
+entry:
+  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:
+  ret i32 0
+
+if.else:
+  ret i32 1
+}
-- 
2.7.4