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