[GlobalISel][NFC]: Add interface to reserve memory in GISelWorklist

[aditya_nandakumar]

Summary

Added an interface to specify how many elements to reserve to GISelWorkList.
This change resulted in a 12% compile time improvement in the combiner pass(es), and 2.5% improvement in the legalizer.

[arsenm]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

46

size_t

lib/CodeGen/GlobalISel/Combiner.cpp

114

size_t

115

It seems weird to me to scan over the function just to estimate this. Can you start with some large constant and increase with each block as it's seen?

[paquette]

lib/CodeGen/GlobalISel/Combiner.cpp

114

MFSize?

115

MF.getInstructionCount() does this

[aditya_nandakumar]

lib/CodeGen/GlobalISel/Combiner.cpp

115

What according to you is a large constant? Also could you elaborate on what you mean by increase with each block as it's seen? IIUC are you suggesting NumBlocks * some_large_constant?

[aditya_nandakumar]

lib/CodeGen/GlobalISel/Combiner.cpp

114

Thanks. Will update.

115

Didn't know it existed. Will change to it.

[arsenm]

lib/CodeGen/GlobalISel/Combiner.cpp

115

Well both the number of blocks and count of instructions in the block are scans of the entire linked lists IIRC. You could update the estimate at the end of the loop when you can know how many instructions are around. I don't know if it matters. If I were to randomly pick an initial number I would guess thousands?

[aditya_nandakumar]

lib/CodeGen/GlobalISel/Combiner.cpp

115

I just realized that in the combiner it's silly that we're recomputing this for every loop - I'm not sure if your original comment was addressing that or in general about traversing linked lists even once (I assumed it was the latter). I also don't think it matters if we care about the exact size during each iteration - if we're doing the full list traversal, I'll definitely move this out of the main loop and use an old estimate.
Alternatively I can use something like 4096 * getNumBlocks() if that works better.. I can run some numbers to see how this performs.

[aemerson]

lib/CodeGen/GlobalISel/Combiner.cpp

115

I think that ilist's size() is a linear time linked list walk.

[aditya_nandakumar]

Changed the strategy to fix problems of DenseMap migration as well as silly traversals of MachineFunction just to estimate the size.

[arsenm]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

86

This is redundant

103

Ditto

[paquette]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

70–72

Don't need braces here.

88–89

I think that in standard LLVM code style, the return should be on a newline. (Or, that's what clang-format does on my end anyway)

if (It == WorklistMap.end())
    return;

[aditya_nandakumar]

Removed redundant NDEBUG checks.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

88–89

Clang format does not do that for me.

[aditya_nandakumar]

Addressed some formatting related feedback.

[aemerson]

LGTM, thanks.

[aditya_nandakumar]

r354093

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

 //
 // FIXME: Does it make sense to factor out common code with the
 // instcombinerWorkList?
 template<unsigned N>
 class GISelWorkList {
   SmallVector<MachineInstr *, N> Worklist;
   DenseMap<MachineInstr *, unsigned> WorklistMap;
 
+#ifndef NDEBUG
+  bool Finalized = true;
+#endif
+
 public:
   GISelWorkList() : WorklistMap(N) {}
 
   bool empty() const { return WorklistMap.empty(); }
 
   unsigned size() const { return WorklistMap.size(); }
 
+  // Since we don't know ahead of time how many instructions we're going to add
+  // to the worklist, and migrating densemap's elements is quite expensive
+  // everytime we resize, only insert to the smallvector (typically during the
+  // initial phase of populating lists). Before the worklist can be used,
+  // finalize should be called. Also assert with NDEBUG if list is ever used
+  // without finalizing. Note that unlike insert, we won't check for duplicates
+  // - so the ideal place to use this is during the initial prepopulating phase
+  // of most passes.
+  void deferred_insert(MachineInstr *I) {
+    Worklist.push_back(I);
+#ifndef NDEBUG
+    Finalized = false;
+#endif
+  }
+
+  // This should only be called when using deferred_insert.
+  // This asserts that the WorklistMap is empty, and then
+  // inserts all the elements in the Worklist into the map.
+  // It also asserts if there are any duplicate elements found.
+  void finalize() {
+    assert(WorklistMap.empty() && "Expecting empty worklistmap");
+    if (Worklist.size() > N)
+      WorklistMap.reserve(Worklist.size());
+    for (unsigned i = 0; i < Worklist.size(); ++i)
+      if (!WorklistMap.try_emplace(Worklist[i], i).second)
+        llvm_unreachable("Duplicate elements in the list");
+#ifndef NDEBUG
+    Finalized = true;
+#endif
+  }
+
   /// Add the specified instruction to the worklist if it isn't already in it.
   void insert(MachineInstr *I) {
+    assert(Finalized && "GISelWorkList used without finalizing");
     if (WorklistMap.try_emplace(I, Worklist.size()).second)
       Worklist.push_back(I);
   }
 
   /// Remove I from the worklist if it exists.
   void remove(const MachineInstr *I) {
+    assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty");
     auto It = WorklistMap.find(I);
-    if (It == WorklistMap.end()) return; // Not in worklist.
+    if (It == WorklistMap.end())
+      return; // Not in worklist.
 
     // Don't bother moving everything down, just null out the slot.
     Worklist[It->second] = nullptr;
 
     WorklistMap.erase(It);
   }
 
   void clear() {
     Worklist.clear();
     WorklistMap.clear();
   }
 
   MachineInstr *pop_back_val() {
+    assert(Finalized && "GISelWorkList used without finalizing");
     MachineInstr *I;
     do {
       I = Worklist.pop_back_val();
     } while(!I);
     assert(I && "Pop back on empty worklist");
     WorklistMap.erase(I);
     return I;
   }
 };
 
 } // end namespace llvm.
 
 #endif

