1 //===-- Transfer.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 transfer functions that evaluate program statements and
10 //  update an environment accordingly.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/Analysis/FlowSensitive/Transfer.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/AST/OperationKinds.h"
21 #include "clang/AST/Stmt.h"
22 #include "clang/AST/StmtVisitor.h"
23 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
24 #include "clang/Basic/OperatorKinds.h"
25 #include "llvm/ADT/STLExtras.h"
26 #include "llvm/Support/Casting.h"
27 #include <cassert>
28 #include <memory>
29 #include <tuple>
30 
31 namespace clang {
32 namespace dataflow {
33 
34 static const Expr *skipExprWithCleanups(const Expr *E) {
35   if (auto *C = dyn_cast_or_null<ExprWithCleanups>(E))
36     return C->getSubExpr();
37   return E;
38 }
39 
40 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
41 public:
42   TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env)
43       : StmtToEnv(StmtToEnv), Env(Env) {}
44 
45   void VisitBinaryOperator(const BinaryOperator *S) {
46     switch (S->getOpcode()) {
47     case BO_Assign: {
48       // The CFG does not contain `ParenExpr` as top-level statements in basic
49       // blocks, however sub-expressions can still be of that type.
50       assert(S->getLHS() != nullptr);
51       const Expr *LHS = S->getLHS()->IgnoreParens();
52 
53       assert(LHS != nullptr);
54       auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
55       if (LHSLoc == nullptr)
56         break;
57 
58       // The CFG does not contain `ParenExpr` as top-level statements in basic
59       // blocks, however sub-expressions can still be of that type.
60       assert(S->getRHS() != nullptr);
61       const Expr *RHS = S->getRHS()->IgnoreParens();
62 
63       assert(RHS != nullptr);
64       Value *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
65       if (RHSVal == nullptr)
66         break;
67 
68       // Assign a value to the storage location of the left-hand side.
69       Env.setValue(*LHSLoc, *RHSVal);
70 
71       // Assign a storage location for the whole expression.
72       Env.setStorageLocation(*S, *LHSLoc);
73       break;
74     }
75     case BO_LAnd:
76     case BO_LOr: {
77       const Expr *LHS = S->getLHS();
78       assert(LHS != nullptr);
79 
80       const Expr *RHS = S->getRHS();
81       assert(RHS != nullptr);
82 
83       BoolValue *LHSVal =
84           dyn_cast_or_null<BoolValue>(Env.getValue(*LHS, SkipPast::Reference));
85 
86       // `RHS` and `S` might be part of different basic blocks. We need to
87       // access their values from the corresponding environments.
88       BoolValue *RHSVal = nullptr;
89       const Environment *RHSEnv = StmtToEnv.getEnvironment(*RHS);
90       if (RHSEnv != nullptr)
91         RHSVal = dyn_cast_or_null<BoolValue>(
92             RHSEnv->getValue(*RHS, SkipPast::Reference));
93 
94       // Create fresh values for unknown boolean expressions.
95       // FIXME: Consider providing a `GetOrCreateFresh` util in case this style
96       // is expected to be common or make sure that all expressions are assigned
97       // values and drop this.
98       if (LHSVal == nullptr)
99         LHSVal = &Env.takeOwnership(std::make_unique<AtomicBoolValue>());
100       if (RHSVal == nullptr)
101         RHSVal = &Env.takeOwnership(std::make_unique<AtomicBoolValue>());
102 
103       auto &Loc = Env.createStorageLocation(*S);
104       Env.setStorageLocation(*S, Loc);
105       if (S->getOpcode() == BO_LAnd)
106         Env.setValue(Loc, Env.takeOwnership(std::make_unique<ConjunctionValue>(
107                               *LHSVal, *RHSVal)));
108       else
109         Env.setValue(Loc, Env.takeOwnership(std::make_unique<DisjunctionValue>(
110                               *LHSVal, *RHSVal)));
111       break;
112     }
113     default:
114       // FIXME: Add support for BO_EQ, BO_NE.
115       break;
116     }
117   }
118 
119   void VisitDeclRefExpr(const DeclRefExpr *S) {
120     assert(S->getDecl() != nullptr);
121     auto *DeclLoc = Env.getStorageLocation(*S->getDecl(), SkipPast::None);
122     if (DeclLoc == nullptr)
123       return;
124 
125     if (S->getDecl()->getType()->isReferenceType()) {
126       Env.setStorageLocation(*S, *DeclLoc);
127     } else {
128       auto &Loc = Env.createStorageLocation(*S);
129       auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*DeclLoc));
130       Env.setStorageLocation(*S, Loc);
131       Env.setValue(Loc, Val);
132     }
133   }
134 
135   void VisitDeclStmt(const DeclStmt *S) {
136     // Group decls are converted into single decls in the CFG so the cast below
137     // is safe.
138     const auto &D = *cast<VarDecl>(S->getSingleDecl());
139 
140     // Static local vars are already initialized in `Environment`.
141     if (D.hasGlobalStorage())
142       return;
143 
144     auto &Loc = Env.createStorageLocation(D);
145     Env.setStorageLocation(D, Loc);
146 
147     const Expr *InitExpr = D.getInit();
148     if (InitExpr == nullptr) {
149       // No initializer expression - associate `Loc` with a new value.
150       if (Value *Val = Env.createValue(D.getType()))
151         Env.setValue(Loc, *Val);
152       return;
153     }
154 
155     // The CFG does not contain `ParenExpr` as top-level statements in basic
156     // blocks, however sub-expressions can still be of that type.
157     InitExpr = skipExprWithCleanups(D.getInit()->IgnoreParens());
158     assert(InitExpr != nullptr);
159 
160     if (D.getType()->isReferenceType()) {
161       // Initializing a reference variable - do not create a reference to
162       // reference.
163       if (auto *InitExprLoc =
164               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
165         auto &Val =
166             Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
167         Env.setValue(Loc, Val);
168       } else {
169         // FIXME: The initializer expression must always be assigned a value.
170         // Replace this with an assert when we have sufficient coverage of
171         // language features.
172         if (Value *Val = Env.createValue(D.getType()))
173           Env.setValue(Loc, *Val);
174       }
175       return;
176     }
177 
178     if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
179       Env.setValue(Loc, *InitExprVal);
180     } else if (!D.getType()->isStructureOrClassType()) {
181       // FIXME: The initializer expression must always be assigned a value.
182       // Replace this with an assert when we have sufficient coverage of
183       // language features.
184       if (Value *Val = Env.createValue(D.getType()))
185         Env.setValue(Loc, *Val);
186     } else {
187       llvm_unreachable("structs and classes must always be assigned values");
188     }
189   }
190 
191   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
192     // The CFG does not contain `ParenExpr` as top-level statements in basic
193     // blocks, however sub-expressions can still be of that type.
194     assert(S->getSubExpr() != nullptr);
195     const Expr *SubExpr = S->getSubExpr()->IgnoreParens();
196     assert(SubExpr != nullptr);
197 
198     switch (S->getCastKind()) {
199     case CK_LValueToRValue: {
200       auto *SubExprVal = Env.getValue(*SubExpr, SkipPast::Reference);
201       if (SubExprVal == nullptr)
202         break;
203 
204       auto &ExprLoc = Env.createStorageLocation(*S);
205       Env.setStorageLocation(*S, ExprLoc);
206       Env.setValue(ExprLoc, *SubExprVal);
207       break;
208     }
209     case CK_NoOp: {
210       // FIXME: Consider making `Environment::getStorageLocation` skip noop
211       // expressions (this and other similar expressions in the file) instead of
212       // assigning them storage locations.
213       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
214       if (SubExprLoc == nullptr)
215         break;
216 
217       Env.setStorageLocation(*S, *SubExprLoc);
218       break;
219     }
220     default:
221       // FIXME: Add support for CK_UserDefinedConversion,
222       // CK_ConstructorConversion, CK_UncheckedDerivedToBase.
223       break;
224     }
225   }
226 
227   void VisitUnaryOperator(const UnaryOperator *S) {
228     // The CFG does not contain `ParenExpr` as top-level statements in basic
229     // blocks, however sub-expressions can still be of that type.
230     assert(S->getSubExpr() != nullptr);
231     const Expr *SubExpr = S->getSubExpr()->IgnoreParens();
232     assert(SubExpr != nullptr);
233 
234     switch (S->getOpcode()) {
235     case UO_Deref: {
236       // Skip past a reference to handle dereference of a dependent pointer.
237       const auto *SubExprVal = cast_or_null<PointerValue>(
238           Env.getValue(*SubExpr, SkipPast::Reference));
239       if (SubExprVal == nullptr)
240         break;
241 
242       auto &Loc = Env.createStorageLocation(*S);
243       Env.setStorageLocation(*S, Loc);
244       Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
245                             SubExprVal->getPointeeLoc())));
246       break;
247     }
248     case UO_AddrOf: {
249       // Do not form a pointer to a reference. If `SubExpr` is assigned a
250       // `ReferenceValue` then form a value that points to the location of its
251       // pointee.
252       StorageLocation *PointeeLoc =
253           Env.getStorageLocation(*SubExpr, SkipPast::Reference);
254       if (PointeeLoc == nullptr)
255         break;
256 
257       auto &PointerLoc = Env.createStorageLocation(*S);
258       auto &PointerVal =
259           Env.takeOwnership(std::make_unique<PointerValue>(*PointeeLoc));
260       Env.setStorageLocation(*S, PointerLoc);
261       Env.setValue(PointerLoc, PointerVal);
262       break;
263     }
264     case UO_LNot: {
265       auto *SubExprVal =
266           dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr, SkipPast::None));
267       if (SubExprVal == nullptr)
268         break;
269 
270       auto &ExprLoc = Env.createStorageLocation(*S);
271       Env.setStorageLocation(*S, ExprLoc);
272       Env.setValue(ExprLoc, Env.takeOwnership(
273                                 std::make_unique<NegationValue>(*SubExprVal)));
274       break;
275     }
276     default:
277       break;
278     }
279   }
280 
281   void VisitCXXThisExpr(const CXXThisExpr *S) {
282     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
283     assert(ThisPointeeLoc != nullptr);
284 
285     auto &Loc = Env.createStorageLocation(*S);
286     Env.setStorageLocation(*S, Loc);
287     Env.setValue(Loc, Env.takeOwnership(
288                           std::make_unique<PointerValue>(*ThisPointeeLoc)));
289   }
290 
291   void VisitMemberExpr(const MemberExpr *S) {
292     ValueDecl *Member = S->getMemberDecl();
293     assert(Member != nullptr);
294 
295     // FIXME: Consider assigning pointer values to function member expressions.
296     if (Member->isFunctionOrFunctionTemplate())
297       return;
298 
299     if (auto *D = dyn_cast<VarDecl>(Member)) {
300       if (D->hasGlobalStorage()) {
301         auto *VarDeclLoc = Env.getStorageLocation(*D, SkipPast::None);
302         if (VarDeclLoc == nullptr)
303           return;
304 
305         if (VarDeclLoc->getType()->isReferenceType()) {
306           Env.setStorageLocation(*S, *VarDeclLoc);
307         } else {
308           auto &Loc = Env.createStorageLocation(*S);
309           Env.setStorageLocation(*S, Loc);
310           Env.setValue(Loc, Env.takeOwnership(
311                                 std::make_unique<ReferenceValue>(*VarDeclLoc)));
312         }
313         return;
314       }
315     }
316 
317     // The receiver can be either a value or a pointer to a value. Skip past the
318     // indirection to handle both cases.
319     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
320         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
321     if (BaseLoc == nullptr)
322       return;
323 
324     // FIXME: Add support for union types.
325     if (BaseLoc->getType()->isUnionType())
326       return;
327 
328     auto &MemberLoc = BaseLoc->getChild(*Member);
329     if (MemberLoc.getType()->isReferenceType()) {
330       Env.setStorageLocation(*S, MemberLoc);
331     } else {
332       auto &Loc = Env.createStorageLocation(*S);
333       Env.setStorageLocation(*S, Loc);
334       Env.setValue(
335           Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
336     }
337   }
338 
339   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
340     const Expr *InitExpr = S->getExpr();
341     assert(InitExpr != nullptr);
342 
343     Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
344     if (InitExprVal == nullptr)
345       return;
346 
347     const FieldDecl *Field = S->getField();
348     assert(Field != nullptr);
349 
350     auto &ThisLoc =
351         *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
352     auto &FieldLoc = ThisLoc.getChild(*Field);
353     Env.setValue(FieldLoc, *InitExprVal);
354   }
355 
356   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
357     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
358     assert(ConstructorDecl != nullptr);
359 
360     if (ConstructorDecl->isCopyOrMoveConstructor()) {
361       assert(S->getNumArgs() == 1);
362 
363       const Expr *Arg = S->getArg(0);
364       assert(Arg != nullptr);
365 
366       if (S->isElidable()) {
367         auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
368         if (ArgLoc == nullptr)
369           return;
370 
371         Env.setStorageLocation(*S, *ArgLoc);
372       } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
373         auto &Loc = Env.createStorageLocation(*S);
374         Env.setStorageLocation(*S, Loc);
375         Env.setValue(Loc, *ArgVal);
376       }
377       return;
378     }
379 
380     auto &Loc = Env.createStorageLocation(*S);
381     Env.setStorageLocation(*S, Loc);
382     if (Value *Val = Env.createValue(S->getType()))
383       Env.setValue(Loc, *Val);
384   }
385 
386   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
387     if (S->getOperator() == OO_Equal) {
388       assert(S->getNumArgs() == 2);
389 
390       const Expr *Arg0 = S->getArg(0);
391       assert(Arg0 != nullptr);
392 
393       const Expr *Arg1 = S->getArg(1);
394       assert(Arg1 != nullptr);
395 
396       // Evaluate only copy and move assignment operators.
397       auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
398       auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
399       if (Arg0Type != Arg1Type)
400         return;
401 
402       auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
403       if (ObjectLoc == nullptr)
404         return;
405 
406       auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
407       if (Val == nullptr)
408         return;
409 
410       Env.setValue(*ObjectLoc, *Val);
411     }
412   }
413 
414   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
415     if (S->getCastKind() == CK_ConstructorConversion) {
416       // The CFG does not contain `ParenExpr` as top-level statements in basic
417       // blocks, however sub-expressions can still be of that type.
418       assert(S->getSubExpr() != nullptr);
419       const Expr *SubExpr = S->getSubExpr();
420       assert(SubExpr != nullptr);
421 
422       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
423       if (SubExprLoc == nullptr)
424         return;
425 
426       Env.setStorageLocation(*S, *SubExprLoc);
427     }
428   }
429 
430   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
431     auto &Loc = Env.createStorageLocation(*S);
432     Env.setStorageLocation(*S, Loc);
433     if (Value *Val = Env.createValue(S->getType()))
434       Env.setValue(Loc, *Val);
435   }
436 
437   void VisitCallExpr(const CallExpr *S) {
438     if (S->isCallToStdMove()) {
439       assert(S->getNumArgs() == 1);
440 
441       const Expr *Arg = S->getArg(0);
442       assert(Arg != nullptr);
443 
444       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
445       if (ArgLoc == nullptr)
446         return;
447 
448       Env.setStorageLocation(*S, *ArgLoc);
449     }
450   }
451 
452   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
453     const Expr *SubExpr = S->getSubExpr();
454     assert(SubExpr != nullptr);
455 
456     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
457     if (SubExprLoc == nullptr)
458       return;
459 
460     Env.setStorageLocation(*S, *SubExprLoc);
461   }
462 
463   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
464     const Expr *SubExpr = S->getSubExpr();
465     assert(SubExpr != nullptr);
466 
467     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
468     if (SubExprLoc == nullptr)
469       return;
470 
471     Env.setStorageLocation(*S, *SubExprLoc);
472   }
473 
474   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
475     if (S->getCastKind() == CK_NoOp) {
476       const Expr *SubExpr = S->getSubExpr();
477       assert(SubExpr != nullptr);
478 
479       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
480       if (SubExprLoc == nullptr)
481         return;
482 
483       Env.setStorageLocation(*S, *SubExprLoc);
484     }
485   }
486 
487   void VisitConditionalOperator(const ConditionalOperator *S) {
488     // FIXME: Revisit this once flow conditions are added to the framework. For
489     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
490     // condition.
491     auto &Loc = Env.createStorageLocation(*S);
492     Env.setStorageLocation(*S, Loc);
493     if (Value *Val = Env.createValue(S->getType()))
494       Env.setValue(Loc, *Val);
495   }
496 
497   void VisitInitListExpr(const InitListExpr *S) {
498     QualType Type = S->getType();
499 
500     auto &Loc = Env.createStorageLocation(*S);
501     Env.setStorageLocation(*S, Loc);
502 
503     auto *Val = Env.createValue(Type);
504     if (Val == nullptr)
505       return;
506 
507     Env.setValue(Loc, *Val);
508 
509     if (Type->isStructureOrClassType()) {
510       for (auto IT : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) {
511         const FieldDecl *Field = std::get<0>(IT);
512         assert(Field != nullptr);
513 
514         const Expr *Init = std::get<1>(IT);
515         assert(Init != nullptr);
516 
517         if (Value *InitVal = Env.getValue(*Init, SkipPast::None))
518           cast<StructValue>(Val)->setChild(*Field, *InitVal);
519       }
520     }
521     // FIXME: Implement array initialization.
522   }
523 
524   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
525     auto &Loc = Env.createStorageLocation(*S);
526     Env.setStorageLocation(*S, Loc);
527     Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
528   }
529 
530 private:
531   const StmtToEnvMap &StmtToEnv;
532   Environment &Env;
533 };
534 
535 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
536   assert(!isa<ParenExpr>(&S));
537   TransferVisitor(StmtToEnv, Env).Visit(&S);
538 }
539 
540 } // namespace dataflow
541 } // namespace clang
542