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/Support/Casting.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include <cassert>
26 #include <memory>
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 static bool areEquivalentIndirectionValues(Value *Val1, Value *Val2) {
52   if (auto *IndVal1 = dyn_cast<ReferenceValue>(Val1)) {
53     auto *IndVal2 = cast<ReferenceValue>(Val2);
54     return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc();
55   }
56   if (auto *IndVal1 = dyn_cast<PointerValue>(Val1)) {
57     auto *IndVal2 = cast<PointerValue>(Val2);
58     return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
59   }
60   return false;
61 }
62 
63 /// Returns true if and only if `Val1` is equivalent to `Val2`.
64 static bool equivalentValues(QualType Type, Value *Val1,
65                              const Environment &Env1, Value *Val2,
66                              const Environment &Env2,
67                              Environment::ValueModel &Model) {
68   return Val1 == Val2 || areEquivalentIndirectionValues(Val1, Val2) ||
69          Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2);
70 }
71 
72 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
73 /// respectively, of the same type `Type`. Merging generally produces a single
74 /// value that (soundly) approximates the two inputs, although the actual
75 /// meaning depends on `Model`.
76 static Value *mergeDistinctValues(QualType Type, Value *Val1,
77                                   const Environment &Env1, Value *Val2,
78                                   const Environment &Env2,
79                                   Environment &MergedEnv,
80                                   Environment::ValueModel &Model) {
81   // Join distinct boolean values preserving information about the constraints
82   // in the respective path conditions.
83   //
84   // FIXME: Does not work for backedges, since the two (or more) paths will not
85   // have mutually exclusive conditions.
86   if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) {
87     auto *Expr2 = cast<BoolValue>(Val2);
88     auto &MergedVal = MergedEnv.makeAtomicBoolValue();
89     MergedEnv.addToFlowCondition(MergedEnv.makeOr(
90         MergedEnv.makeAnd(Env1.getFlowConditionToken(),
91                           MergedEnv.makeIff(MergedVal, *Expr1)),
92         MergedEnv.makeAnd(Env2.getFlowConditionToken(),
93                           MergedEnv.makeIff(MergedVal, *Expr2))));
94     return &MergedVal;
95   }
96 
97   // FIXME: add unit tests that cover this statement.
98   if (areEquivalentIndirectionValues(Val1, Val2)) {
99     return Val1;
100   }
101 
102   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
103   // returns false to avoid storing unneeded values in `DACtx`.
104   if (Value *MergedVal = MergedEnv.createValue(Type))
105     if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv))
106       return MergedVal;
107 
108   return nullptr;
109 }
110 
111 /// Initializes a global storage value.
112 static void initGlobalVar(const VarDecl &D, Environment &Env) {
113   if (!D.hasGlobalStorage() ||
114       Env.getStorageLocation(D, SkipPast::None) != nullptr)
115     return;
116 
117   auto &Loc = Env.createStorageLocation(D);
118   Env.setStorageLocation(D, Loc);
119   if (auto *Val = Env.createValue(D.getType()))
120     Env.setValue(Loc, *Val);
121 }
122 
123 /// Initializes a global storage value.
124 static void initGlobalVar(const Decl &D, Environment &Env) {
125   if (auto *V = dyn_cast<VarDecl>(&D))
126     initGlobalVar(*V, Env);
127 }
128 
129 /// Initializes global storage values that are declared or referenced from
130 /// sub-statements of `S`.
131 // FIXME: Add support for resetting globals after function calls to enable
132 // the implementation of sound analyses.
133 static void initGlobalVars(const Stmt &S, Environment &Env) {
134   for (auto *Child : S.children()) {
135     if (Child != nullptr)
136       initGlobalVars(*Child, Env);
137   }
138 
139   if (auto *DS = dyn_cast<DeclStmt>(&S)) {
140     if (DS->isSingleDecl()) {
141       initGlobalVar(*DS->getSingleDecl(), Env);
142     } else {
143       for (auto *D : DS->getDeclGroup())
144         initGlobalVar(*D, Env);
145     }
146   } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
147     initGlobalVar(*E->getDecl(), Env);
148   } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
149     initGlobalVar(*E->getMemberDecl(), Env);
150   }
151 }
152 
153 Environment::Environment(DataflowAnalysisContext &DACtx)
154     : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
155 
156 Environment::Environment(const Environment &Other)
157     : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc),
158       ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal),
159       MemberLocToStruct(Other.MemberLocToStruct),
160       FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
161 }
162 
163 Environment &Environment::operator=(const Environment &Other) {
164   Environment Copy(Other);
165   *this = std::move(Copy);
166   return *this;
167 }
168 
169 Environment::Environment(DataflowAnalysisContext &DACtx,
170                          const DeclContext &DeclCtx)
171     : Environment(DACtx) {
172   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
173     assert(FuncDecl->getBody() != nullptr);
174     initGlobalVars(*FuncDecl->getBody(), *this);
175     for (const auto *ParamDecl : FuncDecl->parameters()) {
176       assert(ParamDecl != nullptr);
177       auto &ParamLoc = createStorageLocation(*ParamDecl);
178       setStorageLocation(*ParamDecl, ParamLoc);
179       if (Value *ParamVal = createValue(ParamDecl->getType()))
180         setValue(ParamLoc, *ParamVal);
181     }
182   }
183 
184   if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
185     auto *Parent = MethodDecl->getParent();
186     assert(Parent != nullptr);
187     if (Parent->isLambda())
188       MethodDecl = dyn_cast<CXXMethodDecl>(Parent->getDeclContext());
189 
190     if (MethodDecl && !MethodDecl->isStatic()) {
191       QualType ThisPointeeType = MethodDecl->getThisObjectType();
192       // FIXME: Add support for union types.
193       if (!ThisPointeeType->isUnionType()) {
194         auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
195         DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
196         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
197           setValue(ThisPointeeLoc, *ThisPointeeVal);
198       }
199     }
200   }
201 }
202 
203 bool Environment::equivalentTo(const Environment &Other,
204                                Environment::ValueModel &Model) const {
205   assert(DACtx == Other.DACtx);
206 
207   if (DeclToLoc != Other.DeclToLoc)
208     return false;
209 
210   if (ExprToLoc != Other.ExprToLoc)
211     return false;
212 
213   // Compare the contents for the intersection of their domains.
214   for (auto &Entry : LocToVal) {
215     const StorageLocation *Loc = Entry.first;
216     assert(Loc != nullptr);
217 
218     Value *Val = Entry.second;
219     assert(Val != nullptr);
220 
221     auto It = Other.LocToVal.find(Loc);
222     if (It == Other.LocToVal.end())
223       continue;
224     assert(It->second != nullptr);
225 
226     if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model))
227       return false;
228   }
229 
230   return true;
231 }
232 
233 LatticeJoinEffect Environment::join(const Environment &Other,
234                                     Environment::ValueModel &Model) {
235   assert(DACtx == Other.DACtx);
236 
237   auto Effect = LatticeJoinEffect::Unchanged;
238 
239   Environment JoinedEnv(*DACtx);
240 
241   JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
242   if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
243     Effect = LatticeJoinEffect::Changed;
244 
245   JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
246   if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
247     Effect = LatticeJoinEffect::Changed;
248 
249   JoinedEnv.MemberLocToStruct =
250       intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
251   if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
252     Effect = LatticeJoinEffect::Changed;
253 
254   // FIXME: set `Effect` as needed.
255   JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
256       *FlowConditionToken, *Other.FlowConditionToken);
257 
258   for (auto &Entry : LocToVal) {
259     const StorageLocation *Loc = Entry.first;
260     assert(Loc != nullptr);
261 
262     Value *Val = Entry.second;
263     assert(Val != nullptr);
264 
265     auto It = Other.LocToVal.find(Loc);
266     if (It == Other.LocToVal.end())
267       continue;
268     assert(It->second != nullptr);
269 
270     if (Val == It->second) {
271       JoinedEnv.LocToVal.insert({Loc, Val});
272       continue;
273     }
274 
275     if (Value *MergedVal = mergeDistinctValues(
276             Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model))
277       JoinedEnv.LocToVal.insert({Loc, MergedVal});
278   }
279   if (LocToVal.size() != JoinedEnv.LocToVal.size())
280     Effect = LatticeJoinEffect::Changed;
281 
282   *this = std::move(JoinedEnv);
283 
284   return Effect;
285 }
286 
287 StorageLocation &Environment::createStorageLocation(QualType Type) {
288   return DACtx->getStableStorageLocation(Type);
289 }
290 
291 StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
292   // Evaluated declarations are always assigned the same storage locations to
293   // ensure that the environment stabilizes across loop iterations. Storage
294   // locations for evaluated declarations are stored in the analysis context.
295   return DACtx->getStableStorageLocation(D);
296 }
297 
298 StorageLocation &Environment::createStorageLocation(const Expr &E) {
299   // Evaluated expressions are always assigned the same storage locations to
300   // ensure that the environment stabilizes across loop iterations. Storage
301   // locations for evaluated expressions are stored in the analysis context.
302   return DACtx->getStableStorageLocation(E);
303 }
304 
305 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
306   assert(DeclToLoc.find(&D) == DeclToLoc.end());
307   DeclToLoc[&D] = &Loc;
308 }
309 
310 StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
311                                                  SkipPast SP) const {
312   auto It = DeclToLoc.find(&D);
313   return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
314 }
315 
316 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
317   const Expr &CanonE = ignoreCFGOmittedNodes(E);
318   assert(ExprToLoc.find(&CanonE) == ExprToLoc.end());
319   ExprToLoc[&CanonE] = &Loc;
320 }
321 
322 StorageLocation *Environment::getStorageLocation(const Expr &E,
323                                                  SkipPast SP) const {
324   // FIXME: Add a test with parens.
325   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
326   return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
327 }
328 
329 StorageLocation *Environment::getThisPointeeStorageLocation() const {
330   return DACtx->getThisPointeeStorageLocation();
331 }
332 
333 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
334   return DACtx->getOrCreateNullPointerValue(PointeeType);
335 }
336 
337 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
338   LocToVal[&Loc] = &Val;
339 
340   if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
341     auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
342 
343     const QualType Type = AggregateLoc.getType();
344     assert(Type->isStructureOrClassType());
345 
346     for (const FieldDecl *Field : getObjectFields(Type)) {
347       assert(Field != nullptr);
348       StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
349       MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
350       if (auto *FieldVal = StructVal->getChild(*Field))
351         setValue(FieldLoc, *FieldVal);
352     }
353   }
354 
355   auto IT = MemberLocToStruct.find(&Loc);
356   if (IT != MemberLocToStruct.end()) {
357     // `Loc` is the location of a struct member so we need to also update the
358     // value of the member in the corresponding `StructValue`.
359 
360     assert(IT->second.first != nullptr);
361     StructValue &StructVal = *IT->second.first;
362 
363     assert(IT->second.second != nullptr);
364     const ValueDecl &Member = *IT->second.second;
365 
366     StructVal.setChild(Member, Val);
367   }
368 }
369 
370 Value *Environment::getValue(const StorageLocation &Loc) const {
371   auto It = LocToVal.find(&Loc);
372   return It == LocToVal.end() ? nullptr : It->second;
373 }
374 
375 Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
376   auto *Loc = getStorageLocation(D, SP);
377   if (Loc == nullptr)
378     return nullptr;
379   return getValue(*Loc);
380 }
381 
382 Value *Environment::getValue(const Expr &E, SkipPast SP) const {
383   auto *Loc = getStorageLocation(E, SP);
384   if (Loc == nullptr)
385     return nullptr;
386   return getValue(*Loc);
387 }
388 
389 Value *Environment::createValue(QualType Type) {
390   llvm::DenseSet<QualType> Visited;
391   int CreatedValuesCount = 0;
392   Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
393                                                 CreatedValuesCount);
394   if (CreatedValuesCount > MaxCompositeValueSize) {
395     llvm::errs() << "Attempting to initialize a huge value of type: " << Type
396                  << '\n';
397   }
398   return Val;
399 }
400 
401 Value *Environment::createValueUnlessSelfReferential(
402     QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
403     int &CreatedValuesCount) {
404   assert(!Type.isNull());
405 
406   // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
407   if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
408       Depth > MaxCompositeValueDepth)
409     return nullptr;
410 
411   if (Type->isBooleanType()) {
412     CreatedValuesCount++;
413     return &makeAtomicBoolValue();
414   }
415 
416   if (Type->isIntegerType()) {
417     CreatedValuesCount++;
418     return &takeOwnership(std::make_unique<IntegerValue>());
419   }
420 
421   if (Type->isReferenceType()) {
422     CreatedValuesCount++;
423     QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
424     auto &PointeeLoc = createStorageLocation(PointeeType);
425 
426     if (Visited.insert(PointeeType.getCanonicalType()).second) {
427       Value *PointeeVal = createValueUnlessSelfReferential(
428           PointeeType, Visited, Depth, CreatedValuesCount);
429       Visited.erase(PointeeType.getCanonicalType());
430 
431       if (PointeeVal != nullptr)
432         setValue(PointeeLoc, *PointeeVal);
433     }
434 
435     return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
436   }
437 
438   if (Type->isPointerType()) {
439     CreatedValuesCount++;
440     QualType PointeeType = Type->castAs<PointerType>()->getPointeeType();
441     auto &PointeeLoc = createStorageLocation(PointeeType);
442 
443     if (Visited.insert(PointeeType.getCanonicalType()).second) {
444       Value *PointeeVal = createValueUnlessSelfReferential(
445           PointeeType, Visited, Depth, CreatedValuesCount);
446       Visited.erase(PointeeType.getCanonicalType());
447 
448       if (PointeeVal != nullptr)
449         setValue(PointeeLoc, *PointeeVal);
450     }
451 
452     return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
453   }
454 
455   if (Type->isStructureOrClassType()) {
456     CreatedValuesCount++;
457     // FIXME: Initialize only fields that are accessed in the context that is
458     // being analyzed.
459     llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
460     for (const FieldDecl *Field : getObjectFields(Type)) {
461       assert(Field != nullptr);
462 
463       QualType FieldType = Field->getType();
464       if (Visited.contains(FieldType.getCanonicalType()))
465         continue;
466 
467       Visited.insert(FieldType.getCanonicalType());
468       if (auto *FieldValue = createValueUnlessSelfReferential(
469               FieldType, Visited, Depth + 1, CreatedValuesCount))
470         FieldValues.insert({Field, FieldValue});
471       Visited.erase(FieldType.getCanonicalType());
472     }
473 
474     return &takeOwnership(
475         std::make_unique<StructValue>(std::move(FieldValues)));
476   }
477 
478   return nullptr;
479 }
480 
481 StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
482   switch (SP) {
483   case SkipPast::None:
484     return Loc;
485   case SkipPast::Reference:
486     // References cannot be chained so we only need to skip past one level of
487     // indirection.
488     if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
489       return Val->getReferentLoc();
490     return Loc;
491   case SkipPast::ReferenceThenPointer:
492     StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
493     if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
494       return Val->getPointeeLoc();
495     return LocPastRef;
496   }
497   llvm_unreachable("bad SkipPast kind");
498 }
499 
500 const StorageLocation &Environment::skip(const StorageLocation &Loc,
501                                          SkipPast SP) const {
502   return skip(*const_cast<StorageLocation *>(&Loc), SP);
503 }
504 
505 void Environment::addToFlowCondition(BoolValue &Val) {
506   DACtx->addFlowConditionConstraint(*FlowConditionToken, Val);
507 }
508 
509 bool Environment::flowConditionImplies(BoolValue &Val) const {
510   return DACtx->flowConditionImplies(*FlowConditionToken, Val);
511 }
512 
513 void Environment::dump() const {
514   DACtx->dumpFlowCondition(*FlowConditionToken);
515 }
516 
517 } // namespace dataflow
518 } // namespace clang
519