/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/ADT/SparseSet.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- llvm/ADT/SparseSet.h - Sparse set ------------------------*- 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 | | // This file defines the SparseSet class derived from the version described in |
10 | | // Briggs, Torczon, "An efficient representation for sparse sets", ACM Letters |
11 | | // on Programming Languages and Systems, Volume 2 Issue 1-4, March-Dec. 1993. |
12 | | // |
13 | | // A sparse set holds a small number of objects identified by integer keys from |
14 | | // a moderately sized universe. The sparse set uses more memory than other |
15 | | // containers in order to provide faster operations. |
16 | | // |
17 | | //===----------------------------------------------------------------------===// |
18 | | |
19 | | #ifndef LLVM_ADT_SPARSESET_H |
20 | | #define LLVM_ADT_SPARSESET_H |
21 | | |
22 | | #include "llvm/ADT/STLExtras.h" |
23 | | #include "llvm/ADT/SmallVector.h" |
24 | | #include "llvm/Support/Allocator.h" |
25 | | #include <cassert> |
26 | | #include <cstdint> |
27 | | #include <cstdlib> |
28 | | #include <limits> |
29 | | #include <utility> |
30 | | |
31 | | namespace llvm { |
32 | | |
33 | | /// SparseSetValTraits - Objects in a SparseSet are identified by keys that can |
34 | | /// be uniquely converted to a small integer less than the set's universe. This |
35 | | /// class allows the set to hold values that differ from the set's key type as |
36 | | /// long as an index can still be derived from the value. SparseSet never |
37 | | /// directly compares ValueT, only their indices, so it can map keys to |
38 | | /// arbitrary values. SparseSetValTraits computes the index from the value |
39 | | /// object. To compute the index from a key, SparseSet uses a separate |
40 | | /// KeyFunctorT template argument. |
41 | | /// |
42 | | /// A simple type declaration, SparseSet<Type>, handles these cases: |
43 | | /// - unsigned key, identity index, identity value |
44 | | /// - unsigned key, identity index, fat value providing getSparseSetIndex() |
45 | | /// |
46 | | /// The type declaration SparseSet<Type, UnaryFunction> handles: |
47 | | /// - unsigned key, remapped index, identity value (virtual registers) |
48 | | /// - pointer key, pointer-derived index, identity value (node+ID) |
49 | | /// - pointer key, pointer-derived index, fat value with getSparseSetIndex() |
50 | | /// |
51 | | /// Only other, unexpected cases require specializing SparseSetValTraits. |
52 | | /// |
53 | | /// For best results, ValueT should not require a destructor. |
54 | | /// |
55 | | template<typename ValueT> |
56 | | struct SparseSetValTraits { |
57 | 217M | static unsigned getValIndex(const ValueT &Val) { |
58 | 217M | return Val.getSparseSetIndex(); |
59 | 217M | } llvm::SparseSetValTraits<llvm::LiveRegSet::IndexMaskPair>::getValIndex(llvm::LiveRegSet::IndexMaskPair const&) Line | Count | Source | 57 | 42.7M | static unsigned getValIndex(const ValueT &Val) { | 58 | 42.7M | return Val.getSparseSetIndex(); | 59 | 42.7M | } |
llvm::SparseSetValTraits<llvm::LiveRegUnit>::getValIndex(llvm::LiveRegUnit const&) Line | Count | Source | 57 | 5.08M | static unsigned getValIndex(const ValueT &Val) { | 58 | 5.08M | return Val.getSparseSetIndex(); | 59 | 5.08M | } |
llvm::SparseSetValTraits<llvm::VReg2SUnit>::getValIndex(llvm::VReg2SUnit const&) Line | Count | Source | 57 | 24.1M | static unsigned getValIndex(const ValueT &Val) { | 58 | 24.1M | return Val.getSparseSetIndex(); | 59 | 24.1M | } |
RegAllocFast.cpp:llvm::SparseSetValTraits<(anonymous namespace)::RegAllocFast::LiveReg>::getValIndex((anonymous namespace)::RegAllocFast::LiveReg const&) Line | Count | Source | 57 | 453k | static unsigned getValIndex(const ValueT &Val) { | 58 | 453k | return Val.getSparseSetIndex(); | 59 | 453k | } |
llvm::SparseSetValTraits<llvm::SchedDFSImpl::RootData>::getValIndex(llvm::SchedDFSImpl::RootData const&) Line | Count | Source | 57 | 1.04k | static unsigned getValIndex(const ValueT &Val) { | 58 | 1.04k | return Val.getSparseSetIndex(); | 59 | 1.04k | } |
llvm::SparseSetValTraits<llvm::PhysRegSUOper>::getValIndex(llvm::PhysRegSUOper const&) Line | Count | Source | 57 | 111M | static unsigned getValIndex(const ValueT &Val) { | 58 | 111M | return Val.getSparseSetIndex(); | 59 | 111M | } |
llvm::SparseSetValTraits<llvm::VReg2SUnitOperIdx>::getValIndex(llvm::VReg2SUnitOperIdx const&) Line | Count | Source | 57 | 33.8M | static unsigned getValIndex(const ValueT &Val) { | 58 | 33.8M | return Val.getSparseSetIndex(); | 59 | 33.8M | } |
|
60 | | }; |
61 | | |
62 | | /// SparseSetValFunctor - Helper class for selecting SparseSetValTraits. The |
63 | | /// generic implementation handles ValueT classes which either provide |
64 | | /// getSparseSetIndex() or specialize SparseSetValTraits<>. |
65 | | /// |
66 | | template<typename KeyT, typename ValueT, typename KeyFunctorT> |
67 | | struct SparseSetValFunctor { |
68 | 217M | unsigned operator()(const ValueT &Val) const { |
69 | 217M | return SparseSetValTraits<ValueT>::getValIndex(Val); |
70 | 217M | } llvm::SparseSetValFunctor<unsigned int, llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int> >::operator()(llvm::LiveRegSet::IndexMaskPair const&) const Line | Count | Source | 68 | 42.7M | unsigned operator()(const ValueT &Val) const { | 69 | 42.7M | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 42.7M | } |
llvm::SparseSetValFunctor<unsigned int, llvm::LiveRegUnit, llvm::identity<unsigned int> >::operator()(llvm::LiveRegUnit const&) const Line | Count | Source | 68 | 5.08M | unsigned operator()(const ValueT &Val) const { | 69 | 5.08M | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 5.08M | } |
llvm::SparseSetValFunctor<unsigned int, llvm::VReg2SUnit, llvm::VirtReg2IndexFunctor>::operator()(llvm::VReg2SUnit const&) const Line | Count | Source | 68 | 24.1M | unsigned operator()(const ValueT &Val) const { | 69 | 24.1M | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 24.1M | } |
RegAllocFast.cpp:llvm::SparseSetValFunctor<unsigned int, (anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int> >::operator()((anonymous namespace)::RegAllocFast::LiveReg const&) const Line | Count | Source | 68 | 453k | unsigned operator()(const ValueT &Val) const { | 69 | 453k | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 453k | } |
llvm::SparseSetValFunctor<unsigned int, llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int> >::operator()(llvm::SchedDFSImpl::RootData const&) const Line | Count | Source | 68 | 1.04k | unsigned operator()(const ValueT &Val) const { | 69 | 1.04k | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 1.04k | } |
llvm::SparseSetValFunctor<unsigned int, llvm::PhysRegSUOper, llvm::identity<unsigned int> >::operator()(llvm::PhysRegSUOper const&) const Line | Count | Source | 68 | 111M | unsigned operator()(const ValueT &Val) const { | 69 | 111M | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 111M | } |
llvm::SparseSetValFunctor<unsigned int, llvm::VReg2SUnitOperIdx, llvm::VirtReg2IndexFunctor>::operator()(llvm::VReg2SUnitOperIdx const&) const Line | Count | Source | 68 | 33.8M | unsigned operator()(const ValueT &Val) const { | 69 | 33.8M | return SparseSetValTraits<ValueT>::getValIndex(Val); | 70 | 33.8M | } |
|
71 | | }; |
72 | | |
73 | | /// SparseSetValFunctor<KeyT, KeyT> - Helper class for the common case of |
74 | | /// identity key/value sets. |
75 | | template<typename KeyT, typename KeyFunctorT> |
76 | | struct SparseSetValFunctor<KeyT, KeyT, KeyFunctorT> { |
77 | 561M | unsigned operator()(const KeyT &Key) const { |
78 | 561M | return KeyFunctorT()(Key); |
79 | 561M | } llvm::SparseSetValFunctor<unsigned short, unsigned short, llvm::identity<unsigned short> >::operator()(unsigned short const&) const Line | Count | Source | 77 | 213M | unsigned operator()(const KeyT &Key) const { | 78 | 213M | return KeyFunctorT()(Key); | 79 | 213M | } |
llvm::SparseSetValFunctor<unsigned int, unsigned int, llvm::VirtReg2IndexFunctor>::operator()(unsigned int const&) const Line | Count | Source | 77 | 4.90M | unsigned operator()(const KeyT &Key) const { | 78 | 4.90M | return KeyFunctorT()(Key); | 79 | 4.90M | } |
llvm::SparseSetValFunctor<unsigned int, unsigned int, llvm::identity<unsigned int> >::operator()(unsigned int const&) const Line | Count | Source | 77 | 342M | unsigned operator()(const KeyT &Key) const { | 78 | 342M | return KeyFunctorT()(Key); | 79 | 342M | } |
|
80 | | }; |
81 | | |
82 | | /// SparseSet - Fast set implmentation for objects that can be identified by |
83 | | /// small unsigned keys. |
84 | | /// |
85 | | /// SparseSet allocates memory proportional to the size of the key universe, so |
86 | | /// it is not recommended for building composite data structures. It is useful |
87 | | /// for algorithms that require a single set with fast operations. |
88 | | /// |
89 | | /// Compared to DenseSet and DenseMap, SparseSet provides constant-time fast |
90 | | /// clear() and iteration as fast as a vector. The find(), insert(), and |
91 | | /// erase() operations are all constant time, and typically faster than a hash |
92 | | /// table. The iteration order doesn't depend on numerical key values, it only |
93 | | /// depends on the order of insert() and erase() operations. When no elements |
94 | | /// have been erased, the iteration order is the insertion order. |
95 | | /// |
96 | | /// Compared to BitVector, SparseSet<unsigned> uses 8x-40x more memory, but |
97 | | /// offers constant-time clear() and size() operations as well as fast |
98 | | /// iteration independent on the size of the universe. |
99 | | /// |
100 | | /// SparseSet contains a dense vector holding all the objects and a sparse |
101 | | /// array holding indexes into the dense vector. Most of the memory is used by |
102 | | /// the sparse array which is the size of the key universe. The SparseT |
103 | | /// template parameter provides a space/speed tradeoff for sets holding many |
104 | | /// elements. |
105 | | /// |
106 | | /// When SparseT is uint32_t, find() only touches 2 cache lines, but the sparse |
107 | | /// array uses 4 x Universe bytes. |
108 | | /// |
109 | | /// When SparseT is uint8_t (the default), find() touches up to 2+[N/256] cache |
110 | | /// lines, but the sparse array is 4x smaller. N is the number of elements in |
111 | | /// the set. |
112 | | /// |
113 | | /// For sets that may grow to thousands of elements, SparseT should be set to |
114 | | /// uint16_t or uint32_t. |
115 | | /// |
116 | | /// @tparam ValueT The type of objects in the set. |
117 | | /// @tparam KeyFunctorT A functor that computes an unsigned index from KeyT. |
118 | | /// @tparam SparseT An unsigned integer type. See above. |
119 | | /// |
120 | | template<typename ValueT, |
121 | | typename KeyFunctorT = identity<unsigned>, |
122 | | typename SparseT = uint8_t> |
123 | | class SparseSet { |
124 | | static_assert(std::numeric_limits<SparseT>::is_integer && |
125 | | !std::numeric_limits<SparseT>::is_signed, |
126 | | "SparseT must be an unsigned integer type"); |
127 | | |
128 | | using KeyT = typename KeyFunctorT::argument_type; |
129 | | using DenseT = SmallVector<ValueT, 8>; |
130 | | using size_type = unsigned; |
131 | | DenseT Dense; |
132 | | SparseT *Sparse = nullptr; |
133 | | unsigned Universe = 0; |
134 | | KeyFunctorT KeyIndexOf; |
135 | | SparseSetValFunctor<KeyT, ValueT, KeyFunctorT> ValIndexOf; |
136 | | |
137 | | public: |
138 | | using value_type = ValueT; |
139 | | using reference = ValueT &; |
140 | | using const_reference = const ValueT &; |
141 | | using pointer = ValueT *; |
142 | | using const_pointer = const ValueT *; |
143 | | |
144 | 6.78M | SparseSet() = default; llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::SparseSet() Line | Count | Source | 144 | 1.42M | SparseSet() = default; |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::SparseSet() Line | Count | Source | 144 | 1.33M | SparseSet() = default; |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::SparseSet() Line | Count | Source | 144 | 1.33M | SparseSet() = default; |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::SparseSet() Line | Count | Source | 144 | 56.2k | SparseSet() = default; |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::SparseSet() Line | Count | Source | 144 | 2.63M | SparseSet() = default; |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::SparseSet() Line | Count | Source | 144 | 1.83k | SparseSet() = default; |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::SparseSet() Line | Count | Source | 144 | 10 | SparseSet() = default; |
|
145 | | SparseSet(const SparseSet &) = delete; |
146 | | SparseSet &operator=(const SparseSet &) = delete; |
147 | 6.78M | ~SparseSet() { free(Sparse); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::~SparseSet() Line | Count | Source | 147 | 1.42M | ~SparseSet() { free(Sparse); } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::~SparseSet() Line | Count | Source | 147 | 1.33M | ~SparseSet() { free(Sparse); } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::~SparseSet() Line | Count | Source | 147 | 1.33M | ~SparseSet() { free(Sparse); } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::~SparseSet() Line | Count | Source | 147 | 56.0k | ~SparseSet() { free(Sparse); } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::~SparseSet() Line | Count | Source | 147 | 2.63M | ~SparseSet() { free(Sparse); } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::~SparseSet() Line | Count | Source | 147 | 1.82k | ~SparseSet() { free(Sparse); } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::~SparseSet() Line | Count | Source | 147 | 10 | ~SparseSet() { free(Sparse); } |
|
148 | | |
149 | | /// setUniverse - Set the universe size which determines the largest key the |
150 | | /// set can hold. The universe must be sized before any elements can be |
151 | | /// added. |
152 | | /// |
153 | | /// @param U Universe size. All object keys must be less than U. |
154 | | /// |
155 | 4.74M | void setUniverse(unsigned U) { |
156 | 4.74M | // It's not hard to resize the universe on a non-empty set, but it doesn't |
157 | 4.74M | // seem like a likely use case, so we can add that code when we need it. |
158 | 4.74M | assert(empty() && "Can only resize universe on an empty map"); |
159 | 4.74M | // Hysteresis prevents needless reallocations. |
160 | 4.74M | if (U >= Universe/4 && U <= Universe4.72M ) |
161 | 1.28M | return; |
162 | 3.45M | free(Sparse); |
163 | 3.45M | // The Sparse array doesn't actually need to be initialized, so malloc |
164 | 3.45M | // would be enough here, but that will cause tools like valgrind to |
165 | 3.45M | // complain about branching on uninitialized data. |
166 | 3.45M | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); |
167 | 3.45M | Universe = U; |
168 | 3.45M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 711k | void setUniverse(unsigned U) { | 156 | 711k | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 711k | // seem like a likely use case, so we can add that code when we need it. | 158 | 711k | assert(empty() && "Can only resize universe on an empty map"); | 159 | 711k | // Hysteresis prevents needless reallocations. | 160 | 711k | if (U >= Universe/4711k && U <= Universe) | 161 | 426k | return; | 162 | 285k | free(Sparse); | 163 | 285k | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 285k | // would be enough here, but that will cause tools like valgrind to | 165 | 285k | // complain about branching on uninitialized data. | 166 | 285k | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 285k | Universe = U; | 168 | 285k | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 759k | void setUniverse(unsigned U) { | 156 | 759k | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 759k | // seem like a likely use case, so we can add that code when we need it. | 158 | 759k | assert(empty() && "Can only resize universe on an empty map"); | 159 | 759k | // Hysteresis prevents needless reallocations. | 160 | 759k | if (U >= Universe/4 && U <= Universe741k ) | 161 | 656k | return; | 162 | 103k | free(Sparse); | 163 | 103k | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 103k | // would be enough here, but that will cause tools like valgrind to | 165 | 103k | // complain about branching on uninitialized data. | 166 | 103k | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 103k | Universe = U; | 168 | 103k | } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 2.63M | void setUniverse(unsigned U) { | 156 | 2.63M | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 2.63M | // seem like a likely use case, so we can add that code when we need it. | 158 | 2.63M | assert(empty() && "Can only resize universe on an empty map"); | 159 | 2.63M | // Hysteresis prevents needless reallocations. | 160 | 2.63M | if (U >= Universe/4 && U <= Universe2.63M ) | 161 | 0 | return; | 162 | 2.63M | free(Sparse); | 163 | 2.63M | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 2.63M | // would be enough here, but that will cause tools like valgrind to | 165 | 2.63M | // complain about branching on uninitialized data. | 166 | 2.63M | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 2.63M | Universe = U; | 168 | 2.63M | } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 8.06k | void setUniverse(unsigned U) { | 156 | 8.06k | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 8.06k | // seem like a likely use case, so we can add that code when we need it. | 158 | 8.06k | assert(empty() && "Can only resize universe on an empty map"); | 159 | 8.06k | // Hysteresis prevents needless reallocations. | 160 | 8.06k | if (U >= Universe/4 && U <= Universe7.90k ) | 161 | 5.64k | return; | 162 | 2.42k | free(Sparse); | 163 | 2.42k | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 2.42k | // would be enough here, but that will cause tools like valgrind to | 165 | 2.42k | // complain about branching on uninitialized data. | 166 | 2.42k | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 2.42k | Universe = U; | 168 | 2.42k | } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 474k | void setUniverse(unsigned U) { | 156 | 474k | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 474k | // seem like a likely use case, so we can add that code when we need it. | 158 | 474k | assert(empty() && "Can only resize universe on an empty map"); | 159 | 474k | // Hysteresis prevents needless reallocations. | 160 | 474k | if (U >= Universe/4 && U <= Universe) | 161 | 149k | return; | 162 | 325k | free(Sparse); | 163 | 325k | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 325k | // would be enough here, but that will cause tools like valgrind to | 165 | 325k | // complain about branching on uninitialized data. | 166 | 325k | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 325k | Universe = U; | 168 | 325k | } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 158k | void setUniverse(unsigned U) { | 156 | 158k | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 158k | // seem like a likely use case, so we can add that code when we need it. | 158 | 158k | assert(empty() && "Can only resize universe on an empty map"); | 159 | 158k | // Hysteresis prevents needless reallocations. | 160 | 158k | if (U >= Universe/4 && U <= Universe) | 161 | 49.7k | return; | 162 | 108k | free(Sparse); | 163 | 108k | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 108k | // would be enough here, but that will cause tools like valgrind to | 165 | 108k | // complain about branching on uninitialized data. | 166 | 108k | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 108k | Universe = U; | 168 | 108k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::setUniverse(unsigned int) Line | Count | Source | 155 | 10 | void setUniverse(unsigned U) { | 156 | 10 | // It's not hard to resize the universe on a non-empty set, but it doesn't | 157 | 10 | // seem like a likely use case, so we can add that code when we need it. | 158 | 10 | assert(empty() && "Can only resize universe on an empty map"); | 159 | 10 | // Hysteresis prevents needless reallocations. | 160 | 10 | if (U >= Universe/4 && U <= Universe) | 161 | 0 | return; | 162 | 10 | free(Sparse); | 163 | 10 | // The Sparse array doesn't actually need to be initialized, so malloc | 164 | 10 | // would be enough here, but that will cause tools like valgrind to | 165 | 10 | // complain about branching on uninitialized data. | 166 | 10 | Sparse = static_cast<SparseT*>(safe_calloc(U, sizeof(SparseT))); | 167 | 10 | Universe = U; | 168 | 10 | } |
|
169 | | |
170 | | // Import trivial vector stuff from DenseT. |
171 | | using iterator = typename DenseT::iterator; |
172 | | using const_iterator = typename DenseT::const_iterator; |
173 | | |
174 | 954k | const_iterator begin() const { return Dense.begin(); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::begin() const Line | Count | Source | 174 | 321k | const_iterator begin() const { return Dense.begin(); } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::begin() const Line | Count | Source | 174 | 632k | const_iterator begin() const { return Dense.begin(); } |
|
175 | 36.4M | const_iterator end() const { return Dense.end(); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::end() const Line | Count | Source | 175 | 17.2M | const_iterator end() const { return Dense.end(); } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::end() const Line | Count | Source | 175 | 18.6M | const_iterator end() const { return Dense.end(); } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::end() const Line | Count | Source | 175 | 556k | const_iterator end() const { return Dense.end(); } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::end() const Line | Count | Source | 175 | 146 | const_iterator end() const { return Dense.end(); } |
|
176 | 177M | iterator begin() { return Dense.begin(); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::begin() Line | Count | Source | 176 | 58.7M | iterator begin() { return Dense.begin(); } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::begin() Line | Count | Source | 176 | 15.5M | iterator begin() { return Dense.begin(); } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::begin() Line | Count | Source | 176 | 451k | iterator begin() { return Dense.begin(); } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::begin() Line | Count | Source | 176 | 100M | iterator begin() { return Dense.begin(); } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::begin() Line | Count | Source | 176 | 2.76M | iterator begin() { return Dense.begin(); } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::begin() Line | Count | Source | 176 | 161k | iterator begin() { return Dense.begin(); } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::begin() Line | Count | Source | 176 | 520 | iterator begin() { return Dense.begin(); } |
|
177 | 835M | iterator end() { return Dense.end(); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::end() Line | Count | Source | 177 | 356M | iterator end() { return Dense.end(); } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::end() Line | Count | Source | 177 | 36.3M | iterator end() { return Dense.end(); } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::end() Line | Count | Source | 177 | 6.10M | iterator end() { return Dense.end(); } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::end() Line | Count | Source | 177 | 427M | iterator end() { return Dense.end(); } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::end() Line | Count | Source | 177 | 7.85M | iterator end() { return Dense.end(); } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::end() Line | Count | Source | 177 | 252k | iterator end() { return Dense.end(); } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::end() Line | Count | Source | 177 | 1.01k | iterator end() { return Dense.end(); } |
|
178 | | |
179 | | /// empty - Returns true if the set is empty. |
180 | | /// |
181 | | /// This is not the same as BitVector::empty(). |
182 | | /// |
183 | 107M | bool empty() const { return Dense.empty(); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::empty() const Line | Count | Source | 183 | 874k | bool empty() const { return Dense.empty(); } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::empty() const Line | Count | Source | 183 | 106M | bool empty() const { return Dense.empty(); } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::empty() const Line | Count | Source | 183 | 14.5k | bool empty() const { return Dense.empty(); } |
|
184 | | |
185 | | /// size - Returns the number of elements in the set. |
186 | | /// |
187 | | /// This is not the same as BitVector::size() which returns the size of the |
188 | | /// universe. |
189 | | /// |
190 | 585M | size_type size() const { return Dense.size(); } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::size() const Line | Count | Source | 190 | 219M | size_type size() const { return Dense.size(); } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::size() const Line | Count | Source | 190 | 38.3M | size_type size() const { return Dense.size(); } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::size() const Line | Count | Source | 190 | 4.52M | size_type size() const { return Dense.size(); } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::size() const Line | Count | Source | 190 | 318M | size_type size() const { return Dense.size(); } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::size() const Line | Count | Source | 190 | 5.09M | size_type size() const { return Dense.size(); } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::size() const Line | Count | Source | 190 | 265k | size_type size() const { return Dense.size(); } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::size() const Line | Count | Source | 190 | 826 | size_type size() const { return Dense.size(); } |
|
191 | | |
192 | | /// clear - Clears the set. This is a very fast constant time operation. |
193 | | /// |
194 | 16.7M | void clear() { |
195 | 16.7M | // Sparse does not need to be cleared, see find(). |
196 | 16.7M | Dense.clear(); |
197 | 16.7M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::clear() Line | Count | Source | 194 | 1.51M | void clear() { | 195 | 1.51M | // Sparse does not need to be cleared, see find(). | 196 | 1.51M | Dense.clear(); | 197 | 1.51M | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::clear() Line | Count | Source | 194 | 9.24M | void clear() { | 195 | 9.24M | // Sparse does not need to be cleared, see find(). | 196 | 9.24M | Dense.clear(); | 197 | 9.24M | } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::clear() Line | Count | Source | 194 | 11.8k | void clear() { | 195 | 11.8k | // Sparse does not need to be cleared, see find(). | 196 | 11.8k | Dense.clear(); | 197 | 11.8k | } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::clear() Line | Count | Source | 194 | 2.97M | void clear() { | 195 | 2.97M | // Sparse does not need to be cleared, see find(). | 196 | 2.97M | Dense.clear(); | 197 | 2.97M | } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::clear() Line | Count | Source | 194 | 2.97M | void clear() { | 195 | 2.97M | // Sparse does not need to be cleared, see find(). | 196 | 2.97M | Dense.clear(); | 197 | 2.97M | } |
|
198 | | |
199 | | /// findIndex - Find an element by its index. |
200 | | /// |
201 | | /// @param Idx A valid index to find. |
202 | | /// @returns An iterator to the element identified by key, or end(). |
203 | | /// |
204 | 404M | iterator findIndex(unsigned Idx) { |
205 | 404M | assert(Idx < Universe && "Key out of range"); |
206 | 404M | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; |
207 | 539M | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride135M ) { |
208 | 291M | const unsigned FoundIdx = ValIndexOf(Dense[i]); |
209 | 291M | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); |
210 | 291M | if (Idx == FoundIdx) |
211 | 156M | return begin() + i; |
212 | 135M | // Stride is 0 when SparseT >= unsigned. We don't need to loop. |
213 | 135M | if (!Stride) |
214 | 0 | break; |
215 | 135M | } |
216 | 404M | return end()247M ; |
217 | 404M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 155M | iterator findIndex(unsigned Idx) { | 205 | 155M | assert(Idx < Universe && "Key out of range"); | 206 | 155M | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 237M | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride81.2M ) { | 208 | 118M | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 118M | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 118M | if (Idx == FoundIdx) | 211 | 37.7M | return begin() + i; | 212 | 81.2M | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 81.2M | if (!Stride) | 214 | 0 | break; | 215 | 81.2M | } | 216 | 155M | return end()118M ; | 217 | 155M | } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 32.1M | iterator findIndex(unsigned Idx) { | 205 | 32.1M | assert(Idx < Universe && "Key out of range"); | 206 | 32.1M | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 50.1M | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride17.9M ) { | 208 | 33.5M | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 33.5M | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 33.5M | if (Idx == FoundIdx) | 211 | 15.5M | return begin() + i; | 212 | 17.9M | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 17.9M | if (!Stride) | 214 | 0 | break; | 215 | 17.9M | } | 216 | 32.1M | return end()16.6M ; | 217 | 32.1M | } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 2.58M | iterator findIndex(unsigned Idx) { | 205 | 2.58M | assert(Idx < Universe && "Key out of range"); | 206 | 2.58M | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 5.01M | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride2.42M ) { | 208 | 2.87M | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 2.87M | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 2.87M | if (Idx == FoundIdx) | 211 | 451k | return begin() + i; | 212 | 2.42M | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 2.42M | if (!Stride) | 214 | 0 | break; | 215 | 2.42M | } | 216 | 2.58M | return end()2.13M ; | 217 | 2.58M | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 209M | iterator findIndex(unsigned Idx) { | 205 | 209M | assert(Idx < Universe && "Key out of range"); | 206 | 209M | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 242M | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride32.6M ) { | 208 | 132M | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 132M | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 132M | if (Idx == FoundIdx) | 211 | 100M | return begin() + i; | 212 | 32.6M | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 32.6M | if (!Stride) | 214 | 0 | break; | 215 | 32.6M | } | 216 | 209M | return end()109M ; | 217 | 209M | } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 4.00M | iterator findIndex(unsigned Idx) { | 205 | 4.00M | assert(Idx < Universe && "Key out of range"); | 206 | 4.00M | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 4.82M | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride819k ) { | 208 | 3.10M | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 3.10M | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 3.10M | if (Idx == FoundIdx) | 211 | 2.28M | return begin() + i; | 212 | 819k | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 819k | if (!Stride) | 214 | 0 | break; | 215 | 819k | } | 216 | 4.00M | return end()1.72M ; | 217 | 4.00M | } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 207k | iterator findIndex(unsigned Idx) { | 205 | 207k | assert(Idx < Universe && "Key out of range"); | 206 | 207k | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 388k | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride180k ) { | 208 | 329k | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 329k | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 329k | if (Idx == FoundIdx) | 211 | 149k | return begin() + i; | 212 | 180k | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 180k | if (!Stride) | 214 | 0 | break; | 215 | 180k | } | 216 | 207k | return end()58.0k ; | 217 | 207k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::findIndex(unsigned int) Line | Count | Source | 204 | 644 | iterator findIndex(unsigned Idx) { | 205 | 644 | assert(Idx < Universe && "Key out of range"); | 206 | 644 | const unsigned Stride = std::numeric_limits<SparseT>::max() + 1u; | 207 | 816 | for (unsigned i = Sparse[Idx], e = size(); i < e; i += Stride172 ) { | 208 | 626 | const unsigned FoundIdx = ValIndexOf(Dense[i]); | 209 | 626 | assert(FoundIdx < Universe && "Invalid key in set. Did object mutate?"); | 210 | 626 | if (Idx == FoundIdx) | 211 | 454 | return begin() + i; | 212 | 172 | // Stride is 0 when SparseT >= unsigned. We don't need to loop. | 213 | 172 | if (!Stride) | 214 | 0 | break; | 215 | 172 | } | 216 | 644 | return end()190 ; | 217 | 644 | } |
|
218 | | |
219 | | /// find - Find an element by its key. |
220 | | /// |
221 | | /// @param Key A valid key to find. |
222 | | /// @returns An iterator to the element identified by key, or end(). |
223 | | /// |
224 | 71.5M | iterator find(const KeyT &Key) { |
225 | 71.5M | return findIndex(KeyIndexOf(Key)); |
226 | 71.5M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::find(unsigned short const&) Line | Count | Source | 224 | 64.5M | iterator find(const KeyT &Key) { | 225 | 64.5M | return findIndex(KeyIndexOf(Key)); | 226 | 64.5M | } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) Line | Count | Source | 224 | 4.91M | iterator find(const KeyT &Key) { | 225 | 4.91M | return findIndex(KeyIndexOf(Key)); | 226 | 4.91M | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) Line | Count | Source | 224 | 4.75k | iterator find(const KeyT &Key) { | 225 | 4.75k | return findIndex(KeyIndexOf(Key)); | 226 | 4.75k | } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) Line | Count | Source | 224 | 2.08M | iterator find(const KeyT &Key) { | 225 | 2.08M | return findIndex(KeyIndexOf(Key)); | 226 | 2.08M | } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) Line | Count | Source | 224 | 5.46k | iterator find(const KeyT &Key) { | 225 | 5.46k | return findIndex(KeyIndexOf(Key)); | 226 | 5.46k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) Line | Count | Source | 224 | 138 | iterator find(const KeyT &Key) { | 225 | 138 | return findIndex(KeyIndexOf(Key)); | 226 | 138 | } |
|
227 | | |
228 | 35.5M | const_iterator find(const KeyT &Key) const { |
229 | 35.5M | return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); |
230 | 35.5M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::find(unsigned short const&) const Line | Count | Source | 228 | 16.9M | const_iterator find(const KeyT &Key) const { | 229 | 16.9M | return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); | 230 | 16.9M | } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) const Line | Count | Source | 228 | 17.9M | const_iterator find(const KeyT &Key) const { | 229 | 17.9M | return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); | 230 | 17.9M | } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::find(unsigned int const&) const Line | Count | Source | 228 | 556k | const_iterator find(const KeyT &Key) const { | 229 | 556k | return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); | 230 | 556k | } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) const Line | Count | Source | 228 | 77.9k | const_iterator find(const KeyT &Key) const { | 229 | 77.9k | return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); | 230 | 77.9k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::find(unsigned int const&) const Line | Count | Source | 228 | 146 | const_iterator find(const KeyT &Key) const { | 229 | 146 | return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key)); | 230 | 146 | } |
|
231 | | |
232 | | /// count - Returns 1 if this set contains an element identified by Key, |
233 | | /// 0 otherwise. |
234 | | /// |
235 | 17.5M | size_type count(const KeyT &Key) const { |
236 | 17.5M | return find(Key) == end() ? 013.6M : 13.93M ; |
237 | 17.5M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::count(unsigned short const&) const Line | Count | Source | 235 | 16.9M | size_type count(const KeyT &Key) const { | 236 | 16.9M | return find(Key) == end() ? 013.4M : 13.57M ; | 237 | 16.9M | } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::count(unsigned int const&) const Line | Count | Source | 235 | 556k | size_type count(const KeyT &Key) const { | 236 | 556k | return find(Key) == end() ? 0197k : 1358k ; | 237 | 556k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::count(unsigned int const&) const Line | Count | Source | 235 | 146 | size_type count(const KeyT &Key) const { | 236 | 146 | return find(Key) == end() ? 08 : 1138 ; | 237 | 146 | } |
|
238 | | |
239 | | /// insert - Attempts to insert a new element. |
240 | | /// |
241 | | /// If Val is successfully inserted, return (I, true), where I is an iterator |
242 | | /// pointing to the newly inserted element. |
243 | | /// |
244 | | /// If the set already contains an element with the same key as Val, return |
245 | | /// (I, false), where I is an iterator pointing to the existing element. |
246 | | /// |
247 | | /// Insertion invalidates all iterators. |
248 | | /// |
249 | 297M | std::pair<iterator, bool> insert(const ValueT &Val) { |
250 | 297M | unsigned Idx = ValIndexOf(Val); |
251 | 297M | iterator I = findIndex(Idx); |
252 | 297M | if (I != end()) |
253 | 116M | return std::make_pair(I, false); |
254 | 180M | Sparse[Idx] = size(); |
255 | 180M | Dense.push_back(Val); |
256 | 180M | return std::make_pair(end() - 1, true); |
257 | 180M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::insert(unsigned short const&) Line | Count | Source | 249 | 74.4M | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 74.4M | unsigned Idx = ValIndexOf(Val); | 251 | 74.4M | iterator I = findIndex(Idx); | 252 | 74.4M | if (I != end()) | 253 | 11.2M | return std::make_pair(I, false); | 254 | 63.1M | Sparse[Idx] = size(); | 255 | 63.1M | Dense.push_back(Val); | 256 | 63.1M | return std::make_pair(end() - 1, true); | 257 | 63.1M | } |
llvm::SparseSet<llvm::LiveRegSet::IndexMaskPair, llvm::identity<unsigned int>, unsigned char>::insert(llvm::LiveRegSet::IndexMaskPair const&) Line | Count | Source | 249 | 9.24M | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 9.24M | unsigned Idx = ValIndexOf(Val); | 251 | 9.24M | iterator I = findIndex(Idx); | 252 | 9.24M | if (I != end()) | 253 | 3.66M | return std::make_pair(I, false); | 254 | 5.58M | Sparse[Idx] = size(); | 255 | 5.58M | Dense.push_back(Val); | 256 | 5.58M | return std::make_pair(end() - 1, true); | 257 | 5.58M | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::insert(unsigned int const&) Line | Count | Source | 249 | 209M | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 209M | unsigned Idx = ValIndexOf(Val); | 251 | 209M | iterator I = findIndex(Idx); | 252 | 209M | if (I != end()) | 253 | 100M | return std::make_pair(I, false); | 254 | 109M | Sparse[Idx] = size(); | 255 | 109M | Dense.push_back(Val); | 256 | 109M | return std::make_pair(end() - 1, true); | 257 | 109M | } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::insert(llvm::LiveRegUnit const&) Line | Count | Source | 249 | 1.91M | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 1.91M | unsigned Idx = ValIndexOf(Val); | 251 | 1.91M | iterator I = findIndex(Idx); | 252 | 1.91M | if (I != end()) | 253 | 823k | return std::make_pair(I, false); | 254 | 1.09M | Sparse[Idx] = size(); | 255 | 1.09M | Dense.push_back(Val); | 256 | 1.09M | return std::make_pair(end() - 1, true); | 257 | 1.09M | } |
RegAllocFast.cpp:llvm::SparseSet<(anonymous namespace)::RegAllocFast::LiveReg, llvm::identity<unsigned int>, unsigned char>::insert((anonymous namespace)::RegAllocFast::LiveReg const&) Line | Count | Source | 249 | 123k | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 123k | unsigned Idx = ValIndexOf(Val); | 251 | 123k | iterator I = findIndex(Idx); | 252 | 123k | if (I != end()) | 253 | 65.8k | return std::make_pair(I, false); | 254 | 58.0k | Sparse[Idx] = size(); | 255 | 58.0k | Dense.push_back(Val); | 256 | 58.0k | return std::make_pair(end() - 1, true); | 257 | 58.0k | } |
llvm::SparseSet<unsigned int, llvm::VirtReg2IndexFunctor, unsigned char>::insert(unsigned int const&) Line | Count | Source | 249 | 2.03M | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 2.03M | unsigned Idx = ValIndexOf(Val); | 251 | 2.03M | iterator I = findIndex(Idx); | 252 | 2.03M | if (I != end()) | 253 | 92.6k | return std::make_pair(I, false); | 254 | 1.93M | Sparse[Idx] = size(); | 255 | 1.93M | Dense.push_back(Val); | 256 | 1.93M | return std::make_pair(end() - 1, true); | 257 | 1.93M | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::insert(llvm::SchedDFSImpl::RootData const&) Line | Count | Source | 249 | 360 | std::pair<iterator, bool> insert(const ValueT &Val) { | 250 | 360 | unsigned Idx = ValIndexOf(Val); | 251 | 360 | iterator I = findIndex(Idx); | 252 | 360 | if (I != end()) | 253 | 178 | return std::make_pair(I, false); | 254 | 182 | Sparse[Idx] = size(); | 255 | 182 | Dense.push_back(Val); | 256 | 182 | return std::make_pair(end() - 1, true); | 257 | 182 | } |
|
258 | | |
259 | | /// array subscript - If an element already exists with this key, return it. |
260 | | /// Otherwise, automatically construct a new value from Key, insert it, |
261 | | /// and return the newly inserted element. |
262 | 1.91M | ValueT &operator[](const KeyT &Key) { |
263 | 1.91M | return *insert(ValueT(Key)).first; |
264 | 1.91M | } llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::operator[](unsigned int const&) Line | Count | Source | 262 | 1.91M | ValueT &operator[](const KeyT &Key) { | 263 | 1.91M | return *insert(ValueT(Key)).first; | 264 | 1.91M | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::operator[](unsigned int const&) Line | Count | Source | 262 | 360 | ValueT &operator[](const KeyT &Key) { | 263 | 360 | return *insert(ValueT(Key)).first; | 264 | 360 | } |
|
265 | | |
266 | 94.0M | ValueT pop_back_val() { |
267 | 94.0M | // Sparse does not need to be cleared, see find(). |
268 | 94.0M | return Dense.pop_back_val(); |
269 | 94.0M | } |
270 | | |
271 | | /// erase - Erases an existing element identified by a valid iterator. |
272 | | /// |
273 | | /// This invalidates all iterators, but erase() returns an iterator pointing |
274 | | /// to the next element. This makes it possible to erase selected elements |
275 | | /// while iterating over the set: |
276 | | /// |
277 | | /// for (SparseSet::iterator I = Set.begin(); I != Set.end();) |
278 | | /// if (test(*I)) |
279 | | /// I = Set.erase(I); |
280 | | /// else |
281 | | /// ++I; |
282 | | /// |
283 | | /// Note that end() changes when elements are erased, unlike std::list. |
284 | | /// |
285 | 24.8M | iterator erase(iterator I) { |
286 | 24.8M | assert(unsigned(I - begin()) < size() && "Invalid iterator"); |
287 | 24.8M | if (I != end() - 1) { |
288 | 20.6M | *I = Dense.back(); |
289 | 20.6M | unsigned BackIdx = ValIndexOf(Dense.back()); |
290 | 20.6M | assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); |
291 | 20.6M | Sparse[BackIdx] = I - begin(); |
292 | 20.6M | } |
293 | 24.8M | // This depends on SmallVector::pop_back() not invalidating iterators. |
294 | 24.8M | // std::vector::pop_back() doesn't give that guarantee. |
295 | 24.8M | Dense.pop_back(); |
296 | 24.8M | return I; |
297 | 24.8M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::erase(unsigned short*) Line | Count | Source | 285 | 24.1M | iterator erase(iterator I) { | 286 | 24.1M | assert(unsigned(I - begin()) < size() && "Invalid iterator"); | 287 | 24.1M | if (I != end() - 1) { | 288 | 20.5M | *I = Dense.back(); | 289 | 20.5M | unsigned BackIdx = ValIndexOf(Dense.back()); | 290 | 20.5M | assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); | 291 | 20.5M | Sparse[BackIdx] = I - begin(); | 292 | 20.5M | } | 293 | 24.1M | // This depends on SmallVector::pop_back() not invalidating iterators. | 294 | 24.1M | // std::vector::pop_back() doesn't give that guarantee. | 295 | 24.1M | Dense.pop_back(); | 296 | 24.1M | return I; | 297 | 24.1M | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::erase(unsigned int*) Line | Count | Source | 285 | 2.63k | iterator erase(iterator I) { | 286 | 2.63k | assert(unsigned(I - begin()) < size() && "Invalid iterator"); | 287 | 2.63k | if (I != end() - 1) { | 288 | 7 | *I = Dense.back(); | 289 | 7 | unsigned BackIdx = ValIndexOf(Dense.back()); | 290 | 7 | assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); | 291 | 7 | Sparse[BackIdx] = I - begin(); | 292 | 7 | } | 293 | 2.63k | // This depends on SmallVector::pop_back() not invalidating iterators. | 294 | 2.63k | // std::vector::pop_back() doesn't give that guarantee. | 295 | 2.63k | Dense.pop_back(); | 296 | 2.63k | return I; | 297 | 2.63k | } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::erase(llvm::LiveRegUnit*) Line | Count | Source | 285 | 619k | iterator erase(iterator I) { | 286 | 619k | assert(unsigned(I - begin()) < size() && "Invalid iterator"); | 287 | 619k | if (I != end() - 1) { | 288 | 64.6k | *I = Dense.back(); | 289 | 64.6k | unsigned BackIdx = ValIndexOf(Dense.back()); | 290 | 64.6k | assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); | 291 | 64.6k | Sparse[BackIdx] = I - begin(); | 292 | 64.6k | } | 293 | 619k | // This depends on SmallVector::pop_back() not invalidating iterators. | 294 | 619k | // std::vector::pop_back() doesn't give that guarantee. | 295 | 619k | Dense.pop_back(); | 296 | 619k | return I; | 297 | 619k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::erase(llvm::SchedDFSImpl::RootData*) Line | Count | Source | 285 | 138 | iterator erase(iterator I) { | 286 | 138 | assert(unsigned(I - begin()) < size() && "Invalid iterator"); | 287 | 138 | if (I != end() - 1) { | 288 | 56 | *I = Dense.back(); | 289 | 56 | unsigned BackIdx = ValIndexOf(Dense.back()); | 290 | 56 | assert(BackIdx < Universe && "Invalid key in set. Did object mutate?"); | 291 | 56 | Sparse[BackIdx] = I - begin(); | 292 | 56 | } | 293 | 138 | // This depends on SmallVector::pop_back() not invalidating iterators. | 294 | 138 | // std::vector::pop_back() doesn't give that guarantee. | 295 | 138 | Dense.pop_back(); | 296 | 138 | return I; | 297 | 138 | } |
|
298 | | |
299 | | /// erase - Erases an element identified by Key, if it exists. |
300 | | /// |
301 | | /// @param Key The key identifying the element to erase. |
302 | | /// @returns True when an element was erased, false if no element was found. |
303 | | /// |
304 | 64.6M | bool erase(const KeyT &Key) { |
305 | 64.6M | iterator I = find(Key); |
306 | 64.6M | if (I == end()) |
307 | 41.6M | return false; |
308 | 22.9M | erase(I); |
309 | 22.9M | return true; |
310 | 22.9M | } llvm::SparseSet<unsigned short, llvm::identity<unsigned short>, unsigned char>::erase(unsigned short const&) Line | Count | Source | 304 | 64.5M | bool erase(const KeyT &Key) { | 305 | 64.5M | iterator I = find(Key); | 306 | 64.5M | if (I == end()) | 307 | 41.5M | return false; | 308 | 22.9M | erase(I); | 309 | 22.9M | return true; | 310 | 22.9M | } |
llvm::SparseSet<unsigned int, llvm::identity<unsigned int>, unsigned char>::erase(unsigned int const&) Line | Count | Source | 304 | 4.74k | bool erase(const KeyT &Key) { | 305 | 4.74k | iterator I = find(Key); | 306 | 4.74k | if (I == end()) | 307 | 2.11k | return false; | 308 | 2.63k | erase(I); | 309 | 2.63k | return true; | 310 | 2.63k | } |
llvm::SparseSet<llvm::LiveRegUnit, llvm::identity<unsigned int>, unsigned char>::erase(unsigned int const&) Line | Count | Source | 304 | 68.5k | bool erase(const KeyT &Key) { | 305 | 68.5k | iterator I = find(Key); | 306 | 68.5k | if (I == end()) | 307 | 43.7k | return false; | 308 | 24.8k | erase(I); | 309 | 24.8k | return true; | 310 | 24.8k | } |
llvm::SparseSet<llvm::SchedDFSImpl::RootData, llvm::identity<unsigned int>, unsigned char>::erase(unsigned int const&) Line | Count | Source | 304 | 138 | bool erase(const KeyT &Key) { | 305 | 138 | iterator I = find(Key); | 306 | 138 | if (I == end()) | 307 | 0 | return false; | 308 | 138 | erase(I); | 309 | 138 | return true; | 310 | 138 | } |
|
311 | | }; |
312 | | |
313 | | } // end namespace llvm |
314 | | |
315 | | #endif // LLVM_ADT_SPARSESET_H |