use a MapVector for pass manage LastUser

[airlied]

Summary

with AMDGPU we end up having 208 passes to initialise, this
makes the loop over LastUser in PMTopLevelManager::setLastUser
appear quite high on the CPU usage. Since we have to initialise
the context and pass for every shader due to threading, we
see this quite often.

In a test of initing a bunch of shaders and exiting, this takes
the runtime down from 2.3s to 2.2s since the MapVector has
more efficient iterating.

[chandlerc]

I really don't think this is the right approach.

First, this is fundamentally a more expensive data structure than DenseMap. I'm honestly surprised that *any* query pattern is actually faster with it, but I can understand why your particular one happens to be faster. But it does make every other code path a bit slower. It doesn't really seem like the right tradeoff for all of LLVM, especially given that this doesn't even help *that* much.

If you want to fix this, you should fix the bad algorithm in setLastUser. We already have an inverse map, so there should be some way that simply doesn't iterate over the entire thing in this way.

But honestly, I'm not sure its worth spending a lot of time tuning this. If you see lots of overhead due to these kinds of pass management infrastructure, I would *strongly* suggest working on moving to the new pass manager. It fundamentally doesn't have these pitfalls. So far no one has stepped forward to work on making this happen for the code generator, but it really does need to happen...

[airlied]

Thanks for the review, Chandler,

Yes it does appear as if the amdgpu usage pattern is a bit special here, I've spent some time getting patches into the mesa side to avoid recreating the pass managers so often and it removes the needs for this.

Dave.

[foad]

If you want to fix this, you should fix the bad algorithm in setLastUser. We already have an inverse map, so there should be some way that simply doesn't iterate over the entire thing in this way.

I've done this in D92309.

include/llvm/IR/LegacyPassManagers.h

 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/Pass.h"
 #include <vector>
 

 
   // Map to keep track of last user of the analysis pass.
   // LastUser->second is the last user of Lastuser->first.
-  DenseMap<Pass *, Pass *> LastUser;
+  MapVector<Pass *, Pass *> LastUser;
 
   // Map to keep track of passes that are last used by a pass.
   // This inverse map is initialized at PM->run() based on