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