[clang] Handle __declspec() attributes in using
[llvm-project.git] / clang / lib / Analysis / FlowSensitive / Transfer.cpp
blob74dd59851ad44571d6a5d47432860a8f1d557e14
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.
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"
32 #include <cassert>
33 #include <memory>
34 #include <tuple>
36 namespace clang {
37 namespace dataflow {
39 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS,
40 Environment &Env) {
41 if (auto *LHSValue =
42 dyn_cast_or_null<BoolValue>(Env.getValue(LHS, SkipPast::Reference)))
43 if (auto *RHSValue =
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)
65 return V;
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:
79 return V;
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);
90 if (&USub == &Sub)
91 return V;
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);
117 if (Loc == nullptr)
118 return nullptr;
119 auto *Val = Env.getValue(*Loc);
121 auto *B = dyn_cast_or_null<BoolValue>(Val);
122 if (B == nullptr)
123 return Val;
125 auto &UnpackedVal = unpackValue(*B, Env);
126 if (&UnpackedVal == Val)
127 return Val;
128 Env.setValue(*Loc, UnpackedVal);
129 return &UnpackedVal;
132 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> {
133 public:
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()) {
145 case BO_Assign: {
146 auto *LHSLoc = Env.getStorageLocation(*LHS, SkipPast::Reference);
147 if (LHSLoc == nullptr)
148 break;
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)
154 break;
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);
161 break;
163 case BO_LAnd:
164 case BO_LOr: {
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));
172 else
173 Env.setValue(Loc, Env.makeOr(LHSVal, RHSVal));
174 break;
176 case BO_NE:
177 case BO_EQ: {
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));
183 break;
185 case BO_Comma: {
186 if (auto *Loc = Env.getStorageLocation(*RHS, SkipPast::None))
187 Env.setStorageLocation(*S, *Loc);
188 break;
190 default:
191 break;
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)
200 return;
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);
214 } else {
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
224 // is safe.
225 const auto &D = *cast<VarDecl>(S->getSingleDecl());
227 // Static local vars are already initialized in `Environment`.
228 if (D.hasGlobalStorage())
229 return;
231 // The storage location for `D` could have been created earlier, before the
232 // variable's declaration statement (for example, in the case of
233 // BindingDecls).
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);
246 return;
249 if (D.getType()->isReferenceType()) {
250 // Initializing a reference variable - do not create a reference to
251 // reference.
252 // FIXME: reuse the ReferenceValue instead of creating a new one.
253 if (auto *InitExprLoc =
254 Env.getStorageLocation(*InitExpr, SkipPast::Reference)) {
255 auto &Val =
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
269 // surrounding code.
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
274 // references).
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());
291 if (DE == nullptr)
292 continue;
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);
297 VisitMemberExpr(ME);
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
324 // boolean.
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);
330 else
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());
334 break;
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)
343 break;
345 auto &ExprLoc = Env.createStorageLocation(*S);
346 Env.setStorageLocation(*S, ExprLoc);
347 Env.setValue(ExprLoc, *SubExprVal);
348 break;
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
356 // value.
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.
362 case CK_NoOp: {
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)
368 break;
370 Env.setStorageLocation(*S, *SubExprLoc);
371 break;
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);
381 break;
383 default:
384 break;
388 void VisitUnaryOperator(const UnaryOperator *S) {
389 const Expr *SubExpr = S->getSubExpr();
390 assert(SubExpr != nullptr);
392 switch (S->getOpcode()) {
393 case UO_Deref: {
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)
398 break;
400 auto &Loc = Env.createStorageLocation(*S);
401 Env.setStorageLocation(*S, Loc);
402 Env.setValue(Loc, Env.takeOwnership(std::make_unique<ReferenceValue>(
403 SubExprVal->getPointeeLoc())));
404 break;
406 case UO_AddrOf: {
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
409 // pointee.
410 StorageLocation *PointeeLoc =
411 Env.getStorageLocation(*SubExpr, SkipPast::Reference);
412 if (PointeeLoc == nullptr)
413 break;
415 auto &PointerLoc = Env.createStorageLocation(*S);
416 auto &PointerVal =
417 Env.takeOwnership(std::make_unique<PointerValue>(*PointeeLoc));
418 Env.setStorageLocation(*S, PointerLoc);
419 Env.setValue(PointerLoc, PointerVal);
420 break;
422 case UO_LNot: {
423 auto *SubExprVal =
424 dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr, SkipPast::None));
425 if (SubExprVal == nullptr)
426 break;
428 auto &ExprLoc = Env.createStorageLocation(*S);
429 Env.setStorageLocation(*S, ExprLoc);
430 Env.setValue(ExprLoc, Env.makeNot(*SubExprVal));
431 break;
433 default:
434 break;
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.
443 return;
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)
453 return;
455 auto *Ret = S->getRetValue();
456 if (Ret == nullptr)
457 return;
459 auto *Val = Env.getValue(*Ret, SkipPast::None);
460 if (Val == nullptr)
461 return;
463 // FIXME: Support reference-type returns.
464 if (Val->getKind() == Value::Kind::Reference)
465 return;
467 auto *Loc = Env.getReturnStorageLocation();
468 assert(Loc != nullptr);
469 // FIXME: Support reference-type returns.
470 if (Loc->getType()->isReferenceType())
471 return;
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())
483 return;
485 // FIXME: if/when we add support for modeling enums, use that support here.
486 if (isa<EnumConstantDecl>(Member))
487 return;
489 if (auto *D = dyn_cast<VarDecl>(Member)) {
490 if (D->hasGlobalStorage()) {
491 auto *VarDeclLoc = Env.getStorageLocation(*D, SkipPast::None);
492 if (VarDeclLoc == nullptr)
493 return;
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);
499 } else {
500 auto &Loc = Env.createStorageLocation(*S);
501 Env.setStorageLocation(*S, Loc);
502 Env.setValue(Loc, Env.takeOwnership(
503 std::make_unique<ReferenceValue>(*VarDeclLoc)));
505 return;
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)
514 return;
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);
534 } else {
535 auto &Loc = Env.createStorageLocation(*S);
536 Env.setStorageLocation(*S, Loc);
537 Env.setValue(
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)
548 return;
550 const FieldDecl *Field = S->getField();
551 assert(Field != nullptr);
553 auto &ThisLoc =
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)
572 return;
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);
580 return;
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)
605 return;
607 auto *ObjectLoc = Env.getStorageLocation(*Arg0, SkipPast::Reference);
608 if (ObjectLoc == nullptr)
609 return;
611 auto *Val = Env.getValue(*Arg1, SkipPast::Reference);
612 if (Val == nullptr)
613 return;
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)
631 return;
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
647 // construction.
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)
656 return;
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)
668 return;
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)
681 return;
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)
692 return;
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)
704 return;
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
713 // condition.
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);
727 if (Val == nullptr)
728 return;
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);
759 Visit(SubExpr);
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);
768 Visit(SubExpr);
771 private:
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)))
779 return *Val;
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.
788 Visit(&SubExpr);
791 if (auto *Val = dyn_cast_or_null<BoolValue>(
792 Env.getValue(SubExpr, SkipPast::Reference)))
793 return *Val;
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)))
807 return;
809 const ControlFlowContext *CFCtx = Env.getControlFlowContext(F);
810 if (!CFCtx)
811 return;
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
830 // ASTContext.
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];
842 assert(ExitState);
844 Env.popCall(ExitState->Env);
847 const StmtToEnvMap &StmtToEnv;
848 Environment &Env;
851 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) {
852 TransferVisitor(StmtToEnv, Env).Visit(&S);
855 } // namespace dataflow
856 } // namespace clang