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/ControlFlowContext.h"
24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
25 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
26 #include "clang/Analysis/FlowSensitive/Value.h"
27 #include "clang/Basic/Builtins.h"
28 #include "clang/Basic/OperatorKinds.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/Casting.h"
31 #include <cassert>
32 #include <memory>
33 #include <tuple>
34 
35 namespace clang {
36 namespace dataflow {
37 
evaluateBooleanEquality(const Expr & LHS,const Expr & RHS,Environment & Env)38 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
39                                           Environment &Env) {
40   if (auto *LHSValue =
41           dyn_cast_or_null<BoolValue>(Env.getValue(LHS, SkipPast::Reference)))
42     if (auto *RHSValue =
43             dyn_cast_or_null<BoolValue>(Env.getValue(RHS, SkipPast::Reference)))
44       return Env.makeIff(*LHSValue, *RHSValue);
45 
46   return Env.makeAtomicBoolValue();
47 }
48 
49 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
50 public:
TransferVisitor(const StmtToEnvMap & StmtToEnv,Environment & Env,TransferOptions Options)51   TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
52                   TransferOptions Options)
53       : StmtToEnv(StmtToEnv), Env(Env), Options(Options) {}
54 
VisitBinaryOperator(const BinaryOperator * S)55   void VisitBinaryOperator(const BinaryOperator *S) {
56     const Expr *LHS = S->getLHS();
57     assert(LHS != nullptr);
58 
59     const Expr *RHS = S->getRHS();
60     assert(RHS != nullptr);
61 
62     switch (S->getOpcode()) {
63     case BO_Assign: {
64       auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
65       if (LHSLoc == nullptr)
66         break;
67 
68       auto *RHSVal = Env.getValue(*RHS, SkipPast::Reference);
69       if (RHSVal == nullptr)
70         break;
71 
72       // Assign a value to the storage location of the left-hand side.
73       Env.setValue(*LHSLoc, *RHSVal);
74 
75       // Assign a storage location for the whole expression.
76       Env.setStorageLocation(*S, *LHSLoc);
77       break;
78     }
79     case BO_LAnd:
80     case BO_LOr: {
81       BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS);
82       BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS);
83 
84       auto &Loc = Env.createStorageLocation(*S);
85       Env.setStorageLocation(*S, Loc);
86       if (S->getOpcode() == BO_LAnd)
87         Env.setValue(Loc, Env.makeAnd(LHSVal, RHSVal));
88       else
89         Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
90       break;
91     }
92     case BO_NE:
93     case BO_EQ: {
94       auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env);
95       auto &Loc = Env.createStorageLocation(*S);
96       Env.setStorageLocation(*S, Loc);
97       Env.setValue(Loc, S->getOpcode() == BO_EQ ? LHSEqRHSValue
98                                                 : Env.makeNot(LHSEqRHSValue));
99       break;
100     }
101     case BO_Comma: {
102       if (auto *Loc = Env.getStorageLocation(*RHS, SkipPast::None))
103         Env.setStorageLocation(*S, *Loc);
104       break;
105     }
106     default:
107       break;
108     }
109   }
110 
VisitDeclRefExpr(const DeclRefExpr * S)111   void VisitDeclRefExpr(const DeclRefExpr *S) {
112     assert(S->getDecl() != nullptr);
113     auto *DeclLoc = Env.getStorageLocation(*S->getDecl(), SkipPast::None);
114     if (DeclLoc == nullptr)
115       return;
116 
117     if (S->getDecl()->getType()->isReferenceType()) {
118       Env.setStorageLocation(*S, *DeclLoc);
119     } else {
120       auto &Loc = Env.createStorageLocation(*S);
121       auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*DeclLoc));
122       Env.setStorageLocation(*S, Loc);
123       Env.setValue(Loc, Val);
124     }
125   }
126 
VisitDeclStmt(const DeclStmt * S)127   void VisitDeclStmt(const DeclStmt *S) {
128     // Group decls are converted into single decls in the CFG so the cast below
129     // is safe.
130     const auto &D = *cast<VarDecl>(S->getSingleDecl());
131 
132     // Static local vars are already initialized in `Environment`.
133     if (D.hasGlobalStorage())
134       return;
135 
136     auto &Loc = Env.createStorageLocation(D);
137     Env.setStorageLocation(D, Loc);
138 
139     const Expr *InitExpr = D.getInit();
140     if (InitExpr == nullptr) {
141       // No initializer expression - associate `Loc` with a new value.
142       if (Value *Val = Env.createValue(D.getType()))
143         Env.setValue(Loc, *Val);
144       return;
145     }
146 
147     if (D.getType()->isReferenceType()) {
148       // Initializing a reference variable - do not create a reference to
149       // reference.
150       if (auto *InitExprLoc =
151               Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
152         auto &Val =
153             Env.takeOwnership(std::make_unique<ReferenceValue>(*InitExprLoc));
154         Env.setValue(Loc, Val);
155       }
156     } else if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) {
157       Env.setValue(Loc, *InitExprVal);
158     }
159 
160     if (Env.getValue(Loc) == nullptr) {
161       // We arrive here in (the few) cases where an expression is intentionally
162       // "uninterpreted". There are two ways to handle this situation: propagate
163       // the status, so that uninterpreted initializers result in uninterpreted
164       // variables, or provide a default value. We choose the latter so that
165       // later refinements of the variable can be used for reasoning about the
166       // surrounding code.
167       //
168       // FIXME. If and when we interpret all language cases, change this to
169       // assert that `InitExpr` is interpreted, rather than supplying a default
170       // value (assuming we don't update the environment API to return
171       // references).
172       if (Value *Val = Env.createValue(D.getType()))
173         Env.setValue(Loc, *Val);
174     }
175 
176     if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) {
177       // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
178       // needs to be evaluated after initializing the values in the storage for
179       // VarDecl, as the bindings refer to them.
180       // FIXME: Add support for ArraySubscriptExpr.
181       // FIXME: Consider adding AST nodes that are used for structured bindings
182       // to the CFG.
183       for (const auto *B : Decomp->bindings()) {
184         auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding());
185         if (ME == nullptr)
186           continue;
187 
188         auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase());
189         if (DE == nullptr)
190           continue;
191 
192         // ME and its base haven't been visited because they aren't included in
193         // the statements of the CFG basic block.
194         VisitDeclRefExpr(DE);
195         VisitMemberExpr(ME);
196 
197         if (auto *Loc = Env.getStorageLocation(*ME, SkipPast::Reference))
198           Env.setStorageLocation(*B, *Loc);
199       }
200     }
201   }
202 
VisitImplicitCastExpr(const ImplicitCastExpr * S)203   void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
204     const Expr *SubExpr = S->getSubExpr();
205     assert(SubExpr != nullptr);
206 
207     switch (S->getCastKind()) {
208     case CK_IntegralToBoolean: {
209       // This cast creates a new, boolean value from the integral value. We
210       // model that with a fresh value in the environment, unless it's already a
211       // boolean.
212       auto &Loc = Env.createStorageLocation(*S);
213       Env.setStorageLocation(*S, Loc);
214       if (auto *SubExprVal = dyn_cast_or_null<BoolValue>(
215               Env.getValue(*SubExpr, SkipPast::Reference)))
216         Env.setValue(Loc, *SubExprVal);
217       else
218         // FIXME: If integer modeling is added, then update this code to create
219         // the boolean based on the integer model.
220         Env.setValue(Loc, Env.makeAtomicBoolValue());
221       break;
222     }
223 
224     case CK_LValueToRValue: {
225       auto *SubExprVal = Env.getValue(*SubExpr, SkipPast::Reference);
226       if (SubExprVal == nullptr)
227         break;
228 
229       auto &ExprLoc = Env.createStorageLocation(*S);
230       Env.setStorageLocation(*S, ExprLoc);
231       Env.setValue(ExprLoc, *SubExprVal);
232       break;
233     }
234 
235     case CK_IntegralCast:
236       // FIXME: This cast creates a new integral value from the
237       // subexpression. But, because we don't model integers, we don't
238       // distinguish between this new value and the underlying one. If integer
239       // modeling is added, then update this code to create a fresh location and
240       // value.
241     case CK_UncheckedDerivedToBase:
242     case CK_ConstructorConversion:
243     case CK_UserDefinedConversion:
244       // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
245       // CK_ConstructorConversion, and CK_UserDefinedConversion.
246     case CK_NoOp: {
247       // FIXME: Consider making `Environment::getStorageLocation` skip noop
248       // expressions (this and other similar expressions in the file) instead of
249       // assigning them storage locations.
250       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
251       if (SubExprLoc == nullptr)
252         break;
253 
254       Env.setStorageLocation(*S, *SubExprLoc);
255       break;
256     }
257     case CK_NullToPointer:
258     case CK_NullToMemberPointer: {
259       auto &Loc = Env.createStorageLocation(S->getType());
260       Env.setStorageLocation(*S, Loc);
261 
262       auto &NullPointerVal =
263           Env.getOrCreateNullPointerValue(S->getType()->getPointeeType());
264       Env.setValue(Loc, NullPointerVal);
265       break;
266     }
267     default:
268       break;
269     }
270   }
271 
VisitUnaryOperator(const UnaryOperator * S)272   void VisitUnaryOperator(const UnaryOperator *S) {
273     const Expr *SubExpr = S->getSubExpr();
274     assert(SubExpr != nullptr);
275 
276     switch (S->getOpcode()) {
277     case UO_Deref: {
278       // Skip past a reference to handle dereference of a dependent pointer.
279       const auto *SubExprVal = cast_or_null<PointerValue>(
280           Env.getValue(*SubExpr, SkipPast::Reference));
281       if (SubExprVal == nullptr)
282         break;
283 
284       auto &Loc = Env.createStorageLocation(*S);
285       Env.setStorageLocation(*S, Loc);
286       Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
287                             SubExprVal->getPointeeLoc())));
288       break;
289     }
290     case UO_AddrOf: {
291       // Do not form a pointer to a reference. If `SubExpr` is assigned a
292       // `ReferenceValue` then form a value that points to the location of its
293       // pointee.
294       StorageLocation *PointeeLoc =
295           Env.getStorageLocation(*SubExpr, SkipPast::Reference);
296       if (PointeeLoc == nullptr)
297         break;
298 
299       auto &PointerLoc = Env.createStorageLocation(*S);
300       auto &PointerVal =
301           Env.takeOwnership(std::make_unique<PointerValue>(*PointeeLoc));
302       Env.setStorageLocation(*S, PointerLoc);
303       Env.setValue(PointerLoc, PointerVal);
304       break;
305     }
306     case UO_LNot: {
307       auto *SubExprVal =
308           dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr, SkipPast::None));
309       if (SubExprVal == nullptr)
310         break;
311 
312       auto &ExprLoc = Env.createStorageLocation(*S);
313       Env.setStorageLocation(*S, ExprLoc);
314       Env.setValue(ExprLoc, Env.makeNot(*SubExprVal));
315       break;
316     }
317     default:
318       break;
319     }
320   }
321 
VisitCXXThisExpr(const CXXThisExpr * S)322   void VisitCXXThisExpr(const CXXThisExpr *S) {
323     auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
324     if (ThisPointeeLoc == nullptr)
325       // Unions are not supported yet, and will not have a location for the
326       // `this` expression's pointee.
327       return;
328 
329     auto &Loc = Env.createStorageLocation(*S);
330     Env.setStorageLocation(*S, Loc);
331     Env.setValue(Loc, Env.takeOwnership(
332                           std::make_unique<PointerValue>(*ThisPointeeLoc)));
333   }
334 
VisitMemberExpr(const MemberExpr * S)335   void VisitMemberExpr(const MemberExpr *S) {
336     ValueDecl *Member = S->getMemberDecl();
337     assert(Member != nullptr);
338 
339     // FIXME: Consider assigning pointer values to function member expressions.
340     if (Member->isFunctionOrFunctionTemplate())
341       return;
342 
343     if (auto *D = dyn_cast<VarDecl>(Member)) {
344       if (D->hasGlobalStorage()) {
345         auto *VarDeclLoc = Env.getStorageLocation(*D, SkipPast::None);
346         if (VarDeclLoc == nullptr)
347           return;
348 
349         if (VarDeclLoc->getType()->isReferenceType()) {
350           Env.setStorageLocation(*S, *VarDeclLoc);
351         } else {
352           auto &Loc = Env.createStorageLocation(*S);
353           Env.setStorageLocation(*S, Loc);
354           Env.setValue(Loc, Env.takeOwnership(
355                                 std::make_unique<ReferenceValue>(*VarDeclLoc)));
356         }
357         return;
358       }
359     }
360 
361     // The receiver can be either a value or a pointer to a value. Skip past the
362     // indirection to handle both cases.
363     auto *BaseLoc = cast_or_null<AggregateStorageLocation>(
364         Env.getStorageLocation(*S->getBase(), SkipPast::ReferenceThenPointer));
365     if (BaseLoc == nullptr)
366       return;
367 
368     // FIXME: Add support for union types.
369     if (BaseLoc->getType()->isUnionType())
370       return;
371 
372     auto &MemberLoc = BaseLoc->getChild(*Member);
373     if (MemberLoc.getType()->isReferenceType()) {
374       Env.setStorageLocation(*S, MemberLoc);
375     } else {
376       auto &Loc = Env.createStorageLocation(*S);
377       Env.setStorageLocation(*S, Loc);
378       Env.setValue(
379           Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(MemberLoc)));
380     }
381   }
382 
VisitCXXDefaultInitExpr(const CXXDefaultInitExpr * S)383   void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
384     const Expr *InitExpr = S->getExpr();
385     assert(InitExpr != nullptr);
386 
387     Value *InitExprVal = Env.getValue(*InitExpr, SkipPast::None);
388     if (InitExprVal == nullptr)
389       return;
390 
391     const FieldDecl *Field = S->getField();
392     assert(Field != nullptr);
393 
394     auto &ThisLoc =
395         *cast<AggregateStorageLocation>(Env.getThisPointeeStorageLocation());
396     auto &FieldLoc = ThisLoc.getChild(*Field);
397     Env.setValue(FieldLoc, *InitExprVal);
398   }
399 
VisitCXXConstructExpr(const CXXConstructExpr * S)400   void VisitCXXConstructExpr(const CXXConstructExpr *S) {
401     const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
402     assert(ConstructorDecl != nullptr);
403 
404     if (ConstructorDecl->isCopyOrMoveConstructor()) {
405       assert(S->getNumArgs() == 1);
406 
407       const Expr *Arg = S->getArg(0);
408       assert(Arg != nullptr);
409 
410       if (S->isElidable()) {
411         auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
412         if (ArgLoc == nullptr)
413           return;
414 
415         Env.setStorageLocation(*S, *ArgLoc);
416       } else if (auto *ArgVal = Env.getValue(*Arg, SkipPast::Reference)) {
417         auto &Loc = Env.createStorageLocation(*S);
418         Env.setStorageLocation(*S, Loc);
419         Env.setValue(Loc, *ArgVal);
420       }
421       return;
422     }
423 
424     auto &Loc = Env.createStorageLocation(*S);
425     Env.setStorageLocation(*S, Loc);
426     if (Value *Val = Env.createValue(S->getType()))
427       Env.setValue(Loc, *Val);
428   }
429 
VisitCXXOperatorCallExpr(const CXXOperatorCallExpr * S)430   void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
431     if (S->getOperator() == OO_Equal) {
432       assert(S->getNumArgs() == 2);
433 
434       const Expr *Arg0 = S->getArg(0);
435       assert(Arg0 != nullptr);
436 
437       const Expr *Arg1 = S->getArg(1);
438       assert(Arg1 != nullptr);
439 
440       // Evaluate only copy and move assignment operators.
441       auto *Arg0Type = Arg0->getType()->getUnqualifiedDesugaredType();
442       auto *Arg1Type = Arg1->getType()->getUnqualifiedDesugaredType();
443       if (Arg0Type != Arg1Type)
444         return;
445 
446       auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
447       if (ObjectLoc == nullptr)
448         return;
449 
450       auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
451       if (Val == nullptr)
452         return;
453 
454       // Assign a value to the storage location of the object.
455       Env.setValue(*ObjectLoc, *Val);
456 
457       // FIXME: Add a test for the value of the whole expression.
458       // Assign a storage location for the whole expression.
459       Env.setStorageLocation(*S, *ObjectLoc);
460     }
461   }
462 
VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr * S)463   void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) {
464     if (S->getCastKind() == CK_ConstructorConversion) {
465       const Expr *SubExpr = S->getSubExpr();
466       assert(SubExpr != nullptr);
467 
468       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
469       if (SubExprLoc == nullptr)
470         return;
471 
472       Env.setStorageLocation(*S, *SubExprLoc);
473     }
474   }
475 
VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr * S)476   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
477     auto &Loc = Env.createStorageLocation(*S);
478     Env.setStorageLocation(*S, Loc);
479     if (Value *Val = Env.createValue(S->getType()))
480       Env.setValue(Loc, *Val);
481   }
482 
VisitCallExpr(const CallExpr * S)483   void VisitCallExpr(const CallExpr *S) {
484     // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
485     // others (like trap, debugtrap, and unreachable) are handled by CFG
486     // construction.
487     if (S->isCallToStdMove()) {
488       assert(S->getNumArgs() == 1);
489 
490       const Expr *Arg = S->getArg(0);
491       assert(Arg != nullptr);
492 
493       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
494       if (ArgLoc == nullptr)
495         return;
496 
497       Env.setStorageLocation(*S, *ArgLoc);
498     } else if (S->getDirectCallee() != nullptr &&
499                S->getDirectCallee()->getBuiltinID() ==
500                    Builtin::BI__builtin_expect) {
501       assert(S->getNumArgs() > 0);
502       assert(S->getArg(0) != nullptr);
503       // `__builtin_expect` returns by-value, so strip away any potential
504       // references in the argument.
505       auto *ArgLoc = Env.getStorageLocation(*S->getArg(0), SkipPast::Reference);
506       if (ArgLoc == nullptr)
507         return;
508       Env.setStorageLocation(*S, *ArgLoc);
509     } else if (const FunctionDecl *F = S->getDirectCallee()) {
510       // This case is for context-sensitive analysis, which we only do if we
511       // have the callee body available in the translation unit.
512       if (!Options.ContextSensitive || F->getBody() == nullptr)
513         return;
514 
515       auto &ASTCtx = F->getASTContext();
516 
517       // FIXME: Cache these CFGs.
518       auto CFCtx = ControlFlowContext::build(F, F->getBody(), &ASTCtx);
519       // FIXME: Handle errors here and below.
520       assert(CFCtx);
521       auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
522 
523       auto CalleeEnv = Env.pushCall(S);
524 
525       // FIXME: Use the same analysis as the caller for the callee.
526       DataflowAnalysisOptions Options;
527       auto Analysis = NoopAnalysis(ASTCtx, Options);
528 
529       auto BlockToOutputState =
530           dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
531       assert(BlockToOutputState);
532       assert(ExitBlock < BlockToOutputState->size());
533 
534       auto ExitState = (*BlockToOutputState)[ExitBlock];
535       assert(ExitState);
536 
537       Env = ExitState->Env;
538     }
539   }
540 
VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr * S)541   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
542     const Expr *SubExpr = S->getSubExpr();
543     assert(SubExpr != nullptr);
544 
545     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
546     if (SubExprLoc == nullptr)
547       return;
548 
549     Env.setStorageLocation(*S, *SubExprLoc);
550   }
551 
VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr * S)552   void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
553     const Expr *SubExpr = S->getSubExpr();
554     assert(SubExpr != nullptr);
555 
556     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
557     if (SubExprLoc == nullptr)
558       return;
559 
560     Env.setStorageLocation(*S, *SubExprLoc);
561   }
562 
VisitCXXStaticCastExpr(const CXXStaticCastExpr * S)563   void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
564     if (S->getCastKind() == CK_NoOp) {
565       const Expr *SubExpr = S->getSubExpr();
566       assert(SubExpr != nullptr);
567 
568       auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);
569       if (SubExprLoc == nullptr)
570         return;
571 
572       Env.setStorageLocation(*S, *SubExprLoc);
573     }
574   }
575 
VisitConditionalOperator(const ConditionalOperator * S)576   void VisitConditionalOperator(const ConditionalOperator *S) {
577     // FIXME: Revisit this once flow conditions are added to the framework. For
578     // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
579     // condition.
580     auto &Loc = Env.createStorageLocation(*S);
581     Env.setStorageLocation(*S, Loc);
582     if (Value *Val = Env.createValue(S->getType()))
583       Env.setValue(Loc, *Val);
584   }
585 
VisitInitListExpr(const InitListExpr * S)586   void VisitInitListExpr(const InitListExpr *S) {
587     QualType Type = S->getType();
588 
589     auto &Loc = Env.createStorageLocation(*S);
590     Env.setStorageLocation(*S, Loc);
591 
592     auto *Val = Env.createValue(Type);
593     if (Val == nullptr)
594       return;
595 
596     Env.setValue(Loc, *Val);
597 
598     if (Type->isStructureOrClassType()) {
599       for (auto It : llvm::zip(Type->getAsRecordDecl()->fields(), S->inits())) {
600         const FieldDecl *Field = std::get<0>(It);
601         assert(Field != nullptr);
602 
603         const Expr *Init = std::get<1>(It);
604         assert(Init != nullptr);
605 
606         if (Value *InitVal = Env.getValue(*Init, SkipPast::None))
607           cast<StructValue>(Val)->setChild(*Field, *InitVal);
608       }
609     }
610     // FIXME: Implement array initialization.
611   }
612 
VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr * S)613   void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
614     auto &Loc = Env.createStorageLocation(*S);
615     Env.setStorageLocation(*S, Loc);
616     Env.setValue(Loc, Env.getBoolLiteralValue(S->getValue()));
617   }
618 
VisitParenExpr(const ParenExpr * S)619   void VisitParenExpr(const ParenExpr *S) {
620     // The CFG does not contain `ParenExpr` as top-level statements in basic
621     // blocks, however manual traversal to sub-expressions may encounter them.
622     // Redirect to the sub-expression.
623     auto *SubExpr = S->getSubExpr();
624     assert(SubExpr != nullptr);
625     Visit(SubExpr);
626   }
627 
VisitExprWithCleanups(const ExprWithCleanups * S)628   void VisitExprWithCleanups(const ExprWithCleanups *S) {
629     // The CFG does not contain `ExprWithCleanups` as top-level statements in
630     // basic blocks, however manual traversal to sub-expressions may encounter
631     // them. Redirect to the sub-expression.
632     auto *SubExpr = S->getSubExpr();
633     assert(SubExpr != nullptr);
634     Visit(SubExpr);
635   }
636 
637 private:
getLogicOperatorSubExprValue(const Expr & SubExpr)638   BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
639     // `SubExpr` and its parent logic operator might be part of different basic
640     // blocks. We try to access the value that is assigned to `SubExpr` in the
641     // corresponding environment.
642     if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) {
643       if (auto *Val = dyn_cast_or_null<BoolValue>(
644               SubExprEnv->getValue(SubExpr, SkipPast::Reference)))
645         return *Val;
646     }
647 
648     if (Env.getStorageLocation(SubExpr, SkipPast::None) == nullptr) {
649       // Sub-expressions that are logic operators are not added in basic blocks
650       // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
651       // operator, it may not have been evaluated and assigned a value yet. In
652       // that case, we need to first visit `SubExpr` and then try to get the
653       // value that gets assigned to it.
654       Visit(&SubExpr);
655     }
656 
657     if (auto *Val = dyn_cast_or_null<BoolValue>(
658             Env.getValue(SubExpr, SkipPast::Reference)))
659       return *Val;
660 
661     // If the value of `SubExpr` is still unknown, we create a fresh symbolic
662     // boolean value for it.
663     return Env.makeAtomicBoolValue();
664   }
665 
666   const StmtToEnvMap &StmtToEnv;
667   Environment &Env;
668   TransferOptions Options;
669 };
670 
transfer(const StmtToEnvMap & StmtToEnv,const Stmt & S,Environment & Env,TransferOptions Options)671 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,
672               TransferOptions Options) {
673   TransferVisitor(StmtToEnv, Env, Options).Visit(&S);
674 }
675 
676 } // namespace dataflow
677 } // namespace clang
678