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/Type.h" 19 #include "clang/Analysis/FlowSensitive/DataflowLattice.h" 20 #include "clang/Analysis/FlowSensitive/Value.h" 21 #include "llvm/ADT/DenseMap.h" 22 #include "llvm/ADT/DenseSet.h" 23 #include "llvm/ADT/MapVector.h" 24 #include "llvm/ADT/STLExtras.h" 25 #include "llvm/Support/ErrorHandling.h" 26 #include <cassert> 27 #include <utility> 28 29 namespace clang { 30 namespace dataflow { 31 32 // FIXME: convert these to parameters of the analysis or environment. Current 33 // settings have been experimentaly validated, but only for a particular 34 // analysis. 35 static constexpr int MaxCompositeValueDepth = 3; 36 static constexpr int MaxCompositeValueSize = 1000; 37 38 /// Returns a map consisting of key-value entries that are present in both maps. 39 template <typename K, typename V> 40 llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1, 41 const llvm::DenseMap<K, V> &Map2) { 42 llvm::DenseMap<K, V> Result; 43 for (auto &Entry : Map1) { 44 auto It = Map2.find(Entry.first); 45 if (It != Map2.end() && Entry.second == It->second) 46 Result.insert({Entry.first, Entry.second}); 47 } 48 return Result; 49 } 50 51 // Whether to consider equivalent two values with an unknown relation. 52 // 53 // FIXME: this function is a hack enabling unsoundness to support 54 // convergence. Once we have widening support for the reference/pointer and 55 // struct built-in models, this should be unconditionally `false` (and inlined 56 // as such at its call sites). 57 static bool equateUnknownValues(Value::Kind K) { 58 switch (K) { 59 case Value::Kind::Integer: 60 case Value::Kind::Pointer: 61 case Value::Kind::Record: 62 return true; 63 default: 64 return false; 65 } 66 } 67 68 static bool compareDistinctValues(QualType Type, Value &Val1, 69 const Environment &Env1, Value &Val2, 70 const Environment &Env2, 71 Environment::ValueModel &Model) { 72 // Note: Potentially costly, but, for booleans, we could check whether both 73 // can be proven equivalent in their respective environments. 74 75 // FIXME: move the reference/pointers logic from `areEquivalentValues` to here 76 // and implement separate, join/widen specific handling for 77 // reference/pointers. 78 switch (Model.compare(Type, Val1, Env1, Val2, Env2)) { 79 case ComparisonResult::Same: 80 return true; 81 case ComparisonResult::Different: 82 return false; 83 case ComparisonResult::Unknown: 84 return equateUnknownValues(Val1.getKind()); 85 } 86 llvm_unreachable("All cases covered in switch"); 87 } 88 89 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`, 90 /// respectively, of the same type `Type`. Merging generally produces a single 91 /// value that (soundly) approximates the two inputs, although the actual 92 /// meaning depends on `Model`. 93 static Value *mergeDistinctValues(QualType Type, Value &Val1, 94 const Environment &Env1, Value &Val2, 95 const Environment &Env2, 96 Environment &MergedEnv, 97 Environment::ValueModel &Model) { 98 // Join distinct boolean values preserving information about the constraints 99 // in the respective path conditions. 100 if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) { 101 // FIXME: Checking both values should be unnecessary, since they should have 102 // a consistent shape. However, right now we can end up with BoolValue's in 103 // integer-typed variables due to our incorrect handling of 104 // boolean-to-integer casts (we just propagate the BoolValue to the result 105 // of the cast). So, a join can encounter an integer in one branch but a 106 // bool in the other. 107 // For example: 108 // ``` 109 // std::optional<bool> o; 110 // int x; 111 // if (o.has_value()) 112 // x = o.value(); 113 // ``` 114 auto &Expr1 = cast<BoolValue>(Val1).formula(); 115 auto &Expr2 = cast<BoolValue>(Val2).formula(); 116 auto &A = MergedEnv.arena(); 117 auto &MergedVal = A.makeAtomRef(A.makeAtom()); 118 MergedEnv.addToFlowCondition( 119 A.makeOr(A.makeAnd(A.makeAtomRef(Env1.getFlowConditionToken()), 120 A.makeEquals(MergedVal, Expr1)), 121 A.makeAnd(A.makeAtomRef(Env2.getFlowConditionToken()), 122 A.makeEquals(MergedVal, Expr2)))); 123 return &A.makeBoolValue(MergedVal); 124 } 125 126 Value *MergedVal = nullptr; 127 if (auto *RecordVal1 = dyn_cast<RecordValue>(&Val1)) { 128 auto *RecordVal2 = cast<RecordValue>(&Val2); 129 130 if (&RecordVal1->getLoc() == &RecordVal2->getLoc()) 131 // `RecordVal1` and `RecordVal2` may have different properties associated 132 // with them. Create a new `RecordValue` with the same location but 133 // without any properties so that we soundly approximate both values. If a 134 // particular analysis needs to merge properties, it should do so in 135 // `DataflowAnalysis::merge()`. 136 MergedVal = &MergedEnv.create<RecordValue>(RecordVal1->getLoc()); 137 else 138 // If the locations for the two records are different, need to create a 139 // completely new value. 140 MergedVal = MergedEnv.createValue(Type); 141 } else { 142 MergedVal = MergedEnv.createValue(Type); 143 } 144 145 // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge` 146 // returns false to avoid storing unneeded values in `DACtx`. 147 if (MergedVal) 148 if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv)) 149 return MergedVal; 150 151 return nullptr; 152 } 153 154 // When widening does not change `Current`, return value will equal `&Prev`. 155 static Value &widenDistinctValues(QualType Type, Value &Prev, 156 const Environment &PrevEnv, Value &Current, 157 Environment &CurrentEnv, 158 Environment::ValueModel &Model) { 159 // Boolean-model widening. 160 if (isa<BoolValue>(&Prev)) { 161 assert(isa<BoolValue>(Current)); 162 // Widen to Top, because we know they are different values. If previous was 163 // already Top, re-use that to (implicitly) indicate that no change occured. 164 if (isa<TopBoolValue>(Prev)) 165 return Prev; 166 return CurrentEnv.makeTopBoolValue(); 167 } 168 169 // FIXME: Add other built-in model widening. 170 171 // Custom-model widening. 172 if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv)) 173 return *W; 174 175 return equateUnknownValues(Prev.getKind()) ? Prev : Current; 176 } 177 178 // Returns whether the values in `Map1` and `Map2` compare equal for those 179 // keys that `Map1` and `Map2` have in common. 180 template <typename Key> 181 bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1, 182 const llvm::MapVector<Key, Value *> &Map2, 183 const Environment &Env1, const Environment &Env2, 184 Environment::ValueModel &Model) { 185 for (auto &Entry : Map1) { 186 Key K = Entry.first; 187 assert(K != nullptr); 188 189 Value *Val = Entry.second; 190 assert(Val != nullptr); 191 192 auto It = Map2.find(K); 193 if (It == Map2.end()) 194 continue; 195 assert(It->second != nullptr); 196 197 if (!areEquivalentValues(*Val, *It->second) && 198 !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2, 199 Model)) 200 return false; 201 } 202 203 return true; 204 } 205 206 // Perform a join on either `LocToVal` or `ExprToVal`. `Key` must be either 207 // `const StorageLocation *` or `const Expr *`. 208 template <typename Key> 209 llvm::MapVector<Key, Value *> 210 joinKeyToValueMap(const llvm::MapVector<Key, Value *> &Map1, 211 const llvm::MapVector<Key, Value *> &Map2, 212 const Environment &Env1, const Environment &Env2, 213 Environment &JoinedEnv, Environment::ValueModel &Model) { 214 llvm::MapVector<Key, Value *> MergedMap; 215 for (auto &Entry : Map1) { 216 Key K = Entry.first; 217 assert(K != nullptr); 218 219 Value *Val = Entry.second; 220 assert(Val != nullptr); 221 222 auto It = Map2.find(K); 223 if (It == Map2.end()) 224 continue; 225 assert(It->second != nullptr); 226 227 if (areEquivalentValues(*Val, *It->second)) { 228 MergedMap.insert({K, Val}); 229 continue; 230 } 231 232 if (Value *MergedVal = mergeDistinctValues( 233 K->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) { 234 MergedMap.insert({K, MergedVal}); 235 } 236 } 237 238 return MergedMap; 239 } 240 241 // Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either 242 // `const StorageLocation *` or `const Expr *`. 243 template <typename Key> 244 llvm::MapVector<Key, Value *> 245 widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap, 246 const llvm::MapVector<Key, Value *> &PrevMap, 247 Environment &CurEnv, const Environment &PrevEnv, 248 Environment::ValueModel &Model, LatticeJoinEffect &Effect) { 249 llvm::MapVector<Key, Value *> WidenedMap; 250 for (auto &Entry : CurMap) { 251 Key K = Entry.first; 252 assert(K != nullptr); 253 254 Value *Val = Entry.second; 255 assert(Val != nullptr); 256 257 auto PrevIt = PrevMap.find(K); 258 if (PrevIt == PrevMap.end()) 259 continue; 260 assert(PrevIt->second != nullptr); 261 262 if (areEquivalentValues(*Val, *PrevIt->second)) { 263 WidenedMap.insert({K, Val}); 264 continue; 265 } 266 267 Value &WidenedVal = widenDistinctValues(K->getType(), *PrevIt->second, 268 PrevEnv, *Val, CurEnv, Model); 269 WidenedMap.insert({K, &WidenedVal}); 270 if (&WidenedVal != PrevIt->second) 271 Effect = LatticeJoinEffect::Changed; 272 } 273 274 return WidenedMap; 275 } 276 277 /// Initializes a global storage value. 278 static void insertIfGlobal(const Decl &D, 279 llvm::DenseSet<const VarDecl *> &Vars) { 280 if (auto *V = dyn_cast<VarDecl>(&D)) 281 if (V->hasGlobalStorage()) 282 Vars.insert(V); 283 } 284 285 static void insertIfFunction(const Decl &D, 286 llvm::DenseSet<const FunctionDecl *> &Funcs) { 287 if (auto *FD = dyn_cast<FunctionDecl>(&D)) 288 Funcs.insert(FD); 289 } 290 291 static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) { 292 if (!C.getMethodDecl()) 293 return nullptr; 294 auto *Body = dyn_cast_or_null<CompoundStmt>(C.getMethodDecl()->getBody()); 295 if (!Body || Body->size() != 1) 296 return nullptr; 297 if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin())) 298 if (auto *Return = RS->getRetValue()) 299 return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts()); 300 return nullptr; 301 } 302 303 static void 304 getFieldsGlobalsAndFuncs(const Decl &D, FieldSet &Fields, 305 llvm::DenseSet<const VarDecl *> &Vars, 306 llvm::DenseSet<const FunctionDecl *> &Funcs) { 307 insertIfGlobal(D, Vars); 308 insertIfFunction(D, Funcs); 309 if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D)) 310 for (const auto *B : Decomp->bindings()) 311 if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding())) 312 // FIXME: should we be using `E->getFoundDecl()`? 313 if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl())) 314 Fields.insert(FD); 315 } 316 317 /// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields, 318 /// global variables and functions that are declared in or referenced from 319 /// sub-statements. 320 static void 321 getFieldsGlobalsAndFuncs(const Stmt &S, FieldSet &Fields, 322 llvm::DenseSet<const VarDecl *> &Vars, 323 llvm::DenseSet<const FunctionDecl *> &Funcs) { 324 for (auto *Child : S.children()) 325 if (Child != nullptr) 326 getFieldsGlobalsAndFuncs(*Child, Fields, Vars, Funcs); 327 if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S)) 328 getFieldsGlobalsAndFuncs(*DefaultInit->getExpr(), Fields, Vars, Funcs); 329 330 if (auto *DS = dyn_cast<DeclStmt>(&S)) { 331 if (DS->isSingleDecl()) 332 getFieldsGlobalsAndFuncs(*DS->getSingleDecl(), Fields, Vars, Funcs); 333 else 334 for (auto *D : DS->getDeclGroup()) 335 getFieldsGlobalsAndFuncs(*D, Fields, Vars, Funcs); 336 } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) { 337 insertIfGlobal(*E->getDecl(), Vars); 338 insertIfFunction(*E->getDecl(), Funcs); 339 } else if (const auto *C = dyn_cast<CXXMemberCallExpr>(&S)) { 340 // If this is a method that returns a member variable but does nothing else, 341 // model the field of the return value. 342 if (MemberExpr *E = getMemberForAccessor(*C)) 343 if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl())) 344 Fields.insert(FD); 345 } else if (auto *E = dyn_cast<MemberExpr>(&S)) { 346 // FIXME: should we be using `E->getFoundDecl()`? 347 const ValueDecl *VD = E->getMemberDecl(); 348 insertIfGlobal(*VD, Vars); 349 insertIfFunction(*VD, Funcs); 350 if (const auto *FD = dyn_cast<FieldDecl>(VD)) 351 Fields.insert(FD); 352 } else if (auto *InitList = dyn_cast<InitListExpr>(&S)) { 353 if (RecordDecl *RD = InitList->getType()->getAsRecordDecl()) 354 for (const auto *FD : getFieldsForInitListExpr(RD)) 355 Fields.insert(FD); 356 } 357 } 358 359 // FIXME: Add support for resetting globals after function calls to enable 360 // the implementation of sound analyses. 361 void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) { 362 assert(FuncDecl->getBody() != nullptr); 363 364 FieldSet Fields; 365 llvm::DenseSet<const VarDecl *> Vars; 366 llvm::DenseSet<const FunctionDecl *> Funcs; 367 368 // Look for global variable and field references in the 369 // constructor-initializers. 370 if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) { 371 for (const auto *Init : CtorDecl->inits()) { 372 if (Init->isMemberInitializer()) { 373 Fields.insert(Init->getMember()); 374 } else if (Init->isIndirectMemberInitializer()) { 375 for (const auto *I : Init->getIndirectMember()->chain()) 376 Fields.insert(cast<FieldDecl>(I)); 377 } 378 const Expr *E = Init->getInit(); 379 assert(E != nullptr); 380 getFieldsGlobalsAndFuncs(*E, Fields, Vars, Funcs); 381 } 382 // Add all fields mentioned in default member initializers. 383 for (const FieldDecl *F : CtorDecl->getParent()->fields()) 384 if (const auto *I = F->getInClassInitializer()) 385 getFieldsGlobalsAndFuncs(*I, Fields, Vars, Funcs); 386 } 387 getFieldsGlobalsAndFuncs(*FuncDecl->getBody(), Fields, Vars, Funcs); 388 389 // These have to be added before the lines that follow to ensure that 390 // `create*` work correctly for structs. 391 DACtx->addModeledFields(Fields); 392 393 for (const VarDecl *D : Vars) { 394 if (getStorageLocation(*D) != nullptr) 395 continue; 396 397 setStorageLocation(*D, createObject(*D)); 398 } 399 400 for (const FunctionDecl *FD : Funcs) { 401 if (getStorageLocation(*FD) != nullptr) 402 continue; 403 auto &Loc = createStorageLocation(FD->getType()); 404 setStorageLocation(*FD, Loc); 405 } 406 } 407 408 Environment::Environment(DataflowAnalysisContext &DACtx) 409 : DACtx(&DACtx), 410 FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {} 411 412 Environment Environment::fork() const { 413 Environment Copy(*this); 414 Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken); 415 return Copy; 416 } 417 418 Environment::Environment(DataflowAnalysisContext &DACtx, 419 const DeclContext &DeclCtx) 420 : Environment(DACtx) { 421 CallStack.push_back(&DeclCtx); 422 423 if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) { 424 assert(FuncDecl->getBody() != nullptr); 425 426 initFieldsGlobalsAndFuncs(FuncDecl); 427 428 for (const auto *ParamDecl : FuncDecl->parameters()) { 429 assert(ParamDecl != nullptr); 430 setStorageLocation(*ParamDecl, createObject(*ParamDecl, nullptr)); 431 } 432 } 433 434 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) { 435 auto *Parent = MethodDecl->getParent(); 436 assert(Parent != nullptr); 437 438 if (Parent->isLambda()) { 439 for (auto Capture : Parent->captures()) { 440 if (Capture.capturesVariable()) { 441 const auto *VarDecl = Capture.getCapturedVar(); 442 assert(VarDecl != nullptr); 443 setStorageLocation(*VarDecl, createObject(*VarDecl, nullptr)); 444 } else if (Capture.capturesThis()) { 445 const auto *SurroundingMethodDecl = 446 cast<CXXMethodDecl>(DeclCtx.getNonClosureAncestor()); 447 QualType ThisPointeeType = 448 SurroundingMethodDecl->getFunctionObjectParameterType(); 449 ThisPointeeLoc = 450 &cast<RecordValue>(createValue(ThisPointeeType))->getLoc(); 451 } 452 } 453 } else if (MethodDecl->isImplicitObjectMemberFunction()) { 454 QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType(); 455 ThisPointeeLoc = 456 &cast<RecordValue>(createValue(ThisPointeeType))->getLoc(); 457 } 458 } 459 } 460 461 bool Environment::canDescend(unsigned MaxDepth, 462 const DeclContext *Callee) const { 463 return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee); 464 } 465 466 Environment Environment::pushCall(const CallExpr *Call) const { 467 Environment Env(*this); 468 469 if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) { 470 if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) { 471 if (!isa<CXXThisExpr>(Arg)) 472 Env.ThisPointeeLoc = 473 cast<RecordStorageLocation>(getStorageLocation(*Arg)); 474 // Otherwise (when the argument is `this`), retain the current 475 // environment's `ThisPointeeLoc`. 476 } 477 } 478 479 Env.pushCallInternal(Call->getDirectCallee(), 480 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs())); 481 482 return Env; 483 } 484 485 Environment Environment::pushCall(const CXXConstructExpr *Call) const { 486 Environment Env(*this); 487 488 Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call); 489 490 Env.pushCallInternal(Call->getConstructor(), 491 llvm::ArrayRef(Call->getArgs(), Call->getNumArgs())); 492 493 return Env; 494 } 495 496 void Environment::pushCallInternal(const FunctionDecl *FuncDecl, 497 ArrayRef<const Expr *> Args) { 498 // Canonicalize to the definition of the function. This ensures that we're 499 // putting arguments into the same `ParamVarDecl`s` that the callee will later 500 // be retrieving them from. 501 assert(FuncDecl->getDefinition() != nullptr); 502 FuncDecl = FuncDecl->getDefinition(); 503 504 CallStack.push_back(FuncDecl); 505 506 initFieldsGlobalsAndFuncs(FuncDecl); 507 508 const auto *ParamIt = FuncDecl->param_begin(); 509 510 // FIXME: Parameters don't always map to arguments 1:1; examples include 511 // overloaded operators implemented as member functions, and parameter packs. 512 for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) { 513 assert(ParamIt != FuncDecl->param_end()); 514 const VarDecl *Param = *ParamIt; 515 setStorageLocation(*Param, createObject(*Param, Args[ArgIndex])); 516 } 517 } 518 519 void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) { 520 // We ignore some entries of `CalleeEnv`: 521 // - `DACtx` because is already the same in both 522 // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or 523 // `ThisPointeeLoc` because they don't apply to us. 524 // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the 525 // callee's local scope, so when popping that scope, we do not propagate 526 // the maps. 527 this->LocToVal = std::move(CalleeEnv.LocToVal); 528 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken); 529 530 if (Call->isGLValue()) { 531 if (CalleeEnv.ReturnLoc != nullptr) 532 setStorageLocation(*Call, *CalleeEnv.ReturnLoc); 533 } else if (!Call->getType()->isVoidType()) { 534 if (CalleeEnv.ReturnVal != nullptr) 535 setValue(*Call, *CalleeEnv.ReturnVal); 536 } 537 } 538 539 void Environment::popCall(const CXXConstructExpr *Call, 540 const Environment &CalleeEnv) { 541 // See also comment in `popCall(const CallExpr *, const Environment &)` above. 542 this->LocToVal = std::move(CalleeEnv.LocToVal); 543 this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken); 544 545 if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) { 546 setValue(*Call, *Val); 547 } 548 } 549 550 bool Environment::equivalentTo(const Environment &Other, 551 Environment::ValueModel &Model) const { 552 assert(DACtx == Other.DACtx); 553 554 if (ReturnVal != Other.ReturnVal) 555 return false; 556 557 if (ReturnLoc != Other.ReturnLoc) 558 return false; 559 560 if (ThisPointeeLoc != Other.ThisPointeeLoc) 561 return false; 562 563 if (DeclToLoc != Other.DeclToLoc) 564 return false; 565 566 if (ExprToLoc != Other.ExprToLoc) 567 return false; 568 569 if (!compareKeyToValueMaps(ExprToVal, Other.ExprToVal, *this, Other, Model)) 570 return false; 571 572 if (!compareKeyToValueMaps(LocToVal, Other.LocToVal, *this, Other, Model)) 573 return false; 574 575 return true; 576 } 577 578 LatticeJoinEffect Environment::widen(const Environment &PrevEnv, 579 Environment::ValueModel &Model) { 580 assert(DACtx == PrevEnv.DACtx); 581 assert(ReturnVal == PrevEnv.ReturnVal); 582 assert(ReturnLoc == PrevEnv.ReturnLoc); 583 assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc); 584 assert(CallStack == PrevEnv.CallStack); 585 586 auto Effect = LatticeJoinEffect::Unchanged; 587 588 // By the API, `PrevEnv` is a previous version of the environment for the same 589 // block, so we have some guarantees about its shape. In particular, it will 590 // be the result of a join or widen operation on previous values for this 591 // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that 592 // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain 593 // this property here, we don't need change their current values to widen. 594 assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size()); 595 assert(ExprToVal.size() <= PrevEnv.ExprToVal.size()); 596 assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size()); 597 598 ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv, 599 Model, Effect); 600 601 LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv, 602 Model, Effect); 603 if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() || 604 ExprToLoc.size() != PrevEnv.ExprToLoc.size() || 605 ExprToVal.size() != PrevEnv.ExprToVal.size() || 606 LocToVal.size() != PrevEnv.LocToVal.size()) 607 Effect = LatticeJoinEffect::Changed; 608 609 return Effect; 610 } 611 612 Environment Environment::join(const Environment &EnvA, const Environment &EnvB, 613 Environment::ValueModel &Model) { 614 assert(EnvA.DACtx == EnvB.DACtx); 615 assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc); 616 assert(EnvA.CallStack == EnvB.CallStack); 617 618 Environment JoinedEnv(*EnvA.DACtx); 619 620 JoinedEnv.CallStack = EnvA.CallStack; 621 JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc; 622 623 if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) { 624 // `ReturnVal` might not always get set -- for example if we have a return 625 // statement of the form `return some_other_func()` and we decide not to 626 // analyze `some_other_func()`. 627 // In this case, we can't say anything about the joined return value -- we 628 // don't simply want to propagate the return value that we do have, because 629 // it might not be the correct one. 630 // This occurs for example in the test `ContextSensitiveMutualRecursion`. 631 JoinedEnv.ReturnVal = nullptr; 632 } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) { 633 JoinedEnv.ReturnVal = EnvA.ReturnVal; 634 } else { 635 assert(!EnvA.CallStack.empty()); 636 // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this 637 // cast. 638 auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back()); 639 assert(Func != nullptr); 640 if (Value *MergedVal = 641 mergeDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA, 642 *EnvB.ReturnVal, EnvB, JoinedEnv, Model)) 643 JoinedEnv.ReturnVal = MergedVal; 644 } 645 646 if (EnvA.ReturnLoc == EnvB.ReturnLoc) 647 JoinedEnv.ReturnLoc = EnvA.ReturnLoc; 648 else 649 JoinedEnv.ReturnLoc = nullptr; 650 651 JoinedEnv.DeclToLoc = intersectDenseMaps(EnvA.DeclToLoc, EnvB.DeclToLoc); 652 653 JoinedEnv.ExprToLoc = intersectDenseMaps(EnvA.ExprToLoc, EnvB.ExprToLoc); 654 655 // FIXME: update join to detect backedges and simplify the flow condition 656 // accordingly. 657 JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions( 658 EnvA.FlowConditionToken, EnvB.FlowConditionToken); 659 660 JoinedEnv.ExprToVal = joinKeyToValueMap(EnvA.ExprToVal, EnvB.ExprToVal, EnvA, 661 EnvB, JoinedEnv, Model); 662 663 JoinedEnv.LocToVal = joinKeyToValueMap(EnvA.LocToVal, EnvB.LocToVal, EnvA, 664 EnvB, JoinedEnv, Model); 665 666 return JoinedEnv; 667 } 668 669 StorageLocation &Environment::createStorageLocation(QualType Type) { 670 return DACtx->createStorageLocation(Type); 671 } 672 673 StorageLocation &Environment::createStorageLocation(const ValueDecl &D) { 674 // Evaluated declarations are always assigned the same storage locations to 675 // ensure that the environment stabilizes across loop iterations. Storage 676 // locations for evaluated declarations are stored in the analysis context. 677 return DACtx->getStableStorageLocation(D); 678 } 679 680 StorageLocation &Environment::createStorageLocation(const Expr &E) { 681 // Evaluated expressions are always assigned the same storage locations to 682 // ensure that the environment stabilizes across loop iterations. Storage 683 // locations for evaluated expressions are stored in the analysis context. 684 return DACtx->getStableStorageLocation(E); 685 } 686 687 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { 688 assert(!DeclToLoc.contains(&D)); 689 DeclToLoc[&D] = &Loc; 690 } 691 692 StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const { 693 auto It = DeclToLoc.find(&D); 694 if (It == DeclToLoc.end()) 695 return nullptr; 696 697 StorageLocation *Loc = It->second; 698 699 return Loc; 700 } 701 702 void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(&D); } 703 704 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { 705 // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason, 706 // but we still want to be able to associate a `StorageLocation` with them, 707 // so allow these as an exception. 708 assert(E.isGLValue() || 709 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn)); 710 setStorageLocationInternal(E, Loc); 711 } 712 713 StorageLocation *Environment::getStorageLocation(const Expr &E) const { 714 // See comment in `setStorageLocation()`. 715 assert(E.isGLValue() || 716 E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn)); 717 return getStorageLocationInternal(E); 718 } 719 720 RecordStorageLocation *Environment::getThisPointeeStorageLocation() const { 721 return ThisPointeeLoc; 722 } 723 724 RecordStorageLocation & 725 Environment::getResultObjectLocation(const Expr &RecordPRValue) { 726 assert(RecordPRValue.getType()->isRecordType()); 727 assert(RecordPRValue.isPRValue()); 728 729 if (StorageLocation *ExistingLoc = getStorageLocationInternal(RecordPRValue)) 730 return *cast<RecordStorageLocation>(ExistingLoc); 731 auto &Loc = cast<RecordStorageLocation>( 732 DACtx->getStableStorageLocation(RecordPRValue)); 733 setStorageLocationInternal(RecordPRValue, Loc); 734 return Loc; 735 } 736 737 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { 738 return DACtx->getOrCreateNullPointerValue(PointeeType); 739 } 740 741 void Environment::setValue(const StorageLocation &Loc, Value &Val) { 742 assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc); 743 744 LocToVal[&Loc] = &Val; 745 } 746 747 void Environment::setValue(const Expr &E, Value &Val) { 748 assert(E.isPRValue()); 749 ExprToVal[&E] = &Val; 750 } 751 752 Value *Environment::getValue(const StorageLocation &Loc) const { 753 return LocToVal.lookup(&Loc); 754 } 755 756 Value *Environment::getValue(const ValueDecl &D) const { 757 auto *Loc = getStorageLocation(D); 758 if (Loc == nullptr) 759 return nullptr; 760 return getValue(*Loc); 761 } 762 763 Value *Environment::getValue(const Expr &E) const { 764 if (E.isPRValue()) { 765 auto It = ExprToVal.find(&ignoreCFGOmittedNodes(E)); 766 return It == ExprToVal.end() ? nullptr : It->second; 767 } 768 769 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); 770 if (It == ExprToLoc.end()) 771 return nullptr; 772 return getValue(*It->second); 773 } 774 775 Value *Environment::createValue(QualType Type) { 776 llvm::DenseSet<QualType> Visited; 777 int CreatedValuesCount = 0; 778 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0, 779 CreatedValuesCount); 780 if (CreatedValuesCount > MaxCompositeValueSize) { 781 llvm::errs() << "Attempting to initialize a huge value of type: " << Type 782 << '\n'; 783 } 784 return Val; 785 } 786 787 void Environment::setStorageLocationInternal(const Expr &E, 788 StorageLocation &Loc) { 789 const Expr &CanonE = ignoreCFGOmittedNodes(E); 790 assert(!ExprToLoc.contains(&CanonE)); 791 ExprToLoc[&CanonE] = &Loc; 792 } 793 794 StorageLocation *Environment::getStorageLocationInternal(const Expr &E) const { 795 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); 796 return It == ExprToLoc.end() ? nullptr : &*It->second; 797 } 798 799 Value *Environment::createValueUnlessSelfReferential( 800 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth, 801 int &CreatedValuesCount) { 802 assert(!Type.isNull()); 803 assert(!Type->isReferenceType()); 804 805 // Allow unlimited fields at depth 1; only cap at deeper nesting levels. 806 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) || 807 Depth > MaxCompositeValueDepth) 808 return nullptr; 809 810 if (Type->isBooleanType()) { 811 CreatedValuesCount++; 812 return &makeAtomicBoolValue(); 813 } 814 815 if (Type->isIntegerType()) { 816 // FIXME: consider instead `return nullptr`, given that we do nothing useful 817 // with integers, and so distinguishing them serves no purpose, but could 818 // prevent convergence. 819 CreatedValuesCount++; 820 return &arena().create<IntegerValue>(); 821 } 822 823 if (Type->isPointerType()) { 824 CreatedValuesCount++; 825 QualType PointeeType = Type->getPointeeType(); 826 StorageLocation &PointeeLoc = 827 createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount); 828 829 return &arena().create<PointerValue>(PointeeLoc); 830 } 831 832 if (Type->isRecordType()) { 833 CreatedValuesCount++; 834 llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs; 835 for (const FieldDecl *Field : DACtx->getModeledFields(Type)) { 836 assert(Field != nullptr); 837 838 QualType FieldType = Field->getType(); 839 840 FieldLocs.insert( 841 {Field, &createLocAndMaybeValue(FieldType, Visited, Depth + 1, 842 CreatedValuesCount)}); 843 } 844 845 RecordStorageLocation &Loc = 846 arena().create<RecordStorageLocation>(Type, std::move(FieldLocs)); 847 RecordValue &RecordVal = create<RecordValue>(Loc); 848 849 // As we already have a storage location for the `RecordValue`, we can and 850 // should associate them in the environment. 851 setValue(Loc, RecordVal); 852 853 return &RecordVal; 854 } 855 856 return nullptr; 857 } 858 859 StorageLocation & 860 Environment::createLocAndMaybeValue(QualType Ty, 861 llvm::DenseSet<QualType> &Visited, 862 int Depth, int &CreatedValuesCount) { 863 if (!Visited.insert(Ty.getCanonicalType()).second) 864 return createStorageLocation(Ty.getNonReferenceType()); 865 Value *Val = createValueUnlessSelfReferential( 866 Ty.getNonReferenceType(), Visited, Depth, CreatedValuesCount); 867 Visited.erase(Ty.getCanonicalType()); 868 869 Ty = Ty.getNonReferenceType(); 870 871 if (Val == nullptr) 872 return createStorageLocation(Ty); 873 874 if (Ty->isRecordType()) 875 return cast<RecordValue>(Val)->getLoc(); 876 877 StorageLocation &Loc = createStorageLocation(Ty); 878 setValue(Loc, *Val); 879 return Loc; 880 } 881 882 StorageLocation &Environment::createObjectInternal(const ValueDecl *D, 883 QualType Ty, 884 const Expr *InitExpr) { 885 if (Ty->isReferenceType()) { 886 // Although variables of reference type always need to be initialized, it 887 // can happen that we can't see the initializer, so `InitExpr` may still 888 // be null. 889 if (InitExpr) { 890 if (auto *InitExprLoc = getStorageLocation(*InitExpr)) 891 return *InitExprLoc; 892 } 893 894 // Even though we have an initializer, we might not get an 895 // InitExprLoc, for example if the InitExpr is a CallExpr for which we 896 // don't have a function body. In this case, we just invent a storage 897 // location and value -- it's the best we can do. 898 return createObjectInternal(D, Ty.getNonReferenceType(), nullptr); 899 } 900 901 Value *Val = nullptr; 902 if (InitExpr) 903 // In the (few) cases where an expression is intentionally 904 // "uninterpreted", `InitExpr` is not associated with a value. There are 905 // two ways to handle this situation: propagate the status, so that 906 // uninterpreted initializers result in uninterpreted variables, or 907 // provide a default value. We choose the latter so that later refinements 908 // of the variable can be used for reasoning about the surrounding code. 909 // For this reason, we let this case be handled by the `createValue()` 910 // call below. 911 // 912 // FIXME. If and when we interpret all language cases, change this to 913 // assert that `InitExpr` is interpreted, rather than supplying a 914 // default value (assuming we don't update the environment API to return 915 // references). 916 Val = getValue(*InitExpr); 917 if (!Val) 918 Val = createValue(Ty); 919 920 if (Ty->isRecordType()) 921 return cast<RecordValue>(Val)->getLoc(); 922 923 StorageLocation &Loc = 924 D ? createStorageLocation(*D) : createStorageLocation(Ty); 925 926 if (Val) 927 setValue(Loc, *Val); 928 929 return Loc; 930 } 931 932 void Environment::addToFlowCondition(const Formula &Val) { 933 DACtx->addFlowConditionConstraint(FlowConditionToken, Val); 934 } 935 936 bool Environment::flowConditionImplies(const Formula &Val) const { 937 return DACtx->flowConditionImplies(FlowConditionToken, Val); 938 } 939 940 void Environment::dump(raw_ostream &OS) const { 941 // FIXME: add printing for remaining fields and allow caller to decide what 942 // fields are printed. 943 OS << "DeclToLoc:\n"; 944 for (auto [D, L] : DeclToLoc) 945 OS << " [" << D->getNameAsString() << ", " << L << "]\n"; 946 947 OS << "ExprToLoc:\n"; 948 for (auto [E, L] : ExprToLoc) 949 OS << " [" << E << ", " << L << "]\n"; 950 951 OS << "ExprToVal:\n"; 952 for (auto [E, V] : ExprToVal) 953 OS << " [" << E << ", " << V << ": " << *V << "]\n"; 954 955 OS << "LocToVal:\n"; 956 for (auto [L, V] : LocToVal) { 957 OS << " [" << L << ", " << V << ": " << *V << "]\n"; 958 } 959 960 OS << "FlowConditionToken:\n"; 961 DACtx->dumpFlowCondition(FlowConditionToken, OS); 962 } 963 964 void Environment::dump() const { 965 dump(llvm::dbgs()); 966 } 967 968 RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, 969 const Environment &Env) { 970 Expr *ImplicitObject = MCE.getImplicitObjectArgument(); 971 if (ImplicitObject == nullptr) 972 return nullptr; 973 if (ImplicitObject->getType()->isPointerType()) { 974 if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*ImplicitObject))) 975 return &cast<RecordStorageLocation>(Val->getPointeeLoc()); 976 return nullptr; 977 } 978 return cast_or_null<RecordStorageLocation>( 979 Env.getStorageLocation(*ImplicitObject)); 980 } 981 982 RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, 983 const Environment &Env) { 984 Expr *Base = ME.getBase(); 985 if (Base == nullptr) 986 return nullptr; 987 if (ME.isArrow()) { 988 if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Base))) 989 return &cast<RecordStorageLocation>(Val->getPointeeLoc()); 990 return nullptr; 991 } 992 return cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Base)); 993 } 994 995 std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD) { 996 // Unnamed bitfields are only used for padding and do not appear in 997 // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s 998 // field list, and we thus need to remove them before mapping inits to 999 // fields to avoid mapping inits to the wrongs fields. 1000 std::vector<FieldDecl *> Fields; 1001 llvm::copy_if( 1002 RD->fields(), std::back_inserter(Fields), 1003 [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); }); 1004 return Fields; 1005 } 1006 1007 RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env) { 1008 auto &NewVal = Env.create<RecordValue>(Loc); 1009 Env.setValue(Loc, NewVal); 1010 return NewVal; 1011 } 1012 1013 RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env) { 1014 assert(Expr.getType()->isRecordType()); 1015 1016 if (Expr.isPRValue()) { 1017 if (auto *ExistingVal = cast_or_null<RecordValue>(Env.getValue(Expr))) { 1018 auto &NewVal = Env.create<RecordValue>(ExistingVal->getLoc()); 1019 Env.setValue(Expr, NewVal); 1020 return NewVal; 1021 } 1022 1023 auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType())); 1024 Env.setValue(Expr, NewVal); 1025 return NewVal; 1026 } 1027 1028 if (auto *Loc = 1029 cast_or_null<RecordStorageLocation>(Env.getStorageLocation(Expr))) { 1030 auto &NewVal = Env.create<RecordValue>(*Loc); 1031 Env.setValue(*Loc, NewVal); 1032 return NewVal; 1033 } 1034 1035 auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType())); 1036 Env.setStorageLocation(Expr, NewVal.getLoc()); 1037 return NewVal; 1038 } 1039 1040 } // namespace dataflow 1041 } // namespace clang 1042