LLVM  6.0.0svn
ArrayRecycler.h
Go to the documentation of this file.
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"
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.
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 
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.
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
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
#define __msan_allocated_memory(p, size)
Definition: Compiler.h:376
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
T * allocate(Capacity Cap, AllocatorType &Allocator)
Allocate an array of at least the requested capacity.
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
Capacity getNext() const
Get the next larger capacity.
Definition: ArrayRecycler.h:93
Recycle small arrays allocated from a BumpPtrAllocator.
Definition: ArrayRecycler.h:29
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
The size of an allocated array is represented by a Capacity instance.
Definition: ArrayRecycler.h:72
unsigned getBucket() const
Get the bucket number for this capacity.
Definition: ArrayRecycler.h:88
#define __asan_unpoison_memory_region(p, size)
Definition: Compiler.h:388
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:138
Basic Register Allocator
static Capacity get(size_t N)
Get the capacity of an array that can hold at least N elements.
Definition: ArrayRecycler.h:80
void clear(AllocatorType &Allocator)
Release all the tracked allocations to the allocator.
unsigned Log2_64_Ceil(uint64_t Value)
Return the ceil log base 2 of the specified value, 64 if the value is zero.
Definition: MathExtras.h:550
size_t getSize() const
Get the number of elements in an array with this capacity.
Definition: ArrayRecycler.h:85
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:61
#define N
void clear(BumpPtrAllocator &)
Special case for BumpPtrAllocator which has an empty Deallocate() function.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
#define __asan_poison_memory_region(p, size)
Definition: Compiler.h:387
void deallocate(Capacity Cap, T *Ptr)
Deallocate an array with the specified Capacity.
void resize(size_type N)
Definition: SmallVector.h:355