[LegacyPM] Update InversedLastUser on the fly. NFC.

[foad]

Summary

This speeds up setLastUser enough to give a 5% to 10% speed up on
trivial invocations of opt and llc, as measured by:

perf stat -r 100 opt -S -o /dev/null -O3 /dev/null
perf stat -r 100 llc -march=amdgcn /dev/null -filetype null

Don't dump last use information unless -debug-pass=Details to avoid
printing lots of spam that will break some existing lit tests. Before
this patch, dumping last use information was broken anyway, because it
used InversedLastUser before it had been populated.

[serge-sans-paille]

As the state of LastUser are closely tied, it would make sense to encapsulate the two members in a class that would maintain the consistency of these two states, so that the two new operations recordNewUser(Pass, User) and updatelastUser(Pass, User) become explicit ?

[foad]

In D92309#2422720, @serge-sans-paille wrote:

As the state of LastUser are closely tied, it would make sense to encapsulate the two members in a class that would maintain the consistency of these two states, so that the two new operations recordNewUser(Pass, User) and updatelastUser(Pass, User) become explicit ?

I think the best way to do that would be using a generic bidirectional map like https://theboostcpplibraries.com/boost.bimap. But there is no bimap in include/llvm/ADT/ yet and I'm not sure my C++ is good enough to write it myself.

[bjope]

llvm/include/llvm/IR/LegacyPassManagers.h

234

I suggest adding a comment here that the intention is to always keep InversedLastUser in sync with this map.

238

As above, I suggest adding a comment here that this map should be updated whenever LastUser is updated to keep them in sync.

[foad]

Rebase. Add comments.

[bjope]

LGTM

[foad]

In D92309#2509390, @bjope wrote:

LGTM

Thanks. This patch depends on D92308. Without D92308, this patch would add lots of extra lines to the output of opt -debug-pass=Structure, which breaks various tests in test/CodeGen and test/Other.

[bjope]

In D92309#2509524, @foad wrote:

In D92309#2509390, @bjope wrote:

LGTM

Thanks. This patch depends on D92308. Without D92308, this patch would add lots of extra lines to the output of opt -debug-pass=Structure, which breaks various tests in test/CodeGen and test/Other.

Maybe an alternative to D92308 would be to bail out from dumpLastUses if (PassDebugging < Details). I.e. to limit the dumping of last uses to -debug-pass=Details.
I do not think it is that harmful to get more printouts when using Details level for debug-pass. And this way one can get the detailed information when debugging the pass manager on detailed level, while not impacting tests using -debug-pass=Structure etc.

(if that sounds good, then I guess you can even squeeze that into this revision)

[foad]

Don't dump last uses unless -debug-pass=Details.

[foad]

In D92309#2509618, @bjope wrote:

In D92309#2509524, @foad wrote:

In D92309#2509390, @bjope wrote:

LGTM

Thanks. This patch depends on D92308. Without D92308, this patch would add lots of extra lines to the output of opt -debug-pass=Structure, which breaks various tests in test/CodeGen and test/Other.

Maybe an alternative to D92308 would be to bail out from dumpLastUses if (PassDebugging < Details). I.e. to limit the dumping of last uses to -debug-pass=Details.
I do not think it is that harmful to get more printouts when using Details level for debug-pass. And this way one can get the detailed information when debugging the pass manager on detailed level, while not impacting tests using -debug-pass=Structure etc.

(if that sounds good, then I guess you can even squeeze that into this revision)

Good idea!

[bjope]

Still LGTM

llvm/include/llvm/IR/LegacyPassManagers.h

 
 private:
   /// Collection of pass managers that are not directly maintained
   /// by this pass manager
   SmallVector<PMDataManager *, 8> IndirectPassManagers;
 
   // Map to keep track of last user of the analysis pass.
   // LastUser->second is the last user of Lastuser->first.
+  // This is kept in sync with InversedLastUser.
   DenseMap<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
-  // LastUser map.
+  // This is kept in sync with LastUser.
   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;
 
 

llvm/lib/IR/LegacyPassManager.cpp

 /// Set pass P as the last user of the given analysis passes.
 void
 PMTopLevelManager::setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P) {
   unsigned PDepth = 0;
   if (P->getResolver())
     PDepth = P->getResolver()->getPMDataManager().getDepth();
 
   for (Pass *AP : AnalysisPasses) {
-    LastUser[AP] = P;
+    // Record P as the new last user of AP.
+    auto &LastUserOfAP = LastUser[AP];
+    if (LastUserOfAP)
+      InversedLastUser[LastUserOfAP].erase(AP);
+    LastUserOfAP = P;
+    InversedLastUser[P].insert(AP);
 
     if (P == AP)
       continue;
 
     // Update the last users of passes that are required transitive by AP.
     AnalysisUsage *AnUsage = findAnalysisUsage(AP);
     const AnalysisUsage::VectorType &IDs = AnUsage->getRequiredTransitiveSet();
     SmallVector<Pass *, 12> LastUses;
for (Pass *AP : AnalysisPasses) {
 
     setLastUser(LastUses, P);
 
     // If this pass has a corresponding pass manager, push higher level
     // analysis to this pass manager.
     if (P->getResolver())
       setLastUser(LastPMUses, P->getResolver()->getPMDataManager().getAsPass());
 
-
     // If AP is the last user of other passes then make P last user of
     // such passes.
-    for (auto &LU : LastUser) {
-      if (LU.second == AP)
-        LU.second = P;
-    }
+    auto &LastUsedByAP = InversedLastUser[AP];
+    for (Pass *L : LastUsedByAP)
+      LastUser[L] = P;
+    InversedLastUser[P].insert(LastUsedByAP.begin(), LastUsedByAP.end());
+    LastUsedByAP.clear();
   }
 }
 
 /// Collect passes whose last user is P
 void PMTopLevelManager::collectLastUses(SmallVectorImpl<Pass *> &LastUses,
                                         Pass *P) {
   auto DMI = InversedLastUser.find(P);
   if (DMI == InversedLastUser.end())

 
 void PMTopLevelManager::initializeAllAnalysisInfo() {
   for (PMDataManager *PM : PassManagers)
     PM->initializeAnalysisInfo();
 
   // Initailize other pass managers
   for (PMDataManager *IPM : IndirectPassManagers)
     IPM->initializeAnalysisInfo();
-
-  for (auto LU : LastUser) {
-    SmallPtrSet<Pass *, 8> &L = InversedLastUser[LU.second];
-    L.insert(LU.first);
-  }
 }
 
 /// Destructor
 PMTopLevelManager::~PMTopLevelManager() {
   for (PMDataManager *PM : PassManagers)
     delete PM;
 
   for (ImmutablePass *P : ImmutablePasses)
Pass *PMDataManager::findAnalysisPass(AnalysisID AID, bool SearchParent) {
   if (SearchParent)
     return TPM->findAnalysisPass(AID);
 
   return nullptr;
 }
 
 // Print list of passes that are last used by P.
 void PMDataManager::dumpLastUses(Pass *P, unsigned Offset) const{
+  if (PassDebugging < Details)
+    return;
 
   SmallVector<Pass *, 12> LUses;
 
   // If this is a on the fly manager then it does not have TPM.
   if (!TPM)
     return;
 
   TPM->collectLastUses(LUses, P);