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/Support/Casting.h"
26 #include <cassert>
27 #include <memory>
28 
29 namespace clang {
30 namespace dataflow {
31 
32 static const Expr *skipExprWithCleanups(const Expr *E) {
33   if (auto *C = dyn_cast_or_null<ExprWithCleanups>(E))
34     return C->getSubExpr();
35   return E;
36 }
37 
38 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
39 public:
40   TransferVisitor(Environment &Env) : Env(Env) {}
41 
42   void VisitBinaryOperator(const BinaryOperator *S) {
43     if (S->getOpcode() == BO_Assign) {
44       // The CFG does not contain `ParenExpr` as top-level statements in basic
45       // blocks, however sub-expressions can still be of that type.
46       assert(S->getLHS() != nullptr);
47       const Expr *LHS = S->getLHS()->IgnoreParens();
48 
49       assert(LHS != nullptr);
50       auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
51       if (LHSLoc == nullptr)
52         return;
53 
54       // The CFG does not contain `ParenExpr` as top-level statements in basic
55       // blocks, however sub-expressions can still be of that type.
56       assert(S->getRHS() != nullptr);
57       const Expr *RHS = S->getRHS()->IgnoreParens();
58 
59       assert(RHS != nullptr);
60       Value *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
61       if (RHSVal == nullptr)
62         return;
63 
64       // Assign a value to the storage location of the left-hand side.
65       Env.setValue(*LHSLoc, *RHSVal);
66 
67       // Assign a storage location for the whole expression.
68       Env.setStorageLocation(*S, *LHSLoc);
69     }
70     // FIXME: Add support for BO_EQ, BO_NE.
71   }
72 
73   void VisitDeclRefExpr(const DeclRefExpr *S) {
74     assert(S->getDecl() != nullptr);
75     auto *DeclLoc = Env.getStorageLocation(*S->getDecl(), SkipPast::None);
76     if (DeclLoc == nullptr)
77       return;
78 
79     if (S->getDecl()->getType()->isReferenceType()) {
80       Env.setStorageLocation(*S, *DeclLoc);
81     } else {
82       auto &Loc = Env.createStorageLocation(*S);
83       auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*DeclLoc));
84       Env.setStorageLocation(*S, Loc);
85       Env.setValue(Loc, Val);
86     }
87   }
88 
89   void VisitDeclStmt(const DeclStmt *S) {
90     // Group decls are converted into single decls in the CFG so the cast below
91     // is safe.
92     const auto &D = *cast<VarDecl>(S->getSingleDecl());
93     auto &Loc = Env.createStorageLocation(D);
94     Env.setStorageLocation(D, Loc);
95 
96     const Expr *InitExpr = D.getInit();
97     if (InitExpr == nullptr) {
98       // No initializer expression - associate `Loc` with a new value.
99       if (Value *Val = Env.createValue(D.getType()))
100         Env.setValue(Loc, *Val);
101       return;
102     }
103 
104     // The CFG does not contain `ParenExpr` as top-level statements in basic
105     // blocks, however sub-expressions can still be of that type.
106     InitExpr = skipExprWithCleanups(D.getInit()->IgnoreParens());
107     assert(InitExpr != nullptr);
108 
109     if (D.getType()->isReferenceType()) {
110       // Initializing a reference variable - do not create a reference to
111       // reference.
112       if (auto *InitExprLoc =
113               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
114         auto &Val =
115             Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
116         Env.setValue(Loc, Val);
117       } else {
118         // FIXME: The initializer expression must always be assigned a value.
119         // Replace this with an assert when we have sufficient coverage of
120         // language features.
121         if (Value *Val = Env.createValue(D.getType()))
122           Env.setValue(Loc, *Val);
123       }
124       return;
125     }
126 
127     if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
128       Env.setValue(Loc, *InitExprVal);
129     } else if (!D.getType()->isStructureOrClassType()) {
130       // FIXME: The initializer expression must always be assigned a value.
131       // Replace this with an assert when we have sufficient coverage of
132       // language features.
133       if (Value *Val = Env.createValue(D.getType()))
134         Env.setValue(Loc, *Val);
135     } else {
136       llvm_unreachable("structs and classes must always be assigned values");
137     }
138   }
139 
140   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
141     // The CFG does not contain `ParenExpr` as top-level statements in basic
142     // blocks, however sub-expressions can still be of that type.
143     assert(S->getSubExpr() != nullptr);
144     const Expr *SubExpr = S->getSubExpr()->IgnoreParens();
145     assert(SubExpr != nullptr);
146 
147     switch (S->getCastKind()) {
148     case CK_LValueToRValue: {
149       auto *SubExprVal = Env.getValue(*SubExpr, SkipPast::Reference);
150       if (SubExprVal == nullptr)
151         break;
152 
153       auto &ExprLoc = Env.createStorageLocation(*S);
154       Env.setStorageLocation(*S, ExprLoc);
155       Env.setValue(ExprLoc, *SubExprVal);
156       break;
157     }
158     case CK_NoOp: {
159       // FIXME: Consider making `Environment::getStorageLocation` skip noop
160       // expressions (this and other similar expressions in the file) instead of
161       // assigning them storage locations.
162       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
163       if (SubExprLoc == nullptr)
164         break;
165 
166       Env.setStorageLocation(*S, *SubExprLoc);
167       break;
168     }
169     default:
170       // FIXME: Add support for CK_UserDefinedConversion,
171       // CK_ConstructorConversion, CK_UncheckedDerivedToBase.
172       break;
173     }
174   }
175 
176   void VisitUnaryOperator(const UnaryOperator *S) {
177     // The CFG does not contain `ParenExpr` as top-level statements in basic
178     // blocks, however sub-expressions can still be of that type.
179     assert(S->getSubExpr() != nullptr);
180     const Expr *SubExpr = S->getSubExpr()->IgnoreParens();
181     assert(SubExpr != nullptr);
182 
183     switch (S->getOpcode()) {
184     case UO_Deref: {
185       const auto *SubExprVal = cast_or_null<PointerValue>(
186           Env.getValue(*SubExpr, SkipPast::Reference));
187       if (SubExprVal == nullptr)
188         break;
189 
190       auto &Loc = Env.createStorageLocation(*S);
191       Env.setStorageLocation(*S, Loc);
192       Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
193                             SubExprVal->getPointeeLoc())));
194       break;
195     }
196     case UO_AddrOf: {
197       // Do not form a pointer to a reference. If `SubExpr` is assigned a
198       // `ReferenceValue` then form a value that points to the location of its
199       // pointee.
200       StorageLocation *PointeeLoc =
201           Env.getStorageLocation(*SubExpr, SkipPast::Reference);
202       if (PointeeLoc == nullptr)
203         break;
204 
205       auto &PointerLoc = Env.createStorageLocation(*S);
206       auto &PointerVal =
207           Env.takeOwnership(std::make_unique<PointerValue>(*PointeeLoc));
208       Env.setStorageLocation(*S, PointerLoc);
209       Env.setValue(PointerLoc, PointerVal);
210       break;
211     }
212     default:
213       // FIXME: Add support for UO_LNot.
214       break;
215     }
216   }
217 
218   void VisitCXXThisExpr(const CXXThisExpr *S) {
219     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
220     assert(ThisPointeeLoc != nullptr);
221 
222     auto &Loc = Env.createStorageLocation(*S);
223     Env.setStorageLocation(*S, Loc);
224     Env.setValue(Loc, Env.takeOwnership(
225                           std::make_unique<PointerValue>(*ThisPointeeLoc)));
226   }
227 
228   void VisitMemberExpr(const MemberExpr *S) {
229     ValueDecl *Member = S->getMemberDecl();
230     assert(Member != nullptr);
231 
232     // FIXME: Consider assigning pointer values to function member expressions.
233     if (Member->isFunctionOrFunctionTemplate())
234       return;
235 
236     // The receiver can be either a value or a pointer to a value. Skip past the
237     // indirection to handle both cases.
238     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
239         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
240     if (BaseLoc == nullptr)
241       return;
242 
243     // FIXME: Add support for union types.
244     if (BaseLoc->getType()->isUnionType())
245       return;
246 
247     auto &MemberLoc = BaseLoc->getChild(*Member);
248     if (MemberLoc.getType()->isReferenceType()) {
249       Env.setStorageLocation(*S, MemberLoc);
250     } else {
251       auto &Loc = Env.createStorageLocation(*S);
252       Env.setStorageLocation(*S, Loc);
253       Env.setValue(
254           Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
255     }
256   }
257 
258   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
259     const Expr *InitExpr = S->getExpr();
260     assert(InitExpr != nullptr);
261 
262     Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
263     if (InitExprVal == nullptr)
264       return;
265 
266     const FieldDecl *Field = S->getField();
267     assert(Field != nullptr);
268 
269     auto &ThisLoc =
270         *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
271     auto &FieldLoc = ThisLoc.getChild(*Field);
272     Env.setValue(FieldLoc, *InitExprVal);
273   }
274 
275   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
276     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
277     assert(ConstructorDecl != nullptr);
278 
279     if (ConstructorDecl->isCopyOrMoveConstructor()) {
280       assert(S->getNumArgs() == 1);
281 
282       const Expr *Arg = S->getArg(0);
283       assert(Arg != nullptr);
284 
285       if (S->isElidable()) {
286         auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
287         if (ArgLoc == nullptr)
288           return;
289 
290         Env.setStorageLocation(*S, *ArgLoc);
291       } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
292         auto &Loc = Env.createStorageLocation(*S);
293         Env.setStorageLocation(*S, Loc);
294         Env.setValue(Loc, *ArgVal);
295       }
296       return;
297     }
298 
299     auto &Loc = Env.createStorageLocation(*S);
300     Env.setStorageLocation(*S, Loc);
301     if (Value *Val = Env.createValue(S->getType()))
302       Env.setValue(Loc, *Val);
303   }
304 
305   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
306     if (S->getOperator() == OO_Equal) {
307       assert(S->getNumArgs() == 2);
308 
309       const Expr *Arg0 = S->getArg(0);
310       assert(Arg0 != nullptr);
311 
312       const Expr *Arg1 = S->getArg(1);
313       assert(Arg1 != nullptr);
314 
315       // Evaluate only copy and move assignment operators.
316       auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
317       auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
318       if (Arg0Type != Arg1Type)
319         return;
320 
321       auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
322       if (ObjectLoc == nullptr)
323         return;
324 
325       auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
326       if (Val == nullptr)
327         return;
328 
329       Env.setValue(*ObjectLoc, *Val);
330     }
331   }
332 
333   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
334     if (S->getCastKind() == CK_ConstructorConversion) {
335       // The CFG does not contain `ParenExpr` as top-level statements in basic
336       // blocks, however sub-expressions can still be of that type.
337       assert(S->getSubExpr() != nullptr);
338       const Expr *SubExpr = S->getSubExpr();
339       assert(SubExpr != nullptr);
340 
341       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
342       if (SubExprLoc == nullptr)
343         return;
344 
345       Env.setStorageLocation(*S, *SubExprLoc);
346     }
347   }
348 
349   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
350     auto &Loc = Env.createStorageLocation(*S);
351     Env.setStorageLocation(*S, Loc);
352     if (Value *Val = Env.createValue(S->getType()))
353       Env.setValue(Loc, *Val);
354   }
355 
356   void VisitCallExpr(const CallExpr *S) {
357     if (S->isCallToStdMove()) {
358       assert(S->getNumArgs() == 1);
359 
360       const Expr *Arg = S->getArg(0);
361       assert(Arg != nullptr);
362 
363       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
364       if (ArgLoc == nullptr)
365         return;
366 
367       Env.setStorageLocation(*S, *ArgLoc);
368     }
369   }
370 
371   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
372     const Expr *SubExpr = S->getSubExpr();
373     assert(SubExpr != nullptr);
374 
375     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
376     if (SubExprLoc == nullptr)
377       return;
378 
379     Env.setStorageLocation(*S, *SubExprLoc);
380   }
381 
382   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
383     const Expr *SubExpr = S->getSubExpr();
384     assert(SubExpr != nullptr);
385 
386     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
387     if (SubExprLoc == nullptr)
388       return;
389 
390     Env.setStorageLocation(*S, *SubExprLoc);
391   }
392 
393   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
394     if (S->getCastKind() == CK_NoOp) {
395       const Expr *SubExpr = S->getSubExpr();
396       assert(SubExpr != nullptr);
397 
398       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
399       if (SubExprLoc == nullptr)
400         return;
401 
402       Env.setStorageLocation(*S, *SubExprLoc);
403     }
404   }
405 
406   // FIXME: Add support for:
407   // - CXXBoolLiteralExpr
408 
409 private:
410   Environment &Env;
411 };
412 
413 void transfer(const Stmt &S, Environment &Env) {
414   assert(!isa<ParenExpr>(&S));
415   TransferVisitor(Env).Visit(&S);
416 }
417 
418 } // namespace dataflow
419 } // namespace clang
420