| 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/Expr.h" |
| 19 | #include "clang/AST/ExprCXX.h" |
| 20 | #include "clang/AST/Stmt.h" |
| 21 | #include "clang/AST/Type.h" |
| 22 | #include "clang/Analysis/FlowSensitive/ASTOps.h" |
| 23 | #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h" |
| 24 | #include "clang/Analysis/FlowSensitive/DataflowLattice.h" |
| 25 | #include "clang/Analysis/FlowSensitive/Formula.h" |
| 26 | #include "clang/Analysis/FlowSensitive/StorageLocation.h" |
| 27 | #include "clang/Analysis/FlowSensitive/Value.h" |
| 28 | #include "clang/Basic/LLVM.h" |
| 29 | #include "llvm/ADT/DenseMap.h" |
| 30 | #include "llvm/ADT/DenseSet.h" |
| 31 | #include "llvm/ADT/MapVector.h" |
| 32 | #include "llvm/ADT/STLExtras.h" |
| 33 | #include "llvm/ADT/ScopeExit.h" |
| 34 | #include "llvm/ADT/SetVector.h" |
| 35 | #include "llvm/ADT/SmallVector.h" |
| 36 | #include "llvm/Support/ErrorHandling.h" |
| 37 | #include <cassert> |
| 38 | #include <memory> |
| 39 | #include <optional> |
| 40 | #include <stack> |
| 41 | #include <utility> |
| 42 | |
| 43 | #define DEBUG_TYPE "dataflow" |
| 44 | |
| 45 | namespace clang { |
| 46 | namespace dataflow { |
| 47 | |
| 48 | namespace { |
| 49 | |
| 50 | class SimpleBoolModel final : public Environment::BoolModel { |
| 51 | public: |
| 52 | SimpleBoolModel() : BoolModel(BoolModelKind::Simple) {} |
| 53 | |
| 54 | static bool classof(const BoolModel *M) { |
| 55 | return M->getKind() == BoolModelKind::Simple; |
| 56 | } |
| 57 | |
| 58 | std::unique_ptr<BoolModel> clone() const override { |
| 59 | return std::make_unique<SimpleBoolModel>(args: *this); |
| 60 | } |
| 61 | |
| 62 | void onFork() override {} |
| 63 | |
| 64 | void assume(const Formula &F) override { |
| 65 | if (HasContradiction) |
| 66 | return; |
| 67 | unsigned PrevSize = AtomToVal.size(); |
| 68 | // Given that F is assumed true, see if we can force the assignment |
| 69 | // of any atoms and ultimately reduce F to a literal (if possible). |
| 70 | // For example, if F is `A && B`, we will force `A` and `B` to be true. |
| 71 | // If F is `A || B`, we will only force an assignment if one of A or B is |
| 72 | // already known to be false. |
| 73 | assumeFormula(/*AssumedVal=*/true, F); |
| 74 | if (HasContradiction) |
| 75 | return; |
| 76 | |
| 77 | if (std::optional<bool> Val = getLiteralValue(F)) { |
| 78 | if (!*Val) { |
| 79 | HasContradiction = true; |
| 80 | return; |
| 81 | } |
| 82 | } else { |
| 83 | // Retain `F` in `AssumedFormulas` only if it has not yet been reduced to |
| 84 | // a known truth value in `AtomToVal` (e.g., `A || B` or `A == B` where |
| 85 | // neither side is known yet). |
| 86 | // |
| 87 | // - Why save unresolved formulas: a compound formula (like |
| 88 | // `EqVal => (LHS == RHS)` from a comparison expression) is often |
| 89 | // assumed while its atoms are still unknown; when we later follow a |
| 90 | // branch that fixes one of those atoms, the propagation loop below can |
| 91 | // reduce the saved formula to concrete `AtomToVal` entries. |
| 92 | // |
| 93 | // - Skipping formulas that already evaluate to `true` avoids bloating |
| 94 | // `AssumedFormulas` with single-atom and conjunctive assumptions that |
| 95 | // are already fully represented by `AtomToVal` (though it also drops |
| 96 | // disjunctive formulas that were reduced using a branch-local atom, |
| 97 | // such as on the RHS of a short-circuit `&&` or `||`). |
| 98 | // TODO: We may want to retain some disjunctive formulas, but would need |
| 99 | // to profile and see how much it helps vs how much it costs. |
| 100 | AssumedFormulas.insert(X: &F); |
| 101 | } |
| 102 | |
| 103 | if (AtomToVal.size() == PrevSize) |
| 104 | return; |
| 105 | |
| 106 | // Propagate newly learned atom values through any pending assumed formulas. |
| 107 | // Note: Do not remove formulas from `AssumedFormulas` when they evaluate to |
| 108 | // `true` in a branch, because the atoms that satisfied them may be |
| 109 | // branch-local and discarded at a subsequent `join`, where the formula |
| 110 | // itself still holds on both branches. |
| 111 | bool Changed = true; |
| 112 | while (Changed) { |
| 113 | Changed = false; |
| 114 | for (const Formula *Pending : AssumedFormulas) { |
| 115 | unsigned Before = AtomToVal.size(); |
| 116 | assumeFormula(/*AssumedVal=*/true, F: *Pending); |
| 117 | if (HasContradiction) |
| 118 | return; |
| 119 | if (auto V = getLiteralValue(F: *Pending); V.has_value() && *V == false) { |
| 120 | HasContradiction = true; |
| 121 | return; |
| 122 | } |
| 123 | if (AtomToVal.size() > Before) |
| 124 | Changed = true; |
| 125 | } |
| 126 | } |
| 127 | } |
| 128 | |
| 129 | bool proves(const Formula &F) const override { |
| 130 | if (HasContradiction) |
| 131 | return true; |
| 132 | auto V = getLiteralValue(F); |
| 133 | return V.value_or(u: false); |
| 134 | } |
| 135 | |
| 136 | bool allows(const Formula &F) const override { |
| 137 | if (HasContradiction) |
| 138 | return false; |
| 139 | auto V = getLiteralValue(F); |
| 140 | // We are conservative in the negative direction: if we can't determine the |
| 141 | // value, assume it is allowed. |
| 142 | return V.value_or(u: true); |
| 143 | } |
| 144 | |
| 145 | BoolValue &joinBoolValues(BoolValue &Val1, const BoolModel &Model1, |
| 146 | BoolValue &Val2, const BoolModel &Model2, |
| 147 | Environment &JoinedEnv) override { |
| 148 | const auto &S1 = cast<SimpleBoolModel>(Val: Model1); |
| 149 | const auto &S2 = cast<SimpleBoolModel>(Val: Model2); |
| 150 | if (S1.HasContradiction) |
| 151 | return Val2; |
| 152 | if (S2.HasContradiction) |
| 153 | return Val1; |
| 154 | if (auto V1 = S1.getLiteralValue(F: Val1.formula()); |
| 155 | V1.has_value() && V1 == S2.getLiteralValue(F: Val2.formula())) |
| 156 | return JoinedEnv.getBoolLiteralValue(Value: *V1); |
| 157 | return JoinedEnv.makeAtomicBoolValue(); |
| 158 | } |
| 159 | |
| 160 | void join(const BoolModel &ModelA, const BoolModel &ModelB) override { |
| 161 | const auto &SA = cast<SimpleBoolModel>(Val: ModelA); |
| 162 | const auto &SB = cast<SimpleBoolModel>(Val: ModelB); |
| 163 | AtomToVal.clear(); |
| 164 | AssumedFormulas.clear(); |
| 165 | HasContradiction = false; |
| 166 | |
| 167 | if (SA.HasContradiction && SB.HasContradiction) { |
| 168 | HasContradiction = true; |
| 169 | } else if (SA.HasContradiction) { |
| 170 | AtomToVal = SB.AtomToVal; |
| 171 | AssumedFormulas = SB.AssumedFormulas; |
| 172 | } else if (SB.HasContradiction) { |
| 173 | AtomToVal = SA.AtomToVal; |
| 174 | AssumedFormulas = SA.AssumedFormulas; |
| 175 | } else { |
| 176 | // Intersect the AtomToVal maps. |
| 177 | for (const auto &[A, V] : SA.AtomToVal) { |
| 178 | auto It = SB.AtomToVal.find(Val: A); |
| 179 | if (It != SB.AtomToVal.end() && V == It->second) |
| 180 | AtomToVal.insert(KV: {A, V}); |
| 181 | } |
| 182 | |
| 183 | // Keep assumed formulas that hold on both branches (and are not already |
| 184 | // reduced to `true` by the joined `AtomToVal`): either because both |
| 185 | // environments still carry `F` as an unresolved formula, or because one |
| 186 | // branch carries `F` and the other branch's `AtomToVal` assignments |
| 187 | // already prove `F`. Any branch-local formulas not proved by the other |
| 188 | // branch are dropped here, which shrinks `AssumedFormulas` at joins. |
| 189 | for (const Formula *F : SA.AssumedFormulas) { |
| 190 | if (!proves(F: *F) && (SB.AssumedFormulas.contains(key: F) || SB.proves(F: *F))) |
| 191 | AssumedFormulas.insert(X: F); |
| 192 | } |
| 193 | for (const Formula *F : SB.AssumedFormulas) { |
| 194 | if (!proves(F: *F) && SA.proves(F: *F)) |
| 195 | AssumedFormulas.insert(X: F); |
| 196 | } |
| 197 | } |
| 198 | } |
| 199 | |
| 200 | LatticeEffect widen(const BoolModel &PrevModel) override { |
| 201 | const auto &PrevSimple = cast<SimpleBoolModel>(Val: PrevModel); |
| 202 | SimpleBoolModel Widened; |
| 203 | Widened.join(ModelA: *this, ModelB: PrevSimple); |
| 204 | LatticeEffect Effect = Widened.isEquivalentTo(Other: PrevSimple) |
| 205 | ? LatticeEffect::Unchanged |
| 206 | : LatticeEffect::Changed; |
| 207 | *this = std::move(Widened); |
| 208 | return Effect; |
| 209 | } |
| 210 | |
| 211 | bool isEquivalentTo(const BoolModel &Other) const override { |
| 212 | const auto &OtherSimple = cast<SimpleBoolModel>(Val: Other); |
| 213 | if (HasContradiction != OtherSimple.HasContradiction) |
| 214 | return false; |
| 215 | if (HasContradiction) |
| 216 | return true; |
| 217 | return AtomToVal == OtherSimple.AtomToVal && |
| 218 | AssumedFormulas.size() == OtherSimple.AssumedFormulas.size() && |
| 219 | // SetVector::operator== compares insertion order, so check set |
| 220 | // membership. |
| 221 | llvm::all_of(Range: AssumedFormulas, P: [&](const Formula *F) { |
| 222 | return OtherSimple.AssumedFormulas.contains(key: F); |
| 223 | }); |
| 224 | } |
| 225 | |
| 226 | Atom getFlowConditionToken() const override { |
| 227 | llvm_unreachable( |
| 228 | "getFlowConditionToken() is only supported in SatBoolModel" ); |
| 229 | } |
| 230 | |
| 231 | void dump(raw_ostream &OS) const override { |
| 232 | OS << "SimpleBoolModel:\n" ; |
| 233 | OS << " HasContradiction: " << HasContradiction << "\n" ; |
| 234 | OS << " AtomToVal:\n" ; |
| 235 | SmallVector<std::pair<Atom, bool>> SortedAtomToVal(AtomToVal.begin(), |
| 236 | AtomToVal.end()); |
| 237 | llvm::sort(C&: SortedAtomToVal, Comp: llvm::less_first()); |
| 238 | for (auto [A, V] : SortedAtomToVal) |
| 239 | OS << " " << A << " = " << (V ? "true" : "false" ) << "\n" ; |
| 240 | OS << " AssumedFormulas:\n" ; |
| 241 | for (const Formula *F : AssumedFormulas) |
| 242 | OS << " " << *F << "\n" ; |
| 243 | } |
| 244 | |
| 245 | private: |
| 246 | std::optional<bool> getAtomValue(Atom A) const { |
| 247 | auto It = AtomToVal.find(Val: A); |
| 248 | if (It == AtomToVal.end()) |
| 249 | return std::nullopt; |
| 250 | return It->second; |
| 251 | } |
| 252 | |
| 253 | std::optional<bool> getLiteralValue(const Formula &F) const { |
| 254 | switch (F.kind()) { |
| 255 | case Formula::AtomRef: |
| 256 | return getAtomValue(A: F.getAtom()); |
| 257 | case Formula::Literal: |
| 258 | return F.literal(); |
| 259 | case Formula::Not: { |
| 260 | ArrayRef<const Formula *> Operands = F.operands(); |
| 261 | assert(Operands.size() == 1); |
| 262 | if (std::optional<bool> V = getLiteralValue(F: *Operands[0])) |
| 263 | return !*V; |
| 264 | return std::nullopt; |
| 265 | } |
| 266 | case Formula::And: { |
| 267 | ArrayRef<const Formula *> Operands = F.operands(); |
| 268 | assert(Operands.size() == 2); |
| 269 | auto &LHS = *Operands[0]; |
| 270 | auto &RHS = *Operands[1]; |
| 271 | if (std::optional<bool> Left = getLiteralValue(F: LHS)) |
| 272 | return !*Left ? Left : getLiteralValue(F: RHS); |
| 273 | if (std::optional<bool> Right = getLiteralValue(F: RHS); |
| 274 | Right.has_value() && *Right == false) |
| 275 | return Right; |
| 276 | return std::nullopt; |
| 277 | } |
| 278 | case Formula::Or: { |
| 279 | ArrayRef<const Formula *> Operands = F.operands(); |
| 280 | assert(Operands.size() == 2); |
| 281 | auto &LHS = *Operands[0]; |
| 282 | auto &RHS = *Operands[1]; |
| 283 | if (std::optional<bool> Left = getLiteralValue(F: LHS)) |
| 284 | return *Left ? Left : getLiteralValue(F: RHS); |
| 285 | if (std::optional<bool> Right = getLiteralValue(F: RHS); |
| 286 | Right.has_value() && *Right == true) |
| 287 | return Right; |
| 288 | return std::nullopt; |
| 289 | } |
| 290 | case Formula::Implies: { |
| 291 | ArrayRef<const Formula *> Operands = F.operands(); |
| 292 | assert(Operands.size() == 2); |
| 293 | auto &LHS = *Operands[0]; |
| 294 | auto &RHS = *Operands[1]; |
| 295 | if (std::optional<bool> Left = getLiteralValue(F: LHS)) |
| 296 | return !*Left ? true : getLiteralValue(F: RHS); |
| 297 | if (std::optional<bool> Right = getLiteralValue(F: RHS); |
| 298 | Right.has_value() && *Right == true) |
| 299 | return true; |
| 300 | return std::nullopt; |
| 301 | } |
| 302 | case Formula::Equal: { |
| 303 | ArrayRef<const Formula *> Operands = F.operands(); |
| 304 | assert(Operands.size() == 2); |
| 305 | auto &LHS = *Operands[0]; |
| 306 | auto &RHS = *Operands[1]; |
| 307 | // If the formula is of the form `A == A`, then we can simplify to |
| 308 | // true, without needing to know A is set to a literal value. |
| 309 | if (&LHS == &RHS) |
| 310 | return true; |
| 311 | // Similarly, if the formula is of the form `A == !A` (or !A == A), |
| 312 | // then we can simplify to false. |
| 313 | // We should consider lifting such simplification with identities into a |
| 314 | // a separate function (there are more cases, e.g., `A OR !A` is true), |
| 315 | // while keeping this function focused on cases where the operands are |
| 316 | // literal values. |
| 317 | if ((LHS.kind() == Formula::Not && LHS.operands()[0] == &RHS) || |
| 318 | (RHS.kind() == Formula::Not && RHS.operands()[0] == &LHS)) |
| 319 | return false; |
| 320 | auto V_L = getLiteralValue(F: LHS); |
| 321 | if (!V_L.has_value()) |
| 322 | return std::nullopt; |
| 323 | auto V_R = getLiteralValue(F: RHS); |
| 324 | if (!V_R.has_value()) |
| 325 | return std::nullopt; |
| 326 | return *V_L == *V_R; |
| 327 | } |
| 328 | } |
| 329 | llvm_unreachable("fully covered switch" ); |
| 330 | } |
| 331 | |
| 332 | // Updates atom assignments under the assumption that subformula `F` |
| 333 | // evaluates to `AssumedVal` (i.e., `F == AssumedVal`). |
| 334 | // |
| 335 | // Top-level `assume(F)` starts with `AssumedVal = true`, and recursive |
| 336 | // calls flip `AssumedVal` when traversing negations (`Formula::Not`) or |
| 337 | // comparisons (`Formula::Equal`) against known boolean values. |
| 338 | // |
| 339 | // For example: |
| 340 | // - for `assume(!A)`, then `A` must be `false` |
| 341 | // - for `assume(A && B)`, then both `A` and `B` must be `true`. |
| 342 | void assumeFormula(bool AssumedVal, const Formula &F) { |
| 343 | if (HasContradiction) |
| 344 | return; |
| 345 | switch (F.kind()) { |
| 346 | case Formula::AtomRef: { |
| 347 | // Base case: `F` is a single atom, so assuming `F == AssumedVal` directly |
| 348 | // binds this atom to `AssumedVal`, or marks the environment as having a |
| 349 | // contradiction if the atom was already bound to the opposite value. |
| 350 | auto [It, Inserted] = AtomToVal.try_emplace(Key: F.getAtom(), Args&: AssumedVal); |
| 351 | if (!Inserted && It->second != AssumedVal) |
| 352 | HasContradiction = true; |
| 353 | break; |
| 354 | } |
| 355 | case Formula::Literal: |
| 356 | if (F.literal() != AssumedVal) |
| 357 | HasContradiction = true; |
| 358 | break; |
| 359 | case Formula::Not: { |
| 360 | // Assuming `(!Operand) == AssumedVal` is equivalent to assuming |
| 361 | // `Operand == !AssumedVal`. |
| 362 | ArrayRef<const Formula *> Operands = F.operands(); |
| 363 | assert(Operands.size() == 1); |
| 364 | assumeFormula(AssumedVal: !AssumedVal, F: *Operands[0]); |
| 365 | break; |
| 366 | } |
| 367 | case Formula::And: { |
| 368 | // - If `AssumedVal == true` (`LHS && RHS`), both operands must be `true`. |
| 369 | // - If `AssumedVal == false` (`!(LHS && RHS)` <=> `!LHS || !RHS`), at |
| 370 | // least one operand is `false`; if one operand is already known `true`, |
| 371 | // the other must be `false`. |
| 372 | ArrayRef<const Formula *> Operands = F.operands(); |
| 373 | assert(Operands.size() == 2); |
| 374 | auto &LHS = *Operands[0]; |
| 375 | auto &RHS = *Operands[1]; |
| 376 | if (AssumedVal == true) { |
| 377 | assumeFormula(AssumedVal: true, F: LHS); |
| 378 | assumeFormula(AssumedVal: true, F: RHS); |
| 379 | } else { |
| 380 | if (auto V = getLiteralValue(F: LHS); V.has_value() && *V == true) |
| 381 | assumeFormula(AssumedVal: false, F: RHS); |
| 382 | else if (auto V = getLiteralValue(F: RHS); V.has_value() && *V == true) |
| 383 | assumeFormula(AssumedVal: false, F: LHS); |
| 384 | } |
| 385 | break; |
| 386 | } |
| 387 | case Formula::Or: { |
| 388 | // - If `AssumedVal == false` (`!(LHS || RHS)` <=> `!LHS && !RHS`), both |
| 389 | // operands must be `false`. |
| 390 | // - If `AssumedVal == true` (`LHS || RHS`), at least one operand is |
| 391 | // `true`; if one operand is already known `false`, the other must be |
| 392 | // `true`. |
| 393 | ArrayRef<const Formula *> Operands = F.operands(); |
| 394 | assert(Operands.size() == 2); |
| 395 | auto &LHS = *Operands[0]; |
| 396 | auto &RHS = *Operands[1]; |
| 397 | if (AssumedVal == false) { |
| 398 | assumeFormula(AssumedVal: false, F: LHS); |
| 399 | assumeFormula(AssumedVal: false, F: RHS); |
| 400 | } else { |
| 401 | if (auto V = getLiteralValue(F: LHS); V.has_value() && *V == false) |
| 402 | assumeFormula(AssumedVal: true, F: RHS); |
| 403 | else if (auto V = getLiteralValue(F: RHS); V.has_value() && *V == false) |
| 404 | assumeFormula(AssumedVal: true, F: LHS); |
| 405 | } |
| 406 | break; |
| 407 | } |
| 408 | case Formula::Implies: { |
| 409 | // `LHS => RHS` is equivalent to `!LHS || RHS`. |
| 410 | // - If `AssumedVal == false` (`!(LHS => RHS)`), then `LHS` must be `true` |
| 411 | // and `RHS` must be `false`. |
| 412 | // - If `AssumedVal == true` (`LHS => RHS`): |
| 413 | // - Modus ponens: if `LHS` is known `true`, then `RHS` must be `true`. |
| 414 | // - Modus tollens: if `RHS` is known `false`, then `LHS` must be |
| 415 | // `false`. |
| 416 | ArrayRef<const Formula *> Operands = F.operands(); |
| 417 | assert(Operands.size() == 2); |
| 418 | auto &LHS = *Operands[0]; |
| 419 | auto &RHS = *Operands[1]; |
| 420 | if (AssumedVal == false) { |
| 421 | assumeFormula(AssumedVal: true, F: LHS); |
| 422 | assumeFormula(AssumedVal: false, F: RHS); |
| 423 | } else { |
| 424 | if (auto V = getLiteralValue(F: LHS); V.has_value() && *V == true) |
| 425 | assumeFormula(AssumedVal: true, F: RHS); |
| 426 | else if (auto V = getLiteralValue(F: RHS); V.has_value() && *V == false) |
| 427 | assumeFormula(AssumedVal: false, F: LHS); |
| 428 | } |
| 429 | break; |
| 430 | } |
| 431 | case Formula::Equal: { |
| 432 | // Assuming `(LHS == RHS) == AssumedVal`: if one side already has a known |
| 433 | // truth value `*V`, then the other side must evaluate to |
| 434 | // `(AssumedVal == *V)`. |
| 435 | ArrayRef<const Formula *> Operands = F.operands(); |
| 436 | assert(Operands.size() == 2); |
| 437 | auto &LHS = *Operands[0]; |
| 438 | auto &RHS = *Operands[1]; |
| 439 | if (auto V = getLiteralValue(F: LHS)) { |
| 440 | assumeFormula(AssumedVal: AssumedVal == *V, F: RHS); |
| 441 | } else if (auto V = getLiteralValue(F: RHS)) { |
| 442 | assumeFormula(AssumedVal: AssumedVal == *V, F: LHS); |
| 443 | } |
| 444 | break; |
| 445 | } |
| 446 | } |
| 447 | } |
| 448 | |
| 449 | llvm::DenseMap<Atom, bool> AtomToVal; |
| 450 | llvm::SmallSetVector<const Formula *, 4> AssumedFormulas; |
| 451 | bool HasContradiction = false; |
| 452 | }; |
| 453 | |
| 454 | class SatBoolModel final : public Environment::BoolModel { |
| 455 | public: |
| 456 | SatBoolModel(DataflowAnalysisContext &DACtx, Atom FlowConditionToken) |
| 457 | : BoolModel(BoolModelKind::SAT), DACtx(DACtx), |
| 458 | FlowConditionToken(FlowConditionToken) {} |
| 459 | |
| 460 | explicit SatBoolModel(DataflowAnalysisContext &DACtx) |
| 461 | : SatBoolModel(DACtx, DACtx.arena().makeFlowConditionToken()) {} |
| 462 | |
| 463 | static bool classof(const BoolModel *M) { |
| 464 | return M->getKind() == BoolModelKind::SAT; |
| 465 | } |
| 466 | |
| 467 | std::unique_ptr<BoolModel> clone() const override { |
| 468 | return std::make_unique<SatBoolModel>(args: *this); |
| 469 | } |
| 470 | |
| 471 | void onFork() override { |
| 472 | FlowConditionToken = DACtx.forkFlowCondition(Token: FlowConditionToken); |
| 473 | } |
| 474 | |
| 475 | void assume(const Formula &F) override { |
| 476 | DACtx.addFlowConditionConstraint(Token: FlowConditionToken, Constraint: F); |
| 477 | } |
| 478 | |
| 479 | bool proves(const Formula &F) const override { |
| 480 | return DACtx.flowConditionImplies(Token: FlowConditionToken, F); |
| 481 | } |
| 482 | |
| 483 | bool allows(const Formula &F) const override { |
| 484 | return DACtx.flowConditionAllows(Token: FlowConditionToken, F); |
| 485 | } |
| 486 | |
| 487 | BoolValue &joinBoolValues(BoolValue &Val1, const BoolModel &Model1, |
| 488 | BoolValue &Val2, const BoolModel &Model2, |
| 489 | Environment &JoinedEnv) override { |
| 490 | const auto &Sat1 = cast<SatBoolModel>(Val: Model1); |
| 491 | const auto &Sat2 = cast<SatBoolModel>(Val: Model2); |
| 492 | auto &A = JoinedEnv.arena(); |
| 493 | auto &JoinedVal = A.makeAtomRef(A: A.makeAtom()); |
| 494 | JoinedEnv.assume( |
| 495 | A.makeOr(LHS: A.makeAnd(LHS: A.makeAtomRef(A: Sat1.getFlowConditionToken()), |
| 496 | RHS: A.makeEquals(LHS: JoinedVal, RHS: Val1.formula())), |
| 497 | RHS: A.makeAnd(LHS: A.makeAtomRef(A: Sat2.getFlowConditionToken()), |
| 498 | RHS: A.makeEquals(LHS: JoinedVal, RHS: Val2.formula())))); |
| 499 | return A.makeBoolValue(JoinedVal); |
| 500 | } |
| 501 | |
| 502 | void join(const BoolModel &ModelA, const BoolModel &ModelB) override { |
| 503 | const auto &SatA = cast<SatBoolModel>(Val: ModelA); |
| 504 | const auto &SatB = cast<SatBoolModel>(Val: ModelB); |
| 505 | // FIXME: update join to detect backedges and simplify the flow condition |
| 506 | // accordingly. |
| 507 | FlowConditionToken = DACtx.joinFlowConditions(FirstToken: SatA.FlowConditionToken, |
| 508 | SecondToken: SatB.FlowConditionToken); |
| 509 | } |
| 510 | |
| 511 | LatticeEffect widen(const BoolModel &PrevModel) override { |
| 512 | (void)cast<SatBoolModel>(Val: PrevModel); |
| 513 | return LatticeEffect::Unchanged; |
| 514 | } |
| 515 | |
| 516 | bool isEquivalentTo(const BoolModel &Other) const override { |
| 517 | (void)cast<SatBoolModel>(Val: Other); |
| 518 | return true; |
| 519 | } |
| 520 | |
| 521 | Atom getFlowConditionToken() const override { return FlowConditionToken; } |
| 522 | |
| 523 | void dump(raw_ostream &OS) const override { |
| 524 | DACtx.dumpFlowCondition(Token: FlowConditionToken, OS); |
| 525 | } |
| 526 | |
| 527 | private: |
| 528 | DataflowAnalysisContext &DACtx; |
| 529 | Atom FlowConditionToken; |
| 530 | }; |
| 531 | |
| 532 | } // namespace |
| 533 | |
| 534 | // FIXME: convert these to parameters of the analysis or environment. Current |
| 535 | // settings have been experimentaly validated, but only for a particular |
| 536 | // analysis. |
| 537 | static constexpr int MaxCompositeValueDepth = 3; |
| 538 | static constexpr int MaxCompositeValueSize = 1000; |
| 539 | |
| 540 | /// Returns a map consisting of key-value entries that are present in both maps. |
| 541 | static llvm::DenseMap<const ValueDecl *, StorageLocation *> intersectDeclToLoc( |
| 542 | const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc1, |
| 543 | const llvm::DenseMap<const ValueDecl *, StorageLocation *> &DeclToLoc2) { |
| 544 | llvm::DenseMap<const ValueDecl *, StorageLocation *> Result; |
| 545 | for (auto &Entry : DeclToLoc1) { |
| 546 | auto It = DeclToLoc2.find(Val: Entry.first); |
| 547 | if (It != DeclToLoc2.end() && Entry.second == It->second) |
| 548 | Result.insert(KV: {Entry.first, Entry.second}); |
| 549 | } |
| 550 | return Result; |
| 551 | } |
| 552 | |
| 553 | // Performs a join on either `ExprToLoc` or `ExprToVal`. |
| 554 | // The maps must be consistent in the sense that any entries for the same |
| 555 | // expression must map to the same location / value. This is the case if we are |
| 556 | // performing a join for control flow within a full-expression (which is the |
| 557 | // only case when this function should be used). |
| 558 | template <typename MapT> |
| 559 | static MapT joinExprMaps(const MapT &Map1, const MapT &Map2) { |
| 560 | MapT Result = Map1; |
| 561 | |
| 562 | for (const auto &Entry : Map2) { |
| 563 | [[maybe_unused]] auto [It, Inserted] = Result.insert(Entry); |
| 564 | // If there was an existing entry, its value should be the same as for the |
| 565 | // entry we were trying to insert. |
| 566 | assert(It->second == Entry.second); |
| 567 | } |
| 568 | |
| 569 | return Result; |
| 570 | } |
| 571 | |
| 572 | // Whether to consider equivalent two values with an unknown relation. |
| 573 | // |
| 574 | // FIXME: this function is a hack enabling unsoundness to support |
| 575 | // convergence. Once we have widening support for the reference/pointer and |
| 576 | // struct built-in models, this should be unconditionally `false` (and inlined |
| 577 | // as such at its call sites). |
| 578 | static bool equateUnknownValues(Value::Kind K) { |
| 579 | switch (K) { |
| 580 | case Value::Kind::Integer: |
| 581 | case Value::Kind::Pointer: |
| 582 | return true; |
| 583 | default: |
| 584 | return false; |
| 585 | } |
| 586 | } |
| 587 | |
| 588 | static bool compareDistinctValues(QualType Type, Value &Val1, |
| 589 | const Environment &Env1, Value &Val2, |
| 590 | const Environment &Env2, |
| 591 | Environment::ValueModel &Model) { |
| 592 | // Note: Potentially costly, but, for booleans, we could check whether both |
| 593 | // can be proven equivalent in their respective environments. |
| 594 | |
| 595 | // FIXME: move the reference/pointers logic from `areEquivalentValues` to here |
| 596 | // and implement separate, join/widen specific handling for |
| 597 | // reference/pointers. |
| 598 | switch (Model.compare(Type, Val1, Env1, Val2, Env2)) { |
| 599 | case ComparisonResult::Same: |
| 600 | return true; |
| 601 | case ComparisonResult::Different: |
| 602 | return false; |
| 603 | case ComparisonResult::Unknown: |
| 604 | return equateUnknownValues(K: Val1.getKind()); |
| 605 | } |
| 606 | llvm_unreachable("All cases covered in switch" ); |
| 607 | } |
| 608 | |
| 609 | /// Attempts to join distinct values `Val1` and `Val2` in `Env1` and `Env2`, |
| 610 | /// respectively, of the same type `Type`. Joining generally produces a single |
| 611 | /// value that (soundly) approximates the two inputs, although the actual |
| 612 | /// meaning depends on `Model`. |
| 613 | static Value *joinDistinctValues(QualType Type, Value &Val1, |
| 614 | const Environment &Env1, Value &Val2, |
| 615 | const Environment &Env2, |
| 616 | Environment &JoinedEnv, |
| 617 | Environment::ValueModel &Model) { |
| 618 | // Join distinct boolean values preserving information about the constraints |
| 619 | // in the respective path conditions. |
| 620 | if (isa<BoolValue>(Val: &Val1) && isa<BoolValue>(Val: &Val2)) { |
| 621 | // FIXME: Checking both values should be unnecessary, since they should have |
| 622 | // a consistent shape. However, right now we can end up with BoolValue's in |
| 623 | // integer-typed variables due to our incorrect handling of |
| 624 | // boolean-to-integer casts (we just propagate the BoolValue to the result |
| 625 | // of the cast). So, a join can encounter an integer in one branch but a |
| 626 | // bool in the other. |
| 627 | // For example: |
| 628 | // ``` |
| 629 | // std::optional<bool> o; |
| 630 | // int x; |
| 631 | // if (o.has_value()) |
| 632 | // x = o.value(); |
| 633 | // ``` |
| 634 | return &JoinedEnv.joinBoolValues(Val1&: cast<BoolValue>(Val&: Val1), Env1, |
| 635 | Val2&: cast<BoolValue>(Val&: Val2), Env2); |
| 636 | } |
| 637 | |
| 638 | Value *JoinedVal = JoinedEnv.createValue(Type); |
| 639 | if (JoinedVal) |
| 640 | Model.join(Type, Val1, Env1, Val2, Env2, JoinedVal&: *JoinedVal, JoinedEnv); |
| 641 | |
| 642 | return JoinedVal; |
| 643 | } |
| 644 | |
| 645 | static WidenResult widenDistinctValues(QualType Type, Value &Prev, |
| 646 | const Environment &PrevEnv, |
| 647 | Value &Current, Environment &CurrentEnv, |
| 648 | Environment::ValueModel &Model) { |
| 649 | // Boolean-model widening. |
| 650 | if (isa<BoolValue>(Val: Prev) && isa<BoolValue>(Val: Current)) { |
| 651 | // FIXME: Checking both values should be unnecessary, but we can currently |
| 652 | // end up with `BoolValue`s in integer-typed variables. See comment in |
| 653 | // `joinDistinctValues()` for details. |
| 654 | auto &PrevBool = cast<BoolValue>(Val&: Prev); |
| 655 | auto &CurBool = cast<BoolValue>(Val&: Current); |
| 656 | |
| 657 | if (isa<TopBoolValue>(Val: Prev)) |
| 658 | // Safe to return `Prev` here, because Top is never dependent on the |
| 659 | // environment. |
| 660 | return {.V: &Prev, .Effect: LatticeEffect::Unchanged}; |
| 661 | |
| 662 | // We may need to widen to Top, but before we do so, check whether both |
| 663 | // values are implied to be either true or false in the current environment. |
| 664 | // In that case, we can simply return a literal instead. |
| 665 | bool TruePrev = PrevEnv.proves(PrevBool.formula()); |
| 666 | bool TrueCur = CurrentEnv.proves(CurBool.formula()); |
| 667 | if (TruePrev && TrueCur) |
| 668 | return {.V: &CurrentEnv.getBoolLiteralValue(Value: true), .Effect: LatticeEffect::Unchanged}; |
| 669 | if (!TruePrev && !TrueCur && |
| 670 | PrevEnv.proves(PrevEnv.arena().makeNot(Val: PrevBool.formula())) && |
| 671 | CurrentEnv.proves(CurrentEnv.arena().makeNot(Val: CurBool.formula()))) |
| 672 | return {.V: &CurrentEnv.getBoolLiteralValue(Value: false), .Effect: LatticeEffect::Unchanged}; |
| 673 | |
| 674 | return {.V: &CurrentEnv.makeTopBoolValue(), .Effect: LatticeEffect::Changed}; |
| 675 | } |
| 676 | |
| 677 | // FIXME: Add other built-in model widening. |
| 678 | |
| 679 | // Custom-model widening. |
| 680 | if (auto Result = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv)) |
| 681 | return *Result; |
| 682 | |
| 683 | return {.V: &Current, .Effect: equateUnknownValues(K: Prev.getKind()) |
| 684 | ? LatticeEffect::Unchanged |
| 685 | : LatticeEffect::Changed}; |
| 686 | } |
| 687 | |
| 688 | // Returns whether the values in `Map1` and `Map2` compare equal for those |
| 689 | // keys that `Map1` and `Map2` have in common. |
| 690 | template <typename Key> |
| 691 | static bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1, |
| 692 | const llvm::MapVector<Key, Value *> &Map2, |
| 693 | const Environment &Env1, |
| 694 | const Environment &Env2, |
| 695 | Environment::ValueModel &Model) { |
| 696 | for (auto &Entry : Map1) { |
| 697 | Key K = Entry.first; |
| 698 | assert(K != nullptr); |
| 699 | |
| 700 | Value *Val = Entry.second; |
| 701 | assert(Val != nullptr); |
| 702 | |
| 703 | auto It = Map2.find(K); |
| 704 | if (It == Map2.end()) |
| 705 | continue; |
| 706 | assert(It->second != nullptr); |
| 707 | |
| 708 | if (!areEquivalentValues(*Val, *It->second) && |
| 709 | !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2, |
| 710 | Model)) |
| 711 | return false; |
| 712 | } |
| 713 | |
| 714 | return true; |
| 715 | } |
| 716 | |
| 717 | // Perform a join on two `LocToVal` maps. |
| 718 | static llvm::MapVector<const StorageLocation *, Value *> |
| 719 | joinLocToVal(const llvm::MapVector<const StorageLocation *, Value *> &LocToVal, |
| 720 | const llvm::MapVector<const StorageLocation *, Value *> &LocToVal2, |
| 721 | const Environment &Env1, const Environment &Env2, |
| 722 | Environment &JoinedEnv, Environment::ValueModel &Model) { |
| 723 | llvm::MapVector<const StorageLocation *, Value *> Result; |
| 724 | for (auto &Entry : LocToVal) { |
| 725 | const StorageLocation *Loc = Entry.first; |
| 726 | assert(Loc != nullptr); |
| 727 | |
| 728 | Value *Val = Entry.second; |
| 729 | assert(Val != nullptr); |
| 730 | |
| 731 | auto It = LocToVal2.find(Key: Loc); |
| 732 | if (It == LocToVal2.end()) |
| 733 | continue; |
| 734 | assert(It->second != nullptr); |
| 735 | |
| 736 | if (Value *JoinedVal = Environment::joinValues( |
| 737 | Ty: Loc->getType(), Val1: Val, Env1, Val2: It->second, Env2, JoinedEnv, Model)) { |
| 738 | Result.insert(KV: {Loc, JoinedVal}); |
| 739 | } |
| 740 | } |
| 741 | |
| 742 | return Result; |
| 743 | } |
| 744 | |
| 745 | // Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either |
| 746 | // `const StorageLocation *` or `const Expr *`. |
| 747 | template <typename Key> |
| 748 | static llvm::MapVector<Key, Value *> |
| 749 | widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap, |
| 750 | const llvm::MapVector<Key, Value *> &PrevMap, |
| 751 | Environment &CurEnv, const Environment &PrevEnv, |
| 752 | Environment::ValueModel &Model, LatticeEffect &Effect) { |
| 753 | llvm::MapVector<Key, Value *> WidenedMap; |
| 754 | for (auto &Entry : CurMap) { |
| 755 | Key K = Entry.first; |
| 756 | assert(K != nullptr); |
| 757 | |
| 758 | Value *Val = Entry.second; |
| 759 | assert(Val != nullptr); |
| 760 | |
| 761 | auto PrevIt = PrevMap.find(K); |
| 762 | if (PrevIt == PrevMap.end()) |
| 763 | continue; |
| 764 | assert(PrevIt->second != nullptr); |
| 765 | |
| 766 | if (areEquivalentValues(*Val, *PrevIt->second)) { |
| 767 | WidenedMap.insert({K, Val}); |
| 768 | continue; |
| 769 | } |
| 770 | |
| 771 | auto [WidenedVal, ValEffect] = widenDistinctValues( |
| 772 | K->getType(), *PrevIt->second, PrevEnv, *Val, CurEnv, Model); |
| 773 | WidenedMap.insert({K, WidenedVal}); |
| 774 | if (ValEffect == LatticeEffect::Changed) |
| 775 | Effect = LatticeEffect::Changed; |
| 776 | } |
| 777 | |
| 778 | return WidenedMap; |
| 779 | } |
| 780 | |
| 781 | namespace { |
| 782 | |
| 783 | // Visitor that builds a map from record prvalues to result objects. |
| 784 | // For each result object that it encounters, it propagates the storage location |
| 785 | // of the result object to all record prvalues that can initialize it. |
| 786 | class ResultObjectVisitor : public AnalysisASTVisitor { |
| 787 | public: |
| 788 | // `ResultObjectMap` will be filled with a map from record prvalues to result |
| 789 | // object. If this visitor will traverse a function that returns a record by |
| 790 | // value, `LocForRecordReturnVal` is the location to which this record should |
| 791 | // be written; otherwise, it is null. |
| 792 | explicit ResultObjectVisitor( |
| 793 | llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap, |
| 794 | RecordStorageLocation *LocForRecordReturnVal, |
| 795 | DataflowAnalysisContext &DACtx) |
| 796 | : ResultObjectMap(ResultObjectMap), |
| 797 | LocForRecordReturnVal(LocForRecordReturnVal), DACtx(DACtx) {} |
| 798 | |
| 799 | // Traverse all member and base initializers of `Ctor`. This function is not |
| 800 | // called by `RecursiveASTVisitor`; it should be called manually if we are |
| 801 | // analyzing a constructor. `ThisPointeeLoc` is the storage location that |
| 802 | // `this` points to. |
| 803 | void traverseConstructorInits(const CXXConstructorDecl *Ctor, |
| 804 | RecordStorageLocation *ThisPointeeLoc) { |
| 805 | assert(ThisPointeeLoc != nullptr); |
| 806 | for (const CXXCtorInitializer *Init : Ctor->inits()) { |
| 807 | Expr *InitExpr = Init->getInit(); |
| 808 | if (FieldDecl *Field = Init->getMember(); |
| 809 | Field != nullptr && Field->getType()->isRecordType()) { |
| 810 | PropagateResultObject(E: InitExpr, Loc: cast<RecordStorageLocation>( |
| 811 | Val: ThisPointeeLoc->getChild(D: *Field))); |
| 812 | } else if (Init->getBaseClass()) { |
| 813 | PropagateResultObject(E: InitExpr, Loc: ThisPointeeLoc); |
| 814 | } |
| 815 | |
| 816 | // Ensure that any result objects within `InitExpr` (e.g. temporaries) |
| 817 | // are also propagated to the prvalues that initialize them. |
| 818 | TraverseStmt(S: InitExpr); |
| 819 | |
| 820 | // If this is a `CXXDefaultInitExpr`, also propagate any result objects |
| 821 | // within the default expression. |
| 822 | if (auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(Val: InitExpr)) |
| 823 | TraverseStmt(S: DefaultInit->getExpr()); |
| 824 | } |
| 825 | } |
| 826 | |
| 827 | bool VisitVarDecl(VarDecl *VD) override { |
| 828 | if (VD->getType()->isRecordType() && VD->hasInit()) |
| 829 | PropagateResultObject( |
| 830 | E: VD->getInit(), |
| 831 | Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(D: *VD))); |
| 832 | return true; |
| 833 | } |
| 834 | |
| 835 | bool VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE) override { |
| 836 | if (MTE->getType()->isRecordType()) |
| 837 | PropagateResultObject( |
| 838 | E: MTE->getSubExpr(), |
| 839 | Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(E: *MTE))); |
| 840 | return true; |
| 841 | } |
| 842 | |
| 843 | bool VisitReturnStmt(ReturnStmt *Return) override { |
| 844 | Expr *RetValue = Return->getRetValue(); |
| 845 | if (RetValue != nullptr && RetValue->getType()->isRecordType() && |
| 846 | RetValue->isPRValue()) |
| 847 | PropagateResultObject(E: RetValue, Loc: LocForRecordReturnVal); |
| 848 | return true; |
| 849 | } |
| 850 | |
| 851 | bool VisitExpr(Expr *E) override { |
| 852 | // Clang's AST can have record-type prvalues without a result object -- for |
| 853 | // example as full-expressions contained in a compound statement or as |
| 854 | // arguments of call expressions. We notice this if we get here and a |
| 855 | // storage location has not yet been associated with `E`. In this case, |
| 856 | // treat this as if it was a `MaterializeTemporaryExpr`. |
| 857 | if (E->isPRValue() && E->getType()->isRecordType() && |
| 858 | !ResultObjectMap.contains(Val: E)) |
| 859 | PropagateResultObject( |
| 860 | E, Loc: &cast<RecordStorageLocation>(Val&: DACtx.getStableStorageLocation(E: *E))); |
| 861 | return true; |
| 862 | } |
| 863 | |
| 864 | void |
| 865 | PropagateResultObjectToRecordInitList(const RecordInitListHelper &InitList, |
| 866 | RecordStorageLocation *Loc) { |
| 867 | for (auto [Base, Init] : InitList.base_inits()) { |
| 868 | assert(Base->getType().getCanonicalType() == |
| 869 | Init->getType().getCanonicalType()); |
| 870 | |
| 871 | // Storage location for the base class is the same as that of the |
| 872 | // derived class because we "flatten" the object hierarchy and put all |
| 873 | // fields in `RecordStorageLocation` of the derived class. |
| 874 | PropagateResultObject(E: Init, Loc); |
| 875 | } |
| 876 | |
| 877 | for (auto [Field, Init] : InitList.field_inits()) { |
| 878 | // Fields of non-record type are handled in |
| 879 | // `TransferVisitor::VisitInitListExpr()`. |
| 880 | if (Field->getType()->isRecordType()) |
| 881 | PropagateResultObject( |
| 882 | E: Init, Loc: cast<RecordStorageLocation>(Val: Loc->getChild(D: *Field))); |
| 883 | } |
| 884 | } |
| 885 | |
| 886 | // Assigns `Loc` as the result object location of `E`, then propagates the |
| 887 | // location to all lower-level prvalues that initialize the same object as |
| 888 | // `E` (or one of its base classes or member variables). |
| 889 | void PropagateResultObject(Expr *E, RecordStorageLocation *Loc) { |
| 890 | if (!E->isPRValue() || !E->getType()->isRecordType()) { |
| 891 | assert(false); |
| 892 | // Ensure we don't propagate the result object if we hit this in a |
| 893 | // release build. |
| 894 | return; |
| 895 | } |
| 896 | |
| 897 | ResultObjectMap[E] = Loc; |
| 898 | |
| 899 | // The following AST node kinds are "original initializers": They are the |
| 900 | // lowest-level AST node that initializes a given object, and nothing |
| 901 | // below them can initialize the same object (or part of it). |
| 902 | if (isa<CXXConstructExpr>(Val: E) || isa<CallExpr>(Val: E) || isa<LambdaExpr>(Val: E) || |
| 903 | isa<CXXDefaultArgExpr>(Val: E) || isa<CXXStdInitializerListExpr>(Val: E) || |
| 904 | isa<AtomicExpr>(Val: E) || isa<CXXInheritedCtorInitExpr>(Val: E) || |
| 905 | // We treat `BuiltinBitCastExpr` as an "original initializer" too as |
| 906 | // it may not even be casting from a record type -- and even if it is, |
| 907 | // the two objects are in general of unrelated type. |
| 908 | isa<BuiltinBitCastExpr>(Val: E) || |
| 909 | // This covers both co_await and co_yield. |
| 910 | // The result object of co_await is <op>.await_resume(), but there is |
| 911 | // no expression for that to propagate to. |
| 912 | // co_yield is equivalent to `co_await promise.yield_value(expr)`. |
| 913 | isa<CoroutineSuspendExpr>(Val: E)) { |
| 914 | return; |
| 915 | } |
| 916 | if (auto *Op = dyn_cast<BinaryOperator>(Val: E); |
| 917 | Op && Op->getOpcode() == BO_Cmp) { |
| 918 | // Builtin `<=>` returns a `std::strong_ordering` object. |
| 919 | return; |
| 920 | } |
| 921 | |
| 922 | if (auto *InitList = dyn_cast<InitListExpr>(Val: E)) { |
| 923 | if (!InitList->isSemanticForm()) |
| 924 | return; |
| 925 | if (InitList->isTransparent()) { |
| 926 | PropagateResultObject(E: InitList->getInit(Init: 0), Loc); |
| 927 | return; |
| 928 | } |
| 929 | |
| 930 | PropagateResultObjectToRecordInitList(InitList: RecordInitListHelper(InitList), |
| 931 | Loc); |
| 932 | return; |
| 933 | } |
| 934 | |
| 935 | if (auto *ParenInitList = dyn_cast<CXXParenListInitExpr>(Val: E)) { |
| 936 | PropagateResultObjectToRecordInitList(InitList: RecordInitListHelper(ParenInitList), |
| 937 | Loc); |
| 938 | return; |
| 939 | } |
| 940 | |
| 941 | if (auto *Op = dyn_cast<BinaryOperator>(Val: E); Op && Op->isCommaOp()) { |
| 942 | PropagateResultObject(E: Op->getRHS(), Loc); |
| 943 | return; |
| 944 | } |
| 945 | |
| 946 | if (auto *Cond = dyn_cast<AbstractConditionalOperator>(Val: E)) { |
| 947 | PropagateResultObject(E: Cond->getTrueExpr(), Loc); |
| 948 | PropagateResultObject(E: Cond->getFalseExpr(), Loc); |
| 949 | return; |
| 950 | } |
| 951 | |
| 952 | if (auto *SE = dyn_cast<StmtExpr>(Val: E)) { |
| 953 | PropagateResultObject(E: cast<Expr>(Val: SE->getSubStmt()->body_back()), Loc); |
| 954 | return; |
| 955 | } |
| 956 | |
| 957 | if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Val: E)) { |
| 958 | PropagateResultObject(E: DIE->getExpr(), Loc); |
| 959 | return; |
| 960 | } |
| 961 | |
| 962 | // All other expression nodes that propagate a record prvalue should have |
| 963 | // exactly one child. |
| 964 | SmallVector<Stmt *, 1> Children(E->child_begin(), E->child_end()); |
| 965 | LLVM_DEBUG({ |
| 966 | if (Children.size() != 1) |
| 967 | E->dump(); |
| 968 | }); |
| 969 | assert(Children.size() == 1); |
| 970 | for (Stmt *S : Children) |
| 971 | PropagateResultObject(E: cast<Expr>(Val: S), Loc); |
| 972 | } |
| 973 | |
| 974 | private: |
| 975 | llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap; |
| 976 | RecordStorageLocation *LocForRecordReturnVal; |
| 977 | DataflowAnalysisContext &DACtx; |
| 978 | }; |
| 979 | |
| 980 | /// A visitor that finds `CXXThisExpr` that can refer to an object other than |
| 981 | /// the `this` of a member function. |
| 982 | class ThisExprOverridesVisitor : public AnalysisASTVisitor { |
| 983 | using BaseVisitor = AnalysisASTVisitor; |
| 984 | |
| 985 | public: |
| 986 | ThisExprOverridesVisitor( |
| 987 | RecordStorageLocation *ThisPointeeLoc, |
| 988 | const llvm::DenseMap<const Expr *, RecordStorageLocation *> |
| 989 | &ResultObjectMap, |
| 990 | llvm::DenseMap<const CXXThisExpr *, RecordStorageLocation *> |
| 991 | &ThisExprOverrides) |
| 992 | : DefaultThisPointeeLoc(ThisPointeeLoc), ResultObjectMap(ResultObjectMap), |
| 993 | ThisExprOverrides(ThisExprOverrides) { |
| 994 | ThisLocations.push(x: DefaultThisPointeeLoc); |
| 995 | } |
| 996 | |
| 997 | void traverseConstructorInits(const CXXConstructorDecl *Ctor) { |
| 998 | for (const CXXCtorInitializer *Init : Ctor->inits()) { |
| 999 | TraverseStmt(S: Init->getInit()); |
| 1000 | } |
| 1001 | } |
| 1002 | |
| 1003 | bool TraverseInitListExpr(InitListExpr *ILE) override { |
| 1004 | if (!ILE->isSemanticForm() || ILE->isTransparent()) { |
| 1005 | BaseVisitor::TraverseInitListExpr(S: ILE); |
| 1006 | return true; |
| 1007 | } |
| 1008 | bool IsRecordType = ILE->getType()->isRecordType(); |
| 1009 | if (IsRecordType) { |
| 1010 | auto It = ResultObjectMap.find(Val: ILE); |
| 1011 | if (It == ResultObjectMap.end()) { |
| 1012 | llvm_unreachable("InitListExpr not found in ResultObjectMap" ); |
| 1013 | return false; |
| 1014 | } |
| 1015 | InitListLocations.push(x: It->second); |
| 1016 | } |
| 1017 | BaseVisitor::TraverseInitListExpr(S: ILE); |
| 1018 | if (IsRecordType) |
| 1019 | InitListLocations.pop(); |
| 1020 | return true; |
| 1021 | } |
| 1022 | |
| 1023 | bool TraverseCXXParenListInitExpr(CXXParenListInitExpr *PLIE) override { |
| 1024 | auto It = ResultObjectMap.find(Val: PLIE); |
| 1025 | if (It == ResultObjectMap.end()) { |
| 1026 | llvm_unreachable("CXXParenListInitExpr not found in ResultObjectMap" ); |
| 1027 | return false; |
| 1028 | } |
| 1029 | InitListLocations.push(x: It->second); |
| 1030 | BaseVisitor::TraverseCXXParenListInitExpr(S: PLIE); |
| 1031 | InitListLocations.pop(); |
| 1032 | return true; |
| 1033 | } |
| 1034 | |
| 1035 | bool TraverseCXXDefaultInitExpr(CXXDefaultInitExpr *CDIE) override { |
| 1036 | bool HasInitListLocations = !InitListLocations.empty(); |
| 1037 | if (HasInitListLocations) { |
| 1038 | auto *Loc = InitListLocations.top(); |
| 1039 | ThisLocations.push(x: Loc); |
| 1040 | } |
| 1041 | BaseVisitor::TraverseCXXDefaultInitExpr(S: CDIE); |
| 1042 | if (HasInitListLocations) |
| 1043 | ThisLocations.pop(); |
| 1044 | return true; |
| 1045 | } |
| 1046 | |
| 1047 | bool TraverseCXXThisExpr(CXXThisExpr *This) override { |
| 1048 | assert(!ThisLocations.empty()); |
| 1049 | auto *Loc = ThisLocations.top(); |
| 1050 | if (Loc != DefaultThisPointeeLoc) |
| 1051 | ThisExprOverrides[This] = Loc; |
| 1052 | return true; |
| 1053 | } |
| 1054 | |
| 1055 | // The default `this` pointee location (null if not in a member function). |
| 1056 | RecordStorageLocation *DefaultThisPointeeLoc; |
| 1057 | // Locations to use for `this`, with the most recent scope on top. |
| 1058 | std::stack<RecordStorageLocation *> ThisLocations; |
| 1059 | // A stack of nested InitListExpr and CXXParenListInitExprs storage |
| 1060 | // locations that may be used for `this` if we enter a CXXDefaultInitExpr. |
| 1061 | std::stack<RecordStorageLocation *> InitListLocations; |
| 1062 | // Map to look up a storage location, e.g., when encountering an |
| 1063 | // InitListExpr. |
| 1064 | const llvm::DenseMap<const Expr *, RecordStorageLocation *> &ResultObjectMap; |
| 1065 | // The visitor will update this map with locations to use for `this`, |
| 1066 | // if different from `DefaultThisPointeeLoc`. |
| 1067 | llvm::DenseMap<const CXXThisExpr *, RecordStorageLocation *> |
| 1068 | &ThisExprOverrides; |
| 1069 | }; |
| 1070 | |
| 1071 | } // namespace |
| 1072 | |
| 1073 | Environment::Environment(DataflowAnalysisContext &DACtx, |
| 1074 | Atom FlowConditionToken) |
| 1075 | : DACtx(&DACtx), |
| 1076 | BoolState(std::make_unique<SatBoolModel>(args&: DACtx, args&: FlowConditionToken)) { |
| 1077 | assert(DACtx.getOptions().BoolModel == BoolModelKind::SAT && |
| 1078 | "FlowConditionToken constructor requires BoolModelKind::SAT" ); |
| 1079 | } |
| 1080 | |
| 1081 | Environment::Environment(DataflowAnalysisContext &DACtx) : DACtx(&DACtx) { |
| 1082 | switch (DACtx.getOptions().BoolModel) { |
| 1083 | case BoolModelKind::SAT: |
| 1084 | BoolState = std::make_unique<SatBoolModel>(args&: DACtx); |
| 1085 | break; |
| 1086 | case BoolModelKind::Simple: |
| 1087 | BoolState = std::make_unique<SimpleBoolModel>(); |
| 1088 | break; |
| 1089 | } |
| 1090 | } |
| 1091 | |
| 1092 | Environment::Environment(const Environment &Other) |
| 1093 | : DACtx(Other.DACtx), CallStack(Other.CallStack), |
| 1094 | InitialTargetFunc(Other.InitialTargetFunc), |
| 1095 | InitialTargetStmt(Other.InitialTargetStmt), |
| 1096 | ResultObjectMap(Other.ResultObjectMap), ReturnVal(Other.ReturnVal), |
| 1097 | ReturnLoc(Other.ReturnLoc), |
| 1098 | LocForRecordReturnVal(Other.LocForRecordReturnVal), |
| 1099 | ThisPointeeLoc(Other.ThisPointeeLoc), |
| 1100 | ThisExprOverrides(Other.ThisExprOverrides), DeclToLoc(Other.DeclToLoc), |
| 1101 | ExprToLoc(Other.ExprToLoc), ExprToVal(Other.ExprToVal), |
| 1102 | LocToVal(Other.LocToVal), BoolState(Other.BoolState->clone()) {} |
| 1103 | |
| 1104 | void Environment::initialize() { |
| 1105 | if (InitialTargetStmt == nullptr) |
| 1106 | return; |
| 1107 | |
| 1108 | if (InitialTargetFunc == nullptr) { |
| 1109 | initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(S: *InitialTargetStmt)); |
| 1110 | ResultObjectMap = |
| 1111 | std::make_shared<PrValueToResultObject>(args: buildResultObjectMap( |
| 1112 | DACtx, S: InitialTargetStmt, ThisPointeeLoc: getThisPointeeStorageLocation(), |
| 1113 | /*LocForRecordReturnValue=*/LocForRecordReturnVal: nullptr)); |
| 1114 | |
| 1115 | ThisExprOverrides = |
| 1116 | std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap( |
| 1117 | S: InitialTargetStmt, ThisPointeeLoc: getThisPointeeStorageLocation(), |
| 1118 | ResultObjectMap: *ResultObjectMap)); |
| 1119 | return; |
| 1120 | } |
| 1121 | |
| 1122 | initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(FD: *InitialTargetFunc)); |
| 1123 | |
| 1124 | for (const auto *ParamDecl : InitialTargetFunc->parameters()) { |
| 1125 | assert(ParamDecl != nullptr); |
| 1126 | setStorageLocation(D: *ParamDecl, Loc&: createObject(D: *ParamDecl, InitExpr: nullptr)); |
| 1127 | } |
| 1128 | |
| 1129 | if (InitialTargetFunc->getReturnType()->isRecordType()) |
| 1130 | LocForRecordReturnVal = &cast<RecordStorageLocation>( |
| 1131 | Val&: createStorageLocation(Type: InitialTargetFunc->getReturnType())); |
| 1132 | |
| 1133 | if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(Val: InitialTargetFunc)) { |
| 1134 | auto *Parent = MethodDecl->getParent(); |
| 1135 | assert(Parent != nullptr); |
| 1136 | |
| 1137 | if (Parent->isLambda()) { |
| 1138 | for (const auto &Capture : Parent->captures()) { |
| 1139 | if (Capture.capturesVariable()) { |
| 1140 | const auto *VarDecl = Capture.getCapturedVar(); |
| 1141 | assert(VarDecl != nullptr); |
| 1142 | setStorageLocation(D: *VarDecl, Loc&: createObject(D: *VarDecl, InitExpr: nullptr)); |
| 1143 | } else if (Capture.capturesThis()) { |
| 1144 | if (auto *Ancestor = InitialTargetFunc->getNonClosureAncestor()) { |
| 1145 | const auto *SurroundingMethodDecl = cast<CXXMethodDecl>(Val: Ancestor); |
| 1146 | QualType ThisPointeeType = |
| 1147 | SurroundingMethodDecl->getFunctionObjectParameterType(); |
| 1148 | setThisPointeeStorageLocation( |
| 1149 | cast<RecordStorageLocation>(Val&: createObject(Ty: ThisPointeeType))); |
| 1150 | } else if (auto *FieldBeingInitialized = |
| 1151 | dyn_cast<FieldDecl>(Val: Parent->getLambdaContextDecl())) { |
| 1152 | // This is in a field initializer, rather than a method. |
| 1153 | const RecordDecl *RD = FieldBeingInitialized->getParent(); |
| 1154 | const ASTContext &Ctx = RD->getASTContext(); |
| 1155 | CanQualType T = Ctx.getCanonicalTagType(TD: RD); |
| 1156 | setThisPointeeStorageLocation( |
| 1157 | cast<RecordStorageLocation>(Val&: createObject(Ty: T))); |
| 1158 | } else { |
| 1159 | assert(false && "Unexpected this-capturing lambda context." ); |
| 1160 | } |
| 1161 | } |
| 1162 | } |
| 1163 | } else if (MethodDecl->isImplicitObjectMemberFunction()) { |
| 1164 | QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType(); |
| 1165 | auto &ThisLoc = |
| 1166 | cast<RecordStorageLocation>(Val&: createStorageLocation(Type: ThisPointeeType)); |
| 1167 | setThisPointeeStorageLocation(ThisLoc); |
| 1168 | // Initialize fields of `*this` with values, but only if we're not |
| 1169 | // analyzing a constructor; after all, it's the constructor's job to do |
| 1170 | // this (and we want to be able to test that). |
| 1171 | if (!isa<CXXConstructorDecl>(Val: MethodDecl)) |
| 1172 | initializeFieldsWithValues(Loc&: ThisLoc); |
| 1173 | } |
| 1174 | } |
| 1175 | |
| 1176 | // We do this below the handling of `CXXMethodDecl` above so that we can |
| 1177 | // be sure that the storage location for `this` has been set. |
| 1178 | ResultObjectMap = |
| 1179 | std::make_shared<PrValueToResultObject>(args: buildResultObjectMap( |
| 1180 | DACtx, FuncDecl: InitialTargetFunc, ThisPointeeLoc: getThisPointeeStorageLocation(), |
| 1181 | LocForRecordReturnVal)); |
| 1182 | |
| 1183 | ThisExprOverrides = |
| 1184 | std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap( |
| 1185 | FuncDecl: InitialTargetFunc, ThisPointeeLoc: getThisPointeeStorageLocation(), |
| 1186 | ResultObjectMap: *ResultObjectMap)); |
| 1187 | } |
| 1188 | |
| 1189 | // FIXME: Add support for resetting globals after function calls to enable the |
| 1190 | // implementation of sound analyses. |
| 1191 | |
| 1192 | void Environment::initFieldsGlobalsAndFuncs(const ReferencedDecls &Referenced) { |
| 1193 | // These have to be added before the lines that follow to ensure that |
| 1194 | // `create*` work correctly for structs. |
| 1195 | DACtx->addModeledFields(Fields: Referenced.Fields); |
| 1196 | |
| 1197 | for (const VarDecl *D : Referenced.Globals) { |
| 1198 | if (getStorageLocation(D: *D) != nullptr) |
| 1199 | continue; |
| 1200 | |
| 1201 | // We don't run transfer functions on the initializers of global variables, |
| 1202 | // so they won't be associated with a value or storage location. We |
| 1203 | // therefore intentionally don't pass an initializer to `createObject()`; in |
| 1204 | // particular, this ensures that `createObject()` will initialize the fields |
| 1205 | // of record-type variables with values. |
| 1206 | setStorageLocation(D: *D, Loc&: createObject(D: *D, InitExpr: nullptr)); |
| 1207 | } |
| 1208 | |
| 1209 | for (const FunctionDecl *FD : Referenced.Functions) { |
| 1210 | if (getStorageLocation(D: *FD) != nullptr) |
| 1211 | continue; |
| 1212 | auto &Loc = createStorageLocation(D: *FD); |
| 1213 | setStorageLocation(D: *FD, Loc); |
| 1214 | } |
| 1215 | } |
| 1216 | |
| 1217 | Environment Environment::fork() const { |
| 1218 | Environment Copy(*this); |
| 1219 | Copy.BoolState->onFork(); |
| 1220 | return Copy; |
| 1221 | } |
| 1222 | |
| 1223 | bool Environment::canDescend(unsigned MaxDepth, |
| 1224 | const FunctionDecl *Callee) const { |
| 1225 | return CallStack.size() < MaxDepth && !llvm::is_contained(Range: CallStack, Element: Callee); |
| 1226 | } |
| 1227 | |
| 1228 | Environment Environment::pushCall(const CallExpr *Call) const { |
| 1229 | Environment Env(*this); |
| 1230 | |
| 1231 | if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Val: Call)) { |
| 1232 | if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) { |
| 1233 | if (!isa<CXXThisExpr>(Val: Arg)) |
| 1234 | Env.ThisPointeeLoc = |
| 1235 | cast<RecordStorageLocation>(Val: getStorageLocation(E: *Arg)); |
| 1236 | // Otherwise (when the argument is `this`), retain the current |
| 1237 | // environment's `ThisPointeeLoc`. |
| 1238 | } |
| 1239 | } |
| 1240 | |
| 1241 | if (Call->getType()->isRecordType() && Call->isPRValue()) |
| 1242 | Env.LocForRecordReturnVal = &Env.getResultObjectLocation(RecordPRValue: *Call); |
| 1243 | |
| 1244 | Env.pushCallInternal(FuncDecl: Call->getDirectCallee(), |
| 1245 | Args: llvm::ArrayRef(Call->getArgs(), Call->getNumArgs())); |
| 1246 | |
| 1247 | return Env; |
| 1248 | } |
| 1249 | |
| 1250 | Environment Environment::pushCall(const CXXConstructExpr *Call) const { |
| 1251 | Environment Env(*this); |
| 1252 | |
| 1253 | Env.ThisPointeeLoc = &Env.getResultObjectLocation(RecordPRValue: *Call); |
| 1254 | Env.LocForRecordReturnVal = &Env.getResultObjectLocation(RecordPRValue: *Call); |
| 1255 | |
| 1256 | Env.pushCallInternal(FuncDecl: Call->getConstructor(), |
| 1257 | Args: llvm::ArrayRef(Call->getArgs(), Call->getNumArgs())); |
| 1258 | |
| 1259 | return Env; |
| 1260 | } |
| 1261 | |
| 1262 | void Environment::pushCallInternal(const FunctionDecl *FuncDecl, |
| 1263 | ArrayRef<const Expr *> Args) { |
| 1264 | // Canonicalize to the definition of the function. This ensures that we're |
| 1265 | // putting arguments into the same `ParamVarDecl`s` that the callee will later |
| 1266 | // be retrieving them from. |
| 1267 | assert(FuncDecl->getDefinition() != nullptr); |
| 1268 | FuncDecl = FuncDecl->getDefinition(); |
| 1269 | |
| 1270 | CallStack.push_back(x: FuncDecl); |
| 1271 | |
| 1272 | initFieldsGlobalsAndFuncs(Referenced: getReferencedDecls(FD: *FuncDecl)); |
| 1273 | |
| 1274 | const auto *ParamIt = FuncDecl->param_begin(); |
| 1275 | |
| 1276 | // FIXME: Parameters don't always map to arguments 1:1; examples include |
| 1277 | // overloaded operators implemented as member functions, and parameter packs. |
| 1278 | for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) { |
| 1279 | assert(ParamIt != FuncDecl->param_end()); |
| 1280 | const VarDecl *Param = *ParamIt; |
| 1281 | setStorageLocation(D: *Param, Loc&: createObject(D: *Param, InitExpr: Args[ArgIndex])); |
| 1282 | } |
| 1283 | |
| 1284 | ResultObjectMap = std::make_shared<PrValueToResultObject>( |
| 1285 | args: buildResultObjectMap(DACtx, FuncDecl, ThisPointeeLoc: getThisPointeeStorageLocation(), |
| 1286 | LocForRecordReturnVal)); |
| 1287 | ThisExprOverrides = |
| 1288 | std::make_shared<ThisExprOverridesMap>(args: buildThisExprOverridesMap( |
| 1289 | FuncDecl, ThisPointeeLoc: getThisPointeeStorageLocation(), ResultObjectMap: *ResultObjectMap)); |
| 1290 | } |
| 1291 | |
| 1292 | void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) { |
| 1293 | // We ignore some entries of `CalleeEnv`: |
| 1294 | // - `DACtx` because is already the same in both |
| 1295 | // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or |
| 1296 | // `ThisPointeeLoc` because they don't apply to us. |
| 1297 | // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the |
| 1298 | // callee's local scope, so when popping that scope, we do not propagate |
| 1299 | // the maps. |
| 1300 | this->LocToVal = std::move(CalleeEnv.LocToVal); |
| 1301 | this->BoolState = CalleeEnv.BoolState->clone(); |
| 1302 | |
| 1303 | if (Call->isGLValue()) { |
| 1304 | if (CalleeEnv.ReturnLoc != nullptr) |
| 1305 | setStorageLocation(E: *Call, Loc&: *CalleeEnv.ReturnLoc); |
| 1306 | } else if (!Call->getType()->isVoidType()) { |
| 1307 | if (CalleeEnv.ReturnVal != nullptr) |
| 1308 | setValue(E: *Call, Val&: *CalleeEnv.ReturnVal); |
| 1309 | } |
| 1310 | } |
| 1311 | |
| 1312 | void Environment::popCall(const CXXConstructExpr *Call, |
| 1313 | const Environment &CalleeEnv) { |
| 1314 | // See also comment in `popCall(const CallExpr *, const Environment &)` above. |
| 1315 | this->LocToVal = std::move(CalleeEnv.LocToVal); |
| 1316 | this->BoolState = CalleeEnv.BoolState->clone(); |
| 1317 | } |
| 1318 | |
| 1319 | bool Environment::equivalentTo(const Environment &Other, |
| 1320 | Environment::ValueModel &Model) const { |
| 1321 | assert(DACtx == Other.DACtx); |
| 1322 | |
| 1323 | if (ReturnVal != Other.ReturnVal) |
| 1324 | return false; |
| 1325 | |
| 1326 | if (ReturnLoc != Other.ReturnLoc) |
| 1327 | return false; |
| 1328 | |
| 1329 | if (LocForRecordReturnVal != Other.LocForRecordReturnVal) |
| 1330 | return false; |
| 1331 | |
| 1332 | if (ThisPointeeLoc != Other.ThisPointeeLoc) |
| 1333 | return false; |
| 1334 | |
| 1335 | if (DeclToLoc != Other.DeclToLoc) |
| 1336 | return false; |
| 1337 | |
| 1338 | if (ExprToLoc != Other.ExprToLoc) |
| 1339 | return false; |
| 1340 | |
| 1341 | if (!compareKeyToValueMaps(Map1: ExprToVal, Map2: Other.ExprToVal, Env1: *this, Env2: Other, Model)) |
| 1342 | return false; |
| 1343 | |
| 1344 | if (!compareKeyToValueMaps(Map1: LocToVal, Map2: Other.LocToVal, Env1: *this, Env2: Other, Model)) |
| 1345 | return false; |
| 1346 | if (!BoolState->isEquivalentTo(Other: *Other.BoolState)) |
| 1347 | return false; |
| 1348 | |
| 1349 | return true; |
| 1350 | } |
| 1351 | |
| 1352 | LatticeEffect Environment::widen(const Environment &PrevEnv, |
| 1353 | Environment::ValueModel &Model) { |
| 1354 | assert(DACtx == PrevEnv.DACtx); |
| 1355 | assert(ReturnVal == PrevEnv.ReturnVal); |
| 1356 | assert(ReturnLoc == PrevEnv.ReturnLoc); |
| 1357 | assert(LocForRecordReturnVal == PrevEnv.LocForRecordReturnVal); |
| 1358 | assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc); |
| 1359 | assert(ThisExprOverrides == PrevEnv.ThisExprOverrides); |
| 1360 | assert(CallStack == PrevEnv.CallStack); |
| 1361 | assert(ResultObjectMap == PrevEnv.ResultObjectMap); |
| 1362 | assert(InitialTargetFunc == PrevEnv.InitialTargetFunc); |
| 1363 | assert(InitialTargetStmt == PrevEnv.InitialTargetStmt); |
| 1364 | |
| 1365 | auto Effect = LatticeEffect::Unchanged; |
| 1366 | |
| 1367 | // By the API, `PrevEnv` is a previous version of the environment for the same |
| 1368 | // block, so we have some guarantees about its shape. In particular, it will |
| 1369 | // be the result of a join or widen operation on previous values for this |
| 1370 | // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that |
| 1371 | // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain |
| 1372 | // this property here, we don't need change their current values to widen. |
| 1373 | assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size()); |
| 1374 | assert(ExprToVal.size() <= PrevEnv.ExprToVal.size()); |
| 1375 | assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size()); |
| 1376 | |
| 1377 | ExprToVal = widenKeyToValueMap(CurMap: ExprToVal, PrevMap: PrevEnv.ExprToVal, CurEnv&: *this, PrevEnv, |
| 1378 | Model, Effect); |
| 1379 | |
| 1380 | LocToVal = widenKeyToValueMap(CurMap: LocToVal, PrevMap: PrevEnv.LocToVal, CurEnv&: *this, PrevEnv, |
| 1381 | Model, Effect); |
| 1382 | if (BoolState->widen(PrevModel: *PrevEnv.BoolState) == LatticeEffect::Changed) |
| 1383 | Effect = LatticeEffect::Changed; |
| 1384 | if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() || |
| 1385 | ExprToLoc.size() != PrevEnv.ExprToLoc.size() || |
| 1386 | ExprToVal.size() != PrevEnv.ExprToVal.size() || |
| 1387 | LocToVal.size() != PrevEnv.LocToVal.size()) |
| 1388 | Effect = LatticeEffect::Changed; |
| 1389 | |
| 1390 | return Effect; |
| 1391 | } |
| 1392 | |
| 1393 | Environment Environment::join(const Environment &EnvA, const Environment &EnvB, |
| 1394 | Environment::ValueModel &Model, |
| 1395 | ExprJoinBehavior ExprBehavior) { |
| 1396 | assert(EnvA.DACtx == EnvB.DACtx); |
| 1397 | assert(EnvA.LocForRecordReturnVal == EnvB.LocForRecordReturnVal); |
| 1398 | assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc); |
| 1399 | assert(EnvA.ThisExprOverrides == EnvB.ThisExprOverrides); |
| 1400 | assert(EnvA.CallStack == EnvB.CallStack); |
| 1401 | assert(EnvA.ResultObjectMap == EnvB.ResultObjectMap); |
| 1402 | assert(EnvA.InitialTargetFunc == EnvB.InitialTargetFunc); |
| 1403 | assert(EnvA.InitialTargetStmt == EnvB.InitialTargetStmt); |
| 1404 | |
| 1405 | Environment JoinedEnv(*EnvA.DACtx); |
| 1406 | |
| 1407 | JoinedEnv.CallStack = EnvA.CallStack; |
| 1408 | JoinedEnv.ResultObjectMap = EnvA.ResultObjectMap; |
| 1409 | JoinedEnv.LocForRecordReturnVal = EnvA.LocForRecordReturnVal; |
| 1410 | JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc; |
| 1411 | JoinedEnv.ThisExprOverrides = EnvA.ThisExprOverrides; |
| 1412 | JoinedEnv.InitialTargetFunc = EnvA.InitialTargetFunc; |
| 1413 | JoinedEnv.InitialTargetStmt = EnvA.InitialTargetStmt; |
| 1414 | |
| 1415 | const FunctionDecl *Func = EnvA.getCurrentFunc(); |
| 1416 | if (!Func) { |
| 1417 | JoinedEnv.ReturnVal = nullptr; |
| 1418 | } else { |
| 1419 | JoinedEnv.ReturnVal = |
| 1420 | joinValues(Ty: Func->getReturnType(), Val1: EnvA.ReturnVal, Env1: EnvA, Val2: EnvB.ReturnVal, |
| 1421 | Env2: EnvB, JoinedEnv, Model); |
| 1422 | } |
| 1423 | |
| 1424 | if (EnvA.ReturnLoc == EnvB.ReturnLoc) |
| 1425 | JoinedEnv.ReturnLoc = EnvA.ReturnLoc; |
| 1426 | else |
| 1427 | JoinedEnv.ReturnLoc = nullptr; |
| 1428 | |
| 1429 | JoinedEnv.DeclToLoc = intersectDeclToLoc(DeclToLoc1: EnvA.DeclToLoc, DeclToLoc2: EnvB.DeclToLoc); |
| 1430 | |
| 1431 | JoinedEnv.BoolState->join(ModelA: *EnvA.BoolState, ModelB: *EnvB.BoolState); |
| 1432 | |
| 1433 | JoinedEnv.LocToVal = |
| 1434 | joinLocToVal(LocToVal: EnvA.LocToVal, LocToVal2: EnvB.LocToVal, Env1: EnvA, Env2: EnvB, JoinedEnv, Model); |
| 1435 | |
| 1436 | if (ExprBehavior == KeepExprState) { |
| 1437 | JoinedEnv.ExprToVal = joinExprMaps(Map1: EnvA.ExprToVal, Map2: EnvB.ExprToVal); |
| 1438 | JoinedEnv.ExprToLoc = joinExprMaps(Map1: EnvA.ExprToLoc, Map2: EnvB.ExprToLoc); |
| 1439 | } |
| 1440 | |
| 1441 | return JoinedEnv; |
| 1442 | } |
| 1443 | |
| 1444 | Value *Environment::joinValues(QualType Ty, Value *Val1, |
| 1445 | const Environment &Env1, Value *Val2, |
| 1446 | const Environment &Env2, Environment &JoinedEnv, |
| 1447 | Environment::ValueModel &Model) { |
| 1448 | if (Val1 == nullptr || Val2 == nullptr) |
| 1449 | // We can't say anything about the joined value -- even if one of the values |
| 1450 | // is non-null, we don't want to simply propagate it, because it would be |
| 1451 | // too specific: Because the other value is null, that means we have no |
| 1452 | // information at all about the value (i.e. the value is unconstrained). |
| 1453 | return nullptr; |
| 1454 | |
| 1455 | if (areEquivalentValues(Val1: *Val1, Val2: *Val2)) |
| 1456 | // Arbitrarily return one of the two values. |
| 1457 | return Val1; |
| 1458 | |
| 1459 | return joinDistinctValues(Type: Ty, Val1&: *Val1, Env1, Val2&: *Val2, Env2, JoinedEnv, Model); |
| 1460 | } |
| 1461 | |
| 1462 | StorageLocation &Environment::createStorageLocation(QualType Type) { |
| 1463 | return DACtx->createStorageLocation(Type); |
| 1464 | } |
| 1465 | |
| 1466 | StorageLocation &Environment::createStorageLocation(const ValueDecl &D) { |
| 1467 | // Evaluated declarations are always assigned the same storage locations to |
| 1468 | // ensure that the environment stabilizes across loop iterations. Storage |
| 1469 | // locations for evaluated declarations are stored in the analysis context. |
| 1470 | return DACtx->getStableStorageLocation(D); |
| 1471 | } |
| 1472 | |
| 1473 | StorageLocation &Environment::createStorageLocation(const Expr &E) { |
| 1474 | // Evaluated expressions are always assigned the same storage locations to |
| 1475 | // ensure that the environment stabilizes across loop iterations. Storage |
| 1476 | // locations for evaluated expressions are stored in the analysis context. |
| 1477 | return DACtx->getStableStorageLocation(E); |
| 1478 | } |
| 1479 | |
| 1480 | void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { |
| 1481 | assert(!DeclToLoc.contains(&D)); |
| 1482 | // The only kinds of declarations that may have a "variable" storage location |
| 1483 | // are declarations of reference type and `BindingDecl`. For all other |
| 1484 | // declaration, the storage location should be the stable storage location |
| 1485 | // returned by `createStorageLocation()`. |
| 1486 | assert(D.getType()->isReferenceType() || isa<BindingDecl>(D) || |
| 1487 | &Loc == &createStorageLocation(D)); |
| 1488 | DeclToLoc[&D] = &Loc; |
| 1489 | } |
| 1490 | |
| 1491 | StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const { |
| 1492 | auto It = DeclToLoc.find(Val: &D); |
| 1493 | if (It == DeclToLoc.end()) |
| 1494 | return nullptr; |
| 1495 | |
| 1496 | StorageLocation *Loc = It->second; |
| 1497 | |
| 1498 | return Loc; |
| 1499 | } |
| 1500 | |
| 1501 | void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(Val: &D); } |
| 1502 | |
| 1503 | void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { |
| 1504 | // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason, |
| 1505 | // but we still want to be able to associate a `StorageLocation` with them, |
| 1506 | // so allow these as an exception. |
| 1507 | assert(E.isGLValue() || |
| 1508 | E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn)); |
| 1509 | const Expr &CanonE = ignoreCFGOmittedNodes(E); |
| 1510 | assert(!ExprToLoc.contains(&CanonE)); |
| 1511 | ExprToLoc[&CanonE] = &Loc; |
| 1512 | } |
| 1513 | |
| 1514 | StorageLocation *Environment::getStorageLocation(const Expr &E) const { |
| 1515 | // See comment in `setStorageLocation()`. |
| 1516 | assert(E.isGLValue() || |
| 1517 | E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn)); |
| 1518 | auto It = ExprToLoc.find(Val: &ignoreCFGOmittedNodes(E)); |
| 1519 | return It == ExprToLoc.end() ? nullptr : &*It->second; |
| 1520 | } |
| 1521 | |
| 1522 | RecordStorageLocation & |
| 1523 | Environment::getResultObjectLocation(const Expr &RecordPRValue) const { |
| 1524 | assert(RecordPRValue.getType()->isRecordType()); |
| 1525 | assert(RecordPRValue.isPRValue()); |
| 1526 | |
| 1527 | assert(ResultObjectMap != nullptr); |
| 1528 | RecordStorageLocation *Loc = ResultObjectMap->lookup(Val: &RecordPRValue); |
| 1529 | assert(Loc != nullptr); |
| 1530 | // In release builds, use the "stable" storage location if the map lookup |
| 1531 | // failed. |
| 1532 | if (Loc == nullptr) |
| 1533 | return cast<RecordStorageLocation>( |
| 1534 | Val&: DACtx->getStableStorageLocation(E: RecordPRValue)); |
| 1535 | return *Loc; |
| 1536 | } |
| 1537 | |
| 1538 | PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) { |
| 1539 | return DACtx->getOrCreateNullPointerValue(PointeeType); |
| 1540 | } |
| 1541 | |
| 1542 | void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc, |
| 1543 | QualType Type) { |
| 1544 | llvm::DenseSet<QualType> Visited; |
| 1545 | int CreatedValuesCount = 0; |
| 1546 | initializeFieldsWithValues(Loc, Type, Visited, Depth: 0, CreatedValuesCount); |
| 1547 | if (CreatedValuesCount > MaxCompositeValueSize) { |
| 1548 | llvm::errs() << "Attempting to initialize a huge value of type: " << Type |
| 1549 | << '\n'; |
| 1550 | } |
| 1551 | } |
| 1552 | |
| 1553 | void Environment::setValue(const StorageLocation &Loc, Value &Val) { |
| 1554 | // Records should not be associated with values. |
| 1555 | assert(!isa<RecordStorageLocation>(Loc)); |
| 1556 | LocToVal[&Loc] = &Val; |
| 1557 | } |
| 1558 | |
| 1559 | void Environment::setValue(const Expr &E, Value &Val) { |
| 1560 | const Expr &CanonE = ignoreCFGOmittedNodes(E); |
| 1561 | |
| 1562 | assert(CanonE.isPRValue()); |
| 1563 | // Records should not be associated with values. |
| 1564 | assert(!CanonE.getType()->isRecordType()); |
| 1565 | ExprToVal[&CanonE] = &Val; |
| 1566 | } |
| 1567 | |
| 1568 | Value *Environment::getValue(const StorageLocation &Loc) const { |
| 1569 | // Records should not be associated with values. |
| 1570 | assert(!isa<RecordStorageLocation>(Loc)); |
| 1571 | return LocToVal.lookup(Key: &Loc); |
| 1572 | } |
| 1573 | |
| 1574 | Value *Environment::getValue(const ValueDecl &D) const { |
| 1575 | auto *Loc = getStorageLocation(D); |
| 1576 | if (Loc == nullptr) |
| 1577 | return nullptr; |
| 1578 | return getValue(Loc: *Loc); |
| 1579 | } |
| 1580 | |
| 1581 | Value *Environment::getValue(const Expr &E) const { |
| 1582 | // Records should not be associated with values. |
| 1583 | assert(!E.getType()->isRecordType()); |
| 1584 | |
| 1585 | if (E.isPRValue()) { |
| 1586 | auto It = ExprToVal.find(Key: &ignoreCFGOmittedNodes(E)); |
| 1587 | return It == ExprToVal.end() ? nullptr : It->second; |
| 1588 | } |
| 1589 | |
| 1590 | auto It = ExprToLoc.find(Val: &ignoreCFGOmittedNodes(E)); |
| 1591 | if (It == ExprToLoc.end()) |
| 1592 | return nullptr; |
| 1593 | return getValue(Loc: *It->second); |
| 1594 | } |
| 1595 | |
| 1596 | Value *Environment::createValue(QualType Type) { |
| 1597 | llvm::DenseSet<QualType> Visited; |
| 1598 | int CreatedValuesCount = 0; |
| 1599 | Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0, |
| 1600 | CreatedValuesCount); |
| 1601 | if (CreatedValuesCount > MaxCompositeValueSize) { |
| 1602 | llvm::errs() << "Attempting to initialize a huge value of type: " << Type |
| 1603 | << '\n'; |
| 1604 | } |
| 1605 | return Val; |
| 1606 | } |
| 1607 | |
| 1608 | Value *Environment::createValueUnlessSelfReferential( |
| 1609 | QualType Type, llvm::DenseSet<QualType> &Visited, int Depth, |
| 1610 | int &CreatedValuesCount) { |
| 1611 | assert(!Type.isNull()); |
| 1612 | assert(!Type->isReferenceType()); |
| 1613 | assert(!Type->isRecordType()); |
| 1614 | |
| 1615 | // Allow unlimited fields at depth 1; only cap at deeper nesting levels. |
| 1616 | if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) || |
| 1617 | Depth > MaxCompositeValueDepth) |
| 1618 | return nullptr; |
| 1619 | |
| 1620 | if (Type->isBooleanType()) { |
| 1621 | CreatedValuesCount++; |
| 1622 | return &makeAtomicBoolValue(); |
| 1623 | } |
| 1624 | |
| 1625 | if (Type->isIntegerType()) { |
| 1626 | // FIXME: consider instead `return nullptr`, given that we do nothing useful |
| 1627 | // with integers, and so distinguishing them serves no purpose, but could |
| 1628 | // prevent convergence. |
| 1629 | CreatedValuesCount++; |
| 1630 | return &arena().create<IntegerValue>(); |
| 1631 | } |
| 1632 | |
| 1633 | if (Type->isPointerType()) { |
| 1634 | CreatedValuesCount++; |
| 1635 | QualType PointeeType = Type->getPointeeType(); |
| 1636 | StorageLocation &PointeeLoc = |
| 1637 | createLocAndMaybeValue(Ty: PointeeType, Visited, Depth, CreatedValuesCount); |
| 1638 | |
| 1639 | return &arena().create<PointerValue>(args&: PointeeLoc); |
| 1640 | } |
| 1641 | |
| 1642 | return nullptr; |
| 1643 | } |
| 1644 | |
| 1645 | StorageLocation & |
| 1646 | Environment::createLocAndMaybeValue(QualType Ty, |
| 1647 | llvm::DenseSet<QualType> &Visited, |
| 1648 | int Depth, int &CreatedValuesCount) { |
| 1649 | if (!Visited.insert(V: Ty.getCanonicalType()).second) |
| 1650 | return createStorageLocation(Type: Ty.getNonReferenceType()); |
| 1651 | llvm::scope_exit EraseVisited( |
| 1652 | [&Visited, Ty] { Visited.erase(V: Ty.getCanonicalType()); }); |
| 1653 | |
| 1654 | Ty = Ty.getNonReferenceType(); |
| 1655 | |
| 1656 | if (Ty->isRecordType()) { |
| 1657 | auto &Loc = cast<RecordStorageLocation>(Val&: createStorageLocation(Type: Ty)); |
| 1658 | initializeFieldsWithValues(Loc, Type: Ty, Visited, Depth, CreatedValuesCount); |
| 1659 | return Loc; |
| 1660 | } |
| 1661 | |
| 1662 | StorageLocation &Loc = createStorageLocation(Type: Ty); |
| 1663 | |
| 1664 | if (Value *Val = createValueUnlessSelfReferential(Type: Ty, Visited, Depth, |
| 1665 | CreatedValuesCount)) |
| 1666 | setValue(Loc, Val&: *Val); |
| 1667 | |
| 1668 | return Loc; |
| 1669 | } |
| 1670 | |
| 1671 | void Environment::initializeFieldsWithValues(RecordStorageLocation &Loc, |
| 1672 | QualType Type, |
| 1673 | llvm::DenseSet<QualType> &Visited, |
| 1674 | int Depth, |
| 1675 | int &CreatedValuesCount) { |
| 1676 | auto initField = [&](QualType FieldType, StorageLocation &FieldLoc) { |
| 1677 | if (FieldType->isRecordType()) { |
| 1678 | auto &FieldRecordLoc = cast<RecordStorageLocation>(Val&: FieldLoc); |
| 1679 | initializeFieldsWithValues(Loc&: FieldRecordLoc, Type: FieldRecordLoc.getType(), |
| 1680 | Visited, Depth: Depth + 1, CreatedValuesCount); |
| 1681 | } else { |
| 1682 | if (getValue(Loc: FieldLoc) != nullptr) |
| 1683 | return; |
| 1684 | if (!Visited.insert(V: FieldType.getCanonicalType()).second) |
| 1685 | return; |
| 1686 | if (Value *Val = createValueUnlessSelfReferential( |
| 1687 | Type: FieldType, Visited, Depth: Depth + 1, CreatedValuesCount)) |
| 1688 | setValue(Loc: FieldLoc, Val&: *Val); |
| 1689 | Visited.erase(V: FieldType.getCanonicalType()); |
| 1690 | } |
| 1691 | }; |
| 1692 | |
| 1693 | for (const FieldDecl *Field : DACtx->getModeledFields(Type)) { |
| 1694 | assert(Field != nullptr); |
| 1695 | QualType FieldType = Field->getType(); |
| 1696 | |
| 1697 | if (FieldType->isReferenceType()) { |
| 1698 | Loc.setChild(D: *Field, |
| 1699 | Loc: &createLocAndMaybeValue(Ty: FieldType, Visited, Depth: Depth + 1, |
| 1700 | CreatedValuesCount)); |
| 1701 | } else { |
| 1702 | StorageLocation *FieldLoc = Loc.getChild(D: *Field); |
| 1703 | assert(FieldLoc != nullptr); |
| 1704 | initField(FieldType, *FieldLoc); |
| 1705 | } |
| 1706 | } |
| 1707 | for (const auto &[FieldName, FieldType] : DACtx->getSyntheticFields(Type)) { |
| 1708 | // Synthetic fields cannot have reference type, so we don't need to deal |
| 1709 | // with this case. |
| 1710 | assert(!FieldType->isReferenceType()); |
| 1711 | initField(FieldType, Loc.getSyntheticField(Name: FieldName)); |
| 1712 | } |
| 1713 | } |
| 1714 | |
| 1715 | StorageLocation &Environment::createObjectInternal(const ValueDecl *D, |
| 1716 | QualType Ty, |
| 1717 | const Expr *InitExpr) { |
| 1718 | if (Ty->isReferenceType()) { |
| 1719 | // Although variables of reference type always need to be initialized, it |
| 1720 | // can happen that we can't see the initializer, so `InitExpr` may still |
| 1721 | // be null. |
| 1722 | if (InitExpr) { |
| 1723 | if (auto *InitExprLoc = getStorageLocation(E: *InitExpr)) |
| 1724 | return *InitExprLoc; |
| 1725 | } |
| 1726 | |
| 1727 | // Even though we have an initializer, we might not get an |
| 1728 | // InitExprLoc, for example if the InitExpr is a CallExpr for which we |
| 1729 | // don't have a function body. In this case, we just invent a storage |
| 1730 | // location and value -- it's the best we can do. |
| 1731 | return createObjectInternal(D, Ty: Ty.getNonReferenceType(), InitExpr: nullptr); |
| 1732 | } |
| 1733 | |
| 1734 | StorageLocation &Loc = |
| 1735 | D ? createStorageLocation(D: *D) : createStorageLocation(Type: Ty); |
| 1736 | |
| 1737 | if (Ty->isRecordType()) { |
| 1738 | auto &RecordLoc = cast<RecordStorageLocation>(Val&: Loc); |
| 1739 | if (!InitExpr) |
| 1740 | initializeFieldsWithValues(Loc&: RecordLoc); |
| 1741 | } else { |
| 1742 | Value *Val = nullptr; |
| 1743 | if (InitExpr) |
| 1744 | // In the (few) cases where an expression is intentionally |
| 1745 | // "uninterpreted", `InitExpr` is not associated with a value. There are |
| 1746 | // two ways to handle this situation: propagate the status, so that |
| 1747 | // uninterpreted initializers result in uninterpreted variables, or |
| 1748 | // provide a default value. We choose the latter so that later refinements |
| 1749 | // of the variable can be used for reasoning about the surrounding code. |
| 1750 | // For this reason, we let this case be handled by the `createValue()` |
| 1751 | // call below. |
| 1752 | // |
| 1753 | // FIXME. If and when we interpret all language cases, change this to |
| 1754 | // assert that `InitExpr` is interpreted, rather than supplying a |
| 1755 | // default value (assuming we don't update the environment API to return |
| 1756 | // references). |
| 1757 | Val = getValue(E: *InitExpr); |
| 1758 | if (!Val) |
| 1759 | Val = createValue(Type: Ty); |
| 1760 | if (Val) |
| 1761 | setValue(Loc, Val&: *Val); |
| 1762 | } |
| 1763 | |
| 1764 | return Loc; |
| 1765 | } |
| 1766 | |
| 1767 | void Environment::assume(const Formula &F) { BoolState->assume(F); } |
| 1768 | |
| 1769 | bool Environment::proves(const Formula &F) const { |
| 1770 | return BoolState->proves(F); |
| 1771 | } |
| 1772 | |
| 1773 | bool Environment::allows(const Formula &F) const { |
| 1774 | return BoolState->allows(F); |
| 1775 | } |
| 1776 | |
| 1777 | void Environment::dump(raw_ostream &OS) const { |
| 1778 | llvm::DenseMap<const StorageLocation *, std::string> LocToName; |
| 1779 | if (LocForRecordReturnVal != nullptr) |
| 1780 | LocToName[LocForRecordReturnVal] = "(returned record)" ; |
| 1781 | if (ThisPointeeLoc != nullptr) |
| 1782 | LocToName[ThisPointeeLoc] = "this" ; |
| 1783 | |
| 1784 | OS << "DeclToLoc:\n" ; |
| 1785 | for (auto [D, L] : DeclToLoc) { |
| 1786 | auto Iter = LocToName.insert(KV: {L, D->getNameAsString()}).first; |
| 1787 | OS << " [" << Iter->second << ", " << L << "]\n" ; |
| 1788 | } |
| 1789 | OS << "ExprToLoc:\n" ; |
| 1790 | for (auto [E, L] : ExprToLoc) |
| 1791 | OS << " [" << E << ", " << L << "]\n" ; |
| 1792 | |
| 1793 | OS << "ExprToVal:\n" ; |
| 1794 | for (auto [E, V] : ExprToVal) |
| 1795 | OS << " [" << E << ", " << V << ": " << *V << "]\n" ; |
| 1796 | |
| 1797 | OS << "LocToVal:\n" ; |
| 1798 | for (auto [L, V] : LocToVal) { |
| 1799 | OS << " [" << L; |
| 1800 | if (auto Iter = LocToName.find(Val: L); Iter != LocToName.end()) |
| 1801 | OS << " (" << Iter->second << ")" ; |
| 1802 | OS << ", " << V << ": " << *V << "]\n" ; |
| 1803 | } |
| 1804 | |
| 1805 | if (const FunctionDecl *Func = getCurrentFunc()) { |
| 1806 | if (Func->getReturnType()->isReferenceType()) { |
| 1807 | OS << "ReturnLoc: " << ReturnLoc; |
| 1808 | if (auto Iter = LocToName.find(Val: ReturnLoc); Iter != LocToName.end()) |
| 1809 | OS << " (" << Iter->second << ")" ; |
| 1810 | OS << "\n" ; |
| 1811 | } else if (Func->getReturnType()->isRecordType() || |
| 1812 | isa<CXXConstructorDecl>(Val: Func)) { |
| 1813 | OS << "LocForRecordReturnVal: " << LocForRecordReturnVal << "\n" ; |
| 1814 | } else if (!Func->getReturnType()->isVoidType()) { |
| 1815 | if (ReturnVal == nullptr) |
| 1816 | OS << "ReturnVal: nullptr\n" ; |
| 1817 | else |
| 1818 | OS << "ReturnVal: " << *ReturnVal << "\n" ; |
| 1819 | } |
| 1820 | |
| 1821 | if (isa<CXXMethodDecl>(Val: Func)) { |
| 1822 | OS << "ThisPointeeLoc: " << ThisPointeeLoc << "\n" ; |
| 1823 | } |
| 1824 | } |
| 1825 | |
| 1826 | OS << "\n" ; |
| 1827 | BoolState->dump(OS); |
| 1828 | } |
| 1829 | |
| 1830 | void Environment::dump() const { dump(OS&: llvm::dbgs()); } |
| 1831 | |
| 1832 | Environment::PrValueToResultObject Environment::buildResultObjectMap( |
| 1833 | DataflowAnalysisContext *DACtx, const FunctionDecl *FuncDecl, |
| 1834 | RecordStorageLocation *ThisPointeeLoc, |
| 1835 | RecordStorageLocation *LocForRecordReturnVal) { |
| 1836 | assert(FuncDecl->doesThisDeclarationHaveABody()); |
| 1837 | |
| 1838 | PrValueToResultObject Map = buildResultObjectMap( |
| 1839 | DACtx, S: FuncDecl->getBody(), ThisPointeeLoc, LocForRecordReturnVal); |
| 1840 | |
| 1841 | ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx); |
| 1842 | if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: FuncDecl)) |
| 1843 | Visitor.traverseConstructorInits(Ctor, ThisPointeeLoc); |
| 1844 | |
| 1845 | return Map; |
| 1846 | } |
| 1847 | |
| 1848 | Environment::PrValueToResultObject Environment::buildResultObjectMap( |
| 1849 | DataflowAnalysisContext *DACtx, Stmt *S, |
| 1850 | RecordStorageLocation *ThisPointeeLoc, |
| 1851 | RecordStorageLocation *LocForRecordReturnVal) { |
| 1852 | PrValueToResultObject Map; |
| 1853 | ResultObjectVisitor Visitor(Map, LocForRecordReturnVal, *DACtx); |
| 1854 | Visitor.TraverseStmt(S); |
| 1855 | return Map; |
| 1856 | } |
| 1857 | |
| 1858 | Environment::ThisExprOverridesMap Environment::buildThisExprOverridesMap( |
| 1859 | const FunctionDecl *FuncDecl, RecordStorageLocation *ThisPointeeLoc, |
| 1860 | const PrValueToResultObject &ResultObjectMap) { |
| 1861 | assert(FuncDecl->doesThisDeclarationHaveABody()); |
| 1862 | |
| 1863 | ThisExprOverridesMap Map = buildThisExprOverridesMap( |
| 1864 | S: FuncDecl->getBody(), ThisPointeeLoc, ResultObjectMap); |
| 1865 | |
| 1866 | ThisExprOverridesVisitor Visitor(ThisPointeeLoc, ResultObjectMap, Map); |
| 1867 | if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: FuncDecl)) { |
| 1868 | Visitor.traverseConstructorInits(Ctor); |
| 1869 | } |
| 1870 | return Map; |
| 1871 | } |
| 1872 | |
| 1873 | Environment::ThisExprOverridesMap Environment::buildThisExprOverridesMap( |
| 1874 | Stmt *S, RecordStorageLocation *ThisPointeeLoc, |
| 1875 | const PrValueToResultObject &ResultObjectMap) { |
| 1876 | ThisExprOverridesMap Map; |
| 1877 | ThisExprOverridesVisitor Visitor(ThisPointeeLoc, ResultObjectMap, Map); |
| 1878 | Visitor.TraverseStmt(S); |
| 1879 | return Map; |
| 1880 | } |
| 1881 | |
| 1882 | RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE, |
| 1883 | const Environment &Env) { |
| 1884 | Expr *ImplicitObject = MCE.getImplicitObjectArgument(); |
| 1885 | if (ImplicitObject == nullptr) |
| 1886 | return nullptr; |
| 1887 | if (ImplicitObject->getType()->isPointerType()) { |
| 1888 | if (auto *Val = Env.get<PointerValue>(E: *ImplicitObject)) |
| 1889 | return &cast<RecordStorageLocation>(Val&: Val->getPointeeLoc()); |
| 1890 | return nullptr; |
| 1891 | } |
| 1892 | return cast_or_null<RecordStorageLocation>( |
| 1893 | Val: Env.getStorageLocation(E: *ImplicitObject)); |
| 1894 | } |
| 1895 | |
| 1896 | RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME, |
| 1897 | const Environment &Env) { |
| 1898 | Expr *Base = ME.getBase(); |
| 1899 | if (Base == nullptr) |
| 1900 | return nullptr; |
| 1901 | if (ME.isArrow()) { |
| 1902 | if (auto *Val = Env.get<PointerValue>(E: *Base)) |
| 1903 | return &cast<RecordStorageLocation>(Val&: Val->getPointeeLoc()); |
| 1904 | return nullptr; |
| 1905 | } |
| 1906 | return Env.get<RecordStorageLocation>(E: *Base); |
| 1907 | } |
| 1908 | |
| 1909 | } // namespace dataflow |
| 1910 | } // namespace clang |
| 1911 | |