contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyUtil.h

   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
  62 } // end namespace til
  63 } // end namespace threadSafety
  64 } // end namespace clang
  65
  66
  67 inline void *operator new(size_t Sz,
  68                           clang::threadSafety::til::MemRegionRef &R) {
  69   return R.allocate(Sz);
  70 }
  71
  72
  73 namespace clang {
  74 namespace threadSafety {
  75
  76 std::string getSourceLiteralString(const clang::Expr *CE);
  77
  78 using llvm::StringRef;
  79 using clang::SourceLocation;
  80
  81 namespace til {
  82
  83
  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 {
  87 public:
  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) {
  95     A.Data = nullptr;
  96     A.Size = 0;
  97     A.Capacity = 0;
  98   }
  99
 100   SimpleArray &operator=(SimpleArray &&RHS) {
 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     return;
 121   }
 122
 123   // Reserve space for at least N more items.
 124   void reserveCheck(size_t N, MemRegionRef A) {
 125     if (Capacity == 0)
 126       reserve(u_max(InitialCapacity, N), A);
 127     else if (Size + N < Capacity)
 128       reserve(u_max(Size + N, Capacity * 2), A);
 129   }
 130
 131   typedef T *iterator;
 132   typedef const T *const_iterator;
 133
 134   size_t size() const { return Size; }
 135   size_t capacity() const { return Capacity; }
 136
 137   T &operator[](unsigned i) {
 138     assert(i < Size && "Array index out of bounds.");
 139     return Data[i];
 140   }
 141   const T &operator[](unsigned i) const {
 142     assert(i < Size && "Array index out of bounds.");
 143     return Data[i];
 144   }
 145   T &back() {
 146     assert(Size && "No elements in the array.");
 147     return Data[Size - 1];
 148   }
 149   const T &back() const {
 150     assert(Size && "No elements in the array.");
 151     return Data[Size - 1];
 152   }
 153
 154   iterator begin() { return Data; }
 155   iterator end()   { return Data + Size; }
 156
 157   const_iterator begin() const { return Data; }
 158   const_iterator end()   const { return Data + Size; }
 159
 160   const_iterator cbegin() const { return Data; }
 161   const_iterator cend()   const { return Data + Size; }
 162
 163   void push_back(const T &Elem) {
 164     assert(Size < Capacity);
 165     Data[Size++] = Elem;
 166   }
 167
 168   // drop last n elements from array
 169   void drop(unsigned n = 0) {
 170     assert(Size > n);
 171     Size -= n;
 172   }
 173
 174   void setValues(unsigned Sz, const T& C) {
 175     assert(Sz <= Capacity);
 176     Size = Sz;
 177     for (unsigned i = 0; i < Sz; ++i) {
 178       Data[i] = C;
 179     }
 180   }
 181
 182   template <class Iter> unsigned append(Iter I, Iter E) {
 183     size_t Osz = Size;
 184     size_t J = Osz;
 185     for (; J < Capacity && I != E; ++J, ++I)
 186       Data[J] = *I;
 187     Size = J;
 188     return J - Osz;
 189   }
 190
 191   // An adaptor to reverse a simple array
 192   class ReverseAdaptor {
 193    public:
 194     ReverseAdaptor(SimpleArray &Array) : Array(Array) {}
 195     // A reverse iterator used by the reverse adaptor
 196     class Iterator {
 197      public:
 198       Iterator(T *Data) : Data(Data) {}
 199       T &operator*() { return *Data; }
 200       const T &operator*() const { return *Data; }
 201       Iterator &operator++() {
 202         --Data;
 203         return *this;
 204       }
 205       bool operator!=(Iterator Other) { return Data != Other.Data; }
 206
 207      private:
 208       T *Data;
 209     };
 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; }
 214
 215    private:
 216     SimpleArray &Array;
 217   };
 218
 219   const ReverseAdaptor reverse() const { return ReverseAdaptor(*this); }
 220   ReverseAdaptor reverse() { return ReverseAdaptor(*this); }
 221
 222 private:
 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; }
 226
 227   static const size_t InitialCapacity = 4;
 228
 229   SimpleArray(const SimpleArray<T> &A) LLVM_DELETED_FUNCTION;
 230
 231   T *Data;
 232   size_t Size;
 233   size_t Capacity;
 234 };
 235
 236
 237 }  // end namespace til
 238
 239
 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.
 246 template<typename T>
 247 class CopyOnWriteVector {
 248   class VectorData {
 249   public:
 250     VectorData() : NumRefs(1) { }
 251     VectorData(const VectorData &VD) : NumRefs(1), Vect(VD.Vect) { }
 252
 253     unsigned NumRefs;
 254     std::vector<T> Vect;
 255   };
 256
 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;
 260
 261 public:
 262   CopyOnWriteVector() : Data(nullptr) {}
 263   CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
 264   ~CopyOnWriteVector() { destroy(); }
 265
 266   // Returns true if this holds a valid vector.
 267   bool valid() const  { return Data; }
 268
 269   // Returns true if this vector is writable.
 270   bool writable() const { return Data && Data->NumRefs == 1; }
 271
 272   // If this vector is not valid, initialize it to a valid vector.
 273   void init() {
 274     if (!Data) {
 275       Data = new VectorData();
 276     }
 277   }
 278
 279   // Destroy this vector; thus making it invalid.
 280   void destroy() {
 281     if (!Data)
 282       return;
 283     if (Data->NumRefs <= 1)
 284       delete Data;
 285     else
 286       --Data->NumRefs;
 287     Data = nullptr;
 288   }
 289
 290   // Make this vector writable, creating a copy if needed.
 291   void makeWritable() {
 292     if (!Data) {
 293       Data = new VectorData();
 294       return;
 295     }
 296     if (Data->NumRefs == 1)
 297       return;   // already writeable.
 298     --Data->NumRefs;
 299     Data = new VectorData(*Data);
 300   }
 301
 302   // Create a lazy copy of this vector.
 303   CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
 304
 305   CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
 306     destroy();
 307     Data = V.Data;
 308     V.Data = nullptr;
 309     return *this;
 310   }
 311
 312   typedef typename std::vector<T>::const_iterator const_iterator;
 313
 314   const std::vector<T> &elements() const { return Data->Vect; }
 315
 316   const_iterator begin() const { return elements().cbegin(); }
 317   const_iterator end() const { return elements().cend(); }
 318
 319   const T& operator[](unsigned i) const { return elements()[i]; }
 320
 321   unsigned size() const { return Data ? elements().size() : 0; }
 322
 323   // Return true if V and this vector refer to the same data.
 324   bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
 325
 326   // Clear vector.  The vector must be writable.
 327   void clear() {
 328     assert(writable() && "Vector is not writable!");
 329     Data->Vect.clear();
 330   }
 331
 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);
 336   }
 337
 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];
 343   }
 344
 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());
 349   }
 350
 351 private:
 352   CopyOnWriteVector(VectorData *D) : Data(D) {
 353     if (!Data)
 354       return;
 355     ++Data->NumRefs;
 356   }
 357
 358   VectorData *Data;
 359 };
 360
 361
 362 inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
 363   return ss.write(str.data(), str.size());
 364 }
 365
 366
 367 } // end namespace threadSafety
 368 } // end namespace clang
 369
 370 #endif  // LLVM_CLANG_THREAD_SAFETY_UTIL_H