1 //===-- DataflowEnvironment.cpp ---------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
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"
38 #define DEBUG_TYPE "dataflow"
43 // FIXME: convert these to parameters of the analysis or environment. Current
44 // settings have been experimentaly validated, but only for a particular
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
});
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
) {
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
);
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
) {
89 case Value::Kind::Integer
:
90 case Value::Kind::Pointer
:
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
:
110 case ComparisonResult::Different
:
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.
138 // std::optional<bool> o;
140 // if (o.has_value())
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());
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
);
157 Model
.join(Type
, Val1
, Env1
, Val2
, Env2
, *JoinedVal
, JoinedEnv
);
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
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
))
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
) {
215 assert(K
!= nullptr);
217 Value
*Val
= Entry
.second
;
218 assert(Val
!= nullptr);
220 auto It
= Map2
.find(K
);
221 if (It
== Map2
.end())
223 assert(It
->second
!= nullptr);
225 if (!areEquivalentValues(*Val
, *It
->second
) &&
226 !compareDistinctValues(K
->getType(), *Val
, Env1
, *It
->second
, Env2
,
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())
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
});
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
) {
273 assert(K
!= nullptr);
275 Value
*Val
= Entry
.second
;
276 assert(Val
!= nullptr);
278 auto PrevIt
= PrevMap
.find(K
);
279 if (PrevIt
== PrevMap
.end())
281 assert(PrevIt
->second
!= nullptr);
283 if (areEquivalentValues(*Val
, *PrevIt
->second
)) {
284 WidenedMap
.insert({K
, Val
});
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
;
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
{
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
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(
348 &cast
<RecordStorageLocation
>(DACtx
.getStableStorageLocation(*VD
)));
352 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr
*MTE
) override
{
353 if (MTE
->getType()->isRecordType())
354 PropagateResultObject(
356 &cast
<RecordStorageLocation
>(DACtx
.getStableStorageLocation(*MTE
)));
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
);
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
)));
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()) {
409 // Ensure we don't propagate the result object if we hit this in a
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
)) {
428 if (auto *Op
= dyn_cast
<BinaryOperator
>(E
);
429 Op
&& Op
->getOpcode() == BO_Cmp
) {
430 // Builtin `<=>` returns a `std::strong_ordering` object.
434 if (auto *InitList
= dyn_cast
<InitListExpr
>(E
)) {
435 if (!InitList
->isSemanticForm())
437 if (InitList
->isTransparent()) {
438 PropagateResultObject(InitList
->getInit(0), Loc
);
442 PropagateResultObjectToRecordInitList(RecordInitListHelper(InitList
),
447 if (auto *ParenInitList
= dyn_cast
<CXXParenListInitExpr
>(E
)) {
448 PropagateResultObjectToRecordInitList(RecordInitListHelper(ParenInitList
),
453 if (auto *Op
= dyn_cast
<BinaryOperator
>(E
); Op
&& Op
->isCommaOp()) {
454 PropagateResultObject(Op
->getRHS(), Loc
);
458 if (auto *Cond
= dyn_cast
<AbstractConditionalOperator
>(E
)) {
459 PropagateResultObject(Cond
->getTrueExpr(), Loc
);
460 PropagateResultObject(Cond
->getFalseExpr(), Loc
);
464 if (auto *SE
= dyn_cast
<StmtExpr
>(E
)) {
465 PropagateResultObject(cast
<Expr
>(SE
->getSubStmt()->body_back()), Loc
);
469 if (auto *DIE
= dyn_cast
<CXXDefaultInitExpr
>(E
)) {
470 PropagateResultObject(DIE
->getExpr(), Loc
);
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());
478 if (Children
.size() != 1)
481 assert(Children
.size() == 1);
482 for (Stmt
*S
: Children
)
483 PropagateResultObject(cast
<Expr
>(S
), Loc
);
487 llvm::DenseMap
<const Expr
*, RecordStorageLocation
*> &ResultObjectMap
;
488 RecordStorageLocation
*LocForRecordReturnVal
;
489 DataflowAnalysisContext
&DACtx
;
494 void Environment::initialize() {
495 if (InitialTargetStmt
== nullptr)
498 if (InitialTargetFunc
== nullptr) {
499 initFieldsGlobalsAndFuncs(getReferencedDecls(*InitialTargetStmt
));
501 std::make_shared
<PrValueToResultObject
>(buildResultObjectMap(
502 DACtx
, InitialTargetStmt
, getThisPointeeStorageLocation(),
503 /*LocForRecordReturnValue=*/nullptr));
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))));
542 assert(false && "Unexpected this-capturing lambda context.");
546 } else if (MethodDecl
->isImplicitObjectMemberFunction()) {
547 QualType ThisPointeeType
= MethodDecl
->getFunctionObjectParameterType();
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.
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)
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)
590 auto &Loc
= createStorageLocation(*FD
);
591 setStorageLocation(*FD
, Loc
);
595 Environment
Environment::fork() const {
596 Environment
Copy(*this);
597 Copy
.FlowConditionToken
= DACtx
->forkFlowCondition(FlowConditionToken
);
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
))
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()));
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()));
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
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
)
701 if (ReturnLoc
!= Other
.ReturnLoc
)
704 if (LocForRecordReturnVal
!= Other
.LocForRecordReturnVal
)
707 if (ThisPointeeLoc
!= Other
.ThisPointeeLoc
)
710 if (DeclToLoc
!= Other
.DeclToLoc
)
713 if (ExprToLoc
!= Other
.ExprToLoc
)
716 if (!compareKeyToValueMaps(ExprToVal
, Other
.ExprToVal
, *this, Other
, Model
))
719 if (!compareKeyToValueMaps(LocToVal
, Other
.LocToVal
, *this, Other
, Model
))
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
,
752 LocToVal
= widenKeyToValueMap(LocToVal
, PrevEnv
.LocToVal
, *this, PrevEnv
,
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
;
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();
785 JoinedEnv
.ReturnVal
= nullptr;
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
;
795 JoinedEnv
.ReturnLoc
= nullptr;
797 JoinedEnv
.DeclToLoc
= intersectDeclToLoc(EnvA
.DeclToLoc
, EnvB
.DeclToLoc
);
799 // FIXME: update join to detect backedges and simplify the flow condition
801 JoinedEnv
.FlowConditionToken
= EnvA
.DACtx
->joinFlowConditions(
802 EnvA
.FlowConditionToken
, EnvB
.FlowConditionToken
);
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
);
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).
826 if (areEquivalentValues(*Val1
, *Val2
))
827 // Arbitrarily return one of the two values.
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())
867 StorageLocation
*Loc
= It
->second
;
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
904 return cast
<RecordStorageLocation
>(
905 DACtx
->getStableStorageLocation(RecordPRValue
));
909 PointerValue
&Environment::getOrCreateNullPointerValue(QualType PointeeType
) {
910 return DACtx
->getOrCreateNullPointerValue(PointeeType
);
913 void Environment::initializeFieldsWithValues(RecordStorageLocation
&Loc
,
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
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
);
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());
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())
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,
972 if (CreatedValuesCount
> MaxCompositeValueSize
) {
973 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
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
)
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
);
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
);
1033 StorageLocation
&Loc
= createStorageLocation(Ty
);
1035 if (Value
*Val
= createValueUnlessSelfReferential(Ty
, Visited
, Depth
,
1036 CreatedValuesCount
))
1037 setValue(Loc
, *Val
);
1042 void Environment::initializeFieldsWithValues(RecordStorageLocation
&Loc
,
1044 llvm::DenseSet
<QualType
> &Visited
,
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
);
1053 if (getValue(FieldLoc
) != nullptr)
1055 if (!Visited
.insert(FieldType
.getCanonicalType()).second
)
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
));
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
1081 assert(!FieldType
->isReferenceType());
1082 initField(FieldType
, Loc
.getSyntheticField(FieldName
));
1086 StorageLocation
&Environment::createObjectInternal(const ValueDecl
*D
,
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
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
);
1111 initializeFieldsWithValues(RecordLoc
);
1113 Value
*Val
= nullptr;
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()`
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
1128 Val
= getValue(*InitExpr
);
1130 Val
= createValue(Ty
);
1132 setValue(Loc
, *Val
);
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
) {
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
<< ")";
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";
1191 OS
<< "ReturnVal: " << *ReturnVal
<< "\n";
1194 if (isa
<CXXMethodDecl
>(Func
)) {
1195 OS
<< "ThisPointeeLoc: " << ThisPointeeLoc
<< "\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
);
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
);
1231 RecordStorageLocation
*getImplicitObjectLocation(const CXXMemberCallExpr
&MCE
,
1232 const Environment
&Env
) {
1233 Expr
*ImplicitObject
= MCE
.getImplicitObjectArgument();
1234 if (ImplicitObject
== nullptr)
1236 if (ImplicitObject
->getType()->isPointerType()) {
1237 if (auto *Val
= Env
.get
<PointerValue
>(*ImplicitObject
))
1238 return &cast
<RecordStorageLocation
>(Val
->getPointeeLoc());
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)
1251 if (auto *Val
= Env
.get
<PointerValue
>(*Base
))
1252 return &cast
<RecordStorageLocation
>(Val
->getPointeeLoc());
1255 return Env
.get
<RecordStorageLocation
>(*Base
);
1258 } // namespace dataflow
1259 } // namespace clang