[Attributor] Regularly clear dependences to remove spurious ones

[jdoerfert]

Summary

As dependences between abstract attributes can become stale, e.g., if
one was sufficient to imply another one at some point but it has since
been wakened to the point it is not usable for the formerly implied one.
To weed out spurious dependences, and thereby eliminate unneeded
updates, we introduce an option to determine how often the dependence
cache is cleared and recomputed during the fixpoint iteration.

Note that the initial value is set to 0 which disables recomputation.

[nicholas]

Could you include a test with this patch?

[jdoerfert]

In D63315#1542999, @nicholas wrote:

Could you include a test with this patch?

I will construct one as soon as we deduce an actual attribute in the tree (it's impossible without one).
Once the wrappers (D63312) go in there will be more test opportunities to show the interplay, thus fewer dependences cause fewer wrappers.
The same holds for D63317.

[sstefan1]

LGTM. Except for lack of tests

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

 ///       information in the IR.
 ///    b) This avoids reimplementing various kinds of lookups, e.g., to check
 ///       for existing IR attributes, in favor of a single lookups interface
 ///       provided by an abstract attribute subclass.
 ///
 /// 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) {}
+
+  /// 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).
   ///
   /// \Returns CHANGED if the IR was changed, otherwise UNCHANGED.
private:
   /// A map from abstract attributes to the ones that queried them through calls
   /// to the getAAFor<...>(...) method.
   ///{
   using QueryMapTy =
       DenseMap<AbstractAttribute *, SetVector<AbstractAttribute *>>;
   QueryMapTy QueryMap;
   ///}
 
+  /// Number of iterations until the dependences between abstract attributes are
+  /// recomputed.
+  const unsigned DependenceRecomputeInterval;
+
   /// 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> 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."),
     cl::init(false));
 
 static cl::opt<bool> VerifyAttributor(
     "attributor-verify", cl::Hidden,
     cl::desc("Verify the Attributor deduction and "
ChangeStatus Attributor::run() {
   // abstract analysis.
 
   unsigned IterationCounter = 1;
 
   SmallVector<AbstractAttribute *, 64> ChangedAAs;
   SetVector<AbstractAttribute *> Worklist;
   Worklist.insert(AllAbstractAttributes.begin(), AllAbstractAttributes.end());
 
+  bool RecomputeDependences = false;
+
   do {
     LLVM_DEBUG(dbgs() << "\n\n[Attributor] #Iteration: " << IterationCounter
                       << ", Worklist size: " << Worklist.size() << "\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());
+    }
+
     // Add all abstract attributes that are potentially dependent on one that
     // changed to the work list.
     for (AbstractAttribute *ChangedAA : ChangedAAs) {
       auto &QuerriedAAs = QueryMap[ChangedAA];
       Worklist.insert(QuerriedAAs.begin(), QuerriedAAs.end());
     }
 
     // Reset the changed set.
     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);
 
+    // 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);
 
   LLVM_DEBUG(dbgs() << "\n[Attributor] Fixpoint iteration done after: "
                     << IterationCounter << "/" << MaxFixpointIterations
                     << " iterations\n");
 
   bool FinishedAtFixpoint = Worklist.empty();
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;
+  Attributor A(DepRecInterval);
   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;