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