[clang][dataflow] Add base types for building dataflow analyses

[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]

Fix ifndefs.

[sgatev]

Use triple slash at the start of declaration comments.

[ymandel]

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

22–23

It's more common in .cpp files to use using declarations instead:

using clang;
using dataflow;

[sgatev]

Add using namespace declarations in the cpp file.

[xazax.hun]

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

49

Does the Dynamic in the suffix refer to the fact this is using type erasure as opposed to templates?

I have multiple questions at this point:

• Why do we prefer type erasure over generic programming?
• Do you plan to have non-dynamic counterparts?

Nit: having Dynamic both in the class name and in the method names sounds overly verbose to me.
Nit: please add a comment what dynamic refers to in the name,

141

Do we need a ctor? Or is this a workaround for aggregate initialization not working well with certain library facilities?

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

27

Is there a way to query how the CFG was built? Adding an assert to see if setAlwaysAdd was set might be useful.

[sgatev]

Remove unnecessary constructor.

[sgatev]

Add a note about asserting the requirements of the CFG object.

[sgatev]

Document the role of the "Dynamic" suffix in the name of DataflowAnalysisDynamic and its members.

[sgatev]

Put typed and type-erased interfaces in separate files.

[sgatev]

Rename Environment.h to DataflowEnvironment.h.

[sgatev]

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

49

Right. The "Dynamic" suffix emphasizes the type-erased nature of the class and its members and is used to differentiate them from their typed counterparts in DataflowAnalysis. I added this to the documentation of the type. I also split the typed and type-erased interfaces in separate files. Users of the framework shouldn't need to interact with types and functions from DataflowAnalysisDynamic.h.

The names are verbose, but should be used in relatively few internal places in the framework. Currently, we have one call site for each of the methods of DataflowAnalysisDynamic. Nevertheless, if you have ideas for better names I'd be happy to change them.

The reason we went with a type-erased layer is to avoid pulling a lot of code in the templates. Over time the implementation got cleaner and as I'm preparing these patches I see some opportunities to simplify it further. However, it's still non-trivial amount of code. I think we should revisit this decision at some point and consider having entirely template-based implementation of the algorithm. I personally don't see clear benefits of one approach over the other at this point. If you have strong preference for using templates, we can consider going down that route now.

141

We don't really need it at this point. Removed.

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

27

Good point. I believe there isn't a way to do that currently, but this is something we should consider implementing. I added a FIXME.

[xazax.hun]

Thanks, it looks good to me. Most of my comments are just brainstorming, exploring alternative ideas. Feel free to ignore some/all of them.

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

49

Thanks for the explanation! I don't have a strong preference, we could stick with the type-erased version unless we see some reason to change in the future. However, I don't see much value in the "Dynamic" suffix for the method names. What do you think about simply dropping them?

95

If I understand this correctly, this could derive from DataflowAnalysisStateDynamic, it could just provide a getter function that casts the type erased lattice element to LatticeT, returning a reference to the contents of the any object. As a result, you would no longer need to do move/copy in runDataflowAnalysis. On the other hand, the user would need to call a getter to get out the lattice element. I guess we expect lattice elements to be relatively cheap to move. Feel free to leave this unchanged, it is more of an observation.

103

While it is probably obvious to most of us, I wonder if it is obvious to all future readers that the block IDs are the indices of the vector. Depending on how beginner-friendly do we want these comments to be we could make that more explicit.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h

45 ↗

