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

1 files changed, 11 insertions, 21 deletions

diff --git a/include/llvm/CodeGen/SlotIndexes.h b/include/llvm/CodeGen/SlotIndexes.h
index 063ac9900d..0e2adb5897 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;
     }