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, llvm::AlignOf<AlignmentType>::Alignment); 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, 66 clang::threadSafety::til::MemRegionRef &R) { 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; 76 using clang::SourceLocation; 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) {} 89 SimpleArray(SimpleArray<T> &&A) 90 : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { 91 A.Data = nullptr; 92 A.Size = 0; 93 A.Capacity = 0; 94 } 95 96 SimpleArray &operator=(SimpleArray &&RHS) { 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> 228 class CopyOnWriteVector { 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. 284 CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } 285 286 CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { 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 350