(On Diff #389774)

Alternatively, we could replace Dynamic with TypeErased in the class name making the comment redundant.

[sgatev]

Replace "Dynamic" with "TypeErased" in the names of types and their members.

[sgatev]

Minor tweaks to documentation.

[sgatev]

Thanks Gábor and Dmitri!

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

49

Well, the only reason I see to have the suffix is to differentiate the type-erased methods from the methods of the concrete dataflow analysis class that will derive from DataflowAnalysis. For example, we could have

class ConstantPropagationAnalysis : public DataflowAnalysis<
  ConstantPropagationAnalysis, ConstantPropagationLattice> {
public:
  ConstantPropagationLattice initialElement();

  ConstantPropagationLattice transfer(
    const Stmt *, const ConstantPropagationLattice &, Environment &);
};

In this setup ConstantPropagationAnalysis has two methods that return the initial element and two methods that perform the transfer function - one pair in the definition and one pair inherited from TypeErasedDataflowAnalysis. For the initial element we need to use different names as the two methods differ only in their return types. For the transfer function we could use the same name and rely on overload resolution, however it seems that's not recommended - https://clang.llvm.org/docs/DiagnosticsReference.html#woverloaded-virtual. The names of the remaining methods (joinTypeErased and isEqualTypeErased) have the suffix for consistency.

95

Acknowledged. I'll keep this option in mind. For now I suggest we keep the typed and type-erased structs separate if possible and if the cost isn't too high.

103

Let's make it clear. I added a note on that.

clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisDynamic.h

45 ↗

(On Diff #389774)

That would be appropriate indeed. I updated the names.

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

+//===- DataflowAnalysis.h ---------------------------------------*- C++ -*-===//
+//
+// 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 base types for building dataflow analyses that run over
+//  Control-Flow Graphs (CFGs).
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LOCAL_GOOGLE_HOME_SGATEV_LLVM_PROJECT_DATAFLOW_CLANG_INCLUDE_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H_
+#define LOCAL_GOOGLE_HOME_SGATEV_LLVM_PROJECT_DATAFLOW_CLANG_INCLUDE_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H_
+
+#include <cassert>
+#include <utility>
+#include <vector>
+
+#include "clang/AST/ASTContext.h"
+#include "clang/AST/Stmt.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/Environment.h"
+#include "llvm/ADT/Any.h"
+#include "llvm/ADT/Optional.h"
+
+namespace clang {
+namespace dataflow {
+
+// Type-erased lattice element container.
+//
+// Requirements:
+//
+//  The type of the object stored in the container must be a bounded
+//  join-semilattice.
+struct AnyLatticeElement {
+  llvm::Any Value;
+};
+
+// Effect indicating whether a lattice join operation resulted in a new value.
+enum class LatticeJoinEffect {
+  Unchanged,
+  Changed,
+};
+
+// Type-erased base class for dataflow analyses built on a single lattice type.
+class DataflowAnalysisDynamic {
+public:
+  // Returns the `ASTContext` that is used by the analysis.
+  virtual ASTContext &getASTContext() = 0;
+
+  // Returns a lattice element that models the initial state of a basic block.
+  virtual AnyLatticeElement initialElementDynamic() = 0;
+
+  // Joins two 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 joinDynamic(AnyLatticeElement &,
+                                        const AnyLatticeElement &) = 0;
+
+  // Returns true if and only if the two given lattice elements are equal.
+  virtual bool isEqualDynamic(const AnyLatticeElement &,
+                              const AnyLatticeElement &) = 0;
+
+  // Applies the analysis transfer function for a given statement and lattice
+  // element.
+  virtual AnyLatticeElement
+  transferDynamic(const Stmt *, const AnyLatticeElement &, Environment &) = 0;
+};
+
+// Base class template for dataflow analyses built on a single lattice type.
+//
+// Requirements:
+//
+//  `Derived` must be derived from a specialization of this class template and
+//  must provide the following public members:
+//   * `LatticeT InitialElement()` - returns a lattice element that models the
+//     initial state of a basic block;
+//   * `LatticeT Transfer(const Stmt*, const LatticeT&, Environment&)` - applies
+//     the analysis transfer function for a given statement and lattice element.
+//
+//  `LatticeT` is a bounded join-semilattice that is used by `Derived` and must
+//  provide the following public members:
+//   * `LatticeJoinEffect Join(const LatticeT&)` - joins the object and the
+//     argument by computing their least upper bound, modifies the object if
+//     necessary, and returns an effect indicating whether any changes were made
+//     to it;
+//   * `bool operator==(const LatticeT&) const` - returns true if and only if
+//     the object is equal to the argument.
+template <typename Derived, typename LatticeT>
+class DataflowAnalysis : public DataflowAnalysisDynamic {
+public:
+  // Bounded join-semilattice that is used in the analysis.
+  using Lattice = LatticeT;
+
+  explicit DataflowAnalysis(ASTContext &Context) : Context(Context) {}
+
+  ASTContext &getASTContext() final { return Context; }
+
+  AnyLatticeElement initialElementDynamic() final {
+    return AnyLatticeElement{static_cast<Derived *>(this)->initialElement()};
+  }
+
+  LatticeJoinEffect joinDynamic(AnyLatticeElement &E1,
+                                const AnyLatticeElement &E2) final {
+    Lattice *L1 = llvm::any_cast<Lattice>(&E1.Value);
+    assert(L1 != nullptr);
+    const Lattice *L2 = llvm::any_cast<Lattice>(&E2.Value);
+    assert(L2 != nullptr);
+    return L1->join(*L2);
+  }
+
+  bool isEqualDynamic(const AnyLatticeElement &E1,
+                      const AnyLatticeElement &E2) final {
+    const Lattice *L1 = llvm::any_cast<Lattice>(&E1.Value);
+    assert(L1 != nullptr);
+    const Lattice *L2 = llvm::any_cast<Lattice>(&E2.Value);
+    assert(L2 != nullptr);
+    return *L1 == *L2;
+  }
+
+  AnyLatticeElement transferDynamic(const Stmt *Stmt,
+                                    const AnyLatticeElement &E,
+                                    Environment &Environment) final {
+    const Lattice *L = llvm::any_cast<Lattice>(&E.Value);
+    assert(L != nullptr);
+    return AnyLatticeElement{
+        static_cast<Derived *>(this)->transfer(Stmt, *L, Environment)};
+  }
+
+private:
+  ASTContext &Context;
+};
+
+// Model of the program at a given program point.
+struct DataflowAnalysisState {
+  DataflowAnalysisState(AnyLatticeElement Lattice, Environment Env)
+      : Lattice(std::move(Lattice)), Env(std::move(Env)) {}
+
+  // Model of a program property.
+  AnyLatticeElement Lattice;
+
+  // Model of the state of the program (store and heap).
+  Environment Env;
+};
+
+// Performs dataflow analysis and returns a mapping from basic block IDs to
+// dataflow analysis states that model the respective basic blocks.
+//
+// Requirements:
+//
+//  `Cfg` must have been built with `CFG::BuildOptions::setAllAlwaysAdd()` to
+//  ensure that all sub-expressions in a basic block are evaluated.
+std::vector<llvm::Optional<DataflowAnalysisState>>
+runDataflowAnalysis(const CFG &Cfg, DataflowAnalysisDynamic &Analysis,
+                    const Environment &InitEnv);
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LOCAL_GOOGLE_HOME_SGATEV_LLVM_PROJECT_DATAFLOW_CLANG_INCLUDE_CLANG_ANALYSIS_FLOWSENSITIVE_DATAFLOWANALYSIS_H_

clang/include/clang/Analysis/FlowSensitive/Environment.h

+//===-- Environment.h -------------------------------------------*- C++ -*-===//
+//
+// 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 an Environment class that is used by dataflow analyses
+//  that run over Control-Flow Graphs (CFGs) to keep track of the state of the
+//  program at given program points.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LOCAL_GOOGLE_HOME_SGATEV_LLVM_PROJECT_DATAFLOW_CLANG_INCLUDE_CLANG_ANALYSIS_FLOWSENSITIVE_ENVIRONMENT_H_
+#define LOCAL_GOOGLE_HOME_SGATEV_LLVM_PROJECT_DATAFLOW_CLANG_INCLUDE_CLANG_ANALYSIS_FLOWSENSITIVE_ENVIRONMENT_H_
+
+namespace clang {
+namespace dataflow {
+
+// Holds the state of the program (store and heap) at a given program point.
+class Environment {};
+
+} // namespace dataflow
+} // namespace clang
+
+#endif // LOCAL_GOOGLE_HOME_SGATEV_LLVM_PROJECT_DATAFLOW_CLANG_INCLUDE_CLANG_ANALYSIS_FLOWSENSITIVE_ENVIRONMENT_H_

clang/lib/Analysis/CMakeLists.txt

add_clang_library(clangAnalysis
   clangBasic
   clangLex
 
   DEPENDS
   omp_gen
   )
 
 add_subdirectory(plugins)
+add_subdirectory(FlowSensitive)

clang/lib/Analysis/FlowSensitive/CMakeLists.txt

+add_clang_library(clangAnalysisFlowSensitive
+  DataflowAnalysis.cpp
+
+  LINK_LIBS
+  clangAnalysis
+  clangAST
+  )

clang/lib/Analysis/FlowSensitive/DataflowAnalysis.cpp

+//===- DataflowAnalysis.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 base types for building dataflow analyses that run over
+//  Control-Flow Graphs (CFGs).
+//
+//===----------------------------------------------------------------------===//
+
+#include <vector>
+
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/FlowSensitive/DataflowAnalysis.h"
+#include "clang/Analysis/FlowSensitive/Environment.h"
+#include "llvm/ADT/Optional.h"
+
+namespace clang {
+namespace dataflow {
+
+std::vector<llvm::Optional<DataflowAnalysisState>>
+runDataflowAnalysis(const CFG &Cfg, DataflowAnalysisDynamic &Analysis,
+                    const Environment &InitEnv) {
+  // FIXME: Implement work list-based algorithm to compute the fixed
+  // point of `Analysis::transform` for every basic block in `Cfg`.
+  return {};
+}
+
+} // namespace dataflow
+} // namespace clang