[clang][dataflow] Add an option for context-sensitive depth

[samestep]

Summary

This patch adds a Depth field (default value 2) to ContextSensitiveOptions, allowing context-sensitive analysis of functions that call other functions. This also requires replacing the DeclCtx field on Environment with a CallString field that contains a vector of decl contexts, to ensure that the analysis doesn't try to analyze recursive or mutually recursive calls (which would result in a crash, due to the way we handle StorageLocations).

[sgatev]

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

395

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

210

If canDescend is supposed to return false for MaxDepth = 0, shouldn't this be <?

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

4033

Let's add a similar test with Depth set to 0.

[xazax.hun]

Once the Stanislav's comments are resolved, it looks good to me.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

665

Alternatively, canDescend could get the optional ContextSensitiveOpts and we can do all the checking there.

[samestep]

clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp

210

I don't follow; could you clarify? The CallStack should always be nonempty.

clang/lib/Analysis/FlowSensitive/Transfer.cpp

665

Ah, good idea!

[samestep]

clang/lib/Analysis/FlowSensitive/Transfer.cpp

665

Oh... actually that doesn't work quite so nicely, because it introduces a circular dependency between Transfer.h and DataflowEnvironment.h. I'll leave it as-is for now.

[samestep]

Address Stanislav's comments

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

public:
   void addToFlowCondition(BoolValue &Val);
 
   /// Returns true if and only if the clauses that constitute the flow condition
   /// imply that `Val` is true.
   bool flowConditionImplies(BoolValue &Val) const;
 
   /// Returns the `DeclContext` of the block being analysed, if any. Otherwise,
   /// returns null.
-  const DeclContext *getDeclCtx() { return DeclCtx; }
+  const DeclContext *getDeclCtx() { return CallStack.back(); }
 
-  /// Sets the `DeclContext` of the block being analysed.
-  void setDeclCtx(const DeclContext *Ctx) { DeclCtx = Ctx; }
+  /// Returns whether this `Environment` can be extended to analyze the given
+  /// `Callee` (i.e. if `pushCall` can be used), with recursion disallowed and a
+  /// given `MaxDepth`.
+  bool canDescend(unsigned MaxDepth, const DeclContext *Callee) const;
 
   /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise,
   /// returns null.
   const ControlFlowContext *getControlFlowContext(const FunctionDecl *F) {
     return DACtx->getControlFlowContext(F);
   }
 
   LLVM_DUMP_METHOD void dump() const;
private:
   /// of the caller.
   void pushCallInternal(const FunctionDecl *FuncDecl,
                         ArrayRef<const Expr *> Args);
 
   // `DACtx` is not null and not owned by this object.
   DataflowAnalysisContext *DACtx;
 
   // `DeclContext` of the block being analysed if provided.
-  const DeclContext *DeclCtx = nullptr;
+  std::vector<const DeclContext *> CallStack;
 
   // In a properly initialized `Environment`, `ReturnLoc` should only be null if
   // its `DeclContext` could not be cast to a `FunctionDecl`.
   StorageLocation *ReturnLoc = nullptr;
   // The storage location of the `this` pointee. Should only be null if the
   // function being analyzed is only a function and not a method.
   StorageLocation *ThisPointeeLoc = nullptr;
 

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

 
 #include "clang/AST/Stmt.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "llvm/ADT/Optional.h"
 
 namespace clang {
 namespace dataflow {
 
-struct ContextSensitiveOptions {};
+struct ContextSensitiveOptions {
+  /// The maximum depth to analyze. A value of zero is equivalent to disabling
+  /// context-sensitive analysis entirely.
+  unsigned Depth = 2;
+};
 
 struct TransferOptions {
   /// Options for analyzing function bodies when present in the translation
   /// unit, or empty to disable context-sensitive analysis. Note that this is
   /// fundamentally limited: some constructs, such as recursion, are explicitly
   /// unsupported.
   llvm::Optional<ContextSensitiveOptions> ContextSensitiveOpts;
 };

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), DeclCtx(Other.DeclCtx), ReturnLoc(Other.ReturnLoc),
-      ThisPointeeLoc(Other.ThisPointeeLoc), DeclToLoc(Other.DeclToLoc),
-      ExprToLoc(Other.ExprToLoc), LocToVal(Other.LocToVal),
-      MemberLocToStruct(Other.MemberLocToStruct),
+    : DACtx(Other.DACtx), CallStack(Other.CallStack),
+      ReturnLoc(Other.ReturnLoc), ThisPointeeLoc(Other.ThisPointeeLoc),
+      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);
   return *this;
 }
 
 Environment::Environment(DataflowAnalysisContext &DACtx,
-                         const DeclContext &DeclCtxArg)
+                         const DeclContext &DeclCtx)
     : Environment(DACtx) {
-  setDeclCtx(&DeclCtxArg);
+  CallStack.push_back(&DeclCtx);
 
-  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(DeclCtx)) {
+  if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
     assert(FuncDecl->getBody() != nullptr);
     initGlobalVars(*FuncDecl->getBody(), *this);
     for (const auto *ParamDecl : FuncDecl->parameters()) {
       assert(ParamDecl != nullptr);
       auto &ParamLoc = createStorageLocation(*ParamDecl);
       setStorageLocation(*ParamDecl, ParamLoc);
       if (Value *ParamVal = createValue(ParamDecl->getType()))
         setValue(ParamLoc, *ParamVal);
     }
 
     QualType ReturnType = FuncDecl->getReturnType();
     ReturnLoc = &createStorageLocation(ReturnType);
   }
 
