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