[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

42

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

57

This is redundant

72

Ditto

[paquette]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

58

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;

66–68

Don't need braces here.

[aditya_nandakumar]

Removed redundant NDEBUG checks.

[aditya_nandakumar]

include/llvm/CodeGen/GlobalISel/GISelWorkList.h

58

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

 
 public:
   GISelWorkList() : WorklistMap(N) {}
 
   bool empty() const { return WorklistMap.empty(); }
 
   unsigned size() const { return WorklistMap.size(); }
 
+  void reserve(unsigned Size) {
+    if (Size > N) {
+      Worklist.reserve(Size);
+      WorklistMap.reserve(Size);
+    }
+  }
+
   /// Add the specified instruction to the worklist if it isn't already in it.
   void insert(MachineInstr *I) {
     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) {
     auto It = WorklistMap.find(I);
     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() {
     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;
+    unsigned MF_Size = 0;
+    for (auto &MBB : MF)
+      MF_Size += MBB.size();
     GISelWorkList<512> WorkList;
+    WorkList.reserve(MF_Size);
     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;

lib/CodeGen/GlobalISel/Legalizer.cpp

 };
 } // namespace
 
 bool Legalizer::runOnMachineFunction(MachineFunction &MF) {
   // If the ISel pipeline failed, do not bother running that pass.
   if (MF.getProperties().hasProperty(
           MachineFunctionProperties::Property::FailedISel))
     return false;
-  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
   init(MF);
   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
   GISelCSEAnalysisWrapper &Wrapper =
       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
 
   const size_t NumBlocks = MF.size();
   MachineRegisterInfo &MRI = MF.getRegInfo();
 
   // Populate Insts
   InstListTy InstList;
   ArtifactListTy ArtifactList;
+  LLVM_DEBUG(dbgs() << "Legalize Machine IR for: " << MF.getName() << '\n');
+  unsigned MF_Size = 0;
+  for (auto &MBB : MF)
+    MF_Size += MBB.size();
+  InstList.reserve(MF_Size);
+  ArtifactList.reserve(MF_Size);
   ReversePostOrderTraversal<MachineFunction *> RPOT(&MF);
   // Perform legalization bottom up so we can DCE as we legalize.
   // Traverse BB in RPOT and within each basic block, add insts top down,
   // so when we pop_back_val in the legalization process, we traverse bottom-up.
   for (auto *MBB : RPOT) {
     if (MBB->empty())
       continue;
     for (MachineInstr &MI : *MBB) {