[clang][dataflow] Handle multiple context-sensitive calls to the same function

[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 replacing the Environment copy-assignment with a call to the new popCall method, which std::moves some fields but specifically does not move DeclToLoc and ExprToLoc from the callee back to the caller.

To enable this, the StorageLocation for a given parameter needs to be stable across different calls to the same function, so this patch also improves the modeling of parameter initialization, using ReferenceValue when necessary (for arguments passed by reference).

This approach explicitly does not work for recursive calls, because we currently only plan to use this context-sensitive machinery to support specialized analysis models we write, not analysis of arbitrary callees.

[ymandel]

Looks great!

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

227

maybe mention in the patch description that it also improves the modeling of parameter initialization?

236

Add an else that calls createValue on the decl's type, and then sets it, like VisitDeclStmt?

249

Maybe add something like "Conceptually, these maps capture information from the local scope, so when popping that scope, we do not propagate the maps".

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

3963

Are there more scenarios testable at this point? e.g

1. 2 layers of callees
2. more than one line of code inside the body?
3. one than one CFG block in the body?

If so, please add tests for those that are supported.

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

227

Good point; done.

236

Ah yes, I meant to do this before but forgot; will do that now.

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

3963

1. This currently isn't supported.
2. This should work.
3. This should work.

For (2) and (3), should I add those tests now, or do that in a followup patch?

[samestep]

Address some of Yitzie's comments

[ymandel]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

3963

1. This currently isn't supported.

What's limiting us here? Just curious, not asking you to update the comments, etc.

2. This should work.
3. This should work.

For (2) and (3), should I add those tests now, or do that in a followup patch?

may as well add them now. thx

3963

1. This currently isn't supported.
2. This should work.
3. This should work.

For (2) and (3), should I add those tests now, or do that in a followup patch?

[samestep]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

3963

What's limiting us here? Just curious, not asking you to update the comments, etc.

Nothing's really limiting us; all I meant was that currently we don't turn on context-sensitivity for the sub-analysis when we analyze the callee, and I don't want to turn that on until I've added support both for limiting the depth and for selecting the set of symbols to analyze using an allowlist.

[xazax.hun]

I'd love to see some comments in the source code to make sure one will not use these facilities for other purposes that would not work. Alternatively, ContextSensitive option could be renamed to NonRecursiveContextSensitive.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

512–513

Since we do not support recursion (and only do inlining with the depth of one), I think we should have a check here to avoid a inlining recursive call.

[samestep]

Add more comments and tests

[ymandel]

Nice work!

[sgatev]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

252

Does std::move help here? CalleeEnv is a const reference.

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:

clang/include/clang/Analysis/FlowSensitive/Transfer.h

 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 
 namespace clang {
 namespace dataflow {
 
 struct TransferOptions {
   /// Determines whether to analyze function bodies when present in the
-  /// translation unit.
+  /// translation unit. Note: this is currently only meant to be used for
+  /// inlining of specialized model code, not for context-sensitive analysis of
+  /// arbitrary subject code. In particular, some fundamentals such as recursion
+  /// are explicitly unsupported.
   bool ContextSensitive = false;
 };
 
 /// Maps statements to the environments of basic blocks that contain them.
 class StmtToEnvMap {
 public:
   virtual ~StmtToEnvMap() = default;
 

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

if (MethodDecl && !MethodDecl->isStatic()) {
       }
     }
   }
 }
 
 Environment Environment::pushCall(const CallExpr *Call) const {
   Environment Env(*this);
 
-  // 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.
-
   const auto *FuncDecl = Call->getDirectCallee();
   assert(FuncDecl != nullptr);
   const auto *Body = FuncDecl->getBody();
   assert(Body != nullptr);
   // FIXME: In order to allow the callee to reference globals, we probably need
   // to call `initGlobalVars` here in some way.
 
   auto ParamIt = FuncDecl->param_begin();
   auto ParamEnd = FuncDecl->param_end();
   auto ArgIt = Call->arg_begin();
   auto ArgEnd = Call->arg_end();
 
   // FIXME: Parameters don't always map to arguments 1:1; examples include
   // overloaded operators implemented as member functions, and parameter packs.
   for (; ArgIt != ArgEnd; ++ParamIt, ++ArgIt) {
     assert(ParamIt != ParamEnd);
 
-    const VarDecl *Param = *ParamIt;
     const Expr *Arg = *ArgIt;
     auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::Reference);
     assert(ArgLoc != nullptr);
-    Env.setStorageLocation(*Param, *ArgLoc);
+
+    const VarDecl *Param = *ParamIt;
+    auto &Loc = Env.createStorageLocation(*Param);
+    Env.setStorageLocation(*Param, Loc);
+
+    QualType ParamType = Param->getType();
+    if (ParamType->isReferenceType()) {
+      auto &Val = Env.takeOwnership(std::make_unique<ReferenceValue>(*ArgLoc));
+      Env.setValue(Loc, Val);
+    } else if (auto *ArgVal = Env.getValue(*ArgLoc)) {
+      Env.setValue(Loc, *ArgVal);
+    } else if (Value *Val = Env.createValue(ParamType)) {
+      Env.setValue(Loc, *Val);
+    }
   }
 
   return Env;
 }
 
