[WIP][Attributor] Per function iteration and memory tracking.

[kuter]

Summary

This patch makes the attribute iterate on per function (and it's deps)
function basis. This way we don't have to have all AAs in memory at
once.

We do this by having a separate allocator per each function. And attributes that are not in the "Function interface" are kept there.
Function interface attributess are kept alive till the end on the fixpoint iteration.
Seeded attributes are allocated in a user provided allocator.

For doing iteration on each function separately, we track seeded attributes per function first and "bootstrap" them when it is their time.
Functions can still query what they want regardless of which function we are currently iterating in (as long as the queried AA is a interface AA).

[kuter]

I only updated the allow_list.ll. This brakes many tests and in some cases cause invalid IR (assertion gets trigered for a tail call).

I am looking for feedback on this, there is something that I am missing.

[jdoerfert]

I am looking for feedback on this, there is something that I am missing.

Please describe the approach in the commit message with sufficient detail so one does not need to reconstruct what is going on from the code.

llvm/include/llvm/Transforms/IPO/Attributor.h

147

Unrelated.

164

Unrelated.

185

Unrelated.

365

Documentation.

964

Documentation.

[kuter]

Thank you I will update the commit message.

llvm/include/llvm/Transforms/IPO/Attributor.h

164

I had to make this a SmallVector

llvm/lib/Transforms/IPO/Attributor.cpp

1360–1361

This is no longer used.

[sstefan1]

Thanks for the explanation. Since the patch is not small and it is a WIP, can you add some more information about the failing tests? Maybe some specific examples?

Merge checks are helpfull, but I guess if you give few specific examples with problems, it will be easier to focus. WDYT?

[kuter]

In D86587#2238117, @sstefan1 wrote:

Thanks for the explanation. Since the patch is not small and it is a WIP, can you add some more information about the failing tests? Maybe some specific examples?

Merge checks are helpfull, but I guess if you give few specific examples with problems, it will be easier to focus. WDYT?

I wasn't sure of the issue, but I now think that there is a problem with the way things are manifested.
I think there is a problem when we manifest a attribute without manifesting it's deps and this could happen with stub attributes.

We have to create "stub" (the name should change) AAs if we query for a deleted attribute.
I used to not update the "stub" attributes but now I do, maybe we can call them "duplicate".

The reason that we end up querying deleted AAs is because we don't seed every function interface AA.
We can reduce this significantly by changing the order that we iterate on functions.

Or we can also try keeping internal function AAs "alive" until we look at it's every caller(This would also fix the problem with call base context),
Of course this would increase the memory usage. This shouldn't be too hard because of the way I coded things.

llvm/test/Transforms/Attributor/allow_list.ll

85

This could be a example to the manifest problem.

[kuter]

Split unrelated changes to another patch
Handle attibutes that are created after function delete.

llvm/include/llvm/Transforms/IPO/Attributor.h

 ///
 ///{
 enum class ChangeStatus {
   CHANGED,
   UNCHANGED,
 };
 
 ChangeStatus operator|(ChangeStatus l, ChangeStatus r);
+void operator|=(ChangeStatus &l, ChangeStatus r);
 ChangeStatus operator&(ChangeStatus l, ChangeStatus r);
+void operator&=(ChangeStatus &l, ChangeStatus r);
 
 enum class DepClassTy {
   REQUIRED,
   OPTIONAL,
 };
 ///}
 
 /// The data structure for the nodes of a dependency graph
 struct AADepGraphNode {
 public:
   virtual ~AADepGraphNode(){};
   using DepTy = PointerIntPair<AADepGraphNode *, 1>;
 
 protected:
-  /// Set of dependency graph nodes which should be updated if this one
-  /// is updated. The bit encodes if it is optional.
-  TinyPtrVector<DepTy> Deps;
+  /// Set of dependency graph nodes which this one depends on.
+  /// The bit encodes if it is optional.
+  SmallVector<DepTy, 4> Deps;
 
   static AADepGraphNode *DepGetVal(DepTy &DT) { return DT.getPointer(); }
   static AbstractAttribute *DepGetValAA(DepTy &DT) {
     return cast<AbstractAttribute>(DT.getPointer());
   }
 
   operator AbstractAttribute *() { return cast<AbstractAttribute>(this); }
 
 public:
   using iterator =
       mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetVal)>;
   using aaiterator =
       mapped_iterator<TinyPtrVector<DepTy>::iterator, decltype(&DepGetValAA)>;
 
   aaiterator begin() { return aaiterator(Deps.begin(), &DepGetValAA); }
   aaiterator end() { return aaiterator(Deps.end(), &DepGetValAA); }
   iterator child_begin() { return iterator(Deps.begin(), &DepGetVal); }
   iterator child_end() { return iterator(Deps.end(), &DepGetVal); }
 
   virtual void print(raw_ostream &OS) const { OS << "AADepNode Impl\n"; }
-  TinyPtrVector<DepTy> &getDeps() { return Deps; }
+  SmallVector<DepTy, 4> &getDeps() { return Deps; }
 
   friend struct Attributor;
   friend struct AADepGraph;
 };
 
 /// The data structure for the dependency graph
 ///
 /// Note that in this graph if there is an edge from A to B (A -> B),
