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

source code of clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp