Index: llvm/include/llvm/Transforms/IPO/Attributor.h
===================================================================
--- llvm/include/llvm/Transforms/IPO/Attributor.h
+++ llvm/include/llvm/Transforms/IPO/Attributor.h
@@ -1820,6 +1820,27 @@
   /// State representing for dereferenceable bytes.
   IncIntegerState<> DerefBytesState;
 
+  /// Map representing for accessed memory offsets and sizes.
+  /// A key is Offset and a value is size.
+  /// If there is a load/store instruction something like,
+  ///   p[offset] = v;
+  /// (offset, sizeof(v)) will be inserted to this map.
+  /// std::map is used because we want to iterate keys in ascending order.
+  std::map<int64_t, int64_t> AccessedBytesMap;
+
+  /// Helper function to calculate dereferenceable bytes from current known
+  /// bytes and accessed bytes.
+  void computeKnownDerefBytesFromAccessedMap() {
+    int64_t KnownBytes = DerefBytesState.getKnown();
+    for (auto &Access : AccessedBytesMap) {
+      if (KnownBytes < Access.first)
+        break;
+      KnownBytes = std::max(KnownBytes, Access.first + Access.second);
+    }
+
+    DerefBytesState.takeKnownMaximum(KnownBytes);
+  }
+
   /// State representing that whether the value is globaly dereferenceable.
   BooleanState GlobalState;
 
@@ -1849,6 +1870,9 @@
   /// Update known dereferenceable bytes.
   void takeKnownDerefBytesMaximum(uint64_t Bytes) {
     DerefBytesState.takeKnownMaximum(Bytes);
+
+    // Known bytes might increase.
+    computeKnownDerefBytesFromAccessedMap();
   }
 
   /// Update assumed dereferenceable bytes.
@@ -1856,6 +1880,14 @@
     DerefBytesState.takeAssumedMinimum(Bytes);
   }
 
+  /// Add accessed bytes to the map.
+  void addAccessedBytes(int64_t Offset, int64_t Size) {
+    AccessedBytesMap[Offset] = std::max(AccessedBytesMap[Offset], Size);
+
+    // Known bytes might increase.
+    computeKnownDerefBytesFromAccessedMap();
+  }
+
   /// Equality for DerefState.
   bool operator==(const DerefState &R) {
     return this->DerefBytesState == R.DerefBytesState &&
Index: llvm/lib/Transforms/IPO/Attributor.cpp
===================================================================
--- llvm/lib/Transforms/IPO/Attributor.cpp
+++ llvm/lib/Transforms/IPO/Attributor.cpp
@@ -308,15 +308,16 @@
 
   return nullptr;
 }
-static const Value *getBasePointerOfAccessPointerOperand(const Instruction *I,
-                                                         int64_t &BytesOffset,
-                                                         const DataLayout &DL) {
+static const Value *
+getBasePointerOfAccessPointerOperand(const Instruction *I, int64_t &BytesOffset,
+                                     const DataLayout &DL,
+                                     bool AllowNonInbounds = false) {
   const Value *Ptr = getPointerOperand(I);
   if (!Ptr)
     return nullptr;
 
   return GetPointerBaseWithConstantOffset(Ptr, BytesOffset, DL,
-                                          /*AllowNonInbounds*/ false);
+                                          AllowNonInbounds);
 }
 
 ChangeStatus AbstractAttribute::update(Attributor &A) {
@@ -1702,8 +1703,7 @@
     return 0;
   }
   if (auto *GEP = dyn_cast<GetElementPtrInst>(I))
-    if (GEP->hasAllZeroIndices() ||
-        (GEP->isInBounds() && GEP->hasAllConstantIndices())) {
+    if (GEP->hasAllConstantIndices()) {
       TrackUse = true;
       return 0;
     }
@@ -1718,6 +1718,18 @@
       return std::max(int64_t(0), DerefBytes);
     }
   }
