Home | History | Annotate | Download | only in Support 
      1 //==- llvm/Support/Recycler.h - Recycling Allocator --------------*- 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 Recycler class template.  See the doxygen comment for
     11 // Recycler for more details.
     12 //
     13 //===----------------------------------------------------------------------===//
     14 
     15 #ifndef LLVM_SUPPORT_RECYCLER_H
     16 #define LLVM_SUPPORT_RECYCLER_H
     17 
     18 #include "llvm/ADT/ilist.h"
     19 #include "llvm/Support/AlignOf.h"
     20 #include "llvm/Support/Allocator.h"
     21 #include "llvm/Support/ErrorHandling.h"
     22 #include <cassert>
     23 
     24 namespace llvm {
     25 
     26 /// PrintRecyclingAllocatorStats - Helper for RecyclingAllocator for
     27 /// printing statistics.
     28 ///
     29 void PrintRecyclerStats(size_t Size, size_t Align, size_t FreeListSize);
     30 
     31 /// Recycler - This class manages a linked-list of deallocated nodes
     32 /// and facilitates reusing deallocated memory in place of allocating
     33 /// new memory.
     34 ///
     35 template<class T, size_t Size = sizeof(T), size_t Align = AlignOf<T>::Alignment>
     36 class Recycler {
     37   struct FreeNode {
     38     FreeNode *Next;
     39   };
     40 
     41   /// List of nodes that have deleted contents and are not in active use.
     42   FreeNode *FreeList = nullptr;
     43 
     44   FreeNode *pop_val() {
     45     auto *Val = FreeList;
     46     FreeList = FreeList->Next;
     47     return Val;
     48   }
     49 
     50   void push(FreeNode *N) {
     51     N->Next = FreeList;
     52     FreeList = N;
     53   }
     54 
     55 public:
     56   ~Recycler() {
     57     // If this fails, either the callee has lost track of some allocation,
     58     // or the callee isn't tracking allocations and should just call
     59     // clear() before deleting the Recycler.
     60     assert(!FreeList && "Non-empty recycler deleted!");
     61   }
     62 
     63   /// clear - Release all the tracked allocations to the allocator. The
     64   /// recycler must be free of any tracked allocations before being
     65   /// deleted; calling clear is one way to ensure this.
     66   template<class AllocatorType>
     67   void clear(AllocatorType &Allocator) {
     68     while (FreeList) {
     69       T *t = reinterpret_cast<T *>(pop_val());
     70       Allocator.Deallocate(t);
     71     }
     72   }
     73 
     74   /// Special case for BumpPtrAllocator which has an empty Deallocate()
     75   /// function.
     76   ///
     77   /// There is no need to traverse the free list, pulling all the objects into
     78   /// cache.
     79   void clear(BumpPtrAllocator &) { FreeList = nullptr; }
     80 
     81   template<class SubClass, class AllocatorType>
     82   SubClass *Allocate(AllocatorType &Allocator) {
     83     static_assert(AlignOf<SubClass>::Alignment <= Align,
     84                   "Recycler allocation alignment is less than object align!");
     85     static_assert(sizeof(SubClass) <= Size,
     86                   "Recycler allocation size is less than object size!");
     87     return FreeList ? reinterpret_cast<SubClass *>(pop_val())
     88                     : static_cast<SubClass *>(Allocator.Allocate(Size, Align));
     89   }
     90 
     91   template<class AllocatorType>
     92   T *Allocate(AllocatorType &Allocator) {
     93     return Allocate<T>(Allocator);
     94   }
     95 
     96   template<class SubClass, class AllocatorType>
     97   void Deallocate(AllocatorType & /*Allocator*/, SubClass* Element) {
     98     push(reinterpret_cast<FreeNode *>(Element));
     99   }
    100 
    101   void PrintStats();
    102 };
    103 
    104 template <class T, size_t Size, size_t Align>
    105 void Recycler<T, Size, Align>::PrintStats() {
    106   size_t S = 0;
    107   for (auto *I = FreeList; I; I = I->Next)
    108     ++S;
    109   PrintRecyclerStats(Size, Align, S);
    110 }
    111 
    112 }
    113 
    114 #endif
    115