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