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