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

diff --git a/include/llvm/CodeGen/LiveIntervalAnalysis.h b/include/llvm/CodeGen/LiveIntervalAnalysis.h
index 2e539fa4c7b5669329c6cab650646ec7e9bc701d..a941cc0bbaf3281649dbf4ed25472a8787658bb4 100644 (file)
--- 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;
     }

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 92037aa61e13f675cf6382e16a0ef7f2562d3bbc..873edddf8b32ab1908a2fb417c38c775553ccfc5 100644 (file)
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -76,11 +76,9 @@ LiveIntervals::~LiveIntervals() {
 
 void LiveIntervals::releaseMemory() {
   // Free the live intervals themselves.
-  for (DenseMap<unsigned, LiveInterval*>::iterator I = R2IMap.begin(),
-       E = R2IMap.end(); I != E; ++I)
-    delete I->second;
-
-  R2IMap.clear();
+  for (unsigned i = 0, e = VirtRegIntervals.size(); i != e; ++i)
+    delete VirtRegIntervals[TargetRegisterInfo::index2VirtReg(i)];
+  VirtRegIntervals.clear();
   RegMaskSlots.clear();
   RegMaskBits.clear();
   RegMaskBlocks.clear();
@@ -124,21 +122,17 @@ bool LiveIntervals::runOnMachineFunction(MachineFunction &fn) {
 void LiveIntervals::print(raw_ostream &OS, const Module* ) const {
   OS << "********** INTERVALS **********\n";
 
-  // Dump the physregs.
-  for (unsigned Reg = 1, RegE = TRI->getNumRegs(); Reg != RegE; ++Reg)
-    if (const LiveInterval *LI = R2IMap.lookup(Reg))
-      OS << PrintReg(Reg, TRI) << '\t' << *LI << '\n';
-
   // Dump the regunits.
   for (unsigned i = 0, e = RegUnitIntervals.size(); i != e; ++i)
     if (LiveInterval *LI = RegUnitIntervals[i])
       OS << PrintRegUnit(i, TRI) << " = " << *LI << '\n';
 
   // Dump the virtregs.
-  for (unsigned Reg = 0, RegE = MRI->getNumVirtRegs(); Reg != RegE; ++Reg)
-    if (const LiveInterval *LI =
-        R2IMap.lookup(TargetRegisterInfo::index2VirtReg(Reg)))
-      OS << PrintReg(LI->reg) << '\t' << *LI << '\n';
+  for (unsigned i = 0, e = MRI->getNumVirtRegs(); i != e; ++i) {
+    unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
+    if (hasInterval(Reg))
+      OS << PrintReg(Reg) << " = " << getInterval(Reg) << '\n';
+  }
 
   printInstrs(OS);
 }