aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/Support/DenseMap.h61
-rw-r--r--include/llvm/ADT/DenseMap.h61
-rw-r--r--include/llvm/ADT/IndexedMap.h61
-rw-r--r--include/llvm/CodeGen/SSARegMap.h23
-rw-r--r--include/llvm/Target/MRegisterInfo.h10
-rw-r--r--lib/CodeGen/RegAllocLocal.cpp21
-rw-r--r--lib/CodeGen/VirtRegMap.cpp14
-rw-r--r--lib/CodeGen/VirtRegMap.h30
8 files changed, 232 insertions, 49 deletions
diff --git a/include/Support/DenseMap.h b/include/Support/DenseMap.h
new file mode 100644
index 0000000..5fcdfae
--- /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 0000000..5fcdfae
--- /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 0000000..5fcdfae
--- /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 65c0cce..afed38a 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 ce39f09..0a83ac2 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 a3d6639..f375332 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 bb29ffd..4f06c67 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 b5a819f..3c991ab 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);
generated by cgit v1.1 at 2025-01-13 21:42:34 +0000