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
17namespace clang::dataflow {
18
19/// The Arena owns the objects that model data within an analysis.
20/// For example, `Value`, `StorageLocation`, `Atom`, and `Formula`.
21class Arena {
22public:
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
126private:
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