llvm/Support/ArrayRecycler.h

0001 //==- llvm/Support/ArrayRecycler.h - Recycling of Arrays ---------*- C++ -*-==//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines the ArrayRecycler class template which can recycle small
0010 // arrays allocated from one of the allocators in Allocator.h
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_SUPPORT_ARRAYRECYCLER_H
0015 #define LLVM_SUPPORT_ARRAYRECYCLER_H
0016
0017 #include "llvm/ADT/SmallVector.h"
0018 #include "llvm/Support/Allocator.h"
0019 #include "llvm/Support/MathExtras.h"
0020
0021 namespace llvm {
0022
0023 /// Recycle small arrays allocated from a BumpPtrAllocator.
0024 ///
0025 /// Arrays are allocated in a small number of fixed sizes. For each supported
0026 /// array size, the ArrayRecycler keeps a free list of available arrays.
0027 ///
0028 template <class T, size_t Align = alignof(T)> class ArrayRecycler {
0029   // The free list for a given array size is a simple singly linked list.
0030   // We can't use iplist or Recycler here since those classes can't be copied.
0031   struct FreeList {
0032     FreeList *Next;
0033   };
0034
0035   static_assert(Align >= alignof(FreeList), "Object underaligned");
0036   static_assert(sizeof(T) >= sizeof(FreeList), "Objects are too small");
0037
0038   // Keep a free list for each array size.
0039   SmallVector<FreeList*, 8> Bucket;
0040
0041   // Remove an entry from the free list in Bucket[Idx] and return it.
0042   // Return NULL if no entries are available.
0043   T *pop(unsigned Idx) {
0044     if (Idx >= Bucket.size())
0045       return nullptr;
0046     FreeList *Entry = Bucket[Idx];
0047     if (!Entry)
0048       return nullptr;
0049     __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
0050     Bucket[Idx] = Entry->Next;
0051     __msan_allocated_memory(Entry, Capacity::get(Idx).getSize());
0052     return reinterpret_cast<T*>(Entry);
0053   }
0054
0055   // Add an entry to the free list at Bucket[Idx].
0056   void push(unsigned Idx, T *Ptr) {
0057     assert(Ptr && "Cannot recycle NULL pointer");
0058     FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
0059     if (Idx >= Bucket.size())
0060       Bucket.resize(size_t(Idx) + 1);
0061     Entry->Next = Bucket[Idx];
0062     Bucket[Idx] = Entry;
0063     __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
0064   }
0065
0066 public:
0067   /// The size of an allocated array is represented by a Capacity instance.
0068   ///
0069   /// This class is much smaller than a size_t, and it provides methods to work
0070   /// with the set of legal array capacities.
0071   class Capacity {
0072     uint8_t Index;
0073     explicit Capacity(uint8_t idx) : Index(idx) {}
0074
0075   public:
0076     Capacity() : Index(0) {}
0077
0078     /// Get the capacity of an array that can hold at least N elements.
0079     static Capacity get(size_t N) {
0080       return Capacity(N ? Log2_64_Ceil(N) : 0);
0081     }
0082
0083     /// Get the number of elements in an array with this capacity.
0084     size_t getSize() const { return size_t(1u) << Index; }
0085
0086     /// Get the bucket number for this capacity.
0087     unsigned getBucket() const { return Index; }
0088
0089     /// Get the next larger capacity. Large capacities grow exponentially, so
0090     /// this function can be used to reallocate incrementally growing vectors
0091     /// in amortized linear time.
0092     Capacity getNext() const { return Capacity(Index + 1); }
0093   };
0094
0095   ~ArrayRecycler() {
0096     // The client should always call clear() so recycled arrays can be returned
0097     // to the allocator.
0098     assert(Bucket.empty() && "Non-empty ArrayRecycler deleted!");
0099   }
0100
0101   /// Release all the tracked allocations to the allocator. The recycler must
0102   /// be free of any tracked allocations before being deleted.
0103   template<class AllocatorType>
0104   void clear(AllocatorType &Allocator) {
0105     for (; !Bucket.empty(); Bucket.pop_back())
0106       while (T *Ptr = pop(Bucket.size() - 1))
0107         Allocator.Deallocate(Ptr);
0108   }
0109
0110   /// Special case for BumpPtrAllocator which has an empty Deallocate()
0111   /// function.
0112   ///
0113   /// There is no need to traverse the free lists, pulling all the objects into
0114   /// cache.
0115   void clear(BumpPtrAllocator&) {
0116     Bucket.clear();
0117   }
0118
0119   /// Allocate an array of at least the requested capacity.
0120   ///
0121   /// Return an existing recycled array, or allocate one from Allocator if
0122   /// none are available for recycling.
0123   ///
0124   template<class AllocatorType>
0125   T *allocate(Capacity Cap, AllocatorType &Allocator) {
0126     // Try to recycle an existing array.
0127     if (T *Ptr = pop(Cap.getBucket()))
0128       return Ptr;
0129     // Nope, get more memory.
0130     return static_cast<T*>(Allocator.Allocate(sizeof(T)*Cap.getSize(), Align));
0131   }
0132
0133   /// Deallocate an array with the specified Capacity.
0134   ///
0135   /// Cap must be the same capacity that was given to allocate().
0136   ///
0137   void deallocate(Capacity Cap, T *Ptr) {
0138     push(Cap.getBucket(), Ptr);
0139   }
0140 };
0141
0142 } // end llvm namespace
0143
0144 #endif