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