[GISel][NFC]: Add methods to speed up insertion into GISelWorklist
https://reviews.llvm.org/D58073
Speed up insertion during the initial populating phase into the
GISelWorkList by deferring repeatedly resizing the DenseMap.
This results in ~10% improvement in the combiner passes, and
~3% speedup in the Legalizer.
reviewed by: aemerson.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@354093 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/CodeGen/GlobalISel/GISelWorkList.h b/include/llvm/CodeGen/GlobalISel/GISelWorkList.h
index 626a666..b0bb519 100644
--- a/include/llvm/CodeGen/GlobalISel/GISelWorkList.h
+++ b/include/llvm/CodeGen/GlobalISel/GISelWorkList.h
@@ -32,6 +32,10 @@
SmallVector<MachineInstr *, N> Worklist;
DenseMap<MachineInstr *, unsigned> WorklistMap;
+#ifndef NDEBUG
+ bool Finalized = true;
+#endif
+
public:
GISelWorkList() : WorklistMap(N) {}
@@ -39,16 +43,50 @@
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;
@@ -62,6 +100,7 @@
}
MachineInstr *pop_back_val() {
+ assert(Finalized && "GISelWorkList used without finalizing");
MachineInstr *I;
do {
I = Worklist.pop_back_val();
diff --git a/lib/CodeGen/GlobalISel/Combiner.cpp b/lib/CodeGen/GlobalISel/Combiner.cpp
index 093702b..31cb1db 100644
--- a/lib/CodeGen/GlobalISel/Combiner.cpp
+++ b/lib/CodeGen/GlobalISel/Combiner.cpp
@@ -129,9 +129,10 @@
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();
diff --git a/lib/CodeGen/GlobalISel/Legalizer.cpp b/lib/CodeGen/GlobalISel/Legalizer.cpp
index 02fa4d1..bd486d7 100644
--- a/lib/CodeGen/GlobalISel/Legalizer.cpp
+++ b/lib/CodeGen/GlobalISel/Legalizer.cpp
@@ -155,11 +155,13 @@
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()
