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 bool Environment::equivalentTo(const Environment &Other, 204 Environment::ValueModel &Model) const { 205 assert(DACtx == Other.DACtx); 206 207 if (DeclToLoc != Other.DeclToLoc) 208 return false; 209 210 if (ExprToLoc != Other.ExprToLoc) 211 return false; 212 213 // Compare the contents for the intersection of their domains. 214 for (auto &Entry : LocToVal) { 215 const StorageLocation *Loc = Entry.first; 216 assert(Loc != nullptr); 217 218 Value *Val = Entry.second; 219 assert(Val != nullptr); 220 221 auto It = Other.LocToVal.find(Loc); 222 if (It == Other.LocToVal.end()) 223 continue; 224 assert(It->second != nullptr); 225 226 if (!equivalentValues(Loc->getType(), Val, *this, It->second, Other, Model)) 227 return false; 228 } 229 230 return true; 231 } 232 233 LatticeJoinEffect Environment::join(const Environment &Other, 234 Environment::ValueModel &Model) { 235 assert(DACtx == Other.DACtx); 236 237 auto Effect = LatticeJoinEffect::Unchanged; 238 239 Environment JoinedEnv(*DACtx); 240 241 JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); 242 if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size()) 243 Effect = LatticeJoinEffect::Changed; 244 245 JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc); 246 if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size()) 247 Effect = LatticeJoinEffect::Changed; 248 249 JoinedEnv.MemberLocToStruct = 250 intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct); 251 if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size()) 252 Effect = LatticeJoinEffect::Changed; 253 254 // FIXME: set `Effect` as needed. 255 JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions( 256 *FlowConditionToken, *Other.FlowConditionToken); 257 258 for (auto &Entry : LocToVal) { 259 const StorageLocation *Loc = Entry.first; 260 assert(Loc != nullptr); 261 262 Value *Val = Entry.second; 263 assert(Val != nullptr); 264 265 auto It = Other.LocToVal.find(Loc); 266 if (It == Other.LocToVal.end()) 267 continue; 268 assert(It->second != nullptr); 269 270 if (Val == It->second) { 271 JoinedEnv.LocToVal.insert({Loc, Val}); 272 continue; 273 } 274 275 if (Value *MergedVal = mergeDistinctValues( 276 Loc->getType(), Val, *this, It->second, Other, JoinedEnv, Model)) 277 JoinedEnv.LocToVal.insert({Loc, MergedVal}); 278 } 279 if (LocToVal.size() != JoinedEnv.LocToVal.size()) 280 Effect = LatticeJoinEffect::Changed; 281 282 *this = std::move(JoinedEnv); 283 284 return Effect; 285 } 286 287 StorageLocation &Environment::createStorageLocation(QualType Type) { 288 return DACtx->getStableStorageLocation(Type); 289 } 290 291 StorageLocation &Environment::createStorageLocation(const VarDecl &D) { 292 // Evaluated declarations are always assigned the same storage locations to 293 // ensure that the environment stabilizes across loop iterations. Storage 294 // locations for evaluated declarations are stored in the analysis context. 295 return DACtx->getStableStorageLocation(D); 296 } 297 298 StorageLocation &Environment::createStorageLocation(const Expr &E) { 299 // Evaluated expressions are always assigned the same storage locations to 300 // ensure that the environment stabilizes across loop iterations. Storage 301 // locations for evaluated expressions are stored in the analysis context. 302 return DACtx->getStableStorageLocation(E); 303 } 304 305 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { 306 assert(DeclToLoc.find(&D) == DeclToLoc.end()); 307 DeclToLoc[&D] = &Loc; 308 } 309 310 StorageLocation *Environment::getStorageLocation(const ValueDecl &D, 311 SkipPast SP) const { 312 auto It = DeclToLoc.find(&D); 313 return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP); 314 } 315 316 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { 317 const Expr &CanonE = ignoreCFGOmittedNodes(E); 318 assert(ExprToLoc.find(&CanonE) == ExprToLoc.end()); 319 ExprToLoc[&CanonE] = &Loc; 320 } 321 322 StorageLocation *Environment::getStorageLocation(const Expr &E, 323 SkipPast SP) const { 324 // FIXME: Add a test with parens. 325 auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E)); 326 return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP); 327 } 328 329 StorageLocation *Environment::getThisPointeeStorageLocation() const { 330 return DACtx->getThisPointeeStorageLocation(); 331 } 332 333 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { 334 return DACtx->getOrCreateNullPointerValue(PointeeType); 335 } 336 337 void Environment::setValue(const StorageLocation &Loc, Value &Val) { 338 LocToVal[&Loc] = &Val; 339 340 if (auto *StructVal = dyn_cast<StructValue>(&Val)) { 341 auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc); 342 343 const QualType Type = AggregateLoc.getType(); 344 assert(Type->isStructureOrClassType()); 345 346 for (const FieldDecl *Field : getObjectFields(Type)) { 347 assert(Field != nullptr); 348 StorageLocation &FieldLoc = AggregateLoc.getChild(*Field); 349 MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field); 350 if (auto *FieldVal = StructVal->getChild(*Field)) 351 setValue(FieldLoc, *FieldVal); 352 } 353 } 354 355 auto IT = MemberLocToStruct.find(&Loc); 356 if (IT != MemberLocToStruct.end()) { 357 // `Loc` is the location of a struct member so we need to also update the 358 // value of the member in the corresponding `StructValue`. 359 360 assert(IT->second.first != nullptr); 361 StructValue &StructVal = *IT->second.first; 362 363 assert(IT->second.second != nullptr); 364 const ValueDecl &Member = *IT->second.second; 365 366 StructVal.setChild(Member, Val); 367 } 368 } 369 370 Value *Environment::getValue(const StorageLocation &Loc) const { 371 auto It = LocToVal.find(&Loc); 372 return It == LocToVal.end() ? nullptr : It->second; 373 } 374 375 Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const { 376 auto *Loc = getStorageLocation(D, SP); 377 if (Loc == nullptr) 378 return nullptr; 379 return getValue(*Loc); 380 } 381 382 Value *Environment::getValue(const Expr &E, SkipPast SP) const { 383 auto *Loc = getStorageLocation(E, SP); 384 if (Loc == nullptr) 385 return nullptr; 386 return getValue(*Loc); 387 } 388 389 Value *Environment::createValue(QualType Type) { 390 llvm::DenseSet<QualType> Visited; 391 int CreatedValuesCount = 0; 392 Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0, 393 CreatedValuesCount); 394 if (CreatedValuesCount > MaxCompositeValueSize) { 395 llvm::errs() << "Attempting to initialize a huge value of type: " << Type 396 << '\n'; 397 } 398 return Val; 399 } 400 401 Value *Environment::createValueUnlessSelfReferential( 402 QualType Type, llvm::DenseSet<QualType> &Visited, int Depth, 403 int &CreatedValuesCount) { 404 assert(!Type.isNull()); 405 406 // Allow unlimited fields at depth 1; only cap at deeper nesting levels. 407 if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) || 408 Depth > MaxCompositeValueDepth) 409 return nullptr; 410 411 if (Type->isBooleanType()) { 412 CreatedValuesCount++; 413 return &makeAtomicBoolValue(); 414 } 415 416 if (Type->isIntegerType()) { 417 CreatedValuesCount++; 418 return &takeOwnership(std::make_unique<IntegerValue>()); 419 } 420 421 if (Type->isReferenceType()) { 422 CreatedValuesCount++; 423 QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType(); 424 auto &PointeeLoc = createStorageLocation(PointeeType); 425 426 if (Visited.insert(PointeeType.getCanonicalType()).second) { 427 Value *PointeeVal = createValueUnlessSelfReferential( 428 PointeeType, Visited, Depth, CreatedValuesCount); 429 Visited.erase(PointeeType.getCanonicalType()); 430 431 if (PointeeVal != nullptr) 432 setValue(PointeeLoc, *PointeeVal); 433 } 434 435 return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc)); 436 } 437 438 if (Type->isPointerType()) { 439 CreatedValuesCount++; 440 QualType PointeeType = Type->castAs<PointerType>()->getPointeeType(); 441 auto &PointeeLoc = createStorageLocation(PointeeType); 442 443 if (Visited.insert(PointeeType.getCanonicalType()).second) { 444 Value *PointeeVal = createValueUnlessSelfReferential( 445 PointeeType, Visited, Depth, CreatedValuesCount); 446 Visited.erase(PointeeType.getCanonicalType()); 447 448 if (PointeeVal != nullptr) 449 setValue(PointeeLoc, *PointeeVal); 450 } 451 452 return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc)); 453 } 454 455 if (Type->isStructureOrClassType()) { 456 CreatedValuesCount++; 457 // FIXME: Initialize only fields that are accessed in the context that is 458 // being analyzed. 459 llvm::DenseMap<const ValueDecl *, Value *> FieldValues; 460 for (const FieldDecl *Field : getObjectFields(Type)) { 461 assert(Field != nullptr); 462 463 QualType FieldType = Field->getType(); 464 if (Visited.contains(FieldType.getCanonicalType())) 465 continue; 466 467 Visited.insert(FieldType.getCanonicalType()); 468 if (auto *FieldValue = createValueUnlessSelfReferential( 469 FieldType, Visited, Depth + 1, CreatedValuesCount)) 470 FieldValues.insert({Field, FieldValue}); 471 Visited.erase(FieldType.getCanonicalType()); 472 } 473 474 return &takeOwnership( 475 std::make_unique<StructValue>(std::move(FieldValues))); 476 } 477 478 return nullptr; 479 } 480 481 StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const { 482 switch (SP) { 483 case SkipPast::None: 484 return Loc; 485 case SkipPast::Reference: 486 // References cannot be chained so we only need to skip past one level of 487 // indirection. 488 if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc))) 489 return Val->getReferentLoc(); 490 return Loc; 491 case SkipPast::ReferenceThenPointer: 492 StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference); 493 if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef))) 494 return Val->getPointeeLoc(); 495 return LocPastRef; 496 } 497 llvm_unreachable("bad SkipPast kind"); 498 } 499 500 const StorageLocation &Environment::skip(const StorageLocation &Loc, 501 SkipPast SP) const { 502 return skip(*const_cast<StorageLocation *>(&Loc), SP); 503 } 504 505 void Environment::addToFlowCondition(BoolValue &Val) { 506 DACtx->addFlowConditionConstraint(*FlowConditionToken, Val); 507 } 508 509 bool Environment::flowConditionImplies(BoolValue &Val) const { 510 return DACtx->flowConditionImplies(*FlowConditionToken, Val); 511 } 512 513 void Environment::dump() const { 514 DACtx->dumpFlowCondition(*FlowConditionToken); 515 } 516 517 } // namespace dataflow 518 } // namespace clang 519