clang 17.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/STLExtras.h"
24#include "llvm/Support/Casting.h"
25#include "llvm/Support/ErrorHandling.h"
26#include <cassert>
27#include <memory>
28#include <utility>
29
30namespace clang {
31namespace dataflow {
32
33// FIXME: convert these to parameters of the analysis or environment. Current
34// settings have been experimentaly validated, but only for a particular
35// analysis.
36static constexpr int MaxCompositeValueDepth = 3;
37static constexpr int MaxCompositeValueSize = 1000;
38
39/// Returns a map consisting of key-value entries that are present in both maps.
40template <typename K, typename V>
41llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
42 const llvm::DenseMap<K, V> &Map2) {
43 llvm::DenseMap<K, V> Result;
44 for (auto &Entry : Map1) {
45 auto It = Map2.find(Entry.first);
46 if (It != Map2.end() && Entry.second == It->second)
47 Result.insert({Entry.first, Entry.second});
48 }
49 return Result;
50}
51
53 const Environment &Env1, Value &Val2,
54 const Environment &Env2,
56 // Note: Potentially costly, but, for booleans, we could check whether both
57 // can be proven equivalent in their respective environments.
58
59 // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
60 // and implement separate, join/widen specific handling for
61 // reference/pointers.
62 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
64 return true;
66 return false;
68 switch (Val1.getKind()) {
73 // FIXME: this choice intentionally introduces unsoundness to allow
74 // for convergence. Once we have widening support for the
75 // reference/pointer and struct built-in models, this should be
76 // `false`.
77 return true;
78 default:
79 return false;
80 }
81 }
82 llvm_unreachable("All cases covered in switch");
83}
84
85/// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
86/// respectively, of the same type `Type`. Merging generally produces a single
87/// value that (soundly) approximates the two inputs, although the actual
88/// meaning depends on `Model`.
90 const Environment &Env1, Value &Val2,
91 const Environment &Env2,
92 Environment &MergedEnv,
94 // Join distinct boolean values preserving information about the constraints
95 // in the respective path conditions.
96 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
97 // FIXME: Checking both values should be unnecessary, since they should have
98 // a consistent shape. However, right now we can end up with BoolValue's in
99 // integer-typed variables due to our incorrect handling of
100 // boolean-to-integer casts (we just propagate the BoolValue to the result
101 // of the cast). So, a join can encounter an integer in one branch but a
102 // bool in the other.
103 // For example:
104 // ```
105 // std::optional<bool> o;
106 // int x;
107 // if (o.has_value())
108 // x = o.value();
109 // ```
110 auto *Expr1 = cast<BoolValue>(&Val1);
111 auto *Expr2 = cast<BoolValue>(&Val2);
112 auto &MergedVal = MergedEnv.makeAtomicBoolValue();
113 MergedEnv.addToFlowCondition(MergedEnv.makeOr(
114 MergedEnv.makeAnd(Env1.getFlowConditionToken(),
115 MergedEnv.makeIff(MergedVal, *Expr1)),
116 MergedEnv.makeAnd(Env2.getFlowConditionToken(),
117 MergedEnv.makeIff(MergedVal, *Expr2))));
118 return &MergedVal;
119 }
120
121 // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
122 // returns false to avoid storing unneeded values in `DACtx`.
123 // FIXME: Creating the value based on the type alone creates misshapen values
124 // for lvalues, since the type does not reflect the need for `ReferenceValue`.
125 if (Value *MergedVal = MergedEnv.createValue(Type))
126 if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
127 return MergedVal;
128
129 return nullptr;
130}
131
132// When widening does not change `Current`, return value will equal `&Prev`.
134 const Environment &PrevEnv, Value &Current,
135 Environment &CurrentEnv,
137 // Boolean-model widening.
138 if (isa<BoolValue>(&Prev)) {
139 assert(isa<BoolValue>(Current));
140 // Widen to Top, because we know they are different values. If previous was
141 // already Top, re-use that to (implicitly) indicate that no change occured.
142 if (isa<TopBoolValue>(Prev))
143 return Prev;
144 return CurrentEnv.makeTopBoolValue();
145 }
146
147 // FIXME: Add other built-in model widening.
148
149 // Custom-model widening.
150 if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
151 return *W;
152
153 // Default of widening is a no-op: leave the current value unchanged.
154 return Current;
155}
156
157/// Initializes a global storage value.
158static void insertIfGlobal(const Decl &D,
161 if (auto *V = dyn_cast<VarDecl>(&D))
162 if (V->hasGlobalStorage())
163 Vars.insert(V);
164}
165
166static void getFieldsAndGlobalVars(const Decl &D,
169 insertIfGlobal(D, Fields, Vars);
170 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
171 for (const auto *B : Decomp->bindings())
172 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
173 // FIXME: should we be using `E->getFoundDecl()`?
174 if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
175 Fields.insert(FD);
176}
177
178/// Traverses `S` and inserts into `Vars` any global storage values that are
179/// declared in or referenced from sub-statements.
180static void getFieldsAndGlobalVars(const Stmt &S,
183 for (auto *Child : S.children())
184 if (Child != nullptr)
185 getFieldsAndGlobalVars(*Child, Fields, Vars);
186
187 if (auto *DS = dyn_cast<DeclStmt>(&S)) {
188 if (DS->isSingleDecl())
189 getFieldsAndGlobalVars(*DS->getSingleDecl(), Fields, Vars);
190 else
191 for (auto *D : DS->getDeclGroup())
192 getFieldsAndGlobalVars(*D, Fields, Vars);
193 } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
194 insertIfGlobal(*E->getDecl(), Fields, Vars);
195 } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
196 // FIXME: should we be using `E->getFoundDecl()`?
197 const ValueDecl *VD = E->getMemberDecl();
198 insertIfGlobal(*VD, Fields, Vars);
199 if (const auto *FD = dyn_cast<FieldDecl>(VD))
200 Fields.insert(FD);
201 }
202}
203
204// FIXME: Add support for resetting globals after function calls to enable
205// the implementation of sound analyses.
206void Environment::initVars(llvm::DenseSet<const VarDecl *> Vars) {
207 for (const VarDecl *D : Vars) {
208 if (getStorageLocation(*D, SkipPast::None) != nullptr)
209 continue;
210 auto &Loc = createStorageLocation(*D);
211 setStorageLocation(*D, Loc);
212 if (auto *Val = createValue(D->getType()))
213 setValue(Loc, *Val);
214 }
215}
216
218 : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
219
221 : DACtx(Other.DACtx), CallStack(Other.CallStack),
222 ReturnLoc(Other.ReturnLoc), ThisPointeeLoc(Other.ThisPointeeLoc),
223 DeclToLoc(Other.DeclToLoc), ExprToLoc(Other.ExprToLoc),
224 LocToVal(Other.LocToVal), MemberLocToStruct(Other.MemberLocToStruct),
225 FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
226}
227
229 Environment Copy(Other);
230 *this = std::move(Copy);
231 return *this;
232}
233
235 const DeclContext &DeclCtx)
236 : Environment(DACtx) {
237 CallStack.push_back(&DeclCtx);
238
239 if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
240 assert(FuncDecl->getBody() != nullptr);
241
244
245 // Look for global variable and field references in the
246 // constructor-initializers.
247 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&DeclCtx)) {
248 for (const auto *Init : CtorDecl->inits()) {
249 if (const auto *M = Init->getAnyMember())
250 Fields.insert(M);
251 const Expr *E = Init->getInit();
252 assert(E != nullptr);
253 getFieldsAndGlobalVars(*E, Fields, Vars);
254 }
255 // Add all fields mentioned in default member initializers.
256 for (const FieldDecl *F : CtorDecl->getParent()->fields())
257 if (const auto *I = F->getInClassInitializer())
258 getFieldsAndGlobalVars(*I, Fields, Vars);
259 }
260 getFieldsAndGlobalVars(*FuncDecl->getBody(), Fields, Vars);
261
262 // These have to be added before the lines that follow to ensure that
263 // `create*` work correctly for structs.
264 DACtx.addModeledFields(Fields);
265
266 initVars(Vars);
267
268 for (const auto *ParamDecl : FuncDecl->parameters()) {
269 assert(ParamDecl != nullptr);
270 auto &ParamLoc = createStorageLocation(*ParamDecl);
271 setStorageLocation(*ParamDecl, ParamLoc);
272 if (Value *ParamVal = createValue(ParamDecl->getType()))
273 setValue(ParamLoc, *ParamVal);
274 }
275
276 QualType ReturnType = FuncDecl->getReturnType();
277 ReturnLoc = &createStorageLocation(ReturnType);
278 }
279
280 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
281 auto *Parent = MethodDecl->getParent();
282 assert(Parent != nullptr);
283 if (Parent->isLambda())
284 MethodDecl = dyn_cast<CXXMethodDecl>(Parent->getDeclContext());
285
286 // FIXME: Initialize the ThisPointeeLoc of lambdas too.
287 if (MethodDecl && !MethodDecl->isStatic()) {
288 QualType ThisPointeeType = MethodDecl->getThisObjectType();
289 ThisPointeeLoc = &createStorageLocation(ThisPointeeType);
290 if (Value *ThisPointeeVal = createValue(ThisPointeeType))
291 setValue(*ThisPointeeLoc, *ThisPointeeVal);
292 }
293 }
294}
295
296bool Environment::canDescend(unsigned MaxDepth,
297 const DeclContext *Callee) const {
298 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
299}
300
302 Environment Env(*this);
303
304 // FIXME: Support references here.
305 Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
306
307 if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
308 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
309 if (!isa<CXXThisExpr>(Arg))
310 Env.ThisPointeeLoc = getStorageLocation(*Arg, SkipPast::Reference);
311 // Otherwise (when the argument is `this`), retain the current
312 // environment's `ThisPointeeLoc`.
313 }
314 }
315
316 Env.pushCallInternal(Call->getDirectCallee(),
317 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
318
319 return Env;
320}
321
323 Environment Env(*this);
324
325 // FIXME: Support references here.
326 Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
327
328 Env.ThisPointeeLoc = Env.ReturnLoc;
329
330 Env.pushCallInternal(Call->getConstructor(),
331 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
332
333 return Env;
334}
335
336void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
338 CallStack.push_back(FuncDecl);
339
340 // FIXME: Share this code with the constructor, rather than duplicating it.
343 // Look for global variable references in the constructor-initializers.
344 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
345 for (const auto *Init : CtorDecl->inits()) {
346 if (const auto *M = Init->getAnyMember())
347 Fields.insert(M);
348 const Expr *E = Init->getInit();
349 assert(E != nullptr);
350 getFieldsAndGlobalVars(*E, Fields, Vars);
351 }
352 }
353 getFieldsAndGlobalVars(*FuncDecl->getBody(), Fields, Vars);
354
355 // These have to be added before the lines that follow to ensure that
356 // `create*` work correctly for structs.
357 DACtx->addModeledFields(Fields);
358
359 initVars(Vars);
360
361 const auto *ParamIt = FuncDecl->param_begin();
362
363 // FIXME: Parameters don't always map to arguments 1:1; examples include
364 // overloaded operators implemented as member functions, and parameter packs.
365 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
366 assert(ParamIt != FuncDecl->param_end());
367
368 const Expr *Arg = Args[ArgIndex];
369 auto *ArgLoc = getStorageLocation(*Arg, SkipPast::Reference);
370 if (ArgLoc == nullptr)
371 continue;
372
373 const VarDecl *Param = *ParamIt;
374 auto &Loc = createStorageLocation(*Param);
375 setStorageLocation(*Param, Loc);
376
377 QualType ParamType = Param->getType();
378 if (ParamType->isReferenceType()) {
379 auto &Val = takeOwnership(std::make_unique<ReferenceValue>(*ArgLoc));
380 setValue(Loc, Val);
381 } else if (auto *ArgVal = getValue(*ArgLoc)) {
382 setValue(Loc, *ArgVal);
383 } else if (Value *Val = createValue(ParamType)) {
384 setValue(Loc, *Val);
385 }
386 }
387}
388
389void Environment::popCall(const Environment &CalleeEnv) {
390 // We ignore `DACtx` because it's already the same in both. We don't want the
391 // callee's `DeclCtx`, `ReturnLoc` or `ThisPointeeLoc`. We don't bring back
392 // `DeclToLoc` and `ExprToLoc` because we want to be able to later analyze the
393 // same callee in a different context, and `setStorageLocation` requires there
394 // to not already be a storage location assigned. Conceptually, these maps
395 // capture information from the local scope, so when popping that scope, we do
396 // not propagate the maps.
397 this->LocToVal = std::move(CalleeEnv.LocToVal);
398 this->MemberLocToStruct = std::move(CalleeEnv.MemberLocToStruct);
399 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
400}
401
403 Environment::ValueModel &Model) const {
404 assert(DACtx == Other.DACtx);
405
406 if (ReturnLoc != Other.ReturnLoc)
407 return false;
408
409 if (ThisPointeeLoc != Other.ThisPointeeLoc)
410 return false;
411
412 if (DeclToLoc != Other.DeclToLoc)
413 return false;
414
415 if (ExprToLoc != Other.ExprToLoc)
416 return false;
417
418 // Compare the contents for the intersection of their domains.
419 for (auto &Entry : LocToVal) {
420 const StorageLocation *Loc = Entry.first;
421 assert(Loc != nullptr);
422
423 Value *Val = Entry.second;
424 assert(Val != nullptr);
425
426 auto It = Other.LocToVal.find(Loc);
427 if (It == Other.LocToVal.end())
428 continue;
429 assert(It->second != nullptr);
430
431 if (!areEquivalentValues(*Val, *It->second) &&
432 !compareDistinctValues(Loc->getType(), *Val, *this, *It->second, Other,
433 Model))
434 return false;
435 }
436
437 return true;
438}
439
442 assert(DACtx == PrevEnv.DACtx);
443 assert(ReturnLoc == PrevEnv.ReturnLoc);
444 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
445 assert(CallStack == PrevEnv.CallStack);
446
447 auto Effect = LatticeJoinEffect::Unchanged;
448
449 // By the API, `PrevEnv` is a previous version of the environment for the same
450 // block, so we have some guarantees about its shape. In particular, it will
451 // be the result of a join or widen operation on previous values for this
452 // block. For `DeclToLoc` and `ExprToLoc`, join guarantees that these maps are
453 // subsets of the maps in `PrevEnv`. So, as long as we maintain this property
454 // here, we don't need change their current values to widen.
455 //
456 // FIXME: `MemberLocToStruct` does not share the above property, because
457 // `join` can cause the map size to increase (when we add fresh data in places
458 // of conflict). Once this issue with join is resolved, re-enable the
459 // assertion below or replace with something that captures the desired
460 // invariant.
461 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
462 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
463 // assert(MemberLocToStruct.size() <= PrevEnv.MemberLocToStruct.size());
464
465 llvm::DenseMap<const StorageLocation *, Value *> WidenedLocToVal;
466 for (auto &Entry : LocToVal) {
467 const StorageLocation *Loc = Entry.first;
468 assert(Loc != nullptr);
469
470 Value *Val = Entry.second;
471 assert(Val != nullptr);
472
473 auto PrevIt = PrevEnv.LocToVal.find(Loc);
474 if (PrevIt == PrevEnv.LocToVal.end())
475 continue;
476 assert(PrevIt->second != nullptr);
477
478 if (areEquivalentValues(*Val, *PrevIt->second)) {
479 WidenedLocToVal.insert({Loc, Val});
480 continue;
481 }
482
483 Value &WidenedVal = widenDistinctValues(Loc->getType(), *PrevIt->second,
484 PrevEnv, *Val, *this, Model);
485 WidenedLocToVal.insert({Loc, &WidenedVal});
486 if (&WidenedVal != PrevIt->second)
488 }
489 LocToVal = std::move(WidenedLocToVal);
490 // FIXME: update the equivalence calculation for `MemberLocToStruct`, once we
491 // have a systematic way of soundly comparing this map.
492 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
493 ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
494 LocToVal.size() != PrevEnv.LocToVal.size() ||
495 MemberLocToStruct.size() != PrevEnv.MemberLocToStruct.size())
497
498 return Effect;
499}
500
503 assert(DACtx == Other.DACtx);
504 assert(ReturnLoc == Other.ReturnLoc);
505 assert(ThisPointeeLoc == Other.ThisPointeeLoc);
506 assert(CallStack == Other.CallStack);
507
508 auto Effect = LatticeJoinEffect::Unchanged;
509
510 Environment JoinedEnv(*DACtx);
511
512 JoinedEnv.CallStack = CallStack;
513 JoinedEnv.ReturnLoc = ReturnLoc;
514 JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
515
516 JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
517 if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
519
520 JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
521 if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
523
524 JoinedEnv.MemberLocToStruct =
525 intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
526 if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
528
529 // FIXME: set `Effect` as needed.
530 // FIXME: update join to detect backedges and simplify the flow condition
531 // accordingly.
532 JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
533 *FlowConditionToken, *Other.FlowConditionToken);
534
535 for (auto &Entry : LocToVal) {
536 const StorageLocation *Loc = Entry.first;
537 assert(Loc != nullptr);
538
539 Value *Val = Entry.second;
540 assert(Val != nullptr);
541
542 auto It = Other.LocToVal.find(Loc);
543 if (It == Other.LocToVal.end())
544 continue;
545 assert(It->second != nullptr);
546
547 if (areEquivalentValues(*Val, *It->second)) {
548 JoinedEnv.LocToVal.insert({Loc, Val});
549 continue;
550 }
551
552 if (Value *MergedVal =
553 mergeDistinctValues(Loc->getType(), *Val, *this, *It->second, Other,
554 JoinedEnv, Model)) {
555 JoinedEnv.LocToVal.insert({Loc, MergedVal});
557 }
558 }
559 if (LocToVal.size() != JoinedEnv.LocToVal.size())
561
562 *this = std::move(JoinedEnv);
563
564 return Effect;
565}
566
568 return DACtx->createStorageLocation(Type);
569}
570
572 // Evaluated declarations are always assigned the same storage locations to
573 // ensure that the environment stabilizes across loop iterations. Storage
574 // locations for evaluated declarations are stored in the analysis context.
575 return DACtx->getStableStorageLocation(D);
576}
577
579 // Evaluated expressions are always assigned the same storage locations to
580 // ensure that the environment stabilizes across loop iterations. Storage
581 // locations for evaluated expressions are stored in the analysis context.
582 return DACtx->getStableStorageLocation(E);
583}
584
586 assert(!DeclToLoc.contains(&D));
587 DeclToLoc[&D] = &Loc;
588}
589
591 SkipPast SP) const {
592 auto It = DeclToLoc.find(&D);
593 return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
594}
595
597 const Expr &CanonE = ignoreCFGOmittedNodes(E);
598 assert(!ExprToLoc.contains(&CanonE));
599 ExprToLoc[&CanonE] = &Loc;
600}
601
603 SkipPast SP) const {
604 // FIXME: Add a test with parens.
605 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
606 return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
607}
608
610 return ThisPointeeLoc;
611}
612
614 return ReturnLoc;
615}
616
618 return DACtx->getOrCreateNullPointerValue(PointeeType);
619}
620
622 LocToVal[&Loc] = &Val;
623
624 if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
625 auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
626
627 const QualType Type = AggregateLoc.getType();
629
630 for (const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
631 assert(Field != nullptr);
632 StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
633 MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
634 if (auto *FieldVal = StructVal->getChild(*Field))
635 setValue(FieldLoc, *FieldVal);
636 }
637 }
638
639 auto It = MemberLocToStruct.find(&Loc);
640 if (It != MemberLocToStruct.end()) {
641 // `Loc` is the location of a struct member so we need to also update the
642 // value of the member in the corresponding `StructValue`.
643
644 assert(It->second.first != nullptr);
645 StructValue &StructVal = *It->second.first;
646
647 assert(It->second.second != nullptr);
648 const ValueDecl &Member = *It->second.second;
649
650 StructVal.setChild(Member, Val);
651 }
652}
653
655 auto It = LocToVal.find(&Loc);
656 return It == LocToVal.end() ? nullptr : It->second;
657}
658
660 auto *Loc = getStorageLocation(D, SP);
661 if (Loc == nullptr)
662 return nullptr;
663 return getValue(*Loc);
664}
665
667 auto *Loc = getStorageLocation(E, SP);
668 if (Loc == nullptr)
669 return nullptr;
670 return getValue(*Loc);
671}
672
675 int CreatedValuesCount = 0;
676 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
677 CreatedValuesCount);
678 if (CreatedValuesCount > MaxCompositeValueSize) {
679 llvm::errs() << "Attempting to initialize a huge value of type: " << Type
680 << '\n';
681 }
682 return Val;
683}
684
685Value *Environment::createValueUnlessSelfReferential(
686 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
687 int &CreatedValuesCount) {
688 assert(!Type.isNull());
689
690 // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
691 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
693 return nullptr;
694
695 if (Type->isBooleanType()) {
696 CreatedValuesCount++;
697 return &makeAtomicBoolValue();
698 }
699
700 if (Type->isIntegerType()) {
701 // FIXME: consider instead `return nullptr`, given that we do nothing useful
702 // with integers, and so distinguishing them serves no purpose, but could
703 // prevent convergence.
704 CreatedValuesCount++;
705 return &takeOwnership(std::make_unique<IntegerValue>());
706 }
707
708 if (Type->isReferenceType()) {
709 CreatedValuesCount++;
710 QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
711 auto &PointeeLoc = createStorageLocation(PointeeType);
712
713 if (Visited.insert(PointeeType.getCanonicalType()).second) {
714 Value *PointeeVal = createValueUnlessSelfReferential(
715 PointeeType, Visited, Depth, CreatedValuesCount);
716 Visited.erase(PointeeType.getCanonicalType());
717
718 if (PointeeVal != nullptr)
719 setValue(PointeeLoc, *PointeeVal);
720 }
721
722 return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
723 }
724
725 if (Type->isPointerType()) {
726 CreatedValuesCount++;
727 QualType PointeeType = Type->castAs<PointerType>()->getPointeeType();
728 auto &PointeeLoc = createStorageLocation(PointeeType);
729
730 if (Visited.insert(PointeeType.getCanonicalType()).second) {
731 Value *PointeeVal = createValueUnlessSelfReferential(
732 PointeeType, Visited, Depth, CreatedValuesCount);
733 Visited.erase(PointeeType.getCanonicalType());
734
735 if (PointeeVal != nullptr)
736 setValue(PointeeLoc, *PointeeVal);
737 }
738
739 return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
740 }
741
742 if (Type->isStructureOrClassType() || Type->isUnionType()) {
743 CreatedValuesCount++;
744 llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
745 for (const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
746 assert(Field != nullptr);
747
748 QualType FieldType = Field->getType();
749 if (Visited.contains(FieldType.getCanonicalType()))
750 continue;
751
752 Visited.insert(FieldType.getCanonicalType());
753 if (auto *FieldValue = createValueUnlessSelfReferential(
754 FieldType, Visited, Depth + 1, CreatedValuesCount))
755 FieldValues.insert({Field, FieldValue});
756 Visited.erase(FieldType.getCanonicalType());
757 }
758
759 return &takeOwnership(
760 std::make_unique<StructValue>(std::move(FieldValues)));
761 }
762
763 return nullptr;
764}
765
766StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
767 switch (SP) {
768 case SkipPast::None:
769 return Loc;
771 // References cannot be chained so we only need to skip past one level of
772 // indirection.
773 if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
774 return Val->getReferentLoc();
775 return Loc;
777 StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
778 if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
779 return Val->getPointeeLoc();
780 return LocPastRef;
781 }
782 llvm_unreachable("bad SkipPast kind");
783}
784
785const StorageLocation &Environment::skip(const StorageLocation &Loc,
786 SkipPast SP) const {
787 return skip(*const_cast<StorageLocation *>(&Loc), SP);
788}
789
791 DACtx->addFlowConditionConstraint(*FlowConditionToken, Val);
792}
793
795 return DACtx->flowConditionImplies(*FlowConditionToken, Val);
796}
797
798void Environment::dump(raw_ostream &OS) const {
799 // FIXME: add printing for remaining fields and allow caller to decide what
800 // fields are printed.
801 OS << "DeclToLoc:\n";
802 for (auto [D, L] : DeclToLoc)
803 OS << " [" << D->getName() << ", " << L << "]\n";
804
805 OS << "ExprToLoc:\n";
806 for (auto [E, L] : ExprToLoc)
807 OS << " [" << E << ", " << L << "]\n";
808
809 OS << "LocToVal:\n";
810 for (auto [L, V] : LocToVal) {
811 OS << " [" << L << ", " << V << ": " << *V << "]\n";
812 }
813
814 OS << "FlowConditionToken:\n";
815 DACtx->dumpFlowCondition(*FlowConditionToken, OS);
816}
817
818void Environment::dump() const {
819 dump(llvm::dbgs());
820}
821
822} // namespace dataflow
823} // namespace clang
#define V(N, I)
Definition: ASTContext.h:3217
NodeId Parent
Definition: ASTDiff.cpp:191
MatchType Type
Defines the C++ Decl subclasses, other than those for templates (found in DeclTemplate....
llvm::raw_ostream & OS
Definition: Logger.cpp:24
C Language Family Type Representation.
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1518
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2812
DeclContext - This is used only as base class of specific decl types that can act as declaration cont...
Definition: DeclBase.h:1393
Decl - This represents one declaration (or definition), e.g.
Definition: DeclBase.h:83
This represents one expression.
Definition: Expr.h:110
Represents a member of a struct/union/class.
Definition: Decl.h:2941
const RecordDecl * getParent() const
Returns the parent of this field declaration, which is the struct in which this field is defined.
Definition: Decl.h:3137
Represents a function declaration or definition.
Definition: Decl.h:1917
Stmt * getBody(const FunctionDecl *&Definition) const
Retrieve the body (definition) of the function.
Definition: Decl.cpp:3135
param_iterator param_end()
Definition: Decl.h:2595
param_iterator param_begin()
Definition: Decl.h:2594
A (possibly-)qualified type.
Definition: Type.h:736
field_range fields() const
Definition: Decl.h:4225
Stmt - This represents one statement.
Definition: Stmt.h:72
The base class of the type hierarchy.
Definition: Type.h:1566
bool isBooleanType() const
Definition: Type.h:7334
bool isIntegerType() const
isIntegerType() does not include complex integers (a GCC extension).
Definition: Type.h:7250
bool isStructureOrClassType() const
Definition: Type.cpp:585
bool isUnionType() const
Definition: Type.cpp:599
Represent the declaration of a variable (in which case it is an lvalue) a function (in which case it ...
Definition: Decl.h:701
Represents a variable declaration or definition.
Definition: Decl.h:913
Models a boolean.
Definition: Value.h:93
Owns objects that encompass the state of a program and stores context that is used during dataflow an...
StorageLocation & getStableStorageLocation(const VarDecl &D)
Returns a stable storage location for D.
bool flowConditionImplies(AtomicBoolValue &Token, BoolValue &Val)
Returns true if and only if the constraints of the flow condition identified by Token imply that Val ...
void addFlowConditionConstraint(AtomicBoolValue &Token, BoolValue &Constraint)
Adds Constraint to the flow condition identified by Token.
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.
AtomicBoolValue & joinFlowConditions(AtomicBoolValue &FirstToken, AtomicBoolValue &SecondToken)
Creates a new flow condition that represents the disjunction of the flow conditions identified by Fir...
LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token, llvm::raw_ostream &OS=llvm::dbgs())
Supplements Environment with non-standard comparison and join operations.
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...
virtual bool merge(QualType Type, const Value &Val1, const Environment &Env1, const Value &Val2, const Environment &Env2, Value &MergedVal, Environment &MergedEnv)
Modifies MergedVal to approximate both Val1 and Val2.
Holds the state of the program (store and heap) at a given program point.
StorageLocation * getStorageLocation(const ValueDecl &D, SkipPast SP) const
Returns the storage location assigned to D in the environment, applying the SP policy for skipping pa...
std::enable_if_t< std::is_base_of< StorageLocation, T >::value, T & > takeOwnership(std::unique_ptr< T > Loc)
Transfers ownership of Loc to the analysis context and returns a reference to it.
PointerValue & getOrCreateNullPointerValue(QualType PointeeType)
Returns a pointer value that represents a null pointer.
BoolValue & makeAnd(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the conjunction of LHS and RHS.
LatticeJoinEffect widen(const Environment &PrevEnv, Environment::ValueModel &Model)
Widens the environment point-wise, using PrevEnv as needed to inform the approximation.
BoolValue & makeIff(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value represents LHS <=> RHS.
void addToFlowCondition(BoolValue &Val)
Adds Val to the set of clauses that constitute the flow condition.
Environment pushCall(const CallExpr *Call) const
Creates and returns an environment to use for an inline analysis of the callee.
LLVM_DUMP_METHOD void dump() const
StorageLocation * getThisPointeeStorageLocation() const
Returns the storage location assigned to the this pointee in the environment or null if the this poin...
BoolValue & makeTopBoolValue() const
Returns a unique instance of boolean Top.
StorageLocation & createStorageLocation(QualType Type)
Creates a storage location appropriate for Type.
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.
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.
void setStorageLocation(const ValueDecl &D, StorageLocation &Loc)
Assigns Loc as the storage location of D in the environment.
Value * createValue(QualType Type)
Creates a value appropriate for Type, if Type is supported, otherwise return null.
void popCall(const Environment &CalleeEnv)
Moves gathered information back into this from a CalleeEnv created via pushCall.
void setValue(const StorageLocation &Loc, Value &Val)
Assigns Val as the value of Loc in the environment.
AtomicBoolValue & getFlowConditionToken() const
Returns the token that identifies the flow condition of the environment.
BoolValue & makeOr(BoolValue &LHS, BoolValue &RHS) const
Returns a boolean value that represents the disjunction of LHS and RHS.
LatticeJoinEffect join(const Environment &Other, Environment::ValueModel &Model)
Joins the environment with Other by taking the intersection of storage locations and values that are ...
bool flowConditionImplies(BoolValue &Val) const
Returns true if and only if the clauses that constitute the flow condition imply that Val is true.
StorageLocation * getReturnStorageLocation() const
Returns the storage location of the return value or null, if unset.
Environment & operator=(const Environment &Other)
Models a symbolic pointer. Specifically, any value of type T*.
Definition: Value.h:269
Base class for elements of the local variable store and of the heap.
Models a value of struct or class type, with a flat map of fields to child storage locations,...
Definition: Value.h:287
void setChild(const ValueDecl &D, Value &Val)
Assigns Val as the child value for D.
Definition: Value.h:308
Base class for all values computed by abstract interpretation.
Definition: Value.h:33
Kind getKind() const
Definition: Value.h:61
static void getFieldsAndGlobalVars(const Decl &D, llvm::DenseSet< const FieldDecl * > &Fields, llvm::DenseSet< const VarDecl * > &Vars)
static Value & widenDistinctValues(QualType Type, Value &Prev, const Environment &PrevEnv, Value &Current, Environment &CurrentEnv, Environment::ValueModel &Model)
llvm::DenseMap< K, V > intersectDenseMaps(const llvm::DenseMap< K, V > &Map1, const llvm::DenseMap< K, V > &Map2)
Returns a map consisting of key-value entries that are present in both maps.
static void insertIfGlobal(const Decl &D, llvm::DenseSet< const FieldDecl * > &Fields, llvm::DenseSet< const VarDecl * > &Vars)
Initializes a global storage value.
bool areEquivalentValues(const Value &Val1, const Value &Val2)
An equivalence relation for values.
Definition: Value.cpp:33
static constexpr int MaxCompositeValueDepth
LatticeJoinEffect
Effect indicating whether a lattice join operation resulted in a new value.
static Value * mergeDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment &MergedEnv, Environment::ValueModel &Model)
Attempts to merge distinct values Val1 and Val2 in Env1 and Env2, respectively, of the same type Type...
static constexpr int MaxCompositeValueSize
SkipPast
Indicates what kind of indirections should be skipped past when retrieving storage locations or value...
@ ReferenceThenPointer
An optional reference should be skipped past, then an optional pointer should be skipped past.
@ Reference
An optional reference should be skipped past.
@ None
No indirections should be skipped past.
const Expr & ignoreCFGOmittedNodes(const Expr &E)
Skip past nodes that the CFG does not emit.
static bool compareDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, Environment::ValueModel &Model)
@ Result
The result type of a method or function.