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, Formula::Literal, {}, 1)),
25        False(Formula::create(Alloc, Formula::Literal, {}, 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>(makeBoolValue(makeAtomRef(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>(makeAtomRef(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