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       // Assign a value to the storage location of the object.
386       Env.setValue(*ObjectLoc, *Val);
387 
388       // FIXME: Add a test for the value of the whole expression.
389       // Assign a storage location for the whole expression.
390       Env.setStorageLocation(*S, *ObjectLoc);
391     }
392   }
393 
394   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
395     if (S->getCastKind() == CK_ConstructorConversion) {
396       // The CFG does not contain `ParenExpr` as top-level statements in basic
397       // blocks, however sub-expressions can still be of that type.
398       assert(S->getSubExpr() != nullptr);
399       const Expr *SubExpr = S->getSubExpr();
400       assert(SubExpr != nullptr);
401 
402       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
403       if (SubExprLoc == nullptr)
404         return;
405 
406       Env.setStorageLocation(*S, *SubExprLoc);
407     }
408   }
409 
410   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
411     auto &Loc = Env.createStorageLocation(*S);
412     Env.setStorageLocation(*S, Loc);
413     if (Value *Val = Env.createValue(S->getType()))
414       Env.setValue(Loc, *Val);
415   }
416 
417   void VisitCallExpr(const CallExpr *S) {
418     if (S->isCallToStdMove()) {
419       assert(S->getNumArgs() == 1);
420 
421       const Expr *Arg = S->getArg(0);
422       assert(Arg != nullptr);
423 
424       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
425       if (ArgLoc == nullptr)
426         return;
427 
428       Env.setStorageLocation(*S, *ArgLoc);
429     }
430   }
431 
432   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
433     const Expr *SubExpr = S->getSubExpr();
434     assert(SubExpr != nullptr);
435 
436     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
437     if (SubExprLoc == nullptr)
438       return;
439 
440     Env.setStorageLocation(*S, *SubExprLoc);
441   }
442 
443   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
444     const Expr *SubExpr = S->getSubExpr();
445     assert(SubExpr != nullptr);
446 
447     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
448     if (SubExprLoc == nullptr)
449       return;
450 
451     Env.setStorageLocation(*S, *SubExprLoc);
452   }
453 
454   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
455     if (S->getCastKind() == CK_NoOp) {
456       const Expr *SubExpr = S->getSubExpr();
457       assert(SubExpr != nullptr);
458 
459       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
460       if (SubExprLoc == nullptr)
461         return;
462 
463       Env.setStorageLocation(*S, *SubExprLoc);
464     }
465   }
466 
467   void VisitConditionalOperator(const ConditionalOperator *S) {
468     // FIXME: Revisit this once flow conditions are added to the framework. For
469     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
470     // condition.
471     auto &Loc = Env.createStorageLocation(*S);
472     Env.setStorageLocation(*S, Loc);
473     if (Value *Val = Env.createValue(S->getType()))
474       Env.setValue(Loc, *Val);
475   }
476 
477   void VisitInitListExpr(const InitListExpr *S) {
478     QualType Type = S->getType();
479 
480     auto &Loc = Env.createStorageLocation(*S);
481     Env.setStorageLocation(*S, Loc);
482 
483     auto *Val = Env.createValue(Type);
484     if (Val == nullptr)
485       return;
486 
487     Env.setValue(Loc, *Val);
488 
489     if (Type->isStructureOrClassType()) {
490       for (auto IT : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) {
491         const FieldDecl *Field = std::get<0>(IT);
492         assert(Field != nullptr);
493 
494         const Expr *Init = std::get<1>(IT);
495         assert(Init != nullptr);
496 
497         if (Value *InitVal = Env.getValue(*Init, SkipPast::None))
498           cast<StructValue>(Val)->setChild(*Field, *InitVal);
499       }
500     }
501     // FIXME: Implement array initialization.
502   }
503 
504   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
505     auto &Loc = Env.createStorageLocation(*S);
506     Env.setStorageLocation(*S, Loc);
507     Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
508   }
509 
510 private:
511   BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
512     // `SubExpr` and its parent logic operator might be part of different basic
513     // blocks. We try to access the value that is assigned to `SubExpr` in the
514     // corresponding environment.
515     if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
516       if (auto *Val = dyn_cast_or_null<BoolValue>(
517               SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
518         return *Val;
519     }
520 
521     // Sub-expressions that are logic operators are not added in basic blocks
522     // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
523     // operator, it isn't evaluated and assigned a value yet. In that case, we
524     // need to first visit `SubExpr` and then try to get the value that gets
525     // assigned to it.
526     Visit(&SubExpr);
527     if (auto *Val = dyn_cast_or_null<BoolValue>(
528             Env.getValue(SubExpr, SkipPast::Reference)))
529       return *Val;
530 
531     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
532     // boolean value for it.
533     return Env.makeAtomicBoolValue();
534   }
535 
536   const StmtToEnvMap &StmtToEnv;
537   Environment &Env;
538 };
539 
540 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
541   assert(!isa<ParenExpr>(&S));
542   TransferVisitor(StmtToEnv, Env).Visit(&S);
543 }
544 
545 } // namespace dataflow
546 } // namespace clang
547