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