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 <memory>
  22 #include <set>
  23 #include <type_traits>
  24
  25 namespace llvm {
  26 namespace PBQP {
  27
  28 template <typename CostT,
  29           typename CostKeyTComparator>
  30 class CostPool {
  31 public:
  32   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
  33   public:
  34     template <typename CostKeyT>
  35     PoolEntry(CostPool &pool, CostKeyT cost)
  36         : pool(pool), cost(std::move(cost)) {}
  37     ~PoolEntry() { pool.removeEntry(this); }
  38     CostT& getCost() { return cost; }
  39     const CostT& getCost() const { return cost; }
  40   private:
  41     CostPool &pool;
  42     CostT cost;
  43   };
  44
  45   typedef std::shared_ptr<CostT> PoolRef;
  46
  47 private:
  48   class EntryComparator {
  49   public:
  50     template <typename CostKeyT>
  51     typename std::enable_if<
  52                !std::is_same<PoolEntry*,
  53                              typename std::remove_const<CostKeyT>::type>::value,
  54                bool>::type
  55     operator()(const PoolEntry* a, const CostKeyT &b) {
  56       return compare(a->getCost(), b);
  57     }
  58     bool operator()(const PoolEntry* a, const PoolEntry* b) {
  59       return compare(a->getCost(), b->getCost());
  60     }
  61   private:
  62     CostKeyTComparator compare;
  63   };
  64
  65   typedef std::set<PoolEntry*, EntryComparator> EntrySet;
  66
  67   EntrySet entrySet;
  68
  69   void removeEntry(PoolEntry *p) { entrySet.erase(p); }
  70
  71 public:
  72   template <typename CostKeyT> PoolRef getCost(CostKeyT costKey) {
  73     typename EntrySet::iterator itr =
  74       std::lower_bound(entrySet.begin(), entrySet.end(), costKey,
  75                        EntryComparator());
  76
  77     if (itr != entrySet.end() && costKey == (*itr)->getCost())
  78       return PoolRef((*itr)->shared_from_this(), &(*itr)->getCost());
  79
  80     auto p = std::make_shared<PoolEntry>(*this, std::move(costKey));
  81     entrySet.insert(itr, p.get());
  82     return PoolRef(std::move(p), &p->getCost());
  83   }
  84 };
  85
  86 template <typename VectorT, typename VectorTComparator,
  87           typename MatrixT, typename MatrixTComparator>
  88 class PoolCostAllocator {
  89 private:
  90   typedef CostPool<VectorT, VectorTComparator> VectorCostPool;
  91   typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
  92 public:
  93   typedef VectorT Vector;
  94   typedef MatrixT Matrix;
  95   typedef typename VectorCostPool::PoolRef VectorPtr;
  96   typedef typename MatrixCostPool::PoolRef MatrixPtr;
  97
  98   template <typename VectorKeyT>
  99   VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
 100
 101   template <typename MatrixKeyT>
 102   MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
 103 private:
 104   VectorCostPool vectorPool;
 105   MatrixCostPool matrixPool;
 106 };
 107
 108 } // namespace PBQP
 109 } // namespace llvm
 110
 111 #endif