Yi Kong | 8328301 | 2023-12-13 12:57:00 +0900 | [diff] [blame^] | 1 | //===-- Arena.h -------------------------------*- C++ -------------------*-===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__ARENA_H |
| 9 | #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__ARENA_H |
| 10 | |
| 11 | #include "clang/Analysis/FlowSensitive/Formula.h" |
| 12 | #include "clang/Analysis/FlowSensitive/StorageLocation.h" |
| 13 | #include "clang/Analysis/FlowSensitive/Value.h" |
| 14 | #include <vector> |
| 15 | |
| 16 | namespace clang::dataflow { |
| 17 | |
| 18 | /// The Arena owns the objects that model data within an analysis. |
| 19 | /// For example, `Value`, `StorageLocation`, `Atom`, and `Formula`. |
| 20 | class Arena { |
| 21 | public: |
| 22 | Arena() : True(makeAtom()), False(makeAtom()) {} |
| 23 | Arena(const Arena &) = delete; |
| 24 | Arena &operator=(const Arena &) = delete; |
| 25 | |
| 26 | /// Creates a `T` (some subclass of `StorageLocation`), forwarding `args` to |
| 27 | /// the constructor, and returns a reference to it. |
| 28 | /// |
| 29 | /// The `DataflowAnalysisContext` takes ownership of the created object. The |
| 30 | /// object will be destroyed when the `DataflowAnalysisContext` is destroyed. |
| 31 | template <typename T, typename... Args> |
| 32 | std::enable_if_t<std::is_base_of<StorageLocation, T>::value, T &> |
| 33 | create(Args &&...args) { |
| 34 | // Note: If allocation of individual `StorageLocation`s turns out to be |
| 35 | // costly, consider creating specializations of `create<T>` for commonly |
| 36 | // used `StorageLocation` subclasses and make them use a `BumpPtrAllocator`. |
| 37 | return *cast<T>( |
| 38 | Locs.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)) |
| 39 | .get()); |
| 40 | } |
| 41 | |
| 42 | /// Creates a `T` (some subclass of `Value`), forwarding `args` to the |
| 43 | /// constructor, and returns a reference to it. |
| 44 | /// |
| 45 | /// The `DataflowAnalysisContext` takes ownership of the created object. The |
| 46 | /// object will be destroyed when the `DataflowAnalysisContext` is destroyed. |
| 47 | template <typename T, typename... Args> |
| 48 | std::enable_if_t<std::is_base_of<Value, T>::value, T &> |
| 49 | create(Args &&...args) { |
| 50 | // Note: If allocation of individual `Value`s turns out to be costly, |
| 51 | // consider creating specializations of `create<T>` for commonly used |
| 52 | // `Value` subclasses and make them use a `BumpPtrAllocator`. |
| 53 | return *cast<T>( |
| 54 | Vals.emplace_back(std::make_unique<T>(std::forward<Args>(args)...)) |
| 55 | .get()); |
| 56 | } |
| 57 | |
| 58 | /// Creates a BoolValue wrapping a particular formula. |
| 59 | /// |
| 60 | /// Passing in the same formula will result in the same BoolValue. |
| 61 | /// FIXME: Interning BoolValues but not other Values is inconsistent. |
| 62 | /// Decide whether we want Value interning or not. |
| 63 | BoolValue &makeBoolValue(const Formula &); |
| 64 | |
| 65 | /// Creates a fresh atom and wraps in in an AtomicBoolValue. |
| 66 | /// FIXME: For now, identical-address AtomicBoolValue <=> identical atom. |
| 67 | /// Stop relying on pointer identity and remove this guarantee. |
| 68 | AtomicBoolValue &makeAtomValue() { |
| 69 | return cast<AtomicBoolValue>(makeBoolValue(makeAtomRef(makeAtom()))); |
| 70 | } |
| 71 | |
| 72 | /// Creates a fresh Top boolean value. |
| 73 | TopBoolValue &makeTopValue() { |
| 74 | // No need for deduplicating: there's no way to create aliasing Tops. |
| 75 | return create<TopBoolValue>(makeAtomRef(makeAtom())); |
| 76 | } |
| 77 | |
| 78 | /// Returns a symbolic integer value that models an integer literal equal to |
| 79 | /// `Value`. These literals are the same every time. |
| 80 | /// Integer literals are not typed; the type is determined by the `Expr` that |
| 81 | /// an integer literal is associated with. |
| 82 | IntegerValue &makeIntLiteral(llvm::APInt Value); |
| 83 | |
| 84 | // Factories for boolean formulas. |
| 85 | // Formulas are interned: passing the same arguments return the same result. |
| 86 | // For commutative operations like And/Or, interning ignores order. |
| 87 | // Simplifications are applied: makeOr(X, X) => X, etc. |
| 88 | |
| 89 | /// Returns a formula for the conjunction of `LHS` and `RHS`. |
| 90 | const Formula &makeAnd(const Formula &LHS, const Formula &RHS); |
| 91 | |
| 92 | /// Returns a formula for the disjunction of `LHS` and `RHS`. |
| 93 | const Formula &makeOr(const Formula &LHS, const Formula &RHS); |
| 94 | |
| 95 | /// Returns a formula for the negation of `Val`. |
| 96 | const Formula &makeNot(const Formula &Val); |
| 97 | |
| 98 | /// Returns a formula for `LHS => RHS`. |
| 99 | const Formula &makeImplies(const Formula &LHS, const Formula &RHS); |
| 100 | |
| 101 | /// Returns a formula for `LHS <=> RHS`. |
| 102 | const Formula &makeEquals(const Formula &LHS, const Formula &RHS); |
| 103 | |
| 104 | /// Returns a formula for the variable A. |
| 105 | const Formula &makeAtomRef(Atom A); |
| 106 | |
| 107 | /// Returns a formula for a literal true/false. |
| 108 | const Formula &makeLiteral(bool Value) { |
| 109 | return makeAtomRef(Value ? True : False); |
| 110 | } |
| 111 | |
| 112 | /// Returns a new atomic boolean variable, distinct from any other. |
| 113 | Atom makeAtom() { return static_cast<Atom>(NextAtom++); }; |
| 114 | |
| 115 | /// Creates a fresh flow condition and returns a token that identifies it. The |
| 116 | /// token can be used to perform various operations on the flow condition such |
| 117 | /// as adding constraints to it, forking it, joining it with another flow |
| 118 | /// condition, or checking implications. |
| 119 | Atom makeFlowConditionToken() { return makeAtom(); } |
| 120 | |
| 121 | private: |
| 122 | llvm::BumpPtrAllocator Alloc; |
| 123 | |
| 124 | // Storage for the state of a program. |
| 125 | std::vector<std::unique_ptr<StorageLocation>> Locs; |
| 126 | std::vector<std::unique_ptr<Value>> Vals; |
| 127 | |
| 128 | // Indices that are used to avoid recreating the same integer literals and |
| 129 | // composite boolean values. |
| 130 | llvm::DenseMap<llvm::APInt, IntegerValue *> IntegerLiterals; |
| 131 | using FormulaPair = std::pair<const Formula *, const Formula *>; |
| 132 | llvm::DenseMap<FormulaPair, const Formula *> Ands; |
| 133 | llvm::DenseMap<FormulaPair, const Formula *> Ors; |
| 134 | llvm::DenseMap<const Formula *, const Formula *> Nots; |
| 135 | llvm::DenseMap<FormulaPair, const Formula *> Implies; |
| 136 | llvm::DenseMap<FormulaPair, const Formula *> Equals; |
| 137 | llvm::DenseMap<Atom, const Formula *> AtomRefs; |
| 138 | |
| 139 | llvm::DenseMap<const Formula *, BoolValue *> FormulaValues; |
| 140 | unsigned NextAtom = 0; |
| 141 | |
| 142 | Atom True, False; |
| 143 | }; |
| 144 | |
| 145 | } // namespace clang::dataflow |
| 146 | |
| 147 | #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE__ARENA_H |