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 return &LHS == &RHS ? getBoolLiteralValue(true) 117 : getOrCreateDisjunction(getOrCreateNegation(LHS), RHS); 118 } 119 120 BoolValue &DataflowAnalysisContext::getOrCreateIff(BoolValue &LHS, 121 BoolValue &RHS) { 122 return &LHS == &RHS 123 ? getBoolLiteralValue(true) 124 : getOrCreateConjunction(getOrCreateImplication(LHS, RHS), 125 getOrCreateImplication(RHS, LHS)); 126 } 127 128 AtomicBoolValue &DataflowAnalysisContext::makeFlowConditionToken() { 129 return createAtomicBoolValue(); 130 } 131 132 void DataflowAnalysisContext::addFlowConditionConstraint( 133 AtomicBoolValue &Token, BoolValue &Constraint) { 134 auto Res = FlowConditionConstraints.try_emplace(&Token, &Constraint); 135 if (!Res.second) { 136 Res.first->second = &getOrCreateConjunction(*Res.first->second, Constraint); 137 } 138 } 139 140 AtomicBoolValue & 141 DataflowAnalysisContext::forkFlowCondition(AtomicBoolValue &Token) { 142 auto &ForkToken = makeFlowConditionToken(); 143 FlowConditionDeps[&ForkToken].insert(&Token); 144 addFlowConditionConstraint(ForkToken, Token); 145 return ForkToken; 146 } 147 148 AtomicBoolValue & 149 DataflowAnalysisContext::joinFlowConditions(AtomicBoolValue &FirstToken, 150 AtomicBoolValue &SecondToken) { 151 auto &Token = makeFlowConditionToken(); 152 FlowConditionDeps[&Token].insert(&FirstToken); 153 FlowConditionDeps[&Token].insert(&SecondToken); 154 addFlowConditionConstraint(Token, 155 getOrCreateDisjunction(FirstToken, SecondToken)); 156 return Token; 157 } 158 159 Solver::Result 160 DataflowAnalysisContext::querySolver(llvm::DenseSet<BoolValue *> Constraints) { 161 Constraints.insert(&getBoolLiteralValue(true)); 162 Constraints.insert(&getOrCreateNegation(getBoolLiteralValue(false))); 163 return S->solve(std::move(Constraints)); 164 } 165 166 bool DataflowAnalysisContext::flowConditionImplies(AtomicBoolValue &Token, 167 BoolValue &Val) { 168 // Returns true if and only if truth assignment of the flow condition implies 169 // that `Val` is also true. We prove whether or not this property holds by 170 // reducing the problem to satisfiability checking. In other words, we attempt 171 // to show that assuming `Val` is false makes the constraints induced by the 172 // flow condition unsatisfiable. 173 llvm::DenseSet<BoolValue *> Constraints = {&Token, &getOrCreateNegation(Val)}; 174 llvm::DenseSet<AtomicBoolValue *> VisitedTokens; 175 addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens); 176 return isUnsatisfiable(std::move(Constraints)); 177 } 178 179 bool DataflowAnalysisContext::flowConditionIsTautology(AtomicBoolValue &Token) { 180 // Returns true if and only if we cannot prove that the flow condition can 181 // ever be false. 182 llvm::DenseSet<BoolValue *> Constraints = {&getOrCreateNegation(Token)}; 183 llvm::DenseSet<AtomicBoolValue *> VisitedTokens; 184 addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens); 185 return isUnsatisfiable(std::move(Constraints)); 186 } 187 188 bool DataflowAnalysisContext::equivalentBoolValues(BoolValue &Val1, 189 BoolValue &Val2) { 190 llvm::DenseSet<BoolValue *> Constraints = { 191 &getOrCreateNegation(getOrCreateIff(Val1, Val2))}; 192 return isUnsatisfiable(Constraints); 193 } 194 195 void DataflowAnalysisContext::addTransitiveFlowConditionConstraints( 196 AtomicBoolValue &Token, llvm::DenseSet<BoolValue *> &Constraints, 197 llvm::DenseSet<AtomicBoolValue *> &VisitedTokens) { 198 auto Res = VisitedTokens.insert(&Token); 199 if (!Res.second) 200 return; 201 202 auto ConstraintsIT = FlowConditionConstraints.find(&Token); 203 if (ConstraintsIT == FlowConditionConstraints.end()) { 204 Constraints.insert(&Token); 205 } else { 206 // Bind flow condition token via `iff` to its set of constraints: 207 // FC <=> (C1 ^ C2 ^ ...), where Ci are constraints 208 Constraints.insert(&getOrCreateIff(Token, *ConstraintsIT->second)); 209 } 210 211 auto DepsIT = FlowConditionDeps.find(&Token); 212 if (DepsIT != FlowConditionDeps.end()) { 213 for (AtomicBoolValue *DepToken : DepsIT->second) { 214 addTransitiveFlowConditionConstraints(*DepToken, Constraints, 215 VisitedTokens); 216 } 217 } 218 } 219 220 BoolValue &DataflowAnalysisContext::substituteBoolValue( 221 BoolValue &Val, 222 llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) { 223 auto IT = SubstitutionsCache.find(&Val); 224 if (IT != SubstitutionsCache.end()) { 225 // Return memoized result of substituting this boolean value. 226 return *IT->second; 227 } 228 229 // Handle substitution on the boolean value (and its subvalues), saving the 230 // result into `SubstitutionsCache`. 231 BoolValue *Result; 232 switch (Val.getKind()) { 233 case Value::Kind::AtomicBool: { 234 Result = &Val; 235 break; 236 } 237 case Value::Kind::Negation: { 238 auto &Negation = *cast<NegationValue>(&Val); 239 auto &Sub = substituteBoolValue(Negation.getSubVal(), SubstitutionsCache); 240 Result = &getOrCreateNegation(Sub); 241 break; 242 } 243 case Value::Kind::Disjunction: { 244 auto &Disjunct = *cast<DisjunctionValue>(&Val); 245 auto &LeftSub = 246 substituteBoolValue(Disjunct.getLeftSubValue(), SubstitutionsCache); 247 auto &RightSub = 248 substituteBoolValue(Disjunct.getRightSubValue(), SubstitutionsCache); 249 Result = &getOrCreateDisjunction(LeftSub, RightSub); 250 break; 251 } 252 case Value::Kind::Conjunction: { 253 auto &Conjunct = *cast<ConjunctionValue>(&Val); 254 auto &LeftSub = 255 substituteBoolValue(Conjunct.getLeftSubValue(), SubstitutionsCache); 256 auto &RightSub = 257 substituteBoolValue(Conjunct.getRightSubValue(), SubstitutionsCache); 258 Result = &getOrCreateConjunction(LeftSub, RightSub); 259 break; 260 } 261 default: 262 llvm_unreachable("Unhandled Value Kind"); 263 } 264 SubstitutionsCache[&Val] = Result; 265 return *Result; 266 } 267 268 BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowCondition( 269 AtomicBoolValue &Token, 270 llvm::DenseMap<AtomicBoolValue *, BoolValue *> Substitutions) { 271 assert( 272 Substitutions.find(&getBoolLiteralValue(true)) == Substitutions.end() && 273 Substitutions.find(&getBoolLiteralValue(false)) == Substitutions.end() && 274 "Do not substitute true/false boolean literals"); 275 llvm::DenseMap<BoolValue *, BoolValue *> SubstitutionsCache( 276 Substitutions.begin(), Substitutions.end()); 277 return buildAndSubstituteFlowConditionWithCache(Token, SubstitutionsCache); 278 } 279 280 BoolValue &DataflowAnalysisContext::buildAndSubstituteFlowConditionWithCache( 281 AtomicBoolValue &Token, 282 llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache) { 283 auto ConstraintsIT = FlowConditionConstraints.find(&Token); 284 if (ConstraintsIT == FlowConditionConstraints.end()) { 285 return getBoolLiteralValue(true); 286 } 287 auto DepsIT = FlowConditionDeps.find(&Token); 288 if (DepsIT != FlowConditionDeps.end()) { 289 for (AtomicBoolValue *DepToken : DepsIT->second) { 290 auto &NewDep = buildAndSubstituteFlowConditionWithCache( 291 *DepToken, SubstitutionsCache); 292 SubstitutionsCache[DepToken] = &NewDep; 293 } 294 } 295 return substituteBoolValue(*ConstraintsIT->second, SubstitutionsCache); 296 } 297 298 void DataflowAnalysisContext::dumpFlowCondition(AtomicBoolValue &Token) { 299 llvm::DenseSet<BoolValue *> Constraints = {&Token}; 300 llvm::DenseSet<AtomicBoolValue *> VisitedTokens; 301 addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens); 302 303 llvm::DenseMap<const AtomicBoolValue *, std::string> AtomNames = { 304 {&getBoolLiteralValue(false), "False"}, 305 {&getBoolLiteralValue(true), "True"}}; 306 llvm::dbgs() << debugString(Constraints, AtomNames); 307 } 308 309 } // namespace dataflow 310 } // namespace clang 311 312 using namespace clang; 313 314 const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) { 315 const Expr *Current = &E; 316 if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) { 317 Current = EWC->getSubExpr(); 318 assert(Current != nullptr); 319 } 320 Current = Current->IgnoreParens(); 321 assert(Current != nullptr); 322 return *Current; 323 } 324 325 const Stmt &clang::dataflow::ignoreCFGOmittedNodes(const Stmt &S) { 326 if (auto *E = dyn_cast<Expr>(&S)) 327 return ignoreCFGOmittedNodes(*E); 328 return S; 329 } 330 331 // FIXME: Does not precisely handle non-virtual diamond inheritance. A single 332 // field decl will be modeled for all instances of the inherited field. 333 static void 334 getFieldsFromClassHierarchy(QualType Type, 335 llvm::DenseSet<const FieldDecl *> &Fields) { 336 if (Type->isIncompleteType() || Type->isDependentType() || 337 !Type->isRecordType()) 338 return; 339 340 for (const FieldDecl *Field : Type->getAsRecordDecl()->fields()) 341 Fields.insert(Field); 342 if (auto *CXXRecord = Type->getAsCXXRecordDecl()) 343 for (const CXXBaseSpecifier &Base : CXXRecord->bases()) 344 getFieldsFromClassHierarchy(Base.getType(), Fields); 345 } 346 347 /// Gets the set of all fields in the type. 348 llvm::DenseSet<const FieldDecl *> 349 clang::dataflow::getObjectFields(QualType Type) { 350 llvm::DenseSet<const FieldDecl *> Fields; 351 getFieldsFromClassHierarchy(Type, Fields); 352 return Fields; 353 } 354