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