CodeGen/PBQP/CostAllocator.h

0001 //===- CostAllocator.h - PBQP Cost Allocator --------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // Defines classes conforming to the PBQP cost value manager concept.
0010 //
0011 // Cost value managers are memory managers for PBQP cost values (vectors and
0012 // matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands
0013 // of edges on the largest function in SPEC2006).
0014 //
0015 //===----------------------------------------------------------------------===//
0016
0017 #ifndef LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
0018 #define LLVM_CODEGEN_PBQP_COSTALLOCATOR_H
0019
0020 #include "llvm/ADT/DenseSet.h"
0021 #include <algorithm>
0022 #include <cstdint>
0023 #include <memory>
0024
0025 namespace llvm {
0026 namespace PBQP {
0027
0028 template <typename ValueT> class ValuePool {
0029 public:
0030   using PoolRef = std::shared_ptr<const ValueT>;
0031
0032 private:
0033   class PoolEntry : public std::enable_shared_from_this<PoolEntry> {
0034   public:
0035     template <typename ValueKeyT>
0036     PoolEntry(ValuePool &Pool, ValueKeyT Value)
0037         : Pool(Pool), Value(std::move(Value)) {}
0038
0039     ~PoolEntry() { Pool.removeEntry(this); }
0040
0041     const ValueT &getValue() const { return Value; }
0042
0043   private:
0044     ValuePool &Pool;
0045     ValueT Value;
0046   };
0047
0048   class PoolEntryDSInfo {
0049   public:
0050     static inline PoolEntry *getEmptyKey() { return nullptr; }
0051
0052     static inline PoolEntry *getTombstoneKey() {
0053       return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
0054     }
0055
0056     template <typename ValueKeyT>
0057     static unsigned getHashValue(const ValueKeyT &C) {
0058       return hash_value(C);
0059     }
0060
0061     static unsigned getHashValue(PoolEntry *P) {
0062       return getHashValue(P->getValue());
0063     }
0064
0065     static unsigned getHashValue(const PoolEntry *P) {
0066       return getHashValue(P->getValue());
0067     }
0068
0069     template <typename ValueKeyT1, typename ValueKeyT2>
0070     static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
0071       return C1 == C2;
0072     }
0073
0074     template <typename ValueKeyT>
0075     static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
0076       if (P == getEmptyKey() || P == getTombstoneKey())
0077         return false;
0078       return isEqual(C, P->getValue());
0079     }
0080
0081     static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
0082       if (P1 == getEmptyKey() || P1 == getTombstoneKey())
0083         return P1 == P2;
0084       return isEqual(P1->getValue(), P2);
0085     }
0086   };
0087
0088   using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
0089
0090   EntrySetT EntrySet;
0091
0092   void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
0093
0094 public:
0095   template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
0096     typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
0097
0098     if (I != EntrySet.end())
0099       return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
0100
0101     auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
0102     EntrySet.insert(P.get());
0103     return PoolRef(P, &P->getValue());
0104   }
0105 };
0106
0107 template <typename VectorT, typename MatrixT> class PoolCostAllocator {
0108 private:
0109   using VectorCostPool = ValuePool<VectorT>;
0110   using MatrixCostPool = ValuePool<MatrixT>;
0111
0112 public:
0113   using Vector = VectorT;
0114   using Matrix = MatrixT;
0115   using VectorPtr = typename VectorCostPool::PoolRef;
0116   using MatrixPtr = typename MatrixCostPool::PoolRef;
0117
0118   template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
0119     return VectorPool.getValue(std::move(v));
0120   }
0121
0122   template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
0123     return MatrixPool.getValue(std::move(m));
0124   }
0125
0126 private:
0127   VectorCostPool VectorPool;
0128   MatrixCostPool MatrixPool;
0129 };
0130
0131 } // end namespace PBQP
0132 } // end namespace llvm
0133
0134 #endif // LLVM_CODEGEN_PBQP_COSTALLOCATOR_H