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,42 @@ /// 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 AccessedBytesMap; + + /// Helper function to calculate dereferenceable bytes from current known + /// bytes and accessed bytes. + /// + /// int f(int *A){ + /// *A = 0; + /// *(A+2) = 2; + /// *(A+1) = 1; + /// *(A+10) = 10; + /// } + /// ``` + /// In that case, AccessedBytesMap is `{0:4, 4:4, 8:4, 40:4}`. + /// AccessedBytesMap is std::map so it is iterated in accending order on + /// key(Offset). So KnownBytes will be updated like this: |Access | KnownBytes + /// |(0, 4)| 0 -> 4 + /// |(4, 4)| 4 -> 8 + /// |(8, 4)| 8 -> 12 + /// |(40, 4) | 12 (break) + void computeKnownDerefBytesFromAccessedMap() { + int64_t KnownBytes = DerefBytesState.getKnown(); + for (auto &Access : AccessedBytesMap) { + if (KnownBytes < Access.first) + break; + KnownBytes = std::max(KnownBytes, Access.first + (int64_t)Access.second); + } + + DerefBytesState.takeKnownMaximum(KnownBytes); + } + /// State representing that whether the value is globaly dereferenceable. BooleanState GlobalState; @@ -1849,6 +1885,9 @@ /// Update known dereferenceable bytes. void takeKnownDerefBytesMaximum(uint64_t Bytes) { DerefBytesState.takeKnownMaximum(Bytes); + + // Known bytes might increase. + computeKnownDerefBytesFromAccessedMap(); } /// Update assumed dereferenceable bytes. @@ -1856,6 +1895,14 @@ DerefBytesState.takeAssumedMinimum(Bytes); } + /// Add accessed bytes to the map. + void addAccessedBytes(int64_t Offset, uint64_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 @@ -2961,12 +2961,34 @@ const StateType &getState() const override { return *this; } /// } + /// Helper function for collecting accessed bytes in must-be-executed-context + 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) { + uint64_t Size = 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/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 @atomic_is_alright(i16* %ptr) { ; CHECK-LABEL: @atomic_is_alright(i16* %ptr) +; ATTRIBUTOR-LABEL: @atomic_is_alright(i16* nocapture nofree nonnull readonly align 2 dereferenceable(6) %ptr) %arrayidx0 = getelementptr i16, i16* %ptr, i64 0 %arrayidx1 = getelementptr i16, i16* %ptr, i64 1 %arrayidx2 = getelementptr i16, i16* %ptr, i64 2 @@ -178,6 +184,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 @@ -192,6 +199,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 @@ -204,6 +212,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 @@ -213,6 +223,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 @@ -222,6 +233,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 @@ -233,6 +245,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 @@ -246,6 +259,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 @@ -261,6 +275,7 @@ define void @more_bytes_and_not_null(i32* dereferenceable_or_null(8) %ptr) { ; CHECK-LABEL: @more_bytes_and_not_null(i32* dereferenceable_or_null(8) %ptr) +; ATTRIBUTOR-LABEL: @more_bytes_and_not_null(i32* nocapture nofree nonnull readonly dereferenceable(16) dereferenceable_or_null(8) %ptr) %arrayidx3 = getelementptr i32, i32* %ptr, i64 3 %arrayidx1 = getelementptr i32, i32* %ptr, i64 1 %arrayidx0 = getelementptr i32, i32* %ptr, i64 0 @@ -276,6 +291,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 @@ -289,6 +305,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 @@ -299,6 +316,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 @@ -317,6 +335,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 @@ -327,6 +346,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 @@ -337,6 +357,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