From 979869c28e5bc68e2d4d546c7019525177f1d399 Mon Sep 17 00:00:00 2001
From: Jakob Stoklund Olesen <stoklund@2pi.dk>
Date: Fri, 4 Mar 2011 19:43:38 +0000
Subject: [PATCH] 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
---
 include/llvm/CodeGen/SlotIndexes.h | 32 ++++++++++--------------------
 lib/CodeGen/SlotIndexes.cpp        | 27 +++++++++++++++++++++++--
 2 files changed, 36 insertions(+), 23 deletions(-)

diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h
index 063ac9900d9..0e2adb58977 100644
--- a/include/llvm/CodeGen/SlotIndexes.h
+++ b/include/llvm/CodeGen/SlotIndexes.h
@@ -113,7 +113,7 @@ namespace llvm {
     enum {
       /// The default distance between instructions as returned by distance().
       /// This may vary as instructions are inserted and removed.
-      InstrDist = 2*NUM
+      InstrDist = 4*NUM
     };
 
     static inline SlotIndex getEmptyKey() {
@@ -427,6 +427,9 @@ namespace llvm {
       insert(getTail(), val);
     }
 
+    /// Renumber locally after inserting newEntry.
+    void renumberIndexes(IndexListEntry *newEntry);
+
   public:
     static char ID;
 
@@ -599,7 +602,6 @@ namespace llvm {
              "Instruction's parent MBB has not been added to SlotIndexes.");
 
       MachineBasicBlock::iterator miItr(mi);
-      bool needRenumber = false;
       IndexListEntry *newEntry;
       // Get previous index, considering that not all instructions are indexed.
       IndexListEntry *prevEntry;
@@ -622,31 +624,19 @@ namespace llvm {
 
       // Get a number for the new instr, or 0 if there's no room currently.
       // In the latter case we'll force a renumber later.
-      unsigned dist = nextEntry->getIndex() - prevEntry->getIndex();
-      unsigned newNumber = dist > SlotIndex::NUM ?
-        prevEntry->getIndex() + ((dist >> 1) & ~3U) : 0;
-
-      if (newNumber == 0) {
-        needRenumber = true;
-      }
+      unsigned dist = ((nextEntry->getIndex() - prevEntry->getIndex())/2) & ~3u;
+      unsigned newNumber = prevEntry->getIndex() + dist;
 
       // Insert a new list entry for mi.
       newEntry = createEntry(mi, newNumber);
       insert(nextEntry, newEntry);
-  
-      SlotIndex newIndex(newEntry, SlotIndex::LOAD);
-      mi2iMap.insert(std::make_pair(mi, newIndex));
-
-      if (miItr == mbb->end()) {
-        // If this is the last instr in the MBB then we need to fix up the bb
-        // range:
-        mbbRangeItr->second.second = SlotIndex(newEntry, SlotIndex::STORE);
-      }
 
-      // Renumber if we need to.
-      if (needRenumber)
-        renumberIndexes();
+      // Renumber locally if we need to.
+      if (dist == 0)
+        renumberIndexes(newEntry);
 
+      SlotIndex newIndex(newEntry, SlotIndex::LOAD);
+      mi2iMap.insert(std::make_pair(mi, newIndex));
       return newIndex;
     }
 
diff --git a/lib/CodeGen/SlotIndexes.cpp b/lib/CodeGen/SlotIndexes.cpp
index 28e3fb5c159..c0ae34301dc 100644
--- a/lib/CodeGen/SlotIndexes.cpp
+++ b/lib/CodeGen/SlotIndexes.cpp
@@ -22,7 +22,8 @@ char SlotIndexes::ID = 0;
 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 @@ bool SlotIndexes::runOnMachineFunction(MachineFunction &fn) {
 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 @@ void SlotIndexes::renumberIndexes() {
   }
 }
 
+// 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()) {
-- 
2.34.1