[clang][dataflow] Separate context by frame

[samestep]

Summary

This patch enables context-sensitive analysis of multiple different calls to the same function (see the ContextSensitiveSetBothTrueAndFalse example in the TransferTest suite) by moving the DeclToLoc, ExprToLoc, and ThisPointeeLoc fields (along with their associated methods) from the DataflowAnalysisContext class into a new StorageFrame class, replacing them with a Frames map keyed by std::vector<const CallExpr *>. The only other change necessary was to replace the copy-assignment with a call to the new popCall method on Environment, which std::moves some fields but specifically does not move DeclToLoc and ExprToLoc from the callee back to the caller.

This approach still does not yet work for recursive calls, such as the example pointed out by @xazax.hun in D130306#3670259; that should be addressable in a followup by limiting the CallString depth.

[samestep]

Use operator[] instead of try_emplace for C++14 compatibility

[xazax.hun]

While separate call strings are properly isolated from each other, repeated analysis of the same call is not:|

while (...)
{
  foo(...);
}

In the above code snippet, we will end up analyzing foo with leftover state from the previous iteration. The analysis can potentially observe state private to the previous call in the current call. Do I miss something or is this intentional?

[samestep]

In D130593#3681126, @xazax.hun wrote:

While separate call strings are properly isolated from each other, repeated analysis of the same call is not:|

while (...)
{
  foo(...);
}

In the above code snippet, we will end up analyzing foo with leftover state from the previous iteration. The analysis can potentially observe state private to the previous call in the current call. Do I miss something or is this intentional?

Sorry, I originally misread your message and thought you were asking about recursion, not iteration. The answer is yes, this is intentional, in the same way that we use a stable StorageLocation for a variable used inside of a loop.

old message:

Correct, you didn't miss something. I'm not really sure of the best way to deal with this; in the short term, my plan is to only allow analysis of a callee when it is not already present in the call-string. @ymandel any ideas for the longer term?

[samestep]

Note: after some discussion with @ymandel, we've decided to adjust our design for this. A new patch is on the way which will replace this one.

[samestep]

Here is the new patch: D130726

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h

 #include "clang/AST/TypeOrdering.h"
 #include "clang/Analysis/FlowSensitive/Solver.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/Support/Compiler.h"
 #include <cassert>
+#include <map>
 #include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace dataflow {
 
 /// Skip past nodes that the CFG does not emit. These nodes are invisible to
 /// flow-sensitive analysis, and should be ignored as they will effectively not
 /// exist.
 ///
 ///   * `ParenExpr` - The CFG takes the operator precedence into account, but
 ///   otherwise omits the node afterwards.
 ///
 ///   * `ExprWithCleanups` - The CFG will generate the appropriate calls to
 ///   destructors and then omit the node.
 ///
 const Expr &ignoreCFGOmittedNodes(const Expr &E);
 const Stmt &ignoreCFGOmittedNodes(const Stmt &S);
 
 /// Returns the set of all fields in the type.
 llvm::DenseSet<const FieldDecl *> getObjectFields(QualType Type);
 
