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"
18#include "clang/AST/Type.h"
21#include "llvm/ADT/DenseMap.h"
22#include "llvm/ADT/DenseSet.h"
23#include "llvm/ADT/MapVector.h"
24#include "llvm/ADT/STLExtras.h"
25#include "llvm/Support/ErrorHandling.h"
26#include <cassert>
27#include <utility>
28
29namespace clang {
30namespace dataflow {
31
32// FIXME: convert these to parameters of the analysis or environment. Current
33// settings have been experimentaly validated, but only for a particular
34// analysis.
35static constexpr int MaxCompositeValueDepth = 3;
36static constexpr int MaxCompositeValueSize = 1000;
37
38/// Returns a map consisting of key-value entries that are present in both maps.
39static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc(
40 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1,
41 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) {
42 llvm::DenseMap<const ValueDecl *, StorageLocation *> Result;
43 for (auto &Entry : DeclToLoc1) {
44 auto It = DeclToLoc2.find(Entry.first);
45 if (It != DeclToLoc2.end() && Entry.second == It->second)
46 Result.insert({Entry.first, Entry.second});
47 }
48 return Result;
49}
50
51// Whether to consider equivalent two values with an unknown relation.
52//
53// FIXME: this function is a hack enabling unsoundness to support
54// convergence. Once we have widening support for the reference/pointer and
55// struct built-in models, this should be unconditionally `false` (and inlined
56// as such at its call sites).
58 switch (K) {
62 return true;
63 default:
64 return false;
65 }
66}
67
69 const Environment &Env1, Value &Val2,
70 const Environment &Env2,
72 // Note: Potentially costly, but, for booleans, we could check whether both
73 // can be proven equivalent in their respective environments.
74
75 // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
76 // and implement separate, join/widen specific handling for
77 // reference/pointers.
78 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
80 return true;
82 return false;
84 return equateUnknownValues(Val1.getKind());
85 }
86 llvm_unreachable("All cases covered in switch");
87}
88
89/// Attempts to join distinct values `Val1` and `Val2` in `Env1` and `Env2`,
90/// respectively, of the same type `Type`. Joining generally produces a single
91/// value that (soundly) approximates the two inputs, although the actual
92/// meaning depends on `Model`.
94 const Environment &Env1, Value &Val2,
95 const Environment &Env2,
96 Environment &JoinedEnv,
98 // Join distinct boolean values preserving information about the constraints
99 // in the respective path conditions.
100 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
101 // FIXME: Checking both values should be unnecessary, since they should have
102 // a consistent shape. However, right now we can end up with BoolValue's in
103 // integer-typed variables due to our incorrect handling of
104 // boolean-to-integer casts (we just propagate the BoolValue to the result
105 // of the cast). So, a join can encounter an integer in one branch but a
106 // bool in the other.
107 // For example:
108 // ```
109 // std::optional<bool> o;
110 // int x;
111 // if (o.has_value())
112 // x = o.value();
113 // ```
114 auto &Expr1 = cast<BoolValue>(Val1).formula();
115 auto &Expr2 = cast<BoolValue>(Val2).formula();
116 auto &A = JoinedEnv.arena();
117 auto &JoinedVal = A.makeAtomRef(A.makeAtom());
118 JoinedEnv.assume(
119 A.makeOr(A.makeAnd(A.makeAtomRef(Env1.getFlowConditionToken()),
120 A.makeEquals(JoinedVal, Expr1)),
121 A.makeAnd(A.makeAtomRef(Env2.getFlowConditionToken()),
122 A.makeEquals(JoinedVal, Expr2))));
123 return &A.makeBoolValue(JoinedVal);
124 }
125
126 Value *JoinedVal = nullptr;
127 if (auto *RecordVal1 = dyn_cast<RecordValue>(&Val1)) {
128 auto *RecordVal2 = cast<RecordValue>(&Val2);
129
130 if (&RecordVal1->getLoc() == &RecordVal2->getLoc())
131 // `RecordVal1` and `RecordVal2` may have different properties associated
132 // with them. Create a new `RecordValue` with the same location but
133 // without any properties so that we soundly approximate both values. If a
134 // particular analysis needs to join properties, it should do so in
135 // `DataflowAnalysis::join()`.
136 JoinedVal = &JoinedEnv.create<RecordValue>(RecordVal1->getLoc());
137 else
138 // If the locations for the two records are different, need to create a
139 // completely new value.
140 JoinedVal = JoinedEnv.createValue(Type);
141 } else {
142 JoinedVal = JoinedEnv.createValue(Type);
143 }
144
145 if (JoinedVal)
146 Model.join(Type, Val1, Env1, Val2, Env2, *JoinedVal, JoinedEnv);
147
148 return JoinedVal;
149}
150
151// When widening does not change `Current`, return value will equal `&Prev`.
153 const Environment &PrevEnv, Value &Current,
154 Environment &CurrentEnv,
156 // Boolean-model widening.
157 if (auto *PrevBool = dyn_cast<BoolValue>(&Prev)) {
158 // If previous value was already Top, re-use that to (implicitly) indicate
159 // that no change occurred.
160 if (isa<TopBoolValue>(Prev))
161 return Prev;
162
163 // We may need to widen to Top, but before we do so, check whether both
164 // values are implied to be either true or false in the current environment.
165 // In that case, we can simply return a literal instead.
166 auto &CurBool = cast<BoolValue>(Current);
167 bool TruePrev = PrevEnv.proves(PrevBool->formula());
168 bool TrueCur = CurrentEnv.proves(CurBool.formula());
169 if (TruePrev && TrueCur)
170 return CurrentEnv.getBoolLiteralValue(true);
171 if (!TruePrev && !TrueCur &&
172 PrevEnv.proves(PrevEnv.arena().makeNot(PrevBool->formula())) &&
173 CurrentEnv.proves(CurrentEnv.arena().makeNot(CurBool.formula())))
174 return CurrentEnv.getBoolLiteralValue(false);
175
176 return CurrentEnv.makeTopBoolValue();
177 }
178
179 // FIXME: Add other built-in model widening.
180
181 // Custom-model widening.
182 if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
183 return *W;
184
185 return equateUnknownValues(Prev.getKind()) ? Prev : Current;
186}
187
188// Returns whether the values in `Map1` and `Map2` compare equal for those
189// keys that `Map1` and `Map2` have in common.
190template <typename Key>
191bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
192 const llvm::MapVector<Key, Value *> &Map2,
193 const Environment &Env1, const Environment &Env2,
195 for (auto &Entry : Map1) {
196 Key K = Entry.first;
197 assert(K != nullptr);
198
199 Value *Val = Entry.second;
200 assert(Val != nullptr);
201
202 auto It = Map2.find(K);
203 if (It == Map2.end())
204 continue;
205 assert(It->second != nullptr);
206
207 if (!areEquivalentValues(*Val, *It->second) &&
208 !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2,
209 Model))
210 return false;
211 }
212
213 return true;
214}
215
216// Perform a join on two `LocToVal` maps.
217static llvm::MapVector<const StorageLocation *, Value *>
218joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal,
219 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2,
220 const Environment &Env1, const Environment &Env2,
221 Environment &JoinedEnv, Environment::ValueModel &Model) {
222 llvm::MapVector<const StorageLocation *, Value *> Result;
223 for (auto &Entry : LocToVal) {
224 const StorageLocation *Loc = Entry.first;
225 assert(Loc != nullptr);
226
227 Value *Val = Entry.second;
228 assert(Val != nullptr);
229
230 auto It = LocToVal2.find(Loc);
231 if (It == LocToVal2.end())
232 continue;
233 assert(It->second != nullptr);
234
235 if (areEquivalentValues(*Val, *It->second)) {
236 Result.insert({Loc, Val});
237 continue;
238 }
239
240 if (Value *JoinedVal = joinDistinctValues(
241 Loc->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) {
242 Result.insert({Loc, JoinedVal});
243 }
244 }
245
246 return Result;
247}
248
249// Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
250// `const StorageLocation *` or `const Expr *`.
251template <typename Key>
252llvm::MapVector<Key, Value *>
253widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
254 const llvm::MapVector<Key, Value *> &PrevMap,
255 Environment &CurEnv, const Environment &PrevEnv,
257 llvm::MapVector<Key, Value *> WidenedMap;
258 for (auto &Entry : CurMap) {
259 Key K = Entry.first;
260 assert(K != nullptr);
261
262 Value *Val = Entry.second;
263 assert(Val != nullptr);
264
265 auto PrevIt = PrevMap.find(K);
266 if (PrevIt == PrevMap.end())
267 continue;
268 assert(PrevIt->second != nullptr);
269
270 if (areEquivalentValues(*Val, *PrevIt->second)) {
271 WidenedMap.insert({K, Val});
272 continue;
273 }
274
275 Value &WidenedVal = widenDistinctValues(K->getType(), *PrevIt->second,
276 PrevEnv, *Val, CurEnv, Model);
277 WidenedMap.insert({K, &WidenedVal});
278 if (&WidenedVal != PrevIt->second)
280 }
281
282 return WidenedMap;
283}
284
285/// Initializes a global storage value.
286static void insertIfGlobal(const Decl &D,
288 if (auto *V = dyn_cast<VarDecl>(&D))
289 if (V->hasGlobalStorage())
290 Vars.insert(V);
291}
292
293static void insertIfFunction(const Decl &D,
295 if (auto *FD = dyn_cast<FunctionDecl>(&D))
296 Funcs.insert(FD);
297}
298
300 // Use getCalleeDecl instead of getMethodDecl in order to handle
301 // pointer-to-member calls.
302 const auto *MethodDecl = dyn_cast_or_null<CXXMethodDecl>(C.getCalleeDecl());
303 if (!MethodDecl)
304 return nullptr;
305 auto *Body = dyn_cast_or_null<CompoundStmt>(MethodDecl->getBody());
306 if (!Body || Body->size() != 1)
307 return nullptr;
308 if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))
309 if (auto *Return = RS->getRetValue())
310 return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());
311 return nullptr;
312}
313
314static void
318 insertIfGlobal(D, Vars);
319 insertIfFunction(D, Funcs);
320 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
321 for (const auto *B : Decomp->bindings())
322 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
323 // FIXME: should we be using `E->getFoundDecl()`?
324 if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
325 Fields.insert(FD);
326}
327
328/// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields,
329/// global variables and functions that are declared in or referenced from
330/// sub-statements.
331static void
335 for (auto *Child : S.children())
336 if (Child != nullptr)
337 getFieldsGlobalsAndFuncs(*Child, Fields, Vars, Funcs);
338 if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S))
339 getFieldsGlobalsAndFuncs(*DefaultInit->getExpr(), Fields, Vars, Funcs);
340
341 if (auto *DS = dyn_cast<DeclStmt>(&S)) {
342 if (DS->isSingleDecl())
343 getFieldsGlobalsAndFuncs(*DS->getSingleDecl(), Fields, Vars, Funcs);
344 else
345 for (auto *D : DS->getDeclGroup())
346 getFieldsGlobalsAndFuncs(*D, Fields, Vars, Funcs);
347 } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
348 insertIfGlobal(*E->getDecl(), Vars);
349 insertIfFunction(*E->getDecl(), Funcs);
350 } else if (const auto *C = dyn_cast<CXXMemberCallExpr>(&S)) {
351 // If this is a method that returns a member variable but does nothing else,
352 // model the field of the return value.
354 if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl()))
355 Fields.insert(FD);
356 } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
357 // FIXME: should we be using `E->getFoundDecl()`?
358 const ValueDecl *VD = E->getMemberDecl();
359 insertIfGlobal(*VD, Vars);
360 insertIfFunction(*VD, Funcs);
361 if (const auto *FD = dyn_cast<FieldDecl>(VD))
362 Fields.insert(FD);
363 } else if (auto *InitList = dyn_cast<InitListExpr>(&S)) {
364 if (InitList->getType()->isRecordType())
365 for (const auto *FD : getFieldsForInitListExpr(InitList))
366 Fields.insert(FD);
367 }
368}
369
371 : DACtx(&DACtx),
372 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
373
375 const DeclContext &DeclCtx)
376 : Environment(DACtx) {
377 CallStack.push_back(&DeclCtx);
378}
379
381 const DeclContext *DeclCtx = getDeclCtx();
382 if (DeclCtx == nullptr)
383 return;
384
385 if (const auto *FuncDecl = dyn_cast<FunctionDecl>(DeclCtx)) {
386 assert(FuncDecl->doesThisDeclarationHaveABody());
387
388 initFieldsGlobalsAndFuncs(FuncDecl);
389
390 for (const auto *ParamDecl : FuncDecl->parameters()) {
391 assert(ParamDecl != nullptr);
392 setStorageLocation(*ParamDecl, createObject(*ParamDecl, nullptr));
393 }
394 }
395
396 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(DeclCtx)) {
397 auto *Parent = MethodDecl->getParent();
398 assert(Parent != nullptr);
399
400 if (Parent->isLambda()) {
401 for (auto Capture : Parent->captures()) {
402 if (Capture.capturesVariable()) {
403 const auto *VarDecl = Capture.getCapturedVar();
404 assert(VarDecl != nullptr);
406 } else if (Capture.capturesThis()) {
407 const auto *SurroundingMethodDecl =
408 cast<CXXMethodDecl>(DeclCtx->getNonClosureAncestor());
409 QualType ThisPointeeType =
410 SurroundingMethodDecl->getFunctionObjectParameterType();
412 cast<RecordStorageLocation>(createObject(ThisPointeeType)));
413 }
414 }
415 } else if (MethodDecl->isImplicitObjectMemberFunction()) {
416 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
418 cast<RecordStorageLocation>(createObject(ThisPointeeType)));
419 }
420 }
421}
422
423// FIXME: Add support for resetting globals after function calls to enable
424// the implementation of sound analyses.
425void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) {
426 assert(FuncDecl->doesThisDeclarationHaveABody());
427
428 FieldSet Fields;
431
432 // Look for global variable and field references in the
433 // constructor-initializers.
434 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
435 for (const auto *Init : CtorDecl->inits()) {
436 if (Init->isMemberInitializer()) {
437 Fields.insert(Init->getMember());
438 } else if (Init->isIndirectMemberInitializer()) {
439 for (const auto *I : Init->getIndirectMember()->chain())
440 Fields.insert(cast<FieldDecl>(I));
441 }
442 const Expr *E = Init->getInit();
443 assert(E != nullptr);
444 getFieldsGlobalsAndFuncs(*E, Fields, Vars, Funcs);
445 }
446 // Add all fields mentioned in default member initializers.
447 for (const FieldDecl *F : CtorDecl->getParent()->fields())
448 if (const auto *I = F->getInClassInitializer())
449 getFieldsGlobalsAndFuncs(*I, Fields, Vars, Funcs);
450 }
451 getFieldsGlobalsAndFuncs(*FuncDecl->getBody(), Fields, Vars, Funcs);
452
453 // These have to be added before the lines that follow to ensure that
454 // `create*` work correctly for structs.
455 DACtx->addModeledFields(Fields);
456
457 for (const VarDecl *D : Vars) {
458 if (getStorageLocation(*D) != nullptr)
459 continue;
460
462 }
463
464 for (const FunctionDecl *FD : Funcs) {
465 if (getStorageLocation(*FD) != nullptr)
466 continue;
467 auto &Loc = createStorageLocation(FD->getType());
468 setStorageLocation(*FD, Loc);
469 }
470}
471
473 Environment Copy(*this);
474 Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken);
475 return Copy;
476}
477
478bool Environment::canDescend(unsigned MaxDepth,
479 const DeclContext *Callee) const {
480 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
481}
482
484 Environment Env(*this);
485
486 if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
487 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
488 if (!isa<CXXThisExpr>(Arg))
489 Env.ThisPointeeLoc =
490 cast<RecordStorageLocation>(getStorageLocation(*Arg));
491 // Otherwise (when the argument is `this`), retain the current
492 // environment's `ThisPointeeLoc`.
493 }
494 }
495
496 Env.pushCallInternal(Call->getDirectCallee(),
497 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
498
499 return Env;
500}
501
503 Environment Env(*this);
504
505 Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call);
506
507 Env.pushCallInternal(Call->getConstructor(),
508 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
509
510 return Env;
511}
512
513void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
515 // Canonicalize to the definition of the function. This ensures that we're
516 // putting arguments into the same `ParamVarDecl`s` that the callee will later
517 // be retrieving them from.
518 assert(FuncDecl->getDefinition() != nullptr);
519 FuncDecl = FuncDecl->getDefinition();
520
521 CallStack.push_back(FuncDecl);
522
523 initFieldsGlobalsAndFuncs(FuncDecl);
524
525 const auto *ParamIt = FuncDecl->param_begin();
526
527 // FIXME: Parameters don't always map to arguments 1:1; examples include
528 // overloaded operators implemented as member functions, and parameter packs.
529 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
530 assert(ParamIt != FuncDecl->param_end());
531 const VarDecl *Param = *ParamIt;
532 setStorageLocation(*Param, createObject(*Param, Args[ArgIndex]));
533 }
534}
535
536void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
537 // We ignore some entries of `CalleeEnv`:
538 // - `DACtx` because is already the same in both
539 // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or
540 // `ThisPointeeLoc` because they don't apply to us.
541 // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the
542 // callee's local scope, so when popping that scope, we do not propagate
543 // the maps.
544 this->LocToVal = std::move(CalleeEnv.LocToVal);
545 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
546
547 if (Call->isGLValue()) {
548 if (CalleeEnv.ReturnLoc != nullptr)
549 setStorageLocation(*Call, *CalleeEnv.ReturnLoc);
550 } else if (!Call->getType()->isVoidType()) {
551 if (CalleeEnv.ReturnVal != nullptr)
552 setValue(*Call, *CalleeEnv.ReturnVal);
553 }
554}
555
557 const Environment &CalleeEnv) {
558 // See also comment in `popCall(const CallExpr *, const Environment &)` above.
559 this->LocToVal = std::move(CalleeEnv.LocToVal);
560 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
561
562 if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) {
563 setValue(*Call, *Val);
564 }
565}
566
568 Environment::ValueModel &Model) const {
569 assert(DACtx == Other.DACtx);
570
571 if (ReturnVal != Other.ReturnVal)
572 return false;
573
574 if (ReturnLoc != Other.ReturnLoc)
575 return false;
576
577 if (ThisPointeeLoc != Other.ThisPointeeLoc)
578 return false;
579
580 if (DeclToLoc != Other.DeclToLoc)
581 return false;
582
583 if (ExprToLoc != Other.ExprToLoc)
584 return false;
585
586 if (!compareKeyToValueMaps(ExprToVal, Other.ExprToVal, *this, Other, Model))
587 return false;
588
589 if (!compareKeyToValueMaps(LocToVal, Other.LocToVal, *this, Other, Model))
590 return false;
591
592 return true;
593}
594
597 assert(DACtx == PrevEnv.DACtx);
598 assert(ReturnVal == PrevEnv.ReturnVal);
599 assert(ReturnLoc == PrevEnv.ReturnLoc);
600 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
601 assert(CallStack == PrevEnv.CallStack);
602
603 auto Effect = LatticeJoinEffect::Unchanged;
604
605 // By the API, `PrevEnv` is a previous version of the environment for the same
606 // block, so we have some guarantees about its shape. In particular, it will
607 // be the result of a join or widen operation on previous values for this
608 // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that
609 // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain
610 // this property here, we don't need change their current values to widen.
611 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
612 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
613 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
614
615 ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv,
616 Model, Effect);
617
618 LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv,
619 Model, Effect);
620 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
621 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
622 ExprToVal.size() != PrevEnv.ExprToVal.size() ||
623 LocToVal.size() != PrevEnv.LocToVal.size())
625
626 return Effect;
627}
628
631 assert(EnvA.DACtx == EnvB.DACtx);
632 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
633 assert(EnvA.CallStack == EnvB.CallStack);
634
635 Environment JoinedEnv(*EnvA.DACtx);
636
637 JoinedEnv.CallStack = EnvA.CallStack;
638 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
639
640 if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) {
641 // `ReturnVal` might not always get set -- for example if we have a return
642 // statement of the form `return some_other_func()` and we decide not to
643 // analyze `some_other_func()`.
644 // In this case, we can't say anything about the joined return value -- we
645 // don't simply want to propagate the return value that we do have, because
646 // it might not be the correct one.
647 // This occurs for example in the test `ContextSensitiveMutualRecursion`.
648 JoinedEnv.ReturnVal = nullptr;
649 } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) {
650 JoinedEnv.ReturnVal = EnvA.ReturnVal;
651 } else {
652 assert(!EnvA.CallStack.empty());
653 // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this
654 // cast.
655 auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
656 assert(Func != nullptr);
657 if (Value *JoinedVal =
658 joinDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA,
659 *EnvB.ReturnVal, EnvB, JoinedEnv, Model))
660 JoinedEnv.ReturnVal = JoinedVal;
661 }
662
663 if (EnvA.ReturnLoc == EnvB.ReturnLoc)
664 JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
665 else
666 JoinedEnv.ReturnLoc = nullptr;
667
668 JoinedEnv.DeclToLoc = intersectDeclToLoc(EnvA.DeclToLoc, EnvB.DeclToLoc);
669
670 // FIXME: update join to detect backedges and simplify the flow condition
671 // accordingly.
672 JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions(
673 EnvA.FlowConditionToken, EnvB.FlowConditionToken);
674
675 JoinedEnv.LocToVal =
676 joinLocToVal(EnvA.LocToVal, EnvB.LocToVal, EnvA, EnvB, JoinedEnv, Model);
677
678 // We intentionally leave `JoinedEnv.ExprToLoc` and `JoinedEnv.ExprToVal`
679 // empty, as we never need to access entries in these maps outside of the
680 // basic block that sets them.
681
682 return JoinedEnv;
683}
684
686 return DACtx->createStorageLocation(Type);
687}
688
690 // Evaluated declarations are always assigned the same storage locations to
691 // ensure that the environment stabilizes across loop iterations. Storage
692 // locations for evaluated declarations are stored in the analysis context.
693 return DACtx->getStableStorageLocation(D);
694}
695
697 // Evaluated expressions are always assigned the same storage locations to
698 // ensure that the environment stabilizes across loop iterations. Storage
699 // locations for evaluated expressions are stored in the analysis context.
700 return DACtx->getStableStorageLocation(E);
701}
702
704 assert(!DeclToLoc.contains(&D));
705 DeclToLoc[&D] = &Loc;
706}
707
709 auto It = DeclToLoc.find(&D);
710 if (It == DeclToLoc.end())
711 return nullptr;
712
713 StorageLocation *Loc = It->second;
714
715 return Loc;
716}
717
718void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(&D); }
719
721 // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
722 // but we still want to be able to associate a `StorageLocation` with them,
723 // so allow these as an exception.
724 assert(E.isGLValue() ||
725 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
726 const Expr &CanonE = ignoreCFGOmittedNodes(E);
727 assert(!ExprToLoc.contains(&CanonE));
728 ExprToLoc[&CanonE] = &Loc;
729}
730
732 // See comment in `setStorageLocation()`.
733 assert(E.isGLValue() ||
734 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
735 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
736 return It == ExprToLoc.end() ? nullptr : &*It->second;
737}
738
739// Returns whether a prvalue of record type is the one that originally
740// constructs the object (i.e. it doesn't propagate it from one of its
741// children).
742static bool isOriginalRecordConstructor(const Expr &RecordPRValue) {
743 if (auto *Init = dyn_cast<InitListExpr>(&RecordPRValue))
744 return !Init->isSemanticForm() || !Init->isTransparent();
745 return isa<CXXConstructExpr>(RecordPRValue) || isa<CallExpr>(RecordPRValue) ||
746 isa<LambdaExpr>(RecordPRValue) ||
747 isa<CXXDefaultInitExpr>(RecordPRValue) ||
748 // The framework currently does not propagate the objects created in
749 // the two branches of a `ConditionalOperator` because there is no way
750 // to reconcile their storage locations, which are different. We
751 // therefore claim that the `ConditionalOperator` is the expression
752 // that originally constructs the object.
753 // Ultimately, this will be fixed by propagating locations down from
754 // the result object, rather than up from the original constructor as
755 // we do now (see also the FIXME in the documentation for
756 // `getResultObjectLocation()`).
757 isa<ConditionalOperator>(RecordPRValue);
758}
759
760RecordStorageLocation &
761Environment::getResultObjectLocation(const Expr &RecordPRValue) const {
762 assert(RecordPRValue.getType()->isRecordType());
763 assert(RecordPRValue.isPRValue());
764
765 // Returns a storage location that we can use if assertions fail.
766 auto FallbackForAssertFailure =
767 [this, &RecordPRValue]() -> RecordStorageLocation & {
768 return cast<RecordStorageLocation>(
769 DACtx->getStableStorageLocation(RecordPRValue));
770 };
771
772 if (isOriginalRecordConstructor(RecordPRValue)) {
773 auto *Val = cast_or_null<RecordValue>(getValue(RecordPRValue));
774 // The builtin transfer function should have created a `RecordValue` for all
775 // original record constructors.
776 assert(Val);
777 if (!Val)
778 return FallbackForAssertFailure();
779 return Val->getLoc();
780 }
781
782 if (auto *Op = dyn_cast<BinaryOperator>(&RecordPRValue);
783 Op && Op->isCommaOp()) {
784 return getResultObjectLocation(*Op->getRHS());
785 }
786
787 // All other expression nodes that propagate a record prvalue should have
788 // exactly one child.
789 llvm::SmallVector<const Stmt *> children(RecordPRValue.child_begin(),
790 RecordPRValue.child_end());
791 assert(children.size() == 1);
792 if (children.empty())
793 return FallbackForAssertFailure();
794
795 return getResultObjectLocation(*cast<Expr>(children[0]));
796}
797
799 return DACtx->getOrCreateNullPointerValue(PointeeType);
800}
801
803 assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc);
804
805 LocToVal[&Loc] = &Val;
806}
807
808void Environment::setValue(const Expr &E, Value &Val) {
809 const Expr &CanonE = ignoreCFGOmittedNodes(E);
810
811 if (auto *RecordVal = dyn_cast<RecordValue>(&Val)) {
812 assert(isOriginalRecordConstructor(CanonE) ||
813 &RecordVal->getLoc() == &getResultObjectLocation(CanonE));
814 }
815
816 assert(CanonE.isPRValue());
817 ExprToVal[&CanonE] = &Val;
818}
819
821 return LocToVal.lookup(&Loc);
822}
823
825 auto *Loc = getStorageLocation(D);
826 if (Loc == nullptr)
827 return nullptr;
828 return getValue(*Loc);
829}
830
832 if (E.isPRValue()) {
833 auto It = ExprToVal.find(&ignoreCFGOmittedNodes(E));
834 return It == ExprToVal.end() ? nullptr : It->second;
835 }
836
837 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
838 if (It == ExprToLoc.end())
839 return nullptr;
840 return getValue(*It->second);
841}
842
845 int CreatedValuesCount = 0;
846 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
847 CreatedValuesCount);
848 if (CreatedValuesCount > MaxCompositeValueSize) {
849 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
850 << '\n';
851 }
852 return Val;
853}
854
855Value *Environment::createValueUnlessSelfReferential(
857 int &CreatedValuesCount) {
858 assert(!Type.isNull());
859 assert(!Type->isReferenceType());
860
861 // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
862 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
864 return nullptr;
865
866 if (Type->isBooleanType()) {
867 CreatedValuesCount++;
868 return &makeAtomicBoolValue();
869 }
870
871 if (Type->isIntegerType()) {
872 // FIXME: consider instead `return nullptr`, given that we do nothing useful
873 // with integers, and so distinguishing them serves no purpose, but could
874 // prevent convergence.
875 CreatedValuesCount++;
876 return &arena().create<IntegerValue>();
877 }
878
879 if (Type->isPointerType()) {
880 CreatedValuesCount++;
881 QualType PointeeType = Type->getPointeeType();
882 StorageLocation &PointeeLoc =
883 createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount);
884
885 return &arena().create<PointerValue>(PointeeLoc);
886 }
887
888 if (Type->isRecordType()) {
889 CreatedValuesCount++;
890 auto &Loc = cast<RecordStorageLocation>(createStorageLocation(Type));
891 initializeFieldsWithValues(Loc, Visited, Depth, CreatedValuesCount);
892
893 return &refreshRecordValue(Loc, *this);
894 }
895
896 return nullptr;
897}
898
899StorageLocation &
900Environment::createLocAndMaybeValue(QualType Ty,
902 int Depth, int &CreatedValuesCount) {
903 if (!Visited.insert(Ty.getCanonicalType()).second)
904 return createStorageLocation(Ty.getNonReferenceType());
905 Value *Val = createValueUnlessSelfReferential(
906 Ty.getNonReferenceType(), Visited, Depth, CreatedValuesCount);
907 Visited.erase(Ty.getCanonicalType());
908
909 Ty = Ty.getNonReferenceType();
910
911 if (Val == nullptr)
912 return createStorageLocation(Ty);
913
914 if (Ty->isRecordType())
915 return cast<RecordValue>(Val)->getLoc();
916
917 StorageLocation &Loc = createStorageLocation(Ty);
918 setValue(Loc, *Val);
919 return Loc;
920}
921
922void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc,
924 int Depth,
925 int &CreatedValuesCount) {
926 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) {
927 if (FieldType->isRecordType()) {
928 auto &FieldRecordLoc = cast<RecordStorageLocation>(FieldLoc);
929 setValue(FieldRecordLoc, create<RecordValue>(FieldRecordLoc));
930 initializeFieldsWithValues(FieldRecordLoc, Visited, Depth + 1,
931 CreatedValuesCount);
932 } else {
933 if (!Visited.insert(FieldType.getCanonicalType()).second)
934 return;
935 if (Value *Val = createValueUnlessSelfReferential(
936 FieldType, Visited, Depth + 1, CreatedValuesCount))
937 setValue(FieldLoc, *Val);
938 Visited.erase(FieldType.getCanonicalType());
939 }
940 };
941
942 for (const auto &[Field, FieldLoc] : Loc.children()) {
943 assert(Field != nullptr);
944 QualType FieldType = Field->getType();
945
946 if (FieldType->isReferenceType()) {
947 Loc.setChild(*Field,
948 &createLocAndMaybeValue(FieldType, Visited, Depth + 1,
949 CreatedValuesCount));
950 } else {
951 assert(FieldLoc != nullptr);
952 initField(FieldType, *FieldLoc);
953 }
954 }
955 for (const auto &[FieldName, FieldLoc] : Loc.synthetic_fields()) {
956 assert(FieldLoc != nullptr);
957 QualType FieldType = FieldLoc->getType();
958
959 // Synthetic fields cannot have reference type, so we don't need to deal
960 // with this case.
961 assert(!FieldType->isReferenceType());
962 initField(FieldType, Loc.getSyntheticField(FieldName));
963 }
964}
965
966StorageLocation &Environment::createObjectInternal(const ValueDecl *D,
967 QualType Ty,
968 const Expr *InitExpr) {
969 if (Ty->isReferenceType()) {
970 // Although variables of reference type always need to be initialized, it
971 // can happen that we can't see the initializer, so `InitExpr` may still
972 // be null.
973 if (InitExpr) {
974 if (auto *InitExprLoc = getStorageLocation(*InitExpr))
975 return *InitExprLoc;
976 }
977
978 // Even though we have an initializer, we might not get an
979 // InitExprLoc, for example if the InitExpr is a CallExpr for which we
980 // don't have a function body. In this case, we just invent a storage
981 // location and value -- it's the best we can do.
982 return createObjectInternal(D, Ty.getNonReferenceType(), nullptr);
983 }
984
985 Value *Val = nullptr;
986 if (InitExpr) {
987 // In the (few) cases where an expression is intentionally
988 // "uninterpreted", `InitExpr` is not associated with a value. There are
989 // two ways to handle this situation: propagate the status, so that
990 // uninterpreted initializers result in uninterpreted variables, or
991 // provide a default value. We choose the latter so that later refinements
992 // of the variable can be used for reasoning about the surrounding code.
993 // For this reason, we let this case be handled by the `createValue()`
994 // call below.
995 //
996 // FIXME. If and when we interpret all language cases, change this to
997 // assert that `InitExpr` is interpreted, rather than supplying a
998 // default value (assuming we don't update the environment API to return
999 // references).
1000 Val = getValue(*InitExpr);
1001
1002 if (!Val && isa<ImplicitValueInitExpr>(InitExpr) &&
1003 InitExpr->getType()->isPointerType())
1004 Val = &getOrCreateNullPointerValue(InitExpr->getType()->getPointeeType());
1005 }
1006 if (!Val)
1007 Val = createValue(Ty);
1008
1009 if (Ty->isRecordType())
1010 return cast<RecordValue>(Val)->getLoc();
1011
1012 StorageLocation &Loc =
1014
1015 if (Val)
1016 setValue(Loc, *Val);
1017
1018 return Loc;
1019}
1020
1022 DACtx->addFlowConditionConstraint(FlowConditionToken, F);
1023}
1024
1025bool Environment::proves(const Formula &F) const {
1026 return DACtx->flowConditionImplies(FlowConditionToken, F);
1027}
1028
1029bool Environment::allows(const Formula &F) const {
1030 return DACtx->flowConditionAllows(FlowConditionToken, F);
1031}
1032
1033void Environment::dump(raw_ostream &OS) const {
1034 llvm::DenseMap<const StorageLocation *, std::string> LocToName;
1035 if (ThisPointeeLoc != nullptr)
1036 LocToName[ThisPointeeLoc] = "this";
1037
1038 OS << "DeclToLoc:\n";
1039 for (auto [D, L] : DeclToLoc) {
1040 auto Iter = LocToName.insert({L, D->getNameAsString()}).first;
1041 OS << " [" << Iter->second << ", " << L << "]\n";
1042 }
1043 OS << "ExprToLoc:\n";
1044 for (auto [E, L] : ExprToLoc)
1045 OS << " [" << E << ", " << L << "]\n";
1046
1047 OS << "ExprToVal:\n";
1048 for (auto [E, V] : ExprToVal)
1049 OS << " [" << E << ", " << V << ": " << *V << "]\n";
1050
1051 OS << "LocToVal:\n";
1052 for (auto [L, V] : LocToVal) {
1053 OS << " [" << L;
1054 if (auto Iter = LocToName.find(L); Iter != LocToName.end())
1055 OS << " (" << Iter->second << ")";
1056 OS << ", " << V << ": " << *V << "]\n";
1057 }
1058
1059 if (const FunctionDecl *Func = getCurrentFunc()) {
1060 if (Func->getReturnType()->isReferenceType()) {
1061 OS << "ReturnLoc: " << ReturnLoc;
1062 if (auto Iter = LocToName.find(ReturnLoc); Iter != LocToName.end())
1063 OS << " (" << Iter->second << ")";
1064 OS << "\n";
1065 } else if (!Func->getReturnType()->isVoidType()) {
1066 if (ReturnVal == nullptr)
1067 OS << "ReturnVal: nullptr\n";
1068 else
1069 OS << "ReturnVal: " << *ReturnVal << "\n";
1070 }
1071
1072 if (isa<CXXMethodDecl>(Func)) {
1073 OS << "ThisPointeeLoc: " << ThisPointeeLoc << "\n";
1074 }
1075 }
1076
1077 OS << "\n";
1078 DACtx->dumpFlowCondition(FlowConditionToken, OS);
1079}
1080
1081void Environment::dump() const {
1082 dump(llvm::dbgs());
1083}
1084
1086 const Environment &Env) {
1087 Expr *ImplicitObject = MCE.getImplicitObjectArgument();
1088 if (ImplicitObject == nullptr)
1089 return nullptr;
1090 if (ImplicitObject->getType()->isPointerType()) {
1091 if (auto *Val = Env.get<PointerValue>(*ImplicitObject))
1092 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
1093 return nullptr;
1094 }
1095 return cast_or_null<RecordStorageLocation>(
1096 Env.getStorageLocation(*ImplicitObject));
1097}
1098
1100 const Environment &Env) {
1101 Expr *Base = ME.getBase();
1102 if (Base == nullptr)
1103 return nullptr;
1104 if (ME.isArrow()) {
1105 if (auto *Val = Env.get<PointerValue>(*Base))
1106 return &cast<RecordStorageLocation>(Val->getPointeeLoc());
1107 return nullptr;
1108 }
1109 return Env.get<RecordStorageLocation>(*Base);
1110}
1111
1112std::vector<const FieldDecl *>
1114 const RecordDecl *RD = InitList->getType()->getAsRecordDecl();
1115 assert(RD != nullptr);
1116
1117 std::vector<const FieldDecl *> Fields;
1118
1119 if (InitList->getType()->isUnionType()) {
1120 Fields.push_back(InitList->getInitializedFieldInUnion());
1121 return Fields;
1122 }
1123
1124 // Unnamed bitfields are only used for padding and do not appear in
1125 // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
1126 // field list, and we thus need to remove them before mapping inits to
1127 // fields to avoid mapping inits to the wrongs fields.
1128 llvm::copy_if(
1129 RD->fields(), std::back_inserter(Fields),
1130 [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); });
1131 return Fields;
1132}
1133
1135 auto &NewVal = Env.create<RecordValue>(Loc);
1136 Env.setValue(Loc, NewVal);
1137 return NewVal;
1138}
1139
1141 assert(Expr.getType()->isRecordType());
1142
1143 if (Expr.isPRValue()) {
1144 if (auto *ExistingVal = Env.get<RecordValue>(Expr)) {
1145 auto &NewVal = Env.create<RecordValue>(ExistingVal->getLoc());
1146 Env.setValue(Expr, NewVal);
1147 Env.setValue(NewVal.getLoc(), NewVal);
1148 return NewVal;
1149 }
1150
1151 auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType()));
1152 Env.setValue(Expr, NewVal);
1153 return NewVal;
1154 }
1155
1156 if (auto *Loc = Env.get<RecordStorageLocation>(Expr)) {
1157 auto &NewVal = Env.create<RecordValue>(*Loc);
1158 Env.setValue(*Loc, NewVal);
1159 return NewVal;
1160 }
1161
1162 auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType()));
1163 Env.setStorageLocation(Expr, NewVal.getLoc());
1164 return NewVal;
1165}
1166
1167} // namespace dataflow
1168} // namespace clang
#define V(N, I)
Definition: ASTContext.h:3259
NodeId Parent
Definition: ASTDiff.cpp:191
MatchType Type
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
const Environment & Env
Definition: HTMLLogger.cpp:148
llvm::DenseSet< const void * > Visited
Definition: HTMLLogger.cpp:146
unsigned Iter
Definition: HTMLLogger.cpp:154
C Language Family Type Representation.
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1530
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:2808
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1436
Decl * getNonClosureAncestor()
Find the nearest non-closure ancestor of this context, i.e.
Definition: DeclBase.cpp:1173
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:85
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 member of a struct/union/class.
Definition: Decl.h:3025
Represents a function declaration or definition.
Definition: Decl.h:1959
Stmt * getBody(const FunctionDecl *&Definition) const
Retrieve the body (definition) of the function.
Definition: Decl.cpp:3191
param_iterator param_end()
Definition: Decl.h:2664
param_iterator param_begin()
Definition: Decl.h:2663
bool doesThisDeclarationHaveABody() const
Returns whether this specific declaration of the function has a body.
Definition: Decl.h:2270
FunctionDecl * getDefinition()
Get the definition for this declaration.
Definition: Decl.h:2226
Describes an C or C++ initializer list.
Definition: Expr.h:4830
FieldDecl * getInitializedFieldInUnion()
If this initializes a union, specifies which field in the union to initialize.
Definition: Expr.h:4949
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:3171
Expr * getBase() const
Definition: Expr.h:3244
bool isArrow() const
Definition: Expr.h:3351
A (possibly-)qualified type.
Definition: Type.h:737
Represents a struct/union/class.
Definition: Decl.h:4133
field_range fields() const
Definition: Decl.h:4339
Stmt - This represents one statement.
Definition: Stmt.h:84
child_iterator child_begin()
Definition: Stmt.h:1455
child_iterator child_end()
Definition: Stmt.h:1456
The base class of the type hierarchy.
Definition: Type.h:1606
bool isBooleanType() const
Definition: Type.h:7562
bool isPointerType() const
Definition: Type.h:7153
bool isIntegerType() const
isIntegerType() does not include complex integers (a GCC extension).
Definition: Type.h:7474
bool isReferenceType() const
Definition: Type.h:7165
bool isSpecificBuiltinType(unsigned K) const
Test for a particular builtin type.
Definition: Type.h:7411
bool isRecordType() const
Definition: Type.h:7243
bool isUnionType() const
Definition: Type.cpp:621
RecordDecl * getAsRecordDecl() const
Retrieves the RecordDecl this type refers to.
Definition: Type.cpp:1823
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:706
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.
StorageLocation & createStorageLocation(QualType Type)
Returns a new storage location appropriate for Type.
LLVM_DUMP_METHOD void dumpFlowCondition(Atom Token, llvm::raw_ostream &OS=llvm::dbgs())
Supplements Environment with non-standard comparison and join operations.
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.
virtual Value * 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...
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.
static Environment join(const Environment &EnvA, const Environment &EnvB, Environment::ValueModel &Model)
Joins two environments by taking the intersection of storage locations and values that are stored in ...
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
LatticeJoinEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
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.
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.
Environment(DataflowAnalysisContext &DACtx)
Creates an environment that uses DACtx to store objects that encompass the state of a program.
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...
bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const
Returns whether this Environment can be extended to analyze the given Callee (i.e.
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.
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.
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).
const DeclContext * getDeclCtx() const
Returns the DeclContext of the block being analysed, if any.
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,...
std::enable_if_t< std::is_base_of< Value, T >::value, T & > create(Args &&...args)
Creates a T (some subclass of Value), forwarding args to the constructor, and returns a reference to ...
Models a symbolic pointer. Specifically, any value of type T*.
Definition: Value.h:172
A storage location for a record (struct, class, or union).
Models a value of struct or class type.
Definition: Value.h:210
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:56
static Value & widenDistinctValues(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv, Environment::ValueModel &Model)
static void getFieldsGlobalsAndFuncs(const Decl &D, FieldSet &Fields, llvm::DenseSet< const VarDecl * > &Vars, llvm::DenseSet< const FunctionDecl * > &Funcs)
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
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
static constexpr int MaxCompositeValueSize
static bool isOriginalRecordConstructor(const Expr &RecordPRValue)
static void insertIfFunction(const Decl &D, llvm::DenseSet< const FunctionDecl * > &Funcs)
static MemberExpr * getMemberForAccessor(const CXXMemberCallExpr &C)
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, LatticeJoinEffect &Effect)
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...
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
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 void insertIfGlobal(const Decl &D, llvm::DenseSet< const VarDecl * > &Vars)
Initializes a global storage value.
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.
std::vector< const FieldDecl * > getFieldsForInitListExpr(const InitListExpr *InitList)
Returns the fields of a RecordDecl that are initialized by an InitListExpr, in the order in which the...
RecordValue & refreshRecordValue(RecordStorageLocation &Loc, Environment &Env)
Associates a new RecordValue with Loc and returns the 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.