Home | History | Annotate | Download | only in PBQP 
      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
    133