Store live intervals in an IndexedMap.

It is both smaller and faster than DenseMap.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@159029 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 26 insertions, 28 deletions

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 2e539fa..a941cc0 100644
--- a/include/llvm/CodeGen/LiveIntervalAnalysis.h
+++ b/include/llvm/CodeGen/LiveIntervalAnalysis.h
@@ -20,12 +20,13 @@
 #ifndef LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
 #define LLVM_CODEGEN_LIVEINTERVAL_ANALYSIS_H
 
+#include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/LiveInterval.h"
 #include "llvm/CodeGen/SlotIndexes.h"
 #include "llvm/ADT/BitVector.h"
-#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/IndexedMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Support/Allocator.h"
@@ -61,8 +62,8 @@ namespace llvm {
     ///
     VNInfo::Allocator VNInfoAllocator;
 
-    typedef DenseMap<unsigned, LiveInterval*> Reg2IntervalMap;
-    Reg2IntervalMap R2IMap;
+    /// Live interval pointers for all the virtual registers.
+    IndexedMap<LiveInterval*, VirtReg2IndexFunctor> VirtRegIntervals;
 
     /// AllocatableRegs - A bit vector of allocatable registers.
     BitVector AllocatableRegs;
@@ -108,22 +109,20 @@ namespace llvm {
     // Calculate the spill weight to assign to a single instruction.
     static float getSpillWeight(bool isDef, bool isUse, unsigned loopDepth);
 
-    unsigned getNumIntervals() const { return (unsigned)R2IMap.size(); }
+    unsigned getNumIntervals() const { return (unsigned)VirtRegIntervals.size(); }
 
-    LiveInterval &getInterval(unsigned reg) {
-      Reg2IntervalMap::iterator I = R2IMap.find(reg);
-      assert(I != R2IMap.end() && "Interval does not exist for register");
-      return *I->second;
+    LiveInterval &getInterval(unsigned Reg) {
+      LiveInterval *LI = VirtRegIntervals[Reg];
+      assert(LI && "Interval does not exist for virtual register");
+      return *LI;
     }
 
-    const LiveInterval &getInterval(unsigned reg) const {
-      Reg2IntervalMap::const_iterator I = R2IMap.find(reg);
-      assert(I != R2IMap.end() && "Interval does not exist for register");
-      return *I->second;
+    const LiveInterval &getInterval(unsigned Reg) const {
+      return const_cast<LiveIntervals*>(this)->getInterval(Reg);
     }
 
-    bool hasInterval(unsigned reg) const {
-      return R2IMap.count(reg);
+    bool hasInterval(unsigned Reg) const {
+      return VirtRegIntervals.inBounds(Reg) && VirtRegIntervals[Reg];
     }
 
     /// isAllocatable - is the physical register reg allocatable in the current
@@ -138,12 +137,19 @@ namespace llvm {
       return ReservedRegs.test(reg);
     }
 
-    // Interval creation
-    LiveInterval &getOrCreateInterval(unsigned reg) {
-      Reg2IntervalMap::iterator I = R2IMap.find(reg);
-      if (I == R2IMap.end())
-        I = R2IMap.insert(std::make_pair(reg, createInterval(reg))).first;
-      return *I->second;
+    // Interval creation.
+    LiveInterval &getOrCreateInterval(unsigned Reg) {
+      if (!hasInterval(Reg)) {
+        VirtRegIntervals.grow(Reg);
+        VirtRegIntervals[Reg] = createInterval(Reg);
+      }
+      return getInterval(Reg);
+    }
+
+    // Interval removal.
+    void removeInterval(unsigned Reg) {
+      delete VirtRegIntervals[Reg];
+      VirtRegIntervals[Reg] = 0;
     }
 
     /// addLiveRangeToEndOfBlock - Given a register and an instruction,
@@ -161,14 +167,6 @@ namespace llvm {
     bool shrinkToUses(LiveInterval *li,
                       SmallVectorImpl<MachineInstr*> *dead = 0);
 
-    // Interval removal
-
-    void removeInterval(unsigned Reg) {
-      DenseMap<unsigned, LiveInterval*>::iterator I = R2IMap.find(Reg);
-      delete I->second;
-      R2IMap.erase(I);
-    }
-
     SlotIndexes *getSlotIndexes() const {
       return Indexes;
     }