+
+  /// Corner case when an offset is 0.
+  if (const Value *Base = getBasePointerOfAccessPointerOperand(
+          I, Offset, DL, /*AllowNonInbounds*/ true)) {
+    if (Offset == 0 && Base == &AssociatedValue &&
+        getPointerOperand(I) == UseV) {
+      int64_t DerefBytes =
+          (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType());
+      IsNonNull |= !NullPointerIsDefined;
+      return std::max(int64_t(0), DerefBytes);
+    }
+  }
   if (const Value *Base =
           GetPointerBaseWithConstantOffset(UseV, Offset, DL,
                                            /*AllowNonInbounds*/ false)) {
@@ -2949,12 +2961,34 @@
   const StateType &getState() const override { return *this; }
   /// }
 
+  void addAccessedBytesForUse(Attributor &A, const Use *U,
+                              const Instruction *I) {
+    const Value *UseV = U->get();
+    if (!UseV->getType()->isPointerTy())
+      return;
+
+    Type *PtrTy = UseV->getType();
+    const DataLayout &DL = A.getDataLayout();
+    int64_t Offset;
+    if (const Value *Base = getBasePointerOfAccessPointerOperand(
+            I, Offset, DL, /*AllowNonInbounds*/ true)) {
+      if (Base == &getAssociatedValue() && getPointerOperand(I) == UseV) {
+        int64_t Size =
+            (int64_t)DL.getTypeStoreSize(PtrTy->getPointerElementType());
+        addAccessedBytes(Offset, Size);
+      }
+    }
+    return;
+  }
+
   /// See AAFromMustBeExecutedContext
   bool followUse(Attributor &A, const Use *U, const Instruction *I) {
     bool IsNonNull = false;
     bool TrackUse = false;
     int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
         A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
+
+    addAccessedBytesForUse(A, U, I);
     takeKnownDerefBytesMaximum(DerefBytes);
     return TrackUse;
   }
Index: llvm/test/Transforms/FunctionAttrs/align.ll
===================================================================
--- llvm/test/Transforms/FunctionAttrs/align.ll
+++ llvm/test/Transforms/FunctionAttrs/align.ll
@@ -351,8 +351,7 @@
   ret i64 %ret
 }
 
-; FXIME: %p should have nonnull
-; ATTRIBUTOR: define i64 @test12-2(i32* nocapture nofree readonly align 16 %p)
+; ATTRIBUTOR: define i64 @test12-2(i32* nocapture nofree nonnull readonly align 16 dereferenceable(8) %p)
 define i64 @test12-2(i32* align 4 %p) {
   %p-cast = bitcast i32* %p to i64*
   %arrayidx0 = getelementptr i64, i64* %p-cast, i64 0
@@ -370,8 +369,7 @@
   ret void 
 }
 