-  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(DeclCtx)) {
+  if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
     auto *Parent = MethodDecl->getParent();
     assert(Parent != nullptr);
     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()) {
         ThisPointeeLoc = &createStorageLocation(ThisPointeeType);
         if (Value *ThisPointeeVal = createValue(ThisPointeeType))
           setValue(*ThisPointeeLoc, *ThisPointeeVal);
       }
     }
   }
 }
 
+bool Environment::canDescend(unsigned MaxDepth,
+                             const DeclContext *Callee) const {
+  return CallStack.size() <= MaxDepth &&
+         std::find(CallStack.begin(), CallStack.end(), Callee) ==
+             CallStack.end();
+}
+
 Environment Environment::pushCall(const CallExpr *Call) const {
   Environment Env(*this);
 
   // FIXME: Support references here.
   Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
 
   if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
     if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
Environment Environment::pushCall(const CXXConstructExpr *Call) const {
   Env.pushCallInternal(Call->getConstructor(),
                        llvm::makeArrayRef(Call->getArgs(), Call->getNumArgs()));
 
   return Env;
 }
 
 void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
                                    ArrayRef<const Expr *> Args) {
-  setDeclCtx(FuncDecl);
+  CallStack.push_back(FuncDecl);
 
   // 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();
 
   // FIXME: Parameters don't always map to arguments 1:1; examples include
   // overloaded operators implemented as member functions, and parameter packs.
bool Environment::equivalentTo(const Environment &Other,
   return true;
 }
 
 LatticeJoinEffect Environment::join(const Environment &Other,
                                     Environment::ValueModel &Model) {
   assert(DACtx == Other.DACtx);
   assert(ReturnLoc == Other.ReturnLoc);
   assert(ThisPointeeLoc == Other.ThisPointeeLoc);
-  assert(DeclCtx == Other.DeclCtx);
+  assert(CallStack == Other.CallStack);
 
   auto Effect = LatticeJoinEffect::Unchanged;
 
   Environment JoinedEnv(*DACtx);
 
-  JoinedEnv.setDeclCtx(DeclCtx);
+  JoinedEnv.CallStack = CallStack;
   JoinedEnv.ReturnLoc = ReturnLoc;
   JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
 
   JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
   if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
     Effect = LatticeJoinEffect::Changed;
 
   JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);

clang/lib/Analysis/FlowSensitive/Transfer.cpp

BoolValue &getLogicOperatorSubExprValue(const Expr &SubExpr) {
     // boolean value for it.
     return Env.makeAtomicBoolValue();
   }
 
   // If context sensitivity is enabled, try to analyze the body of the callee
   // `F` of `S`. The type `E` must be either `CallExpr` or `CXXConstructExpr`.
   template <typename E>
   void transferInlineCall(const E *S, const FunctionDecl *F) {
-    if (!Options.ContextSensitiveOpts)
+    if (!(Options.ContextSensitiveOpts &&
+          Env.canDescend(Options.ContextSensitiveOpts->Depth, F)))
       return;
 
     const ControlFlowContext *CFCtx = Env.getControlFlowContext(F);
     if (!CFCtx)
       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`
void transferInlineCall(const E *S, const FunctionDecl *F) {
     auto CalleeEnv = Env.pushCall(S);
 
     // FIXME: Use the same analysis as the caller for the callee. Note,
     // though, that doing so would require support for changing the analysis's
     // ASTContext.
     assert(CFCtx->getDecl() != nullptr &&
            "ControlFlowContexts in the environment should always carry a decl");
     auto Analysis = NoopAnalysis(CFCtx->getDecl()->getASTContext(),
-                                 DataflowAnalysisOptions());
+                                 DataflowAnalysisOptions{Options});
 
     auto BlockToOutputState =
         dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
     assert(BlockToOutputState);
     assert(ExitBlock < BlockToOutputState->size());
 
     auto ExitState = (*BlockToOutputState)[ExitBlock];
     assert(ExitState);

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 auto &FooVal =
                     *cast<BoolValue>(Env.getValue(*FooDecl, SkipPast::None));
                 EXPECT_FALSE(Env.flowConditionImplies(FooVal));
                 EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal)));
               },
               {TransferOptions{/*.ContextSensitiveOpts=*/llvm::None}});
 }
 
+TEST(TransferTest, ContextSensitiveDepthZero) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool(bool &Var) { Var = true; }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool(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)));
+              },
+              {TransferOptions{ContextSensitiveOptions{/*.Depth=*/0}}});
+}
+
 TEST(TransferTest, ContextSensitiveSetTrue) {
   std::string Code = R"(
     bool GiveBool();
     void SetBool(bool &Var) { Var = true; }
 
     void target() {
       bool Foo = GiveBool();
       SetBool(Foo);
runDataflow(Code,
                 auto &BarVal =
                     *cast<BoolValue>(Env.getValue(*BarDecl, SkipPast::None));
                 EXPECT_FALSE(Env.flowConditionImplies(BarVal));
                 EXPECT_TRUE(Env.flowConditionImplies(Env.makeNot(BarVal)));
               },
               {TransferOptions{ContextSensitiveOptions{}}});
 }
 
-TEST(TransferTest, ContextSensitiveSetTwoLayers) {
+TEST(TransferTest, ContextSensitiveSetTwoLayersDepthOne) {
   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);
runDataflow(Code,
                 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)));
               },
-              {TransferOptions{ContextSensitiveOptions{}}});
+              {TransferOptions{ContextSensitiveOptions{/*.Depth=*/1}}});
+}
+
+TEST(TransferTest, ContextSensitiveSetTwoLayersDepthTwo) {
+  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_TRUE(Env.flowConditionImplies(FooVal));
+              },
+              {TransferOptions{ContextSensitiveOptions{/*.Depth=*/2}}});
+}
+
+TEST(TransferTest, ContextSensitiveSetThreeLayersDepthTwo) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool1(bool &Var) { Var = true; }
+    void SetBool2(bool &Var) { SetBool1(Var); }
+    void SetBool3(bool &Var) { SetBool2(Var); }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool3(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)));
+              },
+              {TransferOptions{ContextSensitiveOptions{/*.Depth=*/2}}});
+}
+
+TEST(TransferTest, ContextSensitiveSetThreeLayersDepthThree) {
+  std::string Code = R"(
+    bool GiveBool();
+    void SetBool1(bool &Var) { Var = true; }
+    void SetBool2(bool &Var) { SetBool1(Var); }
+    void SetBool3(bool &Var) { SetBool2(Var); }
+
+    void target() {
+      bool Foo = GiveBool();
+      SetBool3(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_TRUE(Env.flowConditionImplies(FooVal));
+              },
+              {TransferOptions{ContextSensitiveOptions{/*.Depth=*/3}}});
+}
+
+TEST(TransferTest, ContextSensitiveMutualRecursion) {
+  std::string Code = R"(
+    bool Pong(bool X, bool Y);
+
+    bool Ping(bool X, bool Y) {
+      if (X) {
+        return Y;
+      } else {
+        return Pong(!X, Y);
+      }
+    }
+
+    bool Pong(bool X, bool Y) {
+      if (Y) {
+        return X;
+      } else {
+        return Ping(X, !Y);
+      }
+    }
+
+    void target() {
+      bool Foo = Ping(false, false);
+      // [[p]]
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                // The analysis doesn't crash...
+                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));
+                // ... but it also can't prove anything here.
+                EXPECT_FALSE(Env.flowConditionImplies(FooVal));
+                EXPECT_FALSE(Env.flowConditionImplies(Env.makeNot(FooVal)));
+              },
+              {TransferOptions{ContextSensitiveOptions{/*.Depth=*/4}}});
 }
 
 TEST(TransferTest, ContextSensitiveSetMultipleLines) {
   std::string Code = R"(
     void SetBools(bool &Var1, bool &Var2) {
       Var1 = true;
       Var2 = false;
     }