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/MathExtras.h"
  19 #include "llvm/System/DataTypes.h"
  20 #include <algorithm>
  21 #include <cassert>
  22 #include <cstdlib>
  23 #include <cstddef>
  24
  25 namespace llvm {
  26
  27 class MallocAllocator {
  28 public:
  29   MallocAllocator() {}
  30   ~MallocAllocator() {}
  31
  32   void Reset() {}
  33
  34   void *Allocate(size_t Size, size_t /*Alignment*/) { return malloc(Size); }
  35
  36   template <typename T>
  37   T *Allocate() { return static_cast<T*>(malloc(sizeof(T))); }
  38
  39   template <typename T>
  40   T *Allocate(size_t Num) {
  41     return static_cast<T*>(malloc(sizeof(T)*Num));
  42   }
  43
  44   void Deallocate(const void *Ptr) { free(const_cast<void*>(Ptr)); }
  45
  46   void PrintStats() const {}
  47 };
  48
  49 /// MemSlab - This structure lives at the beginning of every slab allocated by
  50 /// the bump allocator.
  51 class MemSlab {
  52 public:
  53   size_t Size;
  54   MemSlab *NextPtr;
  55 };
  56
  57 /// SlabAllocator - This class can be used to parameterize the underlying
  58 /// allocation strategy for the bump allocator.  In particular, this is used
  59 /// by the JIT to allocate contiguous swathes of executable memory.  The
  60 /// interface uses MemSlab's instead of void *'s so that the allocator
  61 /// doesn't have to remember the size of the pointer it allocated.
  62 class SlabAllocator {
  63 public:
  64   virtual ~SlabAllocator();
  65   virtual MemSlab *Allocate(size_t Size) = 0;
  66   virtual void Deallocate(MemSlab *Slab) = 0;
  67 };
  68
  69 /// MallocSlabAllocator - The default slab allocator for the bump allocator
  70 /// is an adapter class for MallocAllocator that just forwards the method
  71 /// calls and translates the arguments.
  72 class MallocSlabAllocator : public SlabAllocator {
  73   /// Allocator - The underlying allocator that we forward to.
  74   ///
  75   MallocAllocator Allocator;
  76
  77 public:
  78   MallocSlabAllocator() : Allocator() { }
  79   virtual ~MallocSlabAllocator();
  80   virtual MemSlab *Allocate(size_t Size);
  81   virtual void Deallocate(MemSlab *Slab);
  82 };
  83
  84 /// BumpPtrAllocator - This allocator is useful for containers that need
  85 /// very simple memory allocation strategies.  In particular, this just keeps
  86 /// allocating memory, and never deletes it until the entire block is dead. This
  87 /// makes allocation speedy, but must only be used when the trade-off is ok.
  88 class BumpPtrAllocator {
  89   BumpPtrAllocator(const BumpPtrAllocator &); // do not implement
  90   void operator=(const BumpPtrAllocator &);   // do not implement
  91
  92   /// SlabSize - Allocate data into slabs of this size unless we get an
  93   /// allocation above SizeThreshold.
  94   size_t SlabSize;
  95
  96   /// SizeThreshold - For any allocation larger than this threshold, we should
  97   /// allocate a separate slab.
  98   size_t SizeThreshold;
  99
 100   /// Allocator - The underlying allocator we use to get slabs of memory.  This
 101   /// defaults to MallocSlabAllocator, which wraps malloc, but it could be
 102   /// changed to use a custom allocator.
 103   SlabAllocator &Allocator;
 104
 105   /// CurSlab - The slab that we are currently allocating into.
 106   ///
 107   MemSlab *CurSlab;
 108
 109   /// CurPtr - The current pointer into the current slab.  This points to the
 110   /// next free byte in the slab.
 111   char *CurPtr;
 112
 113   /// End - The end of the current slab.
 114   ///
 115   char *End;
 116
 117   /// BytesAllocated - This field tracks how many bytes we've allocated, so
 118   /// that we can compute how much space was wasted.
 119   size_t BytesAllocated;
 120
 121   /// AlignPtr - Align Ptr to Alignment bytes, rounding up.  Alignment should
 122   /// be a power of two.  This method rounds up, so AlignPtr(7, 4) == 8 and
 123   /// AlignPtr(8, 4) == 8.
 124   static char *AlignPtr(char *Ptr, size_t Alignment);
 125
 126   /// StartNewSlab - Allocate a new slab and move the bump pointers over into
 127   /// the new slab.  Modifies CurPtr and End.
 128   void StartNewSlab();
 129
 130   /// DeallocateSlabs - Deallocate all memory slabs after and including this
 131   /// one.
 132   void DeallocateSlabs(MemSlab *Slab);
 133
 134   static MallocSlabAllocator DefaultSlabAllocator;
 135
 136 public:
 137   typedef void (*DTorFunction)(void*);
 138   BumpPtrAllocator(size_t size = 4096, size_t threshold = 4096,
 139                    SlabAllocator &allocator = DefaultSlabAllocator);
 140   ~BumpPtrAllocator();
 141
 142   /// Reset - Deallocate all but the current slab and reset the current pointer
 143   /// to the beginning of it, freeing all memory allocated so far.
 144   void Reset();
 145
 146   /// Reset - like Reset(), but call DTorFunction for each allocated
 147   /// object. This assumes that all objects allocated with this allocator
 148   /// had the same size and alignment specified here.
 149   void Reset(size_t Size, size_t Alignment, DTorFunction DTor);
 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 }  // end namespace llvm
 186
 187 inline void *operator new(size_t Size, llvm::BumpPtrAllocator &Allocator) {
 188   struct S {
 189     char c;
 190 #ifdef __GNUC__
 191     char x __attribute__((aligned));
 192 #else
 193     union {
 194       double D;
 195       long double LD;
 196       long long L;
 197       void *P;
 198     } x;
 199 #endif
 200   };
 201   return Allocator.Allocate(Size, std::min((size_t)llvm::NextPowerOf2(Size),
 202                                            offsetof(S, x)));
 203 }
 204
 205 #endif // LLVM_SUPPORT_ALLOCATOR_H