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
26namespace clang {
27namespace 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`.
33class Value {
34public:
35  enum class Kind {
36    Integer,
37    Pointer,
38    Record,
39
40    // TODO: Top values should not be need to be type-specific.
41    TopBool,
42    AtomicBool,
43    FormulaBool,
44  };
45
46  explicit Value(Kind ValKind) : ValKind(ValKind) {}
47
48  // Non-copyable because addresses of values are used as their identities
49  // throughout framework and user code. The framework is responsible for
50  // construction and destruction of values.
51  Value(const Value &) = delete;
52  Value &operator=(const Value &) = delete;
53
54  virtual ~Value() = default;
55
56  Kind getKind() const { return ValKind; }
57
58  /// Returns the value of the synthetic property with the given `Name` or null
59  /// if the property isn't assigned a value.
60  Value *getProperty(llvm::StringRef Name) const {
61    return Properties.lookup(Name);
62  }
63
64  /// Assigns `Val` as the value of the synthetic property with the given
65  /// `Name`.
66  ///
67  /// Properties may not be set on `RecordValue`s; use synthetic fields instead
68  /// (for details, see documentation for `RecordStorageLocation`).
69  void setProperty(llvm::StringRef Name, Value &Val) {
70    assert(getKind() != Kind::Record);
71    Properties.insert_or_assign(Name, &Val);
72  }
73
74  llvm::iterator_range<llvm::StringMap<Value *>::const_iterator>
75  properties() const {
76    return {Properties.begin(), Properties.end()};
77  }
78
79private:
80  Kind ValKind;
81  llvm::StringMap<Value *> Properties;
82};
83
84/// An equivalence relation for values. It obeys reflexivity, symmetry and
85/// transitivity. It does *not* include comparison of `Properties`.
86///
87/// Computes equivalence for these subclasses:
88/// * PointerValue -- pointee locations are equal. Does not compute deep
89///   equality of `Value` at said location.
90/// * TopBoolValue -- both are `TopBoolValue`s.
91///
92/// Otherwise, falls back to pointer equality.
93bool areEquivalentValues(const Value &Val1, const Value &Val2);
94
95/// Models a boolean.
96class BoolValue : public Value {
97  const Formula *F;
98
99public:
100  explicit BoolValue(Kind ValueKind, const Formula &F)
101      : Value(ValueKind), F(&F) {}
102
103  static bool classof(const Value *Val) {
104    return Val->getKind() == Kind::TopBool ||
105           Val->getKind() == Kind::AtomicBool ||
106           Val->getKind() == Kind::FormulaBool;
107  }
108
109  const Formula &formula() const { return *F; }
110};
111
112/// A TopBoolValue represents a boolean that is explicitly unconstrained.
113///
114/// This is equivalent to an AtomicBoolValue that does not appear anywhere
115/// else in a system of formula.
116/// Knowing the value is unconstrained is useful when e.g. reasoning about
117/// convergence.
118class TopBoolValue final : public BoolValue {
119public:
120  TopBoolValue(const Formula &F) : BoolValue(Kind::TopBool, F) {
121    assert(F.kind() == Formula::AtomRef);
122  }
123
124  static bool classof(const Value *Val) {
125    return Val->getKind() == Kind::TopBool;
126  }
127
128  Atom getAtom() const { return formula().getAtom(); }
129};
130
131/// Models an atomic boolean.
132///
133/// FIXME: Merge this class into FormulaBoolValue.
134///        When we want to specify atom identity, use Atom.
135class AtomicBoolValue final : public BoolValue {
136public:
137  explicit AtomicBoolValue(const Formula &F) : BoolValue(Kind::AtomicBool, F) {
138    assert(F.kind() == Formula::AtomRef);
139  }
140
141  static bool classof(const Value *Val) {
142    return Val->getKind() == Kind::AtomicBool;
143  }
144
145  Atom getAtom() const { return formula().getAtom(); }
146};
147
148/// Models a compound boolean formula.
149class FormulaBoolValue final : public BoolValue {
150public:
151  explicit FormulaBoolValue(const Formula &F)
152      : BoolValue(Kind::FormulaBool, F) {
153    assert(F.kind() != Formula::AtomRef && "For now, use AtomicBoolValue");
154  }
155
156  static bool classof(const Value *Val) {
157    return Val->getKind() == Kind::FormulaBool;
158  }
159};
160
161/// Models an integer.
162class IntegerValue : public Value {
163public:
164  explicit IntegerValue() : Value(Kind::Integer) {}
165
166  static bool classof(const Value *Val) {
167    return Val->getKind() == Kind::Integer;
168  }
169};
170
171/// Models a symbolic pointer. Specifically, any value of type `T*`.
172class PointerValue final : public Value {
173public:
174  explicit PointerValue(StorageLocation &PointeeLoc)
175      : Value(Kind::Pointer), PointeeLoc(PointeeLoc) {}
176
177  static bool classof(const Value *Val) {
178    return Val->getKind() == Kind::Pointer;
179  }
180
181  StorageLocation &getPointeeLoc() const { return PointeeLoc; }
182
183private:
184  StorageLocation &PointeeLoc;
185};
186
187/// Models a value of `struct` or `class` type.
188/// In C++, prvalues of class type serve only a limited purpose: They can only
189/// be used to initialize a result object. It is not possible to access member
190/// variables or call member functions on a prvalue of class type.
191/// Correspondingly, `RecordValue` also serves only a limited purpose: It
192/// conveys a prvalue of class type from the place where the object is
193/// constructed to the result object that it initializes.
194///
195/// When creating a prvalue of class type, we already need a storage location
196/// for `this`, even though prvalues are otherwise not associated with storage
197/// locations. `RecordValue` is therefore essentially a wrapper for a storage
198/// location, which is then used to set the storage location for the result
199/// object when we process the AST node for that result object.
200///
201/// For example:
202///    MyStruct S = MyStruct(3);
203///
204/// In this example, `MyStruct(3) is a prvalue, which is modeled as a
205/// `RecordValue` that wraps a `RecordStorageLocation`. This
206/// `RecordStorageLocation` is then used as the storage location for `S`.
207///
208/// Over time, we may eliminate `RecordValue` entirely. See also the discussion
209/// here: https://reviews.llvm.org/D155204#inline-1503204
210class RecordValue final : public Value {
211public:
212  explicit RecordValue(RecordStorageLocation &Loc)
213      : Value(Kind::Record), Loc(Loc) {}
214
215  static bool classof(const Value *Val) {
216    return Val->getKind() == Kind::Record;
217  }
218
219  /// Returns the storage location that this `RecordValue` is associated with.
220  RecordStorageLocation &getLoc() const { return Loc; }
221
222private:
223  RecordStorageLocation &Loc;
224};
225
226raw_ostream &operator<<(raw_ostream &OS, const Value &Val);
227
228} // namespace dataflow
229} // namespace clang
230
231#endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_VALUE_H
232