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