1 //===-- Transfer.cpp --------------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file defines transfer functions that evaluate program statements and
10 // update an environment accordingly.
12 //===----------------------------------------------------------------------===//
14 #include "clang/Analysis/FlowSensitive/Transfer.h"
15 #include "clang/AST/Decl.h"
16 #include "clang/AST/DeclBase.h"
17 #include "clang/AST/DeclCXX.h"
18 #include "clang/AST/Expr.h"
19 #include "clang/AST/ExprCXX.h"
20 #include "clang/AST/OperationKinds.h"
21 #include "clang/AST/Stmt.h"
22 #include "clang/AST/StmtVisitor.h"
23 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
25 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h"
26 #include "clang/Analysis/FlowSensitive/Value.h"
27 #include "clang/Basic/Builtins.h"
28 #include "clang/Basic/OperatorKinds.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/Casting.h"
31 #include "llvm/Support/ErrorHandling.h"
39 static BoolValue
&evaluateBooleanEquality(const Expr
&LHS
, const Expr
&RHS
,
42 dyn_cast_or_null
<BoolValue
>(Env
.getValue(LHS
, SkipPast::Reference
)))
44 dyn_cast_or_null
<BoolValue
>(Env
.getValue(RHS
, SkipPast::Reference
)))
45 return Env
.makeIff(*LHSValue
, *RHSValue
);
47 return Env
.makeAtomicBoolValue();
50 // Functionally updates `V` such that any instances of `TopBool` are replaced
51 // with fresh atomic bools. Note: This implementation assumes that `B` is a
52 // tree; if `B` is a DAG, it will lose any sharing between subvalues that was
53 // present in the original .
54 static BoolValue
&unpackValue(BoolValue
&V
, Environment
&Env
);
56 template <typename Derived
, typename M
>
57 BoolValue
&unpackBinaryBoolValue(Environment
&Env
, BoolValue
&B
, M build
) {
58 auto &V
= *cast
<Derived
>(&B
);
59 BoolValue
&Left
= V
.getLeftSubValue();
60 BoolValue
&Right
= V
.getRightSubValue();
61 BoolValue
&ULeft
= unpackValue(Left
, Env
);
62 BoolValue
&URight
= unpackValue(Right
, Env
);
64 if (&ULeft
== &Left
&& &URight
== &Right
)
67 return (Env
.*build
)(ULeft
, URight
);
70 static BoolValue
&unpackValue(BoolValue
&V
, Environment
&Env
) {
71 switch (V
.getKind()) {
72 case Value::Kind::Integer
:
73 case Value::Kind::Reference
:
74 case Value::Kind::Pointer
:
75 case Value::Kind::Struct
:
76 llvm_unreachable("BoolValue cannot have any of these kinds.");
78 case Value::Kind::AtomicBool
:
81 case Value::Kind::TopBool
:
82 // Unpack `TopBool` into a fresh atomic bool.
83 return Env
.makeAtomicBoolValue();
85 case Value::Kind::Negation
: {
86 auto &N
= *cast
<NegationValue
>(&V
);
87 BoolValue
&Sub
= N
.getSubVal();
88 BoolValue
&USub
= unpackValue(Sub
, Env
);
92 return Env
.makeNot(USub
);
94 case Value::Kind::Conjunction
:
95 return unpackBinaryBoolValue
<ConjunctionValue
>(Env
, V
,
96 &Environment::makeAnd
);
97 case Value::Kind::Disjunction
:
98 return unpackBinaryBoolValue
<DisjunctionValue
>(Env
, V
,
99 &Environment::makeOr
);
100 case Value::Kind::Implication
:
101 return unpackBinaryBoolValue
<ImplicationValue
>(
102 Env
, V
, &Environment::makeImplication
);
103 case Value::Kind::Biconditional
:
104 return unpackBinaryBoolValue
<BiconditionalValue
>(Env
, V
,
105 &Environment::makeIff
);
107 llvm_unreachable("All reachable cases in switch return");
110 // Unpacks the value (if any) associated with `E` and updates `E` to the new
111 // value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion,
112 // by skipping past the reference.
113 static Value
*maybeUnpackLValueExpr(const Expr
&E
, Environment
&Env
) {
114 // FIXME: this is too flexible: it _allows_ a reference, while it should
115 // _require_ one, since lvalues should always be wrapped in `ReferenceValue`.
116 auto *Loc
= Env
.getStorageLocation(E
, SkipPast::Reference
);
119 auto *Val
= Env
.getValue(*Loc
);
121 auto *B
= dyn_cast_or_null
<BoolValue
>(Val
);
125 auto &UnpackedVal
= unpackValue(*B
, Env
);
126 if (&UnpackedVal
== Val
)
128 Env
.setValue(*Loc
, UnpackedVal
);
132 class TransferVisitor
: public ConstStmtVisitor
<TransferVisitor
> {
134 TransferVisitor(const StmtToEnvMap
&StmtToEnv
, Environment
&Env
)
135 : StmtToEnv(StmtToEnv
), Env(Env
) {}
137 void VisitBinaryOperator(const BinaryOperator
*S
) {
138 const Expr
*LHS
= S
->getLHS();
139 assert(LHS
!= nullptr);
141 const Expr
*RHS
= S
->getRHS();
142 assert(RHS
!= nullptr);
144 switch (S
->getOpcode()) {
146 auto *LHSLoc
= Env
.getStorageLocation(*LHS
, SkipPast::Reference
);
147 if (LHSLoc
== nullptr)
150 // No skipping should be necessary, because any lvalues should have
151 // already been stripped off in evaluating the LValueToRValue cast.
152 auto *RHSVal
= Env
.getValue(*RHS
, SkipPast::None
);
153 if (RHSVal
== nullptr)
156 // Assign a value to the storage location of the left-hand side.
157 Env
.setValue(*LHSLoc
, *RHSVal
);
159 // Assign a storage location for the whole expression.
160 Env
.setStorageLocation(*S
, *LHSLoc
);
165 BoolValue
&LHSVal
= getLogicOperatorSubExprValue(*LHS
);
166 BoolValue
&RHSVal
= getLogicOperatorSubExprValue(*RHS
);
168 auto &Loc
= Env
.createStorageLocation(*S
);
169 Env
.setStorageLocation(*S
, Loc
);
170 if (S
->getOpcode() == BO_LAnd
)
171 Env
.setValue(Loc
, Env
.makeAnd(LHSVal
, RHSVal
));
173 Env
.setValue(Loc
, Env
.makeOr(LHSVal
, RHSVal
));
178 auto &LHSEqRHSValue
= evaluateBooleanEquality(*LHS
, *RHS
, Env
);
179 auto &Loc
= Env
.createStorageLocation(*S
);
180 Env
.setStorageLocation(*S
, Loc
);
181 Env
.setValue(Loc
, S
->getOpcode() == BO_EQ
? LHSEqRHSValue
182 : Env
.makeNot(LHSEqRHSValue
));
186 if (auto *Loc
= Env
.getStorageLocation(*RHS
, SkipPast::None
))
187 Env
.setStorageLocation(*S
, *Loc
);
195 void VisitDeclRefExpr(const DeclRefExpr
*S
) {
196 const ValueDecl
*VD
= S
->getDecl();
197 assert(VD
!= nullptr);
198 auto *DeclLoc
= Env
.getStorageLocation(*VD
, SkipPast::None
);
199 if (DeclLoc
== nullptr)
202 // If the value is already an lvalue, don't double-wrap it.
203 if (isa_and_nonnull
<ReferenceValue
>(Env
.getValue(*DeclLoc
))) {
204 // We only expect to encounter a `ReferenceValue` for a reference type
205 // (always) or for `BindingDecl` (sometimes). For the latter, we can't
206 // rely on type, because their type does not indicate whether they are a
207 // reference type. The assert is not strictly necessary, since we don't
208 // depend on its truth to proceed. But, it verifies our assumptions,
209 // which, if violated, probably indicate a problem elsewhere.
210 assert((VD
->getType()->isReferenceType() || isa
<BindingDecl
>(VD
)) &&
211 "Only reference-typed declarations or `BindingDecl`s should map "
212 "to `ReferenceValue`s");
213 Env
.setStorageLocation(*S
, *DeclLoc
);
215 auto &Loc
= Env
.createStorageLocation(*S
);
216 auto &Val
= Env
.takeOwnership(std::make_unique
<ReferenceValue
>(*DeclLoc
));
217 Env
.setStorageLocation(*S
, Loc
);
218 Env
.setValue(Loc
, Val
);
222 void VisitDeclStmt(const DeclStmt
*S
) {
223 // Group decls are converted into single decls in the CFG so the cast below
225 const auto &D
= *cast
<VarDecl
>(S
->getSingleDecl());
227 // Static local vars are already initialized in `Environment`.
228 if (D
.hasGlobalStorage())
231 // The storage location for `D` could have been created earlier, before the
232 // variable's declaration statement (for example, in the case of
234 auto *MaybeLoc
= Env
.getStorageLocation(D
, SkipPast::None
);
235 if (MaybeLoc
== nullptr) {
236 MaybeLoc
= &Env
.createStorageLocation(D
);
237 Env
.setStorageLocation(D
, *MaybeLoc
);
239 auto &Loc
= *MaybeLoc
;
241 const Expr
*InitExpr
= D
.getInit();
242 if (InitExpr
== nullptr) {
243 // No initializer expression - associate `Loc` with a new value.
244 if (Value
*Val
= Env
.createValue(D
.getType()))
245 Env
.setValue(Loc
, *Val
);
249 if (D
.getType()->isReferenceType()) {
250 // Initializing a reference variable - do not create a reference to
252 // FIXME: reuse the ReferenceValue instead of creating a new one.
253 if (auto *InitExprLoc
=
254 Env
.getStorageLocation(*InitExpr
, SkipPast::Reference
)) {
256 Env
.takeOwnership(std::make_unique
<ReferenceValue
>(*InitExprLoc
));
257 Env
.setValue(Loc
, Val
);
259 } else if (auto *InitExprVal
= Env
.getValue(*InitExpr
, SkipPast::None
)) {
260 Env
.setValue(Loc
, *InitExprVal
);
263 if (Env
.getValue(Loc
) == nullptr) {
264 // We arrive here in (the few) cases where an expression is intentionally
265 // "uninterpreted". There are two ways to handle this situation: propagate
266 // the status, so that uninterpreted initializers result in uninterpreted
267 // variables, or provide a default value. We choose the latter so that
268 // later refinements of the variable can be used for reasoning about the
271 // FIXME. If and when we interpret all language cases, change this to
272 // assert that `InitExpr` is interpreted, rather than supplying a default
273 // value (assuming we don't update the environment API to return
275 if (Value
*Val
= Env
.createValue(D
.getType()))
276 Env
.setValue(Loc
, *Val
);
279 // `DecompositionDecl` must be handled after we've interpreted the loc
280 // itself, because the binding expression refers back to the
281 // `DecompositionDecl` (even though it has no written name).
282 if (const auto *Decomp
= dyn_cast
<DecompositionDecl
>(&D
)) {
283 // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This
284 // needs to be evaluated after initializing the values in the storage for
285 // VarDecl, as the bindings refer to them.
286 // FIXME: Add support for ArraySubscriptExpr.
287 // FIXME: Consider adding AST nodes used in BindingDecls to the CFG.
288 for (const auto *B
: Decomp
->bindings()) {
289 if (auto *ME
= dyn_cast_or_null
<MemberExpr
>(B
->getBinding())) {
290 auto *DE
= dyn_cast_or_null
<DeclRefExpr
>(ME
->getBase());
294 // ME and its base haven't been visited because they aren't included
295 // in the statements of the CFG basic block.
296 VisitDeclRefExpr(DE
);
299 if (auto *Loc
= Env
.getStorageLocation(*ME
, SkipPast::Reference
))
300 Env
.setStorageLocation(*B
, *Loc
);
301 } else if (auto *VD
= B
->getHoldingVar()) {
302 // Holding vars are used to back the BindingDecls of tuple-like
303 // types. The holding var declarations appear *after* this statement,
304 // so we have to create a location for them here to share with `B`. We
305 // don't visit the binding, because we know it will be a DeclRefExpr
306 // to `VD`. Note that, by construction of the AST, `VD` will always be
307 // a reference -- either lvalue or rvalue.
308 auto &VDLoc
= Env
.createStorageLocation(*VD
);
309 Env
.setStorageLocation(*VD
, VDLoc
);
310 Env
.setStorageLocation(*B
, VDLoc
);
316 void VisitImplicitCastExpr(const ImplicitCastExpr
*S
) {
317 const Expr
*SubExpr
= S
->getSubExpr();
318 assert(SubExpr
!= nullptr);
320 switch (S
->getCastKind()) {
321 case CK_IntegralToBoolean
: {
322 // This cast creates a new, boolean value from the integral value. We
323 // model that with a fresh value in the environment, unless it's already a
325 auto &Loc
= Env
.createStorageLocation(*S
);
326 Env
.setStorageLocation(*S
, Loc
);
327 if (auto *SubExprVal
= dyn_cast_or_null
<BoolValue
>(
328 Env
.getValue(*SubExpr
, SkipPast::Reference
)))
329 Env
.setValue(Loc
, *SubExprVal
);
331 // FIXME: If integer modeling is added, then update this code to create
332 // the boolean based on the integer model.
333 Env
.setValue(Loc
, Env
.makeAtomicBoolValue());
337 case CK_LValueToRValue
: {
338 // When an L-value is used as an R-value, it may result in sharing, so we
339 // need to unpack any nested `Top`s. We also need to strip off the
340 // `ReferenceValue` associated with the lvalue.
341 auto *SubExprVal
= maybeUnpackLValueExpr(*SubExpr
, Env
);
342 if (SubExprVal
== nullptr)
345 auto &ExprLoc
= Env
.createStorageLocation(*S
);
346 Env
.setStorageLocation(*S
, ExprLoc
);
347 Env
.setValue(ExprLoc
, *SubExprVal
);
351 case CK_IntegralCast
:
352 // FIXME: This cast creates a new integral value from the
353 // subexpression. But, because we don't model integers, we don't
354 // distinguish between this new value and the underlying one. If integer
355 // modeling is added, then update this code to create a fresh location and
357 case CK_UncheckedDerivedToBase
:
358 case CK_ConstructorConversion
:
359 case CK_UserDefinedConversion
:
360 // FIXME: Add tests that excercise CK_UncheckedDerivedToBase,
361 // CK_ConstructorConversion, and CK_UserDefinedConversion.
363 // FIXME: Consider making `Environment::getStorageLocation` skip noop
364 // expressions (this and other similar expressions in the file) instead of
365 // assigning them storage locations.
366 auto *SubExprLoc
= Env
.getStorageLocation(*SubExpr
, SkipPast::None
);
367 if (SubExprLoc
== nullptr)
370 Env
.setStorageLocation(*S
, *SubExprLoc
);
373 case CK_NullToPointer
:
374 case CK_NullToMemberPointer
: {
375 auto &Loc
= Env
.createStorageLocation(S
->getType());
376 Env
.setStorageLocation(*S
, Loc
);
378 auto &NullPointerVal
=
379 Env
.getOrCreateNullPointerValue(S
->getType()->getPointeeType());
380 Env
.setValue(Loc
, NullPointerVal
);
388 void VisitUnaryOperator(const UnaryOperator
*S
) {
389 const Expr
*SubExpr
= S
->getSubExpr();
390 assert(SubExpr
!= nullptr);
392 switch (S
->getOpcode()) {
394 // Skip past a reference to handle dereference of a dependent pointer.
395 const auto *SubExprVal
= cast_or_null
<PointerValue
>(
396 Env
.getValue(*SubExpr
, SkipPast::Reference
));
397 if (SubExprVal
== nullptr)
400 auto &Loc
= Env
.createStorageLocation(*S
);
401 Env
.setStorageLocation(*S
, Loc
);
402 Env
.setValue(Loc
, Env
.takeOwnership(std::make_unique
<ReferenceValue
>(
403 SubExprVal
->getPointeeLoc())));
407 // Do not form a pointer to a reference. If `SubExpr` is assigned a
408 // `ReferenceValue` then form a value that points to the location of its
410 StorageLocation
*PointeeLoc
=
411 Env
.getStorageLocation(*SubExpr
, SkipPast::Reference
);
412 if (PointeeLoc
== nullptr)
415 auto &PointerLoc
= Env
.createStorageLocation(*S
);
417 Env
.takeOwnership(std::make_unique
<PointerValue
>(*PointeeLoc
));
418 Env
.setStorageLocation(*S
, PointerLoc
);
419 Env
.setValue(PointerLoc
, PointerVal
);
424 dyn_cast_or_null
<BoolValue
>(Env
.getValue(*SubExpr
, SkipPast::None
));
425 if (SubExprVal
== nullptr)
428 auto &ExprLoc
= Env
.createStorageLocation(*S
);
429 Env
.setStorageLocation(*S
, ExprLoc
);
430 Env
.setValue(ExprLoc
, Env
.makeNot(*SubExprVal
));
438 void VisitCXXThisExpr(const CXXThisExpr
*S
) {
439 auto *ThisPointeeLoc
= Env
.getThisPointeeStorageLocation();
440 if (ThisPointeeLoc
== nullptr)
441 // Unions are not supported yet, and will not have a location for the
442 // `this` expression's pointee.
445 auto &Loc
= Env
.createStorageLocation(*S
);
446 Env
.setStorageLocation(*S
, Loc
);
447 Env
.setValue(Loc
, Env
.takeOwnership(
448 std::make_unique
<PointerValue
>(*ThisPointeeLoc
)));
451 void VisitReturnStmt(const ReturnStmt
*S
) {
452 if (!Env
.getAnalysisOptions().ContextSensitiveOpts
)
455 auto *Ret
= S
->getRetValue();
459 auto *Val
= Env
.getValue(*Ret
, SkipPast::None
);
463 // FIXME: Support reference-type returns.
464 if (Val
->getKind() == Value::Kind::Reference
)
467 auto *Loc
= Env
.getReturnStorageLocation();
468 assert(Loc
!= nullptr);
469 // FIXME: Support reference-type returns.
470 if (Loc
->getType()->isReferenceType())
473 // FIXME: Model NRVO.
474 Env
.setValue(*Loc
, *Val
);
477 void VisitMemberExpr(const MemberExpr
*S
) {
478 ValueDecl
*Member
= S
->getMemberDecl();
479 assert(Member
!= nullptr);
481 // FIXME: Consider assigning pointer values to function member expressions.
482 if (Member
->isFunctionOrFunctionTemplate())
485 // FIXME: if/when we add support for modeling enums, use that support here.
486 if (isa
<EnumConstantDecl
>(Member
))
489 if (auto *D
= dyn_cast
<VarDecl
>(Member
)) {
490 if (D
->hasGlobalStorage()) {
491 auto *VarDeclLoc
= Env
.getStorageLocation(*D
, SkipPast::None
);
492 if (VarDeclLoc
== nullptr)
495 if (VarDeclLoc
->getType()->isReferenceType()) {
496 assert(isa_and_nonnull
<ReferenceValue
>(Env
.getValue((*VarDeclLoc
))) &&
497 "reference-typed declarations map to `ReferenceValue`s");
498 Env
.setStorageLocation(*S
, *VarDeclLoc
);
500 auto &Loc
= Env
.createStorageLocation(*S
);
501 Env
.setStorageLocation(*S
, Loc
);
502 Env
.setValue(Loc
, Env
.takeOwnership(
503 std::make_unique
<ReferenceValue
>(*VarDeclLoc
)));
509 // The receiver can be either a value or a pointer to a value. Skip past the
510 // indirection to handle both cases.
511 auto *BaseLoc
= cast_or_null
<AggregateStorageLocation
>(
512 Env
.getStorageLocation(*S
->getBase(), SkipPast::ReferenceThenPointer
));
513 if (BaseLoc
== nullptr)
516 auto &MemberLoc
= BaseLoc
->getChild(*Member
);
517 if (MemberLoc
.getType()->isReferenceType()) {
518 // Based on its type, `MemberLoc` must be mapped either to nothing or to a
519 // `ReferenceValue`. For the former, we won't set a storage location for
520 // this expression, so as to maintain an invariant lvalue expressions;
521 // namely, that their location maps to a `ReferenceValue`. In this,
522 // lvalues are unlike other expressions, where it is valid for their
523 // location to map to nothing (because they are not modeled).
525 // Note: we need this invariant for lvalues so that, when accessing a
526 // value, we can distinguish an rvalue from an lvalue. An alternative
527 // design, which takes the expression's value category into account, would
528 // avoid the need for this invariant.
529 if (auto *V
= Env
.getValue(MemberLoc
)) {
530 assert(isa
<ReferenceValue
>(V
) &&
531 "reference-typed declarations map to `ReferenceValue`s");
532 Env
.setStorageLocation(*S
, MemberLoc
);
535 auto &Loc
= Env
.createStorageLocation(*S
);
536 Env
.setStorageLocation(*S
, Loc
);
538 Loc
, Env
.takeOwnership(std::make_unique
<ReferenceValue
>(MemberLoc
)));
542 void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr
*S
) {
543 const Expr
*InitExpr
= S
->getExpr();
544 assert(InitExpr
!= nullptr);
546 Value
*InitExprVal
= Env
.getValue(*InitExpr
, SkipPast::None
);
547 if (InitExprVal
== nullptr)
550 const FieldDecl
*Field
= S
->getField();
551 assert(Field
!= nullptr);
554 *cast
<AggregateStorageLocation
>(Env
.getThisPointeeStorageLocation());
555 auto &FieldLoc
= ThisLoc
.getChild(*Field
);
556 Env
.setValue(FieldLoc
, *InitExprVal
);
559 void VisitCXXConstructExpr(const CXXConstructExpr
*S
) {
560 const CXXConstructorDecl
*ConstructorDecl
= S
->getConstructor();
561 assert(ConstructorDecl
!= nullptr);
563 if (ConstructorDecl
->isCopyOrMoveConstructor()) {
564 assert(S
->getNumArgs() == 1);
566 const Expr
*Arg
= S
->getArg(0);
567 assert(Arg
!= nullptr);
569 if (S
->isElidable()) {
570 auto *ArgLoc
= Env
.getStorageLocation(*Arg
, SkipPast::Reference
);
571 if (ArgLoc
== nullptr)
574 Env
.setStorageLocation(*S
, *ArgLoc
);
575 } else if (auto *ArgVal
= Env
.getValue(*Arg
, SkipPast::Reference
)) {
576 auto &Loc
= Env
.createStorageLocation(*S
);
577 Env
.setStorageLocation(*S
, Loc
);
578 Env
.setValue(Loc
, *ArgVal
);
583 auto &Loc
= Env
.createStorageLocation(*S
);
584 Env
.setStorageLocation(*S
, Loc
);
585 if (Value
*Val
= Env
.createValue(S
->getType()))
586 Env
.setValue(Loc
, *Val
);
588 transferInlineCall(S
, ConstructorDecl
);
591 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr
*S
) {
592 if (S
->getOperator() == OO_Equal
) {
593 assert(S
->getNumArgs() == 2);
595 const Expr
*Arg0
= S
->getArg(0);
596 assert(Arg0
!= nullptr);
598 const Expr
*Arg1
= S
->getArg(1);
599 assert(Arg1
!= nullptr);
601 // Evaluate only copy and move assignment operators.
602 auto *Arg0Type
= Arg0
->getType()->getUnqualifiedDesugaredType();
603 auto *Arg1Type
= Arg1
->getType()->getUnqualifiedDesugaredType();
604 if (Arg0Type
!= Arg1Type
)
607 auto *ObjectLoc
= Env
.getStorageLocation(*Arg0
, SkipPast::Reference
);
608 if (ObjectLoc
== nullptr)
611 auto *Val
= Env
.getValue(*Arg1
, SkipPast::Reference
);
615 // Assign a value to the storage location of the object.
616 Env
.setValue(*ObjectLoc
, *Val
);
618 // FIXME: Add a test for the value of the whole expression.
619 // Assign a storage location for the whole expression.
620 Env
.setStorageLocation(*S
, *ObjectLoc
);
624 void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr
*S
) {
625 if (S
->getCastKind() == CK_ConstructorConversion
) {
626 const Expr
*SubExpr
= S
->getSubExpr();
627 assert(SubExpr
!= nullptr);
629 auto *SubExprLoc
= Env
.getStorageLocation(*SubExpr
, SkipPast::None
);
630 if (SubExprLoc
== nullptr)
633 Env
.setStorageLocation(*S
, *SubExprLoc
);
637 void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr
*S
) {
638 auto &Loc
= Env
.createStorageLocation(*S
);
639 Env
.setStorageLocation(*S
, Loc
);
640 if (Value
*Val
= Env
.createValue(S
->getType()))
641 Env
.setValue(Loc
, *Val
);
644 void VisitCallExpr(const CallExpr
*S
) {
645 // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
646 // others (like trap, debugtrap, and unreachable) are handled by CFG
648 if (S
->isCallToStdMove()) {
649 assert(S
->getNumArgs() == 1);
651 const Expr
*Arg
= S
->getArg(0);
652 assert(Arg
!= nullptr);
654 auto *ArgLoc
= Env
.getStorageLocation(*Arg
, SkipPast::None
);
655 if (ArgLoc
== nullptr)
658 Env
.setStorageLocation(*S
, *ArgLoc
);
659 } else if (S
->getDirectCallee() != nullptr &&
660 S
->getDirectCallee()->getBuiltinID() ==
661 Builtin::BI__builtin_expect
) {
662 assert(S
->getNumArgs() > 0);
663 assert(S
->getArg(0) != nullptr);
664 // `__builtin_expect` returns by-value, so strip away any potential
665 // references in the argument.
666 auto *ArgLoc
= Env
.getStorageLocation(*S
->getArg(0), SkipPast::Reference
);
667 if (ArgLoc
== nullptr)
669 Env
.setStorageLocation(*S
, *ArgLoc
);
670 } else if (const FunctionDecl
*F
= S
->getDirectCallee()) {
671 transferInlineCall(S
, F
);
675 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr
*S
) {
676 const Expr
*SubExpr
= S
->getSubExpr();
677 assert(SubExpr
!= nullptr);
679 auto *SubExprLoc
= Env
.getStorageLocation(*SubExpr
, SkipPast::None
);
680 if (SubExprLoc
== nullptr)
683 Env
.setStorageLocation(*S
, *SubExprLoc
);
686 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr
*S
) {
687 const Expr
*SubExpr
= S
->getSubExpr();
688 assert(SubExpr
!= nullptr);
690 auto *SubExprLoc
= Env
.getStorageLocation(*SubExpr
, SkipPast::None
);
691 if (SubExprLoc
== nullptr)
694 Env
.setStorageLocation(*S
, *SubExprLoc
);
697 void VisitCXXStaticCastExpr(const CXXStaticCastExpr
*S
) {
698 if (S
->getCastKind() == CK_NoOp
) {
699 const Expr
*SubExpr
= S
->getSubExpr();
700 assert(SubExpr
!= nullptr);
702 auto *SubExprLoc
= Env
.getStorageLocation(*SubExpr
, SkipPast::None
);
703 if (SubExprLoc
== nullptr)
706 Env
.setStorageLocation(*S
, *SubExprLoc
);
710 void VisitConditionalOperator(const ConditionalOperator
*S
) {
711 // FIXME: Revisit this once flow conditions are added to the framework. For
712 // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow
714 auto &Loc
= Env
.createStorageLocation(*S
);
715 Env
.setStorageLocation(*S
, Loc
);
716 if (Value
*Val
= Env
.createValue(S
->getType()))
717 Env
.setValue(Loc
, *Val
);
720 void VisitInitListExpr(const InitListExpr
*S
) {
721 QualType Type
= S
->getType();
723 auto &Loc
= Env
.createStorageLocation(*S
);
724 Env
.setStorageLocation(*S
, Loc
);
726 auto *Val
= Env
.createValue(Type
);
730 Env
.setValue(Loc
, *Val
);
732 if (Type
->isStructureOrClassType()) {
733 for (auto It
: llvm::zip(Type
->getAsRecordDecl()->fields(), S
->inits())) {
734 const FieldDecl
*Field
= std::get
<0>(It
);
735 assert(Field
!= nullptr);
737 const Expr
*Init
= std::get
<1>(It
);
738 assert(Init
!= nullptr);
740 if (Value
*InitVal
= Env
.getValue(*Init
, SkipPast::None
))
741 cast
<StructValue
>(Val
)->setChild(*Field
, *InitVal
);
744 // FIXME: Implement array initialization.
747 void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr
*S
) {
748 auto &Loc
= Env
.createStorageLocation(*S
);
749 Env
.setStorageLocation(*S
, Loc
);
750 Env
.setValue(Loc
, Env
.getBoolLiteralValue(S
->getValue()));
753 void VisitParenExpr(const ParenExpr
*S
) {
754 // The CFG does not contain `ParenExpr` as top-level statements in basic
755 // blocks, however manual traversal to sub-expressions may encounter them.
756 // Redirect to the sub-expression.
757 auto *SubExpr
= S
->getSubExpr();
758 assert(SubExpr
!= nullptr);
762 void VisitExprWithCleanups(const ExprWithCleanups
*S
) {
763 // The CFG does not contain `ExprWithCleanups` as top-level statements in
764 // basic blocks, however manual traversal to sub-expressions may encounter
765 // them. Redirect to the sub-expression.
766 auto *SubExpr
= S
->getSubExpr();
767 assert(SubExpr
!= nullptr);
772 BoolValue
&getLogicOperatorSubExprValue(const Expr
&SubExpr
) {
773 // `SubExpr` and its parent logic operator might be part of different basic
774 // blocks. We try to access the value that is assigned to `SubExpr` in the
775 // corresponding environment.
776 if (const Environment
*SubExprEnv
= StmtToEnv
.getEnvironment(SubExpr
)) {
777 if (auto *Val
= dyn_cast_or_null
<BoolValue
>(
778 SubExprEnv
->getValue(SubExpr
, SkipPast::Reference
)))
782 if (Env
.getStorageLocation(SubExpr
, SkipPast::None
) == nullptr) {
783 // Sub-expressions that are logic operators are not added in basic blocks
784 // (e.g. see CFG for `bool d = a && (b || c);`). If `SubExpr` is a logic
785 // operator, it may not have been evaluated and assigned a value yet. In
786 // that case, we need to first visit `SubExpr` and then try to get the
787 // value that gets assigned to it.
791 if (auto *Val
= dyn_cast_or_null
<BoolValue
>(
792 Env
.getValue(SubExpr
, SkipPast::Reference
)))
795 // If the value of `SubExpr` is still unknown, we create a fresh symbolic
796 // boolean value for it.
797 return Env
.makeAtomicBoolValue();
800 // If context sensitivity is enabled, try to analyze the body of the callee
801 // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
802 template <typename E
>
803 void transferInlineCall(const E
*S
, const FunctionDecl
*F
) {
804 const auto &Options
= Env
.getAnalysisOptions();
805 if (!(Options
.ContextSensitiveOpts
&&
806 Env
.canDescend(Options
.ContextSensitiveOpts
->Depth
, F
)))
809 const ControlFlowContext
*CFCtx
= Env
.getControlFlowContext(F
);
813 // FIXME: We don't support context-sensitive analysis of recursion, so
814 // we should return early here if `F` is the same as the `FunctionDecl`
815 // holding `S` itself.
817 auto ExitBlock
= CFCtx
->getCFG().getExit().getBlockID();
819 if (const auto *NonConstructExpr
= dyn_cast
<CallExpr
>(S
)) {
820 // Note that it is important for the storage location of `S` to be set
821 // before `pushCall`, because the latter uses it to set the storage
822 // location for `return`.
823 auto &ReturnLoc
= Env
.createStorageLocation(*S
);
824 Env
.setStorageLocation(*S
, ReturnLoc
);
826 auto CalleeEnv
= Env
.pushCall(S
);
828 // FIXME: Use the same analysis as the caller for the callee. Note,
829 // though, that doing so would require support for changing the analysis's
831 assert(CFCtx
->getDecl() != nullptr &&
832 "ControlFlowContexts in the environment should always carry a decl");
833 auto Analysis
= NoopAnalysis(CFCtx
->getDecl()->getASTContext(),
834 DataflowAnalysisOptions
{Options
});
836 auto BlockToOutputState
=
837 dataflow::runDataflowAnalysis(*CFCtx
, Analysis
, CalleeEnv
);
838 assert(BlockToOutputState
);
839 assert(ExitBlock
< BlockToOutputState
->size());
841 auto ExitState
= (*BlockToOutputState
)[ExitBlock
];
844 Env
.popCall(ExitState
->Env
);
847 const StmtToEnvMap
&StmtToEnv
;
851 void transfer(const StmtToEnvMap
&StmtToEnv
, const Stmt
&S
, Environment
&Env
) {
852 TransferVisitor(StmtToEnv
, Env
).Visit(&S
);
855 } // namespace dataflow