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