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