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       // Skip past a reference to handle dereference of a dependent pointer.
186       const auto *SubExprVal = cast_or_null<PointerValue>(
187           Env.getValue(*SubExpr, SkipPast::Reference));
188       if (SubExprVal == nullptr)
189         break;
190 
191       auto &Loc = Env.createStorageLocation(*S);
192       Env.setStorageLocation(*S, Loc);
193       Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
194                             SubExprVal->getPointeeLoc())));
195       break;
196     }
197     case UO_AddrOf: {
198       // Do not form a pointer to a reference. If `SubExpr` is assigned a
199       // `ReferenceValue` then form a value that points to the location of its
200       // pointee.
201       StorageLocation *PointeeLoc =
202           Env.getStorageLocation(*SubExpr, SkipPast::Reference);
203       if (PointeeLoc == nullptr)
204         break;
205 
206       auto &PointerLoc = Env.createStorageLocation(*S);
207       auto &PointerVal =
208           Env.takeOwnership(std::make_unique<PointerValue>(*PointeeLoc));
209       Env.setStorageLocation(*S, PointerLoc);
210       Env.setValue(PointerLoc, PointerVal);
211       break;
212     }
213     default:
214       // FIXME: Add support for UO_LNot.
215       break;
216     }
217   }
218 
219   void VisitCXXThisExpr(const CXXThisExpr *S) {
220     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
221     assert(ThisPointeeLoc != nullptr);
222 
223     auto &Loc = Env.createStorageLocation(*S);
224     Env.setStorageLocation(*S, Loc);
225     Env.setValue(Loc, Env.takeOwnership(
226                           std::make_unique<PointerValue>(*ThisPointeeLoc)));
227   }
228 
229   void VisitMemberExpr(const MemberExpr *S) {
230     ValueDecl *Member = S->getMemberDecl();
231     assert(Member != nullptr);
232 
233     // FIXME: Consider assigning pointer values to function member expressions.
234     if (Member->isFunctionOrFunctionTemplate())
235       return;
236 
237     // The receiver can be either a value or a pointer to a value. Skip past the
238     // indirection to handle both cases.
239     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
240         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
241     if (BaseLoc == nullptr)
242       return;
243 
244     // FIXME: Add support for union types.
245     if (BaseLoc->getType()->isUnionType())
246       return;
247 
248     auto &MemberLoc = BaseLoc->getChild(*Member);
249     if (MemberLoc.getType()->isReferenceType()) {
250       Env.setStorageLocation(*S, MemberLoc);
251     } else {
252       auto &Loc = Env.createStorageLocation(*S);
253       Env.setStorageLocation(*S, Loc);
254       Env.setValue(
255           Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
256     }
257   }
258 
259   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
260     const Expr *InitExpr = S->getExpr();
261     assert(InitExpr != nullptr);
262 
263     Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
264     if (InitExprVal == nullptr)
265       return;
266 
267     const FieldDecl *Field = S->getField();
268     assert(Field != nullptr);
269 
270     auto &ThisLoc =
271         *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
272     auto &FieldLoc = ThisLoc.getChild(*Field);
273     Env.setValue(FieldLoc, *InitExprVal);
274   }
275 
276   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
277     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
278     assert(ConstructorDecl != nullptr);
279 
280     if (ConstructorDecl->isCopyOrMoveConstructor()) {
281       assert(S->getNumArgs() == 1);
282 
283       const Expr *Arg = S->getArg(0);
284       assert(Arg != nullptr);
285 
286       if (S->isElidable()) {
287         auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
288         if (ArgLoc == nullptr)
289           return;
290 
291         Env.setStorageLocation(*S, *ArgLoc);
292       } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
293         auto &Loc = Env.createStorageLocation(*S);
294         Env.setStorageLocation(*S, Loc);
295         Env.setValue(Loc, *ArgVal);
296       }
297       return;
298     }
299 
300     auto &Loc = Env.createStorageLocation(*S);
301     Env.setStorageLocation(*S, Loc);
302     if (Value *Val = Env.createValue(S->getType()))
303       Env.setValue(Loc, *Val);
304   }
305 
306   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
307     if (S->getOperator() == OO_Equal) {
308       assert(S->getNumArgs() == 2);
309 
310       const Expr *Arg0 = S->getArg(0);
311       assert(Arg0 != nullptr);
312 
313       const Expr *Arg1 = S->getArg(1);
314       assert(Arg1 != nullptr);
315 
316       // Evaluate only copy and move assignment operators.
317       auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
318       auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
319       if (Arg0Type != Arg1Type)
320         return;
321 
322       auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
323       if (ObjectLoc == nullptr)
324         return;
325 
326       auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
327       if (Val == nullptr)
328         return;
329 
330       Env.setValue(*ObjectLoc, *Val);
331     }
332   }
333 
334   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
335     if (S->getCastKind() == CK_ConstructorConversion) {
336       // The CFG does not contain `ParenExpr` as top-level statements in basic
337       // blocks, however sub-expressions can still be of that type.
338       assert(S->getSubExpr() != nullptr);
339       const Expr *SubExpr = S->getSubExpr();
340       assert(SubExpr != nullptr);
341 
342       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
343       if (SubExprLoc == nullptr)
344         return;
345 
346       Env.setStorageLocation(*S, *SubExprLoc);
347     }
348   }
349 
350   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
351     auto &Loc = Env.createStorageLocation(*S);
352     Env.setStorageLocation(*S, Loc);
353     if (Value *Val = Env.createValue(S->getType()))
354       Env.setValue(Loc, *Val);
355   }
356 
357   void VisitCallExpr(const CallExpr *S) {
358     if (S->isCallToStdMove()) {
359       assert(S->getNumArgs() == 1);
360 
361       const Expr *Arg = S->getArg(0);
362       assert(Arg != nullptr);
363 
364       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
365       if (ArgLoc == nullptr)
366         return;
367 
368       Env.setStorageLocation(*S, *ArgLoc);
369     }
370   }
371 
372   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
373     const Expr *SubExpr = S->getSubExpr();
374     assert(SubExpr != nullptr);
375 
376     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
377     if (SubExprLoc == nullptr)
378       return;
379 
380     Env.setStorageLocation(*S, *SubExprLoc);
381   }
382 
383   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
384     const Expr *SubExpr = S->getSubExpr();
385     assert(SubExpr != nullptr);
386 
387     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
388     if (SubExprLoc == nullptr)
389       return;
390 
391     Env.setStorageLocation(*S, *SubExprLoc);
392   }
393 
394   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
395     if (S->getCastKind() == CK_NoOp) {
396       const Expr *SubExpr = S->getSubExpr();
397       assert(SubExpr != nullptr);
398 
399       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
400       if (SubExprLoc == nullptr)
401         return;
402 
403       Env.setStorageLocation(*S, *SubExprLoc);
404     }
405   }
406 
407   void VisitConditionalOperator(const ConditionalOperator *S) {
408     // FIXME: Revisit this once flow conditions are added to the framework. For
409     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
410     // condition.
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   // FIXME: Add support for:
418   // - CXXBoolLiteralExpr
419 
420 private:
421   Environment &Env;
422 };
423 
424 void transfer(const Stmt &S, Environment &Env) {
425   assert(!isa<ParenExpr>(&S));
426   TransferVisitor(Env).Visit(&S);
427 }
428 
429 } // namespace dataflow
430 } // namespace clang
431