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
@@ -2808,6 +2808,20 @@
   ///    in the `updateImpl` method.
   virtual void initialize(Attributor &A) {}
 
+  /// A query AA is always scheduled as long as we do updates because it does
+  /// lazy computation that cannot be determined to be done from the outside.
+  /// To determine if we are done, query AAs also need to overwrite the
+  /// `hasNewQueries` interface.
+  virtual bool isQueryAA() const { return false; }
+
+  /// Returns true if a query AA has received new queries since the last update
+  /// call. This means we cannot stop iterating as the new queries have been
+  /// answered optimistically and we do not know if their state is fix yet.
+  /// Only needs to be implemented by query AAs (see `isQueryAA`).
+  virtual bool hasNewQueries() const {
+    llvm_unreachable("A query AA needs to overwrite this function!");
+  }
+
   /// Return the internal abstract state for inspection.
   virtual StateType &getState() = 0;
   virtual const StateType &getState() const = 0;
@@ -4615,6 +4629,9 @@
 
   AAFunctionReachability(const IRPosition &IRP, Attributor &A) : Base(IRP) {}
 
+  /// See AbstractAttribute::isQueryAA.
+  bool isQueryAA() const override { return true; }
+
   /// If the function represented by this possition can reach \p Fn.
   virtual bool canReach(Attributor &A, const Function &Fn) const = 0;
 
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
@@ -1438,10 +1438,12 @@
   else
     MaxFixedPointIterations = SetFixpointIterations;
 
+  SmallVector<AbstractAttribute *> QueryAAs;
   SmallVector<AbstractAttribute *, 32> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist, InvalidAAs;
   Worklist.insert(DG.SyntheticRoot.begin(), DG.SyntheticRoot.end());
 
+  bool DoneIterating;
   do {
     // Remember the size to determine new attributes.
     size_t NumAAs = DG.SyntheticRoot.Deps.size();
@@ -1496,9 +1498,12 @@
     // changed.
     for (AbstractAttribute *AA : Worklist) {
       const auto &AAState = AA->getState();
-      if (!AAState.isAtFixpoint())
+      if (!AAState.isAtFixpoint()) {
         if (updateAA(*AA) == ChangeStatus::CHANGED)
           ChangedAAs.push_back(AA);
+        else if (AA->isQueryAA())
+          QueryAAs.push_back(AA);
+      }
 
       // Use the InvalidAAs vector to propagate invalid states fast transitively
       // without requiring updates.
@@ -1514,10 +1519,18 @@
     // Reset the work list and repopulate with the changed abstract attributes.
     // Note that dependent ones are added above.
     Worklist.clear();
+    Worklist.insert(QueryAAs.begin(), QueryAAs.end());
     Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
+    QueryAAs.clear();
+
+    bool HasChangedAAs = !ChangedAAs.empty();
+    DoneIterating = !HasChangedAAs &&
+                    !llvm::any_of(QueryAAs, [](AbstractAttribute *QueryAA) {
+                      return QueryAA->hasNewQueries();
+                    });
 
-  } while (!Worklist.empty() && (IterationCounter++ < MaxFixedPointIterations ||
-                                 VerifyMaxFixpointIterations));
+  } while (!DoneIterating && (IterationCounter++ < MaxFixedPointIterations ||
+                              VerifyMaxFixpointIterations));
 
   if (IterationCounter > MaxFixedPointIterations && !Worklist.empty()) {
     auto Remark = [&](OptimizationRemarkMissed ORM) {
@@ -1975,11 +1988,13 @@
   auto &AAState = AA.getState();
   ChangeStatus CS = ChangeStatus::UNCHANGED;
   bool UsedAssumedInformation = false;
-  if (!isAssumedDead(AA, nullptr, UsedAssumedInformation,
-                     /* CheckBBLivenessOnly */ true))
+  bool IsQueryAA = AA.isQueryAA();
+
+  if (IsQueryAA || !isAssumedDead(AA, nullptr, UsedAssumedInformation,
+                                  /* CheckBBLivenessOnly */ true))
     CS = AA.update(*this);
 
-  if (DV.empty()) {
+  if (!IsQueryAA && DV.empty()) {
     // If the attribute did not query any non-fix information, the state
     // will not change and we can indicate that right away.
     AAState.indicateOptimisticFixpoint();
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
@@ -9582,11 +9582,14 @@
     /// If we can reach a function with a call to a unknown function we assume
     /// that we can reach any function.
     bool CanReachUnknownCallee = false;
+
+    bool HasNewQueries = false;
   };
 
   struct QueryResolver : public QuerySet {
     ChangeStatus update(Attributor &A, const AAFunctionReachability &AA,
                         ArrayRef<const AACallEdges *> AAEdgesList) {
+      HasNewQueries = false;
       ChangeStatus Change = ChangeStatus::UNCHANGED;
 
       for (auto *AAEdges : AAEdgesList) {
@@ -9614,6 +9617,8 @@
       if (Cached.hasValue())
         return Cached.getValue();
 
+      HasNewQueries = true;
+
       // We need to assume that this function can't reach Fn to prevent
       // an infinite loop if this function is recursive.
       Unreachable.insert(&Fn);
@@ -9726,6 +9731,15 @@
   AAFunctionReachabilityFunction(const IRPosition &IRP, Attributor &A)
       : AAFunctionReachability(IRP, A) {}
 
+  bool hasNewQueries() const override {
+    if (WholeFunction.HasNewQueries)
+      return true;
+    for (const auto &It : CBQueries)
+      if (It.second.HasNewQueries)
+        return true;
+    return false;
+  }
+
   bool canReach(Attributor &A, const Function &Fn) const override {
     const AACallEdges &AAEdges =
         A.getAAFor<AACallEdges>(*this, getIRPosition(), DepClassTy::REQUIRED);