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: Arena()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 &> create(Args &&...args)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 &> create(Args &&...args)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. makeAtomValue()71 AtomicBoolValue &makeAtomValue() { 72 return cast<AtomicBoolValue>(makeBoolValue(makeAtomRef(makeAtom()))); 73 } 74 75 /// Creates a fresh Top boolean value. makeTopValue()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. makeLiteral(bool Value)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. makeAtom()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. makeFlowConditionToken()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