[LegacyPassManager] Reduce memory usage for AnalysisUsage

[reames]

Summary

The LegacyPassManager was storing an instance of AnalysisUsage for each instance of each pass. In practice, most instances of a single pass class share the same dependencies. We can't rely on this because passes can (and some do) have dynamic dependencies based on instance options.

We can exploit the likely commonality by uniqueing the usage information after querying the pass, but before storing it into the pass manager. This greatly reduces memory consumption by the AnalysisUsage objects. For a long pass pipeline, I measured a decrease in memory consumption for this storage of about 50%. I have not measured on the default O3 pipeline, but I suspect it will see some benefit as well since many passes are repeated (e.g. InstCombine).

I believe this enhancement does not apply to the new pass manager; please correct me if I'm wrong.

Once this is in, I also plan to re-examine the use of SmallVectors in AnalysisUsage and their default size of 32 elements. Given most passes have only a few direct dependencies, this seems likely to be rather wasteful of memory.

[chandlerc]

This is a really nice improvement. Minor adjustment below is my only real suggestion.

lib/IR/LegacyPassManager.cpp

582–587 ↗

(On Diff #40200)

Since we build this completely each time, the folding set machinery isn't really hepling much. Maybe just provide a hash_value overload and use a SmallSet? Should be able to either delegate to the vector's hash_value or use hash_combine_range.

(This isn't because they're that much simpler, I'd just rather move everything away from folding sets where reasonable.)

594 ↗

(On Diff #40200)

As sympathetic as I am to using multiple returns like this in an immediately called lamda, I find it quite confusing. Especially with the auto type on the variable.

Fortunately, I think with a set, the code to do this without a lambda shouldn't be onerous at all.

[reames]

lib/IR/LegacyPassManager.cpp

582–587 ↗

(On Diff #40200)

I actually started with trying to use DenseSet, but the choice of empty and tombstone keys was non-obvious. I'm not familiar enough with the AU data structure to identify values which could never occur.

SmallSet is probably a bad choice. I have no evidence the set of AU values is small, only that its elements are heavily reused. Picking a good small size would be tricky. In particular, the small size which works for O2 is probably not the one which works for my out of tree pipeline and vice versa.

I would prefer to use the folding set here. I believe it is the appropriate data structure choice and the usage pattern closely maps usages elsewhere (e.g. SCEV).

594 ↗

(On Diff #40200)

I slightly disagree, but minor. Will fix in an update version shortly.

[reames]

Remove lambda per Chandler's comment.

[reames]

ping - Chandler?

[chandlerc]

Mostly minor changes. I'm not thrilled with the folding set stuff still, but i don't want to spend more time tweaking the legacy pass manager code honestly. I'm not even thrilled by this complexity going in, but I understand why it's so significant for your use case.

include/llvm/IR/LegacyPassManagers.h

257–258 ↗

(On Diff #40342)

nit: Just make this a struct to avoid needing to specify "public" everywhere.

259–260 ↗

(On Diff #40342)

This would make a bit more sense below, where we process the arrays?

273–274 ↗

(On Diff #40342)

I would prefer to not add to the Profile overload set since that gets called at a distance in the folding set code. Instead, I'd rather make it clearly an implementation detail. Unless I missed something and it's actually used elsewhere?

ProfileImpl would be fine. Maybe even a local lambda?

Actually, what about writing the above as:

for (auto &Vec : {AU.getRequiredSet(), AU.getRequiredTransitiveSet(), ...}) {
  ID.AddInteger(Vec.size());
  for (AnalysisID AID : Vec)
    ID.AddPointer(AID);
}

I think we're finally at a point where MSVC's initializer list support is up to this style of usage.

lib/IR/LegacyPassManager.cpp

595 ↗

(On Diff #40342)

Add a message here? Maybe "found a null pointer in cached analysis usages" or somesuch?

llvm/trunk/include/llvm/IR/LegacyPassManagers.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_LEGACYPASSMANAGERS_H
 #define LLVM_IR_LEGACYPASSMANAGERS_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Pass.h"
 #include <map>
 #include <vector>
 
 //===----------------------------------------------------------------------===//
 // Overview:
private:
   DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser;
 
   /// Immutable passes are managed by top level manager.
   SmallVector<ImmutablePass *, 16> ImmutablePasses;
 
   /// Map from ID to immutable passes.
   SmallDenseMap<AnalysisID, ImmutablePass *, 8> ImmutablePassMap;
 
-  DenseMap<Pass *, AnalysisUsage *> AnUsageMap;
+
+  /// A wrapper around AnalysisUsage for the purpose of uniqueing.  The wrapper
+  /// is used to avoid needing to make AnalysisUsage itself a folding set node.
+  struct AUFoldingSetNode : public FoldingSetNode {
+    AnalysisUsage AU;
+    AUFoldingSetNode(const AnalysisUsage &AU) : AU(AU) {}
+    void Profile(FoldingSetNodeID &ID) const {
+      Profile(ID, AU);
+    }
+    static void Profile(FoldingSetNodeID &ID, const AnalysisUsage &AU) {
+      // TODO: We could consider sorting the dependency arrays within the
+      // AnalysisUsage (since they are conceptually unordered).
+      ID.AddBoolean(AU.getPreservesAll());
+      for (auto &Vec : {AU.getRequiredSet(), AU.getRequiredTransitiveSet(),
+            AU.getPreservedSet(), AU.getUsedSet()}) {
+        ID.AddInteger(Vec.size());
+        for(AnalysisID AID : Vec)
+          ID.AddPointer(AID);
+      }
+    }
+  };
+
+  // Contains all of the unique combinations of AnalysisUsage.  This is helpful
+  // when we have multiple instances of the same pass since they'll usually
+  // have the same analysis usage and can share storage.
+  FoldingSet<AUFoldingSetNode> UniqueAnalysisUsages;
+  
+  // Allocator used for allocating UAFoldingSetNodes.  This handles deletion of
+  // all allocated nodes in one fell swoop.
+  BumpPtrAllocator AUFoldingSetNodeAllocator;
+  
+  // Maps from a pass to it's associated entry in UniqueAnalysisUsages.  Does
+  // not own the storage associated with either key or value.. 
+  DenseMap<Pass *, AnalysisUsage*> AnUsageMap;
 
   /// Collection of PassInfo objects found via analysis IDs and in this top
   /// level manager. This is used to memoize queries to the pass registry.
   /// FIXME: This is an egregious hack because querying the pass registry is
   /// either slow or racy.
   mutable DenseMap<AnalysisID, const PassInfo *> AnalysisPassInfos;
 };
 

llvm/trunk/lib/IR/LegacyPassManager.cpp

void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
   for (Pass *LUP : LU) {
     LastUses.push_back(LUP);
   }
 
 }
 
 AnalysisUsage *PMTopLevelManager::findAnalysisUsage(Pass *P) {
   AnalysisUsage *AnUsage = nullptr;
-  DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.find(P);
+  auto DMI = AnUsageMap.find(P);
   if (DMI != AnUsageMap.end())
     AnUsage = DMI->second;
   else {
-    AnUsage = new AnalysisUsage();
-    P->getAnalysisUsage(*AnUsage);
-    AnUsageMap[P] = AnUsage;
+    // Look up the analysis usage from the pass instance (different instances
+    // of the same pass can produce different results), but unique the
+    // resulting object to reduce memory usage.  This helps to greatly reduce
+    // memory usage when we have many instances of only a few pass types
+    // (e.g. instcombine, simplifycfg, etc...) which tend to share a fixed set
+    // of dependencies.
+    AnalysisUsage AU;
+    P->getAnalysisUsage(AU);
+    
+    AUFoldingSetNode* Node = nullptr;
+    FoldingSetNodeID ID;
+    AUFoldingSetNode::Profile(ID, AU);
+    void *IP = nullptr;
+    if (auto *N = UniqueAnalysisUsages.FindNodeOrInsertPos(ID, IP))
+      Node = N;
+    else {
+      Node = new (AUFoldingSetNodeAllocator) AUFoldingSetNode(AU);
+      UniqueAnalysisUsages.InsertNode(Node, IP);
+    }
+    assert(Node && "cached analysis usage must be non null");
+
+    AnUsageMap[P] = &Node->AU;
+    AnUsage = &Node->AU;;
   }
   return AnUsage;
 }
 
 /// Schedule pass P for execution. Make sure that passes required by
 /// P are run before P is run. Update analysis info maintained by
 /// the manager. Remove dead passes. This is a recursive function.
 void PMTopLevelManager::schedulePass(Pass *P) {

 PMTopLevelManager::~PMTopLevelManager() {
   for (SmallVectorImpl<PMDataManager *>::iterator I = PassManagers.begin(),
          E = PassManagers.end(); I != E; ++I)
     delete *I;
 
   for (SmallVectorImpl<ImmutablePass *>::iterator
          I = ImmutablePasses.begin(), E = ImmutablePasses.end(); I != E; ++I)
     delete *I;
-
-  for (DenseMap<Pass *, AnalysisUsage *>::iterator DMI = AnUsageMap.begin(),
-         DME = AnUsageMap.end(); DMI != DME; ++DMI)
-    delete DMI->second;
 }
 
 //===----------------------------------------------------------------------===//
 // PMDataManager implementation
 
 /// Augement AvailableAnalysis by adding analysis made available by pass P.
 void PMDataManager::recordAvailableAnalysis(Pass *P) {
   AnalysisID PI = P->getPassID();