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/Support/Casting.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include <cassert> 26 #include <memory> 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 static bool areEquivalentIndirectionValues(Value *Val1, Value *Val2) { 52 if (auto *IndVal1 = dyn_cast<ReferenceValue>(Val1)) { 53 auto *IndVal2 = cast<ReferenceValue>(Val2); 54 return &IndVal1->getReferentLoc() == &IndVal2->getReferentLoc(); 55 } 56 if (auto *IndVal1 = dyn_cast<PointerValue>(Val1)) { 57 auto *IndVal2 = cast<PointerValue>(Val2); 58 return &IndVal1->getPointeeLoc() == &IndVal2->getPointeeLoc(); 59 } 60 return false; 61 } 62 63 /// Returns true if and only if `Val1` is equivalent to `Val2`. 64 static bool equivalentValues(QualType Type, Value *Val1, 65 const Environment &Env1, Value *Val2, 66 const Environment &Env2, 67 Environment::ValueModel &Model) { 68 return Val1 == Val2 || areEquivalentIndirectionValues(Val1, Val2) || 69 Model.compareEquivalent(Type, *Val1, Env1, *Val2, Env2); 70 } 71 72 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`, 73 /// respectively, of the same type `Type`. Merging generally produces a single 74 /// value that (soundly) approximates the two inputs, although the actual 75 /// meaning depends on `Model`. 76 static Value *mergeDistinctValues(QualType Type, Value *Val1, 77 const Environment &Env1, Value *Val2, 78 const Environment &Env2, 79 Environment &MergedEnv, 80 Environment::ValueModel &Model) { 81 // Join distinct boolean values preserving information about the constraints 82 // in the respective path conditions. 83 // 84 // FIXME: Does not work for backedges, since the two (or more) paths will not 85 // have mutually exclusive conditions. 86 if (auto *Expr1 = dyn_cast<BoolValue>(Val1)) { 87 auto *Expr2 = cast<BoolValue>(Val2); 88 auto &MergedVal = MergedEnv.makeAtomicBoolValue(); 89 MergedEnv.addToFlowCondition(MergedEnv.makeOr( 90 MergedEnv.makeAnd(Env1.getFlowConditionToken(), 91 MergedEnv.makeIff(MergedVal, *Expr1)), 92 MergedEnv.makeAnd(Env2.getFlowConditionToken(), 93 MergedEnv.makeIff(MergedVal, *Expr2)))); 94 return &MergedVal; 95 } 96 97 // FIXME: add unit tests that cover this statement. 98 if (areEquivalentIndirectionValues(Val1, Val2)) { 99 return Val1; 100 } 101 102 // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge` 103 // returns false to avoid storing unneeded values in `DACtx`. 104 if (Value *MergedVal = MergedEnv.createValue(Type)) 105 if (Model.merge(Type, *Val1, Env1, *Val2, Env2, *MergedVal, MergedEnv)) 106 return MergedVal; 107 108 return nullptr; 109 } 110 111 /// Initializes a global storage value. 112 static void initGlobalVar(const VarDecl &D, Environment &Env) { 113 if (!D.hasGlobalStorage() || 114 Env.getStorageLocation(D, SkipPast::None) != nullptr) 115 return; 116 117 auto &Loc = Env.createStorageLocation(D); 118 Env.setStorageLocation(D, Loc); 119 if (auto *Val = Env.createValue(D.getType())) 120 Env.setValue(Loc, *Val); 121 } 122 123 /// Initializes a global storage value. 124 static void initGlobalVar(const Decl &D, Environment &Env) { 125 if (auto *V = dyn_cast<VarDecl>(&D)) 126 initGlobalVar(*V, Env); 127 } 128 129 /// Initializes global storage values that are declared or referenced from 130 /// sub-statements of `S`. 131 // FIXME: Add support for resetting globals after function calls to enable 132 // the implementation of sound analyses. 133 static void initGlobalVars(const Stmt &S, Environment &Env) { 134 for (auto *Child : S.children()) { 135 if (Child != nullptr) 136 initGlobalVars(*Child, Env); 137 } 138 139 if (auto *DS = dyn_cast<DeclStmt>(&S)) { 140 if (DS->isSingleDecl()) { 141 initGlobalVar(*DS->getSingleDecl(), Env); 142 } else { 143 for (auto *D : DS->getDeclGroup()) 144 initGlobalVar(*D, Env); 145 } 146 } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) { 147 initGlobalVar(*E->getDecl(), Env); 148 } else if (auto *E = dyn_cast<MemberExpr>(&S)) { 149 initGlobalVar(*E->getMemberDecl(), Env); 150 } 151 } 152 153 Environment::Environment(DataflowAnalysisContext &DACtx) 154 : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {} 155 156 Environment::Environment(const Environment &Other) 157 : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc), 158 ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal), 159 MemberLocToStruct(Other.MemberLocToStruct), 160 FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) { 161 } 162 163 Environment &Environment::operator=(const Environment &Other) { 164 Environment Copy(Other); 165 *this = std::move(Copy); 166 return *this; 167 } 168 169 Environment::Environment(DataflowAnalysisContext &DACtx, 170 const DeclContext &DeclCtx) 171 : Environment(DACtx) { 172 if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) { 173 assert(FuncDecl->getBody() != nullptr); 174 initGlobalVars(*FuncDecl->getBody(), *this); 175 for (const auto *ParamDecl : FuncDecl->parameters()) { 176 assert(ParamDecl != nullptr); 177 auto &ParamLoc = createStorageLocation(*ParamDecl); 178 setStorageLocation(*ParamDecl, ParamLoc); 179 if (Value *ParamVal = createValue(ParamDecl->getType())) 180 setValue(ParamLoc, *ParamVal); 181 } 182 } 183 184 if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) { 185 auto *Parent = MethodDecl->getParent(); 186 assert(Parent != nullptr); 187 if (Parent->isLambda()) 188 MethodDecl = dyn_cast<CXXMethodDecl>(Parent->getDeclContext()); 189 190 if (MethodDecl && !MethodDecl->isStatic()) { 191 QualType ThisPointeeType = MethodDecl->getThisObjectType(); 192 // FIXME: Add support for union types. 193 if (!ThisPointeeType->isUnionType()) { 194 auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType); 195 DACtx.setThisPointeeStorageLocation(ThisPointeeLoc); 196 if (Value *ThisPointeeVal = createValue(ThisPointeeType)) 197 setValue(ThisPointeeLoc, *ThisPointeeVal); 198 } 199 } 200 } 201 } 202 203 Environment Environment::pushCall(const CallExpr *Call) const { 204 Environment Env(*this); 205 206 // FIXME: Currently this only works if the callee is never a method and the 207 // same callee is never analyzed from multiple separate callsites. To 208 // generalize this, we'll need to store a "context" field (probably a stack of 209 // `const CallExpr *`s) in the `Environment`, and then change the 210 // `DataflowAnalysisContext` class to hold a map from contexts to "frames", 211 // where each frame stores its own version of what are currently the 212 // `DeclToLoc`, `ExprToLoc`, and `ThisPointeeLoc` fields. 213 214 const auto *FuncDecl = Call->getDirectCallee(); 215 assert(FuncDecl != nullptr); 216 assert(FuncDecl->getBody() != nullptr); 217 // FIXME: In order to allow the callee to reference globals, we probably need 218 // to call `initGlobalVars` here in some way. 219 220 auto ParamIt = FuncDecl->param_begin(); 221 auto ArgIt = Call->arg_begin(); 222 auto ArgEnd = Call->arg_end(); 223 224 // FIXME: Parameters don't always map to arguments 1:1; examples include 225 // overloaded operators implemented as member functions, and parameter packs. 226 for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) { 227 assert(ParamIt != FuncDecl->param_end()); 228 229 const VarDecl *Param = *ParamIt; 230 const Expr *Arg = *ArgIt; 231 auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference); 232 assert(ArgLoc != nullptr); 233 Env.setStorageLocation(*Param, *ArgLoc); 234 } 235 236 return Env; 237 } 238 239 bool Environment::equivalentTo(const Environment &Other, 240 Environment::ValueModel &Model) const { 241 assert(DACtx == Other.DACtx); 242 243 if (DeclToLoc != Other.DeclToLoc) 244 return false; 245 246 if (ExprToLoc != Other.ExprToLoc) 247 return false; 248 249 // Compare the contents for the intersection of their domains. 250 for (auto &Entry : LocToVal) { 251 const StorageLocation *Loc = Entry.first; 252 assert(Loc != nullptr); 253 254 Value *Val = Entry.second; 255 assert(Val != nullptr); 256 257 auto It = Other.LocToVal.find(Loc); 258 if (It == Other.LocToVal.end()) 259 continue; 260 assert(It->second != nullptr); 261 262 if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model)) 263 return false; 264 } 265 266 return true; 267 } 268 269 LatticeJoinEffect Environment::join(const Environment &Other, 270 Environment::ValueModel &Model) { 271 assert(DACtx == Other.DACtx); 272 273 auto Effect = LatticeJoinEffect::Unchanged; 274 275 Environment JoinedEnv(*DACtx); 276 277 JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); 278 if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size()) 279 Effect = LatticeJoinEffect::Changed; 280 281 JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc); 282 if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size()) 283 Effect = LatticeJoinEffect::Changed; 284 285 JoinedEnv.MemberLocToStruct = 286 intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct); 287 if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size()) 288 Effect = LatticeJoinEffect::Changed; 289 290 // FIXME: set `Effect` as needed. 291 JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions( 292 *FlowConditionToken, *Other.FlowConditionToken); 293 294 for (auto &Entry : LocToVal) { 295 const StorageLocation *Loc = Entry.first; 296 assert(Loc != nullptr); 297 298 Value *Val = Entry.second; 299 assert(Val != nullptr); 300 301 auto It = Other.LocToVal.find(Loc); 302 if (It == Other.LocToVal.end()) 303 continue; 304 assert(It->second != nullptr); 305 306 if (Val == It->second) { 307 JoinedEnv.LocToVal.insert({Loc, Val}); 308 continue; 309 } 310 311 if (Value *MergedVal = mergeDistinctValues( 312 Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model)) 313 JoinedEnv.LocToVal.insert({Loc, MergedVal}); 314 } 315 if (LocToVal.size() != JoinedEnv.LocToVal.size()) 316 Effect = LatticeJoinEffect::Changed; 317 318 *this = std::move(JoinedEnv); 319 320 return Effect; 321 } 322 323 StorageLocation &Environment::createStorageLocation(QualType Type) { 324 return DACtx->getStableStorageLocation(Type); 325 } 326 327 StorageLocation &Environment::createStorageLocation(const VarDecl &D) { 328 // Evaluated declarations are always assigned the same storage locations to 329 // ensure that the environment stabilizes across loop iterations. Storage 330 // locations for evaluated declarations are stored in the analysis context. 331 return DACtx->getStableStorageLocation(D); 332 } 333 334 StorageLocation &Environment::createStorageLocation(const Expr &E) { 335 // Evaluated expressions are always assigned the same storage locations to 336 // ensure that the environment stabilizes across loop iterations. Storage 337 // locations for evaluated expressions are stored in the analysis context. 338 return DACtx->getStableStorageLocation(E); 339 } 340 341 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { 342 assert(DeclToLoc.find(&D) == DeclToLoc.end()); 343 DeclToLoc[&D] = &Loc; 344 } 345 346 StorageLocation *Environment::getStorageLocation(const ValueDecl &D, 347 SkipPast SP) const { 348 auto It = DeclToLoc.find(&D); 349 return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP); 350 } 351 352 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { 353 const Expr &CanonE = ignoreCFGOmittedNodes(E); 354 assert(ExprToLoc.find(&CanonE) == ExprToLoc.end()); 355 ExprToLoc[&CanonE] = &Loc; 356 } 357 358 StorageLocation *Environment::getStorageLocation(const Expr &E, 359 SkipPast SP) const { 360 // FIXME: Add a test with parens. 361 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); 362 return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP); 363 } 364 365 StorageLocation *Environment::getThisPointeeStorageLocation() const { 366 return DACtx->getThisPointeeStorageLocation(); 367 } 368 369 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { 370 return DACtx->getOrCreateNullPointerValue(PointeeType); 371 } 372 373 void Environment::setValue(const StorageLocation &Loc, Value &Val) { 374 LocToVal[&Loc] = &Val; 375 376 if (auto *StructVal = dyn_cast<StructValue>(&Val)) { 377 auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc); 378 379 const QualType Type = AggregateLoc.getType(); 380 assert(Type->isStructureOrClassType()); 381 382 for (const FieldDecl *Field : getObjectFields(Type)) { 383 assert(Field != nullptr); 384 StorageLocation &FieldLoc = AggregateLoc.getChild(*Field); 385 MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field); 386 if (auto *FieldVal = StructVal->getChild(*Field)) 387 setValue(FieldLoc, *FieldVal); 388 } 389 } 390 391 auto It = MemberLocToStruct.find(&Loc); 392 if (It != MemberLocToStruct.end()) { 393 // `Loc` is the location of a struct member so we need to also update the 394 // value of the member in the corresponding `StructValue`. 395 396 assert(It->second.first != nullptr); 397 StructValue &StructVal = *It->second.first; 398 399 assert(It->second.second != nullptr); 400 const ValueDecl &Member = *It->second.second; 401 402 StructVal.setChild(Member, Val); 403 } 404 } 405 406 Value *Environment::getValue(const StorageLocation &Loc) const { 407 auto It = LocToVal.find(&Loc); 408 return It == LocToVal.end() ? nullptr : It->second; 409 } 410 411 Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const { 412 auto *Loc = getStorageLocation(D, SP); 413 if (Loc == nullptr) 414 return nullptr; 415 return getValue(*Loc); 416 } 417 418 Value *Environment::getValue(const Expr &E, SkipPast SP) const { 419 auto *Loc = getStorageLocation(E, SP); 420 if (Loc == nullptr) 421 return nullptr; 422 return getValue(*Loc); 423 } 424 425 Value *Environment::createValue(QualType Type) { 426 llvm::DenseSet<QualType> Visited; 427 int CreatedValuesCount = 0; 428 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0, 429 CreatedValuesCount); 430 if (CreatedValuesCount > MaxCompositeValueSize) { 431 llvm::errs() << "Attempting to initialize a huge value of type: " << Type 432 << '\n'; 433 } 434 return Val; 435 } 436 437 Value *Environment::createValueUnlessSelfReferential( 438 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth, 439 int &CreatedValuesCount) { 440 assert(!Type.isNull()); 441 442 // Allow unlimited fields at depth 1; only cap at deeper nesting levels. 443 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) || 444 Depth > MaxCompositeValueDepth) 445 return nullptr; 446 447 if (Type->isBooleanType()) { 448 CreatedValuesCount++; 449 return &makeAtomicBoolValue(); 450 } 451 452 if (Type->isIntegerType()) { 453 CreatedValuesCount++; 454 return &takeOwnership(std::make_unique<IntegerValue>()); 455 } 456 457 if (Type->isReferenceType()) { 458 CreatedValuesCount++; 459 QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType(); 460 auto &PointeeLoc = createStorageLocation(PointeeType); 461 462 if (Visited.insert(PointeeType.getCanonicalType()).second) { 463 Value *PointeeVal = createValueUnlessSelfReferential( 464 PointeeType, Visited, Depth, CreatedValuesCount); 465 Visited.erase(PointeeType.getCanonicalType()); 466 467 if (PointeeVal != nullptr) 468 setValue(PointeeLoc, *PointeeVal); 469 } 470 471 return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc)); 472 } 473 474 if (Type->isPointerType()) { 475 CreatedValuesCount++; 476 QualType PointeeType = Type->castAs<PointerType>()->getPointeeType(); 477 auto &PointeeLoc = createStorageLocation(PointeeType); 478 479 if (Visited.insert(PointeeType.getCanonicalType()).second) { 480 Value *PointeeVal = createValueUnlessSelfReferential( 481 PointeeType, Visited, Depth, CreatedValuesCount); 482 Visited.erase(PointeeType.getCanonicalType()); 483 484 if (PointeeVal != nullptr) 485 setValue(PointeeLoc, *PointeeVal); 486 } 487 488 return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc)); 489 } 490 491 if (Type->isStructureOrClassType()) { 492 CreatedValuesCount++; 493 // FIXME: Initialize only fields that are accessed in the context that is 494 // being analyzed. 495 llvm::DenseMap<const ValueDecl *, Value *> FieldValues; 496 for (const FieldDecl *Field : getObjectFields(Type)) { 497 assert(Field != nullptr); 498 499 QualType FieldType = Field->getType(); 500 if (Visited.contains(FieldType.getCanonicalType())) 501 continue; 502 503 Visited.insert(FieldType.getCanonicalType()); 504 if (auto *FieldValue = createValueUnlessSelfReferential( 505 FieldType, Visited, Depth + 1, CreatedValuesCount)) 506 FieldValues.insert({Field, FieldValue}); 507 Visited.erase(FieldType.getCanonicalType()); 508 } 509 510 return &takeOwnership( 511 std::make_unique<StructValue>(std::move(FieldValues))); 512 } 513 514 return nullptr; 515 } 516 517 StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const { 518 switch (SP) { 519 case SkipPast::None: 520 return Loc; 521 case SkipPast::Reference: 522 // References cannot be chained so we only need to skip past one level of 523 // indirection. 524 if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc))) 525 return Val->getReferentLoc(); 526 return Loc; 527 case SkipPast::ReferenceThenPointer: 528 StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference); 529 if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef))) 530 return Val->getPointeeLoc(); 531 return LocPastRef; 532 } 533 llvm_unreachable("bad SkipPast kind"); 534 } 535 536 const StorageLocation &Environment::skip(const StorageLocation &Loc, 537 SkipPast SP) const { 538 return skip(*const_cast<StorageLocation *>(&Loc), SP); 539 } 540 541 void Environment::addToFlowCondition(BoolValue &Val) { 542 DACtx->addFlowConditionConstraint(*FlowConditionToken, Val); 543 } 544 545 bool Environment::flowConditionImplies(BoolValue &Val) const { 546 return DACtx->flowConditionImplies(*FlowConditionToken, Val); 547 } 548 549 void Environment::dump() const { 550 DACtx->dumpFlowCondition(*FlowConditionToken); 551 } 552 553 } // namespace dataflow 554 } // namespace clang 555