+void Environment::popCall(const Environment &CalleeEnv) {
+  // We ignore `DACtx` because it's already the same in both. We don't bring
+  // back `DeclToLoc` and `ExprToLoc` because we want to be able to later
+  // analyze the same callee in a different context, and `setStorageLocation`
+  // requires there to not already be a storage location assigned. Conceptually,
+  // these maps capture information from the local scope, so when popping that
+  // scope, we do not propagate the maps.
+  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)

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (S->isCallToStdMove()) {
       // references in the argument.
       auto *ArgLoc = Env.getStorageLocation(*S->getArg(0), SkipPast::Reference);
       if (ArgLoc == nullptr)
         return;
       Env.setStorageLocation(*S, *ArgLoc);
     } else if (const FunctionDecl *F = S->getDirectCallee()) {
       // This case is for context-sensitive analysis, which we only do if we
       // have the callee body available in the translation unit.
       if (!Options.ContextSensitive || F->getBody() == nullptr)
         return;
 
+      // FIXME: We don't support context-sensitive analysis of recursion, so
+      // we should return early here if `F` is the same as the `FunctionDecl`
+      // holding `S` itself.
+
       auto &ASTCtx = F->getASTContext();
 
       // FIXME: Cache these CFGs.
       auto CFCtx = ControlFlowContext::build(F, F->getBody(), &ASTCtx);
       // FIXME: Handle errors here and below.
       assert(CFCtx);
       auto ExitBlock = CFCtx->getCFG().getExit().getBlockID();
 
       auto CalleeEnv = Env.pushCall(S);
 
       // FIXME: Use the same analysis as the caller for the callee.
       DataflowAnalysisOptions Options;
       auto Analysis = NoopAnalysis(ASTCtx, Options);
 
       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}});
+}
+
+TEST(TransferTest, ContextSensitiveSetTwoLayers) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool1(bool &Var) { Var = true; }
+    void SetBool2(bool &Var) { SetBool1(Var); }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool2(Foo);
+      // [[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());
+
+                auto &FooVal =
+                    *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
+                EXPECT_FALSE(Env.flowConditionImplies(FooVal));
+                EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal)));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
+TEST(TransferTest, ContextSensitiveSetMultipleLines) {
+  std::string Code = R"(
+    void SetBools(bool &Var1, bool &Var2) {
+      Var1 = true;
+      Var2 = false;
+    }
+
+    void target() {
+      bool Foo = false;
+      bool Bar = true;
+      SetBools(Foo, Bar);
+      // [[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}});
+}
+
+TEST(TransferTest, ContextSensitiveSetMultipleBlocks) {
+  std::string Code = R"(
+    void IfCond(bool Cond, bool &Then, bool &Else) {
+      if (Cond) {
+        Then = true;
+      } else {
+        Else = true;
+      }
+    }
+
+    void target() {
+      bool Foo = false;
+      bool Bar = false;
+      bool Baz = false;
+      IfCond(Foo, Bar, Baz);
+      // [[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 *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                const ValueDecl *BazDecl = findValueDecl(ASTCtx, "Baz");
+                ASSERT_THAT(BazDecl, NotNull());
+
+                auto &BarVal =
+                    *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
+                EXPECT_FALSE(Env.flowConditionImplies(BarVal));
+                EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal)));
+
+                auto &BazVal =
+                    *cast<BoolValue>(Env.getValue(*BazDecl, SkipPast::None));
+                EXPECT_TRUE(Env.flowConditionImplies(BazVal));
+                EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(BazVal)));
+              },
+              {/*.ApplyBuiltinTransfer=*/true,
+               /*.BuiltinTransferOptions=*/{/*.ContextSensitive=*/true}});
+}
+
 } // namespace