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