[clang][dataflow] Implement a basic algorithm for dataflow analysis

[sgatev]

Summary

This is part of the implementation of the dataflow analysis framework.
See "[RFC] A dataflow analysis framework for Clang AST" on cfe-dev.

[sgatev]

Minor changes to parameter names.

[gribozavr2]

LGTM but deferring approval to @xazax.hun .

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

31

Add assert(BlockStates.empty()); ?

59

Please prefer StringRef to const char * if possible.

[xazax.hun]

This patch looks good to me, most of my comments are things to consider in follow-up patches.

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

32

Alternatively, if we have a bottom, forall e in lattice join(e, bottom) == e, so we do not really need optionals and can express nodes that do not contribute to the state using the bottom value. (Or using top, depending on the orientation for our lattices, unfortunately the literature is using both orientations which is really confusing.)

I'm fine with the current approach, but I'd love to see a function level comment about nullopts representing nodes that were not yet evaluated.

35

I did not catch this earlier, but I wonder if we should pass the block in to typeErasedInitialElement. There are some analysis where the initial element might be different for certain nodes. E.g. here is the algorithms for computing dominators from wikipedia:

// dominator of the start node is the start itself
Dom(n0) = {n0}
// for all other nodes, set all nodes as the dominators
for each n in N - {n0}
    Dom(n) = N;
// iteratively eliminate nodes that are not dominators
while changes in any Dom(n)
    for each n in N - {n0}:
        Dom(n) = {n} union with intersection over Dom(p) for all p in pred(n)

Here the initial analysis state for the entry node differs from the initial state for the rest of the nodes.

69

I think this is fine for now, but in general, CFGStmt is probably not the only kind of CFGElement that we want to evaluate.

E.g., CFGImplicitDtor or CFGLifetimeEnds might also be interesting in the future if we want to find certain problems, like dereferencing an invalid pointer. I'd love to see a FIXME.

118

I'd strongly suggest setting up some statistics in the future: https://llvm.org/docs/ProgrammersManual.html#the-statistic-class-stats-option

Having some counters, like how many function timed out, what is the average iteration count and so on could be very handy to monitor the performance of the analysis before and after some changes (both for client analyses or for the framework itself).

148

If a block still has None as its state at this point, it is unreachable in the CFG. One option is to ignore them, as we do at the moment and it is completely fine and should not change this patch. But for some analysis in the future, we might want to check dead code as well (it might be dead for the current platform due to some preprocessor defines but alive for some other). E.g., it would also be nice to diagnose a null dereference in a block that was not reached.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

38–41

I wonder if the dataflow analysis framework should provide a factory that that returns a CFG::BuildOptions which is a good default for most clients. Can be in a follow-up patch, or completely ignored. Or maybe even a convenience function running the analysis on a function definition without the user having to know about the CFG.

[ymandel]

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

2

Why create a new sub directory? From what I've seen elsewhere, it seems uncommon. I'm fine either way, but want to be sure we have a good reason for differing.

[sgatev]

Address reviewers' comments.

[sgatev]

Thanks everyone!

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

32

Right. Perhaps we can use Analysis.typeErasedInitialElement() and InitEnv to express states of blocks that were not evaluated? In practice, these often coincide with bottom. In that case we're loosing the ability to understand which blocks have been evaluated. An alternative, as you mentioned, would be to require an additional bottom element to be provided by the analysis. I added a function level comment for now and will consider this a bit more.

35

Good point, though, I'm not sure if this algorithm is the best choice for such an analysis. It seems that in that case we don't need to evaluate the statements in the basic blocks, right? Perhaps we can generalize the algorithm or offer a separate one for more efficient implementation of such analyses. I added a FIXME and will consider this a bit more.

148

I added a FIXME to consider evaluating unreachable blocks. However, I think it's preferable to run the analysis with the same configuration that will be used to compile the code. Do you think this isn't always possible/practical?

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

2

