xref: /llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp (revision 14b039c1dd1e20cf7527aa717bac05133273a7dd)
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/Type.h"
19 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
20 #include "clang/Analysis/FlowSensitive/Value.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 
29 namespace clang {
30 namespace 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.
35 static constexpr int MaxCompositeValueDepth = 3;
36 static constexpr int MaxCompositeValueSize = 1000;
37 
38 /// Returns a map consisting of key-value entries that are present in both maps.
39 template <typename K, typename V>
40 llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
41                                         const llvm::DenseMap<K, V> &Map2) {
42   llvm::DenseMap<K, V> Result;
43   for (auto &Entry : Map1) {
44     auto It = Map2.find(Entry.first);
45     if (It != Map2.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).
57 static bool equateUnknownValues(Value::Kind K) {
58   switch (K) {
59   case Value::Kind::Integer:
60   case Value::Kind::Pointer:
61   case Value::Kind::Record:
62     return true;
63   default:
64     return false;
65   }
66 }
67 
68 static bool compareDistinctValues(QualType Type, Value &Val1,
69                                   const Environment &Env1, Value &Val2,
70                                   const Environment &Env2,
71                                   Environment::ValueModel &Model) {
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)) {
79   case ComparisonResult::Same:
80     return true;
81   case ComparisonResult::Different:
82     return false;
83   case ComparisonResult::Unknown:
84     return equateUnknownValues(Val1.getKind());
85   }
86   llvm_unreachable("All cases covered in switch");
87 }
88 
89 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
90 /// respectively, of the same type `Type`. Merging generally produces a single
91 /// value that (soundly) approximates the two inputs, although the actual
92 /// meaning depends on `Model`.
93 static Value *mergeDistinctValues(QualType Type, Value &Val1,
94                                   const Environment &Env1, Value &Val2,
95                                   const Environment &Env2,
96                                   Environment &MergedEnv,
97                                   Environment::ValueModel &Model) {
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 = MergedEnv.arena();
117     auto &MergedVal = A.makeAtomRef(A.makeAtom());
118     MergedEnv.addToFlowCondition(
119         A.makeOr(A.makeAnd(A.makeAtomRef(Env1.getFlowConditionToken()),
120                            A.makeEquals(MergedVal, Expr1)),
121                  A.makeAnd(A.makeAtomRef(Env2.getFlowConditionToken()),
122                            A.makeEquals(MergedVal, Expr2))));
123     return &A.makeBoolValue(MergedVal);
124   }
125 
126   Value *MergedVal = 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 merge properties, it should do so in
135       // `DataflowAnalysis::merge()`.
136       MergedVal = &MergedEnv.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       MergedVal = MergedEnv.createValue(Type);
141   } else {
142     MergedVal = MergedEnv.createValue(Type);
143   }
144 
145   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
146   // returns false to avoid storing unneeded values in `DACtx`.
147   if (MergedVal)
148     if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
149       return MergedVal;
150 
151   return nullptr;
152 }
153 
154 // When widening does not change `Current`, return value will equal `&Prev`.
155 static Value &widenDistinctValues(QualType Type, Value &Prev,
156                                   const Environment &PrevEnv, Value &Current,
157                                   Environment &CurrentEnv,
158                                   Environment::ValueModel &Model) {
159   // Boolean-model widening.
160   if (isa<BoolValue>(&Prev)) {
161     assert(isa<BoolValue>(Current));
162     // Widen to Top, because we know they are different values. If previous was
163     // already Top, re-use that to (implicitly) indicate that no change occured.
164     if (isa<TopBoolValue>(Prev))
165       return Prev;
166     return CurrentEnv.makeTopBoolValue();
167   }
168 
169   // FIXME: Add other built-in model widening.
170 
171   // Custom-model widening.
172   if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
173     return *W;
174 
175   return equateUnknownValues(Prev.getKind()) ? Prev : Current;
176 }
177 
178 // Returns whether the values in `Map1` and `Map2` compare equal for those
179 // keys that `Map1` and `Map2` have in common.
180 template <typename Key>
181 bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
182                            const llvm::MapVector<Key, Value *> &Map2,
183                            const Environment &Env1, const Environment &Env2,
184                            Environment::ValueModel &Model) {
185   for (auto &Entry : Map1) {
186     Key K = Entry.first;
187     assert(K != nullptr);
188 
189     Value *Val = Entry.second;
190     assert(Val != nullptr);
191 
192     auto It = Map2.find(K);
193     if (It == Map2.end())
194       continue;
195     assert(It->second != nullptr);
196 
197     if (!areEquivalentValues(*Val, *It->second) &&
198         !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2,
199                                Model))
200       return false;
201   }
202 
203   return true;
204 }
205 
206 // Perform a join on either `LocToVal` or `ExprToVal`. `Key` must be either
207 // `const StorageLocation *` or `const Expr *`.
208 template <typename Key>
209 llvm::MapVector<Key, Value *>
210 joinKeyToValueMap(const llvm::MapVector<Key, Value *> &Map1,
211                   const llvm::MapVector<Key, Value *> &Map2,
212                   const Environment &Env1, const Environment &Env2,
213                   Environment &JoinedEnv, Environment::ValueModel &Model) {
214   llvm::MapVector<Key, Value *> MergedMap;
215   for (auto &Entry : Map1) {
216     Key K = Entry.first;
217     assert(K != nullptr);
218 
219     Value *Val = Entry.second;
220     assert(Val != nullptr);
221 
222     auto It = Map2.find(K);
223     if (It == Map2.end())
224       continue;
225     assert(It->second != nullptr);
226 
227     if (areEquivalentValues(*Val, *It->second)) {
228       MergedMap.insert({K, Val});
229       continue;
230     }
231 
232     if (Value *MergedVal = mergeDistinctValues(
233             K->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) {
234       MergedMap.insert({K, MergedVal});
235     }
236   }
237 
238   return MergedMap;
239 }
240 
241 // Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
242 // `const StorageLocation *` or `const Expr *`.
243 template <typename Key>
244 llvm::MapVector<Key, Value *>
245 widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
246                    const llvm::MapVector<Key, Value *> &PrevMap,
247                    Environment &CurEnv, const Environment &PrevEnv,
248                    Environment::ValueModel &Model, LatticeJoinEffect &Effect) {
249   llvm::MapVector<Key, Value *> WidenedMap;
250   for (auto &Entry : CurMap) {
251     Key K = Entry.first;
252     assert(K != nullptr);
253 
254     Value *Val = Entry.second;
255     assert(Val != nullptr);
256 
257     auto PrevIt = PrevMap.find(K);
258     if (PrevIt == PrevMap.end())
259       continue;
260     assert(PrevIt->second != nullptr);
261 
262     if (areEquivalentValues(*Val, *PrevIt->second)) {
263       WidenedMap.insert({K, Val});
264       continue;
265     }
266 
267     Value &WidenedVal = widenDistinctValues(K->getType(), *PrevIt->second,
268                                             PrevEnv, *Val, CurEnv, Model);
269     WidenedMap.insert({K, &WidenedVal});
270     if (&WidenedVal != PrevIt->second)
271       Effect = LatticeJoinEffect::Changed;
272   }
273 
274   return WidenedMap;
275 }
276 
277 /// Initializes a global storage value.
278 static void insertIfGlobal(const Decl &D,
279                            llvm::DenseSet<const VarDecl *> &Vars) {
280   if (auto *V = dyn_cast<VarDecl>(&D))
281     if (V->hasGlobalStorage())
282       Vars.insert(V);
283 }
284 
285 static void insertIfFunction(const Decl &D,
286                              llvm::DenseSet<const FunctionDecl *> &Funcs) {
287   if (auto *FD = dyn_cast<FunctionDecl>(&D))
288     Funcs.insert(FD);
289 }
290 
291 static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {
292   if (!C.getMethodDecl())
293     return nullptr;
294   auto *Body = dyn_cast_or_null<CompoundStmt>(C.getMethodDecl()->getBody());
295   if (!Body || Body->size() != 1)
296     return nullptr;
297   if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))
298     if (auto *Return = RS->getRetValue())
299       return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());
300   return nullptr;
301 }
302 
303 static void
304 getFieldsGlobalsAndFuncs(const Decl &D, FieldSet &Fields,
305                          llvm::DenseSet<const VarDecl *> &Vars,
306                          llvm::DenseSet<const FunctionDecl *> &Funcs) {
307   insertIfGlobal(D, Vars);
308   insertIfFunction(D, Funcs);
309   if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
310     for (const auto *B : Decomp->bindings())
311       if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
312         // FIXME: should we be using `E->getFoundDecl()`?
313         if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
314           Fields.insert(FD);
315 }
316 
317 /// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields,
318 /// global variables and functions that are declared in or referenced from
319 /// sub-statements.
320 static void
321 getFieldsGlobalsAndFuncs(const Stmt &S, FieldSet &Fields,
322                          llvm::DenseSet<const VarDecl *> &Vars,
323                          llvm::DenseSet<const FunctionDecl *> &Funcs) {
324   for (auto *Child : S.children())
325     if (Child != nullptr)
326       getFieldsGlobalsAndFuncs(*Child, Fields, Vars, Funcs);
327   if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S))
328     getFieldsGlobalsAndFuncs(*DefaultInit->getExpr(), Fields, Vars, Funcs);
329 
330   if (auto *DS = dyn_cast<DeclStmt>(&S)) {
331     if (DS->isSingleDecl())
332       getFieldsGlobalsAndFuncs(*DS->getSingleDecl(), Fields, Vars, Funcs);
333     else
334       for (auto *D : DS->getDeclGroup())
335         getFieldsGlobalsAndFuncs(*D, Fields, Vars, Funcs);
336   } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
337     insertIfGlobal(*E->getDecl(), Vars);
338     insertIfFunction(*E->getDecl(), Funcs);
339   } else if (const auto *C = dyn_cast<CXXMemberCallExpr>(&S)) {
340     // If this is a method that returns a member variable but does nothing else,
341     // model the field of the return value.
342     if (MemberExpr *E = getMemberForAccessor(*C))
343       if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl()))
344         Fields.insert(FD);
345   } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
346     // FIXME: should we be using `E->getFoundDecl()`?
347     const ValueDecl *VD = E->getMemberDecl();
348     insertIfGlobal(*VD, Vars);
349     insertIfFunction(*VD, Funcs);
350     if (const auto *FD = dyn_cast<FieldDecl>(VD))
351       Fields.insert(FD);
352   } else if (auto *InitList = dyn_cast<InitListExpr>(&S)) {
353     if (RecordDecl *RD = InitList->getType()->getAsRecordDecl())
354       for (const auto *FD : getFieldsForInitListExpr(RD))
355         Fields.insert(FD);
356   }
357 }
358 
359 // FIXME: Add support for resetting globals after function calls to enable
360 // the implementation of sound analyses.
361 void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) {
362   assert(FuncDecl->getBody() != nullptr);
363 
364   FieldSet Fields;
365   llvm::DenseSet<const VarDecl *> Vars;
366   llvm::DenseSet<const FunctionDecl *> Funcs;
367 
368   // Look for global variable and field references in the
369   // constructor-initializers.
370   if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
371     for (const auto *Init : CtorDecl->inits()) {
372       if (Init->isMemberInitializer()) {
373         Fields.insert(Init->getMember());
374       } else if (Init->isIndirectMemberInitializer()) {
375         for (const auto *I : Init->getIndirectMember()->chain())
376           Fields.insert(cast<FieldDecl>(I));
377       }
378       const Expr *E = Init->getInit();
379       assert(E != nullptr);
380       getFieldsGlobalsAndFuncs(*E, Fields, Vars, Funcs);
381     }
382     // Add all fields mentioned in default member initializers.
383     for (const FieldDecl *F : CtorDecl->getParent()->fields())
384       if (const auto *I = F->getInClassInitializer())
385           getFieldsGlobalsAndFuncs(*I, Fields, Vars, Funcs);
386   }
387   getFieldsGlobalsAndFuncs(*FuncDecl->getBody(), Fields, Vars, Funcs);
388 
389   // These have to be added before the lines that follow to ensure that
390   // `create*` work correctly for structs.
391   DACtx->addModeledFields(Fields);
392 
393   for (const VarDecl *D : Vars) {
394     if (getStorageLocation(*D) != nullptr)
395       continue;
396 
397     setStorageLocation(*D, createObject(*D));
398   }
399 
400   for (const FunctionDecl *FD : Funcs) {
401     if (getStorageLocation(*FD) != nullptr)
402       continue;
403     auto &Loc = createStorageLocation(FD->getType());
404     setStorageLocation(*FD, Loc);
405   }
406 }
407 
408 Environment::Environment(DataflowAnalysisContext &DACtx)
409     : DACtx(&DACtx),
410       FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
411 
412 Environment Environment::fork() const {
413   Environment Copy(*this);
414   Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken);
415   return Copy;
416 }
417 
418 Environment::Environment(DataflowAnalysisContext &DACtx,
419                          const DeclContext &DeclCtx)
420     : Environment(DACtx) {
421   CallStack.push_back(&DeclCtx);
422 
423   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
424     assert(FuncDecl->getBody() != nullptr);
425 
426     initFieldsGlobalsAndFuncs(FuncDecl);
427 
428     for (const auto *ParamDecl : FuncDecl->parameters()) {
429       assert(ParamDecl != nullptr);
430       setStorageLocation(*ParamDecl, createObject(*ParamDecl, nullptr));
431     }
432   }
433 
434   if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
435     auto *Parent = MethodDecl->getParent();
436     assert(Parent != nullptr);
437 
438     if (Parent->isLambda()) {
439       for (auto Capture : Parent->captures()) {
440         if (Capture.capturesVariable()) {
441           const auto *VarDecl = Capture.getCapturedVar();
442           assert(VarDecl != nullptr);
443           setStorageLocation(*VarDecl, createObject(*VarDecl, nullptr));
444         } else if (Capture.capturesThis()) {
445           const auto *SurroundingMethodDecl =
446               cast<CXXMethodDecl>(DeclCtx.getNonClosureAncestor());
447           QualType ThisPointeeType =
448               SurroundingMethodDecl->getFunctionObjectParameterType();
449           ThisPointeeLoc =
450               &cast<RecordValue>(createValue(ThisPointeeType))->getLoc();
451         }
452       }
453     } else if (MethodDecl->isImplicitObjectMemberFunction()) {
454       QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
455       ThisPointeeLoc =
456           &cast<RecordValue>(createValue(ThisPointeeType))->getLoc();
457     }
458   }
459 }
460 
461 bool Environment::canDescend(unsigned MaxDepth,
462                              const DeclContext *Callee) const {
463   return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
464 }
465 
466 Environment Environment::pushCall(const CallExpr *Call) const {
467   Environment Env(*this);
468 
469   if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
470     if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
471       if (!isa<CXXThisExpr>(Arg))
472           Env.ThisPointeeLoc =
473               cast<RecordStorageLocation>(getStorageLocation(*Arg));
474       // Otherwise (when the argument is `this`), retain the current
475       // environment's `ThisPointeeLoc`.
476     }
477   }
478 
479   Env.pushCallInternal(Call->getDirectCallee(),
480                        llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
481 
482   return Env;
483 }
484 
485 Environment Environment::pushCall(const CXXConstructExpr *Call) const {
486   Environment Env(*this);
487 
488   Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call);
489 
490   Env.pushCallInternal(Call->getConstructor(),
491                        llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
492 
493   return Env;
494 }
495 
496 void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
497                                    ArrayRef<const Expr *> Args) {
498   // Canonicalize to the definition of the function. This ensures that we're
499   // putting arguments into the same `ParamVarDecl`s` that the callee will later
500   // be retrieving them from.
501   assert(FuncDecl->getDefinition() != nullptr);
502   FuncDecl = FuncDecl->getDefinition();
503 
504   CallStack.push_back(FuncDecl);
505 
506   initFieldsGlobalsAndFuncs(FuncDecl);
507 
508   const auto *ParamIt = FuncDecl->param_begin();
509 
510   // FIXME: Parameters don't always map to arguments 1:1; examples include
511   // overloaded operators implemented as member functions, and parameter packs.
512   for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
513     assert(ParamIt != FuncDecl->param_end());
514     const VarDecl *Param = *ParamIt;
515     setStorageLocation(*Param, createObject(*Param, Args[ArgIndex]));
516   }
517 }
518 
519 void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
520   // We ignore some entries of `CalleeEnv`:
521   // - `DACtx` because is already the same in both
522   // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or
523   //   `ThisPointeeLoc` because they don't apply to us.
524   // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the
525   //   callee's local scope, so when popping that scope, we do not propagate
526   //   the maps.
527   this->LocToVal = std::move(CalleeEnv.LocToVal);
528   this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
529 
530   if (Call->isGLValue()) {
531     if (CalleeEnv.ReturnLoc != nullptr)
532       setStorageLocation(*Call, *CalleeEnv.ReturnLoc);
533   } else if (!Call->getType()->isVoidType()) {
534     if (CalleeEnv.ReturnVal != nullptr)
535       setValue(*Call, *CalleeEnv.ReturnVal);
536   }
537 }
538 
539 void Environment::popCall(const CXXConstructExpr *Call,
540                           const Environment &CalleeEnv) {
541   // See also comment in `popCall(const CallExpr *, const Environment &)` above.
542   this->LocToVal = std::move(CalleeEnv.LocToVal);
543   this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
544 
545   if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) {
546     setValue(*Call, *Val);
547   }
548 }
549 
550 bool Environment::equivalentTo(const Environment &Other,
551                                Environment::ValueModel &Model) const {
552   assert(DACtx == Other.DACtx);
553 
554   if (ReturnVal != Other.ReturnVal)
555     return false;
556 
557   if (ReturnLoc != Other.ReturnLoc)
558     return false;
559 
560   if (ThisPointeeLoc != Other.ThisPointeeLoc)
561     return false;
562 
563   if (DeclToLoc != Other.DeclToLoc)
564     return false;
565 
566   if (ExprToLoc != Other.ExprToLoc)
567     return false;
568 
569   if (!compareKeyToValueMaps(ExprToVal, Other.ExprToVal, *this, Other, Model))
570     return false;
571 
572   if (!compareKeyToValueMaps(LocToVal, Other.LocToVal, *this, Other, Model))
573     return false;
574 
575   return true;
576 }
577 
578 LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
579                                      Environment::ValueModel &Model) {
580   assert(DACtx == PrevEnv.DACtx);
581   assert(ReturnVal == PrevEnv.ReturnVal);
582   assert(ReturnLoc == PrevEnv.ReturnLoc);
583   assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
584   assert(CallStack == PrevEnv.CallStack);
585 
586   auto Effect = LatticeJoinEffect::Unchanged;
587 
588   // By the API, `PrevEnv` is a previous version of the environment for the same
589   // block, so we have some guarantees about its shape. In particular, it will
590   // be the result of a join or widen operation on previous values for this
591   // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that
592   // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain
593   // this property here, we don't need change their current values to widen.
594   assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
595   assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
596   assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
597 
598   ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv,
599                                  Model, Effect);
600 
601   LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv,
602                                 Model, Effect);
603   if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
604       ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
605       ExprToVal.size() != PrevEnv.ExprToVal.size() ||
606       LocToVal.size() != PrevEnv.LocToVal.size())
607     Effect = LatticeJoinEffect::Changed;
608 
609   return Effect;
610 }
611 
612 Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
613                               Environment::ValueModel &Model) {
614   assert(EnvA.DACtx == EnvB.DACtx);
615   assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
616   assert(EnvA.CallStack == EnvB.CallStack);
617 
618   Environment JoinedEnv(*EnvA.DACtx);
619 
620   JoinedEnv.CallStack = EnvA.CallStack;
621   JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
622 
623   if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) {
624     // `ReturnVal` might not always get set -- for example if we have a return
625     // statement of the form `return some_other_func()` and we decide not to
626     // analyze `some_other_func()`.
627     // In this case, we can't say anything about the joined return value -- we
628     // don't simply want to propagate the return value that we do have, because
629     // it might not be the correct one.
630     // This occurs for example in the test `ContextSensitiveMutualRecursion`.
631     JoinedEnv.ReturnVal = nullptr;
632   } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) {
633     JoinedEnv.ReturnVal = EnvA.ReturnVal;
634   } else {
635     assert(!EnvA.CallStack.empty());
636     // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this
637     // cast.
638     auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
639     assert(Func != nullptr);
640     if (Value *MergedVal =
641             mergeDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA,
642                                 *EnvB.ReturnVal, EnvB, JoinedEnv, Model))
643       JoinedEnv.ReturnVal = MergedVal;
644   }
645 
646   if (EnvA.ReturnLoc == EnvB.ReturnLoc)
647     JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
648   else
649     JoinedEnv.ReturnLoc = nullptr;
650 
651   JoinedEnv.DeclToLoc = intersectDenseMaps(EnvA.DeclToLoc, EnvB.DeclToLoc);
652 
653   JoinedEnv.ExprToLoc = intersectDenseMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
654 
655   // FIXME: update join to detect backedges and simplify the flow condition
656   // accordingly.
657   JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions(
658       EnvA.FlowConditionToken, EnvB.FlowConditionToken);
659 
660   JoinedEnv.ExprToVal = joinKeyToValueMap(EnvA.ExprToVal, EnvB.ExprToVal, EnvA,
661                                           EnvB, JoinedEnv, Model);
662 
663   JoinedEnv.LocToVal = joinKeyToValueMap(EnvA.LocToVal, EnvB.LocToVal, EnvA,
664                                          EnvB, JoinedEnv, Model);
665 
666   return JoinedEnv;
667 }
668 
669 StorageLocation &Environment::createStorageLocation(QualType Type) {
670   return DACtx->createStorageLocation(Type);
671 }
672 
673 StorageLocation &Environment::createStorageLocation(const ValueDecl &D) {
674   // Evaluated declarations are always assigned the same storage locations to
675   // ensure that the environment stabilizes across loop iterations. Storage
676   // locations for evaluated declarations are stored in the analysis context.
677   return DACtx->getStableStorageLocation(D);
678 }
679 
680 StorageLocation &Environment::createStorageLocation(const Expr &E) {
681   // Evaluated expressions are always assigned the same storage locations to
682   // ensure that the environment stabilizes across loop iterations. Storage
683   // locations for evaluated expressions are stored in the analysis context.
684   return DACtx->getStableStorageLocation(E);
685 }
686 
687 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
688   assert(!DeclToLoc.contains(&D));
689   DeclToLoc[&D] = &Loc;
690 }
691 
692 StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
693   auto It = DeclToLoc.find(&D);
694   if (It == DeclToLoc.end())
695     return nullptr;
696 
697   StorageLocation *Loc = It->second;
698 
699   return Loc;
700 }
701 
702 void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(&D); }
703 
704 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
705   // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
706   // but we still want to be able to associate a `StorageLocation` with them,
707   // so allow these as an exception.
708   assert(E.isGLValue() ||
709          E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
710   setStorageLocationInternal(E, Loc);
711 }
712 
713 StorageLocation *Environment::getStorageLocation(const Expr &E) const {
714   // See comment in `setStorageLocation()`.
715   assert(E.isGLValue() ||
716          E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
717   return getStorageLocationInternal(E);
718 }
719 
720 RecordStorageLocation *Environment::getThisPointeeStorageLocation() const {
721   return ThisPointeeLoc;
722 }
723 
724 RecordStorageLocation &
725 Environment::getResultObjectLocation(const Expr &RecordPRValue) {
726   assert(RecordPRValue.getType()->isRecordType());
727   assert(RecordPRValue.isPRValue());
728 
729   if (StorageLocation *ExistingLoc = getStorageLocationInternal(RecordPRValue))
730     return *cast<RecordStorageLocation>(ExistingLoc);
731   auto &Loc = cast<RecordStorageLocation>(
732       DACtx->getStableStorageLocation(RecordPRValue));
733   setStorageLocationInternal(RecordPRValue, Loc);
734   return Loc;
735 }
736 
737 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
738   return DACtx->getOrCreateNullPointerValue(PointeeType);
739 }
740 
741 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
742   assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc);
743 
744   LocToVal[&Loc] = &Val;
745 }
746 
747 void Environment::setValue(const Expr &E, Value &Val) {
748   assert(E.isPRValue());
749   ExprToVal[&E] = &Val;
750 }
751 
752 Value *Environment::getValue(const StorageLocation &Loc) const {
753   return LocToVal.lookup(&Loc);
754 }
755 
756 Value *Environment::getValue(const ValueDecl &D) const {
757   auto *Loc = getStorageLocation(D);
758   if (Loc == nullptr)
759     return nullptr;
760   return getValue(*Loc);
761 }
762 
763 Value *Environment::getValue(const Expr &E) const {
764   if (E.isPRValue()) {
765     auto It = ExprToVal.find(&ignoreCFGOmittedNodes(E));
766     return It == ExprToVal.end() ? nullptr : It->second;
767   }
768 
769   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
770   if (It == ExprToLoc.end())
771     return nullptr;
772   return getValue(*It->second);
773 }
774 
775 Value *Environment::createValue(QualType Type) {
776   llvm::DenseSet<QualType> Visited;
777   int CreatedValuesCount = 0;
778   Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
779                                                 CreatedValuesCount);
780   if (CreatedValuesCount > MaxCompositeValueSize) {
781     llvm::errs() << "Attempting to initialize a huge value of type: " << Type
782                  << '\n';
783   }
784   return Val;
785 }
786 
787 void Environment::setStorageLocationInternal(const Expr &E,
788                                              StorageLocation &Loc) {
789   const Expr &CanonE = ignoreCFGOmittedNodes(E);
790   assert(!ExprToLoc.contains(&CanonE));
791   ExprToLoc[&CanonE] = &Loc;
792 }
793 
794 StorageLocation *Environment::getStorageLocationInternal(const Expr &E) const {
795   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
796   return It == ExprToLoc.end() ? nullptr : &*It->second;
797 }
798 
799 Value *Environment::createValueUnlessSelfReferential(
800     QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
801     int &CreatedValuesCount) {
802   assert(!Type.isNull());
803   assert(!Type->isReferenceType());
804 
805   // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
806   if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
807       Depth > MaxCompositeValueDepth)
808     return nullptr;
809 
810   if (Type->isBooleanType()) {
811     CreatedValuesCount++;
812     return &makeAtomicBoolValue();
813   }
814 
815   if (Type->isIntegerType()) {
816     // FIXME: consider instead `return nullptr`, given that we do nothing useful
817     // with integers, and so distinguishing them serves no purpose, but could
818     // prevent convergence.
819     CreatedValuesCount++;
820     return &arena().create<IntegerValue>();
821   }
822 
823   if (Type->isPointerType()) {
824     CreatedValuesCount++;
825     QualType PointeeType = Type->getPointeeType();
826     StorageLocation &PointeeLoc =
827         createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount);
828 
829     return &arena().create<PointerValue>(PointeeLoc);
830   }
831 
832   if (Type->isRecordType()) {
833     CreatedValuesCount++;
834     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
835     for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
836       assert(Field != nullptr);
837 
838       QualType FieldType = Field->getType();
839 
840       FieldLocs.insert(
841           {Field, &createLocAndMaybeValue(FieldType, Visited, Depth + 1,
842                                           CreatedValuesCount)});
843     }
844 
845     RecordStorageLocation &Loc =
846         arena().create<RecordStorageLocation>(Type, std::move(FieldLocs));
847     RecordValue &RecordVal = create<RecordValue>(Loc);
848 
849     // As we already have a storage location for the `RecordValue`, we can and
850     // should associate them in the environment.
851     setValue(Loc, RecordVal);
852 
853     return &RecordVal;
854   }
855 
856   return nullptr;
857 }
858 
859 StorageLocation &
860 Environment::createLocAndMaybeValue(QualType Ty,
861                                     llvm::DenseSet<QualType> &Visited,
862                                     int Depth, int &CreatedValuesCount) {
863   if (!Visited.insert(Ty.getCanonicalType()).second)
864     return createStorageLocation(Ty.getNonReferenceType());
865   Value *Val = createValueUnlessSelfReferential(
866       Ty.getNonReferenceType(), Visited, Depth, CreatedValuesCount);
867   Visited.erase(Ty.getCanonicalType());
868 
869   Ty = Ty.getNonReferenceType();
870 
871   if (Val == nullptr)
872     return createStorageLocation(Ty);
873 
874   if (Ty->isRecordType())
875     return cast<RecordValue>(Val)->getLoc();
876 
877   StorageLocation &Loc = createStorageLocation(Ty);
878   setValue(Loc, *Val);
879   return Loc;
880 }
881 
882 StorageLocation &Environment::createObjectInternal(const ValueDecl *D,
883                                                    QualType Ty,
884                                                    const Expr *InitExpr) {
885   if (Ty->isReferenceType()) {
886     // Although variables of reference type always need to be initialized, it
887     // can happen that we can't see the initializer, so `InitExpr` may still
888     // be null.
889     if (InitExpr) {
890       if (auto *InitExprLoc = getStorageLocation(*InitExpr))
891           return *InitExprLoc;
892     }
893 
894     // Even though we have an initializer, we might not get an
895     // InitExprLoc, for example if the InitExpr is a CallExpr for which we
896     // don't have a function body. In this case, we just invent a storage
897     // location and value -- it's the best we can do.
898     return createObjectInternal(D, Ty.getNonReferenceType(), nullptr);
899   }
900 
901   Value *Val = nullptr;
902   if (InitExpr)
903     // In the (few) cases where an expression is intentionally
904     // "uninterpreted", `InitExpr` is not associated with a value.  There are
905     // two ways to handle this situation: propagate the status, so that
906     // uninterpreted initializers result in uninterpreted variables, or
907     // provide a default value. We choose the latter so that later refinements
908     // of the variable can be used for reasoning about the surrounding code.
909     // For this reason, we let this case be handled by the `createValue()`
910     // call below.
911     //
912     // FIXME. If and when we interpret all language cases, change this to
913     // assert that `InitExpr` is interpreted, rather than supplying a
914     // default value (assuming we don't update the environment API to return
915     // references).
916     Val = getValue(*InitExpr);
917   if (!Val)
918     Val = createValue(Ty);
919 
920   if (Ty->isRecordType())
921     return cast<RecordValue>(Val)->getLoc();
922 
923   StorageLocation &Loc =
924       D ? createStorageLocation(*D) : createStorageLocation(Ty);
925 
926   if (Val)
927     setValue(Loc, *Val);
928 
929   return Loc;
930 }
931 
932 void Environment::addToFlowCondition(const Formula &Val) {
933   DACtx->addFlowConditionConstraint(FlowConditionToken, Val);
934 }
935 
936 bool Environment::flowConditionImplies(const Formula &Val) const {
937   return DACtx->flowConditionImplies(FlowConditionToken, Val);
938 }
939 
940 void Environment::dump(raw_ostream &OS) const {
941   // FIXME: add printing for remaining fields and allow caller to decide what
942   // fields are printed.
943   OS << "DeclToLoc:\n";
944   for (auto [D, L] : DeclToLoc)
945     OS << "  [" << D->getNameAsString() << ", " << L << "]\n";
946 
947   OS << "ExprToLoc:\n";
948   for (auto [E, L] : ExprToLoc)
949     OS << "  [" << E << ", " << L << "]\n";
950 
951   OS << "ExprToVal:\n";
952   for (auto [E, V] : ExprToVal)
953     OS << "  [" << E << ", " << V << ": " << *V << "]\n";
954 
955   OS << "LocToVal:\n";
956   for (auto [L, V] : LocToVal) {
957     OS << "  [" << L << ", " << V << ": " << *V << "]\n";
958   }
959 
960   OS << "FlowConditionToken:\n";
961   DACtx->dumpFlowCondition(FlowConditionToken, OS);
962 }
963 
964 void Environment::dump() const {
965   dump(llvm::dbgs());
966 }
967 
968 RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
969                                                  const Environment &Env) {
970   Expr *ImplicitObject = MCE.getImplicitObjectArgument();
971   if (ImplicitObject == nullptr)
972     return nullptr;
973   if (ImplicitObject->getType()->isPointerType()) {
974     if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*ImplicitObject)))
975       return &cast<RecordStorageLocation>(Val->getPointeeLoc());
976     return nullptr;
977   }
978   return cast_or_null<RecordStorageLocation>(
979       Env.getStorageLocation(*ImplicitObject));
980 }
981 
982 RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
983                                              const Environment &Env) {
984   Expr *Base = ME.getBase();
985   if (Base == nullptr)
986     return nullptr;
987   if (ME.isArrow()) {
988     if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Base)))
989       return &cast<RecordStorageLocation>(Val->getPointeeLoc());
990     return nullptr;
991   }
992   return cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Base));
993 }
994 
995 std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD) {
996   // Unnamed bitfields are only used for padding and do not appear in
997   // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
998   // field list, and we thus need to remove them before mapping inits to
999   // fields to avoid mapping inits to the wrongs fields.
1000   std::vector<FieldDecl *> Fields;
1001   llvm::copy_if(
1002       RD->fields(), std::back_inserter(Fields),
1003       [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); });
1004   return Fields;
1005 }
1006 
1007 RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env) {
1008   auto &NewVal = Env.create<RecordValue>(Loc);
1009   Env.setValue(Loc, NewVal);
1010   return NewVal;
1011 }
1012 
1013 RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env) {
1014   assert(Expr.getType()->isRecordType());
1015 
1016   if (Expr.isPRValue()) {
1017     if (auto *ExistingVal = cast_or_null<RecordValue>(Env.getValue(Expr))) {
1018       auto &NewVal = Env.create<RecordValue>(ExistingVal->getLoc());
1019       Env.setValue(Expr, NewVal);
1020       return NewVal;
1021     }
1022 
1023     auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType()));
1024     Env.setValue(Expr, NewVal);
1025     return NewVal;
1026   }
1027 
1028   if (auto *Loc =
1029           cast_or_null<RecordStorageLocation>(Env.getStorageLocation(Expr))) {
1030     auto &NewVal = Env.create<RecordValue>(*Loc);
1031     Env.setValue(*Loc, NewVal);
1032     return NewVal;
1033   }
1034 
1035   auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType()));
1036   Env.setStorageLocation(Expr, NewVal.getLoc());
1037   return NewVal;
1038 }
1039 
1040 } // namespace dataflow
1041 } // namespace clang
1042