Coverage Report

Created: 2019-07-24 05:18

/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
// 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
201
        : 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
37
41
        : 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
37
136
        : 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
37
24
        : Pool(Pool), Value(std::move(Value)) {}
38
39
201
    ~PoolEntry() { Pool.removeEntry(this); }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry::~PoolEntry()
Line
Count
Source
39
41
    ~PoolEntry() { Pool.removeEntry(this); }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry::~PoolEntry()
Line
Count
Source
39
136
    ~PoolEntry() { Pool.removeEntry(this); }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry::~PoolEntry()
Line
Count
Source
39
24
    ~PoolEntry() { Pool.removeEntry(this); }
40
41
2.44k
    const ValueT &getValue() const { return Value; }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntry::getValue() const
Line
Count
Source
41
512
    const ValueT &getValue() const { return Value; }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry::getValue() const
Line
Count
Source
41
402
    const ValueT &getValue() const { return Value; }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry::getValue() const
Line
Count
Source
41
1.53k
    const ValueT &getValue() const { return Value; }
42
43
  private:
44
    ValuePool &Pool;
45
    ValueT Value;
46
  };
47
48
  class PoolEntryDSInfo {
49
  public:
50
5.58k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getEmptyKey()
Line
Count
Source
50
1.30k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getEmptyKey()
Line
Count
Source
50
1.07k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getEmptyKey()
Line
Count
Source
50
3.20k
    static inline PoolEntry *getEmptyKey() { return nullptr; }
51
52
3.21k
    static inline PoolEntry *getTombstoneKey() {
53
3.21k
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
54
3.21k
    }
llvm::PBQP::ValuePool<llvm::PBQP::MDMatrix<llvm::PBQP::RegAlloc::MatrixMetadata> >::PoolEntryDSInfo::getTombstoneKey()
Line
Count
Source
52
667
    static inline PoolEntry *getTombstoneKey() {
53
667
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
54
667
    }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getTombstoneKey()
Line
Count
Source
52
474
    static inline PoolEntry *getTombstoneKey() {
53
474
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
54
474
    }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getTombstoneKey()
Line
Count
Source
52
2.07k
    static inline PoolEntry *getTombstoneKey() {
53
2.07k
      return reinterpret_cast<PoolEntry *>(static_cast<uintptr_t>(1));
54
2.07k
    }
55
56
    template <typename ValueKeyT>
57
1.00k
    static unsigned getHashValue(const ValueKeyT &C) {
58
1.00k
      return hash_value(C);
59
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
57
117
    static unsigned getHashValue(const ValueKeyT &C) {
58
117
      return hash_value(C);
59
117
    }
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
57
82
    static unsigned getHashValue(const ValueKeyT &C) {
58
82
      return hash_value(C);
59
82
    }
unsigned int llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getHashValue<llvm::PBQP::RegAlloc::AllowedRegVector>(llvm::PBQP::RegAlloc::AllowedRegVector const&)
Line
Count
Source
57
193
    static unsigned getHashValue(const ValueKeyT &C) {
58
193
      return hash_value(C);
59
193
    }
unsigned int llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getHashValue<llvm::PBQP::Vector>(llvm::PBQP::Vector const&)
Line
Count
Source
57
610
    static unsigned getHashValue(const ValueKeyT &C) {
58
610
      return hash_value(C);
59
610
    }
60
61
402
    static unsigned getHashValue(PoolEntry *P) {
62
402
      return getHashValue(P->getValue());
63
402
    }
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
61
82
    static unsigned getHashValue(PoolEntry *P) {
62
82
      return getHashValue(P->getValue());
63
82
    }
llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntryDSInfo::getHashValue(llvm::PBQP::ValuePool<llvm::PBQP::RegAlloc::AllowedRegVector>::PoolEntry*)
Line
Count
Source
61
48
    static unsigned getHashValue(PoolEntry *P) {
62
48
      return getHashValue(P->getValue());
63
48
    }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntryDSInfo::getHashValue(llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*)
Line
Count
Source
61
272
    static unsigned getHashValue(PoolEntry *P) {
62
272
      return getHashValue(P->getValue());
63
272
    }
64
65
    static unsigned getHashValue(const PoolEntry *P) {
66
      return getHashValue(P->getValue());
67
    }
68
69
    template <typename ValueKeyT1, typename ValueKeyT2>
70
737
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71
737
      return C1 == C2;
72
737
    }
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
70
111
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71
111
      return C1 == C2;
72
111
    }
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
70
45
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71
45
      return C1 == C2;
72
45
    }
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
70
153
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71
153
      return C1 == C2;
