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>
  72   std::shared_ptr<CostT> 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 std::shared_ptr<CostT>((*itr)->shared_from_this(),
  79                                     &(*itr)->getCost());
  80
  81     auto p = std::make_shared<PoolEntry>(*this, std::move(costKey));
  82     entrySet.insert(itr, p.get());
  83     return std::shared_ptr<CostT>(std::move(p), &p->getCost());
  84   }
  85 };
  86
  87 template <typename VectorT, typename VectorTComparator,
  88           typename MatrixT, typename MatrixTComparator>
  89 class PoolCostAllocator {
  90 private:
  91   typedef CostPool<VectorT, VectorTComparator> VectorCostPool;
  92   typedef CostPool<MatrixT, MatrixTComparator> MatrixCostPool;
  93 public:
  94   typedef VectorT Vector;
  95   typedef MatrixT Matrix;
  96   typedef typename VectorCostPool::PoolRef VectorPtr;
  97   typedef typename MatrixCostPool::PoolRef MatrixPtr;
  98
  99   template <typename VectorKeyT>
 100   VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
 101
 102   template <typename MatrixKeyT>
 103   MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
 104 private:
 105   VectorCostPool vectorPool;
 106   MatrixCostPool matrixPool;
 107 };
 108
 109 }
 110
 111 #endif