lib/CodeGen/GlobalISel/Combiner.cpp

bool Combiner::combineMachineInstrs(MachineFunction &MF,
   bool Changed;
   MachineIRBuilder &B = *Builder.get();
 
   do {
     // Collect all instructions. Do a post order traversal for basic blocks and
     // insert with list bottom up, so while we pop_back_val, we'll traverse top
     // down RPOT.
     Changed = false;
     GISelWorkList<512> WorkList;
     WorkListMaintainer Observer(WorkList);
     GISelObserverWrapper WrapperObserver(&Observer);
     if (CSEInfo)
       WrapperObserver.addObserver(CSEInfo);
     RAIIDelegateInstaller DelInstall(MF, &WrapperObserver);
     for (MachineBasicBlock *MBB : post_order(&MF)) {
       if (MBB->empty())
         continue;
       for (auto MII = MBB->rbegin(), MIE = MBB->rend(); MII != MIE;) {
         MachineInstr *CurMI = &*MII;
         ++MII;
         // Erase dead insts before even adding to the list.
         if (isTriviallyDead(*CurMI, *MRI)) {
           LLVM_DEBUG(dbgs() << *CurMI << "Is dead; erasing.\n");
           CurMI->eraseFromParentAndMarkDBGValuesForRemoval();
           continue;
         }
-        WorkList.insert(CurMI);
+        WorkList.deferred_insert(CurMI);
       }
     }
+    WorkList.finalize();
     // Main Loop. Process the instructions here.
     while (!WorkList.empty()) {
       MachineInstr *CurrInst = WorkList.pop_back_val();
       LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;);
       Changed |= CInfo.combine(WrapperObserver, *CurrInst, B);
       Observer.reportFullyCreatedInstrs();
     }
     MFChanged |= Changed;
   } while (Changed);
 
   return MFChanged;
 }

lib/CodeGen/GlobalISel/Legalizer.cpp

for (auto *MBB : RPOT) {
     if (MBB->empty())
       continue;
     for (MachineInstr &MI : *MBB) {
       // Only legalize pre-isel generic instructions: others don't have types
       // and are assumed to be legal.
       if (!isPreISelGenericOpcode(MI.getOpcode()))
         continue;
       if (isArtifact(MI))
-        ArtifactList.insert(&MI);
+        ArtifactList.deferred_insert(&MI);
       else
-        InstList.insert(&MI);
+        InstList.deferred_insert(&MI);
     }
   }
+  ArtifactList.finalize();
+  InstList.finalize();
   std::unique_ptr<MachineIRBuilder> MIRBuilder;
   GISelCSEInfo *CSEInfo = nullptr;
   bool EnableCSE = EnableCSEInLegalizer.getNumOccurrences()
                        ? EnableCSEInLegalizer
                        : TPC.isGISelCSEEnabled();
 
   if (EnableCSE) {
     MIRBuilder = make_unique<CSEMIRBuilder>();