[clang][dataflow] Add action caching support to MatchSwitch

[sgatev]

Summary

Enable default caching of actionsin MatchSwitch so that for each
unique statement matchers are invoked at most once.

[ymandel]

What is the motivation for stashing the results of a match on a statement? Do we expect to encounter the same statement often?

I thought the concern was more specific to re-matching particular types, like std::optional. For that, we could lazily store the declaration nodes (like we do in https://github.com/llvm/llvm-project/blob/main/clang/lib/Analysis/FlowSensitive/Models/ChromiumCheckModel.cpp with CheckDecls). But, I'm less clear on the impact of storing the result of the match itself.

For the decls concern, I think we'll want evidence of the cost before we try to optimize it. The hasName matcher is already optimized, so I'm not sure how much we have to gain here. Something, but probably not a lot.

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

159

What is this function doing? Please add a comment. Also, I don't understand how it compiles -- the return type is std::function<void(State &)> but it returns a lambda of type (State &S) -> std::function<void(State &)>?

[sgatev]

Address comments.

[sgatev]

In D122121#3396022, @ymandel wrote:

What is the motivation for stashing the results of a match on a statement? Do we expect to encounter the same statement often?

The matcher is evaluated for each fixpoint iteration so I expect that we'll encounter the same statement as many times as there are iterations over the same basic block. Does that make sense?

I thought the concern was more specific to re-matching particular types, like std::optional. For that, we could lazily store the declaration nodes (like we do in https://github.com/llvm/llvm-project/blob/main/clang/lib/Analysis/FlowSensitive/Models/ChromiumCheckModel.cpp with CheckDecls). But, I'm less clear on the impact of storing the result of the match itself.

I was thinking that maybe we can split the problem in two:

1. duplicated work across matchDynamic calls, and
2. duplicated work within a single matchDynamic call.

This patch addresses 1. as I see it as responsibility of MatchSwitch. Your comment seems to be about 2., if I'm reading it correctly. Do you think it's possible and makes sense to solve it in the AST matcher framework? Would that address your concerns?

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

159

The outer lambda was a leftover. I removed it and added a comment.

[ymandel]

Much clearer now, thanks for the changes! The only real question I have is what's the best design for the cache -- lambda or explicit pair. I leave it up to you.

In D122121#3396096, @sgatev wrote:

In D122121#3396022, @ymandel wrote:

What is the motivation for stashing the results of a match on a statement? Do we expect to encounter the same statement often?

The matcher is evaluated for each fixpoint iteration so I expect that we'll encounter the same statement as many times as there are iterations over the same basic block. Does that make sense?

Yes, it does! Thanks for clarifying.

I thought the concern was more specific to re-matching particular types, like std::optional. For that, we could lazily store the declaration nodes (like we do in https://github.com/llvm/llvm-project/blob/main/clang/lib/Analysis/FlowSensitive/Models/ChromiumCheckModel.cpp with CheckDecls). But, I'm less clear on the impact of storing the result of the match itself.

I was thinking that maybe we can split the problem in two:

1. duplicated work across matchDynamic calls, and
2. duplicated work within a single matchDynamic call.

This patch addresses 1. as I see it as responsibility of MatchSwitch. Your comment seems to be about 2., if I'm reading it correctly.

Right. This division makes sense, particularly the point about responsibility. Point 2 is very much independent of MatchSwitch. But, I think matching the optional type is about both really in that every time we call the matcher we'll be checking the optional type, even if we only check it once *within* a single match. Still, fixing it doen't belong in MatchSwitch.

Do you think it's possible and makes sense to solve it in the AST matcher framework? Would that address your concerns?

Interesting idea -- basically, we'd need to build a caching mechanism into matchers based on names (identity really). That might make sense in general -- it's certainly a general concern -- but I'd be more inclined to try to fix it locally for now. That said, before we go there I'd want to profile the code, so no rush on this regardless.

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

162

nit: maybe replace Matcher with Action or SpecializedAction?

176–180

Given that we only use Actions and Index in Actions[Index], what about only stashing that? Similarly, for MatchResult?
e.g.

[&Action = Actions[Index], Result = ast_matchers::MatchFinder::MatchResult(Results[0], &Context), &Stmt] ...

Alternatively, cache the pair of Action, Result directly instead of caching a lambda. This saves the path through a std::function and might make the code more readable (although, that's a matter of taste).

[xazax.hun]

Thanks! Did you have a chance whether this makes a difference in real world scenarios? I'm mostly curious because I do not have a good mental model of how the matchers are implemented, specifically what optimizations are in place, so I don't really know how much of an impact can caching make :)

Once the rest of the comments are resolved this looks good to me.

In D122121#3396149, @ymandel wrote:

In D122121#3396096, @sgatev wrote:

I was thinking that maybe we can split the problem in two:

1. duplicated work across matchDynamic calls, and
2. duplicated work within a single matchDynamic call.

This patch addresses 1. as I see it as responsibility of MatchSwitch. Your comment seems to be about 2., if I'm reading it correctly.

Right. This division makes sense, particularly the point about responsibility. Point 2 is very much independent of MatchSwitch. But, I think matching the optional type is about both really in that every time we call the matcher we'll be checking the optional type, even if we only check it once *within* a single match. Still, fixing it doen't belong in MatchSwitch.

+1, I like how the problem was split. I also agree that MatchSwitch might not be the best place to fix #2 as a more broad fix would potentially benefit other parts of Clang, like Tidy. But speaking of other parts of Clang, I wonder whether MatchSwitch is something that could be part of the ASTMatcher library. Some people might find it useful for implementing tools other than flow sensitive checks. Although, I do not have a strong preference, I'm completely fine leaving it where it currently is.

[ymandel]

In D122121#3396688, @xazax.hun wrote:

Thanks! Did you have a chance whether this makes a difference in real world scenarios? I'm mostly curious because I do not have a good mental model of how the matchers are implemented, specifically what optimizations are in place, so I don't really know how much of an impact can caching make :)

In general, for clang-tidy style use, we've found that building the AST dwarfs the cost of the matchers, so there's limited room for performance improvements from the matchers themselves. That said, the hasName matcher is optimized in the case of qualified names, and I expect that was motivated by noticable performance costs from the easy version of just printing the fully qualified name of the type and comparing the strings.

The complication from caching is that it can only be done when we're sure that the name is unique. So, either its a fully qualified name, or the user (of the matcher) tells us explicitly that it can be cached. That might make the hasName interface a little clunkier, but maybe its worth it.

Once the rest of the comments are resolved this looks good to me.

In D122121#3396149, @ymandel wrote:

In D122121#3396096, @sgatev wrote:

I was thinking that maybe we can split the problem in two:

1. duplicated work across matchDynamic calls, and
2. duplicated work within a single matchDynamic call.

This patch addresses 1. as I see it as responsibility of MatchSwitch. Your comment seems to be about 2., if I'm reading it correctly.

Right. This division makes sense, particularly the point about responsibility. Point 2 is very much independent of MatchSwitch. But, I think matching the optional type is about both really in that every time we call the matcher we'll be checking the optional type, even if we only check it once *within* a single match. Still, fixing it doen't belong in MatchSwitch.

+1, I like how the problem was split. I also agree that MatchSwitch might not be the best place to fix #2 as a more broad fix would potentially benefit other parts of Clang, like Tidy. But speaking of other parts of Clang, I wonder whether MatchSwitch is something that could be part of the ASTMatcher library. Some people might find it useful for implementing tools other than flow sensitive checks. Although, I do not have a strong preference, I'm completely fine leaving it where it currently is.

I'll check w/ Aaron Ballman, one of the main contributors/reviewers for matchers these days.

clang/include/clang/Analysis/FlowSensitive/MatchSwitch.h

 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
 #include "clang/ASTMatchers/ASTMatchFinder.h"
 #include "clang/ASTMatchers/ASTMatchers.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/ErrorHandling.h"
 #include <functional>
 #include <string>
 #include <utility>
 #include <vector>
 
 namespace clang {
 namespace dataflow {
 
 /// A common form of state shared between the cases of a transfer function.
 template <typename LatticeT> struct TransferState {
   TransferState(LatticeT &Lattice, Environment &Env)
       : Lattice(Lattice), Env(Env) {}
 
   /// Current lattice element.
   LatticeT &Lattice;
   Environment &Env;
 };
 
 /// Matches against `Stmt` and, based on its structure, dispatches to an
 /// appropriate handler.
 template <typename State>
 using MatchSwitch = std::function<void(const Stmt &, ASTContext &, State &)>;
 
+/// Options that determine the behavior of a `MatchSwitchBuilder` instance.
+struct MatchSwitchBuildOptions {
+  /// If true, caches the action of a match for a given statement. As a result,
+  /// matchers will be invoked at most once for each unique statement.
+  ///
+  /// Note: This assumes that all invocations of `MatchSwitch` for a given
+  /// `Stmt` use the same `ASTContext`.
+  bool CacheActions = true;
+};
+
 /// Collects cases of a "match switch": a collection of matchers paired with
 /// callbacks, which together define a switch that can be applied to a
 /// `Stmt`. This structure can simplify the definition of `transfer` functions
 /// that rely on pattern-matching.
 ///
 /// For example, consider an analysis that handles particular function calls. It
 /// can define the `MatchSwitch` once, in the constructor of the analysis, and
 /// then reuse it each time that `transfer` is called, with a fresh state value.
CaseOf(ast_matchers::internal::Matcher<Stmt> M,
     Matchers.push_back(std::move(M));
     Actions.push_back(
         [A = std::move(A)](const Stmt *Stmt,
                            const ast_matchers::MatchFinder::MatchResult &R,
                            State &S) { A(cast<Node>(Stmt), R, S); });
     return std::move(*this);
   }
 
-  MatchSwitch<State> Build() && {
+  MatchSwitch<State> Build(MatchSwitchBuildOptions Options = {}) && {
+    if (!Options.CacheActions) {
       return [Matcher = BuildMatcher(), Actions = std::move(Actions)](
                  const Stmt &Stmt, ASTContext &Context, State &S) {
-      auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context);
-      if (Results.empty())
-        return;
-      // Look through the map for the first binding of the form "TagN..." use
-      // that to select the action.
-      for (const auto &Element : Results[0].getMap()) {
-        llvm::StringRef ID(Element.first);
-        size_t Index = 0;
-        if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) &&
-            Index < Actions.size()) {
-          Actions[Index](
-              &Stmt,
-              ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S);
-          return;
-        }
-      }
+        if (auto M = BuildMatcherForStmt(Matcher, Actions, Stmt, Context))
+          M(S);
+      };
+    return
+        [Cache = llvm::DenseMap<const Stmt *, std::function<void(State &)>>(),
+         Matcher = BuildMatcher(), Actions = std::move(Actions)](
+            const Stmt &Stmt, ASTContext &Context, State &S) mutable {
+          auto Res = Cache.try_emplace(&Stmt, nullptr);
+          if (Res.second)
+            Res.first->second =
+                BuildMatcherForStmt(Matcher, Actions, Stmt, Context);
+          if (Res.first->second != nullptr)
+            Res.first->second(S);
         };
   }
 
 private:
   ast_matchers::internal::DynTypedMatcher BuildMatcher() {
     using ast_matchers::anything;
     using ast_matchers::stmt;
     using ast_matchers::unless;
     using ast_matchers::internal::DynTypedMatcher;
ast_matchers::internal::DynTypedMatcher BuildMatcher() {
     }
     // The matcher type on the cases ensures that `Expr` kind is compatible with
     // all of the matchers.
     return DynTypedMatcher::constructVariadic(
         DynTypedMatcher::VO_AnyOf, ASTNodeKind::getFromNodeKind<Stmt>(),
         std::move(Matchers));
   }
 
+  using Action = std::function<void(
+      const Stmt *, const ast_matchers::MatchFinder::MatchResult &, State &)>;
+
+  static std::function<void(State &)>
+  BuildMatcherForStmt(const ast_matchers::internal::DynTypedMatcher &Matcher,
+                      const std::vector<Action> &Actions, const Stmt &Stmt,
+                      ASTContext &Context) {
+    return [&Stmt, &Context, &Matcher,
+            &Actions](State &S) -> std::function<void(State &)> {
+      auto Results = ast_matchers::matchDynamic(Matcher, Stmt, Context);
+      if (Results.empty()) {
+        return nullptr;
+      }
+
+      // Look through the map for the first binding of the form "TagN..." use
+      // that to select the action.
+      for (const auto &Element : Results[0].getMap()) {
+        llvm::StringRef ID(Element.first);
+        size_t Index = 0;
+        if (ID.consume_front("Tag") && !ID.getAsInteger(10, Index) &&
+            Index < Actions.size()) {
+          Actions[Index](
+              &Stmt,
+              ast_matchers::MatchFinder::MatchResult(Results[0], &Context), S);
+          return [&Actions, Index, &Stmt, Res = std::move(Results[0]),
+                  &Context](State &S) {
+            Actions[Index](
+                &Stmt, ast_matchers::MatchFinder::MatchResult(Res, &Context),
+                S);
+          };
+        }
+      }
+
+      llvm_unreachable("Unhandled result in MatchSwitch!");
+    };
+  }
+
   std::vector<ast_matchers::internal::DynTypedMatcher> Matchers;
-  std::vector<std::function<void(
-      const Stmt *, const ast_matchers::MatchFinder::MatchResult &, State &)>>
-      Actions;
+  std::vector<Action> Actions;
 };
+
 } // namespace dataflow
 } // namespace clang
