1 //===-- Transfer.cpp --------------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file defines transfer functions that evaluate program statements and 10 // update an environment accordingly. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "clang/Analysis/FlowSensitive/Transfer.h" 15 #include "clang/AST/Decl.h" 16 #include "clang/AST/DeclBase.h" 17 #include "clang/AST/DeclCXX.h" 18 #include "clang/AST/Expr.h" 19 #include "clang/AST/ExprCXX.h" 20 #include "clang/AST/OperationKinds.h" 21 #include "clang/AST/Stmt.h" 22 #include "clang/AST/StmtVisitor.h" 23 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h" 24 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 25 #include "clang/Analysis/FlowSensitive/NoopAnalysis.h" 26 #include "clang/Analysis/FlowSensitive/RecordOps.h" 27 #include "clang/Analysis/FlowSensitive/Value.h" 28 #include "clang/Basic/Builtins.h" 29 #include "clang/Basic/OperatorKinds.h" 30 #include "llvm/Support/Casting.h" 31 #include "llvm/Support/Debug.h" 32 #include <assert.h> 33 #include <cassert> 34 35 #define DEBUG_TYPE "dataflow" 36 37 namespace clang { 38 namespace dataflow { 39 40 const Environment *StmtToEnvMap::getEnvironment(const Stmt &S) const { 41 auto BlockIt = CFCtx.getStmtToBlock().find(&ignoreCFGOmittedNodes(S)); 42 assert(BlockIt != CFCtx.getStmtToBlock().end()); 43 if (!CFCtx.isBlockReachable(*BlockIt->getSecond())) 44 return nullptr; 45 if (BlockIt->getSecond()->getBlockID() == CurBlockID) 46 return &CurState.Env; 47 const auto &State = BlockToState[BlockIt->getSecond()->getBlockID()]; 48 if (!(State)) 49 return nullptr; 50 return &State->Env; 51 } 52 53 static BoolValue &evaluateBooleanEquality(const Expr &LHS, const Expr &RHS, 54 Environment &Env) { 55 Value *LHSValue = Env.getValue(LHS); 56 Value *RHSValue = Env.getValue(RHS); 57 58 if (LHSValue == RHSValue) 59 return Env.getBoolLiteralValue(true); 60 61 if (auto *LHSBool = dyn_cast_or_null<BoolValue>(LHSValue)) 62 if (auto *RHSBool = dyn_cast_or_null<BoolValue>(RHSValue)) 63 return Env.makeIff(*LHSBool, *RHSBool); 64 65 return Env.makeAtomicBoolValue(); 66 } 67 68 static BoolValue &unpackValue(BoolValue &V, Environment &Env) { 69 if (auto *Top = llvm::dyn_cast<TopBoolValue>(&V)) { 70 auto &A = Env.getDataflowAnalysisContext().arena(); 71 return A.makeBoolValue(A.makeAtomRef(Top->getAtom())); 72 } 73 return V; 74 } 75 76 // Unpacks the value (if any) associated with `E` and updates `E` to the new 77 // value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion, 78 // by skipping past the reference. 79 static Value *maybeUnpackLValueExpr(const Expr &E, Environment &Env) { 80 auto *Loc = Env.getStorageLocation(E); 81 if (Loc == nullptr) 82 return nullptr; 83 auto *Val = Env.getValue(*Loc); 84 85 auto *B = dyn_cast_or_null<BoolValue>(Val); 86 if (B == nullptr) 87 return Val; 88 89 auto &UnpackedVal = unpackValue(*B, Env); 90 if (&UnpackedVal == Val) 91 return Val; 92 Env.setValue(*Loc, UnpackedVal); 93 return &UnpackedVal; 94 } 95 96 static void propagateValue(const Expr &From, const Expr &To, Environment &Env) { 97 if (auto *Val = Env.getValue(From)) 98 Env.setValue(To, *Val); 99 } 100 101 static void propagateStorageLocation(const Expr &From, const Expr &To, 102 Environment &Env) { 103 if (auto *Loc = Env.getStorageLocation(From)) 104 Env.setStorageLocation(To, *Loc); 105 } 106 107 // Propagates the value or storage location of `From` to `To` in cases where 108 // `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff 109 // `From` is a glvalue. 110 static void propagateValueOrStorageLocation(const Expr &From, const Expr &To, 111 Environment &Env) { 112 assert(From.isGLValue() == To.isGLValue()); 113 if (From.isGLValue()) 114 propagateStorageLocation(From, To, Env); 115 else 116 propagateValue(From, To, Env); 117 } 118 119 namespace { 120 121 class TransferVisitor : public ConstStmtVisitor<TransferVisitor> { 122 public: 123 TransferVisitor(const StmtToEnvMap &StmtToEnv, Environment &Env) 124 : StmtToEnv(StmtToEnv), Env(Env) {} 125 126 void VisitBinaryOperator(const BinaryOperator *S) { 127 const Expr *LHS = S->getLHS(); 128 assert(LHS != nullptr); 129 130 const Expr *RHS = S->getRHS(); 131 assert(RHS != nullptr); 132 133 switch (S->getOpcode()) { 134 case BO_Assign: { 135 auto *LHSLoc = Env.getStorageLocation(*LHS); 136 if (LHSLoc == nullptr) 137 break; 138 139 auto *RHSVal = Env.getValue(*RHS); 140 if (RHSVal == nullptr) 141 break; 142 143 // Assign a value to the storage location of the left-hand side. 144 Env.setValue(*LHSLoc, *RHSVal); 145 146 // Assign a storage location for the whole expression. 147 Env.setStorageLocation(*S, *LHSLoc); 148 break; 149 } 150 case BO_LAnd: 151 case BO_LOr: { 152 BoolValue &LHSVal = getLogicOperatorSubExprValue(*LHS); 153 BoolValue &RHSVal = getLogicOperatorSubExprValue(*RHS); 154 155 if (S->getOpcode() == BO_LAnd) 156 Env.setValue(*S, Env.makeAnd(LHSVal, RHSVal)); 157 else 158 Env.setValue(*S, Env.makeOr(LHSVal, RHSVal)); 159 break; 160 } 161 case BO_NE: 162 case BO_EQ: { 163 auto &LHSEqRHSValue = evaluateBooleanEquality(*LHS, *RHS, Env); 164 Env.setValue(*S, S->getOpcode() == BO_EQ ? LHSEqRHSValue 165 : Env.makeNot(LHSEqRHSValue)); 166 break; 167 } 168 case BO_Comma: { 169 propagateValueOrStorageLocation(*RHS, *S, Env); 170 break; 171 } 172 default: 173 break; 174 } 175 } 176 177 void VisitDeclRefExpr(const DeclRefExpr *S) { 178 const ValueDecl *VD = S->getDecl(); 179 assert(VD != nullptr); 180 181 // Some `DeclRefExpr`s aren't glvalues, so we can't associate them with a 182 // `StorageLocation`, and there's also no sensible `Value` that we can 183 // assign to them. Examples: 184 // - Non-static member variables 185 // - Non static member functions 186 // Note: Member operators are an exception to this, but apparently only 187 // if the `DeclRefExpr` is used within the callee of a 188 // `CXXOperatorCallExpr`. In other cases, for example when applying the 189 // address-of operator, the `DeclRefExpr` is a prvalue. 190 if (!S->isGLValue()) 191 return; 192 193 auto *DeclLoc = Env.getStorageLocation(*VD); 194 if (DeclLoc == nullptr) 195 return; 196 197 Env.setStorageLocation(*S, *DeclLoc); 198 } 199 200 void VisitDeclStmt(const DeclStmt *S) { 201 // Group decls are converted into single decls in the CFG so the cast below 202 // is safe. 203 const auto &D = *cast<VarDecl>(S->getSingleDecl()); 204 205 ProcessVarDecl(D); 206 } 207 208 void ProcessVarDecl(const VarDecl &D) { 209 // Static local vars are already initialized in `Environment`. 210 if (D.hasGlobalStorage()) 211 return; 212 213 // If this is the holding variable for a `BindingDecl`, we may already 214 // have a storage location set up -- so check. (See also explanation below 215 // where we process the `BindingDecl`.) 216 if (D.getType()->isReferenceType() && Env.getStorageLocation(D) != nullptr) 217 return; 218 219 assert(Env.getStorageLocation(D) == nullptr); 220 221 Env.setStorageLocation(D, Env.createObject(D)); 222 223 // `DecompositionDecl` must be handled after we've interpreted the loc 224 // itself, because the binding expression refers back to the 225 // `DecompositionDecl` (even though it has no written name). 226 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) { 227 // If VarDecl is a DecompositionDecl, evaluate each of its bindings. This 228 // needs to be evaluated after initializing the values in the storage for 229 // VarDecl, as the bindings refer to them. 230 // FIXME: Add support for ArraySubscriptExpr. 231 // FIXME: Consider adding AST nodes used in BindingDecls to the CFG. 232 for (const auto *B : Decomp->bindings()) { 233 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) { 234 auto *DE = dyn_cast_or_null<DeclRefExpr>(ME->getBase()); 235 if (DE == nullptr) 236 continue; 237 238 // ME and its base haven't been visited because they aren't included 239 // in the statements of the CFG basic block. 240 VisitDeclRefExpr(DE); 241 VisitMemberExpr(ME); 242 243 if (auto *Loc = Env.getStorageLocation(*ME)) 244 Env.setStorageLocation(*B, *Loc); 245 } else if (auto *VD = B->getHoldingVar()) { 246 // Holding vars are used to back the `BindingDecl`s of tuple-like 247 // types. The holding var declarations appear after the 248 // `DecompositionDecl`, so we have to explicitly process them here 249 // to know their storage location. They will be processed a second 250 // time when we visit their `VarDecl`s, so we have code that protects 251 // against this above. 252 ProcessVarDecl(*VD); 253 auto *VDLoc = Env.getStorageLocation(*VD); 254 assert(VDLoc != nullptr); 255 Env.setStorageLocation(*B, *VDLoc); 256 } 257 } 258 } 259 } 260 261 void VisitImplicitCastExpr(const ImplicitCastExpr *S) { 262 const Expr *SubExpr = S->getSubExpr(); 263 assert(SubExpr != nullptr); 264 265 switch (S->getCastKind()) { 266 case CK_IntegralToBoolean: { 267 // This cast creates a new, boolean value from the integral value. We 268 // model that with a fresh value in the environment, unless it's already a 269 // boolean. 270 if (auto *SubExprVal = 271 dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr))) 272 Env.setValue(*S, *SubExprVal); 273 else 274 // FIXME: If integer modeling is added, then update this code to create 275 // the boolean based on the integer model. 276 Env.setValue(*S, Env.makeAtomicBoolValue()); 277 break; 278 } 279 280 case CK_LValueToRValue: { 281 // When an L-value is used as an R-value, it may result in sharing, so we 282 // need to unpack any nested `Top`s. 283 auto *SubExprVal = maybeUnpackLValueExpr(*SubExpr, Env); 284 if (SubExprVal == nullptr) 285 break; 286 287 Env.setValue(*S, *SubExprVal); 288 break; 289 } 290 291 case CK_IntegralCast: 292 // FIXME: This cast creates a new integral value from the 293 // subexpression. But, because we don't model integers, we don't 294 // distinguish between this new value and the underlying one. If integer 295 // modeling is added, then update this code to create a fresh location and 296 // value. 297 case CK_UncheckedDerivedToBase: 298 case CK_ConstructorConversion: 299 case CK_UserDefinedConversion: 300 // FIXME: Add tests that excercise CK_UncheckedDerivedToBase, 301 // CK_ConstructorConversion, and CK_UserDefinedConversion. 302 case CK_NoOp: { 303 // FIXME: Consider making `Environment::getStorageLocation` skip noop 304 // expressions (this and other similar expressions in the file) instead 305 // of assigning them storage locations. 306 propagateValueOrStorageLocation(*SubExpr, *S, Env); 307 break; 308 } 309 case CK_NullToPointer: { 310 auto &NullPointerVal = 311 Env.getOrCreateNullPointerValue(S->getType()->getPointeeType()); 312 Env.setValue(*S, NullPointerVal); 313 break; 314 } 315 case CK_NullToMemberPointer: 316 // FIXME: Implement pointers to members. For now, don't associate a value 317 // with this expression. 318 break; 319 case CK_FunctionToPointerDecay: { 320 StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr); 321 if (PointeeLoc == nullptr) 322 break; 323 324 Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc)); 325 break; 326 } 327 case CK_BuiltinFnToFnPtr: 328 // Despite its name, the result type of `BuiltinFnToFnPtr` is a function, 329 // not a function pointer. In addition, builtin functions can only be 330 // called directly; it is not legal to take their address. We therefore 331 // don't need to create a value or storage location for them. 332 break; 333 default: 334 break; 335 } 336 } 337 338 void VisitUnaryOperator(const UnaryOperator *S) { 339 const Expr *SubExpr = S->getSubExpr(); 340 assert(SubExpr != nullptr); 341 342 switch (S->getOpcode()) { 343 case UO_Deref: { 344 const auto *SubExprVal = Env.get<PointerValue>(*SubExpr); 345 if (SubExprVal == nullptr) 346 break; 347 348 Env.setStorageLocation(*S, SubExprVal->getPointeeLoc()); 349 break; 350 } 351 case UO_AddrOf: { 352 // FIXME: Model pointers to members. 353 if (S->getType()->isMemberPointerType()) 354 break; 355 356 if (StorageLocation *PointeeLoc = Env.getStorageLocation(*SubExpr)) 357 Env.setValue(*S, Env.create<PointerValue>(*PointeeLoc)); 358 break; 359 } 360 case UO_LNot: { 361 auto *SubExprVal = dyn_cast_or_null<BoolValue>(Env.getValue(*SubExpr)); 362 if (SubExprVal == nullptr) 363 break; 364 365 Env.setValue(*S, Env.makeNot(*SubExprVal)); 366 break; 367 } 368 default: 369 break; 370 } 371 } 372 373 void VisitCXXThisExpr(const CXXThisExpr *S) { 374 auto *ThisPointeeLoc = Env.getThisPointeeStorageLocation(); 375 if (ThisPointeeLoc == nullptr) 376 // Unions are not supported yet, and will not have a location for the 377 // `this` expression's pointee. 378 return; 379 380 Env.setValue(*S, Env.create<PointerValue>(*ThisPointeeLoc)); 381 } 382 383 void VisitCXXNewExpr(const CXXNewExpr *S) { 384 if (Value *Val = Env.createValue(S->getType())) 385 Env.setValue(*S, *Val); 386 } 387 388 void VisitCXXDeleteExpr(const CXXDeleteExpr *S) { 389 // Empty method. 390 // We consciously don't do anything on deletes. Diagnosing double deletes 391 // (for example) should be done by a specific analysis, not by the 392 // framework. 393 } 394 395 void VisitReturnStmt(const ReturnStmt *S) { 396 if (!Env.getDataflowAnalysisContext().getOptions().ContextSensitiveOpts) 397 return; 398 399 auto *Ret = S->getRetValue(); 400 if (Ret == nullptr) 401 return; 402 403 if (Ret->isPRValue()) { 404 auto *Val = Env.getValue(*Ret); 405 if (Val == nullptr) 406 return; 407 408 // FIXME: Model NRVO. 409 Env.setReturnValue(Val); 410 } else { 411 auto *Loc = Env.getStorageLocation(*Ret); 412 if (Loc == nullptr) 413 return; 414 415 // FIXME: Model NRVO. 416 Env.setReturnStorageLocation(Loc); 417 } 418 } 419 420 void VisitMemberExpr(const MemberExpr *S) { 421 ValueDecl *Member = S->getMemberDecl(); 422 assert(Member != nullptr); 423 424 // FIXME: Consider assigning pointer values to function member expressions. 425 if (Member->isFunctionOrFunctionTemplate()) 426 return; 427 428 // FIXME: if/when we add support for modeling enums, use that support here. 429 if (isa<EnumConstantDecl>(Member)) 430 return; 431 432 if (auto *D = dyn_cast<VarDecl>(Member)) { 433 if (D->hasGlobalStorage()) { 434 auto *VarDeclLoc = Env.getStorageLocation(*D); 435 if (VarDeclLoc == nullptr) 436 return; 437 438 Env.setStorageLocation(*S, *VarDeclLoc); 439 return; 440 } 441 } 442 443 RecordStorageLocation *BaseLoc = getBaseObjectLocation(*S, Env); 444 if (BaseLoc == nullptr) 445 return; 446 447 auto *MemberLoc = BaseLoc->getChild(*Member); 448 if (MemberLoc == nullptr) 449 return; 450 Env.setStorageLocation(*S, *MemberLoc); 451 } 452 453 void VisitCXXDefaultInitExpr(const CXXDefaultInitExpr *S) { 454 const Expr *InitExpr = S->getExpr(); 455 assert(InitExpr != nullptr); 456 propagateValueOrStorageLocation(*InitExpr, *S, Env); 457 } 458 459 void VisitCXXConstructExpr(const CXXConstructExpr *S) { 460 const CXXConstructorDecl *ConstructorDecl = S->getConstructor(); 461 assert(ConstructorDecl != nullptr); 462 463 if (ConstructorDecl->isCopyOrMoveConstructor()) { 464 // It is permissible for a copy/move constructor to have additional 465 // parameters as long as they have default arguments defined for them. 466 assert(S->getNumArgs() != 0); 467 468 const Expr *Arg = S->getArg(0); 469 assert(Arg != nullptr); 470 471 auto *ArgLoc = Env.get<RecordStorageLocation>(*Arg); 472 if (ArgLoc == nullptr) 473 return; 474 475 if (S->isElidable()) { 476 if (Value *Val = Env.getValue(*ArgLoc)) 477 Env.setValue(*S, *Val); 478 } else { 479 auto &Val = *cast<RecordValue>(Env.createValue(S->getType())); 480 Env.setValue(*S, Val); 481 copyRecord(*ArgLoc, Val.getLoc(), Env); 482 } 483 return; 484 } 485 486 // `CXXConstructExpr` can have array type if default-initializing an array 487 // of records, and we currently can't create values for arrays. So check if 488 // we've got a record type. 489 if (S->getType()->isRecordType()) { 490 auto &InitialVal = *cast<RecordValue>(Env.createValue(S->getType())); 491 Env.setValue(*S, InitialVal); 492 } 493 494 transferInlineCall(S, ConstructorDecl); 495 } 496 497 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *S) { 498 if (S->getOperator() == OO_Equal) { 499 assert(S->getNumArgs() == 2); 500 501 const Expr *Arg0 = S->getArg(0); 502 assert(Arg0 != nullptr); 503 504 const Expr *Arg1 = S->getArg(1); 505 assert(Arg1 != nullptr); 506 507 // Evaluate only copy and move assignment operators. 508 const auto *Method = 509 dyn_cast_or_null<CXXMethodDecl>(S->getDirectCallee()); 510 if (!Method) 511 return; 512 if (!Method->isCopyAssignmentOperator() && 513 !Method->isMoveAssignmentOperator()) 514 return; 515 516 RecordStorageLocation *LocSrc = nullptr; 517 if (Arg1->isPRValue()) { 518 if (auto *Val = Env.get<RecordValue>(*Arg1)) 519 LocSrc = &Val->getLoc(); 520 } else { 521 LocSrc = Env.get<RecordStorageLocation>(*Arg1); 522 } 523 auto *LocDst = Env.get<RecordStorageLocation>(*Arg0); 524 525 if (LocSrc == nullptr || LocDst == nullptr) 526 return; 527 528 // The assignment operators are different from the type of the destination 529 // in this model (i.e. in one of their base classes). This must be very 530 // rare and we just bail. 531 if (Method->getFunctionObjectParameterType() 532 .getCanonicalType() 533 .getUnqualifiedType() != 534 LocDst->getType().getCanonicalType().getUnqualifiedType()) 535 return; 536 537 copyRecord(*LocSrc, *LocDst, Env); 538 Env.setStorageLocation(*S, *LocDst); 539 } 540 } 541 542 void VisitCXXFunctionalCastExpr(const CXXFunctionalCastExpr *S) { 543 if (S->getCastKind() == CK_ConstructorConversion) { 544 const Expr *SubExpr = S->getSubExpr(); 545 assert(SubExpr != nullptr); 546 547 propagateValue(*SubExpr, *S, Env); 548 } 549 } 550 551 void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) { 552 if (Value *Val = Env.createValue(S->getType())) 553 Env.setValue(*S, *Val); 554 } 555 556 void VisitCallExpr(const CallExpr *S) { 557 // Of clang's builtins, only `__builtin_expect` is handled explicitly, since 558 // others (like trap, debugtrap, and unreachable) are handled by CFG 559 // construction. 560 if (S->isCallToStdMove()) { 561 assert(S->getNumArgs() == 1); 562 563 const Expr *Arg = S->getArg(0); 564 assert(Arg != nullptr); 565 566 auto *ArgLoc = Env.getStorageLocation(*Arg); 567 if (ArgLoc == nullptr) 568 return; 569 570 Env.setStorageLocation(*S, *ArgLoc); 571 } else if (S->getDirectCallee() != nullptr && 572 S->getDirectCallee()->getBuiltinID() == 573 Builtin::BI__builtin_expect) { 574 assert(S->getNumArgs() > 0); 575 assert(S->getArg(0) != nullptr); 576 auto *ArgVal = Env.getValue(*S->getArg(0)); 577 if (ArgVal == nullptr) 578 return; 579 Env.setValue(*S, *ArgVal); 580 } else if (const FunctionDecl *F = S->getDirectCallee()) { 581 transferInlineCall(S, F); 582 583 // If this call produces a prvalue of record type, make sure that we have 584 // a `RecordValue` for it. This is required so that 585 // `Environment::getResultObjectLocation()` is able to return a location 586 // for this `CallExpr`. 587 if (S->getType()->isRecordType() && S->isPRValue()) 588 if (Env.getValue(*S) == nullptr) 589 refreshRecordValue(*S, Env); 590 } 591 } 592 593 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) { 594 const Expr *SubExpr = S->getSubExpr(); 595 assert(SubExpr != nullptr); 596 597 Value *SubExprVal = Env.getValue(*SubExpr); 598 if (SubExprVal == nullptr) 599 return; 600 601 if (RecordValue *RecordVal = dyn_cast<RecordValue>(SubExprVal)) { 602 Env.setStorageLocation(*S, RecordVal->getLoc()); 603 return; 604 } 605 606 StorageLocation &Loc = Env.createStorageLocation(*S); 607 Env.setValue(Loc, *SubExprVal); 608 Env.setStorageLocation(*S, Loc); 609 } 610 611 void VisitCXXBindTemporaryExpr(const CXXBindTemporaryExpr *S) { 612 const Expr *SubExpr = S->getSubExpr(); 613 assert(SubExpr != nullptr); 614 615 propagateValue(*SubExpr, *S, Env); 616 } 617 618 void VisitCXXStaticCastExpr(const CXXStaticCastExpr *S) { 619 if (S->getCastKind() == CK_NoOp) { 620 const Expr *SubExpr = S->getSubExpr(); 621 assert(SubExpr != nullptr); 622 623 propagateValueOrStorageLocation(*SubExpr, *S, Env); 624 } 625 } 626 627 void VisitConditionalOperator(const ConditionalOperator *S) { 628 // FIXME: Revisit this once flow conditions are added to the framework. For 629 // `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow 630 // condition. 631 // When we do this, we will need to retrieve the values of the operands from 632 // the environments for the basic blocks they are computed in, in a similar 633 // way to how this is done for short-circuited logical operators in 634 // `getLogicOperatorSubExprValue()`. 635 if (S->isGLValue()) 636 Env.setStorageLocation(*S, Env.createObject(S->getType())); 637 else if (Value *Val = Env.createValue(S->getType())) 638 Env.setValue(*S, *Val); 639 } 640 641 void VisitInitListExpr(const InitListExpr *S) { 642 QualType Type = S->getType(); 643 644 if (!Type->isStructureOrClassType()) { 645 if (auto *Val = Env.createValue(Type)) 646 Env.setValue(*S, *Val); 647 648 return; 649 } 650 651 // In case the initializer list is transparent, we just need to propagate 652 // the value that it contains. 653 if (S->isSemanticForm() && S->isTransparent()) { 654 propagateValue(*S->getInit(0), *S, Env); 655 return; 656 } 657 658 llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs; 659 660 // This only contains the direct fields for the given type. 661 std::vector<FieldDecl *> FieldsForInit = 662 getFieldsForInitListExpr(Type->getAsRecordDecl()); 663 664 // `S->inits()` contains all the initializer epressions, including the 665 // ones for direct base classes. 666 auto Inits = S->inits(); 667 size_t InitIdx = 0; 668 669 // Initialize base classes. 670 if (auto* R = S->getType()->getAsCXXRecordDecl()) { 671 assert(FieldsForInit.size() + R->getNumBases() == Inits.size()); 672 for ([[maybe_unused]] const CXXBaseSpecifier &Base : R->bases()) { 673 assert(InitIdx < Inits.size()); 674 auto Init = Inits[InitIdx++]; 675 assert(Base.getType().getCanonicalType() == 676 Init->getType().getCanonicalType()); 677 auto *BaseVal = Env.get<RecordValue>(*Init); 678 if (!BaseVal) 679 BaseVal = cast<RecordValue>(Env.createValue(Init->getType())); 680 // Take ownership of the fields of the `RecordValue` for the base class 681 // and incorporate them into the "flattened" set of fields for the 682 // derived class. 683 auto Children = BaseVal->getLoc().children(); 684 FieldLocs.insert(Children.begin(), Children.end()); 685 } 686 } 687 688 assert(FieldsForInit.size() == Inits.size() - InitIdx); 689 for (auto Field : FieldsForInit) { 690 assert(InitIdx < Inits.size()); 691 auto Init = Inits[InitIdx++]; 692 assert( 693 // The types are same, or 694 Field->getType().getCanonicalType().getUnqualifiedType() == 695 Init->getType().getCanonicalType().getUnqualifiedType() || 696 // The field's type is T&, and initializer is T 697 (Field->getType()->isReferenceType() && 698 Field->getType().getCanonicalType()->getPointeeType() == 699 Init->getType().getCanonicalType())); 700 auto& Loc = Env.createObject(Field->getType(), Init); 701 FieldLocs.insert({Field, &Loc}); 702 } 703 704 // Check that we satisfy the invariant that a `RecordStorageLoation` 705 // contains exactly the set of modeled fields for that type. 706 // `ModeledFields` includes fields from all the bases, but only the 707 // modeled ones. However, if a class type is initialized with an 708 // `InitListExpr`, all fields in the class, including those from base 709 // classes, are included in the set of modeled fields. The code above 710 // should therefore populate exactly the modeled fields. 711 assert(containsSameFields( 712 Env.getDataflowAnalysisContext().getModeledFields(Type), FieldLocs)); 713 714 RecordStorageLocation::SyntheticFieldMap SyntheticFieldLocs; 715 for (const auto &Entry : 716 Env.getDataflowAnalysisContext().getSyntheticFields(Type)) { 717 SyntheticFieldLocs.insert( 718 {Entry.getKey(), &Env.createObject(Entry.getValue())}); 719 } 720 721 auto &Loc = Env.getDataflowAnalysisContext().createRecordStorageLocation( 722 Type, std::move(FieldLocs), std::move(SyntheticFieldLocs)); 723 RecordValue &RecordVal = Env.create<RecordValue>(Loc); 724 725 Env.setValue(Loc, RecordVal); 726 727 Env.setValue(*S, RecordVal); 728 729 // FIXME: Implement array initialization. 730 } 731 732 void VisitCXXBoolLiteralExpr(const CXXBoolLiteralExpr *S) { 733 Env.setValue(*S, Env.getBoolLiteralValue(S->getValue())); 734 } 735 736 void VisitIntegerLiteral(const IntegerLiteral *S) { 737 Env.setValue(*S, Env.getIntLiteralValue(S->getValue())); 738 } 739 740 void VisitParenExpr(const ParenExpr *S) { 741 // The CFG does not contain `ParenExpr` as top-level statements in basic 742 // blocks, however manual traversal to sub-expressions may encounter them. 743 // Redirect to the sub-expression. 744 auto *SubExpr = S->getSubExpr(); 745 assert(SubExpr != nullptr); 746 Visit(SubExpr); 747 } 748 749 void VisitExprWithCleanups(const ExprWithCleanups *S) { 750 // The CFG does not contain `ExprWithCleanups` as top-level statements in 751 // basic blocks, however manual traversal to sub-expressions may encounter 752 // them. Redirect to the sub-expression. 753 auto *SubExpr = S->getSubExpr(); 754 assert(SubExpr != nullptr); 755 Visit(SubExpr); 756 } 757 758 private: 759 /// Returns the value for the sub-expression `SubExpr` of a logic operator. 760 BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) { 761 // `SubExpr` and its parent logic operator might be part of different basic 762 // blocks. We try to access the value that is assigned to `SubExpr` in the 763 // corresponding environment. 764 if (const Environment *SubExprEnv = StmtToEnv.getEnvironment(SubExpr)) 765 if (auto *Val = 766 dyn_cast_or_null<BoolValue>(SubExprEnv->getValue(SubExpr))) 767 return *Val; 768 769 // The sub-expression may lie within a basic block that isn't reachable, 770 // even if we need it to evaluate the current (reachable) expression 771 // (see https://discourse.llvm.org/t/70775). In this case, visit `SubExpr` 772 // within the current environment and then try to get the value that gets 773 // assigned to it. 774 if (Env.getValue(SubExpr) == nullptr) 775 Visit(&SubExpr); 776 if (auto *Val = dyn_cast_or_null<BoolValue>(Env.getValue(SubExpr))) 777 return *Val; 778 779 // If the value of `SubExpr` is still unknown, we create a fresh symbolic 780 // boolean value for it. 781 return Env.makeAtomicBoolValue(); 782 } 783 784 // If context sensitivity is enabled, try to analyze the body of the callee 785 // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`. 786 template <typename E> 787 void transferInlineCall(const E *S, const FunctionDecl *F) { 788 const auto &Options = Env.getDataflowAnalysisContext().getOptions(); 789 if (!(Options.ContextSensitiveOpts && 790 Env.canDescend(Options.ContextSensitiveOpts->Depth, F))) 791 return; 792 793 const ControlFlowContext *CFCtx = 794 Env.getDataflowAnalysisContext().getControlFlowContext(F); 795 if (!CFCtx) 796 return; 797 798 // FIXME: We don't support context-sensitive analysis of recursion, so 799 // we should return early here if `F` is the same as the `FunctionDecl` 800 // holding `S` itself. 801 802 auto ExitBlock = CFCtx->getCFG().getExit().getBlockID(); 803 804 auto CalleeEnv = Env.pushCall(S); 805 806 // FIXME: Use the same analysis as the caller for the callee. Note, 807 // though, that doing so would require support for changing the analysis's 808 // ASTContext. 809 auto Analysis = NoopAnalysis(CFCtx->getDecl().getASTContext(), 810 DataflowAnalysisOptions{Options}); 811 812 auto BlockToOutputState = 813 dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv); 814 assert(BlockToOutputState); 815 assert(ExitBlock < BlockToOutputState->size()); 816 817 auto &ExitState = (*BlockToOutputState)[ExitBlock]; 818 assert(ExitState); 819 820 Env.popCall(S, ExitState->Env); 821 } 822 823 const StmtToEnvMap &StmtToEnv; 824 Environment &Env; 825 }; 826 827 } // namespace 828 829 void transfer(const StmtToEnvMap &StmtToEnv, const Stmt &S, Environment &Env) { 830 TransferVisitor(StmtToEnv, Env).Visit(&S); 831 } 832 833 } // namespace dataflow 834 } // namespace clang 835