clang  15.0.0git
DataflowAnalysisContext.h
Go to the documentation of this file.
1 //===-- DataflowAnalysisContext.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 a DataflowAnalysisContext class that owns objects that
10 // encompass the state of a program and stores context that is used during
11 // dataflow analysis.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
16 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
17 
18 #include "clang/AST/Decl.h"
19 #include "clang/AST/Expr.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/DenseSet.h"
25 #include <cassert>
26 #include <memory>
27 #include <type_traits>
28 #include <utility>
29 #include <vector>
30 
31 namespace clang {
32 namespace dataflow {
33 
34 /// Skip past nodes that the CFG does not emit. These nodes are invisible to
35 /// flow-sensitive analysis, and should be ignored as they will effectively not
36 /// exist.
37 ///
38 /// * `ParenExpr` - The CFG takes the operator precedence into account, but
39 /// otherwise omits the node afterwards.
40 ///
41 /// * `ExprWithCleanups` - The CFG will generate the appropriate calls to
42 /// destructors and then omit the node.
43 ///
44 const Expr &ignoreCFGOmittedNodes(const Expr &E);
45 const Stmt &ignoreCFGOmittedNodes(const Stmt &S);
46 
47 /// Owns objects that encompass the state of a program and stores context that
48 /// is used during dataflow analysis.
50 public:
51  /// Constructs a dataflow analysis context.
52  ///
53  /// Requirements:
54  ///
55  /// `S` must not be null.
56  DataflowAnalysisContext(std::unique_ptr<Solver> S)
57  : S(std::move(S)), TrueVal(createAtomicBoolValue()),
58  FalseVal(createAtomicBoolValue()) {
59  assert(this->S != nullptr);
60  }
61 
62  /// Takes ownership of `Loc` and returns a reference to it.
63  ///
64  /// Requirements:
65  ///
66  /// `Loc` must not be null.
67  template <typename T>
68  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
69  takeOwnership(std::unique_ptr<T> Loc) {
70  assert(Loc != nullptr);
71  Locs.push_back(std::move(Loc));
72  return *cast<T>(Locs.back().get());
73  }
74 
75  /// Takes ownership of `Val` and returns a reference to it.
76  ///
77  /// Requirements:
78  ///
79  /// `Val` must not be null.
80  template <typename T>
81  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
82  takeOwnership(std::unique_ptr<T> Val) {
83  assert(Val != nullptr);
84  Vals.push_back(std::move(Val));
85  return *cast<T>(Vals.back().get());
86  }
87 
88  /// Assigns `Loc` as the storage location of `D`.
89  ///
90  /// Requirements:
91  ///
92  /// `D` must not be assigned a storage location.
94  assert(DeclToLoc.find(&D) == DeclToLoc.end());
95  DeclToLoc[&D] = &Loc;
96  }
97 
98  /// Returns the storage location assigned to `D` or null if `D` has no
99  /// assigned storage location.
101  auto It = DeclToLoc.find(&D);
102  return It == DeclToLoc.end() ? nullptr : It->second;
103  }
104 
105  /// Assigns `Loc` as the storage location of `E`.
106  ///
107  /// Requirements:
108  ///
109  /// `E` must not be assigned a storage location.
110  void setStorageLocation(const Expr &E, StorageLocation &Loc) {
111  const Expr &CanonE = ignoreCFGOmittedNodes(E);
112  assert(ExprToLoc.find(&CanonE) == ExprToLoc.end());
113  ExprToLoc[&CanonE] = &Loc;
114  }
115 
116  /// Returns the storage location assigned to `E` or null if `E` has no
117  /// assigned storage location.
119  auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
120  return It == ExprToLoc.end() ? nullptr : It->second;
121  }
122 
123  /// Assigns `Loc` as the storage location of the `this` pointee.
124  ///
125  /// Requirements:
126  ///
127  /// The `this` pointee must not be assigned a storage location.
129  assert(ThisPointeeLoc == nullptr);
130  ThisPointeeLoc = &Loc;
131  }
132 
133  /// Returns the storage location assigned to the `this` pointee or null if the
134  /// `this` pointee has no assigned storage location.
136  return ThisPointeeLoc;
137  }
138 
139  /// Returns a symbolic boolean value that models a boolean literal equal to
140  /// `Value`.
142  return Value ? TrueVal : FalseVal;
143  }
144 
145  /// Creates an atomic boolean value.
147  return takeOwnership(std::make_unique<AtomicBoolValue>());
148  }
149 
150  /// Returns a boolean value that represents the conjunction of `LHS` and
151  /// `RHS`. Subsequent calls with the same arguments, regardless of their
152  /// order, will return the same result. If the given boolean values represent
153  /// the same value, the result will be the value itself.
155 
156  /// Returns a boolean value that represents the disjunction of `LHS` and
157  /// `RHS`. Subsequent calls with the same arguments, regardless of their
158  /// order, will return the same result. If the given boolean values represent
159  /// the same value, the result will be the value itself.
161 
162  /// Returns a boolean value that represents the negation of `Val`. Subsequent
163  /// calls with the same argument will return the same result.
165 
166  /// Creates a fresh flow condition and returns a token that identifies it. The
167  /// token can be used to perform various operations on the flow condition such
168  /// as adding constraints to it, forking it, joining it with another flow
169  /// condition, or checking implications.
171 
172  /// Adds `Constraint` to the flow condition identified by `Token`.
174  BoolValue &Constraint);
175 
176  /// Creates a new flow condition with the same constraints as the flow
177  /// condition identified by `Token` and returns its token.
179 
180  /// Creates a new flow condition that represents the disjunction of the flow
181  /// conditions identified by `FirstToken` and `SecondToken`, and returns its
182  /// token.
184  AtomicBoolValue &SecondToken);
185 
186  /// Returns true if and only if the constraints of the flow condition
187  /// identified by `Token` imply that `Val` is true.
189 
190  /// Returns true if and only if the constraints of the flow condition
191  /// identified by `Token` are always true.
193 
194 private:
195  /// Adds all constraints of the flow condition identified by `Token` and all
196  /// of its transitive dependencies to `Constraints`. `VisitedTokens` is used
197  /// to track tokens of flow conditions that were already visited by recursive
198  /// calls.
199  void addTransitiveFlowConditionConstraints(
201  llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) const;
202 
203  std::unique_ptr<Solver> S;
204 
205  // Storage for the state of a program.
206  std::vector<std::unique_ptr<StorageLocation>> Locs;
207  std::vector<std::unique_ptr<Value>> Vals;
208 
209  // Maps from program declarations and statements to storage locations that are
210  // assigned to them. These assignments are global (aggregated across all basic
211  // blocks) and are used to produce stable storage locations when the same
212  // basic blocks are evaluated multiple times. The storage locations that are
213  // in scope for a particular basic block are stored in `Environment`.
214  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
215  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
216 
217  StorageLocation *ThisPointeeLoc = nullptr;
218 
219  AtomicBoolValue &TrueVal;
220  AtomicBoolValue &FalseVal;
221 
222  // Indices that are used to avoid recreating the same composite boolean
223  // values.
224  llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, ConjunctionValue *>
225  ConjunctionVals;
226  llvm::DenseMap<std::pair<BoolValue *, BoolValue *>, DisjunctionValue *>
227  DisjunctionVals;
228  llvm::DenseMap<BoolValue *, NegationValue *> NegationVals;
229 
230  // Flow conditions are tracked symbolically: each unique flow condition is
231  // associated with a fresh symbolic variable (token), bound to the clause that
232  // defines the flow condition. Conceptually, each binding corresponds to an
233  // "iff" of the form `FC <=> (C1 ^ C2 ^ ...)` where `FC` is a flow condition
234  // token (an atomic boolean) and `Ci`s are the set of constraints in the flow
235  // flow condition clause. Internally, we do not record the formula directly as
236  // an "iff". Instead, a flow condition clause is encoded as conjuncts of the
237  // form `(FC v !C1 v !C2 v ...) ^ (C1 v !FC) ^ (C2 v !FC) ^ ...`. The first
238  // conjuct is stored in the `FlowConditionFirstConjuncts` map and the set of
239  // remaining conjuncts are stored in the `FlowConditionRemainingConjuncts`
240  // map, both keyed by the token of the flow condition.
241  //
242  // Flow conditions depend on other flow conditions if they are created using
243  // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
244  // dependencies is stored in the `FlowConditionDeps` map.
245  llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>>
246  FlowConditionDeps;
247  llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionFirstConjuncts;
248  llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<BoolValue *>>
249  FlowConditionRemainingConjuncts;
250 };
251 
252 } // namespace dataflow
253 } // namespace clang
254 
255 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
type
clang::dataflow::DataflowAnalysisContext::makeFlowConditionToken
AtomicBoolValue & makeFlowConditionToken()
Creates a fresh flow condition and returns a token that identifies it.
Definition: DataflowAnalysisContext.cpp:68
clang::dataflow::DataflowAnalysisContext::setStorageLocation
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D.
Definition: DataflowAnalysisContext.h:93
clang::dataflow::StorageLocation
Base class for elements of the local variable store and of the heap.
Definition: StorageLocation.h:28
clang::dataflow::DataflowAnalysisContext::flowConditionImplies
bool flowConditionImplies(AtomicBoolValue &Token, BoolValue &Val)
Returns true if and only if the constraints of the flow condition identified by Token imply that Val ...
Definition: DataflowAnalysisContext.cpp:103
clang::Token
Token - This structure provides full information about a lexed token.
Definition: Token.h:34
clang::dataflow::DataflowAnalysisContext::flowConditionIsTautology
bool flowConditionIsTautology(AtomicBoolValue &Token)
Returns true if and only if the constraints of the flow condition identified by Token are always true...
Definition: DataflowAnalysisContext.cpp:121
Decl.h
clang::dataflow::DisjunctionValue
Models a boolean disjunction.
Definition: Value.h:104
clang::dataflow::DataflowAnalysisContext
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
Definition: DataflowAnalysisContext.h:49
clang::dataflow::DataflowAnalysisContext::DataflowAnalysisContext
DataflowAnalysisContext(std::unique_ptr< Solver > S)
Constructs a dataflow analysis context.
Definition: DataflowAnalysisContext.h:56
clang::dataflow::DataflowAnalysisContext::getOrCreateNegationValue
BoolValue & getOrCreateNegationValue(BoolValue &Val)
Returns a boolean value that represents the negation of Val.
Definition: DataflowAnalysisContext.cpp:61
clang::dataflow::ConjunctionValue
Models a boolean conjunction.
Definition: Value.h:82
Solver.h
clang::dataflow::ignoreCFGOmittedNodes
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
Definition: DataflowAnalysisContext.cpp:162
clang::dataflow::DataflowAnalysisContext::setThisPointeeStorageLocation
void setThisPointeeStorageLocation(StorageLocation &Loc)
Assigns Loc as the storage location of the this pointee.
Definition: DataflowAnalysisContext.h:128
Expr.h
clang::dataflow::DataflowAnalysisContext::addFlowConditionConstraint
void addFlowConditionConstraint(AtomicBoolValue &Token, BoolValue &Constraint)
Adds Constraint to the flow condition identified by Token.
Definition: DataflowAnalysisContext.cpp:75
clang::dataflow::DataflowAnalysisContext::getOrCreateConjunctionValue
BoolValue & getOrCreateConjunctionValue(BoolValue &LHS, BoolValue &RHS)
Returns a boolean value that represents the conjunction of LHS and RHS.
Definition: DataflowAnalysisContext.cpp:34
llvm::DenseSet
Definition: Sema.h:77
clang::dataflow::AtomicBoolValue
Models an atomic boolean.
Definition: Value.h:69
clang::dataflow::DataflowAnalysisContext::getOrCreateDisjunctionValue
BoolValue & getOrCreateDisjunctionValue(BoolValue &LHS, BoolValue &RHS)
Returns a boolean value that represents the disjunction of LHS and RHS.
Definition: DataflowAnalysisContext.cpp:48
clang::dataflow::DataflowAnalysisContext::joinFlowConditions
AtomicBoolValue & joinFlowConditions(AtomicBoolValue &FirstToken, AtomicBoolValue &SecondToken)
Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...
Definition: DataflowAnalysisContext.cpp:93
clang::dataflow::BoolValue
Models a boolean.
Definition: Value.h:56
clang::dataflow::DataflowAnalysisContext::getStorageLocation
StorageLocation * getStorageLocation(const Expr &E) const
Returns the storage location assigned to E or null if E has no assigned storage location.
Definition: DataflowAnalysisContext.h:118
clang::ValueDecl
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:674
clang::dataflow::DataflowAnalysisContext::forkFlowCondition
AtomicBoolValue & forkFlowCondition(AtomicBoolValue &Token)
Creates a new flow condition with the same constraints as the flow condition identified by Token and ...
Definition: DataflowAnalysisContext.cpp:85
clang::dataflow::DataflowAnalysisContext::getBoolLiteralValue
AtomicBoolValue & getBoolLiteralValue(bool Value) const
Returns a symbolic boolean value that models a boolean literal equal to Value.
Definition: DataflowAnalysisContext.h:141
std
Definition: Format.h:4296
clang::dataflow::DataflowAnalysisContext::setStorageLocation
void setStorageLocation(const Expr &E, StorageLocation &Loc)
Assigns Loc as the storage location of E.
Definition: DataflowAnalysisContext.h:110
clang::dataflow::DataflowAnalysisContext::getStorageLocation
StorageLocation * getStorageLocation(const ValueDecl &D) const
Returns the storage location assigned to D or null if D has no assigned storage location.
Definition: DataflowAnalysisContext.h:100
clang
Definition: CalledOnceCheck.h:17
clang::dataflow::DataflowAnalysisContext::getThisPointeeStorageLocation
StorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee or null if the this pointee has no assigned...
Definition: DataflowAnalysisContext.h:135
clang::dataflow::DataflowAnalysisContext::takeOwnership
std::enable_if< std::is_base_of< Value, T >::value, T & >::type takeOwnership(std::unique_ptr< T > Val)
Takes ownership of Val and returns a reference to it.
Definition: DataflowAnalysisContext.h:82
clang::dataflow::Value
Base class for all values computed by abstract interpretation.
Definition: Value.h:29
StorageLocation.h
clang::dataflow::DataflowAnalysisContext::takeOwnership
std::enable_if< std::is_base_of< StorageLocation, T >::value, T & >::type takeOwnership(std::unique_ptr< T > Loc)
Takes ownership of Loc and returns a reference to it.
Definition: DataflowAnalysisContext.h:69
clang::Expr
This represents one expression.
Definition: Expr.h:109
Value.h
clang::dataflow::DataflowAnalysisContext::createAtomicBoolValue
AtomicBoolValue & createAtomicBoolValue()
Creates an atomic boolean value.
Definition: DataflowAnalysisContext.h:146