[PassManager] Tuning Memory Usage of AnalysisUsage

[reames]

Summary

This patch isn't read for submission yet; it's a vehicle for discussion.

By tuning the initialize sizes of the SmallVector's used by AnalysisUsage, I can cut the memory allocated for all AnalysisUsage objects in the legacy pass manager by nearly 40kb on -O3. This is over half (original 77kb, new 38kb) of the memory allocated from that site (reporting via massif). The peak memory usage is reduced from 762 KB to 716 KB.

I picked these thresholds somewhat at random. Given the result, I'm really questioning whether small vector is even the right data structure for this case. Does anyone have any data on the actual numbers of dependencies? I can measure, but I thought I'd ask first.

Chandler - I haven't examined how AnalysisUsage is used by the new pass manager. If I tune for performance/memory in the old pass manager, am I going to possible make things worse for the new one? What do I need to watch out for in expected usage patterns?

[chandlerc]

LGTM

I agree that SmallVector seems ... dubious here. But it might not be worth it to try to change that. I like your change. I'd re-balance the numbers a bit differently based on my intuition (see the comment below) but I have no data. Also feel free to rebalance them based on actual data if you would like. Feel free to commit any updated numbers without pre-commit review also. =] Seems totally straightforward.

include/llvm/IR/LegacyPassManagers.h

267–270 ↗

(On Diff #41928)

Alternatively, you could use:

for (AnalysisUsage::VectorType &Vec : ...

include/llvm/PassAnalysisSupport.h

43–46 ↗

(On Diff #41928)

FWIW, these don't match my basic expectations. I would expect Preserved to be the largest, followed by Required. They'll probably be close. Both RequiredTransitive and Used should be quite rare. I would go for 8, 8, 1, 1.

[reames]

Here's the raw data for a single O3 pass pipeline. Each line is a unique instance of AnalysisUsage.
#Required #Transitive #Preserved #Used

0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
2 0 1 0
2 0 17 0
4 0 17 0
1 0 0 0
1 0 0 0
2 0 0 0
0 0 0 0
4 0 18 0
1 0 0 6
2 0 0 0
0 0 0 0
2 0 1 0
2 0 0 0
1 0 1 0
1 0 0 0
4 0 1 0
3 0 1 0
3 0 17 0
3 0 1 0
2 0 17 0
4 0 17 0
2 0 2 0
1 0 1 0
1 0 1 0
0 0 17 0
5 0 9 0
1 0 0 0
3 0 9 0
2 0 21 0
1 0 0 0
6 0 23 0
6 0 6 0
5 0 20 0
4 4 0 0
8 0 9 0
5 0 6 0
7 0 6 0
2 0 18 0
5 0 2 0
3 2 0 0
5 0 18 0
1 0 1 0
1 0 17 0
2 0 16 0
4 0 19 0
11 0 5 0
2 0 0 0
4 0 0 0
6 0 18 0
3 0 19 0

Observations:
#Used is always (?) zero
#Required is < 8
#Transative is < 2
#Preserved is bimodal

Reasonable numbers appear to be:
Required: 8
Transitive: 2
Preserved: 2
Used: 0

[chandlerc]

Those numbers make sense to me. Feel free to submit with them.

FWIW, the zero is because "Used" is only needed in rare circumstances. I'm not completely surprised that the O3 pipeline doesn't trigger it, although I thought it did...

llvm/trunk/include/llvm/PassAnalysisSupport.h

 /// that the pass REQUIRES (must be available when the pass runs), REQUIRES
 /// TRANSITIVE (must be available throughout the lifetime of the pass), and
 /// analyses that the pass PRESERVES (the pass does not invalidate the results
 /// of these analyses).  This information is provided by a pass to the Pass
 /// infrastructure through the getAnalysisUsage virtual function.
 ///
 class AnalysisUsage {
 public:
-  typedef SmallVector<AnalysisID, 32> VectorType;
+  typedef SmallVectorImpl<AnalysisID> VectorType;
 
 private:
   /// Sets of analyses required and preserved by a pass
-  VectorType Required, RequiredTransitive, Preserved, Used;
+  // TODO: It's not clear that SmallVector is an appropriate data structure for
+  // this usecase.  The sizes were picked to minimize wasted space, but are
+  // otherwise fairly meaningless.
+  SmallVector<AnalysisID, 8> Required;
+  SmallVector<AnalysisID, 2> RequiredTransitive;
+  SmallVector<AnalysisID, 2> Preserved;
+  SmallVector<AnalysisID, 0> Used;
   bool PreservesAll;
 
 public:
   AnalysisUsage() : PreservesAll(false) {}
 
   ///@{
   /// Add the specified ID to the required set of the usage info for a pass.
   AnalysisUsage &addRequiredID(const void *ID);