[Attributor] Recompute dependences once a fixpoint is reached

[jdoerfert]

Summary

We use dependences to determine what attributes can be manifested and if
(deep) wrappers are needed. To improve these decisions we allow to
eliminate spurious dependences at the end by running a final iteration
of updates after a fixpoint was reached.

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

 ///
 /// NOTE: The mechanics of adding a new "concrete" abstract attribute are
 ///       described in the file comment.
 struct Attributor {
   /// Constructor
   ///
   /// \param DependenceRecomputeInterval Number of iterations until the
   ///        dependences between abstract attributes are recomputed.
-  Attributor(unsigned DependenceRecomputeInterval)
-      : DependenceRecomputeInterval(DependenceRecomputeInterval) {}
+  /// \param DependenceRecomputeFixpoint Flag to determine if dependences should
+  ///        be recomputed once a fixpoint is reached.
+  Attributor(unsigned DependenceRecomputeInterval,
+             bool DependenceRecomputeFixpoint)
+      : DependenceRecomputeInterval(DependenceRecomputeInterval),
+        DependenceRecomputeFixpoint(DependenceRecomputeFixpoint) {}
 
   /// Destructor
   ~Attributor() { DeleteContainerPointers(AllAbstractAttributes); }
 
   /// 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).
using QueryMapTy =
       DenseMap<AbstractAttribute *, SetVector<AbstractAttribute *>>;
   QueryMapTy QueryMap;
   ///}
 
   /// Number of iterations until the dependences between abstract attributes are
   /// recomputed.
   const unsigned DependenceRecomputeInterval;
 
+  /// Flag to determine if dependences should be recomputed once a fixpoint is
+  /// reached.
+  const bool DependenceRecomputeFixpoint;
+
   /// Check if the state of the abstract attribute \p AA may depend on
   /// information derived from a non-exact definition.
   ///
   /// We cannot use information from non-exact definitions to improve other
   /// definitions as the non-exact ones might be redefined at link-time which
   /// could invalidate the result.
   ///
   /// We can, however, use information from non-exact definitions to improve

llvm/lib/Transforms/IPO/Attributor.cpp

 //
 // This will become more evolved once we perform two interleaved fixpoint
 // iterations: bottom-up and top-down.
 static cl::opt<unsigned>
     MaxFixpointIterations("attributor-max-iterations", cl::Hidden,
                           cl::desc("Maximal number of fixpoint iterations."),
                           cl::init(32));
 
+static cl::opt<unsigned> DepRecFixpoint(
+    "attributor-dependence-recompute-at-fixpoint", cl::Hidden,
+    cl::desc("Recompute dependences after a fixpoint was reached."),
+    cl::init(false));
+
 static cl::opt<unsigned> DepRecInterval(
     "attributor-dependence-recompute-interval", cl::Hidden,
     cl::desc("Number of iterations until dependences are recomputed."),
     cl::init(0));
 
 static cl::opt<bool> DisableAttributor(
     "attributor-disable", cl::Hidden,
     cl::desc("Disable the attributor inter-procedural deduction pass."),
ChangeStatus Attributor::run() {
   // abstract analysis.
 
   unsigned IterationCounter = 1;
 
   SmallVector<AbstractAttribute *, 64> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist;
   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 
+  bool FinishedAtFixpoint = false;
   bool RecomputeDependences = false;
 
   do {
-    LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
-                      << ", Worklist size: " << Worklist.size() << "\n");
+    LLVM_DEBUG({
+      if (FinishedAtFixpoint)
+        dbgs() << "\n\n[Attributor] Final iteration to recompute dependences\n";
+      else
+        dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
+               << ", Worklist size: " << Worklist.size()
+               << ", Recomp. Deps.: " << RecomputeDependences << "\n";
+    });
 
     // If dependences (=QueryMap) are recomputed we have to look at all abstract
     // attributes again, regardless of what changed in the last iteration.
     if (RecomputeDependences) {
       QueryMap.clear();
       ChangedAAs.clear();
       Worklist.insert(AllAbstractAttributes.begin(),
                       AllAbstractAttributes.end());
do {
     ChangedAAs.clear();
 
     // Update all abstract attribute in the work list and record the ones that
     // changed.
     for (AbstractAttribute *AA : Worklist)
       if (AA->update(*this) == ChangeStatus::CHANGED)
         ChangedAAs.push_back(AA);
 
+    if (FinishedAtFixpoint)
+      break;
+
     // Check if we recompute the dependences in the next iteration.
     RecomputeDependences =
         (DependenceRecomputeInterval > 0 &&
          IterationCounter % DependenceRecomputeInterval == 0);
 
     // Reset the work list and repopulate with the changed abstract attributes.
     // Note that dependent ones are added above.
     Worklist.clear();
     if (!RecomputeDependences)
       Worklist.insert(ChangedAAs.begin(), ChangedAAs.end());
 
-  } while (!Worklist.empty() && ++IterationCounter < MaxFixpointIterations);
+    // An optimistic fixpoint was found when the worklist is empty. While we
+    // could simply stop the update loop, we can traverse it once more to remove
+    // stale dependences from the QueryMap. This can be beneficial as it might
+    // prevent deep wrappers for functions with non-exact definitions.
+    if (Worklist.empty()) {
+      FinishedAtFixpoint = true;
+
+      // Check if we run a final iteration to recompute dependences.
+      if (!DependenceRecomputeFixpoint)
+        break;
+
+      RecomputeDependences = true;
+      continue;
+    }
+
+  } while (++IterationCounter < MaxFixpointIterations);
 
   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
                     << IterationCounter << "/" << MaxFixpointIterations
                     << " iterations\n");
 
-  bool FinishedAtFixpoint = Worklist.empty();
-
   // 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];
static bool runAttributorOnModule(Module &M) {
   if (DisableAttributor)
     return false;
 
   LLVM_DEBUG(dbgs() << "[Attributor] Run on module with " << M.size()
                     << " functions.\n");
 
   // Create an Attributor and initially empty information cache that is filled
   // while we identify default attribute opportunities.
-  Attributor A(DepRecInterval);
+  Attributor A(DepRecInterval, DepRecFixpoint);
   InformationCache InfoCache;
 
   for (Function &F : M) {
     // For now we ignore naked and optnone functions as well as declarations.
     if (F.hasFnAttribute(Attribute::Naked) ||
         F.hasFnAttribute(Attribute::OptimizeNone) || F.isDeclaration())
       continue;