1//===-- DataflowEnvironment.cpp ---------------------------------*- 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 an Environment class that is used by dataflow analyses
10// that run over Control-Flow Graphs (CFGs) to keep track of the state of the
11// program at given program points.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
16#include "clang/AST/Decl.h"
17#include "clang/AST/DeclCXX.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/ExprCXX.h"
20#include "clang/AST/Stmt.h"
21#include "clang/AST/Type.h"
22#include "clang/Analysis/FlowSensitive/ASTOps.h"
23#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
24#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
25#include "clang/Analysis/FlowSensitive/Formula.h"
26#include "clang/Analysis/FlowSensitive/StorageLocation.h"
27#include "clang/Analysis/FlowSensitive/Value.h"
28#include "clang/Basic/LLVM.h"
29#include "llvm/ADT/DenseMap.h"
30#include "llvm/ADT/DenseSet.h"
31#include "llvm/ADT/MapVector.h"
32#include "llvm/ADT/STLExtras.h"
33#include "llvm/ADT/ScopeExit.h"
34#include "llvm/ADT/SetVector.h"
35#include "llvm/ADT/SmallVector.h"
36#include "llvm/Support/ErrorHandling.h"
37#include <cassert>
38#include <memory>
39#include <optional>
40#include <stack>
41#include <utility>
42
43#define DEBUG_TYPE "dataflow"
44
45namespace clang {
46namespace dataflow {
47
48namespace {
49
50class SimpleBoolModel final : public Environment::BoolModel {
51public:
52 SimpleBoolModel() : BoolModel(BoolModelKind::Simple) {}
53
54 static bool classof(const BoolModel *M) {
55 return M->getKind() == BoolModelKind::Simple;
56 }
57
58 std::unique_ptr<BoolModel> clone() const override {
59 return std::make_unique<SimpleBoolModel>(args: *this);
60 }
61
62 void onFork() override {}
63
64 void assume(const Formula &F) override {
65 if (HasContradiction)
66 return;
67 unsigned PrevSize = AtomToVal.size();
68 // Given that F is assumed true, see if we can force the assignment
69 // of any atoms and ultimately reduce F to a literal (if possible).
70 // For example, if F is `A && B`, we will force `A` and `B` to be true.
71 // If F is `A || B`, we will only force an assignment if one of A or B is
72 // already known to be false.
73 assumeFormula(/*AssumedVal=*/true, F);
74 if (HasContradiction)
75 return;
76
77 if (std::optional<bool> Val = getLiteralValue(F)) {
78 if (!*Val) {
79 HasContradiction = true;
80 return;
81 }
82 } else {
83 // Retain `F` in `AssumedFormulas` only if it has not yet been reduced to
84 // a known truth value in `AtomToVal` (e.g., `A || B` or `A == B` where
85 // neither side is known yet).
86 //
87 // - Why save unresolved formulas: a compound formula (like
88 // `EqVal => (LHS == RHS)` from a comparison expression) is often
89 // assumed while its atoms are still unknown; when we later follow a
90 // branch that fixes one of those atoms, the propagation loop below can
91 // reduce the saved formula to concrete `AtomToVal` entries.
92 //
93 // - Skipping formulas that already evaluate to `true` avoids bloating
94 // `AssumedFormulas` with single-atom and conjunctive assumptions that
95 // are already fully represented by `AtomToVal` (though it also drops
96 // disjunctive formulas that were reduced using a branch-local atom,
97 // such as on the RHS of a short-circuit `&&` or `||`).
98 // TODO: We may want to retain some disjunctive formulas, but would need
99 // to profile and see how much it helps vs how much it costs.
100 AssumedFormulas.insert(X: &F);
101 }
102
103 if (AtomToVal.size() == PrevSize)
104 return;
105
106 // Propagate newly learned atom values through any pending assumed formulas.
107 // Note: Do not remove formulas from `AssumedFormulas` when they evaluate to
108 // `true` in a branch, because the atoms that satisfied them may be
109 // branch-local and discarded at a subsequent `join`, where the formula
110 // itself still holds on both branches.
111 bool Changed = true;
112 while (Changed) {
113 Changed = false;
114 for (const Formula *Pending : AssumedFormulas) {
115 unsigned Before = AtomToVal.size();
116 assumeFormula(/*AssumedVal=*/true, F: *Pending);
117 if (HasContradiction)
118 return;
119 if (auto V = getLiteralValue(F: *Pending); V.has_value() && *V == false) {
120 HasContradiction = true;
121 return;
122 }
123 if (AtomToVal.size() > Before)
124 Changed = true;
125 }
126 }
127 }
128
129 bool proves(const Formula &F) const override {
130 if (HasContradiction)
131 return true;
132 auto V = getLiteralValue(F);
133 return V.value_or(u: false);
134 }
135
136 bool allows(const Formula &F) const override {
137 if (HasContradiction)
138 return false;
139 auto V = getLiteralValue(F);
140 // We are conservative in the negative direction: if we can't determine the
141 // value, assume it is allowed.
142 return V.value_or(u: true);
143 }
144
145 BoolValue &joinBoolValues(BoolValue &Val1, const BoolModel &Model1,
146 BoolValue &Val2, const BoolModel &Model2,
147 Environment &JoinedEnv) override {
148 const auto &S1 = cast<SimpleBoolModel>(Val: Model1);
149 const auto &S2 = cast<SimpleBoolModel>(Val: Model2);
150 if (S1.HasContradiction)
151 return Val2;
152 if (S2.HasContradiction)
153 return Val1;
154 if (auto V1 = S1.getLiteralValue(F: Val1.formula());
155 V1.has_value() && V1 == S2.getLiteralValue(F: Val2.formula()))
156 return JoinedEnv.getBoolLiteralValue(Value: *V1);
157 return JoinedEnv.makeAtomicBoolValue();
158 }
159
160 void join(const BoolModel &ModelA, const BoolModel &ModelB) override {
161 const auto &SA = cast<SimpleBoolModel>(Val: ModelA);
162 const auto &SB = cast<SimpleBoolModel>(Val: ModelB);
163 AtomToVal.clear();
164 AssumedFormulas.clear();
165 HasContradiction = false;
166
167 if (SA.HasContradiction && SB.HasContradiction) {
168 HasContradiction = true;
169 } else if (SA.HasContradiction) {
170 AtomToVal = SB.AtomToVal;
171 AssumedFormulas = SB.AssumedFormulas;
172 } else if (SB.HasContradiction) {
173 AtomToVal = SA.AtomToVal;
174 AssumedFormulas = SA.AssumedFormulas;
175 } else {
176 // Intersect the AtomToVal maps.
177 for (const auto &[A, V] : SA.AtomToVal) {
178 auto It = SB.AtomToVal.find(Val: A);
179 if (It != SB.AtomToVal.end() && V == It->second)
180 AtomToVal.insert(KV: {A, V});
181 }
182
183 // Keep assumed formulas that hold on both branches (and are not already
184 // reduced to `true` by the joined `AtomToVal`): either because both
185 // environments still carry `F` as an unresolved formula, or because one
186 // branch carries `F` and the other branch's `AtomToVal` assignments
187 // already prove `F`. Any branch-local formulas not proved by the other
188 // branch are dropped here, which shrinks `AssumedFormulas` at joins.
189 for (const Formula *F : SA.AssumedFormulas) {
190 if (!proves(F: *F) && (SB.AssumedFormulas.contains(key: F) || SB.proves(F: *F)))
191 AssumedFormulas.insert(X: F);
192 }
193 for (const Formula *F : SB.AssumedFormulas) {
194 if (!proves(F: *F) && SA.proves(F: *F))
195 AssumedFormulas.insert(X: F);
196 }
197 }
198 }
199
200 LatticeEffect widen(const BoolModel &PrevModel) override {
201 const auto &PrevSimple = cast<SimpleBoolModel>(Val: PrevModel);
202 SimpleBoolModel Widened;
203 Widened.join(ModelA: *this, ModelB: PrevSimple);
204 LatticeEffect Effect = Widened.isEquivalentTo(Other: PrevSimple)
205 ? LatticeEffect::Unchanged
206 : LatticeEffect::Changed;
207 *this = std::move(Widened);
208 return Effect;
209 }
210
211 bool isEquivalentTo(const BoolModel &Other) const override {
212 const auto &OtherSimple = cast<SimpleBoolModel>(Val: Other);
213 if (HasContradiction != OtherSimple.HasContradiction)
214 return false;
215 if (HasContradiction)
216 return true;
217 return AtomToVal == OtherSimple.AtomToVal &&
218 AssumedFormulas.size() == OtherSimple.AssumedFormulas.size() &&
219 // SetVector::operator== compares insertion order, so check set
220 // membership.
221 llvm::all_of(Range: AssumedFormulas, P: [&](const Formula *F) {
222 return OtherSimple.AssumedFormulas.contains(key: F);
223 });
224 }
225
226 Atom getFlowConditionToken() const override {
227 llvm_unreachable(
228 "getFlowConditionToken() is only supported in SatBoolModel");
229 }
230
231 void dump(raw_ostream &OS) const override {
232 OS << "SimpleBoolModel:\n";
233 OS << " HasContradiction: " << HasContradiction << "\n";
234 OS << " AtomToVal:\n";
235 SmallVector<std::pair<Atom, bool>> SortedAtomToVal(AtomToVal.begin(),
236 AtomToVal.end());
237 llvm::sort(C&: SortedAtomToVal, Comp: llvm::less_first());
238 for (auto [A, V] : SortedAtomToVal)
239 OS << " " << A << " = " << (V ? "true" : "false") << "\n";
240 OS << " AssumedFormulas:\n";
241 for (const Formula *F : AssumedFormulas)
242 OS << " " << *F << "\n";
243 }
244
245private:
246 std::optional<bool> getAtomValue(Atom A) const {
247 auto It = AtomToVal.find(Val: A);
248 if (It == AtomToVal.end())
249 return std::nullopt;
250 return It->second;
251 }
252
253 std::optional<bool> getLiteralValue(const Formula &F) const {
254 switch (F.kind()) {
255 case Formula::AtomRef:
256 return getAtomValue(A: F.getAtom());
257 case Formula::Literal:
258 return F.literal();
259 case Formula::Not: {
260 ArrayRef<const Formula *> Operands = F.operands();
261 assert(Operands.size() == 1);
262 if (std::optional<bool> V = getLiteralValue(F: *Operands[0]))
263 return !*V;
264 return std::nullopt;
265 }
266 case Formula::And: {
267 ArrayRef<const Formula *> Operands = F.operands();
268 assert(Operands.size() == 2);
269 auto &LHS = *Operands[0];
270 auto &RHS = *Operands[1];
271 if (std::optional<bool> Left = getLiteralValue(F: LHS))
272 return !*Left ? Left : getLiteralValue(F: RHS);
273 if (std::optional<bool> Right = getLiteralValue(F: RHS);
274 Right.has_value() && *Right == false)
275 return Right;
276 return std::nullopt;
277 }
278 case Formula::Or: {
279 ArrayRef<const Formula *> Operands = F.operands();
280 assert(Operands.size() == 2);
281 auto &LHS = *Operands[0];
282 auto &RHS = *Operands[1];
283 if (std::optional<bool> Left = getLiteralValue(F: LHS))
284 return *Left ? Left : getLiteralValue(F: RHS);
285 if (std::optional<bool> Right = getLiteralValue(F: RHS);
286 Right.has_value() && *Right == true)
287 return Right;
288 return std::nullopt;
289 }
290 case Formula::Implies: {
291 ArrayRef<const Formula *> Operands = F.operands();
292 assert(Operands.size() == 2);
293 auto &LHS = *Operands[0];
294 auto &RHS = *Operands[1];
295 if (std::optional<bool> Left = getLiteralValue(F: LHS))
296 return !*Left ? true : getLiteralValue(F: RHS);
297 if (std::optional<bool> Right = getLiteralValue(F: RHS);
298 Right.has_value() && *Right == true)
299 return true;
300 return std::nullopt;
301 }
302 case Formula::Equal: {
303 ArrayRef<const Formula *> Operands = F.operands();
304 assert(Operands.size() == 2);
305 auto &LHS = *Operands[0];
306 auto &RHS = *Operands[1];
307 // If the formula is of the form `A == A`, then we can simplify to
308 // true, without needing to know A is set to a literal value.
309 if (&LHS == &RHS)
310 return true;
311 // Similarly, if the formula is of the form `A == !A` (or !A == A),
312 // then we can simplify to false.
313 // We should consider lifting such simplification with identities into a
314 // a separate function (there are more cases, e.g., `A OR !A` is true),
315 // while keeping this function focused on cases where the operands are
316 // literal values.
317 if ((LHS.kind() == Formula::Not && LHS.operands()[0] == &RHS) ||
318 (RHS.kind() == Formula::Not && RHS.operands()[0] == &LHS))
319 return false;
320 auto V_L = getLiteralValue(F: LHS);
321 if (!V_L.has_value())
322 return std::nullopt;
323 auto V_R = getLiteralValue(F: RHS);
324 if (!V_R.has_value())
325 return std::nullopt;
326 return *V_L == *V_R;
327 }
328 }
329 llvm_unreachable("fully covered switch");
330 }
331
332 // Updates atom assignments under the assumption that subformula `F`
333 // evaluates to `AssumedVal` (i.e., `F == AssumedVal`).
334 //
335 // Top-level `assume(F)` starts with `AssumedVal = true`, and recursive
336 // calls flip `AssumedVal` when traversing negations (`Formula::Not`) or
337 // comparisons (`Formula::Equal`) against known boolean values.
338 //
339 // For example:
340 // - for `assume(!A)`, then `A` must be `false`
341 // - for `assume(A && B)`, then both `A` and `B` must be `true`.
342 void assumeFormula(bool AssumedVal, const Formula &F) {
343 if (HasContradiction)
344 return;
345 switch (F.kind()) {
346 case Formula::AtomRef: {
347 // Base case: `F` is a single atom, so assuming `F == AssumedVal` directly
348 // binds this atom to `AssumedVal`, or marks the environment as having a
349 // contradiction if the atom was already bound to the opposite value.
350 auto [It, Inserted] = AtomToVal.try_emplace(Key: F.getAtom(), Args&: AssumedVal);
351 if (!Inserted && It->second != AssumedVal)
352 HasContradiction = true;
353 break;
354 }
355 case Formula::Literal:
356 if (F.literal() != AssumedVal)
357 HasContradiction = true;
358 break;
359 case Formula::Not: {
360 // Assuming `(!Operand) == AssumedVal` is equivalent to assuming
361 // `Operand == !AssumedVal`.
362 ArrayRef<const Formula *> Operands = F.operands();
363 assert(Operands.size() == 1);
364 assumeFormula(AssumedVal: !AssumedVal, F: *Operands[0]);
365 break;
366 }
367 case Formula::And: {
368 // - If `AssumedVal == true` (`LHS && RHS`), both operands must be `true`.
369 // - If `AssumedVal == false` (`!(LHS && RHS)` <=> `!LHS || !RHS`), at
370 // least one operand is `false`; if one operand is already known `true`,
371 // the other must be `false`.
372 ArrayRef<const Formula *> Operands = F.operands();
373 assert(Operands.size() == 2);
374 auto &LHS = *Operands[0];
375 auto &RHS = *Operands[1];
376 if (AssumedVal == true) {
377 assumeFormula(AssumedVal: true, F: LHS);
378 assumeFormula(AssumedVal: true, F: RHS);
379 } else {
380 if (auto V = getLiteralValue(F: LHS); V.has_value() && *V == true)
381 assumeFormula(AssumedVal: false, F: RHS);
382 else if (auto V = getLiteralValue(F: RHS); V.has_value() && *V == true)
383 assumeFormula(AssumedVal: false, F: LHS);
384 }
385 break;
386 }
387 case Formula::Or: {
388 // - If `AssumedVal == false` (`!(LHS || RHS)` <=> `!LHS && !RHS`), both
389 // operands must be `false`.
390 // - If `AssumedVal == true` (`LHS || RHS`), at least one operand is
391 // `true`; if one operand is already known `false`, the other must be
392 // `true`.
393 ArrayRef<const Formula *> Operands = F.operands();
394 assert(Operands.size() == 2);
395 auto &LHS = *Operands[0];
396 auto &RHS = *Operands[1];
397 if (AssumedVal == false) {
398 assumeFormula(AssumedVal: false, F: LHS);
399 assumeFormula(AssumedVal: false, F: RHS);
400 } else {
401 if (auto V = getLiteralValue(F: LHS); V.has_value() && *V == false)
402 assumeFormula(AssumedVal: true, F: RHS);
403 else if (auto V = getLiteralValue(F: RHS); V.has_value() && *V == false)
404 assumeFormula(AssumedVal: true, F: LHS);
405 }
406 break;
407 }
408 case Formula::Implies: {
409 // `LHS => RHS` is equivalent to `!LHS || RHS`.
410 // - If `AssumedVal == false` (`!(LHS => RHS)`), then `LHS` must be `true`
411 // and `RHS` must be `false`.
412 // - If `AssumedVal == true` (`LHS => RHS`):
413 // - Modus ponens: if `LHS` is known `true`, then `RHS` must be `true`.
414 // - Modus tollens: if `RHS` is known `false`, then `LHS` must be
415 // `false`.
416 ArrayRef<const Formula *> Operands = F.operands();
417 assert(Operands.size() == 2);
418 auto &LHS = *Operands[0];
419 auto &RHS = *Operands[1];
420 if (AssumedVal == false) {
421 assumeFormula(AssumedVal: true, F: LHS);
422 assumeFormula(AssumedVal: false, F: RHS);
423 } else {
424 if (auto V = getLiteralValue(F: LHS); V.has_value() && *V == true)
425 assumeFormula(AssumedVal: true, F: RHS);
426 else if (auto V = getLiteralValue(F: RHS); V.has_value() && *V == false)
427 assumeFormula(AssumedVal: false, F: LHS);
428 }
429 break;
430 }
431 case Formula::Equal: {
432 // Assuming `(LHS == RHS) == AssumedVal`: if one side already has a known
433 // truth value `*V`, then the other side must evaluate to
434 // `(AssumedVal == *V)`.
435 ArrayRef<const Formula *> Operands = F.operands();
436 assert(Operands.size() == 2);
437 auto &LHS = *Operands[0];
438 auto &RHS = *Operands[1];
439 if (auto V = getLiteralValue(F: LHS)) {
440 assumeFormula(AssumedVal: AssumedVal == *V, F: RHS);
441 } else if (auto V = getLiteralValue(F: RHS)) {
442 assumeFormula(AssumedVal: AssumedVal == *V, F: LHS);
443 }
444 break;
445 }
446 }
447 }
448
449 llvm::DenseMap<Atom, bool> AtomToVal;
450 llvm::SmallSetVector<const Formula *, 4> AssumedFormulas;
451 bool HasContradiction = false;
452};
453
454class SatBoolModel final : public Environment::BoolModel {
455public:
456 SatBoolModel(DataflowAnalysisContext &DACtx, Atom FlowConditionToken)
457 : BoolModel(BoolModelKind::SAT), DACtx(DACtx),
458 FlowConditionToken(FlowConditionToken) {}
459
460 explicit SatBoolModel(DataflowAnalysisContext &DACtx)
461 : SatBoolModel(DACtx, DACtx.arena().makeFlowConditionToken()) {}
462
463 static bool classof(const BoolModel *M) {
464 return M->getKind() == BoolModelKind::SAT;
465 }
466
467 std::unique_ptr<BoolModel> clone() const override {
468 return std::make_unique<SatBoolModel>(args: *this);
469 }
470
471 void onFork() override {
472 FlowConditionToken = DACtx.forkFlowCondition(Token: FlowConditionToken);
473 }
474
475 void assume(const Formula &F) override {
476 DACtx.addFlowConditionConstraint(Token: FlowConditionToken, Constraint: F);
477 }
478
479 bool proves(const Formula &F) const override {
480 return DACtx.flowConditionImplies(Token: FlowConditionToken, F);
481 }
482
483 bool allows(const Formula &F) const override {
484 return DACtx.flowConditionAllows(Token: FlowConditionToken, F);
485 }
486
487 BoolValue &joinBoolValues(BoolValue &Val1, const BoolModel &Model1,
488 BoolValue &Val2, const BoolModel &Model2,
489 Environment &JoinedEnv) override {
490 const auto &Sat1 = cast<SatBoolModel>(Val: Model1);
491 const auto &Sat2 = cast<SatBoolModel>(Val: Model2);
492 auto &A = JoinedEnv.arena();
493 auto &JoinedVal = A.makeAtomRef(A: A.makeAtom());
494 JoinedEnv.assume(
495 A.makeOr(LHS: A.makeAnd(LHS: A.makeAtomRef(A: Sat1.getFlowConditionToken()),
496 RHS: A.makeEquals(LHS: JoinedVal, RHS: Val1.formula())),
497 RHS: A.makeAnd(LHS: A.makeAtomRef(A: Sat2.getFlowConditionToken()),
498 RHS: A.makeEquals(LHS: JoinedVal, RHS: Val2.formula()))));
499 return A.makeBoolValue(JoinedVal);
500 }
501
502 void join(const BoolModel &ModelA, const BoolModel &ModelB) override {
503 const auto &SatA = cast<SatBoolModel>(Val: ModelA);
504 const auto &SatB = cast<SatBoolModel>(Val: ModelB);
505 // FIXME: update join to detect backedges and simplify the flow condition
506 // accordingly.
507 FlowConditionToken = DACtx.joinFlowConditions(FirstToken: SatA.FlowConditionToken,
508 SecondToken: SatB.FlowConditionToken);
509 }
510
511 LatticeEffect widen(const BoolModel &PrevModel) override {
512 (void)cast<SatBoolModel>(Val: PrevModel);
513 return LatticeEffect::Unchanged;
514 }
515
516 bool isEquivalentTo(const BoolModel &Other) const override {
517 (void)cast<SatBoolModel>(Val: Other);
518 return true;
519 }
520
521 Atom getFlowConditionToken() const override { return FlowConditionToken; }
522
523 void dump(raw_ostream &OS) const override {
524 DACtx.dumpFlowCondition(Token: FlowConditionToken, OS);
525 }
526
527private:
528 DataflowAnalysisContext &DACtx;
529 Atom FlowConditionToken;
530};
531
532} // namespace
533
534// FIXME: convert these to parameters of the analysis or environment. Current
535// settings have been experimentaly validated, but only for a particular
536// analysis.
537static constexpr int MaxCompositeValueDepth = 3;
538static constexpr int MaxCompositeValueSize = 1000;
539
540/// Returns a map consisting of key-value entries that are present in both maps.
541static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc(
542 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,
543 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) {
544 llvm::DenseMap<const ValueDecl *, StorageLocation *> Result;
545 for (auto &Entry : DeclToLoc1) {
546 auto It = DeclToLoc2.find(Val: Entry.first);
547 if (It != DeclToLoc2.end() && Entry.second == It->second)
548 Result.insert(KV: {Entry.first, Entry.second});
549 }
550 return Result;
551}
552
553// Performs a join on either `ExprToLoc` or `ExprToVal`.
554// The maps must be consistent in the sense that any entries for the same
555// expression must map to the same location / value. This is the case if we are
556// performing a join for control flow within a full-expression (which is the
557// only case when this function should be used).
558template <typename MapT>
559static MapT joinExprMaps(const MapT &Map1, const MapT &Map2) {
560 MapT Result = Map1;
561
562 for (const auto &Entry : Map2) {
563 [[maybe_unused]] auto [It, Inserted] = Result.insert(Entry);
564 // If there was an existing entry, its value should be the same as for the
565 // entry we were trying to insert.
566 assert(It->second == Entry.second);
567 }
568
569 return Result;
570}
571
572// Whether to consider equivalent two values with an unknown relation.
573//
574// FIXME: this function is a hack enabling unsoundness to support
575// convergence. Once we have widening support for the reference/pointer and
576// struct built-in models, this should be unconditionally `false` (and inlined
577// as such at its call sites).
578static bool equateUnknownValues(Value::Kind K) {
579 switch (K) {
580 case Value::Kind::Integer:
581 case Value::Kind::Pointer:
582 return true;
583 default:
584 return false;
585 }
586}
587
588static bool compareDistinctValues(QualType Type, Value &Val1,
589 const Environment &Env1, Value &Val2,
590 const Environment &Env2,
591 Environment::ValueModel &Model) {
592 // Note: Potentially costly, but, for booleans, we could check whether both
593 // can be proven equivalent in their respective environments.
594
595 // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
596 // and implement separate, join/widen specific handling for
597 // reference/pointers.
598 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
599 case ComparisonResult::Same:
600 return true;
601 case ComparisonResult::Different:
602 return false;
603 case ComparisonResult::Unknown:
604 return equateUnknownValues(K: Val1.getKind());
605 }
606 llvm_unreachable("All cases covered in switch");
607}
608
609/// Attempts to join distinct values `Val1` and `Val2` in `Env1` and `Env2`,
610/// respectively, of the same type `Type`. Joining generally produces a single
611/// value that (soundly) approximates the two inputs, although the actual
612/// meaning depends on `Model`.
613static Value *joinDistinctValues(QualType Type, Value &Val1,
614 const Environment &Env1, Value &Val2,
615 const Environment &Env2,
616 Environment &JoinedEnv,
617 Environment::ValueModel &Model) {
618 // Join distinct boolean values preserving information about the constraints
619 // in the respective path conditions.
620 if (isa<BoolValue>(Val: &Val1) && isa<BoolValue>(Val: &Val2)) {
621 // FIXME: Checking both values should be unnecessary, since they should have
622 // a consistent shape. However, right now we can end up with BoolValue's in
623 // integer-typed variables due to our incorrect handling of
624 // boolean-to-integer casts (we just propagate the BoolValue to the result
625 // of the cast). So, a join can encounter an integer in one branch but a
626 // bool in the other.
627 // For example:
628 // ```
629 // std::optional<bool> o;
630 // int x;
631 // if (o.has_value())
632 // x = o.value();
633 // ```
634 return &JoinedEnv.joinBoolValues(Val1&: cast<BoolValue>(Val&: Val1), Env1,
635 Val2&: cast<BoolValue>(Val&: Val2), Env2);
636 }
637
638 Value *JoinedVal = JoinedEnv.createValue(Type);
639 if (JoinedVal)
640 Model.join(Type, Val1, Env1, Val2, Env2, JoinedVal&: *JoinedVal, JoinedEnv);
641
642 return JoinedVal;
643}
644
645static WidenResult widenDistinctValues(QualType Type, Value &Prev,
646 const Environment &PrevEnv,
647 Value &Current, Environment &CurrentEnv,
648 Environment::ValueModel &Model) {
649 // Boolean-model widening.
650 if (isa<BoolValue>(Val: Prev) && isa<BoolValue>(Val: Current)) {
651 // FIXME: Checking both values should be unnecessary, but we can currently
652 // end up with `BoolValue`s in integer-typed variables. See comment in
653 // `joinDistinctValues()` for details.
654 auto &PrevBool = cast<BoolValue>(Val&: Prev);
655 auto &CurBool = cast<BoolValue>(Val&: Current);
656
657 if (isa<TopBoolValue>(Val: Prev))
658 // Safe to return `Prev` here, because Top is never dependent on the
659 // environment.
660 return {.V: &Prev, .Effect: LatticeEffect::Unchanged};
661
662 // We may need to widen to Top, but before we do so, check whether both
663 // values are implied to be either true or false in the current environment.
664 // In that case, we can simply return a literal instead.
665 bool TruePrev = PrevEnv.proves(PrevBool.formula());
666 bool TrueCur = CurrentEnv.proves(CurBool.formula());
667 if (TruePrev && TrueCur)
668 return {.V: &CurrentEnv.getBoolLiteralValue(Value: true), .Effect: LatticeEffect::Unchanged};
669 if (!TruePrev && !TrueCur &&
670 PrevEnv.proves(PrevEnv.arena().makeNot(Val: PrevBool.formula())) &&
671 CurrentEnv.proves(CurrentEnv.arena().makeNot(Val: CurBool.formula())))
672 return {.V: &CurrentEnv.getBoolLiteralValue(Value: false), .Effect: LatticeEffect::Unchanged};
673
674 return {.V: &CurrentEnv.makeTopBoolValue(), .Effect: LatticeEffect::Changed};
675 }
676
677 // FIXME: Add other built-in model widening.
678
679 // Custom-model widening.
680 if (auto Result = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
681 return *Result;
682
683 return {.V: &Current, .Effect: equateUnknownValues(K: Prev.getKind())
684 ? LatticeEffect::Unchanged
685 : LatticeEffect::Changed};
686}
687
688// Returns whether the values in `Map1` and `Map2` compare equal for those
689// keys that `Map1` and `Map2` have in common.
690template <typename Key>
691static bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
692 const llvm::MapVector<Key, Value *> &Map2,
693 const Environment &Env1,
694 const Environment &Env2,
695 Environment::ValueModel &Model) {
696 for (auto &Entry : Map1) {
697 Key K = Entry.first;
698 assert(K != nullptr);
699
700 Value *Val = Entry.second;
701 assert(Val != nullptr);
702
703 auto It = Map2.find(K);
704 if (It == Map2.end())
705 continue;
706 assert(It->second != nullptr);
707
708 if (!areEquivalentValues(*Val, *It->second) &&
709 !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2,
710 Model))
711 return false;
712 }
713
714 return true;
715}
716
717// Perform a join on two `LocToVal` maps.
718static llvm::MapVector<const StorageLocation *, Value *>
719joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
720 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
721 const Environment &Env1, const Environment &Env2,
722 Environment &JoinedEnv, Environment::ValueModel &Model) {
723 llvm::MapVector<const StorageLocation *, Value *> Result;
724 for (auto &Entry : LocToVal) {
725 const StorageLocation *Loc = Entry.first;
726 assert(Loc != nullptr);
727
728 Value *Val = Entry.second;
729 assert(Val != nullptr);
730
731 auto It = LocToVal2.find(Key: Loc);
732 if (It == LocToVal2.end())
733 continue;
734 assert(It->second != nullptr);
735
736 if (Value *JoinedVal = Environment::joinValues(
737 Ty: Loc->getType(), Val1: Val, Env1, Val2: It->second, Env2, JoinedEnv, Model)) {
738 Result.insert(KV: {Loc, JoinedVal});
739 }
740 }
741
742 return Result;
743}
744
745// Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
746// `const StorageLocation *` or `const Expr *`.
747template <typename Key>
748static llvm::MapVector<Key, Value *>
749widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
750 const llvm::MapVector<Key, Value *> &PrevMap,
751 Environment &CurEnv, const Environment &PrevEnv,
752 Environment::ValueModel &Model, LatticeEffect &Effect) {
753 llvm::MapVector<Key, Value *> WidenedMap;
754 for (auto &Entry : CurMap) {
755 Key K = Entry.first;
756 assert(K != nullptr);
757
758 Value *Val = Entry.second;
759 assert(Val != nullptr);
760
761 auto PrevIt = PrevMap.find(K);
762 if (PrevIt == PrevMap.end())
763 continue;
764 assert(PrevIt->second != nullptr);
765
766 if (areEquivalentValues(*Val, *PrevIt->second)) {
767 WidenedMap.insert({K, Val});
768 continue;
769 }
770
771 auto [WidenedVal, ValEffect] = widenDistinctValues(
772 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model);
773 WidenedMap.insert({K, WidenedVal});
774 if (ValEffect == LatticeEffect::Changed)
775 Effect = LatticeEffect::Changed;
776 }
777
778 return WidenedMap;
779}
780
781namespace {
782
783// Visitor that builds a map from record prvalues to result objects.
784// For each result object that it encounters, it propagates the storage location
785// of the result object to all record prvalues that can initialize it.
786class ResultObjectVisitor : public AnalysisASTVisitor {
787public:
788 // `ResultObjectMap` will be filled with a map from record prvalues to result
789 // object. If this visitor will traverse a function that returns a record by
790 // value, `LocForRecordReturnVal` is the location to which this record should
791 // be written; otherwise, it is null.
792 explicit ResultObjectVisitor(
793 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap,
794 RecordStorageLocation *LocForRecordReturnVal,
795 DataflowAnalysisContext &DACtx)
796 : ResultObjectMap(ResultObjectMap),
797 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}
798
799 // Traverse all member and base initializers of `Ctor`. This function is not
800 // called by `RecursiveASTVisitor`; it should be called manually if we are
801 // analyzing a constructor. `ThisPointeeLoc` is the storage location that
802 // `this` points to.
803 void traverseConstructorInits(const CXXConstructorDecl *Ctor,
804 RecordStorageLocation *ThisPointeeLoc) {
805 assert(ThisPointeeLoc != nullptr);
806 for (const CXXCtorInitializer *Init : Ctor->inits()) {
807 Expr *InitExpr = Init->getInit();
808 if (FieldDecl *Field = Init->getMember();
809 Field != nullptr && Field->getType()->isRecordType()) {
810 PropagateResultObject(E: InitExpr, Loc: cast<RecordStorageLocation>(
811 Val: ThisPointeeLoc->getChild(D: *Field)));
812 } else if (Init->getBaseClass()) {
813 PropagateResultObject(E: InitExpr, Loc: ThisPointeeLoc);
814 }
815
816 // Ensure that any result objects within `InitExpr` (e.g. temporaries)
817 // are also propagated to the prvalues that initialize them.
818 TraverseStmt(S: InitExpr);
819
820 // If this is a `CXXDefaultInitExpr`, also propagate any result objects
821 // within the default expression.
822 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(Val: InitExpr))
823 TraverseStmt(S: DefaultInit->getExpr());
824 }
825 }
826
827 bool VisitVarDecl(VarDecl *VD) override {
828 if (VD->getType()->isRecordType() && VD->hasInit())
829 PropagateResultObject(
830 E: VD->getInit(),
831 Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(D: *VD)));
832 return true;
833 }
834
835 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) override {
836 if (MTE->getType()->isRecordType())
837 PropagateResultObject(
838 E: MTE->getSubExpr(),
839 Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(E: *MTE)));
840 return true;
841 }
842
843 bool VisitReturnStmt(ReturnStmt *Return) override {
844 Expr *RetValue = Return->getRetValue();
845 if (RetValue != nullptr && RetValue->getType()->isRecordType() &&
846 RetValue->isPRValue())
847 PropagateResultObject(E: RetValue, Loc: LocForRecordReturnVal);
848 return true;
849 }
850
851 bool VisitExpr(Expr *E) override {
852 // Clang's AST can have record-type prvalues without a result object -- for
853 // example as full-expressions contained in a compound statement or as
854 // arguments of call expressions. We notice this if we get here and a
855 // storage location has not yet been associated with `E`. In this case,
856 // treat this as if it was a `MaterializeTemporaryExpr`.
857 if (E->isPRValue() && E->getType()->isRecordType() &&
858 !ResultObjectMap.contains(Val: E))
859 PropagateResultObject(
860 E, Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(E: *E)));
861 return true;
862 }
863
864 void
865 PropagateResultObjectToRecordInitList(const RecordInitListHelper &InitList,
866 RecordStorageLocation *Loc) {
867 for (auto [Base, Init] : InitList.base_inits()) {
868 assert(Base->getType().getCanonicalType() ==
869 Init->getType().getCanonicalType());
870
871 // Storage location for the base class is the same as that of the
872 // derived class because we "flatten" the object hierarchy and put all
873 // fields in `RecordStorageLocation` of the derived class.
874 PropagateResultObject(E: Init, Loc);
875 }
876
877 for (auto [Field, Init] : InitList.field_inits()) {
878 // Fields of non-record type are handled in
879 // `TransferVisitor::VisitInitListExpr()`.
880 if (Field->getType()->isRecordType())
881 PropagateResultObject(
882 E: Init, Loc: cast<RecordStorageLocation>(Val: Loc->getChild(D: *Field)));
883 }
884 }
885
886 // Assigns `Loc` as the result object location of `E`, then propagates the
887 // location to all lower-level prvalues that initialize the same object as
888 // `E` (or one of its base classes or member variables).
889 void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) {
890 if (!E->isPRValue() || !E->getType()->isRecordType()) {
891 assert(false);
892 // Ensure we don't propagate the result object if we hit this in a
893 // release build.
894 return;
895 }
896
897 ResultObjectMap[E] = Loc;
898
899 // The following AST node kinds are "original initializers": They are the
900 // lowest-level AST node that initializes a given object, and nothing
901 // below them can initialize the same object (or part of it).
902 if (isa<CXXConstructExpr>(Val: E) || isa<CallExpr>(Val: E) || isa<LambdaExpr>(Val: E) ||
903 isa<CXXDefaultArgExpr>(Val: E) || isa<CXXStdInitializerListExpr>(Val: E) ||
904 isa<AtomicExpr>(Val: E) || isa<CXXInheritedCtorInitExpr>(Val: E) ||
905 // We treat `BuiltinBitCastExpr` as an "original initializer" too as
906 // it may not even be casting from a record type -- and even if it is,
907 // the two objects are in general of unrelated type.
908 isa<BuiltinBitCastExpr>(Val: E) ||
909 // This covers both co_await and co_yield.
910 // The result object of co_await is <op>.await_resume(), but there is
911 // no expression for that to propagate to.
912 // co_yield is equivalent to `co_await promise.yield_value(expr)`.
913 isa<CoroutineSuspendExpr>(Val: E)) {
914 return;
915 }
916 if (auto *Op = dyn_cast<BinaryOperator>(Val: E);
917 Op && Op->getOpcode() == BO_Cmp) {
918 // Builtin `<=>` returns a `std::strong_ordering` object.
919 return;
920 }
921
922 if (auto *InitList = dyn_cast<InitListExpr>(Val: E)) {
923 if (!InitList->isSemanticForm())
924 return;
925 if (InitList->isTransparent()) {
926 PropagateResultObject(E: InitList->getInit(Init: 0), Loc);
927 return;
928 }
929
930 PropagateResultObjectToRecordInitList(InitList: RecordInitListHelper(InitList),
931 Loc);
932 return;
933 }
934
935 if (auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(Val: E)) {
936 PropagateResultObjectToRecordInitList(InitList: RecordInitListHelper(ParenInitList),
937 Loc);
938 return;
939 }
940
941 if (auto *Op = dyn_cast<BinaryOperator>(Val: E); Op && Op->isCommaOp()) {
942 PropagateResultObject(E: Op->getRHS(), Loc);
943 return;
944 }
945
946 if (auto *Cond = dyn_cast<AbstractConditionalOperator>(Val: E)) {
947 PropagateResultObject(E: Cond->getTrueExpr(), Loc);
948 PropagateResultObject(E: Cond->getFalseExpr(), Loc);
949 return;
950 }
951
952 if (auto *SE = dyn_cast<StmtExpr>(Val: E)) {
953 PropagateResultObject(E: cast<Expr>(Val: SE->getSubStmt()->body_back()), Loc);
954 return;
955 }
956
957 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: E)) {
958 PropagateResultObject(E: DIE->getExpr(), Loc);
959 return;
960 }
961
962 // All other expression nodes that propagate a record prvalue should have
963 // exactly one child.
964 SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end());
965 LLVM_DEBUG({
966 if (Children.size() != 1)
967 E->dump();
968 });
969 assert(Children.size() == 1);
970 for (Stmt *S : Children)
971 PropagateResultObject(E: cast<Expr>(Val: S), Loc);
972 }
973
974private:
975 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
976 RecordStorageLocation *LocForRecordReturnVal;
977 DataflowAnalysisContext &DACtx;
978};
979
980/// A visitor that finds `CXXThisExpr` that can refer to an object other than
981/// the `this` of a member function.
982class ThisExprOverridesVisitor : public AnalysisASTVisitor {
983 using BaseVisitor = AnalysisASTVisitor;
984
985public:
986 ThisExprOverridesVisitor(
987 RecordStorageLocation *ThisPointeeLoc,
988 const llvm::DenseMap<const Expr *, RecordStorageLocation *>
989 &ResultObjectMap,
990 llvm::DenseMap<const CXXThisExpr *, RecordStorageLocation *>
991 &ThisExprOverrides)
992 : DefaultThisPointeeLoc(ThisPointeeLoc), ResultObjectMap(ResultObjectMap),
993 ThisExprOverrides(ThisExprOverrides) {
994 ThisLocations.push(x: DefaultThisPointeeLoc);
995 }
996
997 void traverseConstructorInits(const CXXConstructorDecl *Ctor) {
998 for (const CXXCtorInitializer *Init : Ctor->inits()) {
999 TraverseStmt(S: Init->getInit());
1000 }
1001 }
1002
1003 bool TraverseInitListExpr(InitListExpr *ILE) override {
1004 if (!ILE->isSemanticForm() || ILE->isTransparent()) {
1005 BaseVisitor::TraverseInitListExpr(S: ILE);
1006 return true;
1007 }
1008 bool IsRecordType = ILE->getType()->isRecordType();
1009 if (IsRecordType) {
1010 auto It = ResultObjectMap.find(Val: ILE);
1011 if (It == ResultObjectMap.end()) {
1012 llvm_unreachable("InitListExpr not found in ResultObjectMap");
1013 return false;
1014 }
1015 InitListLocations.push(x: It->second);
1016 }
1017 BaseVisitor::TraverseInitListExpr(S: ILE);
1018 if (IsRecordType)
1019 InitListLocations.pop();
1020 return true;
1021 }
1022
1023 bool TraverseCXXParenListInitExpr(CXXParenListInitExpr *PLIE) override {
1024 auto It = ResultObjectMap.find(Val: PLIE);
1025 if (It == ResultObjectMap.end()) {
1026 llvm_unreachable("CXXParenListInitExpr not found in ResultObjectMap");
1027 return false;
1028 }
1029 InitListLocations.push(x: It->second);
1030 BaseVisitor::TraverseCXXParenListInitExpr(S: PLIE);
1031 InitListLocations.pop();
1032 return true;
1033 }
1034
1035 bool TraverseCXXDefaultInitExpr(CXXDefaultInitExpr *CDIE) override {
1036 bool HasInitListLocations = !InitListLocations.empty();
1037 if (HasInitListLocations) {
1038 auto *Loc = InitListLocations.top();
1039 ThisLocations.push(x: Loc);
1040 }
1041 BaseVisitor::TraverseCXXDefaultInitExpr(S: CDIE);
1042 if (HasInitListLocations)
1043 ThisLocations.pop();
1044 return true;
1045 }
1046
1047 bool TraverseCXXThisExpr(CXXThisExpr *This) override {
1048 assert(!ThisLocations.empty());
1049 auto *Loc = ThisLocations.top();
1050 if (Loc != DefaultThisPointeeLoc)
1051 ThisExprOverrides[This] = Loc;
1052 return true;
1053 }
1054
1055 // The default `this` pointee location (null if not in a member function).
1056 RecordStorageLocation *DefaultThisPointeeLoc;
1057 // Locations to use for `this`, with the most recent scope on top.
1058 std::stack<RecordStorageLocation *> ThisLocations;
1059 // A stack of nested InitListExpr and CXXParenListInitExprs storage
1060 // locations that may be used for `this` if we enter a CXXDefaultInitExpr.
1061 std::stack<RecordStorageLocation *> InitListLocations;
1062 // Map to look up a storage location, e.g., when encountering an
1063 // InitListExpr.
1064 const llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
1065 // The visitor will update this map with locations to use for `this`,
1066 // if different from `DefaultThisPointeeLoc`.
1067 llvm::DenseMap<const CXXThisExpr *, RecordStorageLocation *>
1068 &ThisExprOverrides;
1069};
1070
1071} // namespace
1072
1073Environment::Environment(DataflowAnalysisContext &DACtx,
1074 Atom FlowConditionToken)
1075 : DACtx(&DACtx),
1076 BoolState(std::make_unique<SatBoolModel>(args&: DACtx, args&: FlowConditionToken)) {
1077 assert(DACtx.getOptions().BoolModel == BoolModelKind::SAT &&
1078 "FlowConditionToken constructor requires BoolModelKind::SAT");
1079}
1080
1081Environment::Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) {
1082 switch (DACtx.getOptions().BoolModel) {
1083 case BoolModelKind::SAT:
1084 BoolState = std::make_unique<SatBoolModel>(args&: DACtx);
1085 break;
1086 case BoolModelKind::Simple:
1087 BoolState = std::make_unique<SimpleBoolModel>();
1088 break;
1089 }
1090}
1091
1092Environment::Environment(const Environment &Other)
1093 : DACtx(Other.DACtx), CallStack(Other.CallStack),
1094 InitialTargetFunc(Other.InitialTargetFunc),
1095 InitialTargetStmt(Other.InitialTargetStmt),
1096 ResultObjectMap(Other.ResultObjectMap), ReturnVal(Other.ReturnVal),
1097 ReturnLoc(Other.ReturnLoc),
1098 LocForRecordReturnVal(Other.LocForRecordReturnVal),
1099 ThisPointeeLoc(Other.ThisPointeeLoc),
1100 ThisExprOverrides(Other.ThisExprOverrides), DeclToLoc(Other.DeclToLoc),
1101 ExprToLoc(Other.ExprToLoc), ExprToVal(Other.ExprToVal),
1102 LocToVal(Other.LocToVal), BoolState(Other.BoolState->clone()) {}
1103
1104void Environment::initialize() {
1105 if (InitialTargetStmt == nullptr)
1106 return;
1107
1108 if (InitialTargetFunc == nullptr) {
1109 initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(S: *InitialTargetStmt));
1110 ResultObjectMap =
1111 std::make_shared<PrValueToResultObject>(args: buildResultObjectMap(
1112 DACtx, S: InitialTargetStmt, ThisPointeeLoc: getThisPointeeStorageLocation(),
1113 /*LocForRecordReturnValue=*/LocForRecordReturnVal: nullptr));
1114
1115 ThisExprOverrides =
1116 std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap(
1117 S: InitialTargetStmt, ThisPointeeLoc: getThisPointeeStorageLocation(),
1118 ResultObjectMap: *ResultObjectMap));
1119 return;
1120 }
1121
1122 initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(FD: *InitialTargetFunc));
1123
1124 for (const auto *ParamDecl : InitialTargetFunc->parameters()) {
1125 assert(ParamDecl != nullptr);
1126 setStorageLocation(D: *ParamDecl, Loc&: createObject(D: *ParamDecl, InitExpr: nullptr));
1127 }
1128
1129 if (InitialTargetFunc->getReturnType()->isRecordType())
1130 LocForRecordReturnVal = &cast<RecordStorageLocation>(
1131 Val&: createStorageLocation(Type: InitialTargetFunc->getReturnType()));
1132
1133 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(Val: InitialTargetFunc)) {
1134 auto *Parent = MethodDecl->getParent();
1135 assert(Parent != nullptr);
1136
1137 if (Parent->isLambda()) {
1138 for (const auto &Capture : Parent->captures()) {
1139 if (Capture.capturesVariable()) {
1140 const auto *VarDecl = Capture.getCapturedVar();
1141 assert(VarDecl != nullptr);
1142 setStorageLocation(D: *VarDecl, Loc&: createObject(D: *VarDecl, InitExpr: nullptr));
1143 } else if (Capture.capturesThis()) {
1144 if (auto *Ancestor = InitialTargetFunc->getNonClosureAncestor()) {
1145 const auto *SurroundingMethodDecl = cast<CXXMethodDecl>(Val: Ancestor);
1146 QualType ThisPointeeType =
1147 SurroundingMethodDecl->getFunctionObjectParameterType();
1148 setThisPointeeStorageLocation(
1149 cast<RecordStorageLocation>(Val&: createObject(Ty: ThisPointeeType)));
1150 } else if (auto *FieldBeingInitialized =
1151 dyn_cast<FieldDecl>(Val: Parent->getLambdaContextDecl())) {
1152 // This is in a field initializer, rather than a method.
1153 const RecordDecl *RD = FieldBeingInitialized->getParent();
1154 const ASTContext &Ctx = RD->getASTContext();
1155 CanQualType T = Ctx.getCanonicalTagType(TD: RD);
1156 setThisPointeeStorageLocation(
1157 cast<RecordStorageLocation>(Val&: createObject(Ty: T)));
1158 } else {
1159 assert(false && "Unexpected this-capturing lambda context.");
1160 }
1161 }
1162 }
1163 } else if (MethodDecl->isImplicitObjectMemberFunction()) {
1164 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
1165 auto &ThisLoc =
1166 cast<RecordStorageLocation>(Val&: createStorageLocation(Type: ThisPointeeType));
1167 setThisPointeeStorageLocation(ThisLoc);
1168 // Initialize fields of `*this` with values, but only if we're not
1169 // analyzing a constructor; after all, it's the constructor's job to do
1170 // this (and we want to be able to test that).
1171 if (!isa<CXXConstructorDecl>(Val: MethodDecl))
1172 initializeFieldsWithValues(Loc&: ThisLoc);
1173 }
1174 }
1175
1176 // We do this below the handling of `CXXMethodDecl` above so that we can
1177 // be sure that the storage location for `this` has been set.
1178 ResultObjectMap =
1179 std::make_shared<PrValueToResultObject>(args: buildResultObjectMap(
1180 DACtx, FuncDecl: InitialTargetFunc, ThisPointeeLoc: getThisPointeeStorageLocation(),
1181 LocForRecordReturnVal));
1182
1183 ThisExprOverrides =
1184 std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap(
1185 FuncDecl: InitialTargetFunc, ThisPointeeLoc: getThisPointeeStorageLocation(),
1186 ResultObjectMap: *ResultObjectMap));
1187}
1188
1189// FIXME: Add support for resetting globals after function calls to enable the
1190// implementation of sound analyses.
1191
1192void Environment::initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced) {
1193 // These have to be added before the lines that follow to ensure that
1194 // `create*` work correctly for structs.
1195 DACtx->addModeledFields(Fields: Referenced.Fields);
1196
1197 for (const VarDecl *D : Referenced.Globals) {
1198 if (getStorageLocation(D: *D) != nullptr)
1199 continue;
1200
1201 // We don't run transfer functions on the initializers of global variables,
1202 // so they won't be associated with a value or storage location. We
1203 // therefore intentionally don't pass an initializer to `createObject()`; in
1204 // particular, this ensures that `createObject()` will initialize the fields
1205 // of record-type variables with values.
1206 setStorageLocation(D: *D, Loc&: createObject(D: *D, InitExpr: nullptr));
1207 }
1208
1209 for (const FunctionDecl *FD : Referenced.Functions) {
1210 if (getStorageLocation(D: *FD) != nullptr)
1211 continue;
1212 auto &Loc = createStorageLocation(D: *FD);
1213 setStorageLocation(D: *FD, Loc);
1214 }
1215}
1216
1217Environment Environment::fork() const {
1218 Environment Copy(*this);
1219 Copy.BoolState->onFork();
1220 return Copy;
1221}
1222
1223bool Environment::canDescend(unsigned MaxDepth,
1224 const FunctionDecl *Callee) const {
1225 return CallStack.size() < MaxDepth && !llvm::is_contained(Range: CallStack, Element: Callee);
1226}
1227
1228Environment Environment::pushCall(const CallExpr *Call) const {
1229 Environment Env(*this);
1230
1231 if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Val: Call)) {
1232 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
1233 if (!isa<CXXThisExpr>(Val: Arg))
1234 Env.ThisPointeeLoc =
1235 cast<RecordStorageLocation>(Val: getStorageLocation(E: *Arg));
1236 // Otherwise (when the argument is `this`), retain the current
1237 // environment's `ThisPointeeLoc`.
1238 }
1239 }
1240
1241 if (Call->getType()->isRecordType() && Call->isPRValue())
1242 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(RecordPRValue: *Call);
1243
1244 Env.pushCallInternal(FuncDecl: Call->getDirectCallee(),
1245 Args: llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
1246
1247 return Env;
1248}
1249
1250Environment Environment::pushCall(const CXXConstructExpr *Call) const {
1251 Environment Env(*this);
1252
1253 Env.ThisPointeeLoc = &Env.getResultObjectLocation(RecordPRValue: *Call);
1254 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(RecordPRValue: *Call);
1255
1256 Env.pushCallInternal(FuncDecl: Call->getConstructor(),
1257 Args: llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
1258
1259 return Env;
1260}
1261
1262void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
1263 ArrayRef<const Expr *> Args) {
1264 // Canonicalize to the definition of the function. This ensures that we're
1265 // putting arguments into the same `ParamVarDecl`s` that the callee will later
1266 // be retrieving them from.
1267 assert(FuncDecl->getDefinition() != nullptr);
1268 FuncDecl = FuncDecl->getDefinition();
1269
1270 CallStack.push_back(x: FuncDecl);
1271
1272 initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(FD: *FuncDecl));
1273
1274 const auto *ParamIt = FuncDecl->param_begin();
1275
1276 // FIXME: Parameters don't always map to arguments 1:1; examples include
1277 // overloaded operators implemented as member functions, and parameter packs.
1278 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
1279 assert(ParamIt != FuncDecl->param_end());
1280 const VarDecl *Param = *ParamIt;
1281 setStorageLocation(D: *Param, Loc&: createObject(D: *Param, InitExpr: Args[ArgIndex]));
1282 }
1283
1284 ResultObjectMap = std::make_shared<PrValueToResultObject>(
1285 args: buildResultObjectMap(DACtx, FuncDecl, ThisPointeeLoc: getThisPointeeStorageLocation(),
1286 LocForRecordReturnVal));
1287 ThisExprOverrides =
1288 std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap(
1289 FuncDecl, ThisPointeeLoc: getThisPointeeStorageLocation(), ResultObjectMap: *ResultObjectMap));
1290}
1291
1292void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
1293 // We ignore some entries of `CalleeEnv`:
1294 // - `DACtx` because is already the same in both
1295 // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or
1296 // `ThisPointeeLoc` because they don't apply to us.
1297 // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the
1298 // callee's local scope, so when popping that scope, we do not propagate
1299 // the maps.
1300 this->LocToVal = std::move(CalleeEnv.LocToVal);
1301 this->BoolState = CalleeEnv.BoolState->clone();
1302
1303 if (Call->isGLValue()) {
1304 if (CalleeEnv.ReturnLoc != nullptr)
1305 setStorageLocation(E: *Call, Loc&: *CalleeEnv.ReturnLoc);
1306 } else if (!Call->getType()->isVoidType()) {
1307 if (CalleeEnv.ReturnVal != nullptr)
1308 setValue(E: *Call, Val&: *CalleeEnv.ReturnVal);
1309 }
1310}
1311
1312void Environment::popCall(const CXXConstructExpr *Call,
1313 const Environment &CalleeEnv) {
1314 // See also comment in `popCall(const CallExpr *, const Environment &)` above.
1315 this->LocToVal = std::move(CalleeEnv.LocToVal);
1316 this->BoolState = CalleeEnv.BoolState->clone();
1317}
1318
1319bool Environment::equivalentTo(const Environment &Other,
1320 Environment::ValueModel &Model) const {
1321 assert(DACtx == Other.DACtx);
1322
1323 if (ReturnVal != Other.ReturnVal)
1324 return false;
1325
1326 if (ReturnLoc != Other.ReturnLoc)
1327 return false;
1328
1329 if (LocForRecordReturnVal != Other.LocForRecordReturnVal)
1330 return false;
1331
1332 if (ThisPointeeLoc != Other.ThisPointeeLoc)
1333 return false;
1334
1335 if (DeclToLoc != Other.DeclToLoc)
1336 return false;
1337
1338 if (ExprToLoc != Other.ExprToLoc)
1339 return false;
1340
1341 if (!compareKeyToValueMaps(Map1: ExprToVal, Map2: Other.ExprToVal, Env1: *this, Env2: Other, Model))
1342 return false;
1343
1344 if (!compareKeyToValueMaps(Map1: LocToVal, Map2: Other.LocToVal, Env1: *this, Env2: Other, Model))
1345 return false;
1346 if (!BoolState->isEquivalentTo(Other: *Other.BoolState))
1347 return false;
1348
1349 return true;
1350}
1351
1352LatticeEffect Environment::widen(const Environment &PrevEnv,
1353 Environment::ValueModel &Model) {
1354 assert(DACtx == PrevEnv.DACtx);
1355 assert(ReturnVal == PrevEnv.ReturnVal);
1356 assert(ReturnLoc == PrevEnv.ReturnLoc);
1357 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);
1358 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
1359 assert(ThisExprOverrides == PrevEnv.ThisExprOverrides);
1360 assert(CallStack == PrevEnv.CallStack);
1361 assert(ResultObjectMap == PrevEnv.ResultObjectMap);
1362 assert(InitialTargetFunc == PrevEnv.InitialTargetFunc);
1363 assert(InitialTargetStmt == PrevEnv.InitialTargetStmt);
1364
1365 auto Effect = LatticeEffect::Unchanged;
1366
1367 // By the API, `PrevEnv` is a previous version of the environment for the same
1368 // block, so we have some guarantees about its shape. In particular, it will
1369 // be the result of a join or widen operation on previous values for this
1370 // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that
1371 // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain
1372 // this property here, we don't need change their current values to widen.
1373 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
1374 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
1375 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
1376
1377 ExprToVal = widenKeyToValueMap(CurMap: ExprToVal, PrevMap: PrevEnv.ExprToVal, CurEnv&: *this, PrevEnv,
1378 Model, Effect);
1379
1380 LocToVal = widenKeyToValueMap(CurMap: LocToVal, PrevMap: PrevEnv.LocToVal, CurEnv&: *this, PrevEnv,
1381 Model, Effect);
1382 if (BoolState->widen(PrevModel: *PrevEnv.BoolState) == LatticeEffect::Changed)
1383 Effect = LatticeEffect::Changed;
1384 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
1385 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
1386 ExprToVal.size() != PrevEnv.ExprToVal.size() ||
1387 LocToVal.size() != PrevEnv.LocToVal.size())
1388 Effect = LatticeEffect::Changed;
1389
1390 return Effect;
1391}
1392
1393Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
1394 Environment::ValueModel &Model,
1395 ExprJoinBehavior ExprBehavior) {
1396 assert(EnvA.DACtx == EnvB.DACtx);
1397 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal);
1398 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
1399 assert(EnvA.ThisExprOverrides == EnvB.ThisExprOverrides);
1400 assert(EnvA.CallStack == EnvB.CallStack);
1401 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap);
1402 assert(EnvA.InitialTargetFunc == EnvB.InitialTargetFunc);
1403 assert(EnvA.InitialTargetStmt == EnvB.InitialTargetStmt);
1404
1405 Environment JoinedEnv(*EnvA.DACtx);
1406
1407 JoinedEnv.CallStack = EnvA.CallStack;
1408 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;
1409 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;
1410 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
1411 JoinedEnv.ThisExprOverrides = EnvA.ThisExprOverrides;
1412 JoinedEnv.InitialTargetFunc = EnvA.InitialTargetFunc;
1413 JoinedEnv.InitialTargetStmt = EnvA.InitialTargetStmt;
1414
1415 const FunctionDecl *Func = EnvA.getCurrentFunc();
1416 if (!Func) {
1417 JoinedEnv.ReturnVal = nullptr;
1418 } else {
1419 JoinedEnv.ReturnVal =
1420 joinValues(Ty: Func->getReturnType(), Val1: EnvA.ReturnVal, Env1: EnvA, Val2: EnvB.ReturnVal,
1421 Env2: EnvB, JoinedEnv, Model);
1422 }
1423
1424 if (EnvA.ReturnLoc == EnvB.ReturnLoc)
1425 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
1426 else
1427 JoinedEnv.ReturnLoc = nullptr;
1428
1429 JoinedEnv.DeclToLoc = intersectDeclToLoc(DeclToLoc1: EnvA.DeclToLoc, DeclToLoc2: EnvB.DeclToLoc);
1430
1431 JoinedEnv.BoolState->join(ModelA: *EnvA.BoolState, ModelB: *EnvB.BoolState);
1432
1433 JoinedEnv.LocToVal =
1434 joinLocToVal(LocToVal: EnvA.LocToVal, LocToVal2: EnvB.LocToVal, Env1: EnvA, Env2: EnvB, JoinedEnv, Model);
1435
1436 if (ExprBehavior == KeepExprState) {
1437 JoinedEnv.ExprToVal = joinExprMaps(Map1: EnvA.ExprToVal, Map2: EnvB.ExprToVal);
1438 JoinedEnv.ExprToLoc = joinExprMaps(Map1: EnvA.ExprToLoc, Map2: EnvB.ExprToLoc);
1439 }
1440
1441 return JoinedEnv;
1442}
1443
1444Value *Environment::joinValues(QualType Ty, Value *Val1,
1445 const Environment &Env1, Value *Val2,
1446 const Environment &Env2, Environment &JoinedEnv,
1447 Environment::ValueModel &Model) {
1448 if (Val1 == nullptr || Val2 == nullptr)
1449 // We can't say anything about the joined value -- even if one of the values
1450 // is non-null, we don't want to simply propagate it, because it would be
1451 // too specific: Because the other value is null, that means we have no
1452 // information at all about the value (i.e. the value is unconstrained).
1453 return nullptr;
1454
1455 if (areEquivalentValues(Val1: *Val1, Val2: *Val2))
1456 // Arbitrarily return one of the two values.
1457 return Val1;
1458
1459 return joinDistinctValues(Type: Ty, Val1&: *Val1, Env1, Val2&: *Val2, Env2, JoinedEnv, Model);
1460}
1461
1462StorageLocation &Environment::createStorageLocation(QualType Type) {
1463 return DACtx->createStorageLocation(Type);
1464}
1465
1466StorageLocation &Environment::createStorageLocation(const ValueDecl &D) {
1467 // Evaluated declarations are always assigned the same storage locations to
1468 // ensure that the environment stabilizes across loop iterations. Storage
1469 // locations for evaluated declarations are stored in the analysis context.
1470 return DACtx->getStableStorageLocation(D);
1471}
1472
1473StorageLocation &Environment::createStorageLocation(const Expr &E) {
1474 // Evaluated expressions are always assigned the same storage locations to
1475 // ensure that the environment stabilizes across loop iterations. Storage
1476 // locations for evaluated expressions are stored in the analysis context.
1477 return DACtx->getStableStorageLocation(E);
1478}
1479
1480void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
1481 assert(!DeclToLoc.contains(&D));
1482 // The only kinds of declarations that may have a "variable" storage location
1483 // are declarations of reference type and `BindingDecl`. For all other
1484 // declaration, the storage location should be the stable storage location
1485 // returned by `createStorageLocation()`.
1486 assert(D.getType()->isReferenceType() || isa<BindingDecl>(D) ||
1487 &Loc == &createStorageLocation(D));
1488 DeclToLoc[&D] = &Loc;
1489}
1490
1491StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
1492 auto It = DeclToLoc.find(Val: &D);
1493 if (It == DeclToLoc.end())
1494 return nullptr;
1495
1496 StorageLocation *Loc = It->second;
1497
1498 return Loc;
1499}
1500
1501void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(Val: &D); }
1502
1503void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
1504 // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
1505 // but we still want to be able to associate a `StorageLocation` with them,
1506 // so allow these as an exception.
1507 assert(E.isGLValue() ||
1508 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
1509 const Expr &CanonE = ignoreCFGOmittedNodes(E);
1510 assert(!ExprToLoc.contains(&CanonE));
1511 ExprToLoc[&CanonE] = &Loc;
1512}
1513
1514StorageLocation *Environment::getStorageLocation(const Expr &E) const {
1515 // See comment in `setStorageLocation()`.
1516 assert(E.isGLValue() ||
1517 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
1518 auto It = ExprToLoc.find(Val: &ignoreCFGOmittedNodes(E));
1519 return It == ExprToLoc.end() ? nullptr : &*It->second;
1520}
1521
1522RecordStorageLocation &
1523Environment::getResultObjectLocation(const Expr &RecordPRValue) const {
1524 assert(RecordPRValue.getType()->isRecordType());
1525 assert(RecordPRValue.isPRValue());
1526
1527 assert(ResultObjectMap != nullptr);
1528 RecordStorageLocation *Loc = ResultObjectMap->lookup(Val: &RecordPRValue);
1529 assert(Loc != nullptr);
1530 // In release builds, use the "stable" storage location if the map lookup
1531 // failed.
1532 if (Loc == nullptr)
1533 return cast<RecordStorageLocation>(
1534 Val&: DACtx->getStableStorageLocation(E: RecordPRValue));
1535 return *Loc;
1536}
1537
1538PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
1539 return DACtx->getOrCreateNullPointerValue(PointeeType);
1540}
1541
1542void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
1543 QualType Type) {
1544 llvm::DenseSet<QualType> Visited;
1545 int CreatedValuesCount = 0;
1546 initializeFieldsWithValues(Loc, Type, Visited, Depth: 0, CreatedValuesCount);
1547 if (CreatedValuesCount > MaxCompositeValueSize) {
1548 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
1549 << '\n';
1550 }
1551}
1552
1553void Environment::setValue(const StorageLocation &Loc, Value &Val) {
1554 // Records should not be associated with values.
1555 assert(!isa<RecordStorageLocation>(Loc));
1556 LocToVal[&Loc] = &Val;
1557}
1558
1559void Environment::setValue(const Expr &E, Value &Val) {
1560 const Expr &CanonE = ignoreCFGOmittedNodes(E);
1561
1562 assert(CanonE.isPRValue());
1563 // Records should not be associated with values.
1564 assert(!CanonE.getType()->isRecordType());
1565 ExprToVal[&CanonE] = &Val;
1566}
1567
1568Value *Environment::getValue(const StorageLocation &Loc) const {
1569 // Records should not be associated with values.
1570 assert(!isa<RecordStorageLocation>(Loc));
1571 return LocToVal.lookup(Key: &Loc);
1572}
1573
1574Value *Environment::getValue(const ValueDecl &D) const {
1575 auto *Loc = getStorageLocation(D);
1576 if (Loc == nullptr)
1577 return nullptr;
1578 return getValue(Loc: *Loc);
1579}
1580
1581Value *Environment::getValue(const Expr &E) const {
1582 // Records should not be associated with values.
1583 assert(!E.getType()->isRecordType());
1584
1585 if (E.isPRValue()) {
1586 auto It = ExprToVal.find(Key: &ignoreCFGOmittedNodes(E));
1587 return It == ExprToVal.end() ? nullptr : It->second;
1588 }
1589
1590 auto It = ExprToLoc.find(Val: &ignoreCFGOmittedNodes(E));
1591 if (It == ExprToLoc.end())
1592 return nullptr;
1593 return getValue(Loc: *It->second);
1594}
1595
1596Value *Environment::createValue(QualType Type) {
1597 llvm::DenseSet<QualType> Visited;
1598 int CreatedValuesCount = 0;
1599 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
1600 CreatedValuesCount);
1601 if (CreatedValuesCount > MaxCompositeValueSize) {
1602 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
1603 << '\n';
1604 }
1605 return Val;
1606}
1607
1608Value *Environment::createValueUnlessSelfReferential(
1609 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
1610 int &CreatedValuesCount) {
1611 assert(!Type.isNull());
1612 assert(!Type->isReferenceType());
1613 assert(!Type->isRecordType());
1614
1615 // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
1616 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
1617 Depth > MaxCompositeValueDepth)
1618 return nullptr;
1619
1620 if (Type->isBooleanType()) {
1621 CreatedValuesCount++;
1622 return &makeAtomicBoolValue();
1623 }
1624
1625 if (Type->isIntegerType()) {
1626 // FIXME: consider instead `return nullptr`, given that we do nothing useful
1627 // with integers, and so distinguishing them serves no purpose, but could
1628 // prevent convergence.
1629 CreatedValuesCount++;
1630 return &arena().create<IntegerValue>();
1631 }
1632
1633 if (Type->isPointerType()) {
1634 CreatedValuesCount++;
1635 QualType PointeeType = Type->getPointeeType();
1636 StorageLocation &PointeeLoc =
1637 createLocAndMaybeValue(Ty: PointeeType, Visited, Depth, CreatedValuesCount);
1638
1639 return &arena().create<PointerValue>(args&: PointeeLoc);
1640 }
1641
1642 return nullptr;
1643}
1644
1645StorageLocation &
1646Environment::createLocAndMaybeValue(QualType Ty,
1647 llvm::DenseSet<QualType> &Visited,
1648 int Depth, int &CreatedValuesCount) {
1649 if (!Visited.insert(V: Ty.getCanonicalType()).second)
1650 return createStorageLocation(Type: Ty.getNonReferenceType());
1651 llvm::scope_exit EraseVisited(
1652 [&Visited, Ty] { Visited.erase(V: Ty.getCanonicalType()); });
1653
1654 Ty = Ty.getNonReferenceType();
1655
1656 if (Ty->isRecordType()) {
1657 auto &Loc = cast<RecordStorageLocation>(Val&: createStorageLocation(Type: Ty));
1658 initializeFieldsWithValues(Loc, Type: Ty, Visited, Depth, CreatedValuesCount);
1659 return Loc;
1660 }
1661
1662 StorageLocation &Loc = createStorageLocation(Type: Ty);
1663
1664 if (Value *Val = createValueUnlessSelfReferential(Type: Ty, Visited, Depth,
1665 CreatedValuesCount))
1666 setValue(Loc, Val&: *Val);
1667
1668 return Loc;
1669}
1670
1671void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
1672 QualType Type,
1673 llvm::DenseSet<QualType> &Visited,
1674 int Depth,
1675 int &CreatedValuesCount) {
1676 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {
1677 if (FieldType->isRecordType()) {
1678 auto &FieldRecordLoc = cast<RecordStorageLocation>(Val&: FieldLoc);
1679 initializeFieldsWithValues(Loc&: FieldRecordLoc, Type: FieldRecordLoc.getType(),
1680 Visited, Depth: Depth + 1, CreatedValuesCount);
1681 } else {
1682 if (getValue(Loc: FieldLoc) != nullptr)
1683 return;
1684 if (!Visited.insert(V: FieldType.getCanonicalType()).second)
1685 return;
1686 if (Value *Val = createValueUnlessSelfReferential(
1687 Type: FieldType, Visited, Depth: Depth + 1, CreatedValuesCount))
1688 setValue(Loc: FieldLoc, Val&: *Val);
1689 Visited.erase(V: FieldType.getCanonicalType());
1690 }
1691 };
1692
1693 for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
1694 assert(Field != nullptr);
1695 QualType FieldType = Field->getType();
1696
1697 if (FieldType->isReferenceType()) {
1698 Loc.setChild(D: *Field,
1699 Loc: &createLocAndMaybeValue(Ty: FieldType, Visited, Depth: Depth + 1,
1700 CreatedValuesCount));
1701 } else {
1702 StorageLocation *FieldLoc = Loc.getChild(D: *Field);
1703 assert(FieldLoc != nullptr);
1704 initField(FieldType, *FieldLoc);
1705 }
1706 }
1707 for (const auto &[FieldName, FieldType] : DACtx->getSyntheticFields(Type)) {
1708 // Synthetic fields cannot have reference type, so we don't need to deal
1709 // with this case.
1710 assert(!FieldType->isReferenceType());
1711 initField(FieldType, Loc.getSyntheticField(Name: FieldName));
1712 }
1713}
1714
1715StorageLocation &Environment::createObjectInternal(const ValueDecl *D,
1716 QualType Ty,
1717 const Expr *InitExpr) {
1718 if (Ty->isReferenceType()) {
1719 // Although variables of reference type always need to be initialized, it
1720 // can happen that we can't see the initializer, so `InitExpr` may still
1721 // be null.
1722 if (InitExpr) {
1723 if (auto *InitExprLoc = getStorageLocation(E: *InitExpr))
1724 return *InitExprLoc;
1725 }
1726
1727 // Even though we have an initializer, we might not get an
1728 // InitExprLoc, for example if the InitExpr is a CallExpr for which we
1729 // don't have a function body. In this case, we just invent a storage
1730 // location and value -- it's the best we can do.
1731 return createObjectInternal(D, Ty: Ty.getNonReferenceType(), InitExpr: nullptr);
1732 }
1733
1734 StorageLocation &Loc =
1735 D ? createStorageLocation(D: *D) : createStorageLocation(Type: Ty);
1736
1737 if (Ty->isRecordType()) {
1738 auto &RecordLoc = cast<RecordStorageLocation>(Val&: Loc);
1739 if (!InitExpr)
1740 initializeFieldsWithValues(Loc&: RecordLoc);
1741 } else {
1742 Value *Val = nullptr;
1743 if (InitExpr)
1744 // In the (few) cases where an expression is intentionally
1745 // "uninterpreted", `InitExpr` is not associated with a value. There are
1746 // two ways to handle this situation: propagate the status, so that
1747 // uninterpreted initializers result in uninterpreted variables, or
1748 // provide a default value. We choose the latter so that later refinements
1749 // of the variable can be used for reasoning about the surrounding code.
1750 // For this reason, we let this case be handled by the `createValue()`
1751 // call below.
1752 //
1753 // FIXME. If and when we interpret all language cases, change this to
1754 // assert that `InitExpr` is interpreted, rather than supplying a
1755 // default value (assuming we don't update the environment API to return
1756 // references).
1757 Val = getValue(E: *InitExpr);
1758 if (!Val)
1759 Val = createValue(Type: Ty);
1760 if (Val)
1761 setValue(Loc, Val&: *Val);
1762 }
1763
1764 return Loc;
1765}
1766
1767void Environment::assume(const Formula &F) { BoolState->assume(F); }
1768
1769bool Environment::proves(const Formula &F) const {
1770 return BoolState->proves(F);
1771}
1772
1773bool Environment::allows(const Formula &F) const {
1774 return BoolState->allows(F);
1775}
1776
1777void Environment::dump(raw_ostream &OS) const {
1778 llvm::DenseMap<const StorageLocation *, std::string> LocToName;
1779 if (LocForRecordReturnVal != nullptr)
1780 LocToName[LocForRecordReturnVal] = "(returned record)";
1781 if (ThisPointeeLoc != nullptr)
1782 LocToName[ThisPointeeLoc] = "this";
1783
1784 OS << "DeclToLoc:\n";
1785 for (auto [D, L] : DeclToLoc) {
1786 auto Iter = LocToName.insert(KV: {L, D->getNameAsString()}).first;
1787 OS << " [" << Iter->second << ", " << L << "]\n";
1788 }
1789 OS << "ExprToLoc:\n";
1790 for (auto [E, L] : ExprToLoc)
1791 OS << " [" << E << ", " << L << "]\n";
1792
1793 OS << "ExprToVal:\n";
1794 for (auto [E, V] : ExprToVal)
1795 OS << " [" << E << ", " << V << ": " << *V << "]\n";
1796
1797 OS << "LocToVal:\n";
1798 for (auto [L, V] : LocToVal) {
1799 OS << " [" << L;
1800 if (auto Iter = LocToName.find(Val: L); Iter != LocToName.end())
1801 OS << " (" << Iter->second << ")";
1802 OS << ", " << V << ": " << *V << "]\n";
1803 }
1804
1805 if (const FunctionDecl *Func = getCurrentFunc()) {
1806 if (Func->getReturnType()->isReferenceType()) {
1807 OS << "ReturnLoc: " << ReturnLoc;
1808 if (auto Iter = LocToName.find(Val: ReturnLoc); Iter != LocToName.end())
1809 OS << " (" << Iter->second << ")";
1810 OS << "\n";
1811 } else if (Func->getReturnType()->isRecordType() ||
1812 isa<CXXConstructorDecl>(Val: Func)) {
1813 OS << "LocForRecordReturnVal: " << LocForRecordReturnVal << "\n";
1814 } else if (!Func->getReturnType()->isVoidType()) {
1815 if (ReturnVal == nullptr)
1816 OS << "ReturnVal: nullptr\n";
1817 else
1818 OS << "ReturnVal: " << *ReturnVal << "\n";
1819 }
1820
1821 if (isa<CXXMethodDecl>(Val: Func)) {
1822 OS << "ThisPointeeLoc: " << ThisPointeeLoc << "\n";
1823 }
1824 }
1825
1826 OS << "\n";
1827 BoolState->dump(OS);
1828}
1829
1830void Environment::dump() const { dump(OS&: llvm::dbgs()); }
1831
1832Environment::PrValueToResultObject Environment::buildResultObjectMap(
1833 DataflowAnalysisContext *DACtx, const FunctionDecl *FuncDecl,
1834 RecordStorageLocation *ThisPointeeLoc,
1835 RecordStorageLocation *LocForRecordReturnVal) {
1836 assert(FuncDecl->doesThisDeclarationHaveABody());
1837
1838 PrValueToResultObject Map = buildResultObjectMap(
1839 DACtx, S: FuncDecl->getBody(), ThisPointeeLoc, LocForRecordReturnVal);
1840
1841 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1842 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: FuncDecl))
1843 Visitor.traverseConstructorInits(Ctor, ThisPointeeLoc);
1844
1845 return Map;
1846}
1847
1848Environment::PrValueToResultObject Environment::buildResultObjectMap(
1849 DataflowAnalysisContext *DACtx, Stmt *S,
1850 RecordStorageLocation *ThisPointeeLoc,
1851 RecordStorageLocation *LocForRecordReturnVal) {
1852 PrValueToResultObject Map;
1853 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1854 Visitor.TraverseStmt(S);
1855 return Map;
1856}
1857
1858Environment::ThisExprOverridesMap Environment::buildThisExprOverridesMap(
1859 const FunctionDecl *FuncDecl, RecordStorageLocation *ThisPointeeLoc,
1860 const PrValueToResultObject &ResultObjectMap) {
1861 assert(FuncDecl->doesThisDeclarationHaveABody());
1862
1863 ThisExprOverridesMap Map = buildThisExprOverridesMap(
1864 S: FuncDecl->getBody(), ThisPointeeLoc, ResultObjectMap);
1865
1866 ThisExprOverridesVisitor Visitor(ThisPointeeLoc, ResultObjectMap, Map);
1867 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: FuncDecl)) {
1868 Visitor.traverseConstructorInits(Ctor);
1869 }
1870 return Map;
1871}
1872
1873Environment::ThisExprOverridesMap Environment::buildThisExprOverridesMap(
1874 Stmt *S, RecordStorageLocation *ThisPointeeLoc,
1875 const PrValueToResultObject &ResultObjectMap) {
1876 ThisExprOverridesMap Map;
1877 ThisExprOverridesVisitor Visitor(ThisPointeeLoc, ResultObjectMap, Map);
1878 Visitor.TraverseStmt(S);
1879 return Map;
1880}
1881
1882RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
1883 const Environment &Env) {
1884 Expr *ImplicitObject = MCE.getImplicitObjectArgument();
1885 if (ImplicitObject == nullptr)
1886 return nullptr;
1887 if (ImplicitObject->getType()->isPointerType()) {
1888 if (auto *Val = Env.get<PointerValue>(E: *ImplicitObject))
1889 return &cast<RecordStorageLocation>(Val&: Val->getPointeeLoc());
1890 return nullptr;
1891 }
1892 return cast_or_null<RecordStorageLocation>(
1893 Val: Env.getStorageLocation(E: *ImplicitObject));
1894}
1895
1896RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
1897 const Environment &Env) {
1898 Expr *Base = ME.getBase();
1899 if (Base == nullptr)
1900 return nullptr;
1901 if (ME.isArrow()) {
1902 if (auto *Val = Env.get<PointerValue>(E: *Base))
1903 return &cast<RecordStorageLocation>(Val&: Val->getPointeeLoc());
1904 return nullptr;
1905 }
1906 return Env.get<RecordStorageLocation>(E: *Base);
1907}
1908
1909} // namespace dataflow
1910} // namespace clang
1911