include/llvm/Support/Allocator.h

   1 //===--- Allocator.h - Simple memory allocation abstraction -----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the MallocAllocator and BumpPtrAllocator interfaces.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_SUPPORT_ALLOCATOR_H
  15 #define LLVM_SUPPORT_ALLOCATOR_H
  16
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/Support/AlignOf.h"
  20 #include "llvm/Support/DataTypes.h"
  21 #include "llvm/Support/MathExtras.h"
  22 #include <algorithm>
  23 #include <cassert>
  24 #include <cstddef>
  25 #include <cstdlib>
  26
  27 namespace llvm {
  28 template <typename T> struct ReferenceAdder { typedef T& result; };
  29 template <typename T> struct ReferenceAdder<T&> { typedef T result; };
  30
  31 class MallocAllocator {
  32 public:
  33   MallocAllocator() {}
  34   ~MallocAllocator() {}
  35
  36   void Reset() {}
  37
  38   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
  39
  40   template <typename T>
  41   T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
  42
  43   template <typename T>
  44   T *Allocate(size_t Num) {
  45     return static_cast<T*>(malloc(sizeof(T)*Num));
  46   }
  47
  48   void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
  49
  50   void PrintStats() const {}
  51 };
  52
  53 /// MemSlab - This structure lives at the beginning of every slab allocated by
  54 /// the bump allocator.
  55 class MemSlab {
  56 public:
  57   size_t Size;
  58   MemSlab *NextPtr;
  59 };
  60
  61 /// SlabAllocator - This class can be used to parameterize the underlying
  62 /// allocation strategy for the bump allocator.  In particular, this is used
  63 /// by the JIT to allocate contiguous swathes of executable memory.  The
  64 /// interface uses MemSlab's instead of void *'s so that the allocator
  65 /// doesn't have to remember the size of the pointer it allocated.
  66 class SlabAllocator {
  67 public:
  68   virtual ~SlabAllocator();
  69   virtual MemSlab *Allocate(size_t Size) = 0;
  70   virtual void Deallocate(MemSlab *Slab) = 0;
  71 };
  72
  73 /// MallocSlabAllocator - The default slab allocator for the bump allocator
  74 /// is an adapter class for MallocAllocator that just forwards the method
  75 /// calls and translates the arguments.
  76 class MallocSlabAllocator : public SlabAllocator {
  77   /// Allocator - The underlying allocator that we forward to.
  78   ///
  79   MallocAllocator Allocator;
  80
  81 public:
  82   MallocSlabAllocator() : Allocator() { }
  83   virtual ~MallocSlabAllocator();
  84   virtual MemSlab *Allocate(size_t Size) LLVM_OVERRIDE;
  85   virtual void Deallocate(MemSlab *Slab) LLVM_OVERRIDE;
  86 };
  87
  88 /// BumpPtrAllocator - This allocator is useful for containers that need
  89 /// very simple memory allocation strategies.  In particular, this just keeps
  90 /// allocating memory, and never deletes it until the entire block is dead. This
  91 /// makes allocation speedy, but must only be used when the trade-off is ok.
  92 class BumpPtrAllocator {
  93   BumpPtrAllocator(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
  94   void operator=(const BumpPtrAllocator &) LLVM_DELETED_FUNCTION;
  95
  96   /// SlabSize - Allocate data into slabs of this size unless we get an
  97   /// allocation above SizeThreshold.
  98   size_t SlabSize;
  99
 100   /// SizeThreshold - For any allocation larger than this threshold, we should
 101   /// allocate a separate slab.
 102   size_t SizeThreshold;
 103
 104   /// \brief the default allocator used if one is not provided
 105   MallocSlabAllocator DefaultSlabAllocator;
 106
 107   /// Allocator - The underlying allocator we use to get slabs of memory.  This
 108   /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
 109   /// changed to use a custom allocator.
 110   SlabAllocator &Allocator;
 111
 112   /// CurSlab - The slab that we are currently allocating into.
 113   ///
 114   MemSlab *CurSlab;
 115
 116   /// CurPtr - The current pointer into the current slab.  This points to the
 117   /// next free byte in the slab.
 118   char *CurPtr;
 119
 120   /// End - The end of the current slab.
 121   ///
 122   char *End;
 123
 124   /// BytesAllocated - This field tracks how many bytes we've allocated, so
 125   /// that we can compute how much space was wasted.
 126   size_t BytesAllocated;
 127
 128   /// AlignPtr - Align Ptr to Alignment bytes, rounding up.  Alignment should
 129   /// be a power of two.  This method rounds up, so AlignPtr(7, 4) == 8 and
 130   /// AlignPtr(8, 4) == 8.
 131   static char *AlignPtr(char *Ptr, size_t Alignment);
 132
 133   /// StartNewSlab - Allocate a new slab and move the bump pointers over into
 134   /// the new slab.  Modifies CurPtr and End.
 135   void StartNewSlab();
 136
 137   /// DeallocateSlabs - Deallocate all memory slabs after and including this
 138   /// one.
 139   void DeallocateSlabs(MemSlab *Slab);
 140
 141   template<typename T> friend class SpecificBumpPtrAllocator;
 142 public:
 143   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096);
 144   BumpPtrAllocator(size_t size, size_t threshold, SlabAllocator &allocator);
 145   ~BumpPtrAllocator();
 146
 147   /// Reset - Deallocate all but the current slab and reset the current pointer
 148   /// to the beginning of it, freeing all memory allocated so far.
 149   void Reset();
 150
 151   /// Allocate - Allocate space at the specified alignment.
 152   ///
 153   void *Allocate(size_t Size, size_t Alignment);
 154
 155   /// Allocate space, but do not construct, one object.
 156   ///
 157   template <typename T>
 158   T *Allocate() {
 159     return static_cast<T*>(Allocate(sizeof(T),AlignOf<T>::Alignment));
 160   }
 161
 162   /// Allocate space for an array of objects.  This does not construct the
 163   /// objects though.
 164   template <typename T>
 165   T *Allocate(size_t Num) {
 166     return static_cast<T*>(Allocate(Num * sizeof(T), AlignOf<T>::Alignment));
 167   }
 168
 169   /// Allocate space for a specific count of elements and with a specified
 170   /// alignment.
 171   template <typename T>
 172   T *Allocate(size_t Num, size_t Alignment) {
 173     // Round EltSize up to the specified alignment.
 174     size_t EltSize = (sizeof(T)+Alignment-1)&(-Alignment);
 175     return static_cast<T*>(Allocate(Num * EltSize, Alignment));
 176   }
 177
 178   void Deallocate(const void * /*Ptr*/) {}
 179
 180   unsigned GetNumSlabs() const;
 181
 182   void PrintStats() const;
 183
 184
 185   /// Allocate space and copy content into it.
 186   void *allocateCopy(const void *Src, size_t Size, size_t Alignment=1) {
 187     void *P = Allocate(Size, Alignment);
 188     memcpy(P, Src, Size);
 189     return P;
 190   }
 191
 192   /// Allocate space for an array of type T, and use std::copy()
 193   /// to copy the array contents.
 194   template <typename T>
 195   typename enable_if<isPodLike<T>, T*>::type
 196   allocateCopy(const T Src[], size_t Num) {
 197     T *P = Allocate<T>(Num);
 198     std::copy(Src, &Src[Num], P);
 199     return P;
 200   }
 201
 202   /// Copy a StringRef by allocating copy in BumpPtrAllocator.
 203   StringRef allocateCopy(StringRef Str) {
 204     size_t Length = Str.size();
 205     char *P = allocateCopy<char>(Str.data(), Length);
 206     return StringRef(P, Length);
 207   }
 208
 209   /// Copy a ArrayRef<T> by allocating copy in BumpPtrAllocator.
 210   template <typename T>
 211   typename enable_if<isPodLike<T>, ArrayRef<T> >::type
 212   allocateCopy(ArrayRef<T> Src) {
 213     size_t Length = Src.size();
 214     T *P = allocateCopy<T>(Src.data(), Length);
 215     return makeArrayRef(P, Length);
 216   }
 217
 218   /// Compute the total physical memory allocated by this allocator.
 219   size_t getTotalMemory() const;
 220 };
 221
 222 /// SpecificBumpPtrAllocator - Same as BumpPtrAllocator but allows only
 223 /// elements of one type to be allocated. This allows calling the destructor
 224 /// in DestroyAll() and when the allocator is destroyed.
 225 template <typename T>
 226 class SpecificBumpPtrAllocator {
 227   BumpPtrAllocator Allocator;
 228 public:
 229   SpecificBumpPtrAllocator(size_t size = 4096, size_t threshold = 4096)
 230     : Allocator(size, threshold) {}
 231   SpecificBumpPtrAllocator(size_t size, size_t threshold,
 232                            SlabAllocator &allocator)
 233     : Allocator(size, threshold, allocator) {}
 234
 235   ~SpecificBumpPtrAllocator() {
 236     DestroyAll();
 237   }
 238
 239   /// Call the destructor of each allocated object and deallocate all but the
 240   /// current slab and reset the current pointer to the beginning of it, freeing
 241   /// all memory allocated so far.
 242   void DestroyAll() {
 243     MemSlab *Slab = Allocator.CurSlab;
 244     while (Slab) {
 245       char *End = Slab == Allocator.CurSlab ? Allocator.CurPtr :
 246                                               (char *)Slab + Slab->Size;
 247       for (char *Ptr = (char*)(Slab+1); Ptr < End; Ptr += sizeof(T)) {
 248         Ptr = Allocator.AlignPtr(Ptr, alignOf<T>());
 249         if (Ptr + sizeof(T) <= End)
 250           reinterpret_cast<T*>(Ptr)->~T();
 251       }
 252       Slab = Slab->NextPtr;
 253     }
 254     Allocator.Reset();
 255   }
 256
 257   /// Allocate space for a specific count of elements.
 258   T *Allocate(size_t num = 1) {
 259     return Allocator.Allocate<T>(num);
 260   }
 261 };
 262
 263 }  // end namespace llvm
 264
 265 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
 266   struct S {
 267     char c;
 268     union {
 269       double D;
 270       long double LD;
 271       long long L;
 272       void *P;
 273     } x;
 274   };
 275   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
 276                                            offsetof(S, x)));
 277 }
 278
 279 inline void operator delete(void *, llvm::BumpPtrAllocator &) {}
 280
 281 #endif // LLVM_SUPPORT_ALLOCATOR_H