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