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/StorageLocation.h"
21 #include "clang/Analysis/FlowSensitive/Value.h"
22 #include "llvm/ADT/DenseMap.h"
23 #include "llvm/ADT/DenseSet.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include <memory>
26 #include <utility>
27 
28 namespace clang {
29 namespace dataflow {
30 
31 /// Returns a map consisting of key-value entries that are present in both maps.
32 template <typename K, typename V>
33 llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
34                                         const llvm::DenseMap<K, V> &Map2) {
35   llvm::DenseMap<K, V> Result;
36   for (auto &Entry : Map1) {
37     auto It = Map2.find(Entry.first);
38     if (It != Map2.end() && Entry.second == It->second)
39       Result.insert({Entry.first, Entry.second});
40   }
41   return Result;
42 }
43 
44 /// Returns true if and only if `Val1` is equivalent to `Val2`.
45 static bool equivalentValues(QualType Type, Value *Val1, Value *Val2,
46                              Environment::ValueModel &Model) {
47   if (Val1 == Val2)
48     return true;
49 
50   if (auto *IndVal1 = dyn_cast<IndirectionValue>(Val1)) {
51     auto *IndVal2 = cast<IndirectionValue>(Val2);
52     assert(IndVal1->getKind() == IndVal2->getKind());
53     return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc();
54   }
55 
56   return Model.compareEquivalent(Type, *Val1, *Val2);
57 }
58 
59 Environment::Environment(DataflowAnalysisContext &DACtx,
60                          const DeclContext &DeclCtx)
61     : Environment(DACtx) {
62   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
63     for (const auto *ParamDecl : FuncDecl->parameters()) {
64       assert(ParamDecl != nullptr);
65       auto &ParamLoc = createStorageLocation(*ParamDecl);
66       setStorageLocation(*ParamDecl, ParamLoc);
67       if (Value *ParamVal = createValue(ParamDecl->getType()))
68         setValue(ParamLoc, *ParamVal);
69     }
70   }
71 
72   if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
73     if (!MethodDecl->isStatic()) {
74       QualType ThisPointeeType = MethodDecl->getThisObjectType();
75       // FIXME: Add support for union types.
76       if (!ThisPointeeType->isUnionType()) {
77         auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
78         DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
79         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
80           setValue(ThisPointeeLoc, *ThisPointeeVal);
81       }
82     }
83   }
84 }
85 
86 bool Environment::equivalentTo(const Environment &Other,
87                                Environment::ValueModel &Model) const {
88   assert(DACtx == Other.DACtx);
89 
90   if (DeclToLoc != Other.DeclToLoc)
91     return false;
92 
93   if (ExprToLoc != Other.ExprToLoc)
94     return false;
95 
96   if (LocToVal.size() != Other.LocToVal.size())
97     return false;
98 
99   for (auto &Entry : LocToVal) {
100     const StorageLocation *Loc = Entry.first;
101     assert(Loc != nullptr);
102 
103     Value *Val = Entry.second;
104     assert(Val != nullptr);
105 
106     auto It = Other.LocToVal.find(Loc);
107     if (It == Other.LocToVal.end())
108       return false;
109     assert(It->second != nullptr);
110 
111     if (!equivalentValues(Loc->getType(), Val, It->second, Model))
112       return false;
113   }
114 
115   return true;
116 }
117 
118 LatticeJoinEffect Environment::join(const Environment &Other,
119                                     Environment::ValueModel &Model) {
120   assert(DACtx == Other.DACtx);
121 
122   auto Effect = LatticeJoinEffect::Unchanged;
123 
124   const unsigned DeclToLocSizeBefore = DeclToLoc.size();
125   DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
126   if (DeclToLocSizeBefore != DeclToLoc.size())
127     Effect = LatticeJoinEffect::Changed;
128 
129   const unsigned ExprToLocSizeBefore = ExprToLoc.size();
130   ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
131   if (ExprToLocSizeBefore != ExprToLoc.size())
132     Effect = LatticeJoinEffect::Changed;
133 
134   // Move `LocToVal` so that `Environment::ValueModel::merge` can safely assign
135   // values to storage locations while this code iterates over the current
136   // assignments.
137   llvm::DenseMap<const StorageLocation *, Value *> OldLocToVal =
138       std::move(LocToVal);
139   for (auto &Entry : OldLocToVal) {
140     const StorageLocation *Loc = Entry.first;
141     assert(Loc != nullptr);
142 
143     Value *Val = Entry.second;
144     assert(Val != nullptr);
145 
146     auto It = Other.LocToVal.find(Loc);
147     if (It == Other.LocToVal.end())
148       continue;
149     assert(It->second != nullptr);
150 
151     if (equivalentValues(Loc->getType(), Val, It->second, Model)) {
152       LocToVal.insert({Loc, Val});
153       continue;
154     }
155 
156     // FIXME: Consider destroying `MergedValue` immediately if
157     // `ValueModel::merge` returns false to avoid storing unneeded values in
158     // `DACtx`.
159     if (Value *MergedVal = createValue(Loc->getType()))
160       if (Model.merge(Loc->getType(), *Val, *It->second, *MergedVal, *this))
161         LocToVal.insert({Loc, MergedVal});
162   }
163   if (OldLocToVal.size() != LocToVal.size())
164     Effect = LatticeJoinEffect::Changed;
165 
166   return Effect;
167 }
168 
169 StorageLocation &Environment::createStorageLocation(QualType Type) {
170   assert(!Type.isNull());
171   if (Type->isStructureOrClassType() || Type->isUnionType()) {
172     // FIXME: Explore options to avoid eager initialization of fields as some of
173     // them might not be needed for a particular analysis.
174     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
175     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
176       FieldLocs.insert({Field, &createStorageLocation(Field->getType())});
177     }
178     return takeOwnership(
179         std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
180   }
181   return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
182 }
183 
184 StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
185   // Evaluated declarations are always assigned the same storage locations to
186   // ensure that the environment stabilizes across loop iterations. Storage
187   // locations for evaluated declarations are stored in the analysis context.
188   if (auto *Loc = DACtx->getStorageLocation(D))
189     return *Loc;
190   auto &Loc = createStorageLocation(D.getType());
191   DACtx->setStorageLocation(D, Loc);
192   return Loc;
193 }
194 
195 StorageLocation &Environment::createStorageLocation(const Expr &E) {
196   // Evaluated expressions are always assigned the same storage locations to
197   // ensure that the environment stabilizes across loop iterations. Storage
198   // locations for evaluated expressions are stored in the analysis context.
199   if (auto *Loc = DACtx->getStorageLocation(E))
200     return *Loc;
201   auto &Loc = createStorageLocation(E.getType());
202   DACtx->setStorageLocation(E, Loc);
203   return Loc;
204 }
205 
206 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
207   assert(DeclToLoc.find(&D) == DeclToLoc.end());
208   DeclToLoc[&D] = &Loc;
209 }
210 
211 StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
212                                                  SkipPast SP) const {
213   auto It = DeclToLoc.find(&D);
214   return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
215 }
216 
217 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
218   assert(ExprToLoc.find(&E) == ExprToLoc.end());
219   ExprToLoc[&E] = &Loc;
220 }
221 
222 StorageLocation *Environment::getStorageLocation(const Expr &E,
223                                                  SkipPast SP) const {
224   auto It = ExprToLoc.find(&E);
225   return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
226 }
227 
228 StorageLocation *Environment::getThisPointeeStorageLocation() const {
229   return DACtx->getThisPointeeStorageLocation();
230 }
231 
232 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
233   LocToVal[&Loc] = &Val;
234 
235   if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
236     auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
237 
238     const QualType Type = AggregateLoc.getType();
239     assert(Type->isStructureOrClassType());
240 
241     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
242       assert(Field != nullptr);
243       setValue(AggregateLoc.getChild(*Field), StructVal->getChild(*Field));
244     }
245   }
246 }
247 
248 Value *Environment::getValue(const StorageLocation &Loc) const {
249   auto It = LocToVal.find(&Loc);
250   return It == LocToVal.end() ? nullptr : It->second;
251 }
252 
253 Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
254   auto *Loc = getStorageLocation(D, SP);
255   if (Loc == nullptr)
256     return nullptr;
257   return getValue(*Loc);
258 }
259 
260 Value *Environment::getValue(const Expr &E, SkipPast SP) const {
261   auto *Loc = getStorageLocation(E, SP);
262   if (Loc == nullptr)
263     return nullptr;
264   return getValue(*Loc);
265 }
266 
267 Value *Environment::createValue(QualType Type) {
268   llvm::DenseSet<QualType> Visited;
269   return createValueUnlessSelfReferential(Type, Visited);
270 }
271 
272 Value *Environment::createValueUnlessSelfReferential(
273     QualType Type, llvm::DenseSet<QualType> &Visited) {
274   assert(!Type.isNull());
275 
276   if (Type->isIntegerType()) {
277     return &takeOwnership(std::make_unique<IntegerValue>());
278   }
279 
280   if (Type->isReferenceType()) {
281     QualType PointeeType = Type->getAs<ReferenceType>()->getPointeeType();
282     auto &PointeeLoc = createStorageLocation(PointeeType);
283 
284     if (!Visited.contains(PointeeType.getCanonicalType())) {
285       Visited.insert(PointeeType.getCanonicalType());
286       Value *PointeeVal =
287           createValueUnlessSelfReferential(PointeeType, Visited);
288       Visited.erase(PointeeType.getCanonicalType());
289 
290       if (PointeeVal != nullptr)
291         setValue(PointeeLoc, *PointeeVal);
292     }
293 
294     return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
295   }
296 
297   if (Type->isPointerType()) {
298     QualType PointeeType = Type->getAs<PointerType>()->getPointeeType();
299     auto &PointeeLoc = createStorageLocation(PointeeType);
300 
301     if (!Visited.contains(PointeeType.getCanonicalType())) {
302       Visited.insert(PointeeType.getCanonicalType());
303       Value *PointeeVal =
304           createValueUnlessSelfReferential(PointeeType, Visited);
305       Visited.erase(PointeeType.getCanonicalType());
306 
307       if (PointeeVal != nullptr)
308         setValue(PointeeLoc, *PointeeVal);
309     }
310 
311     return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
312   }
313 
314   if (Type->isStructureOrClassType()) {
315     // FIXME: Initialize only fields that are accessed in the context that is
316     // being analyzed.
317     llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
318     for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) {
319       assert(Field != nullptr);
320 
321       QualType FieldType = Field->getType();
322       if (Visited.contains(FieldType.getCanonicalType()))
323         continue;
324 
325       Visited.insert(FieldType.getCanonicalType());
326       FieldValues.insert(
327           {Field, createValueUnlessSelfReferential(FieldType, Visited)});
328       Visited.erase(FieldType.getCanonicalType());
329     }
330 
331     return &takeOwnership(
332         std::make_unique<StructValue>(std::move(FieldValues)));
333   }
334 
335   return nullptr;
336 }
337 
338 StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
339   switch (SP) {
340   case SkipPast::None:
341     return Loc;
342   case SkipPast::Reference:
343     // References cannot be chained so we only need to skip past one level of
344     // indirection.
345     if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
346       return Val->getPointeeLoc();
347     return Loc;
348   case SkipPast::ReferenceThenPointer:
349     StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
350     if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
351       return Val->getPointeeLoc();
352     return LocPastRef;
353   }
354   llvm_unreachable("bad SkipPast kind");
355 }
356 
357 const StorageLocation &Environment::skip(const StorageLocation &Loc,
358                                          SkipPast SP) const {
359   return skip(*const_cast<StorageLocation *>(&Loc), SP);
360 }
361 
362 } // namespace dataflow
363 } // namespace clang
364