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 <algorithm>
     23 #include <cstdint>
     24 #include <memory>
     25 
     26 namespace llvm {
     27 namespace PBQP {
     28 
     29 template <typename ValueT> class ValuePool {
     30 public:
     31   using PoolRef = std::shared_ptr<const ValueT>;
     32 
     33 private:
     34   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
     35   public:
     36     template <typename ValueKeyT>
     37     PoolEntry(ValuePool &Pool, ValueKeyT Value)
     38         : Pool(Pool), Value(std::move(Value)) {}
     39 
     40     ~PoolEntry() { Pool.removeEntry(this); }
     41 
     42     const ValueT &getValue() const { return Value; }
     43 
     44   private:
     45     ValuePool &Pool;
     46     ValueT Value;
     47   };
     48 
     49   class PoolEntryDSInfo {
     50   public:
     51     static inline PoolEntry *getEmptyKey() { return nullptr; }
     52 
     53     static inline PoolEntry *getTombstoneKey() {
     54       return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
     55     }
     56 
     57     template <typename ValueKeyT>
     58     static unsigned getHashValue(const ValueKeyT &C) {
     59       return hash_value(C);
     60     }
     61 
     62     static unsigned getHashValue(PoolEntry *P) {
     63       return getHashValue(P->getValue());
     64     }
     65 
     66     static unsigned getHashValue(const PoolEntry *P) {
     67       return getHashValue(P->getValue());
     68     }
     69 
     70     template <typename ValueKeyT1, typename ValueKeyT2>
     71     static 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   using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
     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> class PoolCostAllocator {
    109 private:
    110   using VectorCostPool = ValuePool<VectorT>;
    111   using MatrixCostPool = ValuePool<MatrixT>;
    112 
    113 public:
    114   using Vector = VectorT;
    115   using Matrix = MatrixT;
    116   using VectorPtr = typename VectorCostPool::PoolRef;
    117   using MatrixPtr = typename MatrixCostPool::PoolRef;
    118 
    119   template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
    120     return VectorPool.getValue(std::move(v));
    121   }
    122 
    123   template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
    124     return MatrixPool.getValue(std::move(m));
    125   }
    126 
    127 private:
    128   VectorCostPool VectorPool;
    129   MatrixCostPool MatrixPool;
    130 };
    131 
    132 } // end namespace PBQP
    133 } // end namespace llvm
    134 
    135 #endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
    136