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/ASTOps.h"
24#include "clang/Analysis/FlowSensitive/AdornedCFG.h"
25#include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
26#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
27#include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
28#include "clang/Analysis/FlowSensitive/RecordOps.h"
29#include "clang/Analysis/FlowSensitive/Value.h"
30#include "clang/Basic/Builtins.h"
31#include "clang/Basic/OperatorKinds.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Support/Debug.h"
34#include <assert.h>
35#include <cassert>
36
37#define DEBUG_TYPE "dataflow"
38
39namespace clang {
40namespace dataflow {
41
42const Environment *StmtToEnvMap::getEnvironment(const Stmt &S) const {
43 auto BlockIt = ACFG.getStmtToBlock().find(Val: &ignoreCFGOmittedNodes(S));
44 assert(BlockIt != ACFG.getStmtToBlock().end());
45 if (!ACFG.isBlockReachable(B: *BlockIt->getSecond()))
46 return nullptr;
47 if (BlockIt->getSecond()->getBlockID() == CurBlockID)
48 return &CurState.Env;
49 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()];
50 if (!(State))
51 return nullptr;
52 return &State->Env;
53}
54
55static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
56 Environment &Env) {
57 Value *LHSValue = Env.getValue(E: LHS);
58 Value *RHSValue = Env.getValue(E: RHS);
59
60 if (LHSValue == RHSValue)
61 return Env.getBoolLiteralValue(Value: true);
62
63 if (auto *LHSBool = dyn_cast_or_null<BoolValue>(Val: LHSValue))
64 if (auto *RHSBool = dyn_cast_or_null<BoolValue>(Val: RHSValue))
65 return Env.makeIff(LHS&: *LHSBool, RHS&: *RHSBool);
66
67 return Env.makeAtomicBoolValue();
68}
69
70static BoolValue &unpackValue(BoolValue &V, Environment &Env) {
71 if (auto *Top = llvm::dyn_cast<TopBoolValue>(Val: &V)) {
72 auto &A = Env.getDataflowAnalysisContext().arena();
73 return A.makeBoolValue(A.makeAtomRef(A: Top->getAtom()));
74 }
75 return V;
76}
77
78// Unpacks the value (if any) associated with `E` and updates `E` to the new
79// value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,
80// by skipping past the reference.
81static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) {
82 auto *Loc = Env.getStorageLocation(E);
83 if (Loc == nullptr)
84 return nullptr;
85 auto *Val = Env.getValue(Loc: *Loc);
86
87 auto *B = dyn_cast_or_null<BoolValue>(Val);
88 if (B == nullptr)
89 return Val;
90
91 auto &UnpackedVal = unpackValue(V&: *B, Env);
92 if (&UnpackedVal == Val)
93 return Val;
94 Env.setValue(Loc: *Loc, Val&: UnpackedVal);
95 return &UnpackedVal;
96}
97
98static void propagateValue(const Expr &From, const Expr &To, Environment &Env) {
99 if (From.getType()->isRecordType())
100 return;
101 if (auto *Val = Env.getValue(E: From))
102 Env.setValue(E: To, Val&: *Val);
103}
104
105static void propagateStorageLocation(const Expr &From, const Expr &To,
106 Environment &Env) {
107 if (auto *Loc = Env.getStorageLocation(E: From))
108 Env.setStorageLocation(E: To, Loc&: *Loc);
109}
110
111// Propagates the value or storage location of `From` to `To` in cases where
112// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff
113// `From` is a glvalue.
114static void propagateValueOrStorageLocation(const Expr &From, const Expr &To,
115 Environment &Env) {
116 assert(From.isGLValue() == To.isGLValue());
117 if (From.isGLValue())
118 propagateStorageLocation(From, To, Env);
119 else
120 propagateValue(From, To, Env);
121}
122
123namespace {
124
125class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
126public:
127 TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env,
128 Environment::ValueModel &Model)
129 : StmtToEnv(StmtToEnv), Env(Env), Model(Model) {}
130
131 void VisitBinaryOperator(const BinaryOperator *S) {
132 const Expr *LHS = S->getLHS();
133 assert(LHS != nullptr);
134
135 const Expr *RHS = S->getRHS();
136 assert(RHS != nullptr);
137
138 switch (S->getOpcode()) {
139 case BO_Assign: {
140 auto *LHSLoc = Env.getStorageLocation(E: *LHS);
141 if (LHSLoc == nullptr)
142 break;
143
144 auto *RHSVal = Env.getValue(E: *RHS);
145 if (RHSVal == nullptr)
146 break;
147
148 // Assign a value to the storage location of the left-hand side.
149 Env.setValue(Loc: *LHSLoc, Val&: *RHSVal);
150
151 // Assign a storage location for the whole expression.
152 Env.setStorageLocation(*S, *LHSLoc);
153 break;
154 }
155 case BO_LAnd:
156 case BO_LOr: {
157 BoolValue &LHSVal = getLogicOperatorSubExprValue(SubExpr: *LHS);
158 BoolValue &RHSVal = getLogicOperatorSubExprValue(SubExpr: *RHS);
159
160 if (S->getOpcode() == BO_LAnd)
161 Env.setValue(*S, Env.makeAnd(LHS&: LHSVal, RHS&: RHSVal));
162 else
163 Env.setValue(*S, Env.makeOr(LHS&: LHSVal, RHS&: RHSVal));
164 break;
165 }
166 case BO_NE:
167 case BO_EQ: {
168 auto &LHSEqRHSValue = evaluateBooleanEquality(LHS: *LHS, RHS: *RHS, Env);
169 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue
170 : Env.makeNot(Val&: LHSEqRHSValue));
171 break;
172 }
173 case BO_Comma: {
174 propagateValueOrStorageLocation(*RHS, *S, Env);
175 break;
176 }
177 default:
178 break;
179 }
180 }
181
182 void VisitDeclRefExpr(const DeclRefExpr *S) {
183 const ValueDecl *VD = S->getDecl();
184 assert(VD != nullptr);
185
186 // Some `DeclRefExpr`s aren't glvalues, so we can't associate them with a
187 // `StorageLocation`, and there's also no sensible `Value` that we can
188 // assign to them. Examples:
189 // - Non-static member variables
190 // - Non static member functions
191 // Note: Member operators are an exception to this, but apparently only
192 // if the `DeclRefExpr` is used within the callee of a
193 // `CXXOperatorCallExpr`. In other cases, for example when applying the
194 // address-of operator, the `DeclRefExpr` is a prvalue.
195 if (!S->isGLValue())
196 return;
197
198 auto *DeclLoc = Env.getStorageLocation(D: *VD);
199 if (DeclLoc == nullptr)
200 return;
201
202 Env.setStorageLocation(*S, *DeclLoc);
203 }
204
205 void VisitDeclStmt(const DeclStmt *S) {
206 // Group decls are converted into single decls in the CFG so the cast below
207 // is safe.
208 const auto &D = *cast<VarDecl>(Val: S->getSingleDecl());
209
210 ProcessVarDecl(D);
211 }
212
213 void ProcessVarDecl(const VarDecl &D) {
214 // Static local vars are already initialized in `Environment`.
215 if (D.hasGlobalStorage())
216 return;
217
218 // If this is the holding variable for a `BindingDecl`, we may already
219 // have a storage location set up -- so check. (See also explanation below
220 // where we process the `BindingDecl`.)
221 if (D.getType()->isReferenceType() && Env.getStorageLocation(D) != nullptr)
222 return;
223
224 assert(Env.getStorageLocation(D) == nullptr);
225
226 Env.setStorageLocation(D, Env.createObject(D));
227
228 // `DecompositionDecl` must be handled after we've interpreted the loc
229 // itself, because the binding expression refers back to the
230 // `DecompositionDecl` (even though it has no written name).
231 if (const auto *Decomp = dyn_cast<DecompositionDecl>(Val: &D)) {
232 // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
233 // needs to be evaluated after initializing the values in the storage for
234 // VarDecl, as the bindings refer to them.
235 // FIXME: Add support for ArraySubscriptExpr.
236 // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
237 for (const auto *B : Decomp->bindings()) {
238 if (auto *ME = dyn_cast_or_null<MemberExpr>(Val: B->getBinding())) {
239 auto *DE = dyn_cast_or_null<DeclRefExpr>(Val: ME->getBase());
240 if (DE == nullptr)
241 continue;
242
243 // ME and its base haven't been visited because they aren't included
244 // in the statements of the CFG basic block.
245 VisitDeclRefExpr(S: DE);
246 VisitMemberExpr(S: ME);
247
248 if (auto *Loc = Env.getStorageLocation(*ME))
249 Env.setStorageLocation(*B, *Loc);
250 } else if (auto *VD = B->getHoldingVar()) {
251 // Holding vars are used to back the `BindingDecl`s of tuple-like
252 // types. The holding var declarations appear after the
253 // `DecompositionDecl`, so we have to explicitly process them here
254 // to know their storage location. They will be processed a second
255 // time when we visit their `VarDecl`s, so we have code that protects
256 // against this above.
257 ProcessVarDecl(D: *VD);
258 auto *VDLoc = Env.getStorageLocation(*VD);
259 assert(VDLoc != nullptr);
260 Env.setStorageLocation(*B, *VDLoc);
261 }
262 }
263 }
264 }
265
266 void VisitImplicitCastExpr(const ImplicitCastExpr *S) {
267 const Expr *SubExpr = S->getSubExpr();
268 assert(SubExpr != nullptr);
269
270 switch (S->getCastKind()) {
271 case CK_IntegralToBoolean: {
272 // This cast creates a new, boolean value from the integral value. We
273 // model that with a fresh value in the environment, unless it's already a
274 // boolean.
275 if (auto *SubExprVal =
276 dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr)))
277 Env.setValue(*S, *SubExprVal);
278 else
279 // FIXME: If integer modeling is added, then update this code to create
280 // the boolean based on the integer model.
281 Env.setValue(*S, Env.makeAtomicBoolValue());
282 break;
283 }
284
285 case CK_LValueToRValue: {
286 // When an L-value is used as an R-value, it may result in sharing, so we
287 // need to unpack any nested `Top`s.
288 auto *SubExprVal = maybeUnpackLValueExpr(E: *SubExpr, Env);
289 if (SubExprVal == nullptr)
290 break;
291
292 Env.setValue(*S, *SubExprVal);
293 break;
294 }
295
296 case CK_IntegralCast:
297 // FIXME: This cast creates a new integral value from the
298 // subexpression. But, because we don't model integers, we don't
299 // distinguish between this new value and the underlying one. If integer
300 // modeling is added, then update this code to create a fresh location and
301 // value.
302 case CK_UncheckedDerivedToBase:
303 case CK_ConstructorConversion:
304 case CK_UserDefinedConversion:
305 // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
306 // CK_ConstructorConversion, and CK_UserDefinedConversion.
307 case CK_NoOp: {
308 // FIXME: Consider making `Environment::getStorageLocation` skip noop
309 // expressions (this and other similar expressions in the file) instead
310 // of assigning them storage locations.
311 propagateValueOrStorageLocation(*SubExpr, *S, Env);
312 break;
313 }
314 case CK_NullToPointer: {
315 auto &NullPointerVal =
316 Env.getOrCreateNullPointerValue(PointeeType: S->getType()->getPointeeType());
317 Env.setValue(*S, NullPointerVal);
318 break;
319 }
320 case CK_NullToMemberPointer:
321 // FIXME: Implement pointers to members. For now, don't associate a value
322 // with this expression.
323 break;
324 case CK_FunctionToPointerDecay: {
325 StorageLocation *PointeeLoc = Env.getStorageLocation(E: *SubExpr);
326 if (PointeeLoc == nullptr)
327 break;
328
329 Env.setValue(*S, Env.create<PointerValue>(args&: *PointeeLoc));
330 break;
331 }
332 case CK_BuiltinFnToFnPtr:
333 // Despite its name, the result type of `BuiltinFnToFnPtr` is a function,
334 // not a function pointer. In addition, builtin functions can only be
335 // called directly; it is not legal to take their address. We therefore
336 // don't need to create a value or storage location for them.
337 break;
338 default:
339 break;
340 }
341 }
342
343 void VisitUnaryOperator(const UnaryOperator *S) {
344 const Expr *SubExpr = S->getSubExpr();
345 assert(SubExpr != nullptr);
346
347 switch (S->getOpcode()) {
348 case UO_Deref: {
349 const auto *SubExprVal = Env.get<PointerValue>(E: *SubExpr);
350 if (SubExprVal == nullptr)
351 break;
352
353 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc());
354 break;
355 }
356 case UO_AddrOf: {
357 // FIXME: Model pointers to members.
358 if (S->getType()->isMemberPointerType())
359 break;
360
361 if (StorageLocation *PointeeLoc = Env.getStorageLocation(E: *SubExpr))
362 Env.setValue(*S, Env.create<PointerValue>(args&: *PointeeLoc));
363 break;
364 }
365 case UO_LNot: {
366 auto *SubExprVal = dyn_cast_or_null<BoolValue>(Val: Env.getValue(E: *SubExpr));
367 if (SubExprVal == nullptr)
368 break;
369
370 Env.setValue(*S, Env.makeNot(Val&: *SubExprVal));
371 break;
372 }
373 default:
374 break;
375 }
376 }
377
378 void VisitCXXThisExpr(const CXXThisExpr *S) {
379 auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation();
380 if (ThisPointeeLoc == nullptr)
381 // Unions are not supported yet, and will not have a location for the
382 // `this` expression's pointee.
383 return;
384
385 Env.setValue(*S, Env.create<PointerValue>(args&: *ThisPointeeLoc));
386 }
387
388 void VisitCXXNewExpr(const CXXNewExpr *S) {
389 if (Value *Val = Env.createValue(Type: S->getType()))
390 Env.setValue(*S, *Val);
391 }
392
393 void VisitCXXDeleteExpr(const CXXDeleteExpr *S) {
394 // Empty method.
395 // We consciously don't do anything on deletes. Diagnosing double deletes
396 // (for example) should be done by a specific analysis, not by the
397 // framework.
398 }
399
400 void VisitReturnStmt(const ReturnStmt *S) {
401 if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts)
402 return;
403
404 auto *Ret = S->getRetValue();
405 if (Ret == nullptr)
406 return;
407
408 if (Ret->isPRValue()) {
409 if (Ret->getType()->isRecordType())
410 return;
411
412 auto *Val = Env.getValue(E: *Ret);
413 if (Val == nullptr)
414 return;
415
416 // FIXME: Model NRVO.
417 Env.setReturnValue(Val);
418 } else {
419 auto *Loc = Env.getStorageLocation(E: *Ret);
420 if (Loc == nullptr)
421 return;
422
423 // FIXME: Model NRVO.
424 Env.setReturnStorageLocation(Loc);
425 }
426 }
427
428 void VisitMemberExpr(const MemberExpr *S) {
429 ValueDecl *Member = S->getMemberDecl();
430 assert(Member != nullptr);
431
432 // FIXME: Consider assigning pointer values to function member expressions.
433 if (Member->isFunctionOrFunctionTemplate())
434 return;
435
436 // FIXME: if/when we add support for modeling enums, use that support here.
437 if (isa<EnumConstantDecl>(Val: Member))
438 return;
439
440 if (auto *D = dyn_cast<VarDecl>(Val: Member)) {
441 if (D->hasGlobalStorage()) {
442 auto *VarDeclLoc = Env.getStorageLocation(*D);
443 if (VarDeclLoc == nullptr)
444 return;
445
446 Env.setStorageLocation(*S, *VarDeclLoc);
447 return;
448 }
449 }
450
451 RecordStorageLocation *BaseLoc = getBaseObjectLocation(ME: *S, Env);
452 if (BaseLoc == nullptr)
453 return;
454
455 auto *MemberLoc = BaseLoc->getChild(D: *Member);
456 if (MemberLoc == nullptr)
457 return;
458 Env.setStorageLocation(*S, *MemberLoc);
459 }
460
461 void VisitCXXDefaultArgExpr(const CXXDefaultArgExpr *S) {
462 const Expr *ArgExpr = S->getExpr();
463 assert(ArgExpr != nullptr);
464 propagateValueOrStorageLocation(*ArgExpr, *S, Env);
465
466 if (S->isPRValue() && S->getType()->isRecordType()) {
467 auto &Loc = Env.getResultObjectLocation(*S);
468 Env.initializeFieldsWithValues(Loc);
469 }
470 }
471
472 void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) {
473 const Expr *InitExpr = S->getExpr();
474 assert(InitExpr != nullptr);
475
476 // If this is a prvalue of record type, the handler for `*InitExpr` (if one
477 // exists) will initialize the result object; there is no value to propgate
478 // here.
479 if (S->getType()->isRecordType() && S->isPRValue())
480 return;
481
482 propagateValueOrStorageLocation(*InitExpr, *S, Env);
483 }
484
485 void VisitCXXConstructExpr(const CXXConstructExpr *S) {
486 const CXXConstructorDecl *ConstructorDecl = S->getConstructor();
487 assert(ConstructorDecl != nullptr);
488
489 // `CXXConstructExpr` can have array type if default-initializing an array
490 // of records. We don't handle this specifically beyond potentially inlining
491 // the call.
492 if (!S->getType()->isRecordType()) {
493 transferInlineCall(S, ConstructorDecl);
494 return;
495 }
496
497 RecordStorageLocation &Loc = Env.getResultObjectLocation(*S);
498
499 if (ConstructorDecl->isCopyOrMoveConstructor()) {
500 // It is permissible for a copy/move constructor to have additional
501 // parameters as long as they have default arguments defined for them.
502 assert(S->getNumArgs() != 0);
503
504 const Expr *Arg = S->getArg(Arg: 0);
505 assert(Arg != nullptr);
506
507 auto *ArgLoc = Env.get<RecordStorageLocation>(E: *Arg);
508 if (ArgLoc == nullptr)
509 return;
510
511 // Even if the copy/move constructor call is elidable, we choose to copy
512 // the record in all cases (which isn't wrong, just potentially not
513 // optimal).
514 copyRecord(Src&: *ArgLoc, Dst&: Loc, Env);
515 return;
516 }
517
518 Env.initializeFieldsWithValues(Loc, S->getType());
519
520 transferInlineCall(S, ConstructorDecl);
521 }
522
523 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) {
524 if (S->getOperator() == OO_Equal) {
525 assert(S->getNumArgs() == 2);
526
527 const Expr *Arg0 = S->getArg(0);
528 assert(Arg0 != nullptr);
529
530 const Expr *Arg1 = S->getArg(1);
531 assert(Arg1 != nullptr);
532
533 // Evaluate only copy and move assignment operators.
534 const auto *Method =
535 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee());
536 if (!Method)
537 return;
538 if (!Method->isCopyAssignmentOperator() &&
539 !Method->isMoveAssignmentOperator())
540 return;
541
542 RecordStorageLocation *LocSrc = nullptr;
543 if (Arg1->isPRValue()) {
544 LocSrc = &Env.getResultObjectLocation(RecordPRValue: *Arg1);
545 } else {
546 LocSrc = Env.get<RecordStorageLocation>(E: *Arg1);
547 }
548 auto *LocDst = Env.get<RecordStorageLocation>(E: *Arg0);
549
550 if (LocSrc == nullptr || LocDst == nullptr)
551 return;
552
553 copyRecord(*LocSrc, *LocDst, Env);
554
555 // If the expr is a glvalue, we can reasonably assume the operator is
556 // returning T& and thus we can assign it `LocDst`.
557 if (S->isGLValue()) {
558 Env.setStorageLocation(*S, *LocDst);
559 } else if (S->getType()->isRecordType()) {
560 // Assume that the assignment returns the assigned value.
561 copyRecord(*LocDst, Env.getResultObjectLocation(*S), Env);
562 }
563
564 return;
565 }
566
567 // `CXXOperatorCallExpr` can be a prvalue. Call `VisitCallExpr`() to
568 // initialize the prvalue's fields with values.
569 VisitCallExpr(S);
570 }
571
572 void VisitCXXRewrittenBinaryOperator(const CXXRewrittenBinaryOperator *RBO) {
573 propagateValue(*RBO->getSemanticForm(), *RBO, Env);
574 }
575
576 void VisitCallExpr(const CallExpr *S) {
577 // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
578 // others (like trap, debugtrap, and unreachable) are handled by CFG
579 // construction.
580 if (S->isCallToStdMove()) {
581 assert(S->getNumArgs() == 1);
582
583 const Expr *Arg = S->getArg(Arg: 0);
584 assert(Arg != nullptr);
585
586 auto *ArgLoc = Env.getStorageLocation(E: *Arg);
587 if (ArgLoc == nullptr)
588 return;
589
590 Env.setStorageLocation(*S, *ArgLoc);
591 } else if (S->getDirectCallee() != nullptr &&
592 S->getDirectCallee()->getBuiltinID() ==
593 Builtin::BI__builtin_expect) {
594 assert(S->getNumArgs() > 0);
595 assert(S->getArg(0) != nullptr);
596 auto *ArgVal = Env.getValue(E: *S->getArg(Arg: 0));
597 if (ArgVal == nullptr)
598 return;
599 Env.setValue(*S, *ArgVal);
600 } else if (const FunctionDecl *F = S->getDirectCallee()) {
601 transferInlineCall(S, F);
602
603 // If this call produces a prvalue of record type, initialize its fields
604 // with values.
605 if (S->getType()->isRecordType() && S->isPRValue()) {
606 RecordStorageLocation &Loc = Env.getResultObjectLocation(*S);
607 Env.initializeFieldsWithValues(Loc);
608 }
609 }
610 }
611
612 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
613 const Expr *SubExpr = S->getSubExpr();
614 assert(SubExpr != nullptr);
615
616 StorageLocation &Loc = Env.createStorageLocation(*S);
617 Env.setStorageLocation(*S, Loc);
618
619 if (SubExpr->getType()->isRecordType())
620 // Nothing else left to do -- we initialized the record when transferring
621 // `SubExpr`.
622 return;
623
624 if (Value *SubExprVal = Env.getValue(E: *SubExpr))
625 Env.setValue(Loc, Val&: *SubExprVal);
626 }
627
628 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) {
629 const Expr *SubExpr = S->getSubExpr();
630 assert(SubExpr != nullptr);
631
632 propagateValue(*SubExpr, *S, Env);
633 }
634
635 void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) {
636 if (S->getCastKind() == CK_NoOp) {
637 const Expr *SubExpr = S->getSubExpr();
638 assert(SubExpr != nullptr);
639
640 propagateValueOrStorageLocation(*SubExpr, *S, Env);
641 }
642 }
643
644 void VisitConditionalOperator(const ConditionalOperator *S) {
645 const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr());
646 const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr());
647
648 if (TrueEnv == nullptr || FalseEnv == nullptr) {
649 // If the true or false branch is dead, we may not have an environment for
650 // it. We could handle this specifically by forwarding the value or
651 // location of the live branch, but this case is rare enough that this
652 // probably isn't worth the additional complexity.
653 return;
654 }
655
656 if (S->isGLValue()) {
657 StorageLocation *TrueLoc = TrueEnv->getStorageLocation(E: *S->getTrueExpr());
658 StorageLocation *FalseLoc =
659 FalseEnv->getStorageLocation(E: *S->getFalseExpr());
660 if (TrueLoc == FalseLoc && TrueLoc != nullptr)
661 Env.setStorageLocation(*S, *TrueLoc);
662 } else if (!S->getType()->isRecordType()) {
663 // The conditional operator can evaluate to either of the values of the
664 // two branches. To model this, join these two values together to yield
665 // the result of the conditional operator.
666 // Note: Most joins happen in `computeBlockInputState()`, but this case is
667 // different:
668 // - `computeBlockInputState()` (which in turn calls `Environment::join()`
669 // joins values associated with the _same_ expression or storage
670 // location, then associates the joined value with that expression or
671 // storage location. This join has nothing to do with transfer --
672 // instead, it joins together the results of performing transfer on two
673 // different blocks.
674 // - Here, we join values associated with _different_ expressions (the
675 // true and false branch), then associate the joined value with a third
676 // expression (the conditional operator itself). This join is what it
677 // means to perform transfer on the conditional operator.
678 if (Value *Val = Environment::joinValues(
679 Ty: S->getType(), Val1: TrueEnv->getValue(E: *S->getTrueExpr()), Env1: *TrueEnv,
680 Val2: FalseEnv->getValue(E: *S->getFalseExpr()), Env2: *FalseEnv, JoinedEnv&: Env, Model))
681 Env.setValue(*S, *Val);
682 }
683 }
684
685 void VisitInitListExpr(const InitListExpr *S) {
686 QualType Type = S->getType();
687
688 if (!Type->isRecordType()) {
689 // Until array initialization is implemented, we skip arrays and don't
690 // need to care about cases where `getNumInits() > 1`.
691 if (!Type->isArrayType() && S->getNumInits() == 1)
692 propagateValueOrStorageLocation(*S->getInit(Init: 0), *S, Env);
693 return;
694 }
695
696 // If the initializer list is transparent, there's nothing to do.
697 if (S->isSemanticForm() && S->isTransparent())
698 return;
699
700 RecordStorageLocation &Loc = Env.getResultObjectLocation(*S);
701
702 // Initialization of base classes and fields of record type happens when we
703 // visit the nested `CXXConstructExpr` or `InitListExpr` for that base class
704 // or field. We therefore only need to deal with fields of non-record type
705 // here.
706
707 RecordInitListHelper InitListHelper(S);
708
709 for (auto [Field, Init] : InitListHelper.field_inits()) {
710 if (Field->getType()->isRecordType())
711 continue;
712 if (Field->getType()->isReferenceType()) {
713 assert(Field->getType().getCanonicalType()->getPointeeType() ==
714 Init->getType().getCanonicalType());
715 Loc.setChild(D: *Field, Loc: &Env.createObject(Field->getType(), Init));
716 continue;
717 }
718 assert(Field->getType().getCanonicalType().getUnqualifiedType() ==
719 Init->getType().getCanonicalType().getUnqualifiedType());
720 StorageLocation *FieldLoc = Loc.getChild(*Field);
721 // Locations for non-reference fields must always be non-null.
722 assert(FieldLoc != nullptr);
723 Value *Val = Env.getValue(E: *Init);
724 if (Val == nullptr && isa<ImplicitValueInitExpr>(Val: Init) &&
725 Init->getType()->isPointerType())
726 Val =
727 &Env.getOrCreateNullPointerValue(PointeeType: Init->getType()->getPointeeType());
728 if (Val == nullptr)
729 Val = Env.createValue(Type: Field->getType());
730 if (Val != nullptr)
731 Env.setValue(Loc: *FieldLoc, Val&: *Val);
732 }
733
734 for (const auto &[FieldName, FieldLoc] : Loc.synthetic_fields()) {
735 QualType FieldType = FieldLoc->getType();
736 if (FieldType->isRecordType()) {
737 Env.initializeFieldsWithValues(*cast<RecordStorageLocation>(FieldLoc));
738 } else {
739 if (Value *Val = Env.createValue(FieldType))
740 Env.setValue(*FieldLoc, *Val);
741 }
742 }
743
744 // FIXME: Implement array initialization.
745 }
746
747 void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) {
748 Env.setValue(*S, Env.getBoolLiteralValue(Value: S->getValue()));
749 }
750
751 void VisitIntegerLiteral(const IntegerLiteral *S) {
752 Env.setValue(*S, Env.getIntLiteralValue(Value: S->getValue()));
753 }
754
755 void VisitParenExpr(const ParenExpr *S) {
756 // The CFG does not contain `ParenExpr` as top-level statements in basic
757 // blocks, however manual traversal to sub-expressions may encounter them.
758 // Redirect to the sub-expression.
759 auto *SubExpr = S->getSubExpr();
760 assert(SubExpr != nullptr);
761 Visit(SubExpr);
762 }
763
764 void VisitExprWithCleanups(const ExprWithCleanups *S) {
765 // The CFG does not contain `ExprWithCleanups` as top-level statements in
766 // basic blocks, however manual traversal to sub-expressions may encounter
767 // them. Redirect to the sub-expression.
768 auto *SubExpr = S->getSubExpr();
769 assert(SubExpr != nullptr);
770 Visit(SubExpr);
771 }
772
773private:
774 /// Returns the value for the sub-expression `SubExpr` of a logic operator.
775 BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
776 // `SubExpr` and its parent logic operator might be part of different basic
777 // blocks. We try to access the value that is assigned to `SubExpr` in the
778 // corresponding environment.
779 if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr))
780 if (auto *Val =
781 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr)))
782 return *Val;
783
784 // The sub-expression may lie within a basic block that isn't reachable,
785 // even if we need it to evaluate the current (reachable) expression
786 // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr`
787 // within the current environment and then try to get the value that gets
788 // assigned to it.
789 if (Env.getValue(E: SubExpr) == nullptr)
790 Visit(&SubExpr);
791 if (auto *Val = dyn_cast_or_null<BoolValue>(Val: Env.getValue(E: SubExpr)))
792 return *Val;
793
794 // If the value of `SubExpr` is still unknown, we create a fresh symbolic
795 // boolean value for it.
796 return Env.makeAtomicBoolValue();
797 }
798
799 // If context sensitivity is enabled, try to analyze the body of the callee
800 // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
801 template <typename E>
802 void transferInlineCall(const E *S, const FunctionDecl *F) {
803 const auto &Options = Env.getDataflowAnalysisContext().getOptions();
804 if (!(Options.ContextSensitiveOpts &&
805 Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
806 return;
807
808 const AdornedCFG *ACFG = Env.getDataflowAnalysisContext().getAdornedCFG(F);
809 if (!ACFG)
810 return;
811
812 // FIXME: We don't support context-sensitive analysis of recursion, so
813 // we should return early here if `F` is the same as the `FunctionDecl`
814 // holding `S` itself.
815
816 auto ExitBlock = ACFG->getCFG().getExit().getBlockID();
817
818 auto CalleeEnv = Env.pushCall(S);
819
820 // FIXME: Use the same analysis as the caller for the callee. Note,
821 // though, that doing so would require support for changing the analysis's
822 // ASTContext.
823 auto Analysis = NoopAnalysis(ACFG->getDecl().getASTContext(),
824 DataflowAnalysisOptions{.BuiltinOpts: Options});
825
826 auto BlockToOutputState =
827 dataflow::runDataflowAnalysis(*ACFG, Analysis, CalleeEnv);
828 assert(BlockToOutputState);
829 assert(ExitBlock < BlockToOutputState->size());
830
831 auto &ExitState = (*BlockToOutputState)[ExitBlock];
832 assert(ExitState);
833
834 Env.popCall(S, ExitState->Env);
835 }
836
837 const StmtToEnvMap &StmtToEnv;
838 Environment &Env;
839 Environment::ValueModel &Model;
840};
841
842} // namespace
843
844void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env,
845 Environment::ValueModel &Model) {
846 TransferVisitor(StmtToEnv, Env, Model).Visit(&S);
847}
848
849} // namespace dataflow
850} // namespace clang
851

source code of clang/lib/Analysis/FlowSensitive/Transfer.cpp