Coverage Report

Created: 2018-07-19 03:59

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/CodeGen/PBQP/CostAllocator.h
Line
Count
Source
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
202
        : Pool(Pool), Value(std::move(Value)) {}
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry::PoolEntry<llvm::PBQP::Matrix>(llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >&, llvm::PBQP::Matrix)
Line
Count
Source
38
43
        : Pool(Pool), Value(std::move(Value)) {}
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry::PoolEntry<llvm::PBQP::Vector>(llvm::PBQP::ValuePool<llvm::PBQP::Vector>&, llvm::PBQP::Vector)
Line
Count
Source
38
135
        : Pool(Pool), Value(std::move(Value)) {}
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry::PoolEntry<llvm::PBQP::RegAlloc::AllowedRegVector>(llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>&, llvm::PBQP::RegAlloc::AllowedRegVector)
Line
Count
Source
38
24
        : Pool(Pool), Value(std::move(Value)) {}
39
40
202
    ~PoolEntry() { Pool.removeEntry(this); }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry::~PoolEntry()
Line
Count
Source
40
43
    ~PoolEntry() { Pool.removeEntry(this); }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry::~PoolEntry()
Line
Count
Source
40
135
    ~PoolEntry() { Pool.removeEntry(this); }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry::~PoolEntry()
Line
Count
Source
40
24
    ~PoolEntry() { Pool.removeEntry(this); }
41
42
2.41k
    const ValueT &getValue() const { return Value; }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry::getValue() const
Line
Count
Source
42
526
    const ValueT &getValue() const { return Value; }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry::getValue() const
Line
Count
Source
42
1.48k
    const ValueT &getValue() const { return Value; }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry::getValue() const
Line
Count
Source
42
402
    const ValueT &getValue() const { return Value; }
43
44
  private:
45
    ValuePool &Pool;
46
    ValueT Value;
47
  };
48
49
  class PoolEntryDSInfo {
50
  public:
51
5.55k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getEmptyKey()
Line
Count
Source
51
1.33k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getEmptyKey()
Line
Count
Source
51
3.14k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getEmptyKey()
Line
Count
Source
51
1.07k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
52
53
3.19k
    static inline PoolEntry *getTombstoneKey() {
54
3.19k
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
55
3.19k
    }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getTombstoneKey()
Line
Count
Source
53
687
    static inline PoolEntry *getTombstoneKey() {
54
687
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
55
687
    }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getTombstoneKey()
Line
Count
Source
53
2.03k
    static inline PoolEntry *getTombstoneKey() {
54
2.03k
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
55
2.03k
    }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getTombstoneKey()
Line
Count
Source
53
474
    static inline PoolEntry *getTombstoneKey() {
54
474
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
55
474
    }
56
57
    template <typename ValueKeyT>
58
1.00k
    static unsigned getHashValue(const ValueKeyT &C) {
59
1.00k
      return hash_value(C);
60
1.00k
    }
unsigned int llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getHashValue<llvm::PBQP::Matrix>(llvm::PBQP::Matrix const&)
Line
Count
Source
58
120
    static unsigned getHashValue(const ValueKeyT &C) {
59
120
      return hash_value(C);
60
120
    }
unsigned int llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getHashValue<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >(llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> const&)
Line
Count
Source
58
86
    static unsigned getHashValue(const ValueKeyT &C) {
59
86
      return hash_value(C);
60
86
    }
unsigned int llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getHashValue<llvm::PBQP::Vector>(llvm::PBQP::Vector const&)
Line
Count
Source
58
605
    static unsigned getHashValue(const ValueKeyT &C) {
59
605
      return hash_value(C);
60
605
    }
unsigned int llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getHashValue<llvm::PBQP::RegAlloc::AllowedRegVector>(llvm::PBQP::RegAlloc::AllowedRegVector const&)
Line
Count
Source
58
193
    static unsigned getHashValue(const ValueKeyT &C) {
59
193
      return hash_value(C);
60
193
    }
61
62
404
    static unsigned getHashValue(PoolEntry *P) {
63
404
      return getHashValue(P->getValue());
64
404
    }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getHashValue(llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry*)
Line
Count
Source
62
86
    static unsigned getHashValue(PoolEntry *P) {
63
86
      return getHashValue(P->getValue());
64
86
    }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getHashValue(llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*)
Line
Count
Source
62
270
    static unsigned getHashValue(PoolEntry *P) {
63
270
      return getHashValue(P->getValue());
64
270
    }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getHashValue(llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry*)
Line
Count
Source
62
48
    static unsigned getHashValue(PoolEntry *P) {
63
48
      return getHashValue(P->getValue());
64
48
    }
65
66
    static unsigned getHashValue(const PoolEntry *P) {
67
      return getHashValue(P->getValue());
68
    }
69
70
    template <typename ValueKeyT1, typename ValueKeyT2>
71
726
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72
726
      return C1 == C2;
73
726
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::isEqual<llvm::PBQP::Matrix, llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >(llvm::PBQP::Matrix const&, llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> const&)
Line
Count
Source
71
112
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72
112
      return C1 == C2;
73
112
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::isEqual<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata>, llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >(llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> const&, llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> const&)
Line
Count
Source
71
47
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72
47
      return C1 == C2;
73
47
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::isEqual<llvm::PBQP::Vector, llvm::PBQP::Vector>(llvm::PBQP::Vector const&, llvm::PBQP::Vector const&)
Line
Count
Source
71
414
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72
414
      return C1 == C2;
73
414
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::isEqual<llvm::PBQP::RegAlloc::AllowedRegVector, llvm::PBQP::RegAlloc::AllowedRegVector>(llvm::PBQP::RegAlloc::AllowedRegVector const&, llvm::PBQP::RegAlloc::AllowedRegVector const&)
Line
Count
Source
71
153
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
72
153
      return C1 == C2;
73
153
    }
