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