1 //===-- DataflowEnvironment.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 an Environment class that is used by dataflow analyses 10 // that run over Control-Flow Graphs (CFGs) to keep track of the state of the 11 // program at given program points. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h" 16 #include "clang/AST/Decl.h" 17 #include "clang/AST/DeclCXX.h" 18 #include "clang/AST/RecursiveASTVisitor.h" 19 #include "clang/AST/Type.h" 20 #include "clang/Analysis/FlowSensitive/ASTOps.h" 21 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 22 #include "clang/Analysis/FlowSensitive/Value.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/DenseSet.h" 25 #include "llvm/ADT/MapVector.h" 26 #include "llvm/ADT/STLExtras.h" 27 #include "llvm/Support/ErrorHandling.h" 28 #include <cassert> 29 #include <utility> 30 31 #define DEBUG_TYPE "dataflow" 32 33 namespace clang { 34 namespace dataflow { 35 36 // FIXME: convert these to parameters of the analysis or environment. Current 37 // settings have been experimentaly validated, but only for a particular 38 // analysis. 39 static constexpr int MaxCompositeValueDepth = 3; 40 static constexpr int MaxCompositeValueSize = 1000; 41 42 /// Returns a map consisting of key-value entries that are present in both maps. 43 static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc( 44 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1, 45 const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) { 46 llvm::DenseMap<const ValueDecl *, StorageLocation *> Result; 47 for (auto &Entry : DeclToLoc1) { 48 auto It = DeclToLoc2.find(Entry.first); 49 if (It != DeclToLoc2.end() && Entry.second == It->second) 50 Result.insert({Entry.first, Entry.second}); 51 } 52 return Result; 53 } 54 55 // Performs a join on either `ExprToLoc` or `ExprToVal`. 56 // The maps must be consistent in the sense that any entries for the same 57 // expression must map to the same location / value. This is the case if we are 58 // performing a join for control flow within a full-expression (which is the 59 // only case when this function should be used). 60 template <typename MapT> MapT joinExprMaps(const MapT &Map1, const MapT &Map2) { 61 MapT Result = Map1; 62 63 for (const auto &Entry : Map2) { 64 [[maybe_unused]] auto [It, Inserted] = Result.insert(Entry); 65 // If there was an existing entry, its value should be the same as for the 66 // entry we were trying to insert. 67 assert(It->second == Entry.second); 68 } 69 70 return Result; 71 } 72 73 // Whether to consider equivalent two values with an unknown relation. 74 // 75 // FIXME: this function is a hack enabling unsoundness to support 76 // convergence. Once we have widening support for the reference/pointer and 77 // struct built-in models, this should be unconditionally `false` (and inlined 78 // as such at its call sites). 79 static bool equateUnknownValues(Value::Kind K) { 80 switch (K) { 81 case Value::Kind::Integer: 82 case Value::Kind::Pointer: 83 case Value::Kind::Record: 84 return true; 85 default: 86 return false; 87 } 88 } 89 90 static bool compareDistinctValues(QualType Type, Value &Val1, 91 const Environment &Env1, Value &Val2, 92 const Environment &Env2, 93 Environment::ValueModel &Model) { 94 // Note: Potentially costly, but, for booleans, we could check whether both 95 // can be proven equivalent in their respective environments. 96 97 // FIXME: move the reference/pointers logic from `areEquivalentValues` to here 98 // and implement separate, join/widen specific handling for 99 // reference/pointers. 100 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) { 101 case ComparisonResult::Same: 102 return true; 103 case ComparisonResult::Different: 104 return false; 105 case ComparisonResult::Unknown: 106 return equateUnknownValues(Val1.getKind()); 107 } 108 llvm_unreachable("All cases covered in switch"); 109 } 110 111 /// Attempts to join distinct values `Val1` and `Val2` in `Env1` and `Env2`, 112 /// respectively, of the same type `Type`. Joining generally produces a single 113 /// value that (soundly) approximates the two inputs, although the actual 114 /// meaning depends on `Model`. 115 static Value *joinDistinctValues(QualType Type, Value &Val1, 116 const Environment &Env1, Value &Val2, 117 const Environment &Env2, 118 Environment &JoinedEnv, 119 Environment::ValueModel &Model) { 120 // Join distinct boolean values preserving information about the constraints 121 // in the respective path conditions. 122 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) { 123 // FIXME: Checking both values should be unnecessary, since they should have 124 // a consistent shape. However, right now we can end up with BoolValue's in 125 // integer-typed variables due to our incorrect handling of 126 // boolean-to-integer casts (we just propagate the BoolValue to the result 127 // of the cast). So, a join can encounter an integer in one branch but a 128 // bool in the other. 129 // For example: 130 // ``` 131 // std::optional<bool> o; 132 // int x; 133 // if (o.has_value()) 134 // x = o.value(); 135 // ``` 136 auto &Expr1 = cast<BoolValue>(Val1).formula(); 137 auto &Expr2 = cast<BoolValue>(Val2).formula(); 138 auto &A = JoinedEnv.arena(); 139 auto &JoinedVal = A.makeAtomRef(A.makeAtom()); 140 JoinedEnv.assume( 141 A.makeOr(A.makeAnd(A.makeAtomRef(Env1.getFlowConditionToken()), 142 A.makeEquals(JoinedVal, Expr1)), 143 A.makeAnd(A.makeAtomRef(Env2.getFlowConditionToken()), 144 A.makeEquals(JoinedVal, Expr2)))); 145 return &A.makeBoolValue(JoinedVal); 146 } 147 148 Value *JoinedVal = nullptr; 149 if (auto *RecordVal1 = dyn_cast<RecordValue>(&Val1)) { 150 auto *RecordVal2 = cast<RecordValue>(&Val2); 151 152 if (&RecordVal1->getLoc() == &RecordVal2->getLoc()) 153 // `RecordVal1` and `RecordVal2` may have different properties associated 154 // with them. Create a new `RecordValue` with the same location but 155 // without any properties so that we soundly approximate both values. If a 156 // particular analysis needs to join properties, it should do so in 157 // `DataflowAnalysis::join()`. 158 JoinedVal = &JoinedEnv.create<RecordValue>(RecordVal1->getLoc()); 159 else 160 // If the locations for the two records are different, need to create a 161 // completely new value. 162 JoinedVal = JoinedEnv.createValue(Type); 163 } else { 164 JoinedVal = JoinedEnv.createValue(Type); 165 } 166 167 if (JoinedVal) 168 Model.join(Type, Val1, Env1, Val2, Env2, *JoinedVal, JoinedEnv); 169 170 return JoinedVal; 171 } 172 173 static WidenResult widenDistinctValues(QualType Type, Value &Prev, 174 const Environment &PrevEnv, 175 Value &Current, Environment &CurrentEnv, 176 Environment::ValueModel &Model) { 177 // Boolean-model widening. 178 if (auto *PrevBool = dyn_cast<BoolValue>(&Prev)) { 179 if (isa<TopBoolValue>(Prev)) 180 // Safe to return `Prev` here, because Top is never dependent on the 181 // environment. 182 return {&Prev, LatticeEffect::Unchanged}; 183 184 // We may need to widen to Top, but before we do so, check whether both 185 // values are implied to be either true or false in the current environment. 186 // In that case, we can simply return a literal instead. 187 auto &CurBool = cast<BoolValue>(Current); 188 bool TruePrev = PrevEnv.proves(PrevBool->formula()); 189 bool TrueCur = CurrentEnv.proves(CurBool.formula()); 190 if (TruePrev && TrueCur) 191 return {&CurrentEnv.getBoolLiteralValue(true), LatticeEffect::Unchanged}; 192 if (!TruePrev && !TrueCur && 193 PrevEnv.proves(PrevEnv.arena().makeNot(PrevBool->formula())) && 194 CurrentEnv.proves(CurrentEnv.arena().makeNot(CurBool.formula()))) 195 return {&CurrentEnv.getBoolLiteralValue(false), LatticeEffect::Unchanged}; 196 197 return {&CurrentEnv.makeTopBoolValue(), LatticeEffect::Changed}; 198 } 199 200 // FIXME: Add other built-in model widening. 201 202 // Custom-model widening. 203 if (auto Result = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv)) 204 return *Result; 205 206 return {&Current, equateUnknownValues(Prev.getKind()) 207 ? LatticeEffect::Unchanged 208 : LatticeEffect::Changed}; 209 } 210 211 // Returns whether the values in `Map1` and `Map2` compare equal for those 212 // keys that `Map1` and `Map2` have in common. 213 template <typename Key> 214 bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1, 215 const llvm::MapVector<Key, Value *> &Map2, 216 const Environment &Env1, const Environment &Env2, 217 Environment::ValueModel &Model) { 218 for (auto &Entry : Map1) { 219 Key K = Entry.first; 220 assert(K != nullptr); 221 222 Value *Val = Entry.second; 223 assert(Val != nullptr); 224 225 auto It = Map2.find(K); 226 if (It == Map2.end()) 227 continue; 228 assert(It->second != nullptr); 229 230 if (!areEquivalentValues(*Val, *It->second) && 231 !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2, 232 Model)) 233 return false; 234 } 235 236 return true; 237 } 238 239 // Perform a join on two `LocToVal` maps. 240 static llvm::MapVector<const StorageLocation *, Value *> 241 joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal, 242 const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2, 243 const Environment &Env1, const Environment &Env2, 244 Environment &JoinedEnv, Environment::ValueModel &Model) { 245 llvm::MapVector<const StorageLocation *, Value *> Result; 246 for (auto &Entry : LocToVal) { 247 const StorageLocation *Loc = Entry.first; 248 assert(Loc != nullptr); 249 250 Value *Val = Entry.second; 251 assert(Val != nullptr); 252 253 auto It = LocToVal2.find(Loc); 254 if (It == LocToVal2.end()) 255 continue; 256 assert(It->second != nullptr); 257 258 if (areEquivalentValues(*Val, *It->second)) { 259 Result.insert({Loc, Val}); 260 continue; 261 } 262 263 if (Value *JoinedVal = joinDistinctValues( 264 Loc->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) { 265 Result.insert({Loc, JoinedVal}); 266 } 267 } 268 269 return Result; 270 } 271 272 // Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either 273 // `const StorageLocation *` or `const Expr *`. 274 template <typename Key> 275 llvm::MapVector<Key, Value *> 276 widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap, 277 const llvm::MapVector<Key, Value *> &PrevMap, 278 Environment &CurEnv, const Environment &PrevEnv, 279 Environment::ValueModel &Model, LatticeEffect &Effect) { 280 llvm::MapVector<Key, Value *> WidenedMap; 281 for (auto &Entry : CurMap) { 282 Key K = Entry.first; 283 assert(K != nullptr); 284 285 Value *Val = Entry.second; 286 assert(Val != nullptr); 287 288 auto PrevIt = PrevMap.find(K); 289 if (PrevIt == PrevMap.end()) 290 continue; 291 assert(PrevIt->second != nullptr); 292 293 if (areEquivalentValues(*Val, *PrevIt->second)) { 294 WidenedMap.insert({K, Val}); 295 continue; 296 } 297 298 auto [WidenedVal, ValEffect] = widenDistinctValues( 299 K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model); 300 WidenedMap.insert({K, WidenedVal}); 301 if (ValEffect == LatticeEffect::Changed) 302 Effect = LatticeEffect::Changed; 303 } 304 305 return WidenedMap; 306 } 307 308 namespace { 309 310 // Visitor that builds a map from record prvalues to result objects. 311 // This traverses the body of the function to be analyzed; for each result 312 // object that it encounters, it propagates the storage location of the result 313 // object to all record prvalues that can initialize it. 314 class ResultObjectVisitor : public RecursiveASTVisitor<ResultObjectVisitor> { 315 public: 316 // `ResultObjectMap` will be filled with a map from record prvalues to result 317 // object. If the function being analyzed returns a record by value, 318 // `LocForRecordReturnVal` is the location to which this record should be 319 // written; otherwise, it is null. 320 explicit ResultObjectVisitor( 321 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap, 322 RecordStorageLocation *LocForRecordReturnVal, 323 DataflowAnalysisContext &DACtx) 324 : ResultObjectMap(ResultObjectMap), 325 LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {} 326 327 bool shouldVisitImplicitCode() { return true; } 328 329 bool shouldVisitLambdaBody() const { return false; } 330 331 // Traverse all member and base initializers of `Ctor`. This function is not 332 // called by `RecursiveASTVisitor`; it should be called manually if we are 333 // analyzing a constructor. `ThisPointeeLoc` is the storage location that 334 // `this` points to. 335 void TraverseConstructorInits(const CXXConstructorDecl *Ctor, 336 RecordStorageLocation *ThisPointeeLoc) { 337 assert(ThisPointeeLoc != nullptr); 338 for (const CXXCtorInitializer *Init : Ctor->inits()) { 339 Expr *InitExpr = Init->getInit(); 340 if (FieldDecl *Field = Init->getMember(); 341 Field != nullptr && Field->getType()->isRecordType()) { 342 PropagateResultObject(InitExpr, cast<RecordStorageLocation>( 343 ThisPointeeLoc->getChild(*Field))); 344 } else if (Init->getBaseClass()) { 345 PropagateResultObject(InitExpr, ThisPointeeLoc); 346 } 347 348 // Ensure that any result objects within `InitExpr` (e.g. temporaries) 349 // are also propagated to the prvalues that initialize them. 350 TraverseStmt(InitExpr); 351 352 // If this is a `CXXDefaultInitExpr`, also propagate any result objects 353 // within the default expression. 354 if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(InitExpr)) 355 TraverseStmt(DefaultInit->getExpr()); 356 } 357 } 358 359 bool TraverseBindingDecl(BindingDecl *BD) { 360 // `RecursiveASTVisitor` doesn't traverse holding variables for 361 // `BindingDecl`s by itself, so we need to tell it to. 362 if (VarDecl *HoldingVar = BD->getHoldingVar()) 363 TraverseDecl(HoldingVar); 364 return RecursiveASTVisitor<ResultObjectVisitor>::TraverseBindingDecl(BD); 365 } 366 367 bool VisitVarDecl(VarDecl *VD) { 368 if (VD->getType()->isRecordType() && VD->hasInit()) 369 PropagateResultObject( 370 VD->getInit(), 371 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*VD))); 372 return true; 373 } 374 375 bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) { 376 if (MTE->getType()->isRecordType()) 377 PropagateResultObject( 378 MTE->getSubExpr(), 379 &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*MTE))); 380 return true; 381 } 382 383 bool VisitReturnStmt(ReturnStmt *Return) { 384 Expr *RetValue = Return->getRetValue(); 385 if (RetValue != nullptr && RetValue->getType()->isRecordType() && 386 RetValue->isPRValue()) 387 PropagateResultObject(RetValue, LocForRecordReturnVal); 388 return true; 389 } 390 391 bool VisitExpr(Expr *E) { 392 // Clang's AST can have record-type prvalues without a result object -- for 393 // example as full-expressions contained in a compound statement or as 394 // arguments of call expressions. We notice this if we get here and a 395 // storage location has not yet been associated with `E`. In this case, 396 // treat this as if it was a `MaterializeTemporaryExpr`. 397 if (E->isPRValue() && E->getType()->isRecordType() && 398 !ResultObjectMap.contains(E)) 399 PropagateResultObject( 400 E, &cast<RecordStorageLocation>(DACtx.getStableStorageLocation(*E))); 401 return true; 402 } 403 404 // Assigns `Loc` as the result object location of `E`, then propagates the 405 // location to all lower-level prvalues that initialize the same object as 406 // `E` (or one of its base classes or member variables). 407 void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) { 408 if (!E->isPRValue() || !E->getType()->isRecordType()) { 409 assert(false); 410 // Ensure we don't propagate the result object if we hit this in a 411 // release build. 412 return; 413 } 414 415 ResultObjectMap[E] = Loc; 416 417 // The following AST node kinds are "original initializers": They are the 418 // lowest-level AST node that initializes a given object, and nothing 419 // below them can initialize the same object (or part of it). 420 if (isa<CXXConstructExpr>(E) || isa<CallExpr>(E) || isa<LambdaExpr>(E) || 421 isa<CXXDefaultArgExpr>(E) || isa<CXXDefaultInitExpr>(E) || 422 isa<CXXStdInitializerListExpr>(E)) { 423 return; 424 } 425 if (auto *Op = dyn_cast<BinaryOperator>(E); 426 Op && Op->getOpcode() == BO_Cmp) { 427 // Builtin `<=>` returns a `std::strong_ordering` object. 428 return; 429 } 430 431 if (auto *InitList = dyn_cast<InitListExpr>(E)) { 432 if (!InitList->isSemanticForm()) 433 return; 434 if (InitList->isTransparent()) { 435 PropagateResultObject(InitList->getInit(0), Loc); 436 return; 437 } 438 439 RecordInitListHelper InitListHelper(InitList); 440 441 for (auto [Base, Init] : InitListHelper.base_inits()) { 442 assert(Base->getType().getCanonicalType() == 443 Init->getType().getCanonicalType()); 444 445 // Storage location for the base class is the same as that of the 446 // derived class because we "flatten" the object hierarchy and put all 447 // fields in `RecordStorageLocation` of the derived class. 448 PropagateResultObject(Init, Loc); 449 } 450 451 for (auto [Field, Init] : InitListHelper.field_inits()) { 452 // Fields of non-record type are handled in 453 // `TransferVisitor::VisitInitListExpr()`. 454 if (!Field->getType()->isRecordType()) 455 continue; 456 PropagateResultObject( 457 Init, cast<RecordStorageLocation>(Loc->getChild(*Field))); 458 } 459 return; 460 } 461 462 if (auto *Op = dyn_cast<BinaryOperator>(E); Op && Op->isCommaOp()) { 463 PropagateResultObject(Op->getRHS(), Loc); 464 return; 465 } 466 467 if (auto *Cond = dyn_cast<AbstractConditionalOperator>(E)) { 468 PropagateResultObject(Cond->getTrueExpr(), Loc); 469 PropagateResultObject(Cond->getFalseExpr(), Loc); 470 return; 471 } 472 473 if (auto *SE = dyn_cast<StmtExpr>(E)) { 474 PropagateResultObject(cast<Expr>(SE->getSubStmt()->body_back()), Loc); 475 return; 476 } 477 478 // All other expression nodes that propagate a record prvalue should have 479 // exactly one child. 480 SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end()); 481 LLVM_DEBUG({ 482 if (Children.size() != 1) 483 E->dump(); 484 }); 485 assert(Children.size() == 1); 486 for (Stmt *S : Children) 487 PropagateResultObject(cast<Expr>(S), Loc); 488 } 489 490 private: 491 llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap; 492 RecordStorageLocation *LocForRecordReturnVal; 493 DataflowAnalysisContext &DACtx; 494 }; 495 496 } // namespace 497 498 Environment::Environment(DataflowAnalysisContext &DACtx) 499 : DACtx(&DACtx), 500 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {} 501 502 Environment::Environment(DataflowAnalysisContext &DACtx, 503 const DeclContext &DeclCtx) 504 : Environment(DACtx) { 505 CallStack.push_back(&DeclCtx); 506 } 507 508 void Environment::initialize() { 509 const DeclContext *DeclCtx = getDeclCtx(); 510 if (DeclCtx == nullptr) 511 return; 512 513 const auto *FuncDecl = dyn_cast<FunctionDecl>(DeclCtx); 514 if (FuncDecl == nullptr) 515 return; 516 517 assert(FuncDecl->doesThisDeclarationHaveABody()); 518 519 initFieldsGlobalsAndFuncs(FuncDecl); 520 521 for (const auto *ParamDecl : FuncDecl->parameters()) { 522 assert(ParamDecl != nullptr); 523 setStorageLocation(*ParamDecl, createObject(*ParamDecl, nullptr)); 524 } 525 526 if (FuncDecl->getReturnType()->isRecordType()) 527 LocForRecordReturnVal = &cast<RecordStorageLocation>( 528 createStorageLocation(FuncDecl->getReturnType())); 529 530 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(DeclCtx)) { 531 auto *Parent = MethodDecl->getParent(); 532 assert(Parent != nullptr); 533 534 if (Parent->isLambda()) { 535 for (const auto &Capture : Parent->captures()) { 536 if (Capture.capturesVariable()) { 537 const auto *VarDecl = Capture.getCapturedVar(); 538 assert(VarDecl != nullptr); 539 setStorageLocation(*VarDecl, createObject(*VarDecl, nullptr)); 540 } else if (Capture.capturesThis()) { 541 const auto *SurroundingMethodDecl = 542 cast<CXXMethodDecl>(DeclCtx->getNonClosureAncestor()); 543 QualType ThisPointeeType = 544 SurroundingMethodDecl->getFunctionObjectParameterType(); 545 setThisPointeeStorageLocation( 546 cast<RecordStorageLocation>(createObject(ThisPointeeType))); 547 } 548 } 549 } else if (MethodDecl->isImplicitObjectMemberFunction()) { 550 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType(); 551 auto &ThisLoc = 552 cast<RecordStorageLocation>(createStorageLocation(ThisPointeeType)); 553 setThisPointeeStorageLocation(ThisLoc); 554 refreshRecordValue(ThisLoc, *this); 555 // Initialize fields of `*this` with values, but only if we're not 556 // analyzing a constructor; after all, it's the constructor's job to do 557 // this (and we want to be able to test that). 558 if (!isa<CXXConstructorDecl>(MethodDecl)) 559 initializeFieldsWithValues(ThisLoc); 560 } 561 } 562 563 // We do this below the handling of `CXXMethodDecl` above so that we can 564 // be sure that the storage location for `this` has been set. 565 ResultObjectMap = std::make_shared<PrValueToResultObject>( 566 buildResultObjectMap(DACtx, FuncDecl, getThisPointeeStorageLocation(), 567 LocForRecordReturnVal)); 568 } 569 570 // FIXME: Add support for resetting globals after function calls to enable 571 // the implementation of sound analyses. 572 void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) { 573 assert(FuncDecl->doesThisDeclarationHaveABody()); 574 575 ReferencedDecls Referenced = getReferencedDecls(*FuncDecl); 576 577 // These have to be added before the lines that follow to ensure that 578 // `create*` work correctly for structs. 579 DACtx->addModeledFields(Referenced.Fields); 580 581 for (const VarDecl *D : Referenced.Globals) { 582 if (getStorageLocation(*D) != nullptr) 583 continue; 584 585 // We don't run transfer functions on the initializers of global variables, 586 // so they won't be associated with a value or storage location. We 587 // therefore intentionally don't pass an initializer to `createObject()`; 588 // in particular, this ensures that `createObject()` will initialize the 589 // fields of record-type variables with values. 590 setStorageLocation(*D, createObject(*D, nullptr)); 591 } 592 593 for (const FunctionDecl *FD : Referenced.Functions) { 594 if (getStorageLocation(*FD) != nullptr) 595 continue; 596 auto &Loc = createStorageLocation(*FD); 597 setStorageLocation(*FD, Loc); 598 } 599 } 600 601 Environment Environment::fork() const { 602 Environment Copy(*this); 603 Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken); 604 return Copy; 605 } 606 607 bool Environment::canDescend(unsigned MaxDepth, 608 const DeclContext *Callee) const { 609 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee); 610 } 611 612 Environment Environment::pushCall(const CallExpr *Call) const { 613 Environment Env(*this); 614 615 if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) { 616 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) { 617 if (!isa<CXXThisExpr>(Arg)) 618 Env.ThisPointeeLoc = 619 cast<RecordStorageLocation>(getStorageLocation(*Arg)); 620 // Otherwise (when the argument is `this`), retain the current 621 // environment's `ThisPointeeLoc`. 622 } 623 } 624 625 if (Call->getType()->isRecordType() && Call->isPRValue()) 626 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(*Call); 627 628 Env.pushCallInternal(Call->getDirectCallee(), 629 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs())); 630 631 return Env; 632 } 633 634 Environment Environment::pushCall(const CXXConstructExpr *Call) const { 635 Environment Env(*this); 636 637 Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call); 638 Env.LocForRecordReturnVal = &Env.getResultObjectLocation(*Call); 639 640 Env.pushCallInternal(Call->getConstructor(), 641 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs())); 642 643 return Env; 644 } 645 646 void Environment::pushCallInternal(const FunctionDecl *FuncDecl, 647 ArrayRef<const Expr *> Args) { 648 // Canonicalize to the definition of the function. This ensures that we're 649 // putting arguments into the same `ParamVarDecl`s` that the callee will later 650 // be retrieving them from. 651 assert(FuncDecl->getDefinition() != nullptr); 652 FuncDecl = FuncDecl->getDefinition(); 653 654 CallStack.push_back(FuncDecl); 655 656 initFieldsGlobalsAndFuncs(FuncDecl); 657 658 const auto *ParamIt = FuncDecl->param_begin(); 659 660 // FIXME: Parameters don't always map to arguments 1:1; examples include 661 // overloaded operators implemented as member functions, and parameter packs. 662 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) { 663 assert(ParamIt != FuncDecl->param_end()); 664 const VarDecl *Param = *ParamIt; 665 setStorageLocation(*Param, createObject(*Param, Args[ArgIndex])); 666 } 667 668 ResultObjectMap = std::make_shared<PrValueToResultObject>( 669 buildResultObjectMap(DACtx, FuncDecl, getThisPointeeStorageLocation(), 670 LocForRecordReturnVal)); 671 } 672 673 void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) { 674 // We ignore some entries of `CalleeEnv`: 675 // - `DACtx` because is already the same in both 676 // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or 677 // `ThisPointeeLoc` because they don't apply to us. 678 // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the 679 // callee's local scope, so when popping that scope, we do not propagate 680 // the maps. 681 this->LocToVal = std::move(CalleeEnv.LocToVal); 682 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken); 683 684 if (Call->isGLValue()) { 685 if (CalleeEnv.ReturnLoc != nullptr) 686 setStorageLocation(*Call, *CalleeEnv.ReturnLoc); 687 } else if (!Call->getType()->isVoidType()) { 688 if (CalleeEnv.ReturnVal != nullptr) 689 setValue(*Call, *CalleeEnv.ReturnVal); 690 } 691 } 692 693 void Environment::popCall(const CXXConstructExpr *Call, 694 const Environment &CalleeEnv) { 695 // See also comment in `popCall(const CallExpr *, const Environment &)` above. 696 this->LocToVal = std::move(CalleeEnv.LocToVal); 697 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken); 698 699 if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) { 700 setValue(*Call, *Val); 701 } 702 } 703 704 bool Environment::equivalentTo(const Environment &Other, 705 Environment::ValueModel &Model) const { 706 assert(DACtx == Other.DACtx); 707 708 if (ReturnVal != Other.ReturnVal) 709 return false; 710 711 if (ReturnLoc != Other.ReturnLoc) 712 return false; 713 714 if (LocForRecordReturnVal != Other.LocForRecordReturnVal) 715 return false; 716 717 if (ThisPointeeLoc != Other.ThisPointeeLoc) 718 return false; 719 720 if (DeclToLoc != Other.DeclToLoc) 721 return false; 722 723 if (ExprToLoc != Other.ExprToLoc) 724 return false; 725 726 if (!compareKeyToValueMaps(ExprToVal, Other.ExprToVal, *this, Other, Model)) 727 return false; 728 729 if (!compareKeyToValueMaps(LocToVal, Other.LocToVal, *this, Other, Model)) 730 return false; 731 732 return true; 733 } 734 735 LatticeEffect Environment::widen(const Environment &PrevEnv, 736 Environment::ValueModel &Model) { 737 assert(DACtx == PrevEnv.DACtx); 738 assert(ReturnVal == PrevEnv.ReturnVal); 739 assert(ReturnLoc == PrevEnv.ReturnLoc); 740 assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal); 741 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc); 742 assert(CallStack == PrevEnv.CallStack); 743 assert(ResultObjectMap == PrevEnv.ResultObjectMap); 744 745 auto Effect = LatticeEffect::Unchanged; 746 747 // By the API, `PrevEnv` is a previous version of the environment for the same 748 // block, so we have some guarantees about its shape. In particular, it will 749 // be the result of a join or widen operation on previous values for this 750 // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that 751 // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain 752 // this property here, we don't need change their current values to widen. 753 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size()); 754 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size()); 755 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size()); 756 757 ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv, 758 Model, Effect); 759 760 LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv, 761 Model, Effect); 762 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() || 763 ExprToLoc.size() != PrevEnv.ExprToLoc.size() || 764 ExprToVal.size() != PrevEnv.ExprToVal.size() || 765 LocToVal.size() != PrevEnv.LocToVal.size()) 766 Effect = LatticeEffect::Changed; 767 768 return Effect; 769 } 770 771 Environment Environment::join(const Environment &EnvA, const Environment &EnvB, 772 Environment::ValueModel &Model, 773 ExprJoinBehavior ExprBehavior) { 774 assert(EnvA.DACtx == EnvB.DACtx); 775 assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal); 776 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc); 777 assert(EnvA.CallStack == EnvB.CallStack); 778 assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap); 779 780 Environment JoinedEnv(*EnvA.DACtx); 781 782 JoinedEnv.CallStack = EnvA.CallStack; 783 JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap; 784 JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal; 785 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc; 786 787 if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) { 788 // `ReturnVal` might not always get set -- for example if we have a return 789 // statement of the form `return some_other_func()` and we decide not to 790 // analyze `some_other_func()`. 791 // In this case, we can't say anything about the joined return value -- we 792 // don't simply want to propagate the return value that we do have, because 793 // it might not be the correct one. 794 // This occurs for example in the test `ContextSensitiveMutualRecursion`. 795 JoinedEnv.ReturnVal = nullptr; 796 } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) { 797 JoinedEnv.ReturnVal = EnvA.ReturnVal; 798 } else { 799 assert(!EnvA.CallStack.empty()); 800 // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this 801 // cast. 802 auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back()); 803 assert(Func != nullptr); 804 if (Value *JoinedVal = 805 joinDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA, 806 *EnvB.ReturnVal, EnvB, JoinedEnv, Model)) 807 JoinedEnv.ReturnVal = JoinedVal; 808 } 809 810 if (EnvA.ReturnLoc == EnvB.ReturnLoc) 811 JoinedEnv.ReturnLoc = EnvA.ReturnLoc; 812 else 813 JoinedEnv.ReturnLoc = nullptr; 814 815 JoinedEnv.DeclToLoc = intersectDeclToLoc(EnvA.DeclToLoc, EnvB.DeclToLoc); 816 817 // FIXME: update join to detect backedges and simplify the flow condition 818 // accordingly. 819 JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions( 820 EnvA.FlowConditionToken, EnvB.FlowConditionToken); 821 822 JoinedEnv.LocToVal = 823 joinLocToVal(EnvA.LocToVal, EnvB.LocToVal, EnvA, EnvB, JoinedEnv, Model); 824 825 if (ExprBehavior == KeepExprState) { 826 JoinedEnv.ExprToVal = joinExprMaps(EnvA.ExprToVal, EnvB.ExprToVal); 827 JoinedEnv.ExprToLoc = joinExprMaps(EnvA.ExprToLoc, EnvB.ExprToLoc); 828 } 829 830 return JoinedEnv; 831 } 832 833 StorageLocation &Environment::createStorageLocation(QualType Type) { 834 return DACtx->createStorageLocation(Type); 835 } 836 837 StorageLocation &Environment::createStorageLocation(const ValueDecl &D) { 838 // Evaluated declarations are always assigned the same storage locations to 839 // ensure that the environment stabilizes across loop iterations. Storage 840 // locations for evaluated declarations are stored in the analysis context. 841 return DACtx->getStableStorageLocation(D); 842 } 843 844 StorageLocation &Environment::createStorageLocation(const Expr &E) { 845 // Evaluated expressions are always assigned the same storage locations to 846 // ensure that the environment stabilizes across loop iterations. Storage 847 // locations for evaluated expressions are stored in the analysis context. 848 return DACtx->getStableStorageLocation(E); 849 } 850 851 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { 852 assert(!DeclToLoc.contains(&D)); 853 // The only kinds of declarations that may have a "variable" storage location 854 // are declarations of reference type and `BindingDecl`. For all other 855 // declaration, the storage location should be the stable storage location 856 // returned by `createStorageLocation()`. 857 assert(D.getType()->isReferenceType() || isa<BindingDecl>(D) || 858 &Loc == &createStorageLocation(D)); 859 DeclToLoc[&D] = &Loc; 860 } 861 862 StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const { 863 auto It = DeclToLoc.find(&D); 864 if (It == DeclToLoc.end()) 865 return nullptr; 866 867 StorageLocation *Loc = It->second; 868 869 return Loc; 870 } 871 872 void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(&D); } 873 874 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { 875 // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason, 876 // but we still want to be able to associate a `StorageLocation` with them, 877 // so allow these as an exception. 878 assert(E.isGLValue() || 879 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn)); 880 const Expr &CanonE = ignoreCFGOmittedNodes(E); 881 assert(!ExprToLoc.contains(&CanonE)); 882 ExprToLoc[&CanonE] = &Loc; 883 } 884 885 StorageLocation *Environment::getStorageLocation(const Expr &E) const { 886 // See comment in `setStorageLocation()`. 887 assert(E.isGLValue() || 888 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn)); 889 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); 890 return It == ExprToLoc.end() ? nullptr : &*It->second; 891 } 892 893 RecordStorageLocation & 894 Environment::getResultObjectLocation(const Expr &RecordPRValue) const { 895 assert(RecordPRValue.getType()->isRecordType()); 896 assert(RecordPRValue.isPRValue()); 897 898 assert(ResultObjectMap != nullptr); 899 RecordStorageLocation *Loc = ResultObjectMap->lookup(&RecordPRValue); 900 assert(Loc != nullptr); 901 // In release builds, use the "stable" storage location if the map lookup 902 // failed. 903 if (Loc == nullptr) 904 return cast<RecordStorageLocation>( 905 DACtx->getStableStorageLocation(RecordPRValue)); 906 return *Loc; 907 } 908 909 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { 910 return DACtx->getOrCreateNullPointerValue(PointeeType); 911 } 912 913 void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc, 914 QualType Type) { 915 llvm::DenseSet<QualType> Visited; 916 int CreatedValuesCount = 0; 917 initializeFieldsWithValues(Loc, Type, Visited, 0, CreatedValuesCount); 918 if (CreatedValuesCount > MaxCompositeValueSize) { 919 llvm::errs() << "Attempting to initialize a huge value of type: " << Type 920 << '\n'; 921 } 922 } 923 924 void Environment::setValue(const StorageLocation &Loc, Value &Val) { 925 assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc); 926 927 LocToVal[&Loc] = &Val; 928 } 929 930 void Environment::setValue(const Expr &E, Value &Val) { 931 const Expr &CanonE = ignoreCFGOmittedNodes(E); 932 933 if (auto *RecordVal = dyn_cast<RecordValue>(&Val)) { 934 assert(&RecordVal->getLoc() == &getResultObjectLocation(CanonE)); 935 (void)RecordVal; 936 } 937 938 assert(CanonE.isPRValue()); 939 ExprToVal[&CanonE] = &Val; 940 } 941 942 Value *Environment::getValue(const StorageLocation &Loc) const { 943 return LocToVal.lookup(&Loc); 944 } 945 946 Value *Environment::getValue(const ValueDecl &D) const { 947 auto *Loc = getStorageLocation(D); 948 if (Loc == nullptr) 949 return nullptr; 950 return getValue(*Loc); 951 } 952 953 Value *Environment::getValue(const Expr &E) const { 954 if (E.isPRValue()) { 955 auto It = ExprToVal.find(&ignoreCFGOmittedNodes(E)); 956 return It == ExprToVal.end() ? nullptr : It->second; 957 } 958 959 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); 960 if (It == ExprToLoc.end()) 961 return nullptr; 962 return getValue(*It->second); 963 } 964 965 Value *Environment::createValue(QualType Type) { 966 llvm::DenseSet<QualType> Visited; 967 int CreatedValuesCount = 0; 968 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0, 969 CreatedValuesCount); 970 if (CreatedValuesCount > MaxCompositeValueSize) { 971 llvm::errs() << "Attempting to initialize a huge value of type: " << Type 972 << '\n'; 973 } 974 return Val; 975 } 976 977 Value *Environment::createValueUnlessSelfReferential( 978 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth, 979 int &CreatedValuesCount) { 980 assert(!Type.isNull()); 981 assert(!Type->isReferenceType()); 982 983 // Allow unlimited fields at depth 1; only cap at deeper nesting levels. 984 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) || 985 Depth > MaxCompositeValueDepth) 986 return nullptr; 987 988 if (Type->isBooleanType()) { 989 CreatedValuesCount++; 990 return &makeAtomicBoolValue(); 991 } 992 993 if (Type->isIntegerType()) { 994 // FIXME: consider instead `return nullptr`, given that we do nothing useful 995 // with integers, and so distinguishing them serves no purpose, but could 996 // prevent convergence. 997 CreatedValuesCount++; 998 return &arena().create<IntegerValue>(); 999 } 1000 1001 if (Type->isPointerType()) { 1002 CreatedValuesCount++; 1003 QualType PointeeType = Type->getPointeeType(); 1004 StorageLocation &PointeeLoc = 1005 createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount); 1006 1007 return &arena().create<PointerValue>(PointeeLoc); 1008 } 1009 1010 if (Type->isRecordType()) { 1011 CreatedValuesCount++; 1012 auto &Loc = cast<RecordStorageLocation>(createStorageLocation(Type)); 1013 initializeFieldsWithValues(Loc, Loc.getType(), Visited, Depth, 1014 CreatedValuesCount); 1015 1016 return &refreshRecordValue(Loc, *this); 1017 } 1018 1019 return nullptr; 1020 } 1021 1022 StorageLocation & 1023 Environment::createLocAndMaybeValue(QualType Ty, 1024 llvm::DenseSet<QualType> &Visited, 1025 int Depth, int &CreatedValuesCount) { 1026 if (!Visited.insert(Ty.getCanonicalType()).second) 1027 return createStorageLocation(Ty.getNonReferenceType()); 1028 Value *Val = createValueUnlessSelfReferential( 1029 Ty.getNonReferenceType(), Visited, Depth, CreatedValuesCount); 1030 Visited.erase(Ty.getCanonicalType()); 1031 1032 Ty = Ty.getNonReferenceType(); 1033 1034 if (Val == nullptr) 1035 return createStorageLocation(Ty); 1036 1037 if (Ty->isRecordType()) 1038 return cast<RecordValue>(Val)->getLoc(); 1039 1040 StorageLocation &Loc = createStorageLocation(Ty); 1041 setValue(Loc, *Val); 1042 return Loc; 1043 } 1044 1045 void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc, 1046 QualType Type, 1047 llvm::DenseSet<QualType> &Visited, 1048 int Depth, 1049 int &CreatedValuesCount) { 1050 auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) { 1051 if (FieldType->isRecordType()) { 1052 auto &FieldRecordLoc = cast<RecordStorageLocation>(FieldLoc); 1053 setValue(FieldRecordLoc, create<RecordValue>(FieldRecordLoc)); 1054 initializeFieldsWithValues(FieldRecordLoc, FieldRecordLoc.getType(), 1055 Visited, Depth + 1, CreatedValuesCount); 1056 } else { 1057 if (!Visited.insert(FieldType.getCanonicalType()).second) 1058 return; 1059 if (Value *Val = createValueUnlessSelfReferential( 1060 FieldType, Visited, Depth + 1, CreatedValuesCount)) 1061 setValue(FieldLoc, *Val); 1062 Visited.erase(FieldType.getCanonicalType()); 1063 } 1064 }; 1065 1066 for (const FieldDecl *Field : DACtx->getModeledFields(Type)) { 1067 assert(Field != nullptr); 1068 QualType FieldType = Field->getType(); 1069 1070 if (FieldType->isReferenceType()) { 1071 Loc.setChild(*Field, 1072 &createLocAndMaybeValue(FieldType, Visited, Depth + 1, 1073 CreatedValuesCount)); 1074 } else { 1075 StorageLocation *FieldLoc = Loc.getChild(*Field); 1076 assert(FieldLoc != nullptr); 1077 initField(FieldType, *FieldLoc); 1078 } 1079 } 1080 for (const auto &[FieldName, FieldType] : DACtx->getSyntheticFields(Type)) { 1081 // Synthetic fields cannot have reference type, so we don't need to deal 1082 // with this case. 1083 assert(!FieldType->isReferenceType()); 1084 initField(FieldType, Loc.getSyntheticField(FieldName)); 1085 } 1086 } 1087 1088 StorageLocation &Environment::createObjectInternal(const ValueDecl *D, 1089 QualType Ty, 1090 const Expr *InitExpr) { 1091 if (Ty->isReferenceType()) { 1092 // Although variables of reference type always need to be initialized, it 1093 // can happen that we can't see the initializer, so `InitExpr` may still 1094 // be null. 1095 if (InitExpr) { 1096 if (auto *InitExprLoc = getStorageLocation(*InitExpr)) 1097 return *InitExprLoc; 1098 } 1099 1100 // Even though we have an initializer, we might not get an 1101 // InitExprLoc, for example if the InitExpr is a CallExpr for which we 1102 // don't have a function body. In this case, we just invent a storage 1103 // location and value -- it's the best we can do. 1104 return createObjectInternal(D, Ty.getNonReferenceType(), nullptr); 1105 } 1106 1107 StorageLocation &Loc = 1108 D ? createStorageLocation(*D) : createStorageLocation(Ty); 1109 1110 if (Ty->isRecordType()) { 1111 auto &RecordLoc = cast<RecordStorageLocation>(Loc); 1112 if (!InitExpr) 1113 initializeFieldsWithValues(RecordLoc); 1114 refreshRecordValue(RecordLoc, *this); 1115 } else { 1116 Value *Val = nullptr; 1117 if (InitExpr) 1118 // In the (few) cases where an expression is intentionally 1119 // "uninterpreted", `InitExpr` is not associated with a value. There are 1120 // two ways to handle this situation: propagate the status, so that 1121 // uninterpreted initializers result in uninterpreted variables, or 1122 // provide a default value. We choose the latter so that later refinements 1123 // of the variable can be used for reasoning about the surrounding code. 1124 // For this reason, we let this case be handled by the `createValue()` 1125 // call below. 1126 // 1127 // FIXME. If and when we interpret all language cases, change this to 1128 // assert that `InitExpr` is interpreted, rather than supplying a 1129 // default value (assuming we don't update the environment API to return 1130 // references). 1131 Val = getValue(*InitExpr); 1132 if (!Val) 1133 Val = createValue(Ty); 1134 if (Val) 1135 setValue(Loc, *Val); 1136 } 1137 1138 return Loc; 1139 } 1140 1141 void Environment::assume(const Formula &F) { 1142 DACtx->addFlowConditionConstraint(FlowConditionToken, F); 1143 } 1144 1145 bool Environment::proves(const Formula &F) const { 1146 return DACtx->flowConditionImplies(FlowConditionToken, F); 1147 } 1148 1149 bool Environment::allows(const Formula &F) const { 1150 return DACtx->flowConditionAllows(FlowConditionToken, F); 1151 } 1152 1153 void Environment::dump(raw_ostream &OS) const { 1154 llvm::DenseMap<const StorageLocation *, std::string> LocToName; 1155 if (LocForRecordReturnVal != nullptr) 1156 LocToName[LocForRecordReturnVal] = "(returned record)"; 1157 if (ThisPointeeLoc != nullptr) 1158 LocToName[ThisPointeeLoc] = "this"; 1159 1160 OS << "DeclToLoc:\n"; 1161 for (auto [D, L] : DeclToLoc) { 1162 auto Iter = LocToName.insert({L, D->getNameAsString()}).first; 1163 OS << " [" << Iter->second << ", " << L << "]\n"; 1164 } 1165 OS << "ExprToLoc:\n"; 1166 for (auto [E, L] : ExprToLoc) 1167 OS << " [" << E << ", " << L << "]\n"; 1168 1169 OS << "ExprToVal:\n"; 1170 for (auto [E, V] : ExprToVal) 1171 OS << " [" << E << ", " << V << ": " << *V << "]\n"; 1172 1173 OS << "LocToVal:\n"; 1174 for (auto [L, V] : LocToVal) { 1175 OS << " [" << L; 1176 if (auto Iter = LocToName.find(L); Iter != LocToName.end()) 1177 OS << " (" << Iter->second << ")"; 1178 OS << ", " << V << ": " << *V << "]\n"; 1179 } 1180 1181 if (const FunctionDecl *Func = getCurrentFunc()) { 1182 if (Func->getReturnType()->isReferenceType()) { 1183 OS << "ReturnLoc: " << ReturnLoc; 1184 if (auto Iter = LocToName.find(ReturnLoc); Iter != LocToName.end()) 1185 OS << " (" << Iter->second << ")"; 1186 OS << "\n"; 1187 } else if (Func->getReturnType()->isRecordType() || 1188 isa<CXXConstructorDecl>(Func)) { 1189 OS << "LocForRecordReturnVal: " << LocForRecordReturnVal << "\n"; 1190 } else if (!Func->getReturnType()->isVoidType()) { 1191 if (ReturnVal == nullptr) 1192 OS << "ReturnVal: nullptr\n"; 1193 else 1194 OS << "ReturnVal: " << *ReturnVal << "\n"; 1195 } 1196 1197 if (isa<CXXMethodDecl>(Func)) { 1198 OS << "ThisPointeeLoc: " << ThisPointeeLoc << "\n"; 1199 } 1200 } 1201 1202 OS << "\n"; 1203 DACtx->dumpFlowCondition(FlowConditionToken, OS); 1204 } 1205 1206 void Environment::dump() const { 1207 dump(llvm::dbgs()); 1208 } 1209 1210 Environment::PrValueToResultObject Environment::buildResultObjectMap( 1211 DataflowAnalysisContext *DACtx, const FunctionDecl *FuncDecl, 1212 RecordStorageLocation *ThisPointeeLoc, 1213 RecordStorageLocation *LocForRecordReturnVal) { 1214 assert(FuncDecl->doesThisDeclarationHaveABody()); 1215 1216 PrValueToResultObject Map; 1217 1218 ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx); 1219 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(FuncDecl)) 1220 Visitor.TraverseConstructorInits(Ctor, ThisPointeeLoc); 1221 Visitor.TraverseStmt(FuncDecl->getBody()); 1222 1223 return Map; 1224 } 1225 1226 RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, 1227 const Environment &Env) { 1228 Expr *ImplicitObject = MCE.getImplicitObjectArgument(); 1229 if (ImplicitObject == nullptr) 1230 return nullptr; 1231 if (ImplicitObject->getType()->isPointerType()) { 1232 if (auto *Val = Env.get<PointerValue>(*ImplicitObject)) 1233 return &cast<RecordStorageLocation>(Val->getPointeeLoc()); 1234 return nullptr; 1235 } 1236 return cast_or_null<RecordStorageLocation>( 1237 Env.getStorageLocation(*ImplicitObject)); 1238 } 1239 1240 RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, 1241 const Environment &Env) { 1242 Expr *Base = ME.getBase(); 1243 if (Base == nullptr) 1244 return nullptr; 1245 if (ME.isArrow()) { 1246 if (auto *Val = Env.get<PointerValue>(*Base)) 1247 return &cast<RecordStorageLocation>(Val->getPointeeLoc()); 1248 return nullptr; 1249 } 1250 return Env.get<RecordStorageLocation>(*Base); 1251 } 1252 1253 RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env) { 1254 auto &NewVal = Env.create<RecordValue>(Loc); 1255 Env.setValue(Loc, NewVal); 1256 return NewVal; 1257 } 1258 1259 RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env) { 1260 assert(Expr.getType()->isRecordType()); 1261 1262 if (Expr.isPRValue()) 1263 refreshRecordValue(Env.getResultObjectLocation(Expr), Env); 1264 1265 if (auto *Loc = Env.get<RecordStorageLocation>(Expr)) 1266 refreshRecordValue(*Loc, Env); 1267 1268 auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType())); 1269 Env.setStorageLocation(Expr, NewVal.getLoc()); 1270 return NewVal; 1271 } 1272 1273 } // namespace dataflow 1274 } // namespace clang 1275