clang  6.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/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:
44  MemRegionRef() : Allocator(nullptr) {}
45  MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
46 
47  void *allocate(size_t Sz) {
48  return Allocator->Allocate(Sz, alignof(AlignmentType));
49  }
50 
51  template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
52 
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 
65 inline void *operator new(size_t Sz,
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;
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:
84  SimpleArray() : Data(nullptr), Size(0), Capacity(0) {}
85  SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
86  : Data(Dat), Size(Sz), Capacity(Cp) {}
87  SimpleArray(MemRegionRef A, size_t Cp)
88  : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {}
90  : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
91  A.Data = nullptr;
92  A.Size = 0;
93  A.Capacity = 0;
94  }
95 
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.
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.
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 
131  size_t size() const { return Size; }
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  }
142  T &back() {
143  assert(Size && "No elements in the array.");
144  return Data[Size - 1];
145  }
146  const T &back() const {
147  assert(Size && "No elements in the array.");
148  return Data[Size - 1];
149  }
150 
151  iterator begin() { return Data; }
152  iterator end() { return Data + Size; }
153 
154  const_iterator begin() const { return Data; }
155  const_iterator end() const { return Data + Size; }
156 
157  const_iterator cbegin() const { return Data; }
158  const_iterator cend() const { return Data + Size; }
159 
160  reverse_iterator rbegin() { return reverse_iterator(end()); }
161  reverse_iterator rend() { return reverse_iterator(begin()); }
162 
163  const_reverse_iterator rbegin() const {
164  return const_reverse_iterator(end());
165  }
166  const_reverse_iterator rend() const {
167  return const_reverse_iterator(begin());
168  }
169 
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 
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 
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 
198  llvm::iterator_range<reverse_iterator> reverse() {
199  return llvm::make_range(rbegin(), rend());
200  }
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.
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>
229  class VectorData {
230  public:
231  VectorData() : NumRefs(1) { }
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:
243  CopyOnWriteVector() : Data(nullptr) {}
244  CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
245  ~CopyOnWriteVector() { destroy(); }
246 
247  // Returns true if this holds a valid vector.
248  bool valid() const { return Data; }
249 
250  // Returns true if this vector is writable.
251  bool writable() const { return Data && Data->NumRefs == 1; }
252 
253  // If this vector is not valid, initialize it to a valid vector.
254  void init() {
255  if (!Data) {
256  Data = new VectorData();
257  }
258  }
259 
260  // Destroy this vector; thus making it invalid.
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.
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.
285 
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 
295  const std::vector<T> &elements() const { return Data->Vect; }
296 
297  const_iterator begin() const { return elements().cbegin(); }
298  const_iterator end() const { return elements().cend(); }
299 
300  const T& operator[](unsigned i) const { return elements()[i]; }
301 
302  unsigned size() const { return Data ? elements().size() : 0; }
303 
304  // Return true if V and this vector refer to the same data.
305  bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
306 
307  // Clear vector. The vector must be writable.
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.
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.
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.
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:
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
SimpleArray(T *Dat, size_t Cp, size_t Sz=0)
const_reverse_iterator rbegin() const
Defines the clang::Expr interface and subclasses for C++ expressions.
std::vector< T >::const_iterator const_iterator
llvm::iterator_range< reverse_iterator > reverse()
std::reverse_iterator< const_iterator > const_reverse_iterator
Expr - This represents one expression.
Definition: Expr.h:106
const FunctionProtoType * T
std::reverse_iterator< iterator > reverse_iterator
const T & operator[](unsigned i) const
Encodes a location in the source.
std::ostream & operator<<(std::ostream &ss, const StringRef str)
CopyOnWriteVector & operator=(CopyOnWriteVector &&V)
llvm::iterator_range< const_reverse_iterator > reverse() const
std::string getSourceLiteralString(const clang::Expr *CE)
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