LCOV - code coverage report
Current view: top level - include/llvm/Support - ArrayRecycler.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 23 23 100.0 %
Date: 2017-09-14 15:23:50 Functions: 8 8 100.0 %
Legend: Lines: hit not hit

          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      328566 : 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    42793314 :     if (Idx >= Bucket.size())
      46             :       return nullptr;
      47    26950164 :     FreeList *Entry = Bucket[Idx];
      48    13475082 :     if (!Entry)
      49             :       return nullptr;
      50             :     __asan_unpoison_memory_region(Entry, Capacity::get(Idx).getSize());
      51    14430358 :     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    18295840 :   void push(unsigned Idx, T *Ptr) {
      58             :     assert(Ptr && "Cannot recycle NULL pointer");
      59    18295840 :     FreeList *Entry = reinterpret_cast<FreeList*>(Ptr);
      60    36591680 :     if (Idx >= Bucket.size())
      61     1026452 :       Bucket.resize(size_t(Idx) + 1);
      62    36591682 :     Entry->Next = Bucket[Idx];
      63    36591682 :     Bucket[Idx] = Entry;
      64             :     __asan_poison_memory_region(Ptr, Capacity::get(Idx).getSize());
      65    18295841 :   }
      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     6455413 :     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    60919745 :       return Capacity(N ? Log2_64_Ceil(N) : 0);
      82             :     }
      83             : 
      84             :     /// Get the number of elements in an array with this capacity.
      85    37290665 :     size_t getSize() const { return size_t(1u) << Index; }
      86             : 
      87             :     /// Get the bucket number for this capacity.
      88    18295837 :     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     1363602 :     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      328156 :   }
     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      888298 :     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    21396657 :   T *allocate(Capacity Cap, AllocatorType &Allocator) {
     127             :     // Try to recycle an existing array.
     128    28611836 :     if (T *Ptr = pop(Cap.getBucket()))
     129             :       return Ptr;
     130             :     // Nope, get more memory.
     131    14181478 :     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    18295841 :     push(Cap.getBucket(), Ptr);
     140             :   }
     141             : };
     142             : 
     143             : } // end llvm namespace
     144             : 
     145             : #endif

Generated by: LCOV version 1.13