Line data Source code
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 101259847 : if (Idx >= Bucket.size())
46 : return nullptr;
47 66091962 : FreeList *Entry = Bucket[Idx];
48 66091962 : if (!Entry)
49 : return nullptr;
50 : __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
51 20065999 : 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 66952074 : void push(unsigned Idx, T *Ptr) {
58 : assert(Ptr && "Cannot recycle NULL pointer");
59 : FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
60 66952074 : if (Idx >= Bucket.size())
61 3943940 : Bucket.resize(size_t(Idx) + 1);
62 66952072 : Entry->Next = Bucket[Idx];
63 66952072 : Bucket[Idx] = Entry;
64 : __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
65 66952072 : }
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 52582194 : 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 136040311 : return Capacity(N ? Log2_64_Ceil(N) : 0);
82 : }
83 :
84 : /// Get the number of elements in an array with this capacity.
85 260881035 : size_t getSize() const { return size_t(1u) << Index; }
86 :
87 : /// Get the bucket number for this capacity.
88 125977369 : 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 6632786 : 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 440060 : }
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 0 : void clear(BumpPtrAllocator&) {
117 : Bucket.clear();
118 0 : }
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 101259847 : T *allocate(Capacity Cap, AllocatorType &Allocator) {
127 : // Try to recycle an existing array.
128 : if (T *Ptr = pop(Cap.getBucket()))
129 20065999 : return Ptr;
130 : // Nope, get more memory.
131 81193848 : 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 24717524 : push(Cap.getBucket(), Ptr);
140 : }
141 : };
142 :
143 : } // end llvm namespace
144 :
145 : #endif
|
