Analysis/Analyses/ThreadSafetyUtil.h

0001 //===- ThreadSafetyUtil.h ---------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines some basic utility classes for use by ThreadSafetyTIL.h
0010 //
0011 //===----------------------------------------------------------------------===//
0012
0013 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
0014 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H
0015
0016 #include "clang/AST/Decl.h"
0017 #include "clang/Basic/LLVM.h"
0018 #include "llvm/ADT/StringRef.h"
0019 #include "llvm/ADT/iterator_range.h"
0020 #include "llvm/Support/Allocator.h"
0021 #include <cassert>
0022 #include <cstddef>
0023 #include <cstring>
0024 #include <iterator>
0025 #include <ostream>
0026 #include <string>
0027 #include <vector>
0028
0029 namespace clang {
0030
0031 class Expr;
0032
0033 namespace threadSafety {
0034 namespace til {
0035
0036 // Simple wrapper class to abstract away from the details of memory management.
0037 // SExprs are allocated in pools, and deallocated all at once.
0038 class MemRegionRef {
0039 private:
0040   union AlignmentType {
0041     double d;
0042     void *p;
0043     long double dd;
0044     long long ii;
0045   };
0046
0047 public:
0048   MemRegionRef() = default;
0049   MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {}
0050
0051   void *allocate(size_t Sz) {
0052     return Allocator->Allocate(Sz, alignof(AlignmentType));
0053   }
0054
0055   template <typename T> T *allocateT() { return Allocator->Allocate<T>(); }
0056
0057   template <typename T> T *allocateT(size_t NumElems) {
0058     return Allocator->Allocate<T>(NumElems);
0059   }
0060
0061 private:
0062   llvm::BumpPtrAllocator *Allocator = nullptr;
0063 };
0064
0065 } // namespace til
0066 } // namespace threadSafety
0067
0068 } // namespace clang
0069
0070 inline void *operator new(size_t Sz,
0071                           clang::threadSafety::til::MemRegionRef &R) {
0072   return R.allocate(Sz);
0073 }
0074
0075 namespace clang {
0076 namespace threadSafety {
0077
0078 std::string getSourceLiteralString(const Expr *CE);
0079
0080 namespace til {
0081
0082 // A simple fixed size array class that does not manage its own memory,
0083 // suitable for use with bump pointer allocation.
0084 template <class T> class SimpleArray {
0085 public:
0086   SimpleArray() = default;
0087   SimpleArray(T *Dat, size_t Cp, size_t Sz = 0)
0088       : Data(Dat), Size(Sz), Capacity(Cp) {}
0089   SimpleArray(MemRegionRef A, size_t Cp)
0090       : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {}
0091   SimpleArray(const SimpleArray<T> &A) = delete;
0092
0093   SimpleArray(SimpleArray<T> &&A)
0094       : Data(A.Data), Size(A.Size), Capacity(A.Capacity) {
0095     A.Data = nullptr;
0096     A.Size = 0;
0097     A.Capacity = 0;
0098   }
0099
0100   SimpleArray &operator=(SimpleArray &&RHS) {
0101     if (this != &RHS) {
0102       Data = RHS.Data;
0103       Size = RHS.Size;
0104       Capacity = RHS.Capacity;
0105
0106       RHS.Data = nullptr;
0107       RHS.Size = RHS.Capacity = 0;
0108     }
0109     return *this;
0110   }
0111
0112   // Reserve space for at least Ncp items, reallocating if necessary.
0113   void reserve(size_t Ncp, MemRegionRef A) {
0114     if (Ncp <= Capacity)
0115       return;
0116     T *Odata = Data;
0117     Data = A.allocateT<T>(Ncp);
0118     Capacity = Ncp;
0119     memcpy(Data, Odata, sizeof(T) * Size);
0120   }
0121
0122   // Reserve space for at least N more items.
0123   void reserveCheck(size_t N, MemRegionRef A) {
0124     if (Capacity == 0)
0125       reserve(u_max(InitialCapacity, N), A);
0126     else if (Size + N < Capacity)
0127       reserve(u_max(Size + N, Capacity * 2), A);
0128   }
0129
0130   using iterator = T *;
0131   using const_iterator = const T *;
0132   using reverse_iterator = std::reverse_iterator<iterator>;
0133   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
0134
0135   size_t size() const { return Size; }
0136   size_t capacity() const { return Capacity; }
0137
0138   T &operator[](unsigned i) {
0139     assert(i < Size && "Array index out of bounds.");
0140     return Data[i];
0141   }
0142
0143   const T &operator[](unsigned i) const {
0144     assert(i < Size && "Array index out of bounds.");
0145     return Data[i];
0146   }
0147
0148   T &back() {
0149     assert(Size && "No elements in the array.");
0150     return Data[Size - 1];
0151   }
0152
0153   const T &back() const {
0154     assert(Size && "No elements in the array.");
0155     return Data[Size - 1];
0156   }
0157
0158   iterator begin() { return Data; }
0159   iterator end() { return Data + Size; }
0160
0161   const_iterator begin() const { return Data; }
0162   const_iterator end() const { return Data + Size; }
0163
0164   const_iterator cbegin() const { return Data; }
0165   const_iterator cend() const { return Data + Size; }
0166
0167   reverse_iterator rbegin() { return reverse_iterator(end()); }
0168   reverse_iterator rend() { return reverse_iterator(begin()); }
0169
0170   const_reverse_iterator rbegin() const {
0171     return const_reverse_iterator(end());
0172   }
0173
0174   const_reverse_iterator rend() const {
0175     return const_reverse_iterator(begin());
0176   }
0177
0178   void push_back(const T &Elem) {
0179     assert(Size < Capacity);
0180     Data[Size++] = Elem;
0181   }
0182
0183   // drop last n elements from array
0184   void drop(unsigned n = 0) {
0185     assert(Size > n);
0186     Size -= n;
0187   }
0188
0189   void setValues(unsigned Sz, const T& C) {
0190     assert(Sz <= Capacity);
0191     Size = Sz;
0192     for (unsigned i = 0; i < Sz; ++i) {
0193       Data[i] = C;
0194     }
0195   }
0196
0197   template <class Iter> unsigned append(Iter I, Iter E) {
0198     size_t Osz = Size;
0199     size_t J = Osz;
0200     for (; J < Capacity && I != E; ++J, ++I)
0201       Data[J] = *I;
0202     Size = J;
0203     return J - Osz;
0204   }
0205
0206   llvm::iterator_range<reverse_iterator> reverse() {
0207     return llvm::reverse(*this);
0208   }
0209
0210   llvm::iterator_range<const_reverse_iterator> reverse() const {
0211     return llvm::reverse(*this);
0212   }
0213
0214 private:
0215   // std::max is annoying here, because it requires a reference,
0216   // thus forcing InitialCapacity to be initialized outside the .h file.
0217   size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; }
0218
0219   static const size_t InitialCapacity = 4;
0220
0221   T *Data = nullptr;
0222   size_t Size = 0;
0223   size_t Capacity = 0;
0224 };
0225
0226 }  // namespace til
0227
0228 // A copy on write vector.
0229 // The vector can be in one of three states:
0230 // * invalid -- no operations are permitted.
0231 // * read-only -- read operations are permitted.
0232 // * writable -- read and write operations are permitted.
0233 // The init(), destroy(), and makeWritable() methods will change state.
0234 template<typename T>
0235 class CopyOnWriteVector {
0236   class VectorData {
0237   public:
0238     unsigned NumRefs = 1;
0239     std::vector<T> Vect;
0240
0241     VectorData() = default;
0242     VectorData(const VectorData &VD) : Vect(VD.Vect) {}
0243
0244     // The copy assignment operator is defined as deleted pending further
0245     // motivation.
0246     VectorData &operator=(const VectorData &) = delete;
0247   };
0248
0249 public:
0250   CopyOnWriteVector() = default;
0251   CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; }
0252
0253   CopyOnWriteVector &operator=(CopyOnWriteVector &&V) {
0254     destroy();
0255     Data = V.Data;
0256     V.Data = nullptr;
0257     return *this;
0258   }
0259
0260   // No copy constructor or copy assignment.  Use clone() with move assignment.
0261   CopyOnWriteVector(const CopyOnWriteVector &) = delete;
0262   CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete;
0263
0264   ~CopyOnWriteVector() { destroy(); }
0265
0266   // Returns true if this holds a valid vector.
0267   bool valid() const  { return Data; }
0268
0269   // Returns true if this vector is writable.
0270   bool writable() const { return Data && Data->NumRefs == 1; }
0271
0272   // If this vector is not valid, initialize it to a valid vector.
0273   void init() {
0274     if (!Data) {
0275       Data = new VectorData();
0276     }
0277   }
0278
0279   // Destroy this vector; thus making it invalid.
0280   void destroy() {
0281     if (!Data)
0282       return;
0283     if (Data->NumRefs <= 1)
0284       delete Data;
0285     else
0286       --Data->NumRefs;
0287     Data = nullptr;
0288   }
0289
0290   // Make this vector writable, creating a copy if needed.
0291   void makeWritable() {
0292     if (!Data) {
0293       Data = new VectorData();
0294       return;
0295     }
0296     if (Data->NumRefs == 1)
0297       return;   // already writeable.
0298     --Data->NumRefs;
0299     Data = new VectorData(*Data);
0300   }
0301
0302   // Create a lazy copy of this vector.
0303   CopyOnWriteVector clone() { return CopyOnWriteVector(Data); }
0304
0305   using const_iterator = typename std::vector<T>::const_iterator;
0306
0307   const std::vector<T> &elements() const { return Data->Vect; }
0308
0309   const_iterator begin() const { return elements().cbegin(); }
0310   const_iterator end() const { return elements().cend(); }
0311
0312   const T& operator[](unsigned i) const { return elements()[i]; }
0313
0314   unsigned size() const { return Data ? elements().size() : 0; }
0315
0316   // Return true if V and this vector refer to the same data.
0317   bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; }
0318
0319   // Clear vector.  The vector must be writable.
0320   void clear() {
0321     assert(writable() && "Vector is not writable!");
0322     Data->Vect.clear();
0323   }
0324
0325   // Push a new element onto the end.  The vector must be writable.
0326   void push_back(const T &Elem) {
0327     assert(writable() && "Vector is not writable!");
0328     Data->Vect.push_back(Elem);
0329   }
0330
0331   // Gets a mutable reference to the element at index(i).
0332   // The vector must be writable.
0333   T& elem(unsigned i) {
0334     assert(writable() && "Vector is not writable!");
0335     return Data->Vect[i];
0336   }
0337
0338   // Drops elements from the back until the vector has size i.
0339   void downsize(unsigned i) {
0340     assert(writable() && "Vector is not writable!");
0341     Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end());
0342   }
0343
0344 private:
0345   CopyOnWriteVector(VectorData *D) : Data(D) {
0346     if (!Data)
0347       return;
0348     ++Data->NumRefs;
0349   }
0350
0351   VectorData *Data = nullptr;
0352 };
0353
0354 inline std::ostream& operator<<(std::ostream& ss, const StringRef str) {
0355   return ss.write(str.data(), str.size());
0356 }
0357
0358 } // namespace threadSafety
0359 } // namespace clang
0360
0361 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H