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 "llvm/ADT/DenseSet.h"
  22 #include <memory>
  23 #include <type_traits>
  24
  25 namespace llvm {
  26 namespace PBQP {
  27
  28 template <typename CostT>
  29 class CostPool {
  30 public:
  31   typedef std::shared_ptr<CostT> PoolRef;
  32
  33 private:
  34
  35   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
  36   public:
  37     template <typename CostKeyT>
  38     PoolEntry(CostPool &pool, CostKeyT cost)
  39         : pool(pool), cost(std::move(cost)) {}
  40     ~PoolEntry() { pool.removeEntry(this); }
  41     CostT& getCost() { return cost; }
  42     const CostT& getCost() const { return cost; }
  43   private:
  44     CostPool &pool;
  45     CostT cost;
  46   };
  47
  48   class PoolEntryDSInfo {
  49   public:
  50     static inline PoolEntry* getEmptyKey() { return nullptr; }
  51
  52     static inline PoolEntry* getTombstoneKey() {
  53       return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
  54     }
  55
  56     template <typename CostKeyT>
  57     static unsigned getHashValue(const CostKeyT &C) {
  58       return hash_value(C);
  59     }
  60
  61     static unsigned getHashValue(PoolEntry *P) {
  62       return getHashValue(P->getCost());
  63     }
  64
  65     static unsigned getHashValue(const PoolEntry *P) {
  66       return getHashValue(P->getCost());
  67     }
  68
  69     template <typename CostKeyT1, typename CostKeyT2>
  70     static
  71     bool isEqual(const CostKeyT1 &C1, const CostKeyT2 &C2) {
  72       return C1 == C2;
  73     }
  74
  75     template <typename CostKeyT>
  76     static bool isEqual(const CostKeyT &C, PoolEntry *P) {
  77       if (P == getEmptyKey() || P == getTombstoneKey())
  78         return false;
  79       return isEqual(C, P->getCost());
  80     }
  81
  82     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
  83       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
  84         return P1 == P2;
  85       return isEqual(P1->getCost(), P2);
  86     }
  87
  88   };
  89
  90   typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySet;
  91
  92   EntrySet entrySet;
  93
  94   void removeEntry(PoolEntry *p) { entrySet.erase(p); }
  95
  96 public:
  97   template <typename CostKeyT> PoolRef getCost(CostKeyT costKey) {
  98     typename EntrySet::iterator itr = entrySet.find_as(costKey);
  99
 100     if (itr != entrySet.end())
 101       return PoolRef((*itr)->shared_from_this(), &(*itr)->getCost());
 102
 103     auto p = std::make_shared<PoolEntry>(*this, std::move(costKey));
 104     entrySet.insert(p.get());
 105     return PoolRef(std::move(p), &p->getCost());
 106   }
 107 };
 108
 109 template <typename VectorT, typename MatrixT>
 110 class PoolCostAllocator {
 111 private:
 112   typedef CostPool<VectorT> VectorCostPool;
 113   typedef CostPool<MatrixT> MatrixCostPool;
 114 public:
 115   typedef VectorT Vector;
 116   typedef MatrixT Matrix;
 117   typedef typename VectorCostPool::PoolRef VectorPtr;
 118   typedef typename MatrixCostPool::PoolRef MatrixPtr;
 119
 120   template <typename VectorKeyT>
 121   VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); }
 122
 123   template <typename MatrixKeyT>
 124   MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); }
 125 private:
 126   VectorCostPool vectorPool;
 127   MatrixCostPool matrixPool;
 128 };
 129
 130 } // namespace PBQP
 131 } // namespace llvm
 132
 133 #endif