bool isFnInterfaceKind() const {
     case IRPosition::IRP_RETURNED:
     case IRPosition::IRP_ARGUMENT:
       return true;
     default:
       return false;
     }
   }
 
+  bool isPermenantPosition() const {
+    return isFnInterfaceKind() || isAnyCallSitePosition();
+  }
+
   /// Return the Function surrounding the anchor value.
   Function *getAnchorScope() const {
     Value &V = getAnchorValue();
     if (isa<Function>(V))
       return &cast<Function>(V);
     if (isa<Argument>(V))
       return cast<Argument>(V).getParent();
     if (isa<Instruction>(V))
struct Attributor {
   /// \param Functions The set of functions we are deriving attributes for.
   /// \param InfoCache Cache to hold various information accessible for
   ///                  the abstract attributes.
   /// \param CGUpdater Helper to update an underlying call graph.
   /// \param Allowed If not null, a set limiting the attribute opportunities.
   Attributor(SetVector<Function *> &Functions, InformationCache &InfoCache,
              CallGraphUpdater &CGUpdater,
              DenseSet<const char *> *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();
 
   /// Run the analyses until a fixpoint is reached or enforced (timeout).
   ///
   /// The attributes registered with this Attributor can be used after as long
   /// as the Attributor is not destroyed (it owns the attributes now).
   ///
   /// \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 <typename AAType>
+  AAType &createForPosition(IRPosition IRP, bool isStub = false) {
+    AAType &result = AAType::createForPosition(IRP, *this);
+    AbstractAttribute *AAPtr = static_cast<AbstractAttribute *>(&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
   /// might be anchored at a different position, e.g., the callee if \p IRP is a
   /// call base.
   ///
   /// This method is the only (supported) way an abstract attribute can retrieve
   /// information from another abstract attribute. As an example, take an
struct Attributor {
   /// only the Attributor itself. Initial seeding of AAs can be done via this
   /// function.
   template <typename AAType>
   const AAType &getOrCreateAAFor(const IRPosition &IRP,
                                  const AbstractAttribute *QueryingAA = nullptr,
                                  bool TrackDependence = false,
                                  DepClassTy DepClass = DepClassTy::OPTIONAL,
                                  bool ForceUpdate = false) {
+
     if (AAType *AAPtr = lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence)) {
-      if (ForceUpdate)
+      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<AAType>(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;
     }
 
     registerAA(AA);
 
     // For now we ignore naked and optnone functions.
     bool Invalidate = Allowed && !Allowed->count(&AAType::ID);
     const Function *FnScope = IRP.getAnchorScope();
     if (FnScope)
       Invalidate |= FnScope->hasFnAttribute(Attribute::Naked) ||
                     FnScope->hasFnAttribute(Attribute::OptimizeNone);
 
     // 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<Function *>(FnScope))) {
       AA.getState().indicatePessimisticFixpoint();
       return AA;
     }
 
-    // Allow seeded attributes to declare dependencies.
-    // Remember the seeding state.
-    bool OldSeedingPeriod = SeedingPeriod;
-    SeedingPeriod = false;
-
+    // First updates are delayed for seeded attributes.
+    if (!SeedingPeriod)
       updateAA(AA);
 
-    SeedingPeriod = OldSeedingPeriod;
-
     if (TrackDependence && AA.getState().isValidState())
       recordDependence(AA, const_cast<AbstractAttribute &>(*QueryingAA),
                        DepClass);
     return AA;
   }
 
   /// Return the attribute of \p AAType for \p IRP if existing. This also allows
   /// non-AA users lookup.
assert((QueryingAA || !TrackDependence) &&
            "Cannot track dependences without a QueryingAA!");
 
     // Lookup the abstract attribute of type AAType. If found, return it after
     // registering a dependence of QueryingAA on the one returned attribute.
     AbstractAttribute *AAPtr = AAMap.lookup({&AAType::ID, IRP});
     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<AAType>(IRP, true);
+      AAPtr = static_cast<AbstractAttribute *>(&AA);
+      registerAA(AA);
+
+      initStubAttribute(AAPtr);
+
+      // AAMap[{&AAType::ID, IRP}] = AAPtr;
+    }
+
     AAType *AA = static_cast<AAType *>(AAPtr);
 
     // Do not register a dependence on an attribute with an invalid state.
     if (TrackDependence && AA->getState().isValidState())
       recordDependence(*AA, const_cast<AbstractAttribute &>(*QueryingAA),
                        DepClass);
     return AA;
   }
template <typename AAType> AAType &registerAA(AAType &AA) {
     // Put the attribute in the lookup map structure and the container we use to
     // keep track of all attributes.
     const IRPosition &IRP = AA.getIRPosition();
     AbstractAttribute *&AAPtr = AAMap[{&AAType::ID, IRP}];
 
     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)));
 
     return AA;
   }
 
   /// Return the internal information cache.
   InformationCache &getInfoCache() { return InfoCache; }
