Home | History | Annotate | Download | only in Support 
      1 //==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- 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 ArrayRecycler class template which can recycle small
     11 // arrays allocated from one of the allocators in Allocator.h
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_SUPPORT_ARRAYRECYCLER_H
     16 #define LLVM_SUPPORT_ARRAYRECYCLER_H
     17 
     18 #include "llvm/ADT/SmallVector.h"
     19 #include "llvm/Support/Allocator.h"
     20 #include "llvm/Support/MathExtras.h"
     21 
     22 namespace llvm {
     23 
     24 /// Recycle small arrays allocated from a BumpPtrAllocator.
     25 ///
     26 /// Arrays are allocated in a small number of fixed sizes. For each supported
     27 /// array size, the ArrayRecycler keeps a free list of available arrays.
     28 ///
     29 template <class T, size_t Align = alignof(T)> class ArrayRecycler {
     30   // The free list for a given array size is a simple singly linked list.
     31   // We can't use iplist or Recycler here since those classes can't be copied.
     32   struct FreeList {
     33     FreeList *Next;
     34   };
     35 
     36   static_assert(Align >= alignof(FreeList), "Object underaligned");
     37   static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
     38 
     39   // Keep a free list for each array size.
     40   SmallVector<FreeList*, 8> Bucket;
     41 
     42   // Remove an entry from the free list in Bucket[Idx] and return it.
     43   // Return NULL if no entries are available.
     44   T *pop(unsigned Idx) {
     45     if (Idx >= Bucket.size())
     46       return nullptr;
     47     FreeList *Entry = Bucket[Idx];
     48     if (!Entry)
     49       return nullptr;
     50     __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
     51     Bucket[Idx] = Entry->Next;
     52     __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
     53     return reinterpret_cast<T*>(Entry);
     54   }
     55 
     56   // Add an entry to the free list at Bucket[Idx].
     57   void push(unsigned Idx, T *Ptr) {
     58     assert(Ptr && "Cannot recycle NULL pointer");
     59     FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
     60     if (Idx >= Bucket.size())
     61       Bucket.resize(size_t(Idx) + 1);
     62     Entry->Next = Bucket[Idx];
     63     Bucket[Idx] = Entry;
     64     __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
     65   }
     66 
     67 public:
     68   /// The size of an allocated array is represented by a Capacity instance.
     69   ///
     70   /// This class is much smaller than a size_t, and it provides methods to work
     71   /// with the set of legal array capacities.
     72   class Capacity {
     73     uint8_t Index;
     74     explicit Capacity(uint8_t idx) : Index(idx) {}
     75 
     76   public:
     77     Capacity() : Index(0) {}
     78 
     79     /// Get the capacity of an array that can hold at least N elements.
     80     static Capacity get(size_t N) {
     81       return Capacity(N ? Log2_64_Ceil(N) : 0);
     82     }
     83 
     84     /// Get the number of elements in an array with this capacity.
     85     size_t getSize() const { return size_t(1u) << Index; }
     86 
     87     /// Get the bucket number for this capacity.
     88     unsigned getBucket() const { return Index; }
     89 
     90     /// Get the next larger capacity. Large capacities grow exponentially, so
     91     /// this function can be used to reallocate incrementally growing vectors
     92     /// in amortized linear time.
     93     Capacity getNext() const { return Capacity(Index + 1); }
     94   };
     95 
     96   ~ArrayRecycler() {
     97     // The client should always call clear() so recycled arrays can be returned
     98     // to the allocator.
     99     assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
    100   }
    101 
    102   /// Release all the tracked allocations to the allocator. The recycler must
    103   /// be free of any tracked allocations before being deleted.
    104   template<class AllocatorType>
    105   void clear(AllocatorType &Allocator) {
    106     for (; !Bucket.empty(); Bucket.pop_back())
    107       while (T *Ptr = pop(Bucket.size() - 1))
    108         Allocator.Deallocate(Ptr);
    109   }
    110 
    111   /// Special case for BumpPtrAllocator which has an empty Deallocate()
    112   /// function.
    113   ///
    114   /// There is no need to traverse the free lists, pulling all the objects into
    115   /// cache.
    116   void clear(BumpPtrAllocator&) {
    117     Bucket.clear();
    118   }
    119 
    120   /// Allocate an array of at least the requested capacity.
    121   ///
    122   /// Return an existing recycled array, or allocate one from Allocator if
    123   /// none are available for recycling.
    124   ///
    125   template<class AllocatorType>
    126   T *allocate(Capacity Cap, AllocatorType &Allocator) {
    127     // Try to recycle an existing array.
    128     if (T *Ptr = pop(Cap.getBucket()))
    129       return Ptr;
    130     // Nope, get more memory.
    131     return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
    132   }
    133 
    134   /// Deallocate an array with the specified Capacity.
    135   ///
    136   /// Cap must be the same capacity that was given to allocate().
    137   ///
    138   void deallocate(Capacity Cap, T *Ptr) {
    139     push(Cap.getBucket(), Ptr);
    140   }
    141 };
    142 
    143 } // end llvm namespace
    144 
    145 #endif
    146