Renumber slot indexes locally when possible.
Initially, slot indexes are quad-spaced. There is room for inserting up to 3
new instructions between the original instructions.
When we run out of indexes between two instructions, renumber locally using
double-spaced indexes. The original quad-spacing means that we catch up quickly,
and we only have to renumber a handful of instructions to get a monotonic
sequence. This is much faster than renumbering the whole function as we did
before.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127023 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/SlotIndexes.cpp b/lib/CodeGen/SlotIndexes.cpp
index 28e3fb5..c0ae343 100644
--- a/lib/CodeGen/SlotIndexes.cpp
+++ b/lib/CodeGen/SlotIndexes.cpp
@@ -22,7 +22,8 @@
INITIALIZE_PASS(SlotIndexes, "slotindexes",
"Slot index numbering", false, false)
-STATISTIC(NumRenumPasses, "Number of slot index renumber passes");
+STATISTIC(NumLocalRenum, "Number of local renumberings");
+STATISTIC(NumGlobalRenum, "Number of global renumberings");
void SlotIndexes::getAnalysisUsage(AnalysisUsage &au) const {
au.setPreservesAll();
@@ -112,7 +113,7 @@
void SlotIndexes::renumberIndexes() {
// Renumber updates the index of every element of the index list.
DEBUG(dbgs() << "\n*** Renumbering SlotIndexes ***\n");
- ++NumRenumPasses;
+ ++NumGlobalRenum;
unsigned index = 0;
@@ -123,6 +124,28 @@
}
}
+// Renumber indexes locally after curEntry was inserted, but failed to get a new
+// index.
+void SlotIndexes::renumberIndexes(IndexListEntry *curEntry) {
+ // Number indexes with half the default spacing so we can catch up quickly.
+ const unsigned Space = SlotIndex::InstrDist/2;
+ assert((Space & 3) == 0 && "InstrDist must be a multiple of 2*NUM");
+
+ IndexListEntry *start = curEntry->getPrev();
+ unsigned index = start->getIndex();
+ IndexListEntry *tail = getTail();
+ do {
+ curEntry->setIndex(index += Space);
+ curEntry = curEntry->getNext();
+ // If the next index is bigger, we have caught up.
+ } while (curEntry != tail && curEntry->getIndex() <= index);
+
+ DEBUG(dbgs() << "\n*** Renumbered SlotIndexes " << start->getIndex() << '-'
+ << index << " ***\n");
+ ++NumLocalRenum;
+}
+
+
void SlotIndexes::dump() const {
for (const IndexListEntry *itr = front(); itr != getTail();
itr = itr->getNext()) {