clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

   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/Type.h"
  19 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
  20 #include "clang/Analysis/FlowSensitive/Value.h"
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/DenseSet.h"
  23 #include "llvm/ADT/MapVector.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/Support/ErrorHandling.h"
  26 #include <cassert>
  27 #include <utility>
  28
  29 namespace clang {
  30 namespace dataflow {
  31
  32 // FIXME: convert these to parameters of the analysis or environment. Current
  33 // settings have been experimentaly validated, but only for a particular
  34 // analysis.
  35 static constexpr int MaxCompositeValueDepth = 3;
  36 static constexpr int MaxCompositeValueSize = 1000;
  37
  38 /// Returns a map consisting of key-value entries that are present in both maps.
  39 template <typename K, typename V>
  40 llvm::DenseMap<K, V> intersectDenseMaps(const llvm::DenseMap<K, V> &Map1,
  41                                         const llvm::DenseMap<K, V> &Map2) {
  42   llvm::DenseMap<K, V> Result;
  43   for (auto &Entry : Map1) {
  44     auto It = Map2.find(Entry.first);
  45     if (It != Map2.end() && Entry.second == It->second)
  46       Result.insert({Entry.first, Entry.second});
  47   }
  48   return Result;
  49 }
  50
  51 // Whether to consider equivalent two values with an unknown relation.
  52 //
  53 // FIXME: this function is a hack enabling unsoundness to support
  54 // convergence. Once we have widening support for the reference/pointer and
  55 // struct built-in models, this should be unconditionally `false` (and inlined
  56 // as such at its call sites).
  57 static bool equateUnknownValues(Value::Kind K) {
  58   switch (K) {
  59   case Value::Kind::Integer:
  60   case Value::Kind::Pointer:
  61   case Value::Kind::Record:
  62     return true;
  63   default:
  64     return false;
  65   }
  66 }
  67
  68 static bool compareDistinctValues(QualType Type, Value &Val1,
  69                                   const Environment &Env1, Value &Val2,
  70                                   const Environment &Env2,
  71                                   Environment::ValueModel &Model) {
  72   // Note: Potentially costly, but, for booleans, we could check whether both
  73   // can be proven equivalent in their respective environments.
  74
  75   // FIXME: move the reference/pointers logic from `areEquivalentValues` to here
  76   // and implement separate, join/widen specific handling for
  77   // reference/pointers.
  78   switch (Model.compare(Type, Val1, Env1, Val2, Env2)) {
  79   case ComparisonResult::Same:
  80     return true;
  81   case ComparisonResult::Different:
  82     return false;
  83   case ComparisonResult::Unknown:
  84     return equateUnknownValues(Val1.getKind());
  85   }
  86   llvm_unreachable("All cases covered in switch");
  87 }
  88
  89 /// Attempts to merge distinct values `Val1` and `Val2` in `Env1` and `Env2`,
  90 /// respectively, of the same type `Type`. Merging generally produces a single
  91 /// value that (soundly) approximates the two inputs, although the actual
  92 /// meaning depends on `Model`.
  93 static Value *mergeDistinctValues(QualType Type, Value &Val1,
  94                                   const Environment &Env1, Value &Val2,
  95                                   const Environment &Env2,
  96                                   Environment &MergedEnv,
  97                                   Environment::ValueModel &Model) {
  98   // Join distinct boolean values preserving information about the constraints
  99   // in the respective path conditions.
 100   if (isa<BoolValue>(&Val1) && isa<BoolValue>(&Val2)) {
 101     // FIXME: Checking both values should be unnecessary, since they should have
 102     // a consistent shape.  However, right now we can end up with BoolValue's in
 103     // integer-typed variables due to our incorrect handling of
 104     // boolean-to-integer casts (we just propagate the BoolValue to the result
 105     // of the cast). So, a join can encounter an integer in one branch but a
 106     // bool in the other.
 107     // For example:
 108     // ```
 109     // std::optional<bool> o;
 110     // int x;
 111     // if (o.has_value())
 112     //   x = o.value();
 113     // ```
 114     auto &Expr1 = cast<BoolValue>(Val1).formula();
 115     auto &Expr2 = cast<BoolValue>(Val2).formula();
 116     auto &A = MergedEnv.arena();
 117     auto &MergedVal = A.makeAtomRef(A.makeAtom());
 118     MergedEnv.addToFlowCondition(
 119         A.makeOr(A.makeAnd(A.makeAtomRef(Env1.getFlowConditionToken()),
 120                            A.makeEquals(MergedVal, Expr1)),
 121                  A.makeAnd(A.makeAtomRef(Env2.getFlowConditionToken()),
 122                            A.makeEquals(MergedVal, Expr2))));
 123     return &A.makeBoolValue(MergedVal);
 124   }
 125
 126   Value *MergedVal = nullptr;
 127   if (auto *RecordVal1 = dyn_cast<RecordValue>(&Val1)) {
 128     auto *RecordVal2 = cast<RecordValue>(&Val2);
 129
 130     if (&RecordVal1->getLoc() == &RecordVal2->getLoc())
 131       // `RecordVal1` and `RecordVal2` may have different properties associated
 132       // with them. Create a new `RecordValue` with the same location but
 133       // without any properties so that we soundly approximate both values. If a
 134       // particular analysis needs to merge properties, it should do so in
 135       // `DataflowAnalysis::merge()`.
 136       MergedVal = &MergedEnv.create<RecordValue>(RecordVal1->getLoc());
 137     else
 138       // If the locations for the two records are different, need to create a
 139       // completely new value.
 140       MergedVal = MergedEnv.createValue(Type);
 141   } else {
 142     MergedVal = MergedEnv.createValue(Type);
 143   }
 144
 145   // FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
 146   // returns false to avoid storing unneeded values in `DACtx`.
 147   if (MergedVal)
 148     if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
 149       return MergedVal;
 150
 151   return nullptr;
 152 }
 153
 154 // When widening does not change `Current`, return value will equal `&Prev`.
 155 static Value &widenDistinctValues(QualType Type, Value &Prev,
 156                                   const Environment &PrevEnv, Value &Current,
 157                                   Environment &CurrentEnv,
 158                                   Environment::ValueModel &Model) {
 159   // Boolean-model widening.
 160   if (isa<BoolValue>(&Prev)) {
 161     assert(isa<BoolValue>(Current));
 162     // Widen to Top, because we know they are different values. If previous was
 163     // already Top, re-use that to (implicitly) indicate that no change occured.
 164     if (isa<TopBoolValue>(Prev))
 165       return Prev;
 166     return CurrentEnv.makeTopBoolValue();
 167   }
 168
 169   // FIXME: Add other built-in model widening.
 170
 171   // Custom-model widening.
 172   if (auto *W = Model.widen(Type, Prev, PrevEnv, Current, CurrentEnv))
 173     return *W;
 174
 175   return equateUnknownValues(Prev.getKind()) ? Prev : Current;
 176 }
 177
 178 // Returns whether the values in `Map1` and `Map2` compare equal for those
 179 // keys that `Map1` and `Map2` have in common.
 180 template <typename Key>
 181 bool compareKeyToValueMaps(const llvm::MapVector<Key, Value *> &Map1,
 182                            const llvm::MapVector<Key, Value *> &Map2,
 183                            const Environment &Env1, const Environment &Env2,
 184                            Environment::ValueModel &Model) {
 185   for (auto &Entry : Map1) {
 186     Key K = Entry.first;
 187     assert(K != nullptr);
 188
 189     Value *Val = Entry.second;
 190     assert(Val != nullptr);
 191
 192     auto It = Map2.find(K);
 193     if (It == Map2.end())
 194       continue;
 195     assert(It->second != nullptr);
 196
 197     if (!areEquivalentValues(*Val, *It->second) &&
 198         !compareDistinctValues(K->getType(), *Val, Env1, *It->second, Env2,
 199                                Model))
 200       return false;
 201   }
 202
 203   return true;
 204 }
 205
 206 // Perform a join on either `LocToVal` or `ExprToVal`. `Key` must be either
 207 // `const StorageLocation *` or `const Expr *`.
 208 template <typename Key>
 209 llvm::MapVector<Key, Value *>
 210 joinKeyToValueMap(const llvm::MapVector<Key, Value *> &Map1,
 211                   const llvm::MapVector<Key, Value *> &Map2,
 212                   const Environment &Env1, const Environment &Env2,
 213                   Environment &JoinedEnv, Environment::ValueModel &Model) {
 214   llvm::MapVector<Key, Value *> MergedMap;
 215   for (auto &Entry : Map1) {
 216     Key K = Entry.first;
 217     assert(K != nullptr);
 218
 219     Value *Val = Entry.second;
 220     assert(Val != nullptr);
 221
 222     auto It = Map2.find(K);
 223     if (It == Map2.end())
 224       continue;
 225     assert(It->second != nullptr);
 226
 227     if (areEquivalentValues(*Val, *It->second)) {
 228       MergedMap.insert({K, Val});
 229       continue;
 230     }
 231
 232     if (Value *MergedVal = mergeDistinctValues(
 233             K->getType(), *Val, Env1, *It->second, Env2, JoinedEnv, Model)) {
 234       MergedMap.insert({K, MergedVal});
 235     }
 236   }
 237
 238   return MergedMap;
 239 }
 240
 241 // Perform widening on either `LocToVal` or `ExprToVal`. `Key` must be either
 242 // `const StorageLocation *` or `const Expr *`.
 243 template <typename Key>
 244 llvm::MapVector<Key, Value *>
 245 widenKeyToValueMap(const llvm::MapVector<Key, Value *> &CurMap,
 246                    const llvm::MapVector<Key, Value *> &PrevMap,
 247                    Environment &CurEnv, const Environment &PrevEnv,
 248                    Environment::ValueModel &Model, LatticeJoinEffect &Effect) {
 249   llvm::MapVector<Key, Value *> WidenedMap;
 250   for (auto &Entry : CurMap) {
 251     Key K = Entry.first;
 252     assert(K != nullptr);
 253
 254     Value *Val = Entry.second;
 255     assert(Val != nullptr);
 256
 257     auto PrevIt = PrevMap.find(K);
 258     if (PrevIt == PrevMap.end())
 259       continue;
 260     assert(PrevIt->second != nullptr);
 261
 262     if (areEquivalentValues(*Val, *PrevIt->second)) {
 263       WidenedMap.insert({K, Val});
 264       continue;
 265     }
 266
 267     Value &WidenedVal = widenDistinctValues(K->getType(), *PrevIt->second,
 268                                             PrevEnv, *Val, CurEnv, Model);
 269     WidenedMap.insert({K, &WidenedVal});
 270     if (&WidenedVal != PrevIt->second)
 271       Effect = LatticeJoinEffect::Changed;
 272   }
 273
 274   return WidenedMap;
 275 }
 276
 277 /// Initializes a global storage value.
 278 static void insertIfGlobal(const Decl &D,
 279                            llvm::DenseSet<const VarDecl *> &Vars) {
 280   if (auto *V = dyn_cast<VarDecl>(&D))
 281     if (V->hasGlobalStorage())
 282       Vars.insert(V);
 283 }
 284
 285 static void insertIfFunction(const Decl &D,
 286                              llvm::DenseSet<const FunctionDecl *> &Funcs) {
 287   if (auto *FD = dyn_cast<FunctionDecl>(&D))
 288     Funcs.insert(FD);
 289 }
 290
 291 static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr &C) {
 292   if (!C.getMethodDecl())
 293     return nullptr;
 294   auto *Body = dyn_cast_or_null<CompoundStmt>(C.getMethodDecl()->getBody());
 295   if (!Body || Body->size() != 1)
 296     return nullptr;
 297   if (auto *RS = dyn_cast<ReturnStmt>(*Body->body_begin()))
 298     if (auto *Return = RS->getRetValue())
 299       return dyn_cast<MemberExpr>(Return->IgnoreParenImpCasts());
 300   return nullptr;
 301 }
 302
 303 static void
 304 getFieldsGlobalsAndFuncs(const Decl &D, FieldSet &Fields,
 305                          llvm::DenseSet<const VarDecl *> &Vars,
 306                          llvm::DenseSet<const FunctionDecl *> &Funcs) {
 307   insertIfGlobal(D, Vars);
 308   insertIfFunction(D, Funcs);
 309   if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
 310     for (const auto *B : Decomp->bindings())
 311       if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
 312         // FIXME: should we be using `E->getFoundDecl()`?
 313         if (const auto *FD = dyn_cast<FieldDecl>(ME->getMemberDecl()))
 314           Fields.insert(FD);
 315 }
 316
 317 /// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields,
 318 /// global variables and functions that are declared in or referenced from
 319 /// sub-statements.
 320 static void
 321 getFieldsGlobalsAndFuncs(const Stmt &S, FieldSet &Fields,
 322                          llvm::DenseSet<const VarDecl *> &Vars,
 323                          llvm::DenseSet<const FunctionDecl *> &Funcs) {
 324   for (auto *Child : S.children())
 325     if (Child != nullptr)
 326       getFieldsGlobalsAndFuncs(*Child, Fields, Vars, Funcs);
 327   if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S))
 328     getFieldsGlobalsAndFuncs(*DefaultInit->getExpr(), Fields, Vars, Funcs);
 329
 330   if (auto *DS = dyn_cast<DeclStmt>(&S)) {
 331     if (DS->isSingleDecl())
 332       getFieldsGlobalsAndFuncs(*DS->getSingleDecl(), Fields, Vars, Funcs);
 333     else
 334       for (auto *D : DS->getDeclGroup())
 335         getFieldsGlobalsAndFuncs(*D, Fields, Vars, Funcs);
 336   } else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
 337     insertIfGlobal(*E->getDecl(), Vars);
 338     insertIfFunction(*E->getDecl(), Funcs);
 339   } else if (const auto *C = dyn_cast<CXXMemberCallExpr>(&S)) {
 340     // If this is a method that returns a member variable but does nothing else,
 341     // model the field of the return value.
 342     if (MemberExpr *E = getMemberForAccessor(*C))
 343       if (const auto *FD = dyn_cast<FieldDecl>(E->getMemberDecl()))
 344         Fields.insert(FD);
 345   } else if (auto *E = dyn_cast<MemberExpr>(&S)) {
 346     // FIXME: should we be using `E->getFoundDecl()`?
 347     const ValueDecl *VD = E->getMemberDecl();
 348     insertIfGlobal(*VD, Vars);
 349     insertIfFunction(*VD, Funcs);
 350     if (const auto *FD = dyn_cast<FieldDecl>(VD))
 351       Fields.insert(FD);
 352   } else if (auto *InitList = dyn_cast<InitListExpr>(&S)) {
 353     if (RecordDecl *RD = InitList->getType()->getAsRecordDecl())
 354       for (const auto *FD : getFieldsForInitListExpr(RD))
 355         Fields.insert(FD);
 356   }
 357 }
 358
 359 // FIXME: Add support for resetting globals after function calls to enable
 360 // the implementation of sound analyses.
 361 void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) {
 362   assert(FuncDecl->getBody() != nullptr);
 363
 364   FieldSet Fields;
 365   llvm::DenseSet<const VarDecl *> Vars;
 366   llvm::DenseSet<const FunctionDecl *> Funcs;
 367
 368   // Look for global variable and field references in the
 369   // constructor-initializers.
 370   if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
 371     for (const auto *Init : CtorDecl->inits()) {
 372       if (Init->isMemberInitializer()) {
 373         Fields.insert(Init->getMember());
 374       } else if (Init->isIndirectMemberInitializer()) {
 375         for (const auto *I : Init->getIndirectMember()->chain())
 376           Fields.insert(cast<FieldDecl>(I));
 377       }
 378       const Expr *E = Init->getInit();
 379       assert(E != nullptr);
 380       getFieldsGlobalsAndFuncs(*E, Fields, Vars, Funcs);
 381     }
 382     // Add all fields mentioned in default member initializers.
 383     for (const FieldDecl *F : CtorDecl->getParent()->fields())
 384       if (const auto *I = F->getInClassInitializer())
 385           getFieldsGlobalsAndFuncs(*I, Fields, Vars, Funcs);
 386   }
 387   getFieldsGlobalsAndFuncs(*FuncDecl->getBody(), Fields, Vars, Funcs);
 388
 389   // These have to be added before the lines that follow to ensure that
 390   // `create*` work correctly for structs.
 391   DACtx->addModeledFields(Fields);
 392
 393   for (const VarDecl *D : Vars) {
 394     if (getStorageLocation(*D) != nullptr)
 395       continue;
 396
 397     setStorageLocation(*D, createObject(*D));
 398   }
 399
 400   for (const FunctionDecl *FD : Funcs) {
 401     if (getStorageLocation(*FD) != nullptr)
 402       continue;
 403     auto &Loc = createStorageLocation(FD->getType());
 404     setStorageLocation(*FD, Loc);
 405   }
 406 }
 407
 408 Environment::Environment(DataflowAnalysisContext &DACtx)
 409     : DACtx(&DACtx),
 410       FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
 411
 412 Environment Environment::fork() const {
 413   Environment Copy(*this);
 414   Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken);
 415   return Copy;
 416 }
 417
 418 Environment::Environment(DataflowAnalysisContext &DACtx,
 419                          const DeclContext &DeclCtx)
 420     : Environment(DACtx) {
 421   CallStack.push_back(&DeclCtx);
 422
 423   if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
 424     assert(FuncDecl->getBody() != nullptr);
 425
 426     initFieldsGlobalsAndFuncs(FuncDecl);
 427
 428     for (const auto *ParamDecl : FuncDecl->parameters()) {
 429       assert(ParamDecl != nullptr);
 430       setStorageLocation(*ParamDecl, createObject(*ParamDecl, nullptr));
 431     }
 432   }
 433
 434   if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
 435     auto *Parent = MethodDecl->getParent();
 436     assert(Parent != nullptr);
 437
 438     if (Parent->isLambda()) {
 439       for (auto Capture : Parent->captures()) {
 440         if (Capture.capturesVariable()) {
 441           const auto *VarDecl = Capture.getCapturedVar();
 442           assert(VarDecl != nullptr);
 443           setStorageLocation(*VarDecl, createObject(*VarDecl, nullptr));
 444         } else if (Capture.capturesThis()) {
 445           const auto *SurroundingMethodDecl =
 446               cast<CXXMethodDecl>(DeclCtx.getNonClosureAncestor());
 447           QualType ThisPointeeType =
 448               SurroundingMethodDecl->getFunctionObjectParameterType();
 449           ThisPointeeLoc =
 450               &cast<RecordValue>(createValue(ThisPointeeType))->getLoc();
 451         }
 452       }
 453     } else if (MethodDecl->isImplicitObjectMemberFunction()) {
 454       QualType ThisPointeeType = MethodDecl->getFunctionObjectParameterType();
 455       ThisPointeeLoc =
 456           &cast<RecordValue>(createValue(ThisPointeeType))->getLoc();
 457     }
 458   }
 459 }
 460
 461 bool Environment::canDescend(unsigned MaxDepth,
 462                              const DeclContext *Callee) const {
 463   return CallStack.size() <= MaxDepth && !llvm::is_contained(CallStack, Callee);
 464 }
 465
 466 Environment Environment::pushCall(const CallExpr *Call) const {
 467   Environment Env(*this);
 468
 469   if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
 470     if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
 471       if (!isa<CXXThisExpr>(Arg))
 472           Env.ThisPointeeLoc =
 473               cast<RecordStorageLocation>(getStorageLocation(*Arg));
 474       // Otherwise (when the argument is `this`), retain the current
 475       // environment's `ThisPointeeLoc`.
 476     }
 477   }
 478
 479   Env.pushCallInternal(Call->getDirectCallee(),
 480                        llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
 481
 482   return Env;
 483 }
 484
 485 Environment Environment::pushCall(const CXXConstructExpr *Call) const {
 486   Environment Env(*this);
 487
 488   Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call);
 489
 490   Env.pushCallInternal(Call->getConstructor(),
 491                        llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
 492
 493   return Env;
 494 }
 495
 496 void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
 497                                    ArrayRef<const Expr *> Args) {
 498   // Canonicalize to the definition of the function. This ensures that we're
 499   // putting arguments into the same `ParamVarDecl`s` that the callee will later
 500   // be retrieving them from.
 501   assert(FuncDecl->getDefinition() != nullptr);
 502   FuncDecl = FuncDecl->getDefinition();
 503
 504   CallStack.push_back(FuncDecl);
 505
 506   initFieldsGlobalsAndFuncs(FuncDecl);
 507
 508   const auto *ParamIt = FuncDecl->param_begin();
 509
 510   // FIXME: Parameters don't always map to arguments 1:1; examples include
 511   // overloaded operators implemented as member functions, and parameter packs.
 512   for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
 513     assert(ParamIt != FuncDecl->param_end());
 514     const VarDecl *Param = *ParamIt;
 515     setStorageLocation(*Param, createObject(*Param, Args[ArgIndex]));
 516   }
 517 }
 518
 519 void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
 520   // We ignore some entries of `CalleeEnv`:
 521   // - `DACtx` because is already the same in both
 522   // - We don't want the callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or
 523   //   `ThisPointeeLoc` because they don't apply to us.
 524   // - `DeclToLoc`, `ExprToLoc`, and `ExprToVal` capture information from the
 525   //   callee's local scope, so when popping that scope, we do not propagate
 526   //   the maps.
 527   this->LocToVal = std::move(CalleeEnv.LocToVal);
 528   this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
 529
 530   if (Call->isGLValue()) {
 531     if (CalleeEnv.ReturnLoc != nullptr)
 532       setStorageLocation(*Call, *CalleeEnv.ReturnLoc);
 533   } else if (!Call->getType()->isVoidType()) {
 534     if (CalleeEnv.ReturnVal != nullptr)
 535       setValue(*Call, *CalleeEnv.ReturnVal);
 536   }
 537 }
 538
 539 void Environment::popCall(const CXXConstructExpr *Call,
 540                           const Environment &CalleeEnv) {
 541   // See also comment in `popCall(const CallExpr *, const Environment &)` above.
 542   this->LocToVal = std::move(CalleeEnv.LocToVal);
 543   this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
 544
 545   if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) {
 546     setValue(*Call, *Val);
 547   }
 548 }
 549
 550 bool Environment::equivalentTo(const Environment &Other,
 551                                Environment::ValueModel &Model) const {
 552   assert(DACtx == Other.DACtx);
 553
 554   if (ReturnVal != Other.ReturnVal)
 555     return false;
 556
 557   if (ReturnLoc != Other.ReturnLoc)
 558     return false;
 559
 560   if (ThisPointeeLoc != Other.ThisPointeeLoc)
 561     return false;
 562
 563   if (DeclToLoc != Other.DeclToLoc)
 564     return false;
 565
 566   if (ExprToLoc != Other.ExprToLoc)
 567     return false;
 568
 569   if (!compareKeyToValueMaps(ExprToVal, Other.ExprToVal, *this, Other, Model))
 570     return false;
 571
 572   if (!compareKeyToValueMaps(LocToVal, Other.LocToVal, *this, Other, Model))
 573     return false;
 574
 575   return true;
 576 }
 577
 578 LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
 579                                      Environment::ValueModel &Model) {
 580   assert(DACtx == PrevEnv.DACtx);
 581   assert(ReturnVal == PrevEnv.ReturnVal);
 582   assert(ReturnLoc == PrevEnv.ReturnLoc);
 583   assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
 584   assert(CallStack == PrevEnv.CallStack);
 585
 586   auto Effect = LatticeJoinEffect::Unchanged;
 587
 588   // By the API, `PrevEnv` is a previous version of the environment for the same
 589   // block, so we have some guarantees about its shape. In particular, it will
 590   // be the result of a join or widen operation on previous values for this
 591   // block. For `DeclToLoc`, `ExprToVal`, and `ExprToLoc`, join guarantees that
 592   // these maps are subsets of the maps in `PrevEnv`. So, as long as we maintain
 593   // this property here, we don't need change their current values to widen.
 594   assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
 595   assert(ExprToVal.size() <= PrevEnv.ExprToVal.size());
 596   assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
 597
 598   ExprToVal = widenKeyToValueMap(ExprToVal, PrevEnv.ExprToVal, *this, PrevEnv,
 599                                  Model, Effect);
 600
 601   LocToVal = widenKeyToValueMap(LocToVal, PrevEnv.LocToVal, *this, PrevEnv,
 602                                 Model, Effect);
 603   if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
 604       ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
 605       ExprToVal.size() != PrevEnv.ExprToVal.size() ||
 606       LocToVal.size() != PrevEnv.LocToVal.size())
 607     Effect = LatticeJoinEffect::Changed;
 608
 609   return Effect;
 610 }
 611
 612 Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
 613                               Environment::ValueModel &Model) {
 614   assert(EnvA.DACtx == EnvB.DACtx);
 615   assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
 616   assert(EnvA.CallStack == EnvB.CallStack);
 617
 618   Environment JoinedEnv(*EnvA.DACtx);
 619
 620   JoinedEnv.CallStack = EnvA.CallStack;
 621   JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
 622
 623   if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) {
 624     // `ReturnVal` might not always get set -- for example if we have a return
 625     // statement of the form `return some_other_func()` and we decide not to
 626     // analyze `some_other_func()`.
 627     // In this case, we can't say anything about the joined return value -- we
 628     // don't simply want to propagate the return value that we do have, because
 629     // it might not be the correct one.
 630     // This occurs for example in the test `ContextSensitiveMutualRecursion`.
 631     JoinedEnv.ReturnVal = nullptr;
 632   } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) {
 633     JoinedEnv.ReturnVal = EnvA.ReturnVal;
 634   } else {
 635     assert(!EnvA.CallStack.empty());
 636     // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this
 637     // cast.
 638     auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
 639     assert(Func != nullptr);
 640     if (Value *MergedVal =
 641             mergeDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA,
 642                                 *EnvB.ReturnVal, EnvB, JoinedEnv, Model))
 643       JoinedEnv.ReturnVal = MergedVal;
 644   }
 645
 646   if (EnvA.ReturnLoc == EnvB.ReturnLoc)
 647     JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
 648   else
 649     JoinedEnv.ReturnLoc = nullptr;
 650
 651   JoinedEnv.DeclToLoc = intersectDenseMaps(EnvA.DeclToLoc, EnvB.DeclToLoc);
 652
 653   JoinedEnv.ExprToLoc = intersectDenseMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
 654
 655   // FIXME: update join to detect backedges and simplify the flow condition
 656   // accordingly.
 657   JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions(
 658       EnvA.FlowConditionToken, EnvB.FlowConditionToken);
 659
 660   JoinedEnv.ExprToVal = joinKeyToValueMap(EnvA.ExprToVal, EnvB.ExprToVal, EnvA,
 661                                           EnvB, JoinedEnv, Model);
 662
 663   JoinedEnv.LocToVal = joinKeyToValueMap(EnvA.LocToVal, EnvB.LocToVal, EnvA,
 664                                          EnvB, JoinedEnv, Model);
 665
 666   return JoinedEnv;
 667 }
 668
 669 StorageLocation &Environment::createStorageLocation(QualType Type) {
 670   return DACtx->createStorageLocation(Type);
 671 }
 672
 673 StorageLocation &Environment::createStorageLocation(const ValueDecl &D) {
 674   // Evaluated declarations are always assigned the same storage locations to
 675   // ensure that the environment stabilizes across loop iterations. Storage
 676   // locations for evaluated declarations are stored in the analysis context.
 677   return DACtx->getStableStorageLocation(D);
 678 }
 679
 680 StorageLocation &Environment::createStorageLocation(const Expr &E) {
 681   // Evaluated expressions are always assigned the same storage locations to
 682   // ensure that the environment stabilizes across loop iterations. Storage
 683   // locations for evaluated expressions are stored in the analysis context.
 684   return DACtx->getStableStorageLocation(E);
 685 }
 686
 687 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
 688   assert(!DeclToLoc.contains(&D));
 689   DeclToLoc[&D] = &Loc;
 690 }
 691
 692 StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
 693   auto It = DeclToLoc.find(&D);
 694   if (It == DeclToLoc.end())
 695     return nullptr;
 696
 697   StorageLocation *Loc = It->second;
 698
 699   return Loc;
 700 }
 701
 702 void Environment::removeDecl(const ValueDecl &D) { DeclToLoc.erase(&D); }
 703
 704 void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
 705   // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
 706   // but we still want to be able to associate a `StorageLocation` with them,
 707   // so allow these as an exception.
 708   assert(E.isGLValue() ||
 709          E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
 710   setStorageLocationInternal(E, Loc);
 711 }
 712
 713 StorageLocation *Environment::getStorageLocation(const Expr &E) const {
 714   // See comment in `setStorageLocation()`.
 715   assert(E.isGLValue() ||
 716          E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
 717   return getStorageLocationInternal(E);
 718 }
 719
 720 RecordStorageLocation *Environment::getThisPointeeStorageLocation() const {
 721   return ThisPointeeLoc;
 722 }
 723
 724 RecordStorageLocation &
 725 Environment::getResultObjectLocation(const Expr &RecordPRValue) {
 726   assert(RecordPRValue.getType()->isRecordType());
 727   assert(RecordPRValue.isPRValue());
 728
 729   if (StorageLocation *ExistingLoc = getStorageLocationInternal(RecordPRValue))
 730     return *cast<RecordStorageLocation>(ExistingLoc);
 731   auto &Loc = cast<RecordStorageLocation>(
 732       DACtx->getStableStorageLocation(RecordPRValue));
 733   setStorageLocationInternal(RecordPRValue, Loc);
 734   return Loc;
 735 }
 736
 737 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
 738   return DACtx->getOrCreateNullPointerValue(PointeeType);
 739 }
 740
 741 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
 742   assert(!isa<RecordValue>(&Val) || &cast<RecordValue>(&Val)->getLoc() == &Loc);
 743
 744   LocToVal[&Loc] = &Val;
 745 }
 746
 747 void Environment::setValue(const Expr &E, Value &Val) {
 748   assert(E.isPRValue());
 749   ExprToVal[&E] = &Val;
 750 }
 751
 752 Value *Environment::getValue(const StorageLocation &Loc) const {
 753   return LocToVal.lookup(&Loc);
 754 }
 755
 756 Value *Environment::getValue(const ValueDecl &D) const {
 757   auto *Loc = getStorageLocation(D);
 758   if (Loc == nullptr)
 759     return nullptr;
 760   return getValue(*Loc);
 761 }
 762
 763 Value *Environment::getValue(const Expr &E) const {
 764   if (E.isPRValue()) {
 765     auto It = ExprToVal.find(&ignoreCFGOmittedNodes(E));
 766     return It == ExprToVal.end() ? nullptr : It->second;
 767   }
 768
 769   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
 770   if (It == ExprToLoc.end())
 771     return nullptr;
 772   return getValue(*It->second);
 773 }
 774
 775 Value *Environment::createValue(QualType Type) {
 776   llvm::DenseSet<QualType> Visited;
 777   int CreatedValuesCount = 0;
 778   Value *Val = createValueUnlessSelfReferential(Type, Visited, /*Depth=*/0,
 779                                                 CreatedValuesCount);
 780   if (CreatedValuesCount > MaxCompositeValueSize) {
 781     llvm::errs() << "Attempting to initialize a huge value of type: " << Type
 782                  << '\n';
 783   }
 784   return Val;
 785 }
 786
 787 void Environment::setStorageLocationInternal(const Expr &E,
 788                                              StorageLocation &Loc) {
 789   const Expr &CanonE = ignoreCFGOmittedNodes(E);
 790   assert(!ExprToLoc.contains(&CanonE));
 791   ExprToLoc[&CanonE] = &Loc;
 792 }
 793
 794 StorageLocation *Environment::getStorageLocationInternal(const Expr &E) const {
 795   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
 796   return It == ExprToLoc.end() ? nullptr : &*It->second;
 797 }
 798
 799 Value *Environment::createValueUnlessSelfReferential(
 800     QualType Type, llvm::DenseSet<QualType> &Visited, int Depth,
 801     int &CreatedValuesCount) {
 802   assert(!Type.isNull());
 803   assert(!Type->isReferenceType());
 804
 805   // Allow unlimited fields at depth 1; only cap at deeper nesting levels.
 806   if ((Depth > 1 && CreatedValuesCount > MaxCompositeValueSize) ||
 807       Depth > MaxCompositeValueDepth)
 808     return nullptr;
 809
 810   if (Type->isBooleanType()) {
 811     CreatedValuesCount++;
 812     return &makeAtomicBoolValue();
 813   }
 814
 815   if (Type->isIntegerType()) {
 816     // FIXME: consider instead `return nullptr`, given that we do nothing useful
 817     // with integers, and so distinguishing them serves no purpose, but could
 818     // prevent convergence.
 819     CreatedValuesCount++;
 820     return &arena().create<IntegerValue>();
 821   }
 822
 823   if (Type->isPointerType()) {
 824     CreatedValuesCount++;
 825     QualType PointeeType = Type->getPointeeType();
 826     StorageLocation &PointeeLoc =
 827         createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount);
 828
 829     return &arena().create<PointerValue>(PointeeLoc);
 830   }
 831
 832   if (Type->isRecordType()) {
 833     CreatedValuesCount++;
 834     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
 835     for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
 836       assert(Field != nullptr);
 837
 838       QualType FieldType = Field->getType();
 839
 840       FieldLocs.insert(
 841           {Field, &createLocAndMaybeValue(FieldType, Visited, Depth + 1,
 842                                           CreatedValuesCount)});
 843     }
 844
 845     RecordStorageLocation &Loc =
 846         arena().create<RecordStorageLocation>(Type, std::move(FieldLocs));
 847     RecordValue &RecordVal = create<RecordValue>(Loc);
 848
 849     // As we already have a storage location for the `RecordValue`, we can and
 850     // should associate them in the environment.
 851     setValue(Loc, RecordVal);
 852
 853     return &RecordVal;
 854   }
 855
 856   return nullptr;
 857 }
 858
 859 StorageLocation &
 860 Environment::createLocAndMaybeValue(QualType Ty,
 861                                     llvm::DenseSet<QualType> &Visited,
 862                                     int Depth, int &CreatedValuesCount) {
 863   if (!Visited.insert(Ty.getCanonicalType()).second)
 864     return createStorageLocation(Ty.getNonReferenceType());
 865   Value *Val = createValueUnlessSelfReferential(
 866       Ty.getNonReferenceType(), Visited, Depth, CreatedValuesCount);
 867   Visited.erase(Ty.getCanonicalType());
 868
 869   Ty = Ty.getNonReferenceType();
 870
 871   if (Val == nullptr)
 872     return createStorageLocation(Ty);
 873
 874   if (Ty->isRecordType())
 875     return cast<RecordValue>(Val)->getLoc();
 876
 877   StorageLocation &Loc = createStorageLocation(Ty);
 878   setValue(Loc, *Val);
 879   return Loc;
 880 }
 881
 882 StorageLocation &Environment::createObjectInternal(const ValueDecl *D,
 883                                                    QualType Ty,
 884                                                    const Expr *InitExpr) {
 885   if (Ty->isReferenceType()) {
 886     // Although variables of reference type always need to be initialized, it
 887     // can happen that we can't see the initializer, so `InitExpr` may still
 888     // be null.
 889     if (InitExpr) {
 890       if (auto *InitExprLoc = getStorageLocation(*InitExpr))
 891           return *InitExprLoc;
 892     }
 893
 894     // Even though we have an initializer, we might not get an
 895     // InitExprLoc, for example if the InitExpr is a CallExpr for which we
 896     // don't have a function body. In this case, we just invent a storage
 897     // location and value -- it's the best we can do.
 898     return createObjectInternal(D, Ty.getNonReferenceType(), nullptr);
 899   }
 900
 901   Value *Val = nullptr;
 902   if (InitExpr)
 903     // In the (few) cases where an expression is intentionally
 904     // "uninterpreted", `InitExpr` is not associated with a value.  There are
 905     // two ways to handle this situation: propagate the status, so that
 906     // uninterpreted initializers result in uninterpreted variables, or
 907     // provide a default value. We choose the latter so that later refinements
 908     // of the variable can be used for reasoning about the surrounding code.
 909     // For this reason, we let this case be handled by the `createValue()`
 910     // call below.
 911     //
 912     // FIXME. If and when we interpret all language cases, change this to
 913     // assert that `InitExpr` is interpreted, rather than supplying a
 914     // default value (assuming we don't update the environment API to return
 915     // references).
 916     Val = getValue(*InitExpr);
 917   if (!Val)
 918     Val = createValue(Ty);
 919
 920   if (Ty->isRecordType())
 921     return cast<RecordValue>(Val)->getLoc();
 922
 923   StorageLocation &Loc =
 924       D ? createStorageLocation(*D) : createStorageLocation(Ty);
 925
 926   if (Val)
 927     setValue(Loc, *Val);
 928
 929   return Loc;
 930 }
 931
 932 void Environment::assume(const Formula &F) {
 933   DACtx->addFlowConditionConstraint(FlowConditionToken, F);
 934 }
 935
 936 bool Environment::proves(const Formula &F) const {
 937   return DACtx->flowConditionImplies(FlowConditionToken, F);
 938 }
 939
 940 bool Environment::allows(const Formula &F) const {
 941   return DACtx->flowConditionAllows(FlowConditionToken, F);
 942 }
 943
 944 void Environment::dump(raw_ostream &OS) const {
 945   // FIXME: add printing for remaining fields and allow caller to decide what
 946   // fields are printed.
 947   OS << "DeclToLoc:\n";
 948   for (auto [D, L] : DeclToLoc)
 949     OS << "  [" << D->getNameAsString() << ", " << L << "]\n";
 950
 951   OS << "ExprToLoc:\n";
 952   for (auto [E, L] : ExprToLoc)
 953     OS << "  [" << E << ", " << L << "]\n";
 954
 955   OS << "ExprToVal:\n";
 956   for (auto [E, V] : ExprToVal)
 957     OS << "  [" << E << ", " << V << ": " << *V << "]\n";
 958
 959   OS << "LocToVal:\n";
 960   for (auto [L, V] : LocToVal) {
 961     OS << "  [" << L << ", " << V << ": " << *V << "]\n";
 962   }
 963
 964   OS << "FlowConditionToken:\n";
 965   DACtx->dumpFlowCondition(FlowConditionToken, OS);
 966 }
 967
 968 void Environment::dump() const {
 969   dump(llvm::dbgs());
 970 }
 971
 972 RecordStorageLocation *getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
 973                                                  const Environment &Env) {
 974   Expr *ImplicitObject = MCE.getImplicitObjectArgument();
 975   if (ImplicitObject == nullptr)
 976     return nullptr;
 977   if (ImplicitObject->getType()->isPointerType()) {
 978     if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*ImplicitObject)))
 979       return &cast<RecordStorageLocation>(Val->getPointeeLoc());
 980     return nullptr;
 981   }
 982   return cast_or_null<RecordStorageLocation>(
 983       Env.getStorageLocation(*ImplicitObject));
 984 }
 985
 986 RecordStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
 987                                              const Environment &Env) {
 988   Expr *Base = ME.getBase();
 989   if (Base == nullptr)
 990     return nullptr;
 991   if (ME.isArrow()) {
 992     if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Base)))
 993       return &cast<RecordStorageLocation>(Val->getPointeeLoc());
 994     return nullptr;
 995   }
 996   return cast_or_null<RecordStorageLocation>(Env.getStorageLocation(*Base));
 997 }
 998
 999 std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD) {
1000   // Unnamed bitfields are only used for padding and do not appear in
1001   // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
1002   // field list, and we thus need to remove them before mapping inits to
1003   // fields to avoid mapping inits to the wrongs fields.
1004   std::vector<FieldDecl *> Fields;
1005   llvm::copy_if(
1006       RD->fields(), std::back_inserter(Fields),
1007       [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); });
1008   return Fields;
1009 }
1010
1011 RecordValue &refreshRecordValue(RecordStorageLocation &Loc, Environment &Env) {
1012   auto &NewVal = Env.create<RecordValue>(Loc);
1013   Env.setValue(Loc, NewVal);
1014   return NewVal;
1015 }
1016
1017 RecordValue &refreshRecordValue(const Expr &Expr, Environment &Env) {
1018   assert(Expr.getType()->isRecordType());
1019
1020   if (Expr.isPRValue()) {
1021     if (auto *ExistingVal = cast_or_null<RecordValue>(Env.getValue(Expr))) {
1022       auto &NewVal = Env.create<RecordValue>(ExistingVal->getLoc());
1023       Env.setValue(Expr, NewVal);
1024       return NewVal;
1025     }
1026
1027     auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType()));
1028     Env.setValue(Expr, NewVal);
1029     return NewVal;
1030   }
1031
1032   if (auto *Loc =
1033           cast_or_null<RecordStorageLocation>(Env.getStorageLocation(Expr))) {
1034     auto &NewVal = Env.create<RecordValue>(*Loc);
1035     Env.setValue(*Loc, NewVal);
1036     return NewVal;
1037   }
1038
1039   auto &NewVal = *cast<RecordValue>(Env.createValue(Expr.getType()));
1040   Env.setStorageLocation(Expr, NewVal.getLoc());
1041   return NewVal;
1042 }
1043
1044 } // namespace dataflow
1045 } // namespace clang