-/// Owns objects that encompass the state of a program and stores context that
-/// is used during dataflow analysis.
-class DataflowAnalysisContext {
-public:
-  /// Constructs a dataflow analysis context.
-  ///
-  /// Requirements:
-  ///
-  ///  `S` must not be null.
-  DataflowAnalysisContext(std::unique_ptr<Solver> S)
-      : S(std::move(S)), TrueVal(createAtomicBoolValue()),
-        FalseVal(createAtomicBoolValue()) {
-    assert(this->S != nullptr);
-  }
-
-  /// Takes ownership of `Loc` and returns a reference to it.
-  ///
-  /// Requirements:
-  ///
-  ///  `Loc` must not be null.
-  template <typename T>
-  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
-  takeOwnership(std::unique_ptr<T> Loc) {
-    assert(Loc != nullptr);
-    Locs.push_back(std::move(Loc));
-    return *cast<T>(Locs.back().get());
-  }
-
-  /// Takes ownership of `Val` and returns a reference to it.
-  ///
-  /// Requirements:
-  ///
-  ///  `Val` must not be null.
-  template <typename T>
-  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
-  takeOwnership(std::unique_ptr<T> Val) {
-    assert(Val != nullptr);
-    Vals.push_back(std::move(Val));
-    return *cast<T>(Vals.back().get());
-  }
-
-  /// Returns a stable storage location appropriate for `Type`.
-  ///
-  /// Requirements:
-  ///
-  ///  `Type` must not be null.
-  StorageLocation &getStableStorageLocation(QualType Type);
-
-  /// Returns a stable storage location for `D`.
-  StorageLocation &getStableStorageLocation(const VarDecl &D);
-
-  /// Returns a stable storage location for `E`.
-  StorageLocation &getStableStorageLocation(const Expr &E);
+/// A sequence of method calls that resembles the call stack.
+using CallString = std::vector<const CallExpr *>;
 
+/// Holds stable storage locations in the context of a particular `CallString`.
+class StorageFrame {
+public:
   /// Assigns `Loc` as the storage location of `D`.
   ///
   /// Requirements:
   ///
   ///  `D` must not be assigned a storage location.
   void setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
     assert(DeclToLoc.find(&D) == DeclToLoc.end());
     DeclToLoc[&D] = &Loc;
public:
   }
 
   /// Returns the storage location assigned to the `this` pointee or null if the
   /// `this` pointee has no assigned storage location.
   StorageLocation *getThisPointeeStorageLocation() const {
     return ThisPointeeLoc;
   }
 
+private:
+  // Maps from program declarations and statements to storage locations that are
+  // assigned to them. These assignments are global (aggregated across all basic
+  // blocks) and are used to produce stable storage locations when the same
+  // basic blocks are evaluated multiple times. The storage locations that are
+  // in scope for a particular basic block are stored in `Environment`.
+  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
+  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
+
+  StorageLocation *ThisPointeeLoc = nullptr;
+};
+
+/// Owns objects that encompass the state of a program and stores context that
+/// is used during dataflow analysis.
+class DataflowAnalysisContext {
+public:
+  /// Constructs a dataflow analysis context.
+  ///
+  /// Requirements:
+  ///
+  ///  `S` must not be null.
+  DataflowAnalysisContext(std::unique_ptr<Solver> S)
+      : S(std::move(S)), TrueVal(createAtomicBoolValue()),
+        FalseVal(createAtomicBoolValue()) {
+    assert(this->S != nullptr);
+  }
+
+  /// Takes ownership of `Loc` and returns a reference to it.
+  ///
+  /// Requirements:
+  ///
+  ///  `Loc` must not be null.
+  template <typename T>
+  typename std::enable_if<std::is_base_of<StorageLocation, T>::value, T &>::type
+  takeOwnership(std::unique_ptr<T> Loc) {
+    assert(Loc != nullptr);
+    Locs.push_back(std::move(Loc));
+    return *cast<T>(Locs.back().get());
+  }
+
+  /// Takes ownership of `Val` and returns a reference to it.
+  ///
+  /// Requirements:
+  ///
+  ///  `Val` must not be null.
+  template <typename T>
+  typename std::enable_if<std::is_base_of<Value, T>::value, T &>::type
+  takeOwnership(std::unique_ptr<T> Val) {
+    assert(Val != nullptr);
+    Vals.push_back(std::move(Val));
+    return *cast<T>(Vals.back().get());
+  }
+
+  /// Returns a stable storage location appropriate for `Type`.
+  ///
+  /// Requirements:
+  ///
+  ///  `Type` must not be null.
+  StorageLocation &getStableStorageLocation(const CallString &CallStr,
+                                            QualType Type);
+
+  /// Returns a stable storage location for `D`.
+  StorageLocation &getStableStorageLocation(const CallString &CallStr,
+                                            const VarDecl &D);
+
+  /// Returns a stable storage location for `E`.
+  StorageLocation &getStableStorageLocation(const CallString &CallStr,
+                                            const Expr &E);
+
+  StorageFrame &getFrame(const CallString &CallStr);
+
   /// Returns a pointer value that represents a null pointer. Calls with
   /// `PointeeType` that are canonically equivalent will return the same result.
   /// A null `PointeeType` can be used for the pointee of `std::nullptr_t`.
   PointerValue &getOrCreateNullPointerValue(QualType PointeeType);
 
   /// Returns a symbolic boolean value that models a boolean literal equal to
   /// `Value`.
   AtomicBoolValue &getBoolLiteralValue(bool Value) const {
BoolValue &buildAndSubstituteFlowConditionWithCache(
       llvm::DenseMap<BoolValue *, BoolValue *> &SubstitutionsCache);
 
   std::unique_ptr<Solver> S;
 
   // Storage for the state of a program.
   std::vector<std::unique_ptr<StorageLocation>> Locs;
   std::vector<std::unique_ptr<Value>> Vals;
 
-  // Maps from program declarations and statements to storage locations that are
-  // assigned to them. These assignments are global (aggregated across all basic
-  // blocks) and are used to produce stable storage locations when the same
-  // basic blocks are evaluated multiple times. The storage locations that are
-  // in scope for a particular basic block are stored in `Environment`.
-  llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
-  llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
-
-  StorageLocation *ThisPointeeLoc = nullptr;
+  std::map<CallString, StorageFrame> Frames;
 
   // Null pointer values, keyed by the canonical pointee type.
   //
   // FIXME: The pointer values are indexed by the pointee types which are
   // required to initialize the `PointeeLoc` field in `PointerValue`. Consider
   // creating a type-independent `NullPointerValue` without a `PointeeLoc`
   // field.
   llvm::DenseMap<QualType, PointerValue *, NullableQualTypeDenseMapInfo>

clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h

public:
   ///
   ///  The body of the callee must not reference globals.
   ///
   ///  The arguments of `Call` must map 1:1 to the callee's parameters.
   ///
   ///  Each argument of `Call` must already have a `StorageLocation`.
   Environment pushCall(const CallExpr *Call) const;
 
+  /// Moves gathered information back into `this` from a `CalleeEnv` created via
+  /// `pushCall`.
+  void popCall(const Environment &CalleeEnv);
+
   /// Returns true if and only if the environment is equivalent to `Other`, i.e
   /// the two environments:
   ///  - have the same mappings from declarations to storage locations,
   ///  - have the same mappings from expressions to storage locations,
   ///  - have the same or equivalent (according to `Model`) values assigned to
   ///    the same storage locations.
   ///
   /// Requirements:
Value *createValueUnlessSelfReferential(QualType Type,
                                           llvm::DenseSet<QualType> &Visited,
                                           int Depth, int &CreatedValuesCount);
 
   StorageLocation &skip(StorageLocation &Loc, SkipPast SP) const;
   const StorageLocation &skip(const StorageLocation &Loc, SkipPast SP) const;
 
   // `DACtx` is not null and not owned by this object.
   DataflowAnalysisContext *DACtx;
+  CallString CallStr;
 
   // Maps from program declarations and statements to storage locations that are
   // assigned to them. Unlike the maps in `DataflowAnalysisContext`, these
   // include only storage locations that are in scope for a particular basic
   // block.
   llvm::DenseMap<const ValueDecl *, StorageLocation *> DeclToLoc;
   llvm::DenseMap<const Expr *, StorageLocation *> ExprToLoc;
 

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

 #include <cassert>
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 StorageLocation &
-DataflowAnalysisContext::getStableStorageLocation(QualType Type) {
+DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr,
+                                                  QualType Type) {
   if (!Type.isNull() &&
       (Type->isStructureOrClassType() || Type->isUnionType())) {
     // FIXME: Explore options to avoid eager initialization of fields as some of
     // them might not be needed for a particular analysis.
     llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
     for (const FieldDecl *Field : getObjectFields(Type))
-      FieldLocs.insert({Field, &getStableStorageLocation(Field->getType())});
+      FieldLocs.insert(
+          {Field, &getStableStorageLocation(CallStr, Field->getType())});
     return takeOwnership(
         std::make_unique<AggregateStorageLocation>(Type, std::move(FieldLocs)));
   }
   return takeOwnership(std::make_unique<ScalarStorageLocation>(Type));
 }
 
 StorageLocation &
-DataflowAnalysisContext::getStableStorageLocation(const VarDecl &D) {
-  if (auto *Loc = getStorageLocation(D))
+DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr,
+                                                  const VarDecl &D) {
+  StorageFrame &Frame = getFrame(CallStr);
+  if (auto *Loc = Frame.getStorageLocation(D))
     return *Loc;
-  auto &Loc = getStableStorageLocation(D.getType());
-  setStorageLocation(D, Loc);
+  auto &Loc = getStableStorageLocation(CallStr, D.getType());
+  Frame.setStorageLocation(D, Loc);
   return Loc;
 }
 
 StorageLocation &
-DataflowAnalysisContext::getStableStorageLocation(const Expr &E) {
-  if (auto *Loc = getStorageLocation(E))
+DataflowAnalysisContext::getStableStorageLocation(const CallString &CallStr,
+                                                  const Expr &E) {
+  StorageFrame &Frame = getFrame(CallStr);
+  if (auto *Loc = Frame.getStorageLocation(E))
     return *Loc;
-  auto &Loc = getStableStorageLocation(E.getType());
-  setStorageLocation(E, Loc);
+  auto &Loc = getStableStorageLocation(CallStr, E.getType());
+  Frame.setStorageLocation(E, Loc);
   return Loc;
 }
 
+StorageFrame &DataflowAnalysisContext::getFrame(const CallString &CallStr) {
+  return Frames[CallStr];
+}
+
 PointerValue &
 DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) {
   auto CanonicalPointeeType =
       PointeeType.isNull() ? PointeeType : PointeeType.getCanonicalType();
   auto Res = NullPointerVals.try_emplace(CanonicalPointeeType, nullptr);
   if (Res.second) {
-    auto &PointeeLoc = getStableStorageLocation(CanonicalPointeeType);
+    // We arbitrarily put this in the outermost context; doesn't really matter.
+    auto &PointeeLoc = getStableStorageLocation({}, CanonicalPointeeType);
     Res.first->second =
         &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
   }
   return *Res.first->second;
 }
 
 static std::pair<BoolValue *, BoolValue *>
 makeCanonicalBoolValuePair(BoolValue &LHS, BoolValue &RHS) {

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (auto *DS = dyn_cast<DeclStmt>(&S)) {
     initGlobalVar(*E->getMemberDecl(), Env);
   }
 }
 
 Environment::Environment(DataflowAnalysisContext &DACtx)
     : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
 
 Environment::Environment(const Environment &Other)
-    : DACtx(Other.DACtx), DeclToLoc(Other.DeclToLoc),
+    : DACtx(Other.DACtx), CallStr(Other.CallStr), DeclToLoc(Other.DeclToLoc),
       ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal),
       MemberLocToStruct(Other.MemberLocToStruct),
       FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
 }
 
 Environment &Environment::operator=(const Environment &Other) {
   Environment Copy(Other);
   *this = std::move(Copy);
if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
     if (Parent->isLambda())
       MethodDecl = dyn_cast<CXXMethodDecl>(Parent->getDeclContext());
 
     if (MethodDecl && !MethodDecl->isStatic()) {
       QualType ThisPointeeType = MethodDecl->getThisObjectType();
       // FIXME: Add support for union types.
       if (!ThisPointeeType->isUnionType()) {
         auto &ThisPointeeLoc = createStorageLocation(ThisPointeeType);
-        DACtx.setThisPointeeStorageLocation(ThisPointeeLoc);
+        DACtx.getFrame(CallStr).setThisPointeeStorageLocation(ThisPointeeLoc);
         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
           setValue(ThisPointeeLoc, *ThisPointeeVal);
       }
     }
   }
 }
 
 Environment Environment::pushCall(const CallExpr *Call) const {
   Environment Env(*this);
+  Env.CallStr.push_back(Call);
 
   // FIXME: Currently this only works if the callee is never a method and the
   // same callee is never analyzed from multiple separate callsites. To
   // generalize this, we'll need to store a "context" field (probably a stack of
   // `const CallExpr *`s) in the `Environment`, and then change the
   // `DataflowAnalysisContext` class to hold a map from contexts to "frames",
   // where each frame stores its own version of what are currently the
   // `DeclToLoc`, `ExprToLoc`, and `ThisPointeeLoc` fields.
for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) {
     auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
     assert(ArgLoc != nullptr);
     Env.setStorageLocation(*Param, *ArgLoc);
   }
 
   return Env;
 }
 
