[clang][dataflow] Allow clients to disable built-in transfer functions.

[ymandel]

Summary

These built-in functions build the (sophisticated) model of the code's
memory. This model isn't used by all analyses, so we provide for disabling it to
avoid incurring the costs associated with its construction.

[sgatev]

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

44

We use /// to start a doc comment.

45

Let's add a FIXME to consider removing this if the framework gains support for composite analyses.

80

We use /// to start a doc comment.

82

Make this member const?

clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h

42–48

We use /// to start a doc comment.

[ymandel]

addressed comments

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

 ///     the object is equal to the argument.
 template <typename Derived, typename LatticeT>
 class DataflowAnalysis : public TypeErasedDataflowAnalysis {
 public:
   /// Bounded join-semilattice that is used in the analysis.
   using Lattice = LatticeT;
 
   explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
+  explicit DataflowAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
+      : TypeErasedDataflowAnalysis(ApplyBuiltinTransfer), Context(Context) {}
 
   ASTContext &getASTContext() final { return Context; }
 
   TypeErasedLattice typeErasedInitialElement() final {
     return {static_cast<Derived *>(this)->initialElement()};
   }
 
   LatticeJoinEffect joinTypeErased(TypeErasedLattice &E1,

clang/include/clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h

 ///  The type of the object stored in the container must be a bounded
 ///  join-semilattice.
 struct TypeErasedLattice {
   llvm::Any Value;
 };
 
 /// Type-erased base class for dataflow analyses built on a single lattice type.
 class TypeErasedDataflowAnalysis : public Environment::Merger {
+  /// Determines whether to apply the built-in transfer functions.
+  // FIXME: Remove this option once the framework supports composing analyses
+  // (at which point the built-in transfer functions can be simply a standalone
+  // analysis).
+  bool ApplyBuiltinTransfer;
+
 public:
+  TypeErasedDataflowAnalysis() : ApplyBuiltinTransfer(true) {}
+  TypeErasedDataflowAnalysis(bool ApplyBuiltinTransfer)
+      : ApplyBuiltinTransfer(ApplyBuiltinTransfer) {}
+
   virtual ~TypeErasedDataflowAnalysis() {}
 
   /// Returns the `ASTContext` that is used by the analysis.
   virtual ASTContext &getASTContext() = 0;
 
   /// Returns a type-erased lattice element that models the initial state of a
   /// basic block.
   virtual TypeErasedLattice typeErasedInitialElement() = 0;
 
   /// Joins two type-erased lattice elements by computing their least upper
   /// bound. Places the join result in the left element and returns an effect
   /// indicating whether any changes were made to it.
   virtual LatticeJoinEffect joinTypeErased(TypeErasedLattice &,
                                            const TypeErasedLattice &) = 0;
 
   /// Returns true if and only if the two given type-erased lattice elements are
   /// equal.
   virtual bool isEqualTypeErased(const TypeErasedLattice &,
                                  const TypeErasedLattice &) = 0;
 
   /// Applies the analysis transfer function for a given statement and
   /// type-erased lattice element.
   virtual void transferTypeErased(const Stmt *, TypeErasedLattice &,
                                   Environment &) = 0;
+
+  /// Determines whether to apply the built-in transfer functions, which model
+  /// the heap and stack in the `Environment`.
+  bool applyBuiltinTransfer() const { return ApplyBuiltinTransfer; }
 };
 
 /// Type-erased model of the program at a given program point.
 struct TypeErasedDataflowAnalysisState {
   /// Type-erased model of a program property.
   TypeErasedLattice Lattice;
 
   /// Model of the state of the program (store and heap).

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 transferCFGStmt(const CFGStmt &CfgStmt, TypeErasedDataflowAnalysis &Analysis,
                 TypeErasedDataflowAnalysisState &State,
                 std::function<void(const CFGStmt &,
                                    const TypeErasedDataflowAnalysisState &)>
                     HandleTransferredStmt) {
   const Stmt *S = CfgStmt.getStmt();
   assert(S != nullptr);
 
+  if (Analysis.applyBuiltinTransfer())
     transfer(*S, State.Env);
   Analysis.transferTypeErased(S, State.Lattice, State.Env);
 
   if (HandleTransferredStmt != nullptr)
     HandleTransferredStmt(CfgStmt, State);
 }
 
 /// Transfers `State` by evaluating `CfgInit`.
 static void transferCFGInitializer(const CFGInitializer &CfgInit,
TypeErasedDataflowAnalysisState State =
       computeBlockInputState(CFCtx, BlockStates, Block, InitEnv, Analysis);
   for (const CFGElement &Element : Block) {
     switch (Element.getKind()) {
     case CFGElement::Statement:
       transferCFGStmt(*Element.getAs<CFGStmt>(), Analysis, State,
                       HandleTransferredStmt);
       break;
     case CFGElement::Initializer:
+      if (Analysis.applyBuiltinTransfer())
         transferCFGInitializer(*Element.getAs<CFGInitializer>(), State);
       break;
     default:
       // FIXME: Evaluate other kinds of `CFGElement`.
       break;
     }
   }
   return State;
 }

clang/unittests/Analysis/FlowSensitive/NoopAnalysis.h

 };
 
 inline std::ostream &operator<<(std::ostream &OS, const NoopLattice &) {
   return OS << "noop";
 }
 
 class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
 public:
-  NoopAnalysis(ASTContext &Context)
-      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
+  /// `ApplyBuiltinTransfer` controls whether to run the built-in transfer
+  /// functions that model memory during the analysis. Their results are not
+  /// used by `NoopAnalysis`, but tests that need to inspect the environment
+  /// should enable them.
+  NoopAnalysis(ASTContext &Context, bool ApplyBuiltinTransfer)
+      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context,
+                                                    ApplyBuiltinTransfer) {}
 
   static NoopLattice initialElement() { return {}; }
 
   void transfer(const Stmt *S, NoopLattice &E, Environment &Env) {}
 };
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_UNITTESTS_ANALYSIS_FLOWSENSITIVE_NOOPANALYSIS_H

clang/unittests/Analysis/FlowSensitive/TestingSupportTest.cpp

 
 void checkDataflow(
     llvm::StringRef Code, llvm::StringRef Target,
     std::function<void(llvm::ArrayRef<std::pair<
                            std::string, DataflowAnalysisState<NoopLattice>>>,
                        ASTContext &)>
         Expectations) {
   ASSERT_THAT_ERROR(
-      test::checkDataflow<NoopAnalysis>(Code, Target,
-                                        [](ASTContext &Context, Environment &) {
-                                          return NoopAnalysis(Context);
-                                        },
-                                        std::move(Expectations),
-                                        {"-fsyntax-only", "-std=c++17"}),
+      test::checkDataflow<NoopAnalysis>(
+          Code, Target,
+            return NoopAnalysis(Context, /*ApplyBuiltinTransfer=*/false);
+          std::move(Expectations), {"-fsyntax-only", "-std=c++17"}),
       llvm::Succeeded());
 }
 
 TEST(ProgramPointAnnotations, NoAnnotations) {
   ::testing::MockFunction<void(
       llvm::ArrayRef<
           std::pair<std::string, DataflowAnalysisState<NoopLattice>>>,
       ASTContext &)>

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

 using ::testing::IsNull;
 using ::testing::NotNull;
 using ::testing::Pair;
 
 class TransferTest : public ::testing::Test {
 protected:
   template <typename Matcher>
   void runDataflow(llvm::StringRef Code, Matcher Match,
-                   LangStandard::Kind Std = LangStandard::lang_cxx17) {
+                   LangStandard::Kind Std = LangStandard::lang_cxx17,
+                   bool ApplyBuiltinTransfer = true) {
     ASSERT_THAT_ERROR(
         test::checkDataflow<NoopAnalysis>(
             Code, "target",
-            [](ASTContext &C, Environment &) { return NoopAnalysis(C); },
+            [ApplyBuiltinTransfer](ASTContext &C, Environment &) {
+              return NoopAnalysis(C, ApplyBuiltinTransfer);
+            },
             [&Match](
                 llvm::ArrayRef<
                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
                     Results,
                 ASTContext &ASTCtx) { Match(Results, ASTCtx); },
             {"-fsyntax-only", "-fno-delayed-template-parsing",
              "-std=" +
                  std::string(
                      LangStandard::getLangStandardForKind(Std).getName())}),
         llvm::Succeeded());
   }
 };
 
+TEST_F(TransferTest, IntVarDeclNotTrackedWhenTransferDisabled) {
+  std::string Code = R"(
+    void target() {
+      int 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());
+
+        EXPECT_EQ(Env.getStorageLocation(*FooDecl, SkipPast::None), nullptr);
+      },
+      LangStandard::lang_cxx17,
+      /*ApplyBuiltinTransfer=*/false);
+}
+
 TEST_F(TransferTest, IntVarDecl) {
   std::string Code = R"(
     void target() {
       int Foo;
       // [[p]]
     }
   )";
   runDataflow(

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

 using ::testing::NotNull;
 using ::testing::Pair;
 using ::testing::Test;
 using ::testing::UnorderedElementsAre;
 
 template <typename AnalysisT>
 class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
 public:
+  AnalysisCallback(AnalysisT (*MakeAnalysis)(ASTContext &))
+      : MakeAnalysis(MakeAnalysis) {}
   void run(const ast_matchers::MatchFinder::MatchResult &Result) override {
     assert(BlockStates.empty());
 
     const auto *Func = Result.Nodes.getNodeAs<FunctionDecl>("func");
     assert(Func != nullptr);
 
     Stmt *Body = Func->getBody();
     assert(Body != nullptr);
 
     auto CFCtx = llvm::cantFail(
         ControlFlowContext::build(nullptr, Body, Result.Context));
 
-    AnalysisT Analysis(*Result.Context);
+    AnalysisT Analysis = MakeAnalysis(*Result.Context);
     DataflowAnalysisContext DACtx;
     Environment Env(DACtx);
     BlockStates = runDataflowAnalysis(CFCtx, Analysis, Env);
   }
 
+  AnalysisT (*MakeAnalysis)(ASTContext &);
   std::vector<
       llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
       BlockStates;
 };
 
 template <typename AnalysisT>
 std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