72
153
    }
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
70
428
    static bool isEqual(const ValueKeyT1 &C1, const ValueKeyT2 &C2) {
71
428
      return C1 == C2;
72
428
    }
73
74
    template <typename ValueKeyT>
75
1.36k
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76
1.36k
      if (P == getEmptyKey() || 
P == getTombstoneKey()869
)
77
625
        return false;
78
737
      return isEqual(C, P->getValue());
79
737
    }
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
75
145
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76
145
      if (P == getEmptyKey() || 
P == getTombstoneKey()111
)
77
34
        return false;
78
111
      return isEqual(C, P->getValue());
79
111
    }
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
75
150
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76
150
      if (P == getEmptyKey() || 
P == getTombstoneKey()77
)
77
105
        return false;
78
45
      return isEqual(C, P->getValue());
79
45
    }
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
75
193
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76
193
      if (P == getEmptyKey() || 
P == getTombstoneKey()153
)
77
40
        return false;
78
153
      return isEqual(C, P->getValue());
79
153
    }
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
75
874
    static bool isEqual(const ValueKeyT &C, PoolEntry *P) {
76
874
      if (P == getEmptyKey() || 
P == getTombstoneKey()528
)
77
446
        return false;
78
428
      return isEqual(C, P->getValue());
79
428
    }
80
81
2.97k
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82
2.97k
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()1.11k
)
83
2.28k
        return P1 == P2;
84
686
      return isEqual(P1->getValue(), P2);
85
686
    }
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
81
755
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82
755
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()232
)
83
605
        return P1 == P2;
84
150
      return isEqual(P1->getValue(), P2);
85
150
    }
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
81
648
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82
648
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()96
)
83
600
        return P1 == P2;
84
48
      return isEqual(P1->getValue(), P2);
85
48
    }
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
81
1.56k
    static bool isEqual(PoolEntry *P1, PoolEntry *P2) {
82
1.56k
      if (P1 == getEmptyKey() || 
P1 == getTombstoneKey()791
)
83
1.07k
        return P1 == P2;
84
488
      return isEqual(P1->getValue(), P2);
85
488
    }
86
  };
87
88
  using EntrySetT = DenseSet<PoolEntry *, PoolEntryDSInfo>;
89
90
  EntrySetT EntrySet;
91
92
201
  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
92
41
  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
92
24
  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
llvm::PBQP::ValuePool<llvm::PBQP::Vector>::removeEntry(llvm::PBQP::ValuePool<llvm::PBQP::Vector>::PoolEntry*)
Line
Count
Source
92
136
  void removeEntry(PoolEntry *P) { EntrySet.erase(P); }
93
94
public:
95
623
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
96
623
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
97
623
98
623
    if (I != EntrySet.end())
99
422
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
100
201
101
201
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
102
201
    EntrySet.insert(P.get());
103
201
    return PoolRef(std::move(P), &P->getValue());
104
201
  }
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
95
124
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
96
124
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
97
124
98
124
    if (I != EntrySet.end())
99
83
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
100
41
101
41
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
102
41
    EntrySet.insert(P.get());
103
41
    return PoolRef(std::move(P), &P->getValue());
104
41
  }
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
95
153
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
96
153
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
97
153
98
153
    if (I != EntrySet.end())
99
129
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
100
24
101
24
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
102
24
    EntrySet.insert(P.get());
103
24
    return PoolRef(std::move(P), &P->getValue());
104
24
  }
std::__1::shared_ptr<llvm::PBQP::Vector const> llvm::PBQP::ValuePool<llvm::PBQP::Vector>::getValue<llvm::PBQP::Vector>(llvm::PBQP::Vector)
Line
Count
Source
95
346
  template <typename ValueKeyT> PoolRef getValue(ValueKeyT ValueKey) {
96
346
    typename EntrySetT::iterator I = EntrySet.find_as(ValueKey);
97
346
98
346
    if (I != EntrySet.end())
99
210
      return PoolRef((*I)->shared_from_this(), &(*I)->getValue());
100
136
101
136
    auto P = std::make_shared<PoolEntry>(*this, std::move(ValueKey));
102
136
    EntrySet.insert(P.get());
103
136
    return PoolRef(std::move(P), &P->getValue());
104
136
  }
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
346
  template <typename VectorKeyT> VectorPtr getVector(VectorKeyT v) {
119
346
    return VectorPool.getValue(std::move(v));
120
346
  }
121
122
124
  template <typename MatrixKeyT> MatrixPtr getMatrix(MatrixKeyT m) {
123
124
    return MatrixPool.getValue(std::move(m));
124
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