+
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_MATCHSWITCH_H_

clang/lib/Analysis/FlowSensitive/Models/UncheckedOptionalAccessModel.cpp

 
 void transferNulloptAssignment(const CXXOperatorCallExpr *E,
                                const MatchFinder::MatchResult &,
                                LatticeTransferState &State) {
   transferAssignment(E, State.Env.getBoolLiteralValue(false), State);
 }
 
 auto buildTransferMatchSwitch() {
-  // FIXME: Evaluate the efficiency of matchers. If using matchers results in a
-  // lot of duplicated work (e.g. string comparisons), consider providing APIs
-  // that avoid it through memoization.
   return MatchSwitchBuilder<LatticeTransferState>()
       // Attach a symbolic "has_value" state to optional values that we see for
       // the first time.
       .CaseOf<Expr>(expr(anyOf(declRefExpr(), memberExpr()), hasOptionalType()),
                     initializeOptionalReference)
 
       // make_optional
       .CaseOf<CallExpr>(isMakeOptionalCall(), transferMakeOptionalCall)

clang/unittests/Analysis/FlowSensitive/MatchSwitchTest.cpp

 
 void TransferSetFalse(const Stmt *,
                       const ast_matchers::MatchFinder::MatchResult &,
                       TransferState<BooleanLattice> &State) {
   State.Lattice = BooleanLattice(false);
 }
 
 class TestAnalysis : public DataflowAnalysis<TestAnalysis, BooleanLattice> {
+  bool CacheMatchSwitchActions;
   MatchSwitch<TransferState<BooleanLattice>> TransferSwitch;
 
 public:
+  TestAnalysis(ASTContext &ASTCtx, bool CacheMatchSwitchActions)
+      : DataflowAnalysis<TestAnalysis, BooleanLattice>(ASTCtx),
+        CacheMatchSwitchActions(CacheMatchSwitchActions) {}
+
   explicit TestAnalysis(ASTContext &Context)
       : DataflowAnalysis<TestAnalysis, BooleanLattice>(Context) {
     using namespace ast_matchers;
+    MatchSwitchBuildOptions BuildOptions;
+    BuildOptions.CacheActions = CacheMatchSwitchActions;
     TransferSwitch =
         MatchSwitchBuilder<TransferState<BooleanLattice>>()
             .CaseOf<DeclRefExpr>(declRefExpr(to(varDecl(hasName("X")))),
                                  TransferSetTrue)
             .CaseOf<Stmt>(callExpr(callee(functionDecl(hasName("Foo")))),
                           TransferSetFalse)
-            .Build();
+            .Build(std::move(BuildOptions));
   }
 
   static BooleanLattice initialElement() { return BooleanLattice::bottom(); }
 
   void transfer(const Stmt *S, BooleanLattice &L, Environment &Env) {
     TransferState<BooleanLattice> State(L, Env);
     TransferSwitch(*S, getASTContext(), State);
   }
 };
 
-class MatchSwitchTest : public ::testing::Test {
+class MatchSwitchTest : public ::testing::TestWithParam<bool> {
 protected:
   template <typename Matcher>
   void RunDataflow(llvm::StringRef Code, Matcher Expectations) {
     ASSERT_THAT_ERROR(
         test::checkDataflow<TestAnalysis>(
             Code, "fun",
             [](ASTContext &C, Environment &) { return TestAnalysis(C); },
             [&Expectations](
                 llvm::ArrayRef<std::pair<
                     std::string, DataflowAnalysisState<TestAnalysis::Lattice>>>
                     Results,
                 ASTContext &) { EXPECT_THAT(Results, Expectations); },
             {"-fsyntax-only", "-std=c++17"}),
         llvm::Succeeded());
   }
 };
 
-TEST_F(MatchSwitchTest, JustX) {
+INSTANTIATE_TEST_SUITE_P(MatchSwitchTestInst, MatchSwitchTest,
+                         ::testing::Bool());
+
+TEST_P(MatchSwitchTest, JustX) {
   std::string Code = R"(
     void fun() {
       int X = 1;
       (void)X;
       // [[p]]
     }
   )";
   RunDataflow(Code,
               UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true)))));
 }
 
