From 4d0d864be3d9a698c4edfe36961a22126f041298 Mon Sep 17 00:00:00 2001 From: Alkis Evlogimenos Date: Wed, 25 Feb 2004 21:55:45 +0000 Subject: 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 --- include/Support/DenseMap.h | 61 +++++++++++++++++++++++++++++++++++++ include/llvm/ADT/DenseMap.h | 61 +++++++++++++++++++++++++++++++++++++ include/llvm/ADT/IndexedMap.h | 61 +++++++++++++++++++++++++++++++++++++ include/llvm/CodeGen/SSARegMap.h | 23 +++++++------- include/llvm/Target/MRegisterInfo.h | 10 +++++- 5 files changed, 203 insertions(+), 13 deletions(-) create mode 100644 include/Support/DenseMap.h create mode 100644 include/llvm/ADT/DenseMap.h create mode 100644 include/llvm/ADT/IndexedMap.h (limited to 'include') 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 + +namespace llvm { + +template +class DenseMap { + typedef typename ToIndexT::argument_type IndexT; + typedef std::vector 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 + +namespace llvm { + +template +class DenseMap { + typedef typename ToIndexT::argument_type IndexT; + typedef std::vector 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 + +namespace llvm { + +template +class DenseMap { + typedef typename ToIndexT::argument_type IndexT; + typedef std::vector 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 RegClassMap; - - unsigned rescale(unsigned Reg) { - return Reg - MRegisterInfo::FirstVirtualRegister; - } + DenseMap 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 #include "llvm/CodeGen/MachineBasicBlock.h" +#include +#include 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 operator()(unsigned Reg) const { + return Reg - MRegisterInfo::FirstVirtualRegister; + } +}; + } // End llvm namespace #endif -- cgit v1.1