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 ValueT>
  29 class ValuePool {
  30 public:
  31   typedef std::shared_ptr<ValueT> PoolRef;
  32
  33 private:
  34
  35   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
  36   public:
  37     template <typename ValueKeyT>
  38     PoolEntry(ValuePool &Pool, ValueKeyT Value)
  39         : Pool(Pool), Value(std::move(Value)) {}
  40     ~PoolEntry() { Pool.removeEntry(this); }
  41     ValueT& getValue() { return Value; }
  42     const ValueT& getValue() const { return Value; }
  43   private:
  44     ValuePool &Pool;
  45     ValueT Value;
  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 ValueKeyT>
  57     static unsigned getHashValue(const ValueKeyT &C) {
  58       return hash_value(C);
  59     }
  60
  61     static unsigned getHashValue(PoolEntry *P) {
  62       return getHashValue(P->getValue());
  63     }
  64
  65     static unsigned getHashValue(const PoolEntry *P) {
  66       return getHashValue(P->getValue());
  67     }
  68
  69     template <typename ValueKeyT1, typename ValueKeyT2>
  70     static
  71     bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
  72       return C1 == C2;
  73     }
  74
  75     template <typename ValueKeyT>
  76     static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
  77       if (P == getEmptyKey() || P == getTombstoneKey())
  78         return false;
  79       return isEqual(C, P->getValue());
  80     }
  81
  82     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
  83       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
  84         return P1 == P2;
  85       return isEqual(P1->getValue(), P2);
  86     }
  87
  88   };
  89
  90   typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT;
  91
  92   EntrySetT EntrySet;
  93
  94   void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
  95
  96 public:
  97   template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
  98     typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
  99
 100     if (I != EntrySet.end())
 101       return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
 102
 103     auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
 104     EntrySet.insert(P.get());
 105     return PoolRef(std::move(P), &P->getValue());
 106   }
 107 };
 108
 109 template <typename VectorT, typename MatrixT>
 110 class PoolCostAllocator {
 111 private:
 112   typedef ValuePool<VectorT> VectorCostPool;
 113   typedef ValuePool<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.getValue(std::move(v)); }
 122
 123   template <typename MatrixKeyT>
 124   MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); }
 125 private:
 126   VectorCostPool VectorPool;
 127   MatrixCostPool MatrixPool;
 128 };
 129
 130 } // namespace PBQP
 131 } // namespace llvm
 132
 133 #endif