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