LLVM 19.0.0git
ArrayRecycler.h
Go to the documentation of this file.
1//==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines the ArrayRecycler class template which can recycle small
10// arrays allocated from one of the allocators in Allocator.h
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_SUPPORT_ARRAYRECYCLER_H
15#define LLVM_SUPPORT_ARRAYRECYCLER_H
16
20
21namespace llvm {
22
23/// Recycle small arrays allocated from a BumpPtrAllocator.
24///
25/// Arrays are allocated in a small number of fixed sizes. For each supported
26/// array size, the ArrayRecycler keeps a free list of available arrays.
27///
28template <class T, size_t Align = alignof(T)> class ArrayRecycler {
29 // The free list for a given array size is a simple singly linked list.
30 // We can't use iplist or Recycler here since those classes can't be copied.
31 struct FreeList {
32 FreeList *Next;
33 };
34
35 static_assert(Align >= alignof(FreeList), "Object underaligned");
36 static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
37
38 // Keep a free list for each array size.
40
41 // Remove an entry from the free list in Bucket[Idx] and return it.
42 // Return NULL if no entries are available.
43 T *pop(unsigned Idx) {
44 if (Idx >= Bucket.size())
45 return nullptr;
46 FreeList *Entry = Bucket[Idx];
47 if (!Entry)
48 return nullptr;
50 Bucket[Idx] = Entry->Next;
52 return reinterpret_cast<T*>(Entry);
53 }
54
55 // Add an entry to the free list at Bucket[Idx].
56 void push(unsigned Idx, T *Ptr) {
57 assert(Ptr && "Cannot recycle NULL pointer");
58 FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
59 if (Idx >= Bucket.size())
60 Bucket.resize(size_t(Idx) + 1);
61 Entry->Next = Bucket[Idx];
62 Bucket[Idx] = Entry;
64 }
65
66public:
67 /// The size of an allocated array is represented by a Capacity instance.
68 ///
69 /// This class is much smaller than a size_t, and it provides methods to work
70 /// with the set of legal array capacities.
71 class Capacity {
72 uint8_t Index;
73 explicit Capacity(uint8_t idx) : Index(idx) {}
74
75 public:
76 Capacity() : Index(0) {}
77
78 /// Get the capacity of an array that can hold at least N elements.
79 static Capacity get(size_t N) {
80 return Capacity(N ? Log2_64_Ceil(N) : 0);
81 }
82
83 /// Get the number of elements in an array with this capacity.
84 size_t getSize() const { return size_t(1u) << Index; }
85
86 /// Get the bucket number for this capacity.
87 unsigned getBucket() const { return Index; }
88
89 /// Get the next larger capacity. Large capacities grow exponentially, so
90 /// this function can be used to reallocate incrementally growing vectors
91 /// in amortized linear time.
92 Capacity getNext() const { return Capacity(Index + 1); }
93 };
94
96 // The client should always call clear() so recycled arrays can be returned
97 // to the allocator.
98 assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
99 }
100
101 /// Release all the tracked allocations to the allocator. The recycler must
102 /// be free of any tracked allocations before being deleted.
103 template<class AllocatorType>
104 void clear(AllocatorType &Allocator) {
105 for (; !Bucket.empty(); Bucket.pop_back())
106 while (T *Ptr = pop(Bucket.size() - 1))
107 Allocator.Deallocate(Ptr);
108 }
109
110 /// Special case for BumpPtrAllocator which has an empty Deallocate()
111 /// function.
112 ///
113 /// There is no need to traverse the free lists, pulling all the objects into
114 /// cache.
116 Bucket.clear();
117 }
118
119 /// Allocate an array of at least the requested capacity.
120 ///
121 /// Return an existing recycled array, or allocate one from Allocator if
122 /// none are available for recycling.
123 ///
124 template<class AllocatorType>
125 T *allocate(Capacity Cap, AllocatorType &Allocator) {
126 // Try to recycle an existing array.
127 if (T *Ptr = pop(Cap.getBucket()))
128 return Ptr;
129 // Nope, get more memory.
130 return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
131 }
132
133 /// Deallocate an array with the specified Capacity.
134 ///
135 /// Cap must be the same capacity that was given to allocate().
136 ///
137 void deallocate(Capacity Cap, T *Ptr) {
138 push(Cap.getBucket(), Ptr);
139 }
140};
141
142} // end llvm namespace
143
144#endif
This file defines the BumpPtrAllocator interface.
#define __asan_poison_memory_region(p, size)
Definition: Compiler.h:459
#define __asan_unpoison_memory_region(p, size)
Definition: Compiler.h:460
#define __msan_allocated_memory(p, size)
Definition: Compiler.h:434
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
#define T
Basic Register Allocator
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
static unsigned getSize(unsigned Kind)
The size of an allocated array is represented by a Capacity instance.
Definition: ArrayRecycler.h:71
Capacity getNext() const
Get the next larger capacity.
Definition: ArrayRecycler.h:92
size_t getSize() const
Get the number of elements in an array with this capacity.
Definition: ArrayRecycler.h:84
static Capacity get(size_t N)
Get the capacity of an array that can hold at least N elements.
Definition: ArrayRecycler.h:79
unsigned getBucket() const
Get the bucket number for this capacity.
Definition: ArrayRecycler.h:87
Recycle small arrays allocated from a BumpPtrAllocator.
Definition: ArrayRecycler.h:28
T * allocate(Capacity Cap, AllocatorType &Allocator)
Allocate an array of at least the requested capacity.
void clear(BumpPtrAllocator &)
Special case for BumpPtrAllocator which has an empty Deallocate() function.
void clear(AllocatorType &Allocator)
Release all the tracked allocations to the allocator.
void deallocate(Capacity Cap, T *Ptr)
Deallocate an array with the specified Capacity.
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void resize(size_type N)
Definition: SmallVector.h:651
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
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:332
#define N
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39