1 //===- ThreadSafetyUtil.h --------------------------------------*- C++ --*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines some basic utility classes for use by ThreadSafetyTIL.h
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
15 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
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"
29 namespace threadSafety {
32 // Simple wrapper class to abstract away from the details of memory management.
33 // SExprs are allocated in pools, and deallocated all at once.
44 MemRegionRef() : Allocator(nullptr) {}
45 MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
47 void *allocate(size_t Sz) {
48 return Allocator->Allocate(Sz, llvm::AlignOf<AlignmentType>::Alignment);
51 template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
53 template <typename T> T *allocateT(size_t NumElems) {
54 return Allocator->Allocate<T>(NumElems);
58 llvm::BumpPtrAllocator *Allocator;
62 } // end namespace til
63 } // end namespace threadSafety
64 } // end namespace clang
67 inline void *operator new(size_t Sz,
68 clang::threadSafety::til::MemRegionRef &R) {
69 return R.allocate(Sz);
74 namespace threadSafety {
76 std::string getSourceLiteralString(const clang::Expr *CE);
78 using llvm::StringRef;
79 using clang::SourceLocation;
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 {
88 SimpleArray() : Data(nullptr), Size(0), Capacity(0) {}
89 SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
90 : Data(Dat), Size(Sz), Capacity(Cp) {}
91 SimpleArray(MemRegionRef A, size_t Cp)
92 : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Size(0), Capacity(Cp) {}
93 SimpleArray(SimpleArray<T> &&A)
94 : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
100 SimpleArray &operator=(SimpleArray &&RHS) {
104 Capacity = RHS.Capacity;
107 RHS.Size = RHS.Capacity = 0;
112 // Reserve space for at least Ncp items, reallocating if necessary.
113 void reserve(size_t Ncp, MemRegionRef A) {
117 Data = A.allocateT<T>(Ncp);
119 memcpy(Data, Odata, sizeof(T) * Size);
123 // Reserve space for at least N more items.
124 void reserveCheck(size_t N, MemRegionRef A) {
126 reserve(u_max(InitialCapacity, N), A);
127 else if (Size + N < Capacity)
128 reserve(u_max(Size + N, Capacity * 2), A);
132 typedef const T *const_iterator;
134 size_t size() const { return Size; }
135 size_t capacity() const { return Capacity; }
137 T &operator[](unsigned i) {
138 assert(i < Size && "Array index out of bounds.");
141 const T &operator[](unsigned i) const {
142 assert(i < Size && "Array index out of bounds.");
146 assert(Size && "No elements in the array.");
147 return Data[Size - 1];
149 const T &back() const {
150 assert(Size && "No elements in the array.");
151 return Data[Size - 1];
154 iterator begin() { return Data; }
155 iterator end() { return Data + Size; }
157 const_iterator begin() const { return Data; }
158 const_iterator end() const { return Data + Size; }
160 const_iterator cbegin() const { return Data; }
161 const_iterator cend() const { return Data + Size; }
163 void push_back(const T &Elem) {
164 assert(Size < Capacity);
168 // drop last n elements from array
169 void drop(unsigned n = 0) {
174 void setValues(unsigned Sz, const T& C) {
175 assert(Sz <= Capacity);
177 for (unsigned i = 0; i < Sz; ++i) {
182 template <class Iter> unsigned append(Iter I, Iter E) {
185 for (; J < Capacity && I != E; ++J, ++I)
191 // An adaptor to reverse a simple array
192 class ReverseAdaptor {
194 ReverseAdaptor(SimpleArray &Array) : Array(Array) {}
195 // A reverse iterator used by the reverse adaptor
198 Iterator(T *Data) : Data(Data) {}
199 T &operator*() { return *Data; }
200 const T &operator*() const { return *Data; }
201 Iterator &operator++() {
205 bool operator!=(Iterator Other) { return Data != Other.Data; }
210 Iterator begin() { return Array.end() - 1; }
211 Iterator end() { return Array.begin() - 1; }
212 const Iterator begin() const { return Array.end() - 1; }
213 const Iterator end() const { return Array.begin() - 1; }
219 const ReverseAdaptor reverse() const { return ReverseAdaptor(*this); }
220 ReverseAdaptor reverse() { return ReverseAdaptor(*this); }
223 // std::max is annoying here, because it requires a reference,
224 // thus forcing InitialCapacity to be initialized outside the .h file.
225 size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
227 static const size_t InitialCapacity = 4;
229 SimpleArray(const SimpleArray<T> &A) LLVM_DELETED_FUNCTION;
237 } // end namespace til
240 // A copy on write vector.
241 // The vector can be in one of three states:
242 // * invalid -- no operations are permitted.
243 // * read-only -- read operations are permitted.
244 // * writable -- read and write operations are permitted.
245 // The init(), destroy(), and makeWritable() methods will change state.
247 class CopyOnWriteVector {
250 VectorData() : NumRefs(1) { }
251 VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { }
257 // No copy constructor or copy assignment. Use clone() with move assignment.
258 CopyOnWriteVector(const CopyOnWriteVector &V) LLVM_DELETED_FUNCTION;
259 void operator=(const CopyOnWriteVector &V) LLVM_DELETED_FUNCTION;
262 CopyOnWriteVector() : Data(nullptr) {}
263 CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
264 ~CopyOnWriteVector() { destroy(); }
266 // Returns true if this holds a valid vector.
267 bool valid() const { return Data; }
269 // Returns true if this vector is writable.
270 bool writable() const { return Data && Data->NumRefs == 1; }
272 // If this vector is not valid, initialize it to a valid vector.
275 Data = new VectorData();
279 // Destroy this vector; thus making it invalid.
283 if (Data->NumRefs <= 1)
290 // Make this vector writable, creating a copy if needed.
291 void makeWritable() {
293 Data = new VectorData();
296 if (Data->NumRefs == 1)
297 return; // already writeable.
299 Data = new VectorData(*Data);
302 // Create a lazy copy of this vector.
303 CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
305 CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
312 typedef typename std::vector<T>::const_iterator const_iterator;
314 const std::vector<T> &elements() const { return Data->Vect; }
316 const_iterator begin() const { return elements().cbegin(); }
317 const_iterator end() const { return elements().cend(); }
319 const T& operator[](unsigned i) const { return elements()[i]; }
321 unsigned size() const { return Data ? elements().size() : 0; }
323 // Return true if V and this vector refer to the same data.
324 bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
326 // Clear vector. The vector must be writable.
328 assert(writable() && "Vector is not writable!");
332 // Push a new element onto the end. The vector must be writable.
333 void push_back(const T &Elem) {
334 assert(writable() && "Vector is not writable!");
335 Data->Vect.push_back(Elem);
338 // Gets a mutable reference to the element at index(i).
339 // The vector must be writable.
340 T& elem(unsigned i) {
341 assert(writable() && "Vector is not writable!");
342 return Data->Vect[i];
345 // Drops elements from the back until the vector has size i.
346 void downsize(unsigned i) {
347 assert(writable() && "Vector is not writable!");
348 Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
352 CopyOnWriteVector(VectorData *D) : Data(D) {
362 inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
363 return ss.write(str.data(), str.size());
367 } // end namespace threadSafety
368 } // end namespace clang
370 #endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H