clang  10.0.0svn
ThreadSafetyUtil.h
Go to the documentation of this file.
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  MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
50 
51  void *allocate(size_t Sz) {
52  return Allocator->Allocate(Sz, alignof(AlignmentType));
53  }
54 
55  template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
56 
57  template <typename T> T *allocateT(size_t NumElems) {
58  return Allocator->Allocate<T>(NumElems);
59  }
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,
72  return R.allocate(Sz);
73 }
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  SimpleArray() = default;
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  : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {}
91  SimpleArray(const SimpleArray<T> &A) = delete;
92 
94  : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
95  A.Data = nullptr;
96  A.Size = 0;
97  A.Capacity = 0;
98  }
99 
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  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  }
121 
122  // Reserve space for at least N more items.
123  void reserveCheck(size_t N, MemRegionRef A) {
124  if (Capacity == 0)
125  reserve(u_max(InitialCapacity, N), A);
126  else if (Size + N < Capacity)
127  reserve(u_max(Size + N, Capacity * 2), A);
128  }
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  size_t size() const { return Size; }
136  size_t capacity() const { return Capacity; }
137 
138  T &operator[](unsigned i) {
139  assert(i < Size && "Array index out of bounds.");
140  return Data[i];
141  }
142 
143  const T &operator[](unsigned i) const {
144  assert(i < Size && "Array index out of bounds.");
145  return Data[i];
146  }
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  iterator begin() { return Data; }
159  iterator end() { return Data + Size; }
160 
161  const_iterator begin() const { return Data; }
162  const_iterator end() const { return Data + Size; }
163 
164  const_iterator cbegin() const { return Data; }
165  const_iterator cend() const { return Data + Size; }
166 
168  reverse_iterator rend() { return reverse_iterator(begin()); }
169 
171  return const_reverse_iterator(end());
172  }
173 
175  return const_reverse_iterator(begin());
176  }
177 
178  void push_back(const T &Elem) {
179  assert(Size < Capacity);
180  Data[Size++] = Elem;
181  }
182 
183  // drop last n elements from array
184  void drop(unsigned n = 0) {
185  assert(Size > n);
186  Size -= n;
187  }
188 
189  void setValues(unsigned Sz, const T& C) {
190  assert(Sz <= Capacity);
191  Size = Sz;
192  for (unsigned i = 0; i < Sz; ++i) {
193  Data[i] = C;
194  }
195  }
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  llvm::iterator_range<reverse_iterator> reverse() {
207  return llvm::make_range(rbegin(), rend());
208  }
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  size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
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>
236  class VectorData {
237  public:
238  unsigned NumRefs = 1;
239  std::vector<T> Vect;
240 
241  VectorData() = default;
242  VectorData(const VectorData &VD) : Vect(VD.Vect) {}
243  };
244 
245 public:
246  CopyOnWriteVector() = default;
247  CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
248 
250  destroy();
251  Data = V.Data;
252  V.Data = nullptr;
253  return *this;
254  }
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  ~CopyOnWriteVector() { destroy(); }
261 
262  // Returns true if this holds a valid vector.
263  bool valid() const { return Data; }
264 
265  // Returns true if this vector is writable.
266  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  void destroy() {
277  if (!Data)
278  return;
279  if (Data->NumRefs <= 1)
280  delete Data;
281  else
282  --Data->NumRefs;
283  Data = nullptr;
284  }
285 
286  // Make this vector writable, creating a copy if needed.
287  void makeWritable() {
288  if (!Data) {
289  Data = new VectorData();
290  return;
291  }
292  if (Data->NumRefs == 1)
293  return; // already writeable.
294  --Data->NumRefs;
295  Data = new VectorData(*Data);
296  }
297 
298  // Create a lazy copy of this vector.
300 
301  using const_iterator = typename std::vector<T>::const_iterator;
302 
303  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  const T& operator[](unsigned i) const { return elements()[i]; }
309 
310  unsigned size() const { return Data ? elements().size() : 0; }
311 
312  // Return true if V and this vector refer to the same data.
313  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  void push_back(const T &Elem) {
323  assert(writable() && "Vector is not writable!");
324  Data->Vect.push_back(Elem);
325  }
326 
327  // Gets a mutable reference to the element at index(i).
328  // The vector must be writable.
329  T& elem(unsigned i) {
330  assert(writable() && "Vector is not writable!");
331  return Data->Vect[i];
332  }
333 
334  // Drops elements from the back until the vector has size i.
335  void downsize(unsigned i) {
336  assert(writable() && "Vector is not writable!");
337  Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
338  }
339 
340 private:
341  CopyOnWriteVector(VectorData *D) : Data(D) {
342  if (!Data)
343  return;
344  ++Data->NumRefs;
345  }
346 
347  VectorData *Data = nullptr;
348 };
349 
350 inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
351  return ss.write(str.data(), str.size());
352 }
353 
354 } // namespace threadSafety
355 } // namespace clang
356 
357 #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()
#define V(N, I)
Definition: ASTContext.h:2915
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