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