include/llvm/CodeGen/PBQP/CostAllocator.h

   1 //===---------- CostAllocator.h - PBQP Cost 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 // Defines classes conforming to the PBQP cost value manager concept.
  11 //
  12 // Cost value managers are memory managers for PBQP cost values (vectors and
  13 // matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
  14 // of edges on the largest function in SPEC2006).
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
  19 #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
  20
  21 #include <set>
  22 #include <type_traits>
  23
  24 namespace PBQP {
  25
  26 template <typename CostT,
  27           typename CostKeyTComparator>
  28 class CostPool {
  29 public:
  30
  31   class PoolEntry {
  32   public:
  33     template <typename CostKeyT>
  34     PoolEntry(CostPool &pool, CostKeyT cost)
  35       : pool(pool), cost(std::move(cost)), refCount(0) {}
  36     ~PoolEntry() { pool.removeEntry(this); }
  37     void incRef() { ++refCount; }
  38     bool decRef() { --refCount; return (refCount == 0); }
  39     CostT& getCost() { return cost; }
  40     const CostT& getCost() const { return cost; }
  41   private:
  42     CostPool &pool;
  43     CostT cost;
  44     std::size_t refCount;
  45   };
  46
  47   class PoolRef {
  48   public:
  49     PoolRef(PoolEntry *entry) : entry(entry) {
  50       this->entry->incRef();
  51     }
  52     PoolRef(const PoolRef &r) {
  53       entry = r.entry;
  54       entry->incRef();
  55     }
  56     PoolRef& operator=(const PoolRef &r) {
  57       assert(entry != nullptr && "entry should not be null.");
  58       PoolEntry *temp = r.entry;
  59       temp->incRef();
  60       entry->decRef();
  61       entry = temp;
  62       return *this;
  63     }
  64
  65     ~PoolRef() {
  66       if (entry->decRef())
  67         delete entry;
  68     }
  69     void reset(PoolEntry *entry) {
  70       entry->incRef();
  71       this->entry->decRef();
  72       this->entry = entry;
  73     }
  74     CostT& operator*() { return entry->getCost(); }
  75     const CostT& operator*() const { return entry->getCost(); }
  76     CostT* operator->() { return &entry->getCost(); }
  77     const CostT* operator->() const { return &entry->getCost(); }
  78   private:
  79     PoolEntry *entry;
  80   };
  81
  82 private:
  83   class EntryComparator {
  84   public:
  85     template <typename CostKeyT>
  86     typename std::enable_if<
  87                !std::is_same<PoolEntry*,
  88                              typename std::remove_const<CostKeyT>::type>::value,
  89                bool>::type
  90     operator()(const PoolEntry* a, const CostKeyT &b) {
  91       return compare(a->getCost(), b);
  92     }
  93     bool operator()(const PoolEntry* a, const PoolEntry* b) {
  94       return compare(a->getCost(), b->getCost());
  95     }
  96   private:
  97     CostKeyTComparator compare;
  98   };
  99
 100   typedef std::set<PoolEntry*, EntryComparator> EntrySet;
 101
 102   EntrySet entrySet;
 103
 104   void removeEntry(PoolEntry *p) { entrySet.erase(p); }
 105
 106 public:
 107
 108   template <typename CostKeyT>
 109   PoolRef getCost(CostKeyT costKey) {
 110     typename EntrySet::iterator itr =
 111       std::lower_bound(entrySet.begin(), entrySet.end(), costKey,
 112                        EntryComparator());
 113
 114     if (itr != entrySet.end() && costKey == (*itr)->getCost())
 115       return PoolRef(*itr);
 116
 117     PoolEntry *p = new PoolEntry(*this, std::move(costKey));
 118     entrySet.insert(itr, p);
 119     return PoolRef(p);
 120   }
 121 };
 122
 123 template <typename VectorT, typename VectorTComparator,
 124           typename MatrixT, typename MatrixTComparator>
 125 class PoolCostAllocator {
 126 private:
 127   typedef CostPool<VectorT, VectorTComparator> VectorCostPool;
 128   typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
 129 public:
 130   typedef VectorT Vector;
 131   typedef MatrixT Matrix;
 132   typedef typename VectorCostPool::PoolRef VectorPtr;
 133   typedef typename MatrixCostPool::PoolRef MatrixPtr;
 134
 135   template <typename VectorKeyT>
 136   VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
 137
 138   template <typename MatrixKeyT>
 139   MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
 140 private:
 141   VectorCostPool vectorPool;
 142   MatrixCostPool matrixPool;
 143 };
 144
 145 }
 146
 147 #endif