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