I created the directory to match the structure in llvm-project/clang/include/clang/Analysis/FlowSensitive and llvm-project/clang/lib/Analysis/FlowSensitive. In general, I think it'd be easier to find related code if it's structured similarly. If this doesn't follow the established practices for the project I'd be happy to change it.

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

31

Done, and also changed the other ASSERT_THAT to assert.

38–41

I added a FIXME. A utility that runs an analysis on a function definition would mean that the CFG will need to be built each time we want to run an analysis which could be wasteful if we want to run several analyses on the same CFG. Perhaps we can consider providing a function that builds the CFG using default options and returns it, possibly wrapped in another type.

[xazax.hun]

Thanks!

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

35

Dominators is one example, but there might be other analyses where the initial state differs :)
Since this change is really easy to make, I'm ok deferring this until we see the actual need.

[ymandel]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

31

should this be declared in the header? If not, please mark static.

62

Please declare this function in the header.

[sgatev]

Declare transferBlock in the header.

[sgatev]

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

31

Marked it as static.

[thakis]

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

2

I'm also confused by this.

Would this work:

% git diff
diff --git a/clang/lib/Analysis/CMakeLists.txt b/clang/lib/Analysis/CMakeLists.txt
index 16e3f474060c..eec02b31a9a8 100644
--- a/clang/lib/Analysis/CMakeLists.txt
+++ b/clang/lib/Analysis/CMakeLists.txt
@@ -18,6 +18,7 @@ add_clang_library(clangAnalysis
   CodeInjector.cpp
   Dominators.cpp
   ExprMutationAnalyzer.cpp
+  FlowSensitive/TypeErasedDataflowAnalysis.cpp
   IssueHash.cpp
   LiveVariables.cpp
   MacroExpansionContext.cpp
@@ -44,4 +45,3 @@ add_clang_library(clangAnalysis
   )

 add_subdirectory(plugins)
-add_subdirectory(FlowSensitive)
diff --git a/clang/unittests/Analysis/CMakeLists.txt b/clang/unittests/Analysis/CMakeLists.txt
index 7e2a00b96057..f1cb402268c0 100644
--- a/clang/unittests/Analysis/CMakeLists.txt
+++ b/clang/unittests/Analysis/CMakeLists.txt
@@ -8,6 +8,7 @@ add_clang_unittest(ClangAnalysisTests
   CFGTest.cpp
   CloneDetectionTest.cpp
   ExprMutationAnalyzerTest.cpp
+  FlowSensitive/TypeErasedDataflowAnalysisTest.cpp
   MacroExpansionContextTest.cpp
   )

Or do the flow-sensitive analyses have different library dependencies and there are places that want to depend on analysis without the flow sensitive bits or the other way round?

(Why are these files in a subdirectory at all?)

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

 //  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
 //  program at given program points.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 #define LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H
 
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+
 namespace clang {
 namespace dataflow {
 
 /// Holds the state of the program (store and heap) at a given program point.
-class Environment {};
+class Environment {
+public:
+  bool operator==(const Environment &) const { return true; }
+
+  LatticeJoinEffect join(const Environment &) {
+    return LatticeJoinEffect::Unchanged;
+  }
+};
 
 } // namespace dataflow
 } // namespace clang
 
 #endif // LLVM_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWENVIRONMENT_H

clang/include/clang/Analysis/FlowSensitive/DataflowWorklist.h

struct ReversePostOrderCompare {
   }
 };
 
 /// A worklist implementation for forward dataflow analysis. The enqueued
 /// blocks will be dequeued in reverse post order. The worklist cannot contain
 /// the same block multiple times at once.
 struct ForwardDataflowWorklist
     : DataflowWorklistBase<ReversePostOrderCompare, 20> {
+  ForwardDataflowWorklist(const CFG &Cfg, PostOrderCFGView *POV)
+      : DataflowWorklistBase(Cfg, POV,
+                             ReversePostOrderCompare{POV->getComparator()}) {}
+
   ForwardDataflowWorklist(const CFG &Cfg, AnalysisDeclContext &Ctx)
-      : DataflowWorklistBase(
-            Cfg, Ctx.getAnalysis<PostOrderCFGView>(),
-            ReversePostOrderCompare{
-                Ctx.getAnalysis<PostOrderCFGView>()->getComparator()}) {}
+      : ForwardDataflowWorklist(Cfg, Ctx.getAnalysis<PostOrderCFGView>()) {}
 
   void enqueueSuccessors(const CFGBlock *Block) {
     for (auto B : Block->succs())
       enqueueBlock(B);
   }
 };
 
 /// A worklist implementation for backward dataflow analysis. The enqueued

clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp

 //===- TypeErasedDataflowAnalysis.cpp -------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 //  This file defines type-erased base types and functions for building dataflow
 //  analyses that run over Control-Flow Graphs (CFGs).
 //
 //===----------------------------------------------------------------------===//
 
+#include <utility>
 #include <vector>
 
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowWorklist.h"
 #include "clang/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.h"
+#include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/Support/raw_ostream.h"
 
-using namespace clang;
-using namespace dataflow;
+namespace clang {
+namespace dataflow {
+
+/// Computes the input state for a given basic block by joining the output
+/// states of its predecessors.
+///
+/// Requirements:
+///
+///   All predecessors of `Block` except those with loop back edges must have
+///   already been transferred. States in `BlockStates` that are set to
+///   `llvm::None` represent basic blocks that are not evaluated yet.
+TypeErasedDataflowAnalysisState computeBlockInputState(
+    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
+    const CFGBlock &Block, const Environment &InitEnv,
+    TypeErasedDataflowAnalysis &Analysis) {
+  // FIXME: Consider passing `Block` to `Analysis.typeErasedInitialElement()`
+  // to enable building analyses like computation of dominators that initialize
+  // the state of each basic block differently.
+  TypeErasedDataflowAnalysisState State = {Analysis.typeErasedInitialElement(),
+                                           InitEnv};
+  for (const CFGBlock *Pred : Block.preds()) {
+    // Skip if the `Block` is unreachable or control flow cannot get past it.
+    if (!Pred || Pred->hasNoReturnElement())
+      continue;
+
+    // Skip if `Pred` was not evaluated yet. This could happen if `Pred` has a
+    // loop back edge to `Block`.
+    const llvm::Optional<TypeErasedDataflowAnalysisState> &MaybePredState =
+        BlockStates[Pred->getBlockID()];
+    if (!MaybePredState.hasValue())
+      continue;
+
+    const TypeErasedDataflowAnalysisState &PredState =
+        MaybePredState.getValue();
+    Analysis.joinTypeErased(State.Lattice, PredState.Lattice);
+    State.Env.join(PredState.Env);
+  }
+  return State;
+}
+
+/// Transfers the state of a basic block by evaluating each of its statements in
+/// the context of `Analysis` and the states of its predecessors that are
+/// available in `BlockStates`.
+///
+/// Requirements:
+///
+///   All predecessors of `Block` except those with loop back edges must have
+///   already been transferred. States in `BlockStates` that are set to
+///   `llvm::None` represent basic blocks that are not evaluated yet.
+TypeErasedDataflowAnalysisState transferBlock(
+    std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> &BlockStates,
+    const CFGBlock &Block, const Environment &InitEnv,
+    TypeErasedDataflowAnalysis &Analysis) {
+  TypeErasedDataflowAnalysisState State =
+      computeBlockInputState(BlockStates, Block, InitEnv, Analysis);
+  for (const CFGElement &Element : Block) {
+    // FIXME: Evaluate other kinds of `CFGElement`.
+    const llvm::Optional<CFGStmt> Stmt = Element.getAs<CFGStmt>();
+    if (!Stmt.hasValue())
+      continue;
+
+    // FIXME: Evaluate the statement contained in `Stmt`.
+
+    State.Lattice = Analysis.transferTypeErased(Stmt.getValue().getStmt(),
+                                                State.Lattice, State.Env);
+  }
+  return State;
+}
 
 std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>>
 runTypeErasedDataflowAnalysis(const CFG &Cfg,
                               TypeErasedDataflowAnalysis &Analysis,
                               const Environment &InitEnv) {
   // FIXME: Consider enforcing that `Cfg` meets the requirements that
   // are specified in the header. This could be done by remembering
   // what options were used to build `Cfg` and asserting on them here.
 
-  // FIXME: Implement work list-based algorithm to compute the fixed
-  // point of `Analysis::transform` for every basic block in `Cfg`.
-  return {};
+  PostOrderCFGView POV(&Cfg);
+  ForwardDataflowWorklist Worklist(Cfg, &POV);
+
+  std::vector<llvm::Optional<TypeErasedDataflowAnalysisState>> BlockStates;
+  BlockStates.resize(Cfg.size(), llvm::None);
+
+  // The entry basic block doesn't contain statements so it can be skipped.
+  const CFGBlock &Entry = Cfg.getEntry();
+  BlockStates[Entry.getBlockID()] = {Analysis.typeErasedInitialElement(),
+                                     InitEnv};
+  Worklist.enqueueSuccessors(&Entry);
+
+  // Bugs in lattices and transfer functions can prevent the analysis from
+  // converging. To limit the damage (infinite loops) that these bugs can cause,
+  // limit the number of iterations.
+  // FIXME: Consider making the maximum number of iterations configurable.
+  // FIXME: Set up statistics (see llvm/ADT/Statistic.h) to count average number
+  // of iterations, number of functions that time out, etc.
+  unsigned Iterations = 0;
+  static constexpr unsigned MaxIterations = 1 << 16;
+  while (const CFGBlock *Block = Worklist.dequeue()) {
+    if (++Iterations > MaxIterations) {
+      llvm::errs() << "Maximum number of iterations reached, giving up.\n";
+      break;
+    }
+
+    const llvm::Optional<TypeErasedDataflowAnalysisState> &OldBlockState =
+        BlockStates[Block->getBlockID()];
+    TypeErasedDataflowAnalysisState NewBlockState =
+        transferBlock(BlockStates, *Block, InitEnv, Analysis);
+
+    if (OldBlockState.hasValue() &&
+        Analysis.isEqualTypeErased(OldBlockState.getValue().Lattice,
+                                   NewBlockState.Lattice) &&
+        OldBlockState->Env == NewBlockState.Env) {
+      // The state of `Block` didn't change after transfer so there's no need to
+      // revisit its successors.
+      continue;
     }
+
+    BlockStates[Block->getBlockID()] = std::move(NewBlockState);
+
+    // Do not add unreachable successor blocks to `Worklist`.
+    if (Block->hasNoReturnElement())
+      continue;
+
+    Worklist.enqueueSuccessors(Block);
+  }
+  // FIXME: Consider evaluating unreachable basic blocks (those that have a
+  // state set to `llvm::None` at this point) to also analyze dead code.
+
+  return BlockStates;
+}
+
+} // namespace dataflow
+} // namespace clang

