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<const 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     const ValueT& getValue() const { return Value; }
  42   private:
  43     ValuePool &Pool;
  44     ValueT Value;
  45   };
  46
  47   class PoolEntryDSInfo {
  48   public:
  49     static inline PoolEntry* getEmptyKey() { return nullptr; }
  50
  51     static inline PoolEntry* getTombstoneKey() {
  52       return reinterpret_cast<PoolEntry*>(static_cast<uintptr_t>(1));
  53     }
  54
  55     template <typename ValueKeyT>
  56     static unsigned getHashValue(const ValueKeyT &C) {
  57       return hash_value(C);
  58     }
  59
  60     static unsigned getHashValue(PoolEntry *P) {
  61       return getHashValue(P->getValue());
  62     }
  63
  64     static unsigned getHashValue(const PoolEntry *P) {
  65       return getHashValue(P->getValue());
  66     }
  67
  68     template <typename ValueKeyT1, typename ValueKeyT2>
  69     static
  70     bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
  71       return C1 == C2;
  72     }
  73
  74     template <typename ValueKeyT>
  75     static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
  76       if (P == getEmptyKey() || P == getTombstoneKey())
  77         return false;
  78       return isEqual(C, P->getValue());
  79     }
  80
  81     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
  82       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
  83         return P1 == P2;
  84       return isEqual(P1->getValue(), P2);
  85     }
  86
  87   };
  88
  89   typedef DenseSet<PoolEntry*, PoolEntryDSInfo> EntrySetT;
  90
  91   EntrySetT EntrySet;
  92
  93   void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
  94
  95 public:
  96   template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
  97     typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
  98
  99     if (I != EntrySet.end())
 100       return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
 101
 102     auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
 103     EntrySet.insert(P.get());
 104     return PoolRef(std::move(P), &P->getValue());
 105   }
 106 };
 107
 108 template <typename VectorT, typename MatrixT>
 109 class PoolCostAllocator {
 110 private:
 111   typedef ValuePool<VectorT> VectorCostPool;
 112   typedef ValuePool<MatrixT> MatrixCostPool;
 113 public:
 114   typedef VectorT Vector;
 115   typedef MatrixT Matrix;
 116   typedef typename VectorCostPool::PoolRef VectorPtr;
 117   typedef typename MatrixCostPool::PoolRef MatrixPtr;
 118
 119   template <typename VectorKeyT>
 120   VectorPtr getVector(VectorKeyT v) { return VectorPool.getValue(std::move(v)); }
 121
 122   template <typename MatrixKeyT>
 123   MatrixPtr getMatrix(MatrixKeyT m) { return MatrixPool.getValue(std::move(m)); }
 124 private:
 125   VectorCostPool VectorPool;
 126   MatrixCostPool MatrixPool;
 127 };
 128
 129 } // namespace PBQP
 130 } // namespace llvm
 131
 132 #endif