diff --git a/llvm/include/llvm/Transforms/IPO/Attributor.h b/llvm/include/llvm/Transforms/IPO/Attributor.h --- a/llvm/include/llvm/Transforms/IPO/Attributor.h +++ b/llvm/include/llvm/Transforms/IPO/Attributor.h @@ -130,6 +130,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/ModRef.h" #include "llvm/Support/TimeProfiler.h" +#include "llvm/Support/TypeSize.h" #include "llvm/TargetParser/Triple.h" #include "llvm/Transforms/Utils/CallGraphUpdater.h" @@ -6087,6 +6088,42 @@ static const char ID; }; +struct AAAllocationInfo : public StateWrapper { + AAAllocationInfo(const IRPosition &IRP, Attributor &A) + : StateWrapper(IRP) {} + + /// See AbstractAttribute::isValidIRPositionForInit + static bool isValidIRPositionForInit(Attributor &A, const IRPosition &IRP) { + if (!IRP.getAssociatedType()->isPtrOrPtrVectorTy()) + return false; + return AbstractAttribute::isValidIRPositionForInit(A, IRP); + } + + /// Create an abstract attribute view for the position \p IRP. + static AAAllocationInfo &createForPosition(const IRPosition &IRP, + Attributor &A); + + virtual std::optional getAllocatedSize() const = 0; + + /// See AbstractAttribute::getName() + const std::string getName() const override { return "AAAllocationInfo"; } + + /// See AbstractAttribute::getIdAddr() + const char *getIdAddr() const override { return &ID; } + + /// This function should return true if the type of the \p AA is + /// AAAllocationInfo + static bool classof(const AbstractAttribute *AA) { + return (AA->getIdAddr() == &ID); + } + + // No AllocatedSpace which means it doesn't allocated memory. + constexpr static const std::optional NOAllocatedSize = + std::optional(TypeSize(-1, true)); + + static const char ID; +}; + raw_ostream &operator<<(raw_ostream &, const AAPointerInfo::Access &); /// Run options, used by the pass manager. diff --git a/llvm/lib/Transforms/IPO/Attributor.cpp b/llvm/lib/Transforms/IPO/Attributor.cpp --- a/llvm/lib/Transforms/IPO/Attributor.cpp +++ b/llvm/lib/Transforms/IPO/Attributor.cpp @@ -3545,6 +3545,20 @@ UsedAssumedInformation); (void)Success; assert(Success && "Expected the check call to be successful!"); + + // AllocaInstPredicate + auto AllocaInstPred = [&](Instruction &I) -> bool { + if (auto *AI = dyn_cast(&I)) { + getOrCreateAAFor(IRPosition::value(*AI)); + } + return true; + }; + + Success = checkForAllInstructionsImpl( + nullptr, OpcodeInstMap, AllocaInstPred, nullptr, nullptr, + {(unsigned)Instruction::Alloca}, UsedAssumedInformation); + (void)Success; + assert(Success && "Expected the check call to be successful!"); } /// Helpers to ease debugging through output streams and print calls. diff --git a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp --- a/llvm/lib/Transforms/IPO/AttributorAttributes.cpp +++ b/llvm/lib/Transforms/IPO/AttributorAttributes.cpp @@ -64,6 +64,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GraphWriter.h" #include "llvm/Support/MathExtras.h" +#include "llvm/Support/TypeSize.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Transforms/Utils/ValueMapper.h" @@ -188,6 +189,7 @@ PIPE_OPERATOR(AAAssumptionInfo) PIPE_OPERATOR(AAUnderlyingObjects) PIPE_OPERATOR(AAAddressSpace) +PIPE_OPERATOR(AAAllocationInfo) #undef PIPE_OPERATOR @@ -869,6 +871,7 @@ using const_bin_iterator = OffsetBinsTy::const_iterator; const_bin_iterator begin() const { return OffsetBins.begin(); } const_bin_iterator end() const { return OffsetBins.end(); } + int64_t size() const { return OffsetBins.size(); } const AAPointerInfo::Access &getAccess(unsigned Index) const { return AccessList[Index]; @@ -12189,6 +12192,173 @@ }; } // namespace +/// ----------- Allocation Info ---------- +namespace { +struct AAAllocationInfoImpl : public AAAllocationInfo { + AAAllocationInfoImpl(const IRPosition &IRP, Attributor &A) + : AAAllocationInfo(IRP, A) {} + + std::optional getAllocatedSize() const override { + assert(isValidState() && "the AA is invalid"); + return AssumedAllocatedSize; + } + + ChangeStatus updateImpl(Attributor &A) override { + + auto *I = this->getIRPosition().getCtxI(); + AllocaInst &AI = cast(*I); + const IRPosition &IRP = IRPosition::inst(AI); + auto *PI = + A.getOrCreateAAFor(IRP, *this, DepClassTy::OPTIONAL); + + if (!PI) { + return indicatePessimisticFixpoint(); + } + + const AAPointerInfo &OtherAA = *PI; + + if (!OtherAA.getState().isValidState()) { + return indicatePessimisticFixpoint(); + } + + const auto &OtherAAImpl = static_cast(*PI); + const auto &State = OtherAAImpl.getState(); + + int BinSize = State.size(); + + if (BinSize > 1) { + return indicatePessimisticFixpoint(); + } + + const auto &It = State.begin(); + + if (It->getFirst().Offset != 0) { + return indicatePessimisticFixpoint(); + } + + int64_t OffsetEnd = It->getFirst().Offset + It->getFirst().Size; + const DataLayout &DL = AI.getModule()->getDataLayout(); + const auto &AllocationSize = AI.getAllocationSize(DL); + + if (!AllocationSize) { + return indicatePessimisticFixpoint(); + } + + if (OffsetEnd == AllocationSize) { + return indicatePessimisticFixpoint(); + } + + Type *IntegerSizeOfOffsetEnd = + Type::getIntNTy(AI.getContext(), OffsetEnd * 8); + + if (!changeAllocationSize( + IntegerSizeOfOffsetEnd->getPrimitiveSizeInBits())) { + return ChangeStatus::UNCHANGED; + } + + return ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::manifest(...). + ChangeStatus manifest(Attributor &A) override { + + if (!isValidState()) { + return indicatePessimisticFixpoint(); + } + + auto *I = this->getIRPosition().getCtxI(); + AllocaInst &AI = cast(*I); + + Type *IntegerSizeOfAlloca = + Type::getIntNTy(AI.getContext(), getAllocatedSize()->getFixedValue()); + + AI.setAllocatedType(IntegerSizeOfAlloca); + return ChangeStatus::CHANGED; + } + + /// See AbstractAttribute::getAsStr(). + const std::string getAsStr(Attributor *A) const override { + if (!isValidState()) + return "allocationinfo()"; + return "allocationinfo(" + + (AssumedAllocatedSize == NOAllocatedSize + ? "none" + : std::to_string(AssumedAllocatedSize->getFixedValue())) + + ")"; + } + +private: + std::optional AssumedAllocatedSize = NOAllocatedSize; + + bool changeAllocationSize(std::optional Size) { + if (AssumedAllocatedSize == NOAllocatedSize || + AssumedAllocatedSize != Size) { + AssumedAllocatedSize = Size; + return true; + } + return false; + } +}; + +struct AAAllocationInfoFloating : AAAllocationInfoImpl { + AAAllocationInfoFloating(const IRPosition &IRP, Attributor &A) + : AAAllocationInfoImpl(IRP, A) {} + + void trackStatistics() const override { + STATS_DECLTRACK_FLOATING_ATTR(allocationinfo); + } +}; + +struct AAAllocationInfoReturned : AAAllocationInfoImpl { + AAAllocationInfoReturned(const IRPosition &IRP, Attributor &A) + : AAAllocationInfoImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + // TODO: we don't rewrite function argument for now because it will need to + // rewrite the function signature and all call sites + (void)indicatePessimisticFixpoint(); + } + + void trackStatistics() const override { + STATS_DECLTRACK_FNRET_ATTR(allocationinfo); + } +}; + +struct AAAllocationInfoCallSiteReturned : AAAllocationInfoImpl { + AAAllocationInfoCallSiteReturned(const IRPosition &IRP, Attributor &A) + : AAAllocationInfoImpl(IRP, A) {} + + void trackStatistics() const override { + STATS_DECLTRACK_CSRET_ATTR(allocationinfo); + } +}; + +struct AAAllocationInfoArgument : AAAllocationInfoImpl { + AAAllocationInfoArgument(const IRPosition &IRP, Attributor &A) + : AAAllocationInfoImpl(IRP, A) {} + + void trackStatistics() const override { + STATS_DECLTRACK_ARG_ATTR(allocationinfo); + } +}; + +struct AAAllocationInfoCallSiteArgument : AAAllocationInfoImpl { + AAAllocationInfoCallSiteArgument(const IRPosition &IRP, Attributor &A) + : AAAllocationInfoImpl(IRP, A) {} + + /// See AbstractAttribute::initialize(...). + void initialize(Attributor &A) override { + + (void)indicatePessimisticFixpoint(); + } + + void trackStatistics() const override { + STATS_DECLTRACK_CSARG_ATTR(allocationinfo); + } +}; +} // namespace + const char AANoUnwind::ID = 0; const char AANoSync::ID = 0; const char AANoFree::ID = 0; @@ -12222,6 +12392,7 @@ const char AAAssumptionInfo::ID = 0; const char AAUnderlyingObjects::ID = 0; const char AAAddressSpace::ID = 0; +const char AAAllocationInfo::ID = 0; // Macro magic to create the static generator function for attributes that // follow the naming scheme. @@ -12340,6 +12511,7 @@ CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AANoFPClass) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAPointerInfo) CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAddressSpace) +CREATE_VALUE_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAAllocationInfo) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAValueSimplify) CREATE_ALL_ABSTRACT_ATTRIBUTE_FOR_POSITION(AAIsDead) diff --git a/llvm/test/Transforms/Attributor/allocator.ll b/llvm/test/Transforms/Attributor/allocator.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/Attributor/allocator.ll @@ -0,0 +1,122 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-attributes --check-globals --version 2 +; RUN: opt -aa-pipeline=basic-aa -passes=attributor -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,TUNIT +; RUN: opt -aa-pipeline=basic-aa -passes=attributor-cgscc -attributor-manifest-internal -attributor-annotate-decl-cs -S < %s | FileCheck %s --check-prefixes=CHECK,CGSCC + +%struct.Foo = type { i32, i32, i8 } + +@.str = private unnamed_addr constant [15 x i8] c"Field 1 is %d\0A\00", align 1 + +;. +; CHECK: @[[_STR:[a-zA-Z0-9_$"\\.-]+]] = private unnamed_addr constant [15 x i8] c"Field 1 is %d\0A\00", align 1 +;. +define dso_local void @foo_positive_test(i32 noundef %val) #0 { +; CHECK-LABEL: define dso_local void @foo_positive_test +; CHECK-SAME: (i32 noundef [[VAL:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[VAL_ADDR:%.*]] = alloca i32, align 4 +; CHECK-NEXT: [[F:%.*]] = alloca i32, align 4 +; CHECK-NEXT: store i32 [[VAL]], ptr [[VAL_ADDR]], align 4 +; CHECK-NEXT: store i32 10, ptr [[F]], align 4 +; CHECK-NEXT: [[TMP0:%.*]] = load i32, ptr [[F]], align 4 +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[TMP0]], 1 +; CHECK-NEXT: store i32 [[ADD]], ptr [[F]], align 4 +; CHECK-NEXT: [[TMP1:%.*]] = load i32, ptr [[F]], align 4 +; CHECK-NEXT: [[ADD3:%.*]] = add nsw i32 [[TMP1]], [[VAL]] +; CHECK-NEXT: [[CALL:%.*]] = call i32 (ptr, ...) @printf(ptr noundef nonnull dereferenceable(15) @.str, i32 noundef [[ADD3]]) +; CHECK-NEXT: ret void +; +entry: + %val.addr = alloca i64, align 4 + %f = alloca %struct.Foo, align 4 + store i32 %val, ptr %val.addr, align 4 + %field1 = getelementptr inbounds %struct.Foo, ptr %f, i32 0, i32 0 + store i32 10, ptr %field1, align 4 + %field11 = getelementptr inbounds %struct.Foo, ptr %f, i32 0, i32 0 + %0 = load i32, ptr %field11, align 4 + %add = add nsw i32 %0, 1 + store i32 %add, ptr %field11, align 4 + %field12 = getelementptr inbounds %struct.Foo, ptr %f, i32 0, i32 0 + %1 = load i32, ptr %field12, align 4 + %2 = load i32, ptr %val.addr, align 4 + %add3 = add nsw i32 %1, %2 + %call = call i32 (ptr, ...) @printf(ptr noundef @.str, i32 noundef %add3) + ret void +} + +; Function Attrs: noinline nounwind uwtable +define dso_local ptr @foo_negative_test_escaping_pointer(i32 noundef %val) #0 { +; CHECK-LABEL: define dso_local ptr @foo_negative_test_escaping_pointer +; CHECK-SAME: (i32 noundef [[VAL:%.*]]) { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[VAL_ADDR:%.*]] = alloca i32, align 4 +; CHECK-NEXT: [[F:%.*]] = alloca ptr, align 8 +; CHECK-NEXT: store i32 [[VAL]], ptr [[VAL_ADDR]], align 4 +; CHECK-NEXT: [[CALL:%.*]] = call noalias ptr @malloc(i64 noundef 16) +; CHECK-NEXT: store ptr [[CALL]], ptr [[F]], align 8 +; CHECK-NEXT: [[TMP0:%.*]] = load ptr, ptr [[F]], align 8 +; CHECK-NEXT: store i32 2, ptr [[TMP0]], align 8 +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 10, [[VAL]] +; CHECK-NEXT: [[TMP1:%.*]] = load ptr, ptr [[F]], align 8 +; CHECK-NEXT: [[TMP2:%.*]] = load i32, ptr [[TMP1]], align 8 +; CHECK-NEXT: [[ADD2:%.*]] = add nsw i32 [[TMP2]], [[ADD]] +; CHECK-NEXT: store i32 [[ADD2]], ptr [[TMP1]], align 8 +; CHECK-NEXT: [[TMP3:%.*]] = load ptr, ptr [[F]], align 8 +; CHECK-NEXT: ret ptr [[TMP3]] +; +entry: + %val.addr = alloca i32, align 4 + %f = alloca ptr, align 8 + store i32 %val, ptr %val.addr, align 4 + %call = call noalias ptr @malloc(i64 noundef 16) #2 + store ptr %call, ptr %f, align 8 + %0 = load ptr, ptr %f, align 8 + %field1 = getelementptr inbounds %struct.Foo, ptr %0, i32 0, i32 0 + store i32 2, ptr %field1, align 8 + %1 = load i32, ptr %val.addr, align 4 + %add = add nsw i32 10, %1 + %2 = load ptr, ptr %f, align 8 + %field11 = getelementptr inbounds %struct.Foo, ptr %2, i32 0, i32 0 + %3 = load i32, ptr %field11, align 8 + %add2 = add nsw i32 %3, %add + store i32 %add2, ptr %field11, align 8 + %4 = load ptr, ptr %f, align 8 + ret ptr %4 +} + +; Function Attrs: noinline nounwind uwtable +define dso_local { i64, ptr } @foo_negative_test_not_a_single_start_offset(i32 noundef %val) #0 { +; CHECK: Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) +; CHECK-LABEL: define dso_local { i64, ptr } @foo_negative_test_not_a_single_start_offset +; CHECK-SAME: (i32 noundef [[VAL:%.*]]) #[[ATTR0:[0-9]+]] { +; CHECK-NEXT: entry: +; CHECK-NEXT: [[RETVAL:%.*]] = alloca [[STRUCT_FOO:%.*]], align 8 +; CHECK-NEXT: [[VAL_ADDR:%.*]] = alloca i32, align 4 +; CHECK-NEXT: store i32 [[VAL]], ptr [[VAL_ADDR]], align 4 +; CHECK-NEXT: store i32 2, ptr [[RETVAL]], align 8 +; CHECK-NEXT: [[FIELD3:%.*]] = getelementptr inbounds [[STRUCT_FOO]], ptr [[RETVAL]], i32 0, i32 2 +; CHECK-NEXT: store ptr [[VAL_ADDR]], ptr [[FIELD3]], align 8 +; CHECK-NEXT: [[TMP0:%.*]] = load { i64, ptr }, ptr [[RETVAL]], align 8 +; CHECK-NEXT: ret { i64, ptr } [[TMP0]] +; +entry: + %retval = alloca %struct.Foo, align 8 + %val.addr = alloca i32, align 4 + store i32 %val, ptr %val.addr, align 4 + %field1 = getelementptr inbounds %struct.Foo, ptr %retval, i32 0, i32 0 + store i32 2, ptr %field1, align 8 + %field3 = getelementptr inbounds %struct.Foo, ptr %retval, i32 0, i32 2 + store ptr %val.addr, ptr %field3, align 8 + %0 = load { i64, ptr }, ptr %retval, align 8 + ret { i64, ptr } %0 +} + +declare i32 @printf(ptr noundef, ...) #1 + +; Function Attrs: nounwind allocsize(0) +declare noalias ptr @malloc(i64 noundef) #1 +;. +; CHECK: attributes #[[ATTR0]] = { mustprogress nofree norecurse nosync nounwind willreturn memory(none) } +;. +;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line: +; CGSCC: {{.*}} +; TUNIT: {{.*}}