/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- ThreadSafetyUtil.h ---------------------------------------*- 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 some basic utility classes for use by ThreadSafetyTIL.h |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H |
14 | | #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H |
15 | | |
16 | | #include "clang/AST/Decl.h" |
17 | | #include "clang/Basic/LLVM.h" |
18 | | #include "llvm/ADT/StringRef.h" |
19 | | #include "llvm/ADT/iterator_range.h" |
20 | | #include "llvm/Support/Allocator.h" |
21 | | #include <cassert> |
22 | | #include <cstddef> |
23 | | #include <cstring> |
24 | | #include <iterator> |
25 | | #include <ostream> |
26 | | #include <string> |
27 | | #include <vector> |
28 | | |
29 | | namespace clang { |
30 | | |
31 | | class Expr; |
32 | | |
33 | | namespace threadSafety { |
34 | | namespace til { |
35 | | |
36 | | // Simple wrapper class to abstract away from the details of memory management. |
37 | | // SExprs are allocated in pools, and deallocated all at once. |
38 | | class MemRegionRef { |
39 | | private: |
40 | | union AlignmentType { |
41 | | double d; |
42 | | void *p; |
43 | | long double dd; |
44 | | long long ii; |
45 | | }; |
46 | | |
47 | | public: |
48 | | MemRegionRef() = default; |
49 | 2.25k | MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} |
50 | | |
51 | 21.3k | void *allocate(size_t Sz) { |
52 | 21.3k | return Allocator->Allocate(Sz, alignof(AlignmentType)); |
53 | 21.3k | } |
54 | | |
55 | | template <typename T> T *allocateT() { return Allocator->Allocate<T>(); } |
56 | | |
57 | 0 | template <typename T> T *allocateT(size_t NumElems) { |
58 | 0 | return Allocator->Allocate<T>(NumElems); |
59 | 0 | } Unexecuted instantiation: clang::threadSafety::til::SExpr** clang::threadSafety::til::MemRegionRef::allocateT<clang::threadSafety::til::SExpr*>(unsigned long) Unexecuted instantiation: clang::threadSafety::til::BasicBlock** clang::threadSafety::til::MemRegionRef::allocateT<clang::threadSafety::til::BasicBlock*>(unsigned long) |
60 | | |
61 | | private: |
62 | | llvm::BumpPtrAllocator *Allocator = nullptr; |
63 | | }; |
64 | | |
65 | | } // namespace til |
66 | | } // namespace threadSafety |
67 | | |
68 | | } // namespace clang |
69 | | |
70 | | inline void *operator new(size_t Sz, |
71 | 21.3k | clang::threadSafety::til::MemRegionRef &R) { |
72 | 21.3k | return R.allocate(Sz); |
73 | 21.3k | } |
74 | | |
75 | | namespace clang { |
76 | | namespace threadSafety { |
77 | | |
78 | | std::string getSourceLiteralString(const Expr *CE); |
79 | | |
80 | | namespace til { |
81 | | |
82 | | // A simple fixed size array class that does not manage its own memory, |
83 | | // suitable for use with bump pointer allocation. |
84 | | template <class T> class SimpleArray { |
85 | | public: |
86 | 0 | SimpleArray() = default; Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::SimpleArray() Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::SimpleArray() |
87 | | SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) |
88 | | : Data(Dat), Size(Sz), Capacity(Cp) {} |
89 | | SimpleArray(MemRegionRef A, size_t Cp) |
90 | 0 | : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {} Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::SimpleArray(clang::threadSafety::til::MemRegionRef, unsigned long) Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::SimpleArray(clang::threadSafety::til::MemRegionRef, unsigned long) |
91 | | SimpleArray(const SimpleArray<T> &A) = delete; |
92 | | |
93 | | SimpleArray(SimpleArray<T> &&A) |
94 | | : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { |
95 | | A.Data = nullptr; |
96 | | A.Size = 0; |
97 | | A.Capacity = 0; |
98 | | } |
99 | | |
100 | | SimpleArray &operator=(SimpleArray &&RHS) { |
101 | | if (this != &RHS) { |
102 | | Data = RHS.Data; |
103 | | Size = RHS.Size; |
104 | | Capacity = RHS.Capacity; |
105 | | |
106 | | RHS.Data = nullptr; |
107 | | RHS.Size = RHS.Capacity = 0; |
108 | | } |
109 | | return *this; |
110 | | } |
111 | | |
112 | | // Reserve space for at least Ncp items, reallocating if necessary. |
113 | 0 | void reserve(size_t Ncp, MemRegionRef A) { |
114 | 0 | if (Ncp <= Capacity) |
115 | 0 | return; |
116 | 0 | T *Odata = Data; |
117 | 0 | Data = A.allocateT<T>(Ncp); |
118 | 0 | Capacity = Ncp; |
119 | 0 | memcpy(Data, Odata, sizeof(T) * Size); |
120 | 0 | } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::reserve(unsigned long, clang::threadSafety::til::MemRegionRef) Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::reserve(unsigned long, clang::threadSafety::til::MemRegionRef) |
121 | | |
122 | | // Reserve space for at least N more items. |
123 | 0 | void reserveCheck(size_t N, MemRegionRef A) { |
124 | 0 | if (Capacity == 0) |
125 | 0 | reserve(u_max(InitialCapacity, N), A); |
126 | 0 | else if (Size + N < Capacity) |
127 | 0 | reserve(u_max(Size + N, Capacity * 2), A); |
128 | 0 | } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::reserveCheck(unsigned long, clang::threadSafety::til::MemRegionRef) Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::reserveCheck(unsigned long, clang::threadSafety::til::MemRegionRef) |
129 | | |
130 | | using iterator = T *; |
131 | | using const_iterator = const T *; |
132 | | using reverse_iterator = std::reverse_iterator<iterator>; |
133 | | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
134 | | |
135 | 0 | size_t size() const { return Size; } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::size() const Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::size() const |
136 | | size_t capacity() const { return Capacity; } |
137 | | |
138 | 0 | T &operator[](unsigned i) { |
139 | 0 | assert(i < Size && "Array index out of bounds."); |
140 | 0 | return Data[i]; |
141 | 0 | } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::operator[](unsigned int) Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::operator[](unsigned int) |
142 | | |
143 | 0 | const T &operator[](unsigned i) const { |
144 | 0 | assert(i < Size && "Array index out of bounds."); |
145 | 0 | return Data[i]; |
146 | 0 | } |
147 | | |
148 | | T &back() { |
149 | | assert(Size && "No elements in the array."); |
150 | | return Data[Size - 1]; |
151 | | } |
152 | | |
153 | | const T &back() const { |
154 | | assert(Size && "No elements in the array."); |
155 | | return Data[Size - 1]; |
156 | | } |
157 | | |
158 | 0 | iterator begin() { return Data; } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::begin() Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::begin() |
159 | 0 | iterator end() { return Data + Size; } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::end() Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::end() |
160 | | |
161 | 0 | const_iterator begin() const { return Data; } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::begin() const Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::begin() const |
162 | 0 | const_iterator end() const { return Data + Size; } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::end() const Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::end() const |
163 | | |
164 | 0 | const_iterator cbegin() const { return Data; } |
165 | 0 | const_iterator cend() const { return Data + Size; } |
166 | | |
167 | 0 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
168 | 0 | reverse_iterator rend() { return reverse_iterator(begin()); } |
169 | | |
170 | | const_reverse_iterator rbegin() const { |
171 | | return const_reverse_iterator(end()); |
172 | | } |
173 | | |
174 | | const_reverse_iterator rend() const { |
175 | | return const_reverse_iterator(begin()); |
176 | | } |
177 | | |
178 | 0 | void push_back(const T &Elem) { |
179 | 0 | assert(Size < Capacity); |
180 | 0 | Data[Size++] = Elem; |
181 | 0 | } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::push_back(clang::threadSafety::til::SExpr* const&) Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::push_back(clang::threadSafety::til::BasicBlock* const&) |
182 | | |
183 | | // drop last n elements from array |
184 | 0 | void drop(unsigned n = 0) { |
185 | 0 | assert(Size > n); |
186 | 0 | Size -= n; |
187 | 0 | } |
188 | | |
189 | 0 | void setValues(unsigned Sz, const T& C) { |
190 | 0 | assert(Sz <= Capacity); |
191 | 0 | Size = Sz; |
192 | 0 | for (unsigned i = 0; i < Sz; ++i) { |
193 | 0 | Data[i] = C; |
194 | 0 | } |
195 | 0 | } |
196 | | |
197 | | template <class Iter> unsigned append(Iter I, Iter E) { |
198 | | size_t Osz = Size; |
199 | | size_t J = Osz; |
200 | | for (; J < Capacity && I != E; ++J, ++I) |
201 | | Data[J] = *I; |
202 | | Size = J; |
203 | | return J - Osz; |
204 | | } |
205 | | |
206 | 0 | llvm::iterator_range<reverse_iterator> reverse() { |
207 | 0 | return llvm::make_range(rbegin(), rend()); |
208 | 0 | } |
209 | | |
210 | | llvm::iterator_range<const_reverse_iterator> reverse() const { |
211 | | return llvm::make_range(rbegin(), rend()); |
212 | | } |
213 | | |
214 | | private: |
215 | | // std::max is annoying here, because it requires a reference, |
216 | | // thus forcing InitialCapacity to be initialized outside the .h file. |
217 | 0 | size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; } Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::SExpr*>::u_max(unsigned long, unsigned long) Unexecuted instantiation: clang::threadSafety::til::SimpleArray<clang::threadSafety::til::BasicBlock*>::u_max(unsigned long, unsigned long) |
218 | | |
219 | | static const size_t InitialCapacity = 4; |
220 | | |
221 | | T *Data = nullptr; |
222 | | size_t Size = 0; |
223 | | size_t Capacity = 0; |
224 | | }; |
225 | | |
226 | | } // namespace til |
227 | | |
228 | | // A copy on write vector. |
229 | | // The vector can be in one of three states: |
230 | | // * invalid -- no operations are permitted. |
231 | | // * read-only -- read operations are permitted. |
232 | | // * writable -- read and write operations are permitted. |
233 | | // The init(), destroy(), and makeWritable() methods will change state. |
234 | | template<typename T> |
235 | | class CopyOnWriteVector { |
236 | | class VectorData { |
237 | | public: |
238 | | unsigned NumRefs = 1; |
239 | | std::vector<T> Vect; |
240 | | |
241 | 0 | VectorData() = default; |
242 | 0 | VectorData(const VectorData &VD) : Vect(VD.Vect) {} |
243 | | }; |
244 | | |
245 | | public: |
246 | 2.25k | CopyOnWriteVector() = default; |
247 | 0 | CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; } |
248 | | |
249 | 0 | CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { |
250 | 0 | destroy(); |
251 | 0 | Data = V.Data; |
252 | 0 | V.Data = nullptr; |
253 | 0 | return *this; |
254 | 0 | } |
255 | | |
256 | | // No copy constructor or copy assignment. Use clone() with move assignment. |
257 | | CopyOnWriteVector(const CopyOnWriteVector &) = delete; |
258 | | CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete; |
259 | | |
260 | 2.25k | ~CopyOnWriteVector() { destroy(); } |
261 | | |
262 | | // Returns true if this holds a valid vector. |
263 | 0 | bool valid() const { return Data; } |
264 | | |
265 | | // Returns true if this vector is writable. |
266 | 0 | bool writable() const { return Data && Data->NumRefs == 1; } |
267 | | |
268 | | // If this vector is not valid, initialize it to a valid vector. |
269 | | void init() { |
270 | | if (!Data) { |
271 | | Data = new VectorData(); |
272 | | } |
273 | | } |
274 | | |
275 | | // Destroy this vector; thus making it invalid. |
276 | 2.25k | void destroy() { |
277 | 2.25k | if (!Data) |
278 | 2.25k | return; |
279 | 0 | if (Data->NumRefs <= 1) |
280 | 0 | delete Data; |
281 | 0 | else |
282 | 0 | --Data->NumRefs; |
283 | 0 | Data = nullptr; |
284 | 0 | } |
285 | | |
286 | | // Make this vector writable, creating a copy if needed. |
287 | 0 | void makeWritable() { |
288 | 0 | if (!Data) { |
289 | 0 | Data = new VectorData(); |
290 | 0 | return; |
291 | 0 | } |
292 | 0 | if (Data->NumRefs == 1) |
293 | 0 | return; // already writeable. |
294 | 0 | --Data->NumRefs; |
295 | 0 | Data = new VectorData(*Data); |
296 | 0 | } |
297 | | |
298 | | // Create a lazy copy of this vector. |
299 | 0 | CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } |
300 | | |
301 | | using const_iterator = typename std::vector<T>::const_iterator; |
302 | | |
303 | 0 | const std::vector<T> &elements() const { return Data->Vect; } |
304 | | |
305 | | const_iterator begin() const { return elements().cbegin(); } |
306 | | const_iterator end() const { return elements().cend(); } |
307 | | |
308 | 0 | const T& operator[](unsigned i) const { return elements()[i]; } |
309 | | |
310 | 0 | unsigned size() const { return Data ? elements().size() : 0; } |
311 | | |
312 | | // Return true if V and this vector refer to the same data. |
313 | 0 | bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; } |
314 | | |
315 | | // Clear vector. The vector must be writable. |
316 | | void clear() { |
317 | | assert(writable() && "Vector is not writable!"); |
318 | | Data->Vect.clear(); |
319 | | } |
320 | | |
321 | | // Push a new element onto the end. The vector must be writable. |
322 | 0 | void push_back(const T &Elem) { |
323 | 0 | assert(writable() && "Vector is not writable!"); |
324 | 0 | Data->Vect.push_back(Elem); |
325 | 0 | } |
326 | | |
327 | | // Gets a mutable reference to the element at index(i). |
328 | | // The vector must be writable. |
329 | 0 | T& elem(unsigned i) { |
330 | 0 | assert(writable() && "Vector is not writable!"); |
331 | 0 | return Data->Vect[i]; |
332 | 0 | } |
333 | | |
334 | | // Drops elements from the back until the vector has size i. |
335 | 0 | void downsize(unsigned i) { |
336 | 0 | assert(writable() && "Vector is not writable!"); |
337 | 0 | Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end()); |
338 | 0 | } |
339 | | |
340 | | private: |
341 | 0 | CopyOnWriteVector(VectorData *D) : Data(D) { |
342 | 0 | if (!Data) |
343 | 0 | return; |
344 | 0 | ++Data->NumRefs; |
345 | 0 | } |
346 | | |
347 | | VectorData *Data = nullptr; |
348 | | }; |
349 | | |
350 | 2.79k | inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { |
351 | 2.79k | return ss.write(str.data(), str.size()); |
352 | 2.79k | } |
353 | | |
354 | | } // namespace threadSafety |
355 | | } // namespace clang |
356 | | |
357 | | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H |