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     // FIXME: Add support for group decls, e.g: `int a, b;`
91     if (S->isSingleDecl()) {
92       if (const auto *D = dyn_cast<VarDecl>(S->getSingleDecl())) {
93         visitVarDecl(*D);
94       }
95     }
96   }
97 
98   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
99     // The CFG does not contain `ParenExpr` as top-level statements in basic
100     // blocks, however sub-expressions can still be of that type.
101     assert(S->getSubExpr() != nullptr);
102     const Expr *SubExpr = S->getSubExpr()->IgnoreParens();
103     assert(SubExpr != nullptr);
104 
105     switch (S->getCastKind()) {
106     case CK_LValueToRValue: {
107       auto *SubExprVal = Env.getValue(*SubExpr, SkipPast::Reference);
108       if (SubExprVal == nullptr)
109         break;
110 
111       auto &ExprLoc = Env.createStorageLocation(*S);
112       Env.setStorageLocation(*S, ExprLoc);
113       Env.setValue(ExprLoc, *SubExprVal);
114       break;
115     }
116     case CK_NoOp: {
117       // FIXME: Consider making `Environment::getStorageLocation` skip noop
118       // expressions (this and other similar expressions in the file) instead of
119       // assigning them storage locations.
120       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
121       if (SubExprLoc == nullptr)
122         break;
123 
124       Env.setStorageLocation(*S, *SubExprLoc);
125       break;
126     }
127     default:
128       // FIXME: Add support for CK_UserDefinedConversion,
129       // CK_ConstructorConversion, CK_UncheckedDerivedToBase.
130       break;
131     }
132   }
133 
134   void VisitUnaryOperator(const UnaryOperator *S) {
135     if (S->getOpcode() == UO_Deref) {
136       assert(S->getSubExpr() != nullptr);
137       const auto *SubExprVal = cast_or_null<PointerValue>(
138           Env.getValue(*S->getSubExpr(), SkipPast::Reference));
139       if (SubExprVal == nullptr)
140         return;
141 
142       auto &Loc = Env.createStorageLocation(*S);
143       Env.setStorageLocation(*S, Loc);
144       Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
145                             SubExprVal->getPointeeLoc())));
146     }
147     // FIXME: Add support for UO_AddrOf, UO_LNot.
148   }
149 
150   void VisitCXXThisExpr(const CXXThisExpr *S) {
151     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
152     assert(ThisPointeeLoc != nullptr);
153 
154     auto &Loc = Env.createStorageLocation(*S);
155     Env.setStorageLocation(*S, Loc);
156     Env.setValue(Loc, Env.takeOwnership(
157                           std::make_unique<PointerValue>(*ThisPointeeLoc)));
158   }
159 
160   void VisitMemberExpr(const MemberExpr *S) {
161     ValueDecl *Member = S->getMemberDecl();
162     assert(Member != nullptr);
163 
164     // FIXME: Consider assigning pointer values to function member expressions.
165     if (Member->isFunctionOrFunctionTemplate())
166       return;
167 
168     // The receiver can be either a value or a pointer to a value. Skip past the
169     // indirection to handle both cases.
170     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
171         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
172     if (BaseLoc == nullptr)
173       return;
174 
175     // FIXME: Add support for union types.
176     if (BaseLoc->getType()->isUnionType())
177       return;
178 
179     auto &MemberLoc = BaseLoc->getChild(*Member);
180     if (MemberLoc.getType()->isReferenceType()) {
181       Env.setStorageLocation(*S, MemberLoc);
182     } else {
183       auto &Loc = Env.createStorageLocation(*S);
184       Env.setStorageLocation(*S, Loc);
185       Env.setValue(
186           Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
187     }
188   }
189 
190   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
191     const Expr *InitExpr = S->getExpr();
192     assert(InitExpr != nullptr);
193 
194     Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
195     if (InitExprVal == nullptr)
196       return;
197 
198     const FieldDecl *Field = S->getField();
199     assert(Field != nullptr);
200 
201     auto &ThisLoc =
202         *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
203     auto &FieldLoc = ThisLoc.getChild(*Field);
204     Env.setValue(FieldLoc, *InitExprVal);
205   }
206 
207   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
208     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
209     assert(ConstructorDecl != nullptr);
210 
211     if (ConstructorDecl->isCopyOrMoveConstructor()) {
212       assert(S->getNumArgs() == 1);
213 
214       const Expr *Arg = S->getArg(0);
215       assert(Arg != nullptr);
216 
217       if (S->isElidable()) {
218         auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
219         if (ArgLoc == nullptr)
220           return;
221 
222         Env.setStorageLocation(*S, *ArgLoc);
223       } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
224         auto &Loc = Env.createStorageLocation(*S);
225         Env.setStorageLocation(*S, Loc);
226         Env.setValue(Loc, *ArgVal);
227       }
228       return;
229     }
230 
231     auto &Loc = Env.createStorageLocation(*S);
232     Env.setStorageLocation(*S, Loc);
233     Env.initValueInStorageLocation(Loc, S->getType());
234   }
235 
236   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
237     if (S->getOperator() == OO_Equal) {
238       assert(S->getNumArgs() == 2);
239 
240       const Expr *Arg0 = S->getArg(0);
241       assert(Arg0 != nullptr);
242 
243       const Expr *Arg1 = S->getArg(1);
244       assert(Arg1 != nullptr);
245 
246       // Evaluate only copy and move assignment operators.
247       auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
248       auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
249       if (Arg0Type != Arg1Type)
250         return;
251 
252       auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
253       if (ObjectLoc == nullptr)
254         return;
255 
256       auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
257       if (Val == nullptr)
258         return;
259 
260       Env.setValue(*ObjectLoc, *Val);
261     }
262   }
263 
264   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
265     if (S->getCastKind() == CK_ConstructorConversion) {
266       // The CFG does not contain `ParenExpr` as top-level statements in basic
267       // blocks, however sub-expressions can still be of that type.
268       assert(S->getSubExpr() != nullptr);
269       const Expr *SubExpr = S->getSubExpr();
270       assert(SubExpr != nullptr);
271 
272       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
273       if (SubExprLoc == nullptr)
274         return;
275 
276       Env.setStorageLocation(*S, *SubExprLoc);
277     }
278   }
279 
280   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
281     auto &Loc = Env.createStorageLocation(*S);
282     Env.setStorageLocation(*S, Loc);
283     Env.initValueInStorageLocation(Loc, S->getType());
284   }
285 
286   void VisitCallExpr(const CallExpr *S) {
287     if (S->isCallToStdMove()) {
288       assert(S->getNumArgs() == 1);
289 
290       const Expr *Arg = S->getArg(0);
291       assert(Arg != nullptr);
292 
293       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
294       if (ArgLoc == nullptr)
295         return;
296 
297       Env.setStorageLocation(*S, *ArgLoc);
298     }
299   }
300 
301   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
302     const Expr *SubExpr = S->getSubExpr();
303     assert(SubExpr != nullptr);
304 
305     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
306     if (SubExprLoc == nullptr)
307       return;
308 
309     Env.setStorageLocation(*S, *SubExprLoc);
310   }
311 
312   // FIXME: Add support for:
313   // - CXXBindTemporaryExpr
314   // - CXXBoolLiteralExpr
315   // - CXXStaticCastExpr
316 
317 private:
318   void visitVarDecl(const VarDecl &D) {
319     auto &Loc = Env.createStorageLocation(D);
320     Env.setStorageLocation(D, Loc);
321 
322     const Expr *InitExpr = D.getInit();
323     if (InitExpr == nullptr) {
324       // No initializer expression - associate `Loc` with a new value.
325       Env.initValueInStorageLocation(Loc, D.getType());
326       return;
327     }
328 
329     // The CFG does not contain `ParenExpr` as top-level statements in basic
330     // blocks, however sub-expressions can still be of that type.
331     InitExpr = skipExprWithCleanups(D.getInit()->IgnoreParens());
332     assert(InitExpr != nullptr);
333 
334     if (D.getType()->isReferenceType()) {
335       // Initializing a reference variable - do not create a reference to
336       // reference.
337       if (auto *InitExprLoc =
338               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
339         auto &Val =
340             Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
341         Env.setValue(Loc, Val);
342       } else {
343         // FIXME: The initializer expression must always be assigned a value.
344         // Replace this with an assert when we have sufficient coverage of
345         // language features.
346         Env.initValueInStorageLocation(Loc, D.getType());
347       }
348       return;
349     }
350 
351     if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
352       Env.setValue(Loc, *InitExprVal);
353     } else if (!D.getType()->isStructureOrClassType()) {
354       // FIXME: The initializer expression must always be assigned a value.
355       // Replace this with an assert when we have sufficient coverage of
356       // language features.
357       Env.initValueInStorageLocation(Loc, D.getType());
358     } else {
359       llvm_unreachable("structs and classes must always be assigned values");
360     }
361   }
362 
363   Environment &Env;
364 };
365 
366 void transfer(const Stmt &S, Environment &Env) {
367   assert(!isa<ParenExpr>(&S));
368   TransferVisitor(Env).Visit(&S);
369 }
370 
371 } // namespace dataflow
372 } // namespace clang
373