Add DenseMap template and actually use it for for mapping virtual regs

to objects.


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

8 files changed, 232 insertions, 49 deletions

diff --git a/include/Support/DenseMap.h b/include/Support/DenseMap.h
new file mode 100644
index 0000000000..5fcdfae9de
--- /dev/null
+++ b/include/Support/DenseMap.h
@@ -0,0 +1,61 @@
+//===- DenseMap.h - A dense map implmentation -------------------*- C++ -*-===//
+// 
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file implements a dense map. A dense map template takes two
+// types. The first is the mapped type and the second is a functor
+// that maps its argument to a size_t. On instanciation a "null" value
+// can be provided to be used as a "does not exist" indicator in the
+// map. A member function grow() is provided that given the value of
+// the maximally indexed key (the argument of the functor) makes sure
+// the map has enough space for it.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUPPORT_DENSEMAP_H
+#define SUPPORT_DENSEMAP_H
+
+#include <vector>
+
+namespace llvm {
+
+template <typename T, typename ToIndexT>
+class DenseMap {
+    typedef typename ToIndexT::argument_type IndexT;
+    typedef std::vector<T> StorageT;
+    StorageT storage_;
+    T nullVal_;
+    ToIndexT toIndex_;
+
+public:
+    DenseMap() { }
+
+    explicit DenseMap(const T& val) : nullVal_(val) { }
+
+    typename StorageT::reference operator[](IndexT n) {
+        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
+        return storage_[toIndex_(n)];
+    }
+
+    typename StorageT::const_reference operator[](IndexT n) const {
+        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
+        return storage_[toIndex_(n)];
+    }
+
+    void clear() {
+        storage_.assign(storage_.size(), nullVal_);
+    }
+
+    void grow(IndexT n) {
+        storage_.resize(toIndex_(n) + 1, nullVal_);
+    }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
new file mode 100644
index 0000000000..5fcdfae9de
--- /dev/null
+++ b/include/llvm/ADT/DenseMap.h
@@ -0,0 +1,61 @@
+//===- DenseMap.h - A dense map implmentation -------------------*- C++ -*-===//
+// 
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file implements a dense map. A dense map template takes two
+// types. The first is the mapped type and the second is a functor
+// that maps its argument to a size_t. On instanciation a "null" value
+// can be provided to be used as a "does not exist" indicator in the
+// map. A member function grow() is provided that given the value of
+// the maximally indexed key (the argument of the functor) makes sure
+// the map has enough space for it.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUPPORT_DENSEMAP_H
+#define SUPPORT_DENSEMAP_H
+
+#include <vector>
+
+namespace llvm {
+
+template <typename T, typename ToIndexT>
+class DenseMap {
+    typedef typename ToIndexT::argument_type IndexT;
+    typedef std::vector<T> StorageT;
+    StorageT storage_;
+    T nullVal_;
+    ToIndexT toIndex_;
+
+public:
+    DenseMap() { }
+
+    explicit DenseMap(const T& val) : nullVal_(val) { }
+
+    typename StorageT::reference operator[](IndexT n) {
+        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
+        return storage_[toIndex_(n)];
+    }
+
+    typename StorageT::const_reference operator[](IndexT n) const {
+        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
+        return storage_[toIndex_(n)];
+    }
+
+    void clear() {
+        storage_.assign(storage_.size(), nullVal_);
+    }
+
+    void grow(IndexT n) {
+        storage_.resize(toIndex_(n) + 1, nullVal_);
+    }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/ADT/IndexedMap.h b/include/llvm/ADT/IndexedMap.h
new file mode 100644
index 0000000000..5fcdfae9de
--- /dev/null
+++ b/include/llvm/ADT/IndexedMap.h
@@ -0,0 +1,61 @@
+//===- DenseMap.h - A dense map implmentation -------------------*- C++ -*-===//
+// 
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file implements a dense map. A dense map template takes two
+// types. The first is the mapped type and the second is a functor
+// that maps its argument to a size_t. On instanciation a "null" value
+// can be provided to be used as a "does not exist" indicator in the
+// map. A member function grow() is provided that given the value of
+// the maximally indexed key (the argument of the functor) makes sure
+// the map has enough space for it.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef SUPPORT_DENSEMAP_H
+#define SUPPORT_DENSEMAP_H
+
+#include <vector>
+
+namespace llvm {
+
+template <typename T, typename ToIndexT>
+class DenseMap {
+    typedef typename ToIndexT::argument_type IndexT;
+    typedef std::vector<T> StorageT;
+    StorageT storage_;
+    T nullVal_;
+    ToIndexT toIndex_;
+
+public:
+    DenseMap() { }
+
+    explicit DenseMap(const T& val) : nullVal_(val) { }
+
+    typename StorageT::reference operator[](IndexT n) {
+        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
+        return storage_[toIndex_(n)];
+    }
+
+    typename StorageT::const_reference operator[](IndexT n) const {
+        assert(toIndex_(n) < storage_.size() && "index out of bounds!");
+        return storage_[toIndex_(n)];
+    }
+
+    void clear() {
+        storage_.assign(storage_.size(), nullVal_);
+    }
+
+    void grow(IndexT n) {
+        storage_.resize(toIndex_(n) + 1, nullVal_);
+    }
+};
+
+} // End llvm namespace
+
+#endif
diff --git a/include/llvm/CodeGen/SSARegMap.h b/include/llvm/CodeGen/SSARegMap.h
index 65c0cce732..afed38a334 100644
--- a/include/llvm/CodeGen/SSARegMap.h
+++ b/include/llvm/CodeGen/SSARegMap.h
@@ -18,35 +18,34 @@
 #define LLVM_CODEGEN_SSAREGMAP_H
 
 #include "llvm/Target/MRegisterInfo.h"
+#include "Support/DenseMap.h"
 
 namespace llvm {
 
 class TargetRegisterClass;
 
 class SSARegMap {
-  std::vector<const TargetRegisterClass*> RegClassMap;
-
-  unsigned rescale(unsigned Reg) {
-    return Reg - MRegisterInfo::FirstVirtualRegister;
-  }
+  DenseMap<const TargetRegisterClass*, VirtReg2IndexFunctor> RegClassMap;
+  unsigned NextRegNum;
 
  public:
+  SSARegMap() : NextRegNum(MRegisterInfo::FirstVirtualRegister) { }
+
   const TargetRegisterClass* getRegClass(unsigned Reg) {
-    unsigned actualReg = rescale(Reg);
-    assert(actualReg < RegClassMap.size() && "Register out of bounds");
-    return RegClassMap[actualReg];
+    return RegClassMap[Reg];
   }
 
   /// createVirtualRegister - Create and return a new virtual register in the
   /// function with the specified register class.
   ///
   unsigned createVirtualRegister(const TargetRegisterClass *RegClass) {
-    RegClassMap.push_back(RegClass);
-    return RegClassMap.size()+MRegisterInfo::FirstVirtualRegister-1;
+    RegClassMap.grow(NextRegNum);
+    RegClassMap[NextRegNum] = RegClass;
+    return NextRegNum++;
   }
 
-  unsigned getNumVirtualRegs() const {
-    return RegClassMap.size();
+  unsigned getLastVirtReg() const {
+    return NextRegNum - 1;
   }
 };
 
diff --git a/include/llvm/Target/MRegisterInfo.h b/include/llvm/Target/MRegisterInfo.h
index ce39f09ac7..0a83ac2ae3 100644
--- a/include/llvm/Target/MRegisterInfo.h
+++ b/include/llvm/Target/MRegisterInfo.h
@@ -16,8 +16,9 @@
 #ifndef LLVM_TARGET_MREGISTERINFO_H
 #define LLVM_TARGET_MREGISTERINFO_H
 
-#include <cassert>
 #include "llvm/CodeGen/MachineBasicBlock.h"
+#include <cassert>
+#include <functional>
 
 namespace llvm {
 
@@ -319,6 +320,13 @@ public:
                             MachineBasicBlock &MBB) const = 0;
 };
 
+// This is useful when building DenseMap's keyed on virtual registers
+struct VirtReg2IndexFunctor : std::unary_function<unsigned, unsigned> {
+  unsigned operator()(unsigned Reg) const {
+    return Reg - MRegisterInfo::FirstVirtualRegister;
+  }
+};
+
 } // End llvm namespace
 
 #endif
diff --git a/lib/CodeGen/RegAllocLocal.cpp b/lib/CodeGen/RegAllocLocal.cpp
index a3d66391cc..f3753326ee 100644
--- a/lib/CodeGen/RegAllocLocal.cpp
+++ b/lib/CodeGen/RegAllocLocal.cpp
@@ -23,6 +23,7 @@
 #include "llvm/Target/TargetMachine.h"
 #include "Support/CommandLine.h"
 #include "Support/Debug.h"
+#include "Support/DenseMap.h"
 #include "Support/Statistic.h"
 #include <iostream>
 using namespace llvm;
@@ -43,19 +44,11 @@ namespace {
     std::map<unsigned, int> StackSlotForVirtReg;
 
     // Virt2PhysRegMap - This map contains entries for each virtual register
-    // that is currently available in a physical register.  This is "logically"
-    // a map from virtual register numbers to physical register numbers.
-    // Instead of using a map, however, which is slow, we use a vector.  The
-    // index is the VREG number - FirstVirtualRegister.  If the entry is zero,
-    // then it is logically "not in the map".
-    //
-    std::vector<unsigned> Virt2PhysRegMap;
+    // that is currently available in a physical register.
+    DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysRegMap;
 
     unsigned &getVirt2PhysRegMapSlot(unsigned VirtReg) {
-      assert(MRegisterInfo::isVirtualRegister(VirtReg) &&"Illegal VREG #");
-      assert(VirtReg-MRegisterInfo::FirstVirtualRegister <Virt2PhysRegMap.size()
-             && "VirtReg not in map!");
-      return Virt2PhysRegMap[VirtReg-MRegisterInfo::FirstVirtualRegister];
+      return Virt2PhysRegMap[VirtReg];
     }
 
     // PhysRegsUsed - This array is effectively a map, containing entries for
@@ -661,7 +654,8 @@ void RA::AllocateBasicBlock(MachineBasicBlock &MBB) {
 
 #ifndef NDEBUG
   bool AllOk = true;
-  for (unsigned i = 0, e = Virt2PhysRegMap.size(); i != e; ++i)
+  for (unsigned i = MRegisterInfo::FirstVirtualRegister,
+           e = MF->getSSARegMap()->getLastVirtReg(); i <= e; ++i)
     if (unsigned PR = Virt2PhysRegMap[i]) {
       std::cerr << "Register still mapped: " << i << " -> " << PR << "\n";
       AllOk = false;
@@ -689,7 +683,8 @@ bool RA::runOnMachineFunction(MachineFunction &Fn) {
 
   // initialize the virtual->physical register map to have a 'null'
   // mapping for all virtual registers
-  Virt2PhysRegMap.assign(MF->getSSARegMap()->getNumVirtualRegs(), 0);
+  Virt2PhysRegMap.clear();
+  Virt2PhysRegMap.grow(MF->getSSARegMap()->getLastVirtReg());
 
   // Loop over all of the basic blocks, eliminating virtual register references
   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
diff --git a/lib/CodeGen/VirtRegMap.cpp b/lib/CodeGen/VirtRegMap.cpp
index bb29ffd954..4f06c6730f 100644
--- a/lib/CodeGen/VirtRegMap.cpp
+++ b/lib/CodeGen/VirtRegMap.cpp
@@ -38,12 +38,12 @@ namespace {
 int VirtRegMap::assignVirt2StackSlot(unsigned virtReg)
 {
     assert(MRegisterInfo::isVirtualRegister(virtReg));
-    assert(v2ssMap_[toIndex(virtReg)] == NO_STACK_SLOT &&
+    assert(v2ssMap_[virtReg] == NO_STACK_SLOT &&
            "attempt to assign stack slot to already spilled register");
     const TargetRegisterClass* rc =
         mf_->getSSARegMap()->getRegClass(virtReg);
     int frameIndex = mf_->getFrameInfo()->CreateStackObject(rc);
-    v2ssMap_[toIndex(virtReg)] = frameIndex;
+    v2ssMap_[virtReg] = frameIndex;
     ++numSpills;
     return frameIndex;
 }
@@ -53,14 +53,16 @@ std::ostream& llvm::operator<<(std::ostream& os, const VirtRegMap& vrm)
     const MRegisterInfo* mri = vrm.mf_->getTarget().getRegisterInfo();
 
     std::cerr << "********** REGISTER MAP **********\n";
-    for (unsigned i = 0, e = vrm.v2pMap_.size(); i != e; ++i) {
+    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
+             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
         if (vrm.v2pMap_[i] != VirtRegMap::NO_PHYS_REG)
-            std::cerr << "[reg" << VirtRegMap::fromIndex(i) << " -> "
+            std::cerr << "[reg" << i << " -> "
                       << mri->getName(vrm.v2pMap_[i]) << "]\n";
     }
-    for (unsigned i = 0, e = vrm.v2ssMap_.size(); i != e; ++i) {
+    for (unsigned i = MRegisterInfo::FirstVirtualRegister,
+             e = vrm.mf_->getSSARegMap()->getLastVirtReg(); i <= e; ++i) {
         if (vrm.v2ssMap_[i] != VirtRegMap::NO_STACK_SLOT)
-            std::cerr << "[reg" << VirtRegMap::fromIndex(i) << " -> fi#"
+            std::cerr << "[reg" << i << " -> fi#"
                       << vrm.v2ssMap_[i] << "]\n";
     }
     return std::cerr << '\n';
diff --git a/lib/CodeGen/VirtRegMap.h b/lib/CodeGen/VirtRegMap.h
index b5a819f373..3c991abb62 100644
--- a/lib/CodeGen/VirtRegMap.h
+++ b/lib/CodeGen/VirtRegMap.h
@@ -20,14 +20,15 @@
 
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/SSARegMap.h"
+#include "Support/DenseMap.h"
 #include <climits>
 
 namespace llvm {
 
     class VirtRegMap {
     public:
-        typedef std::vector<unsigned> Virt2PhysMap;
-        typedef std::vector<int> Virt2StackSlotMap;
+        typedef DenseMap<unsigned, VirtReg2IndexFunctor> Virt2PhysMap;
+        typedef DenseMap<int, VirtReg2IndexFunctor> Virt2StackSlotMap;
 
     private:
         MachineFunction* mf_;
@@ -38,13 +39,6 @@ namespace llvm {
         VirtRegMap(const VirtRegMap& rhs);
         const VirtRegMap& operator=(const VirtRegMap& rhs);
 
-        static unsigned toIndex(unsigned virtReg) {
-            return virtReg - MRegisterInfo::FirstVirtualRegister;
-        }
-        static unsigned fromIndex(unsigned index) {
-            return index + MRegisterInfo::FirstVirtualRegister;
-        }
-
         enum {
             NO_PHYS_REG   = 0,
             NO_STACK_SLOT = INT_MAX
@@ -53,8 +47,10 @@ namespace llvm {
     public:
         VirtRegMap(MachineFunction& mf)
             : mf_(&mf),
-              v2pMap_(mf.getSSARegMap()->getNumVirtualRegs(), NO_PHYS_REG),
-              v2ssMap_(mf.getSSARegMap()->getNumVirtualRegs(), NO_STACK_SLOT) {
+              v2pMap_(NO_PHYS_REG),
+              v2ssMap_(NO_STACK_SLOT) {
+            v2pMap_.grow(mf.getSSARegMap()->getLastVirtReg());
+            v2ssMap_.grow(mf.getSSARegMap()->getLastVirtReg());
         }
 
         bool hasPhys(unsigned virtReg) const {
@@ -63,23 +59,23 @@ namespace llvm {
 
         unsigned getPhys(unsigned virtReg) const {
             assert(MRegisterInfo::isVirtualRegister(virtReg));
-            return v2pMap_[toIndex(virtReg)];
+            return v2pMap_[virtReg];
         }
 
         void assignVirt2Phys(unsigned virtReg, unsigned physReg) {
             assert(MRegisterInfo::isVirtualRegister(virtReg) &&
                    MRegisterInfo::isPhysicalRegister(physReg));
-            assert(v2pMap_[toIndex(virtReg)] == NO_PHYS_REG &&
+            assert(v2pMap_[virtReg] == NO_PHYS_REG &&
                    "attempt to assign physical register to already mapped "
                    "virtual register");
-            v2pMap_[toIndex(virtReg)] = physReg;
+            v2pMap_[virtReg] = physReg;
         }
 
         void clearVirtReg(unsigned virtReg) {
             assert(MRegisterInfo::isVirtualRegister(virtReg));
-            assert(v2pMap_[toIndex(virtReg)] != NO_PHYS_REG &&
+            assert(v2pMap_[virtReg] != NO_PHYS_REG &&
                    "attempt to clear a not assigned virtual register");
-            v2pMap_[toIndex(virtReg)] = NO_PHYS_REG;
+            v2pMap_[virtReg] = NO_PHYS_REG;
         }
 
         bool hasStackSlot(unsigned virtReg) const {
@@ -88,7 +84,7 @@ namespace llvm {
 
         int getStackSlot(unsigned virtReg) const {
             assert(MRegisterInfo::isVirtualRegister(virtReg));
-            return v2ssMap_[toIndex(virtReg)];
+            return v2ssMap_[virtReg];
         }
 
         int assignVirt2StackSlot(unsigned virtReg);