+void Environment::popCall(const Environment &CalleeEnv) {
+  // We ignore `DACtx` because it's already the same in both. We don't want the
+  // callee's `CallStr` because it is one level deeper than ours. We don't bring
+  // back `DeclToLoc` and `ExprToLoc` because their mappings are only valid for
+  // the `CallStr` in `CalleeEnv`, and we want to be able to later analyze the
+  // same callee in a different context.
+  this->LocToVal = std::move(CalleeEnv.LocToVal);
+  this->MemberLocToStruct = std::move(CalleeEnv.MemberLocToStruct);
+  this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
+}
+
 bool Environment::equivalentTo(const Environment &Other,
                                Environment::ValueModel &Model) const {
   assert(DACtx == Other.DACtx);
 
   if (DeclToLoc != Other.DeclToLoc)
     return false;
 
   if (ExprToLoc != Other.ExprToLoc)
if (LocToVal.size() != JoinedEnv.LocToVal.size())
     Effect = LatticeJoinEffect::Changed;
 
   *this = std::move(JoinedEnv);
 
   return Effect;
 }
 
 StorageLocation &Environment::createStorageLocation(QualType Type) {
-  return DACtx->getStableStorageLocation(Type);
+  return DACtx->getStableStorageLocation(CallStr, Type);
 }
 
 StorageLocation &Environment::createStorageLocation(const VarDecl &D) {
   // Evaluated declarations are always assigned the same storage locations to
   // ensure that the environment stabilizes across loop iterations. Storage
   // locations for evaluated declarations are stored in the analysis context.
-  return DACtx->getStableStorageLocation(D);
+  return DACtx->getStableStorageLocation(CallStr, D);
 }
 
 StorageLocation &Environment::createStorageLocation(const Expr &E) {
   // Evaluated expressions are always assigned the same storage locations to
   // ensure that the environment stabilizes across loop iterations. Storage
   // locations for evaluated expressions are stored in the analysis context.
-  return DACtx->getStableStorageLocation(E);
+  return DACtx->getStableStorageLocation(CallStr, E);
 }
 
 void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
   assert(DeclToLoc.find(&D) == DeclToLoc.end());
   DeclToLoc[&D] = &Loc;
 }
 
 StorageLocation *Environment::getStorageLocation(const ValueDecl &D,

 StorageLocation *Environment::getStorageLocation(const Expr &E,
                                                  SkipPast SP) const {
   // FIXME: Add a test with parens.
   auto It = ExprToLoc.find(&ignoreCFGOmittedNodes(E));
   return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
 }
 
 StorageLocation *Environment::getThisPointeeStorageLocation() const {
-  return DACtx->getThisPointeeStorageLocation();
+  return DACtx->getFrame(CallStr).getThisPointeeStorageLocation();
 }
 
 PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
   return DACtx->getOrCreateNullPointerValue(PointeeType);
 }
 
 void Environment::setValue(const StorageLocation &Loc, Value &Val) {
   LocToVal[&Loc] = &Val;

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (S->isCallToStdMove()) {
       auto BlockToOutputState =
           dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
       assert(BlockToOutputState);
       assert(ExitBlock < BlockToOutputState->size());
 
       auto ExitState = (*BlockToOutputState)[ExitBlock];
       assert(ExitState);
 
-      Env = ExitState->Env;
+      Env.popCall(ExitState->Env);
     }
   }
 
   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 auto &FooVal =
                     *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
                 EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(FooVal)));
               },
               {/*.ApplyBuiltinTransfer=*/true,
                /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
 }
 
+TEST(TransferTest, ContextSensitiveSetBothTrueAndFalse) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool(bool &Var, bool Val) { Var = Val; }
+
+    void target() {
+      bool Foo = GiveBool();
+      bool Bar = GiveBool();
+      SetBool(Foo, true);
+      SetBool(Bar, false);
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const Environment &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(FooVal));
+                EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal)));
+
+                auto &BarVal =
+                    *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
+                EXPECT_FALSE(Env.flowConditionImplies(BarVal));
+                EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal)));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
 } // namespace