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