include/llvm/CodeGen/PBQP/CostAllocator.h

   1 //===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Defines classes conforming to the PBQP cost value manager concept.
  10 //
  11 // Cost value managers are memory managers for PBQP cost values (vectors and
  12 // matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
  13 // of edges on the largest function in SPEC2006).
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
  18 #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
  19
  20 #include "llvm/ADT/DenseSet.h"
  21 #include <algorithm>
  22 #include <cstdint>
  23 #include <memory>
  24
  25 namespace llvm {
  26 namespace PBQP {
  27
  28 template <typename ValueT> class ValuePool {
  29 public:
  30   using PoolRef = std::shared_ptr<const ValueT>;
  31
  32 private:
  33   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
  34   public:
  35     template <typename ValueKeyT>
  36     PoolEntry(ValuePool &Pool, ValueKeyT Value)
  37         : Pool(Pool), Value(std::move(Value)) {}
  38
  39     ~PoolEntry() { Pool.removeEntry(this); }
  40
  41     const ValueT &getValue() const { return Value; }
  42
  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 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   using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
  89
  90   EntrySetT EntrySet;
  91
  92   void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
  93
  94 public:
  95   template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
  96     typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
  97
  98     if (I != EntrySet.end())
  99       return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
 100
 101     auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
 102     EntrySet.insert(P.get());
 103     return PoolRef(std::move(P), &P->getValue());
 104   }
 105 };
 106
 107 template <typename VectorT, typename MatrixT> class PoolCostAllocator {
 108 private:
 109   using VectorCostPool = ValuePool<VectorT>;
 110   using MatrixCostPool = ValuePool<MatrixT>;
 111
 112 public:
 113   using Vector = VectorT;
 114   using Matrix = MatrixT;
 115   using VectorPtr = typename VectorCostPool::PoolRef;
 116   using MatrixPtr = typename MatrixCostPool::PoolRef;
 117
 118   template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
 119     return VectorPool.getValue(std::move(v));
 120   }
 121
 122   template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
 123     return MatrixPool.getValue(std::move(m));
 124   }
 125
 126 private:
 127   VectorCostPool VectorPool;
 128   MatrixCostPool MatrixPool;
 129 };
 130
 131 } // end namespace PBQP
 132 } // end namespace llvm
 133
 134 #endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H