[clang][dataflow] Add cache of `ControlFlowContext`s for function decls.

[ymandel]

Summary

This patch modifies context-sensitive analysis of functions to use a cache,
rather than recreate the ControlFlowContext from a function decl on each
encounter. However, this is just step 1 (of N) in adding support for a
configurable map of "modeled" function decls. The map will go from the actual
function decl to the ControlFlowContext used to model it. Only functions
pre-configured in the map will be modeled in a context-sensitive way.

We start with a cache because it introduces the desired map, while retaining the
current behavior. Here, functions are mapped to their actual implementations
(when available).

[sgatev]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

34

Can we make them references?

55–57

Can we make it a reference?

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

369

Can we make the keys FunctionDecl * and use FunctionDecl::getDefinition in getControlFlowContext to obtain a canonical pointer?

[samestep]

Looks awesome, thanks @ymandel!

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

23

I'm guessing this change is unrelated to the patch as a whole?

[ymandel]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

34

Turns out I was wrong - D can be null. Would that CFG has comments about what its parameters do... We have a test that excercises this (though I can't say why):

https://github.com/llvm/llvm-project/blob/9a976f36615dbe15e76c12b22f711b2e597a8e51/clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp#L70

The other two -- yes -- but then we'd have to update the various callers as well. I'd rather not do that in this patch, but I'll add the new overload and we can follow up with cleanups in another patch.

55–57

See above.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

23

correct. it was a driveby fix (for better or worse).

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

369

We can for now -- for the purposes of the cache that makes the most sense. I thought of strings because the goal is a map from *specific* (named) functions, for which we won't a priori have the function decls. still, I'll change for now and we can change it back (or to a better implementation) in the follow up patches.

[ymandel]

addressed comments

[ymandel]

adusted interface to return (nullable) pointer rather than reference.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

34

Weird. I think we should change the test to pass the decl.

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

369

Perhaps FunctionContexts?

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

19

Is this still needed?

[ymandel]

update.

[ymandel]

tweaks.

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

34

I'd like that, but when looking through other uses found a bunch that pass nullptr (and for no apparent reason - they all have the function decl handy).

So, I propose that we mark the new API as such and then in the cleanup we'll make sure to pass a non-null argument.

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

19

Nope.

[ymandel]

comments

[xazax.hun]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

38

I think LLVM can use the [[deprecated]] attribute.

63–65

This starts to look more and more similar to AnalysisDeclContext. I wonder if at some point we should factor the common code out into a common base class or something.

[ymandel]

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

38

Thanks -- I verifed and it works. But, it produces warnings which I'm afraid may be a problem with some builds. So, I want to hold off until I can clean up all of our uses.

63–65

Agreed. Filed issue #56932.

clang/include/clang/Analysis/FlowSensitive/ControlFlowContext.h

 
 namespace clang {
 namespace dataflow {
 
 /// Holds CFG and other derived context that is needed to perform dataflow
 /// analysis.
 class ControlFlowContext {
 public:
-  /// Builds a ControlFlowContext from an AST node.
+  /// Builds a ControlFlowContext from an AST node. `D` is the function in which
+  /// `S` resides and must not be null.
+  static llvm::Expected<ControlFlowContext> build(const Decl *D, Stmt &S,
+                                                  ASTContext &C);
+
+  // DEPRECATED. Use overload above.
   static llvm::Expected<ControlFlowContext> build(const Decl *D, Stmt *S,
                                                   ASTContext *C);
 
+  /// Returns the `Decl` containing the statement used to construct the CFG, if
+  /// available.
+  const Decl *getDecl() const { return ContainingDecl; }
+
   /// Returns the CFG that is stored in this context.
   const CFG &getCFG() const { return *Cfg; }
 
   /// Returns a mapping from statements to basic blocks that contain them.
   const llvm::DenseMap<const Stmt *, const CFGBlock *> &getStmtToBlock() const {
     return StmtToBlock;
   }
 
 private:
-  ControlFlowContext(std::unique_ptr<CFG> Cfg,
+  // FIXME: Once the deprecated `build` method is removed, mark `D` as "must not
+  // be null" and add an assertion.
+  ControlFlowContext(const Decl *D, std::unique_ptr<CFG> Cfg,
                      llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock)
-      : Cfg(std::move(Cfg)), StmtToBlock(std::move(StmtToBlock)) {}
+      : ContainingDecl(D), Cfg(std::move(Cfg)),
+        StmtToBlock(std::move(StmtToBlock)) {}
 
+  /// The `Decl` containing the statement used to construct the CFG.
+  const Decl *ContainingDecl;
   std::unique_ptr<CFG> Cfg;
   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_CONTROLFLOWCONTEXT_H

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysis.h

 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H
 
 #include <iterator>
 #include <utility>
 #include <vector>
 
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Stmt.h"
-#include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Error.h"
 

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

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/TypeOrdering.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.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 <memory>
public:
 
   /// Returns true if `Val1` is equivalent to `Val2`.
   /// Note: This function doesn't take into account constraints on `Val1` and
   /// `Val2` imposed by the flow condition.
   bool equivalentBoolValues(BoolValue &Val1, BoolValue &Val2);
 
   LLVM_DUMP_METHOD void dumpFlowCondition(AtomicBoolValue &Token);
 
+  /// Returns the `ControlFlowContext` registered for `F`, if any. Otherwise,
+  /// returns null.
+  const ControlFlowContext *getControlFlowContext(const FunctionDecl *F);
+
 private:
   struct NullableQualTypeDenseMapInfo : private llvm::DenseMapInfo<QualType> {
     static QualType getEmptyKey() {
       // Allow a NULL `QualType` by using a different value as the empty key.
       return QualType::getFromOpaquePtr(reinterpret_cast<Type *>(1));
     }
 
     using DenseMapInfo::getHashValue;
private:
   // condition.
   //
   // Flow conditions depend on other flow conditions if they are created using
   // `forkFlowCondition` or `joinFlowConditions`. The graph of flow condition
   // dependencies is stored in the `FlowConditionDeps` map.
   llvm::DenseMap<AtomicBoolValue *, llvm::DenseSet<AtomicBoolValue *>>
       FlowConditionDeps;
   llvm::DenseMap<AtomicBoolValue *, BoolValue *> FlowConditionConstraints;
+
+  llvm::DenseMap<const FunctionDecl *, ControlFlowContext> FunctionContexts;
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSISCONTEXT_H

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

 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/Type.h"
+#include "clang/Analysis/FlowSensitive/ControlFlowContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/Analysis/FlowSensitive/DataflowLattice.h"
 #include "clang/Analysis/FlowSensitive/StorageLocation.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include <memory>
 #include <type_traits>
public:
 
   /// Adds `Val` to the set of clauses that constitute the flow condition.
   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 `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:
   /// Creates a value appropriate for `Type`, if `Type` is supported, otherwise
   /// return null.
   ///
   /// Recursively initializes storage locations and values until it sees a
   /// self-referential pointer or reference type. `Visited` is used to track

clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

for (const CFGBlock *Block : Cfg) {
     }
     if (const Stmt *TerminatorStmt = Block->getTerminatorStmt())
       StmtToBlock[TerminatorStmt] = Block;
   }
   return StmtToBlock;
 }
 
 llvm::Expected<ControlFlowContext>
-ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) {
+ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) {
   CFG::BuildOptions Options;
   Options.PruneTriviallyFalseEdges = false;
   Options.AddImplicitDtors = true;
   Options.AddTemporaryDtors = true;
   Options.AddInitializers = true;
   Options.AddCXXDefaultInitExprInCtors = true;
 
   // Ensure that all sub-expressions in basic blocks are evaluated.
   Options.setAllAlwaysAdd();
 
-  auto Cfg = CFG::buildCFG(D, S, C, Options);
+  auto Cfg = CFG::buildCFG(D, &S, &C, Options);
   if (Cfg == nullptr)
     return llvm::createStringError(
         std::make_error_code(std::errc::invalid_argument),
         "CFG::buildCFG failed");
 
   llvm::DenseMap<const Stmt *, const CFGBlock *> StmtToBlock =
       buildStmtToBasicBlockMap(*Cfg);
-  return ControlFlowContext(std::move(Cfg), std::move(StmtToBlock));
+  return ControlFlowContext(D, std::move(Cfg), std::move(StmtToBlock));
+}
+
+llvm::Expected<ControlFlowContext>
+ControlFlowContext::build(const Decl *D, Stmt *S, ASTContext *C) {
+  assert(S != nullptr);
+  assert(C != nullptr);
+  return build(D, *S, *C);
 }
 
 } // namespace dataflow
 } // namespace clang

clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp

 //  dataflow analysis.
 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Analysis/FlowSensitive/DataflowAnalysisContext.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/Analysis/FlowSensitive/DebugSupport.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
 #include "llvm/Support/Debug.h"
 #include <cassert>
 #include <memory>
 #include <utility>
 
 namespace clang {
 namespace dataflow {
 
 StorageLocation &DataflowAnalysisContext::createStorageLocation(QualType Type) {
void DataflowAnalysisContext::dumpFlowCondition(AtomicBoolValue &Token) {
   addTransitiveFlowConditionConstraints(Token, Constraints, VisitedTokens);
 
   llvm::DenseMap<const AtomicBoolValue *, std::string> AtomNames = {
       {&getBoolLiteralValue(false), "False"},
       {&getBoolLiteralValue(true), "True"}};
   llvm::dbgs() << debugString(Constraints, AtomNames);
 }
 
+const ControlFlowContext *
+DataflowAnalysisContext::getControlFlowContext(const FunctionDecl *F) {
+  // Canonicalize the key:
+  F = F->getDefinition();
+  if (F == nullptr)
+    return nullptr;
+  auto It = FunctionContexts.find(F);
+  if (It != FunctionContexts.end())
+    return &It->second;
+
+  if (Stmt *Body = F->getBody()) {
+    auto CFCtx = ControlFlowContext::build(F, *Body, F->getASTContext());
+    // FIXME: Handle errors.
+    assert(CFCtx);
+    auto Result = FunctionContexts.insert({F, std::move(*CFCtx)});
+    return &Result.first->second;
+  }
+
+  return nullptr;
+}
+
 } // namespace dataflow
 } // namespace clang
 
 using namespace clang;
 
 const Expr &clang::dataflow::ignoreCFGOmittedNodes(const Expr &E) {
   const Expr *Current = &E;
   if (auto *EWC = dyn_cast<ExprWithCleanups>(Current)) {

clang/lib/Analysis/FlowSensitive/Transfer.cpp

if (S->isCallToStdMove()) {
       assert(S->getArg(0) != nullptr);
       // `__builtin_expect` returns by-value, so strip away any potential
       // 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)
+      // This case is for context-sensitive analysis.
+      if (!Options.ContextSensitive)
+        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`
       // 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);
+      // 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());
 
       auto BlockToOutputState =
           dataflow::runDataflowAnalysis(*CFCtx, Analysis, CalleeEnv);
       assert(BlockToOutputState);
       assert(ExitBlock < BlockToOutputState->size());
 
       auto ExitState = (*BlockToOutputState)[ExitBlock];
       assert(ExitState);