-runAnalysis(llvm::StringRef Code) {
+runAnalysis(llvm::StringRef Code, AnalysisT (*MakeAnalysis)(ASTContext &)) {
   std::unique_ptr<ASTUnit> AST =
       tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
 
-  AnalysisCallback<AnalysisT> Callback;
+  AnalysisCallback<AnalysisT> Callback(MakeAnalysis);
   ast_matchers::MatchFinder Finder;
   Finder.addMatcher(
       ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"),
       &Callback);
   Finder.matchAST(AST->getASTContext());
 
   return Callback.BlockStates;
 }
 
 TEST(DataflowAnalysisTest, NoopAnalysis) {
-  auto BlockStates = runAnalysis<NoopAnalysis>(R"(
-    void target() {}
-  )");
+  auto BlockStates = runAnalysis<NoopAnalysis>(
+      "void target() {}", [](ASTContext &C) { return NoopAnalysis(C, false); });
   EXPECT_EQ(BlockStates.size(), 2u);
   EXPECT_TRUE(BlockStates[0].hasValue());
   EXPECT_TRUE(BlockStates[1].hasValue());
 }
 
 struct NonConvergingLattice {
   int State;
 
   bool operator==(const NonConvergingLattice &Other) const {
     return State == Other.State;
   }
 
   LatticeJoinEffect join(const NonConvergingLattice &Other) {
     if (Other.State == 0)
       return LatticeJoinEffect::Unchanged;
     State += Other.State;
     return LatticeJoinEffect::Changed;
   }
 };
 
 class NonConvergingAnalysis
     : public DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice> {
 public:
   explicit NonConvergingAnalysis(ASTContext &Context)
-      : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(Context) {
-  }
+      : DataflowAnalysis<NonConvergingAnalysis, NonConvergingLattice>(
+            Context,
+            /*ApplyBuiltinTransfer=*/false) {}
 
   static NonConvergingLattice initialElement() { return {0}; }
 
   void transfer(const Stmt *S, NonConvergingLattice &E, Environment &Env) {
     ++E.State;
   }
 };
 
 TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
-  auto BlockStates = runAnalysis<NonConvergingAnalysis>(R"(
+  auto BlockStates = runAnalysis<NonConvergingAnalysis>(
+      R"(
     void target() {
       while(true) {}
     }
-  )");
+  )",
+      [](ASTContext &C) { return NonConvergingAnalysis(C); });
   EXPECT_EQ(BlockStates.size(), 4u);
   EXPECT_TRUE(BlockStates[0].hasValue());
   EXPECT_TRUE(BlockStates[1].hasValue());
   EXPECT_TRUE(BlockStates[2].hasValue());
   EXPECT_TRUE(BlockStates[3].hasValue());
 }
 
 struct FunctionCallLattice {