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