struct Attributor {
   /// to memory present in the information cache and return true if \p Pred
   /// holds on all of them.
   bool checkForAllReadWriteInstructions(function_ref<bool(Instruction &)> Pred,
                                         AbstractAttribute &QueryingAA);
 
   /// 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.
   ///
   /// If the maximum iteration count is reached, This method will
   /// indicate pessimistic fixpoint on attributes that transitively depend
   /// on attributes that were scheduled for an update.
   void runTillFixpoint();
private:
   /// was altered.
   ChangeStatus
   rewriteFunctionSignatures(SmallPtrSetImpl<Function *> &ModifiedFns);
 
   /// Check if the Attribute \p AA should be seeded.
   /// 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.
   ///{
   using AAMapKeyTy = std::pair<const char *, IRPosition>;
   DenseMap<AAMapKeyTy, AbstractAttribute *> AAMap;
   ///}
 
private:
 
   /// Invoke instructions with at least a single dead successor block.
   SmallVector<WeakVH, 16> InvokeWithDeadSuccessor;
 
   /// Wheather attributes are being `seeded`, always false after ::run function
   /// gets called \see getOrCreateAAFor.
   bool SeedingPeriod = true;
 
+  /// TODO: Document
+  bool InitPeriod = false;
+
   /// Functions, blocks, and instructions we delete after manifest is done.
   ///
   ///{
   SmallPtrSet<Function *, 8> ToBeDeletedFunctions;
   SmallPtrSet<BasicBlock *, 8> ToBeDeletedBlocks;
   SmallDenseSet<WeakVH, 8> 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<Function *, BumpPtrAllocator> 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<Function *, 16> 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<Function *, SmallVector<AbstractAttribute *, 16>>
+      AliveAttributesPerFunction;
+
+  /// Always equals to AliveAttributesPerFunction[CurrentFn]
+  SmallVector<AbstractAttribute *, 16> *AliveAttributesForCurrentFunction;
+
+  /// Attributes that where deleted that we had to recreate.
+  SmallPtrSet<AbstractAttribute *, 16> StubAttributes;
+
+  // Non Seeded permenant AAs. We have to deconstruct these since we own them.
+  SmallVector<AbstractAttribute *, 16> NonSeededPermenant;
+  ///}
+
+  /// Attributes per function that where explicitly requested from outise
+  /// of the attributor
+  DenseMap<Function *, SmallSetVector<AbstractAttribute *, 16>>
+      SeededAttributesPerFunction;
+
   friend AADepGraph;
 };
 
 /// An interface to query the internal state of an abstract attribute.
 ///
 /// The abstract state is a minimal interface that allows the Attributor to
 /// communicate with the abstract attributes about their internal state without
 /// enforcing or exposing implementation details, e.g., the (existence of an)
struct AbstractAttribute : public IRPosition, public AADepGraphNode {
   /// This function is used to identify if an \p DGN is of type
   /// AbstractAttribute so that the dyn_cast and cast can use such information
   /// to cast an AADepGraphNode to an AbstractAttribute.
   ///
   /// We eagerly return true here because all AADepGraphNodes except for the
   /// 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;
   virtual const StateType &getState() const = 0;
 
   /// Return an IR position, see struct IRPosition.
   const IRPosition &getIRPosition() const { return *this; };
   IRPosition &getIRPosition() { return *this; };
struct AbstractAttribute : public IRPosition, public AADepGraphNode {
   /// This function should return the address of the ID of the AbstractAttribute
   virtual const char *getIdAddr() const = 0;
   ///}
 
   /// Allow the Attributor access to the protected methods.
   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,
   /// otherwise it delegates to `AbstractAttribute::updateImpl`.
   ///
   /// \Return CHANGED if the internal state changed, otherwise UNCHANGED.
   ChangeStatus update(Attributor &A);
 
protected:
   /// The actual update/transfer function which has to be implemented by the
   /// derived classes.
   ///
   /// If it is called, the environment has changed and we have to determine if
   /// the current information is still valid or adjust it otherwise.
   ///
   /// \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.
 ///
 ///{
 raw_ostream &operator<<(raw_ostream &OS, const AbstractAttribute &AA);
 raw_ostream &operator<<(raw_ostream &OS, ChangeStatus S);
 raw_ostream &operator<<(raw_ostream &OS, IRPosition::Kind);

llvm/lib/Transforms/IPO/Attributor.cpp

static cl::opt<bool> PrintDependencies("attributor-print-dep", cl::Hidden,
                                        cl::init(false));
 
 /// Logic operators for the change status enum class.
 ///
 ///{
 ChangeStatus llvm::operator|(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::CHANGED ? l : r;
 }
+
+void llvm::operator|=(ChangeStatus &l, ChangeStatus r) { l = l | r; }
+
 ChangeStatus llvm::operator&(ChangeStatus l, ChangeStatus r) {
   return l == ChangeStatus::UNCHANGED ? l : r;
 }
+
+void llvm::operator&=(ChangeStatus &l, ChangeStatus r) { l = l & r; }
+
 ///}
 
