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 @@ -159,9 +159,9 @@ using DepTy = PointerIntPair; protected: - /// Set of dependency graph nodes which should be updated if this one - /// is updated. The bit encodes if it is optional. - TinyPtrVector Deps; + /// Set of dependency graph nodes which this one depends on. + /// The bit encodes if it is optional. + SmallVector Deps; static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); } static AbstractAttribute *DepGetValAA(DepTy &DT) { @@ -182,7 +182,7 @@ iterator child_end() { return iterator(Deps.end(), &DepGetVal); } virtual void print(raw_ostream &OS) const { OS << "AADepNode Impl\n"; } - TinyPtrVector &getDeps() { return Deps; } + SmallVector &getDeps() { return Deps; } friend struct Attributor; friend struct AADepGraph; @@ -360,6 +360,10 @@ } } + bool isPermenantPosition() const { + return isFnInterfaceKind() || isAnyCallSitePosition(); + } + /// Return the Function surrounding the anchor value. Function *getAnchorScope() const { Value &V = getAnchorValue(); @@ -912,8 +916,8 @@ Attributor(SetVector &Functions, InformationCache &InfoCache, CallGraphUpdater &CGUpdater, DenseSet *Allowed = nullptr) - : Allocator(InfoCache.Allocator), Functions(Functions), - InfoCache(InfoCache), CGUpdater(CGUpdater), Allowed(Allowed) {} + : Functions(Functions), InfoCache(InfoCache), CGUpdater(CGUpdater), + Allowed(Allowed), SeedAllocator(InfoCache.Allocator) {} ~Attributor(); @@ -925,6 +929,40 @@ /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED. ChangeStatus run(); + /// Get the correct allocator to create the AA + BumpPtrAllocator &getAllocatorForPosition(IRPosition IRP) { + // Seeded AAs can outlive the Attributor. Use the user provided allocator. + if (SeedingPeriod) + return SeedAllocator; + + Function *Fn = IRP.getAnchorScope(); + + // If we have deleted the function for this attribute, we are creating a + // stub use the permenant allocator + if (FreedFunctions.count(Fn)) + return PermenantAllocator; + + // Let functions interface attributes live past the life time of the + // function. + if (IRP.isPermenantPosition()) + return PermenantAllocator; + + return FunctionInternalAllocator[Fn]; + } + + /// Initialize a stub AA \see lookupAAFor + void initStubAttribute(AbstractAttribute *AA); + + template + AAType &createForPosition(IRPosition IRP, bool isStub = false) { + AAType &result = AAType::createForPosition(IRP, *this); + AbstractAttribute *AAPtr = static_cast(&result); + if (isStub || IRP.isPermenantPosition()) + NonSeededPermenant.push_back(AAPtr); + + return result; + } + /// Lookup an abstract attribute of type \p AAType at position \p IRP. While /// no abstract attribute is found equivalent positions are checked, see /// SubsumingPositionIterator. Thus, the returned abstract attribute @@ -977,17 +1015,23 @@ bool TrackDependence = false, DepClassTy DepClass = DepClassTy::OPTIONAL, bool ForceUpdate = false) { + if (AAType *AAPtr = lookupAAFor(IRP, QueryingAA, TrackDependence)) { - if (ForceUpdate) - updateAA(*AAPtr); + bool OldInit = AAPtr->DidInitialize; + if (!SeedingPeriod) { + AAPtr->doInitialize(*this); + if (ForceUpdate || !OldInit) + updateAA(*AAPtr); + } return *AAPtr; } // No matching attribute found, create one. - // Use the static create method. - auto &AA = AAType::createForPosition(IRP, *this); + auto &AA = createForPosition(IRP); // If we are currenty seeding attributes, enforce seeding rules. + // We are doing this pre registery on purpose, if it gets queried by another + // AA, it will be initialized. if (SeedingPeriod && !shouldSeedAttribute(AA)) { AA.getState().indicatePessimisticFixpoint(); return AA; @@ -1005,31 +1049,29 @@ // Bootstrap the new attribute with an initial update to propagate // information, e.g., function -> call site. If it is not on a given // Allowed we will not perform updates at all. + // AA is regitered, it will always be pessimistic. if (Invalidate) { AA.getState().indicatePessimisticFixpoint(); return AA; } - { - TimeTraceScope TimeScope(AA.getName() + "::initialize"); - AA.initialize(*this); - } + // We have to delay the initialization. Since some AAs query other + // attributes in the initialize function. + if (!SeedingPeriod) + AA.doInitialize(*this); + // We can initialize (=look at) code outside the current function set but // not call update because that would again spawn new abstract attributes in // potentially unconnected code regions (=SCCs). + // AA is initialized, it will retain the information collected from the IR. if (FnScope && !Functions.count(const_cast(FnScope))) { AA.getState().indicatePessimisticFixpoint(); return AA; } - // Allow seeded attributes to declare dependencies. - // Remember the seeding state. - bool OldSeedingPeriod = SeedingPeriod; - SeedingPeriod = false; - - updateAA(AA); - - SeedingPeriod = OldSeedingPeriod; + // First updates are delayed for seeded attributes. + if (!SeedingPeriod) + updateAA(AA); if (TrackDependence && AA.getState().isValidState()) recordDependence(AA, const_cast(*QueryingAA), @@ -1056,6 +1098,23 @@ if (!AAPtr) return nullptr; + // Asking for non seeded interface AAs can result in the querying of freed + // AAs. + // Don't create a stub if this already a stub attribute. + if (!IRP.isPermenantPosition() && + FreedFunctions.count(IRP.getAnchorScope()) && + !StubAttributes.count(AAPtr)) { + AAMap.erase({&AAType::ID, IRP}); + + auto &AA = createForPosition(IRP, true); + AAPtr = static_cast(&AA); + registerAA(AA); + + initStubAttribute(AAPtr); + + // AAMap[{&AAType::ID, IRP}] = AAPtr; + } + AAType *AA = static_cast(AAPtr); // Do not register a dependence on an attribute with an invalid state. @@ -1098,6 +1157,10 @@ assert(!AAPtr && "Attribute already in map!"); AAPtr = &AA; + if (SeedingPeriod) + SeededAttributesPerFunction[AA.getAnchorScope()].insert(AA); + AliveAttributesPerFunction[AA.getAnchorScope()].push_back(AA); + DG.SyntheticRoot.Deps.push_back( AADepGraphNode::DepTy(&AA, unsigned(DepClassTy::REQUIRED))); @@ -1412,9 +1475,6 @@ /// Return the data layout associated with the anchor scope. const DataLayout &getDataLayout() const { return InfoCache.DL; } - /// The allocator used to allocate memory, e.g. for `AbstractAttribute`s. - BumpPtrAllocator &Allocator; - private: /// This method will do fixpoint iteration until fixpoint or the /// maximum iteration count is reached. @@ -1462,6 +1522,7 @@ /// See getOrCreateAAFor. bool shouldSeedAttribute(AbstractAttribute &AA); + bool isAttributeSeeded(AbstractAttribute &AA); /// A nested map to lookup abstract attributes based on the argument position /// on the outer level, and the addresses of the static member (AAType::ID) on /// the inner level. @@ -1536,6 +1597,54 @@ SmallDenseSet ToBeDeletedInsts; ///} + /// AA memory managment. + ///{ + /// The allocators used to allocate memory, e.g. for `AbstractAttribute`s. + /// The specific allocator to be used is chosen by the + /// getAllocatorForPosition function + + /// The seed allocator is provided by the user. + /// Attributes that are here kept alive as long the user wan't them to be. + BumpPtrAllocator &SeedAllocator; + + /// The allocator that is used for interface AAs and AAs that we don't + /// know which function it is from. + /// These are saved until the run function is over. + BumpPtrAllocator PermenantAllocator; + + /// The allocators per function that are used for the allocation of the + /// AAs. + DenseMap FunctionInternalAllocator; + + /// The set of functions that we have freed. This is different from the + /// functions that we have not yet seeded or created a allocator for. + SmallPtrSet FreedFunctions; + + /// Current function that we are iterating on. + Function *CurrentFn; + + /// Attributes per function that are alive. + /// We need this for manifesting and deconstructing AAs once we are done + /// with them. + /// Permenant attributes are alive until the end, even if they are not listed. + DenseMap> + AliveAttributesPerFunction; + + /// Always equals to AliveAttributesPerFunction[CurrentFn] + SmallVector *AliveAttributesForCurrentFunction; + + /// Attributes that where deleted that we had to recreate. + SmallPtrSet StubAttributes; + + // Non Seeded permenant AAs. We have to deconstruct these since we own them. + SmallVector NonSeededPermenant; + ///} + + /// Attributes per function that where explicitly requested from outise + /// of the attributor + DenseMap> + SeededAttributesPerFunction; + friend AADepGraph; }; @@ -2125,15 +2234,16 @@ /// Synthethis Node are of type AbstractAttribute static bool classof(const AADepGraphNode *DGN) { return true; } - /// Initialize the state with the information in the Attributor \p A. - /// - /// This function is called by the Attributor once all abstract attributes - /// have been identified. It can and shall be used for task like: - /// - identify existing knowledge in the IR and use it for the "known state" - /// - perform any work that is not going to change over time, e.g., determine - /// a subset of the IR, or attributes in-flight, that have to be looked at - /// in the `updateImpl` method. - virtual void initialize(Attributor &A) {} + /// Make sure that the attribute have initialized. + /// TODO: rename this function to initialize and rename the current init + /// function to doInitialize. + void doInitialize(Attributor &A) { + if (!DidInitialize) { + DidInitialize = true; + TimeTraceScope TimeScope(getName() + "::initialize"); + initialize(A); + } + } /// Return the internal abstract state for inspection. virtual StateType &getState() = 0; @@ -2163,6 +2273,16 @@ friend struct Attributor; protected: + /// Initialize the state with the information in the Attributor \p A. + /// + /// This function is called by the Attributor once all abstract attributes + /// have been identified. It can and shall be used for task like: + /// - identify existing knowledge in the IR and use it for the "known state" + /// - perform any work that is not going to change over time, e.g., determine + /// a subset of the IR, or attributes in-flight, that have to be looked at + /// in the `updateImpl` method. + virtual void initialize(Attributor &A) {} + /// Hook for the Attributor to trigger an update of the internal state. /// /// If this attribute is already fixed, this method will return UNCHANGED, @@ -2194,6 +2314,9 @@ /// /// \Return CHANGED if the internal state changed, otherwise UNCHANGED. virtual ChangeStatus updateImpl(Attributor &A) = 0; + + /// Did we call ::initilize before. + bool DidInitialize = false; }; /// Forward declarations of output streams for debug purposes. 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 @@ -546,12 +546,6 @@ } Attributor::~Attributor() { - // The abstract attributes are allocated via the BumpPtrAllocator Allocator, - // thus we cannot delete them. We can, and want to, destruct them though. - for (auto &DepAA : DG.SyntheticRoot.Deps) { - AbstractAttribute *AA = cast(DepAA.getPointer()); - AA->~AbstractAttribute(); - } } bool Attributor::isAssumedDead(const AbstractAttribute &AA, @@ -1050,18 +1044,24 @@ << IterationCounter << "/" << MaxFixpointIterations << " iterations\n"); + SmallVector ToInvalidate; + for (AbstractAttribute *AA : ChangedAAs) + if (AA->getAnchorScope() == CurrentFn) + ToInvalidate.push_back(AA); + // Reset abstract arguments not settled in a sound fixpoint by now. This // happens when we stopped the fixpoint iteration early. Note that only the // ones marked as "changed" *and* the ones transitively depending on them // need to be reverted to a pessimistic state. Others might not be in a // fixpoint state but we can use the optimistic results for them anyway. SmallPtrSet Visited; - for (unsigned u = 0; u < ChangedAAs.size(); u++) { - AbstractAttribute *ChangedAA = ChangedAAs[u]; + for (unsigned u = 0; u < ToInvalidate.size(); u++) { + AbstractAttribute *ChangedAA = ToInvalidate[u]; if (!Visited.insert(ChangedAA).second) continue; AbstractState &State = ChangedAA->getState(); + // If the AA is in a different function then don't invalide it. if (!State.isAtFixpoint()) { State.indicatePessimisticFixpoint(); @@ -1069,7 +1069,7 @@ } while (!ChangedAA->Deps.empty()) { - ChangedAAs.push_back( + ToInvalidate.push_back( cast(ChangedAA->Deps.back().getPointer())); ChangedAA->Deps.pop_back(); } @@ -1081,14 +1081,27 @@ << " abstract attributes.\n"; }); - if (VerifyMaxFixpointIterations && - IterationCounter != MaxFixpointIterations) { - errs() << "\n[Attributor] Fixpoint iteration done after: " - << IterationCounter << "/" << MaxFixpointIterations - << " iterations\n"; - llvm_unreachable("The fixpoint was not reached with exactly the number of " - "specified iterations!"); - } + // FIXME + // if (VerifyMaxFixpointIterations && + // IterationCounter != MaxFixpointIterations) { + // errs() << "\n[Attributor] Fixpoint iteration done after: " + // << IterationCounter << "/" << MaxFixpointIterations + // << " iterations\n"; + // llvm_unreachable("The fixpoint was not reached with exactly the number of + // " + // "specified iterations!"); + // } +} + +void Attributor::initStubAttribute(AbstractAttribute *AA) { + StubAttributes.insert(AA); + AA->doInitialize(*this); + + LLVM_DEBUG(dbgs() << "[Attributor] WARNING: A stub attribute for a deleted " + "attribute is created: " + << *AA << "\n"); + + updateAA(*AA); } ChangeStatus Attributor::manifestAttributes() { @@ -1098,8 +1111,8 @@ unsigned NumManifested = 0; unsigned NumAtFixpoint = 0; ChangeStatus ManifestChange = ChangeStatus::UNCHANGED; - for (auto &DepAA : DG.SyntheticRoot.Deps) { - AbstractAttribute *AA = cast(DepAA.getPointer()); + + for (auto AA : *AliveAttributesForCurrentFunction) { AbstractState &State = AA->getState(); // If there is not already a fixpoint reached, we can now take the @@ -1325,26 +1338,97 @@ ChangeStatus Attributor::run() { TimeTraceScope TimeScope("Attributor::run"); - SeedingPeriod = false; - runTillFixpoint(); + ChangeStatus Result = ChangeStatus::UNCHANGED; + + auto RunOnAttributes = + [&](Function *Fn, + SmallSetVector &AttributesToSeed) { + AliveAttributesForCurrentFunction = &AliveAttributesPerFunction[Fn]; + CurrentFn = Fn; + + // We have to delay the initialization as init can cause AAs to be + // queried, and in some cases using the result of AAs that did not + // recive a update on creation can cause problems. + for (AbstractAttribute *AA : AttributesToSeed) + AA->doInitialize(*this); + + DG.SyntheticRoot.Deps.assign(AttributesToSeed.begin(), + AttributesToSeed.end()); + + runTillFixpoint(); + + if (DumpDepGraph) + DG.dumpGraph(); + + if (ViewDepGraph) + DG.viewGraph(); + + if (PrintDependencies) + DG.print(); + + Result |= manifestAttributes(); + + for (AbstractAttribute *AA : *AliveAttributesForCurrentFunction) { + if (!isAttributeSeeded(*AA) && !AA->isPermenantPosition()) { + // If this a internal AA, deconstruct it. + AA->~AbstractAttribute(); + } else { + // if this a interface or seeded AA just purge it's deps. + // NOTE: We might want to handle seeded AAs differently. + AA->Deps.clear(); + } + } + + AliveAttributesPerFunction.erase(Fn); + FunctionInternalAllocator.erase(Fn); + FreedFunctions.insert(Fn); + }; + + for (auto SeedPoint : SeededAttributesPerFunction) { + /// Skip the nullptr, it will be handled later. + if (SeedPoint.first == nullptr) + continue; - // dump graphs on demand - if (DumpDepGraph) - DG.dumpGraph(); + LLVM_DEBUG(dbgs() << "[Attributor] Seeding function: " + << SeedPoint.first->getName() << "\n"); - if (ViewDepGraph) - DG.viewGraph(); + RunOnAttributes(SeedPoint.first, SeedPoint.second); + } + + // Manifest attributes that we missed. + for (auto &AttributeSet : AliveAttributesPerFunction) { + if (AttributeSet.second.size() == 0) + continue; + + AliveAttributesForCurrentFunction = &AttributeSet.second; + Result |= manifestAttributes(); + AliveAttributesForCurrentFunction->clear(); + } - if (PrintDependencies) - DG.print(); + // The AAs that we can't identify a function for are handled here. + // They stay in the memory for the lifetime of the run function so handle we + // handle them at the end + // The Default seeding should not cause any of these AAs + RunOnAttributes(nullptr, SeededAttributesPerFunction[nullptr]); - ChangeStatus ManifestChange = manifestAttributes(); - ChangeStatus CleanupChange = cleanupIR(); - return ManifestChange | CleanupChange; + // Actually make the changes. + Result |= cleanupIR(); + + // We don't need AAs that where not seeded anymore. + for (auto AA : NonSeededPermenant) + AA->~AbstractAttribute(); + + PermenantAllocator.Reset(); + + return Result; } ChangeStatus Attributor::updateAA(AbstractAttribute &AA) { + // Don't update this AA if we already deleted it's function. + if (FreedFunctions.count(AA.getAnchorScope()) && !StubAttributes.count(&AA)) + return ChangeStatus::UNCHANGED; + TimeTraceScope TimeScope(AA.getName() + "::updateAA"); // Use a new dependence vector for this update. @@ -1596,6 +1680,10 @@ return Result; } +bool Attributor::isAttributeSeeded(AbstractAttribute &AA) { + return SeededAttributesPerFunction[AA.getAnchorScope()].count(&AA); +} + ChangeStatus Attributor::rewriteFunctionSignatures( SmallPtrSetImpl &ModifiedFns) { ChangeStatus Changed = ChangeStatus::UNCHANGED; 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 @@ -6258,7 +6258,7 @@ struct AAMemoryLocationImpl : public AAMemoryLocation { AAMemoryLocationImpl(const IRPosition &IRP, Attributor &A) - : AAMemoryLocation(IRP, A), Allocator(A.Allocator) { + : AAMemoryLocation(IRP, A), Allocator(A.getAllocatorForPosition(IRP)) { for (unsigned u = 0; u < llvm::CTLog2(); ++u) AccessKind2Accesses[u] = nullptr; } @@ -7853,7 +7853,7 @@ #define SWITCH_PK_CREATE(CLASS, IRP, PK, SUFFIX) \ case IRPosition::PK: \ - AA = new (A.Allocator) CLASS##SUFFIX(IRP, A); \ + AA = new (A.getAllocatorForPosition(IRP)) CLASS##SUFFIX(IRP, A); \ ++NumAAs; \ break; diff --git a/llvm/lib/Transforms/IPO/OpenMPOpt.cpp b/llvm/lib/Transforms/IPO/OpenMPOpt.cpp --- a/llvm/lib/Transforms/IPO/OpenMPOpt.cpp +++ b/llvm/lib/Transforms/IPO/OpenMPOpt.cpp @@ -1422,7 +1422,7 @@ case IRPosition::IRP_CALL_SITE: llvm_unreachable("ICVTracker can only be created for function position!"); case IRPosition::IRP_FUNCTION: - AA = new (A.Allocator) AAICVTrackerFunction(IRP, A); + AA = new (A.getAllocatorForPosition(IRP)) AAICVTrackerFunction(IRP, A); break; } diff --git a/llvm/test/Transforms/Attributor/allow_list.ll b/llvm/test/Transforms/Attributor/allow_list.ll --- a/llvm/test/Transforms/Attributor/allow_list.ll +++ b/llvm/test/Transforms/Attributor/allow_list.ll @@ -27,10 +27,6 @@ ; CHECK_DISABLED_FUNCTION-NEXT: [[TMP1:%.*]] = icmp sgt i32 [[A]], 100 ; CHECK_DISABLED_FUNCTION-NEXT: [[TMP2:%.*]] = zext i1 [[TMP1]] to i32 ; CHECK_DISABLED_FUNCTION-NEXT: ret i32 [[TMP2]] -; -; CHECK_ENABLED_FUNCTION: Function Attrs: noinline nounwind readnone uwtable -; CHECK_ENABLED_FUNCTION-LABEL: define {{[^@]+}}@range_test() -; CHECK_ENABLED_FUNCTION-NEXT: ret i32 1 ; %1 = icmp sgt i32 %a, 100 %2 = zext i1 %1 to i32 @@ -79,8 +75,7 @@ ; ; CHECK_ENABLED_FUNCTION: Function Attrs: noinline nounwind uwtable ; CHECK_ENABLED_FUNCTION-LABEL: define {{[^@]+}}@range_use2() -; CHECK_ENABLED_FUNCTION-NEXT: [[TMP1:%.*]] = call i32 @range_test() -; CHECK_ENABLED_FUNCTION-NEXT: ret i32 [[TMP1]] +; CHECK_ENABLED_FUNCTION-NEXT: ret i32 1 ; %1 = call i32 @range_test(i32 123) ret i32 %1