xref: /freebsd/contrib/llvm-project/clang/include/clang/Analysis/FlowSensitive/Value.h (revision 0fca6ea1d4eea4c934cfff25ac9ee8ad6fe95583)
1 //===-- Value.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 //
9 // This file defines classes for values computed by abstract interpretation
10 // during dataflow analysis.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
15 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
16 
17 #include "clang/AST/Decl.h"
18 #include "clang/Analysis/FlowSensitive/Formula.h"
19 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/StringMap.h"
22 #include "llvm/ADT/StringRef.h"
23 #include <cassert>
24 #include <utility>
25 
26 namespace clang {
27 namespace dataflow {
28 
29 /// Base class for all values computed by abstract interpretation.
30 ///
31 /// Don't use `Value` instances by value. All `Value` instances are allocated
32 /// and owned by `DataflowAnalysisContext`.
33 class Value {
34 public:
35   enum class Kind {
36     Integer,
37     Pointer,
38 
39     // TODO: Top values should not be need to be type-specific.
40     TopBool,
41     AtomicBool,
42     FormulaBool,
43   };
44 
Value(Kind ValKind)45   explicit Value(Kind ValKind) : ValKind(ValKind) {}
46 
47   // Non-copyable because addresses of values are used as their identities
48   // throughout framework and user code. The framework is responsible for
49   // construction and destruction of values.
50   Value(const Value &) = delete;
51   Value &operator=(const Value &) = delete;
52 
53   virtual ~Value() = default;
54 
getKind()55   Kind getKind() const { return ValKind; }
56 
57   /// Returns the value of the synthetic property with the given `Name` or null
58   /// if the property isn't assigned a value.
getProperty(llvm::StringRef Name)59   Value *getProperty(llvm::StringRef Name) const {
60     return Properties.lookup(Name);
61   }
62 
63   /// Assigns `Val` as the value of the synthetic property with the given
64   /// `Name`.
65   ///
66   /// Properties may not be set on `RecordValue`s; use synthetic fields instead
67   /// (for details, see documentation for `RecordStorageLocation`).
setProperty(llvm::StringRef Name,Value & Val)68   void setProperty(llvm::StringRef Name, Value &Val) {
69     Properties.insert_or_assign(Name, &Val);
70   }
71 
72   llvm::iterator_range<llvm::StringMap<Value *>::const_iterator>
properties()73   properties() const {
74     return {Properties.begin(), Properties.end()};
75   }
76 
77 private:
78   Kind ValKind;
79   llvm::StringMap<Value *> Properties;
80 };
81 
82 /// An equivalence relation for values. It obeys reflexivity, symmetry and
83 /// transitivity. It does *not* include comparison of `Properties`.
84 ///
85 /// Computes equivalence for these subclasses:
86 /// * PointerValue -- pointee locations are equal. Does not compute deep
87 ///   equality of `Value` at said location.
88 /// * TopBoolValue -- both are `TopBoolValue`s.
89 ///
90 /// Otherwise, falls back to pointer equality.
91 bool areEquivalentValues(const Value &Val1, const Value &Val2);
92 
93 /// Models a boolean.
94 class BoolValue : public Value {
95   const Formula *F;
96 
97 public:
BoolValue(Kind ValueKind,const Formula & F)98   explicit BoolValue(Kind ValueKind, const Formula &F)
99       : Value(ValueKind), F(&F) {}
100 
classof(const Value * Val)101   static bool classof(const Value *Val) {
102     return Val->getKind() == Kind::TopBool ||
103            Val->getKind() == Kind::AtomicBool ||
104            Val->getKind() == Kind::FormulaBool;
105   }
106 
formula()107   const Formula &formula() const { return *F; }
108 };
109 
110 /// A TopBoolValue represents a boolean that is explicitly unconstrained.
111 ///
112 /// This is equivalent to an AtomicBoolValue that does not appear anywhere
113 /// else in a system of formula.
114 /// Knowing the value is unconstrained is useful when e.g. reasoning about
115 /// convergence.
116 class TopBoolValue final : public BoolValue {
117 public:
TopBoolValue(const Formula & F)118   TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) {
119     assert(F.kind() == Formula::AtomRef);
120   }
121 
classof(const Value * Val)122   static bool classof(const Value *Val) {
123     return Val->getKind() == Kind::TopBool;
124   }
125 
getAtom()126   Atom getAtom() const { return formula().getAtom(); }
127 };
128 
129 /// Models an atomic boolean.
130 ///
131 /// FIXME: Merge this class into FormulaBoolValue.
132 ///        When we want to specify atom identity, use Atom.
133 class AtomicBoolValue final : public BoolValue {
134 public:
AtomicBoolValue(const Formula & F)135   explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) {
136     assert(F.kind() == Formula::AtomRef);
137   }
138 
classof(const Value * Val)139   static bool classof(const Value *Val) {
140     return Val->getKind() == Kind::AtomicBool;
141   }
142 
getAtom()143   Atom getAtom() const { return formula().getAtom(); }
144 };
145 
146 /// Models a compound boolean formula.
147 class FormulaBoolValue final : public BoolValue {
148 public:
FormulaBoolValue(const Formula & F)149   explicit FormulaBoolValue(const Formula &F)
150       : BoolValue(Kind::FormulaBool, F) {
151     assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue");
152   }
153 
classof(const Value * Val)154   static bool classof(const Value *Val) {
155     return Val->getKind() == Kind::FormulaBool;
156   }
157 };
158 
159 /// Models an integer.
160 class IntegerValue : public Value {
161 public:
IntegerValue()162   explicit IntegerValue() : Value(Kind::Integer) {}
163 
classof(const Value * Val)164   static bool classof(const Value *Val) {
165     return Val->getKind() == Kind::Integer;
166   }
167 };
168 
169 /// Models a symbolic pointer. Specifically, any value of type `T*`.
170 class PointerValue final : public Value {
171 public:
PointerValue(StorageLocation & PointeeLoc)172   explicit PointerValue(StorageLocation &PointeeLoc)
173       : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
174 
classof(const Value * Val)175   static bool classof(const Value *Val) {
176     return Val->getKind() == Kind::Pointer;
177   }
178 
getPointeeLoc()179   StorageLocation &getPointeeLoc() const { return PointeeLoc; }
180 
181 private:
182   StorageLocation &PointeeLoc;
183 };
184 
185 raw_ostream &operator<<(raw_ostream &OS, const Value &Val);
186 
187 } // namespace dataflow
188 } // namespace clang
189 
190 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
191