74
75
    template <typename ValueKeyT>
76
1.33k
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
77
1.33k
      if (P == getEmptyKey() || 
P == getTombstoneKey()854
)
78
612
        return false;
79
726
      return isEqual(C, P->getValue());
80
726
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::isEqual<llvm::PBQP::Matrix>(llvm::PBQP::Matrix const&, llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry*)
Line
Count
Source
76
148
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
77
148
      if (P == getEmptyKey() || 
P == getTombstoneKey()112
)
78
36
        return false;
79
112
      return isEqual(C, P->getValue());
80
112
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::isEqual<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >(llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> const&, llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry*)
Line
Count
Source
76
154
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
77
154
      if (P == getEmptyKey() || 
P == getTombstoneKey()79
)
78
107
        return false;
79
47
      return isEqual(C, P->getValue());
80
47
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::isEqual<llvm::PBQP::Vector>(llvm::PBQP::Vector const&, llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*)
Line
Count
Source
76
843
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
77
843
      if (P == getEmptyKey() || 
P == getTombstoneKey()510
)
78
429
        return false;
79
414
      return isEqual(C, P->getValue());
80
414
    }
bool llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::isEqual<llvm::PBQP::RegAlloc::AllowedRegVector>(llvm::PBQP::RegAlloc::AllowedRegVector const&, llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry*)
Line
Count
Source
76
193
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
77
193
      if (P == getEmptyKey() || 
P == getTombstoneKey()153
)
78
40
        return false;
79
153
      return isEqual(C, P->getValue());
80
153
    }
81
82
2.96k
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83
2.96k
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()1.11k
)
84
2.30k
        return P1 == P2;
85
664
      return isEqual(P1->getValue(), P2);
86
664
    }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::isEqual(llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry*, llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry*)
Line
Count
Source
82
767
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83
767
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()240
)
84
613
        return P1 == P2;
85
154
      return isEqual(P1->getValue(), P2);
86
154
    }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::isEqual(llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*, llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*)
Line
Count
Source
82
1.55k
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83
1.55k
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()776
)
84
1.08k
        return P1 == P2;
85
462
      return isEqual(P1->getValue(), P2);
86
462
    }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::isEqual(llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry*, llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry*)
Line
Count
Source
82
648
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
83
648
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()96
)
84
600
        return P1 == P2;
85
48
      return isEqual(P1->getValue(), P2);
86
48
    }
87
  };
88
89
  using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
90
91
  EntrySetT EntrySet;
92
93
202
  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::removeEntry(llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry*)
Line
Count
Source
93
43
  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::removeEntry(llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*)
Line
Count
Source
93
135
  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::removeEntry(llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry*)
Line
Count
Source
93
24
  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
94
95
public:
96
623
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
97
623
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
98
623
99
623
    if (I != EntrySet.end())
100
421
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
101
202
102
202
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
103
202
    EntrySet.insert(P.get());
104
202
    return PoolRef(std::move(P), &P->getValue());
105
202
  }
std::__1::shared_ptr<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> const> llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::getValue<llvm::PBQP::Matrix>(llvm::PBQP::Matrix)
Line
Count
Source
96
127
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
97
127
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
98
127
99
127
    if (I != EntrySet.end())
100
84
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
101
43
102
43
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
103
43
    EntrySet.insert(P.get());
104
43
    return PoolRef(std::move(P), &P->getValue());
105
43
  }
std::__1::shared_ptr<llvm::PBQP::Vector const> llvm::PBQP::ValuePool<llvm::PBQP::Vector>::getValue<llvm::PBQP::Vector>(llvm::PBQP::Vector)
Line
Count
Source
96
343
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
97
343
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
98
343
99
343
    if (I != EntrySet.end())
100
208
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
101
135
102
135
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
103
135
    EntrySet.insert(P.get());
104
135
    return PoolRef(std::move(P), &P->getValue());
105
135
  }
std::__1::shared_ptr<llvm::PBQP::RegAlloc::AllowedRegVector const> llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::getValue<llvm::PBQP::RegAlloc::AllowedRegVector>(llvm::PBQP::RegAlloc::AllowedRegVector)
Line
Count
Source
96
153
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
97
153
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
98
153
99
153
    if (I != EntrySet.end())
100
129
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
101
24
102
24
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
103
24
    EntrySet.insert(P.get());
104
24
    return PoolRef(std::move(P), &P->getValue());
105
24
  }
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
343
  template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
120
343
    return VectorPool.getValue(std::move(v));
121
343
  }
122
123
127
  template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
124
127
    return MatrixPool.getValue(std::move(m));
125
127
  }
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