| //===- ThreadSafetyUtil.h ---------------------------------------*- C++ -*-===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines some basic utility classes for use by ThreadSafetyTIL.h |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H |
| #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYUTIL_H |
| |
| #include "clang/AST/Decl.h" |
| #include "clang/Basic/LLVM.h" |
| #include "llvm/ADT/StringRef.h" |
| #include "llvm/ADT/iterator_range.h" |
| #include "llvm/Support/Allocator.h" |
| #include <cassert> |
| #include <cstddef> |
| #include <cstring> |
| #include <iterator> |
| #include <ostream> |
| #include <string> |
| #include <vector> |
| |
| namespace clang { |
| |
| class Expr; |
| |
| namespace threadSafety { |
| namespace til { |
| |
| // Simple wrapper class to abstract away from the details of memory management. |
| // SExprs are allocated in pools, and deallocated all at once. |
| class MemRegionRef { |
| private: |
| union AlignmentType { |
| double d; |
| void *p; |
| long double dd; |
| long long ii; |
| }; |
| |
| public: |
| MemRegionRef() = default; |
| MemRegionRef(llvm::BumpPtrAllocator *A) : Allocator(A) {} |
| |
| void *allocate(size_t Sz) { |
| return Allocator->Allocate(Sz, alignof(AlignmentType)); |
| } |
| |
| template <typename T> T *allocateT() { return Allocator->Allocate<T>(); } |
| |
| template <typename T> T *allocateT(size_t NumElems) { |
| return Allocator->Allocate<T>(NumElems); |
| } |
| |
| private: |
| llvm::BumpPtrAllocator *Allocator = nullptr; |
| }; |
| |
| } // namespace til |
| } // namespace threadSafety |
| |
| } // namespace clang |
| |
| inline void *operator new(size_t Sz, |
| clang::threadSafety::til::MemRegionRef &R) { |
| return R.allocate(Sz); |
| } |
| |
| namespace clang { |
| namespace threadSafety { |
| |
| std::string getSourceLiteralString(const Expr *CE); |
| |
| namespace til { |
| |
| // A simple fixed size array class that does not manage its own memory, |
| // suitable for use with bump pointer allocation. |
| template <class T> class SimpleArray { |
| public: |
| SimpleArray() = default; |
| SimpleArray(T *Dat, size_t Cp, size_t Sz = 0) |
| : Data(Dat), Size(Sz), Capacity(Cp) {} |
| SimpleArray(MemRegionRef A, size_t Cp) |
| : Data(Cp == 0 ? nullptr : A.allocateT<T>(Cp)), Capacity(Cp) {} |
| SimpleArray(const SimpleArray<T> &A) = delete; |
| |
| SimpleArray(SimpleArray<T> &&A) |
| : Data(A.Data), Size(A.Size), Capacity(A.Capacity) { |
| A.Data = nullptr; |
| A.Size = 0; |
| A.Capacity = 0; |
| } |
| |
| SimpleArray &operator=(SimpleArray &&RHS) { |
| if (this != &RHS) { |
| Data = RHS.Data; |
| Size = RHS.Size; |
| Capacity = RHS.Capacity; |
| |
| RHS.Data = nullptr; |
| RHS.Size = RHS.Capacity = 0; |
| } |
| return *this; |
| } |
| |
| // Reserve space for at least Ncp items, reallocating if necessary. |
| void reserve(size_t Ncp, MemRegionRef A) { |
| if (Ncp <= Capacity) |
| return; |
| T *Odata = Data; |
| Data = A.allocateT<T>(Ncp); |
| Capacity = Ncp; |
| memcpy(Data, Odata, sizeof(T) * Size); |
| } |
| |
| // Reserve space for at least N more items. |
| void reserveCheck(size_t N, MemRegionRef A) { |
| if (Capacity == 0) |
| reserve(u_max(InitialCapacity, N), A); |
| else if (Size + N < Capacity) |
| reserve(u_max(Size + N, Capacity * 2), A); |
| } |
| |
| using iterator = T *; |
| using const_iterator = const T *; |
| using reverse_iterator = std::reverse_iterator<iterator>; |
| using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
| |
| size_t size() const { return Size; } |
| size_t capacity() const { return Capacity; } |
| |
| T &operator[](unsigned i) { |
| assert(i < Size && "Array index out of bounds."); |
| return Data[i]; |
| } |
| |
| const T &operator[](unsigned i) const { |
| assert(i < Size && "Array index out of bounds."); |
| return Data[i]; |
| } |
| |
| T &back() { |
| assert(Size && "No elements in the array."); |
| return Data[Size - 1]; |
| } |
| |
| const T &back() const { |
| assert(Size && "No elements in the array."); |
| return Data[Size - 1]; |
| } |
| |
| iterator begin() { return Data; } |
| iterator end() { return Data + Size; } |
| |
| const_iterator begin() const { return Data; } |
| const_iterator end() const { return Data + Size; } |
| |
| const_iterator cbegin() const { return Data; } |
| const_iterator cend() const { return Data + Size; } |
| |
| reverse_iterator rbegin() { return reverse_iterator(end()); } |
| reverse_iterator rend() { return reverse_iterator(begin()); } |
| |
| const_reverse_iterator rbegin() const { |
| return const_reverse_iterator(end()); |
| } |
| |
| const_reverse_iterator rend() const { |
| return const_reverse_iterator(begin()); |
| } |
| |
| void push_back(const T &Elem) { |
| assert(Size < Capacity); |
| Data[Size++] = Elem; |
| } |
| |
| // drop last n elements from array |
| void drop(unsigned n = 0) { |
| assert(Size > n); |
| Size -= n; |
| } |
| |
| void setValues(unsigned Sz, const T& C) { |
| assert(Sz <= Capacity); |
| Size = Sz; |
| for (unsigned i = 0; i < Sz; ++i) { |
| Data[i] = C; |
| } |
| } |
| |
| template <class Iter> unsigned append(Iter I, Iter E) { |
| size_t Osz = Size; |
| size_t J = Osz; |
| for (; J < Capacity && I != E; ++J, ++I) |
| Data[J] = *I; |
| Size = J; |
| return J - Osz; |
| } |
| |
| llvm::iterator_range<reverse_iterator> reverse() { |
| return llvm::make_range(rbegin(), rend()); |
| } |
| |
| llvm::iterator_range<const_reverse_iterator> reverse() const { |
| return llvm::make_range(rbegin(), rend()); |
| } |
| |
| private: |
| // std::max is annoying here, because it requires a reference, |
| // thus forcing InitialCapacity to be initialized outside the .h file. |
| size_t u_max(size_t i, size_t j) { return (i < j) ? j : i; } |
| |
| static const size_t InitialCapacity = 4; |
| |
| T *Data = nullptr; |
| size_t Size = 0; |
| size_t Capacity = 0; |
| }; |
| |
| } // namespace til |
| |
| // A copy on write vector. |
| // The vector can be in one of three states: |
| // * invalid -- no operations are permitted. |
| // * read-only -- read operations are permitted. |
| // * writable -- read and write operations are permitted. |
| // The init(), destroy(), and makeWritable() methods will change state. |
| template<typename T> |
| class CopyOnWriteVector { |
| class VectorData { |
| public: |
| unsigned NumRefs = 1; |
| std::vector<T> Vect; |
| |
| VectorData() = default; |
| VectorData(const VectorData &VD) : Vect(VD.Vect) {} |
| }; |
| |
| public: |
| CopyOnWriteVector() = default; |
| CopyOnWriteVector(CopyOnWriteVector &&V) : Data(V.Data) { V.Data = nullptr; } |
| |
| CopyOnWriteVector &operator=(CopyOnWriteVector &&V) { |
| destroy(); |
| Data = V.Data; |
| V.Data = nullptr; |
| return *this; |
| } |
| |
| // No copy constructor or copy assignment. Use clone() with move assignment. |
| CopyOnWriteVector(const CopyOnWriteVector &) = delete; |
| CopyOnWriteVector &operator=(const CopyOnWriteVector &) = delete; |
| |
| ~CopyOnWriteVector() { destroy(); } |
| |
| // Returns true if this holds a valid vector. |
| bool valid() const { return Data; } |
| |
| // Returns true if this vector is writable. |
| bool writable() const { return Data && Data->NumRefs == 1; } |
| |
| // If this vector is not valid, initialize it to a valid vector. |
| void init() { |
| if (!Data) { |
| Data = new VectorData(); |
| } |
| } |
| |
| // Destroy this vector; thus making it invalid. |
| void destroy() { |
| if (!Data) |
| return; |
| if (Data->NumRefs <= 1) |
| delete Data; |
| else |
| --Data->NumRefs; |
| Data = nullptr; |
| } |
| |
| // Make this vector writable, creating a copy if needed. |
| void makeWritable() { |
| if (!Data) { |
| Data = new VectorData(); |
| return; |
| } |
| if (Data->NumRefs == 1) |
| return; // already writeable. |
| --Data->NumRefs; |
| Data = new VectorData(*Data); |
| } |
| |
| // Create a lazy copy of this vector. |
| CopyOnWriteVector clone() { return CopyOnWriteVector(Data); } |
| |
| using const_iterator = typename std::vector<T>::const_iterator; |
| |
| const std::vector<T> &elements() const { return Data->Vect; } |
| |
| const_iterator begin() const { return elements().cbegin(); } |
| const_iterator end() const { return elements().cend(); } |
| |
| const T& operator[](unsigned i) const { return elements()[i]; } |
| |
| unsigned size() const { return Data ? elements().size() : 0; } |
| |
| // Return true if V and this vector refer to the same data. |
| bool sameAs(const CopyOnWriteVector &V) const { return Data == V.Data; } |
| |
| // Clear vector. The vector must be writable. |
| void clear() { |
| assert(writable() && "Vector is not writable!"); |
| Data->Vect.clear(); |
| } |
| |
| // Push a new element onto the end. The vector must be writable. |
| void push_back(const T &Elem) { |
| assert(writable() && "Vector is not writable!"); |
| Data->Vect.push_back(Elem); |
| } |
| |
| // Gets a mutable reference to the element at index(i). |
| // The vector must be writable. |
| T& elem(unsigned i) { |
| assert(writable() && "Vector is not writable!"); |
| return Data->Vect[i]; |
| } |
| |
| // Drops elements from the back until the vector has size i. |
| void downsize(unsigned i) { |
| assert(writable() && "Vector is not writable!"); |
| Data->Vect.erase(Data->Vect.begin() + i, Data->Vect.end()); |
| } |
| |
| private: |
| CopyOnWriteVector(VectorData *D) : Data(D) { |
| if (!Data) |
| return; |
| ++Data->NumRefs; |
| } |
| |
| VectorData *Data = nullptr; |
| }; |
| |
| inline std::ostream& operator<<(std::ostream& ss, const StringRef str) { |
| return ss.write(str.data(), str.size()); |
| } |
| |
| } // namespace threadSafety |
| } // namespace clang |
| |
| #endif // LLVM_CLANG_THREAD_SAFETY_UTIL_H |