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_THREAD_SAFETY_UTIL_H
15 #define LLVM_CLANG_THREAD_SAFETY_UTIL_H
16
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/Support/AlignOf.h"
19 #include "llvm/Support/Allocator.h"
20 #include "llvm/Support/Compiler.h"
21 #include "clang/AST/ExprCXX.h"
22
23 #include <cassert>
24 #include <cstddef>
25 #include <vector>
26 #include <utility>
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
62 } // end namespace til
63 } // end namespace threadSafety
64 } // end namespace clang
65
66
new(size_t Sz,clang::threadSafety::til::MemRegionRef & R)67 inline void *operator new(size_t Sz,
68 clang::threadSafety::til::MemRegionRef &R) {
69 return R.allocate(Sz);
70 }
71
72
73 namespace clang {
74 namespace threadSafety {
75
76 std::string getSourceLiteralString(const clang::Expr *CE);
77
78 using llvm::StringRef;
79 using clang::SourceLocation;
80
81 namespace til {
82
83
84 // A simple fixed size array class that does not manage its own memory,
85 // suitable for use with bump pointer allocation.
86 template <class T> class SimpleArray {
87 public:
SimpleArray()88 SimpleArray() : Data(nullptr), Size(0), Capacity(0) {}
89 SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
Data(Dat)90 : Data(Dat), Size(Sz), Capacity(Cp) {}
SimpleArray(MemRegionRef A,size_t Cp)91 SimpleArray(MemRegionRef A, size_t Cp)
92 : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {}
SimpleArray(SimpleArray<T> && A)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.
reserve(size_t Ncp,MemRegionRef A)113 void reserve(size_t Ncp, MemRegionRef A) {
114 if (Ncp <= Capacity)
115 return;
116 T *Odata = Data;
117 Data = A.allocateT<T>(Ncp);
118 Capacity = Ncp;
119 memcpy(Data, Odata, sizeof(T) * Size);
120 return;
121 }
122
123 // Reserve space for at least N more items.
reserveCheck(size_t N,MemRegionRef A)124 void reserveCheck(size_t N, MemRegionRef A) {
125 if (Capacity == 0)
126 reserve(u_max(InitialCapacity, N), A);
127 else if (Size + N < Capacity)
128 reserve(u_max(Size + N, Capacity * 2), A);
129 }
130
131 typedef T *iterator;
132 typedef const T *const_iterator;
133
size()134 size_t size() const { return Size; }
capacity()135 size_t capacity() const { return Capacity; }
136
137 T &operator[](unsigned i) {
138 assert(i < Size && "Array index out of bounds.");
139 return Data[i];
140 }
141 const T &operator[](unsigned i) const {
142 assert(i < Size && "Array index out of bounds.");
143 return Data[i];
144 }
145
begin()146 iterator begin() { return Data; }
end()147 iterator end() { return Data + Size; }
148
cbegin()149 const_iterator cbegin() const { return Data; }
cend()150 const_iterator cend() const { return Data + Size; }
151
push_back(const T & Elem)152 void push_back(const T &Elem) {
153 assert(Size < Capacity);
154 Data[Size++] = Elem;
155 }
156
setValues(unsigned Sz,const T & C)157 void setValues(unsigned Sz, const T& C) {
158 assert(Sz <= Capacity);
159 Size = Sz;
160 for (unsigned i = 0; i < Sz; ++i) {
161 Data[i] = C;
162 }
163 }
164
append(Iter I,Iter E)165 template <class Iter> unsigned append(Iter I, Iter E) {
166 size_t Osz = Size;
167 size_t J = Osz;
168 for (; J < Capacity && I != E; ++J, ++I)
169 Data[J] = *I;
170 Size = J;
171 return J - Osz;
172 }
173
174 private:
175 // std::max is annoying here, because it requires a reference,
176 // thus forcing InitialCapacity to be initialized outside the .h file.
u_max(size_t i,size_t j)177 size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
178
179 static const size_t InitialCapacity = 4;
180
181 SimpleArray(const SimpleArray<T> &A) LLVM_DELETED_FUNCTION;
182
183 T *Data;
184 size_t Size;
185 size_t Capacity;
186 };
187
188 } // end namespace til
189
190
191 // A copy on write vector.
192 // The vector can be in one of three states:
193 // * invalid -- no operations are permitted.
194 // * read-only -- read operations are permitted.
195 // * writable -- read and write operations are permitted.
196 // The init(), destroy(), and makeWritable() methods will change state.
197 template<typename T>
198 class CopyOnWriteVector {
199 class VectorData {
200 public:
VectorData()201 VectorData() : NumRefs(1) { }
VectorData(const VectorData & VD)202 VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { }
203
204 unsigned NumRefs;
205 std::vector<T> Vect;
206 };
207
208 // No copy constructor or copy assignment. Use clone() with move assignment.
209 CopyOnWriteVector(const CopyOnWriteVector &V) LLVM_DELETED_FUNCTION;
210 void operator=(const CopyOnWriteVector &V) LLVM_DELETED_FUNCTION;
211
212 public:
CopyOnWriteVector()213 CopyOnWriteVector() : Data(nullptr) {}
CopyOnWriteVector(CopyOnWriteVector && V)214 CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
~CopyOnWriteVector()215 ~CopyOnWriteVector() { destroy(); }
216
217 // Returns true if this holds a valid vector.
valid()218 bool valid() const { return Data; }
219
220 // Returns true if this vector is writable.
writable()221 bool writable() const { return Data && Data->NumRefs == 1; }
222
223 // If this vector is not valid, initialize it to a valid vector.
init()224 void init() {
225 if (!Data) {
226 Data = new VectorData();
227 }
228 }
229
230 // Destroy this vector; thus making it invalid.
destroy()231 void destroy() {
232 if (!Data)
233 return;
234 if (Data->NumRefs <= 1)
235 delete Data;
236 else
237 --Data->NumRefs;
238 Data = nullptr;
239 }
240
241 // Make this vector writable, creating a copy if needed.
makeWritable()242 void makeWritable() {
243 if (!Data) {
244 Data = new VectorData();
245 return;
246 }
247 if (Data->NumRefs == 1)
248 return; // already writeable.
249 --Data->NumRefs;
250 Data = new VectorData(*Data);
251 }
252
253 // Create a lazy copy of this vector.
clone()254 CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
255
256 CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
257 destroy();
258 Data = V.Data;
259 V.Data = nullptr;
260 return *this;
261 }
262
263 typedef typename std::vector<T>::const_iterator const_iterator;
264
elements()265 const std::vector<T> &elements() const { return Data->Vect; }
266
begin()267 const_iterator begin() const { return elements().cbegin(); }
end()268 const_iterator end() const { return elements().cend(); }
269
270 const T& operator[](unsigned i) const { return elements()[i]; }
271
size()272 unsigned size() const { return Data ? elements().size() : 0; }
273
274 // Return true if V and this vector refer to the same data.
sameAs(const CopyOnWriteVector & V)275 bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
276
277 // Clear vector. The vector must be writable.
clear()278 void clear() {
279 assert(writable() && "Vector is not writable!");
280 Data->Vect.clear();
281 }
282
283 // Push a new element onto the end. The vector must be writable.
push_back(const T & Elem)284 void push_back(const T &Elem) {
285 assert(writable() && "Vector is not writable!");
286 Data->Vect.push_back(Elem);
287 }
288
289 // Gets a mutable reference to the element at index(i).
290 // The vector must be writable.
elem(unsigned i)291 T& elem(unsigned i) {
292 assert(writable() && "Vector is not writable!");
293 return Data->Vect[i];
294 }
295
296 // Drops elements from the back until the vector has size i.
downsize(unsigned i)297 void downsize(unsigned i) {
298 assert(writable() && "Vector is not writable!");
299 Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
300 }
301
302 private:
CopyOnWriteVector(VectorData * D)303 CopyOnWriteVector(VectorData *D) : Data(D) {
304 if (!Data)
305 return;
306 ++Data->NumRefs;
307 }
308
309 VectorData *Data;
310 };
311
312
313 } // end namespace threadSafety
314 } // end namespace clang
315
316 #endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H
317