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         break;
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       break;
270     }
271     default:
272       break;
273     }
274   }
275 
276   void VisitCXXThisExpr(const CXXThisExpr *S) {
277     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
278     assert(ThisPointeeLoc != nullptr);
279 
280     auto &Loc = Env.createStorageLocation(*S);
281     Env.setStorageLocation(*S, Loc);
282     Env.setValue(Loc, Env.takeOwnership(
283                           std::make_unique<PointerValue>(*ThisPointeeLoc)));
284   }
285 
286   void VisitMemberExpr(const MemberExpr *S) {
287     ValueDecl *Member = S->getMemberDecl();
288     assert(Member != nullptr);
289 
290     // FIXME: Consider assigning pointer values to function member expressions.
291     if (Member->isFunctionOrFunctionTemplate())
292       return;
293 
294     // The receiver can be either a value or a pointer to a value. Skip past the
295     // indirection to handle both cases.
296     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
297         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
298     if (BaseLoc == nullptr)
299       return;
300 
301     // FIXME: Add support for union types.
302     if (BaseLoc->getType()->isUnionType())
303       return;
304 
305     auto &MemberLoc = BaseLoc->getChild(*Member);
306     if (MemberLoc.getType()->isReferenceType()) {
307       Env.setStorageLocation(*S, MemberLoc);
308     } else {
309       auto &Loc = Env.createStorageLocation(*S);
310       Env.setStorageLocation(*S, Loc);
311       Env.setValue(
312           Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
313     }
314   }
315 
316   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
317     const Expr *InitExpr = S->getExpr();
318     assert(InitExpr != nullptr);
319 
320     Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
321     if (InitExprVal == nullptr)
322       return;
323 
324     const FieldDecl *Field = S->getField();
325     assert(Field != nullptr);
326 
327     auto &ThisLoc =
328         *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
329     auto &FieldLoc = ThisLoc.getChild(*Field);
330     Env.setValue(FieldLoc, *InitExprVal);
331   }
332 
333   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
334     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
335     assert(ConstructorDecl != nullptr);
336 
337     if (ConstructorDecl->isCopyOrMoveConstructor()) {
338       assert(S->getNumArgs() == 1);
339 
340       const Expr *Arg = S->getArg(0);
341       assert(Arg != nullptr);
342 
343       if (S->isElidable()) {
344         auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
345         if (ArgLoc == nullptr)
346           return;
347 
348         Env.setStorageLocation(*S, *ArgLoc);
349       } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
350         auto &Loc = Env.createStorageLocation(*S);
351         Env.setStorageLocation(*S, Loc);
352         Env.setValue(Loc, *ArgVal);
353       }
354       return;
355     }
356 
357     auto &Loc = Env.createStorageLocation(*S);
358     Env.setStorageLocation(*S, Loc);
359     if (Value *Val = Env.createValue(S->getType()))
360       Env.setValue(Loc, *Val);
361   }
362 
363   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
364     if (S->getOperator() == OO_Equal) {
365       assert(S->getNumArgs() == 2);
366 
367       const Expr *Arg0 = S->getArg(0);
368       assert(Arg0 != nullptr);
369 
370       const Expr *Arg1 = S->getArg(1);
371       assert(Arg1 != nullptr);
372 
373       // Evaluate only copy and move assignment operators.
374       auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
375       auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
376       if (Arg0Type != Arg1Type)
377         return;
378 
379       auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
380       if (ObjectLoc == nullptr)
381         return;
382 
383       auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
384       if (Val == nullptr)
385         return;
386 
387       Env.setValue(*ObjectLoc, *Val);
388     }
389   }
390 
391   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
392     if (S->getCastKind() == CK_ConstructorConversion) {
393       // The CFG does not contain `ParenExpr` as top-level statements in basic
394       // blocks, however sub-expressions can still be of that type.
395       assert(S->getSubExpr() != nullptr);
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 VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
408     auto &Loc = Env.createStorageLocation(*S);
409     Env.setStorageLocation(*S, Loc);
410     if (Value *Val = Env.createValue(S->getType()))
411       Env.setValue(Loc, *Val);
412   }
413 
414   void VisitCallExpr(const CallExpr *S) {
415     if (S->isCallToStdMove()) {
416       assert(S->getNumArgs() == 1);
417 
418       const Expr *Arg = S->getArg(0);
419       assert(Arg != nullptr);
420 
421       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
422       if (ArgLoc == nullptr)
423         return;
424 
425       Env.setStorageLocation(*S, *ArgLoc);
426     }
427   }
428 
429   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
430     const Expr *SubExpr = S->getSubExpr();
431     assert(SubExpr != nullptr);
432 
433     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
434     if (SubExprLoc == nullptr)
435       return;
436 
437     Env.setStorageLocation(*S, *SubExprLoc);
438   }
439 
440   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
441     const Expr *SubExpr = S->getSubExpr();
442     assert(SubExpr != nullptr);
443 
444     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
445     if (SubExprLoc == nullptr)
446       return;
447 
448     Env.setStorageLocation(*S, *SubExprLoc);
449   }
450 
451   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
452     if (S->getCastKind() == CK_NoOp) {
453       const Expr *SubExpr = S->getSubExpr();
454       assert(SubExpr != nullptr);
455 
456       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
457       if (SubExprLoc == nullptr)
458         return;
459 
460       Env.setStorageLocation(*S, *SubExprLoc);
461     }
462   }
463 
464   void VisitConditionalOperator(const ConditionalOperator *S) {
465     // FIXME: Revisit this once flow conditions are added to the framework. For
466     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
467     // condition.
468     auto &Loc = Env.createStorageLocation(*S);
469     Env.setStorageLocation(*S, Loc);
470     if (Value *Val = Env.createValue(S->getType()))
471       Env.setValue(Loc, *Val);
472   }
473 
474   void VisitInitListExpr(const InitListExpr *S) {
475     QualType Type = S->getType();
476 
477     auto &Loc = Env.createStorageLocation(*S);
478     Env.setStorageLocation(*S, Loc);
479 
480     auto *Val = Env.createValue(Type);
481     if (Val == nullptr)
482       return;
483 
484     Env.setValue(Loc, *Val);
485 
486     if (Type->isStructureOrClassType()) {
487       for (auto IT : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) {
488         const FieldDecl *Field = std::get<0>(IT);
489         assert(Field != nullptr);
490 
491         const Expr *Init = std::get<1>(IT);
492         assert(Init != nullptr);
493 
494         if (Value *InitVal = Env.getValue(*Init, SkipPast::None))
495           cast<StructValue>(Val)->setChild(*Field, *InitVal);
496       }
497     }
498     // FIXME: Implement array initialization.
499   }
500 
501   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
502     auto &Loc = Env.createStorageLocation(*S);
503     Env.setStorageLocation(*S, Loc);
504     Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
505   }
506 
507 private:
508   const StmtToEnvMap &StmtToEnv;
509   Environment &Env;
510 };
511 
512 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
513   assert(!isa<ParenExpr>(&S));
514   TransferVisitor(StmtToEnv, Env).Visit(&S);
515 }
516 
517 } // namespace dataflow
518 } // namespace clang
519