 /// Return true if \p New is equal or worse than \p Old.
 static bool isEqualOrWorse(const Attribute &New, const Attribute &Old) {
   if (!Old.isIntAttribute())
     return true;
 
   return Old.getValueAsInt() >= New.getValueAsInt();
if (CI && CI->getType() != V.getType()) {
     return nullptr;
   }
   if (CI)
     recordDependence(ValueSimplifyAA, AA, DepClassTy::OPTIONAL);
   return CI;
 }
 
 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<AbstractAttribute>(DepAA.getPointer());
-    AA->~AbstractAttribute();
-  }
 }
 
 bool Attributor::isAssumedDead(const AbstractAttribute &AA,
                                const AAIsDead *FnLivenessAA,
                                bool CheckBBLivenessOnly, DepClassTy DepClass) {
   const IRPosition &IRP = AA.getIRPosition();
   if (!Functions.count(IRP.getAnchorScope()))
     return false;
do {
     // to run updates.
     for (unsigned u = 0; u < InvalidAAs.size(); ++u) {
       AbstractAttribute *InvalidAA = InvalidAAs[u];
 
       // Check the dependences to fast track invalidation.
       LLVM_DEBUG(dbgs() << "[Attributor] InvalidAA: " << *InvalidAA << " has "
                         << InvalidAA->Deps.size()
                         << " required & optional dependences\n");
+
       while (!InvalidAA->Deps.empty()) {
         const auto &Dep = InvalidAA->Deps.back();
         InvalidAA->Deps.pop_back();
         AbstractAttribute *DepAA = cast<AbstractAttribute>(Dep.getPointer());
+
         if (Dep.getInt() == unsigned(DepClassTy::OPTIONAL)) {
           Worklist.insert(DepAA);
           continue;
         }
         DepAA->getState().indicatePessimisticFixpoint();
         assert(DepAA->getState().isAtFixpoint() && "Expected fixpoint state!");
         if (!DepAA->getState().isValidState())
           InvalidAAs.insert(DepAA);
         else
           ChangedAAs.push_back(DepAA);
       }
     }
 
     // Add all abstract attributes that are potentially dependent on one that
     // changed to the work list.
     for (AbstractAttribute *ChangedAA : ChangedAAs)
       while (!ChangedAA->Deps.empty()) {
-        Worklist.insert(
-            cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
+        AbstractAttribute *AA =
+            cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer());
+        Worklist.insert(AA);
+
         ChangedAA->Deps.pop_back();
       }
 
     LLVM_DEBUG(dbgs() << "[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist+Dependent size: " << Worklist.size()
                       << "\n");
 
     // Reset the changed and invalid set.
void Attributor::runTillFixpoint() {
 
   } while (!Worklist.empty() && (IterationCounter++ < MaxFixpointIterations ||
                                  VerifyMaxFixpointIterations));
 
   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
                     << IterationCounter << "/" << MaxFixpointIterations
                     << " iterations\n");
 
+  SmallVector<AbstractAttribute *, 32> 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<AbstractAttribute *, 32> 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();
 
       NumAttributesTimedOut++;
     }
 
     while (!ChangedAA->Deps.empty()) {
-      ChangedAAs.push_back(
+      ToInvalidate.push_back(
           cast<AbstractAttribute>(ChangedAA->Deps.back().getPointer()));
       ChangedAA->Deps.pop_back();
     }
   }
 
   LLVM_DEBUG({
     if (!Visited.empty())
       dbgs() << "\n[Attributor] Finalized " << Visited.size()
              << " 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() {
   TimeTraceScope TimeScope("Attributor::manifestAttributes");
   size_t NumFinalAAs = DG.SyntheticRoot.Deps.size();
 
   unsigned NumManifested = 0;
   unsigned NumAtFixpoint = 0;
   ChangeStatus ManifestChange = ChangeStatus::UNCHANGED;
-  for (auto &DepAA : DG.SyntheticRoot.Deps) {
-    AbstractAttribute *AA = cast<AbstractAttribute>(DepAA.getPointer());
+
+  for (auto AA : *AliveAttributesForCurrentFunction) {
     AbstractState &State = AA->getState();
 
     // If there is not already a fixpoint reached, we can now take the
     // optimistic state. This is correct because we enforced a pessimistic one
     // on abstract attributes that were transitively dependent on a changed one
     // already above.
     if (!State.isAtFixpoint())
       State.indicateOptimisticFixpoint();
 
+    // Don't manifest Stub Attributes.
+    if (StubAttributes.count(AA))
+      continue;
+
     // If the state is invalid, we do not try to manifest it.
     if (!State.isValidState())
       continue;
 
     // Skip dead code.
     if (isAssumedDead(*AA, nullptr, /* CheckBBLivenessOnly */ true))
       continue;
     // Manifest the state and record if we changed the IR.
#ifdef EXPENSIVE_CHECKS
   }
 #endif
 
   return ManifestChange;
 }
 
 ChangeStatus Attributor::run() {
   TimeTraceScope TimeScope("Attributor::run");
-
   SeedingPeriod = false;
+  ChangeStatus Result = ChangeStatus::UNCHANGED;
+
+  auto RunOnAttributes =
+      [&](Function *Fn,
+          SmallSetVector<AbstractAttribute *, 16> &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.
+        InitPeriod = true;
+        for (AbstractAttribute *AA : AttributesToSeed)
+          AA->doInitialize(*this);
+        InitPeriod = false;
+
+        DG.SyntheticRoot.Deps.assign(AttributesToSeed.begin(),
+                                     AttributesToSeed.end());
+
         runTillFixpoint();
 
-  // dump graphs on demand
         if (DumpDepGraph)
           DG.dumpGraph();
 
         if (ViewDepGraph)
           DG.viewGraph();
 
         if (PrintDependencies)
           DG.print();
 
-  ChangeStatus ManifestChange = manifestAttributes();
-  ChangeStatus CleanupChange = cleanupIR();
-  return ManifestChange | CleanupChange;
+        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;
+
+    LLVM_DEBUG(dbgs() << "[Attributor] Seeding function: "
+                      << SeedPoint.first->getName() << "\n");
+
+    RunOnAttributes(SeedPoint.first, SeedPoint.second);
+  }
+
+  // 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]);
+
+  // 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.
   DependenceVector DV;
   DependenceStack.push_back(&DV);
 
   auto &AAState = AA.getState();
   ChangeStatus CS = ChangeStatus::UNCHANGED;
#ifndef NDEBUG
   Function *Fn = AA.getAnchorScope();
   if (FunctionSeedAllowList.size() != 0 && Fn)
     Result &= std::count(FunctionSeedAllowList.begin(),
                          FunctionSeedAllowList.end(), Fn->getName());
 #endif
   return Result;
 }
 
+bool Attributor::isAttributeSeeded(AbstractAttribute &AA) {
+  return SeededAttributesPerFunction[AA.getAnchorScope()].count(&AA);
+}
+
 ChangeStatus Attributor::rewriteFunctionSignatures(
     SmallPtrSetImpl<Function *> &ModifiedFns) {
   ChangeStatus Changed = ChangeStatus::UNCHANGED;
 
   for (auto &It : ArgumentReplacementMap) {
     Function *OldFn = It.getFirst();
 
     // Deleted functions do not require rewrites.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp

std::string AAMemoryLocation::getMemoryLocationsAsStr(
   S.pop_back();
   return S;
 }
 
 namespace {
 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<VALID_STATE>(); ++u)
       AccessKind2Accesses[u] = nullptr;
   }
 
   ~AAMemoryLocationImpl() {
     // The AccessSets are allocated via a BumpPtrAllocator, we call
     // the destructor manually.
     for (unsigned u = 0; u < llvm::CTLog2<VALID_STATE>(); ++u)

 // follow the naming scheme.
 
 #define SWITCH_PK_INV(CLASS, PK, POS_NAME)                                     \
   case IRPosition::PK:                                                         \
     llvm_unreachable("Cannot create " #CLASS " for a " POS_NAME " position!");
 
 #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;
 
 #define CREATE_FUNCTION_ABSTRACT_ATTRIBUTE_FOR_POSITION(CLASS)                 \
   CLASS &CLASS::createForPosition(const IRPosition &IRP, Attributor &A) {      \
     CLASS *AA = nullptr;                                                       \
     switch (IRP.getPositionKind()) {                                           \
       SWITCH_PK_INV(CLASS, IRP_INVALID, "invalid")                             \

llvm/lib/Transforms/IPO/OpenMPOpt.cpp

AAICVTracker &AAICVTracker::createForPosition(const IRPosition &IRP,
   case IRPosition::IRP_FLOAT:
   case IRPosition::IRP_ARGUMENT:
   case IRPosition::IRP_RETURNED:
   case IRPosition::IRP_CALL_SITE_RETURNED:
   case IRPosition::IRP_CALL_SITE_ARGUMENT:
   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;
   }
 
   return *AA;
 }
 
 PreservedAnalyses OpenMPOptPass::run(LazyCallGraph::SCC &C,
                                      CGSCCAnalysisManager &AM,

llvm/test/Transforms/Attributor/allow_list.ll

 define internal i32 @range_test(i32 %a) #0 {
 ; CHECK_DISABLED: Function Attrs: noinline nounwind uwtable
 ; CHECK_DISABLED-LABEL: define {{[^@]+}}@range_test
 ; CHECK_DISABLED-SAME: (i32 [[A:%.*]])
 ; CHECK_DISABLED-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[A]], 100
 ; CHECK_DISABLED-NEXT:    [[TMP2:%.*]] = zext i1 [[TMP1]] to i32
 ; CHECK_DISABLED-NEXT:    ret i32 [[TMP2]]
 ;
+; CHECK_ENABLED: Function Attrs: noinline nounwind uwtable
+; CHECK_ENABLED-LABEL: define {{[^@]+}}@range_test
+; CHECK_ENABLED-SAME: (i32 [[A:%.*]])
+; CHECK_ENABLED-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[A]], 100
+; CHECK_ENABLED-NEXT:    [[TMP2:%.*]] = zext i1 [[TMP1]] to i32
+; CHECK_ENABLED-NEXT:    ret i32 [[TMP2]]
+;
 ; CHECK_DISABLED_FUNCTION: Function Attrs: noinline nounwind uwtable
 ; CHECK_DISABLED_FUNCTION-LABEL: define {{[^@]+}}@range_test
 ; CHECK_DISABLED_FUNCTION-SAME: (i32 [[A:%.*]])
 ; 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
+; CHECK_ENABLED_FUNCTION: Function Attrs: noinline nounwind uwtable
+; CHECK_ENABLED_FUNCTION-LABEL: define {{[^@]+}}@range_test
+; CHECK_ENABLED_FUNCTION-SAME: (i32 [[A:%.*]])
+; CHECK_ENABLED_FUNCTION-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[A]], 100
+; CHECK_ENABLED_FUNCTION-NEXT:    [[TMP2:%.*]] = zext i1 [[TMP1]] to i32
+; CHECK_ENABLED_FUNCTION-NEXT:    ret i32 [[TMP2]]
 ;
   %1 = icmp sgt i32 %a, 100
   %2 = zext i1 %1 to i32
   ret i32 %2
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @range_use1() #0 {
 ; CHECK_DISABLED: Function Attrs: noinline nounwind uwtable
 ; CHECK_DISABLED-LABEL: define {{[^@]+}}@range_use1()
 ; CHECK_DISABLED-NEXT:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_DISABLED-NEXT:    ret i32 [[TMP1]]
 ;
 ; CHECK_ENABLED: Function Attrs: noinline nounwind uwtable
 ; CHECK_ENABLED-LABEL: define {{[^@]+}}@range_use1()
+; CHECK_ENABLED-NEXT:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_ENABLED-NEXT:    ret i32 1
 ;
 ; CHECK_DISABLED_FUNCTION: Function Attrs: noinline nounwind uwtable
 ; CHECK_DISABLED_FUNCTION-LABEL: define {{[^@]+}}@range_use1()
 ; CHECK_DISABLED_FUNCTION-NEXT:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_DISABLED_FUNCTION-NEXT:    ret i32 [[TMP1]]
 ;
 ; CHECK_ENABLED_FUNCTION: Function Attrs: nofree noinline nosync nounwind readnone uwtable willreturn
 ; CHECK_ENABLED_FUNCTION-LABEL: define {{[^@]+}}@range_use1()
 ; CHECK_ENABLED_FUNCTION-NEXT:    ret i32 1
 ;
   %1 = call i32 @range_test(i32 123)
   ret i32 %1
 }
 
 ; Function Attrs: nounwind uwtable
 define i32 @range_use2() #0 {
 ; CHECK_DISABLED: Function Attrs: noinline nounwind uwtable
 ; CHECK_DISABLED-LABEL: define {{[^@]+}}@range_use2()
 ; CHECK_DISABLED-NEXT:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_DISABLED-NEXT:    ret i32 [[TMP1]]
 ;
 ; CHECK_ENABLED: Function Attrs: noinline nounwind uwtable
 ; CHECK_ENABLED-LABEL: define {{[^@]+}}@range_use2()
+; CHECK_ENABLED-NEXT:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_ENABLED-NEXT:    ret i32 1
 ;
 ; CHECK_DISABLED_FUNCTION: Function Attrs: noinline nounwind uwtable
 ; CHECK_DISABLED_FUNCTION-LABEL: define {{[^@]+}}@range_use2()
 ; CHECK_DISABLED_FUNCTION-NEXT:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_DISABLED_FUNCTION-NEXT:    ret i32 [[TMP1]]
 ;
 ; 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:    [[TMP1:%.*]] = call i32 @range_test(i32 123)
 ; CHECK_ENABLED_FUNCTION-NEXT:    ret i32 [[TMP1]]
 ;
   %1 = call i32 @range_test(i32 123)
   ret i32 %1
 }
 
 attributes #0 = { nounwind uwtable noinline }