1 //===-- DataflowAnalysisContext.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 a DataflowAnalysisContext class that owns objects that 10 // encompass the state of a program and stores context that is used during 11 // dataflow analysis. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" 16 #include "clang/AST/ExprCXX.h" 17 #include "clang/Analysis/FlowSensitive/DebugSupport.h" 18 #include "clang/Analysis/FlowSensitive/Value.h" 19 #include "llvm/ADT/SetOperations.h" 20 #include "llvm/Support/Debug.h" 21 #include <cassert> 22 #include <memory> 23 #include <utility> 24 25 namespace clang { 26 namespace dataflow { 27 28 void DataflowAnalysisContext::addModeledFields( 29 const llvm::DenseSet<const FieldDecl *> &Fields) { 30 llvm::set_union(ModeledFields, Fields); 31 } 32 33 llvm::DenseSet<const FieldDecl *> 34 DataflowAnalysisContext::getReferencedFields(QualType Type) { 35 llvm::DenseSet<const FieldDecl *> Fields = getObjectFields(Type); 36 llvm::set_intersect(Fields, ModeledFields); 37 return Fields; 38 } 39 40 StorageLocation &DataflowAnalysisContext::createStorageLocation(QualType Type) { 41 if (!Type.isNull() && 42 (Type->isStructureOrClassType() || Type->isUnionType())) { 43 llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs; 44 // During context-sensitive analysis, a struct may be allocated in one 45 // function, but its field accessed in a function lower in the stack than 46 // the allocation. Since we only collect fields used in the function where 47 // the allocation occurs, we can't apply that filter when performing 48 // context-sensitive analysis. But, this only applies to storage locations, 49 // since field access it not allowed to fail. In contrast, field *values* 50 // don't need this allowance, since the API allows for uninitialized fields. 51 auto Fields = Opts.ContextSensitiveOpts ? getObjectFields(Type) 52 : getReferencedFields(Type); 53 for (const FieldDecl *Field : Fields) 54 FieldLocs.insert({Field, &createStorageLocation(Field->getType())}); 55 return takeOwnership( 56 std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs))); 57 } 58 return takeOwnership(std::make_unique<ScalarStorageLocation>(Type)); 59 } 60 61 StorageLocation & 62 DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) { 63 if (auto *Loc = getStorageLocation(D)) 64 return *Loc; 65 auto &Loc = createStorageLocation(D.getType()); 66 setStorageLocation(D, Loc); 67 return Loc; 68 } 69 70 StorageLocation & 71 DataflowAnalysisContext::getStableStorageLocation(const Expr &E) { 72 if (auto *Loc = getStorageLocation(E)) 73 return *Loc; 74 auto &Loc = createStorageLocation(E.getType()); 75 setStorageLocation(E, Loc); 76 return Loc; 77 } 78 79 PointerValue & 80 DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) { 81 auto CanonicalPointeeType = 82 PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType(); 83 auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr); 84 if (Res.second) { 85 auto &PointeeLoc = createStorageLocation(CanonicalPointeeType); 86 Res.first->second = 87 &takeOwnership(std::make_unique<PointerValue>(PointeeLoc)); 88 } 89 return *Res.first->second; 90 } 91 92 static std::pair<BoolValue *, BoolValue *> 93 makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) { 94 auto Res = std::make_pair(&LHS, &RHS); 95 if (&RHS < &LHS) 96 std::swap(Res.first, Res.second); 97 return Res; 98 } 99 100 BoolValue &DataflowAnalysisContext::getOrCreateConjunction(BoolValue &LHS, 101 BoolValue &RHS) { 102 if (&LHS == &RHS) 103 return LHS; 104 105 auto Res = ConjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS), 106 nullptr); 107 if (Res.second) 108 Res.first->second = 109 &takeOwnership(std::make_unique<ConjunctionValue>(LHS, RHS)); 110 return *Res.first->second; 111 } 112 113 BoolValue &DataflowAnalysisContext::getOrCreateDisjunction(BoolValue &LHS, 114 BoolValue &RHS) { 115 if (&LHS == &RHS) 116 return LHS; 117 118 auto Res = DisjunctionVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS), 119 nullptr); 120 if (Res.second) 121 Res.first->second = 122 &takeOwnership(std::make_unique<DisjunctionValue>(LHS, RHS)); 123 return *Res.first->second; 124 } 125 126 BoolValue &DataflowAnalysisContext::getOrCreateNegation(BoolValue &Val) { 127 auto Res = NegationVals.try_emplace(&Val, nullptr); 128 if (Res.second) 129 Res.first->second = &takeOwnership(std::make_unique<NegationValue>(Val)); 130 return *Res.first->second; 131 } 132 133 BoolValue &DataflowAnalysisContext::getOrCreateImplication(BoolValue &LHS, 134 BoolValue &RHS) { 135 if (&LHS == &RHS) 136 return getBoolLiteralValue(true); 137 138 auto Res = ImplicationVals.try_emplace(std::make_pair(&LHS, &RHS), nullptr); 139 if (Res.second) 140 Res.first->second = 141 &takeOwnership(std::make_unique<ImplicationValue>(LHS, RHS)); 142 return *Res.first->second; 143 } 144 145 BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS, 146 BoolValue &RHS) { 147 if (&LHS == &RHS) 148 return getBoolLiteralValue(true); 149 150 auto Res = BiconditionalVals.try_emplace(makeCanonicalBoolValuePair(LHS, RHS), 151 nullptr); 152 if (Res.second) 153 Res.first->second = 154 &takeOwnership(std::make_unique<BiconditionalValue>(LHS, RHS)); 155 return *Res.first->second; 156 } 157 158 AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() { 159 return createAtomicBoolValue(); 160 } 161 162 void DataflowAnalysisContext::addFlowConditionConstraint( 163 AtomicBoolValue &Token, BoolValue &Constraint) { 164 auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint); 165 if (!Res.second) { 166 Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint); 167 } 168 } 169 170 AtomicBoolValue & 171 DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) { 172 auto &ForkToken = makeFlowConditionToken(); 173 FlowConditionDeps[&ForkToken].insert(&Token); 174 addFlowConditionConstraint(ForkToken, Token); 175 return ForkToken; 176 } 177 178 AtomicBoolValue & 179 DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken, 180 AtomicBoolValue &SecondToken) { 181 auto &Token = makeFlowConditionToken(); 182 FlowConditionDeps[&Token].insert(&FirstToken); 183 FlowConditionDeps[&Token].insert(&SecondToken); 184 addFlowConditionConstraint(Token, 185 getOrCreateDisjunction(FirstToken, SecondToken)); 186 return Token; 187 } 188 189 Solver::Result 190 DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) { 191 Constraints.insert(&getBoolLiteralValue(true)); 192 Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false))); 193 return S->solve(std::move(Constraints)); 194 } 195 196 bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token, 197 BoolValue &Val) { 198 // Returns true if and only if truth assignment of the flow condition implies 199 // that `Val` is also true. We prove whether or not this property holds by 200 // reducing the problem to satisfiability checking. In other words, we attempt 201 // to show that assuming `Val` is false makes the constraints induced by the 202 // flow condition unsatisfiable. 203 llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)}; 204 llvm::DenseSet<AtomicBoolValue *> VisitedTokens; 205 addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens); 206 return isUnsatisfiable(std::move(Constraints)); 207 } 208 209 bool DataflowAnalysisContext::flowConditionIsTautology(AtomicBoolValue &Token) { 210 // Returns true if and only if we cannot prove that the flow condition can 211 // ever be false. 212 llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)}; 213 llvm::DenseSet<AtomicBoolValue *> VisitedTokens; 214 addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens); 215 return isUnsatisfiable(std::move(Constraints)); 216 } 217 218 bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1, 219 BoolValue &Val2) { 220 llvm::DenseSet<BoolValue *> Constraints = { 221 &getOrCreateNegation(getOrCreateIff(Val1, Val2))}; 222 return isUnsatisfiable(Constraints); 223 } 224 225 void DataflowAnalysisContext::addTransitiveFlowConditionConstraints( 226 AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints, 227 llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) { 228 auto Res = VisitedTokens.insert(&Token); 229 if (!Res.second) 230 return; 231 232 auto ConstraintsIt = FlowConditionConstraints.find(&Token); 233 if (ConstraintsIt == FlowConditionConstraints.end()) { 234 Constraints.insert(&Token); 235 } else { 236 // Bind flow condition token via `iff` to its set of constraints: 237 // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints 238 Constraints.insert(&getOrCreateIff(Token, *ConstraintsIt->second)); 239 } 240 241 auto DepsIt = FlowConditionDeps.find(&Token); 242 if (DepsIt != FlowConditionDeps.end()) { 243 for (AtomicBoolValue *DepToken : DepsIt->second) { 244 addTransitiveFlowConditionConstraints(*DepToken, Constraints, 245 VisitedTokens); 246 } 247 } 248 } 249 250 BoolValue &DataflowAnalysisContext::substituteBoolValue( 251 BoolValue &Val, 252 llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) { 253 auto It = SubstitutionsCache.find(&Val); 254 if (It != SubstitutionsCache.end()) { 255 // Return memoized result of substituting this boolean value. 256 return *It->second; 257 } 258 259 // Handle substitution on the boolean value (and its subvalues), saving the 260 // result into `SubstitutionsCache`. 261 BoolValue *Result; 262 switch (Val.getKind()) { 263 case Value::Kind::AtomicBool: { 264 Result = &Val; 265 break; 266 } 267 case Value::Kind::Negation: { 268 auto &Negation = *cast<NegationValue>(&Val); 269 auto &Sub = substituteBoolValue(Negation.getSubVal(), SubstitutionsCache); 270 Result = &getOrCreateNegation(Sub); 271 break; 272 } 273 case Value::Kind::Disjunction: { 274 auto &Disjunct = *cast<DisjunctionValue>(&Val); 275 auto &LeftSub = 276 substituteBoolValue(Disjunct.getLeftSubValue(), SubstitutionsCache); 277 auto &RightSub = 278 substituteBoolValue(Disjunct.getRightSubValue(), SubstitutionsCache); 279 Result = &getOrCreateDisjunction(LeftSub, RightSub); 280 break; 281 } 282 case Value::Kind::Conjunction: { 283 auto &Conjunct = *cast<ConjunctionValue>(&Val); 284 auto &LeftSub = 285 substituteBoolValue(Conjunct.getLeftSubValue(), SubstitutionsCache); 286 auto &RightSub = 287 substituteBoolValue(Conjunct.getRightSubValue(), SubstitutionsCache); 288 Result = &getOrCreateConjunction(LeftSub, RightSub); 289 break; 290 } 291 case Value::Kind::Implication: { 292 auto &IV = *cast<ImplicationValue>(&Val); 293 auto &LeftSub = 294 substituteBoolValue(IV.getLeftSubValue(), SubstitutionsCache); 295 auto &RightSub = 296 substituteBoolValue(IV.getRightSubValue(), SubstitutionsCache); 297 Result = &getOrCreateImplication(LeftSub, RightSub); 298 break; 299 } 300 case Value::Kind::Biconditional: { 301 auto &BV = *cast<BiconditionalValue>(&Val); 302 auto &LeftSub = 303 substituteBoolValue(BV.getLeftSubValue(), SubstitutionsCache); 304 auto &RightSub = 305 substituteBoolValue(BV.getRightSubValue(), SubstitutionsCache); 306 Result = &getOrCreateIff(LeftSub, RightSub); 307 break; 308 } 309 default: 310 llvm_unreachable("Unhandled Value Kind"); 311 } 312 SubstitutionsCache[&Val] = Result; 313 return *Result; 314 } 315 316 BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition( 317 AtomicBoolValue &Token, 318 llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) { 319 assert( 320 Substitutions.find(&getBoolLiteralValue(true)) == Substitutions.end() && 321 Substitutions.find(&getBoolLiteralValue(false)) == Substitutions.end() && 322 "Do not substitute true/false boolean literals"); 323 llvm::DenseMap<BoolValue *, BoolValue *> SubstitutionsCache( 324 Substitutions.begin(), Substitutions.end()); 325 return buildAndSubstituteFlowConditionWithCache(Token, SubstitutionsCache); 326 } 327 328 BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache( 329 AtomicBoolValue &Token, 330 llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) { 331 auto ConstraintsIt = FlowConditionConstraints.find(&Token); 332 if (ConstraintsIt == FlowConditionConstraints.end()) { 333 return getBoolLiteralValue(true); 334 } 335 auto DepsIt = FlowConditionDeps.find(&Token); 336 if (DepsIt != FlowConditionDeps.end()) { 337 for (AtomicBoolValue *DepToken : DepsIt->second) { 338 auto &NewDep = buildAndSubstituteFlowConditionWithCache( 339 *DepToken, SubstitutionsCache); 340 SubstitutionsCache[DepToken] = &NewDep; 341 } 342 } 343 return substituteBoolValue(*ConstraintsIt->second, SubstitutionsCache); 344 } 345 346 void DataflowAnalysisContext::dumpFlowCondition(AtomicBoolValue &Token) { 347 llvm::DenseSet<BoolValue *> Constraints = {&Token}; 348 llvm::DenseSet<AtomicBoolValue *> VisitedTokens; 349 addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens); 350 351 llvm::DenseMap<const AtomicBoolValue *, std::string> AtomNames = { 352 {&getBoolLiteralValue(false), "False"}, 353 {&getBoolLiteralValue(true), "True"}}; 354 llvm::dbgs() << debugString(Constraints, AtomNames); 355 } 356 357 const ControlFlowContext * 358 DataflowAnalysisContext::getControlFlowContext(const FunctionDecl *F) { 359 // Canonicalize the key: 360 F = F->getDefinition(); 361 if (F == nullptr) 362 return nullptr; 363 auto It = FunctionContexts.find(F); 364 if (It != FunctionContexts.end()) 365 return &It->second; 366 367 if (Stmt *Body = F->getBody()) { 368 auto CFCtx = ControlFlowContext::build(F, *Body, F->getASTContext()); 369 // FIXME: Handle errors. 370 assert(CFCtx); 371 auto Result = FunctionContexts.insert({F, std::move(*CFCtx)}); 372 return &Result.first->second; 373 } 374 375 return nullptr; 376 } 377 378 } // namespace dataflow 379 } // namespace clang 380 381 using namespace clang; 382 383 const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) { 384 const Expr *Current = &E; 385 if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) { 386 Current = EWC->getSubExpr(); 387 assert(Current != nullptr); 388 } 389 Current = Current->IgnoreParens(); 390 assert(Current != nullptr); 391 return *Current; 392 } 393 394 const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) { 395 if (auto *E = dyn_cast<Expr>(&S)) 396 return ignoreCFGOmittedNodes(*E); 397 return S; 398 } 399 400 // FIXME: Does not precisely handle non-virtual diamond inheritance. A single 401 // field decl will be modeled for all instances of the inherited field. 402 static void 403 getFieldsFromClassHierarchy(QualType Type, 404 llvm::DenseSet<const FieldDecl *> &Fields) { 405 if (Type->isIncompleteType() || Type->isDependentType() || 406 !Type->isRecordType()) 407 return; 408 409 for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) 410 Fields.insert(Field); 411 if (auto *CXXRecord = Type->getAsCXXRecordDecl()) 412 for (const CXXBaseSpecifier &Base : CXXRecord->bases()) 413 getFieldsFromClassHierarchy(Base.getType(), Fields); 414 } 415 416 /// Gets the set of all fields in the type. 417 llvm::DenseSet<const FieldDecl *> 418 clang::dataflow::getObjectFields(QualType Type) { 419 llvm::DenseSet<const FieldDecl *> Fields; 420 getFieldsFromClassHierarchy(Type, Fields); 421 return Fields; 422 } 423