-; FXIME: %p should have nonnull
-; ATTRIBUTOR: define void @test12-4(i32* nocapture nofree writeonly align 16 %p)
+; ATTRIBUTOR: define void @test12-4(i32* nocapture nofree nonnull writeonly align 16 dereferenceable(8) %p)
 define void @test12-4(i32* align 4 %p) {
   %p-cast = bitcast i32* %p to i64*
   %arrayidx0 = getelementptr i64, i64* %p-cast, i64 0
Index: llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll
===================================================================
--- llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll
+++ llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll
@@ -48,8 +48,7 @@
 
 define double @PR21780_without_inbounds(double* %ptr) {
 ; CHECK-LABEL: @PR21780_without_inbounds(double* %ptr)
-; FIXME: this should be @PR21780_without_inbounds(double* nonnull dereferenceable(32) %ptr)
-; ATTRIBUTOR-LABEL: @PR21780_without_inbounds(double* nocapture nofree nonnull readonly align 8 dereferenceable(8) %ptr)
+; ATTRIBUTOR-LABEL: @PR21780_without_inbounds(double* nocapture nofree nonnull readonly align 8 dereferenceable(32) %ptr)
 
   %arrayidx1 = getelementptr double, double* %ptr, i64 1
   %arrayidx2 = getelementptr double, double* %ptr, i64 2
@@ -67,6 +66,7 @@
 
 define void @gep0(i8* %unused, i8* %other, i8* %ptr) {
 ; CHECK-LABEL: @gep0(i8* %unused, i8* %other, i8* %ptr)
+; ATTRIBUTOR-LABEL: @gep0(i8* nocapture nofree readnone %unused, i8* nocapture nofree nonnull writeonly dereferenceable(1) %other, i8* nocapture nofree nonnull readonly dereferenceable(3) %ptr)
   %arrayidx0 = getelementptr i8, i8* %ptr, i64 0
   %arrayidx1 = getelementptr i8, i8* %ptr, i64 1
   %arrayidx2 = getelementptr i8, i8* %ptr, i64 2
@@ -82,6 +82,7 @@
 
 define void @ordering(i8* %ptr1, i32* %ptr2) {
 ; CHECK-LABEL: @ordering(i8* %ptr1, i32* %ptr2)
+; ATTRIBUTOR-LABEL: @ordering(i8* nocapture nofree nonnull readonly dereferenceable(3) %ptr1, i32* nocapture nofree nonnull readonly dereferenceable(8) %ptr2)
   %a20 = getelementptr i32, i32* %ptr2, i64 0
   %a12 = getelementptr i8, i8* %ptr1, i64 2
   %t12 = load i8, i8* %a12
@@ -99,6 +100,7 @@
 
 define void @not_entry_but_guaranteed_to_execute(i8* %ptr) {
 ; CHECK-LABEL: @not_entry_but_guaranteed_to_execute(i8* %ptr)
+; ATTRIBUTOR-LABEL: @not_entry_but_guaranteed_to_execute(i8* nocapture nofree nonnull readonly dereferenceable(3) %ptr)
 entry:
   br label %exit
 exit:
@@ -115,6 +117,7 @@
 
 define void @not_entry_not_guaranteed_to_execute(i8* %ptr, i1 %cond) {
 ; CHECK-LABEL: @not_entry_not_guaranteed_to_execute(i8* %ptr, i1 %cond)
+; ATTRIBUTOR-LABEL: @not_entry_not_guaranteed_to_execute(i8* nocapture nofree readonly %ptr, i1 %cond)
 entry:
   br i1 %cond, label %loads, label %exit
 loads:
@@ -133,6 +136,7 @@
 
 define void @partial_in_entry(i16* %ptr, i1 %cond) {
 ; CHECK-LABEL: @partial_in_entry(i16* %ptr, i1 %cond)
+; ATTRIBUTOR-LABEL: @partial_in_entry(i16* nocapture nofree nonnull readonly dereferenceable(4) %ptr, i1 %cond)
 entry:
   %arrayidx0 = getelementptr i16, i16* %ptr, i64 0
   %arrayidx1 = getelementptr i16, i16* %ptr, i64 1
@@ -152,6 +156,7 @@
 
 define void @volatile_is_not_dereferenceable(i16* %ptr) {
 ; CHECK-LABEL: @volatile_is_not_dereferenceable(i16* %ptr)
+; ATTRIBUTOR-LABEL: @volatile_is_not_dereferenceable(i16* nofree %ptr)
   %arrayidx0 = getelementptr i16, i16* %ptr, i64 0
   %arrayidx1 = getelementptr i16, i16* %ptr, i64 1
   %arrayidx2 = getelementptr i16, i16* %ptr, i64 2
@@ -165,6 +170,7 @@
 
 define void @not_guaranteed_to_transfer_execution(i16* %ptr) {
 ; CHECK-LABEL: @not_guaranteed_to_transfer_execution(i16* %ptr)
+; ATTRIBUTOR-LABEL: @not_guaranteed_to_transfer_execution(i16* nocapture nonnull readonly dereferenceable(2) %ptr)
   %arrayidx0 = getelementptr i16, i16* %ptr, i64 0
   %arrayidx1 = getelementptr i16, i16* %ptr, i64 1
   %arrayidx2 = getelementptr i16, i16* %ptr, i64 2
@@ -179,6 +185,7 @@
 
 define void @variable_gep_index(i8* %unused, i8* %ptr, i64 %variable_index) {
 ; CHECK-LABEL: @variable_gep_index(i8* %unused, i8* %ptr, i64 %variable_index)
+; ATTRIBUTOR-LABEL: @variable_gep_index(i8* nocapture nofree readnone %unused, i8* nocapture nofree nonnull readonly dereferenceable(1) %ptr, i64 %variable_index)
   %arrayidx1 = getelementptr i8, i8* %ptr, i64 %variable_index
   %arrayidx2 = getelementptr i8, i8* %ptr, i64 2
   %t0 = load i8, i8* %ptr
@@ -191,6 +198,8 @@
 
 define void @multi_index_gep(<4 x i8>* %ptr) {
 ; CHECK-LABEL: @multi_index_gep(<4 x i8>* %ptr)
+; FIXME: %ptr should be dereferenceable(4)
+; ATTRIBUTOR-LABEL: @multi_index_gep(<4 x i8>* nocapture nofree nonnull readonly dereferenceable(1) %ptr)
   %arrayidx00 = getelementptr <4 x i8>, <4 x i8>* %ptr, i64 0, i64 0
   %t0 = load i8, i8* %arrayidx00
   ret void
@@ -200,6 +209,7 @@
 
 define void @not_byte_multiple(i9* %ptr) {
 ; CHECK-LABEL: @not_byte_multiple(i9* %ptr)
+; ATTRIBUTOR-LABEL: @not_byte_multiple(i9* nocapture nofree nonnull readonly dereferenceable(2) %ptr) 
   %arrayidx0 = getelementptr i9, i9* %ptr, i64 0
   %t0 = load i9, i9* %arrayidx0
   ret void
@@ -209,6 +219,7 @@
 
 define void @no_pointer_deref(i16* %ptr) {
 ; CHECK-LABEL: @no_pointer_deref(i16* %ptr)
+; ATTRIBUTOR-LABEL: @no_pointer_deref(i16* nocapture nofree readonly %ptr)
   %arrayidx1 = getelementptr i16, i16* %ptr, i64 1
   %arrayidx2 = getelementptr i16, i16* %ptr, i64 2
   %t1 = load i16, i16* %arrayidx1
@@ -220,6 +231,7 @@
 
 define void @non_consecutive(i32* %ptr) {
 ; CHECK-LABEL: @non_consecutive(i32* %ptr)
+; ATTRIBUTOR-LABEL: @non_consecutive(i32* nocapture nofree nonnull readonly dereferenceable(8) %ptr)
   %arrayidx1 = getelementptr i32, i32* %ptr, i64 1
   %arrayidx0 = getelementptr i32, i32* %ptr, i64 0
   %arrayidx3 = getelementptr i32, i32* %ptr, i64 3
@@ -233,6 +245,7 @@
 
 define void @more_bytes(i32* dereferenceable(8) %ptr) {
 ; CHECK-LABEL: @more_bytes(i32* dereferenceable(8) %ptr)
+; ATTRIBUTOR-LABEL: @more_bytes(i32* nocapture nofree nonnull readonly dereferenceable(16) %ptr)
   %arrayidx3 = getelementptr i32, i32* %ptr, i64 3
   %arrayidx1 = getelementptr i32, i32* %ptr, i64 1
   %arrayidx0 = getelementptr i32, i32* %ptr, i64 0
@@ -248,6 +261,7 @@
 
 define void @better_bytes(i32* dereferenceable(100) %ptr) {
 ; CHECK-LABEL: @better_bytes(i32* dereferenceable(100) %ptr)
+; ATTRIBUTOR-LABEL: @better_bytes(i32* nocapture nofree nonnull readonly dereferenceable(100) %ptr)
   %arrayidx3 = getelementptr i32, i32* %ptr, i64 3
   %arrayidx1 = getelementptr i32, i32* %ptr, i64 1
   %arrayidx0 = getelementptr i32, i32* %ptr, i64 0
@@ -261,6 +275,7 @@
 
 define void @bitcast(i32* %arg) {
 ; CHECK-LABEL: @bitcast(i32* %arg)
+; ATTRIBUTOR-LABEL: @bitcast(i32* nocapture nofree nonnull readonly dereferenceable(8) %arg)
   %ptr = bitcast i32* %arg to float*
   %arrayidx0 = getelementptr float, float* %ptr, i64 0
   %arrayidx1 = getelementptr float, float* %ptr, i64 1
@@ -271,6 +286,7 @@
 
 define void @bitcast_different_sizes(double* %arg1, i8* %arg2) {
 ; CHECK-LABEL: @bitcast_different_sizes(double* %arg1, i8* %arg2)
+; ATTRIBUTOR-LABEL: @bitcast_different_sizes(double* nocapture nofree nonnull readonly dereferenceable(12) %arg1, i8* nocapture nofree nonnull readonly dereferenceable(16) %arg2)
   %ptr1 = bitcast double* %arg1 to float*
   %a10 = getelementptr float, float* %ptr1, i64 0
   %a11 = getelementptr float, float* %ptr1, i64 1
@@ -289,6 +305,7 @@
 
 define void @negative_offset(i32* %arg) {
 ; CHECK-LABEL: @negative_offset(i32* %arg)
+; ATTRIBUTOR-LABEL: @negative_offset(i32* nocapture nofree nonnull readonly dereferenceable(4) %arg)
   %ptr = bitcast i32* %arg to float*
   %arrayidx0 = getelementptr float, float* %ptr, i64 0
   %arrayidx1 = getelementptr float, float* %ptr, i64 -1
@@ -299,6 +316,7 @@
 
 define void @stores(i32* %arg) {
 ; CHECK-LABEL: @stores(i32* %arg)
+; ATTRIBUTOR-LABEL: @stores(i32* nocapture nofree nonnull writeonly dereferenceable(8) %arg)
   %ptr = bitcast i32* %arg to float*
   %arrayidx0 = getelementptr float, float* %ptr, i64 0
   %arrayidx1 = getelementptr float, float* %ptr, i64 1
@@ -309,6 +327,7 @@
 
 define void @load_store(i32* %arg) {
 ; CHECK-LABEL: @load_store(i32* %arg)
+; ATTRIBUTOR-LABEL: @load_store(i32* nocapture nofree nonnull dereferenceable(8) %arg)
   %ptr = bitcast i32* %arg to float*
   %arrayidx0 = getelementptr float, float* %ptr, i64 0
   %arrayidx1 = getelementptr float, float* %ptr, i64 1