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