-TEST_F(MatchSwitchTest, JustFoo) {
+TEST_P(MatchSwitchTest, JustFoo) {
   std::string Code = R"(
     void Foo();
     void fun() {
       Foo();
       // [[p]]
     }
   )";
   RunDataflow(Code,
               UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
 }
 
-TEST_F(MatchSwitchTest, XThenFoo) {
+TEST_P(MatchSwitchTest, XThenFoo) {
   std::string Code = R"(
     void Foo();
     void fun() {
       int X = 1;
       (void)X;
       Foo();
       // [[p]]
     }
   )";
   RunDataflow(Code,
               UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
 }
 
-TEST_F(MatchSwitchTest, FooThenX) {
+TEST_P(MatchSwitchTest, FooThenX) {
   std::string Code = R"(
     void Foo();
     void fun() {
       Foo();
       int X = 1;
       (void)X;
       // [[p]]
     }
   )";
   RunDataflow(Code,
               UnorderedElementsAre(Pair("p", Holds(BooleanLattice(true)))));
 }
 
-TEST_F(MatchSwitchTest, Neither) {
+TEST_P(MatchSwitchTest, Neither) {
   std::string Code = R"(
     void Bar();
     void fun(bool b) {
       Bar();
       // [[p]]
     }
   )";
   RunDataflow(Code,
               UnorderedElementsAre(Pair("p", Holds(BooleanLattice(false)))));
 }