clang/unittests/Analysis/CMakeLists.txt

clang_target_link_libraries(ClangAnalysisTests
   clangTesting
   clangTooling
   )
 
 target_link_libraries(ClangAnalysisTests
   PRIVATE
   LLVMTestingSupport
   )
+
+add_subdirectory(FlowSensitive)

clang/unittests/Analysis/FlowSensitive/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Support
+  )
+
+add_clang_unittest(ClangAnalysisFlowSensitiveTests
+  TypeErasedDataflowAnalysisTest.cpp
+  )
+
+clang_target_link_libraries(ClangAnalysisFlowSensitiveTests
+  PRIVATE
+  clangAnalysis
+  clangAnalysisFlowSensitive
+  clangAST
+  clangASTMatchers
+  clangBasic
+  clangFrontend
+  clangTesting
+  clangTooling
+  )
+

clang/unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp

+//===- unittests/Analysis/FlowSensitive/TypeErasedDataflowAnalysisTest.cpp ===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/Decl.h"
+#include "clang/ASTMatchers/ASTMatchFinder.h"
+#include "clang/ASTMatchers/ASTMatchers.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
+#include "clang/Analysis/FlowSensitive/DataflowLattice.h"
+#include "clang/Tooling/Tooling.h"
+#include "llvm/ADT/StringRef.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+#include <cassert>
+#include <memory>
+#include <vector>
+
+using namespace clang;
+using namespace dataflow;
+
+template <typename AnalysisT>
+class AnalysisCallback : public ast_matchers::MatchFinder::MatchCallback {
+public:
+  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);
+
+    // FIXME: Consider providing a utility that returns a `CFG::BuildOptions`
+    // which is a good default for most clients or a utility that directly
+    // builds the `CFG` using default `CFG::BuildOptions`.
+    CFG::BuildOptions Options;
+    Options.AddImplicitDtors = true;
+    Options.AddTemporaryDtors = true;
+    Options.setAllAlwaysAdd();
+
+    std::unique_ptr<CFG> Cfg =
+        CFG::buildCFG(nullptr, Body, Result.Context, Options);
+    assert(Cfg != nullptr);
+
+    AnalysisT Analysis(*Result.Context);
+    Environment Env;
+    BlockStates = runDataflowAnalysis(*Cfg, Analysis, Env);
+  }
+
+  std::vector<
+      llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
+      BlockStates;
+};
+
+template <typename AnalysisT>
+std::vector<llvm::Optional<DataflowAnalysisState<typename AnalysisT::Lattice>>>
+runAnalysis(llvm::StringRef Code) {
+  std::unique_ptr<ASTUnit> AST =
+      tooling::buildASTFromCodeWithArgs(Code, {"-std=c++11"});
+
+  AnalysisCallback<AnalysisT> Callback;
+  ast_matchers::MatchFinder Finder;
+  Finder.addMatcher(
+      ast_matchers::functionDecl(ast_matchers::hasName("target")).bind("func"),
+      &Callback);
+  Finder.matchAST(AST->getASTContext());
+
+  return Callback.BlockStates;
+}
+
+class NoopLattice {
+public:
+  bool operator==(const NoopLattice &) const { return true; }
+
+  LatticeJoinEffect join(const NoopLattice &) {
+    return LatticeJoinEffect::Unchanged;
+  }
+};
+
+class NoopAnalysis : public DataflowAnalysis<NoopAnalysis, NoopLattice> {
+public:
+  NoopAnalysis(ASTContext &Context)
+      : DataflowAnalysis<NoopAnalysis, NoopLattice>(Context) {}
+
+  static NoopLattice initialElement() { return {}; }
+
+  NoopLattice transfer(const Stmt *S, const NoopLattice &E, Environment &Env) {
+    return {};
+  }
+};
+
+TEST(DataflowAnalysisTest, NoopAnalysis) {
+  auto BlockStates = runAnalysis<NoopAnalysis>(R"(
+    void target() {}
+  )");
+  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) {
+  }
+
+  static NonConvergingLattice initialElement() { return {0}; }
+
+  NonConvergingLattice transfer(const Stmt *S, const NonConvergingLattice &E,
+                                Environment &Env) {
+    return {E.State + 1};
+  }
+};
+
+TEST(DataflowAnalysisTest, NonConvergingAnalysis) {
+  auto BlockStates = runAnalysis<NonConvergingAnalysis>(R"(
+    void target() {
+      while(true) {}
+    }
+  )");
+  EXPECT_EQ(BlockStates.size(), 4u);
+  EXPECT_FALSE(BlockStates[0].hasValue());
+  EXPECT_TRUE(BlockStates[1].hasValue());
+  EXPECT_TRUE(BlockStates[2].hasValue());
+  EXPECT_TRUE(BlockStates[3].hasValue());
+}