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 22namespace 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/// 29template <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 67public: 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