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/StorageLocation.h"
26#include "clang/Analysis/FlowSensitive/Value.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/DenseSet.h"
29#include "llvm/ADT/MapVector.h"
30#include "llvm/ADT/STLExtras.h"
31#include "llvm/ADT/ScopeExit.h"
32#include "llvm/Support/ErrorHandling.h"
33#include <cassert>
34#include <memory>
35#include <stack>
36#include <utility>
37
38#define DEBUG_TYPE "dataflow"
39
40namespace clang {
41namespace dataflow {
42
43// FIXME: convert these to parameters of the analysis or environment. Current
44// settings have been experimentaly validated, but only for a particular
45// analysis.
46static constexpr int MaxCompositeValueDepth = 3;
47static constexpr int MaxCompositeValueSize = 1000;
48
49/// Returns a map consisting of key-value entries that are present in both maps.
50static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc(
51 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,
52 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) {
53 llvm::DenseMap<const ValueDecl *, StorageLocation *> Result;
54 for (auto &Entry : DeclToLoc1) {
55 auto It = DeclToLoc2.find(Val: Entry.first);
56 if (It != DeclToLoc2.end() && Entry.second == It->second)
57 Result.insert(KV: {Entry.first, Entry.second});
58 }
59 return Result;
60}
61
62// Performs a join on either `ExprToLoc` or `ExprToVal`.
63// The maps must be consistent in the sense that any entries for the same
64// expression must map to the same location / value. This is the case if we are
65// performing a join for control flow within a full-expression (which is the
66// only case when this function should be used).
67template <typename MapT>
68static MapT joinExprMaps(const MapT &Map1, const MapT &Map2) {
69 MapT Result = Map1;
70
71 for (const auto &Entry : Map2) {
72 [[maybe_unused]] auto [It, Inserted] = Result.insert(Entry);
73 // If there was an existing entry, its value should be the same as for the
74 // entry we were trying to insert.
75 assert(It->second == Entry.second);
76 }
77
78 return Result;
79}
80
81// Whether to consider equivalent two values with an unknown relation.
82//
83// FIXME: this function is a hack enabling unsoundness to support
84// convergence. Once we have widening support for the reference/pointer and
85// struct built-in models, this should be unconditionally `false` (and inlined
86// as such at its call sites).
87static bool equateUnknownValues(Value::Kind K) {
88 switch (K) {
89 case Value::Kind::Integer:
90 case Value::Kind::Pointer:
91 return true;
92 default:
93 return false;
94 }
95}
96
97static bool compareDistinctValues(QualType Type, Value &Val1,
98 const Environment &Env1, Value &Val2,
99 const Environment &Env2,
100 Environment::ValueModel &Model) {
101 // Note: Potentially costly, but, for booleans, we could check whether both
102 // can be proven equivalent in their respective environments.
103
104 // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
105 // and implement separate, join/widen specific handling for
106 // reference/pointers.
107 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
108 case ComparisonResult::Same:
109 return true;
110 case ComparisonResult::Different:
111 return false;
112 case ComparisonResult::Unknown:
113 return equateUnknownValues(K: Val1.getKind());
114 }
115 llvm_unreachable("All cases covered in switch");
116}
117
118/// Attempts to join distinct values `Val1` and `Val2` in `Env1` and `Env2`,
119/// respectively, of the same type `Type`. Joining generally produces a single
120/// value that (soundly) approximates the two inputs, although the actual
121/// meaning depends on `Model`.
122static Value *joinDistinctValues(QualType Type, Value &Val1,
123 const Environment &Env1, Value &Val2,
124 const Environment &Env2,
125 Environment &JoinedEnv,
126 Environment::ValueModel &Model) {
127 // Join distinct boolean values preserving information about the constraints
128 // in the respective path conditions.
129 if (isa<BoolValue>(Val: &Val1) && isa<BoolValue>(Val: &Val2)) {
130 // FIXME: Checking both values should be unnecessary, since they should have
131 // a consistent shape. However, right now we can end up with BoolValue's in
132 // integer-typed variables due to our incorrect handling of
133 // boolean-to-integer casts (we just propagate the BoolValue to the result
134 // of the cast). So, a join can encounter an integer in one branch but a
135 // bool in the other.
136 // For example:
137 // ```
138 // std::optional<bool> o;
139 // int x;
140 // if (o.has_value())
141 // x = o.value();
142 // ```
143 auto &Expr1 = cast<BoolValue>(Val&: Val1).formula();
144 auto &Expr2 = cast<BoolValue>(Val&: Val2).formula();
145 auto &A = JoinedEnv.arena();
146 auto &JoinedVal = A.makeAtomRef(A: A.makeAtom());
147 JoinedEnv.assume(
148 A.makeOr(LHS: A.makeAnd(LHS: A.makeAtomRef(A: Env1.getFlowConditionToken()),
149 RHS: A.makeEquals(LHS: JoinedVal, RHS: Expr1)),
150 RHS: A.makeAnd(LHS: A.makeAtomRef(A: Env2.getFlowConditionToken()),
151 RHS: A.makeEquals(LHS: JoinedVal, RHS: Expr2))));
152 return &A.makeBoolValue(JoinedVal);
153 }
154
155 Value *JoinedVal = JoinedEnv.createValue(Type);
156 if (JoinedVal)
157 Model.join(Type, Val1, Env1, Val2, Env2, JoinedVal&: *JoinedVal, JoinedEnv);
158
159 return JoinedVal;
160}
161
162static WidenResult widenDistinctValues(QualType Type, Value &Prev,
163 const Environment &PrevEnv,
164 Value &Current, Environment &CurrentEnv,
165 Environment::ValueModel &Model) {
166 // Boolean-model widening.
167 if (isa<BoolValue>(Val: Prev) && isa<BoolValue>(Val: Current)) {
168 // FIXME: Checking both values should be unnecessary, but we can currently
169 // end up with `BoolValue`s in integer-typed variables. See comment in
170 // `joinDistinctValues()` for details.
171 auto &PrevBool = cast<BoolValue>(Val&: Prev);
172 auto &CurBool = cast<BoolValue>(Val&: Current);
173
174 if (isa<TopBoolValue>(Val: Prev))
175 // Safe to return `Prev` here, because Top is never dependent on the
176 // environment.
177 return {.V: &Prev, .Effect: LatticeEffect::Unchanged};
178
179 // We may need to widen to Top, but before we do so, check whether both
180 // values are implied to be either true or false in the current environment.
181 // In that case, we can simply return a literal instead.
182 bool TruePrev = PrevEnv.proves(PrevBool.formula());
183 bool TrueCur = CurrentEnv.proves(CurBool.formula());
184 if (TruePrev && TrueCur)
185 return {.V: &CurrentEnv.getBoolLiteralValue(Value: true), .Effect: LatticeEffect::Unchanged};
186 if (!TruePrev && !TrueCur &&
187 PrevEnv.proves(PrevEnv.arena().makeNot(Val: PrevBool.formula())) &&
188 CurrentEnv.proves(CurrentEnv.arena().makeNot(Val: CurBool.formula())))
189 return {.V: &CurrentEnv.getBoolLiteralValue(Value: false), .Effect: LatticeEffect::Unchanged};
190
191 return {.V: &CurrentEnv.makeTopBoolValue(), .Effect: LatticeEffect::Changed};
192 }
193
194 // FIXME: Add other built-in model widening.
195
196 // Custom-model widening.
197 if (auto Result = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
198 return *Result;
199
200 return {.V: &Current, .Effect: equateUnknownValues(K: Prev.getKind())
201 ? LatticeEffect::Unchanged
202 : LatticeEffect::Changed};
203}
204
205// Returns whether the values in `Map1` and `Map2` compare equal for those
206// keys that `Map1` and `Map2` have in common.
207template <typename Key>
208static bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
209 const llvm::MapVector<Key, Value *> &Map2,
210 const Environment &Env1,
211 const Environment &Env2,
212 Environment::ValueModel &Model) {
213 for (auto &Entry : Map1) {
214 Key K = Entry.first;
215 assert(K != nullptr);
216
217 Value *Val = Entry.second;
218 assert(Val != nullptr);
219
220 auto It = Map2.find(K);
221 if (It == Map2.end())
222 continue;
223 assert(It->second != nullptr);
224
225 if (!areEquivalentValues(*Val, *It->second) &&
226 !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2,
227 Model))
228 return false;
229 }
230
231 return true;
232}
233
234// Perform a join on two `LocToVal` maps.
235static llvm::MapVector<const StorageLocation *, Value *>
236joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
237 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
238 const Environment &Env1, const Environment &Env2,
239 Environment &JoinedEnv, Environment::ValueModel &Model) {
240 llvm::MapVector<const StorageLocation *, Value *> Result;
241 for (auto &Entry : LocToVal) {
242 const StorageLocation *Loc = Entry.first;
243 assert(Loc != nullptr);
244
245 Value *Val = Entry.second;
246 assert(Val != nullptr);
247
248 auto It = LocToVal2.find(Key: Loc);
249 if (It == LocToVal2.end())
250 continue;
251 assert(It->second != nullptr);
252
253 if (Value *JoinedVal = Environment::joinValues(
254 Ty: Loc->getType(), Val1: Val, Env1, Val2: It->second, Env2, JoinedEnv, Model)) {
255 Result.insert(KV: {Loc, JoinedVal});
256 }
257 }
258
259 return Result;
260}
261
262// Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
263// `const StorageLocation *` or `const Expr *`.
264template <typename Key>
265static llvm::MapVector<Key, Value *>
266widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
267 const llvm::MapVector<Key, Value *> &PrevMap,
268 Environment &CurEnv, const Environment &PrevEnv,
269 Environment::ValueModel &Model, LatticeEffect &Effect) {
270 llvm::MapVector<Key, Value *> WidenedMap;
271 for (auto &Entry : CurMap) {
272 Key K = Entry.first;
273 assert(K != nullptr);
274
275 Value *Val = Entry.second;
276 assert(Val != nullptr);
277
278 auto PrevIt = PrevMap.find(K);
279 if (PrevIt == PrevMap.end())
280 continue;
281 assert(PrevIt->second != nullptr);
282
283 if (areEquivalentValues(*Val, *PrevIt->second)) {
284 WidenedMap.insert({K, Val});
285 continue;
286 }
287
288 auto [WidenedVal, ValEffect] = widenDistinctValues(
289 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model);
290 WidenedMap.insert({K, WidenedVal});
291 if (ValEffect == LatticeEffect::Changed)
292 Effect = LatticeEffect::Changed;
293 }
294
295 return WidenedMap;
296}
297
298namespace {
299
300// Visitor that builds a map from record prvalues to result objects.
301// For each result object that it encounters, it propagates the storage location
302// of the result object to all record prvalues that can initialize it.
303class ResultObjectVisitor : public AnalysisASTVisitor {
304public:
305 // `ResultObjectMap` will be filled with a map from record prvalues to result
306 // object. If this visitor will traverse a function that returns a record by
307 // value, `LocForRecordReturnVal` is the location to which this record should
308 // be written; otherwise, it is null.
309 explicit ResultObjectVisitor(
310 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap,
311 RecordStorageLocation *LocForRecordReturnVal,
312 DataflowAnalysisContext &DACtx)
313 : ResultObjectMap(ResultObjectMap),
314 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {}
315
316 // Traverse all member and base initializers of `Ctor`. This function is not
317 // called by `RecursiveASTVisitor`; it should be called manually if we are
318 // analyzing a constructor. `ThisPointeeLoc` is the storage location that
319 // `this` points to.
320 void traverseConstructorInits(const CXXConstructorDecl *Ctor,
321 RecordStorageLocation *ThisPointeeLoc) {
322 assert(ThisPointeeLoc != nullptr);
323 for (const CXXCtorInitializer *Init : Ctor->inits()) {
324 Expr *InitExpr = Init->getInit();
325 if (FieldDecl *Field = Init->getMember();
326 Field != nullptr && Field->getType()->isRecordType()) {
327 PropagateResultObject(E: InitExpr, Loc: cast<RecordStorageLocation>(
328 Val: ThisPointeeLoc->getChild(D: *Field)));
329 } else if (Init->getBaseClass()) {
330 PropagateResultObject(E: InitExpr, Loc: ThisPointeeLoc);
331 }
332
333 // Ensure that any result objects within `InitExpr` (e.g. temporaries)
334 // are also propagated to the prvalues that initialize them.
335 TraverseStmt(S: InitExpr);
336
337 // If this is a `CXXDefaultInitExpr`, also propagate any result objects
338 // within the default expression.
339 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(Val: InitExpr))
340 TraverseStmt(S: DefaultInit->getExpr());
341 }
342 }
343
344 bool VisitVarDecl(VarDecl *VD) override {
345 if (VD->getType()->isRecordType() && VD->hasInit())
346 PropagateResultObject(
347 E: VD->getInit(),
348 Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(D: *VD)));
349 return true;
350 }
351
352 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) override {
353 if (MTE->getType()->isRecordType())
354 PropagateResultObject(
355 E: MTE->getSubExpr(),
356 Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(E: *MTE)));
357 return true;
358 }
359
360 bool VisitReturnStmt(ReturnStmt *Return) override {
361 Expr *RetValue = Return->getRetValue();
362 if (RetValue != nullptr && RetValue->getType()->isRecordType() &&
363 RetValue->isPRValue())
364 PropagateResultObject(E: RetValue, Loc: LocForRecordReturnVal);
365 return true;
366 }
367
368 bool VisitExpr(Expr *E) override {
369 // Clang's AST can have record-type prvalues without a result object -- for
370 // example as full-expressions contained in a compound statement or as
371 // arguments of call expressions. We notice this if we get here and a
372 // storage location has not yet been associated with `E`. In this case,
373 // treat this as if it was a `MaterializeTemporaryExpr`.
374 if (E->isPRValue() && E->getType()->isRecordType() &&
375 !ResultObjectMap.contains(Val: E))
376 PropagateResultObject(
377 E, Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(E: *E)));
378 return true;
379 }
380
381 void
382 PropagateResultObjectToRecordInitList(const RecordInitListHelper &InitList,
383 RecordStorageLocation *Loc) {
384 for (auto [Base, Init] : InitList.base_inits()) {
385 assert(Base->getType().getCanonicalType() ==
386 Init->getType().getCanonicalType());
387
388 // Storage location for the base class is the same as that of the
389 // derived class because we "flatten" the object hierarchy and put all
390 // fields in `RecordStorageLocation` of the derived class.
391 PropagateResultObject(E: Init, Loc);
392 }
393
394 for (auto [Field, Init] : InitList.field_inits()) {
395 // Fields of non-record type are handled in
396 // `TransferVisitor::VisitInitListExpr()`.
397 if (Field->getType()->isRecordType())
398 PropagateResultObject(
399 E: Init, Loc: cast<RecordStorageLocation>(Val: Loc->getChild(D: *Field)));
400 }
401 }
402
403 // Assigns `Loc` as the result object location of `E`, then propagates the
404 // location to all lower-level prvalues that initialize the same object as
405 // `E` (or one of its base classes or member variables).
406 void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) {
407 if (!E->isPRValue() || !E->getType()->isRecordType()) {
408 assert(false);
409 // Ensure we don't propagate the result object if we hit this in a
410 // release build.
411 return;
412 }
413
414 ResultObjectMap[E] = Loc;
415
416 // The following AST node kinds are "original initializers": They are the
417 // lowest-level AST node that initializes a given object, and nothing
418 // below them can initialize the same object (or part of it).
419 if (isa<CXXConstructExpr>(Val: E) || isa<CallExpr>(Val: E) || isa<LambdaExpr>(Val: E) ||
420 isa<CXXDefaultArgExpr>(Val: E) || isa<CXXStdInitializerListExpr>(Val: E) ||
421 isa<AtomicExpr>(Val: E) || isa<CXXInheritedCtorInitExpr>(Val: E) ||
422 // We treat `BuiltinBitCastExpr` as an "original initializer" too as
423 // it may not even be casting from a record type -- and even if it is,
424 // the two objects are in general of unrelated type.
425 isa<BuiltinBitCastExpr>(Val: E) ||
426 // This covers both co_await and co_yield.
427 // The result object of co_await is <op>.await_resume(), but there is
428 // no expression for that to propagate to.
429 // co_yield is equivalent to `co_await promise.yield_value(expr)`.
430 isa<CoroutineSuspendExpr>(Val: E)) {
431 return;
432 }
433 if (auto *Op = dyn_cast<BinaryOperator>(Val: E);
434 Op && Op->getOpcode() == BO_Cmp) {
435 // Builtin `<=>` returns a `std::strong_ordering` object.
436 return;
437 }
438
439 if (auto *InitList = dyn_cast<InitListExpr>(Val: E)) {
440 if (!InitList->isSemanticForm())
441 return;
442 if (InitList->isTransparent()) {
443 PropagateResultObject(E: InitList->getInit(Init: 0), Loc);
444 return;
445 }
446
447 PropagateResultObjectToRecordInitList(InitList: RecordInitListHelper(InitList),
448 Loc);
449 return;
450 }
451
452 if (auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(Val: E)) {
453 PropagateResultObjectToRecordInitList(InitList: RecordInitListHelper(ParenInitList),
454 Loc);
455 return;
456 }
457
458 if (auto *Op = dyn_cast<BinaryOperator>(Val: E); Op && Op->isCommaOp()) {
459 PropagateResultObject(E: Op->getRHS(), Loc);
460 return;
461 }
462
463 if (auto *Cond = dyn_cast<AbstractConditionalOperator>(Val: E)) {
464 PropagateResultObject(E: Cond->getTrueExpr(), Loc);
465 PropagateResultObject(E: Cond->getFalseExpr(), Loc);
466 return;
467 }
468
469 if (auto *SE = dyn_cast<StmtExpr>(Val: E)) {
470 PropagateResultObject(E: cast<Expr>(Val: SE->getSubStmt()->body_back()), Loc);
471 return;
472 }
473
474 if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: E)) {
475 PropagateResultObject(E: DIE->getExpr(), Loc);
476 return;
477 }
478
479 // All other expression nodes that propagate a record prvalue should have
480 // exactly one child.
481 SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end());
482 LLVM_DEBUG({
483 if (Children.size() != 1)
484 E->dump();
485 });
486 assert(Children.size() == 1);
487 for (Stmt *S : Children)
488 PropagateResultObject(E: cast<Expr>(Val: S), Loc);
489 }
490
491private:
492 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
493 RecordStorageLocation *LocForRecordReturnVal;
494 DataflowAnalysisContext &DACtx;
495};
496
497/// A visitor that finds `CXXThisExpr` that can refer to an object other than
498/// the `this` of a member function.
499class ThisExprOverridesVisitor : public AnalysisASTVisitor {
500 using BaseVisitor = AnalysisASTVisitor;
501
502public:
503 ThisExprOverridesVisitor(
504 RecordStorageLocation *ThisPointeeLoc,
505 const llvm::DenseMap<const Expr *, RecordStorageLocation *>
506 &ResultObjectMap,
507 llvm::DenseMap<const CXXThisExpr *, RecordStorageLocation *>
508 &ThisExprOverrides)
509 : DefaultThisPointeeLoc(ThisPointeeLoc), ResultObjectMap(ResultObjectMap),
510 ThisExprOverrides(ThisExprOverrides) {
511 ThisLocations.push(x: DefaultThisPointeeLoc);
512 }
513
514 void traverseConstructorInits(const CXXConstructorDecl *Ctor) {
515 for (const CXXCtorInitializer *Init : Ctor->inits()) {
516 TraverseStmt(S: Init->getInit());
517 }
518 }
519
520 bool TraverseInitListExpr(InitListExpr *ILE) override {
521 if (!ILE->isSemanticForm() || ILE->isTransparent()) {
522 BaseVisitor::TraverseInitListExpr(S: ILE);
523 return true;
524 }
525 bool IsRecordType = ILE->getType()->isRecordType();
526 if (IsRecordType) {
527 auto It = ResultObjectMap.find(Val: ILE);
528 if (It == ResultObjectMap.end()) {
529 llvm_unreachable("InitListExpr not found in ResultObjectMap");
530 return false;
531 }
532 InitListLocations.push(x: It->second);
533 }
534 BaseVisitor::TraverseInitListExpr(S: ILE);
535 if (IsRecordType)
536 InitListLocations.pop();
537 return true;
538 }
539
540 bool TraverseCXXParenListInitExpr(CXXParenListInitExpr *PLIE) override {
541 auto It = ResultObjectMap.find(Val: PLIE);
542 if (It == ResultObjectMap.end()) {
543 llvm_unreachable("CXXParenListInitExpr not found in ResultObjectMap");
544 return false;
545 }
546 InitListLocations.push(x: It->second);
547 BaseVisitor::TraverseCXXParenListInitExpr(S: PLIE);
548 InitListLocations.pop();
549 return true;
550 }
551
552 bool TraverseCXXDefaultInitExpr(CXXDefaultInitExpr *CDIE) override {
553 bool HasInitListLocations = !InitListLocations.empty();
554 if (HasInitListLocations) {
555 auto *Loc = InitListLocations.top();
556 ThisLocations.push(x: Loc);
557 }
558 BaseVisitor::TraverseCXXDefaultInitExpr(S: CDIE);
559 if (HasInitListLocations)
560 ThisLocations.pop();
561 return true;
562 }
563
564 bool TraverseCXXThisExpr(CXXThisExpr *This) override {
565 assert(!ThisLocations.empty());
566 auto *Loc = ThisLocations.top();
567 if (Loc != DefaultThisPointeeLoc)
568 ThisExprOverrides[This] = Loc;
569 return true;
570 }
571
572 // The default `this` pointee location (null if not in a member function).
573 RecordStorageLocation *DefaultThisPointeeLoc;
574 // Locations to use for `this`, with the most recent scope on top.
575 std::stack<RecordStorageLocation *> ThisLocations;
576 // A stack of nested InitListExpr and CXXParenListInitExprs storage
577 // locations that may be used for `this` if we enter a CXXDefaultInitExpr.
578 std::stack<RecordStorageLocation *> InitListLocations;
579 // Map to look up a storage location, e.g., when encountering an
580 // InitListExpr.
581 const llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap;
582 // The visitor will update this map with locations to use for `this`,
583 // if different from `DefaultThisPointeeLoc`.
584 llvm::DenseMap<const CXXThisExpr *, RecordStorageLocation *>
585 &ThisExprOverrides;
586};
587
588} // namespace
589
590void Environment::initialize() {
591 if (InitialTargetStmt == nullptr)
592 return;
593
594 if (InitialTargetFunc == nullptr) {
595 initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(S: *InitialTargetStmt));
596 ResultObjectMap =
597 std::make_shared<PrValueToResultObject>(args: buildResultObjectMap(
598 DACtx, S: InitialTargetStmt, ThisPointeeLoc: getThisPointeeStorageLocation(),
599 /*LocForRecordReturnValue=*/LocForRecordReturnVal: nullptr));
600
601 ThisExprOverrides =
602 std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap(
603 S: InitialTargetStmt, ThisPointeeLoc: getThisPointeeStorageLocation(),
604 ResultObjectMap: *ResultObjectMap));
605 return;
606 }
607
608 initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(FD: *InitialTargetFunc));
609
610 for (const auto *ParamDecl : InitialTargetFunc->parameters()) {
611 assert(ParamDecl != nullptr);
612 setStorageLocation(D: *ParamDecl, Loc&: createObject(D: *ParamDecl, InitExpr: nullptr));
613 }
614
615 if (InitialTargetFunc->getReturnType()->isRecordType())
616 LocForRecordReturnVal = &cast<RecordStorageLocation>(
617 Val&: createStorageLocation(Type: InitialTargetFunc->getReturnType()));
618
619 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(Val: InitialTargetFunc)) {
620 auto *Parent = MethodDecl->getParent();
621 assert(Parent != nullptr);
622
623 if (Parent->isLambda()) {
624 for (const auto &Capture : Parent->captures()) {
625 if (Capture.capturesVariable()) {
626 const auto *VarDecl = Capture.getCapturedVar();
627 assert(VarDecl != nullptr);
628 setStorageLocation(D: *VarDecl, Loc&: createObject(D: *VarDecl, InitExpr: nullptr));
629 } else if (Capture.capturesThis()) {
630 if (auto *Ancestor = InitialTargetFunc->getNonClosureAncestor()) {
631 const auto *SurroundingMethodDecl = cast<CXXMethodDecl>(Val: Ancestor);
632 QualType ThisPointeeType =
633 SurroundingMethodDecl->getFunctionObjectParameterType();
634 setThisPointeeStorageLocation(
635 cast<RecordStorageLocation>(Val&: createObject(Ty: ThisPointeeType)));
636 } else if (auto *FieldBeingInitialized =
637 dyn_cast<FieldDecl>(Val: Parent->getLambdaContextDecl())) {
638 // This is in a field initializer, rather than a method.
639 const RecordDecl *RD = FieldBeingInitialized->getParent();
640 const ASTContext &Ctx = RD->getASTContext();
641 CanQualType T = Ctx.getCanonicalTagType(TD: RD);
642 setThisPointeeStorageLocation(
643 cast<RecordStorageLocation>(Val&: createObject(Ty: T)));
644 } else {
645 assert(false && "Unexpected this-capturing lambda context.");
646 }
647 }
648 }
649 } else if (MethodDecl->isImplicitObjectMemberFunction()) {
650 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
651 auto &ThisLoc =
652 cast<RecordStorageLocation>(Val&: createStorageLocation(Type: ThisPointeeType));
653 setThisPointeeStorageLocation(ThisLoc);
654 // Initialize fields of `*this` with values, but only if we're not
655 // analyzing a constructor; after all, it's the constructor's job to do
656 // this (and we want to be able to test that).
657 if (!isa<CXXConstructorDecl>(Val: MethodDecl))
658 initializeFieldsWithValues(Loc&: ThisLoc);
659 }
660 }
661
662 // We do this below the handling of `CXXMethodDecl` above so that we can
663 // be sure that the storage location for `this` has been set.
664 ResultObjectMap =
665 std::make_shared<PrValueToResultObject>(args: buildResultObjectMap(
666 DACtx, FuncDecl: InitialTargetFunc, ThisPointeeLoc: getThisPointeeStorageLocation(),
667 LocForRecordReturnVal));
668
669 ThisExprOverrides =
670 std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap(
671 FuncDecl: InitialTargetFunc, ThisPointeeLoc: getThisPointeeStorageLocation(),
672 ResultObjectMap: *ResultObjectMap));
673}
674
675// FIXME: Add support for resetting globals after function calls to enable the
676// implementation of sound analyses.
677
678void Environment::initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced) {
679 // These have to be added before the lines that follow to ensure that
680 // `create*` work correctly for structs.
681 DACtx->addModeledFields(Fields: Referenced.Fields);
682
683 for (const VarDecl *D : Referenced.Globals) {
684 if (getStorageLocation(D: *D) != nullptr)
685 continue;
686
687 // We don't run transfer functions on the initializers of global variables,
688 // so they won't be associated with a value or storage location. We
689 // therefore intentionally don't pass an initializer to `createObject()`; in
690 // particular, this ensures that `createObject()` will initialize the fields
691 // of record-type variables with values.
692 setStorageLocation(D: *D, Loc&: createObject(D: *D, InitExpr: nullptr));
693 }
694
695 for (const FunctionDecl *FD : Referenced.Functions) {
696 if (getStorageLocation(D: *FD) != nullptr)
697 continue;
698 auto &Loc = createStorageLocation(D: *FD);
699 setStorageLocation(D: *FD, Loc);
700 }
701}
702
703Environment Environment::fork() const {
704 Environment Copy(*this);
705 Copy.FlowConditionToken = DACtx->forkFlowCondition(Token: FlowConditionToken);
706 return Copy;
707}
708
709bool Environment::canDescend(unsigned MaxDepth,
710 const FunctionDecl *Callee) const {
711 return CallStack.size() < MaxDepth && !llvm::is_contained(Range: CallStack, Element: Callee);
712}
713
714Environment Environment::pushCall(const CallExpr *Call) const {
715 Environment Env(*this);
716
717 if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Val: Call)) {
718 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
719 if (!isa<CXXThisExpr>(Val: Arg))
720 Env.ThisPointeeLoc =
721 cast<RecordStorageLocation>(Val: getStorageLocation(E: *Arg));
722 // Otherwise (when the argument is `this`), retain the current
723 // environment's `ThisPointeeLoc`.
724 }
725 }
726
727 if (Call->getType()->isRecordType() && Call->isPRValue())
728 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(RecordPRValue: *Call);
729
730 Env.pushCallInternal(FuncDecl: Call->getDirectCallee(),
731 Args: llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
732
733 return Env;
734}
735
736Environment Environment::pushCall(const CXXConstructExpr *Call) const {
737 Environment Env(*this);
738
739 Env.ThisPointeeLoc = &Env.getResultObjectLocation(RecordPRValue: *Call);
740 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(RecordPRValue: *Call);
741
742 Env.pushCallInternal(FuncDecl: Call->getConstructor(),
743 Args: llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
744
745 return Env;
746}
747
748void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
749 ArrayRef<const Expr *> Args) {
750 // Canonicalize to the definition of the function. This ensures that we're
751 // putting arguments into the same `ParamVarDecl`s` that the callee will later
752 // be retrieving them from.
753 assert(FuncDecl->getDefinition() != nullptr);
754 FuncDecl = FuncDecl->getDefinition();
755
756 CallStack.push_back(x: FuncDecl);
757
758 initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(FD: *FuncDecl));
759
760 const auto *ParamIt = FuncDecl->param_begin();
761
762 // FIXME: Parameters don't always map to arguments 1:1; examples include
763 // overloaded operators implemented as member functions, and parameter packs.
764 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
765 assert(ParamIt != FuncDecl->param_end());
766 const VarDecl *Param = *ParamIt;
767 setStorageLocation(D: *Param, Loc&: createObject(D: *Param, InitExpr: Args[ArgIndex]));
768 }
769
770 ResultObjectMap = std::make_shared<PrValueToResultObject>(
771 args: buildResultObjectMap(DACtx, FuncDecl, ThisPointeeLoc: getThisPointeeStorageLocation(),
772 LocForRecordReturnVal));
773 ThisExprOverrides =
774 std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap(
775 FuncDecl, ThisPointeeLoc: getThisPointeeStorageLocation(), ResultObjectMap: *ResultObjectMap));
776}
777
778void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
779 // We ignore some entries of `CalleeEnv`:
780 // - `DACtx` because is already the same in both
781 // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or
782 // `ThisPointeeLoc` because they don't apply to us.
783 // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the
784 // callee's local scope, so when popping that scope, we do not propagate
785 // the maps.
786 this->LocToVal = std::move(CalleeEnv.LocToVal);
787 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
788
789 if (Call->isGLValue()) {
790 if (CalleeEnv.ReturnLoc != nullptr)
791 setStorageLocation(E: *Call, Loc&: *CalleeEnv.ReturnLoc);
792 } else if (!Call->getType()->isVoidType()) {
793 if (CalleeEnv.ReturnVal != nullptr)
794 setValue(E: *Call, Val&: *CalleeEnv.ReturnVal);
795 }
796}
797
798void Environment::popCall(const CXXConstructExpr *Call,
799 const Environment &CalleeEnv) {
800 // See also comment in `popCall(const CallExpr *, const Environment &)` above.
801 this->LocToVal = std::move(CalleeEnv.LocToVal);
802 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
803}
804
805bool Environment::equivalentTo(const Environment &Other,
806 Environment::ValueModel &Model) const {
807 assert(DACtx == Other.DACtx);
808
809 if (ReturnVal != Other.ReturnVal)
810 return false;
811
812 if (ReturnLoc != Other.ReturnLoc)
813 return false;
814
815 if (LocForRecordReturnVal != Other.LocForRecordReturnVal)
816 return false;
817
818 if (ThisPointeeLoc != Other.ThisPointeeLoc)
819 return false;
820
821 if (DeclToLoc != Other.DeclToLoc)
822 return false;
823
824 if (ExprToLoc != Other.ExprToLoc)
825 return false;
826
827 if (!compareKeyToValueMaps(Map1: ExprToVal, Map2: Other.ExprToVal, Env1: *this, Env2: Other, Model))
828 return false;
829
830 if (!compareKeyToValueMaps(Map1: LocToVal, Map2: Other.LocToVal, Env1: *this, Env2: Other, Model))
831 return false;
832
833 return true;
834}
835
836LatticeEffect Environment::widen(const Environment &PrevEnv,
837 Environment::ValueModel &Model) {
838 assert(DACtx == PrevEnv.DACtx);
839 assert(ReturnVal == PrevEnv.ReturnVal);
840 assert(ReturnLoc == PrevEnv.ReturnLoc);
841 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal);
842 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
843 assert(ThisExprOverrides == PrevEnv.ThisExprOverrides);
844 assert(CallStack == PrevEnv.CallStack);
845 assert(ResultObjectMap == PrevEnv.ResultObjectMap);
846 assert(InitialTargetFunc == PrevEnv.InitialTargetFunc);
847 assert(InitialTargetStmt == PrevEnv.InitialTargetStmt);
848
849 auto Effect = LatticeEffect::Unchanged;
850
851 // By the API, `PrevEnv` is a previous version of the environment for the same
852 // block, so we have some guarantees about its shape. In particular, it will
853 // be the result of a join or widen operation on previous values for this
854 // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that
855 // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain
856 // this property here, we don't need change their current values to widen.
857 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
858 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
859 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
860
861 ExprToVal = widenKeyToValueMap(CurMap: ExprToVal, PrevMap: PrevEnv.ExprToVal, CurEnv&: *this, PrevEnv,
862 Model, Effect);
863
864 LocToVal = widenKeyToValueMap(CurMap: LocToVal, PrevMap: PrevEnv.LocToVal, CurEnv&: *this, PrevEnv,
865 Model, Effect);
866 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
867 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
868 ExprToVal.size() != PrevEnv.ExprToVal.size() ||
869 LocToVal.size() != PrevEnv.LocToVal.size())
870 Effect = LatticeEffect::Changed;
871
872 return Effect;
873}
874
875Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
876 Environment::ValueModel &Model,
877 ExprJoinBehavior ExprBehavior) {
878 assert(EnvA.DACtx == EnvB.DACtx);
879 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal);
880 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
881 assert(EnvA.ThisExprOverrides == EnvB.ThisExprOverrides);
882 assert(EnvA.CallStack == EnvB.CallStack);
883 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap);
884 assert(EnvA.InitialTargetFunc == EnvB.InitialTargetFunc);
885 assert(EnvA.InitialTargetStmt == EnvB.InitialTargetStmt);
886
887 Environment JoinedEnv(*EnvA.DACtx);
888
889 JoinedEnv.CallStack = EnvA.CallStack;
890 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap;
891 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal;
892 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
893 JoinedEnv.ThisExprOverrides = EnvA.ThisExprOverrides;
894 JoinedEnv.InitialTargetFunc = EnvA.InitialTargetFunc;
895 JoinedEnv.InitialTargetStmt = EnvA.InitialTargetStmt;
896
897 const FunctionDecl *Func = EnvA.getCurrentFunc();
898 if (!Func) {
899 JoinedEnv.ReturnVal = nullptr;
900 } else {
901 JoinedEnv.ReturnVal =
902 joinValues(Ty: Func->getReturnType(), Val1: EnvA.ReturnVal, Env1: EnvA, Val2: EnvB.ReturnVal,
903 Env2: EnvB, JoinedEnv, Model);
904 }
905
906 if (EnvA.ReturnLoc == EnvB.ReturnLoc)
907 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
908 else
909 JoinedEnv.ReturnLoc = nullptr;
910
911 JoinedEnv.DeclToLoc = intersectDeclToLoc(DeclToLoc1: EnvA.DeclToLoc, DeclToLoc2: EnvB.DeclToLoc);
912
913 // FIXME: update join to detect backedges and simplify the flow condition
914 // accordingly.
915 JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions(
916 FirstToken: EnvA.FlowConditionToken, SecondToken: EnvB.FlowConditionToken);
917
918 JoinedEnv.LocToVal =
919 joinLocToVal(LocToVal: EnvA.LocToVal, LocToVal2: EnvB.LocToVal, Env1: EnvA, Env2: EnvB, JoinedEnv, Model);
920
921 if (ExprBehavior == KeepExprState) {
922 JoinedEnv.ExprToVal = joinExprMaps(Map1: EnvA.ExprToVal, Map2: EnvB.ExprToVal);
923 JoinedEnv.ExprToLoc = joinExprMaps(Map1: EnvA.ExprToLoc, Map2: EnvB.ExprToLoc);
924 }
925
926 return JoinedEnv;
927}
928
929Value *Environment::joinValues(QualType Ty, Value *Val1,
930 const Environment &Env1, Value *Val2,
931 const Environment &Env2, Environment &JoinedEnv,
932 Environment::ValueModel &Model) {
933 if (Val1 == nullptr || Val2 == nullptr)
934 // We can't say anything about the joined value -- even if one of the values
935 // is non-null, we don't want to simply propagate it, because it would be
936 // too specific: Because the other value is null, that means we have no
937 // information at all about the value (i.e. the value is unconstrained).
938 return nullptr;
939
940 if (areEquivalentValues(Val1: *Val1, Val2: *Val2))
941 // Arbitrarily return one of the two values.
942 return Val1;
943
944 return joinDistinctValues(Type: Ty, Val1&: *Val1, Env1, Val2&: *Val2, Env2, JoinedEnv, Model);
945}
946
947StorageLocation &Environment::createStorageLocation(QualType Type) {
948 return DACtx->createStorageLocation(Type);
949}
950
951StorageLocation &Environment::createStorageLocation(const ValueDecl &D) {
952 // Evaluated declarations are always assigned the same storage locations to
953 // ensure that the environment stabilizes across loop iterations. Storage
954 // locations for evaluated declarations are stored in the analysis context.
955 return DACtx->getStableStorageLocation(D);
956}
957
958StorageLocation &Environment::createStorageLocation(const Expr &E) {
959 // Evaluated expressions are always assigned the same storage locations to
960 // ensure that the environment stabilizes across loop iterations. Storage
961 // locations for evaluated expressions are stored in the analysis context.
962 return DACtx->getStableStorageLocation(E);
963}
964
965void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
966 assert(!DeclToLoc.contains(&D));
967 // The only kinds of declarations that may have a "variable" storage location
968 // are declarations of reference type and `BindingDecl`. For all other
969 // declaration, the storage location should be the stable storage location
970 // returned by `createStorageLocation()`.
971 assert(D.getType()->isReferenceType() || isa<BindingDecl>(D) ||
972 &Loc == &createStorageLocation(D));
973 DeclToLoc[&D] = &Loc;
974}
975
976StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
977 auto It = DeclToLoc.find(Val: &D);
978 if (It == DeclToLoc.end())
979 return nullptr;
980
981 StorageLocation *Loc = It->second;
982
983 return Loc;
984}
985
986void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(Val: &D); }
987
988void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
989 // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
990 // but we still want to be able to associate a `StorageLocation` with them,
991 // so allow these as an exception.
992 assert(E.isGLValue() ||
993 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
994 const Expr &CanonE = ignoreCFGOmittedNodes(E);
995 assert(!ExprToLoc.contains(&CanonE));
996 ExprToLoc[&CanonE] = &Loc;
997}
998
999StorageLocation *Environment::getStorageLocation(const Expr &E) const {
1000 // See comment in `setStorageLocation()`.
1001 assert(E.isGLValue() ||
1002 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
1003 auto It = ExprToLoc.find(Val: &ignoreCFGOmittedNodes(E));
1004 return It == ExprToLoc.end() ? nullptr : &*It->second;
1005}
1006
1007RecordStorageLocation &
1008Environment::getResultObjectLocation(const Expr &RecordPRValue) const {
1009 assert(RecordPRValue.getType()->isRecordType());
1010 assert(RecordPRValue.isPRValue());
1011
1012 assert(ResultObjectMap != nullptr);
1013 RecordStorageLocation *Loc = ResultObjectMap->lookup(Val: &RecordPRValue);
1014 assert(Loc != nullptr);
1015 // In release builds, use the "stable" storage location if the map lookup
1016 // failed.
1017 if (Loc == nullptr)
1018 return cast<RecordStorageLocation>(
1019 Val&: DACtx->getStableStorageLocation(E: RecordPRValue));
1020 return *Loc;
1021}
1022
1023PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
1024 return DACtx->getOrCreateNullPointerValue(PointeeType);
1025}
1026
1027void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
1028 QualType Type) {
1029 llvm::DenseSet<QualType> Visited;
1030 int CreatedValuesCount = 0;
1031 initializeFieldsWithValues(Loc, Type, Visited, Depth: 0, CreatedValuesCount);
1032 if (CreatedValuesCount > MaxCompositeValueSize) {
1033 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
1034 << '\n';
1035 }
1036}
1037
1038void Environment::setValue(const StorageLocation &Loc, Value &Val) {
1039 // Records should not be associated with values.
1040 assert(!isa<RecordStorageLocation>(Loc));
1041 LocToVal[&Loc] = &Val;
1042}
1043
1044void Environment::setValue(const Expr &E, Value &Val) {
1045 const Expr &CanonE = ignoreCFGOmittedNodes(E);
1046
1047 assert(CanonE.isPRValue());
1048 // Records should not be associated with values.
1049 assert(!CanonE.getType()->isRecordType());
1050 ExprToVal[&CanonE] = &Val;
1051}
1052
1053Value *Environment::getValue(const StorageLocation &Loc) const {
1054 // Records should not be associated with values.
1055 assert(!isa<RecordStorageLocation>(Loc));
1056 return LocToVal.lookup(Key: &Loc);
1057}
1058
1059Value *Environment::getValue(const ValueDecl &D) const {
1060 auto *Loc = getStorageLocation(D);
1061 if (Loc == nullptr)
1062 return nullptr;
1063 return getValue(Loc: *Loc);
1064}
1065
1066Value *Environment::getValue(const Expr &E) const {
1067 // Records should not be associated with values.
1068 assert(!E.getType()->isRecordType());
1069
1070 if (E.isPRValue()) {
1071 auto It = ExprToVal.find(Key: &ignoreCFGOmittedNodes(E));
1072 return It == ExprToVal.end() ? nullptr : It->second;
1073 }
1074
1075 auto It = ExprToLoc.find(Val: &ignoreCFGOmittedNodes(E));
1076 if (It == ExprToLoc.end())
1077 return nullptr;
1078 return getValue(Loc: *It->second);
1079}
1080
1081Value *Environment::createValue(QualType Type) {
1082 llvm::DenseSet<QualType> Visited;
1083 int CreatedValuesCount = 0;
1084 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
1085 CreatedValuesCount);
1086 if (CreatedValuesCount > MaxCompositeValueSize) {
1087 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
1088 << '\n';
1089 }
1090 return Val;
1091}
1092
1093Value *Environment::createValueUnlessSelfReferential(
1094 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
1095 int &CreatedValuesCount) {
1096 assert(!Type.isNull());
1097 assert(!Type->isReferenceType());
1098 assert(!Type->isRecordType());
1099
1100 // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
1101 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
1102 Depth > MaxCompositeValueDepth)
1103 return nullptr;
1104
1105 if (Type->isBooleanType()) {
1106 CreatedValuesCount++;
1107 return &makeAtomicBoolValue();
1108 }
1109
1110 if (Type->isIntegerType()) {
1111 // FIXME: consider instead `return nullptr`, given that we do nothing useful
1112 // with integers, and so distinguishing them serves no purpose, but could
1113 // prevent convergence.
1114 CreatedValuesCount++;
1115 return &arena().create<IntegerValue>();
1116 }
1117
1118 if (Type->isPointerType()) {
1119 CreatedValuesCount++;
1120 QualType PointeeType = Type->getPointeeType();
1121 StorageLocation &PointeeLoc =
1122 createLocAndMaybeValue(Ty: PointeeType, Visited, Depth, CreatedValuesCount);
1123
1124 return &arena().create<PointerValue>(args&: PointeeLoc);
1125 }
1126
1127 return nullptr;
1128}
1129
1130StorageLocation &
1131Environment::createLocAndMaybeValue(QualType Ty,
1132 llvm::DenseSet<QualType> &Visited,
1133 int Depth, int &CreatedValuesCount) {
1134 if (!Visited.insert(V: Ty.getCanonicalType()).second)
1135 return createStorageLocation(Type: Ty.getNonReferenceType());
1136 llvm::scope_exit EraseVisited(
1137 [&Visited, Ty] { Visited.erase(V: Ty.getCanonicalType()); });
1138
1139 Ty = Ty.getNonReferenceType();
1140
1141 if (Ty->isRecordType()) {
1142 auto &Loc = cast<RecordStorageLocation>(Val&: createStorageLocation(Type: Ty));
1143 initializeFieldsWithValues(Loc, Type: Ty, Visited, Depth, CreatedValuesCount);
1144 return Loc;
1145 }
1146
1147 StorageLocation &Loc = createStorageLocation(Type: Ty);
1148
1149 if (Value *Val = createValueUnlessSelfReferential(Type: Ty, Visited, Depth,
1150 CreatedValuesCount))
1151 setValue(Loc, Val&: *Val);
1152
1153 return Loc;
1154}
1155
1156void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
1157 QualType Type,
1158 llvm::DenseSet<QualType> &Visited,
1159 int Depth,
1160 int &CreatedValuesCount) {
1161 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {
1162 if (FieldType->isRecordType()) {
1163 auto &FieldRecordLoc = cast<RecordStorageLocation>(Val&: FieldLoc);
1164 initializeFieldsWithValues(Loc&: FieldRecordLoc, Type: FieldRecordLoc.getType(),
1165 Visited, Depth: Depth + 1, CreatedValuesCount);
1166 } else {
1167 if (getValue(Loc: FieldLoc) != nullptr)
1168 return;
1169 if (!Visited.insert(V: FieldType.getCanonicalType()).second)
1170 return;
1171 if (Value *Val = createValueUnlessSelfReferential(
1172 Type: FieldType, Visited, Depth: Depth + 1, CreatedValuesCount))
1173 setValue(Loc: FieldLoc, Val&: *Val);
1174 Visited.erase(V: FieldType.getCanonicalType());
1175 }
1176 };
1177
1178 for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
1179 assert(Field != nullptr);
1180 QualType FieldType = Field->getType();
1181
1182 if (FieldType->isReferenceType()) {
1183 Loc.setChild(D: *Field,
1184 Loc: &createLocAndMaybeValue(Ty: FieldType, Visited, Depth: Depth + 1,
1185 CreatedValuesCount));
1186 } else {
1187 StorageLocation *FieldLoc = Loc.getChild(D: *Field);
1188 assert(FieldLoc != nullptr);
1189 initField(FieldType, *FieldLoc);
1190 }
1191 }
1192 for (const auto &[FieldName, FieldType] : DACtx->getSyntheticFields(Type)) {
1193 // Synthetic fields cannot have reference type, so we don't need to deal
1194 // with this case.
1195 assert(!FieldType->isReferenceType());
1196 initField(FieldType, Loc.getSyntheticField(Name: FieldName));
1197 }
1198}
1199
1200StorageLocation &Environment::createObjectInternal(const ValueDecl *D,
1201 QualType Ty,
1202 const Expr *InitExpr) {
1203 if (Ty->isReferenceType()) {
1204 // Although variables of reference type always need to be initialized, it
1205 // can happen that we can't see the initializer, so `InitExpr` may still
1206 // be null.
1207 if (InitExpr) {
1208 if (auto *InitExprLoc = getStorageLocation(E: *InitExpr))
1209 return *InitExprLoc;
1210 }
1211
1212 // Even though we have an initializer, we might not get an
1213 // InitExprLoc, for example if the InitExpr is a CallExpr for which we
1214 // don't have a function body. In this case, we just invent a storage
1215 // location and value -- it's the best we can do.
1216 return createObjectInternal(D, Ty: Ty.getNonReferenceType(), InitExpr: nullptr);
1217 }
1218
1219 StorageLocation &Loc =
1220 D ? createStorageLocation(D: *D) : createStorageLocation(Type: Ty);
1221
1222 if (Ty->isRecordType()) {
1223 auto &RecordLoc = cast<RecordStorageLocation>(Val&: Loc);
1224 if (!InitExpr)
1225 initializeFieldsWithValues(Loc&: RecordLoc);
1226 } else {
1227 Value *Val = nullptr;
1228 if (InitExpr)
1229 // In the (few) cases where an expression is intentionally
1230 // "uninterpreted", `InitExpr` is not associated with a value. There are
1231 // two ways to handle this situation: propagate the status, so that
1232 // uninterpreted initializers result in uninterpreted variables, or
1233 // provide a default value. We choose the latter so that later refinements
1234 // of the variable can be used for reasoning about the surrounding code.
1235 // For this reason, we let this case be handled by the `createValue()`
1236 // call below.
1237 //
1238 // FIXME. If and when we interpret all language cases, change this to
1239 // assert that `InitExpr` is interpreted, rather than supplying a
1240 // default value (assuming we don't update the environment API to return
1241 // references).
1242 Val = getValue(E: *InitExpr);
1243 if (!Val)
1244 Val = createValue(Type: Ty);
1245 if (Val)
1246 setValue(Loc, Val&: *Val);
1247 }
1248
1249 return Loc;
1250}
1251
1252void Environment::assume(const Formula &F) {
1253 DACtx->addFlowConditionConstraint(Token: FlowConditionToken, Constraint: F);
1254}
1255
1256bool Environment::proves(const Formula &F) const {
1257 return DACtx->flowConditionImplies(Token: FlowConditionToken, F);
1258}
1259
1260bool Environment::allows(const Formula &F) const {
1261 return DACtx->flowConditionAllows(Token: FlowConditionToken, F);
1262}
1263
1264void Environment::dump(raw_ostream &OS) const {
1265 llvm::DenseMap<const StorageLocation *, std::string> LocToName;
1266 if (LocForRecordReturnVal != nullptr)
1267 LocToName[LocForRecordReturnVal] = "(returned record)";
1268 if (ThisPointeeLoc != nullptr)
1269 LocToName[ThisPointeeLoc] = "this";
1270
1271 OS << "DeclToLoc:\n";
1272 for (auto [D, L] : DeclToLoc) {
1273 auto Iter = LocToName.insert(KV: {L, D->getNameAsString()}).first;
1274 OS << " [" << Iter->second << ", " << L << "]\n";
1275 }
1276 OS << "ExprToLoc:\n";
1277 for (auto [E, L] : ExprToLoc)
1278 OS << " [" << E << ", " << L << "]\n";
1279
1280 OS << "ExprToVal:\n";
1281 for (auto [E, V] : ExprToVal)
1282 OS << " [" << E << ", " << V << ": " << *V << "]\n";
1283
1284 OS << "LocToVal:\n";
1285 for (auto [L, V] : LocToVal) {
1286 OS << " [" << L;
1287 if (auto Iter = LocToName.find(Val: L); Iter != LocToName.end())
1288 OS << " (" << Iter->second << ")";
1289 OS << ", " << V << ": " << *V << "]\n";
1290 }
1291
1292 if (const FunctionDecl *Func = getCurrentFunc()) {
1293 if (Func->getReturnType()->isReferenceType()) {
1294 OS << "ReturnLoc: " << ReturnLoc;
1295 if (auto Iter = LocToName.find(Val: ReturnLoc); Iter != LocToName.end())
1296 OS << " (" << Iter->second << ")";
1297 OS << "\n";
1298 } else if (Func->getReturnType()->isRecordType() ||
1299 isa<CXXConstructorDecl>(Val: Func)) {
1300 OS << "LocForRecordReturnVal: " << LocForRecordReturnVal << "\n";
1301 } else if (!Func->getReturnType()->isVoidType()) {
1302 if (ReturnVal == nullptr)
1303 OS << "ReturnVal: nullptr\n";
1304 else
1305 OS << "ReturnVal: " << *ReturnVal << "\n";
1306 }
1307
1308 if (isa<CXXMethodDecl>(Val: Func)) {
1309 OS << "ThisPointeeLoc: " << ThisPointeeLoc << "\n";
1310 }
1311 }
1312
1313 OS << "\n";
1314 DACtx->dumpFlowCondition(Token: FlowConditionToken, OS);
1315}
1316
1317void Environment::dump() const { dump(OS&: llvm::dbgs()); }
1318
1319Environment::PrValueToResultObject Environment::buildResultObjectMap(
1320 DataflowAnalysisContext *DACtx, const FunctionDecl *FuncDecl,
1321 RecordStorageLocation *ThisPointeeLoc,
1322 RecordStorageLocation *LocForRecordReturnVal) {
1323 assert(FuncDecl->doesThisDeclarationHaveABody());
1324
1325 PrValueToResultObject Map = buildResultObjectMap(
1326 DACtx, S: FuncDecl->getBody(), ThisPointeeLoc, LocForRecordReturnVal);
1327
1328 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1329 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: FuncDecl))
1330 Visitor.traverseConstructorInits(Ctor, ThisPointeeLoc);
1331
1332 return Map;
1333}
1334
1335Environment::PrValueToResultObject Environment::buildResultObjectMap(
1336 DataflowAnalysisContext *DACtx, Stmt *S,
1337 RecordStorageLocation *ThisPointeeLoc,
1338 RecordStorageLocation *LocForRecordReturnVal) {
1339 PrValueToResultObject Map;
1340 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx);
1341 Visitor.TraverseStmt(S);
1342 return Map;
1343}
1344
1345Environment::ThisExprOverridesMap Environment::buildThisExprOverridesMap(
1346 const FunctionDecl *FuncDecl, RecordStorageLocation *ThisPointeeLoc,
1347 const PrValueToResultObject &ResultObjectMap) {
1348 assert(FuncDecl->doesThisDeclarationHaveABody());
1349
1350 ThisExprOverridesMap Map = buildThisExprOverridesMap(
1351 S: FuncDecl->getBody(), ThisPointeeLoc, ResultObjectMap);
1352
1353 ThisExprOverridesVisitor Visitor(ThisPointeeLoc, ResultObjectMap, Map);
1354 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: FuncDecl)) {
1355 Visitor.traverseConstructorInits(Ctor);
1356 }
1357 return Map;
1358}
1359
1360Environment::ThisExprOverridesMap Environment::buildThisExprOverridesMap(
1361 Stmt *S, RecordStorageLocation *ThisPointeeLoc,
1362 const PrValueToResultObject &ResultObjectMap) {
1363 ThisExprOverridesMap Map;
1364 ThisExprOverridesVisitor Visitor(ThisPointeeLoc, ResultObjectMap, Map);
1365 Visitor.TraverseStmt(S);
1366 return Map;
1367}
1368
1369RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
1370 const Environment &Env) {
1371 Expr *ImplicitObject = MCE.getImplicitObjectArgument();
1372 if (ImplicitObject == nullptr)
1373 return nullptr;
1374 if (ImplicitObject->getType()->isPointerType()) {
1375 if (auto *Val = Env.get<PointerValue>(E: *ImplicitObject))
1376 return &cast<RecordStorageLocation>(Val&: Val->getPointeeLoc());
1377 return nullptr;
1378 }
1379 return cast_or_null<RecordStorageLocation>(
1380 Val: Env.getStorageLocation(E: *ImplicitObject));
1381}
1382
1383RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
1384 const Environment &Env) {
1385 Expr *Base = ME.getBase();
1386 if (Base == nullptr)
1387 return nullptr;
1388 if (ME.isArrow()) {
1389 if (auto *Val = Env.get<PointerValue>(E: *Base))
1390 return &cast<RecordStorageLocation>(Val&: Val->getPointeeLoc());
1391 return nullptr;
1392 }
1393 return Env.get<RecordStorageLocation>(E: *Base);
1394}
1395
1396} // namespace dataflow
1397} // namespace clang
1398